多元第十二章习题

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.给出式子详细推导过程

D_{MJ}^2& =(\overline{x}^{(M)}-\overline{x}^{(J)})^{\prime}(\overline{x}^{(M)}-\overline{x}^{(J)}) \\ &\text{=} =\left[\frac{n_{K}}{n_{M}}(\overline{\boldsymbol{x}}^{(J)}-\overline{\boldsymbol{x}}^{(K)})+\frac{n_{L}}{n_{M}}(\overline{\boldsymbol{x}}^{(J)}-\overline{\boldsymbol{x}}^{(L)})\right]^{\prime} \\ &\times\left[\frac{n_K}{n_M}(\overline{\boldsymbol{x}}^{(J)}-\overline{\boldsymbol{x}}^{(K)})+\frac{n_L}{n_M}(\overline{\boldsymbol{x}}^{(J)}-\overline{\boldsymbol{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},\quad J\neq K,L. \end{aligned}$$ 下面用简略符号代替证明：(由于转置完都是一个数所以简略写不再加入转置)

\begin{aligned} &(\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{aligned}

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

\begin{aligned} &\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_kX_J+2X_kX_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{aligned}

由限制$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|,\quad J\neq K,L.$$ 试证明：当$\gamma = 0$, $\alpha _K\geqslant 0$, $\alpha _L\geqslant 0$, $\alpha _K+ \alpha _L+ \beta \geqslant 1$时，系统聚类中的类平均法、可变类平 均法、可变法，以及 Ward 方法的单调性. 由递推关系可知，上一步类内距离最小的为$G_{k}$和$G_{L}$ 因此有不等式 $D_{KJ}^{2}\geq D_{KL}^{2}$ $D_{LJ}^{2}\geq D_{KL}^{2}$ 因此有 $$D_{MJ}^{2}=\alpha_{K}D_{KJ}^{2}+\alpha_{L}D_{LJ}^{2}+\beta D_{KL}^{2}\geq(\alpha_{K}+\alpha_L+\beta)D^{2}_{KL}

由不等式约束${\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}$单调性得证 最长距离法单调性同理。