k‑Nearest Neighbors (k‑NN)

k‑Nearest Neighbors (w skrócie k‑NN) to prosty, ale bardzo efektywny algorytm klasyfikacji i regresji w dziedzinie uczenia maszynowego. Działa on na zasadzie porównywania nowego obiektu z k najbliższymi obserwacjami w zbiorze treningowym przy użyciu wybranej metryki odległości.

Historia

Pierwszy opis metody najbliższych sąsiadów pojawił się w pracach Thomas Cover i Peter Hart w 1967 roku. Od tego czasu k‑NN stał się jednym z fundamentów statystyki i sztucznej inteligencji, a jego popularność rosła wraz z rozwojem mocy obliczeniowej i dostępnością dużych zbiorów danych.

Zasada działania

Wybór liczby sąsiadów k – typowo nieparzysta liczba, aby uniknąć remisu w klasyfikacji.
Określenie metryki odległości (np. odległość euklidesowa, Manhattan, Minkowskiego).
Dla nowego przykładu obliczana jest odległość do wszystkich punktów w zbiorze treningowym.
Wybierane są k najbliższe obserwacje.
W zależności od zadania:
- W klasyfikacji – nowy obiekt otrzymuje etykietę najczęściej występującą wśród k sąsiadów (głosowanie większościowe).
- W regresji – przewidywana wartość jest średnią (lub ważoną średnią) wartości k najbliższych punktów.

Wybór liczby k

Wartość k ma istotny wpływ na model:

Małe k (np. 1–3) – model jest bardzo elastyczny, łatwo dopasowuje się do szumów (przejawia się wysokie przejawy).
Duże k – zwiększa stabilność, ale może prowadzić do przeszacowania (underfitting).

Optymalną wartość zazwyczaj wyznacza się metodą cross‑validation lub testując kilka kandydatów i oceniając je miarą dokładności.

Metryki odległości

Wybór metryki zależy od charakteru danych:

Odległość euklidesowa – najczęściej stosowana w danych ciągłych.
Manhattan (odległość taksówkowa) – lepsza przy danych o wymiarach o różnej skali.
Minkowskiego – uogólnienie, parametr p określa typ metryki.
Odległość cosinusowa – przydatna przy analizie tekstu i wektorów o wysokiej wymiarowości.

Warianty i usprawnienia

Weighted k‑NN – sąsiedzi są ważeni w zależności od odległości (np. odwrotność odległości).
k‑d tree i Ball tree – struktury danych przyspieszające wyszukiwanie najbliższych sąsiadów.
Approximate Nearest Neighbors – algorytmy przybliżające, wykorzystywane przy wielkiej liczbie wymiarów.
Edited k‑NN – technika czyszczenia zbioru treningowego w celu redukcji szumów.

Zastosowania

Algorytm k‑NN znajduje zastosowanie w wielu dziedzinach, między innymi:

Rozpoznawanie wzorców – rozpoznawanie obrazów, rozpoznawanie mowy, rozpoznawanie tekstu.
Systemy rekomendacyjne – filtracja collaborative filtering.
Diagnostyka medyczna – klasyfikacja wyników badań.
Systemy wykrywania anomalii – np. w sieciach komputerowych.
Geolokalizacja – przybliżanie położenia na podstawie danych z GPS.

Zalety i wady

Zalety	Wady
Prostota implementacji i zrozumienia. Brak procesu uczenia – model jest „instancyjny”. Dobre wyniki przy odpowiednio dobranym k i metryce. Łatwość adaptacji do nowych danych (dodanie przykładu to jedynie aktualizacja zbioru).	Wysoki koszt obliczeniowy przy dużych zbiorach (czas predykcji). Wrażliwość na skalowanie cech – wymaga normalizacji. Utrata interpretowalności przy wysokiej wymiarowości. Może być podatny na „klątwę wymiarowości”.

Implementacje i biblioteki

W językach programowania dostępne są gotowe implementacje k‑NN, m.in.:

scikit‑learn (Python) – klasy KNeighborsClassifier i KNeighborsRegressor.
mlpack (C++).
Weka (Java) – klasyfikator IBk.
Biblioteka R – funkcja knn() w pakiecie class.

Przykładowy kod (Python, scikit‑learn)

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score

# Załadowanie danych
X, y = load_iris(return_X_y=True)

# Podział na zbiór treningowy i testowy
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42)

# Inicjalizacja klasyfikatora k‑NN z k=5 i metryką euklidesową
knn = KNeighborsClassifier(n_neighbors=5, metric='euclidean')

# Trening (w rzeczywistości jedynie zapamiętanie danych)
knn.fit(X_train, y_train)

# Predykcja
y_pred = knn.predict(X_test)

# Ocena
print('Dokładność:', accuracy_score(y_test, y_pred))

Literatura

Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory.
Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning. Springer.
James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An Introduction to Statistical Learning. Springer.
Pedregosa, F. et al. (2011). Scikit-learn: Machine Learning in Python. JMLR.

Algorytm k‑Nearest Neighbors pozostaje jednym z najważniejszych narzędzi w arsenale metod uczenia maszynowego, zwłaszcza w sytuacjach, gdy interpretowalność i szybka adaptacja do nowych danych mają kluczowe znaczenie.