Segmentation des Données

Méthodologie Complète et Métriques de Qualité

Pr. ACHRAF TOUIL

Analyse de Données

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 1 / 25

Plan de la Présentation

1 Introduction

2 Introduction au K-means

3 Distance Euclidienne

4 Algorithme K-means

5 Métriques de Qualité

6 Conclusions

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 2 / 25

Objectif de la Segmentation

Définition
Découvrir des structures cachées dans
des données non étiquetées
Apprentissage non supervisé
Identifier un nombre fini de groupes
(clusters) C1 , C2 , . . . , Ck

Objectifs
A. Objets dans le même cluster Ci : aussi
similaires que possible
B. Objets de clusters différents Ci , Cj
(i ̸= j) : aussi différents que possible

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 3 / 25

Applications de la Segmentation

Méthodes Principales
K-means
Clustering Hiérarchique
DBSCAN

Domaines d’Application
Segmentation de clients
Recherche de molécules
Détection d’anomalies
Compression d’images

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 4 / 25

Concept de K-means : Objectif
L’algorithme K-means est une méthode de partitionnement qui divise n observations en k
groupes (clusters) où chaque observation appartient au cluster dont la moyenne est la plus
proche.

k X
X
argmin ∥x − µi ∥2
C i=1 x∈Ci

où Ci représente le i-ème cluster et µi son centroı̈de.

Dataset Exemple : 6 Clients
Client Âge Revenu Client Âge Revenu
P1 0.2 2.5 P4 0.7 4.2
P2 0.3 2.8 P5 0.9 4.8
P3 0.8 4.5 P6 0.1 2.3

(Âge normalisé, Revenu en milliers d’euros)

Concept de K-means : Structure Globale

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 6 / 25

Concept de K-means : Initialisation

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 7 / 25

Concept de K-means : Affectation & Mise-à-jour des centroides

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 8 / 25

Concept de K-means : Mise-à-jour des centroides

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 9 / 25

Concept de K-means : Convergence

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 10 / 25

Calcul de Distance pour les Attributs Numériques
Pour deux objets x = (x1 , x2 , · · · , xd ) et y = (y1 , y2 , · · · , yd ) :
Lp -Metric (Minkowski-Distance)
v
u d
uX
p
dist(x, y ) = t |xi − yi |p
i=1

Euclidean Distance (p = 2)
v
u d
uX
dist(x, y ) = t (xi − yi )2
i=1

Manhattan-Distance (p = 1)
d
X
dist(x, y ) = |xi − yi |
i=1

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 11 / 25

Distance Euclidienne : Formule et Exemple

Calcul : P1 vers P3
Formule Générale P1 = (0.2, 2.5), P3 = (0.8, 4.5)
Pour deux points x = (x1 , x2 ) et Étape 1 : Différences
y = (y1 , y2 ) :
q ∆1 = 0.2 − 0.8 = −0.6
d(x, y ) = (x1 − y1 )2 + (x2 − y2 )2 ∆2 = 2.5 − 4.5 = −2.0

Étape 2 : Carrés et somme

Propriétés
d(x, y ) ≥ 0 0.36 + 4.00 = 4.36
d(x, y ) = 0 ⇔ x = y
Étape 3 : Racine carrée
Distance plus petite = plus similaire
√
4.36 = 2.09

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 12 / 25

Itération K-means : Initialisation et Affectation

Étape 1 : Initialisation (k=2) Tableau des Distances

Sélection aléatoire :
Point vers C1 vers C2 Cluster
C1 = P1 = (0.2, 2.5)
P1 0.00 2.09 C1
C2 = P3 = (0.8, 4.5) P2 0.32 1.77 C1
P3 2.09 0.00 C2
P4 1.91 0.32 C2
Étape 2 : Calcul des Distances P5 2.50 0.32 C2
Pour chaque point, calculer la distance aux P6 0.22 2.32 C1
deux centroı̈des

Résultat
C1 = {P1, P2, P6} (3 points) — C2 = {P3, P4, P5} (3 points)

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 13 / 25

Itération K-means : Mise à Jour des Centroı̈des

Calcul du Nouveau C1 Calcul du Nouveau C2

Cluster C1 = {P1, P2, P6} Cluster C2 = {P3, P4, P5}
Coordonnée Âge : Coordonnée Âge :

(1) 0.2 + 0.3 + 0.1 (1) 0.8 + 0.7 + 0.9

µ1 = = 0.20 µ2 = = 0.80
3 3
Coordonnée Revenu : Coordonnée Revenu :
(2) 2.5 + 2.8 + 2.3 (2) 4.5 + 4.2 + 4.8
µ1 = = 2.53 µ2 = = 4.50
3 3
Nouveau C1 = (0.20, 2.53) Nouveau C2 = (0.80, 4.50)

Vérification de Convergence
Calculer le déplacement des centroı̈des. Si significatif → répéter l’affectation
Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 14 / 25
Indice de Silhouette : Définition
Formule de la Métrique de Qualité
Pour chaque point i :

b(i) − a(i)
s(i) = où − 1 ≤ s(i) ≤ 1
max(a(i), b(i))

Composantes Interprétation
a(i) : Distance moyenne aux points du même s(i) ≈ 1 : Bien clusterisé
cluster (cohésion)
s(i) ≈ 0 : Sur la frontière
b(i) : Distance moyenne aux points du
cluster voisin le plus proche (séparation) s(i) < 0 : Mal classé

Silhouette Globale
1 Pn
sC = n i=1 s(i) — sC ≥ 0.7 : Fort, sC ≥ 0.5 : Raisonnable
Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 15 / 25
Qualité de la Segmentation

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 16 / 25

Qualité de la Segmentation

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 17 / 25

Qualité de la Segmentation

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 18 / 25

Qualité de la Segmentation

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 19 / 25

Calcul de Silhouette : P1 dans Cluster C1 = {P1, P2, P6}
Étape 1 : Calculer a(P1) (cohésion intra-cluster)
Autres points dans C1 : P2, P6 → d(P1, P2) = 0.32, d(P1, P6) = 0.28
0.32+0.28
a(P1) = 2 = 0.30
Étape 2 : Calculer b(P1) (séparation inter-cluster)
Cluster le plus proche : C2 = {P3, P4, P5}
Distances : d(P1, P3) = 2.36, d(P1, P4) = 2.06, d(P1, P5) = 2.67
2.36+2.06+2.67
b(P1) = 3 = 2.36
Étape 3 : Appliquer la formule

b(P1) − a(P1) 2.36 − 0.30

s(P1) = = = 0.87
max(a(P1), b(P1)) 2.36

Interprétation
s(P1) = 0.87 ≈ 1 ⇒ P1 est très bien clusterisé
Calcul de Silhouette : P3 dans Cluster C2 = {P3, P4, P5}
Étape 1 : Calculer a(P3) (cohésion intra-cluster)
Autres points dans C2 : P4, P5 → d(P3, P4) = 0.32, d(P3, P5) = 0.42
0.32+0.42
a(P3) = 2 = 0.37
Étape 2 : Calculer b(P3) (séparation inter-cluster)
Cluster le plus proche : C1 = {P1, P2, P6}
Distances : d(P3, P1) = 2.36, d(P3, P2) = 2.05, d(P3, P6) = 2.62
2.36+2.05+2.62
b(P3) = 3 = 2.34
Étape 3 : Appliquer la formule

b(P3) − a(P3) 2.34 − 0.37

s(P3) = = = 0.84
max(a(P3), b(P3)) 2.34

Interprétation
s(P3) = 0.84 ⇒ P3 est bien clusterisé
Résumé Complet des Résultats

Tous les Scores de Silhouette

Point Cluster a(i) b(i) s(i)
P1 C1 0.30 2.36 0.87
P2 C1 0.43 2.05 0.79 Évaluation
P6 C1 0.28 2.62 0.89 sC = 0.83 > 0.7
⇒ Structure de clusters forte
Moyenne C1 : 0.85
Les deux clusters montrent :
P3 C2 0.37 2.34 0.84
P4 C2 0.48 2.04 0.76
Haute cohésion (faible a(i))
P5 C2 0.42 2.67 0.84 Bonne séparation (élevé b(i))
Moyenne C2 : 0.81

Silhouette Globale : 0.83

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 22 / 25

Points Clés à Retenir

Bonnes Pratiques
Méthodologie Normaliser les données d’abord
1 Distance : Euclidienne Tester plusieurs valeurs de k
qX Utiliser plusieurs exécutions
d= (xi − yi )2
Combiner les métriques :
Silhouette
2 K-means : Itératif
Connaissance du domaine
Affecter au plus proche
Mettre à jour centroı̈des
Répéter jusqu’à stabilité
Applications
3 Évaluer : Plusieurs métriques Segmentation clients
Silhouette Détection d’anomalies
Clustering de documents

Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 23 / 25

Tableau Récapitulatif des Métriques

Critère WCSS (Elbow) Silhouette

Ce qu’elle mesure Compacité intra-cluster Cohésion + Séparation
Plage de valeurs [0, +∞[ [−1, 1]
Meilleure valeur Plus petit Proche de 1
Complexité O(nk) O(n2 )
Visualisation Courbe avec coude Scores individuels + moyenne
Avantage principal Rapide, intuitif Complet, précis
Inconvénient Coude ambigu parfois Coûteux en calcul
Notre résultat (k=2) 3.21 (réduction 74%) 0.83 (structure forte)

Message Final
Pour un clustering robuste, ne pas se fier à une seule métrique. La convergence de plusieurs
métriques renforce la confiance dans le choix de k.
Pr. ACHRAF TOUIL (Analyse de Données) Segmentation K-means 24 / 25
Merci pour votre attention !

Questions ?

Pr. ACHRAF TOUIL

Analyse de Données