奇异值分解
奇异值分解,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}\)
特征值与奇异值
奇异值可以通过特征值来得出:
- 求出 \(A^T A\) 的特征值和特征向量, \((A^T A)\nu_i=\lambda_i\nu_i\)
- 计算奇异值 \(\sigma_i=\sqrt{\lambda_i}\)
- 右奇异向量等于 \(\nu_i\)
- 左奇异向量等于 \({1\over \sigma_i}A\nu_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 |
示例程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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); } |
示例结果
1 2 3 4 5 6 7 |
[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表示坐标系的变换:
\(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示例
示例程序
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)
你好,向您请教一下我直接求取一个矩阵的特征向量该如何求取
有很多,比较常见的是Jacob迭代法,一次迭代O(n^3),迭代次数不清楚。
如果是手动算的话按照定义求就可以了
HI,请问一下,U,S,V得到后,怎么得到近似矩阵呢(用spark java),谢谢。