一种基于用户反馈的时间感知推荐方法

邢 星 ，贾志淳 ，2，杨玉强

1.渤海大学 信息科学与技术学院，辽宁 锦州 121013

2.美国新墨西哥大学 计算机科学系，美国 87131

1 引言

社交网络中的用户兴趣信息会随着时间发生变化，用户之间的朋友关系也随着时间的变化而变化。社交网络是在不断演化的，用户兴趣也是不断变化的，如何为社交网络中的个人用户提供即时感兴趣的项目推荐成为社交网络推荐方法研究的新要求和新挑战[1-2]。传统的推荐方法只考虑用户是否点击了项目，对项目是否感兴趣，并没有考虑用户点击项目的时间因素[3-4]。因此，在实际的社交网络推荐场景中，如果时间因素对用户兴趣影响较大，那么传统的推荐方法无法为社交网络用户提供高质量的推荐[5]。

上下文背景信息（context information）中除了时间因素，用户的反馈信息也可以用来提高推荐方法的推荐质量[2，6-7]。传统的推荐方法只考虑用户的正反馈信息，即用户─项目的点击数据[8]。另一类反馈信息，如推荐系统推荐给用户的项目中，用户没有点击的项目，这类反馈信息称为负反馈信息。负反馈信息从另一个方面反映了用户的兴趣，也可以用来分析用户兴趣偏好。将负反馈信任融入到基于用户兴趣的推荐方法中，提高社交网络推荐方法的推荐质量[9]。

针对上述问题，本文提出一种基于用户反馈时间感知推荐方法。通过对社交网络的动态性建模，将时间因素引入到社交兴趣网络中。将用户反馈信息建模为正反馈信息和负反馈信息，建立用户兴趣的时间衰变函数刻画用户兴趣变化随时间衰减的影响，综合利用两种反馈信息和用户兴趣衰变函数建立用户兴趣的动态模型。根据用户兴趣的动态模型为社交网络中用户提供时间感知的推荐。

2 社交网络和用户反馈表示

在社交网络推荐方法研究和应用领域，人们只关注挖掘用户与项目之间的二元关系[10]，较少考虑用户与项目所处的上下文背景信息，如时间、社交网络朋友关系、用户反馈等信息[11-14]。但是，在许多应用场景下，仅仅依靠用户与项目之间的二元关系并不能生成有效推荐[15-16]。

为了考虑时间因素对社交网络推荐方法的影响，首先给出动态社交网络的形式化表示。

定义1（动态社交网络）给定目标用户u，动态社交网络可以表示为GS=(V,follow,T,u)，其中，

（1）V是动态社交网络中用户U={u1,u2,…,un}结点的非空有限集合；

（2）follow⊆U×U，是用户─用户的关注关系，代表社交网络的朋友关系代表社交网络中的关注关系（followship）；

（3）T代表社交网络中用户之间建立关注关系的时间集合。

动态社交网络Gs与传统社交网络G的定义不同之处在于动态社交网络考虑了关注关系建立的时间。在此基础上，给定时间t和目标用户u，定义社交网络中朋友（被关注者）集合：

其中，tu,u′是目标用户u关注用户u′的时间。

当推荐系统为用户推荐项目时，记录了用户点击的项目，同时也记录了推荐列表中用户没有点击的项目。一方面，用户点击的项目反映了用户兴趣偏好，可以直接用来计算用户兴趣的相似度。另一方面，用户没有点击的项目也反映了用户的兴趣，也可以用来分析用户兴趣偏好。将这类数据融入到基于用户兴趣的推荐方法中，通过分析反馈信息准确刻画用户兴趣偏好，可以进一步提供推荐方法的推荐质量。

根据用户是否点击推荐项目，将用户反馈信息分为两类：正反馈信息和负反馈信息，定义表示如下：

定义2（正反馈表示）给定目标用户u，正反馈可以表示为图的形式G+=(V,click,T,u)，其中，

（1）V=I∪U代表结点的非空有限集合，I={i1,i2,…,im}代表社交网络中的项目集合，U={u1,u2,…,un}代表用户集合。

（2）click⊆U×I是用户─项目的点击关系，代表用户的正反馈信息。

（3）T代表用户点击项目的时间集合。

给定时间t和G+，目标用户u点击的项目集合可以表示如下形式：

其中，tu,i是目标用户u点击项目i的时间。

定义3（负反馈表示）给定目标用户u，负反馈可以表示为图的形式G-=(V,unclick,T,u)，其中，

（1）V=I∪U代表结点的非空有限集合，I={i1,i2,…,im}代表社交网络中的项目集合，U={u1,u2,…,un}代表用户集合。

（2）unclick⊆U×I指在推荐给用户项目时候，用户没有选择点击的推荐项目，代表用户的负反馈信息。

（3）T代表用项目推荐给用户但是没有被用户点击的时间集合。

与式（2）的定义相似，在给定时间t和G-的情况下，目标用户u没有点击的项目集合定义如下：

其中，tu,i是目标用户u没有选择点击项目i的时间。

式（2）和式（3）分别计算目标用户在给定时间内的正反馈信息和负反馈信息，两者从两个不同方面反映了用户在特定时间的兴趣。结合用户的正反馈和负反馈信息，定义用户的推荐项目集合如下：

其中，I+(u,t)由式（2）计算得到，I-(u,t)由式（3）计算得到。

最后，定义基于时间感知和用户反馈的社交网络项目推荐的目标函数F如下：

其中，i∈Irec(u,t),u∈U 。

目标函数F通过对社交网络中影响目标用户点击推荐项目的正反馈信息，负反馈信息和时间因素进行分析，将基于目标用户u上下文背景信息生成的推荐项目映射到实数范围，根据目标函数的函数值大小来预测目标用户对推荐项目的喜好程度。

3 基于用户反馈时间感知推荐方法

3.1 基于用户反馈的相似度计算

在传统的推荐方法中，用户之间的相似度是分析用户之间点击相同项目的个数和用户分别点击项目的个数计算而得到的[3]，计算公式如下：

其中，I(u)代表用户u点击的项目集合，I(u′)代表用户u′点击的项目集合。

为了将时间因素和用户反馈信任融入到推荐方法中，扩展式（6）的用户相似度计算方法。给定时间t，用户之间的相似度计算公式如下所示：

t′u,i是用户u没有选择点击推荐项目i的时间；同样地，t′u′,i是用户u′没有选择点击推荐项目i的时间，且满足t′u,i≤t，t′u′,i≤t。

weight(tu,i-tu′,i)是时间加权函数，值域为[0，1]；通过对用户u和用户u′点击项目i的不同时间间隔加权，刻画时间因素对推荐方法的影响。

α是调和参数，将用户的正反馈信息和负反馈信息对用户相似度的影响调和在一起，参数α的取值通过实验得到。

在式（7）中，如果将参数设为α=1，那么只有用户的正反馈信息起作用，影响用户的相似度计算。

用户对项目的选择是有时间效应的。一般情况下，用户对最近选择的东西比较感兴趣，而会忽视很早以前选择的东西，不同时间下的用户的项目选择信息对推荐预测的贡献是不一样的。

应用文献[17]中的时间加权方法计算时间因素对用户兴趣的影响。令Δt=tu,i-tu′,i表示用户u和用户u′点击项目i的时间间隔，时间加权函数定义为：

其中，λ是时间衰变参数，控制着用户兴趣衰变的速率。

式（8）定义的时间加权函数在Δt≥0的条件下，是一个单调递减函数，在Δt=0的时候，函数取最大值1，在Δt→+∞的时候，函数取最小值0。

参数λ控制时间加权函数函数值曲线下降的速率，λ的值越大，曲线下降的越快。这符合用户兴趣时间因素加权的要求：时间间隔较近的用户点击行为对项目的推荐作用获得较高的贡献度。同样用式（8）分析用户没有选择推荐项目数据对项目推荐结果带来的影响。

3.2 推荐算法

基于时间感知和用户反馈的推荐算法如下所示，其中，参数α和λ需要通过实验分析确定参数的最优值。

算法1基于时间感知和用户反馈的推荐算法

通过上面的分析，利用社交网络目标用户邻居节点的项目点击信息来预测目标用户未来点击项目的概率，求解式（5）中推荐任务的目标函数F。

4 实验

4.1 数据来源

应用新浪微博所提供的数据访问接口抽取推荐数据，通过记录用户推荐项目列表和用户点击的推荐项目计算用户反馈信息。抽取到数据的时间跨度从2011年10月12日到2011年11月12日，共计744个小时的数据。数据集中共有6 101个用户，2 343个项目，954 015条带时间信息的用户-项目点击日志记录（user-item clicked log），1 203 421条用户没有选择点击推荐项目的日志记录（user-item unclick log），132 747个关注关系。

4.2 实验设置

将数据集划分为训练集和测试集，在训练集上训练基于时间感知和用户反馈的推荐方法中的参数，在测试集上评估提出推荐方法的推荐质量。时间采样窗口设置为1小时，共采样745次。

采用下面两个常用的评价指标来评估基于用户反馈的时间感知推荐方法的推荐质量：

（1）前k个推荐项目的平均准确率AP@k。

（2）前k个推荐项目平均准确率的平均值MAP。

其中，将k分别设置为k=5，k=10，k=15和k=20。

对比实验中的基线方法（Baseline）采用基于项目的推荐方法（item-based recommendation method）。如文献[4]中所示，项目i和项目j之间的相似度sim(i,j)计算如下：

其中，U(i)代表点击项目i的用户集合，U(j)代表点击项目j的用户集合。

4.3 推荐质量与分析

图1给出了参数λ和α的不同设置对前k个推荐项目平均准确率的平均值MAP值。实验结果表明，当α=0.8且λ=0.005时，基于时间感知和用户反馈推荐方法的推荐质量最高，前k个推荐项目平均准确率的平均值MAP为0.243 5。因此，将参数α设定为0.8，进行下面的对比实验。

图1 参数λ和α的不同设置对推荐质量的影响

将参数λ设置为0.5，0.01和0.005，评价不同参数λ设置对基于时间感知和用户反馈的推荐方法带来的影响，将该方法与基线方法（baseline）做比较，实验结果如图2所示。基线方法的前k个推荐项目平均准确率的平均值MAP为0.170 5。当λ=0.005时，基于时间感知和用户反馈的推荐方法的MAP取值最大，为0.243 5。与基线方法相比，基于时间感知和用户反馈的推荐方法在前k个推荐项目平均准确率的平均值MAP上提高了近30%。

图2 不同参数λ对推荐质量的影响

此外，参数λ也影响基于时间感知推荐方法的推荐质量，当λ=0.5时，推荐方法前k个推荐项目平均准确率的平均值为0.167 6，这个值比基线方法的0.170 5要低。因此，合适的参数选取对基于用户反馈的时间感知推荐方法而言至关重要，直接关系到推荐方法的推荐质量。

5 结束语

本文给出了动态社交网络项目推荐问题的定义，将用户反馈形式化表示为正反馈信息和负反馈信息。通过扩展用户相似度计算方法，将时间因素，用户反馈信息等影响推荐质量的上下文信息融入到推荐方法中。应用时间加权函数刻画时间因素对用户兴趣的影响，使时间间隔较近的用户点击行为对项目的推荐作用获得较高的贡献度，充分体现用户兴趣的时间效应特性。对社交网络中邻居节点点击的项目来预测目标用户未来点击的项目，构建基于用户反馈的时间感知推荐方法。数据来源于新浪微博中抽取到的实际数据，实验表明通过选择合适的参数，基于用户反馈的时间感知推荐方法可以显著提高推荐质量。

[1]Biancalana C，Gasparetti F，Micarelli A，et al.An approach to social recommendation for context-aware mobile services[J].ACM Trans on Intell Syst Technol，2013，4（1）：1-31.

[2]Yang Xiwang，Steck H，Guo Yang，et al.On top-krecommendation using social networks[C]//Proceedings of the Sixth ACM Conference on Recommender Systems，2012：67-74.

[3]Adomavicius G，Tuzhilin A.Toward the next generation of recommender systems：a survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering，2005，17（6）：734-749.

[4]Deshpande M，Karypis G.Item-based top-n recommendation algorithms[J].ACM Transactions on Information Systems，2004，22（1）：143-177.

[5]王立才，孟祥武，张玉洁.上下文感知推荐系统[J].软件学报，2012，23（1）：1-20.

[6]Yang Shuanghong，Long Bo，Smola A J，et al.Collaborative competitive filtering：learning recommender using context of user choice[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval，2011：295-304.

[7]Bakshy E，Hofman J M，Mason W A，et al.Everyone’s an influencer：quantifying influence on twitter[C]//Proceedings of the Fourth ACM International Conference on Web Search and Data Mining，2011：65-74.

[8]Sarwar B，Karypis G，Konstan J，et al.Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th International Conference on World Wide Web，2001：285-295.

[9]Moghaddam S，Jamali M，Ester M，et al.FeedbackTrust：using feedback effects in trust-based recommendation systems[C]//Proceedings of the Third ACM Conference on Recommender Systems，2009：269-272.

[10]吴湖，王永吉，王哲，等.两阶段联合聚类协同过滤算法[J].软件学报，2010（5）：1042-1054.

[11]Kuter U，Golbeck J.Using probabilistic confidence models for trust inference in web-based social networks[J].ACM Trans on Internet Technol，2010，10（2）：1-23.

[12]Hannon J，Bennett M，Smyth B.Recommending twitter users to follow using content and collaborative filtering approaches[C]//Proceedings of the Fourth ACM Conference on Recommender Systems，2010：199-206.

[13]Guy I，Zwerdling N，Ronen I，et al.Social media recommendation based on people and tags[C]//Proceedings of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval，2010：194-201.

[14]Ma Hao，King I，Lyu M R.Learning to recommend with social trust ensemble[C]//Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval，2009：203-210.

[15]Jahrer M，Toscher A，Legenstein R.Combining predictions for accurate recommender systems[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2010：693-702.

[16]Jamali M，Ester M.A matrix factorization technique with trust propagation for recommendation in social networks[C]//Proceedings of the Fourth ACM Conference on Recommender Systems，2010：135-142.

[17]Ding Yi，Li Xue.Time weight collaborative filtering[C]//Proceedings of the 14th ACM International Conference on Information and Knowledge Management，2005：485-492.