0%

线性鉴别分析

基本思想

线性鉴别分析又被称为 Fisher 鉴别,其目标就是寻找一个 $\vec w$,使得 样本集 $D$ 投影后,类内距离最小,类间间距最大。

从上图可以直观地看出,右图方向上的 $\vec w$ 比左图方向上的 $\vec w$ 更能使 ${\vec x_i}$ 的投影值 ${\vec \lambda_i}$ 分隔开,所以我们说右图中的 $\vec w$ 明显有着更好的划分效果。

Fisher准则

按照上文中提到的基本思想,Fisher 鉴别的目标函数又被称为 Fisher 准则:

$$ \max J = \frac {类间平均距离}{类内平均距离} $$

类间距离

我们使用 $\vec \mu_i$ 来代表类别 $i$ 的样本平均值,于是有:

$$ \vec \mu_1 = \frac {1} {|C_1|} \sum_{i \in C_1} \vec x_i \\ \vec \mu_2 = \frac {1} {|C_2|} \sum_{i \in C_2} \vec x_i $$

记样本均值点 $\vec \mu_1$,$\vec \mu_2$ 在方向 $\vec w$ 上的投影为 $m_1$,$m_2$,所以:

$$ m_1 = \vec w^T \vec \mu_1
\\ m_2 = \vec w^T \vec \mu_2 $$

则类间距离为 $(m_1-m_2)^2$,于是有:

$$\begin{align} (m_1-m_2)^2 & = (m_2 - m_1)(m_2 - m_1)^T \nonumber
\\& = [\vec w^T(\vec \mu_1-\vec \mu_2)][\vec w^T(\vec \mu_1-\vec \mu_2)]^T \nonumber
\\& = \vec w^T(\vec \mu_1-\vec \mu_2)(\vec \mu_1-\vec \mu_2)^T\vec w \nonumber
\\& = \vec w^T S_b\vec w \nonumber
\end{align}$$

其中, $S_b=(\vec \mu_1-\vec \mu_2)(\vec \mu_1-\vec \mu_2)^T$ 为类间散度矩阵。

类内距离

我们用均方差来表示映射后类别内部的松散程度,作为类内距离:

$$\begin{align}
S_c^2 &= \sum_{i\in C} ||\vec w^T \vec x_i - m_C || \nonumber
\\&= \sum_{i\in C} ||\vec w^T (\vec x_i - \mu_C) || \nonumber
\\&= \sum_{i\in C} [\vec w^T(\vec x_i-\vec \mu_C)][\vec w^T(\vec x_i-\vec \mu_C)]^T \nonumber
\\&= \sum_{i\in C} \vec w^T(\vec x_i-\vec \mu_C)(\vec x_i-\vec \mu_C)^T \vec w \nonumber
\\&= \vec w^T [\sum_{i\in C} (\vec x_i-\vec \mu_C)(\vec x_i-\vec \mu_C)^T ]\vec w \nonumber
\end{align}$$

两类问题的类内平均距离:
$$\begin{align}
S_1^2 +S_2^2 &= \vec w^T [\sum_{i\in C_1} (\vec x_i-\vec \mu_1)(\vec x_i-\vec \mu_1)^T ]\vec w + \vec w^T [\sum_{i\in C_2} (\vec x_i-\vec \mu_2)(\vec x_i-\vec \mu_2)^T ]\vec w \nonumber
\\&= \vec w^T [\sum_{j=1,2}\sum_{i\in C_j} (\vec x_i-\vec \mu_j)(\vec x_i-\vec \mu_j)^T]\vec w \nonumber
\\&= \vec w^T S_w \vec w \nonumber
\end{align}$$

其中, $S_w=\sum_{j=1,2}\sum_{i\in C_j} (\vec x_i-\vec \mu_j)(\vec x_i-\vec \mu_j)^T$ 为类内平均散度矩阵。

求解过程

有了类间距离和类内平均距离,目标函数可以写成:
$$\max_w\;J(w) = \frac{(m_2 - m_1)^2}{S_1^2 + S_2^2} = \frac {\vec w^T S_b \vec w}{\vec w^T S_w \vec w}$$

写成目标函数的拉格朗日函数:

$$ L(w,\lambda) = \vec w^T S_b \vec w - \lambda(\vec w^T S_w \vec w -c) $$

对 $\vec w$ 求导:

$$\frac {\partial L(w,\lambda)} {\partial \vec w} = S_b \vec w - \lambda S_w \vec w = 0
\\ \Rightarrow S_b \vec w = \lambda S_w \vec w
\\ \Rightarrow S_w^{-1} S_b \vec w = \lambda \vec w $$

所以,最优解即为 $S_w^{-1} S_b$ 的特征向量。

但是在实际过程中,并不需要求出其特征值,因为 $S_b \vec w$ 在 $\mu_1-\mu_2$ 的方向上,把 $S_b$ 代入可以得到:

$$S_b \vec w = (\vec \mu_1-\vec \mu_2)(\vec \mu_1-\vec \mu_2)^T \vec w = (\vec \mu_1-\vec \mu_2)[(\vec \mu_1-\vec \mu_2)^T \vec w]$$

其中,$(\vec \mu_1-\vec \mu_2)^T \vec w$ 是一个标量值,所以上式等价于:

$$S_b \vec w = \beta(\vec \mu_1-\vec \mu_2)$$

代入到 $S_w^{-1} S_b \vec w = \lambda \vec w $ 中得到:

$$ S_w^{-1} \beta(\vec \mu_1-\vec \mu_2) = \lambda \vec w
\\ \Rightarrow \vec w = \frac {\beta} {\lambda} S_w^{-1}(\vec \mu_1-\vec \mu_2)
$$

其中标量值可以忽略,所以$\vec w = S_w^{-1}(\vec \mu_1-\vec \mu_2)$ ,即只需要求出原始样本的均值和方差就可以求出最佳的方向 $w$。

参考文献:
[1] 周晓飞,《统计机器学习》,中国科学院大学2017年秋季研究生课程
[2] 周晓飞,《Fisher鉴别推导过程》