机器学习领域输入的数据往往以向量的形式，但是如果向量的的维度过高，会极大消耗计算资源，而有些计算并不是必须的，所以合适的降维方法非常重要。 本文将主要从原理的角度介绍PCA和LDA这两种常见的降维方式。
[TOC]
1. PCA主成分分析
PCA(Principle Component Analysis)是降维方法中的一种非常经典的方法，属于一种线性，非监督，全局的降维算法。
1.1 如何定义主成分？基于这种定义，如何定义目标函数？对于PCA的问题如何求解？
PCA旨在用原始数据的主成分来表征原始数据，以达到降维的目的。
下面有一个二维数据的例子。
在信号处理领域，我们认为信号具有较大的方差，而噪声具有较小的方差，信噪比越大说明数据的质量越好。同理，PCA的目标就是最大化投影方差，即让数据在主轴上的投影方差最大。
对一组给定列向量${v_1,v_2, …, v_n}$，中心化后得到${x_1, x_2, …, x_n}={v_1-\mu,v_2-\mu, …, v_n-\mu}$，where $\mu=\frac{1}{n}\sum^n_{i=1}v_i$。$x_i$在$w$（单位方向向量）上的投影可以表示为$<x_i, w>=x_i^Tw$。所以我们的目标就是找到这个$w$使得$x_1, x_2, …, x_n$在$w$上的方差最大。因为中心化，易知投影之后$x_1, x_2, …, x_n$的均值$\mu’=0$（这也是中心化的意义所在），因此投影后的方差可以表示为\(\begin{equation}\begin{split}D(x)&=\frac{1}{n}\sum_{i=1}^n(x_i^Tw)^2=\frac{1}{n}\sum_{i=1}^n(x_i^Tw)^T(x_i^Tw)\\&=\frac{1}{n}\sum_{i=1}^nw^Tx_ix_i^Tw=w^T(\frac{1}{n}\sum_{i=1}^nx_ix_i^T)w\end{split}\end{equation}\)
这里我们可以发现$(\frac{1}{n}\sum_{i=1}^nx_ix_i^T)$就是样本的协方差矩阵，记作$\Sigma$。因此我们要求解的最大化问题就可以表示为 $max(w^T\Sigma w) \space\space\space s.t. \space\space w^Tw=0$
引入拉格朗日乘子，对$w$求导令其等于0，便可以推出$\Sigma w=\lambda w$，此时 $D(x)=w^T\Sigma w=\lambda w^Tw=\lambda$
所以，$x$投影后的方差就是协方差矩阵的特征值，最佳投影方向就是最大特征值对应的特征向量。
故，PCA的求解分为以下几步：
- 对样本数据进行中心化处理
- 求样本的协方差矩阵
- 对协方差矩阵进行特征值分解，将特征值按照从大到小排列
- 取特征值前d大的特征向量$w_1,w_2, … ,w_d$, 将n维样本映射到d维$\begin{equation}x’_i = \begin{bmatrix}w_1^Tx_i, w_2^Tx_i, \dots, w_d^Tx_i\end{bmatrix}^T\end{equation}$
新的$x_i’$的第d维就是$x_i$在第d个主成分$w_d$方向上的投影，通过选取最大d个特征值的特征向量，方差较小的特征被抛弃，降维后的信息占比 $\eta = \sqrt{\frac{\sum_{i=1}^d\lambda_i^2}{\sum_{i=1}^n\lambda_i^2}}$
1.2 PCA最小平方误差理论
PCA同样可以从回归的角度取理解。在高维空间中，我们实际上要找到一个d维超平面，是的数据点到这个平面的距离平方和最小。
总结
PCA是一种非常经典的降维算法，但是也有其局限性。对于非线性降维问题，我们通过核映射对PCA进行扩展得到核主成分分析(KPCA)；也可以通过流形映射的降维方法，比如等距映射，局部线性嵌入，拉普拉斯特征映射等。
2. LDA线性判别分析
LDA(Linear Discriminant Analysis)是一种监督学习算法，也常用来做降维操作。
PCA默认地将数据投影到方差最大的向量上。但是如下图，对于有标签的数据，按照下图分布的数据就可能会在降维过程中丢失特征。而LDA则会考虑到标签信息。
2.1 对于有类别标签的数据，如何设计目标函数使得降维过程中不损失类别信息？对于这种方法又该如何求解？
LDA本身是为了分类服务的，所以我们只要找到一个单位向量$w$，使得投影之后的样本能够尽可能按照原是类别分开。这里用一个二分类问题来解释。有$C_1$, $C_2$两个类别的样本，两类的均值分别为$\mu_1=\frac{1}{N_1}\sum_{x\in C_1}x$，$\mu_2=\frac{1}{N}\sum_{x\in C_2}x$，投影之后的距离可以表示为 $D(C_1, C_2)=\left\Vert{\tilde\mu_1-\tilde\mu_2}\right\Vert^2_2$, 其中$\tilde\mu_1$，$\tilde\mu_2$表示两类的中心在$w$方向上的投影向量，即$\tilde\mu_1=w^T\mu_1$，$\tilde\mu_2=w^T\mu_2$。
因此需要优化的问题就变成了 $max_x\left\Vert w^T(\mu_1-\mu_2)\right\Vert^2_2 \space\space\space s.t. \space\space w^Tw=1$.
所以当$w$方向与$(\mu_1-\mu_2)$一致的时候，这个距离变为最大。
由图(a)可以发现，如果按照最大化两类投影中心距离的原则，两类样本的投影在一定程度上会有重叠，显然不是最优解。所以我们有了图(b)中的方法，适当减少两类投影中心距离，使每类内部的方差减小。
即，LDA的核心思想是，最大化类间距离同时最小化类内距离。
我们将整个数据集的类内方差定义为各个类别的方差之和，目标函数定义为类间距离和类内距离的比值，即 $max_xJ(w)=\frac{max_x\Vert w^T(\mu_1-\mu_2)\Vert ^2_2}{D_1+D_2}$, 其中$w$为单位向量，$D_1, D_2$分别表示两个类别的方差。
\(\begin{equation} \begin{split}D_1&=\sum_{x\in C_1}(w^Tx-w^T\mu_1)^2=\sum_{x\in C_1}w^T(x-\mu_1)(x-\mu_1)^Tw\\D_2 &=\sum_{x\in C_2}w^T(x-\mu_2)(x-\mu_2)^Tw\end{split} \end{equation}\) 因此，\(\begin{equation} J(w)=max_xJ(w)=\frac{w^T(\mu_1-\mu_2)(\mu_1-\mu_2)^Tw}{\sum_{x\in C_i}w^T(x-\mu_i)(x-\mu_i)^Tw} \end{equation}\)
令类间散度矩阵为$S_B=(\mu_1-\mu_2)(\mu_1-\mu_2)$，类内散度矩阵为$S_w=\sum_{x\in C_i}(x-\mu_i)(x-\mu_i)^T$，则
$J(w)=\frac{w^TS_Bw}{w^TS_ww}$。
我们想要最大化$J(w)$，只需要对$w$求偏导数，并令其等于0，即 $\frac{\partial J(w)}{\partial w}=\frac{(\frac{\partial w^TS_Bw}{\partial w}w^TS_ww-\frac{\partial w^TS_ww}{\partial w}w^TS_Bw)}{(w^TS_ww)^2}$,
求解可得 $(w^TS_ww)S_Bw=(w^TS_Bw)S_ww$ 。
因为在简化的二分类问题中，$w^TS_ww$和$w^TS_Bw$是两个数，所以可以令$\lambda=J(w)=\frac{w^TS_Bw}{w^TS_ww}$。于是上面的解可以写为$S_Bw=\lambda S_ww，即S_w^{-1}S_Bw=\lambda w$。
综上，不难看出，最大化的目标实际上对应的是一个矩阵的特征值，于是LDA降维的过程实际上是求矩阵特征向量的问题。$J(w)$的最大值实际上就是矩阵$S_w^{-1}S_B$最大特征值，投影的方向向量就是这个特征值对应的特征向量。
对于二分类这个问题，因为$S_B=w^T(\mu_1-\mu_2)(\mu_1-\mu_2)^Tw$，所以$S_Bw$的方向与$\mu_1-\mu_2$的方向一致。如果只考虑$w$方向，那么$w=S_B^{-1}(\mu_1-\mu_2)$。所以，只需要知道样本的均值和类内方差，那么就可以快速求出最佳的投影方向$w$。
注意：虽然LDA可以对有类别数据进行降维处理，但是他对数据的分布做了一些强假设，比如数据需要服从高斯分布，各类数据的协方差相等。实际上这些条件并不一定能满足。当遇到分布复杂的数据时，可以适当使用核技巧，构建合适的核函数扩大LDA的适用范围。
2.2 LDA和PCA从应用的角度和数据原理的角度有什么区别和联系？
2.2.1 原理推导
要做对比首先要基于2.1把LDA扩展到高维，即把原始数据集有N个类别，并且目标降到d维，因此LDA的目标是找到d维投影超平面$W={{w_1,w_2,\dots,w_d }}$，使投影后的样本点满足LDA的目标——最大化类间距离并且最小化类内距离。
上图是三类样本的分布情况，$\mu_1, \mu_2, \mu_3$分别表示这三类样本的样本中心，$\mu$表示这三类样本的总体中心，$S_{wi}$表示第$i$类样本的类内散度矩阵。同时我们定义全局散度矩阵为 $S_t=\sum_{i=1}^N(x_i-\mu)(x_i-\mu)^T$。
如果把全局散度定义为类内散度和类间散度之和，即$S_t = S_b+S_w$，则类见散度矩阵可以表示为
\[\begin{equation}\begin{aligned}S_b&=S_t-S_W=\sum_{i=1}^N(x_i-\mu)(x_i-\mu)^T-\sum_{x\in C_i}(x-\mu_i)(x-\mu_i)^T\\&=\sum_{j=1}^N(\sum_{x\in C_j}(x-\mu)(x-\mu)^T)-\sum_{j=1}^N(\sum_{x\in C_j}(x-\mu_j)(x-\mu_j)^T)\\&=\sum_{j=1}^Nm_j(\mu_j-\mu)(\mu_j-\mu)^T\end{aligned}\end{equation}\]其中\(m_j\)是第$j$个类别中的样本个数，N是总类别的数量。从上式可以看出，类间散度就是每个类别中心到全局中心的加权距离。最大化类见散度就是使每个类别中心经过投影后离全局中心足够远。
所以我们可以定义最大化的目标函数为 $J(W)=\frac{tr(W^TS_bW)}{tr(W^TS_wW)}$.
其中$W$使需要求解的超平面，$W^TW=\boldsymbol{I}$，根据2.1可以类似的推出最大化$J(W)$对应了广义特征值求解的问题 $S_bw=\lambda S_ww$. 求解超平面 $W={{w_1,w_2,\dots,w_d }}$，即求解 $S_w^{-1}S_b$ 矩阵前 $d$ 个从大到小排列的特征值对应的特征向量构成的矩阵，这样就把原始数据集投影到了d维的新的空间。
综上我们适用LDA对多类别高维数据集降维的步骤可以分为：
- 计算数据集中各个类别的样本均值向量$\mu_j$，和总体样本均值向量$\mu$。
- 计算类内散度矩阵$S_w$，全局散度矩阵$S_t$和类间散度矩阵 $S_b=S_t-S-b$。
- 对矩阵$S_w^{-1}S_b$进行特征值分解，从大到小排列。
- 取前d大的特征值对应的特征向量$w_1,w_2, … ,w_d$, 将n维样本映射到d维$\begin{equation}x’_i = \begin{bmatrix}w_1^Tx_i, w_2^Tx_i, \dots, w_d^Tx_i\end{bmatrix}^T\end{equation}$。
2.2.3 LDA和PCA对比
从求解过程看，的确PCA和LDA非常相似，但是对应的原理却不大相同。
- PCA目标选取是数据投影后方差最大的方向。因为PCA的输入数据是无监督的，因此数据投影方差越大，投影后保存下来的信息量越多，主成分用于表示原始数据除去一定维度的冗余和噪声，以达到降维的目的。
- LDA目标选择是投影后数据类内方差最小，类外方差最大的方向。因为输入数据通常包含标签，为了尽可能保留标签包含的信息，所以要从数据中找到具有判别性的维度使得原始数据投影后，不同类别的数据依旧可以分开。
从应用的角度看，简单来说，对于无标签的数据使用PCA，有标签的数据使用LDA。对于复杂的问题则需要根据问题作相应的调整，比如对于非线性的数据分布，可以使用核技巧将数据映射到高维空间再做降维处理。
