這段 pseudocode 在跑什麼分群演算法？
原題
請參考附圖，下列虛擬程式碼（pseudocode）最可能是在描述何種演算法？ Input: - data_points: N 筆資料，每筆資料有 D 個特徵 - X: 要分成的群數 Output: - clusters: 每筆資料所屬的群編號 - centroids: 每個群的中心點 Algorithm: 1. 隨機選擇 X 個資料點作為初始中心 2. 重複以下步驟直到收斂: a. 分群: 對每個資料點，計算它到每個中心的距離，將資料點指派給距離最近的中心 b. 更新中心: 對每個群，計算該群中所有資料點的平均值，將群中心更新為這個平均值 3. 當群中心不再變動時，停止 回傳每筆資料的群編號 clusters，以及最後的群中心 centroids
白話
這段 pseudocode 給定 N 筆資料和一個目標群數 X，先隨機挑 X 個點當中心，然後反覆做兩件事：把每筆資料分給最近的中心，再把中心移到各群的平均位置，直到中心不再移動為止，最後輸出每筆資料的群編號和各群中心座標。
問你：這個「先設 X 個中心、反覆分群更新、直到收斂」的流程，對應哪一種分群演算法？
先自己選一個答案，再看完整解析。
一句話總結
這段 pseudocode 描述的是 K-means 分群（K-means Clustering）：事先指定群數 K，反覆做「分派到最近中心」和「更新中心為群平均」兩個步驟，直到中心收斂為止。
情境
先感受問題：把 1000 個客戶分成 3 群，用手怎麼做？
「旅行衛星」電商有 1000 名顧客，每人有兩個特徵：年購買次數和平均客單價。行銷團隊想把這些顧客分成 3 群，方便針對性推播。
手動做的想像步驟：
第一步：隨便挑 3 個顧客，當作「三群的暫定代表人」（中心）。
第二步：對剩下所有顧客，看他們跟哪個代表人最像（距離最近），就分進那群。
第三步：每群分好後，重新算這群的「平均人」（平均購買次數、平均客單價），更新代表人。
第四步：繼續重複第二、三步，直到「代表人不再移動」為止。
最後：每個顧客都有一個群號，以及每群的中心座標。
這個「先設 K 個中心，反覆分群更新」的手動流程，就是 K-means 的核心邏輯。pseudocode 裡的 X 就是 K，centroids 就是每次更新後的代表人座標。
舊方法
怎麼從 pseudocode 排除其他三個選項
- 高斯混合模型（GMM）用的不是「距離最近」：GMM 的核心是機率，每個資料點屬於某群的機率是用高斯分佈計算的，不是「找最近中心」。pseudocode 裡寫的是「計算距離、指派給最近中心」，這是 K-means 的做法，不是 GMM。
- 階層式分群沒有「預設群數 X」：階層式分群是由下而上（或由上而下）合併或分裂，最後用樹狀圖（dendrogram）呈現，使用者事後再決定切幾層。pseudocode 開頭就要求輸入 X（群數），這是 K-means 的特徵，不是階層式。
- DBSCAN 沒有「中心更新」這步：DBSCAN 根據密度定義群，核心概念是「高密度區域的點」，不需要計算群平均值或更新中心。pseudocode 中明確有「更新中心為該群所有點的平均值」，這是 K-means 獨有的。
- 「收斂條件 = 中心不再移動」是 K-means 特徵：其他三種演算法都沒有「當中心不再移動時停止」這個終止條件。DBSCAN 沒有迭代、階層式沒有「中心」的概念、GMM 的停止條件是 log-likelihood 不再增加。
- 輸出同時有 clusters 和 centroids：K-means 的輸出包含每筆資料的群號（clusters）和每群的中心座標（centroids），這兩個輸出在 pseudocode 裡都有明確標示，和 K-means 的 API 完全吻合。
新方法
逐行對照 pseudocode 與 K-means 定義
旅行衛星的工程師把 pseudocode 和 K-means 定義逐行比對：
「輸入 X（群數）」= K-means 要求事先指定 K 的核心特徵
「隨機選 X 個資料點作為初始中心」= K-means 初始化步驟，稱為 random initialization
「計算到每個中心的距離，指派給最近的中心」= Assignment Step，用歐氏距離（Euclidean distance）
「計算群內所有點的平均值，更新中心」= Update Step，這就是「means」這個字的來源
「當中心不再變動時停止」= 收斂條件（convergence criterion）
「回傳 clusters 和 centroids」= K-means 的標準輸出
每一行都完美對應 K-means 的定義，排除了其他三個選項。這就是選項 A 講的：K-means 分群（K-means Clustering）。
中級考試大概率會考程式碼跟公式，所以這部分你還是要學。但如果現在學起來很痛苦，可以先跳過，等讀完其他題目回頭再來。
Step 1 純故事版
把 1000 個彈珠分成 3 堆，用顏色（特徵）分。先隨便拿 3 個彈珠，當各堆的「代表」。接下來每個彈珠都靠近最像它的代表，分好堆後重新找新代表（這堆所有彈珠平均出來的想像彈珠）。反覆換代表、重分堆，直到換來換去代表都不動了，這就結束了。
Step 2 中文 ↔ 程式碼對照
| 白話說法 | pseudocode / 程式碼 |
|---|---|
| 輸入：N 筆資料、要分幾群 | data_points, X |
| 隨機選初始中心 | centroids = random.sample(data_points, X) |
| 計算每點到每個中心的距離 | dist = euclidean(point, centroid) |
| 分進最近的群 | clusters[i] = argmin(dist) |
| 更新中心為群平均 | centroids[k] = mean(data_points[clusters==k]) |
| 直到中心不再變動 | while not converged |
Step 3 符號角色表
- K（或 X）：事先設定的群數，是 K-means 最重要的超參數，需要人工指定。
- centroid：群中心（質心），是群內所有點的特徵平均值，每次 Update Step 後重算。
- Assignment Step：把每筆資料指派給距離最近的 centroid，決定每個點屬於哪群。
- Update Step：重算每群的 centroid，K-means 名稱中 "means" 就是這一步的「計算平均值」。
- 收斂（converge）：所有 centroid 的位置與上一輪相同（或變動幅度小於閾值），迭代停止。
Step 4 完整公式對應
K-means 核心公式有兩個：
| 意義 | 公式 |
|---|---|
| Assignment Step：把點 x 分進最近的群 | c(i) = argmin_k ‖x(i) − μ_k‖² |
| Update Step：重算第 k 群的中心 | μ_k = (1/|S_k|) Σ x(i)，其中 x(i)∈S_k |
| 目標函式（最小化群內誤差平方和） | J = Σ_k Σ_{x∈S_k} ‖x − μ_k‖² |
Step 5 自我複述
- K-means 需要事先知道幾個超參數？分別是什麼？
- Assignment Step 和 Update Step 各做什麼事？哪個步驟讓名字叫「means」？
- K-means 的收斂條件是什麼？達到收斂後輸出什麼？
- K-means 和 DBSCAN 最大的差別是什麼？各適合什麼形狀的群？
- 為什麼說 K-means 是「非監督式學習」？訓練時需要標籤嗎？
錯選項
為什麼其他選項是錯的
B高斯混合模型分群（GMM）
字面在說什麼
GMM 也是一種分群方法，可能和這段 pseudocode 對應。
為什麼不對
GMM 使用期望最大化（EM 演算法），每個點屬於某群的方式是計算「機率」，而不是「距離最近的中心」。GMM 的 E-step 算每個點屬於各群的後驗機率，M-step 更新每群的均值、變異數和權重。pseudocode 裡只有距離計算和平均值更新，沒有任何機率或變異數的概念，所以不是 GMM。
誰會選錯
記得「GMM 也有類似 centroid 的均值參數」的人，混淆了 GMM 的均值（高斯分佈的 μ）和 K-means 的 centroid（群重心），兩者更新方式完全不同。
C階層式分群（Hierarchical Clustering）
字面在說什麼
階層式分群也是分群方法，可能描述這段流程。
為什麼不對
階層式分群的核心是建立樹狀結構（dendrogram），不需要預先指定群數，也不需要「更新中心」這個步驟。pseudocode 第一行就要求輸入群數 X，階層式分群做不到這件事，它是先分析完所有資料的合併/分裂關係，最後才讓使用者選切幾群。
誰會選錯
只知道「階層式分群也有群」但不了解它「不需要預設群數」這個根本特徵的人。
DDBSCAN 分群
字面在說什麼
DBSCAN 也是常見的分群演算法，可能就是這段 pseudocode 描述的。
為什麼不對
DBSCAN 根據密度定群，核心概念是「核心點（core point）」「邊界點（border point）」「雜訊點（noise point）」，整個演算法不需要計算群中心、不需要更新中心、不需要事先指定群數。pseudocode 裡有「隨機選 X 個初始中心」和「更新中心為群平均」這兩個步驟，DBSCAN 完全沒有這種操作。
誰會選錯
考前背「DBSCAN 也是分群演算法」但沒記住它和 K-means 核心差異的人：DBSCAN 不需要 K、不計算距離到中心、不更新中心。
變形題
同個考點下次怎麼變形
答案
K-means 保證收斂，因為每一輪迭代都只會讓目標函式（群內誤差平方和 J）減少或維持不變，所以不可能無限迭代。但收斂不一定得到全域最佳解，只是局部最佳。初始中心選得不好可能需要很多輪才收斂，實務上通常跑多次（random restart）取最好的結果。
答案
K-means 效果差。因為 K-means 用歐氏距離判斷「最近」，只能分出球形群（convex clusters）。月牙形或環形資料的「距離最近的中心」不等於「同一個形狀結構」。這種情況應該用 DBSCAN（以密度定群）或 Spectral Clustering（考慮拓撲結構），而非 K-means。
答案
K-means++ 改進的是初始化步驟：標準 K-means 隨機選初始中心，可能導致多個中心聚在一起，收斂到很差的局部最佳解。K-means++ 選初始中心時刻意讓它們分散：第一個隨機選，之後每個新中心以「與已選中心的距離平方」為機率選出，讓初始中心分佈更均勻，通常能更快收斂到更好的結果。
答案
把圖片的每個像素顏色（RGB）視為資料點，用 K-means 分成 K 群（例如 K=256）。每個像素用它所在群的 centroid 顏色代替，這樣只需要儲存 256 個顏色和每個像素的群號，大幅減少資料量。這是「向量量化（Vector Quantization）」的基本概念，K-means 是其中最常用的方法。
答案
常用手肘法（Elbow Method）：對 K=1,2,3...N 跑 K-means，畫出每個 K 對應的群內誤差平方和（WCSS）。WCSS 隨 K 增加而下降，但降幅在某個 K 之後會明顯變緩，這個「轉折點」就像手肘，建議選那個 K。另一個指標是輪廓分數（Silhouette Score），值越接近 1 表示每個點和自己群的距離比與最近外群的距離小得多，群分得越好。
延伸
想再往下看，這 5 個
- K-means 分群（K-means Clustering）
本題核心考點：事先指定群數 K、反覆做分派和更新中心兩步驟直到收斂的非監督式分群演算法。 - 非監督式學習（Unsupervised Learning）
K-means 屬於非監督式學習，訓練時不需要人工標籤，直接從資料結構中發現群體。 - 密度分群（DBSCAN）
和 K-means 對比的分群演算法，以密度定群、不需要事先指定群數，能處理任意形狀的群。 - 降維處理（Dimensionality Reduction）
K-means 在高維資料表現較差，通常先用 PCA 等降維方法處理後再分群，是實務常見的前處理步驟。 - 特徵縮放（Feature Scaling）
K-means 用距離計算，必須先做特徵縮放（如標準化），否則數值範圍大的特徵會主導分群結果。