# KMeans 聚类算法 Python 实现与深度解析 KMeans 是一种经典的无监督学习算法，其核心目标是通过迭代优化将数据划分为 $K$ 个簇，使得簇内样本距离尽可能小，而簇间距离尽可能大 [ref_2]。以下将从算法原理、代码实现及结果解析三个维度进行详细阐述。 ### 一、 问题解构与方案推演 要实现 KMeans 算法，必须遵循以下逻辑闭环： 1. **数据预处理**：加载并标准化数据，消除量纲影响。 2. **初始化质心**：随机选择 $K$ 个样本点作为初始聚类中心。 3. **迭代分配**：计算每个样本到各质心的距离（通常为欧氏距离），将样本归入距离最近的簇 [ref_1]。 4. **更新质心**：计算每个簇内所有样本的均值，作为新的质心。 5. **收敛判断**：判断质心是否发生变化或达到最大迭代次数，若满足则结束，否则回到步骤 3 [ref_2]。 ### 二、 Python 代码实现与详细解析 以下代码不依赖 `sklearn` 等高级库，仅使用 `numpy` 和 `matplotlib` 从零实现算法逻辑，以便深入理解其内部机制 [ref_2]。 #### 1. 环境准备与数据加载 首先，我们需要生成模拟数据并进行可视化。为了让聚类效果明显，我们生成几个呈团状分布的数据点。 ```python import numpy as np import matplotlib.pyplot as plt # 设置随机种子，保证结果可复现 np.random.seed(42) # 模拟生成数据：生成3个簇中心 # 簇1 center1 = [2, 2] # 簇2 center2 = [8, 8] # 簇3 center3 = [5, 5] # 在中心点附近生成随机点 data1 = np.random.randn(50, 2) + center1 data2 = np.random.randn(50, 2) + center2 data3 = np.random.randn(50, 2) + center3 # 合并所有数据 data = np.vstack((data1, data2, data3)) # 可视化原始数据分布 plt.figure(figsize=(6, 6)) plt.scatter(data[:, 0], data[:, 1], c='gray', s=20, alpha=0.6) plt.title("Raw Data Distribution") plt.show() ``` #### 2. 核心算法实现 这部分代码封装了距离计算、质心更新和迭代逻辑。 ```python def calculate_distance(point, centroid): """ 计算点与质心之间的欧氏距离 :param point: 单个数据点 :param centroid: 单个质心 :return: 欧氏距离 """ return np.sqrt(np.sum((point - centroid) ** 2)) def kmeans(dataset, k, max_iters=100): """ KMeans算法实现函数 :param dataset: 数据集 :param k: 聚类簇数 :param max_iters: 最大迭代次数 :return: 质心列表, 每个点的簇索引 """ # 1. 随机初始化质心：从数据集中随机选择k个点作为初始质心 m, n = dataset.shape # 随机生成k个索引 random_indices = np.random.choice(m, k, replace=False) centroids = dataset[random_indices] # 用于存储每个点的簇分配结果，初始化为全0矩阵 cluster_assessment = np.zeros((m, 2)) # 第一列存储簇索引，第二列存储误差（距离） cluster_changed = True iter_count = 0 while cluster_changed and iter_count < max_iters: cluster_changed = False iter_count += 1 # 2. 分配样本：遍历每个点，计算其到所有质心的距离，归入最近的簇 for i in range(m): min_dist = np.inf min_index = -1 for j in range(k): dist = calculate_distance(dataset[i], centroids[j]) if dist < min_dist: min_dist = dist min_index = j # 如果当前点的簇分配发生了变化，标记为True以继续迭代 if cluster_assessment[i, 0] != min_index: cluster_changed = True # 更新分配结果：簇索引和误差平方 cluster_assessment[i, :] = min_index, min_dist**2 # 3. 更新质心：计算每个簇的均值，作为新质心 for j in range(k): # 获取属于第j个簇的所有点 points_in_cluster = dataset[cluster_assessment[:, 0] == j] if len(points_in_cluster) > 0: # 计算均值作为新质心 centroids[j] = np.mean(points_in_cluster, axis=0) print(f"Algorithm converged after {iter_count} iterations.") return centroids, cluster_assessment ``` #### 3. 算法执行与可视化 调用上述函数进行聚类，并绘制结果。 ```python # 定义聚类数量 k = 3 # 执行KMeans算法 final_centroids, final_assessment = kmeans(data, k) # 提取每个点的簇标签 labels = final_assessment[:, 0].astype(int) # 可视化聚类结果 plt.figure(figsize=(8, 6)) colors = ['r', 'g', 'b', 'y', 'c'] # 绘制数据点，根据簇标签着色 for i in range(k): points = data[labels == i] plt.scatter(points[:, 0], points[:, 1], c=colors[i], s=20, label=f'Cluster {i+1}') # 绘制最终质心 plt.scatter(final_centroids[:, 0], final_centroids[:, 1], c='black', marker='x', s=200, linewidths=3, label='Centroids') plt.title("KMeans Clustering Results") plt.legend() plt.grid(True) plt.show() ``` ### 三、 深度解析与算法局限性 #### 1. 核心步骤解析 * **距离度量**：代码中采用了欧氏距离来衡量样本与质心的相似度，这是 KMeans 中最常用的度量方式 [ref_1]。 * **质心更新策略**：通过计算簇内所有样本坐标的算术平均值来更新质心位置。这种策略能够最小化簇内误差平方和（SSE），即目标函数 $J = \sum \sum ||x_i^{(j)} - c_j||^2$ [ref_2]。 * **收敛条件**：当所有样本的簇归属不再发生变化，或者达到预设的最大迭代次数时，算法停止。这保证了算法在有限时间内结束 [ref_1]。 #### 2. 算法的局限性 尽管 KMeans 简单高效，但在实际应用中存在以下问题： * **对初始值敏感**：由于初始质心是随机选择的，不同的初始点可能导致不同的聚类结果，甚至陷入局部最优解。解决方案是使用 KMeans++ 算法进行初始化 [ref_2]。 * **难以处理非凸簇**：KMeans 假设簇是凸形的（即球形），对于环形、月牙形等复杂几何结构的数据，聚类效果往往很差 [ref_2]。 * **K 值的选择**：算法需要预先指定 $K$ 值，但在无监督学习中，往往并不知道数据应该分成几类。通常需要结合“手肘法”或“轮廓系数”来确定最佳 $K$ 值。 ### 四、 总结 通过上述 Python 代码，我们从底层实现了 KMeans 聚类算法的完整流程，包括数据准备、距离计算、迭代更新和结果可视化。理解这一过程有助于掌握机器学习中“迭代优化”的核心思想。在实际工程中，虽然通常会直接调用 `sklearn.cluster.KMeans`，但了解其背后的逻辑对于调参和解决异常问题至关重要 [ref_2]。