Multi-density DBSCAN Algorithm Based on Density Levels Partitioning

摘要

DBSCAN is a typical density-based clustering algorithm, it has an advantage of discovering clusters of different shapes and sizes along with detection of outliers. However, the parameter Eps and MinPts are hard to determine but directly influence the clustering result. Furthermore, the adoption of global parameters makes it an unsuitable one for datasets with varied densities. To address these problems, this paper proposes a multi-density clustering method called DBSCAN-DLP (Multi-density DBSCAN based on Density Levels Partitioning). DBSCAN-DLP partitions a dataset into different density level sets by analyzing the statistical characteristics of its density variation, and then estimates Eps for each density level set, finally adopts DBSCAN clustering on each density level set with corresponding Eps to get clustering results. Extensive theoretical analysis and experimental results on both synthetic and real-world datasets confirm that proposed algorithm is efficient in clustering multi-density datasets.