Qu’est-ce que le clustering hiérarchique ?

Le partitionnement (ou clustering) est une technique de machine learning non supervisé utilisée dans l’analyse des données afin de détecter et de regrouper des objets similaires. L’analyse hiérarchique des clusters (HCA), ou partitionnement hiérarchique, regroupe les objets dans une hiérarchie de clusters sans y imposer un ordre linéaire. De nombreuses disciplines, telles que la biologie, l’analyse d’images et les sciences sociales, utilisent des méthodes de partitionnement hiérarchique en vue d’explorer et de reconnaître des schémas dans les jeux de données. Les cas d’utilisation incluent la catégorisation des populations dans la recherche clinique, la segmentation des clients et la détection des communautés de nœuds dans les modèles de réseau.

Il existe deux types de partitionnement hiérarchique :

- L’approche agglomérative ou ascendante¹ qui fusionne plusieurs fois les clusters jusqu’à ce qu’un seul grand cluster émerge.

- L’approche de division ou descendante² qui commence avec un seul cluster contenant toutes les données, puis qui divise les clusters de manière successive jusqu’à ce que tous les clusters soient des singletons.

L’analyse par partitionnement hiérarchique implique des coûts de calcul élevés. Bien que l’utilisation d’un tas puisse réduire le temps de calcul, les besoins en mémoire sont plus importants. Les deux types de partitionnement (par division et agglomération) sont « gourmands », ce qui signifie que l’algorithme décide quels clusters fusionner ou fractionner en faisant le choix optimal au niveau local à chaque étape du processus. Il est également possible d’appliquer un critère d’arrêt, où l’algorithme arrête l’agglomération ou la division des clusters lorsqu’il atteint un nombre prédéterminé de clusters.

Un diagramme arborescent appelé dendrogramme³ est souvent utilisé pour visualiser la hiérarchie des clusters. Il affiche l’ordre dans lequel les clusters ont été fusionnés ou divisés et montre la similarité ou la distance entre les points de données. Les dendrogrammes peuvent également être considérés comme une liste imbriquée de listes⁴ comportant des attributs.

Les algorithmes de partitionnement hiérarchique utilisent le concept de matrice de dissimilarité pour décider quels clusters fusionner ou diviser. La dissimilarité est la distance entre deux points de données telle que mesurée par une méthode de liaison choisie. Les valeurs d’une matrice de dissimilarité expriment :

- La distance⁵, par exemple la distance euclidienne, entre des points isolés d’un jeu

- Un critère de partitionnement par liaison, qui spécifie la dissimilarité en fonction des distances des paires de points dans les jeux

Découvrons les méthodes de liaison de distance euclidienne les plus courantes. Parmi les autres indicateurs de distance qui peuvent être utilisées, citons les distances de Minkowski, Hamming, Mahalanobis, Hausdorf et Manhattan. Notez que chaque méthode de liaison génère différents clusters à partir du même jeu de données. Le choix de la méthode de partitionnement par liaison appropriée dépend de facteurs tels que le type de données partitionnée, la densité de données, la forme des clusters et la présence de valeurs aberrantes ou de bruit dans le jeu de données.

La méthode de liaison unique analyse les distances par paires entre les éléments de deux clusters, puis utilise la distance minimale entre les clusters. Cette méthode est bien adaptée aux formes de cluster non elliptiques, mais elle sera affectée par le bruit et les données aberrantes. Elle présente une limitation connue sous le nom d’effet de chaîne⁶. Quelques points créant un pont entre une paire de clusters peuvent faire fusionner les deux clusters en un seul. Les critères de liaison minimale peuvent être représentés comme suit :

 mina∈A,b∈Bd(a,b)

où A et B sont deux jeux d’observations et d est une fonction de distance.

Les distances entre les clusters peuvent également être calculées en fonction des points les plus éloignés les uns des autres. La méthode maximale est moins sensible au bruit et aux données aberrantes que la méthode minimale, mais son utilisation peut fausser les résultats en présence de clusters globulaires ou de grande taille. La liaison maximale produit souvent plus de clusters sphériques que la liaison minimale. La liaison maximale peut être représentée par la formule suivante :

 maxa∈A,b∈Bd(a,b)

où A et B sont deux jeux d’observations et d est une distance.

Ces méthodes, introduites par Sokal et Michelen⁷, définissent la distance entre les clusters comme la distance moyenne entre les paires sur toutes les paires de points des clusters. L’algorithme peut être soit la méthode des groupes de paires non pondérés avec moyenne arithmétique (UPGMA), soit la méthode des groupes de paires pondérés avec moyenne arithmétique (WPGMA). Le terme « non pondéré » signifie que toutes les distances contribuent de manière égale à chaque moyenne.

UPGMA est représenté par la formule suivante :

 1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)

où *A* et *B* sont deux jeux d’observations et *d* est la distance.

WPGMA est représenté par la formule suivante :

 d(i∪j,k)=d(i,k)+d(j,k)2

où i et j sont les clusters les plus proches combinés à chaque étape pour former un nouveau cluster composé de l’union de i et j. Nous pouvons ensuite calculer la distance par rapport à un autre cluster k, qui est la moyenne arithmétique des distances moyennes entre les points de données en k et i et k et j.

Ici, nous utilisons la distance entre les centres de cluster, aussi appelés centroïdes. La distance entre les centroïdes est calculée à l’aide d’une fonction de distance :

∥μA-μB∥2

où μ_A est le centroïde de A et μ_B est le centroïde de B.

Joe H. Ward a introduit la méthode de l’augmentation minimale de la somme des carrés (MISSQ)⁸ dans les années 1960. Chaque point de données commence dans son propre cluster. Cette approche signifie que la somme des carrés entre les points de données est initialement égale à zéro, puis augmente au fur et à mesure que l’on fusionne les clusters. La méthode de Ward minimise la somme des carrés des distances entre les points et les centres des clusters au fur et à mesure de leur fusion. La méthode de Ward est un bon choix pour les variables quantitatives⁹, et elle est moins affectée par le bruit ou les données aberrantes. Elle peut être représentée comme suit :

 ∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2

où la moyenne de A et la moyenne de B sont les centroïdes de A et de B respectivement, et x est un point de données qui appartient à l’union de A et de B

La méthode de variance minimale de Ward peut être affinée à l’aide d’un algorithme de Lance-Williams. Ces algorithmes utilisent une formule récursive pour mettre à jour les distances des clusters et trouver la paire de clusters la plus proche à fusionner.

Dans le partitionnement hiérarchique agglomératif, également connu sous le nom d’imbrication agglomérative (AGNES), chaque point de données commence en tant que cluster. L’algorithme utilise un critère de partitionnement de liaison sélectionné basé sur une matrice de dissimilarité pour décider de la paire de clusters à regrouper. L’algorithme monte dans la hiérarchie et continue d’apparier les clusters jusqu’à ce que tout ait été lié, créant ainsi une série hiérarchique de clusters imbriqués. En résumé, les étapes du partitionnement agglomératif¹⁰ sont les suivantes :

1. Calculez la matrice de dissimilarité en utilisant un indicateur de distance particulier.

2. Attribuez chaque point de données à un cluster.

3. Fusionnez les clusters en fonction d’un critère de liaison pour la similarité entre les clusters.

4. Mettez à jour la matrice de distance.

5. Répétez les étapes 3 et 4 jusqu’à ce qu’il reste un seul cluster ou que tout critère d’arrêt soit atteint.

Les principes du partitionnement hiérarchique par division ont été développés par Macnaughton-Smith et d’autres¹¹ en 1964, puis ils ont été étudiés davantage par Kaufman et Rousseeuw avec leur algorithme DIANA (Divisive ANAlysis clustering)¹² en 1990. Le partitionnement par division utilise l’approche opposée à celle du partitionnement agglomératif. Tous les points de données commencent dans un seul cluster qui est divisé en plusieurs clusters. Le fractionnement se produit jusqu’à ce que tous les clusters restants soient des singletons ou qu’un critère d’arrêt tel qu’un nombre prédéfini de clusters soit atteint. Les méthodes par division permettent d’identifier les clusters volumineux¹³ et peuvent être plus précises que les méthodes agglomératives, car l’algorithme prend en compte l’ensemble de la distribution du jeu de données dès le début du processus.

Pour gagner en efficacité, les méthodes par division utilisent des algorithmes de partitionnement plats tels que k-means pour diviser le jeu de données en clusters. Le nombre de clusters doit être spécifié à l’avance. L’algorithme k-means divise les clusters en minimisant la somme des carrés entre les points centroïdes au sein des clusters. C’est ce que l’on appelle le critère d’inertie¹⁴. Les étapes du partitionnement par division¹⁵ sont les suivantes :

1. Commencez par tous les points de données d’un jeu de données de taille N (d1, d2, d3 ... dN) dans un cluster.

2. Divisez le cluster en deux clusters différents ou hétérogènes en utilisant une méthode de partitionnement plat telle que l’algorithme k-means.

3. Répétez l’étape 2, en choisissant le meilleur cluster à diviser et en supprimant les données aberrantes du cluster le moins cohérent après chaque itération.

4. Arrêtez lorsque chaque exemple se trouve dans son propre cluster, sinon répétez l’étape 3.

Les résultats des clusters sont généralement présentés sous forme de dendrogramme (structure arborescente binaire). L’axe des x du dendrogramme représente les points de données et l’axe des y, ou la hauteur des lignes, indique la distance qui les séparait au moment de leur fusion.

Vous pouvez utiliser un dendrogramme pour déterminer le nombre de clusters¹⁶ que contiendra votre modèle de partitionnement final. Une stratégie consiste à identifier le point de coupure naturel dans l’arbre, où les branches diminuent et deviennent plus longues. Alternativement, le nombre de clusters est donné par le nombre de lignes verticales traversées lorsqu’une ligne horizontale coupe le dendrogramme.

Dans l’exemple présenté ici, la ligne horizontale H1 coupe deux lignes verticales. Cela montre qu’il y a deux clusters à ce stade du processus : un cluster avec les points 5, 8 et 2 et un cluster avec les points restants. Plus la ligne horizontale peut se déplacer vers le haut ou vers le bas sans couper d’autres lignes horizontales dans le dendrogramme, meilleure est la sélection de ce nombre de clusters pour votre modèle de partitionnement. Dans l’exemple ci-dessous, la ligne horizontale H2 sélectionne quatre clusters. H2 ne peut pas se déplacer de haut en bas jusqu’à H1 sans couper d’autres lignes horizontales. Ce scénario montre que le choix de deux clusters (H1) est probablement plus approprié pour votre modèle de partitionnement.

Un modèle de partitionnement robuste¹⁷ crée des clusters avec une similarité intraclasse élevée et une faible similarité interclasse. Cependant, il peut être difficile de définir la qualité des clusters, et votre sélection des critères de liaison et des nombres de clusters peut avoir une incidence significative sur vos résultats. Ainsi, lors de la création d’un modèle de partitionnement, essayez différentes options et sélectionnez celles qui vous aident le mieux à découvrir et à révéler des schémas dans le jeu de données pour une considération future. Les facteurs à prendre en compte¹⁸ sont les suivants :

- Le nombre de clusters pratiques ou logiques pour le jeu de données (compte tenu de la taille du jeu de données, de la forme des clusters, du bruit, etc.)

- Les statistiques, telles que les valeurs moyennes, maximales et minimales pour chaque cluster

- Le meilleur indicateur de dissimilarité ou critère de liaison à appliquer

- L’impact de toute donnée aberrante ou variable de résultat

- Toute connaissance spécifique d’un domaine ou d’un jeu de données

Voici d’autres méthodes permettant de déterminer le nombre optimal de clusters¹⁹ :

- La méthode du coude, qui consiste à tracer la somme des carrés au sein du cluster par rapport au nombre de clusters et à déterminer le « coude » (le point où le graphique se stabilise)

- La statistique d’écart, qui consiste à comparer la somme des carrés réelle à la somme des carrés attendue au sein des clusters pour obtenir une distribution de référence nulle et à identifier l’écart le plus important.

Le partitionnement hiérarchique fournit aux data scientists des informations sur la structure et les relations au sein des jeux de données et peut être appliqué dans de nombreux cas d’utilisation.

Le partitionnement hiérarchique permet d’analyser les tendances et de segmenter les données des clients, par exemple, par choix de produit, démographie, comportement d’achat, profil de risque ou interactions avec les réseaux sociaux.

Les cohortes de patients pour la recherche clinique peuvent se compter par milliers. Le partitionnement hiérarchique permet de classer les populations mixtes en groupes plus homogènes²⁰ en utilisant, par exemple, des critères de diagnostic, des réponses psychologiques ou des mutations de l’ADN. Il peut également être appliqué pour regrouper les espèces par caractéristiques biologiques afin de comprendre leur développement évolutif.

Le partitionnement hiérarchique est utilisé dans les applications de reconnaissance de texte à partir d’images pour regrouper les caractères manuscrits en fonction de leur forme. Il est également utilisé pour stocker et récupérer des informations en fonction de certains critères ou pour classer les résultats de recherche.

Les langages de programmation Python et R sont largement utilisés dans le domaine de la science des données. Python est flexible et peut gérer un large éventail de tâches. En revanche, R est spécialement conçu pour le calcul statistique et propose de nombreuses options pour visualiser votre analyse de partitionnement hiérarchique.

Python fournit la fonction AgglomerativeCluster²¹ (voir aussi les exemples de partitionnement agglomératif²² sur sklearn), et SciPy fournit une fonction pour tracer des dendrogrammes²³. Des packages tels que dendextend²⁴ complètent les fonctionnalités de dendrogramme de R, améliorent l’analyse de sensibilité et vous permettent de comparer et de manipuler différents dendrogrammes. Pour une expérience pratique, consultez nos tutoriels étape par étape : comment implémenter le partitionnement hiérarchique dans Python et comment implémenter le partitionnement hiérarchique dans R.