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

1、哈尔滨工业大学哈尔滨工业大学21. 关于期末考试关于期末考试/考察考察2. 章节知识点整理章节知识点整理31. 1. 关于期末考试关于期末考试/ /考察考察41. 确认考试人员名单；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分 （记得要带尺子，铅笔，橡皮擦记得要带尺子，铅笔，橡皮擦）【关于期末考试】52.2.章节知识点整理章节知识点整理哈尔滨工业大学哈尔滨工

2、业大学模式识别基本概念模式识别系统组成模式识别基本问题应用领域小结模式识别系统组成模式识别系统组成 【模式识别系统组成】1. 1. 信息的获取：通过测量、采样、量化并用矩阵或向量表示。通常信息的获取：通过测量、采样、量化并用矩阵或向量表示。通常输入对象的信息有三个类型：二维图像（文字、指纹、地图、照片输入对象的信息有三个类型：二维图像（文字、指纹、地图、照片等）、一维波形（脑电图、心电图、机械震动波形等）、物理参量等）、一维波形（脑电图、心电图、机械震动波形等）、物理参量和逻辑值（体检中的温度、血化验结果等）和逻辑值（体检中的温度、血化验结果等）2. 2. 预处理：去除噪声，加强有用的信息，并

3、对输入测量仪器或其它预处理：去除噪声，加强有用的信息，并对输入测量仪器或其它因素造成的干扰进行处理。因素造成的干扰进行处理。3. 3. 特征提取与选择：为了实现有效的识别分类，要对原始数据进行特征提取与选择：为了实现有效的识别分类，要对原始数据进行变换得到最能反映分类本质的特征，此过程为特征提取和选择。变换得到最能反映分类本质的特征，此过程为特征提取和选择。4. 4. 分类决策：在特征空间中用统计方法把被识别对象归为某一类。分类决策：在特征空间中用统计方法把被识别对象归为某一类。基本作法是在样本训练集基础上确定某个判决规则，使按这种判决基本作法是在样本训练集基础上确定某个判决规则，使按这种判决

4、规则对被识别对象进行分类所造成的错误识别率最小或引起的损失规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。最小。5.5.后处理：针对决策采取相应的行动。后处理：针对决策采取相应的行动。信息信息获取获取预处理预处理特征提取特征提取与选择与选择分类分类决策决策后处理后处理模式识别系统组成框图模式识别系统组成框图哈尔滨工业大学哈尔滨工业大学概率论基础知识概率论基础知识贝叶斯决策基础知识贝叶斯决策基础知识基于最小错误率的贝叶斯决策基于最小错误率的贝叶斯决策基于最小风险的贝叶斯决策基于最小风险的贝叶斯决策贝叶斯分类器设计贝叶斯分类器设计正态分布时的统计决策正态分布时的统计决策小结小结贝叶

5、斯决策基础知识贝叶斯决策基础知识【贝叶斯决策基础知识】贝叶斯决策理论贝叶斯决策理论 先验概率： 后验概率： 类条件概率： 贝叶斯公式：iPiPxiPx iiiPPPPxxx基于最小错误率的贝基于最小错误率的贝叶斯决策叶斯决策【基于最小错误率的贝叶斯决策】 1122()( )ln ( )ln( |)ln( |)ln()Ph xl xp xp xP 1122()( )ln ( )ln( |)ln( |)ln()Ph xl xp xp xP （4）1x2x【基于最小错误率的贝叶斯决策】 【基于最小错误率的贝叶斯决策】【基于最小风险的贝叶斯决策】概念概念 决策决策决策空间决策空间 前面所讲的错误率达到

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

7、失：条件期望损失：目的：期望风险最小化目的：期望风险最小化1(| )(,)(,) (| ),1,2,.,ciijijjjRxEPx ia ( ( )| ) ( )RRxx p x dx【基于最小风险的贝叶斯决策】最小风险贝叶斯决策规则最小风险贝叶斯决策规则: : 1,2,.,(| )min(| )kiiaRxRxka【基于最小风险的贝叶斯决策】算法步骤算法步骤: : 【基于最小风险的贝叶斯决策】例题例题2:2: 【基于最小风险的贝叶斯决策】【基于最小错误率的贝叶斯决策与最小风险的贝叶斯决策的关系】定理：定理：0-10-1风险风险 哈尔滨工业大学哈尔滨工业大学 引言引言参数估计参数估计正态分布的

8、参数估计正态分布的参数估计非参数估计非参数估计本章小结本章小结参数估计参数估计 【参数估计】 最大似然估计最大似然估计贝叶斯估计贝叶斯估计贝叶斯学习贝叶斯学习【最大似然估计】基本假设基本假设【最大似然估计】基本概念基本概念【最大似然估计】基本原理基本原理【最大似然估计】估计量估计量估计值估计值 【最大似然估计】一元参数一元参数【最大似然估计】多元参数多元参数【最大似然估计】12211,( | )0 xp x其它121212N211( ,.,|,),( )0Np x xxxl 其它21H( )Nln 121H( )1N221H( )1N 例子（梯度法不适合）：不成功！不成功！12xxx12,xx

9、21,xx【贝叶斯估计】采用最小风险贝叶斯决策采用最小风险贝叶斯决策1(| )(,)(,) (| ),1,2,.,ciijijjjRxEPx ia 【贝叶斯估计】( , ) ( , )dERp xd dx ( | ) ( )( | ) ( )( | )( )( | ) ( )p xpp xppxp xp xpd( , )( | ) ( )( | ) ( )pxpx p xp xp( , ) ( | ) ( ) ( )( , ) ( | ) ( | ) ( )dddEEERpx p x d dxp xpx d dxRx p x dx ( | )( , ) ( | )Rxpx d 【贝叶斯估计】【

10、贝叶斯学习】【三种方法总结】【三种方法总结】哈尔滨工业大学哈尔滨工业大学线性判别函数的基本概念线性判别函数的基本概念Fisher线性判别准则函数线性判别准则函数感知准则函数感知准则函数最小平方误差准则函数最小平方误差准则函数多类问题多类问题4.1.1 概念的提出概念的提出【线性判别函数】定义定义4.1.1 概念的提出概念的提出【线性判别函数】分类决策分类决策4.1.1 概念的提出概念的提出【线性判别函数】分析分析4.1.1 概念的提出概念的提出【线性判别函数】分析分析说明：判别函数说明：判别函数g(x)正比于任意一正比于任意一点点x到超平面的代数距离。到超平面的代数距离。FisherFishe

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

12、er判别的基本思想：希望投影后的一维数据满足：判别的基本思想：希望投影后的一维数据满足： 两类之间的距离尽可能远；两类之间的距离尽可能远； 每一类自身尽可能紧凑。每一类自身尽可能紧凑。【 Fisher线性判别准则函数】【 Fisher线性判别准则函数】【 Fisher线性判别准则函数】【 Fisher线性判别准则函数】哈尔滨工业大学哈尔滨工业大学基本概念基本概念基于距离的分段线性判别函数基于距离的分段线性判别函数分段线性分类器设计分段线性分类器设计二次判别函数二次判别函数程序设计方法程序设计方法实际应用系统设计研究报告实际应用系统设计研究报告哈尔滨工业大学哈尔滨工业大学1.1.引言引言2 2

13、类别可分离性判据类别可分离性判据3 3 特征选择特征选择4.4.特征提取特征提取60哈尔滨工业大学哈尔滨工业大学610.0.引言引言1.1.近邻法原理及其决策规则近邻法原理及其决策规则 2.2.快速搜索近邻法快速搜索近邻法3.3.剪辑近邻法剪辑近邻法4.4.压缩近邻法压缩近邻法621.1.近邻法原理及其决策规则近邻法原理及其决策规则 63【基本原理】 最小距离分类器是将各类训练样本划分成若干子类，并最小距离分类器是将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本为代表点。测试样本的类别则以其与这些代

14、表点距某一样本为代表点。测试样本的类别则以其与这些代表点距离最近作决策。该法的缺点是所选择的代表点并离最近作决策。该法的缺点是所选择的代表点并不一定不一定能很能很好地代表各类好地代表各类, 后果将使错误率增加。后果将使错误率增加。 近邻法的基本思想：近邻法的基本思想： 增加代表点的数量有没有可能获得性能好的分类器呢增加代表点的数量有没有可能获得性能好的分类器呢?一种一种极端的情况是以全部训练样本作为极端的情况是以全部训练样本作为“代表点代表点”，计算测试，计算测试样本与这些样本与这些“代表点代表点”，即所有样本的距离，并以最近邻，即所有样本的距离，并以最近邻者的类别作为决策。此为近邻法的基本思

15、想。者的类别作为决策。此为近邻法的基本思想。 64【最近邻法决策规则 】若若则则其中其中 表示是表示是 类的第类的第 个样本。决策规则为个样本。决策规则为: 定义：将与测试样本最近邻样本类别作为决策的方法。定义：将与测试样本最近邻样本类别作为决策的方法。 对一个对一个 类别问题，每类有类别问题，每类有 个样本，个样本， ，则，则第第 类类 的判别函数的判别函数 65 最近邻法可以扩展成找测试样本的最近邻法可以扩展成找测试样本的 个最近样本作决策个最近样本作决策依据的方法。其基本规则是，在所有依据的方法。其基本规则是，在所有 个样本中找到与测试个样本中找到与测试样本的样本的 个最近邻者；个最近邻

16、者； 其中各类别所占个数表示成其中各类别所占个数表示成 则决策为：则决策为：【 -近邻法决策规则 】 注意：注意： 近邻一般采用近邻一般采用 为奇数，跟投票表决一样，避免因两为奇数，跟投票表决一样，避免因两种票数相等而难以决策。种票数相等而难以决策。 若若则则66【问题的提出】 上述讨论中可以看出，尽管近邻法有其优良品质，但是它的上述讨论中可以看出，尽管近邻法有其优良品质，但是它的一个严重弱点与问题是需要存储全部训练样本，以及繁重的距一个严重弱点与问题是需要存储全部训练样本，以及繁重的距离计算量。但以简单的方式降低样本数量，只能使其性能降低离计算量。但以简单的方式降低样本数量，只能使其性能降低

17、，这也是不希望的。为此要研究既能减少近邻法计算量与存储，这也是不希望的。为此要研究既能减少近邻法计算量与存储量，同时又不明显降低其性能的一些改进算法。量，同时又不明显降低其性能的一些改进算法。 改进算法大致基于两种原理改进算法大致基于两种原理。一种是对样本集进行组织与。一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免与训练样本集中每个样本进行距离计算。小范围内，避免与训练样本集中每个样本进行距离计算。 另一种原理则是在原有样本集中挑选出对分类计算有效的另一种原理则是在原有样本集中挑选出对分类计算有

18、效的样本，使样本总数合理地减少，以同时达到既减少计算量，又样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。减少存储量的双重效果。672.2.快速搜索近邻法快速搜索近邻法683. 3. 剪辑近邻法剪辑近邻法694. 4. 压缩近邻法压缩近邻法70哈尔滨工业大学哈尔滨工业大学711.1.引言引言2 2 主成分分析主成分分析(PCA)(PCA)3 3 基于基于K-LK-L展开式的特征提取展开式的特征提取4.4.应用举例应用举例722.2.主成分分析主成分分析73 根据方差最大化原理，用一组新的、线性无关且相互正交的向量来表征原来数据矩阵的行（或列）。这组新向量（主成分）是

19、原始数据向量的线性组合。 通过对原始数据的平移、尺度伸缩平移、尺度伸缩(减均值减均值除方差除方差)和坐标旋转坐标旋转(特征分解特征分解)，得到新的新的坐标系坐标系(特征向量特征向量)后，用原始数据在新坐标系下的投影投影(点积点积)来替代原始变量。 一一. . 主成分分析的基本原理主成分分析的基本原理74主成分分析的优点主成分分析的优点 它能找到表现原始数据阵最重要的变它能找到表现原始数据阵最重要的变量的组合量的组合 通过表示最大的方差，能有效地直观通过表示最大的方差，能有效地直观反映样本之间的关系反映样本之间的关系 能从最大的几个主成分的得分来近似能从最大的几个主成分的得分来近似反映原始的数据

20、阵的信息反映原始的数据阵的信息75图像预处理图像预处理 【人脸识别】76【人脸识别】77【人脸识别】78【人脸识别】79 基于基于PCA构建特征脸空间是对图像进行构建特征脸空间是对图像进行K-L变换，以去除变换，以去除样本间的相关性，然后根据特征值的大小选择特征向量。样本间的相关性，然后根据特征值的大小选择特征向量。 这种方法首先将人脸图像映射为高维空间的向量，然后应这种方法首先将人脸图像映射为高维空间的向量，然后应用基于统计的离散用基于统计的离散K-L变换方法，构造一个各分量互不相变换方法，构造一个各分量互不相关的特征空间，即特征脸空间，再将人脸图像在高维空间关的特征空间，即特征脸空间，再将

21、人脸图像在高维空间中的向量映射到特征脸空间，得到特征系数。中的向量映射到特征脸空间，得到特征系数。PCA构建特征脸空间构建特征脸空间哈尔滨工业大学哈尔滨工业大学1.1.基础知识基础知识2.2.前馈神经网络前馈神经网络3.3.反馈神经网络反馈神经网络4.4.自组织映射神经网络自组织映射神经网络神经网络的学习方法神经网络的学习方法u神经网络的学习：从环境中获取知识并改进自身性能，主要指调节网络参数使网络达到某种度量，又称为网络的训练。u学习方式：监督学习非监督学习再励学习u学习规则：误差纠正学习算法竞争学习算法4.自组织映射自组织映射自组织映射自组织映射Self-Organizing Map 亦称

22、亦称SOFM。 Kohonen 提出（提出（1980s）SOM SOM 用于非监督模式识别用于非监督模式识别自组织学习过程本身就是一个非监督学习过程SOMA(自组织分析)基本思路： 用未知样本集训练SOM; 计算象密度图; 根据象密度图划分聚类(把结点代表的小聚类合并)。特点： 对数据分布形状少依赖性；可反映真实存在的聚类数目，尤其适合人机合作分析(高维数据的有效二维显示)数学上待研究的问题多： 象密度与样本分布密度之间的关系？拓扑保持特性？如何在SOM 平面上聚类？哈尔滨工业大学哈尔滨工业大学1. 1. 引言引言2. 2. 单峰子集（类）的分离方法单峰子集（类）的分离方法3. 3. 类别分离

23、的间接方法类别分离的间接方法4. 4. 分级聚类方法分级聚类方法监督模式识别：（已知）样本集 训练（学习） 识别（分类）非监督模式识别：（未知）样本集 非监督学习（聚类分析） 后处理【引言】通过寻找可能存在的分类来理解某一对象将复杂多样的对象用有限典型来代表根据：某种假设（对聚类应具有的性质的认识）结果：聚类（clusters）属中间结果（数学结果），需经解释赋予物理含义（后处理）应用：复杂系统未知特性分析（举例）航天、航空、航海（具体阐述）直接方法:基于概率密度函数估计 相间接聚类方法:基于样本间似性度量【动态聚类】多次迭代，逐步调整类别划分，最终使某准则达到最优。三个要点： 选某种距离作为

24、样本相似性度量 定义某个准则函数，用于评价聚类质量。 初始分类方法及迭代算法l C- 均值聚类l ISODATA聚类常用算法：【动态聚类】C C 均值算法均值算法【动态聚类】C C 均值算法均值算法【动态聚类】C C 均值算法均值算法初始划分：一般可先选代表点，再进行初始分类。代表点选择方法：1. 经验选择2. 随机分成c 类，选各类重心作为代表点3. “密度”法。计算每个样本的一定球形邻域内的样本数作为“密度”，选“密度”最大的样本点作为第一个代表点，在离它一定距离选最大“密度”点作为第二个代表点，依次类推。4. 用前c 个样本点作为代表点。5. 用c 1聚类求c 个代表点：各类中心外加离它

25、们最远的样本点，从1 类开始。【动态聚类】C C 均值算法均值算法初始分类方法：1. 最近距离法。离哪个代表点近就归入哪一类。2. 最近距离法归类，但每次都重新计算该类代表点。3. 直接划分初始分类：每一个样本自成一类，第二个样本若离它小于某距离阈值则归入此类，否则建新类，4. 将特征归一化，用样本各特征之和作为初始分类依据。说明：初始划分无一定之规，多为启发式方法。C 均值方法结果受初值影响，是局部最优解。【动态聚类】C 均值聚类方法用于非监督模式识别的问题：l 要求类别数已知；l 是最小方差划分，并不一定能反映内在分布；l 与初始划分有关，不保证全局最优。C C 均值算法均值算法4. 分级

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

27、相似性度量）：样本之间的度量聚类之间的度量算法（从底向上）：（1）初始化，每个样本形成一类（2）把相似性最大（距离最小）的两类合并（3）重复（2），直到所有样本合并为两类。【分级聚类方法 】【分级聚类方法 】哈尔滨工业大学哈尔滨工业大学 1. 引言引言 2. 模糊集的基本知识模糊集的基本知识 3. 模糊特征和模糊分类模糊特征和模糊分类 4. 特征的模糊评价特征的模糊评价 5. 模糊聚类方法模糊聚类方法 6. 模糊模糊k 近邻分类器近邻分类器【模糊C 均值方法（FCM）】C C 均值算法均值算法【模糊C 均值】【模糊C 均值】【模糊C 均值】模糊模糊C 均值算法：均值算法：【改进的模糊C 均值算

28、法】模糊模糊C 均值算法的一个缺点：均值算法的一个缺点：【改进的模糊C 均值算法】【改进的模糊C 均值算法】特点特点AFC 有更好的鲁棒，且对给定的聚类数目不十分敏感。但有时可能会有更好的鲁棒，且对给定的聚类数目不十分敏感。但有时可能会出现一个类中只包含一个样本的情况，可通过在距离计算中引入非线出现一个类中只包含一个样本的情况，可通过在距离计算中引入非线性，使之不会小于革值来改进。性，使之不会小于革值来改进。 AFC、FCM 与与C 均值一样，依赖于初值。均值一样，依赖于初值。实验效果举例实验效果举例例一：类别重迭及类别不明显情况例一：类别重迭及类别不明显情况+：C 圴值圴值：FCMO：AFC

29、【改进的模糊C 均值算法】正确聚类(C=4)CM聚类(C=3)FCM聚类(C=3)AFC聚类(C=3)例二：给定类别数与实际类别数不一致的情况例二：给定类别数与实际类别数不一致的情况109 改进的模糊C均值算法 改进的模糊C均值算法较前面提到的模糊C均值算法具有更好的鲁棒性，它不但可以在有孤立样本存在的情况下得到较好的聚类效果，而且可以放松隶属度条件，而且因为放松了隶属度条件，使最终聚类结果对预先确定的聚类数目不十分敏感。 与确定性C均值算法和模糊C均值算法一样，改进的模糊C均值算法仍然对聚类中心的初值十分敏感，为了得到较好的结果，可以用确定性C均值算法或模糊C均值算法的结果作为初值。【改进的

30、模糊C 均值算法】哈尔滨工业大学哈尔滨工业大学1. 1. 统计学习理论统计学习理论2. 2. 支持向量机支持向量机3. 3. 核方法核方法2. 支持向量机支持向量机 根据统计学习理论，学习机器的实际风险由经验风险值和置根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部分组成。而基于经验风险最小化准则的学习方信范围值两部分组成。而基于经验风险最小化准则的学习方法只强调了训练样本的经验风险最小误差，没有最小化置信法只强调了训练样本的经验风险最小误差，没有最小化置信范围值，因此其推广能力较差。范围值，因此其推广能力较差。【基本概念】 Vapnik 与与1995年提出的支持向量机（年提出

31、的支持向量机（Support Vector Machine, SVM）以训练误差作为优化问题的约束条件，以）以训练误差作为优化问题的约束条件，以置信范围值最小化作为优化目标，即置信范围值最小化作为优化目标，即SVM是一种基于结构是一种基于结构风险最小化准则的学习方法，其推广能力明显优于一些传统风险最小化准则的学习方法，其推广能力明显优于一些传统的学习方法。的学习方法。【基本概念】 由于由于SVM 的求解最后转化成二次规划问题的求的求解最后转化成二次规划问题的求解，因此解，因此SVM 的解是全局唯一的最优解的解是全局唯一的最优解 SVM在解决在解决小样本、非线性及高维小样本、非线性及高维模式识别问题模式识别问题中表现出许多特有的优势，并能够推广应用到函中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中数拟合等其他机器学习问题中 Joachims 最近采用最近采用SVM在在Reuters-21578来进行来进行文本分类，并声称它比当前发表的其他方法都好文本分类，并声称它比当前发表的其他方法都好【基本概念】 由于由于SVM 的求解最后转化成二次规划问题的求解，因此的求解最后转化成二次规划问题的求解，因此SVM 的解是全局唯一的最优解的解是全局唯一的最优解 SVM在解决小样本、非线性及高维模式识别问题中表现在解决小样本、非线性及高维模式识别问题中表现出许多特有