CLUSTERING
Objet
Méthodes
La classification hierarchique ascendante
Le partitionnement
Introduction
• Méthodes de l’analyse mutidimentionnelle/multivariée
• Compraison entre les méthodes en composantes
principale et le clustering
• Différentes approche de clustering, dont:
• Classification hierarchique: créer un regroupement hierarchique des
individus selon certains critères (e.g., WARD)
• Partionnement: construire plusieurs partitions puis les évaluer selon
certains critères (e.g. K-mean)
Objet du clustering
Regrouper des individus selon
leur similarité en un nombre fini
de classes.
Métrique de similarité /
dissemblance
Qualité de la partition
Notion de similarité
1- Similarité entre individus:
Distances comme mesure de similarité:
la distance entre deux individus i et j:
d(i, j) =
λ
λ
| xki − xkj |
K
∑
k=1
Cette distance de Minkowski donne :
• λ = 2: distance Euclidienne
• λ=1 distance de Manhattan
0
d(2,1)
)
d(3,1
:
0
d
)2,3(
:
0
:
nd
)1,(
nd
)2,(
...
...
0
⎤
⎥
Publicité
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
Comparaison de deux distances:
Données
Matrice distance:
mesure Euclidienne
Matrice de distance:
Mesure Manhattan
Les deux distances donne des mesures de similarité différentes
Quelle mesure de distance choisir?
Il est préconisé d’utilisé la distance euclidienne pour pouvoir
combiner le clustering avec les méthodes de composantes
principales
2- Similarité entre les groupes:
Pour pouvoir construire un dendogram la similarité ou la dissemblance
entre groupe d’individus devrait être définie.
Lien simple
Lien complet
Définition de similarité entre clusters:
• Lien simple: distance entre les deux points les plus proches dans les
deux groupe A et B
• Le lien complet: la plus grande distance entre un élément de A et un
élément de B.
Cette définition de mesure de similarité peut être appliquée
pour toute les mesure de distances.
Pour la distance Euclidienne d’autres possibilité sont présentes:
Soient A et B deux groupe d’individus et GA et GB leur centre de gravité et
soit G le centre de gravité de
A ∪ B
La mesure de la similarité/dissemblance entre A et B pourrait se basée sur
l’approche de:
1. Distance: d(GA,GB)
2. Inertie entre cluster: de {GA,GB} par rapport à G
Classification hiérarchique ascendante
C’est une méthode dont l’objet est de
construire un arbre hiérarchique
(dendrogram) représentant le lien entre
les individus: visualiser la variabilité
contenue dans les données.
Chaque branche de l’arbre regroupe
les individus d’un groupe polythétique:
1. Chaque élément du groupe
possède un grand nombre de
Publicité
caractéristiques
2. Chaque caractéristique est
possédée par un grand nombre
d’individus au sein du groupe
Exemple de regroupement de
cinq individus par rapport à la
distance Euclidienne (index)
Index de hiérarchisation:
Le regroupement de individus se fait par rapport à un critère (index) spécifique
choisi d’avance.
I. Algorithme d'agglomération classique: Indice de distance:
1. Calculer la matrice de distance D
2. Regrouper les individu i et j les plus proche; un nouvel élément (i,j) est
créé;
3. Mettre à jour D en enlevant les colonnes et les lignes relatives à i et j
et les remplaçant par une ligne et une colonne pour le nouveau
élément (i,j); on obtient une nouvelle matrice D1
4. Refaire à partir de l’étape 2 la même procédure sur la nouvelle
matrice.
Source: François Husson “Classification ascendante hiérarchique (CAH)”
Hiérarchie et partition:
Chaque arbre hiérarchique peut être
considéré comme une séquence de
partitions imbriquées allant du plus
précis (dans lequel chaque individu est
une classe) au plus général (dans
lequel il n'y a qu'une seule classe).
La coupe en A définit une partition en
deux groupes {1,2,3,4} et {5,6,7,8};
La coupe en B définit une partition
plus précise en quatre groupes {1, 2},
{3, 4}, {5, 6} et {7, 8}.
Par construction, ces partitions sont
imbriquées: chaque cluster de niveau
B est inclus dans le même cluster au
niveau A.
2- Méthode WARD (Ward’s minimum variance method)
A chaque étape du processus, regrouper deux éléments (individus isolés ou
pré-classés) en maximisant la qualité de la partition obtenue: en minimisant
l’inertie intra-classe.
Qualité d’une partition:
Une partition est de bonne qualité ssi:
•
les individus dans chaque cluster sont homogènes (faible variabilité intra-
cluster)
les individus dans différents clusters sont très différents (forte variabilité
entre cluster)
•
Dans un espace Euclidien, on peut appliquer le théorème de Huygens:
Inertie totale = inertie entre cluster + inertie intra-cluster
Pour expliciter cette notion, on écrit la décomposition de Huygens pour le cas d’une
seule variable:
Inertie totale
Inertie inter-classe
Utiliser l’inertie comme mesure de variabilité et comme critère de
Publicité
regroupement, revient à :
Minimiser la variabilité intra-cluster Maximiser la variabilité entre cluster
Ainsi la qualité de partition peut être mesurer par :
Or:
0 <
Inertie int er − cluster
Inertie totale
< 1
Inertie int er − cluster
Inertie totale
∀q xq = x
• Si le rapport tend vers 0, alors ne permet pas de classifier
• Si le rapport tend vers 1, alors possibilité de classsifier
∀q xiq = xq
Regroupement selon l’inertie:
Comment regrouper deux clusters?
On choisit les deux clusters à regrouper tels que la variation
(l’augmentation) de l’inertie intra-cluster est minimisée; ce qui
revient à minimiser la diminution de l’inertie inter-cluster;
Formellement:
Soit les cluster P et Q de centres de gravité Gp et GQ et de
taille IP et IQ respectivement.
Inertie(P) + Inertie(Q) = Inertie(P ∪Q) −
IPIQ
IP + IQ
d 2 (GP, GQ )
La variation de l’inertie suite au regroupement de P et Q est
égale:
Δ(P,Q) =
IPIQ
IP + IQ
d 2 (GP, GQ )
Choisir P et Q tel que
est minimum, revient à choisir les
clusters dont:
Δ(P,Q)
•
les centres de gravité sont les
plus proches
d 2 (GP, GQ ) petite
•
la taille est la plus petite
IPIQ
IP + IQ
est minimale
Partitionnement: K-means methode
18
Soit: la partition des individus à l'étape n de l'algorithme et soit
Pn
Δn =
inertie int er − cluster
inertie totale
P0
1. Etape 0: on considérer une partition en k groupes; le nombre de groupe est
fixé d’avance; on calcule
Publicité
Δ0
A chaque étape n de l’algorithme:
2. on calcule le centre de gravité pour chaque cluster q de
gn (q)
Pn
3. On affecte chaque individus au cluster q dont le centre de gravité est le plus
Δn+1
proche. On obtient une nouvelle partition et on calcule
Pn+1
Δn+1 − Δn > seuil
4. tant que ( càd la partition est meilleure que ) alors on
recommence le processus depuis l’étape 2; sinon la partition est la partiton
optimale
Pn+1
Pn+1
Pn
Exemple d’une partition en trois classes:
19
Etape 0: Choisir au hasard le
centre de classes d’une
partition
Etape1: affecter chaque
individus à la classe don’t le
centre est le plus proche
Etape 3: Déplacer l’ancien
centre vers le nouveau centre
de gravité des nouvelles
classes
Etape 4: réaffecter les individus
aux classe don’t le centre est le
plus proche
Etape 5: rechercher les
nouveaux centres de gravité
Etape 6: recommencer le
processus jusqu’à stabilisation
des centres de gravité
20
Exemple 4: HCPC
Réferences
21
Cette présentation a été largement inspirée par les travaux suivants:
1. Husson, F., Lê, S., & Pagès, J. (2017). Exploratory multivariate analysis by
example using R. Chapman and Hall/CRC.
2. Escofier, B., & Pagès, J. (2008). Analyses factorielles simples et multiples.
Objectifs méthodes et interprétation (pp. 328-p). Dunod.
3. Husson, F., Josse, J., & Pages, J. (2010). Principal component methods-
hierarchical clustering-partitional clustering: why would we need to choose for
visualizing data. Applied Mathematics Department.
4. Pagès, J. (2004). Analyse factorielle de données mixtes. Revue de statistique
appliquée, 52(4), 93-111.