CLUSTERING

DBSCAN

Hoy trabajaremos con el siguiente dataset que he creado usando esta utilísima web; drawdata.xyz

\[\Lambda = \{(x_i, y_i) , x_i \in X, y_i \in \{amarillo, verde, azul\} \}^m_{i=1}\]

Donde tenemos una serie de observaciones que pertenecen a tres clases diferentes; amarillo, verde y azul. El objetivo es encontrar estas clases de forma no-supervisada, mediante clustering.

Algoritmos tan famosos como k-means no van a poder encontrar una solución satisfactoria para la clasificación de estas regiones ya que estos datos no son separables de forma lineal. K-means no es siempre la única solución!

DBSCAN

DBSCAN es uno de los algoritmos de clustering más usados y citados. Propuesto por Martin Ester, Hans-Peter Kriegel, Jörg Sander y Xiaowei Xu en 1996, DBSCAN es un algoritmo de referencia cuando los datos no son linealmente separables.

DBSCAN calcula la densidad de cada región contando el número de vecinos de cada observación en nuestro dataset. Los vecinos de una observación $x_i$ serán todas aquellas observaciones que se encuentren a un radio $\epsilon$. Definimos por tanto los vecinos de una observación $x_i$ como:

\[N_{Eps}(x_i) = \{x_j \in D : d(x_j, x_i) \leq \epsilon \}\]

Una posible solución para encontrar los clústers sería obligar a que todos los puntos pertenecientes a un clúster tengan un número prefijado de vecinos:

\[|N_{Eps}| \geq MinPts\]

Pero no todos los puntos tienen por qué cumplir esta condición, van a existir diferentes tipos de estos.

Clases de puntos

Hay tres clases de puntos diferenciales en un clúster, los puntos que se encuentran dentro del clúster (puntos núcleo), los puntos en la frontera del clúster (puntos frontera) y los que no pertenecen al clúster (puntos ruido). Se define cada uno de ellos como:

  • Puntos núcleo: Si el número de vecinos es al menos un valor prefijado ($MinPts$)
  • Puntos frontera: Si es vecino de un punto núcleo
  • Puntos ruido: Si no es núcleo ni frontera

Relaciones

En general, los puntos núcleo van a tener un número de vecinos mucho mayor que un punto frontera. Por tanto, para cada punto $p$ del clúster, habrá un punto $q$ dentro del clúster de forma que $p$ será vecino de $q$ y $q$ tendrá al menos $MinPts$ vecinos. En este caso, diremos que $p$ es densamente directamente alcanzable desde $q$. De forma más formal;

Un punto $p$ es densamente directamente alcanzable desde $q$ si:

\[p \in N_{Eps}(q) \;\; \wedge \;\; |N_{Eps}(q)| \geq MinPts\]

Por otra parte, diremos que un punto $p$ es densamente alcanzable desde $q$ (punto núcleo) si existe una secuencia de puntos desde $q$ hasta $p$ ; $q,p_1, p_2,…, p$ de forma que $p_{i+1}$ es densamente directamente alcanzable desde $p_i$. O sea, si existe una secuencia de puntos densamente directamente alcanzables entre $p$ y $q$.

Con estas definiciones, dos puntos frontera no serían densamente alcanzables ya que ninguno cumpliría las propiedades de un punto núcleo. Pero en un clúster dos puntos frontera sí se pueden alcanzar, para terminar de definir la conectividad de un clúster debemos definir un último concepto; dos puntos $p$ y $q$ están densamente conectados si existe un punto $o$ tal que ambos $p$ y $q$ sean densamente alcanzables desde $o$.

Los puntos marcados como $A$ son puntos núcleo. Los puntos $B$ y $C$ son densamente alcanzables desde A y están densamente conectados. El punto $N$ es un punto ruido que no es núcleo ni densamente alcanzable.

Definimos un clúster como un conjunto no vacío de puntos que satisface dos condiciones:

  • Todos los puntos del clúster están densamente conectados entre sí
  • Si un punto $p$ es densamente alcanzable desde otro punto $q$, entonces $p$ también forma parte del clúster

El ruido es simplemente todos aquellos puntos que no pertenecen a ningún clúster; ¿outliers?

Algoritmo

Brevemente, este es el algoritmo que sigue DBSCAN. La implementación en python la podéis encontrar aquí; DBSCAN-Algoritmo

Entrada: epsilon, minpts, X

Etapa 1 Visitar un punto que aún no haya sido visitado

Etapa 2 Obtener los vecinos de la observación visitada usando como radio de la circunferencia; $\epsilon$

Etapa 3 Si el número de vecinos es mayor o igual que $MinPts$ entonces se llama a la función auxiliar; expandir_clúster y el punto se marca como visitado. En caso contrario, el punto se marca como ruido (pero más tarde puede acabar formando parte de un clúster)

Etapa 4 Si se llama a la función expandir_clúster entonces los vecinos de esa observación también forman parte del clúster y se repite el paso 2, 3 hasta que se encuentren todos los puntos del clúster

Etapa 5 Se sigue con otro punto que no haya sido visitado hasta que todos los puntos se marcan como visitados

Elección de hiperparámetros

Los parámetros iniciales de DBSCAN son $\epsilon$ (radio de la circunferencia) y $MinPts$ (valor de densidad aceptable para los puntos núcleo). Estos hiperparámetros son críticos ya que si escogemos un valor de $\epsilon$ demasiado grande, todos los puntos serán vecinos ya que la circunferencia podría abarcarlos a todos y se encontraría tan solo un clúster. Pero si $\epsilon$ es demasiado pequeño, cada observación solo tendría un único vecino (él mismo) y habrían tantos clústeres como observaciones.

Una forma de calcular el número óptimo de clusters es ir variando el valor de $\epsilon$ y $MinPts$ en cada iteración y comparar estos valores frente al número de clusters encontrados o frente a la cantidad de ruido encontrado.

Referencias