Introduction a l’algorithme des kmeans

L'algorithme des kmeans permet de regrouper les informations (points) au sein de cluster distincts en utilisant une estimation de distance, ici ce seras une simple distance euclidien. Pour ce faire, nous allons fixer dans l’algorithme les centres de départs aléatoirement et leurs nombres donnés au début du programme. Ce sont des informations à priori que nous avons sur les données. Ensuite nous allons effectuer plusieurs itérations jusqu'a ce que deux itérations successive n’améliore pas suffisamment le résultat (avec une tolérance).

Ainsi à chaque itération, nous allons réattribuer les centres à chaque point, en fonction de la distance du point (la donnée) avec le centre le plus proche ce seras le rôle de la fonction updateClusterId. Ensuite, on recalcule le centre de tous les clusters grâce à la fonction updateCenters et finalement, on calcule le « score » global (la somme des distances des clusters) avec une autre fonction computeSSE. Si la différence entre le score courant et l’ancien est inférieurs à la tolérance donné, il y a stabilisation et ont arrête. À l'issue de son exécution, l’algorithme des kmeans à alors associé chaque donnée à un groupe.

Pour tester chaque partie de l'algorithme nous allos utiliser quelques données simple :

data = [(1,1),(1,2),(1,3),(5,4),(4,5),(4.5,4.5)]
centers = [(1,2),(4.5,4.5)]
clusertID = [0,0,0,1,1,1]

Associations des points au centres les plus proches

Dans cette étape ont cherche à attribuer un numéro de cluster à chaque point. Chaque cluster a sont « tampon » pour construire la liste des distances et venir prendre le minimum facilement :

def updateClusterID(data, centers):
    clusterID = np.zeros(len(data))
    L = np.zeros(len(centers))
    
    for idx,elm in enumerate(data):
        for jdx,cent in enumerate(centers):
            L[jdx] = np.linealg.norm(elm,cent,2)
        clusterID[idx] = np.argmin(L)

    return clusterID

Avec les données précédemment obtenue, nous pouvons constater et vérifié (à la main) le résultat

updateClusterID(data, centers): [0, 0, 1, 1, 1, 0]

Mise à jours des centres des clusters

Finalement, ont recalcul les coordonnées du centre de chaque cluster

def updateCenters(data, clusterID, R):
    centers = np.zeros((len(data[0]),R))
    count = np.zeros(R)
    
    for idx,elm in enumerate(data):
        centers[clusterID[idx]] = np.sum(elm)
        count[clusterID[idx]] += 1

    return np.nan_to_num(centers / count)

Calcule du score

Pour vérifier l'association nous alons définir une fonction qui correspond à ma somme des erreurs quadratique entre les points et le centre de leur cluster associées :

def computeSSE(data, centers, clusterID):
    somme = 0;
    for i in range(len(data)):
        somme += np.linealg.norm(centers[clusterID[i]], data[i], 2);
    return somme

Par exemple on peu défini quelques données et tester:

computeSSE(data, centers, clusertID): 3.0

Appliquer chaque étapes

Pour résumer, ont affecte chaque point au centre le plus proche et donc le numero de cluster associé. Ont recalcul les centres des clusters et ont calcule la nouvelle erreur. S'il n'y a pas d'amélioration qui dépasse un certain seuil alors ont est dans un minimum local et il y a stabilisation. Bien entendu dans certain cas ont peu tourné autour de ce minimum local sans converger et il suffi de limiter le nombre d'itération ! L'algorithme ce traduit alors par la fonction kmeans :

def kmeans(data, centers, maxIter = 100, tol = 1e-6):
    nData, R = len(data), len(centers)
    
    if nData == 0 or R >= nData:
        return [], []

    clusterID = [0] * nData
    stabilise = False
    oldDistance = float("inf");
    iter = 0
    
    while not stabilise and iter < maxIter:
        clusterID = updateClusterID(data, centers)
        centers = updateCenters(data, clusterID, R)
        curDistance = computeSSE(data, centers, clusterID)
        print("# it ", iter, " SSE = ", curDistance)
        stabilise = abs(curDistance-oldDistance) < tol
        oldDistance = curDistance
        iter += 1

    print("# of iterations:", iter)
    print("SSE = ", oldDistance)
    return clusterID, centers

Utilisation

# Nombre de clusters a priori
centers = [data[randint(0,len(data)-1)] for i in range(3)]
results, centers = kmeans(data, centers)

On peut alors simplement lancer l’application avec différent jeux de testes (2d, 4d) et venir et tester le résultat de l’algorithme avec différents paramètres : tel que le nombre de center/cluster (K).

Comme nous pouvons le constater algorithmie n’est pas stable puisque le choix des centres de départ sont choisi aléatoirement au lancement de l’application ce qui en résulte en une association différente pour chaque éxécution.

Évidement ce type d'analyse existe déjà, par exemple le module sklearn la propose :

from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
kmeans.labels_
kmeans.cluster_centers_