Wenn ich eine Menge von N Punkten im 2D-Raum habe, die durch die Vektoren X und Y ihrer Positionen definiert sind. Was ist ein effizienter Algorithmus, der
wird?Das Sortieren nach ihrem kürzesten nächsten Nachbarn und das Entfernen der Punkte mit den kleinsten Werten ergibt nicht die richtige Antwort, da Sie dann beide Punkte von nahen Paaren entfernen, während Sie möglicherweise nur einen der Punkte in diesen entfernen müssen Paare.
Für meinen Fall habe ich es normalerweise mit 1.000-10.000 Punkten zu tun, und ich kann 50-90% der Punkte entfernen.
Sie sollten nicht die gesamte Entfernungsmatrix speichern (oder berechnen) müssen: Eine Delaunay-Triangulation sollte effizient ( O(n log n) worst case) geben dir die nächsten Nachbarn deines Punktsatzes. Sie sollten es auch effizient aktualisieren können, wenn Sie Punkte löschen.
In den meisten Fällen enger Paare sollten Sie prüfen können, welches der beiden Paare am weitesten von seinen Nachbarn entfernt ist, wenn das andere Paar entfernt wird. Dies ist keine exakte Lösung; Besonders wenn Sie einen großen Anteil von Punkten entfernen, kann das Entfernen eines lokal optimalen Punktes die global optimale Lösung ausschließen. Außerdem sollten Sie in der Lage sein, sich mit Clustern aus 3 oder mehr lokal benachbarten Punkten zu befassen. Wenn Sie jedoch nur einen kleinen Teil der Punkte aus einer zufällig verteilten Menge entfernen, können beide Fälle relativ selten sein.
Es gibt möglicherweise einen besseren Weg (dh einen genauen und effizienten Algorithmus), um Ihr Problem zu lösen, aber die obigen Vorschläge sollten zu einem approximativen und / oder kombinatorischen Ansatz führen, der am besten funktioniert, wenn die Punkte gelöscht werden müssen spärlich verteilt.
Noam
Eine Methode besteht darin, Ihren 2D-Raum in N Partitionen aufzuteilen. Bestimmen Sie in jeder Partition eine durchschnittliche Position für jedes X, Y. Dann führen Sie den nächsten Nachbarn algorightm auf den gemittelten Punkten durch. Wiederholen Sie dann den nächsten Nachbar-Test für den vollständigen Punktsatz der übereinstimmenden Partitionen.
Hier ist der Haken. Je größer die Partitionen sind, desto weniger Punkte haben Sie, aber desto weniger genau. Je kleiner die Partitionen, desto genauer wird es sein, aber mit mehr Punkten zu verarbeiten.
Ich kann mir nichts anderes vorstellen als einen Brute-Force-Ansatz. Aber Sie können wahrscheinlich den Datensatz, den Sie betrachten, vor jeder Analyse deutlich verkürzen.
Also, was ich tun würde ist. Berechnen Sie zunächst für jeden Punkt die Entfernung zum nächsten Nachbarn. Nennen wir das P_in . Berechnen Sie dann die maximale Entfernung jedes Punktes zu seinen M nächsten Nachbarn, nennen Sie P_iM . Wenn P_in für einen beliebigen Punkt größer als P_iM ist, kann es von der Analyse ausgeschlossen werden. Wenn Sie einen Punkt haben, der 10 von einem anderen Punkt entfernt ist, und Sie einen anderen Punkt haben, der 9 von den nächsten M -Punkten entfernt ist, sollten Sie den ersten Punkt entfernen.
Abhängig von der Cluster-Ebene oder davon, wie groß M ist, kann dies Ihre Datenmenge erheblich reduzieren.
Tags und Links algorithm nearest-neighbor