Beslutningstrær

Tenk deg en nettbutikk som vil vite om et besøk ender i kjøp. En erfaren selger kunne sagt: «Kunder over 30 kjøper nesten alltid. For de yngre kommer det an på om de har vært innom flere ganger før.» Et beslutningstre lærer slike regler fra data i stedet for at noen skriver dem for hånd.

Treet består av noder. Hver indre beslutningsnode stiller ett spørsmål av formen $x_j\le t$: er feature $j$ mindre enn eller lik terskelen $t$? Valget av feature og terskel kalles en split. Ja-svar går til venstre og nei-svar til høyre, helt til observasjonen havner i en bladnode. For å predikere følger vi én sti fra roten og ned. Det regnes ingen vektet sum og ingen avstand, vi sammenligner bare tall med terskler.

Hva står i bladet? Under treningen havnet en gruppe treningspunkter i hvert blad. I klassifikasjon predikerer bladet majoritetsklassen blant dem, og predict_proba rapporterer klasseandelene. I regresjon predikerer bladet gjennomsnittet av målverdiene, som du ser i steg 4.

Hvilke terskler kan treet teste? For en numerisk feature sorterer algoritmen verdiene i noden og prøver midtpunktene mellom naboverdier som er ulike. Med verdiene $2,4,4,7$ er kandidatene $3$ og $5,5$. En terskel på $4,8$ ville gitt nøyaktig samme inndeling som $5,5$, så den trenger ikke testes. Hver split deler rommet med en linje parallelt med en akse, og beslutningsgrensen til et tre blir derfor alltid en trapp av akseparallelle biter.

Reglene koden skriver ut, er de samme som i figuren.

import numpy as np
from sklearn.tree import DecisionTreeClassifier, export_text

# Kunder: [alder, tidligere besøk] og om besøket endte i kjøp (1) eller ikke (0)
X = np.array([[19, 1], [22, 4], [21, 0], [31, 0], [24, 2], [34, 1],
              [26, 1], [39, 4], [27, 0], [44, 2], [29, 2], [48, 0],
              [23, 2], [53, 3], [25, 5]])
y = np.array([0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1])
dybde = 2  # @param 1..4
alder = 24  # @param 18..60

tre = DecisionTreeClassifier(max_depth=dybde, random_state=0).fit(X, y)
print(export_text(tre, feature_names=["alder", "besok"]))
ny = np.array([[alder, 1]])                 # ny kunde med 1 tidligere besøk
print(f"ny kunde, {alder} år og 1 besøk: P(kjøp) = {tre.predict_proba(ny)[0, 1]:.2f}")
print("sti for den nye kunden:")
t = tre.tree_
for node in tre.decision_path(ny).indices:
    if t.children_left[node] == -1:
        print(f"  blad: klasse {t.value[node][0].argmax()}")
    else:
        v = ny[0, t.feature[node]]
        print(f"  {['alder', 'besok'][t.feature[node]]} = {v} {'<=' if v <= t.threshold[node] else '>'} {t.threshold[node]:.2f}")

For å velge et spørsmål trenger treet et tall for hvor blandet en node er. Det tallet kalles urenhet. En node der alle punktene har samme klasse, er ren og har urenhet 0. En node der klassene er like store, er så uren som den kan bli. To mål er vanlige.

ƒGini-urenhet kan leses som sannsynligheten for å ta feil hvis du trekker et tilfeldig punkt fra noden og gjetter klassen ved å trekke en etikett etter klassefordelingen i noden:

Med to klasser og $p=0,5$ blir $G=1-0,25-0,25=0,5$, som er maksimum for to klasser. Med $K$ like store klasser er maksimum $1-1/K$, for eksempel $2/3$ med tre klasser.

ƒEntropi måler hvor mange bits du i snitt trenger for å fortelle hvilken klasse et tilfeldig punkt fra noden har:

Ledd med $p_k=0$ regnes som 0. En ren node har $H=0$, og en 50/50-node har $H=1$ bit. Med tre like store klasser er $H={\log }_{2}3\approx 1,585$, så entropi er ikke begrenset til 1.

De to målene har samme form: null i en ren node, størst ved jevn fordeling og symmetriske i klassene. De rangerer derfor nesten alltid splittene likt. Gini er litt billigere å regne ut, siden den ikke trenger logaritmer, og er standard i scikit-learn (criterion="gini"). Entropi henger sammen med informasjonsgevinst, som du møter i neste steg.

Med terskelen helt ut mot en av kantene nærmer entropien i det store barnet seg entropien til hele noden, 1 bit for fem mot fem.

Nå kan vi måle hvor uren én node er. Men en split lager to barn, og vi trenger ett tall for hele splitten. Det naive er å legge sammen urenheten i barna, men det straffer feil ting: et barn med ett punkt er nesten alltid rent, og et barn med hundre punkter betyr hundre ganger så mye for treningsfeilen. Derfor vekter vi hvert barn med hvor stor andel av punktene det får. Med $L$ og $R$ for venstre og høyre barn og $P$ for forelderen er

der $I$ er Gini eller entropi. ƒReduksjon i urenhet er forskjellen mellom forelderens urenhet og dette tallet. Med entropi kalles reduksjonen informasjonsgevinst: hvor mange bits usikkerhet spørsmålet i snitt fjerner.

Treet prøver alle features og alle kandidatterskler i noden og velger splitten med lavest vektet urenhet. Siden forelderens urenhet er den samme for alle kandidatene i en node, er det nøyaktig det samme som å velge størst reduksjon. Så gjentas jobben i hvert barn. Algoritmen er grådig: den tar det beste spørsmålet akkurat nå og går aldri tilbake for å sjekke om et dårligere første spørsmål kunne gitt et bedre tre totalt.

Et regresjonstre predikerer et tall, for eksempel en månedsleie. Strukturen er den samme, men to ting endres: hva bladet sier, og hva «ren» betyr.

Bladet predikerer gjennomsnittet av målverdiene til treningspunktene som havnet der, ƒbladprediksjon i regresjon. Gjennomsnittet er valgt fordi det er det tallet som gir minst kvadratisk feil i bladet. En node er «ren» når målverdiene i den ligger tett, altså når variansen er liten. Splitkriteriet blir ƒvektet varians etter split:

Treet velger splitten med lavest vektet varians, som er det samme som størst variansreduksjon fra forelderen. Fordi $\mathrm{Var}(S)$ er gjennomsnittlig kvadratavvik fra bladets gjennomsnitt, betyr dette at treet minimerer treningens MSE rett etter splitten. I scikit-learn heter kriteriet derfor criterion="squared_error".

Resultatet er en trappefunksjon: hvert blad gir én konstant, og prediksjonen hopper ved tersklene. Et regresjonstre kan aldri predikere en verdi utenfor området til treningsmålene, siden et gjennomsnitt alltid ligger mellom den minste og den største verdien. Innenfor dataene er det greit, men det betyr at treet ikke kan forlenge en trend, for eksempel en pris som fortsetter å stige.

Får treet fortsette å splitte, stopper det først når hvert blad er rent, i verste fall med ett treningspunkt per blad. Da er treningsfeilen null, men treet har lært støyen. Det er overtilpasning i sin reneste form: et dypt tre har lav bias og svært høy varians. Bytt ut noen få treningspunkter, så kan den første splitten bli en annen, og dermed hele treet under den.

Derfor bremser vi veksten med forbeskjæring, regler som avgjør når en node blir et blad:

• •max_depth: største antall spørsmål fra rot til blad. Et tre med dybde $d$ har høyst $2^d$ blader.
• •min_samples_leaf: minste antall treningspunkter i et blad. Med $n$ punkter og grense $m$ gir det høyst $\lfloor n/m\rfloor$ blader, og hvert blad blir et gjennomsnitt over minst $m$ punkter, som demper støyen.
• •min_samples_split og min_impurity_decrease: splitt bare noder som er store nok, og bare når gevinsten er stor nok.

Alle disse er hyperparametre som velges med validering eller kryssvalidering, aldri med testsettet. Mindre dybde og større blader gir mer bias og mindre varians. Et alternativ er etterbeskjæring: la treet vokse fullt og klipp så bort grener som ikke hjelper på valideringsdata (i scikit-learn med ccp_alpha).

En annen kilde til overtilpasning er features med svært mange verdier. En kolonne der hver rad har sin egen verdi, kan dele dataene i rene små grupper uten at det sier noe om nye rader.

Høy varians er også grunnen til at enkelttrær sjelden brukes alene i praksis. Neste kapittel snur svakheten til en styrke: mange ustabile trær som er trent litt ulikt, gir et stabilt snitt.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor

rng = np.random.default_rng(9)
x = rng.uniform(0, 10, 120)
y = np.sin(x) + rng.normal(0, 0.3, 120)      # sann kurve + støy
X = x.reshape(-1, 1)
tren = np.arange(120) < 80                   # 80 til trening, 40 til test
min_blad = 1  # @param 1..20

dybder = list(range(1, 13))
mse_tren, mse_test = [], []
for d in dybder:
    tre = DecisionTreeRegressor(max_depth=d, min_samples_leaf=min_blad, random_state=0).fit(X[tren], y[tren])
    mse_tren.append(np.mean((tre.predict(X[tren]) - y[tren]) ** 2))
    mse_test.append(np.mean((tre.predict(X[~tren]) - y[~tren]) ** 2))
print(f"min_samples_leaf={min_blad}: lavest test-MSE {min(mse_test):.3f} ved max_depth={dybder[np.argmin(mse_test)]}")
print(f"dybde 12: {tre.get_n_leaves()} blader, MSE trening {mse_tren[-1]:.3f}, test {mse_test[-1]:.3f}")

plt.figure()
plt.plot(dybder, mse_tren, label="trening")
plt.plot(dybder, mse_test, label="test")
plt.xlabel("max_depth")
plt.ylabel("MSE")
plt.legend()
plt.tight_layout()
plt.show()

To egenskaper skiller trær fra lineære modeller og nevrale nett, og begge følger direkte av at hver split er en sammenligning $x_j\le t$.

Trær trenger ikke skalering. En split bryr seg bare om rekkefølgen på verdiene. Ganger du en feature med 1000 eller standardiserer den med $z=(x-\mu )/\sigma$, flytter terskelen seg tilsvarende, og nøyaktig de samme punktene havner på hver side. Det gjelder enhver strengt voksende transformasjon, også logaritmen. Treet blir det samme, og prediksjonene blir de samme. Gradient descent, k-nærmeste naboer og regularisering er derimot følsomme for skala.

Trær fanger vekselvirkninger. En lineær modell $\hat{y}=w_1{x}_1+w_2{x}_2+b$ gir $x_2$ samme effekt uansett verdien av $x_1$, med mindre du selv lager et produktledd. I et tre stilles spørsmålet om $x_2$ inne i en gren som allerede har svart på $x_1$, så effekten av $x_2$ kan være helt forskjellig i de to grenene. Det så du i nettbutikktreet: antall besøk betydde noe bare for de unge kundene.

Prisen er trappeformede grenser. En enkel skrå grense som $x_1+x_2>10$ krever mange små trappetrinn, mens en lineær modell klarer den med én linje.

Koden lager et XOR-mønster for en kornsilo, der risikoen er høy når nøyaktig én av fukt og temperatur er høy.

import numpy as np
from sklearn.linear_model import LogisticRegression
from sklearn.tree import DecisionTreeClassifier

seed = 4  # @param 0..20
dybde = 2  # @param 1..6
rng = np.random.default_rng(seed)
X = rng.uniform(0, 10, size=(300, 2))             # [fukt, temperatur] i en kornsilo
y = ((X[:, 0] > 5) != (X[:, 1] > 5)).astype(int)  # risiko når nøyaktig én er høy

lin = LogisticRegression().fit(X, y)
tre = DecisionTreeClassifier(max_depth=dybde, random_state=0).fit(X, y)
print(f"logistisk regresjon: accuracy {lin.score(X, y):.2f}")
print(f"tre, max_depth={dybde}:    accuracy {tre.score(X, y):.2f}")

# Samme tre på omregnede features: fukt i promille, temperatur i Fahrenheit
X2 = np.column_stack([X[:, 0] * 10, X[:, 1] * 1.8 + 32])
tre2 = DecisionTreeClassifier(max_depth=dybde, random_state=0).fit(X2, y)
print(f"like prediksjoner etter omregning: {np.all(tre.predict(X) == tre2.predict(X2))}")