# Maximising cluster density around geo points using qgis

I am looking for some advice for clustering points around other defined centres while maximising the density i.e. I need to identify clusters but constrain the cluster densities to be `>= MinRequired` and `<=MaxCapacity`while also keeping the clusters as compact as possible

The following discussion pointed out a way to create a buffer around my Centres and spatially join that with my points dataset to see where they overlap but is there a way to add the cluster density constraints to the method?

• Could clustering the points (K = minRequired) using KNN then getting the distance from that cluster to my defined centres be an option? – Michael Jul 19 '17 at 9:56
• Where do you define the defined centres? Within the same shapefile that stores all the points to be clustered or they comes from another layer? – mgri Jul 21 '17 at 15:39
• Destination Points aka defined centres are all in 1 separate shapefile. Source points to cluster around those centres are in another shapefile – Michael Jul 21 '17 at 15:40

It seems to be a similar problem to create n equal clusters. If you want to have constraints like that, it is not only clustering problem but more complex one.

Lets say that we have n points and we want to create k equal clusters. It is not possible with a clustering methods like a k-means etc. But it is a nice start, after that we just need to solve the assignment problem. First we can use a clustering algorithm, k-means is enough. Then we have k clusters but of course each one has different number of objects. Also each cluster has its centroid and this is a good waypoint for the next part of our task.

Now we can take all of these centroids and just solve the assignment problem. Hungarian Algorithm is the most popular I guess. It has a polynomial complexity but it should be quite fast in the most of GIS tasks. It finds k points (one for each cluster) and assigns them. Then again and again until n it assigns n points.

That is how we can create equal clusters. As you said:

I need to identify clusters but constrain the cluster densities to be >= MinRequired and <=MaxCapacity

So If you run k-means for n points to find n/MinRequired clusters and then assign points to each centroid with HA, you will solve this problem.

I did tasks like that, mostly dividing into equal clusters and I can recommend for you a following: https://docs.scipy.org/doc/scipy-0.19.0/reference/generated/scipy.cluster.vq.kmeans2.html https://docs.scipy.org/doc/scipy-0.19.0/reference/generated/scipy.optimize.linear_sum_assignment.html

• Am I correct in thinking your method clusters around the centroids from the source points and not the designated destination points? – Michael Jul 21 '17 at 19:04
• If you have a set of designated points you can skip the first part with k-means and just use Hungarian Algorithm. – dmh126 Jul 21 '17 at 19:17
• For others this video might be useful to understanding the Hungarian Algorithm youtube.com/watch?v=dQDZNHwuuOY – Michael Jul 25 '17 at 8:16