Coordenadas de localização geográfica em cluster (pares longos e latinos)

51

Qual é a abordagem correta e o algoritmo de clustering para clustering de geolocalização?

Estou usando o seguinte código para agrupar coordenadas de localização geográfica:

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

É correto usar K-means para agrupamento de geolocalização, pois usa distância euclidiana, e não a fórmula de Haversine como função de distância?

rok
fonte
Você também pode dar uma olhada nesta pergunta semelhante: datascience.stackexchange.com/questions/10063/…
VividD
Eu acho que a viabilidade do k-means dependerá de onde estão seus dados. Se seus dados estiverem espalhados por todo o mundo, eles não funcionarão, pois a distância não é euclidiana, como outros usuários já disseram. Mas se seus dados forem mais locais, o k-means seria bom o suficiente, pois a geometria é localmente euclidiana.
Juan Ignacio Gil

Respostas:

7

K-significa deve estar certo neste caso. Como o k-means tenta agrupar com base apenas na distância euclidiana entre os objetos, você receberá grupos de locais próximos um do outro.

Para encontrar o número ideal de clusters, você pode tentar fazer um gráfico de cotovelo da soma da distância quadrada dentro do grupo. Isso pode ser útil ( http://nbviewer.ipython.org/github/nborwankar/LearnDataScience/blob/master/notebooks/D3.%20K-Means%20Clustering%20Analysis.ipynb )

mike1886
fonte
3
Como são tratados os pontos próximos um do outro no ponto de contorno?
casperOne
11
Você precisa encontrar um algoritmo que utilize uma matriz de distância pré-calculada ou permita fornecer uma função de distância que ele pode chamar quando precisar calcular distâncias. Caso contrário, não funcionará.
21414 Spacedman
O gráfico do cotovelo pode não ajudá-lo, pois pode não haver cotovelo. Além disso, tente executar várias execuções de k-means com o mesmo número de cluster, pois você pode obter resultados diferentes.
Grasshopper
Essa é uma péssima idéia, pois todos os pontos serão agrupados, o que raramente é uma boa idéia no mapeamento.
Richard
52

K-means não é o algoritmo mais apropriado aqui.

A razão é que o k-means é projetado para minimizar a variação . Obviamente, isso está aparecendo do ponto de vista estatístico e de processamento de sinais, mas seus dados não são "lineares".

Como seus dados estão no formato de latitude e longitude, você deve usar um algoritmo que possa lidar com funções de distância arbitrárias , em particular funções de distância geodésica. O cluster hierárquico, PAM, CLARA e DBSCAN são exemplos populares disso.

https://www.youtube.com/watch?v=QsGOoWdqaT8 recomenda o agrupamento OPTICS.

Os problemas dos meios k são fáceis de ver quando se considera pontos próximos à curva de + -180 graus. Mesmo que você tenha hackeado o k-means para usar a distância Haversine, na etapa de atualização, quando recalcular a média, o resultado será mal ferrado. O pior caso é que o k-means nunca convergirá!

Anony-Mousse
fonte
Você pode sugerir um método de cluster mais apropriado para dados de localização geográfica?
Alex Spurling
Você notou o terceiro parágrafo?
Anony-Mousse
7

As coordenadas de GPS podem ser convertidas diretamente em uma geohash . O Geohash divide a Terra em "baldes" de tamanho diferente, com base no número de dígitos (códigos curtos de Geohash criam grandes áreas e códigos mais longos para áreas menores). Geohash é um método de agrupamento de precisão ajustável.

Brian Spiering
fonte
Isso parece sofrer do mesmo problema de 180 graus que o K-Means faz pelo artigo da Wikipedia vinculado na resposta.
Norman H
Sim! Os códigos de adição são muito melhores códigos de adição.
Brian Spiering
Um benefício para esta solução é que, desde que você calcule a geohash uma vez, as operações de comparação repetidas serão muito mais rápidas.
Norman H
O Geohash terá problemas com os casos de borda do balde - dois pontos muito próximos serão colocados em baldes diferentes com base nas arestas arbitrárias de cada balde.
Dan G
5

Provavelmente estou muito atrasado com a minha resposta, mas se você ainda está lidando com o agrupamento geográfico, pode achar este estudo interessante. Ele lida com a comparação de duas abordagens bastante diferentes para classificar dados geográficos: cluster K-significa e modelagem de crescimento de classe latente.

Uma das imagens do estudo:

insira a descrição da imagem aqui

Os autores concluíram que os resultados finais eram similares em geral e que havia alguns aspectos em que a LCGM superestimou as médias-K.

VividD
fonte
5

Você pode usar o HDBSCAN para isso. O pacote python suporta a distância do haversine, que calculará adequadamente as distâncias entre os pontos lat / lon.

Como os documentos mencionam , você precisará converter seus pontos em radianos primeiro para que isso funcione. O seguinte psuedocode deve executar o truque:

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)
Matt
fonte
0

O algoritmo k-means para agrupar os locais é uma má ideia. Seus locais podem ser espalhados por todo o mundo e o número de clusters não pode ser previsto por você, não apenas que, se você colocar o cluster como 1, os locais serão agrupados em um único cluster. Estou usando o cluster hierárquico para o mesmo.

Rugham Mahamune
fonte
-1

Siga o clustering do Kmeans, pois o HBScan levará uma eternidade. Eu tentei para um dos projetos e terminei, mas usando o Kmeans com os resultados desejados.

Vivek Khetan
fonte