# Notizen SL Lektion 4 (Foliensatz 12: Algorithmen — Decision Trees)

> Thema: Supervised Learning Algorithmen
> Datum: 04.06.2026
> Dozentin: Violeta Vogel

## Theorie Decision Trees

- Ein Entscheidungsbaum ist ein Modell, das Daten anhand von Wenn-Dann-Regeln klassifiziert oder vorhersagt
- Der Baum versucht Daten so aufzuteilen, dass Gruppen möglichst **rein** werden *(rein, nicht klein — Reinheit ist das Ziel, ein reiner Knoten darf gross sein)*
    - nur noch eine Klasse enthalten
- Besteht aus
    - Wurzelknoten
    - Entscheidungsknoten
    - Blattknoten
    - Äste
- Arbeitet nach Top-Down Prinzip
- Divide and Conquer
    - Merkmale wählen dass die Daten am besten trennt
    - Entweder mit Gini Koeffizient oder Entropie-Reduktion trennen
    - Aufteilen entlang dieses Merkmales in eine oder mehrere Gruppen
    - Rekursiv weiter aufteilen
    - Stop wenn
        - Daten in einem Knoten homogen sind
        - keine sinvollen Splits mehr möglich
        - maximale Tiefe erreicht
- Eigenschaften
    - Gut nachvollziehbar
    - Flexibel
    - Geringe Anforderungen an Feature Engineering
        - keine Normierung oder Skalierung
    - Anfällig zu Overfitting!
- Feature Importance 
    - Wichtigkeit eines Features
    - Wie stark trägt ein Feature zur Vorhersage bei?
    - Ein Feature ist wichtig, wenn es
        - oft gesplittet werden kann
        - früh im Baum vorkommt
        - grosse Verbesserungen der Reinheit bringt
- Zwei Arten von Feature Importance
    - Impurity based Importance
        - schnell
        - berechnet man während des Trainings
        - Importance ergibt sich aus der Summe aller Reinheitsverbesserungen, die dieses Feature bringt
        - die Summen werden zum Schluss normiert, sodass alle Importances zusammen **1** ergeben *(Folie 81 — daher sind es relative Anteile)*
        - Wann verwenden?
            - Für erste Einschätzungen
            - Um Übersicht zu gewinnen
            - Wenn Modell nicht zu viele korellierte Features hat
    - Permutation Importance
        - robust
        - langsam
        - berechnet man nach dem Training
        - misst wie stark die Modellleistung sinkt wenn ein Feature zufällig permutiert (durchgewürfelt) wird
            - **sinkt** die Leistung stark → Feature ist wichtig → bleibt *(korrigiert: nicht „verändert sich → raus“)*
            - bleibt die Leistung ~gleich → Feature unwichtig → kann raus
            - permutieren über alle Features
        - Wann verwenden?
            - Wenn man eine verlässliche Feature-Wichtigkeit braucht
            - Wenn man ein BlackBoxModel erklärbar machen will
            - Prüfen auf Bias
        - Importance = Baseline Score - Score nach Permutation:
            1. Zuerst Baseline Leistung messen
            2. Ein Feature permutieren
            3. Leistung erneut messen
            4. Wichtigkeitswert berechnen

### Gini Impurity

- misst wie wahrscheinlich es ist, dass zwei zufällig ausgewählte Elemente aus einem Knoten verschiedenen Klassen angehören
- Für einen Knoten mit Klassenanteilen p1,p2,...,pK:
    - Gini = 1 - sum(i=1,k,pi^2)
- Gini = 0 -> perfekte Reinheit (nur eine Klasse)
- Gini hoch -> starke Durchmischung
- Vorteile
    - Effizient
    - Schneller als Entropie
    - ideal für grosse Datensätze
    - Gut geeignet für Random Forests
- Nachteile
    - Bevorzugt Features mit vielen Splitpunkten
    - Also numerische Features und solche mit vielen Kategorien
    - Kann bei unbalancierten Klassen verzerren

### Entropie

- misst wie viel Unsicherheit in einem Datensegment steckt
- Entscheidungsbaum versucht Unsicherheit durch Splits zu reduzieren
- Für einen Knoten mit Klassenanteilen p1,p2,...,pK:
    - entropie = -sum(i=1,k,pi*log2(pi))
- Entropie = 0 -> perfekte Reinheit (nur eine Klasse)
- Entropie hoch -> starke durchmischung
- Vorteile
    - hohe sensitivität
    - reagiert stärker auf Veränderung als Gini
    - mathematisch sauber definiert
    - gute Trennung bei seltenen Klassen
- Nachteile
    - höherer Rechenaufwand als Gini, da Logarithmen berechnet werden müssen
    - Ähnliches Verhalten wie Gini, der Aufwand lohnt sich also nicht immer
    - Kann bei stark unbalancierten Daten instabil sein
        - überempfindliche Splits bei seltenen Klassen
    - Kann zu tiefen Bäumen führen
        - overfitting

### Splitting

- ist der Prozess bei dem der Entscheidungsbaum die Frage auswählt, die Daten am besten trennt
- testet viele mögliche Splits und bewertet nach Reinheitsmass
- wählt Split mit höchstem Informationsgewinn

1. Alle features testen
    - für jedes Feature mögliche Schwellenwerte prüfen
        - Feature Alter -> teste 20,25,30,45 ...
        - Feautre Einkommen -> teste 40k,50k,69k ...
2. für jeden Split die Reinheit berechnen
    - berechnen wie "rein" die beiden entstehenden Gruppen sind, bspw. mit:
        - Gini-Impurity
        - Entropie
        - Misclassification Error
3. Splitqualität bestimmen
    - Baum misst wie stark sich die Reinheit verbessert
    - je grösser Gain desto besser der Split
4. Den besten Split auswählen
5. Rekursiv weiter splitten
    - bis Stopkriterium erreicht ist

### Pruning

- Pruning ist der Oberbegriff fürs Begrenzen der Baum-Komplexität gegen Overfitting; es gibt zwei Spielarten: Pre-Pruning (Wachstum begrenzen) und Post-Pruning (voll wachsen lassen, dann zurückschneiden) *(die Definition „nach dem Training verkleinern“ beschreibt genau genommen nur Post-Pruning)*
- Ziel ist es Overfitting zu reduzieren
- Vorteil
    - reduziert overfitting
    - verbessert generalisierung
    - vereinfacht interpretierbarkeit
    - erhöht stabilität
    - verhindert unnötige splits
- Nachteile
    - kann zu stark vereinfachen
    - nicht immer nötig
    - erfordert Validierungsdaten um optimal zu funktionieren
    - rechenintensiver als pre-pruning

### Pre-Pruning

- setzt Wachstumsgrenzen für den Baum damit er nicht unnötig tief wird
- typische Kriterien
    - maximale Tiefe
    - minimale Samples pro Blatt
    - minimale Verbesserung nötig für Split
- Methoden
    - max_depth
        - begrenzung der Baumtiefe
    - min_samples_split
        - nur splitten wenn genügend Datenpunkte verfügbar
    - min_samples_leaf
        - jedes Blatt muss mindestens n Samples enthalten
    - min_impurity_decrease
        - Split wird nur akzeptiert wenn er die Reinheit genügend verbessert
    - max_leaf_nodes
        - begrenzt die Anzahl Blätter direkt → kompakte Bäume

### Entscheidung Pruning/Prepruning

- Vorteile von Pre-Pruning
    - schnell
    - weniger Rechenaufwand
    - verhindert overfitting früh
    - einfachere modelle (flache bäume) sind einfacher zu verstehen
- Nachteile von Pre-Pruning
    - kann gute Spliuts verhindern wenn Grenzen zu streng sind
    - erfordert Hyperparameter-Tuning -> sonst Underfitting
    - weniger flexibel als Post-Pruning
 
 ### Post-Pruning 

- Post-Pruning schneided bereits gewachsene Bäume zurück um Overfitting zu reduzieren
- Methoden
    - Cost-Complexity-Pruning *(in sklearn: Parameter `ccp_alpha`)*
    - Reduced Error Pruning
- Vorteile
    - robuster gegenüber neuen Daten
    - verbessert generalisierung
    - flexibler als Pre-Pruning, der Baum darf zuerst alle Muster entdecken
- Nachteile 
    - rechenintensiver
    - benötigt Validierungsdaten
    - komplexere Implementierung

## Decision Tree Classifier

- ist ein überwachter Machine-Learning-Algorihmus der Daten anhand einer Reihe von regelbasierten Entscheidungen klassifiziert
- Erstell ein umgedrehtes Baumdiegramm
    - oben ist das wichtigste Merkmal
    - jede Antwort führt zu einem neuen Ast und zu einer weiteren Frage
    - bis ein Blattknoten erreicht wird, der die finale Klassenzuordnung enthält

---

## Praxis: Decision Tree Classifier (Code)

> Ergänzung zu den übersprungenen Praxis-Folien (bis Workshop 5). Datengrundlage:
> vorbereiteter Bank-Datensatz, geladen über das Kursmodul `bfh_cas_pml`.

### Basismodell

```python
from bfh_cas_pml import prep_data
from sklearn.tree import DecisionTreeClassifier

X_train, X_test, y_train, y_test = prep_data('bank_data_prep.csv', 'y', seed=1234)

model = DecisionTreeClassifier(random_state=1234)   # random_state nur für Reproduzierbarkeit
model.fit(X_train, y_train)
print(model.score(X_test, y_test))                  # ≈ 0.83
```

### Diagnose — Overfitting sichtbar machen

```python
print('depth :', model.get_depth())              # 28
print('leaves:', model.get_n_leaves())           # 777
print('train :', model.score(X_train, y_train))  # 1.0   <- perfekt
print('test  :', model.score(X_test,  y_test))   # 0.83
```

`train=1.0` vs `test=0.83` ist das Lehrbuch-Symptom: der voll ausgewachsene Baum
memoriert die Trainingsdaten (jedes Blatt rein), generalisiert aber schlecht.
→ Abhilfe = Pruning.

### Pre-Pruning per Hyperparameter-Tuning (Workshop 5: `min_impurity_decrease`)

Ein Split wird nur gemacht, wenn er die Impurity um mindestens diesen Wert senkt —
**normiert auf den ganzen Baum und gewichtet nach Knotengröße**:

```
ΔI_norm = (N_node / N_total) * ( I_parent - w_left*I_left - w_right*I_right )
```

Folge: tiefe Knoten betreffen wenige Samples → ihr ΔI_norm ist winzig → sinnvolle
Schwellen liegen bei ~1e-4 … 1e-2 (Float → `np.arange`, nicht `range`).

```python
import numpy as np

model  = DecisionTreeClassifier(random_state=1234)
params = np.arange(0, 0.004, 0.0002)
scores = []
for p in params:
    model.set_params(min_impurity_decrease=p)
    model.fit(X_train, y_train)
    scores.append(model.score(X_test, y_test))

best_i = np.argmax(scores)                       # Index des Maximums
print(f'best={scores[best_i]:.4f} @ {params[best_i]}')   # ~0.879 @ 0.0004
```

Vorgehen = Wertebereich **schrittweise eingrenzen** (grob → fein). Erwarteter
Kurvenverlauf: kurzer Anstieg/Bump über der Baseline (0.83), dann Abfall, sobald
nützliche Splits wegfallen; im Extrem Stumpf → Accuracy ≈ Mehrheitsklasse.

> ⚠ Methodik-Caveat: hier wird gegen `X_test` getunt → **optimistic bias** (wie
> in W4). Der „beste“ Score ist optimistisch verzerrt; sauber wäre ein
> Validation-Split bzw. CV.

### Baum visualisieren (gepruntes Modell)

```python
from bfh_cas_pml import inspect_decision_tree_model
inspect_decision_tree_model(
    DecisionTreeClassifier(min_impurity_decrease=0.0004, random_state=1234),
    X_train, y_train)
# druckt depth/leaves/score und zeichnet plot_tree -> der geprunte Baum ist klein & lesbar
```

### Feature Importance (impurity-based)

```python
import pandas as pd
import seaborn as sns

imp = pd.Series(model.feature_importances_, index=X_train.columns).sort_values()
sns.barplot(x=imp.values, y=imp.index)   # horizontaler Bar-Chart wie auf Folie 83
# Top-Features im Bank-Set: duration, nr_employed, month, euribor3m, age
```

Permutation Importance (robuster, in den Folien nur als Theorie):

```python
from sklearn.inspection import permutation_importance
r = permutation_importance(model, X_test, y_test, n_repeats=10, random_state=1234)
perm = pd.Series(r.importances_mean, index=X_train.columns).sort_values()
```

---

## RandomForest Tree

- ist ein ensemble Lernverfahren das aus vielen einzelnen Entscheidungsbäumen besteht
- jeder Baum trifft eine Vorhersage und der RandomForest kombiniert diese zu einer Gesamtvorhersage
- Sammlung zufällig trainierter Entscheidungsbäume
- Gemeinsame Entscheidung ist besser als einzelne Vorhersagen

### Ablauf

1. Bootstrap-Sampling
    - Für jeden baum zufälliges Dataset ziehen (mit zurücklegen)
2. Random Feature Selection
    - Bei jedem Split darf der Baum nur aus einer zufälligen Auswahl von Features wählen
3. Viele Bäume trainieren
    - 100-1000 Bäume
    - jeder Baum ist schwach, zusammen sind sie stark
4. Aggregation der Vorhersagen
    - Klassifikation (Mehrheitsvoting)
    - Regression (Durchschnitt aller Baumvorhersagen)

### Hyperparameter

1. n_estimators
    - Anzahl der Bäume im Wald
    - Mehr Bäume -> stabiler, genauer aber langsamer
2. max_depth
    - Maximale Tiefe jedes einzelnen Baums
    - Klein -> verhindert Overfitting
    - Gross -> jeder Baum wird komplexer
3. max_features
    - Wie viele Features pro Split?
    - Klassifikation oft "sqrt"
4. min_samples_split
    - Minimale Anzahl Samples die nötig sind um einen Split zu erzeugen
    - Höher  -> glattere, stabilere Bäume
    - Tiefer -> Mehr Splits
5. min_samples_leaf
    - Minimale Anzahl Samples in einem Blatt
    - Höher -> robust gegen rauschen
    - Tiefer -> feinere instabilere Blätter (bei unbalancierten Daten wichtig)
6. Bootstrap
    - Ob bootstrap-Sampling verwendet wird
    - True -> jeder Baum sieht zufällige Daten
    - False -> alle Bäume sehen dieselben Daten
7. criterion
    - Reinheitsmass für Splits
    - Klassifikation: Gini oder entropy
    - Regression: squared_error oder absolute_error
8. max_leaf_nodes
    - Begrenzt die Anzahl Blätter pro Baum
    - Verhindert extreme Tiefe
9. oob_score
    - Out Of Bag validierung aktivieren
    - Liefert eine eingebaute Testgenauigkeit
    - Spart einen separaten Validierungssplit

### Unterschied zu DecisionTree

- es werden viele Bäume trainiert (100-1000)
- jeder Baum basiert auf Zufallsstichprobe
- kein Pruning, Bäume werden voll ausgebaut
- Vorhersage: Alle Bäume werden aus gewertet und es wird abgestimmt

- DecistionTree, wenn
    - leicht erklärbares Modell wird benötigt
    - Daten sind einfach und Overfitting kontrollierbar ist
    - schnelle Trainings und Vorhersagezeiten
- Random Forest, wenn
    - Maximale Genauigkeit
    - komplexe Daten, verrauscht, hochdimensional
    - Robustheit
    - Overfitting unbedingt zu vermeiden ist