综合项目权值分配与时间相关的协同过滤模型*

2014-09-13朱彦松窦桂琴

计算机工程与科学 2014年11期

关键词：冷门相似性协同

朱彦松,窦桂琴

(中原工学院计算机学院,河南郑州 450007)

综合项目权值分配与时间相关的协同过滤模型*

朱彦松,窦桂琴

(中原工学院计算机学院,河南郑州 450007)

根据长尾理论,被反馈次数少的项目所包含的反馈信息并不少于被反馈次数较高的,传统的协同过滤算法中缺乏考虑冷门项目在最终的项目推荐过程中的影响力,对此,提出了一种改进的协同过滤推荐模型。通过对冷门项目的分析筛选,在用户相似性计算时提高冷门项目所占的比重，以体现用户的个性和兴趣。此外,考虑到时间效应的影响,在兴趣预测过程中引入时间因子。实验结果表明,提出的算法能提高寻找最近邻居的准确性,从而改善协同过滤的推荐质量。

反馈次数；协同过滤；个性化推荐；时间因子

1 引言

根据用户对信息的不同需求,个性化推荐系统可通过数据筛选和分析得到用户感兴趣的信息内容,它往往能从海量信息中提取出用户最感兴趣、最有用的结果,因此,个性化推荐系统被认为能解决信息超载问题。目前所公认的推荐算法主要包括：协同过滤推荐算法、基于内容的推荐算法、谱分析方法、主元素分析方法以及组合推荐算法等[1]。

协同过滤(Collaborative Filtering)是一种在推荐系统中广泛采用的推荐方法,通过计算用户之间的相似度寻求目标用户的最邻近邻居集合,综合这些用户对某一信息的评价后形成目标用户的推荐集。针对不同的应用需求,专家学者对基本的协同过滤算法从不同的侧重方面进行了改进。

文献[2]考虑到由于对未知目标相关联的近邻对象的分析不够全面可能影响推荐质量,基于动态规划思想提出了一种对推荐子群进行概率分析的方法。文献[3]在综合显性兴趣度、隐性兴趣度和预测兴趣度的基础上提出了一种基于综合兴趣的协同过滤方法。文献[4]设计了一个基于朴素贝叶斯方法的协同过滤推荐算法,能根据应用需求的不同自适应动态调整,而无需像其他算法(例如k-NN)那样需要事先手动设置参数。文献[5]提出一种有效的针对稀疏评分的最近邻选择方法,先通过计算用户间的近邻倾向性后得到初始近邻集合,再在该集合的基础上进行目标用户与其他用户相似性比较,然后不断进行修正后得到最近邻集合。文献[6]引入二分网络来描述个性化推荐系统,使用灰色关联度来度量用户相似性和项目相似性,再通过加权求和对项目进行预测打分,排序后得到推荐项目列表。

但是，现有的算法在计算用户的相似性时往往基于用户共同评价过的项目来计算,而对于项目之间的关系分析得不够,对于评分项目的流行度以及在求解相似度时所占的权重考虑得不够细致。另外,在推荐过程中往往忽视了用户评价的时效性特征。这些因素都可能对推荐质量造成影响。

2 基于用户的协同过滤推荐算法

对于协同过滤推荐模型来说,应用比较多的方法是基于用户的算法,通过计算活跃用户与其他用户的相似度,选出近邻子集；再使用邻居评分进行活跃用户评分预测；最后对预测结果进行排序形成Top-N推荐。具体步骤如下：

(1)首先定义一个用户评分矩阵Rm×n,其中m表示用户数,n表示评测项目个数,Rij为第i个用户对第j个项目的评分。

(2)根据评分矩阵计算用户之间的相似性。求解用户相似性的主要方法有余弦相似性、修正的余弦相似性和Pearson相关系数等。

①余弦相似性。相似性度量采用向量间的余弦夹角来计算求得。

其中的项目i、j为两个m维的用户向量。

②修正的余弦相似性。通过减去用户评分平均值修正了不同用户的评分尺度之间的差异性。

③皮尔森相关系数(Pearson Correlation Coefficient)。在求解相似性之前先筛选出共同评分的用户,以提高相似性度量的精确性。

(4)得到最近邻集合之后,通过以下公式来预测评估用户对商品i的评分:

3 综合项目权值分配与时间相关的协同过滤模型

在个性化推荐系统中,如果两个用户对某一项目的评分相近,且从项目分类的角度来说,此项目上参与评分的用户数量占总体评分人数比例较大,那么我们可认定该评分项为热门项目；与之相反则为冷门项目。从现实生活中来看,多数人对某一问题持相同观点,说明该评价对象就很难反馈用户间的理解差异；反之,如果两个用户评分相近,而其参与评分用户数量相比总参与评分人数较少,则更能从中找到代表两用户独特的偏好信息,更能真正体现两用户间的相似性。显然,在计算相似性时,将所有项目的被反馈信息不加区分地设置为相同的权重并不合理,易导致马太效应。即,在推荐系统中,大部分无特定兴趣的用户会对热门或流行度高的项目评价并反馈,这些项目在推荐系统中会更加热门；而冷门或流行度低的项目因不易被用户发掘,反馈程度差而变得愈加不受关注。

大多数算法选择两用户共同评分的所有项目进行用户之间的相似度的计算,且在用户共同评分的项目中被反馈程度高的项目和被反馈程度低的项目在相似度计算时所占的比重一样。而实际上,冷门项目相比热门项目,其反馈信息更能凸显用户的真实兴趣度。本文对传统的协同过滤算法进行如下改进：首先,通过对冷门项目的分析筛选,在用户相似性计算时提高冷门项目所占的比重以体现用户的个性和兴趣；其次,考虑到时间效应的影响,在兴趣预测过程中引入时间因子。

3.1 改进的算法

(1)根据m个用户对n个项目的评价,构造用户评价矩阵R：

(1)

进而,根据对项目是否进行评价,可以得到反馈信息矩阵,表示为：

(2)

矩阵Q为0-1矩阵,矩阵中qij取值为0或者为1,当用户ui对项目pj做出反馈,则qij=1；反之,qij=0。

(2)D=QTQ,D为一个n×n的对称矩阵,对角线上元素djj的值即为第j个评价项目被评价的次数,记为d[j]。

(3)对所有项目的评价次数进行规范化,有：norm(d[j])=(d[j]-dmin)/(dmax-dmin), 其中dmax、dmin分别为评价次数的最大值、最小值。进一步,从评价项目被评价次数角度得到该评价项目的权值,有：

(3)

(4)

(5)在计算用户相似性过程中，本文根据对项目流行度的分析,引入项目相关性的权重。推荐系统中项目相关性的计算不采用Pearson相关系数法,而是采用更客观的基于项目特征属性的方法。改进后的用户相似性计算公式如下：

(5)

得到计算给果后,按照相似性值从大到小排序,前N个用户构成邻居用户集合。

(6)时间因子。用户的评价具有时效性特征,早期评价对于预测值的影响相对要小。目前,多数推荐系统主要依据用户的兴趣进行推荐,但系统中早期的评价信息可能会过期失效,导致推荐成功率的下降。为此,我们充分考虑到时效带来的影响,引入时间加权函数C(t)=e-a(t-t0)(t为时间变量)到兴趣预测过程中,网络信息老化继承了信息老化的经典负指数模型[7]:

(6)

其中,t0表示评价发布的时间,t表示当前的时间,a代表的是信息老化率系数,C(t)表示信息在t时刻的影响力因子。

(7)最后,在预测评分中加入时间因子,目标用户uT对未评分项目iT的加权预测评分TP(uT,pT)进行改进,如公式(7)所示：

(7)

3.2 改进算法的实现

输入：包括目标用户uT,最近邻用户数T,评分矩阵R以及待预测项目集IT。

输出：产生目标用户uT的M个推荐项目。

步骤1构造用户评价矩阵R得到反馈信息矩阵Q;

步骤2求解D=QTQ,定义一个一维数组d[j],存放对称矩阵D对角线元素djj的值；

步骤3根据公式(3)求得各评价项目的权值wj；

步骤4对用户评价矩阵进行归一化后的矩阵P,计算各用户评价向量之间的差异系数φij；

步骤5求解代入差异系数后的改进的用户相似性;

步骤6按照相似性值从大到小排序,选取前N个用户构成邻居用户集合；

步骤7根据加入了时间因子的加权预测评分函数,对目标用户uT的未评分项目iT进行评分预测。

3.3 算法分析

本文提出的改进算法通过在计算用户相似性时考虑了流行度不同项目权重的区别,尽可能将用户对冷门项目评价的个性化特质凸显出来,以求推导出的邻居用户集更准确。此外,在预测评分过程中,引入时间因子函数,对项目评价从时效上进行了区分,这对于最终推荐精度的提高起到很重要的作用。

此外,从时间复杂度上来看,算法执行的时间开销主要在于公式(4)、公式(5)和公式(7)中对于用户相似度的计算,若用户属性中有m个数值型属性和评价项目n个名称型属性,本文中算法时间复杂度保持在O(n2)内,与文献[2，3]提出的推荐算法的时间复杂度相同，不会带来太大的开销。

4 实验结果与分析

为了对改进算法的性能进行验证,本文以MovieLens网站提供的数据样本进行实验,根据评价推荐质量的平均绝对误差标准,从准确率和覆盖率等方面，与传统Top-N推荐算法(tradition-CF)[8]和适应用户兴趣变化的协同过滤算法(interest-CF)[9]进行了对比。实验中选取的样本集包含了943名用户、1 682部电影以及100 000 个评分数据。用户对评价指标分为五个等级，评分取值为从1到5的整数，评价喜好程度与取值大小成正比。在所有实验中,推荐数目N的取值为20,邻居数目则在5～80变动。

此外，本文提出的算法与tradition-CF在推荐准确率方面进行了比较,结果如图1所示。可以看出，当最近邻居节点数为30时,本文算法的准确率达到最高,为17.76%,另外两个算法的准确率分别为17.58%和17.67%。此后,随着邻居节点数量的增加,准确率呈逐步下降趋势,本文的算法与其他两种算法相比较下降得更为平稳。

图2为本文提出的算法与tradition-CF算法以及interest-CF在推荐覆盖率上的比较。对比随着最近邻节点数取值的变化，本文算法的覆盖率稍高,且随着最近邻居节点数的增加呈线性下降的趋势,当邻居节点数量为50～80时,覆盖率基本保持在一个比较窄的区间内变化。

Figure 1 Comparison of the precision rate with different numbers of neighbour nodes图1 最近邻居节点数不同时的准确率比较

Figure 2 Comparison of the coverage rate with different numbers of neighbour nodes图2 最近邻居节点数不同时的覆盖率比较

5 结束语

在传统的协同过滤算法中,冷门项目在项目推荐过程中的影响不易引起重视,但实际上冷门项目上的评分更能突出用户真正兴趣。本文提出了一种综合项目权值分配与时间相关的协同过滤推荐模型,在用户相似性计算时提高冷门项目所占的比重以体现用户的个性化选择；另外，在兴趣预测过程中引入时间因子，以反映项目评分随时间变化而衰减,以提高寻找最近邻居时的准确性，并改善协同过滤的推荐质量。

[1] Wang Guo-xia, Liu He-ping. Survey of personalized recommendation system[J]. Computer Engineering and Applications,2012,48(7):66-76. (in Chinese)

[2] Huang Chuang-guang,Yin Jian,Wang Jing.Uncertain neighbors’ collaborative filtering recommendation algorithm[J]. Chinese Journal of Computers, 2010, 33(8):1369-1373.(in Chinese)

[3] Inoue T,Abe S. Fuzzy support vector machines for pattern classification[C]∥Proc of International Joint Conference on Neural Networks(IJCNN’01), 2001:1449-1454.

[4] Wang Ke-bin, Tan Ying. A new collaborative filtering recommendation approach based on naive Bayesian method[C]∥Proc of the 2nd International Conference on Swarm Intelligence(ICSI’2011), 2011:218-227.

[5] Leng Ya-Jun, Liang Chang-yong, Ding Yong, et al. Method of neighborhood formation in collaborative filtering[J]. Pattern Recognition and Artificial Intelligence, 2013,26(10):968-974.(in Chinese)

[6] Li Xia, Li Shou-wei. Research on collaborative filtering algorithm of bipartite network oriented to personal recommendation system[J]. Application Research of Computers, 2013,30(7):1946-1949.(in Chinese)

[7] Blanco-Fernandez Y, Lopez-Nores M, Pazos-Arias J J, et al. An improvement for semantics-based recommender systems grounded on attaching temporal information to ontologies and user profiles[J]. Engineering Applications of Artificial Intelligence, 2011, 24(8):1385-1397.

[8] Hyung Jun Ahn.Utilizing popularity characteristics for product recommendation[J]. International Journal of Electronic Commerce,2006,11(2):59-80.

[9] Xing Chun-xiao,Gao Feng-rong,Zhan Si-nan. A collaborative filtering recommendation algorithm incorporated with user interest change[J]. Journal of Computer Research and Development, 2007, 44(2):296-301.(in Chinese)

附中文参考文献：

[1] 王国霞,刘贺平. 个性化推荐系统综述[J]. 计算机工程与应用,2012,48(7):66-76.

[2] 黄创光,印鉴,汪静. 不确定近邻的协同过滤推荐算法[J]. 计算机学报, 2010, 33(8):1369-1373.

[5] 冷亚军,梁昌勇,丁勇, 等. 协同过滤中一种有效的最近邻选择方法[J]. 模式识别与人工智能,2013,26(10):968-974.

[6] 李霞,李守伟. 面向个性化推荐系统的二分网络协同过滤算法研究[J].计算机应用研究, 2013, 30(7):1946-1949.

[9] 刑春晓, 高风荣, 战思南. 适应用户兴趣变化的协同过滤推荐算法[J]. 计算机研究与发展, 2007, 44(2):296-301.

ZHUYan-song,born in 1979,MS,lecturer,his research interests include software engineering, and computer simulation.

窦桂琴(1979),女,山西洪洞人，硕士，讲师，研究方向为软件工程和计算机仿真。E-mail:dou_guiqin@163.com

DOUGui-qin,born in 1979,MS,lecturer,her research interests include software engineering, and computer simulation.

Acollaborativefilteringrecommendationalgorithmcombiningitemsweightallocationandtimedependence

ZHU Yan-song,DOU Gui-qin

(College of Computer,Zhongyuan University of Technology,Zhengzhou 450007,China)

According to the long tail theory,the items with fewer feedbacks do not necessarily contain less information than those with more feedbacks.In the traditional collaborative filtering algorithms,the influences from unpopular items are usually ignored in the process of the eventual recommendation.To address this problem,an improved collaborative filtering recommendation model is proposed.By evaluating the unpopular items analytically,the weight of these items should be improved in calculating users’ similarities,so as to reflect users’ personalities and interests. Moreover,taking into account the impact of the time dependence,the time factor is introduced during the prediction of interests.Experimental results show that the algorithm can raise the accuracy of searching the nearest neighbors,and improve the recommendation quality of the collaborative filtering.

feedback frequency;collaborative filtering;personalized recommendation;time factor

1007-130X(2014)11-2234-05

2014-06-21;

：2014-08-28

河南省教育厅项目(13A520125)

TP311.13

：A

10.3969/j.issn.1007-130X.2014.11.030