k-dimensionální strom (kd-tree)
(doplněk k IBL algoritmům)
Prohledávání prostoru mívá obecně vysokou výpočetní složitost (neli-
neárně narůstají požadavky na čas a paměť v závislosti na počtu zkou-
maných bodů prostoru, n). Efektivnější hledání lze dosáhnout vymeze-
ním podprostoru. Jednou z možností je pomocí nadrovin (rovnoběžných
s příslušnými osami) vymezit část k-rozměrného prostoru, která buď pří-
mo obsahuje hledané řešení, nebo umožňuje již přijatelné libovolné
dohledání (např. sekvenčně, pokud již prostor není rozdělen na jedno-
prvkové podprostory).
kd-strom je jedna z možností, kdy je prostor rozdělován postupným
zpracováním jednotlivých os x1, x2, ..., xk, ..., x1, x2, ..., xk tak, že se za
bod dělení (jímž prochází příslušná nadrovina, kolmá k dané ose) volí
medián souřadnic bodů v příslušném podintervalu vzniklém rozdělením
předchozího intervalu. Zmíněný postup vede k vyváženému stromu, roz-
dělujícímu prostor až na podprostory obsahující 1 bod. U metody nej-
bližšího souseda l-NN pak stačí zjistit, ve kterém vzniklém podprostoru
je zároveň l instancí známých (trénovacích) a ta neznámá (klasifikova-
ná). Navíc lze postupně dělit při klasifikaci jen ty podprostory, v nichž je
klasifikovaná instance, jejíž souřadnice x jsou známy, ale není známo je-
jí hledané označení (které se zjistí až po nalezení požadovaného počtu
l známých nejbližších "sousedů" ve výsledném podprostoru--zde je oz-
načován počet sousedů pomocí l, aby nedošlo k záměně s k, jež v tomto
případě znamená počet dimenzí prohledávaného prostoru).
Horní výpočetní složitost vytvoření kd-stromu je O(n log2 n) pro n zada-
ných bodů (prostor a vznikající podprostory jsou "půleny" mediánem,
proto log2).
Existuje řada modifikací generování kd-stromu, kdy lze volit i jiný bod
dělení než medián, přičemž pak nemusí být zaručena vyváženost stromu.