发布时间 : 星期日 文章习题及参考答案更新完毕开始阅读1796390079563c1ec5da713d
(b)如图，
4.3 聚类被广泛地认为是一种重要的数据挖掘方法，有着广泛的应用。对如下的每种情况给
出一个应用例子：
(a) 采用聚类作为主要的数据挖掘方法的应用；
(b) 采用聚类作为预处理工具，为其它数据挖掘任务作数据准备的应用。
答：(a) 如电子商务网站中的客户群划分。根据客户的个人信息、消费习惯、浏览行为等信
息，计算客户之间的相似度，然后采用合适的聚类算法对所有客户进行类划分；基于得到的客户群信息，相关的店主可以制定相应的营销策略，如交叉销售，根据某个客户群中的其中一个客户的购买商品推荐给另外一个未曾购买此商品的客户。 (b) 如电子商务网站中的推荐系统。电子商务网站可以根据得到的客户群，采用关联规则或者隐马尔科夫模型对每个客户群生成消费习惯规则，检测客户的消费模式，这些规则或模式可以用于商品推荐。其中客户群可以通过聚类算法来预先处理获取得到。
第 17 页 共 27 页
4.4 假设你将在一个给定的区域分配一些自动取款机以满足需求。住宅区或工作区可以被聚
类以便每个簇被分配一个ATM。但是，这个聚类可能被一些因素所约束，包括可能影
响ATM 可达性的桥梁，河流和公路的位置。其它的约束可能包括对形成一个区域的每个地域的ATM 数目的限制。给定这些约束，怎样修改聚类算法来实现基于约束的聚类？ 答：约束的存在会使得原来被定义在同一个簇的对象之间的距离发生变化。这时可以考虑将
这些约束因素融入到距离的计算公式中，如在存在桥梁、河流和公路的区域中，可通过对象之间的连通性以及路径来计算距离；而地域ATM数目的限制问题则可在聚类的初始化阶段解决，如在K-MEANS的初始化时，可根据区域的个数来确定簇个数K的值，然后所选择的初始化种子尽可能分布在距离各个ATM附近的地方。
4.5 给出一个数据集的例子，它包含三个自然簇。对于该数据集，k-means(几乎总是)能够发现正确的簇，但二分k-means不能。
答：有三个完全一样的球型簇，三个簇的点的个数和分布密度以及位置均完全相同。其中两
个簇关于第三个簇完全对称，则在k-means方法中可以很轻易找出这三个簇，但用二分k-means则会把处于对称中心的那个簇分成两半。
4.6 总SSE是每个属性的SSE之和。如果对于所有的簇，某变量的SSE都很低，这意味什么？如果只对一个簇很低呢？如果对所有的簇都很高？如果仅对一个簇高呢？如何使用每个变量的SSE信息改进聚类？ 答：
(a) 如果对于所有的簇，某属性的SSE都很低，那么该属性值变化不大，本质上等于
常量，对数据的分组没什么用处。
(b) 如果某属性的SSE只对一个簇很低，那么该属性有助于该簇的定义。 (c) 如果对于所有的簇，某属性的SSE都很高，那么意味着该属性是噪声属性。 (d) 如果某属性的SSE仅对一个簇很高，那么该属性与定义该簇的属性提供的信息不
一致。在少数情况下，由该属性定义的簇不同于由其他属性定义的簇，但是在某些情况下，这也意味着该属性不利于簇的定义。 (e) 消除簇之间具有小分辨力的属性，比如对于所有簇都是低或高SSE的属性，因为
他们对聚类没有帮助。对于所有簇的SSE都高且相对其他属性来说SSE也很高的属性特别麻烦，因为这些属性在SSE的总和计算中引入了很多的噪声。
4.7 使用基于中心、邻近性和密度的方法，识别图4-19中的簇。对于每种情况指出簇个数，
并简要给出你的理由。注意，明暗度或点数指明密度。如果有帮助的话，假定基于中心
即K均值，基于邻近性即单链，而基于密度为DBSCAN。
第 18 页 共 27 页
图4-19 题4.7图
答：
(a) 基于中心的方法有2个簇。矩形区域被分成两半，同时2个簇里都包含了噪声数据；
基于邻近性的方法有1个簇。因为两个圆圈区域受噪声数据影响而形成一个簇； 基于密度的方法有2个簇，每个圆圈区域代表一个簇，而噪声数据会被忽略。
(b) 基于中心的方法有1个簇，该簇包含图中的一个圆环和一个圆盘；
基于邻近性的方法有2个簇，外部圆环代表一个簇，内层圆盘代表一个簇； 基于密度的方法有2个簇，外部圆环代表一个簇，内层圆盘代表一个簇。
(c) 基于中心的方法有3个簇，每个三角形代表一个簇；
基于邻近性的方法有1个簇，三个三角形区域会联合起来因为彼此相互接触；
基于密度的方法有3个簇，每个三角形区域代表一个簇。即使三个三角形相互接触，但是所接触的区域的密度比三角形内的密度小。
(d) 基于中心的方法有2个簇。两组线被分到两个簇里；
基于邻近性的方法有5个簇。相互缠绕的线被分到一个簇中；
基于密度的方法有2个簇。这两组线定义了被低密度区域所分割的两个高密度的
区域。
4.8 传统的凝聚层次聚类过程每步合并两个簇。这样的方法能够正确地捕获数据点集的(嵌
套的)簇结构吗？如果不能，解释如何对结果进行后处理，以得到簇结构更正确的视图。 答:传统的凝聚层次聚类过程关键是每步合并两个最相似的簇，直至只剩下一个簇才停止聚
类。该聚类方法并不能产生嵌套的簇结构。但我们可以采用树结构的方法来捕捉形成的
层次结构，每次合并都记录父子簇之间的关系，最后形成一个清晰的树状层次簇结构。
4.9 我们可以将一个数据集表示成对象节点的集合和属性节点的集合，其中每个对象与每个
属性之间有一条边，该边的权值是对象在该属性上的值。对于稀疏数据，如果权值为0，则忽略该边。双划分聚类(Bipartite)试图将该图划分成不相交的簇，其中每个簇由一个对
象节点集和一个属性节点集组成。目标是最大化簇中对象节点和属性节点之间的边的权值，并且最小化不同簇的对象节点和属性节点之间的边的权值。这种聚类称作协同聚类(co-clustering)，因为对象和属性之间同时聚类。
(a) 双划分聚类(协同聚类)与对象和属性集分别聚类有何不同？ (b) 是否存在某些情况，这些方法产生相同的结果？ (c) 与一般聚类相比，协同聚类的优点和缺点是什么？ 答:
(a) 对于普通聚类，只有一组约束条件被运用，要么与对象相关，要么与属性相关。对于协
同聚类，两组约束条件同时被运用。因此，单独地划分对象和属性无法产生相同的结果。
(b) 是的。例如，如果一组属性只与一个特定的簇对象相关，如在所有其他簇中的对象权值
为0；相反地，这组对象在一个簇中对所有其他属性的权值为0，那么由协同聚类发现的簇会与分别通过对象和属性聚类的结果一样。以文本聚类作为例子，有一组文本组成的簇仅包含了某部分的词或短语，相反地，某些词或短语也仅出现在部分文本里。
(c) 协同聚类的优点是能自动产生由属性描述的簇，这种描述信息带有更强的表达能力，在
第 19 页 共 27 页
现实应用中，较由对象描述的簇更有用(如在客户细分中，有属性描述的簇能为营销战略决策提供更为直接的辅助作用)。但具有强区分能力的属性有时候出现严重的重叠现象，这种情况下协同聚类产生的结果并不理想，如出现重叠率很高的聚类结果。
4.10 下表中列出了4个点的两个最近邻。使用SNN相似度定义，计算每对点之间的SNN
相似度。
点 1 2 3 4 第一个近邻 4 3 4 3 第二个近邻 3 4 2 1 答：SNN即共享最近邻个数为其相似度。 点1和点2的SNN相似度：0（没有共享最近邻）
点1和点3的SNN相似度：1（共享点4这个最近邻） 点1和点4的SNN相似度：1（共享点3这个最近邻） 点2和点3的SNN相似度：1（共享点4这个最近邻） 点2和点4的SNN相似度：1（共享点3这个最近邻） 点3和点4的SNN相似度：0（没有共享最近邻）
4.11对于SNN相似度定义，SNN距离的计算没有考虑两个最近邻表中共享近邻的位置。换
言之，可能希望基于以相同或粗略相同的次序共享最近邻的两个点以更高的相似度。 (a) 描述如何修改SNN相似度定义，基于以粗略相同的次序共享近邻的两个点以更高
的相似度；
(b) 讨论这种修改的优点和缺点。 答：(a)
i) 把两个最近邻表中共享近邻按照距离从小达大排列，然后以一个最近邻表为基准，调
整另一个最近邻表中近邻的位置，总共调整步数为r，其中共享的最近邻个数为n，则相似度可以简单定义为
nr??或log?????r???n，其中?为平滑参数，可以简单设置为??1。
ii) 找出两个最近邻表中的最长子序列，最长子序列长度为L, 共享的最近邻个数为N，则相似度为N?L。
(b) 以上相似度计算方法更好地体现了共享近邻在最近邻表中位置的因素对相似度评价的影响，增大了略同次序共享近邻的相似度；缺点是计算复杂度增大。
4.12一种稀疏化邻近度矩阵的方法如下：对于每个对象，除对应于对象的k-最近邻的项之外，所有的项都设置为0。然而，稀疏化之后的邻近度矩阵一般是不对称的。
(a) 如果对象a在对象b的k-最近邻中，为什么不能保证b在对象a的k-最近邻中？ (b) 至少建议两种方法，可以用来使稀疏化的矩阵是对称的。
答：(a) 可能出现对象a的密度较大而对象b的密度小的情况。另一种典型情况是：在一个
只包含k+1个正常对象和一个异常对象的数据区域中，异常对象b的k个最近邻为k+1个正常对象中距离其最近的k个对象，但正常对象a的k个最近邻不可能包含异常对象（这是因为异常对象b本来就是距离正常对象最远的点，因此，它与正常对象a的距离会大于任何其它正常对象与a之间的距离） (b)
第 20 页 共 27 页