DBSCAN

Algoritmo de agrupación de datos basado en densidad

La agrupación espacial de aplicaciones con ruido basada en densidad ( DBSCAN ) es un algoritmo de agrupación de datos propuesto por Martin Ester , Hans-Peter Kriegel , Jörg Sander y Xiaowei Xu en 1996. ^[1] Es un algoritmo no paramétrico de agrupación basada en densidad : Dado un conjunto de puntos en algún espacio, agrupa puntos que están muy juntos (puntos con muchos vecinos cercanos ), marcando como valores atípicos los puntos que se encuentran solos en regiones de baja densidad (cuyos vecinos más cercanos están demasiado lejos). DBSCAN es uno de los algoritmos de agrupamiento más comunes y citados. ^[2]

En 2014, el algoritmo recibió el premio Test of Time (un premio otorgado a algoritmos que han recibido una atención sustancial en la teoría y la práctica) en la principal conferencia de minería de datos, ACM SIGKDD . ^[3] A partir de julio de 2020 ^[update], el documento de seguimiento "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN" ^[4] aparece en la lista de los 8 artículos más descargados del prestigioso ACM Transactions on Database Revista de sistemas (TODS) . ^[5]

La popular continuación HDBSCAN* fue publicada inicialmente por Ricardo JG Campello, David Moulavi y Jörg Sander en 2013, ^[6] luego ampliada con Arthur Zimek en 2015. ^[7] Revisa algunas de las decisiones originales, como la frontera puntos y produce un resultado jerárquico en lugar de plano.

Historia

En 1972, Robert F. Ling publicó un algoritmo estrechamente relacionado en "The Theory and Construction of k-Clusters" ^[8] en The Computer Journal con una complejidad de tiempo de ejecución estimada de O(n³). ^[8] DBSCAN tiene el peor de los casos O(n²), y la formulación de consulta de rango orientada a la base de datos de DBSCAN permite la aceleración del índice. Los algoritmos difieren ligeramente en el manejo de los puntos fronterizos.

Preliminar

Considere un conjunto de puntos en algún espacio que se van a agrupar. Sea ε un parámetro que especifica el radio de una vecindad con respecto a algún punto. A los efectos de la agrupación de DBSCAN, los puntos se clasifican como puntos centrales , puntos ( directamente ) alcanzables y valores atípicos , de la siguiente manera:

• Un punto p es un punto central si al menos puntos minPts están a una distancia ε de él (incluido p ).
• Un punto q es directamente accesible desde p si el punto q está a una distancia ε del punto central p . Se dice que sólo se puede acceder directamente a los puntos desde los puntos centrales.
• Un punto q es alcanzable desde p si hay un camino p ₁ , ..., p _n con p ₁ = p y p _n = q , donde cada p _{i +1} es directamente alcanzable desde p _i . Tenga en cuenta que esto implica que el punto inicial y todos los puntos del camino deben ser puntos centrales, con la posible excepción de q .
• Todos los puntos a los que no se puede llegar desde ningún otro punto son valores atípicos o puntos de ruido .

Ahora bien, si p es un punto central, entonces forma un grupo junto con todos los puntos (centrales o no centrales) a los que se puede acceder desde él. Cada grupo contiene al menos un punto central; Los puntos no centrales pueden ser parte de un grupo, pero forman su "borde", ya que no se pueden usar para alcanzar más puntos.

En este diagrama, minPts = 4 . El punto A y los otros puntos rojos son puntos centrales, porque el área que rodea estos puntos en un radio ε contiene al menos 4 puntos (incluido el punto mismo). Como todos ellos son accesibles entre sí, forman un único grupo. Los puntos B y C no son puntos centrales, pero son accesibles desde A (a través de otros puntos centrales) y, por lo tanto, también pertenecen al grupo. El punto N es un punto de ruido que no es un punto central ni accesible directamente.

La accesibilidad no es una relación simétrica: por definición, sólo los puntos centrales pueden llegar a los puntos no centrales. Lo contrario no es cierto, por lo que se puede alcanzar un punto no central, pero no se puede llegar a nada a partir de él. Por lo tanto, se necesita una noción adicional de conectividad para definir formalmente la extensión de los grupos encontrados por DBSCAN. Dos puntos p y q están conectados por densidad si hay un punto o tal que tanto p como q sean alcanzables desde o . La conexión de densidad es simétrica.

Entonces, un clúster satisface dos propiedades:

1. Todos los puntos dentro del grupo están mutuamente conectados por densidad.
2. Si un punto es alcanzable en densidad desde algún punto del grupo, también es parte del grupo.

Algoritmo

Algoritmo original basado en consultas

DBSCAN requiere dos parámetros: ε (eps) y el número mínimo de puntos necesarios para formar una región densa ^[a] (minPts). Comienza con un punto de partida arbitrario que no ha sido visitado. Se recupera la vecindad ε de este punto y, si contiene suficientes puntos, se inicia un grupo. De lo contrario, el punto se etiqueta como ruido. Tenga en cuenta que este punto podría encontrarse más tarde en un entorno ε de tamaño suficiente de un punto diferente y, por lo tanto, formar parte de un grupo.

Si se encuentra que un punto es una parte densa de un grupo, su vecindad ε también es parte de ese grupo. Por lo tanto, se suman todos los puntos que se encuentran dentro de la vecindad ε, al igual que su propia vecindad ε cuando también son densos. Este proceso continúa hasta que se encuentra completamente el grupo conectado por densidad. Luego, se recupera y procesa un nuevo punto no visitado, lo que lleva al descubrimiento de otro grupo o ruido.

DBSCAN se puede utilizar con cualquier función de distancia ^{[1] [4]} (así como funciones de similitud u otros predicados). ^[9] Por lo tanto, la función de distancia (dist) puede considerarse un parámetro adicional.

El algoritmo se puede expresar en pseudocódigo de la siguiente manera: ^[4]

DBSCAN(DB, distFunc, eps, minPts) { C := 0 /* Contador de clúster */  para cada punto P en la base de datos DB { si etiqueta(P) ≠ indefinido entonces  continuar  /* Procesado previamente en el bucle interno */ Vecinos N := RangeQuery(DB, distFunc, P, eps) /* Buscar vecinos */  si |N| < minPts entonces { /* Comprobación de densidad */ etiqueta(P) := Ruido /* Etiquetar como ruido */  continuar } C := C + 1 /* siguiente etiqueta del grupo */ label(P) := C /* Etiqueta punto inicial */ SeedSet S := N \ {P} /* Vecinos a expandir */  para cada punto Q en S { /* Procesar cada punto semilla Q */  si etiqueta(Q) = Ruido entonces etiqueta(Q) := C /* Cambiar Ruido al punto de borde */  si etiqueta(Q) ≠ indefinido entonces  continuar  /* Procesado previamente (p. ej., borde punto) */ etiqueta(Q) := C /* Etiqueta vecino */ Vecinos N := RangeQuery(DB, distFunc, Q, eps) /* Buscar vecinos */  if |N| ≥ minPts entonces { /* Verificación de densidad (si Q es un punto central) */ S := S ∪ N /* Agregar nuevos vecinos al conjunto de semillas */ } } }}

donde RangeQuery se puede implementar usando un índice de base de datos para un mejor rendimiento o usando un escaneo lineal lento:

RangeQuery(DB, distFunc, Q, eps) { Vecinos N := lista vacía para cada punto P en la base de datos DB { /* Escanea todos los puntos en la base de datos */  si distFunc(Q, P) ≤ eps entonces { /* Calcula la distancia y verifica épsilon */ N := N ∪ {P} /* Agregar a resultado */ } } retorno sustantivo, masculino—}

Algoritmo abstracto

El algoritmo DBSCAN se puede resumir en los siguientes pasos: ^[4]

1. Encuentre los puntos en la vecindad ε (eps) de cada punto e identifique los puntos centrales con más de minPts vecinos.
2. Encuentre los componentes conectados de los puntos centrales en el gráfico vecino, ignorando todos los puntos no centrales.
3. Asigne cada punto no central a un grupo cercano si el grupo es un vecino ε (eps); de lo contrario, asígnelo al ruido.

Una implementación ingenua de esto requiere almacenar las vecindades en el paso 1, por lo que requiere una memoria sustancial. El algoritmo DBSCAN original no requiere esto al realizar estos pasos un punto a la vez.

Criterio de optimización

DBSCAN optimiza la siguiente función de pérdida: ^[10] Para cualquier posible agrupación fuera del conjunto de todas las agrupaciones , minimiza el número de agrupaciones bajo la condición de que cada par de puntos en un grupo sea alcanzable en densidad, lo que corresponde a los dos originales. propiedades "maximalidad" y "conectividad" de un clúster: ^[1] ${\displaystyle C=\{C_{1},\ldots ,C_{l}\}}$ ${\displaystyle {\mathcal {C}}}$

$${\displaystyle \min _{C\subset {\mathcal {C}},~d_{db}(p,q)\leq \varepsilon ~\forall p,q\in C_{i}~\forall C_{i}\in C}|C|}$$

donde da el valor más pequeño tal que dos puntos p y q están conectados por densidad. ${\displaystyle d_{db}(p,q)}$ ${\displaystyle \varepsilon }$

Complejidad

DBSCAN visita cada punto de la base de datos, posiblemente varias veces (por ejemplo, como candidatos a diferentes grupos). Sin embargo, por consideraciones prácticas, la complejidad del tiempo se rige principalmente por el número de invocaciones de regionQuery. DBSCAN ejecuta exactamente una de esas consultas para cada punto, y si se utiliza una estructura de indexación que ejecuta una consulta de vecindad en O(log n ) , se obtiene una complejidad de tiempo de ejecución promedio general de O( n log n ) (si se elige el parámetro ε en de forma significativa, es decir, de modo que en promedio sólo se devuelvan O(log n ) puntos). Sin el uso de una estructura de índice de aceleración, o en datos degenerados (por ejemplo, todos los puntos dentro de una distancia menor que ε ), la complejidad del tiempo de ejecución en el peor de los casos sigue siendo O( n² ) . El triángulo superior de tamaño - n = ( n ²- n )/2 de la matriz de distancia se puede materializar para evitar recálculos de distancia, pero esto necesita memoria O ( n ² ) , mientras que una implementación de DBSCAN no basada en matriz solo necesita O ( n ) memoria. ${\displaystyle \textstyle {\binom {n}{2}}}$

DBSCAN puede encontrar grupos separables no linealmente. Este conjunto de datos no se puede agrupar adecuadamente con k-means o agrupación EM de mezcla gaussiana.

Ventajas

1. DBSCAN no requiere que uno especifique el número de grupos en los datos a priori, a diferencia de k-means .
2. DBSCAN puede encontrar grupos de formas arbitrarias. Incluso puede encontrar un clúster completamente rodeado (pero no conectado) por un clúster diferente. Debido al parámetro MinPts, se reduce el llamado efecto de enlace único (diferentes grupos conectados por una delgada línea de puntos).
3. DBSCAN tiene una noción de ruido y es resistente a los valores atípicos .
4. DBSCAN requiere sólo dos parámetros y es prácticamente insensible al orden de los puntos en la base de datos. (Sin embargo, los puntos que se encuentran en el borde de dos grupos diferentes pueden intercambiar la membresía del grupo si se cambia el orden de los puntos, y la asignación del grupo es única solo hasta el isomorfismo).
5. DBSCAN está diseñado para usarse con bases de datos que pueden acelerar consultas de regiones, por ejemplo, usando un árbol R* .
6. Los parámetros minPts y ε pueden ser establecidos por un experto en el dominio, si los datos se comprenden bien.

Desventajas

1. DBSCAN no es del todo determinista: los puntos fronterizos a los que se puede llegar desde más de un grupo pueden formar parte de cualquiera de ellos, dependiendo del orden en que se procesen los datos. Para la mayoría de los dominios y conjuntos de datos, esta situación no surge con frecuencia y tiene poco impacto en el resultado de la agrupación: ^[4] tanto en los puntos centrales como en los puntos de ruido, DBSCAN es determinista. DBSCAN* ^{[6] [7]} es una variación que trata los puntos fronterizos como ruido y de esta manera logra un resultado completamente determinista, así como una interpretación estadística más consistente de los componentes conectados por densidad.
2. La calidad de DBSCAN depende de la medida de distancia utilizada en la función regionQuery(P,ε). La métrica de distancia más común utilizada es la distancia euclidiana . Especialmente para datos de alta dimensión , esta métrica puede volverse casi inútil debido a la llamada " maldición de la dimensionalidad ", lo que dificulta encontrar un valor apropiado para ε. Este efecto, sin embargo, también está presente en cualquier otro algoritmo basado en la distancia euclidiana.
3. DBSCAN no puede agrupar bien conjuntos de datos con grandes diferencias en densidades, ya que la combinación minPts-ε no se puede elegir adecuadamente para todos los grupos. ^[11]
4. Si los datos y la escala no se comprenden bien, puede resultar difícil elegir un umbral de distancia significativo ε.

Consulte la sección siguiente sobre extensiones para modificaciones algorítmicas para manejar estos problemas.

Estimación de parámetros

Toda tarea de minería de datos tiene el problema de los parámetros. Cada parámetro influye en el algoritmo de formas específicas. Para DBSCAN, se necesitan los parámetros ε y minPts . Los parámetros deben ser especificados por el usuario. Idealmente, el valor de ε viene dado por el problema a resolver (por ejemplo, una distancia física), y minPts es entonces el tamaño mínimo de grupo deseado. ^[a]

• MinPts : Como regla general, se puede derivar un mínimo de minPts a partir del número de dimensiones D en el conjunto de datos, como minPts ≥ D + 1. El valor bajo de minPts = 1 no tiene sentido, ya que entonces cada punto es un punto central por definición. Con minPts ≤ 2, el resultado será el mismo que el del clustering jerárquico con la métrica de enlace único, con el dendrograma cortado a la altura ε. Por lo tanto, se deben elegir minPts al menos 3. Sin embargo, los valores más grandes suelen ser mejores para conjuntos de datos con ruido y producirán grupos más significativos. Como regla general, se puede utilizar minPts = 2 · dim , ^[9] pero puede ser necesario elegir valores mayores para datos muy grandes, para datos ruidosos o para datos que contienen muchos duplicados. ^[4]
• ε: El valor de ε se puede elegir usando un gráfico de k-distancia , trazando la distancia al vecino más cercano k = minPts -1 ordenada del valor más grande al más pequeño. ^[4] Los buenos valores de ε se encuentran donde este gráfico muestra un "codo": ^{[1] [9] [4]} si ε se elige demasiado pequeño, una gran parte de los datos no se agruparán; mientras que para un valor demasiado alto de ε, los grupos se fusionarán y la mayoría de los objetos estarán en el mismo grupo. En general, son preferibles valores pequeños de ε ^[4] y, como regla general, sólo una pequeña fracción de puntos debe estar dentro de esta distancia entre sí. Alternativamente, se puede usar un gráfico OPTICS para elegir ε, ^[4] pero luego se puede usar el algoritmo OPTICS para agrupar los datos.
• Función de distancia: la elección de la función de distancia está estrechamente relacionada con la elección de ε y tiene un impacto importante en los resultados. En general, será necesario identificar primero una medida razonable de similitud para el conjunto de datos, antes de poder elegir el parámetro ε. No existe una estimación para este parámetro, pero las funciones de distancia deben elegirse adecuadamente para el conjunto de datos. Por ejemplo, en el caso de datos geográficos, la distancia del círculo máximo suele ser una buena opción.

OPTICS puede verse como una generalización de DBSCAN que reemplaza el parámetro ε con un valor máximo que afecta principalmente al rendimiento. MinPts se convierte entonces esencialmente en el tamaño de clúster mínimo a encontrar. Si bien el algoritmo es mucho más fácil de parametrizar que DBSCAN, los resultados son un poco más difíciles de usar, ya que generalmente producirá una agrupación jerárquica en lugar de la simple partición de datos que produce DBSCAN.

Recientemente, uno de los autores originales de DBSCAN revisó DBSCAN y OPTICS y publicó una versión refinada de DBSCAN jerárquico (HDBSCAN*), ^{[6] [7]} que ya no tiene la noción de puntos fronterizos. En cambio, sólo los puntos centrales forman el grupo.

Relación con la agrupación espectral

Una implementación espectral de DBSCAN está relacionada con la agrupación espectral en el caso trivial de determinar los componentes del gráfico conectados : las agrupaciones óptimas sin bordes cortados. ^[12] Sin embargo, puede ser computacionalmente intensivo, hasta . Además, hay que elegir el número de vectores propios a calcular. Por razones de rendimiento, el algoritmo DBSCAN original sigue siendo preferible a su implementación espectral. ${\displaystyle O(n^{3})}$

Extensiones

DBSCAN generalizado (GDBSCAN) ^{[9] [13]} es una generalización de los mismos autores a predicados arbitrarios de "vecindad" y "denso". Los parámetros ε y minPts se eliminan del algoritmo original y se trasladan a los predicados. Por ejemplo, en datos de polígonos, el "vecindario" podría ser cualquier polígono que se cruce, mientras que el predicado de densidad utiliza las áreas del polígono en lugar de solo el recuento de objetos.

Se han propuesto varias extensiones del algoritmo DBSCAN, incluidos métodos de paralelización, estimación de parámetros y soporte para datos inciertos. La idea básica se ha ampliado a la agrupación jerárquica mediante el algoritmo OPTICS . DBSCAN también se utiliza como parte de algoritmos de agrupamiento subespacial como PreDeCon y SUBCLU . HDBSCAN* ^{[6] [7]} es una versión jerárquica de DBSCAN que también es más rápida que OPTICS, de la cual se puede extraer de la jerarquía una partición plana que consta de los grupos más destacados. ^[14]

Disponibilidad

Se descubrió que diferentes implementaciones del mismo algoritmo exhibían enormes diferencias de rendimiento: la más rápida en un conjunto de datos de prueba finalizó en 1,4 segundos y la más lenta en 13803 segundos. ^[15] Las diferencias se pueden atribuir a la calidad de la implementación, las diferencias de lenguaje y compilador, y el uso de índices para la aceleración.

• Apache Commons Math contiene una implementación Java del algoritmo que se ejecuta en tiempo cuadrático.
• ELKI ofrece una implementación de DBSCAN así como GDBSCAN y otras variantes. Esta implementación puede utilizar varias estructuras de índice para un tiempo de ejecución subcuadrático y admite funciones de distancia arbitrarias y tipos de datos arbitrarios, pero puede verse superada por implementaciones optimizadas (y especializadas) de bajo nivel en conjuntos de datos pequeños.
• MATLAB incluye una implementación de DBSCAN en su "Caja de herramientas de aprendizaje automático y estadísticas" desde la versión R2019a.
• mlpack incluye una implementación de DBSCAN acelerado con técnicas de búsqueda de rango de árbol dual.
• PostGIS incluye ST_ClusterDBSCAN, una implementación 2D de DBSCAN que utiliza el índice de árbol R. Se admite cualquier tipo de geometría, por ejemplo, punto, cadena de líneas, polígono, etc.
• R contiene implementaciones de DBSCAN en los paquetes dbscan y fpc. Ambos paquetes admiten funciones de distancia arbitrarias mediante matrices de distancia. El paquete fpc no tiene soporte de índice (y por lo tanto tiene tiempo de ejecución cuadrático y complejidad de memoria) y es bastante lento debido al intérprete de R. El paquete dbscan proporciona una implementación rápida de C++ utilizando árboles kd (solo para distancia euclidiana) y también incluye implementaciones de DBSCAN*, HDBSCAN*, OPTICS, OPTICSXi y otros métodos relacionados.
• scikit-learn incluye una implementación en Python de DBSCAN para métricas arbitrarias de Minkowski , que se puede acelerar usando árboles kd y árboles de bolas pero que usa memoria cuadrática en el peor de los casos. Una contribución a scikit-learn proporciona una implementación del algoritmo HDBSCAN*.
• La biblioteca pyclustering incluye una implementación en Python y C++ de DBSCAN solo para distancia euclidiana, así como el algoritmo OPTICS.
• SPMF incluye una implementación del algoritmo DBSCAN con soporte de árbol kd solo para distancia euclidiana.
• Weka contiene (como paquete opcional en las últimas versiones) una implementación básica de DBSCAN que se ejecuta en tiempo cuadrático y memoria lineal.
• Linfa incluye una implementación de DBSCAN para el lenguaje de programación Rust .
• Julia incluye una implementación de DBSCAN en el paquete Clustering.jl de Julia Statistics.

Notas

1. Si bien minPts es intuitivamente el tamaño mínimo de grupo, en algunos casos DBSCAN puede producir grupos más pequeños. ^[4] Un grupo DBSCAN consta de al menos un punto central . ^[4] Como otros puntos pueden ser puntos fronterizos para más de un grupo, no hay garantía de que al menos se incluyan puntos minPts en cada grupo.

Referencias

1. Ester, Martín ; Kriegel, Hans-Peter ; Sander, Jörg; Xu, Xiaowei (1996). Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (eds.). Un algoritmo basado en densidad para descubrir grupos en grandes bases de datos espaciales con ruido (PDF) . Actas de la Segunda Conferencia Internacional sobre Descubrimiento de Conocimiento y Minería de Datos (KDD-96). Prensa AAAI . págs. 226-231. CiteSeerX  10.1.1.121.9220 . ISBN 1-57735-004-9.
2. "Búsqueda académica de Microsoft: artículos". Archivado desde el original el 21 de abril de 2010 . Consultado el 18 de abril de 2010 .Artículos de minería de datos más citados según la búsqueda académica de Microsoft; DBSCAN está en el puesto 24.
3. "Premio Prueba del Tiempo SIGKDD 2014". ACM SIGKDD. 2014-08-18 . Consultado el 27 de julio de 2016 .
4. Schubert, Erich; Sander, Jörg; Ester, Martín; Kriegel, Hans Peter ; Xu, Xiaowei (julio de 2017). "DBSCAN revisado, revisado: por qué y cómo debería (todavía) utilizar DBSCAN". Transmisión ACM. Sistema de base de datos . 42 (3): 19:1–19:21. doi :10.1145/3068335. ISSN  0362-5915. S2CID  5156876.
5. "Inicio TODS". tods.acm.org . Asociación para Maquinaria de Computación . Consultado el 16 de julio de 2020 .
6. Campello, Ricardo JGB; Moulavi, Davoud; Sander, Joerg (2013). Pei, Jian; Tseng, Vicente S.; Cao, Longbing; Motoda, Hiroshi (eds.). Agrupación basada en densidad basada en estimaciones de densidad jerárquica. Avances en descubrimiento de conocimiento y minería de datos. vol. 7819. Berlín, Heidelberg: Springer Berlín Heidelberg. págs. 160-172. doi :10.1007/978-3-642-37456-2_14. ISBN 978-3-642-37455-5. Consultado el 18 de agosto de 2023 .
7. Campello, Ricardo JGB; Moulavi, Davoud; Zimek, Arturo ; Sander, Jörg (2015). "Estimaciones de densidad jerárquica para agrupación, visualización y detección de valores atípicos de datos". Transacciones ACM sobre descubrimiento de conocimiento a partir de datos . 10 (1): 1–51. doi :10.1145/2733381. ISSN  1556-4681. S2CID  2887636.
8. Ling, RF (1 de enero de 1972). "Sobre la teoría y construcción de k-clusters". La revista informática . 15 (4): 326–332. doi :10.1093/comjnl/15.4.326. ISSN  0010-4620.
9. Sander, Jörg; Ester, Martín; Kriegel, Hans-Peter ; Xu, Xiaowei (1998). "Agrupación basada en densidad en bases de datos espaciales: el algoritmo GDBSCAN y sus aplicaciones". Minería de datos y descubrimiento de conocimientos . Berlín: Springer-Verlag . 2 (2): 169-194. Código Bib : 1998DMKD....2..169S. doi :10.1023/A:1009745219419. S2CID  445002.
10. Cerveza, Anna; Draganov, Andrés; Hohma, Elena; Jahn, Philipp; Frey, Christian MM; Consentimiento, Ira (6 de agosto de 2023). "Conectando los puntos: la distancia de densidad-conectividad unifica DBSCAN, k-Center y Spectral Clustering". Actas de la 29ª Conferencia ACM SIGKDD sobre descubrimiento de conocimientos y minería de datos . ACM. págs. 80–92. doi :10.1145/3580305.3599283. ISBN 9798400701030. S2CID  260499476.
11. Kriegel, Hans-Peter ; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). "Agrupación basada en densidad". WIREs Minería de datos y descubrimiento de conocimientos . 1 (3): 231–240. doi :10.1002/widm.30. S2CID  36920706. Archivado desde el original el 17 de noviembre de 2016 . Consultado el 12 de diciembre de 2011 .
12. Schubert, Erich; Hess, Sibila; Morik, Katharina (2018). La relación de DBSCAN con la factorización matricial y la agrupación espectral (PDF) . Lernen, Wissen, Daten, Analysen (LWDA). págs. 330–334 - a través de CEUR-WS.org.
13. Sander, Jörg (1998). Agrupación generalizada basada en densidad para minería de datos espaciales . Múnich: Herbert Utz Verlag. ISBN 3-89675-469-6.
14. Campello, RJGB; Moulavi, D.; Zimek, A .; Lijadora, J. (2013). "Un marco para la extracción óptima semisupervisada y no supervisada de grupos de jerarquías". Minería de datos y descubrimiento de conocimientos . 27 (3): 344. doi :10.1007/s10618-013-0311-4. S2CID  8144686.
15. Kriegel, Hans-Peter ; Schubert, Erich; Zimek, Arthur (2016). "El arte (negro) de la evaluación del tiempo de ejecución: ¿estamos comparando algoritmos o implementaciones?". Sistemas de Conocimiento y Información . 52 (2): 341. doi :10.1007/s10115-016-1004-2. ISSN  0219-1377. S2CID  40772241.