2. 淮海工学院 计算机工程学院, 江苏 连云港 222001
2. School of Computer Engineering, Huaihai Institute of Technology, Lianyungang Jiangsu 222001, China
近年来,随着诸如Twitter、Facebook等社交媒体的兴起,现实世界中人与人之间构建起来的社交关系已经慢慢迁移到了这些社交网站中。与现实生活相似,社会网络中自己所信任的朋友推荐的物品更容易被人们所采纳,这是因为相互信任的朋友之间具有相似的兴趣爱好。基于信任关系进行社会网络推荐,可以有效解决传统推荐系统中的数据稀疏问题与用户冷启动问题等问题,从而提高社会网络推荐的精准度。
目前,以信任关系为基础来进行社会网络推荐的算法有很多,但多数侧重于研究如何进行准确的信任度计算和信任模型的推理,如通过多种相似度度量方法的线性组合对用户进行推荐预测[1],通过对用户信任关系矩阵和原始评分矩阵的概率分解提出基于受限关系和概率分解矩阵的推荐方法[2],在用户兴趣关系建模过程中通过进一步识别出与目标用户存在共同爱好的朋友来优化信任度求解的过程[3-4]、通过将多种目标函数进行整合,并在矩阵分解的框架下进行求解[5-6]。
现有的信任网络推荐技术多数是利用用户间的社会信任关系进行推荐,而忽略了社会网络中的新用户。由于新用户缺乏历史评分信息,因此无法为新用户提供有效准确的信息推荐。为了解决新用户信任度计算问题[7-10],本文首先提出一种面向新用户的信任度计算方法,解决了信任网络中的用户信任传递问题;随后通过结合用户评价与社会化网络两项要素,构建一种全新的以信任关系为基础的社会网络推荐(Trust-based Social Recommendation, TSR)方法。该方法利用朋友的信任矩阵对用户自身的特征向量进行修正,解决了用户特征向量的精准构建及信任传递问题。实验结果表明,与传统的协同推荐算法相比,本文提出的新型算法性能得到显著提升,尤其在用户评分不足甚至是缺乏评分的条件下,该算法仍然能取得较高的推荐性能。
1 问题定义 1.1 信任网络的形式化定义定义 1 信任网络。由代表用户的节点和节点之间的信任关系构成的一个有向带权图G来形式化表示,记为G=(V, E, B)。其中:信任网络的顶点集合用V代表,顶点之间的边集合用E代表,节点之间的信任度集合用B代表。
在社会网络这一环境下,信任网络通常由用户间复杂的信任关系构成。信任度是信任网络中的重要概念,合理和高效的信任度计算是建立准确的信任网络的前提条件,下面给出信任度的定义:
定义 2 信任度。在信任网络G这一环境里,节点i对节点j的信任程度的量化构成了信任度,用符号B(i, j)表示。bi, j∈[0,1]表示用户之间信任关系的强度:1表示完全信任,0表示完全不信任。
社会网络环境中,用户所信赖的朋友为其推荐的产品总是更容易被用户所接受,并且用户之间的信任关系越强,受其朋友影响的可能性就越大。本文把这种方法称为基于信任关系的社会化推荐,它实质上是一种利用用户之间信任关系而进行推荐的方法。
定义 3 基于信任关系的推荐。设用户ui对uj的信任度用bij表示,且对商品vk评分为rik的概率表示为yui, uj, vk:=η(UiTQj, UiTVk),其中Ui、Vk、Qj分别表示用户特征向量、商品特征向量和信任特征向量。用户特征向量与信任特征向量的内积UiTQj可以求得用户信任权重,另外可以根据用户特征向量与商品特征向量的内积UiTVk从而求出用户-项目评分rik;用户信任关系矩阵和用户商品矩阵的联合函数用η(·)表示,则基于信任关系的推荐问题可描述为用户商品矩阵中的Top-N 问题:
$Top({u_i},{\rm{ }}N): = \mathop {{\rm{arg max}}}\limits_{{v_k} \in V,{u_j} \in U}^N {y_{{u_i},{\rm{ }}{u_j},{\rm{ }}{v_k}}}$ | (1) |
本文通过概率矩阵分解(Probabilistic Matrix Factorization, PMF)方法[11]对信任关系中的用户特征进行提炼,并在此基础上对信任关系进行建模。通过对信任关系应用矩阵分解,求解出能够表示用户之间信任关系的主要因素,即生成一个低维的用户潜在特征向量。
假设G=(V, E, B)表示信任关系网络,B={bij}表示用户间信任关系矩阵(m×m)。U∈Rl×m表示应用矩阵分解推导出来的用户特征矩阵,与其对应的潜在特征向量用列向量Ui来表示。由于PMF假设可观测信任值是由概率线性模型UiUk和高斯观测噪声组成的,因此信任关系矩阵C的条件概率分布定义如下:
$p(\mathit{\boldsymbol{C}}|\mathit{\boldsymbol{U}},{\rm{ }}\sigma _c^2) = \prod\limits_{i = 1}^m {\prod\limits_{k = 1}^m {{{[N({c_{ik}}g(\mathit{\boldsymbol{U}}{{_i^{\rm{T}}}_i}{\mathit{\boldsymbol{U}}_k}),{\rm{ }}\sigma _c^2)]}^{I_{ik}^c}}} } $ | (2) |
N(x|μ, σ2)的含义为参数x服从均值μ、方差σ的高斯分布。Iik c为属于指示函数,其值0与1分别表示用户ui不信任或信任用户uk。函数g(x)是逻辑回归函数g(x)=1/(1+exp(-x))。假设用户的特征矩阵服从均值为0的球形高斯先验:
$p(\mathit{\boldsymbol{U}}\sigma _\mathit{\boldsymbol{U}}^2) = \prod\limits_{i = 1}^m {} {\rm N}({\mathit{\boldsymbol{U}}_i}|0,\sigma _\mathit{\boldsymbol{U}}^2\mathit{\boldsymbol{I}})$ | (3) |
式(3) 经过贝叶斯推断,可以得到:
$\begin{array}{l} P(\mathit{\boldsymbol{U}}|\mathit{\boldsymbol{C}},{\rm{ }}\sigma _\mathit{\boldsymbol{C}}^2,\sigma _\mathit{\boldsymbol{U}}^2) \propto p(\mathit{\boldsymbol{C}}|\mathit{\boldsymbol{U}},{\rm{ }}\sigma _\mathit{\boldsymbol{C}}^2)P(\mathit{\boldsymbol{U}}\sigma _\mathit{\boldsymbol{U}}^2) = \\ \prod\limits_{i = 1}^m {\prod\limits_{k = 1}^m {{{[{\rm N}({c_{ik}}g(\mathit{\boldsymbol{U}}_i^{\rm{T}}{\mathit{\boldsymbol{U}}_k}),{\rm{ }}\sigma _c^2)]}^{I_{ik}^c}}} } \times \prod\limits_{i = 1}^m {{\rm N}({\mathit{\boldsymbol{U}}_i}|0,\sigma _\mathit{\boldsymbol{U}}^2\mathit{\boldsymbol{I}})} \end{array}$ | (4) |
式(4) 给出的方法中,只通过用户间的信任关系来估计用户的特征。文献[12]中提出了联合用户信任关系B与用户-项目评分矩阵R的概率分解模型,即SocialMF方法,但该方法未全面考虑到不可信节点会极大影响推荐准确性这一实际问题。为了切实提高推荐系统的精度,必须对不可信节点进行弱化或者消除,通过降低其权重的方面降低其对推荐系统的影响作用。
本文提出的系统优化方法主要有以下工作:对网络中的新用户进行初始信任的赋值,构建新用户的信任推荐模型;然后对用户信任关系所构成的矩阵进行因式分解等科学处理,并借助社会正则化项引入到原始目标函数中实现对误差函数的约束,从而实现基于可信度的社会网络推荐。
2 新用户的信任推荐模型现有的基于二值信任网络的推荐方法都是假定被同一用户信任的不同朋友对其产生的影响是相同的;然而,现实世界中,人们之间建立起来的关系强度是不同的。有一些关系可能是强大的,如亲密的朋友关系;而有些关系可能是微弱的,如熟人关系。因此,基于信任关系进行推荐时,就需要区别对待不同关系的影响作用。其次,进行用户关系模型构建时,现有的方法大多只考虑了显性的社会信任信息,而忽视了其他社会网络维度信息的影响,而一些其他类型的关系可以被利用,如用户的标签信息、上下文信息等。
为了区分用户之间的信任程度,对在信任评估中起关键作用的两个因素进行了定义:能力度与可信度,并使用这两个维度进行社会信任关系的评估:
能力度 指在多大程度上被信任者能被认为有能力提供正确的推荐。它反映了被信任者的能力或专业知识水平的高低程度。
受信度 指在多大程度上被信任者被其直接邻居认为是可信的亲密朋友。
2.1 能力度如果被信任者可以随时提供准确预测并表现出高度的灵活性,则可认为他/她是一个具有较高能力度的人。基于这一假设,被信任者推荐产品的准确率很大程度上决定了被信任者的推荐能力。
对于被信任者v,他/她给其信任者u的推荐用三元组〈u, v, i〉来表示,其中i表示由信任者u和被信任者v评分的项目,用RecSet(v)表示用户v推荐给其所信任用户的推荐集合,其定义如下:
$\begin{array}{l} RecSet\left( v \right) = \\ \left\{ {\left\langle {u,v,i} \right\rangle |\forall u \in B,v \in {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }}_{\left( u \right)}},{r_{u,i}} > 0,{r_{v,i}} > 0} \right\} \end{array}$ | (5) |
其中Γ(u)表示用户u的直接邻居集合。文献[7]中对正确的推荐给出了定义,即当且仅当用户v对项目i的推荐评分rv, i非常接近目标用户u对项目i的实际评分ru, i时才是一个正确的推荐,因此采用如下的公式对其进行定义:
$Correc{t_{u,v,i}} = \left\{ \begin{array}{l} 0,\left| {{r_{u,i}} - {r_{v,i}}} \right| > \varepsilon \\ 1,{\rm{ }}\left| {{r_{u,i}} - {r_{v,i}}} \right| \le \varepsilon \end{array} \right.$ | (6) |
其中实数ε表示阈值。用CorSet(v)表示由用户v作出的正确的推荐集合,其定义如下:
$\begin{array}{l} CorSet\left( v \right) = \\ \left\{ {\left\langle {u,v,i} \right\rangle \in RecSet\left( v \right)|Correc{t_{u,v,i}} = 1} \right\} \end{array}$ | (7) |
另外,能力度不仅要考虑用户的正确推荐能力,还要考虑其评价的次数。因为对于那些评价过多次均能取得很高的准确率的用户应该具有更高的能力度,因此为了防止那些只评价过一次就获得很高能力度的情况,本文将引入一个评分活跃因子来权衡用户以往评分的活跃程度。用Iv表示为由用户v评定的项目数量,用avg表示推荐系统中所有用户平均评分项数目。对于被信任者v,其评分活跃因子βv定义如下:
${{\beta }_{v}}=\left\{ \begin{matrix} \left| {{I}_{v}} \right|/avg, & \left| {{I}_{v}} \right|<avg \\ 1, & 其他 \\ \end{matrix} \right.$ | (8) |
最终,用户的推荐能力度Comp(v)计算公式为:
$Comp\left( v \right) = {\beta _v}\frac{{\left| {CorSet\left( v \right)} \right|}}{{\left| {RecSet\left( v \right)} \right|}}$ | (9) |
受信度是指被信任者在多大程度上被其直接邻居认为是可信的亲密朋友。如同在学术文献中的引用,如果某篇文章被引的次数非常多,可以直观地认为该文具有相对较高的质量。基于这样的假设,可以认为在信任网络中受到很多人信任的用户会比被少数人所信任的用户更值得信赖。信任者u对被信任者v的受信度TW(u, v)可用如下公式计算:
$TW\left( {u,v} \right) = \sqrt {\frac{{d_{\left( v \right)}^ - }}{{d_u^ + + d_{\left( v \right)}^ - }}} \times b_{uv}^*$ | (10) |
其中:d(v)-表示用户v在社会信任网络的入度,d(u)+表示用户u在社会信任网络的出度,buv*表示用户之间的信任度。通过上式可以实现被越多人所信任的用户,其受信度将会被提升。
2.3 最终信任度用户的能力度与受信度计算完成之后,可以利用它们完成最终的信任值计算。社会信任网络中,信任者u对被信任者v赋予的信任值为:
$b_{uv}^{*}=\left\{ \begin{array}{*{35}{l}} \begin{matrix} 0.5*TW\left( u,v \right), & Comp\left( v \right)=0 \\ \end{matrix} \\ (1-Comp\left( v \right)\left( 1-TW\left( u,v \right) \right), \\ \begin{matrix} & \begin{matrix} Comp\left( v \right)>0 & \text{and} & TW\left( u,v \right)=0 \\ \end{matrix} \\ \end{matrix} \\ \end{array} \right.$ | (11) |
该值越大表明用户之间具有越高的信任度。如果用户被认为是可信的但不专业(当能力度为0,受信度不为0时),表示其给出的推荐精准率不高,则其最终的信任值将被减弱,可以将其设置为受信度的一半。初始没有邻居用户,也没有与任何用户产生信任交互,对于这些没有添加用户到其社会列表中的用户,称为冷启动用户。这些用户没有历史的评分信息,也没有信任用户的推荐信息,因此无法用传统的推荐方法进行解决。本文的具体做法是:选择一些能力度较高的用户作为冷启动用户的初始邻居集合。通过最终信任值的修正,不仅使社会网络的信任关系更加合理与精准,更重要的是解决了新用户的信任值计算问题,大幅度提高了推荐系统的准确度。
3 基于可信度的推荐模型社会关系网络中,邻居节点Γ(u)常常会对用户u的行为与喜好产生影响,因此来自用户所信任好友的推荐则更容易被用户所接受。也就是说,相邻节点v∈Γ(u)会对用户u的潜在特征向量产生特定影响。该影响作用可以用如下公式进行表示:
${{\mathit{\boldsymbol{\hat U}}}_u} = \sum\limits_{v \in \mathit{\Gamma }(u)} {b_{uv}^*{\mathit{\boldsymbol{U}}_v}} $ | (12) |
其中:
$\left( {\begin{array}{*{20}{c}} {{{\hat U}_{u,1}}}\\ {{{\hat U}_{u,2}}}\\ \vdots \\ {{{\hat U}_{u,m}}} \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {{U_{1,1}}} & {{U_{2,1}}} & \cdots & {{U_{n,1}}}\\ {{U_{2,1}}} & {{U_{2,2}}} & \cdots & {{U_{n,2}}}\\ \vdots & \vdots & & \vdots \\ {{U_{1,K}}} & {{U_{2,K}}} & \cdots & {{U_{n,m}}} \end{array}} \right)\left( {\begin{array}{*{20}{c}} {b_{u,1}^*}\\ {b_{u,2}^*}\\ \vdots \\ {b_{u,n}^*} \end{array}} \right)$ | (13) |
这里虽然考虑了社会网络中朋友的喜好可以影响用户特征向量的构建,但这并不会改变用户-项目评分矩阵R的条件概率分布,并且用户u的特征向量可以反映其所信任朋友特征向量的条件概率分布,即:
$\begin{array}{l} p\left( {\mathit{\boldsymbol{U}}|\mathit{\boldsymbol{B}},\sigma _\mathit{\boldsymbol{U}}^2,\sigma _\mathit{\boldsymbol{B}}^2} \right) \propto p\left( {\mathit{\boldsymbol{U}}|\sigma _\mathit{\boldsymbol{U}}^2} \right)P\left( {\mathit{\boldsymbol{U}}|\mathit{\boldsymbol{B}},\sigma _\mathit{\boldsymbol{B}}^2} \right) = \\ \prod\limits_{i = 1}^m {N\left( {{\mathit{\boldsymbol{U}}_i}|0,\sigma _U^2\mathit{\boldsymbol{I}}} \right)} \times \prod\limits_{i = 1}^m {N\left( {{\mathit{\boldsymbol{U}}_i}|\sum\limits_{k \in \mathit{\Gamma }\left( i \right)} {b_{ik}^*{\mathit{\boldsymbol{U}}_k},\sigma _c^2\mathit{\boldsymbol{I}}} } \right)} \end{array}$ | (14) |
上式可以看作是两个正态分布的乘积因此结果仍然符合正态分布,这样即可以保证用户特征向量不会太大并且与其邻居节点的特征向量非常相近。
同样为了防止过拟合,对于项目特征向量也假设服从均值为0的高斯分布,即:
$p(\mathit{\boldsymbol{V}}|\sigma _\mathit{\boldsymbol{V}}^2) = \prod\limits_{j = 1}^n {N({\mathit{\boldsymbol{V}}_j}|0,{\rm{ }}\sigma _\mathit{\boldsymbol{V}}^2\mathit{\boldsymbol{I}})} $ | (15) |
运用贝叶斯推理可知:
$\begin{array}{l} p(\mathit{\boldsymbol{U}},\mathit{\boldsymbol{V|R}},\mathit{\boldsymbol{B}},{\rm{ }}\sigma _\mathit{\boldsymbol{B}}^2,{\rm{ }}\sigma _\mathit{\boldsymbol{U}}^2,{\rm{ }}\sigma _\mathit{\boldsymbol{V}}^2) \propto \\ p(\mathit{\boldsymbol{R}}|\mathit{\boldsymbol{B}},{\rm{ }}\mathit{\boldsymbol{U}},{\rm{ }}\mathit{\boldsymbol{V}},{\rm{ }}\sigma _\mathit{\boldsymbol{B}}^2)p(U|B,{\rm{ }}\sigma _\mathit{\boldsymbol{U}}^2)p(\mathit{\boldsymbol{V}}|\mathit{\boldsymbol{B}},{\rm{ }}\sigma _\mathit{\boldsymbol{V}}^2) \end{array}$ | (16) |
仍然假设B与低维矩阵U和V是相互独立的,则上式可表示为:
$\begin{array}{l} p(\mathit{\boldsymbol{U}},\mathit{\boldsymbol{V|R}},\mathit{\boldsymbol{B}},\sigma _R^2,\sigma _B^2,\sigma _U^2,\sigma _V^2) \propto \\ p(\mathit{\boldsymbol{R|U}},\mathit{\boldsymbol{V}},\sigma _R^2)p(\mathit{\boldsymbol{U|B}},{\rm{ }}\sigma _B^2,{\rm{ }}\sigma _U^2)p(\mathit{\boldsymbol{V}}\sigma _V^2) = \\ \prod\limits_{i = 1}^m {\prod\limits_{j = 1}^n {{{[N({\mathit{\boldsymbol{R}}_{ij}}|g(\mathit{\boldsymbol{U}}_i^{\rm{T}}{\mathit{\boldsymbol{V}}_j}),{\rm{ }}\sigma _R^2)]}^{I_{ij}^R}}} } \times \\ \prod\limits_{i = 1}^m {N({\mathit{\boldsymbol{U}}_i}|\sum\limits_{k \in {\mathit{\Gamma }_{(i)}}} {b_{ik}^*{\mathit{\boldsymbol{U}}_k},\sigma _B^2\mathit{\boldsymbol{{\rm I}}}} )} \times \\ \prod\limits_{i = 1}^m {N({\mathit{\boldsymbol{U}}_i}|0,\sigma _U^2\mathit{\boldsymbol{{\rm I}}})} \times \prod\limits_{j = 1}^n {N({V_j}|0,{\rm{ }}\sigma _V^2\mathit{\boldsymbol{{\rm I}}})} \end{array}$ | (17) |
其中:p(U|σU2)与p(VσV2)分别表示用户与项目特征矩阵仍然假设服从均值为0的球形高斯先验。式(12) 可以理解为仅依靠用户所信任朋友的品味进行推荐。通过该模型,可以很好地解决信任冷启动问题。
给定上述推荐模型后,其对数联合后验概率分布可以表示为:
$\begin{array}{l} \ln p(\mathit{\boldsymbol{U}},{\rm{ }}\mathit{\boldsymbol{V|R}},{\rm{ }}\mathit{\boldsymbol{B}},{\rm{ }}\sigma _R^2,{\rm{ }}\sigma _B^2,{\rm{ }}\sigma _U^2,{\rm{ }}\sigma _V^2) = \\ - \frac{1}{{2\sigma _R^2}}\prod\limits_{i = 1}^m {\prod\limits_{j = 1}^n {I_{ij}^R{{({\mathit{\boldsymbol{R}}_{ij}} - g(\alpha {\mathit{\boldsymbol{U}}_i}^{\rm{T}}{\mathit{\boldsymbol{V}}_j}))}^2}} } - \frac{1}{{2\sigma _U^2}}\sum\limits_{i = 1}^m {U_i^{\rm{T}}{U_i}} - \\ \frac{1}{{2\sigma _V^2}}\sum\limits_{j = 1}^n {\mathit{\boldsymbol{V}}_j^{\rm{T}}{\mathit{\boldsymbol{V}}_j}} - \frac{1}{{2\sigma _B^2}}\sum\limits_{i = 1}^m {({{({U_i} - \sum\limits_{k \in {\mathit{\Gamma }_{(i)}}} {b_{ik}^*{\mathit{\boldsymbol{U}}_k}} )}^{\rm{T}}}({\mathit{\boldsymbol{U}}_i}} - \\ \sum\limits_{k \in {\mathit{\Gamma }_{(i)}}} {b_{ik}^*{\mathit{\boldsymbol{U}}_k}} )) - \frac{1}{2}(\sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {I_{ij}^R} } )\ln \sigma _R^2 - \frac{1}{2}(ml\ln \sigma _U^2 + \\ nl\ln \sigma _V^2 + ml\ln \sigma _B^2) + \varepsilon \end{array}$ | (18) |
其中:ε为与参数无关的常数。在参数U、V固定时,求解上式对数后验概率的最大值问题可以转换为对以下带二次正则项的误差平方和函数求最小值问题:
$\begin{array}{l} E\left( {\mathit{\boldsymbol{U}},\mathit{\boldsymbol{V}},\mathit{\boldsymbol{R}},\mathit{\boldsymbol{B}}} \right) = \frac{1}{2}\prod\limits_{i = 1}^m {\prod\limits_{j = 1}^n {I_{ij}^R} } {({\mathit{\boldsymbol{R}}_{ij}} - g(\mathit{\boldsymbol{U}}_i^{\rm{T}}{\mathit{\boldsymbol{V}}_j}))^2} + \\ \frac{{{\mathit{\boldsymbol{\lambda }}_U}}}{2}\sum\limits_{i = 1}^m {\mathit{\boldsymbol{U}}_i^{\rm{T}}{\mathit{\boldsymbol{U}}_i}} + \frac{{{\mathit{\boldsymbol{\lambda }}_V}}}{2}\sum\limits_{j = 1}^n {\mathit{\boldsymbol{V}}_j^{\rm{T}}{\mathit{\boldsymbol{V}}_j}} + \frac{{{\mathit{\boldsymbol{\lambda }}_B}}}{2}\sum\limits_{i = 1}^m {(({\mathit{\boldsymbol{U}}_i} - } \\ \sum\limits_{k \in {\mathit{\Gamma }_{(i)}}} {b_{ik}^*{\mathit{\boldsymbol{U}}_k}} {)^{\rm{T}}}({\mathit{\boldsymbol{U}}_i} - \sum\limits_{k \in {\mathit{\Gamma }_{(i)}}} {b_{ik}^*{\mathit{\boldsymbol{U}}_k}} )) \end{array}$ | (19) |
其中λU=σR2/σU2,λV=σR2/σV2,λB=σR2/σB2,‖·‖F2表示Frobenius范数。
对于目标函数E(式(20) 所示)求解局部最小值,可以通过对所有用户和项目在Ui和Vj上使用梯度下降法获得局部极小值:
$\left\{ \begin{array}{l} \frac{{\partial \mathit{\boldsymbol{E}}}}{{\partial {\mathit{\boldsymbol{U}}_i}}} = \sum\limits_{j = 1}^n {I_{IJ}^Rg'(\mathit{\boldsymbol{U}}_i^{\rm{T}}{\mathit{\boldsymbol{V}}_j})(g(\mathit{\boldsymbol{U}}_i^{\rm{T}}{\mathit{\boldsymbol{V}}_j}) - {\mathit{\boldsymbol{R}}_{ij}}){\mathit{\boldsymbol{V}}_j} + {\mathit{\boldsymbol{\lambda }}_U}{\mathit{\boldsymbol{U}}_i}} + \\ {\mathit{\boldsymbol{\lambda }}_B}({\mathit{\boldsymbol{U}}_i} - \sum\limits_{k \in {\mathit{\Gamma }_i}} {b_{ik}^*{\mathit{\boldsymbol{U}}_k})} - {\lambda _B}\sum\limits_{\{ k|i \in {\mathit{\Gamma }_k}} {b_{ik}^*({\mathit{\boldsymbol{U}}_k} - \sum\limits_{g \in {\mathit{\Gamma }_k}} {b_{gk}^*{\mathit{\boldsymbol{U}}_g}} )} \\ \frac{{\partial \mathit{\boldsymbol{E}}}}{{\partial {\mathit{\boldsymbol{V}}_j}}} = \sum\limits_{i = 1}^m {I_{ij}^R} g'(\mathit{\boldsymbol{U}}_i^{\rm{T}}{\mathit{\boldsymbol{V}}_j})(g(\mathit{\boldsymbol{U}}_i^{\rm{T}}{\mathit{\boldsymbol{V}}_j}) - {\mathit{\boldsymbol{R}}_{ij}}){\mathit{\boldsymbol{U}}_i} + {\mathit{\boldsymbol{\lambda }}_V}{\mathit{\boldsymbol{V}}_j} \end{array} \right.$ | (20) |
其中:g′(x)为函数g(x)的导数,B(x)表示所有信任用户ui的用户集合。为了减少算法的复杂度,令λU=λV。
4 实验评估 4.1 数据集与评价指标实验选择两个公开的产品评论网站数据作为本次实验的数据集:Epinions和MovieLens数据集。这两个网站中,用户不仅可以对不同产品进行打分,而且还可以写下有关商品的评论信息。此外,用户还可以评价其他用户发表的评论,并将其信任的用户加入到其“信任列表”中。MovieLens数据集中包含了大量的社会标签信息,该数据集包含10 000 054条评分信息和95 580条标记信息,是由71 567名用户对10 681部电影标注产生的。
实验选取的测试集比重分别为10%、30%、50%、80%。MovieLens 10 M/100 M数据集中随机选择80%作为训练集,20%作为测试集。每次验证都被独立执行多次,最终取平均值。实验具体以平均绝对误差(Mean Absolute Error, MAE)、均方根误差(Root Mean Square Error, RMSE)等为系统评估指标,对各个推荐系统的性能进行对比。
MAE是所有单个观测值与算术平均值的偏差的绝对值,该值越小,表明推荐算法的性能越好,其定义如下:
$MAE = (\sum\limits_{i,j} {\left| {{r_{i,j}} - {{\bar r}_{i,j}}} \right|} )/N$ | (21) |
ri,j表示用户i为项目j作出的具体评分,ri, j表示应用推荐算法计算得到的预测评分,N表示观测评分的个数。
RMSE表示观测值与真值偏差的平方与观测次数N比值的平方根,该值越小,表明推荐算法的性能越好,其定义如下:
$RMSE = \sqrt {(\sum\limits_{i,j} {{{({r_{i,j}} - {{\bar r}_{i,j}})}^2})/N} } $ | (22) |
URMSE(User Root Mean Square Error)用来评估推荐算法对不同用户的推荐效果,其定义如下:
$URMSE = \left( {\sum\limits_{{u_k} \in U} {\sqrt {\sum\limits_{i = 1}^{{n_k}} {{{({r_{i,j}} - {{\bar r}_{i,j}})}^2}/{n_k}} } } } \right)/\left| U \right|$ | (23) |
其中:nk表示第k个用户需要预测的评价数量,|U|表示用户总数。
4.2 参数影响实验在TSR推荐模型中,参数λB是用于平衡来自用户-项目评分矩阵和用户信任关系的信息比例。如果λB取值为0,表示仅依靠用户评分矩阵信息进行推荐;反之,当λB取无穷大时,表示推荐模型在推荐时仅依赖于用户的信任关系矩阵进行用户喜好的预测。显然,只有联合用户自身的评分信息与信任关系信息才能使推荐效果达到最优。下面通过实验验证参数λB的不同取值对推荐性能的产生影响。
实验中对用户特征矩阵的维度L分别取5和10两种取值,测试集比重分别为20%、50%、80%三种比例,使用MAE衡量λB对推荐效果的影响。表 1给出了参数在用户特征矩阵维度分别为5和10,及其在不同比例测试集下MAE的结果。
由表 1中数据可知,参数λB对算法的推荐性能有着重要的影响,也验证了在推荐时综合考虑用户评分矩阵与信任关系可以大幅度提高推荐性能。随着λB的增大,推荐的准确度逐渐提高,但当λB值继续增大时,推荐性能反而降低。由此可知,参数λB的取值为10的时候,MAE取值最低,算法推荐性能最好;并且对比用户特征矩阵维度分别为5和10下的MAE结果可知,维度为10时的推荐效果更好。这是由于用户特征矩阵越大则对应的用户特征分类越细,从而算法的推荐性能越好,因此最终将参数λB的取值设为10,用户特征矩阵的维度L设为10。
4.3 算法性能对比实验为了验证TSNR算法的有效性,本文利用衡量推荐算法性能所常用的几种算法进行仿真测试,与以下几种算法进行对比,以验证本文所提模型的正确性:
1) UserMean。该方法利用每个用户对项目评分的均值进行用户未评分项的预测。
2) ItemMean。该方法利用每个项目评分的平均值对评分数据进行预测。
3) PMF (Probabilistic Matrix Factorization) [11] 。该算法来自于Salakhutdinov等的研究成果。PMF具体以概率分布的矩阵因式分解为基础,利用用户-项目评分矩阵开展协同推荐计算。
4) NMF ( Non-negative Matrix Factorization) [12]。该方法是由Lee等提出的。NMF是也是一种仅利用评分矩阵信息进行推荐的方法。
5) Trust[13]。该协同推荐算法具体以信任网络为基础,但与本文提出的推荐算法的最大区别在于,该算法并未考虑新用户的信任度计算问题。
6) SocialMF[14]。该算法具体以用户偏好传播为基础进行模型构建,并完成偏好推荐。这种由Jamali等提出的推荐模型也是本文的研究基础,但该算法对新用户的信任度也没有进行初始化。
实验选取的测试集比重分别为10%、30%、50%、80%。算法中用到的参数设置如下:λB=10,用户特征矩阵的维度L=10。λU=λV=0.1。数据稀疏性问题是影响推荐系统有效性的最大因素,历史评分数据的缺乏,则直接影响和限制了推荐系统的性能与效率,因此,为了确定本文所提出的推荐模型在推荐性能上的改进,需要与其他推荐模型进行对比实验验证。
表 2给出了在不同测试集比例下本文所提TSR算法与其他各类推荐算法分别在MAE与RMSE上的对比结果。根据结果可知,TSR算法的性能在MAE与RMSE作为评估指标下均要显著高于SVD、NMF、PMF、SoRec等算法,特别是在训练数据较少的情况下。特别是在像MovieLens这样冷启动用户较多的数据集上本算法的优势更加明显。通过实验结果表明TSR的推荐效果由于考虑了新用户的信任冷启动问题,对新用户的初始信任度进行了合理赋值,因此推荐质量较其他推荐算法都有所提升。
社会网络分析的诸多应用中,对网络节点的可信度进行评估是其中的一项关键技术[15-16]。从朋友推荐这一非常典型的社交网络推荐关系出发,提出一种将关系信任度与用户-项目评分矩阵进行联合矩阵分解的社会化推荐方法,通过朋友的喜好对用户特征向量的构建进行修正,实现了信任传递,从而解决了新用户无信任值的冷启动问题,提高了基于信任度推荐的准确度。实验结果表明TSR方法由于考虑了新用户的信任度初始化问题及信任传递等问题,其推荐质量较其他推荐方法有大幅度的提高。
[1] | BOBADILLA J, ORTEGA F, HERNANDO A, et al. A collaborative filtering approach to mitigate the new user cold start problem[J]. Knowledge-Based Systems, 2012, 26 : 225-238. doi: 10.1016/j.knosys.2011.07.021 |
[2] | 印桂生, 张亚楠, 董宇欣, 等. 基于受限信任关系和概率分解矩阵的推荐[J]. 电子学报, 2014, 42 (5) : 904-911. ( YIN G S, ZHANG Y N, DONG Y X. A contrained trust recommendation using probabilistic matrix factorization[J]. Acta Electronica Sinica, 2014, 42 (5) : 904-911. ) |
[3] | 郭磊, 马军, 陈竹敏. 一种信任关系强度敏感的社会化推荐算法[J]. 计算机研究与发展, 2013, 50 (9) : 1805-1813. ( GUO L, MA J, CHEN Z M. Trust strenth aware social recommendation method[J]. Journal of Computer Research and Development, 2013, 50 (9) : 1805-1813. ) |
[4] | 郭磊, 马军, 陈竹敏, 等. 一种结合推荐对象间关联关系的社会化推荐算法[J]. 计算机学报, 2014, 37 (1) : 219-228. ( GUO L, MA J, CHEN Z M, et al. Incorating item relations for social recommendaiton[J]. Chinese Journal of Computers, 2014, 37 (1) : 219-228. ) |
[5] | NOEL J, SANNER S, TRAN K N, et al. New objective functions for social collaborative filtering[C]//WWW'12:Proceedings of the 21st International Conference on World Wide Web. New York:ACM, 2012:859-868. |
[6] | MASSA P, BHATTACHARJEE B. Using trust in recommender systems:an experimental analysis[EB/OL].[2016-02-04]. https://static.aminer.org/pdf/PDF/000/458/209/using_trust_in_recommender_systems_an_experimental_analysis.pdf. |
[7] | WANG Y, YIN G, CAI Z, et al. A trust-based probabilistic recommendation model for social networks[J]. Journal of Network and Computer Applications, 2015, 55 : 59-67. doi: 10.1016/j.jnca.2015.04.007 |
[8] | MORADI P, AHMADIAN S, AKHLAGHIAN F. An effective trust-based recommendation method using a novel graph clustering algorithm[J]. Physica A:Statistical Mechanics and its Applications, 2015, 436 : 462-481. doi: 10.1016/j.physa.2015.05.008 |
[9] | 龚卫华, 郭伟鹏, 裴小兵, 等. 信任网络中基于节点重要性的层次化划分方法[J]. 浙江大学学报(工学版), 2015, 49 (9) : 1609-1615. ( GONG W H, GUO W P, PEI X B, et al. Hierarchical classification method of trust networks based on nodes importance[J]. Journal of ZheJiang University (Engineering Science), 2015, 49 (9) : 1609-1615. ) |
[10] | VERMA V K, SINGH S, PATHAK N P. Towards comparative evaluation of trust and reputation models over static, dynamic and oscillating wireless sensor networks[J]. Wireless Networks, 2017, 23 (2) : 335-343. doi: 10.1007/s11276-015-1144-4 |
[11] | SALAKHUTDINOV R, MNIH A. Probabilistic matrix factorization[EB/OL].[2016-01-09]. http://drona.csa.iisc.ernet.in/~shivani/Teaching/E0371/Papers/nips07-prob-matrix-factorization.pdf. |
[12] | LEE D D, SEUNG H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401 (6755) : 788-791. doi: 10.1038/44565 |
[13] | YAHYAOUI H, Al-MUTAIRI A. A feature-based trust sequence classification algorithm[J]. Information Sciences, 2016, 328 . |
[14] | JAMALI M, ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks[C]//RecSys'10:Proceedings of the 4th ACM Conference on Recommender Systems. New York:ACM, 2010:135-142. |
[15] | YANG T, CUI Y-D, JIN Y-H. BPR-UserRec:a personalized user recommendation method in social tagging systems[J]. Journal of China Universities of Posts and Telecommunications, 2013, 20 (1) : 122-128. doi: 10.1016/S1005-8885(13)60018-7 |
[16] | PUGLISI S, PARRA-ARNAU J, FORNE J, et al. On content-based recommendation and user privacy in social-tagging systems[J]. Computer Standards and Interfaces, 2015, 41 : 17-27. doi: 10.1016/j.csi.2015.01.004 |