Data mining Data mining Van boodschappenmandjes tot bio-informatica
Walter Kosters Informatica, Universiteit Leiden
donderdag 6 april 2006
http://www.liacs.nl/home/kosters/ 1
Data mining
Wat is Data mining?
Data mining probeert interessante en (on)verwachte patronen te vinden in grote hoeveelheden (on)geordende data. Bijvoorbeeld: • Boodschappenmandjes: wat en hoe kopen we? • Bio-informatica: DNA? Problemen (selectie): • resultaten: zowel verwacht als onverwacht • bewegende doelen: steeds andere eisen • data vergaren: wat/hoeveel kan/mag/is er? • afstandsbegrip: wie lijkt op wat? 2
Data mining
KDD
Het Data mining proces — of beter het KDD proces, voor Knowledge Discovery in Databases — wordt vaak als volgt opgedeeld: 1. data selectie 2. opschonen: de-duplicatie en domein-consistentie 3. verrijking: data-fusie 4. coderen 5. Data mining — het echte gebeuren 6. rapporteren 3
Data mining
Technieken
Er zijn veel Data mining technieken, of beter gezegd: algoritmen, die we kunnen gebruiken om data te “minen”: • (niet vergeten:) statistische methoden • allerlei “machine learning” technieken uit de AI: evolutionaire algoritmen, neurale netwerken, Bayesiaanse netwerken, . . . • allerlei technieken voor clustering en classificatie: beslissingsbomen, . . . • associatieregels • ad-hoc methoden 4
Data mining
Beslissingsbomen
Als voorbeeld iets over beslissingsbomen (= decision trees). Meestal wordt Quinlan’s algoritme J48 gebruikt om uit een aantal voorbeelden zo’n boom te maken. Het berust op Shannon’s informatietheorie. Interne knopen vragen naar een attribuutwaarde, bladeren geven de classificatie. Patrons?
None F
Some
Full
T
WaitEstimate?
>60
30−60
F
10−30
Alternate?
No
Yes
Bar?
No F
T
Yes T
Hungry?
Yes
No
Fri/Sat?
T
Reservation?
No
0−10
No F
Yes T
T
Yes Alternate?
No
Yes
T
Raining?
No F
Yes T
5
Data mining
Beslissingsbomen — algoritme
Het recursieve algoritme werkt als volgt. Stel we zitten in een knoop, en hebben de verzameling V van alle voorbeelden die in die knoop terecht komen. Dan: 1. Geen voorbeelden meer (V = ∅)? Geef defaultwaarde, bijvoorbeeld “majority-value” van ouderknoop. 2. Alle voorbeelden dezelfde classificatie? Geef die. 3. Geen attributen meer? “Majority-value” van V . 4. Bepaal “beste” attribuut (entropie), splits daarop, en ga recursief verder met de kinderen: ν X pi + n i
pi ni pi ni ·{− log2 − log2 } p + n p + n p + n p + n p + n i i i i i i i i i=1 6
Data mining
Thema’s
Ter inspiratie bekijken we nu drie thema’s:
• associatieregels
• boodschappenmandjes
• bio-informatica
7
Data mining
Associatieregels
⇒
8
Data mining
Klanten en producten
We zijn geinteresseerd in verbanden tussen verzamelingen “items”: producten, of moleculen, of woorden, of bezoeken aan websites. Regels zijn: “als je boter koopt, koop je meestal ook brood”. Stel we hebben een database met records = transacties = klanten, waarbij ieder record uit een aantal items = producten bestaat. De support van een stel artikelen is het aantal klanten dat al die artikelen koopt, meestal als percentage van het totaal. Een stel artikelen met hoge support (boven een zekere drempel) heet frequent. Bijvoorbeeld: 20% van de klanten in een supermarkt kopen brood, boter en kaas — en wellicht meer producten. 9
Data mining
Betrouwbaarheid
Stel dat van de α klanten die A kopen, er β ook B kopen. We zeggen dan dat de associatieregel A ⇒ B een betrouwbaarheid heeft van β/α. Bijvoorbeeld: het zou kunnen zijn dat 80% van de klanten die boter en kaas kopen, ook brood aanschaffen. We zijn benieuwd naar regels A ⇒ B met zowel hoge betrouwbaarheid als hoge support, dat wil zeggen hoge support voor A en B samen (20% in ons voorbeeld).
10
Data mining
Aspecten
Er is veel nagedacht over associatieregels:
ente algoritmen om ze te vinden • geef effici¨
• hoe vind je vervolgens de interessante?
• en hoe ga je om met niet 0/1-en?
Voor dat laatste gebruikt men fuzzy logica, met in plaats van alleen 0/1 (niet-kopen vs. kopen) ook tussenliggende waarden. Voorbeeld: iemands leeftijd kan 0,3 “jong” zijn. 11
Data mining product = item klant = transactie 1 2 3 4 5 6
Voorbeeld 1
2
3
4
5
6
7
8
9
1 1 0 1 0 0
1 0 1 0 0 1
0 1 1 1 0 0
0 0 0 0 0 0
1 0 1 1 1 1
1 0 0 1 0 0
1 0 1 0 0 1
1 1 0 1 0 0
0 1 0 1 0 0
Zelfs voor deze kleine database is het moeilijk om te zien dat {2, 5, 7} het enige drietal is dat “gekocht” wordt door minstens 50% (een vaste drempelwaarde) van de klanten. Frequente itemsets leveren associatieregels: {2, 7} ⇒ {5}. 12
Data mining
Apriori
De meeste snelle implementaties zijn gebaseerd op: een deel van een iets frequents is zelf ook frequent! Dit heet de Apriori-eigenschap, omdat het wordt gebruikt in Apriori, een van de meest bekende Data mining algoritmen. Kleine frequente verzamelingen worden samengevoegd tot grotere. De databases worden opgeslagen in FP-bomen.
13
Data mining
Boodschappenmandjes
14
Data mining
Boodschappenmandjes
Winkels analyseren klantgedrag: boodschappenmandjes. Toepassingen zijn bijvoorbeeld: • direct marketing “Welke klant doen we een speciale aanbieding?” • Wat verkopen we? “Welke producten zetten we in een een station?”
kleine
winkel, zeg op
• clustering en classificatie “Kunnen we klanten groeperen of herkennen aan hun koopgedrag?” (Ja!) Een wat algemener doel is het begrijpen van klanten. 15
Data mining
Winkels clusteren
Een grote winkelketen wilde inzicht in hun “positionering”, Hema: filialen — weektotalen gebaseerd op weekverkopen. Dit resulteert in plaatjes als: Walter A. Kosters, Universiteit Leiden — Informatica 18 maart 2002
36 1186 336 136 586 1126 11061116 226 746 1026 1096 196 96 806 1216 66 76
576 186
636
1136
826 6661036 1056 26 216 476 616 596 1206 156 706 306 656 116 56 326 236 376 556 686 1166 546 146 356 106 16 266 396
46
566 646 796 86 206 126766 406 526
1176 716 1016 776 736 246 1086 176 1066 626 1146
1196 696 1156 1076 286 456 466676 166 516 276486 316 346 756 256 1046446 536 606 366786 496416 386 726 426 506
Fout: 652.583 Aantal produkten afgebeeld: 100 uit 100. Randomseed: 7. Ondergrens: 10. Aantal cykels: 1000. Aantrekking: 15.
Hier zien we 100 winkels.
1
16
Data mining
Methode
Om te clusteren heb je een afstandsbegrip nodig. Stel dat twee winkels de afgelopen week dit verkocht hebben: wijn 7 10
brood 120 100
kaas 34 21
tomaat 0 0
banaan 40 0
Hun afstand kan dan zijn: 3 + 20 + 13 + 0 + 40 = 76, of 3 + 20 + 13 = 36, of 3/10 + 20/120 + 13/34, of . . . Het lijkt redelijk te normaliseren voor de totale verkoop bij een winkel. Hoe dan ook, er zijn veel mogelijkheden!
17
Data mining
Clustering technieken
Clustering technieken kunnen • hierarchisch zijn: voeg kleinere clusters samen tot grotere • niet-hierarchisch zijn: verbeter bestaande clustering
Wij gebruiken AI-technieken als Self Organizing Maps (Kohonen’s SOMs), gebaseerd op neurale netwerken. Er zijn random aspecten — kansen spelen een rol.
18
Data mining
Meer resultaten
Links zien we duidelijk verschil tussen winkels met en zonder restaurant. Recht gebruiken we postcode, en zien we “eetgewoontes” terug.
19
Data mining
Supermarkt
In een supermarkt zijn er veel klanten die een grote keuze hebben. Associatieregels kunnen eenvoudig worden toegepast. “Onderzoek” onthulde dat vloei en tabak vaak samen worden verkocht (wat een verrassing!), maar ook dat speciale shag speciale vloei vereist. en: merken ↔ algemene Er is veel interesse in hierarchie¨ categorie¨ en. Het luiers—bier verhaal is een sprookje.
20
Data mining
Groeperen
Een laatste toepassing in een supermarkt is het volgende. We willen dranken zodanig groeperen dat producten dicht bij elkaar komen als ze elkaar kunnen “vervangen”. Deze informatie haal je uit de boodschappenmandjes: zulke producten worden zelden samen verkocht. Technieken als boven leiden tot plaatjes als: appelsap
water
cola 1 cola 2
21
Data mining
Bio-informatica
22
Data mining
Bio-informatica
Veel vragen uit de Bio-informatica kunnen als Data mining problemen worden beschouwd. Een enkel voorbeeld. DNA kan gezien worden als een rijtje letters uit het alfabet {A, C, G, T }: AGGT CAAT . . . T T . Menselijk DNA bevat ongeveer 3.000.000.000 letters — het menselijk genoom, verdeeld over zo’n 20+ chromosomen. Stel dat we voor zo’n 2.000+ speciale stukjes DNA (clones geheten), netjes verspreid over het menselijk genoom, weten hoeveel er aanwezig is in 150 pati¨ enten. Hier is “hoeveel” een getal tussen −5 (“verlies”) en +5 (“versterking”). Hoe “mine” je deze berg aan data? 23
Data mining
Plots
Links: versterkingen (985 frequente “duos”’); rechts: verliezen (629 frequente “duos”’). Verticale lijnen zijn de chromosoomgrenzen. Drempelwaarde: 100. 700 1
1000
2 3
4
5
6
7
8
9
10
11
1
12 13 14 15 16 17 1819 2021 2223
2
3
4
5
6
7
8
9
10
11
12 13 14 15 16 17 1819 20 21 2223
600
500
frequent sets
frequent sets
800
600
400
300
400 200 200 100
0
0 0
500
1000 clones
1500
2000
0
500
1000 clones
1500
2000
24
Data mining
Uitleg
In zo’n plot zien we talrijke groepen pati¨ enten, waarbij elke groep zich ongeveer hetzelfde gedraagt op de 2000+ clones. Een tweetal pati¨ enten is frequent als beiden op minstens 100 dezelfde clones een versterking, respectievelijk een verlies hebben.
25
Data mining
Meer plots
Links: de 55 “maximale” 10-itemsets (met steeds 10 pati¨ enten), gecombineerde versterkingen en verliezen, met drempelwaarde 100; rechts: de pati¨ enten uit die verzamelingen.
1
2
3
4
5
6
7
8
9
10
11
60
12 13 14 15 16 17 1819 20 21 2223
50
50
40
40 sample sets
sample sets
60
30
30
20
20
10
10
0
0 0
500
1000 clones
1500
2000
0
20
40
60 samples
80
100
De verzamelingen hebben veel gemeen: goed of slecht? 26
120
Data mining
Clustering
Deze 55 verzamelingen kun je inbedden in het eenheidsvierkant: 45 54 33 28 16 4632 35 15 29 14 31 17 47 273034 19 23 36 48 51 22 44 40 18 25 24 52 21 38 37 3926 20 13 9 11 53 43 42 10 12 55 49 50 5 41 31 84 76 2 De Euclidische afstand lijkt op de afstand die je krijgt door versterkingen en verliezen “kwadratisch op te tellen”.
27
Data mining
En verder?
• beoordeel grenzen versterking/verlies (0.225? fuzzy?) • maten voor interessantheid • visualisaties (SOMs, . . . ) • verwerk “aaneengesloten zijn” in support • voeg gegevens als leeftijd toe • en tijdsafhankelijkheid • tool 28
Data mining
Slotopmerkingen
We zien succesvolle inzet van Data mining. Aandachtspunten zijn onder meer:
• privacy
• presentatie van resultaten
• toepasbaarheid van mooie algoritmen
• grootschaligheid 29
