Regroupement hiérarchique
Le regroupement hiérarchique, également connu sous le nom d'analyse de regroupement hiérarchique (ARH), est une méthode de regroupement en exploration de données et en statistiques qui vise à construire une hiérarchie de groupes. Contrairement aux méthodes de partitionnement telles que les k-moyennes, qui nécessitent de spécifier à l'avance le nombre de groupes, le regroupement hiérarchique produit une structure imbriquée qui peut être coupée à n'importe quel niveau pour obtenir différents nombres de groupes. Les résultats sont généralement présentés sous forme de dendrogramme, un diagramme en forme d'arbre qui illustre la séquence des fusions ou des divisions. Cette approche est largement utilisée dans des domaines tels que la biologie, les sciences sociales et l'apprentissage automatique pour l'analyse exploratoire des données.
L'avantage clé du regroupement hiérarchique réside dans sa flexibilité : toute mesure de distance valide peut être utilisée, et les observations elles-mêmes ne sont pas requises, seulement une matrice de distances. Cependant, à l'exception du cas particulier de la distance à lien unique, aucun des algorithmes ne peut garantir de trouver la solution optimale sans une recherche exhaustive, dont la complexité temporelle est de O(2^n).
Stratégies agglomératives et divisives
Les stratégies de regroupement hiérarchique se répartissent généralement en deux catégories : agglomératives et divisives. Le regroupement agglomératif, souvent appelé approche « ascendante », commence avec chaque point de données comme groupe individuel. À chaque étape, l'algorithme fusionne les deux groupes les plus similaires en fonction d'une métrique de distance choisie (par exemple, la distance euclidienne) et d'un critère de liaison (par exemple, le lien unique, le lien complet). Ce processus se poursuit jusqu'à ce que tous les points de données soient combinés en un seul groupe ou qu'un critère d'arrêt soit satisfait. Les méthodes agglomératives sont plus couramment utilisées en raison de leur simplicité et de leur efficacité computationnelle pour les ensembles de données de petite à moyenne taille.
Le regroupement divisif, connu sous le nom d'approche « descendante », commence avec tous les points de données dans un seul groupe et divise récursivement le groupe en sous-groupes plus petits. À chaque étape, l'algorithme sélectionne un groupe et le divise en deux ou plusieurs sous-ensembles, souvent en utilisant un critère tel que la maximisation de la distance entre les groupes résultants. Les méthodes divisives sont moins courantes mais peuvent être utiles lorsque l'objectif est d'identifier d'abord les grands groupes distincts. En général, les fusions et divisions sont déterminées de manière gloutonne, ce qui signifie que l'algorithme fait des choix localement optimaux à chaque étape sans tenir compte de la structure globale.
Complexité et algorithmes
L'algorithme standard pour le regroupement hiérarchique agglomératif (RHA) a une complexité temporelle de O(n^3) et nécessite une mémoire de Ω(n^2), ce qui le rend trop lent pour les ensembles de données de grande taille. Cependant, pour certains cas particuliers, des méthodes agglomératives optimales et efficaces de complexité O(n^2) sont connues : SLINK pour le lien unique et CLINK pour le lien complet. Avec l'utilisation d'un tas, la durée d'exécution du cas général peut être réduite à O(n^2 log n) au lieu de O(n^3), au prix d'exigences mémoire supplémentaires. Dans de nombreux cas, les surcoûts mémoire de cette approche sont trop importants pour qu'elle soit pratiquement utilisable. Il existe des méthodes qui utilisent des quadtrees et démontrent une durée totale de O(n^2) avec un espace de O(n).
Le regroupement divisif avec une recherche exhaustive a une complexité de O(2^n), mais il est courant d'utiliser des heuristiques plus rapides pour choisir les divisions, comme les k-moyennes. Ces heuristiques échangent l'optimalité contre la faisabilité computationnelle, permettant d'appliquer les méthodes divisives à des ensembles de données plus volumineux.
Métriques de distance
Alors que le critère de liaison détermine comment la dissimilarité entre les ensembles d'observations est calculée, la métrique de distance sous-jacente détermine comment la dissimilarité entre les observations individuelles est mesurée. Étant donné que le regroupement hiérarchique permet toute mesure de distance valide, le choix de la métrique est guidé par la nature des données et peut avoir un effet significatif sur le regroupement résultant.
La distance euclidienne est la métrique la plus largement utilisée pour les données numériques continues. Elle correspond à la distance en ligne droite entre deux points dans l'espace euclidien et est le choix par défaut dans la plupart des logiciels statistiques. La distance de Manhattan (également appelée distance en bloc ou distance L1) somme les différences absolues entre les caractéristiques. Elle est souvent préférée lorsque les caractéristiques sont mesurées sur différentes échelles ou lorsque les données contiennent des valeurs aberrantes, car elle est moins sensible aux grandes déviations que la distance euclidienne. La distance cosinus mesure la dissimilarité angulaire entre deux vecteurs non nuls et est couramment utilisée dans l'analyse de texte et d'autres contextes à haute dimensionnalité.
Critères de liaison
Le critère de liaison détermine comment la distance entre deux groupes est calculée à partir des distances entre leurs membres individuels. Le lien unique (ou plus proche voisin) utilise la distance minimale entre deux points quelconques des deux groupes, ce qui tend à produire des groupes longs et en chaîne. Le lien complet (ou plus éloigné voisin) utilise la distance maximale entre deux points quelconques des deux groupes, ce qui tend à produire des groupes compacts et sphériques. La liaison moyenne utilise la distance moyenne entre toutes les paires de points, offrant un compromis entre les deux. La méthode de Ward minimise la variance totale intra-groupe, ce qui la rend populaire pour les données continues. Le choix du critère de liaison peut modifier considérablement la forme et l'interprétation du dendrogramme résultant.
Applications et limites
Le regroupement hiérarchique est utilisé dans de nombreux domaines. En biologie, il sert à construire des arbres phylogénétiques basés sur la similarité génétique. En marketing, il aide à segmenter les clients en groupes ayant des comportements similaires. En analyse d'images, il peut regrouper des pixels ou des caractéristiques. Dans le domaine de l'intelligence artificielle, il est souvent utilisé comme technique d'apprentissage non supervisé pour l'analyse exploratoire des données et comme étape de prétraitement pour d'autres algorithmes.
Malgré ses avantages, le regroupement hiérarchique présente des limites. La nature gloutonne des algorithmes signifie qu'une fois qu'une fusion ou une division est effectuée, elle ne peut pas être annulée, ce qui peut conduire à des résultats sous-optimaux. La complexité computationnelle de l'algorithme standard restreint son utilisation à des ensembles de données de taille modérée, bien que des implémentations optimisées existent pour des critères de liaison spécifiques. De plus, l'interprétation d'un dendrogramme peut être subjective, et le choix de la métrique de distance et du critère de liaison nécessite une connaissance du domaine.