模式识别导论本(四).ppt

第四讲聚类分析按距离聚类的概念模式相似性测度与聚类准则聚类算法对聚类的评价,AnoldChinesesaying:物以类聚，人以群分,引言没有训练样本存在，属于非监督分类。目的是将一批数据（模式）组成一些“有意义”的集合（聚类）这个思想在生物学、社会学、医学、地球科学等学科都是很常见的下面举一个生物学中的例子：设我们有下列动物：羊，狗，猫，麻雀，海鸥，小毒蛇，金鱼，红色mullet（一种小海鱼，可以吃），蓝色鲨鱼和青蛙。为将它们分成不同的类别，我们需要一定的准则。如果我们不同的准则来聚类，可以形成不同的结果，如下面所示,羊、狗、猫、鲨鱼,麻雀、海鸥、小毒蛇、金鱼、青蛙、红mullet,以产后代的方式分,金鱼、红mullet、鲨鱼,羊、麻雀、狗、海鸥,以肺是否存在分,金鱼、红mullet、鲨鱼,羊、麻雀、狗、海鸥,青蛙,以生活环境分,麻雀、青蛙、海鸥、小毒蛇,羊、狗、猫,鲨鱼,金鱼、红mullet,以产后代的方式和是否有肺联合标准来分,这个例子说明两个问题：聚类在生物分类中很常见，不同的准则结果有很大的差别人类总是将获取的信息在聚类，否则，不可能处理每个信息。然后根据每个类的共同特征来表征这个类。比如当我们看见草地上一条狗的时候，我们会推断它的叫声，因为狗叫声作是一个共同特征聚类过程如下：特征的选择相似性度量聚类准则聚类算法聚类评价聚类结果的解译,按距离聚类的概念所谓聚类分析就是根据模式的特征空间分布，按点间距离的大小确定其相似程度，进而进行归类工作的，一般说来，可以认为每类模式都聚集在一个有代表性的或典型的模式周围，这个有代表性的模式称为聚类中心，或称为标准模式,若有M个类别,其标准模式分别为,，任一模式x与第,类标准模式间的距离表示为,聚类分析就是按照这种距离函数（或者更加广义的相似性度量）来进行归类处理，由于以最小距离为准则，故可以认为聚类分析的分类器是最小距离分类器,？,不考虑无关项，上面的式子可以转化为：,设模式特征空间为n维空间，即有,可见最小距离分类器是线性分类器的特殊情况,模式相似性测度与聚类准则,同一类模式的特征数据都是相近的或相同的，这一性质称为模式的相似性。这种相似性用什么公式来表达，也就相似性测度问题。式（4-1-1）是用距离函数来表示对相似性的度量，它是一种常用的测度。一般用于模式识别的相似性测度有如下几种（1）明氏（Minkowaski）距离n维模式向量与之间的明氏距离为,称为“城市街坊距离”（“cityblock”distance）。当m=2时，即式（4-1-1），它又称为欧氏距离。,当,时，称为切比雪夫距离,（2）马氏（Mahalanobis）距离,第一类,第二类,其中m为均值向量，C为协方差矩阵欧氏距离和马氏距离之间的差别：,欧氏距离来说应该是属于第一类,例子：二维两类问题，设都服从正态分布，协方差矩阵一样,计算向量到这两类的欧氏距离和马氏距离,可见，给定的向量和第一类的中心比较近。但如果从欧氏距离类看，则是相反的，下图,（3）向量夹角余弦,它反映了几何相似性，在模式向量具有扇形分布时常采用这种测度,当模式特征向量各分量取0、1二值时，常采用此式,二、聚类准则,当采用某一相似性测度如欧氏距离对所有模式进行判别时，将距离数值计算出来，必须确定一个阈值，在小于此阈值时，判为同类，否则在大于它时，定为异类。怎样确定阈值才比较正确、合理，这就是聚类准则问题。一般有两种方式来确定这一准则（1）经验法根据经验和直观，确定相似性度量中的阈值，或在确定这些阈值后试行分类，视结果对尚不够合理的阈值加以调整、修正，直至满意为止。这就是所谓经验法，或称为试探法。,（2）函数法这是根据理论分析确定阈值的方法，它采用聚类准则函数进行分析。这种准则函数有许多，下面介绍三种准则。误差平方和准则对于C类模式，准则函数为,当J最小时，认为聚类合理。在各类样本密集，类别间分离明显时，最宜采用这一准则,与最小方差有关的准则,它是,类中所有点间距离平方的均值，相似性算子,也可以由其它形式取代，如夹角余弦算子。这一准则也是以J最小作为判断聚类合理的依据,散布准则,并定义类间散布矩阵为,总体散布矩阵为,可以推出,推导过程如下：,准则函数根据各种散布矩阵的“大小”来定义。度量矩阵“大小”可按矩阵迹（矩阵对角线元素之和）进行。例如,当J最小时，也就是类内散布矩阵迹最小时，认为聚类合理。同样可以定义,当J最大时，即类间散布矩阵迹最大时，认为聚类合理,聚类算法,在选择了某一聚类准则函数J之后，需要对模式总体进行分类，并计算J值。对于不同的阈值，各种可能的分类结果，都要计算J值，以求达到最优。这样做需要大量计算，实际上是不可能的。一般采取一些被认为是可以达到最优结果的聚类算法一、简单搜索算法,对N个待分类的模式样本集合,首先任意选择一个样本,作为第一个聚类中心,并确定一个非负阈值T，一般为方便起见，令,继续搜索，直至得到N个样本的所有聚类中心,这种算法与阈值T的大小、第一个聚类中心的选择、模式样本的排列次序和样本分布的几何特性有关。阈值T较大时，聚类数较少，T较小时，得到的类别数就很多。图4-3-1说明了T值大小对聚类结果的影响。阈值T确定之后，第一个聚类中心的选取不同，结果也不相同（如图4-3-1(e)、(d)）。因此，当对于模式样本的几何分布有所了解之后，就可以合理地确定阈值T和第一个聚类中心，得到较为满意的结果。一般低于四维的分布容易得到演示，高维分布则不可能直观地表示出来，这时只能根据具体情况，选用不同的阈值和起始点进行试探，根据聚类结果调整，或在进行某些数值分析后重新确定阈值和起始点。这种方法对于只需要某种粗略聚类的问题来说，是简单快速的方法,二、最大的最小距离算法这种方法以类间欧氏距离最大作为选择聚类中心的条件。下面以图为例，说明其基本思想。图4-3-2中有10个二维样本。现按最大的最小距离算法作聚类分析,第一步，任选一模式样本作为第一聚类中心。这里令,第二步，确定离,距离最远的样本作为第二聚类中心,第三步，逐一计算各样本与,间的距离，即,并确定,中最小值，即,即在,中的最大值如果超过,间距离的一半的,就定为第三聚类中心,第四步，有,存在，计算,同样，若此最大值大于,则存在,，否则聚类中心的搜寻计算结束。由于此例中找不到满足上述条件的最大值，故停止搜寻聚类中心第五步，对所有模式样本，逐一计算它们到三个聚类中心的距离，归入到距离小的类中心对应的类中,两步曲：用距离最大原则寻找聚类中心用距离最小原则将剩余的样本归入到相应的类别中,上例中三类分别为：,三、K均值算法以上算法是逐一搜索确定聚类中心，下面介绍的，则是首先确定若干初始聚类中心，然后依一定算法改变或调整这些中心，使它们逐步趋于合理K均值算法要求各类样本到聚类中心的距离平方和最小，它是在误差平方和准则的基础上建立起来的（1）任选K个初始聚类中心一般以开头K个样本作为初始中心,（2）逐个将模式样本集的每一样本按最小距离原则分配给K个聚类中心，形成K个类群，即在第m次迭代时，若,则,，这里,表示第m次迭代时，以第j个聚类中心为代表的聚类域。,（3）由（2），计算新的聚类中心，即,式中,为第,个聚类域,中的样本个数。其均值向量作为新的聚类中心，因为这样可以使误差平方和准则函数,达到最小值,（4）若,算法收敛，计算完毕。否则回到（2），进行下一次迭代。例2图4-3-3所示为二维模式样本的分布，现用K均值算法分类第一步：取K=2，令第二步,第三步：计算新的聚类中心,第四步：,故回到第二步,(第二轮）第二步：按新的聚类中心分类，有,(第二轮）第三步：计算聚类中心,第四步：因,回到第二步,（第三轮）第二步：求得,第三步：聚类中心与前一次迭代结果相同,第四步：因,故算法收敛,与初始聚类中心的确定有关,四、ISODATA算法ISODTA意为迭代自组织数据分析技术。这个算法与K均值算法相似，也是以均值迭代确定聚类中心，但它加进了人机对话环节，可以调整参数，并且引入了归并与分裂的机制，即当某两类别中心间距小于某一阈值时，将它们合并为一类，而在某类样本标准差大于某一阈值时，或其样本数目超过某一阈值时，则将它分为两类，在类别数目少于某一阈值时，也实行分裂。另外，在某类样本数目少于某阈值时，又需要将其消除。因此，这种方法灵活性更强，更为合理。该算法需要确定并在计算中可以调整的参数有：,K:所要求的聚类中心数。,一个类别至少应具有的样本数目。,一个类别样本标准差阈值。,聚类中心之间距离的阈值，即归并系数。,L:在一次迭代中可以归并的类别的最多对数。I:允许迭代的最多次数。这一算法的步骤如下：,第一步：对于N个模式样本的集合，确定C个初始聚类中心C不一定等于K。这些聚类中心可为模式集合中的任意样本。,第二步：确定上述六个参数，即,第三步：将N个样本按最小距离分类，即若,第四步：若对于某一聚类域fj，其样本数目,则取消该子集,和,并且C=C-1，即类别数减少1，,第五步：修正各聚类中心值：,转入第3步,第六步：对每一聚类域fj，计算其所有样本到其聚类中心的距离的平均值。,第七步：计算所有样本到其相应聚类中心的距离的平均值。,第八步：若迭代次数达到I次，置,转入第十二步，运算结束；,若,即聚类中心数目等于或不到规定数目的二分之一，则转入第九步，以对现有类别进行分裂；,若C=2k,跳过分裂，转12，否则转下,若k/2C2k,当迭代次数是奇数转第九步（分裂），迭代次数为偶数时，转12步（合并）,第九步：计算每一类别中样本与聚类中心距离的标准差向量：,其中每一分量为,这里n为模式样本的维数,第十步：对每一标准差向量,求其最大分量,用S记下它是第几分量。,第十一步：在最大分量集中,并且满足下列条件之一：,ThesplittingiscontrolledbyparameterMwhichensuresnoticeablebutNotdramaticchangeinclustercentersarrangement,分裂完毕，转入第三步。如果没有可分裂的类别，则继续。第十二步：计算每两个聚类中心之间的距离：,第十五步：如果是最后一次迭代计算（即第I次），算法结束。否则，如果需要改变参数则转入第二步，不需要改变参数则转入第三步。,例3，图4-3-5所示的模式表明N=8，n=2。现用ISODATA算法进行聚类分析参考教材模式样本的选取和初始聚类中心的确定待识别分类的模式集合有时是一个很大的集合，如遥感数字化影像等。而在采取聚类分析方法时，大都进行迭代计算，若将所有模式反复进行迭代计算，是不经济的。为此，需要进行抽样，在样本集合中先实施迭代，以确定各类中心，然后对模式集合的全体进行分类。另一方面，迭代计算的初始聚类中心的确定往往具有一定的盲目性，如何尽可能减少这种盲目性的程度，也成为一个课题。,ItisneedlesstosaythatasuccessfulimplementationofISODATAongeneralpatternsets,requiresextensiveexperimentationsinordertoobtaintheappropriatevaluesofparameterssuchas,ItshouldbenotedthatusingISODATAwithinappropriateparametersmayleadtoosci