Hierarchical Aggregation Clustering Algorithms Derived from the Bi-partial Objective Function

1. Problématique

Le papier aborde un problème fondamental en analyse de données : la classification hiérarchique (ou agrégation). Bien que les algorithmes hiérarchiques classiques (comme le lien simple, le lien complet, la méthode de Ward) soient intuitifs et largement utilisés, ils souffrent d'un déficit théorique majeur :

• Ils sont définis de manière procédurale (étape par étape) plutôt que par l'optimisation d'une fonction objectif globale.
• Il n'existe pas de critère interne cohérent pour déterminer le moment optimal d'arrêter l'algorithme (le « couper » dans le dendrogramme) sans recourir à des critères externes ou statistiques ad hoc.
• La relation entre les règles de fusion locales (mise à jour des distances) et l'optimisation globale de la partition n'est pas explicitement établie pour la classe générale de ces algorithmes.

L'auteur cherche à combler ce fossé en démontrant comment une classe d'algorithmes d'agrégation hiérarchique peut être dérivée directement d'une fonction objectif générale, appelée fonction objectif bi-partielle.

2. Méthodologie

La méthodologie repose sur la formulation d'un problème d'optimisation sous la forme d'une fonction objectif bi-partielle, notée $Q(P, r)$, qui dépend d'une partition $P$ et d'un paramètre de pondération $r \in [0, 1]$.

A. La Fonction Objectif Bi-partielle

La fonction est conçue pour équilibrer deux aspects contradictoires du problème de clustering :

1. La cohésion intra-cluster (proximité/similarité à l'intérieur des groupes).
2. La séparation inter-cluster (distance entre les groupes).

La forme générale proposée (pour une maximisation) est :
$$Q(P, r) = r \cdot Q_S(P) + (1-r) \cdot Q_D(P)$$
Où :

• $Q_S(P)$ mesure la similarité globale à l'intérieur des clusters.
• $Q_D(P)$ mesure la distance globale entre les clusters.
• $r$ est un paramètre qui fait varier l'importance relative de la similarité par rapport à la distance.

B. Dérivation de l'Algorithme Hiérarchique

L'auteur propose une procédure itérative pour résoudre ce problème d'optimisation :

1. Point de départ ($r=0$) : La solution optimale est la partition où chaque objet forme son propre cluster (car $Q_D$ domine et les distances inter-objets sont minimisées quand les clusters sont individuels).
2. Augmentation de $r$ : En augmentant progressivement $r$, on cherche le seuil critique où la fusion de deux clusters devient bénéfique pour la fonction objectif globale.
3. Règle de fusion : Pour chaque étape $t$, on calcule la valeur critique du paramètre $r_t$ pour laquelle la fusion de deux clusters $A_{q1}$ et $A_{q2}$ améliore la fonction objectif. La formule dérivée est :
   $$r_t = \frac{\Delta Q_D}{\Delta Q_D + \Delta Q_S}$$
   Où $\Delta Q_D$ est la réduction de la distance inter-cluster et $\Delta Q_S$ est l'augmentation de la similarité intra-cluster résultant de la fusion.
4. Stratégie Gloutonne (Greedy) : L'algorithme sélectionne à chaque étape la paire de clusters qui minimise $r_t$ (c'est-à-dire celle qui offre le meilleur compromis immédiat). Cela génère une séquence de fusions identique à celle des algorithmes hiérarchiques classiques.

C. Exemples Concrets

L'article illustre cette approche avec plusieurs cas :

• Lien Moyen (Average Linkage) : Dérivé d'une fonction où les distances et similarités sont des sommes totales.
• Problème de localisation d'installations : Modélisé avec un coût fixe par cluster et des coûts de distance.
• Cas du K-Means : L'auteur reformule le K-Means classique (qui minimise uniquement la variance intra-cluster) en y ajoutant une composante de similarité inter-cluster. Cela permet de déterminer le nombre optimal de clusters ($k$) sans critère externe (comme le critère du coude ou BIC), en observant les minima locaux de la fonction bi-partielle.

3. Contributions Clés

1. Lien Théorique Explicite : C'est la première présentation explicite et générale reliant les algorithmes d'agrégation hiérarchique (basés sur la distance minimale) à une fonction d'optimisation globale. Les algorithmes ne sont plus de simples heuristiques, mais des approximations d'un problème d'optimisation bien défini.
2. Critère d'Arrêt Interne : La méthode fournit un critère naturel pour arrêter l'agrégation. L'algorithme doit s'arrêter lorsque le paramètre critique $r_t$ dépasse une certaine valeur (souvent $r = 0.5$, correspondant à l'équilibre entre similarité et distance), éliminant le besoin de critères externes arbitraires.
3. Généralité et Flexibilité : Le cadre bi-partiel est suffisamment flexible pour englober diverses définitions de distances et de similarités, permettant de dériver de nouveaux algorithmes adaptés à des problèmes spécifiques (ex: K-Means, localisation d'installations).
4. Justification des Algorithmes Existants : Elle offre une justification profonde aux algorithmes classiques (comme le lien moyen ou le K-Means) en montrant qu'ils correspondent à la sub-optimisation de fonctions objectif spécifiques.

4. Résultats et Illustrations

• Validation par l'exemple : L'auteur démontre mathématiquement que la règle de fusion dérivée pour le cas du lien moyen correspond exactement à la formule de Lance-Williams utilisée dans les algorithmes classiques.
• Application au K-Means : Une expérience sur un jeu de données académique montre que la fonction objectif bi-partielle modifiée pour le K-Means permet d'identifier clairement le nombre optimal de clusters (ici $k=4$) en observant les minima de la fonction globale, là où le K-Means standard nécessiterait un critère externe.
• Structure Hiérarchique : La séquence des valeurs $r_t$ générée par l'algorithme sert d'indice hiérarchique plus pertinent que la simple distance de fusion, car elle est directement liée à la qualité de la partition selon la fonction objectif.

5. Signification et Implications

• Théorique : Ce travail transforme la perception des algorithmes hiérarchiques, passant d'une approche purement algorithmique à une approche d'optimisation. Cela répond à la critique de Dasgupta (2016) soulignant le manque de fonctions objectif claires pour ces méthodes.
• Pratique :
  • Évaluation de la qualité : Les partitions générées peuvent être évaluées directement par la valeur de la fonction objectif, offrant une mesure de qualité intrinsèque.
  • Hybridation : Reconnaissant la lourdeur computationnelle des méthodes hiérarchiques sur les grands jeux de données, l'auteur suggère des approches hybrides (ex: K-Means initial suivi d'une agrégation hiérarchique guidée par la fonction bi-partielle).
  • Détermination du nombre de clusters : La méthode offre une voie prometteuse pour déterminer le nombre de clusters optimal de manière autonome, sans dépendre de critères statistiques externes souvent mal adaptés à la logique de l'algorithme utilisé.

En conclusion, l'article propose un cadre unificateur puissant qui légitime les algorithmes d'agrégation hiérarchique en les ancrant dans une théorie d'optimisation rigoureuse, tout en fournissant des outils pratiques pour améliorer leur application et leur interprétation.