Scalable clustering by aggregating representatives in hierarchical groups. (April 2023)

• Record Type: Journal Article
• Authors: Xie, Wen-Bo; Liu, Zhen; Das, Debarati; Chen, Bin; Srivastava, Jaideep
• Is Part Of: Pattern recognition. Volume 136(2023)
• Publication Date: 2023-04
• Subjects: Hierarchical clustering -- Election tree -- Representative node -- Root; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2022.109230
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: A scalable hierarchical clustering framework for discrete data segments is proposed. Multiple indices are proposed to effectively spot the most representative node in each sub-MST. Swapping data points in overlap areas between pairwise sub-MSTs ensures the accuracy of the hierarchical clustering across multiple data segments. The proposed model provides a good balance between accuracy and scalability of hierarchical clustering. Abstract: Appropriately handling the scalability of clustering is a long-standing challenge for the study of clustering techniques and is of fundamental interest to researchers in the community of data mining and knowledge discovery. In comparison to other clustering methods, hierarchical clustering demonstrates better interpretability of clustering results but poor scalability while handling large-scale data. Thus, more comprehensive studies on this problem need to be conducted. This paper develops a new scalable hierarchical clustering model called Election Tree, which can detect the most representative point for each sub-cluster via the process of node election in split data and adjust the members in sub-clusters by the operations of node merging and swap. Extensive experiments on real-world datasets reveal that the proposed computational framework has better clustering accuracy as opposed to the competing baseline methods. Meanwhile, with respect to the scalability tests on incremental synthetic datasets, the results show that the new model has a significantly lower time consumption than the state-of-the-art hierarchical clustering models such as PERCH, GRINCH, SCC and other classic baselines.