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$ 的分量作线性组合可得标量

这样便得到 $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$

    (2) 样本类内离散度矩阵 $S_i$ 和总类内离散度矩阵 $S_w$

    (3) 样本类间离散度矩阵 $S_b$

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

  1. 在 1 维 $Y$ 空间

    (1) 各类样本均值 $\tilde m$

    (2) 样本类内离散度 $\tilde S_i^2$ 和总类内离散度 $\tilde S_w$

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

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

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

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

因此,

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

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

定义Lagrange函数为

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

令偏导数为零,得

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

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

式中,$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)式可得

从而可得

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

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

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

一分一毛也是心意