模式识别与智能计算——Matlab技术实现(第2版)(txt+pdf+epub+mobi电子书下载)

作者：杨淑莹

出版社：电子工业出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

模式识别与智能计算——Matlab技术实现(第2版)试读：

再版前言

模式识别已经成为当代高科技研究的重要领域之一，它已发展成为一门独立的新学科。模式识别技术迅速扩展，已经应用在人工智能、机器人、系统控制、遥感数据分析、生物医学工程、军事目标识别等领域，几乎遍及各个学科领域，在国民经济、国防建设、社会发展的各个方面得到广泛应用，产生了深远的影响。

再版新书广泛吸取了统计学、神经网络、数据挖掘、机器学习、人工智能、群智能计算等学科的先进思想和理论，将其扩充到模式识别体系中。以一种新的体系，系统、全面地介绍模式识别的理论、方法及应用。全书共分为三部分，第一部分基础篇，内容包括模式识别的基本概念，特征的选择与提取，模式相似性测度。这一部分介绍模式识别的基本概念和基本方法。第二部分分类器设计篇，内容包括：贝叶斯（Bayes）分类器设计，判别函数设计，神经网络分类器设计，决策树分类器设计，粗糙集分类器设计。这一部分利用手写数字分类识别的具体实例把模式识别方法结合起来，为广大研究工作者和工程技术人员对相关理论的应用起到借鉴作用。第三部分聚类分析，内容包括基本聚类算法，模拟退火聚类分析，模糊聚类分析，禁忌搜索算法聚类分析，遗传算法聚类分析，群体智能聚类算法（蚁群算法聚类分析，粒子算法群聚类分析）。这一部分采用一幅含有需要聚类分析的图像形象生动地说明各种聚类算法。

国内外论述模式识别技术的书籍不少，但由于这一领域涉及深奥的数学理论，往往使实际工作者感到困难，而大部分书是罗列模式识别的各种算法，见不到算法的实际效果和各种算法对比的结果，而这正是学习者和实际工作者所需要了解和掌握的内容。目前还确实缺少一本关于模式识别技术在实际应用方面，具有系统性、可比性和实用性的参考书。

本书特点如下：

1.选用新技术。除了介绍许多重要经典的内容以外，书中还包括了最近十几年来才刚刚发展起来的并被实践证明有用的新技术、新理论，比如支持向量机、BP神经网络、RBF神经网络、PNN神经网络、CPN神经网络、SORNN神经网络、决策树、粗糙集理论、模糊集理论、模拟退火、遗传算法、蚁群算法、粒子群算法等，并将这些新技术应用于模式识别当中，提供这些新技术的实现方法和源代码。

2.实用性强，针对实例介绍理论和技术，使理论和实践相结合，避免了空洞的理论说教。书中实例取材于手写数字模式识别，对于数字识别属于多类问题，在实际应用中具有广泛的代表性，读者对程序稍加改进，就可以应用到不同的场合，如文字识别、字符识别、图形识别等。

3.针对每一种模式识别技术，书中分为理论基础、实现步骤、编程代码三部分。在掌握了基本理论之后，按照实现步骤的指导，可以了解算法的实现思路和方法，再进一步体会短小精悍的核心代码，学习者可以很快掌握模式识别技术，经过应用本书提供的实例程序，立刻会见到算法的实际效果。书中所有算法都用Matlab编程实现，便于读者学习和应用。

本书内容基本涵盖了目前“模式识别”重要的理论和方法，但并没有简单地将各种理论方法堆砌起来，而是将作者自身的研究成果和实践经验传授给读者，在介绍各种理论和方法时，将不同算法应用于实际中，内容包括需要应用模式识别技术解决的问题，模式识别理论的讲解和推理，将理论转化为编程的步骤，计算机能够运行的源代码，计算机运行模式识别算法程序后的效果，以及不同算法应用于同一个问题的效果对比。使读者面对如此丰富的理论和方法不至于无所适从，而是有所学就会有所用。

由于至今还没有统一的、有效的可应用于所有的模式识别的理论，当前的一种普遍看法是，不存在对所有的模式识别问题都适用的单一模型和解决识别问题的单一技术，我们所要做的是把模式识别方法与具体问题结合起来，把模式识别与统计学、神经网络、数据挖掘、机器学习、人工智能、群智能计算等学科的先进思想和理论结合起来，为读者提供一个多种理论的测试平台，并在此基础上，深入掌握各种理论的效能和应用的可能性，互相取长补短，开创模式识别应用的新局面。

本书可作为高等院校计算机工程、信息工程、生物医学工程、智能机器人学、工业自动化、模式识别等学科研究生、本科生的教材或教学参考书，也可供有关工程技术人员参考。

参加本书编写的还有：邓飞、张成、王立群、任翠池、冯帆、王博凯、牛廷伟、王丽贤、王光彪、贾紫鹃等，他们在作者指导下的研究工作中付出了辛苦的劳动，取得了有益的研究成果，正是在他们的努力下本书得以顺利完成，在此表示衷心的感谢。同时，对张桦教授、徐伯夏研究员、李兰友教授给予的帮助和支持表示衷心的感谢。本书的出版得到天津理工大学出版基金的资助。由于编者业务水平和实践经验有限，书中缺点与错误在所难免，欢迎读者予以指正！

作者将不辜负广大读者的期望，努力工作，不断充实新的内容。为方便广大读者，提供了技术支持电子邮箱：ysying1262＠126.com。读者可通过该邮箱及时与作者取得联系，获得技术支持。

著者

再版说明

这次修订，增加了局部搜索算法，即禁忌搜索算法，使本书的寻优算法涵盖了基本聚类算法、基本启发式的局部搜索和基于群体智能的全局搜索三大类算法，较第一版内容更加全面。基本聚类算法当中比较典型的有：层次聚类算法，K均值算法和迭代自组织的数据分析、模糊聚类算法，它们采用点对点计算方式。基于模拟退火思想改进的K均值聚类算法和禁忌搜索算法属于启发式方法，是对局部邻域搜索扩展后的一种全局逐步寻优算法，其中模拟退火算法从单个解出发，通过扰动产生一个新的候选解，禁忌搜索算法从单个解出发产生多个新的候选解。群体智能搜索算法有遗传算法、蚁群算法和粒子群算法等，它们采用全局分布随机产生多个候选解，属于全局搜索算法。这些算法各有不同的特点，随着读者对这些算法的了解和深入研究，将它们结合起来，形成混合算法，将会避免单一算法的缺点，保证算法的收敛性，从而提高解的质量。

此外，还将全书内容进行归纳整合，将特征的选择与优化内容进行精简，压缩部分复杂内容；改进了一些分析、论断和文字表述，同时改进了部分编程代码，力求使之更为准确。

著者

第1章 模式识别概述

本章要点：模式识别的基本概念特征空间优化设计问题分类器设计聚类设计模式识别的应用

1.1 模式识别的基本概念

模式识别（Pattern Recognition）就是机器识别、计算机识别或机器自动识别，目的在于让机器自动识别事物。例如，手写数字的识别，结果就是将手写的数字分到具体的数字类别中；智能交通管理系统的识别，就是判断是否有汽车闯红灯，闯红灯的汽车车牌号码；还有文字识别、语音识别、图像中物体识别，等等。该学科研究的内容是使机器能做以前只能由人类才能做的事，具备人所具有的对各种事物与现象进行分析、描述与判断的部分能力。模式识别是直观的、无处不在的，实际上人类在日常生活的每个环节，都从事着模式识别的活动。人和动物较容易做到模式识别，但对机器来说却是非常困难的。让机器能识别、分类，就需要研究识别的方法，这就是这门学科的任务。

模式识别研究的目的是利用计算机对物理对象进行分类，在错误概率最小的条件下，使识别的结果尽量与客观物体相符合。机器辨别事物最基本的方法是计算，原则上讲是对计算机要分析的事物与标准模板的相似程度进行计算。例如，要识别一个手写的数字，就要将它与从0～9的模板做比较，看跟哪个模板最相似，或最接近。因此首先要能从度量中看出不同事物之间的差异，才能分辨当前要识别的事物，因此最关键的是找到有效地度量不同类事物的差异的方法。

在模式识别学科中，就“模式”与“模式类”而言，模式类是一类事物的代表，而“模式”则是某一事物的具体体现，例如，数字0、1、2、3、4、5、6、7、8、9是模式类，而用户任意手写的一个数字或任意一个印刷数字则是“模式”，是数字的具体化。

1.模式的描述方法

在模式识别技术中，被观测的每个对象称为样品，例如，在手写数字识别中，每个手写数字可以作为一个样品，如果共写了N个数字，我们把这N个数字叫做N个样品（X，X，…，X，…，X），其中012jN表示有N个样品，1表示有N个样品，2表示有N个样品，3表示有N0123个样品，……，一共有ω，ω，…，ω（M=10）个不同的类别。12M

对于一个样品来说，必须确定一些与识别有关的因素，作为研究的根据，每一个因素称为一个特征。模式就是样品所具有特征的描述。模式的特征集又可用处于同一个特征空间的特征向量表示。特征向量的每个元素称为特征，该向量也因此称为特征向量，一般我们用小写英文字母x，y，z来表示特征。如果一个样品X有n个特征，则可把X看做一个n维列向量，该向量X称为特征向量，记做

若有一批样品共有N个，每个样品有n个特征，这些数值可以构成一个n行N列的矩阵，称为原始资料矩阵，如表1-1所示。表1-1 原始资料矩阵

模式识别问题就是根据X的n个特征来判别模式X属于ω，ω，…，12ω类中的哪一类。待识别的不同模式都在同一特征空间中考察，不M同模式类由于性质上的不同，它们在各特征取值范围内有所不同，因而会在特征空间的不同区域中出现。要记住向量的运算是建立在各个分量基础之上的。

因此，模式识别系统的目标是在特征空间和解释空间之间找到一种映射关系。特征空间由从模式得到的对分类有用的度量、属性或基元构成的空间。解释空间由M个所属类别的集合构成。

如果一个对象的特征观测值为｛x，x，…，x｝，它可构成一12n个n维的特征向量值X，即T

X=（x，x，…，x）12n

式中，x，x，…，x为特征向量X的各个分量。12n

一个模式可以看做n维空间中的向量或点，此空间称为模式的特n征空间R。在模式识别过程中，要对许多具体对象进行测量，以获得许多观测值，其中有均值、方差、协方差与协方差矩阵等。

2.模式识别系统

一个典型的模式识别系统如图1-1所示，由数据获取、预处理、特征提取、分类决策及分类器设计五部分组成。一般分为上下两部分：上半部分完成未知类别模式的分类；下半部分属于分类器设计的训练过程，利用样品进行训练，确定分类器的具体参数，完成分类器的设计。而分类决策在识别过程中起作用，对待识别的样品进行分类决策。图1-1 模式识别系统及识别过程

模式识别系统组成单元功能如下。（1）数据获取

用计算机可以运算的符号来表示所研究的对象，一般获取的数据类型有以下几种。

① 二维图像：文字、指纹、地图、照片等。

② 一维波形：脑电图、心电图、季节震动波形等。

③ 物理参量和逻辑值：体温、化验数据、参量正常与否的描述。（2）预处理

对输入测量仪器或其他因素所造成的退化现象进行复原、去噪声，提取有用信息。（3）特征提取和选择

对原始数据进行变换，得到最能反映分类本质的特征。将维数较高的测量空间（原始数据组成的空间）转变为维数较低的特征空间（分类识别赖以进行的空间）。（4）分类决策

在特征空间中用模式识别方法把被识别对象归为某一类别。（5）分类器设计

基本做法是在样品训练集基础上确定判别函数，改进判别函数和误差检验。

研究模式识别的主要目的是利用计算机进行模式识别，并对样本进行分类。执行模式识别的计算机系统称为模式识别系统。设计人员按需要设计模式识别系统，而该系统被用来执行模式分类的具体任务。

3.统计模式识别研究的主要问题

统计模式识别主要研究的问题有：特征的选择与优化、分类判别、聚类判别。（1）特征的选择与优化

如何确定合适的特征空间是设计模式识别系统一个十分重要的问题，对特征空间进行优化有两种基本方法。一种是特征选择，如果所选用的特征空间能使同类物体分布具有紧致性，可以为分类器设计成功提供良好的基础；反之，如果不同类别的样品在该特征空间中混杂在一起，再好的设计方法也无法提高分类器的准确性。另一种是特征的组合优化，通过一种映射变换改造原特征空间，构造一个新的精简的特征空间。（2）分类判别

已知若干个样品的类别以及特征，例如，手写阿拉伯数字的判别是10个类的分类问题，机器首先要知道每个手写数字的形状特征，对同一个数字，不同的人有不同的写法，甚至同一个人对同一个数字也有多种写法，就必须让机器知道它属于哪一类。因此对分类问题需要建立样品库。根据这些样品库建立判别分类函数，这一过程由机器来实现，称为学习过程，然后对一个未知的新对象分析它的特征，决定它属于哪一类。这是一种监督学习的方法。（3）聚类判别

已知若干对象和它们的特征，但不知道每个对象属于哪一个类，而且事先并不知道究竟分成多少类，用某种相似性度量的方法，即“物以类聚，人以群分”，把特征相同的归为一类。例如，手写了若干个阿拉伯数字，把相同的数字归为一类。这是一种非监督学习的方法。

机器识别也往往借鉴人的思维活动，像人类一样找出待识别物的外形或颜色等特征，进行分析、判断，然后加以分门别类，即识别它们。模式识别的方法很多，很难将其全部概括，也很难说哪种方法最佳，常常需要根据实际情况运用多种方法进行实验，然后选择最佳的分类方法。

1.2 特征空间优化设计问题

如何确定合适的特征空间是设计模式识别系统中一个十分重要，甚至更为关键的问题。如果所选用的特征空间能使同类物体分布具有紧致性，即各类样本能分布在该特征空间中彼此分割开的区域内，这就为分类器设计成功提供良好的基础。反之，如果不同类别的样本在该特征空间中混杂在一起，再好的设计方法也无法提高分类器的准确性。

在已有了特征的描述方法之后，也就是已有了一个初始的特征空间，需要对它进行改造，改造目的在于提高其某方面的性能，因此又称特征的优化问题。一般来说，对初始的特征空间进行优化就是为了降维，即初始的特征空间维数较高，能否改成一个维数较低的空间。优化后的特征空间应该更有利于后续的分类计算。对特征空间进行优化有两种基本方法：一种是特征选择，另一种是特征的组合优化。特征选择就是对原特征空间进行筛选，筛选掉一些次要的特征，构造出一个新的精简的特征空间，涉及对要识别的事物用什么方法进行描述和分析的问题；而特征的组合优化通过一种映射变换改造原特征空间，也就是说，新的每一个特征是原有特征的一个函数，使用变换的手段，在这里主要限定在线性变换的方法上，通过变换来实现降维。

1.特征选择

在模式识别中特征选择是一个重要问题，直接从样品得到的数据量往往是相当大的。例如，从一个图像中可以有几十万个数据，而一个卫星云图的数据量更多。为了对样品进行准确的识别，需要进行特征选择或特征压缩。特征选择指对原始数据进行抽取，抽取那些对区别不同类别最为重要的特征，而舍去那些对分类并无多大贡献的特征，得到能反映分类本质的特征。如果把区别不同类别的特征都从输入数据中找到，这时自动模式识别问题就简化为匹配和查表，模式识别就简单多了。对一个模式类特征选择得好与坏，很难在事先完全预测，而只能针对从整个分类识别系统获得的分类结果给予评价。

对分类器设计来说，使用什么样的特征描述事物，也就是说，使用什么样的特征空间是个很重要的问题。颜色指标对区分红灯与绿灯很有效。因为前者是红色，后者是绿色，用这个指标上的差异很容易将红灯与绿灯区分开。但是如果用颜色指标区别人脸就会困难得多。换句话说，在这种情况下，这个指标就不太有效了。

特征的选择常常面临着保留哪些描述量，删除哪些描述量，通常要经过从多到少的过程，因为在设计识别方案的初期阶段，应该尽量多地列举出各种可能与分类有关的特征，这样可以充分利用各种有用的信息，改善分类效果。但大量的特征中肯定会包含许多彼此相关的因素，造成特征的重复和浪费，给计算带来困难。Kanal.L曾经总结过经验：样品数N与特征数n之比应足够大，通常样本数N是特征数n的5～10倍。为了使特征数从多变少，需要进行特征选择，特征选择通常包括两方面内容：一方面是对单个特征的选择，即对每个特征分别进行评价，从中找出对识别作用最大的那些特征；另一方面是从大量的原有特征出发构造出少数的有效新特征，这种方法称为降维映射。

对一个具体问题来说，有以下两个不同的层次。（1）物理量的获取与转换

这是指用什么样的传感器获取电信号，对从传感器中得到的信号，可以称为原始信息，因为它要经过加工、处理才能得到对模式分类更加有用的信号，如摄取景物要用到摄像机。文字与数字识别首先要用扫描仪等设备。手写体文字所用传感器与印刷体文字也很可能不同。这些都属于物理量的获取，并且已转换成电信号，为计算机分析打下基础。（2）描述事物方法的选择与设计

在得到了原始信息之后，必须对原始信息进行加工，以获取对分类最有效的信息。设计所要信息的形式是十分关键的。例如，对数字的识别特征提取可以有多种方法，有的分析从框架的左边框到数字之间的距离变化反映了不同数字的不同形状，这可以用来作为数字分类的依据。另外一种方法是在每个数字图形上提取特征值，定义一个N×N模板，在本书实例程序中设定N=5，将每个样品的长度和宽度5等分，平均有25个等份，构成一个5×5模板。对每一份内的像素个数进行统计，再除以每一份的面积总数，即得特征初值，将特征初值大于20%所对应的模板置为1，取得该数字对应的特征。

对事物的描述方法是充分发挥设计者智慧的过程，这个层次的工作往往因事物而异，与设计者本人的知识结构也有关。这是一个目前还无法自动进行的过程。这个层次的工作是最关键的，但因为太缺乏共性，也不是本书讨论的内容。

2.特征优化

假设已有D维特征向量空间，Y=｛y，y，…，y｝，特征的组12D合优化问题涉及到特征选择和特征提取两部分。特征选择是指从原有的D维特征空间，删去一些特征描述量，从而得到精简后的特征空间。在这个特征空间中，样本由n维的特征向量描述：X=｛x，x，…，12x｝，n＜D。由于X只是Y的一个子集，因此每个分量x必然能在原特ni征集中找到其对应的描述量x=y。ij

特征优化则是找到一个映射关系：

A∶Y→X

使样本新特征描述维数比原维数低。其中每个分量x是原特征向i量各分量的函数，即

x=A（y，y，…，y）i12D

因此这两种降维的基本方法是不同的。在实际应用中可将两者结合起来使用，例如，先进行特征选择，指从原有的D维特征空间，删去一些特征描述量，从而得到精简后的特征空间，然后再进一步进行特征优化，或反过来操作。

要对原特征空间进行优化，就要对优化的结果进行评价，在实际应用中经常采用的评价方法是对系统性能进行测试。最主要的测试指标是识别正确率，其他指标还有识别计算速度、存储容量等。需要有定量分析比较的方法，判断所得到的特征维数及所使用特征是否对分类最有利，这种用以定量检验分类性能的准则称为类别可分离性判据。为此，人们设法从另一些更直观的方法出发，设计类别可分离性判据，用来检验不同的特征组合对分类性能好坏的影响，甚至用来导出特征选择与特征提取的方法。对特征空间进行优化是一种计算过程，它的基本方法仍然是模式识别的典型方法，即找到一种准则（或称判据），通常用一种式子表示，以及计算出一种优化方法，使这种计算准则达到一个极值。

总之，特征选择与特征优化的任务是求出一组对分类最有效的特征。有效是指在特征维数减少到同等水平时，其分类性能最佳。

1.3 分类器设计

模式识别分类问题是指根据待识别对象所呈现的观测值，将其分到某个类别中去。具体步骤是建立特征空间中的训练集，已知训练集里每个点所属的类别，从这些条件出发，寻求某种判别函数或判别准则，设计判决函数模型，然后根据训练集中的样品确定模型中的参数，便可将这模型用于判别，利用判别函数或判别准则去判别每个未知类别的点应该属于哪一个类。

如何做出合理的判决就是模式识别分类器要讨论的问题。在统计模式识别中，感兴趣的主要问题并不是决策正误，而在于如何使决策错误造成的分类误差在整个识别过程中的风险代价达到最小。模式识别算法的设计都是强调“最佳”与“最优”，即希望所设计的系统在性能上最优。这种最优是针对某一种设计原则讲的，这种原则称为准则，常用的准则有最小错误率准则、最小风险准则、近邻准则、Fisher准则、均方误差最小准则、感知准则等。设计准则，并使该准则达到最优的条件是设计模式识别系统最基本的方法。模式识别中以确定准则函数来实现优化的计算框架。分类器设计使用哪种原则是关键，会影响到分类器的效果。不同的决策规则反映了分类器设计者的不同考虑，对决策结果有不同的影响。分类决策在识别过程中起作用，对待识别的样品进行分类决策。

一般来说，M类不同的物体应该具有各不相同的属性值，在n维特征空间中，各自有不同的分布。当某一特征向量值X只为某一类物体所特有，对其做出决策是容易的，也不会出什么差错。问题在于常常会出现模棱两可的情况。由于属于不同类的待识别对象存在着呈现相同特征值的可能，即所观测到的某一样品的特征向量为X，而在M类中又有不止一类可能呈现这一X值，如图1-2所示，A、B直线之间的样品属于不同类别，但是它们具有相同的特征值。例如，癌症病人初期症状与正常人的症状相同，这两个类别样品分别用“-”与“+”表示。从图中可见这两类样品在二维特征空间中相互穿插，很难用简单的分界线将它们完全分开。如果用一直线作为分界线，称为线性分类器，将图中所示的样品分开，观察其分布情况，无论直线参数如何设计，总会有错分类发生。此时，任何决策都存在判错的可能性。图1-2 分界线示意图

模式识别的基本计算框架———制定准则函数，实现准则函数极值化。常用的准则有以下几种。（1）最小错分率准则

完全以减少分类错误为原则，这是一个通用原则，参见图1-2，如果以错分类最小为原则分类，则图中A直线可能是最佳的分界线，它使错分类的样品数量为最小。（2）最小风险准则

当接触到实际问题时，可以发现，使错误率最小并不一定是一个普遍适用的最佳选择。有的分类系统将错分率多少看成最重要的指标，如语音识别、文字识别；而有的分类系统对于错分率多少并不看重，而是要考虑错分类的不同后果，如对医疗诊断、地震、天气预报等。例如，可能多次将没有发生的地震预报成有地震，也有可能将发生的地震预报为没有地震，这类系统并不看重错分率，而是要考虑错分类引起的严重后果。又如，上面讨论过的细胞分类中，把正常细胞错分为癌细胞，或相反的错误，其严重性是截然不同的。以B直线划分，有可能把正常细胞误判为异常细胞，“+”样品错分成“-”类，给正常人带来不必要的痛苦，错分率多；但以A直线划分，有可能把癌细胞误判为正常细胞，“-”分成“+”类，会使病人因失去及早治疗的机会而遭受极大的损失，但错分率少。为使总的损失为最小，那么B直线就可能比A直线更适合作为分界线。这是基于最小风险的原理。

由此可见，根据不同性质的错误会引起不同程度的损失这一角度出发，我们宁肯扩大一些总的错误率，但也要使总的损失减少。因此引入风险、损失这些概念，以便在决策时兼顾不同后果产生的影响。在实际问题中计算损失与风险是复杂的，在使用数学式子计算时，往往用赋予不同权值来表示。在做出决策时，要考虑所承担的风险。基于最小风险的贝叶斯决策规则正是为了体现这一点而产生的。（3）近邻准则

近邻准则是分段线性判别函数的一种典型方法。这种方法主要依据同类物体在特征空间具有聚类特性的原理。同类物体由于其性质相近，它们在特征空间中应具有聚类的现象，因此可以利用这种性质产生分类决策的规则。例如，有两类样品，可以求出每一类的平均值，对于任何一个未知样品，先求出它到各个类的平均值距离，判断距离离哪个类近就属于哪个类。（4）Fisher准则

根据两类样品一般类内密集，类间分离的特点，寻找线性分类器最佳的法线向量方向，使两类样品在该方向上的投影满足类内尽可能密集，类间尽可能分开的原则，把它们投影到任意一根直线上，有可能不同类别的样品就混在一起了，无法区分，如图1-3（a）所示，投影到x或x轴无法区分。若把直线绕原点转动一下，就有可能找到一12个方向，样品投影到这个方向的直线上，各类样品就能很好地分开，如图1-3（b）所示。因此直线方向选择是很重要的。一般来说，总能够找到一个最好的方向，使样品投影到这个方向的直线上很容易分开。如何找到这个最好的直线方向以及如何实现向最好方向投影的变换，这正是Fisher算法要解决的基本问题。图1-3 Fisher线性判别原理示意图

这说明如果两类分布围绕各自均值的确相近，Fisher准则可使错误率较小，实际上Fisher方法涉及到维数压缩的问题。（5）感知准则

感知准则函数以使错分类样品到分界面距离之和最小为原则。提出利用错误提供信息实现迭代修正的学习原理，即利用错分类提供信息修正错误。这种思想对机器学习的发展以及人工神经元网络的发生发展产生深远影响，其优点是通过错分类样品提供的信息对分类器函数进行修正，这种准则是人工神经元网络多层感知器的基础。（6）最小均方误差准则

LMSE算法以最小均方误差作为准则。1.3.1 分类器设计基本方法

在n维特征空间已经确定的前提下，讨论的分类器设计问题是一个选择什么准则、使用什么方法，将已确定的n维特征空间划分成决策域的问题。模式识别有多种方法：模板匹配法、判别函数法、神经网络分类法、基于规则推理法，等等。

1.模板匹配

将待分类样品与标准模板进行比较，看跟哪个模板匹配程度更好些，从而确定待测试样品的分类。而近邻法则在原理上属于模板匹配。它将训练样品集中的每个样品都作为模板，用测试样品与每个模板做比较，看与哪个模板最近似（即为近邻），就按最近似的模板的类别作为自己的类别。例如，A类有10个训练样品，因此有10个模板，B类有8个训练样品，就有8个模板。任何一个待测试样品在分类时，先与这18个模板都计算一下相似度，如果最相似的那个近邻是B类中的一个，就确定待测试样品为B类，否则为A类。因此原则上说近邻法是最简单的。但是近邻法有一个明显的缺点就是计算量大，存储量大，要存储的模板很多，每个测试样品都要对每个模板计算一次相似度，因此在模板数量很大时，计算量也很大。

2.判别函数

设计判别函数的形式有两种方法：基于概率统计的分类法和判别函数分类法。（1）基于概率统计的分类法

基于概率统计的分类法主要有基于最小错误率的贝叶斯决策、基于最小风险的贝叶斯决策。直接使用贝叶斯决策需要首先得到有关样品总体分布的知识，包括各类先验概率P（ω）及类条件概率密度函1数，计算出样品的后验概率P（ω|X），并以此作为产生判别函数的1必要数据，设计出相应的判别函数与决策面。当各类样品近似于正态分布时，可以算出使错误率最小或风险最小的分界面，及相应的分界面方程。因此，如果能从训练样品估计出各类样品服从近似的正态分布，可以按贝叶斯决策方法对分类器进行设计。

这种利用训练样品的方法是通过它的概率分布进行估计，然后用它进行分类器设计，这种方法称为参数判别方法。它的前提是对特征空间中的各类样品的分布已很清楚，一旦要测试分类样品的特征向量值X已知，就可以确定X对各类的后验概率，也就可以按相应的准则计算和分类。所以判别函数等的确定取决于样品统计分布的有关知识。因此参数分类判别方法一般只能用在有统计知识的场合，或能利用训练样品估计出参数的场合。

贝叶斯分类器可以用一般的形式给出数学上严格的分析证明：在给出某些变量的条件下，能使分类所造成的平均损失最小，或分类决策的风险最小。因此能计算出分类器的极限性能。贝叶斯决策采用分类器中最重要的指标———错误率作为产生判别函数和决策面的依据，因此它给出了最一般情况下适用的“最优”分类器设计方法，对各种不同的分类器设计技术在理论上都有指导意义。（2）判别函数分类法

由于一个模式通过某种变换映射为一个特征向量后，该特征向量可以理解为特征空间的一个点，在特征空间中，属于一个类的点集，总是在某种程度上与属于另一个类的点集相分离，各个类之间确定可分，因此如果能够找到一个判别函数（线性或非线性函数），把不同类的点集分开，则分类任务就解决了。判别分类器不依赖于条件概率密度的知识，可以理解为通过几何的方法，把特征空间分解为对应于不同类别的子空间。而且呈线性的分离函数可以简化计算。分离函数又分为线性判别函数和非线性判别函数。

3.神经网络分类

神经网络可以看成是从输入空间到输出空间的一个非线性映射，它通过调整权重和阈值来“学习”或发现变量间的关系，实现对事物的分类。由于神经网络是一种对数据分布无任何要求的非线性技术，它能有效解决非正态分布、非线性的评价问题，因而受到广泛的应用。由于神经网络具有信息的分布存储，并行处理以及自学习能力等特点，它在泛化处理能力上显示出较高的优势。

4.基于规则推理法

通过样本训练集构建推理规则进行模式分类的方法主要有：决策树和粗糙集理论。决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的实例中推理出决策树表示形式的分类规则。决策树整体为一棵倒长的树，分类时，它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，并根据不同属性判断从该结点向下的分支，在决策树的叶结点得到结论。粗糙集理论反映了认知过程在非确定、非模型信息处理方面的机制和特点，是一种有效的非单调推理工具。粗糙集以等价关系为基础，用上、下近似两个集合来逼近任意一个集合，该集合的边界区域被定义为上近似集和下近似集之差集，边界区域就是那些无法归属的个体。上、下近似两个集合可以通过等价关系给出确定的描述，边界区域的元素数目可以被计算出来。

这两个理论在数据的决策和分析、模式识别、机器学习与知识发展等方面有着成功的应用，已成为信息科学最活跃的研究领域之一。1.3.2 判别函数

无论应用概率统计的分类法还是应用几何分类法，最终都转化为确定判别函数形式。

1.二类情况

对于只有简单的两类情况，判别函数形式如图1-4所示，根据计算结果的符号将X分类。图1-4 两类分类器形式

这里首先假定判别函数d（X）是X的线性函数：T

d（X）=WX+W0（1）二维特征

在二维模式空间中存在一线性判别函数：（2）n维特征T

用矢量X=（x，x，…，x）来表示模式，一般的线性判别函12n数形式为T

式中，W=（w，w，…，w）称为权矢量或参数矢量。如果012n在所有模式矢量的最末元素后再附加元素1，则式（1-2）可以写成

W=（w，w，…，w，w）。12nn+1

2.多类情况

对于多类别问题，假设有M类模式ω，ω，…，ω，对于n维空12M间中的M个类别，就要给出 M个判别函数：d（X），d（X），…，12d（X），各个判别函数构成的分类器基本形式如图1-5所示。若X属M于第i类，则有图1-5 判别函数构成的多类分类器形式

特殊情况，有

这时，在两类的分界线上，X既属于第i类，也属于第j类，因此这种判别无效，还必须考虑其他特征，重新判别。

判别函数的自变量是待测样品X的n个特征值，将待测样品X的n个特征值分别代入M个判别函数中，计算出各个函数表达式的结果，哪一个最大，待测样品X就属于哪一个类。M个判别函数一般表示成d（X），如果d（X）=，则称特征空间的这一点X属于ii第i类的决策域。由d（X）占主导地位的区域称为第i类的决策域，将i它表示成R，如果第i类决策域R与第j类决策域相邻，则它们之间有ii边界。在边界上有d（X）=d（X），该式是一个方程式，称为决策面ij方程。决策面是一种统称，当特征空间只是一维时，一个决策面实际上只是一个点。在二维特征空间里，决策面是一条曲线。三维则是一曲面，超过三维的空间，决策面是一个超曲面。判别函数d（X）用i于表达决策规则的某些函数。判别函数d（X）与决策面方程d（X）ii=d（X）是密切相关的，并且都是由相应决策规则所确定的。j

对于线性情况，判别函数形式为TT

其中，X=（x，x，…，x，1），W=（w，w，…，w）12n12n+1

对于非线性情况，判别函数形式为

3.参数的确定

由于决策域的分界面是用数学式子来描述的，如线性函数、各种非线性函数等。因此确定分界面方程包括选择函数类型与确定最佳参数两个部分。一般来说，选择函数类型是由设计者确定的，但其参数的确定则是通过一个学习过程来实现的，是一个迭代实现优化的过程。

由此可见设计分类器，一是选定所用的判别函数类型，二是确定方程的两个参数（权向量W，阈值w）。对于线性判别函数来说，n+1方程的形式固定为线性，维数固定为特征向量的维数，方程组的数量取决于待识别对象的类数。既然方程组的数量、维数和形式已定，则对判别函数的设计就是确定函数的各系数，即线性方程的各个权值。确定线性方程的各个权值的方法有Fisher准则、感知器算法、增量校正算法、LMSE算法等。

线性分类器设计任务是在给定样品集和集合内各样品所属类别条件下，确定线性判别函数的各项系数，对待测样品进行分类时，能满足相应的准则函数J为最优的要求。这种方法的具体运算过程如下：

① 确定使用的判别函数类型或决策面方程类型，如线性分类器、分段线性分类器、非线性分类器或近邻法等。

② 按需要确定一准则函数J，如Fisher算法、感知器算法、增量校正算法、LMSE算法。增量校正算法与感知器算法的实现相似，只是在进行权矢量修正时加上了权系数；LMSE算法以最小均方误差作为准则。*

③ 确定准则函数J达到极值时W的具体数值，从而确定判别函数，完成分类器设计。在计算机上确定各权值时采用“训练”或“学习”的方法，就是挑选一批已分类的样品，把这批样品输入到计算机的“训练”程序中去，通过多次迭代，最后准则函数J达到极值，得到正确的线性判别函数。

这种方法绕过统计分布状况的分析，绕过参数估计这一环，而试图对特征空间实行划分，称为非参数判别分类法，即不依赖统计参数的分类法。非参数判别分类方法的核心是由训练样品集提供的信息直接确定决策域。线性判别函数法是一类较为简单的判别函数方法，计算量少，它以模式的样品集线性可分离为前提。1.3.3 分类器的选择

在讨论了判别函数等概念后，设计分类器的任务就清楚了。根据样品分布情况来确定分类器的类型。在设计分类器的方法时，要有一个样品集，样品集中的样品用一个各分量含义已经确定的向量来描述，这也就是说，对要分类的样品怎样描述是已经确定的。在这种条件下研究用贝叶斯分类器、线性分类器与非线性分类器等，以及这些分类器的其他设计问题。

按照基于统计参数的决策分类方法，判别函数及决策面方程的类别确定是由样品分布规律决定的，贝叶斯决策是基于统计分布确定的情况下计算的，如果要按贝叶斯决策方法设计分类器，就必须设法获得必需的统计参数。如果有条件得到准确的统计分布知识，具体说来包括各类先验概率P（ω）及类条件概率密度函数，即可计算出样品1的后验概率P（ω|X），并以此作为产生判别函数的必要依据，利用1贝叶斯决策来实现对样品的分类。但是在这些参数未知的情况下使用贝叶斯决策方法，就得有一个学习阶段。在这个阶段，设法获得一定数量的样品，然后从这些样品数据中获得对样品概率分布的估计。有了概率分布的估计后，才能对未知的新样品按贝叶斯决策方法实行分类。

在一般情况下要得到准确的统计分布知识是极其困难的事。当实际问题中并不具备获取准确统计分布的条件时，使用几何分类器。几何分类器设计过程主要是判别函数、决策面方程的确定过程。设计分类器首先要确定准则函数，然后再利用训练样品集确定该分类器的参数，以求使所确定的准则达到最佳。在使用分类器时，样品的分类由其判别函数值决定。判别函数可以是线性函数、也可以设计成非线性函数。设特征向量的特征分量数目为n，可分类数目为M，符合某种条件就可使用线性分类器，正态分布条件下一般适合使用二次函数决策面。

① 若可分类数目M=2（n+1）≈2n，则几乎无法用一个线性函数分类器将它们分成两类。

②在模式识别中，理论上，M＞n+1的线性分类器不能应用，但是如果一个类别的特征向量在空间中密集地聚集在一起，几乎不和其他类别的特征向量混合在一起，则无论M多大，线性分类器的效果总是良好的。在字符识别机中，线性函数分类器已经证明能够提供良好的识别效果，它能识别数量很大的字符识别任务。

因此，在手写数字识别中，只要读者规范书写数字，不同数字类别的特征空间可以看成彼此分离的，而同一类别的数字在特征空间中类集群性质较好，应用线性分类器是可行的。相反，如果特征向量的类集群性质不好，则线性分类器的效果总是不理想，此时，必须求助于非线性分类器。1.3.4 训练与学习

所谓模式识别中的学习与训练是从训练样品提供的数据中找出某种数学式子的最优解，这个最优解使分类器得到一组参数，按这种参数设计的分类器使人们设计的某种准则达到极值。确定分类决策的具体数学公式是通过分类器设计确定的。在模式识别学科中一般把这个过程称为训练与学习的过程。

分类的规则是依据训练样品提供信息确定的。分类器设计在训练过程中完成，利用一批训练样品，包括各种类别的样品，由这些样品大致勾画出各类事物在特征空间分布的规律性，为确定使用什么样的数学公式并为这些公式中的参数提供信息。一般来说，决定使用什么类型的分类函数是人为决定的。分类参数的选择或者在学习过程得到的结果取决于设计者选择什么样的准则函数。不同准则函数的最优解对应不同的学习结果，得到性能不同的分类器。数学式子中的参数则往往通过学习来确定，分类器有一种学习过程，如果发现当前采用的分类函数会造成分类错误，那么利用错误提供的纠正信息，就可以使分类函数朝正确的方向前进，这就形成了一种迭代的过程，如果分类函数及其参数使出错的情况越来越少，就可以说逐渐收敛，学习过程就收到了效果，设计也就可以结束。

训练与学习的过程常常用到以下三个概念。（1）训练集

训练集是一个已知样品集，在监督学习方法中，用它来开发模式分类器。

在分类实例中，样品库训练集是程序开发人员按照自己的手写数字习惯来书写的数字，因此，会造成对读者手写的数字分类有误的情况，为了尽量避免此类情况发生，我们把每次添加的手写数字放在样品训练集的首位，读者可以尽量多写一些数字以使程序适应书写样式。（2）测试集

测试集是指在设计识别和分类系统时没有用过的独立样品集。

在分类实例中，以读者自己手写的数字作为测试检验，每写一个可以用各种模式识别算法进行检验。这样的好处是在相同的样品特征值下，可以对不同的模式识别算法进行比较，找出最佳适应算法。（3）系统评价原则

系统评价原则就是判断该模式识别系统能否正确分类，为了更好地对模式识别系统性能进行评价，必须使用一组独立于训练集的测试集对系统进行测试。

1.4 聚类设计

前面介绍的分类问题是利用已知类别的样品训练集来构造分类器的。其训练集样品是已知类别的，所以又称为有监督学习或有教师分类，在已知类别样品的“指导”监督下对单个待测样品进行分类。聚类问题则不同，它事先不了解一批样品中的每一个样品的类别或者其他的先验知识，而唯一的分类根据是样品的特性，利用样品的特性来构造分类器。这种分类称为无监督分类，通常叫做聚类或集群。

聚类分析就是对探测数据进行分类分析的一个工具，许多学科要根据所测得的或感知到的相似性对数据进行分类，把探测数据归入到各个聚合类中，且在同一个聚合类中的模式比不同聚合类中的模式更相似，从而对模式间的相互关系做出估计。聚类分析的结果可以被用来对数据提出初始假设，分类新数据，测试数据的同类型及压缩数据。

聚类算法的重点是寻找特征相似的聚合类。人类是二维的最佳分类器，然而大多数实际的问题涉及高维的聚类。对高维空间内的数据的直观解释，其困难是显而易见的，另外，数据也不会服从规则理想分布，这就是有大量聚类算法出现在文献中的原因。

1.聚类的定义

Evertt提出一个聚合类是一些相似的实体集合，而且不同聚合类的实体是不相似的。在一个聚合类内的两个点间的距离小于在这个类内任一点和不在这个类内的另一点间的距离。聚合类可以被描述成在n维空间内，存在较高密度点的连续区域和较低密度点的区域，而较低密度点的区域把其他较高密度点的区域分开。

在模式空间S中，若给定N个样品X，X，…，X，聚类的定义12N是：按照相互类似的程度找到相应的区域R，R，…，R，对任意12MX（i=1，2，…，N）归入其中一类，而且不会同时属于两类，即i

R∪R∪…∪R=R12M

选择聚类的方法应以一个理想的聚类概念为基础。然而，如果数据不满足由聚类技术所做的假设，则算法不是去发现真实的结构而是在数据上强加某种结构。

2.聚类准则

设有未知类别的N个样品，要把它们划分到M类中去，可以有多种优劣不同的聚类方法；怎样评价聚类的优劣，这就需要确定一种聚类准则。但客观地说，聚类的优劣是就某一种评价准则而言的，很难有对各种准则均呈优良表现的聚类方法。

聚类准则的确定，基本上有两种方法。一种是凭经验，根据所分类的问题，确定一种准则，并用它来判断样品分类是否合理。例如，以距离函数作为相似性的度量，用不断修改的阈值来探究对此种准则的满足程度。另一种是规定一种准则函数，其函数值与样品的划分有关，当取得极小值时，就认为得到了最佳划分。下面给出一种简单而又广泛应用的准则，即误差平方和准则：

设有N个样品，分属于ω，ω，…，ω类，设有N个样品的ω类，12Mii其均值为

因为有若干种方法可将N个样品划分到M类中去，因此对应一种划分，可求得一个误差平方和J，要找到使J值最小的那种划分。定义误差平方和

经验表明，当各类样品均很密集，各类样品个数相差不大，而类间距离较大时，适合采用误差平方和准则，如图1-6（a）所示。若各类样品数相差很大，类间距离较小时，就有可能将样品数多的类一分为二，而得到的J值却比大类保持完整时小，误以为得到了最优划分，实际上得到了错误的划分，如图1-6（b）所示。图1-6 样品分布与误差平方和准则关系

1.5 模式识别的应用

模式识别已经广泛应用于文字识别、语音识别、指纹识别、遥感、医学诊断、工业产品检测、天气预报、卫星航空图片解释等领域。近年来，用模式识别方法发展起来的“模式识别优化技术”在化工、冶金、石化、轻工等领域用于配方、工艺过程的优化设计和优化控制，产生了巨大的经济效益。在节约原料、提高产品质量和产量、降低单位能耗等方面充分显示了这一高新技术的巨大潜力。模式识别技术除了可以对配方、工艺进行优化设计外，还可以用于工业过程控制，这就是模式识别智能控制优化专家系统。它的特别之处在于可以根据目标（如降低能耗、提高产量等）优化影响目标的参量（如原料的组成、工艺参数等），在众多影响参量中筛选出对目标具有较重要影响的参量。经过模式分类、网络训练，确定优化区域，找出优化方向，动态建立模型，定量预报结果，使生产操作条件始终保持在优化状态，尽可能地挖掘生产潜力，在现代化工业（包括化工、冶金、轻工、建材等）中有广阔的应用前景。

所有这些应用都是和问题的性质密不可分的，至今还没有发展成统一的、有效的可以应用于所有模式识别的理论。当前的一种普遍看法是：不存在对所有的模式识别问题都适用的单一模型和解决识别问题的单一技术，我们现在拥有的是一个工具袋，我们所要做的是结合具体问题把模式识别方法结合起来，把模式识别与人工智能中的启发式搜索结合起来，把人工神经元网络、不确定方法、智能计算结合起来，深入掌握各种工具的效能和应用的可能性，互相取长补短，开创模式识别应用的新局面。

模式识别技术是人工智能的基础技术。21世纪是智能化、信息化、计算化、网络化的世纪，在这个以数字计算为特征的世纪里，作为人工智能技术基础学科的模式识别技术，必将获得巨大的发展空间。

本章小结

假定有一批待识别的事物，事先也不知道相关的先验知识，即不知道它们属于哪种类别，满足哪种分布，在这种情况下我们对这批事物分类的方法就是按照它们特征之间的相似性，将有相同或相似特征的事物聚集在一起。也就是说，我们最后的分类结果中每一类聚集的物体都有共同的特征，这种不知所属类别而是根据事物相似性的程度分类的方法称为聚类。例如，手写了15个数字（0，2，3，0，0，2，3，2，2，0，3，3，3，2，0），通过模式识别会把它们归成（0，2，3）3个类，这种方法叫做非监督学习方法。如果给定了一批待识别的事物，而且还知道了某些事物的类别，根据已知事物特征及其类别判断未知事物的类别，这种问题称为分类问题。分类与聚类的不同点在于类数是确定的，而且已经知道了一批已经分类的事物。例如，数字有固定的类数（0～9），能够识别出手写数字为哪一类，这种方法叫做监督学习方法。

监督学习方法用来对数据实现分类，分类规则通过训练获得。该训练集由带分类号的数据集组成，因此监督学习方法的训练过程是离线的。非监督学习方法不需要单独的离线训练过程，也没有带分类号的训练数据集，一般用来对数据集进行聚类分析，确定其分布。

总之，分类与聚类的效果好坏，最基本的性能评估是其错误率；如果能采用反映错误率大小的准则，在理论上是最合适的。但是正如在前面讨论中提到的，对错误率的计算是极其复杂的，以至于很难构筑直接基于错误率的判据。而且分类与聚类效果还受所使用的训练样品集，以及所用的算法影响。通常需要靠实践来检验。

本章介绍了设计分类器需要考虑的基本问题，包括特征空间优化设计问题、分类器设计准则、分类器设计基本方法、判别函数、分类器的选择和训练与学习，还介绍了聚类判别所涉及的基本问题。这些都是模式识别需要考虑的重要内容，掌握这些内容为理解及实现后续各章所介绍的理论打下基础。

习题1

1.简述特征空间优化的方法。

2.简述几种常用的分类器设计准则。

3.简述分类器设计的基本方法。

4.试写出基于二维特征两类分类问题的线性判别函数形式。

5.试写出基于n维特征两类分类问题的线性判别函数形式。

6.试写出基于n维特征多类分类问题的线性判别函数形式。

7.试写出基于n维特征多类分类问题的非线性判别函数形式。

8.简述设计判别函数需要确定的基本要素。

9.简述在什么情况下分类器不可分。

10.简述设计一个分类器的基本方法。

第2章 特征的选择与优化

本章要点：特征空间优化设计问题样本特征库初步分析样品筛选处理特征筛选处理特征评估基于主成分分析的特征提取特征空间描述与分析手写数字特征提取与分析

在实际的应用中，信息采集的对象多数是多特征、高噪声、非线性的数据集。人们只能尽量多列一些可能有影响的因素，在样本数不是很多的情况下，用很多特征进行分类器设计，无论从计算的复杂程度还是就分类器性能来看都是不适宜的。因此，研究如何把高维特征空间压缩到低维特征空间就成为了一个重要的课题。任何识别过程的第一步，不论用计算机还是由人去识别，都要首先分析各种特征的有效性并选出最具有代表性的特征。

特征的选择与优化是非常重要的，它强烈地影响到分类器的设计及其性能。若对于不同类别样品特征的差别很大，那就比较容易设计出具有较高性能的分类器。因此，特征的选择是模式识别中的一个关键问题。由于在很多实际问题中常常不容易找到那些最重要的特征，或受条件限制不能对它们进行测量，这就使特征选择和优化的任务复杂化而成为构造模式识别系统最困难的任务之一。这个问题已经越来越受到人们的重视。

2.1 特征空间优化设计问题

特征选择和优化的基本任务是如何从许多特征中找出那些最有效的特征。解决特征选择和特征优化问题，最核心的内容就是如何对现有特征进行评估，以及如何通过现有特征产生更好的特征。在实际应用中，对特征选择与处理大致过程如图2-1所示。图2-1 特征选择与处理过程

特征选择与优化过程如下：（1）对样本特征库进行初步分析是指对原始数据进行抽取，抽取那些对区别不同类别最为重要的特征，而舍去那些对分类并无多大贡献的特征，从而得到能反映分类本质的特征。考查所选特征是否合理，能否实现分类。如果把区别不同类别的特征都从输入数据中找到，这时自动模式识别问题就简化为匹配和查表，模式识别就不困难了。（2）对样本筛选处理的目的是去掉“离群点”，减少这些“离群点”对分类器的干扰。当条件所限无法采集大量的训练样品时，应慎重对待离群点。样本在特征空间中的理想分布是同类相聚、异类远离，但是在现实中很难达到理想的分布状态，就要求分类器具有泛化。（3）特征筛选处理的目的是分析特征之间的相关性，考查每个

试读结束[说明：试读内容隐藏了图片]

下载完整电子书