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

Maschinelles Lernen und Datenanalyse

In der Soziologie

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 33

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 / 33

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 / 33

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

  • 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 / 33

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 / 33

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, 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 / 33

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

Baumstruktur