Co to jest najbliższy sąsiad K? Algorytm ML do klasyfikacji danych

Algorytmy napędzają świat uczenia maszynowego.

Często są chwaleni za ich zdolności przewidywania i mówi się o nich jako o ciężkich pracownikach, którzy zużywają ogromne ilości danych w celu uzyskania natychmiastowych wyników.

Wśród nich jest algorytm często określany jako leniwy. Ale jest całkiem wydajny, jeśli chodzi o klasyfikację punktów danych. Nazywa się to algorytmem k-najbliższych sąsiadów i jest często wymieniany jako jeden z najważniejszych   nauczanie maszynowe   algorytmy.

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

Algorytm k-najbliższych sąsiadów (KNN) to metoda klasyfikacji danych służąca do szacowania prawdopodobieństwa, że ​​punkt danych stanie się członkiem tej lub innej grupy, w oparciu o grupę, do której należą najbliższe punkty danych.

Algorytm k-najbliższego sąsiada jest typem   nadzorowane uczenie maszynowe   algorytm używany do rozwiązywania problemów klasyfikacji i regresji. Jest jednak używany głównie do problemów z klasyfikacją.

KNN to leniwy uczący się i nieparametryczny algorytm.

Nazywa się to algorytmem leniwego uczenia się lub leniwym uczeniem się, ponieważ nie przeprowadza żadnego szkolenia, gdy dostarczasz dane szkoleniowe. Zamiast tego po prostu przechowuje dane w czasie treningu i nie wykonuje żadnych obliczeń. Nie buduje modelu, dopóki zapytanie nie zostanie wykonane w zestawie danych. To sprawia, że ​​KNN jest idealne dla   eksploracja danych.

Jest uważana za metodę nieparametryczną, ponieważ nie przyjmuje żadnych założeń dotyczących podstawowej dystrybucji danych. Mówiąc najprościej, KNN próbuje określić, do jakiej grupy należy punkt danych, patrząc na punkty danych wokół niego.

Rozważmy dwie grupy, A i B.

Aby określić, czy punkt danych znajduje się w grupie A, czy w grupie B, algorytm sprawdza stany punktów danych znajdujących się w pobliżu. Jeśli większość punktów danych znajduje się w grupie A, jest bardzo prawdopodobne, że dany punkt danych znajduje się w grupie A i odwrotnie.

Krótko mówiąc, KNN polega na klasyfikowaniu punktu danych przez spojrzenie na najbliższy punkt danych z adnotacjami, znany również jako najbliższy sąsiad .

Nie myl klasyfikacji K-NN z grupowaniem K-średnich. KNN to nadzorowany algorytm klasyfikacji, który klasyfikuje nowe punkty danych na podstawie najbliższych punktów danych. Z drugiej strony, grupowanie K-średnich jest an   bez nadzoru   algorytm grupowania, który grupuje dane w liczbę K klastrów.

Jak działa KNN?

Jak wspomniano powyżej, algorytm KNN jest używany głównie jako klasyfikator. Przyjrzyjmy się, jak KNN klasyfikuje niewidoczne wejściowe punkty danych.

W przeciwieństwie do klasyfikacji przy użyciu sztucznych sieci neuronowych, klasyfikacja k-najbliższych sąsiadów jest łatwa do zrozumienia i prosta do wdrożenia. Jest to idealne rozwiązanie w sytuacjach, w których punkty danych są dobrze zdefiniowane lub nieliniowe.

Zasadniczo KNN przeprowadza mechanizm głosowania w celu określenia klasy niewidocznej obserwacji. Oznacza to, że klasa z większością głosów stanie się klasą danego punktu danych.

Jeśli wartość K jest równa jeden, do określenia klasy punktu danych użyjemy tylko najbliższego sąsiada. Jeśli wartość K jest równa dziesięć, użyjemy dziesięciu najbliższych sąsiadów i tak dalej.

Aby spojrzeć na to z innej perspektywy, rozważ niesklasyfikowany punkt danych X. Na wykresie punktowym znajduje się kilka punktów danych ze znanymi kategoriami A i B.

Załóżmy, że punkt danych X znajduje się w pobliżu grupy A.

Jak wiesz, klasyfikujemy punkt danych, patrząc na najbliższe punkty z adnotacjami. Jeśli wartość K jest równa jeden, użyjemy tylko jednego najbliższego sąsiada do określenia grupy punktu danych.

W tym przypadku punkt danych X należy do grupy A, ponieważ jego najbliższy sąsiad znajduje się w tej samej grupie. Jeśli grupa A ma więcej niż dziesięć punktów danych, a wartość K jest równa 10, to punkt danych X nadal będzie należeć do grupy A, ponieważ wszyscy jego najbliżsi sąsiedzi są w tej samej grupie.

Załóżmy, że inny niesklasyfikowany punkt danych Y znajduje się między grupą A a grupą B. Jeśli K jest równe 10, wybieramy grupę, która otrzyma najwięcej głosów, co oznacza, że ​​klasyfikujemy Y do grupy, w której ma najwięcej sąsiadów. Na przykład, jeśli Y ma siedmiu sąsiadów w grupie B i trzech sąsiadów w grupie A, należy do grupy B.

Fakt, że klasyfikator przypisuje kategorię z największą liczbą głosów, jest prawdą niezależnie od liczby obecnych kategorii.

Być może zastanawiasz się, jak obliczana jest metryka odległości w celu określenia, czy punkt danych jest sąsiadem, czy nie.

Istnieją cztery sposoby obliczania miary odległości między punktem danych a jego najbliższym sąsiadem: odległość euklidesowa , odległość Manhattan , odległość Hamminga i odległość Minkowskiego . Z tych trzech, odległość euklidesowa jest najczęściej używaną funkcją odległości lub metryką.

Aby zweryfikować dokładność klasyfikacji KNN, a   macierz zamieszania   jest używany. Do walidacji wykorzystywane są również inne metody statystyczne, takie jak test ilorazu wiarygodności.

W przypadku regresji KNN większość kroków jest taka sama. Zamiast przypisywać klasę z największą liczbą głosów, obliczana jest średnia wartości sąsiadów i przypisywana do nieznanego punktu danych.

Dlaczego warto korzystać z algorytmu KNN?

Klasyfikacja jest krytycznym problemem w nauce o danych i uczeniu maszynowym. KNN jest jednym z najstarszych, ale dokładnych algorytmów używanych do klasyfikacji wzorców i modeli regresji.

Oto niektóre obszary, w których można użyć algorytmu k-najbliższego sąsiada:

• Rating kredytowy: Algorytm KNN pomaga określić rating kredytowy osoby, porównując ją z osobami o podobnych cechach.
• Zatwierdzanie pożyczki: podobnie jak ocena kredytowa, algorytm k-najbliższego sąsiada jest korzystny w identyfikowaniu osób, które są bardziej narażone na niespłacanie pożyczek, porównując ich cechy z podobnymi osobami.
• Wstępne przetwarzanie danych: zestawy danych mogą zawierać wiele braków danych. Algorytm KNN jest używany w procesie zwanym imputacją brakujących danych , który szacuje brakujące wartości.
• Rozpoznawanie wzorców: Zdolność algorytmu KNN do identyfikacji wzorców tworzy szeroki zakres zastosowań. Na przykład pomaga wykrywać wzorce w korzystaniu z kart kredytowych i wykrywać nietypowe wzorce. Wykrywanie wzorców jest również przydatne w identyfikowaniu wzorców zachowań zakupowych klientów.
• Przewidywanie cen akcji: Ponieważ algorytm KNN ma talent do przewidywania wartości nieznanych podmiotów, jest przydatny w przewidywaniu przyszłej wartości akcji na podstawie danych historycznych.
• Systemy rekomendacji: Ponieważ KNN może pomóc w znalezieniu użytkowników o podobnych cechach, może być stosowany w systemach rekomendacji. Na przykład może być używany w internetowej platformie strumieniowego przesyłania wideo, aby sugerować treści, które użytkownik z większym prawdopodobieństwem obejrzy, analizując to, co oglądają podobni użytkownicy.
• Wizja komputerowa: Algorytm KNN służy do klasyfikacji obrazów. Ponieważ jest w stanie grupować podobne punkty danych, na przykład grupować koty i psy w innej klasie, jest przydatny w kilku   wizja komputerowa   Aplikacje.

Jak wybrać optymalną wartość K

Nie ma konkretnego sposobu określenia najlepszej wartości K – innymi słowy – liczby sąsiadów w KNN. Oznacza to, że być może będziesz musiał poeksperymentować z kilkoma wartościami, zanim zdecydujesz, z którą z nich pójść dalej.

Jednym ze sposobów na to jest rozważenie (lub udawanie), że część próbek uczących jest „nieznana”. Następnie możesz skategoryzować nieznane dane w zestawie testowym, używając algorytmu k-najbliższych sąsiadów i przeanalizować, jak dobra jest nowa kategoryzacja, porównując ją z informacjami, które już masz w danych uczących.

Kiedy mamy do czynienia z problemem dwuklasowym, lepiej wybrać nieparzystą wartość K. W przeciwnym razie może powstać scenariusz, w którym liczba sąsiadów w każdej klasie jest taka sama. Ponadto wartość K nie może być wielokrotnością liczby obecnych klas.

Innym sposobem wybrania optymalnej wartości K jest obliczenie sqrt(N), gdzie N oznacza liczbę próbek w zbiorze danych uczących.

Jednak K o niższych wartościach, takich jak K=1 lub K=2, może być zaszumione i narażone na działanie wartości odstających. W takich przypadkach szansa na overfitting również jest duża.

Z drugiej strony K z większymi wartościami w większości przypadków da początek gładszym granicom decyzyjnym, ale nie powinno być zbyt duże. W przeciwnym razie grupy z mniejszą liczbą punktów danych będą zawsze przegłosowane przez inne grupy. Dodatkowo, większe K będzie kosztowne obliczeniowo.

Zalety i wady KNN

Jedną z najważniejszych zalet korzystania z algorytmu KNN jest to, że nie ma potrzeby budowania modelu ani dostrajania kilku parametrów. Ponieważ jest to algorytm uczenia się leniwie, a nie chętny do nauki, nie ma potrzeby uczenia modelu; zamiast tego wszystkie punkty danych są używane w momencie przewidywania.

Oczywiście jest to obliczeniowo kosztowne i czasochłonne. Ale jeśli masz potrzebne zasoby obliczeniowe, możesz użyć KNN do rozwiązywania problemów z regresją i klasyfikacją. Istnieje jednak kilka szybszych algorytmów, które mogą generować dokładne prognozy.

Oczywiście KNN nie jest idealnym algorytmem uczenia maszynowego. Ponieważ predyktor KNN oblicza wszystko od podstaw, może nie być idealny dla dużych zbiorów danych.

KNN i przekleństwo wymiarowości

Gdy masz pod ręką ogromne ilości danych, wydobycie z nich szybkich i prostych informacji może być dość trudne. W tym celu możemy użyć algorytmów redukcji wymiarowości, które w istocie sprawiają, że dane „dostają się bezpośrednio do celu”.

Termin „przekleństwo wymiarowości” może sprawiać wrażenie, że pochodzi prosto z filmu science fiction. Ale oznacza to, że dane mają zbyt wiele funkcji.

Jeśli dane mają zbyt wiele funkcji, istnieje wysokie ryzyko nadmiernego dopasowania modelu, co prowadzi do niedokładnych modeli. Zbyt wiele wymiarów utrudnia również grupowanie danych, ponieważ każda próbka danych w zestawie danych będzie wyglądać tak samo od siebie.

Algorytm k-najbliższych sąsiadów jest bardzo podatny na overfitting z powodu przekleństwa wymiarowości. Jednak ten problem można rozwiązać za pomocą   implementacja brute force   algorytmu KNN. Ale nie jest to praktyczne w przypadku dużych zestawów danych.

KNN nie działa dobrze, jeśli jest zbyt wiele funkcji. W związku z tym techniki redukcji wymiarów, takie jak analiza głównych składowych (PCA) i wybór cech, muszą być wykonywane w fazie przygotowania danych.

KNN: leniwy algorytm, który zdobył serca

Pomimo tego, że jest najbardziej leniwy wśród algorytmów, KNN zbudował imponującą reputację i jest algorytmem do rozwiązywania kilku problemów z klasyfikacją i regresją. Oczywiście ze względu na swoje lenistwo może nie być najlepszym wyborem w przypadku dużych zbiorów danych. Ale jest to jeden z najstarszych, najprostszych i najdokładniejszych algorytmów.

Szkolenie i weryfikacja algorytmu z ograniczoną ilością danych może być zadaniem herkulesowym. Ale jest sposób, aby zrobić to skutecznie. Nazywa się to sprawdzaniem krzyżowym i polega na zarezerwowaniu części danych uczących jako zestawu danych testowych.