Apprentissage Statistique

Apprentissage non supervisé

Lucien D. GNING
[email protected]

March 22, 2025

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 1 / 54

Plan

1 Introduction

2 Techniques de réduction de dimension

Analyse en composantes principales (PCA)

3 Clustering
Évaluation d’un algorithme de Clustering
Kmeans Clustering
 1 Introduction

2 Techniques de réduction de dimension

Analyse en composantes principales (PCA)

3 Clustering
Évaluation d’un algorithme de Clustering
Kmeans Clustering

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 3 / 54

 Introduction

Technique destinée à découvrir la structure des données X pour réaliser

des tâches comme :
1 clustering

1 Classifications d’images, de documents, ...

2 Étude de marché
3 Recherche d’information
2 détection d’anomalie
1 Détection de fraude bancaire
2 Détection de défaillance technique
3 Systèmes de sécurité
3 réduction de dimensionnalité
1 Visualisation de données
2 Compression de données
3 Simplification de Dataset

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 4 / 54

 Algorithmes

1 clustering
1 K-means clustering
2 Hierachical clustering
3 Spectral clustering
4 DBSCAN (Density-based spatial clustering of applications with noise)
5 OPTCIS (ordering points to identify the clustering structure)
2 détection d’anomalie
1 Isolation Forest
2 Local Outlier Forest
3 One-class SVM
3 réduction de dimensionnalité
1 Principal composant analysis (PCA)
2 T-SNE (t-distributed stochastic neighbor embedding)
3 Multi-dimensional Scaling (MDS)

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 5 / 54

Introduction
′
1 Données d’apprentissage x = (x1 , . . . , xn ) avec xi ∈ X (quelconque
souvent Rp )
2 Consiste à inférer des connaissances sur les données : sur la seule
base des échantillons d’apprentissage, recherche de structures
naturelles dans les données.
3 Ici pas de variable réponse y !
4 Buts plus flous : description de données, analyse de données
5 Difficulté de l’évaluation du résultat
6 Différent de l’apprentissage supervisé, mais peut être une étape
préliminaire à un apprentissage supervisé
7 Objectif : comprendre les données
8 Trouver des ’clusters’
9 Trouver des tendances fréquentes
10 Trouver des valeurs aberrantes (’outliers’)
11 Modéliser la distribution des données
Introduction
1 Différentes tâches sont associées à l’apprentissage non supervisé
(Clustering, Réduction de dimension, Règle d’association)
2 Règle d’association : analyser les relations entre les variables ou
détecter des associations
3 Quelques bonnes raisons de s’intéresser à l’apprentissage non
supervisé
Profusion d’enregistrements et de variables
Constituer des échantillons d’apprentissage étiquetés peut être très
coûteux
Découvertes sur la structure et la nature des données à travers
l’analyse exploratoire
Utile pour l’étude de caractéristiques pertinentes
Prétraitement avant l’application d’une autre technique de fouille de
données (data mining)
4 On obtient des modèles descriptifs qui permettent mieux connaı̂tre
ses données, de découvrir des informations cachées dans la masse des
données
 Applications

1 analyse des données quand il n’y a pas de connaissance sur la classe

(pas d’étiquetage des données (problème nouveau))
2 trop de données ou étiquetage trop compliqué (traces utilisateur
(web), documents web, parole, etc)
3 réduction de la quantité d’information (quantification)
4 découverte de régularités sur les données ou de similarités

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 8 / 54

 1 Introduction

2 Techniques de réduction de dimension

Analyse en composantes principales (PCA)

3 Clustering
Évaluation d’un algorithme de Clustering
Kmeans Clustering

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 9 / 54

 1 Données représentées sous la forme d’une matrice X de dimension
n × p , où n est le nombre d’observations et p le nombre de variables;
2 p est généralement un nombre assez grand, qui peut aller jusqu’à
plusieurs dizaines de milliers dans certaines applications.
3 C’est le cas par exemple lorsqu’on traite des images en haute
résolution, et que chaque variable représente un pixel de cette image.
4 C’est aussi le cas de l’analyse de données génomiques, où des
centaines de milliers de positions du génome peuvent être
caractérisées.
5 Dans cette partie, nous allons étudier des techniques non-supervisées
permettant de réduire ce nombre de variables.
6 Il s’agira de trouver m variables, avec m < p, que nous allons
choisir d’utiliser pour construire une nouvelle matrice X̃ , de
dimension n × m pour représenter nos données.

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 10 / 54

 Réduire la dimension des données, c’est-à-dire le nombre de variables
utilisées pour les représenter, permet de :
1 Visualiser les données
2 Réduire les coûts (coût en espace mémoire, en temps de calcul, coût
d’acquisition)
3 Améliorer l’apprentissage en construisant des modèles moins
complexes, en éliminant les variables non pertinentes qui pourraient
fausser les prédictions et enfin en réduisant le problème du fléau de la
dimension (le fait que les intuitions développées en faible dimension
ne s’appliquent pas nécessairement en haute dimension. En effet, en
haute dimension, les exemples d’apprentissage ont tendance à tous
être éloignés les uns des autres.)

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 11 / 54

 exemple knn (k− plus proches voisins)

Figure: En utilisant les deux dimensions, les trois plus proches voisins de l’étoile
sont majoritairement des (x). En utilisant seulement la variable en abscisse, ses
trois plus proches voisins sont majoritairement des (+). Si la variable en ordonnée
n’est pas pertinente, elle fausse le résultat de l’algorithme des trois plus proches
voisins.

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 12 / 54

 Techniques de réduction de dimension

Deux possibilités s’offrent à nous pour réduire la dimension de nos données

:
1 la sélection de variables, qui consiste à éliminer un nombre p − m de
variables de nos données ;
2 l’extraction de variables, qui consiste à créer m nouvelles variables à
partir des p variables dont nous disposons initialement.

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 13 / 54

 1 Introduction

2 Techniques de réduction de dimension

Analyse en composantes principales (PCA)

3 Clustering
Évaluation d’un algorithme de Clustering
Kmeans Clustering

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 14 / 54

 Analyse en composantes principales (ACP)

La méthode la plus classique pour réduire la dimension d’un jeu de

données par extraction de variables est l’analyse en composantes
principales, ou ACP. On parle aussi souvent de PCA, de son nom anglais
Principal Component Analysis.
L’ACP permet de dégager rapidement les principales tendances de votre
échantillon, en diminuant le nombre de variables nécessaires à la
représentation de vos données tout en perdant le moins d’informations
possible.
L’ACP permet d’étudier :
1 la variabilité entre les individus, c’est-à-dire quelles sont les différences
et les ressemblances entre les individus ;
2 les liaisons entre les variables : y a-t-il des groupes de variables très
corrélées entre elles qui peuvent être regroupées en de nouvelles
variables synthétiques ?

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 15 / 54

Analyse en composantes principales (ACP)

1 Objectif : Réduire le nombre de dimensions pour représenter les

données tout en minimisant l’information perdue.
2 Principe : Maximiser la variance (inertie) lors de la projection dans le
nouvel espace de représentation.
3 Standardisation des données : centrer et normaliser
Définition
(Analyse en composantes principales) Une analyse en composantes
principales, ou ACP, de la matrice X ∈ Rn×p est une transformation
linéaire orthogonale qui permet d’exprimer X dans une nouvelle base
orthonormée, de sorte que la plus grande variance de X par projection
s’aligne sur le premier axe de cette nouvelle base, la seconde plus grande
variance sur le deuxième axe, et ainsi de suite. Les axes de cette nouvelle
base sont appelés les composantes principales, abrégées en PC pour
Principal Components.
 Analyse en composantes principales
1 Les données sont représentées sous forme de la matrice
 
x11 x12 . . . x1p
x21 x22 . . . x2p 
n×p
X = . ..  ∈ R
 
.. ..
 .. . . . 
xn1 xn2 . . . xnp

Les variables x1 , . . . , xp représentent les colonnes de la matrice X

2 La standardisation est un pré-requis de l’application de l’ACP. Cette
standardisation s’effectue en centrant la moyenne et en réduisant la
variance de chaque variable :
xij − x̄j
xij ← q P
1 n 2
n l=1 (xlj − x̄j )
Pn
où x̄j = l=1 xlj .

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 17 / 54

Analyse en composantes principales
Théorème
′
Soit X ∈ Rn×p une matrice centrée de variance covariance Σ = n1 X X .
Les composantes principales de X sont les vecteurs propres de Σ, ordonnés
par valeur propre décroissante.

Preuve
Commençons par démontrer que, pour tout vecteur w ∈ Rp , la variance de
′
la projection de X sur w vaut w Xw .
La projection de X ∈ Rn×p sur w ∈ Rp est le vecteur z = Xw . Comme X
est centrée, la moyenne de z vaut :
n n p p n
1X 1 XX 1X X
z̄ = zi = xij wj = wj xij = 0.
n n n
i=1 i=1 j=1 j=1 i=1

Sa variance vaut
n
1X 2 1 ′ ′ ′
var(z) = zi = w X Xw = w Σw
n n
i=1
Analyse en composantes principales
(Suite preuve)
Preuve
Appelons maintenant w1 ∈ Rp la première composante principale. w1 est
orthonormé et tel que la variance de Xw1 soit maximale :
′
w1 = argmax w Σw avec ∥w1 ∥2 = 1
w ∈Rp

Il s’agit d’un problème d’optimisation quadratique sous contrainte

d’égalité, que l’on peut résoudre en introduisant le multiplicateur de
Lagrange α1 > 0 et en écrivant le lagrangien
′
L(α1 , w ) = w Σw − α1 (∥w ∥2 − 1)
′
Le maximum de w Σw sous la contrainte ∥w ∥2 = 1 est égal à
min sup L(α1 , w ). Le supremum du lagrangien est atteint en un point où
α1 w ∈Rp
son gradient s’annule, c’est-à-dire qui vérifie

2Σw − 2α1 w = 0
(Suite preuve)
Preuve
Ainsi Σw1 = α1 w1 et (α1 , w1 ) forment un couple (valeur propre, vecteur
propre) de Σ.
Parmi tous les vecteurs propres de Σ, w1 est celui qui maximise la variance
′
w1 Σw1 = α1 ∥w1 ∥2 = α1
Ainsi, α1 est la plus grande valeur propre de Σ (rappelons que Σ étant
′
définie par X X est semi-définie positive et que toutes ses valeurs propres
sont positives.)
La deuxième composante principale de X vérifie :
′ ′
w2 = argmax w Σw avec ∥w2 ∥2 = 1 et w2 w1 = 0.
w ∈Rp

Cette dernière contrainte nous permet de garantir que la base des

composantes principales est orthonormée.
Nous introduisons donc maintenant deux multiplicateurs de Lagrange
α2 > 0 et β2 > 0 et obtenons le lagrangien
′ ′
L(α2 , β2 , w ) = w Σw − α2 (∥w ∥2 − 1) − β2 w w1
Analyse en composantes principales
(Suite preuve)
Preuve
Comme précédemment, son supremum en w est atteint en un point où son
gradient s’annule :
2Σw2 − 2α2 w2 − β2 w1 = 0
′
En multipliant à gauche par w1 , on obtient :
′ ′ ′
2w1 Σw2 − 2α2 w1 w2 − β2 w1 w1 = 0

d’où l’on conclut que β2 = 0 et, en remplaçant dans l’équation précédente,

que, comme pour w1 , 2Σw2 − 2α2 w2 = 0. Ainsi (α2 , w2 ) forment un
couple (valeur propre, vecteur propre) de Σ et α2 est maximale : il s’agit
donc nécessairement de la deuxième valeur propre de Σ.
Le raisonnement se poursuit de la même manière pour les composantes
principales suivantes.
 Décomposition en valeurs singulières (SVD)

Théorème
′
Si l’on écrit X sous la forme UDV où U ∈ Rn×n , V ∈ Rp×p et D ∈ Rn×p
est diagonale, alors
′ ′ ′ ′
Σ = X X = VDU UDV = VD 2 V

et les valeurs singulières de X (les entrées de D) sont les racines carrées

des valeurs propres de Σ, tandis que les vecteurs singuliers à droite de X
(les colonnes de V ) sont les vecteurs propres de Σ.

En pratique, les implémentations de la décomposition en valeurs

singulières (ou SVD) sont numériquement plus stables que celles de
décomposition spectrale. On préférera donc calculer les composantes
principales de X en calculant la SVD de X plutôt que la décomposition
′
spectrale de X X .

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 22 / 54

 Choix du nombre de composantes principales

1 Réduire la dimension des données par une ACP implique de choisir un

nombre de composantes principales à conserver. Pour ce faire, on
utilise la proportion de variance expliquée par ces composantes : la
variance de X s’exprime comme la trace de Σ, qui est elle-même la
somme de ses valeurs propres.
2 Ainsi, si l’on décide de conserver les m premières composantes
principales de X , la proportion de variance qu’elles expliquent est :
α1 + α1 + . . . αm
Tr (Σ)

où α1 ≥ α2 ≥ . . . ≥ αp sont les valeurs propres de Σ par ordre

décroissant.

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 23 / 54

 Choix du nombre de composantes principales
Il est classique de s’intéresser à l’évolution, avec le nombre de
composantes, soit de la proportion de variance expliquée par chacune
d’entre elles, soit à cette proportion cumulée, que l’on peut représenter
visuellement sur la figure suivante.

Figure: Pour choisir le nombre de composantes principales, on utilise le

pourcentage de variance expliquée.

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 24 / 54

 Analyse en composantes principales

Exemple pratique de PCA sous Python

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 25 / 54

 1 Introduction

2 Techniques de réduction de dimension

Analyse en composantes principales (PCA)

3 Clustering
Évaluation d’un algorithme de Clustering
Kmeans Clustering

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 26 / 54

 Plusieurs approches

1 Partitionnement : Construire plusieurs partitions puis les évaluer selon

certains critères.
2 Hiérarchique : Créer une décomposition hiérarchique des objets selon
certains critères.
3 Densité : basée sur une fonction de densité ou de connectivité
4 Grille : basée sur une structure de granularité à plusieurs niveaux
5 Algorithmes à modèles : Un modèle est supposé pour chaque cluster.
Puis vérifier chaque modèle sur chaque groupe pour choisir le meilleur.

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 27 / 54

Pourquoi partitionner ?
Les algorithmes de partitionnement de données permettent :
1 d’effectuer une analyse exploratoire sur des données non étiquetées
2 d’identifier des utilisateurs qui ont des comportements similaires
(segmentation de marché)
3 d’identifier des communautés sur un réseau social
4 d’identifier des motifs récurrents dans des transactions financières,
5 d’identifier des pixels d’un même objet dans une image (segmentation
d’image)
6 d’identifier des patients dont la maladie s’explique par un même profil
génétique.
7 Ils permettent aussi de visualiser les données, en se contentant de
regarder un exemple représentatif par cluster.
8 de transférer à toutes les observations du même cluster les propriétés
que l’on sait vraies de l’un des éléments de ce cluster. Cela est
particulièrement utile dans le cas où l’étiquetage des données est
difficile ou coûteux.
 Qu’est-ce que le clustering ?

1 Regroupement (Clustering): construire une collection d’objets

similaires au sein d’un même groupe (cluster) et dissimilaires quand
ils appartiennent à des groupes différents.
2 Le Clustering est de la classification non supervisée : pas de classes
prédéfinies
3 Les méthodes d’analyse de clusters sont des algorithmes
non-supervisés, ils permettent de générer et de trouver des classes
naturelles.
4 La qualité d’un regroupement dépend donc de la mesure de similarité
utilisée par la méthode et de son implémentation.
5 La qualité d’une méthode peut aussi être mesurée par sa capacité à
identifier certains groupes ou bien tous les groupes intéressants

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 29 / 54

 Propriétés d’un cluster

Les deux propriétés importantes définissant un cluster pertinent sont :

1 sa cohésion interne (que les objets appartenant à ce cluster soient les
plus similaires possibles)
2 son isolation externe (que les objets appartenant aux autres clusters
soient les plus éloignés possible).

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 30 / 54

 Similarité et dissimilarité

1 Similarité
Mesure numérique de à quel point deux objets (individus) sont
similaires
Plus ils se ressemblent, plus la valeur est élevée
Généralement dans [0, 1]
2 Dissimilarité (distance)
Mesure numérique de à quel point deux objets sont différent
Plus ils se ressemblent, plus la valeur est faible
Minimum 0 (identique), maximum variable

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 31 / 54

Similarité et dissimilarité
1 Les données sont représentées sous forme de la matrice
 
x11 x12 . . . x1p
x21 x22 . . . x2p 
n×p
X = . ..  ∈ R
 
.. ..
 .. . . . 
xn1 xn2 . . . xnp
′
On note x i = (xi1 , . . . , xip ) ∈ Rp la i ème ligne de X .
2 On peut créer une matrice de dissimilarité. d(i, j) : représente la
différence entre la ligne (objet, individu) i et la ligne j.
 
0 ... ... ... ...
d(2, 1) 0 ... ... ... 
 
d(3, 1) d(3, 2) 0 ... ... 
  ∈ Rn×n
 .. .. .. .. .. 
 . . . . . 
d(n, 1) d(n, 2) . . . d(n, n − 1) 0
3 Comment calculer d(i, j) ?
 Choix de la distance

La mesure de distance dépend du type de variables

1 Binaire
2 Nominal
3 Numérique
4 Ordinal
5 Mixte
Propriétés d’une distance
1 d(x, y ) ≥ 0
2 d(x, y ) = 0 ⇔ x = y
3 d(x, y ) = d(y , x) (symétrie)
4 d(x, y ) ≤ d(x, z) + d(z, y ) (inégalité triangulaire)

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 33 / 54

 Dissimilarité d’attributs nominaux

1 Attributs descriptifs qualitatifs sans valeurs quantitatives

Aucun ordre dans les valeurs, aucune façon de quantifier les niveaux de
différences
La seule mesure possible: ”est-ce la même valeur?”
2 Matrice de dissimilarité binaire:
1 si les attributs ont des valeurs différentes
0 si les attributs ont la même valeur
3 Si les objets ont plusieurs attributs nominaux, on peut calculer le ratio
de disparité
P est le nombre total d’attributs nominaux
mi,j est le nombre d’attributs nominaux pour lesquels les objets i et j
ont la même valeur
P − mi,j
d(i, j) =
P

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 34 / 54

 Dissimilarité d’attributs nominaux

Exercice

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 35 / 54

 Dissimilarité d’attributs nominaux

1 Calculer le nombre de PP, PN, NP et NN sur tous les attributs

binaires

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 36 / 54

 Dissimilarité d’attributs binaires

1 Attributs symétriques (Positif et négatif sont également important)

PN + NP
d(i, j) =
PP + PN + NP + NN

2 Attributs asymétriques (Positif est important, NN est trivial)

PN + NP
d(i, j) =
PP + PN + NP

Coefficient de Jaccard
PP
sim(i, j) = 1 − d(i, j) =
PP + PN + NP

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 37 / 54

 Dissimilarité d’attributs binaires

Exercice

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 38 / 54

Dissimilarité d’attributs numériques
1 Attributs avec valeurs quantitatives
On n’est plus limité à ”sont-ils différent ou non”
On peut mesurer à quel point ils sont différent
2 Distance de Minkowski
p
X 1/q
d(i, j) = ∥x i − x j ∥q = q
|xik − xjk |
k=1

3 Distance de Manhattan (q=1)

p
X 
d(i, j) = ∥x i − x j ∥1 = |xik − xjk |
k=1

4 Distance euclidienne (q=2)

p
X 1/2
d(i, j) = ∥x i − x j ∥2 = |xik − xjk | 2

k=1
5 Distance de Tchebychev (Chebyshev, supremum)
d(i, j) = max |xik − xjk |
k∈[1,p]
Dissimilarité d’attributs numériques

Exercice

Figure: Exemple illustratif pour le calcul de distance

1 Calculer les distances (euclidienne) entre ces individus.

2 Convertir la variable taille en cm et refaire le calcul des distances.
Remarque ?
3 Standardiser les données et refaire les calculs
Dissimilarité d’attributs ordinaux
1 Catégories ordonnées : froid, tiède, chaud
2 Possible d’avoir un ordre relatif
Froid est plus dissimilaire à chaud qu’à tiède
Impossible de mesurer exactement la différence
3 Solution: quantifier les catégories
froid, tiède, chaud → 0, 0.5, 1.0
Ensuite, traiter comme des attributs numériques
4 Utiliser une échelle normalisée à [0.0, 1.0] : Évite qu’un attribut avec
plus de catégories soit numériquement plus important.
5 Exemple normalisé :
froid, tiède, chaud → 0, 0.5, 1.0
glacial, froid, frais, tiède, chaud, brûlant → 0.0, 0.2, 0.4, 0.6, 0.8, 1
6 Exemple non normalisé :
froid, tiède, chaud → 0, 1, 2
glacial, froid, frais, tiède, chaud, brûlant → 0, 1, 2, 3, 4, 5
7 Valeur max de la 2ème échelle est 2.5 fois plus grand que la première
échelle
 Dissimilarité d’attributs ordinaux

Exemple :
1 Qualité : ok, bon, excellent
2 Évaluation : *,**,***,****
3 Distance euclidenne

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 42 / 54

Dissimilarité d’attributs mixtes
1 Les objets ont des attributs de plusieurs types différents
2 Besoin d’une mesure de dissimilarité globale
3 Dissimilarité de deux objets i et j avec p attributs :
Pp (f ) (f )
f =1 δij d (i, j)
d(i, j) = Pp (f )
f =1 δij

4 δ (f ) détermine si l’attribut doit être compté


0 si xif ou xjf manque,

(f )
δij = 0 si xif = xjf = 0 et f est binaire asymétrique

1, sinon


5 d (f ) (i, j) doit être normalisé à [0, 1]

Ok pour nominal et binaire
Pour ordinal et numérique, diviser chaque attribut par sa distance max
 Dissimilarité d’attributs mixtes

Exercice
1 Prix est numérique (distance de Manhattan)

2 Sujet est nominal

3 Qualité est ordinal (3 catégories)

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 44 / 54

 Dissimilarité : similarité cosinus

1 Utile pour calculer la similarité entre vecteurs d’attributs numériques

et clairsemé (sparse)
2 Matrice creuse (sparse matrix) de grande dimension commune en
données massives
3 Exemple: sac de mots, en traitement du langage naturel

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 45 / 54

 Dissimilarité : similarité cosinus

1
< xi, xj >
sim(i, j) =
∥x i ∥∥x j ∥
où
< x i , x j >= xi1 xj1 + . . . + xip xjp
q
∥x i ∥ = xi1 2 + . . . + x2
ip

2 Valeur dans [0, 1]

3 d(i, j) = 1 − sim(i, j)

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 46 / 54

 1 Introduction

2 Techniques de réduction de dimension

Analyse en composantes principales (PCA)

3 Clustering
Évaluation d’un algorithme de Clustering
Kmeans Clustering

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 47 / 54

Définitions préliminaires
1 Soit D = {x 1 , . . . , x n } le jeu de données non étiquetés de n points
d’un espace X .
2 On veut partitionner nos données en K clusters notés : C1 , . . . , CK
3 On appelle centroı̈de d’un cluster C le point défini par
1 X
µC = x
|C|
x ∈C

4 Le médoı̈de est le point du cluster le plus proche du centroı̈de (il peut

ne pas être unique, auquel cas il sera choisi arbitrairement). Il sert de
représentant du cluster :

mC = argmin d(x , µC )
x ∈C

5 Inertie : on appelle variance intra-cluster, ou inertie du cluster C la

1 P
valeur Varin (C) = |C| x∈C ∥x − µ∥22 . L’inertie globale d’un clustering
de D est alors donnée par la somme des inerties des clusters.
Evaluation d’un algorithme de clustering
1 Homogénéité(tightness) d’un cluster : moyenne des distances de
chacun des points contenus dans ce cluster au centroı̈de
1 X
Tk = d(x, µk )
|Ck |
x∈Ck

Pour caractériser l’ensemble des clusters on peut calculer la moyenne

1 PK
des homogénéités de chaque cluster : T = K k=1 Tk
2 Séparation de deux clusters : la distance entre leurs centroı̈des
Skl = d(µk , µl ). On peut calculer la moyenne de ces quantités sur
l’ensemble des
PKpairesPKde cluster (k, l) obtenues :
2
S = K (K −1) k=1 l=k+1 Skl
3 l’indice de Davies-Bouldin d’un cluster regroupe les deux critères
précédents en un seul :
Tk + Tl
Dk = max
k̸=l Skl
on peut calculer un indice de Davies-Bouldin global en moyennant les
indices de Davies-Bouldin de tous les clusters.
Evaluation d’un algorithme de clustering

1 Le coefficient de silhouette s(x) permet d’évaluer si le point x

appartient au ”bon” cluster Ck : est-il proche des points du cluster
auquel il appartient ? Est-il loin des autres points ?

b(x) − a(x)
s(x) =
max(a(x), b(x))

où
1 X 1 X
a(x) = d(u, x), b(x) = min d(u, x)
|Ck | − 1 l̸=k |Cl |
u∈Ck u̸=x u∈Cl

On a −1 ≤ s(x) ≤ 1. s(x) est d’autant plus proche de 1 que

l’assignation de x à son cluster est satisfaisante. Pour évaluer un
clustering, on peut calculer son coefficient de silhouette moyen. Dans
scikit-learn, le coefficient de silhouette se calcule avec
sklearn.metrics.silhouette score.
Evaluation d’un algorithme de clustering
1 Stabilité des clusters : on s’attend à obtenir les mêmes clusters si on
supprime ou perturbe quelques observations, ou en initialisant
différemment l’algorithme de partitionnement. Ce critère peut être
utilisé pour choisir les hyperparamètres de l’algorithme : si on
obtient des clusters très différents pour différentes initialisations de
l’algorithme de partitionnement, cela peut indiquer que les
hyperparamètres sont mal choisis.
2 Les connaissances expert : on dispose d’un jeu de données
partiellement étiqueté par des classes que nous aimerions retrouver
par clustering.
On peut alors évaluer le résultat d’un algorithme de partitionnement
comme on évaluerait celui d’un algorithme de classification
multi-classe.
Des mesures de performance spécifiques comme l’indice de Rand
permettent d’évaluer la concordance de deux partitions du jeu de
données. Vous en trouverez une liste dans scikit-learn.metrics
 1 Introduction

2 Techniques de réduction de dimension

Analyse en composantes principales (PCA)

3 Clustering
Évaluation d’un algorithme de Clustering
Kmeans Clustering

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 52 / 54

K-means
1 Pour un nombre de clusters K fixé, il s’agit alors de trouver
l’affectation des observations à K clusters qui minimise la variance
intra-cluster globale :
K X
X
argmin ∥x − µk ∥22
C1 ,C2 ,...,CK k=1 x∈C
k

où µk est le centroı̈de du cluster CK .

Algorithme
1 Choisir K observations µ1 , µ2 , . . . , µK parmi les n observations, pour
servir de centroı̈des initiaux.
2 Affecter chaque observation xi ∈ D au centroı̈de dont elle est le plus
proche : k(xi ) = argmin ∥xi − µk ∥2 , k(xi ) est l’indice du cluster
k=1,...,K
auquel xi a été assigné.
3 Recalculer les centroı̈des de chaque cluster :
1 X
µk = xi
|Ck |
xi ∈Ck

4 Répéter les opérations 2 − 3 jusqu’à convergence, c’est-à-dire jusqu’à

ce que les affectations ne changent plus.
 Quelques remarque sur le K-means Clustering

1 AVANTAGES
Relativement efficace : complexité O(ntKd) où n est le nombre de
points, d nombre d’attributs, K nombre de clusters et t le nombre
d’itérations.
Termine souvent sur un optimum local. L’optimum global peut être
atteint en utilisant des techniques telles que les algorithmes génétiques

2 FAIBLESSES
Utilisable seulement lorsque la moyenne est définie. Que faire dans le
cas de données nominales ? K-mode
Besoin de spécifier K à l’avance ( Pour calculer automatiquement le
meilleur K voir Hastie et al. 2009)
Ne gère pas le bruit et les exceptions
Ne trouve que des clusters de forme convexe

Lucien D. GNING [email protected] Apprentissage Statistique March 22, 2025 54 / 54