Co to jest KNN (K-najbliżsi sąsiedzi)?

Co to jest K-najbliżsi sąsiedzi (KNN)?

K-Nearest Neighbors to technika i algorytm uczenia maszynowego, który można używać zarówno do zadań regresyjnych, jak i klasyfikacyjnych. K-Najbliżsi sąsiedzi zbadać etykiety wybranej liczby punktów danych wokół docelowego punktu danych, aby przewidzieć klasę, do której należy ten punkt danych. K-Nearest Neighbors (KNN) to koncepcyjnie prosty, ale bardzo potężny algorytm i z tego powodu jest jednym z najpopularniejszych algorytmów uczenia maszynowego. Przyjrzyjmy się bliżej algorytmowi KNN i zobaczmy dokładnie, jak on działa. Dobre zrozumienie sposobu działania KNN pozwoli Ci ocenić najlepsze i najgorsze przypadki użycia KNN.

Przegląd K-najbliższych sąsiadów (KNN)

Zdjęcie: Antti Ajanki AnAj za pośrednictwem Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:KnnClassification.svg)

Zwizualizujmy zbiór danych na płaszczyźnie 2D. Wyobraź sobie kilka punktów danych na wykresie rozmieszczonych wzdłuż wykresu w małych skupiskach. KNN bada rozkład punktów danych i w zależności od argumentów podanych do modelu dzieli punkty danych na grupy. Grupom tym przypisuje się następnie etykietę. Podstawowym założeniem modelu KNN jest to, że punkty/instancje danych istniejące blisko siebie są bardzo podobne, natomiast jeśli punkt danych jest daleko od innej grupy, nie jest podobny do tych punktów danych.

Model KNN oblicza podobieństwo na podstawie odległości między dwoma punktami na wykresie. Im większa odległość między punktami, tym mniej są one podobne. Istnieje wiele sposobów obliczania odległości między punktami, ale najczęstszą metryką odległości jest po prostu odległość euklidesowa (odległość między dwoma punktami w linii prostej).

KNN jest algorytmem uczenia się nadzorowanego, co oznacza, że ​​przykłady w zbiorze danych muszą mieć przypisane etykiety/ich klasy muszą być znane. Są dwie inne ważne rzeczy, które warto wiedzieć o KNN. Po pierwsze, KNN jest algorytmem nieparametrycznym. Oznacza to, że podczas stosowania modelu nie są dokonywane żadne założenia dotyczące zbioru danych. Model jest raczej zbudowany w całości na podstawie dostarczonych danych. Po drugie, przy użyciu KNN nie ma podziału zbioru danych na zbiory uczące i testowe. KNN nie dokonuje żadnych uogólnień między zbiorem uczącym i testowym, więc wszystkie dane uczące są również wykorzystywane, gdy model jest proszony o dokonanie prognoz.

Jak działa algorytm KNN

Algorytm KNN podczas realizacji przechodzi przez trzy główne fazy:

1. Ustawienie K na wybraną liczbę sąsiadów.
2. Obliczanie odległości między dostarczonym/testowanym przykładem a przykładami ze zbioru danych.
3. Sortowanie obliczonych odległości.
4. Pobieranie etykiet najważniejszych wpisów K.
5. Zwracanie prognozy dotyczącej przykładu testowego.

W pierwszym kroku użytkownik wybiera K i mówi algorytmowi, ilu sąsiadów (ile otaczających punktów danych) należy wziąć pod uwagę przy ocenie grupy, do której należy docelowy przykład. W drugim kroku zauważ, że model sprawdza odległość między przykładem docelowym a każdym przykładem w zbiorze danych. Odległości są następnie dodawane do listy i sortowane. Następnie sprawdzana jest posortowana lista i zwracane są etykiety dla K górnych elementów. Innymi słowy, jeśli K jest ustawione na 5, model sprawdza etykiety 5 górnych punktów danych znajdujących się najbliżej docelowego punktu danych. Podczas renderowania prognozy dotyczącej docelowego punktu danych znaczenie ma to, czy zadaniem jest a regresja or klasyfikacja zadanie. W zadaniu regresji wykorzystuje się średnią z górnych K etykiet, natomiast w przypadku klasyfikacji stosuje się tryb z górnych K etykiet.

Dokładne operacje matematyczne stosowane do przeprowadzenia KNN różnią się w zależności od wybranej metryki odległości. Jeśli chcesz dowiedzieć się więcej o tym, jak obliczane są dane, możesz przeczytać o niektórych najpopularniejszych wskaźnikach odległości, takich jak Euklidesa, Manhattan, Minkowskiego.

Dlaczego wartość K ma znaczenie

Głównym ograniczeniem podczas korzystania z KNN jest to, że przy niewłaściwej wartości K (niewłaściwa liczba sąsiadów, które należy wziąć pod uwagę), może zostać wybrana. Jeśli tak się stanie, zwracane prognozy mogą znacznie się różnić. Bardzo ważne jest, aby przy zastosowaniu algorytmu KNN wybrać odpowiednią wartość K. Chcesz wybrać wartość K, która maksymalizuje zdolność modelu do przewidywania niewidocznych danych, jednocześnie zmniejszając liczbę popełnianych błędów.

Zdjęcie: Agor153 za pośrednictwem Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)

Niższe wartości K oznaczają, że przewidywania KNN są mniej stabilne i wiarygodne. Aby zrozumieć, dlaczego tak się dzieje, rozważmy przypadek, w którym mamy 7 sąsiadów wokół docelowego punktu danych. Załóżmy, że model KNN działa z wartością K wynoszącą 2 (prosimy go, aby w celu przewidzenia przyjrzał się dwóm najbliższym sąsiadom). Jeśli zdecydowana większość sąsiadów (pięciu z siedmiu) należy do klasy Blue, ale tak się składa, że ​​dwóch najbliższych sąsiadów to Red, model przewidzi, że przykładowe zapytanie to Red. Pomimo przypuszczeń modela, w takim scenariuszu lepszym wyborem byłby kolor niebieski.

Jeśli tak jest, dlaczego nie wybrać po prostu najwyższej możliwej wartości K? Dzieje się tak, ponieważ nakazanie modelowi uwzględnienia zbyt wielu sąsiadów również zmniejszy dokładność. W miarę wzrostu promienia uwzględnianego w modelu KNN w końcu zacznie on uwzględniać punkty danych znajdujące się bliżej innych grup niż docelowy punkt danych i zacznie się pojawiać błędna klasyfikacja. Na przykład, nawet jeśli początkowo wybrany punkt znajdował się w jednym z czerwonych obszarów powyżej, jeśli K zostało ustawione zbyt wysoko, model sięgałby do innych obszarów, aby uwzględnić punkty. Podczas korzystania z modelu KNN próbuje się różnych wartości K, aby sprawdzić, która wartość zapewnia modelowi najlepszą wydajność.

KNN Plusy i minusy

Przyjrzyjmy się niektórym zaletom i wadom modelu KNN.

Plusy:

W przeciwieństwie do innych algorytmów uczenia się nadzorowanego, KNN może być używany zarówno do zadań regresji, jak i klasyfikacji.

KNN jest bardzo dokładny i prosty w użyciu. Jest łatwy do zinterpretowania, zrozumienia i wdrożenia.

KNN nie przyjmuje żadnych założeń na temat danych, co oznacza, że ​​można je wykorzystać do wielu różnych problemów.

Wady:

KNN przechowuje większość lub wszystkie dane, co oznacza, że ​​model wymaga dużej ilości pamięci i jest kosztowny obliczeniowo. Duże zbiory danych mogą również powodować, że przewidywanie będzie trwało długo.

KNN okazuje się bardzo wrażliwy na skalę zbioru danych i w porównaniu z innymi modelami dość łatwo może zostać odrzucony przez nieistotne cechy.

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

K-Nearest Neighbors to jeden z najprostszych algorytmów uczenia maszynowego. Pomimo tego, jak prosty jest KNN, w koncepcji jest to także potężny algorytm, który zapewnia dość wysoką dokładność w przypadku większości problemów. Korzystając z KNN, należy poeksperymentować z różnymi wartościami K, aby znaleźć liczbę zapewniającą najwyższą dokładność.