Znajdź bliskie pary w przestrzeni o bardzo dużych wymiarach za pomocą rzadkich wektorów

9

mam N(~ milion) wektorów cech. Tam sąM (~ milion) funkcji binarnych, ale tylko w każdym wektorze K (~ tysiąc) z nich byłoby 1, reszta to 0. Szukam par wektorów, które mają przynajmniejL (~ sto) wspólnych cech (1zarówno). Liczba takich par jest podobna do wielkościN (~ milion).

Myślę, że można to potraktować jako szukanie bliskich par punktowych w przestrzeni o bardzo dużych wymiarach. Funkcja odległości może być taka, że ​​jest oparta na tym, ile wspólnych cech mają te dwa wektory. Ale prawdopodobnie przydałby się również w bardziej konwencjonalnym pomiarze odległości (takim jak euklides).

Jakie dobrze znane algorytmy byłyby przydatne do rozwiązania tego problemu? Wszystko, co jest kwadratoweN lub M nie będzie praktyczne.


Przykład sformułowania problemu w świecie rzeczywistym należy rozważyć Nludzie przemieszczający się między wieloma lokalizacjami. Jeśli dwie osoby były w tym samym miejscu w tym samym czasie, mówimy, że się poznali. (Liczba kombinacji lokalizacji i czasu z obecną co najmniej 1 osobą wynosiM.) Szukamy przyjaciół: osób, które przynajmniej spotkały L czasy.

Daniel Darabos
źródło
1
Jeśli wektor 1, cechą 1 jest 0, i wektor 2, funkcja 1 jest również 0czy mają tę cechę „wspólną”?
Gung - Przywróć Monikę
@ user777, zakładam, że nie , w takim przypadku Twoja odpowiedź jest idealna, ale byłoby miło, gdyby to zostało wyraźnie określone przez OP.
Gung - Przywróć Monikę
@ Gung, zakładasz, że masz rację. Zredagowałem pytanie, aby wyjaśnić. Dzięki!
Daniel Darabos,
1
O tym, ile par wektorów ma> 100 wspólnych cech - próbka losowa + brutalna siła? Czy rozmiary 1M x 1M stanowią prawdziwy problem, czy są już gotowe? Zobacz także podejście do wyszukiwania bit-string-najbliższego sąsiada przy przepełnieniu stosu.
denis
1
Być może szalona sugestia: wyświetl wektory cech o długości 1 Mbit jako obrazy o wymiarach 1000 x 1000 pikseli i wyszukaj metody grupowania obrazów, np . Stackoverflow.com/search?q=[image]+clustering . Afaik, musisz znaleźć dobre cechy (nie pojedyncze piksele), żeby to działało, ale nie jestem ekspertem.
den

Odpowiedzi:

6

Wygląda na to, że podejście, którego szukasz, to połączenie sygnatur minhash i mieszania wrażliwego na lokalizację (LSH); (bezpłatnie dostępny) pdf Mining Massive Datasets opisuje to podejście (i inne miary podobieństwa) bardziej szczegółowo w rozdziale 3, ale krótko:

Podpis minhash skondensowana reprezentacja pierwotnego matrycy, która jest wykonana poprzez zastosowanie pewnej liczby N w funkcji mieszania cech, co zmniejsza liczbę funkcji, na obserwacji. Zmniejsza to rozmiar twoich danych, jednak prawdopodobnie zauważysz, że nadal pozostawia ci toO(N2) problem.

Aby rozwiązać ten problem, MMDS radzi, że jeśli wszystko, co chcesz znaleźć, to pary powyżej pewnego progu podobieństwa (który wydaje się mieć zastosowanie w twoim przypadku), możesz skupić się tylko na tych parach, które najprawdopodobniej będą podobne - takie podejście nazywa się Hashing wrażliwy na lokalizację , aw sekcji 3.4 przedstawiają przykład połączenia podejścia podpisu minhash z LSH.

Oprócz tekstu dostępne są również wykłady na temat kursu Coursera o tej samej nazwie.

Tchotchke
źródło
7

Szukam par wektorów, które mają przynajmniej L cechy wspólne.

To tylko wewnętrzny produkt binarnych wektorów cech. Gdy iloczyn wewnętrzny jest większy niżL1, para będzie miała przynajmniej Lelementy wspólne. Powinno to być stosunkowo szybkie obliczenie - przynajmniej szybsze niż odległość euklidesowa, co byłoby marnotrawstwem i powolne dla tych danych. Ponieważ zastrzegasz, że szukasz par, oznacza to z natury, że musisz wykonać aby porównać każdy wektor.(N2)

Znalezienie punktów, które są blisko siebie, jest w rzeczywistości problemem klastrowym. Ale pierwszym krokiem algorytmów grupowania, które znam, jest obliczenie par odległości lub podobieństw. Jestem pewien, że ktoś opracował bardziej wydajne alternatywy. Chodzi o terminologię: posiadanie co najmniej wspólnych sąsiadów jest wyrażone jako podobieństwo , a nie odległość! Produkty wewnętrzne to w tym przypadku nienormalizowane podobieństwa kosinusowe.L

Możesz uczynić to łatwiejszym do wykonania, wykonując obliczenia produktu wewnętrznego tylko wtedy, gdy suma wektora cech (która w tym przypadku jest taka sama jak norma) dla obserwacji jest większa niż , ponieważ jest to niemożliwe dla tego binarnego wektora cech aby mieć wewnętrzną produkt z innym binarnym wektorem cech, które będą spełniać moje kryterium, gdy suma ta jest mniejsza niż . Oczywiście, obliczanie tych sum to tylko złożoność , więc jestem tanim sposobem na zmniejszenie wielkości wewnętrznego kroku produktu.L1LO(N)

Ale klasycznym sposobem na ograniczenie zakresu tego problemu jest wykonanie dodatkowego filtrowania wstępnego. Czy jesteś szczególnie zainteresowany, gdy jedna, dość nietypowa funkcja przyjmuje wartość 1? Jeśli tak, wykonaj obliczenia tylko dla tych wektorów cech.

A może przydałoby Ci się ponowne sformułowanie problemu. Na przykład wiadomo, że pobieranie próbek ma dobre właściwości; statystyki wnioskowania rozwijają się do tego pomysłu do dość głębokiej. Być może analiza całego zestawu danych jest niewykonalna, ale badanie małej próbki jest całkowicie wykonalne. Nie wiem na pytanie, na które próbujesz odpowiedzieć, ale jeśli dokładnie zaplanujesz eksperyment, możesz uciec od patrzenia tylko na kilka tysięcy obserwacji, a do celów weryfikacji pozostaje więcej niż wystarczająca ilość danych.

Po jakimś dodatkowym myśli, mam silne przeczucie, że dane pracujesz z jakiś rodzaj grafu . Jest bardzo prawdopodobne, że składa się z kilku połączonych komponentów, w którym to przypadku można rozłożyć na zestaw wykresów, z przyjemnym efektem ubocznym zmniejszenia wymiarów danych. Nawet jeśli wykres jest tylko dwoma połączonymi komponentami mniej więcej tego samego rozmiaru, oznacza to, że twoje porównania par mają w przybliżeniu całkowity koszt!GGGO(N2)14

Jeśli wykres jest symetryczny, pomocne mogą być następujące obserwacje:

  1. Zdefiniuj Laplaciana na swoim wykresie jako , gdzie jest macierzą diagonalną stopnia (suma każdego wektora cech), a jest macierzą przyległości (układaniem wektorów cech w macierz).P=DADA
  2. Ilość razy rozpoznawane jako wartości własnej jest liczbą połączonych składników . Rozkład wykresu na połączone ze sobą komponenty i praca wyłącznie z tymi komponentami spowoduje efekt uboczny zmniejszenia wymiaru danych; obliczenie ilości twoich zainteresowań będzie łatwiejsze. Ale obliczenie składu eigend będzie kosztowne dla miliona wierzchołków ...0PG
  3. (Po pełnym permutacji) jest blok macierzą diagonalną o Laplacians połączonych ze sobą elementów .PG
  4. P jest dodatnim półfinałem. Jest to prawie na pewno przydatne w jakiś sposób.
  5. Algebraiczną przyłączeniowa jest wartością drugiego najmniejszym wartości własnej . To pokazuje, jak dobrze podłączony jestByć może to odpowie na niektóre pytania, które Cię interesują: wektory, które mają wspólne cechy. Teoria grafów spektralnych rozwija tę ideę bardziej szczegółowo.GPG

„Czy to problem SNA?” Nie jestem pewny. W jednej aplikacji funkcje opisują zachowanie, a my chcemy połączyć ludzi o podobnych zachowaniach. Czy to sprawia, że ​​jest to problem SNA?

Jeśli masz dwustronny wykres łączący ludzi z zachowaniami, możesz myśleć o tym jak o sieci afiliacyjnej , w której ludzie są rzędami, a zachowania jak kolumnami. Jeśli chcesz połączyć ludzi do ludzi za pośrednictwem zachowań mają wspólnego, można obliczyć . to liczba wspólnych zachowań ludzi. Oczywiście zestaw wierzchołków, w których odpowiada na twoje pytanie.BBBT=AAijAijL

Sycorax mówi Przywróć Monikę
źródło
Dzięki za doskonałą odpowiedź! To wiele rzeczy, które będę musiał zbadać dalej. Nie jestem jednak przekonany, że porównania parami są nieuniknione. Czy to nie jest problem klastrowania, gdy szukam klastrów o rozmiarze> 1? Spodziewałem się, że pewne podejście do podziału przestrzennego może znacznie ograniczyć liczbę porównań parami.
Daniel Darabos,
Przepraszam, ale niewiele wiem o analizie danych. Ale czy nie jest to problem grupowania, gdy chcemy zgrupować punkty, które leżą blisko siebie? Mam maksymalną odległość (L) i chcę znaleźć grupy (pary) punktów, które leżą w tej odległości od siebie. Czy to zbytnio rozszerza definicję grupowania?
Daniel Darabos,
1
Rzeczywiście można to wyrazić jako problem graficzny. W takim przypadku mamy dwudzielny wykres N punktów i cech M i chcemy znaleźć pary punktów, które mają co najmniej L wspólnych sąsiadów. W szczególności patrzę teraz na frazowanie oparte na wektorze cech, mając nadzieję, że istnieje metoda klastrowania, która mogłaby mi się przydać. K-SVD zasugerowano podobny problem w stats.stackexchange.com/questions/93366/... , więc czytam o tym w tej chwili. Dzięki!
Daniel Darabos,
„Czy to problem SNA?” Nie jestem pewny. W jednej aplikacji funkcje opisują zachowanie, a my chcemy połączyć ludzi o podobnych zachowaniach. Czy to sprawia, że ​​jest to problem SNA? Dziękujemy za zapoznanie się z terminologią, bardzo pomocne jest kierowanie moim wyszukiwaniem.
Daniel Darabos,
Poprawiłem swoją odpowiedź. Czy twoim ostatecznym celem jest tylko wyliczenie ludzi o wielu wspólnych zachowaniach, czy też jest to coś innego?
Sycorax mówi: Przywróć Monikę
2

Szukając ludzi spotykających się w blokach czasoprzestrzennych:
podziel przestrzeń na bloki (bloki miejskie, km kwadratowe, cokolwiek), a czas na bloki . Istnieje duża szansa, że ​​jeśli ludzie się spotkają, spotkają się w tym samym bloku. Więc uruchom NN w każdym bloku. Środowiska wykonawcze i wskaźniki błędów będą oczywiście zależeć od rozmiarów i kształtów bloków (także od tego, co można zrównoleglać / MapReduce), ale masz parametry do zabawy - inżynieria, nie szeroko otwarte .NspaceNtime
O(N2)

Zobacz także:
najbliżsi sąsiedzi-szukaj-bardzo-wymiarowo-danych na datascience.stackexchange

pairwise.py :

wykorzystuje bibliotekę Python Gensim i heapq ze standardowej biblioteki, aby dokonywać ogromnie szybkich i skalowalnych porównań parami między arbiteralnie dużą liczbą dokumentów przy użyciu TF-IDF i odległości cosinus.

denis
źródło
1

Odwrócony słownik! Reprezentuj punkt jako , klucze odpowiadające niezerowym wartościom (tj. Właściwościom prawdziwe). Średnia wielkość pamięci elementu będzie . Rzeczywiście, potrzebuję tylko ciągów do przechowywania funkcji, a pływaków do przechowywania wartości.xfeat1:value1,feat101:value101KKK

Dla każdej funkcji zbuduj słownik zawierający indeksy udostępniające tę funkcję. Mamy nadzieję, że liczba ta nie będzie zbyt duża (jeśli masz funkcję wspólną dla wszystkich indeksów, to podejście jest zrujnowane, możesz przestać czytać tutaj).

Ten słownik wygląda następująco: . Jeśli chcę zwiększyć prędkość i zaoszczędzić miejsce, mogę nawet upuścić funkcje, które można znaleźć tylko z jednym elementem (tutaj: ), ponieważ nie będą tworzyć bliskich par. Słownik ten jest wbudowany w operacje .feat1:{1,101,202},feat2:{7,202},feat3:{202}...featM:{3,45,6}feat3O(NK)

Teraz, gdy chcesz oszacować odległość elementu od pozostałych, wygeneruj (ze słownikiem) listę indeksów współdzielących co najmniej jedną cechę z . Wiesz, że wszystkie pozostałe elementy są dalekie od (nie mają nawet jednej funkcji!). Jeśli średnia liczba „elementów na funkcję” jest niska (nazwij to ), nie musisz już być w .xxxPO(N2)

Jest jeszcze jedna wielka poprawa, jeśli i są również reprezentowane jako słowniki, ponieważ lub można oceniać iterując po klawiszach i , w operacjach .xyd(x,y)<x,y>xyO(K)

Twoja ostateczna złożoność to zamiast naiwnego wstępnego podejścia .O(NPK)O(MN2)

Zastosowałem tę metodę do wdrożenia KNN na dużym zestawie tekstowym (pociąg: 2 000 000 linii, test 35 000 linii, liczba funkcji: 10 000, średnia liczba funkcji na element: 20), które trwały około godziny .. .

RUser4512
źródło
Nie do końca rozumiem to podejście - to nie dlatego, że ci nie wierzę, to całkowicie z powodu mojej nieznajomości różnych strategii reprezentowania danych. Być może mógłbyś bardziej szczegółowo omówić to, co omawiasz w pierwszych dwóch akapitach?
Sycorax mówi Przywróć Monikę
1) „ta liczba nie będzie zbyt duża”: średnia suma kolumn = średnia suma wierszy = 1000. 2) unosi się? funkcje OP to binarne 3) środowiska wykonawcze dla 3 przebiegów N, 2N, 4N byłyby interesujące, pokazałyby, gdyby były w przybliżeniu . O(N2)
den
1

Znalazłem odniesienie, które może ci się przydać, i uważam, że jest asymptotycznie bardziej wydajne niż każde inne przedstawione dotąd rozwiązanie. Jeśli dobrze rozumiem, możesz zbudować wykres najbliższego sąsiada (KNN) w czasie .kO(LNlog(N))

L. Erotz, M. Steinbach i V. Kumar. „Nowy wspólny algorytm klastrowania najbliższego sąsiada i jego zastosowania”. Materiały z pierwszego warsztatu na temat klastrowania danych wielowymiarowych i ich zastosowań, 2002.

Sycorax mówi Przywróć Monikę
źródło
Dzięki, to ciekawa lektura. Jak uzyskałeś czas O (LN log (N))? To brzmi świetnie. Ale opis algorytmu zaczyna się od „Skonstruuj macierz podobieństwa” i będzie to, o ile rozumiem, macierz NxN.
Daniel Darabos
@DanielDarabos Złożoność została opisana w książce Practical Graph Mining with R.
Sycorax mówi Reinstate Monica
1

Szalonym, ale prawdopodobnie działającym podejściem może być przejście do dziedziny częstotliwości. Istnieje zwariowany / chory szybki fft o nazwie „ rzadki FFT ”, w którym określasz liczbę trybów, na których Ci zależy (liczba 100 funkcji), a następnie pracujesz w zwojach i szukasz wartości maksymalnego rzędu większej niż próg (poszukaj bity w górnych rejestrach twoich liczb). Będzie to gdzie .O(klogn)k<<n

Biorąc pod uwagę, że k wynosi 100, a n to 1e6, powinno to dać ~ 1e4x przyspieszenie w porównaniu z klasycznym FFT.

Jeśli potrzebujesz jeszcze 20-krotnej prędkości i jesteś ryzykantem, zamiast zwoływać wszystkie wiersze względem domeny i szukać piku, możesz załadować podzbiór wierszy.

Możesz również wstępnie filtrować kolumny, usuwając kolumny, których sumy są mniejsze niż 50, lub inny próg, który jest rzędu połowy liczby wierszy, które chcesz dopasować. Przynajmniej powinieneś usunąć kolumny wszystkich zer i wszystkich 1 jako nieinformacyjne. To samo dotyczy wierszy, które są całkowicie puste lub wystarczająco puste, lub wierszy, które są tak pełne, że nie mają znaczenia.

Zadanie: powinienem tu podać przykład, używając danych syntetycznych i porównać niektóre metody.

EngrStudent
źródło
0

Właśnie natrafiłem na artykuł, który jest bezpośrednio istotny.

Algorytmy randomizowane i NLP: korzystanie z funkcji skrótu uwzględniającej lokalizację w celu szybkiego grupowania rzeczowników (Ravichandran i in., 2005)

W rzeczywistości jest zaimplementowany w https://github.com/soundcloud/cosine-lsh-join-spark, gdzie go znalazłem.

Opiera się na haszowaniu wrażliwym na lokalizację (wspomnianym już w innych odpowiedziach). Po zredukowaniu wektorów cech do przestrzeni mało wymiarowej używa szybkiego połączenia Hamminga, aby znaleźć najbliższych sąsiadów.

Daniel Darabos
źródło