{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Entscheidungsbäume lernen" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Einführung\n", "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](EntscheidungsbaumlernenEinfuehrung.pdf). \n", "\n", "
\n", "\n", " \"Description\n", "\n", "
\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Gini-Unreinheit und gewichtete Gini-Unreinheit\n", "Die folgenden Formeln findest du auch in Abschnitt 6.2 der Formelsammlung.\n", "\n", "### Gini-Unreinheit\n", "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: \n", "\n", "$$ Gini(D) = 1 - \\sum_{i=1}^{k} (p_i)^2 $$\n", "wobei die $p_i$ die relativen Häufigkeiten der Klassen sind.\n", "\n", "**Beispiel**: Wir betrachten eine Menge $D$ von *31* Datensätzen, die zu *drei* möglichen Klassen (*A*, *B* oder *C*) gehören.\n", "Dabei gilt:\n", "- 10 Datensätze gehören zur Klasse *A*\n", "- 8 Datensätze gehören zur Klasse *B*\n", "- 13 Datensätze gehören zur Klasse *C*\n", "\n", "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}$.\n", "\n", "Für die Gini-Unreinheit ergibt sich in diesem konkreten Beispiel:\n", "\n", "$$ Gini(D) = 1 - \\left[ \\left(\\frac{10}{31}\\right)^2 + \\left(\\frac{8}{31}\\right)^2 + \\left(\\frac{13}{31}\\right)^2 \\right] $$\n", "\n", "### Gewichtete Gini-Unreinheit\n", "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.\n", "\n", "Dazu benötigen wir ein Maß, das die Gini-Unreinheit der *Untergruppen* berücksichtigt. Dies ist die gewichtete Gini-Unreinheit.\n", "\n", "Mit $Gini(F=v)$ bezeichnen wir die (ungewichtete) Gini-Unreinheit der Auswahl von Datensätzen, bei denen das\n", "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.\n", "\n", "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:\n", "\n", "$$ Gini(F) = \\sum_{v} p_v \\cdot Gini(F=v) $$\n", "\n", "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.)\n", "\n", "```{margin} \n", "Achtung: Es geht uns immer noch darum, die Unreinheit bezüglich des Ziel-Features $Z$ zu minimieren. D.h. $Gini(F)$ beschreibt die \"Trennschärfe\" des Features $F$ *in Bezug auf das Ziel-Feature $Z$*.\n", "```\n", "\n", "**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. \n", "\n", "\n", "Angenommen, die Datensätze verteilen sich wie folgt auf die Werte des Features $F$:\n", "- 17 Datensätze haben beim Feature $F$ den Wert *ja*\n", " - davon gehören 5 zur Klasse *A*, 6 zur Klasse *B* und 6 zur Klasse *C*\n", "- 14 Datensätze haben beim Feature $F$ den Wert *nein*\n", " - davon gehören 2 zur Klasse *A*, 4 zur Klasse *B* und 8 zur Klasse *C*\n", "\n", "Aus diesen Werten ergibt sich mit der im vorigen Absatz beschriebenen Formel für die ungewichtete Gini-Unreinheit:\n", "\n", "$$ Gini(F=ja) = 1 - \\left[ \\left(\\frac{5}{17}\\right)^2 + \\left(\\frac{6}{17}\\right)^2 + \\left(\\frac{6}{17}\\right)^2 \\right] $$\n", "und\n", "\n", "$$ Gini(F=nein) = 1 - \\left[ \\left(\\frac{2}{14}\\right)^2 + \\left(\\frac{4}{14}\\right)^2 + \\left(\\frac{8}{14}\\right)^2 \\right] $$\n", "\n", "Um die *gewichtete* Gini-Unreinheit $Gini(F)$ zu berechnen, müssen wir nun noch die *Anteile* $Gini(F=ja)$ und $Gini(F=nein)$\n", "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:\n", "\n", "$$ Gini(F) = \\frac{17}{31} \\cdot Gini(F=ja) + \\frac{14}{31} \\cdot Gini(F=nein) $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Übung: Beratung beim Smartphone-Kauf\n", "Lade dir dieses [Aufgabenblatt](AB_Entscheidungsbaumlernen_Smartphone.pdf) herunter und bearbeite es. Die Anweisungen findest du auf dem Arbeitsblatt. Viel Erfolg 💪\n", "\n", "Hier noch einmal die Daten vom Aufgabenblatt:\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "\n", "\n", "| Budget | Akkulaufzeit | Kamera | Speicher | Empfehlung |\n", "|----------|--------------|----------|----------|------------|\n", "| niedrig | lang | mittel | groß | Modell A |\n", "| hoch | mittel | wichtig | groß | Modell B |\n", "| mittel | lang | mittel | groß | Modell C |\n", "| niedrig | kurz | egal | klein | Modell A |\n", "| hoch | lang | wichtig | groß | Modell B |\n", "| mittel | mittel | mittel | klein | Modell C |\n", "| niedrig | lang | egal | klein | Modell A |\n", "| hoch | mittel | mittel | groß | Modell B |\n", "| mittel | lang | wichtig | groß | Modell C |\n", "| niedrig | kurz | egal | klein | Modell A |\n", "| mittel | mittel | wichtig | groß | Modell C |\n", "| niedrig | lang | mittel | groß | Modell C |\n", "| hoch | mittel | wichtig | groß | Modell B |\n", "| niedrig | lang | wichtig | klein | Modell B |\n", "| hoch | lang | mittel | klein | Modell B |\n", "| mittel | lang | wichtig | klein | Modell B |\n", "| niedrig | lang | wichtig | groß | Modell C |\n", "| hoch | kurz | mittel | groß | Modell C |\n", "| mittel | kurz | egal | groß | Modell A |\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Ausführliche Musterlösung\n", "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Gini-Unreinheit der gesamten Tabelle\n", "\n", "Die Tabelle enthält insg. **19** Datensätze. Wir wollen wissen, wie \"unrein\" die Tabelle bezüglich des \n", "Zielmerkmals *Empfehlung* ist. Dazu zählen wir die Häufigkeiten der drei möglichen Werte (Klassen) von *Empfehlung*:\n", "\n", "\"Modell A\" wird 5-mal empfohlen, \"Modell B\" und \"Modell C\" je 7-mal. \n", "Es ergibt sich also in diese Fall folgende Formel für die Gini-Unreinheit:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$ 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 $$\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Gewichtete Gini-Unreinheit für das Feature *Budget*\n", "Weil es für das Feature *Budget* drei mögliche Werte gibt (*niedrig*, *mittel*, *hoch*), teilen wir die Datensätze entsprechend auf.\n", "Für jede Aufteilung berechnen wir\n", "1. die relative Häufigkeit der Datensätze mit dem jeweiligen Wert von *Budget*\n", "2. die (ungewichtete) Gini-Unreinheit für diese Aufteilung\n", "\n", "- 7 von 19 Datensätzen haben beim Merkmal *Budget* den Wert *niedrig* → Relative Häufigkeit $p_{niedrig} = \\frac{7}{19}$:\n", " - Aus diesen 7 wird 4-mal Modell A empfohlen, 1-mal Modell B und 2-mal Modell C. Es ergibt sich also:\n", " \n", " $$ 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 $$\n", "\n", "- 6 von 19 Datensätzen haben beim Merkmal *Budget* den Wert *mittel* → Relative Häufigkeit $p_{mittel} = \\frac{6}{19}$:\n", " - Aus diesen 6 wird 1-mal Modell A empfohlen, 1-mal Modell B und 4-mal Modell C. Es ergibt sich also:\n", "\n", " $$ 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 $$\n", "\n", "- 6 von 19 Datensätzen haben beim Merkmal *Budget* den Wert *hoch* → Relative Häufigkeit $p_{hoch} = \\frac{6}{19}$:\n", " - Aus diesen 6 wird 0-mal Modell A empfohlen, 5-mal Modell B und 1-mal Modell C. Es ergibt sich also: \n", "\n", " $$ 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 $$\n", "\n", "Die **gewichtete Gini-Unreinheit** für das Feature *Budget* ergibt sich dann aus der Summe der gewichteten Gini-Unreinheiten:\n", "\n", "$$ Gini(Budget) = \\frac{7}{19} \\cdot 0.571 + \\frac{6}{19} \\cdot 0.5 + \\frac{6}{19} \\cdot 0.278 = 0.456 $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Auswahl des besten Features\n", "Die gewichteten Gini-Unreinheiten für die Features *Budget*, *Akkulaufzeit*, *Kamera* und *Speicher* sind:\n", "-\tBudget: 0,456 (s.o.)\n", "-\tAkkulaufzeit: 0,542\n", "-\tKamera: 0,408\n", "-\tSpeicher: 0,612\n", "\n", "Das Feature *Kamera* hat die *geringste* gewichtete Gini-Unreinheit und ist daher das beste Feature für die erste Entscheidung im Entscheidungsbaum." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Der Entscheidungsbaum nach dem ersten Schritt\n", "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.\n", "\n", "```{figure} bilder/entscheidungsbaum_tiefe_1_ohne_endknoten.svg\n", "---\n", "width: 50%\n", "---\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Daten, mit denen weitergearbeitet wird\n", "Die Datensätze, die beim Feature *Kamera* den Wert *wichtig* haben, sind:\n", "\n", "\n", "\n", "\n", "\n", "| Budget | Akkulaufzeit | Kamera | Speicher | Empfehlung |\n", "|----------|--------------|----------|----------|------------|\n", "| hoch | mittel | wichtig | groß | Modell B |\n", "| hoch | lang | wichtig | groß | Modell B |\n", "| mittel | lang | wichtig | groß | Modell C |\n", "| mittel | mittel | wichtig | groß | Modell C |\n", "| hoch | mittel | wichtig | groß | Modell B |\n", "| niedrig | lang | wichtig | klein | Modell B |\n", "| mittel | lang | wichtig | klein | Modell B |\n", "| niedrig | lang | wichtig | groß | Modell C |\n", "\n", "\n", "\n", "Der Teil des Baums unterhalb des Knotens *Kamera=wichtig* muss also nur noch mit diesen Datensätzen arbeiten. \n", "Das Feature *Kamera* wird dafür nicht mehr benötigt (weil alle Datensätze sowieso denselben Wert haben). Es\n", "bleiben also noch die Features *Budget*, *Akkulaufzeit* und *Speicher*.\n", "\n", "Wir versuchen ohne zu rechnen abzuschätzen, welche Features am besten dazu geeignet sind, das Zielmerkmal *Empfehlung* zu klassifizieren:\n", "\n", "- *Budget:* Bei hohem Budget wird immer Modell B empfohlen, bei mittlerem Budget in 2 von 3 Fällen Modell C und bei \n", " 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.\n", "\n", "- *Akkulaufzeit:* Wenn eine lange Akkulaufzeit wichtig ist, wird in 3 von 5 Fällen Modell B empfohlen, in den \n", " 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.)\n", " Das Feature *Akkulaufzeit* scheint nicht besonders aussagekräftig zu sein.\n", " \n", "- *Speicher*: Wenn der Wunsch nach großem Speicherplatz besteht, wird in 3 von 6 Fällen Modell C empfohlen, in den \n", " anderen 3 Fällen Modell B. Das ist nicht sehr hilfreich. Bei kleinem Speicherplatz wird zwar in beiden Fällen Modell B empfohlen,\n", " da aber die meisten Datensätze großen Speicherplatz haben, ist das \n", " Feature *Speicher* auch nicht besonders aussagekräftig. \n", "\n", "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:\n", "\n", "- Gini(Budget) = $0,292$\n", "- Gini(Akkulaufzeit) = $0,467$\n", "- Gini(Speicher) = $0,375$\n", "\n", "Das passt einigermaßen zu unserer Einschätzung. Das Feature *Budget* ist also das beste für den nächsten Schritt im Entscheidungsbaum." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Fertiger Entscheidungsbaum (Tiefe 2)\n", "\n", "```{figure} bilder/entscheidungsbaum_tiefe_2.svg\n", "---\n", "width: 80%\n", "---\n", "```\n", "\n", "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 \n", "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.\n", "\n", "\n", "\n", "|Nr | Zielwert | Vorhersage | korrekt? |\n", "|---|----------|------------|---------|\n", "| 0 | Modell A | Modell A | ja |\n", "| 1 | Modell B | Modell B | ja |\n", "| 2 | Modell C | Modell C | ja |\n", "| 3 | Modell A | Modell A | ja |\n", "| 4 | Modell B | Modell B | ja |\n", "| 5 | Modell C | Modell C | ja |\n", "| 6 | Modell A | Modell A | ja |\n", "| 7 | Modell B | Modell B | ja |\n", "| 8 | Modell C | Modell C | ja |\n", "| 9 | Modell A | Modell A | ja |\n", "|10 | Modell C | Modell C | ja |\n", "|11 | Modell C | Modell A | nein |\n", "|12 | Modell B | Modell B | ja |\n", "|13 | Modell B | Modell B | ja |\n", "|14 | Modell B | Modell B | ja |\n", "|15 | Modell B | Modell C | nein |\n", "|16 | Modell C | Modell B | nein |\n", "|17 | Modell C | Modell B | nein |\n", "|18 | Modell A | Modell A | ja |\n", "\n", "\n", "\n", "Es sind 15 von 19 Datensätzen korrekt klassifiziert. Das entspricht einer Genauigkeit von $\\frac{15}{19} \\approx 0,789$ oder 78,9%. " ] } ], "metadata": { "kernelspec": { "display_name": "base", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.3" } }, "nbformat": 4, "nbformat_minor": 2 }