Ich habe eine Datenbank mit 500.000 Punkten in einem 100-dimensionalen Raum, und ich möchte die nächsten 2 Punkte finden. Wie mache ich es?Wie findet man die nächsten 2 Punkte in einem 100-dimensionalen Raum mit 500.000 Punkten?
Update: Space ist euklidisch, Sorry. Und danke für alle Antworten. Übrigens sind das keine Hausaufgaben.
Sie könnten versuchen, die ANN library, aber das gibt nur zuverlässige Ergebnisse bis zu 20 Dimensionen.
Danke. ANN ist genau das, wonach ich gesucht habe. Hoffentlich kann es alles im RAM halten. – louzer
ANN ist einfach zu verwenden, aber es sollte angemerkt werden, dass es eine ungefähre Implementierung des nächsten Nachbarn ist, also ist nicht garantiert, dass es korrekt ist. –
Es gibt ein Kapitel in Introduction to Algorithms, das dem Finden von zwei nächsten Punkten im zweidimensionalen Raum in O (n * logn) Zeit gewidmet ist. Sie können es auf google books überprüfen. In der Tat, ich schlage es für jeden vor, da die Art und Weise, wie man die Teile-und-herrsche-Technik auf dieses Problem anwendet, sehr einfach, elegant und beeindruckend ist.
Obwohl es nicht direkt auf Ihr Problem erweitert werden kann (als Konstante 7 würde durch 2^101 - 1 ersetzt werden), sollte es für die meisten Datensätze in Ordnung sein. Also, wenn Sie eine relativ zufällige Eingabe haben, gibt es Ihnen O(n*logn*m) Komplexität wo n ist die Anzahl der Punkte und m ist die Anzahl der Dimensionen.
bearbeiten
Das ist alles unter der Annahme, dass Sie euklidischen Raum haben. Das heißt, die Länge des Vektors v ist sqrt(v0^2 + v1^2 + v2^2 + ...). Wenn Sie jedoch Metrik wählen können, könnte es andere Optionen geben, um den Algorithmus zu optimieren.
Führen Sie PCA auf Ihren Daten aus, um Vektoren von 100 Dimensionen in etwa 20 Dimensionen zu konvertieren. Erstellen Sie dann einen K-Nearest Neighbor-Baum (KD-Tree) und ermitteln Sie anhand der euklidischen Entfernung die nächsten 2 Nachbarn.
Im Allgemeinen wenn nein. Da die Dimensionen sehr groß sind, müssen Sie entweder einen Brute-Force-Ansatz (parallel + verteilt/Karte reduzieren) oder einen clusterbasierten Ansatz verwenden.
Verwenden Sie einen kd-Baum. Sie betrachten ein Problem mit dem nächsten Nachbarn und es gibt hoch optimierte Datenstrukturen für die Behandlung dieser genauen Klasse von Problemen.
http://en.wikipedia.org/wiki/Kd-tree
P. S. Spaß Problem!
Dies ist die richtige Antwort. –
Verwenden Sie die Datenstruktur, die als KD-TREE bezeichnet wird. Sie müssen viel Speicher reservieren, aber Sie können auf der Grundlage Ihrer Daten eine oder zwei Optimierungen entdecken.
http://en.wikipedia.org/wiki/Kd-tree.
Mein Freund arbeitete vor Jahren an seiner Doktorarbeit, als er auf ein ähnliches Problem stieß. Seine Arbeit lag in der Größenordnung von 1 Mio. Punkten in 10 Dimensionen. Wir haben eine kd-tree-Bibliothek erstellt, um sie zu lösen. Wir sind möglicherweise in der Lage, den Code auszugraben, wenn Sie uns offline kontaktieren möchten.
Hier ist sein veröffentlichtes Papier: http://www.elec.qmul.ac.uk/people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf
kdtrees machen es leicht, einen nächsten Nachbarn zu einem gegebenen Punkt in O (log n) Zeit zu finden, wie ich mich erinnere. Gibt es eine Optimierung, um das nächstgelegene Punktepaar in weniger als O (n log n) zu finden? – rampion
-1, auch nach Wikipedia kD-Baum sind effizient, wenn N >> 2^k (wo k ist Dimensionen und N Anzahl der Punkte; in diesem Fall 2^100 >> 5e5 und die Antwort ist völlig irreführend) – Unreason
10d ist nicht 100d. Selbst wenn die Datenpunkte ungefähr in einer 10-d-Ebene in 100d liegen, kann kd-tree nicht funktionieren (imho): denke an einen kd-Baum 100 s tief. – denis
Ist es ein metrischer Raum? – Seth
Aus Interesse, wo hast du einen 100-dimensionalen Raum bekommen? –
die Frage fehlt Klarheit. Ist das eine mathematische Frage? – Sarmaad