模式识别复习资料ppt课件.ppt

复习复习1模式和模式识别的概念 1）模式：对某些感兴趣的客体的定量的或结构的描述。模式类是具有某些共同特性的模式的集合。2）模式识别：研究一种自动技术，依靠这种技术，计算机将自动地（或人尽量少地干涉）把待别识模式分配到各自的模式类中去。复习复习2 模式识别系统组成 学习过程判决过程分类规则训练分类决策数据获取预处理特征选择 或提取模式识别系统框图 复习复习1）监督分类：需要依靠已知类别的训练样本集，按照他们特征向量的分布来确定判别函数，然后利用判别函数对未知模式进行分类。需要足够的先验知识。判别。需要有足够的先验知识。2）非监督分类：用于没有先验知识的情况，通常采用聚类分析的方法。3 监督分类和无监督分类复习复习4 模式识别整体知识结构5 最大最小距离算法（小中取大距离算法最大最小距离算法（小中取大距离算法）算法描述算法描述 选任意一模式样本做为第一聚类中心Z1。选择离Z1距离最远的样本作为第二聚类中心Z2。逐个计算各模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。例当聚类中心数k=2时，计算min(Di1,Di2)，i=1，N（N个最小距离）复习复习 将样本 按最近距离划分到相应聚类中心对应的类别中。重复步骤，直到没有新的聚类中心出现为止。在所有最小距离中选出最大距离，如该最大值达到 的一定分数比值(阈值T)以上，则相应的样本点取为新的聚类中心，返回；否则，寻找聚类中心的工作结束。（：用试探法取为一固定分数，如1/2。）则Z3存在。例k=2时复习复习例2.1 对图示模式样本用最大最小距离算法进行聚类分析。选选Z1=X1距距Z1最远，选为最远，选为Z2。计算。计算T。对应最小距离对应最小距离中的最大值，中的最大值，且且T，选作，选作Z3。结果：Z1=X1；Z2=X6；Z3=X7。用全体模式对三个聚类中心计算最小距离中的最大值，无T 情况，停止寻找中心。聚类10个最小距离中，X7对应的距离T,算法描述算法描述1）N个初始模式样本自成一类，即建立N 类：计算各类之间（即各样本间）的距离，得一NN维距离矩阵D(0)。“0”表示初始状态。(G_Group)6 层次聚类法层次聚类法2）假设已求得距离矩阵D(n)（n为逐次聚类合并的次数），找出D(n)中的最小元素，将其对应的两类合并为一类。由此建立新的分类：3）计算合并后新类别之间的距离，得D(n+1)。4）跳至第2步，重复计算及合并。复习复习 结束条件：结束条件：1）取距离阈值T，当D(n)的最小分量超过给定值 T 时，算法停 止。所得即为聚类结果。2）或不设阈值T，一直将全部样本聚成一类为止，输出聚类的分 级树。复习复习例：给出6个五维模式样本如下，按最短距离准则进行系统聚类分类。计算各类间欧氏距离：解：（1）将每一样本看作单独一类，得：，；（2）将最小距离 对应的类 和 合并为1类，得 新的分类。计算聚类后的距离矩阵D(1)：由D(0)递推出D(1)。得距离矩阵D(0)：（3）将D(1)中最小值 对应的类合为一类，得D(2)。（4）将D(2)中最小值 对应的类合为一类，得D(3)。若给定的阈值为 ，D(3)中的最小元素 ，聚类结束。若无阈值，继续分下去，最终全部样本归为一类。可给出聚类过程的树状表示图。层次聚类法的树状表示 类间距离类间距离阈值增大，阈值增大，分类变粗。分类变粗。7 K-均值算法均值算法 算法描述算法描述（1）任选K个初始聚类中心：Z1(1)，Z2(1)，ZK(1)（2）按最小距离原则将其余样品分配到K个聚类中心中的某一 个。Nj：第j类的样本数。（3）计算各个聚类中心的新向量值：（4）如果 ，则回到（2），将模式 样本逐个重新分类，重复迭代计算。，算法收敛，计算完毕。如果复习复习例2.3：已知20个模式样本如下，试用K-均值算法分类。解：取K=2，并选：计算距离，聚类：，可得到：计算新的聚类中：判断：，故返回第步。从新的聚类中心得：有：计算聚类中心：返回第步，以Z1(3)，Z2(3)为中心进行聚类。以新的聚类中心分类，求得的分类结果与前一次迭代结果相 同：计算新聚类中心向量值，聚类中心与前一次结果相同，即：，故算法收敛，得聚类中心为结果图示：图2.10 K-均值算法聚类结果X1X4X3X5X8X9X7X10X2X6x1x213579135790X11X12X13X14X15X16X17X18X19X20 上述K-均值算法，其类型数目假定已知为K个。当K未知时，可以令K逐渐增加，此时J j 会单调减少。最初减小速度快，但当K 增加到一定数值时，减小速度会减慢，直到K=总样本数N 时，Jj=0。JjK关系曲线如下图：8 聚类准则函数聚类准则函数Jj与与K的关系曲线的关系曲线JjA135724608109K 曲线的拐点 A 对应着接近最优的K值（J 值减小量、计算量以及分类效果的权衡）。并非所有的情况都容易找到关系曲线的拐点。迭代自组织的数据分析算法可以确定模式类的个数K。两分法(1)多类情况1：用线性判别函数将属于i类的模式与其余不属于i类的模式分开。将某个待分类模式 X 分别代入 M 个类的d(X)中，若只有di(X)0，其他d(X)均0，则判为i类。识别分类时：9 线性判别函数线性判别函数复习复习 全部不属任何类 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，分类失效。相当于不确定区(indefiniteregion，IR)。此法将 M 个多类问题分成M个两类问题，识别每一类均需M个判别函数。识别出所有的M类仍是这M个函数。例例3.1 设有一个三类问题，其判别式为：现有一模式，X=7,5T，试判定应属于哪类？并画出三类模式的分布区域。解：将X=7,5T代入上三式，有：三个判别界面分别为：图示如下：1 0-112x1x0)(2=Xd0)(3=Xd(10)=Xd44 步骤：a)画出界面直线。b)判别界面正负侧：找特殊点带入。c)找交集。感知器算法步骤：（1）选择N个分属于1和 2类的模式样本构成训练样本集 X1,XN 构成增广向量形式，并进行规范化处理。任取权向量初始 值W(1)，开始迭代。迭代次数k=1。（2）用全部训练样本进行一轮迭代，计算WT(k)Xi 的值，并修 正权向量。分两种情况，更新权向量的值：9 感知器算法感知器算法复习复习c：正的校正增量。分类器对第i个模式做了错误分类，权向量校正为：统一写为：分类正确，权向量不变：（3）分析分类结果：只要有一个错误分类，回到（2），直至 对所有样本正确分类。分类正确时，对权向量“赏”这里用“不罚”，即权向量不变；分类错误时，对权向量“罚”对其修改，向正确的方向转换。感知器算法是一种赏罚过程：感知器算法是一种赏罚过程：例例3.8 已知两类训练样本解：所有样本写成增广向量形式；进行规范化处理，属于2的样本乘以(1)。用感知器算法求出将模式分为两类的权向量解和判别函数。任取W(1)=0，取c=1，迭代过程为：第一轮：有两个WT(k)Xi 0的情况（错判），进行第二轮迭代。第二轮：第三轮：第四轮：该轮迭代的分类结果全部正确，故解向量相应的判别函数为：当c、W(1)取其他值时，结果可能不一样，所以感知器算法的解不是单值的。判别界面d(X)=0如图示。10 最小错误率贝叶斯决策最小错误率贝叶斯决策对两类问题若，则若，则可改写为：统计学中称l12(X)为似然比，为似然比阈值。若，则 （4-8）例例4.1 假定在细胞识别中，病变细胞的先验概率和正常细胞的先验概率分别为 。现有一待识别细胞，其观察值为X，从类条件概率密度发布曲线上查得：试对细胞X进行分类。解：方法1 通过后验概率计算。方法2：利用先验概率和类概率密度计算。，是正常细胞。最小风险贝叶斯决策基本思想：以各种错误分类所造成的平均风险最小为规则，进行分类决策。11 最小风险贝叶斯决策最小风险贝叶斯决策2）两类情况）两类情况：对样本 X当X 被判为1类时：当X 被判为2类时：（4-15）（4-16）由（4-15）式：决策规则：令：，称似然比；，为阈值。计算 。计算 。定义损失函数Lij。判别步骤：类概率密度函数p(X|i)也称i的似然函数解：计算 和 得：例4.2 在细胞识别中，病变细胞和正常细胞的先验概率 分别为现有一待识别细胞，观察值为X，从类概率密度分布曲线上查得损失函数分别为L11=0，L21=10，L22=0，L12=1。按最小风险贝叶斯决策分类。为病变细胞。经过选择或变换，组成识别特征，尽可能保留分类信息，在保证一定分类精度的前提下，减少特征维数，使分类器的工作即快又准确。12 特征选择和提取的目的特征选择和提取的目的 13 特征选择和特征提取的异同特征选择和特征提取的异同（1）特征选择：从L个度量值集合 中按一定准 则选出供分类用的子集，作为降维（m维，m L）的分类 特征。（2）特征提取：使一组度量值 通过某种变换 产生新的m个特征 ，作为降维的分类特征，其中 。复习复习14特征提取的方法特征提取的方法其中，第二步：计算C的特征值，对特征值从小到大进行排队，选择 前m个。第四步：利用A对样本集X进行变换。则m维（m n）模式向量X*就是作为分类用的模式向量。解：1)求样本均值向量和协方差矩阵。由 得由归一化特征向量u1构成变换矩阵A：变换前变换后多类类内散布矩阵Sw15 特征选择特征选择 从n个特征中选择d个(d n)最优特征构成分类用特征向量。1）散布矩阵准则类别可分性测度类间散布矩阵Sb多类总体散布矩阵St特征选择准则 使tr(Sw)最小使tr(Sb)最大使J1J4最大 复习复习例：从5个特征中选出2个特征作为模式向量。