Data Mining 2. Vorlesung

Data Mining2. Vorlesung

Georg Pölzlbauer15. Mai 2007

[email protected]

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. 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



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

?

?

?


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


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



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



Übersicht



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


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


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


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


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













Übersicht



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





Übersicht



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


150 160 170 180 190 200

140 150 160 170 180 190 200


150 160 170 180 190 200


150 160 170 180 190 200

f m f m

140 150 160 170 180 190 200


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



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. 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




-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!

Documents

Data Mining 2. Vorlesung