Wie gruppieren Sie Breiten- und Längenpunkte, die nahe beieinander liegen?

Question

Ich habe eine Datenbank mit vom Benutzer übermittelten Breiten-/Längengradpunkten und versuche, 'nahe' Punkte zu gruppieren. "Schließen" ist relativ, aber für jetzt scheint es ~ 500 Fuß.

Zuerst schien es, als könnte ich nur nach Reihen gruppieren, die die gleiche Breite/Länge für die ersten 3 Dezimalstellen haben (ungefähr eine 300x300 Box, zu verstehen, dass sie sich ändert, wenn man sich vom Äquator wegbewegt).

Allerdings scheint diese Methode ziemlich fehlen. 'Nähe' kann nicht wesentlich anders sein als die Entfernung, die jede Dezimalstelle darstellt. Es wird nicht berücksichtigt, dass zwei Orte unterschiedliche Ziffern in der 3. (oder irgendeiner) Dezimalstelle haben können, aber immer noch innerhalb der Entfernung, die diese Stelle darstellt (33.1239 und 33.1240).

Ich habe auch über die Situation, wo Punkt A und Punkt C sind beide nah an Punkt B (aber nicht miteinander) - sollten sie zusammen gruppiert? Wenn dies der Fall ist, was passiert, wenn Punkt D "nahe" an Punkt C (und keine anderen Punkte) ist - sollte es ebenfalls gruppiert werden. Sicher muss ich das gewünschte Verhalten bestimmen, aber wie würde es umgesetzt werden?

Kann mir jemand in die richtige Richtung zeigen, wie das gemacht werden kann und welche verschiedenen Methoden/Ansätze verwendet werden können?

Ich fühle mich ein bisschen wie ich etwas offensichtliches vermisse.

Derzeit sind die Daten eine MySQL-Datenbank, die von einer PHP-Anwendung verwendet wird; Ich bin jedoch offen für andere Speichermethoden, wenn sie eine Schlüsselrolle dabei spielen. Hier.

Answer 1

Es gibt eine Reihe von Möglichkeiten, den Abstand zwischen zwei Punkten zu bestimmen, aber zum Zeichnen von Punkten in einem 2-D-Diagramm möchten Sie wahrscheinlich Euclidean distance. Wenn (x1, y1) Ihren ersten Punkt darstellt und (x2, y2) stellt Ihre zweite ist der Abstand

d = sqrt((x2-x1)^2 + (y2-y1)^2) 

In Bezug auf Gruppierung, können Sie irgendeine Art von 2-D verwendet werden soll bedeuten, zu bestimmen, wie „dicht“ Dinge miteinander sind. wenn Sie drei Punkte haben zum Beispiel, (x1, y1), (x2, y2), (x3, y3), können Sie das Zentrum dieser drei Punkte durch einfache Mittel finden:

x(mean) = (x1+x2+x3)/3 
y(mean) = (y1+y2+y3)/3 

Sie können dann sehen, wie nahe jeder zum Zentrum ist, ob es zu bestimmen, sollte Teil des "Clusters" sein.

---

Es gibt eine Reihe von Möglichkeiten, ein Cluster definieren, von denen alle eine Variante eines clustering algorithm verwenden. Ich bin jetzt in Eile und habe keine Zeit, um zusammenzufassen, aber überprüfen Sie den Link und die Algorithmen, und hoffentlich werden andere Leute mehr Details zur Verfügung stellen können. Viel Glück!

Answer 2

Wenn ich es angehen würde, würde ich mit einem Gitter beginnen. Setzen Sie jeden Punkt in ein Quadrat auf dem Gitter. Suchen Sie nach Gittern, die dicht bevölkert sind. Wenn die benachbarten Gitter nicht belegt sind, haben Sie eine anständige Gruppe.

Wenn Sie benachbarte dicht besetzte Gitter haben, können Sie immer einen Kreis in der Mitte jedes Gitters ablegen und für die Kreisfläche vs (Anzahl der Punkte im Kreis * etwas abstimmbares Gewicht) optimieren. Nicht perfekt, aber einfach. Bessere Gruppierungen sind viel kompliziertere Optimierungsprobleme.

Answer 3

Vielleicht Overkill, aber es scheint mir ein clustering problem: Abstand measure wird bestimmen, wie die Ähnlichkeit zweier Elemente berechnet wird. Wenn Sie eine weniger naive Lösung Data Mining: Practical Machine Learning Tools and Techniques versuchen, und verwenden Sie Weka oder Orange

Answer 4

Verwenden etwas ähnliches wie die Methode, die Sie in Ihrer Frage skizzierten einen ungefähren Satz von Ergebnissen zu erhalten, dann whittle, die indem richtige Berechnungen ungefähren festgelegt. Wenn Sie Ihre Rastergröße (d. H. Wie stark Sie Ihre Koordinaten abrunden) richtig auswählen, können Sie zumindest hoffen, den Arbeitsaufwand auf ein akzeptables Maß zu reduzieren, obwohl Sie die Rastergröße verwalten müssen.

Zum Beispiel die Earthdistance Erweiterung zu PostgreSQL funktioniert durch Umwandlung von Lat/langen Paaren zu kartesischen Koordinaten (x, y, z), Modellierung der Erde als eine einheitliche Kugel. PostgreSQL verfügt über ein ausgefeiltes Indizierungssystem, das es ermöglicht, diese Koordinaten oder Boxen um sie herum in R-Bäume zu indizieren, aber Sie können etwas zusammenschlagen, das ohne das noch nützlich ist.

Wenn Sie Ihre (x, y, z) triple und runden off - dh mit einem Faktor multiplizieren und auf ganze Zahl abschneiden - haben Sie dann drei ganze Zahlen, die Sie verketten können, um einen "box name" zu erzeugen, der a identifiziert Feld in Ihrem "Raster", in dem sich der Punkt befindet.

Wenn Sie nach allen Punkten innerhalb von X km eines Zielpunkts suchen möchten, generieren Sie alle "Feldnamen" um diesen Punkt herum (nach der Konvertierung Ihres Zielpunkt auf ein (x, y, z) Triple, das ist einfach) und eliminieren alle Felder, die nicht die Erdoberfläche schneiden (Trick, aber die Verwendung der x^2+y^2+z^2=R^2 Formel an jeder Ecke wird Ihnen sagen) Sie am Ende mit einer Liste von Kästchen Zielpunkte können Sie auch nur nach allen Punkten suchen, die zu einem dieser Kästchen passen, wodurch Sie auch etwas mehr zurückgeben Punkte. Als letzte Stufe müssen Sie die tatsächliche Entfernung zu Ihrem Zielpunkt berechnen und einige eliminieren (dies kann wiederum beschleunigt werden, indem Sie in kartesischen Koordinaten arbeiten und den Zielradius des Großkreises in Sekantenabstand umrechnen).

Beim Herumspielen müssen Sie nicht zu viele Boxen durchsuchen, aber gleichzeitig nicht zu viele Extrapunkte einbringen. Ich habe es nützlich gefunden, jeden Punkt auf mehreren verschiedenen Gittern zu indizieren (z. B. Auflösungen von 1Km, 5Km, 25Km, 125Km usw.). Idealerweise möchten Sie nur eine Box suchen. Denken Sie daran, dass sie auf mindestens 27 erweitert wird, sobald Ihr Zielradius die Gittergröße überschreitet.

Ich habe diese Technik verwendet, um einen räumlichen Index mit Lucene zu erstellen, anstatt Berechnungen in SQL-Datenbanken durchzuführen. Es funktioniert, obwohl es ein paar Tricks gibt, um es einzurichten, und die Indizes brauchen eine Weile, um zu generieren und sind ziemlich groß. Einen R-Baum zu verwenden, um alle Koordinaten zu halten, ist ein viel netterer Ansatz, würde aber mehr benutzerdefiniertes Kodieren erfordern - diese Technik erfordert im Grunde nur eine schnelle Hash-Tabellen-Suche (würde also wahrscheinlich mit allen NoSQL-Datenbanken funktionieren, die das sind Wut in diesen Tagen, und sollte auch in einer SQL-Datenbank verwendbar sein).

Answer 5

Wenn Sie Breiten- und Längengrad berücksichtigen, müssen in Echtzeitdaten mehrere Faktoren berücksichtigt werden: Hindernisse wie Flüsse und Seen und Einrichtungen wie Brücken und Tunnel. Sie können sie nicht einfach gruppieren; Wenn Sie den einfachen Algorithmus als k verwenden, können Sie sie nicht gruppieren. Ich denke, Sie sollten für die räumlichen Clustering-Methoden als Partitionierung CLARANS-Methode gehen.