K najbliższych sąsiadów

Z Wikipedii, wolnej encyklopedii
(Przekierowano z K-najbliższych sąsiadów)
Skocz do: nawigacja, szukaj

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 oraz wartość zmiennej objaśnianej .
  • Dana jest obserwacja z przypisanym wektorem zmiennych objaśniających dla której chcemy prognozować wartość zmiennej objaśnianej .

Algorytm polega na:

  1. porównaniu wartości zmiennych objaśniających dla obserwacji z wartościami tych zmiennych dla każdej obserwacji w zbiorze uczącym.
  2. wyborze (ustalona z góry liczba) najbliższych do 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]