计算机应用   2016, Vol. 36 Issue (12): 3363-3368  DOI: 10.11772/j.issn.1001-9081.2016.12.3363
0

引用本文 

张萌, 南志红. 基于用户偏好的信任网络随机游走推荐模型[J]. 计算机应用, 2016, 36(12): 3363-3368.DOI: 10.11772/j.issn.1001-9081.2016.12.3363.
ZHANG Meng, NAN Zhihong. Trust network random walk model based on user preferences[J]. JOURNAL OF COMPUTER APPLICATIONS, 2016, 36(12): 3363-3368. DOI: 10.11772/j.issn.1001-9081.2016.12.3363.

通信作者

张萌(1990-),男,山西太原人,硕士研究生,主要研究方向:智能系统、金融预测、推荐系统. E-mail:1216081662@qq.com.

作者简介

南志红(1964-),女,山西沁源人,副教授,硕士,主要研究方向:信息系统、商务智能

文章历史

收稿日期:2016-06-15
修回日期:2016-09-06
基于用户偏好的信任网络随机游走推荐模型
张萌, 南志红    
山西财经大学 信息管理学院, 太原 030006
摘要: 为了提高推荐算法评分预测的准确度,解决冷启动用户推荐问题,在TrustWalker模型基础上提出一种基于用户偏好的随机游走模型——PtTrustWalker。首先,利用矩阵分解法对社会网络中的用户、项目相似度进行计算;其次,将项目进行聚类,通过用户评分计算用户对项目类的偏好和不同项目类下的用户相似度;最后,利用权威度和用户偏好将信任细化为不同类别下用户的信任,并在游走过程中利用信任用户最高偏好类中与目标物品相似的项目评分进行评分预测。该模型降低了噪声数据的影响,从而提高了推荐结果的稳定性。实验结果表明,PtTrustWalker模型在推荐质量和推荐速度方面相比现有随机游走模型有所提高。
关键词: 基于信任网络推荐    用户偏好    随机游走    推荐系统    冷启动    
Trust network random walk model based on user preferences
ZHANG Meng, NAN Zhihong     
Faculty of Information and Management, Shanxi University of Finance and Economics, Taiyuan Shanxi 030006, China
Abstract: In order to improve the accuracy of rating prediction and resolve cold-start problem in recommended systems, on the basis of the TrustWalker model, a random walk model based on user preferences, named PtTrustWalker, was proposed. Firstly, the similarities of users and items were calculated in social networks through matrix factorization method. And then, the items were clustered and the preference of user to items and the user similarity in different categories were calculated through user's scores. Finally, by making use of authority score and user preference, the credibility was detailed into user's credit in different categories, and the score was predicted by the item score of trusted user's highest preference which was similar to the target item in the process of migration. The proposed model decreases the influence of noisy data and improves the stability of the recommendation. The experimental results show that, the PtTrustWalker model has some improvements in the quality and speed of recommendation compared with the existing random walk models.
Key words: trust-based network recommendation    user preference    random walk    recommendation system    cold-start    
0 引言

随着互联网的快速发展,移动设备、Web服务所产生的大量数据使用户难以从中选择满足其需求的服务。为帮助用户在信息过载的情况下能够获取所需信息,推荐系统应运而生并在电子商务领域发挥重要作用,如Amazon、豆瓣、Facebook等网站中推荐服务已经成为其个性化服务的重要组成部分。为精确有效为用户进行推荐,研究者提出了多种推荐算法并不断改进,其中协同过滤[1]是目前应用最为广泛的推荐算法之一。

而面对推荐系统中普遍出现的冷启动问题,协同过滤由于其推荐机制局限性,无法对存在冷启动问题的系统进行推荐。现有的解决方式大多是将流行物品推荐给用户,或利用用户上下文信息进行推荐来缓解冷启动问题。而随着在线社交网络的兴起,引入信任网络已经成为改进协同过滤的一个重要手段。在信任网络中,目标用户信任的邻居用户可以被推荐相同的服务。Golbeck[2]提出的TidalTrust模型在信任网络中使用改进的广度优先搜索策略,从离目标用户最短路径中找出所有对预测项目评分的用户,以此来预测用户对该项目的评分。Massa等[3]提出的MoleTrust模型利用信任传播理论评估信任值的方式,提高了利用信任网络推荐准确性和覆盖率。Jamali 等[4]将协同过滤与基于信任的推荐相结合,提出一种在信任网络中随机游走的模型TrustWalker,有效地避免噪声数据的影响,游走过程中不仅考虑目标项目,同时考虑了信任用户在目标项目相似项目上的评分。其理论框架以信任网络为基础,协同过滤作为补充。朱丽中等[5]提出的CoTrustWalker模型针对TrustWalker模型的不稳定性,采用云模型计算相似度,在小规模数据集上提高了推荐结果的稳定性,并保证了其推荐精确度。Deng等[6]提出的RelevantTrustWalker模型将评分矩阵分解后利用特征矩阵进行相似度计算,同时利用用户相似度修正TrustWalker模型,提高了模型推荐质量。上述方法的局限之一在于信任用户的建议并不绝对适用于目标用户,因为两者可能有不同的偏好方向。

因此,针对上述模型中推荐适用性、模型稳定性等问题,本文提出了一种社会网络中基于用户偏好的PtTrustWalker模型。PtTrustWalker在TrustWalker模型基础上通过细化信任、引入权威度等手段加强信任网络,使推荐更有针对性以及易解释性;并对原模型游走过程进行修正,增强模型的稳定性,一定程度上提高了推荐速度。最后在Epinions数据集上评估方法的准确性和效率,通过实验结果证明了所提算法可获得较好的推荐效果。

1 问题定义

定义 U={u1,u2,…,un} 表示用户集合,S={s1,s2,…,sm} 用来表示项目集合。R=[ri,j]n×m 为评分矩阵,ri,j一般属于[1, 5]的整数。T=[tu,v]n×n 为信任矩阵,tu,v∈[0,1]表示用户u 和v 之间的信任度,其中0表示不信任,1表示信任。推荐系统任务的定义如下:

定义 1 给定一个目标用户u0∈U,对其未评分项目s0∈S进行预测评分,即预测ru0,s0的数值。

1.1 相似度计算

矩阵分解(Matrix Factorization,MF)[7]以其高扩展性以及良好的预测能力备受研究者喜爱。MF将评分矩阵分解成为两个低维矩阵——用户和项目潜在特征矩阵,在保留主要信息特征的同时,降低了数据维度,为计算用户项目相似度提供便利。文中将用户评分矩阵R大致分解为两个矩阵P和Q:

$\mathbf{R}\approx \mathbf{P}{{\mathbf{Q}}^{\text{T}}}$ (1)

其中P∈Rm×d、Q∈Rn×d分别表示用户和项目的潜在特征矩阵,两矩阵的每一行代表一个用户或物品的潜在特征向量。分解后的矩阵,利用余弦相似度来衡量用户之间和物品之间的相似性,计算方式如下:

$User\_Sim(u,v)=\cos ({{u}^{*}},{{v}^{*}})=\frac{{{u}^{*}}\cdot {{v}^{*}}}{\left| {{u}^{*}} \right|\cdot \left| {{v}^{*}} \right|}$ (2)
$Item\_Sim({{s}_{i}},{{s}_{j}})=\cos (s_{i}^{*},s_{j}^{*})=\frac{s_{i}^{*}\cdot s_{j}^{*}}{\left| s_{i}^{*} \right|\cdot \left| s_{j}^{*} \right|}$ (3)

其中:u*、v*分别代表用户u、v的潜在特征向量;si*、sj*分别代表物品si、sj的潜在特征向量。 下面的例子将清楚地说明计算过程。

例1 给定一个6名用户和4个物品的评分矩阵如下:

$\mathbf{R}=\left[ \begin{matrix} 5 & 3 & 0 & 2 \\ 5 & 0 & 2 & 2 \\ 3 & 4 & 0 & 3 \\ 0 & 0 & 5 & 1 \\ 3 & 5 & 1 & 1 \\ 5 & 3 & 2 & 5 \\ \end{matrix} \right]$

将其分解后,得到特征矩阵P和Q :

$\begin{align} & \mathbf{P}=\left[ \begin{matrix} -0.4427 & 0.2295 \\ -0.3626 & -0.3357 \\ -0.4106 & 0.2727 \\ -0.1146 & -0.8192 \\ -0.3940 & 0.2486 \\ -0.5793 & -0.1656 \\ \end{matrix} \right] \\ & \mathbf{Q}=\left[ \begin{matrix} \text{-0}\text{.6980} & \text{ 0}\text{.0371} \\ \text{-0}\text{.4993} & \text{0}\text{.4568} \\ \text{-0}\text{.2131} & \text{ -0}\text{.8772} \\ \text{ -0}\text{.4670 } & \text{-0}\text{.1434} \\ \end{matrix} \right] \\ \end{align}$

选择用户u4(0.1146,-0.8192)和u6(-0.5793,-0.1656),通过式(2)可以计算相似度为0.1390,同理可由矩阵Q计算物品s1与s3相似度为0.1842。从评分矩阵可以观察到两用户评分差异十分明显,因此两者相似度不高。该方法可以较精确地计算用户和物品间相似度。

1.2 用户偏好

根据项目相似度,将物品集合进行聚类SC={Sc1,Sc2,…,Scn},其中n为聚类数,并可得到不同类别评分矩阵R={Rc1,Rc2,…,Rcn}。Rcn中评分不仅表示用户对项目喜好程度,同时隐含了用户对项目所属类别Scn的偏好度。例如,用户对一部武侠电影评了高分,能够推测用户对武侠类电影有较高的兴趣度,在为该用户进行电影推荐时,武侠片的效果相比其他类型电影效果可能更好。本文就用户对项目类偏好度计算基于以下假设:在某物品类中,用户评分的项目数占用户总共评分的项目数的比例越高并且对该类中项目的平均评分越高,则表示用户越有可能喜欢该类项目[8]。只有同时符合两项条件时,推测的可信度才越大。如用户在项目类A中评分次数占其总评分数比例很高,但评分都在1~2分(评分在1~5),那么该用户对A类项目的偏好度可能不高,若为其推荐类A中的项目,效果可能不是很好。又如用户对项目B中某一物品评5分,即该用户对B类项目平均评分为最高分,但由于其评分次数过少,不能因此确定用户偏向于B类项目。所以在同时满足两个条件时,用户喜欢该项目类的可信度才越高。偏好由两部分组成:类偏好数占总偏好比例X,类内平均喜好度Y。

$\begin{align} & {{P}_{uc}}={{X}_{uc}}*{{Y}_{uc}}=\frac{\left| {{S}_{c}}\cap {{S}_{u}} \right|}{\left| {{S}_{u}} \right|}*\frac{\sum\limits_{s\in {{S}_{c}}\cap {{S}_{u}}}^{{}}{{{r}_{u,s}}}}{\left| {{S}_{c}}\cap {{S}_{u}} \right|} \\ & \text{ }=\frac{\sum\limits_{s\in {{S}_{c}}\cap {{S}_{u}}}^{{}}{{{r}_{u,s}}}}{\left| {{S}_{u}} \right|} \\ \end{align}$ (4)

其中:Sc 表示项目类c中的物品集合;Su 表示用户u评过分的物品集合;ru,s表示用户u对项目s的评分。

1.3 信任度量

在推荐系统中,信任常被认为与用户交互历史和评分喜好相关。其最大作用是帮助去除来自恶意虚假用户的信息,保证信息真实性。现给出如下定义:

定义2 信任是用户在其交互历史基础上所建立的相互依赖的关系,是判断用户提供某种服务的能力的度量。

定义3 信任度是信任等级的体现,是反映用户信任关系的度量。信任具有不对称性、传递性、动态性等特性[9]

定义4 信任度可分为局部信任和全局信任。局部信任度指用户对其他用户主观信任度。全局信任指的是社区中某个用户的总信任或权威度,全局信任越大表明该用户在网络中影响力越大,越容易得到其他用户的信赖。

本节首先介绍全局信任度,即权威度的度量方法,进而与类信任度融合得到细化后的信任网络。

1.4 权威度度量

Goldbaum[10]在2011年提出follow the leader模型,模型以两种用户类型leader、follower来区分用户,其中follower在某个领域中较信任leader,即leader在一定程度上能够影响follower的决策。在社交平台中,被许多人信任的用户具有较高的权威度,可以引领其他用户作出决策,如论坛中的资深版主,微博的”大V”都可以从某种程度上反映该用户的影响力。综上所述,专家会被许多人信任,并且评价能力能够代表物品的平均水平,下面将阐述权威度的计算方法。

信任网络的传递性使得越被权威用户所信任的用户专家度越高,将其定义为全局权威度。用户全局权威度由信任该用户的数量与质量度量,可表示为:

$PR(u)=\frac{(1-\alpha )}{\left| U \right|}+\alpha \sum\limits_{{{u}_{i}}:({{u}_{i}},u)\in T}{\frac{PR({{u}_{i}})}{Out({{u}_{i}})}}$ (5)

其中:PR(u)表示用户u的全局权威度;|U|为数据集中用户数量;ui:(ui,u)∈T表示信任u的用户;Out(ui)表示用户ui信任用户数;$\sum\limits_{{{u}_{i}}:({{u}_{i}},{{u}_{0}})\in T}{\frac{PR({{u}_{i}})}{Out({{u}_{i}})}}$表示信任用户u的用户传递给u的信任度。该公式结合社会网络信任特性,较好地解释了用户全局权威度取决于信任该用户的所有用户的全局权威度。

社会网络中专家的评分往往与大众评分较为符合,用户评价的物品数量与评价质量决定用户局部权威度,其计算方式如下:

$Au(u)=\frac{\sum\limits_{s\in {{S}_{u}}}{(1-\left| {{r}_{u,s}}-\overline{{{r}_{s}}} \right|*{{e}^{-\left| U(s) \right|}})}}{\left| {{N}_{u\_\max }} \right|}$ (6)

其中:$\sum\limits_{s\in {{S}_{u}}}{(1-\left| {{r}_{u,s}}-\overline{{{r}_{s}}} \right|*{{e}^{-\left| U(s) \right|}})}$表示用户评价质量;|ru,s-rs|表示用户u对项目s评分与项目s平均得分偏离程度,计算项目均分时应取出该用户对其评分已保证其公平性。计算中将评分归一化到[0,1],所以|ru,srs|∈[0,1]。e-|U(s)|反映了项目s流行程度,|U(s)|表示对项目s有评分的用户数,评分用户越多,e-|U(s)|越小;$\sum\limits_{s\in {{S}_{u}}}{(1-\left| {{r}_{u,s}}-\overline{{{r}_{s}}} \right|*{{e}^{-\left| U(s) \right|}})}$越大表示用户u受信任程度越高。同时,用户权威度与自身评分数目有关,|Nu_max|表示评分次数最多的用户评分次数。

由上述结论可知用户权威度应由全局权威度与局部权威度衡量,故将用户权威度Auth(u)定义为:

$Auth(u)=\alpha PR(u)+\beta Au(u)$ (7)

其中:参数α、β分别调节全局权威度和局部权威度占用户专家度的比例,α,β∈[0,1],α+β=1。Auth(u)∈(0,1)值越大,说明该用户在某些领域受信任越高,越具有权威性。根据不同信任网络,调节参数使用户权威度能有效影响其他用户评分的状态。

如前文所述,局部信任关系直接应用于推荐系统并不总能增加预测精度,依靠信任用户的推荐只能算是可靠,但这样的建议并不绝对影响目标用户的评分,因为目标用户和信任用户会有不同的兴趣偏好,因此对信任的细化工作是有必要的。本文将信任度分为全局信任和局部信任,其中全局信任即上文所提权威度或专家度,并将信任度与用户偏好相似性结合,将其称为信任融合过程。本文认为用户相似度越高其信任邻居的推荐越可靠,否则会参考用户的声望影响力,即用户权威度。用户u、v在c类的信任融合公式如下:

$\begin{align} & tr(u,v,c)=User\_Sim(u,v,c)*{{t}_{u,v}}+ \\ & \text{ }(1-User\_Sim(u,v,c))*Auth(v) \\ \end{align}$ (8)

其中:User_Sim(u,v,c) 表示在类别c下利用类评分矩阵Rc计算出的用户u与用户v相似度;tu,v表示用户非对称的局部信任;Auth(v)表示用户v在信任网络的影响力。利用类相似度与权威度等信任度量,可以有效区分不同信任用户推荐对目标用户的影响力。

2 PtTrustWalker模型

在TrustWalker模型中仅对目标用户和特定项目进行预测,如1.4节所述,仅依靠信任用户的推荐,结果只是可靠,但这样的推荐在目标用户与信任用户的偏好有较大差异时,解释性与预测效果并不理想;并且模型在游走过程中选择项目的随机性导致其推荐精度不高,引入权威度并结合用户相似度细化信任同时修正其游走过程,可以有效解决上述问题。本文借鉴TrustWalker模型框架,结合偏好信任提出了一种基于用户偏好的信任网络随机游走PtTrustWalker模型,模型框架如图 1,并有如下改进:

图 1 PtTrustWalker模型框架

1) TrustWalker模型在局部信任网络中游走,预测分数时没有考虑用户的偏好,信任用户的推荐只能算是可靠,但这样的建议并不绝对影响目标用户的评分。PtTrustWalker模型将目标用户信任细化结合用户权威度,针对不同类别项目预测时在类别信任网络中游走,优先考虑同一类别的项目评分作为参考,若停止用户在该类别未评分,将根据停止用户具有高偏好的类别中与预测项目相似度最高的项目作为预测评分参考,使得推荐具有较好的可解释性。

2) TrustWalker模型以等概率选择下一跳转节点,过高的随机性使其推荐精度不佳,易限于盲目游走。考虑到信任网络特性,用户相似度,用户局部信任和权威度,都应当作为选择节点时需要考虑的因素。这就是说当前用户更信任、更相似的节点在游走时以更大概率被选择,作为评分参考。

3) 每趟游走停留节点的概率不仅应当考虑当前节点用户偏好相似度和游走的深度,同时考虑到信任网络的传递性,节点之间的信任度也需考虑。

4) 在随机游走过程中停留概率较小的及节点可能是噪声数据,本文设定了全局游走停止条件。PtTrustWalker模型在多趟游走后得到一个用户参考列表,当游走过程中参考列表足够稳定并且符合预测需要时终止游走。

2.1 推荐算法

PtTrustWalker模型通过多次迭代得到推荐结果。每一趟游走从目标用户u0开始,在其加权信任网络中游走。在第k步游走至特定用户u,若用户u对目标物品s0有评分,游走停止并返回当前节点及其评分作为游走结果。否则,有如下几种情况:

1)随机游走以φu,k,sim,Tr 的概率停留在当前用户u。若u在项目s0所在类c有评分,在u、c类已评分项目中以Fu(c,si)概率选择项目si的评分;若u未在该类评分,将在u偏好最高类中以Fu(c,sj)概率选择项目sj的评分。其计算方式如下:

${{F}_{u}}(c,{{s}_{i}})=\frac{Item\_Sim({{s}_{0}},{{s}_{i}})}{\sum\limits_{{{s}_{j}}\in {{S}_{cu}}}{Item\_Sim({{s}_{0}},{{s}_{j}})}}$ (9)

其中Fu(c,si)是通过轮盘赌博[11]选择相似项目,即相似度较高的项目更可能被选中。

停止的概率φu,k,sim,Tr受当前节点u与目标用户u0相似度,目标物品s0与用户u评分过的物品相似度影响。另外,当前用户与上一节点用户u′信任度也将作为重要参考因素,用户信任度越高,该用户的评分越有参考价值,停止的概率越大。同时,随着在信任网络游走深度的增加,引入噪声的概率也越大,随机游走停止的概率φu,k,sim,Tr也应该越大。因此,综合以上考虑,将φu,k,sim,Tr定义为:

$\begin{align} & {{\phi }_{{u}',k,sim,Tr}}=t{{r}_{{{u}_{0}},{u}'}}_{,c}\times \frac{\underset{{{s}_{j}}\in {{S}_{{{u}'}}}}{\mathop{\max }}\,\{item\_sim({{s}_{0}},{{s}_{j}})\}}{1+{{e}^{-\frac{k}{2}}}} \\ & \text{ }\times Sim({{u}_{0}},{u}') \\ \end{align}$ (10)

其中:tr(u,u′,c)为式(8)中用户融合信任度的计算方法;User_Sim(u0,u)为计算用户相似度的方法;item_sim(s0,sj)表示物品相似度;,k表示当前游走的深度。

根据“六度分割理论”[12-13],本文将游走步数上限设为6步,更符合现实社会网络。随着游走深度的增加,噪声数据的概率也不断增大,因此限制游走步数有助于提高推荐效果。

2) 相反地,以1-φu,k,sim,Tr的概率继续游走,从当前用户u的融合信任邻居中选择下一步的游走目标

TrustWalker从当前节点直接信任用户中随机选择作为下一步游走节点,这意味着用户u的信任用户被选择的概率是相同的。然而这些用户对评分预测有不同的参考价值,为了区分不同用户对推荐的权重,定义选择下一步节点v的概率计算方法:

$P(v)=\frac{t{{r}_{u,v,c}}}{\sum\limits_{\omega \in T{{r}_{u}}}{t{{r}_{u,\omega ,c}}}}$ (11)

其中,w:(u,w)∈T表示u的信任邻居用户。从节点u选择下一节点时,须从用户u 信任邻居中选取。tr(u,v,c)为式(8)中计算用户u、v 信任度的方法。从式(11)可以看出,用户u的信任邻居v作为下一游走节点的概率为两者信任度占用户u所有信任邻居信任度之和的比值,融合信任度包含了用户相似度以及权威信任,使得选择节点更加合理,准确。

2.2 评分预测

PtTrustWalker模型通过多次游走得到稳定的预测结果。最终的预测结果是通过聚合每次游走结果计算的值,其计算方法如下:

${{r}_{{{u}_{0}},s}}=\frac{1}{n}\sum\limits_{i=1}^{n}{{{r}_{i}}}$ (12)

其中:ri为每趟随机游走结果;n为游走次数。模型预测结果是多次随机游走执行结果的平均值。

PtTrustWalker模型为获得稳定的预测结果,需要进行一定次数的随机游走,最终可以通过计算预测值方差σ2来说明预测结果已经稳定且符合评分预测需要。其计算公式如下:

$\sigma _{i}^{2}=\frac{1}{i}\sum\limits_{j=1}^{i}{({{r}_{j}}-\overline{r}}{{)}^{2}}$ (13)

其中:rj为此次随机游走的结果;i为当前游走的次数。σi2表示在执行i次随机游走后预测结果的方差。由式(13)可知,σ2最终趋近于一个固定的值,表示预测结果已经稳定。本文设定当|σi+12-σi2|≤ε 时游走停止,结束预测。实验中设定ε=0.0001。

3 实验结果及分析 3.1 实验设计

本文使用数据集为Epinions数据集[3],数据来自真实世界Epinions网站,数据量非常巨大且具有冷启动和稀疏性问题,数据集的具体信息如表 1所示。

表 1 数据集信息

该数据集有49290个用户,系统中有139738个不同的项目被评分过,总评分数次数为664824次,其用户评分矩阵密度不足0.01%。每个用户平均有13.4条评分记录。信任数据集中,总信任关系数为487181条,每个用户平均有9.9个直接信任邻居。可以看到相比常用的MoiveLens数据集4.25%的数据密度,Epinions更加稀疏,因此,该数据集能在大数据量与高稀疏性下评估模型的推荐效果。将评分少于5条的用户看作冷启动用户[3],在全集用户集和冷启动用户集分别进行实验。本文使用的留一法(Leave-one-out)是评分预测中广泛使用评估模型的方法,保留一条评分信息,用其余信息预测该评分。对PtTrustWalker分别在冷启动用户集和全体用户集中与以下五种方法进行比较:TidalTrust(Tidal)、MoleTrust(Mole)、TrustWalker(TW)、CoTrustWalker(CoTW)和RelevantTrustWalker(RT)模型。

实验使用Intel Core i5 2.5 GHz机器,内存12 GB,操作系统为Win 10系统,算法使用Python 2.7实现。比较算法的参数的设定沿用原文中的参数值,并将物品评分数小于5 的用户看作冷启动用户,PtTrustWalker模型中每趟游走最大深度为6,最大游走失败次数10000。

3.2 实验评估方法

评分预测的预测准确度通常通过均方根误差(Root Mean Squared Error,RMSE)计算,该方法被许多研究所采用。RMSE在测试集N中计算公式为:

$RMSE=\sqrt{\frac{\sum\limits_{{{u}_{0}},{{i}_{0}}}{{{({{r}_{{{u}_{0}},{{i}_{0}}}}-{{{\hat{r}}}_{{{u}_{0}},{{i}_{0}}}})}^{2}}}}{\left| N \right|}}$ (14)

其中,ru0,i0和${{\hat{r}}_{{{u}_{0}},{{i}_{0}}}}$表示目标用户u0对项目i0的评分与预测评分。RMSE值越小说明预测结果越准确。在高稀疏性的测试集中,一些模型可能无法预测所有评分,因此利用覆盖率(coverage)来评估模型来评估模型能够进行预测的用户项目对的比例。

$coverage=S/N$ (15)

其中:S表示模型成功预测的次数;N表示测试集项目评分次数。

利用F-Measure将RMSE和coverage结合成一个单一的评价指标,需将精度误差RMSE转化到[0,1]区间,精确度(precision)和F-Measure的计算公式如下:

$precision=1-\frac{RMSE}{4}$ (16)
$F-Measure=\frac{2\times precision\times coverage}{precision+coverage}$ (17)
3.3 实验结果

图 2展示了将项目分为不同类别数时,PtTrustWalker的RMSE。从图 2可知,项目分为8类时,在实验数据上可取得较好的结果。因此,在下文计算中,将项目分类数取8。

图 2 项目分类数对推荐影响

图 3将展示式(7)用户专家度参数对实验结果的影响,采用RMSE度量结果的准确性。如图 3所示,在测试集中当α=0.6、β=0.4时可以达到最好效果。相比用户评分矩阵,用户信任矩阵相对稠密,提升全局权威度权重可以提高推荐准确度。在下文对比实验中,取α=0.6、β=0.4时的实验结果与其他模型进行比较。

图 3 参数α与β对各数据集的影响

PtTrustWalker等信任增强模型主要是为解决冷启动用户而提出的。因此,本文首先对模型在冷启动用户集上的评价表现进行评估。表 2给出了冷启动用户的比较结果。

表 2 冷启动用户集实验结果

表 2的实验结果中,观察到PtTrustWalker在冷启动用户集中相比其他算法有着较高的精确度。由于引入了用户之间的信任关系,TidalTrust和MoleTrust可以利用信任关系对冷启动用户进行推荐,但未提高推荐精度。TrustWalker、CoTrustWalker、RelevantTrustWalker模型引入随机游走策略,相比TidalTrust和MoleTrust模型推荐精度和覆盖率有着明显的提高。相比这三种随机游走方法,PtTrustWalker选择将信任细化,并引入权威度,在游走过程中,选择更信任且在预测项目类别中偏好相似的用户,而不是随机选择。此外CoTrustWalker、PtTrustWalker覆盖率也是最高的,模型利用矩阵分解方法来计算相似度,避免了在稀疏评分矩阵中无法计算相似度的难题。因此,本文提出的PtTrustWalker模型在冷启动用户集下推荐效果优于其他算法。

表 3显示了在全集用户集上几种模型的实验结果对比。相对于冷启动用户实验结果,由于全集用户集的评分信息更为充足,所有算法的效果相对于冷启动用户集推荐效果有着明显提高。从表 3可以看出,信任增强的推荐算法(包括TidalTrust、MoleTrust和TrustWalker)由于在推荐过程中只考虑用户之间的信任,没有考虑用户相似度对推荐的影响,这导致模型推荐精度较低,其覆盖率也不理想。后续的改进模型CoTrustWalker和RelevantTrustWalker,在此基础上结合用户信任度和相似度,提高了推荐准确度。改进模型局限之一在于信任用户的建议并不绝对适用于目标用户,针对该问题本文提出的PtTrustWalker模型引入了权威度,并将用户信任度与相似度细化为不同项目类别下的信任与相似度,改善模型在冷启动情况下的推荐效果的同时提高了模型推荐精度与解释性。因此,本文提出的PtTrustWalker模型在全集用户集下推荐效果优于其他算法。

表 3 全集用户集实验结果

推荐系统的时间成本也是一个重要的评价指标。图 4显示几个信任推荐模型的平均时间成本。相对于TrustWalker和CoTrustWalker随机游走模型,RelevantTrustWalker与PtTrustWalker大幅度减少了推荐耗时。这是因为RelevantTrustWalker与PtTrustWalker在选择游走节点时不是随机地选择目标,而是根据信任度计算下一步节点,这就使得推荐结果更快速地趋向于平稳,提高了模型的计算效率。而相对于RelevantTrustWalker,PtTrustWalker将参考评分项目规定到停止用户中具有最高偏好的项目类中,因此在项目相似度计算过程中,只需计算某一类下的项目相似度,节省了一定的推荐时间。

图 4 模型推荐时间对比结果

随机游走中每次游走的深度为社会网络直径D,在PtTrustWalker模型中,引入“六度分割理论”将D最大值限定为6,更符合社会网络特点并降低噪声数据对推荐的影响。在PtTrustWalker模型每趟游走中,需对用户与邻居的融合信任度以及特定项目类中项目的相似度进行计算。为计算用户信任度需对用户评分和信任邻居进行计算;同理,需要利用用户对项目的评分来计算项目的相似度。总体而言,一次随机游走的时间复杂度如下:

$D\times (\frac{\left| {{E}_{c}} \right|}{\left| {{U}_{c}} \right|}\frac{\left| {{R}_{c}} \right|}{\left| {{U}_{c}} \right|}+\frac{\left| {{R}_{c}} \right|}{\left| {{U}_{c}} \right|}\frac{\left| {{R}_{c}} \right|}{\left| {{S}_{c}} \right|})$ (18)

其中:$\frac{\left| {{E}_{c}} \right|}{\left| {{U}_{c}} \right|}$为用户在项目类c的平均信任邻居数;$\frac{\left| {{R}_{c}} \right|}{\left| {{U}_{c}} \right|}$为用户对类c中项目的平均评分次数;$\frac{\left| {{R}_{c}} \right|}{\left| {{S}_{c}} \right|}$为项目类c平均被评分次数。评分预测的复杂度是t倍的单次游走复杂度,其中 t是PtTrustWalker模型预测结果稳定时游走次数。

4 结语

在解决大型数据集个性化推荐问题上,本文有三个出发点:1)解决冷启动用户推荐问题;2)解决高维稀疏评分矩阵推荐问题;3)是解决如何有效信任为用户推荐的问题。为解决问题1),本文在TrustWalker模型上提出了一种基于用户偏好的信任推荐方法,TrustWalker本身就是为解决冷启动用户推荐所提出的算法。本文在此基础上,在游走过程中选择偏好更相似,信任度更高的目标节点,使得每一次选择走向更相似的用户。实验证明这一改进是有效的,并提高了模型的易解释性。对于问题2),利用矩阵分解,在高维稀疏评分矩阵下可以高效精确地计算相似度。而对于问题3),由于信任用户与目标用户的偏好差异会使推荐精度降低,本文将项目聚类并得到用户偏好,在此基础上利用权威度和局部信任度等手段将信任度细化,在游走中利用类信任度,预测中参考停留用户高偏好类中相似度较高物品进行预测,提高了算法的解释性和推荐精度。通过实验表明,该方法能在现有的社会网络中直接应用,具有较好的准确度和实时性。本文在计算用户信任时,仅考虑了用户兴趣度这一上下文信息,而上下文环境包括时间、位置、情绪等内容。文中未考虑时间因素对用户信任关系的影响,用户之间的信任关系会随着时间推移发生变化。同理,用户对项目的评分也是对时间因素敏感的,过时的评分信息会成为干扰推荐的噪声。因此,利用多维度上下文信息来增强推荐质量和用户满意度将是我们下一步的工作。

参考文献
[1] GOLDBERG D, NICHOLS D, OKI B M, et al. Using collaborative filtering to weave an information tapestry[J]. Communications of the ACM, 1992, 35 (12) : 61-70. doi: 10.1145/138859.138867
[2] GOLBECK J A. Computing and applying trust in Web-based social networks[C]//College Park, MD:University of Maryland-College Park, 2005:199.
[3] MASSA P, AVESANI P. Trust-aware recommender systems[C]//RecSys'07:Proceedings of the 2007 ACM Conference on Recommender Systems. New York:ACM, 2007:17-24.
[4] JAMALI M, ESTER M. TrustWalker:a random walk model for combining trust-based and item-based recommendation[C]//KDD'09:Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mmining. New York:ACM, 2009:397-406.
[5] 朱丽中, 徐秀娟, 刘宇. 基于项目和信任的协同过滤推荐算法[J]. 计算机工程, 2013, 39 (1) : 58-62. ( ZHU L Z, XU X J, LIU Y. Collaborative filtering recommendation algorithm based on item and trust[J]. Computer Engineering, 2013, 39 (1) : 58-62. )
[6] DENG S G, HUANG L T, XU G H. Social network-based service recommendation with trust enhancement[J]. Expert Systems with Applications, 2014, 41 (18) : 8075-8084. doi: 10.1016/j.eswa.2014.07.012
[7] KOREN Y, BELL R, VOLINSKY C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42 (8) : 30-37. doi: 10.1109/MC.2009.263
[8] 张碧云.基于二分图的聚类推荐算法研究[D].广州:华南理工大学,2014:27-30. ( ZHANG B Y. Recommendation algorithm research based on clustering in bipartite graph[D]. Guangzhou:South China University of Technology, 2014:27-30. )
[9] GUO G, ZHANG J, THALMANN D, et al. From ratings to trust:an empirical study of implicit trust in recommender systems[C]//SAC'14:Proceedings of the 29th Annual ACM Symposium on Applied Computing. New York:ACM, 2014:248-253.
[10] GOLDBAUM D. Follow the leader:simulations on a dynamic social network[EB/OL].[2016-01-06]. http://www.uts.edu.au/sites/default/files/edg_wp15.pdf.
[11] LIPOWSKI A, LIPOWSKA D. Roulette-wheel selection via stochastic acceptance[J]. Physica A:Statistical Mechanics and its Applications, 2012, 391 (6) : 2193-2196. doi: 10.1016/j.physa.2011.12.004
[12] WATTS D J. Six degrees:the science of a connected age[EB/OL].[2016-02-03]. http://www.gbv.de/dms/goettingen/353198986.pdf.
[13] JAMALI S. Probabilistic models for recommendation in social networks[D]. Burnaby, British Columbia:Simon Fraser University, 2013:61-63.