Faire du Clustering avec l’algorithme K-means

K-means (k-moyens en français) est un algorithme de clustering. Le clustering est un type d’apprentissage non supervisé (contrairement à la regression linéaire par exemple qui est un type d’apprentissage supervisé). Il consiste à regrouper les éléments de notre jeu de donnée en groupes, appelés clusters. Le but est de faire ressortir les patterns cachés dans la donnée en regroupant les éléments qui se « ressemblent ».

L’algorithme des k-moyens regroupe les points en k clusters. Cela suppose qu’il faut avoir une idée du nombre de clusters pour appliquer cet algorithme.

Comment marche l’algorithme k-means ?

L’élement central de cet algorithme est le centroïde. Un centroïde est un point du jeu de données que l’on choisira comme le « centre » d’un cluster. C’est en fonction du centroïde que nous définiront l’appartenance à un cluster.

Un autre élément important dans cet algorithme est la distance. Une distance est une application qui associe un couple de vecteurs à un nombre réel positif. Il existe plusieurs types de distances dont la plus connue est la distance euclidienne. Soit, en dimension 2 :

$D(X,Y) = \sqrt{(X^2+Y^2)}$

Plus D(X,Y) est petit, plus X et Y sont proches.

Algorithme

Initialisation

On commence par choisir, au hasard, k centroïdes. Qui seront les centres des clusters de départ.

Boucle

• On construit k clusters : Chaque point est dans le cluster du centroïde qui lui est le plus proche.
• On calcule les nouveaux centroïdes : Pour chacun des clusters qu’on vient de former, on calcule la moyenne. Celle-ci devient le nouveau centroïde (n’est pas necessairement un point du jeu de donnée).
• On recommence jusqu’à ce qu’à ce qu’il y ait convergence : La convergence correspond au fait que les centroïdes ne changent pas après une mise à jour.

Attention : La convergence des centroïdes n’est pas garantie dans cet algorithme. Il faut en tenir compte dans lors de l’implémentation et ajouter une autre condition de sortie pour la boucle principale.

Voilà, vous connaissez le principe de base. Si vous voulez plus d’informations ou des mise en équations par exemple, n’hésitez pas à laisser un commentaire ou à envoyer un mail.

Application en Python

Vu qu’on connait le principe du k-mean, on peut implémenter l’algorithme en python grâce à NumPy et Scipy par exemple. Cependant, il existe déjà une implémentation de la bibliothèque Scikit-Learn. Que je vous recommande, si vous n’avez pas besoin d’un k-moyen particulièrement customisé.

Je vous propose un script simple de clustering qui utilise cette implémentation du k-mean.

On commence par générer un jeu de donnée simple dans lequel on « regroupe » les points exprès.

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
%matplotlib inline

# Génération d'un jeu de données aléatoire
data_set_1 = 1*np.random.rand(100,2)
data_set_2 = 4*np.random.rand(100,2)
data_set_3 = 2*np.random.rand(100,2

x = np.concatenate((data_set_1[0:,0], data_set_2[0:,0] + 6, data_set_3[0:,0] + 8))
y = np.concatenate((data_set_1[0:,1], data_set_2[0:,1]+ 6, data_set_3[0:,1] + 3))
plt.scatter(x,y)



On peut clairement voir qu’on a 3 groupes qui se dessinent (ceci est fait exprès, on veut faire confirmer ces cluster par k-means). Dans le bout de code qui suit on crée le model en lui fournissant « k » et on le fait « apprendre » (grâce à la méthode fit() ) en fournissant le jeu de donnée.

data_set = np.dstack((x,y))
data_set = data_set[0]
model = KMeans(3).fit(data_set)


Une fois l’apprentissage terminé, on peut regarder les paramètres du modèle dont les centroïdes finaux par example :

print(model.cluster_centers_)


Le résultat ressemble à ça :

Regardons ce que donne notre k-mean en faisant un plot des differents clusters.

for point in data_set:
    if model.predict(point.reshape(1,-1)) == [0]:
        plt.scatter(point[0], point[1], c='b')
    elif model.predict(point.reshape(1,-1)) == [1]:
        plt.scatter(point[0], point[1], c='g')
    elif model.predict(point.reshape(1,-1)) == [2]:
        plt.scatter(point[0], point[1], c='r')

for center in model.cluster_centers_:
    plt.scatter(center[0],center[1], marker="x")
plt.show()



Voilà! Les clusters, rouge, vert et bleu correspondent bien à groupes que nous avons naturellement. Évidement dans la vrai vie les clusters ne seront pas aussi apparents. N’hesitez pas à laisser un commentaire. À bientôt!