Algoritmos de 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.
Desde un punto de vista intuitivo, este problema tiene un objetivo muy claro: agrupar adecuadamente un conjunto de datos no etiquetados. A pesar de su intuición, la noción de "clúster/agrupamiento" no puede ser definido con precisión, una de las casusas por las que se ha propuesto un rango tan amplio de algoritmos de clustering (es interesante leer este blog).
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.
Axiomatización del Clustering
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.
Jon Kleinberg (J. Kleinberg, “An impossibility theorem for clustering” en Proceedings of the 15th International Conference on Neural Information Processing Systems, NIPS’02, pp. 463–470, MIT Press, 2002) propone tres axiomas que destacan las características que debe presentar un problema de agrupamiento y que pueden considerarse buenas, independientemente del algoritmo utilizado para encontrar la solución. Estos axiomas son (se puede ver una buena introducción aquí):
- Invariancia por escala: Un algoritmo de clustering no debe dar resultados distintos si se aplica una escala al conjunto de puntos.
- Consistencia: Un algoritmo de clustering no debe dar resultados distintos si las distancias dentro de cada clúster se reducen, o si las distancias entre clusters se aumentan.
- Riqueza: La función de agrupación debe ser lo suficientemente flexible como para producir cualquier partición/agrupación arbitraria del conjunto de datos de entrada.
El resultado más interesante del trabajo de Kleinberg es que, pese al claro carácter intuitivo de estos axiomas, no se puede construir una función de agrupamiento que verifique los tres simultáneamente.
Y ya que los tres axiomas no pueden verificarse simultáneamente, se pueden diseñar algoritmos de clustering que violan uno de los axiomas mientras se verifican los otros dos. Kleinberg ilustra este punto describiendo tres variantes del tipo particular de jerárquico (que veremos más abajo, como ejemplo de algoritmo de clustering):
- Condición de parada del $k$-cluster: Dejar de unir clústers cuando ya hay $k$ clústers (viola el axioma de riqueza, ya que el algoritmo nunca devolvería un número de clusters diferente a $k$).
- Condición de parada de la $r$-distancia: Dejar de unir clústers cuando el par más cercano de ellos está más lejos que $r$ (viola la invariancia de escala, ya que cada clúster contendrá una sola instancia cuando la escala es grande, y un solo clúster con todos los datos cuando la escala es muy pequeña).
- Condición de detención de la escala: Dejar de unir clústers cuando el par de clústers más cercano está más lejos que una fracción de la distancia máxima por pares (se satisface la invariancia de escala, pero se viola la consistencia).
Clasificación de Algoritmos de Clustering
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 difuso): 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.
Algunos representantes
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:
-
K-medias: modelo de centroides.
-
DBSCAN: modelo de densidad discreto.
-
Mean Shift: modelo de gradientes en densidad.
-
AGNES: modelo jerárquico.
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:
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 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
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 muestreo 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.
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:
- 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\}$.
- 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\}$.
- 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\}$.
- 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 resultantes.
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.