Najbliżsi sąsiedzi w danych wielowymiarowych?

I. Metryka Odległości

Po pierwsze, liczba cech (kolumn) w zbiorze danych nie jest czynnikiem przy wyborze metryki odległości do zastosowania w kNN. Istnieje sporo opublikowanych badań skierowanych właśnie na to pytanie, a zwykłe podstawy do porównania to: {]}

• Podstawowe Dane statystyczne dystrybucja danych;

• Związek między cechami które zawierają Twoje dane (czy są niezależne-czyli co robi KOWARIANCJA matrix look like); oraz

• Przestrzeń współrzędnych, z której twój dane zostały uzyskane.

Jeśli nie masz wcześniejszej wiedzy o dystrybucji (dystrybucjach), z których pobrano próbki danych, co najmniej jedno (dobrze udokumentowane i dokładne) badanie stwierdza, że odległość euklidesowa jest najlepszym wyborem.

Metryka YEuclidean używana w silnikach rekomendacji internetowych w skali mega, a także w bieżących badaniach naukowych. Odległości obliczane przez Euklidesa mają intuicyjne znaczenie i skale obliczeniowe-tzn. odległość euklidesowa jest obliczana w ten sam sposób, niezależnie od tego, czy dwa punkty są w dwóch wymiarach, czy w przestrzeni dwuwymiarowej.

Dla mnie zawiodło tylko kilka razy, każdy z tych przypadków odległość euklidesowa zawiodła, ponieważ podstawowy (kartezjański) układ współrzędnych był kiepskim wyborem. I zazwyczaj rozpoznasz to, ponieważ na przykład długości ścieżek (odległości) nie są już addytywne-np. gdy przestrzeń metryczna jest szachownicą, odległość jest lepsza niż euklidesowa, podobnie gdy przestrzenią metryczną jest ziemia, a twoje odległości są lotami transkontynentalnymi, dobrym pomysłem jest metryka odległości odpowiednia dla biegunowego układu współrzędnych (np. Londyn do Wiednia wynosi 2,5 godziny, Wiedeń do Petersburga wynosi kolejne 3 godziny, mniej więcej w tym samym kierunku, jednak Londyn do Petersburga Nie wynosi 5,5 godziny, zamiast tego jest nieco ponad 3 godziny.)

Ale oprócz tych przypadków, w których dane należą do współrzędnych nie kartezjańskich system, wybór metryki odległości zwykle nie jest materiałem. (Zobacz ten post na blogu od ucznia CS, porównując kilka metryk odległości, badając ich wpływ na klasyfikator kNN-kwadrat chi daje najlepsze wyniki, ale różnice nie są duże; bardziej kompleksowe badanie znajduje się w artykule akademickim, Comparative Study of Distance Functions for Nearest neighbours - Mahalanobis (zasadniczo euklidesowy znormalizowany przez uwzględnienie kowariancji wymiarów) był najlepszy w tym przypadku. ucz się.

Jeden ważny zapis: aby obliczenia metryczne odległości były znaczące, musisz re-scale Twoje dane-rzadko jest możliwe zbudowanie modelu kNN do generowania dokładnych prognoz bez tego. Na przykład, jeśli budujesz model kNN do przewidywania wyników sportowych, a zmiennymi oczekiwanymi są Wzrost( cm), Waga (kg), tłuszcz ( % ) i puls spoczynkowy (uderzenia na minutę), typowy punkt danych może wyglądać mniej więcej tak: [ 180.4, 66.1, 11.3, 71 ]. Oczywiście Obliczanie odległości będzie zdominowane przez wysokość, podczas gdy udział % tłuszczu ciała będzie prawie znikomy. Innymi słowy, jeśli zamiast tego dane były zgłaszane inaczej, tak że masa ciała była w gramach, a nie kilogramach, to pierwotna wartość 86,1, wynosiłaby 86,100, co miałoby duży wpływ na Twoje wyniki, co jest dokładnie tym, czego nie chcesz. Prawdopodobnie najczęstszą techniką skalowania jest odejmowanie średniej i dzielenie przez standard deviation (mean I sd odnoszą się oddzielnie do każdej kolumny lub funkcji w tym zbiorze danych; X odnosi się do pojedynczego wpisu/komórki w wierszu danych):

X_new = (X_old - mu) / sigma

II. Struktura danych

Jeśli martwisz się o wydajność struktury drzewa kd, Teselacja Woronoi jest koncepcyjnie prostym kontenerem, ale drastycznie poprawi wydajność i skaluje lepiej niż drzewa kd.

Używanie VT dla kNN działa tak:

Z Twoich danych, losowo wybierz punkty w--to są Twoje centra Voronoi. Komórka Woronoja obejmuje wszystkie sąsiednie punkty, które są najbliżej każdego centrum. Wyobraź sobie, że przypisujesz inny kolor do każdego z centrów Voronoi, tak aby każdy punkt przypisany do danego Centrum był pomalowany na ten kolor. Tak długo, jak masz wystarczającą gęstość, robi to ładnie pokazać granice każdego Centrum Voronoi (jak granica, która oddziela dwa kolory.

Jak wybrać Ośrodki Voronoi? Używam dwóch ortogonalnych wskazówek. Po losowym wybraniu punktów w, Oblicz VT dla danych treningowych. Następnie sprawdź liczbę punktów danych przypisanych do każdego Centrum Voronoi--wartości te powinny być mniej więcej takie same (biorąc pod uwagę jednolitą gęstość punktów w całej przestrzeni danych). W dwóch wymiarach spowodowałoby to powstanie VT z płytkami o tym samym rozmiarze.To pierwsza zasada, tu jest druga. Wybierz w przez iterację--run algorytm kNN z w jako parametrem zmiennej i zmierzyć wydajność (czas wymagany do powrotu prognozy poprzez zapytanie VT).

III. Obliczanie wyniku (przewidywana zmienna odpowiedzi)

Istnieją dwa kroki do obliczenia przewidywanej wartości z zestawu danych treningowych kNN. Pierwszy to N, czyli liczba najbliższych sąsiadów do użycia do tego obliczenia. Drugi to jak ważyć ich wkład do przewidywanej wartości.

W/r / T pierwszy składnik, można określić najlepszą wartość n rozwiązując problem optymalizacji (bardzo podobny do optymalizacji najmniejszych kwadratów). Taka jest teoria; w praktyce większość ludzi po prostu używa n = 3. W każdym razie łatwo jest uruchomić algorytm kNN na zestawach instancji testowych (aby obliczyć przewidywane wartości) dla n=1, n=2, n=3 itd. i wykreślić błąd jako funkcję n. Jeśli po prostu chcesz wiarygodną wartość dla n, aby zacząć, ponownie, po prostu użyj n = 3.

Drugim składnikiem jest sposób ważenia wkładu każdego z sąsiadów (zakładając, że n > 1).

Najprostsza technika ważenia polega na pomnożeniu każdego sąsiada przez współczynnik ważenia, który jest tylko 1/(dist * K), lub odwrotnością odległości od tego sąsiada do instancji testowej często pomnożonej przez jakąś empirycznie pochodną stałą, K. nie jestem fanem tej techniki, ponieważ jest to często nadmiernie obciąża najbliższych sąsiadów (a jednocześnie zaniża wagę tych bardziej odległych); znaczenie tego polega na tym, że dana prognoza może być niemal całkowicie zależna od pojedynczego sąsiada, co z kolei zwiększa wrażliwość algorytmu na szum.

Funkcja ważenia musi być lepsza, co znacznie unika tego ograniczenia jest funkcja Gaussa, co w Pythonie wygląda tak:

def weight_gauss(dist, sig=2.0) :
    return math.e**(-dist**2/(2*sig**2))

Aby obliczyć przewidywaną wartość za pomocą kod kNN, można zidentyfikować N najbliższych sąsiadów do punktu danych, którego zmienną odpowiedzi chcesz przewidzieć ('instancja testowa'), a następnie wywołać funkcję weight_gauss, raz dla każdego z n sąsiadów, przechodząc w odległości między każdym sąsiadem punkt testowy.Funkcja ta zwróci wagę dla każdego sąsiada, która jest następnie używana jako współczynnik tego sąsiada w obliczeniach średniej ważonej.

To, przed czym stoisz, jest znane jako przekleństwo wymiarowości. Czasami przydatne jest uruchomienie algorytmu takiego jak pca lub ICA, aby upewnić się, że naprawdę potrzebujesz wszystkich 21 wymiarów i ewentualnie znaleźć transformację liniową, która pozwoli Ci użyć mniej niż 21 Z w przybliżeniu taką samą jakością wyniku.

Aktualizacja: Spotkałem się z nimi w książce o nazwie Biomedical Signal Processing Rangayyan (mam nadzieję, że dobrze pamiętam). ICA nie jest trywialna technika, ale została opracowana przez naukowców w Finlandii i myślę, że kod Matlab dla niego jest publicznie dostępny do pobrania. PCA jest szeroko stosowaną techniką i uważam, że powinieneś być w stanie znaleźć jej implementację R lub innego oprogramowania. PCA jest wykonywana przez rozwiązywanie równań liniowych iteracyjnie. Zrobiłem to zbyt dawno temu, żeby pamiętać jak. = )

Chodzi o to, że rozbijasz swoje sygnały na niezależne eigenvektory (dyskretne eigenfunctions, naprawdę) i ich wartości własne, 21 w Twoim przypadku. Każda wartość własna pokazuje wysokość wkładu, jaki każda funkcja własna dostarcza do każdego z pomiarów. Jeśli wartość własna jest mała, możesz bardzo dokładnie reprezentować sygnały bez używania odpowiadającej im funkcji własnej, i w ten sposób pozbędziesz się wymiaru.

Aby odpowiedzieć na twoje pytania jeden po drugim:

• nie, odległość euklidesowa jest złą metryką w wysokiej przestrzeni wymiarowej. Zasadniczo w dużych wymiarach nie ma różnicy między najbliższym i najdalszym sąsiadem.
• wiele prac / badań jest tam w danych o wysokich wymiarach, ale większość rzeczy wymaga dużo matematycznej sofistyki.
• drzewo KD jest złe dla danych o dużych wymiarach ... avoid it by all means

Oto fajna Gazeta na początek we właściwym kierunku. "Kiedy w najbliższym sąsiedztwie?"by Beyer et all.

Pracuję z danymi tekstowymi o wymiarach 20K i wyższych. Jeśli potrzebujesz porady związanej z tekstem, może będę w stanie Ci pomóc.

Najlepsze odpowiedzi są dobre, ale stare, więc chciałbym dodać 2016 odpowiedź .

Jak już wspomniano, w wysokiej przestrzeni wymiarowej Klątwa wymiarowości czai się za rogiem, sprawiając, że tradycyjne podejścia, takie jak popularne drzewo k-d, są tak powolne, jak podejście brute force. W rezultacie, zwracamy nasze zainteresowanie Approximate Near Neighbor Search (ANNS) {7]}, które na korzyść pewnej dokładności przyspiesza proces. Dostajesz dobre przybliżenie dokładnego NN, z dobra propability.

Gorące tematy, które mogą być godne:

1. nowoczesne podejścia LSH, takie jak Razenshteyn 'S.
2. RKD forest : Las(s) randomizowanych drzew k-d (RKD), jak opisano w FLANN , lub w nowszym podejściu, w którym byłem częścią, KD-GeRaF.
3. LOPQ co oznacza lokalnie zoptymalizowaną kwantyzację produktów, jak opisano tutaj . Jest bardzo podobny do nowego Babenko+Lemptitsky ' s approach .

Możesz również sprawdzić moje istotne odpowiedzi:

1. dwa zbiory wysokich punktów wymiarowych: Znajdź najbliższego sąsiada w drugim zbiorze
2. porównanie czasu wykonywania zapytań najbliższych sąsiadów na różnych strukturach danych
3. implementacja PCL kd-tree niezwykle powolna

Podobieństwo cosinusa jest powszechnym sposobem porównywania wektorów dużych wymiarów. Zauważ, że ponieważ jest to podobieństwo, a nie odległość, chcesz je zmaksymalizować, a nie zminimalizować. Możesz również użyć specyficznego dla danej domeny sposobu porównywania danych, na przykład jeśli Twoje dane były sekwencjami DNA, możesz użyć podobieństwa sekwencji, które uwzględnia prawdopodobieństwo mutacji itp.

Liczba najbliższych sąsiadów do wykorzystania różni się w zależności od rodzaju danych, ilości szumów itp. Nie ma ogólne zasady, po prostu trzeba znaleźć to, co działa najlepiej dla konkretnych danych i problemu, próbując wszystkich wartości w zakresie. Ludzie mają intuicyjne zrozumienie, że im więcej jest Danych, tym mniej sąsiadów potrzebujesz. W hipotetycznej sytuacji, w której masz wszystkie możliwe DANE, wystarczy poszukać jednego najbliższego sąsiada do sklasyfikowania.

Metoda K najbliższego sąsiada jest znana jako kosztowna obliczeniowo. Jest to jeden z głównych powodów, dla których ludzie zwracają się do innych algorytmów jak maszyny wektorowe.

Wiele zależy od tego, dlaczego chcesz poznać najbliższych sąsiadów. Możesz przyjrzeć się algorytmowi mean shift http://en.wikipedia.org/wiki/Mean-shift jeśli naprawdę chcesz znaleźć tryby swojego zestawu danych.

KD-trees rzeczywiście nie będzie działać zbyt dobrze na danych o dużych wymiarach. Ponieważ etap przycinania już nie pomaga, ponieważ najbliższa krawędź - odchylenie o 1 wymiar - prawie zawsze będzie mniejsza niż pełnowymiarowe odchylenie do znanych najbliższych sąsiadów.

Ale co więcej, drzewa kd działają dobrze tylko z normami Lp z tego, co wiem, i istnieje efekt koncentracji odległości, który sprawia, że algorytmy oparte na odległości ulegają degradacji z rosnącą wymiarowością.

Do dalszych informacje, warto poczytać o przekleństwie wymiarowości i jej różnych wariantach (jest ich więcej niż jedna strona!)

Nie jestem przekonany, że jest wiele przydatnych do ślepego przybliżania euklidesowych najbliższych sąsiadów, np. za pomocą LSH lub losowych projekcji. W pierwszej kolejności może być konieczne użycie znacznie bardziej precyzyjnej funkcji odległości!

Idystancja jest prawdopodobnie najlepsza do dokładnego wyszukiwania knn w danych o dużych wymiarach. Można go zobaczyć jako przybliżoną tessalację Woronoja.

Drzewa KD działają dobrze dla 21 wymiarów, jeśli zrezygnujesz wcześniej, po przyjrzeniu się powiedzmy 5% wszystkich punktów. FLANN robi to (i inne speedupy) aby dopasować 128-dołkowe wektory SIFT. (Niestety Flann wykonuje tylko metrykę euklidesową, i szybko i solidnie scipy.przestrzenne.cKDTree czy tylko metryki Lp; mogą one, ale nie muszą być odpowiednie dla Twoich danych.) Jest tu oczywiście kompromis z szybkością i dokładnością.

(Jeśli możesz opisać swoje Ndata, NQuery, data Dystrybucja, to może pomóc ludziom wypróbować podobne dane.)

Dodano 26 kwietnia, czasy uruchamiania cKDTree z odcięciem na moim starym mac ppc, aby dać bardzo szorstki pomysł wykonalności:

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=1000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.1 % of the 1000000 points, 0.31 % of 188315 boxes; better 0.0042 0.014 0.1 %
3.5 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.253

kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=5000 eps=0 leafsize=10 clustype=uniformp
14 sec to build KDtree of 1000000 points
kdtree: 1000 queries looked at av 0.48 % of the 1000000 points, 1.1 % of 188315 boxes; better 0.0071 0.026 0.5 %
15 sec to query 1000 points
distances to 2 nearest: av 0.131  max 0.245

Możesz spróbować krzywej kolejności Z. To łatwe dla 3 wymiaru.

Myślę, że cosine na TF-idf z funkcji logicznych będzie działać dobrze dla większości problemów. To dlatego, że jego sprawdzona w czasie heurystyka używana w wielu wyszukiwarkach, takich jak Lucene. Odległość euklidesowa z mojego doświadczenia pokazuje złe wyniki dla jakichkolwiek danych tekstowych. Wybór różnych ciężarów i przykładów k można wykonać za pomocą danych treningowych i wyboru parametrów brute-force.

Doświadczyłem tego samego problemu i mogę powiedzieć, co następuje.

1. Odległość euklidesowa jest dobrą metryką odległości, jednak jest obliczeniowo droższa niż odległość i czasami daje nieco gorsze wyniki, dlatego wybrałbym później.

2. Wartość k można znaleźć empirycznie. Możesz wypróbować różne wartości i sprawdzić otrzymane krzywe ROC lub inne miary precyzji / przypomnienia, aby znaleźć wartość akceptowalna.

3. Zarówno odległości Euklidesowe, jak i Manhattańskie respektują nierówność trójkąta , więc można ich używać w drzewach metrycznych. Rzeczywiście, drzewa KD mają swoją wydajność poważnie obniżoną, gdy dane mają więcej niż 10 wymiarów(sam doświadczyłem tego problemu). Znalazłem VP-trees jako lepszą opcję.

Czy odległość euklidesowa jest dobrą metryką znajdowania najbliższych sąsiadów? Jeśli nie, to jakie mam opcje?

Sugerowałbym miękkie grupowanie podprzestrzeni , dość powszechne podejście w dzisiejszych czasach, gdzie wagi cech są obliczane, aby znaleźć najbardziej odpowiednie wymiary. Możesz użyć tych wag na przykład przy użyciu odległości euklidesowej. Zobacz przekleństwo wymiarowości dla typowych problemów, a także ten artykuł może cię jakoś oświecić:

A k-oznacza Typ algorytm klastrowania podprzestrzeni mieszanych liczb i categorical datasets