PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen ::

Klassifikation und Regression mit Entscheidungsbäumen

Zielvariablen: Primär Kategorische Variablen; Sekundär Numerische Variablen

Eigenschaftsvariablen: Kategorische und Numerische Variablen

Modell: Gerichteter azyklischer Graph (Baumstruktur)

Training und Algorithmen: C4.5, ID3, C5.0, ICE, CART, RF

Klasse: Überwachtes Lernen

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Entscheidungsbäume

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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Entscheidungsbäume

• 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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Entscheidungsbäume

• Entscheidungsbäume können neben einem 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})} \\ {{x_j} = {v_2},val({y})} \\ {{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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Entscheidungsbäume

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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Entscheidungsbäume

Baumstruktur

Grundlegende Struktur eines Entscheidungbaumes

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Entscheidungsbäume

Vorteile

⊕ Entscheidungsbäume sind einfach aufgebaut und können mit einfachen Algorithmen erzeugt werden.
⊕ Entscheidungsbäume als inferiertes 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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Entscheidungsbäume

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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Entscheidungsbäume

Beispiel Regression:

use math
x=[1,2,3,4,5,6,7,8]
y=[1,2,3,4,5,6,7,8]
y.median = fivenum(y)$median
loss2 = sqrt(mean((y-y.median)^2))
>> 2.29

Solange beim oder nach dem Training der fehler/Verlust nicht nennenswert kleiner (mindestens 1/2, besser 1/10) ist kann ist das Modell nicht brauchbar (bei Regressionsmodellen spricht man auch von der Todeslinie wenn das Modell konstant ungefähr den Median ausgibt).

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Training

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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Training

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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Training

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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Training

Das "NP" Problembeispiel

14 k-stelliger Entscheidungsbaum für kategorische Variablen

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Training

Das Titanic Überlebensbeispiel

www.statistik-dresden.de Binärer Entscheidungsbaum (Relation und Auswahl) für numerische und kategorische Variablen: Beantwortung "soziologischen Fragen", und nicht Prädiktion

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Training

Beispiel Materialeigenschaften

100 (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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Training

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.
  • C5.0 Nachfolger von C4.5 mit verbesserten Split und Baumreduzierung
  • INN. Die Eigenkreation (auch ICE, Stefan Bosse, 2016) für numerische unsichere und verrauschte Sensorwerte mit Intervallarithmetik (also im Prinzip Intervallkategorisierung und Kantenbedingungen sind x ∈ [a,b]), basierend auf C4.5 und ID3
  • CART Classification and Regression Tree (kat. und kont. numerische Zielvariablen)

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Training

Bewertung

• Binäre Kreuzentropie bei kategorischen Ausgabevariable(n)

Die Kreuzentropie ist in der Informationstheorie und der mathematischen Statistik ein Maß für die Qualität eines Modells für eine Wahrscheinlichkeitsverteilung. Eine Minimierung der Kreuzentropie in Bezug auf die Modellparameter kommt einer Maximierung der Log-Likelihood-Funktion gleich. Es gilt mit p als Zielwertverteilung von y und q als verteilung der Prädktion y_p:

$${H}{\left({p},{q}\right)}=-\sum_{{c}}{p}{\left({c}\right)}{\log{{\left({q}{\left({c}\right)}\right)}}}\\ {p}{\left({c}\right)}=\frac{{\text{count}{\left({y}{\mid}{y}={c}\right)}}}{{N}}\\ {q}{\left({c}\right)}=\frac{{\text{count}{\left({y}_{{p}}{\mid}{y}_{{p}}={c}\right)}}}{{N}}\\ {c}\in{C}={\left\lbrace{U},{V},{W},..\right\rbrace}$$

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Training

Bewertung

• Logloss, die Abkürzung für logarithmischer Verlust, misst die Genauigkeit eines Klassifikators mit kontinuierlichen Ausgabevariablen, d.h. im Werteintervall [0,1], indem es falsche Klassifizierungen bestraft. Für eine binäre Klassifizierung mit echter Bezeichnung y={0,1} und vorhergesagter Wahrscheinlichkeit p=[0,1] ist der Logloss gegeben durch:

$${L}{\left({y},{p}\right)}=\frac{{1}}{{N}}{\sum_{{{i}={1}}}^{{N}}}-{y}_{{i}}{\log{{\left({p}_{{i}}\right)}}}-{\left({1}-{y}_{{i}}\right)}{\log{{\left({1}-{p}_{{i}}\right)}}}$$

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Training

Bewertung

• MSE/RMSE bei numerischen Ausgabevariablen (sowohl diskrete als auch regressive Bäume), hier ist y_p der vom Modell vorhergesagte Wert, und y₀ der bekannte Ground Truth Wert:

$$\text{rmse}{\left({y}_{{p}},{y}_{{0}}\right)}=\sqrt{{\frac{{1}}{{N}}\sum{\left({y}_{{p}}-{y}_{{0}}\right)}^{{2}}}}$$

Weitere Informationen und Vertiefung:

https://towardsdatascience.com/understanding-binary-cross-entropy-log-loss-a-visual-explanation-a3ac6025181a

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Vergleich ID3 - C4.5

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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ID3 Verfahren

ID3 Verfahren

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

Entropie

• 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(X=c_i)}{|X|},X=\left\{c | c \in C\right\}$$

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ID3 Verfahren

https://towardsdatascience.com/understanding-entropy-the-golden-measurement-of-machine-learning-4ea97c663dc3 Illustration der Bedeutung der Entropie: Entropie hat ihre Wurzeln in der Physik- sie ist ein Maß für Unordnung oder Unvorhersehbarkeit in einem System.

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ID3 Verfahren

Entscheidungsbäume verwenden Entropie für ihre Konstruktion: Um Eingaben so effektiv wie möglich nach einer Reihe von Bedingungen zu einem korrekten Ergebnis (Zielvariable) zu lenken, werden Merkmalteilungen (mit Bedingungen) mit niedrigerer Entropie (höherer Informationsgewinn) höher im Baum platziert.

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ID3 Verfahren

Um die Idee von Bedingungen mit niedriger und hoher Entropie zu veranschaulichen, betrachten wir hypothetische Merkmale mit einer durch Farbe (rot oder blau) markierten Klasse und der durch eine vertikale gestrichelte Linie markierten Teilung.

https://towardsdatascience.com/understanding-entropy-the-golden-measurement-of-machine-learning-4ea97c663dc3 Betrachtet man die Verteilung der Zielvariablen y, dann ergibt sich ein hoher Informationsgewinn bei niedriger Entropie (von y) für eine gute Teilung

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ID3 Verfahren

• Entscheidungsbäume berechnen die Entropie von Merkmalen und ordnen sie so an, dass die Gesamtentropie des Modells minimiert (und der Informationsgewinn maximiert) wird.

• Mathematisch bedeutet dies, dass die Bedingung mit der niedrigsten Entropie oben platziert wird, so dass sie dazu beitragen kann, Knoten darunter zu spalten, um die Entropie zu verringern.

• Informationsgewinn und relative Entropie, die beim Training von Entscheidungsbäumen verwendet werden, sind definiert als der Abstand zwischen zwei Wahrscheinlichkeitsverteilungen p(x) und q(x) (siehe vorherige Abb.).

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ID3 Verfahren

Bedingte Entropie

• Interessant ist die Werteverteilung einer Eingabevariablen X in Bezug auf die Werte (Partitionen) der Zielvariable Y ⇒ Bedingte Entropie

$$H(X|Y=y) = -\sum_{i=1,k}p_i\log_2(p_i),\\ p_i=\frac{count(X|X=c_i\wedge Y=y)}{N_y},\\ X_y=\left\{c | c \in C\wedge Y=y\right\},\\ C=\left\{c_i|i=1,2,..,k\right\}$$

• C ist die Menge aller unterscheidbaren Werte von X!

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ID3 Verfahren

Beispiel

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ID3 Verfahren

Informationsgewinn

• Ausgehend von der bedingten Entropie kann der Informationsgewinn einer Spalte X hinsichtlich der Zielvariablenspalte Y berechnet werden:

$$G(Y|X) = E(Y) - \sum_{v \in Val(X)} \frac{|(Y|X=v)|}{|Y|}E(Y|X=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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Algorithmus

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 Attributvariable 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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: C4.5 Verfahren

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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: C4.5 Verfahren

• 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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Teilung von kategorischen und numerischen Variablen

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 numerischen 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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Teilung von kategorischen und numerischen Variablen

Teilung von numerischen Variablen mit Intervallanalyse

Naiver Ansatz:

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Teilung von kategorischen und numerischen Variablen

Vertiefung

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

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Intervallkodierung

Intervallkodierung

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

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Unvollständige Trainingsdaten

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 Wertes mit einem Standardwert
  • Ersetzen des fehlenden Wertes mit einem probabalistisch über Verteilungshäufigkeiten bestimmten Wert (auch unter Einbeziehung des gesamten Datensamples)
  • Attributvariablen mit fehlenden Werten nicht verwenden

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ICE/INN Intervallkategorisierte Entscheidungsbäume

ICE/INN Intervallkategorisierte Entscheidungsbäume

• 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 in der Soziologie) sind fehlerbehaftet, d.h. es gibt bei jedem x-Wert ein Unsicherheitsintervall [x-δ,x+δ] → Rauschen, ebenso Teilungsintervalle [x₁-δ,x₂+δ]

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

  • Wenn die Teilung 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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ICE/INN Intervallkategorisierte Entscheidungsbäume

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

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

Vergleich der verschiedenen Baumarten und Knotenverzweigungen

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ICE/INN Intervallkategorisierte Entscheidungsbäume

• 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

• Entropie 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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: ICE/INN Intervallkategorisierte Entscheidungsbäume

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 einerseits auch ein Intervall [v-ε,v+ε] gebildet und mit den Kantenintervallen verglichen, andererseits wird das nächstliegende Intervall gesucht

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Gini-Index/Gini-Unreinheit

Gini-Index/Gini-Unreinheit

Die Gini-Unreinheit (Ginit Impurity GI) ist die Wahrscheinlichkeit, ein zufällig ausgewähltes Element im Datensatz falsch zu klassifizieren, wenn es gemäß der Klassenverteilung im Datensatz zufällig annotiert wurde. GI wird berechnet als:

$${G}={\sum_{{{i}={1}}}^{{C}}}​{p}{\left({i}\right)}∗{\left({1}−{p}{\left({i}\right)}\right)}$$

wobei C die Anzahl der Klassen und p(i) die Wahrscheinlichkeit ist, zufällig ein Element der Klasse i auszuwählen.

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Gini-Index/Gini-Unreinheit

Gini-Index/Gini-Unreinheit

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Gini-Index/Gini-Unreinheit

Gini-Index/Gini-Unreinheit

Beispiel

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Random Forest Trees

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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Random Forest Trees

• 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)
  • Maximale Höhe eines Teilsbaumes
  • Fusionsmodell und Algorithmus

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Random Forest Trees

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

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Beispiel

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 - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Beispiel

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Beispiel

Ressourcen

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Beispiel

Genauigkeit

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Regressionsbäume

Regressionsbäume

Classification and Regression Tree CART

• Regressionsbäume können zwar auch nur eine diskrete Menge von Werten ausgeben, die aber nicht unmittelbar in den Trainingsdaten enthalten sein müssen (nur numerische Zielvariablen) und aus einer statistischen Analyse stammen

Breiman, Friedman, Olshen, and Stone (1984)

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Regressionsbäume

Regressionsbäume

• Ein CART gruppiert einzelne Dateninstanzen und Trainingsbeispiele in Gruppen und berechnet statistische Größen der Zielvariable: Mittelwert, Standardabewichung usw.

• Jeder Knoten ist hier auch ein Zielknoten der diese statistischen Informationen der Zielvariablen liefert und kann für die Beantwortung einzelner Fragen verwendet werden d.h.,

  • Der Einfluss von Variablen und deren Wertebereiche auf die Zielvariable ist unmittelbar ablesbar,
  • Pfade entlang des Baumes ergeben Variablenkonditionale (also wenn A und dann B dann ...)

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Regressionsbäume

Regressionsbäume

• Je tiefer ein Knoten sich im Baum befindet, desto geringer sollte die Streuung und Breite der verteilung der Ergebnisvariable sein

• Bei Regressionsbäumen wird i.A. der mittlere Teilungsfehler für einen gegebenen Teilungspunkt berechnet und verwendet (i.a. Binärbaum bei nuemrischen Eingabevariablen)

$$\text{MSE}=\frac{{1}}{{n}}{\sum_{{{i}={1}}}^{{n}}}{\left({Y}_{{i}}-\hat{{Y}}_{{i}}\right)}^{{2}}$$

wobei Y der vorgebenene Trainingswert ist und Y der berechnete (vorhergesagte) Zielvariabenwert ist.

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Regressionsbäume

Regressionsbäume

14 CART mit der Zielvariable y:Raucher? und verschiedenen Eingabevariablen (Attributen): Alter (Monate!), Elternstress (Score 0-5)

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Regressionsbäume

Regressionsbäume

Als eine statistische Methode gruppiert CART Individuen in eine Reihe von sich gegenseitig ausschließenden und repräsentativen Gruppen, die auf starke Zusammenhänge zwischen den unabhängigen Variablen basieren. CART ist eine effektive explorative statistische Technik.

Vertiefung: https://towardsdatascience.com/cart-classification-and-regression-trees-for-clean-but-powerful-models-cc89e60b7a85 https://medium.com/analytics-vidhya/regression-trees-decision-tree-for-regression-machine-learning-e4d7525d8047

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Regressionsbäume

Algorithmus

• Es wird wieder die Entropie ε als Maß für die Unordnung herangezogen (der Zielvariable)

Der Grad der Verringerung der Unordnung, der mit der Partitionierung eines übergeordneten Knotens in zwei untergeordnete Knoten verbunden ist, wird berechnet als [14]:

$$\Delta=\epsilon{\left(\tau\right)}-\epsilon{\left(\tau_{{L}}\right)}\frac{{n}_{{{l}{1}}}}{{{n}_{{{l}{1}}}+{n}_{{{l}{2}}}}}-\epsilon{\left(\tau_{{R}}\right)}\frac{{n}_{{{r}{1}}}}{{{n}_{{{r}{1}}}+{n}_{{{r}{2}}}}}$$

wobei ε(τ) die Entropie des Elternknoten ist.

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Baumkompaktierung

Baumkompaktierung

• Viele Baumstrukturen können nach dem Training vereinfacht werden ⇒ Tree Pruning

  • Dabei können auf gleicher Ebene Teilungsknoten und Blätter zusammengafasst werden (Redundanzen)
  • Aber auch Reduktion ganzer Teilbäume ist möglich (Komplexität)

• Man unterscheidet Pre- und Postkompaktierung

https://www.kdnuggets.com/2022/09/decision-tree-pruning-hows-whys.html

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Baumkompaktierung

Pre-Kompaktierung

Die Vorbeschneidungstechnik von Entscheidungsbäumen besteht darin, die Hyperparameter vor der Trainingspipeline zu optimieren. Es beinhaltet die Heuristik, die als 'frühes Stoppen' bekannt ist und das Wachstum des Entscheidungsbaums stoppt - und verhindert, dass er seine volle Tiefe erreicht.

Es stoppt den Baumbildungsprozess, um zu vermeiden, dass Blätter mit kleinen Proben produziert werden. Während jeder Phase der Aufteilung des Baums wird der Kreuzvalidierungsfehler überwacht. Wenn der Wert des Fehlers nicht mehr abnimmt, stoppen wir das Wachstum des Entscheidungsbaums.

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Baumkompaktierung

Pre-Kompaktierung

Die Hyperparameter, die für ein frühzeitiges Stoppen und Verhindern einer Überanpassung eingestellt werden können, sind:

max_depth, min_samples_leaf und min_samples_split

Dieselben Parameter können auch zum Abstimmen verwendet werden, um ein robustes Modell zu erhalten. Sie sollten jedoch vorsichtig sein, da ein frühzeitiges Anhalten auch zu einer Unteranpassung führen kann.

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Baumkompaktierung

Post-Kompaktierung

Post-Pruning bewirkt das Gegenteil von Pre-Pruning und ermöglicht es dem Entscheidungsbaummodell, seine volle Tiefe zu erreichen. Sobald das Modell seine volle Tiefe erreicht hat, werden Äste entfernt, um eine Überanpassung des Modells zu verhindern.

Der Algorithmus partitioniert die Daten weiterhin in kleinere Teilmengen, bis die endgültigen erzeugten Teilmengen in Bezug auf die Ergebnisvariable ähnlich sind. Wenn jedoch ein neuer Datenpunkt eingeführt wird, der sich von den gelernten Daten unterscheidet, wird er möglicherweise nicht gut vorhergesagt.

• "Cost Complexity Pruning" ist eine gängige parametrisierbare Methode um die Komplexität von Bäumen iterativ zu reduzieren

• C4.5/ID3 bieten kaum eingebaute Möglichkeiten die Komplexität und Redundanzen zu reduzieren

• C5.0 bietet Kompaktierung zur Trainingszeit

• ICE kann Blattknoten zusammenfassen (mit fusionierten Intervallen)

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Zusammenfassung

Zusammenfassung

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: C5.0 Verfahren

C5.0 Verfahren

• Erhältlich in R https://cran.r-project.org/web/packages/C50/vignettes/C5.0.html
• Einzelheiten: https://www.geeksforgeeks.org/c5-0-algorithm-of-decision-tree/

Schlüsselkonzepte des C5.0-Algorithmus

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: C5.0 Verfahren

C5.0 Verfahren

Pruning

Winnowing

PD Stefan Bosse - Automatische Schadensdiagnostik - Modul D Klassifikation und Regression mit Entscheidungsbäumen :: Zusammenfassung

Zusammenfassung