Méthode de Ward

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

Définitions

Inertie

Si $G=\{e_i:i=\{1:n\}\}$ est un groupe d'individus, de centre de gravité $g$, partitionné en k classes d'effectifs $n_1,n_2,..,n_k$ qu'on appellera $G_1,G_2,..,G_k$ qui ont pour centres de gravité $g_1,g_2,..,g_k$ alors

l'inertie totale du nuage est égale à : $I_t=\frac{1}{n}\sum _{i=1}^{n}d(e_i,g{)}^2$ où d est une distance l'inertie interclasse est égale à : $I_e=\frac{1}{n}\sum _{i=1}^k{n}_i\times d(g_i,g{)}^2$ l'inertie intraclasse est égale à : $I_a=\frac{1}{n}\sum _{i=1}^k\sum _{e\in Gi}d(e,g_i{)}^2$

Méthode

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. En effet, 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. Cette méthode requiert donc un nombre considérable de calculs puisqu’il est nécessaire, à chaque étape, de considérer l’ensemble des possibilités de regroupement.

Algorithmiquement, à chaque étape, il s'agit de 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.

Voir aussi

Bibliographie

• Modèle:Ouvrage

Articles connexes

• Exploration de données
• Statistique multivariée
• Analyse factorielle

Liens externes

• DEA-ÉCO-DÉMO : cours élémentaires d'économétrie et d'analyse des données, donné à l'Institut d'études politiques de Paris