Classification ascendante hiérarchique, critère de Ward

Soit une matrice de dissimilarités, euclidiennes ou non, de composantes d . La classification ascendante hiérarchique regroupe les individus (ou objets) les plus similaires, qui vont former de nouveaux individus agrégés, dont les plus similaires sont à nouveau regroupés pour créer, au final, un dendrogramme. Le point crucial consiste à définir la dissimilarité entre le nouvel individu formé par le regroupement de deux individus a et b, et un autre individu i, noté comme d((a, b), i). Plusieurs critères d’agrégation, bien connus, ont été proposés pour calculer cette nouvelle dissimilarité, tels que le saut maximal, le saut minimal, la moyenne des distances, etc. (voir par exemple Lebart et al., 1995, section 2.2 ; Jain et al., 1999, section 5.1 ; Le Roux et Rouanet, 2004, section 3.6 ; Saporta, 2006, section 11.3). Toutes ces méthodes constituent des cas particuliers de la formule de Lance et Williams généralisée (voir par exemple Saporta, 2006, section 11.3.2.2). Parmi ces dernières, seul le critère de Ward, utilisé dans le chapitre 8, est présenté ici. ), le critère de Ward consiste à minimiser l’inertie intra-groupe et donc à maximiser l’inertie inter-groupe à chaque étape. À la première étape, tous les individus représentent un groupe, et donc l’inertie intra- groupe est nulle (∆diminue, et ce jusqu’à la dernière étape, r, lorsque tous les individus ne forment plus qu’un groupe. L’inertie intra-groupe est alors maximale (∆= (δ(i, j)), qui donne, pour chaque paire d’individus (i, j), la valeur du critère d’agrégation (2.5). Comme avec les autres critères, la paire d’individus dont la valeur est la plus petite (a et b par exemple) sont regroupés pour former un nouvel individu.

Puis, pour recalculer D La méthode K-means (ou méthode des centres mobiles), déjà brièvement présentée avec les dissimilarités objet-groupe au début de cette section, est relativement intuitive et sa paternité n’est pas clairement établie. Lebart et al. (1995) proposent cependant quelques pistes dans l’introduction de leur section 2.1. On peut, entre autres, noter que l’algorithme K-means présenté par MacQueen (1967) diffère de la procédure ci-dessous, car la position des centroïdes (ou centres de gravité) est recalculée après chaque nouvelle attribution d’un individu, et non après l’attribution de tous les individus à tous les centroïdes.La première opération, étape 0), consiste à choisir un nombre de groupes m. Ensuite, les m centres provisoires sont positionnés aléatoirement, bien que souvent sélectionnés parmi les individus. Puis, l’algorithme se poursuit itérativement :), une matrice de dissimilarités quidoivent être euclidiennes carrées , les étapes sont un peu différentes. Lors de l’initialisation, soit lors de l’étape 0), on commence par décider d’un nombre de groupes m, comme dans la version « ordinaire » de l’algorithme. Puis, une matrice d’appartenance dure Z de taille n × m est créée,où chaque individu est attribué aléatoirement à un des m groupes (d’autres variantes existent). À ce stade, on décide d’opérer deux vérifications supplémentaires pour effectivement avoir m groupes à la fin des itérations. Premièrement, on contrôle qu’aucun groupe ne soit vide et on réinitialise la procédure avec une nouvelle matrice Z le cas échéant. Deuxièmement, on vérifie qu’il n’y ait pas une configuration des positions des centroïdes particulière qui engendrerait la disparition d’un ou plusieurs groupes au premier tour d’itération. Pour ce faire, une première itération est exécutée et si l’un des groupes disparaît, la matrice Z est recréée. Pendant cette étape d’initialisation, on calcule aussi la matrice des dissimilarités euclidiennes carrées D =D = ϕ(D). Comme déjà mentionné, la seule transformation utilisée dans ce travail est celle de la puissance (1.22).

Les étapes de l’algorithme K-means flou sont presque identiques à celles de l’algorithme K- means présenté ci-dessus. Une première différence est qu’à l’étape 0), au lieu de créer une matrice d’appartenance dure, on décide de créer un matrice d’appartenance Z floue. Pour ce faire, une matrice de taille n × m est créée avec des valeurs aléatoires extraites d’une loi uniforme etEnsuite, une étape supplémentaire d’agrégation entre les groupes dont les profils sont assez similaires est effectuée, soit l’étape 4), réduisant le nombre de groupes de m à M . En effet, la valeur de β contrôle l’étendue moyenne de chaque groupe et donc le nombre de groupes final M . Ainsi, avec m ≤ n choisi assez grand, le nombre de groupes est indirectement, mais entièrement,Pour la classification supervisée (classification en anglais), on dispose d’un ensemble de données (échantillon d’objets ou d’individus) dont on connaît les profils ou caractéristiques, ainsi que le groupe (ou classe ou étiquette) de chaque individu. Dans un premier temps (phase d’apprentissage), l’algorithme « apprend » des règles sur l’ensemble des données. Ensuite (phase de test), on soumet de nouvelles données à l’algorithme, sans lui spécifier les groupes auxquels ces données appartiennent, et il attribue un groupe à chaque donnée selon les règles élaborées durant la phase d’apprentissage. Puisque l’on connaît les groupes auxquels les nouvelles données appartiennent, la phase de test permet de vérifier si l’algorithme fonctionne correctement ou, en d’autres termes, sa capacité à produire des règles généralisables.