哈工大模式识别课程期末总结

主要内容1.关于期末考试/考察2.章节知识点整理第一页1第二页，共123页。1.关于期末考试/考察第二页2第三页，共123页。1.确认考试人员名单；2.考试/考察方式学位课：考试70%+报告30%；选修课：报告100%（不用考试）。3.报告形式(见word文档)4.考试题目（100分）1．简答题（35分）7*5’=35分2．推导题（8分）3．证明题（8分）4．问答题（24分）3*8’=24分5．计算题（25分）9’+8’+8’=25分（记得要带尺子，铅笔，橡皮擦）【关于期末考试】第三页3第四页，共123页。2.章节知识点整理第四页4第五页，共123页。哈尔滨工业大学第1章模式识别绪论第五页第六页，共123页。主要内容模式识别基本概念模式识别系统组成模式识别基本问题应用领域小结第六页第七页，共123页。模式识别系统组成

第七页第八页，共123页。【模式识别系统组成】1.信息的获取：通过测量、采样、量化并用矩阵或向量表示。通常输入对象的信息有三个类型：二维图像（文字、指纹、地图、照片等）、一维波形（脑电图、心电图、机械震动波形等）、物理参量和逻辑值（体检中的温度、血化验结果等）2.预处理：去除噪声，加强有用的信息，并对输入测量仪器或其它因素造成的干扰进行处理。3.特征提取与选择：为了实现有效的识别分类，要对原始数据进行变换得到最能反映分类本质的特征，此过程为特征提取和选择。4.分类决策：在特征空间中用统计方法把被识别对象归为某一类。基本作法是在样本训练集基础上确定某个判决规则，使按这种判决规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。5.后处理：针对决策采取相应的行动。信息获取预处理特征提取与选择分类决策后处理模式识别系统组成框图第八页第九页，共123页。哈尔滨工业大学第2章贝叶斯决策理论第九页第十页，共123页。主要内容概率论基础知识贝叶斯决策基础知识基于最小错误率的贝叶斯决策基于最小风险的贝叶斯决策贝叶斯分类器设计正态分布时的统计决策小结第十页第十一页，共123页。贝叶斯决策基础知识第十一页第十二页，共123页。【贝叶斯决策基础知识】贝叶斯决策理论先验概率：后验概率：类条件概率：贝叶斯公式：第十二页第十三页，共123页。基于最小错误率的贝叶斯决策第十三页第十四页，共123页。【基于最小错误率的贝叶斯决策】

（4）第十四页第十五页，共123页。【基于最小错误率的贝叶斯决策】

第十五页第十六页，共123页。【基于最小错误率的贝叶斯决策】第十六页第十七页，共123页。【基于最小风险的贝叶斯决策】概念

决策决策空间前面所讲的错误率达到最小。在某些实际应用中，最小错误率的贝叶斯准则并不适合。以癌细胞识别为例，诊断中如果把正常细胞判为癌症细胞，固然会给病人精神造成伤害，但伤害有限；相反地，若把癌症细胞误判为正常细胞，将会使早期的癌症患者失去治疗的最佳时机，造成验证的后果。第十七页第十八页，共123页。【基于最小风险的贝叶斯决策】数学描述

第十八页第十九页，共123页。【基于最小风险的贝叶斯决策】期望风险：条件期望损失：目的：期望风险最小化第十九页第二十页，共123页。【基于最小风险的贝叶斯决策】最小风险贝叶斯决策规则:

第二十页第二十一页，共123页。【基于最小风险的贝叶斯决策】算法步骤:

第二十一页第二十二页，共123页。【基于最小风险的贝叶斯决策】例题2:

第二十二页第二十三页，共123页。【基于最小风险的贝叶斯决策】第二十三页第二十四页，共123页。【基于最小错误率的贝叶斯决策与最小风险的贝叶斯决策的关系】定理：0-1风险

第二十四页第二十五页，共123页。哈尔滨工业大学第3章概率密度函数估计第二十五页第二十六页，共123页。主要内容

引言参数估计正态分布的参数估计非参数估计本章小结第二十六页第二十七页，共123页。参数估计

第二十七页第二十八页，共123页。【参数估计】

最大似然估计贝叶斯估计贝叶斯学习第二十八页第二十九页，共123页。【最大似然估计】基本假设第二十九页第三十页，共123页。【最大似然估计】基本概念第三十页第三十一页，共123页。【最大似然估计】基本原理第三十一页第三十二页，共123页。【最大似然估计】估计量估计值

第三十二页第三十三页，共123页。【最大似然估计】一元参数第三十三页第三十四页，共123页。【最大似然估计】多元参数第三十四页第三十五页，共123页。【最大似然估计】例子（梯度法不适合）：不成功！第三十五页第三十六页，共123页。【贝叶斯估计】采用最小风险贝叶斯决策第三十六页第三十七页，共123页。【贝叶斯估计】第三十七页第三十八页，共123页。【贝叶斯估计】第三十八页第三十九页，共123页。【贝叶斯学习】第三十九页第四十页，共123页。【三种方法总结】第四十页第四十一页，共123页。【三种方法总结】第四十一页第四十二页，共123页。哈尔滨工业大学第4章线性判别函数第四十二页第四十三页，共123页。主要内容线性判别函数的基本概念Fisher线性判别准则函数感知准则函数最小平方误差准则函数多类问题第四十三页第四十四页，共123页。§4.1.1概念的提出【线性判别函数】定义第四十四页第四十五页，共123页。§4.1.1概念的提出【线性判别函数】分类决策第四十五页第四十六页，共123页。§4.1.1概念的提出【线性判别函数】分析第四十六页第四十七页，共123页。§4.1.1概念的提出【线性判别函数】分析说明：判别函数g(x)正比于任意一点x到超平面的代数距离。第四十七页第四十八页，共123页。Fisher线性判别准则函数第四十八页第四十九页，共123页。【Fisher线性判别准则函数】概念

应用统计方法解决模式识别问题时，往往遇到维数问题（举例：图像识别），降维是有效方法。考虑到降d维空间的样本投影到一条直线上，如果投影到任意一条直线上则可能造成本来有很好区分度的样本在直线上线性不可分。因此，直线的方向很关键。第四十九页第五十页，共123页。【Fisher线性判别准则函数】基本思路

Fisher判别的基本思想：希望投影后的一维数据满足：两类之间的距离尽可能远；每一类自身尽可能紧凑。第五十页第五十一页，共123页。【Fisher线性判别准则函数】第五十一页第五十二页，共123页。【Fisher线性判别准则函数】第五十二页第五十三页，共123页。【Fisher线性判别准则函数】第五十三页第五十四页，共123页。【Fisher线性判别准则函数】第五十四页第五十五页，共123页。哈尔滨工业大学第5章非线性判别函数第五十五页第五十六页，共123页。主要内容基本概念基于距离的分段线性判别函数分段线性分类器设计二次判别函数程序设计方法实际应用系统设计研究报告第五十六页第五十七页，共123页。哈尔滨工业大学第6章特征的选择与提取第五十七页第五十八页，共123页。主要内容1.引言2类别可分离性判据3特征选择4.特征提取第五十八页第五十九页，共123页。哈尔滨工业大学第7章近邻法第五十九页59第六十页，共123页。主要内容0.引言1.近邻法原理及其决策规则2.快速搜索近邻法3.剪辑近邻法4.压缩近邻法第六十页60第六十一页，共123页。1.近邻法原理及其决策规则第六十一页61第六十二页，共123页。【基本原理】最小距离分类器是将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本为代表点。测试样本的类别则以其与这些代表点距离最近作决策。该法的缺点是所选择的代表点并不一定能很好地代表各类,后果将使错误率增加。近邻法的基本思想：增加代表点的数量有没有可能获得性能好的分类器呢?一种极端的情况是以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。此为近邻法的基本思想。第六十二页62第六十三页，共123页。【最近邻法决策规则

】若则其中表示是类的第

个样本。决策规则为:

定义：将与测试样本最近邻样本类别作为决策的方法。对一个

类别问题，每类有个样本，，则第

类的判别函数

第六十三页63第六十四页，共123页。最近邻法可以扩展成找测试样本的个最近样本作决策依据的方法。其基本规则是，在所有个样本中找到与测试样本的

个最近邻者；其中各类别所占个数表示成则决策为：【-近邻法决策规则

】注意：

近邻一般采用为奇数，跟投票表决一样，避免因两种票数相等而难以决策。

若则第六十四页64第六十五页，共123页。【问题的提出】上述讨论中可以看出，尽管近邻法有其优良品质，但是它的一个严重弱点与问题是需要存储全部训练样本，以及繁重的距离计算量。但以简单的方式降低样本数量，只能使其性能降低，这也是不希望的。为此要研究既能减少近邻法计算量与存储量，同时又不明显降低其性能的一些改进算法。

改进算法大致基于两种原理。一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免与训练样本集中每个样本进行距离计算。另一种原理则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。第六十五页65第六十六页，共123页。2.快速搜索近邻法第六十六页66第六十七页，共123页。3.剪辑近邻法第六十七页67第六十八页，共123页。4.压缩近邻法第六十八页68第六十九页，共123页。哈尔滨工业大学第8章主成分分析(PCA)第六十九页69第七十页，共123页。主要内容1.引言2主成分分析(PCA)3基于K-L展开式的特征提取4.应用举例第七十页70第七十一页，共123页。2.主成分分析第七十一页71第七十二页，共123页。根据方差最大化原理，用一组新的、线性无关且相互正交的向量来表征原来数据矩阵的行（或列）。这组新向量（主成分）是原始数据向量的线性组合。通过对原始数据的平移、尺度伸缩(减均值除方差)和坐标旋转(特征分解)，得到新的坐标系(特征向量)后，用原始数据在新坐标系下的投影(点积)来替代原始变量。一.主成分分析的基本原理第七十二页72第七十三页，共123页。主成分分析的优点

★它能找到表现原始数据阵最重要的变量的组合★

通过表示最大的方差，能有效地直观反映样本之间的关系★

能从最大的几个主成分的得分来近似反映原始的数据阵的信息第七十三页73第七十四页，共123页。图像预处理

【人脸识别】第七十四页74第七十五页，共123页。【人脸识别】第七十五页75第七十六页，共123页。【人脸识别】第七十六页76第七十七页，共123页。【人脸识别】第七十七页77第七十八页，共123页。基于PCA构建特征脸空间是对图像进行K-L变换，以去除样本间的相关性，然后根据特征值的大小选择特征向量。这种方法首先将人脸图像映射为高维空间的向量，然后应用基于统计的离散K-L变换方法，构造一个各分量互不相关的特征空间，即特征脸空间，再将人脸图像在高维空间中的向量映射到特征脸空间，得到特征系数。PCA构建特征脸空间第七十八页78第七十九页，共123页。哈尔滨工业大学第9章人工神经网络第七十九页第八十页，共123页。主要内容1.基础知识2.前馈神经网络3.反馈神经网络4.自组织映射神经网络第八十页第八十一页，共123页。神经网络的学习方法神经网络的学习：从环境中获取知识并改进自身性能，主要指调节网络参数使网络达到某种度量，又称为网络的训练。学习方式：监督学习非监督学习再励学习学习规则：误差纠正学习算法竞争学习算法第八十一页第八十二页，共123页。4.自组织映射自组织映射Self-OrganizingMap亦称SOFM。Kohonen提出（1980s）第八十二页第八十三页，共123页。SOM用于非监督模式识别自组织学习过程本身就是一个非监督学习过程SOMA(自组织分析)基本思路：用未知样本集训练SOM;计算象密度图;根据象密度图划分聚类(把结点代表的小聚类合并)。特点：对数据分布形状少依赖性；可反映真实存在的聚类数目，尤其适合人机合作分析(高维数据的有效二维显示)数学上待研究的问题多：象密度与样本分布密度之间的关系？拓扑保持特性？如何在SOM平面上聚类？第八十三页第八十四页，共123页。哈尔滨工业大学第10章无监督学习第八十四页第八十五页，共123页。主要内容1.引言2.单峰子集（类）的分离方法3.类别分离的间接方法4.分级聚类方法第八十五页第八十六页，共123页。监督模式识别：（已知）样本集→训练（学习）→识别（分类）非监督模式识别：（未知）样本集→非监督学习（聚类分析）→后处理【引言】通过寻找可能存在的分类来理解某一对象将复杂多样的对象用有限典型来代表根据：某种假设（对聚类应具有的性质的认识）结果：聚类（clusters）属中间结果（数学结果），需经解释赋予物理含义（后处理）应用：复杂系统未知特性分析（举例）航天、航空、航海（具体阐述）直接方法:基于概率密度函数估计

相间接聚类方法:基于样本间似性度量第八十六页第八十七页，共123页。【动态聚类】多次迭代，逐步调整类别划分，最终使某准则达到最优。三个要点：①选某种距离作为样本相似性度量②定义某个准则函数，用于评价聚类质量。③初始分类方法及迭代算法C-均值聚类ISODATA聚类常用算法：第八十七页第八十八页，共123页。【动态聚类】C均值算法第八十八页第八十九页，共123页。【动态聚类】C均值算法第八十九页第九十页，共123页。【动态聚类】C均值算法初始划分：一般可先选代表点，再进行初始分类。代表点选择方法：1.经验选择2.随机分成c类，选各类重心作为代表点3.“密度”法。计算每个样本的一定球形邻域内的样本数作为“密度”，选“密度”最大的样本点作为第一个代表点，在离它一定距离选最大“密度”点作为第二个代表点，…，依次类推。4.用前c个样本点作为代表点。5.用c−1聚类求c个代表点：各类中心外加离它们最远的样本点，从1类开始。第九十页第九十一页，共123页。【动态聚类】C均值算法初始分类方法：1.最近距离法。离哪个代表点近就归入哪一类。2.最近距离法归类，但每次都重新计算该类代表点。3.直接划分初始分类：每一个样本自成一类，第二个样本若离它小于某距离阈值则归入此类，否则建新类，……4.将特征归一化，用样本各特征之和作为初始分类依据。说明：初始划分无一定之规，多为启发式方法。C均值方法结果受初值影响，是局部最优解。第九十一页第九十二页，共123页。【动态聚类】C均值聚类方法用于非监督模式识别的问题：要求类别数已知；是最小方差划分，并不一定能反映内在分布；与初始划分有关，不保证全局最优。C均值算法第九十二页第九十三页，共123页。4.分级聚类方法（HierachicalClustering）第九十三页第九十四页，共123页。【分级聚类方法

】思想：从各类只有一个样本点开始，逐级合并，每级只合并两类，直到最后所有样本都归到一类。Hierarchicaltree--dendrogram聚类过程中逐级考查类间相似度，依此决定类别数第九十四页第九十五页，共123页。树枝长度：反映结点/树枝之间的相似度或距离树枝位置：在不改变树结构情况下可以任意调整，调整方法需研究距离/相似性度量：多种选择，如欧式距离、相关、CityBlock、…【分级聚类方法

】第九十五页第九十六页，共123页。距离（相似性度量）：样本之间的度量聚类之间的度量算法（从底向上）：（1）初始化，每个样本形成一类（2）把相似性最大（距离最小）的两类合并（3）重复（2），直到所有样本合并为两类。【分级聚类方法

】第九十六页第九十七页，共123页。【分级聚类方法

】第九十七页第九十八页，共123页。哈尔滨工业大学第11章模糊模式识别第九十八页第九十九页，共123页。主要内容1.引言2.模糊集的基本知识3.模糊特征和模糊分类4.特征的模糊评价5.模糊聚类方法6.模糊k近邻分类器第九十九页第一百页，共123页。【模糊C均值方法（FCM）】C均值算法第一百页第一百零一页，共123页。【模糊C均值】第一百零一页第一百零二页，共123页。【模糊C均值】第一百零二页第一百零三页，共123页。【模糊C均值】模糊C均值算法：第一百零三页第一百零四页，共123页。【改进的模糊C均值算法】模糊C均值算法的一个缺点：第一百零四页第一百零五页，共123页。【改进的模糊C均值算法】第一百零五页第一百零六页，共123页。【改进的模糊C均值算法】特点AFC有更好的鲁棒，且对给定的聚类数目不十分敏感。但有时可能会出现一个类中只包含一个样本的情况，可通过在距离计算中引入非线性，使之不会小于革值来改进。

AFC、FCM与C均值一样，依赖于初值。实验效果举例例一：类别重迭及类别不明显情况+：C圴值×：FCMO：AFC第一百零六页第一百零七页，共123页。【改进的模糊C均值算法】正确聚类(C=4)CM聚类(C=3)FCM聚类(C=3)AFC聚类(C=3)例二：给定类别数与实际类别数不一致的情况第一百零七页第一百零八页，共123页。改进的模糊C均值算法改进的模糊C均值算法较前面提到的模糊C均值算法具有更好的鲁棒性，它不但可以在有孤立样本存在的情况下得到较好的聚类效果，而且可以放松隶属度条件，而且因为放松了隶属度条件，使最终聚类结果对预先确定的聚类数目不十分敏感。与确定性C均值算法和模糊C均值算法一样，改进的模糊C均值算法仍然对聚类中心的初值十分敏感，为了得到较好的结果，可以用确定性C均值算法或模糊C均值算法的结果作为初值。【改进的模糊C均值算法】第一百零八页108第一百零九页，共123页。哈尔滨工业大学第12章统计学习理论第一百零九页第一百一十页，共123页。主要内容1.统计学习理论2.支持向量机3.核方法第一百一十页第一百一十一页，共123页。2.支持向量机第一百一十一页第一百一十二页，共123页。根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部分组成。而基于经验风险最小化准则的学习方法只强调了训练样本的经验风险最小误差，没有最小化置信范围值，因此其推广能力较差。【基本概念】Vapnik与1995年提出的支持向量机（SupportVectorMachine,SVM）以训练误差作为优化问题的约束条件，以置信范围值最小化作为优化目标，即SVM是一种基于结构风险最小化准则的学习方法，其推广能力明显优于一些传统的学习方法。第一百一十二页第一百一十三页，共123页。【基本概念】由于SVM的求解最后转化成二次规划问题的求解，因此SVM的解是全局唯一的最优解SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中Joachims最近采用SVM在Reuters-21578来进行文本分类，并声称它比当前发表的其他方法都好第一百一十三页第一百一十四页，共123页。【基本概念】由于SVM的求解最后转化成二次规划问题的求解，因此SVM的解是全