第1章-模式识别课程绪论

第1章模式识别绪论•模式识别的定义Patternrecognitionisthestudyofhowmachinescanobservetheenvironment,learntodistinguishpatternsofinterestfromtheirbackground,andmakesoundandreasonabledecisionsaboutthecategoriesofthepatterns.——AnilK.Jain，MichiganStateUniversity~jain/Ref:AnilK.Jainetal.StatisticalPatternRecognition：AReview.IEEETrans.onpatternanalysisandmachineintelligence.2000,22(1):4-37什么是模式识别？•模式识别的目的：利用计算机对物理对象进行分类，在错误概率最小的条件下，使识别的结果尽量与客观物体相符合。•Y=F(X)–X的定义域取自特征集–Y的值域为类别的标号集–F是模式识别的判别方法什么是识别？•生产实践的需要：需要智能机器人，另外人的工资高，而计算机的价格越来便宜。•信息爆炸现象：处理人来不及处理的信息。如：卫星遥感，超级市场，邮政，银行，指纹库。•危险地带：油漆、放射、高温、核电站。•提高工效：自动化带来的好处已经显而易见。为什么要研究模式识别•与其他学科的联系与区别–人工智能:符号主义，连接主义，行为主义，机制主义（结构，功能，行为）–计算智能：神经网络，模糊逻辑，进化计算……–机器学习：分类，聚类，回归，有监督学习，无监督学习，半监督学习……–统计学–运筹学与其他学科的关系模式识别基本概念模式识别系统组成模式识别基本问题应用领域小结模式识别基本概念【基本概念】(1)模式识别(PatternRecognition)：确定一个样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。(2)样本（Sample)：一个具体的研究（客观）对象。如患者，某人写的一个汉字，一幅图片等。(3)模式(Pattern)：对客体（研究对象）特征的描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。它是一种具有时间或空间分布的信息。从工程角度讲是指客观事物存在形式的数学表达。【基本概念】(4)模式类（PatternClass）：把模式所属的类别或同一类别中模式的总体称为模式类（或简称为类）。(5)例子：以身高为例，模式：身高：167cm,180cm,156cm,176cm,…模式类：高个头、中等个头、矮个头；【基本概念】(6)说明：（1）模式所指的不是事物本身，而是我们从事物中获得的信息。（2）模式往往表现为具体的时间和空间分布的信息。（3）本课程讨论的是用计算机进行模式识别，信息进入计算机之前通常要经过取样和量化，在计算机中表现为具有时空分布的信息表现为向量或数组，数组中元素的序号可以对应时间和空间，也可对应其它标识，此处所说的时间和空间是更广义和抽象的理解。模式识别基本概念模式识别系统组成模式识别基本问题应用领域小结模式识别系统组成【模式识别系统组成】1.信息的获取：通过测量、采样、量化并用矩阵或向量表示。通常输入对象的信息有三个类型：二维图像（文字、指纹、地图、照片等）、一维波形（脑电图、心电图、机械震动波形等）、物理参量和逻辑值（体检中的温度、血化验结果等）2.预处理：去除噪声，加强有用的信息，并对输入测量仪器或其它因素造成的干扰进行处理。3.特征提取与选择：为了实现有效的识别分类，要对原始数据进行变换得到最能反映分类本质的特征，此过程为特征提取和选择。4.分类决策：在特征空间中用统计方法把被识别对象归为某一类。基本作法是在样本训练集基础上确定某个判决规则，使按这种判决规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。5.后处理：针对决策采取相应的行动。信息获取预处理特征提取与选择分类决策后处理模式识别系统组成框图【模式识别系统组成】数据采集特征提取二次特征提取与选择分类识别待识对象识别结果数据采集特征提取改进分类识别规则二次特征提取与选择训练样本改进采集提取方法改进特征提取与选择制定改进分类识别规则人工干预正确率测试【例1：车牌识别】车牌识别系统框图原始图像车牌定位字符识别倾斜校正字符分割系统流程图车牌定位车牌倾斜校正字符分割•传感器：–摄像头•预处理：–统一光照、统一焦距，去除背景，分割…•特征提取：–长度，亮度，重量，鳍的数目…•输入（测量）：–重量，长度，宽度，光泽度（亮还是暗）鳍数目•特征选择：哪个特征能最好的区分两种鱼？•设计分类器：线性？非线性？例2：鲈鱼和鲑鱼识别从长度很难区分Salmon：鲑鱼Seabass：鲈鱼特征选择：长度错误率仍然较高特征选择：亮度完美的分界特征选择：宽度+亮度线性分类器分类器设计非线性分类器分类器设计哪一个好？为什么？分类器设计•泛化能力/推广能力（Generalization）–设计分类器的中心目标是能够对新样本做出正确的反应，而不是对训练样本的完美分类。–分类模型对训练样本的过分匹配是一种应当努力避免的现象：过拟合（Overfitting）•避免过拟合的方法：避免过于复杂的决策面•复杂的决策面or简单的决策面？分类器的泛化能力模式识别的基本问题对象空间模式空间特征空间类型空间模式识别的任务模式采集：从客观世界（对象空间）到模式空间的过程称为模式采集。特征提取和特征选择：由模式空间到特征空间的变换和选择。类型判别：特征空间到类型空间所作的操作。模式识别三大任务【主要内容】(1)模式识别的训练方法(2)紧致性(3)特征选取(4)相似性度量与分类(5)性能评价(6)识别系统设计过程【模式识别的训练方法】学习的分类：学习的定义：广义地讲，任何设计分类器时所用的方法只要它利用了训练样本的信息就可以认为学习，学习的目的是指利用某种算法来降低由于训练样本的差异导致的分类误差。监督学习（supervisedlearning）：存在一个教师信号，对训练样本集的每个输入样本能提供类别标记和分类代价并寻找能够降低总体代价的方向。(人脸识别)。利用一组已知类别的样本调整分类器的参数，使其达到所要求性能的过程。对具有概念标记（分类）的训练样本进行学习，以尽可能对训练样本集外的数据进行标记（分类）预测。所有的标记（分类）是已知的。因此，训练样本的岐义性低。无监督学习（unsupervisedlearning）：没有显示的教师指导整个训练过程。（图像检索）。对没有概念标记（分类）的训练样本进行学习，以发现训练样本集中的结构性知识。所有的标记（分类）是未知的。因此，训练样本的岐义性高。聚类就是典型的无监督学习。半监督学习（Semi-supervisedLearning）：半监督学习是利用少部分标记数据集及未标记样本进行学习的主流技术。（如医学图像）。无监督学习只利用未标记的样本集，而监督学习则只利用标记的样本集进行学习。但在很多实际问题中，只有少量的带有标记的数据，因为对数据进行标记的代价有时很高。【监督学习与无监督学习】监督的学习方法的性能完全由训练样本的数量和质量决定，目标是通过已有的一部分输入数据与输出数据之间的对应关系，生成一个函数，建立问题域的预测模型，将输入映射到合适的输出。主要存在以下两点缺陷：(1)垃圾进、垃圾出。是指分类器的有效性完全依赖于训练样本的质量，当训练样本的质量不高时，很难得到好的分类效果。（2）过分适应训练样本（过拟合）。当训练样本的数量有限时，就会出现过分适应训练样本的现象，从而影响对新到数据的分类性能。简单解决的办法是增加训练样本的数量，但是给训练数据分类是一项极其耗费时间的工作，甚至有些情况下是不可能的。比如：对于有些问题，人们还不知道问题的正确答案，因此“增加训练样本的数量”看似简单，实际上并不简单。一句话：从它得到的训练集中进行“学习”，从而对未知数据进行分类。常用的算法包括：决策树分类法，朴素的贝叶斯分类算法(nativeBayesianclassifier)、基于支持向量机(SVM)的分类器，神经网络法，k-最近邻法(k-nearestneighbor，kNN)，模糊分类法等等。无监督的学习方法的目标是直接对输入数据集进行建模，通过数据分析以发现有趣的模式或结构。聚类方法是一种典型的无监督的学习方法。需要聚类的数据对象没有标记，需要由聚类算法自己确定。由于对数据对象不具备任何背景知识，聚类算法采用相同的原则对这些数据进行分析，聚类结果是否有效依赖于数据集对事先所制定的原则（假设）的符合程度。【半监督学习】Motivation：1、有标记样本难以获取。需要专门的人员,特别的设备,额外的开销等等。2、无标记的样本相对而言是很廉价，容易获取的。两个例子：（1）在计算机辅助医学图像分析中,可以从医院获得大量的医学图像作为训练例,但如果要求医学专家把这些图像中的病灶都标识出来,则往往是不现实的。（2）在进行Web网页推荐时,需要用户标记出哪些网页是他感兴趣的,很少会有用户愿意花大量的时间来提供标记,因此有标记的网页示例比较少,Web上存在着无数的网页,它们都可作为未标记示例来使用。显然,如果只使用少量的有标记示例,那么利用它们所训练出的学习系统往往很难具有强泛化能力;另一方面,如果仅使用少量“昂贵的”有标记示例而不利用大量“廉价的”未标记示例,则是对数据资源的极大的浪费。目前,利用未标记示例的主流学习技术主要有三大类：半监督学习(semi-supervisedlearning)、直推学习(transductivelearning)和主动学习(activelearning)。这三类技术都是试图利用大量的未标记示例来辅助对少量有标记示例的学习,但它们的基本思想却有显著的不同。在半监督学习中,学习器试图自行利用未标记示例,即整个学习过程不需人工干预,仅基于学习器自身对未标记示例进行利用。直推学习与半监督学习的相似之处是它也是由学习器自行利用未标记示例,但不同的是,直推学习假定未标记示例就是测试例,即学习的目的就是在这些未标记示例上取得最佳泛化能力。换句话说,半监督学习考虑的是一个“开放世界”,即在进行学习时并不知道要预测的示例是什么,而直推学习考虑的则是一个“封闭世界”,在学习时已经知道了需要预测哪些示例。总结：半监督学习是归纳式的,生成的模型可用做更广泛的样本;而直推式学习仅仅为了当前无标记样本的分类。前者使用无标记样本,为了以后其他样本更好的分类。后者只是为了分类好这些有限的无标记样本。主动学习算法可以主动地提出一些标注请求，将一些经过筛选的数据提交给专家进行标注。【主要内容】(1)模式识别的训练方法(2)紧致性(3)特征选取(4)相似性度量与分类(5)性能评价(6)识别系统设计过程【紧致性】紧致集：同一类模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集。临界点(样本)：在多类样本中，某些样本的值有微小变化时就变成另一类样本称为临界样本（点）。紧致性的概念：为了能在某个空间中进行分类，通常假设同一类的各个模式在该空间中组成一个紧致集。从这个紧致集中的任何一点可以均匀过渡到同一集中的另外一点，且在过渡途中的所有各个点都仍然属于这个紧致集（即属于同一模式类）。此外，当紧致集中各个点在任意方向有某些不大的移动时它仍然属于这个集合。第1种情况：A1:111,101,110,011A2：000，010，100，001只要用一个平面就可以将两个点集分开。【举例】011111001101100110010x1x3x2000第2种情况：A1:111A2：000任何一个通过点000与111连线的平面都能达到分类的目的。【举例】x2011111001101100110010x1x3000第3种情况：A1:111,001,100,010A2：000，011，101，110需要用3个平面才能分开。【举例】0