模式识别导论6

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 聚类分析,6,1,分类与聚类的区别,分类：用已知类别的样本训练集来设计分类器（监督学习）,聚类（集群）：用事先不知样本的类别，而利用样本的先验,知识来构造分类器（无监督学习）,1,6-2,系统聚类,系统聚类：先把每个样本作为一类，然后根据它们间的相,似性和相邻性聚合。,相似性、相邻性一般用距离表示,（,1,）两类间的距离,1,、最短距离：两类中相距最近的两样品间的距离。,2,2,、最长距离 ：两类中相距最远的两个样本间的距离。,3,、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。设,1,类和,23,类间的最短距离为,d,12,，,最长距离为,d,13,，,23,类的长度为,d,23,，,则中间距离为：,上式推广为一般情况：,3,4,、重心距离：均值间的距离,5,、类平均距离：两类中各个元素两两之间的距离平方相加后取平均值,4,6,、 离差平方和：,设,N,个样品原分,q,类，则定义第,i,类的离差平方和为：,离差平方和增量：设样本已分成,p,q,两类，若把,p,q,合为,r,类，则定义离差平方：,5,（,2,）系统聚类的算法,设参加聚类的样本共,N,个，先选定样本间距离和类间距离的计算公式，再按以下步骤聚类。,1,、假定,N,个样本各成一类，记作,1,2,N,。,2,、作距离矩阵,D(0),因,D(0),矩阵是对称的,NN,矩阵，我们只计算下三角部分，第,i,行第,j,列处的元素,d,ij,用,i,和,j,两样本的距离平方表示。,6,3,、求,D(0),的最小元素,d,pq,min,d,ij,pq,因此，,p,和,q,是目前最近的两类。,4,、把,p,与,q,合并成新的类，并求新类与原有其它各类间的距离。,5,、作下一距离矩阵,D(1),。,6,、,若分的类数已满足预先要求或全部样本已合成一类，则算法结束。否则，重复以上步骤。,1,2,2,3,d,2,ij,.,7,例：有六个样本,X=,x,1,x,2,x,3,x,4,x,5,x,6,其分布如下图所示 ：,1,、设全部样本分为,6,类，,2,、作距离矩阵,D(0),1,2,3,4,5,2,9,3,1,16,4,49,16,64,5,25,4,36,4,6,64,25,81,1,9,8,3,、求最小元素：,4,、把,1,3,合并,7,=(1,3),4,6,合并,8,=(4,6),5,、,作距离矩阵,D(1),7,2,8,2,9,8,49,16,5,25,4,4,9,6,、若合并的类数没有达到要求，转,3,。否则停止。,3,、求最小元素：,4,、,8,5,2,合并,9,=,（,2,5,4,6,）,10,6-2,分解聚类,分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。,目标函数 两类均值方差,N,：,总样本数，,：,1,类样本数,：,2,类样本数，,11,分解聚类框图,：,初始分类,调整分类方案,最终结果,目标函数,达到最优否,？,12,对分,算法：,1,、选取目标函数，把全体样品分成两类,2,、分别计算把,x,1,x,2,x,N,并入,G,2,类时的,E,值，设当,x,i,并入,G,2,时的,E,值最大，则把它并入,G,2,得,:,3,、再分别计算把,x,1,x,i,-1,x,i,+1,x,N,并入,G,2,的,E,值，若当,x,j,并入,G,2,时,E,最大，则并入,G,2,得：,13,4,、若,E(k+1)E(k),则重复上述步骤，直到某个,E(K),达到最大值为止。这时最好的分类是,G,1,(k),共有,n-k,个样品，,G,2,(k),有,k,个样品。,每次分类后都要重新计算 之值。可用以下递推公式：,14,例：已知,21,个样本，每个样本取二个特征，原始资料矩阵如下表：,样本号,1,2,3,4,5,6,7,8,9,10,x,1,0,0,2,2,4,4,5,6,6,7,x,2,6,5,5,3,4,3,1,2,1,0,11,12,13,14,15,16,17,18,19,20,21,-4,-2,-3,-3,-5,1,0,0,-1,-1,-3,3,2,2,0,2,1,-1,-2,-1,-3,-5,15,解：第一次分类时计算所有样本，分别划到,G,2,时的,E,值，找出最大的。,1,、开始时，,目标函数,2,、分别计算当,x,1,x,2,.,x,21,划入,G,2,时的,E,值。把,x,1,划入,G,2,时有：利用递推公式,16,然后再把,x,2,.,x,21,划入,G,2,时对应的,E,值，计算出来进行比较，找出一个最大的,E,值。即把,x,21,划为,G,2,的,E,值最大。,再继续进行第二，第三次迭代,计算出,E(2),E(3),如下表：,17,18,第,10,次迭代,x,1,划入,G,2,时，,E,最大。于是分成以下,两类：,19,作业：,样本,1 2 3 4 5 6 7 8,0 2 1 5 6 5 6 7,0 2 1 3 3 4 4 5,用对分法编程上机，分成两类画出图形。,20,6-3,动态聚类,兼顾系统聚类和分解聚类,一、动态聚类的方法概要, 先选定某种距离作为样本间的相似性的度量,;,确定评价聚类结果的准则函数,;,给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果,。,21,选代表点,初始分类,分类合理否,最终分类,修改分类,Y,N,动态聚类框图,二、代表点的选取方法,代表点就是初始分类的聚类中心数,k,。,凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的代表点,k;,将全部样本随机分成,k,类，计算每类重心，把这些重心作为每类的代表点,;,22, 按密度大小选代表点：,以每个样本作为球心，以,d,为半径做球形,;,落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于,d,1,（,人为规定的正数）则把第二大密度点作为第二代表点，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于,d,1,。,d,1,太小，代表点太多，,d,1,太大，代表点太小，一般选,d,1,2d,。,对代表点内的密度一般要求大于,T,。,T0,为规定的一个正数。, 用前,k,个样本点作为代表点。,23,三、初始分类和调整, 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。, 选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。, 直接用样本进行初始分类，先规定距离,d,把第一个样品 作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于,d,，,就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于,d,，,决定分裂还是合并。,24,最佳初始分类,初始分类数,k,的确定有时是不准确的。假设,k,是逐渐增加的。如图所示，,准则函数下降很快，经过拐点,A,后，下降很慢。说明拐点附近对应的,k,，,比较接近最佳的初始分类。就是最佳初始分类。,25,四、,K,次平均算法：,这是一种常用的动态聚类方法，修改聚类中心的准则函数为（所有样本到聚类中心的距离平方和相加）,其中,G,j,是第,j,个聚类，,N,j,是第,j,个聚类中的样本数，,Z,j,为第,j,个聚类的聚类中心。,K,均值算法的聚类准则是：聚类中心,Z,j,的,选择应使准则函数的,J,j,值,最小。因此，令,26,上式表明，,G,j,类的聚类中心应选在该类样本的均值,第一步：任选,k,个初始聚类中心,Z,1,(,l,), Z,2,(,l,),.,Z,k,(,l,),第二步：计算每个样本到,k,个聚类中心的距离，并按最近规则 归类。,其中,G,j,(,k,),为,聚类中心,Z,j,(,k,),的样本聚类。在第,k,次迭代，分配各个样本,x,到,k,个聚类中心。,27,第三步：从第二步的结果，计算新的聚类中心。,上面已经证明，该新聚类中心可以使准则函数的,J,j,值最小。,第四步：若新聚类中心与前一个聚类中心相等，即,Z,j,(,k+,1) =,Z,j,(,k,) j=1,2,.k,则,算法收敛，聚类结束。否则，转第二步。,28,例：已知有,20,个样本，每个样本有,2,个特征，数据分布,如下图,第一步：令,K=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,29,30,31,32,第三步：根据新分成的两类建立新的聚类中心,第四步：,转第二步。,第二步：重新计算 到,z,1,(2) , z,2,(2),的距离，把它们归为最近聚类中心，重新分为两类，,33,第三步，更新聚类中心,34,第四步，,第二步，,第三步，更新聚类中心,35,上机作业,已知十个样本，每个样本,2,个特征，数据如下：,用,K,次,平均算法和,ISODATA,算法分成,3,类，编程上机，并画出分类图。,样本序号,1 2 3 4 5 6 7 8 9 10,x,1,0 1 2 4 5 5 6 1 1 1,x,2,0 1 1 3 3 4 5 4 5 6,36,五、,ISODATA,算法,(,迭代自组织数据分析算法）,ISODATA,算法与,K,均值算法有相似之处，即聚类中心根据样,本的均值来修改。不同的是，这种算法进行的过程中聚类中心的,数目不是固定不变而是反复进行修改。聚类既有合并也有分裂，,合并与分裂是在一组预先选定的参数指导下进行的。此外，一些,经验结果也包含在算法中。,ISODATA,算法共分十四步。其中第一步到第六步是预选参,数、进行初始分类，并为合并和分裂准备必要的数据；第七步,决定下一步是进行合并还是进行分裂；第八步到第十步是分裂算,法，第十一步到第十三步是合并算法，第十四步决定算法是否结,束。算法的具体步骤如下：,37,设有,N,个样本模式,X,1,，,X,2,，,X,N,第一步：预选,N,C,个聚类中心,Z,1,，,Z,2,，,Z,NC,N,C,不,要求等于希,望的聚类数目。,N,C,个聚类中心也可在,N,个样本中选择。然后预,选下列指标：,K,：,K,是希望的聚类中心的数目。,N,：,每个聚类中最少的样本数。若某聚类中的样本少,N,，,则该聚类不能作为一个独立的聚类，应删去。,S,：,一个聚类中样本的标准偏差参数。要求每一个聚类内,标准偏差向量的所有分量中的最大分量小于,S,，,否则该类,应分裂为两类。标准偏差向量的每一分量 等于每个样本的分,量与聚类中心对应分量差的平方和平均值。,C,：,两聚类中心之间的最小距离。若两类中心之间距离小于,C,，,则这两类合并为一类。,L,：,在一次迭代中允许合并的聚类中心的最大对数。,I,：,允许迭代的次数。,38,第二步：把,N,个样本按最近邻规则分配到,N,c,个,聚类中。,第三步：若,S,j,中的样本数,N,j,S,，,(,即,S,j,类样本在,jmax,对应方向上的标准偏差大于允许的值），同时又满足以下两条之一：,(1),和,N,j,2(,N,1),，,即类内平均距离大于总体平均距离，并且,S,j,类,中样本数很大。,(2) N,C,K/2,即聚类数小于或等于希望数目的一半。,本步完成后，跳回第二步，且迭代次数加,1,。,42,第,十一步：计算所有聚类中心之间的距离。,S,i,类和,S,j,类中心间的距离为,第十二步：比较所有,D,ij,与,C,的值，将小于,C,的,D,ij,按,升序排列：,D,i,1,j,1,D,i,2,j,2, ,D,iLjL,其中，,D,i,1,j,1,D,i,2,j,2, ,N,故无聚类可删除。,45,第四步：修改聚类中心，,第五步：计算,第六步：计算 。因只有一类，故,第七步：因不是最后一次迭代，且,N,C,K/2,，,故进入第八步进行分裂运算。,46,第八步：求,S,1,的标准偏差向量,1,，,得,1,=1.99,1.56,t,第九步：,1,的最大分量是,1.99,，因此，,1max,1.99,第十步：因,1max,S,且,N,C,K/2,，,可将,Z,1,分裂为两个新的聚类中心。因,1max,是,1,的第一个分量，即,S,1,中样本分布在,X,的第一个分量方向上较分散，故分裂应在,Z,1,的第一个分量方向上进行。分裂系数,k,选为,0.5,，得,47,为了方便，令 。这一步之后，,N,C,加,1,，迭代次数加,1,，即下面进行第,2,次迭代运算。跳回到第二步。,第二步：按最近邻规则对所有样本聚类，得到两个聚类分别为,S,1,=X,4,X,5, X,6,X,7, X,8,S,2,=X,1,X,2, X,3,N,1,=5,，,N,2,=3,第三步：因,N,1,和,N,2,都大于,N,，,无聚类可以删除。,第四步：修改聚类中心，得,48,第五步：计算 和 ，得,第六步：计算 ，得,第七步：因这是偶数次迭代，符合第七步的第,(3),条，故进入第十一步。,第十一步：计算聚类之间距离，得,49,第十二步：比较,D,12,与,C,，,这里,D,12,C,。,第十三步：根据第十二步的结果，聚类中心不能发生合并。,第十四步：因为不是最后一次迭代，需要判断是否要修改给定的参数。但前面的迭代运算结果已得到希望的聚类数目；聚类之间分散程度大于类内样本的标准差；每一聚类中样本数目都具有样本总数的足够大的百分比，且两类样本数相差不大，故可不必修改参数。因此，回到第二步，且迭代次数加,1,。,第二步到第六步：与前一次迭代运算的结果相同。,第七步：没有一种情况被满足，继续执行第八步。,50,第八步：计算,S,1,和,S,2,的标准偏差向量,1,和,2,。,这时,S,1,和,S,2,仍为,S,1,=X,4,X,5, X,6, X,7, X,8,S,2,=X,1,X,2, X,3,计算结果为：,1,=0.75,0.75,t,2,=0.82,0.82,t,第九步：,1max,0.75,，,2max,0.82,第十步：分裂条件不满足，故继续执行第十一步。,51,第,十一步：计算聚类中心之间的距离，结果与前次迭代计算结果相同。,第十二步、十三步：与前一次迭代结果相同。,第十四步：因不是最后一次迭代，且不需修改参数，故返回第二步。迭代次数加,1,。,第二到第六步：与前一次迭代结果相同。,第七步：因为是最后一次迭代，置,C,0,，,跳到第十一步。,第十一步：,第十二步：与前一次迭代结果相同。,第十三步：没有合并发生。,第十四步：最后一次迭代，故算法结束。,52,作业、有一样本集共七个样本为：,X,1,=0,0,t,X,2,=0,1,t,X,3,=4,4,t,X,4,=4,5,t,X,5,=5,4,t,X,6,=5,5,t,X,7,=1,0,t,试用,ISODATA,聚类算法编程上机分类，打印出分类图。,53,