Limit radius of ST_Clusterwithin (PostGIS)

Question

I have a set of over 800k points and I am looking to cluster them within specified circle radius. I need them to be clustered to maximise the number of points within the circle. This is to model how many signal towers are needed to cover the points.

I tried using ST_ClusterWithin in PostGIS, but this seems to merge nearby clusters to form mega-clusters, but this is not what I want.

1) Is it possible to limit the maximum radius of a cluster so that it is forced to break up and form new clusters?

2) Is it possible to force the minimum radius too to match my signal radius, so that clusters are formed to maximise the points within the circle? I.e. if there was initially two clusters of 10km radius near each other, forcing a 15km radius would position the circle between them so as to maximise the points in the cluster.

Please let me know if you need clarifications.

I have QGIS, ArcGIS if helpful.

Answer 1

I am afraid this is not possible from postgis. Also it sounds like a question that may involve more than 1 valid answer, there being more than 1 distribution of cell towers that would fit your area.

You can play however with the new postgis (v2.3) function ST_ClusterDBScan which lets you give a search radius for finding neighbouring points. It is not the same as you propose, but at least it lets you find clusters up to a certain density and after playing around with the two parameters you might nevertheless come to an agreeable distribution of your towers.

http://postgis.net/docs/manual-dev/ST_ClusterDBSCAN.html

Answer 2

I had a very similar problem which I was able to solve by nesting a KMEANS cluster inside a DBSCAN cluster.

The KMEANS cluster is very good a clumping up distinct areas and then the DBSCAN splits sparse cluster into several smaller cluster.

This is the bit of code which I took from the answer by Dan Baston which solved the problem.

SELECT
  st_pointonsurface(st_union(geomcntr)) AS geom,
  count(1) AS c
FROM (
  SELECT
    qid,
    brand,
    store,
    kmeans_cid,
    geomcntr,
    ST_ClusterDBSCAN(geomcntr, 0.1, 1) OVER (PARTITION BY kmeans_cid) AS dbscan_cid
  FROM (
    SELECT
      qid,
      brand,
      store,
      geomcntr,
      ST_ClusterKMeans(geomcntr, 200) OVER () AS kmeans_cid
    FROM retailpoints
  ) retail_kmeans
) retail_dbscan
GROUP BY kmeans_cid, dbscan_cid