1、第章聚类分析第第6章聚章聚 类类 分分 析析6.1模式相似性测度与聚类准则模式相似性测度与聚类准则6.2基于试探的聚类算法基于试探的聚类算法6.3层次聚类法层次聚类法6.4动态聚类法动态聚类法6.5分解法分解法习题习题第章聚类分析6.1模式相似性测度与聚类准则模式相似性测度与聚类准则聚类分析是以模式相似性为基础,按照某种聚类准则进行判决。本节主要介绍模式相似性测度与聚类准则。6.1.1模式相似性测度模式相似性测度分类在实际工作中经常出现,例如,在古生物研究中,根据骨骼的形状和大小对它们进行分类;在地质勘探中,根据矿石标本的物探和化探指标对标本进行分类,等等。其中,骨骼的形状和大小、标本的物探和
2、化探指标是描述样本特征的具体参数,是分类的依据。第章聚类分析根据测量尺度的不同,模式特征的数值化测量结果主要分为以下三种类型:(1)物理量:特征用连续的量来表示,如长度、重量、压力等。(2)次序量:特征度量没有明确的数量表示,只有次序关系。例如,评价茶叶的质量分成优、良、中、差四等,其中,有次序关系,没有数量表示。第章聚类分析(3)名义量:特征度量既没有数量表示也没有次序关系。例如,电路中的开和关;医疗诊断中的“+”和“-”;天气中的晴天和雨天,等等。为了对模式进行分类,需要定义相似性测度来度量各模式之间的相似性和差异性。一种方法是将每一个样本看成m维特征空间的一个点,并在该空间定义距离,距离
3、较近的点归为一类,距离较远的点划分为不同的类。第章聚类分析另一种方法是利用相似系数,特征越接近的样本之间的相似系数越大(接近于1),把它们归为一类;反过来,彼此无关的样本之间的相似系数接近于0,把它们划分为不同的类。在聚类分析中正确选择距离与相似系数是非常重要的,它直接影响到分类的效果。第章聚类分析1.距离距离用dij表示第i个样本与第j个样本之间的距离,一般要求距离满足三个条件(即距离三公理):(1)非负性:dij0(i,j),当且仅当第i个样本与第j个样本的各个特征相同时,dij=0;(2)对称性:dij=dji(i,j);(3)三角不等式:第章聚类分析kjikijdddkji,(6-1)
4、在模式识别中定义的有些距离并不满足“三角不等式”,只是在广义的角度上也称它为距离。在有些场合,“三角不等式”加强为,maxkjikijddd kji,(6-2)第5章已经给出了几种常用的距离,包括欧几里德(Euclidean)距离、加权欧几里德距离、汉明(Haming)距离、马氏(Mahalanobis)距离、明可夫斯基(Minkowsky)距离和切比雪夫(Chebyshev)距离等。第章聚类分析2.相似系数相似系数用cij表示向量yi与yj的相似系数,一般规定:(1)cij=1 yi=ayj,a0是一常数;(2)|cij|1,对一切i,j;(3)cij=cji,对一切i,j,其中,|cij|
5、越接近于1,yi与yj的关系越密切。当特征用连续的量来表示时,常用的相似系数有如下几种。第章聚类分析1)夹角余弦 夹角余弦是受相似形的启发而产生的。向量(xi1,xi2,xin)T与(xj1,xj2,xjn)T之间的夹角余弦的定义为 12211()()nikjkkijnnikjkkkx xcxx(6-3)第章聚类分析2)相关系数 相关系数是将数据标准化后的夹角余弦,即 12211nikikjkjkkijnnikikjkjkkkxxxxcxxxx(6-4)其中,为第k个分量的平均值(k=1,2,n)。可以借助于相似系数来定义距离,例如:ikx第章聚类分析221ijijcd(6-5)3)指数相似系
6、数 指数相似系数定义为 2213()1exp4nikjkijkkxxcns(6-6)其中,为相应分量的方差。指数相似系数不受量纲变化的影响。2ks第章聚类分析4)特征向量的各分量为非负时的几种相似系数当特征向量的各分量非负时,还有下列几种相似系数:11min(,)max(,)nikjkkijnikjkkxxcxx(6-7)11min(,)1()2nikjkkijnikjkkxxCxx(6-8)第章聚类分析11min(,)nikjkkijnikjkkxxcx x(6-9)5)列联系数和关联系数对于名义量,它们之间的相似系数通过列联表来定义。设名义量yi取值是t1,t2,tp,yj取值是r1,r2
7、,rq,用nkl表示yi取tk、yj取rl的样本数,列成表6-1的形式,称为列联表。第章聚类分析令22111pqijijijnnn n(6-10)其中1qiijjnn1,2,ip(6-11)1pjijinn1,2,jq(6-12)11pqijijnn(6-13)第章聚类分析利用2可以定义名义量之间的相似系数:列联系数 22ijcn(6-14)关联系数2max(1,1)ijcnpq(6-15)2min(1,1)ijcnpq(6-16)第章聚类分析2(1)(1)ijcnpq(6-17)111212122212qqpppqnnnnnnnnn12pttt1n2npniyjy12qryr1n1nqnn表
8、6-1 列联表第章聚类分析6.1.2聚类准则聚类准则在模式分类中,可以有多种不同的聚类方法,将未知类别的N个样本划分到m类中去,从而,需要确定一种聚类准则来评价各种聚类方法的优劣。事实上,聚类的优劣只是就某种评价准则而言的,很难找到对各种准则均表现优良特性的聚类方法。第章聚类分析聚类准则的确定主要有两种方式:(1)试探方式。凭直观和经验,针对实际问题给定一种模式相似性测度的阈值,按最近邻规则指定待分类样本属于某一类别。例如,以欧氏距离作相似性的度量,将一个样本分到某一类时,凭直观和经验规定一个距离阈值作为聚类的判别准则。第章聚类分析(2)聚类准则函数法。定义一种聚类准则函数J,其函数值与样本的
9、划分有关,当J取得极值时,就认为得到了最佳划分。常用的聚类准则函数为误差平方和准则与类间距离和准则。假设有N个样本,在某种相似性测度的准则下属于类1,2,m,类i中有Ni个样本。第章聚类分析1.误差平方和准则误差平方和准则误差平方和准则也可以称为类内距离准则,是一种简单而又应用广泛的聚类准则。类i的均值为1 (1,2,)iiiimNxx(6-18)误差平方和定义为 21imiiJxx(6-19)第章聚类分析J是样本与聚类中心的函数,表示各样本到其被划归类别的中心的距离之平方和。对应一种划分,可求得一个误差平方和J。以误差平方和作为准则时,目的就是要找到使J值最小的那种划分。误差平方和准则适用于
10、同类样本比较密集,各类样本数目相差不大,且类间距离较大的情况。当各类样本数相差很大且类间距离较小时,采用误差平方和准则,就有可能将样本数多的一类拆成两类或多类,从而出现错误聚类。第章聚类分析2.类间距离和准则类间距离和准则全部样本的均值为 11NjjNx(6-20)类间距离和定义为 1()()mTiiiJ(6-21)第章聚类分析加权的类间距离和定义为 1()()mTiiiiNJN(6-22)对应一种划分，可求得一个类间距离和。类间距离和准则是找到使类间距离和达到最大的那种划分。第章聚类分析6.2基于试探的聚类算法基于试探的聚类算法确定一种聚类准则后,每一种分类方法对应于一个J值,其中使J取得极
11、值的分类,就被认为是最佳分类。这种处理方式的计算量太大,可以对某些关键性的参数进行试探性地选取,使聚类准则函数达到最优,这类方法可称为基于试探的聚类算法。第章聚类分析6.2.1基于最近邻规则的试探法基于最近邻规则的试探法设待分类样本集为x1,x2,xN,按最近邻规则进行聚类,算法具体步骤如下:(1)选取任意一个样本作为第一个聚类中心z1,例如,令1类的中心z1=x1,选定一非负的类内距离阈值T。(2)计算下一个样本x2到z1的距离d21。若d21T,则建立一新的聚类中心z2,且2类的中心z2=x2;若d21T,则认为x2在以z1为中心的邻域中,即x2属于1类。第章聚类分析(3)假定已有m类的中
12、心z1,z2,zm,计算尚未确定类别的样本xi到m类中心zj(j=1,2,m)的距离dij。如果所有的dij均满足dijT,则建立一新的聚类中心zm+1,且m+1类的中心zm+1=xi;否则将xi划分到距离其最近的聚类中心所代表的类中。(4)检查是否所有的样本已经确定类别,如果都已确定类别,则转下一步;否则返回(3)。第章聚类分析(5)按照某种聚类准则评价聚类结果,如果不满意,则重新选取第一个聚类中心和类间距离阈值T,返回(2);如果满意,则算法结束。这种方法的聚类结果与第一个聚类中心的选取、待分类样本的排列次序、阈值T的大小以及样本分布的几何特性有关。图6-1表示了距离阈值T的大小和初始聚类
13、中心位置对聚类结果的影响。第章聚类分析图6-1 距离阈值和初始类心对聚类结果的影响第章聚类分析6.2.2最大最小距离聚类算法最大最小距离聚类算法最大最小距离聚类算法是另一种简单的试探法,以类间距离最大作为选取新的聚类中心的条件,以最小距离原则进行样本归类。这种算法通常采用欧氏距离,算法具体步骤如下:(1)选取任意一个样本作为第一个聚类中心z1。(2)选取距离z1最远的样本作为第二个聚类中心z2。第章聚类分析(3)计算所有未作为聚类中心的样本xi与z1、z2的距离di1,di2,并设di=min(di1,di2),若存在则建立第三个聚类中心z3,且z3=xl。其中:d(z1,z2)为z1与z2之
14、间的距离;可用试探法取为一固定分数,例如,。(4)假定已有m个聚类中心z1,z2,zm,计算尚未作为聚类中心的各样本xi到m类中心zj(j=1,2,m)的距离dij,并计算12max(,)liidddz z1/2第章聚类分析1212min(,)maxmin(,)JJJJmiiimiddddddd如果dJd(z1,z2),则建立第m+1个聚类中心zm+1,且zm+1=xJ,并转(4);否则转下一步。(5)将全部样本按最近距离原则划分到各类中。(6)按照某种聚类准则评价聚类结果,如果不满意,则重新选取第一个聚类中心和值,返回(2);如果满意,则算法结第章聚类分析【例例 6.1】10个样本数据如图6
15、-2所示,用最大最小距离聚类算法对样本集分类。解解(1)给定=1/2,选取任意一个样本作为第一个聚类中心z1,令z1=x1。(2)计算其他样本到z1的距离,可得x6距离z1最远,则建立第二个聚类中心z2=x6。第章聚类分析(3)计算所有未作为聚类中心的样本与z1、z2的距离,根据最大最小距离聚类算法,得到第三个聚类中心z3=x7。(4)判断出不再有新的聚类中心,将全部样本按最近距离原则划分到各类中,得到x1,x3,x4为第一类,x2,x6为第二类,x5,x7,x8,x9,x10为第三类。(5)通过直观判断,认为本次分类结果比较合理,对样本集的分类完成。第章聚类分析图6-2 最大最小距离聚类算法
16、示例第章聚类分析6.3层层 次次 聚聚 类类 法法6.3.1层次聚类法概述层次聚类法概述层次聚类法(Hierarchical Clustering Method)又称为系统聚类法,是一种常用的聚类方法。这种方法的基本思想是:首先将N个样本各自看成一类,计算类与类之间的距离,选择距离最小的一对合并成一个新类;计算新类和其他类之间的距离,再将距离最近的两类合并;这样每次减少一类,直至所有的样本划分成两类为止,或者直到满足分类要求。第章聚类分析层次聚类算法的具体步骤如下:(1)初始分类。假设有N个样本,每个样本自成一类,则有N类:G01,G02,G0N(Gki表示第k次合并时的第i类,此步k=0)。
17、(2)计算各类之间的距离,得mm维的距离矩阵Dk,m为类别个数(初始时m=N,k=0)。(3)已求得距离矩阵Dk,找出Dk中类间距离最小的元素,如果它对应着Gki和Gkj,则将类Gki与Gkj合并为一类,由此得到新的分类Gk+11,Gk+12,并令m=m1,计算距离矩阵Dk+1。第章聚类分析 (4)若Dk+1中类间距离最小值大于距离阈值T,则算法停止,所得分类即为聚类结果(或者,如果所有的样本被聚成两类,则算法停止);否则转(3)。层次聚类法将样本逐步聚类,类别由多到少。层次聚类算法的特点是在聚类的过程中类心不断地调整,但样本一旦划到某个类以后就不会再改变了。第章聚类分析6.3.2类与类之间的
18、距离类与类之间的距离层次聚类算法中,需要计算各类之间的距离构成距离矩阵。类与类之间的距离有许多定义的方法,例如可定义为两类之间最近的距离,或者定义为两类重心之间的距离等,采用不同的定义就产生了层次聚类的不同过程。下面介绍常用的8种类间距离定义方法。第章聚类分析1.最短距离法最短距离法用dij表示样本xi和样本xj之间的距离,G1,G2,表示类,定义类与类之间的距离为两类相距最近的样本之间的距离,用Dpq表示类Gp与类Gq的距离,则,minipjqpqijGGDdxx(6-23)若Gpq是Gp与Gq合并而得,则递推可得Gi与Gpq的距离为,min,iqippqiDDD(6-24)第章聚类分析2.
19、最长距离法最长距离法最长距离法就是类与类之间的距离用两类样本之间最远的距离来表示,即,maxipjqpqijGGDdxx(6-25)若Gpq是Gp与Gq合并而得,则递推可得Gi与Gpq的距离为,max,iqippqiDDD(6-26)第章聚类分析3.中间距离法中间距离法设某一步将Gp与Gq合并为类Gpq,需要计算Gpq与任意一类Gi的距离。不失一般性,假设DiqDip。按最短距离法,Di,pq=Dip;按最长距离法,Di,pq=Diq。如图6-3所示,三角形的三个边是Dip、Diq、Dpq,直观上看,在Dip与Diq之间,选择边Dpq的中线为好。第章聚类分析图6-3 中间距离法示意图 第章聚类
20、分析由初等几何可知,中线长度的平方等于 222412121pqiqipDDD。若把这个中线长度作为类Gpq与类Gi之间的距离Di,pq,则有递推公式:2222,412121pqiqippqiDDDD(6-27)Di,pq介于最短距离和最长距离之间。第章聚类分析由于式(6-27)中出现的全是距离的平方,为了计算方便,在层次聚类中,若采用中间距离法,一般用距离的平方代替距离,进行比较。中间距离法还可以推广为更一般的形式,即2222,2121pqiqippqiDDDD(6-28)其中,1/40。第章聚类分析4.重心法重心法重心法用一个类的重心(该类样本的均值)代表该类,类与类之间的距离就用重心之间的
21、距离来表示。设Gp与Gq的重心分别是xp和xq,则Gp与Gq之间的距离是Dpq=d(xp,xq)。设某一个类Gp与Gq的重心分别是xp和xq,它们的样本数分别为np与nq,将类Gp与Gq合并为Gpq,则类Gpq的样本数为npq=np+nq,它的重心xpq为ppqqpqpqnnnxxx(6-29)第章聚类分析进一步假设类Gi的重心为xi。采用欧氏距离时,类Gi与Gpq的距离满足:22,(,)()()22Ti pqipqipqipqTppqqppqqiipqpqpqTTTiiipiqpqpqDdnnnnnnnnnn x xxxxxxxxxxxx xx xx x22212TTTppppqpqqqqp
22、qnn nnnx xx xx x(6-30)第章聚类分析其中,TTpiiqiiTiipqnnnx xx xx x(6-31)则2222,pqpqqpqpiqpqqippqppqiDnnnnDnnDnnD(6-32)式(6-32)是重心法的递推公式。第章聚类分析5.类平均距离法类平均距离法类平均距离法是将两类之间的距离平方定义为这两类样本两两之间的距离平方的平均,即 22,1ipjqpqijGGpqDdn nxx(6-33)将类 Gp与 Gq 合并为 Gpq,由式(6-33)可得,类Gk与Gpq的距离平方为 2222,11ikjpqikjpikjqk pqijijijGGGGGGkpqkpqDd
23、ddn nn nxxxxxx(6-34)第章聚类分析于是,类平均距离法的递推公式为222,kqpqqkppqppqkDnnDnnD(6-35)类平均距离法充分利用各样本的信息,从而成为层次聚类法中效果比较好的方法之一。6.可变类平均法可变类平均法可变类平均法是在类平均距离法的递推公式(6-35)中加入Dpq的影响,把递推公式修正为 第章聚类分析2222,)1()1(pqkqpqqkppqppqkDDnnDnnD(6-36)1()7.可变法可变法可变法是在中间距离法的推广递推公式(6-28)中将前两项的系数也依赖于,即2222,)1(21pqkqkppqkDDDD(6-37)可变类平均法与可变法
24、的分类效果依赖于的选择,有一定的主观性,在实际中使用并不多。第章聚类分析8.离差平方和法离差平方和法设将N个样本分成k类G1,G2,Gk,用xit表示Gt中的第i个样本,nt表示Gt中的样本个数,xt是Gt的重心,则在Gt中的样本的类内离差平方和为 1tnTtittittiSxxxx(6-38)聚类过程中,将两类合并,离差平方和就会增大。把两类合并所增加的离差平方和定义为两类距离平方,即将类Gp与Gq合并为Gpq时,定义D2pq=SpqSpSq,且有第章聚类分析2()()pqTpqpqpqpqn nDnxxxx(6-39)可以证明,离差平方和法有递推公式如下:2222,pqpqkkkqpqkq
25、kkppqkpkpqkDnnnDnnnnDnnnnD(6-40)公式中各符号意义同前。第章聚类分析以上给出了8种类与类之间的距离,并且得到不同的递推公式,这些递推公式具有统一的形式:222222,kqkppqkqqkpppqkDDDDDD(6-41)其中,系数p、q、对于不同的方法有不同的取值。表6-2列出了上述8种方法中四个参数的取值。第章聚类分析表表6-2递推公式中的参数递推公式中的参数 方法pq最短距离法1/21/20-1/2最长距离法1/21/201/2中间距离法1/21/400重心法np/npqnq/npq-pq0类平均距离法np/npqnq/npq00可变类平均法10可变法(1)/
26、2(1)/210离差平方和法0pqpnn)1(pqpnn)1(pqkpknnnnpqkpknnnnpqkknnn第章聚类分析6.4动动 态态 聚聚 类类 法法6.4.1动态聚类法的基本思想动态聚类法的基本思想在层次聚类法中,样本一旦归入某个类以后就不再改变了,因此要求分类方法的准确度要高。动态聚类法就是,先选择一些初始聚类中心,让样本按某种原则划分到各类中,得到初始分类;然后,用某种原则进行修正,直到分类比较合理为止。动态聚类法的流程框图如图6-4所示,其中,每一部分都有很多种方法,不同的组合方式可得到不同动态聚类算法。动态聚类法有三个要点:第章聚类分析(1)选定某种相似性测度作为样本间的相似
27、性度量;(2)确定某个评价聚类结果质量的准则函数;(3)给定某个初始分类,用迭代的算法找出使准则函数取极值的聚类结果。下面简要介绍几种典型的动态聚类法:K均值算法和迭代自组织的数据分析算法,以及基于LBG算法的聚类分析。第章聚类分析图6-4 动态聚类法的流程框图第章聚类分析6.4.2K均值算法均值算法K均值算法使用的聚类准则函数是误差平方和准则,通过反复迭代优化聚类结果,使所有样本到各自所属类别的中心的距离平方和达到最小。K均值算法的步骤如下:(1)任选K个初始聚类中心:z(1)1,z(1)2,z(1)K,其中,上角标表示聚类过程中的迭代运算次数。(2)假设已进行到第r次迭代。若对某一样本x有
28、第章聚类分析()()(,)min(,),1,2,rrjiddiKx zx z(6-42)则xS(r)j。其中,S(r)j是以z(r)j为聚类中心的样本子集。以此种方法,即最小距离原则,将全部样本分配到K个聚类中。(3)计算重新分类后的各聚类中心:()(1)()1rjrjrSjnxzx1,2,jK(6-43)式中,n(r)j为S(r)j中所包含的样本数。第章聚类分析(4)若z(r+1)j=z(r)j,j=1,2,K,则结束;否则转(2)。因为在第(3)步要计算K个聚类的样本均值,故称做K均值算法。该算法的特点是选一批代表点(初始聚类中心)后,计算所有样本到聚类中心的距离,将所有样本按最小距离原则
29、划分类别,形成初始分类,再重新计算各聚类中心,这是一种批处理方法。另一种方法是逐个处理法,每读入一个样本就把它归于距离最近的一类,形成新的分类并计算新的聚类中心,然后再读入下一个样本归类,即每个样本的归类都改变一次聚类中心。第章聚类分析K均值算法的分类结果与所选聚类中心的个数K和初始聚类中心选择有关,因此在实际应用中需试探不同的K值和选择不同的初始聚类中心。初始聚类中心的选取方法一般有如下几种:(1)用样本集的前K个样本作为初始聚类中心。(2)将全部样本随机分成K类,计算每类重心,把这些重心作为每类的初始聚类中心。(3)凭经验选初始聚类中心。根据问题的性质、数据分布,选择从直观上看来较合理的K
30、个初始聚类中心。第章聚类分析(4)按密度大小选代表点。以每个样本作为球心,以d为半径作球形,落在球内的样本数称为该点的密度,并按密度大小排序。首先选密度最大的样本点作为第一个代表点,即第一个初始聚类中心。再考虑第二大密度点,若第二大密度点距第一个代表点的距离大于d1(预先规定的一个正数),则把第二大密度点作为第二个代表点,否则不能作为代表点。这样按密度大小依次考察下去,选择K个样本作为初始聚类中心。第章聚类分析(5)将相距最远的K个样本作为初始聚类中心。此外,K均值算法的分类结果受到样本的几何性质和读入次序的影响。如果样本的几何特性能使它们形成几个相距较远的孤立区,那么算法一般能够收敛。【例例
31、 6.2】模式分布如图6-5所示,试用K均值法进行聚类。取K=2。第章聚类分析图 6-5K均值算法例题样本集 第章聚类分析解解(1)选取z(1)1=x1=(0,0)T,z(1)2=x2=(1,0)T。(2)因为x1z(1)1x2z(1)2,所以x2S(1)2;因为x3z(1)1x3z(1)2,所以x3S(1)1;得S(1)1=x1,x3(3)计算新的聚类中心(1)224567891011121314151617181920,S xxx xxx xxxxxxxxxxxx第章聚类分析(1)1(2)113111()(0,0.5)2TSNxzxxx(1)2(2)22420211(.)(5.67,5.3
32、3)18TSNxzxxxx(4)因为z(2)iz(1)i,i=1,2,所以回到(2)按新的聚类中心重新分类(用(2)表示)。第章聚类分析(2)由新的聚类中心,有(2)(2)1112xzxz，所以(2)11Sx(2)(2)2122xzxz，所以(2)21Sx得(2)112345678,S x xx xx xxx(2)291011121314151617181920,S x xxxxxxxxxxx第章聚类分析(3)计算新的聚类中心(2)1(3)111(1.25,1.13)TSNxzx(2)2(3)221(7.67,7.33)TSNxzx(4)因为z(3)iz(2)i,i=1,2,所以回到(2)(用
33、(2)表示)。第章聚类分析(2)按新的聚类中心进行分类,分类结果与上一次迭代相同S(3)1=S(2)1,S(3)2=S(2)2。(3)计算聚类中心。(4)因为聚类中心与上一次相同,算法结束。第章聚类分析6.4.3迭代自组织的数据分析算法迭代自组织的数据分析算法迭代自组织的数据分析算法(Iterative SelfOrganizing Data Technique Algorithm)简称ISODATA算法。类似于K均值算法,ISODATA算法的聚类中心也是通过样本均值的迭代运算来决定的。与K均值算法不同的是,ISODATA算法增加了一些试探性步骤和人机交互的“自组织”处理方式,在迭代过程中可将
34、一类分成两类,亦可能将两类合为一类,即分裂和合并处理。迭代自组织算法流程图如图6-6所示。第章聚类分析图6-6 迭代自组织算法流程图第章聚类分析ISODATA算法的具体步骤如下:(1)读入包含N个模式的样本集x1,x2,xN,选择m个初始聚类中心z1,z2,zm。其中,m不一定等于预期的聚类中心数目。参数设计如下:K预期的聚类中心数目;N 一个聚类中最少的样本数目,即如少于此数就不作为一个独立的聚类;s聚类中样本单个分量的标准方差的上限,若某个聚类中样本单个分量的标准方差的最大值大于此数,则可能分裂该聚类的中心。第章聚类分析c两聚类中心之间的最小距离,如小于此数,合并两个聚类;L在一次迭代过程
35、中,最多可以合并的聚类中心的对数;I最大的迭代次数。(2)根据最小距离准则,将样本x1,x2,xN分别归入最近的聚类,若(,)min(,),1,2,jjiDddimx zx z(6-44)第章聚类分析即距离d(x,zj)最小,则xSj。其中,Sj是以zj为聚类中心的样本子集。(3)如果Sj(j=1,2,m)中的样本数目Njs(该值给定),同时又满足以下两个条件中的一个:和Nj2(N+1),即Sj中样本总数超过规定值的一倍以上;mK/2,jDD第章聚类分析则将Sj的中心zj分裂为两个新的聚类中心z+j和zj,且令m=m+1,其中,z+j和zj的计算如下:选定一个p值,0p1;令j=pj或j=(0
36、,pj,max,0)T;z+j=zj+j,zj=zjj。如果本步完成了分裂运算,则转入(2),否则转入(11)。第章聚类分析合并处理:(11)计算全部聚类中心之间的距离:(,)ijijDdz z1,2,1im1,jim ；(6-50)(12)比较Dij与c值,将Dijc的前L个值递增排列,即,2211LLjijijiDDD其中,Di1j1Di2j2DiLjL。第章聚类分析(13)从最小的Di1j1开始,对于每个Diljl,合并相应的两个聚类中心zil和zjl,新的聚类中心为 lllllliijjlijNNNNzzz1,2,lL(6-51)并令m=mL。(14)如果迭代运算次数已达最大的迭代次数
37、I,即最后一次迭代,则算法结束;否则,如果需要由操作者改变输入参数,转入(1),设计相应的参数;否则,转入(2)。到了本步运算,迭代运算的次数加1。第章聚类分析6.4.4基于基于LBG算法的聚类分析算法的聚类分析LBG算法是K均值算法的推广。LBG算法是矢量量化中的一种重要码书生成算法,先选取初始码书,通过对训练样本的量化、聚类、迭代,产生局部最优的码书。这里,把LBG算法应用于聚类分析,具体步骤如下:(1)设样本集为x1,x2,xN。给定初始聚类中心z(0)i|i=1,2,K,并置r=0,设起始平均失真D(-1),给定计算停止门限(00,i为样本矢量中第i个分量的标准方差,i=1,2,d。=
38、(1,2,d)T,其中,比例因子0,为样本矢量协方差矩阵的最大的特征值所对应的特征向量。第章聚类分析习题习题6-1证明离差平方和法有如下递推公式:2222,pqpqkkkqpqkqkkppqkpkpqkDnnnDnnnnDnnnnD6-2证明在动态聚类算法中当样本x移入聚类j后的集合为,则移入前后的误差平方和变化为j第章聚类分析2|1jjjjjNJJNmx其中:Jj与分别为j与的误差平方和;Nj为j的样本数;mj为j的均值向量。6-3设有样本集X=(0,0)T,(0,1)T,(1,0)T,(4,4)T,(4,5)T,(5,4)T,(5,5)T,试用最大最小距离聚类算法对样本集分类。jj第章聚类分析6-4对6-3题中的样本集X,试用层次聚类算法对样本集分类。6-5设有五个六维样本:x1=(0,1,3,1,3,4)T,x2=(3,3,3,1,2,1)T,x3=(1,0,0,0,1,1)T,x4=(2,1,0,2,2,1)T和x5=(0,0,1,0,1,0)T,试按最短距离法进行层次聚类分析。6-6对6-3题中的样本集 X,试用 K 均值算法对样本集分类。6-7对6-3题中的样本集 X,试用ISODATA算法对样本集分类。
