Machine Learning
Decision Trees (2)
Beispiel (Wiederholung)
Beispiel (Baum)
Was passiert beim Hinzufügen eines neuen, falschen Beispiels D15?
D15 = Sunny, Hot, Normal, Strong, PlayTennis = No
Overfitting
• Problem: gültige Verallgemeinerungen können
zerstört werden durch :
– Einzelne fehlerhafte Trainingsdaten
– Ausreißer bei großen Datenmengen
• Konstruierter Entscheidungsbaum passt zwar
optimal auf die Trainingsmenge, aber schlechter
auf die Gesamtdistribution, als ein
möglicherweise kleinerer Baum, der die
Trainingsmenge schlechter apporximiert
Overfitting
• Def.
– Sei T Trainingsmenge, D Gesamtdistribution.
Overfitting einer Hypothese h  H liegt vor,
gdw
• errorT(h) < errorT(h‘) und
• errorD(h) > errorD(h‘)
Overfitting
Overfitting
• Strategien zur Vermeidung von Overfitting:
– Breche die Generierung weiterer Knoten an
bestimmter Stelle bei der Konstruktion ab
– Berechne vollständigen Baum und lösche
nachträglich Knoten (= „Pruning“)
• Notwendig: Validationsmenge (auch
Testmenge)
Overfitting
• Auswahlkriterien für den „besten“ Baum
– Beste Übereinstimmung mit der
Trainingsmenge
– Beste Übereinstimmung mit der
Validationsmenge
– „Minimal Description Length“ (MDL)
– Mass: Akkuratheit = (TP + TN) / (TP + TN +
FP + FN)
Baumbeschneidungsmethoden
• Löschen von Knoten zur FehlerReduktion:
– Teile Daten in Trainings- und
Validationsmenge
– Für jeden Knoten (top-down):
• Überprüfe die Akkuratheit auf der
Validationsmenge, wenn dieser Knoten (und evt.
alle darunter) gelöscht wird.
• Lösche den Knoten, wenn die Akkuratheit dadurch
vergrößert wird (das erfordert u.U. Reoranisation
des Baumes!)
Regelmodifikation
• Reduktion der Entscheidungsschritte
durch Modifikation der Regeln, die einem
Entscheidungsbaum entsprechen
Entscheidungsbaum als geordnete
Menge von Regeln
• Jeder Entscheidungsbaum lässt sich in
eine äquivalente Menge von Regeln
transformieren:
– Jeder Pfad im Baum entspricht einer
Implikation: die Konjunktion aller inneren
Knoten impliziert das Blatt
– Der Baum entspricht der Disjunktion der
Regeln, die durch die Pfade definiert werden.
Beispiel
• Wenn (Outlook=sunny und
Humidity=high), dann
PlayTennis=No
• Wenn (Outlook=sunny und
Humidity=normal), dann
PlayTennis=Yes
• Wenn (Outlook=overcast), dann
PlayTennis=Yes
• Wenn (Outlook=rain und
Wind=strong), dann
PlayTennis=No
• Wenn (Outlook=rain und
Wind=weak), dann
PlayTennis=Yes
„Pruning“ durch Generalisierung
der Regeln
• Konvertiere den Baum in seine Regelmenge
• Generalisiere jede Regel für sich:
– Entferne diejenigen Bedingungen aus der Regel, die
zu einer Verbesserung der Akkuratheit führen
• Sortiere die endgültigen Regeln nach ihrer
erwarteten Akkuratheit
• Bemerkung: das Ergebnis entspricht nicht mehr
notwendig einem Entscheidungs-Baum!
Warum?
Regelgeneralisierung
• Vorteile:
– Größere Flexibilität bei der Generalisierung:
im Baum kann ein Knoten nur komplett oder
gar nicht gelöscht werden, in der Regel ist
„partielles Löschen“ abhängig vom Kontext
möglich
– Keine Anordnung der Tests, d.h. Löschen
erfordert keine Umorganisation
– Bessere Lesbarkeit und Verständlichkeit der
Regeln für den Benutzer
Attribut-Selektion
• Problem:
– Information Gain bevorzugt tendenziell
Attribute mit rel. vielen Werten gegenüber
solchen mit rel. wenig Werten
• Alternatives Mass zur Selektion:
– „gain ratio“
Gain Ratio
• Basiert auf Information Gain
• Modifiziert durch einen Faktor, der misst,
wie breit und wie gleichmäßig ein Attribut
die Daten splittet: SI (= Split Information)
• SI(T,A) = -∑i=1c(|Ti|/|T|)*log2*(|Ti|/|T|)
• GainRatio(T,A) =
GAIN(T,A)/SplitInformation(T,A)
C4.5
• C4.5 ist die Weiterentwicklung von ID3
(Quinlan 1986)
• Unterschied:
– Verwende GainRation zur Attribut-Selektion
– Nachträgliche Generalisierung der Regeln
Weitere Probleme
• Attribute mit nicht-diskreten Werten
– Z.B. Temperatur
– Lösung: mache Werte diskret, z.B. durch
• Runden auf ganze Zahlen
• Abbildung auf Intervalle
• Zweiteilung durch >, <=
• „Kosten“ eines Attributs
– Wichtig z.B. bei med. Entscheidungen: „Kosten“ einer
Untersuchung
• Berechne die Kosten bei der Auswahl der Attribute mit ein
• Z.B. Gain(T,A)2/Cost(A)
• Z.B. 2GAIN(T,A) -1)/((cost(A)+1)w
Weitere Probleme
• Unbekannte Attribut Werte
– Was passiert mit unvollständigen Trainingsdaten?
– Versuche sie trotzdem in den Baum einzubauen:
• Falls Knoten k nicht spezifiziertes Attribut A testet: nehme für
A einen plausiblen Wert an:
– Z.B. der häufigste in Bezug auf die Beispiele, die unterhalb von
k liegen
– Z.B. der häufigste in Bezug auf alle Beispiele mit demselben
Zielwert
– Weise jedem Wert seine Wahrscheinlichkeit pi zu und weise
jedem Wert das Beispiel zum Anteil von pi zu
– Verfahre analog zur Klassifikation von neuen
Instanzen
Zusammenfassung
• Entscheidungsbäume eignen sich insbesondere für das Lernen von
Konzepten und Klassifikationsproblemen
• Basis für die meist verwandten Algorithmen ist der ID3 Algorithmus
von Quinlan
• ID3 geht von einem vollständigen Hypothesen-Raum aus mit einer
Präferenz für möglichst kurze Bäume und den spezifischsten
Attributen möglichst nahe an der Wurzel
• Hauptproblem von ID3: Overfitting
• Weiterentwicklungen von ID3 beziehen sich auf:
– Lösen des Overfitting Problems
– Verbesserte Attribut-Selektion
– Berühmtestes Beispiel: C4.5
• Overfitting ist – nicht nur in Bezug auf Entscheidungsbäume – eines
der großen Probleme beim maschinellen Lernen
Aufgaben
•
Ziel: erstellen Sie sich einen individuellen Entscheidungsbaum für die Auswahl von Kursen.
Trainingsmenge sind die Veranstaltungen des CIS im WS 03/04 und SS 04 zusammen mit Ihrer
Auswahl: Besucht – nicht besucht. Beschreiben Sie zunächst alle Veranstaltungen gemäß
folgenden Attributen und Werten:
–
–
–
–
–
–
–
–
–
–
–
–
•
•
•
•
Typ = {PS, HS, Vorl., Praktikum}
Bereich = {CL, Inf, Math. Ling}
Art = {theoretisch, praktisch}
Dozent = {alle Dozenten des CIS} (bei mehreren bitte einen auswählen)
Uhrzeit = {vorm., nachm., abends}
Semester = {WS, SS}
Stundenzahl = {1,2,3,4}
Klausur = {ja,nein}
Hausarbeit = {ja,nein}
Übungsaufgaben = {ja,nein}
Schon besucht = {ja,ein}
Pflichtkurs = {ja,nein}
Erstellen Sie mit einem Algorithmus Ihrer Wahl (ID3 oder C4.5) einen Entscheidungsbaum (falls
Sie sehr wenig Kurse besuchen, betrachten Sie bitte auch diejenigen als besucht, die Sie evt.
Auch gerne besucht hätten.
Extrahieren Sie aus diesem Baum die Regeln
Inwiefern entsprechen die so entstandenen Regeln Ihren tatsächlichen Kriterien bei der Auswahl
der Kurse?
Haben Sie das Gefühl, dass es zu Overfitting kam? Wie würden Sie das in diesem Fall beheben?

Entscheidungsbäume Teil 2