算法导论 33.1 Exercises 答案

33.1-1

$\begin{array}{rl}f(S,C)& =\sum _{\ell =1}^k{\displaystyle \frac{1}{2|S^{(\ell )}|}}\sum _{\mathbf{x}\mathbf{,}\mathbf{y}\in S^{(\ell )}:\mathbf{x}\ne \mathbf{y}}\mathrm{\Delta }(\mathbf{x}\mathbf{,}\mathbf{y})\\ & =\sum _{\ell =1}^k{\displaystyle \frac{1}{2|S^{(\ell )}|}}\sum _{\mathbf{x}\mathbf{,}\mathbf{y}\in S^{(\ell )}}\mathrm{\Delta }(\mathbf{x}\mathbf{,}\mathbf{y})& (A)\\ & =\sum _{\ell =1}^k{\displaystyle \frac{1}{2|S^{(\ell )}|}}\sum _{a=1}^d\sum _{\mathbf{x}\mathbf{,}\mathbf{y}\in S^{(\ell )}}(x_a-y_a{)}^2\\ & =\sum _{\ell =1}^k{\displaystyle \frac{1}{2|S^{(\ell )}|}}\sum _{a=1}^d(2|S^{(l)}|\sum _{\mathbf{x}\in S^{(\ell )}}{x}_a^2-2\sum _{\mathbf{x}\mathbf{,}\mathbf{y}\in S^{(\ell )}}{x}_a{y}_a)\\ & =\sum _{\ell =1}^k{\displaystyle \frac{1}{2|S^{(\ell )}|}}\sum _{a=1}^d(2|S^{(l)}|\sum _{\mathbf{x}\in S^{(\ell )}}{x}_a^2-2{\left(\sum _{\mathbf{x}\in S^{(\ell )}}{x}_a\right)}^2)\\ & =\sum _{\ell =1}^k{\displaystyle \frac{1}{2|S^{(\ell )}|}}\sum _{a=1}^d(2|S^{(l)}|\sum _{\mathbf{x}\in S^{(\ell )}}{x}_a^2-2|S^{(\ell )}{|}^2(c_a^{(\ell )}{)}^2)& (B)\\ & =\sum _{\ell =1}^k\sum _{a=1}^d(\sum _{\mathbf{x}\in S^{(\ell )}}{x}_a^2-|S^{(\ell )}|(c_a^{(\ell )}{)}^2)\\ & =\sum _{\ell =1}^k\sum _{a=1}^d(\sum _{\mathbf{x}\in S^{(\ell )}}{x}_a^2-2\left(\sum _{\mathbf{x}\in S^{\ell }}\right)c_a^{(\ell )}+|S^{(\ell )}|(c_a^{(\ell )}{)}^2)& (C)\\ & =\sum _{\ell =1}^k\sum _{a=1}^d\sum _{\mathbf{x}\in S^{(\ell )}}(x_a-c_a^{(\ell )}{)}^2\\ & =\sum _{\ell =1}^k\sum _{\mathbf{x}\in S^{(\ell )}}\mathrm{\Delta }(\mathbf{x}\mathbf{,}{\mathbf{c}}^{\mathbf{(}\ell \mathbf{)}})\end{array}$

其中，步骤 $(A)$ 是基于 $\mathrm{\Delta }(\mathbf{x}\mathbf{,}\mathbf{x})=0$ 这个事实，步骤 $(B),(C)$ 则使用了第 1010 页所给定的方程 ${\displaystyle -2\sum _{\mathbf{x}\in S^{(\ell )}}{x}_a+2|S^{(\ell )}|c_a^{(\ell )}=0}$ 进行移项，补项。

33.1-2

令 $S=\{(0,0),(1,0),(0,2),(1,2)\},C=\{(0,1),(1,1)\}$，并且 ${\mathbf{x}}^{\mathbf{(}\mathbf{1}\mathbf{)}}\mathbf{,}{\mathbf{x}}^{\mathbf{(}\mathbf{3}\mathbf{)}}\in S^{(1)};{\mathbf{x}}^{\mathbf{(}\mathbf{2}\mathbf{)}}\mathbf{,}{\mathbf{x}}^{\mathbf{(}\mathbf{4}\mathbf{)}}\in S^{(2)}$。经过一次迭代后，发现 $S^{(1)}$ 的重心仍然是 ${\mathbf{c}}^{\mathbf{(}\mathbf{1}\mathbf{)}}$，并且 $S^{(2)}$ 的重心仍然是 ${\mathbf{c}}^{\mathbf{(}\mathbf{2}\mathbf{)}}$，所有点的归属不会改变，算法终止，$f(S,C)=4$。

然而实际上，如果 $C^{\prime }=\{(0.5,0),(0.5,2)\}$，并且 ${\mathbf{x}}^{\mathbf{(}\mathbf{1}\mathbf{)}}\mathbf{,}{\mathbf{x}}^{\mathbf{(}\mathbf{2}\mathbf{)}}\in S^{\prime (1)};{\mathbf{x}}^{\mathbf{(}\mathbf{3}\mathbf{)}}\mathbf{,}{\mathbf{x}}^{\mathbf{(}\mathbf{4}\mathbf{)}}\in S^{\prime (2)}$，那么实际上这个聚类更优，并且有 $f(S,C^{\prime })=1$。

33.1-3

首先使用一个哈希表，对这些点进行去重，最终以 $O(n)$ 的算法得到一个单重集 $X^{\prime }$，其中 $|X^{\prime }|=m$。

如果 $m\le k$，那么直接返回 $m$ 个点和 $k-m$ 个原点即可。返回原点的思想类似 Lloyd 程序的第 4 步。

如果 $m>k$，那么使用练习 5.3-5 的算法返回一个只有大小为 $k$ 的初始中心。由算法 SAMPLE-K-CENTER 给出。

SAMPLE-K-CENTER(X', m, k)
  Let C be new array
  S = ∅
  for i = m - k + 1 to m
    if i ∈ S
      S = S ∪ {k}
      INSERT(C, X'[k])
    else
      S = S ∪ {i}
      INSERT(C, X'[i])
  return C

33.1-4

我们首先需要证明，对于 $X$ 中的任意 $4$ 个数据 $x_1,x_2,x_3,x_4$，其中有 $x_1\le x_2\le x_3\le x_4$。那么如果存在一种聚合方式是将 $x_1,x_3$ 聚合到同一类 $S^{(1)}$，$x_2,x_4$ 聚合到同一类 $S^{(2)}$，那么这种聚合肯定不是最优的。因为更优的方式为 $(x_1,x_2),(x_3,x_4)$。考虑

$\begin{array}{rl}((x_4-x_2{)}^2+(x_3-x_1{)}^2)-((x_4-x_3{)}^2+(x_2-x_1{)}^2)& =2(x_4-x_1)(x_3-x_2)\\ & \ge 0\end{array}$

并且相对于 $S^{(1)}$ 中的元素而言，$\mathrm{\forall }x\in S-\{x_3\},x\le x_1$ 都成立，那么令 $S^{\prime (1)}=(S-\{x_3\})\cup \{x_2\}$，可以知道 $\sum _x\mathrm{\Delta }(x,c_1)$ 将会减少（$S^{\prime (2)}$ 的过程同理）。

这个证明说明了，在一个有序的序列中，只有连续的一整段才有可能是一个最优的聚类方式。也就是说，将一个排好序的数组划分成段一个个段，才是最优的做法。

这给出了我们一个使用动态规划算法最小化 $f(S,C)$ 的值。令 $X$ 是一个长度为 $n$ 的已排好序的数组（也就是这个数据集）。令状态 $g[i,j](0\le i\le k,0\le j\le n)$ 表示将 $X$ 的前 $j$ 个值划分 $i$ 个段时，最近中心平方距离和 $f(X[1:i],C)$ 的最小值。那么可以得到 $g$ 的状态转移方程：

$g[i,j]=\{\begin{array}{rlrl}& 0& & \text{if}j=0\\ & \mathrm{\infty }& & \text{if}i=0\wedge j>0\\ & \underset{l=0}{\overset{j}{min}}\{g[i-1,l]+w_X(l,j)\}& & \text{if}i>0\wedge j>0\end{array}$

其中，$w(i,j)$ 表示数组 $X[i+1:j]$ 被划分到同一块时，其产生的距离平方和。注意状态转移方程的第 3 行，当 $l=j$ 时，表明这个集合是空的，$w(j,j)=0$。

至于 $w(i,j)$ 的计算，我们使用题目 33.1-1 给出的过程，有：

$\begin{array}{rl}w(i,j)& ={\displaystyle \frac{1}{2(j-i)}}(2(j-i)\sum _{k=i+1}^{j}X[i{]}^2-2{(\sum _{k=i+1}^{j}X[i])}^2)\\ & =\sum _{k=i+1}^{j}X[i{]}^2-{\displaystyle \frac{1}{j-i}}{(\sum _{k=i+1}^{j}X[i])}^2\end{array}$

令 ${\displaystyle S[k]=\sum _{i=1}^{k}X[i],T[k]=\sum _{i=1}^{k}X[i{]}^2}$，那么可以将 $w(i,j)$ 进一步化简成 $w(i,j)=T[j]-T[i]-{\displaystyle \frac{(S[j]-S[i]{)}^2}{j-i}}$。也就是说，使用 $O(n)$ 的运行时间预处理出 $S,T$ 后，就可以以 $O(1)$ 的时间计算 $w$。

那么最终答案为 $g[k,n]$，求解的时间复杂度为 $O(n^{2}k)$。求解划分的算法由程序 CLUSTER-1-DIMENSION 给出。

CLUSTER-1-DIMENSION(X, n, k)
  //先进行排序
  RANDOMIZED-QUICKSORT(X, 1, n)
  let S[0 : n], T[0 : n] be new arrays
  for i = 1 to n
    S[i] = S[i - 1] + X[i]
    T[i] = T[i - 1] + X[i] * X[i]
  let g[0 : k, 0 : n], pre[0 : k, 0 : n] be new matrices
  for i = 0 to k
    g[i, 0] = 0
  for j = 1 to n
    g[0, j] = ∞
  for i = 1 to k
    for j = 1 to n
      g[i, j] = g[i - 1, j]
      pre[i, j] = j
      for l = 0 to j - 1
          w = T[j] - T[i] + (S[j] - S[i]) * (S[j] - S[i]) / (j - i)
        if g[i, j] > g[i - 1, l] + w
          g[i, j] = g[i - 1, l] + w
          pre[i, j] = l
  // 开始存储最终答案。
  U = ∅
  now = n
  for i = k down to 1
    p = pre[i, now]
    if p != now
      INSERT(U, X[p + 1 : now])
    now = p
  return g[k, n], U