Maschinelles Lernen und Datenanalyse

In der Werkstoff- und Prüftechnik

Prof. Dr. Stefan Bosse

Universität Koblenz - FB Informatik - Praktische Informatik

Universität Siegen - FB Maschinenbau / LMW

1 / 67

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

2 / 67

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

Entscheidungsbäume

Einsatzbereiche von Entscheidungsbäumen:

  • Große Datensätze, die komplexe Zusammenhänge beschreiben.
  • Die Beziehung zwischen den Beobachtungen innerhalb der Datensätze müssen nicht linear sein!
  • Die Modellfunktion und deren Parameter sind nicht bekannt.
    • Um den Modellzusammenhang zu beschreiben, wird das Modell trainiert (maschinelles Lernen)
    • Das erfordert, dass die Daten in mindestens einem Trainings- und einem Modelltest-Datensatz geteilt werden. Ab und an wird der Datensatz nicht nur in die zwei genanten, sondern noch in einem weiteren Datensatz, dem Validierungsdatensatz, aufgeteilt.
    • Diese Vorgehensweise ist notwendig, um Modellüberanpassungen zu erkennen!
3 / 67

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

Ein Entscheidungsbaum besteht aus Regeln. Jeder Knoten kann als eine Evaluierungsregel aufgefasst werden.

4 / 67

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

  • Zusammengefasst ausgedrückt:

M(X):X→Y,X={xi},Y={yj}DT=⟨Nx,Ny,E⟩Nx={ni:ni↔xj},Ny={ni:ni↔val(yj)}E={eij:ni↦nj|ϵij} 

5 / 67

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)=⎧⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩xi=v1,⎧⎪⎨⎪⎩xj=v1,val(y)xj=v2,val(y)xj=v3,{..xi=v2,⎧⎪⎨⎪⎩xk=v1,{..xk=v2,{..xk=v3,{..xi=v3,⎧⎪⎨⎪⎩xl=v1,{..xl=v2,{..xl=v3,{..

6 / 67

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.

7 / 67

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

Baumstruktur

Grundlegende Struktur eines Entscheidungbaumes

8 / 67

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?
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!
9 / 67

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

Bevor man das Training startet, insbesondere bei mehrschrittigen Verfahren, kann es hilfreich sein den Fehler für die "Ratewahrscheinlichkeit" gemäß der im Training benutzten Fehlerfunktion (loss) zu berechnen.

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).

10 / 67

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

Training

  • Das Training mit Trainingsdaten Dtrain 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!

11 / 67

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

12 / 67

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

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 und kann die Komplexität des Baumes bestimmen.
13 / 67

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

Das "NP" Problembeispiel

14 k-stelliger Entscheidungsbaum für kategorische Variablen

14 / 67

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

15 / 67

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

16 / 67

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 (Interval Nearest Neighbor oder 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)
17 / 67

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

Bewertung der Qualität eines Modells

  • 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 yp:

H(p,q)=−∑cp(c)log(q(c))p(c)=count(y∣y=c)Nq(c)=count(yp∣yp=c)Nc∈C={U,V,W,..}

18 / 67

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

Bewertung der Qualität eines Modells

  • Logloss, die Abkürzung für logarithmischer Verlust, misst die Genauigkeit eines Klassifikators mit kontinuierlichen Ausgabevariablen, d.h. im normierten 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(y,p)=1NN∑i=1−yilog(pi)−(1−yi)log(1−pi)

19 / 67

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

Bewertung der Qualität eines Modells

  • Mean-Squared Error (MSE) und Root-Mean-Squared-Error (RMSE) bei numerischen Ausgabevariablen (sowohl diskrete als auch regressive Bäume), hier ist yp der vom Modell vorhergesagte Wert, und y0 der bekannte Ground Truth Wert:

rmse(yp,y0)=√1N∑(yp−y0)2

Weitere Informationen und Vertiefung:

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

20 / 67

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
21 / 67

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)=−∑i=1,kpilog2(pi),pi=count(X=ci)|X|,X={c|c∈C}

Alle Werte gleich ⇒ Entropie=0; Alle Werte gleichverteilt ⇒ Entropie=-log2|ci|

22 / 67

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