引用本文
任永功, 王宁婧, 张志鹏. 基于加权三部图的协同过滤推荐算法. 模式识别与人工智能, 2021,34(7): 666-676
REN Yonggong, WANG Ningjing, ZHANG Zhipeng. Collaborative Filtering Recommendation Algorithm Based on Weighted Tripartite Network. PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2021,34(7): 666-676.  
Doi: 10.16451/j.cnki.issn1003-6059.202107008
Permissions
Copyright©2021, 《模式识别与人工智能》编辑部
《模式识别与人工智能》编辑部
基于加权三部图的协同过滤推荐算法
任永功1, 王宁婧1, 张志鹏1
1.辽宁师范大学 计算机与信息技术学院 大连 116081
通讯作者:

张志鹏,博士,讲师,主要研究方向为数据挖掘、推荐系统.E-mail:zhipengzhang@lnnu.edu.cn.

作者简介:

任永功,博士,教授,主要研究方向为人工智能、数据挖掘.E-mail:jsj_paper@163.com.

王宁婧,硕士研究生,主要研究方向为人工智能、数据挖掘.E-mail:ning9609@163.com.

收稿日期: 2020-09-25 修回日期: 2021-05-17 接受日期: 2021-05-17
资助项目: 国家自然科学基金项目(No.61976109)、辽宁省自然科学基金博士启动项目(No.2020-BS-184)、大连市科技创新基金项目(No.2018J12GX047)、大连市高层次人才创新支持计划项目(No.2020RQ49)、大连市重点实验室专项基金项目资助
摘要

针对基于用户的协同过滤算法推荐结果过度集中在热门物品,导致多样性和新颖性较低、覆盖率较小的问题,文中提出基于加权三部图的协同过滤推荐算法.在分析数据稀疏和附加信息较少的基础上引入标签信息,可同时反映用户兴趣和物品属性,利用用户、物品和标签三元关系构建三部图.通过三部图网络映射到单模网络的方法获得用户偏好度,构建用户偏好度加权的三部图模型.根据热传导方法在加权三部图上进行资源重分配,挖掘更多的相似关系,利用协同过滤框架预测评分并进行推荐.在真实数据集上的实验表明,文中算法可较好地挖掘长尾物品,实现个性化推荐.

关键词: 协同过滤; 加权三部图; 用户偏好度; 热传导
中图分类号:TP 391
Collaborative Filtering Recommendation Algorithm Based on Weighted Tripartite Network
REN Yonggong1, WANG Ningjing1, ZHANG Zhipeng1
1. School of Computer and Information Technology, Liaoning Nor-mal University, Dalian 116081
Corresponding author:
ZHANG Zhipeng, Ph.D., lecturer. His research interests include data mining and recommender system.

About Author:
REN Yonggong, Ph.D., professor. His research interests include artificial intelligence and data mining.
WANG Ningjing, master student. Her research interests include artificial intelligence and data mining.

Fund:National Natural Science Foundation of China(No.61976109), Doctoral Start-up Project of Natural Science Foundation of Liaoning Province(No.2020-BS-184), Dalian Science and Technology Innovation Fund(No.2018J12GX047), Dalian High Level Talents Innovation Support Project (No.2020RQ49), Special Fund of Dalian Key Laboratory
Abstract

The over-concentration of recommendation results of user-based collaborative filtering algorithm on popular items causes the lack of diversity, novelty and coverage. Aiming at this problem, a collaborative filtering recommendation algorithm based on weighted tripartite network is proposed. Based on sparse analysis data and little additional information, tags are introduced to reflect user interests and item attributes simultaneously. Ternary relationships among users, items and tags are utilized to construct a tripartite network.The user preference is obtained by projecting the tripartite network to the one-mode network, and a tripartite network model weighted by user preference is constructed. According to the heat spreading method, resources are redistributed on the weighted tripartite network to find more similarity relationships. The standard framework of collaborative filtering is applied for prediction and recommendation. Experiments on real datasets show that the proposed method mines long-tail items better and realizes personalized recommendations.

Key words: Collaborative Filtering; Weighted Tripartite Network; User Preference; Heat Spreading

本文责任编委 张燕平

Recommended by Associate Editor ZHANG Yanping

随着互联网技术的飞速发展, 爆炸式增长的数据导致信息过载问题[1, 2].推荐系统不需要用户提供明确的需求, 通过分析用户的历史行为, 建立用户的兴趣模型, 为用户推荐与之兴趣一致的物品, 缓解信息过载问题.

目前学者们提出很多推荐算法, 运用最广泛的是基于预测评分的推荐算法, 如协同过滤(Colla-borative Filtering, CF)[3].这类算法主要利用用户对物品的评分信息预测用户未评分物品的评分值, 进而对预测评分值降序排列, 组成top-L列表推荐给用户.因此, 这类算法都致力于提高预测准确性.

但是, 准确性并不是衡量用户对推荐物品满意度的唯一标准, 多样性也很重要.而且, 在实际生活中, 一些热门物品会被很多用户喜欢, 基于用户的协同过滤(User-Based CF, UBCF)在依靠邻近用户为目标用户进行推荐时, 如果目标用户的邻近用户集中存在喜欢热门物品的用户, 这些热门物品大概率会被推荐给目标用户, 而那些长尾物品由于大多数用户不了解, 预测评分值较小, 难以出现在推荐列表中.这就导致推荐的物品过度集中在热门物品中, 而潜在的长尾物品往往被忽略, 大幅降低UBCF推荐的多样性和新颖性.因此, 挖掘长尾物品、提升推荐多样性和新颖性, 已成为推荐系统中重要的研究话题.

近年来, 学者们为了改进传统推荐算法的多样性, 进行大量的研究工作, 这些研究主要分为两类:物理信息法和二次优化法.物理信息法是应用物理学中的热传导、物质扩散等理论.热传导的原理是当两个不同温度的物体接触时, 热量会从温度较高的物体传导到温度较低的物体上, 直到两者的温度相同, 所以有助于提高系统中低温物体的温度.应用到推荐系统中, 物品推荐可看作是用户-物品二部图上的连边预测问题, 而传导过程可用于寻找图中两个节点之间的关联强度, 热传导的方法像凹透镜一样把用户的视野发散到那些关联强度较小(较不流行)的长尾物品上, 提高推荐的多样性.Liu等[4]等消除冗余的物品二阶相似性, 通过平衡补偿设计物质扩散和热传导过程的对称组合, 提高推荐多样性.孟桓羽等[5]结合CF、图计算与K最近邻(K Nearest Neighbor, KNN), 通过图的消息传播及改进的相似度计算模型先筛选用户再计算相似度.Molaei等[6]提出异构深度扩散方法, 以元路径作为网络中的实体, 通过学习异构网络的潜在表示以考虑信息扩散.Song等[7]将特征组合应用于局部随机游走模型, 根据每个特征组合的强度计算和重新分配随机游走粒子的传递概率, 然后预测连边.Zare等[8]使用元路径计算用户之间的相似性, 利用链接预测发现相似度网络中的隐藏连边, 然后应用扩散规则预测隐藏用户的评分.上述算法通过结点间的资源扩散, 可快速地在更多的结点间建立联系, 提高计算效率, 但是忽略结点间连边的强度和其它附加信息, 不能提供更个性化的推荐.

二次优化法因其简单高效和良好的可扩展性被许多研究者采用.Zhang等[9]提出协同过滤优化算法, 同时考虑评分和社交关系, 重新排列阈值控制的区域以调整推荐列表, 提高推荐多样性.Ma等[10]提出基于核方法和多目标优化的协同过滤算法, 引入核密度估计和多目标优化, 改善动态数据中的概念漂移, 提高推荐系统的多样性.Yi等[11]基于用户属性和评分求解用户相似度, 并聚类用户, 然后利用低阶矩阵填充方法填充评分矩阵, 找到目标用户所在类, 为目标用户选择最优的近邻用户.Zhao等[12]采用融合宽度与深度的框架, 减轻选择偏见, 探索多种软参数共享技术, 优化多个排名目标.Lin等[13]提出产生帕雷托最优解的推荐框架, 通过加权聚合协调多个优化目标, 然后提出限制条件, 保证两步帕雷托最优解优化算法.Hamedani等[14]将推荐问题转化为多目标优化问题, 基于提高准确性、多样性和降低流行度三个优化目标给出推荐列表, 然后求解定义的优化问题.Gogna等[15]提出利用现有的评分预测排序和重排序策略的两阶段机制, 降低过拟合度, 提升多样性.二次优化算法只是在推荐后进行二次优化, 不在推荐过程中考虑多样性, 如果推荐结果本身不具有多样性, 二次优化算法未起到作用.

针对协同过滤存在的多样性较低的问题, 本文提出基于加权三部图的协同过滤推荐算法(Weighted Tripartite Network Based CF, WTNCF).引入标签信息, 将用户、物品二元关系扩充为用户、物品、标签三元关系, 用于构建三部图, 并计算用户偏好度, 作为图中对应的边权.然后在加权的item-user-tag三部图上通过热传导方法计算用户相似度, 并整合物品和标签两个维度的用户相似度.在UBCF框架基础上, 再进行预测评分并推荐.相比现有的协同过滤算法[11]和基于图扩散的算法[4], 本文算法中标签的使用可反映用户兴趣和物品属性, 将不跟随大众的个性化偏好度作为边权, 提高用户喜欢的长尾物品的推荐, 同时利用热传导倾向于将资源传播到关联强度较小的物品这一特性, 与潜在的长尾物品建立联系.标准数据集上的实验表明, 本文算法可给用户提供更具多样性、新颖性的推荐.

1 基于加权三部图的协同过滤推荐算法

基于图网络扩散的推荐算法是协同过滤研究的新方向.随着标签的使用, 用户可自由地为电影、音乐添加标签.标签既表示物品的潜在属性, 又可反映用户的兴趣, 因此将标签信息加入到user-item二部图中, 形成基于item-user-tag三部图的推荐算法, 可获得个性化推荐.已有的利用未加权的图模型的研究未考虑图中连边的权值, 将所有边权视为相等的, 但在实际应用中边权具有重要意义.因此, 本文提出基于加权三部图的协同过滤推荐算法.

1.1 三部图模型的构建

item-user-tag三部图模型将用户U、物品I和标签T三种元素视为抽象的结点并利用结点之间的关系构建三部图.U={u1, u2, …, um}表示m个用户的集合, I={i1, i2, …, in}表示n个物品的集合, T={t1, t2, …, tr}表示r个标签的集合.3个集合之间的关系使用三部图IUT=(U, I, T, E)表示, 其中U∩ I∩ T=Ø , E表示用户与物品及用户与标签之间的连边集合.用户和物品之间的连边表示用户选择物品, 用户和标签之间的连边表示用户使用过标签.

三部图由2个子图(二部图user-item和user-tag)组成, 分别表示为

如果用户u选择物品i, aui =1, 否则aui=0.同样, 如果用户u使用标签t, a'ut=1, 否则a'ut=0.未加权的item-user-tag三部图模型如图1(a)所示.

图1 item-user-tag三部图模型Fig.1 Tripartite network model

三部图中用户与物品及标签之间连边的权值通常表示用户对物品及用户对标签的喜欢程度, 本文将用户对物品及用户对标签的喜欢程度定义为用户偏好度, 包括用户对物品的偏好度(User Preference from Item Perspective, upi)和用户对标签的偏好度(User Preference from Tag Perspective, upt).然后将用户偏好度值作为item-user-tag三部图中对应连边的权值, 构建加权item-user-tag三部图模型.用户对物品及用户对标签的偏好度定义如下.

定义 1 在三部图IUT中, 如果用户u与物品i之间存在连边, 则用户u与物品i之间连边的权值表示用户u对物品i的喜欢程度, 定义为用户u对物品i的偏好度, 记为upi(i, u).

定义 2 在三部图IUT中, 如果用户u与标签t之间存在连边, 则用户u与标签t之间连边的权值表示用户u对标签t的喜欢程度, 定义为用户u对标签t的偏好度, 记为upt(t, u).

根据上述定义得到加权item-user-tag三部图模型如图1(b)所示.表示加权user-item和user-tag的二部图A和A'中, 如果用户u选择物品i, aui=upi(i, u), 否则aui=0.同样地, 如果用户u使用标签t, a'ut=upt(t, u), 否则a'ut=0.

在加权user-item二部图中, 记与物品i连接的所有边的边权之和

表示物品i的度.记与用户u连接的所有边的边权之和

表示用户u的度.A的转置矩阵 .在此基础上, 构造与用户度相关的对角矩阵:

其中

构造与物品度相关的对角矩阵:

其中

在加权user-tag二部图中, 记与标签t连接的所有边的边权之和

表示标签t的度.记与用户u连接的所有边的边权之和

表示用户u的度.A'的转置矩阵 .构造与用户度相关的对角矩阵:

其中

构造与标签度相关的对角矩阵

其中

1.2 用户偏好度计算

将三部图IUT视为2个二部图UI和UT, 利用投影技术将2个二部图中的二元关系映射到2位用户相关的单模网络UI和UT中, 使用文献[16]方法求出用户对物品及标签的偏好度, 分别作为三部图中用户与物品及用户与标签之间对应连边的权值.其中:如果用户u选择物品i, 表示二部图UI的矩阵P中元素pui=1, 否则pui=0; 如果用户u使用标签t, 表示二部图UT的矩阵P'中元素p'ut=1, 否则p'ut=0.UI的矩阵Q=PPT, 表示选择相同物品的每个用户对之间的关系, UT的矩阵Q'=P'P'T, 表示使用过相同标签的每个用户对之间的关系, PT和P'T分别为P和P'的转置矩阵.三部图转为二部图和单模网络的过程如图2所示.

图2 三部图转为二部图网络和单模网络的过程Fig.2 Transformation process of tripartite network to bipartite network and one-mode network

用户对物品的偏好相似度表示, 如果2位用户选择某些相同的物品, 他们对物品的偏好是相似的.用户对物品的偏好相似度矩阵X中的元素xuv表示用户u和v对物品的偏好相似度:

基于上述用户对物品的偏好相似度, 可得到用户对物品的偏好度:

Y中元素yiu为用户u对物品i的偏好度upi(i, u).

用户对标签的偏好相似度表示如果2位用户使用某些相同的标签, 则他们对标签的偏好是相似的.用户对标签的偏好相似度矩阵X'中的元素x'uv表示用户u和v对标签的偏好相似度:

基于上述用户对标签的偏好相似度, 可得到用户对标签的偏好度:

Y'中元素y'tu为用户u对标签t的偏好度upt(t, u).

1.3 相似度计算

本文考虑计算用户间的相似度, 因此将加权三部图中用户结点作为中心结点, 目标用户的初始资源按边权比例传播到与其邻接的物品和标签两类结点.然后所有的用户结点将接收到来自邻接结点的资源, 也就是资源在两个加权的二部图中传播, 将其他用户从目标用户处获得的资源作为用户间的相似度.最后以线性方式整合物品和标签两个维度的用户相似度.

首先考虑加权的user-item二部图, 假设为目标用户u分配“ 1” 单位的资源, 其他用户资源为0, 得到m维初始资源向量f1.经过热传导扩散后得到所有用户的最终资源向量 f'1=Wf1, 其中W为热传导过程的状态转移矩阵.第一步用户将资源按照用户和物品之间的边权与每个物品边权之和的比分配给每个物品, 扩散后可得物品资源向量

g1=DIATf1.

第二步按照物品和用户之间的边权与每个用户边权之和的比例将资源扩散给用户, 得到所有用户的最终资源向量

f '1=DUAg1=DUADIATf1.

由此可得状态转移矩阵W=DUADIAT, W中第v行第u列的元素wvu表示用户v从用户u处获得的资源:

将用户v从用户u处获得的资源wvu定义为加权user-item二部图中目标用户u和用户v之间的相似度:

其中, upi(i, u)为用户u对物品i的偏好度,

表示user-item加权二部图中用户v的度,

表示user-item加权二部图中物品i的度.Eui表示user-item加权二部图中用户u与物品i之间的连边.

类似地, 考虑加权user-tag二部图中的扩散, 假设为目标用户u分配“ 1” 单位的初始资源, 其他用户资源为0, 得到m维初始资源向量f2.热传导扩散后得到所有用户的最终资源向量f '2=W'f2.第一步用户将资源按照用户和标签之间的边权与每个标签边权之和的比分配给每个标签, 扩散后可得标签资源向量

g2=DTA'Tf2.

第二步标签以同样的方式按照标签和用户之间的边权与每个用户边权之和的比例将资源返回给用户, 得到所有用户的最终资源向量

f '2=D'UA'g2=D'UA'DTA'Tf2.

可得状态转移矩阵

W'=D'UA'DTA'T.

W'中第v行第u列的元素w'vu表示用户v从用户u处获得的资源:

将w'vu定义为加权user-tag二部图中目标用户u、v之间的相似度:

其中, upt(t, u)为用户u对标签t的偏好度,

表示user-tag二部图中标签t的度,

表示user-tag二部图中用户v的度, Eut表示user-tag加权二部图中用户u与标签t之间的边.

目标用户为u1, user-item加权二部图上求解用户相似度的过程如图3所示, 在加权的user-tag二部图上扩散的过程也是类似的.

图3 资源在加权的user-item二部图上的扩散过程Fig.3 Resource diffusion on a weighted user-item bipartite network

最后, 引入参数λ 整合物品和标签两方面的用户相似度sim(v, u)和sim'(v, u), 得到最终用户间的相似度:

similarity(v, u)=λ sim(v, u)+(1-λ )sim'(v, u), (7)

其中, λ ∈ [0, 1], 为可调节的参数.当λ =0时, 相似度变为单独的加权user-tag二部图上的用户相似度, 当λ =1时, 相似度变为单独的加权user-item二部图上的用户相似度.

1.4 预测评分及推荐

在基于用户的协同过滤框架基础上, 为目标用户未选择的物品进行预测评分.给定目标用户u和未选择的物品i, 用户u对物品i的预测评分为

其中, v表示已经对物品i评过分的用户, rv, i表示用户v对物品i的评分, 分别表示用户u、v的所有评分的平均评分, Nu(s)表示用户u的s个邻近用户.

再将目标用户u未选择物品的预测评分进行降序排列, 产生推荐列表, 前L个物品将被推荐给用户u.

本文算法的具体步骤如下所示.

算法 1 基于加权三部图的协同过滤推荐算法

输入 三部图IUT, 评分矩阵

输出 为目标用户u推荐的L个物品

for each u∈ U do

if Eui∈ E, Eut∈ E then

pui=1, p'ut=1

else

pui=0, p'ut=0

end if

end for

P、P'的转置矩阵为PT、P'T

表示单模网络的矩阵Q=PPT, Q'=P'P'T

根据式(1)和式(3)计算用户偏好相似度矩阵X、X'

根据式(2)和式(4)计算用户偏好度矩阵Y、Y'

计算A、A'的转置矩阵AT和A'T

计算加权user-item二部图中u和i的度

计算加权user-tag二部图中u和t的度

构造对角矩阵DU、DI、D'U、DT

根据式(5)式(7)计算用户相似度

计算目标用户u的s个邻近用户集Nu(s)

for v∈ Nu(s) do

end for

向目标用户u推荐预测评分最高的L个物品

1.5 算法复杂度分析

假设一个推荐系统含有m位用户、n个物品、r个标签.本文算法计算用户对物品及标签偏好度的时间复杂度为O(m2), 计算2种用户相似度的时间复杂度分别为O(nm2)和O(rm2), 预测评分的时间复杂度为O(mn).因此, 当r> n时, 本文算法的时间复杂度为O(rm2), 当r≤ n时, 本文算法的时间复杂度为O(nm2).UBCF计算用户相似度阶段的时间复杂度为O(nm2), 而预测评分阶段的时间复杂度为O(mn), 所以总的算法时间复杂度为O(nm2).

UBCF仅考虑评分信息, 推荐列表中的物品多集中在热门物品.而本文算法需要同时考虑评分和标签信息, 但在实际应用中, 标签的个数r相对于物品数n并不会太大.所以, 相比UBCF, 本文算法在提高推荐列表的多样性和系统中物品覆盖率的基础上, 并未提高时间复杂度.

2 实验及结果分析
2.1 实验数据集和评估指标

本文采用公开的电影数据集HetRec2011-Movie-Lens-2k[17]和社交音乐网站的Last.fm数据集[17], 验证算法的有效性.HetRec2011-MovieLens-2k数据集包括2 113位用户、10 197部电影(物品)、13 222个标签, 共有855 598条用户对电影的评分.Last.fm数据集记录每位用户聆听艺术家作品的次数, 聆听次数表示用户对艺术家作品的兴趣, 将聆听次数映射为15的整数值作为用户的隐式评分:

其中l表示聆听次数.Last.fm数据集包含1 892位用户、17 632名艺术家(物品)、92 834条评分、11 946个标签.

2个数据集上评分范围为15分, 评分大于等于3分表示用户喜欢该物品.实验采用交叉验证方法进行性能评估, 在数据集中随机选取其中80%的数据作为训练集, 剩余20%的数据作为测试集.为了保证实验的准确性, 5组测试集间互不相交, 覆盖整个数据集, 对5次实验的结果求平均值.

为了评估本文算法推荐质量, 采用3种评估指标:平均个性度(Mean Personality, MP)[18]、覆盖率(Coverage)[19]和新颖性(Novelty)[20].MP和Coverage用于衡量推荐系统推荐结果的多样性:

其中, L表示推荐的物品数量, #u表示用户总数, Ω u(L)、Ω v(L)分别表示用户u、v的数量为L的推荐物品集合, U表示用户集合, I表示物品集合.MP值和Coverage值越大, 推荐的多样性越好.

为了进一步衡量推荐结果, 评估推荐系统的新颖性:

其中, k(i)表示选择过物品i的所有用户数.Novelty值越小, 推荐的新颖性越好.给定目标用户u的前L个物品推荐列表Ω u(L), 将所有用户的Novelty值求平均值, 得到系统的平均新颖性.

2.2 参数设置

本文算法引入可调节的参数λ .当λ =0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1

时, 计算MP值、Coverage值和Novelty值.选取物品推荐列表长度为12, 邻近用户数目为20, 随着λ 的变化, 2个数据集上指标值的变化趋势如图4所示.

图4 两个数据集上λ 对指标值的影响Fig.4 Effect of λ on indexes on 2 datasets

在HetRec2011-MovieLens-2k数据集上, 由图4(a)可看出, 随着λ 值的增大, MP值也随之增大, 当λ =0.3时, MP值达到最优, 之后不再变化并趋向平稳.由(b)可看出, Coverage值先随着λ 值的增大而增大, 在λ =0.4, 0.5时达到峰值, 然后Coverage值随之减小.由(c)可看出, Novelty值先随着λ 值的增大而减小, 在λ =0.4时达到最小值, 之后变化较小.

对实验数据的分析表明, 当λ =0.4时, 算法的各项指标都达到最优.因此, 在HetRec2011-Movie-Lens-2k数据集上将λ 的最优值定为0.4.同理, 在Last.fm数据集上选取λ =0.6.

2.3 实验结果

为了验证本文算法(WTNCF)的推荐性能, 使用如下5种对比算法.

1)基于用户的协同过滤算法(UBCF)[21].只利用评分信息度量用户间的相似度, 通过用户最近邻进行预测并推荐物品.

2)基于二部图的物质扩散算法 (Probabilistic Spreading, ProbS)[20].该算法通过两步资源扩散的过程实现:在第一步物品向用户扩散时, 用户的资源等于与其有连边的每个物品资源平均值的总和; 在第二步用户向物品扩散时, 物品的资源等于与其有连边的每个用户资源平均值的总和.

3)基于二部图的热传导算法(Heat Conduction, HeatS)[20].在两步资源扩散时:在第一步资源从物品向用户扩散时, 每位用户的资源等于与该用户连接的所有物品资源的平均值; 在第二步用户向物品扩散时, 每个物品的资源等于所有与该物品有连接的用户资源的平均值.

4)基于用户属性和矩阵填充的协同过滤算法(CF Based on User Attributes and Matrix Completion, UAMCCF)[11].算法基于用户属性和评分求解用户相似度并聚类用户, 再利用低阶矩阵填充评分矩阵, 找到目标用户所在类, 为目标用户选择最优的邻近用户.

5)基于消除冗余扩散和补偿平衡的推荐算法(Information Filtering Based on Eliminating Redundant Diffusion and Compensating Balance, ERDCB)[4].首先消除物品冗余的二阶相似性, 再通过平衡补偿设计物质扩散和热传导过程的对称组合.

本文选取邻近用户数为20、25、30、35、40、45、50, 推荐列表长度为2、4、6、8、10、12, 分别在2个数据集上对比算法的MP值、Coverage值和Novelty值.

各算法在2个数据集上的Coverage值对比如图5所示.由图可知, Coverage值随着邻近用户数的增加逐渐降低, WTNCF的Coverage值均最高.

图5 各算法在2个数据集上的Coverage值对比Fig.5 Coverage comparison of different algorithms on 2 datasets

各算法在2个数据集上的MP值对比如表1所示.由表可知, WTNCF具有较高的MP值.当推荐长度一定时, 推荐的多样性和新颖性会随着邻近用户数目的增加而降低.因此, 当邻近用户数目较小时, WTNCF具有较理想的推荐效果.

表1 各算法在2个数据集上的MP值对比 Table 1 MP comparison of different algorithms on 2 datasets

各算法在2个数据集上的Novelty值对比如图6所示.

图6 各算法在2个数据集上的Novelty值对比Fig.6 Novelty comparison of different algorithms on two datasets

由图6可知, 在2个数据集上, 随着邻近用户数的增加, Novelty值逐渐升高.当邻近用户数为20, 时Novelty值最低.随着邻近用户数的增加, ProbS、UBCF的Novelty值明显最高, 推荐质量不佳, 而WTNCF具有较低的Novelty值, 可提供更加新颖的推荐.

UBCF是基础的协同过滤算法, 参考邻近用户的建议越多, 推荐结果的个性化程度越低.HeatS、ProbS是基于图扩散的推荐算法的基础算法, HeatS的资源在扩散过程中倾向于关联强度小的物品, 推荐结果多样性较好.ProbS资源扩散倾向于关联强度大(流行)的物品, 多样性较差.UAMCCF为基于用户的协同过滤算法, 使用用户属性作为附加信息, 结合属性和评分信息计算用户相似度, 对推荐结果有一定的改进.ERDCB为基于图结构的推荐算法, 消除冗余的用户相似度, 并结合热传导和物质扩散算法, 提高推荐的多样性.

从实验结果可看出, UBCF、ProbS两种基础算法具有较差的多样性和新颖性.HeatS在资源扩散的过程中扩大用户视野, 提升推荐个性化程度.UAM-CCF使用用户属性信息, 性能具有一定提升, 但包含流行物品的偏差.ERDCB虽然消减冗余的物品二阶相似性, 但是引入物质扩散, 在一定程度上导致结果受流行物品影响, 且未考虑用户-物品二部图中连边的权重问题, 降低推荐的多样性和新颖性.WTNCF在引入标签信息的图上通过热传导资源扩散的过程计算得到物品和标签两个维度的用户相似度, 提高推荐个性化程度, 同时考虑图中连边的权值, 消除同一边权对多样性造成的影响, 达到较理想的个性化推荐.

3 结束语

本文针对UBCF中推荐结果集中在热门物品而导致多样性、新颖性较低的问题, 提出基于加权三部图的协同过滤推荐算法, 将基于图的热传导算法应用到UBCF中以计算相似度, 可较容易地推荐潜在的长尾物品, 提高推荐结果的多样性.引入标签丰富可用的信息, 同时反映用户兴趣偏好和物品潜在属性.将三部图中用户喜欢的物品和标签赋予更高的权值, 更好地实现个性化推荐.本文算法在一定程度上提高推荐结果的个性化程度, 但是忽略随着时间的推移用户偏好会发生改变的问题, 今后将继续研究如何引入时间信息, 及时准确地跟随时间的变化更新用户偏好, 进一步提高推荐质量.

参考文献
[1] CHEN R, HUA Q Y, CHANG Y S, et al. A Survey of Collaborative Filtering-Based Recommender Systems: From Traditional Methods to Hybrid Methods Based on Social Networks. IEEE Access, 2018, 6: 64301-64320. [本文引用:1]
[2] ADOMAVICIUS G, TUZHILIN A. Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(6): 734-749. [本文引用:1]
[3] JAFFALI S, JAMOUSSI S, SMAILI K, et al. Like-Tasted User Groups to Predict Ratings in Recommender Systems. Social Network Analysis and Mining, 2020, 10(1): 42-52. [本文引用:1]
[4] LIU X C, SU X, MA J M, et al. Information Filtering Based on Eliminating Redundant Diffusion and Compensating Balance. Inter-national Journal of Modern Physics B, 2019, 33(13). DOI: DOI:10.1142/S0217979219501297. [本文引用:3]
[5] 孟桓羽, 刘真, 王芳, 等. 基于图和改进 K近邻模型的高效协同过滤推荐算法. 计算机研究与发展, 2017, 54(7): 1426-1438.
(MENG H Y, LIU Z, WANG F, et al. An Efficient Collaborative Filtering Algorithm Based on Graph Model and Improved KNN. Journal of Computer Research and Development, 2017, 54(7): 1426-1438). [本文引用:1]
[6] MOLAEI S, ZARE H, VEISI H. Deep Learning Approach on Information Diffusion in Heterogeneous Networks. Knowledge Based Systems, 2020, 189. DOI: DOI:10.1016/j.knosys.2019.105153. [本文引用:1]
[7] SONG A B, LIU Y Y, WU Z A, et al. A Local Rand om Walk Model for Complex Networks Based on Discriminative Feature Combinations. Expert Systems with Applications, 2019, 118: 329-339. [本文引用:1]
[8] ZARE H, POUR M A N, MORADI P. Enhanced Recommender System Using Predictive Network Approach. Physica A(Statistical Mechanics and Its Applications), 2019, 520(8): 322-337. [本文引用:1]
[9] ZHANG L, WEI Q S, ZHANG L, et al. Diversity Balancing for Two-Stage Collaborative Filtering in Recommender Systems. Applied Science, 2020, 10(4): 1257-1272. [本文引用:1]
[10] MA T M, WANG X, ZHOU F C, et al. Research on Diversity and Accuracy of the Recommendation System Based on Multi-objective Optimization. Neural Computing and Applications, 2020, 33(3). DOI: DOI:10.1007/S00521-020-05438-W. [本文引用:1]
[11] YI J, ZHONG M S, CHEN Y F, et al. A Hybrid Collaborative Filtering Recommendation Algorithm Based on User Attributes and Matrix Completion // Proc of the 2nd International Conference on Communication, Network and Artificial Intelligence. Bristol, UK: IOP, 2019: 388-395. [本文引用:3]
[12] ZHAO Z, HONG L C, WEI L, et al. Recommending What Video to Watch Next: A Multitask Ranking System // Proc of the 13th ACM Conference on Recommender Systems. New York, USA: ACM, 2019: 43-51. [本文引用:1]
[13] LIN X, CHEN H J, PEI C H, et al. A Pareto-Efficient Algorithm for Multiple Objective Optimization in E-Commerce Recommendation // Proc of the 13th ACM Conference on Recommendation Systems. New York, USA: ACM, 2019: 20-28. [本文引用:1]
[14] HAMEDANI E M, KAEDI M. Recommending the Long Tail Items through Personalized Diversification. Knowledge Based Systems, 2019, 164(2): 348-357. [本文引用:1]
[15] GOGNA A, MAJUMDAR A. DiABIO: Optimization Based Design for Improving Diversity in Recommender System. Information Sciences, 2017, 378: 59-74. [本文引用:1]
[16] HU J Y, GAO Z W, PAN W S. Multiangle Social Network Reco-mmendation Algorithms and Similarity Network Evaluation[J/OL]. [2020-08-23]. https://www.emis.de/journals/HOA/JAM/Volume2013/248084.pdf. [本文引用:1]
[17] CANTADOR I, BRUSILOVSKY P, KUFLIK T. Second Workshop on Information Heterogeneity and Fusion in Recommender Systems// Proc of the 5th ACM Conference on Recommender Systems. New York, USA: ACM, 2011: 387-388. [本文引用:2]
[18] GAN M X, JIANG R. Constructing a User Similarity Network to Remove Adverse Influence of Popular Objects for Personalized Re-commendation. Expert Systems with Applications, 2013, 40(10): 4044-4053. [本文引用:1]
[19] 谭昶, 刘淇, 吴乐, 等. 推荐系统中典型用户群组的发现和应用. 模式识别与人工智能, 2015, 28(5): 462-471.
(TAN C, LIU Q, WU L, et al. Finding and Applying Typical User Group in Recommender Systems. Pattern Recognition and Artificial Intelligence, 2015, 28(5): 462-471. ) [本文引用:1]
[20] REN X L, LÜ L Y, LIU R R, et al. Avoiding Congestion in Re-commender Systems. New Journal of Physics, 2014, 16(6): 1367-1385. [本文引用:3]
[21] JALILI M, AHMADIAN S, IZADI M, et al. Evaluating Collaborative Filtering Recommender Algorithms: A Survey. IEEE Access, 2018, 6: 74003-74024. [本文引用:1]