LDA（分类、降维）、PCA（降维）和KPCA（升维+PCA）-蒲公英云

原文链接：https://www.jianshu.com/p/fb25e7c8d36e

线性判别分析（LDA）

LDA思想总结

线性判别分析（Linear Discriminant Analysis，LDA）是一种经典的降维方法。和主成分分析PCA不考虑样本类别输出的无监督降维技术不同，LDA是一种监督学习的降维技术，数据集的每个样本有类别输出。

**LDA分类思想**简单总结如下：

多维空间中，数据处理分类问题较为复杂，LDA算法将多维空间中的数据投影到一条直线上，将d维数据转化成1维数据进行处理。
对于训练数据，设法将多维数据投影到一条直线上，同类数据的投影点尽可能接近，异类数据点尽可能远离。
对数据进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定样本的类别。

如果用一句话概括LDA思想，即“投影后类内方差最小，类间方差最大”。

图解LDA核心思想

假设有红、蓝两类数据，这些数据特征均为二维，如下图所示。我们的目标是将这些数据投影到一维，让每一类相近的数据的投影点尽可能接近，不同类别数据尽可能远，即图中红色和蓝色数据中心之间的距离尽可能大。

![Image 1][]

[外链图片转存失败(img-YH3WFnCd-1562980711001)(./img/ch2/2.29/1.png)]

左图和右图是两种不同的投影方式。

左图思路：让不同类别的平均点距离最远的投影方式。

右图思路：让同类别的数据挨得最近的投影方式。

从上图直观看出，右图红色数据和蓝色数据在各自的区域来说相对集中，根据数据分布直方图也可看出，所以右图的投影效果好于左图，左图中间直方图部分有明显交集。

以上例子是基于数据是二维的，分类后的投影是一条直线。如果原始数据是多维的，则投影后的分类面是一低维的超平面。

二类LDA算法原理

输入：数据集 $D=\\\{(\\boldsymbol x\_1,\\boldsymbol y\_1),(\\boldsymbol x\_2,\\boldsymbol y\_2),...,(\\boldsymbol x\_m,\\boldsymbol y\_m)\\\}$ ，其中样本 $\\boldsymbol x\_i $ 是n维向量， $\\boldsymbol y\_i \\epsilon \\\{0, 1\\\}$ ，降维后的目标维度 $d$ 。定义

$N\_j(j=0,1)$ 为第 $j$ 类样本个数；

$X\_j(j=0,1)$ 为第 $j$ 类样本的集合；

$u\_j(j=0,1)$ 为第 $j$ 类样本的均值向量；

$\\sum\_j(j=0,1)$ 为第 $j$ 类样本的协方差矩阵。

其中
$u\_j = \\frac\{1\}\{N\_j\} \\sum\_\{\\boldsymbol x\\epsilon X\_j\}\\boldsymbol x(j=0,1)， \\sum\_j = \\sum\_\{\\boldsymbol x\\epsilon X\_j\}(\\boldsymbol x-u\_j)(\\boldsymbol x-u\_j)^T(j=0,1)$
假设投影直线是向量 $\\boldsymbol w$ ，对任意样本 $\\boldsymbol x\_i$ ，它在直线 $w$ 上的投影为 $\\boldsymbol w^Tx\_i$ ，两个类别的中心点 $u\_0$ , $u\_1$ 在直线 $w$ 的投影分别为 $\\boldsymbol w^Tu\_0$ 、 $\\boldsymbol w^Tu\_1$ 。

LDA的目标是让两类别的数据中心间的距离 $\\| \\boldsymbol w^Tu\_0 - \\boldsymbol w^Tu\_1 \\|^2\_2$ 尽量大，与此同时，希望同类样本投影点的协方差 $\\boldsymbol w^T \\sum\_0 \\boldsymbol w$ 、 $\\boldsymbol w^T \\sum\_1 \\boldsymbol w$ 尽量小，最小化 $\\boldsymbol w^T \\sum\_0 \\boldsymbol w - \\boldsymbol w^T \\sum\_1 \\boldsymbol w$ 。
定义
类内散度矩阵
$S\_w = \\sum\_0 + \\sum\_1 = \\sum\_\{\\boldsymbol x\\epsilon X\_0\}(\\boldsymbol x-u\_0)(\\boldsymbol x-u\_0)^T + \\sum\_\{\\boldsymbol x\\epsilon X\_1\}(\\boldsymbol x-u\_1)(\\boldsymbol x-u\_1)^T$
类间散度矩阵 $S\_b = (u\_0 - u\_1)(u\_0 - u\_1)^T$

据上分析，优化目标为
$\\mathop\{\\arg\\max\}\_\\boldsymbol w J(\\boldsymbol w) = \\frac\{\\| \\boldsymbol w^Tu\_0 - \\boldsymbol w^Tu\_1 \\|^2\_2\}\{\\boldsymbol w^T \\sum\_0\\boldsymbol w + \\boldsymbol w^T \\sum\_1\\boldsymbol w\} = \\frac\{\\boldsymbol w^T(u\_0-u\_1)(u\_0-u\_1)^T\\boldsymbol w\}\{\\boldsymbol w^T(\\sum\_0 + \\sum\_1)\\boldsymbol w\} = \\frac\{\\boldsymbol w^TS\_b\\boldsymbol w\}\{\\boldsymbol w^TS\_w\\boldsymbol w\}$
根据广义瑞利商的性质，矩阵 $S^\{-1\}\_\{w\} S\_b$ 的最大特征值为 $J(\\boldsymbol w)$ 的最大值，矩阵 $S^\{-1\}\_\{w\} S\_b$ 的最大特征值对应的特征向量即为 $\\boldsymbol w$ 。

LDA算法流程总结

**LDA算法降维**流程如下：

输入：数据集 $D = \\\{ (x\_1,y\_1),(x\_2,y\_2), ... ,(x\_m,y\_m) \\\}$ ，其中样本 $x\_i$ 是n维向量， $y\_i \\epsilon \\\{C\_1, C\_2, ..., C\_k\\\}$ ，降维后的目标维度 $d$ 。

输出：降维后的数据集 $\\overline\{D\}$ 。

步骤：

计算类内散度矩阵 $S\_w$ 。
计算类间散度矩阵 $S\_b$ 。
计算矩阵 $S^\{-1\}\_wS\_b$ 。
计算矩阵 $S^\{-1\}\_wS\_b$ 的最大的 d 个特征值。
计算 d 个特征值对应的 d 个特征向量，记投影矩阵为 W 。
转化样本集的每个样本，得到新样本 $P\_i = W^Tx\_i$ 。
输出新样本集 $\\overline\{D\} = \\\{ (p\_1,y\_1),(p\_2,y\_2),...,(p\_m,y\_m) \\\}$

LDA和PCA区别

异同点	LDA	PCA
相同点	1. 两者均可以对数据进行降维；<br />2. 两者在降维时均使用了矩阵特征分解的思想；<br />3. 两者都假设数据符合高斯分布；
不同点	有监督的降维方法；	无监督的降维方法；
	降维最多降到k-1维；	降维多少没有限制；
	可以用于降维，还可以用于分类；	只用于降维；
	选择分类性能最好的投影方向；	选择样本点投影具有最大方差的方向；
	更明确，更能反映样本间差异；	目的较为模糊；

LDA优缺点

优缺点	简要说明
优点	1. 可以使用类别的先验知识；<br />2. 以标签、类别衡量差异性的有监督降维方式，相对于PCA的模糊性，其目的更明确，更能反映样本间的差异；
缺点	1. LDA不适合对非高斯分布样本进行降维；<br />2. LDA降维最多降到分类数k-1维；<br />3. LDA在样本分类信息依赖方差而不是均值时，降维效果不好；<br />4. LDA可能过度拟合数据。

主成分分析（PCA）

主成分分析（PCA）思想总结

PCA就是将高维的数据通过线性变换投影到低维空间上去。
投影思想：找出最能够代表原始数据的投影方法。被PCA降掉的那些维度只能是那些噪声或是冗余的数据。
去冗余：去除可以被其他向量代表的线性相关向量，这部分信息量是多余的。
去噪声，去除较小特征值对应的特征向量，特征值的大小反映了变换后在特征向量方向上变换的幅度，幅度越大，说明这个方向上的元素差异也越大，要保留。
对角化矩阵，寻找极大线性无关组，保留较大的特征值，去除较小特征值，组成一个投影矩阵，对原始样本矩阵进行投影，得到降维后的新样本矩阵。
完成PCA的关键是——协方差矩阵。协方差矩阵，能同时表现不同维度间的相关性以及各个维度上的方差。协方差矩阵度量的是维度与维度之间的关系，而非样本与样本之间。
之所以对角化，因为对角化之后非对角上的元素都是0，达到去噪声的目的。对角化后的协方差矩阵，对角线上较小的新方差对应的就是那些该去掉的维度。所以我们只取那些含有较大能量(特征值)的维度，其余的就舍掉，即去冗余。

图解PCA核心思想

PCA可解决训练数据中存在数据特征过多或特征累赘的问题。核心思想是将m维特征映射到n维（n < m），这n维形成主元，是重构出来最能代表原始数据的正交特征。

假设数据集是m个n维， $(\\boldsymbol x^\{(1)\}, \\boldsymbol x^\{(2)\}, \\cdots, \\boldsymbol x^\{(m)\})$ 。如果 $n=2$ ，需要降维到 $n'=1$ ，现在想找到某一维度方向代表这两个维度的数据。下图有 $u\_1, u\_2$ 两个向量方向，但是哪个向量才是我们所想要的，可以更好代表原始数据集的呢？

![Image 1][]

[外链图片转存失败(img-lA5YN1vc-1562980711002)(./img/ch2/2.34/1.png)]

从图可看出， $u\_1$ 比 $u\_2$ 好，为什么呢？有以下两个主要评价指标：

样本点到这个直线的距离足够近。
样本点在这个直线上的投影能尽可能的分开。

如果我们需要降维的目标维数是其他任意维，则：

样本点到这个超平面的距离足够近。
样本点在这个超平面上的投影能尽可能的分开。

PCA算法推理

下面以基于最小投影距离为评价指标推理：

假设数据集是m个n维， $(x^\{(1)\}, x^\{(2)\},...,x^\{(m)\})$ ，且数据进行了中心化。经过投影变换得到新坐标为 $\{w\_1,w\_2,...,w\_n\}$ ，其中 $w$ 是标准正交基，即 $\\| w \\|\_2 = 1$ ， $w^T\_iw\_j = 0$ 。

经过降维后，新坐标为 $\\\{ w\_1,w\_2,...,w\_n \\\}$ ，其中 $n'$ 是降维后的目标维数。样本点 $x^\{(i)\}$ 在新坐标系下的投影为 $z^\{(i)\} = \\left(z^\{(i)\}\_1, z^\{(i)\}\_2, ..., z^\{(i)\}\_\{n'\} \\right)$ ，其中 $z^\{(i)\}\_j = w^T\_j x^\{(i)\}$ 是 $x^\{(i)\} $ 在低维坐标系里第 j 维的坐标。

如果用 $z^\{(i)\}$ 去恢复 $x^\{(i)\}$ ，则得到的恢复数据为 $\\widehat\{x\}^\{(i)\} = \\sum^\{n'\}\_\{j=1\} x^\{(i)\}\_j w\_j = Wz^\{(i)\}$ ，其中 $W$ 为标准正交基组成的矩阵。

考虑到整个样本集，样本点到这个超平面的距离足够近，目标变为最小化 $\\sum^m\_\{i=1\} \\| \\hat\{x\}^\{(i)\} - x^\{(i)\} \\|^2\_2$ 。对此式进行推理，可得：
$\\sum^m\_\{i=1\} \\| \\hat\{x\}^\{(i)\} - x^\{(i)\} \\|^2\_2 = \\sum^m\_\{i=1\} \\| Wz^\{(i)\} - x^\{(i)\} \\|^2\_2 \\\\ = \\sum^m\_\{i=1\} \\left( Wz^\{(i)\} \\right)^T \\left( Wz^\{(i)\} \\right) - 2\\sum^m\_\{i=1\} \\left( Wz^\{(i)\} \\right)^T x^\{(i)\} + \\sum^m\_\{i=1\} \\left( x^\{(i)\} \\right)^T x^\{(i)\} \\\\ = \\sum^m\_\{i=1\} \\left( z^\{(i)\} \\right)^T \\left( z^\{(i)\} \\right) - 2\\sum^m\_\{i=1\} \\left( z^\{(i)\} \\right)^T x^\{(i)\} + \\sum^m\_\{i=1\} \\left( x^\{(i)\} \\right)^T x^\{(i)\} \\\\ = - \\sum^m\_\{i=1\} \\left( z^\{(i)\} \\right)^T \\left( z^\{(i)\} \\right) + \\sum^m\_\{i=1\} \\left( x^\{(i)\} \\right)^T x^\{(i)\} \\\\ = -tr \\left( W^T \\left( \\sum^m\_\{i=1\} x^\{(i)\} \\left( x^\{(i)\} \\right)^T \\right)W \\right) + \\sum^m\_\{i=1\} \\left( x^\{(i)\} \\right)^T x^\{(i)\} \\\\ = -tr \\left( W^TXX^TW \\right) + \\sum^m\_\{i=1\} \\left( x^\{(i)\} \\right)^T x^\{(i)\}$

在推导过程中，分别用到了 $\\overline\{x\}^\{(i)\} = Wz^\{(i)\}$ ，矩阵转置公式 $(AB)^T = B^TA^T$ ， $W^TW = I$ ， $z^\{(i)\} = W^Tx^\{(i)\}$ 以及矩阵的迹，最后两步是将代数和转为矩阵形式。
由于 $W$ 的每一个向量 $w\_j$ 是标准正交基， $\\sum^m\_\{i=1\} x^\{(i)\} \\left( x^\{(i)\} \\right)^T$ 是数据集的协方差矩阵， $\\sum^m\_\{i=1\} \\left( x^\{(i)\} \\right)^T x^\{(i)\}$ 是一个常量。最小化 $\\sum^m\_\{i=1\} \\| \\hat\{x\}^\{(i)\} - x^\{(i)\} \\|^2\_2$ 又可等价于
$\\underbrace\{\\arg \\min\}\_W - tr \\left( W^TXX^TW \\right) s.t.W^TW = I$
利用拉格朗日函数可得到
$J(W) = -tr(W^TXX^TW) + \\lambda(W^TW - I)$
对 $W$ 求导，可得 $\-XX^TW + \\lambda W = 0$ ，也即 $XX^TW = \\lambda W$ 。 $XX^T$ 是 $n'$ 个特征向量组成的矩阵， $\\lambda$ 为 $XX^T$ 的特征值。 $W$ 即为我们想要的矩阵。
对于原始数据，只需要 $z^\{(i)\} = W^TX^\{(i)\}$ ，就可把原始数据集降维到最小投影距离的 $n'$ 维数据集。

基于最大投影方差的推导，这里就不再赘述，有兴趣的同仁可自行查阅资料。

PCA算法流程总结

输入： $n$ 维样本集 $D = \\left( x^\{(1)\},x^\{(2)\},...,x^\{(m)\} \\right)$ ，目标降维的维数 $n'$ 。

输出：降维后的新样本集 $D' = \\left( z^\{(1)\},z^\{(2)\},...,z^\{(m)\} \\right)$ 。

主要步骤如下：

对所有的样本进行中心化， $x^\{(i)\} = x^\{(i)\} - \\frac\{1\}\{m\} \\sum^m\_\{j=1\} x^\{(j)\}$ 。
计算样本的协方差矩阵 $XX^T$ 。
对协方差矩阵 $XX^T$ 进行特征值分解。
取出最大的 $n'$ 个特征值对应的特征向量 $\\\{ w\_1,w\_2,...,w\_\{n'\} \\\}$ 。
标准化特征向量，得到特征向量矩阵 $W$ 。
转化样本集中的每个样本 $z^\{(i)\} = W^T x^\{(i)\}$ 。
得到输出矩阵 $D' = \\left( z^\{(1)\},z^\{(2)\},...,z^\{(n)\} \\right)$ 。
注：在降维时，有时不明确目标维数，而是指定降维到的主成分比重阈值 $k(k \\epsilon(0,1\])$ 。假设 $n$ 个特征值为 $\\lambda\_1 \\geqslant \\lambda\_2 \\geqslant ... \\geqslant \\lambda\_n$ ，则 $n'$ 可从 $\\sum^\{n'\}\_\{i=1\} \\lambda\_i \\geqslant k \\times \\sum^n\_\{i=1\} \\lambda\_i $ 得到。

PCA算法主要优缺点

优缺点	简要说明
优点	1. 仅仅需要以方差衡量信息量，不受数据集以外的因素影响。　2.各主成分之间正交，可消除原始数据成分间的相互影响的因素。3. 计算方法简单，主要运算是特征值分解，易于实现。
缺点	1.主成分各个特征维度的含义具有一定的模糊性，不如原始样本特征的解释性强。2. 方差小的非主成分也可能含有对样本差异的重要信息，因降维丢弃可能对后续数据处理有影响。