PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Klassifikation mit Entscheidungsbäumen

Zielvariablen: Kategorische Variablen

Eigenschaftsvariablen: Kategorische und Numerische Variablen

Modell: Gerichteter azyklischer Graph (Baumstruktur)

Training und Algorithmen: C4.5, ID3, INN

Klasse: Überwachtes Lernen

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Entscheidungsbäume

• Ein Entscheidungsbaum ist ein gerichteter azyklischer Graph bestehend aus einer Menge von Knoten N die mit den Eingabevariablen x verknüpft sind und Kanten E die die Knoten verbinden

• Die Endknoten sind Blätter und enthalten Werte der Zielvariablen y(daher kann y nur eine kategorische Variable sein, oder eine intervallkategorisierte)

• Die Kanten bestimmen die Evaluierung des Entscheidungsbaum beginnend von dem Wurzelknoten bis zu einem Blattknoten

  • Jede Kante hat eine Evaluierungsbedingung ε(x) der Variable des ausgehenden Knotens x

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

• Zusammengefasst ausgedrückt:

$$\begin{gathered} M(X):X \to Y,X = \{ {x_i}\} ,Y = \{ {y_j}\} \hfill \\ DT = \left\langle {{N_x},{N_y},E} \right\rangle \hfill \\ {N_x} = \{ {n_i}:{n_i} \leftrightarrow {x_j}\} ,{N_y} = \{ {n_i}:{n_i} \leftrightarrow val({y_j})\} \hfill \\ E = \{ {e_{ij}}:{n_i} \mapsto {n_j} | \epsilon_{ij} \} \hfill \ \end{gathered}$$

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

• Entscheidungsbäume können neben dem Graphen auch funktional dargestellt werden:

$$M(X) = \left\{ {\begin{array}{_{20}{c}} {{x_i} = {v_1},\left\{ {\begin{array}{_{20}{c}} {{x_j} = {v_1},val({y_i})} \\ {{x_j} = {v_2},val({y_i})} \\ {{x_j} = {v_3},\left\{ {..} \right.} \end{array}} \right.} \\ {{x_i} = {v_2},\left\{ {\begin{array}{_{20}{c}} {{x_k} = {v_1},\left\{ {..} \right.} \\ {{x_k} = {v_2},\left\{ {..} \right.} \\ {{x_k} = {v_3},\left\{ {..} \right.} \end{array}} \right.} \\ {{x_i} = {v_3},\left\{ {\begin{array}{_{20}{c}} {{x_l} = {v_1},\left\{ {..} \right.} \\ {{x_l} = {v_2},\left\{ {..} \right.} \\ {{x_l} = {v_3},\left\{ {..} \right.} \end{array}} \right.} \end{array}} \right.$$

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Baumklassen

Man unterscheidet:

• Binäre Bäume. Jeder Knoten hat genau (oder maximal) zwei ausgehende Kanten (Verzweigungen). Der Test der Variable x kann daher nur x < v, x > v, x ≥ v, oder x ≤ v sein! Wird vor allem bei numerischen Variablen eingesetzt.

• Bereichs- und Mehrfachbäume. Jeder Knoten hat 1..k ausgehende Kanten (Knotengrad k). Der Test der Variable x kann auf einen bestimmten Wert x ∈ V oder auf ein Intervall [a,b] erfolgen! Wird vor allem bei kategorischen Variablen eingesetzt.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Baumstruktur

Grundlegende Struktur eines Entscheidungbaumes

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Vorteile

⊕ Entscheidungsbäume sind einfach aufgebaut und können mit einfachen Algorithmen erzeugt werden.
⊕ Entscheidungsbäume als inferriertes Modell erlauben eine Erklärbarkeit des Modells, also die Antwort auf die Frage wie sich ein y aus einem x ergibt.
⊕ Weiterhin ist eine Ableitung eines inversen Problems möglich, d.h. welche Werte x für gegebenes y sind möglich?

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Nachteile

⊗ Entscheidungsbäume können schnell spezialisieren, d.h. es fehlt an Generalisierung.
⊗ Theoretisch kann mit einem Entscheidungsbaum jede Trainingsdatentabelle mit einer Trefferquote von 100% abgebildet werden. Der Test mit nicht trainierten Daten ergibt aber Prädiktion in der Größenordnung der Ratewahrscheinlichkeit!

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Training

• Das Training mit Trainingsdaten D_train erzeugt den Baum schrittweise:

  • Es werden geeignete Variablen x ∈ X ausgewählt die einen Knoten im Baum erzeugen
  • Jeder hinzugefügte Knoten erzeugt neue Teilbäume (durch Verzweigungen)
  • Die Verzweigungsbedingungen ε (Kanten) werden ebenfalls vom Trainer anhand der Werte der Variable x in Abhängigkeit von der Zielvariablen y gewählt/berechnet.

• Die Auswahl der Variablen und die Verzweigungsbedingungen können je nach Algorithmus und Baumklasse variieren!

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Beispiel

10 Schrittweise Erzeugung des Entscheidungsbaums aus den Eingabedaten (a) erst mit einer Variable (b,c), dann mit zwei (d) unter Beachtung des Klassifikationsfehlers

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Jeder Knoten in einem binären Baum stellt eine lineare Separation des Eingabedatenraums dar.

Probleme bei Mehrbereichsbäumen

• Wenn die Wertemenge val(x) groß ist gibt es entsprechend auch viele Verzweigungen im Baum!
  • Die Größe des Baums wächst an (Speicher)
  • Die Rechenzeit für das Training (Induktion) aber auch die Anwendung (Inferenz, Deduktion) wächst
  • Die Entropie kann als Maß der Varianz der Wertemenge gesehen werden.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Das "NP" Problembeispiel

14 k-stelliger Entscheidungsbaum für kategorische Variablen

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Beispiel Materialeigenschaften

15 (Links) Entscheidungsbaum für die Vorhersage von Reibungskoeffizienten von Materialien auf der Grundlage von sechs grundlegenden Materialmerkmalen (Rechts) Vergleich der vorhergesagten und experimentellen Reibungskoeffizienten

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Trainingsalgorithmen

• Es gibt verschiedene Trainingsverfahren (für verschiedene Baumklassen):
  • ID3. Der Klassiker (Iterative DiChaudomiser 3, Ross Quinlan, 1975-1986) für kategorische Variablen (k-stelliger Baum)
  • C4.5. Der Klassiker (Ross Quinlan 1988-1993) für numerische (und kategorische) Variablen (Binär- und k-stelliger Baum) als Erweiterung des ID3 Verfahrens.
  • INN. Die Eigenkreation (ICE, Stefan Bosse, 2016) für numerische Werte mit Intervallarithmetik für unsichere verrauschte Sensorwerte (also im Prinzip mit Intervallkategorisierung und Kantenbedingungen sind x ∈ [a,b]), basierend auf C4.5 und ID3

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Vergleich ID3 - C4.5

• Der ID3-Algorithmus wählt das beste Attribut basierend auf dem Konzept der Entropie und dem Informationsgewinn für die Entwicklung des Baumes.
• Der C4.5-Algorithmus verhält sich ähnlich wie ID3, verbessert jedoch einige ID3-Verhaltensweisen:
  • Möglichkeit, numerische (kont.) Daten zu verarbeiten.
  • Verarbeitung unbekannter (fehlender) Werte
  • Möglichkeit, Attribute mit unterschiedlichen Gewichten zu verwenden.
  • Beschneiden des Baumes nach der Erstellung (Modellkompaktierung).
  • Vorhersage der Fehler
  • Hervorhebung und Extraktion von Teilbäumen

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

ID3 Verfahren

[1] J. R. Quinlan, “Induction of Decision Trees,” in Machine Learning, Kluwer Academic Publishers, Boston, 1986.

• Ausgangspunkt für die Konstruktion des Entscheidungsbaums ist die (Shannon) Entropie einer Spalte X der Datentabelle (mit der Variable x):

$$E(X) = -\sum_{i=1,k}p_i\log_2(p_i),p_i=\frac{count(c_i,X)}{N},X=\left\{c | c \in C\right\}$$

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

• Dann der Informationsgewinn einer Spalte X hinsichtlich der Zielvariablenspalte Y:

$$G(Y|X) = E(Y) - \sum_{v \in Val(X)} \frac{|Y_v|}{|Y|}E(Y_v)$$

• Der Informationsgewinn, der durch Auswahl des Attributs x und der Spalte X erzielt wird, errechnet sich dann als Differenz der Entropie von Y und der erwarteten/durchschnittlichen Entropie von Y bei Fixierung von x.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Algorithmus

0. Starte mit leeren Baum, allen Eingansattributen X, der Zielvariablen Y,
   und der vollständigen Datentabelle D(X,Y).
1. Berechne den Informationsgewinn für jede Attributevariable x ∈ X.
2. Wenn nicht alle Zeilen zum selben Zielvariablenwert gehören, 
   wird der Datensatz D in Teilmengen D'xbest,v1, D'xbest,v2, usw. 
   aufgeteilt für das Attribut xbest ∈ X mit dem größten Informationsgewinn.
3. Es wird ein Knoten mit der Attributevariable xbest erstellt.
4. Wenn alle Zeilen zur selben Klasse gehören, wird ein Blattknoten 
   mit dem Wert der Zielvariable erstellt.
5. Wiederholung von 1-4 für die verbleibenden Attribute X'=X / xbest,
   allen Teilbäumen (Verzweigungen von aktuellen Knoten) mit jeweiligen D',
   bis alle Attribute verwendet wurden,
   oder der Entscheidungsbaum alle Blattknoten enthält.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

C4.5 Verfahren

[1] J. R. Quinlan, "C4.5: Programs For Machine Learning". Morgan Kaufmann, 1988.

• Wie ID3 werden die Daten und Attribute an jedem Knoten des Baums bewertet um das beste Teilungsattribut zu bestimmen.

• Aber C4.5 verwendet die Methode der "gain ratio impurity", um das Teilungsattribut zu bewerten (Quinlan, 1993).

• Entscheidungsbäume werden in C4.5 mithilfe eines Satzes von Trainingsdaten oder Datensätzen wie in ID3 erstellt.

• An jedem Knoten des Baums wählt C4.5 ein Attribut der Daten aus, das seinen Satz von Samples am effektivsten in Teilmengen aufteilt, die in der einen oder anderen Klasse verteilt sind.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

• Das Kriterium ist der normalisierte Informationsgewinn:
  • Verhältnis des Informationsgewinns G (Gain) zu einer sog. Teilungsqualität (Split Info SI), die sich aus der Zielvariable Y zum Aufteilen nach den Y Werten der Daten ergibt.
  • Das Attribut mit dem höchsten Verhältnis GR (Gain Ratio) wird ausgewählt, um die Entscheidung für die Teilung zu treffen.

$$G(Y|X) = E(Y) - \sum_{v \in Val(X)} \frac{|Y_v|}{|Y|}E(Y_v)\\ SI(Y) = \sum\limits_{c \in Val(Y)}^{} { - \frac{{|{Y_c}|}}{{|Y|}}} {\log _{_2}}\frac{{|{Y_c}|}}{{|Y|}}\\ GR=\frac{G(Y|X)}{SI(Y)}$$

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Teilung von kategorischen und numerischen Variablen

• Bei kategorischen Variablen bestimmen die Werte Val(X) einer Spalte der Datentabelle einer Variablen x die Aufteilung eines Entscheidungbaums (Partitionierung).

• Bei nuemrischen Variablen muss ein Wert als Teilungspunkt aus der Werteverteilung bestimmt!

  • Nicht trivial; Welches Kriterium?
  • Intervallkategorisierung und Wertepartitionierung kann helfen!
  • D.h. mit intervallkategorisierten diskrete Werter wird die Spalte X entsprechend der Zielvariable Y partitioniert.
  • Und diese Partitionen werden bewertet und der Teilungspunkt x_split ∈ X bestimmt (z.B. über Mittelwerte der Intervalle)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Vertiefung

L. Rokach and O. Maimon, Data Mining with Decision Trees - Theory and Applications. World Scientific Publishing, 2015.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Intervallkodierung

Einteilung von kontinuierlichen Werteverteilungen in Intervall und Abbildung auf kategorische (diskrete) Werte

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Unvollständige Trainingsdaten

• Es kommt vor allem in der Soziologie aber auch in der Mess- und Prüftechnik vor, dass nicht alle Werte der Attributvariablen X für alle Trainingssätze bekannt sind.

  • Die Behandlung fehlender Attributwerte in den Zeilen der Datentabellen ist schwierig

• Es gibt keine Universallösung für den Umgang mit ? Werten. Möglichkeiten:

  • Ersetzen des fehlenden Werts mit einem Standardwert
  • Ersetzen des fehlenden Werts mit einem probalistisch über Verzeilungshäufigkeiten bestimmten Wert (auch unter Einbeziehung des gesamten Datensamples)
  • Attributevariablen mit fehlenden Werten nicht verwenden

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Intervallkategorisierte Entscheidungsbäume (INN/ICE)

• Bisherige Entscheidungsbäume (C4.5/ID3) wurden entweder mit einer diskreten Anzahl von kategorischen Werten verzweigt oder mittels binärer Relationen!

• Aber Sensoren (sowohl in der Mess-und Prüftechnik als auch ind er Soziologie) sind fehlerbehaftet, d.h. es gibt bei jedem x-Wert ein Unsicherheitsintervall [x-δ,x+δ] → Rauschen

• Damit können Entscheidngsbäume (anders als Neuronale Netze oder Regressionslerner) nicht umgehen.

  • Wenn der Split mit x<50 und x≥50 an einem Knoten mit x erfolgt würde bei Werten um 50 und überlagerten Rauschen ein Entscheidungsproblem entstehen!

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

• Lösung: k-stellige Knoten mit Intervallverzweigungen, also:

$$M(X) = \left\{ {\begin{array}{*{20}{c}} {{x_i} \in [{v_1} - \varepsilon_i ,{v_1} + \varepsilon_i ],\left\{ \cdots \right.} \\ {{x_i} \in [{v_1} - \varepsilon_i ,{v_1} + \varepsilon_i ],\left\{ \cdots \right.} \\ \cdots \\ {{x_i} \in [{v_n} - \varepsilon_ ,{v_n} + \varepsilon_i ],\left\{ \cdots \right.} \end{array}} \right.$$

Vergleich der verschiedenen Baumarten und Knotenverzweigungen

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

• Bei der Konstruktion des Entscheidungsbaums werden wieder nach Informationsgewinn bzw. Gewinnverhältnis Attributvariablen und Spalten der Datentabelle ausgewählt.

• Die numerischen Werte werden sowohl beim Training als auch bei der Inferenz durch Intervalle ersetzt → Ersetzung von diskreter mit Intervallarithmetik

• Entropien usw. werden durch kategorisierte Intervalle bestimmt

• Das große Problem: Für jede Variable muss ein ε abgeschätzt werden → Statistisches Modell erforderlich.

• Und was bedeuten jetzt überschneidende Intervalle?

  • Überschneidungen bedeuten Ununterscheidbarkeit!

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Inferenz mit NN Suche

• Jeder Knoten x_i hat ausgehende Kanten mit annotierten Intervallen [v_j-ε,v_j+ε]

• Bei einem neuen zu testenden Variablenwert v wird einseits auch ein Intervall [v-ε,v+ε] gebildet und mit den Kantenintervallen verglichen, andererseits wird das nächstliegende Intervall gesucht

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Random Forest Trees

• Multiinstanzmodell
  • Es werden m Entscheidungsbäume DT={dt₁,..,dt_m} getrennt gelernt und erzeugt
  • "Random": Die Aufteilung der Daten in Teilungsvariablen erfolgt randomisiert!
  • Eingabedaten werden zur Inferenz an alle Teilbäume dt_i ∈ DT gegeben
  • Alle Ausgabevariablen der Teilbäume werden fusioniert

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

• Fusion:
  • Mittelwert (bei intervallkodierten oder intervallskalierbaren kat. Zielvariablen durch Dekodierung in numerische Werte)
  • Mehrheitsentscheid
  • Konsensfindung (Verhandlung)

• Parametersatz:
  • Stelligkeit eines Knotens (Anzahl der ausgehenden Kanten)
  • Anzahl der Teilbäume
  • Partitionierung des Eingaberaums (d.h. ein bestimmter Baum verwendet nur eine Teilmenge der Spalten aus D)
  • Fusionsmodell und Algorithmus

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Abhishek Sharma, 2020, www.analyticsvidhya.com Grundprinzip von Multibaumklassifikatoren

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Beispiel

Experiment

• Sensornetzwerk von (3 × 4) Dehnungssensoren
• Stimulus: Bauteilschwingung
• Varianz: Bauteilschäden (Defekte)
• Zielvariable: Schadensklassifikation (9 Positionen)
• Merkmalsvektor: Downgesampletes zeitaufeglöstes Sensorsignal einer

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Ressourcen

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Genauigkeit

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul D: Klassifikation mit Entscheidungsbäumen

Zusammenfassung

• Entscheidungsbäume sind für die Klassifikation von kategorischen Zielvariablen geeignet

• Numerische Zielvariablen müssen intervallkodiert werden.

• ID3/C4.5 Lerner können numerische und kategorische Eingabevariablen (Attribute) verwenden

  • Ein Attributariable ist ein Teilungspunkt

• Rauschen auf Sensordaten muss durch "Unsicherheitsintervall" und Intervallarithmetik behandelt werden

• Vergleich mit anderen Lernverfahren zeigt gute Ergebnisse (je nach Problem)