Unsupervised Niche Clustering: Discovering an Unknown Number of Clusters in Noisy Data Sets

As a valuable unsupervised learning tool, clustering is crucial to many applications in pattern recognition, machine learning, and data mining. Evolutionary techniques have been used with success as global searchers in difficult problems, particularly in the optimization of non-differentiable functions. Hence, they can improve clustering. However, existing

evolutionary

clustering techniques suffer from one or more of the following shortcomings: (i) they are

not robust

in the presence of noise, (ii) they assume a

known

number of clusters, and (iii) the size of the search space

explodes exponentially

with the number of clusters, or with the number of data points. We present a

robust

clustering algorithm, called the

Unsupervised Niche Clustering algorithm (UNC)

, that overcomes all the above difficulties. UNC can successfully find dense areas (clusters) in feature space and determines the

number

of clusters

automatically

. The clustering problem is converted to a multimodal function optimization problem within the context of Genetic Niching. Robust cluster scale estimates are

dynamically

estimated using a hybrid learning scheme coupled with the genetic optimization of the cluster centers, to adapt to clusters of different sizes and noise contamination rates. Genetic optimization enables our approach to handle data with both numeric and qualitative attributes, and general

subjective, non metric, even non-differentiable

dissimilarity measures.