Slope one:简单高效的推荐算法
September 3rd, 2008 | by 超群.com | 知识共享署名-非商业性使用-相同方式共享，转载请保留链接。本博客所有原创文章采用知识共享署名-非商业性使用-相同方式共享，转载请保留链接http://chaoqun.17348.com/2008/09/slope_one/
推荐系统最早在亚马逊的网站上应用，根据以往用户的购买行为，推荐出购买某种产品同时可能购买的其他产品，国内做的不错的当当网,有时候买书，它总能给我推荐出我感兴趣的其他书来，也算是技术极大的促进了销售。
一般的协同过滤算法，首先是收集用户对事物（产品）的评分情况，一种直接对某本书，或者某个歌曲打分，另种是隐性的打分，比如商务系统中，购买了表示打2分，浏览了打1分，其他的0分。我比较看好隐性打分，因为直接打分需要用户的参与程度比较高，很多网站都在内容页中留一个打分的按钮，从1～5选一个，我可能喜欢这篇文章，可我哪里知道我喜欢的程度是几分啊，还要我去思考，而网站设计中一条很重要的原则是:Do not let me think!，于是我就胡打一个分数或者不打，而隐性的打分则不同，只有你喜欢的图书你才会购买，只有你喜欢的歌曲才会听多次。
收集好用户的打分之后，通过最近邻搜索到和某个事物或者某个人特征或者兴趣相近的其他事物或者人，最近邻搜索算法一般是皮尔森相关系数（Person Correlation Coefficient）、余弦相似性（Cosine-based Similarity）以及调整余弦相似性（Adjusted Cosine Similarity）。关于余弦定理在数据挖掘中的应用，google黑白报有过介绍，可以参考数学之美 系列 12 – 余弦定理和新闻的分类。
剩下的工作就是根据最近邻集进行推荐了。
最近邻集的运算相对来说成本比较高，尤其是大量数据的时候，今天和大家分享的是一种简单高效的协同过滤算法：Slope one
基本原理
用户 对事物A打分 对事物B打分 X 3 4 Y 2 4 Z 4 ?
用户Z对事物B的打分可能是多少呢？股票上有个说法是平均值可以掩盖一切异常波动，所以股票上的各个技术指标收拾不同时间段的平均值的曲线图或者柱状图等。同样的，Slope one算法也认为：平均值也可以代替某两个未知个体之间的打分差异，事物A对事物B的平均很差是：((3 – 4) + (2 – 4)) / 2 = -1.5，也就是说人们对事物B的打分一般比事物A的打分要高1.5，于是Slope one算法就猜测Z对事物B的打分是4 + 1.5 = 5.5
是不是非常的简单？
加权算法
有n个人对事物A和事物B打分了，R(A->B)表示这n个人对A和对B打分的平均差（A-B）,有m个人对事物B和事物C打分了，R（C->B）表示这m个人对C和对B打分的平均差（C-B），注意都是平均差而不是平方差，现在某个用户对A的打分是ra，对C的打分是rc，那么A对B的打分可能是：
rb = (n * (ra – R(A->B)) + m * (rc - R(C->B)))/(m+n)
开源的Slope one的程序包
- Python
http://www.serpentine.com/blog/2006/12/12/collaborative-filtering-made-easy/
- Java
http://www.daniel-lemire.com/fr/documents/publications/SlopeOne.java
- PHP
http://sourceforge.net/projects/vogoo
http://www.drupal.org/project/cre
http://www.daniel-lemire.com/fr/documents/publications/webpaper.txt Slope one算法作者写的，简单明了，强烈推荐。
- Erlang
http://chlorophil.blogspot.com/2007/06/collaborative-filtering-weighted-slope.html - C#
http://www.cnblogs.com/kuber/articles/SlopeOne_CSharp.html 国人写的C#版本 - T-SQL
http://blog.charliezhu.com/2008/07/21/implementing-slope-one-in-t-sql/
还有一些其他语言的版本，请参考http://en.wikipedia.org/wiki/Slope_One，即将面世的，居于PHP & Mysql的Slope one算法实现将会在http://code.google.com/p/openslopeone/开源出来，主要优化的是海量数据以及分布式处理，目前在我的笔记本上（迅驰＋1.5G内存），对440W打分记录进行测试，单一线程，3小时47分处理完。速度还算是不错了，最近工作实在太忙了，等我整理好会开源出来放在上面的地址。过几天会有一篇我的算法的详细介绍，盼诸位批评指正，共同学习，共同进步。
6 Responses to “Slope one:简单高效的推荐算法”
By 武影 on Mar 24, 2009 | Reply
此算法模型作为推荐系统感觉缺了一些更核心的元素，推荐应该是一种共同的兴趣或者说价值取向的传递。
首先找出共同的兴趣包括哪些元素，并把AB、BC这种共同兴趣匹配度纳入到推荐系统:
用户1对A和B同时打分，无论分值多少，可以作为A和B之间共同的兴趣传递的一种结果，不是唯一的哦，按照Dont let me think，我觉得可以在浏览行为、订单、评论、收藏夹等等方面都纳入到共同的兴趣这个元素中。
其次，在共同的兴趣匹配度下，按评分平均差排序。
By 超群.com on Mar 25, 2009 | Reply
＠武影：
下面的文字仅是我个人看法，没有怎么研究数学，所以可能有谬。
我们从加权公式看起：rb = (n * (ra – R(A->B)) + m * (rc – R(C->B)))/(m+n)，如果同时给A、B打过分的用户远远大于给C、B打过分的用户，那么A、B的权重n就非常的大，rb ≈ ra – R(A->B)/n，用户对B打分的值主要由同时对A、B打分过的用户决定。这就有点类似关联规则了，A、B频繁出现在一起，那么它们的关联性可能就高一些。
slope one引入了加权平均，所以它的结果可能要比简单的关联规则要好一些。
2007年在看一些股票技术方面的书，感觉核心就是平均值可以掩盖一切波动，这可能也是slope one算法的核心吧。
另外从一些测试的结果看，slope one算法可能是“性价比”最高的一种算法，运算简单，效果还很不错。
现在，推荐系统算法都盯着”SVD”，但已经变的一塌糊涂了，比如类RSVD，也许有效，但很“丑陋”。
至于“兴趣元素”，可能要和具体业务联系，比如音乐，我们分析听歌的次数、收藏的歌曲、评论的歌曲等等，这个是业务的范畴。
感谢你的留言，淘宝的推荐做的不错，我们的推荐系统近期可能也要上线了。
By iceberg on Apr 8, 2009 | Reply
您不觉得slope one这个算法与关联规则相比有点问题吗？就是用平均值的方法掩盖了个性。
比如说全国80%的人都喜欢“千里之外”，那我喜欢的概率是多少呢？
用slope one得出的结论肯定是我也很喜欢“千里之外”。
但关联规则就不一定，它会分析我的历史下载记录，找到我可能喜欢的歌曲。假设我就是个喜欢独立歌曲（或者戏剧）的人，也能找到相应的喜欢的歌。
原因就是因为关联规则关注的是条件概率，而slope one 好像是只统计全局的量，掩盖了个性。
By 超群.com on Apr 8, 2009 | Reply
@iceberg
rb = (n * (ra – R(A->B)) + m * (rc – R(C->B)))/(m+n)
slope one分析的对象是两个事物（比如两首歌），比如你喜欢戏剧，如果80％喜欢戏剧的人都喜欢“千里之外”，那么slope one可能会帮你推荐出来，但‘全国80%的人都喜欢“千里之外”，那我喜欢的概率是多少呢？‘这个不行，你的兴趣爱好和全国80%喜欢千里之外没关系。
slope one和关联规则都比较关注两个事物同时出现的次数，我以此相比较它们。