Cluster Analysis based on point density

Cluster Analysis based on point density

Post by Michael D » Sat, 23 Jul 2005 01:11:49

Hi all,

I am interested in doing a cluster analysis on points in the 2D plane based
on point density (i.e. the number of points per area).

Specifically, given a desired point density D, I want to compute a set of
clusters such that:

1) Each cluster is as big as possible
2) Each cluster contains at least D number of points per unit of area.

As a crude mock-up example involving two clusters, see the illustration in
the following link: ~mdp/cluster_illustration.GIF

There are clearly many variations of cluster analysis around, but I haven't
come across any that will do exactly what I want. For instance I do not want
the number of clusters to be given in advance as in the k-means clustering
method, and I do not necessarily want all points to be included in a cluster
(i.e. the set of clusters need not be a partition of the set of points).

I have been trying to devise a algorithm based on nearest-neighbour
distances and some statistical measures, but I think that an existing (and
much better) solution must be available for this problem. Anyone have any

Any pointers to litterature, online material or other news groups would be
greatly appreciated!

Thank you,

Cluster Analysis based on point density

Post by Gregs » Sun, 24 Jul 2005 18:38:39


I'm not sure if this will help but have you looked at the cluster
analysis methods that are available in the CRIMESTAT program? For more
details and to download it look here -




Cluster Analysis based on point density

Post by Michael Da » Tue, 02 Aug 2005 17:34:06


Thank you for the suggestion. CRIMESTAT contains a lot of interesting
algorithms, but the description of these is not readily available, making it
difficult to implement them.

For the record, I was suggested (by Peter Halls) to look into the method
described in the following paper:

Estivill-Castro & Lee (Estivill-Castro, V., & Lee, I., 2002, Argument free
clustering for large spatial point- data sets via boundary extraction from
Delaunay Diagram. CEUS 26 (2002) 315 - 334.).

This seems to be exactly what I want.