Kernelised k Nearest Neighbor

12

Jestem nowy w jądrach i wpadłem w kłopoty podczas próby jądra kNN.

Czynności wstępne

Używam wielomianowego jądra:
K(x,y)=(1+x,y)d

Twój typowy euklidesowy kNN używa następującej miary odległości:
d(x,y)=||xy||

Niech f(x) mapa x do jakiejś wyższej wymiarowej przestrzeni cech. Następnie kwadrat powyższej metryki odległości w przestrzeni Hilberta można wyrazić przez iloczyn wewnętrzny: d2(f(x),f(y))=K(x,x)2K(x,y)+K(y,y)

Zauważ, że jeśli pozwolimy d=1 powyższe zdegeneruje się do standardowej odległości euklidesowej.


Pytanie

Główny problem, jaki mam, polega na tym, że nie widzę, w jaki sposób jądro kNN daje lepsze wyniki, co pokazano eksperymentalnie np. W tym dokumencie (ostrzeżenie, bezpośredni link pdf!).

Spirala
źródło

Odpowiedzi:

25

Twierdzenie Covera : Z grubsza powiedziane, mówi, że biorąc pod uwagę dowolny losowy zestaw punktów skończonych (z dowolnymi etykietami), to z dużym prawdopodobieństwem punkty te można uczynić liniowo oddzielnymi [1] poprzez odwzorowanie ich na wyższy wymiar [2].

Znaczenie: Świetnie, to twierdzenie mówi mi, że jeśli wezmę mój zestaw danych i zmapuję te punkty do wyższego wymiaru, wtedy mogę łatwo znaleźć liniowy klasyfikator. Jednak większość klasyfikatorów musi obliczyć pewne podobieństwo, takie jak iloczyn iloczynu, a to oznacza, że ​​złożoność czasowa algorytmu klasyfikacji jest proporcjonalna do wymiaru punktu danych. Zatem wyższy wymiar oznacza większą złożoność czasu (nie wspominając o złożoności przestrzeni do przechowywania tych dużych punktów wymiarowych).

Sztuczka jądra: Niech będzie oryginalnym wymiarem punktów danych, a będzie mapą, która odwzorowuje te punkty na przestrzeń o wymiarze . Teraz, jeżeli jest funkcją która odbywa wejścia i od pierwotnego miejsca i oblicza , wówczas mogę obliczyć iloczyn skalarny w przestrzeni o większych wymiarach, ale w złożoności zamiast .nfN(>>n)KxyK(x,y)=f(x),f(y)O(n)O(N)

Znaczenie: Jeśli więc algorytm klasyfikacji zależy tylko od iloczynu kropkowego i nie ma zależności od rzeczywistej mapy , mogę użyć sztuczki jądra, aby uruchomić algorytm w przestrzeni o dużych wymiarach bez prawie żadnych dodatkowych kosztów.f

Czy liniowa separowalność oznacza, że ​​punkty z tej samej klasy będą się zbliżać niż punkty z różnych klas? Nie, nie ma takiej gwarancji jako takiej. Rozdzielność liniowa tak naprawdę nie oznacza, że ​​punkt z tej samej klasy zbliżył się lub że punkty z dwóch różnych klas poszły jeszcze dalej.

Dlaczego więc miałoby działać kNN? Nie musi! Jeśli jednak tak się dzieje, dzieje się tak wyłącznie z powodu jądra.

Co to znaczy? Rozważ boolowski wektor funkcji . Gdy używasz jądra wielomianowego stopnia drugiego, wektor cech jest mapowany na wektorx=(x1,x2)x(x12,2x1x2,x22). Z wektora cech boolowskich, po prostu stosując wielomian stopnia drugiego, otrzymaliśmy wektor cech „koniunkcji”. Zatem same jądra wytwarzają genialne mapy funkcji. Jeśli Twoje dane mają dobre oryginalne funkcje i jeśli Twoje dane mogłyby skorzystać z map funkcji utworzonych przez te jądra. Przez korzyść rozumiem, że funkcje wytworzone przez te mapy funkcji mogą zbliżyć punkty z tej samej klasy do siebie i odepchnąć punkty z różnych klas, a następnie kNN może skorzystać z jądra. W przeciwnym razie wyniki nie będą się różnić od wyników uzyskanych po uruchomieniu kNN na oryginalnych danych.

Więc po co używać jądra kNN? Pokazaliśmy, że złożoność obliczeniowa korzystania z jądra jest tylko nieco większa niż zwykłego kNN, a jeśli dane korzystają z używania jąder, dlaczego ich nie użyć?

Czy jest jakaś praca, która badała, która klasa danych może korzystać z jąder w kNN? O ile mi wiadomo, nie.

[1] http://en.wikipedia.org/wiki/Linear_separability
[2] http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4038449&tag=1

TenaliRaman
źródło