奇异值分解

奇异值分解，singular value decomposition（SVD）是线性代数中一种重要的矩阵分解。

记得大学时学习线性代数中的特征值和特征向量时，我就一直思考这个玩意算出来到底有啥用，难不成就是一群热（xian）爱（de）专（dan）研（teng）的人弄出来的数学小把戏？然后随着时间的推移，这些纯理论的东西就基本忘光了。大学的知识往往都这样的，和实际不接轨，学的时候不知道有啥用，等用的时候就忘的差不多了。

现在，在我学习线性代数后的第8年，我终于知道特征值这个玩意有啥用了。首先，先回忆下什么是特征值和特征向量吧。

特征值

对于一个方阵，其特征值和特征向量满足：

$A\nu=\lambda\nu$

求出所有的特征值和特征向量后，就得出了方阵A的特征值分解：

$A=Q\Sigma Q^{-1}$

其中 $Q$ 是特征向量按照与特征值的对应顺序组合而成 $(\nu_1,\nu_2,..)$ ， $\Sigma$ 是由特征值组成的一个对角矩阵。那么对于方阵A的特征值分解的意义又何在呢？先看下面这个例子，对于矩阵A（为了简单起见，设为对角矩阵）：

$A=\left(\begin{array}{ccc}100 & 0 & 0 \\0 & 10 & 0 \\0 & 0 & 1 \\\end{array}\right)$

其特征值为100，10和1，当一个向量与之相乘时：

$\left(\begin{array}{ccc}100 & 0 & 0 \\0 & 10 & 0 \\0 & 0 & 1 \\\end{array}\right)\left(\begin{array}{ccc}x \\y\\z\\\end{array}\right)=\left(\begin{array}{ccc}100x\\10y\\z \\\end{array}\right)$

这个式子有何意义呢？一个典型的场景是降维（Dimensionality Reduction）。如何降维呢？从上面可以看到，当xyz发生变化时，x的变化将被扩大100倍，y的变化被扩大10倍，而z则不会被扩大。那么当计算的结果不需要十分精确时，z这个变量对于我们来说意义是十分小的。当处理的数据维度十分巨大的时候，计算量变得很大，这时候就可以通过降维来去除不是那么重要的维度（如本例中的z维度），这些维度对最终的计算结果的影响远远小于其它的维度。

这个让我想起了高中物理竞赛时学的第一个知识点，就是估算：当题目中给的数据条件十分的多，导致计算变的十分复杂时，需要选择性的去除那些数量级较小的条件，使得计算量降低。现在回想，其指导思想和降维是一样的。

但是，特征值分解在现实生活中是行不通的（不由自主的想起了rework中话）。原因很简单，特征值分解局限于方阵，而现实生活中，往往都不是方阵。这时就需要奇异值分解了。

奇异值

现实世界里，为了实现类似特征值分解的计算，我们使用奇异值分解。奇异值分解适用于任何矩阵，如下所示，其中A是一个m*n的矩阵：

$A = U_{m*m} \Sigma_{m*n} V^T_{n*n}$

其中

• $U$ 是一个m*m的正交矩阵，其向量被称为左奇异向量
• $V$ 也是一个n*n的正交矩阵，其向量被成为右奇异向量
• $\Sigma$ 是一个m*n的矩阵，其对角线上的元素为奇异值，其余元素皆为0

当选取top k个奇异值时，可以将矩阵降维成为：

$A_{m*n} \approx U_{m*k} \Sigma_{k*k} V^T_{k*n}$

特征值与奇异值

奇异值可以通过特征值来得出：

1. 求出 $A^T A$ 的特征值和特征向量， $(A^T A)\nu_i=\lambda_i\nu_i$
2. 计算奇异值 $\sigma_i=\sqrt{\lambda_i}$
3. 右奇异向量等于 $\nu_i$
4. 左奇异向量等于 ${1\over \sigma_i}A\nu_i$

SVD in Spark示例

示例数据

示例程序

示例结果

主成分分析

主成分分析，Principal components analysis（PCA）是一种分析、简化数据集的技术。主成分分析经常用于减少数据集的维数，同时保持数据集中的对方差贡献最大的特征。其方法主要是通过对协方差矩阵进行特征分解，以得出数据的主成分（即特征向量）与它们的权值（即特征值）。

wiki上PCA的数学定义是：一个正交化线性变换，把数据变换到一个新的坐标系统中，使得这一数据的任何投影的第一大方差在第一个坐标（称为第一主成分）上，第二大方差在第二个坐标（第二主成分）上，依次类推。如下图所示，通过变化将X-Y坐标系映射到signal和noise上：

上图中通过坐标变化后，找出方差最大的方向为第一个坐标（signal），然后在其正交的平面上找出方差最大的方向为第二个坐标（noise）。这样就可以通过选取top k个坐标方向来达到对维度（特征）的提炼。其数学表达如下，其中A矩阵表示m行n维的数据，P表示坐标系的变换：

$A_{m*n}P_{m*n}=\widetilde A_{m*n}$

PCA将上述中的维度n进行提炼，降维成k（k<n），数学表达如下：

$A_{m*n}P_{m*k}=\widetilde A_{m*k}$

SVD在PCA中的使用

前文中提到SVD的降维公式：

$A_{m*n} \approx U_{m*k} \Sigma_{k*k} V^T_{k*n}$

若将两边同时乘以 $V_{n*k}$ ，则得到：

$A_{m*n}V_{n*k} \approx U_{m*k} \Sigma_{k*k} V^T_{k*n}V_{n*k}$

由于 $V_{n*k}$ 为正交矩阵，所以：

$A_{m*n}V_{n*k} \approx U_{m*k} \Sigma_{k*k} \approx \widetilde A_{m*k}$

就这样通过SVD神奇的实现了PCA的坐标系变换和特征的提炼。此外，SVD还可以进行数据的压缩，如下：

$U_{k*m}^T A_{m*n} \approx U_{k*m}^T U_{m*k} \Sigma_{k*k} V^T_{k*n}$

同样由于 $U_{n*k}$ 为正交矩阵，所以：

$U_{k*m}^T A_{m*n} \approx \Sigma_{k*k} V^T_{k*n} \approx \widetilde A_{k*n}$

如此则将m行数据压缩成k行数据，其含义就是去除那些十分相近的数据。

PCA in Spark示例

示例程序

示例结果

参考资料

• MLlib - Dimensionality Reduction
• Singular value decomposition
• Principal component analysis
• 机器学习中的数学(4)-线性判别分析（LDA）, 主成分分析(PCA)