Clustering is a technique that allows data to be organized into groups of similar objects. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) constitutes a popular clustering algorithm that relies on a density-based notion of cluster and is designed to discover clusters of arbitrary shape. The computational complexity of DBSCAN is dominated by the calculation of the ϵ-neighborhood for every object in the dataset. Thus, the efficiency of DBSCAN can be improved in two different ways: (1) by reducing the overall number of ϵ-neighborhood queries (also known as region queries), or (2) by reducing the complexity of the nearest neighbor search conducted for each region query. This paper deals with the first issue by considering the most relevant region query strategies for DBSCAN, all of them characterized by inspecting the neighborhoods of only a subset of the objects in the dataset. We comparatively evaluate these region query strategies (or DBSCAN variants) in terms of clustering effectiveness and efficiency; additionally, a novel region query strategy is introduced in this work. The results show that some specific DBSCAN variants are only slightly inferior to DBSCAN in terms of effectiveness, while greatly improving its efficiency. Among these variants, the novel one outperforms the rest.
The registered version of this article, first published in Information Sciences (2019) 502, p 76-90, is available online at the publisher's website: Elsevier https://doi.org/10.1016/j.ins.2019.06.036
Notas adicionales
La versión registrada de este artículo, publicada por primera vez en Information Sciences (2019) 502, p 76-90, está disponible en línea en el sitio web del editor: Elsevier https://doi.org/10.1016/j.ins.2019.06.036
