[人工智能]《机器学习》慕课版课后习题-第4章

中国工信出版集团、人民邮电出版社出版的赵卫东、董亮编著的《机器学习》慕课版

第4章 聚类分析

1.聚类分析的目的是什么？

解：聚类分析用于对未知类别的样本进行划分，将它们按照一定的规则划分成若干个类簇，把相似(距高相近)的样本聚在一个类簇中，把不相似的样本分为不同类簇，从而揭示样本之间内在的性质以及相互之间的联系规律。

2.讨论聚类与分类的关系。

解：聚类算法将未标记的样本自动划分为多个类簇，但不会提供对每个类簇的语义解释，这部分解释就需要数据分析人员对聚类结果进行归纳总结，阐述聚类的意义。

3.聚类分析常用的应用领域有哪些？

解：金融保险、生物学、医学、军事、地理、电子商务等领域都有重要用途。

4.常见的聚类有哪些方法？这些方法分别适用于什么场合？

解：基于划分的聚类，多适用于中等体量的数据集，数据集越大，越有可能陷入局部最小。

基于层次的聚类有自顶向下和自底向上两种，实际使用中根据数据特点及目标“聚类”结果个数来使用哪一种。

基于密度的聚类对噪声数据的处理比较好，但不适合对参数设置非常敏感的场合。

基于网格的聚类适用于需要执行效率高，而对参数不敏感、无不规则分布的数据等场合。

基于模型的聚类适用于数据的“类”不那么确定，而表现为概率形式的场合。

5.评价聚类算法的好坏可以从哪些方面入手？

解：良好的可伸缩性、处理不同类型数据的能力、处理噪声数据的能力、对样本顺序的不敏感性、约束条件下的表现、易解释性和易用性。

具体评价指标包括外部指标如Rand统计量、F值、Jaccard指数、FM指数等；内部指标如欧式距离、曼哈顿距离、切比雪夫距离、明可夫斯基距离、紧密度、分隔度、戴维森堡丁指数、邓恩指数等。

6.在聚类分析中，样本之间的距离常用的计算方法有哪些？

解：常用的距离度量有欧式距离、曼哈顿距离、切比雪夫距离和明可夫斯基距离等。

7.简要说明基于划分的聚类方法的基本原理。

解：基于划分的方法通过将对象划分为互斥的簇进行聚类，每个样本属于且仅属于一个簇。划分结果旨在使簇之间的相似性低，簇内部的相似度高。

8.k-均值算法的聚类数k如何确定？

解：第一种方法：与层次聚类算法结合，先通过层次聚类算法得出大致的聚类数目，并且获得一个初始聚类结果，然后再通过k-均值算法改进聚类结果。

第二种方法：基于系统演化的方法，将数据集视为伪热力学系统，在分裂和合并过程中，将系统演化到稳定平衡状态从而确定k值。

9.讨论初始的k个假设聚类中心位置对k-均值算法的影响。

解：k-means算法对初始化聚类中心依赖性比较大，很可能陷入局部最优的情况或使得迭代次数增加。

10.举例讨论k-均值算法的应用。

解：如对Iris数据集进行聚类、帮助危险品运输企业进行风险管控、防范等。

11.k-medoids算法和k-prototype算法对k-均值算法做了哪些改进？

解：k-medoids算法不通过计算簇中所有样本的平均值得到簇的中心，而是通过选取原有样本中的样本点作为代表对象代表这个簇，计算剩下的样本点与代表对象的距离，将样本点划分到与其距离最近的代表对象所在的簇中。

k-prototype算法综合了k-均值和k-总数算法，采用新的距离度量算法，加入描述数据簇的原型和混合数据之间的相异度计算公式，能够快速处理混和类型数据集的聚类问题。

12.简述CLARANS算法的思想。

解：CLARANS算法即随机搜索聚类算法，是一种分割聚类算法。它首先随机选择一个点作为当前点，然后随机检查它周围不超过参数Maxneighbor个的一些邻接点，假如找到一个比它更好的邻接点，则把它移入该邻接点，否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量，直至所找到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须都预先调入内存，并且需多次扫描数据集，这对于大数据量而言，无论时间复杂度还是空间复杂度都相当大。虽通过引入R-树结构对其性能进行改善，使之能够处理基于磁盘的大型数据库，但R*-树的构造和维护代价太大。该算法对脏数据和异常数据不敏感，但对数据进入顺序异常敏感，且只能处理凸形或球形边界聚类。

13.讨论DBSCAN算法的几个参数如何选择。

解：Eps的值可以使用绘制k-距离曲线方法得当，在k-距离曲线图明显拐点位置为对应较好的参数。若参数设置过小，大部分数据不能聚类；若参数设置过大，多个簇和大部分对象会归并到同一个簇中。

MinPts的选取有一个指导性的原则，MintPts≥dim+1，其中dim表示待聚类数据的维度。MinPts设置为1是不合理的，因为设置为1，则每个独立点都是一个簇，MinPts≤2时，与层次距离最近邻域结果相同，因此，MinPts必须选择大于等于3的值。若该值选取过小，则稀疏簇中结果由于密度小于MinPts，从而被认为是边界点而不被用于在类的进一步扩展；若该值过大，则密度较大的两个邻近簇可能被合并为同一簇。因此，该值是否设置适当会对聚类结果造成较大影响。

14.举例说明DBSCAN算法的应用。

解：对于城市管理部门而言，尽早发现城市异常事件是重中之重。以往的做法是，城市管理部门部署复杂的基于视频的特定基础设施，并且多数情况下由人员监控。然而，随着基于位置的社交网络(LSBN)的出现和迅速普及，在特定时间检测特定区域中异常高或异常低的市民数量可以通过专家系统来完成，系统能够自动分析带有公共地理位置标签的帖子。这样的解决方案意味着不需要特定的基础设施，因为市民的移动设备由他们自身携带和维护，并在社交网络上主动共享地理位置。此外，位置分析比视频分析更容易，可以自动完成。

本例采用基于密度的聚类，发现所有已知的城市异常事件，还能在实验过程中发现其他未知事件。使用纽约市Instagram获得的带地理标记帖子的数据集验证了近6个月的数据，取得了良好的效果。

15.简述OPTICS算法的原理以及适用场合。

解：OPTICS算法生成一个增广的簇排序，即所有分析对象的线性表，代表各样本点基于密度聚类结构。从线性表的排序中可以得到基于任何领域参数的DBSCAN算法的聚类结果。OPTICS算法适用于数据样本点不均匀或聚类间相差很大，以及对领域参数非常敏感时。

16.简述基于层次聚类的思想。

解：层次聚类的核心思想就是通过对数据集按照层次，把数据划分到不同层的簇，从而形成一个树形的聚类结构。层次聚类算法可以揭示数据的分层结构，在树形结构上不同层次进行划分，可以得到不同粒度的聚类结果。

17.常见的层次聚类算法有哪些？分别阐述其思想。

解：BIRCH算法的核心就是构建一个聚类特征树(Clustering Feature Tree，CF-Tree)，聚类特征树的每一个节点都是由若干个聚类特征(CF)组成的。具体言之，BIRCH算法利用树结构对数据集进行处理，叶节点存储一个聚类，用中心和半径表示，顺序处理每一个对象，并把它划分到距离最近的结点，该算法也可以作为其他聚类算法的预处理过程。

CURE算法采用抽样技术先对数据集D随机抽取样本，再采用分区技术对样本进行分区，然后对每个分区局部聚类，最后对局部聚类进行全局聚类。

ROCK算法也采用了随机抽样技术，该算法在计算两个对象的相似度时，同时考虑了周围对象的影响。

CHEMALOEN(变色龙算法)算法首先由数据集构造成一个K-最近邻图Gk，再通过一个图的划分算法将图Gk划分成大量的子图，每个子图代表一个初始子簇，最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇。

SBAC算法则在计算对象间相似度时，考虑了属性特征对于对象本质的重要程度，对于更能体现对象本质的属性赋予较高的权值。

18.凝聚型层次聚类算法有何优点？结合案例讨论其应用。

解：凝聚的层次聚类并没有类似基本K均值的全局目标函数，没有局部极小问题或是很难选择初始点的问题。合并的操作往往是最终的，一旦合并两个簇之后就不会撤销。当然计算存储的代价是昂贵的。

根据“评估——教育——再评估”的循环过程，设计了一个循环的ESL教学推荐系统，其基本概念是系统为学生精心设计语法测试，对学生完成情况自动分析结果，并在发现学生弱点的地方提出改进学生学习能力的建议。然后，改善自己的弱点之后，学生进行另一个类似的测试，系统重新进行分析和推荐过程。

对于每个学生，系统创建一个正确/错误答案统计表，然后将每个学生的错误答案统计表汇总成学生错误答案汇总表。然后按照层次聚类算法应用于学生错误答案汇总表的数据，将学生划分为一定数量的聚类或类别，每个类别包括共享相似犯错特征的学生。根据这些信息，老师将能够更好地帮助学生。

19.讨论自组织映射网络Kohonen聚类算法的基本思想，并举例说明其应用。

解：Kohonen聚类算法的基本思想是基于赢者通吃法则(也称为竞争学习)，使获胜神经元对其邻近神经元的影响是由近及远，对附近神经元产生兴奋影响逐渐变为抑制。通过自动寻找样本中的内在规律和本质属性，自组织、自适应地改变网络参数与结构。

生物评估计划中使用的分类不足以捕捉地中海溪流的临时变化。可能导致对水质生物学指标的不准确评估和设定参考条件的困难。该案例检查水生无脊椎动物增加的分类学解决方案，数据收集于葡萄牙南部的Quarteira河流域的74个地点的无脊椎动物样本。使用SOM的分类结果有五类，驱动这种分类的变量主要是海拔高度、温度、电导率，还有底层类型、河岸边界和边缘比例。

SOM允许虚拟无脊椎动物样本(以及相应的输出神经元)以灰度梯度的形式显现每个分类群的出现。由于SOM没有提供任何有关无脊椎动物群类群协会的统计验证SOM地区(以及相应的环境条件)，由此将指示物种分析(ISA)应用于二元变量。ISA是基于保真度表示的关联系数，它是根据2*2列联表和每个SOM子集群的无脊椎动物样本计算出来的，并对不同大小的SOM子集进行校正。系数范围从-1(完美负向指示)到1(完美正向指示)。正值表明分类群的出现集中在一个给定的SOM亚群无脊椎动物样本中，而负值表明在给定的SOM亚群无脊椎动物样本中，分类群的出现率不足。

20.举例讨论聚类算法与其他算法的组合应用。

解：需求预测在零售业的易腐商品和新鲜商品的供应链领域具有特别的重要性。这些商品是每日生产和运输的，它们需要尽可能新鲜，否则很快就会变质。需求的高估和低估都会对零售商利润产生不良影响，缺货对消费者有不利影响，而未售出的商品需要在一天结束时扔掉。通过根据最新的销售点数据在不同的的组织级别提供分层预测来支持日常运营，基于日内销售模式来识别用于拓展层次结构的商品聚集。应用多元ARIMA模型来预测日常需求以支持运营决策并用一个工业化的面包连锁店的销售点数据来评估，目的是降低食品销售企业销售的易腐商品的丢弃成本并且通过一系列的预测方法，包括自顶向下、自底向上、层级预测等方法，提高食品的利用率，也就是让这些食品尽可能地卖出去，减少滞留。

易腐商品是快速消费商品的一种，这种商品的特点是每日生产并运送，而且保质期非常短。

供应链的表现基于需求预测的精准性。同时在供应链领域要注意牛鞭效应的影响，这个效应是指需求的波动会导致上游供应链出现库存积压或者缺货的现象。通过构建及使用一个特定领域的层次结构来预测可替代易腐商品的需求。定义的结构由几个字母组成，其中包括了区域?、店铺(S)、商品目录?、特定商品(A)及商品组(X)。决策支持系统就是要通过提供不同组织层级的是日常商品需求预测来最优化日常的操作。短期的预测(三天)往往是高效的。为了创建一种层次结构，将具有相似销售模式的商品进行聚类。ARIMA(X)模型用于预测从销售点数据中汇总到期望水平的时序。