Les techniques d'analyse hiérarchique et de cluster sont des outils fondamentaux de la boîte à outils du data savant, permettant aux chercheurs et aux analystes de découvrir des structures cachées et des regroupements significatifs au sein de ensembles de données complexes.Ces méthodes sont appliquées dans un large éventail de domaines, de la biologie et de la génétique au marketing, aux sciences sociales et à l'analyse d'image, pour transformer les données brutes en idées concrètes.

Comprendre les regroupements hiérarchiques

Le cluster hiérarchique est une famille d'algorithmes de cluster qui construisent une hiérarchie imbriquée de clusters, généralement visualisée comme un diagramme de type arbre appelé un dendrogramme. Contrairement aux méthodes partitionnelles (comme les moyennes k), le regroupement hiérarchique n'exige pas de l'utilisateur qu'il pré-specifie le nombre de regroupements. Il fournit plutôt une représentation détaillée des relations de données à différents niveaux de granularité, permettant à l'analyste de choisir le point de coupe le plus significatif.

Approches agglomératives et approches disciplinées

Le cluster hiérarchique est offert dans deux saveurs principales:

  • Agglomérat (fond-up): C'est l'approche la plus courante. Elle commence par chaque point de données comme son propre cluster. Ensuite, à chaque étape, les deux clusters les plus similaires sont fusionnés. Ce processus se répète jusqu'à ce que tous les points appartiennent à un cluster unique.
  • Diviseur (en haut) : Cette approche commence avec tous les points de données d'un cluster. Ensuite, elle divise récursivement le cluster le moins cohésif en clusters plus petits jusqu'à ce que chaque point soit dans son propre cluster de singleton. Bien que moins commun en raison de la complexité computationnelle, les méthodes de division peuvent être utiles lorsque les données se séparent naturellement du haut.

Critères de couplage

La clé de l'aggloméré est la critère de liaison, qui définit la façon dont la distance entre deux clusters est calculée. Différents critères de liaison produisent différentes formes de dendrogramme et les attributions de clusters.

  • Lien unique (nôt le voisin): La distance entre deux amas est la distance minimale entre n'importe quel point d'un amas et n'importe quel point de l'autre. Elle peut former de longs amas en chaîne et est sensible au bruit.
  • Lien complet (à l'écart du voisin): La distance est la distance maximale entre n'importe quelle paire de points à travers les deux amas. Cela tend à produire des amas compacts, sphériques mais peut être sensible aux aberrations.
  • Lien moyen (UPGMA): La distance est la moyenne de toutes les distances par paire entre les points des deux amas. Elle offre un terrain intermédiaire entre un seul et un lien complet.
  • Méthode de Ward: La distance est l'augmentation de la variance totale à l'intérieur de la grappe après fusion. La méthode de Ward minimise la somme totale des erreurs carrées et tend à produire des grappes de taille à peu près égale.

métriques de distance

Le choix de la distance métrique est également important. Distance euclidienne, mais d'autres mesures comme Manhattan, la similitude des cosinus ou les distances basées sur la corrélation peuvent être plus appropriées selon le type de données (par exemple, texte, expression des gènes, coordonnées spatiales).

Interprétation du Dendroggram et choix du nombre de grappes

Un dendrogramme affiche la hiérarchie des fusions. L'axe vertical représente généralement la distance ou la dissimilarité à laquelle les amas sont fusionnés. Pour choisir un certain nombre de clusters, l'analyste peut couper le dendrogramme à une certaine hauteur. Une heuristique commune est de chercher de grands sauts dans la distance de fusion — une augmentation soudaine suggère que la fusion plus loin combinerait des amas naturels qui sont très éloignés. méthode du coude appliquée à la hauteur des fusions peut aider à identifier un point de coupe significatif.

Le cluster hiérarchique est particulièrement utile lorsque la structure attendue est hiérarchique (par exemple, la taxonomie biologique) ou lorsque le nombre de clusters est inconnu. Cependant, il a des limites : le dendrogramme peut être encombré de gros ensembles de données, et l'algorithme a une complexité temporelle de O(n2) à O(n3), ce qui le rend moins évolutive que les méthodes partitionnelles.

Comprendre l'analyse par division (groupe)

Le regroupement partiel, souvent appelé simplement analyse de cluster, assigne chaque point de données à exactement un nombre de clusters (k) pré-pré-sélectionnés. L'objectif est de partitionner les données de sorte que les points au sein d'un cluster soient aussi semblables que possible, et les points dans différents clusters sont aussi différents que possible. k-moyens de regroupement, mais d'autres méthodes comme DBSCAN et Modèles de mélange gaussien sont également largement utilisés.

Groupement de K-Means

K-means est un algorithme basé sur le centroid qui divise les observations n en groupes k, chacun représenté par la moyenne (centroid) des points du cluster. L'algorithme fonctionne comme suit:

  1. Initialiser les centroïdes k au hasard (ou utiliser une initialisation intelligente comme k-means++).
  2. Attribuer chaque point de données au centroïde le plus proche.
  3. Recalculer chaque centroïde comme la moyenne de tous les points assignés à son amas.
  4. Répétez les étapes 2 et 3 jusqu'à ce que les centroïdes cessent de bouger (convergence) ou qu'un nombre maximum d'itérations soit atteint.

La moyenne K est rapide et s'équilibre bien avec les grandes séries de données (O(n*k*i) où i = itérations).

  • Il suppose que les amas sont sphériques et à peu près égaux en taille (en raison de la distance euclidienne).
  • Il est sensible aux aberrations, qui peuvent tirer les centroïdes loin des véritables centres de clusters.
  • Il faut que k soit spécifié au préalable, ce qui est souvent inconnu.
  • Il peut converger vers un optimum local, de sorte que plusieurs parcours avec différentes initialisations sont recommandés.

Choix du nombre de grappes (k)

Plusieurs techniques aident à déterminer un k approprié:

  • Méthode de l'incision: Placez la somme de carrés (WCSS) à l'intérieur du groupe contre k. Le point où le WCSS commence à diminuer plus lentement (le --elbow) est un candidat pour k.
  • Analyse de la silhouette: Le coefficient de silhouette mesure la similitude d'un point avec son propre groupe par rapport à d'autres groupes. Les scores moyens de silhouette pour différentes valeurs de k peuvent être tracés; la valeur la plus élevée indique le meilleur k.
  • Statistiques sur les écarts: Comparer le WCSS des données à une distribution de référence nulle. L'optimum k est là où l'écart est le plus grand.

DBSCAN (Cluster spatial de sensibilité des applications avec bruit)

DBSCAN est un algorithme basé sur la densité qui pas k. Au lieu de cela, il définit les grappes comme des régions denses séparées par des régions peu étendues. Il comporte deux paramètres clés: eps (le rayon du quartier autour d'un point) et minPts (le nombre minimum de points requis pour former une région dense). Les points qui ne font pas partie d'une région dense sont étiquetés comme du bruit. DBSCAN peut découvrir des grappes de forme arbitraire (contrairement aux moyennes k) et est robuste à aberrant.

Comparaison des regroupements hiérarchiques et partiels

Les deux paradigmes sont utiles, mais ils répondent à différents besoins. Le cluster hiérarchique fournit une structure entièrement imbriquée, ce qui le rend idéal lorsque vous voulez explorer des données à plusieurs niveaux. Les méthodes partielles comme les moyennes k sont plus rapides et évolutives, mais elles exigent que le nombre de clusters soit spécifié et prennent une forme spécifique de cluster. En pratique, de nombreux analystes utilisent le cluster hiérarchique sur un petit échantillon pour décider k, puis appliquent les moyennes k sur l'ensemble des données. Les approches hybrides, comme d'abord l'utilisation de DBSCAN pour supprimer le bruit et ensuite l'application du cluster hiérarchique sur les points de base, peuvent également être efficaces.

Validation des groupes

Une étape souvent négligée mais cruciale est validation du groupe — évaluation de la qualité et de la pertinence des grappes découvertes, les méthodes de validation se répartissant en deux catégories:

  • Validation interne: Les indices communs comprennent le score de silhouette, l'indice Davies-Bouldin, l'indice Dunn et l'indice Calinski-Harabasz. Ils aident à comparer différents algorithmes ou nombres de clusters.
  • Validation externe: Il faut des étiquettes de vérité au sol (p. ex., classes connues). Des mesures comme l'indice Rand ajusté, l'information mutuelle et les scores d'homogénéité/exhaustivité comparent le regroupement aux catégories réelles.

Validez toujours les résultats de regroupement en utilisant au moins une mesure interne, et si possible, l'expertise du domaine ou les étiquettes externes. Un regroupement qui semble mathématiquement optimal peut ne pas être pratiquement utile.

Applications de l'analyse hiérarchique et des grappes

Ces techniques ont été appliquées avec succès dans d'innombrables domaines. Voici quelques exemples détaillés:

Biologie et écologie

Le regroupement hiérarchique est une pierre angulaire de la phylogénétiqueEn écologie, l'analyse des grappes est utilisée pour regrouper les espèces en fonction des préférences en matière d'habitat ou pour identifier des biomes distincts à partir de données de télédétection.

Commercialisation et segmentation des clients

Les entreprises utilisent le regroupement pour segmenter les clients en fonction de leur comportement d'achat, de leur démographie ou de leurs habitudes de navigation. Le regroupement hiérarchique permet de visualiser comment les segments se rapportent les uns aux autres, ce qui permet de mieux nuancer les stratégies de marketing.

Organisation des documents et modélisation des sujets

Les algorithmes de regroupement sont utilisés pour regrouper des documents (articles d'actualité, articles scientifiques, documents juridiques) en catégories d'actualités. Les fonctionnalités sont souvent des vecteurs TF-IDF ou des ancrages de mots.

Analyse d'image et reconnaissance des objets

Dans la vision informatique, le cluster est utilisé pour la segmentation d'images (la partition d'une image dans des régions significatives), la quantification des couleurs et le regroupement des fonctionnalités. Le cluster hiérarchique aide à construire des pyramides d'images, et DBSCAN est utilisé dans le traitement des nuages point (p. ex., les données LiDAR) pour cluster des points 3D représentant des objets.

Détection des anomalies

Des méthodes basées sur la densité comme DBSCAN détectent naturellement des points de bruit aberrants. Dans la détection de fraude ou de l'intrusion en réseau, le regroupement peut identifier des motifs inhabituels qui s'écartent des grappes normales.

Conclusion

L'analyse hiérarchique et l'analyse des grappes sont des techniques puissantes et complémentaires pour explorer et comprendre les données. L'analyse hiérarchique des grappes fournit une structure arborescente riche et interprétable qui révèle les relations de données à plusieurs échelles, tandis que les algorithmes partitionnels comme les moyennes k et DBSCAN offrent rapidité et flexibilité pour les applications à grande échelle. Le choix de la méthode dépend de la taille de l'ensemble de données, des propriétés des grappes souhaitées et du contexte de domaine.

Pour plus de détails, voir le document Wikipedia article sur le cluster hiérarchique, les k-means page de regroupementet La documentation complète de scikit-learn- Oui.