INFa4 - Analyse de Données et

Reconnaissance des Formes

Classifications non supervisées

Emmanuel Dellandréa
[email protected]

Version du 11/09/2023
Plan du cours

§ Introduction
§ Démarche d'une analyse de données
§ Analyses factorielles
§ Analyses en composantes principales (ACP)
§ Analyses factorielles des correspondances binaires (AFC)
§ Analyses factorielles des correspondances multiples (ACM)
§ Classifications non supervisées
§ Méthode des centres mobiles
§ Classification ascendante hiérarchique

2
Classifications non supervisées

§ Introduction
§ Terminologie
§ Les centre mobiles
§ Classification ascendante hiérarchique (CAH)
§ Classification mixte : CAH + centres mobiles
§ Classification et analyse factorielle

3
Introduction
§ Les techniques de classification non supervisée sont
destinées à produire des groupements de lignes ou de
colonnes d’un tableau
§ Le contexte d’utilisation est relativement semblable à celui
des méthodes d’analyse factorielle : analyse d’un grand
tableau de données

4
Introduction
§ On suppose que certains regroupements existent dans les
données
§ On cherche donc à les mettre en évidence par des
représentations des classes d’éléments sous forme de
partitions (ou hiérarchies de partitions)

5
Introduction
§ Il existe plusieurs familles d’algorithmes de classification
§ Les algorithmes construisant directement des partitions comme les
méthodes d’agrégation autour des centres mobiles
§ Les algorithmes ascendants qui procèdent à la construction de
classes par agglomérations successives des objets deux à deux, et
qui fournissent une hiérarchie de partitions des objets
§ Les algorithmes descendants qui procèdent par dichotomies
successives de l’ensemble des objets et qui peuvent également
fournir une hiérarchie de partitions

6
Introduction
§ Ces techniques présentent des avantages différents et
peuvent être utilisées conjointement sous forme de
méthodes hybrides
§ Un des avantages des méthodes de classification est de
mettre en évidence des classes souvent plus faciles à
décrire automatiquement que les axes factoriels
§ La pratique montre que l’on a intérêt à utiliser de façon
conjointe les méthodes factorielles et les méthodes de
classification

7
Classifications non supervisées

§ Introduction
§ Terminologie
§ Les centre mobiles
§ Classification ascendante hiérarchique (CAH)
§ Classification mixte : CAH + centres mobiles
§ Classification et analyse factorielle

8
Partitions
§ Ensemble de parties non vides de l’ensemble des individus,
dont les intersections deux à deux sont vides, et dont la
réunion forme l'univers

" l Î {1, 2, ..., k}, Pl ¹ Æ x

xx
" l , m Î {1,2,..., k }, l ¹ m, Pl  Pm = Æ x x x
k
x x
P =W
l =1
l x x
x

9
Recouvrements
§ Ensemble de parties non vides dont la réunion forme
l'univers

x
" l Î {1, 2, ..., k}, Pl ¹ Æ x x
k
x x x
 Pl = W
l =1 x x
x x

10
Hiérarchies
§ Ensemble de partitions emboîtées
§ Hiérarchie = arbre

h9

x3
h8 x1 x2 x4 x5
h7
h6

x1 x2 x3 x4 x5

11
Pyramides
§ Ensemble de partitions emboîtées, avec la possibilité pour
un élément ou palier, d'appartenir à 2 classes différentes

x1
x2 x5 x8 x9
x4 x6
x3 x7

12
Classifications non supervisées

§ Introduction
§ Terminologie
§ Les centre mobiles
§ Classification ascendante hiérarchique (CAH)
§ Classification mixte : CAH + centres mobiles
§ Classification et analyse factorielle

13
Les centres mobiles
§ C’est la méthode de partitionnement la mieux adaptée aux
vastes ensembles de données
§ Elle est utilisée comme
§ Technique de description et d’analyse
§ Technique de réduction, généralement en association
avec des méthodes d’analyse factorielle

14
Les centres mobiles
§ Bases théoriques de l’algorithme
§ Soit un ensemble I de n individus à partitionner,
caractérisés par p variables
§ On suppose que l’espace Rp est muni d’une distance
appropriée, nommée d (souvent distance euclidienne
usuelle ou distance du χ²)
§ On désire constituer un maximum de q classes
§ L’algorithme procède en m étapes

15
Les centres mobiles
§ Bases théoriques de l’algorithme
§ Etape 0 :
§ On détermine q centres provisoires de classes (par exemple
par un tirage aléatoire des individus)
{C10, …, Ck0, …, Cq0}
§ Ces q centres induisent une première partition P0 de
l’ensemble des I individus en q classes
{I10, …, Ik0, …, Iq0}
§ L’individu i appartient à la classe Ik0 s’il est plus proche de Ck0
que de tous les autres centres

16
Les centres mobiles
§ Bases théoriques de l’algorithme
§ Etape 1 :
§ On détermine q nouveaux centres de classes
{C11, …, Ck1, …, Cq1} en prenant les centres de gravité des
classes qui viennent d’être obtenues : {I10, …, Ik0, …, Iq0}
§ Ces nouveaux centres induisent une nouvelle partition P1 de I
construite selon la même règle que pour P0 :
{I11, …, Ik1, …, Iq1}

17
Les centres mobiles
§ Bases théoriques de l’algorithme
§ Etape m :
§ On détermine q nouveaux centres de classes
{C1m, …, Ckm, …, Cqm} en prenant les centres de gravité des
classes qui obtenues lors de l’étape précédente : {I1m-1, …, Ikm-1,
…, Iqm-1}
§ Ces nouveaux centres induisent une nouvelle partition Pm de I
formée des classes :
{I1m, …, Ikm, …, Iqm}

18
Les centres mobiles
§ Bases théoriques de l’algorithme
§ Le processus se stabilise nécessairement et l’algorithme
s’arrête lorsque deux itérations successives conduisent
à une même partition
§ Deux autres critères d’arrêt peuvent être utilisés
§ La mesure de la variance intra-classe cesse de décroître
§ Un nombre maximal d’itérations a été atteint

19
Les centres mobiles
§ Bases théoriques de l’algorithme
§ La partition obtenue dépend généralement du choix
initial des centres

20
Les centres mobiles : exemple

k1
Y
Choisir 3 k2
centres
de classes
(au hasard)
k3

X
21
Les centres mobiles : exemple

k1
Y

k2
Affecter
chaque point
à la classe
dont le centre
est le plus k3
proche
X
22
Les centres mobiles : exemple

k1 k1
Y

Déplacer k2
chaque centre
de classe vers k3
k2
la moyenne
de chaque k3
classe
X
23
Les centres mobiles : exemple
Réaffecter les
points qui sont
plus proches du
centre d'une k1
autre classe Y

Q : Quels sont
les points qui
changent de
classe? k3
k2

X
24
Les centres mobiles : exemple

k1
Y
R : les trois
points qui
changent k3
de classe k2

X
25
Les centres mobiles : exemple

k1
Y
Re-calculer
les moyennes
des classes k3
k2

X
26
Les centres mobiles : exemple

k1
Y

Déplacer les k2
centres des k3
classes vers
les
moyennes
X
27
Les centres mobiles
§ Il existe plusieurs variantes de l’algorithme des centres
mobiles, dépendant du choix
§ Des distances utilisées
§ Des règles d’affectation
§ Exemple : les nuées dynamiques
§ Les classes ne sont pas caractérisées par un centre de gravité,
mais par un certain nombre d’individus qui constituent un
« noyau »
§ Ce « noyau » a pour certaines utilisations un meilleur pouvoir
descriptif et discriminant qu’un centre ponctuel

28
Classifications non supervisées

§ Introduction
§ Terminologie
§ Les centre mobiles
§ Classification ascendante hiérarchique (CAH)
§ Classification mixte : CAH + centres mobiles
§ Classification et analyse factorielle

29
Classification ascendante
hiérarchique
§ Le principe de cet algorithme est de créer à chaque étape
une partition obtenue en agrégeant deux à deux les
éléments les plus proches
§ Un élément peut désigner un individu, ou un
regroupement d’individus généré par l’algorithme
§ Il existe différentes manières de considérer le nouveau
couple d’éléments agrégés, d’où un nombre important de
variantes de cette technique

30
Classification ascendante
hiérarchique
§ L’algorithme ne fournit pas une partition en q classes d’un
ensemble de n objets, mais une hiérarchie de partitions, se
présentant sous la forme d’arbres (appelés
dendrogrammes) et contenant n-1 partitions
§ L’intérêt de ces arbres est qu’ils peuvent donner une idée
du nombre de classes existant effectivement dans la
population
§ Chaque coupure de l’arbre fournit une partition : plus on
coupe haut, plus le nombre de classes est faible, et moins
les classes sont homogènes

31
Classification ascendante
hiérarchique
§ Dendrogramme

h9

h8
h7
h6

x1 x2 x3 x4 x5

32
Classification ascendante
hiérarchique
§ Critères d’agrégation
§ On suppose que l’ensemble des individus est muni d’une distance
d
§ Lorsqu’un groupe d’individus est constitué, il convient de se
demander sur quelle base on peut calculer une distance entre un
individu et un groupe, ainsi qu’une distance entre deux groupes
§ Ceci revient à définir une stratégie de regroupement, appelée
critères d’agrégation
§ La distance entre groupes pourra généralement se calculer à partir
des distances des différents éléments impliqués dans le groupe

33
Classification ascendante
hiérarchique
§ Critères d’agrégation
§ Les critères les plus usuels sont les suivants
§ Critère du saut minimal
§ Critère du saut maximal
§ Critère de la distance moyenne
§ Critère de la distance moyenne pondérée
§ Critère de Ward

34
Classification ascendante
hiérarchique
§ Critères d’agrégation
§ Critère du saut minimal
§ Soit x, y et z trois objets
§ Les objets x et y sont regroupés en un seul élément noté h
§ Le critère du saut minimal consiste à définir la distance de ce
groupe à z par la plus petite distance des éléments de h à z
d(h,z) = Min{ d(x,z), d(y,z) }

35
Classification ascendante
hiérarchique
§ Critères d’agrégation
§ Critère du saut maximal
§ Soit x, y et z trois objets
§ Les objets x et y sont regroupés en un seul élément noté h
§ Le critère du saut maximal consiste à définir la distance de ce
groupe à z par la plus grande distance des éléments de h à z
d(h,z) = Max{ d(x,z), d(y,z) }

36
Classification ascendante
hiérarchique
§ Critères d’agrégation
§ Critère de la distance moyenne
§ Soit x, y et z trois objets
§ Les objets x et y sont regroupés en un seul élément noté h
§ Le critère de la distance moyenne consiste à définir la distance
de ce groupe à z par la moyenne des distances des éléments
de h à z
d(h,z) = ( d(x,z) + d(y,z) ) / 2

37
Classification ascendante
hiérarchique
§ Critères d’agrégation
§ Critère de la distance moyenne pondérée
§ Soit x, y et z trois objets, x contenant nx éléments et y en
contenant ny
§ Les objets x et y sont regroupés en un seul élément noté h
contenant donc (nx+ ny) éléments
§ Le critère de la distance moyenne pondérée consiste à définir
la distance de ce groupe à z par la distance suivante
d(h,z) = ( nx d(x,z) + ny d(y,z) ) / ( nx + ny )

38
Classification ascendante
hiérarchique
§ Critères d’agrégation
§ Critère de Ward
§ Cette technique d’agrégation, basée sur la variance, cherche à
optimiser à chaque étape, au sens de l’inertie, la partition obtenue
par agrégation de deux éléments
§ En effet, la qualité d’une partition est intuitivement bonne si
§ À l’intérieur de chaque classe, la variance des individus qui la composent
est faible pour chaque variable (inertie intra-classe)
§ La variance entre classes est importante pour chaque variable (inertie
inter-classes)

39
Classification ascendante
hiérarchique
§ Critères d'agrégation
§ Critère de Ward
§ Le théorème de Huygens exprime la décomposition de l’inertie
totale d’une partition par :
Inertie totale = Inertie inter-classes + Inertie intra-classes
§ Puisque l’inertie totale est fixée par les données, cette relation
montre qu’il est équivalent de rechercher une partition
présentant une inertie inter-classes élevée ou une inertie intra-
classe faible

40
Classification ascendante
hiérarchique
§ Critères d’agrégation
§ Critère de Ward
§ A une étape donnée, en agrégeant deux classes, l’inertie intra-
classe est nécessairement plus grande (éventuellement égale)
que celle de la partition obtenue à l’étape précédente
§ L’objectif de ce critère est donc de choisir à chaque étape le
regroupement de classes tel que l’augmentation de l’inertie
intra-classe de la partition soit minimale

41
Classification ascendante
hiérarchique
§ Critères d’agrégation
§ Critère de Ward
§ Soit Ci et Cj les centres de gravités des classes respectives Ii et Ij
§ Soit pi et pj la somme des poids des éléments des classes Ii et Ij
§ On montre que l’augmentation de l’inertie intra-classe due au
regroupement des classes Ii et Ij s’écrit :

pi p j
d (Ii , I j ) = d 2 (Ci , C j )
pi + p j

42
Classification ascendante
hiérarchique
§ Critères d’agrégation
§ Critère de Ward
§ Cette mesure de l’augmentation de l’inertie intra-classe est le critère
à minimiser à chaque étape
§ Elle montre qu’à chaque étape, on regroupe les classes
§ Proches (minimisant la distance d²(Ci,Cj) )
§ De faibles poids (minimisant pi pj / (pi+pj) )

43
Influence du critère
d'agrégation
Tableau des distances
4.5 D
A B C D
A 0 1 3 3.5 3.5
d(A,B) est A
B 1 0 2 4.5 + 3 2.5
la dist min A B
C 3 2 0 2.5 B 2
on aggrège C
D 3.5 4.5 2.5 0 C, D
A avec B

Quelle distance choisir pour d(A+B, C) et pour d(A+B, D)

A+B C D A+B C D A+B C D

A+B 0 2 3.5 A+B 0 3 4.5 A+B 0 2.5 4
C 2 0 2.5 C 3 0 2.5 C 2.5 0 2.5
D 3.5 2.5 0 D 4.5 2.5 0 D 4 2.5 0

Stratégie du saut minimum Stratégie du saut maximum Stratégie de la moyenne

On choisit la distance Min On choisit la distance Max On choisit la distance Moyenne

A B C D A B C D A B C D

44
Classification ascendante
hiérarchique
§ Algorithme de classification
§ Etape 1 : il y a n éléments à classer (les n individus)
§ Etape 2 :
§ On construit la matrice des distances entre les n éléments et
on cherche les deux plus proches, que l’on agrège en un
nouvel élément
§ On obtient une première partition à n-1 classes

45
Classification ascendante
hiérarchique
§ Algorithme de classification
§ Etape 3 :
§ On construit une nouvelle matrice des distances, en calculant les
distances, pour un critère d’agrégation donné, entre le nouvel
élément et les éléments restants (les autres distances sont
inchangées)
§ On cherche à nouveau les deux éléments les plus proches, que l’on
agrège en un nouvel élément
§ On obtient une deuxième partition à n-2 classes, qui englobe la
première

46
Classification ascendante
hiérarchique
§ Algorithme de classification
§ Etape m :
§ On construit une nouvelle matrice des distances
§ Le processus est réitéré jusqu’à n’avoir plus qu’un seul
élément regroupant tous les objets et constituant la dernière
partition
§ Les regroupements successifs peuvent être représentés
par un dendrogramme

47
Classification ascendante
hiérarchique
§ Illustration de l’agglomération progressive des éléments

2
3 1

4
5

48
Classification ascendante
hiérarchique
§ Illustration de l’agglomération progressive des éléments

2
3 1

4
5

49
Classification ascendante
hiérarchique
§ Illustration de l’agglomération progressive des éléments

2
3 1

4
5

50
Classification ascendante
hiérarchique
§ Illustration de l’agglomération progressive des éléments

2
3 1

4
5

51
Classification ascendante
hiérarchique
§ Illustration de l’agglomération progressive des éléments

2
3 1

4
5

52
Classification ascendante
hiérarchique
§ Dendrogramme correspondant à l’agglomération illustrée
précédemment

1 2 5 3 4

53
Classification ascendante
hiérarchique
§ Choix d’une partition à partir du dendrogramme
§ La CAH permet par étapes successives de créer la
hiérarchie de partitions (dendrogramme)
§ Une partition est déterminée par coupure de l’arbre à
un certain niveau d’agrégation

54
Classification ascendante
hiérarchique
§ Choix d’une partition à partir du dendrogramme
§ Le niveau d'agrégation est important
§ Plus les classes sont agrégées avec un faible niveau, plus elles se
ressemblent
§ Les partitions seront prises entre les classes dissemblables (agrégées
avec un fort niveau)

A B CDE A B CDE

Partition à 2 classes Partition à 3 classes

55
Classification ascendante
hiérarchique
§ Choix d’une partition à partir du dendrogramme
§ A toute partie h de la hiérarchie, une valeur numérique
v(h) est associée telle que :
Si h Ì h’ alors v(h) < v(h’)
§ Les valeurs généralement utilisées sont les distances
correspondant à chaque étape d’agrégation
§ Ces valeurs sont appelées indices de niveau

56
Classification ascendante
hiérarchique
§ Choix d’une partition à partir du dendrogramme
§ On représente généralement les indices de niveau par un
diagramme en bâtons
§ Ce diagramme montre l’évolution des valeurs des indices lorsqu’on
passe d’une partition donnée à une partition plus fine
§ L’allure de ce diagramme suggère des niveaux de coupure
privilégiés
§ En effet, une augmentation importante de la valeur de l’indice de
niveau suggère que la nouvelle partition est moins homogène que
la partition de niveau inférieur

57
Classifications non supervisées

§ Introduction
§ Terminologie
§ Les centre mobiles
§ Classification ascendante hiérarchique (CAH)
§ Classification mixte : CAH + centres mobiles
§ Classification et analyse factorielle

58
Classification mixte
§ Les différentes méthodes de classification non supervisée
offrent chacune des avantages et inconvénients
§ La méthode des centres mobiles
§ Avantage : permet d’obtenir une partition sur un ensemble de
données volumineux à un faible coût
§ Inconvénients :
§ La partition obtenue est dépendante des premiers centres choisis
§ Le nombre de classes doit être fixé a priori

59
Classification mixte
§ La méthode de classification ascendante hiérarchique
§ Avantages :
§ Méthode déterministe (donne toujours les mêmes résultats à
partir des mêmes)
§ Donne des indications sur le nombre de classes à retenir
§ Inconvénient :
§ Elle est mal adaptée aux ensembles de données volumineux

60
Classification mixte
§ Il est donc intéressant de combiner ces deux approches
pour obtenir une méthode plus performante
§ La méthode des centres mobiles peut ainsi être utilisée
comme auxiliaire de la méthode de classification
ascendante hiérarchique

61
Classification mixte
§ Principe de l’algorithme
§ Il est composé de trois étapes :
§ Etape 1 : partitionnement initial (méthode des centres
mobiles)
§ Etape 2 : agrégation hiérarchique des classes (CAH)
§ Etape 3 : optimisation de la partition obtenue (méthode des
centres mobiles)

62
Classification mixte
§ Principe de l’algorithme
§ Etape 1 : partitionnement initial
§ Objectif : obtenir rapidement et à faible coût une partition des
n objets en k classes homogènes
§ k doit être plus élevée que le nombre de classes désirées et
plus petit que n
§ Principe : utilisation de la méthode des centres mobiles

63
Classification mixte
§ Principe de l’algorithme
§ Etape 2 : agrégation hiérarchique des classes
§ Une classification ascendante hiérarchique est réalisée
§ Les éléments terminaux de l’arbre sont les k classes de la partition
obtenue précédemment
§ Cette étape permet
§ De reconstituer les classes qui ont été fragmentées
§ D’agréger des éléments dispersés autour de leur centre de gravité
§ L’arbre est construit selon le critère de Ward

64
Classification mixte
§ Principe de l’algorithme
§ Etape 3 : optimisation de la partition obtenue
§ La partition finale est obtenue par coupure de l’arbre
§ L’homogénéité des classes obtenues est optimisée par
réaffectation des objets par la méthode des centres mobiles

65
Classifications non supervisées

§ Introduction
§ Terminologie
§ Les centre mobiles
§ Classification ascendante hiérarchique (CAH)
§ Classification mixte : CAH + centres mobiles
§ Classification et analyse factorielle

66
Classification et analyse
factorielle
§ Les méthodes d’analyse factorielle sont particulièrement
bien adaptées à l’exploration de tableaux de données de
taille importante
§ Elles ne permettent cependant pas toujours de fournir une
visualisation satisfaisante de l’ensemble des données
§ Une seule partie de l’information est représentée
§ Ces représentations sont parfois trop complexes pour être
interprétées facilement

67
Classification et analyse
factorielle
§ Les techniques de classification peuvent ainsi compléter les
résultats d’une analyse factorielle
§ La complémentarité entre l’analyse factorielle et la
classification concerne
§ La compréhension de la structure des données
§ Une aide dans la phase d’interprétation des résultats

68
Classification et analyse
factorielle
§ Principe de la classification mixte
§ Etape 1 : analyse factorielle
§ Etape 2 : classification à partir des facteurs
§ Etape 3 : positionnement des classes dans le plan
factoriel

69
Classification et analyse
factorielle
§ Principe de la classification mixte
§ Etape 1 : analyse factorielle
§ L’analyse factorielle est réalisée à partir des données
§ Elle permet d’obtenir les facteurs qui résument au mieux
l’information contenue dans les données

70
Classification et analyse
factorielle
§ Principe de la classification mixte
§ Etape 2 : classification à partir des facteurs
§ Soit p le nombre de variables
§ L’analyse factorielle permet de mettre en évidence les q
facteurs (q <<p) résumant l’information portée par les p
variables
§ La classification réalisée à partir des q facteurs peut reposer
sur des méthodes de centres mobiles ou de classification
ascendante hiérarchique

71
Classification et analyse
factorielle
§ Principe de la classification mixte
§ Etape 3 : positionnement des classes dans le plan factoriel
§ L’analyse factorielle permet de visualiser les éléments dans un espace
de dimension réduite : les plans factoriels
§ La classification offre la possibilité de projeter les centres des classes
sur ces plans, et d’indiquer également la classe d’appartenance des
éléments (couleurs différentes par exemple)
§ Ainsi, le support visuel permet d’apprécier
§ Les distances entre les classes
§ La densité des classes
§ La dispersion des classes
§ Ces indications permettent donc de valider mutuellement les deux
techniques

72
Références
§ J. P. Fenelon, « Qu'est-ce que l'analyse de données », Ed Lefonen, 1981
§ B. Escoffier, J. Pages, « Analyses factorielles simples et multiples », Ed
Dunod, 1998
§ J. De Lagarde, « Initiation à l'analyse de données », Ed Dunod, 1995
§ G. Govaert, « Analyse des données », Ed Hermes Science, 2003
§ L. Lebart, A. Morineau, M. Piron, « Statistique exploratoire
multidimensionnelle », Ed Dunod, 2004
§ R. Rodriguez Herrera, D. Salles-Le Gac, « Initiation à l'analyse factorielle
des données », Ed Ellipses, 2002
§ A.K. Jain, R.C. Dubes, « Algorithms for clustering data », Prentice Hall
Inc., 1988

73
36, avenue Guy de Collongue 69130 Écully - France
+33 (0)4 72 18 60 00

www.ec-lyon.fr