算法导论33.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 3.4k 阅读时长 ≈ 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)}}xa^2-2\sum{\mathbf{x,y}\in S^{(\ell)}}xay_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)}}xa^2-2\left(\sum{\mathbf{x}\in S^{(\ell)}}xa\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)}}xa^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)}}xa^2-|S^{(\ell)}|(c_a^{(\ell)})^2\right)\
&=\sum{\ell=1}^k\sum{a=1}^d\left(\sum{\mathbf{x}\in S^{(\ell)}}xa^2-2\left(\sum{\mathbf{x}\in S^{\ell}}\right)ca^{(\ell)}+|S^{(\ell)}|(c_a^{(\ell)})^2\right)&\qquad(C)\
&=\sum{\ell=1}^k\sum{a=1}^d\sum{\mathbf{x}\in S^{(\ell)}}(xa-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-{x3},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$的已排好序的数组（也就是这个数据集）。令状态$gi,j$表示将$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