程序员的自我修养
Home » Apache Spark, 机器学习 » SVD与PCA

SVD与PCA

2条评论10,733次浏览

奇异值分解

奇异值分解,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上:
pca

上图中通过坐标变化后,找出方差最大的方向为第一个坐标(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示例

示例程序

示例结果

参考资料

(转载本站文章请注明作者和出处 程序员的自我修养 – SelfUp.cn ,请勿用于任何商业用途)
2条评论
  1. sunddenly说道:

    你好,向您请教一下我直接求取一个矩阵的特征向量该如何求取

发表评论


profile
  • 文章总数:78篇
  • 评论总数:252条
  • 分类总数:31个
  • 标签总数:43个
  • 运行时间:946天

大家好,欢迎来到selfup.cn。

这不是一个只谈技术的博客,这里记录我成长的点点滴滴,coding、riding and everthing!

最新评论
  • pacificLee: :twisted:
  • 小码: 为什么没有后面的呢,只有前10个
  • Anonymous: :lol:
  • Anonymous: :razz: 楼主是属于会聊天的。 我想问,sqoop发了几个版本了,应该没这些问题了吧。
  • Anonymous: Config.kafkaConfig.kafkaGroupI d 这个是指自己配置的group id 还是从 import org.apache.kafka.common.config .Config 这个类...
  • Anonymous: ZkUtils.getPartitionsForTopics (zkClient, Config.kafkaConfig.topic) 那个方法是在 spark-streaming_2.10 中 kafka...
  • Anonymous: ZkUtils.getPartitionsForTopics (zkClient, Config.kafkaConfig.topic) 你确定 kafka 里面有这个类 ? 个人在kafka 最新 稳定版...
  • Anonymous: :roll:
  • Anonymous: 很不错,试问有java版的吗?
  • Anonymous: 赞
  • Anonymous: 哈哈 看楼主的吐槽乐死了 where子句是可以写的 同样找不到资料 一点点试出来的 select id from xxxx where ${CONDITIONS} and 1=1 and 2=2 limit 4
  • EVIL: 我在运行完C4.5的代码后,显示 defined object DecisionTreeTest 是什么意思?这是有错误吗?运行结果在哪里看?
  • sf: 楼主的问题,我都遇到。。。没办法项目已经定型了,最后都硬着头 皮一个一个的改了源码
  • zz: 我去,楼主你真及时,我们今天上了新的HTTP2 push之后也发现速度曲线很奇怪,开始有200k/min,跟 另一台老的推送协议速度差不多,但是过了一会,立马降到只有几k /min,百思不得其解,我们还用了一个海外代理,在...
  • qi365: :mad: 很可恶,百度助纣为虐~
  • qi365: :? :shock: haha~ very good~
  • 张是大: 《深入浅出Spark机器学习实战(用户行为分析)》 课程网盘下载:http://pan.baidu.com/s/ 1mixvUli 密码:1pfn
  • Anonymous: :???:
  • Anonymous: 我用着sqoop感觉还可以,select 几十个字段也没事,估计是版本低。。
  • Anonymous: :grin: