2

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.

Improve this question
6
  • What do you mean, index clustering or spatial clustering? Commented Jun 7, 2017 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. Commented Jun 7, 2017 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. Commented Jun 7, 2017 at 8:12
  • @Evan Carroll ; I meant spatial clustering. I don't know about index clustering. Commented Jun 7, 2017 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/… Commented Jun 7, 2017 at 20:54

2 Answers 2

Reset to default
3

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.

Improve this answer
1

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...

Improve this answer
1
  • 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. Commented Jun 8, 2017 at 19:41

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.