Data mining - Associatieregels

Bij het vak Kunstmatige intelligentie wordt tijdens het laatste college aandacht besteed aan data mining, en meer in het bijzonder aan associatieregels. Op deze bladzijde wordt hier kort wat over verteld. Meer over associatieregels is te vinden in talloze publicaties, zoek maar eens op WWW.

Inleiding | Definities | Algoritme | Interessantheid

Inleiding

Meer informatie over data mining in het algemeen is bijvoorbeeld te vinden in het boek Data mining van Pieter Adriaans en Dolf Zantinge, Addison-Wesley, 1996. De inhoud van deze inleiding is uit dat boek afkomstig.

Een bekend begrip, meer algemeen dan data mining, is KDD, wat staat voor Knowledge Discovery in Databases. Dit is het hele proces van kennis-extractie uit data, waarbij data mining dan weer de "ontdekkingsstap" is. Een definitie van KDD is wel: "the non-trivial extraction of implicit, previously unknown and potentially useful knowledge from data". Het KDD-proces bestaat uit:

data selection
cleaning (onder andere de-duplicatie, domain-consistency)
enrichment (denk aan "datafusie")
coding
data mining
reporting

De volgende lijst van data mining technieken is ook uit bovengenoemd boek afkomstig:

query tools (SQL, ...)
statistische technieken
visualisatie
OLAP = online analytical processing
k-nearest neighbor
Classificeer een object als het gemiddelde (of iets dergelijks) van zijn k "dichtstbijzijnde" buren; je hebt dus een afstandsbegrip nodig, bijvoorbeeld de gewone Euclidische afstand in een n-dimensionale ruimte.
decision trees
associatieregels
neurale netwerken
genetische algorimen

Veel van deze technieken hebben als taak clusteren en/of classificeren.

Definities

Gegeven is een database met transacties. Elke transactie representeert een klant met al zijn aankopen. Een voorbeeld:

   1:   13, 37, 53.
   2:   13, 88, 144, 170, 212.
   3:   4, 66, 88, 212, 933, 1024.
   4:   2, 13, 88.

Per regel staan de "product-aankopen" van een klant opgesomd, oplopend gesorteerd, zonder dubbelen. Klant 1 koopt dus de artikelen 13, 37 en 53. Het kan best zijn dat klant 1 en klant 3 dezelfde persoon zijn, maar dat kun je in de database niet zien. Ieder "boodschappenmandje" representeert weer een nieuwe klant.
Een itemset is een verzameling producten oftewel items; als het er k zijn, heet het een k-itemset. De support van een itemset is het aantal klanten (eventueel in de vorm van een percentage van het totaal aantal klanten) dat deze itemset, en wellicht zelfs meer, aanschaft. In het voorbeeld heeft de 2-itemset {88,212} support 2, oftewel 50%. Hij wordt namelijk door de klanten 2 en 3, en geen andere, gekocht.
Een itemset heet frequent als zijn support minstens gelijk is aan een zekere drempelwaarde, de support threshold. In ons voorbeeld zijn -bij support threshold 2- {88,212} en {13,88} de enige frequente 2-itemsets; {13} is, met support 3, in dat geval overigens een frequente 1-itemset.

De technieken zijn trouwens ook toepasbaar op veel algemenere situaties. Zo kunnen er ook anderssoortige gegevens in het spel zijn, bijvoorbeeld leeftijd van de "klant". Die leeftijd kan weer een "fuzzy" waarde hebben, zoals jong of oud. Ook kan het tijdsaspect een belangrijke rol spelen. Denk maar eens aan de logfile van een webserver, waar de achtereenvolgende kliks van een gebruiker gevolgd worden. Voor het gemak beperken wij ons hier maar tot de eerstgenoemde situatie.

Algoritme

Apriori is een efficiënt algoritme om associatieregels (of eigenlijk frequente itemsets) te vinden. Het is in de jaren negentig bedacht door Agrawal en anderen. Het is gebaseerd op de volgende observatie: iedere deelverzameling van een frequente itemset is zelf ook weer een frequente itemset. Immers de support van een deelverzameling is minstens die van de originele verzameling: als je A, B en C koopt, dan koop je in het bijzonder ook B en C. Maar misschien zijn er zelfs wel meer mensen die B en C kopen, maar niet ook nog A erbij.
Het gevolg is dat uit de frequente k-itemsets alle (kandidaat) (k+1)-itemsets gegenereerd kunnen worden. Stel namelijk dat je alle frequente k-itemsets lexicografisch geordend hebt. Dat wil zeggen: per verzameling staan de elementen oplopend gesorteerd, en daarna beslist het eerste getal dat verschilt over de volgorde van de verzamelingen. Een voorbeeld met k = 3:

   {3,4,5}, {3,4,7}, {3,5,6}, {3,5,7}, {3,5,8}, {4,5,6}, {4,5,7}.

Maak nu voor ieder duo {a_1,a_2,...a_(k-1),X}-{a_1,a_2,...a_(k-1),Y} met hetzelfde beginstuk een kandidaat {a_1,a_2,...a_(k-1),X,Y}. Zo worden kandidaten hooguit één keer gemaakt! In ons voorbeeld levert dit op:

   {3,4,5,7}, {3,5,6,7}, {3,5,6,8}, {3,5,7,8}, {4,5,6,7}.

Verwijder (= prune) nu alle kandidaten met niet-frequente deelverzamelingen. Zo kan {3,5,6,8} zelf nooit frequent zijn, want de deelverzameling {5,6,8} is dat niet: die staat namelijk niet in de lijst. In ons voorbeeld blijft alleen {3,4,5,7} over!
Bepaal tot slot de echte support van de resterende itemsets, en kijk of ze de drempelwaarde halen. Aangezien dit een dure arbeidsintensieve operatie is (je moet namelijk de hele database doorlopen), wil je zo weinig mogelijk kandidaten hebben, vandaar het prunen.

Interessantheid

Er is veel nagedacht over de "interessantheid" van itemsets. De meest gebruikte maat is confidence, oftewel betrouwbaarheid.
Uit een k-itemset kun je 2^k-2 regels maken door de verzameling in twee niet-lege disjuncte stukken X en Y te splitsen, en dan te kijken naar de associatieregel X => Y: als iemand X koopt, dan koopt hij/zij ook Y. De confidence van X => Y is per definitie de support van de vereniging van X en Y gedeeld door de support van X. Dit geeft een maat voor de kans dat iemand Y koopt, gegeven dat hij/zij X ook in zijn/haar boodschappenmandje heeft.
Doorgaans zoek je naar regels die afkomstig zijn van itemsets met hoge support ("het komt vaak samen voor"), en die zelf een hoge confidence hebben ("sterke samenhang"). De regels verklaren overigens niets, ze constateren alleen maar.

Een voorbeeld. Gegeven de volgende database:

   1:   3, 5, 8.
   2:   2, 6, 8.
   3:   1, 4, 7, 10.
   4:   3, 8, 10.
   5:   2, 5, 8.
   6:   1, 5, 6.
   7:   4, 5, 6, 8.
   8:   2, 3, 4.
   9:   1, 5, 7, 8.
   10:   3, 8, 9, 10.

We berekenen support (supp) en confidence (conf) van een aantal verzamelingen en regels: supp({5}) = 5, supp({8}) = 7, supp({5,8}) = 4, en dus conf({5} => {8}) = 4/5 = 0.8, oftewel 80%, terwijl conf({8} => {5}) = 4/7 = 0.57, oftewel 57%; die eerste regel is blijkbaar interessanter. Verder is bijvoorbeeld conf({9} => {3}) = 1/1 = 1.0, oftewel 100%; een zeer hoge confidence, maar omdat supp({3,9}) slechts 1 is, boeit dit nauwelijks.

Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.

23 april 2003 - http://www.liacs.nl/home/kosters/AI/datam.html