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 <=MaxCapacitywhile 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
  • 1
    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
  • 1
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.