Multilevel Paradigm for Hierarchical Clustering

Date of Submission: 
October 10, 1998
Report Number: 
In this paper we present a new multilevel hierarchical clustering algorithm that builds upon recent advances in clustering and graph partitioning. This algorithm combines traditional hierarachical clustering with multilevel refinement that has been found very effective for computing min-cut k-way partitioning of graphs. Our experimental results demonstrate that this algorithm produces clustering solutions that are consistently and significantly better than those produced by hierarchical clustering algorithms alone. Furthermore, our algorithm has the additional advantage of being extremely fast, as it operates on a sparse similarity matrix. The amount of time required by our algorithm ranged from one second for a data set with 358 items, to 40 seconds for a data set with 9133 items on a Pentium II PC.