简介

Fisher线性判别的本质是线性判别，即线性分类。它的思想是由于维数灾难，所以需要降低维数，再设计线性分类器。

再简单地说，Fisher就是也只是将 $d$ 维分类问题转化为一维分类问题。

有点类似于PCA，同属于降维，不过PCA中没有类别标签，所以PCA根据的是总体样本之间的样本方差大小来进行降维。而Fisher是高维空间中存在多个类，所以降维的时候需要考虑到类内距离和类间距离。

这里直接把《模式识别》书里的写过来。

正文

考虑把 $d$ 维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。然而，如果样本在 $d$ 维空间里形成若干紧凑的互相分得开的集群，若把它们投影到一条任意的直线上，也可能是几类样本混在一起而变得无法识别。但在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分开得最好。问题是如何根据实际情况找到这条最好的、最易于分类的投影线。这就是Fisher要解决的基本问题。

首先，讨论从 $d$ 维空间到一维空间的一般数学变换方法。假设有一集合 $\mathcal{H}$ 包含 $N$ 个 $d$ 维样本 $\pmb x_1,x_2,…,x_N$，其中 $N_1$ 个属于 $\omega_1$ 类的样本记为子集 $\mathcal{H}_1$ ，$N_2$ 个属于 $\omega_2$ 类的样本记为 $\mathcal H_2$ 。若对 $\pmb x_n$ 的分量作线性组合可得标量

$y_n=\pmb{w}^T\pmb{x}_n,n=1,2,...,N_i \tag 1$

这样便得到 $N$ 个一维样本 $y_n$ 组成的集合，并可分为两个子集 $\mathcal Y_1$ 和 $\mathcal Y_2$。从几何上看，如果 $||\pmb w||=1$，则每个 $y_n$ 就是相对应的 $\pmb x_n$ 到方向为 $\pmb w$ 的直线上的投影。实际上，$\pmb w$ 的绝对值是无关紧要的，它仅使 $y_n$ 乘上一个比例因子，重要的是选择 $\pmb w$ 的方向。$\pmb w$ 的方向不同，将使样本投影后的可分离程度不同，从而直接影响识别效果。因此，前述所谓寻找最好投影方向的问题，在数学上就是寻找最好的变换向量 $\pmb w^\ast$ 的问题。

在定义Fisher准则函数之前，我们先定义几个必要的基本参量。

在 $d$ 维 $X$ 空间

(1) 各类样本均值向量 $\pmb m_i$
$\pmb{m}_i=\frac{1}{N_i}\sum_{\pmb{x}\in\mathcal H_i}\pmb{x},i=1,2 \tag 2$
(2) 样本类内离散度矩阵 $S_i$ 和总类内离散度矩阵 $S_w$
$S_i=\sum_{\pmb{x}\in \mathcal H_i}(\pmb{x}-\pmb{m}_i)(\pmb{x}-\pmb{m}_i)^T,i=1,2\tag 3$ $S_w = S_1+S_2 \tag 4$
(3) 样本类间离散度矩阵 $S_b$
$S_b=(\pmb{m}_1-\pmb{m}_2)(\pmb{m}_1-\pmb{m}_2)^T\tag 5$

其中 $S_w$ 是对称半正定矩阵，，而且当 $N>d$ 时通常是非奇异的。$S_b$ 也是对称非正定矩阵，在两类条件下，它的秩最大等于1。

在 1 维 $Y$ 空间

(1) 各类样本均值 $\tilde m$
$\tilde m_i=\frac{1}{N_i}\sum_{y\in\mathcal Y_i}y,i=1,2 \tag 6$
(2) 样本类内离散度 $\tilde S_i^2$ 和总类内离散度 $\tilde S_w$
$\tilde S_i^2=\sum_{y\in\mathcal Y_i}(y-\tilde m_2)^2,i=1,2 \tag 7$ $\tilde S_w=\tilde S_1^2+\tilde S_2^2\tag 8$

现在定义Fisher准则函数。我们希望投影后，在一维 $Y$ 空间里各类样本尽可能分得开些，即希望两类均值之差 $(\tilde m_1-\tilde m_2)$ 越大越好；同时希望各类样本内部尽量密集。即希望类内离散度越小越好。因此，可以定义Fisher准则函数为

$\pmb J_F(\pmb w)=\frac{(\tilde m_1 - \tilde m_2)^2}{\tilde S_1^2 + \tilde S_2^2}\tag 9$

显然应该寻找使 $J_F(w)$ 的分子尽可能大，而分母尽可能小，也就是使 $J_F(w)$ 尽可能大的 $\pmb w$ 作为投影方向。但(9)式的 $J_F(\pmb w)$ 并不显含 $w$，因此必须设法将 $J_F(\pmb w)$ 变成 $\pmb w$ 的显函数。由(6)式可推出，

$\begin{align*} \tilde {\pmb m}_i&=\frac{1}{N_i}\sum_{y\in\mathcal Y_i}y=\frac{1}{N_i}\sum_{\pmb x\in\mathcal R_i}\pmb w^T\pmb x\\ &=\pmb w^T\left(\frac{1}{N_i}\sum_{\pmb x\in \mathcal R_i}\pmb x\right)=\pmb w^T\pmb m_i \end{align*}\tag {10}$

这样，(9)式的分子便成为

$\begin{align*} (\tilde {\pmb m}_1-\tilde {\pmb m}_2)&=(\pmb w^T\pmb m_1-\pmb w^T\pmb m_2)^2\\ &=\pmb w^T(\pmb m_1-\pmb m_2)(\pmb m_1-\pmb m_2)^T\pmb w=\pmb w^TS_b \pmb w \end{align*}\tag {11}$

再来考察 $J_F(\pmb w)$ 的分母与 $\pmb w$ 的关系。

$\begin{align*} \tilde S_i^2&=\sum_{y\in\mathcal Y_i}(y-\tilde m_i)^2=\sum_{\pmb x\in\mathcal R_i}(\pmb w^T\pmb x-\pmb w^T \pmb m_i)^2\\ &=\pmb w^T[\sum_{\pmb x\in\mathcal R_i}(\pmb x-\pmb m_i)(\pmb x-\pmb m_i)^T]\pmb w=\pmb w^TS_i\pmb w \end{align*}\tag{12}$

因此，

$\tilde S_1^2+\tilde S_2^2=\pmb w^T(S_1+S_2)\pmb w=\pmb w^TS_w\pmb w\tag{13}$

将(11)(13)代入(9)，可得

$J_F(\pmb w)=\frac{\pmb w^TS_b \pmb w}{\pmb w^TS_w\pmb w} \tag{14}$

下面求使 $J_F(\pmb w)$ 取极大值时的 $\pmb w^\ast$ 。(14)式中的 $J_F(\pmb w)$ 是广义Rayleigh商，可以用Lagrange乘子法求解。令分母等于非零常数，即令

$\pmb w^TS_w\pmb w=c\neq 0$

定义Lagrange函数为

$L(\pmb w,\lambda)=\pmb w^TS_b\pmb w-\lambda(\pmb w^TS_w\pmb w-c) \tag{15}$

式中 $\lambda$ 为Lagrange乘子。将(15)式对 $\pmb w$ 求偏导数，得

$\frac{\partial L(\pmb w,\lambda)}{\partial \pmb w}=S_b\pmb w-\lambda S_w\pmb w$

令偏导数为零，得

$S_b \pmb w^\ast-\lambda S_w\pmb w^\ast=0$

即

$S_b\pmb w^\ast=\lambda S_w\pmb w^\ast \tag{16}$

其中 $\pmb w^\ast$ 就是 $J_F(\pmb w)$ 的极值解。因为 $S_w$ 非奇异，(16)式两边左乘 $S_w^{-1}$，可得

$S_w^{-1}S_b\pmb w^\ast=\lambda \pmb m ^\ast \tag{17}$

(17)式为求一般矩阵 $S_w^{-1}S_b$ 的本征值问题。但在我们这个特殊情况下，利用(5)式 $S_b$ 的定义，(17)式左边的 $S_b\pmb w^\ast$ 可以写成

$S_b \pmb w^\ast = (\pmb m_1-\pmb m_2)(\pmb m_1-\pmb m_2)^T\pmb w^\ast = (\pmb m_1-\pmb m_2)R$

式中，$R=(\pmb m_1-\pmb m_2)^T\pmb w^\ast$，为一标量，所以 $S_b\pmb w^\ast$ 总是在向量 $(\pmb m_1-\pmb m_2)$ 的方向上。由于我们的目的是寻找最好的投影方向，$\pmb w^\ast$ 的比例因子对此并无影响，因此，从(17)式可得

$\lambda \pmb w^\ast=S_w^{-1}(S_b\pmb w^\ast)=S_w^{-1}(\pmb m_1-\pmb m_2)R$

从而可得

$\pmb w^\ast = \frac{R}{\lambda}S_w^{-1}(\pmb m_1-\pmb m_2) \tag{18}$

忽略比例因子 $R/\lambda$，得

$\pmb w^\ast = S_w^{-1}(\pmb m_1-\pmb m_2)$

$\pmb w^\ast$ 就是使Fisher准则函数 $J_F(\pmb w)$ 取极大值时得解，也就是 $d$ 维 $X$ 空间到一维 $Y$ 空间的最好投影空间。有了 $\pmb w^\ast$ ，利用(1)式，就可以把 $d$ 维样本 $\pmb x_n$ 投影到一维，这实际上是多维空间到一维空间的一种映射。

至此，还没有解决分类问题。只是将 $d$ 维分类问题转化为一维分类问题了。之后可以根据几种一维分类问题的基本原则进行分类。