3.4　费希尔分类器的设计与实现

1.费希尔判别法简介和基本原理

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

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

在用统计学方法进行模式识别时，许多问题涉及维数，在低维空间行得通的方法，在高维空间往往不行。因此，降低维数成为解决实际问题的关键。费希尔判别法就是解决维数压缩问题的方法。

对Xn的分量做线性组合可得到标量，如式(3-9)

yn=WTXn　i=1,2

(3-9)

首先要解决的问题就是怎样找到最好的投影直线方向和怎样向这个方向实现投影。这个投影变换就是要寻求的解向量W*。

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

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

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

费希尔准则函数的基本思路:向量W的方向应能使两类样本投影的均值之差尽可能大，以及使类内样本的离散程度尽可能小。

2.费希尔分类器的设计

已知N个d维样本数据集合X={x1,x2,…,xN}，其中类别为ωi(i=1,2)，样本容量为Ni，其子集为xi，求投影坐标向量W与原特征向量X的数量积，可得投影表达式为yn=WTXn,n=1,2,…,N。

相应地，yn也有两个子集y1和y2。如果只考虑投影向量W的方向，不考虑其长度，即默认其长度为1，则yn即为Xn在W方向上的投影。费希尔准则的目的就是寻找最优投影方向，使得W为最好的投影向量W*。

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

(1)各类样本均值向量mi

(3-10)

(2)样本类内离散度矩阵Si与总类内离散度矩阵Sw

(3-11)

Sw=S1+S2

(3-12)

(3)样本类间离散度矩阵Sb

Sb=(m1-m2)(m1-m2)T

(3-13)

如果在一维空间内投影，则有：

各类样本均值向量

(3-14)

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

(3-15)

(3-16)

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

(3-17)

使得JF(W)为最大值的W即为要求的投影向量W*。

式(3-17)称为费希尔准则函数,需进一步化为W的显函数，为此要对等项进一步演化。由于

(3-18)

则有

(3-19)

其中Sb=(m1-m2)(m1-m2)T为类间离散矩阵。类内离散度为

(3-20)

其中

(3-21)

则总类内离散度为

(3-22)

将式(3-19)与式(3-22)代入式(3-17)，得到费希尔准则函数关于变量W的公式为

(3-23)

对Xn的分量做线性组合yn=WTXn，n=1,2,…,N，从几何意义上看，则每个yn就是相对应的Xn到方向为W的直线上的投影。W的方向不同，将使样本投影后的可分离程序不同，从而直接影响识别效果。寻找最好投影方向W*，即是求解费希尔准则函数的条件极值的过程。为求取费希尔准则函数有极大值时的W*。可以采用拉格朗日乘子算法解决，令分母非零，即WTSwW=c≠0

构造拉格朗日函数

L(W,λ)=WTSbW-λ(WTSwW-c)

(3-24)

对W求偏导，并令其为零，即

=SbW-λSwW=0

(3-25)

得到

SbW*=λSwW*

(3-26)

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

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

由于

Sb=(m1-m2)(m1-m2)T

(3-27)

所以

SbW*=(m1-m2)(m1-m2)TW*=(m1-m2)R

(3-28)

其中，R=(m1-m2)TW*为限定标量。由于

(3-29)

得到忽略比例因子R/λ，得到最优解因此，使得JF(W)取极大值时的W即为d维空间到一维空间的最好投影方向

向量W*就是使费希尔准则函数JF(W)达到极大值的解，也就是按费希尔准则将d维X空间投影到一维Y空间的最佳投影方向，W*的各分量值是对原d维特征向量求加权和的权值。

由上述方法表示的最佳投影方向是容易理解的，因为其中一项(m1-m2)是一向量，对与(m1-m2)平行的向量投影可使两均值点的距离最远。

如何使类间分得较开，同时又使类内密集程度较高，解决这个问题需要根据两类样本的分布离散程度对投影方向进行相应的调整，这就体现在对(m1-m2)向量按做线性变换上，从而使费希尔准则函数达到极值点。

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

(3-30)

(3-31)

(3-32)

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

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

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

(3-33)

3.费希尔算法的MATLAB实现

根据上面所介绍的费希尔准则函数，可得出其算法实现流程图，如图3-8所示。

算法具体实现如下。

首先利用MATLAB程序得到训练样本均值：

本节设计的Fisher 分类器进行两次分类，将选取的居民收入分为4类，如图3-9所示。

由训练样本分布图(见图3-10)可以看出有两种分类方法：

第1、3类作为第一类，第2、4类作为第二类。

第1、4类作为第一类，第2、3类作为第二类。

MATLAB仿真结果如图3-11所示。

图3-11中，第1列代表经营收入，第2列代表财产性收入，第3列代表转移性收入。

比较这两种分类方法，有一组数据的分类结果不同。根据给定的标准分类结果计算出每种分类法的识别率，哪个识别率高哪个即为最好的分类方法。