Analyse de données : CAH et k-moyennes (k-means)

Classification Ascendante Hiérarchique et

k-moyennes

Angelina Roche

Executive Master Statistique et Big Data

Analyse de données : CAH et k-moyennes (k-means)

Plan du chapitre

Classification ascendante hierarchique

Application

Pour aller plus loin : méthode des k-moyennes et classification mixte

Analyse de données : CAH et k-moyennes (k-means)

Classification non supervisée ou clustering

Objectif
Effectuer un regroupement en k (k << n) groupes de manière à
rassembler dans chaque groupe les individus “les plus semblables”
selon un critère à définir (en général assimilé à une distance).
Analyse de données : CAH et k-moyennes (k-means)

Exemples d’application

Marketing : création de profils clients permettant de cibler les

offres promotionnelles suivant certains critères.
Médias : création de profils utilisateurs permettant de
personnaliser une page web.
Economie : création de profils pays suivant différents critères tels
que
I les échanges économiques,
I le taux d’armement,
I le niveau d’éducation,
I ...
...
Analyse de données : CAH et k-moyennes (k-means)

Classification automatique : objectifs et méthodes

I Méthode générale : Classification des n individus en k

classes telles que :
I l’homogénéité soit maximale à l’intérieur de chaque classe,
I l’hétérogénéité soit maximale d’une classe a l’autre.

I Remarque : les classes et le nombre k de classes sont

inconnus.
Analyse de données : CAH et k-moyennes (k-means)

Classification = partition ?

I On construit des classes disjointes.

I Si tout individu est classé, on aboutit à la notion de partition :

tout individu appartient à une classe et une seule.

I Les éléments d’une même classe sont équivalents et donc

indiscernables. Il suffit alors d’utiliser un représentant pour
chaque classe (par exemple le point moyen) dans la suite des
traitements.
Analyse de données : CAH et k-moyennes (k-means)

Qualité d’une partition : inertie inter et inertie intra

I n individus dans k groupes I1 , . . . , Ik ,
1
Pn
I x̄ : isobarycentre des n individus, x̄ = n i=1 xi ,
I nj : effectif du groupe Ij ,
I Cj : isobarycentre du groupe Ij , Cj = 1
P
nj i∈Ij xi .
I Inertie intra-classe : Somme des inerties des points du groupe Ij
au barycentre Cj .
k
1 XX
Iintra = Iintra (I1 , ..., Ik ) = kxi − Cj k2 .
n
j=1 i∈Ij

I Inertie inter-classe : Inertie des barycentres Cj au barycentre x̄.

k
1X
Iinter = Iinter (I1 , ..., Ik ) = nj kCj − x̄k2 .
n
j=1
Analyse de données : CAH et k-moyennes (k-means)

Qualité d’une partition : inertie totale

I Inertie totale : Inertie des n points au barycentre x̄.

n
1X
IG = kxi − x̄k2 .
n
i=1

I Relation de Huygens : L’inertie totale est la somme des

inerties intra et inter classes.

IG = Iintra + Iinter .
Analyse de données : CAH et k-moyennes (k-means)

Qualité d’une partition : mesure

I Qualité d’une partition :

Iinter
.
IG

I Dépend du nombre d’individus et du nombre de classes.

I 2 cas extrêmes :
I k = n : Iintra ({1}, ..., {n}) = 0 et Iinter ({1}, ..., {n}) = IG .
I k = 1 : Iintra ({1, ..., n}) = IG et Iinter ({1, ..., n}) = 0.
Analyse de données : CAH et k-moyennes (k-means)

Qualité d’une partition 1

1. Illustrations du livre de Lebart, Morineau et Piron, Statistique exploratoire multidimensionnelle

Analyse de données : CAH et k-moyennes (k-means)

Exemple n = 5
Données
1.5
1.0
x2

0.5
0.0

0.0 0.5 1.0

x1
Analyse de données : CAH et k-moyennes (k-means)

Exemple n = 5
Inertie totale
1.5
1.0

Barycentre des points

x2

0.5
0.0

0.0 0.5 1.0

x1
Analyse de données : CAH et k-moyennes (k-means)

Exemple n = 5
Analyse de la partition
1.5

Isobarycentre classe 1
1.0
x2

0.5

Isobarycentre classe 3
0.0

0.0 0.5 1.0

x1
Analyse de données : CAH et k-moyennes (k-means)

Exemple n = 5
Inertie intra
1.5
1.0
x2

0.5
0.0

0.0 0.5 1.0

x1
Analyse de données : CAH et k-moyennes (k-means)

Exemple n = 5
Inertie inter
1.5
1.0
x2

0.5
0.0

0.0 0.5 1.0

x1
Analyse de données : CAH et k-moyennes (k-means)

Partitions optimales
Idée naïve : Rechercher la (ou une partition) maximisant l’inertie
inter-classes Iinter .
Problème : examen de toutes les partitions possibles en k classes
d’un ensemble à n éléments.
Nombre de partitions possibles (nombres de Stirling)
k  
1 X k−j k
S(n, k) = (−1) j n (résultat admis).
k! j
j=0

Cas k = 2 :
S(n, 2) = 2n−1 − 1.

n 2 3 4 5 200 300 400 500

S(n, 2) 1 3 7 15 8,03.1059 1,02.1090 1,29.10120 1,64.10150
Il faudrait donc au moins 1042 ans à un ordinateur de bureau pour calculer
toutes les partitions à 2 éléments d’un ensemble à 200 éléments.
Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Plan

Classification ascendante hierarchique

Application

Pour aller plus loin : méthode des k-moyennes et classification mixte

Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Hiérarchie de Parties
I Une hiérarchie de parties est un ensemble de parties
“emboîtées”.
I Cette représentation traduit la façon dont elles sont
construites :
I soit par réunion successive de parties (ascendante),
I soit par division successive (descendante).

I La relation d’inclusion conduit à une représentation graphique

du type :
Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Représentation graphique

I L’ordre de formation traduit les différents niveaux de

ressemblance entre les parties. On utilise donc cet ordre pour
ordonner le graphique suivant l’axe vertical :
Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Représentation graphique (2)

I On peut aussi utiliser une quantification de la variabilité entre
les parties, appelée souvent indice de diamètre :

I =⇒ hiérarchie indicée.
I Représentation graphique = dendrogramme.
Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Algorithme d’agrégation par critère de Ward

I Principe général : Au départ de l’algorithme, l’inertie inter
classes est maximale (n classes). A la fin, celle-ci est nulle (1
classe).
⇒ On cherche a minimiser à chaque étape la perte d’inertie
inter-classes (ou à minimiser le gain d’inertie intra-classe).

I A chaque étape : On regroupe les 2 classes pour lesquelles la

perte d’inertie inter-classes est minimale. Cela revient à
regrouper les classes j et j 0 pour lesquelles la perte
nj nj 0
∆jj 0 = kCj − Cj 0 k2
nj + nj 0

est minimale.
Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Un exemple simple
I Cinq points dans un plan = 5 classes au départ de l’algorithme
3.0

1 2
2.0

3 5

Iintra = 0
1.0
0.0

4
0 1 2 3 4

I Perte d’inertie inter-classes (×n) = ∆j,j 0 :

Classes {1} {2} {3} {4} {5}
{1} 0 8 0.5 4.5 5
{2} 0 8.5 12.5 1
{3} 0 2 4.5
{4} 0 6.5
I Regroupement 1 et 3 ⇒ nouvelle classe {1, 3}.
Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Un exemple simple (2)

3.0

1 2
C1
2.0

3 5

Iintra = n × 0.5 = 2.5

1.0
0.0

4
0 1 2 3 4

I Perte d’inertie inter-classes (×n) = ∆j,j 0 (arrondi à 0.1) :

Classes {1, 3} {2} {4} {5}
no de classe (j) 1 2 3 4

{1,3} 0 10.8 4.2 6.3

{2} 0 12.5 1
{4} 0 6.5
I Regroupement 2 et 5 ⇒ nouvelle classe {2, 5}.
Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Un exemple simple (3)

3.0

1 2
C1 C3
2.0

3 5

Iintra = 2.5 + 5 × 1 = 7.5

1.0
0.0

4
0 1 2 3 4

I Perte d’inertie inter-classes (×n) = ∆j,j 0 (arrondi à 0.1) :

Classes {1, 3} {2,5} {4}
no de classe (j) 1 2 3

{1,3} 0 12.3 4.2

{2,5} 0 21.7
I Regroupement {1, 3} et 4 ⇒ nouvelle classe {1, 3, 4}.
Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Un exemple simple (4) 3.0

1 2
C3
2.0

3 5
C1

Iintra = 7.5 + 5 × 4.2 = 28.5

1.0
0.0

4
0 1 2 3 4

I Dendrogramme
Cluster Dendrogram
25
20
15
Height

10
5

4
0

dist(cbind(X, Y))^2
hclust (*, "ward.D2")
Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Choix du nombre de classes

I Coupure de l’arbre à un niveau donné de l’indice =⇒ partition.
I La coupure doit se faire :
I après les agrégations correspondant à des valeurs peu élevées
de l’indice,
I avant les agrégations correpondant à des niveaux élevés de
l’indice, qui dissocient les groupes bien distincts dans la
population.
I Règle empirique : sélection d’une coupure lors d’un saut
important de l’indice par inspection visuelle de l’arbre.
I Ce saut traduit le passage brutal entre des classes d’une
certaine homogénéité de l’ensemble à des classes beaucoup
moins homogènes.
I Dans la plupart des cas, il y a plusieurs paliers et donc
plusieurs choix de partitions possibles.
Analyse de données : CAH et k-moyennes (k-means)
Classification ascendante hierarchique

Choix du nombre de classes : R 2

Souvent, plusieurs choix de partitions possibles
=⇒ utilisation d’un critère numérique :
Iinter (I1 , ..., Ik )
R 2 (I1 , ..., Ik ) =
IG

Repérage du point k où il y a rupture de pente dans le R 2 :

Analyse de données : CAH et k-moyennes (k-means)
Application

Plan

Classification ascendante hierarchique

Application

Pour aller plus loin : méthode des k-moyennes et classification mixte

Analyse de données : CAH et k-moyennes (k-means)
Application

Présentation des données

Janv Fevr Mars Avril Mai Juin Juil Aout ...
Bordeaux 5.60 6.60 10.30 12.80 15.80 19.30 20.90 21.00 ...
Brest 6.10 5.80 7.80 9.20 11.60 14.40 15.60 16.00 ...
Clermont 2.60 3.70 7.50 10.30 13.80 17.30 19.40 19.10 ...
Grenoble 1.50 3.20 7.70 10.60 14.50 17.80 20.10 19.50 ...
Lille 2.40 2.90 6.00 8.90 12.40 15.30 17.10 17.10 ...
Lyon 2.10 3.30 7.70 10.90 14.90 18.50 20.70 20.10 ...
Marseille 5.50 6.60 10.00 13.00 16.80 20.80 23.30 22.80 ...
Montpellier 5.60 6.70 9.90 12.80 16.20 20.10 22.70 22.30 ...
Nantes 5.00 5.30 8.40 10.80 13.90 17.20 18.80 18.60 ...
Nice 7.50 8.50 10.80 13.30 16.70 20.10 22.70 22.50 ...
Paris 3.40 4.10 7.60 10.70 14.30 17.50 19.10 18.70 ...
Rennes 4.80 5.30 7.90 10.10 13.10 16.20 17.90 17.80 ...
Strasbourg 0.40 1.50 5.60 9.80 14.00 17.20 19.00 18.30 ...
Toulouse 4.70 5.60 9.20 11.60 14.90 18.70 20.90 20.90 ...
Vichy 2.40 3.40 7.10 9.90 13.60 17.10 19.30 18.80 ...

Températures mensuelles moyennes de 15 villes françaises.

Analyse de données : CAH et k-moyennes (k-means)
Application

Dendrogramme obtenu par la CAH

Cluster Dendrogram
15
10
Height

Brest

Lille

Strasbourg
Nice
0

Paris
Bordeaux

Toulouse

Nantes

Rennes
Marseille

Montpellier

Grenoble

Lyon

Clermont

Vichy
distances
hclust (*, "ward.D2")
Analyse de données : CAH et k-moyennes (k-means)
Application

Evolution de l’inertie en fonction du nombre de groupes

10
8

Iinter
6
Iinter

Iintra

IG
4
2
0

2 4 6 8 10 12 14

nombre de groupes
Analyse de données : CAH et k-moyennes (k-means)
Application

Evolution du critère R 2 (k)

1.0
0.8
0.6
R2

0.4
0.2
0.0

2 4 6 8 10 12 14

nombre de groupes
Analyse de données : CAH et k-moyennes (k-means)
Application

Dendrogramme
Cluster Dendrogram
25
20
15
Height

10
5

Brest

Lille

Strasbourg
Nice
0

Bordeaux

Toulouse

Nantes

Rennes

Paris
Grenoble

Lyon
Marseille

Montpellier

Clermont

Vichy
distances
hclust (*, "ward.D2")
Analyse de données : CAH et k-moyennes (k-means)
Application

Représentation des clusters

Lille
50

Paris
Brest Strasbourg
Rennes
48

Nantes
Latitude

Vichy
46

Clermont Lyon
Grenoble

Bordeaux
44

Toulouse Montpellier Nice

Marseille

-4 -2 0 2 4 6 8

Longitude
Analyse de données : CAH et k-moyennes (k-means)
Application

Analyse de la classification obtenue

Détection des variables liées à la classification (I)
On travaille variable par variable.
Test du rapport de corrélation
Liaison entre une variable quantitative (ici la température moyenne
mensuelle, la longitude,...) x et une variable qualitative (la classe).
Soit Pk 2
2 Variance inter-groupe j=1 nj (Cj − x̄)
η̂ = = Pn 2
Variance totale i=1 (xi − x̄)
avec nj effectif de la classe j, Cj moyenne de la variable dans la
classe j.
On teste :
H0 : les deux variables sont indépendantes contre H1 : les deux
variables sont dépendantes.
Sous H0 , K = (n − k)η̂ 2 /((k − 1)(1 − η̂ 2 )) ∼ Fisher(k − 1, n − k).
Analyse de données : CAH et k-moyennes (k-means)
Application

Analyse de la classification obtenue

Détection des variables liées à la classification (II)
Eta2 P-value
Moye 0.84 1.91e-05
Oct 0.84 1.93e-05
Sept 0.83 2.41e-05
Fevr 0.82 3.10e-05
Mars 0.81 4.33e-05
Janv 0.81 4.44e-05
Nov 0.81 4.96e-05
Avril 0.79 7.89e-05
Dec 0.79 9.32e-05
Aout 0.79 9.50e-05
Juin 0.72 4.41e-04
Mai 0.72 5.21e-04
Juil 0.72 5.29e-04
Ampl 0.65 1.95e-03
Lati 0.64 2.19e-03
Long 0.60 4.00e-03
Analyse de données : CAH et k-moyennes (k-means)
Application

Analyse de la classification obtenue

Moyenne des variables dans chaque classe

Classe 1 : Bordeaux, Marseille, Montpellier, Nice, Toulouse.

Classe 2 : Brest, Nantes, Rennes.
Classe 3 : Clermont, Grenoble, Lille, Lyon, Paris, Strasbourg, Vichy.

Janv Fevr Mars Avril Mai Juin Juil Aout Sept Oct Nov Dec
1 5.78 6.80 10.04 12.70 16.08 19.80 22.10 21.90 19.28 14.54 9.88 6.66
2 5.30 5.47 8.03 10.03 12.87 15.93 17.43 17.47 15.60 11.93 8.33 5.97
3 2.11 3.16 7.03 10.16 13.93 17.24 19.24 18.80 15.94 10.90 6.36 3.07

Lati Long Moye Ampl

1 43.56 3.37 13.79 16.34
2 47.81 -2.34 11.20 12.37
3 47.05 4.13 10.66 17.13
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Plan

Classification ascendante hierarchique

Application

Pour aller plus loin : méthode des k-moyennes et classification mixte

Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Références

I Algorithme dû principalement à Forgy (1965) : E. Forgy,

Cluster analysis of multivariate data : Efficiency versus
interpretability of classification, Biometrics, 21 :768 :780, 1965
I Prémisses ou variantes : Thorndike (1953), k-means
MacQueen (1967), Ball & Hall (1967)
I Généralisation marquante : Algorithme des nuées dynamiques
proposé par Diday (1971)
I Adapté aux grands ensembles de données :
I traitement séquentiel possible
I ne requiert pas le calcul d’une matrice n × n de distances entre
individus
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Algorithme
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Description de l’algorithme

I On souhaite regrouper X1 , ..., Xn en k classes (k choisi au préalable par

l’utilisateur).
I Etape ` :
n o
(`) (`)
I C1 , . . . , Ck isobarycentres des k classes
n o
(`−1) (`−1)
I1 , . . . , Ik construites à l’étape ` − 1 (à l’étape 1 les
centres sont tirés aléatoirement sans remise parmi
{X1 , ..., Xn }) .
I k nouvelles classes {I1(`) , . . . , Ik(`) } créees en regroupant les
données les plus proches de chaque centre.
I Fin de l’algorithme : l’algorithme converge vers une partition stable. Arrêt
lorsque la partition reste la même, ou lorsque la variance intra-classes ne
décroît plus, ou encore lorsque le nombre maximal d’itérations est atteint.
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Décroissance de l’inertie intra-classe

Théorème
L’inertie intra-classe décroît ou reste stable à chaque itération de
l’algorithme des k-moyennes :
(`) (`) (`+1) (`+1)
Iintra (I1 , ..., Ik ) ≥ Iintra (I1 , ..., Ik ).
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Classes obtenues par la méthode des k-moyennes avec k = 3

kmeans tirage 1

Lille
50

Brest Paris Strasbourg

Rennes
48
Latitude

Nantes
Vichy
46

Clermont Lyon
Grenoble
Bordeaux
44

Toulouse Montpellier Marseille Nice

-4 -2 0 2 4 6 8

Longitude

kmeans tirage 1

Lille
50

Brest Paris Strasbourg

Rennes
48
Latitude

Nantes
Vichy
46

Clermont Lyon
Grenoble
Bordeaux
44

Toulouse Montpellier Marseille Nice

-4 -2 0 2 4 6 8

Longitude

kmeans tirage 1

Lille
50

Brest Paris Strasbourg

Rennes
48
Latitude

Nantes
Vichy
46

Clermont Lyon
Grenoble
Bordeaux
44

Toulouse Montpellier Marseille Nice

-4 -2 0 2 4 6 8

Longitude
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Classes obtenues par la méthode des k-moyennes avec k = 3

Rapport Iinter/IG = 71.9 %

Lille
50

Brest Paris Strasbourg

Rennes
48
Latitude

Nantes
Vichy
46

Clermont Lyon
Grenoble
Bordeaux
44

Toulouse Montpellier Marseille Nice

-4 -2 0 2 4 6 8

Longitude

Rapport Iinter/IG = 69.3 %

Lille
50

Brest Paris Strasbourg

Rennes
48
Latitude

Nantes
Vichy
46

Clermont Lyon
Grenoble
Bordeaux
44

Toulouse Montpellier Marseille Nice

-4 -2 0 2 4 6 8

Longitude

Rapport Iinter/IG = 78.7 %

Lille
50

Brest Paris Strasbourg

Rennes
48
Latitude

Nantes
Vichy
46

Clermont Lyon
Grenoble
Bordeaux
44

Toulouse Montpellier Marseille Nice

-4 -2 0 2 4 6 8

Longitude
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Classes obtenues par la méthode des k-moyennes avec k = 3

Rapport Iinter/IG = 71.9 %

Lille
50

Brest Paris Strasbourg

Rennes
48
Latitude

Nantes
Vichy
46

Clermont Lyon
Grenoble
Bordeaux
44

Toulouse Montpellier Marseille Nice

-4 -2 0 2 4 6 8

Longitude

Rapport Iinter/IG = 69.3 %

Lille
50

Brest Paris Strasbourg

Rennes
48
Latitude

Nantes
Vichy
46

Clermont Lyon
Grenoble
Bordeaux
44

Toulouse Montpellier Marseille Nice

-4 -2 0 2 4 6 8

Longitude

Rapport Iinter/IG = 78.7 %

Lille
50

Brest Paris Strasbourg

Rennes
48
Latitude

Nantes
Vichy
46

Clermont Lyon
Grenoble
Bordeaux
44

Toulouse Montpellier Marseille Nice

-4 -2 0 2 4 6 8

Longitude
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Partition finale

Rapport Iinter/IG = 78.7 %

Lille
50

Paris
Brest Strasbourg
Rennes
48

Nantes
Latitude

Vichy
46

Clermont Lyon
Grenoble

Bordeaux
44

Toulouse Montpellier Nice

Marseille

-4 -2 0 2 4 6 8

Longitude
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Atouts et limites des méthodes

I Atouts et limites de la CAH
I Atout :
I Fournit à la fois les classes et leur nombre
I Limites :
I Souvent malaisé de choisir la coupure significative sur le
dendrogramme
I Partition non-optimale en raison de sa structure hiérarchique
I Fort coût algorithmique lorsque n devient grand
I Atouts et limites des centres mobiles
I Atouts :
I Coût algorithmique faible
I Traitement séquentiel
I Limites :
I Nombre de classes fixé a priori
I Partition obtenue fortement dépendante des centres
provisoires des classes
I Idée : Mixer les 2 méthodes (CAH et centres mobiles)
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Classification mixte
I Etape 1 : Partitionnement préliminaire (si n grand)
Partitionnement en q classes, avec n >> q >> k le nombre de
classes final désiré, en utilisant la méthode des centres mobiles
(q ' 10 ou 100)
I Etape 2 : Classification ascendante hiérarchique
CAH sur les q éléments (centres) obtenus à l’étape 1
I Etape 3 : Optimisation
I Partition finale obtenue par coupure de l’arbre de la CAH
I Homogénéité des classes optimisée par réaffectation par la
technique des centres mobiles (consolidation)

I Remarque : Méthode qui peut être instable sur les

échantillons de petite taille.
Analyse de données : CAH et k-moyennes (k-means)
Méthode des k-moyennes et classification mixte

Quelques fonctions R

I Pour la CAH : fonction hclust() (voir help(hclust)).

I Pour les k-moyennes : fonction kmeans().

I Pour l’analyse de la classification : fonction catdes() du

package FactoMineR (voir
[Link]