1

I have a bunch of thousands of points. I'd like to group them, in a user-defined number of clusters for example or based on some kind of "best number of clusters", based for example on their relatives distances. Which kind of algorithm is available on postGIS and/or shapely (preferred) to do that? I can simply make some buffers around them and a union but I wonder if there is some other advanced technique that are computationally efficient on large dataset.


Edit:

I've found the DBSCAN algorithm [1] interesting and it seems rather simple to insert in an existing code. There is also the OPTICS algorithm [2] but it seems harder to find a solution.

[1]https://en.wikipedia.org/wiki/DBSCAN
[2]https://en.wikipedia.org/wiki/OPTICS_algorithm

Anyway, I'm stuck with DBSCAN now:
how to store the cluster label in which a point lays within a new column "cluster" in a postgreSQL table? Actually, the points ID are not stored along their coordinates within the cluster...
Some checking operations on coordinates in order to retrieve points IDs in original array would be a bit overrated, in my opinion.

  • What do you mean, index clustering or spatial clustering? – Evan Carroll Jun 7 '17 at 0:26
  • Best number of clusters? Finding optimal clusters is one of the unsolved problems of unsupervised classification. See this scikit learn example for an example as to why. – John Powell Jun 7 '17 at 8:08
  • So, there are a number of clustering algorithms included in Postgis directly (k-means, DB scan and a couple of others) and a ton more in Python, as you will see, but you will likely need to provide much more information on what you are trying to do and what a "best number of clusters" might look like. – John Powell Jun 7 '17 at 8:12
  • @Evan Carroll ; I meant spatial clustering. I don't know about index clustering. – s.k Jun 7 '17 at 20:53
  • @JohnPowellakaBarça ; I've had a look on your scikit example link and tried to play with this module in Python directly. It seems promising. I also found this page with a useful example: geoffboeing.com/2014/08/… – s.k Jun 7 '17 at 20:54
2

I assume from your question that your points have some kind of natural clustering. You can use the ST_ClusterDBSCAN function to try to assign cluster id's to every point. Since this is a window function, you will have to group the points together youself later on.

Here is an example use case: Say you have clusters of trees where some of them would be seen as a forest and some of them are just small patches of trees, depending on how many trees are together and close they are to eachother. There should be at least 100 trees to call it a forest and they should be no more than 10 meters apart. Your cluster function would look like: ST_ClusterDBSCAN(geom, eps := 10, minpoints := 100)

The result would be a cluster id and one step later you can aggregate these points into whatever you like (e.g.

WITH clusters AS (
  SELECT ST_ClusterDBSCAN(geom, eps := 10, minpoints := 100) as clusterid, geom 
  FROM mybigtable
)
SELECT clusterid, ST_Collect(geom) as cluster_geometry FROM clusters GROUP BY clusterid

).

Now it is up to you to play with the parameters to find the right clusters. Keep in mind that this algorithm assumes a normal distribution for every clusters, so it wouldn't work if every cluster has different eps and minpoints parameters.

0

Thanks, I've already tried to include the DBSCAN algorithm within my Python script with some success.
But there is yet two small open questions for me:

1)
I think the algorithm is not complicated to understand, but there is no "min cluster radius" constraint for example.
The eps distance is the distance to be checked to know if two points can be considered belonging to the same cluster or not.

It would be nice to also have a 2nd distance which tells "clusters themselves should not be greater than this size" but I guess it would be complicated to find out where should be the limit between two separate clusters when initial points are spread continuously over a much longer than larger area...

An image will be better to understand this: long cluster

Here, there are points along valleys, the red zone indicates a "long cluster" where points up the valley have no more relation with points down the valley. So they should not be clustered together even if they are closed, pairwise, along even a 100 km valley. I'd like to have more "circular" cluster, e.g. no more than x[m] radius for example.

2)
Clusters labels shown properly in the matplotlib image here above but on QGIS they are completely messed up... I guess I should check my script again...

  • It would be better to move this text into the original question as an edit (like you did before) instead of putting it between the answers. In that way it will be easier to understand the questions. You might also consider creating a complete new question altogether, since you already work with python. – tilt Jun 8 '17 at 19:41

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.