← 回首頁

k-means 分群（Lloyd 迭代）

你有一堆點（可以是二維座標，也可以是圖片像素的顏色、一段文字的向量、一張臉的特徵），想把它們自動分成 幾群、每群用一個代表點（質心，centroid）概括——這就是 k-means 要做的事，也是最基礎的 非監督分群（unsupervised clustering，沒有正確答案標籤、只靠資料自己的分布）。做法叫 Lloyd's algorithm，簡單到只有兩步反覆做：①指派——每個點歸到離它最近的質心； ②更新——每個質心搬到自己那群所有點的平均位置。指派會讓質心該負責的點變了、更新又讓質心 位置變了，於是再指派、再更新……直到指派不再變動（收斂）。

這頁用一組固定的 12 個二維點示範一條決定性的收斂軌跡。初始 3 個質心刻意用固定亂數種子 （LCG）選在「兩顆擠在右邊那群、上方那群一開始沒有質心」的位置，所以你會清楚看到一顆質心慢慢遷移 到上方去，最後三顆質心各自落在三個天然群的中心。每一輪我們都算一個叫 inertia（群內平方和）的數字 ——它是 k-means 想要最小化的目標，Lloyd 保證它每一步都不會變大（單調不增），這就是本頁用來當 「真值檢查」的性質。

為什麼 AI 時代重要

現代向量資料庫要存幾億條 embedding（每條可能上千維 float），若原封不動存會爆記憶體。 向量壓縮 PQ（Product Quantization）的做法是：把向量切成子段，每個子段用 k-means 訓練出一本 碼本（codebook，通常 256 個質心），之後每個子段只存「最近的那個質心編號」（1 byte）就好—— k-means 正是那本碼本的產生器。同一招也用在影像色彩量化（把幾百萬種顏色壓到 256 色）、 特徵聚合 / Bag-of-Visual-Words、以及各種「用少數代表點概括海量資料」的前處理。看懂這頁的兩步 迭代，就看懂了 PQ 碼本、色盤壓縮這些 AI/檢索基礎設施底層那顆被埋起來的核心。

它是向量壓縮 PQ 碼本與最近鄰查詢（KD 樹）的延伸

k-means 訓練出的質心，正是 向量壓縮 PQ / IVF 裡每個子空間的 碼本——PQ 頁把 k-means 埋在裡面沒獨立展開，本頁就是那顆核心的獨立解剖。另一條血緣連到 空間結構 KD 樹 / 區間樹：k-means 的「指派」步驟本質是對每個點做 最近鄰查詢（找最近的質心），暴力做是 O(n·k)，低維大 n 時可用 KD 樹的空間索引加速——分群與空間 索引在「快速找最近點」這件事上同源。

分群流程（初始化 → 指派 → 更新 → 收斂 → 真值檢查）

固定 12 個 2D 點分屬 3 個天然群（左下 / 左上 / 右，各 4 點）。以固定種子 LCG 從點集選出 3 個相異點當 初始質心。接著反覆做「更新質心 = 群內均值」與「重新指派每點到最近質心」，直到某一輪沒有任何點改變所屬 群（收斂）。畫面上每個資料點都有一條 spoke（連線）指向它目前所屬的質心——spoke 指向哪顆質心 就代表它屬於哪一群。抽選初始質心的隨機源與 Reservoir / Alias、LLM 取樣 為同一顆 LCG： next(x) = (1664525·x + 1013904223) mod 2^32、取值用高 16 位、先 burn-in 3 步。

固定 12 個 2D 點（左下 [1,1][2,1][1,2][2,2]、左上 [1,8][2,8][1,9][2,9]、右 [8,4][9,4][8,5][9,5]）； k=3；初始質心 LCG seed=62 → 選出點索引 [11, 8, 0]。
Lloyd 輪（iterations）：0 階段：init inertia（群內平方和）：—
點上的數字是索引：0–11 = 資料點，12/13/14 = 三顆質心（C0/C1/C2）。每條 spoke（細線）從 資料點連到它目前所屬的質心——GeometryRenderer 這個既有共用渲染器不支援依群給每點不同填色， 所以本頁用「spoke 指向哪顆質心」表達分群（誠實揭露的渲染簡化）。accent 色的 spoke = 這一輪 被重新指派的點；更新步驟時放大的橘點（current）= 移動最多的質心，虛線對照色線段 = 質心 「舊→新」的移動軌跡。 誠實揭露：k-means 對初始質心敏感、可能收斂到局部最優（非全域最優）；本頁用固定初始 （seed=62）示範一條決定性軌跡，不做多次重啟（multiple restarts）挑最佳。座標為教學縮尺，真實應用是 高維大量向量。

質心座標與群大小（橘色 = 本輪移動最多）

單步操作紀錄（opLog）

（空）

各群成員（點索引）

inertia 歷程（單調不增 = Lloyd 真值性質）

（空）

本輪重新指派的點 / 收斂真值

本頁選初始質心用來擲 u∈[0,1) 從點集抽 k 個相異索引的那顆 LCG（burn-in 3 步、高位取值），與 Reservoir Sampling / Alias Method、LLM 取樣 是同一顆決定性偽隨機產生器——同屬「用偽隨機性做機率決策」的家族。而 k-means 產出的質心碼本，正是 向量壓縮 PQ / IVF 壓縮向量的基礎；其指派步驟的最近鄰查詢，則與 KD 樹 同源。