习题提示

9.1：
（1）闵可夫斯基距离满足相关性质，参见7、有趣的距离与范数的第一部分。

（2）极限

$$\begin{array}{rl}{\left[\sum _{u=1}^n|x_{iu}-x_{ju}{|}^p\right]}^{\frac{1}{p}}& ⩽{\left[\sum _{u=1}^n\underset{u}{\max }|x_{iu}-x_{ju}{|}^p\right]}^{\frac{1}{p}}\\ & =n^{\frac{1}{p}}\underset{u}{\max }|x_{iu}-x_{ju}|\\ & \to \underset{u}{\max }|x_{iu}-x_{ju}|,(whenp\to +\infty )\end{array}\text{\hspace{1em}(1)}$$
又
$$\begin{array}{rlr}{\left[\sum _{u=1}^n|x_{iu}-x_{ju}{|}^p\right]}^{\frac{1}{p}}& ={\left[(\underset{u}{\max }|x_{iu}-x_{ju}|{)}^p+\sum _{otheru}|x_{iu}-x_{ju}{|}^p\right]}^{\frac{1}{p}}& ⩾\underset{u}{\max }|x_{iu}-x_{ju}|\end{array}\text{\hspace{1em}(2)}$$

由式(1)(2)及两边夹法则，即得极限式。

9.2：
豪斯多夫距离满足距离的“四性”要求，参见7、有趣的距离与范数的第二部分。

9.3：
不能。 已证明它是NP难问题。

【西瓜书(9.24)】要求全局找最优解，而k均值算法是迭代的方法，每次只调整局部（将样本纳入最近的均值向量所在的簇），这种动态的调整方法只是最优解的近似。

9.4：
编程实现k均值算法【西瓜书图9.2】。 初始中心越分散（相互间距离大）越好。

9.5：
$X$由$\mathbf{x}$所生成（密度可达），故：

（1）若${\mathbf{x}}_i\in X,{\mathbf{x}}_j\in X$，则${\mathbf{x}}_i$与${\mathbf{x}}_j$均由$\mathbf{x}$密度可达，故${\mathbf{x}}_i$与${\mathbf{x}}_j$密度相连，连接性得证。

（2）若${\mathbf{x}}_i\in X$，则${\mathbf{x}}_i$由$\mathbf{x}$密度可达，又假设${\mathbf{x}}_j$由${\mathbf{x}}_i$密度可达，则从$\mathbf{x}$先到达${\mathbf{x}}_i$，再由${\mathbf{x}}_i$到达${\mathbf{x}}_j$，即${\mathbf{x}}_j$由$\mathbf{x}$密度可达，故${\mathbf{x}}_j\in X$，最大性得证。

9.6：
参见9.5 密度聚类与层次聚类（DBSCAN算法、AGNES算法）中“图9.2 簇间距离”的讨论。

9.7：
（1）k均值算法，${\mu }_i$收罗以它为圆心的某个圆内的所有点（样本），这种簇中局部的凸不一定导致簇中全局的凸，故它可能产生非凸聚类。

（2）学习向量量化算法学习出原型向量$({\mathbf{p}}_1,{\mathbf{p}}_2,\cdots ,{\mathbf{p}}_q)$，再通过该向量组对样本空间进行划分，${\mathbf{p}}_i$与${\mathbf{p}}_j$的剖分线实际为${\mathbf{p}}_i$与${\mathbf{p}}_j$的中垂线，任意三点的两两的中垂线必交于一个点（几何性质），即剖分形成凸形，故LVQ只能产生凸聚类。

（3）高斯混合聚类算法是依赖于分布，而不是依赖于几何性质，故它可能产生非凸聚类。

（4）密度聚类算法（DBSCAN），与k均值算法类似，簇中局部的凸不一定导致全局的凸，故它可能产生非凸聚类，如，可达的折线形成的簇。

（5）AGNES算法：以“最大距离”作为簇间距离时，只能产生凸聚类。 以“最小距离”作为簇间距离时，可能产生非凸聚类。

9.8：
这是一个开放性题目，【西瓜书第9.2节】的指标涉及到计数的比值和距离的比值。

9.9：
这是一个开放性题目，非度量距离通常不满足直递性，而混合属性说明属性中含有无序属性，【西瓜书(9.21)】式是个不错的处理无序属性的方法，而【西瓜书(9.22)】式将【西瓜书(9.21)】式含在里面来定义混合属性距离。 题目放宽对距离的要求（非度量），则可以考虑将前述思路反过来，即距离定义式中的外层为VDM【西瓜书(9.21)】，里层再包含其它距离。

9.10：
这是一个研究性质的题目，将k的增长视为树的生长，再在上面定义评估分数（如，BIC），结合运行的计分，则得到最优的聚类数k以及划分的簇。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：周志华西瓜书《机器学习》习题提示——第8章
下一篇：10.1 k近邻算法（你是住在穷人区还是富人区？）