专栏首页Coggle数据科学奇异值分解(SVD)原理

奇异值分解(SVD)原理

PCA回顾

在之前的文章中我们对PCA降维进行总结

Betten:主成分分析PCA学习总结​zhuanlan.zhihu.com

下面我们回顾下算法流程:

输入:

维样本集

,要降维到的维数

.

输出:降维后的样本集

1.对所有的样本进行中心化

2.计算样本的协方差矩阵

3.求出协方差矩阵的特征值及对应的特征向量

4.将特征向量按对应特征值大小从上到下按行排列成矩阵,取前k行组成矩阵

5.

即为降维到

维后的数据

考虑一个问题,假设样本集

中每个

是一个图片,并且是一个

的图片,如果以像素值作为特征,那么每张图片的特征维度是10000。当进行PCA降维时,难点在于我们构造协方差矩阵时,维度达到

。在这样的协方差矩阵上求解特征值,耗费的计算量程平方级增长。面对这样一个难点,从而引出奇异值分解(SVD),利用SVD不仅可以解出PCA的解,而且无需大的计算量。

奇异值分解(singular value decomposition)

SVD的基本公式:

其中,

且除了主对角线上的元素以外全为0,主对角线上的每个元素都称为奇异值,且已按大小拍好序,

。其中,

的列向量即是

的特征向量,一般我们将

中的每个特征向量叫做

的左奇异向量;

的列向量即是

的特征向量,一般我们将

中的每个特征向量叫做

的右奇异向量。

我们都求出来了,现在就剩下奇异值矩阵

没有求出了。

由于

除了对角线上是奇异值其他位置都是0,那我们只需要求出每个奇异值

就可以了。

我们注意到:

这样我们可以求出我们的每个奇异值,进而求出奇异值矩阵


上面还有一个问题没有讲,就是我们说

的特征向量组成的就是我们SVD中的

矩阵,而

的特征向量组成的就是我们SVD中的

矩阵,这有什么根据吗?这个其实很容易证明,我们以

矩阵的证明为例。

上式证明使用了

。可以看出

的特征向量组成的的确就是我们SVD中的

矩阵。类似的方法可以得到

的特征向量组成的就是我们SVD中的

矩阵。

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方,也就是说特征值和奇异值满足如下关系:

这样也就是说,我们可以不用

来计算奇异值,也可以通过求出

的特征值取平方根来求奇异值。

性质

对于奇异值,它跟我们特征分解中的特征值类似,在奇异值矩阵中也是按照从大到小排列,而且奇异值的减少特别的快,在很多情况下,前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说,我们也可以用最大的

个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说,可以对

三个矩阵进行裁剪,比如将特征

维降至

维,那么

即可。

由于这个重要的性质,SVD可以用于PCA降维,来做数据压缩和去噪。也可以用于推荐算法,将用户和喜好对应的矩阵做特征分解,进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法,比如潜在语义索引(LSI)。下面我们就对SVD用于PCA降维做一个介绍。

小结

SVD作为一个很基本的算法,在很多机器学习算法中都有它的身影,特别是在现在的大数据时代,由于SVD可以实现并行化,因此更是大展身手。SVD的原理不难,只要有基本的线性代数知识就可以理解,实现也很简单因此值得仔细的研究。当然,SVD的缺点是分解出的矩阵解释性往往不强,不过这不影响它的使用。

SVD最早的应用之一是信息检索,我们称利用SVD的方法为潜在语义索引(Latent Semantic Indexing ,LSI)或潜在语义分析(Latent Semantic Analysis ,LSA)。

SVD另一个应用为推荐系统应用,简单版本的推荐系统能够计算物品item或者用户user之间的相似度,可以用SVD将原始数据映射到低维空间中,然后节省计算相似度时的计算资源。

参考出处

斯坦福大学公开课_机器学习_奇异值分解

刘建平Pinard奇异值分解

《机器学习实战》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 拍拍贷第四届魔镜杯大赛-冠亚季军方案梳理

    这是即2019腾讯广告算法之后,又一场数据竞赛。这次比赛以互联网金融信贷业务为背景,帮助选手了解相关业务。

    Coggle数据科学
  • 数据竞赛之常见数据抽样方式

    该抽样方法是按等概率原则直接从总中抽取n个样本,这种随机样本方法简单,易于操作;但是它并不能保证样本能完美的代表总体,这种抽样的基本前提是所有样本个体都是等概率...

    Coggle数据科学
  • DF消费者人群画像—信用智能评分方案分享(top5)

    此次比赛是中国移动福建公司提供2018年某月份的样本数据,包括客户的各类通信支出、欠费情况、出行情况、消费场所、社交、个人兴趣等丰富的多维度数据,参赛者通过分析...

    Coggle数据科学
  • 机器学习降维之奇异值分解(SVD)

    我们首先回顾下特征值和特征向量的定义,如下所示。其中A是一个n×n的矩阵,x是一个n维向量,则我们说λ是矩阵A的一个特征值,x是矩阵A的特征值λ所对应的特征向量...

    小一
  • 深度学习笔记之奇异值分解及几何意义

    SVD实际上是数学专业内容,但它现在已经渗入到不同的领域中。SVD的过程不是很好理解,因为它不够直观,但它对矩阵分解的效果却非常好。比如,Netflix(一个提...

    Jetpropelledsnake21
  • zabbix报错cannot set resource limit: [13] Permission denied解决方法

    [root@localhost ~]# systemctl start zabbix-server

    拓荒者
  • “豪 横”版 channel_v3.json,你确定不需要?

    豪横:下面为你附上channel_v3.json源码,别跑,快来研究研究。。。。。。

    C you again 的博客
  • 资源 | 深度学习图像标注工具汇总

    用户1737318
  • 深度学习可解释性相关论文和代码大全

    https://github.com/lopusz/awesome-interpretable-machine-learning

    代码医生工作室
  • Confluence 6 移动应用 app 你需要什么

    为了让你的用户能够连接使用 Confluence 服务器的移动客户端,你需要满足下面的条件:

    HoneyMoose

扫码关注云+社区

领取腾讯云代金券