首页 > 推荐系统 > [论文笔记] 基于物品的协同过滤算法
2014
06-27

[论文笔记] 基于物品的协同过滤算法

Item-based Collaborative Filtering Recommendation Algorithms


点此下载论文:Item-based Collaborative Filtering Recommendation Algorithms

内容概要:本文研究不同的基于物品的推荐算法、几种物品之间相似度计算方法、如何得到最终推荐结果的方法。最后将讨论的结果和基于最近邻的算法进行对比。

一、协同过滤

两大问题:
  1. 提升协同过滤算法的性能:需要实时找出大量的潜在邻居。但是已知的算法如果邻居有大量信息,那么找邻居性能会很慢。
  2. 提高推荐的质量(准确度)。
    这两大问题看起来是相互制约的,提升性能的话就会减少邻居数量,这样推荐的准确度就会下降。所以算法必须保证两者兼顾。传统协同过滤的瓶颈是存在大量的相似用户。因此,基于物品的协同过滤算法是挖掘物品之间的相似性而不是用户之间。用户一般远远大于商品的数量,比如电影推荐,豆瓣,时光网。购物网站的话,淘宝的商品数量(2013年8亿[1])已经远大于用户数量了(2013年3.7亿[2])假设不考虑购物网站来说,物品之间的相似度相对于用户来说比较稳定,因此,采用基于物品的算法可能效果会更好一些。
 
两个阶段:
  1. 预测:预测出来的是一个数值,表示的是没被用户u操作过的物品的值。
  2. 推荐:取top-N。
 
两种分类:
  1. Memory-based (user-based):寻找那些评分相似的用户或者购买相似的用户。结合这些相似用户生成推荐或者直接用top-N来推荐,应用很广。
  • 面临的两大挑战:
a) 稀疏:商品非常多,而用户购买的往往很少。
b) 性能:计算量随着用户和商品的增加而增加。因此数据量一大性能就降低。
针对这两大挑战,结合了半智能系统,这些系统采用句法特征对商品进行评分,以此来提升效率。在稀疏性方面,减少维度,采用潜在语义分析(也称LSI)来寻找用户和商品之间的关系。
  1. Model-based (item-based):预测用户可能的评分值。模型的建立一般使用机器学习的算法,比如贝叶斯神经网络,聚类,基于规则的方法。贝叶斯是形成了一个可能性模型;聚类是将协同过滤问题看做分类问题;基于规则的方法是寻找两个被一起购买的商品之间的关系,推荐具有强关联规则的商品。
 

二、相关应用:

  1. Tapestry:这是最早应用协同过滤系统的设计,主要是解决Xerox公司在Palo Alto的研究中心资讯过载的问题。这个研究中心的员工每天会收到非常多的电子邮件却无从筛选分类,于是研究中心便发展这项实验性的邮件系统来帮助员工解决这项问题。[3]
  2. The GroupLens research system[4]:这个系统主要是应用在新闻的筛选上,帮助新闻的阅听者过滤其感兴趣的新闻内容,阅听者看过内容后给一个评比的分数,系统会将分数记录起来以备未来参考之用,假设前提是阅听者以前感兴趣的东西在未来也会有兴趣阅听,若阅听者不愿揭露自己的身分也可以匿名进行评分。
  3. Ringo and Video Recommender
 

三、相关技术:

  1. 贝叶斯神经网络:基于决策树训练出来的一个模型,结果模型会很小,实质上跟最近邻的方法差不多。贝叶斯神经网络适用于用户特征变化比较慢的场景,不适用于用户信息更新比较快的场景。
  2. 聚类:聚类一般推荐的不是很个性化,一般准确度要低于最近邻的方法。聚类一般在推荐系统中用于第一步粗略估算出相似用户。
  3. Horting:是一个基于图的技术,它的节点是用户,边是相似度。结合相邻节点的观点形成推荐。与最近邻算法不同之处在于,Horting技术会考虑到那些没有评过分的用户。在一些数据上,Horting效果比最邻近的效果好。

四、Item-based Collaborative Filtering Algorithm

商品相似度计算:根据共同评分过的商品来计算

  1. 余弦相似度:

    sim(\vec i,\vec j) = cos(\vec i, \vec j) = \frac{\vec i \cdot \vec j}{\| \vec i \|_2 \ast \| \vec j \|_2}

  2. 基于相关性的相似度:根据Pearson相关系数来计算相似度。R_{u,i}是用户u对商品i的评分,\overline{R}_{i}是对商品i的平均评分。

    sim(\vec i,\vec j) = \frac{\sum_{u \in U}(R_{u,i} - \overline{R}_{i})(R_{u,j} - \overline{R}_{j})}{\sqrt{\sum_{u \in U}(R_{u,i} - \overline{R}_{i})^2}\sqrt{\sum_{u \in U}(R_{u,j} - \overline{R}_{j})^2}}

  3. 调整后的余弦相似度:是用户u的平均评分。跟上面的公式差别很小。考虑了不同用户的评分范围。比如用户A对自己最喜欢的也只评4分,而B对自己最喜欢的评5分,这样用户标准不同,求得的结果往往不同。

    sim(\vec i,\vec j) = \frac{\sum_{u \in U}(R_{u,i} - \overline{R}_{u})(R_{u,j} - \overline{R}_{u})}{\sqrt{\sum_{u \in U}(R_{u,i} - \overline{R}_{u})^2}\sqrt{\sum_{u \in U}(R_{u,j} - \overline{R}_{u})^2}}

预测:两种选择推荐商品的方法。
  1. 加权总和:用户u预测商品i,计算用户u对相似于商品i的物品的评分权值和。将相似度s_{i,j}作为权值加权在评分上,则

    P_{u,i} = \frac{\sum_{all \ similar \ items,N}(s_{i,N} \ast R_{u,N})}{\sum_{all \ similar \ items,N}(\mid s_{i,N} \mid)}

    R_{u,i}是用户u对商品i的评分。
  2. 回归:跟上面的不同之处在于不是直接使用相似商品的评分,而是使用一个近似的评分。用余弦相似度或者相关系数计算出来的结果可能使得两个很远的向量看起来很相似。线性回归模型使用近似的评分数据R'_{u,N}R_{N}表示与i相似商品N的评分值。模型可以表示为是线性回归模型的误差。

    \overline{R}'_{N} = \alpha \overline{R}_{i} + \beta + \epsilon

    \epsilon是线性回归模型的误差。
性能分析:
    对于一个商品,我们只需要找与它最近似的k个商品即可(k << n)。为了确保推荐的质量,k当然是越大越好(model size)。接下来的实验会验证k的个数与推荐质量的关系。

五、实验评估:

    采用MovieLens推荐系统的数据。大约有43000用户,3500+电影。随机选取了一些活跃的用户(评过至少20部电影)。将这些数据划分为训练集和测试集。假设变量x是训练集所占的百分比。我们使用的数据集有943行(用户),1682列(这些电影至少被一个用户评过分)。我们考虑了稀疏度,定义为1-\frac{nonzero \ entries}{total \ entries}。因此我们使用的数据的稀疏度为1-\frac{100,000}{943 \times 1682},0.9369。

 
评价指标:
  1. Statistical accuracy metrics:统计的准确度。是将预测的分数跟真实数据(测试集)进行对比。引入了MAE[5](平均绝对误差是所有单个观测值与算术平均值的偏差的绝对值的平均),MAE的值越小,说明预测的精确度越高。RMSE[6](均方根误差)和相关系数也可以作为评价精度的指标。
  2. Decision support accuracy metrics:决策支持精度。以二分类的思想将低于1.5或者2.5(总分5分)的作为不相关的预测。这样所有的评分都变成了0或者1。这个指标评测了预测的有效性。其他的一些方法比如reversal rate,weighted errors,ROC sensitivity。[7]
 
实验过程及结果:
    采用了一个最近邻的算法作为对照。考了了一些因素:相似度算法的影响,训练集比例x的影响,邻居数量多少的影响。还分析了模型大小对效率的影响。

 

六、思考

    这篇论文的实验感觉需要改进,没有将数据集作为一个参数作为对照。题目选取的item的数量和user的数量差不多。但是我觉得基于user和基于item的适用场景应该是不一样的。就本文来说,如果item数量远远大于user,那么用基于item的算法是不是会变得很慢?那样的话,相似度矩阵计算的复杂度应该会非常大。所以像购物网站,应该还是基于user的算法效果会比较好。但是就上一篇亚马逊的论文来看,物品的相似度完全可以线下计算,这样就节省了很多时间,不过商品的评分肯定也会实时变化的。而基于user的协同过滤用户购买变化是很大的,所以这样来说需要线上计算。
    文章性能分析大致意思是这样的,给用户A推荐,用户A是确定的,基于user的算法来说,只能从A找相似的用户,但是由于A购买记录是实时的,所以需要重新计算A与其他用户的相似度。而基于item的算法,我们推荐的是A没有购买过的商品,从这里找跟A买商品比较相似的商品,从而可以减少数量(即model size的选择),这样并不依赖于用户最近的购买(当然购买过就不推荐了而已),这样来看,确实不需要实时去更新item矩阵。
    上述提到的购买也可以当做评分来看。
 

七、吐槽:

    论文较好地描述了一下基于物品的协同过滤算法,在那个年代来说应该是比较全面的文章了。真长啊,自己从中还是收获很多的,最起码知道了很多以前看起来高大上的名词是啥意思。看了三天,为自己点赞~~≥v≤~~插公式学会了长期不想学的\LaTeX啊有木有!!!
 
[1] 淘宝商品数量:http://b2b.toocle.com/detail--6124316.html
[2] 淘宝用户数量:http://www.cnbeta.com/articles/131646.htm
[3] Tapestry:http://zh.wikipedia.org/wiki/%E5%8D%94%E5%90%8C%E9%81%8E%E6%BF%BE
[4] GroupLens:http://grouplens.org/ 
[5] MAE:http://en.wikipedia.org/wiki/Mean_absolute_error
[6] RMSE:http://en.wikipedia.org/wiki/RMSE
[7] ROC sensitivity:http://zh.wikipedia.org/wiki/ROC%E6%9B%B2%E7%BA%BF
 
 
最后编辑:
作者:zxy_snow
吃好,喝好,学习好!

  1. 楼主,看了你的文章,觉得你很厉害。我想请教你一个问题:最近在做关于基于项目的协同过滤的毕业设计。我做的方向是关于改进基于项目的协同过滤算法,改进的内容是物品之间相似度算法,我只是提出一些小小的修改,然后利用MAE或者精度、召回率之类的评估方法进行评估,通过对比之前的相似度算法的精度、召回率或者是MAE说明改进的算法有效就行,这也是提出算法改进的一般步骤。但是我最近遇到了一些问题,想请教你: 问题:我利用我提出的改进的相似度算法算出了物品(这里用的数据是MovieLens的电影评论数据集)之间的相似度得到了一个对称的矩阵。但是对什么进行预测?这里有两个小问题:(1)是对用户U没有评分过的电影M进行预测评分吗?如果是这样,怎么评估我提出的改进的相似度算法的优劣?训练样本和测试样本又拿来干嘛的?这里对我而言很混乱,主要是我预测出来以后怎么进行评估?训练样本和测试样本怎么使用?(2)如果是对用户U已经评分过的电影M进行预测评分,然后计算预测评分和真实评分之间的误差,得到评估效果。那么,我们其实没有对用户进行推荐,而且,这样做的话根本不需要测试样本,因为训练样本也可以得到我提出的相似度算法的MAE。所以比较纠结