« Planificación: Fundam… « || Inicio ||

Algoritmos de Clustering

Última modificación: 5 de Diciembre de 2019, y ha tenido 35 vistas

Etiquetas utilizadas: || || || ||

Clustering

Como hemos visto ya en otras entradas un algoritmo de clustering tiene como objetivo agrupar los objetos de un dataset según su similaridad, de forma que los objetos que hay dentro de un grupo (cluster) sean más similares que aquellos que caen en grupos distintos.

Para resolver este problema se han desarrollado muchos algoritmos que se diferencian entre sí según qué se entiende por cluster (que, en esencia, viene dado por cómo definimos que dos objetos son más o menos similares) y por la eficiencia computacional a la hora de conseguir la agrupación final.

Normalmente, para poder hablar de similaridad se suele acudir a algún tipo de distancia (a veces nos conformamos con algo que no llega a cumplir todas las propiedades de una distancia/métrica y trabajamos con pseudo-métricas), con el fin de poder asociar la similitud de los objetos analizados con la distancia que hay entre ellos. Por ejemplo, si podemos describir el objeto por medio de un vector numérico de propiedades, es entonces habitual tratar con métricas vectoriales (como la distancia euclídea) para medir la similitud entre los objetos.

Según la forma en que los clusters se relacionan entre sí y con los objetos del dataset, podemos establecer una primera división entre los diversos algoritmos existentes:

  • Clustering Duro: donde cada objeto pertenece a un solo cluster (por lo que los clusters pasarían a ser algo así como una partición del dataset).
  • Clustering Blando (o difusa): donde los objetos pertenecen a los clusters según un grado de confianza (o grado de pertenencia).

Pero a veces también podemos encontrar una clasificación más fina atendiendo a cómo se relacionan con detalle:

  • Partición estricta: cada objeto pertenece exactamente a un cluster.
  • Partición estricta con outliers: puede haber objetos que no pertenecen a ningún cluster (los outliers).
  • Clustering con superposiciones: un objeto puede pertenecer a más de un cluster.
  • Clustering Jerárquico: Los clusters se ordenan jerárquicamente de forma que los objetos que pertenecen a un cluster también pertenecen a su cluster padre.

Entre la diversidad de aproximaciones existentes en la literatura, en esta entrada nos vamos a centrar en algunas de las más representativas (se pueden encontrar implementaciones específicas de los algoritmos para NetLogo aquí). Concretamente, los algoritmos que veremos a continuación son:

  1. K-medias: modelo de centroides:

  2. DBSCAN: modelo de densidad discreto:

  3. Mean Shift: modelo de gradientes en densidad:

  4. AGNES: modelo jerárquico por agrupamiento:

K-medias

Este algoritmo intenta encontrar una partición de las muestras en $K$ (parámetro del algoritmo) agrupaciones, de forma que cada ejemplo pertenezca a una de ellas, concretamente a aquella cuyo centroide esté más cerca. El mejor valor de $K$ para que la clasificación separe lo mejor posible los ejemplos no se conoce a priori, y depende completamente de los datos con los que trabajemos. Este algoritmo intenta minimizar la varianza total del sistema, es decir, si $c_i$ es el centroide de la agrupación $i$-ésima, y $\{x_{ij}\}$ es el conjunto de ejemplos clasificados en esa agrupación, entonces intentamos minimizar la función:

$$ \sum_i \sum_j d(x_{ij},c_i)^2 $$

que, a veces suele denominarse función potencial.

Aunque podríamos utilizar cualquier algoritmo de optimización para realizar esta tarea, en este caso existe un algoritmo recursivo que converge a una solución local (un mínimo local de la función potencial) de forma rápida y relativamente eficiente:

K-MEANS(D,K) [D: Dataset, K > 0]
C = {c1,...,ck} D (cualesquiera)
Asignar Di = {P ϵ D: d(P,ci) < d(P,cj), j i}, i = 1...K
Mientras algún ci cambie:
Calcular ci = centroide(Di), i=1...K
Recalcular Di, i = 1...K
Devolver {D1,...,DK}

El algoritmo anterior es relativamente eficiente, y normalmente se requieren pocos pasos para que el proceso se estabilice. Pero en contra, es necesario determinar el número de agrupaciones a priori, y el sistema es sensible a la posición inicial de los $K$ clusters seleccionar, haciendo que no consigan un mínimo global, sino que se sitúe en un mínimo local (algo muy común cuando se trabaja con un problema de optimización no convexo).

Por desgracia, no existe un método teórico global que permita encontrar el valor óptimo de grupos iniciales ni las posiciones en las que debemos situar los centros, por lo que se suele hacer una aproximación experimental repitiendo el algoritmo con diversos valores y posiciones de centros. En general, un valor elevado de $K$ hace que el error disminuya, pero a cambio disminuye la cantidad de información que la agrupación resultante proporciona.

DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) es un algoritmo de clustering creado en 1996, no paramétrico, basado en densidades, y que marca como outliers aquellos puntos que no superan un umbral de densidad establecido. Constituye uno de los algoritmos de clustering más usados y citados, y también es relativamente eficiente cuando se usan estructuras de datos adecuadas para su implementación (pudiendo llegar a ser de tiempo $O(n^2)$ en el peor caso).

El algoritmo depende recibe como dato de entrada dos valores que juntos determinan la densidad mínima: $\varepsilon$ (que fija el radio de los entornos que se mirarán alrededor de los puntos del conjunto), y $MinPts$ (que establece el número mínimo de puntos que debe haber en el entorno para que se considere que se supera la densidad mínima).

Con estos parámetros prefijados, el algoritmo opera como sigue:

DBSCAN(D, ε, MinPts) [D: Dataset; ε > 0; MinPts >0]
  C =
  Para cada P ϵ D no visitado:
    Marcar P como visitado
    N = E(P, ε)
    Si tamaño(N) < MinPts:
      marcar P como OUTLIER
    si no:
      C = C ⋃ {creaCluster(P, N, ε, MinPts)}
  Devolver C

Donde:

creaCluster(P, N, ε, MinPts) [P ϵ D; N entorno de P; ε > 0; MinPts > 0]
  Cl = {P}
  Para cada P' ϵ N:
    Si P' no ha sido visitado:
      marcar P' como visitado
      N' = E(P', ε)
      Si tamaño(N')  MinPts:
        N = N  N'
    Si P' no está en ningún cluster:
      Cl = Cl  {P'}
  Devolver Cl

y

$$ E(P,\varepsilon)=\{P'\in D:\ d(P,P')<\varepsilon\} $$

Esencialmente, el algoritmo comienza por un punto con suficiente densidad y va construyendo un cluster añadiendo puntos cercanos relevantes al mismo. Cuando acaba de construir un cluster, salta a otro punto con suficiente densidad y construye otro cluster independiente.

En comparación con K-medias, DBSCAN presenta las siguientes ventajas:

  • No es necesario especificar del número de clusters deseado.
  • Puede encontrar clusters con formas geométricas arbitrarias. Gracias al parámetro $MinPts$, se reduce la posibilidad de que aparezcan clusters distintos conectados por una delgada línea de puntos.
  • Tiene capacidad de detectar outliers (y ruido).
  • Solo necesita dos parámetros y no importa el orden de recorrido de los puntos para la construcción final de los clusters (solo puede haber indeterminismo en los puntos fronterizos entre dos clusters distintos, que pueden acabar asignados a uno u otro, pero no es fácil que ocurra, y el número de puntos involucrados es comparativamente bajo).
  • Usando estructuras de datos adecuadas se puede dar una implementación bastante más rápida.

A cambio, presenta algunas desventajas, que no son específicas, sino comunes a muchos algoritmos de clustering:

  • El uso de distancias equivalentes a la euclídea puede dar resultados indeseados en dimensiones altas.
  • Los valores de $(MinPts,\ \varepsilon)$ se pueden adaptar para tratar conjuntos de densidades específicas, por lo que si hay conjuntos con mucha diferencia en sus densidades, no hay combinación de valores que puedan trabajar adecuadamente para todos ellos a la vez.

Además, se puede usar en datasets que no se representan necesariamente en espacios vectoriales, ya que solo precisa tener definida una distancia entre puntos, no de la representación completa.

Mean Shift

Esta aproximación se basa en el concepto de Kernel de Estimación de Densidad (KDE). La idea es suponer que el conjunto de puntos que se quiere procesar proviene del muestre de una distribución de probabilidad desconocida. KDE proporciona un método para estimar la distribución subyacente. Funciona poniendo una función (kernel) en cada uno de los puntos que representa una ponderación. Hay muchas posibles funciones que usar como ponderaciones puntuales, pero quizás la más habitual es el kernel Gaussiano.

$$ K(x)=e^{-\frac{(x-x_i)^2}{2h^2} } $$

Cambiando la función kernel (o los parámetros de un kernel específico) se obtiene una estimación distinta de la función de densidad. Por ejemplo, si los kernels son muy concentrados en cada punto (en el kernel Gaussiano se consigue haciendo $h\approx 0$ muy pequeño), entonces la función de densidad obtenida separará los puntos entre sí (como pequeños picos que los aíslan), si los kernels son muy suavizados (en el kernel Gaussiano se consigue haciendo $h\approx 1$), entonces la función de densidad se asemejará a una gran meseta que conecta los diversos puntos entre sí.

Una vez obtenida la función de densidad, asociada a una posible distribución de probabilidad que ha generado del dataset, se puede usar esta densidad para establecer los distintos clusters que se asocian a la distribución de puntos. Para saber qué puntos están en el mismo cluster, el algoritmo Mean Shift aplica un proceso de ascenso de la colina y ver cuáles acaban en el mismo máximo (de esta forma, se asocia cada cluster con las diversas cuencas de atracción de la función de densidad).

Así pues, el algoritmo se podría describir brevemente como:

MEAN-SHIFT(D,K) [D: Dataset; K: kernel]
f(x) = _{P ϵ D} K_P(x) (función de densidad centrada en P a partir de K)
M = Para cada P ϵ D:
M = M Max(f,P) (aplicando grad(f) desde P) Para cada m ϵ M:
C_m = {P ϵ D: Max(f,P) = m}
Devolver {C_m: m ϵ M}

El hecho de que Mean Shift no haga suposiciones acerca del número de clusters, o de la forma que tienen éstos, lo convierten en un método ideal para trabajar con un número arbitrario de clusters y de formas arbitrarias. Aunque realmente el algoritmo que se ha explicado es realmente un algoritmo de optimización (los clusters se identifican con los máximos de la función de densidad), el uso de las diversas cuencas de atracción como clusters del dataset original proporciona una ingeniosa (y fructífera) identificación entre conceptos provenientes de mundos intuitivamente lejanos.

AGNES

Vamos a ver el que se conoce como algoritmo AGNES (Agglomerative Nesting), que es un algoritmo de clustering aglomerativo, es decir, va construyendo una jerarquía creciente de clusters desde los clusters más pequeños posibles, los puntos aislados, hasta el mayor cluster posible, que agrupa todos los puntos del dataset.

En general, este algoritmo sigue los siguientes pasos:

AGNES(D,N) [D: Dataset, N > 0]
Cls = { {P} : P ϵ D} (un cluster unitario para cada P ϵ D) Mientras |Cls| > N:
Sean C1, C2 en Cls: d(C1,C2) = min {d(Ci,Cj): Ci,Cj ϵ Cls}
C12 = C1 C2
Cls = Cls - {C1,C2} {C12}
Devolver Cls

La única diferencia que se puede introducir en este algoritmo es acerca de cómo medir la distancia entre clusters para reconocer los más cercanos. Es lo que se conoce como Métodos de Conexión, y supuesto que tenemos una distancia, $d$, definida entre los puntos del dataset, las distancias entre clusters más habituales son:

  1. Conexión completa: $d_{max}(C_1,C_2)=max\{d(x_1,x_2):\ x_1\in C_1,\ x_2\in C_2\}$.
  2. Conexión simple: $d_{min}(C_1,C_2)=min\{d(x_1,x_2):\ x_1\in C_1,\ x_2\in C_2\}$.
  3. Conexión media: $d_{mean}(C_1,C_2)=mean\{d(x_1,x_2):\ x_1\in C_1,\ x_2\in C_2\}$.
  4. Conexión centroide: $d_{cent}(C_1,C_2)=d(c_1,c_2)$ donde $c_i=centroide(C_i)$.

Se debe tener en cuenta que no hay ninguna elección mejor que otra, y que diferentes distancias ofrecerán diferentes agrupaciones.

Debido a la complejidad de representar simultáneamente toda la jerarquía de clusters que aparece en este tipo de algoritmos, se han ideado formas esquemáticas para mostrarlos atendiendo al orden y dando una idea de la lejanía que hay entre los diversos clusters que aparecen. La más común de ellas es la que se conoce como dendogramas, que permiten hacerse una idea de todas las agrupaciones de forma bastante sencilla:

En este tipo de representaciones, además, la altura de los bloques representa la distancia entre los clusters que se unen. En cada altura, el número de ejes verticales indica cuántos clusters hay en ese nivel jerárquico.

Este tipo de algoritmos tienen ventajas claras sobre el algoritmo base de K-medias, como por ejemplo que no necesita que los datasets se representen en espacios vectoriales, ya que solo precisa de la existencia de una distancia entre puntos, no de proyectarlos completamente. Por contra, no es especialmente adecuado cuando el dataset es muy grande.

Existen variantes similares que siguen el proceso contrario: partiendo del cluster formado por todos los elementos del dataset, van dividiendo sucesivamente los clusters presentes para separara aquellos en los que se encuentra mayor disimilaridad entre sus elementos.

« Planificación: Fundam… « || Inicio ||