Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Ecole Nationale Polytechnique d’Alger Cours ADD - 1ère Année-Génie Industriel 8

Ecole Nationale Polytechnique d’Alger Cours ADD - 1ère Année-Génie Industriel 89 Partie III - Classification Chapitre V – Classification hiérarchique Ascendante Introduction : Les techniques de classification automatique sont destinées à produire des groupements de lignes ou de colonnes d'un tableau. Il s'agit le plus souvent d'objets ou d'individus (les lignes) décrits par un certain nombre de variables ou de caractères (les colonnes). Ces groupements peuvent se faire par agglomération progressive des éléments deux à deux (comme cela se fait en classification hiérarchique), ou par recherche directe d'une partition, en affectant les éléments à des centres provisoires de classes, puis en recentrant ces classes (méthode itérative des centres mobiles). Les circonstances d'utilisation de la classification sont sensiblement les mêmes que celles des méthodes d'analyse factorielle descriptive ; on se trouve face à un tableau de valeurs numériques. Ce tableau peut être un tableau de valeurs numériques continues (valeur de la variable j pour l'individu i, à l'intersection de la ligne i et de la colonne j du tableau), un tableau de contingence (croisant deux partitions d'une même population), ou encore un tableau de présence-absence (valeurs 0 ou 1 selon que tel individu ou objet possède tel caractère ou attribut). Dans certaines applications, on peut disposer d'un tableau carré symétrique de similarités ou de distances. Il s’agit de mettre sous forme de partitions des ensembles étudiés (lignes ou colonnes du tableau analysé), ou de hiérarchie de partitions que nous définirons de façon plus précise ultérieurement. Quelquefois, il s'agira d'arbres au sens de la théorie des graphes, arbres dont les sommets sont les objets à classer. Enfin on pourra rechercher des classes empiétantes ou simplement mettre en évidence des zones à forte densité, laissant de nombreux individus ou caractères non classés. Ecole Nationale Polytechnique d’Alger Cours ADD - 1ère Année-Génie Industriel 90 Pour l'essentiel, les techniques de classification font appel à une démarche algorithmique et non aux calculs formalisés usuels. Alors que les valeurs des composantes des axes factoriels, par exemple, sont la solution d'une équation pouvant s'écrire sous une forme très condensée (même si sa résolution est complexe), la définition des classes ne se fera qu'à partir d'une formulation algorithmique: une série d'opérations est définie de façon récursive et répétitive. La mise en œuvre de la plupart des techniques de classification ne nécessite donc, que des notions mathématiques relativement élémentaires. Il existe plusieurs familles d'algorithmes de classification, mais on se limitera à deux techniques de classification :  la classification ascendante hiérarchique qui peut être présentée suivant plusieurs critères d'agrégation. La technique « du saut minimal » (single linkage) est équivalente à la recherche de l'arbre de longueur minimale, alors que la technique d'agrégation selon « la variance », est compatible par ses résultats avec certaines analyses factorielles.  techniques d'agrégation autour de centres mobiles. Un des avantages des méthodes de classification est de créer des éléments qui sont des groupements d’individus qui se ressemblent (les classes) souvent plus faciles à décrire et interpréter que les axes factoriels. En pratique, il est plus intéressant d’utiliser de façon conjointe les méthodes factorielles et les méthodes de classification. I - Classification hiérarchique ascendante : Les principes généraux communs aux diverses techniques de classification ascendante hiérarchique (notée souvent CAH) sont très simples. Elles reposent sur un algorithme convergeant nécessairement vers une classe regroupant tous les individus étudiés. Le principe de l'algorithme consiste à créer, à chaque étape, une partition obtenue en agrégeant deux à deux les éléments les plus proches. On désignera ici par élément à la fois les individus ou objets à classer eux-mêmes et les regroupements d'individus générés par l'algorithme. Il y a différentes manières de considérer le nouveau couple d'éléments agrégés. C’est pourquoi, on trouve un nombre important de variantes de cette technique. Ecole Nationale Polytechnique d’Alger Cours ADD - 1ère Année-Génie Industriel 91 L'algorithme ne fournit pas une partition en q classes d'un ensemble de n objets mais fournit une hiérarchie de partitions, se présentant sous la forme d'arbres appelés dendrogrammes et contenant (n – 1) partitions. L'intérêt de ces arbres est qu'ils peuvent être utilisés pour donner une idée du nombre de classes existant effectivement dans la population. Chaque coupure d'un arbre fournit une partition. Cette partition aura d'autant moins de classes et des classes d'autant moins homogènes que l'on coupe l’arbre plus haut II - Distances et indices d’agrégation : On suppose que l'ensemble des individus à classer est muni d'une distance (il s'agira parfois simplement d'une mesure de dissimilarité ; dans ce cas, l'inégalité triangulaire d(x,y) ≤ d(x,z) + d(y,z) n'est pas exigée). Ceci ne suppose pas que les distances soient toutes calculées en même temps : il faut pouvoir les calculer ou les recalculer à partir des coordonnées des points-individus, celles-ci devant être accessibles rapidement. On peut calculer ainsi une matrice de distances entre tous les individus deux à deux. III - Critères d’agrégation : Une fois constitué un groupe d'individus, il est nécessaire ensuite de savoir évaluer une distance entre un individu et un groupe, et par la suite une distance entre deux groupes. Ceci revient à définir une stratégie de regroupements des éléments, c'est-à-dire se fixer des règles de calcul des distances entre groupements disjoints d'individus. Ces règles sont appelées critères (ou indices) d'agrégation. La distance entre ces groupements pourra en général se calculer directement à partir des distances des différents éléments impliqués dans le regroupement. Par exemple :  Si x, y, z sont trois objets ;  Et si les objets x et y sont regroupés en un seul élément noté h, on peut définir la distance de ce groupement à z par la plus petite distance des deux éléments de h à z : d(h,z) = Min {d(x,z), d(y,z) } . Cette distance s'appelle le saut minimal (single linkage) (Sneath, 1957 ; Johnson, 1967) et constitue un critère d'agrégation.  On peut également définir la distance du saut maximal (ou diamètre) en prenant la plus grande distance des deux éléments de h à z : d(h,z) = Max {d(x,z), d(y,z) } Ecole Nationale Polytechnique d’Alger Cours ADD - 1ère Année-Génie Industriel 92  Une autre règle simple et fréquemment employée est celle de la distance moyenne ; pour deux objets x et y regroupés en h : d(h,z)  (d(x,z)  d(y, z))/ 2  Plus généralement, si x et y désignent des sous-ensembles disjoints de l'ensemble des objets, ayant respectivement nx et ny éléments, h est alors un sous-ensemble formé de (nx + ny )éléments et on définit la distance entre l’ensemble h et un élément z par : d(h,z)  (nx d(x,z)  ny d(y,z))/( nx  ny) IV - Algorithme de classification : L'algorithme fondamental de classification ascendante hiérarchique se déroule de la façon suivante : Étape 1 : il y a n éléments à classer (qui sont les n individus); Étape 2 : on construit la matrice de distances entre les n éléments et l'on cherche les deux plus proches, que l'on agrège en un nouvel élément. On obtient une première partition à (n-1) classes; Étape 3 : on construit une nouvelle matrice des distances qui résultent de l'agrégation, en calculant les distances entre le nouvel élément et les éléments restants (les autres distances sont inchangées). On se trouve dans les mêmes conditions qu'à l'étape 1, mais avec seulement (n-1) éléments à classer et en ayant choisi un critère d'agrégation. On cherche de nouveau les deux éléments les plus proches, que l'on agrège. On obtient une deuxième partition avec n-2 classes et qui englobe la première; Etc. …. …. …. …. Étape m : on calcule les nouvelles distances, et l'on réitère le processus jusqu'à n'avoir plus qu'un seul élément regroupant tous les objets et qui constitue la dernière partition. Exemple : Nous illustrons cette procédure en prenant comme objets à classer cinq points. (1) (2) (3) (4) (5) (1) 0 9 1 4 9 (2) 9 0 9 9 2 (3) 1 9 0 4 9 (4) 4 9 4 0 9 (5) 9 2 9 9 0 Ecole Nationale Polytechnique d’Alger Cours ADD - 1ère Année-Génie Industriel 93  A la 1ère étape, on essaiera d’agréger les deux points les plus proches parmi les cinq.  Il s’agit des points (1) et (3) puisque d((1),(3))= { ) )) }  Les points (1) et (3) sont désormais agrégés. Il faudra reconstruire une nouvelle matrice de rang inférieur de telle manière à regrouper ces deux points.  On recalcule seulement les distances entre le nouvel objet obtenu {(1),(3)}et les autres points ; les autres distances ne changeant pas.  En utilisant le critère du saut minimal, on obtiendra d((i),{(1),(3)})= { ) )) }  La nouvelle matrice sera (1),(3) (2) (4) (5) (1),(3) 0 9 4 9 (2) 9 0 9 2 (4) 4 9 0 9 (5) 9 2 9 0  En même temps, on commence à tracer l’arborescence (1) (3) (2) (4) (5)  On refait l’opération jusqu’à ce que tous les ponts soient agrégés.  Les étapes à venir sont donc les uploads/Industriel/ classification-afd.pdf