Algoritmo de agrupamiento K-Means | Aprendizaje automático

Introducción

K-means es un algoritmo de agrupamiento que divide un conjunto de datos en k clusters, donde cada punto pertenece al cluster cuyo centroide está más cerca de él. La elección del método de inicialización para k-means puede afectar en gran medida el rendimiento y la convergencia del algoritmo. En este laboratorio, evaluaremos el impacto de diferentes métodos de inicialización en la robustez de convergencia del algoritmo de agrupamiento k-means.

Consejos sobre la VM

Una vez que se haya iniciado la VM, haga clic en la esquina superior izquierda para cambiar a la pestaña Cuaderno y acceder a Jupyter Notebook para practicar.

A veces, es posible que tenga que esperar unos segundos a que Jupyter Notebook termine de cargarse. La validación de las operaciones no se puede automatizar debido a las limitaciones de Jupyter Notebook.

Si tiene problemas durante el aprendizaje, no dude en preguntar a Labby. Deje sus comentarios después de la sesión y lo resolveremos rápidamente para usted.

Importar bibliotecas

Comenzaremos importando las bibliotecas necesarias para el laboratorio, que incluyen 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

Generar conjuntos de datos

Generaremos un conjunto de datos de clusters gaussianos isotrópicos ampliamente espaciados. Los parámetros de generación del conjunto de datos incluyen el número de muestras por centro, el tamaño de la cuadrícula, la escala y el número 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)

Evaluación cuantitativa de los métodos de inicialización

Evaluaremos la capacidad de las estrategias de inicialización de k-means para hacer que el algoritmo converja de manera robusta. Mediremos la desviación estándar relativa de la inercia del agrupamiento, que es la suma de las distancias al cuadrado al centro del cluster más cercano. La primera gráfica muestra la mejor inercia alcanzada para cada combinación del modelo (KMeans o MiniBatchKMeans) y el método de inicialización (init="random" o init="k-means++") para valores crecientes del parámetro n_init que controla el número de inicializaciones.

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("Evaluación de %s con %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 con %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)

Inspección visual cualitativa de la convergencia

Demostraremos una sola ejecución del estimador MiniBatchKMeans usando init="random" y n_init=1. Esta ejecución conduce a una mala convergencia (óptimo local), con los centros estimados atascados entre los clusters reales.

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

Resumen

En este laboratorio, evaluamos el impacto de diferentes métodos de inicialización en la robustez de la convergencia del algoritmo de agrupamiento k-means. Medimos la desviación estándar relativa de la inercia del agrupamiento y demostramos una sola ejecución del estimador MiniBatchKMeans usando init="random" y n_init=1. La elección del método de inicialización para k-means puede afectar en gran medida el rendimiento y la convergencia del algoritmo.

Evaluación empírica de la inicialización de K-Means