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 (x1, x2, …, xn), on cherche à partitionner les n points en k ensembles S = {S1, S2, …, Sk} (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 Si.
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 m1(1), …, mk(1) (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 c1, ..., ck ;
- Placer chaque point xj de l'ensemble de départ dans le cluster ci dont la dernière moyenne est la plus proche de xj ;
- 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 |
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 |
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 |
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 |
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 |
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 |
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