An efficient density-based clustering algorithm using reverse nearest\n neighbour

2018/11/19 by Stiphen Chowdhury, Renato Cordeiro de Amorim, Chowdhury, Stiphen +1
Computer Science · #Advanced Clustering Algorithms Research #Data Management and Algorithms #Data Mining Algorithms and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.1811.07615

openalex publication_date 2018/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Density-based clustering is the task of discovering high-density regions of\nentities (clusters) that are separated from each other by contiguous regions of\nlow-density. DBSCAN is, arguably, the most popular density-based clustering\nalgorithm. However, its cluster recovery capabilities depend on the combination\nof the two parameters. In this paper we present a new density-based clustering\nalgorithm which uses reverse nearest neighbour (RNN) and has a single\nparameter. We also show that it is possible to estimate a good value for this\nparameter using a clustering validity index. The RNN queries enable our\nalgorithm to estimate densities taking more than a single entity into account,\nand to recover clusters that are not well-separated or have different\ndensities. Our experiments on synthetic and real-world data sets show our\nproposed algorithm outperforms DBSCAN and its recent variant ISDBSCAN.\n

Related

• Clustering by Deep Nearest Neighbor Descent (D-NND): A Density-based Parameter-Insensitive Clustering Method
• Density Adaptive Parallel Clustering
• Guaranteed Recovery of Unambiguous Clusters
• Geometric reconstructions of density based clusterings
• An Improved Probability Propagation Algorithm for Density Peak Clustering Based on Natural Nearest Neighborhood