Data Mining: Inleiding docent: dr. Toon Calders
Gebaseerd op slides van Tan, Steinbach, and Kumar. Introduction to Data Mining
2II15: Data mining en kennissystemen Lessen: maandag 7de en 8ste uur in Auditorium 16 Docent: Toon Calders (
[email protected] HG 7.82a ) Studeerwijzer: http://www.win.tue.nl/~tcalders/teaching/datamining/ Boek: Tan, Steinbach, Kumar: Introduction to datamining
2II15: Data mining en kennissystemen Evaluatie: 20% Uitdieping: kort verslag en presentatie 40% Groepsopdracht 40% Tentamen
2II15: Data mining en kennissystemen Uitdieping: Lezen en begrijpen van een onderzoeksartikel Kort rapport (ongeveer 2 A4’tjes) Korte presentatie
2II15: Data mining en kennissystemen Groepsopdracht: Groepjes van 3 a 4 personen Zelfstandig analyseren van een dataset Gebruik makend van bestaande algoritmes In praktijk brengen van de theorie Uitgebreide beschrijving binnenkort in studiewijzer
Overzicht: Inleiding tot data mining Waarom data mining? Wat is data mining? Het volledige knowledge discovery proces. De data mining taken. Samenvatting
Overzicht: Inleiding tot data mining Waarom data mining? Wat is data mining? Het volledige knowledge discovery proces. De data mining taken. Samenvatting
Waarom data mining? Explosieve groei aan beschikbare data: petabytes nieuwe technologie (streepjescode, RFID, …) grotere opslagcapaciteit
Waarom data mining? Ook veel wetenschappelijke data Beschikbaar satellietbeelden astronomische gegevens micro-arrays
Waarom data mining? We are drowning in data, but starving for knowledge! Jiawei Han
Doel van data mining = automatisch analyseren 4,000,000
The Data Gap
3,500,000 3,000,000 2,500,000 2,000,000
Total new disk (TB) since 1995
1,500,000 1,000,000 500,000 0 1995
1996
1997
1998
1999
Number of analysts
Overzicht: Inleiding tot data mining Waarom data mining? Wat is data mining? Het volledige knowledge discovery proces. De data mining taken. Samenvatting
Wat is data mining? Data mining (knowledge discovery from data) Extractie van interessante (niet-triviale, impliciete, vooraf ongekende en mogelijk bruikbare) patronen of kennis uit grote hoeveelheden data
Alternatieve benamingen Knowledge discovery (mining) in databases (KDD), knowledge extraction, data/pattern analysis, data archeology, data dredging, information harvesting, business intelligence, etc.
Data Dredging
“Torturing the data until they confess” If you keep trying, eventually you will succeed.
Huidige toepassingen Data analyse en decision support Markt-analyse en management Risico-analyse en management Fraude detectie en de detectie van vreemde patronen (outliers)
Andere toepassingen Tekst en Web mining (nieuwsgroepen, email, elektronische documenten) Stream data mining Bioinformatica and bio-data analyse
Vb. 1: Markt analyse & management Data: transacties van betaalkaarten, klantenkaarten, kortingbonnen, klachten, plus (publieke) lifestyle studies Target marketing Zoek groepen van klanten met gelijkaardige karakteristieken Bepaal het koopgedrag over de tijd van klanten
Vind associaties tussen produkten, voorspel op basis van associatie
Vb. 2: Fraude detectie & vreemde patronen Autoverzekering: ring of collisions
Witwassen van geld: Verdachte geldtransacties
Zorgverzekering Professionele patienten, cirkels van doorverwijzingen Onnodige medische testen
Vb. 2: Fraude detectie & vreemde patronen Telecommunicaties: telefoon-kaart fraude Maak model van belgedrag: bestemming van het gesprek, duur, tijdstip, weekdag. Analyseer patronen die afwijken van het standaardgedrag.
Belastingsfraude Belgische FOD Financien maakt gebruik van data mining om verdachte belastingsaangiftes te identificeren.
Overzicht: Inleiding tot data mining Waarom data mining? Wat is data mining? Het volledige knowledge discovery proces. De data mining taken. Samenvatting
Knowledge discovery (KDD) Proces Evaluatie
Data mining—het hart van het knowledge discovery Data Mining proces Relevant Data voor de taak Data Warehouse Opschonen Data integratie Databanken
Selectie
Overzicht: Inleiding tot data mining Waarom data mining? Wat is data mining? Het volledige knowledge discovery proces. De data mining taken. Samenvatting
De data mining taken Klassificatie [Voorspellend] Regressie [Voorspellend] Deviatie Detectie [Voorspellend] Clustering [Descriptief] Associatie regels ontdekken [Descriptief] Sequentiele patronen ontdekken [Descriptief]
Voorspellende methods (predictive tasks) Voorspellende methodes Gebruik een aantal variabelen om de waarde van een doel-attribuut te voorspellen.
Classificatie Regressie Deviatie Detectie
Descriptieve Methodes Descriptieve Methodes Vind begrijpbare patronen die de data beschrijven.
Clusters Association Regels Sequentiele Patronen
De data mining taken Classificatie [Voorspellend] Regressie [Voorspellend] Deviatie Detectie [Voorspellend] Clustering [Descriptief] Associatie regels ontdekken [Descriptief] Sequentiele patronen ontdekken [Descriptief]
Classificatie ch ch u ris ris se in o o nt as g g l o e e k t t c ca ca Refund Marital Status
Taxable Income Cheat
No
No
Single
75K
?
No
Yes
Married
50K
?
70K
No
No
Married
150K
?
120K
No
Yes
Divorced 90K
?
Divorced 95K
Yes
No
Single
40K
?
No
Married
No
No
Married
80K
?
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
Tid Refund Marital Status
Taxable Income Cheat
1
Yes
Single
125K
2
No
Married
100K
3
No
Single
4
Yes
Married
5
No
6
60K
10
10
Training Set
Leer Classifier
Test Set
Model
Classificatie Soorten modellen: beslissingsboom regel-gebaseerd nearest neighbor neuraal netwerk
Beslissingsboom refund no
yes Cheat = no
married yes
Cheat = no
no Cheat = yes
Classificatie: toepassing Sky Survey Catalog Doel: Voorspel de klasse (ster of melkweg) van objecten, vooral onduidelijke, gebaseerd op telescoop beelden (Palomar observ.). 3000 beelden met een resolutie van 23,040 x 23,040 pixels Aanpak: Segmenteer de beelden. Meet eigenschappen van het beeld (features) - 40 per segment. Modeleer de klassen gebaseerd op deze features. From [Fayyad, et.al.] Advances in Knowledge Discovery and Data Mining, 1996
Classificeren van melkwegen Early
Courtesy: http://aps.umn.edu
Klasses:
Attributen:
• Fases in het ontstaan
• beeld features, • lichtgolven
Intermediate
Late
Grootte van de dataset: • 72 miljoen sterren, 20 miljoen melkwegen • Object catalog: 9 GB • Beelden Databank: 150 GB
Classificeren van melkwegen Succesverhaal: 16 nieuwe high red-shift quasars werden ontdekt; dit zijn objecten ver verwijderd en moeilijk zichtbaar!
Met het blote oog zou de analyse jaren geduurd hebben …
De data mining taken Klassificatie [Voorspellend] Regressie [Voorspellend] Deviatie Detectie [Voorspellend] Clustering [Descriptief] Associatie regels ontdekken [Descriptief] Sequentiele patronen ontdekken [Descriptief]
Regressie Voorspel de waarde van een gegeven continue variabele gebaseerd op de waarden van andere variabelen.
Veel bestudeerd in statistiek (lineaire regressie, niet-lineaire regressie)
Regressie Voorbeelden: Voorspel de verkoopscijfers van een neiuw produkt gebaseerd op de hoeveelheid geld besteed aan reclamecampagnes. Voorspel windsnelheden op basis van windrichting, luchtdruk, weersomstandigheden, etc. Voorspel de koers van een aandeel op basis van voorgaande koersgegevens.
De data mining taken Klassificatie [Voorspellend] Regressie [Voorspellend] Deviatie Detectie [Voorspellend] Clustering [Descriptief] Associatie regels ontdekken [Descriptief] Sequentiele patronen ontdekken [Descriptief]
3. Deviatie detectie/anomalieen Ontdek significante afwijkingen van het normale gedrag
Toepassingen: Fraude met kredietkaarten Network Intrusies ontdekken
De data mining taken Classificatie [Voorspellend] Regressie [Voorspellend] Deviatie Detectie [Voorspellend] Clustering [Descriptief] Associatie regels ontdekken [Descriptief] Sequentiele patronen ontdekken [Descriptief]
Clustering Gebaseerd op Euclidische afstand in 3D.
Intracluster Intraclusterafstanden afstanden minimaliseren minimaliseren Intercluster Interclusterafstanden afstanden maximaliseren maximaliseren
Clustering: Toepassing 1 Clusteren van documenten: Doel: Vind groepen van documenten
Clustering: Toepassing 1 Clusteren van documenten: Doel: Vind groepen van documenten gebaseerd op de woorden die voorkomen in de verschillende documenten. Aanpak: Identificeer frequente termen in de documenten. Maak een similarity measure gebaseerd op de frequenties van de verschillende termen. Gebruik: Information Retrieval kan hiervan gebruik maken om zoekresultaten per cluster weer te geven.
De data mining taken Klassificatie [Voorspellend] Regressie [Voorspellend] Deviatie Detectie [Voorspellend] Clustering [Descriptief] Associatie regels ontdekken [Descriptief] Sequentiele patronen ontdekken [Descriptief]
Associatie regels Gegeven een verzameling records die elk een aantal items bevatten, vind regels die associaties tussen verzamelingen produkten beschrijven TID
Items
1 2 3 4 5
Brood, Cola, Melk Bier, Brood Bier, Cola, Luier, Melk Bier, Brood, Luier, Melk Cola, Luier, Melk
Regels: Regels:
{Melk} {Melk}--> -->{Cola} {Cola} {Luier, {Luier,Melk} Melk}--> -->{Bier} {Bier}
Association regels: toepassingen Marketing en promoties: Stel dat volgende regel ontdekt werd: {Tortilla chips, … } --> {dipsaus}
Association regels: toepassingen Marketing en promoties: Stel dat volgende regel ontdekt werd: {Tortilla chips, … } --> {dipsaus} dipsaus als consequent => Kan gebruikt worden om te bepalen welke produkten de verkoop van dipsaus stimuleren. Chips als antecedent => Welke produkten zullen invloed ondervinden van het verwijderen van Chips uit het assortiment? Chips als antecedent en dipsaus als consequent => Kan gebruikt worden om te zien welke produkten er samen met chips moeten verkocht worden om dipsaus te promoten
De data mining taken Klassificatie [Voorspellend] Regressie [Voorspellend] Deviatie Detectie [Voorspellend] Clustering [Descriptief] Associatie regels ontdekken [Descriptief] Sequentiele patronen ontdekken [Descriptief]
6. Sequentiele Patronen Gegeven een verzameling sequenties, zoek temporele afhankelijkheden tussen verschillende events.
(A B)
(C)
In telecommunicatie (alarm logs), (Inverter_Problem Excessive_Line_Current) (Rectifier_Alarm) --> (Fire_Alarm)
In sequenties van verkoopsdata, (Schoenen) (Racket, bal) --> (kleding)
(D E)
Sequentiele Patronen: Toepassingen Veel gebruikt in bio-informatica ! identificeer genen in DNA-sequenties
Ontdekken van inbraken in netwerken Leer patronen te identificeren die vaak geassocieerd zijn met inbraken in het netwerk
Uitbreidingen naar het spatio-temporele domein sequentie van locaties van GSMs voorspel volgende positie om hand-over efficienter te maken Monitoren van het verkeer
Overzicht: Inleiding tot data mining Waarom data mining? Wat is data mining? Het volledige knowledge discovery proces. De data mining taken. Samenvatting
Samenvatting Data mining is nuttig: Wanneer de hoeveelheid data te groot is om manueel geanalyseerd te worden Als er vele mogelijke hypotheses zijn
Data mining biedt aan: Verzameling tools om modellen en patronen te herkennen Intelligente zoek-technieken
Resultaten van data mining: Samenvatting van de data Onverwachte patronen Model
