T - DBS

DATABASE
SYSTEMS
GROUP
3.5 EntscheidungsbaumKlassifikatoren
Motivation
Autotyp
ID
1
2
3
4
5
Alter
23
17
43
68
32
Autotyp
Familie
Sport
Sport
Familie
LKW
Risiko
hoch
hoch
hoch
niedrig
niedrig
= LKW
≠ LKW
Risikoklasse = niedrig
Alter
> 60
Risikoklasse = niedrig
≤ 60
Risikoklasse = hoch
finden explizites Wissen
Entscheidungsbäume sind für die meisten Benutzer verständlich
58
Grundbegriffe
DATABASE
SYSTEMS
GROUP
• Ein Entscheidungsbaum ist ein Baum mit folgenden Eigenschaften:
•
•
•
ein innerer Knoten repräsentiert ein Attribut,
eine Kante repräsentiert einen Test auf dem Attribut des Vaterknotens,
ein Blatt repräsentiert
p
eine der Klassen.
• Konstruktion eines Entscheidungsbaums
•
anhand der Trainingsmenge
•
Top-Down
Autotyp
= LKW
≠ LKW
Risikoklasse = niedrig
Alter
> 60
• Anwendung eines Entscheidungsbaums
Risikoklasse = niedrig
≤ 60
Risikoklasse = hoch
Durchlauf des Entscheidungsbaum von der Wurzel zu einem der Blätter
⇒ eindeutiger Pfad
Zuordnung des Objekts zur Klasse des erreichten Blatts
59
DATABASE
SYSTEMS
GROUP
Konstruktion eines
g
Entscheidungsbaums
Basis-Algorithmus
• Anfangs gehören alle Trainingsdatensätze zur Wurzel.
• Das nächste Attribut wird ausgewählt (Splitstrategie).
• Die Trainingsdatensätze werden unter Nutzung des Splitattributs
partitioniert.
g
• Das Verfahren wird rekursiv für die Partitionen fortgesetzt.
⇒ lokal optimierender Algorithmus
Abbruchbedingungen
• keine weiteren Splitattribute
• alle Trainingsdatensätze
g
eines Knotens gehören
g
zur selben Klasse
60
Entscheidungsbaum-Klassifikatoren
DATABASE
SYSTEMS
GROUP
Beispiel
Tag
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Aussicht
sonnig
sonnig
bedeckt
regnerisch
g
regnerisch
regnerisch
bedeckt
sonnig
sonnig
regnerisch
sonnig
b d kt
bedeckt
bedeckt
regnerisch
Temperatur
heiß
heiß
heiß
mild
kühl
kühl
kühl
mild
kühl
mild
mild
mild
ild
heiß
mild
Feuchtigkeit
hoch
hoch
hoch
hoch
normal
normal
normal
hoch
normal
normal
normal
h h
hoch
normal
hoch
Wind
schwach
stark
schwach
schwach
schwach
stark
stark
schwach
schwach
schwach
stark
stark
t k
schwach
stark
Tennispielen
nein
nein
ja
ja
jja
nein
ja
nein
ja
ja
ja
j
ja
ja
nein
I t heute
Ist
h t ein
i Tag
T zum Tennisspielen?
T
i i l ?
61
DATABASE
SYSTEMS
GROUP
Entscheidungsbaum-Klassifikatoren
Beispiel
Aussicht
sonnig
Feuchtigkeit
hoch
„nein“
regnerisch
bedeckt
Wind
„ja“
normal
„ja“
stark
„nein“
schwach
„ja“
62
DATABASE
SYSTEMS
GROUP
Splitstrategien
Typen von Splits
• Kategorische Attribute
Splitbedingungen der Form „Attribut = a“ or „Attribut ∈ set“
viele mögliche Teilmengen
Attribut
= a1
= a2
= a3
Attribut
∈ s1
∈ s2
• Numerische Attribute
Splitbedingungen der Form „Attribut
Attribut < a“
a
viele mögliche Splitpunkte
<a
Attribut
≥a
63
DATABASE
SYSTEMS
GROUP
Numerische Splitgrenzen
Wo sollen diskrete Attribute gesplittet werden?
=> An
A d
den S
Stellen,
ll
di
die di
die Qualität
Q li ä maximieren.
i i
Idee: Ordnen der numerischen Attributwerte
Wert
0.9
0.8
0.65
0.5
0.45 0.3
0.15
0.01
Klasse
A
A
B
B
B
A
A
A
Potentielle Splitkandidaten
Teste die Kombination
Kombination, die den höchsten Information Gain erzielen.
erzielen
Schnellere Methode:
• Bilde Gauß-Kurve über alle Klassen
• Wähle Schnittpunkte der Gauß-Kurven
als
l Kandidaten.
K did t
Potentielle
Splitkandidaten
64
DATABASE
SYSTEMS
GROUP
Splitstrategien
Qualitätsmaße für Splits
Gegeben
• eine Menge
g T von Trainingsobjekten
g
j
• eine disjunkte, vollständige Partitionierung T1, T2, . . . , Tm von T
• pi die relative Häufigkeit der Klasse ci in T
Gesucht
• ein
i M
Maß
ßd
der Unreinheit
U i h it einer
i
M
Menge S von Trainingsobjekten
T i i
bj kt in
i B
Bezug
auf die Klassenzugehörigkeit
• ein Split
p von T in T1, T2, . . . , Tm , der dieses Maß der Unreinheit
minimiert
⇒ Informationsgewinn, Gini-Index
65
DATABASE
SYSTEMS
GROUP
Splitstrategien
Informationsgewinn
Entropie: minimale Anzahl von Bits zum Codieren der Nachricht,
mit der man die Klasse eines zufälligen Trainingsobjekts mitteilen möchte
möchte.
Die Entropie für eine Menge T von Trainingsobjekten ist definiert als
k
entropie
i ( T ) = − ∑ pi ⋅ llog pi
i =1
entropie(T) = 0, falls pi = 1 für ein i
entropie(T)
t i (T) = 1 für
fü k = 2 Klassen
Kl
mit
it pi = 1/2
Das Attribut A habe die Partitionierung T1, T2, . . . , Tm erzeugt.
Der
A in
auff T ist
als
D Informationsgewinn
I f
i
i des
d Attributs
A ib
i Bezug
B
i definiert
d fi i
l
| Ti |
⋅ entropie(Ti )
i =1 | T |
m
Informationsgewinn(T , A) = entropie(T ) − ∑
66
DATABASE
SYSTEMS
GROUP
Splitstrategien
Gini-Index
Gini-Index für eine Menge T von Trainingsobjekten
k
gini(T ) = 1 − ∑ pj 2
j =1
– kl
kleiner
i
Gi
Gini-Index
i I d ⇔ geringe
i
U i h i
Unreinheit,
– großer Gini-Index ⇔ hohe Unreinheit
Das Attribut
D
A ib A habe
h b die
di Partitionierung
P ii i
T1, T2, . . . , Tm erzeugt.
Gini-Index des Attributs A in Bezug auf T ist definiert als
|Ti |
giniA (T) = ∑ ⋅ gini(Ti )
i =1 | T|
m
67
DATABASE
SYSTEMS
GROUP
Splitstrategien
Beispiel
p
9 „ja“ 5 „nein“
Entropie = 0,940
9 „ja“ 5 „nein“
Feuchtigkeit
g
hoch
3 „ja“
„ja 4 „nein
„nein“
Entropie = 0,985
Entropie = 0,940
Wind
normal
6 „ja“
„ja 1 „nein
„nein“
Entropie = 0,592
schwach
stark
„ja“ 2 „nein“
„
6 „j
3 „ja“
j 3 „nein“
Entropie = 0,811
Entropie = 1,0
7
7
⋅ 0,985 − ⋅ 0,592 = 0,151
14
14
8
6
Informationsgewinn(T , Wind ) = 0,94 − ⋅ 0,811 − ⋅1,0 = 0,048
14
14
Informationsgewinn(T , Feuchtigkeit ) = 0,94 −
⇒ Feuchtigkeit liefert den höheren Informationsgewinn
68
DATABASE
SYSTEMS
GROUP
Bias
69
DATABASE
SYSTEMS
GROUP
Overfitting
Einführung
Overfitting bei der Konstruktion eines Entscheidungsbaums, wenn es zwei
Entscheidungsbäume E und E’ gibt mit
Kllassifikatioonsgenauigkeit
– E hat auf der Trainingsmenge eine kleinere Fehlerrate als E
E’,
– E’ hat auf der Grundgesamtheit der Daten
eine kleinere Fehlerrate als E.
auf Trainingsdaten
auf Testdaten
Baumgröße
70
DATABASE
SYSTEMS
GROUP
Overfitting
Trainingsdaten
Name
Body Temp
Gives Birth
Four-legged Hibernates
Mammal
porcupine
warm-blooded
yes
yes
yes
yes
cat
warm-blooded
yes
yes
no
yes
bat
warm-blooded
yes
no
yes
no*
whale
warm-blooded
yes
no
no
no*
salamander
cold-blooded
no
yes
yes
no
komodo dragon cold-blooded
no
yes
no
no
python
cold-blooded
no
no
yes
no
salmon
cold-blooded
no
no
no
no
eagle
warm-blooded
no
no
no
no
guppy
cold-blooded
yes
no
no
no
*Fehlerhafte Daten
71
DATABASE
SYSTEMS
GROUP
Overfitting
Testdaten
Name
Body Temp
Gives Birth
Four-legged Hibernates
Mammal
human
warm-blooded
yes
no
no
yes
pigeon
warm-blooded
no
no
no
no
elephant
warm-blooded
yes
yes
no
yes
leopard shark
cold-blooded
yes
no
no
no
turtle
cold-blooded
no
yes
no
no
penguin
warm-blooded
no
no
no
no
eel
cold-blooded
no
no
no
no
dolphin
warm-blooded
yes
no
no
yes
spiny anteater
warm-blooded
no
yes
yes
yes
gila monster
cold-blooded
no
yes
yes
no
72
DATABASE
SYSTEMS
GROUP
Overfitting
Trainingserror: 0%
T
Testerror:
30%
M1:
• Fehlklassifikation
von human und
d l hi aufgrund
dolphin
f
d
von fehlerhaften
Trainingsdaten
• Spiny anteater:
g
ungewöhnlicher
Fall
M2:
ungewöhnlicher
Trainingserror: 20%
Fall kann nicht
T
Testerror:
10%
vermieden werden
73
DATABASE
SYSTEMS
GROUP
Overfitting
Name
Body Temp
Gives Birth
Four-legged Hibernates
Mammal
salamander
cold-blooded
no
yes
yes
no
poorwill
warm-blooded
no
no
yes
no
platypus
warm-blooded
no
yes
yes
yes
eagle
warm-blooded
no
no
no
no
guppy
cold-blooded
yes
no
no
no
Problem:
Mangel an repräsentativen Daten
74
DATABASE
SYSTEMS
GROUP
Overfitting
Ansätze zum Vermeiden von Overfitting
• Entfernen von fehlerhaften Trainingsdaten
i b
insbesondere
d
widersprüchliche
id
ü hli h Trainingsdaten
T i i
d
• Wahl einer geeigneten Größe der Trainingsmenge
nicht zu klein, nicht zu groß
• Wahl einer geeigneten Größe des minimum support
minimum support:
Anzahl der Datensätze, die mindestens zu einem Blattknoten
des Baums gehören müssen
minimum support >> 1
75
DATABASE
SYSTEMS
GROUP
Overfitting
Ansätze zum Vermeiden von Overfitting
• Wahl einer geeigneten Größe der minimum confidence
minimum confidence: Anteil, den die Mehrheitsklasse eines
Blattknotens mindestens besitzen muß.
minimum confidence << 100%
Blätter können auch fehlerhafte Datensätze oder Rauschen
„absorbieren“
• nachträgliches Pruning des Entscheidungsbaums
Abschneiden der überspezialisierten Äste
kleinere Bäume sind weniger anfällig für Overfitting (Occam
(Occam‘ss Razor)
76
DATABASE
SYSTEMS
GROUP
Pruning von Entscheidungsbäumen
Fehlerreduktions-Pruning [Mitchell 1997]
• Aufteilung der klassifizierten Daten in Trainingsmenge und Testmenge
• Konstruktion eines Entscheidungsbaums E für die Trainingsmenge
• Pruning von E mit Hilfe der Testmenge T
- bestimme denjenigen Teilbaum von E, dessen Abschneiden den
Klassifikationsfehler auf T am stärksten reduziert
- entferne diesen Teilbaum
- fertig, falls kein solcher Teilbaum mehr existiert
nur anwendbar, wenn genügend viele klassifizierte Daten
77
DATABASE
SYSTEMS
GROUP
Entscheidungsbaum-Klassifikatoren
Diskussion
+ Interpretation des gefundenen Baumes relativ einfach
+ Implizite
p
Gewichtung
g der Attribute
+ Leistungsfähiger Klassifikator, häufig in der Praxis verwendet
+ Effiziente Auswertung des gefundenen Modells
- Finden eines optimalen Entscheidungsbaums ist exponentiell
- Heuristische Methoden können nur lokales Optimum finden
- Anfällig für Overfitting (besondere Methoden zur
Vermeidung von Overfitting für Entscheidungsbäume)
78
DATABASE
SYSTEMS
GROUP
3.6 Neuronale Netze
Grundlagen [Bigus 1996], [Bishop 1995]
• Paradigma
P di
fü
für ein
i M
Maschinenhi
und
d Berechnungsmodell
B
h
d ll
• Funktionsweise ähnlich der von biologischen Gehirnen
Neuronales Netz: Menge von Neuronen, über Kanten
miteinander
it i
d verbunden
b d
Neuron:
entspricht biologischem Neuron Aktivierung
durch Input-Signale an den Synapsen
• Menschliches Gehirn: 1011 Neuronen,
Neuronen jedes verbunden mit ~10
104
anderen, schnellste Aktionszeit 10-3 Sek. (Computer: 10-10) – aber
komplexe Entscheidungen sehr schnell (visuelle Erkennung der
eigenen Mutter: 10-11 Sek.
Sek ≈ 100 Schritte)
• Erzeugung eines Output-Signals, das zu anderen Neuronen
weitergeleitet wird.
• Organisation
O
i ti eines
i
neuronalen
l N
Netzes
t
Input-Schicht, verborgene Schichten, Output-Schicht
Knoten einer Schicht mit allen Knoten der vorhergehenden Schicht
verbunden
79
DATABASE
SYSTEMS
GROUP
Grundlagen
Kanten besitzen Gewichte
Funktion eines neuronalen Netzes
Vorhergesagte
Klasse
Output-Vektor y
Output-Schicht
verborgene
g
Schicht
wij
Input-Schicht
wij
Input-Vektor x
80
DATABASE
SYSTEMS
GROUP
Neuronen
allgemeines Neuron (auch: Perzeptron)
a: Aktivierungswert x1
x2
n
a = ∑ wi ⋅ xi
w1
×
×
. . w. 2
i =1
xn
Threshold Logic Unit
x1
(TLU)
x2
y=
1
1 + e −a
wn
w1
×
×
y
. . w. 2
xn
×
Σ
a
×
Σ
a
θ
a
⎧1, wenn a ≥ θ
y=⎨
⎩ 0, sonst
wn
81
Neuronen
DATABASE
SYSTEMS
GROUP
Beispiel: Modellierung einer booleschen Funktion
x1
x2
x3
y
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
0
0
1
0
0
1
0
0
0
1
1
1
0
0
0
0
x1
x2
xn
×
×
×
0.3
y
03
0.3
Σ
a
θ
a
⎧1, wenn a ≥ θ
y=⎨
0 sonst
⎩ 0,
0.3
θ=0.4
82
DATABASE
SYSTEMS
GROUP
•
Neuronen
Klassifikation mit Hilfe einer TLU
x2
n
• repräsentiert
ä
i
eine
i (Hyper-)Ebene
(H
)Eb
• links von der Ebene: Klasse 0
• rechts
ht von der
d Ebene:
Eb
Kl
Klasse
1
∑w ⋅x
i =1
i
i
=θ
1
0
1
0
•
1
0
0
1
0
1
1 1
1
0
0
1
0
Trainieren einer TLU
x1
• Lernen der „richtigen“ Gewichte zur Unterscheidung der zwei Klassen
Iterative Anpassung der Gewichte wij
• Rotation der durch w und θ gegebene Hyperebene um einen kleinen Betrag
in Richtung v, wenn v noch nicht auf der richtigen Seite der Ebene liegt
83
DATABASE
SYSTEMS
GROUP
XOR-Problem
nicht linear separierbares Problem
84
DATABASE
SYSTEMS
GROUP
Kombination mehrerer Neuronen
zwei Klassen, die nicht linear separierbar sind:
⇒ mehrere innere Knoten (hidden layer) und ein Output-Knoten (zweiKlassen-Problem, sonst mehr)
Varianten: feed-forward vs. recurrent (auch Verbindungen auf derselben
Ebene oder zu vorherigen Ebenen möglich)
85
DATABASE
SYSTEMS
GROUP
Kombination mehrerer Neuronen
XOR
86
DATABASE
SYSTEMS
GROUP
Kombination mehrerer Neuronen
Beispiel
1
0
A
A
A
A
A
A
B
B
y
A
A
A
A
A
1
B
A
h1 = 0 ∧ h2 = 0 : y = 0 ( Klasse B )
A
B
A
B
B
0
B
A
A
h1
h2
andernfalls : y = 1 ( Klasse A)
B
87
DATABASE
SYSTEMS
GROUP
Lernalgorithmus für komplexe
Neuronale Netze
Bei Abweichung von vorhergesagter und tatsächlicher Klasse:
Anpassung der Gewichte mehrerer Knoten
Frage
g
In welchem Maße sind die verschiedenen Knoten
an dem Fehler beteiligt?
Anpassung der Gewichte
• durch Gradientenverfahren, das den Gesamtfehler minimiert
• Gesamtfehler: Summe der (quadratischen) Abweichungen des
tatsächlichen Outputs y vom gewünschten Output t für die Menge der
I
Inputvektoren.
k
(Least
(L
S
Squares
O i i
Optimierung)
)
• Voraussetzung: Output y stetige Funktion der Aktivierung a
88
DATABASE
SYSTEMS
GROUP
Algorithmus Backpropagation
für j
jedes Paar(v,t)
( , ) // v = Input,t
p , = g
gewünschter Output
p
„forward pass”:
Bestimme den tatsächlichen Output y für Eingabe v;
„backpropagation”:
Bestimme den Fehler (t - y) der Output-Einheiten
und passe die Gewichte der Output-Einheiten
Output Einheiten in die
Richtung an, die den Fehler minimiert;
Solange der Input-Layer nicht erreicht ist:
Propagiere den Fehler auf die nächste Schicht und
passe auch dort die Gewichte der Einheiten in
f hl
fehlerminimierender
i i i
d
W i
Weise
an;
89
Design der Netztopologie
DATABASE
SYSTEMS
GROUP
Bestimmung
g von
• Anzahl der Input-Knoten
g Anzahl der Knoten
• Anzahl der inneren Schichten und jjeweilige
• Anzahl der Output-Knoten
starker Einfluss auf die Klassifikationsgüte:
• zu wenige Knoten
⇒
niedrige
i d i Klassifikationsgüte
Kl ifik ti
üt
• zu viele Knoten
⇒ Overfitting
O fitti
90
DATABASE
SYSTEMS
GROUP
Bestimmung der Netztopologie
nach [SPSS Clementine 2000]
Statische Topologie
– Topologie wird a priori festgelegt
– eine verborgene Schicht reicht in vielen Anwendungen aus
Dynamische Topologie
– dynamisches Hinzufügen von Neuronen (und verborgenen Schichten)
solange Klassifikationsgüte signifikant verbessert wird
M lti l Topologien
Multiple
T
l i
– Trainieren mehrerer dynamischer Netze parallel
z.B.
B jje ein
i N
Netz mit
i 1
1, 2 und
d 3 verborgenen
b
Schichten
S hi h
91
DATABASE
SYSTEMS
GROUP
Bestimmung der Netztopologie
Pruning
•
Trainieren eines Netzes mit statischer Topologie
•
nachträgliches Entfernen der unwichtigsten Neuronen solange
Kl ifik i
Klassifikationsgüte
ü verbessert
b
wird
id
Schlussfolgerung
• statische Topologie: niedrige Klassifikationsgüte, aber relativ schnell.
• Pruning:
beste Klassifikationsgüte, aber sehr hoher
L f it f
Laufzeitaufwand
d zum Training.
T i i
92
DATABASE
SYSTEMS
GROUP
Diskussion
+ im Allgemeinen
g
sehr hohe Klassifikationsgüte
g
beliebig komplexe Entscheidungsflächen (möglichst einfache Topologie
auswählen, um Overfitting zu vermeiden)
+ redundante Features relativ problemlos,
problemlos Gewichte werden klein
+ Effizienz der Anwendung
-
schlechte Verständlichkeit
(lernt nur Gewichte, aber keine Klassenbeschreibung)
Ineffizienz des Lernens (sehr lange Trainingszeiten)
keine Integration von Hintergrundwissen
-
empfindlich gegen Fehler in den Trainingsdaten
-
mögliche Konvergenz in lokales Minimum
93

Download Report