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

SVD与PCA

2条评论11,736次浏览

奇异值分解

奇异值分解,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
  • 文章总数:79篇
  • 评论总数:402条
  • 分类总数:31个
  • 标签总数:44个
  • 运行时间:1013天

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

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

最新评论
  • 晴子: 在主节点初始化CM5数据库的时候报错误:Verifying that we can write to /opt/cm-5.9.0/etc/cloudera-scm -server log4j:ERROR Could not...
  • zhangnew: 就4题 :?:
  • linxh: “ 但要是遇到预先并不知道数组的长度而又需要获取正确的(或者称之 为原始的)split长度时,该如何处理呢。。? ” 印象中可以split函数参数传-1?
  • linxh: 班门弄斧一下: ssh host cmd 和直接ssh上后cmd结果不一样是因为ssh直接运行远程命令 是非交互非登录模式与ssh上去得到一个登录交互式Shell二 者加载的环境变量不一样。
  • 匿名: 其实文本分类和数字分类是一样的,只是文本分类需要多一个步骤, 就是计算它的tf-idf值将其转换为double类型
  • yurnom: 可能苹果最近又改变了返回值吧,最近没做测试了。 BadDeviceToken一般测试环境和正式环境弄错的情况 下会出现。
  • Anonymous: :razz: 博主,良心贴啊, 最近也在弄apns推送。 有个问题想请教你一下啊。 你博客中写的 Unregistered 错误,有准确的说明吗, 我看你博客中写的:...
  • 一波清泉: 回复邮箱: 1004161699@qq.com 多谢
  • Anonymous: 17/02/09 01:15:02 WARN Utils: Service ‘SparkUI’ could not bind on port 4040. Attempting port...
  • 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