Improving data field hierarchical clustering using Barnes-Hut algorithm

作     者：Zhuo, Zhongliu Zhang, Xiaosong Niu, Weina Yang, Guowu Zhang, Jingzhong 

作者机构：Univ Elect Sci & Technol China Sch Engn & Comp Sci 2006 Xiyuan Ave Chengdu 6111731 Peoples R China 

出 版 物：《PATTERN RECOGNITION LETTERS》 (模式识别快报)

年 卷 期：2016年第80卷第0期

页      面：113-120页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：major basic scientific research project in Sichuan province [2016JY0007] National Natural Science Foundation of China 

主　　题：Barnes-Hut algorithm Data field Hierarchical clustering Computation efficiency 

摘      要：Traditional Data Field Hierarchical Clustering Algorithm (DFHCA) uses brute force method to compute the forces exert on each object. The computation complexity increases as O(n(2)). In this study, we improve the force computation efficiency of DFHCA to O (n log n). We use the Barnes-Hut tree to reduce the number of force computation by approximating far away particles with their center of mass. And compared with traditional method, our method does not need to tune the parameters. In our implementation, we discuss two different merging strategies. Experimental results show that the proposed method could improve the computation efficiency under the same settings. We also find that DFHCA-M merging strategy converges faster than DFHCA-S merging strategy. Finally, we compare and analyze the time complexity and space complexity of our algorithm. (C) 2016 Elsevier B.V. All rights reserved.