1

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.

enter image description here

  • How does your question change after you read postgis.net/docs/manual-dev/ST_ClusterDBSCAN.html? – bugmenot123 Jul 23 at 8:17
  • 1
    Thank you for your reply. Not much. I read the manual, but I am neither a gis nor a postgres/postgis expert. So it doesn't say that much to me. Is there something obvious that I am missing? – Georg Jul 23 at 8:55
  • The eps parameter :) You say you want 10km clusters, so try an appropriate value for that. You have to take care of your coordinate values, which SRID is your data in if it is Geometries, not Geographies? Also you might like postgis.net/docs/manual-dev/ST_ClusterWithin.html as easier approach. – bugmenot123 Jul 23 at 9:46
  • I need the actual villages, didn't get that to work with ST_ClusterWithin?!? Cause it only returns clustered geometries?!? Right? So how could I get back to the villages themselfs? Yes... the eps is not stable, right? It will vary depending how far away from the equator I am? The thing is that some, or even most clusters seem to be about 10km. But some are waaaaay bigger, which I don't understand. The srid of my data is: 3857 – Georg Jul 23 at 13:05
  • Also... If I decrease my eps, I don't get those huge clusters any more. But still, I have a lot of geometries that then don't have any cluster, even though there are other villages nearby – Georg Jul 23 at 14:00
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

  • Yes, I figured that out. So I did my own clustering for what I needed. Thanks for the clarification though! – Georg Aug 21 at 5:30
1

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
  • As you can see, the idea is that cluster_id_small takes precedent if it exists, but if not the fallback is on the cluster_id_big. The structure should let you stack other steps easily (if it works, unfortunately I didn't tested it) – robin loche Jul 25 at 10:04

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.