K-Najbliższych Sąsiadów: Klasyczna Klasyfikacja przez Glosowanie

Cały algorytm można opisać jednym zdaniem

Aby klasyfikować nową punkt, znajdź k najbardziej podobnych do niego etykietowanych punktów treningowych i pozwól im głosować: klasy najpopularniejsza wśród tych k sąsiadów staje się prognozą. To cały algorytm - nie ma fazy uczenia w typowym sensie, nie ma do dopasowania wag, ani funkcji straconej do minimalizacji. K-Najbliższych Sąsiadów prosto przechowuje dane etykietowane i odwzorowuje każdą decyzję na czas zapytania, co jest powodem, dla którego nazywa się go uczeniem opóźnionym, w przeciwieństwie do uczenia gotowego, takiego jak regresja logistyczna lub sieć neuronowa, które wykonują swoją pracę od razu.

classify(query, k):
  distances = [ (dist(query, x_i), label_i) for each training point x_i ]
  neighbours = k points with smallest distance
  return the majority label among neighbours    // ties broken by smallest k or nearest

k=1 i szpiczakowa granica Voronoi

Dla k=1 każdy punkt zapytania po prostu dziedziczy etykietę jednego najbliższego przykładu treningowego, co oznacza, że granica decyzyjna jest dokładnie brzegiem diagramu Voronoi dla zestawu treningowego - obszarem wokół każdego punktu, gdzie on jest najbliżej. Ta granica krzywo kręci się wokół każdego z osobnych przykładów, w tym szumowych lub niewłaściwie etykietowanych, co daje bardzo niską bias na zestawie treningowym, ale wysoką wariancję: mała perturbacja danych może zmienić przewidywania całą okoliczność. Jest to typowe obraz nadadapowania widoczne jako szpiczakowa, spiczasta obszar zamiast abstrakcyjnej liczby.

Wybieranie k: wałek regulacji bias-variance

Podnoszenie wartości k powoduje średnianie głosów po większej liczbie sąsiadów, co ułatwia granicę decyzyjną i zmniejsza wariancję - ale zbyt duża wartość k może spowodować, że granica stanie się nieczytelna, kończo predictując tylko najpopularniejszą klase w całym obszarze, co jest maksymalnym biasem i minimalną użytecznością. W praktyce wartość k wybierana jest przy użyciu walidacji krzyżowej, często ograniczona do nieparzystych liczb w przypadku klasyfikacji dwuczynnikowej, aby uniknąć remisów, a powszechnym przesłaniem z reguły jest wybranie k bliskiego pierwiastkowi liczby przykładów treningowych.

Metryki odległości są tak ważne jak wartość k

"Najbliższy" zależy całkowicie od funkcji odległości. Odległość euklidesowa jest domyślna, ale cichym założeniem jest to, że każda cecha ma porównywalny skalę - cecha pomiaru w tysiącach dominuje nad tą pomiarowaną w jednokrotnych cyfrach, chyba że dane są znormalizowane. Odległość manhattanowska jest bardziej odporna na wyggony w poszczególnych osiach, a odległość Minkowskiego generalizuje oba te przypadki za pomocą parametru wykładnikowego. Normalizacja cech nie jest opcjonalna dla k-Najbliższych Sąsiadów w taki sam sposób, jak to może być dla niektórych innych algorytmów; popełnienie błędu w tej kwestii oznacza, że „ najbliżejsze” sąsiady to naprawdę punkty najbliższe wzdłuż takiej cechy, która przypadkiem ma największą skalę netto.

Zasada mroczna wymiarowości i przyspieszenie wyszukiwania

Pytanie brutalne sprawdza odległość do każdego zapisanego punktu, co daje O(n) na każdą prognozę - dobre dla małych zbiorów danych, ale bolesne w skali. Struktury indeksowe przestrzenne, takie jak drzewa kd i drzewa kulowe, zmniejszają to do około O(log n) w niskich wymiarach poprzez rekurencyjne podziałowanie przestrzeni, tak aby całe regiony mogły być odrzucone bez osobistego sprawdzenia każdego punktu zewnątrz nich. Ta przyspieszenie erodeje, gdy rosną wymiary cech, ze względu na zaszę mroczną wymiarowości: w wysokowymiarowych przestrzeniach objętość wzrasta tak ekspansywnie, że punkty danych stają się rzadko i prawie równo oddalone od siebie, co prowadzi do tego, że pojęcie „blisko” zaczyna się rozkładać, a indeksy przestrzenne stopniowo degenerują w performansy brutalnego wyszukiwania. Redukcja wymiarowości lub selekcja cech przed uruchomieniem k-Najbliższych Sąsiadów jest standardowym lekarstwem.

Często zadawane pytania