在线社会网络中推荐算法的研究

黄蓝会

(宝鸡文理学院 计算机学院， 宝鸡 721016)

在线社会网络中推荐算法的研究

黄蓝会

(宝鸡文理学院 计算机学院， 宝鸡 721016)

针对在线社会网络中用户间的关系存在多种关系复合的情况，应用复杂网络理论设计了结合协同过滤推荐算法和基于网络结构推荐算法的混合推荐算法。利用复合多子网模型和在线社会网络演化模型设计的推荐系统用户模型,并在此基础上提出了基于在线社会网络社团结构的最近邻查询算法，并可根据最近邻集合评分后做出推荐。仿真实验证明，该算法具有较高的准确率和召回率。

在线社会网络； 复杂网络； 数据挖掘； 推荐算法

0 引言

网络的迅猛发展伴随着信息量的倍数增加，目前的主要购物平台京东、淘宝的在线商品数量超过了8亿件，主要通信平台微信用户超过5亿，由于信息量太多，用户很难快速直接获取有效信息，形成信息超载问题。[1][2]

目前，针对信息超载问题的解决办法主要有两种，一种是通过搜索引擎如Google、Baidu等检索系统，但这些检索系统只能被动地按照用户给出的条件查询，最后返回一样的查询结果，无法主动为用户提供信息；另一种是个性化推荐系统[3]，通过收集用户的信息，分析他的需求和兴趣后向其推荐信息或产品。[2][4]目前大型的电子商务平台如京东、淘宝等都使用了不同形式的自动推荐系统。[5]推荐系统是电子商务领域的重要研究内容之一，其中的推荐算法是关键点，本文以豆瓣网为例，研究适合在线社会网络的推荐算法。

豆瓣网是目前国内用户数量较大的书影音评价、推荐和交友网站，豆瓣注册用户之间的形成好友关系的方式总结起来有两种，一种是直接通过“关注”操作形成显式好友关系；还有一种是在豆瓣网中由于对同一个事物有相同的爱好成为隐式好友关系。在豆瓣网中用户采用1-10分的数字代表自己对某部电影的喜好程度，喜好同一部电影的用户因为兴趣爱好可能组成讨论组或好友群，这种隐含朋友关系实际上是从用户的行为角度出发，利用相同兴趣作为媒介，帮助用户通过喜爱的电影资源找到兴趣相似的其他用户，然后通过他们找到更多适合自己的电影，最后发展为进入电影购票网站购买电影票，成功完成一次推荐活动。

1 相关研究

推荐系统中推荐方法很多，本文主要研究两种推荐方法，一种是协同过滤推荐[6]。其基本思想是：系统认为某个用户倾向于购买具有相同兴趣爱好的同类用户所购买的商品，即他的邻居用户的购买行为会影响这个用户可能的购买意向。该算法根据用户对信息的评分建立评分矩阵，利用用户和评分的模型建立评分矩阵，通过余弦相似度[7]、相关相似性[8]以及修正的余弦相似度算法来计算两个用户购买同一个商品的相似度。这种利用相似性算法来计算两个用户相似度的方案适用于评分矩阵数量较多的情况。[9]如果某些用户为了保护个人信息或者是嫌麻烦没有在购买商品或看到信息后给出评分，就会导致矩阵中数据较少，产生数据矩阵稀疏问题，从而降低了这种算法的推荐效果[10]。还一种推荐方法是基于网络结构的推荐。其基本思想是：用户和产品都抽象成节点，用户和商品直接的关系抽象成边，节点和边组成网络。周涛等[11]提出了二分图上的资源分配关系，例如如果用户在网络中针对某个信息发表了评价或者购买了商品，就认为用户和该信息或商品建立了联系。

2 推荐算法

本文将豆瓣网用户关注的人所构成的网络称之为豆瓣网用户关注关系网，这个好友关系是显式的，将豆瓣网用户对电影的评价所构成的网络称之为豆瓣网用户影评关系网，这个好友关系是隐式的。利用复杂网络理论，设计了一个将豆瓣网用户关注关系网和豆瓣网用户影评相似关系网组成的在线社会网络演化模型[12]。根据用户对一部电影评分的一致性设定相关兴趣阈值，如果两个节点的相似性系数超过阈值，则认为这两个用户有相同的兴趣，模型中表示为该用户和电影之间有连边，形成隐式好友关系。协同过滤推荐主要用隐式关系的相似性作为判断依据，没有考虑显式好友关系有可能以后建立隐式关系，因此，本文将两种关系都作为推荐系统中用户间相似性的判断依据，设计一个动态用户模型。

建立动态用户模型的步骤是，首先根据用户电影评分数据，建立隐式关系子网，然后建立显式关系子网，再根据多子网复合复杂网络模型的子网加载运算，构造多关系的复合网，在构建过程中将新用户作为新的节点加进去。

基于多关系的在线社会网络演化模型建立动态用户模型，建模步骤如下：

(1) 假设复合网G=(V，E，R，F)中存在N种关系，其中稳固关系为N1种，不稳固关系为N2种，则R=R1×…×Ri×…×RN=((r1,…,ri,…,rN)|ri∈Ri，l≤i≤N)且dom(ri)=(0,1}(1≤i≤N)，其中1表示存在关系Ri，0表示不存在。

(2) 构造初始网络：构造具有m0个节点，e0条边的多关系网络，确保节点没有孤立点并且网络中的边没有重连，同时vh，vi∈{m0}，∈{e0)，存在F()=(r1,…，ri,…，rN)且dom(ri)=1(1≤i≤N)。

推荐系统的动态用户模型生成后的第二步就是根据对模型进行聚类，通过社团发现算法可以得到多个邻居用户群，设定相关阈值后筛选出最近邻居。本文设定目标用户ud，目标用户的最近邻居数为m，聚类结果为C，社团中度最大的用户节点a，相似性阈值为。

具体算法步骤如下：

(1) 设置最近邻用户集NUd=∅；

(2) 判断是否将社团加入最近邻居用户集合。首先计算每个社团结构Ci中度最大的用户节点与目标用户的相似度sim(ud,a)，将相似度按照降序排列；

(3) 将第(2)步得到的相似度和设定阈值比较，只有当sim(ud,a)≥α时，将整个社团结构加入最近邻居用户集；

(4) 在最近邻居集合中选择前K个用户作为目标用户，根据第(2)步相似度的排序结果可知，这K个目标用户的相似度最高。

(5) 根据公式一生成第(4)步目标用户对同一部电影的预测评分。

推荐精度的高低由相似性阈值α来调整，如果候选邻居集合少，可以调小α，这样可以在更多的用户集合中查找最近邻居。

3 实验结果与分析

评价推荐算法优劣的方法很多，本文主要通过分类准确度来评价该算法和协同过滤推荐算法。 衡量分类准确度的主要指标是准确率和召回率。

准确率定义为系统推荐的所有项目中用户喜欢的项目的比例。

公式为准确率=

召回率定义为用户喜欢的项目中是系统推荐的项目比例。

公式为召回率=

本文利用自己编写的程序[13]抓取豆瓣网的数据，利用协同过滤算法和本文推荐算法进行准确率和召回率的比较。经过数据预先处理后抓取了其中的10 235个用户以及他们在豆瓣网上评价的11 298部电影，根据推荐算法，为用户推荐未评分但可能喜欢的电影。

将实验中的用户的电影评分数据集划分80%训练集和20%测试集，利用数据集合E随机选取测试集Ep和训练集Et，某个用户a相关的测试集定义为，训练集地定义为 。将测试集中用户分成10组，同时获取这10 235个用户给出的电影评分,如图1、图2所示。

图1 比较两个算法的准确率

图2 比较两个算法的召回率

从图1和图2可以看出，本文提出的推荐算法10组用户表现平稳，在准确率和召回率方面都比协同过滤推荐算法高。

4 总结

个性化服务是Web信息处理的主要发展趋势之一，个

性化服务技术中提高推荐信息的准确率是目前个性化服务的主要研究方向。本文利用用户在网络中的多种关系建立网络模型，缓解了推荐系统的数据稀疏问题，将新用户采用动态更新的方式加到网络中，解决了冷启动问题，在购物平台使用推荐算法，为用户量身定做地推荐他感兴趣的商品将是商业应用的发展趋势。

[1] 陈洁敏,汤庸,李建国,等. 个性化推荐算法研究[J]. 华南师范大学学报(自然科学版),2014,46(5):9-15.

[2] 王国霞,刘贺平. 个性化推荐系统综述[J]. 计算机工程与应用,2012,48(7):66-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 Oil Knowledgeand Data Engineering,2005,17(6):734-749．

[4] 吴泓辰,王新军,成勇,等. 基于协同过滤与划分聚类的改进推荐算法[J]. 计算机研究与发展,2011,48:205-212.

[5] 李涛等. 王建东,叶飞跃,等.一种基于用户聚类的协同过滤推荐算法[J]. 系统工程与电子技术,2007,29(7):1178-1182.

[6] Adomavicius G,Tuzhilin A. Towards the next generation of recommender system: a survey of the state-of-the-art and possible extensions[J]. IEEE Transaction on Knowledge and Data Engineering,2005,17(6):734-749.

[7] Salton G，McGill M. Introduction to modem informationretrieval [M]. New York, USA：McGraw-Hill,1983.

[8] Resnick P,Iacovou N，Suchak M. An open architecture for collaborative fileting of net news[C]∥Proc. of ACM conferenceon Computer Supported Cooperative Work,1994.

[9] 文俊浩,舒珊. 一种改进相似性度量的协同过滤推荐算法[J]. 计算机科学,2014,41(5):68-70.

[10] 邓爱林,朱扬勇,施伯乐. 基于项目评分预测的协同过滤推荐算法[J]. 软件学报,2003,14(9):1621-1628.

[11] Zhou T, Jiang LL, Su R Q, et al. Effect of initialconfigurationon network-basedrecommendation [J]. EPL(Euro physics Letters),2008,81(5):58004.

[12] 黄蓝会. 基于社会媒体网络的聚类方法的研究[J].微型电脑应用,2016,32(6):1-2.

[13] 黄蓝会.基于在线社会网络的网络爬虫的研究和设计[J].电子设计工程,2014,22(6):106-108.

Recommendation Algorithm in Online Social Network

Huang Lanhui

School of Computer,Baoji University of Arts and Science,Baoji 721016,China

In the online social network, there are many kinds of relationships. In this paper, a hybrid algorithm is introduced to design the complex network. This algorithm combines the two algorithms, one is a collaborative filtering recommendation algorithm, and other is based on the characteristics of the network structure recommendation algorithm. Based on the above researches, a recommendation algorithm for multi-relationship online social network is proposed. User model of the recommendation system is derived from multi-relationship online social network evolution model. Based on the user model, the nearest neighbors query method of community in multi-relationship online social network is proposed, recommendations are made based on the nearest neighbor set and items set selected by the nearest neighbors. Experiments prove that evaluation criteria of recommended system, such as, recall rate, precision rate and so on are higher than those of traditional collaborative filtering recommendation system, and its prediction is more accurate.

Online social network; Complex network; Data mining; Recommendation algorithm

国家自然科学基金(No.61379030);陕西省教育厅专项科研项目(15JK1028)

黄蓝会(1980-),女,湖南岳阳人,硕士,讲师,研究方向:物联网应用,数据挖掘。

1007-757X(2017)04-0042-03

TP311

A

2016.10.14)