A Clustering Algorithm Based on Local Relative Density
Yujuan Zou, Zhijian Wang, Xiangchen Wang, Taizhi Lv · Electronics · 2025
DBSCAN and DPC are typical density-based clustering algorithms. These two algorithms have their drawbacks, such as difficulty in clustering when there are significant differences in density between clusters. This study proposes a clustering algorithm, RDBSCAN, which is based on local relative density, drawing on the extension strategy of DBSCAN and the allocation mechanism of DPC. The algorithm first uses k-nearest neighbors to calculate the original local density, then sorts the points in descending order of this density. It then selects the point with the highest original local density from the unprocessed points as the local center of the next cluster. Based on this local center, RDBSCAN calculates the local relative density, determines the core objects, and performs cluster expansion. Drawing on the allocation mechanism of DPC, the algorithm performs a secondary allocation for points in clusters that are too small to complete the final clustering. Comparative experiments using RDBSCAN and eight other clustering algorithms were conducted, and the test results show that RDBSCAN ranks first in clustering performance metrics among all algorithms on synthetic datasets and second on real-world datasets.