Najbliżsi sąsiedzi w danych wielowymiarowych?

Ja zapytałem pytanie kilka dni wstecz, jak znaleźć najbliższych sąsiadów dla danego wektora. Mój wektor ma teraz 21 wymiarów i zanim przejdę dalej, ponieważ nie jestem z dziedziny uczenia maszynowego ani matematyki, zaczynam zadawać sobie kilka podstawowych pytań:

• Czy odległość euklidesowa jest dobrym wskaźnikiem do znajdowania najbliższych sąsiadów w pierwszej kolejności? Jeśli nie, jakie mam możliwości?
• W dodatku, jak należy podjąć decyzję o właściwym progu do określenia k-sąsiadów? Czy jest jakaś analiza, którą można przeprowadzić, aby obliczyć tę wartość?
• Wcześniej sugerowano mi użycie kd-Trees, ale strona Wikipedii wyraźnie mówi, że dla wysokich wymiarów kd-Tree jest prawie równoważne przeszukiwaniu siłą. W takim przypadku, jaki jest najlepszy sposób na efektywne znajdowanie najbliższych sąsiadów w zbiorze danych o milionie punktów?

Czy ktoś mógłby wyjaśnić niektóre (lub wszystkie) z powyższych pytań?

Obecnie zajmuję się takimi zagadnieniami - klasyfikacja, wyszukiwanie najbliższych sąsiadów - wyszukiwanie informacji muzycznych.

Możesz być zainteresowany algorytmami przybliżonego najbliższego sąsiada ( ANN ). Chodzi o to, że pozwalasz algorytmowi powrócić wystarczająco blisko sąsiadów (być może nie najbliższego sąsiada); w ten sposób zmniejszasz złożoność. Wspomniałeś o drzewie kd ; to jest jeden przykład. Ale jak powiedziałeś, kd-tree działa słabo w dużych wymiarach. W rzeczywistości wszystkie obecne techniki indeksowania (oparte na partycjonowaniu przestrzeni) degradują się do wyszukiwania liniowego dla wystarczająco wysokich wymiarów [1] [2] [3].

Wśród zaproponowanych ostatnio algorytmów ANN , być może najbardziej popularnym jest metoda mieszania zależnego od lokalizacji (ang. Locality-Sensitive Hashing - LSH ), która odwzorowuje zbiór punktów w wielowymiarowej przestrzeni na zbiór koszy, tj. Tablicę mieszającą [1] [3]. Ale w przeciwieństwie do tradycyjnych skrótów , mieszanie zależne od lokalizacji umieszcza pobliskie punkty w tym samym koszu.

LSH ma ogromne zalety. Po pierwsze, jest to proste. Po prostu obliczasz skrót dla wszystkich punktów w swojej bazie danych, a następnie tworzysz z nich tabelę skrótów. Aby wykonać zapytanie, po prostu oblicz skrót punktu zapytania, a następnie pobierz wszystkie punkty w tym samym koszu z tabeli skrótów.

Po drugie, istnieje rygorystyczna teoria, która potwierdza jego skuteczność. Można wykazać, że czas zapytania jest podliniowy względem rozmiaru bazy danych, czyli szybszy niż wyszukiwanie liniowe. To, o ile szybciej, zależy od tego, ile przybliżenia możemy tolerować.

Wreszcie LSH jest zgodny z każdą normą Lp dla 0 < p <= 2. Dlatego, aby odpowiedzieć na pierwsze pytanie, możesz użyć LSH z metryką odległości euklidesowej lub możesz użyć jej z metryką odległości Manhattan (L1). Istnieją również warianty odległości Hamminga i podobieństwa cosinusowego.

Przyzwoity przegląd został napisany przez Malcolma Slaneya i Michaela Casey'a dla IEEE Signal Processing Magazine w 2008 roku [4].

LSH zostało zastosowane pozornie wszędzie. Możesz spróbować.

[1] Datar, Indyk, Immorlica, Mirrokni, „Locality-Sensitive Hashing Scheme Based on p-Stable Distributions”, 2004.

[2] Weber, Schek, Blott, „Analiza ilościowa i badanie wydajności dla metod wyszukiwania podobieństwa w przestrzeniach wielowymiarowych”, 1998.

[3] Gionis, Indyk, Motwani, „Wyszukiwanie podobieństwa w wysokich wymiarach poprzez haszowanie”, 1999.

[4] Slaney, Casey, „Locality-sensitive hashing for znajdowania najbliższych sąsiadów”, 2008.

I. Metryka odległości

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

• podstawowy rozkład statystyczny Twoich danych;

• związek między cechami, które składają się na Twoje dane (czy są one niezależne - tj. jak wygląda macierz kowariancji); i

• przestrzeń współrzędnych, z której uzyskano dane.

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

Metryka YEuklidesa stosowana w ogromnych mechanizmach rekomendacji internetowych, a także w bieżących badaniach naukowych. Odległości obliczane przez Euklidesa mają znaczenie intuicyjne, a skale obliczeniowe - tj. Odległość euklidesowa jest obliczana w ten sam sposób, niezależnie od tego, czy dwa punkty są w dwóch wymiarach, czy w dwudziestu dwóch wymiarach.

U mnie zawiodło tylko kilka razy, w każdym z tych przypadków odległość euklidesowa zawiodła, ponieważ podstawowy (kartezjański) układ współrzędnych był złym wyborem. Zwykle rozpoznajesz to, ponieważ na przykład długości ścieżek (odległości) nie są już sumowane - np. Gdy przestrzeń metryczna jest szachownicą, odległość Manhattanu jest lepsza niż euklidesowa, podobnie, gdy przestrzenią metryczną jest Ziemia, a twoje odległości są trans -loty kontynentalne, dobrym pomysłem jest miara odległości odpowiednia dla układu współrzędnych biegunowych (np. z Londynu do Wiednia to 2,5 godziny, z Wiednia do Sankt Petersburga to kolejne 3 godziny, mniej więcej w tym samym kierunku, ale z Londynu do St. . Petersburg nie trwa 5,5 godziny, zamiast tego jest nieco ponad 3 godziny).

Ale poza przypadkami, w których dane należą do niekartezjańskiego układu współrzędnych, wybór metryki odległości zwykle nie jest istotny. (Zobacz ten wpis na blogu od studenta CS, porównując kilka metryk odległości badając ich wpływ na KNN klasyfikatora - chi kwadrat daje najlepsze rezultaty, ale różnice nie są duże; Bardziej kompleksowe badanie jest w pracy naukowej, Studium porównawcze Funkcje odległości dla najbliższych sąsiadów - Mahalanobis (zasadniczo euklidesowy znormalizowany w celu uwzględnienia kowariancji wymiarów) był najlepszy w tym badaniu.

Jedno ważne zastrzeżenie: aby obliczenia metryki odległości miały sens, należy zmienić skalęTwoje dane - rzadko jest możliwe zbudowanie modelu kNN w celu wygenerowania dokładnych prognoz bez tego. Na przykład, jeśli budujesz model kNN do przewidywania wyników sportowych, a twoje oczekiwane zmienne to wzrost (cm), waga (kg), tłuszcz (%) i tętno spoczynkowe (uderzenia na minutę), typowy punkt danych może wyglądają mniej więcej tak: [180.4, 66.1, 11.3, 71]. Oczywiście obliczanie odległości będzie zdominowane przez wzrost, podczas gdy udział procentowej zawartości tłuszczu w organizmie będzie prawie nieistotny. Innymi słowy, gdyby zamiast tego dane były podawane w inny sposób, tak aby masa ciała była podawana w gramach, a nie w kilogramach, wówczas pierwotna wartość 86,1 wynosiłaby 86,100, co miałoby duży wpływ na Twoje wyniki, czyli dokładnie to, czego nie podajesz nie chcę.

X_new = (X_old - mu) / sigma

II. Struktura danych

Jeśli obawiasz się wydajności struktury drzewa kd, Tesselacja Voronoi jest koncepcyjnie prostym kontenerem, ale znacznie poprawi wydajność i skaluje się lepiej niż kd-Trees.

Nie jest to najczęstszy sposób utrwalania danych szkoleniowych kNN, chociaż zastosowanie VT w tym celu, a także wynikające z tego korzyści w zakresie wydajności, są dobrze udokumentowane (patrz np. Ten raport Microsoft Research ). Praktyczne znaczenie tego jest takie, że jeśli używasz języka „głównego nurtu” (np. W TIOBE Index ), powinieneś znaleźć bibliotekę do wykonywania VT. Wiem, że w Pythonie i R jest wiele opcji dla każdego języka (np. Pakiet voronoi dla R dostępny w CRAN )

Używanie VT dla kNN działa tak:

Ze swoich danych wybierz losowo punkty - to są twoje centra Woronoi. Komórka Voronoi zawiera wszystkie sąsiednie punkty, które są najbliżej każdego centrum. Wyobraź sobie, że przypisujesz inny kolor do każdego z ośrodków Woronoja, tak aby każdy punkt przypisany do danego środka był pomalowany na ten kolor. Dopóki masz wystarczającą gęstość, zrobienie tego ładnie pokaże granice każdego centrum Woronoja (jako granicę oddzielającą dwa kolory.

Jak wybrać centra Voronoi? Używam dwóch prostopadłych prowadnic. Po losowym wybraniu punktów w oblicz VT dla swoich danych treningowych. Następnie sprawdź liczbę punktów danych przypisanych do każdego centrum Voronoi - te wartości 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 VT z płytkami tego samego rozmiaru. To jest pierwsza zasada, tutaj druga. Wybierz w przez iterację - uruchom algorytm kNN z parametrem zmiennym w i zmierz wydajność (czas wymagany do zwrócenia prognozy przez zapytanie VT).

Więc wyobraź sobie, że masz milion punktów danych ..... Gdyby punkty były utrwalone w zwykłej strukturze danych 2D lub w drzewie kd, wykonałbyś średnio kilka milionów obliczeń odległości dla każdegonowe punkty danych, których zmienną odpowiedzi chcesz przewidzieć. Oczywiście obliczenia te są wykonywane na jednym zestawie danych. W przypadku V / T wyszukiwanie najbliższego sąsiada jest przeprowadzane w dwóch krokach, jeden po drugim, na dwóch różnych populacjach danych - najpierw względem centrów Woronoja, a po znalezieniu najbliższego centrum punkty wewnątrz komórki odpowiadające to centrum jest przeszukiwane w celu znalezienia rzeczywistego najbliższego sąsiada (poprzez kolejne obliczenia odległości). W połączeniu te dwa wyszukiwania są znacznie szybsze niż pojedyncze wyszukiwanie siłowe. Łatwo to zauważyć: dla 1 mln punktów danych załóżmy, że wybierasz 250 centrów Voronoi do tesselacji przestrzeni danych. Średnio każda komórka Voronoi będzie miała 4000 punktów danych. Zamiast więc wykonywać średnio 500 000 obliczeń odległości (brutalna siła), wykonujesz znacznie mniej, średnio zaledwie 125 + 2000.

III. Obliczanie wyniku (przewidywana zmienna odpowiedzi)

Obliczanie przewidywanej wartości na podstawie zestawu danych szkoleniowych kNN obejmuje dwa kroki. Pierwszą jest identyfikacja n, czyli liczba najbliższych sąsiadów, których należy użyć do obliczenia. Drugi to sposób ważenia ich wkładu w przewidywaną wartość.

W / r / t pierwszej składowej, możesz określić najlepszą wartość n rozwiązując problem optymalizacji (bardzo podobny do optymalizacji metodą 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 zestawie instancji testowych (w celu obliczenia przewidywanych wartości) dla n = 1, n = 2, n = 3 itd. I wykreślić błąd jako funkcję n. Jeśli chcesz, aby na początku pojawiła się wiarygodna wartość n, ponownie użyj n = 3.

Drugi składnik to sposób ważenia udziału 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 po prostu 1 / (odległość * K) lub odwrotnością odległości od tego sąsiada do instancji testowej, często pomnożonej przez pewną empirycznie wyprowadzoną stałą K. nie jestem fanem tej techniki, ponieważ często przeciąża ona najbliższych sąsiadów (i jednocześnie niedocenia tych bardziej odległych); Znaczenie tego polega na tym, że dana prognoza może być prawie całkowicie zależna od pojedynczego sąsiada, co z kolei zwiększa wrażliwość algorytmu na szum.

Konieczną lepszą funkcją ważenia, która zasadniczo omija to ograniczenie, jest funkcja Gaussa , która w Pythonie wygląda następująco:

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

Aby obliczyć przewidywaną wartość za pomocą kodu kNN, należy zidentyfikować n najbliższych sąsiadów punktu danych, których zmienną odpowiedzi chcesz przewidzieć („instancja testowa”), a następnie wywołać funkcję weight_gauss, raz dla każdego z n sąsiadów, przekazując w odległości między każdym sąsiadem a punktem testowym. Funkcja ta zwraca wagę każdego sąsiada, która jest następnie używana jako współczynnik tego sąsiada w obliczaniu średniej ważonej.

To, z czym się mierzysz, 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 być może znaleźć transformację liniową, która pozwoliłaby ci użyć mniej niż 21 z mniej więcej taką samą jakością wyniku.

Aktualizacja: spotkałem się z nimi w książce Rangayyan pt. Biomedical Signal Processing (mam nadzieję, że dobrze ją pamiętam). ICA nie jest trywialną techniką, ale została opracowana przez naukowców z Finlandii i myślę, że kod Matlab jest publicznie dostępny do pobrania. PCA jest szerzej stosowaną techniką i uważam, że powinieneś być w stanie znaleźć jego R lub inną implementację oprogramowania. PCA wykonuje się poprzez iteracyjne rozwiązywanie równań liniowych. Zrobiłem to zbyt dawno, żeby pamiętać, jak to zrobić. =)

Chodzi o to, że rozkładasz swoje sygnały na niezależne wektory własne (tak naprawdę dyskretne funkcje własne) i ich wartości własne, 21 w twoim przypadku. Każda wartość własna pokazuje wielkość udziału każdej funkcji własnej w każdym z twoich pomiarów. Jeśli wartość własna jest niewielka, możesz bardzo dokładnie odwzorować sygnały bez użycia odpowiadającej im funkcji własnej iw ten sposób pozbywasz się wymiaru.

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

Jak już powiedziano, w wielowymiarowej przestrzeni przekleństwo wymiarowości czai się za rogiem, powodując, że tradycyjne podejścia, takie jak popularne drzewo kd, są tak powolne, jak podejście brutalnej siły. W rezultacie zwracamy uwagę na przybliżone wyszukiwanie najbliższego sąsiada (ANNS) , które na korzyść pewnej dokładności przyspiesza proces. Otrzymasz dobre przybliżenie dokładnego NN, z dobrym prawdopodobieństwem.

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

1. Nowoczesne podejścia do LSH , takie jak Razenshteyn .
2. RKD forest : Forest (s) of Randomized kd trees (RKD), jak opisano w FLANN lub w nowszym podejściu, którego byłem częścią, kd-GeRaF .
3. LOPQ, co oznacza lokalnie zoptymalizowaną kwantyzację produktu, jak opisano tutaj . Jest bardzo podobny do nowego podejścia Babenko + Lemptitsky'ego .

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

1. Dwa zestawy wysoko wymiarowych punktów: znajdź najbliższego sąsiada w drugim zestawie
2. Porównanie czasu wykonywania zapytań Nearest Neighbor na różnych strukturach danych
3. Implementacja drzewa kd w języku PCL jest bardzo powolna

Aby odpowiedzieć na pytania jeden po drugim:

• Nie, odległość euklidesowa jest złą miarą w wielowymiarowej przestrzeni. Zasadniczo w przypadku dużych wymiarów punkty danych mają duże różnice między sobą. Zmniejsza to względną różnicę odległości między danym punktem danych a jego najbliższym i najdalszym sąsiadem.
• Wiele artykułów / badań znajduje się w danych o dużych wymiarach, ale większość z nich wymaga dużego wyrafinowania matematycznego.
• Drzewo KD jest złe dla danych wysokowymiarowych ... unikaj go za wszelką cenę

Oto fajny artykuł, który pomoże Ci zacząć we właściwym kierunku. „ Kiedy w najbliższym sąsiedztwie ma znaczenie ?” przez Beyer et all.

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

Podobieństwo cosinusowe to powszechny sposób porównywania wektorów o dużych wymiarach. Zwróć uwagę, że ponieważ jest to podobieństwo, a nie odległość, chcesz ją zmaksymalizować, a nie minimalizować. Możesz także porównać dane w sposób specyficzny dla domeny, na przykład, jeśli dane były sekwencjami DNA, możesz użyć podobieństwa sekwencji, który uwzględnia prawdopodobieństwo mutacji itp.

Liczba najbliższych sąsiadów, których należy użyć, różni się w zależności od typu danych, ilości szumu itp. Nie ma żadnych ogólnych zasad, wystarczy znaleźć to, co działa najlepiej w przypadku określonych danych i problemu, wypróbowując wszystkie wartości z zakresu . Ludzie intuicyjnie rozumieją, że im więcej danych, tym mniej potrzebnych jest sąsiadów. W hipotetycznej sytuacji, w której masz wszystkie możliwe dane, wystarczy poszukać najbliższego najbliższego sąsiada do sklasyfikowania.

Wiadomo, że metoda k Nearest Neighbor jest kosztowna obliczeniowo. Jest to jeden z głównych powodów, dla których ludzie zwracają się do innych algorytmów, takich jak maszyny wektorów nośnych.

kd-trees rzeczywiście nie będą działać zbyt dobrze na danych wielowymiarowych. Ponieważ krok przycinania nie pomaga już zbytnio, ponieważ najbliższa krawędź - odchylenie 1-wymiarowe - prawie zawsze będzie mniejsza niż odchylenie w pełnym wymiarze od znanych najbliższych sąsiadów.

Co więcej, drzewa kd działają dobrze tylko z normami Lp dla wszystkiego, co znam, i istnieje efekt koncentracji odległości, który sprawia, że ​​algorytmy oparte na odległości degradują się wraz ze wzrostem wymiarowości.

Aby uzyskać więcej informacji, możesz poczytać o klątwie wymiarowości i różnych jej wariantach (jest więcej niż jedna strona!)

Nie jestem przekonany, że po prostu ślepe przybliżanie najbliższych sąsiadów Euklidesa, np. Za pomocą LSH lub losowych rzutów, ma wiele pożytku. W pierwszej kolejności może być konieczne użycie znacznie bardziej precyzyjnej funkcji odległości!

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

Myślę, że cosinus na tf-idf funkcji logicznych działałby dobrze w przypadku większości problemów. Dzieje się tak, ponieważ jego sprawdzona heurystyka używana w wielu wyszukiwarkach, takich jak Lucene. Z mojego doświadczenia wynika, że ​​odległość euklidesowa wykazuje złe wyniki w przypadku danych tekstowych. Wyboru różnych wag i przykładów k można dokonać za pomocą danych treningowych i wyboru parametru brutalnej siły.

iDistance jest prawdopodobnie najlepszym rozwiązaniem do dokładnego wyszukiwania informacji o danych wielowymiarowych. Możesz to postrzegać jako przybliżoną analizę Woronoja.

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

1. Odległość euklidesowa jest dobrym miernikiem odległości, jednak jest obliczeniowo droższa niż odległość na Manhattanie 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ć wynikowe krzywe ROC lub inne miary precyzji / przypomnienia, aby znaleźć akceptowalną wartość.

3. Odległości Euklidesa i Manhattanu uwzględniają nierówność trójkąta , dlatego można ich używać w drzewach metrycznych. Rzeczywiście, drzewa KD mają poważnie obniżoną wydajność, gdy dane mają więcej niż 10 wymiarów (sam doświadczyłem tego problemu). Uważam, że drzewa VP są lepszym rozwiązaniem.

KD Drzewa działają dobrze w 21 wymiarach, jeśli rzucisz wcześnie, po obejrzeniu powiedzmy 5% wszystkich punktów. FLANN robi to (i inne przyspieszenia), aby dopasować 128-dim w wektorach SIFT. (Niestety FLANN robi tylko metrykę euklidesową, a szybki i solidny scipy.spatial.cKDTree robi tylko metryki Lp; te mogą, ale nie muszą być odpowiednie dla twoich danych.) Jest tu oczywiście kompromis między szybkością a dokładnością.

(Gdybyś mógł opisać swoje Ndata, Nquery, dystrybucję danych, może to pomóc ludziom wypróbować podobne dane).

Dodano 26 kwietnia, czasy działania cKDTree z odcięciem na moim starym mac ppc, aby dać bardzo przybliżony obraz 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 wypróbować krzywą kolejności az. To łatwe dla 3 wymiarów.

Czy odległość euklidesowa jest dobrym wskaźnikiem do znajdowania najbliższych sąsiadów w pierwszej kolejności? Jeśli nie, jakie mam możliwości?

Sugerowałbym miękkie grupowanie podprzestrzeni , dość powszechne obecnie podejście, w którym wagi cech są obliczane w celu znalezienia najbardziej odpowiednich wymiarów. Możesz użyć tych wag, na przykład, używając odległości euklidesowej. Zobacz przekleństwo wymiarowości dla typowych problemów, a także ten artykuł może cię w jakiś sposób oświecić:

Algorytm grupowania typu k-średnich dla grupowania podprzestrzennego mieszanych liczbowych i jakościowych zbiorów danych