《模式识别与机器学习》课程笔记：第3章 判别函数

第3章 判别函数

线性判别函数

模式识别系统的主要作用：判别各个模式（也称样本）所属的类别

模式分类若可用任一个线性函数来划分，则这些模式就称为线性可分的，否则就是非线性可分的。

一旦线性函数的系数被确定，这些函数就可用作模式分类的基础。

对一个两类问题的判别，就是将模式划分成和两类

这两类可以通过一个直线方程来划分

若，则，若，则

称为决策面/判别界面方程**（判别函数和判别界面是否等于0要注意）**

用判别函数进行模式分类依赖的两个因素：

• 判别函数的几何性质：线性的（一条直线）和非线性的函数（曲线、折线等）。
  • 线性判别函数建立起来比较简单（实际应用较多）；
  • 非线性判别函数建立起来比较复杂。
• 判别函数的形式确定后，主要就是确定判别函数的系数问题，只要被研究的模式是可分的，就能用给定的模式样本集来确定判别函数的系数。

一个维线性判别函数的一般形式：

权向量（参数向量）：

维线性判别函数也可以表示为

增广模式向量：，增广权向量：

多类情况1：用线性判别函数将属于类的模式与不属于类的模式分开，称为 两分法，即把类多类问题分成个两类问题，因此共有个判别函数。会存在分类失败的问题：

多类情况2：采用每对划分，即 两分法，此时一个判别界面只能分开两种类别，但不能把它与其余所有的界面分开。

判别函数为，若 ，则

因此要分开类模式，共需个判别函数。也会存在不确定区域，即分类失败。

多类情况1和多类情况2的比较

• 对于类模式的分类，多类情况1需要个判别函数，而多类情况2需个判别函数，当较大时，后者需要更多的判别式
• 采用多类情况1时，每一个判别函数都要把一种类别的模式与其余种类别的模式分开，而不是将一种类别的模式仅与另一种类别的模式分开。
• 由于一种模式的分布要比种模式的分布更为聚集，因此多类情况2对模式是线性可分的可能性比多类情况1更大一些。

多类情况3：没有不确定区域的 两分法

，此时，对类情况应有个判别函数。

广义线性判别函数

线性判别函数简单，容易实现，而非线性判别函数复杂，不容易实现。

若能将非线性判别函数转换为线性判别函数，则有利于模式分类的实现。

设有一个训练用的模式集，在模式空间中线性不可分，但在模式空间中线性可分，其中的各个分量是的单值实函数，的维数高于的维数，即若取，则分类界面在中是线性的，在中是非线性的，此时只要将模式进行非线性变换，使之变换后得到维数更高的模式，就可以用线性判别函数来进行分类。

一个非线性判别函数可如下表示：，其中是模式的单值实函数。

若定义成广义形式：

此时有：。其中

非线性判别函数已被变换成广义线性，因此只讨论线性判别函数不会失去一般性意义。

当是模式的二次多项式函数时：

式中各项的组成应包含的各个分量的二次项、一次项和常数项，其中平方项个，二次项个，一次项个，常数项1个，其总项数为：

若是模式的次多项式函数，总项数为

分段线性判别函数

• 线性判别函数在进行分类决策时是最简单有效的，但在实际应用中，常常会出现不能用线性判别函数直接进行分类的情况。
• 采用广义线性判别函数的概念，可以通过增加维数来得到线性判别，但维数的大量增加会使在低维空间里在解析和计算上行得通的方法在高维空间遇到困难，增加计算的复杂性。
• 引入分段线性判别函数的判别过程，它比一般的线性判别函数的错误率小，但又比非线性判别函数简单。

也就是说，可以使用一个二次判别函数进行分类的地方，也可以使用一个分段线性判别函数来逼近这个二次曲线。

可以采用最小距离分类的方法，只有在类别密集地分布在其均值附近时才有效。

对于各类交错分布的情况，若再用每类一个均值代表点产生最小距离分类器，就会产生很明显的错误率。在这种情况下，可以运用聚类方法将一些类分解成若干个子类，再用最小距离分类。

• 寻找交遇区—找到互为最小距离的原型对，组成“交遇区”。
• 用局部训练模式产生分段线性判别函数并迭代优化决策面。
• 撤走已分类正确的样本，从剩下的样本集合中，寻找交遇区，产生分段线性判别函数。

模式空间和权空间

模式空间：

对一个线性方程，它在三维空间中是一个平面方程式，是方程的系数。

把向量作为该平面的法线向量，则该线性方程决定的平面通过原点且与垂直

若是二维的增广向量，为非增广的权向量，它与直线AB垂直

模式空间即为增广向量决定的平面或非增广向量决定的直线。

权空间：

若将方程绘在权向量的三维空间中，则为方程的系数

Fisher线性判别

• 应用统计方法解决模式识别问题时，一再碰到的问题之一就是维数问题。
• 在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通。
• 因此，降低维数有时就会成为处理实际问题的关键。

问题描述：

• 考虑把维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。
• 然而，即使样本在维空间里形成若干紧凑的互相分得开的集群，当把它们投影到一条直线上时，也可能会是几类样本混在一起而变得无法识别。
• 但是，在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分得开。

Fisher判别方法所要解决的基本问题：如何根据实际情况找到一条最好的、最易于分类的投影线。

从维空间到一维空间的一般数学变换方法：

假设有一集合包含个维样本，其中个属于类的样本记为子集，个属于类的样本记为子集，若对的分量做线性组合可得标量：，这样便得到个一维样本组成的集合，并可分为两个子集和。

实际上，的值是无关紧要的，它仅是乘上一个比例因子，重要的是选择的方向。的方向不同，将使样本投影后的可分离程度不同，从而直接影响分类效果。因此，上述寻找最佳投影方向的问题，在数学上就是寻找最好的变换向量的问题。

Fisher准则函数中的基本参量：

在维空间：

各类样本的均值向量

样本类内离散度矩阵：

总样本类内离散度矩阵：（对称半正定矩阵）

样本类间离散度矩阵：（对称半正定矩阵）

在一维空间：

各类样本的均值：

样本类内离散度：

总样本类内离散度：

我们希望投影后，在一维空间中各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各类样本内部尽量密集，即希望类内离散度越小越好。

Fisher准则函数：将其推导为的显函数：

然后使用Lagrange乘数法求解，最终解得

事实上，Fisher的降维就相当于找一个线性判别函数。投影后的是变化得来的，就相当于线性判别。

多类情形：

类间散度矩阵与两类情形略有不同：原来度量的是两个均值点的散列情况，现在度量的是每类均值点相对于样本中心的散列情况

推导可得：

感知器算法

一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。在模式识别中，系数确定的一个主要方法就是通过对已知样本的训练和学习来得到。感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。

基本思想：采用感知器算法能通过对训练模式样本集的“学习”得到判别函数的系数。不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方法。

感知器作为人工神经网络中最基本的单元，由多个输入和一个输出组成。

已知两个训练模式集分别属于类和类，权向量的初始值为，可任意取值。

若，若

第次的训练步骤为：

若，则分类器对第个模式做了错误分类，此时应校正权向量，使得，其中为一个校正增量。

若，则分类器对第个模式做了错误分类，此时应校正权向量，使得，其中为一个校正增量。

若以上情况不符合，则表明该模式样本在第次中分类正确，因此权向量不变

• 对正确分类的模式则“赏”，实际上是“不罚”，即权向量不变。
• 对错误分类的模式则“罚”，使加上一个正比于的分量。
• 当用全部模式样本训练过一轮以后，只要有一个模式是判别错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。
• 如此不断反复直到全部模式样本进行训练都能得到正确的分类结果为止。

感知器算法的收敛性：只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。

采用感知器算法的多类模式的分类

采用多类情况3，将感知器算法推广到多类模式。

多类情况3：对类模式存在个判别函数，若, 则

设有种模式类别，若在训练过程的第次迭代时，一个属于类的模式样本送入分类器，则应先计算出个判别函数：。若的条件成立，则权向量不变，即

若其中第个权向量使得，则相应的权向量应做调整，即

其中是一个正常数。权向量的初始值可视情况任意选择。

这里的分类算法都是通过模式样本来确定判别函数的系数，但一个分类器的判断性能最终要受并未用于训练的那些未知样本来检验。要使一个分类器设计完善，必须采用有代表性的训练数据，它能够合理反映模式数据的整体。

要获得一个判别性能好的线性分类器，直观上训练样本越多越好，但实际上能收集到的样本数目会受到客观条件的限制，且过多的训练样本在训练阶段会使计算机需要较长的运算时间。一般来说，合适的样本数目可如下估计：若是模式的维数，令，则通常选用的训练样本数目约为的10~20倍。

感知器算法的解与初值的选择和迭代过程中误分类点的选择顺序有关。

可训练的确定性分类器的迭代算法

梯度法

设函数 是向量 的函数, 则 的梯度定义为

从导出的一般关系式，是一个正的比例因子（步长）

梯度是一个向量，它的最重要性质就是指出了函数在其自变量增加时最大增长率的方向。负梯度指出的最陡下降方向，利用这个性质可以设计一个迭代方案来寻找函数的最小值。

定义一个对错误分类敏感的准则函数。先任选一个初始权向量，计算准则函数的梯度，然后从出发，在最陡方向（梯度方向）上移动某一距离得到下一个权向量

C值的选择是很重要的。若C值太小，则收敛太慢；若C值太大，则搜索可能过头，引起发散。

固定增量的逐次调整算法

设取准则函数为：

则对的微分式：，其中

则由梯度法中和的关系有：

其中是训练模式样本，是指第次迭代。

若模式是线性可分的，选择合适的准则函数，算法就能给出解。若模式不是线性可分的，算法的结果就会来回摆动，得不到收敛。

最小平方误差(LMSE)算法

感知器算法只是当被分模式可用一个特定的判别界面分开时才收敛，在不可分情况下，只要计算程序不终止，它就始终不收敛。即使在模式可分的情况下，也很难事先算出达到收敛时所需要的迭代次数。这样，在模式分类过程中，有时候会出现一次又一次迭代却不见收敛的情况，白白浪费时间。为此需要知道：发生迟迟不见收敛的情况时，到底是由于收敛速度过慢造成的呢，还是由于所给的训练样本集不是线性可分造成的呢？

最小平方误差(LMSE)算法，除了对可分模式是收敛的以外，对于类别不可分的情况也能指出来。

求两类问题的解相当于求一组线性不等式的解，因此，若给出分别属于和的两个模式样本的训练样本集，即可求出其权向量的解。

设两类模式的训练样本总数为，写成增广形式，则有不等式组

H-K算法：

模式类别可分性的判别：

当不等式组有解时，该算法对收敛，可求得解。

• 若，即，有解。
• 若，此时隐含的条件，有解。若继续进行迭代，可使。
• 若的全部分量停止变为正值（但不是全部为零），表明该模式类别线性不可分。因此，若没有一个分量为正值，则不会再变化，所以不能求得解。

固定增量算法与LMSE算法的比较：

• 固定增量算法：实现相对简单，可直接引伸到多类模式的分类情况，但未提供模式线性可分的测试特征；
• LMSE算法：相对复杂，需要对求逆（维数高时求逆比较困难），但对两类情况，提供了线性可分的测试特征。

势函数法-一种确定性的非线性分类算法

用势函数的概念来确定判别函数和划分类别界面

基本思想：

• 假设要划分属于两种类别和的模式样本，这些样本可看成是分布在维模式空间中的点。
• 把属于的点比拟为某种能源点，在点上，电位达到峰值。
• 随着与该点距离的增大，电位分布迅速减小，即把样本附近空间点上的电位分布，看成是一个势函数。
• 对于属于的样本集群，其附近空间会形成一个“高地”，这些样本点所处的位置就是“山头”。
• 同理，用电位的几何分布来看待属于的模式样本，在其附近空间就形成“凹地”。
• 只要在两类电位分布之间选择合适的等高线，就可以认为是模式分类的判别函数。

判别函数的产生

模式分类的判别函数可由分布在模式空间中的许多样本向量的势函数产生。任意一个样本所产生的势函数以表征，则判别函数可由势函数序列来构成，序列中的这些势函数相应于在训练过程中输入机器的训练模式样本。在训练状态，模式样本逐个输入分类器，分类器就连续计算相应的势函数，在第步迭代时的积累位势决定于在该步前所有的单独势函数的累加。以表示积累位势函数，若加入的训练样本是错误分类，则积累函数需要修改，若是正确分类，则不变。

从势函数可以看出，积累位势起着判别函数的作用：

• 当属于时，；
• 当属于时，，则积累位势不做任何修改就可用作判别函数。

由于一个模式样本的错误分类可造成积累位势在训练时的变化，因此势函数算法提供了确定和两类判别函数的迭代过程。

判别函数表达式：取，则有

势函数的选择

选择势函数的条件：一般来说，若两个维向量和的函数同时满足下列三个条件，则可作为势函数。

• ，并且当且仅当时达到最大值；
• 当向量与的距离趋于无穷时，趋于零；
• 是光滑函数，且是与之间距离的单调下降函数。

第一类势函数：可用对称的有限多项式展开：

，在模式定义域内为正交函数集。

将这类势函数代入判别函数：，其中

因此，积累位势可写成，可用迭代式求得。

第二类势函数：选择双变量和的对称函数作为势函数，即，并且它可展开成无穷级数。

例如：

，是正常数

用第二类势函数，当训练样本维数和数目都较高时，需要计算和存储的指数项较多。

因为势函数由许多新项组成，因此有很强的分类能力。

决策树简介

决策树，或称多级分类器，是模式识别中进行分类的一种有效方法，对于多类或多峰分布问题，这种方法尤为方便。利用树分类器可以把一个复杂的多类别分类问题，转化为若干个简单的分类问题来解决。它不是企图用一种算法、一个决策规则去把多个类别一次分开，而是采用分级的形式，使分类问题逐步得到解决。

一般来讲，一个决策树由一个根节点，一组非终止节点和一些终止节点组成，可对标以各种类别标签，有时不同的终止节点上可以出现相同的类别标签。

如果用表示决策树，则一个决策树对应于特征空间的一种划分，它把特征空间分成若干个区域，在每个区域中，某类的样本占优势，因此可以标出该类样本的类别标签。

决策树的一种简单形式是二叉树，它是指除叶结点外，树的每个节点仅分为两个分支，即每个非终止节点都有且仅有两个子节点和。

二叉树结构分类器可以把一个复杂的多类别分类问题转化为多级多个两类问题来解决，在每个非终止节点都把样本集分成左右两个子集。分成的每一部分仍然可能包含多个类别的样本，可以把每一部分再分成两个子集，如此下去，直至分成的每一部分只包含同一类别的样本，或某一类样本占优势为止。

二叉树结构分类器概念简单、直观、便于解释，而且在各个节点上可以选择不同的特征和采用不同的决策规则，因此设计方法灵活多样，便于利用先验知识来获得一个较好的分类器。

在设计一个决策树时，主要应解决以下几个问题：

• 选择一个合适的树结构，即合理安排树的节点和分支；
• 确定在每个非终止节点上要使用的特征；
• 在每个非终止节点上选择合适的决策规则。

把一个多类别分类问题转化为两类问题的形式是多种多样的，因此，对应的二叉树的结构也是各不相同的。通常的目的是要找一个最优的决策树。一个性能良好的决策树结构应该具有小的错误率和低的决策代价。但是由于很难把错误率的解析表达式和树的结构联系起来，而且在每个节点上所采用的决策规则也仅仅是在该节点上所采用的特征观测值的函数，因此，即使每个节点上的性能都达到最优，也不能说整个决策树的性能达到最优。在实际问题中，人们往往提出其它一些优化准则，例如极小化整个树的节点数目，或从根节点到叶结点的最大路经长度，或从根节点到叶结点的平均路经长度等，然后采用动态规划的方法，力争设计出能满足某种准则的“最优”决策树。