Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I'm looking for spatial clustering algorithm for using it within PostGIS-enabled database for point features. I'm going to write plpgsql function that takes distance between points within the same cluster as input. At the output function returns array of clusters. The most obvious solution is to build buffer zones specified distance around the feature and search for features into this buffer. If such features exist then continue to build a buffer around them, etc. If such features not exist that means cluster building is completed. Maybe there are some clever solutions?

share|improve this question
3  
There is a huge variety of clustering methods because of the differing nature of data and different purposes of clustering. For an overview of what's out there and for some easy reading about what others are doing to cluster distance matrices, search the CV@SE site. In fact, "choosing clustering method" is almost an exact duplicate of yours and has good answers. –  whuber Jun 28 '11 at 16:16
7  
+1 to the question because finding an actual PostGIS SQL example instead of links to algorithms is mission impossible for anything other than basic grid clustering, especially for more exotic clusterings like MCL –  wildpeaks Jun 29 '11 at 18:56

3 Answers 3

up vote 38 down vote accepted
+50

Here is the kmeans-postgresql solution.

Installation: You need to have PostgreSQL 8.4 or greater on a POSIX host system (I wouldn't know where to start for MS Windows). If you have this installed from packages, make sure you also have the development packages (e.g., postgresql-devel for CentOS). Download and extract:

wget http://api.pgxn.org/dist/kmeans/1.1.0/kmeans-1.1.0.zip
unzip kmeans-1.1.0.zip
cd kmeans-1.1.0/

Before building, you need to set the USE_PGXS environment variable (my previous post instructed to delete this part of the Makefile, which wasn't the best of options). One of these two commands should work for your Unix shell:

# bash
export USE_PGXS=1
# csh
setenv USE_PGXS 1

Now build and install the extension:

make
make install
psql -f /usr/share/pgsql/contrib/kmeans.sql -U postgres -D postgis

(Note: I also tried this with Ubuntu 10.10, but no luck, as the path in pg_config --pgxs does not exist! This is probably an Ubuntu packaging bug)

Usage/Example: You should have a table of points somewhere (I drew a bunch of pseudo random points in QGIS). Here is an example with what I did:

SELECT kmeans, count(*), ST_Centroid(ST_Collect(geom)) AS geom
FROM (
  SELECT kmeans(ARRAY[ST_X(geom), ST_Y(geom)], 5) OVER (), geom
  FROM rand_point
) AS ksub
GROUP BY kmeans
ORDER BY kmeans;

the 5 I provided in the second argument of the kmeans window function is the K integer to produce five clusters. You can change this to whatever integer you want.

Below is the 31 pseudo random points I drew and the five centroids with the label showing the count in each cluster. This was created using the above SQL query.

Kmeans


You can also attempt to illustrate where these clusters are with ST_MinimumBoundingCircle:

SELECT kmeans, ST_MinimumBoundingCircle(ST_Collect(geom)) AS circle
FROM (
  SELECT kmeans(ARRAY[ST_X(geom), ST_Y(geom)], 5) OVER (), geom
  FROM rand_point
) AS ksub
GROUP BY kmeans
ORDER BY kmeans;

Kmeans2

share|improve this answer
1  
Great, these modifications will help for the installation :-) However I fear I can't really use that extension in the end because (if I understood correctly), it needs an hardcoded magic number of clusters, which is fine with static data precause you can fine-tune it in advance but wouldn't fit me for clustering arbitrary (due to various filters) data sets, e.g. the large gap in the 10-points cluster on the last image. However this will help other people too because (afaik), this is the only existing SQL example (except the one liners on the extension's homepage) for that extension. –  wildpeaks Jul 4 '11 at 11:19
    
(ah you replied at the same time I deleted the previous comment to reformulate it, sorry) –  wildpeaks Jul 4 '11 at 11:20
4  
For kmeans clustering you need to specify the number of clusters in advance; I'm curious if there are alternative algorithms where the number of clusters is not required though. –  djq Jul 10 '11 at 15:09
1  
Version 1.1.0 is now available: api.pgxn.org/dist/kmeans/1.1.0/kmeans-1.1.0.zip –  djq Aug 26 '12 at 21:26

I've written function that calculates clusters of features based on distance between them and build convex hull over this features:

CREATE OR REPLACE FUNCTION get_domains_n(lname varchar, geom varchar, gid varchar, radius numeric)
    RETURNS SETOF record AS
$$
DECLARE
    lid_new    integer;
    dmn_number integer := 1;
    outr       record;
    innr       record;
    r          record;
BEGIN

    DROP TABLE IF EXISTS tmp;
    EXECUTE 'CREATE TEMPORARY TABLE tmp AS SELECT '||gid||', '||geom||' FROM '||lname;
    ALTER TABLE tmp ADD COLUMN dmn integer;
    ALTER TABLE tmp ADD COLUMN chk boolean DEFAULT FALSE;
    EXECUTE 'UPDATE tmp SET dmn = '||dmn_number||', chk = FALSE WHERE '||gid||' = (SELECT MIN('||gid||') FROM tmp)';

    LOOP
        LOOP
            FOR outr IN EXECUTE 'SELECT '||gid||' AS gid, '||geom||' AS geom FROM tmp WHERE dmn = '||dmn_number||' AND NOT chk' LOOP
                FOR innr IN EXECUTE 'SELECT '||gid||' AS gid, '||geom||' AS geom FROM tmp WHERE dmn IS NULL' LOOP
                    IF ST_DWithin(ST_Transform(ST_SetSRID(outr.geom, 4326), 3785), ST_Transform(ST_SetSRID(innr.geom, 4326), 3785), radius) THEN
                    --IF ST_DWithin(outr.geom, innr.geom, radius) THEN
                        EXECUTE 'UPDATE tmp SET dmn = '||dmn_number||', chk = FALSE WHERE '||gid||' = '||innr.gid;
                    END IF;
                END LOOP;
                EXECUTE 'UPDATE tmp SET chk = TRUE WHERE '||gid||' = '||outr.gid;
            END LOOP;
            SELECT INTO r dmn FROM tmp WHERE dmn = dmn_number AND NOT chk LIMIT 1;
            EXIT WHEN NOT FOUND;
       END LOOP;
       SELECT INTO r dmn FROM tmp WHERE dmn IS NULL LIMIT 1;
       IF FOUND THEN
           dmn_number := dmn_number + 1;
           EXECUTE 'UPDATE tmp SET dmn = '||dmn_number||', chk = FALSE WHERE '||gid||' = (SELECT MIN('||gid||') FROM tmp WHERE dmn IS NULL LIMIT 1)';
       ELSE
           EXIT;
       END IF;
    END LOOP;

    RETURN QUERY EXECUTE 'SELECT ST_ConvexHull(ST_Collect('||geom||')) FROM tmp GROUP by dmn';

    RETURN;
END
$$
LANGUAGE plpgsql;

Example of using this function:

SELECT * FROM get_domains_n('poi', 'wkb_geometry', 'ogc_fid', 14000) AS g(gm geometry)

'poi' - name of layer, 'wkb_geometry' - name of geometry column, 'ogc_fid' - primary key of table, 14000 - cluster distance.

The result of using this function:

enter image description here

share|improve this answer
    
Great! Could you add an example of how to user your function too? Thanks! –  underdark Jul 5 '11 at 7:24
1  
I've modified little bit of source code and have added example of using function. –  drnextgis Jul 5 '11 at 9:28
    
Just tried using this on postgres 9.1 and line " FOR innr IN EXECUTE 'SELECT '||gid||' AS gid, '||geom||' AS geom FROM tmp WHERE dmn IS NULL' LOOP " yields the following error. Any ideas ? ERROR: set-valued function called in context that cannot accept a set –  bitbox Oct 18 '12 at 11:11
    
I'm unsure as how to use this code in PG (PostGIS n00b) in my table. where could I start to understand this syntax? I have a table with lats and lons that I want to cluster –  mga May 5 at 20:41
    
First of all you have to build geometry column within your table, not to store lonlat separately and make column with unique values (IDs). –  drnextgis May 6 at 10:44

So far, the most promising I found is this extension for K-means clustering as a window function: http://pgxn.org/dist/kmeans/

However I haven't been able to install it successfully yet.


Otherwise, for basic grid clustering, you could use SnapToGrid.

SELECT
    array_agg(id) AS ids,
    COUNT( position ) AS count,
    ST_AsText( ST_Centroid(ST_Collect( position )) ) AS center,
FROM mytable
GROUP BY
    ST_SnapToGrid( ST_SetSRID(position, 4326), 22.25, 11.125)
ORDER BY
    count DESC
;
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.