模式识别复习资料

1、.复习复习1模式和模式识别的概念 1）模式：对某些感兴趣的客体的定量的或结构的描述。模式类是具有某些共同特性的模式的集合。 2）模式识别：研究一种自动技术，依靠这种技术，计算机将自动地（或人尽量少地干涉）把待别识模式分配到各自的模式类中去。.复习复习2 模式识别系统组成学习过程判决过程分类规则训练分类决策数据获取预处理特征选择 或提取模式识别系统框图 .复习复习1） 监督分类：需要依靠已知类别的训练样本集，按照他们特征向量的分布来确定判别函数，然后利用判别函数对未知模式进行分类。需要足够的先验知识。 判别。需要有足够的先验知识。2） 非监督分类：用于没有先验知识的情况，通常采用聚类分析的方法。

2、3 监督分类和无监督分类.复习复习4 模式识别整体知识结构.5 最大最小距离算法（小中取大距离算法最大最小距离算法（小中取大距离算法 ） 算法描述算法描述 选任意一模式样本做为第一聚类中心Z1。 选择离Z1距离最远的样本作为第二聚类中心Z2。 逐个计算各模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。例当聚类中心数k=2时，计算11ZX iiD22ZX iiDmin( Di1 , Di2 )，i=1，N（N个最小距离） 复习复习. 将样本 按最近距离划分到相应聚类中心对应的类别中。Nii, 2 , 1,X 重复步骤，直到没有新的聚类中心出现为止。 在所有最小距离中选出最大距离，

3、如该最大值达到 的一定分数比值( 阈值T ) 以上，则相应的样本点取为新的聚类中心，返回；否则，寻找聚类中心的工作结束。21ZZ 10,.,2 , 1),maxmin(2121ZZNiDDii若（：用试探法取为一固定分数，如1/2。）则Z3存在。例k =2时复习复习.例2.1 对图示模式样本用最大最小距离算法进行聚类分析。 选选Z1=X1距距Z1最远，选为最远，选为Z2。计算。计算T。对应最小距离对应最小距离中的最大值，中的最大值，且且T，选作，选作Z3。结果：Z1=X1；Z2=X6； Z3=X7 。 用全体模式对三个聚类中心计算最小距离中的最大值，无T 情况，停止寻找中心。 聚类802121

4、21ZZT10个最小距离中，X7对应的距离T,73XZ.算法描述算法描述1）N个初始模式样本自成一类，即建立N 类：计算各类之间（即各样本间）的距离，得一NN维距离矩阵D(0)。“0”表示初始状态。)0(,),0(),0(21NGGG(G_Group)6 层次聚类法层次聚类法2）假设已求得距离矩阵D(n)（n为逐次聚类合并的次数），找出D(n)中的最小元素，将其对应的两类合并为一类。由此建立新的分类：3）计算合并后新类别之间的距离，得D(n+1)。4）跳至第2步，重复计算及合并。复习复习. 结束条件：结束条件：1）取距离阈值T，当D(n)的最小分量超过给定值 T 时，算法停 止。所得即为聚类结

5、果。2）或不设阈值T，一直将全部样本聚成一类为止，输出聚类的分 级树。复习复习.T10 , 2 , 1 , 3 , 0XT20 , 1 , 0 , 3 , 1XT31 , 0 , 0 , 3 , 3XT40 , 2 , 0 , 1 , 1XT51 , 2 , 1 , 2 , 3XT60 , 1 , 1 , 1 ,4X例：给出6个五维模式样本如下，按最短距离准则进行系统聚类分类。计算各类间欧氏距离：解：（1）将每一样本看作单独一类，得：11)0(XG22)0(XG33)0(XG44)0(XG55)0(XG66)0(XG301101) 0 (2121225152241422313222122211

6、12112xxxxxxxxxxDXX1512103)0(212213D)0(34D)0(35D)0(36D， ， ， ；) 0 (14D) 0 (15D) 0(16D) 0(23D) 0(24D) 0(25D) 0(26D；.) 0(1G)0(2G)0(3G)0(4G)0(5G)0(6G)0(1G)0(2G3)0(3G156)0(4G6513)0(5G11867)0(6G21148114（2）将最小距离 对应的类 和 合并为1类，得 新的分类。3)0(1G) 0(2G)0() 1 (44GG)0() 1 (55GG)0(),0() 1 (2112GGG)0() 1 (33GG)0() 1 (6

7、6GG计算聚类后的距离矩阵D(1)：由D(0) 递推出D(1) 。得距离矩阵D(0)：.) 0(1G)0(2G)0(3G)0(4G)0(5G)0(6G)0(1G)0(2G3)0(3G156)0(4G6513)0(5G11867)0(6G21148114) 1 (12G) 1 (3G) 1 (4G) 1 (5G) 1 (6G) 1 (12G) 1 (3G6) 1 (4G513) 1 (5G867) 1 (6G148114（3）将D(1)中最小值 对应的类合为一类， 得D(2)。4)2(12G)2(3G)2(4G)2(56G) 2(12G)2(3G6)2(4G513) 2(56G867.（4）将D

8、(2)中最小值 对应的类合为一类，得D(3)。5)2(12G)2(3G)2(4G)2(56G) 2(12G)2(3G6)2(4G513) 2(56G867) 3(124G) 3(3G)3(56G) 3(124G) 3(3G6)3(56G76若给定的阈值为 ，D(3)中的最小元素 ，聚类结束。5T4211,XXXG 32XG 653, XXG 若无阈值，继续分下去，最终全部样本归为一类。可给出聚类过程的树状表示图。13T6.65431X2X4X3X5X6X 层次聚类法的树状表示 类间距离类间距离阈值增大，阈值增大，分类变粗。分类变粗。.7 K-均值算法均值算法 算法描述算法描述（1）任选K个初始

9、聚类中心：Z1(1)， Z2(1)， ZK(1) （2）按最小距离原则将其余样品分配到K个聚类中心中的某一 个。Nj：第j类的样本数。 KjNkkjSXjj,2, 11)1(XZKjkj, 2 , 1) 1(Z（3）计算各个聚类中心的新向量值：（4）如果 ，则回到（2），将模式 样本逐个重新分类，重复迭代计算。Kjkkjj, 2 , 1)() 1(ZZ复习复习.例2.3：已知20个模式样本如下，试用K-均值算法分类。 T10 , 0XT20 , 1XT31 , 0X T41 , 1XT51 , 2XT62 , 1XT72 , 2XT82 , 3XT96 , 6XT106 , 7XT116 ,

10、8XT127 , 6XT137 , 7XT147 , 8XT157 , 9XT168 , 7XT178 , 8XT188 , 9XT199 , 8XT209 , 9XT110 , 0) 1 ( XZT220 , 1) 1 ( XZ解： 取K=2，并选： 计算距离，聚类：10010|) 1 (|0|) 1 (|22212111ZXZXDD) 1 (1121SDDX1X： 0|) 1 (|1|) 1 (|222121ZXZXDD) 1 (2212SDDX2X：.20110|) 1 (|10100|) 1 (|2223222131ZXZXDD) 1 (1321SDDX3X： 10111|) 1 (|

11、20101|) 1 (|2224222141ZXZXDD) 1 (2412SDDX4X： 2,) 1 (1311NSXX18,.,) 1 (2205422NSXXXX，可得到： 计算新的聚类中： 5 .00100021)(211)2(311111XXXZSXN 33. 567. 5)(1811)2(20421222XXXXZSXN) 1 ()2(jjZZ2 , 1j 判断：，故返回第步。. 从新的聚类中心得：|)2(|)2(|212111ZXZXDD) 2(11SX1X： |)2(|)2(|22021201ZXZXDD) 2(220S X20X： 8,)2(18211NSXXX12,.,)2(

12、2201092NSXXX有： 计算聚类中心： 13. 125. 1)(811)3(8212111XXXXZSXN 33. 767. 7)(1211) 3(201092222XXXXZSXN.)2() 3(jjZZ2 , 1j 返回第步，以Z1(3)， Z2(3)为中心进行聚类。 以新的聚类中心分类，求得的分类结果与前一次迭代结果相 同：)2() 3(11SS)2() 3(22SS 计算新聚类中心向量值，聚类中心与前一次结果相同，即： 2, 1,3)4(jjjZZ) 3()4(jjZZ33.767.7,13.125.121ZZ ，故算法收敛，得聚类中心为结果图示：.图2.10 K-均值算法聚类结

13、果X1X4X3X5X8X9X7X10X2X6x1x213579135790X11X12X13X14X15X16X17X18X19X2013.125.11Z33. 767. 72Z. 上述K-均值算法，其类型数目假定已知为K个。当K未知时，可以令K逐渐增加， 此时J j 会单调减少。最初减小速度快，但当K 增加到一定数值时，减小速度会减慢，直到K =总样本数N 时，Jj = 0。JjK关系曲线如下图：8 聚类准则函数聚类准则函数Jj与与K的关系曲线的关系曲线JjA135724608109K 曲线的拐点 A 对应着接近最优的K值（J 值减小量、计算量以及分类效果的权衡）。 并非所有的情况都容易找到

14、关系曲线的拐点。迭代自组织的数据分析算法可以确定模式类的个数K 。.ii两分法(1)多类情况1： 用线性判别函数将属于i类的模式与其余不属于i类的模式分开。将某个待分类模式 X 分别代入 M 个类的d (X)中，若只有di(X)0，其他d(X)均0的条件超过一个，或全部的di(X)Tik XW()=1+kW( )ickXW+( )kW( )0Tik XW若( )0Tik XW若（3）分析分类结果：只要有一个错误分类，回到（2），直至 对所有样本正确分类。 分类正确时，对权向量“赏”这里用“不罚”，即权向量不变；分类错误时，对权向量“罚”对其修改，向正确的方向转换。感知器算法是一种赏罚过程：感知

15、器算法是一种赏罚过程：.例例3.8 已知两类训练样本解：所有样本写成增广向量形式； 进行规范化处理，属于2的样本乘以(1)。T11 , 0 , 0XT21 , 1 , 0XT31, 0 , 1 XT41, 1, 1X用感知器算法求出将模式分为两类的权向量解和判别函数。 :1T10,0X:2T21 ,0XT30, 1XT41 , 1X.任取W(1)=0，取c=1，迭代过程为：第一轮： 0,1000 , 0 , 0) 1 (1TXWT11 , 0 , 0) 1 () 2(, 0XWW故1,1101 , 0 , 0)2(2TXWT1 , 0 , 0) 2() 3 (, 0WW故-1,1-01-1 ,

16、 0 , 0)3(3TXWT30 , 0 , 1-) 3 () 4(, 0XWW故1,1-1-1-0 , 0 , 1-)4(4TXWT0 , 0 , 1-) 4() 5 (, 0WW故有两个WT(k)Xi 0的情况（错判），进行第二轮迭代。.T11T1 , 0 , 1-)5()6(,00)5(XWWXW故T2T1 , 0 , 1-(6)7(,01)6(WWXW故T33T0 , 0 , 2-)7()8(,00)7(XWWXW故T4T0 , 0 , 2-)8()9(,02)8(WWXW故第二轮：T11T1 , 0 , 2-)9()10(,00)9(XWWXW故(10)11(,01)10(2TWWX

17、W故)11()12(,01)11(3TWWXW故)12()13(,01)12(4TWWXW故第三轮：)13()14(,01)13(1TWWXW故(14)15(,01)14(2TWWXW故)15()16(,01)15(3TWWXW故)16()17(,01)16(4TWWXW故第四轮：.T1 , 0 , 2W该轮迭代的分类结果全部正确，故解向量1+2=)(1xd X相应的判别函数为： 当c、W(1)取其他值时，结果可能不一样，所以感知器算法的解不是单值的。判别界面d(X)=0如图示。.10 最小错误率贝叶斯决策最小错误率贝叶斯决策对两类问题)()|()|(2211PpPpXX1X若，则)()|()

18、|(2211PpPpXX2X若，则可改写为：统计学中称l12(X)为似然比， 为似然比阈值。)()(12PP21X)|()|()(2112XXXppl12)(PP若，则 （4-8）.2111)(|)()|()|(iiiPpPpPXXX16. 02 . 095. 05 . 005. 005. 05 . 0884. 02 . 095. 05 . 005. 095. 02 . 0)|(2XP)|()|(12XXPP2X例例4.1 假定在细胞识别中，病变细胞的先验概率和正常细胞的先验概率分别为 。现有一待识别细胞，其观察值为X，从类条件概率密度发布曲线上查得： 95. 0)(,05. 0)(21PP5

19、 . 0)|(1Xp2 . 0)|(2Xp试对细胞X进行分类。解：方法1 通过后验概率计算。 .方法2：利用先验概率和类概率密度计算。025. 005. 05 . 0)|(11Pp X19. 095. 02 . 0)|(22Pp X)()|()|(1122PpPpXX2X，是正常细胞。.最小风险贝叶斯决策基本思想： 以各种错误分类所造成的平均风险最小为规则，进行分类决策。11 最小风险贝叶斯决策最小风险贝叶斯决策.)(|)(|)(222211212PpLPpLrXXX)(|)(|)(221211111PpLPpLrXXX2）两类情况）两类情况：对样本 X121)()(XXX则若rr221)()

20、(XXX则若rr当X 被判为1类时：当X 被判为2类时：（4-15） （4-16） )(|)(|)(|)(|2222112122121111PpLPpLPpLPpLXXXX )(|)(|111121222212PpLLPpLLXX)()()()()|()|(111212221221PLLPLLppXX由（4-15）式：MjjjijiPpLr1)()|()(XX决策规则：.令：)|()|()(2112XXXppl，称似然比；)()()()(111122222112PLLPLL，为阈值。 计算 。12 计算 。 X12l 定义损失函数Lij。判别步骤：112)(XX则，若 l任意判决，若1212)

21、(Xl212)(XX则，若 l)()()()()|()|(111122222121PLLPLLppXX类概率密度函数p(X |i) 也称i的似然函数.95.0)(,05.0)(21PP2 . 0)|(, 5 . 0)|(21XXpp解：计算 和 得： X12l125 . 22 . 05 . 0)|()|()(2112XXXppl 1212Xl1X例4.2 在细胞识别中，病变细胞和正常细胞的先验概率 分别为现有一待识别细胞，观察值为X， 从类概率密度分布曲线上查得损失函数分别为L11=0，L21=10， L22=0，L12=1。按最小风险贝叶斯决策分类。为病变细胞。 9 . 105. 0)010(95. 0)01 ()()()()(111212221212PLLPLL. 经过选择或变换，组成识别特征，尽可能保留分类信息，在保证一定分类精度的前提下，减少特征维数，使分类器的工作即快又准确。12 特征选择和提取的目的特征选择和提取的目的 13 特征选择和特征提取的异同特征选择和特征提取的异同（1）特征选择：从L个度量值集合 中按一定准