K-means++ 是 K-means 算法的一个改进版本，主要解决了初始质心选择的问题，从而提高了聚类的质量和稳定性。在 K-means++ 中，初始质心是按照一种特定的方式逐步选择的，而不是随机选择所有质心。这种方式可以确保初始质心之间尽可能远，从而减少算法陷入局部最优的可能性[^3]。 ### 实现步骤 1. **选择第一个质心**：随机从数据集中选择一个样本作为第一个质心。 2. **选择后续质心**：对于每一个新的质心，选择的概率与当前已选质心到该样本的距离的平方成正比。具体来说，距离越远的样本，被选为下一个质心的概率越高。 3. **重复步骤2**：直到选择了 $ K $ 个质心。 4. **使用标准 K-means 算法**：基于这些初始质心进行标准的 K-means 迭代，直到收敛。 ### Python 实现 下面是一个简单的 Python 实现示例，使用 `sklearn` 库中的 `KMeans` 类，它已经内置了 K-means++ 初始化方法： ```python from sklearn.cluster import KMeans from sklearn.datasets import make_blobs import matplotlib.pyplot as plt # 生成模拟数据 X, y = make_blobs(n_samples=300, centers=4, random_state=42) # 使用 K-means++ 初始化的 KMeans 模型 kmeans = KMeans(n_clusters=4, init='k-means++', max_iter=300, n_init=10) kmeans.fit(X) # 可视化结果 plt.scatter(X[:, 0], X[:, 1], c=kmeans.labels_, cmap='viridis') plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s=200, c='red', label='Centroids') plt.legend() plt.title('K-means++ Clustering') plt.show() ``` ### 解释 - **`init='k-means++'`**：这是关键参数，表示使用 K-means++ 初始化方法来选择初始质心。 - **`n_clusters=4`**：指定要分成的簇数。 - **`max_iter=300`**：每次迭代的最大次数。 - **`n_init=10`**：运行算法的次数，选择最佳结果。 ### 自定义实现 如果你希望不依赖 `sklearn` 而是手动实现 K-means++，可以参考以下步骤： ```python import numpy as np def kmeans_plus_plus(X, K): n_samples, n_features = X.shape centroids = [] # 第一个质心随机选择 first_centroid_idx = np.random.choice(n_samples) centroids.append(X[first_centroid_idx]) # 选择后续的 K-1 个质心 for _ in range(1, K): distances = np.zeros(n_samples) for i in range(n_samples): min_dist = np.inf for centroid in centroids: dist = np.sum((X[i] - centroid) ** 2) if dist < min_dist: min_dist = dist distances[i] = min_dist probabilities = distances / distances.sum() next_centroid_idx = np.random.choice(n_samples, p=probabilities) centroids.append(X[next_centroid_idx]) return np.array(centroids) # 生成模拟数据 X, y = make_blobs(n_samples=300, centers=4, random_state=42) # 使用 K-means++ 初始化的质心 initial_centroids = kmeans_plus_plus(X, K=4) # 可视化初始质心 plt.scatter(X[:, 0], X[:, 1], c='gray', alpha=0.5) plt.scatter(initial_centroids[:, 0], initial_centroids[:, 1], s=200, c='red', label='Initial Centroids') plt.legend() plt.title('K-means++ Initialization') plt.show() ``` ### 解释 - **`kmeans_plus_plus` 函数**：实现了 K-means++ 的初始化过程。 - **`distances` 数组**：用于存储每个样本到最近质心的距离。 - **`probabilities` 数组**：根据距离平方的比例计算每个样本被选为下一个质心的概率。 - **`np.random.choice`**：根据概率分布选择下一个质心。 通过上述代码，你可以手动实现 K-means++ 的初始化过程，并将其应用于实际的聚类任务中。 ###