An Effective Divide-and-Merge Method for Hierarchical Clustering

Hierarchical clustering methods have exhibited extremely high performance in a wide variety of learning tasks. However, when processing today’s complex data sets they still face many challenges, such as the lack of the prior knowledge and difficulty in parameter tuning. In order to solve these problems, this paper presents an effective hierarchical clustering algorithm called DMHC, which is based on the divide-and-merge methodology. In DMHC, a data set is first divided into some small homogeneous subsets called data blocks, and then the cluster hierarchy is built according to the merging relationship of these data blocks. This approach needs less prior knowledge and its parameters can be easily tuned. It can not only effectively discover the clusters and the noises in a computationally efficient way, but also provide the cluster hierarchy. Experimental results on several UCI and real world data sets demonstrate the effectiveness of the proposed algorithm.