Algorytm K najbliższych sąsiadów to bardzo prosty algorytm, który całkiem sensownie ogarnia ideę „nie wiemy, co wydarzy się w tym przypadku, ale jak znajdziemy podobne, to pewnie będzie tak samo”. Proste nie? A okazuje się, że również sensowne. Przyjrzyjmy się więc bliżej.
Idea – jeden wymiar
Zastanówmy się, jak to jest z punktami w jednym wymiarze. Skoro mamy jeden wymiar, to oznacza, że każdy punkt możemy zmierzyć na jeden sposób. W praktyce jest to po prostu odległość od jakiegoś miejsca, które uznajemy za początek. Sprawa prosta. Możemy sobie taki pomiar „odległości” wyobrazić na przykład jako wiek. Każda osoba ma przyporządkowaną liczbę pełnych lat z zakresu 0 do 122. Możemy więc ich sobie ułożyć na linii. Jeśli zaczniemy od lewej strony wartością 0 to maksymalnie daleko po prawej stronie, będziemy mieć 122. Wyobraźmy sobie, że mamy kilka osób w naszym zbiorze i że wiemy, które z nich zachorowały na jakąś chorobę. Pomińmy detale. Sytuacja wygląda mniej więcej tak:
Czerwona kropka oznacza stwierdzenie choroby, zielona stwierdzenie braku choroby. Pojawił nam się nowy „pacjent”. Możemy łatwo dokonać pomiaru jego „położenia na linii” (spoglądamy na datę urodzenia w dowodzie osobistym). Po jego umieszczeniu na linii możemy od razu spróbować przewidzieć diagnozę:
W zależności od tego, jaką liczbę sąsiadów sobie wybraliśmy, możemy ocenić naszego pacjenta:
- jeżeli zdecydowaliśmy się na jednego sąsiada, to sytuacja jest prosta: 1 x chory -> chory
- jeśli wybraliśmy dwóch sąsiadów, wciąż jest prosto: 2 x chory -> chory
- przy trzech sytuacja zaczyna się komplikować, ale nie ma remisu: 2 x chory, 1 x zdrowy -> chory
- czterech sąsiadów daje nam problem: 2 x chory, 2 x zdrowy -> ?
Możemy tak iść dalej, aż dojdziemy do wszystkich przebadanych uprzednio pacjentów. Czy widzisz już tutaj hiperparametr?
Idea – dwa wymiary
Okazuje się, że dla każdego pacjenta możemy też uzyskać informację o płci. Super, mamy więc drugi wymiar. Zakodujemy go 0 lub 1, w zależności jaką nomenklaturę sobie przyjmiemy. Weźmy losowo, że 1 oznacza mężczyznę, a 0 kobietę. Gdy już wyskalujemy nasze dane, naszym oczom ukaże się następująca płaszczyzna:
Gdy w tej sytuacji poszukamy najbliższych sąsiadów, to będziemy trafiać na kolejno numerowane obserwacje. Nasze predykcje będą więc wyglądać następująco:
- dla k = 1 jest 1 x chory -> chory
- przy k = 2 otrzymujemy 1 x chory, 1 x zdrowy -> ?
- jeśli k = 3 to 1 x chory, 2 x zdrowy -> zdrowy
- a dla k = 4 sytuacja wygląda tak: 1 x chory, 3 x zdrowy -> zdrowy
Widzimy więc, że dość mocno nam się tutaj sytuacja zmieniła. Faktem jest, że mamy bardzo mało danych, więc jest to całkiem możliwe. W każdym razie liczę, że ogólna idea jest już wyklarowana.
W ten sam sposób możemy dokładać kolejne wymiary. Nie musimy się przejmować ich wizualizacją, istotny dla nas będzie natomiast sposób wyliczania odległości. O tym możesz więcej przeczytać tutaj.
K najbliższych sąsiadów – funkcja w Pythonie
Przyjrzyjmy się, jak możemy zastosować funkcję KNeighborsClassifier dla zbioru Breast Cancer. Przygotujmy sobie zbiór danych (jest to już chyba mój standardowy snippet Breast Cancer, więc jeśli już go widziałeś, to możesz spokojnie pójść dalej):
# Kod 1
import pandas as pd
from sklearn.datasets import load_breast_cancer
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
breast_cancer = load_breast_cancer()
X = pd.DataFrame(breast_cancer["data"],
columns = breast_cancer["feature_names"])
y = pd.Series(breast_cancer["target"])
X_train, X_test, y_train, y_test = train_test_split(X, y,
test_size = 0.25,
random_state = 42)
Jako że użyjemy mojego ulubionego Scikit-Learn, stworzenie modelu, wytrenowanie go i ocena będą bardzo łatwe i zgodne z już poznanymi przez nas standardami:
# Kod 2 knn = KNeighborsClassifier() knn.fit(X = X_train, y = y_train) train_score = knn.score(X = X_train, y = y_train) test_score = knn.score(X = X_test, y = y_test) train_score, test_score
Za to właśnie lubimy Scikit-Learn 😉
Hiperparametry
Oczywiście, żeby nie było zbyt różowo, w przypadku tej funkcji również powinniśmy się zająć hiperparametrami. Jest ich trochę, ale nas będą interesować w zasadzie tylko trzy:
- n_neighbors – najważniejszy, najprostszy w zrozumieniu i chyba najtrudniejszy w wyznaczeniu hiperparametr. Mówi nam o tym, ilu najbliższych sąsiadów zostanie włączonych do predykcji. Domyślna wartość to 5.
- weights – tutaj definiujemy, czy waga cechy (bądź wartości), którą przewidujemy, będzie taka sama u każdego sąsiada, czy też może ta waga będzie proporcjonalna do odległości. Domyślna wartość to uniform.
- p – to chyba najbardziej skomplikowany hiperparametr. Mówi nam którą wersję przestrzeni Minkowskiego użyjemy do wyznaczania odległości. Jeśli będzie to 1, to użyjemy metryki manhattańskiej, jeśli 2 to euklidesowej. Możemy też wstawiać kolejne liczby naturalne, ale będziemy mieć wtedy problemy z interpretowaniem tych odległości. Domyślna wartość to 2.
Przypomnijmy sobie, jak łatwo możemy wyznaczyć te hiperparametry:
%%time
# Kod 3
from sklearn.model_selection import GridSearchCV
param_grid = {'n_neighbors': range(1, 101),
'weights': ["uniform", "distance"],
'p': [1, 2]
}
knn_grid_search = GridSearchCV(estimator = KNeighborsClassifier(), param_grid = param_grid, cv = 5, iid = False)
knn_grid_search.fit(X = X_train, y = y_train)
grid_train_score = knn_grid_search.score(X = X_train, y = y_train)
grid_test_score = knn_grid_search.score(X = X_test, y = y_test)
print(grid_train_score, grid_test_score)
print(knn_grid_search.best_params_)
Podsumowanie
Jak się okazuje intuicja, którą ludzkość ma ze sobą „od zawsze” całkiem fajnie może się sprawdzić w dokonywaniu predykcji. Wiemy już, że stosując algorytm K najbliższych sąsiadów, nie robimy nic szczególnie magicznego. Ale jeśli okaże się, że działa, to dlaczego by nie?
Jeśli interesuje Cię jakiś temat – nie musi być związany z tym artykułem – to zostaw mi sygnał tutaj. Dzięki!
Pełny kod przykładu użytego w artykule znajduje się tutaj.