Data Mining: Data kwaliteit, Preprocessing docent: dr. Toon Calders
Gebaseerd op slides van Tan, Steinbach, and Kumar. Introduction to Data Mining
Herhaling: definitie • Data Mining is: – Extractie van interessante (niet-triviale, impliciete, vooraf ongekende en mogelijk bruikbare) patronen of kennis uit grote hoeveelheden data
1
Herhaling: data mining technieken • Beschrijvende (descriptieve) technieken: – Clustering – Outlier detection – Associatie regels, sequentiele patronen
• Predictieve methodes – Classificatie – Regressie
Herhaling: Classificatie • Gebaseerd op gelabelde data: – Leer model van de data – Met als doel nieuwe objecten correct te kunnen classificeren
• Soorten modellen: – Beslissingsboom – Dataset zelf (Nearest neighbors) – …
2
Herhaling: Classificatie • Gebaseerd op een set van gelabelde objecten: – Leer model van de data – Met als doel nieuwe objecten correct te kunnen classificeren
leeftijd <30
geslacht M
HOOG
V
…
≥30
type auto
…
… …
Herhaling: Associatie regels • Gegeven een transactie database – Vind associaties tussen sets van items – Hoge support en confidence
=>
3
Herhaling: Clustering • Gegeven een set van objecten – Deel de objecten op in homogene groepen (mogelijk overlappend)
Vraag • Welke methode sluit het beste aan bij volgende problemen: – Een Search Company wil zoekresultaten weergeven gegroepeerd per topic. – Welke zoektermen komen vaak samen voor in zoekopdrachten? – Ontwerp een spam-filter die ongewenste emails tegen houdt. – Welke kenmerken zijn karakteristiek voor spam-mails?
4
Inhoud van deze les Evaluatie
Data Mining Relevant Data voor de taak Data Warehouse
Selectie
Opschonen Data integratie Databanken
Overzicht Voorbereiden van de data voor data mining • Types van data • Data kwaliteit • Pre-processing • Maten voor afstand en similariteit
5
Overzicht Voorbereiden van de data voor data mining • Types van data – Soorten attributen – Karakteristieken van datasets
• Data kwaliteit • Pre-processing • Maten voor afstand en similariteit
Wat is Data?
Attributen Tid
Refund
Marital Status
Taxable Income
C heat
attributen
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced
95K
Yes
6
No
Married
60K
No
7
Yes
Divorced
220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
• Een attribuut is een eigenschap of karakteristiek van
Objecten
• Collectie data objecten en hun
een object –Vb.: haarkleur van een persoon, etc.
10
• Een verzameling attributen beschrijft een object
6
Soorten Attributen • Nominaal: ID nummer, kleur, zip-code • Ordinaal: rankings (hoog-medium-laag) • Interval: kalender data, temperatuur in C of F. • Ratio: temperaturen in K
Eigenschappen van attributen • Het type hangt af van welke van de volgende operaties ondersteund worden: – Ongelijkheid:
= ≠
– Volgorde:
< >
– Optelling:
+ -
– Vermenigvuldiging:
*/
7
Numeriek\quantitatief Categorisch/kwalitatief
Attribuut Niveau
Transformatie
Commentaar
Nominaal
Elke permutatie van de waarden
Als alle werknemers nummers opnieuw toegekend worden, maakt dit een verschil?
Ordinaal
Elke transformatie die de volgorde bewaart, bvb.,
Slecht-Gemiddeld-Goed kan gecodeerd worden als 1, 2, 3 of als -1, 0, 1, of als …
Interval
new_value =a * old_value + b met a en b constanten
F en C kunnen in elkaar worden omgezet zonder verlies aan betekenis
new_value = a * old_value
Het is zinvol om te spreken over 2xlengte.
Ratio
Discreet en Continue variabelen • Discrete Attributen – Eindig of aftelbaar aantal attributen – Voorbeeld: aantallen, huisnummers, verzameling van woorden in een document – Kan m.b.v. integers voorgesteld worden. – Merk op: binaire attributen zijn een speciaal geval
• Continue Attributen – Reele getallen als waarden – Voorbeelden: temperatuur, gewicht, lengte, …
8
Vraag: Geef voorbeelden van … Discreet
Continu
Nominaal
------------
Ordinaal
------------
Interval
------------
------------
Ratio
------------
------------
Vraag: Geef voorbeelden van … Discreet
Continu
Nominaal
Student IDs
Ordinaal
Goed-Slecht
Interval
Datums
Tijdstippen
Ratio
Aantallen
Lengte
9
Types van data sets
• Record data – Data Matrix – Document Data – Transaction Data
• Graaf data – World Wide Web – Molecular Structures
• Geordende data – – – –
Spatial Data Temporal Data Sequential Data Genetic Sequence Data
Belangrijke karakteristieken van data • Dimensie – Curse of Dimensionality
• Sparsity • Symmetrisch/assymmetrisch •Resolutie • Patronen afhankelijk van schaal
10
Record Data • Data bestaat uit een
Tid Refund Marital Status
Taxable Income Cheat
collectie van records, elk met
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced 95K
Yes
6
No
Married
No
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
een vast aantal attributen
60K
10
Data Matrix • Objecten met een vast aantal attributen kunnen gezien worden als punten in een multi-dimensionele ruimte • m x n matrix, voor elk van de m objecten is er een rij, voor elk van de n attributen is er een kolom. Projection of x Load
Projection of y load
Distance
Load
Thickness
10.23
5.27
15.22
2.7
1.2
12.65
6.25
16.22
2.2
1.1
11
Document data • Elk document voorgesteld door een “term” vector,
season
timeout
lost
wi n
game
score
ball
pla y
coach
team
Transactie Data • Speciaal type van record data –Elk record is een verzameling.
TID
Items
–Vb: supermarkt; de verzameling
1
Bread, Coke, Milk
producten van een klant tijdens 1
2 3 4 5
Beer, Bread Beer, Coke, Diaper, Milk Beer, Bread, Diaper, Milk Coke, Diaper, Milk
bezoek aan de supermarkt komt overeen met 1 transactie
12
Graaf data: een grote graaf • Vb: HTML Links
2 1
5 2 5
Data Mining Graph Partitioning Parallel Solution of Sparse Linear System of Equations N-Body Computation and Dense Linear System Solvers
Graaf data: afzonderlijke grafen • Benzene Molecule: C6H6
13
Geordende data • Sequenties van
Items/gebeurtenissen
transactions
Een element in de sequentie
Geordende data • Genoomsequenties GGTTCCGCCTTCAGCCCCGCGCC CGCAGGGCCCGCCCCGCGCCGTC GAGAAGGGCCCGCCTGGCGGGCG GGGGGAGGCGGGGCCGCCCGAGC CCAACCGAGTCCGACCAGGTGCC CCCTCTGCTCGGCCTAGACCTGA GCTCATTAGGCGGCAGCGGACAG GCCAAGTAGAACACGCGAAGCGC TGGGCTGCCTGCTGCGACCAGGG
14
Geordende data • SpatioTemporele Data
Gemiddelde maandtemperatuur
Overzicht Voorbereiden van de data voor data mining • Types van data • Data kwaliteit – Welke problemen? – Hoe ontdekken? – Wat er aan doen?
• Pre-processing • Maten voor afstand en similariteit
15
Data kwaliteit • Soorten problemen: – Ruis en outliers – Ontbrekende waarden – duplicaten
Ruis • Ruis
Two Sine Waves
Two Sine Waves + Noise
16
Outliers • Outliers zijn data objecten met significant afwijkende karakteristieken
Ontbrekende waarden • Oorzaken – Informatie was niet beschikbaar (Vb. Sommige mensen willen hun leeftijd of gewicht niet opgeven) – Niet alle attributen van toepassing op alle objecten (vb. Jaarinkomen bij kinderen)
• Hoe er mee omgaan? – – – –
Elimineren van objecten met ontbrekende waarden Schatten van de waarden Negeer de ontbrekende waarden Vervang met alle mogelijkheden + waarschijnlijkheidsdistributie
17
Duplicaten • Typisch probleem wanneer we data uit verschillende bronnen combineren • Voorbeelden: – Persoon heeft meerdere email-adressen
• Data cleaning – Proces van het wegwerken van duplicaten
Overzicht Klaarmaken van de data voor data mining • Types van data • Data kwaliteit • Pre-processing • Maten voor afstand en similariteit
18
Data Pre-processing • Objecten – Aggregatie – Sampling
• Attributen – Dimensionality Reduction – Feature subset selectie – Feature creatie – Discretizatie and Binarizatie – Attribuut Transformatie
Data Pre-processing • Objecten – Aggregatie – Sampling
• Attributen – Dimensionality Reduction – Feature subset selectie – Feature creatie – Discretizatie and Binarizatie – Attribuut Transformatie
19
Aggregatie • Combineren van twee of meer attributen/objecten in een enkel attribuut/object • Doel – Data reductie – Schaalgrootte aanpassen Steden geaggregeerd in regios, landen, …
– Stabielere data Geagregeerde data heeft minder variabiliteit (in het algemeen)
Aggregatie Variatie van neerslag in Australie
Gemiddelde maandelijkse neerslag
Gemiddelde jaarlijkse neerslag
20
Data Pre-processing • Objecten – Aggregatie – Sampling
• Attributen – Dimensionality Reduction – Feature subset selectie – Feature creatie – Discretizatie and Binarizatie – Attribuut Transformatie
Sampling • De belangrijkste data selectie techniek. – Vaak gebruikt bij een eerste analyse van de data.
• Sampeling heeft verschillende doelen – Statistiek: data van volledige populatie is niet beschikbaar (steekproef) – Data mining: de data is wel bechikbaar, maar de algoritmes schalen niet goed met de beschikbare data
21
Sampling • Belangrijkste principes: – Als de data representatief is, dan werkt sampling over het algemeen genomen even goed als het gebruiken van de volledige dataset.
– Een sample is representatief als de eigenschappen die van belang zijn voor de analyse hetzelfde zijn in de sample als in de oorspronkelijke data.
Types van Sampling • Simple Random Sampling – Gelijke kans voor elk object om geselecteerd te worden
• Sampling zonder teruglegging – Elk object kan slechts 1 maal geselecteerd worden
• Sampling met teruglegging – Objecten kunnen meermaals geselecteerd worden
• Stratified sampling – Data wordt verdeeld over verschillende partities en de partities worden afzonderlijk gesampled
22
Sample grootte
8000 points
2000 Points
500 Points
• Vraag: welke sample-grootte is nodig om uit elk van de 10 groepen minstens 1 object te hebben?
23
Data Pre-processing • Objecten – Aggregatie – Sampling
• Attributen – Dimensionality Reduction – Feature subset selectie – Feature creatie – Discretizatie and Binarizatie – Attribuut Transformatie
Curse of Dimensionality • Wanneer de dimensie van data toeneemt, wordt de ruimte “leger”
• Dichtheid en afstand verliezen hun betekenis –Zijn kritisch voor clustering
• 500 random gegenereerde punten • Bereken het relatieve verschil tussen de maximum en minumum afstand over alle paren van punten
24
Data Pre-processing • Objecten – Aggregatie – Sampling
• Attributen – Dimensionality Reduction – Feature subset selectie – Feature creatie – Discretizatie and Binarizatie – Attribuut Transformatie
Dimensionality Reduction • Doel: – – – –
Vermijd curse of dimensionality Reduceer berekeningstijd van data mining algoritmes Betere visualisatie Kan ruis en irrelevante factoren verwijderen
• Technieken – Principle Component Analysis – Singular Value Decomposition – Anderen: gesuperviseerde en niet-lineaire technieken
25
Dimensionality Reduction: PCA • Doel is een projectie te vinden die de grootste variabiliteit van de data vat. x2 e
x1
Dimensionality Reduction: PCA • Zoek de eigenvectoren van de covariantie-matrix • De eigenvectoren vormen de nieuwe basis x2 e
x1
26
Data Pre-processing • Objecten – Aggregatie – Sampling
• Attributen – Dimensionality Reduction – Feature subset selectie – Feature creatie – Discretizatie and Binarizatie – Attribuut Transformatie
Feature Subset Selectie • Andere manier om het aantal dimensies te reduceren • Redundante features – Dupliceren veel van de informatie in de andere attributen – Vb: prijs van een produkt en de hoeveelheid taksen betaald op dat produkt
• Irrelevante features – Bevat geen informatie voor de data mining taak – Vb: studentnummer, haarkleur hebben weinig relatie met de studieresultaten van studenten.
27
Feature Subset Selectie • Technieken: – Brute-force: Probeer alle mogelijkheden
– Embedded: Ingebouwd in het algoritme
– Filter: Vooraf, voor de data mining algoritmes worden uitgevoerd
– Wrapper: Gebruik het data mining algoritme als een black box om verschillende feature sets te evalueren
Data Pre-processing • Objecten – Aggregatie – Sampling
• Attributen – Dimensionality Reduction – Feature subset selectie – Feature creatie – Discretizatie and Binarizatie – Attribuut Transformatie
28
Feature Creatie • Creeer nieuwe attributen die relevant zijn voor de huidige data mining taak • Drie algemene methodologieen: – Feature Extraction – Data transformeren naar een nieuwe ruimte – Feature Construction
Data transformeren naar een nieuwe ruimte • Fourier transformatie • Wavelet transformatie
2 sinussen
Superpositie + ruis
Frequenties
29
Data Pre-processing • Objecten – Aggregatie – Sampling
• Attributen – Dimensionality Reduction – Feature subset selectie – Feature creatie – Discretisatie and Binarisatie – Attribuut Transformatie
Discretiseren met behulp van Class Labels • Vaak gebaseerd op entropie
3 categories for both x and y
5 categories for both x and y
30
Discretiseren zonder Class Labels
Data
Gelijke frequentie
Gelijke interval breedte
K-means
Overzicht Klaarmaken van de data voor data mining • Types van data • Data kwaliteit • Pre-processing • Maten voor afstand en similariteit (Verplaatst naar les 3)
31