Cluster Hierarchical e KMeans para distâncias Geográficas

Um pequeno problema que estava procurando resolver era, através de determinada coordenada geográfica, determinar o ponto central desses pontos a partir de certas restrições.

Sendo direto, a pergunta era: Qual o melhor local de encontro para os pontos?

Com isso, alguns questionamentos vieram:

• Como transformar endereços em lat/lon
• Qual método de distância a ser utilizado
• Como implementar as regras
• Validação de resultados
• Visualização dos resultados

Quando analisamos distâncias temos diversos problemas a serem considerados e, como sempre…esbarramos na qualidade dos dados que temos. Percebi que para a maioria dos dados os endereços não estavam em formatos padrão, apresentavam falta de algumas informações e até alguns estavam para locais que não faziam sentido algum! (infelizmente, para esses casos os desconsiderei das análises)

Para conseguir as coordenadas geográficas utilizei o Google Sheets com o script abaixo:

function GEOCODE_GOOGLE(address) {
if (address.map) {
return address.map(GEOCODE_GOOGLE)
} else {
var r = Maps.newGeocoder().geocode(address)
for (var i = 0; i < r.results.length; i++) {
var res = r.results[i]
return res.geometry.location.lat + ", " + res.geometry.location.lng
}}}
/**
* Returns latitude and longitude values for given address using the Yandex Geocoder.*
* @param {string} address - The address you get the latitude and longitude for.* @customfunction*/

function GEOCODE_YANDEX(address) {
if (address.map) {
return address.map(GEOCODE_YANDEX)
} else {
input = encodeURI(address)
var r = UrlFetchApp.fetch(
"https://geocode-maps.yandex.ru/1.x/?format=json&geocode=" + input + "&results=1&lang=en-US", {
"method": "get"
})
var res = JSON.parse(r)
try {
res = res.response.GeoObjectCollection.featureMember[0].GeoObject.Point.pos
res = res.split(" ")[1] + ", " + res.split(" ")[0]
return res

} catch (e) {
return ""
}}}

Encontrei esse código em um dos muitos fóruns de discussão sobre o assunto, infelizmente não encontrei novamente o artigo para entregar os devidos créditos ao autor.

Portanto, agora eu tinha endereços convertidos em latitude e longitude para começar a devida análise.

A segunda etapa foi iniciar a pesquisa sobre qual a melhor metodologia para o cálculo de distâncias a ser utilizado, dentre elas temos várias opções:

1. Distância Manhattan
2. Distância euclidiana
3. Distância Haversine

Dentre essas opções cogitei, inicialmente, utilizar a distância de Manhattan para o cálculo, faria sentido se o conjunto de cidades que eu estava olhando tivessem uma estrutura similar a de Nova York (spoiler: não é o caso).

Olhando relativamente pequenas distâncias a curvatura da terra (tchau terraplanistas) não impactaria no resultado do cálculo porém, procurando realizar um trabalho replicável acabei por escolher a distância de Haversine (The Great Circle).

from geopy.distance import great_circle
from scipy.spatial.distance import pdist

points = df[['lat','lon']].astype(float).to_numpy()
m_dist = pdist(points, 
               lambda u, v: great_circle(u, v).kilometers)

Pronto, agora temos como calcular a distância entre os pontos, mas fica a pergunta: Como deteminar nossos cluster? Nossos grupos de pontos a serem unificados?

from scipy.cluster.hierarchy import ward, fcluster, centroid

from geopy.distance import great_circle
from scipy.cluster.hierarchy import linkage, fcluster

t = 1

y_pred_h = fcluster(linkage(m_dist), t, criterion='distance')

Nesse caso estou utilizando o Cluster hierárquico para determinar, com base na nossa regra de distância (de 1km entre o centro e os pontos) , quais cluster nós teremos e quais seus integrantes. Contudo essa técnica de clusterização não nos informa o ponto central! Que é exatamente o que queremos.

Para isso simplesmente utilizamos o KMeans, a quantidade de cluster a ser separada será a quantidade de Cluster que a técnica anterior nos retornou. O KMeans procurará encontrar quais os pontos mais próximos entre si, divididos em n clusters.

kmeans = KMeans(n_clusters= max(y_pred_h) + 1).fit(points)
kmeans.labels_

Ao plotar o resultado do Kmeans temos:

plt.style.use('ggplot')
fig_dims = (15, 10)
fig, ax = plt.subplots(figsize=fig_dims)
# plot the cluster centers and samples 
sns.scatterplot(kmeans.cluster_centers_[:,0], kmeans.cluster_centers_[:,1], 
                marker='+', 
                color='black', 
                s=200);
sns.scatterplot(points[:,0], points[:,1])

Por ultimo temos nossos resultados com: stops = kmeans.clustercenters[:]

Sugiro fortemente plotar os resultados no “MyMaps” (https://www.google.com/maps/d/u/0/?hl=pt-BR) e visualizar as informações tantos dos pontos, como dos resultados e verificar por si mesmo que as regras são obedecidas.