3.5　基于Fisher的分类器设计

3.5.1　Fisher判别法简介

Fisher判别法是1936年由R. A. Fisher首先提出的。Fisher判别法是一种线性判别法，线性判别又称线性准则。与线性准则相对应的还有非线性准则，其中一些在变换条件下可以转化为线性准则，因此对应于d维特征空间，线性判别函数虽然最简单，但是在应用上却具有普遍意义，便于对分类问题的理解与描述。

基于线性判别函数的线性分类方法，虽然使用有限样本集合来构造，从严格意义上来讲属于统计分类方法。也就是说，对于线性分类器的检验，应建立在样本扩充的条件下，以基于概率的尺度来评价才是有效的评价。尽管线性分类器的设计在满足统计学的评价下并不严格与完美，但是由于其具有的简单性与实用性，在分类器设计中还是获得了广泛的应用。

3.5.2　Fisher判别法的原理

设计线性分类器首先要确定准则函数，然后再利用训练样本集确定该分类器的参数，以求使所确定的准则达到最佳。在使用线性分类器时，样本的分类由其判别函数值决定，而每个样本的判别函数值是其各分量的线性加权和再加上一个阈值y₀。

如果只考虑各分量的线性加权和，则它是各样本向量与向量w的向量点积。如果向量w的幅度为单位长度，则线性加权和又可被看作各样本向量在向量w上的投影。

Fisher判别法的基本原理是，对于d维空间的样本，投影到一维坐标上，样本特征将混杂在一起，难以区分。Fisher判别法的目的，就是要找到一个最合适的投影轴w，使两类样本在该轴上投影的交叠部分最少，从而使分类效果为最佳。如何寻找一个投影方向，使得样本集合在该投影方向上最易区分，这就是Fisher判别法所要解决的问题。Fisher投影原理如图3-2所示。

Fisher准则函数的基本思路：即向量w的方向选择应能使两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小。

3.5.3　Fisher分类器设计

已知N个d维样本数据集合χ=｛x₁，x₂，…，x_N｝，其中类别为ω_i（i=1，2），样本容量为N_i，其子集为x_i，以投影坐标向量w与原特征向量x作数量积，可得投影表达式为y_n=w^Tx_n（n=1，2，…，N）。

相应地，y_n也为两个子集y₁和y₂。如果只考虑投影向量w的方向，不考虑其长度，即默认其长度为单位1，则y_n即为x_n在w方向上的投影。Fisher准则的目的就是寻找最优投影方向，使得w为最好的投影向量w^*。

样本在d维特征空间的一些描述量如下。

（1）各类样本均值向量m_i

（2）样本类内离散度矩阵S_i与总类内离散度矩阵S_w

（3）样本类间离散度矩阵S_b

如果在一维上投影，则有各类样本均值向量

样本类内离散度矩阵与总类内离散度矩阵

Fisher准则函数的定义原则为，希望投影后，在一维空间中样本类别区分清晰，即两类样本的距离越大越好，也就是均值之差（）越大越好；各类样本内部密集，即类内离散度越小越好。根据上述两条原则，构造Fisher准则函数

使得J_F（w）为最大值的w即为要求的投影向量w^*。

式（3-16）称为Fisher准则函数，需进一步转化为w的显函数，为此要对，等项进一步演化。由于

则有

其中S_b=（m₁-m₂）（m₁-m₂）^T为类间离散矩阵。再由类内离散度

其中。

所以总类内离散度为

将式（3-18）与式（3-20）代入式（3-16），得到Fisher准则函数对于变量w的显式函数为

对x_n的分量作线性组合y_n=w^Tx_n（n=1，2，…，N），从几何意义上看，‖w‖=1，则每个y_n就是相对应的x_n到方向为w的直线上的投影。w的方向不同，将使样本投影后的可分离程序不同，从而直接影响识别效果。

求解Fisher准则函数的条件极值，即可解得使J_F（w）为极值的w^*。对求取其极大值时的w^*，可以采用拉格朗日乘子算法解决，令分母非0，即w^TS_ww=c≠0。

构造拉格朗日函数

对w求偏导，并令其为0，即

得到

由于S_w非奇异，两边左乘，得到，该式为矩阵的特征值问题。其中，拉格朗日算子λ为矩阵的特征值；w^*即对应于特征值λ的特征向量，即最佳投影的坐标向量。

矩阵特征值的问题有标准的求解方法。在此给出一种直接求解方法，不求特征值而直接得到最优解w^*。

由于

所以

S_bw^*=（m₁-m₂）（m₁-m₂）^Tw^*=（m₁-m₂）R

式中，R=（m₁-m₂）^Tw^*为限定标量。进而，由于

得到

忽略比例因子R/λ，得到最优解。因此，使得J_F（w）取极大值时的w即为d维空间到一维空间的最佳投影方向

向量w^*就是使Fisher准则函数J_F（w）达到极大值的解，也就是按Fisher准则将d维X空间投影到一维Y空间的最佳投影方向，w^*的各分量值是对原d维特征向量求加权和的权值。

由式（3-28）表示的最佳投影方向是容易理解的，因为其中的（m₁-m₂）项是一向量，对与（m₁-m₂）平行的向量投影可使两均值点的距离最远。

但是如何使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对（m₁-m₂）向量按作一线性变换，从而使Fisher准则函数达到极值点。

以上讨论了线性判别函数加权向量w的确定方法，并讨论了使Fisher准则函数极大的d维向量w^*的计算方法。由Fisher判别函数得到了最佳一维投影后，还需确定一个阈值点y₀，一般可采用以下几种方法确定y₀，即

式（3-29）是根据两类样本均值之间的平均距离来确定阈值点的。式（3-30）既考虑了样本均值之间的平均距离，又考虑了两类样本的容量大小作阈值位置的偏移修正。式（3-31）既使用了先验概率P（ω_i），又考虑了两类样本的容量大小作阈值位置的偏移修正，目的都是使得分类误差尽可能小。

为了确定具体的分界面，还要指定线性方程的常数项。实际工作中可以采用对y₀进行逐次修正的方式，选择不同的y₀值，计算其对训练样本集的错误率，找到错误率较小的y₀值。

对于任意未知类别的样本x，计算它的投影点y=w^Tx，决策规则为

3.5.4　Fisher算法的MATLAB实现

1．流程图

根据上面所介绍的Fisher判别函数，可得出如图3-3所示的流程图。

2．样本均值

利用MATLAB程序得到训练样本均值，程序代码如下：

3．投影向量

Fisher准则的目的就是寻找最优投影方向，使得w为最好的投影向量w^*。

利用如下MATLAB程序求得最佳投影向量：

4．阈值点

本设计器采用y₀=w^*（m₁+m₂）^T/2来确定阈值点，由于该式既考虑了样本均值之间的平均距离，又考虑了两类样本的容量大小作阈值位置的偏移修正，因此采用它可以使得分类误差尽可能小。

5．输出分类结果

对于任意未知类别的样本x，计算它的投影点y=w^Tx，决策规则为：当y＞y₀时，x∈ω₁；当y＜y₀时，x∈ω₂。

输出分类结果的MATLAB程序如下：

3.5.5　识别待测样本类别

本节内容以兑酒为例。不同类型的酒是由多种成分按不同的比例构成的，兑酒时需要三种原料（X，Y，Z），现在已测出不同酒中三种原料的含量，需要判定它属于四种类型中的哪一种。样本中，前29组数据用于学习，后22组用于识别。

1．选择分类方法

由于Fisher分类法一次只能将样本分成两类，因此，首先要将样本分成两大类，即一类、二类，然后再继续往下分，将其分成1、2、3、4类。分类流程图如图3-4所示。

将样本分成两大类有3种分法，如表3-2所示。

根据所给的训练样本数据，利用MATLAB程序得出训练样本分布图，如图3-5所示。

观察训练样本分布图可知，如果将第1、2类分在一起作为第一类，第3、4类分在一起作为第二类，这样很难将它们分开，因此排除这种分类方法，应选择第二、三种分类方法。

2．MATLAB程序

（1）选择第二种方法的相关程序及仿真结果。

训练样本分布图程序代码如下：

测试样本分为一（1、3）类、二（2、4）类程序代码如下：

程序运行完之后，出现如图3-6所示的一、二类数据分类结果图界面。

运行MATLAB程序的结果如下：

测试样本一类分为1、3类的程序代码如下：

程序运行完之后，出现如图3-7所示的1、3类数据分类结果图界面。

运行MATLAB程序的结果如下：

测试样本二类分为2、4类的程序代码如下：

程序运行完之后，出现如图3-8所示的2、4类数据分类结果图界面。

运行MATLAB程序的结果如下：

（2）选择第三种方法的相关程序及仿真结果。

测试样本分为一（1、4）类、二（2、3）类的程序代码如下：

程序运行完之后，出现如图3-9所示的数据分类结果图界面。

运行MATLAB程序之后的结果如下：

测试样本一类分为1、4类的程序代码如下：

程序运行完之后，出现如图3-10所示的1、4类数据分类结果界面。

运行MATLAB程序的结果如下：

测试样本二类分为2、3类的程序代码如下：

程序运行完之后，出现如图3-11所示的2、3类数据分类结果图界面。

运行MATLAB程序的结果如下：

将两种分类方法的分类结果进行比较，即利用第二、三种分类方法进行比较，得出的分类结果如表3-3所示。

比较这两种分类方法，方法二有两个错误分类，方法三仅有一个错误分类，所以方法三优于方法二。

3.5.6　结论

本节主要论述了Fisher分类法的概念、特点及其分类器设计，重点讨论了利用Fisher分类法设计分类器的全过程。在设计该种分类器的过程中，首先利用训练样本求得最佳投影方向w^*，并确定阈值点y₀；接着通过分析来归纳给定样本数据的分类情况；最后利用MATLAB中的相关函数、工具设计了基于Fisher分类法的分类器，并对测试数据进行了成功分类。整个讨论和设计过程，关键点和创新点就在于对测试数据的处理过程上，通过两种方法做到了快速且相对准确的分类。