Algorytm k-Najbliższych Sąsiadów
Wcześniej widzieliśmy, jak moglibyśmy zastosować proste techniki korelacyjne, aby stworzyć miarę podobieństwa między członkami Kongresu na podstawie ich wyników głosowania. Tu porozmawiamy o tym, jak korzystać z tych samych wskaźników podobieństwa, aby polecać produkty użytkownikom witryny. Algorytm, którego użyjemy, nazywa się k-najbliższych sąsiadów. Jest to prawdopodobnie najbardziej intuicyjny ze wszystkich algorytmów uczenia maszynowego, które prezentujemy. Rzeczywiście, najprostszą formą najbliższych sąsiadów jest algorytm, który większość ludzi wymyśliłaby spontanicznie, gdyby poproszono ich o rekomendacje na podstawie danych podobieństwa: poleciliby utwór, który jest najbliższy utworom, które użytkownik już lubi, ale których jeszcze nie ma na tej liście. Ta intuicja jest zasadniczo algorytmem najbliższego sąsiada. Algorytm pełnego k-najbliższego sąsiada stanowi uogólnienie tej intuicji, w której przed wydaniem zalecenia korzystasz z więcej niż jednego punktu danych. Algorytm pełnego k najbliższych sąsiadów działa bardzo podobnie, jak niektórzy z nas proszą o rekomendacje od naszych przyjaciół. Najpierw zaczynamy od ludzi, których gust dzielimy, a potem prosimy ich, aby coś nam polecili. Jeśli wielu z nich poleca to samo, wywnioskujemy, że nam się spodoba. Jak możemy wziąć tę intuicję i przekształcić ją w coś algorytmicznego? Zanim zaczniemy opracowywać rekomendacje na podstawie rzeczywistych danych, zacznijmy od czegoś prostszego: podzielenie punktów na dwie kategorie. Jeśli pamiętasz, jak po raz pierwszy zmotywowaliśmy problem klasyfikacji spamu
Jak wyjaśniliśmy, możesz użyć regresji logistycznej za pomocą funkcji glm, aby podzielić te punkty za pomocą pojedynczej linii, którą nazwaliśmy granicą decyzji. W tym samym czasie, gdy wyjaśniliśmy, jak stosować regresję logistyczną, powiedzieliśmy również, że istnieją problemy których nie można rozwiązać za pomocą prostej liniowej granicy decyzji.
Jak możesz spróbować zbudować klasyfikator, który pasowałby do bardziej skomplikowanej granicy decyzyjnej, takiej jak ta pokazana na powyższym rysunku? Możesz spróbować wymyślić metodę nieliniową; sztuczka jądra, którą omówimy później, jest przykładem tego podejścia.
Innym podejściem byłoby wykorzystanie punktów najbliższych punktowi, który próbujesz sklasyfikować, aby zgadnąć. Możesz na przykład narysować okrąg wokół punktu, na który patrzysz, a następnie zdecydować o klasyfikacji na podstawie punktów w tym okręgu.
Ten algorytm jest całkiem użyteczny, ale ma jedną zauważalną wadę: musimy wybrać promień okręgu, którego użyjemy do zdefiniowania „lokalnych” punktów. Jeśli wszystkie twoje punkty danych mają sąsiadów w przybliżeniu w tej samej odległości, nie będzie problemu. Ale jeśli niektóre punkty mają wielu bliskich sąsiadów, podczas gdy inne prawie ich nie mają, w końcu wybierzesz okrąg, który jest tak duży, że wykracza daleko poza granice decyzji dla niektórych punktów. Co możemy zrobić, aby obejść ten problem? Oczywistym rozwiązaniem jest uniknięcie użycia koła do zdefiniowania sąsiadów punktu i zamiast tego spojrzenie na k-najbliższych punktów. Punkty te nazywane są najbliższymi sąsiadami. Gdy już je mamy, możemy spojrzeć na ich klasyfikacje i użyć reguły większości, aby zdecydować o klasie dla naszego nowego punktu. Zbudujmy kod, aby właśnie to zrobić.
Najpierw przeczytamy w naszym zestawie danych:
df <- read.csv(‘data/example_data.csv’)
head(df)
# X Y Label
#1 2.373546 5.398106 0
#2 3.183643 4.387974 0
#3 2.164371 5.341120 0
#4 4.595281 3.870637 0
#5 3.329508 6.433024 0
#6 2.179532 6.980400 0
Następnie musimy obliczyć odległość między każdym punktem w naszym zbiorze danych. Będziemy przechowywać te informacje w macierzy odległości, która jest prostą macierzą 2D, w której odległość między punktem i a punktem j znajduje się przy wprowadzeniu tablicy odległości. Matryca [i, j]. Poniższy kod tworzy tę macierz odległości przy użyciu wzoru odległości euklidesowej:
distance.matrix <- function(df)
{
distance <- matrix(rep(NA, nrow(df) ^ 2), nrow = nrow(df))
for (i in 1:nrow(df))
{
for (j in 1:nrow(df))
{
distance[i, j] <- sqrt((df[i, ‘X’] – df[j, ‘X’]) ^ 2 + (df[i, ‘Y’] – df[j, ‘Y’])
^ 2)
}
}
return(distance)
}
Kiedy mamy już macierz odległości, potrzebujemy funkcji, która zwróci k najbliższych sąsiadów dla punktu. Jest to naprawdę łatwe do zaimplementowania w R, ponieważ możesz po prostu spojrzeć na i-ty rząd macierzy odległości, aby dowiedzieć się, jak daleko są wszystkie inne punkty od twojego punktu wejściowego. Po posortowaniu tego wiersza masz uporządkowaną listę sąsiadów i ich odległość od punktu wejściowego.
Po prostu wybierz pierwsze k wpisów po zignorowaniu punktu wejściowego (który zawsze powinien być pierwszym punktem w macierzy odległości), a będziesz mieć k najbliższych sąsiadów swojego punktu wejściowego.
k.nearest.neighbors <- function(i, distance, k = 5)
{
return(order(distance[i, ])[2:(k + 1)])
}
Gdy to zrobisz, zbudujemy funkcję knn, która pobiera ramkę danych i wartość k, a następnie generuje prognozy dla każdego punktu w ramce danych. Nasza funkcja nie jest bardzo ogólna, ponieważ zakładamy, że etykiety klas znajdują się w kolumnie o nazwie Etykieta, ale jest to tylko szybkie ćwiczenie, aby zobaczyć, jak działa algorytm. Istnieją już implementacje k-najbliższych sąsiadów w R, które możesz wykorzystać do praktycznej pracy, a my omówimy je za chwilę
knn <- function(df, k = 5)
{
distance <- distance.matrix(df)
predictions <- rep(NA, nrow(df))
for (i in 1:nrow(df))
{
indices <- k.nearest.neighbors(i, distance, k = k)
predictions[i] <- ifelse(mean(df[indices, ‘Label’]) > 0.5, 1, 0)
}
return(predictions)
}
Jak widać, wykorzystaliśmy zasady głosowania większością do naszych prognoz, przyjmując średnią etykietę, a następnie próg na poziomie 0,5. Wywołanie tej funkcji zwraca wektor prognoz, dlatego dołączamy je do naszej ramki danych, a następnie oceniamy naszą wydajność:
df <- transform(df, kNNPredictions = knn(df))
sum(with(df, Label != kNNPredictions))
#[1] 7
nrow(df)
#[1] 100
Niepoprawnie przewidzieliśmy etykiety dla 7 punktów na 100, więc mamy 93% czasu. To niezła wydajność jak na tak prosty algorytm. Teraz, gdy wyjaśniliśmy, jak działa algorytm k-najbliższych sąsiadów (kNN), zastosujemy kNN do niektórych rzeczywistych danych o użyciu pakietów R. Ale zanim to zrobimy, pokażemy Ci, jak używać implementacji kNN w czarnej skrzynce do własnych projektów:
rm (‘knn’) # Jeśli nadal masz naszą implementację w pamięci.
library(‘class’)
df <- read.csv(‘data/example_data.csv’)
n <- nrow(df)
set.seed(1)
indices <- sort(sample(1:n, n * (1 / 2)))
training.x <- df[indices, 1:2]
test.x <- df[-indices, 1:2]
training.y <- df[indices, 3]
test.y <- df[-indices, 3]
predicted.y <- knn(training.x, test.x, training.y, k = 5)
sum(predicted.y != test.y)
#[1] 7
length(test.y)
#[1] 50
Tutaj przetestowaliśmy funkcję knn z pakietu klas przy użyciu weryfikacji krzyżowej. O dziwo, tutaj również błędnie popełniamy 7 etykiet, ale zestaw testowy zawiera tylko 50 przykładów, więc osiągamy jedynie 86% dokładności. To wciąż jest całkiem niezłe. Pokażmy tylko, jak działałby model logistyczny, aby dać ci punkt porównania:
logit.model <- glm(Label ~ X + Y, data = df[indices, ])
predictions <- as.numeric(predict(logit.model, newdata = df[-indices, ]) > 0)
sum(predictions != test.y)
#[1] 16
Jak widać, najlepszy klasyfikator logistyczny błędnie przewiduje 16 punktów danych, co daje mu dokładność 68%. Kiedy twój problem jest daleki od liniowości, kNN będzie działać od razu znacznie lepiej niż inne metody.