Adaptive Wavelet Clustering for Highly Noisy Data
This addresses the challenge of mining arbitrarily shaped clusters in noisy data for real-world applications, representing an incremental improvement over existing wavelet-based methods.
The paper tackles the problem of unsupervised clustering in highly noisy datasets by proposing AdaWave, an adaptive wavelet-based algorithm that is parameter-free, deterministic, and linear-time, achieving effective clustering on synthetic and natural datasets.
In this paper we make progress on the unsupervised task of mining arbitrarily shaped clusters in highly noisy datasets, which is a task present in many real-world applications. Based on the fundamental work that first applies a wavelet transform to data clustering, we propose an adaptive clustering algorithm, denoted as AdaWave, which exhibits favorable characteristics for clustering. By a self-adaptive thresholding technique, AdaWave is parameter free and can handle data in various situations. It is deterministic, fast in linear time, order-insensitive, shape-insensitive, robust to highly noisy data, and requires no pre-knowledge on data models. Moreover, AdaWave inherits the ability from the wavelet transform to cluster data in different resolutions. We adopt the "grid labeling" data structure to drastically reduce the memory consumption of the wavelet transform so that AdaWave can be used for relatively high dimensional data. Experiments on synthetic as well as natural datasets demonstrate the effectiveness and efficiency of our proposed method.