Decision Trees

Einführung

Wir lernen hier nun sogenannte Decision Tree Modelle kennen (dt. Entscheidungsbäume). Decision Trees gehören zur Klasse der nicht-parametrischen Machine Learning Modelle, da die Anzahl Parameter des Modells nicht von vornherein klar ist und erst nach dem Modell Training feststeht.

Decision Trees können sowohl für Regressions- als auch für Klassifikationsprobleme angewendet werden. Dementsprechend werden die spezifischen Modelle Regression Tree bzw. Classification Tree genannt.

Decision Trees sind in der Praxis sehr beliebt, vorausgesetzt es geht ausschliesslich um die Interpretierbarkeit (wir werden sehen, dass Decision Trees sehr einfach und ansprechend visualisiert werden können). Wenn es allerdings darum geht, möglichst gute Vorhersagen zu machen, dann werden in der Praxis kaum Decision Trees angewendet, weil sie selten zu den am besten performenden Modellen gehören. Wir werden aber später im Modul sehen, dass in der Praxis gut performende Modelle (sogenannte Ensemble Methoden) oft auf Decision Tree Modellen aufbauen.

Themen und Lernziele

Nach der Einführung werden wir uns ausführlich den Regression Trees widmen und sehen, wie ein Baum interpretiert werden muss, wie er Vorhersagen macht und wie man ein Decision Tree Modell trainiert. Danach werden wir sehen, inwiefern sich das Decision Tree Modell für Klassifikationsprobleme von demjenigen für Regressionsprobleme unterscheidet. Im vorletzten Teil werden die Vor- und Nachteile von Decision Trees aufgeführt und zu guter Letzt wird die Anwendung von Decision Tree Modellen mit tidymodels demonstriert.

Lernziele

Sie verstehen, wie sich Decision Trees von linearen und logistischen Regressionsmodellen unterscheiden.
Sie kennen die verschiedenen Elemente eines Baums (Root Node, Internal Nodes, Leaf Nodes, etc.) und wissen, wie ein gegebener graphischer Output zu interpretieren ist, insbesondere in Bezug auf die Entscheidungsregionen und Vorhersagen.
Sie können sich den sogenannten Input Space für max. drei Input-Variablen räumlich vorstellen und wissen, was mit Segmentierung des Inputs Spaces gemeint ist.
Sie verstehen die Äquivalenz eines Decision Trees und eines segmentierten Input Spaces.
Sie verstehen den Trainingsalgorithmus für Decision Trees und kennen die Hauptunterschiede zwischen dem Regressions- und dem Klassifikationsproblem. Sie verstehen insbesondere auch, was mit rekursiven Splits gemeint ist und warum der Algorithmus greedy ist.
Sie verstehen die verschiedenen möglichen Hyperparameter eines Decision Trees (max. Tiefe eines Baums, min. Anzahl Beobachtungen in einem Leaf Node, etc.).
Sie wissen, wie ein Decision Tree mathematisch als Funktion \(f(\mathbf{x}_i)\) geschrieben werden kann.
Sie können den Gini Index für einfache Beispiele rechnen.
Sie sind sich der Vor- und Nachteile von Decision Trees bewusst und können für ein konkretes ML- oder Data Science Problem entscheiden, ob sich ein Decision Tree eignet oder nicht.
Sie können den R Code im Beispiel nachvollziehen und sind in der Lage, den Code auf ein neues Beispiel zu übertragen.

Vergleich zu linearer und logistischer Regression

Folgende Abbildung veranschaulicht den Unterschied zwischen dem Linearen Regressionsmodell und einem Decision Tree für das Regressionsproblem (für eine Input-Variable \(x_i\)):

Wie dem Streudiagramm entnommen werden kann, ist der wahre Zusammenhang zwischen dem Input \(x_i\) und der Zielvariable \(y_i\) hier stark nicht-linear. Der Fit des linearen Regressionsmodells (rechter Plot) ist sehr schlecht, während ein Regressionsbaum zu einem relativ guten Fit führt (linker Plot). Wir können davon bereits ableiten, dass Decision Trees flexibler sind als die lineare Regression. Dementsprechend wird die Gefahr des Overfittings bei Decision Trees auch grösser sein als beim linearen Regressionsmodell.

Folgende Abbildung veranschaulicht den Unterschied zwischen dem Logistischen Regressionsmodell und einem Decision Tree für das Klassifikationsproblem (Quelle Bild: ISLR, p. 339):

Die zwei oberen Plots zeigen (schematisch) den Fall, in dem eine lineare Decision Boundary optimal ist und dementsprechend führt die logistische Regression (Plot links oben) zu einem optimalen Fit. Ein Klassifikationsbaum (Plot rechts oben) führt in diesem Fall zu einem schlechten Fit. Die zwei unteren Plots zeigen den Fall, in dem ein Klassifikationsbaum der logistischen Regression überlegen ist, weil eine nicht-lineare Decision Boundary hier besser ist.

Wir sehen also bereits, dass ein Decision Tree den Raum, der durch die Input-Variablen (hier \(x_1\) und \(x_2\)) aufgespannt wird, in Rechtecke aufteilt. Wir werden in diesem Kapitel viel von diesem durch die Input-Variablen aufgespannten Raum sprechen und nennen ihn darum den Input Space.

Weiterführende Ressourcen

Kapitel 8 in ISLR
Kapitel 6 in HOML
Decision Trees in tidymodels
ISLR mit tidymodels (Trees)
Tune and interpret decision trees for #TidyTuesday

Regression Trees

Warum spricht man überhaupt von Bäumen? Weil die Visualisierung des Modells wie ein umgekehrter Baum aussieht (siehe Abbildung unten). Befassen wir uns als erstes kurz mit der Anatomie eines Entscheidungsbaums.

Anatomie eines Decision Trees

Wir haben einen obersten Knoten, der Root Node genannt wird. Die inneren Knoten, nach denen weitere Splits folgen, werden Internal Nodes genannt. Die untersten Knoten, nach denen keine weiteren Splits folgen, werden Leaf Nodes genannt. Die Nodes sind durch sogenannte Branches verknüpft. Die Tiefe eines Baums entspricht der Anzahl von Ebenen, auf denen Splits durchgeführt werden.

Doch was repräsentiert dieser Baum eigentlich? Der Baum repräsentiert eine Sequenz von Splitting-Regeln basierend auf den Input-Variablen. Wir können eine Beobachtung nehmen und vom Root Node aus bestimmen, welchem Leaf Node diese Beobachtung angehört. Dabei folgen wir immer den im Baum definierten Splitting-Regeln.

Etwas mathematischer ausgedrückt: der Baum repräsentiert eine Segmentierung des Input Spaces in simple, rechteckige Regionen. Wir werden das im nächsten Abschnitt anhand eines Beispiels demonstrieren.

Wie liest man einen Baum?

Wir verwenden hier in der Folge den housingrents Datensatz, den einige von Ihnen bereits gut kennen. Der Datensatz enthält \(n = 152\) Beobachtungen zu Schweizer Wohnungen. Die Zielvariable ist die Miete rent. Die zwei wichtigsten Input-Variablen sind die Fläche einer Wohnung (area) sowie das ökonomische Alter einer Wohnung (econage). Eine weitere Input-Variable ist nre, dabei handelt es sich um eine binäre kategorische Variable, die den Wert 1 annimmt, falls eine Wohnung der Immobilienfirme NRE gehört und sonst 0.

Die folgende Abbildung zeigt den Root Node sowie den ersten Split des Baums, der resultiert, wenn ein Regression Tree auf den housingrents Daten angewendet wird. Der Root Node enthält zwei Zahlen, einerseits die mittlere Miete über den ganzen Trainingsdatensatz (CHF 1240) und andererseits den Anteil von Trainingsbeobachtungen im Root Node. Dieser Anteil ist vor dem ersten Split noch 100%.

Der erste Split verwendet die Variable econage und den Splitpunkt 25. Alle Wohnungen, die min. 25 Jahre alt sind, gehen dem linken Ast entlang in den linken internen Node. Insgesamt landen so 64% der Trainingsbeobachtungen in diesem linken internen Node. Die durchschnittliche Miete für diese Beobachtungen beträgt CHF 974. Alle Wohnungen, die jünger als 25 Jahre alt sind, gehen dem rechten Ast entlang in den rechten internen Node. Das sind dementsprechend die restlichen 36% der Beobachtungen und deren mittlere Miete beträgt CHF 1724.

Wichtig: dieser erste Split segmentiert den Input Space nun in zwei Regionen (Rechtecke), wie im rechten Teil der Abbildung dargestellt. Das wichtigste Take-Away hier ist, dass ein Split im Baum einer Segmentierung des Input Spaces entspricht! Weil wir hier nur die Variablen econage und area betrachten, können wir diesen Input Space ohne Probleme in 2D visualisieren.

Der zweite Split geschieht beim linken internen Node. Dort splitten wir die 64% der Beobachtungen basierend auf der Input-Variable area in zwei Untergruppen. Der Splitpunkt liegt bei 63 Quadratmeter. Der linke Leaf Node enthält nun nur noch 25% der Beobachtungen und deren mittlere Miete beträgt CHF 690. Das macht Sinn, denn es handelt sich dabei um alte (25 Jahre oder älter) und kleine Wohnungen (kleiner als 63 Quadratmeter). Der rechte Leaf Node enthält 39% aller Beobachtungen und deren Mittelwert beträgt CHF 1154. Es handelt sich dabei um alte, aber relativ grosse Wohnungen.

Im rechten Teil der Abbildung sehen wir, dass dieser zweite Split den oberen Teil des Input Spaces weiter segmentiert in zwei Subregionen.

Der dritte Split geschieht im rechten internen Node und basiert ebenfalls auf der Input-Variable area. Der Splitpunkt liegt bei 139 Quadratmeter. Dieser Split teilt also die eher neuen Wohnungen (erster Split) weiter auf in sehr grosse (grösser als 139 Quadratmeter) und weniger grosse (kleiner als 139 Quadratmeter) Wohnungen. Die mittlere Miete für die 31% der Beobachtungen im linken Leaf Node beträgt CHF 1599, während die mittlere Miete für die 5% der Beobachtungen im rechten Leaf Node CHF 2561 beträgt.

Wir sehen in folgender Abbildung, dass der dritte Split das untere Reckteck im Input Space weiter segmentiert.

Der finale Baum sowie die finale Segmentierung des Input Spaces sehen wie folgt aus:

Wir sehen, dass die drei Splits zu vier Leaf Nodes führen. Wichtig: Jeder Leaf Node entspricht einer Region im Input Space. Die blau gestrichelten Linien, welche die Regionen von einander trennen, sind die Decision Boundaries dieses Modells. Sie begrenzen die verschiedenen Regionen, in denen wir je unterschiedliche Vorhersagen machen.

Die Vorhersagen unseres Baums sind die mittleren Mieten in den jeweiligen Regionen. Überlegen wir uns das kurz anhand eines Beispiels: wir haben nun eine 15-jährige Wohnung mit einer Fläche von 110 Quadratmeter. Gemäss unserem Baum gehört diese Wohnung der Region \(R_3\) an und dementsprechend wäre unsere Vorhersage für diese Wohnung CHF 1599. Dabei sehen wir gleich noch eine andere Eigenschaft von Decision Trees: sie machen für alle Beobachtungen in der selben Region die gleiche Vorhersage. Oder in anderen Worten: die Vorhersagen sind pro Region konstant.

Aufgaben: Beantworten Sie die nachfolgenden Fragen zum abgebildeten Regressionsbaum.

Wir trainieren wir einen Baum?

Das Ziel ist, einen Regression Tree zu finden, dessen Regionen zu einer Minimierung des Mean Squared Errors führen. Hier ist also der MSE unsere Kostenfunktion. Mathematisch können wir das wie folgt schreiben:

\[ \text{min} \left(\sum_{j=1}^J \sum_{i \in R_j} (y_i - \hat{y}_{R_j})^2 \right) \] Die äussere Summe summiert über die Regionen \(R_1, R_2, \dots, R_J\) und die innere Summe summiert für jede Region über die quadrierten Distanzen zwischen beobachteten und vorhergesagten Werten der Zielvariable. Es handelt sich in dieser Formel um die Summe der quadrierten Residuen (SQR). Wenn wir die SQR durch \(n\) teilen, dann kriegen wir den MSE. Wenn wir SQR minimieren, dann minimieren wir auch den MSE!

Leider ist es nicht möglich dieses Minimierungsproblem genau zu lösen, denn es gibt zu viele verschiedene (genauer gesagt: unendlich viele) Möglichkeiten, wie die Recktecke im Input Space angeordnet und kombiniert werden können.

Beim Training von Decision Trees treffen wir deshalb einige vereinfachende Annahmen, um eine Annäherung an die optimale Lösung für obiges Minimierungsproblem zu finden. Der Trainingsalgorithmus wird Recursive Binary Splitting genannt. Dieser Algorithmus hat die Eigenschaft, dass er greedy ist. Doch was bedeutet all das?

Binary: Jeder Split hat genau einen Splitpunkt und führt deshalb zu genau zwei “Children Nodes”. Jeder Split entspricht also einer binären “entweder-oder” Entscheidung.
Recursive: Jeder Split basiert auf dem vorangegangenen Split ein Level höher. Der zweite Split splittet also eine der resultierenden Regionen aus dem ersten Split. Wenn Sie nochmal zum zweiten Split beim housingrents Datensatz gehen, dann sehen Sie, dass der zweite Split lediglich die obere Region splittet und nicht den ganzen Input Space. Der zweite Split bezieht sich auf den ersten Split, ist also rekursiv.
Greedy: wir optimieren in jedem Knoten immer nur den nächstmöglichen Split und schauen nicht weiter voraus bzw. den Baum runter. Der Algorithmus ist also in einem gewissen Sinn “geizig”.

Schauen wir uns diesen Trainingsalgorithmus wiederum anhand des housingrents Datensatzes an:

Wir rechnen die Summe der quadrierten Residuen (SQR) für jede Input-Variable und alle möglichen Splitpunkte \(s\) und wählen diejenige Input-Variable mit Splitpunkt \(s\), wo SQR minimal ist. Wir sehen, dass econage mit \(s=25\) zum kleinsten SQR führt. Darum ist dies unser erster Split im Baum. Gleichzeitig können wir daraus ableiten, dass econage die wichtigste Input-Variable im Datensatz ist. Nachfolgend die SQR Werte für ein paar mögliche Splitpunkte:
- econage mit \(s=25\): \(SQR = 50'416'316\)
- area mit \(s=63\): \(SQR = 54'575'445\)
- nre mit \(s=0.5\): \(SQR = 66'749'310\) (Schnittpunkt \(s=0.5\) teilt die Beobachtungen in NRE und nicht-NRE)
- Viele weitere Möglichkeiten!
Basierend auf den zwei Regionen aus dem ersten Split, wählen wir den zweiten Split so, dass wiederum SQR minimiert wird. Es resultieren drei Regionen. Wir sehen, dass area mit \(s=63\) der nächstbeste Split ist.
- area mit \(s=63\): \(SQR = 45'425'043\)
- nre mit \(s=0.5\): \(SQR = 49'902'355\)
- Viele weitere Möglichkeiten!
Wir können so fortfahren bis ein Stoppkriterium erfüllt ist (z.B. maximale Tiefe des Baums erreicht).

Dieser Trainingsalgorithmus hat ein grosses Problem und zwar führt er zu einer krassen Form von Overfitting. Wenn wir den Algorithmus nicht begrenzen, dann splittet der Baum frisch fröhlich weiter bis er irgendwann so viele Leaf Nodes wie Beobachtungen hat und jeder Leaf Node genau den Wert der Trainingsbeobachtung vorhersagt. Der Baum hat dann zwar einen MSE von 0 auf dem Trainingsdatensatz, würde auf einem Testdatensatz jedoch katastrophal schlechte Vorhersagen machen.

Die Lösung ist in der Praxis zum Glück einfach: wir müssen die Komplexität des Baums mittels eines Stoppkriteriums beschränken (siehe 3. im obigen Algorithmus). Folgende Kriterien zur Beschränkung sind möglich:

Maximale Tiefe des Baums
Minimale Anzahl Beobachtungen in einem Leaf Node
Minimale Anzahl Beobachtungen in einem Internen Node
Maximale Anzahl Leaf Nodes
…

All diese Stoppkriterien können wir als Hyperparameter unseres Modells interpretieren und dementsprechend können wir den optimalen Wert für ein gegebenes Stoppkriterium mittels Cross-Validation bestimmen. Eine alternative Lösung, welche in der Literatur manchmal besprochen wird, wäre Tree Pruning. Das schauen wir uns hier aber nicht im Detail an (für die Motivierten: p. 331 - 334 in ISLR).

In dieser Demo rechnen wir einen Regressionsbaum auf einem simplen Datensatz mit einer Input-Variable. Wir beschränken den Baum mittels der minimalen Anzahl Beobachtungen in einem internen Knoten. Wenn dieses Kriterium auf 2 gesetzt wird, dann kann der resultierende Baum die Daten perfekt abbilden. Die R-Funktion, die den Baum lernt, hat einen internen Maximalwert für die Tiefe eines Baums (31). Darum kann, wenn die Anzahl Trainingsbeobachtungen steigt, auch ein Baum ohne Beschränkungen die Daten möglicherweise nicht mehr optimal treffen.

Anzahl Beobachtungen

Min. Anzahl Beobachtungen in internen Knoten

Hier nun einige Aufgaben zum Modelltraining eines Regression Trees:

Regressionsbaum als mathematische Funktion

Wie zu Beginn des Moduls versprochen, kann jedes erdenkliche ML-Modell als mathematische Funktion \(f(\mathbf{x}_i)\) dargestellt werden. Für Regression Trees sieht das Modell wie folgt aus:

\[ f(\mathbf{x}_i) = \sum_{j=1}^J c_j \cdot \mathbb{1}_{(\mathbf{x}_i \in R_j)} \]

Wir summieren also über die Regionen \(R_j\). \(c_j\) ist der Durchschnitt über die Werte der Zielvariable der Trainingsbeobachtungen in Region \(j\). Die Funktion \(\mathbb{1}_{(\mathbf{x}_i \in R_j)}\) ist die sogenannte Indikatorfunktion, die nur genau dann den Wert 1 annimmt, wenn die Beobachtung \(\mathbf{x}_i\) in Region \(R_j\) liegt.

Beispiel: wir haben drei Regionen \(R_1, R_2, R_3\) mit entsprechenden Mittelwerten \(c_1=500, c_2=750, c_3=1000\). Nun haben wir eine neue Beobachtung \(\mathbf{x}_i\), die gemäss unserem Baum der Region 2 angehört. Der Funktionswert ist dementsprechend:

\[ f(\mathbf{x}_i) = 500 \cdot 0 + 750 \cdot 1 + 1000 \cdot 0 = 750 \]

Classification Trees

Classification Trees funktionieren vom Prinzip her fast gleich wie die Regression Trees. Auch hier versuchen wir den Input Space so zu segmentieren, dass die resultierenden Regionen die kategorische Zielvariable möglichst gut klassifizieren. Es gibt jedoch zwei zentrale Unterschiede zum Regressionsproblem:

Die Vorhersage in einer Region \(R_j\) entspricht nicht wie beim Regression Tree dem Mittelwert über die Zielvariable, sondern der am häufigsten vorkommenden Kategorie in Region \(R_j\).
Der Trainingsalgorithmus minimiert nicht wie beim Regression Tree die Summe der quadrierten Residuen (SQR), sondern den Gini Index. Der Gini Index ist ein Mass für die “Reinheit” in einem Node. Warum ist das ein gutes Gütekriterium? Ein perfekter Baum hat in jedem Leaf Node nur noch Beobachtungen einer Kategorie. In dem Fall ist die “Reinheit” maximal.

Schauen wir uns doch kurz die Formel für die Berechnung des Gini Index (für die \(j\)-te Region \(R_j\)) an:

\[ G_j = \sum_{k=1}^K \hat{p}_{jk} \cdot (1-\hat{p}_{jk}) \] \(\hat{p}_{jk}\) beschreibt hier den Anteil der \(k\)-ten Kategorie in der \(j\)-ten Region \(R_j\). Die Gesamtkostenfunktion ist dann einfach die Summe über die Gini Indizes in den verschiedenen Regionen, also \(\sum_j G_j\).

Drei wichtige (letzte) Punkte gibt es noch zu erwähnen:

Wie bei der logistischen Regression gesehen, geben uns die meisten Klassifkationsmodelle eine Wahrscheinlichkeit zurück, dass die Zielvariable \(y_i\) der ersten Kategorie angehört (\(y_i=1\)). Das ist auch für Classification Trees möglich. Anstelle der am häufigsten vorkommenden Kategorie können wir uns vom Baum auch die relativen Anteile der Kategorien in einer Region (bzw. einem Leaf Node) ausgeben lassen. Diese Anteil können als Wahrscheinlichkeiten für die verschiedenen Kategorien interpretiert werden.
Ein Classification Tree ist nicht auf eine binäre Zielvariable limitiert und kann problemlos auf mehrkategoriale Zielvariablen angewendet werden.
Kategoriale Input-Variablen sind übrigens auch problemlos in Bäumen verwendbar. Beispiel: wir haben eine Input-Variable Augenfarbe mit drei möglichen Kategorien “blau”, “grün” und “braun”. Der Trainingsalgorithmus testet in diesem Fall alle möglichen Splits:
- “blau” vs. “grün”/“braun”
- “grün” vs. “blau”/“braun”
- “braun” vs. “blau”/“grün”.

Vor- und Nachteile

Decision Trees haben viele Vorteile, aber leider auch einige gewichtige Nachteile, weshalb sie in der Praxis nicht so häufig angewendet werden.

Vorteile:

Decision Trees sind intuitiv einfach verständlich und gelten darum nicht als Black-Box Modelle.
Sie sind sehr gut visualisierbar. Auch Leute ohne Background in ML können einen Entscheidungsbaum mit den Splitting-Regeln intuitiv verstehen.
Für kategorische Input-Variablen ist kein One-Hot Encoding notwendig. In R kann man die entsprechenden Variablen als Factors dem Modell übergeben.
Im Buch ISLR (p. 339) wird zudem erwähnt, dass ein Decision Tree, der sequenziell Entweder-Oder Entscheidungen macht, unter Umständen menschliches Entscheidungsverhalten besser widerspiegelt als andere ML-Modelle.

Nachteile:

Decision Trees gelten als instabile Modelle, d.h., wenn nur eine Trainingsbeobachtung entfernt wird, dann resultiert unter Umständen ein anderer Baum. Bäume haben also in der Regel hohe Varianz und wenig Bias (Bias-Variance Tradeoff) und sind darum in der Praxis meist nicht die besten Modelle.
Ein Decision Tree kann insbesondere auch bei Rotationen des Trainingsdatensatzes instabil sein. Folgende Abbildung (Quelle: HOML, p. 206) illustriert dieses Problem. Links ist die bestmögliche Decision Boundary in einem rechten Winkel zur x-Achse. In diesem Fall funktioniert der Decision Tree gut. Rechts ist der selbe Datensatz rotiert, so dass der Decision Tree ein unnötig komplexes Modell schätzen muss, denn die Splits müssen immer parallel zu einer der Achsen im Input Space verlaufen. Ein logistisches Modell würde hier die Daten perfekt mit einer Geraden trennen.

Decision Trees in `tidymodels`

Wir illustrieren die Anwendung von Decision Trees anhand des Heart Datensatzes, der auch im Buch ISLR (p. 336 - 338) verwendet wird. Der Datensatz enthält diverse Angaben zu 303 Patientinnen und Patienten, die mit Herzproblemen in ein Spital eingeliefert wurden. Unser Ziel ist es, aufgrund von verschiedenen Attributen vorherzusagen, ob eine Patientin oder ein Patient eine Herzerkrankung hat. Der Datensatz kann vom UC Irvine ML Repository heruntergeladen werden.

Der Datensatz umfasst folgende Variablen:

age: Alter
sex: Geschlecht
cp: Art der Brustkorbschmerzen, 4 Kategorien
trestbps: systolischer Blutdruck
chol: Cholesterin-Wert im Blut
fbs: Blutzuckerwert (gemessen am Morgen auf nüchternen Magen) grösser als 120 mg/dl? (yes / no)
restecg: EKG Resultate, 3 Kategorien
thalach: Maximale erreichte Herzfrequenz
exang: Durch Sport ausgelöstes Angina (reduzierte Blutzufuhr zum Herz)? (yes / no)
oldpeak: Parameter der EKG Messung
slope: Parameter der EKG Messung, 3 Kategorien
ca: Anzahl Hauptarterien
thal: Thallium Stress Test Resultate (wie gut fliesst Blut zum Herz?), 3 Kategorien
hd: Herzerkrankung? (yes / no) - Zielvariable

Der Datensatz ist bereits auf RAPP geladen und kann unter heart aufgerufen werden. Schauen wir uns als erstes mal die ersten paar Zeilen des Dataframes an:

# Erste 10 Wörter in vocab
head(heart)

Als nächstes überprüfen wir kurz, ob der Dataframe fehlende Werte enthält:

# Fehlende Werte
sapply(heart, function(x) sum(is.na(x)))

Wir sehen, dass die Variable ca 4 fehlende Werte und die Variable thal zwei fehlende Werte enthält. Ein weiterer Vorteil von Decision Trees ist, dass diese Methode gut mit fehlenden Werten umgehen kann. Was effektiv passiert, ist folgendes: wenn in einem Split eine Variable verwendet wird, welche fehlende Werte enthält, dann wird für die Beobachtungen mit fehlenden Werten eine andere Variable (sogenanntes Surrogat) für den Split verwendet, welche möglichst ähnliche Entscheidungen trifft wie die Splitvariable.

Als nächstes stellen wir sicher, dass wir keine starke Imbalance in der Zielvariable haben:

# Ist der Datensatz balanced?
heart %>% 
  count(hd) %>% 
  mutate(prop = n / sum(n))

Das sieht gut aus. Ein Verhältnis von 54% Nein (keine Herzerkrankungen) zu 46% Ja (Herzerkrankungen) in der Zielvariable ist akzeptabel.

Wir machen hier ausnahmsweise keinen Train-Test Split, da es hier lediglich darum geht, die Anwendung von Decision Trees zu demonstrieren. In einem richtigen ML-Projekt würden wir allerdings spätestens hier einen Train-Test Split vollziehen.

Stattdessen erstellen wir 5 Folds, um die optimalen Hyperparameter mit 5-Fold Cross-Validation zu finden.

# Seed für Reproduzierbarkeit
set.seed(123)

# 5-Fold CV
folds <- vfold_cv(heart, v = 5, repeats = 1, strata = hd)

Nun spezifizieren wir das Modell mit der Funktion decision_tree() aus tidymodels. Wir werden hier die Hyperparameter tree_depth (Tiefe des Baums) und min_n (minimale Anzahl Beobachtungen in einem Node) tunen. Den Hyperparameter cost_complexity setzen wir auf 0 (diesen würden wir für das Pruning eines Baums verwenden, das wir uns jedoch im Theorieteil nicht angeschaut haben). Wir spezifizieren ausserdem, dass es sich um ein Klassifikationsproblem handelt und dass wir das R-Package rpart für das Fitting verwenden wollen.

# Spezifikation des Classification Trees
dt_mod <- 
  decision_tree(tree_depth = tune(), min_n = tune(), cost_complexity = 0) %>%
  set_mode("classification") %>% 
  set_engine("rpart")

Im Workflow definieren wir unter anderem die Modellgleichung hd ~ ., d.h. die Variable hd ist die Zielvariable und alle anderen werden als Input-Variablen verwendet.

# Workflow
dt_workflow <- 
  workflow() %>% 
  add_model(dt_mod) %>% 
  add_formula(hd ~ .)

Wir erstellen einen Tuning Grid für die beiden Hyperparameter, die wir tunen wollen:

# Tuning Grid
dt_grid <- expand.grid(tree_depth = seq(1, 20, by = 2), min_n = seq(10, 30, 5))

# Wie sieht Grid aus?
print(dt_grid)

Nun sind wir bereit, das Modell zu fitten und das Hyperparameter Tuning durchzuführen. Da der nächste Schritt etwas länger dauert, ist der folgende Code Block nicht interaktiv. Im Hintergrund ist des Resultat des Tunings allerdings bereits als dt_res geladen.

# Tuning / Model Fitting
dt_res <- 
  dt_workflow %>% 
  tune_grid(
    resamples = folds,
    grid = dt_grid,
    control = control_grid(save_pred = TRUE),
    metrics = metric_set(roc_auc, accuracy))

Schauen wir uns doch die besten 10 Hyperparameter Werte gemäss ROC AUC Kriterium an:

# Wir sortieren die Hyperparameter Spezifikationen nach ROC AUC
dt_res %>% 
  show_best(metric = "roc_auc", n = 10) %>% 
  arrange(desc(mean))

Wir speichern das optimale Modell unter dt_best:

# Wir wählen das beste Modell
dt_best <- 
  dt_res %>% 
  select_best(metric = "roc_auc")

Nun fitten wir den optimalen Decision Tree (tree_depth = 5 und min_n = 20) auf dem ganzen Datensatz, so dass wir den letzten optimalen Fit kriegen:

# Last Fit Spezifikation (optimale Hyperparameter Werte)
last_dt_mod <-
  decision_tree(tree_depth = 5, min_n = 20, cost_complexity = 0) %>% 
  set_mode("classification") %>% 
  set_engine("rpart")

# Workflow anpassen (optimales Modell)
last_dt_workflow <- 
  dt_workflow %>% 
  update_model(last_dt_mod)

# Last Fit (auf ganzem Trainingsdatensatz)
last_dt_fit <-
  last_dt_workflow %>% 
  fit(data = heart)

Wir können uns den Last Fit mal in die Konsole ausgeben lassen:

# Last Fit
last_dt_fit

Mithilfe des R-Packages rpart.plot können wir den finalen Baum plotten:

# Plot des finalen Baums
last_dt_fit %>%
  extract_fit_engine() %>%
  rpart.plot()

Jeder Knoten im Baum enthält drei Informationen: erstens die Vorhersage, die der Baum in diesem Knoten machen würde; zweitens den relativen Anteil an Beobachtungen mit Herzerkrankung; und drittens den gesamten relativen Anteil von Beobachtungen, welche in diesem Knoten landen. Anhand der Anzahl Leaf Nodes sehen wir, dass dieser Baum den Input Space in 13 Regionen aufteilt.

Nun plotten wir noch die ROC-Kurve für das finale Modell:

# ROC Kurve für finalen Baum
dt_auc <-augment(last_dt_fit, new_data = heart) %>%
  roc_curve(hd, .pred_yes, event_level = "second")

# ROC Kurve
autoplot(dt_auc)

Mithilfe der Funktion predict() können wir basierend auf dem finalen Baum Vorhersagen für neue Beobachtungen machen. Hier tun wir das der Einfachheit halber für die fünfte Beobachtung im Datensatz heart. Wichtig: mit type = "class" kriegen wir die harte Vorhersage (“hard prediction”) für die Beobachtung, während wir mit type = "prob" die weiche Vorhersage (“soft prediction”) kriegen, also die Anteile von “yes” und “no” im Leaf Node (bzw. Region), in dem die fünfte Beobachtung landet.

# Vorhersagen
predict(last_dt_fit, new_data = heart[5, ], type = "class")
predict(last_dt_fit, new_data = heart[5, ], type = "prob")