Abstract

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 help detect clusters. We propose two new semi-supervised algorithms named K-SSMST and M-SSMST. Both of them aim to discover clusters of diverse density and arbitrary shape. Based on Minimum Spanning Tree's algorithm variant, K-SSMST can automatically find natural clusters in a dataset by using K labeled data objects where K is the number of clusters. M-SSMST can detect new clusters with insufficient semi-supervised information. Our algorithms have been tested on various artificial and UCI datasets. The results demonstrate that the algorithm's accuracy is better than other supervised and semi-supervised approaches.

Keywords

MSC

62H30, 91C20

Cite this article

@article{cai-111222,
  author  = {Xiaoyun Chen and Mengmeng Huo and Yangyang Liu},
  title   = {MST-Based Semi-Supervised Clustering Using M-Labeled Objects},
  journal = {Computing and Informatics},
  volume  = {31},
  number  = {6+},
  pages   = {1557--1574},
  year    = {2012},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2012/6%2B/mst-based-semi-supervised-clustering-using-m-labeled-objects/}
}
Download .bib