Fisher线性判别

2020-10-09 本文已影响0人追求科技的足球

一、简述Fisher线性判别方法的基本思路，写出准则函数及对应的解。

答：

1、Fisher线性判别：

（1）考虑把d维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。

（2）然而，即使样本在d维空间里形成若干紧凑的互相分得开的集群，当把它们投影到一条直线上时，也可能会是几类样本混在一起而变得无法识别。

（3）但是，在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分得开。

2、变换方法：

假设有一集合包含 $N$ 个 $d$ 维样本 $x_1,x_2,\dots,x_N$ ，若对 $x_n$ 的分量做线性组合可得标量：
$y_n = \boldsymbol{ \rm w^T}x_n, n=1,2,…,N$
这样便得到 $N$ 个一维样本 $y_n$ 组成的集合。实际上， $\boldsymbol{ \rm w}$ 的值是无关紧要的，它仅是 $y_n$ 乘上一个比例因子，重要的是选择w的方向。 $\boldsymbol{ \rm w}$ 的方向不同，将使样本投影后的可分离程度不同，从而直接影响的分类效果。
因此，上述寻找最佳投影方向的问题，在数学上就是寻找最好的变换向量 $\boldsymbol{ \rm w^*}$ 的问题

3、准则函数:

$J_F(\boldsymbol{\rm w})=\frac{\boldsymbol{\rm w^T}S_b\boldsymbol{\rm w}}{\boldsymbol{\rm w^T}S_w\boldsymbol{\rm w}}$
其中 $S_b$ 是类间离散度矩阵， $S_w$ 为类内离散度矩阵。
解：
$\boldsymbol{ \rm w^*}=S^{-1}_w(m_1-m_2)$
其中： $m_1$ 和 $m_2$ 为两类的均值。
附：

二、推导过程

1、参数定义

$d$ 维 $X$ 空间

(1)样本均值：
$m_i=\frac{1}{N}\sum_{x\in \Gamma_i}x,i=1,2,...,n$
(2)类内离散度矩阵：
$S_i=\sum_{x\in \Gamma_i}(x-m_i)(x-m_i)^T,i=1,2,\dots,n$
$S_w=S_1+S_2$
(3)类间离散度矩阵：
$S_b=(m_1-m_2)(m_1-m_2)^T$
1维 $Y$ 空间
(1)样本均值
$\widetilde{m_i}=\sum_{y\in \Gamma_i'}y,i=1,2,...,n$
(2)类内离散度矩阵：
$\widetilde{S_i^2}=\sum_{y\in \Gamma_i'}(y-m_i)^2,i=1,2,\dots,n$
$\widetilde{S_w}=\widetilde{S_1^2}+\widetilde{S_2^2}$

2、Fisher准则函数：

定义：
$J_F({\rm w})=\frac{(\widetilde{m_1}-\widetilde{m_2})^2}{\widetilde{S_1^2}+\widetilde{S_2^2}}$
分子为均值之差，分母为样本在Y上类内离散度，应该使得分子尽可能大而分母尽可能小。
则分子可以化为：
$\begin{aligned} (\widetilde{m_1}-\widetilde{m_2})^2&=(\boldsymbol{\rm w^T}m_1-\boldsymbol{\rm w^T}m_2)^2 \\&=(\boldsymbol{\rm w^T}m_1-\boldsymbol{\rm w^T}m_2)(\boldsymbol{\rm w^T}m_1-\boldsymbol{\rm w^T}m_2)^T \\&=(\boldsymbol{\rm w^T}m_1-\boldsymbol{\rm w^T}m_2)(m_1^T\boldsymbol{\rm w}-m_2^T\boldsymbol{\rm w}) \\&=\boldsymbol{\rm w^T}(m_1-m_2)(m_1-m_2)^T\boldsymbol{\rm w} \\&=\boldsymbol{\rm w^T}S_b\boldsymbol{\rm w} \end{aligned}$
同理，分母可以化为 $\boldsymbol{\rm w^T}S_w\boldsymbol{\rm w}$
则总体可以写为：
$J_F(\boldsymbol{\rm w})=\frac{\boldsymbol{\rm w^T}S_b\boldsymbol{\rm w}}{\boldsymbol{\rm w^T}S_w\boldsymbol{\rm w}}$

3、求解

使用拉格朗日乘子法，令分母等于非零常数:
$\boldsymbol{\rm w^T}S_w\boldsymbol{\rm w}=c\neq 0$
定义拉格朗日函数为：
$L(\boldsymbol{\rm w},\lambda)=\boldsymbol{\rm w^T}S_b\boldsymbol{\rm w}-\lambda(\boldsymbol{\rm w^T}S_w\boldsymbol{\rm w}-c)$
令偏导数为零：
$\frac{\partial L(\boldsymbol{\rm w},\lambda)}{\partial \boldsymbol{\rm w}}=S_b\boldsymbol{\rm w}-\lambda S_w\boldsymbol{\rm w}$
即：
$S_b\boldsymbol{\rm w^*}=\lambda S_w\boldsymbol{\rm w^*}$
其中 $\boldsymbol{\rm w^*}$ 就是 $J_F(\boldsymbol{\rm w^*})$ 的极值解。因为 $S_w$ 非奇异，将上式两边左乘 $S_w^{-1}$ ，可得：
$S_w^{-1}S_b\boldsymbol{\rm w^*}=\lambda \boldsymbol{\rm w^*}$
上式为求一般矩阵 $S_w^{-1}S_b$ 的特征值问题。利用 $S_b=(m_1-m_2)(m_1-m_2)^T$ 的定义，将上式左边的 $S_b\boldsymbol{\rm w^*}$ 写成：
$S_b\boldsymbol{\rm w^*}=(m_1-m_2)(m_1-m_2)^T\boldsymbol{\rm w^*}=(m_1-m_2)R$
其中 $R=(m_1-m_2)^T\boldsymbol{\rm w^*}$ 为一标量，所以 $S_b\boldsymbol{\rm w^*}$ 总在向量 $(m_1-m_2)$ 的方向上。因此 $\lambda \boldsymbol{\rm w^*}$ 可以写成：
$\lambda \boldsymbol{\rm w^*}=S_w^{-1}(S_b\boldsymbol{\rm w^*})=S_w^{-1}(m_1-m_2)R$
从而可得：
$\boldsymbol{\rm w^*}=\frac{R}{\lambda}S_w^{-1}(m_1-m_2)$
因为目的是选择最佳投影方向，因此比例因子无影响，忽略比例因子 $\frac{R}{\lambda}$ ，得到：
$\boldsymbol{ \rm w^*}=S^{-1}_w(m_1-m_2)$