4. Wiederholen Sie die Schritte 2 und 3

Danach werden die Clusterzuordnung und die Neuberechnung des Schwerpunkts ** wiederholt **. Wie es aussieht, sehen Sie in der Animation unten. Hier ist die Farbe des Schwerpunkts für eine einfache Anzeige schwarz. Am Ende können Sie sehen, dass es konvergiert hat und sich die Position des Schwerpunkts nicht geändert hat.

Wenn Sie sich das Standbild ansehen, können Sie auch sehen, dass sich der Schwerpunkt in der folgenden Flugbahn bewegt.

Formalisierung des Algorithmus

Der oben beschriebene K-Means-Algorithmus kann wie folgt im Code zusammengefasst werden.

#Initialisierungsschritt für den Schwerpunkt
centroids = kmeans_init_centroids(X, K)

for iter in range(iterations):

    #Schritte zur Clusterzuweisung:Weisen Sie den Cluster zu, zu dem der Schwerpunkt gehört, der den einzelnen Daten am nächsten liegt.
    #idx ist eine Liste, idx[i]Speichert den Index des Schwerpunkts, der den i-ten Daten zugeordnet ist
    idx = find_closest_centroids(X, centroids)

    #Bewegungsschritt des Schwerpunkts:Berechnen Sie den Durchschnitt im Cluster basierend auf der Schwerpunktzuweisung
    centroids = compute_centroids(X, idx, K)

Der Algorithmus hat zwei Eingaben:

• Anzahl der Cluster $ K $
• Trainingssatz {$ x ^ {(1)}, x ^ {(2)}, ..., x ^ {(m)} $}, $ x ^ {(i)} \ in \ mathbb {R} ^ n $

Da K-Means unbeaufsichtigtes Lernen ist, ist der Trainingssatz nicht gekennzeichnet. Jede Trainingsdaten $ x ^ {(i)} $ ist ein $ n $ Dimensionsvektor. Jedes entspricht dem Kreis in der Abbildung. Außerdem muss die Anzahl der Cluster im Voraus festgelegt werden.

Nachdem wir die Eingabedaten kennen, werfen wir einen Blick auf jeden Schritt des Algorithmus.

Initialisierung des Schwerpunkts

Initialisieren Sie zunächst den Schwerpunkt. Der Schwerpunkt ist ein $ n $ -Dimensionsvektor, der durch $ u ^ {(j)} $ dargestellt wird, und es gibt $ K $. In der Abbildung entspricht es dem Punkt des Sterns.

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

Als Methode zum Initialisieren des Schwerpunkts aus dem Trainingssatz $ x ^ {(1)}, x ^ {(2)}, ..., x ^ {(m)} \ in \ mathbb {R} ^ n $ Es gibt eine Methode, um $ K $ Stücke zufällig auszuwählen. Wählen Sie nach dem zufälligen Mischen des Trainingssatzes das erste $ K $ als Schwerpunkt aus.

Bei der Implementierung als Code sieht es folgendermaßen aus:

from numpy import *


def kmeans_init_centroids(X, K):
    #Initialisieren Sie so, dass der Schwerpunkt zufällige Daten sind

    #Sortieren Sie die Trainingsdaten nach dem Zufallsprinzip
    rand_X = random.permutation(X)

    #Nehmen Sie das erste K als Schwerpunkt an
    centroids = rand_X[:K]

    return centroids

Clusterzuordnung

Weisen Sie nach der Initialisierung des Schwerpunkts jedem Daten einen Cluster zu. Suchen Sie insbesondere den Schwerpunkt $ u_j $, der den Trainingsdaten $ x ^ {(i)} $ am nächsten liegt, und weisen Sie einen Cluster dieses Schwerpunkts zu.

Um den Schwerpunkt zu finden, der den Daten am nächsten liegt, ermitteln Sie das Quadrat der Entfernung wie folgt. Ordnen Sie eine Gruppe von Schwerpunkten zu, die das Quadrat der Entfernung minimiert.

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

Wobei $ idx ^ {(i)} $ der Index des Schwerpunkts ist, der $ x ^ {(i)} $ am nächsten liegt, und $ u_j $ die Koordinate des $ j $ -ten Schwerpunkts ist.

Eine einfache Implementierung mit numpy sieht folgendermaßen aus:

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

Mit scipys scipy.spatial.distance.cdist können Sie es wie folgt kurz schreiben. In cdist sind verschiedene Methoden zur Entfernungsberechnung definiert. Diesmal habe ich unter anderem die quadratische Distanz verwendet. Die Leistung ist auch hier besser als der obige naive Code.

import scipy.spatial.distance
from numpy import *


def find_closest_centroids(X, centroids):
    sqdists = scipy.spatial.distance.cdist(centroids, X, 'sqeuclidean')  #Finden Sie den quadratischen Abstand
    idx = argmin(sqdists, axis=0)  #Index des nächstgelegenen Schwerpunkts für jede Daten

    return idx

Neuberechnung des Schwerpunkts

Berechnen Sie den Schwerpunkt neu, nachdem Sie die Daten dem Cluster zugewiesen haben.

Nachdem alle Daten dem Cluster zugewiesen wurden, besteht der nächste Schritt darin, den Schwerpunkt neu zu berechnen. Hier berechnen wir den Durchschnitt der dem Cluster zugewiesenen Daten. Führen Sie für alle Schwerpunkte $ k $ die folgende Formel aus.

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

Wobei $ C_k $ der Datensatz ist, dem der Schwerpunkt $ k $ zugewiesen ist. Insbesondere wenn die beiden Daten $ x ^ {(3)} $ und $ x ^ {(5)} $ dem Schwerpunkt $ k = 2 $ zugeordnet sind, dann ist $ u_2 = \ frac {1} {2 } (x ^ {(3)} + x ^ {(5)}) $.

Eine einfache Implementierung würde folgendermaßen aussehen:

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]     #Rufen Sie die dem Cluster k zugewiesenen Daten ab
        count = temp.shape[0]  #Anzahl der dem Cluster k zugewiesenen Daten

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

    return centroids

Wenn Sie es mit der mittleren Funktion von numpy kurz schreiben, sieht es so aus.

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

Bildkompression

Überblick

Nachdem die Erklärung des Algorithmus abgeschlossen ist, gehen wir zum Hauptthema der Bildkomprimierung über. Bilder können auch mithilfe des K-Means-Algorithmus komprimiert werden. Verwenden Sie grob gesagt K-Means, um die Farbe $ K $ auszuwählen, die zur Darstellung des komprimierten Bildes verwendet wird. Es wird komprimiert, indem die Pixel des Originalbilds durch diese $ K $ -Farbe ersetzt werden. Im Folgenden wird es als $ K = 16 $ erklärt.

Wie man Farben ausdrückt

Wenn die Pixel des Bildes eine 24-Bit-Farbdarstellung sind, können sie in 3 8-Bit-Darstellungen zerlegt werden. Jedes 8-Bit ist ** rot ** </ font>, ** blau ** </ font>, ** Es entspricht grün ** </ font> und ist sogenanntes RGB. Da es 8 Bits sind, können Werte von 0 bis 255 ($ 2 ^ 0 bis 2 ^ 8 -1 $) angenommen werden. Aus diesem Grund enthält die Kombination dieser Werte eine Vielzahl von Farben im Bild. Hier reduzieren wir diese Zahl jedoch auf $ K = 16 $ Farben. Durch Reduzieren der Anzahl von Farben auf 16 Farben sollte jedes Pixel durch 4 Bits dargestellt werden können. ($ 16 = 2 ^ 4 $)

128 x 128 x 24 = 393216 bit

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