Wo finde ich eine serielle C/C++ - Implementierung des k-Nearest-Neighbor-Algorithmus?
Kennen Sie irgendeine Bibliothek, die das hat?
Ich habe openCV gefunden, aber die Implementierung ist bereits parallel.
Ich möchte von einer seriellen Implementierung starten und es mit Pthreads OpenMP und MPI parallelisieren.
K-nächster Nachbar C/C++ - Implementierung
Danke,
Alex
Wie wäre es mit ANN? http://www.cs.umd.edu/~mount/ANN/. Ich habe einmal die kdtree-Implementierung verwendet, aber es gibt andere Optionen.
Zitat von der Website: "ANN ist eine in C++ geschriebene Bibliothek, die Datenstrukturen und Algorithmen sowohl für die exakte als auch die annähernde Nächste-Nachbarn-Suche in beliebig hohen Dimensionen unterstützt."
Danke, ANN ist ein guter Ausgangspunkt. – alexsardan
Der einfachste Weg, dies zu realisieren, ist eine Schleife durch alle Elemente und speichern K am nächsten. (Vergleich nur). Die Komplexität ist O(n), die nicht so gut ist, aber keine Vorverarbeitung benötigt wird. Also jetzt kommt es wirklich auf deine Bewerbung an. Sie sollten einen räumlichen Index zum Partitionierungsbereich verwenden, in dem Sie nach knn suchen. Für einige Anwendungen ist die gitterbasierte räumliche Struktur in Ordnung (teilen Sie einfach Ihre Welt in einen festen Block und suchen Sie erst innerhalb der nächsten Blöcke). Das ist gut, wenn Ihre Entitäten gleichmäßig verteilt sind. Besser ist eine hierarchische Struktur wie kd-Baum zu verwenden ... Es hängt wirklich alles auf, was Sie
für weitere Informationen mit Pseudo-Code Blick in diesen Präsentationen benötigen:
Danke für die Antwort. Eigentlich muss ich von einer bereits implementierten Version ausgehen. – alexsardan
Ich schrieb eine C++ implementation for a KD-tree mit Nearest Neighbor Suche. Sie können es problemlos für K-nächste Nachbarn erweitern, indem Sie eine Prioritätswarteschlange hinzufügen.
Update: I Unterstützung für k-nearest-neighbor-Suche in N Dimensionen
Danke, aber keine Lizenzinformationen sind zu sehen. –
Für welche Probleme dieses Algorithmus anwenden werden? KNN ist wirklich einfach und Sie können versuchen, Ihren eigenen Ansatz zu implementieren. –