08 Entscheidungsbäume Flashcards
Für welche Problemstellungen eignen sich Decision Trees
- Instanzen lassen sich als Attribut-Wert Paar beschreiben
- Zielfunktion besitzt diskrete Ausgabewerte
- Disjunkte Hypothesen erforderlich
- Beispieldaten sind möglicherweise verrauscht
- Beispieldaten enthalten evtl. fehlende Attributwerte
Entropie
Maß der Homogenität der Trainingsdaten
Entropie(S) = -plog_2(p) - plog2(p)
Ziel ist es die Daten durch Festhalten eines Attributwertes v möglichst in die Klassen einzuteilen, dh. die Entropie maximal zu reduzieren
Wahl des nächsten Attributes
Idee: Ein gutes Attribut teilt die Beispiele idealerweise in Teilmengen auf, die alle positiv oder negativ sind
ID3 : Suche im Hypothesenraum
Es gibt typischerweise viele Entscheidungsbäume, die mit den Trainingsbeispielen konsistent sind
Hypothesenraum ist bei Bäumen vollständig, d.h. Zielfunktion ist enthalten
Suche der Hypothese: „Simple-to-Complex“ oder „Hill Climbing“ nach Informationsgewinn
Lokale Minima (wie bei allen Hill Climbing Algorithmen) möglich
ID3: Induktiver Bias
H ist bei ID3 die Potenzmenge der möglichen Instanzen X
Präferenz für kleine Bäume und für Bäume, deren Attribut nahe der Wurzel einen hohen Informationsgewinn besitzen
ID3-Bias ist eine Präferenz für bestimmte Hypothesen, aber keine Restriktion des Hypothesenraums H
Occam‘s Razor: Bevorzuge die einfachste Hypothese, die mit den Trainingsdaten übereinstimmt.
ID3: Overfitting
Jeder Zweig wächst solange, bis die Trainingsbeispiele perfekt klasssifiziert werden
=> kann zu Problemen führen, wenn
- die Daten verrauscht sind
- die Beispiele nicht repräsentativ sind
Eine Hypothese h overfittet die Daten D, wenn es eine alternative Hypothese h’ gibt, sodass:
- Fehler_T(h) < Fehler_T(h’) UND
- Fehler_D(h) > Fehler_D(h’)
Fehler_T(h) : Fehler der Hypothese h auf den Trainingsdaten
Fehler_D(h): Fehler der Hypothese h auf der gesamten Verteilung D der Daten
Vermeidung von Overfitting
Lösungen:
- frühzeitiges stoppen des baumwachstums
- nachträgliches Prunen des Baumes (in der praxis erfolgreicher)
Kriterium für die Bestimmung der optimalen Baumgröße:
- separate testdatenmengen
- statistischer test auf den trainingsdaten
- maß für die kodierungskomplexität der trainingsbeispiele und des entscheidungsbaums
Reduced Error Pruning
- Teile die Daten in Trainings- und Testdaten auf.
- Solange sich das Pruning nicht negativ auswirkt:
a. Evaluiere die Auswirkungen des Entfernens jedes Knotens (und seiner Nachfolgeknoten) auf die Klassifikationsgüte bzgl. der Testdaten.
b. Entferne den Knoten, dessen Entfernen die Klassifikationsrate bzgl. der Testdaten am meisten erhöht.
Resultat:
Liefert die kleinste Variante des akkuratesten Unterbaums
Problem:
Bei wenigen Daten erhöht das Aufteilen der Daten die Fehleranfälligkeit noch weiter
Vorgehen bei kontinuierlichen Attributwerten
Dynamische Definition eines neuen diskret-wertigen Attributs A_c: wahr, wenn A>c
Wahl des Schwwellwertes c:
- sortierung der Beispiele gemäß ihrer Werte
- optimaler schwellwert liegt in der Mitte zwischen zwei benachbarten Beispielen mit unterschiedlichen Klassenzugehörigkeiten
- bei mehreren möglichen c, wahl desjenigen mit dem höchsten Informationsgewinn
ID3: Window
Lernmethode für große Datenmengen
- wähle zufällige Untermenge der Trainingsdaten aus (“window”)
- bestimme Decision Tree mit diesen Beispielen
- klassifiziere alle übrigen beispiele mit gelerntem Decision tree
- falls nicht alle daten korrekt klassifiziert, füge einen zufällig gewählten teil der falsch klassifizierten zum fenster hinzu und erstelle neuen decision tree
C4.5: Rule Post-Pruning
- Erstelle Baum wie gewohnt aus den Trainingsdaten (overfitting erlaubt)
- konvertiere den Baum in äquivalente Menge von IF-Then Regeln. IF-Teil enthält alle Attributtests eines Pfads, THEN die Ausgabe/Klasse
- “Prune” die Regeln so lange sich ihre Vorhersagegenauigkeit nicht verschlechtert (durch Entfernen von Vorbedingungen)
- Sortiere alle Regeln nach ihrer Klassifikationsgüte und verwende sie in diesr Reihenfolge
C4.5 Abschätzung der Güte der Regeln
Pessimistische Abschätzung:
- Bestimmung der Regelgüte auf den Trainingsdaten
- Verwenden von statistischen Verfahren
Heuristik ist statistisch nicht ganz einwandfrei, führt in der Praxis jedoch dennoch zu guten Ergebnissen
Vorteile:
+ unterscheidung zwischen verschiedenen Kontexten, in denen ein Entscheidungskonten benutzt wird
(eine regel für jeden Pfad durch den baum)
+ keine unterscheidung zwischen Attributen näher an der Wurzel und solchen näher an den Blättern
–> vereinfacht das Prunen
+ Lesbarkeit für den Menschen
ID5R
Inkrementelles Verfahren
=> sukzessives Einbringen von Beispielen in den Aufbau des Entscheidungsbaumes
Ergebnis ist äquivalent zu einem von ID3 erzeugten Baum
ID5R Baum Update Algorithmus
- Gegeben: bestehender EB
- Gegeben: neue instanz I
- Wenn EB leer:
- dann gibt einen Antwortkonten mit der Klasse von I zurück
- Wenn EB ein Antwortknoten mit der gleichen Klasse wie I
- dann füge I zur Menge der Instanzen dieses Knotens hinzu
- Sonst: (die ersten beiden Bedingungen sind falsch.)
- Wenn EB Antwortknoten,
- Umwandlung in Entscheidungsknoten mit beliebigem Testattribut.
- Aktualisiere die Zähler des Entscheidungsknotens (für Testattribut und alle anderen Attribute)
- Wenn das Testattribut nicht optimal:
- Restrukturiere den Baum so, dass Attribut mit höchstem Informationsgewinn Testattribut wird.
- Wähle Testattribute mit höchstem Informationsgewinn rekursiv in den Unterbäumen.
- Aktualisiere rekursiv den gemäß des Attributwerts von I (neue Instanz) gewählten Unterbaum.
ID5R: Restrukturierung
- Wenn Attribut A_neu mit höchstem Informationsgewinn an der Wurzel:
- dann terminieren
- sonst:
- Ziehe A_neu rekursiv an die Wurzel jedes direkten Unterbaums. Falls erforderlich wandle jeden Antwortknoten in Entscheidungsknoten mit Testattribut um
- Transponiere den Baum so, dass A_neu an der Wurzel des neuen Baums und A_alt an der Wurzel jedes direkten Unterbaumes steht.
