## Cluster Analysis based on point density

### Cluster Analysis based on point density

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

http://www.yqcomputer.com/ ~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
suggestions?

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

Thank you,
Michael.

### Cluster Analysis based on point density

Micheal,

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
http://www.yqcomputer.com/

HTH

Greg.

### Cluster Analysis based on point density

Greg,

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.

/Michael.