Fisher线性判别

简介

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准则函数之前，我们先定义几个必要的基本参量。

1. 在 $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. 在 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$ 维分类问题转化为一维分类问题了。之后可以根据几种一维分类问题的基本原则进行分类。