模式识别复习资料PPT教案.pptx

模式识别模式识别(m sh sh bi)复习资料复习资料第一页，共45页。复习复习(fx)2 模式识别系统(xtng)组成 学习过程判 决 过程分类规则训练分类决策数据获取预处理特征选择 或提取模式识别系统框图 第1页/共45页第二页，共45页。复习复习(fx)1）监督分类：需要依靠已知类别的训练样本集，按照他们特征向量的分布来确定判别函数，然后利用判别函数对未知模式进行(jnxng)分类。需要足够的先验知识。判别。需要有足够的先验知识。2）非监督分类：用于没有先验知识的情况，通常采用聚类分析的方法。3 监督(jind)分类和无监督(jind)分类第2页/共45页第三页，共45页。复习复习(fx)4 模式识别(m sh sh bi)整体知识结构第3页/共45页第四页，共45页。5 最大最小距离最大最小距离(jl)算法（小中取大距离算法（小中取大距离(jl)算法算法）算法算法(sun f)描述描述 选任意一模式样本(yngbn)做为第一聚类中心Z1。选择离Z1距离最远的样本作为第二聚类中心Z2。逐个计算各模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。例当聚类中心数k=2时，计算min(Di1,Di2)，i=1，N（N个最小距离）复习复习第4页/共45页第五页，共45页。将样本 按最近距离划分到相应聚类中心对应的类别中。重复步骤，直到(zhdo)没有新的聚类中心出现为止。在所有最小距离中选出最大距离，如该最大值达到 的一定分数比值(阈值T)以上，则相应的样本点取为新的聚类中心，返回；否则，寻找聚类中心的工作结束。（：用试探法取为一固定分数，如1/2。）则Z3存在。例k=2时复习复习(fx)第5页/共45页第六页，共45页。例2.1 对图示模式(msh)样本用最大最小距离算法进行聚类分析。选选Z1=X1距距Z1最远，选为最远，选为Z2。计算。计算(j sun)T。对应对应(duyng)最最小距离中的最大值，小距离中的最大值，且且T，选作，选作Z3。结果：Z1=X1；Z2=X6；Z3=X7。用全体模式对三个聚类中心计算最小距离中的最大值，无T 情况，停止寻找中心。聚类10个最小距离中，X7对应的距离T,第6页/共45页第七页，共45页。算法算法(sun f)描描述述1）N个初始模式样本自成一类，即建立N 类：计算各类之间（即各样本间）的距离(jl)，得一NN维距离(jl)矩阵D(0)。“0”表示初始状态。(G_Group)6 层次层次(cngc)聚类法聚类法2）假设已求得距离矩阵D(n)（n为逐次聚类合并的次数），找出D(n)中的最小元素，将其对应的两类合并为一类。由此建立新的分类：3）计算合并后新类别之间的距离，得D(n+1)。4）跳至第2步，重复计算及合并。复习复习第7页/共45页第八页，共45页。结束条件：结束条件：1）取距离阈值）取距离阈值T，当，当D(n)的最小分量超过给定值的最小分量超过给定值 T 时，算法停时，算法停 止。所得即为聚类结果。止。所得即为聚类结果。2）或不设阈值）或不设阈值T，一直将全部，一直将全部(qunb)样本聚成一类为止，输出聚类的样本聚成一类为止，输出聚类的分分 级树。级树。复习复习(fx)第8页/共45页第九页，共45页。例：给出6个五维模式样本如下，按最短距离准则(zhnz)进行系统聚类分类。计算(j sun)各类间欧氏距离：解：（1）将每一样本看作(kn zu)单独一类，得：，；第9页/共45页第十页，共45页。D D(0)(0)0 00 00 00 00 00 0（2）将最小距离 对应的类 和 合并为1类，得 新的分类。计算(j sun)聚类后的距离矩阵D(1)：由D(0)递推出D(1)。得距离(jl)矩阵D(0)：第10页/共45页第十一页，共45页。D D(0)(0)0 00 00 00 00 00 0 D D(1)(1)0 0 0 0 0 0 0 0 0 0（3）将D(1)中最小值 对应的类合为一类，得D(2)。D D(2)(2)0 0 0 0 0 0 0 0第11页/共45页第十二页，共45页。（4）将D(2)中最小值 对应(duyng)的类合为一类，得D(3)。D D(2)(2)0 0 0 0 0 0 0 0 D D(3)(3)0 0 0 0 0 0若给定(i dn)的阈值为 ，D(3)中的最小元素 ，聚类结束。若无阈值，继续分下去(xi q)，最终全部样本归为一类。可给出聚类过程的树状表示图。第12页/共45页第十三页，共45页。层次(cngc)聚类法的树状表示 类间距离类间距离阈值阈值(y zh)增大，增大，分类变粗。分类变粗。第13页/共45页第十四页，共45页。7 K-均值均值(jn zh)算法算法 算法算法(sun f)描述描述（1）任选(rn xun)K个初始聚类中心：Z1(1)，Z2(1)，ZK(1)（2）按最小距离原则将其余样品分配到K个聚类中心中的某一 个。Nj：第j类的样本数。（3）计算各个聚类中心的新向量值：（4）如果 ，则回到（2），将模式 样本逐个重新分类，重复迭代计算。，算法收敛，计算完毕。如果复习复习第14页/共45页第十五页，共45页。例2.3：已知20个模式样本(yngbn)如下，试用K-均值算法分类。解：取K=2，并选：计算(j sun)距离，聚类：第15页/共45页第十六页，共45页。：，可得到：计算(j sun)新的聚类中：判断：，故返回第步。第16页/共45页第十七页，共45页。从新的聚类中心(zhngxn)得：有：计算(j sun)聚类中心：第17页/共45页第十八页，共45页。返回第步，以Z1(3)，Z2(3)为中心(zhngxn)进行聚类。以新的聚类中心分类(fn li)，求得的分类(fn li)结果与前一次迭代结果相 同：计算新聚类中心向量值，聚类中心与前一次结果(ji gu)相同，即：，故算法收敛，得聚类中心为结果图示：第18页/共45页第十九页，共45页。图2.10 K-均值算法(sun f)聚类结果X1X4X3X5X8X9X7X10X2X6x1x213579135790X11X12X13X14X15X16X17X18X19X20第19页/共45页第二十页，共45页。上述K-均值算法，其类型数目假定已知为K个。当K未知时，可以(ky)令K逐渐增加，此时J j 会单调减少。最初减小速度快，但当K 增加到一定数值时，减小速度会减慢，直到K=总样本数N 时，Jj=0。JjK关系曲线如下图：8 聚类准则聚类准则(zhnz)函数函数Jj与与K的关系曲线的关系曲线JjA135724608109K 曲线的拐点 A 对应着接近最优的K值（J 值减小量、计算量以及分类效果的权衡）。并非所有的情况都容易找到关系曲线的拐点。迭代自组织的数据分析算法(sun f)可以确定模式类的个数K。第20页/共45页第二十一页，共45页。两分法(1)多类情况1：用线性判别函数将属于(shy)i类的模式与其余不属于(shy)i类的模式分开。将某个待分类模式 X 分别代入 M 个类的d(X)中，若只有di(X)0，其他d(X)均0，则判为i类。识别(shbi)分类时：9 线性判别函数线性判别函数复习复习(fx)第21页/共45页第二十二页，共45页。全部不属任何类 IR，可能 属于1w或3w 1w2w3w0)(2=Xd0)(3=Xd+IR，可能 属于3w或2w+-0)(1=Xd0,0312ddd0,0321ddd0,0,321dddIR，可能属于1w或2w 0,0213ddd2x1x+对某一模式区，di(X)0的条件超过一个，或全部的di(X)0，分类(fn li)失效。相当于不确定区(indefiniteregion，IR)。此法将 M 个多类问题(wnt)分成M个两类问题(wnt)，识别每一类均需M个判别函数。识别出所有的M类仍是这M个函数。第22页/共45页第二十三页，共45页。例例3.1 设有一个三类设有一个三类(sn li)问题，其判别式为：问题，其判别式为：现有一模式，X=7,5T，试判定应属于哪类？并画出三类模式的分布(fnb)区域。解：将X=7,5T代入上三式，有：三个判别(pnbi)界面分别为：图示如下：第23页/共45页第二十四页，共45页。1 0-112x1x0)(2=Xd0)(3=Xd(10)=Xd44 步骤(bzhu)：a)画出界面(jimin)直线。b)判别界面正负(zhn f)侧：找特殊点带入。c)找交集。第24页/共45页第二十五页，共45页。感知器算法(sun f)步骤：（1）选择N个分属于1和 2类的模式样本构成训练样本集 X1,XN 构成增广向量形式(xngsh)，并进行规范化处理。任取权向量初始 值W(1)，开始迭代。迭代次数k=1。（2）用全部训练样本进行一轮迭代，计算(j sun)WT(k)Xi 的值，并修 正权向量。分两种情况，更新权向量的值：9 感知器算法感知器算法复习复习第25页/共45页第二十六页，共45页。c：正的校正(jiozhng)增量。分类器对第i个模式做了错误(cuw)分类，权向量校正为：统一(tngy)写为：分类正确，权向量不变：（3）分析分类结果：只要有一个错误分类，回到（2），直至 对所有样本正确分类。分类正确时，对权向量“赏”这里用“不罚”，即权向量不变；分类错误时，对权向量“罚”对其修改，向正确的方向转换。感知器算法是一种赏罚过程：感知器算法是一种赏罚过程：第26页/共45页第二十七页，共45页。例例3.8 已知两类训练样本解：所有样本写成增广向量形式(xngsh)；进行规范化处理，属于2的样本乘以(1)。用感知器算法求出将模式(msh)分为两类的权向量解和判别函数。第27页/共45页第二十八页，共45页。任取W(1)=0，取c=1，迭代(di di)过程为：第一轮：有两个WT(k)Xi 0的情况（错判），进行(jnxng)第二轮迭代。第28页/共45页第二十九页，共45页。第二轮：第三轮：第四轮：第29页/共45页第三十页，共45页。该轮迭代的分类(fn li)结果全部正确，故解向量相应(xingyng)的判别函数为：当c、W(1)取其他(qt)值时，结果可能不一样，所以感知器算法的解不是单值的。判别界面d(X)=0如图示。第30页/共45页第三十一页，共45页。10 最小错误率贝叶斯决策最小错误率贝叶斯决策(juc)对两类问题(wnt)若，则若，则可改写(gixi)为：统计学中称l12(X)为似然比，为似然比阈值。若，则 （4-8）第31页/共45页第三十二页，共45页。例例4.1 假定在细胞识别中，病变细胞的先验概率和正常细胞的假定在细胞识别中，病变细胞的先验概率和正常细胞的先验概率分别为先验概率分别为 。现有一待识别细胞，。现有一待识别细胞，其观察值为其观察值为X，从类条件概率密度发布，从类条件概率密度发布(fb)曲线上查得：曲线上查得：试对细胞(xbo)X进行分类。解：方法(fngf)1 通过后验概率计算。第32页/共45页第三十三页，共45页。方法2：利用(lyng)先验概率和类概率密度计算。，是正常细胞。第33页/共45页第三十四页，共45页。最小风险贝叶斯决策基本思想：以各种错误分类所造成的平均风险最小为规则，进行分类决策。11 最小风险最小风险(fngxin)贝叶斯决贝叶斯决策策第34页/共45页第三十五页，共45页。2）两类情况）两类情况(qngkung)：对样本对样本 X当X 被判为1类时：当X 被判为2类时：（4-15）（4-16）由（4-15）式：决策(juc)规则：第35页/共45页第三十六页，共45页。令：，称似然比；，为阈值。计算 。计算 。定义损失(snsh)函数Lij。判别(pnbi)步骤：类概率密度函数(hnsh)p(X|i)也称i的似然函数(hnsh)第36页/共45页第三十七页，共45页。解：计算 和 得：例4.2 在细胞识别中，病变(bngbin)细胞和正常细胞的先验概率 分别为现有一待识别细胞(xbo)，观察值为X，从类概率密度分布曲线上查得损失函数分别(fnbi)为L11=0，L21=10，L22=0，L12=1。按最小风险贝叶斯决策分类。为病变细胞。第37页/共45页第三十八页，共45页。经过选择或变换，组成识别特征，尽可能保留(boli)分类信息，在保证一定分类精度的前提下，减少特征维数，使分类器的工作即快又准确。12 特征选择和提取特征选择和提取(tq)的目的的目的 13 特征选择和特征提取的异同特征选择和特征提取的异同(ytng)（1）特征选择：从L个度量值集合 中按一定准 则选出供分类用的子集，作为降维（m维，m L）的分类 特征。（2）特征提取：使一组度量值 通过某种变换 产生新的m个特征 ，作为降维的分类特征，其中 。复习复习第38页/共45页第三十九页，共45页。14特征提取的方法特征提取的方法(fngf)其中(qzhng)，第二步：计算C的特征值，对特征值从小到大进行(jnxng)排队，选择 前m个。第39页/共45页第四十页，共45页。第四步：利用A对样本(yngbn)集X进行变换。则m维（m n）模式(msh)向量X*就是作为分类用的模式(msh)向量。解：1)求样本均值向量(xingling)和协方差矩阵。第40页/共45页第四十一页，共45页。由 得由归一化特征向量u1构成变换(binhun)矩阵A：第41页/共45页第四十二页，共45页。变换(binhun)前变换(binhun)后第42页/共45页第四十三页，共45页。多类类内散布(snb)矩阵Sw15 特征选择特征选择 从n个特征中选择d个(d n)最优特征构成(guchng)分类用特征向量。1）散布(snb)矩阵准则类别可分性测度类间散布矩阵Sb多类总体散布矩阵St特征选择准则 使tr(Sw)最小使tr(Sb)最大使J1J4最大 复习复习第43页/共45页第四十四页，共45页。例：从5个特征中选出2个特征作为模式(msh)向量。第44页/共45页第四十五页，共45页。