K-Najbliższych Sąsiadów
- Autor metody
- Cover, T.M. & Hart, P.E.
- Rok
- 1967
- Typ
- Instance-based (non-parametric) learning
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
K-Najbliższych Sąsiadów (KNN), sformalizowana przez Covera i Harta w 1967 roku, jest nieparametryczną metodą opartą na instancjach, która klasyfikuje lub przewiduje nową obserwację, analizując k najbliższych przykładów w danych treningowych.
W przypadku klasyfikacji stosuje głosowanie większościowe wśród tych sąsiadów; w przypadku regresji uśrednia ich wartości.
Intuicja stojąca za metodą
Idea jest prosta: podobne dane wejściowe mają tendencję do podobnych danych wyjściowych. Aby przypisać etykietę nowemu punktowi, KNN znajduje garść przykładów treningowych, które znajdują się najbliżej niego w przestrzeni cech i pozwala im podjąć decyzję. Nie ma z góry dopasowanego równania — same dane treningowe stanowią model, a predykcja jest dokonywana dopiero po nadejściu nowego punktu.
Historia
Klasyfikacja wzorców najbliższych sąsiadów została formalnie ugruntowana statystycznie przez Thomasa Covera i Petera Harta w ich artykule z 1967 roku w IEEE Transactions on Information Theory, który analizował wskaźnik błędów reguły najbliższego sąsiada. KNN stała się jedną z najwcześniejszych i najtrwalszych metod uczenia się opartych na instancjach i pozostaje standardowym klasyfikatorem bazowym.
Kiedy stosować
Używaj KNN do klasyfikacji lub predykcji na danych tabelarycznych z cechami ciągłymi, binarnymi lub porządkowymi i co najmniej około 30 obserwacjami. Nie zakłada żadnego konkretnego rozkładu, ale wymaga normalizacji cech i aby liczba cech pozostała mała w stosunku do wielkości próby (preferowane jest p znacznie mniejsze niż n). W małych lub wielowymiarowych próbach dominuje klątwa wymiarowości — odległości między sąsiadami stają się nieinformatywne — a model parametryczny, taki jak regresja logistyczna lub Naiwny Bayes, jest lepszym wyborem.
Ograniczenia i uwagi
- Wrażliwa na skalowanie cech; bez standaryzacji, cechy o dużej skali dominują odległość i zniekształcają ją.
- Szybko degraduje w wysokich wymiarach (klątwa wymiarowości), gdzie odległości między sąsiadami tracą znaczenie.
- Każda predykcja wymaga przeszukania całego zbioru treningowego, co jest powolne w czasie predykcji na dużych danych.
- Wymaga co najmniej umiarkowanej wielkości próby; w małych próbach odległości do najbliższych sąsiadów nie mają znaczenia.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Koncepcyjnie prosta i łatwa do wyjaśnienia: brak równania treningowego, dane to model.
- Nieparametryczna — nie zakłada niczego o podstawowym rozkładzie.
- Naturalnie obsługuje problemy wieloklasowe i złożone, nieliniowe granice decyzyjne.
- Działa zarówno dla klasyfikacji, jak i regresji z tą samą podstawową ideą.
Zastosowania
- Klasyfikacja danych tabelarycznych na dwie lub więcej kategorii.
- Predykcja numeryczna (regresja) przez uśrednianie najbliższych przykładów.
- Prosty, interpretowalny punkt odniesienia przed próbą zastosowania bardziej złożonych modeli.
- Rozpoznawanie wzorców, gdzie podobieństwo do znanych przykładów napędza decyzję.
Jak to działa
Jak to działa
Dla nowej obserwacji, KNN mierzy, jak daleko jest ona od każdego przykładu treningowego, zazwyczaj używając odległości euklidesowej w przestrzeni cech. Ponieważ odległość jest wrażliwa na skalę, cechy muszą być najpierw standaryzowane — w przeciwnym razie zmienna mierzona na dużej skali liczbowej zdominowałaby obliczenia i zniekształciła, którzy sąsiedzi są uważani za najbliższych.
Wzór
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}Wybieranych jest k punktów treningowych o najmniejszych odległościach do nowej obserwacji jako jej sąsiadów. Wartość k kontroluje, jak lokalna jest decyzja: małe k ściśle podąża za danymi, ale jest wrażliwe na szum, podczas gdy większe k wygładza granicę. k powinno być wybierane za pomocą walidacji krzyżowej (na przykład metodą łokcia), a nie zgadywane.
Sąsiedzi decydują o predykcji: w przypadku klasyfikacji nowy punkt przyjmuje najczęstszą klasę wśród swoich k sąsiadów (głosowanie większościowe), a w przypadku regresji przyjmuje średnią ich wartości. To sprawia, że metoda jest łatwa do zrozumienia, ale każda predykcja wymaga przeszukania zbioru treningowego.
Wzór
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}Częste pułapki
- Pomijanie standaryzacji cech, przez co jedna zmienna o dużej skali cicho kontroluje odległość.
- Wybieranie k ręcznie zamiast wybierania go za pomocą walidacji krzyżowej.
- Stosowanie KNN z wieloma cechami i niewielką liczbą obserwacji, gdzie stosunek wymiaru do próby ją łamie.
- Raportowanie tylko dokładności zamiast precyzji, czułości, F1 i macierzy pomyłek.
Najczęściej zadawane pytania
Jak wybrać wartość k?
k powinno być wybierane za pomocą walidacji krzyżowej, a nie zgadywane — na przykład poprzez wypróbowanie zakresu wartości i użycie metody łokcia do znalezienia, gdzie błąd przestaje się poprawiać. Małe k ściśle podąża za danymi, ale jest wrażliwe na szum, podczas gdy większe k wygładza granicę decyzyjną.
Dlaczego muszę standaryzować cechy?
KNN decyduje, kto jest „najbliższy”, używając odległości, która jest wrażliwa na skalę. Jeśli jedna cecha ma znacznie większą skalę liczbową niż inne, dominuje ona odległość i zniekształca zbiór sąsiadów. Standaryzacja cech (na przykład za pomocą StandardScaler) jest wymagana, aby każda cecha wnosiła sprawiedliwy wkład.
Dlaczego KNN ma problemy z wieloma cechami?
W przestrzeniach wielowymiarowych wszystkie punkty stają się w przybliżeniu równoodległe — klątwa wymiarowości — więc „najbliżsi” sąsiedzi nie są już znacząco blisko. Wydajność KNN szybko spada, a model parametryczny, taki jak Naiwny Bayes lub regresja logistyczna, jest zazwyczaj preferowany. Utrzymanie p znacznie mniejszego niż n pomaga.
Czy jest jakiś etap treningu?
Nie w zwykłym sensie. KNN jest oparty na instancjach (leniwy): po prostu przechowuje dane treningowe i wykonuje całą pracę w czasie predykcji, kiedy oblicza odległości, aby znaleźć najbliższych sąsiadów nowego punktu.
Pokrewne metody
Źródła
Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
Otwórz odnośnik DOISkopiowano.