Density Clustering Algorithm Based on KD-Tree and Voting Rules  

作　　者：Hui Du Zhiyuan Hu Depeng Lu Jingrui Liu 

机构地区：[1]The College of Computer Science and Engineering,Northwest Normal University,Lanzhou,730070,China

出　　处：《Computers, Materials & Continua》2024年第5期3239-3259,共21页计算机、材料和连续体（英文）

基　　金：National Natural Science Foundation of China Nos.61962054 and 62372353.

摘　　要：Traditional clustering algorithms often struggle to produce satisfactory results when dealing with datasets withuneven density. Additionally, they incur substantial computational costs when applied to high-dimensional datadue to calculating similarity matrices. To alleviate these issues, we employ the KD-Tree to partition the dataset andcompute the K-nearest neighbors (KNN) density for each point, thereby avoiding the computation of similaritymatrices. Moreover, we apply the rules of voting elections, treating each data point as a voter and casting a votefor the point with the highest density among its KNN. By utilizing the vote counts of each point, we develop thestrategy for classifying noise points and potential cluster centers, allowing the algorithm to identify clusters withuneven density and complex shapes. Additionally, we define the concept of “adhesive points” between two clustersto merge adjacent clusters that have similar densities. This process helps us identify the optimal number of clustersautomatically. Experimental results indicate that our algorithm not only improves the efficiency of clustering butalso increases its accuracy.

关 键 词：Density peaks clustering KD-TREE K-nearest neighbors voting rules 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]