I'm looking for a way, preferably in R, to create a cluster of point data (specifically, the centroids of UK postcodes), where each cluster comes as close as possible to containing a certain number of people (between 100 and 200). The data I have is a SpatialPointsDataFrame of all postcodes with their Eastings/Northings, plus a column in the data for number of people in that postcode.

I can create a cluster of the point data using Kmeans, but that of course creates clusters with anywhere between 1 and several thousand people in them as it is doing so purely on the location of the point data.

Is there a way of clustering not just constraining on the number of clusters, but on the sum of people contained in the resulting cluster, as specified in my data?

My initial thought has been to do an initial set of clusters, and then recluster the clusters continually to create final clusters as close to the desired size as possible. However, at the moment I can only think of a way of doing that which basically involves a lot of trial and error. Is there an algorithm or some way of training R to try and achieve clusters of this specified size?

  • $\begingroup$ I wonder if the postcode areas in each cluster have to be neighbouring? Is the data more suited to a graph structure than just points in the plane? This might be related to cstheory.stackexchange.com/questions/25557/… $\endgroup$
    – ASeaton
    Aug 5 '19 at 9:28
  • $\begingroup$ I would look at hierarchical clustering and before you add a point to the cluster you check it against the constraint. $\endgroup$
    – Tylerr
    Aug 12 at 15:11

While I'm not familiar with the possiblities of R in this regard, off the top of my head I'd suggest to use some kind of fuzzy clustering like fuzzy c-means. Since this will not only provide you with the cluster assignment for each instance, but also a measure of 'belonging' to each cluster.
Based on this fuzzy cluster membership you could then 'balance' the clusters so they don't exceed a certain amount of instances by too much.


Your Answer

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