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 更新 改变聚类目标并更新中心。 奇异值分解与主成分 通过另一种平方距离目标选择低维表示。 课程书目 集中列出进一步阅读的书籍。