模式识别导论(四).pdf

《模式识别导论(四).pdf》由会员分享，可在线阅读，更多相关《模式识别导论(四).pdf（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

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

3、据每个类的共同特征来表征这个类。比如当我们看见草地上一条狗的时候，我们会推断它的叫声，因为狗叫声作是一个共同特征 聚类过程如下：特征的选择 相似性度量 聚类准则 聚类算法 聚类评价 聚类结果的解译 模式识别导论 武汉大学遥感信息工程学院 马洪超 按距离聚类的概念 所谓聚类分析就是根据模式的特征空间分布，按点间距离的大小确定其相似程度，进而进行归类工作的，一般说来，可以认为每类模式都聚集在一个有代表性的或典型的模式周围，这个有代表性的模式称为聚类中心，或称为标准模式 若有M个类别 M21Mzzz21i其标准模式分别为，任一模式x与第 类标准模式间的距离表示为 模式识别导论 武汉大学遥感信息工程学

4、院 马洪超 聚类分析就是按照这种距离函数（或者更加广义的相似性度量）来进行归类处理，由于以最小距离为准则，故可以认为聚类分析的分类器是最小距离分类器 ijiitiiixddjiMizxzxzxd，则有如果,114,2,1 2142,1212222Mizzzxxxzzzxxxzxzxzxditiittitiittitiii？模式识别导论 武汉大学遥感信息工程学院 马洪超 ijiitiitixxdxdijMizzzxxd则存在若,314,2,121不考虑无关项，上面的式子可以转化为：设模式特征空间为n维空间，即有 tnitiniijijtiniiixxxxzzwnjzwzzzz1,21,2,121

5、121令模式识别导论 武汉大学遥感信息工程学院 马洪超 414,2,1Mixwxdtiitniiiiwwww121,可见最小距离分类器是线性分类器的特殊情况 模式识别导论 武汉大学遥感信息工程学院 马洪超 模式相似性测度与聚类准则 同一类模式的特征数据都是相近的或相同的，这一性质称为模式的相似性。这种相似性用什么公式来表达，也就相似性测度问题。式（4-1-1）是用距离函数来表示对相似性的度量，它是一种常用的测度。一般用于模式识别的相似性测度有如下几种 （1）明氏（Minkowaski）距离 n维模式向量 与 之间的明氏距离为 ixjx模式识别导论 武汉大学遥感信息工程学院 马洪超 224,11

6、24,1111jkiknkjimmjkiknkjixxxxd，mxxxxd有时当称为“城市街坊距离”（“city block”distance）。当m=2时，即式（4-1-1），它又称为欧氏距离。当 m时，称为切比雪夫距离 （2）马氏（Mahalanobis）距离 模式识别导论 武汉大学遥感信息工程学院 马洪超 第二类 32412mxCmxtd其中m为均值向量，C 为协方差矩阵 欧氏距离和马氏距离之间的差别：欧氏距离来说应该是属于第一类 模式识别导论 武汉大学遥感信息工程学院 马洪超（3）向量夹角余弦 424,jijtijixxxxxxS它反映了几何相似性，在模式向量具有扇形分布时常采用这种测

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

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

9、武汉大学遥感信息工程学院 马洪超 散布准则 CiiwxtiitiCiiCiiixiiSSmxmxSNNmNNmxNmii111)(,11为由此定义类内散布矩阵类的散布矩阵为则其中哪一类）的均值向量为所有向量（不论它属于类的均值向量为：若模式识别导论 武汉大学遥感信息工程学院 马洪超 并定义类间散布矩阵为 11241tiiiCiBmmmmNS总体散布矩阵为 1224tnTmxmxS1324BWTSSS可以推出 模式识别导论 武汉大学遥感信息工程学院 马洪超 推导过程如下：TxTTxxTxTTTTxTTNSmmxmmxxxmmmxxmxxmxmx整个样本集整个样本集整个样本集整个样本集整个样本集模

10、式识别导论 武汉大学遥感信息工程学院 马洪超 CiTixTiiTxTiixTixiiciTiTiiTiiTiiiCiTiiiBNNNNNNNNNNNNNSiiii1111111mmxmmxxxmmmmmmmmmmmmCixTixiixTxixTixxTCixTiiTiTiTCixTiiWiiiiiiiiiNNNNNS1111111xxxxxxxxmmxmxmxxmxmx模式识别导论 武汉大学遥感信息工程学院 马洪超 TCiTixTxTTxTBWSNSSiii所以，1mmxmmxxx准则函数根据各种散布矩阵的“大小”来定义。度量矩阵“大小”可按矩阵迹（矩阵对角线元素之和）进行。例如 142421

11、1ixCiirCiwrmxStStJi模式识别导论 武汉大学遥感信息工程学院 马洪超 当J最小时，也就是类内散布矩阵迹最小时，认为聚类合理。同样可以定义 152421mmNStJiiCiBr当J最大时，即类间散布矩阵迹最大时，认为聚类合理 模式识别导论 武汉大学遥感信息工程学院 马洪超 聚类算法 在选择了某一聚类准则函数J之后，需要对模式总体进行分类，并计算J值。对于不同的阈值，各种可能的分类结果，都要计算J值，以求达到最优。这样做需要大量计算，实际上是不可能的。一般采取一些被认为是可以达到最优结果的聚类算法 一、简单搜索算法 对N 个待分类的模式样本集合 ,21Nxxx首先任意选择一个样本

12、ix作为第一个聚类中心 1z 模式识别导论 武汉大学遥感信息工程学院 马洪超 并确定一个非负阈值T，一般为方便起见，令 11xz 继续搜索，直至得到N个样本的所有聚类中心 以此类推。则若则否则，若，则得到聚类中心均大于若。计算假定已经确定聚类中心聚类域）。为中心的（以否则个新的聚类中心，则确定一若的距离到计算233231133231332313231211122221122112,;,|,|fxddfxddzTddddzzzfxxzTdzxdzx模式识别导论 武汉大学遥感信息工程学院 马洪超 这种算法与阈值T的大小、第一个聚类中心的选择、模式样本的排列次序和样本分布的几何特性有关。阈值T较大时

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

14、以类间欧氏距离最大作为选择聚类中心的条件。下面以图为例，说明其基本思想。图4-3-2中有10个二维样本。现按最大的最小距离算法作聚类分析 第一步，任选一模式样本作为第一聚类中心。这里令 11xz 第二步，确定离 1Z距离最远的样本作为第二聚类中心 62xz 模式识别导论 武汉大学遥感信息工程学院 马洪超 模式识别导论 武汉大学遥感信息工程学院 马洪超 第三步，逐一计算各样本与 21,zz间的距离，即 6,110,2,12211iizxdzxdiiii并确定 21,iidd中最小值，即 。xz，zzddddiiiii32121max,15.0,min则若令即在 id中的最大值如果超过 21,zz

15、间距离的一半的 模式识别导论 武汉大学遥感信息工程学院 马洪超 就定为第三聚类中心 73xz 第四步，有 3z存在，计算 7,6,1,10,2,1,minmax321ii，dddiii同样，若此最大值大于 21zz 则存在 4z，否则聚类中心的搜寻计算结束。由于此例中找不到满足上述条件的最大值，故停止搜寻聚类中心 第五步，对所有模式样本，逐一计算它们到三个聚类中心的距离，归入到距离小的类中心对应的类中 模式识别导论 武汉大学遥感信息工程学院 马洪超 两步曲：用距离最大原则寻找聚类中心用距离最小 原则将剩余的样本归入到相应的类别中 431,xxx62,xx109875,.,xxxxx上例中三类分

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

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

18、11,11132313221222221111fxzxzxfxzxzxfxzxzx故故故因有模式识别导论 武汉大学遥感信息工程学院 马洪超 2065,422311,1,1xxxxxfxxf从而有第三步：计算新的聚类中心 33.567.5181125.00.02112205421223111121xxxxxNzxxxNzfxfx模式识别导论 武汉大学遥感信息工程学院 马洪超 第四步：,2,1,12jZZjj故回到第二步 (第二轮）第二步：按新的聚类中心分类，有 20109182111221,2,220,10,9,228,2,1,22xxxfxxxfjzxzxizxzxjjii故(第二轮）第三步：

19、计算聚类中心 模式识别导论 武汉大学遥感信息工程学院 马洪超 33.767.71211313.125.181132010922282121121xxxxNzxxxxNzfxfx第四步：因 2,1,23jzzjj回到第二步 （第三轮）第二步：求得 34,34221ffff第三步：聚类中心与前一次迭代结果相同 第四步：因 2,1,34jzzjj故算法收敛 与初始聚类中心的确定有关 模式识别导论 武汉大学遥感信息工程学院 马洪超 四、ISODATA算法 ISODTA意为迭代自组织数据分析技术。这个算法与K均值算法相似，也是以均值迭代确定聚类中心，但它加进了人机对话环节，可以调整参数，并且引入了归并与

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

21、定C个初始聚类中心 C不一定等于K。这些聚类中心可为模式集合中的任意样本。Czzz,21模式识别导论 武汉大学遥感信息工程学院 马洪超 第二步：确定上述六个参数，即 ILKCSN,第三步：将N个样本按最小距离分类，即若 Cizxdij,2,1,minjfx第四步：若对于某一聚类域fj，其样本数目 NjNifiz则取消该子集 和 并且C=C-1，即类别数减少1，第五步：修正各聚类中心值：的样本数为其中ijfxjjfNCjxNzj ,2,1,1转入第3步 模式识别导论 武汉大学遥感信息工程学院 马洪超 第六步：对每一聚类域fj，计算其所有样本到其聚类中心的距离的平均值。CjzxNdjfxjjj,2

22、,11第七步：计算所有样本到其相应聚类中心的距离的平均值。jjCjdNNd11模式识别导论 武汉大学遥感信息工程学院 马洪超 第八步：若迭代次数达到I次，置 0c转入第十二步，运算结束；若 2KC 即聚类中心数目等于或不到规定数目的二分之一，则转入第九步，以对现有类别进行分裂；若C=2k,跳过分裂，转12，否则转下 若k/2C2k,当迭代次数是奇数转第九步（分裂），迭代次数为偶数时，转12步（合并）第九步：计算每一类别中样本与聚类中心距离的标准差向量：tnjjjj，21模式识别导论 武汉大学遥感信息工程学院 马洪超 其中每一分量为 CjnizxNjfxijl ijij,2,1,2,112这里n

23、为模式样本的维数 个分量个样本的第是第iLxil个分量的第是izzjij第十步：对每一标准差向量 Cjj,2,1,求其最大分量 maxj维数；kcjkjkj2,1,maxmax用S记下它是第几分量。模式识别导论 武汉大学遥感信息工程学院 马洪超 第十一步：在最大分量集 中 Cjj,2,1,maxSKmax若有并且满足下列条件之一：12 12CCzzzKCNddjjjNjj，且类别数，心分裂成两个新的聚类中则将定数据两倍且该类样本总数超过规平均距离大于总体距离心的即该类中样本到聚类中且模式识别导论 武汉大学遥感信息工程学院 马洪超 jjjjjjjjjzrszzMMrszz不变，构成，其他分量分量

24、减去的第的其他分量不变，分量上加的分量即第的的确定方法：对于,10maxmaxThe splitting is controlled by parameter M which ensures noticeable but Not dramatic change in cluster centers arrangement 分裂完毕，转入第三步。如果没有可分裂的类别，则继续。第十二步：计算每两个聚类中心之间的距离：CiijCizzdjiij,2,1;1,2,1模式识别导论 武汉大学遥感信息工程学院 马洪超 标志：新类别以新聚类中心为只能合并一次，合并后，每个类别的类别开始，逐一合并第十四步：从且

25、这里合的均取出，组成一个集的值进行比较，凡是的值和第十三步：将每一个jiddLtddddddddCijjijijijijijijiCijCijtttt,1122112211LlzNzNNNziljlililjlill,2,11*第十五步：如果是最后一次迭代计算（即第I次），算法结束。否则，如果需要改变参数则转入第二步，不需要改变参数则转入第三步。模式识别导论 武汉大学遥感信息工程学院 马洪超 例3，图4-3-5所示的模式表明N=8，n=2。现用ISODATA算法进行聚类分析 参考教材 模式样本的选取和初始聚类中心的确定 待识别分类的模式集合有时是一个很大的集合，如遥感数字化影像等。而在采取聚类

26、分析方法时，大都进行迭代计算，若将所有模式反复进行迭代计算，是不经济的。为此，需要进行抽样，在样本集合中先实施迭代，以确定各类中心，然后对模式集合的全体进行分类。另一方面，迭代计算的初始聚类中心的确定往往具有一定的盲目性，如何尽可能减少这种盲目性的程度，也成为一个课题。模式识别导论 武汉大学遥感信息工程学院 马洪超 It is needless to say that a successful implementation of ISODATA on general pattern sets,requires extensive experimentations in order to obt

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