Empirische Auswertung der K-Means-Initialisierung

Einführung

K-Means ist ein Clustering-Algorithmus, der einen Datensatz in k Cluster aufteilt, wobei jeder Punkt dem Cluster angehört, dessen Schwerpunkt am nächsten zu ihm ist. Die Wahl der Initialisierungsmethode für K-Means kann das Performance- und Konvergenzverhalten des Algorithmus erheblich beeinflussen. In diesem Lab werden wir den Einfluss verschiedener Initialisierungsmethoden auf die Konvergenzrobustheit des K-Means-Clustering-Algorithmus evaluieren.

Tipps für die virtuelle Maschine

Nachdem der Start der virtuellen Maschine abgeschlossen ist, klicken Sie in der linken oberen Ecke, um zur Registerkarte Notebook zu wechseln und Jupyter Notebook für die Übung zu nutzen.

Manchmal müssen Sie einige Sekunden warten, bis Jupyter Notebook vollständig geladen ist. Die Validierung von Vorgängen kann aufgrund der Einschränkungen von Jupyter Notebook nicht automatisiert werden.

Wenn Sie während des Lernens Probleme haben, können Sie Labby gerne fragen. Geben Sie nach der Sitzung Feedback ab, und wir werden das Problem für Sie prompt beheben.

Bibliotheken importieren

Wir beginnen mit dem Import der erforderlichen Bibliotheken für das Lab, die numpy, matplotlib und sklearn umfassen.

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm
from sklearn.utils import shuffle
from sklearn.utils import check_random_state
from sklearn.cluster import MiniBatchKMeans
from sklearn.cluster import KMeans

Datensätze generieren

Wir werden einen Datensatz von isotopen Gaußschen Clustern mit großer Abstand generieren. Die Parameter für die Datensatzgenerierung umfassen die Anzahl der Proben pro Zentrum, die Gittergröße, die Skala und die Anzahl der Cluster.

random_state = np.random.RandomState(0)
n_samples_per_center = 100
grid_size = 3
scale = 0.1
n_clusters = grid_size**2

def make_data(random_state, n_samples_per_center, grid_size, scale):
    random_state = check_random_state(random_state)
    centers = np.array([[i, j] for i in range(grid_size) for j in range(grid_size)])
    n_clusters_true, n_features = centers.shape

    noise = random_state.normal(
        scale=scale, size=(n_samples_per_center, centers.shape[1])
    )

    X = np.concatenate([c + noise for c in centers])
    y = np.concatenate([[i] * n_samples_per_center for i in range(n_clusters_true)])
    return shuffle(X, y, random_state=random_state)

X, y = make_data(random_state, n_samples_per_center, grid_size, scale)

Quantitative Evaluation of Initialization Methods

Wir werden die Fähigkeit von K-Means-Initialisierungstrategien zur Herstellung einer robusten Konvergenz des Algorithmus evaluieren. Wir werden die relative Standardabweichung der Trägheit der Clustering berechnen, die die Summe der quadrierten Abstände zum nächsten Clusterzentrum ist. Das erste Diagramm zeigt die beste erreichte Trägheit für jede Kombination des Modells (KMeans oder MiniBatchKMeans) und der Init-Methode (init="random" oder init="k-means++") für zunehmende Werte des n_init-Parameters, der die Anzahl der Initialisierungen steuert.

n_runs = 5
n_init_range = np.array([1, 5, 10, 15, 20])

plt.figure()
plots = []
legends = []

cases = [
    (KMeans, "k-means++", {}, "^-"),
    (KMeans, "random", {}, "o-"),
    (MiniBatchKMeans, "k-means++", {"max_no_improvement": 3}, "x-"),
    (MiniBatchKMeans, "random", {"max_no_improvement": 3, "init_size": 500}, "d-"),
]

for factory, init, params, format in cases:
    print("Evaluation of %s with %s init" % (factory.__name__, init))
    inertia = np.empty((len(n_init_range), n_runs))

    for run_id in range(n_runs):
        X, y = make_data(run_id, n_samples_per_center, grid_size, scale)
        for i, n_init in enumerate(n_init_range):
            km = factory(
                n_clusters=n_clusters,
                init=init,
                random_state=run_id,
                n_init=n_init,
                **params,
            ).fit(X)
            inertia[i, run_id] = km.inertia_
    p = plt.errorbar(
        n_init_range, inertia.mean(axis=1), inertia.std(axis=1), fmt=format
    )
    plots.append(p[0])
    legends.append("%s with %s init" % (factory.__name__, init))

plt.xlabel("n_init")
plt.ylabel("inertia")
plt.legend(plots, legends)
plt.title("Mean inertia for various k-means init across %d runs" % n_runs)

Qualitative Visual Inspection of the Convergence

Wir werden einen einzelnen Durchlauf des MiniBatchKMeans-Schätzers mit init="random" und n_init=1 demonstrieren. Dieser Durchlauf führt zu einer schlechten Konvergenz (lokales Optimum), wobei die geschätzten Zentren zwischen den wahren Clustern stecken bleiben.

km = MiniBatchKMeans(
    n_clusters=n_clusters, init="random", n_init=1, random_state=random_state
).fit(X)

plt.figure()
for k in range(n_clusters):
    my_members = km.labels_ == k
    color = cm.nipy_spectral(float(k) / n_clusters, 1)
    plt.plot(X[my_members, 0], X[my_members, 1], ".", c=color)
    cluster_center = km.cluster_centers_[k]
    plt.plot(
        cluster_center[0],
        cluster_center[1],
        "o",
        markerfacecolor=color,
        markeredgecolor="k",
        markersize=6,
    )
    plt.title(
        "Example cluster allocation with a single random init\nwith MiniBatchKMeans"
    )

plt.show()

Zusammenfassung

In diesem Lab haben wir den Einfluss verschiedener Initialisierungsmethoden auf die Konvergenzrobustheit des K-Means-Clustering-Algorithmus ausgewertet. Wir haben die relative Standardabweichung der Trägheit des Clustering gemessen und einen einzelnen Durchlauf des MiniBatchKMeans-Schätzers mit init="random" und n_init=1 demonstriert. Die Wahl der Initialisierungsmethode für K-Means kann den Algorithmusverhalten und die Konvergenz erheblich beeinflussen.