A Clustering Algorithm Based on the Combination of MST and Cluster Centers

Abstract

Most of traditional MST-based (Minimum spanning tree) clustering algorithms cluster by removing the inconsistent edge. The performances of these algorithms are influenced by the shape of clusters. To address this issue, we proposed a novel cluster algorithm based on the combination of MST and cluster centers (iGMST). Firstly, the cluster centers are determined by the Geodesic distance between vertex pair in the MST. Then, the inconsistent edge is defined along the path between cluster center pair. The experimental results on the synthetic and real data sets show that iGMST is better than k-means++, hierarchical clustering, and spectral clustering. Besides, iGMST can discover clusters of different shape steadily.