clustering

This module contains functions that perform clustering on geographies.

CREATE_CLUSTERDBSCAN

CREATE_CLUSTERDBSCAN(input, output_table, geom_column, epsilon, min_points [, partition_column])

Description

Takes a set of points as input and groups them into clusters using the DBSCAN algorithm, writing the result to a new table.

DBSCAN groups together points lying in dense neighborhoods and labels the rest as noise. Unlike k-means it does not require the number of clusters up front, it finds clusters of arbitrary shape, and it does not force every point into a cluster.

Input parameters

• input: VARCHAR name of the table or literal SQL query to be clustered.

• output_table: VARCHAR(MAX) qualified name of the output table, e.g. <my-schema>.<my-output-table>. It is replaced if it already exists.

• geom_column: VARCHAR name of the POINT column to be clustered, in SRID 4326 or 0.

• epsilon: FLOAT8 the search radius in meters.

• min_points: INT the minimum number of points, counting the point itself, that form a dense neighborhood.

• partition_column (optional): VARCHAR name of a column to cluster within, NULL values forming their own group. If omitted the whole input is one set.

Output

The output table contains all the columns of input plus cluster_id and pt_type.

cluster_id is a zero-based cluster index, restarting at zero in each partition. It is NULL for any point that is not in a cluster.

pt_type is the role of the point. A core point has at least min_points points within epsilon of it, counting itself, and core points within epsilon of each other belong to the same cluster. A border point is not a core point but lies within epsilon of one, so it joins that cluster without connecting it to any other. A noise point is neither. A skipped point was never clustered because its geometry was NULL, which is absent input rather than a result.

info

Cluster assignments match sklearn.cluster.DBSCAN with metric='haversine' for the same epsilon and min_points. Where DBSCAN is inherently ambiguous — a border point reachable from two clusters — this implementation always picks the cluster with the lowest canonical label, so results are deterministic and reproducible across runs.

warning

Only POINT geometries are supported. The input must not already have columns named cluster_id, pt_type or __carto_idx, so the output of one call cannot be fed straight back into another.

Runtime is driven by point density rather than row count: the cost grows with the number of points within epsilon of each other, so a large radius over a tightly packed area is the expensive case.

Examples

CALL carto.CREATE_CLUSTERDBSCAN('<my-schema>.<my-table>', '<my-schema>.<my-output-table>', 'geom', 100, 5);
-- The table `<my-schema>.<my-output-table>` will be created adding the columns
-- cluster_id and pt_type to those in `<my-schema>.<my-table>`.

CALL carto.CREATE_CLUSTERDBSCAN('SELECT * FROM <my-schema>.<my-table>', '<my-schema>.<my-output-table>', 'geom', 100, 5);
-- The table `<my-schema>.<my-output-table>` will be created adding the columns
-- cluster_id and pt_type to those returned in the input query.

CALL carto.CREATE_CLUSTERDBSCAN('<my-schema>.<my-table>', '<my-schema>.<my-output-table>', 'geom', 25, 3, 'store_id');
-- Points are clustered independently for each store_id, in a single call.

-- Keep only the clustered points and count them per cluster
SELECT cluster_id, COUNT(*) AS points
FROM <my-schema>.<my-output-table>
WHERE cluster_id IS NOT NULL
GROUP BY cluster_id
ORDER BY points DESC;

CREATE_CLUSTERKMEANS

CREATE_CLUSTERKMEANS(input, output_table, geom_column, number_of_clusters)

Description

Takes a set of points as input and partitions them into clusters using the k-means algorithm. Creates a new table with the same columns as input plus a cluster_id column with the cluster index for each of the input features.

Input parameters

• input: VARCHAR name of the table or literal SQL query to be clustered.

• output_table: VARCHAR(MAX) qualified name of the output table, e.g. <my-schema>.<my-output-table>. The process will fail if the table already exists.

• geom_column: VARCHAR name of the column to be clusterd.

• number_of_clusters: INT number of clusters that will be generated.

warning

Keep in mid that due to some restrictions in the Redshift VARCHAR size, the maximum number of features (points) allow to be clustered is around 2500.

Examples

CALL carto.CREATE_CLUSTERKMEANS('<my-schema>.<my-table>', '<my-schema>.<my-output-table>', 'geom', 5);
-- The table `<my-schema>.<my-output-table>` will be created
-- adding the column cluster_id to those in `<my-schema>.<my-table>`.

CALL carto.CREATE_CLUSTERKMEANS('SELECT * FROM <my-schema>.<my-table>', '<my-schema>.<my-output-table>', 'geom', 5);
-- The table `<my-schema>.<my-output-table>` will be created
-- adding the column cluster_id to those returned in the input query.

ST_CLUSTERKMEANS

ST_CLUSTERKMEANS(geog [, numberOfClusters])

Description

Takes a set of points as input and partitions them into clusters using the k-means algorithm. Returns an array of tuples with the cluster index for each of the input features and the input geometry.

Input parameters

• geog: GEOMETRY points to be clustered.

• numberOfClusters (optional): INT number of clusters that will be generated. It defaults to the square root of half the number of points (sqrt(<NUMBER OF POINTS>/2)). The output number of cluster cannot be greater to the number of distinct points of the geog.

Return type

SUPER: containing objects with cluster as the cluster id and geom as the geometry in GeoJSON format.

Examples

SELECT carto.ST_CLUSTERKMEANS(ST_GEOMFROMTEXT('MULTIPOINT ((0 0), (0 1), (5 0), (1 0))'));
-- {"cluster":0,"geom":{"type":"Point","coordinates":[0.0,0.0]}}
-- {"cluster":0,"geom":{"type":"Point","coordinates":[0.0,1.0]}}
-- {"cluster":0,"geom":{"type":"Point","coordinates":[5.0,0.0]}}
-- {"cluster":0,"geom":{"type":"Point","coordinates":[1.0,0.0]}}

SELECT carto.ST_CLUSTERKMEANS(ST_GEOMFROMTEXT('MULTIPOINT ((0 0), (0 1), (5 0), (1 0))'), 2);
-- {"cluster":0,"geom":{"type":"Point","coordinates":[0.0,0.0]}}
-- {"cluster":0,"geom":{"type":"Point","coordinates":[0.0,1.0]}}
-- {"cluster":1,"geom":{"type":"Point","coordinates":[5.0,0.0]}}
-- {"cluster":0,"geom":{"type":"Point","coordinates":[1.0,0.0]}}