QGIS Clustering – Identifying Clusters in Vector Point Data

clusteringqgisqgis-processing

I have a vector dataset of rural broadband data-points (how fast, etc.) and I'd like to explore if there are clusters of points with similar characteristics, and to plot polygons encompassing them.

For example, I may have 45,000 points in a single PostGIS dataset distributed over a landscape. I want to identify clusters which lay within x km of each other and where the speed is below y kbps, and to produce convex hulls for each qualifying cluster.

Is there a simple way of doing this in QGIS, for example?

Best Answer

I've combined bits from several suggestions and added a bit of my own and found a solution which works well for me - and all from within QGis!

I first ran a PostGis SELECT to find the points which have the right common attributes and lie within x km of each other:

SELECT DISTINCT s1.postcode,s1.the_geom, s1.gid FROM broadband_data AS s1 JOIN broadband_data AS s2 ON ST_DWithin(s1.the_geom, s2.the_geom,1000) WHERE s1.postcode != s2.postcode AND s1.fastest_broadband <= 2000

(Pretty much straight from Manning's very good PostGis in Action book, only adding a self-join)

I then loaded Carson Farmer's ManageR plugin, and imported the layer. From here I followed the suggested PAM clustering process here, and exported the result to a shape file, on which Convex Hulls were calculated in seconds using fTools (Carson does get around!).

Related Solutions

PostGIS – Using GROUP BY for Linear Spatial Clusters

I'm not at a computer that has access to PostGIS right now, but I feel as though this algorithm might work. Of course if you have vertical groups, you would need to use an exclusion or inclusion clause for ST_Y().

DECLARE @totalUnique int = 0
DECLARE @lastUnique int = 1

CREATE TABLE #TABLEX (ID1 int, ID2 int)
CREATE TABLE #TABLEX2 (ID1 int, ID2 int)

--Get distances of objects
INSERT INTO #TABLEX
SELECT ID1, ID2
FROM   (
         SELECT T1.ID AS ID1, 
                T2.ID AS ID2
         FROM   BaseTable AS T1
                INNER JOIN
                BaseTable AS T2
                    ON  ST_Distance(T1.Shape, T2.Shape) <= SeparationDistance
       ) AS X

--Loop for as long as new connections can be made
WHILE(@lastUnique <> @totalUnique)
BEGIN
  --Count the number of current connections
  SELECT @lastUnique = COUNT(*)
  FROM (
         SELECT * FROM #TABLEX
         GROUP BY ID1, ID2
       ) AS XX 

  --Look for new connections via current known paths
  INSERT INTO #TABLEX (ID1, ID2)
  SELECT A.ID1, B.ID2
  FROM #TABLEX AS A
       INNER JOIN
       #TABLEX AS B
       ON A.ID2 = B.ID1
          AND
          A.ID1 <> B.ID2

  --Count the number of current connections   
  SELECT @totalUnique = COUNT(*)
  FROM (
         SELECT * FROM #TABLEX
         GROUP BY ID1, ID2
       ) AS XX

  --Group each path set by the lowest ID
  INSERT INTO #TABLEX2(ID1, ID2)
  SELECT MIN(ID1) AS theGroup, ID2
  FROM   #TABLEX
  GROUP BY ID2

  TRUNCATE TABLE #TABLEX

  --Reload our new path sets
  INSERT INTO #TABLEX (ID1, ID2)
  SELECT ID1, ID2 FROM #TABLEX2

  TRUNCATE TABLE #TABLEX2
END

--Show final results        
SELECT ID1 AS theGroup, ID2
FROM   #TABLEX

DROP TABLE #TABLEX
DROP TABLE #TABLEX2

[GIS] Clustering geographic points

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.

Best Answer

Related Solutions

PostGIS – Using GROUP BY for Linear Spatial Clusters

[GIS] Clustering geographic points

Related Question