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

Maschinelles Lernen und Datenanalyse

In der Mess- und Prüftechnik

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 37

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

2 / 37

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
3 / 37

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

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

4 / 37

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)=⎧⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩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 / 37

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 b