算法导论33.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 3.7k 阅读时长 ≈ 3 分钟

33.1-1

\(\begin{aligned} f(S,C)&=\sum_{\ell=1}^k\dfrac{1}{2|S^{(\ell)}|}\sum_{\mathbf{x,y}\in S^{(\ell)}:\mathbf{x\neq y}}\Delta(\mathbf{x,y})\\ &=\sum_{\ell=1}^k\dfrac{1}{2|S^{(\ell)}|}\sum_{\mathbf{x,y}\in S^{(\ell)}}\Delta(\mathbf{x,y})&\qquad(A)\\ &=\sum_{\ell=1}^k\dfrac{1}{2|S^{(\ell)}|}\sum_{a=1}^d\sum_{\mathbf{x,y}\in S^{(\ell)}}(x_a-y_a)^2\\ &=\sum_{\ell=1}^k\dfrac{1}{2|S^{(\ell)}|}\sum_{a=1}^d\left(2|S^{(l)}|\sum_{\mathbf{x}\in S^{(\ell)}}x_a^2-2\sum_{\mathbf{x,y}\in S^{(\ell)}}x_ay_a\right)\\ &=\sum_{\ell=1}^k\dfrac{1}{2|S^{(\ell)}|}\sum_{a=1}^d\left(2|S^{(l)}|\sum_{\mathbf{x}\in S^{(\ell)}}x_a^2-2\left(\sum_{\mathbf{x}\in S^{(\ell)}}x_a\right)^2\right)\\ &=\sum_{\ell=1}^k\dfrac{1}{2|S^{(\ell)}|}\sum_{a=1}^d\left(2|S^{(l)}|\sum_{\mathbf{x}\in S^{(\ell)}}x_a^2-2|S^{(\ell)}|^2(c_a^{(\ell)})^2\right)&\qquad(B)\\ &=\sum_{\ell=1}^k\sum_{a=1}^d\left(\sum_{\mathbf{x}\in S^{(\ell)}}x_a^2-|S^{(\ell)}|(c_a^{(\ell)})^2\right)\\ &=\sum_{\ell=1}^k\sum_{a=1}^d\left(\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\right)&\qquad(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)}}\Delta(\mathbf{x,c^{(\ell)}}) \end{aligned}\)

其中，步骤\((A)\)是基于\(\Delta(\mathbf{x,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^{(1)},x^{(3)}}\in S^{(1)};\mathbf{x^{(2)},x^{(4)}}\in S^{(2)}\)。经过一次迭代后，发现\(S^{(1)}\)的重心仍然是\(\mathbf{c^{(1)}}\)，并且\(S^{(2)}\)的重心仍然是\(\mathbf{c^{(2)}}\)，所有点的归属不会改变，算法终止，\(f(S,C)=4\)。

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

33.1-3

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

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

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

1
2
3
4
5
6
7
8
9
10
11
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{aligned} ((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{aligned}\)

并且相对于\(S^{(1)}\)中的元素而言，\(\forall x\in S-\{x_3\},x\le x_1\)都成立，那么令\(S'^{(1)}=(S-\{x_3\})\cup \{x_2\}\)，可以知道\(\sum_{x} \Delta(x,c_1)\)将会减少（\(S'^{(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]= \left \{\begin{aligned} &0 & & \text{if}\quad j=0 \\ &\infty & & \text{if}\quad i = 0\land j > 0 \\ &\min_{l=0}^{j} \{g[i-1,l]+w_X(l,j)\} & & \text{if}\quad i > 0\land j > 0 \\ \end{aligned}\right.\)

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

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

\(\begin{aligned} w(i,j)&=\dfrac{1}{2(j-i)}\left(2(j-i)\sum_{k=i+1}^jX[i]^2-2\left(\sum_{k=i+1}^jX[i]\right)^2\right)\\ &=\sum_{k=i+1}^jX[i]^2-\dfrac{1}{j-i} \left(\sum_{k=i+1}^jX[i]\right)^2 \end{aligned}\)

令\(\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]-\dfrac{(S[j]-S[i])^2}{j-i}\)。也就是说，使用\(O(n)\)的运行时间预处理出\(S,T\)后，就可以以\(O(1)\)的时间计算\(w\)。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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