1.3 分类器设计

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

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

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

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

（1）最小错分率准则

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

（2）最小风险准则

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

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

（3）近邻准则

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

（4）Fisher准则

根据两类样品一般类内密集，类间分离的特点，寻找线性分类器最佳的法线向量方向，使两类样品在该方向上的投影满足类内尽可能密集，类间尽可能分开的原则，把它们投影到任意一根直线上，有可能不同类别的样品就混在一起了，无法区分，如图1-3（a）所示，投影到x1或x2轴无法区分。若把直线绕原点转动一下，就有可能找到一个方向，样品投影到这个方向的直线上，各类样品就能很好地分开，如图1-3（b）所示。因此直线方向选择是很重要的。一般来说，总能够找到一个最好的方向，使样品投影到这个方向的直线上很容易分开。如何找到这个最好的直线方向以及如何实现向最好方向投影的变换，这正是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（ω1｜X），并以此作为产生判别函数的必要数据，设计出相应的判别函数与决策面。当各类样品近似于正态分布时，可以算出使错误率最小或风险最小的分界面，及相应的分界面方程。因此，如果能从训练样品估计出各类样品服从近似的正态分布，可以按贝叶斯决策方法对分类器进行设计。

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

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

（2）判别函数分类法

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

3.神经网络分类

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

4.基于规则推理法

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

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

1.3.2 判别函数

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

1.二类情况

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

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

d（X）=WTX+W0

（1）二维特征

在二维模式空间中存在一线性判别函数：

d（X）=w1x1+w2x2+w3=0 （1-1）

（2）n维特征

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

d（X）=w1x1+w2x2+…+wnxn+wn+1=WT0X+wn+1 （1-2）

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

d（X）=WTX （1-3）

W=（w1，w2，…，wn，wn+1）。

2.多类情况

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

di（X）＞dj（X） j=1，2，…，M i≠j （1-4）

特殊情况，有

di（X）=dj（X） （1-5）

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

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

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

d（X）=w1x1+w2x2+…+wnxn+wn+1

=WT0X+wn+1=WTX （1-6）

其中，X=（x1，x2，…，xn，1）T，W=（w1，w2，…，wn+1）T

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

3.参数的确定

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

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

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

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

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

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

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

1.3.3 分类器的选择

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

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

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

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

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

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

1.3.4 训练与学习

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

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

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

（1）训练集

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

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

（2）测试集

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

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

（3）系统评价原则

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