User

I. Introduction

D'après Wikipédia, le partitionnement en k-moyennes (ou k-means en anglais) est une méthode de partitionnement de données et un problème d'optimisation combinatoire. Étant donnés des points et un entier k, le problème est de diviser les points en k groupes, souvent appelés clusters, de façon à minimiser une certaine fonction. On considère la distance d'un point à la moyenne des points de son cluster ; la fonction à minimiser est la somme des carrés de ces distances.

L'algorithme des k-moyennes peut être utilisé par exemple pour réduire le nombre de couleurs d'une image sans que cela ne nuise trop à sa qualité. Cela peut être utile à des fins de compression ou pour permettre l'affichage optimal d'une image sur un écran ou une imprimante n'offrant pas une grande variété de couleurs. Les k-moyennes sont également employées en apprentissage non supervisé où l'on divise des observations en k groupes.

L'objectif de ce billet est d'implémenter en Python l'algorithme classique des k-moyennes en créant sa propre fonction de partitionnement. En complément, on va également ajouter différentes instructions print() dans le code de la fonction afin d'afficher le contenu de certaines variables durant l'exécution du code et ainsi de mieux suivre son déroulement.

Cet algorithme est également décrit dans le tutoriel Partitionnement des données : algorithme des k-moyennes de Pierre Schwartz.


II. Définition

Étant donné un ensemble de points (x₁, x₂, …, x_n), on cherche à partitionner les n points en k ensembles S = {S₁, S₂, …, S_k} (k ≤ n) en minimisant la distance entre les points à l'intérieur de chaque groupe :


où μ_i est le barycentre ou le centroïde des points dans S_i.



III. Algorithme des k-moyennes

L'algorithme classique pour le problème, parfois appelé méthode des k-moyennes, est très utilisé en pratique. Il peut être décrit de la façon suivante :

1. Choisir k points qui représentent les positions moyennes initiales m₁⁽¹⁾, …, m_k⁽¹⁾ (au hasard par exemple) ;

2. Répéter les étapes suivantes jusqu'à ce qu'il y ait convergence, c'est à dire que les k moyennes ne changent pas après leur mise à jour :

• Initialiser à vide les k clusters c₁, ..., c_k ;
• Placer chaque point x_j de l'ensemble de départ dans le cluster c_i dont la dernière moyenne est la plus proche de x_j ;
• Mettre à jour les k moyennes des k clusters ainsi obtenus.

3. Les derniers clusters obtenus représentent la solution donnée par l'algorithme.

Simulation de la convergence des k-means (issue de la page k-means clustering) :




Cette méthode, le plus souvent efficace, ne donne cependant pas toujours un résultat optimal. En tirant au hasard les k moyennes initiales et en réitérant l'algorithme de partitionnement plusieurs fois, on peut ainsi augmenter les chances d'obtenir les bonnes valeurs initiales et donc d'aboutir à une solution optimale.



IV. Implémentation en Python


IV-A. Partitionnement en k moyennes

La fonction de partitionnement d'un ensemble de points basée sur l'algorithme des k-moyennes :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def partitionnement_k_means(points, k, k_means=None):
    # fonction de partitionnement en k-moyennes
    # sources : https://en.wikipedia.org/wiki/K-means_clustering#Standard_algorithm_(naive_k-means)
 
    # arguments :
    # points : liste des points ;
    # k : nombre de groupes dans le résultat du découpage ;
    # k_means : k moyennes initiales, argument optionnel.
 
    if not k_means: # si l'argument k_means est ommis
        # tirage au hasard des k points représentant les moyennes initiales
        k_means = random.sample(points, k)
 
    # convergence à False au début
    convergence = False
 
    # tant qu'il n'y a pas convergence (que les k moyennes ont changé)
    while not convergence:
 
        # initialisation de la liste des clusters
        clusters = [[] for _ in range(k)] 
 
        # parcours des points
        for xj in points:
 
            # génération de la liste des distances du point xj aux moyennes des clusters
            distances2_k_means = [distance2(xj, mi) for mi in k_means]
 
            # indice du cluster dont la moyenne est la plus proche de xj
            indice_cluster = np.argmin(distances2_k_means)
 
            # ajout de xj au cluster repéré par indice_cluster
            clusters[indice_cluster].append(xj)
 
 
        # la liste des moyennes devient la liste des moyennes précédentes
        prev_k_means = k_means
 
        # génération de la liste des nouvelles moyennes
        k_means = [centroide(ci) for ci in clusters]
 
        convergence = (k_means==prev_k_means)
 
    return clusters

La fonction argmin de la bibliothèque numpy va donc renvoyer l'indice de l'élément ayant la valeur minimale dans un tableau.

si plusieurs occurrences de la valeur minimale existent, la première occurrence sera renvoyée comme indice :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
>>> import numpy as np
>>> np.argmin([3, 2, 4, 2, 5])
1

En ajoutant maintenant différentes instructions print() dans le code de la fonction, instructions permettant d'afficher le contenu de certaines variables durant l'exécution du code, on peut ainsi mieux suivre son déroulement :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def partitionnement_k_means(points, k, k_means=None):
    # fonction de partitionnement en k-moyennes
    # sources : https://en.wikipedia.org/wiki/K-means_clustering#Standard_algorithm_(naive_k-means)
 
    # arguments :
    # points : liste des points ;
    # k : nombre de groupes dans le résultat du découpage ;
    # k_means : k moyennes initiales, argument optionnel.
 
    if not k_means: # si l'argument k_means est ommis
        # tirage au hasard des k points représentant les moyennes initiales
        k_means = random.sample(points, k)
 
    # convergence à False au début
    convergence = False 
 
    no_iteration = 1
 
    # tant qu'il n'y a pas convergence (que les k moyennes ont changé)
    while not convergence:
 
        print(f"Itération n°{no_iteration}\n")
        print("k-means =", k_means)
 
        affectations = ""
 
        # initialisation de la liste des clusters
        clusters = [[] for _ in range(k)]
 
        # parcours des points
        for xj in points:
 
            # génération de la liste des distances du point xj aux moyennes des clusters
            distances2_k_means = [distance2(xj, mi) for mi in k_means]
 
            # indice du cluster dont la moyenne est la plus proche de xj
            indice_cluster = np.argmin(distances2_k_means)
 
            # ajout de xj au cluster repéré par indice_cluster
            clusters[indice_cluster].append(xj)
 
            affectations += str(xj) + " → clusters[{0}]; ".format(indice_cluster)
 
        print("affectations :", affectations[0:-2])        
        print("clusters =", clusters)
        print("somme_carrés_distances =", somme_distances2_k_means(clusters)); print()
 
        # la liste des moyennes devient la liste précédente
        prev_k_means = k_means
 
        # génération de la liste des nouvelles moyennes
        k_means = [centroide(ci) for ci in clusters]
 
        convergence = (k_means==prev_k_means)
 
        no_iteration+=1
 
    return clusters

IV-B. Tests de la fonction

Testons donc notre fonction en choisissant k moyennes initiales :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# liste des points 
points = [(2,10),(2,5),(8,4),(5,8),(7,5),(6,4),(1,2),(4,9)]
 
print("Liste des points :")
print(points)
 
print()
 
# nombre de groupes
k = 3
 
print("k =", k)
print()
 
# moyennes initiales
k_means = [(8,4),(5,8),(7,5)]
 
print("k moyennes initiales :")
print(k_means); print() 
 
# partitionnement des n points en k groupes : algorithme des k-means
resultat_k_means = partitionnement_k_means(points, k, k_means)
 
print()
 
print("Résultat :")
print(resultat_k_means)

Déroulement de l'exécution du code :

Liste des points :
[(2, 10), (2, 5), (8, 4), (5, 8), (7, 5), (6, 4), (1, 2), (4, 9)]

k = 3

k moyennes initiales :
[(8, 4), (5, 8), (7, 5)]

Itération n°1

k-means = [(8, 4), (5, 8), (7, 5)]
affectations : (2, 10) → clusters[1]; (2, 5) → clusters[1]; (8, 4) → clusters[0]; (5, 8) → clusters[1]; (7, 5) → clusters[2]; (6, 4) → clusters[2]; (1, 2) → clusters[2]; (4, 9) → clusters[1]
clusters = [[(8, 4)], [(2, 10), (2, 5), (5, 8), (4, 9)], [(7, 5), (6, 4), (1, 2)]]
somme_carrés_distances = 46.083333333333336

Itération n°2

k-means = [(8.0, 4.0), (3.25, 8.0), (4.666666666666667, 3.6666666666666665)]
affectations : (2, 10) → clusters[1]; (2, 5) → clusters[2]; (8, 4) → clusters[0]; (5, 8) → clusters[1]; (7, 5) → clusters[0]; (6, 4) → clusters[2]; (1, 2) → clusters[2]; (4, 9) → clusters[1]
clusters = [[(8, 4), (7, 5)], [(2, 10), (5, 8), (4, 9)], [(2, 5), (6, 4), (1, 2)]]
somme_carrés_distances = 26.333333333333336

Itération n°3

k-means = [(7.5, 4.5), (3.6666666666666665, 9.0), (3.0, 3.6666666666666665)]
affectations : (2, 10) → clusters[1]; (2, 5) → clusters[2]; (8, 4) → clusters[0]; (5, 8) → clusters[1]; (7, 5) → clusters[0]; (6, 4) → clusters[0]; (1, 2) → clusters[2]; (4, 9) → clusters[1]
clusters = [[(8, 4), (7, 5), (6, 4)], [(2, 10), (5, 8), (4, 9)], [(2, 5), (1, 2)]]
somme_carrés_distances = 14.333333333333334

Itération n°4

k-means = [(7.0, 4.333333333333333), (3.6666666666666665, 9.0), (1.5, 3.5)]
affectations : (2, 10) → clusters[1]; (2, 5) → clusters[2]; (8, 4) → clusters[0]; (5, 8) → clusters[1]; (7, 5) → clusters[0]; (6, 4) → clusters[0]; (1, 2) → clusters[2]; (4, 9) → clusters[1]
clusters = [[(8, 4), (7, 5), (6, 4)], [(2, 10), (5, 8), (4, 9)], [(2, 5), (1, 2)]]
somme_carrés_distances = 14.333333333333334


Résultat :
[[(8, 4), (7, 5), (6, 4)], [(2, 10), (5, 8), (4, 9)], [(2, 5), (1, 2)]]

En considérant la distance d'un point à la moyenne des points de son cluster, on constate que la somme des carrés de ces distances diminue après chaque itération jusqu'à atteindre la convergence.

Dans un second test, les k moyennes initiales sont tirées au hasard, ainsi en réitérant la procédure on augmente les chances d'obtenir les bonnes valeurs initiales et donc d'aboutir à une solution optimale. On cherche en fait à minimiser la somme des carrés des distances :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# liste des points 
points = [(2,10),(5,0),(8,4),(5,8),(7,5),(6,4),(1,2),(4,9)]
 
print("Liste des points :")
print(points)
 
print()
 
# nombre de groupes
k = 3
 
print("k =", k)
print()
 
# variable représentant la somme des distances des points à la moyenne de leur cluster
somme_distances2_mini = 10e10
 
# nombre de tirages aléatoires des k moyennes initiales : nombre d'exécutions de la fonction de partitionnement
nb_tirages = 5
 
print("nombre de tirages =", nb_tirages)
print()
 
# initialisation du générateur de nombres aléatoires
random.seed()
 
# on réitère le partitionnement pour minimiser la somme des distances des points à la moyenne de leur cluster
for no_tirage in range(1, nb_tirages+1):
 
    print("\n---- Tirage n°{0} ----\n".format(no_tirage))
 
    # partitionnement des n points en k groupes : algorithme des k-means
    clusters = partitionnement_k_means(points, k)
 
    # calcul de la somme des carrés des distances de chacun des points à la moyenne de leur cluster
    somme_distances2 = somme_distances2_k_means(clusters)
 
    # si la somme des distances obtenue est inférieure à somme_distances2_mini
    if somme_distances2<somme_distances2_mini:
        # mémorisation des clusters et de la somme minimum des carrés des distances
        resultat_k_means, somme_distances2_mini = clusters, somme_distances2
        print("<<<-- Résultat retenu -->>>\n")
 
print()
 
print("Résultat :")
print(resultat_k_means)
 
print()
 
print("Somme des carrés des distances :")
print(somme_distances2_mini)

Extrait du déroulement du test :

Liste des points :
[(2, 10), (5, 0), (8, 4), (5, 8), (7, 5), (6, 4), (1, 2), (4, 9)]

k = 3

nombre de tirages = 5


---- Tirage n°1 ----

Itération n°1

k-means = [(5, 8), (4, 9), (8, 4)]
affectations : (2, 10) → clusters[1]; (5, 0) → clusters[2]; (8, 4) → clusters[2]; (5, 8) → clusters[0]; (7, 5) → clusters[2]; (6, 4) → clusters[2]; (1, 2) → clusters[0]; (4, 9) → clusters[1]
clusters = [[(5, 8), (1, 2)], [(2, 10), (4, 9)], [(5, 0), (8, 4), (7, 5), (6, 4)]]
somme_carrés_distances = 48.25

Itération n°2

k-means = [(3.0, 5.0), (3.0, 9.5), (6.5, 3.25)]
affectations : (2, 10) → clusters[1]; (5, 0) → clusters[2]; (8, 4) → clusters[2]; (5, 8) → clusters[1]; (7, 5) → clusters[2]; (6, 4) → clusters[2]; (1, 2) → clusters[0]; (4, 9) → clusters[1]
clusters = [[(1, 2)], [(2, 10), (5, 8), (4, 9)], [(5, 0), (8, 4), (7, 5), (6, 4)]]
somme_carrés_distances = 26.416666666666668

Itération n°3

k-means = [(1.0, 2.0), (3.6666666666666665, 9.0), (6.5, 3.25)]
affectations : (2, 10) → clusters[1]; (5, 0) → clusters[2]; (8, 4) → clusters[2]; (5, 8) → clusters[1]; (7, 5) → clusters[2]; (6, 4) → clusters[2]; (1, 2) → clusters[0]; (4, 9) → clusters[1]
clusters = [[(1, 2)], [(2, 10), (5, 8), (4, 9)], [(5, 0), (8, 4), (7, 5), (6, 4)]]
somme_carrés_distances = 26.416666666666668

<<<-- Résultat retenu -->>>


---- Tirage n°2 ----

Itération n°1

k-means = [(2, 10), (8, 4), (1, 2)]
affectations : (2, 10) → clusters[0]; (5, 0) → clusters[2]; (8, 4) → clusters[1]; (5, 8) → clusters[0]; (7, 5) → clusters[1]; (6, 4) → clusters[1]; (1, 2) → clusters[2]; (4, 9) → clusters[0]
clusters = [[(2, 10), (5, 8), (4, 9)], [(8, 4), (7, 5), (6, 4)], [(5, 0), (1, 2)]]
somme_carrés_distances = 19.333333333333336

Itération n°2

k-means = [(3.6666666666666665, 9.0), (7.0, 4.333333333333333), (3.0, 1.0)]
affectations : (2, 10) → clusters[0]; (5, 0) → clusters[2]; (8, 4) → clusters[1]; (5, 8) → clusters[0]; (7, 5) → clusters[1]; (6, 4) → clusters[1]; (1, 2) → clusters[2]; (4, 9) → clusters[0]
clusters = [[(2, 10), (5, 8), (4, 9)], [(8, 4), (7, 5), (6, 4)], [(5, 0), (1, 2)]]
somme_carrés_distances = 19.333333333333336

<<<-- Résultat retenu -->>>


---- Résultats des tirages n°3, 4 et 5 non retenus ----


Résultat :
[[(2, 10), (5, 8), (4, 9)], [(8, 4), (7, 5), (6, 4)], [(5, 0), (1, 2)]]

Somme des carrés des distances :
19.333333333333336

Chacun pourra aussi vérifier que plus k augmente, plus la somme des carrés des distances diminue.

La librairie sklearn.cluster permet également de mettre en œuvre l'algorithme des k-means en Python.


IV-C. Module complet

Voici le code complet du module pour effectuer les différents tests :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
import random
import numpy as np
 
def centroide(points):
    # renvoie le centroïde des points
 
    x = [p[0] for p in points]
    y = [p[1] for p in points]
 
    return (sum(x)/len(x), sum(y)/len(y))
 
 
def distance2(x1, x2):
    # calcul du carré de la distance entre x1 et x2
 
    return pow((x1[0] - x2[0]),2) + pow((x1[1] - x2[1]),2)
 
 
def somme_distances2_k_means(clusters):
    # somme des carrés des distances des points à la moyenne de leur cluster
    # fonction à minimiser
 
    # initialisation de la somme des distances
    somme_distances2 = 0
 
    # parcours des clusters
    for ci in clusters:
        # calcul du centroïde de ci
        mi = centroide(ci)
 
        # ajout de la somme des carrés des distances de chaque point à la moyenne de son cluster 
        somme_distances2 +=  sum([distance2(xj, mi) for xj in ci])
 
    # retourne la somme des carrés des distances        
    return somme_distances2
 
 
def partitionnement_k_means(points, k, k_means=None):
    # fonction de partitionnement en k-moyennes
    # sources : https://en.wikipedia.org/wiki/K-means_clustering#Standard_algorithm_(naive_k-means)
 
    # arguments :
    # points : liste des points ;
    # k : nombre de groupes dans le résultat du découpage ;
    # k_means : k moyennes initiales, argument optionnel.
 
    if not k_means: # si l'argument k_means est ommis
        # tirage au hasard des k points représentant les moyennes initiales
        k_means = random.sample(points, k)
 
    # convergence à False au début
    convergence = False
 
    no_iteration = 1
 
    # tant qu'il n'y a pas convergence (que les k moyennes ont changé)
    while not convergence:
 
        print(f"Itération n°{no_iteration}\n")
        print("k-means =", k_means)
 
        affectations = ""
 
        # initialisation de la liste des clusters
        clusters = [[] for _ in range(k)]
 
        # parcours des points
        for xj in points:
 
            # génération de la liste des distances du point xj aux moyennes des clusters
            distances2_k_means = [distance2(xj, mi) for mi in k_means]
 
            # indice du cluster dont la moyenne est la plus proche de xj
            indice_cluster = np.argmin(distances2_k_means)
 
            # ajout de xj au cluster repéré par indice_cluster
            clusters[indice_cluster].append(xj)
 
            affectations += str(xj) + " → clusters[{0}]; ".format(indice_cluster)
 
        print("affectations :", affectations[0:-2])        
        print("clusters =", clusters)
        print("somme_carrés_distances =", somme_distances2_k_means(clusters)); print()
 
        # la liste des moyennes devient la liste précédente
        prev_k_means = k_means
 
        # génération de la liste des nouvelles moyennes
        k_means = [centroide(ci) for ci in clusters]
 
        convergence = (k_means==prev_k_means)
 
        no_iteration+=1
 
    return clusters 
 
print("--- Algorithme des k-moyennes ---\n")
 
print("I. Partitionnement en k-moyennes : choix de k moyennes initiales :\n")
 
# liste des points 
points = [(2,10),(2,5),(8,4),(5,8),(7,5),(6,4),(1,2),(4,9)]
 
print("Liste des points :")
print(points)
 
print()
 
# nombre de groupes
k = 3
 
print("k =", k)
print()
 
# moyennes initiales
k_means = [(8,4),(5,8),(7,5)]
 
print("k moyennes initiales :")
print(k_means); print() 
 
# partitionnement des n points en k groupes : algorithme des k-means
resultat_k_means = partitionnement_k_means(points, k, k_means)
 
print()
 
print("Résultat :")
print(resultat_k_means)
 
print();print()
 
wait = input("Appuyer su la touche Entrée pour continuer..")
 
print();print()
 
print("II. Partitionnement en k-moyennes : tirage au hasard des k moyennes initiales :\n")
 
# liste des points 
points = [(2,10),(5,0),(8,4),(5,8),(7,5),(6,4),(1,2),(4,9)]
 
print("Liste des points :")
print(points)
 
print()
 
# nombre de groupes
k = 3
 
print("k =", k)
print()
 
# variable représentant la somme des distances des points à la moyenne de leur cluster
somme_distances2_mini = 10e10
 
# nombre de tirages aléatoires des k moyennes initiales : nombre d'exécutions de la fonction de partitionnement
nb_tirages = 5
 
print("nombre de tirages =", nb_tirages)
print()
 
# initialisation du générateur de nombres aléatoires
random.seed()
 
# on réitère le partitionnement pour minimiser la somme des distances des points à la moyenne de leur cluster
for no_tirage in range(1, nb_tirages+1):
 
    print("\n---- Tirage n°{0} ----\n".format(no_tirage))
 
    # partitionnement des n points en k groupes : algorithme des k-means
    clusters = partitionnement_k_means(points, k)
 
    # calcul de la somme des carrés des distances de chacun des points à la moyenne de leur cluster
    somme_distances2 = somme_distances2_k_means(clusters)
 
    # si la somme des distances obtenue est inférieure à somme_distances2_mini
    if somme_distances2<somme_distances2_mini:
        # mémorisation des clusters et de la somme minimum des carrés des distances
        resultat_k_means, somme_distances2_mini = clusters, somme_distances2
        print("<<<-- Résultat retenu -->>>\n")
 
print()
 
print("Résultat :")
print(resultat_k_means)
 
print()
 
print("Somme des carrés des distances :")
print(somme_distances2_mini)

Si vous souhaitez avoir plus d'information sur le sujet, je vous invite à consulter les pages k-moyennes et Partitionnement des données : algorithme des k-moyennes.


V. Conclusion

Après avoir décrit l'algorithme des k-moyennes, on a donc pu l'implémenter en Python en créant sa propre fonction de partitionnement. Ensuite, en plaçant différents instructions print() dans le code de la fonction, on a pu aussi mieux visualiser le déroulement de son exécution.

Enfin, en remarquant que la qualité du résultat de l'algorithme dépendait des k moyennes initiales, on a proposé une méthode permettant d'optimiser notre fonction.


Sources :

https://fr.wikipedia.org/wiki/K-moyennes
https://en.wikipedia.org/wiki/K-means_clustering
https://khayyam.developpez.com/artic...ering/k-means/
https://fr.wikipedia.org/wiki/Appren...supervis%C3%A9