下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 个性化微博推荐算法

个性化微博推荐算法.doc

个性化微博推荐算法

钟言果
2017-12-09 0人阅读 举报 0 0 暂无简介

简介:本文档为《个性化微博推荐算法doc》,可适用于人文社科领域

个性化微博推荐算法王晟王子琪张铭(北京大学信息科学技术学院北京)摘要:微博不同于传统的社会网络和电子商务网站存在用户活跃程度低、微博数据稀疏和用户兴趣动态变化等特点。由于这些挑战的存在因此将传统推荐算法应用于微博推荐时效果并不理想。本文提出一种基于贝叶斯个性化排序的微博推荐算法对用户进行个性化微博推荐。所提出的基于贝叶斯个性化排序的微博推荐算法以微博对的形式提取微博系统中的隐式信息对这些微博对学习从而得到用户对不同微博的兴趣值。根据每条微博发出的时间估计每条微博对的可信度。发出时间越接近的微博对它的可信度就越高并且对用户的兴趣值影响就越大。通过在新浪微博的真实数据上进行实验和评测结果表明本文所提出的基于贝叶斯个性化排序的微博推荐算法相比于对比算法在进行推荐微博时有更好的效果。关键词:微博推荐贝叶斯个性化排序中图分类号:TPAPersonalizedRecommendationAlgorithmonMicroblogsWangSheng,WangZiqi,ZhangMing(PekingUniversity,ElectronicsEngineeringandComputerScience,Beijing)Abstract:Microbloggingcommunityisdifferentfromconventionalsocialnetworksorecommercesystemsforitslowuseractivity,datasparsityanddynamicofuserinterestsBecauseofthesechallenges,conventionalrecommendationalgorithmscannotgetdesirableperformanceinmicrobloggingcommunityThispaperproposesanovelrecommendationalgorithmbasedonBayesianPersonalizedRanking(BPR)bymodelinguser’simplicitfeedbacksinmicrobloggingcommunityTheproposedalgorithmcollectsimplicitfeedbacksintheformofmicroblogspairsandusesthemastrainingpairstolearnusers’interestThispaperdefinesaconfidentialscoreforeachmicroblogspairsbasedonthetimeuserreceiveditMicroblogspairswithshorterintervaltimehavehigherconfidentialscoreandthushavemuchmoreimpactonuser’sinterestExperimentsontworealworldMicroblogsdatasetsshowthatourrecommendationalgorithmoutperformsallthebaselinesKeywords:MicroblogsRecommendationBayesianPersonalizedRanking引言Web时代一个具有代表性的网络现象就是微博的兴起。微博让人们通过虚拟的网络来获取实时、海量的信息。现在流行的微博网站国外有Twitter国内有新浪微博等。在微博上的研究也有许多比如在微博上找到影响力最高的用户在微博上进行广告的宣传和投资检测微博信息的真实性从而防止谣言的传播对微博信息分类等。在微博上关于推荐的研究也有很多。大部分是进行好友推荐、散列标签(HashTag)推荐或者新闻推荐而对于微博中主要的载体简短却包含海量实时信息的微博内容推荐的研究则不多。微博内容推荐(以下简称微博推荐)有以下三个难点:基金项目:自然科学基金()教育部科技发展中心网络时代的科技论文快速共享专项研究资助课题()核高基项目(ZX)作者简介:王晟()男上海人北京大学本科生研究兴趣为社会网络分析、推荐算法等。ShengWangwasborninHeisanundergraduatestudentatPekingUniversityHisresearchinterestsincludeanalysisofsocialnetworkandrecommendationalgorithm通信联系人:张铭()女北京大学教授、博士生导师研究领域为文本挖掘、社会网络分析等。MingZhangwasborninSheisaprofessoranddoctoralsupervisoratPekingUniversityHerresearchinterestsincludeanalysisofsocialnetworkandtextdataEmail:mzhangnetpkueducn()用户的活跃程度低。在传统的推荐系统中用户登录一个推荐系统就是为了选择一些他想要的资源。而在微博推荐中许多用户上微博更多的时间处于“看微博”而不是“发微博”因此很难直接获得他们的显式反馈信息也难以对他们的兴趣进行学习和预测。()数据的稀疏性和不对称性。在传统的推荐问题中用户和资源一般是同一个数量级的。但是在微博推荐问题中由于微博数据海量的特点微博的数量和增长速度远远大于用户的数量和增长速度。()用户兴趣的动态变化。微博的话题一直紧随现实世界的发展导致微博上话题不断变化用户的兴趣也随之变化。在传统推荐问题中往往是用户根据兴趣选择资源。在微博推荐中则是不断出现的微博改变着用户的兴趣再由用户选择喜欢的微博。因此用户的兴趣一直在动态变化很难找到一个用户长时间感兴趣的话题。推荐系统中大部分研究都是利用系统中的一些显式信息来进行学习和预测。显式信息指的是由用户主动提供给网站的信息如用户的资料、用户喜爱的资源。而与显式信息对应的隐式信息指的是网站自动获得的信息如用户的浏览时间、上下文环境等。在现实世界中大量的信息都是隐式信息而不是显式信息。相比显式信息隐式信息不需要用户主动来提供因此更容易在实际应用中被使用。事实上在用户浏览的过程中浏览器和服务器都已经记录了大量的隐式信息可以通过各种方法从后台数据库中和浏览日志中挖掘出来。在微博系统中也存在着多种隐式信息。例如用户发出微博的时间、用户浏览微博时上下文环境、用户与其他用户之间的好友关系。针对以上难点本文提出了一种基于贝叶斯个性化排序(BayesianPersonalizedRankingBPR)的微博推荐算法。BPR的主要思想是利用贝叶斯最大后验估计求出微博对之间的全序关系从而获得用户对微博的个性化排序。本文的贡献有:()利用推荐系统中用户浏览上下文环境这个隐式信息来解决微博推荐问题中用户活跃程度低、发出微博少的问题。()利用基于微博对的推荐算法来解决数据的稀疏性和不对称性。()利用微博所发出的时间这个隐式信息来实时地获取用户的当前兴趣从而解决用户兴趣动态变化的问题。相关工作Twitter有许多推荐算法的应用比如根据用户的资料和兴趣为其推荐可能感兴趣的好友在用户撰写微博时根据微博的内容为其推荐合适的散列标签根据用户以往转发的微博和关注的话题为其推荐可能感兴趣的热点新闻。推荐系统算法中比较成功的是协同过滤算法。基于用户的协同过滤算法通过将用户与系统中其他用户进行比较找到兴趣与该用户最相似的用户群通过对这个用户群进行学习从而对该用户的行为进行预测。这个算法基于现实世界的一个理论“与我行为相似的人喜欢这个东西那么我通常也会喜欢这个东西”。基于用户的协同过滤算法主要有两个模型最邻近点对模型和潜在参数模型。()最邻近点对模型最邻近点对模型首先定义一种用户相似性的评价标准。当要预测用户u对一个资源i的兴趣值时由与用户u最相似的邻居群对资源i的兴趣值来决定。例如将用户u的“邻居”们对资源i的兴趣取平均值作为用户u对资源i的兴趣值。()潜在参数模型潜在参数模型通过学习未被直接观察到的参数来预测推荐系统中未观察到的值。一个Wu对每个资典型的潜在参数模型是矩阵分解模型。对每个用户u找到一个k维向量Hi。并且假设模型中每个用户u对每个资源i的兴趣为对应的潜在源i找到一个k维向量Wu和Hi的内积。向量微博推荐个性化推荐算法的目标是提供给每个用户个性化的、最有可能会感兴趣的一个资源序列。本文提出的微博推荐算法即为一个个性化推荐算法目标是为每个用户提供一个他最可能会感兴趣的微博集合。本文以实际微博系统中用户转发了这条微博来模拟用户选择了这条微博。还将用户对微博的行为定义为回应:用户看到并且转发了这条微博则为正回应其他的情况包括用户未看到这条微博或者用户看到了这条微博但是没有转发都作为未来可能要预测的缺失回应。传统的推荐算法在推荐时会给用户提供多个资源进行选择这些资源就构成了用户选择的上下文环境。用户最终会在这些资源中选择一个、多个或零个资源。许多推荐算法忽视了用户所处的上下文环境即用户是在与什么资源比较下选择了当前资源而仅仅考虑了用户的最终选择。例如电影推荐网站电驴网给用户推荐电影时通常会给用户部电影选择。用户从中选择一部而其余的部则被舍弃。传统的推荐算法只将这被选中的一部作为正回应而忽视了其他的部所代表的负回应仅仅将他们作为缺失数据。在微博推荐问题中由于用户的不活跃导致用户选择的微博数量少而用户面对的可选微博数量又非常大因此本文通过考虑上下文环境来收集隐式信息。另一方面由于微博信息的实时性和大量性的特点用户的兴趣会不停地随着最近发出的微博内容而变化。统计结果表明用户在面对不同时间段发的微博喜好的程度也会随着时间变化。这时候就需要一种能够考虑时间因素的推荐算法。为了能够考虑上下文环境和时间因素本文使用微博对来代替微博作为训练集这里的(u,i,ji,,ttj)。这个五元组的含义是用户u在同时面对微博i和微博对定义为一个五元组tt微博j时选择了微博i而没选择微博j。i为用户u发出微博i的时间j为微博j发出的时间。DS由此定义训练集,DS:,,u,i,j,ti,tj)|iI,jII(uu这个定义有以下几个优点:()通过微博对可以将用户所处的上下文环境也考虑进去不仅仅考虑用户实际转发的微博也考虑了用户未转发的微博利用了微博数据量大的特点来弥补数据稀疏和用户活跃程度低的问题从而扩大训练集使得推荐效果更好。()引入时间变量根据微博实时性、话题不断变化的特点更好的预测用户兴趣。基于BPR的微博推荐算法形式化定义定义U为所有用户构成的集合I为所有微博构成的集合S为所有观察到的正回应构成的集合。在微博推荐问题中SU,I。例如一个用户u转发了微博i则(u,i)就是一个正回应并且属于S。本文的算法是为每个用户找到一个对于所有微博的个性化的全序,u。,u满足全序关系的三条性质:关系完全性:i,jI:i,j,i,ujj,ui反对称性:i,jI:i,uj,j,ui,i,ji,j,kI:i,uj,j,uk,i,uk传递性:矩阵分解模型X为用户与微博的兴趣矩阵X:|U|,|I|。X是一个实数值矩阵Xui的值越高代表用户u对微博i的兴趣值越高。当进行矩阵分解时兴趣矩阵X被近似成两个低秩矩阵W:|U|,k和H:|I|,k的Wu对应每个用户的特征向量矩阵H的每一行Hi所积。矩阵W的每一行所表示的行向量表示的行向量对应每个资源的特征向量。维数k表示矩阵分解模型的潜在参数k一般远小于|U|和|I|以此达到矩阵分解时降维的作用。tˆ满足:X:,WH()kxˆui,wu,hi,wuf,hiff,()W和H从而使得Xˆ研究的目标是通过基于BPR的微博推荐算法找到最合适的矩阵与X最为近似。基于BPR的微博推荐算法描述BPR算法利用最大后验估计来求出参数矩阵W和参数矩阵H。根据贝叶斯公式:p(,,u)p(,u,)p(,)(),u代表用户u对于不同微博的全序关系,即为参数W和H。这里假定不同用户之间对于微博的选择是相互独立的并且一个用户对不同微博对的选择也是相互独立的根据概率的积公式有:,((u,i,j)DS),),j,)p(,up(i,uuU(u,i,j)U,I,I,(p(i,uj,)),((u,i,j)DS)()如果b成立,否则其中这个公式可以被简化为:,),j,)p(,p(i,uuuU(u,i,j)DS()假设一个用户u在面对微博i和微博j时选择了微博i的概率为:p(i,uj,):,,(xˆuij(,))(),(x):,exxˆuij是与模型参数,相关的一个函数xˆuij代表用户u在面对微其中i和微博j时选择微博i而非选择微博j的偏好分值。博假设这个偏好分值与用户与微博的兴趣矩阵中用户u对微博i的兴趣值减去用户u对xˆ微博j的兴趣值成正比。因此uij定义为:xˆuij,(xuiˆxˆuj),f(ittj)()xˆ其中f(t)是关于时间的一个函数。ui已经在中定义。根据对微博的观察发现用户更偏向于转发最近发出的微博并且对于一条微博的兴趣会随着时间下降。所以令:f(t),t()这样定义的直观含义是:两条微博时间差距越大则对应微博对的全序关系可信度越小时间差距越小则对应微博对的全序关系可信度越高。为了求出后验概率还需要获得参数W和H的先验概率。假设参数W和H的先验概率分布符合一个均值为的正态分布。p(,)~N(,,)()至此可以使用最大后验概率估计的方法求参数W和H。BPROPT:,lnp(,,u),lnp(,u,)p(,),ln)p(,)ˆ,(xuij(u,i,j)DS,ˆln,(xuij)lnp(,)(u,i,j)DS,ˆln,(xuij),(u,i,j)DS()对于训练集中的每一组训练数据基于BPR的微博推荐算法的时间复杂度是O(K)。学习算法对于上一节得到的目标函数采用梯度下降法作为学习算法。首先将目标函数对于参数,求导BPROPT,ln,(xuijˆ),,,,(u,i,j)DSxˆeuij,xˆuij,xˆuij,e(u,i,j)DS()xuij根据的定义有,(hifhjf)uf如果,,w,如果,,hif,wufxˆuij,,,如果,,hjf,wuf否则,()梯度下降算法过程:第一步初始化W、H为正态分布矩阵DS中的每个五元组迭代对应的参数W和H第二步遍历训练集xˆeuij,,(,xˆuij,,)xuijˆ,e()第三步判断迭代是否收敛。若收敛则算法结束。否则转到第二步。实验结果及分析本节给出使用基于BPR的微博推荐算法在真实微博数据上进行推荐的实验结果。数据集与数据整理实验使用了新浪微博上独立爬取的两个数据集如表所示。数据集的规模是个用户每个用户的最近条微博和这个用户之间的好友关系。数据集的规模是个用户每个用户的最近条微博和这个用户之间的好友关系。每条微博都包含了微博内容和发出的时间。每个用户的条微博时间跨度最长有个月最短只有天。用户的数据集共包含条不重复的微博。个用户之间相互关注的用户对有对单向关注的用户对有对。平均每个用户有个双向关注好友和个单向关注好友。将月日之前发出的微博作为训练集将月日之后发出的微博作为测试集使得训练集中微博个数和测试集中微博个数比例为:。在生成微博对时先删u对于其发出的每一条微博j提取了用户除了只出现一次的微博。其次对于特定用户u好友发出的、时间在微博i之间并且处于同一天的微博j构成了五元组(u,i,j,ti,tj)tjt分别是微博i和微博j发出的时间。最后训练集中有对微博对测试集中其中i和有对微博对。图数据集中用户的转发率FigUsers’retweetproportionindataset用户的数据集共包含条不重复的微博。个用户之间相互关注的用户对有对单向关注的用户对有对。平均每个用户有个双向关注好友和个单向关注好友。训练集的划分和微博对的提取与用户相同。最后训练集中有对微博对测试集中有对微博对。图是数据集中用户的活跃情况图中的转发率指的是用户转发的微博在其收到的所有微博中占的比例。表数据集与数据集的训练集Tabletrainingdataofdatasetanddataset不重复微博个数MF的训练集大小BPR的训练集中大MF与BPR的训练集大小之比:数据集:数据集评估标准与对比算法实验评估标准采用了AUC标准AUC,,(xˆui,xˆuj)E(u)Uu(i,j)E(u)()E(u):,,(i,j)|(u,i)Stest,(u,j)(Stest,Strain),AUC其中越高代表了越准确的AUC是AUC的上限是。排序质量。一个随机的正态分布的本文选用了矩阵分解(matrixfactorization,MF)算法与全局最优算法(mostpopular,MP)作为对比算法。全局最优算法将所有的微博按照全局被转发的次数进行排序。这个算法基于一个原理:用户倾向于更关注最热门的话题。实验方法实验初始时将W矩阵和H矩阵初始化为服从N,分布的随机数。在迭代过程Wu和Hi。之后在测试集上根据学习出的矩阵W先对训练集中每组微博对迭代更新对应的和H进行测试计算测试集的AUC。若AUC与上次AUC的差小于则停止迭代否则继续迭代。,分别为、、、、迭代过程中的学习速率设为。补偿项参数K分别为、、、和。和。矩阵的潜在参数实验结果和讨论首先通过图和图可以看到基于BPR的微博推荐算法要比MF算法和MP算法更好的适用于微博。在用户的数据集上基于BPR的微博推荐算法要比MF算法高出了个百分点。在用户的数据集上基于BPR的微个百分点同时比MP算法高出了博推荐算法要比MF算法高出了个百分点同时比MP算法高出了个百分点。由此可见基于BPR的微博推荐算法比MF算法和MP算法有更好的效果。图数据集中对比算法和本文提出的算法的对比FigComparisonofbaselinesandourproposedalgorithmindataset图数据集中对比算法和本文提出的算法的对比FigComparisonofbaselinesandourproposedmethodindataset其次通过图和图基于BPR的微博推荐算法分别在维度为和时效果最好而当维度继续增大时效果会下降。这表明基于BPR的微博推荐算法在维度过高时会出现过学习的情况影响推荐结果。MF算法在维度较高时会有较好的结果MP算法与维度无关。再次通过图和图可以看到不同的补偿项参数对基于BPR的微博推荐算法结果的影响。在用户数据集补偿项取时AUC的值最高。在用户数据集补偿项取时AUC的值最高。图数据集中补偿项参数对AUC的影响FigTheimpactofregularizationonAUCindataset图数据集中补偿项参数对AUC的影响FigTheimpactofregularizationonAUCindataset最后通过表可以看到当用户数据集使用MF算法时训练集共有个训练样本。而通过使用微博对作为训练样本后基于BPR的微博推荐算法的训练集共有个训练样本MF算法与基于BPR的微博推荐算法训练集大小比例为:。当用户数据集使用MF算法时训练集共有个训练样本。同样基于BPR的微博推荐算法使得训练集增大到个训练样本MF算法与基于BPR的微博推荐算法训练集大小比例为:。由此可见通过利用微博上下文环境这个隐式信息以微博对作为训练集大大增加了训练集的个数从而解决了用户活跃度不高和数据稀疏导致训练样本不足的问题。而且数据集规模越大使用微博对进行训练的效果越好。总结本文研究了微博推荐问题的难点以及与传统推荐问题的不同。同时设计了一种基于BPR的微博推荐算法。相比于MF算法利用微博对作为训练集在目标函数中也加入了时间差的影响。随后在真实数据集上对该算法进行评测并且在不同的维度和不同的补偿项参数下全面比较了对比算法和基于BPR的微博推荐算法。实验结果表明基于BPR的微博推荐算法在不同维度和补偿项参数上都优于对比算法并且能够解决用户活跃程度低、数据稀疏不对称和用户兴趣动态变化等难点。在今后的工作中还将进一步考虑微博中的用户之间关系和微博系统中冷启动现象。参考文献(References)WengJ,limE,JiangJ,etalTwitterRank:FindingTopicsensitiveInfluentialTwitterersCProceedingsofthethirdACMinternationalconferenceonWebsearchanddataminingPagesChaM,HaddadiH,BenevenutoF,etalMeasuringUserInfluenceinTwitter:TheMillionFollowerFallacyCProceedingsoftwentyfourthconferenceonArtificialIntelligence,PagesQazvinianV,RosengrenE,RadevD,etalRumorhasit:IdentifyingMisinformationinMicroblogsCProceedingsoftheConferenceonEmpiricalMethodsinNaturalLanguageProcessingPagesGroveF,SenSTwitAg:AMultiagentFeatureSelectionandRecommendationFrameworkforTwitterJLectureNotesinComputerScience,,Volume,,DOI:RendleS,FreudenthalerC,GantnerZ,etalBPR:BaysianPersonalizedRankingfromImplicitFeedbackCPagesAUAIPressArlington,Virginia,UnitedStatestableofcontentsISBN:HannonJ,McCarthyK,SmythBFindingUsefulUsersonTwitter:TwittomendertheFolloweeRecommenderJLectureNotesinComputerScience,,Volume,,DOI:HannonJ,BennettM,SmythBRecommendingTwitterUserstoFollowUsingContentandCollaborativeFilteringApproachesCProceedingsofthefourthACMconferenceonRecommendersystemsPagesZangerleE,GasslerW,SpechtGUsingTagRecommendationstoHomogenizeFolksonomiesinMicrobloggingEnvironmentsCProceedingsoftheThirdInternationalConferenceonSocialInformatics,PagesPhelanO,McCarthyK,SmythBUsingTwittertoRecommendRealtimetopicalnewsJLectureNotesinComputerScience,,Volume,,DOI:PhelanO,McCarthyK,BennettM,etalTermsofaFeatureContentbasedNewsRecommendationDiscoveryUsingTwitterJLectureNotesinComputerScience,,Volume,,DOI:YangS,LongB,SmoleA,etalCollaborativecompetitivefiltering:learningrecommenderusingcontextforuserchoiceCProceedingsofthethinternationalACMSIGIRconferenceonResearchanddevelopmentinInformationRetrieval,PagesMcLaughlinM,HerlockerJAcollaborativefilteringalgorithmandevaluationmetricthataccuratelymodeltheuserexperienceCProceedingsofthethannualinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrievalPagesCannyJCollaborativefilteringwithprivacyviafactoranalysisCProceedingsofthethAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrievalPagesKorenY,BellR,VolinskyCMatrixfactorizationtechniquesforrecommendersystemsJComputer,Volume,Issue,Aug,pagesBoydD,GolderS,LotanGTweet,Tweet,Retweet:ConversationalAspectsofRetweetinginTwitterCProceedingsoftherdHawaiiInternationalConferenceonSystemSciencesPagesChenJ,NairnR,NelsonL,etalShortandTweet:ExperimentsonRecommendingContentfromInformationStreamsCProceedingsofthethinternationalconferenceonHumanfactorsincomputingsystemsPagesBardleyATheuseoftheareaundertheROCcurveintheevaluationofmachinelearningalgorithmsJPatternRecognitionVolume,Issue,July,PagesRendleS,SchmidtThiemeLPairwiseInteractionTensorFactorizationforPersonalizedTagRecommendationCProceedingsofthethirdACMinternationalconferenceonWebsearchanddataminingPages

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/20

个性化微博推荐算法

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利