K-najbliższych sąsiadów (K-NN)

Czym jest algorytm K-NN?

K-najbliższych sąsiadów (ang. K-Nearest Neighbors, K-NN) to prosty, ale skuteczny algorytm uczenia maszynowego wykorzystywany do klasyfikacji i regresji. Działa na zasadzie „głosowania” lub średniej wartości cech jego \(k\)-najbliższych sąsiadów w przestrzeni cech, na podstawie zdefiniowanej metryki odległości.

Algorytm K-NN jest przykładem uczenia leniwego (ang. lazy learning), ponieważ nie buduje explicite modelu podczas treningu. Obliczenia są przeprowadzane dopiero podczas predykcji.

Kluczowe kroki algorytmu K-NN

Definicja wartości \(k\):
- Określenie liczby najbliższych sąsiadów, którzy będą brani pod uwagę przy klasyfikacji lub regresji.
Obliczenie odległości:
- Miara odległości między punktami w przestrzeni cech, np.:
  - Odległość euklidesowa: \[ d(x, y) = \sqrt{\sum_{i=1}^n (x_i - y_i)^2} \]
  - Odległość Manhattan: \[ d(x, y) = \sum_{i=1}^n |x_i - y_i| \]
  - Odległość Minkowskiego: \[ d(x, y) = \left( \sum_{i=1}^n |x_i - y_i|^p \right)^{1/p} \]
Wybór najbliższych sąsiadów:
- Znalezienie \(k\)-najbliższych punktów w zbiorze treningowym w stosunku do punktu, który chcemy sklasyfikować lub przewidzieć.
Głosowanie lub predykcja:
- Klasyfikacja: Punkt zostaje przypisany do klasy najczęściej występującej wśród sąsiadów.
- Regresja: Punkt otrzymuje wartość będącą średnią wartości cech sąsiadów: \[ \hat{y} = \frac{1}{k} \sum_{i=1}^k y_i \]

Przykład działania K-NN (klasyfikacja)

Rozważmy zbiór danych z dwiema klasami: A i B. Dla nowego punktu obliczamy odległości do wszystkich punktów treningowych, wybieramy \(k = 3\) najbliższych sąsiadów i określamy klasę większościową.

Dane:

Punkt treningowy	Klasa	Współrzędne (x, y)
P1	A	(1, 1)
P2	B	(2, 2)
P3	A	(3, 1)
P4	B	(5, 5)

Nowy punkt:

\(P_\text{new} = (3, 3)\)

Kroki:

Oblicz odległości:
- \(d(P_\text{new}, P1) = \sqrt{(3-1)^2 + (3-1)^2} = 2.83\)
- \(d(P_\text{new}, P2) = \sqrt{(3-2)^2 + (3-2)^2} = 1.41\)
- \(d(P_\text{new}, P3) = \sqrt{(3-3)^2 + (3-1)^2} = 2.00\)
- \(d(P_\text{new}, P4) = \sqrt{(3-5)^2 + (3-5)^2} = 2.83\)
Wybierz \(k = 3\) najbliższych sąsiadów:
- \(P2, P3, P1\) (klasy: B, A, A).
Głosowanie:
- Klasa większościowa: A.

Wynik: Nowy punkt zostaje sklasyfikowany jako klasa A.

Zalety K-NN

Prostota:
- Łatwy do zrozumienia i zaimplementowania.
Brak potrzeby trenowania modelu:
- Nie wymaga budowy modelu, wszystkie obliczenia są przeprowadzane podczas predykcji.
Wszechstronność:
- Może być stosowany do problemów klasyfikacji i regresji.

Wady K-NN

Koszt obliczeniowy:
- Duże zbiory treningowe mogą znacząco spowolnić działanie algorytmu, ponieważ obliczenia są wykonywane dla każdego punktu.
Wrażliwość na wybór \(k\):
- Zbyt małe \(k\) może prowadzić do nadmiernego dopasowania (overfitting), a zbyt duże \(k\) do niedopasowania (underfitting).
Wrażliwość na skalę cech:
- Cecha o dużych wartościach może zdominować miarę odległości, dlatego konieczne jest skalowanie danych (np. normalizacja, standaryzacja).
Wrażliwość na szum:
- Punkty odstające mogą znacząco wpłynąć na wynik.

Zastosowania K-NN

Klasyfikacja obrazów:
- Rozpoznawanie obiektów, takich jak cyfry czy twarze, na podstawie podobieństwa do obrazów treningowych.
Rekomendacje produktów:
- Sugerowanie produktów na podstawie zachowań użytkowników podobnych do użytkownika docelowego.
Analiza zdrowotna:
- Przewidywanie ryzyka chorób na podstawie danych pacjentów.
Finanse:
- Klasyfikacja klientów na podstawie ich historii kredytowej.

Wybór optymalnej wartości \(k\)

Próba i błąd (grid search):
- Testowanie różnych wartości \(k\) na zbiorze walidacyjnym.
Walidacja krzyżowa:
- Sprawdzanie wydajności modelu dla różnych wartości \(k\) na różnych podzbiorach danych.
Ogólna zasada:
- Zbyt małe \(k\) mogą być podatne na szum, a zbyt duże mogą zignorować lokalne struktury w danych.

K-najbliższych sąsiadów to intuicyjny i skuteczny algorytm, szczególnie w problemach z dobrze zdefiniowaną metryką odległości. Jego prostota sprawia, że jest często wykorzystywany jako punkt wyjścia w analizie danych i budowie modeli uczenia maszynowego.