Beslutsträd

Ett beslutsträd är en serie ja/nej-frågor.

            timmar > 10?
           /            \
         nej            ja
          |              |
     närvaro > 0.8?    GODKÄND
      /        \
    nej        ja
     |          |
  UNDERKÄND  GODKÄND

Träning betyder att hitta frågorna. Algoritmen provar alla kolumner och alla brytpunkter, och väljer den delning som gör de två grupperna mest «rena» — alltså mest ensidiga i sina svar.

Sedan upprepas det i varje gren, tills något säger stopp.

Varför träd är populära:

• Gränssnittet är begripligt — du kan läsa trädet och förklara ett beslut.
• Ingen skalning behövs (trädet delar på tröskelvärden).
• Blandar numeriska och kategoriska variabler utan förbehandling.
• Fångar icke-linjära samband och interaktioner automatiskt.

Och det stora problemet: ett obegränsat träd fortsätter dela tills varje löv innehåller en enda datapunkt. Då är träffsäkerheten på träningsdatan 100 % och på ny data usel. Trädet har memorerat.

Hur en delning väljs. Två mått på orenhet, båda gör i praktiken samma sak:

$\text{Gini} = 1 - \sum_k p_k^2, \qquad \text{Entropi} = -\sum_k p_k \log_2 p_k$

Båda är 0 när noden är helt ren och störst när klasserna är jämnt fördelade. För två klasser: max Gini = 0,5, max entropi = 1 bit.

Algoritmen väljer den delning som ger störst informationsvinst:

$\Delta = I(\text{förälder}) - \frac{n_v}{n}I(\text{vänster}) - \frac{n_h}{n}I(\text{höger})$

Delarna vägs med hur många exempel som hamnar i dem — en delning som bryter ut tre punkter ur tusen räknas lite.

Räkneexempel. 100 exempel, 50 av varje klass → Gini = 1 − (0,5² + 0,5²) = 0,5. En delning ger [40 A, 10 B] och [10 A, 40 B]:

• Vänster: 1 − (0,8² + 0,2²) = 0,32
• Höger: samma, 0,32
• Viktat: 0,5·0,32 + 0,5·0,32 = 0,32
• Vinst: 0,18

Överanpassning och hur den begränsas:

Trädens andra svaghet är instabilitet: byt ut några få datapunkter och trädet kan se helt annorlunda ut. Det gör dem opålitliga som förklaringar av fenomenet — även om de förklarar modellens beslut väl.

Båda problemen löses av samma idé: bygg många träd och låt dem rösta. Random forest tränar varje träd på ett stickprov av data och ett urval av kolumner; gradient boosting bygger träd som rättar föregående träds fel. Resultatet är ofta det bästa som finns för tabelldata — men förklarbarheten från det enskilda trädet är borta.

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

X, y = load_breast_cancer(return_X_y=True, as_frame=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, stratify=y, random_state=0)

for djup in (1, 3, 5, None):
    t = DecisionTreeClassifier(max_depth=djup, random_state=0).fit(Xtr, ytr)
    print(f"djup={str(djup):>4}  löv={t.get_n_leaves():>3}  "
          f"träning {t.score(Xtr, ytr):.3f}  test {t.score(Xte, yte):.3f}")
# djup=   1  löv=  2  träning 0.925  test 0.883
# djup=   3  löv=  8  träning 0.985  test 0.942
# djup=   5  löv= 14  träning 1.000  test 0.930
# djup=None  löv= 19  träning 1.000  test 0.930    ← memorerat träningsdatan

# Ett litet träd går att läsa
t = DecisionTreeClassifier(max_depth=2, random_state=0).fit(Xtr, ytr)
print(export_text(t, feature_names=list(X.columns), max_depth=2))

# Gini för hand
def gini(*antal):
    n = sum(antal)
    return 1 - sum((a / n) ** 2 for a in antal)

fore = gini(50, 50)
efter = 0.5 * gini(40, 10) + 0.5 * gini(10, 40)
print(round(fore, 3), round(efter, 3), "vinst", round(fore - efter, 3))   # 0.5 0.32 vinst 0.18

# Instabilitet: ta bort tre rader och se hur trädet ändras
for start in (0, 3):
    t = DecisionTreeClassifier(max_depth=2, random_state=0).fit(Xtr.iloc[start:], ytr.iloc[start:])
    print("rotdelning:", X.columns[t.tree_.feature[0]], round(float(t.tree_.threshold[0]), 3))