Čo je k-najbližších susedov (kNN)?

Definícia

Algoritmus k-najbližších susedov (kNN) je metóda učenia s učiteľom, ktorá klasifikuje bod podľa väčšinovej triedy jeho k najbližších uložených bodov.

kNN nemá explicitný krok trénovania. Ukladá označené príklady a výpočet robí, až keď príde dopyt. Scikit-learn to nazýva učenie založené na inštanciách bez zovšeobecňovania.

Ako to funguje

1. Zvoľte k a mieru vzdialenosti. Najbežnejšou voľbou je euklidovská vzdialenosť.
2. Nájdite k uložených bodov, ktoré sú najbližšie k dopytovanému bodu.
3. Dopytovanému bodu priraďte triedu, ktorú má väčšina z týchto k bodov.

Štandardne má každý sused jeden hlas. Pri váženom kNN počítajú bližší susedia viac, napríklad s váhou 1/d, kde d je vzdialenosť k susedovi.

Voľba k

Najlepšia hodnota k závisí od dát. Väčšie k potláča šum, ale robí hranice tried menej zreteľnými. Krížová validácia nájde z dát dobrú hodnotu k. Pri dvoch triedach nepárne k zabráni rovnosti hlasov.

Obmedzenia

• Ak majú príznaky rôzne jednotky alebo mierky, normalizácia každého príznaku môže presnosť výrazne zlepšiť.
• Vyhľadávanie hrubou silou porovnáva dopyt s každým uloženým bodom. To sa stane nerealizovateľným, keď počet bodov rastie.
• Vyhľadávanie v stromoch, napríklad KD strom, je rýchle iba v nízkych dimenziách (pod asi 20). Vo vysokých dimenziách je euklidovská vzdialenosť tiež menej užitočná, pretože všetky vektory sú od dopytu takmer rovnako vzdialené.
• Knižnice ako Faiss prehľadávajú veľké množiny vektorov. Ponúkajú presné vyhľadávanie a komprimované indexy. Komprimované indexy dávajú menej presné vyhľadávanie.

História

Evelyn Fix a Joseph Hodges metódu prvýkrát rozvinuli v roku 1951 v správe pre USAF School of Aviation Medicine. Thomas Cover a Hart publikovali „Nearest neighbor pattern classification“ v roku 1967. Pri neobmedzenom množstve trénovacích dát nie je chybovosť pravidla 1-najbližšieho suseda horšia ako dvojnásobok Bayesovej chybovosti.