3. Decision Trees Flashcards
Decision Trees?
Supervised Learning
vorklassifizierte Trainingsdaten benötigt (rein & gut verteilt)
Zielvariable festgelegt
Ziel Decision Tree?
Im Wurzelelement noch alle Elemente des Datensatzes vereint
Aufteilung aufgrund einer Eigenschaft, bzw. eines Attributes, in Teilmengen auf (Knoten)
Ziel: resultierenden Knoten möglichst rein, also die Klassen möglichst gut getrennt sind
Algorithmen Decision Tree?
Je nach Art der Aufteilung und dem Maß für die Güte des Splits haben sich verschiedene Algorithmen herauskristallisiert.
Was kann dabei immer passieren?
Achtung! Kann oft zu Over- oder Underfitting kommen. Dies muss immer mitberücksichtigt werden!
CART Algorithmus
Der Classification und Regression Tree (CART) führt nur Binäre Splits durch, das bedeutet, dass die Knoten immer nur in zwei Teilmengen aufgeteilt werden.
Das Gütemaß hierfür sind die Kombination aus der Reinheit der resultierenden Knoten (rechter Teil der Formel) und einer gleichmäßigen Größe der resultierenden Knoten (linker Teil der Formel).
Der Algorithmus prüft alle möglichen Splits und nimmt den besten raus.
C4.5 Algorithmus
Es finden nicht nur binäre Splits statt. So wird bei Kategorialen Attributen nach allen Attributwerten auf einmal gesplittet –> Jeder Attributwert bekommt einen eigenen Zweig.
Bei numerischen Attributen wird an einer Stelle gesplittet. Zudem ist ein wesentlicher Unterschied, dass das Gütemaß eines Splits beim C4.5 die Entropiereduktion ist.
Verwendet das Konzept der Entropiereduktion, um den optimalen Split auszuwählen.
Entropie?
Ist der Informationsgehalt einer Nachricht oder eines Ereignisses.
Je unwahrscheinlicher ein Ereignis ist, desto höher ist sein Informationsgehalt und damit auch die Entropie.
Bei Entscheidungsbäumen wollen wir die Ordnung erhöhen deshalb müssen wir hierbei die Entropie reduzieren. Wir nennen daher die Entropie auch den Information Gain.
Der Information Gain wird berechnet, indem wir die Entropie vor und nach einem Split brechen und anschließend die Differenz bilden.
Sprich es wird der Split ausgewählt der für die größte Entropiereduktion führt genommen.
Accuracy
Misst die Genauigkeit eines Splits, indem er den Anteil der korrekt klassifizierten Datenpunkte berechnet.
Information Gain
Entspricht der Entropiereduktion und misst die Verringerung der Unordnung nach einem Split. Es berechnet die Differenz zwischen der Entropie vor und nach dem Split.
Information Gain Ratio
Modifiziert das Information Gain, um besonders breite Splits zu vermeiden, indem es das Information Gain durch die Entropie des Attributs teilt. Dies führt zu kompakteren Bäumen.
Gini Index
Ein Maß für die Ungleichverteilung einer Eigenschaft, das die Wahrscheinlichkeit berechnet, dass ein zufällig ausgewähltes Element falsch klassifiziert wird, wenn es nach der Verteilung eines Attributs klassifiziert wird.
Rule Induction?
Klassifikation
–> Regeln direkt aus den Daten anleiten (statt sie aus einem Entscheidungsbaum abzuleiten)
Sequential covering?
- Leere Liste von Regeln
- Man findet eine Regel, die zumindest für ein Teil der vorliegenden Fälle passt (Finde alle möglichen Attribut-Value paare Wende eine Regel an und nehme die mit der höchsten Accuracy oder dem höchsten Information Gain)
- Dann entfernt man diese Fälle
- Sucht für die verbleibenden Fälle wieder eine Lösung
Bis keine Regel mehr da ist oder keine Datensätze mehr da sind
Konsequenz Sequential Covering
Eine Konsequenz des Sequential Covering ist, dass die resultierenden Regeln nicht unabhängig voneinander sind. (Quasi wie eine if-then-else) Kette. Also ist die Reihenfolge der Regeln zu beachten.
Sequential Covering Pruning?
Auch beim Sequential Covering muss das Pruning zum Einsatz kommen. Hier werden die Daten intern in grow (Training, Finde die beste Regel) und prune (Test) Daten eingeteilt. Prune-Datensätze werden verwendet, um die Regel durch Entfernen von Attribut-Wert-Paaren aufzugrenzen und Overfitting zu vermeiden
Pruning of decision trees
Pruning bedeutet, dass Äste des Baums entfernt werden (oder garnicht erst gebildet werden), die zu Overfitting führen würden, weil Sie nicht repräsentativ sind (Speicherung von Trainingsdaten und Overfitting vermeiden)
Parameter M = Mindestanzahl an Elementen pro Blatt an
M zu klein –> dauert der Prozess sehr lange & Baum wird sehr komplex (Overfitting)
3.4 Rule Induction vc. Decision Tree
- Die Verfahren werden bezüglich der Güte also der Accuracy verglichen (hier gibt es kaum Unterschiede)
- Man unterscheidet nach den Prinzipien Divide-and-Conquer und Separate-and-Conquer.
Divide-and-Conquer
Der Datensatz wird in zwei oder mehr Teile aufgeteilt (gesplittet) und für jeden Teil wird eine Regel aufgestellt. Dieser Prozess wird rekursiv wiederholt, wobei jeder gesplittete Teil weiter aufgeteilt wird, bis keine sinnvollen Splits mehr möglich sind oder eine bestimmte Tiefe erreicht ist.
Divide-and-Conquer Beispiel
Beispiel: Bei einem Entscheidungsbaum könnte man zuerst nach Alter splitten (jünger als 30, älter oder gleich 30) und dann jeden Teil weiter nach Einkommen (weniger als 50k, mehr als 50k) usw. splitten.
Separate-and-Conquer
Man wählt ein Attribut-Wert-Paar aus und erstellt eine Regel, die diese Paarung beschreibt. Dann wird diese Regel von den Daten entfernt (separiert) und der Prozess wird wiederholt, um weitere Regeln zu generieren.
Separate-and-Conquer Beispiel
Beispiel: Man könnte eine Regel erstellen wie “Wenn Alter < 30 und Einkommen > 50k, dann Klasse A”. Nachdem diese Regel erstellt ist, werden die Daten, die diese Regel erfüllen, entfernt und der Prozess wird für die verbleibenden Daten wiederholt.
Interpretierbarkeit der Ergebnisse
Entscheidungsbäume: Die hierarchische Struktur von Entscheidungsbäumen macht es leicht, die Entscheidungsregeln zu verstehen und zu verfolgen.
Rule Induction: Da jede Regel unabhängig erstellt wird, kann es schwieriger sein, die Gesamtheit der Regeln zu interpretieren und zu verstehen, wie sie zusammenarbeiten, um die Daten zu klassifizieren.
