多元第十二章习题

1.试证明下列结论： (1) 由两个距离的和所组成的函数仍为距离； (2)由一个正常数乘一个距离所组成的函数仍为距离； (3)设$d$为一个距离，$c>0$为常数，则$d^{\ast }=d/(d+c)$仍是一个距离； (4) 由两个距离的乘积所组成的函数不一定是距离.

(1)记$d_{ij}^{(1)}$、$d_{kl}^{(2)}$为两个距离函数$d_{ij}=d_{ij}^{(1)}+d_{ij}^{(2)}$,下面验证距离的三条性质： 由于$d_{ij}^{(1)}、d_{ij}^{(2)}$满足距离的非负性，对称性，三角不等式则

$d_{ij}=d_{ij}^{(1)}+d_{ij}^{(2)}\ge 0$ $d_{ij}^{(1)}+d_{ij}^{(2)}=d_{ji}^{(1)}+d_{ji}^{(2)}$ $d_{ij}^{(1)}+d_{ij}^{(2)}\le d_{ik}^{(1)}+d_{kj}^{(1)}+d_{ik}^{(2)}+d_{kj}^{(2)}$

(2)同理验证三条性质即可

(3)对于函数$f(x)=\frac{x}{x+c}$可知其为一个单调递增函数$f(0)=0$则可知非负性和对称性得证 三角不等式：由(2)只需要验证不等式即可

$$\frac{a+b}{1+a+b}⩽\frac{a}{1+a}+\frac{b}{1+b}$$

在两侧同乘$(1+a+b)(1+a)(1+b)$可得

$ab(2+a+b)⩾0$ 则可知三角不等式成立$d_{ij}$为一个距离

(4)取$d_{ij}^{(1)}$、$d_{kl}^{(2)}$为欧氏距离即可 验证三角不等式：对于$X_1=0,X_2=0.5,X_3=1$

$$\begin{array}{r}{d}_{13}=1^2=1\\ d_{12}=d_{23}=0.25\\ d_{13}\ge d_{12}+d_{23}\end{array}$$

三角不等式不成立，故两个距离的乘积不一定还是一个距离。

2.给出式子详细推导过程

$$\begin{array}{rl}{D}_{MJ}^2& =({\overline{x}}^{(M)}-{\overline{x}}^{(J)}{)}^{\prime }({\overline{x}}^{(M)}-{\overline{x}}^{(J)})\\ & \text{=}={\left[\frac{n_K}{n_M}({\overline{\mathbf{x}}}^{(J)}-{\overline{\mathbf{x}}}^{(K)})+\frac{n_L}{n_M}({\overline{\mathbf{x}}}^{(J)}-{\overline{\mathbf{x}}}^{(L)})\right]}^{\prime }\\ & \times \left[\frac{n_K}{n_M}({\overline{\mathbf{x}}}^{(J)}-{\overline{\mathbf{x}}}^{(K)})+\frac{n_L}{n_M}({\overline{\mathbf{x}}}^{(J)}-{\overline{\mathbf{x}}}^{(L)})\right]\\ & =\frac{n_K}{n_M}{D}_{KJ}^2+\frac{n_L}{n_M}{D}_{LJ}^2-\frac{n_K{n}_L}{n_M^2}{D}_{KL}^2,J\ne K,L.\end{array}$$

下面用简略符号代替证明：(由于转置完都是一个数所以简略写不再加入转置)

$$\begin{array}{rl}& (\frac{n_k}{n_m}{)}^2{D}_{kj}^2+(\frac{n_l}{n_m}{)}^2{D}_{lj}^2+\frac{2n_k{n}_l}{n_m^2}(X_j-X_k)(X_j-X_l)\\ & =\frac{n_k}{n_m}{D}_{kj}^2+\frac{n_l}{n_m}{D}_{lj}^2-\frac{n_k{n}_l}{n_m^2}{D}_{kl}^2\end{array}$$

其中$n_m=n_k+n_l$ 将第三项展开可得

$$\begin{array}{rl}& \frac{2n_k{n}_l}{n_m^2}(X_j-X_k)(X_j-X_l)\\ & =\frac{n_k{n}_l}{n_m^2}(2X_j^2-2X_j{X}_l-2X_k{X}_J+2X_k{X}_l)\\ & =\frac{n_k{n}_l}{n_m^2}[(X_k-X_j{)}^2+(X_l-X_j{)}^2-(X_k-X_l{)}^2]\end{array}$$

由限制$n_m=n_k+n_l$则可知$n_k{n}_l=n_k(n_m-n_k)=n_l(n_m-n_l)$将其分别带入第一项第二项可得原式

6.利用距离平方的递推公式：

$D_{MJ}^2={\alpha }_K{D}_{KJ}^2+{\alpha }_L{D}_{LJ}^2+\beta D_{KL}^2+\gamma \left|D_{KJ}^2-D_{LJ}^2\right|,J\ne K,L.$ 试证明：当$\gamma =0$, ${\alpha }_K⩾0$, ${\alpha }_L⩾0$, ${\alpha }_K+{\alpha }_L+\beta ⩾1$时，系统聚类中的类平均法、可变类平 均法、可变法，以及 Ward 方法的单调性.

由递推关系可知，上一步类内距离最小的为$G_k$和$G_L$ 因此有不等式 $D_{KJ}^2\ge D_{KL}^2$ $D_{LJ}^2\ge D_{KL}^2$ 因此有

$$D_{MJ}^2={\alpha }_K{D}_{KJ}^2+{\alpha }_L{D}_{LJ}^2+\beta D_{KL}^2\ge ({\alpha }_K+{\alpha }_L+\beta )D_{KL}^2$$

由不等式约束${\alpha }_K+{\alpha }_L+\beta ⩾1$ 可知每一步迭代类内距离都在变大，因此有单调递增的性质。

7.试从定义直接证明最长和最短距离法的单调性

最短距离法：

$$\begin{array}{rl}{D}_{MJ}& =\underset{i\in G_M,j\in G_J}{\min }{d}_{ij}=\min \left\{\underset{i\in G_K,j\in G_J}{\min }{d}_{ij},\underset{i\in G_L,j\in G_J}{\min }{d}_{ij}\right\}\\ & =\min \{D_{KJ},D_{LJ}\},J\ne K,L.\end{array}$$

则可知上一步合并的$D_{KL}\le D_{KJ}$,且$D_{KL}\le D_{LJ}$ 则可知$D_{MJ}\ge D_{kl}$单调性得证 最长距离法单调性同理。