選中心、分群、搬到平均、重複到不動：
這段虛擬碼是哪一種演算法？

這題一樣不考語法，考的是看懂流程。下面先講什麼是分群、中心和平均，中間兩支動畫：一支在地圖上把 4 輪演一次，一支把虛擬碼翻成 Python、打開記憶體一行一行跑。

把觀念合起來：kmeans 在記憶體裡怎麼跑

動畫 2打開記憶體：一輪一輪跑 kmeans2 分 22 秒・有旁白，也有字幕

🔒這支動畫在完整版試看版每頁開放第 1 支動畫

0:00開始 0:07stores 0:14步驟 1 random.sample 0:23while True 0:292a 量距離 0:48clusters 1:002b zip 1:15算平均 1:31步驟 3 比較 1:44第 2～4 輪 1:59break 與 return

畫面上的位址（0x…）、距離、群號和中心，都取自同一次實際執行（Python 3.13.7，random.seed(3)）。位址每次執行都不同。

四個選項都是分群演算法，最後也都會給每個點一個群號；差別在怎麼決定誰和誰一群。下表的最後一列，是 scikit-learn 1.8.0 在這 12 間店上實際分出來的結果。

資料分得很開的時候，四種方法的結果可能一模一樣，所以不能只看結果認演算法，要看做法。虛擬碼寫的「指派給最近的中心」「中心更新為平均值」「中心不再變動時停止」，只有 K-means 是這樣做的。GMM 也是兩個步驟反覆，但每個點分給每一群的是機率（軟分群），而且每群除了平均還要學形狀；新店 (5, 4) 在 GMM 裡屬於東邊那群的機率是 0.9986，不是「直接指派」。

scikit-learn 的 K-means：KMeans（實測 1.8.0）

KMeans(n_clusters=8, *, init='k-means++', n_init='auto', max_iter=300, tol=0.0001,
       verbose=0, random_state=None, copy_x=True, algorithm='lloyd')

實測：給它和本頁 Python 一樣的起點 (1, 3.5)、(5, 9)、(4, 8)，n_init=1，結果 labels_、cluster_centers_ 完全相同，n_iter_ 是 4、inertia_ 是 14.125。用預設的 k-means++，只跑 2 輪就到同樣的 14.125。

虛擬碼沒有規定的事

實驗 1 用 JavaScript 照 §3 的 Python 即時計算（距離用和 Python 的 math.dist 同樣的算法，算到最後一位都一樣）。起點是事先用 Python 的 random.sample 抽好的：X＝2～5、種子 0～19、有沒有偏遠的店，共 160 組。本頁用 Node.js 跑同一段計算程式，從這 160 組起點一路跑到收斂，和 Python 3.13.7 實際執行的每一輪中心、分群、總和比對了 1,066 個結果，全部一致。實驗 2 的每一種分法，是事先用 scikit-learn 1.8.0 實際算出來的。

動畫 3四個選項，四種分法：同一張地圖比一比2 分 16 秒・有旁白，也有字幕

🔒這支動畫在完整版試看版每頁開放第 1 支動畫

0:00四個選項 0:06A K-means 0:13k-means++ 0:30B GMM 0:54C 階層式 1:18D DBSCAN 1:36結果一樣 1:44偏遠的店 1:59答案 A

每一種分法、GMM 的橢圓與機率、階層式的合併距離、DBSCAN 的核心點，都是 scikit-learn 1.8.0（SciPy 1.16.2）在這 12 間店上實際算出來的。顏色照區域上（西南藍、北邊橘、東邊綠），因為各方法的群號編法不同。

先把虛擬碼的每一步，拿去問四種方法「你有沒有做這件事」：

考場上的辨識口訣：看到這些詞，就是這個演算法

常見的錯誤想法

程式 1 只用 Python 本身，裝好 Python 就能跑。程式 2、3 用到 scikit-learn 和 NumPy，要先安裝：pip install scikit-learn（Google Colab 已經內建，直接貼上就能跑）。

程式 1：把虛擬碼翻成 Python，一輪一輪印出來

import math
import random

def kmeans(data_points, X):
    centroids = random.sample(data_points, X)                  # 1
    rnd = 0
    while True:                                                # 2
        clusters = []                                          # 2a 分群
        for p in data_points:
            distances = [math.dist(p, c) for c in centroids]
            clusters.append(distances.index(min(distances)))
        new_centroids = []                                     # 2b 更新中心
        for k in range(X):
            members = [p for p, c in zip(data_points, clusters) if c == k]
            new_centroids.append((sum(x for x, y in members) / len(members),
                                  sum(y for x, y in members) / len(members)))
        rnd += 1
        print(f'第 {rnd} 輪：中心 {[(round(x, 2), round(y, 2)) for x, y in centroids]} → 分群 {clusters}')
        if new_centroids == centroids:                         # 3
            break
        centroids = new_centroids
    return clusters, centroids

# 12 間店在地圖上的位置（公里）
stores = [(1.5, 2), (2, 1), (2.5, 3), (1, 3.5), (7, 2.5), (8, 1.5),
          (8.5, 3), (7.5, 4), (4, 8), (5, 9), (5.5, 7.5), (3.5, 7)]
random.seed(3)
clusters, centroids = kmeans(stores, 3)
print('clusters =', clusters)
print('centroids =', centroids)

第 1 輪：中心 [(1, 3.5), (5, 9), (4, 8)] → 分群 [0, 0, 0, 0, 0, 0, 2, 2, 2, 1, 1, 2]
第 2 輪：中心 [(3.67, 2.25), (5.25, 8.25), (5.88, 5.5)] → 分群 [0, 0, 0, 0, 2, 0, 2, 2, 1, 1, 1, 1]
第 3 輪：中心 [(3.0, 2.2), (4.5, 7.88), (7.67, 3.17)] → 分群 [0, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1]
第 4 輪：中心 [(1.75, 2.38), (4.5, 7.88), (7.75, 2.75)] → 分群 [0, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1]
clusters = [0, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1]
centroids = [(1.75, 2.375), (4.5, 7.875), (7.75, 2.75)]

程式 2：和 scikit-learn 的 KMeans 對答案

import numpy as np
from sklearn.cluster import KMeans

stores = np.array([(1.5, 2), (2, 1), (2.5, 3), (1, 3.5), (7, 2.5), (8, 1.5),
                   (8.5, 3), (7.5, 4), (4, 8), (5, 9), (5.5, 7.5), (3.5, 7)])

# 和程式 1 一樣的起點：(1, 3.5)、(5, 9)、(4, 8)，只跑 1 次
same = KMeans(n_clusters=3, init=np.array([(1, 3.5), (5, 9), (4, 8)]), n_init=1).fit(stores)
print('同樣的起點：labels_ =', same.labels_.tolist())
print('            cluster_centers_ =', same.cluster_centers_.tolist())
print('            n_iter_ =', same.n_iter_, '｜inertia_ =', same.inertia_)

# 壞的起點：(8, 1.5)、(2.5, 3)、(8.5, 3)
bad = KMeans(n_clusters=3, init=np.array([(8, 1.5), (2.5, 3), (8.5, 3)]), n_init=1).fit(stores)
print('壞的起點：labels_ =', bad.labels_.tolist(), '｜inertia_ =', bad.inertia_)

# 預設：init='k-means++'
model = KMeans(n_clusters=3, random_state=0).fit(stores)
print('預設 k-means++：labels_ =', model.labels_.tolist(), '｜n_iter_ =', model.n_iter_, '｜inertia_ =', model.inertia_)
print('新店 (5, 4) 屬於群', model.predict([(5, 4)])[0])

同樣的起點：labels_ = [0, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1]
            cluster_centers_ = [[1.75, 2.375], [4.5, 7.875], [7.75, 2.75]]
            n_iter_ = 4 ｜inertia_ = 14.125
壞的起點：labels_ = [1, 1, 1, 1, 0, 0, 2, 2, 1, 1, 1, 1] ｜inertia_ = 87.25
預設 k-means++：labels_ = [2, 2, 2, 2, 0, 0, 0, 0, 1, 1, 1, 1] ｜n_iter_ = 2 ｜inertia_ = 14.125
新店 (5, 4) 屬於群 0

程式 3：四個選項各跑一次，再加一間偏遠的店

import numpy as np
from sklearn.cluster import KMeans, AgglomerativeClustering, DBSCAN
from sklearn.mixture import GaussianMixture

stores = np.array([(1.5, 2), (2, 1), (2.5, 3), (1, 3.5), (7, 2.5), (8, 1.5),
                   (8.5, 3), (7.5, 4), (4, 8), (5, 9), (5.5, 7.5), (3.5, 7)])

print('A K-means：', KMeans(n_clusters=3, random_state=0).fit(stores).labels_.tolist())
gmm = GaussianMixture(n_components=3, random_state=0).fit(stores)
print('B GMM：    ', gmm.predict(stores).tolist())
print('   新店 (5, 4) 屬於各群的機率：', np.round(gmm.predict_proba([(5, 4)])[0], 4).tolist())
print('C 階層式：  ', AgglomerativeClustering(n_clusters=3).fit(stores).labels_.tolist())
print('D DBSCAN：  ', DBSCAN(eps=1.6, min_samples=3).fit(stores).labels_.tolist())

# 多一間偏遠的店 (9.5, 9.5)
more = np.vstack([stores, [(9.5, 9.5)]])
km = KMeans(n_clusters=3, random_state=0).fit(more)
print('加一間偏遠的店：')
print('  K-means：', km.labels_.tolist(), '中心', np.round(km.cluster_centers_, 2).tolist())
print('  DBSCAN： ', DBSCAN(eps=1.6, min_samples=3).fit(more).labels_.tolist())

A K-means： [2, 2, 2, 2, 0, 0, 0, 0, 1, 1, 1, 1]
B GMM：     [2, 2, 2, 2, 0, 0, 0, 0, 1, 1, 1, 1]
   新店 (5, 4) 屬於各群的機率： [0.9986, 0.0014, 0.0]
C 階層式：   [0, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1]
D DBSCAN：   [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2]
加一間偏遠的店：
  K-means： [2, 2, 2, 2, 0, 0, 0, 0, 1, 1, 1, 1, 1] 中心 [[7.75, 2.75], [5.5, 8.2], [1.75, 2.38]]
  DBSCAN：  [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, -1]