Apprentissage Automatique

M1 IAFA-SECIL
Université Paul Sabatier

Contacts :
[email protected]
[email protected]

1 / 26
Apprentissage non supervisé

2 / 26
Apprentissage non supervisé

Chaîne d’analyse des données

Classification non supervisée

vise à créer une partition (un ensemble de classes) d’un ensemble de données à
partir des mesures de similarité entre ces données afin que des données
appartenant à une même classe soit le plus semblable possible et des données
appartenant à des classes soient le moins semblables possible.

3 / 26
Apprentissage non supervisé

On ne dispose pas de base d’apprentissage/connaissance a priori, la

classification non supervisée sert à
définir des distances entre individus/variables,
identifier des regroupements (agrégations/clusters).

Figure: Exemple de classification non supervisée : diviser cet ensemble de points en 4

classes à partir de la distance entre les points

3 / 26
Classification non supervisée

Approches par partitionnement :

K-ppv
K-means
Classification hiérarchique

Méthodes d’évaluation non supervisée de la partition :

Cohesion, Séparation
SSW, SSB et variantes

⇒ Toolbox Scikit Learn (Python)

4 / 26
Kppv

5 / 26
Kppv

5 / 26
K-means - James MacQueen (1967)

Partitionner un ensemble de données en k classes représentées par les k

centres, notés C = C 1 . . . C k .


On associe alors à chaque point/donnée le centre le plus proche au sens d’une

certaine distance.

Dans le cadre non supervisé on cherche généralement à partitionner l’ensemble

de données de manière à minimiser la variance intra-classe, qui se traduit par
l’énergie, entropie (ou variance intra-classe) :
k
1XX
E = ∥x − mi ∥2
n i=1 i
x∈C

S = {x1 . . . xn } ∈ Rp ensemble des données





#S = n
où


C i = classe i ∀i ∈ 1 . . . k
mi = centre de la classe i , ∀i ∈ {1 . . . k}


6 / 26
Algorithme K-means

Soit S = {x1 . . . xn }, xi ∈ Rp . On veut partitionner S en k classes C i afin de

minimiser les distances intra-classes (ou l’entropie).

7 / 26
Algorithme K-means

8 / 26
K-means : limites

Quelques points cruciaux !

Bien choisir les centres à l’initialisation pour éviter les convergences

locales;

Nombre de classes à déterminer;

Méthode de séparation linéaire.

9 / 26
K-means : limites

Quelques points cruciaux !

Bien choisir les centres à l’initialisation pour éviter les convergences

locales;

→ heuristiques sur la distribution des points;

Nombre de classes à déterminer;

Méthode de séparation linéaire.

9 / 26
K-means : limites

Quelques points cruciaux !

Bien choisir les centres à l’initialisation pour éviter les convergences

locales;

→ heuristiques sur la distribution des points;

Nombre de classes à déterminer;

→ varier le nombre de classes et étudier l’énergie;

Méthode de séparation linéaire.

9 / 26
K-means : limites

Quelques points cruciaux !

Bien choisir les centres à l’initialisation pour éviter les convergences

locales;

→ heuristiques sur la distribution des points;

Nombre de classes à déterminer;

→ varier le nombre de classes et étudier l’énergie;

Méthode de séparation linéaire.

9 / 26
K-means : limites

Pureté = 0.75
SSE = 359.80
Satisfaisant ?

10 / 26
k-moyennes à noyaux / Kernel k-means

Idée : projeter les données sur un espace à plus grande dimension grâce à
une fonction "noyau" et appliquer ensuite l’algorithme k-moyennes dans
cet espace

Attention : cela implique de calculer et avoir en mémoire une matrice de

taille N × N

Exemples de fonctions à noyaux :

Noyau polynomial de degré h : K (xi , xj ) = (xi xj + 1)h

2
/2σ 2
Noyau gaussien radial (RBF) : K (xi , xj ) = e −||xi −xj ||

11 / 26
Exemple : noyau gaussien radial

12 / 26
Exemple : noyau gaussien radial

Pureté = 1.0
SSE = 309.81
Satisfaisant ?

13 / 26
Classification Hiérarchique

Contrairement à la méthode des K-moyennes, les méthodes de clustering

hiérarchique ne dépendent :

ni d’un nombre K de clusters prédéfini;

ni d’une configuration initiale (choisie souvent arbitrairement).

La seule chose à fournir est une mesure de dissimilarité entre groupes

(disjoints) d’observations. Naturellement, une telle mesure est bâtie sur les
dissimilarités prises 2 à 2 au sein de chaque groupe.

14 / 26
Classification Hiérarchique : mesures de dissimilarités

Soient G et H deux groupes d’observations/de données.

Dissimilarité moyenne/Group
Average :
1 X
dGA (G , H) = dii ′
|G ||H| ′ i∈G ,i ∈H

Dissimilarité du lien
complet/complete linkage
dCL (G , H) = max dii ′
i∈G , i ′ ∈H

Dissimilarité du lien simple/single

linkage :
dSL (G , H) = min dii ′
i∈G , i ′ ∈H

15 / 26
Classification Hiérarchique

Les méthodes de classification hiérarchique (CH) fournissent des

représentations pour lesquelles chaque cluster au sein de la hiérarchie et à un
certain niveau est créé par fusion de clusters à un niveau plus fin.
Au niveau le plus fin, chaque cluster est un singleton; au niveau le plus haut,
un seul cluster regroupe toutes les données disponibles.

Définition : Une partition Πi est plus fine que partition Πj ssi tout bloc de Πj
est un bloc de Πi ou est l’union de plusieurs blocs de Πi .

Les stratégies pour la classification hiérarchique sont :

ascendantes/agglomératives/bottom-up : démarrer du bas niveau (une
donnée=une classe) et opèrer des fusions récursives de clusters en plus
gros clusters;
descendantes/séparatrices/top-down : commencer par séparer la classe
regroupant toutes les données en 2 clusters de dissimilarités maximales.
Etant donnée une représentation hiérarchique issue d’un CH, c’est à
l’utilisateur de décider quel est le niveau naturel de partitionnement/clustering
qui correspond à la structure (inconnue) des données.

16 / 26
Classification Hiérarchique

On peut afficher l’arbre binaire de sorte que la hauteur de chaque noeud soit
équivalente à la valeur de la dissimilarité intercluster entre ces deux enfants. Ce
type d’affichage est appelé dendrogramme.

Exemple de hiérarchie sur un ensemble initial de données :

S = {a, b, c, d, e, f , g , h}.

On parle aussi de chaîne de partitions

Π8 : (a, b, c, d, e, f )
Π7 : (a, b, c) (d, e, f , g , h)
Π6 : (a, b, c) (d, e)(f , g , h)
Π5 : (a, b, c) (d, e)(f , g ) (h)
Π4 : (a, b, c) (d) (e) (f , g ) (h)
Π3 : (a, b, c) (d) (e) (f ) (g ) (h)
Π2 : (a, c) (b) (d) (e) (f ) (g ) (h)
Π1 : (a) (b) (c) (d) (e) (f ) (g ) (h)

17 / 26
Classification Hiérarchique

Exercice :
A partir de la matrice des distances entre les points suivante :
A B C D
A 0 1 4 5
B 0 2 6
C 0 3
D 0

1 Réaliser la classification hiérarchique des données par lien simple

2 Réaliser la classification hiérarchique des données par Lien complet
3 Représenter ces partitions par dendrogrammes.

18 / 26
Classification Hiérarchique : limites

Une fois qu’un regroupement ou une division est réalisé, pas de possibilité
de revenir en arrière
Complexité en O(n2 ) : problème de passage à l’échelle
Des variantes plus compliquées existent, comme par exemple BIRCH :
Balanced Iterative Reducing and Clustering using Hierarchies, (Zhang, et
al., 1996).
Principe de BIRCH : clustering multi-niveaux qui construit un arbre de
features. Les feuilles de l’arbre sont l’objet d’un clustering, par exemple un
k-moyennes.

19 / 26
Beaucoup d’autres techniques de clustering

http://scikit-learn.org/stable/modules/clustering.html

20 / 26
Le non-supervisé : un monde...

Comment évaluer les méthodes non supervisées ?

21 / 26
Méthodes d’évaluation non supervisée de la partition

Cohésion et Séparation
la cohésion d’une classe mesure comment les objets d’un cluster sont
étroitement liés;
la séparation d’une classe mesure comment une classe est distincte ou bien
séparée de l’autre.

Pour une classe Ci ,

X
Cohesion(Ci ) = prox(x, y )
x∈Ci ,y ∈Ci

X
Separation(Ci , Cj ) = prox(x, y ), i ̸= j
x∈Ci ,y ∈Cj

où prox est une fonction de proximité (similarité, dissimilarité, distances...)

22 / 26
SSW et BSS

Sum of Squared Error (SSE) ou Sum of Squared Errors Within Cluster

(SSW) correspond à la mesure de cohésion où prox est la distance
euclidienne (à minimiser)
X 1 XX
SSE (Ci ) = d(ci , x)2 = d(x, y )2
2|Ci |
x∈Ci x∈Ci y ∈Ci

où x est un élement de Ci , ci est le centre de Ci et |Ci | le cardinal de la

classe Ci .
Between group Sum of Squares (BSS) basé sur la séparation (à maximiser)
K
X
BSS = |Ci |d(ci , c)2
i=1

où c est le centroid de l’ensemble de données.

23 / 26
SSW et BSS : variantes

Coefficient Calinski-Harabasz (CH) est un ratio (à maximiser) entre la

variance inter-classe et la variance intra-classe :
BSS
CH = K −1
SSE
K
Indice de Hartigan basé sur le logarithme du ratio BSS/SSE :
 
BSS
H = log
SSE
Indice de Dunn est le ratio de la plus petite distance entre les données de
différents groupes et de la plus grande distance entre les groupes.
Pour une classe Ci ,
min1<j<K ,i̸=j δ(Ci , Cj )
Di =
max1<l<K ∆(Cl )

avec ∆(Ci ) = maxx,y ∈Ci d(x, y ) et δ(Ci , Cj ) = minx∈Ci ,y ∈Cj d(x, y ).

24 / 26
SSW et BSS : variantes

Silhouette est le coefficient le plus connu combinant les mesures de

cohésion et de séparation.
Le calcul du coefficient de silhouette à un point donné comprend les trois
étapes suivantes, pour chaque donnée x ∈ Ci ,
1 calcul de la distance moyenne entre x et tous les autres points au sein de la
même classe :
1 X
a(x) = d(x, y )
|Ci | − 1 y ∈C ,x̸=y
i
2 calcul de la dissimilarité moyenne minimale entre le point x et une autre
classe Ck (i ̸= k):
1 X
b(x) = min d(x, y )
k̸=i |Ck |
y ∈C
k
3 calcul du coefficient silhouette s(x) ∈ [−1, 1] :
 b(x) − a(x) si |C | > 1,

i
s(x) = max(a(x), b(x)
0 si |Ci | = 1.


25 / 26
SSW et BSS : variantes
Interprétation : le coefficient de silhouette permet de qualifier simplement le
partitionnement:
Des valeurs positives indiquent une séparation élevée entre les clusters.
Les valeurs négatives indiquent que les classes sont mélangées entre elles
(c’est-à-dire qu’il y a chevauchement de classes).
Lorsque le coefficient de silhouette est nul, c’est une indication que les
données sont uniformément réparties dans l’espace euclidien.

25 / 26
Cas de la classification hiérarchique

Pour évaluer la pertinence de la structure issue du CH, on calculer la distance

cophénétique entre deux objets. C’est la hauteur du dendrogramme où les deux
branches qui comprennent les deux objets fusionnent en une seule branche.

On peut ainsi calculer le coefficient de correlation cophénétique qui mesure la

fidélité avec laquelle un dendrogramme préserve les distances par paires entre
les points de données originaux non modélisés.
P ¯
i<j (d(xi , xj ) − d)(T (xi , xj ) − T̄ )
c = qP ∈ [−1, 1]
¯2
P 2
i<j (d(xi , xj ) − d) i<j (T (xi , xj ) − T̄ )

avec
d(xi , xj ) distace entre les données xi et xj
T (i, j) la distance cophénétique entre les données xi et xj
d¯ (resp. T̄ ) est la moyenne des distances (resp. distances cophénétiques).
⇒ Très utilisé en biostatistique pour évaluer des modèles de séquences d’ADN.

26 / 26