Effiziente Nächste-Nachbarn-Suche nach dünn besetzten Matrizen

Ich habe ein großes Datenkorpus (Text), das ich in eine spärliche Term-Dokument-Matrix umgewandelt habe (ich verwende scipy.sparse.csr.csr_matrix, um Sparse-Matrix zu speichern). Ich möchte für jedes Dokument die nächsten Nachbarn finden. Ich hatte gehofft, dass NearestNeighbor Routine in Python scikit-learn Bibliothek (sklearn.neighbors.NearestNeighbor, um genau zu sein) würde mein Problem lösen, aber effiziente Algorithmen, die Raum Partitionierung Datenstrukturen wie KD trees oder Ball trees arbeiten nicht mit dünn besetzten Matrizen. Nur der Brute-Force-Algorithmus arbeitet mit spärlichen Matrizen (was in meinem Fall unmöglich ist, da ich mit einem großen Korpus zu tun habe).Effiziente Nächste-Nachbarn-Suche nach dünn besetzten Matrizen

Gibt es eine effiziente Implementierung der Nearest Neighbor Suche nach dünn besetzten Matrizen (in Python oder in einer anderen Sprache)?

Danke.

Quelle

2013-08-10 abhinavkulkarni

Sie können versuchen, Ihre hochdimensionalen sparse Daten mit TruncatedSVD zu niedrigdimensionalen dichten Daten zu transformieren und dann einen Ball-Tree zu erstellen.

Quelle

2013-08-13 05:45:18 Mathieu

Sind Sie sicher, dass sich ein Ball-Tree gut mit der SVD-Ausgabe verhält? Normalerweise möchten Sie, dass SVD einige 100-200 Dimensionen beibehält ... –

Späte Antwort: Haben Sie einen Blick auf Locality-Sensitive-Hashing

Unterstützung in Scikit-Learn wurde here und here vorgeschlagen.

Quelle

2014-10-14 09:11:42 Unapiedra

Ich kann bestätigen, dass LSHForest funktioniert und sparsamer Matrix-Input auch im Jahr 2016 unterstützt wird, was großartig ist. Nachteil ist die langsame Entwicklung dieser Implementierung und es könnte eine Version 2 nötig sein, obwohl die Ausgabe von Version 1 zumindest korrekt ist. Für eine bessere Geschwindigkeit versuche ich BallTree und verwende zuerst SVD, um die Dimensionalität zu reduzieren, wie Mathieu vorgeschlagen hat, um die dichte Matrix-Anforderung von BallTree zu unterstützen. SVD könnte mir auch helfen, latente Merkmale zu finden, um das Clustering mit DBSCAN zu unterstützen. Schließlich ist die Kosinusabstandsmetrik die einzige Distanzmetrik von LSHForest, die für viele Daten, aber nicht für alle Daten gut ist. –

Effiziente Nächste-Nachbarn-Suche nach dünn besetzten Matrizen

Antwort

Verwandte Themen