Data Mining: similariteit en visuele data exploratie docent: dr. Toon Calders
Gebaseerd op slides van Tan, Steinbach, and Kumar. Introduction to Data Mining
Overzicht: wat zagen we vorige les? • Data karakteristieken – Soorten attributen • Nominaal, ordinaal, interval, ratio
– Data-formaten • Record data, transactie data, grafen, …
– Dimensie van de data • Curse of dimensionality
1
Overzicht: wat zagen we vorige les? • Data kwaliteit – Ruis – Ontbrekende waarden – Duplicaten
Overzicht: wat zagen we vorige les? • Data preprocessing: – – – – – – –
Aggregatie Sampling Dimensionality Reduction Feature subset selectie Feature creatie Discretizatie and Binarizatie Attribuut Transformatie
2
Wat zien we deze les? • Laatste onderdeel van “data” – Meten van afstand en similariteit – Belangrijke input voor vele algoritmes
• Exploreren van data – Samenvattende statistieken – Visuele methodes
Deel 1: Similariteit en afstand • Wat? • Voor 1 attribuut • Meerdere attributen van hetzelfde type • Meerdere attributen, verschillende types
3
Similariteit en Dissimilariteit • Similariteit – Numerieke maat van gelijkenis tussen objecten. – Hoger als objecten meer gelijk. – Vaak in het interval [0,1]
• Dissimilariteit – Numerieke maat voor verschil tussen objecten. – Lager als objecten meer gelijk. – Minimale dissimilariteit is vaak 0. – Bovengrens is variabel
• Proximity verwijst naar beide
Deel 1: Similariteit en afstand • Wat? • Voor 1 attribuut • Meerdere attributen van hetzelfde type • Meerdere attributen, verschillende types
4
Similariteit/Dissimilariteit voor 1 attribuut p en q zijn de attribuutwaarden voor twee records.
Deel 1: Similariteit en afstand • Wat? • Voor 1 attribuut • Meerdere attributen van hetzelfde type – Numeriek – Binair
• Meerdere attributen, verschillende types • Similariteiten voor sequenties, strings
5
Euclidische afstand • Euclidische afstand
dist =
n
∑ ( pk
k =1
− qk )2
n = aantal dimensies, pk en qk : k-de component van resp. object p en q.
• Standaardisatie is noodzakelijk als de schaal ongelijk is.
Vraag • Standaardisatie is noodzakelijk als de schaal ongelijk is … --- Waarom?
6
Vraag • Standaardisatie is noodzakelijk als de schaal ongelijk is … --- Waarom? Anders kunnen enkele dimensies een te grote rol spelen en de andere dimensies irrelevant maken. Vb: attributen Leeftijd (L) en Inkomen (I) d((30,1900), (32,2000) ) = 22 + 1002 Genormaliseerd (op 100 en op 5000): d((0.30,0.38), (0.32,0.40) ) = (0.02)2 + (0.02)2
Euclidische afstand 3
point p1 p2 p3 p4
p1
2
p3
p4
1 p2
0 0
1
2
3
4
5
y 2 0 1 1
6
p1 p1 p2 p3 p4
x 0 2 3 5
0 2.828 3.162 5.099
p2 2.828 0 1.414 3.162
p3 3.162 1.414 0 2
p4 5.099 3.162 2 0
Distance Matrix
7
Minkowski afstand • Minkowski afstand is een veralgemening van de Euclidische n
dist = ( ∑ | pk − qk
1 |r ) r
k =1
r : parameter n : aantal dimensies pk , qk : k-de component van resp. object p en q.
Minkowski afstand: Voorbeelden • r = 1. City block (Manhattan, taxicab, L1) – Hamming distance; aantal bits verschillend in twee binaire vectoren.
• r = 2. Euclidische afstand • r → ∞. “supremum” (Lmax norm, L∞ norm) – Maximale verschil tussen de componenten van twee vectoren.
• Opgepast! Verwar r niet met n; al deze afstandsmaten zijn gedefinieerd voor alle aantallen dimensies.
8
Minkowski afstand
point p1 p2 p3 p4
x 0 2 3 5
y 2 0 1 1
L1 p1 p2 p3 p4
p1 0 4 4 6
p2 4 0 2 4
p3 4 2 0 2
p4 6 4 2 0
L2 p1 p2 p3 p4
p1
p2 2.828 0 1.414 3.162
p3 3.162 1.414 0 2
p4 5.099 3.162 2 0
L∞ p1 p2 p3 p4
p1
p2
p3
p4
0 2.828 3.162 5.099
0 2 3 5
2 0 1 3
3 1 0 2
5 3 2 0
Afstandsmatrices
Vraag: • Wat gebeurt er indien er correlatie bestaat tussen de verschillende attributen? – Helpt normalisatie? – Worden sommige attributen overbodig? Welke? – Hoe voorkom je mogelijke problemen?
9
Vraag: • Wat gebeurt er indien er correlatie bestaat tussen de verschillende attributen? – Extreem geval: attribuut A1 = A2 en een attribuut B: • d(o1,o2)
= =
(o1.A1 - o2.A1)2 + (o1.A2 -o2.A2)2 + (o1.B -o2.B)2 2 (o1.A - o2.A)2 + (o1.B -o2.B)2
– Komt vaak voor; dit trekt de verhoudingen tussen de attributen scheef
Vraag: • Wat gebeurt er indien er correlatie bestaat tussen de verschillende attributen? – Mogelijke oplossing: dimensionality reduction bvb. Principal component analysis; ontbind de dimensies in orthogonale componenten. – Volgende slide bevat andere mogelijke oplossing
10
Mahalanobis afstand mahalanobi s ( p , q ) = ( p − q ) ∑ −1 ( p − q )T
Σ is de co-variantie matrix van de input matrix X
Σ j ,k =
1 n ∑ ( X ij − X j )( X ik − X k ) n − 1 i =1
Voor de rode punten is de Euclidische afstand 14.7, de Mahalanobis afstand is 6.
Mahalanobis afstand Co-variantie matrix:
0.3 0.2 Σ= 0.2 0.3 C A: (0.5, 0.5) B
B: (0, 1) A
C: (1.5, 1.5)
Mahal(A,B) = 5 Mahal(A,C) = 4
11
Mahalanobis afstand: interpretatie
Mahalanobis afstand: interpretatie
12
Vraag • Waarom lost Mahalanobis het probleem van de gecorreleerde attributen op? – Illustreer met het “extreme voorbeeld”
Vraag • Waarom lost Mahalanobis het probleem van de gecorreleerde attributen op? – Illustreer met het “extreme voorbeeld” Twee objecten met bijna gelijke A1 – waarde zullen ook slechts klein verschil hebben op A2. Door de sterke correlatie tussen die twee attributen, echter, is de “bol” die de distributie beschrijft erg plat in het A1-A2 vlak met breedte in de richting van gelijke A-waarden.
13
Metrieken • Afstanden zoals de Euclidische, hebben een aantal eigenschappen: 1. voor alle p en q: d(p, q) ≥ 0 d(p, q) = 0 asa p = q. (Positief definiet) 2. voor alle p en q: d(p, q) = d(q, p) (Symmetrie) 3. voor alle p, q en r : d(p, r) ≤ d(p, q) + d(q, r) (Driehoeksongelijkheid)
• Een afstandsmaat die hieraan voldoen noemen we een metriek
Eigenschappen van een similariteit • Enkele vaak voorkomende eigenschappen: 1. s(p, q) = 1 (of de maximale similariteit) asa p = q. 2. s(p, q) = s(q, p) voor alle p en q. (Symmetrie)
14
Similariteit tussen binaire vectoren • Vaak voorkomend: p en q hebben enkel binaire attributen. • We gebruik volgende getallen in de definities: M00 = aantal attributen met p = 0 en q = 0 M01 = aantal attributen met p = 0 en q = 1 M10 = aantal attributen met p = 1 en q = 0 M11 = aantal attributen met p = 1 en q = 1
• Simple Matching en Jaccard Coefficient SMC = aantal gelijken / aantal attributen = (M11 + M00) / (M01 + M10 + M11 + M00)
J = aantal 11 matches / aantal niet 0-0 paren = (M11) / (M01 + M10 + M11)
SMC versus Jaccard: Voorbeeld p= 1000000000 q= 0000001001 M01 = 2 M00 = 7
M10 = 1 M11 = 0
SMC = (M11 + M00)/(M01 + M10 + M11 + M00) = (0+7) / (2+1+0+7) = 0.7 J = (M11) / (M01 + M10 + M11) = 0 / (2 + 1 + 0) = 0
15
Cosinus similariteit • Als d1 and d2 bvb. document-vectoren zijn cos( d1, d2 ) = (d1 • d2) / ||d1|| ||d2|| , • is het scalair produkt tussen vectoren en || d || is de lengte van vector d.
• Voorbeeld: d1 = 3 2 0 5 0 0 0 2 0 0 d2 = 1 0 0 0 0 0 0 1 0 2 d1 • d2= 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5 ||d1|| = (3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481 ||d2|| = (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2) 0.5 = (6) 0.5 = 2.245
cos( d1, d2 ) = .3150
Tanimoto Coefficient • Voor continue of count-attributen
16
Vraag • Met welke maat komt Tanimoto overeen indien we ons beperken tot binaire attributen?
Vraag • Met welke maat komt Tanimoto overeen indien we ons beperken tot binaire attributen?
Jaccard. Daarom is deze maat ook bekend als “extended Jaccard”
17
Correlatie • Correlatie meet de mate van lineair verband tussen twee attributen • Correlatie berekenen = vectoren normaliseren en vervolgens het scalair produkt nemen.
pk′ = ( pk − mean( p)) / std ( p)
qk′ = ( qk − mean( q)) / std (q) correlation( p, q) = p′ • q′
Visueel correlatie herkennen
Scatter plots tonen correlaties van –1 tot 1.
18
Opgelet! • Correlatie meet enkel in welke mate er een lineair verband is!
Deel 1: Similariteit en afstand • Wat? • Voor 1 attribuut • Meerdere attributen van hetzelfde type – Numeriek – Binair
• Meerdere attributen, verschillende types •Similariteiten voor sequenties, strings
19
Combineren van similariteiten • Soms hebben attributen verschillende types, maar is er toch een similariteitsmaat nodig.
Gebruik van gewichten bij combinaties • Indien niet alle attributen even belangrijk. – Gebruik gewichten wk tussen 0 en 1 die sommeren tot 1.
20
Deel 1: Similariteit en afstand • Wat? • Voor 1 attribuut • Meerdere attributen van hetzelfde type – Numeriek – Binair
• Meerdere attributen, verschillende types • Similariteiten voor sequenties, strings
Andere afstandsmaten • Voor strings – Edit distance (Levenshtein distance)
• DNA sequences • Voor sequenties – Time-warping distance
21
Edit distance • Afstand tussen twee strings: minimale aantal operaties om de ene in de andere om te zetten – Invoegen van een karakter (insert) – Verwijderen van een karakter (delete) – Substituteren van een karakter
•Voorbeeld: – paard paad parad parade afstand = 3 – eauivlaent equivlaent equivaent equivalent afstand = 3
Edit distance • Afstand tussen twee strings: minimale aantal operaties om de ene in de andere om te zetten – Invoegen van een karakter (insert) – Verwijderen van een karakter (delete) – Substituteren van een karakter
• Relatief duur om uit te rekenen – Dynamisch programmeren
22
Edit distance: algoritme _
P
A
A
R
D
_ P A R
vullen van matrix entry i,j: edit distance tussen t[1..i] en s[1..j]
A D E
Edit distance: algoritme _
P
A
A
R
D
_
0
1
2
3
4
5
P
1
A
2
R
3
A
4
D
5
E
6
Invullen van matrix: recursief d[i,j] = min { d(i-1, j) + 1 (del) d(i,j-1) + 1 (ins) d(i-1,j-1) + cost } (match of subst.)
23
Edit distance: algoritme _
P
A
A
R
D
_
0
1
2
3
4
5
P
1
0
1
2
3
4
A
2
1
0
1
2
3
R
3
2
1
1
1
2
A
4
3
2
1
2
2
D
5
4
3
2
2
2
E
6
5
4
3
3
3
Afstand voor DNA sequenties • Matching in BLAST (Basic Local Alignment and Search Tool) is gebaseerd op soort match die we hier beschrijven • Similarity gedefinieerd als maximale match ATGGCGT *** !** ATG-AGT
24
Sequence alignment • Voor elke mogelijke alignment wordt een score gegeven: – Gebaseerd op de scores tussen residuen plus “strafpunten” voor gaps • A-A score kan lager zijn dan een C-C score • Score van een A-G fout kan zwaarder zijn dan een A-C fout • Gebaseerd op tabellen
– Alignment van een gap met een gap is zinloos – De alignment score is de som van de scores voor de residuen min de strafpunten
Sequence alignment • Simpel score mechanisme: match = 1, nietmatch = -1, gaps niet bestraft • Beste alignment: ATGGCGT ATG-AGT 1 + 1 + 1 + 0 – 1 + 1 + 1 = 4 •Alternatief: ATGGCGT A-TGAGT 1 + 0 - 1 + 1 - 1 + 1 + 1 = 2
25
Sequence alignment • De substitutie matrix geeft aan wat de score is voor een bepaalde match C T A G
C 1 -1 -1 -1
T -1 1 -1 -1
A -1 -1 1 -1
G -1 -1 -1 1
• Er bestaan vaste tabellen waarbij de score gebaseerd is op evolutionaire theorieen; het kan zijn b.v.b. dat een AC mutatie veel waarschijnlijker is dan een AG
BLOSUM62 substitutie matrix
26
Afstand voor DNA sequenties • Gaps moeten ontmoedigd worden – Verstoren de alignment – Veranderen het volledige “time-frame”
• Beter 1 grote gap i.p.v. meerdere kleintjes • Voorbeeld: gap van lengte n krijgt strafpunten: gap_penalty(n) = 5 + 2 x n
Afstand voor DNA sequenties • Similariteit van twee sequenties kan nu gedefinieerd worden als de maximale score over alle alignments. • Er kan opnieuw een dynamisch algoritme gebruikt worden: – Needleman-Wunsch –…
• Opnieuw duur; bestaan vele benaderende algoritmes
27
Time warping afstand voor sequenties
Vaste tijd Punten van de sequenties 1 per 1 matchen
Geen vasts tijd; “Warped” Niet-lineaire alignments mogelijk
Samenvattend • Verschillende afstandsmaten – Belangrijk voor visualisatie, clustering, classificatie, …
• Voor numerieke attributen – Klasse van Minkowski metrieken – Mahalanobis voor gecorreleerde attributen
• Binaire en count attributen – Jaccard, Simple matching – Cosine, extended Jaccard
• Combinaties
28
Deel 2: Data Exploratie
Wat is data exploratie? Eerste onderzoek om karakteristieken van de data te leren kennen • Motivatie – Betere selectie van pre-processing en analyse tools – Gebruik maken van menselijke capaciteit om patronen te herkennen • Visuele patronen
• Gerelateerd aan Exploratory Data Analysis (EDA)
29
Technieken in data exploratie • Origineel gedefinieerd door Tukey: – Focus op visualisatie – Omvat clustering en anomalie detectie • In tegenstelling tot de DM wereld: eigen onderzoeksgebieden
• In deze uiteenzetting, vooral focus op: – Summary statistics – Visualisatie – Online Analytical Processing (OLAP)
Inhoud •Summary statistics •Visualisatie •Online Analytical Processing (OLAP)
30
Iris Sample Data Set • Veel voorbeelden worden geillustreerd met de Iris Plant data set (UCI ML Repository) – Drie bloemtypes (klassen): Setosa • Virginica • Versicolour •
– Vier andere attributen • breedte en lengte van het kelk- en bloemblad
Virginica. Robert H. Mohlenbrock. USDA NRCS. 1995. Northeast wetland flora: Field office guide to plant species. Northeast National Technical Center, Chester, PA. Courtesy of USDA NRCS Wetland Science Institute.
Summary Statistics • Samenvattende statistieken: getallen die de data samenvatten in 1 getal – O.a. Locatie: mediaan, gemiddelde, modus Spreiding: standaard afwijking frequentie – De meeste samenvattende statistieken kunnen berekend worden in 1 data scan.
31
Frequentie en modus • Frequentie van een waarde = aantal maal deze waarde voorkomt – Bvb. “man” komt ongeveer 50% voor als geslacht = frequentie van man is 50%
• De modus is de meest voorkomende waarde • Frequentie en modus worden meest gebruikt bij categorische data – Eerst discretiseren
Percentielen • Voor continue data zijn percentielen meer geschikt. Gegeven een geordend attribuut X in dataset D. Het p-de percentiel voor X in D is een getal xp zodat p% van de punten in D een Xwaarde hebben die kleiner of gelijk is aan Xp. • Bvb. 50% van de waarden zijn kleiner of gelijk en 50% zijn groter dan het 50-ste percentiel.
32
Locatie: gemiddelde en mediaan • Gemiddelde meest bekende voor locatie. • Echter, gemiddelde is gevoelig voor outliers. • Daarom: ook mediaan of trimmed mean.
Spreiding: Bereik en variantie • Bereik = verschil minumum en maximum • Variantie en standaard afwijking: meest gebruikt om spreiding te geven.
• Ook gevoelig voor outliers, daarom:
33
Inhoud •Summary statistics • Visualisatie •Online Analytical Processing (OLAP)
Visualisatie technieken: Histogrammen • Histogram – Distributie van de waarden van 1 variabele – Onderverdeling in bins; hoogte proportioneel aan frequentie. – Vorm v/h histogram hangt af van aantal bins • Voorbeeld: breedte bloemblad (10 vs 20 bins)
34
2D Histogrammen • Toont de gezamelijke distributie van 2 var’s. • Vb: breedte en lengte v/d bloembladen
Visualisatie techniek: Box Plots • Box Plot (J. Tukey) – Toont ook de distributie van de data outlier
90ste percentiel
75ste percentiel 50ste percentiel 25ste percentiel
10de percentiel
35
Voorbeeld van Box Plots
Visualisatie techniek: Scatter-plot • Attribuutwaarden bepalen positie • 2D of 3D • Extra attributen via grootte, kleur, vorm, … • Matrix van scatterplots
36
Scatter-plot matrix van de Iris attributen
Visualisatie techniek: Contour plot • Continu attribuut op spatial grid • Partitioneren van de ruimte – Punten met gelijke waarde verbinden – Cfr. hoogtelijnen – Temperatuur, regenval, etc.
37
Voorbeeld: SST Dec, 1998
Celsius
Visualisatie techniek: Matrix plot • Plot van de data matrix • Nuttig indien objecten geordend naar klasse • Attributen worden typisch genormaliseerd • Ook plots van similariteits- en afstandsmatrices zijn erg bruikbaar voor visuele inspectie van de relatie tussen objecten.
38
Visualisatie van de Iris data matrix
standard deviation
Visualisatie van de correlatie matrix
39
Visualisatie techniek: parallelle coordinaten • Voor hoog-dimensionele data • Parallelle assen i.p.v. loodrechte • Attribuutwaarden van zelfde object worden verbonden door een lijn • Ordening van attributen is belangrijk • Vaak “clusteren” de lijnen samen in groepen voor een aantal attributen.
Parallelle coordinaten voor de Iris data
40
Andere visualisatie technieken •Star Plots – Gelijkaardig aan parallelle coordinaten, maar nu zijn de assen radiaal (cfr. spaken in een wiel) – De verbindingslijn is nu een polygoon
•Chernoff “gezichten” – Elk attribuut is een karakteristiek van het gelaat – De attribuutwaarden komen overeen met een uitdrukking van de geassocieerde karakteristiek – Elk object is een gezicht – Gebaseerd op “gelaatsherkenning”
Star plots voor sample van de Iris data Setosa
Versicolour
Virginica
41
Chernoff “gezichten” Setosa
Versicolour
Virginica
Inhoud • Summary statistics • Visualisatie • Online Analytical Processing (OLAP)
42
OLAP • On-Line Analytical Processing (OLAP) voorgesteld door E. F. Codd. • Relationele databases zetten data in tabellen; OLAP gebruikt een multidimensionele array. • Aantal analyse- en exploratie- taken zijn makkelijker uit te drukken wanneer de data als een cube gezien worden.
Pr od u
TV PC VCR sum
1Qtr
2Qtr
Date 3Qtr
4Qtr
sum Ireland France Germany
Country
ct
Data Cube
sum
43
Data Cube - operaties • Slice/dice: restricteer verschillende dimensies • Roll-up en Drill-down: ga hoger resp. lager in de hierarchie (aggregatie) • Pivoteren: construeer draaitabellen
Samenvatting: Data exploratie • Aantal Summary statistics – Een enkel getal dat de data beschrijft (locatie, spreiding, …)
• Aantal visualisatie technieken – 1 attribuut: histogram, box plot – 2 attributen: scatter plot – Meerdere attributen: matrix plot, parallelle coordinaten, star plots, Chernoff gezichten
• Online Analytical Processing (OLAP)
44
