Méthode de Ward
# Méthode de Ward

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.

## 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

$I_{t}={\frac {1}{n}}\sum _{i=1}^{n}d(e_{i},g)^{2}~$

$I_{e}={\frac {1}{n}}\sum _{i=1}^{k}n_{i}\times d(g_{i},g)^{2}$

$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 (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 différences 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.

