k - algorytm najbliższych sąsiadów - k-nearest neighbors algorithm

W statystykach The k algorytm -nearest sąsiadów ( k -NN ) jest nieparametryczny klasyfikacja metoda opracowana przez Evelyn Fix i Joseph Hodges w 1951 roku, a później rozszerzona przez Thomasa pokrowiec . Służy do klasyfikacji i regresji . W obu przypadkach dane wejściowe składają się z k najbliższych przykładów uczących w zbiorze danych . Wynik zależy od tego, czy k -NN jest używane do klasyfikacji czy regresji:

• W klasyfikacji k-NN wynikiem jest przynależność do klasy. Obiekt jest klasyfikowany przez głosowanie wielu jego sąsiadów, przy czym obiekt jest przypisywany do klasy najczęściej wśród jego k najbliższych sąsiadów ( k jest dodatnią liczbą całkowitą , zwykle małą). Jeśli k  = 1, to obiekt jest po prostu przypisywany do klasy tego pojedynczego najbliższego sąsiada.

• W regresji k-NN wynikiem jest wartość właściwości obiektu. Wartość ta jest średnią wartości k najbliższych sąsiadów.

k -NN to rodzaj klasyfikacji, w której funkcja jest tylko aproksymowana lokalnie, a wszystkie obliczenia są odraczane do czasu oceny funkcji. Ponieważ ten algorytm opiera się na odległości do klasyfikacji, jeśli cechy reprezentują różne jednostki fizyczne lub występują w bardzo różnych skalach, normalizacja danych treningowych może znacznie poprawić ich dokładność.

Zarówno w przypadku klasyfikacji, jak i regresji, użyteczną techniką może być przypisanie wag do wkładów sąsiadów, tak aby bliżsi sąsiedzi mieli większy udział w średniej niż bardziej odlegli. Na przykład, powszechny schemat ważenia polega na przypisaniu każdemu sąsiadowi wagi 1/ d , gdzie d jest odległością od sąsiada.

Sąsiedzi są pobierani ze zbioru obiektów, dla których znana jest klasa (dla klasyfikacji k -NN) lub wartość właściwości obiektu (dla regresji k -NN). Można to traktować jako zbiór uczący dla algorytmu, chociaż nie jest wymagany jawny krok uczący.

Osobliwością algorytmu k- NN jest wrażliwość na lokalną strukturę danych.

Ustawienie statystyczne

Załóżmy, że mamy pary przyjmujące wartości w , gdzie Y jest etykietą klasy X , tak że dla (i rozkładów prawdopodobieństwa ). Biorąc pod uwagę pewną normę na a punktem , niech będzie zmiana kolejności danych treningowych takie, że . ${\ Displaystyle (X_ {1}, Y_ {1}), (X_ {2}, Y _ {2}), \ kropki, (X_ {n}, Y_ {n})}$${\ Displaystyle \ mathbb {R} ^ {d} \ razy \ {1,2 \}}$${\ Displaystyle X | Y = r \ sim P_ {r}}$${\displaystyle r=1,2}$${\displaystyle P_{r}}$${\displaystyle \|\cdot \|}$${\ Displaystyle \ mathbb {R} ^ {d}}$${\ Displaystyle x \ w \ mathbb {R} ^ {d}}$${\ Displaystyle (X_ {(1)}, Y_ {(1)}), \ kropki, (X_ {(n)}, Y_ {(n)})}$${\ Displaystyle \ | X_ {(1)} -x \ | \ leq \ kropki \ leq \ | X_ {(n)} -x \ |}$

Algorytm

Przykład klasyfikacji k- NN. Próbka testowa (zielona kropka) powinna być zaklasyfikowana do niebieskich kwadratów lub czerwonych trójkątów. Jeśli k = 3 (koło z linii ciągłej) jest przypisywane do czerwonych trójkątów, ponieważ w wewnętrznym okręgu są 2 trójkąty i tylko 1 kwadrat. Jeśli k = 5 (przerywana linia koło) jest przypisywane do niebieskich kwadratów (3 kwadraty vs. 2 trójkąty wewnątrz zewnętrznego koła).

Przykładami uczącymi są wektory w wielowymiarowej przestrzeni cech, każdy z etykietą klasy. Faza uczenia algorytmu polega jedynie na przechowywaniu wektorów cech i etykiet klas próbek uczących.

W fazie klasyfikacji k jest stałą zdefiniowaną przez użytkownika, a nieoznakowany wektor (zapytanie lub punkt testowy) jest klasyfikowany przez przypisanie etykiety, która jest najczęstsza wśród k próbek uczących najbliższych temu punktowi zapytania.

Powszechnie używaną metryką odległości dla zmiennych ciągłych jest odległość euklidesowa . W przypadku zmiennych dyskretnych, takich jak klasyfikacja tekstu, można użyć innej metryki, takiej jak metryka nakładania się (lub odległość Hamminga ). W kontekście danych z mikromacierzy ekspresji genów, na przykład, jako metrykę zastosowano k- NN ze współczynnikami korelacji, takimi jak Pearsona i Spearmana. Często dokładność klasyfikacji k -NN można znacznie poprawić, jeśli metryka odległości jest wyuczona za pomocą wyspecjalizowanych algorytmów, takich jak analiza dużego marginesu najbliższego sąsiedztwa lub składowych sąsiedztwa .

Wada podstawowej klasyfikacji „głosowania większością” występuje, gdy rozkład klas jest skośny. Oznacza to, że w przewidywaniach nowego przykładu przeważają przykłady częstszej klasy, ponieważ są one powszechne wśród k najbliższych sąsiadów ze względu na ich dużą liczbę. Jednym ze sposobów przezwyciężenia tego problemu jest ważenie klasyfikacji, biorąc pod uwagę odległość od punktu testowego do każdego z jego k najbliższych sąsiadów. Klasa (lub wartość w problemach regresji) każdego z k najbliższych punktów jest mnożona przez wagę proporcjonalną do odwrotności odległości od tego punktu do punktu testowego. Innym sposobem na pokonanie pochylenia jest abstrakcja w reprezentacji danych. Na przykład na mapie samoorganizującej się (SOM) każdy węzeł jest reprezentantem (centrum) skupiska podobnych punktów, niezależnie od ich gęstości w oryginalnych danych uczących. K- NN można następnie zastosować do SOM.

Wybór parametrów

Najlepszy wybór k zależy od danych; generalnie większe wartości k zmniejszają wpływ szumu na klasyfikację, ale sprawiają, że granice między klasami są mniej wyraźne. Dobre k można wybrać za pomocą różnych technik heurystycznych (patrz optymalizacja hiperparametrów ). Specjalny przypadek, w którym przewiduje się, że klasa będzie klasą najbliższej próbki treningowej (tj. gdy k = 1) jest nazywany algorytmem najbliższego sąsiada.

Dokładność algorytmu k- NN może zostać poważnie obniżona przez obecność zaszumionych lub nieistotnych cech lub jeśli skale cech nie są zgodne z ich znaczeniem. Wiele wysiłku włożono w wybór lub skalowanie funkcji w celu poprawy klasyfikacji. Szczególnie popularnym podejściem jest wykorzystanie algorytmów ewolucyjnych do optymalizacji skalowania cech. Innym popularnym podejściem jest skalowanie cech poprzez wzajemne informowanie danych treningowych z klasami treningowymi.

W binarnych (dwuklasowych) problemach klasyfikacji pomocne jest wybranie k jako liczby nieparzystej, ponieważ pozwala to uniknąć remisowej liczby głosów. Jednym z popularnych sposobów wyboru empirycznie optymalnego k w tym ustawieniu jest metoda ładowania początkowego.

Klasyfikator 1 -najbliższego sąsiada

Najbardziej intuicyjnym klasyfikatorem typu najbliższego sąsiada jest ten klasyfikator najbliższego sąsiada, który przypisuje punkt x do klasy swojego najbliższego sąsiada w przestrzeni cech, czyli . ${\ Displaystyle C_ {n} ^ {1nn} (x) = Y_ {(1)}}$

Gdy rozmiar zbioru danych uczących zbliża się do nieskończoności, klasyfikator jednego najbliższego sąsiada gwarantuje współczynnik błędu nie gorszy niż dwukrotność współczynnika błędu Bayesa (minimalny osiągalny współczynnik błędu przy rozkładzie danych).

Ważony klasyfikator najbliższego sąsiada

Klasyfikator k- najbliższych sąsiadów może być postrzegany jako przypisujący k najbliższym sąsiadom wagę, a wszystkim pozostałym wagę 0 . Można to uogólnić na ważone klasyfikatory najbliższych sąsiadów. Oznacza to, że i- ty najbliższy sąsiad ma przypisaną wagę , z . Analogiczny wynik dotyczący silnej spójności ważonych klasyfikatorów najbliższych sąsiadów również jest aktualny. ${\displaystyle 1/k}$${\displaystyle w_{ni}}$${\ Displaystyle \ suma _ {i = 1} ^ {n} w_ {ni} = 1}$

Niech oznaczają ważonej najbliższym klasyfikator z ciężarkami . Z zastrzeżeniem warunków regularności na rozkładach klas, nadmierne ryzyko ma następującą asymptotyczną ekspansję: ${\ Displaystyle C_ {n} ^ {wnn}}$${\ Displaystyle \ {w_ {ni} \} _ {i = 1} ^ {n}}$

${\ Displaystyle {\ mathcal {R}} _ {\ mathcal {R}} (C_ {n} ^ {wnn}) - {\ mathcal {R}} _ {\ mathcal {R}} (C ^ {Bayes} )=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},}$

dla stałych i gdzie i . ${\displaystyle B_{1}}$${\displaystyle B_{2}}$${\ Displaystyle s_ {n} ^ {2} = \ suma _ {i = 1} ^ {n} w_ {ni} ^ {2}}$${\ Displaystyle t_ {n} = n ^ {-2 / d} \ suma _ {i = 1} ^ {n} w_ {ni} \ {i ^ {1 + 2 / d} - (i-1) ^ {1+2/d}\}}$

Optymalny schemat ważenia równoważący oba wyrazy na powyższym wyświetlaczu przedstawia się następująco: set , ${\ Displaystyle \ {w_ {ni} ^ {*} \} _ {i = 1} ^ {n}}$${\ Displaystyle k ^ {*} = \ l piętro Bn ^ {\ Frac {4} {d + 4}} \ r piętro}$

${\ Displaystyle w_ {ni} ^ {*} = {\ Frac {1} {k ^ {*}}} \ lewo [1 + {\ Frac {d} {2}} - {\ Frac {d} {2 {k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]}$dla i${\ Displaystyle i = 1,2, \ kropki, k ^ {*}}$

${\ Displaystyle w_ {ni} ^ {*} = 0}$dla .${\ Displaystyle i = k ^ {*} + 1 \ kropki, n}$

Przy optymalnych wagach dominującym terminem w asymptotycznej ekspansji nadmiernego ryzyka jest . Podobne wyniki są prawdziwe w przypadku korzystania z workowanego klasyfikatora najbliższego sąsiada . ${\ Displaystyle {\ mathcal {O}} (n ^ {- {\ Frac {4} {d + 4}}})}$

Nieruchomości

k -NN jest szczególnym przypadkiem estymatora „balonowego” o zmiennej przepustowości i gęstości jądra z jednolitym jądrem .

Naiwna wersja algorytmu jest łatwa do zaimplementowania poprzez obliczenie odległości od przykładu testowego do wszystkich przechowywanych przykładów, ale jest intensywna obliczeniowo dla dużych zbiorów uczących. Użycie przybliżonego algorytmu wyszukiwania najbliższego sąsiada sprawia, że k- NN jest możliwe do wykonania obliczeniowego nawet dla dużych zbiorów danych. Na przestrzeni lat zaproponowano wiele algorytmów wyszukiwania najbliższych sąsiadów; zazwyczaj mają one na celu zmniejszenie liczby faktycznie wykonywanych ocen odległości.

k- NN ma pewne silne wyniki konsystencji . Gdy ilość danych zbliża się do nieskończoności, dwuklasowy algorytm k- NN gwarantuje, że stopa błędu nie będzie gorsza niż dwukrotność stopy błędu Bayesa (minimalna osiągalna stopa błędu przy rozkładzie danych). Różne ulepszenia prędkości k- NN są możliwe dzięki wykorzystaniu wykresów zbliżeniowych.

Dla wieloklasowej klasyfikacji k- NN Cover i Hart (1967) udowadniają, że górny limit błędu wynosi

${\ Displaystyle R ^ {*} \ \ leq \ R_ {k \ operatorname {NN}} \ \ leq \ R ^ {*} \ lewo (2-{\ Frac {MR ^ {*}} {M-1} }\Prawidłowy)}$

gdzie jest stopą błędów Bayesa (która jest minimalną możliwą stopą błędów), jest stopą błędów k- NN, a M jest liczbą klas w zadaniu. W przypadku, gdy poziom błędu bayesowskiego zbliża się do zera, limit ten zmniejsza się do „nie więcej niż dwukrotności poziomu błędu bayesowskiego”. ${\ Displaystyle R ^ {*}}$${\ Displaystyle R_ {kNN}}$${\ Displaystyle M = 2}$${\ Displaystyle R ^ {*}}$

Wskaźniki błędów

Istnieje wiele wyników dotyczących wskaźnika błędów k klasyfikatorów najbliższych sąsiadów. Klasyfikator k -najbliższego sąsiada jest silnie (to znaczy dla dowolnego wspólnego rozkładu na ) spójny, pod warunkiem, że rozbieżny i zbieżny do zera jako . ${\ Displaystyle (X, Y)}$${\ Displaystyle k: = k_ {n}}$${\displaystyle k_{n}/n}$${\displaystyle n\do \infty}$

Pozwolić oznaczają k najbliższy sąsiad klasyfikatora opartego na zbiorze treningowym rozmiarze n . W pewnych warunkach regularności nadmierne ryzyko prowadzi do następującej asymptotycznej ekspansji: ${\ Displaystyle C_ {n} ^ {knn}}$

${\ Displaystyle {\ mathcal {R}} _ {\ mathcal {R}} (C_ {n} ^ {knn}) - {\ mathcal {R}} _ {\ mathcal {R}} (C ^ {Bayes} )=\left\{B_{1}{\frac {1}{k}}+B_{2}\left({\frac {k}{n}}\right)^{4/d}\right\ }\{1+o(1)\},}$

dla niektórych stałych i . ${\displaystyle B_{1}}$${\displaystyle B_{2}}$

Wybór oferuje kompromis między dwoma terminami na powyższym ekranie, dla których błąd -najbliższego sąsiada zbiega się z błędem Bayesa w optymalnym ( minimaksowym ) tempie . ${\ Displaystyle k ^ {*} = \ l piętro Bn ^ {\ Frac {4} {d + 4}} \ r piętro}$${\ Displaystyle k ^ {*}}$${\ Displaystyle {\ mathcal {O}} (n ^ {- {\ Frac {4} {d + 4}}})}$

Nauka metryczna

Wydajność klasyfikacji K-najbliższego sąsiada można często znacznie poprawić dzięki ( nadzorowanemu ) uczeniu metryk. Popularne algorytmy to analiza składowych sąsiedztwa i duża marża najbliższego sąsiada . Nadzorowane algorytmy uczenia metryki wykorzystują informacje o etykiecie do uczenia się nowej metryki lub pseudometryki .

Ekstrakcja funkcji

Gdy dane wejściowe do algorytmu są zbyt duże, aby można je było przetworzyć i podejrzewa się, że są zbędne (np. ten sam pomiar w stopach i metrach), dane wejściowe zostaną przekształcone w zredukowany zbiór cech (nazywany również wektorem cech ). Przekształcenie danych wejściowych w zestaw cech nazywa się ekstrakcją cech . Jeśli wyodrębnione cechy zostaną starannie wybrane, oczekuje się, że zestaw cech wydobędzie odpowiednie informacje z danych wejściowych w celu wykonania pożądanego zadania przy użyciu tej zredukowanej reprezentacji zamiast danych wejściowych o pełnym rozmiarze. Ekstrakcja cech jest wykonywana na surowych danych przed zastosowaniem algorytmu k- NN na przekształconych danych w przestrzeni cech .

Przykład typowego potoku obliczeniowego wizji komputerowej do rozpoznawania twarzy przy użyciu k- NN, w tym etapów wstępnego przetwarzania cech i redukcji wymiarów (zwykle realizowanych za pomocą OpenCV ):

1. Haar Wykrywanie twarzy
2. Analiza śledzenia zmiany średniej
3. Projekcja PCA lub Fisher LDA w przestrzeń cech, a następnie klasyfikacja k- NN

Redukcja wymiarów

W przypadku danych wielowymiarowych (np. o liczbie wymiarów większej niż 10) redukcja wymiaru jest zwykle przeprowadzana przed zastosowaniem algorytmu k- NN w celu uniknięcia skutków przekleństwa wymiarowości .

Przekleństwo wymiarowości w k kontekście -NN zasadzie oznacza, że odległość euklidesowa jest nieprzydatny w dużych wymiarach, ponieważ wszystkie wektory są niemal równej odległości do wektora zapytań wyszukiwania (wyobrazić wiele punktów leży mniej więcej na okręgu o punkcie zapytania w środku; odległość od zapytania do wszystkich punktów danych w przestrzeni wyszukiwania jest prawie taka sama).

Wyodrębniania cech oraz zmniejszenie wymiarów mogą być połączone w jednym etapie stosując analizę głównych składowych (PCA), liniowa analiza dyskryminacyjna (LDA) lub kanoniczna analiza korelacji (CCA) techniki jako etap obróbki wstępnej, następuje grupowanie o k -nn w funkcji wektory w przestrzeni o zredukowanych wymiarach. Proces ten nazywany jest również osadzaniem niskowymiarowym .

W przypadku bardzo wysokowymiarowych zestawów danych (np. podczas wyszukiwania podobieństwa w strumieniach wideo na żywo, danych DNA lub wielowymiarowych szeregach czasowych ) uruchomienie szybkiego wyszukiwania przybliżonego k- NN przy użyciu mieszania zależnego od lokalizacji , „losowych projekcji”, „szkiców” lub inne wysokowymiarowe techniki wyszukiwania podobieństwa z zestawu narzędzi VLDB mogą być jedyną możliwą opcją.

Granica decyzji

W efekcie reguły najbliższego sąsiada niejawnie obliczają granicę decyzji . Możliwe jest również jawne obliczenie granicy decyzyjnej i zrobienie tego wydajnie, tak aby złożoność obliczeniowa była funkcją złożoności granicy.

Redukcja danych

Redukcja danych to jeden z najważniejszych problemów w pracy z ogromnymi zbiorami danych. Zwykle do dokładnej klasyfikacji potrzebne są tylko niektóre punkty danych. Dane te nazywane są prototypami i można je znaleźć w następujący sposób:

1. Wybierz klasy odstające , czyli dane treningowe, które są niepoprawnie sklasyfikowane przez k -NN (dla danego k )
2. Rozdziel pozostałe dane na dwa zestawy: (i) prototypy, które są używane do decyzji o klasyfikacji oraz (ii) zaabsorbowane punkty, które mogą być poprawnie sklasyfikowane przez k- NN przy użyciu prototypów. Pochłonięte punkty można następnie usunąć z zestawu treningowego.

Wybór klas odstających

Przykład szkolenia otoczony przykładami innych klas nazywa się wartością odstającą klasy. Przyczyny wartości odstających klas obejmują:

• błąd losowy
• niewystarczające przykłady treningowe tej klasy (pojawia się odosobniony przykład zamiast klastra)
• brak ważnych cech (klasy są rozdzielone w innych wymiarach, których nie znamy)
• zbyt wiele przykładów treningowych innych klas (klasy niezrównoważone), które tworzą „wrogie” tło dla danej małej klasy

Wartości odstające klasy z k- NN wytwarzają szum. Można je wykryć i oddzielić do przyszłej analizy. Biorąc pod uwagę dwie liczby naturalne, k>r>0 , przykład uczący nazywany jest klasą odstającą (k,r) NN, jeśli k najbliższych sąsiadów zawiera więcej niż r przykładów innych klas.

Condensed Nearest Neighbor w celu redukcji danych

Skondensowany najbliższy sąsiad (CNN, algorytm Harta ) to algorytm zaprojektowany w celu zmniejszenia zbioru danych do klasyfikacji k- NN. Wybiera zestaw prototypów U z danych uczących tak, że 1NN z U może klasyfikować przykłady prawie tak dokładnie, jak robi to 1NN z całym zestawem danych.

Obliczanie współczynnika granicznego.

Trzy rodzaje punktów: prototypy, klasy odstające i punkty zaabsorbowane.

Mając zestaw uczący X , CNN działa iteracyjnie:

1. Zeskanuj wszystkie elementy X , szukając elementu x , którego najbliższy prototyp z U ma inną etykietę niż x .
2. Usuń x z X i dodaj go do U
3. Powtarzaj skanowanie, aż nie zostaną dodane żadne więcej prototypów do U .

Użyj U zamiast X do klasyfikacji. Przykłady, które nie są prototypami, nazywane są punktami „wchłoniętymi”.

Efektywne jest skanowanie przykładów uczących w kolejności malejącego wskaźnika granicznego. Współczynnik graniczny przykładu uczącego x jest zdefiniowany jako

a ( x ) = | | x'-y | |/| | xy | |

gdzie | | xy | | jest odległością do najbliższego przykładu y o innym kolorze niż x , a | | x'-y | | jest odległością od y do najbliższego przykładu x' z taką samą etykietą jak x .

Współczynnik graniczny jest w przedziale [0,1], ponieważ | | x'-y | | nigdy nie przekracza | | xy | | . Ta kolejność daje pierwszeństwo granicom klas do włączenia do zbioru prototypów U . Punkt o innej etykiecie niż x jest nazywany zewnętrznym względem x . Obliczenie współczynnika granicznego ilustruje rysunek po prawej stronie. Punkty danych są oznaczone kolorami: początkowym punktem jest x, a jego etykieta jest czerwona. Punkty zewnętrzne są niebieskie i zielone. Najbliższy x punkt zewnętrzny to y . Najbliższy y czerwony punkt to x' . Stosunek graniczny a ( x ) = | | x'-y | | / | | xy | | jest atrybutem początkowego punktu x .

Poniżej znajduje się ilustracja CNN w serii rycin. Istnieją trzy klasy (czerwona, zielona i niebieska). Rys. 1: początkowo w każdej klasie jest 60 punktów. Rys. 2 przedstawia mapę klasyfikacji 1NN: każdy piksel jest klasyfikowany przez 1NN przy użyciu wszystkich danych. Rys. 3 przedstawia mapę klasyfikacji 5NN. Białe obszary odpowiadają niesklasyfikowanym regionom, w których głosowanie 5NN jest remisowe (na przykład, jeśli są dwa zielone, dwa czerwone i jeden niebieski wśród 5 najbliższych sąsiadów). Rys. 4 przedstawia zredukowany zestaw danych. Krzyżyki są klasami odstającymi wybranymi przez regułę (3,2)NN (wszyscy trzej najbliżsi sąsiedzi tych instancji należą do innych klas); kwadraty są prototypami, a puste kółka są punktami zaabsorbowanymi. Lewy dolny róg pokazuje numery klas odstających, prototypów i zaabsorbowanych punktów dla wszystkich trzech klas. W tym przykładzie liczba prototypów waha się od 15% do 20% dla różnych klas. Z rys. 5 wynika, że ​​mapa klasyfikacji 1NN z prototypami jest bardzo podobna do tej z początkowym zbiorem danych. Figurki zostały wyprodukowane przy użyciu apletu Mirkes.

• Redukcja modelu CNN dla klasyfikatorów k-NN
• 

  Rys. 1. Zbiór danych.

• 

  Rys. 2. Mapa klasyfikacji 1NN.

• 

  Rys. 3. Mapa klasyfikacji 5NN.

• 

  Rys. 4. Zredukowany zbiór danych CNN.

• 

  Rys. 5. Mapa klasyfikacji 1NN na podstawie wyekstrahowanych prototypów CNN.

k -NN regresja

W k -NN metodą regresji k algorytm -NN jest wykorzystywana do oszacowania zmiennych ciągłych. Jeden z takich algorytmów wykorzystuje średnią ważoną k najbliższych sąsiadów, ważoną przez odwrotność ich odległości. Ten algorytm działa w następujący sposób:

1. Oblicz odległość euklidesową lub Mahalanobisa od przykładu zapytania do przykładów oznaczonych etykietą.
2. Uporządkuj oznakowane przykłady, zwiększając odległość.
3. Znajdź heurystycznie optymalną liczbę k najbliższych sąsiadów na podstawie RMSE . Odbywa się to za pomocą weryfikacji krzyżowej.
4. Oblicz odwrotną średnią ważoną odległości z k -najbliższymi wielowymiarowymi sąsiadami.

k -NN wartość odstająca

Odległość do k- tego najbliższego sąsiada może być również postrzegana jako oszacowanie gęstości lokalnej, a zatem jest również popularnym wynikiem odstającym w wykrywaniu anomalii . Im większa odległość do k -NN, tym mniejsza gęstość lokalna, tym bardziej prawdopodobne, że punkt zapytania jest wartością odstającą. Chociaż dość prosty, ten model wartości odstających, wraz z inną klasyczną metodą eksploracji danych, lokalnym czynnikiem odstającym , działa całkiem dobrze również w porównaniu z nowszymi i bardziej złożonymi podejściami, zgodnie z wielkoskalową analizą eksperymentalną.

Walidacja wyników

Matryca zamieszanie lub „matryca dopasowanie” jest często używany jako narzędzie do sprawdzania poprawności k -NN klasyfikacji. Można również zastosować bardziej niezawodne metody statystyczne, takie jak test ilorazu wiarygodności .

Zobacz też

• Najbliższy klasyfikator centroid
• Problem z najbliższą parą punktów

Bibliografia

Dalsza lektura

• Dasarathy, Belur V. , wyd. (1991). Normy najbliższego sąsiada (NN): Techniki klasyfikacji wzorców NN . Numer ISBN 978-0-8186-8930-7.
• Szachnarowicz, Grzegorz; Darrella, Trevora; Indyk, Piotr, wyd. (2005). Metody najbliższego sąsiada w nauce i wizji . MIT Naciśnij . Numer ISBN 978-0-262-19547-8.