Clustering von Geostandortkoordinaten (Lat, lange Paare)

Was ist der richtige Ansatz und Clustering-Algorithmus für das Geolocation-Clustering?

Ich verwende den folgenden Code, um Geolocation-Koordinaten zu clustern:

import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.vq import kmeans2, whiten

coordinates= np.array([
           [lat, long],
           [lat, long],
            ...
           [lat, long]
           ])
x, y = kmeans2(whiten(coordinates), 3, iter = 20)  
plt.scatter(coordinates[:,0], coordinates[:,1], c=y);
plt.show()

Ist es richtig, K-means für das Geolocation-Clustering zu verwenden, da es die euklidische Distanz und nicht die Haversine-Formel als Distanzfunktion verwendet?

K-means sollte in diesem Fall stimmen. Da k-means versucht, eine Gruppierung nur anhand des euklidischen Abstands zwischen Objekten vorzunehmen, erhalten Sie Cluster von Standorten, die nahe beieinander liegen.

Um die optimale Anzahl von Clustern zu finden, können Sie versuchen, ein 'Ellbogen'-Diagramm der Summe der Quadratabstände innerhalb der Gruppe zu erstellen. Dies kann hilfreich sein ( http://nbviewer.ipython.org/github/nborwankar/LearnDataScience/blob/master/notebooks/D3.%20K-Means%20Clustering%20Analysis.ipynb )

K-means ist hier nicht der am besten geeignete Algorithmus.

Der Grund dafür ist, dass k-means so ausgelegt ist, dass die Varianz minimiert wird . Dies erscheint natürlich aus statistischer und signaltechnischer Sicht, aber Ihre Daten sind nicht "linear".

Da Ihre Daten im Längen- und Breitengradformat vorliegen, sollten Sie einen Algorithmus verwenden, der beliebige Entfernungsfunktionen, insbesondere geodätische Entfernungsfunktionen, verarbeiten kann. Hierarchisches Clustering, PAM, CLARA und DBSCAN sind beliebte Beispiele dafür.

https://www.youtube.com/watch?v=QsGOoWdqaT8 empfiehlt OPTICS-Clustering.

Die Probleme von k-means sind leicht zu erkennen, wenn Sie Punkte in der Nähe von + -180 Grad betrachten. Selbst wenn Sie k-means gehackt haben, um die Haversine-Distanz zu verwenden, wird das Ergebnis im Aktualisierungsschritt, wenn es den Mittelwert neu berechnet , schlecht geschraubt. Das Schlimmste ist, dass k-means niemals konvergieren wird!

GPS-Koordinaten können direkt in eine Geohash umgewandelt werden . Geohash unterteilt die Erde in "Eimer" unterschiedlicher Größe, basierend auf der Anzahl der Ziffern (kurze Geohash-Codes erzeugen große Flächen und längere Codes für kleinere Flächen). Geohash ist eine einstellbare Präzisionsclustermethode.

Ich bin mit meiner Antwort wahrscheinlich sehr spät dran, aber wenn Sie sich immer noch mit Geo-Clustering beschäftigen, finden Sie diese Studie möglicherweise interessant. Es geht um den Vergleich zweier ziemlich unterschiedlicher Ansätze zur Klassifizierung geografischer Daten: K-bedeutet Clustering und Latent Class Growth Modeling.

Eines der Bilder aus der Studie:

Die Autoren kamen zu dem Schluss, dass die Endergebnisse insgesamt ähnlich waren und dass es einige Aspekte gab, bei denen LCGM K-means übertraf.

Sie können dafür HDBSCAN verwenden . Das Python-Paket unterstützt Haversine-Entfernungen, die die Entfernungen zwischen Lat / Lon-Punkten korrekt berechnen.

Wie in den Dokumenten erwähnt , müssen Sie zuerst Ihre Punkte in Bogenmaß umrechnen, damit dies funktioniert. Der folgende Pseudocode sollte den Trick machen:

points = np.array([[lat1, lon1], [lat2, lon2], ...])
rads = np.radians(points)
clusterer = hdbscan.HDBSCAN(min_cluster_size=N, metric='haversine')
cluster_labels = clusterer.fit_predict(points)

Der k-means-Algorithmus zum Clustering der Standorte ist keine gute Idee. Ihre Standorte können über die ganze Welt verteilt sein und die Anzahl der Cluster kann nicht von Ihnen vorhergesagt werden. Wenn Sie den Cluster auf 1 setzen, werden die Standorte zu einem einzelnen Cluster gruppiert. Ich benutze Hierarchical Clustering für das gleiche.

Java Apache commons-math macht das ziemlich einfach.

https://commons.apache.org/proper/commons-math/javadocs/api-3.1/org/apache/commons/math3/stat/clustering/DBSCANClusterer.html

List<Cluster<T>>    cluster(Collection<T> points) 

Entscheiden Sie sich für Kmeans-Clustering, da HBScan ewig dauern wird. Ich habe es für eines der Projekte ausprobiert und endete mit Kmeans mit den gewünschten Ergebnissen.