Effectively clustering by finding density backbone based-on kNN

Clustering plays an important role in discovering underlying patterns of data points according to their similarities. Many advanced algorithms have difficulty when dealing with variable clusters. In this paper, we propose a simple but effective clustering algorithm, CLUB. First, CLUB finds initial clusters based on mutual k nearest neighbours. Next, taking the initial clusters as input, it identifies the density backbones of clusters based on k nearest neighbours. Then, it yields final clusters by assigning each unlabelled point to the cluster which the unlabelled point's nearest higher-density-neighbour belongs to. To comprehensively demonstrate the performance of CLUB, we benchmark CLUB with six baselines including three classical and three state-of-the-art methods, on nine two-dimensional various-sized datasets containing clusters with various shapes and densities, as well as seven widely-used multi-dimensional datasets. In addition, we also use Olivetti Face dataset to illustrate the effectiveness of our method on face recognition. Experimental results indicate that CLUB outperforms the six compared algorithms in most cases. HighlightsCLUB can easily find clusters with various densities, shapes and sizes.A new density computing method is presented.A novel cluster backbones identification method is proposed.Comprehensive experiments are performed to verify the performance of CLUB.