降维

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

1. 主成分分析——PCA

  PCA 的思想就是找出数据里最主要的方面，用数据里最主要的方面来代替原始数据。具体的，加入我们希望数据是 n n <script type="math/tex" id="MathJax-Element-86">n</script> 维的，共有 m$m$<script type="math/tex" id="MathJax-Element-87">m</script> 个数据 (x(1),x(2),...,x(n)) ( x ( 1 ) , x ( 2 ) , . . . , x ( n ) ) <script type="math/tex" id="MathJax-Element-88">(x^{(1)},x^{(2)},...,x^{(n)})</script>。我们希望将这 m m <script type="math/tex" id="MathJax-Element-89">m</script> 个数据的维度从 n 维降到 n′$n^{\prime }$<script type="math/tex" id="MathJax-Element-90">n'</script> 维，我们希望这 m m <script type="math/tex" id="MathJax-Element-91">m</script> 个 n′$n^{\prime }$<script type="math/tex" id="MathJax-Element-92">n'</script> 维的数据集尽可能的代表原始数据集。我们知道降维的过程中一定会有损失，但是我们希望损失尽可能的小。因此问题就是如何才能让这 n′ n ′ <script type="math/tex" id="MathJax-Element-93">n'</script> 维的数据尽可能表示原来的数据。

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

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

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

1.1 基于投影方差推导

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

  假设我们的 m 个 n 维数据 (x(1),x(2),...,x(m)) ( x ( 1 ) , x ( 2 ) , . . . , x ( m ) ) <script type="math/tex" id="MathJax-Element-9">(x^{(1)},x^{(2)},...,x^{(m)})</script>都已经进行了中心化，也就是有 ∑mi=1x(i)=0 ∑ i = 1 m x ( i ) = 0 <script type="math/tex" id="MathJax-Element-10">\sum_{i=1}^mx^{(i)}=0</script>。经过投影变换后得到的新坐标系为： {w1,w2,...,wn} { w 1 , w 2 , . . . , w n } <script type="math/tex" id="MathJax-Element-11">\{w_1,w_2,...,w_n\}</script>，其中 w w <script type="math/tex" id="MathJax-Element-12">w</script> 是标准正交基，也就是有 ||w||2=1,wTIwj=0$||w|{|}_2=1,w_I^T{w}_j=0$<script type="math/tex" id="MathJax-Element-13">||w||_2=1,w_I^Tw_j=0</script>。

  如果我们将数据从 n 维降到 n′ n ′ <script type="math/tex" id="MathJax-Element-14">n'</script> 维，也就是丢弃新坐标系中的部分坐标，则新的坐标系为 {w1,w2,...,wn‘} { w 1 , w 2 , . . . , w n ‘ } <script type="math/tex" id="MathJax-Element-15">\{w_1,w_2,...,w_{n‘}\}</script> ，样本点 x(i) x ( i ) <script type="math/tex" id="MathJax-Element-16">x^{(i)}</script> 在新坐标系中的投影为 z(i)=(z(i)1,z(i)2,...,z(i)n′) z ( i ) = ( z 1 ( i ) , z 2 ( i ) , . . . , z n ′ ( i ) ) <script type="math/tex" id="MathJax-Element-17">z^{(i)}=(z^{(i)}_1,z^{(i)}_2,...,z^{(i)}_{n'})</script>，其中 z(i)j=wTjx(i) z j ( i ) = w j T x ( i ) <script type="math/tex" id="MathJax-Element-18">z_j^{(i)}=w_j^Tx^{(i)}</script> 是 x(i) x ( i ) <script type="math/tex" id="MathJax-Element-19">x^{(i)}</script> 在低维坐标系里的第 j j <script type="math/tex" id="MathJax-Element-20">j</script> 维的坐标。

  对于任意一个样本 x(i)$x^{(i)}$<script type="math/tex" id="MathJax-Element-21">x^{(i)}</script>，在新坐标系中的投影为 WTx(i) W T x ( i ) <script type="math/tex" id="MathJax-Element-22">W^Tx^{(i)}</script>，在新坐标系中的投影方差为 WTx(i)x(i)TW W T x ( i ) x ( i ) T W <script type="math/tex" id="MathJax-Element-23">W^Tx^{(i)}x^{(i)T}W</script>，要使所有的样本的投影方差和最大，也就是最大化 ∑mi=1WTx(i)x(i)TW ∑ i = 1 m W T x ( i ) x ( i ) T W <script type="math/tex" id="MathJax-Element-24">\sum_{i=1}^mW^Tx^{(i)}x^{(i)T}W</script>，也就是：

<script type="math/tex; mode=display" id="MathJax-Element-25"> arg\ max_W\ tr(W^TXX^TW)\ \ \ \ s.t.W^TW=I </script>
这里我们再次引入拉格朗日函数，可以得到：
<script type="math/tex; mode=display" id="MathJax-Element-26"> J(W)=tr(W^TXX^TW)+\lambda(W^TW-I) </script>
我们对 w 求导可以整理为下式 ：
<script type="math/tex; mode=display" id="MathJax-Element-27"> XX^TW=(-\lambda)W </script>
可以看出，w 是 XXT X X T <script type="math/tex" id="MathJax-Element-28">XX^T</script> 的 n′ n ′ <script type="math/tex" id="MathJax-Element-29">n'</script> 个特征向量组成的矩阵，而 −λ − λ <script type="math/tex" id="MathJax-Element-30">-\lambda</script> 为 XXT X X T <script type="math/tex" id="MathJax-Element-31">XX^T</script> 的特征值。当我们将数据集从 n 为降到 n′ n ′ <script type="math/tex" id="MathJax-Element-32">n'</script> 维时，需要找到最大的 n′ n ′ <script type="math/tex" id="MathJax-Element-33">n'</script> 维特征对应的特征向量。这 n′ n ′ <script type="math/tex" id="MathJax-Element-34">n'</script> 个特征向量组成的矩阵 W W <script type="math/tex" id="MathJax-Element-35">W</script> 也就是我们需要的矩阵。对于原始数据集，我们只需要用 z(i)=WTx(i)$z^{(i)}=W^T{x}^{(i)}$<script type="math/tex" id="MathJax-Element-36">z^{(i)}=W^Tx^{(i)}</script>，就可以把原始数据集降到最小投影距离的 n′ n ′ <script type="math/tex" id="MathJax-Element-37">n'</script> 维数据集。

1.2 PCA 算法流程

• 输入： n n <script type="math/tex" id="MathJax-Element-38">n</script> 维样本集 D=(x(1),(x(2),...,(x(m))$D=(x^{(1)},(x^{(2)},...,(x^{(m)})$<script type="math/tex" id="MathJax-Element-39">D=(x^{(1)},(x^{(2)},...,(x^{(m)})</script>，要降维到的维数 n′ n ′ <script type="math/tex" id="MathJax-Element-40">n'</script>；
• 输出：降维后的样本集 D′ D ′ <script type="math/tex" id="MathJax-Element-41">D'</script>；
• 过程：
  
  1. 对所有的样本进行中心化： x(i)=x(i)−1m∑mj=1x(j) x ( i ) = x ( i ) − 1 m ∑ j = 1 m x ( j ) <script type="math/tex" id="MathJax-Element-42">x^{(i)}=x^{(i)}-\frac{1}{m}\sum_{j=1}^mx^{(j)}</script>
  2. 计算样本的协方差矩阵 XXT X X T <script type="math/tex" id="MathJax-Element-43">XX^T</script>
  3. 对协方差矩阵进行特征值分解
  4. 去除最大的 n′ n ′ <script type="math/tex" id="MathJax-Element-44">n'</script> 个特征值对应的特征向量 (w1,w2,...,wn′) ( w 1 , w 2 , . . . , w n ′ ) <script type="math/tex" id="MathJax-Element-45">(w_1,w_2,...,w_{n'})</script>，将所有的特征向量标准化后，组成特征向量矩阵 W W <script type="math/tex" id="MathJax-Element-46">W</script>
  5. 对样本集中的每一个样本 x(i)$x^{(i)}$<script type="math/tex" id="MathJax-Element-47">x^{(i)}</script>，转化为新的样本 z(i)=WTx(i) z ( i ) = W T x ( i ) <script type="math/tex" id="MathJax-Element-48">z^{(i)}=W^Tx^{(i)}</script>
  6. 得到输出样本集 D′=((z(1),(z(2),...,(z(m)) D ′ = ( ( z ( 1 ) , ( z ( 2 ) , . . . , ( z ( m ) ) <script type="math/tex" id="MathJax-Element-49">D'=((z^{(1)},(z^{(2)},...,(z^{(m)})</script>

  有时候，我们不指定降维后 n′ n ′ <script type="math/tex" id="MathJax-Element-50">n'</script> 的值，而是换一种方式，制定一个降维到的主成分比重阈值 t t <script type="math/tex" id="MathJax-Element-51">t</script>，这个阈值 t$t$<script type="math/tex" id="MathJax-Element-52">t</script> 在 (0,1] ( 0 , 1 ] <script type="math/tex" id="MathJax-Element-53">(0,1]</script> 之间。加入我们的 n 个特征值为 λ1≥λ2≥...≥λn′ λ 1 ≥ λ 2 ≥ . . . ≥ λ n ′ <script type="math/tex" id="MathJax-Element-54">\lambda_1\geq\lambda_2\geq...\geq\lambda_{n'}</script>，则 n′ n ′ <script type="math/tex" id="MathJax-Element-55">n'</script> 可以通过下式得到：

<script type="math/tex; mode=display" id="MathJax-Element-56"> \frac{\sum_{i=1}^{n'}\lambda_i}{\sum_{i=1}^n\lambda_i}\geq t </script>

1.3 核主成分分析 KCPA

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

  使用了核函数的主成分分析一般称之为核主成分分析——KCPA，假设高维空间的数据是由 n 为空间的数据通过映射 ϕ ϕ <script type="math/tex" id="MathJax-Element-59">\phi</script> 产生。

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

<script type="math/tex; mode=display" id="MathJax-Element-60"> \sum_{i=1}^mx^{(i)}x^{(i)T}W=\lambda W </script>
  映射为：
<script type="math/tex; mode=display" id="MathJax-Element-61"> \sum_{i=1}^m\phi(x^{(i)})\phi(x^{(i)})^TW=\lambda W </script>
  通过在高维空间进行协方差矩阵的特征值分解，然后用和 PCA 一样的方法进行将更为。一般来说，映射 ϕ ϕ <script type="math/tex" id="MathJax-Element-62">\phi</script> 不用显式的计算，而是在需要计算的时候通过核函数完成。由于 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 × n <script type="math/tex" id="MathJax-Element-63">m\times n</script> 的矩阵，则定义 A 的 SVD 为 ：

<script type="math/tex; mode=display" id="MathJax-Element-64"> A=U\Sigma V^T </script>
上面的公式中， U 是一个 m×m m × m <script type="math/tex" id="MathJax-Element-65">m\times m</script> 的矩阵， Σ Σ <script type="math/tex" id="MathJax-Element-66">\Sigma</script> 是一个 m×n m × n <script type="math/tex" id="MathJax-Element-67">m\times n</script> 的矩阵，且除了主对角线上的元素意外都为0，且主对角线上每个元素都称为奇异值，V 是一个 n×n n × n <script type="math/tex" id="MathJax-Element-68">n\times n</script> 的矩阵，其中 U,V 均为 酉矩阵，下图可以说明这种分解，from 奇异值分解(SVD)原理与在降维中的应用

2.1 SVD 的一些性质

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

<script type="math/tex; mode=display" id="MathJax-Element-69"> A_{m\times n}=U_{m\times m}\Sigma_{m\times n}V_{n\times n}^T\approx U_{m\times k}\Sigma_{k\times k}V_{n\times k}^T </script>
其中， k k <script type="math/tex" id="MathJax-Element-70">k</script> 比 n$n$<script type="math/tex" id="MathJax-Element-71">n</script> 小很多，也就是一个大的矩阵 A A <script type="math/tex" id="MathJax-Element-72">A</script> 可以用三个小的矩阵 Um×k,Σk×k,Vk×k$U_{m\times k},{\mathrm{\Sigma }}_{k\times k},V_{k\times k}$<script type="math/tex" id="MathJax-Element-73">U_{m\times k},\Sigma_{k\times k},V_{k\times k}</script> 来表示。如下图所示，现在的矩阵 A 只需要灰色的部分的三个小矩阵就可以近似描述了。 from 奇异值分解(SVD)原理与在降维中的应用

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

2.2 将 SVD 用于 PCA

  在主成分分析中，我们是用的是样本的协方差矩阵 XTX X T X <script type="math/tex" id="MathJax-Element-74">X^TX</script> 的最大的 d 个特征向量，然后用这最大的 d 个特征向量张成的矩阵来做低维投影降维。可以看出，在这个过程中首先要求出协方差矩阵 XTX X T X <script type="math/tex" id="MathJax-Element-75">X^TX</script>，当样本数很多且样本特征数也很多的时候，计算协方差矩阵的计算量也是很大的。

  需要注意的是 SVD 也可以得到协方差矩阵 XTX X T X <script type="math/tex" id="MathJax-Element-76">X^TX</script> 最大的 d 个特征向量张成的矩阵，但是 SVD 有一个好处，就是有一些 SVD 实现算法可以不先求出协方差，也能求出我们的右奇异矩阵 V V <script type="math/tex" id="MathJax-Element-77"></script>。也就是说，我们的 PCA 算法可以不用做特征分解，而是做 SVD 来完成。这个方法在样本量很大的时候非常有效。

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

2.3 总结

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

参考：

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

2. 周志华——机器学习