Publicación: Comparative Evaluation of Region Query Strategies for DBSCAN Clustering
Cargando...
Fecha
2019-10
Autores
Editor/a
Director/a
Tutor/a
Coordinador/a
Prologuista
Revisor/a
Ilustrador/a
Derechos de acceso
info:eu-repo/semantics/openAccess
Título de la revista
ISSN de la revista
Título del volumen
Editor
Elsevier
Resumen
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.
Descripción
Categorías UNESCO
Palabras clave
Clustering, DBSCAN algorithm, region query strategy, comparative evaluation
Citación
Centro
E.T.S. de Ingeniería Informática
Departamento
Inteligencia Artificial