Regroupement des coordonnées géographiques (lat, paires longues)

51

Quelle est la bonne approche et le bon algorithme de clustering pour le clustering de géolocalisation?

J'utilise le code suivant pour regrouper les coordonnées de géolocalisation:

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()

Est-il juste d'utiliser K-means pour le clustering de géolocalisation, puisqu'il utilise la distance euclidienne, et non la formule de Haversine en tant que fonction de distance?

rok
la source
Vous pouvez également consulter cette question similaire: datascience.stackexchange.com/questions/10063/…
VividD
Je pense que la faisabilité de k-means dépend de la localisation de vos données. Si vos données sont réparties dans le monde entier, cela ne fonctionnera pas, car la distance n'est pas euclidienne, comme d'autres utilisateurs l'ont déjà dit. Mais si vos données sont plus locales, k-means serait suffisant, car la géométrie est localement euclidienne.
Juan Ignacio Gil

Réponses:

7

K-means devrait avoir raison dans ce cas. Puisque k-means essaie de regrouper uniquement sur la base de la distance euclidienne entre les objets, vous récupérerez des groupes d’emplacements proches les uns des autres.

Pour trouver le nombre optimal de grappes, vous pouvez créer un graphe de type «coude» représentant la somme de la distance au sein d'un groupe. Cela peut être utile ( http://nbviewer.ipython.org/github/nborwankar/LearnDataScience/blob/master/notebooks/D3.%20K-Means%20Clustering%20Analysis.ipynb )

mike1886
la source
3
Comment les points proches les uns des autres sur le point de bouclage sont-ils gérés?
casperOne
1
Vous devez trouver un algorithme prenant une matrice de distance pré-calculée ou vous permettant de fournir une fonction de distance qu'il peut appeler lorsqu'il doit calculer des distances. Sinon, ça ne marchera pas.
Spacedman
L'intrigue des coudes peut ne pas vous aider du tout, car il se peut qu'il n'y ait pas de coude. Veillez également à essayer plusieurs exécutions de k-means avec le même numéro de cluster, car vous pourriez obtenir des résultats différents.
Sauterelle
C'est une mauvaise idée car tous les points seront regroupés, ce qui est rarement une bonne idée pour la cartographie.
Richard
52

K-means n'est pas l'algorithme le plus approprié ici.

La raison en est que k-means est conçu pour minimiser la variance . Ceci apparaît bien sûr d'un point de vue statistique et du traitement du signal, mais vos données ne sont pas "linéaires".

Étant donné que vos données sont au format latitude et longitude, vous devez utiliser un algorithme capable de gérer des fonctions de distance arbitraires , en particulier des fonctions de distance géodésiques. Le clustering hiérarchique, PAM, CLARA et DBSCAN en est un exemple courant.

https://www.youtube.com/watch?v=QsGOoWdqaT8 recommande la mise en cluster OPTICS.

Les problèmes de k-moyennes sont faciles à voir lorsque vous considérez des points proches du cercle enveloppant + -180 degrés. Même si vous piraté k-means utiliser la distance Haversine, dans l'étape de mise à jour quand il recalcule la moyenne sera mal vissé le résultat. Dans le pire des cas, k-means ne convergera jamais!

Anony-Mousse
la source
Pouvez-vous suggérer une méthode de classification plus appropriée pour les données de géolocalisation?
Alex Spurling
Avez-vous remarqué le troisième paragraphe?
Anony-Mousse
7

Les coordonnées GPS peuvent être converties directement en geohash . Geohash divise la Terre en "compartiments" de taille différente en fonction du nombre de chiffres (des codes Geohash courts créent de grandes zones et des codes plus longs pour des zones plus petites). Geohash est une méthode de clustering de précision ajustable.

Brian Spiering
la source
Cela semble souffrir du même problème enveloppant à 180 degrés que K-Means, selon l'article de Wikipédia lié à la réponse.
Norman H
Oui! Les codes plus sont bien meilleurs. Codes
Brian Spiering
Un des avantages de cette solution est que tant que vous calculez le geohash une fois, les opérations de comparaison répétées iront beaucoup plus rapidement.
Norman H
Geohash aura des problèmes avec les cas de bord de seau - deux points très proches seront placés dans des seaux différents en fonction des bords arbitraires de chaque seau.
Dan G
5

Je suis probablement très en retard avec ma réponse, mais si vous traitez toujours avec le regroupement géographique, vous trouverez peut-être cette étude intéressante. Il compare deux approches assez différentes de la classification des données géographiques: le regroupement des moyennes K et la modélisation de la croissance des classes latentes.

Une des images de l'étude:

entrez la description de l'image ici

Les auteurs ont conclu que les résultats finaux étaient globalement similaires et qu'il existait certains aspects dans lesquels la K-moyenne sur-performée par LCGM.

VividD
la source
5

Vous pouvez utiliser HDBSCAN pour cela. Le paquet python prend en charge la distance haversine qui calculera correctement les distances entre les points lat / lon.

Comme le mentionnent les docs , vous devrez d’abord convertir vos points en radians pour que cela fonctionne. Le psuedocode suivant devrait faire l'affaire:

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)
Mat
la source
0

L'algorithme k-means pour regrouper les emplacements est une mauvaise idée. Vos emplacements peuvent être répartis à travers le monde et vous ne pouvez pas prédire le nombre de clusters. Si vous définissez le cluster sur 1, les emplacements seront regroupés en un seul cluster. J'utilise le clustering hiérarchique pour la même chose.

Mahamune taillé
la source
-1

Allez avec le regroupement Kmeans car HBScan prendra une éternité. Je l'ai essayé pour l'un des projets et j'ai fini en utilisant Kmeans avec les résultats souhaités.

Vivek Khetan
la source