A Semi-supervised Clustering Method through Bottleneck Distance Exploration

Semi-supervised clustering is one of the most active research area in machine learning and pattern recognition, which can improve the performance of unsupervised clustering efficiently. This paper focuses on exploiting both the label information of a few labeled samples and the spatial distribution information of large amount of unlabeled samples. We proposed a new semi-supervised clustering method, named Bottleneck Distance based Semi-supervised Clustering (BDSC), which is based on the idea of label propagation and can perform clustering with no parameters. BDSC works by firstly obtaining small amount of labeled samples for each class. Then, a minimum spanning tree is constructed from both labeled and unlabeled samples, where the distances between an unlabeled sample and labeled samples are computed to get the bottleneck distance for each unlabeled sample. Finally, labels are propagated by comparing the bottleneck distances. Experimental results demonstrate that the proposed technique outperforms classical clustering algorithms with respect to the precision and the capability of recognizing nonspherical-shaped clusters.