文档介绍：该【适应用户兴趣变化的协同过滤推荐算法 】是由【Bonnacon】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【适应用户兴趣变化的协同过滤推荐算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。2
2Π2Π
11
2
12
12
12
22
1
12
21
22
1
1
11
1
11
1111
1
计算机研究与发展ISSN10001239CN111777TP
JournalofComputerResearchandDevelopment44(2):296~301,2007
适应用户兴趣变化的协同过滤推荐算法
1122
邢春晓 高凤荣 战思南 周立柱
1(清华大学信息技术研究院Web与软件技术研究中心 北京 100084)
2(清华大学计算机科学与技术系软件研究所 北京 100084)
(******@tsinghuaeducn)
ACollaborativeFilteringRecommendationAlgorithmIncorporatedwithUserIn
terestChange
2
XingChunxiao1,GaoFengrong1,ZhanSinan2,andZhouLizhu2
1(WebandSoftwareTechnologyResearchandDevelopmentCenter,ResearchInstituteofInformationTechnology,TsinghuaUni
versity,Beijing100084)
2(InstituteofSoftware,DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)
Abstract Collaborativefilteringisoneofthemostsuccessfultechnologiesforbuildingrecommendersys
tems,andisextensivelyusedinmanypersonalizedsystemsHowever,existingcollaborativefilteringalgo
rithmsdonotconsiderthechangeofuserinterestsForthisreason,thesystemsmayrecommendunsatis
factoryitemswhenuser’sinteresthaschangedTosolvethisproblem,twonewdataweightingmethods:
timebaseddataweightanditemsimilaritybaseddataweightareproposed,toadaptivelytrackthechange
ofuserinterestsBasedontheanalysis,theadvantagesofbothweightingmethodsarecombinedefficiently
andappliedtotherecommendationgenerationprocessExperimentalresultsshowthattheproposedalgo
rithmoutperformsthetraditionalitembasedcollaborativefilteringalgorithm
Keywords collaborativefiltering;personalizedrecommendation;timebaseddataweight;itemsimilarity
baseddataweight
摘 要 协同过滤算法是至今为止最成功的个性化推荐技术之一,被应用到很多领域中但传统协同过
滤算法不能及时反映用户的兴趣变化针对这个问题,提出两种改进度量:基于时间的数据权重和基于
资源相似度的数据权重,在此基础上将它们有机结合,并将这两种权重引入基于资源的协同过滤算法的
生成推荐过程中实验表明,改进后的算法比传统协同过滤算法在推荐准确度上有明显提高
关键词 协同过滤;个性化推荐;基于时间的数据权重;基于资源相似度的数据权重
中图法分类号 TP3914;TP31113
个性化推荐(personalizedrecommendation)技术根据用户兴趣的相似性来推荐资源,把和当前用户
通过研究不同用户的兴趣,主动为用户推荐最需要相似的其他用户的意见提供给当前用户其优点是
的资源,从而更好地解决互联网信息日益庞大与用无需考虑资源的表示形式,并能为用户发现新的感
户需求之间的矛盾目前,推荐技术被广泛应用到兴趣的资源现有的协同过滤算法存在一个弊端:
电子商务[1]、数字图书馆[2]、新闻网站[3]等系统中不能及时反映用户兴趣变化本文针对这个问题,
协同过滤(collaborativefiltering)是迄今为止应改进推荐算法,提出了两种新的数据加权度量:基于
用最成功的个性化推荐技术[46]它的基本思想是用户访问时间的数据权重和基于资源相似度的数据
收稿日期:2005-11-10;修回日期:2006-05-26
基金项目:国家自然科学基金项目(60473078)
1
1
1
1
1
1
21
1
1
1
1
1
2
1
1
1
1
21
21
12
1
1
1
12
12
112
11
21
1
1
邢春晓等:适1应用户兴趣变化的协同过滤推荐算法2971
权重,将这两种权重引入协同过滤算法的生成推荐Step3对资源j∈Candidate,计算j对u的推
过程中,更好地反映用户兴趣变化,提高推荐精度荐度:
recw(u,j)=∑sim(i,j);
i∈I
1 相关工作u
Step4将Candidate中的资源按加权推荐度大
小排列,其中最前的N个资源作为用户u的推荐集
11 协同过滤推荐算法
相似度计算是影响推荐算法性能的重要因素
在典型协同过滤推荐系统中,输入数据通常可
计算相似度有多种不同的方法,如余弦相似度、
以表述为一个m×n的用户资源访问矩阵R其
Pearson相关系数[7]、条件概率[9]等文中我们选用
中m是用户数,n是资源数,Rij是第i个用户对第j
条件概率来计算资源之间的相似性对于资源i和
个资源的访问记录,矩阵值表示用户访问该资源与
j,用P(i|j)表示他们被同一用户访问的条件概率,
否,1表示访问,0表示未访问例如电子商务系统
它可以衡量资源间相似性计算资源i和j之间的
中,可由顾客交易数据产生购买矩阵,Rij=1表示
相似性公式如下:
顾客i购买了商品j
P(i|j)Freq(ij)
典型的协同过滤算法是基于用户(userbased)sim(i,j)==,
Freq(i)aFreq(j)×Freq(i)a
的[1,5],它的基本原理是利用用户访问行为的相似
性来互相推荐用户可能感兴趣的资源对当前用户(1)
其中,Freq(i),Freq(j),Freq(ij)分别表示访问过
u,系统通过其历史访问记录及特定相似度函数,计
资源的用户数以及同时访问过的用户数α
算出与其访问行为(购买的产品集合、访问的网页集i,ji,j
是一个0~1之间的数,称为缩放系数,引入α的目
等)最相近的k个用户作为用户u的最近邻居集,
的是削弱被访问过很多次的资源在相似度计算中的
统计u的近邻用户访问过而u未访问的资源生成
影响
候选推荐集,然后计算候选推荐集中每个资源i对
现有算法的不足
用户u的推荐度,取其中N个排在最前面的资源作12
现有的协同过滤推荐算法都存在一个问题只
为用户u的topN推荐集:
[7]注重用户或资源间的相似性而忽略了用户兴趣的
为解决传统协同过滤算法的可扩展性问题,,
文献[5,8]提出了基于资源(itembased)的协同过滤动态变化在现实生活中,用户对资源的需求是随
算法,该算法比较资源与资源之间的相似性,由当前着时间的推移不断改变的,传统的协同过滤算法只
用户已访问的资源集合推荐未访问的资源由于资利用用户资源访问矩阵来进行推荐计算,而未考虑
源间的相似性比用户相似性稳定,因此可以离线进用户访问资源的具体时间,因此无法反映出用户的
行计算存储并定期更新,较好地解决了算法的可扩兴趣随时间的变化过程,当用户兴趣发生改变的时
展性问题候,现有的推荐系统无法及时发现,从而导致系统推
相比较而言,基于资源的协同过滤算法推荐精荐的资源在很大程度上偏离了用户的需求
度高,实时性好对这种推荐算法进行优化更具有为解决上述问题,我们将两种数据加权策略:基
现实意义算法1给出了基于资源的协同过滤算法于用户访问时间的数据权重(timebaseddata
描述weight)和基于资源相似度的数据权重(itemsimilar
算法1基于资源的协同过滤推荐算法itybaseddataweight)引入到基于资源的协同过滤
输入:用户u、与之对应的已访问资源集Iu、资算法的推荐过程中,以解决传统协同过滤算法不能
源近邻模型M及时反映用户兴趣变化的弊端
输出:用户u的topN推荐集
过程:2 改进算法描述
Step1对每个资源i∈Iu,读取M得到它的k
最近邻居集Ni={i1,i2,⋯,ik},合并所有Ni得到21 基于时间的数据权重
集合C;现有的协同过滤算法在计算推荐过程中将用户
Step2从C中删除Iu中已经存在的资源,得访问过的每个资源同等对待,这显然是不合理的
到候选推荐项集Candidate;一般来说,用户近期访问过的资源对推荐该用户未
1
1
2
1
1
11
1
1
1
1
1
1
1
1
1
1
1
1
21
11
1
1
298计算机研究与发展 2007,44(2)
来可能感兴趣的资源起比较重要的作用,而早期的可能也和资源i相似,即资源i对生成用户u的推
访问记录对生成推荐影响相对较小,这是因为用户荐起比较重要的作用因此我们可以定义基于资源
的兴趣随时间的推移不断变化,而在较短的一段时相似度的权重函数WS(u,i)衡量资源i和用户u
间内用户的兴趣是相对稳定的,因此一个用户感兴当前兴趣的相关程度,它可以通过i和IuT的总体相
趣的资源最可能和他近期访问过的资源相似因似度sim(i,IuT)计算,而i和IuT总体相似度可以通
此,我们引入基于用户访问时间的数据权重(time过计算i和IuT中每个资源j的平均相似度来表示:
)以提高最近访问数据在推荐生
baseddataweight,∑sim(i,j)
成过程中的重要性j∈IuT
WS(u,i)=sim(i,IuT)=,(3)
size(IuT)
设Dui表示用户u访问资源i的时间与用户u
其中,size(I)表示I中的资源数目通过改变时
最早访问某资源的时间间隔,我们定义基于时间的uTuT
间窗的长短可以得到不同的近期访问集合
权重函数WT(u,i)表示资源i对用户u的权重,T,IuT,
从而影响推荐效果
它是一个和Dui相关的函数值为了突出用户u近
从式()可以看出为计算()需要计
期访问过的资源的重要性,权重函数应该设计成关于3,WSu,i,
算i和IuT中每个资源的相似度,若集合Iu中资源
Dui的非递减函数,即对于Dui>Duj有WT(u,i)≥
数为m,I中资源数为n,则为用户u访问过的所
WT(u,j)本文将基于时间的权重函数作如下uT
有资源进行加权计算的时间复杂度为O(mn),由此
定义:
可见,基于资源相似度的数据加权方法计算量比基
Dui
WT(u,i)=(1-a)+a(2)于时间的数据加权方法要高但由于一个用户访问
Lu,
过的资源数通常比较小,因此不会对算法的实时性
式(2)是一个线形函数,其中Lu表示用户u使
用推荐系统的时间跨度,即该用户最早访问某资源有太大影响
的时间与最近访问某资源的时间间隔,a∈(0,1)称23 两种数据权重的结合
为权重增长指数,改变a的值可以调整权重随访问上面介绍了两种数据加权度量,它们各有优点:
时间变化的速度a越大权重增长速度越快,a的大基于时间的数据权重突出近期数据的重要性,从而
小可以影响到算法性能根据不同的推荐系统,可能够及时捕捉到用户的当前兴趣,适合处理用户兴
以动态调整a的值来优化推荐效果趣变化较频繁的情况;而基于资源相似度的数据权
22 基于资源相似度的数据权重重通过计算用户访问过的某资源与该用户当前兴趣
式(2)中,WT(u,i)的值随着用户u访问资源的相关度,避免了有价值的早期数据被忽略,适合处
i时间间隔Dui呈线性变化,用户近期访问数据的理用户兴趣存在反复的情况因此考虑将两个权重
权重总是大于早期访问数据的权重,从而突出了近函数用一定的比例因子结合起来,定义同时基于时
期数据的重要性但是在现实中,不同用户兴趣变间和资源相似度的权重函数:
化速度和规律不同,此外用户的兴趣经常存在反复,WTS(u,i)=β×WT(u,i)+
所以用户早期访问的资源往往对于生成推荐也很重(1-β)×WS(u,i),(4)
要,单纯使用基于时间的数据权重,削弱了所有早期其中比例因子β∈[0,1],β和(1-β)分别代表两种
资源在推荐计算中的作用,可能对推荐效果产生负权重值所占的比例通过选择合适的β值可以将两
面影响为此我们引入第2种数据加权方法:基于种加权方法的优点结合起来,从而进一步提高推荐
资源相似度的数据权重(itemsimilaritybaseddata算法的准确率
weight)对用户的已访问资源进行加权24 适应用户兴趣变化的协同过滤推荐算法
设用户u的已访问资源集合为Iu,通过定义一我们把上述加权方法引入到传统的协同过滤算
个时间窗(timewindow)T,获取用户u在最近T时法中,提出一种改进的基于资源协同过滤算法首
段内访问过的资源集合为IuT,IuT在一定程度上反先根据前面的式(2)计算并存储每个资源的近邻资
映了用户的近期兴趣对于资源i∈Iu,无论u访问源集,设用户的已访问资源集为Iu,推荐过程中首
i的时间早晚,如果u的近期访问资源集IuT中很多先读入Iu中每个资源i的k最近邻居集及相应的
资源和i相似度很高,说明资源i和用户的当前兴相似度,生成候选推荐集,根据式(3)或(4)计算Iu
趣很相关,则在未来一段时间内,u感兴趣的资源很中每个资源j的权重W(u,j),然后根据计算出的
21
11
11
1
211
1
21
11
11
11
111111
1
1
1
1
1
12
2
211
121
Π1
1
1
22
1
1
邢春晓等:适应用户兴趣变化的协同过滤推荐算法1299
1
数据权重计算候选推荐集中每个资源的加权推荐其中,Hits表示算法产生的正确推荐数,N表示算
度,推荐度最大的前N个资源作为用户u的topN法生成的推荐总数
推荐集算法的具体描述如下:33 实验结果
算法2适应用户兴趣变化的协同过滤推荐算法实验是为了比较本文提出的算法和传统算法之
输入:用户u、与之对应的已访问资源集Iu、资间捕捉用户兴趣变化的能力大小,最终选择1000个
源近邻模型M使用时间跨度超过40天,访问商品数超过10个的
输出:用户u的topN推荐集用户共计38125条记录
过程:我们设计了3组实验,把它们的推荐效果与传
Step1对每个资源i∈Iu,读取M得到它的k统的基于资源的协同过滤算法(即算法1,简称为
最近邻居集Ni={i1,i2,⋯,ik},合并所有Ni得到ItembasedCF)相对比在所有实验中,资源最近邻
集合C;数K=20,观察推荐数目N从10~50每次增加10
Step2从C中删除Iu中已经存在的资源,得不同情况下推荐算法的性能比较实验中我们为所
到候选推荐项集Candidate;用用户计算推荐,以下的实验结果是对所有用户计
Step3对每个资源i∈Iu,根据式(2),(3),或算结果的平均
式(4)计算Weight(u,i);图1给出了不同取值的基于时间的数据权重对
Step4对资源j∈Candidate,计算j对u的加推荐准确率的影响其中权重增长指数a分别取
权推荐度:03,04,05,06,07
recw(u,j)=∑Weight(u,i)×sim(i,j);
i∈Iu
Step5将Candidate中的资源按加权推荐度大
小排列,其中最前的N个资源作为用户u的推荐集
3 实验结果及分析
31 测试数据集
我们用KDD2000的网上交易数据集[10]作为测Fig1 Comparisonofrecommendationqualityoftradi
试数据来对本文提出的算法与传统的基于资源的协tionalitembasedCFalgorithmandourimprovedalgorithm
同过滤算法进行比较原始数据文件是某电子商务usingtimebaseddataweight
图 基于时间的数据权重算法和传统协同过滤算法推
网站的Web日志,通过对日志文件的预处理,保留1
荐效果对比图
了2660个用户对387种商品的90182个有效访问
记录,时间跨度为2个月每个访问记录表示为一从图1可以看出,将基于时间的数据权重引入
个三元组〈用户ID,商品ID,访问时间〉,由于测试传统的协同过滤推荐算法中,推荐精度会有较大的
数据分为训练集和测试集,其中,把实验数据中每个提高,尤其当推荐数目较少时,准确率提高尤为明显
用户最后10天的访问记录隐藏起来作为测试集,其(例如当a取05,推荐数目为10时,准确率比传统
余的访问记录为训练集训练集用于构建用户资源算法提高约16%)由此可见,引入基于时间的数据
访问01矩阵R和进行资源相似度计算权重有效地突出了用户近期访问数据对生成推荐的
32 评价标准重要性,从而使得算法生成的推荐更好地满足用户
实验过程中根据每个用户在训练集中的访问记的当前兴趣同时我们可以看到,权重增长指数a
录为其计算TopN推荐集,如果TopN推荐集中的设置对算法准确率有比较大的影响,对于不同的
某个资源i出现在该用户测试集中的访问记录里,用户和不同类型的资源,用户兴趣的变化速度和变
则表示生成了一个正确推荐我们用信息检索领域化规律也不同,权重增长过快或过慢都会对推推荐
中评估系统效果的准确率(Precision)标准作为对比效果产生负面影响
传统算法和我们的算法推荐精度的标准:图2给出了基于资源相似度的数据权重算法中
Hits不同的时间窗T取值对推荐结果的影响其中T
Precision=,
N分别取5,10,15天
1
1
1
1
1
12
11
2
21
1
11
11
1
11
1
111
122
121
1
2
1
3001计算机研究与发展 2007,44(2)2
1
1
推荐有更好的准确度
1
4 结论和未来工作1
本文针对现1有协同过滤算法不能快速发现用户
12
兴趣变化的问题,提出两种改进方法:基于时间的数
据权重和基1于资源相似度的数据权重,并将两种权1
重有机结合在此基础上,将本文提出的数据权重
Fig2 Comparisonofrecommendationqualityoftradi
方法引入基于资源的协同过滤推荐1算法中1,以反映2
tionalitembasedCFalgorithmandourimprovedalgorithm
用户兴趣的动态变2化2,克服了传统算法的弊1端2
usingitemsimilaritybaseddataweight
加权算法简单易行、效率高、实时性好对比实
图2 基于资源相似度的数据权重推荐算法和传统基于
资源协同过滤算法的推荐准确率对比验表明,引入两种数据权重后,如果参数设置得当,
算法性能会有较大提高从实验结果还可以看出,
实验结果表明,基于资源相似度的数据权重整
体上比基于时间的数据权重在推荐效果上更好一将两种加权方法加以综合能够更有效地捕捉用户兴
些这是由于基于资源相似度的数据权重避免了早趣,因此推荐精度更高
我们未来的工作包括以下两方面一方面不同
期重要数据被忽略,可以有效地处理用户兴趣反复:,
的用户兴趣的变化规律也不同针对不同用户选取
的情况此外,我们得到T=10时算法性能最好,这,
说明时间窗的长短对推荐准确率有一定影响,过长不同的方案并设置不同的参数比设置固定参数有可
则无法反映用户当前兴趣,过短会使计算出的数据权能得到更好的结果,因此我们将对权重函数中参数
重有很大的随机性,都会对算法性能起到负面作用的自动确定方法做进一步研究另一方面,不仅用
最后我们测试同时基于时间和资源相似度的综户兴趣随时间变化,特定类型的资源受欢迎程度也
合权重算法的性能在前两组实验中,我们分别得可能对时间比较敏感(比如电器类产品)因此下一
到a=05,T=10时算法性能达到最优,因此在计步我们考虑将用户兴趣度按时间分段预测,比如以
算综合权重过程中我们就设a=05,T=10为了季度为单位,适合对时间较敏感的产品,从而形成一
获得式(4)中最合适的β值,我们进行了一组改变β个分段连续的预测模型
的实验,让β从02变动到08,每次增加01,结果
如图3所示:参 考 文 献
[1]JSchafer,JKonstan,JRiedlRecommendersystemsinecom
merce[C]In:ProcofACMECommerceNewYork:ACM
Press,1999158-166
[2]ChampaJayawardana,KPriyanthaHewagamageMasashitoHI
rakawaApersonalizeinformationenvironmentfordigitalli
braries[J]InformationTechnologyandLibraries,2001,20
(4):185-196
[3]JKonstan,BMiller,DMaltz,etalGroupLens:Applying
collaborativefilteringtoUsenetnews[J]Communicationsof
Fig3 Recommendationprecisionusingdifferentβon
theACM,1997,40(3):77-87
combineddataweight
[4]GaoFengrongResearchonthekeytechniquesofpersonalized
图3 不同比例的综合加权对算法准确率的影响
recommendersystems:[PhDdissertation][D]Beijing:Ren
由图3可以看出,如果β值选取适当,综合数据minUniversityofChina,2003(inChinese)
权重比两种数据权重单独使用效果又有进一步提(高凤荣个性化推荐系统关键技术研究:[博士论文][D]
北京:中国人民大学,2003)
升,这是由于它结合了两种加权方法优点,不仅能突
[5]GregLinden,BrentSmith,JeremyYorkAmazoncomrecom
出近期数据的重要性,又避免了早期数据被忽略,从mendations:ItemtoItemcollaborativefiltering[J]IEEEIn
而更准确地反映了用户的兴趣变化趋势,使生成的ternetComputing,2003,7(1):76-80
1
1
21
12
222
1
12
221112
2
11
12221
11
11
121112
22
2
11
1
11
1ΠΠΠ2
1
ΠΠ12
1
1
1
1
1
222
11
22
12
1
邢春晓等:适应用户兴趣变化的协同过滤推荐算法301
[6]GAdomavicius,ATuzhilinTowardthenextgenerationofrecGaoFengrong,bornin1975Postdoctorin
ommendersystems:AsurveyofthestateoftheartandpossibletheDepartmentofComputerScienceand
extensions[J]IEEETransonKnowledgeandDataEngineerTechnologyofTsinghuaUniversityHer
()
ing,2005,176:734-749currentresearchinterestsincludepersonalized
[7]ChunZeng,ChunXiaoXing,LiZhuZhou,etalSimilarity
service,digitallibraryandegovernment
measureandinstanceselectionforcollaborativefilteringinterna
高凤荣,1975年生,博士后,主要研究方向为个性化服务、数
tional[J]JournalofElectronicCommerce,2004,4(8):115-
字图书馆、电子政务
129
[8]GKarypisEvaluationofitembasedtopNrecommendational
gorithms[C]In:ProcofCIKM2001NewYork:ACMZhanSinan,bornin1980MasterHiscur
Press,2001247-254rentresearchinterestsincludepersonalized
[9]BrendanKitts,DavidFreed,MartinVriezeCrosssell:Afastservice,datamining,anddigitallibrary
promotiontunablecustomeritemrecommendationmethodbased战思南,1980年生,硕士,主要研究方向为
onconditionalindependentprobabilities[C]In:ProcofACM个性化服务、数据挖掘、数字图书馆
SIGKDDInt’lConfNewYork:ACMPress,2000437-446
[10]KDD2000Dataset[OL]http:,bornin1947Professorand
CUPdata,2005PhDsupervisorHismainresearchinter
estsincludedatabasetechnology,digitalli
XingChunxiao,bornin1967Professorand
brary,andetc
directorofWebandSoftwareTechnology
周立柱,1947年生,教授,博士生导师,主
ResearchandDevelopmentCenterofTs要研究方向为数据库技术、数字图书馆等
inghuaUniversityHismainresearchinter
estsincludedatabasetechnology,software
engineering,personalizedservise,anddigitallibrary,digital
government
邢春晓,1967年生,研究员,清华大学Web与软件研究中心
主任主要研究方向为数据库技术、软件工程、个性化服务、
数字图书馆、电子政务
Researchbackground
OurworkissupportedbytheNationalNaturalScienceFoundationofChinaNo60473078,named“ResearchonTheoryand
TechnologyofPersonalizedServiceBasedonInformationFiltering”Intheconstructionoflargeapplicationsystems,suchasdigital
library,Egovernment,andEcommerce,howtoprovideuserswitheffi