1. 算法邏輯

K均值是一種無監督聚類算法，核心目標是將n個數據點劃分為k個簇（cluster），使得同一簇內數據點相似度高，不同簇間差異大。算法流程如下：

graph TDA[初始化K個質心] --> B[分配數據點到最近質心]B --> C[重新計算質心位置]C --> D{質心是否變化？}D -- 是 --> BD -- 否 --> E[輸出聚類結果]

2. 算法原理與數學推導

2.1 目標函數

最小化簇內平方和（Within-Cluster Sum of Squares, WCSS）：
$$J=\sum _{i=1}^k\sum _{x\in C_i}\Vert x?{\mu }_i{\Vert }^2$$
其中：

• $C_i$ 表示第i個簇
• ${\mu }_i$ 表示第i個簇的質心
• $\Vert x?{\mu }_i\Vert$ 表示歐氏距離

2.2 數學推導

步驟1：初始化質心
隨機選擇k個數據點作為初始質心：
$${\mu }_1^{(0)},{\mu }_2^{(0)},...,{\mu }_k^{(0)}\text{其中}{\mu }_j^{(0)}\in {\mathbb{R}}^d$$

步驟2：分配數據點
對每個數據點$x_i$，計算到所有質心的距離，分配到最近質心的簇：
C j ( t ) = { x i : ∥ x i ? μ j ( t ) ∥ 2 ≤ ∥ x i ? μ l ( t ) ∥ 2 ? l } C_j^{(t)} = \{ x_i : \|x_i - \mu_j^{(t)}\|^2 \leq \|x_i - \mu_l^{(t)}\|^2 \ \forall l \} Cj(t)?={xi?:∥xi??μj(t)?∥2≤∥xi??μl(t)?∥2??l}

步驟3：更新質心
重新計算每個簇的均值作為新質心：
$${\mu }_j^{(t+1)}=\frac{1}{|C_j^{(t)}|}\sum _{x_i\in C_j^{(t)}}{x}_i$$

步驟4：收斂條件
當滿足以下任一條件時停止迭代：
$$\Vert {\mu }_j^{(t+1)}?{\mu }_j^{(t)}\Vert <?\text{或}{J}^{(t)}?J^{(t+1)}<\delta$$

2.3 時間復雜度

• 每次迭代：$O(knd)$
• 總復雜度：$O(tknd)$
  其中k=簇數，n=樣本數，d=特征維度，t=迭代次數

3. 模型評估

內部評估指標

1. 輪廓系數（Silhouette Coefficient）
   s ( i ) = b ( i ) ? a ( i ) max ? { a ( i ) , b ( i ) } s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}} s(i)=max{a(i),b(i)}b(i)?a(i)?

   • $a(i)$：樣本i到同簇其他點的平均距離
   • $b(i)$：樣本i到最近其他簇的平均距離
   • 取值范圍：[-1, 1]，越大越好

2. 戴維森堡丁指數（Davies-Bouldin Index）
   $$DB=\frac{1}{k}\sum _{i=1}^k\underset{j\ne i}{\max }\left(\frac{{\sigma }_i+{\sigma }_j}{d({\mu }_i,{\mu }_j)}\right)$$

   • ${\sigma }_i$：簇i內平均距離
   • $d({\mu }_i,{\mu }_j)$：簇中心距離
   • 取值越小越好

外部評估指標（需真實標簽）

• 調整蘭德指數（Adjusted Rand Index）
• Fowlkes-Mallows 指數
• 互信息（Mutual Information）

4. 應用案例

4.1 客戶細分

• 場景：電商用戶行為分析
• 特征：購買頻率、客單價、瀏覽時長
• 結果：識別高價值客戶群（K=5），營銷轉化率提升23%

4.2 圖像壓縮

• 原理：將像素顏色聚類為K種代表色
• 步驟：
  1. 將圖像視為RGB點集（n=像素數，d=3）
  2. 設置K=256（256色圖像）
  3. 用簇中心顏色代替原始像素
• 效果：文件大小減少85%且視覺質量可接受

4.3 文檔聚類

• 場景：新聞主題分類
• 特征：TF-IDF向量（d≈10,000）
• 挑戰：高維稀疏數據需先降維（PCA/t-SNE）

5. 面試題及答案

Q1：K均值對初始質心敏感，如何改進？
A：采用K-means++初始化：

1. 隨機選第一個質心
2. 后續質心以概率$D(x{)}^2/\sum D(x{)}^2$選擇
   （$D(x)$為點到最近質心的距離）

Q2：如何確定最佳K值？
A：常用方法：

• 肘部法則（Elbow Method）：繪制K與WCSS曲線，選拐點

  from sklearn.cluster import KMeans
  distortions = []
  for k in range(1,10):kmeans = KMeans(n_clusters=k)kmeans.fit(X)distortions.append(kmeans.inertia_)
  

• 輪廓系數法：選擇使平均輪廓系數最大的K

Q3：K均值能否處理非凸數據？
A：不能。K均值假設簇是凸形且各向同性。解決方案：

• 使用譜聚類（Spectral Clustering）
• 或DBSCAN等基于密度的算法

6. 優缺點分析

優點：

1. 簡單高效：時間復雜度線性增長，適合大規模數據
2. 可解釋性強：簇中心代表原型特征
3. 易于實現：核心代碼僅需10行

   def k_means(X, k):centroids = X[np.random.choice(len(X), k)]while True:labels = np.argmin(np.linalg.norm(X[:,None]-centroids, axis=2), axis=1)new_centroids = np.array([X[labels==j].mean(0) for j in range(k)])if np.allclose(centroids, new_centroids): breakcentroids = new_centroidsreturn labels, centroids
   

缺點：

1. 需預先指定K值：實際應用中K常未知
2. 對異常值敏感：均值易受極端值影響
3. 僅適用于數值數據：需對類別變量編碼
4. 局部最優問題：不同初始化可能產生不同結果
5. 假設各向同性：在細長簇或流形數據上效果差

7. 數學證明：為什么均值最小化WCSS？

給定簇$C_j$，優化目標：
$$\underset{{\mu }_j}{\min }\sum _{x_i\in C_j}\Vert x_i?{\mu }_j{\Vert }^2$$
求導并令導數為零：
$$\frac{?}{?{\mu }_j}\sum \Vert x_i?{\mu }_j{\Vert }^2=?2\sum (x_i?{\mu }_j)=0$$
解得：
$${\mu }_j=\frac{1}{|C_j|}\sum x_i$$
證畢：均值是簇內平方和的最優解。

---

💡 關鍵洞察：K均值本質是期望最大化（EM）算法的特例：

• E步：固定質心，分配數據點（期望）
• M步：固定分配，更新質心（最大化）

實際應用時建議：

1. 數據標準化：消除量綱影響
2. 多次運行：取最佳結果（n_init=10）
3. 結合PCA降維：處理高維數據
4. 對分類型數據用K-mode變種