Razonamiento básico
Density-based spatial clustering of applications with noise (DBSCAN) fue introducido en 1996 por Ester et al. como una forma de identificar clusters siguiendo el modo intuitivo en el que lo hace el cerebro humano, identificando regiones con alta densidad de observaciones separadas por regiones de baja densidad. Eso puede usarse para identificar clusters de cualquier forma en un dataset que contenga ruido y valores atípicos.
En el gráfico anterior el cerebro humano identifica 5 clusters junto con algunas observaciones aisladas (ruido), incluyendo:
2 clusters ovales
2 clusters lineales
1 cluster compacto
Sin embargo, veamos los clusters que se obtienen si se aplica, por ejemplo, K-means clustering.
set.seed(123)
km.cluster <- kmeans(df, 5, nstart = 25)
fviz_cluster(km.cluster, df, frame = FALSE,
geom = "point", ellipse = FALSE, pallete = "jco") +
theme_bw() +
theme(legend.position = "none")
Los clusters generados distan mucho de representar las verdaderas agrupaciones. Esto es así porque los métodos de partitioining clustering como k-means, k-medoids, c-means, etc. son buenos encontrando agrupaciones con forma esférica o convexa que no contengan un exceso de outliers o ruido, pero fallan al tratar de identificar formas arbitrarias.
DBSCAN evita este problema al considerar que para que una observación forme parte de un cluster, tiene que haber un mínimo de observaciones vecinas dentro de un radio de proximidad y de que los clusters están separados por regiones vacías o con pocas observaciones.
Algoritmo
El objetivo es identificar regiones densas, que se pueden medir por la cantidad de objetos cercanos a un punto determinado.
El algoritmo DBSCAN necesita dos parámetros:
Epsilon (\(\epsilon\)): radio que define la región vecina a una observación, también llamada \(\epsilon-neighborhood\).
Minimum points (minPts): número mínimo de observaciones dentro de la región epsilon.
Empleando estos dos parámetros, cada observación del dataset se puede clasificar en una de las siguientes tres categorías:
Core point (Punto central): observación que tiene en su \(\epsilon-neighborhood\) un número de observaciones vecinas igual o mayor a minPts.
Border point (Punto fronterizo): observación que no satisface el mínimo de observaciones vecinas para ser core point pero que pertenece al \(\epsilon-neighborhood\) de otra observación que sí es core point.
Noise u outlier: observación que no es core point ni border point.
La siguiente figura muestra los diferentes tipos de puntos (central, frontera y outliers) usando MinPts = 6. Aquí \(x\) es un punto central porque \(neighbours_{\epsilon}(x) = 6\), \(y\) es un punto fronterizo porque \(neighbours_{\epsilon}(x) < MinPts\), pero pertenece a la vecindad \(\epsilon\) del punto central \(x\). Finalmente, \(z\) es un punto atípico.
Ahora definiremos 3 términos, necesarios para comprender el algoritmo DBSCAN:
Directamente alcanzable (direct density reachable): Un punto \(A\) es directamente de densidad alcanzable desde otro punto \(B\) si:
\(A\) está en la vecindad \(\epsilon\) de \(B\)
\(B\) es un punto central
Alcanzable (density reachable): Un punto \(A\) es la densidad alcanzable desde \(B\) si hay un conjunto de puntos centrales que van de \(B\) a \(A\).
Densamente conectadas (density conected): Dos puntos \(A\) y \(B\) están conectados por densidad si hay un punto central \(C\), de modo que tanto \(A\) como \(B\) tienen densidad alcanzable desde \(C\).
La siguiente imagen muestra las conexiones existentes entre un conjunto de observaciones si se emplea minPts = 4. La observación \(A\) y el resto de observaciones marcadas en rojo son puntos centrales, ya que todas ellas contienen al menos 4 observaciones vecinas (incluyéndose a ellas mismas) en su vecindad. Como todas son alcanzables entre ellas, forman un cluster. Las observaciones \(B\) y \(C\) no son puntos centrales pero son alcanzables desde \(A\) a través de otros puntos centrales, por lo tanto, pertenecen al mismo cluster que \(A\). La observación \(N\) no es ni un punto central ni es directamente alcanzable, por lo que se considera como ruido.
Algoritmo
Para cada observación \(x_i\) calcular la distancia entre ella y el resto de observaciones. Si en su vecindad hay un número de observaciones \(\geq minPts\) marcar la observación como punto central, de lo contrario marcarla como visitada.
Para cada observación \(x_i\) marcada como punto central, si todavía no ha sido asignada a ningún cluster, crear uno nuevo y asignarla a él. Encontrar recursivamente todas las observaciones densamente conectadas a ella y asignarlas al mismo cluster.
Iterar el mismo proceso para todas las observaciones que no hayan sido visitadas.
Aquellas observaciones que tras haber sido visitadas no pertenecen a ningún cluster se marcan como outliers.
Como resultado, todo cluster cumple dos propiedades: todos los puntos que forman parte de un mismo cluster están densamente conectados entre ellos y, si una observación \(A\) es densamente alcanzable desde cualquier otra observación de un cluster, entonces \(A\) también pertenece al cluster.
Ventajas y desventajas
Ventajas de DBSCAN
No requiere que el usuario especifique el número de clusters.
La forma que tengan los clusters es independiente ya que no tienen por qué ser circulares.
Puede identificar outliers, por lo que los clusters generados no serán influenciados por ellos.
Desventajas de DBSCAN
No es un método totalmente determinístico: los puntos fronterizos que son alcanzables desde más de un cluster pueden asignarse a uno u otro dependiendo del orden en el que se procesen los datos.
No genera buenos resultados cuando la densidad de los grupos es muy distinta, ya que no es posible encontrar los parámetros \(\epsilon\) y minPts que sirvan para todos a la vez.
Ejemplo
En R existen dos paquetes que permiten aplicar el algoritmo DBSCAN: fpc y dbscan. El segundo paquete contiene una modificación del algoritmo original que lo hace más eficiente. La función kNNdistplot() del paquete dbscan calcula y representa las k-distancias para ayudar a identificar el valor óptimo de epsilon.
# Selección del valor óptimo de epsilon. Como valor de minPts se emplea 5.
dbscan::kNNdistplot(df, k = 5)
abline(h = 0.15, lty = 2)
La curva tiene el punto de inflexión en torno a 0.15, por lo que se escoge este valor como \(\epsilon\) para DBSCAN.
# DBSCAN con epsilon = 0.15 y minPts = 5
dbscan_cluster <- fpc::dbscan(data = df, eps = 0.15, MinPts = 5)
# Resultados de la asignación
print(dbscan_cluster)dbscan Pts=1100 MinPts=5 eps=0.15
0 1 2 3 4 5
border 31 24 1 5 7 1
seed 0 386 404 99 92 50
total 31 410 405 104 99 51En la tabla anterior, número de la primer fila corresponden a los nombres de los clusters. El cero corresponde a valores atípicos (puntos negros en el gráfico DBSCAN).
# Visualización de los clusters
fviz_cluster(object = dbscan_cluster, data = df, stand = FALSE,
geom = "point", ellipse = FALSE, show.clust.cent = FALSE,
pallete = "jco") +
theme_bw() +
theme(legend.position = "bottom")
Algunos consejos
Selección de parámetros
Como ocurre en otras técnicas estadísticas, para DBSCAN no existe una forma única y exacta de encontrar el valor adecuado de \(\epsilon\) y de minPts. Pero como guía se puede seguir lo siguiente:
minPts: cuanto mayor sea el tamaño del dataset, mayor debe ser el valor mínimo de observaciones vecinas. El valor mínimo debe ser 3. Si los datos contienen niveles altos de ruido, aumentar minPts favorecerá la creación de clusters menos influenciados por outliers.
epsilon: una buena forma de escoger su valor es estudiar las distancias promedio entre las k = minPts observaciones más próximas. Al representar estas distancias en función de \(\epsilon\), el punto de inflexión de la curva suele ser un valor óptimo. Si el valor de \(\epsilon\) escogido es muy pequeño, una proporción alta de las observaciones no se asignarán a ningún cluster, por el contrario, si el valor es demasiado grande, la mayoría de observaciones se agruparán en un único cluster.