En statistique, et plus particulièrement en classification hiérarchique, la méthode de Ward est un algorithme permettant de regrouper deux classes d'une partition pour obtenir une partition plus agrégée.

Méthode de Ward
Type
Algorithme de partitionnement de données (d)Voir et modifier les données sur Wikidata

Définitions

modifier

Inertie

modifier

Si   est un groupe d'individus, de centre de gravité  , partitionné en k classes d'effectifs   qu'on appellera   qui ont pour centres de gravité   alors[i 1]

l'inertie totale du nuage est égale à :  d est une distance
l'inertie interclasse est égale à :  
l'inertie intraclasse est égale à :  

Méthode

modifier

On initialise la méthode avec autant de classes que d’éléments. Chaque classe contient un unique élément. L’inertie inter est donc maximale puisqu’il n’y a pas d’inertie intra. Ensuite, on construit les clusters de manière à minimiser la diminution de l’inertie inter (l’inertie inter ne peut que diminuer lors de regroupements). À chaque étape, les deux éléments ou clusters qui seront fusionnés sont donc ceux qui minimisent la diminution de la variabilité inter : on souhaite en effet que la variabilité inter reste la plus grande possible. D’après le théorème d’Huygens, minimiser l’augmentation de l’inertie intra revient au même. On comprend alors que cette méthode requiert un nombre considérable de calculs puisqu’il est nécessaire, à chaque étape, de considérer l’ensemble des possibilités de regroupement.


Algorithmiquement, voici ce que ça donne :


A chaque étape, tester l’ensemble des regroupements possibles et conserver uniquement l’opération qui minimise le résultat du calcul de suivant :


1.   Déterminer le centre de gravité des clusters existants

2.   Calculer la distance euclidienne entre chaque élément d’un cluster et le centre de gravité de ce cluster

3.   Mettre au carrée l’ensemble de ces distances puis les sommer

4.   Sommer les résultats obtenus en 3 pour l’ensemble des clusters


Progressivement, les objets sont agglomérés les uns un autres en respectant ce critère jusqu’à ce que le nombre de cluster souhaité soit atteint.

Notes et références

modifier

Références

modifier

Ouvrages spécialisés

modifier

Articles publiés sur Internet

modifier
  1. [PDF]Mireille Summa-Gettler, Catherine Pardoux, « La Classification Automatique » (consulté le ).

Voir aussi

modifier

Bibliographie

modifier

Articles connexes

modifier

Liens internes

modifier

Liens externes

modifier