k‑nearest neighbors (k-NN)
k‑nearest neighbors, w skrócie k‑NN, to prosty, nienadzorowany i nadzorowany algorytm klasyfikacji oraz regresji, oparty na pomiarze odległości pomiędzy obserwacjami w przestrzeni cech. Działa na zasadzie porównywania nowej próbki z k najbliższymi próbkami ze zbioru treningowego i przydzielania jej klasy (lub wartości) na podstawie większości (klasyfikacja) albo średniej (regresja) wśród tych sąsiadów.
Historia
Pierwsze koncepcje metody najbliższych sąsiadów pojawiły się w latach 1960–1970 w pracach nad statystyką nieparametryczną. Rozwój komputerów umożliwił praktyczne zastosowanie algorytmu, a w latach 1990 stał się on standardem w dziedzinie uczenia maszynowego.
Zasada działania
- Określenie liczby sąsiadów k oraz miary odległości (np. odległość euklidesowa, Manhattan, Minkowskiego).
- Dla nowej próbki oblicz odległości do wszystkich próbek ze zbioru treningowego.
- Wybierz k próbek o najmniejszych odległościach – najbliższych sąsiadów.
- W zależności od zadania:
- Klasyfikacja: przypisz klasę najczęściej występującą wśród k sąsiadów (głosowanie większościowe).
- Regresja: przyjmij średnią wartość zmiennej zależnej wśród k sąsiadów.
Wybór parametru k
Liczba k ma kluczowy wpływ na zachowanie algorytmu. Małe k (np. 1) powoduje, że model jest bardzo wrażliwy na szumy w danych (przeuczenie), natomiast duże k prowadzi do wygładzania granic decyzyjnych, co może skutkować niedouczeniem. Optymalną wartość zazwyczaj wyznacza się metodami krzyżowej walidacji.
Miary odległości
W praktyce najczęściej stosuje się:
- Odległość euklidesową – odpowiednia przy cechach liczbowych o podobnej skali.
- Odległość Manhattan – lepsza przy cechach o różnej skali lub w przestrzeniach o wysokiej wymiarowości.
- Odległość Minkowskiego – uogólnienie obu poprzednich, z parametrem p.
- Odległość kosinusowa – używana przy wektorach o dużej liczbie wymiarów, np. w przetwarzaniu tekstu.
Zalety i wady
| Zalety | Wady |
|---|---|
| Brak konieczności tworzenia modelu trenowanego – metoda lazy learning. | Wysoka złożoność obliczeniowa przy dużych zbiorach danych (każde zapytanie wymaga przeglądu całego zbioru treningowego). |
| Łatwa interpretacja wyników. | Wrażliwość na nieistotne cechy – wymaga selekcji cech i normalizacji. |
| Dobre wyniki w problemach o niskiej wymiarowości i przy niewielkiej liczbie klas. | Mniej skuteczny w bardzo wysokiej wymiarowości (tzw. klątwa wymiarowości). |
Zastosowania
Algorytm k‑NN znajduje zastosowanie w wielu dziedzinach:
- Rozpoznawanie obrazów – np. klasyfikacja ręcznie pisanych cyfr (MNIST).
- Systemy rekomendacyjne – znajdowanie podobnych użytkowników lub produktów.
- Bioinformatyka – klasyfikacja sekwencji DNA lub białek.
- Diagnostyka medyczna – ocena podobieństwa do znanych przypadków chorobowych.
- Analiza sentymentu w przetwarzaniu języka naturalnego.
Implementacja
Podstawowa implementacja k‑NN wymaga jedynie przechowywania całego zbioru treningowego i funkcji obliczającej odległość. W praktyce używa się przyspieszaczy, takich jak:
- Drzewa KD – przyspieszają wyszukiwanie najbliższych sąsiadów w przestrzeni o niewielkiej liczbie wymiarów.
- Ball Tree – lepsze w przypadkach średniej i wysokiej wymiarowości.
- Approximate Nearest Neighbors (ANN) – przybliżone algorytmy, np. FLANN, które oferują kompromis między dokładnością a szybkością.
Przykład w języku Python
from sklearn.neighbors import KNeighborsClassifier
import numpy as np
# przykładowe dane treningowe
X_train = np.array([[1, 2], [2, 3], [3, 3], [6, 5], [7, 8]])
y_train = np.array([0, 0, 0, 1, 1])
# tworzymy klasyfikator k-NN z k=3
knn = KNeighborsClassifier(n_neighbors=3, metric='euclidean')
knn.fit(X_train, y_train)
# nowa próbka
X_new = np.array([[5, 5]])
prediction = knn.predict(X_new)
print('Przewidywana klasa:', prediction[0])
Literatura
- T. Cover i P. Hart, „A simple nearest neighbor algorithm”, IEEE Transactions on Information Theory, 1967.
- K. Müller, S. Ghahramani, „Learning with Kernels and Distance Metrics”, w: Advances in Neural Information Processing Systems, 2001.
- I. Goodfellow, Y. Bengio, A. Courville, Deep Learning, MIT Press, 2016 – rozdział poświęcony metodom nienadzorowanym, w tym k‑NN.
Powiązane pojęcia
Algorytm, Uczenie maszynowe, Klasyfikacja, Regresja, Selekcja cech, Krzyżowa walidacja, Przeuczenie, Niedouczenie, Klątwa wymiarowości.