Agrupación de coordenadas de ubicación geográfica (lat, pares largos)

51

¿Cuál es el enfoque correcto y el algoritmo de agrupación para la agrupación de geolocalización?

Estoy usando el siguiente código para agrupar las coordenadas de geolocalización:

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

¿Es correcto usar K-means para el agrupamiento de geolocalización, ya que usa la distancia euclidiana y no la fórmula de Haversine como una función de distancia?

rok
fuente
También puede echar un vistazo a esta pregunta similar: datascience.stackexchange.com/questions/10063/…
VividD
Creo que la viabilidad de k-means dependerá de dónde estén sus datos. Si sus datos se extienden por todo el mundo, no funcionará, ya que la distancia no es euclidiana, como ya lo han dicho otros usuarios. Pero si sus datos son más locales, k-means sería lo suficientemente bueno, ya que la geometría es localmente euclidiana.
Juan Ignacio Gil

Respuestas:

7

K-means debería tener razón en este caso. Dado que k-means intenta agrupar basándose únicamente en la distancia euclidiana entre los objetos, obtendrá grupos de ubicaciones cercanas entre sí.

Para encontrar el número óptimo de grupos, puede intentar hacer un diagrama de "codo" de la suma de la distancia cuadrada dentro del grupo. Esto puede ser útil ( http://nbviewer.ipython.org/github/nborwankar/LearnDataScience/blob/master/notebooks/D3.%20K-Means%20Clustering%20Analysis.ipynb )

mike1886
fuente
3
¿Cómo se manejan los puntos cercanos entre sí en el punto de ajuste?
casperOne
1
Debe encontrar un algoritmo que tome una matriz de distancia calculada previamente o que le permita proporcionar una función de distancia que pueda llamar cuando necesite calcular distancias. De lo contrario, no funcionará.
Spacedman
Es posible que el diagrama del codo no lo ayude en absoluto porque podría no haber codo. También asegúrese de probar varias ejecuciones de k-means con el mismo número de clúster porque puede obtener resultados diferentes.
Grasshopper
Esta es una mala idea ya que todos los puntos estarán agrupados, lo que rara vez es una buena idea en el mapeo.
Richard
52

K-means no es el algoritmo más apropiado aquí.

La razón es que k-means está diseñado para minimizar la varianza . Esto, por supuesto, aparece desde un punto de vista estadístico y de procesamiento de señal, pero sus datos no son "lineales".

Dado que sus datos están en formato de latitud y longitud, debe usar un algoritmo que pueda manejar funciones de distancia arbitrarias , en particular funciones de distancia geodésicas. El agrupamiento jerárquico, PAM, CLARA y DBSCAN son ejemplos populares de esto.

https://www.youtube.com/watch?v=QsGOoWdqaT8 recomienda la agrupación OPTICS.

Los problemas de k-means son fáciles de ver cuando considera puntos cercanos a la envoltura de + -180 grados. Incluso si hackeó k-means para usar la distancia de Haversine, en el paso de actualización, cuando vuelve a calcular la media, el resultado se verá mal. El peor de los casos es que k-means nunca convergerá.

Anony-Mousse
fuente
¿Puede sugerir un método de agrupación más apropiado para los datos de ubicación geográfica?
Alex Spurling
¿Notaste el tercer párrafo?
Anony-Mousse
7

Las coordenadas GPS se pueden convertir directamente a un geohash . Geohash divide la Tierra en "cubos" de diferente tamaño en función del número de dígitos (los códigos cortos de Geohash crean áreas grandes y códigos más largos para áreas más pequeñas). Geohash es un método de agrupamiento de precisión ajustable.

Brian Spiering
fuente
Esto parece sufrir el mismo problema envolvente de 180 grados que K-Means tiene según el artículo de Wikipedia vinculado en la respuesta.
Norman H
¡Sí! Los códigos plus son mucho mejores códigos plus
Brian Spiering
Un beneficio de esta solución es que, siempre y cuando calcules el geohash una vez, las operaciones de comparación repetidas serán mucho más rápidas.
Norman H
Geohash tendrá problemas con los casos de borde de cubeta: dos puntos muy cercanos se colocarán en cubos diferentes en función de los bordes arbitrarios de cada cubo.
Dan G
5

Probablemente llegue muy tarde con mi respuesta, pero si todavía está lidiando con la agrupación geográfica, puede encontrar este estudio interesante. Se trata de la comparación de dos enfoques bastante diferentes para clasificar datos geográficos: agrupamiento de K-medias y modelado de crecimiento de clase latente.

Una de las imágenes del estudio:

ingrese la descripción de la imagen aquí

Los autores concluyeron que los resultados finales fueron en general similares, y que hubo algunos aspectos en los que LCGM superó el rendimiento de K-medias.

VividD
fuente
5

Puede usar HDBSCAN para esto. El paquete de Python tiene soporte para la distancia de Haversine que calculará correctamente las distancias entre los puntos lat / lon

Como mencionan los documentos , primero deberá convertir sus puntos a radianes para que esto funcione. El siguiente psuedocode debería hacer el truco:

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)
Mate
fuente
0

El algoritmo k-means para agrupar las ubicaciones es una mala idea. Sus ubicaciones se pueden distribuir por todo el mundo y no puede predecir el número de grupos, no solo si coloca el grupo como 1, las ubicaciones se agruparán en 1 solo grupo. Estoy usando el agrupamiento jerárquico para lo mismo.

Mahamune rugoso
fuente
-1

Vaya con la agrupación de Kmeans ya que HBScan tomará una eternidad. Lo probé para uno de los proyectos y terminé pero usando Kmeans con los resultados deseados.

Vivek Khetan
fuente