降维

  在进行特征计算时，如果维度过高，会给很多计算带来灾难性的后果，比如当维度很高的时候甚至连内积的计算都十分困难。在高维的情形下出现的数据样本稀疏，距离计算等困难问题，被称为 “维数灾难（curse of dimensionality）”。而缓解维数灾难的一个途径就是进行降维（dimension reduction），也就是通过某种数学变换将高维属性空间转变为一个低维 “子空间”（subspace），在这个子空间中样本的密度大幅度的提升，距离计算也就变得比较容易。

1. 主成分分析——PCA

  PCA 的思想就是找出数据里最主要的方面，用数据里最主要的方面来代替原始数据。具体的，加入我们希望数据是 n$n$ 维的，共有 m$m$ 个数据 (x(1),x(2),...,x(n))$(x^{(1)},x^{(2)},...,x^{(n)})$。我们希望将这 m$m$ 个数据的维度从 n 维降到 n′$n^{\prime }$ 维，我们希望这 m$m$ 个 n′$n^{\prime }$ 维的数据集尽可能的代表原始数据集。我们知道降维的过程中一定会有损失，但是我们希望损失尽可能的小。因此问题就是如何才能让这 n′$n^{\prime }$ 维的数据尽可能表示原来的数据。

  可以想象，如果存在这样的平面，那么应该有这样的特性：

• 最近重构性：样本点到这个超平面的距离都足够近
• 最大可分性：样本点在这个超平面上的投影尽可能分开

  主成分分析寻找⼀个低维空间，被称为主⼦平⾯，⽤紫⾊的线表⽰，使得数据点（红点）在⼦空
间上的正交投影能够最⼤化投影点（绿点）的⽅差。PCA的另⼀个定义基于的是投影误差的平⽅和的最
⼩值，⽤蓝线表⽰。

1.1 基于投影方差推导

  下面给出基于最大投影方差的推导过程：

  假设我们的 m 个 n 维数据 (x(1),x(2),...,x(m))$(x^{(1)},x^{(2)},...,x^{(m)})$都已经进行了中心化，也就是有 ∑mi=1x(i)=0$\sum _{i=1}^m{x}^{(i)}=0$。经过投影变换后得到的新坐标系为：{w1,w2,...,wn}$\{w_1,w_2,...,w_n\}$，其中 w$w$ 是标准正交基，也就是有 ||w||2=1,wTIwj=0$||w|{|}_2=1,w_I^T{w}_j=0$。

  如果我们将数据从 n 维降到 n′$n^{\prime }$ 维，也就是丢弃新坐标系中的部分坐标，则新的坐标系为{w1,w2,...,wn‘}$\{w_1,w_2,...,w_{n‘}\}$ ，样本点 x(i)$x^{(i)}$ 在新坐标系中的投影为 z(i)=(z(i)1,z(i)2,...,z(i)n′)$z^{(i)}=(z_1^{(i)},z_2^{(i)},...,z_{n^{\prime }}^{(i)})$，其中 z(i)j=wTjx(i)$z_j^{(i)}=w_j^T{x}^{(i)}$ 是 x(i)$x^{(i)}$ 在低维坐标系里的第 j$j$ 维的坐标。

  对于任意一个样本 x(i)$x^{(i)}$，在新坐标系中的投影为 WTx(i)$W^T{x}^{(i)}$，在新坐标系中的投影方差为 WTx(i)x(i)TW$W^T{x}^{(i)}{x}^{(i)T}W$，要使所有的样本的投影方差和最大，也就是最大化 ∑mi=1WTx(i)x(i)TW$\sum _{i=1}^m{W}^T{x}^{(i)}{x}^{(i)T}W$，也就是：

这里我们再次引入拉格朗日函数，可以得到：

我们对 w 求导可以整理为下式 ：

可以看出，w 是 XXT$X{X}^T$ 的 n′$n^{\prime }$ 个特征向量组成的矩阵，而 −λ$-\lambda$ 为 XXT$X{X}^T$ 的特征值。当我们将数据集从 n 为降到 n′$n^{\prime }$ 维时，需要找到最大的 n′$n^{\prime }$ 维特征对应的特征向量。这 n′$n^{\prime }$ 个特征向量组成的矩阵 W$W$ 也就是我们需要的矩阵。对于原始数据集，我们只需要用 z(i)=WTx(i)$z^{(i)}=W^T{x}^{(i)}$，就可以把原始数据集降到最小投影距离的 n′$n^{\prime }$ 维数据集。

1.2 PCA 算法流程

• 输入：n$n$ 维样本集 D=(x(1),(x(2),...,(x(m))$D=(x^{(1)},(x^{(2)},...,(x^{(m)})$，要降维到的维数 n′$n^{\prime }$；
• 输出：降维后的样本集 D′$D^{\prime }$；
• 过程：
  
  1. 对所有的样本进行中心化：x(i)=x(i)−1m∑mj=1x(j)$x^{(i)}=x^{(i)}-\frac{1}{m}\sum _{j=1}^m{x}^{(j)}$
  2. 计算样本的协方差矩阵 XXT$X{X}^T$
  3. 对协方差矩阵进行特征值分解
  4. 去除最大的 n′$n^{\prime }$ 个特征值对应的特征向量 (w1,w2,...,wn′)$(w_1,w_2,...,w_{n^{\prime }})$，将所有的特征向量标准化后，组成特征向量矩阵 W$W$
  5. 对样本集中的每一个样本 x(i)$x^{(i)}$，转化为新的样本 z(i)=WTx(i)$z^{(i)}=W^T{x}^{(i)}$
  6. 得到输出样本集 D′=((z(1),(z(2),...,(z(m))$D^{\prime }=((z^{(1)},(z^{(2)},...,(z^{(m)})$

  有时候，我们不指定降维后 n′$n^{\prime }$ 的值，而是换一种方式，制定一个降维到的主成分比重阈值 t$t$，这个阈值 t$t$ 在 (0,1]$(0,1]$ 之间。加入我们的 n 个特征值为 λ1≥λ2≥...≥λn′${\lambda }_1\ge {\lambda }_2\ge ...\ge {\lambda }_{n^{\prime }}$，则 n′$n^{\prime }$ 可以通过下式得到：

1.3 核主成分分析 KCPA

  在上面的 PCA 算法中，我们假设存在一个线性的超平面，可以让我们对数据进行投影。但是有些饿时候，数据不是现行的，不能直接进行 PCA 降维。这里就需要用到和支持向量机一样的核函数的思想，首先把数据集从 n 维映射到线性可分的高维 N>n，然后在从 N 维降到一个低维度 n′$n^{\prime }$，这里的维度之间满足 n′<n<N$n^{\prime }<n<N$。

  使用了核函数的主成分分析一般称之为核主成分分析——KCPA，假设高维空间的数据是由 n 为空间的数据通过映射 ϕ$\varphi$ 产生。

  则对于 n 维空间的特征分解：

  映射为：

  通过在高维空间进行协方差矩阵的特征值分解，然后用和 PCA 一样的方法进行将更为。一般来说，映射 ϕ$\varphi$ 不用显式的计算，而是在需要计算的时候通过核函数完成。由于 KPCA 需要进行核函数的运算，因此它的计算量要比 PCA 大很多。

1.4 优缺点

  PCA 作为一个非监督学习的降维方法，它只需要进行特征值分解，就可以对数据进行压缩，去噪。因此在实际场景应用很广泛。为了克服 PCA 的一些缺点，出现了很多的 PCA 的变种。

  PCA 的主要优点有：

1. 仅仅需要方差衡量信息量，不受数据集意外地因素影响。
2. 各主成分之间正交，可以消除原始数据成分之间的相互影响的因素。
3. 计算方法简单，主要运算是特征值分解，易于实现

  PCA 的主要缺点有：

1. 主成分各个特征维度的含义具有一定的模糊性，不如原始样本特征的解释性强。
2. 方差小的非主成分也可能含有对样本差异的重要信息，因降维丢弃可能对后续数据处理有影响。

1.5 LDA vs PCA

  这里再次对比一下 LDA 和 PCA

• 相同点：
  
  1. 两者都可以对数据进行降维
  2. 两者在降维时都是用了矩阵特分解的思想
  3. 两者都假设数据符合高斯分布
• 不同点：
  
  1. LDA 是有监督的降维方法，PCA 是无监督的降维方法
  2. LDA 降维醉倒降到类别数 k-1 的维数，而 PCA 没有这个限制
  3. LDA 除了可以用于降维，还可以用于分类
  4. LDA 选择分类性能最好的投影方向，而 PCA 选择样本点具有最大方差的方向。

从下面两图中可以看出 LDA 与 PCA 分别适用的情况。from 线性判别分析LDA原理总结

上面两图中分别表示适用于 LDA 和PCA 的情况。

---

2. SVD 在降维中的运用

  SVD 是矩阵分析中的一种矩阵分解方法，但是和特征值不同，SVD 并不要求分解的矩阵是方阵。假设我们的矩阵 A 是一个 m×n$m\times n$ 的矩阵，则定义 A 的 SVD 为 ：

上面的公式中， U 是一个 m×m$m\times m$ 的矩阵， Σ$\mathrm{\Sigma }$ 是一个 m×n$m\times n$ 的矩阵，且除了主对角线上的元素意外都为0，且主对角线上每个元素都称为奇异值，V 是一个n×n$n\times n$ 的矩阵，其中 U,V 均为 酉矩阵，下图可以说明这种分解，from 奇异值分解(SVD)原理与在降维中的应用

2.1 SVD 的一些性质

  对于奇异值，它和我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前 10% 甚至 1 % 的奇异值的和就占了全部奇异值之和的 99% 以上的比例。也就是说，我们也可以用最大的 k 个奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：

其中，k$k$ 比 n$n$ 小很多，也就是一个大的矩阵 A$A$ 可以用三个小的矩阵 Um×k,Σk×k,Vk×k$U_{m\times k},{\mathrm{\Sigma }}_{k\times k},V_{k\times k}$ 来表示。如下图所示，现在的矩阵 A 只需要灰色的部分的三个小矩阵就可以近似描述了。 from 奇异值分解(SVD)原理与在降维中的应用

  也正是因为这个重要的性质，使得 SVD 可以用于 PCA 降维，以此来做数据压缩和去噪。也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于 NLP 中的算法，比如潜在语义索引。

2.2 将 SVD 用于 PCA

  在主成分分析中，我们是用的是样本的协方差矩阵 XTX$X^{T}X$ 的最大的 d 个特征向量，然后用这最大的 d 个特征向量张成的矩阵来做低维投影降维。可以看出，在这个过程中首先要求出协方差矩阵 XTX$X^{T}X$，当样本数很多且样本特征数也很多的时候，计算协方差矩阵的计算量也是很大的。

  需要注意的是 SVD 也可以得到协方差矩阵 XTX$X^{T}X$ 最大的 d 个特征向量张成的矩阵，但是 SVD 有一个好处，就是有一些 SVD 实现算法可以不先求出协方差，也能求出我们的右奇异矩阵 V$V$。也就是说，我们的 PCA 算法可以不用做特征分解，而是做 SVD 来完成。这个方法在样本量很大的时候非常有效。

  另一方面，注意到 PCA 仅仅使用了 SVD 的右奇异矩阵，没有使用左奇异矩阵，在 SVD 的过程中，左奇异矩阵起到的作用是对 行 进行压缩，相对的，右奇异矩阵起到的作用是对 列 进行压缩，也就是上面说的 PCA。

2.3 总结

  SVD 作为一个基本算法，在很多机器学习算法中都有所应用。特别是现在的大数据，由于 SVD 可以实现并行化，更是如鱼得水。而且实现简单。SVD 的缺点就是分解出的矩阵解释性往往不强，但是这并不影响它的使用。

参考：

1. 奇异值分解(SVD)原理与在降维中的应用

2. 周志华——机器学习