Embed Size (px)
Citation preview
Data Mining
8.5.2007
Georg Pölzlbauer
Datenmatrix (1)
• Messungen werden in Tabellenform dargestellt
• N Zeilen sind gemessene Objekte xi
(samples, patterns)
• D Spalten sind Merkmale (features, variables)
NDN
D
xx
xx
X
1
111
Datenmatrix (2)
• Beispiel: Umfrage; es werden 100 Personen zu ihrer Einstellung zu 5 politischen Parteien gefragt (Bewertung auf Skala von 0 bis 10)
100 Zeilen, 5 Spalten
• Es gibt auch andere Arten von Daten (z.B. Zeitreihen, strukturierte Daten, …), diese sind aber nicht Thema dieser Vorlesung
Geometrische Interpretation (1)
• Samples xi sind Punkte in einem Vektorraum
• "Datenpunkte" bilden Datenwolke
Geometrische Interpretation (2)
1,50 1,60 1,70 1,80 1,90
40
50
60
70
80
90
100
Gewicht(kg)
Größe(m)
Skalentypen (1)
• NominalskalaWerte stehen in keiner Ordnung zueinander,
unterschiedliche Werte sind sich alle gleich unähnlich
z.B. Haarfarbe (blond, brünett, schwarz, …)
• Ordinalskalanumerische Skala, aber Abstände zwischen
den Werten haben keine Bedeutungz.B. Noten (ist der Abstand zw. 4 und 5 genau
so groß wie der zwischen 2 und 3?)
Skalentypen (2)
• IntervallskalaAbstand zwischen 2 Werten kann gemessen
und mit anderen Abständen verglichen werden
z.B. Temperatur (in Celsius, Fahrenheit)
• Verhältnisskalawie Intervallskala, man kann aber Verhältnisse
berechnen, hat sinnvollen Nullpunktz.B. Gewicht, Größe (Person A ist 1,2x so groß
wie B)
Metriken (1)
• Welche Datenpunkte sind ähnlich?
• Euklidische Distanz (L2-Metrik)
• Manhattan Distanz (L1-Metrik, City-Block)
D
iii xxxxxxd
1
2212121 )(),(
D
iii xxxxxxd
1212121 ),(
Metriken (2)
Abstand?
Metriken (2)
EuklidischeDistanz
Metriken (2)
City Block
Mittelwert, Varianz (1)
• Arithmetisches Mittel (Mittelwert, mean) kann pro Merkmal gebildet werden
• Streuungsmaße wie Varianz bzw. Standardabweichung können ebenfalls für jedes Merkmal berechnet werden
N
iijj x
Nx
1
1
Mittelwert, Varianz (2)
1,50 1,60 1,70 1,80 1,90
40
50
60
70
80
90
100
Gewicht(kg)
Größe(m)
1x
2x
Mittelwert, Varianz (2)
1,50 1,60 1,70 1,80 1,90
40
50
60
70
80
90
100
Gewicht(kg)
Größe(m)
s1
s2
1-zu-N Kodierung (1)
• Die meisten Data Mining Algorithmen benötigen intervallskalierte Daten
• Problem v.a. bei kategorischen Daten (nominalskaliert)
• Lösung: Eine binäre Variable für jede mögliche Ausprägung
1-zu-N Kodierung (2)
feature
red
blue
green
red
red
green
blue
red blue green
1 0 0
0 1 0
0 0 1
1 0 0
1 0 0
0 0 1
0 1 0
Fehlende Werte
• Oft vorkommendes Problem bei Data Mining
• Mögliche Lösungen:– Verfahren verwenden, die damit umgehen
können (Decision Trees, SOMs) – Diese Samples weglassen – Werte interpolieren (missing value prediction)
Ausreißer
• Ausreißer können Fehlmessungen oder einfach stark untypische Samples sein
• Problem bei Berechnung von Varianz, Kovarianz etc.
• Robuste Statistik: Median, Quartile, etc.
Normalisierung von Daten (1)
1,50 1,60 1,70 1,80 1,90
40
50
60
70
80
90
100
Gewicht(kg)
Größe(m)
Abstand = sqrt(0,3^2 + 45^2)= sqrt(2025,09)
= 45
45
0,3
Normalisierung von Daten (1)
1500 1600 1700 1800 1900
40
50
60
70
80
90
100
Gewicht(kg)
Größe(mm)
Abstand = sqrt(300^2 + 45^2)= sqrt(92025)
= 303
45
300
Normalisierung von Daten (2)
• Die Abstandsmeßung sollte von der Maßeinheit der Merkmale unabhängig gemacht werden
• Standardisierung (zero-mean-unit-variance):
j
jijij s
xxz
Normalisierung von Daten (3)
1,50 1,60 1,70 1,80 1,90
40
50
60
70
80
90
100
Gewicht(kg)
Größe(m)
Normalisierung von Daten (3)
-2 -1 0 1 2
-3-2-1
01
23
Gewicht
Größe
5,5
4,5
Normalisierung von Daten (4)
Chebyshevs Ungleichung75% der standardisierten Werte zwischen -2
und +2
89% der Werte zwischen -3 und +3
94% der Werte zwischen -4 und +4
Dichtefunktion
• Es wird angenommen, daß den gemessenen Werten (Datenmatrix) eine Dichtefunktion zu Grunde liegt
• Diese Funktion ist unbekannt, es ist eine unserer Aufgaben sie zu schätzen
Normalverteilung (1)
• Die Normalverteilung nimmt in der Statistik eine besondere Rolle ein
• Eine Zufallsvariable X ist normalverteilt:
),(~ 2NX
2)(2
1
2
1)(
x
exf
Normalverteilung (2)
Multivariate Verteilungen (1)
• MV Zufallsvariable werden durch mehrdimensionale Dichtefunktionen beschrieben
• Für MV Normalverteilung schreibt man z.B. ),(~ NX
Zufallsvektor Vektor von Mittelwerten
Kovarianzmatrix
Multivariate Verteilungen (2)
Stichproben (1)
• Die konkreten Ausprägungen, die gemessen werden, sind Stichproben der Population
• Die Stichprobe besteht aus N Samples, Population wird durch kontinuierliche Dichtefunktion beschrieben
Stichproben (2)
Population vs. Stichprobe
Stichprobe Population
Mittelwert
Varianz
Bayes Theorem (1)
• Oft stehen Zufallsereignisse mit einander in Verbindung
• Wenn man z.B. die Ereignisse „die Erde ist naß“ (A) und „es regnet“ (B) betrachtet:– Wahrscheinlichkeiten P(A) = 0,15 und P(B) =
0,12– Mit der Information, daß der Boden naß ist
(also A eingetreten ist), scheint es wahrscheinlicher, daß es regnet
Bayes Theorem (2)
• Bedingte Wahrscheinlichkeit:P(B|A) = 0,8
D.h. unter der Voraussetzung, dass der Boden naß ist, regnet es mit W. von 80% (ohne dieser Information: 12%)
• Das Bayes Theorem erlaubt die Berechnung der W. in die andere Richtung (d.h. wenn man die Bedingung vertauscht)
Bayes Theorem (3)
• Bayes Theorem:
• Z.B.: P(A|B)… W. daß der Boden naß ist wenn es regnet
• P(A|B) = 0,15*0,8/0,12 = 1
)(
)|()()|(
BP
ABPAPBAP
Kovarianz
• Kovarianz mißt die Stärke des linearen Zusammenhangs zweier Variablen
1,50 1,60 1,70 1,80 1,90405060708090
100
Gewicht(kg)
Größe(m)
Kovarianzmatrix
• Die Kovarianzmatrix hat die Varianzen der Variablen in der Diagonale, und die Kovarianzen außerhalb der Diagonale
• Beispiele:
2212
1221
232313
232212
131221
Korrelation
• Standardisierte Kovarianz (dimensionslos, zwischen -1 und +1, ähnlich Normalisierung)
• Negative Korrelation: Wenn x1 steigt, sinkt x2
• Positive Korrelation: Wenn x1 steigt, steigt auch x2
• Korrelation = 0: Kein linearer Zusammenhang
Schiefe (1)
• Weiteres „statistisches Moment“ (neben Mittelwert, Varianz)
• Schiefe ist ungleich 0 wenn Verteilung nicht symmetrisch
Schiefe (2)
Informationstheorie: Entropie
Datenanalyse: Scatterplots
Hauptkomponentenanalyse
