Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Entscheidungsbäume
Baumstruktur
Grundlegende Struktur eines Entscheidungbaumes
In der Mess- und Prüftechnik
PD Stefan Bosse
Universität Bremen - FB Mathematik und Informatik
Stefan Bosse - Maschinelles Lernen - 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
Stefan Bosse - Maschinelles Lernen - 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
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Entscheidungsbäume
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}
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Entscheidungsbäume
M(X)=⎧⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩xi=v1,⎧⎪⎨⎪⎩xj=v1,val(yi)xj=v2,val(yi)xj=v3,{..xi=v2,⎧⎪⎨⎪⎩xk=v1,{..xk=v2,{..xk=v3,{..xi=v3,⎧⎪⎨⎪⎩xl=v1,{..xl=v2,{..xl=v3,{..
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Entscheidungsbäume
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.
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Entscheidungsbäume
Grundlegende Struktur eines Entscheidungbaumes
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Entscheidungsbäume
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Entscheidungsbäume
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Training
Das Training mit Trainingsdaten Dtrain erzeugt den Baum schrittweise:
Die Auswahl der Variablen und die Verzweigungsbedingungen können je nach Algorithmus und Baumklasse variieren!
Stefan Bosse - Maschinelles Lernen - 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
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel
Jeder Knoten in einem binären Baum stellt eine lineare Separation des Eingabedatenraums dar.
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel
14
k-stelliger Entscheidungsbaum für kategorische Variablen
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel
www.statistik-dresden.de
Binärer Entscheidungsbaum (Relation und Auswahl) für numerische und kategorische Variablen: Beantwortung "soziologischen Fragen", und nicht Prädiktion
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel
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
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Vergleich ID3 - C4.5
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - ID3 Verfahren
[1] J. R. Quinlan, “Induction of Decision Trees,” in Machine Learning, Kluwer Academic Publishers, Boston, 1986.
E(X)=−∑i=1,kpilog2(pi),pi=count(X=ci)|X|,X={c|c∈C}
Alle Werte glecih ⇒ Entropie=0; Alle Werte gleichverteilt ⇒ Entropie=-log2|ci|
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - ID3 Verfahren
H(X|Y=y)=−∑i=1,kpilog2(pi),pi=count(X|X=ci∧Y=y)Ny,Xy={c|c∈C∧Y=y},C={ci|i=1,2,..,k}
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - ID3 Verfahren
| a | b | y |
|---|---|---|
| u | u | A |
| v | v | A |
| w | u | B |
| w | v | B |
E(a)=−13log(13)−13log(13)−13log(23)=1.5E(b)=−24log(23)−23log(23)=1H(a∣y=B)=−22log(12)−22log(12)=0H(b∣y=B)=−12log(12)−12log(12)=1
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - ID3 Verfahren
G(Y|X)=E(Y)−∑v∈Val(X)|(Y|X=v)||Y|E(Y|X=v)
Der Informationsgewinn ist auf Y Verteilung bezogen, nicht wie vorher auf X!
Stefan Bosse - Maschinelles Lernen - 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 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.Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - C4.5 Verfahren
[1] J. R. Quinlan, "C4.5: Programs For Machine Learning". Morgan Kaufmann, 1988.
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.
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - C4.5 Verfahren
G(Y|X)=E(Y)−∑v∈Val(X)|Yv||Y|E(Yv)SI(Y)=∑c∈Val(Y)−|Yc||Y|log2|Yc||Y|GR=G(Y|X)SI(Y)
Stefan Bosse - Maschinelles Lernen - 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 numerischen Variablen muss ein Wert als Teilungspunkt aus der Werteverteilung bestimmt!
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Teilung von kategorischen und numerischen Variablen
Vertiefung
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Intervallkodierung
Einteilung von kontinuierlichen Werteverteilungen in Intervall und Abbildung auf kategorische (diskrete) Werte
Stefan Bosse - Maschinelles Lernen - 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.
Es gibt keine Universallösung für den Umgang mit ? Werten. Möglichkeiten:
Stefan Bosse - Maschinelles Lernen - 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 in der Soziologie) sind fehlerbehaftet, d.h. es gibt bei jedem x-Wert ein Unsicherheitsintervall [x-δ,x+δ] → Rauschen
Damit können Entscheidungsbäume (anders als Neuronale Netze oder Regressionslerner) nicht umgehen.
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Intervallkategorisierte Entscheidungsbäume (INN/ICE)
M(X)=⎧⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪⎩xi∈[v1−εi,v1+εi],{⋯xi∈[v1−εi,v1+εi],{⋯⋯xi∈[vn−ε,vn+εi],{⋯
Vergleich der verschiedenen Baumarten und Knotenverzweigungen
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Intervallkategorisierte Entscheidungsbäume (INN/ICE)
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?
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Intervallkategorisierte Entscheidungsbäume (INN/ICE)
Jeder Knoten xi hat ausgehende Kanten mit annotierten Intervallen [vj-ε,vj+ε]
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
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Random Forest Trees
Konzept und Idee: Mehrere schwache Modelle zu einem starken kombinieren.
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Random Forest Trees
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Random Forest Trees
Abhishek Sharma, 2020, www.analyticsvidhya.com
Grundprinzip von Multibaumklassifikatoren
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Regressionsbäume
Classification and Regression Tree CART Breiman, Friedman, Olshen, and Stone (1984)
Bisher gaben Entscheidungsbäume diskrete kategorische Symbolwerte oder intervallkodierte numerische Werte aus. Ausgabewerte die nicht in den Trainingsdaten enthalten waren können auch nicht ausgegeben werden. Es gibt keine Inter- und Extrapolation!
Ein Regressionsbaum ist ein Hybrid aus Regressionsfunktion und Entscheidungsbaum.
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - 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.,
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Regressionsbäume
14
CART mit der Zielvariable y:Raucher? und verschiedenen Eingabevariablen (Attributen): Alter (Monate!), Elternstress (Score 0-5)
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - 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.
Ohne auf einem speziellen statistisches Modell zu basieren, enthält CART keine komplexen mathematischen Gleichungen (die das statistische Modell beschreiben). Die Ergebnisse sind leicht zu interpretieren und zu verstehen.
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Regressionsbäume
Ziel: Mit jeder Ebene/Knoten die "Unordnung" (Impurity) der Datenverteilung mit Bezug zu der Zielvariable zu reduzieren
Der Grad der Verringerung der Unordnung, der mit der Partitionierung eines übergeordneten Knotens in zwei untergeordnete Knoten verbunden ist, wird berechnet als [14]:
Δ=ϵ(τ)−ϵ(τL)nl1nl1+nl2−ϵ(τR)nr1nr1+nr2
wobei ε(τ) die Entropie des Elternknoten ist.
Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Zusammenfassung
Entscheidungsbäume sind für die Klassifikation von kategorischen Zielvariablen geeignet
Mit Ausnahme von CART liefern EB nur Werte der Zielvariablen die im Training enthalten waren
Numerische Zielvariablen müssen intervallkodiert werden (mit Ausnahme von CART).
ID3/C4.5 Lerner können numerische und kategorische Eingabevariablen (Attribute) verwenden
Rauschen auf Sensordaten muss durch "Unsicherheitsintervall" und Intervallarithmetik behandelt werden (und bei CART durch Standardabweichung)
Vergleich mit anderen Lernverfahren zeigt gute Ergebnisse (je nach Problem)