第二章聚类分析

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,模式识别,1,第二章 聚类分析,(Clustering Analysis),2.1,聚类分析的概念,2.2,模式相似性测度,2.3,类的定义与类间距离,2.4,聚类的算法,2,2.1,聚类分析的概念,一、聚类分析的基本思想,相似的归为一类。,模式相似性的度量和聚类算法。,无监督分类,（,Unsupervised,）,。,二、特征量的类型,物理量,-(,重量、长度、速度,),次序量,-(,等级、技能、学识,),名义量,-(,性别、状态、种类,),第二章 聚类分析,3,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,2,w,2,W,1,w,1,W,2,x,1,x,b,分类无效时的情况,1.,特征选取,不当,使分类无效。,第二章 聚类分析,4,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,分类无效时的情况,2.,特征选取,不足,可能使不同类别的模式判为一类。,2,w,2,W,1,w,1,W,2,x,1,x,3,w,3,W,第二章 聚类分析,5,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,分类无效时的情况,3.,特征选取,过多,可能无益反而有害,增加分析负担并使分析效果变差。,2,w,2,W,1,w,1,W,2,x,1,x,b,第二章 聚类分析,6,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,分类无效时的情况,4.,量纲选取不当。,第二章 聚类分析,7,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,分类无效时的情况,4.,量纲选取不当。,第二章 聚类分析,8,三、方法的有效性,取决于分类算法和特征点分布情况的匹配。,2.1,聚类分析的概念,分类无效时的情况,4.,量纲选取不当。,第二章 聚类分析,9,下列是一些动物的名称：,羊 （,sheep,）狗 （,dog,）,蓝鲨（,blue shark,）蜥蜴 （,lizard,）,毒蛇（,viper,）猫 （,cat,）,麻雀（,sparrow,）海鸥 （,seagull,）,金鱼（,gold fish,）绯鲵鲣（,red-mullet,）蛙 （,frog,）,要对这些动物进行分类，则不同的特征有不同的分法：,特征选取不同对聚类结果的影响,第二章 聚类分析,10,特征选取不同对聚类结果的影响,羊,狗,猫,蓝鲨,蜥蜴,毒蛇,麻雀,海鸥,金鱼,绯鲵鲣,青蛙,(a),按繁衍后代的方式分,哺乳动物,非哺乳动物,第二章 聚类分析,11,金鱼绯鲵鲣蓝鲨,羊,狗,猫,蜥蜴,毒蛇麻雀,海鸥 青蛙,(b),按,肺是否存在,分,无肺,有肺,特征选取不同对聚类结果的影响,第二章 聚类分析,12,青蛙,羊,狗,猫 蜥蜴,毒蛇麻雀,海鸥,金鱼绯鲵鲣 蓝鲨,(c),按,生活环境,分,陆地,水里,两栖,特征选取不同对聚类结果的影响,第二章 聚类分析,13,蓝鲨,金鱼绯鲵鲣,蜥蜴,毒蛇麻雀,海鸥 青蛙,羊,狗,猫,(d),按,繁衍后代方式和肺是否存在,分,非哺乳且有肺,哺乳且无肺,哺乳且有肺,非哺乳且无肺,特征选取不同对聚类结果的影响,第二章 聚类分析,14,距离测度不同,聚类结果也不同,数据的粗聚类是两类,细聚类为,4,类,第二章 聚类分析,15,综上可见,:,选择什么特征？,选择多少个特征？,选择什么样的量纲？,选择什么样的距离测度？,这些对分类结果都会产生极大影响。,第二章 聚类分析,16,聚类过程遵循的基本步骤,一、特征选择,(feature selection),尽可能多地包含任务关心的信息,二、近邻测度,(proximity measure),定量测定两特征如何“相似”或“不相似”,三、聚类准则（,clustering criterion,）,以蕴涵在数据集中类的类型为基础,四、聚类算法（,clustering algorithm,）,按近邻测度和聚类准则揭示数据集的聚类结构,五、结果验证（,validation of the results,）,常用逼近检验验证聚类结果的正确性,六、结果判定（,interpretation of the results,）,由专家用其他方法判定结果的正确性,17,聚类应用的四个基本方向,一、减少数据,许多时候，当数据量,N,很大时，会使数据处理变得很费力。因此可使用聚类分析的方法将数据分成几组可判断的聚类,m,（,mN,）来处理，每一个类可当作独立实体来对待。从这个角度看，数据被压缩了。,第二章 聚类分析,18,二、假说生成,在这种情况下，为了推导出数据性质的一些假说，对数据集进行聚类分析。因此，这里使用聚类作为建立假说的方法，然后用其他数据集验证这些假说。,聚类应用的四个基本方向,第二章 聚类分析,19,聚类应用的四个基本方向,三、假说检验,用聚类分析来验证指定假说的有效性。,例如：考虑这样的假说,“大公司在海外投资”,。,要验证这个假说是否正确，就要对大公司和有代表性的公司按规模、海外活跃度、成功完成项目的能力等进行聚类分析。从而来支持这个假说。,第二章 聚类分析,20,四、基于分组的预测,对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，对于一个未知模式，就可以用前面的聚类来确定是哪一类？,聚类应用的四个基本方向,例如：考虑被同种疾病感染的病人数据集。,先按聚类分析进行分类，然后对新的病人确定他适合的聚类，从而判断他病情。,第二章 聚类分析,21,2.2,模式相似性测度,用于描述各模式之间特征的相似程度,距 离 测 度,相 似 测 度,匹 配 测 度,第二章 聚类分析,22,2.2,模式相似性测度,一、距离测度,(,差值测度,),测度基础：,两个矢量矢端的距离,测度数值：,两矢量各相应分量之差的函数,。,时，等号成立；,，当且仅当,第二章 聚类分析,23,2.2,模式相似性测度,常用的距离测度有：,1.,欧氏,(Euclidean),距离,第二章 聚类分析,24,2.2,模式相似性测度,4.,明氏,(Minkowski),距离,(2-2-4),2.,绝对值距离,(,街坊距离或,Manhattan,距离,) (2-2-2),3.,切氏,(Chebyshev),距离,(2-2-3),第二章 聚类分析,25,2.2,模式相似性测度,第二章 聚类分析,26,2.2,模式相似性测度,5.,马氏,(Mahalanobis),距离,注意！,马氏距离对一切非奇异线性变换都是不变的，这说明它不受特征量纲选择的影响，并且是平移不变的。,上面的,V,的含义是这个矢量集的协方差阵的统计量，故马氏距离加入了对特征的相关性的考虑。,第二章 聚类分析,27,2.2,模式相似性测度,第二章 聚类分析,28,29,现金识别例子,(,欧氏平均距离,),数据样本介绍：,10,个文本文件,文件名：,rmb00.txt,rmb09.txt,每个文件有,4,个币种的数据，分别是：,100,圆、,50,圆、,20,圆、,10,圆,每个币种有新旧两种版本，,4,个方向，故有,8,个数据块：,如,100,圆的,8,个数据块：,data100a,data100b,data100c,data100d,老版,data100e,data100f,data100g,data100h,新版,每个数据块有,8,个传感器数据：,传感器,1,，传感器,2,，,，,传感器,8,每个传感器有,60,个采样数据：,数据,1,，数据,2,，,，数据,60,30,现金识别例子,Eucliden=15.000000,Manhattan=33.000000,Chebyshev=11.000000,Minkowski=11.039449,m=8,100,元,A,面第,1,个样本第,10,点和,20,点的距离,X:,(75, 76,101, 83,102, 96, 91, 82),Y:,(70, 74, 90, 76, 99, 96, 90, 86),X-Y:,5, 2, 11, 7, 3, 0, 1, -4,距离测度,rmbdis,31,现金识别例子,欧式平均距离,100a-100a:( 2.65,49.66) 24.41,100a-100b:(16.37,55.87) 33.97,100a-100c:( 3.87,58.34) 29.41,100a-100d:( 6.86,53.74) 33.04,100a-100e:( 3.87,62.12) 27.51,100a-100f:(13.60,67.61) 34.67,100a-100g:(11.40,68.56) 32.27,100a-100h:(11.27,68.61) 34.43,100a- 50a:(18.76,76.20) 40.72,100a- 20a:(13.23,81.28) 42.87,100a- 10a:(12.45,90.91) 54.99,32,现金识别例子,100,圆,A,面的马式矩阵,SW,为,:,43.5 53.9 64.8 52.7 52.7 52.3 46.8 37.9,53.9 132.0 137.5 107.8 59.6 74.0 52.1 31.5,64.8 137.5 165.9 124.1 74.6 84.1 67.6 37.1,52.7 107.8 124.1 105.5 57.5 67.2 54.5 35.2,52.7 59.6 74.6 57.5 76.2 71.7 65.8 57.9,52.3 74.0 84.1 67.2 71.7 73.1 62.8 55.0,46.8 52.1 67.6 54.5 65.8 62.8 59.6 51.9,37.9 31.5 37.1 35.2 57.9 55.0 51.9 54.7,33,现金识别例子,SW,的逆矩阵为,:,0.3 -0.0 0.1 -0.1 -0.1 -0.1 -0.2 0.2,-0.0 0.3 -0.1 -0.1 0.1 -0.6 0.3 0.2,0.1 -0.1 0.3 -0.1 -0.0 -0.2 -0.3 0.4,-0.1 -0.1 -0.1 0.2 0.1 0.3 -0.1 -0.2,-0.1 0.1 -0.0 0.1 0.7 -0.7 -0.4 0.2,-0.1 -0.6 -0.2 0.3 -0.7 2.2 -0.0 -1.0,-0.2 0.3 -0.3 -0.1 -0.4 -0.0 1.2 -0.5,0.2 0.2 0.4 -0.2 0.2 -1.0 -0.5 1.0,34,现金识别例子,马式平均距离,100a: ( 7.46, 80.05) 39.73,100b: (26.75, 179.86) 91.89,100c: (14.50, 231.44) 103.76,100d: (11.69, 155.28) 78.58,100e: ( 5.65,2968.84) 247.42,100f: (39.19,2191.91) 108.10,100g: (10.68,2875.99) 265.16,100h: ( 9.41,2673.54) 107.56,50a: (22.78, 221.07) 101.41,20a: (22.51, 343.26) 162.90,10a: (20.93, 975.67) 256.38,35,现金识别例子,马式平均距离,a: 39.73 101.41 162.90 256.38,b: 91.89 230.25 288.69 659.47,c: 103.76 135.94 257.57 724.96,d: 78.58 171.10 330.97 675.90,e: 247.42 443.46 333.93 218.71,f: 108.10 328.11 305.19 607.51,g: 265.16 956.58 818.83 348.42,h: 107.56 339.64 387.10 628.88,100,圆,50,圆,20,圆,10,圆,其中马式矩阵为,100,圆,A,面的，上面是各面到,100,圆,A,面的均值点的平均马式距离。,36,现金识别例子,100,圆,A,面的传感器,1,到其它各面传感器,1,的街坊距离,37,2.2,模式相似性测度,二、相似测度,测度基础：,以两矢量的方向是否相近作为考虑的基础,矢量长度并不不重要。设,1.,角度相似系数,(,夹角余弦,),(2-2-11),注意：坐标系的旋转和尺度的缩放是不变的,但对一般的线形变换和坐标系的平移不具有不变性。,38,现金识别例子,100,圆,A,面传感器,1,与其它各面的相似系数,39,2.2,模式相似性测度,二、相似测度,2.,相关系数,它实际上是数据中心化后的矢量夹角余弦。,(2-2-12),40,现金识别例子,100,圆,A,面传感器,1,与其它各面的相关系数,41,2.2,模式相似性测度,二、相似测度,3.,指数相似系数,(2-2-13),式中 为相应分量的协方差， 为矢量维数。它不受量纲变化的影响。,42,现金识别例子,100,圆,A,面传感器,1,与其它各面的相关系数,43,2.2,模式相似性测度,当特征只有两个状态（,0,，,1,）时，常用匹配测度。,0,表示无此特征,1,表示有此特征。故称之为,二值特征,。,对于给定的,x,和,y,中的某两个相应分量,x,i,与,y,j,若,x,i,=1,y,j,=1,，则称,x,i,与,y,j,是,(1-1),匹配,；,若,x,i,=1,y,j,=0,，则称,x,i,与,y,j,是,(1-0),匹配；若,x,i,=0,y,j,=1,，则称,x,i,与,y,j,是,(0-1),匹配；若,x,i,=0,y,j,=0,，则称,x,i,与,y,j,是,(0-0),匹配。,二、匹配测度,44,2.2,模式相似性测度,45,2.2,模式相似性测度,三、匹配测度,(1)Tanimoto,测度,46,例,2.2.2,可以看出，它等于,共同具有的特征数目,与分别具有的特征种类总数之比。这里只考虑,(1-1),匹配而不考虑,(0-0),匹配。,设,则,2.2,模式相似性测度,47,现金识别例子,100,圆,A,面与其它各面的匹配系数,Tanimoto,48,2.2,模式相似性测度,三、匹配测度,(2),Rao,测度,注：,(1-1),匹配特征数目和所选用的特征数目之比。,49,现金识别例子,100,圆,A,面与其它各面的匹配系数,Rao,50,2.2,模式相似性测度,三、匹配测度,(3),简单匹配系数,注：上式分子为,(1-1),匹配特征数目与,(0-0),匹配特征数目之和，分母为所考虑的特征数目。,51,现金识别例子,100,圆,A,面与其它各面的匹配系数,Simple,52,2.2,模式相似性测度,三、匹配测度,(4) Dice,系数,(5) Kulzinsky,系数,53,现金识别例子,100,圆,A,面与其它各面的匹配系数,dice,54,现金识别例子,100,圆,A,面与其它各面的匹配系数,Kulzinsky,55,作业,P44: 2.1, 2.3,56,23,类的定义与类间距离,2.3.1,类的定义,定义之,1,设集合,S,中任意元素,x,i,与,y,j,间的距离,d,ij,有,d,ij,h,其中,h,为给定的阀值，称,S,对于阀值,h,组成一类。,类的定义有很多种，类的划分具有人为规定性，这反,映在定义的选取及参数的选择上。一个分类结果的优劣最后只能根据实际来评价。,书中的其它定义方法请大家自行参考学习,57,23,类的定义与类间距离,2.3.2,类间距离测度方法, 最近距离法, 最远距离法, 中间距离法, 重心距离法, 平均距离法, 离差平方和法,58,23,类的定义与类间距离,2.3.2,类间距离测度方法,最近距离法, 最远距离法, 中间距离法, 重心距离法, 平均距离法, 离差平方和法,式中 表示 和 之间的距离。,59,现金识别例子,100,圆,A,面与其它各面的最小距离,60,23,类的定义与类间距离,2.3.2,类间距离测度方法, 最近距离法,最远距离法, 中间距离法, 重心距离法, 平均距离法, 离差平方和法,式中 表示 和,之间的距离。,61,现金识别例子,100,圆,A,面与其它各面的最大距离,62,23,类的定义与类间距离,2.3.2,类间距离测度方法, 最近距离法, 最远距离法,中间距离法, 重心距离法, 平均距离法, 离差平方和法,p,w,q,w,k,w,p,q,k,pq,D,kq,D,kl,D,kp,D,l,w,63,23,类的定义与类间距离,2.3.2,类间距离测度方法, 最近距离法, 最远距离法, 中间距离法,重心距离法, 平均距离法, 离差平方和法,n,p,n,q,分别为类,w,p,和,w,q,的样本个数,64,23,类的定义与类间距离,2.3.2,类间距离测度方法, 最近距离法, 最远距离法, 中间距离法, 重心距离法,平均距离法, 离差平方和法,65,现金识别例子,100,圆,A,面与其它各面的平均距离,66,23,类的定义与类间距离,2.3.2,类间距离测度方法, 最近距离法, 最远距离法, 中间距离法, 重心距离法, 平均距离法,离差平方和法,分别为对应类的重心,类内离差平方和,递推公式为,:,67,最近距离法,1/2,1/2,0,-1/2,最远距离法,1/2,1/2,0,1/2,中间距离法,1/2,1/2,-1/4,0,重心距离法,0,平均距离法,0,0,可变平均法,0,可变法,0,离差平方和法,0,68,23,类的定义与类间距离,2.3.3,聚类的准则函数,判别分类结果好坏的一般标准：,类内距离小，类间距离大。,某些算法需要一个能对分类过程或分类结果,的优劣进行评估的准则函数。如果聚类准则函数,选择得好，聚类质量就会高。聚类准则往往是和,类的定义有关的，是类的定义的某种体现。,69,2.3.3,聚类的准则函数,一、类内距离准则,设有待分类的模式集 在某种相似性测度基础上被划分为 类，,类内距离准则函数 定义为,:(,表示 类的模式均值矢量。,),(2-3-20),23,类的定义与类间距离,70,23,类的定义与类间距离,71,加权类内距离准则,:,(2-3-22),(2-3-23),式中，,表示,类内任两个模式距离,个组合数，所以,表示类内,表示,类先验概率的估计频率。,平方和，共有,两模式间的均方距离。,N,为待分类模式总数，,72,23,类的定义与类间距离,73,加权类间距离准则,:,对于两类问题，类间距离有时取,(2-3-26),和,的关系是,(2-3-27),(2-3-25),74,23,类的定义与类间距离,75,的类内离差阵定义为,(2-3-28),23,类的定义与类间距离,式中 为类 的模式均值矢量,(2-3-29),76,77,例,2.3 .1,证明：,23,类的定义与类间距离,78,聚类的基本目的是使 或,。利用线形代数有关矩阵的迹和行列式的性质,可以定义如下,4,个聚类的准则函数,:,23,类的定义与类间距离,79,23,类的定义与类间距离,由它们的构造可以看出，为得到好的聚类结果，应该使它们尽量的大。这类准则也大量用在特征提取和选择中。,80,23,类的定义与类间距离,J1= 7.60886 J2= 0.0010397,J3= 15.6089 J4= 62.9116,用纸币数据计算获得的结果：,81,作业,P44: 2.4, 2.5, 2.6,82,24,聚类的算法,2.4.1,聚类的技术方案,聚类分析有很多具体的算法,有的比较简单,有的相对复杂和完善,但归纳起来就是三大类,:,1,、按最小距离原则简单聚类方法,2,、按最小距离原则进行两类合并的方法,3,、依据准则函数动态聚类方法,83,24,聚类的算法,(1),简单聚类方法,针对具体问题确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，当大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离原则将其分划到某一类中。,这类算法运行中模式的类别及类的中心一旦确定将不会改变。,84,24,聚类的算法,首先视各模式自成一类,然后将距离最小的两类合并成一类,不断地重复这个过程，直到成为两类为止。,(2),按最小距离原则进行两类合并的方法,这类算法运行中，类心不断地修正，但模式类别一旦指定后就不再改变，就是模式一旦划为一类后就不再被分划开，这类算法也称为谱系聚类法。,85,24,聚类的算法,(3),依据准则函数动态聚类法,设定一些分类的控制参数，定义一个能表征聚类结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。,算法运行中，类心不断地修正，各模式的类别的指定也不断地更改。这类方法有,C,均值法、,ISODATA,法等。,86,24,聚类的算法,-,简单聚类方法,87,24,聚类的算法,-,简单聚类方法,88,24,聚类的算法,-,简单聚类方法,89,24,聚类的算法,-,简单聚类方法,这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。,算法特点,:,从算法的过程可以看出，该算法结果很大程度上依赖于距离门限,T,的选取及模式参与分类的次序。如果能有先验知识指导门限,T,的选取，通常可获得较合理的效果。也可考虑设置不同的,T,和选择不同的次序，最后选择较好的结果进行比较。,90,24,聚类的算法,-,简单聚类方法,简单聚类图例,91,例,2.4.1,：初始条件不同的简单聚类结果,初始中心不同,门限不同,样本顺序不同,1 2 3 4 5,1 2 3 4 5,1 2 3 4 5,1 2 3 4 5,10 9 8,10 9 8,8 7 6,8 7 6,11 6 7,11 6 7,9 10 11,9 10 11,92,24,聚类的算法,简单聚类法程序,simpleclustering,93,24,聚类的算法,最大最小距离法,94,24,聚类的算法,-,最大最小距离法, 算法原理步骤, 选任一模式特征矢量作为第一个聚类中心,例如，,。,作为第二个聚类中心,。, 从待分类矢量集中选距离,最远的特征矢量,95, 计算未被作为聚类中心的各模式特征矢量,与,、,之间的距离，并求出它们之中的最小值，,为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。,即,96,则相应的特征矢量,作为第三个聚类中心，,然后转至；否则，转至最后一步。, 若, 设存在,个聚类中心，计算未被作为聚类中心,并算出,如果,，则,否则，转至最后一步。,的各特征矢量到各聚类中心的距离,并转至；,97, 当判断出不再有新的聚类中心之后，将模式特,中去，即计算,当,，则判,。,征矢量,按最小距离原则分到各类,这种算法的聚类结果与参数,心的选取有关。如果没有先验知识指导,和,取，可适当调整,和,选取最合理的一种聚类。,以及第一个聚类中,的选,，比较多次试探分类结果，,98,24,聚类的算法,最大最小距离法,程序,maxminclustering,99,24,聚类的算法,层次聚类法,(Hierarchical Clustering Method)(,系统聚类法、 谱系聚类法）,按最小距离原则不断进行两类合并,2.4.3,谱系聚类法,100,24,聚类的算法,层次聚类法,(Hierarchical Clustering Method)(,系统聚类法、 谱系聚类法）,按最小距离原则不断进行两类合并, 算法思想,首先将,N,个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。,2.4.3,谱系聚类法,101,24,聚类的算法,2.4.3,谱系聚类法,102,24,聚类的算法,2.4.3,谱系聚类法,103,例,2.4.3,：如下图所示,1,、设全部样本分为,6,类，,2,、作,距离矩阵,D(0),3,、求最小元素：,4,、把,1,3,合并,7=(1,3),4,6,合并,8=(4,6),5,、作,距离矩阵,D(1),1,2,3,4,5,2,3,3,1,4,4,7,4,8,5,5,2,6,2,6,8,5,9,1,3,D(0),104,例,2.4.3,：如下图所示,1,、设全部样本分为,6,类，,2,、作,距离矩阵,D(0),3,、求最小元素：,4,、把,1,3,合并,7=(1,3),4,6,合并,8=(4,6),5,、作,距离矩阵,D(1),D(1),7,2,8,2,3,8,7,4,5,5,2,2,105,6,、若合并的类数没有达到要求，转,3,。否则停止。,3,、求最小元素：,4,、,8,5,2,合并, 9=,（,2,5,4,6,）,106,107,24,聚类的算法,谱系聚类法,程序,Hierarchical,clustering,108,24,聚类的算法,最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了。因此，这些方法效果一般不会太理想。,109,2.,确定评估聚类质量的准则函数。,确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢为,，协方差阵为,，则模式,和该类的,与该类均矢,的马氏距离：,距离平方为,3.,确定模式分划及聚类合并或分裂的规则。,24,聚类的算法,动态聚类算法要点,110,24,聚类的算法,动态聚类的基本步骤,建立初始聚类中心，进行初始聚类；,计算模式和类的距离，调整模式的类别；,计算各聚类的参数，删除、合并或分裂一些聚类；,从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止。,111,24,聚类的算法,动态聚类的框图,产生初始聚类中心,聚类,检验聚类合理性,待分类模式,分类结果,合理,再迭代,/,修改参数,不合理,112, 条件及约定,设待分类的模式特征矢量集为：,类的数目,C,是事先取定的。,24,聚类的算法,2.4.3,动态聚类法,C-,均值法, 算法思想,该方法,取定,C,个类别,和选取,C,个初始聚类中心,，,按最小距离原则将各模式分配到,C,类中的某一类，之后不断地,计算类心和调整各模式,的类别，最终使各模式到其判属类别中心的距离平方之和最小。,113,24,聚类的算法,2.4.3,动态聚类法,C-,均值法,114,24,聚类的算法,2.4.3,动态聚类法,C-,均值法,115,选代表点,初始分类,分类合理否,4.,动态聚类框图,24,聚类的算法,2.4.3,动态聚类法,C-,均值法,最终分类,Y,修改分类,N,116,例,2.4.2,使用聚类算法实现图像分割,在散射图上形成了两个聚类，利用模式识别的方法将其分开，就实现了图象的分割。,117,例,2.4.3,：,已知有,20,个样本，每个样本有,2,个特征，数据分布,如下图,使用,C,均值法实现样本分类（,C=2,）。,第一步,：令,C=2,，选初始聚类中心为,样本序号,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,x,9,x,10,特征,x,1,0,1,0,1,2,1,2,3,6,7,特征,x,2,0,0,1,1,1,2,2,2,6,6,x,11,x,12,x,13,x,14,x,15,x,16,x,17,x,18,x,19,x,20,8,6,7,8,9,7,8,9,8,9,6,7,7,7,7,8,8,8,9,9,118,119,0,0,第二步,：,0,0,0,）,）（,（,-,1,0,1,0,0,）,）（,（,-,1,0,0,0,1,）,）（,（,-,所以,因为,-,-,所以,因为,同理,1,2,2,1,=,-,-,=,-,-,.,.,20,6,5,20,6,5,都属于,、,、,离计算出来，判断,与第二个聚类中心的距,、,、,同样把所有,因此分为两类：,),.,(,),1,(,),(,),1,(,20,5,4,2,2,3,1,1,=,=,18,2,2,1,=,=,N,N,G,G,二、,一、,121,122,123,第三步：,更新聚类中心,124,125,第四步：,第二步：,第三步,：更新聚类中心,126,127,clustering,24,聚类的算法,2.4.3,动态聚类法,C-,均值法程序,128,作业,P45: 2.7, 2.8,129,24,聚类的算法,2.4.3,动态聚类法,C-,均值法,关于,C-,均值法收敛性的分析,130,24,聚类的算法,2.4.3,动态聚类法,C-,均值法,当模式分布呈现类内团聚状，,C-,均值算法是能达到很好的聚类结果，故应用较多。从算法的迭代过程看，,C-,均值算法,是能使各模式到其所判属的类别中心,距离,(,平方,),之和为最小,的最佳聚类。,131,24,聚类的算法,2.4.3,动态聚类法,C-,均值法的改进,在类别数未知的情况下，可使类数,C,由较小值逐步增加，对于每个选定的,C,分别使用该算法。显然准则函数,J,是随,C,的增加而单调减少。,C,的调整,作一条,C,一,J,曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。,在增加过程中，总会出现使本来较密集的类再拆开的情况，此时,J,虽减小，但减小速度将变缓。如果作一条,C,一,J,曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。然而在许多情况下，曲线并无明显的这样的点。,132,24,聚类的算法,2.4.3,动态聚类法,C-,均值法的改进,初始聚类中心的选取, 凭经验选择初始类心。, 将模式随机地分成,C,类，计算每类中心，以其作为初始类心。, （,最大密度,），求以每个特征点为球心、某一正数,d,0,为半径的球形域中特征点个数，这个数称为该点的,密度,。选取密度最大的特征点作为第一个初始类心,Z,1,，然后在与,Z,1,大于某个距离,d,的那些特征点中选取具有,“最大”密度,的特征点作为第二个初始类心,Z,2,，如此进行，选取,C,个初始聚类中心。,133,24,聚类的算法,2.4.3,动态聚类法,C-,均值法的改进,初始聚类中心的选取,用相距最远的,C,个特征点作为初始类心。具体地讲，是按前述的最大最小距离算法求取,C,个初始聚类中心。,当,N,较大时，先随机地从,N,个模式中取出一部分模式用谱系聚类法聚成,C,类，以每类的重心作为初始类心。, 设已标准化的待分类模式集为,希望将它们分为,C,类。,134, 设已标准化的待分类模式集为,希望将它们分为,C,类。,设,:,计算,:,显然,0,a,i,C,，若,a,i,最接近整数,j,，则把,x,i,分划至中,w,j,。对所有样本都实行上述处理，就可实现初始分类，从而产生初始聚类中心。,135,24,聚类的算法,2.4.3,动态聚类法,C-,均值法的改进, 用类核代替类心,前面的算法存在一个不足，即只用一个聚类中心点作为一类的代表，但一个点往往不能充分地反映该类的模式分布结构，从而损失了很多有用的信息。,当类的分布不是球状或近似球状时，这种算法很难有较好的效果。,此时，可用类核代替类心，类核,可以是一个函数、一个点集或其他适当的模型。,比如前面我们讲过的,马式距离,。,136,(3),动态聚类法,ISODATA,算法,(Iterative Self-Organizing Data Analysis Techniques Algorithm,迭代自组织数据分析,),特点：,启发性推理、分析监督、控制聚类结构及人机交互。,算法思想：,在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。,137,ISODATA,算法原理步骤, 预置, 设定聚类分析控制参数：,=,预期的类数，,=,每一类中允许的最少模式数目，,=,初始聚类中心个数,(,可以不等于,c),，,=,类内各分量分布的距离标准差上界，,(,分裂用,),=,两类中心间的最小距离下界，,(,合并用,),=,在每次迭代中可以合并的类的最多对数，,=,允许的最多迭代次数。,138,ISODATA,算法原理步骤,139,ISODATA,算法原理步骤,140,ISODATA,算法原理步骤, 计算各类的中心, 计算分类后的参数,:,各类中心、类内平均距离及总体平均距离。, 计算各类中模式到类心的平均距离, 计算各个模式到其类内中心的总体平均距离,141,ISODATA,算法原理步骤,142,ISODATA,算法原理步骤, 计算各类类内距离的标准差矢量,式中， 为分量编号， 为类的编号， 为矢量维数，,是 的第 个分量， 是 的第 个分量。,143,ISODATA,算法原理步骤,144,ISODATA,算法原理步骤,145,ISODATA,算法原理步骤,146,ISODATA,算法原理步骤,147,148,ISODATA,算法举例,(,二维,),(1),初始值设定,:,类间距离上限,距离标准差上界,最少模式数目,合并的类的最多对数,149,ISODATA,算法举例,(2),聚类,(,只有一个中心,):,150,ISODATA,算法举例,(3),因,无合并,:,(4),计算聚类中心、类内平均距离和总的平均距离。,151,ISODATA,算法举例,(5),因不是最后一步迭代，且 ，转至,(6),求 的标准差矢量,152,ISODATA,算法举例,(7),算得,(6),因,且 将 分裂成,两类，取 ，,则,且 转,(2),153,ISODATA,算法举例,(2),聚类,(,两个中心,):,(3),因,无合并,:,154,ISODATA,算法举例,(4),计算聚类中心、类内平均距离和总的平均距离。,(5),因这是偶次迭代，满足算法原理步骤中,的条件，故转,155,ISODATA,算法举例,(9),计算类间距离,由 ，类不能合并。,(11),因不是最后一,次迭代,(,，题设,),， ，判断是否修改参数。由上面结果可知，已获得所要求类别数目，类间距离大于类内距离，每类样本数都有样本总数的足够大的百分比，因此不改变参数。,156,(2),(4),计算结果与前一次迭代结果相同。,(7),分裂条件不满足，转至。,，无新的变化， ，转至。,(6),计算 和 的标准差矢量,(5),没有任一种情况被满足，到。,与前一次迭代结果相同，,无合并发生。,157, 与前一次迭代结果相同。, 因是最后一次迭代，令 ，转至。, ，同前。, 因 ，无合并发生。, 因是最后一次迭代,结束。,158,Start,输入样本数据，置,c; N,c,;,选初始类心,z,j,，,j=1,2,.N,c,(1),置控制参数：,n,s,D, L , I,(3),合并判决：,n,j,s,),(d,j,d),(n,j,2(,n,+1),N,c,c/2,(6),计算各类类内距离的标准差矢量,(7),找出最大分量,(10),合并处理,(11),结束判决：,I,p, I,(9),计算各类对类间距离,N,End,Y,N,c,= N,c,+ 1,I,p,= I,p,+ 1,(8),分裂处理,Y,N,Y,转修改参数,修改,参数否,转重新聚类,N,161,Start,输入样本数据，置,c; N,c,;,选初始类心,z,j,，,j=1,2,.N,c,(1),置控制参数：,n,s,D, L , I,(2),聚类：,if d,il,= minD(x,i, z,1,), D(x,i, z,2,), D(x,i, z,Nc,) then x,i,l,(3),合并判决：,n,j,n,N,Y,N,c,= N,c,- 1,(4),计算分类后的参数：类心,z,j,; ,类内平均距离,d,j,;,总类内平均距离,d,修改参数入口,重新聚类,入口,162,作业,P45: 2.9, 2.10,163,