Problems with ST_ClusterDBSCAN cluster sizes

Question

I want to cluster all villages (and towns, ...) around the world. So instead of having millions of them, I'd like to reduce them by combining villages that are close enough (like 10km or so) to each other.

So I was looking into ST_ClusterDBSCAN and it's doing quite a good job. This is how I made my table:

INSERT INTO villages_clustered
  SELECT
    name,
    way,
    ST_ClusterDBSCAN(way, eps := 2000, minpoints := 1) over () AS cluster_id
  FROM villages;

Now when I look at my data, I get lots of small clusters which is what I wanted. But there are also some, which are just suuuuper large that should split into smaller ones.

Would really love to know how to improve my query to get better results. What I basically want is clusters of like 10km or so.

Answer 1

The eps distance is the maximum distance between points in the cluster, not the maximum width of the entire cluster.

So if you have points A, B, and C, as long as each point is within the eps distance of one other point, then it gets included in the cluster. If the eps distance was 1 km, A could be within 1 km of B, and C can be within 1 km of B, but A can be 2 km from C and ABC are still a cluster because A & C are within 1 km of B.

https://en.wikipedia.org/wiki/DBSCAN

Answer 2

Maybe you can try an iterative approach:

You first use ST_ClusterDBSCAN with a big eps and a small minpoints, and then you isolate the points that are in a cluster too big for you, for exemple using the radius of the bounding circle (general idea, not tested):

sqrt(ST_Area(ST_MinimumBoundingCircle(ST_Collect(points)))/pi) > your_threshold group by cluster_number

Then you do an other ST_ClusterDBSCAN on them with more stricts parameters (shorter eps and/or bigger minpoints). The main difficulty here relies on the choosing of how many steps and what parameters for each step, it depends on the actual result that you want.

If you do that a couple of time you should in fine have only small clusters, without loosing the aggregation in sparser areas.

EDIT: in my idea, that would look like that (I used max_cluster_id_big in the end to be sure the cluster id doesn't overlap):

INSERT INTO villages_clustered
WITH big_cluster_element AS (
    SELECT
        ROW_NUMBER() OVER() as id,
        name,
        way,
        ST_ClusterDBSCAN(way, eps := 2000, minpoints := 1) over () AS cluster_id_big,
        geom
    FROM villages
), big_cluster AS (
    SELECT
        cluster_id_big,
        sqrt(ST_Area(ST_MinimumBoundingCircle(ST_Collect(geom)))/pi()) as radius
    FROM big_cluster_element
    GROUP BY cluster_id_big
), big_cluster_element_with_radius AS (
    SELECT
        id,
        name,
        way,
        bc.radius,
        bce.cluster_id_big
        geom
    FROM big_cluster_element bce
    LEFT JOIN big_cluster bc
    ON bce.cluster_id_big=bc.cluster_id_big
), small_cluster_element AS (
    SELECT
        id,
        name,
        way,
        ST_ClusterDBSCAN(way, eps := 500, minpoints := 3) over () AS cluster_id_small,
        geom
    FROM big_cluster_element_with_radius bc
    WHERE bc.radius > 10000
), max_id_big AS (
    SELECT
            max(cluster_id_big) as max_cluster_id_big
        FROM big_cluster_element
)
SELECT 
    id,
    name,
    way,
    coalesce(cluster_id_small+max_cluster_id_big, cluster_id_big) as cluster_id,
    geom
    FROM max_id_big, big_cluster_element bce
    LEFT JOIN small_cluster_element sce
    ON bce.id = sce.id