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?n?d)$（n樣本數，d特征數，K簇數）。