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.^[1]​ Es un algoritmo de agrupamiento basado en densidad (density-based clustering) porque encuentra un número de grupos (clusters) comenzando por una estimación de la distribución de densidad de los nodos correspondientes. DBSCAN es uno de los algoritmos de agrupamiento más usados y citados en la literatura científica.^[2]​ OPTICS puede verse como una generalización de DBSCAN para múltiples rangos, reemplazando el parámetro e por el radio máximo de búsqueda.

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).

Preliminares

Los puntos marcados como A son puntos núcleo. Los puntos B y C son densamente alcanzables desde A y densamente conectados con A, y pertenecen al mismo clúster. El punto N es un punto ruidoso que no es núcleo ni densamente alcanzable. (MinPts=3 o MinPts=4)

Considere un conjunto de puntos a ser agrupados en un espacio determinado. La técnica de agrupación DBSCAN clasifica los puntos como puntos núcleo, puntos (densamente-)alcanzables, o ruido de la siguiente forma:

• Un punto ${\displaystyle p}$ es un punto núcleo si al menos minPts puntos están a una distancia ε de él. Se dice que estos puntos son directamente alcanzables desde ${\displaystyle p}$. No es posible tener puntos directamente alcanzables desde un punto que no sea un núcleo.
• Un punto ${\displaystyle q}$ es alcanzable desde ${\displaystyle p}$ si existe una secuencia de puntos ${\displaystyle p_{1},...,p_{n}}$ donde ${\displaystyle p_{1}=p}$ y ${\displaystyle p_{n}=q}$ tal que cada punto ${\displaystyle p_{i+1}}$ es directamente alcanzable desde ${\displaystyle p_{i}}$; es decir, todos los puntos de la secuencia deben ser puntos núcleos, con la posible excepción de ${\displaystyle q}$.
• Un punto que no sea alcanzable desde cualquier otro punto es considerado ruido.

Si ${\displaystyle p}$ es un punto núcleo, este forma un cluster junto a otros puntos (núcleo o no) que sean alcanzables desde él. Cada cluster contiene al menos un punto núcleo. Los puntos no núcleos alcanzables pueden pertenecer a un cluster pero actúan como una barrera puesto que no es posible alcanzar más puntos desde estos.

Note que la relación de ser alcanzable no es simétrica. 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. Por lo tanto la noción de connectividad es necesaria para definir formalmente la extensión de un cluster dada por DBSCAN. Dos puntos ${\displaystyle p}$ y ${\displaystyle q}$ están conectados densamente si existe un punto ${\displaystyle o}$ tal que ambos ${\displaystyle p}$ y ${\displaystyle q}$ sean directamente alcanzables desde ${\displaystyle o}$. La relación estar densamente conectado es simétrica.

Un clúster, satisface por lo tanto dos propiedades:

1. Todos los puntos del clúster están densamente conectados entre sí.
2. Si un punto A es densamente alcanzable desde cualquier otro punto B del clúster, entonces A también forma parte del clúster.

La variante DBSCAN*^[4]​ no distingue entre nodos borde y nodos ruidosos. 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). El agrupamiento resultante, por lo general, contiene más nodos ruidosos.

Algoritmo

DBSCAN requiere dos parámetros: ${\displaystyle e}$ (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. La ${\displaystyle e}$-vecindad de este punto es visitada, y si contiene suficientes puntos, se inicia un clúster sobre el mismo. De lo contrario, el punto es etiquetado como ruido. Notar que el punto en cuestión puede pertenecer a otra vecindad que lo incluya en el clúster correspondiente.

Si un punto se incluye en la parte densa de un clúster, su ${\displaystyle e}$-vecindad también forma parte del clúster. Así, todos los puntos de dicha vecindad se añaden al clúster, al igual que las ${\displaystyle e}$-vecindad de estos puntos que sean lo suficientemente densas. Este proceso continúa hasta construir completamente un clúster densamente conectado. Entonces, un nuevo punto no visitado se visita y procesa con el objetivo de descubrir otro clúster o ruido.

En el siguiente Pseudocódigo se describe este algoritmo:

DBSCAN(D, eps, MinPts)
   C = 0
   for each unvisited point P in dataset D
      mark P as visited
      NeighborPts = regionQuery(P, eps)
      if sizeof(NeighborPts) < MinPts
         mark P as NOISE
      else
         C = next cluster
         expandCluster(P, NeighborPts, C, eps, MinPts)

expandCluster(P, NeighborPts, C, eps, MinPts)
   add P to cluster C
   for each point P' in NeighborPts
      if P' is not visited
         mark P' as visited
         NeighborPts' = regionQuery(P', eps)
         if sizeof(NeighborPts') >= MinPts
            NeighborPts = NeighborPts joined with NeighborPts'
      if P' is not yet member of any cluster
         add P' to cluster C

regionQuery(P, eps)
   return all points within P's eps-neighborhood (including P)

Complejidad

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). Sin usar la estructura de índice, la complejidad temporal sería O(n²). A menudo, la matriz de distancias de tamaño (n²-n)/2 se construye para evitar recalcular las distancias. 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.

DBSCAN puede encontrar clusters que no son linealmente separables. Este conjunto de datos no puede ser correctamente agrupado con k-means o Gaussian Mixture EM clustering.

Ventajas

1. DBSCAN no necesita de la especificación del número de clusters deseado como lo requiere k-means.
2. DBSCAN puede encontrar clusters con formas geométricas arbitrarias. Puede incluso hallar un cluster completamente rodeado (pero no conectado) de otro cluster distinto. Debido al parámetro MinPts, se reduce el efecto single-link (clusters diferentes pueden conectarse mediante una delgada línea de puntos).
3. DBSCAN tiene noción del ruido, y es robusto detectando outliers.
4. DBSCAN requiere solo de dos parámetros y no es susceptible al orden en que se encuentren los puntos dentro de la base de datos. (Sin embargo, los puntos de las fronteras de dos clusters diferentes pueden pertenecer a uno u otro cluster si el orden de los puntos en la base de datos se cambia, y la asignación del cluster es única solo en isomorfismos.)
5. DBSCAN está diseñado para bases de datos que puedan acelerar las consultas en regiones, e.g usando un R* tree.

Desventajas

1. DBSCAN no es enteramente determinista: los puntos borde que son alcanzables desde más de un cluster pueden etiquetarse en cualquiera de estos. Afortunadamente, esta situación no es usual, y tiene un impacto pequeño sobre el cluster: en los puntos núcleo y ruidosos, DBSCAN es determinista. DBSCAN*^[4]​ es una variación que trata los puntos borde como ruido, y así logra un resultado completamente determinista, así como una interpretación estadística de las componentes densamente conectadas más consistente.
2. La calidad de DBSCAN depende de la noción de distancia (distance measure) usada en la función regionQuery(P,${\displaystyle e}$). La distancia más usada es la distancia euclidiana. Especialmente para los datos de alta dimensión, este indicador es inútil debido a la llamada "maldición de dimensionalidad", por lo que es difícil encontrar un valor adecuado para ${\displaystyle e}$. Este efecto, sin embargo, también está presente en cualquier otro algoritmo basado en la distancia euclidiana.
3. DBSCAN no puede agrupar conjuntos de datos bien con grandes diferencias en las densidades, ya que la combinación MinPts-${\displaystyle e}$ no se puede escoger adecuadamente para todos los grupos.

Vea la sección sobre extensiones de modificaciones algorítmicos para manejar estos temas.

Estimación de parámetros

Cada tarea de minería de datos tiene el problema de parámetros. Cada parámetro influye en el algoritmo de manera específica. Para DBSCAN, se necesitan los parámetros ${\displaystyle e}$ y MinPts. Estos deben ser especificados por el usuario. Idealmente, el valor de ${\displaystyle e}$ está dado por el problema a resolver (por ejemplo, una distancia física), y MinPts es entonces el tamaño de clúster mínimo deseado.^[5]​

• MinPts: Como regla general, un MinPts mínimo se pueden derivar de la serie de dimensiones D en el conjunto de datos, como minPts ≥ D+1. El valor de MinPts = 1 no tiene sentido, ya que todos los puntos de su cluster serán un clúster. Con MinPts = 2, el resultado será el mismo que el de la agrupación jerárquica con la métrica single-link, con el corte a la altura del dendrograma ${\displaystyle e}$. Sin embargo, los valores más grandes son generalmente mejores para los conjuntos de datos con ruido y rendirán agrupaciones más importantes. Cuanto más grande es el conjunto de datos, mayor será el valor de MinPts elegido.
• ${\displaystyle e}$: El valor para ${\displaystyle e}$ entonces puede ser elegido por el uso de un gráfico k-distancia, el trazado de la distancia a la k = MinPts vecino más cercano. Buenos valores de ${\displaystyle e}$ son donde este gráfico muestra una fuerte curvatura: si ${\displaystyle e}$ es elegido demasiado pequeño, no se agrupan una gran parte de los datos; mientras que para un muy alto valor de ${\displaystyle e}$, las agrupaciones se fusionan y la mayoría de los objetos serán en el mismo grupo.

OPTICS puede verse como una generalización de DBSCAN que reemplaza el parámetro ${\displaystyle e}$ con un valor máximo que afecta principalmente el rendimiento. MinPts entonces esencialmente se convierte en el tamaño mínimo del conglomerado de encontrar. Mientras que el algoritmo es mucho más fácil para parametrizar de DBSCAN, los resultados son un poco más difícil de utilizar, ya que por lo general producir una agrupación jerárquica en lugar de la partición de datos simple que produce DBSCAN.

Recientemente, uno de los autores originales de DBSCAN ha revisitado DBSCAN y OPTICS, y publicado una versión refinada de DBSCAN jerárquica (HDBSCAN *),,^[4]​^[6]​ que ya no tiene la noción de los puntos fronterizos.

Extensiones

Generalized DBSCAN (GDBSCAN)^[7]​^[8]​ es una generalización de los mismos autores a los algoritmos basados en vecindad y densidad. Los parámetros ${\displaystyle e}$ y MinPts se eliminan del algoritmo original y se trasladan a los predicados. Por ejemplo en los datos del polígono, la vecindad podría ser cualquier polígono de intersección, mientras que la densidad utiliza las áreas de polígonos en lugar de sólo el contador de objeto.

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. DBSCAN también se utiliza como parte de los algoritmos de agrupación subespacio como PreDeCon y SUBCLU. HDBSCAN HDBSCAN^[9]​ es una versión jerárquica de DBSCAN que es también más rápido que OPTICS, donde una partición plana consiste en la mayoría de los grupos prominentes que se pueden extraer de la jerarquía.^[10]​

Implementaciones

Una implementación de DBSCAN así como GDBSCAN y otras variantes están disponibles en ELKI framework. Esta aplicación se puede utilizar diversas estructuras de índices de ejecución sub-cuadrática y apoya diversas funciones de distancia y tipos de datos arbitrarios, pero puede ser superado por el bajo nivel optimizado (y especializados) implementaciones en pequeños conjuntos de datos. La aplicación de la HDBSCAN se pone a disposición de los autores.

scikit-learn incluye una implementación de Python de DBSCAN para arbitrarias métrica de Minkowski, que puede acelerarse mediante kd-trees y ball trees.

GNU R contiene DBSCAN en el paquete "fpc" con soporte para funciones arbitrarias distancia a través de matrices de distancia. Sin embargo, no tiene soporte de índice (y por lo tanto tiene tiempo de ejecución cuadrática y la complejidad de la memoria).

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.

Referencias

1. Ester, Martin; Kriegel, Hans-Peter; Sander, Jörg; Xu, Xiaowei (1996). «A density-based algorithm for discovering clusters in large spatial databases with noise». En Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M., eds. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226-231. ISBN 1-57735-004-9. 
2. «Copia archivada». Archivado desde el original el 21 de abril de 2010. Consultado el 10 de mayo de 2010.  Artículos sobre minería de datos más citados según Microsoft academic search; DBSCAN ocupa el puesto 24, consultado en: 4/18/2010
3. «2014 SIGKDD Test of Time Award». ACM SIGKDD. 18 de agosto de 2014. Archivado desde el original el 26 de agosto de 2014. Consultado el 22 de agosto de 2014. 
4. Campello, Ricardo J. G. B.; Moulavi, Davoud; Sander, Joerg (14 de abril de 2013). Pei, Jian; Tseng, Vincent S.; Cao, Longbing; Motoda, Hiroshi; Xu, Guandong, eds. Density-Based Clustering Based on Hierarchical Density Estimates. Lecture Notes in Computer Science (en inglés). Springer Berlin Heidelberg. pp. 160-172. ISBN 9783642374555. doi:10.1007/978-3-642-37456-2_14. Consultado el 8 de agosto de 2016. 
5. Mientras que minPts intuitivamente es el tamaño del clúster más pequeño, en algunos casos DBSCAN puede producir clusters más pequeños. Un clúster construido por DBSCAN consiste en al menos un punto núcleo. No hay garantía de que al menos minPts puntos se incluyan en todo clúster.
6. Campello, R. J. G. B.; Moulavi, D.; Zimek, A.; Sander, J. (4 de abril de 2013). «A framework for semi-supervised and unsupervised optimal extraction of clusters from hierarchies». Data Mining and Knowledge Discovery (en inglés) 27 (3): 344-371. ISSN 1384-5810. doi:10.1007/s10618-013-0311-4. Consultado el 8 de agosto de 2016. 
7. Sander, Jörg; Ester, Martin; Kriegel, Hans-Peter; Xu, Xiaowei (1998). «Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications». Data Mining and Knowledge Discovery (Berlin: Springer-Verlag) 2 (2): 169-194. doi:10.1023/A:1009745219419. 
8. Sander, Jörg (1998). Generalized Density-Based Clustering for Spatial Data Mining. München: Herbert Utz Verlag. ISBN 3-89675-469-6. 
9. name="hdbscan1"
10. name="hdbscan2"

Bibliografía

• Arlia, Domenica; Coppola, Massimo. «Experiments in Parallel Clustering with DBSCAN». Euro-Par 2001: Parallel Processing: 7th International Euro-Par Conference Manchester, UK August 28–31, 2001, Proceedings. Springer Berlin. 
• Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). «Density-based Clustering». WIREs Data Mining and Knowledge Discovery 1 (3): 231-240. doi:10.1002/widm.30. Archivado desde el original el 17 de noviembre de 2016. Consultado el 18 de diciembre de 2014.