Clustering based on sequential representation of minimum spanning tree
Guanwei Wang, Chunxia Zhang, Jian Zhuang, Dehong Yu · 2011
This paper aims to solve three types of clustering problems (i.e., well-separated, relaxed well separated and connected ones) based on minimum spanning tree (MST) technique. Through analyzing the characteristics of each clustering problem, a good property of inconsistent edges is found and reformulated with several theorems based on the sequential representation of MST. Meanwhile, a new MST-based clustering algorithm SR-MSTC is proposed with purpose to reduce computational cost and to overcome the mutual influence of inconsistent edges. Some experiments demonstrate that SR-MSTC works well to identify different types of clusters embodied in the given data while having lower computational complexity.