推荐功能的两种算法

标签: 功能 算法 | 发表时间:2012-02-28 17:56 | 作者:yysyangyangyangshan
出处:http://blog.csdn.net

    最近做了一个类似淘宝的根据用户的操作,判断出用户对哪些产品感兴趣,并按照一定关系推荐给用户其它产品。查询了一些资料,结果发现时下,很多地方都用到了推荐,淘宝,优酷,迅雷等等,有时候确实让人称心如意,推荐的产品非常和你的胃口,不过也有时推荐的让你莫名其妙。其实推荐的算法有很多种,而且不一定有固定的模式,它会根据产品的特性,推荐的目的,以及其它方面的要求而不同。
不过具体的不一样,但是其原理性的大概有以下几种算法。专门研究算法的人写的太深奥了,全部都是数学术语,太难懂了,我还是以自己的理解来说明下吧。
1、Apriori算法
    Apriori算法是很复杂的,基本思想如下:
    首先找出所有的已收集到的集合,即根据操作记录的集合。然后由这个集合产生强关联规则。然后使用第1步的集合产生期望的规则,产生只包含集合的项的所有规则,其中每一条规则的右部只有一项,这里采用的是中规则的定义。一旦这些规则被生成,那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集,使用了递推的方法。
    我理解的基本步骤如下。
    基本步骤是
    a、根据操作收集对象的属性;

    b、根据已收集的属性为条件,从包含所有数据的库中搜索与之相关的对象;

    c、按照一定的规则过滤,剩下的向用户推荐。

    举例来说,例如在淘宝买东西,用户买了手机,电脑,衣服等,每买一件都记录下来,作为推荐的依据;那么如何推荐呢,手机和电脑属于数码类,那么推荐就可以推荐相机等数码产品,同时,还可以推荐其它品牌的手机或电脑。根据衣服推荐亦相同。当然了,这只是很简单的推荐,不一定能对用户的心思。要想做准确的推荐在每一步中都要进行处理。
    2、Slope One算法
    使用基于Slope One算法的推荐需要以下数据:
    1. 有一组用户
    2. 有一组Items(文章, 商品等)
    3. 用户会对其中某些项目打分(Rating)表达他们的喜好
    Slope One算法要解决的问题是, 对某个用户, 已知道他对其中一些Item的Rating了, 向他推荐一些他还没有Rating的Items, 以增加销售机会. :-)

    一个推荐系统的实现包括以下三步:
    1. 计算出任意两个Item之间Rating的差值
    2. 输入某个用户的Rating记录, 推算出对其它Items的可能Rating值
    3. 根据Rating的值排序, 给出Top Items;

    第一步:例如我们有三个用户和4个Items, 用户打分的情况如下表.

Ratings User1 User2 User3 
Item1 5 4 4 
Item2 4 5 4 
Item3 4 3 N/A 
Item4 N/A 5 5 

    在第一步中我们的工作就是计算出Item之间两两的打分之差, 也就是使说计算出以下矩阵:

Item1 Item2 Item3 Item4 
Item1 N/A 0/3 2/2 -2/2 
Item2 0/3 N/A 2/2 -1/2 
Item3 -2/2 -2/2 N/A -2/1 
Item4 2/2 1/2 2/1 N/A 

    考虑到加权算法, 还要记录有多少人对这两项打了分(Freq), 我们先定义一个结构来保存Rating:

 public class Rating
    {
        public float Value { get; set; }
        public int Freq { get; set; }

        public float AverageValue
        {
            get {return Value / Freq;}
        }
    }

    我决定用一个Dictionary来保存这个结果矩阵:
    public class RatingDifferenceCollection : Dictionary<string, Rating>
    {
        private string GetKey(int Item1Id, int Item2Id)
        {
            return Item1Id + "/" + Item2Id;
        }

        public bool Contains(int Item1Id, int Item2Id)
        {
            return this.Keys.Contains<string>(GetKey(Item1Id, Item2Id));
        }

        public Rating this[int Item1Id, int Item2Id]
        {
            get {
                    return this[this.GetKey(Item1Id, Item2Id)];
            }
            set { this[this.GetKey(Item1Id, Item2Id)] = value; }
        }
    }

接下来我们来实现SlopeOne类. 首先创建一个RatingDifferenceCollection来保存矩阵, 还要创建HashSet来保持系统中总共有哪些Items:
    public class SlopeOne
    {       
        public RatingDifferenceCollection _DiffMarix = new RatingDifferenceCollection();  // The dictionary to keep the diff matrix
        public HashSet<int> _Items = new HashSet<int>();  // Tracking how many items totally

方法AddUserRatings接收一个用户的打分记录(Item-Rating): public void AddUserRatings(IDictionary<int, float> userRatings)
AddUserRatings中有两重循环, 外层循环遍历输入中的所有Item, 内层循环再遍历一次, 计算出一对Item之间Rating的差存入_DiffMarix, 记得Freq加1, 以记录我们又碰到这一对Items一次:
    Rating ratingDiff = _DiffMarix[item1Id, item2Id];
    ratingDiff.Value += item1Rating - item2Rating;
    ratingDiff.Freq += 1;

对每个用户调用AddUserRatings后, 建立起矩阵. 但我们的矩阵是以表的形式保存:
  Rating Dif Freq
Item1-2 0 3
Item1-3 1 2
Item2-1 0 3
Item2-3 1 2
Item3-1 -1 2
Item3-2 -1 2
Item1-4 -1 2
Item2-4 -0.5 2
Item3-4 -2 1
Item4-1 1 2
Item4-2 0.5 2
Item4-3 2 1


第二步:输入某个用户的Rating记录, 推算出对其它Items的可能Rating值:
public IDictionary<int, float> Predict(IDictionary<int, float> userRatings)
也是两重循环, 外层循环遍历_Items中所有的Items; 内层遍历userRatings, 用此用户的ratings结合第一步得到的矩阵, 推算此用户对系统中每个项目的Rating:
    Rating itemRating = new Rating(); // Prediction of this user"s rating
    ...
    Rating diff = _DiffMarix[itemId, inputItemId]:
    itemRating.Value += diff.Freq * (diff.AverageValue + userRating.Value);
    itemRating.Freq += diff.Freq;

第三步:得到用户的Rating预测后,就可以按rating排序, 向用户推荐了. 测试一下:
    Dictionary<int, float> userRating userRating = new Dictionary<int, float>();
    userRating.Add(1, 5);
    userRating.Add(3, 4);
    IDictionary<int, float> Predictions = test.Predict(userRating);
    foreach (var rating in Predictions)
    {
        Console.WriteLine("Item " + rating.Key + " Rating: " + rating.Value);
    }   
输出:
Item 2 Rating: 5
Item 4 Rating: 6

改进:
观察之前产生的矩阵可以发现, 其中有很多浪费的空间; 例如: 对角线上永远是不会有值的. 因为我们是用线性表保存矩阵值, 已经避免了这个问题;
对角线下方的值和对角线上方的值非常对称,下方的值等于上方的值乘以-1; 在数据量很大的时候是很大的浪费. 我们可以通过修改RatingDifferenceCollection来完善. 可以修改GetKey方法, 用Item Pair来作为Key:
    private string GetKey(int Item1Id, int Item2Id) {
        return (Item1Id < Item2Id) ? Item1Id + "/" + Item2Id : Item2Id + "/" + Item1Id ;;
    }
C#实现代码: http://download.csdn.net/detail/yysyangyangyangshan/4097454

作者:yysyangyangyangshan 发表于2012-2-28 17:56:17 原文链接
阅读:3 评论:0 查看评论

相关 [功能 算法] 推荐:

推荐功能的两种算法

- - CSDN博客推荐文章
    最近做了一个类似淘宝的根据用户的操作,判断出用户对哪些产品感兴趣,并按照一定关系推荐给用户其它产品. 查询了一些资料,结果发现时下,很多地方都用到了推荐,淘宝,优酷,迅雷等等,有时候确实让人称心如意,推荐的产品非常和你的胃口,不过也有时推荐的让你莫名其妙. 其实推荐的算法有很多种,而且不一定有固定的模式,它会根据产品的特性,推荐的目的,以及其它方面的要求而不同.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.

贪心算法

- Shan - 博客园-首页原创精华区
顾名思义,贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择. 当然,希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解. 如单源最短路经问题,最小生成树问题等.

缓存算法

- 成 - FeedzShare
来自: 小彰 - FeedzShare  . 发布时间:2011年09月25日,  已有 2 人推荐. 没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率.

K-Means 算法

- - 酷壳 - CoolShell.cn
最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家. k-Means 算法是一种  cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法.

查找算法:

- - CSDN博客推荐文章
从数组的第一个元素开始查找,并将其与查找值比较,如果相等则停止,否则继续下一个元素查找,直到找到匹配值. 注意:要求被查找的数组中的元素是无序的、随机的. 比如,对一个整型数组的线性查找代码:. // 遍历整个数组,并分别将每个遍历元素与查找值对比. 要查找的值在数组的第一个位置. 也就是说只需比较一次就可达到目的,因此最佳情况的大O表达式为:O(1).

排序算法

- - 互联网 - ITeye博客
排序算法有很多,所以在特定情景中使用哪一种算法很重要. 为了选择合适的算法,可以按照建议的顺序考虑以下标准: .     对于数据量较小的情形,(1)(2)差别不大,主要考虑(3);而对于数据量大的,(1)为首要.  一、冒泡(Bubble)排序——相邻交换 .  二、选择排序——每次最小/大排在相应的位置 .

联接算法

- - CSDN博客数据库推荐文章
本文摘自《锋利的SQL》: http://item.jd.com/10380652.html. 在Microsoft SQLServer Management Studio中执行查询时,如果选定工具栏中的 按钮,可以看到为查询生成的执行计划. 执行计划以图形方式显示了SQL Server查询优化器选择的数据检索方法,如表扫描、排序、哈希匹配等.

BTrace功能

- - zzm
       在生产环境中可能经常遇到各种问题,定位问题需要获取程序运行时的数据信息,如方法参数、返回值、全局变量、堆栈信息等. 为了获取这些数据信息,我们可以 通过改写代码,增加日志信息的打印,再发布到生产环境. 通过这种方式,一方面将增大定位问题的成本和周期,对于紧急问题无法做到及时响应;另一方面重新部 署后环境可能已被破坏,很难重新问题的场景.