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

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ą przynajmniej$L$ (~ sto) wspólnych cech ($1$zarówno). Liczba takich par jest podobna do wielkości$N$ (~ 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 kwadratowe$N$ lub $M$ nie będzie praktyczne.

Przykład sformułowania problemu w świecie rzeczywistym należy rozważyć $N$ludzie 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ą wynosi$M$.) Szukamy przyjaciół: osób, które przynajmniej spotkały $L$ czasy.

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 to$O(N^2)$ 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.

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ż$L-1$, para będzie miała przynajmniej $L$elementy 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.$\binom{N}{2}$

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.$L-1$$L$$O(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!$G$$G$$G$$O(N^2)$$\frac{1}{4}$

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=D-A$$D$$A$
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 ...$0$$P$$G$
3. (Po pełnym permutacji) jest blok macierzą diagonalną o Laplacians połączonych ze sobą elementów .$P$$G$
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.$G$$P$$G$

„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.$B$$BB^T=A$$A_{ij}$$A_{ij}\ge L$

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 .$Nspace$$Ntime$
$O( N^2 )$

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.

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.$x$$feat_1:value_1, feat_{101}:value_{101}$$K$$K$$K$

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 .$feat_1 : \{1,101,202\}, feat_2 : \{7,202\},feat_3 : \{202\}...feat_M:\{3,45,6\}$$feat_3$$O(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 .$x$$x$$x$$P$$O(N^2)$

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 .$x$$y$$d(x,y)$$<x,y>$$x$$y$$O(K)$

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

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 .. .

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 .$k$$O(LN\log(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.

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(k \cdot \log{n} )$$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.

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.