推荐系统之协同过滤概述
http://www.vanjor.org/blog/2011/05/rs-collaborative-filtering/ 这篇文章讲得可真够细的
推荐系统之协同过滤概述
想要实现 Slope One，只需要计算并存储“n”对评分间的平均差值和评价数目即可。
算法复杂度
设有“n”个项目，“m”个用户，“N”个评分。计算每对评分之间的差值需要n(n-1)/2 单位的存储空间，最多需要 m*n*n步.
假设用户已经评价了最多 y 个项目, 那么计算不超过n*n+m*y*y个项目间计算差值是可能的。
如果一个用户已经评价过“x”个项目，预测单一的项目评分需要“x“步，而对其所有未评分项目做出评分预测需要最多 (n-x)x 步. 当一个用户已经评价过“x”个项目时，当该用户新增一个评价时，更新数据库需要 x步。
可以通过分割数据（参照 分割 和稀疏存储（没有共同评价项目的用户可以被忽略）来降低存储要求。
还不想亲自实现？找开源吧
开源的Slope one的程序包
Python：
http://www.serpentine.com/blog/2006/12/12/collaborative-filtering-made-easy/
Java：
http://taste.sourceforge.net/
http://www.daniel-lemire.com/fr/documents/publications/SlopeOne.java
http://www.nongnu.org/cofi/
PHP：
http://sourceforge.net/projects/vogoo
http://www.drupal.org/project/cre
http://www.daniel-lemire.com/fr/documents/publications/webpaper.txt Slope one算法作者写的，简单明了。
5.3 Amazon的 item-to-item 专利算法
在更加普遍的场景中，人们并不总是能给出评分，当用户只提供二元数据（购买与否）的时候，就无法应用Slope One 和其它基于评分的算法。但是却有一个更简单更简单的方法：Amazon的 item-to-item 专利算法
item-to-item算法是二元 item-based协同过滤应用的例子之一，该算法中用二元向量表示用户-项目购买关系的矩阵，并计算二元向量间的cosine相关系数。
如以下应用场景：
在本例当中，项目1和项目2间的cosine相关系数为： 项目1和项目3间的cosine相关系数为： 而项目2和项目3的cosine相关系数为：
于是，浏览项目1的顾客会被推荐买项目3,而浏览项目2的顾客会被推荐买项目3,浏览了项目3的会被推荐买1（并由1推荐2）。该模型只使用了每对项目间的一个参数（cosine相关系数）来产生推荐。因此，如果有n个项目，则需要计算和存储 n（n-1）/2次cosine相关系数。
六、算法评价指标
推荐系统，协同过滤领域，在科学研究上的一些评价指标主要有MAE，AUC，MAP，P@N，P·R·F曲线。而实际应用中还要考虑到系统伸缩性，算法复杂度，等等，那些就不说了，P·R·F指标参考我之前的一篇文章：《 信息检索基本评价指标-P·R·F 》
以下指标详细界定参考论文《Mining mood-specific movie similarity with matrix factorization for context-aware recommendation》及《New Approaches to Mood-based Hybrid Collaborative Filtering》
6.1 平均绝对误差 MAE（Mean Absolute Error）
通过计算预测的用户评分与实际的用户评分之间误差来度量。主要结合交叉验证来实现，公式如下：
（其中，g（authentic）为真实评分，g（prediction）为预测评分，G test ，为整个待预测用户评分集）
6.2平均准确率MAP（Mean Aaverage Precision）
MAP是信息检索中解决P·R·F指标的不足，而提出的，其规范的定义是，设P(R)为系统在召回率为R时的准确率。
单个主题的平均准确率是每篇相关文档检索出后的准确率的平均值。主集合的平均准确率(MAP)是每个主题的平均准确率的平均值。 MAP 是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前(rank 越高)，MAP就可能越高。
一个简单的比方就是（ 参考 ）：
设有两个主题，主题1有4个相关网页，主题2有5个相关网页。某系统对于主题1检索出4个相关网页，其rank分别为1, 2, 4, 7；对于主题2检索出3个相关网页，其rank分别为1,3,5。
对于主题1，平均准确率为(1/1+2/2+3/4+4/7)/4=0.83。
对于主题 2，平均准确率为(1/1+2/3+3/5+0+0)/5=0.45。
则MAP= (0.83+0.45)/2=0.64。
应用与协同过滤中的衡量时，也即是测量系统返回推荐项目对应真实用户喜爱偏好的排名的平均准确率。公式如下：
其中：U为测试用户集，|U|表示用户集的数目，| R i |表示用户 u i 相关的项目（如电影）数据， r i,j 表示系统为用户u i 推荐的第 j 个相关项目对于用户 u i 实际的偏好排名。
6.3 P@n测度
测量对于给定用户ui，前n推荐项目中相关项所占比率。如下公式
6.4 AUC（Area Under Curve）
对于用户u，推荐性能AUC 衡量指标计算公式如下：
其中h（x）是一个指标函数，即若参数值x>0或者逻辑真，着函数值为1，否则为0，Pair(u)是一组用户u待计算的配对集值：
其中Tr（u）是训练集中用户u已经有的项目集，Ts（u）为测试集中用户实际预期应该被推荐的项目，实际上，这里面的 n 也就是测试集不应该被推荐的项目。AUC取值[0,1]，最好的就是1了。
其实以上可以看出，AUC是相对其他准确率测度最不直接的一个，理由是AUC涉及到所有配对，包含相关的项目以及不相关的项目（那些即不出现在训练集，也不出现在测试集中），尽管如此，因为通常数据集中不相关的项目比相关项目多得多，表明了AUC可以对于项目排序的变化没有那么敏感。
一些参考：
http://zh.wikipedia.org/zh-cn/%E5%8D%94%E5%90%8C%E9%81%8E%E6%BF%BE http://www.cs.carleton.edu/cs_comps/0607/recommend/recommender/ http://www.cs.carleton.edu/cs_comps/0607/recommend/recommender/svd.html http://wenku.baidu.com/view/e12b10ea81c758f5f61f67fb.html http://zh.wikipedia.org/wiki/Slope_one http://www.kuqin.com/algorithm/20080903/16387.html http://www.cnblogs.com/kuber/archive/2008/06/10/1216846.html 更多参照文章中的链接 前一篇: 算法：图论中Dijkstra最短路径搜寻算法 后一篇: 算法：求字符串指定最小全集子串发表： 技术相关 , 数据挖掘
跟踪评论 RSS 2.0 订阅 . 你可以跳转到页底，留下评论. 暂无法追踪.
?
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did41997