Efficient agglomerative hierarchical clustering

• Published in: Expert systems with applications 2015-04, Vol.42 (5), p.2785-2797
• Main Authors: Bouguettaya, Athman, Yu, Qi, Liu, Xumin, Zhou, Xiangmin, Song, Andy
• Format: Article
• Language: English
• Subjects: Agglomeration; Centroids; Cluster analysis; Clustering; Clustering analysis; Coefficient of correlation; Computational efficiency; Construction; Construction costs; Data distribution; Data mining; Data points; Hierarchies; Hybrid clustering
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2014.09.054

•An efficient hybrid hierarchical clustering is proposed based on agglomerative method.•It performs consistently with different distance measures.•It performs consistently on data with different distributions and sizes. Hierarchical clustering is of great importance in data analytics especially because of the exponential growth of real-world data. Often these data are unlabelled and there is little prior domain knowledge available. One challenge in handling these huge data collections is the computational cost. In this paper, we aim to improve the efficiency by introducing a set of methods of agglomerative hierarchical clustering. Instead of building cluster hierarchies based on raw data points, our approach builds a hierarchy based on a group of centroids. These centroids represent a group of adjacent points in the data space. By this approach, feature extraction or dimensionality reduction is not required. To evaluate our approach, we have conducted a comprehensive experimental study. We tested the approach with different clustering methods (i.e., UPGMA and SLINK), data distributions, (i.e., normal and uniform), and distance measures (i.e., Euclidean and Canberra). The experimental results indicate that, using the centroid based approach, computational cost can be significantly reduced without compromising the clustering performance. The performance of this approach is relatively consistent regardless the variation of the settings, i.e., clustering methods, data distributions, and distance measures.