0

I am trying to cluster geographical locations in such a way that all the locations inside each cluster are at max within 25 miles of each other. For this, I am using Agglomerative clustering. I am using a custom distance function to calculate the distances between each location. I do not want to specify the number of clusters. Instead, I want the model to cluster until all the locations within each cluster are within 25 miles of each other. I have tried doing this in both Scipy and Sklearn but haven't made any progress. Below is the approach that I have tried. It only gives me one cluster. Please help. Thanks in advance.

from scipy.cluster.hierarchy import fclusterdata 

max_dist = 25
# dist is a custom function that calculates the distance (in miles) between two locations using the geographical coordinates

fclusterdata(locations_in_RI[['Latitude', 'Longitude']].values, t=max_dist, metric=dist, criterion='distance')
Karthik Katragadda
  • 1
  • 2

1 Answers1

0

You need to use method="complete" otherwise it will not be a pairwise limit, obviously.

Complete linkage is the maximum distance of any two points, whereas the default just requires that there is some point (minimum of all cluster members) within the given distance.

A faster - greedy - approach is Leader clustering. It's quite stupid, but if you set the clustering radius to half your limit, any two points must be within your threshold if you have a metric.

Has QUIT--Anony-Mousse
  • 39,639
  • 7
  • 61
  • 96
  • Although this is correct, it is likely to lead to obviously inferior solutions. Such solutions can be of interest in practical applications insofar as one can establish bounds on how bad they can be compared to the optimum. Would you be aware of any such bounds? – whuber Mar 19 '19 at 17:31
  • Because of the triangle inequality, I'd assume they will be at most twice as bad as the optimum solution. I don't know of theoretical results here though. It's probably np-hard, so you'll either have to live with an approximation of excessive runtime... – Has QUIT--Anony-Mousse Mar 19 '19 at 17:33
  • Nevertheless it may be worth experimenting with post-clustering optimizations, multiple restarts, and similar. It probably is also worth approaching this from an integer program optimization viewpoint of you need better solutions. – Has QUIT--Anony-Mousse Mar 19 '19 at 18:34
  • But since he has been experimenting with hierarchical clustering, setting the linkage to complete is the easiest way to ensure the maximum distance constraint is satisfied. It won't find the optimum cover (with the smallest number of clusters) but is easy for him to do. – Has QUIT--Anony-Mousse Mar 19 '19 at 18:35