Escaneo de base de datos

El agrupamiento espacial basado en densidad de aplicaciones con ruido ( DBSCAN ) es un algoritmo de agrupamiento 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 agrupamiento basado en densidad : dado un conjunto de puntos en algún espacio, agrupa los puntos que están muy juntos (puntos con muchos vecinos cercanos ) y marca como valores atípicos los puntos que se encuentran solos en regiones de baja densidad (aquellos cuyos vecinos más cercanos están demasiado lejos). DBSCAN es uno de los algoritmos de agrupamiento más utilizados y citados. ^[2]

En 2014, el algoritmo recibió el premio Test of Time Award (un premio otorgado a algoritmos que han recibido una atención sustancial en teoría y práctica) en la conferencia líder en minería de datos, ACM SIGKDD . ^[3] A partir de julio de 2020 ^[update], el artículo 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 de la prestigiosa revista ACM Transactions on Database Systems (TODS) . ^[5]

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

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 un peor caso de O(n²), y la formulación de consulta de rango orientada a la base de datos de DBSCAN permite la aceleración de índices. Los algoritmos difieren ligeramente en su manejo de puntos de borde.

Consideremos un conjunto de puntos en algún espacio que se van a agrupar. Sea ε un parámetro que especifica el radio de un vecindario con respecto a algún punto. Para el propósito de la agrupación 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 minPts puntos están dentro de la distancia ε de él (incluido p ).
• Un punto q es directamente accesible desde p si el punto q está dentro de la distancia ε del punto central p . Solo se dice que los puntos son directamente accesibles desde puntos centrales.
• Un punto q es alcanzable desde p si existe un camino p ₁ , ..., p _n con p ₁ = p y p _n = q , donde cada p _{i +1} es directamente alcanzable desde p _i . Nótese que esto implica que el punto inicial y todos los puntos en el 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, forma un conjunto junto con todos los puntos (centrales o no centrales) a los que se puede llegar desde él. Cada conjunto contiene al menos un punto central; los puntos no centrales pueden formar parte de un conjunto, pero forman su "borde", ya que no se pueden utilizar para llegar a más puntos.

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

Un clúster satisface entonces dos propiedades:

1. Todos los puntos dentro del cúmulo están conectados entre sí por densidad.
2. Si un punto es alcanzable en densidad desde algún punto del cúmulo, también es parte del cúmulo.

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 inicio arbitrario que no se ha visitado. Se recupera el entorno ε de este punto y, si contiene suficientes puntos, se inicia un clúster. De lo contrario, el punto se etiqueta como ruido. Tenga en cuenta que este punto podría encontrarse más adelante en un entorno ε de tamaño suficiente de un punto diferente y, por lo tanto, formar parte de un clúster.

Si se descubre que un punto es una parte densa de un cúmulo, su vecindad ε también forma parte de ese cúmulo. 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 por completo el cúmulo conectado por densidad. Luego, se recupera y procesa un nuevo punto no visitado, lo que conduce al descubrimiento de otro cúmulo 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 verse como 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 bucle interno */ 
        Vecinos N := RangeQuery(DB, distFunc, P, eps)      /* Encontrar vecinos */ 
        si |N| < minPts entonces {                               /* Verificación de densidad */ 
            etiqueta(P) := Ruido                                /* Etiqueta como ruido */ 
            continuar
        }
        C := C + 1                                           /* siguiente etiqueta del clúster */ 
        label(P) := C                                        /* Etiquetar punto inicial */ 
        SeedSet S := N \ {P}                                 /* Vecinos a expandir */ 
        para cada punto Q en S {                              /* Procesar cada punto semilla Q */ 
            si label(Q) = Noise entonces label(Q) := C           /* Cambiar Noise al punto límite */ 
            si label(Q) ≠ undefined entonces  continuar            /* Procesado previamente (por ejemplo, punto límite) */ 
            label(Q) := C                                    /* Etiquetar vecino */ 
            Vecinos N := RangeQuery(DB, distFunc, Q, eps) /* Encontrar vecinos */ 
            si |N| ≥ minPts entonces {                           /* Verificación de densidad (si Q es un punto central) */ 
                S := S ∪ N                                   /* Agregar nuevos vecinos al conjunto semilla */
            }
        }
    }
}

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

Consulta de rango (DB, distFunc, Q, eps) {
    Vecinos N := lista vacía
    para cada punto P en la base de datos DB {                       /* Escanear todos los puntos en la base de datos */ 
        si distFunc(Q, P) ≤ eps entonces {                      /* Calcular la distancia y comprobar épsilon */ 
            N := N ∪ {P}                                    /* Agregar al resultado */
        }
    }
    devolver N
}

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

1. Encuentre los puntos en el vecindario ε (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 clúster cercano si el clúster es un vecino ε (eps); de lo contrario, asígnelo al ruido.

Una implementación sencilla de esto requiere almacenar los vecindarios en el paso 1, lo que requiere una cantidad sustancial de memoria. El algoritmo DBSCAN original no requiere esto, ya que realiza estos pasos para un punto a la vez.

DBSCAN optimiza la siguiente función de pérdida: ^[10] Para cualquier agrupamiento posible del conjunto de todos los agrupamientos , minimiza el número de agrupamientos bajo la condición de que cada par de puntos en un agrupamiento sea alcanzable por densidad, lo que corresponde a las dos propiedades originales "maximalidad" y "conectividad" de un agrupamiento: ^[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 más pequeño tal que dos puntos p y q están densamente conectados. ${\displaystyle d_{db}(p,q)}$${\displaystyle \varepsilon }$

DBSCAN visita cada punto de la base de datos, posiblemente varias veces (por ejemplo, como candidatos a diferentes clústeres). Sin embargo, por consideraciones prácticas, la complejidad temporal se rige principalmente por la cantidad 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 el parámetro ε se elige de una manera significativa, es decir, de modo que, en promedio, solo 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 de tiempo de ejecución del peor caso 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 O( n² ) de memoria, mientras que una implementación de DBSCAN no basada en matriz solo necesita O( n ) de memoria. ${\displaystyle \textstyle {\binom {n}{2}}}$

1. DBSCAN no requiere que se especifique el número de clústeres en los datos a priori, a diferencia de k-means .
2. DBSCAN puede encontrar grupos de formas arbitrarias. Incluso puede encontrar un grupo completamente rodeado por (pero no conectado a) un grupo 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 robusto ante valores atípicos .
4. DBSCAN requiere solo dos parámetros y, en su mayor parte, no es sensible 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 su pertenencia al grupo si se modifica 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 las consultas de región, por ejemplo, utilizando un árbol R* .
6. Los parámetros minPts y ε pueden ser configurados por un experto en la materia, si se comprenden bien los datos.

1. DBSCAN no es completamente determinista: los puntos de frontera a los que se puede llegar desde más de un clúster pueden ser parte de cualquiera de los clústeres, dependiendo del orden en que se procesen los datos. Para la mayoría de los conjuntos de datos y dominios, esta situación no se presenta a menudo 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 de frontera 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 ε. Sin embargo, este efecto 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 puede elegirse apropiadamente 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 a continuación sobre extensiones para obtener modificaciones algorítmicas para manejar estos problemas.

Toda tarea de minería de datos tiene el problema de los parámetros. Cada parámetro influye en el algoritmo de maneras 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 de clúster mínimo deseado. ^[a]

• MinPts : como regla general, se puede derivar un minPts mínimo a partir del número de dimensiones D en el conjunto de datos, ya que minPts ≥ D + 1. El valor bajo de minPts = 1 no tiene sentido, ya que cada punto es un punto central por definición. Con minPts ≤ 2, el resultado será el mismo que el de la agrupación jerárquica con la métrica de enlace único, con el dendrograma cortado a la altura ε. Por lo tanto, minPts debe elegirse al menos en 3. Sin embargo, los valores más grandes suelen ser mejores para los conjuntos de datos con ruido y producirán agrupaciones más significativas. Como regla general, se puede utilizar minPts = 2· dim , ^[9] pero puede ser necesario elegir valores más grandes para datos muy grandes, para datos ruidosos o para datos que contienen muchos duplicados. ^[4]
• ε: El valor para ε puede entonces elegirse usando un gráfico de k-distancia , trazando la distancia al vecino más cercano k = minPts -1 ordenado del valor más grande al más pequeño. ^[4] Los buenos valores de ε son 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 solo 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 en sí 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 gran impacto 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 de manera apropiada para el conjunto de datos. Por ejemplo, en los datos geográficos, la distancia del círculo máximo suele ser una buena opción.

OPTICS puede considerarse una generalización de DBSCAN que reemplaza el parámetro ε por un valor máximo que afecta principalmente al rendimiento. MinPts se convierte entonces esencialmente en el tamaño mínimo de clúster que se debe buscar. 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 partición de datos simple 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 de borde. En cambio, solo los puntos centrales forman el grupo.

Una implementación espectral de DBSCAN está relacionada con la agrupación espectral en el caso trivial de determinar los componentes de un gráfico conectado : las agrupaciones óptimas sin cortes de aristas. ^[12] Sin embargo, puede requerir un gran esfuerzo computacional, hasta . Además, hay que elegir la cantidad de vectores propios que se calcularán. Por razones de rendimiento, el algoritmo DBSCAN original sigue siendo preferible a su implementación espectral. ${\displaystyle O(n^{3})}$

El algoritmo DBSCAN generalizado (GDBSCAN) ^{[9] [13]} es una generalización de los mismos autores a predicados arbitrarios de "vecindario" y "denso". Los parámetros ε y minPts se eliminan del algoritmo original y se trasladan a los predicados. Por ejemplo, en los datos de polígonos, el "vecindario" podría ser cualquier polígono que se intersecte, mientras que el predicado de densidad utiliza las áreas de los polígonos 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 extendido a la agrupación jerárquica mediante el algoritmo OPTICS . DBSCAN también se utiliza como parte de algoritmos de agrupación de subespacios 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 que se puede extraer una partición plana que consta de los clústeres más destacados de la jerarquía. ^[14]

Se encontró que diferentes implementaciones del mismo algoritmo exhibían enormes diferencias de rendimiento: la más rápida en un conjunto de datos de prueba finalizaba en 1,4 segundos, mientras que la más lenta tardaba 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 de GDBSCAN y otras variantes. Esta implementación puede utilizar varias estructuras de índice para tiempos de ejecución subcuadráticos 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 estadística y aprendizaje automático" desde la versión R2019a.
• mlpack incluye una implementación de DBSCAN acelerada con técnicas de búsqueda de rango de árbol dual.
• PostGIS incluye ST_ClusterDBSCAN, una implementación 2D de DBSCAN que utiliza un í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 a través de matrices de distancia. El paquete fpc no admite índices (y, por lo tanto, tiene una complejidad de memoria y tiempo de ejecución cuadráticos) y es bastante lento debido al intérprete de R. El paquete dbscan proporciona una implementación rápida en C++ que utiliza á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 de Minkowski arbitrarias , que se pueden acelerar utilizando árboles kd y árboles de bolas , pero que utilizan 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 la 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 del DBSCAN para el lenguaje de programación Rust .
• Julia incluye una implementación de DBSCAN en el paquete Clustering.jl de Julia Statistics.

• Análisis de conglomerados  : agrupación de un conjunto de objetos por similitud
• Agrupamiento k-means  : algoritmo de cuantificación vectorial que minimiza la suma de las desviaciones al cuadrado