Rozhodovací stromy a k nejbližších sousedů: modely bez vzorců

Kdo splatí půjčku: rozhodovací strom a Giniho nečistota, hloubka a přeučení, schodovité hranice, k nejbližších sousedů, volba k a proč u sousedů záleží na měřítku příznaků.

13 minut Matěj Žalmánek 2026-10-16

Série Základy AI Díl 53 z 83

Celá osnova série 83 z 83 témat hotovo

Co si odnesete

Jak rozhodovací strom vybírá otázky a proč se hluboký strom přeučí.
Jak předpovídá k nejbližších sousedů a jak zvolit k.
Proč kNN potřebuje standardizované příznaky a strom ne — a kdy použít který model.

Co se hodí znát předem: Klasifikace a regrese: dvě úlohy učení s učitelem, Přeučení a regularizace: proč model, který zná data nazpaměť, selže

Lineární a logistická regrese vysvětlují svět vahami: „každý metr přidá 88 tisíc“. Jsou ale modely, které se vysvětlují ještě snáz — bez jediného vzorce. Rozhodovací strom se ptá jako lékař: „Máte horečku? Ano. Bolí vás v krku? Ne. …“ A metoda k nejbližších sousedů dělá to, co dělá každý realitní makléř: „Byt jako tenhle se v téhle ulici prodal za…“. Oba modely umí hranice, které nejsou přímka, a oba mají svou slabinu, kterou je dobré znát.

Navazuje na díly Klasifikace a regrese a Přeučení a regularizace.

1. Úloha: kdo splatí půjčku

Banka má 200 bývalých klientů: u každého zná měsíční příjem (15–90 tisíc Kč), věk (20–70 let) a jestli půjčku splatil. Splatilo 70 %. Data jsou vygenerovaná: šance na splacení roste s příjmem i věkem, takže skutečná hranice mezi „spíš splatí“ a „spíš nesplatí“ je šikmá přímka — vyšší věk vyváží nižší příjem. I model, který by tu přímku znal přesně, se na nových klientech trefí jen v 91,5 % případů; zbytek je náhoda, kterou z příjmu a věku nevyčteme. Úspěch měříme na 4 000 nových klientech.

Data vznikla z tohoto předpisu (model ho samozřejmě nezná, má jen 200 vylosovaných klientů):

P(splatí | příjem, věk) = σ( příjem − 40/5 + věk − 35/7 )

σ(z) = 1/1 + e^−z: sigmoida z dílu o logistické regresi; převede libovolné skóre na číslo mezi 0 a 1, aby šlo o pravděpodobnost. Skóre 0 dá přesně 50 %
příjem − 40/5: příspěvek příjmu (v tisících Kč): 40 tisíc je neutrální bod a každých 5 tisíc navíc přidá skóre 1 — proto šance s příjmem roste
věk − 35/7: příspěvek věku: neutrální je 35 let a skóre 1 přidá každých 7 let. Protože se oba příspěvky sčítají, může vyšší věk vyvážit nižší příjem

Skutečná hranice je tam, kde je skóre 0, tedy příjem/5 + věk/7 = 8 + 5 = 13 — přímka v rovině příjem × věk.

Příklad — kde vede skutečná hranice a jak jistý je jeden klient

hranice pro 30 let: příjem = 5 · (13 − 30/7) = 5 · 8,714 = 43,6 tis. Kč

hranice pro 60 let: příjem = 5 · (13 − 60/7) = 5 · 4,429 = 22,1 tis. Kč

klient s příjmem 35 tisíc, 50 let: skóre = 35 − 40/5 + 50 − 35/7 = −1 + 2,143 = 1,143, σ(1,143) = 75,8 %

Barvy odpovídají členům vzorce výše.

Ani u tohoto klienta tedy splacení není jisté: v 24 % případů takoví klienti nesplatí, ať je model jakkoli dobrý.

Definice — Bayesův klasifikátor a strop přesnosti

Nechť (X, Y) je náhodný vektor, kde X nabývá hodnot v množině příznaků 𝒳 (u nás 𝒳 ⊆ ℝ²: příjem a věk) a Y ∈ {0, 1} je třída (1 = splatí). Pro x ∈ 𝒳 označme

p(x) = P(Y = 1 | X = x)

skutečnou pravděpodobnost třídy 1 v bodě x. Klasifikátor je libovolná funkce h : 𝒳 → {0, 1}; jeho přesnost je P(h(X) = Y). Bayesův klasifikátor je klasifikátor

h*(x) = 1, právě když p(x) > 1/2 (jinak h*(x) = 0).

V bodě x se trefí s pravděpodobností P(h*(X) = Y | X = x) = max(p(x), 1 − p(x)), a pro každý klasifikátor h platí P(h(X) = Y | X = x) ∈ {p(x), 1 − p(x)}, tedy nejvýš totéž. Proto P(h*(X) = Y) ≥ P(h(X) = Y) pro všechny klasifikátory h, které o klientovi znají jen x: přesnost Bayesova klasifikátoru je horní mez (strop) pro všechny modely. Číslo 1 − P(h*(X) = Y) = E[min(p(X), 1 − p(X))] se jmenuje Bayesova chyba. Na našich 4 000 nových klientech má Bayesův klasifikátor přesnost 91,5 %.

2. Rozhodovací strom

Definice — rozhodovací strom

Nechť d ≥ 1 je počet příznaků, x = (x₁, …, x_d) ∈ ℝ^d vektor příznaků a 𝒞 množina možných předpovědí (konečná množina tříd v klasifikaci, ℝ v regresi). Rozhodovací strom je konečný kořenový strom (viz díl Grafy a stromy), ve kterém

každý vnitřní uzel u má právě dva potomky, „ano“ a „ne“, a nese test „x_j(u) ≤ t(u)?“ s indexem příznaku j(u) ∈ {1, …, d} a prahem t(u) ∈ ℝ;
každý list v nese předpověď c(v) ∈ 𝒞.

Předpověď stromu T pro x ∈ ℝ^d je T(x) = c(v), kde v je list, do kterého vede cesta z kořene, na níž se z každého vnitřního uzlu u pokračuje do potomka „ano“, právě když x_j(u) ≤ t(u), a jinak do potomka „ne“.

Při učení na trénovacích datech (x₁, y₁), …, (x_n, y_n) označme D_v množinu indexů příkladů, které do listu v spadnou (předpokládáme D_v ≠ ∅). V klasifikaci je c(v) nejčastější třída mezi y_i, i ∈ D_v; v regresi jejich průměr c(v) = 1/|D_v| ∑_{i ∈ D_v} y_i.

Strom tedy rozdělí prostor příznaků na obdélníkové oblasti (jedna za každý list) a v každé předpovídá jednu hodnotu.

Laicky řečeno

Hra na dvacet otázek, kde se smí ptát jen „je to číslo menší než…?“. Každá odpověď pošle klienta doleva nebo doprava, až skončí v listu s verdiktem. Celý model se dá vytisknout na papír a bankovní úředník podle něj rozhodne bez počítače — a klientovi vysvětlí proč.

Strom hloubky 2 naučený na 200 klientech

První otázka se ptá na příjem: z klientů s příjmem do 39,5 tisíce splácí jen 26 %, z ostatních 97 %. Mezi chudšími pak rozhoduje věk: do 47,6 let splácí jen 9 %, starší v 55 %. Vpravo strom dělí ještě jednou, ale obě větve předpovídají „splatí“ — rozdělení vyčistilo skupiny (86 % a 100 %), ale rozhodnutí nezměnilo.

Algoritmus — předpověď stromem

def predpovez(uzel, x):
    while not uzel.je_list:
        if x[uzel.priznak] <= uzel.prah:   # odpověď „ano“
            uzel = uzel.ano
        else:                               # odpověď „ne“
            uzel = uzel.ne
    return uzel.trida                       # nejčastější třída v listu

Předpověď stojí nejvýš tolik porovnání, kolik je hloubka stromu — u stromu hloubky 2 dvě, ať je trénovacích klientů kolik chce.

Příklad — klient s příjmem 35 tisíc a věkem 50 let

kořen: příjem 35 ≤ 39,5? ano → levá větev (76 klientů, splácí 20, tedy 26 %)

uzel: věk 50 ≤ 47,6? ne → list s 29 klienty, z nich splácí 16, tedy 55 %

16/29 > 1/2, předpověď: splatí

Skutečná pravděpodobnost je u tohoto klienta 75,8 % (příklad výše). List o ní ví jen hrubě — všichni chudší klienti nad 47,6 let v něm dostanou stejných 55 %.

3. Jak strom roste: Giniho nečistota

Definice — Giniho nečistota a hladové dělení

Nechť K ≥ 2 je počet tříd, třídy jsou 1, …, K, a D je konečná neprázdná množina příkladů (x, y) s x ∈ ℝ^d a y ∈ {1, …, K}. Pro k = 1, …, K nechť

p_k = |{(x, y) ∈ D : y = k}|/|D|

je podíl příkladů třídy k v D. Giniho nečistota množiny D je číslo

G(D) = 1 − ∑_k=1^K p_k².

Pro dvě třídy s p = p₁ je G(D) = 2p(1 − p). Vždy 0 ≤ G(D) ≤ 1 − 1/K; G(D) = 0, právě když jsou všechny příklady v D z jedné třídy (D je čistá), a pro dvě třídy je největší, 0,5, právě když p = 1/2.

Dělení množiny D podle příznaku j ∈ {1, …, d} a prahu t ∈ ℝ jsou množiny L = {(x, y) ∈ D : x_j ≤ t} a P = D ∖ L; jeho nečistota je vážený průměr

G_dělení(j, t) = |L|/|D| G(L) + |P|/|D| G(P) (pro prázdnou část je příslušný sčítanec 0).

Algoritmus CART (hladové dělení) staví strom shora:

Vstup: konečná neprázdná množina trénovacích příkladů D a maximální hloubka h ∈ ℕ₀.
Výstup: rozhodovací strom hloubky nejvýš h.

Je-li h = 0 nebo G(D) = 0, vrať list s nejčastější třídou v D.
Pro každý příznak j a každý práh t ležící uprostřed mezi dvěma sousedními různými hodnotami x_j v D spočítej G_dělení(j, t).
Vyber dvojici (j*, t*) s nejmenší G_dělení. Neexistuje-li žádný práh, nebo je-li G_dělení(j*, t*) ≥ G(D), vrať list jako v kroku 1.
Jinak vrať uzel s testem „x_j* ≤ t*?“, jehož potomek „ano“ vznikne rekurzivně z (L, h − 1) a potomek „ne“ z (P, h − 1).

Každé rekurzivní volání sníží h o 1, takže algoritmus skončí nejpozději v hloubce h (nebo dřív, když jsou všechny části čisté). Strom tedy v každém uzlu vybere dělení s nejmenší váženou nečistotou obou částí a totéž pak opakuje v každé části zvlášť.

Laicky řečeno

Giniho nečistota je pravděpodobnost, že se splete člověk, který náhodně vybranému klientovi ze skupiny přidělí štítek naslepo, losem podle podílů ve skupině. Strom hledá otázku, po které budou obě skupiny co nejčistší. V kořeni má nečistotu 0,420 (70 % splácí). Po otázce na příjem klesne vážená nečistota na 0,186 — nejvíc ze všech možných otázek. Strom je hladový: vybírá vždy nejlepší otázku teď a nedívá se dopředu.

G = 1 − ∑_k p_k² = ∑_k p_k · (1 − p_k)

1: součet všech podílů ∑ p_k; od něj se odečítá pravděpodobnost „trefy“, takže zbude pravděpodobnost omylu
p_k²: pravděpodobnost, že náhodný klient patří do třídy k a zároveň mu los přidělí štítek k — dvě nezávislá losování se stejnou pravděpodobností, proto čtverec
p_k: pravděpodobnost, že klient je ve skutečnosti ze třídy k
1 − p_k: pravděpodobnost, že mu los přidělí jinou třídu — tedy omyl. Součet přes třídy dá celkovou pravděpodobnost omylu

Obě strany se rovnají, protože ∑ p_k(1 − p_k) = ∑ p_k − ∑ p_k² = 1 − ∑ p_k². Pro dvě třídy je to p(1 − p) + (1 − p)p = 2p(1 − p).

Dělení se hodnotí váženým průměrem nečistot obou částí:

G_dělení = n_L/n · G(L) + n_P/n · G(P)

n_L/n: podíl klientů, kteří odpověděli „ano“ a šli doleva; váha zajistí, že velká skupina rozhoduje víc než malá
G(L): nečistota levé skupiny — jak moc se v ní ještě mísí ti, kdo splácí, s těmi, kdo ne
n_P/n: podíl klientů v pravé skupině; bez vah by otázka, která odřízne jediného „čistého“ klienta, vypadala skvěle
G(P): nečistota pravé skupiny

Je to pravděpodobnost omylu losujícího úředníka, který už ví, do které skupiny klient patří. Strom volí otázku, po které je nejmenší.

Příklad — první otázka stromu, přepočítaná

kořen: 200 klientů, splácí 140, p = 140/200 = 0,7, G = 2 · 0,7 · 0,3 = 0,420

příjem ≤ 39,5: 76 klientů, splácí 20, p = 20/76 = 0,263, G(L) = 2 · 0,263 · 0,737 = 0,388

příjem > 39,5: 124 klientů, splácí 120, p = 120/124 = 0,968, G(P) = 2 · 0,968 · 0,032 = 0,062

G_dělení = 76/200 · 0,388 + 124/200 · 0,062 = 0,147 + 0,039 = 0,186

Barvy v prvních třech řádcích odpovídají vzorci pro G (p_k, 1 − p_k; dvojka je tam proto, že pro dvě třídy jsou oba sčítance stejné), v posledním řádku vzorci pro G_dělení.

Nejlepší otázka na věk („věk ≤ 39,5?“) by dala jen 0,377 — proto se strom nejdřív ptá na příjem. Práh 39,5 leží v polovině mezi dvěma sousedními příjmy v datech, 38,25 a 40,83 tisíce: každý práh mezi nimi rozdělí klienty stejně, střed je jen dohoda.

Algoritmus — CART (růst stromu)

def postav(D, hloubka):
    if hloubka == 0 or D je čistá:
        return List(nejčastější třída v D)
    nejlepsi = None
    for j in příznaky:                         # u nás příjem a věk
        seřaď D podle x[j]
        for práh in středy mezi sousedními hodnotami x[j]:
            L = [d in D if d.x[j] <= práh];  P = zbytek
            g = len(L)/len(D) * G(L) + len(P)/len(D) * G(P)
            if nejlepsi is None or g < nejlepsi.g:
                nejlepsi = (j, práh, g)
    if nejlepsi.g >= G(D):                  # dělení nic nezlepší
        return List(nejčastější třída v D)
    return Uzel(j, práh, ano=postav(L, hloubka − 1), ne=postav(P, hloubka − 1))

Pro n klientů a d příznaků stojí hledání v jednom uzlu řádově d · n log n operací (třídění); nečistotu pro všechny prahy jde spočítat jedním průchodem setříděnými daty, když se průběžně počítá, kolik splácejících už je vlevo.

4. Hloubka a přeučení

Strom se dá nechat růst, dokud nejsou všechny listy čisté. Tím si ale zapamatuje i šum:

Rozhodovací oblasti stromu; čárkovaně skutečná hranice

Přesnost podle hloubky stromu (vlevo) a podle počtu sousedů (vpravo) trénink noví klienti strop 91,5 %

Strom hloubky 1 má jedinou otázku a přesnost 84,7 %. Nejlepší na nových klientech je hloubka 3: sedm listů a 89,5 %. Od hloubky 7 má strom 25 listů, na trénovacích datech se nemýlí ani jednou — a na nových klientech klesne na 86,5 %. Na obrázku vpravo jsou vidět listy kolem jednotlivých „podivných“ klientů: strom pro ně vykrojil vlastní obdélníček. Proti přeučení se strom omezuje maximální hloubkou, minimálním počtem příkladů v listu, nebo se nechá vyrůst a pak prořeže.

Věta — strom hloubky h má nejvýš 2^h listů

Hloubka rozhodovacího stromu je počet vnitřních uzlů (otázek) na nejdelší cestě z kořene do listu. Nechť h ∈ ℕ₀ a T je rozhodovací strom hloubky h. Pak T má nejvýš 2^h listů.

Každý vnitřní uzel má dva potomky, takže na úrovni i je nejvýš 2ⁱ uzlů a listů je nejvýš 2^h. Důkaz indukcí: strom hloubky 0 je jediný list; strom hloubky h je kořen a dva podstromy hloubky nejvýš h − 1, každý s nejvýš 2^h−1 listy. ∎

U nás: hloubka 3 smí mít 8 listů a má jich 7 (skupina 96 klientů s příjmem nad 51,7 tisíce už po druhé otázce splácí celá, takže se dál nedělí). Hloubka 7 by smila 128, ale stačí 25 — pak jsou všechny listy čisté a dál se nedělí; proto má strom od hloubky 7 výš pořád 25 listů a pořád 86,5 %.

Definice — prořezávání podle ceny za složitost

Nechť T₀ je plně vyrostlý rozhodovací strom. Prořezáním T₀ rozumíme každý strom T, který vznikne z T₀ tak, že se některé vnitřní uzly i s celými svými podstromy nahradí listy (píšeme T ⪯ T₀). Pro strom T označme |T| počet jeho listů a R(T) ∈ [0, 1] jeho chybu (podíl chybně zařazených příkladů) na trénovacích datech. Pro parametr α ≥ 0 je cena za složitost

R_α(T) = R(T) + α · |T|

a prořezávání podle ceny za složitost hledá strom T_α = argmin_{T ⪯ T₀} R_α(T). Hledá se postupným odstraňováním „nejslabšího článku“: pro každý vnitřní uzel u aktuálního stromu T označme T_u jeho podstrom a R(u) chybu stromu, ve kterém je T_u slitý do jediného listu, a spočítejme

g(u) = R(u) − R(T)/|T_u| − 1,

tj. o kolik se zvýší chyba na jeden ušetřený list. Slije se uzel s nejmenším g(u) a postup se opakuje, dokud nezbude jen kořen; z takto vzniklé posloupnosti stromů je T_α pro každé α jeden z členů. Parametr α se volí křížovou validací. Postup pochází z knihy Classification and Regression Trees (Breiman, Friedman, Olshen, Stone, 1984), která dala algoritmu CART jméno.

Laicky řečeno

Každý list stojí „pokutu“ α. List, který opravuje chybu jen u jednoho podivného klienta, si pokutu nevydělá, a tak ho prořezávání odstraní. Je to stejný nápad jako regularizace z dílu o přeučení: chyba na trénovacích datech plus cena za složitost.

5. Strom vidí jen svisle a vodorovně

Každá otázka stromu se týká jednoho příznaku, takže hranice jsou vždy svislé nebo vodorovné. Šikmou hranici „vyšší věk vyváží nižší příjem“ proto strom umí jen jako schody — a každý schod stojí list. Logistická regrese by tu samou hranici popsala třemi čísly. Strom se zase hodí tam, kde hranice opravdu vede po osách („dospělý a s příjmem“) nebo kde se příznaky kombinují složitě a nepravidelně. Díl o ansámblech ukáže, jak schody vyhladit tím, že se stovky stromů zprůměrují.

6. k nejbližších sousedů

Definice — k nejbližších sousedů (kNN)

Nechť (x₁, y₁), …, (x_n, y_n) jsou trénovací data s x_i ∈ ℝ^d a y_i ∈ 𝒞 (konečná množina tříd, v regresi ℝ), nechť δ : ℝ^d × ℝ^d → [0, ∞) je vzdálenost (obvykle eukleidovská, viz níže; v rozboru ji značíme d(x, x′)) a k ∈ {1, …, n}. Pro x ∈ ℝ^d je N_k(x) ⊆ {1, …, n} množina indexů k nejbližších trénovacích příkladů, tj. množina, pro kterou

|N_k(x)| = k,
δ(x, x_i) ≤ δ(x, x_j) pro všechna i ∈ N_k(x) a j ∉ N_k(x)

(při shodných vzdálenostech se vybere podle pevně daného pravidla). Metoda k nejbližších sousedů (kNN) předpovídá

ŷ(x) = argmax_{c ∈ 𝒞} |{i ∈ N_k(x) : y_i = c}| (klasifikace), ŷ(x) = 1/k ∑_{i ∈ N_k(x)} y_i (regrese).

Model si tedy zapamatuje celá trénovací data a pro nový příklad předpoví nejčastější třídu (v regresi průměr hodnot) mezi jeho k nejbližšími sousedy.

Laicky řečeno

„Řekni mi, kdo jsou tví sousedé, a já ti řeknu, kdo jsi.“ Model se vůbec neučí — jen si data uloží. Veškerá práce přijde až při předpovědi, kdy se musí projít všichni známí klienti. Číslo k říká, kolika sousedů se ptáme: jeden soused je jako poslouchat jediného svědka, pětadvacet je jako hlasování.

d(x, x′) = √(x₁ − x′₁)² + (x₂ − x′₂)²

(x₁ − x′₁)²: rozdíl v příjmu; na druhou, aby nezáleželo, kdo vydělává víc, a aby velké rozdíly vážily víc než malé
(x₂ − x′₂)²: rozdíl ve věku. Oba čtverce se prostě sečtou — jednotky příznaků se tu míchají, a proto bude záležet na měřítku

Eukleidovská vzdálenost: Pythagorova věta v rovině příjem × věk. Odmocnina pořadí sousedů nemění, kNN ji proto v praxi vynechává.

ŷ(x) = 1, právě když 1/k ∑_{i ∈ N_k(x)} y_i > 1/2

N_k(x): množina k trénovacích klientů s nejmenší vzdáleností d od x — jediné místo, kde do předpovědi vstupuje vzdálenost
y_i: skutečný výsledek souseda (1 = splatil, 0 = nesplatil); sečtením dostaneme počet hlasů pro „splatí“
1/k: z počtu hlasů udělá podíl — odhad pravděpodobnosti splacení v okolí x
1/2: práh většiny; liché k zaručí, že nenastane remíza (při sudém k náš kód rozhodne nejbližší soused)

Hlasování je odhad Bayesova klasifikátoru: místo neznámé p(x) se použije podíl splácejících mezi sousedy.

Algoritmus — k nejbližších sousedů

def knn(trenink, x, k):
    vzdalenosti = [(d2(x, t.x), t.y) for t in trenink]   # d2 = čtverec vzdálenosti
    vzdalenosti.sort()                                    # od nejbližšího
    sousede = vzdalenosti[:k]
    hlasy = sum(y for _, y in sousede)                    # kolik sousedů splatilo
    if 2 * hlasy > k: return 1
    if 2 * hlasy < k: return 0
    return sousede[0][1]                                  # remíza: nejbližší soused

„Učení“ je jen uložení dat. Předpověď projde všech n trénovacích klientů: vzdálenosti stojí řádově n · d operací (d = počet příznaků) a seřazení nejvýš n log n — pro každý dotaz znovu; velké systémy proto používají přibližné vyhledávání (stromové indexy, hašování).

Rozhodovací oblasti kNN (příznaky standardizované)

S jedním sousedem má kNN na trénovacích datech přesnost 100 % (každý klient je sám sobě nejbližším sousedem) a na nových 88,2 % — ostrůvky kolem jednotlivých klientů jsou stejné přeučení jako u hlubokého stromu. Nejlepší je k = 25 s přesností 91,3 %, skoro na stropu 91,5 %, a hranice je hladká a šikmá. S k = 101, tedy polovinou všech dat, se model začne blížit „vždycky splatí“ a přesnost klesne na 87,2 %. Malé k má malé vychýlení a velký rozptyl, velké k naopak — stejně jako stupeň polynomu.

7. Na měřítku záleží

kNN měří vzdálenost a vzdálenost sčítá rozdíly ve všech příznacích. Co když bance příjem přijde v korunách, a ne v tisících?

Definice — standardizace příznaků

Nechť n ≥ 1, j ∈ {1, …, d} a x_1j, …, x_nj ∈ ℝ jsou hodnoty j-tého příznaku na trénovacích datech, ne všechny stejné. Označme

x̄_j = 1/n ∑_i=1ⁿ x_ij, s_j = √1/n ∑_i=1ⁿ (x_ij − x̄_j)² > 0

průměr a směrodatnou odchylku příznaku na trénovacích datech. Standardizace příznaku j je funkce ℝ → ℝ,

x ↦ z = x − x̄_j/s_j,

kterou se převedou trénovací i nové hodnoty příznaku (vždy s x̄_j, s_j z trénovacích dat). Standardizované trénovací hodnoty mají průměr 0 a rozptyl 1, takže všechny příznaky do vzdálenosti přispívají srovnatelně.

Laicky řečeno

S příjmem v korunách je soused, který vydělává o tisícovku víc, vzdálený 1 000 jednotek. Soused, který je o dvacet let starší, je vzdálený 20 jednotek — padesátkrát blíž. Věk tím pro kNN prakticky přestane existovat a klienti se porovnávají jen podle příjmu. Přesnost kNN s 15 sousedy spadne z 91,1 % (příjem v tisících) na 84,9 %. Po standardizaci je 91,3 %, ať byl příjem zadaný v čemkoli.

z = x − x̄/s

x − x̄: posun: průměrný klient dostane 0. Na posunu vzdálenosti nezávisí (odečte se u obou klientů), ale hodnoty jsou pak kolem nuly a čitelnější
s: směrodatná odchylka příznaku — vydělením se příznak měří „v typických rozdílech“ místo v korunách nebo letech. Tohle je ta část, na které kNN záleží: jednotky zmizí

Příklad — dva sousedé v korunách a po standardizaci

Klient má příjem 40 000 Kč a 30 let. Soused A vydělává o 1 000 Kč víc a je stejně starý, soused B má stejný příjem a je o 20 let starší. Na 200 trénovacích klientech je x̄ = 51,2 tisíce a s = 22,4 tisíce u příjmu, x̄ = 44,0 a s = 14,6 roku u věku.

v korunách: d(A) = √1000² + 0² = 1 000, d(B) = √0² + 20² = 20 → bližší je B, 50krát

standardizovaně: d(A) = √(1/22,4)² + 0² = 0,045, d(B) = √0² + (20/14,6)² = 1,37 → bližší je A, asi 31krát

Barvy odpovídají členům vzorce vzdálenosti: rozdíl v příjmu, rozdíl ve věku. Po standardizaci se rozdíl dělí směrodatnou odchylkou příznaku (průměr x̄ se u obou klientů odečte).

V korunách je „vzdálenost“ téměř jen rozdíl příjmu: dvacet let věku váží stejně jako dvacet korun. Po standardizaci je tisícovka příjmu malý rozdíl (0,045 směrodatné odchylky příjmu) a dvacet let velký (1,37 směrodatné odchylky věku) — což odpovídá selskému rozumu.

Stromu je měřítko jedno: otázka „příjem ≤ 39 500 Kč?“ rozdělí klienty stejně jako „příjem ≤ 39,5 tisíce?“. To je jedna z praktických výhod stromů — data se nemusí předzpracovávat.

Věta — strom nezávisí na rostoucím přeškálování příznaku

Nechť D je konečná množina trénovacích příkladů s příznaky v ℝ^d, j ∈ {1, …, d} a g : ℝ → ℝ je ostře rostoucí funkce, tj. a < b ⇒ g(a) < g(b) (např. g(x) = 1000x, ale na kladných číslech i log x). Nechť v každém příkladu nahradíme příznak x_j hodnotou g(x_j). Pak CART rozdělí trénovací data na tytéž skupiny a strom má tytéž listy se stejnými předpověďmi.

Důkaz: pro ostře rostoucí g platí a ≤ b ⇔ g(a) ≤ g(b), takže setřídění klientů podle x_j se nezmění. Každý práh mezi dvěma sousedními hodnotami rozdělí klienty na tytéž dvě skupiny jako odpovídající práh mezi jejich obrazy; skupiny mají tytéž podíly tříd, tedy tutéž Giniho nečistotu, a vybere se tatáž otázka. Indukcí přes uzly vyjde tentýž strom, jen s prahy převedenými přes g. ∎

(U lineárního g, jako je převod na koruny, se přenese i střed prahu a strom předpovídá stejně i pro nové klienty. U nelineárního g se střed přes g nepřenáší přesně, takže nový klient s hodnotou těsně u prahu může skončit na druhé straně; na trénovací data to vliv nemá.)

kNN naopak kromě měřítka trpí i prokletím dimenze: se stovkou příznaků jsou všichni sousedé skoro stejně daleko.

8. Strom, nebo sousedé?

	rozhodovací strom	k nejbližších sousedů
učení	rychlé (třídění podle příznaků)	žádné, jen uložení dat
předpověď	velmi rychlá (pár otázek)	pomalá (projít všechna data)
vysvětlení	čitelná pravidla	„podobní klienti dopadli takhle“
měřítko příznaků	nevadí	nutná standardizace
šikmé hranice	jen schody	hladké
hlavní parametr	hloubka (u nás nejlépe 3)	`k` (u nás nejlépe 25)
přesnost na našich datech	89,5 %	91,3 %

Samotný strom bývá nestabilní — malá změna dat změní první otázku a s ní celý strom — a jeho přesnost zaostává. Ve skutečných aplikacích se proto používají spíš celé lesy stromů, o kterých je další díl. kNN se zase vrátil v nové podobě: vyhledávání nejpodobnějších vektorů je jádrem doporučovacích systémů a toho, jak jazykové modely hledají v dokumentech.

9. Shrnutí

Rozhodovací strom klade otázky „příznak ≤ práh?“; první otázka našeho stromu byla „příjem ≤ 39,5 tisíce?“ a snížila Giniho nečistotu z 0,420 na 0,186.
Hluboký strom se přeučí: hloubka 3 dala 89,5 %, strom s 25 listy znal trénovací data nazpaměť a měl 86,5 %.
Strom kreslí jen svislé a vodorovné hranice, šikmou hranici skládá ze schodů.
kNN předpovídá podle nejbližších sousedů; s k = 1 se přeučí (88,2 %), s k = 25 dosáhl 91,3 % při stropu 91,5 %.
kNN závisí na měřítku: příjem v korunách srazil přesnost na 84,9 %, standardizace ji vrátila na 91,3 %.

Chcete si to osahat? Nechte AI agenta naučit rozhodovací strom na libovolné tabulce, kterou máte — výsledky sportovního týmu, údaje o počasí — a vypsat ho jako pravidla „když…, pak…“. Dávají smysl?

Máte na to jiný názor? Napište na support@coden-app.com.

Rozhodovací stromy a k nejbližších sousedů: modely bez vzorců

1. Úloha: kdo splatí půjčku

2. Rozhodovací strom

3. Jak strom roste: Giniho nečistota

4. Hloubka a přeučení

5. Strom vidí jen svisle a vodorovně

6. k nejbližších sousedů

7. Na měřítku záleží

8. Strom, nebo sousedé?

9. Shrnutí

Agent na vašem počítači, ovládaný z telefonu