Clustering with Prim's sequential representation of minimum spanning tree

- We investigate MST-based algorithms aiming to detect three types of clusters.
- An inconsistent edge is found to dominate two subtrees at its two end vertices.
- Prim's sequential representation of MST is proposed and studied.
- Two PSR-MST based clustering schemes are developed.
- Experiments on some data sets show their effectiveness and efficiency.

Minimum spanning tree (MST) has been proven to be a powerful tool for performing cluster analysis. In this paper, Prim's sequential representation of MST (PSR-MST) is introduced to solve clustering problems. After investigating the characteristics of MST-based clustering algorithms, it is found that inconsistent edges in an MST dominate two subtrees at their two end vertices. Meanwhile, an edge which is longer than the neighbors on its two sides in a PSR-MST is discovered to dominate two subtrees at its two end vertices. With these findings, we propose two PSR-MST based clustering schemes with one being a hierarchical scheme and the other being a K-partition method which requests users to specify only number of clusters. The experimental results obtained on some synthetic and real-world data sets show that the core procedure of the new clustering schemes finding inconsistent edges from a PSR-MST is effective. Moreover, the K-partition method based on PSR-MST is observed to outperform all the other compared algorithms in terms of clustering quality and time complexity.