fisher判别式

1Fisher线性判别式前面讲过的感知器准则、最小平方和准则属于用神经网络的方法解决分类问题。下面介绍一种新的判决函数分类方法。由于线性判别函数易于分析，关于这方面的研究工作特别多。历史上，这一工作是从R.A.Fisher的经典论文（1936年）开始的。我们知道，在用统计方法进行模式识别时，许多问题涉及到维数，在低维空间行得通的方法，在高维空间往往行不通。因此，降低维数就成为解决实际问题的关键。Fisher的方法，实际上涉及维数压缩。如果要把模式样本在高(d)维的特征向量空间里投影到一条直线上，实际上就是把特征空间压缩到一维，这在数学上容易办到。另外，即使样本在高维空间里聚集成容易分开的群类，把它们投影到一条任意的直线上，也可能把不同的样本混杂在一起而变得无法区分。也就是说，直线的方向选择很重要。在一般情况下，总可以找到某个最好的方向，使样本投影到这个方向的直线上是最容易分得开的。如何找到最好的直线方向，如何实现向最好方向投影的变换，是Fisher法要解决的基本问题。这个投影变换就是我们寻求的解向量*w。1．线性投影与Fisher准则函数在21/ww两类问题中，假定有n个训练样本),....,2,1(nkxk其中1n个样本来自iw类型，2n个样本来自jw类型，21nnn。两个类型的训练样本分别构成训练样本的子集1X和2X。令：kTkxwy，nk,...,2,1(4.5-1)ky是向量kx通过变换w得到的标量，它是一维的。实际上，对于给定的w，ky就是判决函数的值。由子集1X和2X的样本映射后的两个子集为1Y和2Y。因为我们关心的是w的方向，可以令1||||w，那么ky就是kx在w方向上的投影。使1Y和2Y最容易区分开的w方向正是区分超平面的法线方向。如下图：图中画出了直线的两种选择，图(a)中，1Y和2Y还无法分开，而图(b)的选择可以使1Y和2Y区分开来。所以图(b)的方向是一个好的选择。下面讨论怎样得到最佳w方向的解析式。各类在d维特征空间里的样本均值向量：ikXxkiixnM1，2,1i(4.5-2)通过变换w映射到一维特征空间后，各类的平均值为：ikYykiiynm1，2,1i(4.5-3)映射后，各类样本“类内离散度”定义为：22()kiikiyYSym，2,1i(4.5-4)显然，我们希望在映射之后，两类的平均值之间的距离越大越好，而各类的样本类内离散度越小越好。因此，定义Fisher2准则函数：2122212||()FmmJwss(4.5-5)使FJ最大的解*w就是最佳解向量，也就是Fisher的线性判别式。2．求解*w从)(wJF的表达式可知，它并非w的显函数，必须进一步变换。已知：ikYykiiynm1，2,1i,依次代入(4.5-1)和(4.5-2)，有：iTXxkiTkXxTiiMwxnwxwnmikik)1(1，2,1i(4.5-6)所以：221221221||)(||||||||MMwMwMwmmTTTwSwwMMMMwbTTT))((2121(4.5-7)其中：TbMMMMS))((2121(4.5-8)bS是原d维特征空间里的样本类内离散度矩阵，表示两类均值向量之间的离散度大小，因此，bS越大越容易区分。将(4.5-6)iTiMwm和(4.5-2)ikXxkiixnM1代入(4.5-4)2iS式中：ikXxiTkTiMwxwS22)(ikXxTikikTwMxMxw))((wSwiT(4.5-9)其中：TiXxkikiMxMxSik))((，2,1i(4.5-10)因此：wSwwSSwSSwTT)(212221(4.5-11)显然：21SSSw(4.5-12)iS称为原d维特征空间里，样本“类内离散度”矩阵。wS是样本“类内总离散度”矩阵。为了便于分类，显然iS越小越好，也就是wS越小越好。将上述的所有推导结果代入)(wJF表达式：wSwwSwwJwTbTF)(——广义Rayleigh商(4.5-13)式中bS和wS皆可由样本集X计算出。用lagrange乘子法求解)(wJF的极大值点。令分母等于非零常数，也就是：0cwSwcwT。定义lagrange函数：3)(),(cwSwwSwwLwTbT(4.5-14)L对w求偏导数：)(2),(wSwSwwLwb令0),(wwL得到：**wSwSwb(4.5-15)从上述推导(4.5-10)～(4.5-12)可知，wS是d维特征的样本协方差矩阵，它是对称的和半正定的。当样本数目dn时，wS是非奇异的，也就是可求逆。则：*1*wSSwbw(4.5-16)问题转化为求一般矩阵bwSS1的特征值和特征向量。令ASSbw1，则是A的特征根，*w是A的特征向量。*2121*}))({(wMMMMwSTb})){((*2121wMMMMT)(21MM(4.5-17)式中：*21)(wMMT是一个标量。所以*wSb总是在)(21MM方向上。将(4.5-17)代入到(4.5-15)，可以得到：)(211*MMSww其中，是一个比例因子，不影响*w的方向，可以删除，从而得到最后解：)(211*MMSww(4.5-18)*w就使)(wJF取得最大值，*w可使样本由d维空间向一维空间映射，其投影方向最好。)(211*MMSww是一个Fisher线性判断式。讨论：如果21MM，0*w，则样本线性不可分。21MM，未必线性可分。wS不可逆，未必不可分。3.Fisher算法步骤由Fisher线性判别式)(211*MMSww求解向量*w的步骤：①把来自两类21/ww的训练样本集X分成1w和2w两个子集1X和2X。②由ikXxkiixnM1，2,1i，计算iM。4③由TiXxkikiMxMxSik))((计算各类的类内离散度矩阵iS，2,1i。④计算类内总离散度矩阵21SSSw。⑤计算wS的逆矩阵1wS。⑥由)(211*MMSww求解*w。这一节所研究的问题针对确定性模式分类器的训练，实际上，Fisher的线性判别式对于随机模式也是适用的。Fisher算法注释:（1）Fisher方法可直接求解权向量*w；（2）对线性不可分的情况，Fisher方法无法确定分类，Fisher可以进一步推广到多类问题中去。