Clustering spatial data using random walks
Authors:
Open Access
- 26 August 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 281-286
Abstract
Discovering significant patterns that exist implicitly in huge spatial databases is an important computational task. A common approach to this problem is to use cluster analysis. We propose a novel approach to clustering, based on the deterministic analysis of random walks on a weighted graph generated from the data. Our approach can decompose the data into arbitrarily shaped clusters of different sizes and densities, overcoming noise and outliers that may blur the natural decomposition of the data. The method requires only O(n log n) time, and one of its variants needs only constant space.Keywords
This publication has 4 references indexed in Scilit:
- Stochastic image segmentation by typical cuts2003
- Chameleon: hierarchical clustering using dynamic modelingComputer, 1999
- Clustering and knowledge discovery in spatial databasesVistas in Astronomy, 1997
- Algorithms for proximity problems in higher dimensionsComputational Geometry, 1996