WaveCluster: a wavelet-based clustering approach for spatial data in very large databases

Many applications require the management of spatial data in a multidimensio nal feature space. Clustering large spatial databases is an important probl em, which tries to find the densely populated regions in the feature space to be used in data mining, knowledge discovery, or efficient information re trieval. A good clustering approach should be efficient and detect clusters of arbitrary shape. It must be insensitive to the noise (outliers) and the order of input data. We propose WaveCluster, a novel clustering approach b ased on wavelet transforms, which satisfies all the above requirements. Usi ng the multiresolution property of wavelet transforms, we can effectively i dentify arbitrarily shaped clusters at different degrees of detail. We also demonstrate that WaveCluster is highly efficient in terms of time complexi ty. Experimental results on very large datasets are presented, which show t he efficiency and effectiveness of the proposed approach compared to the ot her recent clustering methods.