Co to jest K-Nearest Neighbors (KNN)?

Co to jest K-Nearest Neighbors (KNN)?

K-Nearest Neighbors to technika i algorytm uczenia maszynowego, który może być użyty zarówno do zadań regresji, jak i klasyfikacji. K-Nearest Neighbors sprawdza etykiety wybranej liczby punktów danych wokół punktu danych docelowego, aby zrobić przewidywanie dotyczące klasy, do której należy punkt danych. K-Nearest Neighbors (KNN) to pojęcie proste, lecz bardzo potężne algorytmy, i z tego powodu jest to jeden z najpopularniejszych algorytmów uczenia maszynowego. Zobaczmy, jak dokładnie działa algorytm KNN. Posiadanie dobrego zrozumienia, jak KNN działa, pozwoli nam docenić najlepsze i najgorsze przypadki użycia KNN.

Przegląd K-Nearest Neighbors (KNN)

Foto: Antti Ajanki AnAj via Wikimedia Commons, CC BY SA 3.0 (https://commons.wikimedia.org/wiki/File:KnnClassification.svg)

Wyobraźmy sobie zestaw danych na płaszczyźnie 2D. Wyobraźmy sobie mnóstwo punktów danych na wykresie, rozproszonych po wykresie w małych klastrach. KNN sprawdza rozkład punktów danych i, w zależności od argumentów podanych modelowi, dzieli punkty danych na grupy. Grupy te są następnie oznaczone etykietą. Głównym założeniem, które model KNN przyjmuje, jest to, że punkty danych/instancje, które istnieją w bliskiej odległości od siebie, są bardzo podobne, podczas gdy jeśli punkt danych jest daleko od innej grupy, jest on niepodobny do tych punktów danych.

Model KNN oblicza podobieństwo za pomocą 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ęstszym miernikiem odległości jest po prostu odległość euklidesowa (odległość między dwoma punktami w linii prostej).

KNN to algorytm uczenia nadzorowanego, co oznacza, że przykłady w zestawie danych muszą mieć przypisane etykiety/klasy muszą być znane. Są dwie inne ważne rzeczy, które należy wiedzieć o KNN. Po pierwsze, KNN to algorytm nieparametryczny. Oznacza to, że nie są robione żadne założenia o zestawie danych, gdy model jest używany. Zamiast tego, model jest budowany całkowicie z dostarczonych danych. Po drugie, nie ma podziału zestawu danych na zestaw treningowy i testowy podczas używania KNN. KNN nie robi uogólnień między zestawem treningowym a testowym, więc cały zestaw treningowy jest również używany, gdy model jest proszony o podjęcie przewidywań.

Jak działa algorytm KNN

Algorytm KNN przechodzi przez trzy główne fazy, gdy jest wykonywany:

1. Ustawienie K na wybraną liczbę sąsiadów.
2. Obliczanie odległości między podanym/przykładowym punktem danych a przykładami w zestawie danych.
3. Sortowanie obliczonych odległości.
4. Pobieranie etykiet najwyższych K wpisów.
5. Zwrócenie przewidywania dotyczącego punktu danych testowego.

W pierwszym kroku K jest wybrany przez użytkownika i informuje algorytm, ile sąsiadów (ile punktów danych otaczających) powinno być branych pod uwagę przy podejmowaniu decyzji o grupie, do której należy punkt danych docelowy. W drugim kroku zwróć uwagę, że model sprawdza odległość między punktem danych docelowym a każdym punktem danych w zestawie danych. Odległości są następnie dodawane do listy i sortowane. Następnie posortowana lista jest sprawdzana, a etykiety dla najwyższych K elementów są zwracane. Innymi słowy, jeśli K jest ustawiony na 5, model sprawdza etykiety pięciu najbliższych punktów danych do punktu danych docelowego. Przy podejmowaniu przewidywań dotyczących punktu danych docelowego istotne jest, czy zadanie jest regresją czy klasyfikacją. W przypadku zadania regresji używana jest średnia z najwyższych K etykiet, podczas gdy w przypadku klasyfikacji używany jest tryb najwyższych K etykiet.

Dokładne operacje matematyczne używane do wykonania KNN różnią się w zależności od wybranego miernika odległości. Jeśli chcesz dowiedzieć się więcej o tym, jak są obliczane mierniki, możesz przeczytać o niektórych z najczęstszych mierników odległości, takich jak euklidesowy, manhattanowski i minkowskiego.

Dlaczego wartość K ma znaczenie

Głównym ograniczeniem podczas używania KNN jest to, że może być wybrana niewłaściwa wartość K (niewłaściwa liczba sąsiadów do rozważenia). Jeśli tak się stanie, przewidywania zwracane przez model mogą być znacznie błędne. Bardzo ważne jest, aby podczas używania algorytmu KNN wybrano odpowiednią wartość K. Chcesz wybrać wartość K, która maksymalizuje zdolność modelu do podejmowania przewidywań na nieznanym danych, jednocześnie redukując liczbę błędów, które popełnia.

Foto: Agor153 via Wikimedia Commons, CC BY SA 3.0 (https://en.wikipedia.org/wiki/File:Map1NN.png)

Niskie wartości K oznaczają, że przewidywania podane przez KNN są mniej stabilne i niezawodne. Aby uzyskać intuicję, dlaczego tak jest, rozważmy przypadku, w którym mamy 7 sąsiadów wokół punktu danych docelowego. Załóżmy, że model KNN działa z wartością K 2 (poproszono go o sprawdzenie dwóch najbliższych sąsiadów, aby zrobić przewidywanie). Jeśli ogromna większość sąsiadów (pięć z siedmiu) należy do klasy Niebieskiej, ale dwa najbliższe sąsiedzi przypadkowo są Czerwone, model przewiduje, że przykład testowy jest Czerwony. Pomimo przewidywania modelu, w takim scenariuszu Niebieski byłby lepszym przewidywaniem.

Jeśli tak jest, dlaczego nie wybrać po prostu najwyższej wartości K, jaką możemy? Jest to dlatego, że nakazanie modelowi rozważenia zbyt wielu sąsiadów również zmniejszy dokładność. Im większy promień, który model KNN rozważa, tym bardziej zacznie on rozważać punkty danych, które są bliżej innych grup niż punkt danych docelowy, i zacznie występować błąd klasyfikacji. Na przykład, nawet jeśli punkt, który został wybrany, znajdował się w jednym z czerwonych regionów powyżej, jeśli K został ustawiony zbyt wysoko, model dotrze do innych regionów, aby rozważyć punkty. Podczas używania modelu KNN próbuje się różne wartości K, aby zobaczyć, jaka wartość daje modelowi najlepszą wydajność.

Zalety i wady KNN

Zobaczmy niektóre zalety i wady modelu KNN.

Zalety:

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

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

KNN nie robi żadnych założeń o danych, co oznacza, że może być użyty do szerokiej gamy problemów.

Wady:

KNN przechowuje większość lub wszystkie dane, co oznacza, że model wymaga dużej ilości pamięci i jest obliczeniowo kosztowny. Duże zestawy danych mogą również powodować, że przewidywania zajmują dużo czasu.

KNN okazuje się bardzo wrażliwy na skalę zestawu danych i może być łatwo zmylony przez nieistotne cechy w porównaniu z innymi modelami.

Podsumowanie K-Nearest Neighbors (KNN)

K-Nearest Neighbors to jeden z najprostszych algorytmów uczenia maszynowego. Pomimo prostej koncepcji KNN, jest to potężny algorytm, który daje dość wysoką dokładność w większości problemów. Kiedy używasz KNN, upewnij się, że eksperymentujesz z różnymi wartościami K, aby znaleźć liczbę, która daje najwyższą dokładność.