第十章 聚类分析2.ppt

第三节 聚类分析原理介绍 聚类分析原理介绍 什么是自然分组结构Natural grouping ? 我们看看以下的例子： 有16张牌 如何将他们分为 一组一组的牌呢？ 聚类分析原理介绍 分成四组 每组里花色相同 组与组之间花色相异 聚类分析原理介绍 分成四组 符号相同的牌为一组 聚类分析原理介绍 分成两组 颜色相同的牌为一组 聚类分析原理介绍 分成两组 大小程度相近的牌分到一组 聚类分析原理介绍 这个例子告诉我们，分组的意义在于我们怎么定义并度量“相似性”Similar 因此衍生出一系列度量相似性的算法 聚类分析原理介绍 相似性Similar的度量（统计学角度） 距离Q型聚类（主要讨论） 主要用于对样本分类 常用的距离有（只适用于具有间隔尺度变量的聚类）： 明考夫斯基距离（包括：绝对距离、欧式距离、切比雪夫距离） 兰氏距离 马氏距离 斜交空间距离 此不详述，有兴趣可参考《应用多元分析》（第二版）王学民 相似系数R型聚类 用于对变量分类，可以用变量之间的相似系数的变形如1－rij定义距离 这里不详细介绍这种聚类度量方法 聚类分析原理介绍 变量按测量尺度（Measurement Level）分类 间隔（Interval）尺度变量 连续变量，如长度、重量、速度、温度等 有序（Ordinal）尺度变量 等级变量，不可加，但可比，如一等、二等、三等奖学金 名义（Nominal）尺度变量 类别变量，不可加也不可比，如性别、职业等 当对象是同时被各种类型的变量描述时，怎样描述对象之间的相异度呢？ 一种可取的办法是把所有变量一起处理，将不同类型的变量组合在单个相异矩阵中，把所有有意义的变量转换到【0，1】的区间上，只进行一次聚类分析。详见参考书 第三节 主要聚类算法的分类 层次的方法（也称系统聚类法）（hierarchical method） 划分方法（partitioning method） 基于密度的方法（density-based method） 基于网格的方法（grid-based method） 基于模型的方法（model-based method） …… 其中，前两种算法是利用统计学定义的距离进行度量 层次的方法（也称系统聚类法）（hierarchical method） 定义：对给定的数据进行层次的分解： 分类： 凝聚的（agglomerative）方法（自底向上）（案例介绍）思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为止。 分裂的方法（divisive）（自顶向下）思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。 层次的方法（也称系统聚类法）（hierarchical method） 特点： 类的个数不需事先定好 需确定距离矩阵 运算量要大，适用于处理小样本数据 层次的方法缺陷 一旦一个步骤（合并或分裂）完成，就不能被撤销或修正，因此产生了改进的层次聚类方法，如BRICH,BURE,ROCK,Chameleon。详见参考书 广泛采用的类间距离 最小距离法（single linkage method） 极小异常值在实际中不多出现，避免极大值的影响 广泛采用的类间距离 最大距离法（complete linkage method） 可能被极大值扭曲，删除这些值之后再聚类 广泛采用的类间距离 类平均距离法（average linkage method）类间所有样本点的平均距离 该法利用了所有样本的信息，被认为是较好的系统聚类法 广泛采用的类间距离 重心法（centroid hierarchical method） 类的重心之间的距离 对异常值不敏感，结果更稳定 广泛采用的类间距离 离差平方和法（ward method） D2=WM－WK－WL 即 对异常值很敏感；对较大的类倾向产生较大的距离，从而不易合并，较符合实际需要。 划分方法（Partitioning method） 较流行的方法有: 动态聚类法（也称逐步聚类法），如k－均值算法、k－中心点算法 思想： 随机选择k个对象，每个对象初始地代表一个类的平均值或中心，对剩余每个对象，根据其到类中心的距离，被划分到最近的类；然后重新计算每个类的平均值。不断重复这个过程，直到所有的样本都不能再分配为止。（图解） 划分方法（Partitioning method） 特点： k事先定好 创建一个初始划分，再采用迭代的重定位技术 不必确定距离矩阵 比系统聚类法运算量要小，适用于处理庞大的样本数据 适用于发现球状类 为最小， ⑦= 　⑥ 　 ⑦ ③ ⑥ 6.32