简介

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

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

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

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

正文

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

首先，讨论从 $d$ 维空间到一维空间的一般数学变换方法。假设有一集合 $H$ 包含 $N$ 个 $d$ 维样本 $x x_{1}, x_{2}, \dots, x_{N}$ ，其中 $N_{1}$ 个属于 $ω_{1}$ 类的样本记为子集 $H_{1}$ ， $N_{2}$ 个属于 $ω_{2}$ 类的样本记为 $H_{2}$ 。若对 $x x_{n}$ 的分量作线性组合可得标量

\begin{matrix} (1) & y_{n} = w w^{T} x x_{n}, n = 1, 2, . . ., N_{i} \end{matrix}

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

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

在 $d$ 维 $X$ 空间

(1) 各类样本均值向量 $m m_{i}$
$\begin{matrix} (2) & m m_{i} = \frac{1}{N_{i}} \sum_{x x \in H_{i}} x x, i = 1, 2 \end{matrix}$
(2) 样本类内离散度矩阵 $S_{i}$ 和总类内离散度矩阵 $S_{w}$
$\begin{matrix} (3) & S_{i} = \sum_{x x \in H_{i}} (x x - m m_{i}) (x x - m m_{i})^{T}, i = 1, 2 \end{matrix}$ $\begin{matrix} (4) & S_{w} = S_{1} + S_{2} \end{matrix}$
(3) 样本类间离散度矩阵 $S_{b}$
$\begin{matrix} (5) & S_{b} = (m m_{1} - m m_{2}) (m m_{1} - m m_{2})^{T} \end{matrix}$

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

在 1 维 $Y$ 空间

(1) 各类样本均值 $\tilde{m}$
$\begin{matrix} (6) & {\tilde{m}}_{i} = \frac{1}{N_{i}} \sum_{y \in Y_{i}} y, i = 1, 2 \end{matrix}$
(2) 样本类内离散度 ${\tilde{S}}_{i}^{2}$ 和总类内离散度 ${\tilde{S}}_{w}$
$\begin{matrix} (7) & {\tilde{S}}_{i}^{2} = \sum_{y \in Y_{i}} (y - {\tilde{m}}_{2})^{2}, i = 1, 2 \end{matrix}$ $\begin{matrix} (8) & {\tilde{S}}_{w} = {\tilde{S}}_{1}^{2} + {\tilde{S}}_{2}^{2} \end{matrix}$

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

\begin{matrix} (9) & J J_{F} (w w) = \frac{({\tilde{m}}_{1} - {\tilde{m}}_{2})^{2}}{{\tilde{S}}_{1}^{2} + {\tilde{S}}_{2}^{2}} \end{matrix}

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

\begin{matrix} (10) & \begin{aligned} {\tilde{m m}}_{i} & = \frac{1}{N_{i}} \sum_{y \in Y_{i}} y = \frac{1}{N_{i}} \sum_{x x \in R_{i}} w w^{T} x x \\ = w w^{T} (\frac{1}{N_{i}} \sum_{x x \in R_{i}} x x) = w w^{T} m m_{i} \end{aligned} \end{matrix}

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

\begin{matrix} (11) & \begin{aligned} ({\tilde{m m}}_{1} - {\tilde{m m}}_{2}) & = (w w^{T} m m_{1} - w w^{T} m m_{2})^{2} \\ = w w^{T} (m m_{1} - m m_{2}) (m m_{1} - m m_{2})^{T} w w = w w^{T} S_{b} w w \end{aligned} \end{matrix}

再来考察 $J_{F} (w w)$ 的分母与 $w w$ 的关系。

\begin{matrix} (12) & \begin{aligned} {\tilde{S}}_{i}^{2} & = \sum_{y \in Y_{i}} (y - {\tilde{m}}_{i})^{2} = \sum_{x x \in R_{i}} (w w^{T} x x - w w^{T} m m_{i})^{2} \\ = w w^{T} [\sum_{x x \in R_{i}} (x x - m m_{i}) (x x - m m_{i})^{T}] w w = w w^{T} S_{i} w w \end{aligned} \end{matrix}

因此，

\begin{matrix} (13) & {\tilde{S}}_{1}^{2} + {\tilde{S}}_{2}^{2} = w w^{T} (S_{1} + S_{2}) w w = w w^{T} S_{w} w w \end{matrix}

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

\begin{matrix} (14) & J_{F} (w w) = \frac{w w^{T} S_{b} w w}{w w^{T} S_{w} w w} \end{matrix}

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

w w^{T} S_{w} w w = c \neq 0

定义Lagrange函数为

\begin{matrix} (15) & L (w w, λ) = w w^{T} S_{b} w w - λ (w w^{T} S_{w} w w - c) \end{matrix}

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

\frac{\partial L (w w, λ)}{\partial w w} = S_{b} w w - λ S_{w} w w

令偏导数为零，得

S_{b} w w^{*} - λ S_{w} w w^{*} = 0

即

\begin{matrix} (16) & S_{b} w w^{*} = λ S_{w} w w^{*} \end{matrix}

其中 $w w^{*}$ 就是 $J_{F} (w w)$ 的极值解。因为 $S_{w}$ 非奇异，(16)式两边左乘 $S_{w}^{- 1}$ ，可得

\begin{matrix} (17) & S_{w}^{- 1} S_{b} w w^{*} = λ m m^{*} \end{matrix}

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

S_{b} w w^{*} = (m m_{1} - m m_{2}) (m m_{1} - m m_{2})^{T} w w^{*} = (m m_{1} - m m_{2}) R

式中， $R = (m m_{1} - m m_{2})^{T} w w^{*}$ ，为一标量，所以 $S_{b} w w^{*}$ 总是在向量 $(m m_{1} - m m_{2})$ 的方向上。由于我们的目的是寻找最好的投影方向， $w w^{*}$ 的比例因子对此并无影响，因此，从(17)式可得

λ w w^{*} = S_{w}^{- 1} (S_{b} w w^{*}) = S_{w}^{- 1} (m m_{1} - m m_{2}) R

从而可得

\begin{matrix} (18) & w w^{*} = \frac{R}{λ} S_{w}^{- 1} (m m_{1} - m m_{2}) \end{matrix}

忽略比例因子 $R / λ$ ，得

w w^{*} = S_{w}^{- 1} (m m_{1} - m m_{2})

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

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