Slope One

[toc]

基本的Slope One

Slope One算法是一种基于评分的预测算法,本质上也是一种基于项目的算法。与一般的基于项目的算法不同, 该算法不计算项目之间的相似度, 而是用一种简单的线性回归模型f(x) = ax + b进行预测(可以扩展),其中a=1。算法易于实现,计算速度快,可扩展性好,同时对数据稀疏性有较好的适应性。

假设我们有如下数据:

评分数据库样本
顾客 物品 1 物品 2 物品 3
John 5 3 2
Mark 3 4 未评分
Lucy 未评分 2 5

计算出所有不同物品之间的平均值偏差。

物品2和物品1:[(5-3) + (3-4)]/2 = 0.5

物品3和物品1:  (5-2)/1 = 3

物品3和物品2:[(3-2) + (2-5)]/2 = -1

现在,我们预测Lucy给物品1的评分。

因为Lucy给物品2评价过,所以我们可以根据物品2来预测,其中物品2和物品1的偏差是0.5, 也就是 0.5 + 2 = 2.5;

因为Lucy也给物品3评价过,而物品3和物品1的偏差是3, 所以也有 3 + 5 = 8;

综合起来,我们可以预测Lucy给物品1的评分是 (2.5+8)/2 = 5.25。【因为超过5分,所以可以认为是5分】

比较理论的说明如下:

给定训练集X,物品j和物品i的平均偏差是: dev_{j,i} = \sum_{u\in S_{j,i}(\chi )} \frac{u_{j} - u_{i}}{card(S_{j,i}(\chi ))}

其中S_{j,i} 表示同时评价物品i和物品j的用户集合,card(S_{j,i}(\chi) 则表示此集合的个数。 u_{i}、u_{j} 分别表示用户u对物品i和物品j的实际评分。

因此,预测用户u给物品j的评分为:P(u)_{j} = \frac{1} {card(R_{j})} \sum_{i\in R_{j}} (dev_{j,i} + u_{i})

其中 R_{j} = \left \{i | i \in S(u), i \neq j, card(S_{j, i}(\chi)) > 0 \right \}

带权Slope One

基础的slope-one算法在计算回归直线时,并没有考虑对同一item的评分用户数。

如果一个用户已经评价了一些项目,可以这样做出预测:简单地把各个项目的预测通过加权平均值结合起来。当用户两个项目都评价过的时候,权值就高。在上面的例子中,物品1和物品2都评价了的用户数为2,物品1和物品3 都评价了的用户数为1,因此权重分别为2和1. 我们可以这样预测Lucy对物品1的评价:
(2*2.5 + 1*8) / (2+1) = 4.33。

预测公式为: P(u)_{j} = \frac {\sum_{i \in S(u)-\{ j \}} (dev_{j, i} + u_{i})c_{j,i}} {\sum_{i \in S(u) - \{ j \}} c_{j, i}} ,其中c_{j, i} = card(S_{j, i}(\chi))

突然想到这么一个问题,是否有更合适的值来当权重呢?

Bi-Polar Slope One

带权的slope-one算法很好地考虑了共同评分用户数的问题,但还有另外一个问题:好评和差评对用户的决策影响是不同的。很多的好评对用户的影响也不如少数的差评。因此这个算法先会计算用户对一个item的平均评分,然后将用户对item的评分集拆成两个:好评集(即>平均评分的)和差评集。对好评集中的item使用带权的slope-one算法预测评分,而对差评集中的item使用基础的slope-one算法(即放大了少量的差评),最后计算item的带权平均值。

这个公式太复杂了,懒得编辑了,具体的看论文吧……

Slope One的复杂度

设有“n”个项目,“m”个用户,“N”个评分。计算每对评分之间的差值需要n(n-1)/2 单位的存储空间,最多需要 mn^2步. 计算量也有可能挺悲观的:假设用户已经评价了最多 y 个项目, 那么计算不超过n^2+my^2个项目间计算差值是可能的。 . 如果一个用户已经评价过“x”个项目,预测单一的项目评分需要“x“步,而对其所有未评分项目做出评分预测需要最多 (n-x)x 步. 当一个用户已经评价过“x”个项目时,当该用户新增一个评价时,更新数据库需要 x步. 可以通过分割数据(参照分割和稀疏存储(没有共同评价项目的用户可以被忽略)来降低存储要求,

分布式Slope One

大概思路如下:

假设现在的评分文件A的格式是 [user, item, rating]【每行】.

我们第一步是先把它转换成 user -> [(item1, rating1), (item2, rating2)…]【每行】的形式,令此时文件名为B。

第二步是处理B中的数据,得到<item1, item2> -> (d1, d2 ….dj)格式的文件,令文件名为C。其中dj表示的是item2和item1的偏差,因为有很多用户同时评价item1和item2,所以会有多个偏差。

第三步则是基于文件C,计算出所有物品之间的平均偏差。

以上每个步骤都可以通过Map-Reduce并行实现。具体内容可以查看【ppt

Mahout里面已经有实现基于Map-Reduce的Slope One。

参考文献

http://zh.wikipedia.org/wiki/Slope_one
http://blog.csdn.net/inte_sleeper/article/details/7470809
http://lemire.me/fr/abstracts/SDM2005.html
http://vdisk.weibo.com/s/1xLzw?t=file
 

转载请注明: 转载自http://jyd.me/

本文链接地址: Slope One

发表评论

电子邮件地址不会被公开。 必填项已用*标注