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:
tikety <= 4 ?
/ \
ano ne
/ \
mesice <= 6 ? ODEJDE
/ \
ano ne
/ \
tikety <= 1 ? ZŮSTANE
/ \
ZŮSTANE ODEJDEKaž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))
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:
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}")
č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}")
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
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
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)))
tikety <= 4.5?
mesice <= 7.5?
-> odejde 52% z 29
-> odejde 10% z 124
mesice <= 11.5?
-> odejde 72% z 43
-> odejde 90% z 104Do 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ž 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}")
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.736Tré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.
Strom má na trénovacích datech přesnost 100 % a na testu výrazně méně. Co pomůže nejspíš?
Strom se přeučil. Standardizace na něj nemá vliv, protože pořadí hodnot zůstává stejné.
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:
- 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.
- 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}")
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ň 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}")
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.
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])
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)))
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}")
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.
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
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}")
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.
Opakování
Vyzkoušej si: Jak strom dělí data
Zvyšuj hloubku stromu a sleduj oblasti, dělení a Giniho nečistotu.