4.1　线性判别函数

判别函数是直接用来对样本进行分类的准则函数，也称为判决函数或决策函数（Decision Function）[1]，用表示，它是用来描述决策规则的某种函数。

4.1.1　两类问题

类别数量为两类的线性判别函数的一般表达式为

式中，为常数，表示偏差量；x为d维特征向量，又称为样本向量；为权重向量。两个向量具体表示为

对于两类问题的线性分类器，采用下述决策规则，使，那么

方程定义了一个决策面或分界面，如图4-1所示。当特征空间是一维空间时，它是一个点；当特征空间是二维空间时，它是一条直线；当特征空间是三维空间时，它是一个平面；当特征空间是多维空间时，它是一个超平面。这样一个决策面将除自身之外的整个特征空间划分为和两个部分。对于两类问题来说，人们希望找到函数和相应的决策面，使得同一类别的所有样本都位于决策面的同一侧，而不同类别的样本应位于决策面的不同侧。如图4-1所示，属于第一类的所有样本都位于一侧，也称为正侧；属于第二类的所有样本都位于一侧，也称为负侧。当找到使所有样本都能被正确分类的函数后，该分类问题就解决了。要找到这样的函数，需要解决两个问题：一是要确定的函数类型，在本节，的函数形式是线性函数；二是要确定函数中所包含的参数。

假设和都在决策面上，那么有=0，即，由于在决策面上，而与决策面上的向量正交，因此是决策面的法向量。当样本特征向量在决策面两侧时，有和，的值可以看作样本特征向量到决策面的一种距离度量。设是在决策面上的射影向量，是到决策面的垂直距离，方向上的单位向量，是向量的长度，则可以表示为

将式（4-4）代入式（4-1）得到

根据图4-2容易得出原点到决策面的距离，即

样本x到决策面的距离为

也就是说，是样本x到决策面的欧几里得距离。在的特殊情况下，决策面经过原点，。若，则说明原点在决策面的正侧；若，则说明原点在决策面的负侧。总之，利用线性判别函数判决两类问题，就是用一个决策面把特征空间分成两个决策区域，决策面的方向由权重向量确定，位置由确定。

4.1.2　多类问题

实际应用中经常会遇到多类问题，如在手写数字识别中，有0～9这10个类别。解决多类问题有3种方法，前两种都是把多类问题转换为多个两类问题，通过多个两类分类器实现多个类别的分类；第三种是直接设计多类分类器。

第一种方法是“一对多”的做法，假设有c个类，共需要c−1个两类分类器就可以实现c个类的分类。这种做法可能会遇到以下两个问题。一是假如多类别中各类的训练样本数目相当，那么在构造一对多的两类分类器时将面临训练样本不均衡的问题，即两类训练样本的数目差别过大，样本数目过于不均衡会导致决策面发生偏差，造成错误分类发生在样本数小的那个类上。在实际应用时需要注意，如果出现类似情况，要对算法采取适当的修正措施。二是用c−1个线性分类器来实现c个类的分类，就是用c−1个决策面把样本所在的特征空间划分成c个区域，这种划分一般不会恰好得到c个区域，而是多出一些区域，在这些区域内的分类会有歧义，如图4-3中的阴影部分所示。用两个(c−1)决策面区别3个(c)类别，决策面1把类别一与其他类别分开，决策面2把类别二与其他类别分开，最后会多出一个区域。

第二种情况是对多类中的每两类构造一个分类器，将把类别一和类别二分开与把类别二和类别一分开考虑为一种情况，对于c个类别，需要个两类分类器。显然，这种做法要比“一对多”的做法多出很多两类分类器，但不会出现两类样本数过于不均衡的问题，决策歧义的区域通常要比“一对多”的做法小，如图4-4中的阴影部分所示。

在多数线性分类器中，对于一个正确分类的样本，如果它离分类面越远，就代表分类器对它的类别判断越确定，因此可以把分类器的输出值看作对样本属于某一类别的一种评分。在多类决策时，如果只有一个两类分类器对一个样本属于某类给出了大于阈值的输出，而其余分类器的输出均小于阈值，那么就把这个样本分到该类，而且评分越高表示分类越精准；反之，则判断样本不属于该类。

如果样本本身是层次化的分类结构，那么可以用一个二叉树来解决分类问题，在这种树状结构的每一层上，都会有一个决策将某一类别与其他类别分开，如图4-5所示。可利用树状结构来构建多个两类分类器，这是一种最常见的层次结构决策树。实际应用中，在各层上还可以采用其他各种类型的“多分树”。

第三种情况是第二种情况的特例，即直接对c个类别设计c个判别函数。

其中，i=1,2,…,c。哪一类的判别函数最大则决策就为哪一类，若。与上面讨论的两种情况中用多个两类分类器进行多类别划分的方法相比，多类线性分类器可以保证不会出现有决策歧义的区域。三类线性判别示例如图4-6所示。

假设存在一个能够把所有样本都正确分类的线性机器。在这种情况下，可以借鉴改进的感知器算法思想求解线性分类器，具体步骤如下。

（1）任意选择初始的权重向量，i=1,2,…,c，置t=0。

（2）考查某个样本，若，则所有权重向量不变；若存在某个类j，使，则选择使最大的类别j，对各类的权值进行如下的修正。

其中，为步长，必要时可以随t改变。

（3）若所有样本都分类正确，则停止；否则考查另一个样本，t=t+1，重复步骤（2）。

可以证明，若样本集线性可分，则该算法可以在有限步内收敛于一组解向量；当样本不是线性可分时，这种迭代不能收敛，人们可以对算法进行适当的调整，从而使算法能够停止在一个可以接受的解上，如通过逐渐减小步长来强制使算法收敛。

很多两类分类算法都可以转换成相应的多类分类算法，但它们多数在实际中的应用并不广泛。线性判别函数是形式最简单的判别函数且便于计算，因此在实际中应用广泛。在解决一个多类分类问题时，若是线性可分的情况，则很容易将两类分类问题推广，从而得到多类分类问题的设计标准和方法。如果某些实际问题并不是线性的，但由于样本数目较小或样本中包含较大的噪声，那么可以采用线性分类器，这在某些情况下会比更复杂的模型效果更好，尤其是具有更好的泛化能力。