Maschinelles Lernen und Datenanalyse

In der Mess- und Prüftechnik

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 45

Stefan Bosse - Maschinelles Lernen - 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

2 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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
3 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Entscheidungsbäume

  • Zusammengefasst ausgedrückt:

M(X):XY,X={xi},Y={yj}DT=Nx,Ny,ENx={ni:nixj},Ny={ni:nival(yj)}E={eij:ninj|ϵij} 

4 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Entscheidungsbäume

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

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,{..

5 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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, xv, oder xv 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 xV oder auf ein Intervall [a,b] erfolgen! Wird vor allem bei kategorischen Variablen eingesetzt.

6 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Entscheidungsbäume

Baumstruktur

Grundlegende Struktur eines Entscheidungbaumes

7 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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?
8 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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!
9 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Training

Training

  • Das Training mit Trainingsdaten Dtrain erzeugt den Baum schrittweise:

    • Es werden geeignete Variablen xX 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!

10 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel

Beispiel

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

11 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel

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.
12 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel

Das "NP" Problembeispiel

14 k-stelliger Entscheidungsbaum für kategorische Variablen

13 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel

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

14 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel

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

15 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel

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 (auch 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
16 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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
17 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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|cC}

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

18 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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)=i=1,kpilog2(pi),pi=count(X|X=ciY=y)Ny,Xy={c|cCY=y},C={ci|i=1,2,..,k}

  • C ist die Menge aller unterscheidbaren Werte von X!
19 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - ID3 Verfahren

Beispiel

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(ay=B)=22log(12)22log(12)=0H(by=B)=12log(12)12log(12)=1

20 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - ID3 Verfahren

Informationsgewinn

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

G(Y|X)=E(Y)vVal(X)|(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.

Der Informationsgewinn ist auf Y Verteilung bezogen, nicht wie vorher auf X!

21 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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.
22 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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.

23 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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)vVal(X)|Yv||Y|E(Yv)SI(Y)=cVal(Y)|Yc||Y|log2|Yc||Y|GR=G(Y|X)SI(Y)

24 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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 xsplitX bestimmt (z.B. über Mittelwerte der Intervalle)
25 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Teilung von kategorischen und numerischen Variablen

Vertiefung

  1. Rokach and O. Maimon, Data Mining with Decision Trees - Theory and Applications. World Scientific Publishing, 2015.
26 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Intervallkodierung

Intervallkodierung

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

27 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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
28 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Intervallkategorisierte Entscheidungsbäume (INN/ICE)

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.

    • 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!
29 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Intervallkategorisierte Entscheidungsbäume (INN/ICE)

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

M(X)=⎪ ⎪ ⎪ ⎪⎪ ⎪ ⎪ ⎪xi[v1εi,v1+εi],{xi[v1εi,v1+εi],{xi[vnε,vn+εi],{

Vergleich der verschiedenen Baumarten und Knotenverzweigungen

30 / 45

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?

    • Überschneidungen bedeuten Ununterscheidbarkeit!
31 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Intervallkategorisierte Entscheidungsbäume (INN/ICE)

Inferenz mit NN Suche

  • 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

32 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Random Forest Trees

Random Forest Trees

Konzept und Idee: Mehrere schwache Modelle zu einem starken kombinieren.

  • Multiinstanzmodell
    • Es werden m Entscheidungsbäume DT={dt1,..,dtm} getrennt gelernt und erzeugt
    • "Random": Die Aufteilung der Daten in Teilungsvariablen erfolgt randomisiert!
    • Eingabedaten werden zur Inferenz an alle Teilbäume dtiDT gegeben
    • Alle Ausgabevariablen der Teilbäume werden fusioniert
33 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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)
    • Fusionsmodell und Algorithmus
34 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Random Forest Trees

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

35 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation 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
36 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel

37 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel

Ressourcen

38 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Beispiel

Genauigkeit

39 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Regressionsbäume

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!

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

Ein Regressionsbaum ist ein Hybrid aus Regressionsfunktion und Entscheidungsbaum.

40 / 45

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

    • 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 ...)
41 / 45

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)

42 / 45

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.

43 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Regressionsbäume

Algorithmus

Ziel: Mit jeder Ebene/Knoten die "Unordnung" (Impurity) der Datenverteilung mit Bezug zu der Zielvariable zu reduzieren

  • Es wird wieder die Entropie ε als Maß für die Unordnung herangezogen

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.

44 / 45

Stefan Bosse - Maschinelles Lernen - Klassifikation mit Entscheidungsbäumen - Zusammenfassung

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

    • Eine Attributvariable ist ein Teilungspunkt
  • 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)

45 / 45