Robust clustering based on dominant sets

Clustering is an important unsupervised learning approach and widely used in pattern recognition, data mining and image processing, etc. Different from existing clustering algorithms based on partitioning within data, dominant sets clustering extracts clusters in a sequential fashion. Based on graph-theoretic concept of a cluster, dominant sets clustering can be accomplished with a game dynamics efficiently while being able to determine the number of clusters automatically. However, we have observed that the definition of dominant set over weights the importance of high intra-cluster similarity. Consequently, dominant sets clustering is found to be sensitive to similarity parameters and show the tendency to generate over-segmented clustering results. In order to solve these problems, in this paper we present a cluster extension algorithm by making use of the relationship of intra-cluster and inter-cluster similarity. In experiments on eight datasets, our algorithm performs evidently better than the original dominant sets algorithm, and comparably to other state-of-the-art clustering algorithms.