Příroda | Algoritmus |
---|---|
Akronym | (v) k-NN |
V umělé inteligenci , konkrétně strojovém učení , je metoda k nejbližším sousedům metodou učení pod dohledem . Ve zkrácené formě k-NN nebo KNN, z angličtiny k-nejbližší sousedé .
V této souvislosti máme tréninkovou databázi složenou z N párů „vstup-výstup“. Chcete-li odhadnout výstup spojený s novým vstupem x , metoda k nejbližších sousedů spočívá v zohlednění (identicky) k tréninkových vzorků, jejichž vstup je nejblíže novému vstupu x , podle vzdálenosti, která má být definována. Protože tento algoritmus je založen na vzdálenosti, může normalizace zlepšit jeho přesnost.
Například v klasifikačním problému si ponecháme nejvíce zastoupenou třídu mezi k výstupy spojenými s k vstupy nejblíže novému vstupu x .
Při rozpoznávání vzorů je algoritmus k nejbližším sousedům ( k -NN ) neparametrická metoda používaná pro klasifikaci a regresi. V obou případech jde o zařazení záznamu do kategorie, do které patří k nejbližším sousedům, do prostoru charakteristik identifikovaných učením. Výsledek závisí na tom, zda se algoritmus používá pro účely klasifikace nebo regrese:
Metoda k -NN je založena na předchozím učení nebo slabém učení, kde je funkce hodnocena lokálně, konečný výpočet se provádí na konci klasifikace. Algoritmus k -NN patří mezi nejjednodušší z algoritmů strojového učení.
Ať už jde o klasifikaci nebo regresi, lze použít efektivní techniku k vážení přispívajícího vlivu sousedství, takže nejbližší sousedé přispívají více k průměru než vzdálenější sousedé. Například společné schéma vážení spočívá v tom, že každému sousedovi je dána váha 1 / d , kde d je vzdálenost prvku, který má být klasifikován nebo vážen, od tohoto souseda.
Sousedé jsou převzati ze sady objektů, pro které je známa třída (v klasifikaci k-NN) nebo hodnota (pro k -NN regrese ). Lze to považovat za tréninkovou sadu pro algoritmus, i když není výslovně vyžadováno výslovné školení.
Zvláštností algoritmů k -NN je být zvláště citlivý na místní strukturu dat.
Předpokládáme dvojice dat, které mají svoji hodnotu v množině , kde Y je třída značení X , například pro (a zákon rozdělení pravděpodobnosti ). Vzhledem k tomu, nespecifikované normu o a bod , který je , re-uspořádání dat odborného vzdělávání tak, že páry jsou nejbližšími sousedy, které patří do stejné třídy respektující metrické (třída populace navržení k prvku v okolí). Algoritmus vyžaduje znalost k , počet sousedů, které je třeba vzít v úvahu. Konvenční metodou pro tuto hodnotu je křížová validace ( křížová validace ).
Příklady školení jsou vektory ve vícerozměrném prostoru funkcí, každý se štítkem třídy členství. Fáze tréninku algoritmu spočívá pouze v ukládání charakteristických vektorů a štítků tříd cvičných vzorků.
V klasifikaci fázi, k je uživatelsky definované konstantní, a neznačený vektor (dotaz nebo testovací bod) je klasifikován přiřazením štítku, který je nejčastější mezi k cvičné vzorky. Nejblíže k bodu, se zařazují .
Společnou vzdáleností pro spojité proměnné je euklidovská vzdálenost . U diskrétních proměnných, například při klasifikaci textu, lze použít jinou vzdálenost, například vzdálenost překrytí (nebo Hammingovu vzdálenost ). V kontextu microarray genetických dat se například k -NN používá také s korelačními koeficienty Pearson a Spearman. Přesnost klasifikace k -NN lze často významně zlepšit, pokud se vzdálenost učí specializovanými algoritmy, jako je metoda nejbližšího souseda s vysokou tolerancí nebo analýza sousedních komponent .
Slabina klasifikace v základní verzi většinovým hlasováním se objeví, když je rozdělení tříd asymetrické. To znamená, že příklady častější třídy mají tendenci dominovat klasifikační predikci nového účastníka, protože by byla statisticky častější u k nejbližších sousedů podle definice. Jeden způsob, jak překonat tento problém je k hmotnosti klasifikaci s přihlédnutím vzdálenost nového účastníka ke každému z jeho k nejbližších sousedů. Třída (nebo hodnota v případě regrese) každého z těchto k nejbližších sousedů se vynásobí vážením úměrným inverzní hodnotě vzdálenosti od tohoto souseda k bodu, který má být klasifikován. Dalším způsobem, jak překonat tuto asymetrii, je abstrakce v reprezentaci dat. Například na samodaptivní mapě (SOM) je každý uzel reprezentativní pro těžiště (barycentrum) shluku podobných bodů, bez ohledu na jejich hustotu v původních tréninkových datech. K -NN metoda může být použita pro soms.