Evaluation empirique de l'initialisation de K-Means

Introduction

K-means est un algorithme de clustering qui partitionne un ensemble de données en k clusters, où chaque point appartient au cluster dont le centroïde est le plus proche de lui. Le choix de la méthode d'initialisation pour k-means peut avoir un impact considérable sur les performances et la convergence de l'algorithme. Dans ce laboratoire, nous allons évaluer l'impact de différentes méthodes d'initialisation sur la robustesse de convergence de l'algorithme de clustering k-means.

Conseils sur la machine virtuelle

Une fois le démarrage de la machine virtuelle terminé, cliquez dans le coin supérieur gauche pour basculer vers l'onglet Notebook pour accéder à Jupyter Notebook et pratiquer.

Parfois, vous devrez peut-être attendre quelques secondes pour que Jupyter Notebook ait fini de charger. La validation des opérations ne peut pas être automatisée en raison des limitations de Jupyter Notebook.

Si vous rencontrez des problèmes pendant l'apprentissage, n'hésitez pas à demander à Labby. Donnez votre feedback après la session, et nous résoudrons rapidement le problème pour vous.

Skills Graph

Importation des bibliothèques

Nous allons commencer par importer les bibliothèques nécessaires pour le laboratoire, qui incluent numpy, matplotlib, sklearn.

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

Générer des ensembles de données

Nous allons générer un ensemble de données de clusters gaussiens isotrope largement espacés. Les paramètres de génération de l'ensemble de données incluent le nombre d'échantillons par centre, la taille de la grille, l'échelle et le nombre de clusters.

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)

Evaluation quantitative des méthodes d'initialisation

Nous allons évaluer la capacité des stratégies d'initialisation de k-means à rendre la convergence de l'algorithme robuste. Nous allons mesurer l'écart-type relatif de l'inertie du clustering, qui est la somme des distances au carré au centre du cluster le plus proche. La première figure montre la meilleure inertie atteinte pour chaque combinaison du modèle (KMeans ou MiniBatchKMeans) et de la méthode d'initialisation (init="random" ou init="k-means++") pour des valeurs croissantes du paramètre n_init qui contrôle le nombre d'initialisations.

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)

Inspection visuelle qualitative de la convergence

Nous allons démontrer une exécution unique de l'estimateur MiniBatchKMeans en utilisant init="random" et n_init=1. Cette exécution conduit à une mauvaise convergence (optimum local), avec les centres estimés bloqués entre les clusters de vérité terrain.

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()

Sommaire

Dans ce laboratoire, nous avons évalué l'impact de différentes méthodes d'initialisation sur la robustesse de la convergence de l'algorithme de clustering k-means. Nous avons mesuré l'écart-type relatif de l'inertie du clustering et démontré une exécution unique de l'estimateur MiniBatchKMeans en utilisant init="random" et n_init=1. Le choix de la méthode d'initialisation pour k-means peut avoir un impact considérable sur les performances et la convergence de l'algorithme.