4.1 Voronoi 區域與 k 中心問題

動機

選出一組代表點之後，還要說明其餘觀測值如何與它們聯繫。 把每個觀測值分配到最近代表點，便得到一個聚類規則。在歐氏空間，這個規則 也為尚未量度的可能觀測值劃出幾何區域。Voronoi 區域把所有位置的答案一併描述， 不用逐一測試空間中的每一點。

代表點的位置則是第二個問題。k 中心目標控制觀測值到其代表點的最大距離。 當每個觀測值都需要距離保證時，這個目標很自然：很小的平均距離， 不能補償一個離所有中心都很遠的觀測值。最近站點幾何決定分配方式， 而最大距離目標決定應選哪些站點。

計算中有兩種平局：一個觀測值可能有多個最近站點，貪婪選擇也可能有多個 同樣遠的候選觀測值。明確的平局規則使計算可重現，卻不改變到集合的最小距離， 或這些距離的最大值。閉幾何區域保留共同邊界；單值分配則決定平局觀測值的歸屬。

定義

定義

最近站點與閉 Voronoi 區域

對互不相同的歐氏站點 $S=\{s_1,\ldots,s_k\}\subset\mathbb R^d$，定義

$$V_i=\{x\in\mathbb R^d:\|x-s_i\|_2\le\|x-s_j\|_2,\ \forall j\}.$$

這些集合是閉 Voronoi 區域。它們覆蓋整個空間，並可在等距邊界上重疊。 若需要單值分配，可在所有最近站點中選擇編號最小者。

區域不只包含已觀測的數據。它與有限數據集的交集，才給出可能分配到該站點的 觀測值。不同區域的開內部互不重疊，而非嚴格不等式保留了邊界上的全部點。 站點互不相同的條件很重要：重合站點的距離函數完全相同， 可能共享整片區域，而不只是邊界。

定義

度量 k 中心半徑

設 $X$ 是度量空間 $(M,d)$ 的非空有限子集，且 $1\le k\le|X|$。 對非空中心集合 $S$，定義

$$d(x,S)=\min_{s\in S}d(x,s),\qquad R(X,S)=\max_{x\in X}d(x,S).$$

k 中心問題以 $k$ 個中心最小化這個半徑。中心可限制在 $X$ 內， 也可與位於較大空間 $M$ 中的中心作比較。

度量具有對稱性，並滿足三角不等式。選擇哪個度量是問題的一部分。 普通歐氏距離是度量，其平方一般卻不是。對固定中心，這兩種量可以給出相同分配， 但相應近似保證的常數並不相同。

定理/命題

命題

歐氏 Voronoi 區域是半空間的交集

站點 $s_i$ 的區域可寫成

$$V_i=\bigcap_{j\ne i} \{x:2(s_j-s_i)^Tx\le\|s_j\|_2^2-\|s_i\|_2^2\}.$$

因此它是閉凸多面體區域，而且可以無界。兩個站點之間的等式超平面 是它們連線的垂直平分面。

命題

空外接圓與 Delaunay 對偶

設平面上至少有三個站點，沒有三點共線，也沒有四點共圓。 三個站點構成 Delaunay 三角形，當且僅當其外接圓內部沒有其他站點。 外心是對應的 Voronoi 頂點；以 Delaunay 邊相連的兩站點，其 Voronoi 區域共享一條邊。

定理

最遠點優先法的二倍半徑保證

任取 $s_1\in X$，之後每次加入到目前中心集合距離最大的觀測值， 直至選出 $k$ 個中心。設結果為 $S$。對同一度量空間內任何含 $k$ 個中心的集合 $O$，

$$R(X,S)\le2R(X,O).$$

所以當最優中心集合存在時，$R(X,S)\le2R^*$，其中 $R^*$ 是最優半徑。 演算法選出的中心本身都屬於 $X$。

證明思路

兩個歐氏距離均非負，平方保留其大小次序。 展開 $\|x-s_i\|_2^2\le\|x-s_j\|_2^2$，兩邊的 $x^Tx$ 消去， 便得到半空間不等式。交集保留凸性及閉性。 凸性表示同一區域內任意兩點之間的線段仍在區域內，不表示區域面積有限。

外心與三角形的三個頂點等距。其外接圓為空，恰好表示沒有其他站點更接近外心， 所以外心是三個區域的共同最近站點位置。上述一般位置條件令恰好三個區域在此相遇， 把其站點連接便得到對偶三角形。這也解釋了為何圓內加入第四個站點會使舊三角形失效。

在這些條件下，對偶三角形填滿站點的凸包，但 Voronoi 區域覆蓋整個平面。 凸包上的站點具有無界區域，凸包邊對應一條向外延伸的 Voronoi 射線。 兩幅幾何圖的範圍並不相同：站點連線位於凸包內，對偶平分線卻可延伸至凸包外。 只共享一個頂點，也不同於共享一條邊；相鄰規則使用的是一維共同邊界， 而不是兩個閉區域的任意共同點。

證明近似保證時，記 $R=R(X,S)$，先考慮 $R>0$。 再選一個到 $S$ 最遠的見證點 $s_{k+1}$，但不把它放進輸出的中心集合。 貪婪過程中的目前半徑不會增加，所以每個新站點與所有先前站點的距離 都至少等於最終半徑 $R$。於是

$$d(s_i,s_j)\ge R\qquad(1\le i<j\le k+1).$$

把這 $k+1$ 個點分配到 $O$ 中的最近中心。由鴿籠原理，其中兩點共享一個中心 $o$。 設 $r=R(X,O)$，三角不等式給出

$$R\le d(s_i,s_j)\le d(s_i,o)+d(o,s_j)\le2r.$$

若 $R=0$，所需不等式直接成立。論證對任何比較集合 $O$ 都有效， 所以同時涵蓋數據中心限制及較大空間中的最優中心。 每一步都使用普通度量距離，包括到比較中心的距離。

更仔細地說，若 $S_t$ 是首 $t$ 個選中站點，則 $R(X,S_1)\ge\cdots\ge R(X,S_k)$。新站點 $s_j$ 到先前站點的最小距離為 $R(X,S_{j-1})$，而到每一個先前站點的距離都不少於這個最小值。 見證點 $s_{k+1}$ 也滿足同一敘述，其最小距離恰好是 $R$。 正的最終半徑保證見證點與各已選站點不同。 這才是鴿籠論證需要的分離性；貪婪選擇不必與比較中心重合。

例題

例題

例題 1：計算三個區域及一條無界邊

取 $s_1=(0,0)$、$s_2=(4,0)$、$s_3=(0,4)$。把位置寫成 $(u,v)$，半空間公式給出

$$V_1=\{u\le2,\ v\le2\},\qquad V_2=\{u\ge2,\ v\le u\},\qquad V_3=\{v\ge2,\ u\le v\}.$$

對 $(3,1)$，三個平方距離為 $10$、$2$、$18$，所以第二站點唯一最近。 在 $(2,1)$，首兩個平方距離都是 $5$，第三個是 $13$。 該點屬於兩個閉區域，但最小編號規則把它分配到第一站點。

首兩個區域的共同邊界是 $\{(2,t):t\le2\}$，即向下的射線。 其餘兩邊是一條從 $(2,2)$ 向左的射線，以及沿 $u=v$ 向東北的射線。 共同頂點 $(2,2)$ 到每個站點的平方距離均為 $8$。 Delaunay 對偶就是連接三站點的三角形。其外心恰好在斜邊上； Voronoi 頂點並不一定處於對偶三角形內部。

例題

例題 2：加入站點令舊三角形失效

在上述站點中加入 $s_4=(1,1)$。舊外接圓的圓心為 $(2,2)$、平方半徑為 $8$， 新站點到圓心的平方距離卻只有 $2$。圓不再為空，舊三點不再構成 Delaunay 三角形， 而 $(2,2)$ 也不再是這三個站點的共同最近站點頂點。

改看頂點為 $(0,0)$、$(4,0)$、$(1,1)$ 的三角形。 首兩點的等距條件是 $u=2$，首、第三點的條件是 $u+v=1$， 所以外心為 $(2,-1)$，平方半徑為 $5$。 餘下站點 $(0,4)$ 到此外心的平方距離為 $29$，故此圓為空，新三角形屬於 Delaunay 圖。 可見只檢查三點等距並不足夠；其他站點共同決定外心是否也是 Voronoi 頂點。

例題

例題 3：二倍界限確實可以達到

在直線上使用普通距離，取 $X=\{0,1,2,8,9,10\}$、$k=2$。 從 $0$ 開始，最遠點優先法選出 $10$。到選中集合的距離為

$$\begin{array}{c|rrrrrr} x&0&1&2&8&9&10\\ d(x,\{0,10\})&0&1&2&2&1&0 \end{array}$$

貪婪半徑為 $2$，而中心 $1$、$9$ 可用半徑 $1$ 覆蓋所有觀測值。 任何兩中心解的半徑都不可能小於 $1$：觀測值 $0$、$2$、$10$ 的兩兩距離至少為 $2$， 其中兩點必須共享一個中心，三角不等式便迫使覆蓋半徑至少為 $1$。 因此 $R^*=1$，二倍界限恰好達到。比較中心本身也是觀測值， 所以把中心限制在數據集內時，結論仍相同。

計算分配與最遠點優先中心

以下 NumPy 計算為每個觀測值保存到目前中心的最小距離。 加入中心只會使這些距離不變或減少，所以以逐項最小值更新。 若最遠點平局，陣列次序令程式選擇第一個出現的位置。

import numpy as np

X = np.array([0.0, 1.0, 2.0, 8.0, 9.0, 10.0])
k = 2
selected = [0]
nearest = np.abs(X - X[selected[0]])
for _ in range(1, k):
    j = int(np.argmax(nearest))
    selected.append(j)
    nearest = np.minimum(nearest, np.abs(X - X[j]))
centres = X[selected]
labels = np.argmin(np.abs(X[:, None] - centres[None, :]), axis=1)
print("centres:", centres.tolist())
print("labels:", labels.tolist())
print("radius:", float(nearest.max()))

centres: [0.0, 10.0]
labels: [0, 0, 0, 1, 1, 1]
radius: 2.0

對 $\mathbb R^d$ 中的觀測值，可把絕對差改成列向量差的歐氏範數。 直接計算需要 $O(n)$ 距離儲存量，以及 $O(nkd)$ 算術運算。 單次最近站點查詢要比較到各站點的距離；Voronoi 圖則記錄整個空間中答案如何改變。 兩者處理的計算目的不同。

最遠點優先法也記錄了逐漸縮小的覆蓋半徑。 關鍵是「到最近中心距離」的目前最大值，不是「到某一個中心距離」的最大值。 一點可以離某中心很遠，卻已由另一中心完美代表。若使用後一種量選點， 就沒有遵循已證明的貪婪規則。

半徑保證只關乎 $X$ 中的有限觀測值，並不限制無界 Voronoi 區域中的每一個位置： 這些位置可以任意遠離其站點。區域描述可能觀測值的分配規則， 計算半徑則認證給定數據的距離。把最大值的取值範圍寫清楚，便不會混淆兩種用途。

特徵單位也能改變幾何。對查詢點 $(0,0)$ 和站點 $(0,3)$、$(2,0)$，第二站點較近。 把第一座標加倍後，站點變成 $(0,3)$、$(4,0)$，反而第一站點較近。 若所有座標共同乘同一比例，所有距離與半徑只會乘上該比例，近似比值保留； 分別縮放不同座標，則在原座標中定義了另一個距離模型。

常見錯誤

常見錯誤

忽略幾何結論的適用條件

Voronoi 邊可以是有限線段、射線，或在兩站點情況下是一條完整平分線。 邊界區域常常無界。平面 Delaunay 三角形的對應使用上述一般位置條件； 四點共圓可令四個區域共享頂點，並使三角剖分不唯一。

半空間推導用了歐氏平方範數的展開。其他度量可形成不同形狀的區域， 所以這個平分面公式並非一般度量恆等式。 最遠點優先保證容許較一般的幾何，卻需要度量的三角不等式。 平方歐氏距離保留貪婪次序，但普通半徑的二倍界會變成平方半徑的四倍界。

總結

最近站點幾何把兩兩距離比較化為凸的歐氏區域，閉區域保留平局邊界。 空外接圓辨認對應的 Delaunay 三角形。 對度量 k 中心聚類，最遠點優先選擇產生互相分離的見證點， 再由鴿籠原理與三角不等式，把其最大分配距離與任意最優半徑比較。

練習

思考檢查

練習 1：站點為 $(0,0)$、$(6,0)$，推導其閉區域。$(3,5)$ 位於哪裏？最小編號規則如何分配它？

展開平方距離不等式，並保留等號情況。

思考檢查

練習 2：四站點為 $(0,0)$、$(2,0)$、$(2,2)$、$(0,2)$。求共同等距點，並指出哪一項一般位置條件失效。

計算正方形中心到每個頂點的平方距離。

思考檢查

練習 3：對 $X=\{0,2,3,9\}$、$k=2$，從 $3$ 開始執行最遠點優先法。求選中站點及最終半徑。

加入最遠點後，更新所有觀測值到最近中心的距離。

思考檢查

練習 4：在例題 3 中，貪婪中心與最優中心的最大平方分配距離各是多少？比值如何？為何不能直接把度量證明套用到平方歐氏距離？

把兩個半徑平方，並用 $0$、$1$、$2$ 檢查三角不等式。

解答

解答 · 練習 1 解答

兩區域為 $u\le3$、$u\ge3$，共同邊界是完整垂直線。 $(3,5)$ 屬於兩區域，到兩站點的平方距離同為 $34$，最小編號規則把它分配到第一站點。

解答 · 練習 2 解答

共同點為 $(1,1)$，到每個站點的平方距離都是 $2$。 四站點共圓，所以沒有四點共圓的條件失效。四區域在此相遇； 剖分正方形時可選任一條對角線。

解答 · 練習 3 解答

到 $3$ 的距離為 $3$、$1$、$0$、$6$，所以第二站點是 $9$。 到 $\{3,9\}$ 的最近距離變成 $3$、$1$、$0$、$0$，最終半徑為 $3$。

解答 · 練習 4 解答

兩個最大平方距離是 $4$、$1$，比值為 $4$。 平方歐氏距離不滿足三角不等式，因為 $(2-0)^2=4>(1-0)^2+(2-1)^2=2$。 度量定理適用於普通半徑，把結論平方才得到平方半徑的四倍界。

相關筆記

中心目標與 Lloyd 更新 改變聚類目標，並更新中心。 奇異值分解與主成分 以另一個平方距離目標選擇低維表示。 課程書目 集中列出進一步閱讀資料。