Thematisch verwandte (aufbauende) Lehrveranstaltungen
SS 188.464, Data Mining, 2 VO WS 181.191, Machine Learning, 2
VU WS 188.413, Selbstorganisierende
Systeme, 3 VU SS 188.412, Information Retrieval, 3
VU
Weiterführende Themen
Data Mining Tutorials: http://www.autonlab.org/tutorials/
WS 183.425, Statistische Mustererkennung, 2 VO + 2 UE
SS 107.284, AKSTA Advanced Regression and Classification, 2 VU
Übersicht
I. Hauptkomponentenanalyse (PCA)II. Problemstellung: Überwachtes
LernenIII. k-Nearest NeighborsIV. Decision TreesV. Lineare KlassifizierungVI. ModellselektionVII. Support Vector Machines
Übersicht
I. Hauptkomponentenanalyse (PCA)II. Problemstellung: Überwachtes
LernenIII. k-Nearest NeighborsIV. Decision TreesV. Lineare KlassifizierungVI. ModellselektionVII. Support Vector Machines
I. Visualisierung von Daten
Daten sind meist hochdimensional Scatterplot kann nur 2 Variablen
darstellen Scatterplot Matrix kann beliegig
viele Dimensionen darstellen wird aber schnell unübersichtlich
I. Scatterplot
1,50 1,60 1,70 1,80 1,90
40
50
60
70
80
90
100
Gewicht(kg)
Größe(m)
I. Beispiel 3D
http://noppa5.pc.helsinki.fi/koe/3d3.html
I. Scatterplot Matrix: 3 Dimensionen
I. Scatterplot Matrix: 8 Dimensionen
I. Hauptkomponentenanalyse
Principal Component Analysis (PCA) Sucht (& findet) die
"interessanteste" 2-dimensionale Projektion
"Interessant": Richtung mit der höchsten Varianz
I. Varianz
1,50 1,60 1,70 1,80 1,90
40
50
60
70
80
90
100
Gewicht(kg)
Größe(m)
s1
s2
I. Beispiel PCA
-> Kamera
I. PCA: Theorie
wird aus Kovarianzmatrix berechnet (=> Problem mit Ausreißern)
Eigenvektoren/Eigenwerte werden gebildet
Eigenvektoren mit höchsten Eigenwerten sind Hauptkomponenten
Neue Achsen haben keinen semantischen Sinn mehr
I. Beispiel Hauptkomponenten
1,50 1,60 1,70 1,80 1,90
40
50
60
70
80
90
100
Gewicht(kg)
Größe(m)
I. Beispiel Hauptkomponenten
1,50 1,60 1,70 1,80 1,90
40
50
60
70
80
90
100
Gewicht(kg)
Größe(m)
Übersicht
I. Hauptkomponentenanalyse (PCA)II. Problemstellung: Überwachtes
LernenIII. k-Nearest NeighborsIV. Decision TreesV. Lineare KlassifizierungVI. ModellselektionVII. Support Vector Machines
II. Problemstellunggender age smoker eye
color
male 19 yes green
female 44 yes gray
male 49 yes blue
male 12 no brown
female 37 no brown
female 60 no brown
male 44 no blue
female 27 yes brown
female 51 yes green
female 81 yes gray
male 22 yes brown
male 29 no blue
lung cancer
no
yes
yes
no
no
yes
no
no
yes
no
no
no
male 77 yes gray
male 19 yes green
female 44 no gray
?
?
?
II. Problemstellunggender age smoker eye
color
male 19 yes green
female 44 yes gray
male 49 yes blue
male 12 no brown
female 37 no brown
female 60 no brown
male 44 no blue
female 27 yes brown
female 51 yes green
female 81 yes gray
male 22 yes brown
male 29 no blue
lung cancer
no
yes
yes
no
no
yes
no
no
yes
no
no
no
male 77 yes gray
male 19 yes green
female 44 no gray
?
?
?
Training Modell
II. Problemstellunggender age smoker eye
color
male 19 yes green
female 44 yes gray
male 49 yes blue
male 12 no brown
female 37 no brown
female 60 no brown
male 44 no blue
female 27 yes brown
female 51 yes green
female 81 yes gray
male 22 yes brown
male 29 no blue
lung cancer
no
yes
yes
no
no
yes
no
no
yes
no
no
no
male 77 yes gray
male 19 yes green
female 44 no gray
yes
no
no
Training Modell
Vorhersage
II. Begriffsdefinition
bei ML muss ein kategorisches Attribut vorhergesagt werden (kontinuierlich = Regression)
Synonyme: Überwachtes Lernen (Supervised
Learning) Klassifikation Machine Learning (ML) (Prediction)
II. Beispiel
1,50 1,60 1,70 1,80 1,90
40
50
60
70
80
90
100
Gewicht(kg)
Größe(m)
Übersicht
I. Hauptkomponentenanalyse (PCA)II. Problemstellung: Überwachtes
LernenIII. k-Nearest NeighborsIV. Decision TreesV. Lineare KlassifizierungVI. ModellselektionVII. Support Vector Machines
III. k-Nearest Neighbors (1)
Einfaches Lernverfahren, bei dem kein Modell gebildet wird
Die Trainingsdaten werden zum Klassifizieren verwendet (lazy learning)
Hyperparameter: k ist die Anzahl der nächsten Nachbaren, die betrachtet werden um die Klasse zu ermitteln
III. k-Nearest Neighbors (2)
wenn es nur 2 Klassen gibt sollte k ungerade sein
wird bei einer hohen Anzahl an Samples ineffizient
ist stark von der Skalierung abhängig
III. Beispiel kNN
III. Beispiel kNN
?
III. Beispiel kNN: k = 1
III. Beispiel kNN: k = 3
III. Beispiel kNN: k = 5
Übersicht
I. Hauptkomponentenanalyse (PCA)II. Problemstellung: Überwachtes
LernenIII. k-Nearest NeighborsIV. Decision TreesV. Lineare KlassifizierungVI. ModellselektionVII. Support Vector Machines
IV. Binäre Decision Trees
Bauen auf Informationstheorie auf (Shannon)
Sind ein rekursiver Algorithmus bei dem der Eingaberaum bei jedem Schritt in 2 Teile gespalten wird
Klassifizierung: Baum wird von der Wurzel an abgearbeitet bis ein Blatt erreicht wird
IV. Decision Trees: Beispiel
x < 12.3
y < 4.6 y < 3.9
blue x < 11.7 x < 13.1
red blue y < 1.7
red
red
red blue
IV. Informationstheorie, Entropie
Von Claude Shannon Anwendungen u.a. in
Datenkompression Mißt Informationsgehalt und
Redundanz Informationsgehalt wird in Bits
gemessen
IV. Was ist „Entropie“?
In ML ist Entropie ein Maß für die Unreinheit eines Datensets
Hohe Entropie: schlecht für Klassifizierung muß reduziert werden
Formel für Entropie H von Datensatz X:
∑=
−=n
iii xpxpXH
12 )(log)( )(
IV. Berechnung von H(X)
67.012
8)(
33.012
4)(
blue
red
==
==
xp
xp
∑=
−=n
iii xpxpXH
12 )(log)( )(
67.0log67.033.0log33.0 )( 22 ×−×−=XH
92.0
39.053.0
)0.59()67.0()1.59()33.0(
=+=
−×−+−×−=
IV. H(X): Fallbeispiele
0
0.88
0.88
1
H(X)
0.70.3II
0.30.7III
10IV
0.50.5I
p(xblue)p(xred)
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
p(xred)
H(X) ∑
=
−=n
iii xpxpXH
12 )(log)( )(
IV. H(X): Relative und absolute Häufigkeiten
Nur relative Häufigkeiten sind relevant!
red blue
1 8 4
2 18 9vs.
=> H(X1) = H(X2)
Information Gain: Untergruppen, die die Entropie am stärksten verringern
IV. Information Gain
)()()()()(),( BBAABA XHxpXHxpXHXXIG −−=
H(X) = 1
Gegeben: Datenset und 3 verschiedene Möglichkeiten zur Unterteilung, wie entscheidet man am besten?
A (green) B (yellow)
Points 6 4
p(X.) 0.6 0.4
p(xred) 0.33 0.75
p(xblue) 0.67 0.25
H(X.) 0.92 0.81
IG 0.12
A (green) B (yellow)
Points 9 1
p(X.) 0.9 0.1
p(xred) 0.44 1
p(xblue) 0.56 0
H(X.) 0.99 0
IG 0.11
A (green) B (yellow)
Points 5 5
p(X.) 0.5 0.5
p(xred) 0.2 0.8
p(xblue) 0.8 0.2
H(X.) 0.72 0.72
IG 0.28
IV. Informatin Gain (Eigenschaften)
IG ist höchstens so groß wie die Entropie vor der Teilung
IG ist der Wert um den Entropie durch Teilung verringert werden kann
IG ist mindestens 0 (falls die Entropie nicht reduziert werden kann)
0 <= IG <= H(X)
IV. Decision Trees Algorithmus
Datenset: Kategorische oder quantitative Variable
Für jede Dimension, für jeden möglichen Split wird IG berechnet Kategorisch: Eine gegen den Rest Quantitativ: Sortieren, dann zwischen
allen möglichen Werten trennen Rekursion bis nicht mehr geteilt
werden kann
IV. Decision Trees: Quantitative Varible
0.060.13
0.010.05
0.110.29
0.430.28
0.17
0.090.26
0.16
0.07
0.000.010.030.08
0.03
0.000.000.010.13
0.06
original H: 0.99
x < 12.3
blue red
x < 12.3
y < 4.6 y < 3.9
blue blue red red
x < 12.3
y < 4.6 y < 3.9
blue x < 11.7 x < 13.1
red blue ?
red
red
IV. Decision Trees: Beispiel
x < 12.3
y < 4.6 y < 3.9
blue x < 11.7 x < 13.1
red blue y < 1.7
red
red
red blue
IV. Decision Trees: Klassifikation
x < 12.3
y < 4.6 y < 3.9
blue x < 11.7 x < 13.1
red blue y < 1.7
red
red
red blue
IV. Decision Trees: Klassifikation
x < 12.3
y < 4.6 y < 3.9
blue x < 11.7 x < 13.1
red blue y < 1.7
red
red
red blue
IV. Decision Trees: Klassifikation
x < 12.3
y < 4.6 y < 3.9
blue x < 11.7 x < 13.1
red blue y < 1.7
red
red
red blue
IV. Decision Trees: Mehr als 2 Klassen
∑=
−=n
iii xpxpXH
12 )(log)( )(
x < 12.3
y < 4.6 y < 3.9
blue x < 11.7 x < 13.1
orange blue y < 1.7
red
orange
red blue
∑=
−=m
jjjm XHxpXHXXIG
11 )()()(),...,(
IV. Decision Trees: Nicht-binäre Bäume
drive-wheels?
fwd 4wdrwd
… … …
∑=
−=m
jjjm XHxpXHXXIG
11 )()()(),...,(
∑=
−=n
iii xpxpXH
12 )(log)( )(
IV. Decision Trees: Overfitting
Vollständige Decision Trees sind meistens zu komplex
IV. Decision Trees: Trainingsende
Mögliche Kriterien zur Unterbrechung der Rekursion: Anzahl der Samples ist gering (unter
einem Schwellwert) Entropie ist gering IG ist gering statistische Tests (Chi-Quadrat) etc.
Schwellwerte sind Hyperparameter
IV. Decision Trees: Pruning
"Pruning" bedeutet, daß man den Baum umformt oder Äste wegschneidet
Trainings-Abbruch-Kriterien werden manchmal als "Pre-pruning" bezeichnet
Redundante Knoten werden entfernt, manchmal wird Baum umgeformt
x < 12.3
blue red
x < 12.3
y < 4.6 y < 3.9
blue blue red red
x < 12.3
y < 4.6 y < 3.9
blue x < 11.7 x < 13.1
red blue ?
red
red
IV. Beispiel: Pruning
x < 12.3
y < 4.6 y < 3.9
blue x < 11.7 x < 13.1
red blue y < 1.7
red
red
red blue
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
IV. Decision Trees: Zuverlässigkeit
Übersicht
I. Hauptkomponentenanalyse (PCA)II. Problemstellung: Überwachtes
LernenIII. k-Nearest NeighborsIV. Decision TreesV. Lineare KlassifizierungVI. ModellselektionVII. Support Vector Machines
V. Lineare Klassifikatoren (1)
Eine Trennebene, die den Raum in 2 Hälften teilt, klassifiziert die Samples
Modell besteht nur aus Ebenengleichung Normalvektor (gerichtet) Bezugspunkt
V. Lineare Klassifikatoren (2)
"Hyperebene": Dimension des Vektorraumes – 1 in 2D: Linie in 3D: Ebene in 4D: Raum
Verschiedene Verfahren: Perzeptron (Rosenblatt) Moore-Penrose-Inverse Largest Margin Classifier (->SVM)
V. Perzeptron Algorithmus
Iteratives Verfahren: Hyperebene wird zufällig initialisiert Datenpunkte werden in zufälliger
Reihenfolge iteriert wenn Punkt auf richtiger Seite =>
keine Anpassung wenn Punkt auf falscher Seite =>
Änderung der Hyperebene Wiederholen bis Abbruchskriterium
erreicht
V. Beispiel: Perzeptron
V. Beispiel: Perzeptron
V. Beispiel: Perzeptron
V. Beispiel: Perzeptron
V. Beispiel: Perzeptron
Übersicht
I. Hauptkomponentenanalyse (PCA)II. Problemstellung: Überwachtes
LernenIII. k-Nearest NeighborsIV. Decision TreesV. Lineare KlassifizierungVI. ModellselektionVII. Support Vector Machines
VI. Modellselektion
Allgemeines ML Framework zur Schätzung der Hyperparameter
(Tuning) zur Auswahl des besten Modells
(lokale Minima vermeiden)
VI. Warum ist Generalisierung wichtig?
140 150 160 170 180 190 200
VI. Warum ist Generalisierung wichtig?
150 160 170 180 190 200
140 150 160 170 180 190 200
VI. Warum ist Generalisierung wichtig?
150 160 170 180 190 200
VI. Warum ist Generalisierung wichtig?
150 160 170 180 190 200
f m f m
140 150 160 170 180 190 200
VI. Warum ist Generalisierung wichtig?
150 160 170 180 190 200
f m f m
140 150 160 170 180 190 200
VI. Bayes optimaler Klassifikator
150 160 170 180 190 200
VI. Training Set, Test Set
Lösung: Datenset in Training- und Testset
aufspalten ~80% Training, 20% Test
Verschiedene Modelle trainieren Testset klassifizieren das Modell mit dem geringsten
Testset fehler wird gewählt
VI. Komplexität vs. Generalisierung
Fehler
Modellkomplexität
Testset
Trainingset
Beste Wahl
VI. Schätzung des Generalisierungsfehlers
Testset wird zur Modellselektion und zur Einstellung der Hyperparameter verwendet
deshalb ist der Testset-Fehler kein gutes Maß für den Generalisierungsfehler
Generalisierungsfehler ist der zu erwartende Fehler den der Klassifikator auf einem Datenset machen wird (nach Tuning)
VI. Training-Test-Validation
Teilund des Datensets (ähnl. Training-Test): z.B. 60% Training 20% Test 20% Validation
Klassifikator auf Trainingset trainieren Bestes Modell anhand von Testset-
Performance aussuchen Generalisierungsfehler auf Validationset
abschätzen
VI. Crossvalidation
Datenset wird in 10 gleichgroße Gruppen unterteilt Das heißt dann 10-fold crossvalidation
10 Mal wiederholen (durchrotieren): 9 Teile werden als Training/Testset verwendet die Performance wird am letzten Set gemessen
die Schätzung des Generalisierungsfehlers ist dann der Mittelwert dieser 10 Durchgänge
Übersicht
I. Hauptkomponentenanalyse (PCA)II. Problemstellung: Überwachtes
LernenIII. k-Nearest NeighborsIV. Decision TreesV. Lineare KlassifizierungVI. ModellselektionVII. Support Vector Machines
VII. Support Vector Machines
von V. Vapnik eingeführt ziemlich komplizierter
mathematischer Hintergrund bestehen aus 2 Komponenten:
Optimierung (Maximierung des Abstandes)
Kernel (Transformation des Datenraumes)
VII. Lineare Separierung
VII. Lineare Separierung
VII. Lineare Separierung
VII. Lineare Separierung
VII. Largest Margin
VII. Largest Margin
Optimale Hyperebene kann als Optimierungsproblem dargestellt werden
Durch quadratische Programmierung gelöst
Soft margin: Es müssen nicht 100% sauber getrennt werden, aber jeder falsch klassifizierte Punkt wird bestraft
VII. Nicht linear trennbare Daten
VII. Nicht linear trennbare Daten
VII. Nicht linear trennbare Daten
VII. Nicht linear trennbare Daten
-4 -3 -2 -1 0 1 2 3 4-4
-3
-2
-1
0
1
2
3
x
y
VII. Zusätzliche Koordinate z=x2
-4 -3 -2 -1 0 1 2 3 4
-4
-2
0
2
4
0
5
10
15
x
y
z=x2
VII. Zusätzliche Koordinate z=x2
0 2 4 6 8 10 12-4
-3
-2
-1
0
1
2
3
z=x2
y
VII. Kernel
Projektion des Datenraumes auf höherdimensionalen Featureraum (feature space) z.B. R2->R5
Daten sind dann möglicherweise linear separierbar (in hochdimensionalem Raum)
Projektion passiert durch Multiplikation mit Kernelmatrix
die Kernelmatrix legt die Art der Projektion fest (d.h. wie sich die neuen Koordinaten aus den alten berechnen)
VII. Gängige Kernels
Quadratischer Kernel Radial Basis Kernel (RBF) Polynomieller Kernel (von
beliebigem Grad) Linearer Kernel (=kein Kernel)
VII. Kernel Trick
Alle ML Algorithmen könnten mit dieser Datenprojektion durch einen Kernel arbeiten, warum also SVMs?
Höherdimensionale Daten sind üblicherweise ein Problem für alle Algorithmen (Komplexität, Fluch der Dimensionen)
"Kernel Trick": Das Optimierungsproblem kann so umgeformt werden, dass nur die Distanzen im hochdimensionalen Raum benötigt werden und das kann sehr effizient berechnet werden
VII. Eigenschaften von SVMs
Gute Ergebnisse Lineare Kernels: Gut bei dünn
besetzten, hochdimensionalen Daten
Gut erforscht => solider theoretischer Hintergrund (siehe VC-Dimension etc.)
Prüfungsfragen
Alle der folgenden Begriffe bezeichnen gültige Datenskalen mit Ausnahme von: Nominalskala Intervallskala Binomialskala Ordinalskala
Prüfungsfragen
Welche der folgenden Aussagen über Datenaufbereitung für Data Mining ist richtig?
Verhältnisskalierte Merkmale müssen mit 1-zu-N Kodierung aufbereitet werden, um von den meisten Data Mining Algorithmen verarbeitet werden zu können.
Die Standardabweichung ist ein skalenunabhängiger Wert, der Aussagen über die Streuung zulässt, ohne dass die Einheit des gemessenen Mermals eine Rolle spielt.
Ausreißer führen zu Problemen mit der Verwendbarkeit der Standardabweichung und der Kovarianzmatrix.
Die zero-mean-unit-variance Normalisierung wird durch Division der ursprünglichen Wertes durch den Mittelwert und Subtraktion der Standardabweichung erreicht.
Prüfungsfragen
Welche der folgenden Aussagen über Verteilungen ist falsch? In typischen Data Mining Problemen ist die
Dichtefunktion der analysierten Daten entweder bekannt oder zumindest direkt beobachtbar.
Der Graph der Dichtefunktion einer Normalverteilung wird auch als Gauß'sche Glockenkurve bezeichnet.
Die Standardnormalverteilung ist eine Normalverteilung mit Mittelpunkt 0 und Varianz 1.
Eine multivariate Normalverteilung wird durch den Mittelpunktsvektor und die Kovarianzmatrix vollständig beschrieben.
Ende!