Avaliação Empírica da Inicialização do K-Means

Introdução

K-means é um algoritmo de agrupamento que particiona um conjunto de dados em k clusters, onde cada ponto pertence ao cluster cujo centroide está mais próximo dele. A escolha do método de inicialização para o k-means pode impactar significativamente o desempenho e a convergência do algoritmo. Neste laboratório, avaliaremos o impacto de diferentes métodos de inicialização na robustez da convergência do algoritmo de agrupamento k-means.

Dicas da Máquina Virtual

Após o arranque da VM, clique no canto superior esquerdo para mudar para a aba Notebook para aceder ao Jupyter Notebook para a prática.

Por vezes, pode ser necessário esperar alguns segundos para o Jupyter Notebook terminar de carregar. A validação das operações não pode ser automatizada devido a limitações no Jupyter Notebook.

Se tiver problemas durante o aprendizado, não hesite em contactar o Labby. Forneça feedback após a sessão e resolveremos prontamente o problema para si.

Importar Bibliotecas

Começaremos importando as bibliotecas necessárias para o laboratório, incluindo numpy, matplotlib, e 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

Gerar Conjuntos de Dados

Vamos gerar um conjunto de dados composto por clusters gaussianos isotrópicos amplamente espaçados. Os parâmetros de geração de dados incluem o número de amostras por centro, o tamanho da grade, a escala e o 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)

Avaliação Quantitativa dos Métodos de Inicialização

Avaliaremos a capacidade das estratégias de inicialização do k-means em tornar a convergência do algoritmo robusta. Mediremos o desvio padrão relativo da inércia do agrupamento, que é a soma das distâncias quadradas aos centros de cluster mais próximos. O primeiro gráfico mostra a melhor inércia alcançada para cada combinação do modelo (KMeans ou MiniBatchKMeans) e do método de inicialização (init="random" ou init="k-means++") para valores crescentes do parâmetro n_init, que controla o número de inicializações.

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("Avaliação de %s com inicialização %s" % (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 com inicialização %s" % (factory.__name__, init))

plt.xlabel("n_init")
plt.ylabel("inércia")
plt.legend(plots, legends)
plt.title("Inércia média para diferentes inicializações k-means em %d execuções" % n_runs)

Inspeção Visual Qualitativa da Convergência

Demonstraremos uma única execução do estimador MiniBatchKMeans usando init="random" e n_init=1. Essa execução leva a uma má convergência (ótimo local), com os centros estimados presos entre os clusters verdadeiros.

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(
        "Exemplo de alocação de clusters com uma única inicialização aleatória\ncom MiniBatchKMeans"
    )

plt.show()

Resumo

Neste laboratório, avaliamos o impacto de diferentes métodos de inicialização na robustez da convergência do algoritmo de agrupamento k-means. Medimos o desvio padrão relativo da inércia do agrupamento e demonstramos uma única execução do estimador MiniBatchKMeans usando init="random" e n_init=1. A escolha do método de inicialização para o k-means pode impactar significativamente o desempenho e a convergência do algoritmo.