Finden Sie enge Paare in einem sehr hochdimensionalen Raum mit spärlichen Vektoren

Ich habe (~ eine Million) Merkmalsvektoren. Es gibt (~ eine Million) binäre Merkmale, aber in jedem Vektor wären nur (~ tausend) von ihnen , der Rest ist . Ich suche nach Vektorpaaren, die mindestens (~ hundert) Merkmale gemeinsam haben ( in beiden). Die Anzahl solcher Paare ist ähnlich groß wie (~ eine Million).M K 1 0 L 1 $N$$M$$K$$1$$0$$L$$1$$N$

Ich denke, dies könnte als Suche nach engen Punktpaaren in einem sehr hochdimensionalen Raum betrachtet werden. Die Distanzfunktion könnte so sein, dass sie darauf basiert, wie viele Merkmale die beiden Vektoren gemeinsam haben. Aber es wäre wahrscheinlich auch mit einer konventionelleren Distanzmetrik (wie Euklidisch) nützlich.

Welche bekannten Algorithmen wären nützlich, um dieses Problem anzugehen? Alles, was in oder quadratisch ist, ist nicht praktikabel.$N$$M$

Eine beispielhafte Formulierung des Problems in der Praxis besteht darin, Personen zu berücksichtigen , die sich zwischen mehreren Orten bewegen. Wenn zwei Personen zur selben Zeit am selben Ort waren, sagen wir, dass sie sich getroffen haben. (Die Anzahl der Ort-Zeit-Kombinationen mit mindestens 1 anwesenden Person beträgt ) Wir suchen Freunde: Personen, die sich mindestens mal getroffen haben.M $N$$M$$L$

Es sieht so aus, als ob der Ansatz, den Sie suchen, eine Kombination aus Minhash-Signaturen und Locality Sensitive Hashing (LSH) ist. Das (frei verfügbare) PDF von Mining Massive Datasets beschreibt diesen Ansatz (und andere Ähnlichkeitsmaße) in Kapitel 3 ausführlich, jedoch kurz:

Eine Minhash-Signatur ist eine komprimierte Darstellung Ihrer ursprünglichen Matrix, die durch Anwenden einer Anzahl n von Hash-Funktionen auf Features erstellt wird, wodurch die Anzahl der Features pro Beobachtung verringert wird. Dies reduziert die Größe Ihrer Daten. Sie werden jedoch wahrscheinlich feststellen, dass Sie immer noch ein -Problem haben.$O(N^2)$

Um dies zu beheben, empfiehlt MMDS, dass Sie sich nur auf die Paare konzentrieren können, die am wahrscheinlichsten ähnlich sind - dieser Ansatz, wenn Sie nur Paare oberhalb einer bestimmten Ähnlichkeitsschwelle finden möchten (was in Ihrem Fall zu gelten scheint) wird als Locality Sensitive Hashing bezeichnet . In Abschnitt 3.4 wird anhand eines Beispiels erläutert, wie der Minhash-Signaturansatz mit LSH kombiniert wird.

Neben dem Text gibt es auch Vorlesungen zum gleichnamigen Coursera-Kurs .

Ich suche nach Vektorpaaren, die mindestens Merkmale gemeinsam haben.$L$

Dies ist nur ein inneres Produkt von binären Merkmalsvektoren. Wenn das innere Produkt größer als , hat das Paar mindestens L Elemente gemeinsam. Dies sollte eine relativ schnelle Berechnung sein - zumindest schneller als die euklidische Entfernung, was für diese Daten verschwenderisch und langsam wäre. Da Sie festlegen, dass Sie nach Paaren suchen, bedeutet dies von Natur aus, dass Sie -Berechnungen durchführen müssen, um jeden Vektor zu vergleichen.$L-1$$L$$\binom{N}{2}$

Das Finden von Punkten, die nahe beieinander liegen, ist in der Tat ein Clustering-Problem. Der erste Schritt der mir vertrauten Clustering-Algorithmen ist jedoch die Berechnung paarweiser Abstände oder Ähnlichkeiten. Ich bin sicher, jemand hat effizientere Alternativen entwickelt. Ein Punkt zur Terminologie: Mindestens gemeinsame Nachbarn zu haben, wird als Ähnlichkeit formuliert , nicht als Distanz! Innere Produkte sind in diesem Fall nicht normalisierte Kosinusähnlichkeiten.$L$

Sie können dies leichter nachvollziehen, indem Sie die Berechnung des inneren Produkts nur dann durchführen, wenn die Summe des Merkmalsvektors (in diesem Fall die Norm) für eine Beobachtung größer als , da dies für diesen binären Merkmalsvektor unmöglich ist ein inneres Produkt mit einem anderen binären Merkmalsvektor zu haben, der mein Kriterium erfüllt, wenn diese Summe kleiner als . Offensichtlich ist die Berechnung dieser Summen nur eine -Komplexität, daher ist es eine kostengünstige Möglichkeit, die Größe des inneren Produktschritts zu verringern.L O ( N $L-1$$L$$O(N)$

Der klassische Weg, um den Umfang dieses Problems zu verringern, besteht darin, eine zusätzliche Vorfilterung durchzuführen. Interessieren Sie sich besonders dafür, wenn eine etwas ungewöhnliche Funktion den Wert 1 annimmt? Wenn ja, führen Sie nur die Berechnung für diese Merkmalsvektoren durch.

Oder vielleicht könnten Sie davon profitieren, Ihr Problem neu zu formulieren. Beispielsweise ist bekannt, dass die Probenahme gute Eigenschaften hat. Inferenzstatistiken entwickeln sich zu dieser Idee bis zu einer gewissen Tiefe. Vielleicht ist es nicht möglich, den gesamten Datensatz zu analysieren, aber es ist durchaus möglich, eine kleine Stichprobe zu untersuchen. Ich weiß nicht, welche Frage Sie beantworten möchten, aber wenn Sie Ihr Experiment sorgfältig entwerfen, werden Sie möglicherweise nur ein paar tausend Beobachtungen betrachten, wobei mehr als genug Daten für Validierungszwecke übrig bleiben.

Nach einigen zusätzlichen Überlegungen habe ich die starke Vermutung, dass die Daten, mit denen Sie arbeiten, eine Art Grafik . Es ist sehr plausibel, dass aus mehreren verbundenen Komponenten besteht. In diesem Fall können Sie in eine Reihe von Graphen zerlegen , mit dem glücklichen Nebeneffekt, dass die Dimensionalität der Daten verringert wird. Selbst wenn der Graph nur aus zwei verbundenen Komponenten von ungefähr derselben Größe besteht, bedeutet dies, dass Ihre paarweisen -Vergleiche ungefähr die Gesamtkosten haben!G G O ( N 2 ) $G$$G$$G$$O(N^2)$$\frac{1}{4}$

Wenn der Graph symmetrisch ist, können die folgenden Beobachtungen hilfreich sein:

1. Definieren Sie den Laplace-Wert Ihres Graphen als , wobei eine diagonale Gradmatrix (die Summe jedes Merkmalsvektors) und die Adjazenzmatrix (das Stapeln von Merkmalsvektoren zu einer Matrix) ist.D $P=D-A$$D$$A$
2. Die Zahl mal erscheint als ein Eigenwert von ist die Anzahl der verbundenen Komponenten von . Wenn Sie das Diagramm in seine verbundenen Komponenten zerlegen und nur mit diesen Komponenten arbeiten, wird die Dimension Ihrer Daten verringert. Die Berechnung Ihrer Interessensmenge wird einfacher. Die Berechnung der Eigendekomposition wird jedoch für eine Million Eckpunkte teuer sein ...P $0$$P$$G$
3. (Nach einer vollständigen Permutation) ist ein Blockdiagonalmatrix der Laplace - Operatoren der angeschlossenen Komponenten von .$P$$G$
4. $P$ ist positiv semidefinit. Das ist mit ziemlicher Sicherheit irgendwie nützlich.
5. Die algebraische Konnektivität von ist , wird der Wert des zweiten kleinsten Eigenwert von . Dies zeigt Ihnen, wie gut verbunden ist. Vielleicht beantwortet das einige der Fragen, an denen Sie interessiert sind: die Vektoren, die gemeinsame Merkmale haben. Die Spektralgraphentheorie entwickelt diese Idee etwas detaillierter.P $G$$P$$G$

"Ist das ein SNA-Problem?" Ich bin mir nicht sicher. In einer Anwendung beschreiben die Funktionen das Verhalten und wir möchten Menschen mit ähnlichen Verhaltensweisen verbinden. Ist das ein SNA-Problem?

Wenn Sie ein zweigeteiltes Diagramm haben, das Personen mit Verhaltensweisen verbindet, können Sie sich dies als ein Zugehörigkeitsnetzwerk , mit Personen als Zeilen und Verhaltensweisen als Spalten. Wenn Sie Personen über das gemeinsame Verhalten mit Personen verbinden möchten, können Sie berechnen . ist die Anzahl der Verhaltensweisen, die die Menschen gemeinsam haben. Offensichtlich beantwortet die Menge der Eckpunkte, an denen Ihre Frage beantwortet.B B T = A A i j A i j ≥ $B$$BB^T=A$$A_{ij}$$A_{ij}\ge L$

Auf der Suche nach Personen, die sich in Raum-Zeit-Blöcken :
Raum in Raum- Blöcke (Stadtblöcke, Quadratkilometer, was auch immer) und die Zeit in Blöcke auf. Es besteht eine gute Chance, dass sich Menschen, die sich treffen, im selben Block treffen. Führen Sie also NN in jedem Block aus. Laufzeit und Fehlerraten hängen natürlich von den Blockgrößen und -formen ab (auch davon, was Sie parallelisieren / MapReduce können), aber Sie haben Parameter, mit denen Sie spielen können - Engineering, nicht weit offenes .N t i m e O ( N 2$Nspace$$Ntime$
$O( N^2 )$

Siehe auch:
Suche der nächsten Nachbarn nach sehr hochdimensionalen Daten auf datascience.stackexchange

pairwise.py :

Verwendet die Python Gensim-Bibliothek und den Heapq aus der Standardbibliothek, um mithilfe von TF-IDF und Kosinusabstand massiv schnelle und skalierbare paarweise Vergleiche zwischen einer beliebig großen Anzahl von Dokumenten durchzuführen.

$x$$feat_1:value_1, feat_{101}:value_{101}$$K$$K$$K$

Erstellen Sie für jede Funktion ein Wörterbuch mit den Indizes, die diese Funktion gemeinsam nutzen. Hoffentlich ist diese Zahl nicht zu groß (wenn Sie eine Funktion haben, die von allen Indizes gemeinsam genutzt wird, ist dieser Ansatz ruiniert, Sie können hier aufhören zu lesen).

$feat_1 : \{1,101,202\}, feat_2 : \{7,202\},feat_3 : \{202\}...feat_M:\{3,45,6\}$$feat_3$$O(NK)$

$x$$x$$x$$P$$O(N^2)$

$x$$y$$d(x,y)$$<x,y>$$x$$y$$O(K)$

$O(NPK)$$O(MN^2)$

Ich habe diese Methode angewendet, um eine KNN über einen großen Textsatz (Zug: 2 000 000 Zeilen, Test 35 000 Zeilen, Anzahl der Merkmale: 10 000, durchschnittliche Anzahl der Merkmale pro Element: 20) zu implementieren, der in etwa einer Stunde ausgeführt wurde. .

$k$$O(LN\log(N))$

L. Erotz, M. Steinbach und V. Kumar. "Ein neuer gemeinsamer Clustering-Algorithmus für den nächsten Nachbarn und seine Anwendungen." Vorträge des 1. Workshops zum Clustering hochdimensionaler Daten und ihrer Anwendungen, 2002.

$O(k \cdot \log{n} )$$k << n$

Vorausgesetzt, Ihr k ist 100 und Ihr n ist 1e6, sollte dies Ihnen eine ~ 1e4x-Geschwindigkeit im Vergleich zur klassischen FFT geben.

Wenn Sie eine weitere 20-fache Geschwindigkeit benötigen und ein Risikoträger sind, können Sie eine Untergruppe von Zeilen booten, anstatt alle Zeilen gegen die Domäne zu falten und nach dem Peak zu suchen.

Sie können Spalten auch vorfiltern, indem Sie Spalten entfernen, deren Summen unter 50 liegen, oder einen anderen Schwellenwert, der in der Größenordnung der Hälfte der Anzahl der Zeilen liegt, mit denen Sie übereinstimmen möchten. Zumindest sollten Sie Spalten aller Nullen und aller Einsen als nicht informativ entfernen. Gleiches gilt für Zeilen, die vollständig leer oder leer genug sind, oder für Zeilen, die so voll sind, dass sie irrelevant sind.

Aufgabe: Ich sollte hier ein Beispiel mit synthetischen Daten anführen und einige der Methoden vergleichen.

Ich bin gerade auf ein Papier gestoßen, das direkt relevant ist.

Randomisierte Algorithmen und NLP: Verwendung lokalitätssensitiver Hash-Funktionen für das Hochgeschwindigkeits-Nomen-Clustering (Ravichandran et al., 2005)

Es ist tatsächlich in https://github.com/soundcloud/cosine-lsh-join-spark implementiert, wo ich es gefunden habe.

Es basiert auf lokalitätssensitivem Hashing (bereits in anderen Antworten erwähnt). Nachdem die Merkmalsvektoren auf einen niedrigdimensionalen Raum reduziert wurden, verwendet es eine schnelle Hamming-Distanzverbindung, um die nächsten Nachbarn zu finden.