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

哈哈尔滨工工业大学大学课程总复习11.关于期末考关于期末考试/考察考察2.章章节知知识点整理点整理21.1.关于期末考关于期末考试/考察考察31.确认考试人员名单；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分（记得要得要带尺子，尺子，铅笔，橡皮擦笔，橡皮擦）【关于期末考试】42.2.章章节知知识点整理点整理5哈哈尔滨工工业大学大学第1章 模式识别绪论6模式识别基本概念模式识别系统组成模式识别基本问题应用领域小结7模式模式识别系系统组成成 8【模式识别系统组成】1.1.信息的信息的获取：通取：通过测量、采量、采样、量化并用矩、量化并用矩阵或向量表示。通常或向量表示。通常输入入对象的信息有三个象的信息有三个类型：二型：二维图像（文字、指像（文字、指纹、地、地图、照片等）、照片等）、一、一维波形（波形（脑电图、心、心电图、机械震、机械震动波形等）、物理参量和波形等）、物理参量和逻辑值（体（体检中的温度、血化中的温度、血化验结果等）果等）2.2.预处理：去除噪声，加理：去除噪声，加强有用的信息，并有用的信息，并对输入入测量量仪器或其它器或其它因素造成的干因素造成的干扰进行行处理。理。3.3.特征提取与特征提取与选择：为了了实现有效的有效的识别分分类，要，要对原始数据原始数据进行行变换得到最能反映分得到最能反映分类本本质的特征，此的特征，此过程程为特征提取和特征提取和选择。4.4.分分类决策：在特征空决策：在特征空间中用中用统计方法把被方法把被识别对象象归为某一某一类。基本作法是在基本作法是在样本本训练集基集基础上确定某个判决上确定某个判决规则，使按，使按这种判决种判决规则对被被识别对象象进行分行分类所造成的所造成的错误识别率最小或引起的率最小或引起的损失最小。失最小。5.5.后后处理：理：针对决策采取相决策采取相应的行的行动。信息信息获取取预处理理特征提取特征提取与与选择分分类决策决策后后处理理模式模式识别系系统组成框成框图9哈哈尔滨工工业大学大学第2章 贝叶斯决策理论10概率概率论基基础知知识贝叶斯决策基叶斯决策基础知知识基于最小基于最小错误率的率的贝叶斯决策叶斯决策基于最小基于最小风险的的贝叶斯决策叶斯决策贝叶斯分叶斯分类器器设计正正态分布分布时的的统计决策决策小小结11贝叶斯决策基叶斯决策基础知知识12【贝叶斯决策基础知识】贝叶斯决策理叶斯决策理论先验概率：后验概率：类条件概率：贝叶斯公式：13基于最小基于最小错误率的率的贝叶斯决策叶斯决策14【基于最小错误率的贝叶斯决策】（4）15【基于最小错误率的贝叶斯决策】16【基于最小错误率的贝叶斯决策】17【基于最小风险的贝叶斯决策】概念概念决策决策决策空决策空间 前面所前面所讲的的错误率达到最小。在某些率达到最小。在某些实际应用中，最小用中，最小错误率的率的贝叶斯准叶斯准则并不适合。以癌并不适合。以癌细胞胞识别为例，例，诊断中如果断中如果把正常把正常细胞判胞判为癌症癌症细胞，固然会胞，固然会给病人精神造成病人精神造成伤害，但害，但伤害有限；相反地，若把癌症害有限；相反地，若把癌症细胞胞误判判为正常正常细胞，将会使早期胞，将会使早期的癌症患者失去治的癌症患者失去治疗的最佳的最佳时机，造成机，造成验证的后果。的后果。18【基于最小风险的贝叶斯决策】数学描述数学描述19【基于最小风险的贝叶斯决策】期望期望风险：条件期望条件期望损失：失：目的：期望目的：期望风险最小化最小化20【基于最小风险的贝叶斯决策】最小最小风险贝叶斯决策叶斯决策规则:21【基于最小风险的贝叶斯决策】算法步算法步骤:22【基于最小风险的贝叶斯决策】例例题2:2:23【基于最小风险的贝叶斯决策】24【基于最小错误率的贝叶斯决策与最小风险的贝叶斯决策的关系】定理：定理：0-10-1风险25哈哈尔滨工工业大学大学第3章 概率密度函数估计26引言引言参数估参数估计正正态分布的参数估分布的参数估计非参数估非参数估计本章小本章小结27参数估参数估计 28【参数估计】最大似然估最大似然估计贝叶斯估叶斯估计贝叶斯学叶斯学习29【最大似然估计】基本假基本假设30【最大似然估计】基本概念基本概念31【最大似然估计】基本原理基本原理32【最大似然估计】估估计量量估估计值33【最大似然估计】一元参数一元参数34【最大似然估计】多元参数多元参数35【最大似然估计】例子（梯度法不适合）：不成功！不成功！36【贝叶斯估计】采用最小采用最小风险贝叶斯决策叶斯决策37【贝叶斯估计】38【贝叶斯估计】39【贝叶斯学习】40【三种方法总结】41【三种方法总结】42哈哈尔滨工工业大学大学第4章 线性判别函数43线性判性判别函数的基本概念函数的基本概念Fisher线性判性判别准准则函数函数感知准感知准则函数函数最小平方最小平方误差准差准则函数函数多多类问题444.1.1概念的提出概念的提出【线性判别函数】定定义454.1.1概念的提出概念的提出【线性判别函数】分分类决策决策464.1.1概念的提出概念的提出【线性判别函数】分析分析474.1.1概念的提出概念的提出【线性判别函数】分析分析说明：判明：判别函数函数g(x)正比于任意一正比于任意一点点x到超平面的代数距离。到超平面的代数距离。48FisherFisher线性判性判别准准则函数函数49【Fisher线性判别准则函数】概念概念 应用用统计方法解决模式方法解决模式识别问题时，往往遇到，往往遇到维数数问题（举例：例：图像像识别），降），降维是有效方法。考是有效方法。考虑到降到降d d维空空间的的样本投影到一条直本投影到一条直线上，如果投影到任意一条直上，如果投影到任意一条直线上上则可能造可能造成本来有很好区分度的成本来有很好区分度的样本在直本在直线上上线性不可分。因此，直性不可分。因此，直线的方向很关的方向很关键。50【Fisher线性判别准则函数】基本思路基本思路 FisherFisher判判别的基本思想：希望投影后的一的基本思想：希望投影后的一维数据数据满足：足：两两类之之间的距离尽可能的距离尽可能远；每一每一类自身尽可能自身尽可能紧凑。凑。51【Fisher线性判别准则函数】52【Fisher线性判别准则函数】53【Fisher线性判别准则函数】54【Fisher线性判别准则函数】55哈哈尔滨工工业大学大学第5章 非线性判别函数56基本概念基本概念基于距离的分段基于距离的分段线性判性判别函数函数分段分段线性分性分类器器设计二次判二次判别函数函数程序程序设计方法方法实际应用系用系统设计研究研究报告告57哈哈尔滨工工业大学大学第6章 特征的选择与提取581.1.引言引言2 2 类别可分离性判据可分离性判据3 3 特征特征选择4.4.特征提取特征提取59哈哈尔滨工工业大学大学第7章 近邻法600.0.引言引言1.1.近近邻法原理及其决策法原理及其决策规则 2.2.快速搜索近快速搜索近邻法法3.3.剪剪辑近近邻法法4.4.压缩近近邻法法611.1.近近邻法原理及其决策法原理及其决策规则 62【基本原理】最小距离分最小距离分类器是将各器是将各类训练样本划分成若干子本划分成若干子类，并，并在每个子在每个子类中确定代表点，一般用子中确定代表点，一般用子类的的质心或心或邻近近质心的心的某一某一样本本为代表点。代表点。测试样本的本的类别则以其与以其与这些代表点距些代表点距离最近作决策。离最近作决策。该法的缺点是所法的缺点是所选择的代表点并的代表点并不一定不一定能很能很好地代表各好地代表各类,后果将使后果将使错误率增加。率增加。近近邻法的基本思想：法的基本思想：增加代表点的数量有没有可能增加代表点的数量有没有可能获得性能好的分得性能好的分类器呢器呢?一种一种极端的情况是以全部极端的情况是以全部训练样本作本作为“代表点代表点”，计算算测试样本与本与这些些“代表点代表点”，即所有，即所有样本的距离，并以最近本的距离，并以最近邻者的者的类别作作为决策。此决策。此为近近邻法的基本思想。法的基本思想。63【最近邻法决策规则】若若则其中其中 表示是表示是 类的第的第 个个样本。决策本。决策规则为:定定义：将与：将与测试样本最近本最近邻样本本类别作作为决策的方法。决策的方法。对一个一个 类别问题，每，每类有有 个个样本，本，则第第 类 的判的判别函数函数64 最近最近邻法可以法可以扩展成找展成找测试样本的本的 个最近个最近样本作决策本作决策依据的方法。其基本依据的方法。其基本规则是，在所有是，在所有 个个样本中找到与本中找到与测试样本的本的 个最近个最近邻者；者；其中各其中各类别所占个数表示成所占个数表示成 则决策决策为：【-近邻法决策规则】注意：注意：近近邻一般采用一般采用 为奇数，跟投票表决一奇数，跟投票表决一样，避免因两，避免因两种票数相等而种票数相等而难以决策。以决策。若若则65【问题的提出】上述上述讨论中可以看出，尽管近中可以看出，尽管近邻法有其法有其优良品良品质，但是它的，但是它的一个一个严重弱点与重弱点与问题是需要存是需要存储全部全部训练样本，以及繁重的距本，以及繁重的距离离计算量。但以算量。但以简单的方式降低的方式降低样本数量，只能使其性能降低，本数量，只能使其性能降低，这也是不希望的。也是不希望的。为此要研究既能减少近此要研究既能减少近邻法法计算量与存算量与存储量，量，同同时又不明又不明显降低其性能的一些改降低其性能的一些改进算法。算法。改改进算法大致基于两种原理算法大致基于两种原理。一种是。一种是对样本集本集进行行组织与整与整理，分群分理，分群分层，尽可能将，尽可能将计算算压缩到在接近到在接近测试样本本邻域的小域的小范范围内，避免与内，避免与训练样本集中每个本集中每个样本本进行距离行距离计算。算。另一种原理另一种原理则是在原有是在原有样本集中挑本集中挑选出出对分分类计算有效的算有效的样本，使本，使样本本总数合理地减少，以同数合理地减少，以同时达到既减少达到既减少计算量，又算量，又减少存减少存储量的双重效果。量的双重效果。662.2.快速搜索近快速搜索近邻法法673.3.剪剪辑近近邻法法684.4.压缩近近邻法法69哈哈尔滨工工业大学大学第8章 主成分分析(PCA)701.1.引言引言2 2 主成分分析主成分分析(PCA)(PCA)3 3 基于基于K-LK-L展开式的特征提取展开式的特征提取4.4.应用用举例例712.2.主成分分析主成分分析72根据方差最大化原理，用一组新的、线性无关且相互正交的向量来表征原来数据矩阵的行（或列）。这组新向量（主成分）是原始数据向量的线性组合。通过对原始数据的平移、尺度伸平移、尺度伸缩(减均减均值除方差除方差)和坐坐标旋旋转(特征分解特征分解)，得到新的新的坐坐标系系(特征向量特征向量)后，用原始数据在新坐标系下的投影投影(点点积)来替代原始变量。一一.主成分分析的基本原理主成分分析的基本原理73主成分分析的主成分分析的优点点它它能能找找到到表表现原原始始数数据据阵最最重重要要的的变量的量的组合合通通过表表示示最最大大的的方方差差，能能有有效效地地直直观反映反映样本之本之间的关系的关系能能从从最最大大的的几几个个主主成成分分的的得得分分来来近近似似反映原始的数据反映原始的数据阵的信息的信息74图像像预处理理 【人脸识别】75【人脸识别】76【人脸识别】77【人脸识别】78基于基于PCA构建特征构建特征脸空空间是是对图像像进行行K-L变换，以去除，以去除样本本间的相关性，然后根据特征的相关性，然后根据特征值的大小的大小选择特征向量。特征向量。这种方法首先将人种方法首先将人脸图像映射像映射为高高维空空间的向量，然后的向量，然后应用基于用基于统计的离散的离散K-L变换方法，构造一个各分量互不相方法，构造一个各分量互不相关的特征空关的特征空间，即特征，即特征脸空空间，再将人，再将人脸图像在高像在高维空空间中的向量映射到特征中的向量映射到特征脸空空间，得到特征系数。，得到特征系数。PCA构建特征构建特征脸空空间79哈哈尔滨工工业大学大学第9章 人工神经网络801.1.基基础知知识2.2.前前馈神神经网网络3.3.反反馈神神经网网络4.4.自自组织映射神映射神经网网络81神神经网网络的学的学习方法方法u神经网络的学习：从环境中获取知识并改进自身性能，主要指调节网络参数使网络达到某种度量，又称为网络的训练。u学习方式：监督学习非监督学习再励学习u学习规则：误差纠正学习算法竞争学习算法824.自自组织映射映射自自组织映射映射Self-Organizing Map 亦称亦称SOFM。Kohonen 提出（提出（1980s）83SOM SOM 用于非用于非监督模式督模式识别自组织学习过程本身就是一个非监督学习过程SOMA(自组织分析)基本思路：用未知样本集训练SOM;计算象密度图;根据象密度图划分聚类(把结点代表的小聚类合并)。特点：对数据分布形状少依赖性；可反映真实存在的聚类数目，尤其适合人机合作分析(高维数据的有效二维显示)数学上待研究的问题多：象密度与样本分布密度之间的关系？拓扑保持特性？如何在SOM 平面上聚类？84哈哈尔滨工工业大学大学第10章 无监督学习851.1.引言引言2.2.单峰子集（峰子集（类）的分离方法）的分离方法3.3.类别分离的分离的间接方法接方法4.4.分分级聚聚类方法方法86监督模式识别：（已知）样本集训练（学习）识别（分类）非监督模式识别：（未知）样本集非监督学习（聚类分析）后处理【引言】通过寻找可能存在的分类来理解某一对象将复杂多样的对象用有限典型来代表根据：某种假设（对聚类应具有的性质的认识）结果：聚类（clusters）属中间结果（数学结果），需经解释赋予物理含义（后处理）应用：复杂系统未知特性分析（举例）航天、航空、航海（具体阐述）直接方法:基于概率密度函数估计 相间接聚类方法:基于样本间似性度量87【动态聚类】多次迭代，逐步调整类别划分，最终使某准则达到最优。三个要点：选某种距离作为样本相似性度量 定义某个准则函数，用于评价聚类质量。初始分类方法及迭代算法lC-均值聚类lISODATA聚类常用算法：88【动态聚类】C C 均均值算法算法89【动态聚类】C C 均均值算法算法90【动态聚类】C C 均均值算法算法初始划分：一般可先选代表点，再进行初始分类。代表点选择方法：1.经验选择2.随机分成c 类，选各类重心作为代表点3.“密度”法。计算每个样本的一定球形邻域内的样本数作为“密度”，选“密度”最大的样本点作为第一个代表点，在离它一定距离选最大“密度”点作为第二个代表点，依次类推。4.用前c 个样本点作为代表点。5.用c 1聚类求c 个代表点：各类中心外加离它们最远的样本点，从1 类开始。91【动态聚类】C C 均均值算法算法初始分类方法：1.最近距离法。离哪个代表点近就归入哪一类。2.最近距离法归类，但每次都重新计算该类代表点。3.直接划分初始分类：每一个样本自成一类，第二个样本若离它小于某距离阈值则归入此类，否则建新类，4.将特征归一化，用样本各特征之和作为初始分类依据。说明：初始划分无一定之规，多为启发式方法。C 均值方法结果受初值影响，是局部最优解。92【动态聚类】C 均值聚类方法用于非监督模式识别的问题：l要求类别数已知；l是最小方差划分，并不一定能反映内在分布；l与初始划分有关，不保证全局最优。C C 均均值算法算法934.分分级级聚聚类类方法方法（Hierachical Clustering）94【分级聚类方法】思想：从各思想：从各类只有一个只有一个样本点开始，逐本点开始，逐级合并，每合并，每级只合并只合并两两类，直到最后所有，直到最后所有样本都本都归到一到一类。Hierarchical tree-dendrogram聚聚类过程中逐程中逐级考考查类间相似度，依此决定相似度，依此决定类别数数95树枝长度：反映结点/树枝之间的相似度或距离树枝位置：在不改变树结构情况下可以任意调整，调整方法需研究距离/相似性度量：多种选择，如欧式距离、相关、CityBlock、【分级聚类方法】96距离（相似性度量）：样本之间的度量聚类之间的度量算法（从底向上）：（1）初始化，每个样本形成一类（2）把相似性最大（距离最小）的两类合并（3）重复（2），直到所有样本合并为两类。【分级聚类方法】97【分级聚类方法】98哈哈尔滨工工业大学大学第11章 模糊模式识别991.引言引言2.模糊集的基本知模糊集的基本知识3.模糊特征和模糊分模糊特征和模糊分类4.特征的模糊特征的模糊评价价5.模糊聚模糊聚类方法方法6.模糊模糊k 近近邻分分类器器100【模糊C 均值方法（FCM）】C C 均均值算法算法101【模糊C 均值】102【模糊C 均值】103【模糊C 均值】模糊模糊C 均均值算法：算法：104【改进的模糊C 均值算法】模糊模糊C 均均值算法的一个缺点：算法的一个缺点：105【改进的模糊C 均值算法】106【改进的模糊C 均值算法】特点特点AFC 有更好的有更好的鲁棒，且棒，且对给定的聚定的聚类数目不十分敏感。但有数目不十分敏感。但有时可能会可能会出出现一个一个类中只包含一个中只包含一个样本的情况，可通本的情况，可通过在距离在距离计算中引入非算中引入非线性，使之不会小于革性，使之不会小于革值来改来改进。AFC、FCM 与与C 均均值一一样，依，依赖于初于初值。实验效果效果举例例例一：例一：类别重迭及重迭及类别不明不明显情况情况+：C 圴圴值：FCMO：AFC107【改进的模糊C 均值算法】正确聚类(C=4)CM聚类(C=3)FCM聚类(C=3)AFC聚类(C=3)例二：例二：给定定类别数与数与实际类别数不一致的情况数不一致的情况108改进的模糊C均值算法改进的模糊C均值算法较前面提到的模糊C均值算法具有更好的鲁棒性，它不但可以在有孤立样本存在的情况下得到较好的聚类效果，而且可以放松隶属度条件，而且因为放松了隶属度条件，使最终聚类结果对预先确定的聚类数目不十分敏感。与确定性C均值算法和模糊C均值算法一样，改进的模糊C均值算法仍然对聚类中心的初值十分敏感，为了得到较好的结果，可以用确定性C均值算法或模糊C均值算法的结果作为初值。【改进的模糊C 均值算法】109哈哈尔滨工工业大学大学第12章 统计学习理论1101.1.统计学学习理理论2.2.支持向量机支持向量机3.3.核方法核方法1112.支持向量机支持向量机112根据根据统计学学习理理论，学，学习机器的机器的实际风险由由经验风险值和置和置信范信范围值两部分两部分组成。而基于成。而基于经验风险最小化准最小化准则的学的学习方方法只法只强调了了训练样本的本的经验风险最小最小误差，没有最小化置信差，没有最小化置信范范围值，因此其推广能力，因此其推广能力较差。差。【基本概念】Vapnik 与与1995年提出的支持向量机（年提出的支持向量机（Support Vector Machine,SVM）以）以训练误差作差作为优化化问题的的约束条件，以束条件，以置信范置信范围值最小化作最小化作为优化目化目标，即，即SVM是一种基于是一种基于结构构风险最小化准最小化准则的学的学习方法，其推广能力明方法，其推广能力明显优于一些于一些传统的的学学习方法。方法。113【基本概念】由于由于SVM 的求解最后的求解最后转化成二次化成二次规划划问题的求解，的求解，因此因此SVM 的解是全局唯一的最的解是全局唯一的最优解解SVM在解决在解决小小样本、非本、非线性及高性及高维模式模式识别问题中表中表现出出许多特有的多特有的优势，并能，并能够推广推广应用到函用到函数数拟合等其他机器学合等其他机器学习问题中中Joachims 最近采用最近采用SVM在在Reuters-21578来来进行行文本分文本分类，并声称它比当前，并声称它比当前发表的其他方法都好表的其他方法都好114【基本概念】由于由于SVM 的求解最后的求解最后转化成二次化成二次规划划问题的求解，因此的求解，因此SVM 的解是全局唯一的最的解是全局唯一的最优解解SVM在解决小在解决小样本、非本、非线性及高性及高维模式模式识别问题中表中表现出出许多特有的多特有的优势，并能，并能够推广推广应用到函数用到函数拟合等其他机合等其他机器学器学习问题中中Joachims 最近采用最近采用SVM在在Reuters-21578来来进行文本分行文本分类，并声称它比当前并声称它比当前发表的其他方法都好表的其他方法都好 115特点：特点：非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射;对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心;支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。SVM是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”(transductiveinference),大大简化了通常的分类和回归等问题。【基本概念】116特点：特点：SVM SVM 的最的最终决策函数只由少数的支持向量所确定决策函数只由少数的支持向量所确定,计算的复算的复杂性取决于支持向量的数目性取决于支持向量的数目,而不是而不是样本空本空间的的维数数,这在某种意在某种意义上避免了上避免了“维数灾数灾难”。少数支持向量决定了最少数支持向量决定了最终结果果,这不但可以帮助我不但可以帮助我们抓住关抓住关键样本、本、“剔除剔除”大量冗余大量冗余样本本,而且注定了而且注定了该方法不但算法方法不但算法简单,而且具有而且具有较好的好的“鲁棒棒”性。性。这种种“鲁棒棒”性主要体性主要体现在在:增、增、删非支持向量非支持向量样本本对模型没有影响模型没有影响;支持向量支持向量样本集具有一定的本集具有一定的鲁棒性棒性;有些成功的有些成功的应用中用中,SVM,SVM 方法方法对核的核的选取不敏感。取不敏感。【基本概念】117【SVM示意图】支持向量网络1183.核方法核方法1192、核方法解决非、核方法解决非线性映射性映射问题【基本概念】1203、核函数表示非、核函数表示非线性映射的例子性映射的例子【基本概念】1214、怎、怎样使用核函数？使用核函数？图3.1核学习的非线性特征提取示意图【基本概念】122祝各位同学祝各位同学学学业有成有成123