Gravitational clustering: a new approach based on the spatial distribution of the points

We describe here a new clustering method based on the notion of a. force of attraction between each pair of points, and without using a "similarity" measure. The clusters are formed by allowing each point to move slowly under the resultant effect of all the forces on it, and by merging two points when they become too close to each other. This model can be regarded as a refinement of both the nearest-neighbor method and the fuzzy c-means method, and it avoids some of the pitfalls of both of those methods. It produces a complete cluster-hierarchy in O(N-3) time for N points. We illustrate the method with several examples. (C) 1999 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.