Méthode de Ward

Méthode de Ward

Type	Algorithme de partitionnement de données (d)

modifier - modifier le code - modifier Wikidata

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.

Si ${\displaystyle G=\{e_{i}~:~i=\{1:n\}\}}$ est un groupe d'individus, de centre de gravité ${\displaystyle g~}$, partitionné en k classes d'effectifs ${\displaystyle n_{1},~n_{2},~..,~n_{k}}$ qu'on appellera ${\displaystyle G_{1},~G_{2},~..,~G_{k}}$ qui ont pour centres de gravité ${\displaystyle g_{1},~g_{2},~..,~g_{k}}$ alors^{[i 1]}

l'inertie totale du nuage est égale à : ${\displaystyle I_{t}={\frac {1}{n}}\sum _{i=1}^{n}d(e_{i},g)^{2}~}$ où d est une distance

l'inertie interclasse est égale à : ${\displaystyle I_{e}={\frac {1}{n}}\sum _{i=1}^{k}n_{i}\times d(g_{i},g)^{2}}$

l'inertie intraclasse est égale à : ${\displaystyle I_{a}={\frac {1}{n}}\sum _{i=1}^{k}\sum _{e\in Gi}d(e,g_{i})^{2}}$

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.

• 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).

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

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

• Portail des probabilités et de la statistique
• Portail des données