【字节跳动】数据挖掘面试题0007：Kmeans原理，何时停止迭代

K-means 原理与迭代停止条件

以下是针对数据挖掘面试题中K-Means原理及迭代停止条件的清晰解析，结合算法本质与面试考点整理，便于你快速掌握核心要点。

---

⚙️ 一、K-Means核心思想

K-Means是无监督聚类算法，目标是将n个数据点划分为k个簇（cluster），使得簇内距离最小化，簇间距离最大化。其迭代过程是EM（Expectation-Maximization）算法的特例，分两步交替进行：

• 1. E步（分配点）：固定质心，将每个点分配到最近的质心所属簇。
• 2. M步（更新质心）：固定簇分配，根据簇内点重新计算质心位置。

💡 通俗比喻：
假设有k个班主任（质心）在教室随机站位，学生（数据点）选择最近的班主任排队。
班主任随后走到队伍中心点，学生重新排队。重复此过程直到班主任不再移动。

---

🔁 二、迭代步骤详解

以下流程图展示单次迭代过程：

关键数学操作

• 距离计算：常用欧式距离$$\Vert x_i-{\mu }_j{\Vert }^2$$，决定点所属簇。
• 质心更新：质心 ${\mu }_j$ = $\frac{1}{|C_j|}{\sum }_{x_i\in C_j}{x}_i$，即簇内所有点的均值。

---

⏹️ 三、何时停止迭代？

停止条件决定算法收敛时机，常见以下四类：

停止条件类型	判断标准	应用场景	代码参数示例
1. 质心变化量≤阈值	新旧质心距离 < ε（如 ε=1e-4）	精确收敛要求高时	tol=0.0001
2. 簇分配不再变化	无点改变所属簇	需稳定分类结果时	无显式参数，自动检测
3. 目标函数收敛	SSE（簇内平方和）下降量 < δ（如 δ=0.01）	关注聚类质量优化时	通过SSE监控
4. 达到最大迭代次数	迭代次数 ≥ max_iter（如 300）	防止无限循环/耗时敏感场景	max_iter=100

• Kmeans 算法停止迭代的条件通常有以下几种：
  • 质心不再变化：新计算的质心与上一次的质心完全相同（或差异小于某个极小阈值），说明聚类已经收敛。
  • 达到最大迭代次数：设置一个最大迭代次数（如 100 次），避免算法陷入无限循环。
  • 簇分配不再变化：所有数据点的簇分配在两次迭代之间没有改变。

📌 注意：

• 条件1~3满足任一即停止，条件4是 强制终止 的保底策略。
• 条件1与2不等价：质心微小移动可能不引起重新分配，但SSE仍在优化。

Kmeans 算法实现代码

import numpy as np
import matplotlib.pyplot as pltdef kmeans(X, K, max_iterations=100):"""K-means聚类算法实现参数:X: 输入数据，形状为(n_samples, n_features)K: 聚类的数量max_iterations: 最大迭代次数返回:centroids: 最终的质心坐标，形状为(K, n_features)labels: 每个数据点的聚类标签，形状为(n_samples,)"""# 1. 随机初始化质心：从输入数据中随机选择K个点作为初始质心# replace=False# 表示抽样时不允许重复选择同一个元素，确保每次选择的索引都是唯一的。centroids = X[np.random.choice(len(X), K, replace=False)]for iteration in range(max_iterations):# 2. 分配数据点到最近的质心# 计算每个数据点到每个质心的欧氏距离# np.linalg.norm：计算向量的范数（默认是欧氏范数，即平方和开根号）distances = np.array([np.linalg.norm(X - centroid, axis=1) for centroid in centroids])# 为每个数据点分配最近质心的索引作为聚类标签# NumPy 中用于查找数组中最小值索引的函数调用，在 Kmeans 算法中用于将每个数据点分配到最近的质心。labels = np.argmin(distances, axis=0)# 3. 更新质心：计算每个簇内所有点的平均值作为新质心new_centroids = np.array([X[labels == k].mean(axis=0) for k in range(K)])# 检查停止条件：如果新旧质心之间的差异小于阈值，则认为算法收敛# np.allclose(centroids, new_centroids) 是 NumPy 中用于比较两个数组是否几乎相等的函数，在 Kmeans 算法中用于判断聚类是否收敛。if np.allclose(centroids, new_centroids):print(f"Converged after {iteration+1} iterations")breakcentroids = new_centroidsreturn centroids, labels# 生成示例数据：创建3个不同的高斯分布数据集
np.random.seed(42)  # 设置随机种子，确保结果可重现
X = np.vstack([np.random.normal([0, 0], 1, size=(100, 2)),    # 第一个簇：均值[0,0]，标准差1np.random.normal([5, 5], 1, size=(100, 2)),    # 第二个簇：均值[5,5]，标准差1np.random.normal([10, 0], 1, size=(100, 2))    # 第三个簇：均值[10,0]，标准差1
])# 运行Kmeans算法，将数据聚为3类
K = 3
centroids, labels = kmeans(X, K)# 可视化聚类结果
plt.figure(figsize=(8, 6))
# 绘制数据点，使用不同颜色表示不同的簇
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', alpha=0.6)
# 绘制最终的质心位置，使用红色X标记
plt.scatter(centroids[:, 0], centroids[:, 1], c='red', s=200, marker='X')
plt.title('Kmeans Clustering Results')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()

---

⚠️ 四、面试常见扩展问题

1. K值如何选择？

• 肘部法则（Elbow Method）：绘制K-SSE曲线，选SSE骤降点。
• 轮廓系数（Silhouette Score）：衡量簇内紧密度与簇间分离度，接近1表示聚类合理。

2. 初始质心影响结果吗？

• 随机初始化可能导致局部最优。
• 改进方案：K-Means++，通过概率分布选择分散的初始质心。

3. 算法缺陷与改进

• 缺陷：对异常值敏感、假设簇为球形分布、依赖K值预设。
• 改进：
  • 异常值处理：离群点检测（如DBSCAN）。
  • 非球形簇：谱聚类或核K-Means。

---

💎 五、总结与面试回答要点

• 原理：EM框架下的交替优化（分配点 → 更新质心）。
• 停止条件：质心稳定/簇分配不变/SSE收敛/达到最大迭代次数。
• 考点延伸：
  • 结合RFM模型解释K-Means应用（用户分层场景）。
  • 时间复杂度：$O(K\cdot n\cdot d)$（n样本数，d特征数，K簇数）。