Python AI 教学|SVD(Singular Value Decomposition)算法及应用

1 SVD简介

1.1 特征值分解

如果一个向量v是方阵A的特征向量,则将其可以表示为Av=λv。λ被称为特征向量v对应的特征值。

特征值分解是将一个矩阵分解成下面的形式:

Q是这个矩阵A的特征向量组成的矩阵,Σ是一个对角矩阵,每一个对角线上的元素就是一个特征值。一个矩阵的一组特征向量是一组正交向量。

1.2奇异值分解

提取数据背后因素的方法称为奇异值分解(SVD),SVD使能够用小得多的数据集来表示原始数据集,这样做去除了噪声和冗余信息,我们可以把SVD看成是从噪声数据中抽取相关特征。

(1)奇异值分解定义

奇异值分解指将一个矩阵A(m*n)分解为如下形式:

(其中,U是左奇异矩阵,由左奇异向量组成;V是右奇异矩阵,由右奇异向量组成。)

下图是一个对角矩阵,其除了对角线上的元素外,其余均为0。形如:

该矩阵的对角元素便是奇异值(singular value),一般情况下奇异值是按从大到小排列的。为了节省存储空间,在奇异值分解算法中,只存储σ 值,而不是一个对角矩阵。

(2)奇异值特性

奇异值σ 的减少特别的快,在很多情况下,前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了,则也可以用前r大的奇异值来近似描述矩阵:

(3)奇异值分解与特征值分解的关系

将矩阵A(m*n)和其转置相乘,将得到一个方阵,对这个方阵求特征值可以得到:

v就是矩阵A(m*n)的进行SVD的右奇异向量,同时还有:

σ就是矩阵A(m*n)的奇异值,u则是左奇异向量。

2 SVD算法实现

2.1分解过程

【1】算法实现:

【2】运行结果(python3):

2.2重构过程

由上图可知Sigma的值中,前两个比后面两个大了很多,我们可以将最后两个值去掉,则原始数据集就可以用如下结果来近似:

【1】重构过程示意图:

(其中浅灰色区域是原始数据,深黑色区域是矩阵近似计算仅需要的数据)

【2】重构算法:

【3】运行结果:

(补充:确定要保留的奇异值的数目有很多启发式的策略,其中一个做法就是保留矩阵中90%的能量信息,先将所有的奇异值求其平方和计算出总能量信息,再按照从大到小的顺序将奇异值的平方和累加到大于等于总值的90%为止。举个例子,比如某矩阵分解后得到10个奇异值,这些奇异值的总平方和为500,500*90%=450,则需要累加的奇异值能量和至少为450。按顺序累加,前3个奇异值平方和为100,前5个奇异值的平方为400,前6个平方和为460,则经过计算,重构矩阵的时候,取前6个奇异值。)

函数说明(一)

【1】mat函数

将输入解释为矩阵

语法:numpy.mat(data, dtype=None)

等价于matrix(data, copy=False)

算法示例:

3 SVD应用

SVD在数据压缩(如PCA)、推荐算法、矩阵补全、潜在语义索引(LSI)等领域都有着广泛的应用,这里将详细介绍基于SVD的推荐引擎实现。推荐系统存在于我们生活的各个角落,比如淘宝会给我们推荐我们可能感兴趣的物品,网易云音乐有每日推荐的20首歌,大众点评也会给我们推荐餐厅等。相关的推荐算法有基于内容推荐、协同过滤、关联规则、混合推荐等等。

3.1 基于协同过滤的推荐引擎

协同过滤(collaborative filtering)指通过将用户和其他用户的数据进行对比实现推荐。比如要判断是否给某个用户推荐一部他还没有看过的电影,则可以先将这部电影与用户看过的电影进行比较,如果相似度很高则认为用户会喜欢这部电影,则进行推荐;反之则不推荐。

(1)相似度

假设有一个用户和电影的数据集,我们可以将用户和电影的对应关系看成一个矩阵,如下图所示,行代表用户,列表示电影,矩阵的元素中0表示用户没有看过,1-5表示用户对这部电影的喜爱程度,值越大代表用户越喜欢这部电影。

【1】欧氏距离

电影“一”和“三”的欧氏距离为:

电影“二”和“三”的欧氏距离为:

相似度= ,当距离为0时候,相似度为1,随着距离的增大,相似度减小。

算法实现:

【2】皮尔逊相关系数(Pearson correlation)

它度量的是两个向量之间的相似度。该方法相对于欧氏距离的一个优势在于,它对用户评级的量级并不敏感。皮尔逊相关系数的取值范围从-1到+ 1,通过0.5 + 0.5*corrcoef()这个函数把其取值范围归一化到0-1之间。

算法实现:

【3】余弦相似度(cosine similarity )

计算的是两个向量夹角的余弦值,两个向量之间的夹角为:

余弦相似度的取值范围也在-1到+1之间,因此借助0.5 + 0.5*()也将它归一化到0到1之间。

算法实现:

函数说明(二)

【1】 norm函数

用来计算向量或矩阵范数的函数,同svd一样属于numpy库中的linalg。

语法:numpy.linalg.norm(x,p)

【注释:①x表示向量或者矩阵;②p表示范数的种类:p=1计算1-范数;p=2计算2-范数,同norm(x);p=inf计算无穷范数;p='fro',计算Frobenius范数】

算法示例:

【2】 corrcoef函数

用来计算皮尔逊相关系数

语法:numpy.corrcoef(x, y=None, rowvar=True)

【注释:x为矩阵或者向量,y和x的shape一样】

算法示例:

(2)基于电影内容的相似度计算

【1】数据生成

【2】调取数据

【3】运行结果

(补充:除了上述基于物品(item-based)的相似度外,还可以基于用户(user-based)的相似度计算,使用哪一种相似度取决于用户或物品的数目。因为观看电影人数远远高于电影的数目,所以基于电影的推荐会比基于人的推荐花费更短的时间,但是这种基于item推荐的缺点在于对用户历史喜好数据的量及准确性依赖较强,对小众喜好的用户,推荐效果不佳;)

(3)基于电影内容的推荐引擎

目的是构建一个推荐引擎,寻找到用户没有观看过的电影,算法需要实现的事情包括:①寻找用户没有观看过的电影——矩阵中的0值②在上述没看过的电影中对每部电影预计一个用户可能给予的等级——基于相似度计算③对这些电影的评分从高到低进行排序,返回前N个item。

【1】估计评分

【2】推荐电影

【3】调取数据

【4】运行结果

结果表明用户3(从0开始数,数字2对应于第3个用户)对电影3的评分为2.3(因为用户3只有一部电影没有评级,因此算法只返回一个结果)。

使用另两种相似度计算实现对未观看电影的评级:

函数说明(三)

【1】range函数

是一个python自带的来创建包含算术级数的列表。它最常用于for循环。

语法:range(start, stop[, step])

【注释:①start,是列表起始值,省略时默认为0;②stop,是列表最大能够达到的值,列表最后一个元素小于等于stop值;③step是步长】

算法示例:

【2】append函数

用于在列表末尾添加新的对象

语法:list.append(obj)

【注释:obj表示添加到列表末尾的对象】

算法示例:

【3】logcal_and函数

逻辑与

语法:numpy.logical_and(x1, x2)

逻辑函数包括:

算法示例:

3.2 基于SVD的推荐引擎

现实生活中的数据集会比前文协同过滤用到的矩阵稀疏得多,因为观众不可能看过近乎全部的电影,所以需要通过SVD来减少特征空间并提高推荐的效果。详情可以查阅Netflix推荐算法大赛,里面用到了很多的比较复杂推荐算法,而且推荐准确率也很高。

【1】数据生成

同样保存在“svdRec.py”中

【2】SVD过程

运行结果:

截止第5个奇异值累加能量和高于总能量的90%,于是我们可以将一个11维的矩阵转换成一个5维的矩阵。

【3】推荐实现

这里还是用到了协同过滤里面的推荐算法,只是将相似度的计算模块替换成了基于SVD的相似度计算模块。

运行结果:

基于默认的余弦相似度进行推荐top-3:

基于皮尔逊相关系数进行推荐top-3:

函数说明(四)

【1】eye函数

生成对角矩阵

语法:numpy.eye(M, k)

【注释:①M方阵的规模,即行数、列数;②k默认为0,输出对角线全“1”,其余全“0”的方阵;k为正整数,右上方第k条对角线全“1”其余全“0”; k为负整数,左下方第k条对角线全“1”其余全“0”】

算法示例:

责编 | 罗 栾 申

指导 | 老薛

指导教授简介:

薛巍立,男,博士,东南大学经济管理学院教授,博士生导师,国家自然科学基金优秀青年基金项目获得者。博士毕业于香港中文大学系统工程与工程管理系,主要从事供应链物流管理、运营风险管理和医疗服务运作管理等。主要成果发表在Operations Research、Production and Operations Management、Transportation Science、European Journal of Operational Research、Operations Research Letters等期刊上。

本文分享自微信公众号 - 数据魔术师(data-magician)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-17

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券