假設每段已記錄訊號都已轉為特徵向量。我們想把位置接近的向量分組,事前卻沒有正確的群組標籤。質心式方法以一個中心代表每組,再按觀察值到各中心的距離分配成員。這聽來簡單,但仍須說清楚採用甚麼距離、中心代表甚麼,以及正在改善哪個準則。
對 k-means,準則是每個觀察值到所屬中心的歐氏距離(Euclidean distance)平方總和。通常的迭代交替處理兩個各自容易的問題:固定中心時選標籤,再固定標籤時選中心。合起來不會令準則增加,卻不會自動在全局解決聯合優化問題。
寫清數據與目標函數
定義 1.1.1
(分配、中心與平方誤差目標)
固定觀察值 ,其中 ,並選擇 個中心 。分配標籤 把第 個觀察值交給一組。定義
群組 包含分配到 的索引。這些分配標籤由算法計算,並非事前提供的正確類別標籤。中心不一定是某個觀察值。
平方是模型的一部分,不是可以隨意改動的寫法。最小化距離平方才會得到平均數中心;改用另一種損失,可能就需要不同更新。因此,單憑「中心」一詞不能決定算法。
一次迭代採用以下規則:
- 固定中心,把每個觀察值分配到最近的中心;距離相等時,選中心索引較小者。
- 對每個非空群組,以成員的算術平均數取代中心。
- 本例對空群組保留原中心,再重複分配與更新,直到符合所選停止條件。
空群組規則是一項明確政策:空群組的平均數沒有定義,若默默把它當作零,就會在特徵空間加入無關的位置。保留原中心並非唯一政策,但令程序有完整規定。
為何算術平均數是正確更新
命題 1.1.2
(關於中心的平方誤差)
設 ,,並設 。則對每個 都有
因此 是 的唯一最小化點。
證明
(圍繞平均數展開)
寫 並展開長度平方。交叉項是 ,由於 ,交叉項消失,餘下即所述恆等式。第一項與 無關;第二項非負,而因 ,它恰好在 時為零。所以對這個固定的非空群組,平均數是唯一的最小化中心。
證明透視
恆等式在哪裏用到群組,又在哪裏失效
唯一不算常規的一步,是在 與 之間插入 。這樣選擇,是因為它令交叉項變成與 的內積,而按 的定義它等於零;換成任何其他中間點,交叉項仍會依賴 。
非空這個條件用了兩次:一是讓 有定義,二是令係數 為正,唯一性正是由此而來。恆等式也準確計算了中心放錯的代價:額外損失 隨群組大小及位移平方增加。
這個相消依賴平方歐氏損失。對未平方的距離沒有這種恆等式,最小化點也不一定是平均數:在一維中, 的絕對偏差和在 時是 ,在平均數 時卻是 。空群組沒有 ,也沒有正係數,所以需要獨立政策。
固定中心時,分配規則也有直接理由。每個觀察值對 貢獻一項,並不依賴其他觀察值的標籤選擇;選最小距離平方便令該項最小。保持這些分配不變,再用平均數更新,便令每個非空群組的貢獻最小。
概念視角代數
完全不用中心的目標函數
對大小為 的群組 ,平均數恆等式給出 。因此每個群組貢獻的,是其無序成對距離平方之和再除以群組大小,k-means 就是尋找成員彼此接近的群組。以 驗證:無序成對的平方和為 ,而群組內誤差正是 。
精確追蹤兩輪交替步驟
例題 1.1.3
(中心更新後,觀察值可以轉到另一組)
使用一維觀察值 ,初始兩中心為 與 。表中的群組列出觀察值,而不是索引。直線上兩個不同中心的中點,是最近中心區域的分界。起初分界是 ,所以只有觀察值 0 屬於第一組。
| 階段 | 中心 | 第一組 | 第二組 | 目標值 |
|---|---|---|---|---|
| 第一次分配 | ||||
| 第一次平均數更新 | ||||
| 第二次分配 | ||||
| 第二次平均數更新 |
第一行的非零誤差平方是 。第二組平均數為 ,把固定成員下的誤差降至 。
更新把分界移至 。2 與 3 現在較接近第一中心,因此下一次分配改變了群組,得到 。新平均數為 與 ,最後群內誤差是
新分界為 ,位於 3 與 10 之間,因此再作分配,兩組都不變;再更新平均數也不改變任何值。例子已到達不動點。表格把分配與更新分開,是因為它們改變不同變量;記錄目標值時,不應把舊標籤與未交代的新中心混在一起。
例題 1.1.4
(距離平手,由較小索引規則決定)
取觀察值 ,初始中心為 與 。觀察值 1 到兩個中心的距離平方都是 ,所以依既定規則歸入第一組。
| 階段 | 中心 | 第一組 | 第二組 | 目標值 |
|---|---|---|---|---|
| 第一次分配 | ||||
| 平均數更新 |
第一組的平均數是 ;只有一個成員的群組,其平均數就是該成員,所以第二中心仍在 。分界現在是 ;觀察值 1 與第一中心相距 ,與第二中心相距 ,因此沒有標籤改變,狀態是 的不動點。
若平手改為另一方向解決,群組會是 與 ,;更新後中心為 ,,分界為 ,同樣沒有改變。兩次運行停在不同的不動點,目標值卻相同。因此,平手規則是可重現運行規格的一部分。
例題 1.1.5
(平面上的兩個群組)
取 ,初始中心為 與 。四個觀察值到中心 的距離平方分別是 、、 與 。所以第一個觀察值留在第一中心,其餘三個歸第二中心,得 。
| 階段 | 中心 | 第一組 | 第二組 | 目標值 |
|---|---|---|---|---|
| 第一次分配 | ||||
| 第一次平均數更新 | 相同 | 相同 | ||
| 第二次分配 | ||||
| 第二次平均數更新 | 相同 | 相同 |
第二組平均數是 。在成員不變下,它的誤差減少 ,由 降至 。在新中心下,四個觀察值到最近中心的距離平方是 ,所以 轉組,。新平均數是 與 ,每個觀察值與其中心的距離平方都是 ,所以 。再分配時所有標籤不變,因此這是不動點。第一輪中只有一個成員的群組誤差為零,其中心也沒有移動。
下降性證明了甚麼,又沒有證明甚麼
定理 1.1.6
(Lloyd 一輪不會令目標值增加)
設 為一個分配, 為一組中心。一輪先把每個觀察值分配給 中的最近中心(平手時可用任何規則),得到 ;再把每個非空群組的中心換成其平均數,空群組則保留原中心,得到 。則
所以一輪之中 不增加,且 。
另設 起初是 各群組的平均數、算術為精確、沒有距離平手,而且沒有空群組。則分配在有限輪後不再改變。
證明
(兩個半步,然後嚴格下降)
第一式由最近中心分配對每點分別成立:每個觀察值對 貢獻一項,新的一項是可選之中最小的。第二式由平均數恆等式對每組分別成立;空群組貢獻為零,保留原中心也不會令其貢獻增加。
至於有限步終止,假設分配有所改變。至少一個觀察值移到嚴格較近的中心,所以第一式嚴格成立。每次更新後,平均數由分配決定,因此以 記 的各群平均數,則數值 只依賴 ,並在分配改變時嚴格下降。於是同一個分配不會重現。已標號的分配只有 種,所以分配最終不再改變,隨後平均數亦維持不變。
證明透視
每個不等式用了甚麼,論證又留下甚麼未決
第一式只用到 是獨立各項之和,每個觀察值一項,所以固定中心而改變標籤時可逐項處理。第二式在標籤固定下,對每個非空群組使用平均數恆等式。兩個半步改變不同的變量,因此一步不會抵銷另一步。
嚴格性是較微妙的假設。若有距離平手,觀察值可能以相同距離改變標籤,只能得到 ,上面的有限性論證便不適用;不增加的結論則仍然成立。精確算術也必須假設,因為捨入可能破壞平均數恆等式所給出的等式。
論證以計數收尾:附於有限個分配的嚴格遞減數值序列必須停止。結論是迭代會停止,並沒有說最後的數值與其他聚類相比如何。
這項保證針對的是迭代過程中 的數值,而不是極限的好壞。
反例模式
穩定聚類的目標值仍可能較差
改用另一組數據:,中心為 與 。中點是 ,最近中心分配得到 與 。它們的平均數恰好仍是原中心,所以這是沒有距離平手的不動點。
其目標值是
但另一種分組 與 ,平均數為 與 ,其目標值為
因為 ,原不動點不是全局最佳。要反駁「每個不動點都是全局最佳」,毋須證明 87 本身就是全局最小。初始中心因此可以影響結果;分配不變是一個停止條件,不是全局最優性的證書。
逐步演示重現上面的精確例子與穩定但較差的聚類。空群情況延伸下面練習 2 的第一輪:沒有分配點的群沒有平均數,而這個例子依明確約定保留其原有中心。
常見錯誤
(較小的目標值不能用來選擇群組數目)
增大時, 的最小可達值不會增加,因為多出來的中心總可以放在不起作用的位置。若跨不同 比較 並取最小者,選中的必然是最大的 。對觀察值 ,取 令每個觀察值各有自己的中心,,但數據的結構完全沒有被學到。目標值只可比較 相同的不同運行,例如上面 與 的兩個聚類;選擇 需要另一個準則。
特徵單位會改變正在優化的幾何
反例模式
單位換算可以反轉最近中心的選擇
取觀察值 與固定中心 、。到 的距離平方為 9 及 16,所以最近中心是 。
現在把每個觀察值及中心的第二特徵都乘以 10,第一特徵不變。相同紀錄的座標變為 、、,距離平方是 900 及 16,因此改選 。
新座標中的無權重歐氏距離,相當於改變舊特徵的相對權重。若第 座標縮放 倍,其貢獻變為 。前處理因此是聚類模型的一部分。比較不同單位的特徵時,縮放可能適用,但應表達哪些差異對任務重要,而非描述成目標函數完全不變。
不用捨入重現計算
以下一維 Python 例子用有理數精確重現表格。實作以中心索引 0、1 對應第一組及第二組。assign 按索引打破距離平手,update 則在群組為空時保留原中心。
from fractions import Fraction as F
def assign(points, centers):
return [
min(range(len(centers)), key=lambda j: ((x - centers[j]) ** 2, j))
for x in points
]
def update(points, labels, old_centers):
result = []
for j, old in enumerate(old_centers):
group = [x for x, label in zip(points, labels) if label == j]
result.append(sum(group) / len(group) if group else old)
return result
def objective(points, labels, centers):
return sum((x - centers[label]) ** 2 for x, label in zip(points, labels))
points = list(map(F, [0, 2, 3, 10, 11]))
centers = [F(0), F(3)]
for _ in range(2):
labels = assign(points, centers)
print("assignment", objective(points, labels, centers))
centers = update(points, labels, centers)
print("update", objective(points, labels, centers))
assert assign(points, centers) == labels
四個印出的目標值為 114、65、91/2、31/6。兩輪只對這份特定數據及初始中心足夠,固定輪數不是一般停止規則。最後斷言檢查再分配一次是否維持不變。研究另一個例子時,應同時追蹤分配、中心及目標值,指出每個量在哪個半步改變。
練習
快速檢查
(1. 量化中心偏離的成本)
固定群組的值為 。求平均數與最小誤差平方和,再用平均數恆等式求中心為 5 時的誤差,不要分別重算三個距離平方。
解答 · 解答 1
平均數是 4,最小誤差為 。中心移到 5,增加 ,所以新誤差為 。比較期間,群組成員固定不變。
快速檢查
(2. 分清平手政策與平均數公式)
觀察值為 ,初始中心為 ,採用所述較小索引優先規則。第一次標籤與下一組中心是甚麼?為何第二中心不是空組的平均數?
解答 · 解答 2
兩個觀察值都選中心索引 0。該組平均數是 1;索引 1 的組為空,保留原中心 0,所以下一組中心為 。保留 0 是明確政策,並沒有把空組平均數定義為 0。
快速檢查
(3. 用合適證據檢查全局最佳的聲稱)
某實作回報分配不變,而且目標值沒有增加。這能確立全局最優性嗎?在上述反例中,甚麼證據已足以反駁該不動點是全局最佳?又有哪個更強的聲稱尚未證明?
解答 · 解答 3
不能。目標值為 127 的不動點滿足這兩項觀察。提出一個目標值為 87 的合法分組,已足以證明 127 不是全局最小,但不能單憑這點確立 87 是最佳可能值;後者還須排除所有更好的聚類。
快速檢查
(4. 預測特徵縮放的影響)
若把所有觀察值及中心的某一特徵乘以 100,該特徵對歐氏距離平方的貢獻會乘多少倍?若每個特徵都乘相同正數,會保留最近中心的選擇嗎?這為何與只縮放一個特徵不同?
解答 · 解答 4
該特徵的貢獻乘以 。每個特徵都乘相同正數、中心也同樣縮放時,每個距離平方都乘同一正數常數,因此最近中心比較及平手都不變。只縮放一個特徵,則改變它相對其他特徵的權重,可以反轉比較,正如二維例子所示。