降维（2）LDA
一、线性判别分析（LDA）【监督】
“投影后类内方差最小，类间方差最大”
- https://blog.csdn.net/liuweiyuxiang/article/details/78874106
1.1 概念
线性判别分析（Linear Discriminant Analysis，LDA）是一种经典的降维方法。和主成分分析PCA不考虑样本类别输出的无监督降维技术不同，LDA是一种监督学习的降维技术，数据集的每个样本有类别输出。
LDA分类思想简单总结如下：
- 多维空间中，数据处理分类问题较为复杂，LDA算法将多维空间中的数据投影到一条直线上，将d维数据转化成1维数据进行处理。
- 对于训练数据，设法将多维数据投影到一条直线上，同类数据的投影点尽可能接近，异类数据点尽可能远离。
- 对数据进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定样本的类别。
如果用一句话概括LDA思想，即“投影后类内方差最小，类间方差最大”。
假设有红、蓝两类数据，这些数据特征均为二维，如下图所示。我们的目标是将这些数据投影到一维，让每一类相近的数据的投影点尽可能接近，不同类别数据尽可能远，即图中红色和蓝色数据中心之间的距离尽可能大。
从上图直观看出，右图红色数据和蓝色数据在各自的区域来说相对集中，根据数据分布直方图也可看出，所以右图的投影效果好于左图，左图中间直方图部分有明显交集。 以上例子是基于数据是二维的，分类后的投影是一条直线。如果原始数据是多维的，则投影后的分类面是一低维的超平面。
1.2 原理
LDA的原理是，将带上标签的数据（点），通过投影的方法，投影到维度更低的空间中，使得投影后的点，会形成按类别区分，一簇一簇的情况，相同类别的点，将会在投影后的空间中更接近。要说明白LDA，首先得弄明白线性分类器(Linear Classifier)：因为LDA是一种线性分类器。对于K-分类的一个分类问题，会有K个线性函数：
\[ y_k(x)=w_k^T x+w_{k 0} \]
当满足条件：对于所有的j，都有Yk > Yj,的时候，我们就说x属于类别k。对于每一个分类，都有一个公式去算一个分值，在所有的公式得到的分值中，找一个最大的就是所属的分类了。
上式实际上就是一种投影，是将一个高维的点投影到一条高维的直线上，LDA最求的目标是，给出一个标注了类别的数据集，投影到了一条直线之后，能够使得点尽量的按类别区分开，当k=2即二分类问题的时候，如下图所示：
红色的方形的点为0类的原始点、蓝色的方形点为1类的原始点，经过原点的那条线就是投影的直线，从图上可以清楚的看到，红色的点和蓝色的点被原点明显的分开了，这个数据只是随便画的，如果在高维的情况下，看起来会更好一点。下面我来推导一下二分类LDA问题的公式：假设用来区分二分类的直线（投影函数)为： \[ y_k(x)=w_k^T x+w_{k 0} \] 当满足条件：对于所有的j, 都有 \(Y k>Y j\),的时候, 我们就说 \(x\) 属于类别 \(k\) 。对于每一个分类, 都有一个公式去算一个 分值，在所有的公式得到的分值中, 找一个最大的就是所属的分类了。
上式实际上就是一种投影, 是将一个高维的点投影到一条高维的直线上, LDA最求的目标是, 给出一个标注了类别 的数据集, 投影到了一条直线之后, 能够使得点尽量的按类别区分开, 当 \(k=2\) 即二分类问题的时候, 如下图所示:
红色的方形的点为 0 类的原始点、蓝色的方形点为 1 类的原始点，经过原点的那条线就是投影的直线，从图上可以 清楚的看到, 红色的点和蓝色的点被原点明显的分开了, 这个数据只是随便画的, 如果在高维的情况下, 看起来会 更好一点。下面我来推导一下二分类LDA问题的公式：假设用来区分二分类的直线（投影函数)为： \[ y=w^T x \] LDA分类的一个目标是使得不同类别之间的距离越远越好, 同一类别之中的距离越近越好, 所以我们需要定义几 个关键的值。
- 类别的原始中心点为：(Di表示属于类别的点)
\[ m_i=\frac{1}{n_i} \sum_{x \in D_i} x \]
- 类别投影后的中心点为:
\[ \widetilde{m_i}=w^T m_i \]
- 衡量类别i投影后, 类别点之间的分散程度 (方差) 为:
\[ \tilde{s_i}=\sum_{y \in Y_i}\left(y-\tilde{m_i}\right)^2 \]
- 最终我们可以得到一个下面的公式, 表示LDA投影到w后的损失函数:
\[ J(w)=\frac{\left|\widetilde{m_1}-\widetilde{m_2}\right|^2}{\widetilde{s}_1^2+\widetilde{s}_2^2} \]
我们分类的目标是，使得类别内的点距离越近越好（集中），类别间的点越远越好。分母表示每一个类别内的方差之和，方差越大表示一个类别内的点越分散，分子为两个类别各自的中心点的距离的平方，我们最大化J(w)就可以求出最优的w了。想要求出最优的w，可以使用拉格朗日乘子法，但是现在我们得到的J(w)里面，w是不能被单独提出来的，我们就得想办法将w单独提出来。
我们定义一个投影前的各类别分散程度的矩阵，这个矩阵看起来有一点麻烦，其实意思是，如果某一个分类的输入点集Di里面的点距离这个分类的中心店mi越近，则Si里面元素的值就越小，如果分类的点都紧紧地围绕着mi，则Si里面的元素值越更接近0. \[ S_{i}=\sum_{x \in D_{i}}\left(x-m_{i}\right)\left(x-m_{i}\right)^{T} \] 带入 \(\mathrm{Si}\), 将 \(\mathrm{J}(\mathrm{w})\) 分母化为:
\(\tilde{s}_{i}=\sum_{x \in D_{i}}\left(w^{T} x-w^{T} m_{i}\right)^{2}=\sum_{x \in D_{i}} w^{T}\left(x-m_{i}\right)\left(x-m_{i}\right)^{T} w=w^{T} S_{i} w\)
\[{\tilde{S_{1}}}^{2}+{\tilde{S_{2}}}^{2}=w^{T}\left(S_{1}+S_{2}\right) w=w^{T} S_{w} w\]
同样的将 \(\mathrm{J}(\mathrm{w})\) 分子化为: \[ \left|\widetilde{m_{1}}-\widetilde{m_{2}}\right|^{2}=w^{T}\left(m_{1}-m_{2}\right)\left(m_{1}-m_{2}\right)^{T} w=w^{T} S_{B} w \] 这样损失函数可以化成下面的形式: \[ J(w)=\frac{w^{T} S_{B} w}{w^{T} S_{w} w} \] 这样就可以用最喜欢的拉格朗日乘子法了, 但是还有一个问题, 如果分子、分母是都可以取任意值的, 那就会 使得有无穷解, 我们将分母限制为长度为 1, 并作为拉格朗日乘子法的限制条件, 带入得到: \[ \begin{aligned} &c(w)=w^{T} S_{B} w-\lambda\left(w^{T} S_{w} w-1\right) \\ &\Rightarrow \frac{d c}{d w}=2 S_{B} w-2 \lambda S_{w} w=0 \\ &\Rightarrow S_{B} w=\lambda S_{w} w \end{aligned} \] 这样的式子就是一个求特征值的问题了。 对于 \(N(N>2)\) 分类的问题, 我就直接写出下面的结论了: \[ \begin{aligned} &S_{W}=\sum_{i=1}^{c} S_{i} \\ &S_{B}=\sum_{i=1}^{c} n_{i}\left(m_{i}-m\right)\left(m_{i}-m\right)^{T} \\ &S_{B} w_{i}=\lambda S_{w} w_{i} \end{aligned} \] 这同样是一个求特征值的问题，我们求出的第i大的特征向量，就是对应的Wi了。
这里想多谈谈特征值，特征值在纯数学、量子力学、固体力学、计算机等等领域都有广泛的应用，特征值表示的是矩阵的性质，当我们取到矩阵的前N个最大的特征值的时候，我们可以说提取到的矩阵主要的成分（这个和之后的PCA相关，但是不是完全一样的概念）。在机器学习领域，不少的地方都要用到特征值的计算，比如说图像识别、pagerank、LDA、还有之后将会提到的PCA等等。
优缺点
| 优缺点 | 简要说明 |
|---|---|
| 优点 | 1. 可以使用类别的先验知识； 2. 以标签、类别衡量差异性的有监督降维方式，相对于PCA的模糊性，其目的更明确，更能反映样本间的差异； |
| 缺点 | 1. LDA不适合对非高斯分布样本进行降维； 2. LDA降维最多降到分类数k-1维； 3. LDA在样本分类信息依赖方差而不是均值时，降维效果不好； 4. LDA可能过度拟合数据。 |