0 dní v řadě · 0 bodů

Strojové učení · 40 min

Rozhodovací stromy a náhodné lesy

Model z otázek typu ano, nebo ne. Postavíš strom v NumPy, uvidíš, proč se přeučuje, a spojíš stovky stromů do náhodného lesa.

Hloubka
Úkoly
Lidsky řečeno

Znáš hru dvacet otázek? „Je to živé? Je to větší než pes?“ Dobrá otázka rozdělí možnosti zhruba napůl, špatná („Je to pan Novák z Kolína?“) skoro nic neřekne. Rozhodovací strom je přesně tahle hra a počítač si z dat sám vybírá, které otázky se vyplatí položit. Náhodný les je pak celá třída hráčů, kteří hrají každý trochu jinak a nakonec hlasují.

Strom jako řada otázek

Předplatitelská služba chce vědět, kdo odejde. O každém zákazníkovi ví, kolik měsíců je u ní a kolik tiketů poslal na podporu. Rozhodovací strom je vnořená sada podmínek. Napsaný ručně vypadá takhle:

text
             tikety <= 4 ?
             /           \
           ano            ne
           /               \
     mesice <= 6 ?       ODEJDE
      /        \
    ano         ne
    /            \
 tikety <= 1 ?   ZŮSTANE
   /      \
 ZŮSTANE  ODEJDE

Každá otázka je uzel, konečná odpověď je list. Co vypíše tenhle kód?

def odejde(mesice, tikety):
    if tikety > 4:
        return True
    if mesice > 6:
        return False
    return tikety > 1

print(odejde(3, 0))
print(odejde(3, 2))
print(odejde(24, 2))
print(odejde(24, 9))
Výstup
False
True
False
True

Strom má vlastnost, kterou ostatní modely často nemají: dokážeš ho přečíst a vysvětlit šéfovi. Nepotřebuje ani standardizaci příznaků, protože se jen ptá, jestli je hodnota menší než práh. Měřítko nehraje roli. Zbývá otázka, jak najít dobré otázky automaticky.

Jak strom vybírá otázku

Dobrá otázka vytvoří skupiny, které jsou co nejčistší, tedy převážně z jedné třídy. Čistotu měří Giniho nečistota:

text
gini = 1 - p0² - p1²

p0 a p1 jsou podíly tříd ve skupině. Čistá skupina má 0, půl na půl u dvou tříd 0,5. Otázka rozdělí data na levou a pravou část a její kvalitu spočítáme jako vážený průměr obou nečistot. Vážený proto, že malá čistá skupinka sama o sobě moc nedokázala.

import numpy as np

def gini(y):
    p = np.mean(y)
    return 1 - p ** 2 - (1 - p) ** 2

def kvalita(leva, prava):
    n = len(leva) + len(prava)
    return len(leva) / n * gini(leva) + len(prava) / n * gini(prava)

print("čistá skupina:", gini(np.array([1, 1, 1, 1])))
print("půl na půl:   ", gini(np.array([0, 1, 0, 1])))
print()

dobra = kvalita(np.array([0, 0, 0, 1]), np.array([1, 1, 1, 0]))
spatna = kvalita(np.array([0, 1]), np.array([0, 0, 1, 1, 1, 0]))
print(f"dobrá otázka:  {dobra:.3f}")
print(f"špatná otázka: {spatna:.3f}")
Výstup
čistá skupina: 0.0
půl na půl:    0.5

dobrá otázka:  0.375
špatná otázka: 0.500

Hledání je hrubá síla: pro každý příznak se vyzkouší každý rozumný práh a vyhraje nejnižší vážená nečistota. Prahy se berou doprostřed mezi sousedními hodnotami. Projdi si cyklus tlačítkem krokovat.

import numpy as np

def gini(y):
    p = np.mean(y)
    return 1 - p ** 2 - (1 - p) ** 2

tikety = np.array([0, 0, 1, 1, 2, 3, 5, 6])
odesel = np.array([0, 0, 0, 1, 0, 1, 1, 1])

hodnoty = np.unique(tikety)
for prah in (hodnoty[:-1] + hodnoty[1:]) / 2:
    vlevo = tikety <= prah
    podil = vlevo.mean()
    skore = podil * gini(odesel[vlevo]) + (1 - podil) * gini(odesel[~vlevo])
    print(f"tikety <= {prah:<4} vlevo {vlevo.sum()}, vpravo {(~vlevo).sum()}, nečistota {skore:.3f}")
Výstup
tikety <= 0.5  vlevo 2, vpravo 6, nečistota 0.333
tikety <= 1.5  vlevo 4, vpravo 4, nečistota 0.375
tikety <= 2.5  vlevo 5, vpravo 3, nečistota 0.200
tikety <= 4.0  vlevo 6, vpravo 2, nečistota 0.333
tikety <= 5.5  vlevo 7, vpravo 1, nečistota 0.429
Úkol

Gini pro libovolný počet tříd

Napiš funkci gini(y) pro libovolné třídy, i textové: 1 minus součet druhých mocnin podílů jednotlivých tříd. Hodí se np.unique(y, return_counts=True).

import numpy as np

def gini(y):
    # doplň
    return None
Výstup
Najdi chybu

Strom miluje drobečky

Funkce má najít práh s nejnižší váženou nečistotou. Na těchto datech má vyjít 6,5, tedy oddělit dlouhou řadu nul. Vybírá ale práh 9,5, který odřízne jediný příklad.

Strom od nuly

Celý algoritmus je rekurze: najdi nejlepší otázku, rozděl data a na každou část zavolej totéž. Zastav se, když je skupina čistá, když už nejde dělit, nebo když dojdeš do maximální hloubky. Hloubka je počet otázek na nejdelší cestě a můžeš ji měnit posuvníkem.

import numpy as np

JMENA = ["mesice", "tikety"]

def gini(y):
    p = y.mean()
    return 1 - p ** 2 - (1 - p) ** 2

def nejlepsi_rez(X, y):
    nejlepsi = (np.inf, None, None)
    for j in range(X.shape[1]):
        hodnoty = np.unique(X[:, j])
        for t in (hodnoty[:-1] + hodnoty[1:]) / 2:
            m = X[:, j] <= t
            s = m.mean() * gini(y[m]) + (1 - m.mean()) * gini(y[~m])
            if s < nejlepsi[0]:
                nejlepsi = (s, j, t)
    return nejlepsi[1], nejlepsi[2]

def postav(X, y, hloubka, limit):
    j, t = (None, None)
    if hloubka < limit and 0 < y.mean() < 1:
        j, t = nejlepsi_rez(X, y)
    if j is None:
        return {"p": y.mean(), "n": len(y)}
    m = X[:, j] <= t
    return {"j": j, "t": t,
            "ano": postav(X[m], y[m], hloubka + 1, limit),
            "ne": postav(X[~m], y[~m], hloubka + 1, limit)}

def vypis(uzel, odsazeni=""):
    if "p" in uzel:
        print(f"{odsazeni}-> odejde {uzel['p']:.0%} z {uzel['n']}")
        return
    print(f"{odsazeni}{JMENA[uzel['j']]} <= {uzel['t']}?")
    vypis(uzel["ano"], odsazeni + "  ")
    vypis(uzel["ne"], odsazeni + "  ")

np.random.seed(4)
n = 300
mesice = np.random.randint(1, 37, n)
tikety = np.random.randint(0, 9, n)
y = ((tikety > 4) | ((mesice <= 6) & (tikety > 1))).astype(float)
sum = np.random.random(n) < 0.1
y[sum] = 1 - y[sum]

X = np.column_stack([mesice, tikety])
vypis(postav(X, y, 0, int(max_hloubka)))
Výstup
tikety <= 4.5?
  mesice <= 7.5?
    -> odejde 52% z 29
    -> odejde 10% z 124
  mesice <= 11.5?
    -> odejde 72% z 43
    -> odejde 90% z 104

Do dat jsme schovali pravidlo ze začátku lekce a 10 % náhodně přehozených odpovědí. Strom pravidlo najde jen z příkladů. S větší hloubkou ale začne přibývat větví, které jen vysvětlují šum.

Slož kód

Slož stavbu stromu

Slož funkci tak, aby se nejdřív ověřila podmínka zastavení, potom se našel řez a rekurzí vznikly obě větve.

Přeučení v přímém přenosu

Strom bez omezení se dá dělit tak dlouho, až má každý trénovací příklad vlastní list. Na trénovacích datech pak skoro nedělá chyby, ale naučil se i náhodu. Tomu se říká přeučení (podrobně v lekci o přeučení). Stejná data, různé hloubky:

import numpy as np

def gini(y):
    p = y.mean()
    return 1 - p ** 2 - (1 - p) ** 2

def nejlepsi_rez(X, y):
    nejlepsi = (np.inf, None, None)
    for j in range(X.shape[1]):
        hodnoty = np.unique(X[:, j])
        for t in (hodnoty[:-1] + hodnoty[1:]) / 2:
            m = X[:, j] <= t
            s = m.mean() * gini(y[m]) + (1 - m.mean()) * gini(y[~m])
            if s < nejlepsi[0]:
                nejlepsi = (s, j, t)
    return nejlepsi[1], nejlepsi[2]

def postav(X, y, hloubka, limit):
    j, t = (None, None)
    if hloubka < limit and 0 < y.mean() < 1:
        j, t = nejlepsi_rez(X, y)
    if j is None:
        return y.mean()
    m = X[:, j] <= t
    return j, t, postav(X[m], y[m], hloubka + 1, limit), postav(X[~m], y[~m], hloubka + 1, limit)

def predikuj(uzel, X):
    if not isinstance(uzel, tuple):
        return np.full(len(X), uzel)
    j, t, ano, ne = uzel
    m = X[:, j] <= t
    vysledek = np.empty(len(X))
    vysledek[m] = predikuj(ano, X[m])
    vysledek[~m] = predikuj(ne, X[~m])
    return vysledek

def data(n):
    mesice = np.random.randint(1, 37, n)
    tikety = np.random.randint(0, 9, n)
    y = ((tikety > 4) | ((mesice <= 6) & (tikety > 1))).astype(float)
    sum = np.random.random(n) < 0.15
    y[sum] = 1 - y[sum]
    return np.column_stack([mesice, tikety]), y

np.random.seed(4)
X_tr, y_tr = data(200)
X_te, y_te = data(1000)

print("hloubka  trénink  test")
for h in [1, 2, 3, 4, 6, 8, 12]:
    strom = postav(X_tr, y_tr, 0, h)
    tr = np.mean((predikuj(strom, X_tr) >= 0.5) == y_tr)
    te = np.mean((predikuj(strom, X_te) >= 0.5) == y_te)
    print(f"{h:>7}  {tr:.3f}    {te:.3f}")
Výstup
hloubka  trénink  test
      1  0.810    0.799
      2  0.820    0.790
      3  0.825    0.809
      4  0.840    0.835
      6  0.855    0.816
      8  0.855    0.768
     12  0.915    0.736

Trénovací přesnost s hloubkou neklesá, jen roste. Na testu to tak není: hledej hloubku, kde se testovací číslo zastaví nebo začne klesat. Od té chvíle si strom pamatuje šum.

Kvíz

Strom má na trénovacích datech přesnost 100 % a na testu výrazně méně. Co pomůže nejspíš?

Náhodný les

Jeden hluboký strom je nestabilní: změníš pár řádků a vyroste jiný. Jeho chyby jsou ale z velké části náhodné a náhodné chyby se průměrováním ruší. Stejně jako průměr tipů celé hospody na váhu prasete bývá lepší než tip většiny jednotlivců.

Aby stromy nebyly stejné, les do nich přidá dvojí náhodu:

  1. Bootstrap: každý strom dostane vlastní vzorek dat, losovaný s vracením. Některé řádky se opakují, jiné chybí. Spolu s hlasováním se tomu říká bagging.
  2. Náhodné příznaky: při každém dělení smí strom vybírat jen z náhodné podmnožiny příznaků.

Druhý bod vypadá jako zbytečné omezování, ale je klíčový. Průměr pomáhá tím víc, čím méně si jsou stromy podobné, a číslo níže to ukazuje: rho je podobnost (korelace) chyb.

import numpy as np

np.random.seed(0)
n = 100000
vzorky = np.random.randint(0, n, n)
print(f"podíl různých řádků v bootstrapu: {len(np.unique(vzorky)) / n:.3f}")
print()

print("rho   chyba 1 stromu   chyba průměru 25 stromů")
for rho in [0.0, 0.3, 0.7, 0.95]:
    spolecna = np.random.normal(size=(20000, 1))
    vlastni = np.random.normal(size=(20000, 25))
    chyby = np.sqrt(rho) * spolecna + np.sqrt(1 - rho) * vlastni
    print(f"{rho:<4}  {chyby[:, 0].std():.3f}            {chyby.mean(axis=1).std():.3f}")
Výstup
podíl různých řádků v bootstrapu: 0.633

rho   chyba 1 stromu   chyba průměru 25 stromů
0.0   0.998            0.198
0.3   0.997            0.570
0.7   0.996            0.839
0.95  0.990            0.966

Asi třetina řádků se do vzorku nedostane. Zapamatuj si to, hned se to bude hodit. A druhá část: při nulové podobnosti průměr chybu srazí na pětinu (odmocnina z 25), při vysoké podobnosti skoro nepomůže.

Doplň

Doplň bootstrap

Vylosuj n indexů z rozsahu 0 až n - 1 s vracením a najdi řádky, které se do vzorku nedostaly.

Teď les od nuly. Data mají pět příznaků, ale jen dva rozhodují (kruh v prvních dvou sloupcích), a 15 % odpovědí je přehozených. Každý strom roste do velké hloubky a při každém dělení vidí dva náhodné příznaky.

import numpy as np

KVANTILY = np.linspace(0.1, 0.9, 9)

def gini(y):
    p = y.mean()
    return 1 - p ** 2 - (1 - p) ** 2

def rez(X, y, pocet_priznaku):
    nejlepsi = (np.inf, None, None)
    for j in np.random.permutation(X.shape[1])[:pocet_priznaku]:
        for t in np.unique(np.quantile(X[:, j], KVANTILY)):
            m = X[:, j] <= t
            if m.all() or not m.any():
                continue
            s = m.mean() * gini(y[m]) + (1 - m.mean()) * gini(y[~m])
            if s < nejlepsi[0]:
                nejlepsi = (s, j, t)
    return nejlepsi[1], nejlepsi[2]

def strom(X, y, pocet_priznaku, hloubka=0):
    if hloubka == 10 or len(y) < 2 or y.min() == y.max():
        return y.mean()
    j, t = rez(X, y, pocet_priznaku)
    if j is None:
        return y.mean()
    m = X[:, j] <= t
    return (j, t, strom(X[m], y[m], pocet_priznaku, hloubka + 1),
            strom(X[~m], y[~m], pocet_priznaku, hloubka + 1))

def predikuj(uzel, X):
    if not isinstance(uzel, tuple):
        return np.full(len(X), uzel)
    j, t, ano, ne = uzel
    m = X[:, j] <= t
    vysledek = np.empty(len(X))
    vysledek[m] = predikuj(ano, X[m])
    vysledek[~m] = predikuj(ne, X[~m])
    return vysledek

def data(n):
    X = np.random.normal(size=(n, 5))
    y = (X[:, 0] ** 2 + X[:, 1] ** 2 < 1.4).astype(float)
    sum = np.random.random(n) < 0.15
    y[sum] = 1 - y[sum]
    return X, y

np.random.seed(0)
X_tr, y_tr = data(300)
X_te, y_te = data(1000)

jeden = predikuj(strom(X_tr, y_tr, 5), X_te)
print(f"jeden plný strom:  {np.mean((jeden >= 0.5) == y_te):.3f}")

soucet = np.zeros(len(X_te))
for i in range(1, 26):
    idx = np.random.randint(0, len(X_tr), len(X_tr))
    soucet += predikuj(strom(X_tr[idx], y_tr[idx], 2), X_te)
    if i in (1, 5, 10, 25):
        print(f"les, {i:>2} stromů:     {np.mean((soucet / i >= 0.5) == y_te):.3f}")
Výstup
jeden plný strom:  0.715
les,  1 stromů:     0.612
les,  5 stromů:     0.697
les, 10 stromů:     0.719
les, 25 stromů:     0.752

Sleduj, jak se přesnost lesa s počtem stromů zlepšuje. Přidávání stromů přeučení nezhoršuje, jen se zmenšuje přínos a roste čas.

Úkol

Hlasování lesa

Matice hlasy má řádek pro každý strom a sloupec pro každý příklad, hodnoty jsou 0 a 1. Napiš funkci hlasuj(hlasy), která vrátí pole výsledků po sloupcích: 1, když pro ni hlasuje aspoň polovina stromů, jinak 0.

import numpy as np

def hlasuj(hlasy):
    hlasy = np.asarray(hlasy)
    # doplň
    return np.zeros(hlasy.shape[0])
Výstup

scikit-learn a důležitost příznaků

Knihovna dělá totéž v rychlém Cythonu. Řádky, které strom při bootstrapu nedostal, slouží jako bezplatný test: parametr oob_score=True (out-of-bag) ohodnotí každý příklad jen stromy, které ho neviděly.

from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

data = load_breast_cancer()
X_tr, X_te, y_tr, y_te = train_test_split(
    data.data, data.target, stratify=data.target, random_state=0
)

strom = DecisionTreeClassifier(random_state=0).fit(X_tr, y_tr)
maly = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X_tr, y_tr)
les = RandomForestClassifier(n_estimators=100, oob_score=True, random_state=0).fit(X_tr, y_tr)

print(f"plný strom: hloubka {strom.get_depth()}, listů {strom.get_n_leaves()}")
print(f"  trénink {strom.score(X_tr, y_tr):.3f}, test {strom.score(X_te, y_te):.3f}")
print(f"les:        trénink {les.score(X_tr, y_tr):.3f}, test {les.score(X_te, y_te):.3f}")
print(f"  odhad OOB {les.oob_score_:.3f}")
print()
print(export_text(maly, feature_names=list(data.feature_names)))
Výstup
plný strom: hloubka 5, listů 18
  trénink 1.000, test 0.902
les:        trénink 0.998, test 0.944
  odhad OOB 0.960

|--- worst perimeter <= 106.10
|   |--- worst concave points <= 0.13
|   |   |--- class: 1
|   |--- worst concave points >  0.13
|   |   |--- class: 0
|--- worst perimeter >  106.10
|   |--- worst concave points <= 0.14
|   |   |--- class: 0
|   |--- worst concave points >  0.14
|   |   |--- class: 0

Hledej dvě věci: plný strom má na tréninku plný počet bodů, a odhad OOB má ležet blízko testovací přesnosti lesa, i když testovací data nikdy neviděl.

Les prozradí, které příznaky používá. Pozor, výchozí feature_importances_ měří, jak moc příznak čistil skupiny na trénovacích datech, a přeceňuje sloupce s mnoha různými hodnotami. Spolehlivější je permutační důležitost: zamíchej jeden sloupec testovacích dat a sleduj, o kolik se model zhorší. Přidáme sloupec čistého šumu jako kontrolu.

import numpy as np
from sklearn.datasets import load_wine
from sklearn.ensemble import RandomForestClassifier
from sklearn.inspection import permutation_importance
from sklearn.model_selection import train_test_split

data = load_wine()
rng = np.random.RandomState(0)
X = np.column_stack([data.data, rng.random_sample(len(data.data))])
nazvy = list(data.feature_names) + ["NAHODNY_SUM"]

X_tr, X_te, y_tr, y_te = train_test_split(X, data.target, stratify=data.target, random_state=0)
les = RandomForestClassifier(n_estimators=50, random_state=0).fit(X_tr, y_tr)

perm = permutation_importance(les, X_te, y_te, n_repeats=5, random_state=0)
print(f"{'příznak':<30}{'z nečistoty':>12}{'permutační':>12}")
poradi = np.argsort(les.feature_importances_)[::-1]
for i in list(poradi[:4]) + [nazvy.index("NAHODNY_SUM")]:
    print(f"{nazvy[i]:<30}{les.feature_importances_[i]:>12.3f}{perm.importances_mean[i]:>12.3f}")
Výstup
příznak                        z nečistoty  permutační
proline                              0.171       0.076
od280/od315_of_diluted_wines         0.166       0.040
color_intensity                      0.151       0.062
flavanoids                           0.132       0.009
NAHODNY_SUM                          0.002       0.000

Šumový sloupec dostane z nečistoty nenulovou důležitost, přestože nic neznamená. Permutační hodnota by u něj měla být kolem nuly.

Úkol

Les s odhadem OOB

Natrénuj na datech X, y model les: RandomForestClassifier s 50 stromy, oob_score=True a random_state=0. Do proměnné odhad ulož jeho OOB skóre.

from sklearn.datasets import load_wine
from sklearn.ensemble import RandomForestClassifier

X, y = load_wine(return_X_y=True)
les = None
odhad = None
Výstup
Roztřiď

Co přeučení brzdí?

Zařaď změny nastavení jednoho rozhodovacího stromu.

Pod kapotou · CART v praxi: složitost, extrapolace a kalibrace

Složitost. Hledání řezu v uzlu s n řádky a d příznaky stojí řazením O(d · n log n). Po seřazení jde nečistota aktualizovat inkrementálně, proto nejsou potřeba tisíce průchodů jako v našem naivním kódu. Vyvážený strom má O(log n) úrovní. Předpověď je O(hloubka). scikit-learn navíc u lesa uvolňuje GIL, takže n_jobs=-1 paralelizuje vlákny bez kopírování dat.

Hladovost. CART volí nejlepší řez teď a nedívá se dopředu. Najít optimální strom je NP-úplné. Čistý XOR nedává na prvním řezu žádný zisk. Proto scikit-learn ve výchozím stavu dovolí řez i s nulovým zlepšením (min_impurity_decrease=0), jinak by se strom zastavil hned v kořeni.

Gini vs. entropie. V praxi vedou k velmi podobným stromům. Gini nepotřebuje logaritmus.

Stromy neextrapolují. List vrací průměr trénovacích hodnot, takže predikce regresního lesa nikdy nepřekročí rozsah trénovacího y. U dat s trendem (ceny v čase) je to tichá a drahá chyba.

import numpy as np
from sklearn.ensemble import RandomForestRegressor
from sklearn.linear_model import LinearRegression

X = np.arange(0, 10, 0.1).reshape(-1, 1)
y = 2 * X.ravel()

les = RandomForestRegressor(n_estimators=50, random_state=0).fit(X, y)
primka = LinearRegression().fit(X, y)

for x in [5.0, 15.0, 100.0]:
    bod = [[x]]
    print(f"x={x:<6} les {les.predict(bod)[0]:6.2f}   přímka {primka.predict(bod)[0]:7.2f}")
Výstup
x=5.0    les   9.94   přímka   10.00
x=15.0   les  19.66   přímka   30.00
x=100.0  les  19.66   přímka  200.00

Pravděpodobnosti lesa jsou průměry podílů v listech a často bývají stlačené od 0 a 1. Když je používáš jako pravděpodobnost, zkontroluj kalibraci.

Paměť a latence. Plně rostlé stromy mají počet uzlů úměrný n. Les se stovkami stromů se serializuje do stovek MB. Omezení přes min_samples_leaf často zmenší model řádově a přesnost skoro nezmění.

Chybějící hodnoty. DecisionTreeClassifier je podporuje od verze 1.3, RandomForestClassifier od 1.4. Řádky s NaN jdou při řezu celé do jedné větve. OOB je odhad bez sady navíc, ale neposkytne ochranu při časových datech, kde musí test ležet až po tréninku.

Kartičky

Opakování

Vyzkoušej si: Jak strom dělí data

Zvyšuj hloubku stromu a sleduj oblasti, dělení a Giniho nečistotu.