5 94 90 8460 8836 86. 6983 6 86 75 6450 7396 82. 0455 7 59 49 2891 3481 66. 3423 8 83 79 6557 6889 80. 3007 9 65 77 5005 4225 69. 8319 10 33 52 1716 1089 51. 2207 11 88 74 6512 7744 83. 2087 12 81 90 7290 6561 79. 1375 SUM 866 888 66088 65942
第 16 页 共 27 页 答：令 β
x w= ，对样本数据做变换 ) ,...., 2 , 1 ( n i x w i i = = β
，利用 (w i ， Y i )(i=1 ， 2 ，?， n) 解出 y = aw 中的 a ，再代入 β
ax y = 即得到 y 对 x 的回归方程。 第 第 4 章聚类分析
4.1 什么是聚类？简单描述如下的聚类方法：划分方法，层次方法，基于密度的方法，基于
模型的方法。为每类方法给出例子。 答：聚类是将数据划分为相似对象组的过程，使得同一组中对象相似度最大而不同组中对象 相似度最小。主要有以下几种类型方法： (1) 划分方法
给定一个有 N 个元组或者记录的数据集，分裂法将构造 K 个分组，每一个分组就
代表一个聚类， K 使用这个基本思想的算法有： K-MEANS 算法、 K-MEDOIDS 算法、 CLARANS 算法。 (2) 层次方法 这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可 分为 “ 自底向上 ” 和 “ 自顶向下 ” 两种方案。例如在 “ 自底向上 ” 方案中，初始时每一个数 据记录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个 组，直到所有的记录组成一个分组或者某个条件满足为止。 代表算法有： BIRCH 算法、 CURE 算法、 CHAMELEON 算法等。 (3) 基于密度的方法 基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离，而 是基于密度的。这样就能克服基于距离的算法只能发现 “ 类圆形 ” 的聚类的缺点。这个 方法的指导思想就是：只要一个区域中的点的密度大过某个阈值，就把它加到与之相 近的聚类中去。 代表算法有： DBSCAN 算法、 OPTICS 算法、 DENCLUE 算法等。 (4) 基于模型的方法 基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模 型的数据。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个 潜在假定就是：目标数据集是由一系列的概率分布所决定的。 基于模型的方法主要有两类：统计学方法和神经网络方法 (SOM) 。 4.2 假设数据挖掘的任务是将如下的 8 个点 ( 用 (x,y) 代表位置 ) 聚类为三个簇。 A1(2,10),A2(2,5),A3(8,4),B1(5,8),B2(7,5),B3(6,4),C1(1,2),C2(4,9) 。距离函数是 Euclidean 函数。假设初始我们选择 A1,B1 和 C1 为每个簇的中心，用 k-means 算法来给出 (a) 在第一次循环执行后的三个簇中心； (b) 最后的三个簇中心及簇包含的对象。 答： (a) 如图， 第 17 页 共 27 页 (b) 如图， 4.3 聚类被广泛地认为是一种重要的数据挖掘方法，有着广泛的应用。对如下的每种情况给 出一个应用例子： (a) 采用聚类作为主要的数据挖掘方法的应用； (b) 采用聚类作为预处理工具，为其它数据挖掘任务作数据准备的应用。 答： (a) 如电子商务网站中的客户群划分。根据客户的个人信息、消费习惯、浏览行为等信 息，计算客户之间的相似度，然后采用合适的聚类算法对所有客户进行类划分；基 于得到的客户群信息，相关的店主可以制定相应的营销策略，如交叉销售，根据某 个客户群中的其中一个客户的购买商品推荐给另外一个未曾购买此商品的客户。 (b) 如电子商务网站中的推荐系统。电子商务网站可以根据得到的客户群，采用关联规 则或者隐马尔科夫模型对每个客户群生成消费习惯规则，检测客户的消费模式，这 些规则或模式可以用于商品推荐。其中客户群可以通过聚类算法来预先处理获取得 到。 第 18 页 共 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 。 第 19 页 共 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) 协同聚类的优点是能自动产生由属性描述的簇，这种描述信息带有更强的表达能力，在 第 20 页 共 27 页 现实应用中，较由对象描述的簇更有用 ( 如在客户细分中，有属性描述的簇能为营销战 略决策提供更为直接的辅助作用 ) 。但具有强区分能力的属性有时候出现严重的重叠现 象，这种情况下协同聚类产生的结果并不理想，如出现重叠率很高的聚类结果。 4.10 下表中列出了 4 个点的两个最近邻。使用 SNN 相似度定义，计算每对点之间的 SNN 相似度。 点 第一个近邻 第二个近邻 1 4 3 2 3 4 3 4 2 4 3 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 ，则 相似度可以简单定义为 ε + r n 或 + ε r n log ，其中 ε 为平滑参数，可以简单设置为 1 = ε 。 ii) 找出两个最近邻表中的最长子序列，最长子序列长度为 L, 共享的最近邻个数为 N ， 则相似度为 L N × 。 (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) 第 21 页 共 27 页 i) 在两个对象 a 和 b 中，只要其中一个对象在另一个对象的最近另列表中，我们就设 置 M ba = M ab = 1 （ M ab 是指邻近度矩阵中 a 行和 b 列交叉项的值）； ii) 当某个对象 a 不在另一对象 b 的 k 最近邻中时，不管另一对象 b 是否在该对象 a 的 最近邻中，我们设置 M ba = M ab = 0 。 4.13 给出一个簇集合的例子，其中基于簇的接近性的合并得到的簇集合比基于簇的连接强度 ( 互连性 ) 的合并得到的簇集合更自然。 答：簇集合例子如下图所示： 图 (a) 图 (b) 图 (a) 两个簇合并后的接近性显然较图 (b) 要差，因此，如果是基于簇的接近性来合并图 中的簇，则会合并图 (b) 的两个簇，合并得到的簇结构几乎与原来的每个簇一样。