Zelf aan de slag met wiskundige technieken in AI: Associatie analyse

John Val/ Informatica/ Informatie/ Kunstmatige Intelligentie /associatie analyse

Editor: John Val

Inleiding Associatie analyse Verzamelingenleer Associatieregels Vragen 1 Apriori algoritme Vragen 2
bron:Lesmodule Big Data

Artificiële Intelligentie en data analyse

Toepassingen in Big Data kunnen, zoals we al hebben gezien het hoofdstuk Trends in deze AI cursus en de hoofdstukken Big Data en De kosten van Gratis uit de overkoepelende cursus Informatie, kan nuttig zijn maar ook een bedreiging vormen voor het individu. Maar hoe wordt de informatie geleverd door dit soort toepassingen verkregen uit de data?

De meeste van deze toepassingen gebruiken Artificiële Intelligentie om b.v. patronen te herkennen of groeperingen te maken, technieken die we zijn tegen gekomen in het hoofdstuk Technieken. In dit en de volgende hoofdstukken van de cursus gaan we een paar van die wiskundige technieken verder uitwerken. De berekeningen in dit hoofdstuk zijn niet heel erg ingewikkeld en zouden voor iedere leerling op havo en vwo uit te voeren moeten zijn. Lukt het niet stel dan vragen aan je docent.


Associatie analyse met behulp van verzamelingenleer

all cartoons

Bij associatie analyse is het de bedoeling dat we een gegeven set kenmerken (bijvoorbeeld jouw leeftijd, geslacht, ingetypte zoekopdracht, beluisterde muziek) kunnen koppelen aan een andere set kenmerken (bijvoorbeeld reclame passend bij doelgroep omschrijving, leeftijd en geslacht). Het resultaat van de associatie is dan de uitvoer van de toepassing (bijvoorbeeld de reclame die in de zoekmachine verschijnt, muziek die jij ook wel leuk zou vinden). Hieronder vind je voorbeelden van gebieden waarin associatie analyse gebruikt wordt:

Symbolen
Notatie Betekenis
$\in$ ’is een element van’, ’behoort tot’
$\subset$ ’is een deelverzameling van’
{,} accolades worden gebruikt om een verzameling aan te duiden
$\cap$ ’doorsnede’, het gemeenschappelijke deel van de twee verzamelingen
$\cup$ ’vereniging’, de elementen van de eerste en tweede verzameling worden samengenomen
$\#$ ’aantal’, $\# A$ is het aantal elementen in $A$.
$\Rightarrow$ ’implicatie’, al links waar is dan is ook rechts waar.

Verzamelingenleer

De wiskundige techniek die wordt gebruikt in associatie analyse is gebaseerd op wiskunde op verzamelingen, de zogenaamde verzamelingenleer. Laten we eens kijken wat verzamelingen zijn en hoe we die gaan inzetten in de associatie analyse.

Als leerling zit je in een klas, als voetballer zit je in een team, je ‘play list’ bevat een aantal leuke liedjes, .... Zo kunnen we nog een tijd doorgaan met het geven van voorbeelden. Voorbeelden die allemaal gaan over verzamelingen. In plaats van een ‘klas’, ‘team’, ‘play list’ spreken we van een verzameling ($V$) (ook wel: set). In een verzameling bevindt zich elementen (leerlingen, spelers, liedjes). We noteren een verzameling als volgt: $$V=\{v_{1},v_{2},v_{3},\cdots ,v_{n}\}.$$
Verzameling $V$ bevat elementen $v$ die we kunnen nummeren.

Een verzameling bestaat dus uit elementen, en als $x$ een element is van een verzameling $X$ noteren we dit wiskundig als $x \in X$.
We gebruiken accolades { en } om verzamelingen te noteren.
We gebruiken binnen de accolades het symbool | om elementen met bepaalde eigenschappen aan te geven, zoals in $\{x \in \mathbb{N} | x \, is\, deelbaar \, door \, 2 \}$, wat betekent dat $x$ een natuurlijk getal moet zijn en deelbaar door twee (de even getallen).
Zo is bijvoorbeeld $Winkelmandje = \{Melk , Brood , Kaas\}$ de verzameling Winkelmandje met de elementen Melk, Brood, en Kaas. Als we schrijven $Melk \in Winkelmandje$, dan zeggen we dus dat Melk in het winkelmandje aanwezig is.

Relaties tussen verzamelingen
$X \subset Y$
Y X

Als voor twee verzamelingen $X$ en $Y$ geldt dat elk element van $X$ ook een element is van $Y$, dan zeggen we dat $X$ een deelverzameling (subset) is van $Y$. Notatie: $X \subset Y$

Zo geldt bijvoorbeeld voor $X=\{Melk , Kaas\}$ en $Y = \{Melk , Brood , Kaas\}$ dat $X \subset Y$, $X$ is een deelverzameling van $Y$.

$X \cap Y$
X⋂Y Y X

De doorsnede (intersection) $X \cap Y$ van twee verzamelingen $X$ en $Y$ bestaat uit de gemeenschappelijke elementen van $X$ en $Y$. In de figuur links is de doorsnede het lichtgroene gebied.

Zo is bijvoorbeeld $\{Melk , Brood , Kaas\} \cap \{Melk , Brood , Pindakaas\}$ de verzameling met de elementen $Melk$ en $Brood$.
$\{Melk , Brood , Kaas\} \cap \{Melk , Brood , Pindakaas\} = \{Melk , Brood\}$

$X \cup Y$
X⋃Y Y X

De vereniging (union) $X \cup Y$ van twee verzamelingen $X$ en $Y$ bestaat uit de elementen die tot $X$, tot $Y$ of tot beide horen. In de figuur links bestaat de vereniging uit alle enigszins gele gebieden.

Zo is bijvoorbeeld $\{Melk , Brood , Kaas\}\cup\{Melk , Brood , Pindakaas\}$ de verzameling met de elementen $Kaas, Melk, Brood$ en $Pindakaas$. $\{Melk , Brood , Kaas\}\cup\{Melk , Brood , Pindakaas\} = \{Kaas, Melk, Brood, Pindakaas\}$

Voor een eindige verzameling $A$ definieren we $\#A$ als het aantal elementen in $A$. Zo is bijvoorbeeld $\#\{Chips,Zeep,Appels\}=3$.

Een element van een verzameling kan zelf ook een verzameling zijn. Zo bestaat de verzameling $C= \{ \{ Chips,Zeep,Appels \}, \{Chips,Zeep,Appels\}, \{Zeep,Bananen\},\{Chips,Zeep,Bananen\}\}$ uit vier elementen.

Een verzameling waarin de elementen ook weer verzamelingen zijn noemt men een collectie.

Nog voorbeeld van een collectie is de registratie van aankopen door acht klanten in een klein avondwinkeltje: $$D=\{\{banaan\},\{chips\},\{melk\},\{pruim\},\{banaan,rum\},\{chips,rum\},\{banaan,chips,melk\}, \{banaan,rum,melk,pruim\}\}$$ De collectie $D$ bestaat nu uit de inhoud van de acht winkelmandjes, van iedere klant één ofwel uit de verzamelingen:
$T1=\{banaan\}$,
$T2=\{chips\}$,
$T3=\{melk\}$,
$T4=\{pruim\}$,
$T5=\{banaan,rum\}$,
$T6=\{chips,rum\}$,
$T7=\{banaan,chips,melk\}$ en
$T8=\{banaan,rum,melk,pruim\}$

Associatieregels

Om uitspraken te kunnen doen over verbanden tussen verzamelingen en de waarde van die verzamelingen zijn de volgende definities van belang:

Bekijk weer de bovenstaande collectie winkelmandjes $D$ dan vind je bijvoorbeeld:

Nog een praktische toepassing: Bij marktonderzoek is de support van een stel artikelen (b.v. $K=\{televisie,surround set\}$) het aantal klanten dat al die artikelen koopt, meestal als percentage van het totaal aantal klanten.

Een stel artikelen $K$ met hoge support (boven een zekere drempel) heet frequent(ofwel ten opzichte van het totaal aantal klanten kopen veel klanten alle artikelen in $K$).

In de winkelmandjesanalyse kan niet altijd alles worden meegenomen. Vaak is men alleen geïnteresseerd in artikelen en combinaties van artikelen die vaak voorkomen en dus frequent

Een itemset is een deelverzameling van elementen uit de een collectie. Een $k$-itemset is een deelverzameling die $k$ elementen bevatten.

In de associatieanalyse (b.v. winkelmandjesanalyse) is het van belang dat men wil handelen op basis van associatieregels. Deze associatieregels stelt men dan op voor frequente deelverzamelingen. Maar dat is niet voldoende, de associatieregel met ook nog interessant zijn, ofwel deze moet een hoge waarschijnlijkheid hebben om maatregelen die genomen woorden op basis van die associatieregels te kunnen onderbouwen. Er moet voldoende dus vertrouwen zijn in de associatieregel. In de vaktaal heet dat de confidence van de associatieregel.

De confidence van de associatieregel $X \Rightarrow Y$ wordt berekend door de support van de vereniging van $X$ en $Y$ te delen door de support van $X$.
In notatievorm: $confidence(X \Rightarrow Y) = \frac{support(X \cap Y)}{support(X)}$
Omdat $\frac{support(X \cap Y)}{support(X)}=\frac{freq(X \cap Y)}{freq(X)}$, geldt ook: $confidence(X \Rightarrow Y) =\frac{freq(X \cap Y)}{freq(X)}$

Bij de winkelmandjesanalyse is de confidence een maat voor de kans dat iemand gaat $Y$ kopen, als gegeven is dat hij $X$ al in zijn winkelmandje heeft.

We gaan dit alles weer bekijken vanuit de collectie winkelmandjes $D$. Associatieregel: $\{banaan\} \Rightarrow \{ rum \}$
$confidence(\{ banaan\} \Rightarrow \{ rum \} )= \frac{support(\{ banaan,rum\})}{support(\{banaan\})}=\frac{\frac{2}{8}}{\frac{4}{8}}=\frac{1}{2}$ (=50%)
Want: $support(\{ banaan,rum\})= \frac{2}{8}$ en $support(\{banaan\})= \frac{4}{8}$


Apriori algoritme

Er bestaan veel algoritmes om associatieregels te ontdekken. De oudste en meest bekende methode is het Apriori algoritme (a priori bekent: op basis van eerder onderzoek) ontwikkeld voor transacties (verkopen). Het is in de jaren negentig bedacht door Agrawal en anderen. Met het algoritme wordt je in staat gesteld om interessante voldoende voorkomende verbanden (implicaties) in een collectie te vinden (b.v. welke aankopen van anderen toon ik jou als jij net in de online winkel een slaapzak koopt?). Voldoende voorkomend (frequent) betekent in dit geval dat we niet alle verbanden even nuttig vinden. Als producten te weinig voorkomen, ofwel te weinig support hebben, dan nemen we die niet mee in het algoritme. We stellen dus een ondergrens aan het support (minimaal support).
Naast dit minimale support kun je ook instellen hoe betrouwbaar de implicaties moeten zijn (hoe sterk zijn de aanwijzingen), ofwel je geeft een minimale confidence op.

Het Apriori algoritme voor een collectie $C$ bestaat uit de volgende twee fasen:
  1. Het maken van een collectie $F$ met verzamelingen die voldoende frequent (groter dan een minimale support) zijn in $C$,
  2. Het opstellen van associatieregels met verzamelingen uit $F$ met voldoende betrouwbaarheid (goter dan een minimale confidence) in $C$.

Het maken van een collectie $F$ met verzamelingen die voldoende frequent (groter dan een minimale support) zijn in $C$

In deze fase gebruikt het Apriori algoritme een "bottom up" aanpak op de collectie $C$.
Van te voren kies je een minimale support (minimale aanwezigheid) en bouwen we een collectie $F$ met deelverzamelingen in $C$ met voldoende support. Dit doen we als volgt (zie ook de flowchart hiernaast):

Je begint een nog lege collectie $F$ en met de 1-itemset $S_{1}$. De collectie $S_{1}$ bestaat dan uit alle verzamelingen met slechts één item. (b.v. alle verschillende artikelen in de winkelmandjes). Vervolgens bereken je de support voor al verzamelingen in $S_{1}$ ten opzichte van $C$. Daarna haal je uit $S_{1}$ alle verzamelingen met voldoende support (groter of gelijk aan de minimale support) en voeg die toe aan $F$.

Met de elementen in de verzamelingen in $F$ stel je nu de 2-itemset $S_{2}$ op (dus verzamelingen met twee verschillende artikelen). De support van alle verzamelingen in $S_{2}$ wordt berekend en verzamelingen uit $S_{2}$ met voldoende support worden weer toegevoegd aan $F$.

Dit proces wordt net zolang herhaald tot er in een k-itemset geen verzamelingen met voldoende support meer zijn en er dus niets meer aan $F$ kan worden toegevoegd.

Het Apriori algoritme is dus gebaseerd op de volgende observatie: Iedere deelverzameling van een frequente itemset (voldoende voorkomende itemset) is zelf ook weer een frequente itemset. Als b.v. $\{Melk,Kaas\}$ in $F$ aanwezig is dan zijn de verzamelingen $\{Melk\}$ en $\{Kaas\}$ ook aanwezig.

voorbeeld:

Voor we verder gaan met fase twee in het Apriori algortime bekijken we eerst een voorbeeld voor fase 1.

Collectie $C$
Id Items
0 $\{Spaghetti, Tomatensaus\}$
1 $\{Spaghetti, Brood\}$
2 $\{Spaghetti, Tomatensaus, Brood \}$
3 $\{Brood,Boter\}$
4 $\{Brood, Tomatensaus\}$

Stel je hebt als winkel een groot aantal verkopen per klant, (Collectie $C$) Vraag: Genereer de grootste k-itemsets met behulp van het Apriori-algoritme. Zorg voor een minimale support van 40%.
Iteratie met k=1

  1. Genereer alle deelverzamelingen (itemsets) kandidaten met lengte $1$.
    $S_{1}=\{\{Spaghetti\}, \{Tomatensaus\},\{ Brood \}, \{Boter \}\}$
  2. Bereken support van de kandidaat deelverzamelingen (1-itemsets) uit $S_{1}$ in $W$.
    Itemset Support
    $\{Spaghetti\}$ 60%
    $\{Tomatensaus\}$ 60%
    $\{Brood \}$ 80%
    $\{Boter\}$ 20%
  3. De support van kandidaat itemset $\{Boter\}$ is onder de 40% en voldoet dus niet.
    De frequente 1-itemsets zijn dus: $F_{1}=\{\{Spaghetti\}, \{Tomatensaus\}, \{Brood\}\}$
  4. $F_{1}$ is niet leeg. We gaan op zoek naar grotere frequente itemsets namelijk die uit twee elementen bestaan. k=2

Iteratie met k=2

  1. Genereer alle deelverzamelingen (itemsets) kandidaten met lengte $2$ met elementen uit $F_{1}$.
    $S_{2}=\{\{Spaghetti,Tomatensaus\}, \{Spaghetti, Brood \}, \{Tomatensaus, Brood \}\}$
  2. Bereken support van de kandidaat deelverzamelingen (2-itemsets) uit $S_{2}$ in $W$.
    Itemset Support
    $\{Spaghetti, Tomatensaus \}$ 40%
    $\{Spaghetti, Brood \}$ 40%
    $\{Tomatensaus, Brood \}$ 40%
  3. Alle voldoen aan de 40% eis dus zijn de frequente 2-itemsets:$F_{2}=\{\{Spaghetti,Tomatensaus\}, \{Spaghetti, Brood \}, \{Tomatensaus, Brood \}\}$
  4. $F_{2}$ is niet leeg. We gaan op zoek naar grotere frequente itemsets namelijk die uit drie elementen bestaan. k=3

Iteratie met k=3

  1. Genereer alle deelverzamelingen (itemsets) kandidaten met lengte $2$ met elementen uit $F_{2}$.
    $S_{3}=\{\{Spaghetti,Tomatensaus, Brood \}\}$
  2. Bereken support van de kandidaat deelverzamelingen (3-itemsets) uit $S_{3}$ in $W$.
    Itemset Support
    $\{Spaghetti,Tomatensaus, Brood\}$ 20%
  3. De support van 3-itemset $\{Spaghetti,Tomatensaus, Brood\}$ voldoet niet dus is :$F_{3}=\{\}$
  4. $F_{3}$ is leeg. We zijn bij het einde gekomen.

Na het einde bestaat de uiteindelijke set van voldoende frequente verzamelingen uit
$F=\{\{Spaghetti\}, \{Tomatensaus\}, \{Brood\}, \{Spaghetti,Tomatensaus\}, \{Spaghetti, Brood \}, \{Tomatensaus, Brood \}\}$.

Het opstellen van associatieregels met verzamelingen uit $F$ met voldoende betrouwbaarheid (groter dan een minimale confidence) in $C$.

Als de collectie $F$ is gevonden kunnen we met de verzamelingen in $F$ associatieregels gaan maken. Voor associatieregel bepalen we de confidence. Alleen in die associatieregels met voldoende confidence zijn we geïnteresseerd. We gaan dit duidelijker maken met het voorbeeld hierboven.

Uit $F$ kunnen we de onderstaande associateregels afleiden. Stel dat we associatieregels alleen interessant als de betrouwbaarheid (confidentie) groter is dan 60% (= minimale confidentie).

Associatieregels Confidence
$\{Spaghetti\} \Rightarrow \{Spaghetti,Tomatensaus\}$ $\frac{40}{60}= 67 \% $
$\{Spaghetti\} \Rightarrow \{Spaghetti,Brood\}$ $\frac{40}{60}= 67\% $
$\{Brood\} \Rightarrow \{Spaghetti,Brood\}$ $\frac{40}{80}= 50\% $
$\{Brood\} \Rightarrow \{Tomatensaus,Brood\}$ $\frac{40}{80}= 50\% $
$\{Tomatensaus\} \Rightarrow \{Tomatensaus,Brood\}$ $\frac{40}{60}= 67\% $
$\{Tomatensaus\} \Rightarrow \{Tomatensaus,Spaghetti\}$ $\frac{40}{60}= 67\% $

In de eerste regel in de tabel hierboven geeft voor associatieregel $\{Spaghetti\} \Rightarrow \{Spaghetti,Tomatensaus\}$ een betrouwbaarheid van 67%. Dit zegt dat in 67% van de gevallen dat een klant spaghetti koopt, deze ook tomatensaus gaat kopen. 67% is groter dan 60%, voldoende betrouwbaar dus. De derde regel laat zien dat als iemand brood koopt, deze persoon in 50% van de gevallen spaghetti koopt, te weinig voorspellend om rekening mee te houden want kleiner dan 60%.

Tijd om dit zelf toe te passen: