Subsections of Entscheidungsbäume (Decision Tree Learner - DTL)
Machine Learning 101
TL;DR
Lernen wird in der KI oft als Verhaltensänderung (eines Systems) aufgefasst. Dabei soll eine
Gütefunktion optimiert werden.
Je nach verfügbarem Feedback eines "Lehrers" werden typischerweise drei Arten von Lernen
unterschieden: Überwachtes Lernen, Unüberwachtes Lernen, Reinforcement Lernen. Dabei stellt
der Lehrer beim überwachten Lernen Trainingsbeispiele plus eine Vorgabe (Klasse, Funktionswert)
zur Verfügung, während beim unüberwachten Lernen nur die Trainingsbeispiele bereitgestellt
werden und der Algorithmus selbst Zusammenhänge in den Daten erkennen soll. Beim Reinforcement
Learning erfolgt das Feedback am Ende einer Kette von Aktionen, d.h. der Algorithmus muss
diese Bewertung auf die einzelnen Aktionen zurückrechnen.
Beim überwachten Lernen soll eine Hypothese aufgebaut werden, die der echten (zu lernenden)
Funktion möglichst nahe kommt. Eine konsistente Hypothese erklärt die Trainingsdaten, eine
generalisierende Hypothese kann auch unbekannte Daten (die aus der selben Quelle stammen, also
zum selben Problem gehören) korrekt bewerten. Es wird unterschieden zwischen Klassifikation
(einige wenige diskrete Label/Klassen, die den Trainingsbeispielen zugeordnet sind) und
Regression (Lernen eines Funktionsverlaufs).
Merkmalsvektoren gruppieren Eigenschaften des Problems bzw. der Objekte, d.h. jedes Objekt
kann über einen Merkmalsvektor beschrieben werden. Trainingsdaten sind ausgewählte Beispielobjekte
(durch Merkmalsvektoren beschrieben) plus die Vorgabe (Klasse oder Funktionswert) vom Lehrer.
Videos (HSBI-Medienportal)
Lernziele
- (K1) Definition und Arten des Lernens
- (K2) Überwachtes Lernen: Lernen durch Beobachten (mit Lehrer)
- (K2) Merkmalsvektoren, Eigenschaften, Ausprägung, Objekte, Trainingsmenge
Was ist Lernen?
Verhaltensänderung eines Agenten in Richtung der Optimierung eines
Gütefunktionals (Bewertungsfunktion) durch Erfahrung.
Warum Lernen?
- Nicht alle Situationen vorhersehbar
- Nicht alle Details modellierbar
- Lösung oder Lösungsweg unbekannt, nicht explizit programmierbar
- Data Mining: Entdeckung neuen Wissens durch Analyse der Daten
- Selbstanpassende Programme
=> Lernen wichtige Eigenschaft lebender Wesen :-)
Learning Agent
Feedback während des Lernens
Beispiel Kleinkind: Lernen von Klassen/Konzepten durch Beispiele
- Zuerst ist alles "Katze" (Übergeneralisierung)
- Differenzierung durch Feedback der Umwelt; Erkennung unterschiedlicher Ausprägungen
Beispiel: Kreditrisiko
-
Bankkunde beantragt Kredit
-
Soll er aus Sicht der Bank den Kredit bekommen?
-
Bankangestellter betrachtet (relevante) Merkmale des Kunden:
- Alter, Einkommen, sozialer Status
- Kundenhistorie bei der Bank
- Höhe des Kredits
-
Bewertung des Kreditrisikos:
- Klassifikation: Guter oder schlechter Kunde (Binäre Entscheidung: 2 Klassen)
- Regression: Vorhersage Gewinn/Verlust für die Bank (Höhe des Gewinns/Verlusts interessant)
Beispiel: Autoreparatur
-
Gegeben: Eigenschaften eines Autos
=> Eigenschaften: Ausprägungen der Merkmale
-
Gesucht: Diagnose und Reparaturanleitung
=> Hypothese über den Merkmalen (Funktion $\operatorname{h}$)
Lernen durch Beobachten: Lernen einer Funktion $\operatorname{f}$
Funktionsapproximation: Lernen einer Funktion $\operatorname{f}$ anhand von Beispielen
-
Ein Beispiel ist ein Tupel $(\mathbf{x}, \operatorname{f}(\mathbf{x}))$, etwa
$$
(\mathbf{x}, \operatorname{f}(\mathbf{x})) = \left(\begin{array}{ccc}
O & O & X \\
. & X & . \\
X & . & .
\end{array}, +1\right)
$$
-
Aufgabe: Baue Hypothese $\operatorname{h}$ auf, so dass $\operatorname{h} \approx \operatorname{f}$.
- Benutze dazu Menge von Beispielen => Trainingsdaten.
-
Ziele:
- Konsistente Hypothese: Übereinstimmung bei Trainingsdaten
- Generalisierende Hypothese: Korrekte Vorhersage bei
unbekannten Daten
Anmerkung: Stark vereinfachtes Modell realen Lernens!
Konstruieren einer konsistenten Hypothese
Welcher Zusammenhang ist hier dargestellt? Offenbar eine Art Funktionsverlauf ...
Wir haben für einige x-Werte die zugehörigen y-Werte vorgegeben.
Konstruieren einer konsistenten Hypothese (cnt.)
Die einfachste Approximation wäre eine lineare Funktion. Allerdings werden hierbei
einige Werte mehr oder weniger stark nicht korrekt widergegeben, d.h. man hat einen
relativ hohen (Trainings-) Fehler.
Konstruieren einer konsistenten Hypothese (cnt.)
Die Hyperbel erklärt die Trainingsdaten bis auf den einen Punkt sehr gut.
Die Frage ist, ob dieser eine Punkt zum zu lernenden Zusammenhang gehört
oder ein Ausreißer ist, den man gefahrlos ignorieren kann?
Konstruieren einer konsistenten Hypothese (cnt.)
Die grüne Hypothese ist von allen bisher gezeigten die komplexeste, erklärt
aber alle Datenpunkte. D.h. hier wäre der Trainingsfehler Null. Zwischen den
Trainingsdaten zeigt das Modell eine "glatte" Approximation, d.h. es wird auch
neue Daten, die es beim Training nicht gesehen hat, relativ gut erklären.
(Dabei liegt freilich die Annahme zugrunde, dass alle relevanten Daten in der
Trainingsmenge vorhanden sind, d.h. dass es insbesondere zwischen den Datenpunkten
keine Ausreißer o.ä. gibt.)
Konstruieren einer konsistenten Hypothese (cnt.)
Diese Hypothese erklärt ebenfalls sämtliche Trainingsdaten. Allerdings schwingt
die Funktion zwischen den Daten stark hin und her. Vermutlich entspricht dies
nicht dem zu lernenden Funktionsverlauf. Der Trainingsfehler wäre wie bei der
deutlich einfacheren Hypthese aus dem letzten Schritt Null. Der Generalisierungsfehler
(sprich die Abweichung, wenn man das Modell nach Daten zwischen den Trainingspunkten
fragt) dürfte erheblich höher liegen.
D.h. hier hat das Modell einfach die Trainingsdaten auswendig gelernt, aber nicht
den Zusammenhang zwischen den Daten! Dies ist in der Regel unerwünscht!
Occam's Razor
Bevorzuge die einfachste konsistente Hypothese!
- Wenn es mehrere mögliche Erklärungen für einen Sachverhalt gibt, ist die
einfachste Erklärung allen anderen vorzuziehen.
- Eine Erklärung ist "einfach", wenn sie möglichst wenige Variablen und
Annahmen enthält und wenn diese in klaren logischen Beziehungen zueinander
stehen, aus denen der zu erklärende Sachverhalt logisch folgt.
Trainingsdaten und Merkmalsvektoren
Lehrer gibt Beispiele vor: Eingabe $\mathbf{x}$ und passende Ausgabe $\operatorname{f}(\mathbf{x})$
-
Ausgabe: typischerweise Skalar (Funktionswert oder Klasse)
=> Beispiel: Bewertung eines Spielstandes bei TicTacToe
-
Eingabe: (Beschreibung des) Objekt(s) oder Situation, die zur Ausgabe gehört
=> Beispiel: Spielstand bei TicTacToe
Merkmalsvektoren:
- Zusammenfassen der relevanten Merkmale zu Vektoren
Beispiel: Schwimmen im See
Beschreibung der Faktoren, wann ich im See schwimmen möchte:
- Scheint die Sonne?
- Wie warm ist das Wasser?
- Wie warm ist die Luft?
- Trainingsbeispiel:
- Eingabe: Merkmalsvektor
(sonnig, warm, warm)
- Ausgabe: Klasse
ja
Dabei wird davon ausgegangen, dass jeder Faktor (jedes Merkmal) an einer bestimmten
Stelle im Merkmalsvektor aufgeführt ist. Beispielsweise gehört das sonnig
zur
Frage "Scheint die Sonne", warm
jeweils zur Wasser- und zur Lufttemperatur.
Damit hat man in einem Vektor eine Situation komplett beschrieben, d.h. einen Zustand
der Welt mit den relevanten Dingen beschrieben. Diesem Zustand kann man beispielsweise
ein Label (Klasse) verpassen, hier in diesem Fall "ja, in dieser Welt möchte ich
schwimmen".
Die Trainingsmenge baut sich dann beim überwachten Lernen aus vielen solcher Paare
(Merkmalsvektor, Klasse) auf, und die Algorithmen sollen diese Zuordnung lernen, d.h.
ein Modell für diese Daten erzeugen, welches die Daten gut erklärt und darüber hinaus
für neue Daten aus der selben Datenquelle gute Vorhersagen macht.
Trainingsdaten -- Merkmalsvektoren
Generell: Merkmalsvektor für Objekt $v$:
$$
\mathbf{x}(v) = (x_1, x_2, \ldots, x_n)
$$
- $n$ Merkmale (Attribute)
- Attribut $x_t$ hat $m_t$ mögliche Ausprägungen
- Ausprägung von $v$ bzgl. $x_t$: $\quad x_t(v) = i \quad$ (mit $i = 1 \ldots m_t$)
Anmerkung: Stellen Sie sich den Merkmalsvektor vielleicht wie
einen Konstruktor einer Klasse x
vor: Die einzelnen Attribute $x_t$ sind
die Parameter, aus denen der Merkmalsvektor aufgebaut ist/wird. Jedes der
Attribute hat einen Typ und damit eine bestimmte Anzahl erlaubter Werte
("Ausprägungen") ...
Trainingsbeispiel:
- Tupel aus Merkmalsvektor und zugehöriger Klasse: $\left(\mathbf{x}(v), k\right)$
Wrap-Up
-
Lernen ist Verhaltensänderung, Ziel: Optimierung einer Gütefunktion
- Aufbau einer Hypothese, die beobachtete Daten erklären soll
- Arten: Überwachtes Lernen, Unüberwachtes Lernen, Reinforcement Lernen
-
Merkmalsvektoren gruppieren Eigenschaften des Problems bzw. der Objekte
-
Trainingsdaten: Beispielobjekte (durch Merkmalsvektoren beschrieben) plus Vorgabe vom Lehrer
Challenges
Modellierung
Sie stehen vor der Entscheidung, ob Sie sich zur Vorbereitung auf die
Flipped-Classroom-Sitzung noch das Skript anschauen. Welche Attribute
benötigen Sie, um die Situation zu beschreiben?
Metriken für Klassifikatoren
Es ist wieder Wahlkampf: Zwei Kandidaten O und M bewerben sich um die Kanzlerschaft. Die folgende Tabelle zeigt die Präferenzen von sieben Wählern.
Nr. |
Alter |
Einkommen |
Bildung |
Kandidat |
Vorhersage |
1 |
$\ge 35$ |
hoch |
Abitur |
O |
O |
2 |
$< 35$ |
niedrig |
Master |
O |
O |
3 |
$\ge 35$ |
hoch |
Bachelor |
M |
M |
4 |
$\ge 35$ |
niedrig |
Abitur |
M |
M |
5 |
$\ge 35$ |
hoch |
Master |
O |
O |
6 |
$< 35$ |
hoch |
Bachelor |
O |
M |
7 |
$< 35$ |
niedrig |
Abitur |
M |
O |
Auf diesem Datensatz wurde ein Klassifikator trainiert, die Trainingsergebnisse sind in der Tabelle unter "Vorhersage" angegeben.
Bewerten Sie den Klassifikator.
CAL2
TL;DR
Eine Hypothese kann im einfachsten Fall als Entscheidungsbaum dargestellt werden. Die Merkmale bilden
dabei die Knoten im Baum, und je Ausprägung gibt es eine Kante zu einem Nachfolgerknoten. Ein Merkmal
bildet die Wurzel des Baums, an den Blättern sind die Klassen zugeordnet.
Einen Entscheidungsbaum kann man zur Klassifikation eines Objekts schrittweise durchlaufen: Für jeden
Knoten fragt man die Ausprägung des Merkmals im Objekt ab und wählt den passenden Ausgang aus dem Knoten.
Wenn man am Blatt angekommen ist, hat man die Antwort des Baumes auf das Objekt, d.h. üblicherweise die
Klasse.
Den Baum kann man mit dem Algorithmus CAL2 schrittweise aufbauen. Man startet mit "Nichtwissen" (symbolisiert
mit einem "*") und iteriert durch alle Trainingsbeispiele, bis der Baum sich nicht mehr verändert. Wenn
der Baum auf ein Beispiel einen "*" ausgibt, dann ersetzt man diesen "*" mit der Klasse des eben betrachteten
Beispiels. Wenn der Baum bei einem Beispiel die passende Klasse ausgibt, macht man mit dem nächsten Beispiel
weiter. Wenn der Baum bei einem Beispiel eine andere Klasse ausgibt, muss das Klassensymbol im Baum (an
der Stelle, wo das Objekt gelandet ist) durch den nächsten Test ersetzt werden: Hierzu nimmt man das nächste,
auf diesem konkreten Pfad noch nicht verwendete Merkmal. CAL2 kann nur mit diskreten Attributen und disjunkten
Klassen einen fehlerfreien Baum erzeugen.
Videos (HSBI-Medienportal)
Lernziele
- (K3) Entscheidungsbaumlerner CAL2
Entscheidungsbäume: Klassifikation
- Attribute als Knoten im Baum
- Ausprägungen als Test (Ausgang, Verzweigung)
- Klasse (Funktionswert) als Blatt
Erinnern Sie sich an das Beispiel mit der Auto-Reparatur aus der letzten Sitzung.
Die relevanten Eigenschaften (Merkmale) eines Autos würden als Knoten im Baum
repräsentiert. Beispiel: "Motor startet" oder "Farbe".
Jedes Merkmal hat eine Anzahl von möglichen Ausprägungen, diese entsprechen den
Verzweigungen am Knoten. Beispiel: "startet", "startet nicht" oder "rot", "weiß", "silber", ... .
Entsprechend kann man durch Abarbeiten des Entscheidungsbaumes am Ende zu einer
Diagnose gelangen (Klasse).
Eine andere Sichtweise ist die Nutzung als Checkliste für eine Reparatur ...
Definition Entscheidungsbaum
-
Erinnerung: Merkmalsvektor für Objekt $v$:
$$
\mathbf{x}(v) = (x_1, x_2, \ldots, x_n)
$$
- $n$ Merkmale (Attribute)
- Attribut $x_t$ hat $m_t$ mögliche Ausprägungen
- Ausprägung von $v$ bzgl. $x_t$: $\quad x_t(v) = i \quad$ (mit $i = 1 \ldots m_t$)
-
Alphabet für Baum:
$$
\lbrace x_t | t=1,\ldots,n \rbrace \cup \lbrace \kappa | \kappa = \ast,A,B,C,\ldots \rbrace \cup \lbrace (,) \rbrace
$$
-
Entscheidungsbaum $\alpha$:
$$
\alpha = \left\lbrace \begin{array}{ll}
\kappa & \text{Terminalsymbole: } \kappa = \ast,A,B, \ldots\\
x_t(\alpha_1, \alpha_2, \ldots, \alpha_{m_t}) & x_t \text{ Testattribut mit } m_t \text{ Ausprägungen}
\end{array}\right.
$$
Anmerkung: Stellen Sie sich die linearisierte Schreibweise wieder
wie den (verschachtelten) Aufruf von Konstruktoren vor. Es gibt die
Oberklasse Baum
, von der für jedes Attribut eine Klasse abgeleitet
wird. D.h. der Konstruktor für eine Attributklasse erzeugt letztlich
ein Objekt vom Obertyp Baum
. Außerdem sind die Terminalsymbole A
,
B
, ... Objekte vom Typ Blatt
, welches eine Unterklasse von Baum
ist ...
Dabei wird die Anzahl der möglichen Ausprägungen für ein Attribut
berücksichtigt: Jede Ausprägung hat einen Parameter im Konstruktor.
Damit werden die Unterbäume beim Erzeugen des Knotens übergeben.
Induktion von Entscheidungsbäumen: CAL2
-
Anfangsschritt: $\alpha^{(0)} = \ast$ (totales Unwissen)
-
$n$-ter Lernschritt: Objekt $v$ mit Klasse $k$, Baum $\alpha^{(n-1)}$
gibt $\kappa$ aus
- $\kappa = \ast$: ersetze $\ast$ durch $k$
- $\kappa = k$: keine Aktion nötig
- $\kappa \neq k$: Fehler
- Ersetze $\kappa$ mit neuem Test: $\kappa \gets x_{t+1}(\ast, \ldots, \ast, k, \ast, \ldots, \ast)$
- $x_{t+1}$: nächstes Attribut, auf dem aktuellen Pfad noch nicht verwendet
- Symbol $k$ an Position $i$ wenn $x_{t+1}(v) = i$
$\alpha^{(n)}$ bezeichnet den Baum im $n$-ten Lernschritt.
CAL2 ist ein Meta-Algorithmus: Es ist ein Algorithmus, um einen Algorithmus
zu lernen :-)
Beispiel mit CAL2
$x_1$ |
$x_2$ |
$x_3$ |
$k$ |
0 |
0 |
1 |
A |
1 |
0 |
0 |
A |
0 |
1 |
4 |
B |
1 |
1 |
2 |
B |
0 |
0 |
3 |
A |
Ergebnis: $x_1(x_2(A, B), x_2(A, B))$
Anmerkung: Denken Sie an die Analogie von oben. $x_1$ kann als
Konstruktor einer Klasse x1
betrachtet werden, die eine Unterklasse
von Baum
ist. Durch den Aufruf des Konstruktors wird als ein Baum
erzeugt.
Es gibt in $x_1$ zwei mögliche Ausprägungen, d.h. der Baum hat in
diesem Knoten zwei alternative Ausgänge. Diese Unterbäume werden
dem Konstruktor von x1
direkt beim Aufruf übergeben (müssen also
Referenzen vom Typ Baum
sein).
CAL2: Bemerkungen
Wrap-Up
- Darstellung der Hypothese als Entscheidungsbaum
- CAL2: diskrete Attribute, disjunkte Klassen
Challenges
Modellierung
Sie stehen vor der Entscheidung, ob Sie sich zur Vorbereitung auf die
Flipped-Classroom-Sitzung noch das Skript anschauen.
Zeichnen Sie einen Entscheidungsbaum, der Ihnen bei der Entscheidung hilft.
Textklassifikation
Betrachten Sie die folgenden Aussagen:
- Patient A hat weder Husten noch Fieber und ist gesund.
- Patient B hat Husten, aber kein Fieber und ist gesund.
- Patient C hat keinen Husten, aber Fieber. Er ist krank.
- Patient D hat Husten und kein Fieber und ist krank.
- Patient E hat Husten und Fieber. Er ist krank.
Aufgaben:
- Trainieren Sie auf diesem Datensatz einen Klassifikator mit CAL2.
- Ist Patient F krank? Er hat Husten, aber kein Fieber.
Handsimulation CAL2
Zeigen Sie mit einer Handsimulation, wie CAL2 mit dem folgenden
Trainingsdatensatz schrittweise einen Entscheidungsbaum generiert.
Nutzen Sie die linearisierte Schreibweise.
Beispiel |
$x_1$ |
$x_2$ |
$x_3$ |
Klasse |
1 |
a |
a |
a |
1 |
2 |
a |
b |
a |
2 |
3 |
a |
a |
b |
1 |
4 |
b |
a |
b |
1 |
5 |
a |
a |
c |
1 |
6 |
b |
b |
b |
2 |
Welchen Entscheidungsbaum würde CAL2 lernen, wenn dem Trainingsdatensatz
der Vektor $((a,a,b), 2)$ als Beispiel Nr. 7 hinzugefügt werden würde?
Quellen
- [Unger1981] Lernfähige Klassifizierungssysteme (Classifier Systems Which Are Able to Learn)
Unger, S. und Wysotzki, F., Akademie-Verlag, 1981.
Der Vollständigkeit halber aufgeführt (Werk ist leider vergriffen und wird nicht mehr verlegt)
Pruning
TL;DR
Pruning ist das Entfernen redundanter und irrelevanter Tests (Merkmale).
Irrelevante Merkmale spielen keine Rolle bei der Klassifikation, an jedem Ausgang
eines irrelevanten Merkmals findet sich exakt der selbe Baum. Diese Tests kann man
einfach entfernen und durch einen ihrer Teilbäume ersetzen; dadurch ändert sich
nicht die Klassifikation des Baumes.
Bei redundanten Tests sind alle Ausgänge bis auf einen noch mit "Nichtwissen" ("*")
markiert. Hier kann man den Test durch den einen bekannten Ausgang ersetzen, wodurch
sich die Klassifikation ändert. Allerdings wird der Klassifikationsfehler nicht größer,
da man ja vorher nur für eine Ausprägung des redundanten Merkmals einen Baum hatte und
für die anderen jeweils mit "*" antworten musste (d.h. hier stets einen Fehler gemacht
hatte).
Über die Transformationsregel kann man einfach die Reihenfolge von Tests im Baum ändern.
Videos (HSBI-Medienportal)
Lernziele
- (K3) Pruning: Entfernen bedingt irrelevanter Tests
- (K3) Pruning: Entfernen bedingt redundanter Tests
- (K3) Umformen von Entscheidungsbäumen mit Transformationsregel
Pruning: Bedingt irrelevante Attribute
Baum: $\alpha = x_1(x_2(A, B), x_2(A, B), x_2(A, B))$
$x_1$ ist bedingt irrelevant
=> Vereinfachung: $\alpha = x_2(A, B)$
Allgemein:
- Sei $\tilde{x}$ Weg zu Nichtendknoten $x_t$
- Baum dort $\alpha/\tilde{x} = x_t(\alpha_1, \ldots, \alpha_{m_t})$
- $x_t$ ist bedingt irrelevant unter der Bedingung
$\tilde{x}$, wenn $\alpha_1 = \alpha_2 = \ldots = \alpha_{m_t}$
- Vereinfachung: Ersetze in $\alpha/\tilde{x}$ den Test $x_t$ durch $\alpha_1$
Anmerkung:
Der durch das Entfernen von bedingt irrelevanten Attributen entstandene Baum
hat exakt die selbe Aussage (Klassifikation) wie der Baum vor dem Pruning.
Anmerkung:
$x_1$ im obigen Beispiel ist sogar global irrelevant, da es sich hier
um die Wurzel des Baumes handelt. Der Weg $\tilde{x}$ ist in diesem Fall der leere
Weg ...
Pruning: Bedingt redundante Attribute
Baum: $\alpha = x_1(\ast, \ast, x_2(A, B))$
$x_1$ ist bedingt redundant
=> Vereinfachung: $\alpha = x_2(A, B)$
Allgemein:
- Sei $\tilde{x}$ Weg zu Nichtendknoten $x_t$
- Baum dort $\alpha/\tilde{x} = x_t(\ast, \ldots, \ast, \alpha_i, \ast, \ldots, \ast)$ (mit $\alpha_i \neq \ast$)
- $x_t$ ist bedingt redundant unter der Bedingung $\tilde{x}$
- Vereinfachung: Ersetze in $\alpha/\tilde{x}$ den Test $x_t$ durch $\alpha_i$
Anmerkung:
Der durch das Entfernen von bedingt redundanten Attributen entstandene Baum
hat eine etwas andere Klassifikation als der Baum vor dem Pruning. Wo vorher
ein *
ausgegeben wurde, wird nach dem Pruning u.U. ein Klassensymbol
ausgegeben. Der Klassifikationsfehler erhöht sich aber nicht, da hier ein
*
wie ein falsches Klassensymbol zu werten ist.
Anmerkung:
$x_1$ im obigen Beispiel ist sogar global redundant, da es sich
hier um die Wurzel des Baumes handelt. Der Weg $\tilde{x}$ ist in diesem Fall
der leere Weg ...
$$
x_1(x_2(a, b), x_2(c, d)) \Leftrightarrow x_2(x_1(a, c), x_1(b, d))
$$
Wrap-Up
- Pruning: Entfernen bedingt redundanter und irrelevanter Tests
- Transformationsregel zum Umbauen von Entscheidungsbäumen
CAL3
TL;DR
CAL3 ist eine einfache Erweiterung von CAL2 für nicht-disjunkte (überlappende) Klassen. Statt
beim Baumaufbau bei einer Fehlklassifikation sofort zu verzweigen, werden hier zunächst die
im entsprechenden Pfad aufgelaufenen Klassensymbole gezählt. Wenn ausreichend viele davon
gesehen wurden (Schwelle $S_1$), wird eine Entscheidung getroffen: Wenn eine Klasse in diesem
temporären Blatt dominiert (ihre Häufigkeit über einer Schwelle $S_2$ liegt), dann entscheidet
man sich in diesem Blatt fest für diese Klasse. Ansonsten (die Häufigkeit aller Klassen in
dem Blatt liegt unter $S_2$) nimmt man analog zu CAL2 den nächsten, auf diesem Pfad noch nicht
verwendeten Test hinzu.
Videos (HSBI-Medienportal)
Lernziele
- (K3) Meta-Algorithmus CAL3 für überlappende Klassen
CAL3: Erweiterung von CAL2 für nicht-disjunkte Klassen
-
Anfangsschritt: $\alpha^{(0)} = \ast$ (totales Unwissen)
-
$n$-ter Lernschritt: Objekt $v$ mit Klasse $k$
Falls nun die Summe aller Klassen am Endknoten größer/gleich $S_1$ (Statistikschwelle):
-
Für genau eine Klasse gilt: $P(k | \tilde{x}) \ge S_2$:
=> Abschluss: Ersetze Vereinigungsklasse durch $k$ (für immer!)
-
Für alle Klassen gilt: $P(k | \tilde{x}) < S_2$:
=> Differenzierung: Ersetze Vereinigungsklasse durch neuen
Test: $\kappa \gets x_{t+1}(\ast, \ldots, \ast, /k1/, \ast, \ldots, \ast)$
$x_{t+1}$: nächstes Attribut, auf dem aktuellen Pfad $\tilde{x}$
noch nicht verwendet
Symbol $k$ mit Anzahl 1 an Position $i$ wenn $x_{t+1}(v) = i$
Beispiel mit CAL3
$x_1$ |
$x_2$ |
$k$ |
0 |
0 |
A |
0 |
1 |
B |
0 |
1 |
A |
1 |
0 |
B |
1 |
1 |
A |
Ergebnis: $x_1(A, x_2(B, A))$
Trainingsfehler: $1/5 = 0.2 < 1-S_2 = 1-0.7 = 0.3$
Hinweis: Bei nicht überlappenden Klassen erzeugt CAL3 u.U. andere Bäume als CAL2 ...
CAL3: Abbruchbedingungen und Parameter
-
Parameter:
- $S_1$: Statistikschwelle, problemabhängig wählen
- $S_2$: $0.5 < S_2 \le 1.0$
- Klassifikationsfehler kleiner als $1-S_2$
- kleiner Fehler => großer Baum
- großer Fehler => kleiner Baum
-
Abbruch:
- Alle Trainingsobjekte richtig klassifiziert
=> Kein Fehler in einem kompletten Durchlauf
- Alle Endknoten mit eindeutigen Klassensymbolen belegt
- Differenzierung nötig, aber alle Merkmale verbraucht
- Lernschrittzahl überschritten
Wrap-Up
- CAL3: Erweiterung von CAL2 für überlappende Klassen
- Parameter $S_1$ (Anzahl Objekte bis Entscheidung), $S_2$ (Dominanz?)
- Trainingsfehler wg. überlappender Klassen!
Challenges
Textklassifikation
Betrachten Sie die folgenden Aussagen:
- Patient A hat weder Husten noch Fieber und ist gesund.
- Patient B hat Husten, aber kein Fieber und ist gesund.
- Patient C hat keinen Husten, aber Fieber. Er ist krank.
- Patient D hat Husten und kein Fieber und ist krank.
- Patient E hat Husten und Fieber. Er ist krank.
Aufgaben:
- Trainieren Sie auf diesem Datensatz einen Klassifikator mit CAL3 ($S_1=4, S_2=0.6$).
- Ist Patient F krank? Er hat Husten, aber kein Fieber.
Quellen
- [Unger1981] Lernfähige Klassifizierungssysteme (Classifier Systems Which Are Able to Learn)
Unger, S. und Wysotzki, F., Akademie-Verlag, 1981.
Der Vollständigkeit halber aufgeführt (Werk ist leider vergriffen und wird nicht mehr verlegt)
Entropie
TL;DR
Die Entropie kann als Maß für den Informationsgehalt einer Trainingsmenge betrachtet werden:
Wieviele Ja/Nein-Entscheidungen sind nötig, um die Daten fehlerfrei zu repräsentieren?
Nach der Wahl eines Attributs kann die verbleibende mittlere Entropie berechnet werden. Damit
hat man ein Kriterium für die Auswahl von Attributen beim Aufbau von Entscheidungsbäumen:
Nimm das Attribut, welches einen möglichst hohen Informationsgehalt hat. Oder andersherum:
Wähle das Attribut, bei dem die verbleibende mittlere Entropie der Trainingsmenge nach der
Wahl des Attributs am kleinsten ist.
Videos (HSBI-Medienportal)
Lernziele
- (K3) Berechnung der Entropie und des Information Gain
Wie Attribute wählen?
Erinnerung: CAL2/CAL3
- Zyklische Iteration durch die Trainingsmenge
- Ausschließlich aktuelles Objekt betrachtet
- Reihenfolge der "richtigen" Attributwahl bei Verzweigung unklar
=> Betrachte stattdessen die komplette Trainingsmenge!
- Shannon/Weaver (1949): Entropie
- Maß für die Unsicherheit einer Zufallsvariablen
- Anzahl der Bits zur Darstellung der Ergebnisse eines Zufallsexperiments
Beispiele
- Münze, die immer auf dem Rand landet: keine Unsicherheit, 0 Bit
- Faire Münze: Kopf oder Zahl: Entropie 1 Bit
- Fairer 4-seitiger Würfel: 4 mögliche Ausgänge: Entropie 2 Bit
- Münze, die zu 99% auf einer Seite landet: Entropie nahe Null
=> Anzahl der Ja/Nein-Fragen, um zur gleichen Information zu kommen
Definition der Entropie $H(V)$ für Zufallsvariable $V$
- Zufallsvariable $V$ => mögliche Werte $v_k$
- Wahrscheinlichkeit für $v_k$ sei $p_k = P(v_k)$
$H(V) = -\sum_k p_k \log_2 p_k$
Hinweis:
$\log_2 x = \frac{\log_{10} x}{\log_{10} 2} = \frac{\log x}{\log 2}$
- Nur eine Klasse: $\log_2 1 = 0$ => $H(V) = 0$ Bit
- Zwei Klassen, gleichwahrscheinlich: $\log_2 0.5 = -1$ => $H(V) = 1$ Bit
Beispiele Entropie: faire Münze
Entropie: $H(V) = -\sum_k p_k \log_2 p_k$
- $v_1 = \operatorname{Kopf}, v_2 = \operatorname{Zahl}$
- $p_1 = 0.5, p_2 = 0.5$
- $H(\operatorname{Fair}) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1$ Bit
$\log_2 0.5 = -1$
Beispiele Entropie: unfaire Münze
Entropie: $H(V) = -\sum_k p_k \log_2 p_k$
$\log_2 0.01 \approx -6.64$
$\log_2 0.99 \approx -0,014$
Beispiele Entropie: 4-seitiger Würfel
Entropie: $H(V) = -\sum_k p_k \log_2 p_k$
- $v_1 = 1, v_2 = 2, v_3 = 3, v_4 = 4$
- $p_1 = p_2 = p_3 = p_4 = 0.25$
- $H(\operatorname{Wuerfel}) = -4\cdot(0.25 \log_2 0.25) = 2$ Bit
$\log_2 0.25 = -2$
Entropie der Trainingsmenge: Häufigkeit der Klassen zählen
Nr. |
$x_1$ |
$x_2$ |
$x_3$ |
$k$ |
1 |
0 |
0 |
0 |
A |
2 |
1 |
0 |
2 |
A |
3 |
0 |
1 |
1 |
A |
4 |
1 |
1 |
0 |
B |
5 |
0 |
1 |
1 |
B |
6 |
0 |
1 |
0 |
A |
- Anzahl Klasse $A$: 4
- Anzahl Klasse $B$: 2
- Gesamtzahl Beispiele: 6
Wahrscheinlichkeit für $A$: $p_A = 4/6 = 0.667$
Wahrscheinlichkeit für $B$: $p_B = 2/6 = 0.333$
$$
\begin{array}{rcl}
H(S) &=& -\sum_k p_k \log_2 p_k\\
&=& -(4/6 \cdot \log_2 4/6 + 2/6 \cdot \log_2 2/6)\\
&=& -(-0.39 -0.53) = 0.92 \operatorname{Bit}
\end{array}
$$
Mittlere Entropie nach Betrachtung von Attribut $A$
$$
R(S, A) = \sum_{v \in \operatorname{Values}(A)} \frac{|S_v|}{|S|} H(S_v)
$$
-
Auswahl von Attribut $A$ partitioniert die Trainingsmenge:
Je Ausprägung $v$ von $A$ erhält man eine Submenge $S_v$
-
$R(S, A)$ berechnet die mittlere Entropie der Trainingsmenge, nachdem
Attribut $A$ ausgewählt wurde: Unsicherheit/nötige Bits nach Auswahl von
Attribut $A$
Entropie der Trainingsmenge nach Attributwahl
Nr. |
$x_1$ |
$x_2$ |
$x_3$ |
$k$ |
1 |
0 |
0 |
0 |
A |
2 |
1 |
0 |
2 |
A |
3 |
0 |
1 |
1 |
A |
4 |
1 |
1 |
0 |
B |
5 |
0 |
1 |
1 |
B |
6 |
0 |
1 |
0 |
A |
- Sei Attribut $x_1$ ausgewählt
- $x_1$ partitioniert die Trainingsmenge
- $x_1=0$ liefert $S_0 = \lbrace 1,3,5,6 \rbrace$
- $x_1=1$ liefert $S_1 = \lbrace 2,4 \rbrace$
- Häufigkeit für $x_1=0$: $4/6$
- Häufigkeit für $x_1=1$: $2/6$
- Gesamtzahl Beispiele: 6
$$
\begin{array}{rcl}
R(S, A) &=& \sum_{v \in \operatorname{Values}(A)} \frac{|S_v|}{|S|} H(S_v)\\
&=& 4/6 \cdot H(\lbrace 1,3,5,6 \rbrace) + 2/6 \cdot H(\lbrace 2,4 \rbrace)\\
&=& 4/6\cdot(-3/4 \cdot \log_2 3/4 - 1/4 \cdot \log_2 1/4) +\\
&& 2/6\cdot(-1/2 \cdot \log_2 1/2 - 1/2 \cdot \log_2 1/2)\\
&=& 0.54 + 0.33 = 0.87 \operatorname{Bit}
\end{array}
$$
Ausblick: Gini Impurity
Wir haben hier die Entropie
als Maß für den Informationsgehalt einer Trainingsmenge genutzt. $R(S,A)$ als die mittlere
Entropie nach Betrachtung von Attribut $A$ wird von typischen Entscheidungsbaumverfahren
wie ID3 und C4.5 genutzt, um bei einer Verzweigung das nächste möglichst aussagekräftige
Merkmal auszuwählen.
In anderen Entscheidungsbaumlernern wird stattdessen die
Gini Impurity
zur Bestimmung des Informationsgehalts eingesetzt (u.a. CART). Dieses Maß sagt aus,
wie oft man ein zufällig gezogenes Element des Datensatzes falsch klassifizieren
würde, wenn man es mit einer zufälligen Klasse basierend auf der Verteilung der
Klassen im Datensatz labeln würde.
Hierzu drei lesenswerte Blog-Einträge:
Wrap-Up
- Begriff und Berechnung der Entropie: Maß für die Unsicherheit
- Begriff und Berechnung des Informationsgewinns
- Entropie für eine Trainingsmenge
- Mittlere Entropie nach Wahl eines Attributs
Challenges
Entropie einer Trainingsmenge
Betrachten Sie die folgenden Aussagen:
- Patient A hat weder Husten noch Fieber und ist gesund.
- Patient B hat Husten, aber kein Fieber und ist gesund.
- Patient C hat keinen Husten, aber Fieber. Er ist krank.
- Patient D hat Husten und kein Fieber und ist krank.
- Patient E hat Husten und Fieber. Er ist krank.
Aufgaben:
- Geben Sie die Entropie $H(S)$ der Trainingsmenge an.
- Berechnen Sie $R(H,A)$ (die mittlere Entropie der Trainingsmenge, nachdem Attribut $A$ gesehen wurde) für die einzelnen Attribute.
Quellen
- [Ertel2017] Introduction to Artificial Intelligence
Ertel, W., Springer, 2017. ISBN 978-3-319-58487-4. DOI 10.1007/978-3-319-58487-4.
Entscheidungsbäume: Abschnitt 8.4 - [Mitchell2010] Machine Learning
Mitchell, T., McGraw-Hill, 2010. ISBN 978-0-0711-5467-3.
ID3: Kapitel 3 - [Russell2020] Artificial Intelligence: A Modern Approach
Russell, S. und Norvig, P., Pearson, 2020. ISBN 978-0134610993.
Entscheidungsbäume: Abschnitt 19.3
ID3 und C4.5
TL;DR
Der Entscheidungsbaum-Lernalgorithmus ID3 nutzt den Informationsgehalt für die Entscheidung
bei der Attributwahl: Nimm das Attribut, welches einen möglichst hohen Informationsgehalt hat.
Oder andersherum: Wähle das Attribut, bei dem die verbleibende mittlere Entropie der Trainingsmenge
nach der Wahl des Attributs am kleinsten ist. Oder noch anders formuliert: Nimm das Attribut, bei
dem die Differenz zwischen der Entropie der Trainingsmenge (vor der Wahl des Attributs) und der
verbleibenden mittleren Entropie (nach der Wahl des Attributs) am größten ist (die Differenz nennt
man auch "Information Gain"). Die Trainingsmenge wird entsprechend der Ausprägung in Bezug auf
das eben gewählte Merkmal aufgeteilt und an die Kinder des Knotens weiter gereicht; dort wird der
Baum rekursiv weiter aufgebaut.
Durch eine Normierung des Information Gain kann eine Verbesserung in Bezug auf mehrwertige
Attribute erreicht werden, dies führt zum Algorithmus C4.5.
Videos (HSBI-Medienportal)
Lernziele
- (K3) Entscheidungsbaumalgorithmen ID3 und C4.5
Wie Attribute wählen?
Erinnerung: CAL2/CAL3
- Zyklische Iteration durch die Trainingsmenge
- Ausschließlich aktuelles Objekt betrachtet
- Reihenfolge der "richtigen" Attributwahl bei Verzweigung unklar
=> Betrachte stattdessen die komplette Trainingsmenge!
Erinnerung Entropie: Maß für die Unsicherheit
-
Entropie $H(S)$ der Trainingsmenge $S$: relative Häufigkeit der Klassen zählen
-
Mittlere Entropie nach Betrachtung von Attribut $A$
$$
R(S, A) = \sum_{v \in \operatorname{Values}(A)} \frac{|S_v|}{|S|} H(S_v)
$$
-
Informationsgewinn durch Betrachtung von Attribut $A$
$$
\begin{array}{rcl}
\operatorname{Gain}(S, A) &=& H(S) - R(S, A)\\[5pt]
&=& H(S) - \sum_{v \in \operatorname{Values}(A)} \frac{|S_v|}{|S|} H(S_v)
\end{array}
$$
$R(S,A)$ ist die Unsicherheit/nötige Bits nach Auswahl von Attribut A.
Je kleiner $R(S,A)$, um so kleiner die verbleibende Unsicherheit bzw.
um so kleiner die Anzahl der nötigen Bits zur Darstellung der
partitionierten Trainingsmenge nach Betrachtung von Attribut $A$ ...
=> Je kleiner $R(S,A)$, um so größer der Informationsgewinn
- Informationsgewinn für alle Attribute berechnen
- Nehme Attribut mit größtem Informationsgewinn als nächsten Test
Nr. |
$x_1$ |
$x_2$ |
$x_3$ |
$k$ |
1 |
0 |
0 |
0 |
A |
2 |
1 |
0 |
2 |
A |
3 |
0 |
1 |
1 |
A |
4 |
1 |
1 |
0 |
B |
5 |
0 |
1 |
1 |
B |
6 |
0 |
1 |
0 |
A |
$H(S) = 0.92 \operatorname{Bit}$
$$
\begin{array}{rcl}
\operatorname{Gain}(S, x_1) &=& 0.92 - 0.87 = 0.05 \operatorname{Bit}\\
\operatorname{Gain}(S, x_2) &=& 0.92 - 2/6 \cdot 0 - 4/6 \cdot 1\\
&=& 0.25 \operatorname{Bit}\\
\operatorname{Gain}(S, x_3) &=& 0.92 - 3/6 \cdot 0.92 - 2/6 \cdot 1 - 1/6 \cdot 0\\
&=& 0.13 \operatorname{Bit}
\end{array}
$$
Informationsgewinn für $x_2$ am höchsten => wähle $x_2$ als nächsten Test
Entscheidungsbaumlerner ID3 (Quinlan, 1986)
def ID3(examples, attr, default):
# Abbruchbedingungen
if examples.isEmpty(): return default
if examples.each(class == A): return A # all examples have same class
if attr.isEmpty(): return examples.MajorityValue()
# Baum mit neuem Test erweitern
test = MaxInformationGain(examples, attr)
tree = new DecisionTree(test)
m = examples.MajorityValue()
for v_i in test:
ex_i = examples.select(test == v_i)
st = ID3(ex_i, attr - test, m)
tree.addBranch(label=v_i, subtree=st)
return tree
[Russell2020]: Man erhält aus dem "Learn-Decision-Tree"-Algorithmus [Russell2020, S. 678, Fig. 19.5]
den hier vorgestellten ID3-Algorithmus, wenn man die Funktion $\operatorname{Importance}(a, examples)$
als $\operatorname{InformationGain}(examples, attr)$ implementiert/nutzt.
Hinweis: Mit der Zeile if examples.each(class == A): return A
soll ausgedrückt werden, dass alle
ankommenden Trainingsbeispiele die selbe Klasse haben und dass diese dann als Ergebnis zurückgeliefert
wird. Das "A
" steht im obigen Algorithmus nur symbolisch für die selbe Klasse! Es kann also auch ein
anderes Klassensymbol als "A
" sein ...
Beispiel ID3
Nr. |
$x_1$ |
$x_2$ |
$x_3$ |
$k$ |
1 |
0 |
0 |
0 |
A |
2 |
1 |
0 |
2 |
A |
3 |
0 |
1 |
1 |
A |
4 |
1 |
1 |
0 |
B |
5 |
0 |
1 |
1 |
B |
6 |
0 |
1 |
0 |
A |
- $x2$ höchsten Information Gain
- $x2=0$ => Beispiele 1,2 => A
- $x2=1$ => Beispiele 3,4,5,6 => Information Gain berechnen,
weiter teilen und verzweigen
Beobachtung: $\operatorname{Gain}$ ist bei mehrwertigen Attributen höher
-
Faire Münze:
- Entropie = $H(\operatorname{Fair}) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1 \operatorname{Bit}$
-
4-seitiger Würfel:
- Entropie = $H(\operatorname{Dice}) = -4\cdot(0.25 \log_2 0.25) = 2 \operatorname{Bit}$
=> $\operatorname{Gain}$ ist bei mehrwertigen Attributen höher
Damit würden Attribute bei der Wahl bevorzugt, nur weil sie mehr Ausprägungen haben als andere.
Anmerkung: Im obigen Beispiel wurde einfach die Entropie für zwei "Attribute" mit unterschiedlich
vielen Ausprägungen betrachtet, das ist natürlich kein $\operatorname{Gain}(S, A)$. Aber es sollte
deutlich machen, dass Merkmale mit mehr Ausprägungen bei der Berechnung des Gain für eine Trainingsmenge
einfach wegen der größeren Anzahl an Ausprägungen rechnerisch bevorzugt würden.
C4.5 als Verbesserung zu ID3
Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A)$
$$
\operatorname{Normalisation}(A) = \frac{1}{
\sum_{v \in \operatorname{Values}(A)} p_v \log_2 \frac{1}{p_v}
}
$$
C4.5 kann zusätzlich u.a. auch noch mit kontinuierlichen Attributen umgehen, vgl.
en.wikipedia.org/wiki/C4.5_algorithm.
In einem Paper
(DOI 10.1007/s10115-007-0114-2) wurde
der Algorithmus zu den "Top 10 algorithms in data mining" ausgewählt.
Im Wikipedia-Artikel Information Gain
finden Sie weitere Informationen zum "Informationsgewinn" (Information Gain).
Ein anderer, relativ ähnlich arbeitender Entscheidungsbaumlerner ist der
CART (Classification And Regression Tree)-Algorithmus,
wobei der Begriff "CART" allerdings oft auch einfach allgemein für "Entscheidungsbaumlerner"
genutzt wird.
Hierzu drei lesenswerte Blog-Einträge:
Beispiele zur Normierung bei C4.5
-
Faire Münze:
- Entropie = $H(\operatorname{Fair}) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1 \operatorname{Bit}$
- Normierung: $1/(0.5 \log_2 (1/0.5) + 0.5 \log_2 (1/0.5)) = 1/(0.5 \cdot 1 + 0.5 \cdot 1) = 1$
- Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A) = 1 \operatorname{Bit} \cdot 1 = 1 \operatorname{Bit}$
-
4-seitiger Würfel:
- Entropie = $H(\operatorname{Dice}) = -4\cdot(0.25 \log_2 0.25) = 2 \operatorname{Bit}$
- Normierung: $1/(4\cdot 0.25 \log_2 (1/0.25)) = 1/(4\cdot 0.25 \cdot 2) = 0.5$
- Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A) = 2 \operatorname{Bit} \cdot 0.5 = 1 \operatorname{Bit}$
=> Normierung sorgt für fairen Vergleich der Attribute
Anmerkung: Auch hier ist die Entropie natürlich kein $\operatorname{Gain}(S, A)$. Das Beispiel soll
nur übersichtlich deutlich machen, dass der "Vorteil" von Attributen mit mehr Ausprägungen durch die
Normierung in C4.5 aufgehoben wird.
Wrap-Up
- Entscheidungsbaumlerner ID3
- Nutze Information Gain zur Auswahl des nächsten Attributs
- Teile die Trainingsmenge entsprechend auf ("nach unten hin")
- Verbesserung durch Normierung des Information Gain: C4.5
Challenges
Textklassifikation
Betrachten Sie die folgenden Aussagen:
- Patient A hat weder Husten noch Fieber und ist gesund.
- Patient B hat Husten, aber kein Fieber und ist gesund.
- Patient C hat keinen Husten, aber Fieber. Er ist krank.
- Patient D hat Husten und kein Fieber und ist krank.
- Patient E hat Husten und Fieber. Er ist krank.
Aufgaben:
- Trainieren Sie auf diesem Datensatz einen Klassifikator mit ID3.
- Ist Patient F krank? Er hat Husten, aber kein Fieber.
Quellen
- [Ertel2017] Introduction to Artificial Intelligence
Ertel, W., Springer, 2017. ISBN 978-3-319-58487-4. DOI 10.1007/978-3-319-58487-4.
Entscheidungsbäume: Abschnitt 8.4 - [Mitchell2010] Machine Learning
Mitchell, T., McGraw-Hill, 2010. ISBN 978-0-0711-5467-3.
ID3: Kapitel 3 - [Russell2020] Artificial Intelligence: A Modern Approach
Russell, S. und Norvig, P., Pearson, 2020. ISBN 978-0134610993.
Entscheidungsbäume: Abschnitt 19.3