基于二部分图网络结构推荐的改进算法

, ,

(上海师范大学 信息与机电工程学院,上海 200234)

基于二部分图网络结构推荐的改进算法

邓 松,邱静,陈军华*

(上海师范大学 信息与机电工程学院,上海200234)

介绍了一种基于网络结构推荐的改进算法.在标准物质扩散算法的基础上,考虑到用户的评分对推荐商品的影响,对推荐算法中初始资源分配矢量和资源转移矩阵进行了改进,增加了调节因子.使用来源于GroupLens网站上的训练集数来评价这个推荐算法的性能,从而进行了一系列的实验.实验结果表明,该算法比传统的协同过滤系统、基于网络结构的推荐系统和带有权重的基于网络结构的推荐系统具有更好的推荐精度和更高的命中率,解决了标准物质扩散算法当中的冷启动问题和可扩展性问题,使得推荐结果具有多样性.

推荐算法; 物质扩散算法; 冷启动问题; 可扩展性问题; 推荐多样性

0 绪 论

随着互联网技术日新月异的革新,全世界的网页服务器总数不断增加,网页的数量也因此呈现爆炸性的增长趋势[1].互联网上出现越来越多的暗信息,但是对人们有作用的信息,也越来越难以被发现.由此,诸如Google、百度和bing等搜索引擎[2]应运而生.但是搜索引擎需要用户能够明确自己的需求,输入关键字,所以反馈的信息都限制在用户已知的信息范围中,而不能帮助用户找到其不知道但有价值或感兴趣的内容.

推荐系统能够从一定程度上弥补搜索引擎的缺陷[3],相较于传统的搜索引擎,推荐系统分析用户的历史操作,建立了用户偏好模型,依靠算法计算预测用户对未知商品的偏好权重,并根据权重对商品排序,向用户推送一个可能令其感兴趣的商品推荐列表[4].推荐系统所采用的算法技术可以被分为两大主类:基于内容的推荐算法[5-6]和协同过滤算法[7-8].迄今为止,协同过滤算法是推荐系统中使用最成功、最广泛的算法[8].

基于网络结构的推荐算法[9-14]不考虑用户和产品的内容特征,而仅仅把它们看成抽象的节点,所有算法利用的信息都藏在用户和产品的选择关系之中.这些算法效果明显好于经典的协同过滤算法.但目前这些推荐系统还存在下列问题:

1) 缺乏个性化的推荐.因为推荐系统的不够完善,算法不精确,导致很多信息被笼统粗放地推荐给用户,缺乏个性化,致使用户得到的并不是其感兴趣的产品;

2) 推荐的自动化程度低.用户进行人机交互时,告知系统自己的信息和感兴趣的产品,但是由于系统更新不及时或延时效应等原因,产生了推荐效果不佳的情况;

3) 推荐的持久性程度低.由于大部分系统不能有效地利用用户的历史查找数据,只依赖当前的推荐信息,这样势必导致推荐持久力的下降;

4) 推荐策略单一.推荐系统在进行推荐时,对运用多种推荐策略缺乏考虑,不能将各种推荐算法的优点进行结合,多数情况下只是选择某种单一的推荐策略,如基于内容的搜索或基于分类浏览点击的检索,这将导致推荐的单一性.

1 相关技术基础

根据推荐算法的不同,推荐系统可以分为如下几类:协同过滤系统,基于内容的推荐系统,混合推荐系统[13]以及最近兴起的基于用户—产品二部分图网络结构的推荐系统.

1.1协同过滤算法

协同过滤算法通过以下公式[5]计算用户ui和用户uj之间的相似性:

(1)

(2)

对任意用户ui,所有aij=0的非零预测得分vij都按照降序排列,排在最前面的那些项目会被推荐给用户.

1.2基于内容的推荐算法

最初基于内容的推荐算法是协同过滤技术的延续与发展,它不需要依据用户对项目的评价意见,而是依据用户已经选择的产品内容信息计算用户之间的相似性,从而进行相应的推荐.随着机器学习等技术的完善,当前的基于内容的推荐系统可以分别对用户和产品建立配置文件[5],通过分析已经购买(或浏览)过的内容,建立或更新用户的配置文件.系统可以比较用户与产品配置文件的相似度,并直接向用户推荐与其配置文件最相似的产品.例如,在电影推荐中,基于内容的系统首先分析用户已经看过的打分比较高的电影共性(演员、导演、风格等)[6],再推荐与这些用户感兴趣的电影内容相似度高的其他电影.基于内容的推荐算法的根本在于信息获取和信息过滤.因为在文本信息获取与过滤方面的研究较为成熟,现有很多基于内容的推荐系统都是通过分析产品的文本信息进行推荐.

1.3物质扩散推荐算法

物质扩散算法行为类似于随机游走过程的资源分配过程[11],基于用户—商品二部分图,假设每个商品都具有一定数量的某种推荐能力,即用户选择过的商品都有某种向该用户推荐其他商品的抽象能力,商品占有资源并把更多资源传递给自己更偏好的商品.

由于二部分图本身是无权网络,X节点中的资源将平均分配到在各个Y节点中的邻居,同理,Y节点中的资源也将平均分配到各个X节点中的邻居.以图1(a)为例,3个X节点的初始推荐力资源为a,b,c,资源分配过程为:首先,X节点中的初始化资源根据二部分图的连接关系传递到Y节点,传递过程类似于物质扩散的过程,节点根据自身的度(与该节点的连边)大小而将资源稀释,例如a的度数为2,则每条边的终点将会得到a/2;然后Y节点中积累的资源,又从Y节点传递回到X节点,分配原理与前一步相同.两个集合通过之间的共同连接关系,实现了资源的再分配,节点的度越大,与它相关的连边传递的能量越小.两个过程的资源传递如图1(b)和图1(c)所示.

图1 二部分图的资源分配流程

最终分配到3个X节点的资源为x,y,z,式(3)表示的是最终资源和原资源的矩阵映射关系:

(3)

其中,矩阵是列归一化的权重邻接矩阵.假设推荐系统中有M个用户和N种商品,则二部分图有M+N个节点,用户集合X={x1,x2,…,xm},商品集合Y={y1,y2,…,yn},E为用户历史消费记录集合,假设用户xi选择过的所有产品,都具有某种向xi推荐其他产品的能力.这个抽象的能力可以看作位于相关产品上的某种可分的资源——拥有资源的产品会把更多的资源交给自己更青睐的产品.如果用户xi购买、选择或评价过商品yk,则xiyk∈E.xi的初始资源为f(xi)≥0,第一步从X集合传递到Y集合的推荐力资源,则商品yk的资源为式(4):

(4)

k(xi)是用户xi的用户度,{aik}是一个M×N的矩阵,如式(5)可以描述用户xi和商品yk是否具有选择关系:

(5)

即若用户xi选择了商品yk,则aik=1,否则aik=0.

第二步推荐力资源由Y集合传递回X集合,则用户xi的资源可以表示为式(6):

(6)

通过两步物质扩散,xj到xi的资源贡献可以表示为:

(7)

其中

(8)

资源分配矩阵为W={wij}n×n,wij是j的初始资源传递到i的比例,是原集合资源的最终分配形式,可以认为是节点j对于节点i的重要性,即商品j对于商品i的贡献度,也即产品j愿意分配给产品i的资源配额.W是非对称矩阵,对角线元素大于0.假设对于特定的用户xi定义用户历史消费记录的n维0/1 个性化矢量f,xi选择过的商品资源分配初始化为单位量1,其余的为 0,即f(yj)=aji,f代表了针对该用户的初始资源分配结构,具有个性化的特点,对于不同的用户,初始化矢量f是不同的.最终资源分配向量为f′,f′=wf,式(9)为f′的组成元素f′(yj):

(9)

最后将用户xi所有没有选择的商品yj(1≤j≤m,aji=0)进行降序排列,推荐最终资源最多的商品.

2 考虑用户对商品评分的改进算法

标准物质扩散算法中,任意一个用户收集的产品都被赋予了相同的权重.尽管算法可以得到比协同过滤算法更高的准确率,但是将所有产品一视同仁的做法并没有考虑用户对产品的评分对推荐效果的影响.许多推荐系统都允许用户对购买或者浏览过的项目进行评分,所以推荐系统也可以看成是一个评分系统[10,14],比如Yahoo的音乐推荐系统,允许用户对音乐评5个星级.评分越高说明用户越喜欢该音乐.基于网络结构的推荐算法只是判断用户是否选择过项目,不区分高低评分对推荐结果的影响,然而用户的评分一定程度上表示了用户对项目的喜好程度,不区分高低分可能会造成信息的损失[16-18],有些推荐算法直接忽略低分,在5分的推荐系统中,当且仅当用户对项目的评分大于等于3才认为用户选择过项目.但是用户对项目评分时有可能受当时环境等因素的影响,而且低分同样包含着一些信息,如用户关注过该项目,所以不应该直接去掉低分[11].

在本课题研究的改进算法中要区分高分和低分,即用户对项目的喜好,首先考虑的是,对于用户评分的平均分高的商品,说明用户对它的喜爱程度普遍高,则在初始资源分配时,就不应该跟其他平均评分低的商品获得一样的资源,故可以改进标准物质扩散算法中的初始资源分配矢量为式(10):

(10)

改进的算法中的另一个改进点就是对资源转移矩阵Wij的改进,同样是考虑用户对商品的评分对推荐算法的影响,改进的资源转移矩阵为:

(11)

通过物质扩散算法的资源转移过程,可以得到最终商品获得的推荐资源矢量为:

(12)

3 实验评价

3.1算法评价标准

为了评价算法的性能,采用基准数据集set-MovieLens进行测试,这个数据集被广泛的应用于测试推荐算法的效率.该数据集可以从Netflix网站上下载,它包含了1 837个用户对3 952部电影的评分数据,数据量达到了3×105.每个用户对电影的评分离散的分为1～5分5个等级.这个数据集被随机分为两个部分:其中80%的数据用于做训练集,20%的数据用户做测试集.

包括协同过滤、基于内容的推荐算法、标准的物质扩散算法和改进的考虑用户评分的二部分图网络结构在内的所有算法,都能够给用户提供一个未评分的有序的电影队列.对于任意用户ui,如果用户-项目(ui-oi)对在测试集中,则度量计算oj在有序队列中的位置.例如,如果用户ui未评分的电影有1 000部,而oj排在前面第10位,oj排在前10/1 000位置,记为r(ij)=0.01.一个优秀的推荐算法,r值越小,推荐能力越好[15].

3.2实验结果

电影评分表(表1)中,第一列表示用户的ID,第二列表示用户对电影的评分.这些评分数据都是从原始数据集中进行数据预处理得到的.

采用数据集的训练集和测试集,经过了5次的交叉验证.最终得到用户1的推荐列表如表2所示.

根据本算法和其他基于二部分图网络结构的算法的比较结果如表3所示.

表1 电影1的评分表

表2 用户1的推荐列表

表3 测试集中每一个入口的预测平均位置

如表3所示、根据协同过滤算法、基于内容的推荐算法、标准物质扩散算法和考虑用户对商品评分的改进算法的位置值的平均值分别为0.126、0.124、0.121和0.118.很明显,考虑用户对商品评分的改进算法具有最好的预测精度.

4 结 论

实验结果证明,所提出的算法能提高算法预测精度.关于平均预测精度,本算法分别比协同过滤算法、基于内容的推荐算法和标准的物质扩散算法增长了0.8%,0.6%和0.2%.

[1] 中国互联网信息中心.互联网发展与动态 [EB/OL].[2015-10-22],http://www.cnnic.cn/hlwfzyj/hlwfzzx/201212/t20121217_38186.htm.

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

Xu H L,Wu X,Li X D,et al.Comparison Study of Internet Recommendation System [J].Journal of Software,2009,2(2):350-362.

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

Liu J G,Zhou T,Wang B H.Research Progress of Personalized Recommendation System [J].Progress in Natural Science,2009,19(1):1-15.

[4] Yang M H,Gu Z M.Personalized recommendation based on partial similarity of interests [C].International Conference on Advanced Data Mining and Applications,2006,4093:509-516.

[5] Park H S,Yoo J O,Cho S B.A context-aware music recommendation system using fuzzy Bayesian networks with utility theory [C].Proceedings of the Third International Conference on Fuzzy Systems and Knowledge Discovery,Xi′an:ACM,2006.

[6] Chang Y I,Shen J H,Chen T I.A data mining-based method for the incremental update of supporting personalized information filtering [J].Journal of Information Science and Engineering,2008,24(1):129-142.

[7] Chen Y L,Cheng L C.A novel collaborative filtering approach for recommending ranked items [J].Expert Systems with Applications,2008,34(4):2396-2045.

[8] Liu J G,Wang B H,Guo Q.Improved collaborative filtering algorithm via information transformation [J].International Journal of Modern Physics C,2009,20(2):285-293.

[9] Liu J G,Zhou Tao,Che H A,et al.Effects of high-order correlations on Personaliz-ed recommendations for bipartite networks [J].Physica A,2010,389:881-886.

[10] Shang M S,Lyu L Y,Zhang Y C,et al.Empirical analysis of Web-based user-object bipartite networks [J].Europhysics Letters,2009,90(4):1303-1324.

[11] Zhou Tao,Kuscsik Z,Liu J G,et al.Solving the apparent diversity-accuracy dilemma of systems [C].Proceedings of National Academy of Sciences,2010,107(10):4511-4515.

[12] Wang Q,Duan S Y.Improved recommendation algorithm based on bipartite networks [J].Application Research of Computers,2013,30(3):771-775.

[13] Li Z,Wu X D,Peng H.Nonnegative matrix factorization on orthogonal subspace [J].Pattern Recognition Letters,2010,31(9):905-911.

[14] Zhang C J,Zeng A.Behavior patterns of online users and the effect on information filtering [J].Physica A,2012,391:1822-1830.

[15] Ma S C,Guan Y F.Improved recommendation algorithm based on bipartite networks [J].China Academic Journal Electronic Publishing House,2015,09(04):196-199.

(责任编辑：包震宇)

Animprovedrecommendedalgorithmfornetworkstructurebasedontwopartialgraphs

Deng Song,QiuJing,ChenJunhua*

(The College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai200234,China)

In this thesis,we introduce an improved algorithm based on network structure.Based on the standard material diffusion algorithm,considering the influence of the user′s score on the recommendation,the adjustment factor of the initial resource allocation vector and the resource transfer matrix in the recommendation algorithm is improved.Using the practical data set from GroupLens webite to evaluate the performance of the proposed algorithm,we performed a series of experiments.The experimental results reveal that it can yield better recommendation accuracy and has higher hitting rate than collaborative filtering,network-based inference.It can solve the problem of cold start and scalability in the standard material diffusion algorithm.And it also can make the recommendation results diversified.

recommendation algorithm; standard material diffusion algorithm; the problem of cold start; the problem of capability; recommended diversity

2015-12-22

邓 松(1991-),男,硕士研究生,主要从事推荐算法方面的研究.E-mail:994946153@qq.com

导师简介: 陈军华(1968-),男,副教授,主要从事分布式数据库及数据挖掘方面的研究.E-mail:chenjh@shnu.edu.cn

TP301.6

:A

:1000-5137(2017)04-0535-07

*