Resumen Técnico: Evaluación de la Agrupación con Verdad de Terreno

Declaración del Problema

La evaluación de los algoritmos de agrupación (clustering) presenta un desafío fundamental distinto al de la clasificación. En la clasificación, las etiquetas predichas pueden compararse directamente con las etiquetas de la verdad de terreno (ground truth). En la agrupación, sin embargo, los índices de los grupos son números arbitrarios sin una correspondencia inherente con las etiquetas de la verdad de terreno, y el número de grupos en la solución puede diferir de la verdad de terreno. Por consiguiente, las métricas estándar de precisión de clasificación son inaplicables.

Si bien la validación interna (la optimización de funciones de costo como la Suma de Errores Cuadráticos) y el rendimiento a nivel de aplicación existen, a menudo carecen de una interpretabilidad clara o no proporcionan información profunda sobre el comportamiento específico de agrupación del algoritmo. Cuando se dispone de la verdad de terreno, se requieren índices de validez externa. Sin embargo, las medidas existentes varían significamente en su sesgo, interpretabilidad y adecuación para diferentes escenarios de agrupación (por ejemplo, tamaños de grupo equilibrados frente a desequilibrados).

Metodología

El artículo revisa y categoriza los índices de validez externa en dos clases primarias: Medidas de Pares y Medidas basadas en el Emparejamiento de Conjuntos.

1. Medidas de Pares

Estas medidas evalúan la consistencia de los pares de puntos a través de dos agrupaciones.

• Índice de Rand (RI): Cuenta el porcentaje de pares consistentes (mismo grupo o grupo diferente en ambas soluciones). Se critica por verse abrumado por los acuerdos en pares en diferentes grupos, arrojando valores altos para casi cualquier agrupación razonable.
• Índice de Rand Ajustado (ARI): Normaliza el RI frente a las expectativas de una agrupación aleatoria. Aunque es más útil, sigue estando sesgado hacia los grupos más grandes cuando los tamaños son desequilibrados.
• Información Mutua Normalizada (NMI): Una medida informacional que cuantifica la información compartida entre pares de grupos. Es equivalente a varios otros índices (AVIS, NVIS, AMI), pero se señala que tiene un sesgo cuando el número de grupos es grande.

2. Medidas basadas en el Emparejamiento de Conjuntos

Estas medidas encuentran el mejor grupo coincidente en la verdad de terreno para cada grupo en la solución y calculan la similitud. La metodología involucra tres componentes de diseño:

• Estrategia de Emparejamiento:
  • Mapeo: Unidireccional (ej., Pureza, F-Measure) o bidireccional (ej., NVD, CI).
  • Pareo: Evita que múltiples grupos se mapeen al mismo objetivo. Esto puede resolverse mediante Pareo Codicioso (CH, CR) o Pareo Óptimo usando el algoritmo húngaro (ACC, PSI).
• Métrica de Similitud:
  • Intersección Cruda: Contar puntos compartidos $|A \cap G|$ (ACC, NVD, CH). Esto favorece a los grupos más grandes.
  • Similitud de Conjunto: Usar Jaccard (CSI), Braun-Banquet (PSI) o Sorensen-Dice (FM) para normalizar el tamaño del grupo.
  • Emparejamiento de Centroides: Emparejar centroides directamente (CI, CR, GCI).
• Normalización:
  • La mayoría normaliza por el número total de puntos ($N$), asegurando que todos los puntos contribuyan por igual.
  • Algunos (como CI) calculan puntuaciones a nivel de grupo (0 o 1 por grupo), permitiendo un conteo de errores basado en enteros.

3. El Índice de Centroide (CI)

El artículo otorga especial énfasis al Índice de Centroide (CI). A diferencia de las medidas a nivel de punto, el CI es una medida a nivel de grupo. Determina el número de centroides de la verdad de terreno que no tienen un centroide correspondiente en el resultado de la agrupación (centroides huérfanos).

• Mecanismo: Empareja los grupos basándose en los centroides más cercanos (o máxima superposición en versiones generalizadas) y cuenta los desajustes.
• Salida: Un valor entero en el rango $[0, k]$, donde $k$ es el número de grupos. Un valor de 0 indica que todos los grupos están localizados correctamente.

Contribuciones Clave y Resultados

El artículo proporciona una revisión exhaustiva de los índices externos, destacando fortalezas y debilidades específicas:

• Interpretabilidad: Los autores argumentan que las métricas estándar como NMI y ARI producen valores en $[0, 1]$ que son difíciles de interpretar intuitivamente (ej., ¿implica un 0.90 una agrupación "buena"?). En contraste, el CI proporciona un resultado explicable: el número exacto de grupos incorrectamente resueltos.
• Análisis de Sesgo:
  • Se demuestra que la NMI arroja puntuaciones engañosamente altas para agrupaciones incorrectas cuando el número de grupos es grande (ej., $k=100$), como se demuestra en el conjunto de datos Birch2 donde un resultado incorrecto recibió un NMI de 0.96.
  • El ARI está sesgado hacia el acuerdo de los grupos más grandes en escenarios desequilibrados.
  • El Índice de Rand se considera inadecuado debido a su sesgo inherente independientemente del tamaño o la cantidad de grupos.
• Nivel de Punto vs. Nivel de Grupo: El documento distingue entre medidas que capturan desviaciones a nivel de punto (ACC, PSI) y aquellas que capturan errores estructurales a nivel de grupo (CI). El CI puede perder detalles finos de desviación de puntos (ej., ligeros desplazamientos de centroides), pero sobresale en la identificación de fallos estructurales graves (ej., grupos faltantes o fusionados).
• Implementación: El artículo hace referencia a implementaciones de software disponibles, incluyendo CBEVI para C y una librería de Python para ACC (que soporta tanto variantes de pareo como de emparejamiento).

Significancia y Recomendaciones

El artículo concluye con recomendaciones específicas para los profesionales que evalúan la agrupación con verdad de terreno:

1. Recomendación Primaria (Nivel de Grupo): Utilizar el Índice de Centroide (CI). Se recomienda por su naturaleza intuitiva y su salida explicable (el conteo de errores). Es particularmente efectivo para identificar si se encontró la estructura de agrupación correcta.
2. Recomendación Secundaria (Nivel de Punto): Si se requieren diferencias finas a nivel de punto, se recomienda la Precisión de Agrupación (ACC). Está bien documentada, analizada conductualmente y cuenta con soporte de software accesible.
3. Alternativa para la Normalización: Si se requiere una puntuación normalizada que no favorezca a los grupos más grandes, se sugiere el Índice de Par de Conjuntos (PSI).
4. Advertencias:
   • NMI y ARI pueden usarse, pero requieren conciencia de sus sesgos específicos (NMI con muchos grupos, ARI con tamaños desequilibrados).
   • El Índice de Rand no se recomienda explícitamente.

La importancia de este trabajo radica en el cambio de enfoque desde puntuaciones abstractas y difíciles de interpretar hacia métricas que ofrecen información clara y accionable sobre el rendimiento de la agrupación, abogando específicamente por el Índice de Centroide como un estándar robusto y explicable para la evaluación a nivel de grupo.