PROJECT TITLE :

RNN-DBSCAN: A Density-Based Clustering Algorithm Using Reverse Nearest Neighbor Density Estimates - 2018

ABSTRACT:

A new density-based clustering algorithm, RNN-DBSCAN, is presented which uses reverse nearest neighbor counts as an estimate of observation density. Clustering is performed employing a DBSCAN-like approach primarily based on k nearest neighbor graph traversals through dense observations. RNN-DBSCAN is preferable to the favored density-based clustering algorithm DBSCAN in two aspects. Initial, drawback complexity is reduced to the use of a single parameter (selection of k nearest neighbors), and second, an improved ability for handling large variations in cluster density (heterogeneous density). The prevalence of RNN-DBSCAN is demonstrated on many artificial and real-world datasets with respect to previous work on reverse nearest neighbor based mostly clustering approaches (RECORD, IS-DBSCAN, and ISB-DBSCAN) along with DBSCAN and OPTICS. Every of those clustering approaches is described by a standard graph-based mostly interpretation wherein clusters of dense observations are outlined as connected components, along with a discussion on their computational complexity. Heuristics for RNN-DBSCAN parameter selection are presented, and the consequences of k on RNN-DBSCAN clusterings discussed. Additionally, with respect to scalability, an approximate version of RNN-DBSCAN is presented leveraging an existing approximate k nearest neighbor technique.