Stanford CS229 Lecture 9: K-Means and Gaussian Mixture Models (Spring 2026)

TL;DR

本講義將 K-means 呈現為一種硬分配（hard-assignment）分群演算法，並將高斯混合模型（GMM）作為其軟分配（soft-assignment）的機率對應版本，展示兩者如何透過期望最大化（EM）迴圈來求解、為什麼初始化至關重要，以及 Jensen's inequality 如何為 EM 提供一個可處理的下界。

K-means 演算法直覺

K-means 旨在透過迭代過程將數據劃分為 K 個群集：首先將每個點分配給最近的群集中心，然後將每個中心重新計算為其所分配點的平均值。

演算法從隨機的初始中心 $\mu_1 \dots \mu_K$ 開始，使用歐幾里得距離（Euclidean distance）將每個點分配給中心最近的群集，將每個中心更新為其分配點的算術平均值，並重複此過程直到分配不再改變。

由於群集標籤是任意的，交換所有的 $\mu$ 會得到相同的解；重要的是中心最終會落在正確的位置。

終止、最佳性與初始化

K-means 總是會終止，因為群集內平方誤差和（L₂ objective）是單調遞減且有下界的，因此演算法會達到一個分配不再改變的定點。

尋找此目標函數的全局最小值是 NP-hard 問題，因此 K-means 可能會收斂到一個取決於初始中心的次優解。

存在多個局部最小值；不同的隨機初始化可能導致不同的最終分群結果，這就是為什麼初始化步驟至關重要的原因。

為了改進初始化，K-means++ 程序以一種可證明能產生良好近似比的方式選擇初始中心；這是常見函式庫（如 scikit-learn）中的預設選項。

選擇群集數量 K

選擇 K 是一種建模假設：分析師必須對數據中存在多少個不同群體表達先驗信念。

增加 K 會產生更細緻的劃分，但較低的成本並不自動意味著更好的模型；評估較大的 K 是否真正有益需要外部知識或驗證標準。

因此，選擇 K 仍然是一個由問題領域引導的定性決策，而非純粹的演算法準則。

從硬分配到軟分配：高斯混合模型

GMM 將 K-means 的硬群集成員身份替換為機率分配：每個點都是從具有未知平均值、協方差（covariances）和混合權重的 K 個高斯源之一生成的。

前向模型假設一個隱變量 $Z_i$ 用於指示點 $X_i$ 的來源；$Z_i$ 是從 K 個來源的多元分布中抽取的，然後從對應的高斯分布中對 $X_i$ 進行採樣。

在僅給定觀測點的情況下，目標是推斷最能解釋數據的高斯參數和混合權重。

GMM 的期望最大化 (EM)

EM 在兩個步驟之間交替進行：

• E-step：使用當前參數估計值的貝氏定理，計算點 $i$ 源自來源 $j$ 的後驗機率 $w_{ij}$。
• M-step：將每個高斯的平均值、協方差和混合權重更新為點的加權平均值，其中權重為後驗機率 $w_{ij}$。

當後驗機率為 0 或 1 時，M-step 會完全簡化為 K-means 的更新；否則，EM 會執行相同計算的軟加權版本。

演算法會迭代直到參數估計值收斂。

Jensen's inequality 與 EM 下界

EM 可以被視為最大化數據對數似然（log-likelihood）的下界。

Jensen's inequality 指出，對於凸函數 $\phi$，$\mathbb{E}[\phi(X)] \ge \phi(\mathbb{E}[X])$；對於凹函數，不等式反轉。

在 E-step 中，EM 構建了一個在當前參數處緊湊（tight）且更容易優化的代理函數（surrogate function）；將 Jensen's inequality 應用於對數似然會產生這個代理函數，保證每個 M-step 都會增加（或保持不變）真實的似然值。

因此，EM 保證會收斂到似然函數的一個駐點（stationary point），但不一定是全局最大值。

實務要點

• K-means 簡單且具解釋性，但對初始化敏感，並可能陷入較差的局部最小值。
• K-means++ 提供了一種具有強大理論保證的中心初始化原則方法。
• GMM 擴展了 K-means，透過對群集成員身份建模不確定性，並透過協方差捕捉橢圓形的群集形狀。
• EM 為隱變量模型提供了一個通用框架；其收斂依賴於 Jensen's inequality 來構建緊湊的下界。
• 這兩種演算法都要求分析師指定群集數量 K，這是一個應由領域知識啟發的建模決策。

這些概念構成了許多現代無監督學習技術的基礎，並說明了演算法簡單性、計算難度以及對仔細初始化和模型選擇需求之間的權衡。