4.2 中心目標與 Lloyd 更新

動機

把每個觀測值分配給最近中心，還未完整指定分群方法。我們仍須決定如何合併各點的分配距離：距離平方的總和給出 k-means，普通距離的總和給出中位數目標，最大距離則給出 k 中心問題。在中心固定、採用同一歐氏距離時，這些目標都會選擇最近中心，但最合適的中心位置一般不同。

當某簇有一個遠離其他點的觀測值，差異便很明顯。它的距離平方會在 k-means 損失中佔很大比重，把平均數拉向自己；普通距離總和的最小化代表點則可能不同。若再要求代表點必須是實際觀測值，便加上另一項數學限制。因此，中心更新應由已定義的目標推導，不能只因某個點被稱為「質心」就採用它。

Lloyd 演算法交替更新分配和中心。固定其中一部分後，另一部分都容易求解。分析其下降性，應從這兩個小型最佳化問題開始，而不是推論聯合問題也同樣容易。平局和空簇是迭代中可能出現的狀態；要證明有限終止，也必須先指定它們的處理規則。

定義

定義

分配損失與最近中心損失

設觀測值為 $x_1,\ldots,x_n\in\mathbb R^d$，中心串列為 $C=(c_1,\ldots,c_k)$，標籤為 $z_i\in\{1,\ldots,k\}$。定義

$$J(z,C)=\sum_{i=1}^n\|x_i-c_{z_i}\|_2^2,\qquad F(C)=\sum_{i=1}^n\min_{1\le j\le k}\|x_i-c_j\|_2^2 =\min_z J(z,C).$$

標籤指定一個硬分群。某些標籤可以沒有觀測值，串列中的中心也可以重合。

固定中心後，每個觀測值獨立選擇一個最近中心，便使 $J$ 最小。多個中心並列最近時，選擇其中任何一個對損失的貢獻都相同。固定分配後，記 $I_j=\{i:z_i=j\}$；若 $I_j$ 非空，其平均數為 $\mu_j=|I_j|^{-1}\sum_{i\in I_j}x_i$。

k-median 使用 $\sum_i\min_j\|x_i-c_j\|_2$，而不是距離平方。在一維，固定簇的最優中心是中位數；在多維普通歐氏距離下，所需的是幾何中位數。若改用曼哈頓距離，各座標可以分開處理，逐座標中位數才會使相應目標最小。中心樣本（medoid）另要求中心是容許的觀測點，並在這些候選點中使距離總和最小。

在實數線上，把候選中位數稍向右移，會增加它到左側觀測值的距離，同時減少它到右側觀測值的距離。最小值由兩側的數量平衡決定。觀測值個數為偶數時，兩個中間次序統計量之間的每一點都可以最優。多維歐氏距離中的平方根把座標耦合起來；若幾何中位數候選點不與任何觀測值重合，其梯度條件為 $\sum_i(c-x_i)/\|c-x_i\|_2=0$。逐座標中位數的根據則是曼哈頓距離的可分性，兩者不能混用。

定理與命題

命題

平均數使歐氏距離平方總和最小

對有 $m$ 個觀測值的非空簇，設其平均數為 $\mu$。對任何 $c\in\mathbb R^d$，

$$\sum_{i=1}^m\|x_i-c\|_2^2 =\sum_{i=1}^m\|x_i-\mu\|_2^2+m\|c-\mu\|_2^2.$$

因此唯一最優中心是 $\mu$。空簇對任何中心的損失貢獻都是零，但沒有可計算的平均數。

命題

一次 Lloyd 迭代使損失不增加

從最近中心標籤開始，先固定這些標籤，把每個非空簇的中心換成其平均數，空簇中心則保持原位；再把觀測值分配給最近中心。兩步都不會增加 $J$，結果的最近中心損失 $F$ 也不大於先前的值。

命題

指定平局規則後的有限終止

採用精確運算及上述平均數和空簇規則。重新分配時，若舊標籤仍是最近中心之一，就保留舊標籤；否則選擇最近中心中編號最小的一個。當標籤不再改變便停止。標籤只會改變有限多次，最終中心與標籤構成 Lloyd 不動點。

證明思路

把 $x_i-c=(x_i-\mu)+(\mu-c)$ 代入平方範數並展開。由於 $\sum_i(x_i-\mu)=0$，所有交叉項相加為零，便得到平均數分解式。當 $c\ne\mu$ 時，右邊第二項嚴格為正，故最優中心唯一。這個計算使用歐氏內積，不能把距離任意更換後仍沿用結論。

平均數是以相等非負權重組合各觀測值，所以位於它們的凸包內，但不一定是某個觀測點。分解式中的乘數 $m$ 也有意義：同樣偏離平均數一段距離，大簇的額外損失比小簇大。完整目標給每個觀測值相同權重，並非給每簇相同權重。因此，要由多個簇平均數還原整體樣本平均數，應按各簇大小加權。各簇大小相等時可用相等權重；大小不同時，相等權重一般沒有這項恆等關係。

平均數步驟使各非空簇對 $J$ 的貢獻最小。接着固定這些中心，分配步驟使各觀測值的貢獻最小。空簇保持原中心，其零貢獻不影響不等式。起始標籤是最近中心標籤，因此一輪開始時 $J(z,C)=F(C)$。這兩步證明損失不增加，但僅有數值不增加，還不足以證明有限終止。

要得到更強的結論，令 $W(z)$ 為按分配 $z$ 把各非空中心設為平均數後的損失；空中心不影響這個值。若重新分配改變了某個標籤，按指定規則，舊標籤必定已不是最近中心，因此該觀測值的距離平方嚴格減少。設新分配為 $z'$，平均數更新後的中心為 $C'$，便有

$$W(z')\le J(z',C')<J(z,C')=W(z).$$

帶編號的分配至多有 $k^n$ 個，所以 $W$ 只有有限多個可能值。每次改變標籤都使它嚴格下降，任何分配便不能重現。最後標籤固定，此時非空中心已是相應平均數，空中心一直保留，再迭代一次也不會改變狀態。這證明不動點的存在，並沒有把它等同於 $F$ 的全域最小值。

這個版本容許使用一串 $k$ 個中心，並不要求所有 $k$ 簇始終非空。重合中心或不合適的初始位置都可能令某個標籤未被使用。若要求剛好 $k$ 個非空簇，就是另加最佳化限制；只為填滿空簇而強行移動觀測值，可能增加固定分配的損失，並不包含在上述下降證明內。保留空中心，已是本版本完整而明確的操作規則。

完整算例

例題

例 1：分開追蹤平均數更新與重新分配

取線上的觀測值 $0,2,3,9,10$，初始中心為 $(0,3)$。最近中心分配把 $0$ 放入第一簇，其餘四點放入第二簇，初始損失為 $86$。

第一次平均數更新得到 $(0,6)$。沿用舊標籤的損失為 $50$。重新分配時，$2$ 轉到第一簇；$3$ 到兩個中心的距離同為 $3$，因此保留舊標籤。最近中心損失變為 $38$。

下一次平均數為 $(1,22/3)$，舊分配損失為 $92/3$。重新分配把 $3$ 移入第一簇，損失降至 $143/9$。最終平均數和損失為

$$C=(5/3,19/2),\qquad F(C)=\left(25/9+1/9+16/9\right)+\left(1/4+1/4\right) =31/6.$$

此時最近中心標籤不再改變：$0,2,3$ 屬同一簇，$9,10$ 屬另一簇。區分保留標籤時的 $J$ 和重新分配後的 $F$，便能理解為何 $50$ 與 $38$ 對應同一組中心，卻有不同損失。

例題

例 2：較大 k 的局部運行可以有較差損失

取 $X=\{0,1,8,9,20,21\}$。三個中心 $(0,1,29/2)$ 產生兩個單點簇，以及最後一簇 $\{8,9,20,21\}$。各中心都是所屬簇的平均數，而每點都嚴格較接近其所屬中心，所以這是 Lloyd 不動點。損失為

$$F(0,1,29/2)=\frac{169+121+121+169}{4}=145.$$

比較兩個中心 $(9/2,41/2)$，它們產生簇 $\{0,1,8,9\}$ 和 $\{20,21\}$，損失為 $65+1/2=131/2$。這個已收斂的三中心結果，竟比一個可行的兩中心結果差。若三中心改由 $(1/2,17/2,41/2)$ 開始，則得到三對相鄰點，損失只有 $3/2$。

算例同時說明初始化和重新啟動的作用。重複運行並保留最低損失，可改善目前找到的最佳結果；某次運行到達不動點，並不是全域最優的證明。比較不同 $k$ 的獨立局部運行時，損失也不必單調。

例題

例 3：平均數、中位數與中心樣本解決不同問題

一簇包含 $0,2,9$ 時，距離平方總和由平均數 $11/3$ 最小化，最小值為 $134/3$；中心 $2$ 的平方損失則是 $53$。改用普通絕對距離總和，中位數 $2$ 的損失是 $9$，平均數的損失卻是 $32/3$。若限制中心必須是觀測點，中心樣本也是 $2$，距離總和同為 $9$。

在平面上，考慮 $(0,0)$、$(2,0)$、$(0,2)$。逐座標中位數為 $(0,0)$，歐氏距離總和是 $4$。可行點 $(1/2,1/2)$ 的總和為

$$\frac1{\sqrt2}+\sqrt{10}<4.$$

因此，逐座標中位數不是這組資料的歐氏幾何中位數。逐座標最小化解決的是曼哈頓距離問題，其中各座標的絕對差分開相加。

可重現的 Lloyd 計算

以下程式實作例 1。輸出的是重新分配後的 $F$，並非沿用上一輪標籤的損失。空中心保持原位；距離完全相同時保留舊標籤。

import numpy as np

X = np.array([0.0, 2.0, 3.0, 9.0, 10.0])[:, None]
C = np.array([[0.0], [3.0]])
rows = np.arange(len(X))
def distances2():
    return np.sum((X[:, None, :] - C[None, :, :]) ** 2, axis=2)
D = distances2()
labels = np.argmin(D, axis=1)
print(f"initial cost={D[rows, labels].sum():.6f}")
round_number = 0
while True:
    round_number += 1
    for j in range(len(C)):
        members = X[labels == j]
        if len(members):
            C[j] = members.mean(axis=0)
    D = distances2()
    nearest = np.argmin(D, axis=1)
    new_labels = np.where(D[rows, labels] <= D[rows, nearest], labels, nearest)
    cost = float(D[rows, new_labels].sum())
    centre_text = ", ".join(f"{centre[0]:.6f}" for centre in C)
    print(f"{round_number}: centres=({centre_text}), cost={cost:.6f}")
    if np.array_equal(new_labels, labels):
        break
    labels = new_labels
print("labels:", labels.tolist())

initial cost=86.000000
1: centres=(0.000000, 6.000000), cost=38.000000
2: centres=(1.000000, 7.333333), cost=15.888889
3: centres=(1.666667, 9.500000), cost=5.166667
labels: [0, 0, 0, 1, 1]

初始化與手肘曲線

初始化決定交替更新從哪一個吸引區域開始。最遠優先每次選取目前距離已選中心最遠的觀測值，使中心散開。k-means++ 則先均勻隨機選一個觀測值，再按到已選中心的最近距離平方作比例抽樣。距離平方總和為正時，機率為

$$p_i=\frac{D_i^2}{\sum_{r=1}^nD_r^2},\qquad D_i=\min_{c\in C}\|x_i-c\|_2.$$

若所有 $D_i$ 都是零，每個輸入點都已由某個選定中心代表。否則，抽樣較偏向目前代表不足的點，但並非必定選取最遠的一點。完成初始化後，才進行 Lloyd 更新。

設 $F_k^*$ 為使用至多 $k$ 個中心的全域最小損失。加上一個中心不會增加任何觀測值的最近距離，所以 $F_{k+1}^*\le F_k^*$。每個觀測值各有一個中心時，損失為零。手肘圖觀察額外中心帶來的改善在哪裏明顯減弱；可行集合的論證針對全域最優值，例 2 已說明任意局部運行的損失不必遵守同一排序。手肘是平衡簡潔程度與擬合的建模工具，並非每組資料必能唯一恢復簇數的定理。

常見錯誤

常見錯誤

改了更新方式，卻沿用原來的目標

算術平均數最小化歐氏距離平方總和。一維絕對距離目標使用中位數，多維歐氏普通距離目標使用幾何中位數。中心樣本則須在容許的觀測代表點中最小化距離總和，不能只挑一個看似接近算術平均數的觀測值。

平局時損失可以不變，因此「損失不增加」和「分配數有限」合起來仍未排除等損失狀態的循環。保留舊標籤的規則令每次真正改變標籤都嚴格改善損失。同樣，保留空中心是明確且合法的操作，因為它對固定分配損失的貢獻為零；空集合的平均數則未有定義。

小結

選擇更新前，先指定距離、如何合併分配成本，以及中心容許的位置。Lloyd 的平均數與最近中心步驟使歐氏平方目標下降；配合明確的平局和空簇規則，標籤最終穩定，但不動點仍可能有很大損失。初始化、重新啟動和手肘比較，都應按這項區分解讀。

固定 $k$ 重複運行時，保留實際取得的最小目標值。增加運行次數不會使這個已保留的值變大，因為先前候選仍可選取；這說明的是目前最佳結果，而不是每次隨機初始化的品質。簇的編號也沒有內在意義：把標籤和相應中心一同重新排列，損失不變。比較兩次運行時，應比較目標值和各點的分組，避免把編號不同誤當成品質不同。

練習

思考檢查

練習 1：一簇包含 $1$、$2$、$6$。求平均數、最小平方損失，以及選擇中心 $2$ 所增加的損失。

使用距離平方分解式，毋須重新微分。

思考檢查

練習 2：線上的觀測值為 $0$、$2$、$9$、$11$。求使絕對距離總和最小的所有中心。哪些觀測點是中心樣本？

兩個中間觀測值之間的每一點都是中位數。

思考檢查

練習 3：觀測值為 $0$、$4$、$5$，現有中心為 $(0,4,100)$。按最近中心分配及上述平均數和空簇規則，求更新後的中心與損失。

第三簇是空簇，其中心保持原位。

思考檢查

練習 4：兩個觀測值都等於 $0$，兩個中心也都等於 $0$。任意更改平局標籤，如何在損失保持零時改變狀態？上述平局規則會怎樣做？

區分固定的目標值與固定的帶標籤狀態。

解答

解答 · 練習 1 解答

平均數是 $3$，最小平方損失為 $4+1+9=14$。中心 $2$ 的損失為 $1+0+16=17$，額外損失是 $3(2-3)^2=3$，與兩值之差一致。

解答 · 練習 2 解答

$[2,9]$ 內所有實數中心都使絕對距離總和最小，值為 $18$。限制中心為觀測點後，$2$ 和 $9$ 都是中心樣本，並達到同一數值。

解答 · 練習 3 解答

各簇為 $\{0\}$、$\{4,5\}$ 和空集合，更新後中心為 $(0,9/2,100)$。重新分配後各簇不變，損失為 $(4-9/2)^2+(5-9/2)^2=1/2$。

解答 · 練習 4 解答

可以反覆把標籤 $(1,2)$ 和 $(2,1)$ 互換；各簇平均數仍為零，所有距離也為零。這改變帶標籤狀態，卻沒有改善目標。平局時保留舊標籤會阻止這些互換，因此狀態停止改變。

相關筆記

Voronoi 區域與 k 中心問題推導最近站點幾何及最大距離目標。模型驗證與嶺迴歸解釋比較已擬合模型的另一項工作。課程閱讀書目集中列出相關延伸閱讀。