Density Clustering Algorithm Based on KD-Tree and Voting Rules

作     者：Hui Du Zhiyuan Hu Depeng Lu Jingrui Liu 

作者机构：The College of Computer Science and EngineeringNorthwest Normal UniversityLanzhou730070China 

出 版 物：《Computers, Materials & Continua》 (计算机、材料和连续体（英文）)

年 卷 期：2024年第79卷第5期

页      面：3239-3259页

核心收录：

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

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

主　　题：Density peaks clustering KD-Tree K-nearest neighbors voting rules 

摘      要：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.