Improving data field hierarchical clustering using Barnes–Hut algorithm

• We propose Barnes–Hut based data field hierarchical clustering algorithm.
• Our algorithm does not need to tune the parameters.
• We improve the efficiency of traditional data field hierarchical clustering algorithm.

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(n2). In this study, we improve the force computation efficiency of DFHCA to O(nlog 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.