Chapitre 38
Classification ascendante hiérarchique
8.1 Algorithme
Le but de la classification hiérarchique est de fournir une hiérarchie. Il existe deux ap-
proches :
— la classification descendante : on divise successivement ⌦ en deux parties, etc...
— la classification ascendante : on part des singletons qu’on regroupe par deux, etc...
On s’intéressera uniquement à la classification ascendante hiérarchique (CAH). Pour pou-
voir regrouper des parties de ⌦, il faut définir des critères d’agrégation
— distance ou dissimilarité entre les observations
dM (x, y) 2 R+ , x, y 2 ⌦.
— distance ou dissimilarité entre les classes
D(A, B) 2 R+ ,
où A et B sont deux classes et D est une fonction de dM .
On présente maintenant l’algorithme de la CAH
Algorithme 2 : Algorithme de de CAH
Data : x1 , . . . , xn
Initialisation : définir la partition P [0] consistuée des singletons;
for m = 1, . . . , K 1 do
calculer les distances deux à deux entre les classes de la partition P [m 1] à l’aide de
D;
former la partition P [m] en regroupant les deux classes de P [m 1] les plus proches au
sens de D;
end
Result : Hiérarchie indicée
L’algorithme de la CAH fournit une hiérachie indicée où D est l’indice si D est croissante.
69
8.2 Les critères d’agrégation usuels
Définition 8.2.1. Soit A et B deux classes de ⌦, on a les critères d’agrégation suivants :
— critère du saut minimum ("single linkage")
D(A, B) = min{dM (x, y); x 2 A, y 2 B}.
— critère du saut maximum ("complete linkage")
D(A, B) = max{dM (x, y); x 2 A, y 2 B}.
— critère de la distance moyenne ("average linkage")
P P
x2A y2B dM (x, y)
D(A, B) = ,
nA nB
où nA = card(A) et nB = card(B).
— critère de Ward
nA nB 2
D(A, B) = d (µA , µB ),
nA + nB M
P P
µA = n1A x2A x, µB = n1B y2B y.
Notons que les critères du saut minimum et du saut maximum sont plus sensibles aux
observations atypiques car ils ne basent que sur une observation de chaque classe. Nous
donnons maintenant une propriété de la CAH associée au critère de Ward.
Propriété 8.2.1. L’utilisation de l’indice de Ward permet de regrouper, à chaque étape
de l’algorithme de la CAH, les classes dont la fusion permet le plus faible gain d’inertie
intra-classe.
Preuve de la Propriété 8.2.1. Supposons qu’on dispose, à l’itération m, de la partition
P [m] = {P1 , . . . , PK , A, B} et que, sans perte de généralité, on regroupe à l’itération
m + 1 les classes A et B. De sorte que P [m+1] = {P1 , . . . , PK , {A, B}}. On a
K X
X n X X
[m]
W (P )= zik d2M (xi , µk ) + d2M (xi , µA ) + d2M (xi , µB ),
k=1 i=1 i2A i2B
et
K X
X n X
[m+1]
W (P )= zik d2M (xi , µk ) + d2M (xi , µAB ),
k=1 i=1 i2{A,B}
Pn P P
où µk = i=1 zik xi , µA = n1A i2A xi , µB = n1B i2B xi , nA est le nombre d’observations
affectées à la classe A, nB est le nombre d’observations affectées à la classe B, et
1 X nA nB
µAB = xi = µA + µB .
nA + nB nA + nB nA + nB
i2{A,B}
De plus, X X X
d2M (xi , µAB ) = d2M (xi , µAB ) + d2M (xi , µAB ).
i2{A,B} i2A i2B
70
En appliquant le théorème de Huygens, on a
X X
d2M (xi , µAB ) = d2M (xi , µA ) + nA d2M (µA , µAB )
i2A i2A
et X X
d2M (xi , µAB ) = d2M (xi , µA ) + nB d2M (µB , µAB ).
i2B i2B
Ainsi, en notant = W (P [m+1] ) W (P [m] ), on a
= nA d2M (µA , µAB ) + nB d2M (µB , µAB ).
Or
✓ ◆2
nA nB
d2M (µA , µAB ) = µA µA µB
nA + nB nA + nB
✓ ◆2
nB
= (µA µB )
nA + nB
✓ ◆2
nB
= d2M (µA , µB ).
nA + nB
⇣ ⌘2
De la même façon, on a d2M (µB , µAB ) = nA
nA +nB
d2M (µA , µB ). Ainsi
nA n2B + n2A nB 2
= d (µA , µB )
(nA + nB )2 M
nA nB 2
= d (µA , µB ).
nA + nB M
La perte minimale d’inertie inter-classe est donc bien obtenue lorsque l’on minimise le
critère de Ward.
8.3 Exemple d’une CAH sur données réelles
On considère la même problématique sur les températures des villes européennes présentée
dans le Chapitre 7. On commence par vider l’environement de R, puis on charge les
données à partir du fichier csv.
rm(list=ls())
setwd("~/Documents/enseignements/ENSAI/1A/SEM/exemples/data/")
require(FactoMineR)
Loading required package: FactoMineR
71
require(cluster)
Loading required package: cluster
require(VarSelLCM)
Loading required package: VarSelLCM
Attaching package: ’VarSelLCM’
The following object is masked from ’package:stats’:
predict
# Importation des donnees
temperature <- read.table("temperatures.csv",
header = TRUE,
sep = ";",
dec = ".",
row.names = 1)
Nous ne reproduisons pas les statistiques descriptives (voir Chapitre 7). Nous effectuons
le clustering par la méthode de la classification ascendante hiérarchique. Nous conservons
les mêmes élèments actifs que pour l’ACP. Afin de conserver la même métrique, nous
standardisons les données car la fonction agnes de R ne premet pas de spécifier la métrique
(l’argument “metric” permet de déterminer la nature de la distance utilisée). On effectue
la CAH avec le critère de Ward et aussi avec le critère du saut minimum. On constate
que le choix du critère d’agrégation impacte fortement les résultats. Le dendrogramme
associé au saut minimum est caractéristique de celui-ci. Cependant, comme ce critère est
sensible aux valeurs extrêmes, nous analysons les résultas obtenus avec le critère de Ward.
Avec le critère de Ward, 2 ou 3 classes peuvent être sélectionnées. Ici, nous privilégions
une interprétation en 3 classes.
require(cluster)
dataTocluster <- scale(temperature[1:23, 1:12])
res.CAHward <- agnes(dataTocluster, metric = "euclidean", method = "ward")
res.CAHmini <- agnes(dataTocluster, metric = "euclidean", method = "single")
plot(res.CAHward)
72
Banner of agnes(x = dataTocluster, metric = "euclidean", method =
"ward")
Amste
Londr
Dubli
Pragu
Sofia
Copen
Craco
Oslo
Minsk
Reykj
Lisbo
Rome
0 2 4 6 8 10 12 14 16
Height
Agglomerative Coefficient = 0.91
Dendrogram of agnes(x = dataTocluster, metric = "euclidean", method =
"ward")
15
10
5
Height
Reykjavik
0
Athenes
Lisbonne
Budapest
Copenhague
Dublin
Madrid
Rome
Paris
Kiev
Cracovie
Helsinki
Berlin
Minsk
Moscou
Oslo
Stockholm
Londres
Prague
Sarajevo
Sofia
Amsterdam
Bruxelles
dataTocluster
Agglomerative Coefficient = 0.91
plot(res.CAHmini)
Banner of agnes(x = dataTocluster, metric = "euclidean", method =
"single")
Amste
Londr
Dubli
Pragu
Sofia
Kiev
Budap
Oslo
Minsk
Athen
Madri
Reykj
0 0.5 1 1.5 2 2.5 3 3.41
Height
Agglomerative Coefficient = 0.66
73
Dendrogram of agnes(x = dataTocluster, metric = "euclidean", method =
"single")
3.5
Reykjavik
2.5
1.5
Athenes
Height
Lisbonne
Budapest
Madrid
Rome
Copenhague
0.5
Kiev
Dublin
Cracovie
Helsinki
Minsk
Moscou
Paris
Oslo
Stockholm
Berlin
Prague
Londres
Sarajevo
Sofia
Amsterdam
Bruxelles
dataTocluster
Agglomerative Coefficient = 0.66
Nous commençons par comparer les résultats obtenus par les Kmeans à ceux obtenus
par la CAH associée au critère de Ward. Pour cela, nous récupérons la partition de la
CAH en 3 classes par la fonction cutree. On affiche la matrice de confusion entre les
deux partitions ainsi que la valeur du critère ARI. La valeur du critère ARI nous indique
une forte proximitée entre ces deux partitions (on pouvait s’y attendre vu le lien entre le
critère de ward et l’inertie intra-classe). On constate que les deux méthodes identifie une
classe minoritaire identique (composée de 4 capitales située en méditerranée) groupant
les capitales les plus chaudes.
partitionCAH <- cutree(res.CAHward, 3)
res.kmeans <- kmeans(dataTocluster, 3)
table(res.kmeans$cluster, partitionCAH)
partitionCAH
1 2 3
1 0 4 0
2 12 0 0
3 1 0 6
ARI(res.kmeans$cluster, partitionCAH)
[1] 0.8490153
L’interprétation de la partition en 3 issue de la CAH peut se faire à partir de statistiques
calculées classe par classe. L’interprétation est similaire à celle faite pour les K-means.
by(dataTocluster, partitionCAH, colMeans)
INDICES: 1
Janvier Fevrier Mars Avril Mai Juin
0.002065964 0.014499456 0.066940535 0.059441314 0.013708569 -0.099199185
Juillet Aout Septembre Octobre Novembre Decembre
-0.154566129 -0.092949694 -0.020700134 0.016567019 -0.016687638 -0.009417904
------------------------------------------------------------
INDICES: 2
Janvier Fevrier Mars Avril Mai Juin Juillet Aout
1.496258 1.561010 1.567183 1.604964 1.446530 1.540304 1.637635 1.683786
Septembre Octobre Novembre Decembre
74
1.730971 1.689456 1.678195 1.539356
------------------------------------------------------------
INDICES: 3
Janvier Fevrier Mars Avril Mai Juin Juillet
-1.0019817 -1.0720889 -1.1898264 -1.1987653 -0.9940555 -0.8119380 -0.7568631
Aout Septembre Octobre Novembre Decembre
-0.9211327 -1.1091304 -1.1621989 -1.0826402 -1.0058322
75
