Tekst źródłowy strony K najbliższych sąsiadów

'''Algorytm ''k'' najbliższych sąsiadów''' (lub '''algorytm k-nn''' z [[język angielski|ang.]] ''k nearest neighbours'') – jeden z algorytmów [[regresja nieparametryczna|regresji nieparametrycznej]] używanych w [[statystyka|statystyce]] do [[prognozowanie|prognozowania]] wartości pewnej [[zmienna losowa|zmiennej losowej]]. Może również być używany do [[klasyfikacja statystyczna|klasyfikacji]].

Założenia:
* Dany jest [[Sprawdzian krzyżowy|zbiór uczący]] zawierający [[obserwacja statystyczna|obserwacje]], z których każda ma przypisany wektor [[zmienna objaśniająca|zmiennych objaśniających]] <math>X_1\dots X_n</math> oraz wartość [[zmienna objaśniana|zmiennej objaśnianej]] <math>Y.</math>
* Dana jest obserwacja <math>C</math> z przypisanym wektorem zmiennych objaśniających <math>X_1\dots X_n</math> dla której chcemy prognozować wartość zmiennej objaśnianej <math>Y.</math>

Algorytm polega na:
# porównaniu wartości zmiennych objaśniających dla obserwacji <math>C</math> z wartościami tych zmiennych dla każdej obserwacji w zbiorze uczącym.
# wyborze <math>k</math> (ustalona z góry liczba) najbliższych do <math>C</math> obserwacji ze zbioru uczącego.
# 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 [[przestrzeń metryczna|metryki]], mierzącej odległość pomiędzy wektorami zmiennych objaśniających dwóch obserwacji. Zwykle stosowana jest tu [[Przestrzeń euklidesowa|metryka euklidesowa]] lub [[odległość Mahalanobisa|metryka Mahalanobisa]]. Można również zamiast [[średnia arytmetyczna|średniej arytmetycznej]] stosować np. [[mediana|medianę]].

Algorytm ''k'' najbliższych sąsiadów jest użyteczny szczególnie wtedy, gdy [[zależność między zmiennymi losowymi|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 [[obserwacja odstająca|obserwacji odstających]], metody klasyczne (np. [[regresja liniowa]]) dadzą zwykle dokładniejsze wyniki.

== Przykład klasyfikacji ==
[[Plik:KnnClassification.svg|mały|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 <math>n</math> cechujących ją wartości, a następnie umieścić ją w <math>n</math>-wymiarowej przestrzeni. Chcąc przyporządkować daną do już istniejącej grupy, należy znaleźć <math>k</math> najbliższych obiektów w przestrzeni <math>n</math>-wymiarowej, a następnie wybrać grupę najbardziej liczną.

== Zobacz też ==
* [[regresja (statystyka)|regresja]]

[[Kategoria:Analiza regresji]]
[[Kategoria:Klasyfikacja statystyczna]]
[[Kategoria:Algorytmy]]