SVD与PCA

奇异值分解

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

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

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

特征值

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

Aν=λνAν=λν

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

A=QΣQ−1A=QΣQ−1

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

A=⎛⎝⎜100000100001⎞⎠⎟A=(100000100001)

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

⎛⎝⎜100000100001⎞⎠⎟⎛⎝⎜xyz⎞⎠⎟=⎛⎝⎜100x10yz⎞⎠⎟(100000100001)(xyz)=(100x10yz)

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

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

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

奇异值

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

A=Um∗mΣm∗nVTn∗nA=Um∗mΣm∗nVn∗nT

其中

• UU 是一个m*m的正交矩阵，其向量被称为左奇异向量

• VV 也是一个n*n的正交矩阵，其向量被成为右奇异向量

• ΣΣ 是一个m*n的矩阵，其对角线上的元素为奇异值，其余元素皆为0

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

Am∗n≈Um∗kΣk∗kVTk∗nAm∗n≈Um∗kΣk∗kVk∗nT

特征值与奇异值

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

1. 求出 ATAATA 的特征值和特征向量， (ATA)νi=λiνi(ATA)νi=λiνi

2. 计算奇异值 σi=λi−−√σi=λi

3. 右奇异向量等于 νiνi

4. 左奇异向量等于 1σiAνi1σiAνi

SVD in Spark示例

示例数据

1 2 3 4

1 0 0 0 2 0 0 3 0 0 0 0 0 0 0 0 4 0 0 0

示例程序

public static void main(String[] args) {     SparkConf conf = new SparkConf().setAppName("SVDTest").setMaster("local[2]");     JavaSparkContext sc = new JavaSparkContext(conf);     JavaRDD<String> data = sc.textFile("/home/yurnom/data/svd.txt");     JavaRDD<Vector> rows = data.map(s -> {         double[] values = Arrays.asList(SPACE.split(s))               .stream()               .mapToDouble(Double::parseDouble)               .toArray();         return Vectors.dense(values);     });     RowMatrix mat = new RowMatrix(rows.rdd());     //第一个参数3意味着取top 3个奇异值，第二个参数true意味着计算矩阵U，第三个参数意味小于1.0E-9d的奇异值将被抛弃     SingularValueDecomposition<RowMatrix, Matrix> svd = mat.computeSVD(3, true, 1.0E-9d);     RowMatrix U = svd.U(); //矩阵U     Vector s = svd.s(); //奇异值     Matrix V = svd.V(); //矩阵V     System.out.println(s);     System.out.println("-------------------");     System.out.println(V); }

示例结果

[4.0,3.0,2.23606797749979] ------------------- 0.0   0.0  -0.44721359549995787   -1.0  0.0  0.0                   0.0   1.0  0.0                   0.0   0.0  0.0                   0.0   0.0  -0.8944271909999159

主成分分析

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

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

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

Am∗nPm∗n=A˜m∗nAm∗nPm∗n=A~m∗n

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

Am∗nPm∗k=A˜m∗kAm∗nPm∗k=A~m∗k

SVD在PCA中的使用

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

Am∗n≈Um∗kΣk∗kVTk∗nAm∗n≈Um∗kΣk∗kVk∗nT

若将两边同时乘以 Vn∗kVn∗k ，则得到：

Am∗nVn∗k≈Um∗kΣk∗kVTk∗nVn∗kAm∗nVn∗k≈Um∗kΣk∗kVk∗nTVn∗k

由于 Vn∗kVn∗k 为正交矩阵，所以：

Am∗nVn∗k≈Um∗kΣk∗k≈A˜m∗kAm∗nVn∗k≈Um∗kΣk∗k≈A~m∗k

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

UTk∗mAm∗n≈UTk∗mUm∗kΣk∗kVTk∗nUk∗mTAm∗n≈Uk∗mTUm∗kΣk∗kVk∗nT

同样由于 Un∗kUn∗k 为正交矩阵，所以：

UTk∗mAm∗n≈Σk∗kVTk∗n≈A˜k∗nUk∗mTAm∗n≈Σk∗kVk∗nT≈A~k∗n

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

PCA in Spark示例

示例程序

1 2 3 4 5 6

//（接上述代码） RowMatrix mat = new RowMatrix(rows.rdd()); Matrix pc = mat.computePrincipalComponents(3); //将维度降为3 RowMatrix projected = mat.multiply(pc); //坐标系转换+维度提炼 System.out.println(projected.numRows()); System.out.println(projected.numCols());

示例结果

1 2

4 3

参考资料

• MLlib - Dimensionality Reduction

• Singular value decomposition

• Principal component analysis

• 机器学习中的数学(4)-线性判别分析（LDA）, 主成分分析(PCA)

（转载本站文章请注明作者和出处 程序员的自我修养 – SelfUp.cn ，请勿用于任何商业用途）