Unifying Information-Theoretic and Pair-Counting Clustering Similarity

Résumé Technique : Unification de l'approche informationnelle et du comptage de paires pour la similitude de partitionnement

Énoncé du problème
La comparaison des partitionnements est fondamentale pour évaluer les modèles non supervisés, pourtant les praticiens se heurtent fréquemment à des désaccords significatifs entre différents indices de similitude. Le domaine est actuellement divisé en deux familles dominantes : les mesures de comptage de paires (ex. : Indice de Rand, Indice de Rand Ajusté, Jaccard), qui évaluent l'accord sur des paires d'éléments non ordonnées, et les mesures d'ordre informationnel (ex. : Information Mutuelle, Variation de l'Information), qui agrègent la dépendance à travers la table de contingence complète des cooccurrences de clusters. Ces familles produisent souvent des conclusions divergentes pour une même paire de partitions, obscurcissant ainsi l'interprétation. Bien que des travaux antérieurs aient identifié des différences axiomatiques ou des équivalences géométriques locales, un cadre analytique unifié expliquant pourquoi ces mesures divergent — spécifiquement concernant leurs principes de pondération et leurs espaces d'échantillonnage — faisait défaut.

Méthodologie
L'article développe un cadre analytique qui unifie ces deux familles par le biais d'une ligne de base d'indépendance partagée et d'une extension de leurs structures mathématiques sous-jacentes.

1. Expansion résiduelle autour de l'indépendance :
   Les auteurs définissent un modèle de référence neutre où deux partitionnements sont indépendants, caractérisé par des probabilités attendues $p_{ij}^{ind} = p_{i\cdot}p_{\cdot j}$. Ils analysent l'écart par rapport à cette ligne de base en utilisant des résidus $\delta_{ij} = p_{ij} - p_{i\cdot}p_{\cdot j}$.

   • Information Mutuelle (IM) : L'article dérive une expansion exacte en série de Taylor de l'IM autour de la ligne de base d'indépendance. Le terme de premier ordre est une forme quadratique marginalement pondérée ($\sum \delta_{ij}^2 / (p_{i\cdot}p_{\cdot j})$), ce qui correspond à une statistique du $\chi^2$ de Pearson. Cette pondération accentue les écarts dans les cellules ayant une faible masse attendue (intersections rares).
   • Indices de comptage de paires (ex. : Indice de Rand) : L'indice de Rand est décomposé en une ligne de base marginale (accord dû au hasard) et un terme résiduel. La composante résiduelle est démontrée comme étant une forme quadratique non pondérée ($\sum \delta_{ij}^2$) plus un terme d'alignement linéaire. Contrairement à l'IM, les mesures de comptage de paires ne divisent pas par la masse attendue, ce qui signifie qu'elles sont dominées par les grands clusters et sous-pondèrent les alignements cohérents dans les clusters minoritaires.

2. Extension aux $k$-uplets :
   Les auteurs étendent le cadre de comptage de paires au-delà des paires non ordonnées vers les $k$-uplets. Ils introduisent une hiérarchie de probabilités de collision, définies comme la probabilité que $k$ éléments échantillonnés indépendamment tombent dans le même cluster (ou la même cellule de contingence).

   • Pour $k=2$, ils récupèrent les quantités standards de comptage de paires.
   • Pour $k > 2$, ils définissent une famille de contrastes d'entropie de Rényi $I^{(k)}$, qui mesurent l'accord basé sur la cohérence des co-assignations de $k$ éléments.
   • Cela crée un pont où le comptage de paires est le cas d'ordre deux d'une hiérarchie plus large connectée aux entropies de Rényi, offrant des tests de plus en plus rigoureux de la cohérence au niveau du groupe.

3. Connexion centrée sur les éléments :
   L'article lie cette hiérarchie de comptage de tuples à la similitude centrée sur les éléments (basée sur des marches aléatoires sur des graphes d'affinité). Il démontre que pour les partitions strictes, les probabilités de collision de $k$-uplets correspondent à la probabilité qu'une marche aléatoire reste à l'intérieur d'un cluster pendant $k$ étapes, offrant une interprétation géométrique de la hiérarchie d'échantillonnage.

Principales contributions

• Pont Analytique : L'article fournit une dérivation rigoureuse montrant que les mesures d'ordre informationnel et de comptage de paires sont toutes deux des fonctions des mêmes résidus de la table de contingence, différant principalement par leurs schémas de pondération (pondéré par la probabilité vs non pondéré) et leurs espaces d'échantillonnage (éléments uniques vs paires non ordonnées).
• Hiérarchie d'Accord : Il établit que le comptage de paires n'est pas un paradigme distinct, mais le membre d'ordre deux d'une hiérarchie plus large de comptage de collisions ($k$-uplets) connectée aux entropies de Rényi.
• Interprétabilité de la Divergence : En décomposant les mesures, l'article explique que les désaccords entre indices (ex. : RI vs IM) ne sont pas arbitraires mais découlent de choix mathématiques explicites : privilégier le chevauchement large de grands clusters ou les alignements systématiques et nets dans les petits clusters.

Résultats
À travers des exemples synthétiques contrôlés, l'article démontre les implications pratiques de ces différences théoriques :

• Clusters Équilibrés : Lorsque les tailles de clusters sont équilibrées et que le bruit est symétrique, les mesures ont tendance à s'accorder, car les différences de pondération sont atténuées.
• Clusters Déséquilibrés : Sous un fort déséquilibre de classes, les mesures divergent considérablement.
  • Désaccords Petit-Petit : Lorsque des éléments sont échangés entre deux petits clusters minoritaires, les mesures d'ordre informationnel (IM) chutent brutalement car elles pondèrent les écarts par l'inverse de la masse attendue. Les mesures de comptage de paires (ARI) restent relativement stables car elles sont dominées par les grands clusters inchangés.
  • Désaccords Grand-Petit : Lorsque des éléments sont échangés entre un grand cluster et un petit, toutes les mesures chutent, mais l'analyse résiduelle montre que les mesures de comptage de paires sont entraînées par le terme quadratique non pondéré de la perturbation du grand cluster.
• Sensibilité d'Ordre Supérieur : Les contrastes de $k$-uplets ($I^{(k)}$) montrent que si les mesures de comptage de paires ($I^{(2)}$) ne peuvent pas distinguer entre des chevauchements diffus et concentrés (si les comptes de paires sont identiques), les tuples d'ordre supérieur ($I^{(3)}$, etc.) peuvent détecter si l'accord par paires est soutenu par des structures cohérentes au niveau du groupe.

Signification et Revendications
L'article affirme que cette unification transforme le désaccord métrique d'un désagrément en une preuve interprétable concernant les structures de clustering que chaque mesure met en évidence.

• Il soutient qu'il n'existe pas de mesure unique "optimale" ; plutôt, le choix de l'indice doit dépendre de la tâche. Le comptage de paires est approprié pour résumer l'accord grossier parmi des groupes larges et homogènes. Les mesures d'ordre informationnel sont supérieures pour détecter des alignements systématiques mais de petite taille ou des sous-types minoritaires. Les résumés de tuples d'ordre supérieur offrent un régime intermédiaire pour tester si l'accord par paires s'étend à des groupes cohérents.
• Le cadre reformule la normalisation, la correction du hasard et la variabilité de l'échantillonnage comme des régimes ajustables au sein d'une structure théorique commune, permettant aux praticiens de choisir des indices basés sur des principes fondamentaux plutôt que par essais et erreurs empiriques.
• Les auteurs notent modestement que l'expansion résiduelle est plus transparente à proximité de la ligne de base d'indépendance et que les comptages de tuples d'ordre supérieur peuvent souffrir de la rareté dans les échantillons finis, suggérant des travaux futurs sur les corrections d'échantillons finis et les extensions aux partitionnements chevauchants ou "soft".