线性判别分析（LDA）
1. LDA思想总结
线性判别分析LDA, 是一种经典的降维方法。和主成分分析PCA不考虑样本类别输出的无监督降维技术不同，LDA是一种监督学习的降维技术，数据集的每个样本有类别输出。
LDA分类思想简单总结如下：
- 多维空间中，数据处理分类问题较为复杂，LDA算法将多维空间中的数据投影到一条直线上，将d维数据转化成1维数据进行处理。
- 对于训练数据，设法将多维数据投影到一条直线上，同类数据的投影点尽可能接近，异类数据点尽可能远离。
- 对数据进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定样本的类别。 即“投影后类内方差最小，类间方差最大”。
左图思路：让不同类别的平均点距离最远的投影方式。
右图思路：让同类别的数据挨得最近的投影方式。
从上图直观看出，右图红色数据和蓝色数据在各自的区域来说相对集中，根据数据分布直方图也可看出，所以右图的投影效果好于左图，左图中间直方图部分有明显交集。
以上例子是基于数据是二维的，分类后的投影是一条直线。如果原始数据是多维的，则投影后的分类面是一低维的超平面。
2. LDA算法数学推导
输入：数据集 D={(x1,y1),(x2,y2)……..(xm,ym)},其中样本xi 是n维向量，yi属于{0,1}，降维后的目标维度 d。定义:
Uj为一类数据的中心点,假设投影直线是向量 w，对任意样本xi，它在直线 w上的投影为 w^t xi，两个类别的中心点 u0 , u1在直线 w 的投影分别为 w^tu0 、w^t u1。
定义内散度矩阵：
定义类间散度矩阵:
所以设定优化的目标为：
根据广义瑞利商的性质，矩阵Sw^-1Sb 的最大特征值为 J(w) 的最大值，矩阵Sw^-1Sb 的最大特征值对应的特征向量即为 w。
3. LDA算法流程
LDA算法降维流程如下：
步骤：
- 计算类内散度矩阵 Sw。
- 计算类间散度矩阵 Sb 。
- 计算矩阵 Sw^-1 Sb 。
- 计算矩阵 Sw^-1 Sb 的最大的 d 个特征值。
- 计算 d 个特征值对应的 d 个特征向量，记投影矩阵为 W 。
- 转化样本集的每个样本，得到新样本 pi=W^T*xi。
- 输出新样本集
###