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 :
657882
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 :
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) :
658035
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 :
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.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 :
>>> 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 :
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.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 :
# 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; (2, 5) → clusters; (8, 4) → clusters; (5, 8) → clusters; (7, 5) → clusters; (6, 4) → clusters; (1, 2) → clusters; (4, 9) → clusters
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; (2, 5) → clusters; (8, 4) → clusters; (5, 8) → clusters; (7, 5) → clusters; (6, 4) → clusters; (1, 2) → clusters; (4, 9) → clusters
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; (2, 5) → clusters; (8, 4) → clusters; (5, 8) → clusters; (7, 5) → clusters; (6, 4) → clusters; (1, 2) → clusters; (4, 9) → clusters
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; (2, 5) → clusters; (8, 4) → clusters; (5, 8) → clusters; (7, 5) → clusters; (6, 4) → clusters; (1, 2) → clusters; (4, 9) → clusters
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 :
# 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
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; (5, 0) → clusters; (8, 4) → clusters; (5, 8) → clusters; (7, 5) → clusters; (6, 4) → clusters; (1, 2) → clusters; (4, 9) → clusters
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; (5, 0) → clusters; (8, 4) → clusters; (5, 8) → clusters; (7, 5) → clusters; (6, 4) → clusters; (1, 2) → clusters; (4, 9) → clusters
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; (5, 0) → clusters; (8, 4) → clusters; (5, 8) → clusters; (7, 5) → clusters; (6, 4) → clusters; (1, 2) → clusters; (4, 9) → clusters
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; (5, 0) → clusters; (8, 4) → clusters; (5, 8) → clusters; (7, 5) → clusters; (6, 4) → clusters; (1, 2) → clusters; (4, 9) → clusters
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; (5, 0) → clusters; (8, 4) → clusters; (5, 8) → clusters; (7, 5) → clusters; (6, 4) → clusters; (1, 2) → clusters; (4, 9) → clusters
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 :
import random
import numpy as np
def centroide(points):
# renvoie le centroïde des points
x = [p for p in points]
y = [p 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 - x2),2) + pow((x1 - x2),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.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
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/articles/data-science/clustering/k-means/
https://fr.wikipedia.org/wiki/Apprentissage_non_supervis%C3%A9
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer à vous proposer des publications.