矩阵分解在推荐系统中的应用(转)

标签: 矩阵分解 推荐系统 应用 | 发表时间:2013-09-10 17:48 | 作者:
出处:http://eric-gcm.iteye.com

矩阵分解是最近几年比较火的算法,经过kddcup和netflix比赛的多人多次检验,矩阵分解可以带来更好的结果,而且可以充分地考虑各种因素的影响,有非常好的扩展性,因为要考虑多种因素的综合作用,往往需要构造cost function来将矩阵分解问题转化为优化问题,根据要考虑的因素为优化问题添加constraints,然后通过迭代的方法进行矩阵分解,原来评分矩阵中的missing vlaue可以通过分解后得到的矩阵求的。

本文将简单介绍下最近学习到的矩阵分解方法。

(1)PureSvd

怎么评价这种方法呢?开始觉得这种方法很神奇很数学,而且在实际使用的时候也非常好用。

但最近读了Yehuda大神的paper之后,觉得这种方法比较猥琐。

其实,矩阵分解的核心是将一个非常稀疏的评分矩阵分解为两个矩阵,一个表示user的特性,一个表示item的特性,将两个矩阵中各取一行和一列向量做内积就可以得到对应评分。

那么如何将一个矩阵分解为两个矩阵就是唯一的问题了。

说到这里大家就可能想起了在线代和数值分析中学到的各种矩阵分解方法,QR,Jordan,三角分解,SVD。。。

这里说说svd分解。

svd是将一个任意实矩阵分解为三个矩阵U,S,V,其中,U,V是两个正交矩阵,称为左右奇异矩阵,S是个对角阵,称为奇异值矩阵。

其实svd分解的问题可以化解为特征值分解的问题。

评分矩阵A(m*n)=U(m*k)*S(k*k)*V'(k*n)

令B(m*m)=A(m*n)*A'(n*m)

B矩阵就是一个方阵,可以利用各种简单的方法将B进行特征值分解:

Bv=av,

v是方阵B的特征向量,a是特征向量v对应的特征值。

所以奇异值s=sqrt(a),

左奇异向量u=A*v/s

同样的方法可以求得右奇异向量。

这样我们就得到了svd分解后的三个矩阵。(你可以自己写个c程序计算,当然也可以用matlab算算得到)

分解后的三个矩阵都有着各自的意义,

U:每一行表示一个user的特征。

V:每一列表示一个item的特征。

S:表示对应的user和item的相关性。

所以可以考虑用U和V将S吸收进来,形成两个矩阵分别表示user的矩阵和item的矩阵。

得到这个以后后面的事情就好办了。

为什么说这个方法猥琐呢?

因为我觉得,这种方法有着矩阵分解算法的表,却可以非常简单地完成矩阵的分解,然后填充稀疏的评分矩阵。

但它考虑的因素太少了,不过对于简单的推荐系统,这种方法还是非常有意义的,容易实现,而且结果也不会太差。

(2)Latent Factor Model

这是真正的矩阵分解算法,经过实践检验,具有非常高的准确性和易扩展性。

正如上面提到的,实现推荐系统结果的目标是将那个稀疏的评分矩阵分解成两个矩阵,一个表示user的feature,一个表示item的feature,然后做内积得到预测。

当然要实现满足一定约束条件的矩阵分解,可不像上面的PureSVD那样容易,需要构造一个优化问题,用一些复杂的算法求解优化问题。而这些优化问题往往是NP问题,只有局部最优解。

首先构造一个优化目标函数,

考虑到最后的评价指标是预测分值和实际分值之间的误差的平方(RMSE),所以构造的目标函数也是误差的平方的函数。

为什么这样的算法可以得到更优的结果呢?因为算法可以很容易地扩展很多的feature进来,更加出色地考虑了多种影响推荐效果的实实在在的因素。

 

  • Biases
因为有的用户总是会打出比别人高的分,或者说有的用户他的评价尺度比较宽松;同样有的item总是被打高分。这是一个普遍存在的问题,所以在构造目标函数的时候需要增加几项:所有评分的平均值miu,user的偏见分数bu,item的偏见分数bi。
比如:求用户x对电影y的打分,
所有评分电影的评分的平均分是miu=3.5,
电影y比所有评分电影平均分高bi=0.5
但是用户x是个比较严格的用户,评分总是相对偏低,所以bu=-0.3
所以用户x对电影y的打分为3.7
  • Implicit feedback
用户在使用web应用的时候,会产生大量的行为,充分挖掘这部分的价值,将会很好地提升推荐的效果。
利用用户的隐式反馈,相当于充分的利用了评分矩阵中的missing value的价值,用户在页面的停留时间,检索,浏览,点击等等各种行为都可以建模,内含到目标函数中。
这里,可以将简单地用一个Boolean来描述一种行为有还是没有。
不过在使用的时候,需要进行归一化处理。
  • User-associated attributes
基于用户的社会化属性进行推荐也是一种很基本的推荐,当然也可以考虑到目标函数中。
  • Temporal dynamics
用户的兴趣包括长期和短期,动态地考虑一段时间内用户的兴趣是很有必要的。
上面的几个因素中随着时间变化的有,user的bias项bu=bu(t),item的bias项bi=bi(t),以及user的factor向量pu=pu(t),这里可以忽略item的factor向量的变化,因为item是比较稳定的。
  • Confidence level
因为在处理上述的因素的时候,很多都是比较主观的,所以需要给每个因素添加一个置信权重,以平衡整个结果。
 
通过构造出这个目标函数,然后添加相应的约束条件,接下来的问题就是求解这个优化问题。
通常比较好的方法是Stochastic gradient desent。
 
PS:这种方法是现在学术界的主流方法,大家可以参阅Yehuda的神作( http://research.yahoo.com/Yehuda_Koren)以及上海交大在今年kddcup获奖方法的paper以及他们的开源系统( http://apex.sjtu.edu.cn/apex_wiki/svdfeature

 

 

 

(3)NMF(非负矩阵分解)

很多人用这种方法是因为他们觉得只有一个非负的值对于实际的例子才会有意义。

考虑到svd或者latent factor model会得到负的值,所以这种方法的物理意义比较明确。

同样的道理,NMF也是将评分矩阵的转置矩阵分解成两个矩阵。

不同的是这两个矩阵有着和上面的矩阵不同的物理意义。

其中一个是基矩阵W,另一个是投影矩阵H,即R'(n*m)=W(n*r)*H(r*m)

W:每一列包含一个基向量,这组基向量构成一个r维的空间。

H:每一列则近似为原始数据对应的列向量在该r维空间的投影。

做这个分解的方法也是构造一个目标函数和一些约束条件,然后用梯度下降的算法来计算得到一个局部最优解。

这种方法的思路大概是这样的:

 

  • 将评分矩阵转置然后分解成两个矩阵W和H。
  • 根据基矩阵W,可以计算得到目标用户评分向量a对基矩阵W的投影向量h。
  • 计算投影向量h与投影矩阵H各行之间的欧式距离,将其中距离最小的前k个用户组成目标用户a的最近邻集合。
  • 然后用皮尔逊相关法将最近邻集合中的数据进行加权计算,然后排序进行推荐。
可以看出来,这种方法的思路和上面的两种还是很不相同的,主要还是在计算目标用户的最近邻集合,主要思想还是knn,只是在中间用了矩阵分解的方法降维降低了计算的时间复杂度。
 
矩阵分解在学习的时候感觉既没用又麻烦,尤其是线代里面做矩阵的分解计算,无聊的很。
现在看来,矩阵分解非常有意义。
 
 
 
 
 
 
续:

最近研究了下Yehuda大神的paper,学习了下矩阵分解方法在推荐系统中如何用。

本文中提到的矩阵分解是一般的分解,即R=M*N的形式。

1、矩阵分解方法的来源

CF里的矩阵分解思想是来自于IR领域的Latent Semantic Analysis(LSA)。google黑板报的《数学之美》中很清楚地讲了SVD分解在IR中的应用。( http://www.google.com.hk/ggblog/googlechinablog/2006/12/blog-post_8935.html

2、矩阵分解的优劣

优点是:

 

  • 比较容易编程实现
  • 比较低的时间和空间复杂度
  • 预测的精度比较高
  • 非常好的扩展性
缺点是:推荐的结果不具有很好的可解释性。因为把ratings matrix分解成user-factor matrix和item-factor matrix,这里的factor很难用实际意义的概念来解释。不过,矩阵分解的过程相当于一个软聚类的过程,得到的每一个factor相当于每一个聚类后的分组,只是我们没有一个通用的方法来为这些分组命名。
但是在实际的应用中,我们可以提取这些分组中最突出的特点来给这些factor命名。比如,拿新闻资讯类的推荐系统来说,做好分解之后,每个factor都可以看成是一类资讯,可以从这些资讯中提取一些特征来给这个factor命名。
 
3、矩阵分解的模型(Latent Factor Model)
矩阵分解的思路是把评分矩阵通过分解,用一个低秩的矩阵来逼近原来的评分矩阵,逼近的目标就是让预测的矩阵和原来的矩阵之间的误差平方最小。(矩阵分解一般不用数学上直接分解的办法,尽管分解出来的精度很高,但是效率实在太低!矩阵分解往往会转化为一个优化问题,通过迭代求局部最优解。)
但是有个问题是,原来的评分矩阵的稀疏度太大,分解很容易产生overfitting(过度拟合,意思就是为了迁就一些错误的偏僻的值导致整个模型错误)的问题。所以现在的方法是在目标函数中增加一项regularization(正则化),来避免overfitting问题。
所以一般的矩阵分解的目标函数(或者称为loss function)是:
前一项是预测后的矩阵和现有的评分矩阵的误差,这里计算只针对评分矩阵中已经评分的项。
后一项就是正则化项,用来解决过度拟合的问题。
这个优化问题求解的就是分解之后的user-factor,item-factor矩阵的factor向量。(qi是item的factor向量,pu是user的factor向量)
求解这个优化问题常用两种方法,一种是alternative least squares(交叉最小二乘法),另一种是stochastic gradient descent(随机梯度下降法)。
前一种方法会涉及到矩阵的求逆问题,所以计算起来会比较麻烦。
后一种方法,只需要求梯度,就可以迭代计算了,因此会简单很多。
迭代方程如下:
其中,gamma是学习速率,lamda是正则化系数,是两个可选的参数,而且对于最后的结果非常重要。
这里,gamma的大小不仅会影响到训练时间,还会影响到结果的收敛性。gamma太大的话会导致结果发散,一般都会把gamma取得很小,不同的数据集取得值不同,但大概是0.001这个量级。这样的话训练的时间会长一些,但结果会比较好。
lamda的值一般也比较小,大概取0.01这个量级就好了。
迭代开始前,需要对user和item的特征向量赋初值,这个初值很重要,会严重地影响到计算速度。一般的做法是在所有已评分的平均分附近产生一些随机数作为初值。
迭代结束的条件一般是loss function开始增加了,或者loss function的值小于了某一个阈值。
当我们拿到计算出来的user,item的factor向量后,最后预测结果时有两种选择,一种是保留计算出来的小数rating,一种是将这些小数rating四舍五入并裁减到[1,5]这个区间内。
对于实际的推荐系统来说,结果是小数还是整数,没有所谓,因为我们并不会把预测的分数给用户看,而只是返回一个推荐列表。
但对于线下训练参数或者做论文的童鞋来说,不同的处理方法得到的RMSE或者MAE的值可不相同。
我用这个的算法对movielens 100k的小数据做了测试,用很短的时间就可以计算好,不过那些参数的选择需要不断地用RMSE 来计算得出。在其他的信息都没有利用的情况下,也可以得到0.90这个量级的RMSE。
 
4、增加一些扩展项
上面的模型中只简单的用了已知的评分数据,很多的信息都没有考虑进来。
(1)增加biases信息
因为有的user总是趋向于打一个很高的分,而有的user比较严格,总是打一个很低的分,有的item总是被打一个很高的分,而有的item总是被低估。所以我们需要给模型增加biases项,loss function如下:
迭代方程变成了:
同样的方法,只是多了对bu和bi的赋初值。
同样,我用movielens的100k数据计算,得到的RMSE值也在0.90这个量级,但整体要比没有考虑biases结果好。
(2)增加implicit feedback信息
评分是一个显性的反馈方式,然而在很多时候显性的反馈很少很少,而user的很多行为都可以反映出他们对item的态度,所以利用implicit feedback是非常必要的。给模型增加implicit feedback项,预测模型如下:
迭代方程如下:
implicit feedback信息对于商城来说,可能是购买,浏览等等行为,对于Netflix这样的网站来说,可能是浏览,租赁等等。
 
(3)考虑temporal信息
因为用户的兴趣或者对某一个item的态度是和时间有关的,比如说,可能我今年不太喜欢西服这个东西,因为我用不着,所以我不会购买,但可能若干年后我不得不穿西服的时候,我一定会去买,也就是说我给推荐系统留下我喜欢西服这个东西的印象。(即使我真的不喜欢西服。)
动态地考虑user的兴趣或者需求是非常必要的。
 
矩阵分解是当下非常流行的算法,可以考虑将这种算法和传统的KNN结合在一起来做推荐,相信效果会很不错。


已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [矩阵分解 推荐系统 应用] 推荐:

矩阵分解在推荐系统中的应用(转)

- -
本文将简单介绍下最近学习到的矩阵分解方法. 开始觉得这种方法很神奇很数学,而且在实际使用的时候也非常好用. 但最近读了Yehuda大神的paper之后,觉得这种方法比较猥琐. 其实,矩阵分解的核心是将一个非常稀疏的评分矩阵分解为两个矩阵,一个表示user的特性,一个表示item的特性,将两个矩阵中各取一行和一列向量做内积就可以得到对应评分.

矩阵分解的Jungle

- SuperLucky - 增强视觉 | 计算机视觉 增强现实
美帝的法国貌似是美法混血的有心人士(此有心人士长期从事航天飞机研究. )收集了市面上的矩阵分解的几乎所有算法和应用,由于源地址在某神秘物质之外,特转载过来,源地址. Matrix Decompositions has a long history and generally centers around a set of known factorizations such as LU, QR, SVD and eigendecompositions.

推荐系统经典论文文献及业界应用

- - 海之沙
Survey方面的文章及资料. Knowledge and Data Engineering, IEEE Transactions on, 2005, 17(6): 734-749. 2005年的state-of-the-art的推荐综述,按照content-based, CF, Hybrid的分类方法进行组织,并介绍了推荐引擎设计时需要关注的特性指标,内容非常全.

深度学习在推荐系统中的应用

- -
2016年DeepMind开发的AlphaGo在围棋对决中战胜了韩国九段选手李世石,一时成为轰动全球的重大新闻,被全球多家媒体大肆报道. AlphaGo之所以取得这么大的成功,这其中最重要的技术之一是深度学习技术. 经过这几年的发展,深度学习技术已经在图像分类、语音识别、自然语言处理等领域取得突破性进展,甚至在某些方面(如图像分类等)超越了人类专家的水平.

vivo 应用商店推荐系统探索与实践

- - 掘金 后端
介绍 vivo 应用商店推荐系统如何高效支撑个性化的推荐需求. 商店的应用数据主要来源于运营排期、CPD、游戏、算法等渠道,成立推荐项目之后也没有变化,发生变化的是由推荐系统负责和数据源进行对接,商店服务端只需要和应用推荐系统进行对接即可. 如果读者以为我们单纯是把商店服务端代码给照搬到推荐系统这边来了那就真的是too young too simple 了,不做优化或者升级直接copy一个系统是不可能的,这辈子都不可能.

推荐算法之矩阵分解

- - 标点符
推荐领域的人一般都会听说过十年前 Netflix Prize 的比赛,随着Netflix Prize推荐比赛的成功举办,近年来隐语义模型(Latent Factor MOdel,LFM)受到越来越多的关注. 隐语义模型最早在文本挖掘领域被提出,用于寻找文本的隐含语义,相关的模型常见的有潜在语义分析(Latent Semantic Analysis,LSA)、LDA(Latent Dirichlet Allocation)的主题模型(Topic Model)、矩阵分解(Matrix Factorization)等等.

自然语言处理技术(NLP)在推荐系统中的应用

- - IT瘾-geek
作者:张相於,58集团算法架构师,转转搜索推荐部负责人,负责搜索、推荐以及算法相关工作. 多年来主要从事推荐系统以及机器学习,也做过计算广告、反作弊等相关工作,并热衷于探索大数据和机器学习技术在其他领域的应用实践. 责编:何永灿([email protected]). 《程序员》原创文章,更多精彩文章请. 个性化推荐是大数据时代不可或缺的技术,在电商、信息分发、计算广告、互联网金融等领域都起着重要的作用.

[原]机器学习在热门微博推荐系统的应用

- - CSDN人工智能
近年来,机器学习在搜索、广告、推荐等领域取得了非常突出的成果,成为最引人注目的技术热点之一. 微博也在机器学习方面做了广泛的探索,其中在推荐领域,将机器学习技术应用于微博最主要的产品之一——热门微博,并取得了显著的效果提升. 热门微博是基于微博原生内容的个性化兴趣阅读产品. 提供最新最热优质内容阅读服务,更好地保障用户阅读效率和质量,同时达到激励微博上内容作者更好的创作和推广内容.

知识图谱增强下的智能推荐系统与应用-于敬

- - 我爱自然语言处理
随着互联网技术的迅速发展,尤其是移动互联网的兴起,新产生的信息呈现爆炸式的增长. 为了更好地解决信息获取中的信息过载(Information Overload)和长尾问题(Long Tail),推荐系统应运而生,目前基本上已经成为了各种产品的标配功能. 推荐系统是信息过滤系统的一个分支,它可以自动地挖掘用户和物品之间的联系.

基于矩阵分解的推荐算法,简单入门 - kobeshow

- - 博客园_首页
       本文将要讨论基于矩阵分解的推荐算法,这一类型的算法通常会有很高的预测精度,也活跃于各大推荐系统竞赛上面,前段时间的百度电影推荐最终结果的前10名貌似都是把矩阵分解作为一个单模型,最后各种ensemble,不知道正在进行的阿里推荐比赛( http://102.alibaba.com/competition/addDiscovery/index.htm),会不会惊喜出现.