Scikit Learn - K-Nearest Neighbors (KNN)
Ten rozdział pomoże ci zrozumieć metody najbliższych sąsiadów w Sklearn.
Są dwa rodzaje metod uczenia się opartych na sąsiedztwie supervised i unsupervised. Uczenie się oparte na nadzorowanych sąsiadach może być wykorzystywane zarówno do klasyfikacji, jak i do problemów z predykcją regresji, ale jest używane głównie w przypadku problemów związanych z predykcją klasyfikacji w przemyśle.
Metody uczenia się oparte na sąsiadach nie mają wyspecjalizowanej fazy szkolenia i podczas klasyfikacji wykorzystuje wszystkie dane do szkolenia. Nie zakłada również niczego na temat danych bazowych. Z tego powodu są leniwi i nieparametryczni z natury.
Główną zasadą stojącą za metodami najbliższego sąsiada jest -
Aby znaleźć wstępnie zdefiniowaną liczbę próbek szkoleniowych w niewielkiej odległości od nowego punktu danych
Wytypuj etykietę na podstawie liczby próbek szkoleniowych.
W tym przypadku liczba próbek może być stałą zdefiniowaną przez użytkownika, jak w przypadku uczenia się sąsiada K-najbliższego sąsiada, lub może zmieniać się w zależności od lokalnej gęstości punktu, jak w przypadku uczenia się sąsiada na podstawie promienia.
moduł sklearn.neighbors
Scikit-Learn have sklearn.neighborsmoduł, który zapewnia funkcjonalność zarówno dla nienadzorowanych, jak i nadzorowanych metod uczenia się sąsiadów. Jako dane wejściowe klasy w tym module mogą obsługiwać tablice NumPy lubscipy.sparse matryce.
Rodzaje algorytmów
Poniżej przedstawiono różne typy algorytmów, które można wykorzystać w implementacji metod opartych na sąsiadach -
Brutalna siła
Brute-force obliczanie odległości między wszystkimi parami punktów w zbiorze danych zapewnia najbardziej naiwną implementację wyszukiwania sąsiadów. Matematycznie dla próbek N w wymiarach D skala podejścia brutalnej siły wynosi0[DN2]
W przypadku małych próbek danych algorytm ten może być bardzo przydatny, ale staje się niewykonalny wraz ze wzrostem liczby próbek. Wyszukiwanie sąsiadów metodą Brute force można włączyć, wpisując słowo kluczowealgorithm=’brute’.
Drzewo KD
Jedną z opartych na drzewach struktur danych, które zostały wynalezione w celu rozwiązania problemu nieefektywności obliczeniowej podejścia brute-force, jest struktura danych KD. Zasadniczo drzewo KD jest binarną strukturą drzewa nazywaną drzewem K-wymiarowym. Rekursywnie dzieli przestrzeń parametrów wzdłuż osi danych, dzieląc ją na zagnieżdżone regiony ortograficzne, w których punkty danych są wypełnione.
Zalety
Oto kilka zalet algorytmu drzewa KD -
Construction is fast - Ponieważ partycjonowanie odbywa się tylko wzdłuż osi danych, konstrukcja drzewa KD jest bardzo szybka.
Less distance computations- Ten algorytm wymaga mniej obliczeń odległości, aby określić najbliższego sąsiada punktu zapytania. Trwa to tylko[ ()] obliczenia odległości.
Niedogodności
Fast for only low-dimensional neighbor searches- Jest bardzo szybki w przypadku niskowymiarowych (D <20) wyszukiwań sąsiadów, ale w miarę wzrostu D staje się nieefektywny. Ponieważ partycjonowanie odbywa się tylko wzdłuż osi danych,
Wyszukiwanie sąsiadów w drzewie KD można włączyć, wpisując słowo kluczowe algorithm=’kd_tree’.
Drzewo kulkowe
Ponieważ wiemy, że drzewo KD jest nieefektywne w wyższych wymiarach, dlatego w celu rozwiązania tej nieefektywności drzewa KD opracowano strukturę danych drzewa Ball. Matematycznie, rekurencyjnie dzieli dane na węzły określone przez środek ciężkości C i promień r, w taki sposób, że każdy punkt w węźle leży w hiper-sferze określonej przez środek ciężkościC i promień r. Wykorzystuje nierówność trójkątów, podaną poniżej, co zmniejsza liczbę punktów kandydujących do wyszukiwania sąsiada
$$ \ arrowvert X + Y \ arrowvert \ leq \ arrowvert X \ arrowvert + \ arrowvert Y \ arrowvert $$Zalety
Oto kilka zalet algorytmu Ball Tree -
Efficient on highly structured data - Ponieważ drzewo kulowe dzieli dane na szereg zagnieżdżonych hipersfer, jest wydajne w przypadku wysoce ustrukturyzowanych danych.
Out-performs KD-tree - Drzewo kulowe przewyższa drzewo KD w dużych wymiarach, ponieważ ma sferyczną geometrię węzłów drzewa kul.
Niedogodności
Costly - Podział danych na szereg zagnieżdżonych hipersfer sprawia, że jego konstrukcja jest bardzo kosztowna.
Wyszukiwanie sąsiadów w drzewie piłek można włączyć, wpisując słowo kluczowe algorithm=’ball_tree’.
Wybieranie algorytmu dla najbliższych sąsiadów
Wybór optymalnego algorytmu dla danego zbioru danych zależy od następujących czynników -
Liczba próbek (N) i wymiarowość (D)
Są to najważniejsze czynniki, które należy wziąć pod uwagę przy wyborze algorytmu najbliższego sąsiada. To z powodów podanych poniżej -
Czas zapytania algorytmu Brute Force rośnie do O [DN].
Czas zapytania algorytmu drzewa Ball rośnie jako O [D log (N)].
Czas zapytania algorytmu drzewa KD zmienia się wraz z D w dziwny sposób, który jest bardzo trudny do scharakteryzowania. Gdy D <20, koszt wynosi O [D log (N)], a algorytm ten jest bardzo wydajny. Z drugiej strony jest nieefektywny w przypadku, gdy D> 20, ponieważ koszt wzrasta do prawie O [DN].
Struktura danych
Innym czynnikiem, który wpływa na wydajność tych algorytmów jest wewnętrzna wymiarowość danych lub rzadkość danych. Dzieje się tak, ponieważ może to mieć duży wpływ na czasy zapytań w algorytmach drzewa Ball i KD. Natomiast czas zapytania algorytmu Brute Force pozostaje niezmieniony przez strukturę danych. Generalnie algorytmy drzewa Ball i drzewa KD generują krótszy czas zapytań po wszczepieniu do rzadszych danych o mniejszej wewnętrznej wymiarowości.
Liczba sąsiadów (k)
Liczba sąsiadów (k) żądanych dla punktu zapytania wpływa na czas zapytania algorytmów drzewa Ball i drzewa KD. Ich czas zapytań staje się wolniejszy wraz ze wzrostem liczby sąsiadów (k). Podczas gdy czas zapytania Brute Force pozostanie niezmieniony przez wartość k.
Liczba punktów zapytania
Ponieważ wymagają one fazy konstrukcyjnej, zarówno algorytmy drzewa KD, jak i drzewa Ball będą skuteczne, jeśli istnieje duża liczba punktów zapytań. Z drugiej strony, jeśli istnieje mniejsza liczba punktów zapytania, algorytm Brute Force działa lepiej niż algorytmy drzewa KD i drzewa Ball.