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的平均偏差是：
其中
表示同时评价物品i和物品j的用户集合，
则表示此集合的个数。
分别表示用户u对物品i和物品j的实际评分。
因此，预测用户u给物品j的评分为：
其中
带权Slope One
基础的slope-one算法在计算回归直线时，并没有考虑对同一item的评分用户数。
如果一个用户已经评价了一些项目，可以这样做出预测：简单地把各个项目的预测通过加权平均值结合起来。当用户两个项目都评价过的时候，权值就高。在上面的例子中，物品1和物品2都评价了的用户数为2,物品1和物品3 都评价了的用户数为1,因此权重分别为2和1. 我们可以这样预测Lucy对物品1的评价：
(2*2.5 + 1*8) / (2+1) = 4.33。
预测公式为：
,其中
。
突然想到这么一个问题，是否有更合适的值来当权重呢？
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