《武汉工程大学学报》 2018年04期
455-461
出版日期：2018-08-23
ISSN:1674-2869
CN:42-1779/TQ
一种基于社交网络友情度的个性化推荐算法
随着网络技术发展和社交网络服务的推广，人类交往全面进入在线社交网络服务（social networking services， SNS）时代［1］，国内外知名SNS如微博、微信、FaceBook和Twitter等。SNS用户规模持续扩大，信息交互更加快捷，同时在SNS的基础上又延伸出许多功能强大的应用，如微信在线支付、小程序及微信公众号等，使得SNS的服务内容越来越丰富。在SNS中，用户的自发参与产生了具有一些明显特征属性的社交大数据，主要的特征属性是“用户创建的内容”、“交互信息”及“关系信息”。 “用户创建的内容”是指用户自己在SNS上创建的内容及其相关信息，如博客上的帖子、信息发布的时间和标签信息等；“交互信息”是指用户间交互的内容，例如微信上用户之间的信息传输、朋友圈的点赞、评论等；“关系信息”构成一个社交圈的信息，代表SNS用户之间的直接或间接关联关系，如微信上朋友圈、微博的好友圈等。这类社交大数据已经被应用于个性化推荐领域的研究，挖掘用户的需求和偏好，及时向用户推荐满足个性化需求的信息［2］。传统的个性化推荐系统主要基于相似度的协同过滤（collaborative filtering， CF）算法向用户提供推荐。相似度的算法主要有皮尔逊相关系数（pearson correlation coefficient， PCC）、余弦相似度（cosine similarity， CS）及杰卡德均方差（jaccard?mean squared difference， JMSD）等方法［3］。但是以上算法只适合于利用明确的数据信息（如用户的评分）计算相似度，而大多数社交数据都含有许多隐式信息，这使得传统的推荐系统不能完全适合基于SNS的个性化推荐需求。此外，用户在社交圈信任关系密切的用户信息已被许多研究证实对于提升个性化推荐服务非常有用［4-6］，然而，现有的相似度算法不适合于在线社交用户之间亲密关系的度量，因为除了用户创建的内容之外，它们很少关注社交大数据的其它方面的特征，更没有考虑用户之间共享的主题数量。 本文提出了一种描述SNS用户之间亲密度的新方法——友情度，并通过交互、群体和个人三种相似度来计算友情度。该方法考虑了社交大数据的各种特征，提出的个性化推荐系统充分利用用户关心的主题和兴趣及紧密关联的用户的信息，为SNS用户推荐满足个性化需求的兴趣和主题。并使用各种评估指标如平均绝对误差（mean absolute error，MAE）、精确度Precision、召回率Recall和F1值等，评估所提出的推荐系统的性能和推荐质量，验证友情度在个性化推荐中的重要作用，证实了基于友情度的个性化推荐系统比基于PCC和JMSD算法的CF推荐系统的性能要优越，且推荐结果的质量要高。1 个性化推荐系统1.1 基于社交网络大数据的个性化推荐系统个性化推荐系统收集关于用户对项目的偏好的信息，为用户推荐希望获取的项目。而社交大数据中包含了显式或隐式信息，如博文、朋友圈信息、关注、博文时间和标签信息等，如能合理的利用这些信息，则可以增强个性化推荐。近年来，国内外一些学者在不断努力，试图利用隐式数据信息来改进个性化推荐系统。如潘一腾等［5］提出一种基于信任关系隐含相似度的社会化推荐算法，提高了社会化推荐算法的精度；刘静等［6］提出了一种个性化的标签推荐系统，使用用户的标记历史和地理信息来生成基于学习方法的推荐系统；赵亚辉和刘瑞［7］提出了基于评论的隐式社交关系进行个性化推荐。但是，与考虑SNS用户关联信息以获得推荐的方法相比，上述方法难以充分反映个人倾向并且推荐结果的准确度较低。1.2 基于人际关系的个性化推荐系统基于人际关系的个性化推荐方式可以分为基于影响力的推荐和基于朋友圈的推荐。在SNS上彼此相关的用户的偏好相似度要高于不相关用户的偏好相似度，他们之间的关联信息显然比不相关用户的信息更具有利用价值［8］。1.2.1 基于社交影响力的个性化推荐系统 基于影响力的推荐系统主要用于需要专业领域知识的推荐，如学术或新闻领域的推荐系统。例如陈林等［9］定义了对新闻界影响专家模型，提出一种新颖的个性化新闻推荐算法；文献［10］基于学术搜索平台ArnetMiner，融合深度学习方法、社会网络分析和语义搜索等相关技术，进行跨区域协作推荐与用户相关的专家和论文。 1.2.2 基于朋友圈的个性化推荐系统 对于SNS用户，人们更倾向于关注熟人和朋友的意见，基于朋友之间信任进行的推荐更容易被接受，因此基于朋友的信息提供的推荐效率更高。但是在SNS中，基于朋友的个性化推荐对于用户关系是均等看待的，没有考虑到用户之间关系远近的亲密度，大多数研究都是针对一组具有相似兴趣和偏好的社交网络服务用户提供推荐［11］。如刘海峰［12］提出了基于信任关系的商品推荐方法，改进了推荐的性能，并解决多样性推荐的问题。本文综合分析诸多学者研究成果的基础上，研究影响用户间亲密度的各种因素，提出基于友情度的个性化推荐系统，并对实验过程和实验结果进行分析，评估所提出系统的性能和推荐质量。2 基于友情度的个性化推荐系统近年来，国内外一些学者对基于用户之间亲密度的个性化推荐方法进行了一定的研究。如文献［13］考虑了用户互动和社交圈信息来计算他们之间的亲密度，提出一种基于联系强度的个性化模型来增强社交服务，给出了更高质量的推荐信息；文献［14］提出一种综合信任模型，构建了基于社会网络关系分析的综合推荐模型，应用矩阵分解技术推断微博的主题分布和用户的兴趣取向，实现微博的个性化推荐。但是，先前的研究没有考虑到影响友情度的各种因素，更没有对影响因素进行多维度分析，导致推荐信息的准确性和精度不高，因此需要一种新的方法分析影响友情度的各种因素，利用它们计算友情度，设计一种高效的个性化推荐系统。2.1 推荐算法基本流程本文提出的个性化推荐系统的流程主要分为以下3个阶段9个步骤。阶段一：处理所需的数据集，此阶段分为5个步骤。步骤1：在社交服务网站上抓取推荐领域相关意见及评论数据构建数据集；步骤2：在数据集中添加与推荐领域相关的正面、中性或负面的意见词词语，构建意见词词典；步骤3：根据意见词典，分析用户生成的内容如微博上的博文、大众点评网的贴文、FaceBook上的帖子等，给出内容的极性，如正面、负面或中性；步骤4：挖掘出与推荐领域及其评论信息相关的用户，提取用户的数据如用户ID值等，创建用户社交圈的用户矩阵；步骤5：利用前面内容的极性分析得分及用户的参考项目的次数得分，计算友情度及推荐系统中用到的隐式偏好值和主题分布值。阶段二：计算SNS用户间友情度，分为3个步骤。步骤6：利用SNS用户间的交互信息计算交互相似度，交互信息如微信朋友圈或微博上的评论、点赞或转发等信息；步骤7：使用主题分布值及隐式偏好值，计算个人相似度；步骤8：使用SNS社交圈用户信息计算用户组的相似度。融合以上3个相似度，计算出用户间的友情度。阶段三：构建推荐系统进行推荐阶段。步骤9：利用用户间友情度、隐式偏好值及前面所计算的相似度值，构建推荐系统，为用户提供高质量推荐结果。2.2 用户创建内容的极性分类用户在SNS上发布的内容中表达了自己的看法，代表了自己情绪或感受。根据原先建立的意见词典，可以把用户生成的内容的极性（OD）分类为正面、中性或负面的内容，分别数字化为 1，0，-1。 2.3 用户偏好值的计算从用户生成的信息中提取关键字（即项目）和包含关键字的主题，用户偏好分为用户项目偏好和用户主题偏好。根据内容的极性和用户生成内容的总数计算项目偏好[ru,i]：[ru,i=D∈Du,iODDu,i?] （1）式（1）中，Du，i表示用户u关于项目i所创建的内容的集合。用户的主题偏好是用户高级偏好，在这里以主题分布值来表示，本文通过使用与主题t相关联的用户生成的内容的总数的分布[θu,t]值来计算。算法如式（2）：[θu,t=|Du,t||Du|] （2）式（2）中，Du是关于用户u内容的集合、Du，t与用户u相关的主题t的内容的集合。2.4 友情度的计算在SNS中，综合考虑影响用户友情度的多种因素，用3种相似度来计算用户之间的友情度。这3种相似度分别是个人相似度P、交互相似度I和群体相似度G，如表1所示。2.4.1 个人相似度 个人相似度表示SNS上用户生成内容之间的相似度，可以通过项目的偏好值和主题分布来计算。用户生成的内容会涉及到各种喜好及兴趣，特别是在类似于大众点评、微博等社交网站上，在计算用户对项目的偏好时，共同兴趣的比例比仅计算用户偏好相似度更为重要。因此，本文利用JMSD算法，来计算用户之间的偏好相似度。[σJMSD]为均方差（mean squard difference，MSD）和Jaccard系数的乘积。本文中MSD系数表示用户u和f的项目偏好值之间的差异的平均值，用[σMSD]表示，Jaccard系数[J(u,f)]是SNS上用来计算用户共同兴趣的比率。计算方法分别如下：[σMSD(u,f)=i∈Idiu,fdu,f] [J(u,f)=|ru?rf||ru?rf|=du,f|ru|+|rf|-|du,f|]其中[diu,f]表示用户u和f关于项目i的偏好值之差的平方，[du,f]为一组[diu,f]。如果[ru,i]和[rf,i]皆不null ，[diu,f=（ru,i-rf,i)2?]，否则[diu,f=null]；[ru]和[rf]分别表示用户u和f的一组偏好值。则JMSD的算法如式（4）所示： [σJMSD(u,f)=σMSDu,f×Ju,f?] （4）SNS用户创建大量与推荐领域主题相关的内容，用户间的关系越亲密，用户之间交流的的主题范围就越广，而且SNS用户之间的主题的相似度是实现个性化检索的主要元素之一。因此，个人相似度的计算不仅考虑项目信任，还要考虑用户共享的主题数量及主题的相似度，以便在推荐领域根据个人倾向提供高质量的推荐结果。用户间的主题相似度可以通过使用散度（kullback-leibler divergence，KL）计算［15］。算法如式（5）所示：[QA(u,f)=1εKL(θu,t||θf,t+1)] （5）则个人相似度计算式如式（6），取项目信任度和主题相似度的加权之和，表示项目与用户提及的主题的相似度。[SimP(u,f)=αP?QT(u,f)+βP?QA(u,f)] （6）式（6）中[αP+βP=1]。 2.4.2 交互相似度 在SNS中，用户通过信息的交互来分享彼此的好恶及情感，若用户的好恶或偏好相似，则他们会积极分享信息。因此交互相似度可以通过用户之间“互动的广度和深度”来衡量，用户之间的交互相似度又是计算友情度的重要因素。在许多社交网站中，用户都可以通过转发、评论、关注、回复等功能进行相互交互，因此可以使用这些信息，与交互频率、交互近因等属性结合起来共同计算交互相似度。首先，计算SNS用户的交互频率。用户交互频率反映了用户之间的关系的远近，关系近的用户会频繁的积极交流，交流的信息也更有价值。用户交互频率算法如式（7）所示，其中q（u，f）表示用户u和f联系的次数。[QI(u,f)=lg{1+q(u,f)}????if{q(u,f)<10}1????????????????????????if{q(u,f)10}] （7）其次计算交互近因和交互时长因子。交互近因和交互时长因子是与用户之间的联系时间密切相关的权重。SNS大数据中，最新的信息非常重要，最近的联系意味着用户分享当前的兴趣，因此用户最近是否接触过是衡量亲密关系的关键因素。用户[u]和[f]的交互近因可表示为式（8）所示：[QRu,f=Ru,fLu] （8）R（u，f）表示用户u和f最近一次联系到当前时间所经过的时间，L（u）表示收集用户u的数据的时间。一般地，在SNS中与他人交互时间较长的人的信息比交互时间较短甚至没有沟通的人的信息更重要，如果用L（u，f）表示用户u和f之间的一次交互时长，则交互时长因子算法如式（9）所示：[QLu,f=Lu,fLu] （9）本文交互相似度是通过对[QI(u,f)]，[QRu, f]和[QLu,f]3个权重值进行加权来计算的，如式 （10）所示：[SimI(u,f)=αI?QI(u,f)?+βI??QR(u,f)+χI?QL(u,f)] （10）其中[αI+βI+χI=1]。2.4.3 群体相似度 群体相似度是指不同用户在SNS上所属社交圈的相似度，可以用来衡量用户与他的朋友之间的亲密关系。在SNS的社交圈里，用户倾向于将与他们密切接触或具有类似兴趣的用户作为他们的朋友，因此拥有类似朋友列表的不同用户所在社交圈相似度较高，即群体相似度较高。所以可以通过用户u和f共享的朋友的比率来计算u，f所在社交圈的相似度。在SNS社交圈里，用户朋友关系可分为直接和间接朋友关系。通过间接朋友关系，也可以获取用户社交圈中有用的信息和资源。本文用朋友级别的概念来描述群体相似度。如图1所示，将用户u的直接关联朋友的级别定义为一级，表示为Fu1，用户间接关联（第n层级）朋友的级别定义为n级，以Fun表示，例如Fu2表示用户u的两个边缘内连接的一组用户。在大多SNS中，几乎所有的用户的朋友用户都在6层以内，即n=6。结合Jaccard系数，则用户群体相似度的算法表示式（11）所示：[SimG(u,f)=αG|F1u?F1f||F1u?F1f|+βG|F2u?F2f||F2u?F2f|+?+ χG|Fnu?Fnf||Fnu?Fnf|] （11） 其中[(αG+βG+...+χG=1)]。2.4.4 友情度的计算 在SNS中，本文用友情度来度量用户之间的亲密关系，根据前文分析友情度主要体现在个人相似度、交互相似度和群体相似度几个重要的方面，综合式（6）、式（10）和式（11）3种相似度算式，本文SNS中友情度[QFu,f]算法如式（12）所示：[QFu,f=δSimP(u,f)，SimI(u,f)，SimG(u,f)]（12）其中，[δ]表示根据每个元素的重要性提供权重值差异的加权矢量。在社交网络中，直接或间接关联的用户的信息比未关联的用户的信息更为重要，根据这些用户的信息结合用户友情度和社交圈朋友的级别的定义，给出对用户u关于项目i的偏好值预测式，如式（13）所示：[pu,f=ru+f∈F1u?Fnu(rf,i-rf)*QF(u,f)f∈F1u?FnuQF(u,f)] （13）式（13）中[ru]和[rf]是用户u和f对所有项目的平均偏好值，[rf,i]是用户f对项目i的偏好值。3 结果与讨论3.1 实验环境与数据集的选取实验环境为Intel Xeon E5-2630*2CPU、32 GB DDR4内存、3 TB Sata3硬盘、Windwos Server 2008系统服务器，实验数据集来源于新浪微博音乐及电影2018年1月份乐评及影评博文数据的抓取，共28部在国内上映的电影和亚洲音乐排行榜60首音乐、8 138 315条评论博文和2 368 372个微博会员相关的信息。经过整理，实验中把该数据集分为评论博文信息、微博会员关系信息和评论意见词典。博文信息有博文ID、博文内容、发表时间、转发量、回复数、关注量、点赞量、博主ID、对博文的评论及关注者的微博会员ID；微博会员关系信息包括有微博会员的ID、会员名及会员关注者的ID及会员名；意见词典主要包括电影的正负面词汇列表，用来标志电影评论博文的极性情况。3.2 实验过程分析实验对数据集进行了交叉实验，目的是分析评估本文所提出的个性化推荐系统。实验中，把微博会员数据集分成两部分，其20%用于测试用户集、80%视为训练用户集，并建立了用户对用户的友情度矩阵，基于交互相似度的考虑，20％与其他用户积极互动的活跃用户是测试用户。在数据集中，实验中使用了28个电影和60个音乐共88个项目，但电影评论活跃用户提及的项目数量平均值大约为10个、音乐评论活跃用户大约为16个。对测试集合使用Leave-One-Out交叉验证［16］。首先基于测试集，计算用户之间的友情度，建立用户-用户友情度矩阵，基于此矩阵计算用户间交互和群体相似度；其次利用测试用户与训练用户之间的训练项目的偏好值及主题分部值，来计算个人的相似度；最后利用友情度3个重要元素：交互相似度（I），群体相似度（G）和个人相似度（P）的组合来计算用户之间的相似度。3.3 实验结果分析协同过滤个性化推荐系统是最受欢迎的推荐方式，而基于PCC和JMSD是在CF推荐系统中常用的系数，它的有效性已经在经典的的推荐系统数据集（如Movielens）中得到证实。本文所提出的系统利用直接或间接连接到SNS的用户的信息进行推荐，把本文推荐系统的性能与基于PCC和JMSD的CF推荐系统进行比较。使用衡量个性化推荐系统性能的几个主要指标MAE、精确度、召回率、F1值验证了推荐系统的推荐质量。3.3.1 IGP实验结果分析 本文针对精确度、召回率和F1值对友情度3个重要元素I、G、P及其组合进行实验。实验结果如图2所示。从图2中可以发现，在所有的组合中，I和P的组合（CIP）表现出最好的性能。因此，结合式（12），选择CIP作为友情度。3.3.2 MAE实验结果分析 MAE主要用于预测值的误差测量，定义为公式（14）：[δMAE=1Ii∈I1Ou,iu∈ou,i|pu,i-ru,i|] （14）式（14）中[Ou,i]表示用户集合，[pu,i]和[ru]在测试用户集U中都不为null值。MAE评估实验的结果如图3所示，实验中 K近邻（K）的范围是100到2 000之间。从图3中可以分析，本文所提出的推荐算法比基于PCC和JMSD的CF推荐具有更低的错误率。基于友情度推荐预测偏好值的准确性在整体范围内分比PCC提高20％左右，与JMSD相比，在K<1 000时，它的性能略高，但K≥1 000时，性能提高了大约有8％，K的数量越多，性能改善越高。3.3.3 针对推荐有效性的实验分析 MAE可能是衡量推荐算法性能的一个很好的指标，但是它不能准确衡量用户对推荐结果的满意度，因此有必要使用新的算法测量用户对推荐结果的满意度即评估推荐的有效性。通常精确度p、召回率r和[F1]值被用于衡量个性化推荐结果的有效性，本文中精确度、召回率和[F1]值表示如式（15）~式（17），实验结果如图4所示。[p=1Uu∈U|{i∈Zu|ru,iθ}|N] （15）[r=1Uu∈U|{i∈Zu|ru,iθ}||i∈I|ru,iθ|] （16）[F1=2×p×r(p+r)] （17） 其中Zu表示用户提供的N个推荐项的集合，[ru,i]∈［0，1］，[θ]表示阈值。为了衡量精确度、召回率和[F1]值，不仅要根据预测偏好值对推荐项目进行排序，而且还要确定推荐项目相关性判断的阈值。根据式（1）进行多次计算发现，式（15）和式（16）中如果[ru,i]>0.5，则表示用户在所有他的博文中对于项目i的正面评论都多于1次，因此可以判断推荐结果与i是相关的。因此，将阈值设置为0.5。从实验结果可以看出，就精度而言，所提出的系统与PCC和JMSD相比分别显示提高约8％和5％；在召回率方面，与PCC相比，所提议的系统性能提高约8％，与JMSD相比约为6％；对于F1值，与PCC相比，所提出的系统性能提高约10％，与JMSD相比约为9％。可见，本文所提出的推荐系统推荐质量上比基于PCC和JMSD的CF推荐系统整体上分别提高8.5%和7%左右。4 结 语基于SNS提出的友情度对于推荐有很大帮助，只要它用户之间的交互数据、好友列表信息或具有多个级别的项目，如微信、陌陌、微博等社交网络拥有用户之间的联系信息和用户之间评论的信息，利用这些信息就可以计算出用户之间友情度，而大多数基于SNS的推荐系统都可以使用友情度进行推荐。使用1个月的微博电影、音乐评论数据，针对MAE、精度、召回率、[F1]值进行了比较实验。结果表明，综合考虑SNS上的用户间的友情度，对于推荐结果的有效性有很大的影响，所提出的系统在所有度量方面比基于JMSD和PCC的推荐表现出较好的性能和推荐质量，对于提高推荐的准确性是有用的。虽然推荐质量的差异并不十分显著，但所提出的系统在所有度量指标中值都是最高的。