K-Nearest Neighbors (KNN): co to jest i jak jest wykorzystywane w uczeniu maszynowym

K-najbliżsi sąsiedzi (KNN) to podstawowa technika uczenia maszynowego (ML). Ten przewodnik pomoże Ci zrozumieć KNN, jego działanie oraz jego zastosowania, korzyści i wyzwania.

Spis treści

Jaki jest algorytm k-najbliższych sąsiadów?

Jak działa KNN?

Różnica między k-najbliższymi sąsiadami a innymi algorytmami

W jaki sposób KNN jest wykorzystywane w uczeniu maszynowym?

Zastosowania KNN

Zalety KNN

Wady KNN

Jaki jest algorytm k-najbliższych sąsiadów?

Algorytm k-najbliższych sąsiadów (KNN) to technika nadzorowanego uczenia się stosowana zarówno do klasyfikacji, jak i regresji. KNN określa etykietę (klasyfikację) lub przewidywaną wartość (regresję) danego punktu danych, oceniając pobliskie punkty danych w zbiorze danych.

Jak działa KNN?

KNN opiera się na założeniu, że punkty danych, które są przestrzennie blisko siebie w zbiorze danych, mają zwykle podobne wartości lub należą do podobnych kategorii. KNN wykorzystuje ten prosty, ale skuteczny pomysł do klasyfikowania nowego punktu danych poprzez znalezienie wstępnie ustawionej liczby (hiperparametru k) sąsiadujących punktów danych w oznaczonym zbiorze danych szkoleniowych. Ta wartość k jest jednym z hiperparametrów KNN, które są wstępnie ustawionymi zmiennymi konfiguracyjnymi używanymi przez praktyków ML do kontrolowania sposobu uczenia się algorytmu.

Następnie algorytm określa, które z sąsiednich wartości są najbliżej nowego punktu danych i przypisuje mu tę samą etykietę lub kategorię, co jego sąsiedzi. Wybrana wartość k wpływa na wydajność modelu. Mniejsze wartości zwiększają czułość na szum, podczas gdy większe wartości zwiększają niezawodność, ale mogą spowodować, że KNN przeoczy lokalne wzorce.

Bliskość lub odległość między punktami danych jest obliczana przy użyciu metryk pierwotnie opracowanych do pomiaru podobieństwa punktów w przestrzeni matematycznej. Typowe metryki obejmują odległość euklidesową, odległość Manhattanu i odległość Minkowskiego. Wybrana metryka ma wpływ na wydajność KNN, a różne metryki działają lepiej w przypadku różnych typów i rozmiarów danych.

Na przykład liczba wymiarów w danych, które są indywidualnymi atrybutami opisującymi każdy punkt danych, może mieć wpływ na wydajność metryki. Niezależnie od wybranej metryki odległości celem jest kategoryzowanie lub przewidywanie nowego punktu danych na podstawie jego odległości od innych punktów danych.

• Odległość euklidesowato odległość na linii prostej między dwoma punktami w przestrzeni i jest najczęściej używaną metryką. Najlepiej stosować go w przypadku danych o mniejszej liczbie wymiarów i bez znaczących wartości odstających.
• Odległość Manhattanto suma bezwzględnych różnic pomiędzy współrzędnymi mierzonych punktów. Ta metryka jest przydatna, gdy dane są wielowymiarowe lub gdy punkty danych tworzą strukturę przypominającą siatkę.
• Odległość Minkowskiegoto przestrajalna metryka, która może działać jak odległość euklidesowa lub manhattańska, w zależności od wartości regulowanego parametru. Dostosowanie tego parametru kontroluje sposób obliczania odległości, co jest przydatne przy dostosowywaniu KNN do różnych typów danych.

Inne, mniej powszechne metryki obejmują odległości Czebyszewa, Hamminga i Mahalanobisa. Metryki te są bardziej wyspecjalizowane i nadają się do określonych typów danych i dystrybucji. Na przykład odległość Mahalanobisa mierzy odległość punktu od rozkładu punktów, biorąc pod uwagę relacje między zmiennymi. W związku z tym odległość Mahalanobisa dobrze nadaje się do pracy z danymi, w których funkcje korzystają z różnych skal.

KNN jest często nazywany „leniwym” algorytmem uczenia się, ponieważ w przeciwieństwie do wielu innych algorytmów nie wymaga szkolenia. Zamiast tego KNN przechowuje dane i wykorzystuje je do podejmowania decyzji tylko wtedy, gdy nowe punkty danych wymagają regresji lub klasyfikacji. Oznacza to jednak, że prognozy często mają wysokie wymagania obliczeniowe, ponieważ dla każdej prognozy oceniany jest cały zbiór danych. ∫

Różnica między k-najbliższymi sąsiadami a innymi algorytmami

KNN jest częścią większej rodziny nadzorowanych technik uczenia maszynowego ukierunkowanych na klasyfikację i regresję, która obejmuje drzewa decyzyjne/lasy losowe, regresję logistyczną i maszyny wektorów nośnych (SVM). Jednak KNN różni się od tych technik między innymi prostotą i bezpośrednim podejściem do przetwarzania danych.

Drzewa decyzyjne i lasy losowe

Podobnie jak KNN, drzewa decyzyjne i lasy losowe służą do klasyfikacji i regresji. Jednak algorytmy te wykorzystują wyraźne reguły wyuczone na podstawie danych podczas uczenia, w przeciwieństwie do podejścia KNN opartego na odległości. Drzewa decyzyjne i lasy losowe charakteryzują się zazwyczaj większą szybkością przewidywania, ponieważ mają wstępnie wytrenowane reguły. Oznacza to, że lepiej niż KNN nadają się do zadań predykcyjnych w czasie rzeczywistym i obsługi dużych zbiorów danych.

Regresja logistyczna

Regresja logistyczna zakłada, że ​​dane mają rozkład liniowy i klasyfikuje dane za pomocą linii prostej lub hiperpłaszczyzny (granicy oddzielającej punkty danych w przestrzeniach o wyższych wymiarach), aby podzielić dane na kategorie. Z drugiej strony KNN nie zakłada szczególnego rozkładu danych. W związku z tym KNN może łatwiej dostosować się do złożonych lub nieliniowych danych, podczas gdy regresję logistyczną najlepiej stosować w przypadku danych liniowych.

Obsługa maszyn wektorowych

Zamiast patrzeć na odległości między punktami, jak KNN, maszyny wektorów nośnych (SVM) skupiają się na tworzeniu wyraźnej linii podziału między grupami punktów danych, często w celu maksymalnego zwiększenia odstępu między nimi. SVM doskonale radzi sobie ze złożonymi zbiorami danych z wieloma funkcjami lub gdy konieczne jest wyraźne oddzielenie grup punktów danych. Dla porównania, KNN jest prostszy w obsłudze i zrozumieniu, ale nie działa tak dobrze na dużych zbiorach danych.

W jaki sposób KNN jest wykorzystywane w uczeniu maszynowym?

Wiele algorytmów ML może obsłużyć tylko jeden typ zadań. KNN wyróżnia się możliwością obsługi nie jednego, ale dwóch typowych przypadków użycia: klasyfikacji i regresji.

Klasyfikacja

KNN klasyfikuje punkty danych, wykorzystując metrykę odległości do określenia k najbliższych sąsiadów i przypisując etykietę do nowego punktu danych na podstawie etykiet sąsiadów. Typowe przypadki użycia klasyfikacji KNN obejmują klasyfikację spamu e-mailowego, grupowanie klientów w kategorie na podstawie historii zakupów i rozpoznawanie odręcznych numerów.

Regresja

KNN przeprowadza regresję, szacując wartość punktu danych na podstawie średniej (lub średniej ważonej) k-najbliższych sąsiadów. Na przykład KNN może przewidzieć ceny domów na podstawie podobnych nieruchomości w okolicy, ceny akcji na podstawie danych historycznych dla podobnych spółek lub temperaturę na podstawie historycznych danych pogodowych w podobnych lokalizacjach.

Zastosowania algorytmu KNN w ML

Ze względu na swoją względną prostotę i możliwość wykonywania zarówno klasyfikacji, jak i regresji, KNN ma szeroki zakres zastosowań. Należą do nich rozpoznawanie obrazów, systemy rekomendacji i klasyfikacja tekstu.

Rozpoznawanie obrazu

Rozpoznawanie obrazu jest jednym z najpowszechniejszych zastosowań KNN ze względu na jego możliwości klasyfikacyjne. KNN rozpoznaje obraz, porównując cechy nieznanego obrazu, takie jak kolory i kształty, z cechami zbioru danych obrazu oznaczonego etykietą. To sprawia, że ​​KNN jest przydatny w takich dziedzinach jak wizja komputerowa.

Systemy rekomendacji

KNN może polecać użytkownikom produkty lub treści, porównując ich dane dotyczące preferencji z danymi podobnych użytkowników. Na przykład, jeśli użytkownik przesłuchał kilka klasycznych utworów jazzowych, KNN może znaleźć użytkowników o podobnych preferencjach i polecić utwory, które im się podobały. W związku z tym KNN może pomóc w personalizowaniu doświadczenia użytkownika, polecając produkty lub treści w oparciu o podobne dane.

Klasyfikacja tekstu

Klasyfikacja tekstu ma na celu klasyfikację tekstu bez kategorii na podstawie jego podobieństwa do tekstu wstępnie skategoryzowanego. Zdolność KNN do oceny bliskości wzorców słów sprawia, że ​​jest to skuteczne narzędzie w tym przypadku użycia. Klasyfikacja tekstu jest szczególnie przydatna w przypadku zadań takich jak analiza nastrojów, podczas której teksty są klasyfikowane jako pozytywne, negatywne lub neutralne, lub przy określaniu kategorii artykułu prasowego.

Zalety algorytmu KNN w ML

KNN ma kilka znaczących zalet, w tym prostotę, wszechstronność i brak fazy szkoleniowej.

Prostota

W porównaniu do wielu innych algorytmów ML, KNN jest łatwy do zrozumienia i użycia. Logika stojąca za KNN jest intuicyjna — klasyfikuje lub przewiduje (regresję) nowe punkty danych w oparciu o wartości pobliskich punktów danych — co czyni go popularnym wyborem dla praktyków ML, zwłaszcza początkujących. Ponadto, poza wyborem wartości k, do korzystania z KNN wymagane jest minimalne dostrojenie hiperparametrów.

Wszechstronność

KNN można stosować zarówno do zadań klasyfikacyjnych, jak i regresyjnych, co oznacza, że ​​można go zastosować do szerokiego zakresu problemów i typów danych, od rozpoznawania obrazów po przewidywanie wartości liczbowych. W przeciwieństwie do wyspecjalizowanych algorytmów ograniczonych do jednego typu zadań, KNN można zastosować do dowolnego odpowiednio ustrukturyzowanego, oznaczonego zbioru danych.

Wyraźna faza szkolenia

Wiele modeli uczenia maszynowego wymaga fazy szkoleniowej wymagającej czasu i zasobów, zanim staną się przydatne. Z drugiej strony KNN po prostu przechowuje dane szkoleniowe i wykorzystuje je bezpośrednio w przewidywanym momencie. Dzięki temu KNN może być aktualizowany o nowe dane, które są natychmiast dostępne do wykorzystania w prognozach. To sprawia, że ​​KNN jest szczególnie atrakcyjny w przypadku małych zbiorów danych.

Wady algorytmu KNN w ML

Pomimo swoich mocnych stron KNN wiąże się także z kilkoma wyzwaniami. Należą do nich wysokie koszty obliczeń i pamięci, wrażliwość na szum i nieistotne funkcje oraz „przekleństwo wymiarowości”.

Koszt obliczeniowy predykcji

Ponieważ KNN oblicza odległość między nowym punktem danych a każdym punktem danych w swoim ogólnym zbiorze danych szkoleniowych za każdym razem, gdy dokonuje prognozy, koszt obliczeniowy przewidywania szybko rośnie wraz ze wzrostem zbioru danych. Może to skutkować powolnymi przewidywaniami, gdy zbiór danych jest duży lub KNN działa na niewystarczającym sprzęcie.

Przekleństwo wymiarowości

KNN cierpi na tzw. „przekleństwo wymiarowości”, które ogranicza jego zdolność do przetwarzania danych wielowymiarowych. Wraz ze wzrostem liczby obiektów w zbiorze danych większość punktów danych staje się nieliczna i znajduje się w niemal równej odległości od siebie. W związku z tym metryki odległości stają się mniej przydatne, co utrudnia KNN znalezienie sąsiadów w wielowymiarowych zbiorach danych, którzy są naprawdę blisko.

Intensywne wykorzystanie pamięci

Unikalną cechą KNN jest to, że przechowuje cały zestaw danych szkoleniowych w pamięci do wykorzystania w momencie przewidywania. W przypadku ograniczonej pamięci lub dużych zbiorów danych może to być problematyczne i niepraktyczne. Inne algorytmy ML unikają tego wyzwania, kondensując i przekształcając dane szkoleniowe w wyuczone funkcje poprzez szkolenie modeli i optymalizację parametrów. Z drugiej strony KNN musi zachować każdy punkt danych, co oznacza, że ​​pamięć rośnie liniowo wraz z rozmiarem zbioru danych szkoleniowych.

Wrażliwość na hałas i nieistotne funkcje

Siła KNN leży w prostym, intuicyjnym obliczaniu odległości. Oznacza to jednak również, że nieistotne cechy lub szumy mogą powodować błędne obliczenia odległości, negatywnie wpływając na dokładność przewidywań. W związku z tym w KNN często stosuje się techniki selekcji cech lub redukcji wymiarowości, takie jak analiza głównych składowych (PCA), aby upewnić się, że ważne cechy mają największy wpływ na przewidywanie.