西瓜书《机器学习》课后答案——chapter9

9.1 证明：$pgeq 1$时，闵可夫斯基距离满足距离度量的四条基本性质。$0leq p < 1$时，闵可夫斯基距离只满足非负性、规范性和对称性，不满足三角不等式。当p趋向于无穷大时，闵可夫斯基距离等于对应分量的最大绝对距离，也称为切比雪夫距离：

$$lim_{prightarrow +infty}left( sum_{u=1}^n|x_{iu}-x_{ju}|^pright)^{1over p}=max_{u}|x_{iu}-x_{ju}|.$$

解答：

• 当$p>0$时，
  非负性：显然为正。
  规范性：当$x_i=x_j$时，有$(sum_{u=1}^n|x_{iu}-x_{ju}|^p)^{1over p}=0$；当$(sum_{u=1}^n|x_{iu}-x_{ju}|^p)^{1over p}=0$时，假设$x_i neq x_j$，则$(sum_{u=1}^n|x_{iu}-x_{ju}|^p)^{1over p}neq 0$，与条件矛盾，故假设不成立，应有$x_i=x_j$。
  对称性：绝对值不变，故距离不变。显然

闵可夫斯基不等式
当$pgeq 1$时，则有如下不等式成立，称为闵可夫斯基不等式：

$$left( sum_{i=1}^n|a_i+b_i|^pright)^{1over p}leq left( sum_{i=1}^n|a_i|^pright)^{1over p} + left( sum_{i=1}^n|b_i|^pright)^{1over p}.$$
其中 $a_i,b_i$为实数或者复数。

• 当$pgeq 1$时，根据闵可夫斯基不等式，有
  $$begin{align} (sum_{u=1}^n|x_{iu}-x_{ju}|^p)^{1over p}&=(sum_{u=1}^n|x_{iu}-x_{ku}+x_{ku}-x_{ju}|^p)^{1over p} \\ & leq (sum_{u=1}^n|x_{iu}-x_{ku}|^p)^{1over p}+(sum_{u=1}^n|x_{ku}-x_{ju}|^p)^{1over p} end{align},tag{1}$$
  即三角不等式成立。

至于$0leq p < 1$时，怎么证明此不等式不成立就不知道了。

• 切比雪夫距离：
  $$begin{align} lim_{prightarrow +infty}left( sum_{u=1}^n|x_{iu}-x_{ju}|^pright)^{1over p}&=max_{u}|x_{iu}-x_{ju}| lim_{prightarrow +infty}{left( sum_{u=1}^n({|x_{iu}-x_{ju}| over{max_{u}|x_{iu}-x_{ju}|}})^pright)^{1over p}} \\ &=max_{u}|x_{iu}-x_{ju}|. end{align}tag{2}$$
  $({|x_{iu}-x_{ju}| over{max_{u}|x_{iu}-x_{ju}|}})$大于0小于等于1：对于小于1的项，当$prightarrow+infty$时趋向于0，只有为1的项保留下来了，$prightarrow+infty$时还为1。因为只有有限个等于1的项，所以求和可以认为等于一个常数a，且$ageq 1$，则$lim_{prightarrow +infty}a^{1over p}=1$。于是（2）的第二个等式成立。

9.2 同一样本空间中的集合X与Z之间的距离可以通过豪斯多夫距离计算：

$$dist_H(X,Z)=max(dist_h(X,Z), dist_h(Z, X)),$$

其中，

$$dist_h(X,Z)=max_{xin X} min_{zin Z}||x-z||_2.$$

试证明：豪斯多夫距离满足距离度量的四条基本性质。

解答：

非负性：显然。
规范性：
当$X=Z$时，有$dist_h(X,Z)=0$，所以$dist_H(X,Z)=0$.
当$dist_H(X,Z)=0$时，表明$dist_h(X,Z)$和$dist_h(Z,H)$中最大的那个为0，又因为不可能为负，所以两个只能都为0。而$dist_h(X,Z)=0$意味着X中的任一点到Z的距离为0，这表示X中的任一点都必须属于Z，也就是说$X subset Z$。同样，由$dist_h(Z,H)=0$可以知道$Z subset X$。于是有$X=Z$。
对称性：显然。
三角不等式：

$$begin{align} dist_h(x, Z)&=min_{zin Z}||x-z||_2 \\ &=min_{zin Z}||x-y+y-z||_2 ,forall y in Y\\ &leq min_{zin Z}(||x-y||_2 + ||y-z||_2),forall y in Y\\ &= ||x-y||_2 +min_{zin Z}||y-z||_2,forall y in Y\\ &leq ||x-y||_2 +max_y min_{zin Z}||y-z||_2 , forall y in Y \\ &= ||x-y||_2 +dist_h(Y, Z),forall y in Y\\ end{align}$$

对不等式右边求$min_y$，有

$$dist_h(x, Z) leq min_y ||x-y||_2 +dist_h(Y, Z) , forall x in X$$

对不等式右边求$max_x$，有

$$dist_h(x, Z) leq dist_h(X,Y) +dist_h(Y, Z) , forall x in X$$

对不等式左边求$max_x$，有

$$dist_h(X, Z) leq dist_h(X,Y) +dist_h(Y, Z)$$

参考：http://www.math.harvard.edu/library/sternberg/slides/1180910.pdf

9.3 分析k均值算法能否找到最小化(9.24)的最优解。
解答：
k均值算法是用迭代的方法求解优化问题(9.24)的，每次迭代分为两步：计算簇中心；根据样本到簇中心的距离重新聚类。两个步骤都可以使得代价函数降低（至于为什么，可以阅读PRML p.425），又因为代价函数是有界的（聚类方法是有限的），所以不断迭代之后，最终一定能收敛，但不一定收敛到全局最小。而且收敛结果是对初值敏感的，不同的初值得到的聚类结果可能有很大差别。

上面只是简单的叙述，至于能不能严格证明：k均值算法不一定收敛到最优解，就不得而知了。目前只听说过证明收敛性的。

9.4 编程实现k均值算法，设置三组不同的k值、三组不同初始中心点，在西瓜数据集4.0上进行实验比较，并讨论什么样的初始中心有助于得到好结果。
解答：西瓜书《机器学习》课后答案——chapter9 _9.4

9.5 基于DBSCAN的概念定义，若x为核心对象，由x密度可达的所有样本构成的集合为X，试证明：X满足连接性和最大性。
解答：
连接性：对$forall x_i in X, forall x_j in X$，有$x_i$和$x_j$密度相连。
$x_i in X$，$x_j in X$分别表示$x_i$由$x$密度可达，$x_j$由$x$密度可达，于是由密度相连的定义可以知道$x_i$和$x_j$密度相连。

最大性：对$forall x_i in X$，$x_j$由$x_i$密度可达，则$x_jin C$。
因为$x_i in X$，所以$x_i$由$x$密度可达，又因为$x_j$由$x_i$密度可达，所以$x_j$由$x$密度可达，于是$x_jin C$。

9.6 试析AGNES算法使用最小距离和最大距离的区别。
解答：
当两个类簇比较大且距离比较远，但是有两个点距离对方比较近时，那么单链接算法会把这两个类簇合并，导致产生拉长的类簇而不是一般情况下的圆形类簇，这被称为链式效应。因为这个算法经常由于链式效应而把不相似的对象放到同一类簇中，所以是空间压缩的(space contracting)。
当两个类簇中至少有一对比较远离的对象时，全链接算法会最后合并这两个类簇，于是相似对象会长时间待在不同类簇中，这被称为分离效果(dissection effect)。所以，全链接算法是空间扩张的(space dilating)。

参考：Finding Groups in Data: An Introduction to Cluster Analysis. L Kaufman ， PJ Rousseeuw. 1990. p.225.

9.7 聚类结果中若每个簇都有一个凸包（包含簇样本的凸多面体），且这些凸包不相交，则称为凸聚类。试析本章介绍的哪些聚类算法只能产生凸聚类，哪些能产生非凸聚类。
解答：
k-means算法是凸聚类算法，生成的类簇有凸包包围并且凸包互不相交；
DBSCAN算法是非凸聚类算法；

9.8 试设计一个聚类性能度量指标，并与9.2中的指标比较。

9.9 设计一个能用于混合属性的非度量距离。
用于相似性度量的距离不一定要满足距离的定义，这样的距离称非度量距离。

9.10 设计一个能自动确定聚类数的改进k均值算法，编程实现并在西瓜数据集4.0上运行。

最后

以上就是英勇蚂蚁最近收集整理的关于西瓜书《机器学习》课后答案——chapter9的全部内容，更多相关西瓜书《机器学习》课后答案——chapter9内容请搜索靠谱客的其他文章。