Agrupamiento

Cuando el aprendizaje es no supervisado, ya no hay etiquetas y por lo tanto los algoritmos (como los de agrupamiento) tienen que «descubrir» por sí mismos la estructura «latente» en los propios datos… se podría decir que son algoritmos de descubrimiento, lo cual es muy útil para segmentar clientes en el mundo del marketing o desarrollar sistema de recomendación en base a los productos adquiridos por el usuario como los que encontramos en tiendas como Amazon o Steam.

Agrupamiento

El agrupamiento (clustering) es la piedra angular de las aplicaciones de aprendizaje automático no supervisado que puede usarse tanto para segmentar jugadores (player profiling), como para detectar estilos de juego (player styles) o estructurar niveles o comportamientos de los jugadores.

Aquí ya estamos hablando de una forma de hacer modelado, dentro del aprendizaje automático que se usa muchísimo en minería de datos. Es muy muy potente esta capacidad de «encontrar patrones» sin que nadie haya puesto etiquetas en la base de datos.

El objetivo del agrupamiento es organizar un conjunto de objetos de forma que los elementos del mismo grupo (cluster) sean lo más similares posible entre sí (alta cohesión interna) y lo más diferentes posible de los de otros grupos (alta separación externa).

El agrupamiento no existe sin una métrica para medir qué tan «cercanos» están dos puntos en el espacio de características (feature space). A esto se le conoce como una medida de similitud.

Algunas métricas de distancia comunes:

• Distancia Euclídea: La recta más corta; estándar para datos continuos sin demasiadas dimensiones.
• Distancia de Manhattan: Suma de diferencias absolutas; muy útil cuando las características representan pasos en rejillas o movimientos restringidos.
• Similitud del Coseno: Mide el ángulo entre dos vectores independientemente de su magnitud.

Es importante tener presente la sensibilidad al escalado: si no se han normalizado los datos en la fase de preprocesado, una variable con valores grandes eclipsará a variables con rangos pequeños.

Agrupamiento basado en particiones

El algoritmo llamado de k-Medias (k-Means) para agrupar datos basándose en particiones funciona de la siguiente manera:

1. Seleccionar k centroides iniciales aleatorios.
2. Asignar cada punto al centroide más cercano.
3. Recalcular la posición de cada centroide como la media de los puntos asignados.
4. Repetir hasta convergencia (cuando los centroides dejan de moverse).

La ventaja de este algoritmo es que es extremadamente rápido y escalable, pero como desventaja hay que decir que exige definir el número de grupos k a priori y asume que los grupos son esféricos y de tamaño similar.

Como variantes existen el algoritmo de las k-Medianas (k-Medians), más robusto a outliers, y el de las k-Medias++ (k-Means++) que incluye un método inteligente de inicialización para evitar mínimos locales deficientes.

Agrupamiento jerárquico

El agrupamiento jerárquico (hierarchical clustering) se puede realizar mediante la construcción de árboles de agrupación (llamados «dendrogramas»), lo que permite la visualización en forma de árbol de cómo se van fusionando o dividiendo los grupos a distintas escalas de distancia. Distinguimos dos estrategias:

• Aglomerativa (bottom-up), donde cada punto empieza como su propio grupo y se van fusionando los más cercanos sucesivamente.
• Divisiva (top-down), donde todos los puntos empiezan en un único grupo grande y luego lo vamos particionando.

Para saber cómo medir la distancia entre dos grupos completos se consideran distintos criterios de enlace (linkage criteria):

• Single Linkage, que consiste en mirar la distancia mínima entre puntos.
• Complete Linkage, que consiste en mirar la distancia máxima.
• Average Linkage, que consiste en mirar la distancia media.
• Ward’s Method, que minimiza la varianza total dentro de los grupos.

La ventaja fundamental de este modo de agrupar los datos es que no requiere predefinir el número de grupos k, ya que se puede cortar el «dendrograma» al cualquier altura según el nivel de detalle deseado.

Agrupamiento basado en densidad

A diferencia del algoritmo que veíamos antes de k-Medias, el algoritmo de Agrupamiento Espacial basado en Densidad con Ruido (Density-Based Spatial Clustering of Applications with Noise, ó DBSCAN) define los grupos como regiones de alta densidad separadas por regiones de baja densidad (espacio vacío o casi vacío).

Los conceptos fundamentes aquí son el radio de vecindad (que se suele representar con la letra griega epsilon) y el número mínimo de puntos en el radio epsilon para formar un grupo denso (al que se le suele llamar MinPts).

Las ventajas más importantes de este algoritmo son que es capaz de descubrir grupos con formas complejas y arbitrarias (anillos, formas en C, serpenteantes…) que k-Medias jamás detectaría, algo que es interesante para esbozar mapas de calor con formas peculiares en el escenario de un videojuego. Y como segunda ventaja tenemos que es capaz de identificar y aislar automáticamente los valores atípicos o outliers como «ruido» en lugar de ubicarlos forzosamente dentro de un grupo.

Evaluación

El dilema del aprendizaje no supervisado cuando queremos tener una validación intrínseca de un algoritmo de agrupamiento es el siguiente: al no haber etiquetas reales, no podemos calcular métricas tradicionales como la precisión (que usábamos en el aprendizaje supervisado); debemos medir de alguna manera la calidad estructural de las agrupaciones.

Estas son algunas de las métricas internas clave:

• Coeficiente de Silueta (Silhouette Coefficient): Mide cómo de similar es un objeto a su propio grupo en comparación con otros grupos. Varía entre -1 y +1. Valores cercanos a +1 indican un agrupamiento claro e idóneo.
• Índice Davies-Bouldin: Mide la similitud media entre cada grupo y su grupo más parecido. Valores más bajos indican una mejor separación entre grupos.

¿Cómo se determina la k óptima? Para ello puede utilizarse el método del codo (elbow method) que realiza unas gráficas de la inercia (es decir, la suma de las distancias cuadráticas internas) en función de k, hasta dar con el punto de inflexión… y ese indicaría la k óptima.

Más información

Para complementar es recomendable consultar otros documentos.

• …