模式识别复习资料课件.ppt_163文库

资源描述

1、消消防防给给水水复习复习1模式和模式识别的概念模式和模式识别的概念 1）模式：对某些感兴趣的客体的定量的或结构的描述。模模式：对某些感兴趣的客体的定量的或结构的描述。模式类是具有某些共同特性的模式的集合。式类是具有某些共同特性的模式的集合。2）模式识别：研究一种自动技术，依靠这种技术，计算机模式识别：研究一种自动技术，依靠这种技术，计算机将自动地（或人尽量少地干涉）把待别识模式分配到各自将自动地（或人尽量少地干涉）把待别识模式分配到各自的模式类中去。的模式类中去。消消防防给给水水复习复习2 2 模式识别系统组成模式识别系统组成学习过程学习过程判决过程判决过程分类规则训练分类规则训练

2、分类决策分类决策数据获取数据获取预处理预处理特征选择特征选择或提取或提取模式识别系统框图模式识别系统框图消消防防给给水水复习复习1 1）监督分类：需要依靠已知类别的训练样本集，按监督分类：需要依靠已知类别的训练样本集，按照他们特征向量的分布来确定判别函数，然后利用判照他们特征向量的分布来确定判别函数，然后利用判别函数对未知模式进行分类。需要足够的先验知识。别函数对未知模式进行分类。需要足够的先验知识。判别。需要有足够的先验知识。判别。需要有足够的先验知识。2 2）非监督分类：用于没有先验知识的情况，通常采非监督分类：用于没有先验知识的情况，通常采用聚类分析的方法。用聚类分析的方法。3

3、 3 监督分类和无监督分类监督分类和无监督分类消消防防给给水水复习复习4 4 模式识别整体知识结构模式识别整体知识结构消消防防给给水水5 最大最小距离算法（小中取大距离算法最大最小距离算法（小中取大距离算法）算法描述算法描述选任意一模式样本做为第一聚类中心选任意一模式样本做为第一聚类中心Z1。选择离选择离Z1距离最远的样本作为第二聚类中心距离最远的样本作为第二聚类中心Z2。逐个计算各模式样本与逐个计算各模式样本与已确定的所有聚类中心之间的距离，已确定的所有聚类中心之间的距离，并选出其中的最小距离。例当聚类中心数并选出其中的最小距离。例当聚类中心数k=2时，计算时，计算11ZX i

4、iD22ZX iiDmin(Di1,Di2)，i=1，N（N个最小距离）个最小距离）复习复习消消防防给给水水将样本将样本按最近距离划分到相应聚类中心对应按最近距离划分到相应聚类中心对应的类别中。的类别中。Nii,2,1,X 重复步骤，直到没有新的聚类中心出现为止。重复步骤，直到没有新的聚类中心出现为止。在所有最小距离中选出最大距离，如该最大值达到在所有最小距离中选出最大距离，如该最大值达到的一定分数比值的一定分数比值(阈值阈值T)以上，则相应的样本点取为新的聚类以上，则相应的样本点取为新的聚类中心，返回中心，返回；否则，寻找聚类中心的工作结束。；否则，寻找聚类中心的工作结束。21Z

5、Z 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 情况，情况

6、，停止寻找中心。停止寻找中心。聚类聚类80212121ZZT10个最小距离中，个最小距离中，X7对对应的距离应的距离T,73XZ消消防防给给水水算法描述算法描述1）N个初始模式样本自成一类，即建立个初始模式样本自成一类，即建立N 类：类：计算各类之间（即各样本间）的距离，得一计算各类之间（即各样本间）的距离，得一NN维距离矩阵维距离矩阵D(0)。“0”表示初始状态。表示初始状态。)0(,),0(),0(21NGGG(G_Group)6 层次聚类法层次聚类法2）假设已求得距离矩阵）假设已求得距离矩阵D(n)（n为逐次聚类合并的次数），找出为逐次聚类合并的次数），找出D(n)中的最小元素，将

7、其对应的两类合并为一类。由此建立新的中的最小元素，将其对应的两类合并为一类。由此建立新的分类：分类：3）计算合并后新类别之间的距离，得）计算合并后新类别之间的距离，得D(n+1)。4）跳至第）跳至第2步，重复计算及合并。步，重复计算及合并。复习复习消消防防给给水水结束条件：结束条件：1）取距离阈值）取距离阈值T，当，当D(n)的最小分量超过给定值的最小分量超过给定值 T 时，算法停时，算法停止。所得即为聚类结果。止。所得即为聚类结果。2）或不设阈值）或不设阈值T，一直将全部样本聚成一类为止，输出聚类的分，一直将全部样本聚成一类为止，输出聚类的分级树。级树。复习复习消消防防给给

8、水水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(212122515224142231322212221112112xxxxxxxxxxDXX1512103)0(2

9、12213D)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(66GG计算聚类后的距离矩阵计算聚类后的距离矩阵

10、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消消防防给给水

11、水（4）将）将D(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消消防防给给水水65431X2

12、X4X3X5X6X 层次聚类法的树状表示层次聚类法的树状表示类间距离类间距离阈值增大，阈值增大，分类变粗。分类变粗。消消防防给给水水7 K-均值算法均值算法算法描述算法描述（1）任选）任选K个初始聚类中心：个初始聚类中心：Z1(1)，Z2(1)，ZK(1)（2）按最小距离原则将其余样品分配到）按最小距离原则将其余样品分配到K个聚类个聚类中心中的某一中心中的某一个。个。Nj：第：第j类的样本数。类的样本数。KjNkkjSXjj,2,11)1(XZKjkj,2,1)1(Z（3）计算各个聚类中心的新向量值：）计算各个聚类中心的新向量值：（4）如果）如果，则回到（，则回到（2），将模式）

13、，将模式样本逐个重新分类，重复迭代计算。样本逐个重新分类，重复迭代计算。Kjkkjj,2,1)()1(ZZ复习复习消消防防给给水水例例2.3：已知：已知20个模式样本如下，试用个模式样本如下，试用K-均值算法分类。均值算法分类。T10,0XT20,1XT31,0X T41,1XT51,2XT62,1XT72,2XT82,3XT96,6XT106,7XT116,8XT127,6XT137,7XT147,8XT157,9XT168,7XT178,8XT188,9XT199,8XT209,9XT110,0)1(XZT220,1)1(XZ解：解：取取K=2，并选：，并选：计算距离，聚类：计算距

14、离，聚类：10010|)1(|0|)1(|22212111ZXZXDD)1(1121SDDX1X：0|)1(|1|)1(|222121ZXZXDD)1(2212SDDX2X：消消防防给给水水20110|)1(|10100|)1(|2223222131ZXZXDD)1(1321SDDX3X：10111|)1(|20101|)1(|2224222141ZXZXDD)1(2412SDDX4X：2,)1(1311NSXX18,.,)1(2205422NSXXXX，可得到：，可得到：计算新的聚类中：计算新的聚类中：5.00100021)(211)2(311111XXXZSXN 33.567.5)(

15、1811)2(20421222XXXXZSXN)1()2(jjZZ2,1j 判断：判断：，故返回第步。，故返回第步。消消防防给给水水从新的聚类中心得：从新的聚类中心得：|)2(|)2(|212111ZXZXDD)2(11SX1X：|)2(|)2(|22021201ZXZXDD)2(220S X20X：8,)2(18211NSXXX12,.,)2(2201092NSXXX有：有：计算聚类中心：计算聚类中心：13.125.1)(811)3(8212111XXXXZSXN 33.767.7)(1211)3(201092222XXXXZSXN消消防防给给水水)2()3(jjZZ2,1j

16、返回第步，以返回第步，以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-均值算法聚类结果均值算法聚类结果X1X4X3X5X8X9X7X

17、10X2X6x1x213579135790X11X12X13X14X15X16X17X18X19X2013.125.11Z33.767.72Z消消防防给给水水上述上述K-均值算法，其类型数目假定已知为均值算法，其类型数目假定已知为K个。当个。当K未知时，未知时，可以令可以令K逐渐增加，逐渐增加，此时此时J j 会单调减少。最初减小速度快，但当会单调减少。最初减小速度快，但当K 增加到一定数值时，减小速度会减慢，直到增加到一定数值时，减小速度会减慢，直到K=总样本数总样本数N 时，时，Jj=0。JjK关系曲线如下图：关系曲线如下图：8 聚类准则函数聚类准则函数Jj与与K的关系曲线的关系曲

18、线JjA135724608109K 曲线的拐点曲线的拐点 A 对应着接近最优对应着接近最优的的K值（值（J 值减小量、计算量以及值减小量、计算量以及分类效果的分类效果的权衡权衡）。）。并非所有的情况都容易找到关并非所有的情况都容易找到关系曲线的拐点。迭代自组织的数据系曲线的拐点。迭代自组织的数据分析算法可以确定模式类的个数分析算法可以确定模式类的个数K。消消防防给给水水ii两分法两分法(1)多类情况多类情况1：用线性判别函数将属于用线性判别函数将属于i类的模式与其余不属于类的模式与其余不属于i类的类的模式分开。模式分开。将某个待分类模式将某个待分类模式 X 分别代入分别代入 M 个类的个

19、类的d(X)中，中，若只有若只有di(X)0，其他，其他d(X)均均0的条件超过一个，或全部的条件超过一个，或全部的的di(X)Tik XW()=1+kW()ickXW+()kW()0Tik XW若()0Tik XW若（3）分析分类结果：只要有一个错误分类，回到（）分析分类结果：只要有一个错误分类，回到（2），直至），直至对所有样本正确分类。对所有样本正确分类。分类正确时，对权向量分类正确时，对权向量“赏赏”这里用这里用“不罚不罚”，即权向量不变；，即权向量不变；分类错误时，对权向量分类错误时，对权向量“罚罚”对其修改，向正确的方向转换。对其修改，向正确的方向转换。感知器算法是一种赏罚过程：

20、感知器算法是一种赏罚过程：消消防防给给水水例例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

21、()2(,0XWW故1,1101,0,0)2(2TXWT1,0,0)2()3(,0WW故-1,1-01-1,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故第二轮：第二轮：T11T

22、1,0,2-)9()10(,00)9(XWWXW故(10)11(,01)10(2TWWXW故)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)取其他值取其他值时，结果可能不一

23、样，时，结果可能不一样，所以所以感知器算法的解不是感知器算法的解不是单值的。单值的。判别界面判别界面d(X)=0如图示。如图示。消消防防给给水水10 最小错误率贝叶斯决策最小错误率贝叶斯决策对两类问题对两类问题)()|()|(2211PpPpXX1X若若，则，则)()|()|(2211PpPpXX2X若若，则，则可改写为：可改写为：统计学中称统计学中称l12(X)为似然比，为似然比，为似然比阈值。为似然比阈值。)()(12PP21X)|()|()(2112XXXppl12)(PP若若，则，则（4-8）消消防防给给水水2111)(|)()|()|(iiiPpPpPXXX16.02.

24、095.05.005.005.05.0884.02.095.05.005.095.02.0)|(2XP)|()|(12XXPP2X例例4.1 假定在细胞识别中，病变细胞的先验概率和正常细胞的假定在细胞识别中，病变细胞的先验概率和正常细胞的先验概率分别为先验概率分别为。现有一待识别细胞，。现有一待识别细胞，其观察值为其观察值为X，从类条件概率密度发布曲线上查得：，从类条件概率密度发布曲线上查得：95.0)(,05.0)(21PP5.0)|(1Xp2.0)|(2Xp试对细胞试对细胞X进行分类。进行分类。解：解：方法方法1 通过后验概率计算。通过后验概率计算。消消防防给给水水方法方法2：利用

25、先验概率和类概率密度计算。：利用先验概率和类概率密度计算。025.005.05.0)|(11Pp X19.095.02.0)|(22Pp X)()|()|(1122PpPpXX2X，是正常细胞。，是正常细胞。消消防防给给水水最小风险贝叶斯决策基本思想：最小风险贝叶斯决策基本思想：以各种错误分类所造成的以各种错误分类所造成的平均风险平均风险最小为规则最小为规则，进行分类，进行分类决策。决策。11 最小风险贝叶斯决策最小风险贝叶斯决策消消防防给给水水)(|)(|)(222211212PpLPpLrXXX)(|)(|)(221211111PpLPpLrXXX2）两类情况：对样本）两类情况

26、：对样本 X121)()(XXX则若rr221)()(XXX则若rr当当X 被判为被判为1 1类时：类时：当当X 被判为被判为2类时：类时：（4-15）（4-16）)(|)(|)(|)(|2222112122121111PpLPpLPpLPpLXXXX )(|)(|111121222212PpLLPpLLXX)()()()()|()|(111212221221PLLPLLppXX由（由（4-15）式：式：MjjjijiPpLr1)()|()(XX决策规则：决策规则：消消防防给给水水令：令：)|()|()(2112XXXppl，称似然比；，称似然比；)()()()(111122222112

28、验概率在细胞识别中，病变细胞和正常细胞的先验概率分别为分别为现有一待识别细胞，观察值为现有一待识别细胞，观察值为X，从类概率密度分布曲线上查得从类概率密度分布曲线上查得损失函数分别为损失函数分别为L11=0，L21=10，L22=0，L12=1。按最小风险贝。按最小风险贝叶斯决策分类。叶斯决策分类。为病变细胞。为病变细胞。9.105.0)010(95.0)01()()()()(111212221212PLLPLL消消防防给给水水经过选择或变换，组成识别特征，尽可能保留分类信息，在经过选择或变换，组成识别特征，尽可能保留分类信息，在保证一定分类精度的前提下，减少特征维数，使分类器的工作

29、保证一定分类精度的前提下，减少特征维数，使分类器的工作即快又准确。即快又准确。12 特征选择和提取的目的特征选择和提取的目的 13 特征选择和特征提取的异同特征选择和特征提取的异同（1）特征选择：从）特征选择：从L个度量值集合个度量值集合中按一定准中按一定准则则选出选出供分类用的子集，作为降维（供分类用的子集，作为降维（m维，维，m L）的分类）的分类特征。特征。Lxxx,21（2）特征提取：使一组度量值）特征提取：使一组度量值通过某种通过某种变换变换产生新的产生新的m个特征个特征，作为降维的分类特征，作为降维的分类特征，其中其中。),(21Lxxxih),(21myyyLmmi

30、;,2,1复习复习消消防防给给水水14特征提取的方法特征提取的方法NiiiN1T)(1MXMXCNiiN11XM其中，其中，第二步：计算第二步：计算C的特征值，对特征值从小到大进行排队，选择的特征值，对特征值从小到大进行排队，选择前前m个。个。TTTmuuuA21消消防防给给水水第四步：利用第四步：利用A对样本集对样本集X进行变换。进行变换。AXX*则则m维（维（m n）模式向量）模式向量X*就是就是作为分类用的模式向量。作为分类用的模式向量。解：解：1)求样本均值向量和协方差矩阵。求样本均值向量和协方差矩阵。31T 3.1,231iiXM31TT3.01.01.07.031ii

31、iMMXXC消消防防给给水水由由 03.01.01.07.0得得3.01.01.07.0C2765.017236.02211选由归一化特征向量由归一化特征向量u1构成变换矩阵构成变换矩阵A：1.2,5.066.41A消消防防给给水水74.01*1 AXX48.12*2 AXX28.03*3 AXX变换前变换前变换后变换后T1 1,1 XT22,2XT3 1,3X消消防防给给水水多类类内散布矩阵多类类内散布矩阵Sw15 特征选择特征选择从从n个特征中选择个特征中选择d个个(d n)最优特征构成分类用特征向量。最优特征构成分类用特征向量。1）散布矩阵准则）散布矩阵准则类别可分性测度类别可分性测度类间散布矩阵类间散布矩阵Sb多类总体散布矩阵多类总体散布矩阵St)(tr11bwJSS)(tr)(tr2wbJSSwbJSSln3wbwJSSS 4特征选择准则特征选择准则使使tr(Sw)最小最小使使tr(Sb)最大最大使使J1J4最大最大复习复习消消防防给给水水例：从例：从5个特征中选出个特征中选出2个特征作为模式向量。个特征作为模式向量。

展开阅读全文