Entscheidungsbäume lernen

11. Entscheidungsbäume lernen#

11.1. Einführung#

Zur Einführung in das Thema “Entscheidungsbäume lernen” kannst du dir die folgende Präsentation ansehen. Klicke dazu auf das Bild oder diesen Link.

11.2. Gini-Unreinheit und gewichtete Gini-Unreinheit#

Die folgenden Formeln findest du auch in Abschnitt 6.2 der Formelsammlung.

11.2.1. Gini-Unreinheit#

Für eine (ausgewählte) Menge von Datensätzen \(D\) und einem Ziel-Feature \(Z\) mit \(k\) möglichen Ausprägungen (Klassen) ist die Gini-Unreinheit (auch: Gini-Koeffizient, Gini-Index, Gini Impurity) wie folgt definiert:

\[ Gini(D) = 1 - \sum_{i=1}^{k} (p_i)^2 \]

wobei die \(p_i\) die relativen Häufigkeiten der Klassen sind.

Beispiel: Wir betrachten eine Menge \(D\) von 31 Datensätzen, die zu drei möglichen Klassen (A, B oder C) gehören. Dabei gilt:

  • 10 Datensätze gehören zur Klasse A

  • 8 Datensätze gehören zur Klasse B

  • 13 Datensätze gehören zur Klasse C

Weil wir insgesamt 31 Datensätze haben, gilt: Die relative Häufigkeit der Klasse A ist \(\frac{10}{31}\), die relative Häufigkeit der Klasse B ist \(\frac{8}{31}\) und die relative Häufigkeit der Klasse C ist \(\frac{13}{31}\).

Für die Gini-Unreinheit ergibt sich in diesem konkreten Beispiel:

\[ Gini(D) = 1 - \left[ \left(\frac{10}{31}\right)^2 + \left(\frac{8}{31}\right)^2 + \left(\frac{13}{31}\right)^2 \right] \]

11.2.2. Gewichtete Gini-Unreinheit#

Wir nutzen die Gini-Unreinheit, um zu bewerten, wie gut ein Feauture die Datenmenge \(D\) in Untergruppen aufteilt. Denn genau das macht ein Entscheidungsbaum: Durch “Abfragen” der Werte eines Features wird die Datenmenge in Untergruppen aufgeteilt - die dann hoffentlich homogener sind als die ursprüngliche Datenmenge und sich daher besser klassifizieren lassen.

Dazu benötigen wir ein Maß, das die Gini-Unreinheit der Untergruppen berücksichtigt. Dies ist die gewichtete Gini-Unreinheit.

Mit \(Gini(F=v)\) bezeichnen wir die (ungewichtete) Gini-Unreinheit der Auswahl von Datensätzen, bei denen das Merkmal/Feature \(F\) den Wert \(v\) hat. Für jeden möglichen Wert \(v\) des Features \(F\) berechnen wir die Gini-Unreinheit \(Gini(F=v)\) wie oben beschrieben. Außerdem bestimmen wir die relative Häufigkeit \(p_v\) der Datensätze, bei denen das Merkmal/Feature \(F\) den Wert \(v\) hat.

Diese Werte verknüpfen wir zur gewichteten Gini-Unreinheit \(Gini(F)\). Diese beschreibt, grob gesagt, die durchschnittliche Gini-Unreinheit der Untergruppen. Sie wird wie folgt berechnet:

\[ Gini(F) = \sum_{v} p_v \cdot Gini(F=v) \]

Das bedeutet: Jede Gini-Unreinheit \(Gini(F=v)\) wird mit der relativen Häufigkeit \(p_v\) gewichtet und die gewichteten Gini-Unreinheiten werden summiert. (Das ist ganz ähnlich wie bei der Berechnung eines Durchschnitts oder eines Erwartungswerts.)

Beispiel: Wir betrachten wieder die Menge \(D\) von 31 Datensätzen, die zu drei möglichen Klassen (A, B oder C) gehören. Nehmen wir an, es gibt ein Feature \(F\), das zwei mögliche Werte hat: ja und nein. Wir berechnen die gewichtete Gini-Unreinheit \(Gini(F)\) für dieses Feature.

Angenommen, die Datensätze verteilen sich wie folgt auf die Werte des Features \(F\):

  • 17 Datensätze haben beim Feature \(F\) den Wert ja

    • davon gehören 5 zur Klasse A, 6 zur Klasse B und 6 zur Klasse C

  • 14 Datensätze haben beim Feature \(F\) den Wert nein

    • davon gehören 2 zur Klasse A, 4 zur Klasse B und 8 zur Klasse C

Aus diesen Werten ergibt sich mit der im vorigen Absatz beschriebenen Formel für die ungewichtete Gini-Unreinheit:

\[ Gini(F=ja) = 1 - \left[ \left(\frac{5}{17}\right)^2 + \left(\frac{6}{17}\right)^2 + \left(\frac{6}{17}\right)^2 \right] \]

und

\[ Gini(F=nein) = 1 - \left[ \left(\frac{2}{14}\right)^2 + \left(\frac{4}{14}\right)^2 + \left(\frac{8}{14}\right)^2 \right] \]

Um die gewichtete Gini-Unreinheit \(Gini(F)\) zu berechnen, müssen wir nun noch die Anteile \(Gini(F=ja)\) und \(Gini(F=nein)\) berücksichtigen. D.h. je häufiger z.B. der Wert ja vorkommt, desto stärker fließt die Gini-Unreinheit \(Gini(F=ja)\) in die gewichtete Gini-Unreinheit \(Gini(F)\) ein. Für unser Beispiel sieht die Formel für die gewichtete Gini-Unreinheit \(Gini(F)\) dann so aus:

\[ Gini(F) = \frac{17}{31} \cdot Gini(F=ja) + \frac{14}{31} \cdot Gini(F=nein) \]

11.3. Übung: Beratung beim Smartphone-Kauf#

Lade dir dieses Aufgabenblatt herunter und bearbeite es. Die Anweisungen findest du auf dem Arbeitsblatt. Viel Erfolg 💪

Hier noch einmal die Daten vom Aufgabenblatt:

Budget

Akkulaufzeit

Kamera

Speicher

Empfehlung

niedrig

lang

mittel

groß

Modell A

hoch

mittel

wichtig

groß

Modell B

mittel

lang

mittel

groß

Modell C

niedrig

kurz

egal

klein

Modell A

hoch

lang

wichtig

groß

Modell B

mittel

mittel

mittel

klein

Modell C

niedrig

lang

egal

klein

Modell A

hoch

mittel

mittel

groß

Modell B

mittel

lang

wichtig

groß

Modell C

niedrig

kurz

egal

klein

Modell A

mittel

mittel

wichtig

groß

Modell C

niedrig

lang

mittel

groß

Modell C

hoch

mittel

wichtig

groß

Modell B

niedrig

lang

wichtig

klein

Modell B

hoch

lang

mittel

klein

Modell B

mittel

lang

wichtig

klein

Modell B

niedrig

lang

wichtig

groß

Modell C

hoch

kurz

mittel

groß

Modell C

mittel

kurz

egal

groß

Modell A

11.4. Ausführliche Musterlösung#

Diese Musterlösung entspricht inhaltlich dem, was du in der Klausur und im Abitur schreiben solltest. Manche Erklärungen sind etwas ausführlicher als unbedingt nötig, aber so verstehst du hoffentlich die Zusammenhänge besser.

11.4.1. Gini-Unreinheit der gesamten Tabelle#

Die Tabelle enthält insg. 19 Datensätze. Wir wollen wissen, wie “unrein” die Tabelle bezüglich des Zielmerkmals Empfehlung ist. Dazu zählen wir die Häufigkeiten der drei möglichen Werte (Klassen) von Empfehlung:

“Modell A” wird 5-mal empfohlen, “Modell B” und “Modell C” je 7-mal. Es ergibt sich also in diese Fall folgende Formel für die Gini-Unreinheit:

\[ Gini(Empfehlung) = 1 - \left[ \left(\frac{5}{19} \right)^2 + \left(\frac{7}{19} \right)^2 + \left(\frac{7}{19} \right)^2\right] = 0.659 \]

11.4.2. Gewichtete Gini-Unreinheit für das Feature Budget#

Weil es für das Feature Budget drei mögliche Werte gibt (niedrig, mittel, hoch), teilen wir die Datensätze entsprechend auf. Für jede Aufteilung berechnen wir

  1. die relative Häufigkeit der Datensätze mit dem jeweiligen Wert von Budget

  2. die (ungewichtete) Gini-Unreinheit für diese Aufteilung

  • 7 von 19 Datensätzen haben beim Merkmal Budget den Wert niedrig → Relative Häufigkeit \(p_{niedrig} = \frac{7}{19}\):

    • Aus diesen 7 wird 4-mal Modell A empfohlen, 1-mal Modell B und 2-mal Modell C. Es ergibt sich also:

    \[ Gini(Budget=niedrig) = 1 - \left[ \left(\frac{4}{7}\right)^2 + \left(\frac{1}{7}\right)^2 + \left(\frac{2}{7}\right)^2\right] = \frac{4}{7} = 0.571 \]

  • 6 von 19 Datensätzen haben beim Merkmal Budget den Wert mittel → Relative Häufigkeit \(p_{mittel} = \frac{6}{19}\):

    • Aus diesen 6 wird 1-mal Modell A empfohlen, 1-mal Modell B und 4-mal Modell C. Es ergibt sich also:

    \[ Gini(Budget=mittel) = 1 - \left[ \left(\frac{1}{6}\right)^2 + \left(\frac{1}{6}\right)^2 + \left(\frac{2}{3}\right)^2\right] = \frac{1}{2} = 0.5 \]

  • 6 von 19 Datensätzen haben beim Merkmal Budget den Wert hoch → Relative Häufigkeit \(p_{hoch} = \frac{6}{19}\):

    • Aus diesen 6 wird 0-mal Modell A empfohlen, 5-mal Modell B und 1-mal Modell C. Es ergibt sich also:

    \[ Gini(Budget=hoch) = 1 - \left[ \left(\frac{0}{6}\right)^2 + \left(\frac{5}{6}\right)^2 + \left(\frac{1}{6}\right)^2\right] = \frac{5}{18} = 0.278 \]

Die gewichtete Gini-Unreinheit für das Feature Budget ergibt sich dann aus der Summe der gewichteten Gini-Unreinheiten:

\[ Gini(Budget) = \frac{7}{19} \cdot 0.571 + \frac{6}{19} \cdot 0.5 + \frac{6}{19} \cdot 0.278 = 0.456 \]

11.4.3. Auswahl des besten Features#

Die gewichteten Gini-Unreinheiten für die Features Budget, Akkulaufzeit, Kamera und Speicher sind:

  • Budget: 0,456 (s.o.)

  • Akkulaufzeit: 0,542

  • Kamera: 0,408

  • Speicher: 0,612

Das Feature Kamera hat die geringste gewichtete Gini-Unreinheit und ist daher das beste Feature für die erste Entscheidung im Entscheidungsbaum.

11.4.4. Der Entscheidungsbaum nach dem ersten Schritt#

Der Entscheidungsbaum beginnt also mit der Frage nach dem Feature Kamera. Da dieses Merkmal drei mögliche Werte hat (mittel, wichtig, egal), teilen wir die Datensätze entsprechend auf.

../_images/entscheidungsbaum_tiefe_1_ohne_endknoten.svg

11.4.5. Daten, mit denen weitergearbeitet wird#

Die Datensätze, die beim Feature Kamera den Wert wichtig haben, sind:

Budget

Akkulaufzeit

Kamera

Speicher

Empfehlung

hoch

mittel

wichtig

groß

Modell B

hoch

lang

wichtig

groß

Modell B

mittel

lang

wichtig

groß

Modell C

mittel

mittel

wichtig

groß

Modell C

hoch

mittel

wichtig

groß

Modell B

niedrig

lang

wichtig

klein

Modell B

mittel

lang

wichtig

klein

Modell B

niedrig

lang

wichtig

groß

Modell C

Der Teil des Baums unterhalb des Knotens Kamera=wichtig muss also nur noch mit diesen Datensätzen arbeiten. Das Feature Kamera wird dafür nicht mehr benötigt (weil alle Datensätze sowieso denselben Wert haben). Es bleiben also noch die Features Budget, Akkulaufzeit und Speicher.

Wir versuchen ohne zu rechnen abzuschätzen, welche Features am besten dazu geeignet sind, das Zielmerkmal Empfehlung zu klassifizieren:

  • Budget: Bei hohem Budget wird immer Modell B empfohlen, bei mittlerem Budget in 2 von 3 Fällen Modell C und bei niedrigem Budget in einem der beiden Fälle Modell B, im anderen Modell C. Das Feature Budget scheint insgesamt ganz gut geeignet, um die Empfehlung zu bestimmen.

  • Akkulaufzeit: Wenn eine lange Akkulaufzeit wichtig ist, wird in 3 von 5 Fällen Modell B empfohlen, in den anderen beiden Fällen Modell C. Bei mittlerer Akkulaufzeit wird in 2 von 3 Fällen Modell C empfohlen, in einem Fall Modell B. (Kurze Akkulaufzeit kommt schon nicht mehr vor.) Das Feature Akkulaufzeit scheint nicht besonders aussagekräftig zu sein.

  • Speicher: Wenn der Wunsch nach großem Speicherplatz besteht, wird in 3 von 6 Fällen Modell C empfohlen, in den anderen 3 Fällen Modell B. Das ist nicht sehr hilfreich. Bei kleinem Speicherplatz wird zwar in beiden Fällen Modell B empfohlen, da aber die meisten Datensätze großen Speicherplatz haben, ist das Feature Speicher auch nicht besonders aussagekräftig.

Intuitiv scheint also das Feature Budget am besten geeignet, um die Empfehlung zu bestimmen. Wir berechnen trotzdem noch die gewichteten Gini-Unreinheiten, um sicher zu gehen. Es ergibt sich:

  • Gini(Budget) = \(0,292\)

  • Gini(Akkulaufzeit) = \(0,467\)

  • Gini(Speicher) = \(0,375\)

Das passt einigermaßen zu unserer Einschätzung. Das Feature Budget ist also das beste für den nächsten Schritt im Entscheidungsbaum.

11.4.6. Fertiger Entscheidungsbaum (Tiefe 2)#

../_images/entscheidungsbaum_tiefe_2.svg

Achtung: Die Werte in den Endknoten sind die häufigsten Empfehlungen in den jeweiligen Datensätzen. Das bedeutet nicht, dass die Empfehlung immer so ausfällt. Es ist nur die häufigste Empfehlung in den jeweiligen Datensätzen. Um zu überprüfen, wie gut der Entscheidungsbaum die Trainingsdaten klassifiziert, können wir die Genauigkeit berechnen. Dazu zählen wir die Anzahl der Datensätze, bei denen die Empfehlung des Entscheidungsbaums mit der tatsächlichen Empfehlung übereinstimmt und teilen durch die Gesamtanzahl der Datensätze.

Nr

Zielwert

Vorhersage

korrekt?

0

Modell A

Modell A

ja

1

Modell B

Modell B

ja

2

Modell C

Modell C

ja

3

Modell A

Modell A

ja

4

Modell B

Modell B

ja

5

Modell C

Modell C

ja

6

Modell A

Modell A

ja

7

Modell B

Modell B

ja

8

Modell C

Modell C

ja

9

Modell A

Modell A

ja

10

Modell C

Modell C

ja

11

Modell C

Modell A

nein

12

Modell B

Modell B

ja

13

Modell B

Modell B

ja

14

Modell B

Modell B

ja

15

Modell B

Modell C

nein

16

Modell C

Modell B

nein

17

Modell C

Modell B

nein

18

Modell A

Modell A

ja

Es sind 15 von 19 Datensätzen korrekt klassifiziert. Das entspricht einer Genauigkeit von \(\frac{15}{19} \approx 0,789\) oder 78,9%.

Inhalt