加载中…
个人资料
yfx416
yfx416
  • 博客等级:
  • 博客积分:0
  • 博客访问:103,799
  • 关注人气:75
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

协同过滤

(2011-10-03 00:02:20)
标签:

协同过滤

分类: 数据挖掘

在社交网络的系统设计中,推荐是一种很常见的功能。比如说,人人网有推荐好友的功能,淘宝有推荐商品的功能。那么这些功能是如何实现的呢?其实就是基于我们这篇博客要谈到的算法-协同过滤。协同过滤就是解决类似这样的推荐问题的。这篇博客就介绍一下协同过滤算法(简称CF-collactive filter)。

先简单描述一下整个算法所工作的系统的背景。

1.这是一个书籍推荐系统,在这个系统中有一系列的用户:

U ={u[x] : x = 1...m} m表示用户有m个

2.一系列的物品(书籍) I:

I = {i[x] : x = 1...n} n表示系统中有n本书籍

3.一系列的类别,这些类别有p个。每一本书籍都属于这p个类别中的一个或多个。举个例子来理解,在书籍推荐系统中我们有一系列的类别,比如计算机类,医学类,艺术类,文学类,经济类,历史类,学术类,通俗类等等。每一本书籍都属于这些类别中的一个或多个,比如《资本论》这本书同时属于经济类和学术类,《安徒生童话》就同时属于文学类和通俗类。这些类别表示如下:

C = {c[x] : x =1...p}

4.一系列的显式评级,这些评级有q级,比如用户可以对书籍进行评级,1星,2星,3星,4星,5星,1星最差,5星最好:

R = {r[x] : x=1...q, q^q <= m*n }

5.一系列用户针对分类的隐性的评级, 该隐性评级有t级:

R = {r'[x]:x=1...t, t^t <= m*p }

怎么理解呢?假设一本书,如果它获得了某一用户3星或3星以上的评价,那么我们就认为这个用户对这本书是“好”的评价,否则这本书就是“坏”的评价。我们又知道任何一本书都属于一个或多个分类,那么我们就可以得到用户对该这本书所对应的分类的评价是“好”还是“坏”。那么我们就可以得到一个用户对所有分类的评价矩阵,元素就是用户对该分类做出“好”或“坏”评价的个数。比如张三,他对《资本论》(经济类,学术类)做出了4星评价,对《安徒生童话》(文学类,通俗类)做出了2星评价,对《水浒传》(文学类,通俗类)做出了3星。那么就会得到如下数据:

经济类(+) 经济类(-) 学术类(+) 学术类(-) 文学类(+) 文学类(-) 通俗类(+) 通俗类(-)

张三 1 0 1 0 1 1 1 1

+表示“好”评价 -表示“坏”评价

那么隐性评级可以按照这个公式来计算:

0AC50537F7E7C65A10061613247997AB7442C762

假设我们认为隐性的评级从0到10分,那么张三对经济类得隐性评分为10*1/(1+0) = 10

对文学类得隐性评级为10*1/(1+1)=5

等等

6.用户A7EF14C2D85D8677B4555D0586EF1AC16BADD256对某本书籍E156D8772F1FC97C63EFB2A1DE5023AADDF6324A的显式评级表示为FBD2308EC1C9748367877A566E1E347CEC729C36

7.用户0F86FB8C0CA91D2B04C8A4ED867E7419D96CAF9E对所有书籍的平均显式评级为B3199F0B46BDA5A678E2DA68DFE89D5D20D7B74B这个也很重要,想想看吧,有一个吝啬的用户,他对所有书籍给的评价都很低,3星对她而言都是很高的评价了,对于这种用户,这个平均评级就很有意义了。

好吧,到这里我们就得到了以下三个矩阵,它们将是我们进行推荐的基础。需要解释一下的是矩阵3 - item-category bitmap,1 表示物品I属于某一分类,0表示物品不属于某一分类。比如Ix 属于C1,Cx两个类别,而不属于其它类别。

02DB0174B0480A17009691FF1A70B201D84FA38C

那么接下来的推荐就很简单了,推荐分为两种:推荐人和推荐物。无论哪一种推荐,方法都是一样的。比如推荐用户,我们就计算所有用户之间的相似度,那么就可以根据相似度的高低来进行推荐。我们还可以计算物品之间的相似度,这样当用户买了《格林童话》之后,系统还可以推荐给你一些你可能感兴趣的其他书籍。系统还可以给用户推荐书籍,它可以把相近用户评价高的书籍推荐给用户,提供“买过这本书的用户还买过...”这样的功能。那么剩下的问题就是如何计算相似度了,计算的方法很多,比如余弦夹角,比如皮尔森系数。皮尔森系数在一些论文的工作中被认为是很好的一种方法。

所谓皮尔森系数指的是协方差除以方差,用公式表示就是:

55A42FDFD8712D988E129E48E636874B54CDF383

其实就是

386A1982166FB812E1D0F77AE50145C34263FA43

那么对应到协同过滤算法中,相似度计算如下:

基于显式评级的的用户相似度:

4F9B333B4F569E4245EE9B0DFB7055138D1478D4

n'表示系统中所有书籍

基于隐式评级的用户相似度:

7E91631D5AE7BBE824C73A238BC0194DF4976C9E

对于用户推荐,其本质就是如果用户对于书籍给出了相近的评价,或者对于某些领域表现出相近的评价,那么这两个人兴趣相同,就应该推荐。

基于显式评级的物品相似度:

D7802D61016EA68FE1936680851DAA6222F2282A

这个相似度本质上就是计算用户们对这两个物品的显式评级是否相近。

基于分类位图的物品相似度:

D034CA348533F05FF43452748B99B1D214805991

这个相似度本质上就是计算物品是否属于相近的分类类别。

注意:上面这些公式分子上面的'-'应为'*',从文献上拷图下来的,可能有错误,懒得改了。

这就是最基本协同过滤算法,很多电子商务网站的推荐系统都利用过这个方法。这个算法的不足就是计算比较大,试想一下为了计算两个用户a和b之间的相似度,每次都需要遍历一遍a评价过的商品和b评价过的商品(为了计算平均评级,方差等等),随着用户评价的商品越来越多,这个计算会越来越大,越来越膨胀。因此,有人提出了增量更新的办法来改进协同过滤,利用上一次更新的结果来减少计算。在后面的博客中,博主会介绍它。

文献

[1]http://pespmc1.vub.ac.be/COLLFILT.html

[2]http://original.jamesthornton.com/cf/

[3]Qualitative analysis of user-based and item-based prediction algorithms for recommendation agents

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有