Co je k nejbližších sousedů (kNN)?

Definice

Algoritmus k nejbližších sousedů (kNN) je metoda učení s učitelem, která zařadí bod podle nejčastější třídy mezi jeho k nejbližšími uloženými body.

kNN nemá explicitní krok trénování. Ukládá označené příklady a výpočet provádí až při příchodu dotazu. Scikit-learn to nazývá učení založené na instancích bez zobecňování.

Jak funguje

1. Zvolte k a míru vzdálenosti. Nejčastější volbou je euklidovská vzdálenost.
2. Najděte k uložených bodů nejblíže dotazovanému bodu.
3. Dotazovanému bodu přiřaďte třídu, kterou má většina z těchto k bodů.

Ve výchozím nastavení má každý soused jeden hlas. Ve váženém kNN se bližší sousedé počítají více, například s váhou 1/d, kde d je vzdálenost k sousedovi.

Volba k

Nejlepší hodnota k závisí na datech. Větší k potlačí šum, ale hranice tříd jsou méně výrazné. Křížová validace najde z dat dobrou hodnotu k. U dvou tříd se lichým k vyhnete shodným hlasům.

Omezení

• Mají-li příznaky různé jednotky nebo měřítka, může normalizace každého příznaku výrazně zlepšit přesnost.
• Vyhledávání hrubou silou porovnává dotaz s každým uloženým bodem. S rostoucím počtem bodů se to stane neproveditelným.
• Vyhledávání se stromovou strukturou, například KD stromem, je rychlé jen v nízkých dimenzích (pod zhruba 20). Ve vysokých dimenzích je euklidovská vzdálenost také méně užitečná, protože všechny vektory jsou od dotazu téměř stejně daleko.
• Knihovny jako Faiss prohledávají velké množiny vektorů. Nabízejí přesné vyhledávání a komprimované indexy. Komprimované indexy dávají méně přesné vyhledávání.

Historie

Evelyn Fix a Joseph Hodges metodu poprvé vyvinuli v roce 1951 v zprávě pro USAF School of Aviation Medicine. Thomas Cover a Hart publikovali „Nearest neighbor pattern classification“ v roce 1967. Při neomezeném množství trénovacích dat není chybovost pravidla nejbližšího souseda (1-NN) horší než dvojnásobek Bayesovy chyby.