模式识别导论

第1章引论1.1模式识别及模式识别系统1.2模式识别的基本方法1.3模式识别的一些基本准则1.4模式识别的应用

在日常生活中，我们能够轻而易举地识别出苹果和香蕉；能认出对面的人是张三还是李四；能从口袋里摸出钥匙；闻到气味，能区分出是汽油还是油漆；听到声音，能辨识出是猫叫还是狗吠等。实际上，这些行为都是人类在进行模式识别。为了具备这种能力，在过去的几千万年里，人类进化出了高度复杂的神经和认知系统。然而，人们对于自己所具有的模式识别能力见惯不惊，没有注意到模式识别是一个值得研究的问题。伴随着20世纪40年代计算机的出现和50年代人工智能的兴起，人们开始尝试使用计算机来代替或扩展人类的部分脑力劳动。随后，(计算机)模式识别得到迅速发展，并在20世纪60年代初迅速发展成为一门新的学科领域。至今，它所研究的理论和方法在很多领域得到了广泛的应用，涉及生活中的方方面面。本章首先讨论模式识别的基本概念和模式识别系统的构成，然后介绍模式识别的基本方法，接着讨论模式识别中的主要问题，最后探讨模式识别的应用。

1.1模式识别及模式识别系统

1.1.1模式识别的基本概念

“模式”一词的英文“Pattern”源于法文“Patron”，本来是指可作为大家典范的理想的人，或用以模仿复制的完美的样品。模式识别是包括人类在内的生物体的一项基本智能。对于模式和模式识别，有“广义”和“狭义”两种解释。广义地说，存在于时间和空间中可观察的事物，如果可以区别它们是否相同或相似，都可以称之为模式。此时，模式识别是生物体(包括人)的基本活动，与感觉、记忆、学习、思维等心理过程紧密联系，是透视人类心理活动的重要窗口之一。从这个角度讲，模式识别是研究生物体如何感知对象的学科，属于认识科学的范畴，是生理学家、心理学家、生物学家和神经生理学家的研究内容，常被称做认知模式识别。具体来说，它是指人们把接收到的有关客观事物或人的刺激信息与他在大脑里已有的知识结构中有关单元的信息进行比较和匹配，从而辨认和确定该刺激信息意义的过程。正是通过认知模式识别，我们才能认识世界，才能辨别出各个物体之间的差别，才能更好地学习和生活。

狭义地说，模式是为了能让计算机执行和完成分类识别任务，通过对具体的个别事物进行观测所得到的具有时间和空间分布的信息。把模式所属的类别或同一类中模式的总体称为模式类(或简称为类)。计算机模式识别就是指根据待识别对象的特征或属性，利用以计算机为中心的机器系统，运用一定的分析算法确定对象的类别的学科，是数学家、信息学专家和计算机专家的研究内容。

因此，模式识别的研究主要集中在认知模式识别和计算机模式识别这两个方面。下面分别对这两方面内容进行详细介绍。1.1.2认知模式识别

认知模式识别是认知心理学研究领域中的核心问题之一，是人的一种基本的认知能力或智能，在人的各种活动中都有重要的作用。模式识别可看做一个典型的知觉过程，它依赖于人已有的知识和经验。模式识别过程主要经历分析、比较和决策三个阶段。一般说来，模式识别过程是将感觉信息与长时记忆中的有关信息进行比较，再决定它与哪个长时记忆中的项目有着最佳匹配的过程。

在认知心理学中，匹配过程可以采用模板匹配理论、原型匹配理论、特征匹配理论和结构优势描述理论来实现。

1.模板匹配理论

模板匹配理论是模式识别的最简单的一种理论假设，最早是针对计算机的模式识别而提出来的，后来被用来解释人类的模式识别过程。它的核心思想是，人的长时记忆中的编码信息存储着各式各样的来自个体过去经历的各种外部模式的拷贝或复本，即模板，它们与外部的刺激模式存在着一一对应的关系。当一个刺激作用于人的感觉器官时，刺激信息得到编码并与头脑中所存储的模板进行比较和匹配，然后确定哪一个模板与刺激信息最为吻合，就把该刺激信息确认为是与头脑中的某个模板相同，即产生模式识别效应，反之则不能被辨别与认识。可见，模式识别是刺激信息与脑中某个或某些模板产生最佳匹配的过程。

该理论的基本观点是刺激信息与脑中模板的最佳匹配，而且这种匹配要求两者具有最大相似的重叠。该理论假设个体在长时记忆中存储有大量的，甚至是无穷的相应的特定模板，否则就不能得到模式识别或发生错误的模式识别。如果要得到正确的模式识别，就需要在人的长时记忆中存储不计其数的模板，但这就会极大地增加人的记忆负担，这与人在模式识别过程中所表现出来的高度灵活性是不一致的。有两种改进方法可以弥补该理论的不足：一是假设每一个模式要由几个模板来表征，这样模式识别就有了更大的灵活性，但是，这样就与模板匹配的理论假设相异了。二是假设刺激信息在与模板匹配之前，刺激信息需要先进行标准化过程，通过改变刺激信息的某些原始特征，使它与长时记忆中模板的标准大小和标准方位等相似，以此来达到模式识别的目的。模板匹配理论虽然得到来自实验与应用两个方面的支持，但是不容回避的是，它仍然存在着明显的不足与局限。首先，人的长时记忆需要存储无数个模板，这既会给记忆带来沉重的负担，也会使人在识别事物时缺少灵活性。其次，无法解释人为何有时能够非常迅速地识别一个新的、不熟悉的事物的这种常见情况。第三，没有说明模板匹配的信息编码形式，即外部刺激模式与脑中模板的比较是平行加工还是系列加工的；是从事物的局部特征开始的，还是从事物的整体特征开始的。这些问题都与知觉活动过程和知识表征有关。

2.原型匹配理论

原型匹配理论是针对模板匹配理论的不足而提出的模式识别理论假说。原型匹配理论认为，在人的长时记忆中存储着的不是与外部事物模式一一对应的模板，而是事物的某种“原型”。原型是指一类客观事物的抽象物，是一类客观事物所共有的关键性特征。由于原型是一种概括化了的内部表征，因此它们并不要求与外部刺激信息严格匹配，只需近似匹配即可。一旦外部刺激信息与人脑中的某个原型有最近似的匹配，就可以把它纳入这一原型所概括的范畴内得到识别。如果几个外部刺激信息同属于一个类别或范畴，即使它们之间可能在形状、大小、高低等方面存在着差异，也可以通过与人脑中原型的匹配得到准确识别。这样，不仅能够大大减轻记忆负担，也能够使人的模式识别活动更加灵活，从而能够更好地适应错综复杂的环境变化与外部的刺激信息。

M.I.Posner和J.D.Keele用实验支持了模式识别的原型匹配理论。这些实验结果证实了人脑中原型的存在以及原型在模式识别中的重要作用。在类似研究的基础上，S.K.Reed提出了一个原型匹配的模式识别模型，原型匹配模型在一定程度上还能够容纳模板匹配理论。因此，原型匹配模型显得比较灵活、富有弹性。但是，不足的是，原型匹配模型只具有自下而上的加工过程，而没有自上而下的加工过程。其实，在人的知觉过程中，自上而下的加工过程有时更加重要。

3.特征匹配理论

模式或事物是由若干个元素或特征按照一定的关系组合在一起构成的。因此，要识别事物或模式，就可以分析它们的基本特征。任何模式都可以被分解为诸多特征或属性，模式识别就是通过对刺激信息特征进行分析，然后与其存储在长时记忆中的模式相比较后，决定与哪个模式进行匹配的过程。

特征匹配理论提出，各种模式在长时记忆系统中的编码，既不是具体事物的模板，也不是某类事物的原型，而是该模式所具有的基本特征和基本属性的存储。模式识别的特征匹配理论及其模型，目前备受认知心理学的重视，它也在计算机的模式识别中得到了应用。与其他模式识别模型相比，它能更加灵活有效地解释人的模式识别过程。特征匹配理论仅对刺激信息的部分特征识别过程作出解释，即它只关心自下而上的加工部分，却忽略了基于背景信息和主观期待的自上而下的加工过程。

4.结构优势描述理论

在对刺激信息的知觉过程中，人的经验起着很重要的作用。由于刺激模式不是孤立地出现的，它们总是处于与其他模式或其他模式属性的联系中,为此在模式识别过程中，这种自上而下的加工作用随着模式识别研究的深入而日益受到重视。

1996年，Bruce等人提出了结构优势描述理论。结构描述理论认为，结构是由“一些描述特定构成的命题组成的，这些命题是象征性的，虽然用词汇来描述它们，但是它却不是语言的”。为此，Marr和Biederrman提出了很有影响的计算理论，即“马尔计算理论”。结构描述的优点是它关注刺激信息中的最重要的部分。但是，这个模式识别理论忽视了情境信息对知觉过程的重要影响。同时，在对模式识别时的精细区分与辨别方面，认知心理学家们仍然存在着不同的看法。1.1.3计算机模式识别

早期的计算机模式识别将研究重点放在模型的建立上。20世纪50年代末，F.Rosenblatt提出了一种简化的模拟人脑进行识别的数学模型——感知机，初步实现了通过给定类别的各个样本对识别系统进行训练，使系统在学习完毕后具有对其他未知类别的模式进行正确分类的能力。20世纪60年代,用统计决策理论求解模式识别问题的研究得到了迅速的发展。20世纪70年代前后出版了一系列反映统计模式识别理论和方法的专著。1962年，R.Narasimahan提出了一种基于基元关系的句法识别方法，美籍华人傅京孙在这个领域进行了卓有成效的工作，形成了句法模式识别的系统理论。20世纪80年代，J.J.Hopfield深刻揭示了人工神经元网络所具有的联想存储和计算能力，为模式识别技术提出了一种新的途径，短短几年在很多方面取得了显著成果，从而形成了模式识别的人工神经元网络方法。

一个功能完善的计算机模式识别系统除了具有分类识别过程外，通常还应该具有学习过程。图1.1给出了一个模式识别系统的原理框图，虚线的上部是分类识别过程，虚线的下部是学习过程。学习阶段是对样本进行特征选择，寻找分类的规律；实现(分类识别)阶段则是根据分类规律对未知样本集进行分类和识别。数据的采集及预处理、特征提取和选择、学习和训练、分类识别是任何模式识别系统中都具有的主要环节。

图1.1模式识别系统的原理框图

1.数据采集及预处理

数据采集及预处理是指通过各种传感器把被研究对象的各种物理变量转换为计算机可以接受的数值或符号(串)集合。习惯上，称这种数值或符号(串)所组成的空间为模式空间。

2.特征提取和选择

在进行分类识别和训练学习之前，首先需要对待识别对象的本质特征和重要属性进行测量，从而获得描述对象的模式，这个过程称为特征提取。然而，能描述对象的特征或属性的种类有很多。实际上，对于某些分类算法来说，并不是特征越多越有益于分类，过多的特征会降低算法运行的可行性。同时，为了节省计算机存储空间、算法运行时间和特征提取的费用，在满足一定的分类识别正确率的前提下，也需要按照某种准则选用对分类识别作用较大的特征来完成分类识别任务，这个过程就称为特征选择。需要指出的是，特征提取和选择依赖于具体问题和具体领域，需要在相应领域知识的指导下完成。

3.学习和训练

在日常生活和工作中，人们越来越依赖计算机，几乎认为计算机无所不能，甚至把计算机称为电脑。但与人脑相比，电脑是小巫见大巫，这不仅仅在于人脑约有1011～1012个神经元，更在于每个神经元约有103～104个突触，即一个神经元可以通过突触与8000个其他神经元交换信息，当生物电流通过某一突触时，神经元就将信息传递给下一个神经元。所以，人脑有极其丰富的联想、判别与推理能力。计算机的联想、判别等能力与人脑相差甚远，特别是在对外界信息的感知能力方面更远不如人脑。为了使计算机如同人一样具有分类识别能力，需要对机器进行训练。首先将人类的识别知识和方法以及分类识别对象的信息输入到计算机中，产生分类识别的规则和程序，这个过程就是机器学习的过程。该过程要反复进行多次，不断地修正和改进，最后使系统的正确识别率达到规定要求。目前，机器学习通常需要人为干预。

4.分类识别

学习训练结束之后，产生的分类识别规则和程序用来对未知类别对象进行分类识别。很明显，输入机器的人类识别知识和有关分类识别对象的信息越充分，机器中的知识与待识别对象越匹配，知识的运用就越合理，系统的识别能力就越强，获得的识别率就越高。

针对不同的应用目的，上述四部分的内容可以有很大的差别，特别是在数据处理和识别部分，为了提高识别结果的可靠性，往往需要加入规则以对可能产生的错误进行修正，或通过引入限制条件大大缩小待识别模式在模型库中的搜索空间，以减少匹配计算量。在一个模式识别系统的学习阶段，需要在一个样本集上进行学习或训练。此训练集是非常关键的，训练的数据量要足够大而且要足够典型，这样才能保证算法的可靠性。训练集的选取和应用需注意以下几点：训练样本的个数应该10倍于特性数据维数；相对于训练样本，分类器的未知参数不能过多；分类器不能出现过度训练的问题。

1961年，Bellman首先提出维数灾难问题，他指出，估计一个变量函数所需要的样本采样点数会随着变量个数的增加呈指数增长。在模式识别领域，为了提高分类识别的正确率，人们通常需要采集数量巨大的原始特征，使得原始特征空间或输入空间的维数高达几千维或几万维。对高维样本数据进行处理时，需要的样本点数很多，而实际中可以利用的样本点数相对样本维数来说却少得多，这就是模式识别领域中的维数灾难。维数灾难给模式识别带来了两个方面的重要影响：一是使得很多在低维空间具有良好性能的分类算法在计算上变得不可行；二是在训练样本数量一定的前提下，特征维数的增加使得样本统计特性的估计变得更加困难，从而降低了分类器的泛化能力，出现“过学习”或“过训练”的现象。特征降维是解决维数灾难问题的有效手段之一，它通过对高维数据的分析来寻找嵌入在高维数据空间中的本征低维结构，以达到数据降维的目的。在很多模式识别领域中，人们都用到了特征降维技术。下面以人脸识别为例说明特征降维在模式识别中的作用。人脸识别是利用人的脸部特征进行身份鉴定的生物特征识别技术，它是典型需要特征降维的模式识别应用技术。人脸识别需要处理的对象是二维或者高维数据，灰度人脸图像是二维数据，彩色人脸图像则是三维数据。人们在人脸识别中通常要把二维或者高维数据转变成一维的向量数据，然后再进行后续处理。然而，把二维或高维数据转变成一维数据后，数据维数会变得非常大，例如一个128×128的灰度人脸图像，转变成一维数据后是16384维，这就出现了维数灾难问题。因此，为了进行分类器设计，需要把图像从测量空间变换到维数大大减少的特征空间，使得人脸图像在这个特征空间中可以由一个特征向量有效表示，进而使得计算机可以对其进行高效处理。在图1.2中，应用某种降维算法将灰度人脸图像通过降维处理，嵌入到了一个二维特征空间，横轴反映面部表情的变化，纵轴反映头部角度的变化。可以看出，该特征空间可以有效刻画人脸图像的本质特征，为后续的分类识别提供了很大的方便。

除非特别声明，下面凡是提到模式识别，均指计算机模式识别。图1.2人脸识别中的特征降维

1.2模式识别的基本方法

分类识别是人类时时刻刻都在进行的活动，人们希望机器能代替人类进行分类识别工作。因此，对于模式识别的研究引起了人们极大的兴趣。模式识别伴随着计算机的研究和应用日益发展起来，其应用领域涉及社会生活的各个方面，而且还在不断发展扩大。目前，模式识别已经发展成一门多学科的交叉学科，涉及数学、计算机科学、神经心理学、信息论、控制论、信号处理等。根据是否利用已知类别的训练样本，可将模式识别分为监督模式识别和非监督模式识别。对于不同的分类对象和不同的分类目的，可以采用不同的模式识别方法。根据采用的模式识别方法，可将模式识别分为统计模式识别、结构模式识别、模糊模式识别、神经网络模式识别等。本节简要介绍这些基本的模式识别方法。

1.2.1统计模式识别

统计模式识别方法是应用最广泛的一类模式识别方法。从本质上说，该类方法都是利用各个类的概率密度函数、后验概率等概念进行分类识别的。其中，聚类分析法、最近邻法、判别域代数界面法和统计决策法是最经典的四种统计模式识别方法。

聚类分析法的基本思想是利用模式之间的相似性进行分类，相似的模式归为一类，不相似的模式归入不同类。需要指出的是，聚类算法看似没有利用概率密度函数等概念，其实不然。在分类过程中，算法不断地计算各个聚类的中心，并将模式与各个聚类中心的距离作为分类的依据，这实际上是在隐含地利用概率分布的思想，因为在一般的概率密度函数下，距离期望值较近的点具有较大的概率密度值。

最近邻法是根据待识别模式的一个或k个近邻训练样本的类别来确定其类别的方法。实际上k－近邻法是利用最大后验概率准则进行分类判决的。判别域代数界面法首先利用已知类别的训练样本产生判别函数，然后根据待识别模式代入判别函数后的值的正负确定其类别。判别函数产生了相邻两类的判别界面，其对应于两类概率函数之差。

统计决策法是在一些分类识别准则下，按照概率统计理论产生各种判别准则，然后利用这些判别准则生成最终的分类识别结果。1.2.2结构模式识别

对于具有复杂结构特征的对象，仅用一些数值特征已不能对其进行充分描述，这时需要采用结构模式识别方法。该方法首先将对象分解为若干基本单元(称为基元)，然后利用这些基元和它们之间的结构关系来描述对象。

在结构模式识别方法中，基元以及基元之间的结构关系采用图或字符串来表示，这些图或字符串称为形式语言的句子，然后根据代表类的文法运用形式语言理论和技术对句子进行句法分析，根据其是否符合某一类的文法来确定其类别。因此，结构模式识别又称为句法模式识别。1.2.3模糊模式识别

在传统的集合论中，元素和集合是要么属于、要么不属于的关系，两者必居其一，而且二者仅居其一。在模糊集合论中，元素是以一定的程度(隶属度)属于某一个模糊集合，也可以属于多个模糊集合。模糊集合主要用来描述不精确的、模糊的概念。模糊数学就是建立在模糊集合基础之上的数学分支。模糊模式识别是利用模糊数学的理论和方法来分析和解决模式识别问题，其基本思想是首先将模式类看成模糊集合，将模式的属性转化为对于模糊集合的隶属程度，然后利用隶属函数、模糊推理和模糊关系进行分类识别。模糊模式识别利用模糊技术来设计机器识别系统，可以更广泛、更深入地模拟人脑的思维过程，从而对客观事物进行更为有效的分类和识别。模糊模式识别方法已在工业、农业、军事、医学、管理科学、信息科学和工程技术等学科和领域中发挥着非常重要的作用。1.2.4神经网络模式识别

人工神经网络简称神经网络，是由大量简单的基本单元(为神经元)相互连接而构成的复杂网络系统。其中，每个神经元的结构和功能比较简单，而构成的系统可以非常复杂。人类感知外界信息依靠的生理基础是神经系统。人工神经网络就是在现代生物学研究人脑组织所取得成果的基础上提出的，用以模拟人类大脑神经网络的结构和行为。人工神经网络具有生物神经网络的某些特性，在自学习、自组织、联想记忆和容错方面具有较强的能力。因此，人工神经网络具有用于模式识别的理论和结构基础，可以处理一些环境信息十分复杂、背景知识不清楚、推理规则不明确的模式识别问题。实际上，模式识别是人工神经网络公认的最成功的应用领域之一。

1.3模式识别的一些基本准则

尽管计算机模式识别发展至今已经取得了令人瞩目的成就，但人们逐渐认识到在实际的研究和应用中，面临很多限制或需遵循的原则。这些原则既对人们的探讨提出了“警示”，也对实际操作具有指导价值。下面叙述几个已经得到大家认可的基本准则。1.3.1奥卡姆剃刀原理

奥卡姆剃刀(Occam′sRazor)原理是由14世纪逻辑学家、圣方济各会修士奥卡姆的威廉(WilliamofOccam)提出的一个原理。这个原理简称为“如无必要，勿增实体”(在多种等价物和多种实现方法中提倡选择最简单的模型或假设，尽量避免产生超出解释、观察所严格需要的更为复杂的理论)。也就是说杀鸡焉用牛刀，尽量不要把问题复杂化，要尽力把没用的、会引起问题复杂化的因素剔除掉。对于识别算法而言，并不是越复杂的算法越有用，有时简单的算法也能够达到较好的性能。这正如爱因斯坦所讲的：描述一个问题，解决一个问题，要尽可能的简单，但不能过于简单。总之，设计的分类器要尽可能保持简单，因为简单的通常是最有效的。尽管在模式识别领域有一个主流观点，学习系统不要比限定的需求更复杂，需遵从奥卡姆剃刀原理,但这个原则让人无法明白系统要做到多大才能不用去适配数据的特殊点(所谓过学习)就能具有推广能力。1.3.2没有免费的午餐定理

在1.2节中，我们介绍了模式识别的基本方法，在每一个基本方法下，又有很多学习算法和技术。面对这么多的算法，人们自然要问是否存在最好的算法？答案是否定的。1997年,Wolpert和Macerday提出了没有免费的午餐定理(NoFreeLunch，NFL)。该定理指出,没有最好的算法，每种算法总有它的优势和缺陷。NFL定理可以简单表述为：对于所有可能的问题，任意给定两个算法A和A′，如果A在某些问题上表现比A′好(差)，那么，A在其他问题上的表现一定比A′差(好)。也就是说，任意两个算法A、A′对所有问题的平均表现度量是完全一样的。该定理隐含指出，任何一种分类算法甚至都不比搜索空间的线性列举或者纯随机搜索算法更优。图1.3给出了没有免费的午餐定理的图示。

图1.3没有免费的午餐在图中，每个方块表示所有可能的分类问题，所在的空间是问题空间，其中，“+”号表示算法的推广性能比平均性能要好，“-”号表示算法的推广性能比平均性能要差，“0”表示恰好是平均性能，这些符号的尺寸表示“好”或“差”的程度。例如，图(a)表示算法在一个小区域上的推广性能比平均性能好得多，但在其他区域都比平均性能略差一些；图(d)表示算法在所有区域上的推广性能都比平均性能要好；图(e)表示算法在一个小区域上的推广性能比平均性能要好，在其他区域上都为平均性能。根据没有免费的午餐定理可知，图(a)、(b)和(c)都是可能出现的情况，图(d)、(e)和(f)都是不可能出现的情况。根据没有免费的午餐定理可知，我们在解决实际的模式识别问题时，要根据特定的问题，选择合适的模式识别算法；不要太迷信于某一个算法的绝对优势，在采用某一算法时要明白“得”与“失”；单一的算法往往不能满足实际需要，需要采用多个算法来提高识别性能，即可以采用集成的策略来获得更符合实际需要的结果。1.3.3丑小鸭定理

20世纪60年代，模式识别研究的鼻祖之一、美籍日本学者渡边慧证明了“丑小鸭定理”。这个定理说的是“丑小鸭与白天鹅之间的区别和两只白天鹅之间的区别一样大”。这个看起来完全违背常识的定理实际上说的是：世界上不存在分类的客观标准，一切分类的标准都是主观的。假设对象被描述成一个原子性质集，我们考虑由这些性质进行所有可能的逻辑组合的谓词，以便训练一个模式识别系统。那么，依据它们拥有的谓词数，所有对象对的相似程度是一样的。这是由于，无论存在与否，所有的原子性质具有一样的初始权值。这导致训练集是没有用的。简而言之，如果我们对问题没有任何了解，我们不可能从观察中学习(推广或推导)。

1.4模式识别的应用

随着模式识别理论和方法的快速发展，模式识别已在目标识别、生物特征识别、图像识别、图形识别和故障诊断等很多领域中得到了广泛的应用。

1.4.1生物特征识别

随着社会的进步和发展，各个领域都对人的身份鉴别提出了更高、更全面的要求。鉴于人的生物特征具有唯一性、稳定性、不能盗用、不会遗忘、难以伪造等特性，现有的身份鉴别方法大都针对人的各种生物特征来实现。需要指出的是，人的生物特征包括生理特征和行为特征两大类。生理特征是先天的，例如脸、指纹、手掌纹、虹膜、视网膜、声音等；行为特征是后天的，习惯使然，例如签名、步态、键盘打字习惯等。迄今为止，生物特征识别涉及人脸识别、指纹识别、掌纹识别、掌形识别、虹膜识别、视网膜识别、语音识别、耳廓识别、体形识别、静脉识别、步态识别、签名识别以及键盘敲击识别等。比尔·盖茨曾预言：“以人类生物

特征(指纹、语音、脸像等)进行身份验证的生物识别技术，在今后数年内将成为IT产业最为重要的技术革命。”下面简单介绍人脸识别、指纹识别和语音识别。

1.人脸识别

人脸是指人的面部视觉特征，主要包括两眼、鼻、口等特征。人脸识别就是利用计算机技术从人脸图像分析中提取出有效的识别信息，用以鉴别人的身份。人脸识别技术已经广泛应用于公安刑侦破案、门禁系统、摄像监视系统、网络应用和信息安全等领域。例如，图1.4所示为北京奥运会的人脸识别系统。图1.4北京奥运会的人脸识别系统人脸识别的主要方法有基于几何特征的人脸识别方法、基于特征脸的人脸识别方法、基于神经网络的人脸识别方法、基于弹性图匹配的人脸识别方法以及基于支持向量机(SVM)的人脸识别方法等。

与基于其他生物特征的识别方式相比，人脸识别具有自然和不易被察觉两个特点。自然性是指该识别方式同人类进行个体识别时利用的生物特征相同。与人脸识别类似，人类也是通过观察比较人脸来确认身份的。另外，语音识别、体形识别也是具有自然性的识别方式，而指纹识别、虹膜识别等都不具有自然性，这是因为人类或者其他生物并不通过这些生物特征来区别个体。不易被察觉性是指该识别方式不容易引起人的注意，进而不容易被欺骗，也不会引起人的反感。人脸识别完全利用可见光获取人脸图像信息，不易引起人的注意，具有一定的友好性和方便性。指纹识别或者虹膜识别都不具有这个特性，因为它们需要利用电子压力传感器采集指纹或者利用红外线采集虹膜图像，这些采集方式很容易被人察觉，一方面有可能会引起人的反感，另一方面更有可能

被伪装欺骗。人脸识别是计算机视觉和模式识别领域最具挑战性的研究内容之一。首先，人脸是复杂的三维形体，很难用数学语言具体地描述；其次，人脸在不同个体之间的区别不大，所有的人脸结构都很相似，甚至面部器官的结构外形都很相似，这个特点有利于人脸定位，但是不利于人脸识别。此外，随着人的年龄增长，面部特征会有一定变化。另外，人脸容易受到光照、姿势、表情、观察角度和遮盖物(例如眼镜、口罩、头发、胡须等)等的影响。

2.指纹识别

指纹是指人类手指末端正面皮肤上凹凸不平产生的纹路，其形成依赖于胚胎发育时的环境。指纹纹线有规律地排列形成了不同的纹型，这些纹线的起点、终点、结合点和分叉点是指纹的细节特征点。与其他生物特征相比，指纹具有两个突出的优点：一是稳定性，指纹具有很强的稳定性，从胎儿在6个月时指纹完全形成到人死后尸体腐烂，指纹的纹型和细节特征点等不会有明显变化；二是独特性，指纹具有明显的独特性，至今还没发现两个指纹完全相同的人。基于这两个特点，指纹识别能够非常可靠地进行人的身份鉴别，已经在公安刑侦破案、网络管理、银行、社保、雇员证明、门禁系统等领域得到了非常广泛的应用。指纹识别示例如图1.5所示。图1.5指纹识别指纹识别是指通过图像采集设备读取指纹图像，然后利用计算机识别软件提取指纹的特征数据，最后通过匹配识别算法得到识别结果，以确定指纹所有人身份的技术。指纹识别系统是一个典型的模式识别系统，主要包括指纹图像采集、指纹图像处理、特征提取、保存数据、特征值比对与匹配等过程。指纹识别技术涉及图像处理、模式识别、机器学习、计算机视觉、数学形态学、小波分析等众多学科。指纹识别是生物特征识别领域发展最成熟、最可接受的一种识别技术。然而，指纹识别还面临一定的挑战。在日常生活中，有一部分人的指纹是无法采集的，这里既有先天遗传的问题，也有后天因素造成的。例如由于手指皮肤有伤疤、长茧、病态皮肤、皮肤干燥、皮肤老化、采集设备受污染等原因，会使得图像采集设备无法采集或者不能提供高质量的指纹图像。此外，由于每次捺印的方位不完全一样，着力点不同会带来不同程度的变形，也会给后续正确提取特征和实现正确匹配带来一定的困难。

3.语音识别

语音是人类信息交流的基本手段，语音中包含语义信息、语言信息、说话人信息和情感信息等。语音识别就是让机器通过识别和理解过程把语音信号转变为相应的文本或命令的技术，即让计算机识别出人类语音中的各种信息。语音识别涉及信号处理、模式识别、概率论、信息论、发声机理和听觉机理、人工智能等学科。语音识别已经在语音输入系统、语音控制系统和智能对话查询系统中得到了广泛的应用。例如在语音控制系统中，就是利用语音来控制设备的运行，相对于手动控制来说更加快捷、方便。另外,语音识别可以用在诸如工业控制、语音拨号系统、智能家电等许多领域，如图1.6所示。图1.6语音识别在智能家电中的应用一个语音识别系统主要包括预处理、特征提取、模型建立、模式匹配和判决规则等五个主要部分。语音识别的基本方法有三种:基于声道模型和语音知识的方法、模板匹配的方法以及利用人工神经网络的方法。按照识别任务的不同，语音识别可以分为四类:声纹识别、语种识别、关键词识别和连续语音识别。所谓声纹识别，就是从语音信号中提取说话人的信息以鉴别说话人身份的技术。语种识别就是识别出语音所属的语言，广泛应用于语音信息检索和军事领域。关键词识别就是从说话人的连续语音中把特定的关键词检测出来，例如，人名、地名和事件名等。关键词识别广泛应用于语音检索和语音监控中。连续语音识别就是识别人类的自然语言，将这种口述语言转换为相应的文本，或者对口述语言中包含的要求或询问做出正确的反应。语音识别面临以下几个问题。

第一，不同人具有不同的语音模式，即使同一说话人的语音模式有时也会不同。例如，同一说话人在随意说话和认真说话时的语音信息是不同的，而且，一个人的说话方式会随着时间变化。

第二，语音具有一定模糊性，说话人在讲话时，不同的词可能听起来是相似的。

第三，单个字母或词、

字的语音特性受上下文的影响，以致改变了重音、音调、音量和发音速度等，对于语音识别有一定的影响。

第四，环境噪声和干扰对语音识别有很大影响。

1.4.2目标识别

目标识别有“狭义”和“广义”两种解释。狭义地说，目标识别是利用雷达回波中的幅度、相位、频谱和极化等目标特征信息，通过数学上的各种多维空间变换来估算目标的大小、形状、重量和表面层的物理特性参数，最后根据大量训练样本所确定的鉴别函数，在分类器中进行识别判决的技术。广义地说，目标识别是将一个特殊目标(或一种类型的目标)从其他目标(或其他类型的目标)中区分出来。例如，从一幅遥感或自然图像中识别出感兴趣的目标就属于目标识别。目标识别已经成功应用于国民经济、空间技术和国防等领域，包括利用雷达和计算机对飞机或舰船等目标进行辨认，利用微波遥感仪器勘探矿藏或石油等地球资源，利用图像特定内容对Internet上的图片进行检索等。下面介绍两种经典的目标识别：雷达目标识别和水下目标识别。

1.雷达目标识别

雷达目标识别是从目标的雷达回波中提取目标的有关信息标志和稳定特征并判断其属性的识别技术。在雷达目标识别问题中，首先可以利用回波信号的幅值、相位、频率和极化等获得用于目标识别的信息，然后对目标信息进行训练和识别。进行雷达目标识别，必须依靠目标识别技术，模式识别技术的发展为该问题的研究提供了有利的条件。统计模式识别方法、模糊模式识别方法、基于模型和基于知识的模式识别方法以及神经网络模式识别方法等在雷达目标识别中均有成功的应用。

2.水下目标识别

水下目标识别是现代声纳系统与水声对抗的一个重要组成部分，是水面舰艇和潜艇急需解决的关键技术。在水下目标识别中，由于舰船的辐射噪声包含了丰富的目标相关信息，因此基于舰船辐射噪声的目标识别已经成为一个重要的研究方向，其基本任务就是正确采集各种舰船的辐射噪声并进行分类识别。由于水下目标型号繁多，目标所处环境多变，因此在实际的分类识别应用中很难达到预期的性能。神经网络的在线学习、自适应性能使得其在水下目标识别问题中应用比较普遍。此外，也可以将模糊集理论与神经网络系统结合在一起，得到模糊神经网络分类器，从而提高目标判别的灵活度，增加判决的可信度。1.4.3图像识别

图像是指各种图形和影像的总称。图像识别就是利用计算机对图像进行处理、分析和理解，以识别各种不同模式的目标和对象的技术。目前，图像识别涉及遥感和航空图像分析、显微图像、热像及超声图像检查、金相图分析与鉴定、车牌识别等领域。实际上，前面介绍的人脸识别和指纹识别也属于图像识别的一种。

图像识别的主要方法有统计图像识别方法、结构图像识别方法、模糊图像识别方法和神经网络图像识别方法。一个图像识别系统主要包括四个组成部分：图像输入、预处理、特征提取与选择和分类判决。其中，图像输入是指将图像信息采集下来输入计算机，它是图像识别的首要任务。为了提高后续特征提取和分类判决的效率，对图像进行预处理是必不可少的，它的处理性能好坏直接影响图像识别的效果。图像预处理主要包括图像分割、图像增强、图像去噪、图像二值化和细化等处理步骤。图像分割是将图像分成互不重叠、具有各自特性区域的图像处理过程，这里的特性可以是颜色、亮度、纹理等。图像增强是将原来不清晰的图像变得清晰或强调某些关注的特征、抑制非关注的特征，以改善图像质量、丰富信息量的图像处理过程。图像在数字化和传输过程中常受到成像设备与外部环境噪声干扰等影响，去除或减轻图像中噪声的过程就是图像去噪。图像二值化是将图像转化为二值图像；图像细化是把清晰但不均匀的二值图像转化为线宽仅为一个像素的点线图像。

特征提取是将能够反映图像本质的特征用数值形式表达出来。特征选择是在提取的特征中挑选出对于分类判决最有用的特征，去除冗余或无效的特征。用于图像识别的特征大致有以下四类：颜色或灰度的统计特征、纹理或边缘特征、图像代数特征、图像变换系数特征。

分类判决是指根据所提取和选择的特征进行分类判决的过程。特征提取和分类判决这两个过程密切相关。1.4.4图形识别

图形识别技术是计算机视觉中的一个重要研究内容，已广泛地应用于工业自动化、图像分析与识别、文字识别等领域。图形识别中的模式是指由若干元素或成分按照一定关系形成的某种刺激结构，也可以说模式是刺激的组合,例如，几个线段组成的一个图形或字母，几个笔画组成的一个汉字、一幅人头像等。为了进一步开发计算机的功能，人们力图将图形识别的能力赋予计算机，图形识别系统应运而生。图形识别系统一般包括以下四个部分：获取图形信息、预处理、特征提取和学习及分类识别。图形识别系统的关键在于特征提取和分类识别两个阶段。如果在特征提取阶段能够选取对输入图形具有高度准确描述能力的特征，则对系统的建立具有重要的意义。此外，有效的图形特征可以减轻后续的模式识别工作的负担。在分类识别阶段，分类器的正确设计可使系统具有较高的准确性和稳定性。现有的图形识别方法主要包括基于神经网络的图形识别方法和基于分类器联合的图形识别方法等。1.4.5故障诊断

故障诊断是指对系统运行状态和异常情况作出判断，并根据诊断作出判断，为系统故障恢复提供依据。要对系统进行故障诊断，首先必须对其进行检测，在发生系统故障时，对故障类型、故障部位及原因进行诊断，最终给出解决方案，实现故障恢复。在故障诊断系统中应用模式识别主要是针对系统的运行状态进行识别和分类，从而对故障或者异常情况进行识别和分类。基于模式识别技术的故障诊断系统主要包括四大部分：

(1)数据的获取及预处理，主要是将传感器的信号转变成计算机可以运算的符号，并将数据进行适当的预处理。

(2)为了有效地进行分类识别，根据系统的性质和要求对原始数据进行特征提取和选择。

(3)根据获得的特征正确地选择学习器或分类器，对系统状态进行分类。

(4)根据分类和识别的结果对系统作出相应的决策判断。基于模式识别技术的故障诊断方法已经受到了广泛的关注，包括利用模糊聚类和神经网络模式识别方法进行柴油机故障诊断，利用支持向量机进行电机设备故障诊断，利用模糊推理进行电力电子电路故障诊断等。第2章线性判别函数法2.1判别函数的基本概念2.2线性判别函数2.3感知器学习算法2.4最小均方误差算法2.5Fisher线性判别法2.6线性二分能力在模式识别与分类中，可以根据训练样本集提供的信息，直接进行分类器的设计。我们面临的最简单的是两类样本的分类问题，这时人们自然会想到能否在特征空间(决策域)中做一条直线(平面或超平面)将两类样本分开，需要解决的问题是这条直线(平面或超平面)如何去做，这就是基本的线性判别问题。至于更深一步的理论研究，例如,当样本集扩充后该分类判决是否还有效(也就是泛化性能)？分类界面是否还会是直线(平面或超平面)？样本的分布与统计特征的关系如何?等等,也是要探讨的问题。由于特征空间(决策域)的分界面是由数学表达式来描述的，如线性函数或各种非线性函数等，所以分界面方程的确定主要包括函数类型的选择以及参数的确定。其中函数类型是由设计者选择的，而参数的确定则是依据一定的准则函数并通过学习过程来实现的。线性分类器的优点是简单，在计算机上容易实现，因此在模式识别中被广泛使用。

本章主要讨论判别函数法和线性判别函数的基本概念，线性分类器的设计。

2.1判别函数的基本概念

模式识别系统的主要作用是判别各个模式的类别属性。例如，一个两类问题就是将模式x划分为ω1和ω2两类。对于一个二维的两类问题，模式样本可表示为x=(x1，x2)T，其中x1、x2为坐标变量(即模式的特征值)。所有的样本分布在一个二维平面上，如图2.1所示。如果在两类之间能找到一条分界线将分属于ω1和ω2的样本分开，这样就可以知道每个样本的类别。设分界线的方程为

(2-1)

这里w1、w2、w0是方程的参数或权值。图2.1两类二维样本的分布示意图可以假设属于ω1类的模式位于g(x)>0的一侧，属于ω2类的模式位于g(x)<0的一侧。反之，如果将一个未知类别的模式x带入g(x)，则应该有下面的结果：若g(x)>0，则x属于ω1类；若g(x)<0，则x属于ω2类；若g(x)=0，则x落在分界线上，此时不能判定x的类别。因此，g(x)可以用来判断某一未知模式所属的类别，鉴于此我们称g(x)为判别函数。

判别函数是直接用来对模式样本进行分类的准则函数，也称为判决函数或决策函数。寻找类别之间分界线的方法称为判别函数法，判别函数法的结果提供了一个确定的分界线方程，这个分界线方程就是判别函数。因此，判别函数描述了各类之间的分界线的具体形式。判别函数可以是线性函数，也可以是非线性函数，这取决于模式类在空间中的分布情况，以及我们对分布的先验信息的了解程度。由于线性分类器涉及到的数学方法比较简单，在计算机上容易实现，因此得到广泛的应用。但是在模式识别的许多具体问题中，线性分类器固有的局限性使得它并不能提供理想的识别效果，必须求助于非线性分类器。这里需要强调指出的是，有些简单的非线性分类器对模式识别问题的解决显得既简单效果又好。

2.2线性判别函数

线性判别函数是一种最简单的判别函数，它是由所有特征向量的

线性组合构成的。

2.2.1线性判别函数的一般形式

在一般的d维特征空间中，线性判别函数的表达式为

g(x)=wTx+w0

(2-2)

式中:x是d维特征向量，又称为样本向量；w0是常数且非零，也称为阈值权；w是d维加权向量。x和w分别表示为

x=(x1，x2，…,xd)T，w=(w1，w2，…,wd)T

在二维欧氏空间中，由线性判别函数所确定的判别边界为一条直线；在三维空间中,为一个平面；当维数超过三时,判别边界称为超平面。通常由线性判别函数确定的判别界面通称为超平面。

在式(2-2)表示的一般的线性判别函数中，由于w0非零，决策超平面不通过空间原点，因此可以使用广义线性函数的扩维方法实现齐次化问题。式(2-2)也可以写成增广向量的形式：(2-3)式中:y=(x1，x2，…,xd，1)T称为增广样本向量，a=(w1，w2，…,wd，w0)T称为增广权向量。g[(x)]=aTy称为广义线性判别函数。在这个新的特征空间中，决策超平面通过原点，且特征空间的维数由d维扩张为d+1维。2.2.2线性判别函数的基本性质

下面在模式类线性可分的情况下，讨论线性判别函数的性质。

1.两类情况

已知两个模式类ω1、ω2，待识别样本x，则线性判别函数具有如下性质；(2-4)此时g(x)=0为d维空间的一个分类超平面。

2.多类情况

对于m个线性可分的模式类ω1，ω2，…，ωm，有以下三种划分方式。

1)ωi

/两分法

ωi

/两分法的基本原理是将每一个模式类用一个单独的判别界面与其他模式类分开。ωi类的判别函数gi(x)可以将属于ωi类的样本与不属于ωi类的样本分开。决策准则为，i=1，…，m(2-5)若仅存在gk(x)>0，k∈{1，2，…，m}，而其余gj(x)<0(j≠k，j∈{1，2，…，m})，则判定x∈ωk类。

图2.2是一个二维三类问题的ωi/两分法分类示意图。图2.2ωi/两分法示意图

图2.2中每一类都可用一个简单的直线判别界面将该类与其他类分开。例如样本x∈ω1，从图中的几何表示可知，需同时满足下面三个条件：g1(x)>0，g2(x)<0，g3(x)<0。这时不能只用g1(x)>0这一个条件判定x所属的类别，因为在模式空间中还存在不确定的区域，它们不属于三类中的任何一类，如图中g1(x)<0，g2(x)<0，g3(x)<0所确定的区域。因此对m类问题，需要同时有m个判别函数。例2.1对于一个三类问题，假定三个判别函数分别为

g1(x)=－x1+x2－1，g2(x)=x1+x2－9，g3(x)=－x2+1

请画出各类判别区域，并判断x=(7，5)T属于哪一类。

解将x=(7，5)T代入三个判别函数中，有

g1(x)=－7+5－1=－3<0

g2(x)=7+5－9=3>0

g3(x)=－5+1=－4<0

因为g1(x)<0，g2(x)>0，g3(x)<0，所以x∈ω2。各类的判别区域如图2.3所示，其中ω1的判别区域位于g1(x)>0，g2(x)<0，g3(x)<0的区域；ω2的判别区域位于g1(x)<0，g2(x)>0，g3(x)<0的区域；ω3的判别区域位于g1(x)<0，g2(x)<0，g3(x)>0的区域。图中的IR1、IR2、IR3区域是两个判别函数大于0的区域，IR4区域是三个判别函数都小于0的区域，这些不确定区域的样本是无法分类的。图2.3各类判别区域示意图

2)ωi/ωj两分法

我们可将任意的两个类别用一个判别界面分开。对于m类中的任意两类：由ωi、ωj(i≠j)可以确定一个超平面gij(x)=来把ωi、ωj两类分开，且gij(x)=－gji(x)。决策准则为

识别ωi类时，只有下标以i开头的m－1个判别函数全为正值时，才能判定x∈ωi。若其中有一个为负值，则为不确定区域(IR区)。i，j∈{1，2，…，m}，i≠j

(2-6)

ωi/ωj两分法每分离出一类模式，需要m－1个判别函数，要分离出所有的m类模式，共需要个判别函数。

图2.4是一个二维三类问题的ωi/ωj两分法分类示意图。图中有三个判别界面g12(x)=0，g13(x)=0，g23(x)=0，三个模式类ω1，ω2，ω3，每个判别界面都可以将两个模式类分开，但穿过了其他模式类。以ω1类为例，只有下标以1开

头的所有判别函数值都大于零，即g12(x)>0，g13(x)>0时，才能判定x∈ω1类，而g23(x)在识别ω1类模式时不起作用。图2.4ωi/ωj两分法分类示意图例2.2对于一个三类问题，假定三个判别函数为

g12(x)=－x1－x2+6，g13(x)=－x1+4，g23(x)=－x1+x2

请画出各类判别区域，并判断x=(5，3)T属于哪一类。

解将x=(5，3)T代入三个判别函数中，有g12(x)=－5－3+6=－2，g13(x)=－5+4=－1，g23(x)=－5+3=－2。也可写成g21(x)=2，g31(x)=1，g32(x)=2。因为g31(x)>0，g32(x)>0

，所以x∈ω3。

各类的判别区域如图2.4所示，其中ω1的判别区域位于g12(x)>0，g13(x)>0的区域；ω2的判别区域位于g21(x)>0，g23(x)>0的区域；ω3的判别区域位于g31(x)>0，g32(x)>0的区域。在三条分界线相交组成的三角形区域内的样本无法判断所属类别，该区域为不确定区域IR。

3)ωi/ωj两分法特例

有时为了处理方便，可将ωi/ωj两分法的约束条件放宽。对于m类的判别问题，当确定了m个超平面时，采用下列决策准则：

则x∈ωi。

根据决策准则式(2-7)，任一个模式x总能划分到m类中的某一个模式类中去，因此作为ωi/ωj两分法的特例，除边界之外不存在不确定区域。图2.5是m=3时的判别区域划分示意图。(2-7)图2.5ωi/ωj两分法(特例)分类示意图例2.3对于一个三类问题，假定三个判别函数为

g1(x)=－x1+x2，g2(x)=x1+x2－1，g3(x)=－x2

试用ωi/ωj两分法特例方法判断x=(－0.5，1)T属于哪一类，并分别给出三类的判别界面。

解分别计算得g1(x)=1.5，g2(x)=－0.5，g3(x)=－1，因为g1(x)>g2(x)，g1(x)>g3(x)，所以x∈ω1。

ω1类的判别界面为

g1(x)－g2(x)=－2x1+1=0，g1(x)－g3(x)=－x1+2x2=0

ω2类的判别界面为

g2(x)－g1(x)=2x1－1=0，g2(x)－g3(x)=x1+2x2－1=0

ω3类的判别界面为

g3(x)－g1(x)=x1－2x2=0，g3(x)－g2(x)=－x1－2x2+1=0

三类判别界面如图2.5所示。2.2.3线性判别函数的几何性质

对于两类问题，设线性判别函数为g(x)=wTx+w0，其中w=(w1，w2，…，wd)T，x=(x1，x2，…，xd)T，则由g(x)确定的d维欧几里德空间中的超平面为g(x)=wTx+w0=0。设超平面为H，则对H上的任意两点x1，x2有

g(x1)=wTx1+w0=wTx2+w0=g(x2)

(2-8)

即

wT(x1－x2)=0

(2-9)式(2-9)表明向量w和x1－x2正交，由x1，x2的任意性可知，w垂直于超平面H上的任意向量x1－x2，也就是说w垂直于超平面H，即w是超平面H的法向量。根据决策准则式(2-7)，当g1(x)>g2(x)时，判定x∈ω1；否则，x∈ω2。从而得出法向量w的方向由超平面的负侧指向正侧。设超平面的单位法向量为u，即

其中||w||为向量w的模值，||w||2=wTw。二维情况时的超平面示意图如图2.6所示。(2-10)图2.6超平面示意图当x不在超平面H上时，设xp为x在H上的投影向量，则x可表示为

其中r为x到超平面H的距离。这时

因为xp在超平面H上，故有g(xp)=wTxp+w0=0，于是g(x)=r||w||。因此，x到超平面H的距离为(2-11)(2-12)(2-13)如图2.7所示，这是一种代数距离(带有正负号)。当x在超平面正侧时，g(x)>0；反之，g(x)<0。

特别的，当x在原点时，g(x)=w0，即原点到超平面

H的距离为

若w0>0，则原点在超平面H的正侧；若w0<0，则原点在超平面H的负侧；若w0=0，则超平面H穿过原点。(2-14)图2.7点到超平面的距离综上所述，对于两类问题，线性判别函数的几何意义在于利用一个超平面实现对d维特征空间Rd的划分，超平面方

向由法向量w确定，它的位置由阈值w0确定。判别函数正比于x点到超平面的代数距离。2.2.4设计线性分类器的主要步骤

分类器的设计是利用训练样本集建立线性判别函数，找到表达式中最好的加权系数向量w和w0(或增广权向量α)，最好的结果恰好出现在准则函数的极值点上。这样，线性分类器的设计工作就转化为寻找准则函数的极值点w*和w*0(或a*)的最优化问题。设计线性分类器的主要步骤如下：

(1)选取一组有类别标志的样本集合R={x1，x2，…，xn}。

(2)确定准则函数J，要求满足以下两个条件：①J应为样本集R、w和w0(或a)的函数；②J的值反映分类性能，它的极值对应于“最好”的决策。

(3)用最优化技术求出准则函数的极值解w*和w*0(或a*)。

2.3感知器学习算法

感知器准则函数的基本思想是寻找一个权向量，使得规范化增广样本向量集的错分样本数最少。下面先介绍几个相关的概念。

2.3.1几个基本概念

1.线性可分的定义

设由n个样本构成的样本集合Y={y1，y2，…，yn}，其中yi为d维的来自于ω1和ω2类的增广样本向量。如果存在权向量a使得对于任意的y∈ω1有aTy>0，则称样本集Y是线性可分的，否则称为线性不可分的。反过来，如果样本集合Y是线性可分的，则一定存在权向量a将样本集合Y正确分为两类。

2.样本规范化

对于任意一个样本yi，如果满足aTyi>0，则属于ω1类；如果满足aTyi<0，则属于ω2类。对样本进行规范化处理，即对ω2类的全部样本都乘以-1，有

则对全部样本yn′∈ω1∪ω2，需寻找满足aTyn′>0的权向量。(2-15)

3.解向量和解区

对于规范化增广样本向量而言，满足aTyi>0

(i=1，2，…，n)的权向量称为解向量，记为a*。权向量a可看成权空间中的一点，对于任一yi，要求aTyi>0。方程aTyi=0在权向量空间确定了一个超平面Hi，这个超平面的法向量为a，超平面正侧的向量满足aTyi>0。n个样本将确定n个超平面，每个超平面把权空间分为两个半空间。所以，满足aTyi>0(i=1，2，…，n)的权向量必在这n个超平面正侧的交叠区内，这个区域就是a的解区，解区中的任意向量都是解向量a*，如图2.8所示。为了使解向量a*更加可靠，需要对解区加以限制。一

般来讲，解向量越靠近解区中间,越能对新的样本进行正确分类。因此引入余量b>0，使解向量满足aTyi>b(i=1，2，

…，n)。显然,由此确定的正半空间的交叠区(新解区)位于原解区中，而且它的边界离原来解区边界的距离为b/||yi||，如图2.9所示。

以上关于两类问题的解区和解向量的概念也可以推广到线性可分的多类问题中。图2.8权向量的解区和解向量图2.9解区和解向量示意图2.3.2感知器算法

对于线性可分的两类问题ω1，ω2，设规范化增广样本集合Y={y1，y2，…，yn}，n为样本容量，寻找解向量a使其满足

aTyi>0，i=1，2，…，n

(2-16)

为此构造感知器准则函数

其中yk为错分样本集合，当y∈yk时，有

-aTy≥0

(2-18)(2-17)显然Jp(a)≥0。当且仅当全部样本分类正确且没有错分样本时才会有Jp(a*)=minJp(a)=0，此时a*就是要寻找的最优解向量。下面给出几个求解a*的算法。

1)梯度下降算法

在数学分析中，函数J(a)的梯度方向J(ak)是这样一个方向：在点wk处，它指向J(a)增加最快的方向,而J(a)的负梯度方向－J(ak)则指向J(a)下降最快的方向。设准则函数为Jp(a)，使得Jp(a)达到最小时的最优解向量为a*。下面我们采用感知器的梯度下降算法求解最优解a*。

感知器准则函数的梯度函数为(2-19)梯度下降法的迭代公式为

其中yk是被权向量a(k)错分的样本集，ρk为第k次迭代时的步长因子。ρk的取值大小是有理论依据的，为了简化分析取步长因子ρk=1，得迭代式为

可以证明，对于线性可分的样本集，经过有限次修正，一定可以找到一个解向量a*，使得算法在有限次迭代后收敛。收敛速度取决于初始值a(0)与系数ρk。

(2-20)(2-21)式(2-21)在迭代时，每次计算需要用到所有的错分样本。既然从原理上已经确定了错分样本对于迭代解的修正方向，为了减少计算量，每次迭代只由一个错分样本完成，表示为a(k+1)=a(k)+yk

(2-22)

式中yk为第k次迭代使用的单个错分样本。式(2-22)称为单错分样本迭代式。感知收敛定理如果样本集合是线性可分的，那么由式(2-22)所得到的序列必定终止于某个解向量。

证明设为目标解向量，如果样本集合线性可分，则有Tyi>0。设比例因子α>0，由式(2-22)得到

(2-23)

其平方范数为

由于yk为错分样本，有a(k)Tyk≤0，因此

(2-24)

设样本向量最大长度

(2-25)和解向量与样本向量的最小内积

(2-26)

不等式可化为

(2-27)

选择比例因子

(2-28)得到

(2-29)每次校正，从a(k+1)到的平方距离则减少τ2，经过k次校正后有

(2-30)

由于平方距离非负，因而经过不超过

次校正迭代终止。(2-31)

2)奖惩算法

将感知器梯度下降算法进一步具体化就是“奖惩”算法；当分类器发生分类错误时，通过修正权向量对分类器进行“惩罚”，使其向正确的方向转换；当分类正确时，保持权向量不变对其进行“奖励”，表现为不罚。以两类分类情况为例，算法具体步骤为：

(1)设规范化增广样本集合Y={y1，y2，…，yn}，初始化权向量，置k=0。

(2)输入n个训练样本，计算判别函数g(yk)=a(k)Tyk，其中a(k)为第k次迭代的权向量。

(3)按照如下公式修正权向量：

其中c为正的校正增量。如果a(k)Tyi>0，则表明分类器对样本yi的分类正确，权向量保持不变。如果a(k)Tyi≤0，则表明分类器对样本yi的分类发生了错误，需要修正权向量。

(4)令k=k+1，返回(2)，直到权向量a对所有的训练样本

均稳定不变，此时所有的训练样本被正确分类。(2-32)例2.4已知两类训练样本；

ω1：x1=(0，0)T，x2=(0，1)T

ω2：x3=(1，0)T，x4=(1，－1)T

用感知器奖惩算法求解判别函数，并绘出判别界面。

解将训练样本写成增广向量的形式，并进行规范化处理，将ω2类的样本乘以－1，得

x1=(0，0，1)T，x2=(0，1，1)T，x3=(－1，0，－1)T，x4=(－1，1，－1)T取初始权向量w(1)=［0，0，0］T，取校正增量c=1,则迭代过程如下；

第一次迭代：，故权向量修改为w(2)=w(1)+x1=(0，0，0)T+(0，0，1)T=(0，0，1)T，故权向量修改为

w(3)=w(2)=(0，0，1)T

，故权向量修改为w(4)=w(3)+x3=(0，0，1)T+(－1，0，－1)T=(－1，0，0)T

，故权向量修改为

w(5)=w(4)=(－1，0，0)T

在第一次迭代中有两次w(k)Txi≤0，说明发生了两次错判，进行第二次迭代。第二次迭代：

w(5)Tx1=0≤0，故w(6)=w(5)+x1=(－1，0，0)T+(0，0，1)T=(－1，0，1)T;

w(6)Tx2=1>0，故w(7)=w(6)=(－1，0，1)T;

w(7)Tx3=0≤0，故w(8)=w(7)+x＋=(－2，0，0)T;

w(8)Tx4=2>0，故w(9)=w(8)=(－2，0，0)T。

第三次迭代：

w(9)Tx1=0≤0，故w(10)=w(9)+x1=(－2，0，0)T+(0，0，1)T=(－2，0，1)T;

w(10)Tx2=1>0，故w(11)=w(10);

w(11)Tx3=1>0，故w(12)=w(11);

w(12)Tx4=1>0，故w(13)=w(12)。第四次迭代：

w(13)Tx1=1>0，故w(14)=w(13)；

w(14)Tx2=1>0，故w(15)=w(14)；

w(15)Tx3=1>0，故w(16)=w(15)；

w(16)Tx4=1>0，故w(17)=w(16)。

由于第四次迭代的分类结果全部正确，因此解向量为w=(－2，0，1)T，相应的判别函数为g(x)=－2x+1，判别界面为g(x)=0。

这里需要指出的是，当初始值w(1)和c取其他值时，结果可能不一样。因此，感知器奖惩算法的解不是单值的。

2.4最小均方误差算法

感知器算法是针对线性可分的情形设计的。对于线性不可分的情况，它具有不收敛的缺点。最小均方误差(LeastMeanSquareError，LMSE

)算法