Los métodos de partición y jerarquización están diseñados para encontrar clúster de forma esférica, sin embargo, estos tienen dificultad para encontrar clústers que se presentan con formas arbitraria como la forma de «S» u ovales. Con datos de esta naturaleza, los métodos anteriormente descritos tienen una probabilidad alta de segmentar incorrectamente clústers cuando la distribución de los datos se presenta en formas irregulares, donde el ruido o los valores atípicos se incluyen en los grupos. (Ester, Kriegel, Sander, & Xu, 2007)
Para encontrar clúster de formas arbitrarias, se puede modelar los clústers como regiones densas en el espacio de datos, separadas por regiones dispersas. Esta es la principal estrategia detrás de la agrupación métodos basados en la densidad, lo que puede descubrir grupos de forma no esférica. (Mann & Nagpal, 2001)
La densidad de un objeto se puede medir por el número de objetos cercanos al mismo. Por tanto, los métodos basados en densidad encuentran los objetos principales, es decir, los objetos que tienen los barrios densos, y conectan los objetos principales y sus barrios para formar regiones densas, clústers. La idea clave es que por cada punto de un clúster de la zona de un radio dado tiene que contener al menos un número mínimo de objetos. La forma del clúster estará determinada por la función de la distancia entre dos objetos. (Ester, Kriegel, Sander, & Xu, 2007)
El algoritmo DBSCAN, (Cluster Espacial Basado en Densidad para Aplicaciones con Ruido), uno de los principales algoritmos de los métodos basados en densidad, requiere dos variables de entrada:
- El radio que delimita el área del barrio de un punto (Eps)
- El número mínimo de puntos requeridos para formar un cluster (minPts).
Los puntos principales residen en el interior del cluster, y se sitúan dentro del radio Eps y son uno de los puntos mínimos que conforman el clúster. Por otro lado, los puntos fronterizos, se sitúan en la parte exterior del clúster, aunque también están dentro del radio Eps. (Mann & Nagpal, 2001)
El algoritmo DBSCAN se compone de los siguientes pasos:
- Seleccionar un punto de manera arbitraria.
- Obtener la densidad alcanzable desde cada punto, dentro del rango Eps y MinPts todos los puntos.
- Si el punto analizado:
- Es un punto central se forma clúster.
- Es un punto frontero, el algoritmo visita el siguiente punto de la base de datos.
- Continuar el proceso hasta que todos los puntos han sido procesados
Bibliografía
Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (8 de Enero de 2007). A Density-Based Algorithm for Discovering Clusters. Obtenido de Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining: http://www2.cs.uh.edu/~ceick/7363/Papers/dbscan.pdf
Mann, P., & Nagpal, P. (11 de Agosto de 2001). Comparative Study of Density based Clustering Algorithms. Obtenido de International Journal of Computer Applications: http://www.ijcaonline.org/volume27/number11/pxc3874600.pdf
DataWorld 