Entscheidungsbäume (Decision Tree Learner - DTL)

Beim überwachten Lernen soll eine Hypothese aufgebaut werden, die der echten (zu lernenden) Funktion möglichst nahe kommt. 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.

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 (YouTube)
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

  • Überwachtes Lernen

    • Lernen durch Beobachtung
    • Vorgabe von Beispielen: Ein- und Ausgabewerte

    => Regression, Klassifikation

  • Unüberwachtes Lernen

    • Erkennen von Mustern in den Inputdaten, Clustering
    • Kein Feedback (!)
  • Reinforcement Lernen

    • Bewertung der Aktionen des Agenten am Ende einer Aktionsfolge

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:

    1. Konsistente Hypothese: Übereinstimmung bei Trainingsdaten
    2. 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!

  1. Wenn es mehrere mögliche Erklärungen für einen Sachverhalt gibt, ist die einfachste Erklärung allen anderen vorzuziehen.
  2. 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:

  1. Scheint die Sonne?
  2. Wie warm ist das Wasser?
  3. 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.

Quellen

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 (YouTube)
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

  1. Anfangsschritt: $\alpha^{(0)} = \ast$ (totales Unwissen)

  2. $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

  • Nur für diskrete Merkmale und disjunkte Klassen

  • Zyklischer Durchlauf durch Trainingsmenge

  • Abbruch:

    • Alle Trainingsobjekte richtig klassifiziert => Kein Fehler in einem kompletten Durchlauf
    • (Differenzierung nötig, aber alle Merkmale verbraucht)
    • (Lernschrittzahl überschritten)

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:

  1. Trainieren Sie auf diesem Datensatz einen Klassifikator mit CAL2.
  2. 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 (YouTube)
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 ...

Allgemeine Transformationsregel

$$ 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
Quellen

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 (YouTube)
Videos (HSBI-Medienportal)
Lernziele
  • (K3) Meta-Algorithmus CAL3 für überlappende Klassen

CAL3: Erweiterung von CAL2 für nicht-disjunkte Klassen

  1. Anfangsschritt: $\alpha^{(0)} = \ast$ (totales Unwissen)

  2. $n$-ter Lernschritt: Objekt $v$ mit Klasse $k$

    • Rückweisung (Endknoten mit $\ast$): Ersetze $\ast$ durch Vereinigungsklasse $/k1/$

    • Endknoten mit Vereinigungsklasse:

      • Zähler für $k$ erhöhen, bzw.
      • $k$ mit Anzahl $1$ in Vereinigungsklasse einfügen

    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
  • $S_1 = 4, S_2 = 0.7$

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:

  1. Trainieren Sie auf diesem Datensatz einen Klassifikator mit CAL3 ($S_1=4, S_2=0.6$).
  2. 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 (YouTube)
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!

Relevanz => Informationsgehalt

  • 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$

  • $v_1 = \operatorname{Kopf}, v_2 = \operatorname{Zahl}$
  • $p_1 = 0.99, p_2 = 0.01$
  • $H(\operatorname{UnFair}) = -(0.99 \log_2 0.99 + 0.01 \log_2 0.01)$

    $H(\operatorname{UnFair}) \approx 0.08$ Bit

$\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:

  1. Geben Sie die Entropie $H(S)$ der Trainingsmenge an.
  2. Berechnen Sie $R(H,A)$ (die mittlere Entropie der Trainingsmenge, nachdem Attribut $A$ gesehen wurde) für die einzelnen Attribute.
Quellen

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 (YouTube)
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: Kriterium zur Auswahl von Attributen

  1. Informationsgewinn für alle Attribute berechnen
  2. 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:

  1. Trainieren Sie auf diesem Datensatz einen Klassifikator mit ID3.
  2. Ist Patient F krank? Er hat Husten, aber kein Fieber.
Quellen