一种结合遗忘机制与加权二部图的推荐算法

刘晓光，谢晓尧

(1.贵州大学 计算机科学与技术学院，贵州 贵阳550000；2.贵州师范大学 信息与计算科学重点实验室，贵州 贵阳 550000)



一种结合遗忘机制与加权二部图的推荐算法

刘晓光1，2，谢晓尧2

(1.贵州大学 计算机科学与技术学院，贵州 贵阳550000；2.贵州师范大学 信息与计算科学重点实验室，贵州 贵阳 550000)

为了解决因用户兴趣漂移而导致推荐质量下降的问题，本文引入了用户对产品的遗忘因子。通过分析用户的浏览记录和打分情况，建立用户的动态兴趣模型；并计算用户对产品的遗忘因子，利用遗忘因子作为加权二部图的权值，通过二部图的资源分配方法产生用户的推荐列表。在数据集MovieLens上的实验表明：该算法能有效地处理用户兴趣漂移的问题，提高推荐列表的推荐质量。

兴趣漂移；遗忘机制；加权二部图；资源分配；推荐算法

0 引言

随着现代电子商务和网络技术的快速发展，互联网的规模不断扩大，信息不断膨胀，世界上的信息处于大爆炸的状态，用户所面对的信息数量大、质量差、信息价值低，给用户带来了信息超载的问题。为了解决信息超载问题，推荐系统应运而生[1]。

随着Web2.0技术趋于成熟，推荐系统在网络上的应用也迅速发展，如TaoBao、Amazon、Youtube等网站，它们都拥有自己的推荐系统。在实际的应用中，用户的数量庞大，产品资源的数量巨大，用户很少能一次就找到自己想要的信息。设计一个准确高效的推荐系统不仅可以发现用户潜在的兴趣对象，还可以针对不同用户提供个性化的服务[2]，以帮助用户更好地获取想要的信息。

2012年，文献[3]提出了加权网络推断算法(WNBI)，即加权二部图推荐算法，该推荐算法解决了高评分值的产品不能优先推荐的问题，提高了推荐质量。但是在现实生活中，随着新的产品(选择)的出现，产品的感知和受欢迎程度不断发生变化，同样，用户的倾向也是不断变化的，这种用户偏好随着时间变化的情况，称为用户“兴趣漂移”问题[4]。为了降低“兴趣漂移”问题对推荐质量的影响，研究人员做了大量的工作，如：文献[5]提出的时间加权不确定近邻协同过滤算法，文献[6]提出的融合时间综合影响的轮盘赌游走个性化推荐算法等。本文通过遗忘机制引入了遗忘因子，利用遗忘因子作为加权二部图的权值，提出了一种改进的加权网络推断算法(FWNBI)，即结合遗忘机制与加权二部图的推荐算法。

1 遗忘机制

对于用户的“兴趣漂移”问题，目前有各种不同的遗忘机制来处理。2008年，文献[7]提出了一种遗忘机制，引入了一种指数的遗忘函数F(t)来量化用户兴趣的衰减程度，函数定义为：

(1)

其中：遗忘函数F(t)为当前时间用户的兴趣衰减到的程度，即当前时间用户兴趣的保留程度；t为用户产生推荐列表时的当前时间；est为用户选择某产品的时间；hl为用户遗忘的速率，hl越大表示遗忘的速度越慢，hl越小表示遗忘的速度越快[7]。

1885年，德国心理学家艾宾浩斯研究发现：人们在学习之后立即开始遗忘，而且遗忘的速度并不是均匀的，最初遗忘速度很快，以后逐渐缓慢[8]。遗忘速度曲线如图1所示。

图1 艾宾浩斯遗忘曲线

根据艾宾浩斯理论，将遗忘速率hl定义为：用户初次选择产品的时间距离系统为用户产生推荐列表时的时间间隔。对于某一用户，假设初次选择产品的时间为t1，选择某一产品P的时间为t2，系统为该用户产生推荐列表的时间为t，那么该用户对于产品P的兴趣保留程度为F(t)=e-ln 2*(t-t2)/(t-t1);随着t的推移，hl=t-t1的值越大，即用户对于产品P的遗忘速度越慢。

2 加权二部图推荐算法

近年来复杂网络的研究方兴未艾，越来越多关于网络的研究成果被发掘并应用。二部图是一种特殊的网络，它仅包含两类节点：一类节点是活动的用户节点，例如需要获得推荐的用户等；另一类节点是项目节点，例如要为用户推荐的产品等[3]，它仅允许不同类的节点间相连。

2007年，文献[9]提出了二部图推荐算法，该推荐算法把用户和产品分别抽象为不同的节点，作为二部图的节点，把用户与产品之间的选择关系抽象为两类节点之间的边(如果用户i选择了产品j，那么用户i节点与产品j节点之间连接一条边aji=1，否则aji=0，其中i=1,2,…，m;j=1,2,…，n)。该算法仅考虑用户节点与产品节点之间的连接关系，而不考虑用户和产品的内容特征，所有算法利用的信息都藏在用户节点和产品节点及它们之间的边所构成的二部图中。

该算法假设所有的产品节点上都具有某种可再分配的资源，该资源可以通过用户节点与产品节点之间的边转移到其他的产品节点上，拥有资源的产品会把更多的资源转移给其更加青睐的产品上[10]。通过这种资源分配的方法，把用户没有选择过的产品并且拥有更多资源的产品按照拥有资源的数量从大到小排序，将排名靠前的产品推荐给该用户，形成推荐列表。

但是二部图推荐算法中的二部图是无权值的，产品的资源平均分配给选择过该产品的用户，用户所得到的资源再平均分配给该用户所选择过的产品。在这个资源分配过程中所有产品的重要性相同，对用户的推荐贡献是相同的；但在实际应用中，用户喜欢的产品对用户的推荐贡献要高于用户不太喜欢的产品对于用户的推荐贡献。显然，平均分配资源的方式并不合理。文献[3]提出了加权二部图推荐算法，该推荐算法考虑用户与产品之间的边的权重，根据边的权重来进行资源的分配，如产品j将资源按边aji的权值与该产品边权之和的比分配给用户i，同样，用户i再将所获得的资源按边aki的权值与该用户边权之和的比例分配给产品。

3 FWNBI推荐算法

无论是二部图推荐算法还是加权二部图推荐算法，它们只是单纯的考虑用户喜欢与不喜欢或用户的喜欢程度，并没有考虑用户“兴趣漂移”的问题。二部图推荐算法把用户选择过的产品看做是同等重要，并没有区分用户对产品的喜欢程度(打分值wij)；而加权二部图推荐算法虽然区分了用户对产品的喜欢程度(打分值wij)，不同喜欢程度的产品的重要性不同，但并没有考虑用户的“兴趣漂移”问题，这在一定程度上降低了推荐算法的推荐质量。

基于遗忘机制和加权二部图的推荐算法(FWNBI)，在给用户推荐时考虑了时间对用户兴趣的影响，通过遗忘机制引入了遗忘因子fij，用来量化当前时间t时用户j对于产品i的兴趣的保留程度，见式(2)。

(2)

其中：estij表示用户j选择产品i的时间；hlj=t-tj,t表示系统为用户j产生推荐列表的当前时间，tj表示用户j初次选择产品的时间。

利用遗忘因子fij与当时用户j对产品的打分值wij的乘积，kij来估计当前用户j对于该产品i的喜欢程度，见式(3)。

kij=wijfij。

(3)

图2 改进推荐算法资源转移过程

将kij作为二部图边的权值，资源分配的过程如图2所示。在图2a中，3个产品的起始资源分别为x、y、z，边的权值为kij。首先，资源从产品节点转移到用户节点，产品节点将拥有的资源按照用户-产品边权与该产品边权之和的权重比，分配给每个与该产品节点相连的用户节点上，分配结果见图2b；其次，资源从用户节点返回到产品节点上，用户节点将所分得资源按照用户-产品边权与该用户边权之和的权重比，分配给与其相连的产品节点上，结果见图2c。

由资源分配过程可知，任意产品j分配给产品i的资源权重Wij计算公式为：

(4)

(5)

其中：k(xj)表示与产品xj连接的所有用户边权之和；k(yl)表示与用户yl连接的所有产品边权之和；amn表示用户n是否选择过产品m；kmn表示用户n对产品m的喜欢程度的估计值。

通过式(4)和式(5)可以得到系统的资源分配矩阵W。对于给定的一个目标用户，将他选择过的且打分值大于等于3分的产品上的初始资源设为1，没有选择过或打分值小于3分的产品上的初始资源设为 0。这样得到一个n维的 0/1 矢量，代表针对该用户的初始资源分配构型，显然，这个初始构型表达了个性化信息，对于不同用户是不一样的。记这个矢量为f，通过上述过程得到的最终的资源分配矢量可以表示为：

f′=Wf，

(6)

其中：W为系统的资源分配矩阵；f为目标用户的初始资源分配构型；f′为系统给目标用户推荐的产品的矢量原始列表。

把矢量f′中用户已经选择过的产品所对应的值置为0，然后将矢量f′中的元素按值的大小进行排序，值越大就说明该用户越喜欢其所对应的产品。排序靠前的值所对应的产品，可以推荐给目标用户。

假设(U,P,W,T)表示用户的行为，其中U表示用户集合，P表示用户U选择过的产品集合，W表示用户U给产品集合P的打分集合(1～5分)，T表示用户U选择产品P并给产品打分时的时间集合。用户ui在时间tij时选择产品pj并且给该产品的打分值为wij的一次行为可以表示为(ui，pj，wij，tij)。

FWNBI算法描述：

第1步：估算现在用户对已选产品的打分情况。

输入：用户的浏览记录和打分情况T；

输出：输出格式为(ui，pj，kij，0)的数组initial[ui][pj]，用户ui选择过的产品的边的权值之和记为Ku[ui]，选择过产品pj的用户的边的权值之和记为Km[pj]。

Foreach t in T

生成格式为(ui，pj，wij，tij)的数据集合A；

Endfor

Foreach a in A

根据式(2)生成格式为(ui，pj，wij，fij)的数据b；

根据式(3)将数据b转换为格式为(ui，pj，kij，0)的数组initial[ui][pj]；

计算与用户ui相连的边的权值之和，记为Ku(ui)；

计算与产品pj相连的边的权值之和，记为Km(pj)；

Endfor

第2步：计算资源转移矩阵。

输入：格式为(ui，pj，kij，0)的数据集H，集合Ku，集合Km；

输出：资源转移矩阵W。

Foreach h in H

根据式(4)和式(5)计算得到资源转移矩阵W；

Endfor

第3步：为某个用户计算得到推荐列表。

输入：用户的初始资源分配构型f，资源转移矩阵W；

输出：某个用户的推荐列表R。

Begin

根据式(6)得到系统给用户推荐的产品的推荐值矢量f1；

得到初始推荐列表R=f1-f，取值较大的所对应的产品形成最终推荐列表。

End

4 算法评价

4.1 数据集

采用开源的MovieLens数据集，数据集的规模如表1所示。

表1 数据集规模

从数据集中随机抽取70%的数据并对该数据集按时间的先后进行划分，其中，用户较早选择的80%的数据作为训练集，较晚选择的20%的数据作为测试集。重复上述过程10次，取10次评价结果的平均值作为该推荐算法的最终评价结果。

4.2 评价指标

在该推荐算法中，用户具有明确的二分喜好(用户对电影的打分值大于等于3表示喜欢，否则表示不喜欢)，本文采用特别适合于具有二分喜好的评价指标：分类准确度[10]。目前，最常用的分类准确度指标有准确率、召回率、综合评价指标(F1指标)和曲线下面积(AUC)。该推荐算法对于推荐排序有一定的要求，本文还采用排序准确度评价指标，文献[9]提出了用平均排序分度量推荐算法的排序准确度。本文采用准确率、召回率、F1指标和平均排序分对该推荐算法进行评价。

4.2.1 基于准确率、召回率的评价

准确率和召回率是推荐系统中常用的两个评价指标。准确率也叫查准率，表示用户喜欢的产品在系统推荐列表中所占的比例；召回率也叫查全率，表示一个用户喜欢的商品被推荐的概率[11]。

表2 待预测的产品4种可能的状态

对于用户未选择和打分的产品，往往有4种可能的状态，如表2所示，其中K表示系统中产品的个数。

由表2可知系统整体的推荐准确率为：

(7)

系统整体的召回率为：

(8)

其中：U表示测试用户的集合；M表示测试用户的数量。

图3为基于加权二部图的推荐算法(WNBI)、基于遗忘机制和加权二部图的推荐算法(FWNBI)在推荐长度分别为5个、10个、20个、30个、…、100个下的准确率和召回率折线图。

图3 算法的准确率和召回率折线

由图3可知：FWNBI和WNBI在准确率和召回率上的差别不是很大，随着推荐长度的增大，两者的准确率和召回率曲线几乎重合，在推荐长度为10～50个时，FWNBI的准确率优于WNBI；并且在推荐长度为30个时，FWNBI的准确率达到最大；但在推荐长度大于70个时，两者的准确率和召回率几乎相等，FWNBI相对于WNBI并无明显的优势。

4.2.2 基于F1指标的评价

由于受到推荐列表长度、评分稀疏性以及喜好阀值等多方面因素的影响，很多学者不提倡利用准确率和召回率来评价推荐系统，特别是只单独考虑一种指标的时候误差极大[11]。

一种常用的方法是同时考虑准确率和召回率从而比较全面地评价算法的优劣，文献[12-13]提出了F1指标，定义为：

(9)

图4 F1指标曲线

其中：R(L)为系统整体的召回率；P(L)为系统整体的准确率。

图4为FWNBI和WNBI分别在推荐长度分别为5个、10个、20个、30个、…、100个下的F1指标的折线图。由图4可知：在推荐长度为20～60个时，FWNBI推荐算法明显优于WNBI推荐算法，并且在推荐长度为30个时达到最优。随着推荐长度的增加，FWNBI推荐算法的优势逐渐变小。

4.2.3 基于平均排序分的评价

无论是FBWN推荐算法还是WNBI推荐算法，他们对于推荐的排序都有一定的要求，如果仅仅用分类准确度来评价推荐算法，显然是不太全面的。假设现在有两种推荐算法A和B，它们给某一用户推荐的产品列表a和b中均有一个产品c是该用户所喜欢的，但是c在a列表中排在第一个，而在b列表中排在最后一个；根据式(8)可知：它们的推荐准确率相同，但给用户的体验上显然是A要优于B。文献[9]提出了用平均排序来度量推荐系统的排序准确度。对于某一用户u来说，商品α的排序分定义如下：

图5 平均排序分RS曲线

(10)

其中：Lu表示用户u未选择过的商品数目；luα为待预测商品α在用户u的推荐列表中的排名。将所有用户的排序分求平均即得到系统的排序分RS。排序分值越小，说明系统越趋向于把用户喜欢的商品排在前面；反之，则说明系统把用户喜欢的商品排在了后面[11-16]。图5为FWNBI和WNBI分别在推荐长度为5个、10个、20个、30个、40个、50个的情况下的平均排序分。由图5可知：FWNBI推荐算法更趋向于将用户喜欢的产品排在推荐列表的前面。较WNBI有更好的推荐质量。

5 结束语

本文针对用户“兴趣漂移”问题，提出了一种改进的加权二部图推荐算法：基于遗忘机制与加权二部图的推荐算法FWNBI。实验结果表明：F1指标在推荐长度为30个时，推荐质量达到最优，明显优于WNBI推荐算法;推荐长度在10～60个时，FWNBI的推荐质量要优于WNBI，并且FWNBI推荐算法更趋向于将用户喜欢的产品排在推荐列表的前面。

虽然FWNBI推荐算法的推荐质量要优于WNBI推荐算法，但FWNBI推荐算法的计算复杂度要大于WNBI推荐算法，当产品的数量达到一定的程度，计算复杂度将制约着该推荐算法的效率。

[1] 许海玲,吴潇,李晓东,等.互联网推荐系统比较研究[J].软件学报,2009,20(2):350-362.

[2] 陈敏.个性化推荐系统研究[D].南京:南京邮电大学,2012.

[3] 张新猛,蒋盛益.基于加权二部图的个性化推荐算法[J].计算机应用,2012,32(3):654-657.

[4] Koren Y.Collaborative Filtering with Temporal Dynamics[J].Communications of the ACM,2010,53(4):89-97.

[5] 郑志高,刘京.时间加权不确定近邻协同过滤算法[J].计算机科学,2014,41(8):7-12.

[6] 赵婷,肖如良.融合时间综合影响的轮盘赌游走个性化推荐算法[J].计算机应用,2014,34(4):1114-1117,1129.

[7] Cheng Y,Qiu G,Bu J,et al.Model Bloggers′ Interests Based on Forgetting Mechanism[C]//Proceedings of the 17th international Conference on World Wide Web.ACM,2008:1129-1130.

[8] 于洪,李转运.基于遗忘曲线的协同过滤推荐算法[J].南京大学学报,2010,46(5):520-527.

[9] Zhou T,Ren J,Matúš M,et al.Bipartite Network Projection and Personal Recommendation[J].Physical Review E,2007,76(4):6116-6123.

[10] 刘建国,周涛,汪秉宏.个性化推荐系统的研究进展[J].自然科学进展,2009,19(1):1-15.

[11] 朱郁筱,吕琳媛.推荐系统评价指标综述[J].电子科技大学学报,2012,42(2):163-175.

[12] Van R C J.Information Retrieval[M].MA,USA:Butterworth-Heinemann Newton,1979.

[13] Pazzani M J,Billsus D.Learning and Revising User Profiles:the Identification of Interesting Web Sites[J].Machine Learning,1997,27(3):313-331.

[14] 项亮.推荐系统实践[M].北京:人民邮电出版社,2012.

[15] 黄威,尚有林,王琪凤.二部图匹配的一个判别条件[J].河南科技大学学报:自然科学版,2013,34(4):85-87.

[16] Soboroff I,Nichloas C.Combining Content and Collaboration in Text Filtering[C]//Proceedings of the IJCAI’99 Workshop on Machine Learning for Information Filtering.1999:86-91.

贵州省科学技术基金项目(200917);贵州省教育厅重点基金项目(20090034);贵阳市科技局重点基金项目(2010183)

刘晓光(1990-),男,河南许昌人,硕士生;谢晓尧(1952-),男,贵州贵阳人,教授,博士,博士生导师,主要研究方向为网络信息安全、工程计算应用.

2014-07-03

1672-6871(2015)03-0048-06

TP3

A