K-najbliższych sąsiadów

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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:

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.

Zobacz też[edytuj | edytuj kod]