Regroupement hiérarchique
Type | Algorithme de partitionnement de données (d), partitionnement de données ![]() |
---|---|
Décrit par | The Elements of Statistical Learning (d) ![]() |
modifier - modifier le code - modifier Wikidata
Dans le domaine de l'analyse et de la classification automatique de données, le regroupement hiérarchique est un partitionnement de données ou clustering, au moyen de diverses méthodes, dites « ascendantes » et « descendantes ».
Classification descendante hiérarchique
Les méthodes dites « descendantes » partent d’une solution générale vers une autre plus spécifique. Les méthodes de cette catégorie démarrent avec une seule classe contenant la totalité puis se divisent à chaque étape selon un critère jusqu’à l’obtention d’un ensemble de classes différentes.
Classification ascendante hiérarchique
À l'inverse des méthodes dites « descendantes », la classification ascendante hiérarchique [1] est dite « ascendante » part d'une situation où tous les individus sont seuls dans une classe, puis sont rassemblés en classes de plus en plus grandes. Le qualificatif « hiérarchique » vient du fait qu'elle produit une hiérarchie H, l'ensemble des classes à toutes les étapes de l'algorithme, qui vérifie les propriétés suivantes :
- : au sommet de la hiérarchie, lorsqu'on groupe de manière à obtenir une seule classe, tous les individus sont regroupés ;
- : en bas de la hiérarchie, tous les individus se trouvent seuls ;
- ou ou : si l’on considère deux classes du regroupement, alors soit elles n'ont pas d’individu en commun, soit l'une est incluse dans l’autre.
C'est une méthode de classification automatique utilisée en analyse des données ; à partir d'un ensemble de n individus, son but est de répartir ces individus dans un certain nombre de classes.
La méthode suppose qu'on dispose d'une mesure de dissimilarité entre les individus ; dans le cas de points situés dans un espace euclidien, on peut utiliser la distance comme mesure de dissimilarité. La dissimilarité entre des individus x et y sera notée .
Algorithme
Principe
Initialement, chaque individu forme une classe, soit n classes. On cherche à réduire le nombre de classes à , ce qui se fait itérativement. À chaque étape, on fusionne deux classes choisies comme les plus « proches », donc à la dissimilarité minimale. Cette valeur de dissimilarité, appelée indice d'agrégation, va croître d'itération en itération, la première étant par principe la plus petite.
Mesure de dissimilarité inter-classe
La dissimilarité de deux classes contenant chacune un individu se définit simplement par la dissimilarité entre ses individus.
Lorsque les classes ont plusieurs individus, de multiples critères permettent de calculer la dissimilarité. Les plus simples sont les suivants :
- Le saut minimum retient le minimum des distances entre individus de et : ;
- Le saut maximum est la dissimilarité entre les individus de et les plus éloignés : ;
- Le lien moyen consiste à calculer la moyenne des distances entre les individus de et : ;
- La distance de Ward vise à maximiser l'inertie inter-classe : avec et les effectifs des deux classes, et leurs centres de gravité respectifs.
Implémentation en pseudo-code
Entrées :
- individus : liste d'individus
- nbClasses : nombre de classes que l'on veut finalement obtenir
Sortie :
- classes : liste de classes initialement vide, une classe est vue comme une liste d'individus
Pour i=1 à individus.longueur Faire classes.ajouter(nouvelle classe(individu[i])); Fin Pour Tant Que classes.longueur > nbClasses Faire // Calcul des dissimilarités entre classes dans une matrice triangulaire supérieure matDissim = nouvelle matrice(classes.longueur,classes.longueur); Pour i=1 à classes.longueur Faire Pour j=i+1 à classes.longueur Faire matDissim[i][j] = dissim(classes[i],classes[j]); Fin Pour Fin Pour // Recherche du minimum des dissimilarités Soit (i,j) tel que matDissim[i][j] = min(matDissim[k][l]) avec 1<=k<=classes.longueur et k+1<=l<=classes.longueur; // Fusion de classes[i] et classes[j] Pour tout element dans classes[j] Faire classes[i].ajouter(element); Fin pour supprimer(classes[j]); Fin Tant Que
Dendrogramme
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f5/Dendro.jpg/220px-Dendro.jpg)
Un dendrogramme est la représentation graphique d'une classification ascendante hiérarchique. Il se présente souvent comme un arbre binaire dont les feuilles sont les individus alignés sur l'axe des abscisses. Lorsque deux classes ou deux individus se rejoignent avec l'indice d'agrégation , des traits verticaux sont dessinés de l'abscisse des deux classes jusqu'à l'ordonnée , puis ils sont reliés par un segment horizontal.
À partir d'un indice d'agrégation , on peut tracer une droite d'ordonnée qui permet de voir une classification sur le dendrogramme.
Des versions plus complexes d'arbre de classification peuvent aider à construire un arbre de décision.
Notes et références
- ↑ (en) Gabor J. Székely et Maria L. Rizzo, « Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method. », Journal of Classification, vol. 22, no 2, , p. 151-183 (DOI 10.1007/s00357-005-0012-9)
Voir aussi
Bibliographie
- Thèse « Contextualisation, visualisation et évaluation en apprentissage non supervisé » de Laurent Candillier (Université de Lille 3), 2006/09/15, PDF, 250 pages.
Articles connexes
- Algorithme espérance-maximisation
- Analyse en composantes principales
- Apprentissage automatique
- Apprentissage supervisé
- Apprentissage non supervisé
- Base de données
- Carte auto adaptative
- Exploration de données
- Extraction de connaissances
- Hiérarchie (mathématiques)
- Intelligence artificielle
- Méthode des nuées dynamiques
- Partitionnement de données
- Régression logistique
- Réseau de neurones artificiels
- Sérendipité
- Similarité informatique
- Théorème de Cox-Jaynes
Liens externes
- A visual expedition inside the Linux file systems : étude des similarités entre les systèmes de fichiers implémentés dans Linux, et exemple de classification ascendante hiérarchique
v · m | |||||||||
---|---|---|---|---|---|---|---|---|---|
Paradigmes d'apprentissage | |||||||||
Problèmes | |||||||||
Apprentissage supervisé |
| ||||||||
Apprentissage non supervisé et auto-supervisé |
| ||||||||
Métaheuristique d'optimisation | |||||||||
Théorie | |||||||||
Logiciels |
|
Portail des probabilités et de la statistique
Portail de l’informatique