4. Répétez les étapes 2 et 3

Après cela, l'allocation des grappes et le recalcul du centre de gravité sont ** répétés **. Vous pouvez voir à quoi cela ressemble dans l'animation ci-dessous. Ici, la couleur du centre de gravité est noire pour une visualisation facile. À la fin, vous pouvez voir qu'il a convergé et que la position du centre de gravité n'a pas changé.

De plus, si vous regardez l'image fixe, vous pouvez voir que le centre de gravité se déplace dans la trajectoire suivante.

Formalisation de l'algorithme

L'algorithme K-Means décrit ci-dessus peut être résumé dans le code comme suit.

#Étape d'initialisation du centre de gravité
centroids = kmeans_init_centroids(X, K)

for iter in range(iterations):

    #Étapes d'allocation de cluster:Attribuez le cluster auquel appartient le centre de gravité le plus proche de chaque donnée.
    #idx est une liste, idx[i]Stocke l'indice du centre de gravité attribué aux i-èmes données
    idx = find_closest_centroids(X, centroids)

    #Étape de mouvement du centre de gravité:Calculer la moyenne dans le cluster en fonction de l'affectation du centre de gravité
    centroids = compute_centroids(X, idx, K)

Il y a deux entrées dans l'algorithme:

• Nombre de clusters $ K $
• Ensemble d'entraînement {$ x ^ {(1)}, x ^ {(2)}, ..., x ^ {(m)} $}, $ x ^ {(i)} \ in \ mathbb {R} ^ n $

Puisque K-Means est un apprentissage non supervisé, l'ensemble d'apprentissage n'est pas étiqueté. Chaque donnée d'apprentissage $ x ^ {(i)} $ est un vecteur de dimension $ n $. Chacun correspond au cercle de la figure. De plus, le nombre de grappes doit être déterminé à l'avance.

Maintenant que nous connaissons les données d'entrée, jetons un œil à chaque étape de l'algorithme.

Initialisation du centre de gravité

Tout d'abord, initialisez le centre de gravité. Le centre de gravité est un vecteur de dimension $ n $ représenté par $ u ^ {(j)} $, et il y a $ K $. Sur la figure, cela correspond au point de l'étoile.

u^{(1)}, u^{(2)},...,u^{(K)} \in \mathbb{R}^n

Comme méthode d'initialisation du centre de gravité, à partir de l'ensemble d'apprentissage $ x ^ {(1)}, x ^ {(2)}, ..., x ^ {(m)} \ in \ mathbb {R} ^ n $ Il existe une méthode pour sélectionner au hasard des pièces de $ K $. Plus précisément, après avoir mélangé au hasard l'ensemble d'entraînement, sélectionnez le premier $ K $ comme centre de gravité.

Lorsqu'il est implémenté sous forme de code, il ressemble à ceci:

from numpy import *


def kmeans_init_centroids(X, K):
    #Initialisez pour que le centre de gravité soit des données aléatoires

    #Trier les données d'entraînement de manière aléatoire
    rand_X = random.permutation(X)

    #Adoptez le premier K comme centre de gravité
    centroids = rand_X[:K]

    return centroids

Allocation de cluster

Une fois le centre de gravité initialisé, attribuez un cluster à chaque donnée. Plus précisément, trouvez le centre de gravité $ u_j $ le plus proche de chaque donnée d'apprentissage $ x ^ {(i)} $ et attribuez un cluster de ce centre de gravité.

Pour trouver le centre de gravité le plus proche des données, recherchez le carré de la distance comme suit. Allouez un groupe de centres de gravité qui minimise le carré de la distance.

idx^{(i)} := argmin_j ||x^{(i)} − μ_j||^2

Où $ idx ^ {(i)} $ est l'indice du centre de gravité le plus proche de $ x ^ {(i)} $ et $ u_j $ est la coordonnée du $ j $ ème centre de gravité.

Une implémentation simple utilisant numpy ressemble à ceci:

import sys
from numpy import *


def find_closest_centroids(X, centroids):
    K = centroids.shape[0]
    m = X.shape[0]
    idx = zeros((m, 1))
    for i in range(m):
        lowest = sys.maxint
        lowest_index = 0

        for j in range(K):
            cost = X[i] - centroids[j]
            cost = cost.T.dot(cost)
            if cost < lowest:
                lowest_index = j
                lowest = cost

        idx[i] = lowest_index

    return idx

En utilisant scipy.spatial.distance.cdist de scipy, vous pouvez l'écrire brièvement comme suit. Différentes méthodes de calcul de distance sont définies dans cdist. Parmi eux, cette fois j'ai utilisé la distance au carré. Les performances sont également meilleures ici que le code naïf ci-dessus.

import scipy.spatial.distance
from numpy import *


def find_closest_centroids(X, centroids):
    sqdists = scipy.spatial.distance.cdist(centroids, X, 'sqeuclidean')  #Trouvez la distance au carré
    idx = argmin(sqdists, axis=0)  #Index du centre de gravité le plus proche pour chaque donnée

    return idx

Recalcul du centre de gravité

Après avoir alloué les données au cluster, recalculez le centre de gravité.

Une fois que toutes les données ont été affectées au cluster, l'étape suivante consiste à recalculer le centre de gravité. Ici, nous calculons la moyenne des données affectées au cluster. Pour tout centre de gravité $ k $, exécutez la formule suivante.

u_k := \frac{1}{|C_k|} \sum_{i \in C_k} x^{(i)}

Où $ C_k $ est un jeu de données avec un centre de gravité $ k $ attribué. Plus précisément, si les deux données $ x ^ {(3)} $ et $ x ^ {(5)} $ sont affectées au centre de gravité $ k = 2 $, alors $ u_2 = \ frac {1} {2 } (x ^ {(3)} + x ^ {(5)}) $.

Une implémentation simple ressemblerait à ceci:

from numpy import *


def compute_centroids(X, idx, K):
    m, n = X.shape
    centroids = zeros((K, n))

    for k in range(K):
        temp = X[idx == k]     #Récupérer les données affectées au cluster k
        count = temp.shape[0]  #Nombre de données allouées au cluster k

        for j in range(n):
            centroids[k, j] = sum(temp[:, j]) / count

    return centroids

Si vous l'écrivez court en utilisant la fonction moyenne de numpy, cela ressemblera à ceci.

from numpy import *


def compute_centroids(X, idx, K):
    m, n = X.shape
    centroids = zeros((K, n))

    for k in range(K):
        centroids[k] = mean(X[idx == k], axis=0)

    return centroids

Compression d'image

Aperçu

Maintenant que l'explication de l'algorithme est terminée, passons au sujet principal de la compression d'image. Les images peuvent également être compressées en appliquant l'algorithme K-Means. En gros, utilisez K-Means pour sélectionner la couleur $ K $ utilisée pour représenter l'image compressée. Il compresse en remplaçant les pixels de l'image d'origine par cette couleur $ K $. Dans ce qui suit, il sera expliqué comme $ K = 16 $.

Comment exprimer les couleurs

Si les pixels de l'image sont une représentation couleur 24 bits, ils peuvent être décomposés en 3 représentations 8 bits. Chaque 8 bits est ** rouge ** </ font>, ** bleu ** </ font>, ** Il correspond au vert ** </ font> et s'appelle RVB. Puisqu'il fait 8 bits, il peut prendre des valeurs de 0 à 255 ($ 2 ^ 0 à 2 ^ 8 -1 $) respectivement. C'est pourquoi la combinaison de ces valeurs fait que l'image contient une myriade de couleurs, mais ici nous réduisons ce nombre à $ K = 16 $ couleurs. En réduisant le nombre de couleurs à 16 couleurs, chaque pixel devrait pouvoir être représenté par 4 bits. (16 $ = 2 ^ 4 $)

128 x 128 x 24 = 393216 bit

16 x 24 + 128 x 128 x 4 = 65920 bit