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

《模式识别导论本(四)(精品).ppt》由会员分享，可在线阅读，更多相关《模式识别导论本(四)(精品).ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模式识别导论武汉大学遥感信息工程学院 马洪超第四讲 聚 类 分 析按距离聚类的概念模式相似性测度与聚类准则聚类算法对聚类的评价模式识别导论武汉大学遥感信息工程学院 马洪超An old Chinese saying:物以类聚，人以群分引言没有训练样本存在，属于非监督分类。目的是将一批数据（模式）组成一些“有意义”的集合（聚类）这个思想在生物学、社会学、医学、地球科学等学科都是很常见的下面举一个生物学中的例子：设我们有下列动物：羊，狗，猫，麻雀，海鸥，小毒蛇，金鱼，红色mullet（一种小海鱼，可以吃），蓝色鲨鱼和青蛙。为将它们分成不同的类别，我们需要一定的准则。如果我们不同的准则来聚类，可以形成

2、不同的结果，如下面所示模式识别导论武汉大学遥感信息工程学院 马洪超羊、狗、猫、鲨鱼麻雀、海鸥、小毒蛇、金鱼、青蛙、红mullet以产后代的方式分金鱼、红mullet、鲨鱼羊、麻雀、狗、海鸥以肺是否存在分金鱼、红mullet、鲨鱼羊、麻雀、狗、海鸥青蛙以生活环境分麻雀、青蛙、海鸥、小毒蛇羊、狗、猫鲨鱼金鱼、红mullet以产后代的方式和是否有肺联合标准来分模式识别导论武汉大学遥感信息工程学院 马洪超这个例子说明两个问题：聚类在生物分类中很常见，不同的准则结果有很大的差别人类总是将获取的信息在聚类，否则，不可能处理每个信息。然后根据每个类的共同特征来表征这个类。比如当我们看见草地上一条狗的时候，我

3、们会推断它的叫声，因为狗叫声作是一个共同特征聚类过程如下：特征的选择相似性度量聚类准则聚类算法聚类评价聚类结果的解译模式识别导论武汉大学遥感信息工程学院 马洪超按距离聚类的概念所谓聚类分析就是根据模式的特征空间分布，按点间距离的大小确定其相似程度，进而进行归类工作的，一般说来，可以认为每类模式都聚集在一个有代表性的或典型的模式周围，这个有代表性的模式称为聚类中心，或称为标准模式 若有M个类别 其标准模式分别为，任一模式x与第类标准模式间的距离表示为模式识别导论武汉大学遥感信息工程学院 马洪超聚类分析就是按照这种距离函数（或者更加广义的相似性度量）来进行归类处理，由于以最小距离为准则，故可以认为

4、聚类分析的分类器是最小距离分类器？模式识别导论武汉大学遥感信息工程学院 马洪超不考虑无关项，上面的式子可以转化为：设模式特征空间为n维空间，即有模式识别导论武汉大学遥感信息工程学院 马洪超可见最小距离分类器是线性分类器的特殊情况 模式识别导论武汉大学遥感信息工程学院 马洪超模式相似性测度与聚类准则 同一类模式的特征数据都是相近的或相同的，这一性质称为模式的相似性。这种相似性用什么公式来表达，也就相似性测度问题。式（4-1-1）是用距离函数来表示对相似性的度量，它是一种常用的测度。一般用于模式识别的相似性测度有如下几种（1）明氏（Minkowaski）距离n维模式向量 与 之间的明氏距离为模式识

5、别导论武汉大学遥感信息工程学院 马洪超称为“城市街坊距离”（“city block”distance）。当m=2时，即式（4-1-1），它又称为欧氏距离。当时，称为切比雪夫距离（2）马氏（Mahalanobis）距离模式识别导论武汉大学遥感信息工程学院 马洪超 第一类第二类其中m为均值向量，C 为协方差矩阵 欧氏距离和马氏距离之间的差别：欧氏距离来说应该是属于第一类模式识别导论武汉大学遥感信息工程学院 马洪超例子：二维两类问题，设都服从正态分布，协方差矩阵一样计算向量 到这两类的欧氏距离和马氏距离模式识别导论武汉大学遥感信息工程学院 马洪超可见，给定的向量和第一类的中心比较近。但如果从欧氏距离

6、类看，则是相反的，下图模式识别导论武汉大学遥感信息工程学院 马洪超（3）向量夹角余弦 它反映了几何相似性，在模式向量具有扇形分布时常采用这种测度 当模式特征向量各分量取0、1二值时，常采用此式 模式识别导论武汉大学遥感信息工程学院 马洪超二、聚类准则当采用某一相似性测度如欧氏距离对所有模式进行判别时，将距离数值计算出来，必须确定一个阈值，在小于此阈值时，判为同类，否则在大于它时，定为异类。怎样确定阈值才比较正确、合理，这就是聚类准则问题。一般有两种方式来确定这一准则（1）经验法根据经验和直观，确定相似性度量中的阈值，或在确定这些阈值后试行分类，视结果对尚不够合理的阈值加以调整、修正，直至满意为

7、止。这就是所谓经验法，或称为试探法。模式识别导论武汉大学遥感信息工程学院 马洪超（2）函数法这是根据理论分析确定阈值的方法，它采用聚类准则函数进行分析。这种准则函数有许多，下面介绍三种准则。误差平方和准则对于C类模式，准则函数为当J最小时，认为聚类合理。在各类样本密集，类别间分离明显时，最宜采用这一准则 模式识别导论武汉大学遥感信息工程学院 马洪超与最小方差有关的准则它是类中所有点间距离平方的均值，相似性算子也可以由其它形式取代，如夹角余弦算子。这一准则也是以J最小作为判断聚类合理的依据 模式识别导论武汉大学遥感信息工程学院 马洪超散布准则模式识别导论武汉大学遥感信息工程学院 马洪超并定义类间

8、散布矩阵为总体散布矩阵为 可以推出模式识别导论武汉大学遥感信息工程学院 马洪超推导过程如下：模式识别导论武汉大学遥感信息工程学院 马洪超模式识别导论武汉大学遥感信息工程学院 马洪超准则函数根据各种散布矩阵的“大小”来定义。度量矩阵“大小”可按矩阵迹（矩阵对角线元素之和）进行。例如 模式识别导论武汉大学遥感信息工程学院 马洪超当J最小时，也就是类内散布矩阵迹最小时，认为聚类合理。同样可以定义当J最大时，即类间散布矩阵迹最大时，认为聚类合理 模式识别导论武汉大学遥感信息工程学院 马洪超聚类算法 在选择了某一聚类准则函数J之后，需要对模式总体进行分类，并计算J值。对于不同的阈值，各种可能的分类结果，

9、都要计算J值，以求达到最优。这样做需要大量计算，实际上是不可能的。一般采取一些被认为是可以达到最优结果的聚类算法 一、简单搜索算法 对N 个待分类的模式样本集合 首先任意选择一个样本 作为第一个聚类中心 模式识别导论武汉大学遥感信息工程学院 马洪超并确定一个非负阈值T，一般为方便起见，令 继续搜索，直至得到N个样本的所有聚类中心 模式识别导论武汉大学遥感信息工程学院 马洪超这种算法与阈值T的大小、第一个聚类中心的选择、模式样本的排列次序和样本分布的几何特性有关。阈值T较大时，聚类数较少，T较小时，得到的类别数就很多。图4-3-1说明了T值大小对聚类结果的影响。阈值T确定之后，第一个聚类中心的选

10、取不同，结果也不相同（如图4-3-1(e)、(d)）。因此，当对于模式样本的几何分布有所了解之后，就可以合理地确定阈值T和第一个聚类中心，得到较为满意的结果。一般低于四维的分布容易得到演示，高维分布则不可能直观地表示出来，这时只能根据具体情况，选用不同的阈值和起始点进行试探，根据聚类结果调整，或在进行某些数值分析后重新确定阈值和起始点。这种方法对于只需要某种粗略聚类的问题来说，是简单快速的方法 模式识别导论武汉大学遥感信息工程学院 马洪超二、最大的最小距离算法这种方法以类间欧氏距离最大作为选择聚类中心的条件。下面以图为例，说明其基本思想。图4-3-2中有10个二维样本。现按最大的最小距离算法作

11、聚类分析 第一步，任选一模式样本作为第一聚类中心。这里令 第二步，确定离 距离最远的样本作为第二聚类中心 模式识别导论武汉大学遥感信息工程学院 马洪超模式识别导论武汉大学遥感信息工程学院 马洪超第三步，逐一计算各样本与间的距离，即并确定 中最小值，即 即在 中的最大值如果超过 间距离的一半的 模式识别导论武汉大学遥感信息工程学院 马洪超就定为第三聚类中心 第四步，有存在，计算同样，若此最大值大于 则存在，否则聚类中心的搜寻计算结束。由于此例中找不到满足上述条件的最大值，故停止搜寻聚类中心 第五步，对所有模式样本，逐一计算它们到三个聚类中心的距离，归入到距离小的类中心对应的类中模式识别导论武汉大

12、学遥感信息工程学院 马洪超两步曲：用距离最大原则寻找聚类中心用距离最小原则将剩余的样本归入到相应的类别中上例中三类分别为：模式识别导论武汉大学遥感信息工程学院 马洪超三、K 均值算法以上算法是逐一搜索确定聚类中心，下面介绍的，则是首先确定若干初始聚类中心，然后依一定算法改变或调整这些中心，使它们逐步趋于合理 K均值算法要求各类样本到聚类中心的距离平方和最小，它是在误差平方和准则的基础上建立起来的（1）任选K个初始聚类中心 一般以开头K个样本作为初始中心 模式识别导论武汉大学遥感信息工程学院 马洪超（2）逐个将模式样本集 的每一样本按最小距离原则分配给K个聚类中心，形成K个类群，即在第m次迭代时

13、，若则，这里表示第m次迭代时，以第j个聚类中心为代表的聚类域。（3）由（2），计算新的聚类中心，即模式识别导论武汉大学遥感信息工程学院 马洪超式中为第个聚类域中的样本个数。其均值向量作为新的聚类中心，因为这样可以使误差平方和准则函数达到最小值（4）若 模式识别导论武汉大学遥感信息工程学院 马洪超算法收敛，计算完毕。否则回到（2），进行下一次迭代。例2 图4-3-3所示为二维模式样本的分布，现用K均值算法分类 第一步：取K=2，令 第二步 模式识别导论武汉大学遥感信息工程学院 马洪超第三步：计算新的聚类中心模式识别导论武汉大学遥感信息工程学院 马洪超第四步：故回到第二步(第二轮）第二步：按新的聚

14、类中心分类，有(第二轮）第三步：计算聚类中心 模式识别导论武汉大学遥感信息工程学院 马洪超第四步：因 回到第二步（第三轮）第二步：求得 第三步：聚类中心与前一次迭代结果相同 第四步：因 故算法收敛 与初始聚类中心的确定有关模式识别导论武汉大学遥感信息工程学院 马洪超四、ISODATA算法ISODTA意为迭代自组织数据分析技术。这个算法与K均值算法相似，也是以均值迭代确定聚类中心，但它加进了人机对话环节，可以调整参数，并且引入了归并与分裂的机制，即当某两类别中心间距小于某一阈值时，将它们合并为一类，而在某类样本标准差大于某一阈值时，或其样本数目超过某一阈值时，则将它分为两类，在类别数目少于某一阈

15、值时，也实行分裂。另外，在某类样本数目少于某阈值时，又需要将其消除。因此，这种方法灵活性更强，更为合理。该算法需要确定并在计算中可以调整的参数有：模式识别导论武汉大学遥感信息工程学院 马洪超K:所要求的聚类中心数。一个类别至少应具有的样本数目。一个类别样本标准差阈值。聚类中心之间距离的阈值，即归并系数。L:在一次迭代中可以归并的类别的最多对数。I:允许迭代的最多次数。这一算法的步骤如下：第一步：对于N个模式样本的集合，确定C个初始聚类中心 C不一定等于K。这些聚类中心可为模式集合中的任意样本。模式识别导论武汉大学遥感信息工程学院 马洪超第二步：确定上述六个参数，即第三步：将N个样本按最小距离分

16、类，即若 第四步：若对于某一聚类域fj，其样本数目 则取消该子集和并且C=C-1，即类别数减少1，第五步：修正各聚类中心值：转入第3步模式识别导论武汉大学遥感信息工程学院 马洪超第六步：对每一聚类域fj，计算其所有样本到其聚类中心的距离的平均值。第七步：计算所有样本到其相应聚类中心的距离的平均值。模式识别导论武汉大学遥感信息工程学院 马洪超第八步：若迭代次数达到I次，置 转入第十二步，运算结束；若 即聚类中心数目等于或不到规定数目的二分之一，则转入第九步，以对现有类别进行分裂；若C=2k,跳过分裂，转12，否则转下若k/2C2k,当迭代次数是奇数转第九步（分裂），迭代次数为偶数时，转12步（合

17、并）第九步：计算每一类别中样本与聚类中心距离的标准差向量：模式识别导论武汉大学遥感信息工程学院 马洪超其中每一分量为 这里n为模式样本的维数 第十步：对每一标准差向量 求其最大分量 用S记下它是第几分量。模式识别导论武汉大学遥感信息工程学院 马洪超第十一步：在最大分量集 中 并且满足下列条件之一：模式识别导论武汉大学遥感信息工程学院 马洪超The splitting is controlled by parameter M which ensures noticeable but Not dramatic change in cluster centers arrangement分裂完毕，转入

18、第三步。如果没有可分裂的类别，则继续。第十二步：计算每两个聚类中心之间的距离：模式识别导论武汉大学遥感信息工程学院 马洪超第十五步：如果是最后一次迭代计算（即第I次），算法结束。否则，如果需要改变参数则转入第二步，不需要改变参数则转入第三步。模式识别导论武汉大学遥感信息工程学院 马洪超例3，图4-3-5所示的模式表明N=8，n=2。现用ISODATA算法进行聚类分析 参考教材模式样本的选取和初始聚类中心的确定待识别分类的模式集合有时是一个很大的集合，如遥感数字化影像等。而在采取聚类分析方法时，大都进行迭代计算，若将所有模式反复进行迭代计算，是不经济的。为此，需要进行抽样，在样本集合中先实施迭代

19、，以确定各类中心，然后对模式集合的全体进行分类。另一方面，迭代计算的初始聚类中心的确定往往具有一定的盲目性，如何尽可能减少这种盲目性的程度，也成为一个课题。模式识别导论武汉大学遥感信息工程学院 马洪超It is needless to say that a successful implementation of ISODATA on general pattern sets,requires extensive experimentations in order to obtain the appropriate values of parameters such as ,It should

20、 be noted that using ISODATA with inappropriate parameters may lead to oscillations.For example,a wrong choice of maycause an infinite sequence of alternate splitting and lumping.系统聚类，参看教材对聚类结果的评价：自学模式识别导论武汉大学遥感信息工程学院 马洪超计算机作业（基础题）：编程序实现均值算法和算法，要求参数能有对话框输入，处理的样本数据存储于数据文件中。数据如下图，对程序进行运行演算；（）提高题目：利用上述编写的核心算法代码，对图像进行分类。要求参考商业软件界面，分类结果用色斑图表示各类别。模式识别导论武汉大学遥感信息工程学院 马洪超表示给定的初始聚类中心