K 均值初始化的实证评估

简介

K 均值是一种聚类算法，它将一个数据集划分为 k 个簇，其中每个点属于其质心离它最近的簇。K 均值初始化方法的选择会极大地影响算法的性能和收敛性。在本实验中，我们将评估不同初始化方法对 K 均值聚类算法收敛鲁棒性的影响。

虚拟机使用提示

虚拟机启动完成后，点击左上角切换到“笔记本”标签页，以访问 Jupyter Notebook 进行练习。

有时，你可能需要等待几秒钟让 Jupyter Notebook 完成加载。由于 Jupyter Notebook 的限制，操作验证无法自动化。

如果你在学习过程中遇到问题，随时向 Labby 提问。课程结束后提供反馈，我们会立即为你解决问题。

导入库

我们将首先导入本实验所需的库，其中包括 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

生成数据集

我们将生成一个由广泛分布的各向同性高斯簇组成的数据集。数据集生成参数包括每个中心的样本数量、网格大小、比例以及簇的数量。

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)

初始化方法的定量评估

我们将评估 K 均值初始化策略使算法收敛具有鲁棒性的能力。我们将测量聚类惯性的相对标准偏差，惯性是到最近簇中心的平方距离之和。第一张图展示了对于模型（KMeans 或 MiniBatchKMeans）与初始化方法（init="random" 或 init="k-means++"）的每种组合，随着控制初始化次数的 n_init 参数值增加所达到的最佳惯性。

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)

收敛性的定性可视化检查

我们将展示使用 init="random" 和 n_init=1 对 MiniBatchKMeans 估计器进行的一次运行。这次运行导致了较差的收敛（局部最优），估计的中心被困在真实簇之间。

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

总结

在本实验中，我们评估了不同初始化方法对 K 均值聚类算法收敛鲁棒性的影响。我们测量了聚类惯性的相对标准偏差，并展示了使用 init="random" 和 n_init=1 对 MiniBatchKMeans 估计器进行的一次运行。K 均值初始化方法的选择会极大地影响算法的性能和收敛。