DBSCAN

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 11 de diciembre de 2021; la verificación requiere 1 edición .

El agrupamiento espacial de aplicaciones con ruido basado en la densidad ( DBSCAN ) es un algoritmo de agrupamiento de datos propuesto por Maritin Ester, Hans-Peter Kriegel, Jörg Sander y Xiaowei Su en 1996 [1] . Este es un algoritmo de agrupamiento basado en la densidad: dado un conjunto de puntos en algún espacio, el algoritmo agrupa los puntos que están muy próximos entre sí (puntos con muchos vecinos cercanos ), marcando como valores atípicos los puntos que están solos en áreas de baja densidad. (más cercano cuyos vecinos están lejos). DBSCAN es uno de los algoritmos de agrupamiento más utilizados y es el que se menciona con mayor frecuencia en la literatura científica [2] .

En 2014, el algoritmo recibió el premio "time-tested" (un premio que se otorga a los algoritmos que han recibido una atención significativa en la teoría y la práctica) en la principal conferencia sobre minería de datos, KDD [3] .

Primeras versiones

En 1972, Robert F. Ling ya había publicado un artículo titulado The Theory and Construction of k-Clusters [4] en The Computer Journal con un algoritmo similar con una estimación de la complejidad computacional [4] . DBSCAN tiene la complejidad del peor de los casos y la redacción de DBSCAN en términos orientados a la base de datos de consultas de rango ${\ estilo de visualización O (n ^ {3})}$ $O(n^{2})$ [ clear ] permite acelerar por índice. Los algoritmos difieren en el manejo de los puntos de borde.

Preparación

Considere un conjunto de puntos en algún espacio que requiera agrupamiento. Para realizar el agrupamiento de DBSCAN, los puntos se dividen en puntos centrales , accesibles por densidad de puntos , y valores atípicos de la siguiente manera:

Un punto p es un punto principal si al menos minPts de puntos están a una distancia que no exceda ( es el radio de vecindad máximo de p ) a él (incluido el propio punto p ). Se dice que estos puntos son accesibles directamente desde p . $\epsilon$ $\epsilon$
Un punto q es directamente alcanzable desde p si q está a una distancia no mayor que p de p y p debe ser el punto base. $\epsilon$
Un punto A q es alcanzable desde p si hay un camino con y , donde todos los puntos son accesibles directamente desde (todos los puntos en el camino deben ser primarios excepto q ). ${\displaystyle p_{1},\puntos,p_{n))$ $p_{1}=p$ ${\ estilo de visualización p_ {n} = q}$ $p_{{yo+1}}$ $Pi}$
Todos los puntos a los que no se puede acceder desde los puntos centrales se consideran valores atípicos .

Ahora, si p es un punto central, entonces forma un grupo junto con todos los puntos (centrales o no centrales) accesibles desde ese punto. Cada grupo contiene al menos un punto principal. Los puntos no esenciales pueden formar parte de un grupo, pero forman su "borde" porque no se pueden utilizar para llegar a otros puntos.

La accesibilidad no es una relación simétrica porque, por definición, no se puede llegar a ningún punto desde un punto no central, independientemente de la distancia (por lo que se puede alcanzar un punto no central, pero no se puede llegar a nada desde él). Por lo tanto, el concepto adicional de conectividad es necesario para la definición formal del área de clústeres encontrada por el algoritmo DBSCAN. Dos puntos p y q están relacionados con la densidad si hay un punto o tal que tanto p como q son accesibles desde o . La conectividad de densidad es simétrica.

Entonces el clúster satisface dos propiedades:

Todos los puntos en el grupo están conectados por pares en densidad.
Si un punto es alcanzable por densidad desde algún punto del clúster, también pertenece al clúster.

Algoritmo

El algoritmo original basado en consultas

DBSCAN requiere que se especifiquen dos parámetros: y el número mínimo de puntos que deben formar una región densa [5] (minPts). El algoritmo parte de un punto arbitrario que aún no ha sido visto. Se elige una vecindad del punto y, si contiene suficientes puntos, se forma un grupo; de lo contrario, el punto se marca como ruido. Tenga en cuenta que este punto se puede encontrar más tarde en la vecindad de otro punto e incluirse en algún grupo. $\epsilon$ $\epsilon$ $\epsilon$

Si un punto se encuentra como un punto denso de un grupo, su vecindario también forma parte de este grupo. Por lo tanto, todos los puntos que se encuentran en la vecindad de este punto se agregan al clúster. Este proceso continúa hasta que se encuentra un clúster conectado por densidad . Luego, se selecciona y procesa un nuevo punto no visitado, lo que conduce al descubrimiento del siguiente grupo o ruido. $\epsilon$ $\epsilon$

DBSCAN se puede utilizar con cualquier función de distancia [1] [6] (así como una función de similitud o una condición booleana) [7] . Por lo tanto, la función de distancia (dist) puede considerarse como un parámetro adicional.

El algoritmo se puede escribir en pseudocódigo de la siguiente manera [6] :

DBSCAN(DB, distFunc, eps, minPts) { C=0 /* Recuento de grupos */ para cada punto P en la base de datos DB { if label(P) ≠ indefinido luego continuar /* El punto se buscó en el ciclo interno */ Vecinos N=RangeQuery(DB, distFunc, P, eps) / * Buscar vecinos */ if |N|< minPts then { /* Comprobación de densidad */ label(P)=Ruido /* Marcar como ruido */ continuar } C=C + 1 /* siguiente etiqueta de clúster */ label(P)=C /* Label start point */ Conjunto de semillas S=N \ {P} /* Vecinos a expandir */ para cada punto Q en S { /* Tratar cada punto semilla */ if label(Q)=Noise then label(Q)=C /* Change label Noise to Edge */ if label(Q) ≠ undefined then continue /* Ha sido visto */ label(Q)= C /* Marcar vecino */ Vecinos N=RangeQuery(DB, distFunc, Q, eps) /* Buscar vecinos */ if |N|≥ minPts then { /* Verificar densidad */ S=S ∪ N /* Agregar vecinos a establecer puntos rudimentarios */ } } } }

donde RangeQuery se puede implementar usando un índice de base de datos para un mejor rendimiento, o se puede usar una búsqueda lenta lineal:

RangeQuery(DB, distFunc, Q, ) {

\epsilon

Vecinos=lista vacía para cada punto P en la base de datos DB { /* Escanea todos los puntos en la base de datos */ si entonces { /* Calcula la distancia y verifica épsilon */ Vecinos = Vecinos ∪ {P} /* Agrega al resultado */

distFunc(Q,P)\leqslant\epsilon

} } volver vecinos }

Algoritmo abstracto

El algoritmo DBSCAN se puede descomponer en los siguientes pasos [6] :

Encontramos puntos en la vecindad de cada punto y seleccionamos los puntos principales con más de minPts vecinos. $\epsilon$
Encontramos los componentes conectados de los puntos principales en el gráfico de vecinos, ignorando todos los puntos no básicos.
Asigne cada grupo no primario más cercano si el grupo es vecino; de lo contrario, considere el punto como ruido. $\epsilon$

La implementación ingenua del algoritmo requiere memorizar los vecinos en el paso 1, por lo que requiere una memoria significativa. El algoritmo DBSCAN original no requiere esto al hacer estos pasos un punto a la vez.

Dificultad

DBSCAN visita cada punto de la base de datos, quizás varias veces (por ejemplo, como candidatos para otros grupos). Sin embargo, según la experiencia operativa, la complejidad del tiempo se rige principalmente por el número de consultas regionQuery. DBSCAN ejecuta exactamente una consulta de este tipo para cada punto, y si se usa una estructura de índice que completa la consulta de vecindad en tiempo O(log n ) , la complejidad de tiempo promedio general es O( n log n ) (si el parámetro es elegido con sensatez, entonces es tal que en promedio solo se devuelven O(log n ) puntos). Sin el uso de una estructura de índice de aceleración, o en datos degenerados (por ejemplo, cuando todos los puntos son menores que ), el tiempo de ejecución del peor de los casos permanece . La matriz de distancia de tamaño se puede calcular para evitar volver a calcular las distancias, pero esto requiere memoria , mientras que una implementación de DBSCAN sin una matriz de distancia solo requiere memoria O( n ) . $\epsilon$ $\epsilon$ $O(n^{2})$ ${\ estilo de visualización (n^{2}-n)/2}$ $O(n^{2})$

Beneficios

DBSCAN no requiere la especificación del número de grupos en los datos a priori , a diferencia del método k-means .
DBSCAN puede encontrar grupos de forma arbitraria. Incluso puede encontrar clústeres completamente rodeados por (pero no conectados a) otros clústeres. Gracias al parámetro MinPts, se reduce el llamado efecto de una conexión (la conexión de diferentes grupos con una delgada línea de puntos).
DBSCAN tiene la noción de ruido y tolera los valores atípicos .
DBSCAN requiere sólo dos parámetros y es mayormente insensible al orden de los puntos en la base de datos . (Sin embargo, los puntos que están en el borde de dos grupos diferentes pueden terminar en otro grupo si se cambia el orden de los puntos y la asignación de los grupos es única hasta el isomorfismo).
DBSCAN está diseñado para usarse con bases de datos que pueden acelerar las consultas en un rango de valores, como con un árbol R* .
Los minPts y los parámetros pueden ser establecidos por expertos en el campo en cuestión si los datos se entienden bien. $\epsilon$

Desventajas

DBSCAN no es completamente inequívoco: los puntos de borde a los que se puede llegar desde más de un grupo pueden pertenecer a cualquiera de estos grupos, según el orden en que se visualicen los puntos. Para la mayoría de los conjuntos de datos, estas situaciones rara vez ocurren y tienen poco efecto en el resultado de la agrupación [6] : los puntos principales y el ruido son procesados de forma única por DBSCAN. DBSCAN* [8] es una variante que trata los puntos de borde como ruido y, por lo tanto, logra un resultado completamente inequívoco, así como una interpretación estadística más consistente de los componentes conectados por densidad.
La calidad de DBSCAN depende de la medida de distancia utilizada en la función regionQuery(P,ε). La métrica de distancia más utilizada es la métrica euclidiana . Especialmente para agrupar datos de alta dimensión , esta métrica puede ser casi inútil debido a la llamada "maldición de la dimensionalidad" , que dificulta encontrar un valor apropiado . Este efecto, sin embargo, está presente en cualquier otro algoritmo basado en la distancia euclidiana. $\epsilon$
DBSCAN no puede agrupar bien los conjuntos de datos con grandes diferencias de densidad, porque no puede elegir una combinación que sea aceptable para todos los grupos [9] . $minPts-\epsilon$
Si los datos y la escala no se entienden bien, puede resultar difícil elegir un umbral de distancia significativo. $\epsilon$

Consulte la sección a continuación sobre extensiones para modificaciones algorítmicas que se ocupan de estos problemas.

Estimación de Parámetros

Cualquier tarea de minería de datos tiene un problema de parámetros. Cualquier parámetro tiene un efecto específico en el algoritmo. El algoritmo DBSCAN necesita parámetros y minPts . Los parámetros deben ser definidos por el usuario. Idealmente, el valor está determinado por el problema que se está resolviendo (p. ej., distancias físicas), y minPts luego determina el tamaño de clúster mínimo deseado [5] . $\epsilon$ $\epsilon$

MinPts : como muestra la experiencia, el valor mínimo de minPts se puede obtener de la dimensión D del conjunto de datos como . Un valor bajo de minPts =1 no tiene sentido, ya que entonces cualquier punto será un clúster. Para , el resultado será el mismo que el agrupamiento jerárquico con métrica de conexión única con poda de dendrograma en altura . Por lo tanto, minPts debe ser al menos 3. Sin embargo, para conjuntos de datos ruidosos, los valores más grandes suelen ser mejores y producen grupos más significativos. La experiencia sugiere que se puede usar un valor de [7] , pero puede ser necesario elegir un valor mayor para grandes conjuntos de datos, para datos ruidosos o para datos que contienen muchos duplicados [6] . $minPts\geqslant D+1$ $minPts\leqslant 2$ $\epsilon$ $minPts=2\cdot dim$
$\epsilon$ : El valor se puede elegir usando el gráfico de k-distancia , trazando la distancia al ( ) vecino más cercano en orden de mayor a menor [6] . Los buenos valores son aquellos en los que el gráfico tiene una "curva" [1] [7] [6] : si se elige demasiado pequeño, la mayoría de los datos no se agruparán, y para valores demasiado grandes, los grupos se fusionarán y la mayoría de los objetos estarán en el mismo grupo. Por lo general, los valores pequeños son preferibles [6] y la experiencia muestra que solo una pequeña proporción de puntos debe estar a esta distancia entre sí. Alternativamente, se puede usar un gráfico OPTICS para seleccionar [6] , pero luego el propio algoritmo OPTICS se puede usar para la agrupación. $\epsilon$ $k=minPts-1$ $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$
Función de distancia: la elección de la función de distancia está fuertemente relacionada con la elección y tiene un gran impacto en los resultados. Por lo general, es necesario determinar primero las medidas razonables de la similitud de un conjunto de datos antes de seleccionar el archivo . No hay estimaciones para este parámetro, pero las funciones de distancia deben elegirse de acuerdo con el conjunto de datos. Por ejemplo, para datos geográficos, la distancia de gran círculo suele ser una buena opción. $\epsilon$ $\epsilon$

Se puede pensar en OPTICS como una generalización de DBSCAN en la que el parámetro se reemplaza por el valor máximo que tiene el mayor impacto en el rendimiento. MinPts luego se convierte en el tamaño mínimo de clúster. Aunque el algoritmo es sustancialmente más simple en el dominio de selección de parámetros que DBSCAN, sus resultados son más difíciles de usar, ya que generalmente produce un agrupamiento jerárquico en lugar de la partición simple que produce DBSCAN. $\epsilon$

Recientemente, uno de los autores de DBSCAN revisó DBSCAN y OPTICS y publicó una versión revisada del DBSCAN jerárquico (HDBSCAN*) [8] , que ya no tiene el concepto de puntos de borde. Solo los puntos principales forman un grupo.

Extensiones

DBSCAN generalizado (GDBSCAN) [7] [10] es una generalización de los mismos autores para expresiones booleanas arbitrarias "vecindario" y "densidad". Los parámetros y minPts se eliminan del algoritmo y se transfieren a condiciones booleanas. Por ejemplo, en datos poligonales, "vecindario" puede ser cualquier intersección de polígonos, mientras que la condición de densidad utiliza el área en lugar del recuento de entidades. $\epsilon$

Se han propuesto varias extensiones del algoritmo DBSCAN, incluidos métodos de paralelización, estimación de parámetros y soporte para datos cuestionables. La idea básica se ha extendido a la agrupación jerárquica mediante el algoritmo OPTICS . El algoritmo DBSCAN también se ha utilizado como parte de algoritmos de agrupamiento subespacial como PreDeCon y SUBCLU . HDBSCAN [8] es una versión jerárquica de DBSCAN, que también es más rápida que OPTICS, y en la que se puede extraer una partición plana de la jerarquía, que consta de los clústeres más visibles [11] .

Disponibilidad

Se encontraron varias implementaciones del algoritmo con una gran diferencia en el rendimiento, la más rápida completó el trabajo en los datos de prueba en 1,4 segundos y la más lenta en 13803 segundos [12] . La diferencia se puede atribuir a la calidad de la implementación, la diferencia de lenguajes y compiladores, y el uso de índices para acelerar las cosas.

Apache Commons Math contiene una implementación Java de un algoritmo que se ejecuta en tiempo cuadrático.
ELKI proporciona una implementación de DBSCAN, GDBSCAN y otras opciones. Esta implementación puede usar diferentes estructuras de índice para proporcionar un tiempo de ejecución subcuadrático. En esta implementación, se pueden usar funciones de distancia arbitrarias y tipos de datos arbitrarios, y la aceleración se puede lograr mediante la optimización de bajo nivel y el uso de métodos especiales en pequeños conjuntos de datos.
PostGIS incluye ST_ClusterDBSCAN, una implementación bidimensional de DBSCAN que utiliza un árbol R como índice. Se admite cualquier tipo de geometría, como punto, línea, polígono , etc.
En el lenguaje R , el paquete fpc contiene DBSCAN con soporte para una función de distancia arbitraria a través de matrices de distancia. Sin embargo, la implementación no admite índices (y, por lo tanto, tiene un tiempo de ejecución cuadrático y una complejidad temporal), y hay que decir que la implementación es lenta debido al uso del intérprete de R. Una implementación de C ++ más rápida usando árboles kd (solo para distancias euclidianas) está en el paquete R dbscan .
scikit-learn incluye una implementación de Python de DBSCANpara métricas arbitrarias de Minkowski , que se pueden acelerar con árboles kd y árboles de bolas , pero que utilizan memoria cuadrática en el peor de los casos. El paquete complementario para scikit-learn proporciona una implementación del algoritmo HDBSCAN*.
La biblioteca de pyclustering incluye una implementación de Python y C++ de DBSCAN solo para la distancia euclidiana, así como una implementación del algoritmo OPTICS.
SPMF incluye una implementación del algoritmo DBSCAN con soporte de árbol kd solo para la distancia euclidiana.
Weka contiene (como paquete opcional en la última versión) una implementación básica de DBSCAN que requiere memoria lineal y se ejecuta en tiempo cuadrático.

Notas

↑ 1 2 3 Ester, Kriegel, Sander, Xu, 1996 , pág. 226–231.
↑ Búsqueda académica de Microsoft, 2010 .
↑ Premio Prueba del Tiempo, 2014 .
↑ 12 Ling , 1972 , pág. 326–332.
↑ 1 2 Si bien minPts es intuitivamente el tamaño mínimo de clúster, en algunos casos DBSCAN puede producir clústeres más pequeños ( Schubert, Sander, Ester, Kriegel, Xu 2017 ). Un grupo DBSCAN consta de al menos un punto central . Dado que otros puntos pueden ser puntos de borde de más de un grupo, no hay garantía de que se incluyan al menos minPts de puntos en cada grupo.
↑ 1 2 3 4 5 6 7 8 9 Schubert, Sander, Ester, Kriegel, Xu, 2017 , pág. 19:1–19:21.
↑ 1 2 3 4 Sander, Ester, Kriegel, Xu, 1998 , pág. 169–194.
↑ 1 2 3 Campello, Moulavi, Zimek, Sander, 2015 , p. 1–51.
↑ Kriegel, Kröger, Sander, Zimek, 2011 , pág. 231–240.
↑ Lijadora, 1998 .
↑ Campello, Moulavi, Zimek, Sander, 2013 , p. 344.
↑ Kriegel, Schubert, Zimek, 2016 , pág. 341.

Literatura

Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu. Un algoritmo basado en densidad para descubrir clústeres en grandes bases de datos espaciales con ruido // Actas de la Segunda Conferencia Internacional sobre Descubrimiento de Conocimiento y Minería de Datos (KDD-96) / Evangelos Simoudis, Jiawei Han, Usama M. Fayyad. - AAAI Press , 1996. - S. 226-231 . — ISBN 1-57735-004-9 .
Jörg Sander, Martin Ester, Hans-Peter Kriegel, Xiaowei Xu. Clustering basado en densidad en bases de datos espaciales: el algoritmo GDBSCAN y sus aplicaciones // Minería de datos y descubrimiento de conocimiento. - Berlín: Springer-Verlag , 1998. - Vol. 2 , núm. 2 . — S. 169–194 . -doi : 10.1023/A : 1009745219419 .

Búsqueda académica de Microsoft . - 2010. Archivado el 21 de abril de 2010. La mayoría de los artículos de minería de datos citados por la búsqueda académica de Microsoft; DBSCAN se encuentra en 24 posiciones.
Premio SIGKDD Prueba del Tiempo 2014 . — ACM SIGKDD, 2014.
Ling RF Sobre la teoría y construcción de k-clusters // The Computer Journal. - 1972. - T. 15 , núm. 4 . — ISSN 0010-4620 . -doi : 10.1093 / comjnl/15.4.326 .
Erich Schubert, Jörg Sander, Martin Ester, Hans Peter Kriegel, Xiaowei Xu. DBSCAN revisado, revisado: por qué y cómo debe (todavía) usar DBSCAN // ACM Trans. Database Syst. - 2017. - julio ( vol. 42 , número 3 ). — ISSN 0362-5915 . -doi : 10.1145/ 3068335 .
Hans-Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek. Clustering basado en la densidad // WIREs Data Mining and Knowledge Discovery. - 2011. - Vol. 1 , número. 3 . — S. 231–240 . -doi : 10.1002/ widm.30 .
Ricardo JGB Campello, Davoud Moulavi, Arthur Zimek, Jörg Sander. Estimaciones de densidad jerárquica para agrupación de datos, visualización y detección de valores atípicos // Transacciones de ACM en el descubrimiento de conocimiento a partir de datos. - 2015. - T. 10 , núm. 1 . — ISSN 1556-4681 . -doi : 10.1145/ 2733381 .
Jorge Sander. Clustering basado en la densidad generalizada para la minería de datos espaciales. - Herbert Utz Verlag, 1998. - ISBN 3-89675-469-6 .
Campello RJGB, Moulavi D., Zimek A., Sander J. Un marco para la extracción óptima semisupervisada y no supervisada de clústeres de jerarquías // Minería de datos y descubrimiento de conocimiento. - 2013. - T. 27 , núm. 3 . -doi : 10.1007/ s10618-013-0311-4 .
Hans-Peter Kriegel, Erich Schubert, Arthur Zimek. El arte (negro) de la evaluación en tiempo de ejecución: ¿Estamos comparando algoritmos o implementaciones? // Conocimiento y Sistemas de Información. - 2016. - T. 52 , núm. 2 . - art. 341 . — ISSN 0219-1377 . -doi : 10.1007/ s10115-016-1004-2 .

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ICA LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG