In de introductie van de AI technieken heb je gezien dat AI applicaties data gestuurd zijn. Hoe werkt dat sturen door die data? In deze sectie en volgende secties gaan we dat in een aantal technieken bekijken. De meeste toepassingen gebruiken artificiële intelligentie om b.v. patronen te herkennen of groeperingen te maken.

De berekeningen in dit en de sectie Cluster Analyse 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.

Na het bestuderen van deze sectie:

• Kun je in eigen woorden het doel en de taak van associatie analyse bij datamining toelichten.
• Kun je de begrippen verzamelingenleer, associatieanalyse en associatieregel uitleggen.
• Weet je de toepassingen van associatie analyse, bijvoorbeeld winkelmandjesanalyse (basket analysis).
• Ben je in staat praktische voorbeelden van associaties op te noemen.
• Kun je de berekeningen binnen het apriori algoritme uitvoeren, onder andere:
  • het bepalen van de doorsnede en de vereniging van twee of meer verzamelingen;
  • het berekenen van de support van een deelverzameling;
  • het vinden van de associatieregels in een eenvoudig probleem;
  • het berekenen van de betrouwbaarheid (confidence) van een associatieregel van een deelverzameling;
  • het uitvoeren van alle nodige iteraties in het apriori algoritme.

Introductie

Stel je wordt manager van een supermarkt in een wijk waar veel studenten wonen. Na een paar dagen krijg je onder andere de indruk dat er veel bananen en chocolade verkocht worden. Daarom overweeg je de bananen en de chocolade samen vlak bij de kassa's te leggen om zo de klanten die langs lopen tot meer impuls inkopen te verleiden. Je wilt als verkoper ook niet impulsief te werk gaan, dus ga je een onderzoek doen met alle kassaregistraties van de klanten als gegevens voor je onderzoek. Eén kassaregistratie geeft dan natuurlijk aan wat de klant in het winkelmandje had.

De methoden die je als onderzoeker tot je beschikking hebt om deze gegevens te onderzoeken vallen onder associatie analyse. Voor we algemeen aan de slag gaan en één van de methoden, het apriori algoritime, in detail uitwerken gaan we eerst intuïtief met bovenstaand voorbeeld aan de slag. Na een week heb je deze gegevens verzameld:

• er blijken 8051 klanten te zijn geweest;
• 905 keer stond banaan op de rekening;
• 750 keer stond chocolade op de rekening;
• samen kwamen bananen en chocolade 653 keer voor.

Begrippen die centraal staan in de associatie analyse zijn support, associatieregel en betrouwbaarheid.

Support van één of meerder artikelen is niets anders dan de experimentele kans dat een mandje deze artikelen bevat. Zo is $\mathrm{support}(\{\mathrm{banaan}\}) = 905/8051 \approx 0.112$ of wel ongeveer 11%. Verder is $\mathrm{support}(\{\mathrm{chocolade}\}) = 750/8051 \approx 0.093$ en $\mathrm{support}(\{\mathrm{chocolade}, \mathrm{banaan}\}) = 653/8051 \approx 0.081$.

Om nu te weten te komen of het vermoeden dat bananen vaker samen met chocolade wordt verkocht werkelijkheid is, ben je geïnteresseerd in de vraag: als een klant bananen koopt, hoe groot is dan de kans dat deze klant ook chocolade koopt? Ofwel hoe waar is de uitspraak: Als een klant bananen koopt, koopt de klant ook chocolade? Een dergelijke uitspraak noemt men een associatieregel. Met de gegevens hierboven kunnen we de betrouwbaarheid (=confidence) van deze uitspraak uitrekenen in de vorm van een kans.

Confidence( Als een klant bananen koopt, koopt de klant ook chocolade ) = aantal winkelmandjes met bananen en chocolade / aantal winkelmandjes met alleen bananen= 653/905=0,72.

In ongeveer driekwart van de gevallen zal de klant die bananen in zijn mandje legt doorlopen naar de chocolade. Zullen we het die klant maar eens gemakkelijker maken door deze producten dichter bij elkaar te plaatsen?

In het voorbeeld hierboven hebben we specifiek gekeken naar bananen en chocolade. Het is zinvoller als we uitgaan van alle aankopen en met een methode uitvissen wat de interessante combinaties zijn. De apriori methode, die we hier straks uitwerken, is zo'n methode. Eerst even een meer algemene introductie over associatie analyse.

Bij associatie analyse is het de bedoeling dat een gegeven set kenmerken die een gebruiker in een toepassing aanlevert, bijvoorbeeld jouw leeftijd, geslacht, ingetypte zoekopdracht, beluisterde muziek, artikelen in je winkelmand, wordt vergeleken met dezelfde kenmerken van andere gebruikers. Gezocht wordt dan naar overeenkomsten tussen de gebruikers. Het resultaat van de associatie is dan bijvoorbeeld de uitvoer van de toepassing, bijvoorbeeld de reclame die in de zoekmachine verschijnt, muziek die jij ook wel leuk zou vinden, artikelen die jij ook zou willen kopen. Om zinvolle suggestie te doen moet een grote hoeveelheid gegevens worden geanalyseerd.

De AI techniek associatie analyse die voor deze situaties wordt gebruikt heeft als belangrijkste AI-kenmerk: de invoer die het programma krijgt, is niet volledig te bepalen en is complex . Het leerproces dat in associatieanalyse wordt gebruikt is unsupervised learning. Voor we de theorie van associatie analyse behandelen en leren toepassen geven we een aantal voorbeelden van gebieden waarin associatie analyse wordt gebruikt:

Gezondheidszorg

Artsen kunnen associatieregels gebruiken om een diagnose van patiënten te stellen. Omdat veel ziekten overeenkomstige symptomen hebben, zijn er veel variabelen waarmee rekening moet worden gehouden bij het stellen van een diagnose. Met behulp van associatie analyse, die getraind is met alle symptomen en de daarbij behorende ziekten, kan aan een arts, bij de symptomen die een patiënt heeft, die ziekten tonen die het meest waarschijnlijk zijn. Als er nieuwe symptomen bij een ziekte optreden of als er nieuwe ziekten bijkomen, kan het machine learning-model opnieuw getraind worden met de oude en bijgewerkte gegevens.

Detailhandel

Ontwikkelaars kunnen gegevens verzamelen over hoe consumenten een door hen gemaakte website/app gebruiken. Ze kunnen vervolgens associaties in de gegevens gebruiken om de gebruikersinterface van de website te optimaliseren - door bijvoorbeeld te analyseren waar gebruikers op klikken en hoe ze de kans dat een bezoeker een gewenste handeling verricht kan vergroten.

User experience (UX) design

Ontwikkelaars kunnen gegevens verzamelen over hoe consumenten een door hen gemaakte website/app gebruiken. Ze kunnen vervolgens associaties in de gegevens gebruiken om de gebruikersinterface van de website te optimaliseren - door bijvoorbeeld te analyseren waar gebruikers op klikken en hoe ze de kans dat een bezoeker een gewenste handeling verricht kan vergroten.

Sociale media en entertainment

Services zoals Facebook, Youtube, Netflix, Twitter, Spotify kunnen associatieregels gebruiken om hun engine voor contentaanbeveling van brandstof te voorzien. Machine learning-modellen analyseren gegevens over gebruikersgedrag uit het verleden op frequente patronen, ontwikkelen associatieregels en gebruiken die regels om gebruikers aanbevelingen te doen die hun ook zal interesseren, b.v. die leuke foto van een ooievaar, omdat je als vogelaar heel vaak foto's van vogels bekijkt.

Theorie

In de opwarmer aan het begin van dit hoofdstuk hebben we geprobeerd om op een intuïtieve manier het doel van associatie analyse, een AI algoritme, duidelijk te maken. We meldden daar ook al dat we op basis van alle kassaregistraties zinvolle verbanden willen vinden. Zoals typisch is voor AI bepalen de gegevens, door deze te in te voeren in een iteratief proces, de uitkomst van de analyse.

De wiskundige techniek die wordt gebruikt in associatie analyse is gebaseerd op wiskunde op verzamelingen, de zogenaamde verzamelingenleer. Het is dus nuttig eerst wat begrippen in de verzamelingen leer te introduceren. Een aantal van deze begrippen ben je waarschijnlijk al eens in de wiskundeles tegengekomen. Daarna gebruiken we deze begrippen in de apriori methode, een veel gebruikte methode in de associatie analyse.

Verzamelingenleer

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, in het Engels. 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. $v_{1}$ is dan het eerste element in de verzameling, $v_{2}$ het tweede, $v_{1}$ is dan het derde, enz.

Een verzameling bestaat dus uit elementen, en als $v$ een element is van een verzameling $\small V$ noteren we dit wiskundig als $\small v \in V$. We gebruiken accolades om verzamelingen te noteren.

Voorbeeld: De verzameling winkelmandje met de elementen melk, brood, en kaas noteren we als: $$ \small \text{winkelmandje} = \{\text{melk}, \text{brood}, \text{kaas}\} $$

Als we schrijven $\small \textbf{melk} \in \textbf{winkelmandje}$, dan zeggen we dus dat melk in het winkelmandje aanwezig is.

Een element van een verzameling kan zelf ook een verzameling zijn. Zo bestaat de verzameling  $$ \small \begin{array}{rcl}C &=& \{\{\text{chips}, \text{zeep}, \text{appels}\}\\&&, \{\text{chips}, \text{zeep}, \text{appels}\}\\&&, \{\text{zeep}, \text{bananen}\}\\&&, \{\text{chips}, \text{zeep}, \text{bananen}\}\\&&\}\end{array} $$ uit vier elementen, ieder element is een verzameling.

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

Nog een voorbeeld van een collectie is de registratie van aankopen door acht klanten in een klein avondwinkeltje: $$ \small \begin{array}{lcl}D&=&\{\{\text{banaan}\}\\ & & ,\{\text{chips}\}\\ & & ,\{\text{melk}\}\\ & & ,\{\text{pruim}\}\\ & & ,\{\text{banaan}, \text{rum}\}\\ & & ,\{\text{chips}, \text{rum}\}\\ & & ,\{\text{banaan}, \text{chips}, \text{melk}\}\\ & & ,\{\text{banaan}, \text{rum}, \text{melk}, \text{pruim}\}\\ & & \}\end{array} $$ De collectie D bestaat nu uit de inhoud van de acht winkelmandjes, van iedere klant één. Ieder mandje is een verzameling van producten: $$ \small\begin{array}{rcl}D_1&=& \{\text{banaan}\} \\D_2&=& \{\text{chips}\} \\D_3&=& \{\text{melk}\} \\D_4&=& \{\text{pruim}\} \\D_5&=& \{\text{banaan},\text{rum}\} \\D_6&=& \{\text{chips},\text{rum}\} \\D_7&=& \{\text{banaan},\text{chips},\text{melk}\} \\D_8&=& \{\text{banaan},\text{rum},\text{melk},\text{pruim}\}\end{array} $$

Associatieregels

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

• Associatieregel

  De associatieregel $X \Rightarrow Y $ betekent: als de deelverzameling $X$ voorkomt dan komt ook de deelverzameling $Y$ voor.

  Bijvoorbeeld $\small \{\text{melk}\} ⇒ \{\text{melk},\text{brood}\}$ betekent dat als melk in een winkelmand zit, dan zit er ook brood in. In een winkelmandjes analyse is dit natuurlijk niet altijd waar, maar in associatie analyse is het van belang om te kijken hoe groot de kans op deze associatieregel is, ofwel hoe betrouwbaar is deze regel. Om de betrouwbaarheid te bepalen hebben we nog wat gereedschap nodig.

• Support

  De support van een deelverzameling $\small X$ is het aantal deelverzamelingen van een collectie $\small C$ waar de elementen van $\small X$ in voorkomen gedeeld door het aantal elementen van deze collectie.

  $$ \small \mathrm{support}(X)=\frac{\mathrm{freq}(X)}{\#C} $$

  Hierin is $\mathbf{ \mathrm{freq}(X)}$ het aantal (frequentie) van de (deel)verzamelingen waarin de elementen van $\small X$ voorkomen. Support is dus vaktaal voor de experimentele kans (of relatieve frequentie) dat een mandje de (deel)verzameling $X$ bevat.

Nog een voorbeeld van een praktische toepassing. Bij marktonderzoek is de support van een stel artikelen (bijvoorbeeld $\small K=\{\text{televisie},\text{surroundset}\}$) het aantal klanten dat al die artikelen samen koopt, op het totaal aantal klanten, meestal weergegeven als percentage.

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

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 ofwel de betrouwbaarheid van de associatieregel.

Bij de winkelmandjesanalyse is de betrouwbaarheid een maat voor de kans dat iemand $Y$ gaat kopen, als gegeven is dat hij $X$ al in zijn winkelmandje heeft. We gaan dit alles weer bekijken vanuit de collectie winkelmandjes $D$ voor de associatieregel $ \{\text{banaan}\}⇒\{\text{rum}\}$.

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, de minimale support.
Naast deze minimale support kun je ook instellen hoe betrouwbaar de implicaties moeten zijn (hoe sterk zijn de aanwijzingen), ofwel je geeft een minimale confidence op.

We gaan door deze twee fasen heen aan de hand van het volgende voorbeeld:

Fase 1: 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 iteratief proces met een "bottom up" aanpak op de collectie $C$. Van te voren kies je een minimale support (minimale aanwezigheid) en bouwen we een steeds groter wordende collectie $F$ met deelverzamelingen in C met voldoende support, totdat er geenvoldoende frequente verzamelingen zijn toe te voegen aan $F$. Het algoritme is in de figuur hiernaast weergegeven. We zullen je aan de hand van het voorbeeld door dit algoritme heen leiden.

Na de start van het algoritme maken we eerst de lege collectie $F = \{\}$ en zetten het aantal elementen $k$ aanwezig in een itemset op 0. Gelijk daarna maken we $k$ gelijk aan 1 en gaan we naar het oranje blok:

Vervolgens gaan we naar de stap in het blauwe blok:

Als laatste gaan we in de eerste iteratie naar het paarse blok:

We komen nu aan bij de test "Is er in deze ronde een $k$-itemset aan $F$ toegevoegd?". In het voorbeeld hebben we net drie verzamelingen met 1-item toegevoegd en is het antwoord dus ja, we zijn dus nog niet klaar. We verhogen k naar 2 en gaan weer verder bij het oranje blok:

Op naar het blauwe blok om de support te berekenen:

Kunnen we weer itemsets toevoegen aan $F$?

We komen nu weer aan bij de test "Is er in deze ronde een $k$-itemset aan $F$ toegevoegd?". In het voorbeeld hebben we er weer 3 toegevoegd en is het antwoord dus ja, we zijn dus nog steeds niet klaar. We verhogen $k$ naar 3 en gaan weer verder bij het oranje blok:

Het blauwe blok levert nu de support:

Kunnen we weer itemsets toevoegen aan F?

We komen nu weer aan bij de test "Is er in deze ronde een $k$-itemset aan $F$ toegevoegd?". In het voorbeeld hebben we niets meer hebben toegevoegd dus nee, we zijn klaar en eindigen dus met de verzameling

In het voorbeeld zijn in het algoritme dus 3 iteraties nodig geweest om het proces te stoppen. Andere samenstellingen van de winkelmandjes met vooral meer artikelen zal ervoor zorgen dat er veel meer iteraties nodig zijn.

We zijn nu aan het eind van fase 1 gekomen en gaan nu kijken welke associatieregels interessant zijn.

Fase 2: 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 elke associatieregel bepalen we de confidence. Alleen in die associatieregels met voldoende confidence zijn we geïnteresseerd. We gaan dit duidelijker maken met het voorbeeld.

Tijd om dit zelf toe te passen: