PCA
PCA的思想
PCA顾名思义，就是找出数据里最主要的方面，用数据里最主要的方面来代替原始数据。具体的，假如我们的数据集是\(n\)维的，共有\(m\)个数据\((𝑥(1),𝑥(2),...,𝑥(𝑚))\)。我们希望将这\(m\)个数据的维度从\(n\)维降到\(n'\)维，希望这\(m\)个\(n'\)维的数据集尽可能的代表原始数据集。我们知道数据从\(n\)维降到\(n'\)维肯定会有损失，但是我们希望损失尽可能的小。那么如何让这\(n'\)维的数据尽可能表示原来的数据呢？
我们先看看最简单的情况，也就是\(n=2\)，\(n'=1\),也就是将数据从二维降维到一维。数据如下图。我们希望找到某一个维度方向，它可以代表这两个维度的数据。图中列了两个向量方向，\(u_1\)和\(𝑢_2\)，那么哪个向量可以更好的代表原始数据集呢？从直观上也可以看出，\(𝑢_1\)比\(𝑢_2\)好。
为什么\(𝑢_1\)比\(𝑢_2\)好呢？可以有两种解释，第一种解释是样本点到这个直线的距离足够近，第二种解释是样本点在这个直线上的投影能尽可能的分开。
假如我们把\(n'\)从1维推广到任意维，则我们的希望降维的标准为：样本点到这个超平面的距离足够近,或者说样本点在这个超平面上的投影能尽可能的分开。
基于上面的两种标准，我们可以得到PCA的两种等价推导。
PCA的推导:基于最小投影距离
我们首先看第一种解释的推导，即样本点到这个超平面的距离足够近。
假设\(m\)个\(n\)维数据\((𝑥^{(1)},𝑥^{(2)},...,𝑥^{(𝑚)})\)都已经进行了中心化，即\(∑_{𝑖=1}^𝑚𝑥^{(𝑖)}=0\)。经过投影变换后得到的新坐标系为\(\{𝑤_1,𝑤_2,...,𝑤_𝑛\}\),其中\(𝑤\) 是标准正交基，即\(||𝑤||^2=1,𝑤^𝑇_𝑖𝑤_𝑗=0\)。
如果我们将数据从\(n\)维降到\(n'\)维，即丢弃新坐标系中的部分坐标，则新的坐标系为\(\{𝑤_1,𝑤_2,...,𝑤_{𝑛^′}\}\),样本点\(𝑥^{(𝑖)}\)在\(n'\)维坐标系中的投影为：\(𝑧^{(𝑖)}=(𝑧^{(𝑖)}_1,𝑧^{(𝑖)}_2,...,𝑧^{(𝑖)}_{𝑛^′})^𝑇\).其中，\(𝑧^{(𝑖)}_𝑗=𝑤^𝑇_𝑗𝑥^{(𝑖)}\)是\(𝑥^{(𝑖)}\)在低维坐标系里第j维的坐标。
如果我们用\(𝑧^{(𝑖)}\)来恢复原始数据\(𝑥^{(𝑖)}\),则得到的恢复数据 \(\overline{x}^{(i)}=∑_{j=1}^{n^′}z_j^{(i)}w_j=Wz^{(i)}\),其中，\(W\)为标准正交基组成的矩阵。
现在我们考虑整个样本集，我们希望所有的样本到这个超平面的距离足够近，即最小化下式：
将这个式子进行整理，可以得到:
其中第1步用到了\(\overline{x}^{(i)}=Wz^{(i)}\),第二步用到了平方和展开，第3步用到了矩阵转置公式,第4步用到了\(z^{(i)}=W^Tx^{(i)}\)，第5步合并同类项，第6步用到了\(𝑧^{(𝑖)}=𝑊^𝑇𝑥^{(𝑖)}\)和矩阵的迹,第7步将代数和表达为矩阵形式。
注意到\(\sum\limits_{i=1}^{m}x^{(i)}x^{(i)T}\)是数据集的协方差矩阵，\(W\)的每一个向量\(𝑤_𝑗\)是标准正交基。而\(\sum\limits_{i=1}^{m} x^{(i)T}x^{(i)}\)是一个常量。最小化上式等价于：
这个最小化不难，直接观察也可以发现最小值对应的\(W\)由协方差矩阵\(𝑋𝑋^𝑇\)最大的\(n'\)个特征值对应的特征向量组成。当然用数学推导也很容易。利用拉格朗日函数可以得到
对W求导有\(−𝑋𝑋^𝑇𝑊+\lambda𝑊=0\), 整理下即为：
这样可以更清楚的看出，\(W\)为\(XX^T\)的\(n'\)个特征向量组成的矩阵，而\(λ\)为\(XX^T\)的若干特征值组成的矩阵，特征值在主对角线上，其余位置为0。当我们将数据集从\(n\)维降到\(n'\)维时，需要找到最大的\(n'\)个特征值对应的特征向量。这\(n'\)个特征向量组成的矩阵\(W\)即为我们需要的矩阵。对于原始数据集，我们只需要用\(𝑧^{(𝑖)}=𝑊^𝑇𝑥^{(𝑖)}\),就可以把原始数据集降维到最小投影距离的\(n'\)维数据集。
如果你熟悉谱聚类的优化过程，就会发现和PCA的非常类似，只不过谱聚类是求前\(k\)个最小的特征值对应的特征向量，而PCA是求前\(k\)个最大的特征值对应的特征向量。
PCA的推导:基于最大投影方差
现在我们再来看看基于最大投影方差的推导。
假设\(m\)个\(n\)维数据\((𝑥^{(1)},𝑥^{(2)},...,𝑥^{(𝑚)})\)都已经进行了中心化，即\(∑_{𝑖=1}^𝑚𝑥^{(𝑖)}=0\)。经过投影变换后得到的新坐标系为\(\{𝑤_1,𝑤_2,...,𝑤_𝑛\}\),其中\(𝑤 \)是标准正交基，即\(||𝑤||^2=1,𝑤^𝑇_𝑖𝑤_𝑗=0\)。
如果我们将数据从\(n\)维降到\(n'\)维，即丢弃新坐标系中的部分坐标，则新的坐标系为\(\{𝑤_1,𝑤_2,...,𝑤_{𝑛^′}\}\),样本点\(𝑥^{(𝑖)}\)在\(n'\)维坐标系中的投影为：\(𝑧^{(𝑖)}=(𝑧^{(𝑖)}_1,𝑧^{(𝑖)}_2,...,𝑧^{(𝑖)}_{𝑛^′})^𝑇\).其中，\(𝑧^{(𝑖)}_𝑗=𝑤^𝑇_𝑗𝑥^{(𝑖)}\)是\(𝑥^{(𝑖)}\)在低维坐标系里第\(j\)维的坐标。
对于任意一个样本\(𝑥^{(𝑖)}\)，在新的坐标系中的投影为\(𝑊^𝑇𝑥^{(𝑖)}\),在新坐标系中的投影方差为\(𝑥^{(𝑖)𝑇}𝑊𝑊^𝑇𝑥^{(𝑖)}\)，要使所有的样本的投影方差和最大，也就是最大化\(\sum\limits_{i=1}^{m}W^Tx^{(i)}x^{(i)T}W\)的迹,即：
观察第二节的基于最小投影距离的优化目标，可以发现完全一样，只是一个是加负号的最小化，一个是最大化。
利用拉格朗日函数可以得到
对W求导有\(𝑋𝑋^𝑇𝑊+\lambda𝑊=0\), 整理下即为：
和上面一样可以看出，\(W\)为\(𝑋𝑋^𝑇\)的\(n'\)个特征向量组成的矩阵，而\(−λ\)为\(𝑋𝑋^𝑇\)的若干特征值组成的矩阵，特征值在主对角线上，其余位置为0。当我们将数据集从\(n\)维降到\(n'\)维时，需要找到最大的\(n'\)个特征值对应的特征向量。这\(n'\)个特征向量组成的矩阵\(W\)即为我们需要的矩阵。对于原始数据集，我们只需要用\(z^{(i)}=W^Tx^{(i)}\),就可以把原始数据集降维到最小投影距离的\(n'\)维数据集。
PCA算法流程
从上面两节我们可以看出，求样本\(𝑥^{(𝑖)}\)的\(n'\)维的主成分其实就是求样本集的协方差矩阵\(𝑋𝑋^𝑇\)的前\(n'\)个特征值对应特征向量矩阵\(W\)，然后对于每个样本\(𝑥^{(𝑖)}\),做如下变换\(𝑧^{(𝑖)}=𝑊^𝑇𝑥^{(𝑖)}\)，即达到降维的PCA目的。
下面我们看看具体的算法流程。
输入：\(n\)维样本集\(𝐷=(𝑥^{(1)},𝑥^{(2)},...,𝑥^{(𝑚)})\)，要降维到的维数\(n'\).
输出：降维后的样本集\(𝐷′\)
- 对所有的样本进行中心化： \(x^{(i)}=x^{(i)}−\frac{1}{m}∑_{j=1}^mx^{(j)}\)
- 计算样本的协方差矩阵\(𝑋𝑋^𝑇\)
- 对矩阵\(𝑋𝑋^𝑇\)进行特征值分解
- 取出最大的\(n'\)个特征值对应的特征向量\((𝑤_1,𝑤_2,...,𝑤_{𝑛^{′}})\), 将所有的特征向量标准化后，组成特征向量矩阵\(W\)。
- 对样本集中的每一个样本\(𝑥^{(𝑖)}\),转化为新的样本\(𝑧^{(𝑖)}=𝑊^𝑇𝑥^{(𝑖)}\)
- 得到输出样本集\(𝐷^{′}=(𝑧^{(1)},𝑧^{(2)},...,𝑧^{(𝑚)})\)
有时候，我们不指定降维后的\(n'\)的值，而是换种方式，指定一个降维到的主成分比重阈值\(t\)。这个阈值\(t\)在（0,1]之间。假如我们的\(n\)个特征值为\(\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n\),则\(n'\)可以通过下式得到:
PCA实例
下面举一个简单的例子，说明PCA的过程。
假设我们的数据集有10个二维数据:
需要用PCA降到1维特征。
首先我们对样本中心化，这里样本的均值为\((1.81, 1.91)\),所有的样本减去这个均值向量后，即中心化后的数据集为:
现在我们开始求样本的协方差矩阵，由于我们是二维的，则协方差矩阵为：
对于我们的数据，求出协方差矩阵为：
求出特征值为\((0.0490833989， 1.28402771)\)，对应的特征向量分别为：\((0.735178656,0.677873399)^𝑇\)\((−0.677873399,−0.735178656)^𝑇\),由于最大的\(k=1\)个特征值为\(1.28402771\)，对于的\(k=1\)个特征向量为\((−0.677873399,−0.735178656)^T\). 则我们的\(W=(−0.677873399,−0.735178656)^𝑇\)
我们对所有的数据集进行投影\(z^{(i)}=W^Tx^{(i)}\)，得到PCA降维后的10个一维数据集为:
核主成分分析KPCA介绍
在上面的PCA算法中，我们假设存在一个线性的超平面，可以让我们对数据进行投影。但是有些时候，数据不是线性的，不能直接进行PCA降维。这里就需要用到和支持向量机一样的核函数的思想，先把数据集从\(n\)维映射到线性可分的高维\(N>n\),然后再从N维降维到一个低维度\(n'\), 这里的维度之间满足\(n'<n<N\)。
使用了核函数的主成分分析一般称之为核主成分分析(Kernelized PCA, 以下简称KPCA。假设高维空间的数据是由n维空间的数据通过映射𝜙产生。
则对于\(n\)维空间的特征分解：
映射为
通过在高维空间进行协方差矩阵的特征值分解，然后用和PCA一样的方法进行降维。一般来说，映射𝜙不用显式的计算，而是在需要计算的时候通过核函数完成。由于KPCA需要核函数的运算，因此它的计算量要比PCA大很多。
PCA算法总结
这里对PCA算法做一个总结。作为一个非监督学习的降维方法，它只需要特征值分解，就可以对数据进行压缩，去噪。因此在实际场景应用很广泛。为了克服PCA的一些缺点，出现了很多PCA的变种，比如第六节的为解决非线性降维的KPCA，还有解决内存限制的增量PCA方法Incremental PCA，以及解决稀疏数据降维的PCA方法Sparse PCA等。
PCA算法的主要优点有：
- 仅仅需要以方差衡量信息量，不受数据集以外的因素影响。
- 各主成分之间正交，可消除原始数据成分间的相互影响的因素。
- 计算方法简单，主要运算是特征值分解，易于实现。
PCA算法的主要缺点有：
- 主成分各个特征维度的含义具有一定的模糊性，不如原始样本特征的解释性强。
- 方差小的非主成分也可能含有对样本差异的重要信息，因降维丢弃可能对后续数据处理有影响。
线性判别分析LDA
在主成分分析（PCA）原理总结中，我们对降维算法PCA做了总结。这里我们就对另外一种经典的降维方法线性判别分析（Linear Discriminant Analysis, 以下简称LDA）做一个总结。LDA在模式识别领域（比如人脸识别，舰艇识别等图形图像识别领域）中有非常广泛的应用，因此我们有必要了解下它的算法原理。
在学习LDA之前，有必要将其自然语言处理领域的LDA区别开来，在自然语言处理领域， LDA是隐含狄利克雷分布（Latent Dirichlet Allocation，简称LDA），他是一种处理文档的主题模型。我们本文只讨论线性判别分析，因此后面所有的LDA均指线性判别分析。
LDA的思想
LDA是一种监督学习的降维技术，也就是说它的数据集的每个样本是有类别输出的。这点和PCA不同。PCA是不考虑样本类别输出的无监督降维技术。LDA的思想可以用一句话概括，就是“投影后类内方差最小，类间方差最大”。什么意思呢？ 我们要将数据在低维度上进行投影，投影后希望每一种类别数据的投影点尽可能的接近，而不同类别的数据的类别中心之间的距离尽可能的大。
可能还是有点抽象，我们先看看最简单的情况。假设我们有两类数据 分别为红色和蓝色，如下图所示，这些数据特征是二维的，我们希望将这些数据投影到一维的一条直线，让每一种类别数据的投影点尽可能的接近，而红色和蓝色数据中心之间的距离尽可能的大。
上图中国提供了两种投影方式，哪一种能更好的满足我们的标准呢？从直观上可以看出，右图要比左图的投影效果好，因为右图的黑色数据和蓝色数据各个较为集中，且类别之间的距离明显。左图则在边界处数据混杂。以上就是LDA的主要思想了，当然在实际应用中，我们的数据是多个类别的，我们的原始数据一般也是超过二维的，投影后的也一般不是直线，而是一个低维的超平面。
在我们将上面直观的内容转化为可以度量的问题之前，我们先了解些必要的数学基础知识，这些在后面讲解具体LDA原理时会用到。
瑞利商（Rayleigh quotient）与广义瑞利商（genralized Rayleigh quotient）
我们首先来看看瑞利商的定义。瑞利商是指这样的函数\(R(A,x)\):
其中\(𝑥\)为非零向量，而\(𝐴\)为\(𝑛×𝑛\)的Hermitan矩阵。所谓的Hermitan矩阵就是满足共轭转置矩阵和自己相等的矩阵，即\(𝐴^𝐻=𝐴\)。如果我们的矩阵A是实矩阵，则满足\(𝐴^𝑇=𝐴\)的矩阵即为Hermitan矩阵。
瑞利商\(𝑅(𝐴,𝑥)\)有一个非常重要的性质，即它的最大值等于矩阵\(𝐴\)最大的特征值，而最小值等于矩阵\(𝐴\)的最小的特征值，也就是满足
具体的证明这里就不给出了。当向量\(𝑥\)是标准正交基时，即满足\(𝑥^𝐻𝑥=1\)时，瑞利商退化为：\(𝑅(𝐴,𝑥)=𝑥^𝐻𝐴𝑥\)，这个形式在谱聚类和PCA中都有出现。
以上就是瑞利商的内容，现在我们再看看广义瑞利商。广义瑞利商是指这样的函数\(𝑅(𝐴,𝐵,𝑥)\):
其中𝑥为非零向量，而𝐴,𝐵为\(𝑛×𝑛\) 的Hermitan矩阵。𝐵为正定矩阵。它的最大值和最小值是什么呢？其实我们只要通过将其通过标准化就可以转化为瑞利商的格式。我们令\(𝑥=𝐵^{−1/2}𝑥^′\), 则分母转化为：
而分子转化为：
此时我们的\(𝑅(𝐴,𝐵,𝑥)\)转化为\(𝑅(𝐴,𝐵,𝑥′)\):
利用前面的瑞利商的性质，我们可以很快的知道，\(𝑅(𝐴,𝐵,𝑥′)\)的最大值为矩阵\(𝐵^{−1/2}𝐴𝐵^{−1/2}\)的最大特征值，或者说矩阵\(𝐵^{−1}A\)的最大特征值，而最小值为矩阵\(𝐵^{−1}𝐴\)的最小特征值。如果你看过谱聚类（spectral clustering）原理总结的话，就会发现这里使用了一样的技巧，即对矩阵进行标准化。
二类LDA原理
现在我们回到LDA的原理上，我们在第一节说讲到了LDA希望投影后希望同一种类别数据的投影点尽可能的接近，而不同类别的数据的类别中心之间的距离尽可能的大，但是这只是一个感官的度量。现在我们首先从比较简单的二类LDA入手，严谨的分析LDA的原理。
假设我们的数据集\(𝐷=\{(𝑥_1,𝑦_1),(𝑥_2,𝑦_2),...,((𝑥_𝑚,𝑦_𝑚))\}\),其中任意样本\(𝑥_ 𝑖 \)为\(n\)维向量，\(𝑦_𝑖∈\{0,1\}\)。我们定义\(𝑁_𝑗(𝑗=0,1)\)为第\(j\)类样本的个数，\(𝑋_𝑗(𝑗=0,1)\)为第\(j\)类样本的集合，而\(\mu_𝑗(𝑗=0,1)\)为第\(j\)类样本的均值向量，定义\(Σ_𝑗(𝑗=0,1)\)为第\(j\)类样本的协方差矩阵（严格说是缺少分母部分的协方差矩阵）。
\(\mu_𝑗\)的表达式为：
\(\sum_j\)的表达式为：
由于是两类数据，因此我们只需要将数据投影到一条直线上即可。假设我们的投影直线是向量\(𝑤\),则对任意一个样本\(𝑥_𝑖\),它在直线𝑤的投影为\(𝑤^𝑇𝑥_𝑖\),对于我们的两个类别的中心点\(\mu_0,\mu_1,\) 在直线\(𝑤\)的投影为\(𝑤^𝑇\mu_0\)和\(𝑤^𝑇\mu_1\)。由于LDA需要让不同类别的数据的类别中心之间的距离尽可能的大，也就是我们要最大化\(||𝑤^𝑇\mu_0−𝑤^𝑇\mu_1||^2\),同时我们希望同一种类别数据的投影点尽可能的接近，也就是要同类样本投影点的协方差\(𝑤^𝑇Σ_0𝑤\)和\(𝑤^𝑇Σ_1𝑤\)尽可能的小，即最小化\(𝑤^𝑇Σ_0𝑤+𝑤^𝑇Σ_1𝑤\)。综上所述，我们的优化目标为：
我们一般定义类内散度矩阵\(𝑆_𝑤\)为：
定义类间散度矩阵\(S_b\)为：
这样我们的优化目标重写为：
仔细一看上式，这不就是我们的广义瑞利商嘛！这就简单了，利用我们第二节讲到的广义瑞利商的性质，我们知道我们的𝐽(𝑤′)最大值为矩阵\(𝑆^{−1/2}_𝑤𝑆_𝑏𝑆^{−1/2}_𝑤\)的最大特征值，而对应的𝑤′为\(𝑆^{−1/2}_𝑤𝑆_𝑏𝑆^{−1/2}_𝑤\)的最大特征值对应的特征向量! 而\(𝑆^{−1}_𝑤𝑆_𝑏\)的特征值和\(𝑆^{−1/2}_𝑤𝑆_𝑏𝑆^{−1/2}_𝑤\)的特征值相同,\(𝑆^{−1}_𝑤𝑆_𝑏\)的特征向量𝑤和\(𝑆^{−1/2}_𝑤𝑆_𝑏𝑆^{−1/2}_𝑤\)的特征向量𝑤′满足\(𝑤=𝑆^{−1/2}_𝑤w^′\)的关系!
注意到对于二类的时候，\(𝑆_𝑏𝑤\)的方向恒平行于\(μ_0−μ_1\),不妨令\(𝑆_𝑏𝑤=\lambda(\mu_0−\mu_1)\)，将其带入：\((S_w^{-1}S_b)w=\lambda w\)，可以得到\(w=S_w^{−1}(μ_0−μ_1)\)， 也就是说我们只要求出原始二类样本的均值和方差就可以确定最佳的投影方向𝑤了。
多类LDA原理
有了二类LDA的基础，我们再来看看多类别LDA的原理。
假设我们的数据集\(𝐷=\{(𝑥_1,𝑦_1),(𝑥_2,𝑦_2),...,((𝑥_𝑚,𝑦_𝑚))\}\),其中任意样本\(𝑥_ 𝑖\)为\(n\)维向量，\(𝑦_𝑖∈\{C_1,C_2,...,C_k\}\)。我们定义\(𝑁_𝑗(𝑗=1,2,...,k)\)为第\(j\)类样本的个数，\(𝑋_𝑗(𝑗=1,2,...,k)\)为第\(j\)类样本的集合，而\(\mu_𝑗(𝑗=1,2,...,k)\)为第\(j\)类样本的均值向量，定义\(Σ_𝑗(𝑗=1,2,...,k)\)为第\(j\)类样本的协方差矩阵。
由于我们是多类向低维投影，则此时投影到的低维空间就不是一条直线，而是一个超平面了。假设我们投影到的低维空间的维度为\(d\)，对应的基向量为\((𝑤_1,𝑤_2,...𝑤_𝑑)\)，基向量组成的矩阵为\(𝑊\), 它是一个\(𝑛×𝑑\)的矩阵。
此时我们的优化目标应该可以变成为:
其中\(S_b = \sum\limits_{j=1}^{k}N_j(\mu_j-\mu)(\mu_j-\mu)^T\),\(𝜇\)为所有样本均值向量。\(S_w = \sum\limits_{j=1}^{k}S_{wj} = \sum\limits_{j=1}^{k}\sum\limits_{x \in X_j}(x-\mu_j)(x-\mu_j)^T\)。
但是有一个问题，就是\(W^TS_bW\)和\(W^TS_wW\)都是矩阵，不是标量，无法作为一个标量函数来优化！也就是说，我们无法直接用二类LDA的优化方法，怎么办呢？一般来说，我们可以用其他的一些替代优化目标来实现。
常见的一个LDA多类优化目标函数定义为：
其中\(∏_{diag}A\)为A的主对角线元素的乘积，\(𝑊\)为\(n×d\)的矩阵。
\(𝐽(𝑊)\)的优化过程可以转化为：
仔细观察上式最右边，这不就是广义瑞利商嘛！最大值是矩阵\(S_w^{−1}S_b\)的最大特征值,最大的d个值的乘积就是矩阵\(S_w^{−1}S_b\)的最大的\(d\)个特征值的乘积,此时对应的矩阵𝑊为这最大的\(d\)个特征值对应的特征向量张成的矩阵。
由于\(𝑊\)是一个利用了样本的类别得到的投影矩阵，因此它的降维到的维度\(d\)最大值为\(k-1\)。为什么最大维度不是类别数k呢？因为\(𝑆_𝑏\)中每个\(μ_j−μ\)的秩为1，因此协方差矩阵相加后最大的秩为\(k\)(矩阵的秩小于等于各个相加矩阵的秩的和)，但是由于如果我们知道前\(k-1\)个\(\mu_𝑗\)后，最后一个\(μ_k\)可以由前\(k-1\)个\(μ_j\)线性表示，因此\(S_b\)的秩最大为\(k-1\)，即特征向量最多有\(k-1\)个。
LDA算法流程
现在我们对LDA降维的流程做一个总结。
输入：数据集\(𝐷=\{(𝑥_1,𝑦_1),(𝑥_2,𝑦_2),...,((𝑥_𝑚,𝑦_𝑚))\}\),其中任意样本\(x_i\)为n维向量，\(y_i∈{C_1,C_2,...,C_k}\)，降维到的维度d。
输出：降维后的样本集\(D′\)
- 计算类内散度矩阵\(𝑆_𝑤\)
- 计算类间散度矩阵\(𝑆_𝑏\)
- 计算矩阵\(𝑆^{−1}_𝑤𝑆_𝑏\)
- 计算\(𝑆^{−1}_𝑤𝑆_𝑏\)的最大的d个特征值和对应的d个特征向量\((w_1,w_2,...w_d)\),得到投影矩阵\(𝑊\)
- 对样本集中的每一个样本特征\(𝑥_𝑖\),转化为新的样本\(𝑧_𝑖=𝑊^𝑇𝑥_𝑖\)
- 得到输出样本集\(D^′={(z_1,y_1),(z_2,y_2),...,((z_m,y_m))}\)
以上就是使用LDA进行降维的算法流程。实际上LDA除了可以用于降维以外，还可以用于分类。一个常见的LDA分类基本思想是假设各个类别的样本数据符合高斯分布，这样利用LDA进行投影后，可以利用极大似然估计计算各个类别投影数据的均值和方差，进而得到该类别高斯分布的概率密度函数。当一个新的样本到来后，我们可以将它投影，然后将投影后的样本特征分别带入各个类别的高斯分布概率密度函数，计算它属于这个类别的概率，最大的概率对应的类别即为预测类别。
由于LDA应用于分类现在似乎也不是那么流行，至少我们公司里没有用过，这里我就不多讲了。
LDA vs PCA
LDA用于降维，和PCA有很多相同，也有很多不同的地方，因此值得好好的比较一下两者的降维异同点。
首先我们看看相同点：
- 两者均可以对数据进行降维。
- 两者在降维时均使用了矩阵特征分解的思想。
- 两者都假设数据符合高斯分布。
我们接着看看不同点：
- LDA是有监督的降维方法，而PCA是无监督的降维方法
- LDA降维最多降到类别数k-1的维数，而PCA没有这个限制。
- LDA除了可以用于降维，还可以用于分类。
- LDA选择分类性能最好的投影方向，而PCA选择样本点投影具有最大方差的方向。
这点可以从下图形象的看出，在某些数据分布下LDA比PCA降维较优。
当然，某些某些数据分布下PCA比LDA降维较优，如下图所示：
LDA算法小结
LDA算法既可以用来降维，又可以用来分类，但是目前来说，主要还是用于降维。在我们进行图像识别图像识别相关的数据分析时，LDA是一个有力的工具。下面总结下LDA算法的优缺点。
LDA算法的主要优点有：
- 在降维过程中可以使用类别的先验知识经验，而像PCA这样的无监督学习则无法使用类别先验知识。
- LDA在样本分类信息依赖均值而不是方差的时候，比PCA之类的算法较优。
LDA算法的主要缺点有：
- LDA不适合对非高斯分布样本进行降维，PCA也有这个问题。
- LDA降维最多降到类别数k-1的维数，如果我们降维的维度大于k-1，则不能使用LDA。当然目前有一些LDA的进化版算法可以绕过这个问题。
- LDA在样本分类信息依赖方差而不是均值的时候，降维效果不好。
- LDA可能过度拟合数据。
奇异值分解(SVD)
奇异值分解(Singular Value Decomposition，以下简称SVD)是在机器学习领域广泛应用的算法，它不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域。是很多机器学习算法的基石。本文就对SVD的原理做一个总结，并讨论在在PCA降维算法中是如何运用运用SVD的。
回顾特征值和特征向量
我们首先回顾下特征值和特征向量的定义如下：
其中\(A\)是一个\(𝑛×𝑛\)的实对称矩阵，\(𝑥\)是一个\(𝑛\)维向量，则我们说\(λ\)是矩阵\(A\)的一个特征值，而\(𝑥\)是矩阵\(A\)的特征值\(λ\)所对应的特征向量。
求出特征值和特征向量有什么好处呢？ 就是我们可以将矩阵\(A\)特征分解。如果我们求出了矩阵\(A\)的\(𝑛\)个特征值\(λ_1≤λ_2≤...≤λ_n\),以及这\(n\) 个特征值所对应的特征向量\(\{w_1,w_2,...w_n\}\)，如果这\(n\)个特征向量线性无关，那么矩阵\(A\)就可以用下式的特征分解表示：
其中\(W\)是这\(n\)个特征向量所张成的\(n×n\)维矩阵，而\(Σ\)为这\(n\)个特征值为主对角线的\(n×n\)维矩阵。
一般我们会把\(W\)的这\(n\)个特征向量标准化，即满足\(||𝑤_𝑖||^2=1\), 或者说\(𝑤^𝑇_𝑖𝑤_𝑖=1\)，此时\(W\)的\(n\)个特征向量为标准正交基，满足\(𝑊^𝑇𝑊=𝐼\)，即\(𝑊^𝑇=𝑊^{−1}\), 也就是说\(W\)为酉矩阵。
这样我们的特征分解表达式可以写成
注意到要进行特征分解，矩阵\(A\)必须为方阵。那么如果\(A\)不是方阵，即行和列不相同时，我们还可以对矩阵进行分解吗？答案是可以，此时我们的SVD登场了。
SVD的定义
SVD也是对矩阵进行分解，但是和特征分解不同，SVD并不要求要分解的矩阵为方阵。假设我们的矩阵\(A\)是一个\(m×n\)的矩阵，那么我们定义矩阵\(A\)的SVD为：
其中\(U\)是一个\(𝑚×𝑚\)的矩阵，\(Σ\)是一个\(𝑚×𝑛\)的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，\(V\)是一个\(𝑛×𝑛\)的矩阵。\(U\)和\(V\)都是酉矩阵，即满足\(𝑈^𝑇𝑈=𝐼,𝑉^𝑇𝑉=𝐼\)。下图可以很形象的看出上面SVD的定义：
那么我们如何求出SVD分解后的\(U,Σ,V\)这三个矩阵呢？
如果我们将\(A\)的转置和\(A\)做矩阵乘法，那么会得到\(n×n\)的一个方阵\(A^TA\)。既然\(A^TA\)是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：
这样我们就可以得到矩阵\(A^TA\)的\(n\)个特征值和对应的\(n\)个特征向量\(v\)了。将\(A^TA\)的所有特征向量张成一个\(n×n\)的矩阵\(V\)，就是我们SVD公式里面的\(V\)矩阵了。一般我们将\(V\)中的每个特征向量叫做\(A\)的右奇异向量。
如果我们将\(A\)和\(A\)的转置做矩阵乘法，那么会得到\(m×m\)的一个方阵\(AA^T\)。既然\(AA^T\)是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：
这样我们就可以得到矩阵\(AA^T\)的\(m\)个特征值和对应的\(m\)个特征向量\(u\)了。将\(𝐴𝐴^𝑇\)的所有特征向量张成一个\(m×m\)的矩阵\(U\)，就是我们SVD公式里面的U矩阵了。一般我们将\(U\)中的每个特征向量叫做\(A\)的左奇异向量。
\(U\)和\(V\)我们都出来了，现在就剩下奇异值矩阵\(Σ\)没有求出了。由于\(Σ\)除了对角线上是奇异值其他位置都是0，那我们只需要求出每个奇异值\(σ\)就可以了。
我们注意到:
这样我们可以求出我们的每个奇异值，进而求出奇异值矩阵\(Σ\)。
上面还有一个问题没有讲，就是我们说\(A^TA\)的特征向量组成的就是我们SVD中的\(V\)矩阵，而\(𝐴𝐴^𝑇\)的特征向量组成的就是我们SVD中的\(U\)矩阵，这有什么根据吗？这个其实很容易证明，我们以\(V\)矩阵的证明为例。
上式证明使用了:\(𝑈^𝑇𝑈=𝐼,Σ^𝑇Σ=Σ^2\)。可以看出\(𝐴^𝑇𝐴\)的特征向量组成的的确就是我们SVD中的V矩阵。类似的方法可以得到\(𝐴𝐴^𝑇\)的特征向量组成的就是我们SVD中的\(U\)矩阵。
进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：
这样也就是说，我们可以不用\(\sigma_i=Av_i / u_i\)来计算奇异值，也可以通过求出\(𝐴^𝑇𝐴\)的特征值取平方根来求奇异值。
SVD计算举例
这里我们用一个简单的例子来说明矩阵是如何进行奇异值分解的。我们的矩阵A定义为：
我们首先求出\(𝐴^𝑇𝐴\)和\(𝐴𝐴^𝑇\)
进而求出\(𝐴^𝑇𝐴\)的特征值和特征向量：
接着求\(𝐴𝐴^𝑇\)的特征值和特征向量：
利用\(Av_i = \sigma_i u_i, i=1,2\)求奇异值：
当然，我们也可以用\(\sigma_i = \sqrt{\lambda_i}\)直接求出奇异值为\(\sqrt{3}\)和\(1\).
最终得到\(A\)的奇异值分解为：
SVD的一些性质
上面几节我们对SVD的定义和计算做了详细的描述，似乎看不出我们费这么大的力气做SVD有什么好处。那么SVD有什么重要的性质值得我们注意呢？
对于奇异值,它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说，我们也可以用最大的\(k\)个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：
其中\(k\)要比\(n\)小很多，也就是一个大的矩阵\(A\)可以用三个小的矩阵\(U_{m \times k},\Sigma_{k \times k} ,V^T_{k \times n}\)来表示。如下图所示，现在我们的矩阵\(A\)只需要灰色的部分的三个小矩阵就可以近似描述了。
由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法，比如潜在语义索引（LSI）。下面我们就对SVD用于PCA降维做一个介绍。
SVD用于PCA
在主成分分析（PCA）原理总结中，我们讲到要用PCA降维，需要找到样本协方差矩阵\(𝑋^𝑇𝑋\)的最大的d个特征向量，然后用这最大的d个特征向量张成的矩阵来做低维投影降维。可以看出，在这个过程中需要先求出协方差矩阵\(𝑋^𝑇𝑋\)，当样本数多样本特征数也多的时候，这个计算量是很大的。
注意到我们的SVD也可以得到协方差矩阵\(𝑋^𝑇𝑋\)最大的d个特征向量张成的矩阵，但是SVD有个好处，有一些SVD的实现算法可以不先求出协方差矩阵\(𝑋^𝑇𝑋\)，也能求出我们的右奇异矩阵\(V\)。也就是说，我们的PCA算法可以不用做特征分解，而是做SVD来完成。这个方法在样本量很大的时候很有效。实际上，scikit-learn的PCA算法的背后真正的实现就是用的SVD，而不是我们我们认为的暴力特征分解。
另一方面，注意到PCA仅仅使用了我们SVD的右奇异矩阵，没有使用左奇异矩阵，那么左奇异矩阵有什么用呢？
假设我们的样本是\(m×n\)的矩阵\(X\)，如果我们通过SVD找到了矩阵\(XX^T\)最大的d个特征向量张成的\(m×d\)维矩阵U，则我们如果进行如下处理：
可以得到一个\(d×n\)的矩阵\(X‘\)，这个矩阵和我们原来的\(m×n\)维样本矩阵\(X\)相比，行数从\(m\)减到了\(d\)，可见对行数进行了压缩。也就是说，左奇异矩阵可以用于行数的压缩。相对的，右奇异矩阵可以用于列数即特征维度的压缩，也就是我们的PCA降维。
SVD小结
SVD作为一个很基本的算法，在很多机器学习算法中都有它的身影，特别是在现在的大数据时代，由于SVD可以实现并行化，因此更是大展身手。SVD的原理不难，只要有基本的线性代数知识就可以理解，实现也很简单因此值得仔细的研究。当然，SVD的缺点是分解出的矩阵解释性往往不强，有点黑盒子的味道，不过这不影响它的使用。