# Regroupement hiérarchique

Un article de Wikipédia, l'encyclopédie libre.

Dans le domaine informatique, et plus précisément dans le domaine de l'analyse et de la classification automatique de données, la notion de regroupement hiérarchique recouvre différentes méthodes de clustering, c'est-à-dire de classification par algorithme de classification.

## La classification ascendante hiérarchique (CAH)[modifier | modifier le code]

C'est une méthode de classification automatique utilisée en analyse des données ; à partir d'un ensemble Ω {\displaystyle \Omega } 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 d i s s i m ( x , y ) {\displaystyle dissim(x,y)} .

La classification ascendante hiérarchique [1]est dite ascendante car elle 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 :

- Ω ∈ H {\displaystyle \Omega \in H} : au sommet de la hiérarchie, lorsqu'on groupe de manière à obtenir une seule classe, tous les individus sont regroupés ;
- ∀ ω ∈ Ω , { ω } ∈ H {\displaystyle \forall \omega \in \Omega ,\{\omega \}\in H} : en bas de la hiérarchie, tous les individus se trouvent seuls ;
- ∀ ( h , h ′ ) ∈ H 2 , h ∩ h ′ = ∅ {\displaystyle \forall (h,h')\in H^{2},h\cap h'=\emptyset } ou h ⊂ h ′ {\displaystyle h\subset h'} ou h ′ ⊂ h {\displaystyle h'\subset h} .

### Algorithme[modifier | modifier le code]

#### Principe[modifier | modifier le code]

Initialement, chaque individu forme une classe, soit n classes. On cherche à réduire le nombre de classes à n b c l a s s e s < n {\displaystyle nb_{classes}<n} , ceci se fait itérativement. À chaque étape, on fusionne deux classes, réduisant ainsi le nombre de classes. Les deux classes choisies pour être fusionnées sont celles qui sont les plus « proches », en d'autres termes, celles dont la dissimilarité entre elles est minimale, cette valeur de dissimilarité est appelée indice d'agrégation. Comme on rassemble d'abord les individus les plus proches, la première itération a un indice d'agrégation faible, mais celui-ci va croître d'itération en itération.

#### Mesure de dissimilarité inter-classe[modifier | modifier le code]

La dissimilarité de deux classes C 1 = { x } , C 2 = { y } {\displaystyle C_{1}=\{x\},C_{2}=\{y\}} contenant chacune un individu se définit simplement par la dissimilarité entre ses individus. d i s s i m ( C 1 , C 2 ) = d i s s i m ( x , y ) {\displaystyle dissim(C_{1},C_{2})=dissim(x,y)}

Lorsque les classes ont plusieurs individus, il existe de multiples critères qui permettent de calculer la dissimilarité. Les plus simples sont les suivants :

- Le saut minimum retient le minimum des distances entre individus de C 1 {\displaystyle C_{1}} et C 2 {\displaystyle C_{2}} : d i s s i m ( C 1 , C 2 ) = min x ∈ C 1 , y ∈ C 2 ( d i s s i m ( x , y ) ) {\displaystyle dissim(C_{1},C_{2})=\min _{x\in C_{1},y\in C_{2}}(dissim(x,y))} ;
- Le saut maximum est la dissimilarité entre les individus de C 1 {\displaystyle C_{1}} et C 2 {\displaystyle C_{2}} les plus éloignés : d i s s i m ( C 1 , C 2 ) = max x ∈ C 1 , y ∈ C 2 ( d i s s i m ( x , y ) ) {\displaystyle dissim(C_{1},C_{2})=\max _{x\in C_{1},y\in C_{2}}(dissim(x,y))} ;
- Le lien moyen consiste à calculer la moyenne des distances entre les individus de C 1 {\displaystyle C_{1}} et C 2 {\displaystyle C_{2}} : d i s s i m ( C 1 , C 2 ) = m o y e n n e x ∈ C 1 , y ∈ C 2 ( d i s s i m ( x , y ) ) {\displaystyle dissim(C_{1},C_{2})=moyenne_{x\in C_{1},y\in C_{2}}(dissim(x,y))} ;
- La distance de Ward vise à maximiser l'inertie inter-classe : d i s s i m ( C 1 , C 2 ) = n 1 ∗ n 2 n 1 + n 2 d i s s i m ( G 1 , G 2 ) {\displaystyle dissim(C_{1},C_{2})={\frac {n_{1}*n_{2}}{n_{1}+n_{2}}}dissim(G_{1},G_{2})} avec n 1 {\displaystyle n_{1}} et n 2 {\displaystyle n_{2}} les effectifs des deux classes, G 1 {\displaystyle G_{1}} et G 2 {\displaystyle G_{2}} leurs centres de gravité respectifs.

#### Implémentation en pseudo-code[modifier | modifier le 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[modifier | modifier le code]

Voir l'article : dendrogramme.
Exemple de dendrogramme.

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 τ {\displaystyle \tau } , des traits verticaux sont dessinés de l'abscisse des deux classes jusqu'à l'ordonnée τ {\displaystyle \tau } , puis ils sont reliés par un segment horizontal. À partir d'un indice d'agrégation τ {\displaystyle \tau } , on peut tracer une droite d'ordonnée τ {\displaystyle \tau } qui permet de voir une classification sur le dendrogramme.
Des versions plus complexes d'arbre de classification peuvent éventuellement aider à construire un arbre de décision.

## Voir aussi[modifier | modifier le code]

### Articles connexes[modifier | modifier le code]

- Base de données
- Hiérarchie (mathématiques)
- Similarité informatique
- Intelligence artificielle
- Apprentissage automatique
- Apprentissage supervisé
- Apprentissage non-supervisé
- Réseau de neurones
- Partitionnement de données
- Algorithme espérance-maximisation
- Carte auto adaptative
- Subspace clustering
- Extraction de connaissances
- Règles explicatives
- Contextualisation
- Visualisation
- Évaluation en cascade
- Données semi-structurées
- Méthode des nuées dynamiques
- Théorème de Cox-Jaynes
- Analyse en composantes principales
- Régression logistique
- Sérendipité
- Exploration de données

## Liens externes[modifier | modifier le code]

- A visual expedition inside the Linux file systems [archive] : étude des similarités entre les systèmes de fichiers implémentés dans Linux, et exemple de classification ascendante hiérarchique

### Bibliographie[modifier | modifier le code]

- Thèse « Contextualisation, visualisation et évaluation en apprentissage non supervisé » [archive] de Laurent Candillier (Université de Lille 3), 2006/09/15, PDF, 250 pages.

### Notes et références[modifier | modifier le code]

1. ↑ « Székely, G.J., Rizzo, M.L., 2005. Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method. Journal of Classification, 22, 151-183. », {{Article}} : paramètre « `périodique` » manquant, paramètre « `année` » ou « `date` » manquant

- Portail des probabilités et de la statistique
- Portail de l’informatique

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Regroupement_hiérarchique&oldid=140625653 ».
Catégories :

- Algorithme de classification
- Théorie des ordres
- Exploration de données

[+]
Catégories cachées :

- Page du modèle Article comportant une erreur
- Portail:Probabilités et statistiques/Articles liés
- Projet:Mathématiques/Articles
- Portail:Informatique/Articles liés