Open Access

ARTICLE

Density Clustering Algorithm Based on KD-Tree and Voting Rules

by Hui Du, Zhiyuan Hu^*, Depeng Lu, Jingrui Liu

The College of Computer Science and Engineering, Northwest Normal University, Lanzhou, 730070, China

* Corresponding Author: Zhiyuan Hu. Email:

Computers, Materials & Continua 2024, 79(2), 3239-3259. https://doi.org/10.32604/cmc.2024.046314

Received 26 September 2023; Accepted 22 December 2023; Issue published 15 May 2024

Abstract

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

---

Keywords

---