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.

Méthode de Ward

Type	Algorithme de partitionnement de données (d)

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.

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

Voir aussi

Bibliographie

• Gilbert Saporta, Probabilités, analyse des données et statistiques, Paris, Éditions Technip, 2006, 622 p. (ISBN 978-2-7108-0814-5, lire en ligne).

Articles connexes

Liens internes

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

Liens externes

• Cours d'analyse des données donné à l'Institut d'études politiques de Paris