模式识别7.pdf

《模式识别7.pdf》由会员分享，可在线阅读，更多相关《模式识别7.pdf（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第七章 聚类分析第七章 聚类分析分类与聚类的区别分类与聚类的区别分类分类：用已知类别的样本训练集来设计分类器（监督学习）聚类（集群）聚类（集群）：事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）27.1 聚类的基本概念7.2 模式相似性测度7.3 类的定义与类间距离7.4 聚类的算法?简单聚类?分解(分级)聚类法?层次（系统）聚类?动态聚类337.1 聚类的基本概念7.1 聚类的基本概念似圆度似圆度7.1.1 聚类分析的基本思想7.1.1 聚类分析的基本思想据据相似程度相似程度分类分类无监督分类无监督分类（Unsupervised）1x2x4 47.1.2 聚类准则对聚类结

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

3、本概念7.1 聚类的基本概念57.1.3 距离测度对聚类结果的影响7.1.3 距离测度对聚类结果的影响2.1 聚类的基本概念2.1 聚类的基本概念5数据的粗聚类是两类,细聚类为4类数据的粗聚类是两类,细聚类为4类6 67.2 模式相似性测度7.2 模式相似性测度7.2.1 距 离 测 度7.2.1 距 离 测 度7.2.2 相 似 测 度7.2.3 匹 配 测 度7.2.2 相 似 测 度7.2.3 匹 配 测 度777.2.1 距离测度(差值测度)7.2.1 距离测度(差值测度)Distance(or Dissimilarity)Measure设特征矢量和的距离为则一般应满足如下公理设特征矢

4、量和的距离为则一般应满足如下公理xr(,)0,(,)=0d x yxyd x yxy=r rrrr rrr当且仅当时等号成立，即yr(,)d x yr r(,)d x yr r(,)=(,)d x yd y xr rr r(,)(,)(,)d x yd x zd z y+r rrrrr(1)(2)(3)(triangular inequality)8距离测度(差值测度)欧氏距离测度(差值测度)欧氏(Euclidean)距离距离1212(,)(,)TTnnxx xxyy yy=rrLL设，2 1/21(,)()niiid x yxyxy=r rrr 绝对值距离(街坊距离或 绝对值距离(街坊距离或

5、Manhattan距离)距离)1(,)|niiid x yxy=r r(3)切氏(3)切氏(Chebyshev)距离)距离(,)max|iiid x yxy=r r9距离测度(差值测度)(4)明氏距离测度(差值测度)(4)明氏(Minkowski)距离距离1/1(,)()nmmiiid x yxy=r r(5)(5)Cambera距离距离(Lance距离、距离、Willims距离距离)1|(,)(,0,0)|niiiiiiiiixyd x yx yxyxy=+r r该距离能克服量纲的影响，但不能克服分量间的相关性。该距离能克服量纲的影响，但不能克服分量间的相关性。10距离测度(差值测度)(6)

6、马氏(距离测度(差值测度)(6)马氏(Mahalanobis)距离)距离21(,)()()Tijijijdx xxxVxx=r rrrrr11()()1mTiiiVxxxxm=rrrr11miixxm=rr其中其中（协方差矩阵的无偏估计）（协方差矩阵的无偏估计）（均值向量的估计均值向量的估计）性 质：性 质：对 一 切 非 奇 异 线 性 变 换 都 是 不 变 的。即，具 有 坐 标 系对 一 切 非 奇 异 线 性 变 换 都 是 不 变 的。即，具 有 坐 标 系 比 例、旋 转、平 移 不 变 性，并且从统计意义上尽量去掉了分量间的相关性比 例、旋 转、平 移 不 变 性，并且从统计意

7、义上尽量去掉了分量间的相关性。11马氏距离具有线性变换不变性马氏距离具有线性变换不变性证明：证明：设，有非奇异线性变换：则设，有非奇异线性变换：则yAx=rr111111mmmiiiiiiyyAxAxAxmmm=rrrrr11111()()11 ()()11 ()()11 ()()1mTyiiimTiiimTTiiimTTTiixiVyyyymAxAxAxAxmA xxxxAmAxxxxAAV Am=rrrrrrrrrrrrrrrr12故故2211111111()()()()()()()()()()()(,)(,)TijyijTijyijTTijyijTTTijxijTTTijxijTijxi

8、jyijxijyyVyyAxAxVAxAxxxA VA xxxxAAV AA xxxxA AVA A xxxdy ydxVx xxx=rrrrrrrrrrrrrrrrrrrrrrrr rrr r111()ABB A=Q13马氏距离的一般定义马氏距离的一般定义设、是从期望矢量为、设、是从期望矢量为、协方差矩阵协方差矩阵为的母体G中抽取的两个样本，则它们间的马氏距离定义为当和是分别来自两个数据集中的样本时，设C是它们的为的母体G中抽取的两个样本，则它们间的马氏距离定义为当和是分别来自两个数据集中的样本时，设C是它们的互协方差阵互协方差阵，则它们间的马氏距离定义为，则它们间的马氏距离定义为21(,)

9、()()Tdx yxyxy=r rrrrrxryrrxryr21(,)()()Tdx yxyCxy=r rrrrr?当、V、C为单位矩阵时，马氏距离欧氏距离。当、V、C为单位矩阵时，马氏距离欧氏距离。?对于正态分布，等概率密度点轨迹是到均值矢量的马氏距离为常数的点所构成的超椭球面。对于正态分布，等概率密度点轨迹是到均值矢量的马氏距离为常数的点所构成的超椭球面。147.2.2 相 似 测 度7.2.2 相 似 测 度 重点考虑重点考虑两矢量的方向两矢量的方向是否相近，而忽略矢量长度。是否相近，而忽略矢量长度。(1)角度相似系数(1)角度相似系数(夹角余弦）矢量之间的相似性可用它们的夹角余弦来度量

10、(夹角余弦）矢量之间的相似性可用它们的夹角余弦来度量1/2cos(,)()()TTTTx yx yx yxyx xy y=r rr rr rrrr rr r1/2()()(,)()()()()TTTxxyyr x yxxxxyyyy=rrrrr rrrrrrrrr(2)相关系数(2)相关系数数据中心化后的矢量夹角余弦数据中心化后的矢量夹角余弦性质：性质：相关系数具有坐标系相关系数具有坐标系平移、旋转、比例不变性。平移、旋转、比例不变性。1515221()13(,)exp4niiiixye x yn=r r性质：不受量纲变化的影响。性质：不受量纲变化的影响。(3)指数相关系数(3)指数相关系数这

11、里假设和的维数这里假设和的维数 n 相同、概率分布相同。是第相同、概率分布相同。是第 i 个分量的方差。个分量的方差。xryr2i167.2.3 匹 配 测 度7.2.3 匹 配 测 度若特征只有两个状态：若特征只有两个状态：0=有此特征；有此特征；1=无此特征。称之为二值特征。对于给定的二值特征矢量无此特征。称之为二值特征。对于给定的二值特征矢量x和和y中的某两个相对应的分量中的某两个相对应的分量xi与与yj若若xi=1,yj=1，则称，则称xi与与yj(1-1)匹配；若匹配；若xi=1,yj=0，则称，则称(1-0)匹配；若匹配；若xi=0,yj=1，则称，则称(0-1)匹配；若匹配；若x

12、i=0,yj=0，则称，则称(0-0)匹配。对于二值匹配。对于二值n维特征矢量可定义如下相似性测度：维特征矢量可定义如下相似性测度：17匹 配 测 度匹 配 测 度(1)(1)Tanimoto测度测度(1-1)匹配的特征数目(0-1)匹配的特征数目(1-0)匹配的特征数目(0-0)匹配的特征数目(1-1)匹配的特征数目(0-1)匹配的特征数目(1-0)匹配的特征数目(0-0)匹配的特征数目(1)(1)(1)(1)iiiiiiiiiiiiax ybyxcxyexy=令令(,)TTTTax ys x yabcx xy yx y=+r rr rr rr rr r注意，这里只考虑（1-1）匹配，而不考

13、虑（0-0）匹配。注意，这里只考虑（1-1）匹配，而不考虑（0-0）匹配。18匹 配 测 度匹 配 测 度(2)(2)Rao测度(3)简单匹配系数(4)测度(3)简单匹配系数(4)Dice系数(5)系数(5)Kulzinsky系数系数(,)Tax ys x yabcen=+r rr r(,)aem x yn+=r r（1-1）匹配特征数目与特征总数之比）匹配特征数目与特征总数之比22(,)2TTTax ym x yabcx xy y=+r rr rr rr r(,)2TTTTax ym x ybcx xy yx y=+r rr rr rr rr r（1-1）匹配）匹配+（0-0）匹配）匹配/特

14、征总数只对（特征总数只对（1-1）匹配加权（）匹配加权（1-1）匹配）匹配/（1-0）匹配）匹配+（0-1）匹配）匹配1919例 1设(1)设(1)Tanimoto测度(2)测度(2)Rao测度(3)简单匹配测度(4)测度(3)简单匹配测度(4)Dice系数(5)系数(5)Kulzinsky系数系数(,1,0,1,0)(,0,1,0001,1)1TTxy=rr3,3,1TTTx xy yx y=r rr rr r1(,)6Tx ys x yn=r rr r1 11(,)63aem x yn+=r r221(,)333TTTx ym x yx xy y=+r rr rr rr r1(,)24TT

15、TTx ym x yx xy yx y=+r rr rr rr rr r则11(,)33 15TTTTx ys x yx xy yx y=+r rr rr rr rr r207.3 类的定义与类间距离7.3 类的定义与类间距离7.3.1 类的定义7.3.1 类的定义类的划分具有人为规定性，这反映在类的定义选取及参数选择上。分类结果的优劣最后只能根据实际来评价。定义 设集合S中任意元素xi与xj间的距离dij有dijh其中h为给定的阈值，称S对于阈值h组成一类。217.3.2 类间距离测度方法7.3.2 类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法2

16、222（一）最近距离（一）最近距离两个聚类k和l之间的最近距离定义为式中，dij表示 xi k与xjl间的距离。如果l由p和q两类合并而成，则有递推公式,minkliji jDd=min,=klkpkqDDDkpq23（二）最远距离（二）最远距离递推公式,maxkliji jDd=max,=klkpkqDDDkpq24（三）中间距离（三）中间距离递推公式递推公式2222111224klkpkqpqDDDD=+pqkpqkpqDkqDklDkpDl25（四）重心距离（四）重心距离递推公式式中，和分别是递推公式式中，和分别是 i和和 j的重心，的重心，i,j=k,l,p,q。22222()klkp

17、kqpqpqpqpqpqpqnnn nDDDDnnnnnn=+2()()TijijijDxxxx=rrrrixrjxr26（五）平均距离（五）平均距离两类p和q间的距离平方定义为这两类元素两两之间的平均平方距离，即设l=pq，类平均距离的递推公式为22,1=rrpqipjpijxxpqDdn n222=+klkpkqpqpqpqnnDDDnnnn272727（六）离差平方和法（六）离差平方和法设类t 的重心是，t 的类内离差平方和定义为设设 l=p q，则，则sl要变大。把两类合并所增加的离差平方和定义为两类平方距离，即，可以证明要变大。把两类合并所增加的离差平方和定义为两类平方距离，即，可以

18、证明 k与与 l=p q的离差平方和的递推公式的离差平方和的递推公式2222+=+klkpkqpqkpkqkklklklnnnnnDDDDnnnnnnrtx()()itTtititxsxxxx=rrrrr2=pqlpqDsss2()()pqTpqpqpqpqn nDxxxxnn=+rrrr28222222kqkppqkqqkppklDDDDDD+=0离差平方和法离差平方和法0可变法可变法0可变平均法可变平均法00平均距离法平均距离法0重心距离法重心距离法0-1/41/21/2中间距离法中间距离法1/201/21/2最远距离法最远距离法-1/201/21/2最近距离法最近距离法pqqppnnn+

19、qpqnnn+qpqppnnn+qpqnnn+qppnnn+)1(qpqnnn+)1(1121222xzrr=Td2121xr3774 聚类的算法4 聚类的算法-简单聚类方法简单聚类方法 假设已有聚类中心，计算尚未确定类别的模式特征矢量到各聚类中心的距离。如果,则作为新的一类的中心，；否则，如果,则指判。检查是否所有的模式都分划完类别，如果都分划完了则结束；否则返到。假设已有聚类中心，计算尚未确定类别的模式特征矢量到各聚类中心的距离。如果,则作为新的一类的中心，；否则，如果,则指判。检查是否所有的模式都分划完类别，如果都分划完了则结束；否则返到。kzzzrLrr,21ixr),2,1(kjzj

20、Lr=ijdTdij),2,1(kjL=ixr1k+ikxzrr=+1minilijjdd=ilxr387 74 聚类的算法4 聚类的算法-简单聚类方法简单聚类方法?这类算法的突出优点是这类算法的突出优点是算法简单算法简单。但聚类过程中，。但聚类过程中，类的中心一旦确定将不会改变类的中心一旦确定将不会改变，模式一旦指定类后也不再改变模式一旦指定类后也不再改变。?从算法的过程可以看出，该算法结果很大程度上依赖于从算法的过程可以看出，该算法结果很大程度上依赖于距离门限T的选取及模式参与分类的次序距离门限T的选取及模式参与分类的次序。如果能有先验知识指导门限T的选取，通常可获得较合理的效果。也可考虑

21、设置不同的T和选择不同的次序，最后选择较好的结果进行比较。如果能有先验知识指导门限T的选取，通常可获得较合理的效果。也可考虑设置不同的T和选择不同的次序，最后选择较好的结果进行比较。算法特点:算法特点:39X 轴Y 轴Z1T=21234591076811简单聚类图例简单聚类图例7 74 聚类的算法4 聚类的算法-简单聚类方法简单聚类方法40Y 轴X 轴Y 轴例7.4.1：初始条件不同的简单聚类结果例7.4.1：初始条件不同的简单聚类结果初始中心不同初始中心不同样本顺序不同样本顺序不同1 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 510 9 8 10 9 8 8 7 6

22、8 7 6 11 6 711 6 79 10 119 10 114174 聚类的算法聚类的算法-分解聚类 P244 分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解把全部样本作为一类，然后根据相似性、相邻性分解。目标函数:两类均值方差121212()()TN NENXXXX=N：总样本数，为1类样本数为2类样本数，12,:XX两类均值1N2N42分解聚类框图：初始分类调整分类方案最终结果目标函数达到最优先？NY43用下例说明分解聚类算法例：已知21个样本，每个样本取二个特征，原始资料矩阵如下表：0121343556xi27665442200 xi110987654321样本号-5-3-

23、1-2-1120223-3-1-1001-5-3-3-2-4212019181716151413121144目标函数121212()()0TN NEXXXXN=(0)10.714()1.333X=2(0)0()0X=0,21)0(2)0(1=NN解：第一次分类时计算所有样本，分别划到（即划分为另一类）时的最大E值。1、开始时G2),.,(2121)0(1xxxG=空=G)0(2452、分别计算当依次划入G2时的E值把划入G2时有2121,.,xxx1x(0)(1)(0)11(0)111(1)22210.7 1 40()()0.7 1 40.7 51.3 3 36()(),1.3 3 31.1

24、0(2 11)0()62 010.7 5(1.1 06)2 3.4 02 1xNEXXXX=+=+=+=仅有x1一个样本46然后再把依次划入，计算对应的E值，找出一个最大的E值。通过计算知 把划为的E值最大。2132,.,xxxG2G2x21),.,(2021)1(1xxxG=)(21)1(2xG=10.9(),1.65X=(1)(1)2123(),20,15XNN=E(1)=56.6再继续进行第二、第三次迭代计算出 E(2),E(3),47次数E值1 56.62 79.163 90.904 102.615 120.116 137.157 154.108 176.159 195.2610 21

25、3.0711 212.01G2G1x21x20 x18x14x15x19x11x13x12x17x1648第10次迭代划入时，E最大。于是分成以下两类：G2x17),.,(1610211xxxxG=),(212019181715,141312112xxxxxxxxxxG=每次分类后要重新计算的值。可用以下递推公式：12,XX)1/()()1/()()(2)(2)(2)1(2)(1)(1)(1)1(1+=+=+kikkkkikkkNxxxxNxxxx为二类样品数(k)2N,(k)1N时的两类均值(k)2划到G(k)1从G 把分时1是k1)(k2x,1)(k1x时二类的均值是k(k)2x,(k)1

26、xoix，步对步+4910 x2x3x4x15x11x12x13x14x16x17x18x19x7x8x9x20 x21x6x1x5x6543211234561X2X43215665432150作业：样本1 2 3 4 5 6 7 80 2 1 5 6 5 6 70 2 1 3 3 4 4 5用对分法编程上机，分成两类画出图形。1x2x51层次聚类法层次聚类法(Hierarchical Clustering Method)(系统聚类法系统聚类法、谱系聚类法谱系聚类法）条件及约定 条件及约定设待分类的模式特征矢量为，表示第次合并时的第类。设待分类的模式特征矢量为，表示第次合并时的第类。算法思想

27、算法思想首先将 N 个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。首先将 N 个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。NxxxrLrr,21)(kiGik按最小距离原则不断进行两类合并按最小距离原则不断进行两类合并7 74 聚类的算法4 聚类的算法层次聚类法层次聚类法52m3.算法原理步骤3.算法原理步骤(1)初始分类。令，每个模式自成一类，即(1)初

28、始分类。令，每个模式自成一类，即0=k),2,1()0(NixGiiLr=(2)计算各类间的距离，由此生成一个对称的距离矩阵，为类的个数（初始时）。2)计算各类间的距离，由此生成一个对称的距离矩阵，为类的个数（初始时）。DijmmijkDD=)()(Nm=7 74 聚类的算法4 聚类的算法层次聚类法层次聚类法53 找出前一步求得的矩阵中的最小元素，设它是和间的距离，将和两类合并成一类，于是产生新的聚类令 检查类的个数。如果类数大于2，转至；否则，停止。找出前一步求得的矩阵中的最小元素，设它是和间的距离，将和两类合并成一类，于是产生新的聚类令 检查类的个数。如果类数大于2，转至；否则，停止。Dk

29、)()(kiG)(kjG)(kjG)(kiGL,)1(2)1(1+kkGG1,1kkmm=+=m7 74 聚类的算法4 聚类的算法层次聚类法层次聚类法54例7.4.3：如下图所示例7.4.3：如下图所示 1、设全部样本分为6类，1、设全部样本分为6类，2、作距离矩阵D(0)2、作距离矩阵D(0)3、求最小元素：3、求最小元素：4、把4、把1 1,3 3合并合并7 7=(1,3)=(1,3)4 4,6 6合并合并8 8=(4,6)=(4,6)5、合并的类数没有达到要求作距离矩阵D(1)5、合并的类数没有达到要求作距离矩阵D(1)x1234523314474855262685913D(0)3G1G

30、2G5G4G6G55例7.4.3：如下图所示例7.4.3：如下图所示 7、作距离矩阵D(1)7、作距离矩阵D(1)8、求最小元素：8、求最小元素：9、把9、把2 2,5 5，8 8合并合并9 9=（2,5,4,6）=（2,5,4,6）10、合并的类数达到要求，停止。10、合并的类数达到要求，停止。xD(1)728238745522725856枝状图15234678910577-4 动态聚类动态聚类兼顾系统聚类和分解聚类兼顾系统聚类和分解聚类P235动态聚类的方法概要动态聚类的方法概要 先选定某种距离作为样本间的相似性度量;确定评价聚类结果的准则函数;给出某种初始分类，用迭代法找出使准则函数取极

31、值的最好聚类结果。58选代表点选代表点初始分类初始分类分类合理否分类合理否最终分类最终分类修改分类修改分类YNYN动态聚类框图动态聚类框图59代表点的选取方法代表点的选取方法：代表点就是初始分类的聚类中心数：代表点就是初始分类的聚类中心数C 凭经验选代表点，根据问题的性质、数据分布，从直观上选出较合理的代表点;将全部样本随机分成C类，计算每类重心，把这些重心作为每类的代表点。60 按密度大小选代表点：以每个样本作为球心，以d为半径做球形;落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于

32、d1（人为规定的正数）则把第二大密度点作为第二代表点，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于d1。d1太小，代表点太多，d1太大，代表点太少，一般选d12d。对代表点内的密度一般要求大于T。T0为规定的一个正数。用前C个样本点作为代表点。61初始分类和调整初始分类和调整 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心形成初始分类，再重新计算各聚类中心，称为成批处理法称为成批处理法。E 选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。

33、再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心即每个样本的归类都改变一次聚类中心。此法称为逐个处理法此法称为逐个处理法。E 直接用样本进行初始分类，先规定距离d，把第一个样本作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并决定分裂还是合并。62最佳初始分类。如图所示，随着初始分类C的增大，准则函数下降很快，经过拐点A后，下降速度减慢。拐点A就是最佳初始分类。准则函数JK

34、最佳初始分类A拐点03217654下降快下降慢C63 条件及约定 条件及约定设待分类的模式特征矢量集为，类的数目C是事先设定的。设待分类的模式特征矢量集为，类的数目C是事先设定的。算法思想 算法思想该方法该方法取定 C个类别取定 C个类别和和选取 C个初始聚类中心，选取 C个初始聚类中心，按最小距离原则将各模式分配到 C类中的某一类，之后不断地按最小距离原则将各模式分配到 C类中的某一类，之后不断地计算类心和调整各模式计算类心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方之和最小。的类别，最终使各模式到其判属类别中心的距离平方之和最小。NxxxrLrr,21C-均值法均值法64 算

35、法原理步骤 算法原理步骤 任选C个模式特征矢量作为初始聚类中心：,令。任选C个模式特征矢量作为初始聚类中心：,令。)0()0(2)0(1,czzzrLrr0k=将待分类的模式特征矢量集中的模式逐个按最小距离原则分划给C类中的某一类，即:如果则,式中表示和的中心的距离，上角标表示迭代次数。于是产生新聚类 将待分类的模式特征矢量集中的模式逐个按最小距离原则分划给C类中的某一类，即:如果则,式中表示和的中心的距离，上角标表示迭代次数。于是产生新聚类。ixr()()minkkilijjdd=),2,1(NiL=(1)kilx+r)(kijdixr()kj)(kjzr(1)kj+),2,1(cjL=C-

36、均值法均值法65(4)如果,则结束,否则,转至(2)。(3)计算重新分类后的各类心式中为类中所含模式的个数。(4)如果,则结束,否则,转至(2)。(3)计算重新分类后的各类心式中为类中所含模式的个数。(1)(1)(1)1,kijkjikxjzxn+=rrr),2,1(cjL=)1(+kjn(1)kj+(1)(),kkjjzz+=rrcj,2,1L=1kk=+C-均值法均值法66例7.4.3：例7.4.3：已知有20个样本，每个样本有2个特征，数据分布如下图,使用C均值法实现样本分类（C=2）。已知有20个样本，每个样本有2个特征，数据分布如下图,使用C均值法实现样本分类（C=2）。第一步第一步

37、：令C=2，选初始聚类中心为：令C=2，选初始聚类中心为(1)(1)1122(0,0);(1,0)TTZxZx=rrrr样本序号样本序号x1x2x3x4x5x6x7x8x9x10特征x特征x1 10101212367特征x特征x2 20011122266x11x12x13x14x15x16x17x18x19x208678978989677778889967(1)11(1)12(1)(1)111211(1)210000001100(1)10100 xZxZxZxZxZxZ=因为所以同理同样把所有、与第二个聚类中心的距离计算出来，判断、都属于因此分为两类：一、二、2452012(,.)2,18xx

38、xxNN=69 第三步：根据新分成的两类建立新的聚类中心(1)1(2)113100111()()()012201()(0,0.5)12x GTZXxxN=+=+=(1)2(2)224520211(.)18(5.67,5.33)xGTZXxxxxN=+=第四步：转第二步进行第二次叠代。第二步（第二次叠代）：重新计算到z1(2）,z2(2）的距离，把它们归为最近聚类中心，重新分为两类，(2)(1),1,2()jjZZj=新旧聚类中心不等2021,.,xxx70 第三步（第二次叠代），更新聚类中心(2)1(3)11238111(.)8(1.25,1.13)x GTZXxxxxN=+=(2)2(3)2

39、91020211(.)12(7.67,7.33)x GTZXxxxN=+=(2)11281(,.,),8GxxxN=(2)2910202(,.,),12GxxxN=71 第四步，第二步（第三次叠代），第三步（第三次叠代），更新聚类中心(3)(2),1,2,ZZjjj=因转第二步(3)(3)1220121220(4)1128(4)29102012,.,.,(,.,)(,.,),8,12x xxZZx xxGx xxGxxxNN=重新计算到的距离，分别把归于最近的那个聚类中心，重新分为二类(4)(3)11(4)(3)22(1.25,1.13)(7.67,7.33)TTZZZZ=计算结束。进行第三次

40、叠代721X5461098765109872X9xr10 xr11xr12xr13xr14xr15xr16xr17xr18xr19xr20 xr311243201xr2xr3xr4xr6xr7xr8xr5xr731X5461098765109872X9xr10 xr11xr12xr13xr14xr15xr16xr17xr18xr19xr20 xr311243201xr2xr3xr4xr6xr7xr8xr5xr)1(1Z)1(2ZTGN)33.5,67.5().(181120542)1(22=+=2(2)Zrixrixrxrxrxrxr(0,0.5)741X5461098765109872X9x

41、r10 xr11xr12xr13xr14xr15xr16xr17xr18xr19xr20 xr311243201xr2xr3xr4xr6xr7xr8xr5xr)2(1Z)2(2Z(1.25,1.13)(7.67,7.33)75ISODATA算法算法(Iterative Self-Organizing Data Analysis Techniques Algorithm 迭代自组织数据分析迭代自组织数据分析)特点：特点：启发性推理、分析监督、控制聚类结构及人机交互。启发性推理、分析监督、控制聚类结构及人机交互。条件及约定：条件及约定：设待分类的模式特征矢量为，算法运行前需设定7个初始参数。设待分

42、类的模式特征矢量为，算法运行前需设定7个初始参数。算法思想：算法思想：在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。NxxxrLrr,2176ISODATA算法原理步骤ISODATA算法原理步骤预置设定聚类分析控制参数：=预期的类

43、数，=初始聚类中心个数(可以不等于c)，=每一类中允许的最少模式数目，=类内各分量分布的距离标准差上界，=两类中心间的最小距离下界，=在每次迭代中可以合并的最大聚类对数，=允许的最多迭代次数。将待分类的模式特征矢量读入。选定初始聚类中心，可从待分类的模式特征矢量集中任选个模式特征矢量作为初始聚类中心。预置设定聚类分析控制参数：=预期的类数，=初始聚类中心个数(可以不等于c)，=每一类中允许的最少模式数目，=类内各分量分布的距离标准差上界，=两类中心间的最小距离下界，=在每次迭代中可以合并的最大聚类对数，=允许的最多迭代次数。将待分类的模式特征矢量读入。选定初始聚类中心，可从待分类的模式特征矢量

44、集中任选个模式特征矢量作为初始聚类中心。cLINcnsDNxxxrLrr,21 ixrNc),2,1(cjNjzLr=77ISODATA算法原理步骤ISODATA算法原理步骤 ixr 按最小距离原则将模式集中每个模式分到某一类中，即如果则判式中表示和类的中心之间的距离。依据判断合并。如果类中样本数，则取消该类的中心，转至。按最小距离原则将模式集中每个模式分到某一类中，即如果则判式中表示和类的中心之间的距离。依据判断合并。如果类中样本数，则取消该类的中心，转至。njijilzxdrr=min),2,1(NiL=lixrdilixrllzrjjnnjzr1=ccNN78ISODATA算法原理步骤I

45、SODATA算法原理步骤计算各类的中心计算各类中模式到类心的平均距离计算各个模式到其类内中心的总体平均距离计算各类的中心计算各类中模式到类心的平均距离计算各个模式到其类内中心的总体平均距离=jixijjxnzrrr1),2,1(cNjL=jixjijjzxndrrr1),2,1(cNjL=jcNjjdn=11dN=计算分类后的参数:各类中心、类内平均距离及总体平均距离。计算分类后的参数:各类中心、类内平均距离及总体平均距离。79ISODATA算法原理步骤ISODATA算法原理步骤依据、判断停止、分裂或合并。依据、判断停止、分裂或合并。pIcN若迭代次数已达，则置转到；否则转下。若则转到(将一些

46、类分裂)；否则转下。若,(则跳过分裂处理)转至,否则转下。若，当迭代次数是奇数时转至(若迭代次数已达，则置转到；否则转下。若则转到(将一些类分裂)；否则转下。若,(则跳过分裂处理)转至,否则转下。若，当迭代次数是奇数时转至(分裂处理分裂处理)；迭代次数是偶数时转至()；迭代次数是偶数时转至(合并处理合并处理)。)。pII,0=D2cNccNc2cNcc22maxddj()12+njn2cNc1+=NNcc+jzrjzr+jzrjzrjzrmaxjmaxjk10 kjzr)(jii+jzrjzrj1+=ppIIjrmaxjj+jzrISODATA算法原理步骤ISODATA算法原理步骤82计算各对

47、聚类中心间的距离 依据判断合并。将与比较，并将小于的那些按递增次序排列，取前L个，。从最小的开始，将相应的两类合并。若原来的两个类心为和，则合并后的聚类中心为（已并掉的类数）。在一次迭代中，某一类最多只能被合并一次。计算各对聚类中心间的距离 依据判断合并。将与比较，并将小于的那些按递增次序排列，取前L个，。从最小的开始，将相应的两类合并。若原来的两个类心为和，则合并后的聚类中心为（已并掉的类数）。在一次迭代中，某一类最多只能被合并一次。jiijzzDrr=(1,2,1ciN=L),1;cNijL+=DijDDDijDLLjijijiDDDL2211ijDizrjzrjjiijilznznnnz

48、rrr+=1=ccNNISODATA算法原理步骤ISODATA算法原理步骤83如果迭代次数已达次或过程收敛，则结束。否则，若需要调整参数，则转至；若不改变参数，则转至。如果迭代次数已达次或过程收敛，则结束。否则，若需要调整参数，则转至；若不改变参数，则转至。IpI1+=IIppISODATA算法原理步骤ISODATA算法原理步骤84我们将ISODATA算法的合并和分裂的条件归纳如下：我们将ISODATA算法的合并和分裂的条件归纳如下：合并的条件合并的条件：(类内样本数)(类的数目)(两类间中心距离)：(类内样本数)(类的数目)(两类间中心距离)分裂的条件分裂的条件：(类的数目)(类的某分量标准

49、差)这里，表示“或”的关系；表示“与”的关系。如果类的数目有，当是奇数时分裂，当是偶数时合并。由上述合并与分裂的判断条件可以看出算法初设的7个参数存在一定的相互制约。：(类的数目)(类的某分量标准差)这里，表示“或”的关系；表示“与”的关系。如果类的数目有，当是奇数时分裂，当是偶数时合并。由上述合并与分裂的判断条件可以看出算法初设的7个参数存在一定的相互制约。nc2D+)2()1(2()(cNnddcnjjNccNcc221(3)因，无合并(3)因，无合并:=75.238.31111ixixnzrrr26.211111=ixizxndrrr26.21=ddISODATA算法举例ISODATA算

50、法举例881X5466572X311243201xr2xr3xr4xr6xr7xr8xr5xr1zr(5)因不是最后一步迭代，且，转至(5)因不是最后一步迭代，且，转至2cNc=(6)求的标准差矢量(6)求的标准差矢量1=56.199.11r212)(1=jixkjkijkjzxnrISODATA算法举例ISODATA算法举例891X5466572X311243201xr2xr3xr4xr6xr7xr8xr5xr(6)因且将分裂成两类,取，则(6)因且将分裂成两类,取，则1zr(7)算得(7)算得99.1max1=s=99.1max12cNc=10.15.0,5.0max1=k1175.238