K-najbliżsi sąsiedzi

Algorytm k-najbliższych sąsiadów (KNN) to nieparametryczny, nadzorowany algorytm uczenia maszynowego wykorzystywany do zadań klasyfikacji i regresji. Opiera się na koncepcji bliskości, zakładając, że podobne punkty danych znajdują się blisko siebie. KNN jest algorytmem leniwym (lazy learning), co oznacza, że nie wymaga fazy uczenia – dokonuje predykcji, przechowując cały zbiór treningowy i wykorzystując go do określania klasy lub wartości nowych punktów. Algorytm przewiduje wynik dla punktu testowego, identyfikując ‘k’ punktów treningowych najbliższych temu punktowi i wnioskuje wynik na podstawie tych sąsiadów. Ta metoda jest bardzo intuicyjna i naśladuje ludzkie strategie percepcji polegające na porównywaniu nowych danych do znanych przykładów.

Jak działa KNN

KNN działa poprzez identyfikację ‘k’ najbliższych punktów danych względem punktu zapytania i wykorzystuje tych sąsiadów do dokonania predykcji.

• W zadaniach klasyfikacyjnych algorytm przypisuje punkt zapytania do klasy najczęściej występującej wśród jego ‘k’ najbliższych sąsiadów, co określa się mianem głosowania większościowego. Głosowanie większościowe w KNN można rozumieć jako “głosowanie pluralistyczne” w przypadku wielu klas – punkt zostaje przypisany do tej z największą liczbą głosów, nawet jeśli nie stanowi absolutnej większości.
• W zadaniach regresyjnych przewiduje wartość poprzez uśrednienie wartości ‘k’ najbliższych sąsiadów.

Zasady bliskości i podobieństwa, będące podstawą ludzkiej percepcji, są również kluczowe dla działania KNN – punkty bliskie sobie w przestrzeni cech są uznawane za bardziej podobne i prawdopodobnie mają podobne wyniki.

Metryki odległości

Do określania najbliższych sąsiadów KNN wykorzystuje różne metryki odległości, które są kluczowe dla jego skuteczności:

• Odległość euklidesowa: Prosta odległość między dwoma punktami w przestrzeni wielowymiarowej, powszechnie stosowana dla zmiennych ciągłych. Jest najczęściej używaną metryką w KNN i szczególnie przydatna, gdy dane są gęste i ciągłe.
• Odległość Manhattan: Nazywana także odległością taksówkową, oblicza dystans przez sumowanie bezwzględnych różnic współrzędnych dwóch punktów. Przydaje się w sytuacjach, gdzie ruch odbywa się po siatce ortogonalnej.
• Odległość Minkowskiego: Uogólnienie odległości euklidesowej i Manhattan, z parametrem ‘p’. Dla p=1 jest to Manhattan, dla p=2 – euklidesowa. Zapewnia elastyczność w zależności od wybranego ‘p’.
• Odległość Hamminga: Stosowana do danych kategorycznych, liczy liczbę różniących się bitów pomiędzy dwoma wektorami binarnymi. Szczególnie przydatna w zadaniach klasyfikacji binarnej.

Wybór odpowiedniej wartości ‘k’

Parametr ‘k’ w KNN oznacza liczbę sąsiadów branych pod uwagę. Wybór odpowiedniego ‘k’ jest kluczowy:

• Małe ‘k’ może prowadzić do przeuczenia, gdzie model jest zbyt wrażliwy na szum w danych treningowych, wychwytując przypadkowe wzorce, które nie uogólniają się na nowe dane.
• Duże ‘k’ może prowadzić do niedouczenia, gdy model zbytnio uogólnia i pomija istotne wzorce, co skutkuje słabą skutecznością predykcji.
• Zazwyczaj ‘k’ dobiera się za pomocą walidacji krzyżowej i warto, by była to liczba nieparzysta, by uniknąć remisów w klasyfikacji. Wybór ‘k’ istotnie wpływa na dokładność modelu i często jest ustalany empirycznie.

Zalety i wady

Zalety

• Prostota i intuicyjność: Łatwy do zrozumienia i zaimplementowania, co czyni go dobrym wyborem dla początkujących. Jego prostota polega na bezpośrednim porównywaniu nowych przypadków z zapisanymi przykładami.
• Brak fazy uczenia: KNN nie wymaga jawnej fazy trenowania, predykcje dokonuje na podstawie przechowywanego zbioru danych. Model można łatwo aktualizować, dodając nowe punkty do zbioru danych.
• Wszechstronność: Może być stosowany zarówno do klasyfikacji, jak i regresji, a jego zastosowanie jest szerokie w różnych dziedzinach. Sprawdza się także w problemach klasyfikacji wieloetykietowej.

Wady

• Obciążenie obliczeniowe: Wymaga przechowywania i porównywania każdego nowego punktu do całego zbioru danych, przez co może być wolny i zasobożerny przy dużych zbiorach. Złożoność czasowa KNN to O(n), gdzie n to liczba próbek treningowych.
• Wrażliwość na wartości odstające: Obecność wartości odstających może znacząco wpływać na przewidywania, ponieważ anomalie mogą zniekształcać wyniki, szczególnie przy małym ‘k’.
• Przekleństwo wymiarowości: W przestrzeniach o wysokiej liczbie wymiarów skuteczność algorytmu może spadać, ponieważ odległości między punktami tracą sens. Wraz ze wzrostem liczby wymiarów objętość przestrzeni rośnie, a dane stają się rzadkie, co utrudnia efektywne znajdowanie najbliższych sąsiadów.

Przykłady zastosowań

KNN znajduje zastosowanie w wielu dziedzinach ze względu na swoją prostotę i skuteczność:

• Systemy rekomendacyjne: Wykorzystywany do rekomendowania produktów lub treści użytkownikom na podstawie preferencji podobnych użytkowników. KNN pomaga identyfikować podobnych użytkowników lub przedmioty poprzez ocenę podobieństwa cech.
• Rozpoznawanie wzorców: Stosowany w rozpoznawaniu pisma odręcznego i innych zadaniach rozpoznawania wzorców, gdzie klasyfikuje obrazy na podstawie podobieństwa wartości pikseli.
• Uzupełnianie brakujących danych: Pomocny przy uzupełnianiu braków w danych, szacując je na podstawie podobnych punktów, co pozwala utrzymać spójność zbioru.
• Finanse i opieka zdrowotna: Stosowany w predykcji rynku akcji, ocenie ryzyka czy diagnozie medycznej poprzez analizę podobieństw w danych historycznych. W medycynie może przewidywać diagnozy pacjentów porównując objawy z już znanymi przypadkami.

Implementacja w Pythonie

KNN można zaimplementować przy użyciu bibliotek takich jak scikit-learn w Pythonie. Oto podstawowy przykład użycia KNN do klasyfikacji:

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ładuj zbiór danych
iris = load_iris()
X, y = iris.data, iris.target

# Podział danych na zbiory treningowy i testowy
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Inicjalizacja klasyfikatora KNN z k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Nauka modelu
knn.fit(X_train, y_train)

# Predykcje
y_pred = knn.predict(X_test)

# Ocena dokładności
accuracy = accuracy_score(y_test, y_pred)
print(f"Dokładność: {accuracy:.2f}")

K-najbliżsi sąsiedzi (KNN) w badaniach naukowych

K-najbliżsi sąsiedzi (KNN) to podstawowy algorytm wykorzystywany w różnych dziedzinach, takich jak wyszukiwanie informacji multimedialnych, eksploracja danych i uczenie maszynowe, zwłaszcza w kontekście dużych zbiorów danych.

Wartościowe publikacje naukowe:

• “Approximate k-NN Graph Construction: a Generic Online Approach” autorstwa Wan-Lei Zhao i in.:
  Prezentuje skuteczną metodę przybliżonego wyszukiwania k-najbliższych sąsiadów oraz budowy grafów. Artykuł pokazuje dynamiczne i elastyczne podejście do obsługi różnych rozmiarów i wymiarów danych, umożliwiające aktualizacje online, czego nie zapewnia wiele istniejących metod. Czytaj więcej .

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates” autorstwa Magdalen Dobson i Guy Blelloch:
  Przedstawia algorytmy równoległe łączące drzewo kd i porządkowanie Mortona w strukturę zd-tree, zoptymalizowaną dla danych o niskiej liczbie wymiarów. Autorzy pokazują, że ich podejście jest szybsze od istniejących algorytmów, osiągając znaczne przyspieszenia dzięki przetwarzaniu równoległemu. Zd-tree jako pierwszy wspiera równoległe, dynamiczne aktualizacje wsadowe w strukturach danych typu k-najbliższych sąsiadów. Czytaj więcej .

• “Twin Neural Network Improved k-Nearest Neighbor Regression” autorstwa Sebastiana J. Wetzela:
  Omawia nowatorskie podejście do regresji k-najbliższych sąsiadów z wykorzystaniem bliźniaczych sieci neuronowych. Metoda ta skupia się na przewidywaniu różnic wartości regresji, co prowadzi do lepszych wyników niż tradycyjne sieci neuronowe i klasyczna regresja k-najbliższych sąsiadów na małych i średnich zbiorach danych. Czytaj więcej .