本章首先介绍聚类分析在数据挖掘中的应用,包括作为其它算法的预处理步骤、获得数据的分布情况、孤立点挖掘。聚类分析的目标就是形成的数据簇,衡量一个聚类分析算法质量,依靠相似度测量机制是否合适以及是否能发现数据背后潜在的、手工难以发现的类知识。以及几种距离的计算方法。其次介绍划分聚类方法,包括k-means算法,PAM算法;随后介绍层次聚类方法包括AGNES (AGglomerative NESting)算法,BIRCH算法,CURE算法;密度聚类方法,包括DBSCAN算法;以及一些其它聚类方法

注脚

展开查看详情

1. 第五章 聚类方法 内容提要  聚类方法概述  划分聚类方法  层次聚类方法  密度聚类方法  其它聚类方法 2018年11月22日11月22日22日 DMKD Sides By MAO 1

2. 聚类分析研究概述  聚类分析源于许多研究领域,包括数据挖掘、统 计学、机器学习、模式识别等。作为一个数据挖 掘中的一个功能,聚类分析能作为一个独立的工 具来获得数据分布的情况,并且概括出每个簇的 特点,或者集中注意力对特定的某些簇做进一步 的分析。  数据挖掘技术的一个突出的特点是处理巨大的、 复杂的数据集,这对聚类分析技术提出了特殊的 挑战,要求算法具有可伸缩性、处理不同类型属 性的能力、发现任意形状的类、处理高维数据的 能力等。根据潜在的各项应用,数据挖掘对聚类 分析方法提出了不同要求。 2018年11月22日11月22日22日 DMKD Sides By MAO 2

3. 聚类分析在数据挖掘中的应用分析  聚类在数据挖掘中的典型应用有:  聚类分析可以作为其它算法的预处理步骤:利用聚类进 行数据预处理,可以获得数据的基本概况,在此基础上 进行特征抽取或分类就可以提高精确度和挖掘效率。也 可将聚类结果用于进一步关联分析,以获得进一步的有 用信息。  可以作为一个独立的工具来获得数据的分布情况:聚类 分析是获得数据分布情况的有效方法。通过观察聚类得 到的每个簇的特点,可以集中对特定的某些簇作进一步 分析。这在诸如市场细分、目标顾客定位、业绩估评、 生物种群划分等方面具有广阔的应用前景。  聚类分析可以完成孤立点挖掘:许多数据挖掘算法试图 使孤立点影响最小化,或者排除它们。然而孤立点本身 可能是非常有用的。如在欺诈探测中,孤立点可能预示 着欺诈行为的存在。 2018年11月22日11月22日22日 DMKD Sides By MAO 3

4. 聚类概念  定义 5-1 聚类分析的输入可以用一组有序对 (X, s) 或 (X, d) 表示,这里 X 表示一组样本, s 和 d 分别是度量样 本间相似度或相异度(距离)的标准。聚类系统的输出是 一个分区若 C={C1, C2,…, Ck} ,其中 Ci(i=1,2….,K) 是 X 的子集,且满足:  C1 CC2,… C, CCk=X  C1∩C2= CØ, Cij  C 中的成员 C1, C2,…, Ck 叫做类或簇( Cluster ),每一 个类或簇都是通过一些特征描述的,通常有如下几种表示 方式:  通过它们的中心或类中关系远的(边界)点表示空间的一类点。  使用聚类树中的结点图形化地表示一个类。  使用样本属性的逻辑表达式表示类。  用中心表示一个类是最常见的方式,当类是紧密的或各向 同性时用这种方法非常好,然而,当类是伸长的或向各向 分布异性时,这种方式就不能正确地表示它们了。 2018年11月22日11月22日22日 DMKD Sides By MAO 4

5. 聚类分析的目标  聚类分析的目标就是形成的数据簇,并且满足下 面两个条件:  一个簇内的数据尽量相似( high Cintra-class C similarity );  不同簇的数据尽量不相似( low Cinter-class C similarity )。  衡量一个聚类分析算法质量,依靠:  相似度测量机制是否合适。  是否能发现数据背后潜在的、手工难以发现的类知识。 2018年11月22日11月22日22日 DMKD Sides By MAO 5

6. 聚类分析方法的分类  按照聚类的标准,聚类方法可分为如下两种:  统计聚类方法:这种聚类方法主要基于对象之间的几何距离的。  概念聚类方法:概念聚类方法基于对象具有的概念进行聚类。  按照聚类算法所处理的数据类型,聚类方法可分为三种:  数值型数据聚类方法:所分析的数据的属性只限于数值数据。  离散型数据聚类方法:所分析的数据的属性只限于离散型数据。  混合型数据聚类方法:能同时处理数值和离散数据。  按照聚类的尺度,聚类方法可被分为以下三种:  基于距离的聚类算法:用各式各样的距离来衡量数据对象之间的相似度,如 k- means 、 k-medoids 、 BIRCH 、 CURE 等算法。  基于密度的聚类算法:相对于基于距离的聚类算法,基于密度的聚类方法主要是 依据合适的密度函数等。  基于互连性 (Linkage-Based)Linkage-Based) 的聚类算法:通常基于图或超图模型。高度连通的 数据聚为一类。  按照聚类聚类分析算法的主要思路,可以被归纳为如下几种。  划分法( Partitioning CMethods ):基于一定标准构建数据的划分。  属于该类的聚类方法有: k-means 、 k-modes 、 k-prototypes 、 k- medoids 、 PAM 、 CLARA 、 CLARANS 等。  层次法( Hierarchical CMethods ):对给定数据对象集合进行层次的分解。  密度法( density-based CMethods ):基于数据对象的相连密度评价。  网格法( Grid-based CMethods ):将数据空间划分成为有限个单元( Cell )的 网格结构,基于网格结构进行聚类。  模型法( Model-Based CMethods ):给每一个簇假定一个模型,然后去寻找能够 很好的满足这个模型的数据集。 C C 2018年11月22日11月22日22日 DMKD Sides By MAO 6

7. 常见的距离函数  按照距离公理,在定义距离测度时需要满足距离 公理的四个条件自相似性、最小性、对称性以及 三角不等性。常用的距离函数有如下几种:  明可夫斯基距离( Minkowski )  二次型距离( Quadratic )  余弦距离  二元特征样本的距离度量 2018年11月22日11月22日22日 DMKD Sides By MAO 7

8. 明可夫斯基( Minkowski )距离距离  假定 x 和 y 是相应的特征, n 是特征的维数。 x 和 y 的 明可夫斯基距离度量的形式如下: 1  n r r d ( x, y )    x i  y i   i 1   当取不同的值时,上述距离度量公式演化为一些特殊的 距离测度 :  当 γ=1 时,明可夫斯基距离演变为绝对值距离: n d ( x, y )  x i  yi i 1  当 γ=2 时,明可夫斯基距离演变为欧氏距离: 1/ 2  n 2 d ( x , y )   x i  yi   i 1  2018年11月22日11月22日22日 DMKD Sides By MAO 8

9. 二次型距离  二次型距离测度的形式如下: d ( x, y ) ( x  y ) T A( x  y)  1 2 其中 A 是非负定矩阵。  当取不同的值时,上述距离度量公式演化为一些特殊的距 离测度:  当 A为单位矩阵时,二次型距离演变为欧氏距离。  当 A为对角阵时,二次型距离演变为加权欧氏距离: 1  n 2 2 d ( x, y )   a ii x i  yi   i 1   当为协方差矩阵时,二次型距离演变为马氏距离。 2018年11月22日11月22日22日 DMKD Sides By MAO 9

10. 余弦距离  余弦距离的度量形式如下: n x yi 1 i i d ( x, y )  n n x y i 1 2 i i 1 2 i 2018年11月22日11月22日22日 DMKD Sides By MAO 10

11. 二元特征样本的距离度量  对于包含一些或全部不连续特征的样本,计算样本间的距 离是比较困难的。因为不同类型的特征是不可比的,只用 一个标准作为度量标准是不合适的。下面我们介绍几种二 元类型数据的距离度量标准。  假定 x 和 y 分别是 n 维特征, xi 和 yi 分别表示每维特征 ,且 xi 和 yi 的取值为二元类型数值 {0 , 1} 。则 x 和 y 的距离定义的常规方法是先求出如下几个参数,然后采用 SMC 、 Jaccard 系数或 Rao 系数。  设 a , b , c 和 d 是样本 x 和 y 中满足 xi=yi=1 , xi=1 且 yi=0 , xi=0 且 yi=1 和 xi=yi=0 的二元类型属性的数量,则  简单匹配系数( Simple Match Coefficient,SMC )距离 a b  S smc ( x, y )  a b c d  Jaccard 系数 S jc ( x, y )  a a b c a S rc ( x, y )   Rao 系数 a b c d 2018年11月22日11月22日22日 DMKD Sides By MAO 11

12. 类间距离  距离函数都是关于两个样本的距离刻画,然而在聚类应用 中,最基本的方法是计算类间的距离。  设有两个类 Ca 和 Cb ,它们分别有 m 和 h 个元素,它们的 中心分别为 γa 和 γb 。设元素 x∈ Ca , y∈ Cb ,这两个元 素间的距离通常通过类间距离来刻画,记为 D(Ca, Cb) 。  类间距离的度量主要有:  最短距离法:定义两个类中最靠近的两个元素间的距离为类间距离 。  最长距离法:定义两个类中最远的两个元素间的距离为类间距离。  中心法:定义两类的两个中心间的距离为类间距离。  类平均法:它计算两个类中任意两个元素间的距离,并且综合他们 为类间距离: 1 DG (Ca , Cb )    d ( x, y )  离差平方和。 mh xCa yCb 2018年11月22日11月22日22日 DMKD Sides By MAO 12

13. 中心法  中心法涉及到类的中心的概念。假如 Ci 是一个聚类, x 是 Ci 内的一个数据点,那么类中心定义如下: 1 xi  ni x xCi 其中 ni 是第 i 个聚类中的点数。因此,两个类 Ca 和 Cb 的类 间距离为: DC (Ca , Cb ) d (ra , rb ) 其中 γa 和 γb 是类 Ca 和 Cb 的中心点, d 是某种形式的距离 公式。 2018年11月22日11月22日22日 DMKD Sides By MAO 13

14. 离差平方和  离差平方和用到了类直径的概念:  类的直径反映了类中各元素间的差异,可定义为类中各元素至类 中心的欧氏距离之和,其量纲为距离的平方: m ra  ( xi  x a ) T ( xi  xb ) i 1  根据上式得到两类 Ca 和 Cb 的直径分别为 γa 和 γb ,类 Ca +b= Ca  Cb 的直径为 γa +b ,则可定义类间距离的平方 为: DW2 (C a , C b ) ra b  ra  rb 2018年11月22日11月22日22日 DMKD Sides By MAO 14

15. 第五章 聚类方法 内容提要  聚类方法概述  划分聚类方法  层次聚类方法  密度聚类方法  其它聚类方法 2018年11月22日11月22日22日 DMKD Sides By MAO 15

16. 划分聚类算法的主要思想  定义 5-2 给定一个有 n 个对象的数据集,划分 聚类技术将构造数据 k 个划分,每一个划分就代 表一个簇, k n 。也就是说,它将数据划分为 k 个簇,而且这 k 个划分满足下列条件:  每一个簇至少包含一个对象。  每一个对象属于且仅属于一个簇。  对于给定的 k ,算法首先给出一个初始的划分方 法,以后通过反复迭代的方法改变划分,使得每 一次改进之后的划分方案都较前一次更好。 2018年11月22日11月22日22日 DMKD Sides By MAO 16

17. 聚类设计的评价函数  一种直接方法就是观察聚类的类内差异( Within cluster variation )和类间差异 (Between cluster variation ) 。  类内差异:衡量聚类的紧凑性,类内差异可以用特定的距离函数 k k w(C )  w(C )   d ( x, x ) 2 来定义,例如, i i i 1 i 1 xCi  类间差异:衡量不同聚类之间的距离,类间差异定义为聚类中心 间的距离,例如, b(C )   d ( x j , xi ) 2 1j i k  聚类的总体质量可被定义为 w(c) 和 b(c) 的一个单调组合 ,比如 w(c) / b(c) 。 2018年11月22日11月22日22日 DMKD Sides By MAO 17

18. k-means 算法  k-means 算法,也被称为 k- 平均或 k- 均值,是一种得到 最广泛使用的聚类算法。相似度的计算根据一个簇中对象 的平均值来进行。 算法 5-1 C Ck-means 算法 输入:簇的数目 k 和包含 n 个对象的数据库。 输出: k 个簇,使平方误差准则最小。 ( 1)assign Cinitial Cvalue Cfor Cmeans; C/* 任意选择 k 个对象作为初始的簇中心; */ xi  C i  xCi x C(Linkage-Based)2) CREPEAT k E i 1  xC x  xi 2 i x C(Linkage-Based)3) C C C CFOR Cj=1 Cto Cn CDO Cassign Ceach C C j C Cto Cthe Cclosest clusters;  算法首先随机地选择 k 个对象,每个对象初始地代表了一 C(Linkage-Based)4个簇的平均值或中心。对剩余的每个对象根据其与各个簇 ) C C C C C C CFOR Ci=1 Cto Ck CDO C C C C C C C C C C C C C C C C C C C C C/ C* 更新簇平均值 */ 中心的距离,将它赋给最近的簇。然后重新计算每个簇的 平均值。这个过程不断重复,直到准则函数收敛。 C(Linkage-Based)5) C C CCompute C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C C/* 计算准则函数 E*/  准则函数试图使生成的结果簇尽可能地紧凑和独立。 C(Linkage-Based)6) CUNTIL C CE 不再明显地发生变化。 2018年11月22日11月22日22日 DMKD Sides By MAO 18

19. k-means 例子 样本数据 序号 属性 属性 1 属性 根据所给的数据通过对其实施 k-means ( 设 n=8 , k=2), ,其主要执行执行步骤: 2 1 1 1 2 2 1 第一次迭代:假定随机选择的两个对象,如序号 属性 1 和序号 属性 3 当作初始点,分别找到离两 3 1 2 点最近的对象,并产生两个簇 {1 , 2} 和 {3 , 4 , 5 , 6 , 7 , 8} 。 4 2 2 对于产生的簇分别计算平均值,得到平均值点。 5 4 3 对于 {1 , 2} ,平均值点为( 1.5 , 1 )(这里的平均值是简单的相加出 6 5 3 2 ); 7 4 4 对于 {3 , 4 , 5 , 6 , 7 , 8} ,平均值点为( 3.5 , 3 )。 8 5 4 迭代次数 平均值 第二次迭代:通过平均值调整对象的所在的簇,重新聚类,即将所有点按离平均值点 平均值 产生的新簇 新平均值 新平均值 (簇 1 ) (簇 2 ) (簇 1 ) (簇 2 ) ( 1.5 , 1 )、( 3.5 , 1 )最近的原则重新分配。得到两个新的簇: 1 ( 1 , 1 ) ( 1 , 2 ) {1 , 2} , {3 , 4 , 5 , 6 , 7 , 8} ( 1.5 , 1 ) ( 3.5 , 3 ) 2 {1 , 2 , 3 , 4} 和 {5 , 6 , 7 , 8} 。重新计算簇平均值点,得到新的平均值 ( 1.5 , 1 ) ( 3.5 , 3 ) {1 , 2 , 3 , 4} , {5 , 6 , 7 , 8} ( 1.5 , 1.5 ) ( 4.5 , 3.5 ) 点为( 1.5 , 1.5 )和( 4.5 , 3.5 )。 3 ( 1.5 , 1.5 ) ( 4.5 , 3.5 ) {1 , 2 , 3 , 4} , {5 , 6 , 7 , 8} ( 1.5 , 1.5 ) ( 4.5 , 3.5 ) 2018年11月22日11月22日22日 DMKD Sides By 1.5 第三次迭代:将所有点按离平均值点( MAO , 1.5 )和( 4.5 , 3.5 )最近的原则重 19

20. K-means 1. Ask user how many clusters they’d like. (e.g. k=5) Copyright © 2001, 2004, Andrew W. Moore

21. K-means 1. Ask user how many clusters they’d like. (e.g. k=5) 2. Randomly guess k cluster Center locations Copyright © 2001, 2004, Andrew W. Moore

22. K-means 1. Ask user how many clusters they’d like. (e.g. k=5) 2. Randomly guess k cluster Center locations 3. Each datapoint finds out which Center it’s closest to. (Thus each Center “owns” a set of datapoints) Copyright © 2001, 2004, Andrew W. Moore

23. K-means 1. Ask user how many clusters they’d like. (e.g. k=5) 2. Randomly guess k cluster Center locations 3. Each datapoint finds out which Center it’s closest to. 4. Each Center finds the centroid of the points it owns Copyright © 2001, 2004, Andrew W. Moore

24. K-means 1. Ask user how many clusters they’d like. (e.g. k=5) 2. Randomly guess k cluster Center locations 3. Each datapoint finds out which Center it’s closest to. 4. Each Center finds the centroid of the points it owns… 5. …and jumps Copyright © 2001, 2004, Andrew W. there Moore

25. K-means Start Advance apologies: in Black and White this example will deteriorate Example generated by Dan Pelleg’s super-duper fast K- means system: Dan Pelleg and Andrew Moore. Accelerating Exact k- means Algorithms with Geometric Reasoning. Proc. Conference on Knowledge Discovery in Databases Copyright © 2001, 1999, 2004, Andrew W. (KDD99) (available on Moore

26. K-means continues … Copyright © 2001, 2004, Andrew W. Moore

27. K-means continues … Copyright © 2001, 2004, Andrew W. Moore

28. K-means continues … Copyright © 2001, 2004, Andrew W. Moore

29. K-means continues … Copyright © 2001, 2004, Andrew W. Moore

30. K-means continues … Copyright © 2001, 2004, Andrew W. Moore

31. K-means continues … Copyright © 2001, 2004, Andrew W. Moore

32. K-means continues … Copyright © 2001, 2004, Andrew W. Moore

33. K-means continues … Copyright © 2001, 2004, Andrew W. Moore

34. K-means terminates Copyright © 2001, 2004, Andrew W. Moore

35. k-means 算法的性能分析  主要优点:  是解决聚类问题的一种经典算法,简单、快速。  对处理大数据集,该算法是相对可伸缩和高效率的。  当结果簇是密集的,它的效果较好。  主要缺点  在簇的平均值被定义的情况下才能使用,可能不适用 于某些应用。  必须事先给出 k (要生成的簇的数目),而且对初值 敏感,对于不同的初始值,可能会导致不同结果。  不适合于发现非凸面形状的簇或者大小差别很大的簇。 而且,它对于“躁声”和孤立点数据是敏感的。”和孤立点数据是敏感的。 2018年11月22日11月22日22日 DMKD Sides By MAO 35

36. k-means 的几种改进方法  k-mode 算法:实现对离散数据的快速聚类,保留 了 k-means 算法的效率同时将 k-means 的应用 范围扩大到离散数据。  k-prototype 算法:可以对离散与数值属性两种混 合的数据进行聚类,在 k-prototype 中定义了一个 对数值与离散属性都计算的相异性度量标准。  k- 中心点算法 k -means 算法对于孤立点是敏感的。 为了解决这个问题,不采用簇中的平均值作为参照 点,可以选用簇中位置最中心的对象,即中心点作 为参照点。这样划分方法仍然是基于最小化所有对 象与其参照点之间的相异度之和的原则来执行的。 2018年11月22日11月22日22日 DMKD Sides By MAO 36

37. PAM 算法基本思想  PAM 作为最早提出的 k- 中心点算法之一,它选用簇中位 置最中心的对象作为代表对象,试图对 n 个对象给出 k 个 划分。  代表对象也被称为是中心点,其他对象则被称为非代表对 象。  最初随机选择 k 个对象作为中心点,该算法反复地用非代 表对象来代替代表对象,试图找出更好的中心点,以改进 聚类的质量。  在每次迭代中,所有可能的对象对被分析,每个对中的一 个对象是中心点,而另一个是非代表对象。  对可能的各种组合,估算聚类结果的质量。一个对象 Oi 被 可以产生最大平方 - 误差值减少的对象代替。在一次迭代 中产生的最佳对象集合成为下次迭代的中心点。 2018年11月22日11月22日22日 DMKD Sides By MAO 37

38. PAM 算法基本思想 ( 续 )  为了判定一个非代表对象 Oh 是否是当前一个代表 对象 Oi 的好的替代,对于每一个非中心点对象 Oj ,下面的四种情况被考虑:  第一种情况: Oj 当前隶属于中心点对象 Oi 。如果 Oi 被 Oh 所代替作为中心点,且 Oj 离一个 Om最近, i≠m,那 么 Oj 被重新分配给 Om。  第二种情况: Oj 当前隶属于中心点对象 Oi 。如果 Oi 被 Oh 代替作为一个中心点,且 Oj 离 Oh 最近,那么 Oj 被重 新分配给 Oh 。  第三种情况: Oj 当前隶属于中心点 Om, m≠i 。如果 Oi 被 Oh 代替作为一个中心点,而 Oj 依然离 Om最近,那么 对象的隶属不发生变化。  第四种情况: Oj 当前隶属于中心点 Om, m≠i 。如果 Oi 被 Oh 代替作为一个中心点,且 Oj 离 Oh 最近,那么 Oi 被 重新分配给 Oh 。 2018年11月22日11月22日22日 DMKD Sides By MAO 38

39. PAM 算法基本思想 ( 续 )  每当重新分配发生时,平方 - 误差 E 所产生的差别对代价 函数有影响。因此,如果一个当前的中心点对象被非中心 点对象所代替,代价函数计算平方 - 误差值所产生的差别。 替换的总代价是所有非中心点对象所产生的代价之和。  如果总代价是负的,那么实际的平方 - 误差将会减小, Oi 可以被 Oh 替代 。  如果总代价是正的,则当前的中心点 Oi 被认为是可接受的,在本次迭代中 没有变化。 总代价定义如下: n TCih  C jih j 1 其中, Cjih 表示 Oj 在 Oi 被 Oh 代替后产生的代价。下面 我们将介绍上面所述的四种情况中代价函数的计算公式, 其中所引用的符号有: Oi 和 Om 是两个原中心点, Oh 将 替换 Oi 作为新的中心点。 2018年11月22日11月22日22日 DMKD Sides By MAO 39

40. PAM 算法代价函数的四种情况 第一种情况 第二种情况 第三种情况 第四种情况 Oj 被重新分配给 Om , Oj 被重新分配给 Oh , Cjih =d(j, m)-d(j, i) Cjih =d(j, h)-d(j, i) 2018年11月22日11月22日22日 DMKD Sides By MAO 40

41. PAM 算法基本思想 ( 续 ) 算法 5-2 PAM ( k- 中心点算法) 输入:簇的数目 k 和包含 n 个对象的数据库。 输出: k 个簇,使得所有对象与其最近中心点的相异度总和最小。 ( 1 ) 任意选择 k 个对象作为初始的簇中心点; ( 2 ) REPEAT ( 3 ) 指派每个剩余的对象给离它最近的中心点所代表的簇; (4) REPEAT (5) 选择一个未被选择的中心点 Oi ; (6) REPEAT (7) 选择一个未被选择过的非中心点对象 Oh ; (8) 计算用 Oh 代替 Oi 的总代价并记录在 S 中; (9) UNTIL 所有的非中心点都被选择过; ( 10 ) UNTIL 所有的中心点都被选择过; ( 11 ) IF 在 S 中的所有非中心点代替所有中心点后的计算出的总 代价有小于 0 的存在 THEN 找出 S 中的用非中心点替代中心点后代 价最小的一个,并用该非中心点替代对应的中心点,形成一个新的 k 个中心点的集合; ( 12 ) UNTIL 没有再发生簇的重新分配,即所有的 S 都大于 0. 2018年11月22日11月22日22日 DMKD Sides By MAO 41

42. PAM 算法基本思想 ( 续 ) 假如空间中的五个点{ A 、B、C、D、E}如图如图 1 所示,各点之间的距离关系如表 1 所示, 根据所给的数据对其运行 PAM 算法实现划分聚类(设 k=2 )。 样本点间距离如下表所示 : 样本点 A B C D E C C 2 A A A 0 1 2 2 3 2 D D B 1 0 2 4 3 B B 3 C 2 2 0 1 5 D 2 4 1 0 3 E E E 3 3 5 3 0 样本点 起始中心点为 A,B 第一步 建立阶段:假如从 5 个对象中随机抽取的 2 个中心点为 {AA , B}, 则样本被划分为 {AA 、 C 、 D} 和 {AB 、 E} ,如图 5-3 所示。 第二步 交换阶段:假定中心点 A、 B分别被非中心点 } 和 {AC 、 D、 E} 替换,根据 PAM 算法需 要计算下列代价 TCAC 、 CTCAD 、 CTCAE 、 TCBC 、 TCBD 、 CTCBE 。 我们以 TCAC 为例说明计算过程: a) C 当 A被 C替换以后, A不再是一个中心点,因为 A离 B比 A离 C近, A被分配到 B中心 点代表的簇, CAAC=d(Linkage-Based)A,B)-d(Linkage-Based)A,A)=1 。 b) CB 是一个中心点,当 A被 C替换以后, B不受影响, CBAC=0 。 c) CC 原先属于 A中心点所在的簇,当 A被 C替换以后, C是新中心点,符合 PAM 算法代价 函数的第二种情况 CCAC=d(Linkage-Based)C,C)-d(Linkage-Based)C,A)=0-2=-2 。 d) CD 原先属于 A中心点所在的簇,当 A被 C替换以后,离 D最近的中心点是 C,根据 PAM 算法代价函数的第二种情况 CDAC=d(Linkage-Based)D,C)-d(Linkage-Based)D,A)=1-2=-1 。 e) CE 原先属于 B中心点所在的簇,当 A被 C替换以后,离 E最近的中心仍然是 B,根据 PAM 算法代价函数的第三种情况 CEAC=0 。 因此, TCAC=CAAC+ CBAC+ CBAC+ CDAC+ CEAC=1+0-2-1+0=-2 。 2018年11月22日11月22日22日 DMKD Sides By MAO 42

43. PAM 算法基本思想 ( 续 ) 在上述代价计算完毕后,我们要选取一个最小的代价,显然有多种替换可以选择,我们选择 第一个最小代价的替换(也就是 C替换 A),根据图 5-4 ( a )所示,样本点被划分为 {A CB 、 A 、 E} 和 {AC 、 D} 两个簇。图 5-4 ( b )和图 5-4 ( c )分别表示了 D替换 A, E替换 A的情况 和相应的代价 C C C A A A 1 2 1 1 1 1 D D D B B B 3 3 3 E E E (a) C 替换 A, TCAC=-2 (b) D 替换 A, TCAD=-2 (c) E 替换 A, TCAE=- 1 图 5-4 替换中心点 C C A C 图 5-5 A ( a )、( 1 b )、( c )分别表示了用 A 1 C、 D、 E替换 B的情况和相应的代价。 A 2 1 1 1 D D 2 D B B B 3 3 E E E (a) C 替换 B, TCBC=-2 (b) D 替换 B, TCBD=-2 (c) E 替换 B, TCBE=-2 图 5-5 替换中心点 B 通过上述计算,已经完成了 PAM 算法的第一次迭代。在下一迭代中,将用其他的非中心点 {AA 、 D、 E} 替换中心点 {AB 、 C} ,找出具有最小代价的替换。一直重复上述过程,直到代价不再 减小为止。 2018年11月22日11月22日22日 DMKD Sides By MAO 43

44. 第五章 聚类方法 内容提要  聚类方法概述  划分聚类方法  层次聚类方法  密度聚类方法  其它聚类方法 2018年11月22日11月22日22日 DMKD Sides By MAO 44

45. 层次聚类方法概述  层次聚类方法对给定的数据集进行层次的分解, 直到某种条件满足为止。具体又可分为:  凝聚的层次聚类:一种自底向上的策略,首先将每个对 象作为一个簇,然后合并这些原子簇为越来越大的簇, 直到某个终结条件被满足。  分裂的层次聚类:采用自顶向下的策略,它首先将所有 对象置于一个簇中,然后逐渐细分为越来越小的簇,直 到达到了某个终结条件。  层次凝聚的代表是 AGNES 算法。层次分裂的代 表是 DIANA 算法。 2018年11月22日11月22日22日 DMKD Sides By MAO 45

46. AGNES 算法  AGNES (AGglomerative NESting) 算法最初将 每个对象作为一个簇,然后这些簇根据某些准则 被一步步地合并。两个簇间的相似度由这两个不 同簇中距离最近的数据点对的相似度来确定。聚 类的合并过程反复进行直到所有的对象最终满足 簇数目。 算法 5-3 AGNES (自底向上凝聚算法) 输入:包含 n 个对象的数据库,终止条件簇的数目 k 。 输出: k 个簇,达到终止条件规定簇数目。 (1) 将每个对象当成一个初始簇; (2) REPEAT (3) 根据两个簇中最近的数据点找到最近的两个簇; 2018年11月22日11月22日22日 DMKD Sides By MAO 46

47. AGNES 算法例子 序号 属性 属性 1 属性 2 1 1 1 第 1 步:根据初始簇计算每个簇之间的距离,随机找出距离最小的两个簇,进 2 1 2 行合并,最小距离为 1 ,合并后 1 , 2 点合并为一个簇。 3 2 1 4 2 2 第 2 步:,对上一次合并后的簇计算簇间距离,找出距离最近的两个簇进行合 5 3 4 并,合并后 3 , 4 点成为一簇。 6 3 5 7 4 4 第 3 步:重复第 2 步的工作, 5 , 6 点成为一簇。 8 4 5 第 4 步:重复第 2 步的工作, 7 , 8 点成为一簇。 步骤 最近的簇距离 最近的两个簇 合并后的新簇 1 1 {1} , {2} {1 , 2} , {3} , {4} , {5} , {6} , {7} , {8} 2 1 5 步:合并 第{3} , {4} {1 , 2} , {3 , 4} {1 , 成为一个包含四个点的簇。 2} , {3 , 4} , {5} , {6} , {7} , {8} 3 1 {5} , {6} {1 , 2} , {3 , 4} , {5 , 6} , {7} , {8} 第 6 步:合并 {5 , 6} , {7 , 8} ,由于合并后的簇的数目已经达到了用 4 1 {7} , {8} {1 , 2} , {3 , 4} , {5 , 6} , {7 , 8} 户输入的终止条件程序结束。 5 1 {1 , 2} , {3 , 4} {1 , 2 , 3 , 4} , {5 , 6} , {7 , 8} 2018年11月22日11月22日22日 DMKD Sides By MAO 47

48. AGNES 性能分析  AGNES 算法比较简单,但经常会遇到合并点选择的困难。 假如一旦一组对象被合并,下一步的处理将在新生成的簇 上进行。已做处理不能撤消,聚类之间也不能交换对象。 如果在某一步没有很好的选择合并的决定,可能会导致低 质量的聚类结果。  这种聚类方法不具有很好的可伸缩性,因为合并的决定需 要检查和估算大量的对象或簇。  假定在开始的时候有 n 个簇,在结束的时候有 1 个簇,因 此在主循环中有 n 次迭代,在第 i 次迭代中,我们必须在 n-i+1 个簇中找到最靠近的两个聚类。另外算法必须计算 所有对象两两之间的距离,因此这个算法的复杂度为 O(n2) ,该算法对于 n 很大的情况是不适用的。 2018年11月22日11月22日22日 DMKD Sides By MAO 48

49. DIANA 算法  DIANA (Divisive ANAlysis) 算法是典型的分裂聚类方 法。  在聚类中,用户能定义希望得到的簇数目作为一个结束条 件。同时,它使用下面两种测度方法: 1  簇的直径:在一个簇中的任意两个数据点的距离中的最大值。 d (C , C )    x y avg i j xCi yC j ni n j  平均相异度(平均距离): 算法 5-4 DIANA (自顶向下分裂算法) 输入:包含 n 个对象的数据库,终止条件簇的数目 k 。 输出: k 个簇,达到终止条件规定簇数目。 ( 1 )将所有对象整个当成一个初始簇; ( 2 ) C FOR ( i=1; i≠k; i++) DO BEGIN ( 3 ) 在所有簇中挑出具有最大直径的簇 C ; ( 4 ) 找出 C 中与其它点平均相异度最大的一个点 p 并把 p 放入 splinter group ,剩余的放在 old party 中; ( 5 ) . REPEAT ( 6 ) 在 old party 里找出到最近的 splinter group 中的点的距离不大于到 old party 中最近点的距离的点,并 2018年11月22日11月22日22日 DMKD Sides By MAO 49

50. DIANA 算法例子 序号 属性 属性 1 属性 2 第 1 步,找到具有最大直径的簇,对簇中的每个点计算平均相异度(假定采用是欧式距 1 1 1 离)。 2 1 2 1 的平均距离:( 1+1+1.414+3.6+4.24+4.47+5 ) /7=2.96 3 2 1 类似地, 2 的平均距离为 2.526 ; 3 的平均距离为 2.68 ; 4 的平均距离为 2.18 ; 5 的平均距离为 2.18 ; 6 的平均距离为 2.68 ; 7 的平均距离为 4 2 2 2.526 ; 8 的平均距离为 2.96 。 5 3 4 挑出平均相异度最大的点 1 放到 splinter group 中,剩余点在 old party 中。 6 3 5 7 4 4 第 2 步,在 old party 里找出到最近的 splinter group 中的点的距离不大于到 old 8 4 5 party 中最近的点的距离的点,将该点放入 splinter group 中,该点是 2 。 步骤 具有最大直径的簇 第 3 步,重复第 2splinter 步的工作,group Old party splinter group 中放入点 3 。 1 {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8}{1} {2 , 3 , 4 , 5 , 6 , 7 , 8} 2 {1 , 2 , 3 , 4 , 5 , 第64, 7 , 8}{1 步,重复第 , 2} splinter group 中放入点 2 步的工作, {3 , 4 ,4 。5 , 6 , 7 , 8} 3 {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8}{1 , 2 , 3} {4 , 5 , 6 , 7 , 8} 第 5 步,没有在 old party 中的点放入了 splinter group 中且达到终止条件( k-2 ) 4 {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8}{1 , 2 , 3 , 4} {5 , 6 , 7 , 8} 5 {1 , 2 , 3 , 4 , 5 , 6 ,,程序终止。如果没有到终止条件,因该从分裂好的簇中选一个直径最大的簇继 7 , 8}{1 , 2 , 3 , 4} {5 , 6 , 7 , 8} 终止 2018年11月22日11月22日22日 续分裂。 DMKD Sides By MAO 50

51. 层次聚类方法的改进  层次聚类方法尽管简单,但经常会遇到合并或分 裂点的选择的困难。  改进层次方法的聚类质量的一个有希望的方向是 将层次聚类和其他聚类技术进行集成,形成多阶 段聚类。  下面介绍两个改进的层次聚类方法 CURE 和 BIRTH 。 2018年11月22日11月22日22日 DMKD Sides By MAO 51

52. 层次聚类方法的改进 --BIRCH  BIRCH (利用层次方法的平衡迭代归约和聚类)是一个综 合的层次聚类方法,它用聚类特征和聚类特征树( CF ) 来概括聚类描述。该算法通过聚类特征可以方便地进行中 心、半径、直径及类内、类间距离的运算。 CF 树是一个 具有两个参数分支因子 B 和阂值 T 的高度平衡树,存储了 层次聚类的聚类特征。分支因子定义了每个非叶节点孩子 的最大数目,而阈值给出了存储在树的叶子节点中的子聚 类的最大直径。  BIRCH 算法的工作过程包括两个阶段:  阶段一: BIRCH 扫描数据库,建立一个初始存放于内存的 CF 树, 它可以被看作数据的多层压缩,试图保留数据内在的聚类结构。 随着对象的插入, CF 树被动态地构造,不要求所有的数据读入内 存,而可在外存上逐个读入数据项。因此, BIRTH 方法对增量或 动态聚类也非常有效。  阶段二: BIRCH 采用某个聚类算法对 CF 树的叶结点进行聚类。在 这个阶段可以执行任何聚类算法,例如典型的划分方法。  BIRCH 算法试图利用可用的资源来生成最好的聚类结果。 通过一次扫描就可以进行较好的聚类,故该算法的计算复 杂度是 O(n) , n 是对象的数目。 2018年11月22日11月22日22日 DMKD Sides By MAO 52

53. 层次聚类方法的改进 --CURE  很多聚类算法只擅长处理球形或相似大小的聚类,另外有些聚类算法 对孤立点比较敏感。 CURE 算法解决了上述两方面的问题,选择基于 质心和基于代表对象方法之间的中间策略,即选择空间中固定数目的 具有代表性的点,而不是用单个中心或对象来代表一个簇。该算法首 先把每个数据点看成一簇,然后再以一个特定的收缩因子向簇中心“收 缩”它们,即合并两个距离最近的代表点的簇。  CURE 算法采用随机取样和划分两种方法的组合,具体步骤如下:  从源数据集中抽取一个随机样本。  为了加速聚类,把样本划分成 p 份,每份大小相等。  对每个划分局部地聚类。  根据局部聚类结果,对随机取样进行孤立点剔除。主要有两种措施:如果 一个簇增长得太慢,就去掉它。在聚类结束的时候,非常小的类被剔除。  对上一步中产生的局部的簇进一步聚类。落在每个新形成的簇中的代表点 根据用户定义的一个收缩因子收缩或向簇中心移动。这些点代表和捕捉 到了簇的形状。  用相应的簇标签来标记数据。  由于它回避了用所有点或单个质心来表示一个簇的传统方法,将一个 簇用多个代表点来表示,使 CURE 可以适应非球形的几何形状。另外 ,收缩因子降底了噪音对聚类的影响,从而使 CURE 对孤立点的处理 更加健壮,而且能识别非球形和大小变化比较大的簇。 CURE 的复杂 度是 O(n) , n 是对象的数目,所以该算法适合大型数据的聚类。 2018年11月22日11月22日22日 DMKD Sides By MAO 53

54. 第五章 聚类方法 内容提要  聚类方法概述  划分聚类方法  层次聚类方法  密度聚类方法  其它聚类方法 2018年11月22日11月22日22日 DMKD Sides By MAO 54

55. 密度聚类方法  密度聚类方法的指导思想是,只要一个区域中的点的密度 大于某个域值,就把它加到与之相近的聚类中去。这类算 法能克服基于距离的算法只能发现“类圆形”的聚类的缺点 ,可发现任意形状的聚类,且对噪声数据不敏感。但计算 密度单元的计算复杂度大,需要建立空间索引来降低计算 量,且对数据维数的伸缩性较差。这类方法需要扫描整个 数据库,每个数据对象都可能引起一次查询,因此当数据 量大时会造成频繁的 I/O 操作。代表算法有: DBSCAN 、 OPTICS 、 DENCLUE 算法等。  DBSCAN ( Density-Based Spatial Clustering of Applications with Noise )一个比较有代表性的基于密 度的聚类算法。与划分和层次聚类方法不同,它将簇定义 为密度相连的点的最大集合,能够把具有足够高密度的区 域划分为簇,并可在有“噪声”的空间数据库中发现任意形 状的聚类。 2018年11月22日11月22日22日 DMKD Sides By MAO 55

56. 密度聚类方法 -- DBSCAN  定义 5-3 对象的 ε- 临域:给定对象在半径 ε 内的区域。  定义 5-4 核心对象:如果一个对象的 ε- 临域至少包含最小数目 MinPts 个对象,则称该对象为核心对象。  例如,在图 5-6 中, ε=1cm , MinPts=5 , q 是一个核心对象 。  定义 5-5 直接密度可达:给定一个对象集合 D ,如果 p 是在 q 的 ε- 邻域内,而 q 是一个核心对象,我们说对象 p 从对象 q 出发是 直接密度可达的。  例如,在图 5-6 中, ε=1cm , MinPts=5 , q 是一个核心对象 ,对象 p 从对象 q 出发是直接密度可达的。 图 5-6 直接密度可达 2018年11月22日11月22日22日 DMKD Sides By MAO 56

57. 密度聚类方法 -- DBSCAN  定义 5-6 密度可达的:如果存在一个对象链 p1 , p2 , …, pn , p1=q , pn=p ,对 pi∈D ,( 1<=i<=n ), pi+1 是从 pi 关于 ε 和 MitPts 直接密度可达的,则对象 p 是从对象 q 关于 ε 和 MinPts 密度可达的。  例如,在图 5-7 中, ε=1cm , MinPts=5 , q 是一个核心对象, p1 是 从 q 关于 ε 和 MitPts 直接密度可达, p 是从 p1 关于 ε 和 MitPts 直接密度 可达,则对象 p 从对象 q 关于 ε 和 MinPts 密度可达的。  定义 5-7 密度相连的:如果对象集合 D 中存在一个对象 o ,使得对象 p 和 图 5-6 直接密度可达 q 是从 o 关于 ε 和 MinPts 密度可达的,那么对象 p 和 q 是关于 ε 和 MinPts 密度相连的。  定义 5-8 噪声 : 一个基于密度的簇是基于密度可达性的最大的密度相连对 象的集合。不包含在任何簇中的对象被认为是“噪声”。  图 5-6 直接密度可达 图 5-8 密度相连 图 5-9 噪声 2018年11月22日11月22日22日 DMKD Sides By MAO 57

58. DBSCAN 算法描述  DBSCAN 通过检查数据集中每个对象的 ε- 邻域来寻找 聚类。如果一个点 p 的 ε- 邻域包含多于 MinPts 个对象 ,则创建一个 p 作为核心对象的新簇。然 后, DBSCAN 反复地寻找从这些核心对象直接密度可 达的对象,这个过程可能涉及一些密度可达簇的合并。 当没有新的点可以被添加到任何簇时,该过程结束。具 体如下: DBSCAN 算法描述 算法 5-5 CDBSCAN C C 输入:包含 n个对象的数据库,半径 ε ,最少数目 MinPts 。 输出:所有生成的簇,达到密度要求。 1. C CREPEAT 2. C C C C C 从数据库中抽取一个未处理过的点; 3. C C C C CIF C 抽出的点是核心点 THEN 找出所有从该点密度可达的对象,形成一个簇 4. C C C C CELSE C 抽出的点是边缘点 ( 非核心对象 ) ,跳出本次循环,寻找下一点; 5. C C CUNTIL C 所有点都被处理; 2018年11月22日11月22日22日 DMKD Sides By MAO 58

59. DBSCAN 算法举例 下面给出一个样本事务数据库(见左表),对它实施 DBSCAN 算法。 根据所给的数据通过对其进行 DBSCAN 算法,以下为算法的步骤(设 n=12 ,用户输入 ε=1 , MinPts=4 )                    样本事务数据库              DBSCAN 算法执行过程示意 序 属性 1 属性 2 步骤 选择的点 在 ε 中点的个数 通过计算可达点而找到的新簇 号 属性 1 1 2 无 1 1 0 2 2 2 无 2 4 0 3 3 3 无 3 0 1 4 4 5 簇 C1 : {1 , 3 , 4 , 5 , 9 , 10 , 12} 4 1 1 5 5 3 已在一个簇 C1 中 5 2 1 6 6 3 无 6 3 1 7 7 5 簇 C2 : {2 , 6 , 7 , 8 , 11} 7 4 1 8 8 2 已在一个簇 C2 中 8 5 1 9 0 2 9 9 3 已在一个簇 C1 中 10 1 2 10 10 4 已在一个簇 C1 中, 11 4 2 11 11 2 已在一个簇 C2 中 12 1 3 12 12 2 已在一个簇 C1 中              聚出的类为 {A1 , 3 , 4 , 5 , 9 , 11 , 12} , {A2 , 6 , 7 , 8 , 10} 。 2018年11月22日11月22日22日 DMKD Sides By MAO 59

60. DBSCAN 算法举例(续)距离 第 1 步,在数据库中选择一点 1 ,由于在以它为圆心的,以 1 为 算法执行过程: 半径的圆内包含 2 个点(小于 4 ),因此它不是核心点,    选择下一个点。 步 选 在ε 通过计算可达点而找到的 骤 择 中 新簇 第 2 步,在数据库中选择一点 2 ,由于在以它为圆心的,以 1 为 的 点 半径的圆内包含 2 个点,因此它不是核心点,选择下一个 点 的 个 点。 数 第 3 步,在数据库中选择一点 3 ,由于在以它为圆心的,以 1 为 1 1 2 无 半径的圆内包含 3 个点,因此它不是核心点,选择下一个 2 2 2 无 点。 第 4 步,在数据库中选择一点 4 ,由于在以它为圆心的,以 1 为 3 3 3 无 半径的圆内包含 5 个点,因此它是核心点,寻找从它出发 4 4 5 簇 C1 : {1 , 3 , 4 , 5 可达的点(直接可达 4 个,间接可达 3 个),聚出的新类 , 9 , 10 , 12} {A1 , 3 , 4 , 5 , 9 , 10 , 12} ,选择下一个点。 5 5 3 已在一个簇 C1 中 第 5 步,在数据库中选择一点 5 ,已经在簇 1 中,选择下一个点 6 6 3 无 。 7 7 5 簇 C2 : {2 , 6 , 7 , 8 第 6 步,在数据库中选择一点 6 ,由于在以它为圆心的,以 1 为 , 11} 半径的圆内包含 3 个点,因此它不是核心点,选择下一个 8 8 2 已在一个簇 C2 中 点。 9 9 3 已在一个簇 C1 中 第 7 步,在数据库中选择一点 7 ,由于在以它为圆心的,以 1 为 半径的圆内包含 5 个点,因此它是核心点,寻找从它出发 10 10 4 已在一个簇 C1 中, 可达的点,聚出的新类 {A2 , 6 , 7 , 8 , 11} ,选择下一 11 11 2 已在一个簇 C2 中 个点。 12 12 2 已在一个簇 C1 中 第 8 步,在数据库中选择一点 8 ,已经在簇 2 中,选择下一个点 。 第 9 步,在数据库中选择一点 9 ,已经在簇 1 中,选择下一个点 。 第 10 步,在数据库中选择一点 10 ,已经在簇 1 中,选择下一个 2018年11月22日11月22日22日 点。 DMKD Sides By MAO 60

61. 第五章 聚类方法 内容提要  聚类方法概述  划分聚类方法  层次聚类方法  密度聚类方法  其它聚类方法 2018年11月22日11月22日22日 DMKD Sides By MAO 61

62. STING  STING(Statistaical Information Grid_based method) 是一种基于网格的多分辨率聚类技术,它将空间区域划分为 矩形单元。针对不同级别的分辨率,通常存在多个级别的巨 型单元,这些单元形成了一个层次结构:高层的每个单元被 划分为多个第一层的单元。高层单元的统计参数可以很容易 的从底层单元的计算得到。这些参数包括属性无关的参数 count 、属性相关的参数 m (平均值)、 s( 标准偏 差 ) 、 min( 最小值 ) 、 max( 最大值 ) 以及该单元中属性 值遵循的分布类型。 STING 算法采用了一种多分辨率的方 法来进行聚类分析,该聚类算法的质量取决于网格结构最低 层的粒度。如果粒度比较细,处理的代价会显著增加;但如 果粒度较粗,则聚类质量会受到影响。  STING 算法的主要优点是效率高,通过对数据集的一次扫 描来计算单元的统计信息,因此产生聚类的时间复杂度是 O(n) 。在建立层次结构以后,查询的时间复杂度是 O(g), g 远小于 n 。 STING 算法采用网格结构,有利于并行处理和 增量更新。 2018年11月22日11月22日22日 DMKD Sides By MAO 62

63. SOM 神经网络  SOM 神经网络是一种基于模型的聚类方法。 SOM 神经 网络由输入层和竞争层组成。  输入层由 N个输入神经元组成,竞争层由 mm C= CM个输出神经元组成, 且形成一个二维平面阵列。  输入层各神经元与竞争层各神经元之间实现全互连接。  该网络根据其学习规则,通过对输入模式的反复学习,捕 捉住各个输入模式中所含的模式特征,并对其进行自组织 ,在竞争层将聚类结果表现出来,进行自动聚类。竞争层 的任何一个神经元都可以代表聚类结果。 2018年11月22日11月22日22日 DMKD Sides By MAO 63

64. SOM 神经网络 ( 续 )  图 1 给出了 SOM 神经网络基本结构,图 2 给出了结构中各输入神经元 与竞争层神经元 j 的连接情况。 m m ... ... m m 竞争层 竞争层 ... ... ... 1 ... j ... m 1 2 ... N 输入层 ... ... 1 i N 输入层 Ak (a1k , a2k ,..., a Nk ) Ak (a1k , a2k ,..., a Nk ) 图 1SOM 网络基本结构 图 2 输入神经元与竞争层神经元 j 的连接情况  设网络的输入模式为 k=1,2,…, Cp ;竞争层神经元向量为 Bj=(Linkage-Based)bj1,bj2,…,bjm) , j C =1,2,…,m;其中 Ak 为连续值, Bj 为数字量。网络的连接权为 {Awij} Ci=1,2,…,N; C j=1,2,…,M。  SOM 网络寻找与输入模式 Ak 最接近的连接权向量 Wg=(Linkage-Based)wg1,wg2,…,wgN) ,将该连接权向量 Wg 进一步朝与输入模式 Ak 接近的方向调整,而且还调整邻域内的各个连接权向量 Wj , jNg(Linkage-Based)t) 。随着学习次数的增加,邻域逐渐缩小。最终得到聚类结果。  SOM 类似于大脑的信息处理过程,对二维或三维数据的可视是非常有效的。 SOM 网络的最 大局限性是,当学习模式较少时,网络的聚类效果取决于输入模式的先后顺序;且网络 连接权向量的初始状态对网络的收敛性能有很大影响。 2018年11月22日11月22日22日 DMKD Sides By MAO 64

65. 第五章 聚类方法 内容提要  聚类方法概述  划分聚类方法  层次聚类方法  密度聚类方法  其它聚类方法 2018年11月22日11月22日22日 DMKD Sides By MAO 65

66. Thank you !!! 2018年11月22日11月22日22日 DMKD Sides By MAO 66