PYTHON Geospatial clustering with centroid distance

Question

I'm looking how to cluster geographical data([longitude, Latitude] like that:

n = number of wanted cluster
the Centroids are calculated to be where the density is the highest or centroids could be given by user.
the limit of a cluster must be the distance between the centroid of the cluster and the farest point of the cluster
Also i wanted to specifie the maximum distance between centroids.

I tried DBSCAN but the distance limit (epsilon) is computed between each points and not from the centroid.

Can anybody help me?

Willem Hendriks · Answer

One method to cluster would be using the K-Medoids method. It allows to set the number of cluster k, distances are calculated to the centroids, which are always data points, but there is no such thing as a limit between points and/or centroids. The scikit-learn-extra implementation supports the haversine metric, which you need for geospatial data.

Be aware; with such limits there might not exists a solution at all. And if the centroids are given by the user, no clustering is need to be done at all. In that case you simply assign each point to nearest centroid.

The example below generates 5000 points, and assign clusters using K-Medoids with haversine as metric.

!pip install scikit-learn-extra
!pip install folium

import numpy as np
from sklearn_extra.cluster import KMedoids

random_gps = np.random.multivariate_normal([46.9, 7.4], [[2.0, 0.5], [0.5, 2.0]], size=5000)

kmedoids = KMedoids(metric="haversine", n_clusters=20, method='alternate')
clusters = kmedoids.fit(np.radians(random_gps) )

Now clusters.labels_ will contain the assignment of clusters, and clusters.medoid_indices gives the indici of the data points which are centroid/medoids.

You could visually inspect with e.g. folium;

import folium

colors = ['red', 'blue', 'green', 'purple', 'orange', 'darkred',
'lightred', 'beige', 'darkblue', 'darkgreen', 'cadetblue', 'darkpurple', 'white', 'pink', 'lightblue', 'lightgreen', 'gray', 'black', 'lightgray']

map_osm = folium.Map(location=[np.mean(random_gps.T[0]), np.mean(random_gps.T[1])], zoom_start=6, prefer_canvas=False)

for point, cluster in zip(random_gps, clusters.labels_):
    lat, long = point
    folium.Circle(
      location=[lat, long],
      radius=2500,
      color=colors[cluster % len(colors)],
      fill=True,
      fill_color=colors[cluster % len(colors)],
    ).add_to(map_osm)
    
for centroid in clusters.medoid_indices_:
    lat, long = random_gps[centroid]
    folium.Marker([lat, long]).add_to(map_osm)
    
map_osm

K-Medoids with haversine

PYTHON Geospatial clustering with centroid distance

1 Answers