如果学习分类算法，最好从线性的入手，线性分类器最简单的就是LDA，它可以看做是简化版的SVM，如果想理解SVM这种分类器，那理解LDA就是很有必要的了。谈到LDA，就不得不谈谈PCA，PCA是一个和LDA非常相关的算法，从推导、求解、到算法最终的结果，都有着相当的相似。
本次的内容主要是以推导数学公式为主，都是从算法的物理意义出发，然后一步一步最终推导到最终的式子，LDA和PCA最终的表现都是解一个矩阵特征值的问题，但是理解了如何推导，才能更深刻的理解其中的含义。本次内容要求读者有一些基本的线性代数基础，比如说特征值、特征向量的概念，空间投影，点乘等的一些基本知识等。
PCA是一种无监督的数据降维方法，与之不同的是LDA是一种有监督的数据降维方法。我们知道即使在训练样本上，我们提供了类别标签，在使用PCA模型的时候，我们是不利用类别标签的，而LDA在进行数据降维的时候是利用数据的类别标签提供的信息的。 从几何的角度来看，PCA和LDA都是讲数据投影到新的相互正交的坐标轴上。只不过在投影的过程中他们使用的约束是不同的，也可以说目标是不同的。PCA是将数据投影到方差最大的几个相互正交的方向上，以期待保留最多的样本信息。样本的方差越大表示样本的多样性越好，在训练模型的时候，我们当然希望数据的差别越大越好。否则即使样本很多但是他们彼此相似或者相同，提供的样本信息将相同，相当于只有很少的样本提供信息是有用的。样本信息不足将导致模型性能不够理想。这就是PCA降维的目标：将数据投影到方差最大的几个相互正交的方向上。这种约束有时候很有用，比如在下面这个例子：
对于这个样本集我们可以将数据投影到x轴或者y轴，但这都不是最佳的投影方向，因为这两个方向都不能最好地反映数据的分布。很明显还存在最佳的方向可以描述数据的分布趋势，那就是图中红色直线所在的方向。也是数据样本做投影，方差最大的方向。向这个方向做投影，投影后数据的方差最大，数据保留的信息最多。
但是，对于另外的一些不同分布的数据集，PCA的这个投影后方差最大的目标就不太合适了。比如对于下面图片中的数据集：
针对这个数据集，如果同样选择使用PCA，选择方差最大的方向作为投影方向，来对数据进行降维。那么PCA选出的最佳投影方向，将是图中红色直线所示的方向。这样做投影确实方差最大，但是这样做投影之后两类数据样本将混合在一起，将不再线性可分，甚至是不可分的。这对我们来说简直就是地狱，本来线性可分的样本被我们亲手变得不再可分。 图中还有一条耀眼的黄色直线，向这条直线做投影即能使数据降维，同时还能保证两类数据仍然是线性可分的。上面的这个数据集如果使用LDA降维，找出的投影方向就是黄色直线所在的方向。 这其实就是LDA的思想，或者说LDA降维的目标：将带有标签的数据降维，投影到低维空间同时满足三个条件：
1、尽可能多地保留数据样本的信息（即选择最大的特征是对应的特征向量所代表的的方向）。 2、寻找使样本尽可能好分的最佳投影方向。 3、投影后使得同类样本尽可能近，不同类样本尽可能远。
LDA模型实现基本思想是和PCA相同的，都是向低维空间做投影!
LDA最求的目标是，给出一个标注了类别的数据集，投影到了一条直线之后，能够使得点尽量的按类别区分开，当k=2即二分类问题的时候，如下图所示：
红色的方形的点为0类的原始点、蓝色的方形点为1类的原始点，经过原点的那条线就是投影的直线，从图上可以清楚的看到，红色的点和蓝色的点被原点明显的分开了，如果在高维的情况下，看起来会更好一点。
问：LDA最终要求什么？
求投影空间W。 假设要投影到d维空间，W为这最大的d个特征值对应的特征向量张成的矩阵。所以问题转化为求解特征向量w
求解过程如下：
给定数据集，令Xi、цi、∑i分别表示第i∈{0，1}类示例的集合、均值向量、协方差矩阵。
若将数据投影到直线w上，则两类样本的中心在直线上的投影分别为；若将所有样本点都投影到直线上，则两类样本的协方差分别为。
由于直线是一维空间，因此。
本着同类样例的投影点尽可能接近、异类样例的投影点尽可能远离的原则，欲使同类样例的投影点尽可能接近，可以让同类样例投影点的协方差尽可能小，即尽可能小；而欲使异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大，即尽可能大。同时考虑二者，则可得到欲最大化的目标
定义"类内散度矩阵"
以及"类间散度矩阵"
则上式J可重写为
这就是LDA欲最大化的目标，即Sw与Sb的"广义瑞利商" （Rayleigh）。根据广义瑞利商的性质，我们知道我们的J(w)最大值为矩阵的最大特征值，而对应的为的最大特征值对应的特征向量!（具体的瑞利商的知识见【附录1】）
如何求解w呢？（w向量决定投影方向）
注意到式(3.35)的分子和分母都是关于ω的二次项，因此式(3.35)的解与ω的长度无关，只与其方向有关。（why? 二次项的性质，若w是一个解，则对于任意常数α，αw也是式(3.35)的解.）
不失一般性，令，则上式J等价于
由拉格朗日乘子法，上式等价于
其中λ是拉格朗日乘子。注意到的方向恒为，不妨令
代入式 即得
如何将LDA推广到多分类任务中？
假定存在N个类，且第i类示例数为,我们先定义"全局散度矩阵"
其中μ是所有示例的均值向量。将类内散度矩阵重定义为每个类别的散度矩阵之和，即：
其中，
则有：
例如：三类问题如下直观图所示：
显然，多分类 LDA 可以有多种实现方法：使用 三者中的任何两个即可。
常见的一种实现是采用优化目标：
其中的tr()为矩阵的迹，一个n×n的对角矩阵A的主对角线（从左上方至右下方的对角线）上各个元素的总和被称为矩阵A的迹（或迹数），一般记作tr(A)。 这个优化目标实际上等价于求解N-1个w（特征向量）组合成W。
若将W视为一个投影矩阵，则多分类LDA将样本投影到N-1维空间，N-1通常远小于数据原有的属性数（维度）。于是，可通过这个投影来减小样本点的维数，且投影过程中使用了类别信息，因此LDA也常被视为一种经典的监督降维技术（可用于特征提取）。
PCA（Principal Component Analysis）是一种常用的数据分析方法。PCA通过线性变换将原始数据变换为一组各维度线性无关的表示，可用于提取数据的主要特征分量，常用于高维数据的降维。通俗讲就是将高维度数据变为低维度。例如基于电商的用户数据可能有上亿维，我们可以采用PCA把维度从亿级别降低到万级别或千级别，从而提高计算效率。
向量的内积 在开始下面的内容之前，我们需要弄懂几个基本概念，首相是向量的内积。
向量的内积我们在高中就已经学过,两个维数相同的向量的内积被定义为：
这个定义很好理解，那么内积的几何意义是什么呢，我们看个图
内积的另一种我们熟悉的表述方法为向量的模乘上向量之间的夹角的余弦值，即：
如果我们假设B的模为1，即单位向量，那么：
这里我们可以发现，内积其实就是A向量在B向量的方向上的投影的长度。
接下来我们考虑一个问题：对于空间中的所有样本点，如何找到一个超平面对所有的样本进行恰当的表达？举个例子，例如我们在二维空间内，想把数据降为一维，那么应该把样本点投影到x轴还是y轴呢？
对于这个问题，我们需要找到的超平面需满足最大可分性：样本点在这个超平面上的投影能尽可能分开，这个分开的程度我们称之为散度，散度可以采用方差或协方差来衡量（在机器学中，样本的方差较大时，对最终的结果影响会优于方差较小的样本）如图，对于方差0.2的超平面散度高于方差为0.045的超平面，因此0.2方差的超平面即为我们需要的。
这里我们再简单补充下协方差的知识：
方差是用来形容单个维度的样本的波动程度，协方差是指多个维度的样本数据的相关性，其计算公式为：
其中，绝对值越大说明相关性越高。注意，协方差不等于相关系数，相关系数是协方差除标准差，相关系数的相除操作把样本的单位去除了，因此结果更加标准化一些，实际含义类似。
PCA的首要目标是让投影后的散度最大，因此我们要对所有的超平面的投影都做一次散度的计算，并找到最大散度的超平面。为了方便计算我们需要构建协方差矩阵。
图中是一个三维的协方差矩阵，其中对角线是样本本身的协方差即方差，非对角线是不同样本之间的协方差。
注意，在PCA中，我们会对所有的数据进行中心化的操作，中心化后数据的均值为0，即：
根据我们上文提到的协方差计算公式，我们可以得到数据样本的协方差矩阵为：
我们设可投影的超平面为VV，我们要求投影的协方差，是不是可以根据我们第一条提到的向量的内积呢？因此我们可以得到投影后的值为，我们把投影后的方差计算一下
这里我们进一步的做中心化操作，因此期望值为0，所以有：
仔细看，投影的方差即是原数据样本的协方差矩阵乘。为了后续表述方便，我们设原数据样本的协方差矩阵为C，即：
到了这一步，我们获得了投影的散度的计算方法。我们再看下PCA的首要目标：让投影后的散度最大，既然是要最大化散度，那么就会涉及到我们熟悉的优化问题了，不过这里有一个限制条件，即超平面向量的模为1即：
对于有限制条件的优化问题，我们采用拉格朗日乘子法来解决，即：
对于求极值的问题，当然是求导啦，这里我们对V求导，即：
我们令导数为0，即：
对于这个公式是不是很熟悉，没错就是特征值，特征向量的定义式，其中α即是特征值，V即是特征向量，这也就解释了文章开头提到的问题，为啥PCA是求特征值与特征向量即特征值分解。
最后我们把求出来的偏导带入到f(V,α)f(V,α)中，即：
由公式可知散度的值只由α来决定，α的值越大，散度越大，也就是说我们需要找到最大的特征值与对应的特征向量。
通过上面的推导我们知道了为啥要求特征值与特征向量，那么特征向量和特征值到底有什么意义呢？
首先，我们要明确一个矩阵和一个向量相乘有什么意义？即等式左边CVCV的意义。矩阵和向量相乘实际上是把向量投影到矩阵的列空间，更通俗的理解就是对该向量做个旋转或伸缩变换，我们来看个例子。
从图中我们可以发现（X3为特征向量，X1，X2为非特征向量）：
一个矩阵和该矩阵的非特征向量相乘是对该向量的旋转变换，如AX1，AX2。
一个矩阵和该矩阵的特征向量相乘是对该向量的伸缩变换，如AX3。
再看下等式右边αV，一个标量和一个向量相乘，没错就是对一个向量的伸缩变换。
通过以上分析，我们发现，CV=αV的意思就是：特征向量在矩阵的伸缩变换下，那到底伸缩了多少倍呢？伸缩了“特征值”倍。
接下来就是我们的最后一步了，我们把所有的特征值按照降序排列，根据我们最终需要的维度d来选取前d大的特征向量，并组成一个矩阵，把原始样本数据与投影矩阵做矩阵乘法，即可得到降维后的结果。对于超参数d的选择，可采用交叉验证来选择。最后上一张PCA的流程图。
对于特征较多的数据样本，计算协方差矩阵是很耗时的操作，因此，在实践中会对数据样本做奇异值分解来代替协方差矩阵的特征值分解，感兴趣的读者可参阅其他博文。
降维对于维度较高的数据集是很有必要的，虽然部分数据被舍弃了，但是舍弃这部分信息之后能使样本的采样密度增加，这正是降维的重要动机，另一方面，当数据受到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，将他们舍弃能在一定程度上起到去噪的效果。
首先来看看瑞利商的定义。瑞利商是指这样的函数:
其中为非零向量，而为的Hermitan矩阵。所谓的Hermitan矩阵就是满足共轭转置矩阵和自己相等的矩阵，即。
如果我们的矩阵A是实矩阵，则满足的矩阵即为Hermitan矩阵。
瑞利商有一个非常重要的性质，即它的最大值等于矩阵A 最大的特征值，而最小值等于矩阵A 的最小的特征值，也就是满足:
当向量x 是标准正交基时，即满足 时，瑞利商退化为： 。 这个形式在谱聚类和PCA中都有出现。 以上就是瑞利商的内容，现在我们再看看广义瑞利商。广义瑞利商是指这样的函数: 其中x为非零向量，而A,B为n*n的Hermitan矩阵。B为正定矩阵。 它的最大值和最小值是什么呢？其实我们只要通过将其通过标准化就可以转化为瑞利商的格式。我们令
则分母转化为：
而分子转化为： 利用前面的瑞利商的性质，我们可以很快的知道 的最大值为矩阵的最大特征值，或者说矩阵
的最大特征值。而最小值为矩阵的最小特征值。