DBSCAN
El agrupamiento espacial basado en densidad de aplicaciones con ruido o Density-based spatial clustering of applications with noise (DBSCAN) es un algoritmo de agrupamiento de datos (data clustering) propuesto por Martin Ester, Hans-Peter Kriegel, Jörg Sander y Xiaowei Xu en 1996.
En 2014, el algoritmo fue merecedor del premio a la prueba del tiempo (un reconocimiento dado a algoritmos que han recibido una sustancial atención en la teoría y la práctica) en la conferencia líder de la minería de datos, KDD.
[3] El paper "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN" aparece en la lista de los 8 artículos más descargados en la revista ACM Transactions on Database Systems (TODS).
Considere un conjunto de puntos a ser agrupados en un espacio determinado.
Por definición, ningún punto puede ser alcanzable desde un punto que no sea núcleo, sin importar la distancia a la que se encuentre, es decir, un punto que no sea núcleo puede ser alcanzable pero nada puede ser alcanzado desde este.
Los clusters consisten solo en nodos que están densamente conectados entre sí, esta idea es más cercana a la interpretación estadística de la densidad de componentes conexas (componentes conexas).
(eps) y el número mínimo de puntos requeridos para que una región se considere densa[5] (minPts).
El algoritmo comienza por un punto arbitrario que no haya sido visitado.
Este proceso continúa hasta construir completamente un clúster densamente conectado.
En el siguiente Pseudocódigo se describe este algoritmo: DBSCAN visita cada punto de la base de datos, posiblemente varias veces (e.g., como candidatos a diferentes clusters).
Para la práctica, sin embargo, la complejidad temporal es mayormente gobernada por el número de llamados a regionQuery.
DBSCAN ejecuta exactamente una consulta por cada punto, y si se utiliza una estructura de índice (indexing structure) que ejecute la consulta a los vecinos (neighborhood query) en O(log n), la complejidad temporal total sería O(n log n).
Esto necesita O(n²) de memoria, mientras que con una implementación que no se base en matrices solo se necesita O(n) de memoria.
Vea la sección sobre extensiones de modificaciones algorítmicos para manejar estos temas.
[5] OPTICS puede verse como una generalización de DBSCAN que reemplaza el parámetro
MinPts entonces esencialmente se convierte en el tamaño mínimo del conglomerado de encontrar.
Se han propuesto varias extensiones para el algoritmo de DBSCAN, incluyendo métodos para la paralelización, la estimación de parámetros y el apoyo para los datos inciertos.
La idea básica se ha extendido a la agrupación jerárquica por el algoritmo OPTICS.
[10] Una implementación de DBSCAN así como GDBSCAN y otras variantes están disponibles en ELKI framework.
Weka contiene (como un paquete opcional en las versiones más recientes) una implementación básica de DBSCAN que se ejecutan en el tiempo y la memoria cuadrática lineal.
