Unifying Information-Theoretic and Pair-Counting Clustering Similarity

Resumen Técnico: Unificación de la Similitud entre el Enfoque de la Teoría de la Información y el Conteo de Pares

Planteamiento del Problema
La comparación de agrupamientos (clusterings) es fundamental para evaluar modelos no supervisados, sin embargo, los profesionales encuentran con frecuencia desacuerdos significativos entre diferentes índices de similitud. El campo está dividido actualmente en dos familias dominantes: las medidas de conteo de pares (por ejemplo, el Índice de Rand, el Índice de Rand Ajustado, Jaccard), que evalúan el acuerdo sobre pares no ordenados de elementos, y las medidas de la teoría de la información (por ejemplo, la Información Mutua, la Variación de la Información), que agregan la dependencia a través de la tabla de contingencia completa de las coocurrencias de los grupos. Estas familias suelen ofrecer conclusiones divergentes para un mismo par de particiones, lo que oscurece la interpretación. Aunque trabajos previos han identificado diferencias axiomáticas o equivalencias geométricas locales, faltaba un marco analítico unificado que explicara por qué estas medidas divergen, específicamente en lo que respecta a sus principios de ponderación y espacios de muestreo.

Metodología
El artículo desarrolla un marco analítico que unifica estas dos familias a través de una línea de base de independencia compartida y una expansión de sus estructuras matemáticas subyacentes.

1. Expansión de Residuos alrededor de la Independencia:
   Los autores definen un modelo de referencia neutral donde dos agrupamientos son independientes, caracterizado por probabilidades esperadas $p_{ij}^{ind} = p_{i\cdot}p_{\cdot j}$. Analizan la desviación de esta línea de base utilizando residuos $\delta_{ij} = p_{ij} - p_{i\cdot}p_{\cdot j}$.

   • Información Mutua (MI): El artículo deriva una expansión de la serie de Taylor exacta de la MI alrededor de la línea de base de independencia. El término principal es una forma cuadrática marginalmente ponderada ($\sum \delta_{ij}^2 / (p_{i\cdot}p_{\cdot j})$), que corresponde a un estadístico $\chi^2$ de Pearson. Esta ponderación aumenta el peso de las desviaciones en celdas con masa esperada pequeña (intersecciones raras).
   • Índices de Conteo de Pares (ej. Índice de Rand): El índice de Rand se descompone en una línea de base marginal (acuerdo por azar) y un término residual. Se demuestra que el componente residual es una forma cuadrática no ponderada ($\sum \delta_{ij}^2$) más un término de alineación lineal. A diferencia de la MI, las medidas de conteo de pares no dividen por la masa esperada, lo que significa que están dominadas por los grupos grandes y subestiman las alineaciones coherentes en los grupos minoritarios.

2. Extensión a Tuplas de Orden Superior:
   Los autores extienden el marco de conteo de pares más allá de los pares no ordenados hacia $k$-tuplas. Introducen una jerarquía de probabilidades de colisión, definidas como la probabilidad de que $k$ elementos muestreados independientemente caigan en el mismo grupo (o la misma celda de contingencia).

   • Para $k=2$, estas recuperan las cantidades estándar de conteo de pares.
   • Para $k > 2$, definen una familia de contrastes de entropía de Rényi $I^{(k)}$, que miden el acuerdo basado en la consistencia de las coasignaciones de $k$ elementos.
   • Esto crea un puente donde el conteo de pares es el caso de orden dos de una jerarquía más amplia conectada a las entropías de Rényi, proporcionando pruebas cada vez más estrictas de la coherencia a nivel de grupo.

3. Conexión Centrada en el Elemento:
   El artículo vincula esta jerarquía de conteo de tuplas con la similitud centrada en el elemento (basada en paseos aleatorios en grafos de afinidad). Demuestra que, para particiones estrictas, las probabilidades de colisión de $k$-tuplas corresponden a la probabilidad de que un paseo aleatorio permanezca dentro de un grupo durante $k$ pasos, ofreciendo una interpretación geométrica de la jerarquía de muestreo.

Contribuciones Clave

• Puente Analítico: El artículo proporciona una derivación rigurosa que muestra que tanto las medidas de la teoría de la información como las de conteo de pares son funciones de los mismos residuos de la tabla de contingencia, diferenciándose principalmente en sus esquemas de ponderación (ponderado por probabilidad vs. no ponderado) y sus espacios de muestreo (elementos individuales vs. pares no ordenados).
• Jerarquía de Acuerdo: Establece que el conteo de pares no es un paradigma distinto, sino el miembro de orden dos de una más amplia jerarquía de conteo de colisiones ($k$-tuplas) conectada a las entropías de Rényi.
• Interpretabilidad de la Divergencia: Al descomponer las medidas, el artículo explica que los desacuerdos entre índices (ej. RI vs. MI) no son arbitrarios, sino que surgen de elecciones matemáticas explícitas: si se enfatiza el traslape amplio de grupos grandes o las alineaciones sistemáticas y nítidas en grupos pequeños.

Resultados
A través de ejemplos sintéticos controlados, el artículo demuestra las implicaciones prácticas de estas diferencias teóricas:

• Grupos Balanceados: Cuando los tamaños de los grupos están balanceados y el ruido es simétrico, las medidas tienden a coincidir, ya que las diferencias de ponderación se atenúan.
• Grupos Desbalanceados: Bajo un fuerte desbalance de clases, las medidas divergen significamente.
  • Desacuerdos Pequeño-Pequeño: Cuando se intercambian elementos entre dos grupos minoritarios pequeños, las medidas de la teoría de la información (MI) caen abruptamente porque ponderan las desviaciones por la inversa de la masa esperada. Las medidas de conteo de pares (ARI) permanecen relativamente estables porque están dominadas por los grupos grandes que no han cambiado.
  • Desacuerdos Grande-Pequeño: Cuando se intercambian elementos entre un grupo grande y uno pequeño, todas las medidas caen, pero el análisis de residuos muestra que las medidas de conteo de pares son impulsadas por el término cuadrático no ponderado de la disrupción del grupo grande.
• Sensibilidad de Orden Superior: Los contrastes de $k$-tuplas ($I^{(k)}$) muestran que, mientras que las medidas de conteo de pares ($I^{(2)}$) no pueden distinguir entre traslapes difusos y concentrados (si los conteos de pares son idénticos), las tuplas de orden superior ($I^{(3)}$, etc.) sí pueden detectar si el acuerdo de pares está respaldado por estructuras coherentes a nivel de grupo.

Significancia y Reivindicaciones
El artículo sostiene que esta unificación transforma el desacuerdo métrico de una molestia en evidencia interpretable sobre las estructuras de agrupamiento que cada medida enfatiza.

• Argumenta que no existe una única "mejor" medida; más bien, la elección del índice debe depender de la tarea. El conteo de pares es apropiado para resumir el acuerdo grueso entre grupos grandes y homogéneos. Las medidas de la teoría de la información son superiores para detectar alineaciones pequeñas pero sistemáticas o subtipos minoritarios. Los resúmenes de tuplas de orden superior ofrecen un régimen intermedio para probar si el acuerdo de pares se extiende a grupos coherentes.
• El marco redefine la normalización, la corrección por azar y la variabilidad del muestreo como regímenes ajustables dentro de una estructura teórica común, permitiendo a los profesionales seleccionar índices basados en primeros principios en lugar de ensayo y error empírico.
• Los autores señalan modestamente que la expansión de residuos es más transparente cerca de la línea de base de independencia y que los conteos de tuplas de orden superior pueden sufrir de escasez en muestras finitas, sugiriendo trabajos futuros en correcciones de muestra finita y extensiones a agrupamientos superpuestos o difusos (soft clustering).