Cluster merging and splitting in hierarchical clustering algorithms Chris H. Q. Ding and Xiaofeng He   View Paper (PDF)   Return to Main-Track Regular Papers Abstract Hierarchical clustering constructs a hierarchy of clusters either repeatedly mer in two smaller clusters into a larger one or splittin a larger cluster into smaller ones. The crucial step is how to best select the next cluster(s) to split or merge. Here we provide a comprehensive analysis of selection methods and propose several new methods. We perform extensive clustering experiments to test 8 selection methods, and ?nd that the average similarity is the best method in divisive clustering and MinMax linkage is the best in agglomerative Cluster balance is a key factor to achieve good performance. We also introduce the concept of objective function saturation and clustering target distance to effectively assess the quality of clustering. DiSC'03 © 2003 Association for Computing Machinery