Regroupement hiérarchique

Regroupement hiérarchique

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.

Sommaire

La classification ascendante hiérarchique

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 dissim(x,y).

La classification ascendante hiérarchique 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:

  • \Omega \in H: au sommet de la hiérarchie, lors qu'on groupe de manière à obtenir une seule classe, tous les individus sont regroupés
  • \forall \omega \in H, \{\omega\} \in H: en bas de la hiérarchie, tous les individus se trouvent seuls
  • \forall (h,h') \in H^2, h \cap h' = \emptyset ou h \subset h' ou h' \subset h

Algorithme

Principe

Initialement, chaque individu forme une classe, soit n classes. On cherche à réduire le nombre de classes à nbclasses < n, ceci se fait itérativement. A 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

La dissimilarité de deux classes C1 = x,C2 = y contenant chacune un individu se définit simplement par la dissimilarité entre ces individus. dissim(C1,C2) = 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 C1 et C2: 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 C1 et C2 les plus éloignés: 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 C1 et C2: 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: dissim(C_1,C_2) = \frac{n_1*n_2}{n_1+n_2} dissim(G_1,G_2) avec n1 et n2 les effectifs des deux classes, G1 et G2 leurs centres de gravité respectifs

Implémentation en pseudo-code

Entrées:

  • individus: liste d'individus
  • nbClasses: nombre de classes qu'on veut obtenir au final

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

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. Lors que 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 éventuellement aider à construire un arbre de décision.

Logiciels

  • Alceste (logiciel)  ; logiciel de classification descendante ;
  • IMSL ; bibliothèque mathématique et statistique

Voir aussi

Articles connexes

Liens externes

Bibliographie

Notes et références


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Regroupement hiérarchique de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Regroupement hierarchique — Regroupement hiérarchique La classification ascendante hiérarchique est une méthode de classification automatique utilisée en analyse des données. A partir d un ensemble Ω de n individus, son but est de répartir ces individus dans un certain… …   Wikipédia en Français

  • Regroupement familial en France — Regroupement familial Introduction Droit des étrangers (France) …   Wikipédia en Français

  • Regroupement familial — Introduction Droit des étrangers (France) …   Wikipédia en Français

  • Droit au regroupement familial — Regroupement familial Introduction Droit des étrangers (France) …   Wikipédia en Français

  • Dendrogramme — Un dendrogramme (du Grec dendron arbre , gramma dessiner ) est un diagramme fréquemment utilisé pour illustrer l arrangement de groupes générés par un regroupement hiérarchique. Les dendrogrammes sont souvent utilisés en biologie pour illustrer… …   Wikipédia en Français

  • Partitionnement de données — Exemple de clustering hiérarchique Le partitionnement de données (data clustering en anglais) est une des méthodes Statistiques d analyse des données. Elle vise à diviser un ensemble de données en différents « paquets » homogènes, en ce …   Wikipédia en Français

  • Fouille d'images — Exploration de données Articles principaux Exploration de données Fouille de données spatiales Fouille du web Fouille de flots de données Fouille de textes …   Wikipédia en Français

  • Classification sous contrainte — En intelligence artificielle, la classification sous contrainte désigne une famille d algorithmes d apprentissage semi supervisée. Cette dernière occupe une place intermédiaire entre l apprentissage supervisé (pour laquelle les étiquettes de… …   Wikipédia en Français

  • Partitionnement de donnees — Partitionnement de données Le partitionnement de données (data clustering en anglais) est une méthode statistique d analyse des données qui a pour but de regrouper un ensemble de données en différents paquets homogènes, en ce sens que les données …   Wikipédia en Français

  • Apprentissage automatique — L apprentissage automatique (machine learning en anglais), un des champs d étude de l intelligence artificielle, est la discipline scientifique concernée par le développement, l analyse et l implémentation de méthodes automatisables qui… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”