在机器学习领域，K-Means算法是一种广泛使用的聚类方法。该算法通过迭代地移动聚类中心，将数据点分配给最近的聚类中心，以最小化每个点到其聚类中心的距离的平方和。然而，K-Means算法的一个关键问题是其对初始聚类中心的选择非常敏感，这可能导致算法收敛到局部最优解而非全局最优解。为了解决这个问题，研究者们提出了多种初始化策略，如“k-means++”和“随机初始化”。本文旨在评估这些初始化策略对于算法收敛鲁棒性的影响，通过分析聚类中心的相对标准偏差来衡量。
实验中，使用了两种K-Means模型：标准的KMeans和MiniBatchKMeans。对于每种模型，分别采用了两种初始化方法：“k-means++”和“随机初始化”。通过改变参数n_init的值，即初始化的次数，来评估不同初始化策略的效果。实验中，生成了一个2D网格的高斯聚类数据集，这些聚类之间间隔较远，以便于观察初始化策略对算法收敛的影响。
实验结果表明，对于KMeans模型，使用“k-means++”初始化策略相比于“随机初始化”策略，能够更有效地提高算法的收敛鲁棒性。具体来说，随着n_init参数值的增加，使用“k-means++”初始化的KMeans模型的聚类中心的相对标准偏差显著降低，表明算法的收敛更加稳定。而对于MiniBatchKMeans模型，虽然“k-means++”初始化策略同样能够提高收敛鲁棒性，但其效果不如KMeans模型明显。这可能是因为MiniBatchKMeans模型在每次迭代中只使用部分数据，从而减少了初始化策略对算法收敛的影响。
以下是使用Python和scikit-learn库实现上述实验的代码示例。代码中首先定义了数据生成函数make_data，用于生成2D网格的高斯聚类数据集。然后，定义了实验的主函数，其中使用了不同的K-Means模型和初始化策略，并通过改变n_init参数的值来评估不同初始化策略的效果。最后，代码中还包含了绘制实验结果的函数，以直观地展示不同初始化策略对算法收敛的影响。
import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import KMeans, MiniBatchKMeans
from sklearn.utils import check_random_state, shuffle
# 设置随机数种子以保证实验结果的可重复性
random_state = np.random.RandomState(0)
# 数据生成函数
def make_data(random_state, n_samples_per_center, grid_size, scale):
centers = np.array([[i, j] for i in range(grid_size) for j in range(grid_size)])
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(len(centers))])
return shuffle(X, y, random_state=random_state)
# 实验的主函数
def main():
n_runs = 5
n_init_range = np.array([1, 5, 10, 15, 20])
n_samples_per_center = 100
grid_size = 3
scale = 0.1
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:
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=len(centers), 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)
plt.show()
if __name__ == "__main__":
main()