第1章 模式识别课程绪论ppt课件.ppt

,第1章 模式识别绪论,模式识别的定义Pattern recognition is the study of how machines can observe the environment, learn to distinguish patterns of interest from their background, and make sound and reasonable decisions about the categories of the patterns. Anil K. Jain，Michigan State University http:/www.cse.msu.edu/jain/Ref: Anil K. Jain et al. Statistical Pattern Recognition：A Review. IEEE Trans. on pattern analysis and machine intelligence. 2000, 22(1):4-37,什么是模式识别？,模式识别的目的：利用计算机对物理对象进行分类，在错误概率最小的条件下，使识别的结果尽量与客观物体相符合。Y = F(X) X的定义域取自特征集 Y的值域为类别的标号集 F是模式识别的判别方法,什么是识别？,生产实践的需要：需要智能机器人，另外人的工资高，而计算机的价格越来便宜。信息爆炸现象：处理人来不及处理的信息。如：卫星遥感，超级市场，邮政，银行，指纹库。危险地带：油漆、放射、高温、核电站。提高工效：自动化带来的好处已经显而易见。,为什么要研究模式识别,与其他学科的联系与区别人工智能: 符号主义，连接主义，行为主义，机制主义（结构，功能，行为）计算智能：神经网络，模糊逻辑，进化计算机器学习：分类，聚类，回归，有监督学习，无监督学习，半监督学习统计学运筹学,与其他学科的关系,主要内容,模式识别基本概念模式识别系统组成模式识别基本问题应用领域小结,模式识别基本概念,【基本概念】,【基本概念】,【基本概念】,主要内容,模式识别基本概念模式识别系统组成模式识别基本问题应用领域小结,模式识别系统组成,【模式识别系统组成】,1. 信息的获取：通过测量、采样、量化并用矩阵或向量表示。通常输入对象的信息有三个类型：二维图像（文字、指纹、地图、照片等）、一维波形（脑电图、心电图、机械震动波形等）、物理参量和逻辑值（体检中的温度、血化验结果等）,2. 预处理：去除噪声，加强有用的信息，并对输入测量仪器或其它因素造成的干扰进行处理。,3. 特征提取与选择：为了实现有效的识别分类，要对原始数据进行变换得到最能反映分类本质的特征，此过程为特征提取和选择。,4. 分类决策：在特征空间中用统计方法把被识别对象归为某一类。基本作法是在样本训练集基础上确定某个判决规则，使按这种判决规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。,5.后处理：针对决策采取相应的行动。,【模式识别系统组成】,【例1：车牌识别】,车牌识别系统框图,车牌定位,车牌倾斜校正,字符分割,传感器：摄像头预处理：统一光照、统一焦距，去除背景，分割特征提取：长度，亮度，重量，鳍的数目输入（测量）：重量，长度，宽度，光泽度（亮还是暗）鳍数目特征选择：哪个特征能最好的区分两种鱼？设计分类器：线性？非线性？,例2：鲈鱼和鲑鱼识别,从长度很难区分Salmon：鲑鱼 Sea bass：鲈鱼,特征选择：长度,错误率仍然较高,特征选择：亮度,完美的分界,特征选择：宽度+亮度,线性分类器,分类器设计,非线性分类器,分类器设计,哪一个好？为什么？,分类器设计,泛化能力/推广能力（Generalization）设计分类器的中心目标是能够对新样本做出正确的反应，而不是对训练样本的完美分类。分类模型对训练样本的过分匹配是一种应当努力避免的现象：过拟合（Overfitting）避免过拟合的方法：避免过于复杂的决策面复杂的决策面 or 简单的决策面？,分类器的泛化能力,模式识别的基本问题,模式识别的任务,模式采集：从客观世界（对象空间）到模式空间的过程称为模式采集。,特征提取和特征选择：由模式空间到特征空间的变换和选择。,类型判别：特征空间到类型空间所作的操作。,模式识别三大任务,【主要内容】,【模式识别的训练方法】,监督学习（supervised learning ）：存在一个教师信号，对训练样本集的每个输入样本能提供类别标记和分类代价并寻找能够降低总体代价的方向。(人脸识别)。利用一组已知类别的样本调整分类器的参数，使其达到所要求性能的过程。对具有概念标记（分类）的训练样本进行学习，以尽可能对训练样本集外的数据进行标记（分类）预测。所有的标记（分类）是已知的。因此，训练样本的岐义性低。,无监督学习（unsupervised learning ）：没有显示的教师指导整个训练过程。（图像检索）。对没有概念标记（分类）的训练样本进行学习，以发现训练样本集中的结构性知识。所有的标记（分类）是未知的。因此，训练样本的岐义性高。聚类就是典型的无监督学习。,半监督学习（Semi-supervised Learning ）：半监督学习是利用少部分标记数据集及未标记样本进行学习的主流技术。（如医学图像）。无监督学习只利用未标记的样本集，而监督学习则只利用标记的样本集进行学习。但在很多实际问题中，只有少量的带有标记的数据，因为对数据进行标记的代价有时很高。,【监督学习与无监督学习】,监督的学习方法的性能完全由训练样本的数量和质量决定，目标是通过已有的一部分输入数据与输出数据之间的对应关系，生成一个函数，建立问题域的预测模型，将输入映射到合适的输出。主要存在以下两点缺陷： (1)垃圾进、垃圾出。是指分类器的有效性完全依赖于训练样本的质量，当训练样本的质量不高时，很难得到好的分类效果。（2）过分适应训练样本（过拟合）。当训练样本的数量有限时，就会出现过分适应训练样本的现象，从而影响对新到数据的分类性能。简单解决的办法是增加训练样本的数量，但是给训练数据分类是一项极其耗费时间的工作，甚至有些情况下是不可能的。比如：对于有些问题，人们还不知道问题的正确答案，因此“增加训练样本的数量”看似简单，实际上并不简单。一句话：从它得到的训练集中进行“学习”，从而对未知数据进行分类。常用的算法包括：决策树分类法，朴素的贝叶斯分类算法(native Bayesian classifier)、基于支持向量机(SVM)的分类器，神经网络法，k-最近邻法(k-nearest neighbor，kNN)，模糊分类法等等。,无监督的学习方法的目标是直接对输入数据集进行建模，通过数据分析以发现有趣的模式或结构。聚类方法是一种典型的无监督的学习方法。需要聚类的数据对象没有标记，需要由聚类算法自己确定。由于对数据对象不具备任何背景知识，聚类算法采用相同的原则对这些数据进行分析，聚类结果是否有效依赖于数据集对事先所制定的原则（假设）的符合程度。,【半监督学习】,Motivation：1、有标记样本难以获取。需要专门的人员,特别的设备,额外的开销等等。2、无标记的样本相对而言是很廉价，容易获取的。两个例子：（1）在计算机辅助医学图像分析中,可以从医院获得大量的医学图像作为训练例,但如果要求医学专家把这些图像中的病灶都标识出来,则往往是不现实的。（2）在进行 Web 网页推荐时,需要用户标记出哪些网页是他感兴趣的,很少会有用户愿意花大量的时间来提供标记,因此有标记的网页示例比较少, Web上存在着无数的网页,它们都可作为未标记示例来使用。显然,如果只使用少量的有标记示例,那么利用它们所训练出的学习系统往往很难具有强泛化能力;另一方面,如果仅使用少量“昂贵的”有标记示例而不利用大量“廉价的”未标记示例,则是对数据资源的极大的浪费。,目前,利用未标记示例的主流学习技术主要有三大类：半监督学习(semi-supervisedlearning)、直推学习(transductive learning)和主动学习(active learning)。这三类技术都是试图利用大量的未标记示例来辅助对少量有标记示例的学习,但它们的基本思想却有显著的不同。在半监督学习中,学习器试图自行利用未标记示例,即整个学习过程不需人工干预,仅基于学习器自身对未标记示例进行利用。直推学习与半监督学习的相似之处是它也是由学习器自行利用未标记示例,但不同的是,直推学习假定未标记示例就是测试例,即学习的目的就是在这些未标记示例上取得最佳泛化能力。换句话说,半监督学习考虑的是一个“开放世界”,即在进行学习时并不知道要预测的示例是什么,而直推学习考虑的则是一个“封闭世界”,在学习时已经知道了需要预测哪些示例。总结：半监督学习是归纳式的,生成的模型可用做更广泛的样本;而直推式学习仅仅为了当前无标记样本的分类。前者使用无标记样本,为了以后其他样本更好的分类。后者只是为了分类好这些有限的无标记样本。主动学习算法可以主动地提出一些标注请求，将一些经过筛选的数据提交给专家进行标注。,【主要内容】,【紧致性】,第1种情况：A1: 111,101,110,011A2：000，010，100，001只要用一个平面就可以将两个点集分开。,【举例】,第2种情况：A1: 111A2：000任何一个通过点000与111连线的平面都能达到分类的目的。,【举例】,第3种情况：A1: 111,001,100,010A2：000，011，101，110需要用3个平面才能分开。,【举例】,对于这种情况，结合A1中任意一点的一个码的数值发生变化，例如111变为101，那么就成为A2中的成员。把这些点成为临界点。 把改变其中一个码值不能改变其集合属性的点成为内点。在该情况下，集合A1和集合A2没有内点，全部为临界点。一般情况，两个集合中具有的临界点越多，就越难分开。例如，A1=000;A2=111，没有临界点，全部为内点，因此较为容易将其分开,一般来说，在D维空间中要用超表面进行分类，假若我们用平面图表示D维空间中点的分布。如下图。,【紧致性】,【主要内容】,【特征选取】,Salmon(鲑鱼) 与Sea bass (鲈鱼)分类系统,【特征选取】,光泽度长度宽度,长度特征直方图,光泽度直方图,宽度（纵轴）-光泽度（横轴）,不成功,不成功,成功,【特征选取】,【特征选取】,1.底层特征： （1）数值尺度（numerical size）：有明确的数量和数值。 （2）非数值尺度（non-numerical size) 有序尺度：有先后、好坏的次序关系，如酒 分为上，中，下三个等级。 名义尺度(nominal)：无数量、无次序关系， 如颜色：红、 黄、蓝、黑 2. 中层特征：经过计算，变换得到的特征 3. 高层特征：在中层特征的基础上有目的的经过运 算形成,【特征选取】,车身,车轮,车型,颜色,底层,中层,汽车,高层,品牌,【主要内容】,【相似性度量与分类】,【相似性度量与分类】,距离值越小，相似性越高,【相似性度量与分类】,2. 用各种距离度量相似性： 已知两个样本： Xi=(xi1, xi2 , xi3,xin)T Xj=(xj1, xj2 , xj3,xjn)T, 绝对值距离(街坊距离或Manhattan距离）：,【相似性度量与分类】, 欧几里德(Euclidean)距离明考夫斯基(Minkowski)距离 其中当q=1时为绝对值距离，当q=2时为欧氏距离,其中Xi ，Xj为特征向量， 为协方差矩阵。使用于N个样本的集合中两个样本之间求M氏距离：, 切比雪夫(Chebyshev)距离：,是q趋向无穷大时明氏距离的极限情况, 马哈拉诺比斯（Mahalanobis)距离,N样本个数,例：马哈拉诺比斯（Mahalanobis)距离：,设X1=（0,0)T, X2=（0,1) T, X3=（1,0) T, X4=（1,1) T.则N=4，,两点之间的马氏距离,两点之间的欧氏距离,都具对称性。但数值不同。马氏距离的计算步骤：1.求样本均值；2.求协方差矩阵；3.求协方差矩阵的逆矩阵？；4.按公式求两点间马氏距离。5.优点：量纲无关，排除变量之间的相关性的干扰。,马氏距离的优点,1、用逆矩阵的原因是相当于除去scale对距离的影响。如一维的情况下，同样距离都是3，但对于方差大的数据，这个距离就算小了，所以要用距离再除以方差。高维情况就是协方差阵的逆。2、如：均值分别为a和b两个正态分布的总体，方差不一样，则图中的A点离哪个总体近呢？显然，A离左边的更近，属于左边总体的概率更大，尽管A与a的欧式距离远一些。,【马氏距离的优点】,即样本间夹角小的具有相似性强。例： X1 , X2 , X3的夹角如图：因为X1 , X2 的夹角小，所以X1 , X2 最相似。, 夹角余弦,如：1，3，5，7，9与2，4，6，8，10的相关系数为1； 1，3，5，7，9与10，8，6，4，2的相关系数为-1；注意：在求相关系数之前，要将数标准化,*相关系数,分别为Xi ,Xj的均值:,其中，Xi=(xi1,xi2,xin), Xj=(xj1,xj2,xjn).,相关系数的绝对值越大，则表明两向量相关度越高,【相似性度量与分类】,【主要内容】,【性能评价】,【主要内容】,【识别系统设计过程】,选择模型：用数学形式表达的不同特征的描述。,训练分类器：利用样本数据确定分类器的过程。,评价分类器：避免过拟合。,总结：几个重要问题,特征提取噪声过拟合模型选择先验知识特征缺失部分与整体,分割上下文不变性分类器集成代价与风险计算复杂性,特征提取,Feature Extraction：Which features are most promising problem and domain dependent,噪声,Noise：any property of the sensed pattern due not to the true underlying model but instead to randomness in the world or the sensors.噪声的影响：降低特征值测量的可靠性,过拟合,Overtting ：While an overly complex model may allow perfect classification of the training samples, it is unlikely to give good classification of novel patterns,Are there principled methods for finding the best complexity for a classier?,模型选择,Model Selection：How do we know when to reject a class of models and try another one ?,Linear,Non-linear,先验知识,Prior Knowledge：When there is not sufficient training data, incorporate prior knowledge,特征缺失,Missing Features:How should the classifier make the best decision with missing features?How to train the classifier with missing features ?,部分与整体,Mereology：the problem of subsets and supersets, the study of part / whole relationships.It is related to prior knowledge and segmentation,分割,Segmentation：How do we “group” together the proper number of elements？,上下文,Context：input-dependent information other than from the target pattern itselfThe same pattern within different context might have different meanings,不变性,Invariance：translation invariance, rotational invariance , scale invariance,分类器集成,Evidence Pooling: Classifier Ensemble. Performance can be improved using multiple classifiers,代价与风险,Costs and Risks：Each classification is associated with a cost or risk Can we estimate the lowest possible risk of any classifier?,计算复杂性,Computational Complexity：impractical time or memory requirements？How does an algorithm scale with the number of feature dimensions number of patterns number of categories What is the trade off between computational complexity and performance?,主要内容,模式识别基本概念模式识别系统组成模式识别基本问题应用领域小结,应用领域,【应用领域】,工业机器人,电路板检测,农业采摘机器人,人脸识别,虹膜识别,手掌静脉识别,指纹识别,无人驾驶,车牌识别,交通流量分析,计算机辅助诊断系统,医学图像决策系统,导弹图像末制导,无人侦察机,全天候雷达监控系统,遥感地貌分析,主要内容,模式识别基本概念模式识别系统组成模式识别基本问题应用领域小结,本章小结,【小结】,【4.发展历程】,21世纪以来：蓬勃发展时期 统计学习理论越来越多地用于解决具体的模式识别和模型选择问题 新的概率密度估计、特征选择、特征变换、聚类算法不断提出 模式识别领域和机器学习领域的互相渗透 模式识别系统大规模用于实际问题,Ref： 刘成林, 谈铁牛. 模式识别研究进展. 中科院自动化所,模式识别重点实验室,【4.发展历程】,【5.重要期刊论文和数据】,主要会议,ICPR (International Conference on Pattern Recognition)：2年一次，1000人规模ICDAR (International Conference on Document Analysis and Recognition)： 2年一次，300-400人规模FG (IEEE Intl Conference on Automatic Face and Gesture Recognition),ICASSP (IEEE International Conference on Acoustics, Speech and Signal Processing), ICIP (International Conference on Image Processing)ICML (International Conference on Machine Learning),计算机视觉三大国际会议 ICCV (International Conference on Computer Vision)： 2年一次，1000人规模 CVPR (International Conference on Computer Vision and Pattern Recognition)：每年一次在美国，1000人规模 ECCV (European Conference on Computer Vision)：2年一次,主要组织,国际组织IAPR (International Association for Pattern Recognition, 模式识别国际协会)IEEE Computer Society: TC (Technical Committee ) on PAMI (Pattern Analysis and Machine Intelligence)国内组织中国自动化学会：模式识别与机器智能(PRMI)专业委员会，1981年成立，IAPR (International Association of Pattern Recognition) 成员组织中国计算机学会：人工智能与模式识别专业委员会中国人工智能学会,USA: MIT ( Tomaso Poggio, Brain and Cognitive Sciences and at the Artificial Intelligence Laboratory. ) http:/mcgovern.mit.edu/principal-investigators/tomaso-poggio UIUC (Thomas Huang, University of Illinois Urbana Champaign伊利诺伊大学厄本那香槟分校, Robotics, vision, artificial intelligence ) http:/www.ece.illinois.edu/directory/profile.asp?t-huang1CMU ( Carnegie Mellon University卡内基梅隆大学, computer vision, human-computer interaction, mobile robots ) http:/www.cmu.eduMSU (A. K. Jain, Michigan State University密西根州立大学 , pattern recognition, computer vision and biometric recognition ) http:/www.cse.msu.edu/jain/,Canada: Toronto University 多伦多 (G. E. Hinton, Neural Network, Machine Learning. Boltzmann Machines, Distributed Representations, Time-delay Neural Nets, Deep Belief Nets, Multi-layer Neural networks. ) http:/www.cs.toronto.edu/hinton/Concordia University 肯考迪娅 ( C. Y. Suen, Centre for Pattern Recognition and Machine Intelligence. Document Analysis, Word Recognition, Language Identification ) http:/www.cenparmi.concordia.ca/CENPARMI/Suen/index.html,UK: MSR Cambridge (Christopher M. Bishop. Microsoft Research Cambridge，Machine Learning and its Applications ) http:/ University 萨里大学(Josef Kittler, Pattern Recognition, Image Analysis and Computer Vision, Vision Speech and Signal Processing ) http:/personal.ee.surrey.ac.uk/Personal/J.Kittler/cv.htmlFrance: INRIA (Institut National de Recherche en Informatique et en Automatique, the french national institute for research in computer science and control) http:/en.inria.fr/,中国：中科院自动化所（谭铁牛，模式识别国家重点实验室，模式识别基础理论、图像处理与计算机视觉以及语音语言信息处理） http:/ (Microsoft Research Asia，多媒体、自然语言，人机交互，语音识别) http:/ 清华大学（张钹 ，智能技术与系统国家重点实验室， 智能信号处理、智能图形图像处理、人机交互与媒体集成 ） http:/ ） http:/ ，多传感信息融合及智能检测与控制系统，网络环境下的媒体计算与可视化技术 ） http:/ http:/,【6.参考书目】,