LDA算法——线性判别

2021/9/12 17:07:51

编程Tag： 数据算法投影 lda PCA 判别类别

本文主要是介绍LDA算法——线性判别，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、前言

二、什么是LDA？

三、LDA原理

1.二分类问题

2.多分类问题

3.几点说明

四、算法实现

一、前言

之前我们已经介绍过PCA算法，这是一种无监督的降维方法，可以将高维数据转化为低维数据处理。然而，PCA总是能适用吗？

考虑如下数据点：

由PCA的原理我们可知，这些数据点在经PCA处理后会被映射到x轴上，如下所示：

可以发现，投影后，红色数据点和蓝色数据点并不能很好地区分开。思考其背后的原因，在这个例子中，我们的数据点有了类别标签，而PCA是一种无监督学习算法，它会对所有类别的数据点一视同仁，所以在分类问题中，PCA总是显得乏力。事实上，相比于X轴，将数据点投影到Y轴是一个更优选择：

如上图所示，将数据点投影到Y轴可以将两个类别的数据点很好地区分开来。那么我们该如何找到这种投影方式呢，下面我们将介绍一种新的降维方法——LDA算法。

二、什么是LDA？

线性判别分析（LDA），同PCA类似，也是一种降维算法，不一样的是，LDA是一种监督算法，它需要用到类别信息。LDA算法的思路同PCA一致，即通过某种线性投影，将原本高维空间中的一些数据，映射到更低维度的空间中，但LDA算法要求投影后的数据满足：1.同类别的数据之间尽可能地接近。2.不同类别的数据之间尽可能地远离。

三、LDA原理

1.二分类问题

从最简单的二分类问题开始讨论。根据LDA的投影目标，我们可以得到我们要优化的目标如下：

$J = \frac{\left \| u_1'-u_2' \right \|^2}{S_1'^2+S_2'^2}$

其中， u_1',u_2' 代表投影后两个类别的数据的中心点， S_1',S_2' 代表投影后两个类别的数据的标准差。同PCA一致，我们一般用方差来表示数据的离散散程度，观察优化目标，分子衡量的是投影后两个类别的数据中心点的距离，而分母衡量的是投影后两个类别的数据各自的离散程度。同类别的数据越接近（LDA投影目标1），分母越小，越大；不同类别的数据越远离（LDA投影目标2），分子越大，越大，目标合理。

方便起见，设为原始数据点， $u_1=\sum_{X\in Class1} \frac{X}{N},u_2=\sum_{X\in Class2} \frac{X}{N}$ 分别为原始数据的中心点，为投影向量，则有:

$u_1'=\sum_{X\in Class1} \frac{w^TX}{N}=w^Tu_1$

$u_2'=\sum_{X\in Class2}\frac{w^TX}{N}=w^Tu_2$

$S_1'^2=\frac{1}{N}\sum \left \| w^TX-u_1' \right \|^2=\sum w^T\frac{1}{N}(X-u_1)(X-u_1)^Tw=w^TS_1w$

$S_2'^2=\frac{1}{N}\sum \left \| w^TX-u_2' \right \|^2=\sum w^T\frac{1}{N}(X-u_2)(X-u_2)^Tw=w^TS_2w$

优化目标即为：

$J(w) = \frac{\left \| u_1'-u_2' \right \|^2}{S_1'^2+S_2'^2}=\frac{\left \| w^T(u_1-u_2) \right \|^2}{w^T(S_1+S_2)w}=\frac{w^T(u_1-u_2)(u_1-u_2)^Tw}{w^T(S_1+S_2)w}$

不妨设 S_B=(u_1-u_2)(u_1-u_2)^T,S_w=S_1+S_2 ，则 J(w) 可简化为 $\frac{w^TS_Bw}{w^TS_ww}$ 。

对 J(w) 求导，应有：

$\frac{d J(w)}{dw}=\frac{2S_Bw(w^TS_ww)-2S_ww(w^TS_Bw)}{\left \| w^TS_2w \right \|^2}=0$

化简，得：

S_Bw(w^TS_ww)-S_ww(w^TS_Bw)=0

等式两边同除以 w^TS_ww ，得：

$S_Bw-S_ww\frac{w^TS_Bw}{w^TS_ww}=S_Bw-S_wJw=0$

变形，得：

$S_w^{-1}S_Bw=Jw$

显然，这又是一个矩阵分解问题，是矩阵 $S_w^{-1}S_B$ 的特征值，同时也是我们优化的目标，而即为对应的特征值，也是投影向量，所以我们将矩阵分解得到的特征值从大到小排列，然后取最大的几个特征值对应的特征向量作为我们的投影向量。

观察式子 S_Bw-S_wJw=0 ，由于 S_B=(u_1-u_2)(u_1-u_2)^T ，代入，得：

(u_1-u_2)(u_1-u_2)^Tw=S_wJw

由于 (u_1-u_2)^Tw 代表的是投影后两类数据中心点间的距离，我们可以用常数代替，于是有：

$w=\frac{D}{j}S_w^{-1}(u_1-u_2)$

对于投影向量，我们只需要求得它的方向，对于它的大小（缩放程度）并无要求，所以我们最终求得的投影向量即为 $S_w^{-1}(u_1-u_2)$ 。通过这种方法，我们并不需要对矩阵进行分解便能求得投影向量，大大减少了计算量。

2.多分类问题

对二分类问题进行推广，考虑多分类问题。同样，投影的目的仍是使得同类数据点尽可能近，不同类别的数据点尽可能远。这里需要对优化目标做适当改变，如下：

$J=\frac{\sum N_i\left \| u_i'-u' \right \|^2}{\sum S_i'^2}$

其中， u_i,S_i 和二分类问题一致，仍是第i类数据的中心点和标准差，而则代表所有数据的中心， N_i 代表第i个类别的数据个数。仔细观察，可以发现，目标的分母仍为各类别数据投影后的离散程度，而分子则是投影后各类别数据中心距所有数据中心点的距离的加权平方和，同样是衡量不同类别数据点的分离程度。优化的目标同二分类问题一致，重点关注LDA投影目标，万变不离其宗。

以二分类问题为例进行验证，有：

$\begin{align} S_B&=N_1(u_1-u)(u_1-u)^T+N_2(u_2-u)(u_2-u)^T\\ &=N_1(u_1-u)(u_1-u)^T+N_2(u_2-u)(u_2-u)^T\\ &=N_1(u_1-\frac{N_1u_1+N_2u_2}{N})(u_1-\frac{N_1u_1+N_2u_2}{N})^T+N_2(u_2-\frac{N_1u_1+N_2u_2}{N})(u_2-\frac{N_1u_1+N_2u_2}{N})^T\\ &=N_1(\frac{N_2u_1-N_2u_2}{N})(\frac{N_2u_1-N_2u_2}{N})^T+N_2(\frac{N_1u_2-N_1u_1}{N})(\frac{N_1u_2-N_1u_1}{N})^T\\ &=\frac{N_1N_2^2}{N}(u_1-u_2)(u_1-u_2)^T+\frac{N_1^2N_2}{N}(u_1-u_2)(u_1-u_2)^T\\ &=\frac{N_1N_2}{N}(u_1-u_2)(u_1-u_2)^T \end{align}$

同样，我们只需要知道投影的方向，所以对于常数项 $\frac{N_1N_2}{N}$ ，其只控制投影后数据点的缩放，并不影响最终结果，可以忽略。可以发现，用多分类问题的公式计算出来的结果同二分类的计算公式完全一致。

3.几点说明

(1).维度必减少

PCA算法降维可以理解为旋转坐标轴，新的坐标下每条轴作为一个维度也即成分，对于差距不大的维度可以略去从而达到降维的目的，也就是说实际上PCA算法可以将N维数据仍然变换为N维数据，然后可视情况删减维度。但LDA算法不尽然，使用LDA算法时，新的坐标维度必会减少。

以二分类为例，观察式子 $S_w^{-1}S_Bw=Jw$ ，由于 S_B=(u_1-u_2)(u_1-u_2)^T ，可知 S_B 为奇异矩阵（它的秩最多为C-1)，从而可以知道 $S_w^{-1}S_B$ 也必为奇异矩阵，所以它分解后必有一个特征值为0，我们只能得到C-1个投影向量，C为类别个数。

(2).投影后各维度之间不一定正交

$S_w^{-1}S_B$ 不一定是实对称矩阵，所以它分解后得到的特征向量未必正交。

(3).可能无解

当样本点个数少于样本维度时， S_w 会变为奇异矩阵，无法求逆。在这种情况下可能需要先用PCA降维，再使用LDA。

(4).无法适用

LDA并不是万能的，当同类别数据组成对角时，如下所示：