基于最小生成树的半监督聚类算法

Most of the existing semi-supervised clustering algorithms depend on pairwise constraints, and they usually use lots of priori knowledge to improve their accuracies. In this paper, we use another semi-supervised method called label propagation to show how labeled objects help the algorithms to detect clusters. We propose two new semi-supervised algorithms which have the ability to discover clusters of diverse density and arbitrary shape, named MST-based Semi-Supervised clustering using K-labeled objects ( K-SSMST ) and MST-based Semi-Supervised clustering using M-labeled objects ( M-SSMST ). Based on minimum spanning tree ( K-MST ), the two algorithms assign objects to clusters by using labeled objects. K-SSMST algorithm could automatically find natural clusters in a dataset. It does not need any input parameter and only requires K labeled data objects where K is the number of clusters. M-SSMST can detect new clusters when the number of labeled data M is less than K. It only requires one input parameter. Our algorithms were tested on both various artificial datasets and UCI datasets. The results demonstrate the accuracy when compared with other supervised and semi-supervised approaches.