Nearest Neighbour Problem

Wissenschaft Informatik
#1

Hallo,

ich habe für folgendes Problem eine Lösung überlegt und möchte gerne wissen, ob es nicht noch irgendwie besser geht.

Ich habe eine große Menge von Punkten (ca. 10^5 - 10^6) und benötige nach und nach die nearest neighbours von den Punkten. Ich bezeichne das jetzt mal Englisch, damit es gleich nicht verwirrend wird.
Also zunächst brauche ich den nearest neighbour von irgendeinem Punkt, dann von einem anderen und so weiter. Irgendwann brauche ich dann evtl. auch den „nächsten“ nearest neighbour (also den, der am 2. nächsten dran ist) usw…
Ich kann vorher nicht sagen, wie viele ich brauche (also nicht k-nearest neighbours) und auch nicht wann. Es sind auch zu viele Punkte um für alle Punkte alle NN auszurechnen.

Ich löse das ganze momentan durch Suche in einem 2D-Tree. Dabei wird der letzte nearest neighbour als Schranke genutzt, um beim Suchen unnötige Teilbäume zu sparen. Ist schon nicht schlecht denke ich, aber diese ganze Sucherei nimmt ungefähr 30% der Gesamtlaufzeit ein, so daß sich Verbesserungen da noch richtig lohnen könnten.

Es gibt ja z.B. Voronoi-Diagramme, um die nearest neighbours schnell zu finden. Kann man damit auch die jeweils nächsten nearest neighbours finden?

Bin für jeden Tipp dankbar,

Hendrik.

#2

Auch hallo.

ich habe für folgendes Problem eine Lösung überlegt und möchte
gerne wissen, ob es nicht noch irgendwie besser geht.

Schau’n mer mal, wie der Hesse so sagt :smile:

Ich habe eine große Menge von Punkten (ca. 10^5 - 10^6) und
benötige nach und nach die nearest neighbours von den Punkten.
Ich bezeichne das jetzt mal Englisch, damit es gleich nicht
verwirrend wird.
Also zunächst brauche ich den nearest neighbour von
irgendeinem Punkt, dann von einem anderen und so weiter.
Irgendwann brauche ich dann evtl. auch den „nächsten“ nearest
neighbour (also den, der am 2. nächsten dran ist) usw…
Ich kann vorher nicht sagen, wie viele ich brauche (also nicht
k-nearest neighbours) und auch nicht wann. Es sind auch zu
viele Punkte um für alle Punkte alle NN auszurechnen.

Es gibt ja z.B. Voronoi-Diagramme, um die nearest neighbours
schnell zu finden. Kann man damit auch die jeweils nächsten
nearest neighbours finden?

Das fällt mehr in ‚Mustererkennung‘ und ‚Computergrafik‘. Siehe auch http://www.informatik-forum.at/archive/index.php/t-3…
http://de.wikipedia.org/wiki/Voronoi
Aber die nächsten NN zu finden sollte damit möglich sein. Vor allem, weil ein Zielpunkt als NN eines anderen Punkts zum Ausgangspunkt für die Suche nach dem nächsten NN wird.

HTH
mfg M.L. (gerade keine gute Literatur zu theoretischer Informatik greifbar…)

#3

Spontan würde ich vorschlagen, einen der polylogarithmischen dynamischen nearest Neighbor-Algorithmen
zu nehmen (siehe z.B. http://citeseer.ist.psu.edu/167339.html) und um den
zweitnächsten Punkt zu berechnen den nächsten einfach vorübergehend zu entfernen
(entsprechend um den k’t nächsten zu finden die k-1 anderen löschen und nach dem
Finden wieder einfügen). Je nach Anwendung kannst Du ja evtl. sogar auf das Wiedereinfügen verzichten oder der Algorithmus läßt sich so modifizieren, daß
man das Löschen gar nicht explizit vornehmen muß.

MfG
ML

#4

Ja, Voronoi-Diagramme sind der korrekte Ansatz:
Das „normale“ Voronoi-Diagramm erster Ordnung läßt sich in Zeit O(n*log(n)) konstruieren.
Zu prüfen sind dann jeweils nur die Nachbarpunkte, deren Voronoiregion eine gemeinsame Kante zu der Region des aktuellen Punktes haben.

Um „k-nearest neighbours“ zu finden, wird ein Voronoi-Diagramm k-ter Ordnung benötigt.

Zum Spielen gibts ein Applet unter
http://www.msi.umn.edu/~schaudt/voronoi/voronoi.html
(der hier verwendete algorithmus is allerdings nicht die optimal schnellste lösung)

grüße,
daniel

ich habe für folgendes Problem eine Lösung überlegt und möchte
gerne wissen, ob es nicht noch irgendwie besser geht.

Ich habe eine große Menge von Punkten (ca. 10^5 - 10^6) und
benötige nach und nach die nearest neighbours von den Punkten.
Ich bezeichne das jetzt mal Englisch, damit es gleich nicht
verwirrend wird.
Also zunächst brauche ich den nearest neighbour von
irgendeinem Punkt, dann von einem anderen und so weiter.
Irgendwann brauche ich dann evtl. auch den „nächsten“ nearest
neighbour (also den, der am 2. nächsten dran ist) usw…
Ich kann vorher nicht sagen, wie viele ich brauche (also nicht
k-nearest neighbours) und auch nicht wann. Es sind auch zu
viele Punkte um für alle Punkte alle NN auszurechnen.

Ich löse das ganze momentan durch Suche in einem 2D-Tree.
Dabei wird der letzte nearest neighbour als Schranke genutzt,
um beim Suchen unnötige Teilbäume zu sparen. Ist schon nicht
schlecht denke ich, aber diese ganze Sucherei nimmt ungefähr
30% der Gesamtlaufzeit ein, so daß sich Verbesserungen da noch
richtig lohnen könnten.

Es gibt ja z.B. Voronoi-Diagramme, um die nearest neighbours
schnell zu finden. Kann man damit auch die jeweils nächsten
nearest neighbours finden?

Bin für jeden Tipp dankbar,

Hendrik.

–
!/
@^@
---------oOO-(_)-OOo------------------------------------
Daniel Jung [email protected]
Linux-User #118180 http://www.blumenladenmetrik.de