MSTI: A New Clustering Validity Index for Hierarchical Clustering
Peng Li, Feng Liu, Er-Zhou Zhua · 2018
The clustering validity index (CVI) is an important tool to measure the clustering effect and determine the optimal clustering number (K_opt). However, most of the existing CVIs cannot properly deal with some non-spherical distributions data sets and data sets with great differences in sample size and density among clusters. This paper proposes a revised hierarchical clustering algorithm based on the new clustering validity index (MSTI). Firstly, the new index uses spanning tree related knowledge to construct minimum spanning tree in inter clusters and maximum spanning tree in intra clusters. Then, the new MSTI is defined as the ratio of the cost of the minimum spanning tree among clusters to the cost of maximum spanning tree in each cluster. Under this circumstance, the K_opt is acquired when the above ratio reaches the biggest value. Finally, the new algorithm for optimizing and determining the K_opt is designed by leveraging the Average-Linkage hierarchical clustering algorithm and the new proposed MSTI. We compared the new algorithm integrated with MSTI with the traditional algorithms integrated with 4 commonly used CVIs by utilizing 3 simulated datasets and 3 UCI datasets. The experimental results have shown that the new proposed algorithm integrated with MSTI is effective and accurate in determining the K_opt and the optimal clustering partition for all the tested data sets.