K najbliższych sąsiadów

Algorytm k najbliższych sąsiadów (lub algorytm k-nn z ang. k nearest neighbours) – jeden z algorytmów regresji nieparametrycznej używanych w statystyce do prognozowania wartości pewnej zmiennej losowej. Może również być używany do klasyfikacji.

Założenia:

• Dany jest zbiór uczący zawierający obserwacje, z których każda ma przypisany wektor zmiennych objaśniających $X_{1}\dots X_{n}$ oraz wartość zmiennej objaśnianej $Y.$
• Dana jest obserwacja $C$ z przypisanym wektorem zmiennych objaśniających $X_{1}\dots X_{n}$ dla której chcemy prognozować wartość zmiennej objaśnianej $Y.$

Algorytm polega na:

1. porównaniu wartości zmiennych objaśniających dla obserwacji $C$ z wartościami tych zmiennych dla każdej obserwacji w zbiorze uczącym.
2. wyborze $k$ (ustalona z góry liczba) najbliższych do $C$ obserwacji ze zbioru uczącego.
3. uśrednieniu wartości zmiennej objaśnianej dla wybranych obserwacji, w wyniku czego uzyskujemy prognozę.

Definicja „najbliższych obserwacji” w punkcie 2 sprowadza się do minimalizacji pewnej metryki, mierzącej odległość pomiędzy wektorami zmiennych objaśniających dwóch obserwacji. Zwykle stosowana jest tu metryka euklidesowa lub metryka Mahalanobisa. Można również zamiast średniej arytmetycznej stosować np. medianę.

Algorytm k najbliższych sąsiadów jest użyteczny szczególnie wtedy, gdy zależność między zmiennymi objaśniającymi a objaśnianymi jest złożona lub nietypowa (np. niemonotoniczna), czyli trudna do modelowania w klasyczny sposób. W przypadku, gdy zależność ta jest łatwa do interpretacji (np. liniowa), a zbiór nie zawiera obserwacji odstających, metody klasyczne (np. regresja liniowa) dadzą zwykle dokładniejsze wyniki.

Przykład klasyfikacji

W przypadku k=3 (mniejszy okrąg), zielona kropka zostanie zakwalifikowana do czerwonych trójkątów. W przypadku k=5 (większy okrąg) – do niebieskich kwadratów

Każdej danej należy przypisać pewien zestaw $n$ cechujących ją wartości, a następnie umieścić ją w $n$-wymiarowej przestrzeni. Chcąc przyporządkować daną do już istniejącej grupy, należy znaleźć $k$ najbliższych obiektów w przestrzeni $n$-wymiarowej, a następnie wybrać grupę najbardziej liczną.

Zobacz też

• regresja