Apprentissage statistique : modélisation
descriptive et introduction aux réseaux de
neurones (RCP208)
Classification automatique
Michel Crucianu
([Link]@[Link])
[Link]
EPN05 Informatique
Conservatoire National des Arts & Métiers, Paris, France
7 novembre 2025
Généralités 1 / 26
Plan du cours
2 Généralités
3 K-means
Initialisation de K-means : K-means++
4 Méthode des k-medoids
5 Validité de la classification
6 Classification ascendante hiérarchique
Généralités 2 / 26
Objectifs de la classification automatique
(cluster analysis, clustering)
Objectif général : répartir un ensemble donné de N observations en groupes
(catégories, classes, taxons, clusters) de façon à regrouper les observations similaires
et à séparer les observations dissimilaires
. .
.................. . .
. ... ..................
. ...
. .
..................
. ...
Partitionnement des données Hiérarchie de groupes (→ divers partitionnements)
Généralités 3 / 26
Caractéristiques et utilisations de la classification automatique
Conditions pour pouvoir parler de classification automatique :
Absence d’informations concernant l’appartenance de certaines données à certaines
« classes » (→ méthodes non supervisées)
Le nombre de groupes recherchés est en général inconnu a priori
Les résultats dépendent fortement de la métrique employée
La validation des résultats est difficile en l’absence de toute référence (supervision)
Utilisations :
Mettre en évidence une structure simple dans un ensemble de données
Résumer un grand ensemble de données par les représentants des groupes (ou
« prototypes »)
Généralités 4 / 26
Typologie des méthodes de classification automatique
Choix méthode ⇐ connaissance des données et de la nature des groupes recherchés
Nature des données : numériques, catégorielles, mixtes
Représentation des données :
Représentation vectorielle → définir centres de gravité, densités, intervalles, différentes
distances ⇒ complexité en général O(N)
Simple : seules sont disponibles les distances entre observations ⇒ complexité ≥ O(N 2 )
Groupes mutuellement exclusifs ou non ?
A quel groupe appartiennent les données entourées ?
Nature des groupes :
Nets : une observation appartient ou n’appartient pas à un groupe
Flous : une observation peut appartenir à différents degrés à plusieurs groupes ⇒
convergence souvent plus robuste de l’algorithme de classification
Groupes flous → nets : chaque observation affectée au groupe auquel elle appartient le plus
Généralités 5 / 26
Typologie des méthodes de classification automatique (2)
Critère de regroupement (définition des groupes) : en général n’est pas explicite !
Généralités 5 / 26
Typologie des méthodes de classification automatique (2)
Critère de regroupement (définition des groupes) : en général n’est pas explicite !
. .
.................. . .
. ... ..................
Ensembles compacts éloignés entre eux :
. ...
. .
..................
. ...
Généralités 5 / 26
Typologie des méthodes de classification automatique (2)
Critère de regroupement (définition des groupes) : en général n’est pas explicite !
. .
.................. . .
. ... ..................
Ensembles compacts éloignés entre eux :
. ...
. .
..................
. ...
.. .
.. ....... .......
... ... .... ..
Ensembles denses séparés par des régions moins denses : .... . ....
............
.
K-means 5 / 26
Plan du cours
2 Généralités
3 K-means
Initialisation de K-means : K-means++
4 Méthode des k-medoids
5 Validité de la classification
6 Classification ascendante hiérarchique
K-means 6 / 26
Centres mobiles : la méthode
Ensemble E de N données décrites par p variables à valeurs dans R
Objectif : répartir les N données en k groupes disjoints E1 , . . . , Ek (inconnus a priori)
en minimisant la somme des inerties intra-classe
k X
d 2 (xi , mj ) (1)
X
φE (C) =
j=1 xi ∈Ej
avec
C = {mj , 1 ≤ j ≤ k} l’ensemble des centres des k groupes
d la distance dans Rp qui définit la nature des dissimilarités
La somme des inerties intra-classe peut s’écrire aussi
d 2 (xl , mC(l) ) (2)
X
φE (C) =
1≤l≤N
où C(l) est l’indice du groupe dont fait partie xl
K-means 7 / 26
Centres mobiles : illustration
(données issues de 7 lois normales bidimensionnelles, classification avec 7 centres)
K-means 8 / 26
Centres mobiles : l’algorithme
Data : Ensemble E = {xi }1≤i≤N de N données de Rp
Result : k groupes (clusters) disjoints E1 , . . . , Ek et ensemble C de leurs centres
1 Initialisation aléatoire des centres mj , 1 ≤ j ≤ k ;
2 while centres non stabilisés do
3 Affectation de chaque donnée au groupe du centre le plus proche ;
4 Remplacement des anciens centres par les centres de gravité des groupes ;
5 end
φE (C) diminue lors de chacune des deux étapes du processus itératif ; comme
φE (C) ≥ 0, le processus itératif doit converger
… mais la solution obtenue sera un minimum local, dépendant de l’initialisation,
souvent beaucoup moins bon que le minimum global
K-means 9 / 26
Centres mobiles : illustration (2)
(résultats avec 3 initialisations différentes)
→ Faire tourner l’algorithme plusieurs fois, à partir d’initialisations aléatoires
différentes, ne garantit pas d’arriver à une bonne solution !
K-means 10 / 26
Centres mobiles : convergence
φE (C) diminue de façon monotone non stricte à chaque étape de chaque itération :
1 Affectation de chaque donnée au groupe du centre le plus proche : xi passe du
groupe de centre mp au groupe de centre mq si d 2 (xi , mp ) > d 2 (xi , mq ), donc
d 2 (xi , mp ) + d 2 (xl , mC(l) ) > d 2 (xi , mq ) + d 2 (xl , mC(l) )
X X
l6=i l6=i
2 Remplacement des anciens centres par les centres de gravité des groupes : si m
e j est
l’ancien centre du groupe j et mj le nouveau, alors
d 2 (xi , m kxi − mj + mj − m
X X
ej) = e j k2
xi ∈Ej xi ∈Ej
kxi − mj k2 + kmj − m e j )T
e j k2 + 2 (mj − m (xi − mj )
X X X
=
xi ∈Ej xi ∈Ej xi ∈Ej
| {z }
=0
kxi − mj k2 = d 2 (xi , mj )
X X
≥
xi ∈Ej xi ∈Ej
K-means 11 / 26
Centres mobiles : convergence (2)
Minimisation itérative d’une fonction de deux variables, différentiable :
Coût
1
4 Minimum global
Minimum local
Contrairement au cas illustré ci-dessus, φE (C) n’est pas différentiable (ni même
continue) par rapport aux mj ⇐ un changement infinitésimal dans la position d’un
centre peut provoquer un changement d’affectation de données aux centres et donc
un changement significatif (non infinitésimal) de la valeur de φE (C)
K-means 12 / 26
K-means : l’algorithme online de [2]
K-means de [2] est une variante online (non batch) de la méthode des centres
mobiles ; souvent, K-means est utilisé comme synonyme des centres mobiles…
Data : Ensemble E de N données de Rp
Result : k groupes (clusters) disjoints E1 , . . . , Ek et ensemble C de leurs centres
1 Initialisation aléatoire des centres mj , 1 ≤ j ≤ k ;
2 Chaque groupe est initialisé avec son centre comme seul membre du groupe ;
3 while centres non stabilisés do
4 Choix aléatoire d’une des données ;
5 Affectation de la donnée au groupe du centre le plus proche ;
6 Recalcul des centres pour le groupe que la donnée vient de rejoindre et celui
qu’elle vient de quitter ;
7 end
Recalcul du centre j rejoint par la donnée i : mj = 1
nj
nj m
(e e j + xi ), avec nj = e
nj + 1
Recalcul du centre l quitté par la donnée i : ml = 1
nl
nl m
(e e l − xi ), avec nl = e
nl − 1
Entre batch et online : à chaque itération un échantillon de b données → mini-batch
K-means Initialisation de K-means : K-means++ 13 / 26
Initialisation K-means : K-means++
Une bonne initialisation de l’algorithme K-means
permet d’obtenir une solution de meilleure qualité et
une convergence plus rapide (avec moins d’itérations) vers cette solution
Parmi les nombreux algorithmes d’initialisation nous considérerons K-means++ [1]
Idée : choisir les centres successivement, suivant une loi non uniforme qui privilégie
les candidats éloignés des centres déjà sélectionnés
Data : Ensemble E de N données de Rp ; nombre souhaité de centres k
Result : C = {cj , 1 ≤ j ≤ k}
1 C ← un x de E choisi au hasard ;
2 while kCk ≤ k do
d 2 (x,C)
3 Sélectionner x ∈ E avec la probabilité φE (C)
;
4 C ← C ∪ {x} ;
5 end
Notations : d 2 (x, C) = minj=1,...,t d 2 (x, cj ), φE (C) = d 2 (x, C)
P
x∈E
K-means Initialisation de K-means : K-means++ 14 / 26
K-means++ : évolution des probabilités
(probabilité de sélection proportionnelle à d 2 (x, C), représentée par la couleur rouge)
Après la sélection d’un point Après la sélection de 2 points
( !) ( !)
−4, 6 −4, 6 2, 15
C= C=
8, 0 8, 0 −3, 45
K-means Initialisation de K-means : K-means++ 15 / 26
K-means++ : évolution des probabilités (2)
(probabilité de sélection proportionnelle à d 2 (x, C), représentée par la couleur rouge)
Après la sélection de 3 points Après la sélection de 4 points
( !) ( !)
−4, 6 2, 15 6, 32 −4, 6 2, 15 6, 32 −8, 37
C= C=
8, 0 −3, 45 8, 22 8, 0 −3, 45 8, 22 −4, 54
K-means Initialisation de K-means : K-means++ 16 / 26
K-means : intérêt et limitations
Intérêt (au-delà de la simplicité) :
Paramètre unique : valeur souhaitée pour le nombre de groupes
Faible complexité moyenne : O(tkN) (avec t le nombre d’itérations)
Limitations et solutions :
Données vectorielles uniquement (pour calculer les moyennes)
→ limitation levée dans des méthodes dérivées (ex. k-medoids)
Classes de forme sphérique (si la distance euclidienne usuelle est employée)
→ pour autres formes, on peut se servir de la distance de Mahalanobis (calculée par classe)
Dépendance des conditions initiales (car convergence vers minimum local)
→ initialisation évoluée (par ex. K-means++)
Sensibilité aux données aberrantes
→ fonctionnelle de coût robuste, estimation robuste des moyennes
Choix a priori difficile du nombre de classes
→ régularisation, sélection de modèle
Méthode des k-medoids 16 / 26
Plan du cours
2 Généralités
3 K-means
Initialisation de K-means : K-means++
4 Méthode des k-medoids
5 Validité de la classification
6 Classification ascendante hiérarchique
Méthode des k-medoids 17 / 26
Méthode des k-medoids
Objectif : traiter des données non vectorielles, pour lesquelles seule une métrique d
est connue, tout en conservant la simplicité des centres mobiles
Medoid d’un groupe = individu le plus « central » du groupe
Le seul changement par rapport à K-means est le remplacement des centres de
gravité par des medoids
A chaque itération :
1 Choix, pour chaque donnée, du medoid mC(l) le plus proche : C(l) = arg minj d(xl , mj )
2 Constitution des groupes : Ej est constitué de tous les xl qui sont plus proches de mj
que de tout autre medoid
3 Recherche des medoids de ces (nouveaux) groupes :
mj = arg minxl ∈Ej xp ∈Ej d(xl , xp )
P
Une initialisation de même nature que K-means++ peut être employée
Robustesse apportée par l’utilisation de medoids plutôt que de centres de gravité
Mais complexité O(N 2 ) !
Validité de la classification 17 / 26
Plan du cours
2 Généralités
3 K-means
Initialisation de K-means : K-means++
4 Méthode des k-medoids
5 Validité de la classification
6 Classification ascendante hiérarchique
Validité de la classification 18 / 26
Choix du nombre de groupes k
1 Méthode du « coude » : graphique des valeurs minimales atteintes par φE (C) pour k
croissant, choix de valeur de k avant un palier
2 Mise de la méthode de classification dans un cadre probabiliste et choix d’un critère
d’information comme AIC (Akaike), BIC (Bayes), etc.
3 Stabilité des résultats : une valeur de k est meilleure si les groupes obtenus sont plus
« stables » à l’initialisation aléatoire (voir par ex. [3])
Validité de la classification 19 / 26
Comparaison de classifications
Deux méthodes différentes, ou deux initialisations différentes pour une même
méthode, produisent (approximativement) les mêmes groupes ?
Construction de classifications « consensuelles »
Évaluation de la stabilité (informe sur l’adéquation de la méthode aux données et
même sur la présence de groupes dans les données)
Parmi les propositions (voir par ex. [5], [4]) :
Indice de Rand ajusté : pour deux classifications C, C 0 ,
n11 nombre de paires qui sont dans un même groupe suivant C et C 0
n00 nombre de paires qui sont dans des groupes différents suivant C et C 0
n10 nombre de paires dans un même groupe suivant C et groupes différents suivant C 0
n01 nombre de paires dans un même groupe suivant C 0 et groupes différents suivant C
2(n11 + n00 ) R − E (R)
R(C, C 0 ) = , 0 ≤ R ≤ 1, Radj (C, C 0 ) =
N(N − 1) max(R) − E (R)
Utilisation de l’indice de Jaccard : I(C, C 0 ) = n +nn11 +n (une classification est
11 10 01
définie comme l’ensemble des paires d’observations qui sont dans un même groupe,
parmi toutes les paires possibles)
Information mutuelle normalisée, etc.
Validité de la classification 20 / 26
Validité de la classification
L’algorithme converge vers un résultat quelles que soient les données, mais quelle est
la validité de ce résultat ?
Principales questions :
Y a-t-il réellement des regroupements « naturels » dans les données ?
Validation externe : les groupes identifiés sont-ils en accord avec nos (éventuelles)
connaissances a priori du problème ?
→ Ces connaissances ne sont pas nécessairement directement exploitables dans une fonctionnelle
à minimiser.
Validation interne : les groupes identifiés sont-ils bien « ajustés » aux données ?
→ Nombreux indices : statistique modifiée de Hubert (alignement entre distance et partition),
indice Davies-Bouldin (rapport des inerties), silhouette, etc. Mais les propriétés des données
(groupes plus ou moins séparables) ont un impact !
Validation relative : les résultats de la méthode A sont-ils meilleurs que les résultats de
la méthode B ?
→ Possibilités de sélection de modèle, utilisant les indices de validation interne (car sur les
mêmes données seul l’ajustement compte), la stabilité (voir par ex. [3]), etc.
Classification ascendante hiérarchique 20 / 26
Plan du cours
2 Généralités
3 K-means
Initialisation de K-means : K-means++
4 Méthode des k-medoids
5 Validité de la classification
6 Classification ascendante hiérarchique
Classification ascendante hiérarchique 21 / 26
Classification ascendante hiérarchique (CAH)
Objectif : obtenir une hiérarchie de groupes, structure plus riche qu’un simple
partitionnement
Permet d’examiner l’ordre des agrégations de groupes, les rapports des similarités
entre groupes, etc.
Classification ascendante : procède par agrégation des données et des groupes
Classification ascendante hiérarchique 22 / 26
CAH : indices d’agrégation
Sur la base de la distance entre données, dX : X × X → R+ , différents indices
d’agrégation peuvent être utilisés pour mesurer la dissimilarité entre groupes :
δs (hp , hq ) = min dX (xi , xj ) δs (hp , hq ) = max dX (xi , xj )
xi ∈hp ,xj ∈hq xi ∈hp ,xj ∈hq
lien minimum (single linkage) lien maximum (complete linkage)
Classification ascendante hiérarchique 23 / 26
CAH : indices d’agrégation (2)
1 khp k · khq k 2
δs (hp , hq ) = dX (xi , xj ) δs (hp , hq ) = dX (mp , mq )
X
khp k · khq k khp k + khq k
xi ∈hp ,xj ∈hq
lien moyen (average linkage) indice de Ward (données vectorielles !)
Classification ascendante hiérarchique 24 / 26
CAH : algorithme, mise en œuvre
Data : Ensemble E de N données de X muni de la distance dX
Result : Hiérarchie de groupes (dendrogramme)
1 Chaque donnée définit un groupe ;
2 while nombre de groupes > 1 do
3 Calcul indices d’agrégation entre tous les groupes issus de l’itération précédente ;
4 Regroupement des 2 groupes ayant la plus petite valeur de l’indice d’agrégation ;
5 end
Complexité algorithmique O(N 2 log N) !
N élevé : application de K-means avec k élevé (mais k N), ensuite application de
la CAH sur les groupes obtenus par K-means
Classification ascendante hiérarchique 25 / 26
CAH : effet des différents indices
Indice du lien minimum :
Permet de s’approcher d’un critère de regroupement basé sur la densité
Peut facilement créer des arbres en escalier, déséquilibrés et peu exploitables :
10 1 3 11
2 5 6 7
4
9
8
1 2 3 4 5 6 7 8
Indice du lien maximum, indice de Ward : tiennent compte de la compacité des
groupes résultants, arbres plus équilibrés
Classification ascendante hiérarchique 26 / 26
Références I
D. Arthur and S. Vassilvitskii.
K-means++ : The advantages of careful seeding.
In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’07,
pages 1027–1035, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics.
J. B. MacQueen.
Some methods for classification and analysis of multivariate observations.
In L. M. L. Cam and J. Neyman, editors, Proc. of the fifth Berkeley Symposium on Mathematical
Statistics and Probability, volume 1, pages 281–297. University of California Press, 1967.
O. Shamir and N. Tishby.
Stability and model selection in k-means clustering.
Machine Learning, 80(2) :213–243, 2010.
N. X. Vinh, J. Epps, and J. Bailey.
Information theoretic measures for clusterings comparison : Variants, properties, normalization and
correction for chance.
J. Mach. Learn. Res., 11 :2837–2854, Dec. 2010.
S. Wagner and D. Wagner.
Comparing Clusterings – An Overview.
Technical Report 2006-04, Universität Karlsruhe (TH), 2007.