Geeignete Ähnlichkeitsmetriken für mehrere Sätze von 2D -Koordinaten

Question

Ich habe eine Sammlung von 2D-Koordinatensätzen (auf der Skala von 100K-500K-Punkten in jedem Satz) und suche die effizienteste Möglichkeit, die Ähnlichkeit von 1 Set mit dem anderen zu messen. Ich kenne die üblichen: Cosinus, Jaccard/Tanimoto usw. Ich hoffe jedoch auf einige Vorschläge für alle schnellen/effizienten, um Ähnlichkeit zu messen, insbesondere solche, die sich nach Ähnlichkeit gruppieren können.

Bearbeiten 1: Das Bild zeigt, was ich tun muss. Ich muss alle Roten, Blues und Grünen durch ihre Form/Orientatoin usw. gruppieren.

ALT Text http://img402.imageshack.us/img402/8121/curves.png

Answer 1

Es scheint, dass der erste Schritt jeder Lösung darin besteht, den Schwerpunkt oder einen anderen Referenzpunkt jeder Form zu finden, damit sie unabhängig von der absoluten Position verglichen werden können.

Ein Algorithmus, der mir in den Sinn kommt, wäre, an dem Punkt, der dem Schwerpunkt am nächsten liegt, zu seinen nächsten Nachbarn zu gehen. Vergleichen Sie die Offsets dieser Nachbarn (vom Schwerpunkt) zwischen den verglichenen Sätzen. Gehen Sie weiter zu den nächsten nearsten Nachbarn des Zentroids oder zu den nächsten, die nicht umgegangenen Nachbarn der zuvor verglichenen Nachbarn vergleichbar sind, und verfolgen Sie den aggregierten Unterschied (vielleicht RMS?) Zwischen den beiden Formen. Berechnen Sie bei jedem Schritt dieses Prozesses den Rotationsversatz, der die beiden Formen in die engste Ausrichtung bringen [und ob sich die Spiegelung auch auswirkt?]. Wenn Sie fertig sind, haben Sie drei Werte für jedes Setspaar, einschließlich ihrer direkten Ähnlichkeit, des relativen Rotationsversatzes (meistens nur nützlich, wenn sie nach der Rotation mit enger Übereinstimmung übereinstimmen) und deren Ähnlichkeit nach der Rotation.

Answer 2

Versuchen Sie den K-Means-Algorithmus. Es berechnete dynamisch den Schwerpunkt jedes Clusters und berechnet die Entfernung zu allen Zeigern und assoziiert sie dem nächsten Cluster.

Answer 3

Da Ihr Clustering auf einer Metrik von Neiigkeit zu Form basiert, benötigen Sie möglicherweise eine Form einer verbundenen Komponentenkennzeichnung. Union-Find kann Ihnen einen schnellen grundlegenden Set-Primitiv geben.

Beginnen Sie nur für Gewerkschaftsbekämpfung in einem anderen Satz und fusionieren Sie sie, wenn sie ein Kriterium der Nähe erfüllen, das von der lokalen Kolinearität beeinflusst wird, da dies Ihnen wichtig erscheint. Verschmelzen Sie dann weiter, bis Sie einen Über-Schwellenwert-Zustand für die schwierige Verschmelzung übergeben. Wenn Sie es wie ein Linienbau behandeln (nur die Dinge an ihren Enden verbinden), werden einige Datenstrukturen einfacher. Sind alle Ihre Cluster offene Linien und Kurven? Keine geschlossenen Kurven wie Kreise?

Die Übergangslinien sind schwieriger, um richtig zu werden, Sie müssen entweder einen Weg finden, dann spalten oder Sie haben Ihre Zusammenführungskriterien so festgelegt, dass Sie die Kolinearität extrem bevorzugen.