# Maximize clusters of points from coordinate data

So I am definitely new to the GIS world, so bear with me if I don't know the best way to articulate my problem. That said, I am ready to learn, I would definitely welcome any direction that you all could point me in.

The problem: I have a set of coordinate points (just three attributes: name, lat, long). I hope to identify the minimum number of regions (circles with a predefined radius) that would be required to encompass XX percent of the sites (Where XX is configurable).

Initial thoughts: My thoughts were to first create clusters (of set size) of all data points, then sort the clusters by the number of points they enclose. That way I can just count the number of clusters needed (in order of priority) until they represent the desired XX percent of the points.

Thus far I have tried to do some research, but I haven't found any resources where the clustering is done within a set radius. (I have found plenty where the number of clusters is set, and the size is variable - I need the reverse of that.)

I have tried using QGIS, but I am open to any suggestions. I am new to GIS, but I have a decent knowledge of programming if that could be of any help.

• I did a bit more searching and it would appear that the crux of what I am looking for is "distance-based clustering". However, I cannot seem to find an open/published algorithm (see the end of the section here: developers.google.com/maps/articles/…) – MattJ Jun 29 '14 at 15:01

Given your initial thoughts I'd take a look at scipy.cluster.hierarchy to start with (or the equivalent in scikit-learn) to build the clusters based on distance.

For instance, given a `numpy.array` of coordinates - `coords` you could build a cluster based on distance like so:

``````import numpy as np
import scipy.cluster.hierarchy
import collections

labels = scipy.cluster.hierarchy.fclusterdata(
coords,
threshold, #The distance of whether or not an object is in the cluster
criterion='distance', #cluster based on distance
method='complete' #method complete means all points must be within threshold distance of one another to be in the same cluster
)

cluster_count = np.bincount(labels) # count the number of entities in each cluster
sorted_labels = np.argsort(cluster_count)
sorted_labels = sorted_labels[sorted_labels != 0] #hierarchy starts labels at 0, so you want to get rid of it
sorted_count = cluster_count[sorted_labels]

progressive_sum = np.cumsum(sorted_count)