Faculté des Sciences de Tunis

Leila Ben Othman

Année universitaire: 2022 - 2023
Apprentissage non supervisé
K-Means
Plan

1 Introduction

2 L'algorithme K-Means

3 K-Means avec Scikit-learn

 Introduction

L'apprentissage non supervisé (Unsupervised Learning)

Principe (Apprentissage non supervisé)

L'apprentissage non supervisé désigne la situation d'apprentissage
automatique où les données ne sont pas étiquetées. Il s'agit donc de
découvrir les structures sous-jacentes à ces données non étiquetées.

• Dataset: des observations/exemples/un échantillon X

• Features: des variables xi (i = 1, ..., n)
• Target: Pas d'étiquettes.

NB:
• Données avec étiquettes: coûteuse à obtenir sur des grands volumes
de données.

• Données sans étiquettes: plus faciles à obtenir mais souvent plus

compliqué à exploiter.

Leila Ben Othman, FST 2022-2023 4 / 19

 Introduction

Jeux de données - Iris dataset

Iris Datset Iris Datset

4.5
setosa 2.5 setosa
versicolor versicolor
4.0 virginica virginica
2.0
sepal_width_in_cm

petal_width_in_cm
3.5
1.5
3.0
1.0
2.5
0.5
2.0
0.0
4.5 5.0 5.5 6.0 6.5 7.0 7.5 8.0 1 2 3 4 5 6 7
sepal_length_in_cm petal_length_in_cm

Figure: Exemple 1 Figure: Exemple 2

Leila Ben Othman, FST 2022-2023 5 / 19

 Introduction

Jeux de données - Iris dataset (non étiquetées)

4.5
2.5

4.0
2.0
sepal_width_in_cm

petal_width_in_cm
3.5
1.5

3.0
1.0

2.5
0.5

2.0
0.0
4.5 5.0 5.5 6.0 6.5 7.0 7.5 8.0 1 2 3 4 5 6 7
sepal_length_in_cm petal_length_in_cm

Figure: Exemple 1 Figure: Exemple 2

Leila Ben Othman, FST 2022-2023 6 / 19
 Introduction

Regroupement - Clustering

• Le regroupement (Clustering) est une techniques d'apprentissage

non supervisé qui consiste à séparer ou à diviser un ensemble de
données en un certain nombre de groupes (cluster).

• Principe:
• Regrouper tout ce qui se ressemble
• Éloigner tout ce qui est diérent
=⇒ Former des clusters.

Un cluster est un regroupement de

données tel que:

• les données au sein d'un même

cluster sont similaires.

• les données appartenant à des

clusters diérents dissemblables.

Leila Ben Othman, FST 2022-2023 7 / 19

 Introduction

Applications

• Segmentation des clients

• Système de recommandation

• Détection d'anomalies (données aberrantes)

Leila Ben Othman, FST 2022-2023 8 / 19

 L'algorithme K-Means

K-Means

• K-Means est un algorithme non supervisé de clustering non

hiérarchique.

• C'est l'un des algorithmes de clustering les plus répandus. Il permet

d'analyser un jeu de données caractérisées par un ensemble de
descripteurs, an de regrouper les données similaires en groupes
(clusters).

Leila Ben Othman, FST 2022-2023 9 / 19

 L'algorithme K-Means

Algorithme K-Means

Figure: Clustering - k=3

Leila Ben Othman, FST 2022-2023 10 / 19

 L'algorithme K-Means

K-Means - Démarche

1 La première étape consiste à dénir k centroïdes aléatoirement.

2 Pour chaque observation, calculer la distance aux k centroïdes et

l'associer au centroïde le plus proche. Nous obtenons ainsi k cluster.

3 Recalculer les k nouveaux centroïdes qui seront les centres de

gravité des k cluster.

4 On répète les étapes (2) et (3) jusqu'à ce que les nouveaux

centroïdes restent stables.

NB: Les coordonnées de chaque centroide est la moyenne des

coordonnées des points faisant partie du cluster associé au centroide,
d'où le nom de l'algorithme K-Means ou K-Moyennes.

Leila Ben Othman, FST 2022-2023 11 / 19

 L'algorithme K-Means

Algorithme K-Means - Notion de similarité

L'algorithme K-Means utilise la distance euclidienne qui permet d'évaluer

la distance entre chaque point et les centroïdes de chaque cluster:

• La distance Euclidienne entre deux points A(xA , yA ) et B (xB , yB ):

d= (xB − xA )2 + ( yB − yA ) 2
p

• De façon générale, la distance Euclidienne entre deux points A et B

(n coordonnées):

d= n (x − x )2
qP
i =1 iB iA

Leila Ben Othman, FST 2022-2023 12 / 19

 L'algorithme K-Means

Exemple

• Étape 1: Pour k=2, soient c1 = (5,3) et c2 = (10,15) les centroides

des deux clusters.

• Étape 2: Pour chaque observation, on calcule la distance euclidienne

avec chacun des centroïdes puis on associe l'observation au
centroïde le plus proche.

Observation Distance euclidienne Distance euclidienne Résultat

du Centroid c1 du centroid c2
c1 = (5,3) c2 = (10,15)

(15,12) 13.453 5.830 c2

(5,4) 1.0 12.083 c1
(20,3) 15.0 15.620 c1
(2,2) 3.162 15.264 c1
(2,10) 7.615 9.433 c1
(3,12) 9.219 7.615 c2

Leila Ben Othman, FST 2022-2023 13 / 19

 L'algorithme K-Means

Exemple

• Étape 3

Observation Distance euclidienne Distance euclidienne résultat

du Centroid c1 du centroid c2
c1 = (5,3) c2 = (10,15)

(15,12) 13.453 5.830 c2

(5,4) 1.0 12.083 c1
(20,3) 15.0 15.620 c1
(2,2) 3.162 15.264 c1
(2,10) 7.615 9.433 c1
(3,12) 9.219 7.615 c2

Les nouveaux centroides c1=(7.25, 4.75) et c2=(9.0, 12.0)

Leila Ben Othman, FST 2022-2023 14 / 19

 L'algorithme K-Means

Algorithme K-Means
Entrée:
• Jeu de données

• k le nombre de cluster à former

Résultat:
• Une répartition des observations en k cluster

DEBUT
• Choisir aléatoirement k points. Ces points sont les centres des
clusters (centroïdes).

RÉPÉTER
• Pour chaque observation, calculer la distance aux k centroïdes

• Aecter chaque observation au cluster le plus proche

• Pour chaque cluster, calculer les nouveaux centres (centroides)

JUSQU`A CONVERGENCE

FIN ALGORITHME
Leila Ben Othman, FST 2022-2023 15 / 19
 L'algorithme K-Means

Exemple

80 80
70 70
60 60
50 50
40 40
30 30
20 20
10 10

20 30 40 50 60 20 30 40 50 60

Figure: Données initiales Figure: k=3

Leila Ben Othman, FST 2022-2023 16 / 19

 L'algorithme K-Means

Exemple

80 80
70 70
60 60
50 50
40 40
30 30
20 20
10 10

20 30 40 50 60 20 30 40 50 60

Figure: k=4 Figure: k=5

Leila Ben Othman, FST 2022-2023 17 / 19

 L'algorithme K-Means

K-Means - Discussion

1 La bonne valeur de k?
• un k grand: partitionnement trop fragmenté des données: ceci nous
empêchera de découvrir des patterns intéressants dans les données.
• un k petit: des cluster trop généralistes contenant beaucoup de
données.
2 La convergence de l'algorithme K-Means peut être l'une des
conditions suivantes :
• Un nombre d'itérations xé à l'avance, dans ce cas, K-means
eectuera les itérations et s'arrêtera peu importe la forme de clusters
composés.
• Stabilisation des centres de clusters (les centroides ne bougent plus
lors des itérations).
3 L'initialisation des centroides
• initialisation aléatoire: on obtient pas le même partionnement.
4 Evaluation d'un clustering?

Leila Ben Othman, FST 2022-2023 18 / 19

 K-Means avec Scikit-learn

K-Means avec Scikit-learn

• L'import: from sklearn.cluster import KMeans

• Dénition du modèle: kmeans = KMeans(n_clusters=5) - par

défaut, c'est 8.

• Clustering sur des données data: kmeans.t(data)

• Les centroides: kmeans.cluster_centers_

• Les labels des diérents cluster: kmeans.labels_

• Prédiction pour un nouveau cas x: kmeans.predict([x])

Leila Ben Othman, FST 2022-2023 19 / 19