模式识别 第二章 聚类分析.ppt

《模式识别 第二章 聚类分析.ppt》由会员分享，可在线阅读，更多相关《模式识别 第二章 聚类分析.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1模式识别模式识别第二章第二章 聚类分析聚类分析2 22.1 2.1 聚类的基本概念聚类的基本概念2.1.12.1.1聚类分析的基本思想聚类分析的基本思想 Clustering AnalysisClustering Analysis据据相似程度相似程度分类分类无监督分类无监督分类（Unsupervised）似圆度似圆度3 32.1 2.1 聚类的基本概念聚类的基本概念2.1.22.1.2 特征量的类型特征量的类型物理量物理量：直接反映特征的实际物理意义直接反映特征的实际物理意义如如:长度、重量、速度等。处理前需要离散化。长度、重量、速度等。处理前需要离散化。次序量次序量：按某种规则确定的只

2、反映特征的次序按某种规则确定的只反映特征的次序 关系或等级关系或等级如如:产品的等级、病症的级或期。已是离散量。产品的等级、病症的级或期。已是离散量。名义量名义量：反映样本的状态特征非数值的，反映样本的状态特征非数值的，如男性与女性、事物的状态、种类等。需要数值化。如男性与女性、事物的状态、种类等。需要数值化。这些特征的数值指标既无数量含义，也无次序关系，这些特征的数值指标既无数量含义，也无次序关系，只是用数字代表各种状态。只是用数字代表各种状态。4 4取决于分类算法和特征点分布情况的匹配。取决于分类算法和特征点分布情况的匹配。2w2W1w1W2x1xb1.1.特征选取特征选取不当不当使分类无

3、效。使分类无效。2.1 2.1 聚类的基本概念聚类的基本概念2.1.3 方法的有效性方法的有效性2w2W1w1W2x1x3w3W2.2.特征选取特征选取不足不足可能使不同可能使不同类别的模式判为一类。类别的模式判为一类。5 5取决于分类算法和特征点分布情况的匹配。取决于分类算法和特征点分布情况的匹配。2.1 2.1 聚类的基本概念聚类的基本概念2.1.3 方法的有效性方法的有效性2w2W1w1W2x1xb3.3.特征选取特征选取过多过多可能无益反而有害可能无益反而有害,增加分析负担并使分析效果变差。增加分析负担并使分析效果变差。4.4.量纲选取不当。量纲选取不当。6 62.1.42.1.4聚类

4、准则对聚类结果的影响聚类准则对聚类结果的影响羊羊,狗狗,猫猫,鲨鱼鲨鱼蜥蜴蜥蜴,蛇蛇,麻雀，海鸥麻雀，海鸥,金鱼金鱼,青蛙青蛙(a)(a)繁衍后代的方式繁衍后代的方式金鱼金鱼,鲨鱼鲨鱼羊羊,狗狗,猫猫,蜥蜥蜴蜴,蛇蛇,麻雀，麻雀，海鸥海鸥,青蛙青蛙(b)(b)肺的存在肺的存在金鱼金鱼,鲨鱼鲨鱼羊羊,狗狗,猫猫,蜥蜴蜥蜴,蛇蛇,麻麻雀，海鸥雀，海鸥,青蛙青蛙(c)(c)生存环境生存环境金鱼金鱼蜥蜴蜥蜴,蛇蛇,麻雀，海麻雀，海鸥鸥,青蛙青蛙(d)(d)繁衍后代的方式和是否存在肺繁衍后代的方式和是否存在肺鲨鱼鲨鱼羊羊,狗狗,猫猫,2.1 2.1 聚类的基本概念聚类的基本概念7 72.1.52.1.5

5、 距离测度距离测度对聚类结果的影响对聚类结果的影响2.1 2.1 聚类的基本概念聚类的基本概念数据的粗聚类是两类数据的粗聚类是两类,细聚类为细聚类为4 4类类8 82.2 2.2 模式相似性测度模式相似性测度2.2.12.2.1 距距 离离 测测 度度2.2.22.2.2 相相 似似 测测 度度2.2.32.2.3 匹匹 配配 测测 度度9 92.2.12.2.1 距离测度距离测度(差值测度差值测度)Distance(or Dissimilarity)MeasureDistance(or Dissimilarity)Measure设特征矢量设特征矢量 和和 的距离为的距离为则则 一般应满足如下

6、公理一般应满足如下公理(1)(2)(3)(triangular inequality)1010（一）距离测度（一）距离测度(差值测度差值测度)欧氏欧氏(Euclidean)(Euclidean)距离距离 绝对值距离绝对值距离(街坊距离或街坊距离或ManhattanManhattan距离距离)(3)(3)切氏切氏(ChebyshevChebyshev)距离距离1111（一）距离测度（一）距离测度(差值测度差值测度)(4)(4)明氏明氏(MinkowskiMinkowski)距离距离(5)(5)CamberaCambera距离距离(Lance(Lance距离、距离、WillimsWillims距离

7、距离)该距离能克服量纲的影响，该距离能克服量纲的影响，但不能克服分量间的相关性。但不能克服分量间的相关性。1212（一）距离测度（一）距离测度(差值测度差值测度)(6)(6)马氏马氏(MahalanobisMahalanobis)距离距离其中其中（协协方方差差矩矩阵阵的的无偏估计）无偏估计）（均值向量的估计）（均值向量的估计）性性质质：对对一一切切非非奇奇异异线线性性变变换换都都是是不不变变的的。即即，具具有有坐坐标标系系比比例例、旋旋转转、平平移移不不变变性性，并且从统计意义上尽量去掉了分量间的相关性。并且从统计意义上尽量去掉了分量间的相关性。1313马氏距离具有线性变换不变性马氏距离具有线

8、性变换不变性证明：证明：设，有非奇异线性变换：设，有非奇异线性变换：则则1414故故1515马氏距离的一般定义马氏距离的一般定义设设 、是从期望矢量为是从期望矢量为 、协方差矩阵协方差矩阵为为 的母体的母体G G中抽取的两个样本，则它们间的马氏距离定义为中抽取的两个样本，则它们间的马氏距离定义为 当当 和和 是分别来自两个数据集中的样本时，设是分别来自两个数据集中的样本时，设C C是它们的是它们的互协方差阵互协方差阵，则它们间的马氏距离定义为，则它们间的马氏距离定义为当当、V V、C C为单位矩阵时，马氏距离为单位矩阵时，马氏距离欧氏距离。欧氏距离。对于正态分布，等概率密度点轨迹是到均值矢量的

9、对于正态分布，等概率密度点轨迹是到均值矢量的马氏距离为常数的点所构成的超椭球面。马氏距离为常数的点所构成的超椭球面。1616例2.1求点求点 和和 至均值点至均值点 的距离。的距离。解：解：由题设，可得由题设，可得从而马氏距离从而马氏距离它们之比达它们之比达 倍。若用欧氏距离，则算得的距离值相同：倍。若用欧氏距离，则算得的距离值相同：由分布函数知，由分布函数知，A A、B B两点的概率密度分别为两点的概率密度分别为已知一个二维正态母体已知一个二维正态母体G G的分布为的分布为17172.2.22.2.2 相相 似似 测测 度度重点考虑重点考虑两矢量的方向两矢量的方向是否相近，而忽略矢量长度。是

10、否相近，而忽略矢量长度。(1)(1)角度相似系数角度相似系数(夹角余弦）夹角余弦）矢量之间的相似性可用它们的夹角余弦来度量矢量之间的相似性可用它们的夹角余弦来度量(2)(2)相关系数相关系数数据中心化后的矢量夹角余弦数据中心化后的矢量夹角余弦性质：性质：相关系数具有坐标系相关系数具有坐标系平移、旋转、比例不变性。平移、旋转、比例不变性。1818相关系数具有坐标系平移、旋转、比例变换不变性证明：证明：（作业）（作业）设，有旋转、平移变换：设，有旋转、平移变换：其中，其中，R R是旋转变换矩阵（即正交矩阵），是旋转变换矩阵（即正交矩阵），是平移矢量。是平移矢量。则有则有1919性质：不受量纲变化的

11、影响。性质：不受量纲变化的影响。(3)(3)指数相关系数指数相关系数这里假设这里假设 和和 的维数的维数n n相同、概率分布相同。相同、概率分布相同。是第是第i i个分量的方差。个分量的方差。2020（三）（三）匹匹 配配 测测 度度若特征只有两个状态：若特征只有两个状态：0=0=有此特征；有此特征；1=1=无此特征。称之为二值特征。无此特征。称之为二值特征。对于给定的二值特征矢量对于给定的二值特征矢量x x和和y y中的某两个相对应的分中的某两个相对应的分量量x xi i与与y yj j若若x xi i=1,=1,y yj j=1 1，则称，则称 x xi i与与y yj j (1-1)(1

12、-1)匹配；匹配；若若x xi i=1,=1,y yj j=0=0 ，则称，则称 (1-0)(1-0)匹配；匹配；若若x xi i=0,=0,y yj j=1 1，则称，则称(0-1)(0-1)匹配；匹配；若若x xi i=0,=0,y yj j=0=0 ，则称，则称(0-0)(0-0)匹配。匹配。对于二值对于二值n n维特征矢量可定义如下相似性测度：维特征矢量可定义如下相似性测度：2121（三）（三）匹匹 配配 测测 度度(1)(1)TanimotoTanimoto测度测度(1-1)(1-1)匹配的特征数目匹配的特征数目(0-1)(0-1)匹配的特征数目匹配的特征数目(1-0)(1-0)匹配

13、的特征数目匹配的特征数目(0-0)(0-0)匹配的特征数目匹配的特征数目令令注意，这里只考虑（注意，这里只考虑（1-11-1）匹配，而不考虑（）匹配，而不考虑（0-00-0）匹配。）匹配。2222（三）（三）匹匹 配配 测测 度度(2)(2)RaoRao测度测度(3)(3)简单匹配系数简单匹配系数(4)Dice(4)Dice系数系数(5)(5)KulzinskyKulzinsky系数系数（1-1）匹配特征数目与特征总数之比）匹配特征数目与特征总数之比（1-1）匹配）匹配+（0-0）匹配）匹配/特征总数特征总数只对（只对（1-1）匹配加权）匹配加权（1-1）匹配）匹配/（1-0）匹配）匹配+（0

14、-1）匹配）匹配2323例 2.2 设设(1)(1)TanimotoTanimoto测度测度(2)(2)RaoRao测度测度(3)(3)简单匹配测度简单匹配测度(4)Dice(4)Dice系数系数(5)(5)KulzinskyKulzinsky系数系数则2424一、影响分类的因数（1 1）分类准则；（）分类准则；（2 2）特征量的选择；（）特征量的选择；（3 3）量纲。）量纲。二、模式相似性测度（一）距 离 测 度(1)(1)欧氏距离欧氏距离(2)(2)马氏距离马氏距离对坐标系平移、旋转、比例不变。对坐标系平移、旋转、比例不变。（二）相 似 测 度相关系数相关系数 （特征矢量的方向）（特征矢量

15、的方向）对坐标系平移、旋转、比例不变对坐标系平移、旋转、比例不变。（三）匹 配 测 度（0-10-1）匹配系数）匹配系数小结25252.3 2.3 类的定义与类间距离类的定义与类间距离2.3.1 2.3.1 类的定义类的定义类的划分具有人为规定性，这反映在类的定义的类的划分具有人为规定性，这反映在类的定义的选取及参数的选择上。选取及参数的选择上。分类结果的优劣最后只能根据实际来评价。分类结果的优劣最后只能根据实际来评价。定义定义1 1 设集合设集合S S中任意元素中任意元素x xi i与与x xj j间的距离间的距离d dijij有有d dijij h h其中其中h h为给定的阈值，称为给定的

16、阈值，称S S对于阈值对于阈值h h组成一类。组成一类。定义定义2 2 其中其中k k为为S S中元素的个数。（类内平均距离）中元素的个数。（类内平均距离）2626定义定义5 5 若将集合若将集合S S任意分成两类任意分成两类S S1 1，S S2 2，这两类间的，这两类间的 距离距离D(SD(S1 1,S,S2 2)h h，则称，则称S S对于阈值对于阈值h h组成一类。组成一类。2.3.1 2.3.1 类的定义类的定义定义定义3 3 设集合设集合S S中任意元素中任意元素x xi i与与x xj j间的距离间的距离d dijij有有其中其中k k为为S S中元素的个数，称中元素的个数，称S

17、 S对于阈值对于阈值h h,r r组成一类。组成一类。定义定义4 4 x xi i S S ，x xj j S S，使，使d dijij h h成立，则称成立，则称S S对于对于 阈值阈值h h组成一类。（最近距离）组成一类。（最近距离）27272.3.2 类间距离测度类间距离测度（一）最近距离（一）最近距离两个聚类两个聚类 k k和和 l l之间的最近距离定义为之间的最近距离定义为式中，式中，d dijij表示表示 x xi i k k与与x xj j l l间的距离。间的距离。如果如果 l l由由 p p和和 q q两类合并而成，则有递推公式两类合并而成，则有递推公式28282.3.2 类

18、间距离测度类间距离测度（二）最远距离（二）最远距离递推公式递推公式2929（三）中间距离（三）中间距离递推公式递推公式2.3.2 类间距离测度类间距离测度30302.3.2 类间距离测度类间距离测度（四）重心距离（四）重心距离递推公式递推公式式中式中 ，和和 分别是分别是 i i和和 j j的的重心，重心，i,ji,j=k,l,p,qk,l,p,q 。31312.3.2 类间距离测度类间距离测度（五）（五）平均距离平均距离两类两类 p p和和 q q间的距离平方定义为这两类元素两两间的距离平方定义为这两类元素两两之间的平均平方距离，即之间的平均平方距离，即设设 l l=p p q q ，类平均

19、距离的递推公式为，类平均距离的递推公式为32322.3.2 类间距离测度类间距离测度（六）（六）离差平方和法离差平方和法设类设类 t t的重心是的重心是 ，t t的类内离差平方和定义为的类内离差平方和定义为设设 l l=p p q q ，则，则s sl l要变大。把两类合并所增加的离差平方要变大。把两类合并所增加的离差平方和定义为两类平方距离，即和定义为两类平方距离，即 ，可以证明，可以证明 k k与与 l l=p p q q的离差平方和的递推公式的离差平方和的递推公式3333类间距离递推公式类间距离递推公式（其中其中 l=p q ）p q 最近距离最近距离1/21/20-1/2最远距离最远距

20、离1/21/201/2中间距离中间距离1/21/2-1/40重心距离重心距离np/(np+nq)nq/(np+nq)-p q0平均距离平均距离np/(np+nq)nq/(np+nq)00可变平均可变平均距离距离(1-)np/(np+nq)(1-)nq/(np+nq)10可变距离可变距离(1-)/2(1-)/210离差平方和离差平方和(nk+np)/(nk+nl)(nk+nq)/(nk+nl)-nk/(nk+nl)034342.3.3 2.3.3 聚类准则函数聚类准则函数评估分类过程或分类结果优劣的准则函数评估分类过程或分类结果优劣的准则函数（一）类内距离准则（一）类内距离准则（误差平方和准则）

21、（误差平方和准则）式中，式中，nj是是 j中的样本个数，中的样本个数，加权类内距离准则加权类内距离准则式中，式中，是是 j内样本间的均方距离。内样本间的均方距离。适用于各类模式呈适用于各类模式呈团状分布团状分布的情况的情况。35352.3.3 2.3.3 聚类准则函数聚类准则函数（二）类间距离准则（二）类间距离准则式中，式中，是总是总的样本均值矢的样本均值矢量，量，加权类间距离准则加权类间距离准则对于两类问题对于两类问题，可以定义，可以定义3636（三）基于类内类间距离的准则函数（三）基于类内类间距离的准则函数构造能同时使构造能同时使J Jw wminmin和和J JB Bmaxmax的准则函

22、数的准则函数类内离差矩阵（类内离差矩阵（Scatter MatrixScatter Matrix）总的类内离差矩阵总的类内离差矩阵总的离差矩阵总的离差矩阵 1 3 4 5 2类间离差矩阵类间离差矩阵3737ST=SW+SB （作业作业）证明：证明：3838 妈妈新开了个淘宝店，欢迎前来捧场妈妈新开了个淘宝店，欢迎前来捧场妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，但生意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没但生意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没有人气，所以我也来

23、出自己的一份力，帮忙宣传一下。有人气，所以我也来出自己的一份力，帮忙宣传一下。并且妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。并且妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。欢迎大家来逛逛欢迎大家来逛逛【扬州五亭龙玩具总动员扬州五亭龙玩具总动员】个人小广告：个人小广告：3939（三）基于类内类间距离的准则函数（三）基于类内类间距离的准则函数聚类的基本目标是使聚类的基本目标是使 J JWBWB=TrTrS SB B maxmax和和J JWWWW

24、=TrTrS SW W minmin因此可定义如下聚类准则函数因此可定义如下聚类准则函数Jimax，(i=1,2,3,4)即，即，类内越类内越“紧紧”，类间越，类间越“开开”，聚类效果越好。，聚类效果越好。%该函数用于显示二维正态分布的函数图该函数用于显示二维正态分布的函数图clear;%X1和和X2分别为两个向量分别为两个向量X1=-5:0.1:5;X2=-5:0.1:5;%Miu为均值向量为均值向量Miu=1,1;%E为协方差矩阵为协方差矩阵E=3 0.0;0.0 1.0;%y为求得的函数值为求得的函数值for i=1:length(X1)for j=1:length(X2)x=X1(i)

25、,X2(j);y(i,j)=exp(-0.5*(x-Miu)*inv(E)*(x-Miu);y(i,j)=y(i,j)/(2*pi)*sqrt(det(E);endend%显示函数值显示函数值meshc(X1,X2,y);41412 24 4 聚类的算法聚类的算法(1)(1)简单聚类方法简单聚类方法 算法运行中，两类合并为一类，不断重复进行。也称算法运行中，两类合并为一类，不断重复进行。也称为谱系聚类法。为谱系聚类法。(2)(2)层次聚类法层次聚类法(3)(3)动态聚类法动态聚类法算法运行中，类心不断地修正，各模式的类别的指定算法运行中，类心不断地修正，各模式的类别的指定也不断地更改。这类方法

26、有也不断地更改。这类方法有C C均值法、均值法、ISODATAISODATA法等。法等。算法运行中模式的类别及类的中心一旦确定将不会改算法运行中模式的类别及类的中心一旦确定将不会改变。变。42422 24 4 聚类的算法聚类的算法-简单聚类方法简单聚类方法 根据相似性阈值和最小距离原则根据相似性阈值和最小距离原则 条件及约定条件及约定 设待分类的模式为设待分类的模式为 ,选定类内选定类内距离门限距离门限 。算法思想算法思想 计算模式特征矢量到聚类中心的距离并和门限计算模式特征矢量到聚类中心的距离并和门限 比较，决定归属该类或作为新的一类中心。这种算法通比较，决定归属该类或作为新的一类中心。这种

27、算法通常选择欧氏距离。常选择欧氏距离。43432 24 4 聚类的算法聚类的算法-简单聚类方法简单聚类方法 算法原理步骤算法原理步骤 取任意的一个模式特征矢量作为第一个聚类中心。例取任意的一个模式特征矢量作为第一个聚类中心。例如，令如，令 类的中心类的中心 。计算下一个模式特征矢量计算下一个模式特征矢量 到到 的距的距离离 。若。若 ，则建立新的一类则建立新的一类 ,其中心其中心 。若。若 ，则则 。44442 24 4 聚类的算法聚类的算法-简单聚类方法简单聚类方法 算法原理步骤算法原理步骤 假设已有聚类中心假设已有聚类中心 ，计算尚未确定类别，计算尚未确定类别的模式特征矢量的模式特征矢量

28、到各聚类中心到各聚类中心 的距离的距离 。如果。如果 ,则则 作为新的一类作为新的一类 的中心，的中心，；否则，如果否则，如果 ,则指判则指判 。检查是否所。检查是否所有的模式都分划完类别，如果都分划完了则结束；否则返有的模式都分划完类别，如果都分划完了则结束；否则返到到。45452 24 4 聚类的算法聚类的算法-简单聚类方法简单聚类方法 这类算法的突出优点是算法简单。但聚类过程这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。类后也不再改变。从算法的过程可以看出，该算法结果很大程度从算法的过程可以

29、看出，该算法结果很大程度上依赖于距离门限上依赖于距离门限T T的选取及模式参与分类的次序。的选取及模式参与分类的次序。如果能有先验知识指导门限如果能有先验知识指导门限T T的选取，通常可获得较的选取，通常可获得较合理的效果。也可考虑设置不同的合理的效果。也可考虑设置不同的T T和选择不同的次和选择不同的次序，最后选择较好的结果进行比较。序，最后选择较好的结果进行比较。算法特点算法特点:4646简单聚类图简单聚类图例例2 24 4 聚类的算法聚类的算法-简单聚类方法简单聚类方法 4747例例2.4.12.4.1：初始条件不同的简单聚类结果：初始条件不同的简单聚类结果初始初始中心中心不同不同门门限

30、限不不同同样本样本顺序顺序不同不同 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 114848层次聚类法层次聚类法(Hierarchical Clustering Method)(Hierarchical Clustering Method)(系统聚类法系统聚类法、谱系聚类法谱系聚类法）条件及约定条件及约定 设待分类的模式特征矢量为设待分类的模式特征矢量为 ，表示表示第第 次合并时的第次合并时的第 类。类。算法思想算法思想 首先将首先将 N N 个模式视作

31、各自成为一类，然后计算类与类之个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新间的距离，选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离，再将距离最近的两类合并，的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。直至所有模式聚成两类为止。按最小距离原则不断进行两类合并按最小距离原则不断进行两类合并2 24 4 聚类的算法聚类的算法层次聚类法层次聚类法 4949 3.3.算法原理步骤算法原理步骤(1)(1)初始分类。令初始分类。令 ，每个模式自成一类，即，每个模式自成一类，即 (2)2)计算各类间的距离计

32、算各类间的距离 ，由此生成一个对称的距离，由此生成一个对称的距离 矩阵矩阵 ，为类的个数（初始时为类的个数（初始时 ）。）。2 24 4 聚类的算法聚类的算法层次聚类法层次聚类法 5050 找出前一步求得的矩阵找出前一步求得的矩阵 中的最小元素，设它中的最小元素，设它是是 和和 间的距离，将间的距离，将 和和 两类合并两类合并成一类，于是产生新的聚类成一类，于是产生新的聚类 令令 检查类的个数。如果类数检查类的个数。如果类数 大于大于2 2，转至，转至；否；否则，停止。则，停止。3.3.算法原理步骤算法原理步骤2 24 4 聚类的算法聚类的算法层次聚类法层次聚类法 5151例2.4.3：如下图

33、所示 1、设全部样本分为6类，2、作距离矩阵D(0)3、求最小元素：4、把1,3合并7=(1,3)4,6合并8=(4,6)5、作距离矩阵D(1)1234523314474855262685913D(0)5252例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)72823874552253536 6、若合并的类数没有达到要求，转、若合并的类数没有达到要求，转3 3。否则停止。否则停止。3 3、求最小元素：、求最小元素：4 4、8,5,28,5,2合并合并,9=,9=（2,5,

34、4,62,5,4,6）54545555C-C-均值法均值法 条件及约定条件及约定 设待分类的模式特征矢量集为设待分类的模式特征矢量集为 ，类的，类的数目数目C C是事先取定的。是事先取定的。算法思想算法思想 该方法该方法取定取定 C C个类别个类别和和选取选取 C C个初始聚类中心，个初始聚类中心，按最小按最小距离原则将各模式分配到距离原则将各模式分配到 C C类中的某一类，之后不断地类中的某一类，之后不断地计算计算类心和调整各模式类心和调整各模式的类别，最终使各模式到其判属类别中心的类别，最终使各模式到其判属类别中心的距离平方之和最小。的距离平方之和最小。依据准则函数依据准则函数2 24 4

35、 聚类的算法聚类的算法动态聚类法动态聚类法 5656 算法原理步骤算法原理步骤 任选任选C C个模式特征矢量作为初始聚类中心：个模式特征矢量作为初始聚类中心：,令令 。将待分类的模式特征矢量集将待分类的模式特征矢量集 中的模式逐个按中的模式逐个按最小距离原则分划给最小距离原则分划给C C类中的某一类，即类中的某一类，即:如果如果 则则 ,式中式中 表示表示 和和 的中心的中心 的距离，上角标的距离，上角标表示迭代次数。于是产生新聚类表示迭代次数。于是产生新聚类 。2 24 4 聚类的算法聚类的算法动态聚类法动态聚类法 5757(4)(4)如果如果 ,则则结束结束,否则否则 ,转至转至(2)(2

36、)。(3)(3)计算重新分类后的各类心计算重新分类后的各类心 式中式中 为类为类 中所含模式的个数中所含模式的个数。算法原理步骤算法原理步骤2 24 4 聚类的算法聚类的算法动态聚类法动态聚类法 5858选代表点选代表点初始分类初始分类分类合理否分类合理否最终分类最终分类修改分类修改分类Y YN N4.4.动态聚类框图动态聚类框图2 24 4 聚类的算法聚类的算法动态聚类法动态聚类法 5959 例例2.4.32.4.3：已知有已知有2020个样本，每个样本有个样本，每个样本有2 2个特征，数个特征，数据分布据分布如下图如下图,使用使用C C均值法实现样本分类（均值法实现样本分类（C=2C=2）

37、。）。第一步第一步：令：令C=2C=2，选初始聚类中心为，选初始聚类中心为样本序号样本序号x x1 1x x2 2x x3 3x x4 4x x5 5x x6 6x x7 7x x8 8x x9 9x x1010特征特征x x1 10 01 10 01 12 21 12 23 36 67 7特征特征x x2 20 00 01 11 11 12 22 22 26 66 6x11x12x13x14x15x16x17x18x19x20867897898967777888996060616100第二步第二步：000）（-10100）（-10001）（-所以因为-所以因为同理,12,21=-=-.206

38、52065都属于、离计算出来，判断与第二个聚类中心的距、同样把所有因此分为两类：),.,()1(),()1(205422311=18,221=NNGG二、一、636364646565第三步：第三步：更新聚类中心更新聚类中心66666767第四步：第四步：第二步：第二步：第三步第三步：更新聚类中心：更新聚类中心686824 聚类的算法 2.4.3 动态聚类法动态聚类法C-均值法均值法关于关于C-C-均值法收敛性的分析均值法收敛性的分析696924 聚类的算法 2.4.3 动态聚类法动态聚类法C-均值法均值法当模式分布呈现类内团聚状，当模式分布呈现类内团聚状，C-C-均值算法是能均值算法是能达到很

39、好的聚类结果，故应用较多。从算法的迭代达到很好的聚类结果，故应用较多。从算法的迭代过程看，过程看，C-C-均值算法均值算法是能使各模式到其所判属的类是能使各模式到其所判属的类别中心别中心距离距离(平方平方)之和为最小之和为最小的最佳聚类。的最佳聚类。7070(3)(3)动态聚类法动态聚类法ISODATA算法算法(Iterative Self-Organizing Data Analysis Techniques Algorithm 迭代自组织数据分析迭代自组织数据分析)特点：特点：启发性推理、分析监督、控制聚类结构及人机交互。启发性推理、分析监督、控制聚类结构及人机交互。条件及约定：条件及约定：设待分类的模式特征矢量为设待分类的模式特征矢量为 ，算法运行前，算法运行前需设定需设定7 7个初始参数。个初始参数。算法思想：算法思想：在每轮迭代过程中，样本重新调整类别之后计算类内及类在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地是一类分裂为两类，不断地“自组织自组织”，以达到在各参数满足，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。设计要求条件下，使各模式到其类心的距离平方和最小。