High Dimension Nächster Nachbar Suche und Lokalität Empfindlichkeit Hashing

Question

Hier ist das Hauptproblem. Ich habe eine sehr große Datenbank (25.000 oder so) von 48 dimensionalen Vektoren, die jeweils mit Werten zwischen 0 und 255 bevölkert sind. Die Details sind nicht so wichtig, aber ich denke, es könnte helfen, Kontext zu geben.

Ich brauche keinen nächsten Nachbarn, so dass ungefähre Nachbarsuchen, die innerhalb eines Grads an Genauigkeit liegen, akzeptabel sind. Ich habe mit Locality Sensitivity Hashing gespielt, aber ich bin sehr, sehr verloren.

Ich habe eine Hash-Funktion geschrieben, wie im Artikel unter "Stable Distributions" beschrieben, so gut ich kann. Hier ist der Code.

Die Hashing-Funktion "funktioniert" zumindest einige. Wenn ich eine Liste von Punkten nach Hash-Wert anordne und den durchschnittlichen Abstand zwischen einem Punkt und seinem Nachbarn in der Liste berechne, beträgt die durchschnittliche Entfernung etwa 400, verglichen mit einer durchschnittlichen Entfernung von etwa 530 für zwei zufällig ausgewählte Punkte.

Meine größten Fragen sind diese.

A: Irgendwelche Vorschläge, wo ich mehr darüber lesen kann. Meine Suche hat nicht viele Ergebnisse hervorgebracht.

B: Die Methode schlägt vor, dass sie einen ganzzahligen Wert ausgibt (was meins nicht tut). Und dann sollten Sie versuchen, Übereinstimmungen für diesen ganzzahligen Wert zu finden, und eine Übereinstimmung bezeichnet einen wahrscheinlichsten nächsten Nachbarn. Ich verstehe, dass ich einige Tabellen mit Hash-Werten für alle meine Punkte berechnen und dann diese Tabellen auf Hash-Übereinstimmungen überprüfen soll, aber die Werte, die ich zurückgebe, scheinen nicht gut genug zu sein, damit ich enden kann passt überhaupt. Weitere Tests sind von meiner Seite erforderlich.

C: Anweisungen zum Erstellen von Hash-Funktionen basierend auf den anderen Hash-Methoden?

Answer 1

Maby dies ist ein wenig off Thema, aber Sie können PCA http://en.wikipedia.org/wiki/Principal_component_analysis verwenden, um die Dimensionalität des Datasets zu reduzieren. Es sollte genügend PCA-Module geben, die für numPy ausgelegt sind (zum Beispiel: http://folk.uio.no/henninri/pca_module/). Die Methode ist ziemlich einfach und mit einem gebrauchsfertigen Modul wird es ein Kinderspiel.

Grundsätzlich ist es die Anzahl der Dimensionen reduzieren (Sie können die gewünschte Anzahl angeben) durch Maximierung der Varianz innerhalb der angegebenen Anzahl von Dimensionen.

Answer 2

Hier sind zwei Antworten:

B: Die Wikipedia-Seite zeigt an, dass math.floor() sollte auf hashVal verwendet werden: dies ist, wie Sie ganze Zahlen erhalten.

C: Wenn Sie die Hamming-Methode verwenden möchten, können Sie dies ganz einfach implementieren: Jede Hamming-Hash-Funktion wird einfach durch eine Koordinate (zwischen 0 und 47) und eine Bitnummer (zwischen 0 und 7) definiert . Sie können den Wert einer ganzen Zahl in einem gegebenen Bit b mit bekommen:

bool(i & 2**b)