Ver el código de «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 ([[Análisis de grupos|data clustering]]) propuesto por Martin Ester, [[Hans-Peter Kriegel]], Jörg Sander y Xiaowei Xu en 1996.<ref>{{Cite conference
 | author1-first = Martin | author1-last = Ester | author2-link = Hans-Peter Kriegel | author2-first = Hans-Peter | author2-last =Kriegel | first3 = Jörg | last3 = Sander | first4 = Xiaowei | last4 = Xu
 | title = A density-based algorithm for discovering clusters in large spatial databases with noise
 |  pages = 226–231
 | editor1-first = Evangelos | editor1-last = Simoudis | editor2-first = Jiawei | editor2-last = Han | editor3-first = Usama M. | editor3-last = Fayyad
 | booktitle = Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96)
 | publisher = [[AAAI Press]]
 | year = 1996
 | isbn = 1-57735-004-9 
 | id = 
}}</ref>
Es un algoritmo de agrupamiento basado en densidad ([[Cluster analysis#Density-based clustering|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.<ref>{{cita web |url=http://academic.research.microsoft.com/CSDirectory/paper_category_7.htm |título=Copia archivada |fechaacceso=10 de mayo de 2010 |urlarchivo=https://web.archive.org/web/20100421170848/http://academic.research.microsoft.com/CSDirectory/paper_category_7.htm |fechaarchivo=21 de abril 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</ref> [[OPTICS algorithm|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.<ref>{{cita web|url=http://www.kdd.org/blog/2014-sigkdd-test-time-award|fecha=18 de agosto de 2014|fechaacceso=22 de agosto de 2014|título=2014 SIGKDD Test of Time Award|editorial=ACM SIGKDD|urlarchivo=https://web.archive.org/web/20140826115955/http://www.kdd.org/blog/2014-sigkdd-test-time-award|fechaarchivo=26 de agosto de 2014}}</ref>

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 ==
[[Archivo:DBSCAN-Illustration.svg|miniaturadeimagen|400px|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 <math>p</math> 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 <math>p</math>. No es posible tener puntos directamente alcanzables desde un punto que no sea un núcleo.
* Un punto <math>q</math> es '''alcanzable''' desde <math>p</math> si existe una secuencia de puntos <math>p_1,...,p_n</math> donde <math>p_1=p</math> y <math>p_n=q</math> tal que cada punto <math>p_{i+1}</math> es directamente alcanzable desde <math>p_i</math>; es decir, todos los puntos de la secuencia deben ser puntos núcleos, con la posible excepción de <math>q</math>.
* Un punto que no sea alcanzable desde cualquier otro punto es considerado '''ruido'''. 
Si <math>p</math> 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 <math>p</math> y <math>q</math>  están ''conectados densamente'' si existe un punto <math>o</math> tal que ambos <math>p</math> y <math>q</math> sean directamente alcanzables desde <math>o</math>.  La relación ''estar densamente conectado'' ''es'' simétrica.

Un clúster, satisface por lo tanto dos propiedades:
# Todos los puntos del clúster están densamente conectados entre sí.
# 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*<ref name="hdbscan1" /> 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(teoría de grafos)|componentes conexas]]). El agrupamiento resultante, por lo general, contiene más nodos ruidosos.

== Algoritmo ==
DBSCAN requiere dos parámetros: <math>e</math> (eps) y el número mínimo de puntos requeridos para que una región se considere densa{{refn|name=minpts|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.}} (minPts). El algoritmo comienza por un punto arbitrario que no haya sido visitado. La <math>e</math>-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 <math>e</math>-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 <math>e</math>-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 ([[spatial index|indexing structure]]) que ejecute la consulta a los vecinos ([[fixed-radius near neighbors|neighborhood query]]) en {{math|O(log ''n'')}}, la complejidad temporal total sería {{math|O(''n'' log ''n'')}}. Sin usar la estructura de índice, la complejidad temporal sería {{math|O(''n''²)}}. A menudo, la [[matriz de distancias]] de tamaño {{math|(''n''²-''n'')/2}} se construye para evitar recalcular las distancias. Esto necesita {{math|O(''n''²)}} de memoria, mientras que con una implementación que no se base en matrices solo se necesita {{math|O(''n'')}} de memoria.

[[Archivo:DBSCAN-density-data.svg|miniaturadeimagen|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 ==
# DBSCAN no necesita de la especificación del número de clusters deseado como lo requiere [[K-means algorithm|k-means]].
# 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).
# DBSCAN tiene noción del ruido, y es robusto detectando [[anomaly detection|outliers]].
# 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.)
# DBSCAN está diseñado para bases de datos que puedan acelerar las consultas en regiones, e.g usando un [[R* tree]].

== Desventajas ==
# 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*<ref name="hdbscan1" /> 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.
# La calidad de DBSCAN depende de la noción de distancia ([[Metric (mathematics)|distance measure]]) usada en la función regionQuery(P,<math>e</math>). 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 <math>e</math>. Este efecto, sin embargo, también está presente en cualquier otro algoritmo basado en la distancia euclidiana.
# DBSCAN no puede agrupar conjuntos de datos bien con grandes diferencias en las densidades, ya que la combinación ''MinPts''-<math>e</math> 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 <math>e</math> y ''MinPts''. Estos deben ser especificados por el usuario. Idealmente, el valor de <math>e</math> 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.{{refn|name=minpts}}

* ''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 <math>e</math>. 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.
* <math>e</math>: El valor para <math>e</math> 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 <math>e</math> son donde este gráfico muestra una fuerte curvatura: si <math>e</math> es elegido demasiado pequeño, no se agrupan una gran parte de los datos; mientras que para un muy alto valor de <math>e</math>, 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 <math>e</math> 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 *),,<ref name="hdbscan1">{{cita publicación | editorial = Springer Berlin Heidelberg | isbn = 9783642374555 | idioma = en | título = Density-Based Clustering Based on Hierarchical Density Estimates | url = http://link.springer.com/chapter/10.1007/978-3-642-37456-2_14 | serie = Lecture Notes in Computer Science | fechaacceso = 8 de agosto de 2016 | doi = 10.1007/978-3-642-37456-2_14 | nombre1 = Ricardo J. G. B. | apellido1 = Campello | nombre2 = Davoud | apellido2 = Moulavi | nombre3 = Joerg | apellido3 = Sander | fecha = 14 de abril de 2013 | páginas = 160–172 | nombre-editor1 = Jian | apellidos-editor1 = Pei | nombre-editor2 = Vincent S. | apellidos-editor2 = Tseng | nombre-editor3 = Longbing | apellidos-editor3 = Cao | nombre-editor4 = Hiroshi | apellidos-editor4 = Motoda | nombre-editor5 = Guandong | apellidos-editor5 = Xu}}</ref><ref name="hdbscan2">{{cita publicación | doi = 10.1007/s10618-013-0311-4 | idioma = en | título = A framework for semi-supervised and unsupervised optimal extraction of clusters from hierarchies | url = http://link.springer.com/article/10.1007/s10618-013-0311-4 | páginas = 344–371 | volumen = 27 | fechaacceso = 8 de agosto de 2016 | publicación = Data Mining and Knowledge Discovery | nombre1 = R. J. G. B. | apellido1 = Campello | nombre2 = D. | apellido2 = Moulavi | nombre3 = A. | apellido3 = Zimek | nombre4 = J. | apellido4 = Sander | issn = 1384-5810 | fecha = 4 de abril de 2013 | número = 3}}</ref> que ya no tiene la noción de los puntos fronterizos.

== Extensiones ==

Generalized DBSCAN (GDBSCAN)<ref>{{cita publicación
 |first1       = Jörg
 |last1        = Sander
 |first2       = Martin
 |last2        = Ester
 |first3       = Hans-Peter
 |last3        = Kriegel
 |enlaceautor3 = Hans-Peter Kriegel
 |first4       = Xiaowei
 |last4        = Xu
 |título       = Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications
 |páginas      = 169–194
 |booktitle    = Data Mining and Knowledge Discovery
 |editorial    = [[Springer-Verlag]]
 |place        = Berlin
 |año          = 1998
 |doi          = 10.1023/A:1009745219419
 |url          = http://www.springerlink.com/content/n22065n21n1574k6
 |publicación  = Data Mining and Knowledge Discovery
 |volumen      = 2
 |número       = 2
}}</ref><ref>{{cita libro | nombre = Jörg | apellido = Sander | título = Generalized Density-Based Clustering for Spatial Data Mining | isbn=3-89675-469-6 | año=1998 | place = München | editorial = Herbert Utz Verlag }}</ref> es una generalización de los mismos autores a los algoritmos basados en vecindad y densidad. Los parámetros <math>e</math> 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<ref> name="hdbscan1" </ref>  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.<ref> name="hdbscan2" </ref>

== 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 [[Tipo de dato|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-tree]]s y [[ball tree]]s.

[[R (programming language)|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 (machine learning)|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 ==
{{listaref}}

=== Bibliografía ===
* {{cite conference
 | first1 = Domenica | last1 = Arlia | first2 = Massimo | last2 = Coppola
 | publisher=Springer Berlin
 | accessdate=<!-- 2004-02-19 -->
 | title=Experiments in Parallel Clustering with DBSCAN
 | booktitle = Euro-Par 2001: Parallel Processing: 7th International Euro-Par Conference Manchester, UK August 28–31, 2001, Proceedings
}}
* {{cita publicación | author1-link = Hans-Peter Kriegel | first1 = Hans-Peter | last1 = Kriegel | first2 = Peer | last2 = Kröger | author3-first = Jörg | author3-last = Sander | author4-first = Arthur | author4-last = Zimek | título = Density-based Clustering | publicación = WIREs Data Mining and Knowledge Discovery | volumen = 1 | número = 3 | año = 2011 | páginas = 231–240 | url = http://wires.wiley.com/WileyCDA/WiresArticle/wisId-WIDM30.html | doi = 10.1002/widm.30 | fechaacceso = 18 de diciembre de 2014 | fechaarchivo = 17 de noviembre de 2016 | urlarchivo = https://web.archive.org/web/20161117070919/http://wires.wiley.com/WileyCDA/WiresArticle/wisId-WIDM30.html | deadurl = yes }}

{{DEFAULTSORT:Dbscan}}
{{Control de autoridades}}
[[Categoría:Análisis de datos]]
[[Categoría:Algoritmos]]
[[Categoría:Minería de datos]]