模式识别导论6.ppt

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