Partitionnement des données : algorithme des k-moyennes

Pierre SCHWARTZ

En data-science, le partitionnement de données (clustering) fait partie des techniques d'apprentissage non supervisé permettant de qualifier les données continues d'un dataset d'après la forme de ce dataset.
L'objectif de l'algorithme des k-moyennes (k-means) est de découper notre dataset en k paquets qui se ressemblent. Le résultat du regroupement pourra définir une étiquette associée à chaque élément du dataset. C'est en ça que cette technique est classée dans l'apprentissage non supervisé, par opposition aux techniques où le libellé est fourni au modèle en même temps que les données.
Commentez

- Titre : Partitionnement des données : algorithme des k-moyennes

- Auteur : Pierre SCHWARTZ

- Parution : 22 avril 2020

- Licence : Copyright ® 2020 Pierre SCHWARTZ. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- Déroulement de l'algorithme

- Initialisation des centroïdes

- Itérations de l'algorithme

- Convergence

- Combien de clusters repérer ?

- En conclusion

Déroulement de l'algorithme

Considérons un dataset comme celui-ci :

Nous pouvons visuellement remarquer qu'il y a six paquets de points. La convergence de l'algorithme sera la séparation des points en ces six paquets.

C'est un algorithme itératif qui va affiner sa solution à chaque étape. L'algorithme va déplacer itérativement k centres de paquets (appelés centroïdes) pour les rapprocher des points dont ils sont les plus proches.

Étapes de l'algorithme :

- positionnement des k centroïdes ;

- pour chaque itération

- associer chaque point du dataset au centroïde le plus proche,

- déplacer les k centroïdes vers les barycentres des points dont ils sont les plus proches.

L'algorithme s'arrête lorsqu'on a atteint le nombre maximum d'itérations ou lorsque les centroïdes ne bougent plus.

Initialisation des centroïdes

Il y a plusieurs stratégies pour placer les centroïdes au début de l'algorithme :

- vous pouvez les placer aléatoirement dans la zone couverte par votre dataset ;

- vous pouvez considérer des éléments de votre dataset régulièrement espacés ;

- vous pouvez choisir de les placer volontairement en dehors du dataset.

Cependant, attention, le résultat de l'algorithme est influencé par les positions initiales des centroïdes. Ce sera visible dans les illustrations plus loin dans cet article.

Itérations de l'algorithme

La notion de proximité entre un point et un centroïde est laissée à votre appréciation. Dans le cas d'un dataset géométrique dans le plan, la notion de proximité peut être implémentée par la distance euclidienne.

De manière plus générale, la distance entre deux points a et b peut s'exprimer en n dimensions pour sommer les carrés des écarts sur chaque dimension.

Chaque point va être associé au centroïde dont il est le plus proche, puis le centroïde va se déplacer vers le barycentre de ces points.

1. for p in range(nb_points):

2. # on calcule la distance du point p à chaque centroïde

3. distances = [ distance( dataset[p] , c) for c in centroids]

4. # quel est le centroïde le plus proche ?

5. idCentroideProche = np.argmin(distances)

6. # on place le point p dans la liste des points associés à chaque centroïde

7. centroidesLesPlusProches[idCentroideProche].append(dataset[p])

Le déplacement d'un centroïde se fait en calculant la moyenne des points selon chaque caractéristique (ici x et y)

1. for c in range(nb_centroids):

2. meanx = np.mean([centroidesLesPlusProches[c][p][0] for p in range(len(centroidesLesPlusProches[c])-1)])

3. meany = np.mean([centroidesLesPlusProches[c][p][1] for p in range(len(centroidesLesPlusProches[c])-1)])

5. # si meanx et meany ne changent pas, l'algorithme a convergé et on peut arrêter l'itération

7. centroids[c][0] = meanx

8. centroids[c][1] = meany

Convergence

Selon les positions de départ de nos centroïdes, nous pouvons obtenir plusieurs convergences différentes :

Dans le cas d'un dataset carré, on peut avoir deux convergences :

Si on souhaite obtenir une convergence unique (ou préférée), une solution intéressante est d'exécuter l'algorithme plusieurs fois, en prenant à chaque fois des centroïdes initiaux différents et de repérer quels résultats reviennent le plus souvent.

Combien de clusters repérer ?

À l'origine l'algorithme a été écrit pour qu'il donne les k centroïdes en connaissant k. Cependant on ne connaît pas toujours ce nombre k puisqu'il dépend de la forme qu'on cherche justement à analyser.
Voilà les convergences observées pour k=3, k=4, k=5 et k=8

Une des idées intéressantes est d'exécuter l'algorithme avec différentes valeurs de k et de mesurer pour chacune la somme des distances entre les points et leur centroïde. En utilisant la technique du coude, vous pouvez mettre en évidence une valeur de k optimale. Dans notre cas la valeur optimale est 6, c'est là que le graphique fait un “coude”.

En conclusion

En conclusion, nous pouvons apprécier cet algorithme pour sa simplicité d'utilisation et de compréhension. Il dépend fortement des positions initiales des centroïdes et il dépend fortement de la fonction de distance que vous utilisez. Dans notre exemple nous avons recherché des clusters convexes (qui se ressemblaient au sens de la distance euclidienne). Si vous avez des ensembles allongés, l'algorithme des k-moyennes ne vous donnera pas forcément de bons résultats. Vos clusters doivent être linéairement séparables pour que l'algorithme des k-moyennes s'avère pertinent.

Si vous avez une idée de la forme de vos clusters, vous pouvez essayer de les retravailler en amont pour les rendre davantage convexes sinon vous devrez utiliser d'autres algorithmes de partitionnement de données.

Et bien sûr, cet algorithme a été implémenté dans les principales bibliothèques de manipulation de données. Ne vous embêtez pas à l'écrire à la main : il est ici.