  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.
