Unifying Information-Theoretic and Pair-Counting Clustering Similarity

Resumo Técnico: Unificando a Similaridade de Informação Teórica e de Contagem de Pares

Definição do Problema
A comparação de agrupamentos (clusterings) é fundamental para avaliar modelos não supervisionados, mas os profissionais frequentemente encontram divergências significativas entre diferentes índices de similaridade. O campo está atualmente dividido em duas famílias dominantes: medidas de contagem de pares (ex: Índice de Rand, Índice de Rand Ajustado, Jaccard), que avaliam o acordo sobre pares não ordenados de elementos, e medidas de teoria da informação (ex: Informação Mútua, Variação de Informação), que agregam a dependência através da tabela de contingência completa de coocorrências de clusters. Estas famílias frequentemente produzem conclusões divergentes para o mesmo par de partições, obscurecendo a interpretação. Embora trabalhos anteriores tenham identificado diferenças axiomáticas ou equivalências geométricas locais, faltava um quadro analítico unificado que explicasse por que essas medidas divergem — especificamente em relação aos seus princípios de ponderação e espaços de amostragem.

Metodologia
O artigo desenvolve um quadro analítico que unifica estas duas famílias através de uma linha de base de independência compartilhada e de uma expansão de suas estruturas matemáticas subjacentes.

1. Expansão de Resíduos em Torno da Independência:
   Os autores definem um modelo de referência neutro onde dois agrupamentos são independentes, caracterizado por probabilidades esperadas $p_{ij}^{ind} = p_{i\cdot}p_{\cdot j}$. Eles analisam o desvio deste baseline usando resíduos $\delta_{ij} = p_{ij} - p_{i\cdot}p_{\cdot j}$.

   • Informação Mútua (MI): O artigo deriva uma expansão de série de Taylor exata da MI em torno da linha de base de independência. O termo principal é uma forma quadrática marginalmente ponderada ($\sum \delta_{ij}^2 / (p_{i\cdot}p_{\cdot j})$), que corresponde a uma estatística $\chi^2$ de Pearson. Esta ponderação valoriza excessivamente desvios em células com pequena massa esperada (interseções raras).
   • Índices de Contagem de Pares (ex: Índice de Rand): O índice de Rand é decomposto em uma linha de base marginal (acordo ao acaso) e um termo residual. O componente residual é mostrado como uma forma quadrática não ponderada ($\sum \delta_{ij}^2$) mais um termo de alinhamento linear. Diferente da MI, as medidas de contagem de pares não dividem pelo esperado, o que significa que são dominadas por grandes clusters e subvalorizam alinhamentos coerentes em clusters minoritários.

2. Extensão para Tuplas de Ordem Superior:
   Os autores estendem o quadro de contagem de pares além de pares não ordenados para $k$-tuplas. Eles introduzem uma hierarquia de probabilidades de colisão, definidas como a probabilidade de que $k$ elementos amostrados independentemente caiam no mesmo cluster (ou na mesma célula de contingência).

   • Para $k=2$, eles recuperam as quantidades padrão de contagem de pares.
   • Para $k > 2$, eles definem uma família de contrastes de entropia de Rényi $I^{(k)}$, que medem o acordo baseado na consistência de coatribuições de $k$ elementos.
   • Isso cria uma ponte onde a contagem de pares é o caso de ordem dois de uma hierarquia mais ampla conectada às entropias de Rényi, oferecendo testes cada vez mais rigorosos de coerência em nível de grupo.

3. Conexão Centrada no Elemento:
   O artigo liga esta hierarquia de contagem de tuplas à similaridade centrada no elemento (baseada em passeios aleatórios em grafos de afinidade). Eles demonstram que, para partições estritas, as probabilidades de colisão de $k$-tuplas correspondem à probabilidade de um passeio aleatório permanecer dentro de um cluster por $k$ passos, oferecendo uma interpretação geométrica da hierarquia de amostragem.

Principais Contribuições

• Ponte Analítica: O artigo fornece uma derivação rigorosa mostrando que tanto as medidas de teoria da informação quanto as de contagem de pares são funções dos mesmos resíduos da tabela de contingência, diferindo primariamente em seus esquemas de ponderação (ponderado por probabilidade vs. não ponderado) e espaços de amostragem (elementos únicos vs. pares não ordenados).
• Hierarquia de Acordo: Estabelece que a contagem de pares não é um paradigma distinto, mas o membro de ordem dois de uma hierarquia mais ampla de contagem de colisões ($k$-tuplas) conectada às entropias de Rényi.
• Interpretabilidade da Divergência: Ao decompor as medidas, o artigo explica que os desacordos entre índices (ex: RI vs. MI) não são arbitrários, mas derivam de escolhas matemáticas explícitas: se enfatizar a sobreposição ampla de grandes clusters ou alinhamentos sistemáticos e nítidos em pequenos clusters.

Resultos
Através de exemplos sintéticos controlados, o artigo demonstra as implicações práticas destas diferenças teóricas:

• Clusters Equilibrados: Quando os tamanhos dos clusters são equilibrados e o ruído é simétrico, as medidas tendem a concordar, pois as diferenças de ponderação são atenuadas.
• Clusters Desequilibrados: Sob forte desequilíbrio de classes, as medidas divergem significativamente.
  • Desacordos Pequeno-Pequeno: Quando elementos são trocados entre dois pequenos clusters minoritários, as medidas de teoria da informação (MI) caem bruscamente porque ponderam os desvios pelo inverso da massa esperada. As medidas de contagem de pares (ARI) permanecem relativamente estáveis porque são dominadas pelos grandes clusters inalterados.
  • Desacordos Grande-Pequeno: Quando elementos são trocados entre um cluster grande e um pequeno, todas as medidas caem, mas a análise de resíduos mostra que as medidas de contagem de pares são impulsionadas pelo termo quadrático não ponderado da interrupção do cluster grande.
• Sensibilidade de Ordem Superior: Os contrastes de $k$-tuplas ($I^{(k)}$) mostram que, embora as medidas de contagem de pares ($I^{(2)}$) não consigam distinguir entre sobreposições difusas e concentradas (se as contagens de pares forem idênticas), as tuplas de ordem superior ($I^{(3)}$, etc.) podem detectar se o acordo de pares é sustentado por estruturas coerentes em nível de grupo.

Significância e Alegações
O artigo afirma que esta unificação transforma o desacordo métrico de um incômodo em evidência interpretável sobre as estruturas de agrupamento que cada medida enfatiza.

• Argumenta-se que não existe uma única medida "melhor"; em vez disso, a escolha do índice deve depender da tarefa. A contagem de pares é apropriada para resumir o acordo grosseiro entre grupos grandes e homogêneos. As medidas de teoria da informação são superiores para detectar alinhamentos pequenos, mas sistemáticos, ou subtipos minoritários. Os resumos de tuplas de ordem superior oferecem um regime intermediário para testar se o acordo de pares se estende a grupos coerentes.
• O quadro recodifica normalização, correção de chance e variabilidade de amostragem como regimes ajustáveis dentro de uma estrutura teórica comum, permitindo que os profissionais selecionem índices baseados em primeiros princípios em vez de tentativa e erro empírica.
• Os autores observam modestamente que a expansão de resíduos é mais transparente próximo à linha de base de independência e que as contagens de tuplas de ordem superior podem sofrer de esparsidade em amostras finitas, sugerindo trabalhos futuros em correções de amostra finita e extensões para agrupamentos sobrepostos ou suaves (soft clusterings).