Fisher线性判别式 前面讲过的感知器准则、最小平方和准则属于用神经网络的方法解决分类问题。下面介绍一种新的判决函数分类方法。 由于线性判别函数易于分析，关于这方面的研究工作特别多。历史上，这一工作是从R.A.Fisher的经典论文（1936年） 开始的。我们知道，在用统计方法进行模式识别时，许多问题涉及到维数，在低维空间行得通的方法，在高维空间往往行 不通。因此，降低维数就成为解决实际问题的关键。Fisher的方法，实际上涉及维数压缩。 如果要把模式样本在高( d )维的特征向量空间里投影到一条直线上，实际上就是把特征空间压缩到一维，这在数学上 容易办到。另外，即使样本在高维空间里聚集成容易分开的群类，把它们投影到一条任意的直线上，也可能把不同的样本 混杂在一起而变得无法区分。也就是说，直线的方向选择很重要。 在一般情况下，总可以找到某个最好的方向，使样本投影到这个方向的直线上是最容易分得开的。如何找到最好的直 线方向，如何实现向最好方向投影的变换，是Fisher法要解决的基本问题。这个投影变换就是我们寻求的解向量 *w 。 1．线性投影与Fisher准则函数 在 型， n 1/ ww 2   n 1 y  k 令： 两类问题中，假定有 n 个训练样本 ( kxk  2,1 ,...., n ) 其中 1n 个样本来自 iw 类型， 2n 个样本来自 jw 类 。两个类型的训练样本分别构成训练样本的子集 1X 和 2X 。 n 2 T xw ,...,2,1 (4.5-1) n k ， k ky 是向量 kx 通过变换 w 得到的标量，它是一维的。实际上，对于给定的 w ， ky 就是判决函数的值。 1|| w 由子集 1X 和 2X 的样本映射后的两个子集为 1Y 和 2Y 。因为我们关心的是 w 的方向，可以令 || 是 kx 在 w 方向上的投影。使 1Y 和 2Y 最容易区分开的 w 方向正是区分超平面的法线方向。如下图： ，那么 ky 就 图中画出了直线的两种选择，图(a)中， 1Y 和 2Y 还无法分开，而图(b)的选择可以使 1Y 和 2Y 区分开来。所以图(b)的 方向是一个好的选择。 下面讨论怎样得到最佳 w 方向的解析式。 各类在 d 维特征空间里的样本均值向量： M 1  n i i  k X  x x k i ， 2,1i 通过变换 w 映射到一维特征空间后，各类的平均值为： m i  1 n i  y k Y  i y k ， 2,1i (4.5-2) (4.5-3) 映射后，各类样本“类内离散度”定义为： 2 S i   y m k i ( y Y  k i 2 ) ， 2,1i (4.5-4) 显然，我们希望在映射之后，两类的平均值之间的距离越大越好，而各类的样本类内离散度越小越好。因此，定义Fisher 1 

准则函数： | ) J w F (  m m 1 2 2 2 s s 1   2 2 | (4.5-5) *w 就是最佳解向量，也就是Fisher的线性判别式。 使 FJ 最大的解 2．求解 *w (wJ F ) 从 的表达式可知，它并非 w 的显函数，必须进一步变换。 已知： m i  m i  1 n i 1 n i y k ， 2,1i , 依次代入(4.5-1)和(4.5-2)，有：  y k Y  i  Xx  k T xw k  T w i 1( n i  Xx  k i x k )  T Mw ， i 2,1i (4.5-6) 所以： | 2 |  ||  T MwMw mm 2 1 T wSwwMMMMw T MMw ||  )(       || ) ( ( T T T 2 1 1 2 2 b 其中： S b  ( MMMM )(   1 1 1 2 2 1 T ) 2 2 ||) 2 (4.5-7) (4.5-8) bS 是原 d 维特征空间里的样本类内离散度矩阵，表示两类均值向量之间的离散度大小，因此， bS 越大越容易区分。 将(4.5-6) Mwm  T i 和(4.5-2) i M 1  n i i  k X  x x k i 代入(4.5-4) 2 iS 式中： S 2 i   k X  x ( T xw k  T Mw 2 ) i i  T w   k X  ( i x MxMx k )(   k i T ) i  w (4.5-10) (4.5-11) T wSw i   ( x k  X i MxMx k )(   k i (4.5-9) T ) i ， 2,1i 其中： S i 因此： 显然： 2 S 1 Sw  S 2 2  T ( Sw 1   S 1  S 2 wSwwS 2  ) w T (4.5-12) iS 称为原 d 维特征空间里，样本“类内离散度”矩阵。 wS 是样本“类内总离散度”矩阵。 为了便于分类，显然 iS 越小越好，也就是 wS 越小越好。 将上述的所有推导结果代入 (wJ F ) 表达式： wJ F ( ) b T wSw T wSw w —— 广义Rayleigh商 (4.5-13) 式中 bS 和 wS 皆可由样本集 X 计算出。 用lagrange乘子法求解 ) (wJ F 的极大值点。 令分母等于非零常数，也就是： 定义lagrange函数： cwSwc 0  T w 。 2 

, ( wL )   T wSw b  (  T cwSw  w ) (4.5-14)  (2 wS b   ) wS w L 对 w 求偏导数： )  ( , wL  w  , ( ) wL   w  * wS b 令  0 得到：  * wS w (4.5-15) 从上述推导(4.5-10)～(4.5-12)可知， wS 是 d 维特征的样本协方差矩阵，它是对称的和半正定的。当样本数目 n  d 时， wS 是非奇异的，也就是可求逆。 则： * w  S w  1 * wS b 问题转化为求一般矩阵 的特征值和特征向量。令 b * wS b  {( MMMM   1 * T }) w S 1 w S )( 1 2 ) * wMM  T 2 1   ( ( 1  MM 1 MM  2 2 2 ){( )  } (4.5-17) (4.5-16) 1 S w S b  ，则是 A 的特征根， A *w 是 A 的特征向量。 式中：  ( * wMM  ) T 2 1 是一个标量。所以 *wSb 总是在 ( 1 MM  2 ) 方向上。将(4.5-17)代入到(4.5-15)，可以得到： * w    1  MMS w  ( 1 ) 2 其中，   是一个比例因子，不影响 *w 的方向，可以删除，从而得到最后解： * w   1 MMS w  ( 1 ) 2 (4.5-18) *w 就使 ) (wJ F 取得最大值， *w 可使样本由 d 维空间向一维空间映射，其投影方向最好。 * w  是一个Fisher线性判断式。 讨论： 如果 1 MM  2 ， * w 0 ，则样本线性不可分。 2 ，未必线性可分。 1 MM  wS 不可逆，未必不可分。 3.Fisher算法步骤  1 MMS w  ( 1 ) 2 由Fisher线性判别式   1 MMS w  ( 1 ) 2 求解向量 *w 的步骤： 的训练样本集 X 分成 1w 和 2w 两个子集 1X 和 2X 。 * w 1 / ww 2  x k x k X  ① 把来自两类 ② 由 M 1  n i i ， 2,1i ，计算 iM 。 i 3 

③ 由 S i    X x k MxMx k )(   k i T ) i 计算各类的类内离散度矩阵 iS ， 2,1i 。 ( i ④ 计算类内总离散度矩阵 Sw  S 1  S 2 。 ⑤ 计算 wS 的逆矩阵 1 wS 。 ⑥ 由 * w   1 MMS w  ( 1 ) 求解 *w 。 2 这一节所研究的问题针对确定性模式分类器的训练，实际上，Fisher的线性判别式对于随机模式也是适用的。 Fisher算法注释: （1）Fisher方法可直接求解权向量 *w ； （2）对线性不可分的情况，Fisher 方法无法确定分类，Fisher 可以进一步推广到多类问题中去。 4