基于矩阵分解的社会化推荐模型
严素蓉 1,2 , 冯小青 1 , 廖一星 1     
1. 浙江财经大学 信息学院, 杭州 310018 ;
2. 加州大学尔湾分校 电子工程与计算机科学系, 加利福尼亚 92697-2625
摘要:该文提出一种经由定制关系网络改进的基于矩阵分解的社会化推荐模型来缓解数据稀疏性和冷启动问题,并进一步改善大数据集导致的可扩展性问题。在该模型中,关系网络的社交影响力被建模为矩阵分解模型的用户-物品(user-item)评分倾向,而同质性则被建模为动态正则项。为了获得更好的预测精度和可扩展性,设计了一个关系网络boosting-shrinking算法,在该算法中,基于用户在数据集中的数据密度,自适应地裁减每个用户的关系网络为其定制个性化的关系网络。在稀疏水平不同的不平衡数据集上的实验表明:相比其他的基于矩阵分解的社会化推荐模型,该模型可以显著提高稀疏数据集的预测精度,有效地缓解冷启动问题,并获得较好的可扩展性。
关键词大数据     社交网络     矩阵分解     稀疏性     可扩展性    
Matrix factorization based social recommender model
YAN Surong1,2 , FENG Xiaoqing1 , LIAO Yixing1     
1. College of Information, Zhejiang University of Finance and Economics, Hangzhou 310018, China ;
2. Department of Electrical Engineering & Computer Science, University of California, Irvine, California 92697-2625, USA
Abstract:This study describes an improved matrix factorization based social recommender model that uses tailored relationship networks of users as a solution for the sparsity, cold-start and scalability problems in big datasets. The social influence of the relationship networks is targeted as an extra user-item specific bias for the matrix factorization with the uniformity of relationship networks modeled as dynamic social regularization terms in the matrix factorization. A boosting-shrinking algorithm is used for the relationship networks for better prediction accuracy and scalability where the relationships of each user are tailored to generate personalized relationship networks according to the user-specific data density of the user-item rating matrix and the correlation matrix. Tests on unbalanced datasets with different sparsity levels show that this model significantly improves the prediction accuracy for sparse datasets, effectively addresses the cold-start problem, and has better scalability compared to other state-of-the-art matrix factorization based social recommendation models.
Key words: big data     social networks     matrix factorization     sparsity     scalability    

协同过滤(collaborative filtering,CF)是最受欢迎的构建推荐系统的技术之一[1-2]。尽管CF技术在学术界和业界逐渐被广泛发展和应用,但CF应用仍受到与数据集的特征相关的挑战与限制[3]。在大数据时代,在线用户和产品的数量迅速增加[4-5],导致可扩展性问题; 在有限的时间跨度为大量用户进行推荐成为一个挑战。除了性能,对于成功的CF方案来说,精度是必须的; 用户通常只评价或购买少量的物品,因此大数据集导致数据稀疏性问题; 当没有足量的评分可用时,很难提供准确的预测[6]。冷启动问题代表了系统为新用户和新物品提供推荐时所面临的困难。这些问题影响了依赖于用户-物品评分矩阵的CF推荐系统的精度和效率。

研究人员提出了许多方法来克服上述问题。随着社交网络服务变得无处不在,大量的用户社会关系信息可用。一种引人注意的方法是使用用户的社会关系作为额外的信息来源。基于同质性(homophily)[7]和社交影响力(social influence)[8]开发用户之间的连接信息,如学术文献推荐中的co-authorships,产品推荐中的好友和会员关系[9],可以大大缓解数据稀疏问题,改进推荐的准确性。新用户也可以受益于社交网络中的信任传播。因此,许多融合用户-物品评分矩阵和社交网络的方法(社交网络在推荐系统中通常被表示为用户相关性矩阵或图)通过继承来自其他用户的推荐来提供积极的推荐并缓解信息不足[10-20]。利用社交网络信息推荐物品也称为社会化推荐(social recommendation),已成为推荐系统领域的另一个热门话题[1, 21]

大多数现有的社会化推荐系统是基于矩阵分解(matrix factorization,MF)[21]。利用矩阵分解技术的社会化推荐方法融合了用户-物品评分矩阵和社交网络来学习用户和物品的隐特征。许多优化方法如基于梯度的方法可以用来找到最优解,可快速处理成千上万有数以百万计关系的用户。Ma等[10]提出称为社会化推荐的SoRec,通过使用共享的用户隐特征空间在用户-物品评分矩阵和用户相关性矩阵上执行联合分解,将用户的品味和所信任的朋友的喜好融合在一起。不同于SoRec,LOCABAL方法[21]基于社会相关性理论,2个连接的用户的兴趣偏好经由相关性矩阵关联。这2种方法的一个优点是它们同时执行了推荐和社会关系预测。Ma 等[11]在接下来的工作中提出了STE。STE认为用户对未知物品的评分预测应该是用户与其社交网络成员对同一物品的评分的一个线性组合。这种集成方法是基本的矩阵分解方法和基于社交网络的方法的一个线性组合。Jamali等[14]将信任传播引入到矩阵分解,在提出的SocialMF中每个用户的特征依赖于社交网络中朋友和朋友的朋友的特征向量,使用户的偏好更接近用户的社交网络的平均喜好。Ma等[12]在矩阵分解的基础上考虑用户与其朋友之间品味的差异,在提出的SocialReg中,两个连接用户的兴趣偏好的相似度是以他们之前的物品评分的相似性为基础。这种正则化方法的一个优点是用户的品味间接地在社交网络中传播,可以用来减少冷启动用户和增加物品推荐的覆盖率。一些研究者也尝试将更多的信息添加到模型[22],如Liu等[23]的SoCo处理了上下文信息,Chen等[20]则进一步通过主题建模挖掘了物品内容。

这些社会化推荐方法背后的共同原理是用户的兴趣偏好与其社交网络中的成员相似或受到他们的影响。然而,这些方法忽略的一个重要方面是社交影响力的效果: 社交网络的影响力对不同的个体有不同的影响,且可能随时间而变化。实际上一些用户可能已经有丰富的经验和兴趣偏好信息,而有些用户缺乏足够的甚至没有任何经验或兴趣偏好信息,即用户—物品评分矩阵的数据密度是不平衡(unbalanced)的,因此社交网络对推荐模型的贡献应该取决于用户—物品评分矩阵中每个用户具体的数据密度(即个人的喜好以及经验)。此外随着大数据时代的到来,用户和物品的数量大幅度增加,用户关系网络变得大而稀疏且处于不断变化中; 需要花费高的代价在高维空间搜索出信任或相似的用户。因此社会化推荐系统在近邻搜索中如何适应关系网络规模的增加变得尤为重要。

为了解决上述问题,本文提出一种经由定制关系网络改进的基于矩阵分解的社会化推荐模型来处理关系网络增加的复杂性。为了基于社会关系网络的社交影响力和同质性开发群体智慧(collective intelligence)的潜能缓解数据稀疏和冷启动问题,本文改进了基于矩阵分解的社会化推荐模型,其中社交影响力被建模为矩阵分解的额外的特定用户-物品(user-item)评分倾向; 同质性被建模为目标函数的动态正则项。此外,为了平衡不同个体自己的偏好和经验与社交影响力的影响,并适应关系网络的规模,本文设计了关系网络的boosting-shrinking算法: 基于用户-物品评分矩阵和相关性矩阵中用户的数据密度对关系网络进行剪裁,定制用户的个性化关系网络。定制的关系网络有助于在高维关系空间的近邻搜索获得更好的可扩展性。

1 问题描述

在一个典型的推荐系统中,有一组用户和一组物品。u={u1u2,…,un}和v={v1v2,…,vm}分别代表用户集和物品集,其中n和m分别是用户和物品的数量。RRn×m表示用户-物品评分矩阵,其中Rij表示uivj的评分。Rui$\bar R$ui分布代表用户ui的评分集合和平均评分。R(u)i表示用户ui评价过的物品集,R(v)j)表示评价了vj的用户集。R中有许多未知的用户-物品评分。

UUn×DVVm×D分别表示用户和物品的隐(latent)特征矩阵,UiVj分别代表用户ui和物品vj的隐特征向量,D是向量维度。bu=[bu1bu2,…,bun]∈bnbv=[bv1bv2,…,bvm]∈bm分别表示用户和物品倾向(biases)向量,buibvj分别代表用户ui和物品vj的倾向。单纯的矩阵分解[24-26]关注R分解,利用用户和物品的隐特征和倾向,预测未知的用户物品评分。

用户之间可能相互关联。SSn×n表示用户关系图或相关性矩阵,其中如果ui连接ul,则Sil=1,否则Sil=0。Sui)表示用户ui的关系集合。因此,一个社会化推荐模型的任务是: 给定一个用户ui∈u和vjv,其Rij未知,使用RS预测uivj的评分。

本文首先基于RS中的每个用户具体的数据密度剪裁用户的关系网络; 然后基于定制的关系网络改进的基于矩阵分解模型来学习用户和物品的倾向向量和隐特征矩阵,最后使用这些倾向和隐特征来预测用户对物品的未知评分。

2 提出的模型 2.1 基于评分矩阵和相关性矩阵中用户的数据密度定制用户的关系网络

用户评分直接反映用户对物品的喜好,而用户的评分数量体现了用户对物品的经验和用户的物品评分密度。密度测量是为了根据评分矩阵中的每个用户的具体数据密度来调整用户关系网络对用户的物品评分的贡献。当评分矩阵的整体数据密度和用户的具体数据密度都较高时,那么用户的兴趣偏好和经验足够丰富生成预测,关系网络的贡献应该少一些。然而,当评分矩阵的整体密度和用户的具体数据密度较低时,需要辅助丰富的关系网络以达到更好的预测。

定义1R的整体密度测量OD=|R|/(m×n),其中|R|是R中的评分数量,nm分别是用户和物品的数量.

直观上,拥有怪品味的用户,即使有大量的物品评分,也可能获得较差的推荐。这意味着用户密度测量不仅要考虑物品的数量,同时也要关注物品的数据密度。因此定义更精细的用户密度测量。

定义2  物品感知的用户密度测量旨在精细地测量用户数据密度,以反映用户在不同的物品上的经验差异:

$~M\left( {{u}_{i}} \right)=2\frac{\frac{R\left( {{u}_{i}} \right)}{m}\sum\limits_{{{v}_{j}}\in R\left( {{u}_{i}} \right)}^{{}}{{}}\frac{R\left( {{v}_{j}} \right)}{n}/\left| R\left( {{u}_{i}} \right) \right|}{\frac{R\left( {{u}_{i}} \right)}{m}+\sum\limits_{{{v}_{j}}\in R\left( {{u}_{i}} \right)}^{{}}{{}}\frac{R\left( {{v}_{j}} \right)}{n}/\left| R\left( {{u}_{i}} \right) \right|}.$ (1)

其中:|Rui|是用户ui拥有的物品评分数量,|R(vj)|是评价了物品vj的用户数量。

此外,本文引入一个置信系数反映对个人经验的信心:

$\left( R\left( {{u}_{i}} \right) \right)=\left\{ \begin{align} & \frac{R{{u}_{i}}}{Qmin}\left| R{{u}_{i}} \right|<Qmin; \\ & 1,其他. \\ \end{align} \right.$ (2)

其中Qmin表示实现用户置信度γ和误差ε所需的物品评分的最低数量[27]

$Qmin=-\frac{1}{2{{\varepsilon }^{2}}}ln\frac{1-\gamma }{2}.$ (3)

如果用户不指定γε,Qmin的默认值设置为$\sum\limits_{k=1}^{n}{{}}$|R(uk)|/n.

然而,在线社区中,一些用户的关系网络可能非常稀疏[28]。当评分数据和关系网络都非常稀疏时,间接关系网络提供了补充信息。因此稀疏的用户直接关系集可以用间接关系辅助。同样的,可以计算出关系的置信系数(S(ui))来表示用户对其直接关系网络的信心。

给定用户评分矩阵R和用户相关性矩阵S,根据用户在R和S中的用户级密度以及个人经验的置信水平,拓展和收缩用户的关系网络,为每个用户定制关系网络。用户关系网络的boosting-shrinking算法的伪代码如图 1所示。

图 1 用户关系网络的boosting-shrinking算法伪代码

应该注意到,除了可基于数据集的用户数据密度和个人经验的置信自适应地剪裁关系网络外,该算法的另一个好的方面是生成了规模可控的关系网络,有助于在关系空间的近邻搜索。

原始的S只反映了用户与其他用户之间是否存在连接关系,没有真正地反映出不同用户之间的相似度或关联度。相比Pearson和余弦向量相关性等度量方法[2],Jaccard相关性有助于提高计算的可扩展性。对于给定的S,若两个用户的共同的物品评分数量越大,且这些物品的数据密度越低,那么两个用户的相似度越高。改进的Jaccard相关性关注用户之间共同的物品数量以及这些物品的流行度,被定义为

$~sim\left( i,\text{ }l \right)=\frac{\sum\limits_{{{v}_{j}}\in R\left( {{u}_{i}} \right)\cap R\left( {{u}_{l}} \right)}^{{}}{{}}{{e}^{-lg\left| R({{v}_{j}}) \right|}}}{R\left( {{u}_{i}} \right)\cup R\left( {{u}_{l}} \right)}.$ (4)

此外也可以利用用户的属性、标签和物品元信息等来计算用户或物品之间的相关性,然后可以将这些相似的用户送入改进的矩阵分解模型。

2.2 基于定制的关系网络改进矩阵分解模型

本节将系统地描述如何建模关系网络信息作为矩阵分解的用户-物品评分倾向和正则项来改进单纯的矩阵分解模型。

低秩矩阵分解方法通过低秩(D-rank)特征相乘寻求R的近似[24-25]

$R\approx {{U}^{T}}V.$ (5)

因为用户之间是不同的,物品之间也是不同的,所以biasedMF模型[24, 26]引入两个参数buibvj来表示观察到的用户ui和物品vj的倾向:

${{R}_{ij}}\approx {{b}_{{{u}_{i}}}}+{{b}_{{{v}_{j}}}}+U_{i}^{T}{{V}_{j}}.$ (6)

一般情况下,利用奇异值分解(SVD)通过最小化所有可用的用户-物品评分与其预测评分之间的平方差来近似评分矩阵[1, 24]。为了解决过拟合问题,增加了有关用户和物品的隐特征向量和倾向的正则项约束[1, 24]

$\begin{align} & _{1}\left( R,U,V,{{b}_{u}},{{b}_{v}} \right)= \\ & \frac{1}{2}\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{m}{{{I}_{ij}}}}{{\left( {{R}_{ij}}-{{b}_{{{u}_{i}}}}-{{b}_{{{v}_{j}}}}-U_{i}^{T}{{V}_{j}} \right)}^{2}}+ \\ & \frac{{{\lambda }_{u}}}{2}\left\| {{b}_{u}} \right\|_{2}^{2}+\frac{{{\lambda }_{v}}}{2}\left\| {{b}_{u}} \right\|_{2}^{2}+\frac{{{\lambda }_{U}}}{2}\left\| U \right\|_{F}^{2}+\frac{{{\lambda }_{V}}}{2}\left\| V \right\|_{F}^{2}. \\ \end{align}$ (7)

其中Iij是指标函数。如果用户ui对物品vj进行了评分,那么Iij等于1,否则等于0。

一个用户ui的行为可能受其关系网络的影响。换句话说,ui的物品评分可能受到ui的朋友对相同或相近物品的评价的影响。给定与用户ui—同评价了物品vj的关系网络子集Sjv(ui)和插值权重矩阵WWik 表示uiukSjv(ui)的影响权重,其值通过优化学习获得。本文把社会关系的这种影响作为biasedMF模型的额外的用户-物品评分倾向。

$\begin{align} & {{R}_{ij}}\approx \sum\limits_{k\in S_{j}^{v}\left( {{u}_{i}} \right)}^{{}}{{{W}_{ik}}}\frac{\left( {{R}_{kj}}-{{{\bar{R}}}_{vk}} \right)}{\sqrt{\left| S_{j}^{v}\left( {{u}_{i}} \right) \right|}}+ \\ & {{b}_{ui}}+{{b}_{vj}}+U_{i}^{T}{{V}_{j}}. \\ \end{align}$ (8)

同时式(7)中增加正则项║WF2$\frac{{{\lambda }_{W}}}{2}$是其系数。

基于社交网络的同质性[7],朋友之间共享了许多属性。有些关系成员之间可能有相似的品味,而有些成员之间可能有完全不同的品味。因此,一个更现实的模型应该考虑用户与其朋友之间相似程度的不同。因此在式(7)中增加社会化正则项表示关于用户之间品味相似程度的先验知识。

最终的目标函数是:

$\begin{align} & _{2}\left( R,U,V,{{b}_{u}},{{b}_{v}} \right)= \\ & \frac{1}{2}\sum\limits_{i=1}^{n}{{}}\sum\limits_{j=1}^{m}{{}}{{I}_{ij}}\left( {{R}_{ij}} \right.-{{b}_{{{u}_{i}}}}-{{b}_{{{v}_{j}}}}-U_{i}^{T}{{V}_{j}}- \\ & {{\left. \sum\limits_{k\in S_{j}^{v}\left( {{u}_{i}} \right)}^{{}}{{{W}_{ik}}}\frac{\left( {{R}_{kj}}-{{{\bar{R}}}_{uk}} \right)}{\sqrt{\left| S_{j}^{v}\left( {{u}_{i}} \right) \right|}} \right)}^{2}}+ \\ & \frac{{{\lambda }_{u}}}{2}\left\| {{b}_{u}} \right\|_{2}^{2}+\frac{{{\lambda }_{v}}}{2}\left\| {{b}_{v}} \right\|_{2}^{2}+\frac{{{\lambda }_{U}}}{2}\left\| U \right\|_{F}^{2}+ \\ & \frac{{{\lambda }_{V}}}{2}\left\| V \right\|_{F}^{2}+\frac{{{\lambda }_{W}}}{2}\left\| W \right\|_{F}^{2}. \\ \end{align}$ (9)

其中用户之间的相似度被用来初始化Wil。不同于SocialReg[12],在所有训练点Wil的值会被调整,以反映用户之间品味的“真正”差异和相似。

使用梯度下降法来求解参数; 通过对WikbuibvjUiVj执行梯度下降,最小化式(9)。设Δij=$\sum\limits_{k\in S_{j}^{v}\left( {{u}_{i}} \right)}^{{}}{{{W}_{ik}}}\frac{\left( {{R}_{kj}}-{{{\bar{R}}}_{vk}} \right)}{\sqrt{\left| S_{j}^{v}\left( {{u}_{i}} \right) \right|}}+{{b}_{ui}}+{{b}_{vj}}+U_{i}^{T}{{V}_{j}}-{{R}_{ij}}$目标函数φ2WikbuibvjUiVj的梯度是

$\begin{align} & \frac{\partial {{\varphi }_{2}}}{\partial {{b}_{{{u}_{i}}}}}{{W}_{ik}}=\sum\limits_{j=1}^{m}{{}}{{I}_{ij}}{{\Delta }_{ij}}\frac{\left( {{R}_{kj}}-{{{\bar{R}}}_{vk}} \right)}{\sqrt{\left| S_{j}^{v}\left( {{u}_{i}} \right) \right|}}+{{\lambda }_{w}}{{W}_{ik}}, \\ & \frac{\partial {{\varphi }_{2}}}{\partial {{b}_{{{u}_{i}}}}}=\sum\limits_{j=1}^{m}{{}}{{I}_{ij}}{{\Delta }_{ij}}+{{\lambda }_{u}}{{b}_{{{u}_{i}}}}+{{\lambda }_{S}}\sum\limits_{l\in S\left( {{u}_{i}} \right)}^{{}}{{{W}_{il}}}\left( {{b}_{{{u}_{i}}}}-{{b}_{{{u}_{l}}}} \right), \\ & \frac{\partial {{\varphi }_{2}}}{\partial {{b}_{{{v}_{j}}}}}=\sum\limits_{i=1}^{n}{{}}{{I}_{ij}}{{\Delta }_{ij}}+{{\lambda }_{v}}{{b}_{{{v}_{j}}}}, \\ & \frac{\partial {{\varphi }_{2}}}{\partial {{U}_{i}}}=\sum\limits_{j=1}^{m}{{}}{{I}_{ij}}{{\Delta }_{ij}}+{{V}_{j}}+{{\lambda }_{U}}{{U}_{i}}+ \\ & {{\lambda }_{S}}\sum\limits_{l\in S\left( {{u}_{i}} \right)}^{{}}{{{W}_{il}}}\left( {{U}_{i}}-{{U}_{l}} \right), \\ & \frac{\partial {{\varphi }_{2}}}{\partial {{V}_{j}}}=\sum\limits_{j=1}^{m}{{}}{{I}_{ij}}{{\Delta }_{ij}}+{{U}_{i}}+{{\lambda }_{V}}+{{V}_{j}}, \\ \end{align}$ (10)

为了降低模型复杂度,在实验中设置λU=λVλu=λvUV的初始值是均值为0的标准噪声。bubv的初始值设置为0。W被初始化为用户之间的相似性度量。

3 实验和讨论

本节通过几组实验比较本文的推荐方法与现有一些推荐方法的效果,并对实验结果进行分析。

3.1 实验设置

实验从可用的公开数据集里,选用了3个代表不同数据密度和关系类型的数据集: Epinions、 Flixster、 Netflix5m3k(Netflix的一个子集)。其中,Flixster和Netflix5m3k的密度比Epinions的高。不同于Flixster的社交网络和Epinions的信任网络,Netflix5m3k提供了较为密集的相似用户网络。

为了评价推荐模型,数据通常分为2个部分: 训练集A(已知评分)和测试集E(未知的评分)。在本文的实验中,分别把每个用户和每个物品的75%数据作为训练集,剩下的25%作为测试数据。

预测精度度量了预测评分和真正的评分之间的逼近度。2个广泛使用的精度指标是RMSE和MAE。RMSE=$\sqrt{\frac{1}{\left| E \right|}\sum\limits_{\left( {{u}_{i}},{{v}_{j}} \right)\in E}^{m}{{}}{{\left( {{R}_{ij}}-{{{\hat{R}}}_{ij}} \right)}^{2}}}$,其中|E|是测试集的规模,${\hat{R}}$ijuivj的预测评分。RMSE给相对较高的误差大的权重。MAE度量以相同的权重加权每个评分误差,MAE=$\frac{1}{\left| E \right|}\sum\limits_{\left( {{u}_{i}},{{v}_{j}} \right)\in E}^{m}{{}}\left( {{R}_{ij}}-{{{\hat{R}}}_{ij}} \right)$。较小的RMSE或MAE值意味着推荐模型有更好的性能。

为了证明本文方法的有效性,基于MyMediaLite库[29],将本文方法与UserKNN、 基线矩阵分解(PMF)[25]模型、 biasedMF[24-26]、 SocialMF[14]、 SocialReg[12]进行比较。

在UserKNN中,用户的物品预测评分由与其相似的用户对相同物品的评分决定,主要参数设置为k=80。在PMF模型中,主要参数设置为隐特征维度D=20,正则化系数λU=λV=0.015。在biasedMF中,增加用户和物品倾向,主要参数设置为D=20,λU=λV=0.015,倾向的正则化系数bias_reg=0.01。在SocialMF中,主要参数设置隐特征维度K=20,λU=λV=0.01,bias_reg=0.005,社交正则化系数λT=0.01。在SocialReg中,主要参数设置与SocialMF相同。本文方法被称为SocialNMF,主要参数的设置与SocialReg相同,另外一个重要的参数λW=0.000 5。

在SocialNMF中,参数λSλW扮演了重要的角色。实验进行了迭代学习。λSλW有相似的结果,由于篇幅限制只说明λW的结果。测试结果表明迭代在Epinions、 Netflix5m3k、 Flixster数据集迭代学习约40次开始收敛。图 2比较了SocialNMF在3个数据集上使用不同的学习率αλW的RMSE值。可以看出,无论使用哪个数据集和如何设置α,随着λW的增加,在低于某一阈值时预测精度会增加,但λW再增加则预测精度降低。

图 2 不同αλW对RMSE的影响

3.2 在不平衡的稀疏数据集的实验结果

实验比较了模型在3个数据集上的效果。

表 1表明SocialNMF较好地处理了稀疏数据集。在Epinions这样的稀疏数据集上预测精度明显增加。测试结果还表明,对于SocialNMF而言,改进的Jaccard相关性较稳定地捕获了两个用户在物品偏好方面的交集,因为其在初始化W时,关注用户之间是否存在相关性,而不考虑用户如何评价物品。

表 1 性能比较
数据集 方法 RMSE MAE RMSE MAE
新物品 新用户 新物品 新用户
EpinionsUserKNN1.1020.8541.1051.0970.8580.88
PMF1.1850.9251.1461.2440.8720.968
BiasedMF1.0760.8481.1061.0950.8580.872
SocialMF1.0790.8541.1061.0990.8630.882
SocialReg1.0790.8541.1061.0990.8630.882
1.0790.8541.1061.0990.8630.882
SocialNMF0.9820.7611.0460.9650.8110.752
0.9820.7621.0480.9660.8150.753
FlixsterUserKNN1.0150.7750.8391.0870.8390.853
PMF1.0250.7931.0941.1060.8540.887
BiasedMF0.9780.7470.8441.0870.6260.854
SocialMF0.990.7610.8431.090.6260.856
SocialReg0.9910.7620.8431.090.6280.856
0.9910.7620.8421.090.6260.856
SocialNMF0.9890.7610.8351.0890.6210.857
0.9890.7610.8381.090.6240.856
Netflix5m3kUserKNN1.0170.8031.0441.010.840.806
PMF1.0620.871.1411.0770.950.902
BiasedMF0.9830.7811.0421.0110.8320.805
SocialMF0.9880.7881.0431.0110.8390.806
SocialReg0.9880.7881.0431.0110.8390.806
0.9870.7881.0431.0110.8390.806
SocialNMF1.0280.821.0261.0480.810.856
0.980.7821.0191.0120.8170.81

对于3个数据集,SocialNMF比其他5种方法获得了更好的精度指标得分。

SocialNMF在Epinions数据集上的预测精度获得显著的改善。这是因为Epinions数据集中每个用户的评分和社会关系较为稀少,关系网络的boosting-shrinking算法实际为用户执行了一个可控的关系网络拓展。这也再次证明了当用户没有直接联系时,弱依赖关系可以提供与用户兴趣相关的重要补充信息。而在Flixster和Netflix5m3k中,每个用户有较多的评分和社会关系,SocialNMF也比其他方法获得了更好的预测精度,这是因为根据用户在数据集中的具体数据密度,SocialNMF为每个用户定制其关系网络,这有助于获得更好的预测精度和可扩展性。

也应该注意到,相比新物品问题,所有的方法对新用户问题表现出更好的性能。一种可能的解释是因为事实上,用户对相似类别物品的偏好和需要可能非常不同,文[30-31]建议(电子商务)推荐系统应该推荐最大化用户的边际效用的物品,而不再是类似的物品。另一方面,基于同质性原则,可以较为容易地提取出相连接的用户之间的喜好和品味的交集如各种兴趣组。

3.3 参数学习和评分预测的复杂性分析和运行时分析

学习模型参数的主要成本是计算目标函数φ2中插值权矩阵以及用户和物品的倾向和隐特征向量的梯度。假设每个用户评分的平均数量是r,每个用户和物品的直接关系成员的平均数量分别是uv,每个用户-物品评分的直接邻居平均数量是k。其中,计算biasedMF和PMF梯度的计算复杂度是O(nrD),SocialMF的是O(nrD+nu2D),SocialReg的是O(nrD+nuD),SocialNMF的是O(nrD+nuD+nrk)(k<u), UserKNN的是O(n2)。

在评分预测和测试阶段的主要成本是计算预测函数。计算biasedMF、 PMF、 SocialMF和SocialReg的预测函数的复杂度均是O(nrD),SocialNMF的是 O(nrD+nrk)(k<u),UserKNN的是O(nrk2)(kn),因为UserKNN需要在整个邻居空间进行最近邻搜索和排名。

每个方法的实际运行时间也与每个模型收敛的速度有关。实验在Core4 i5-2450M,2.5 GHz处理器,8 GB内存的机器上进行。表 2列出了方法在训练和测试阶段的实际运行时的单次迭代的平均时间。实际运行时间符合上述关于运行时间的复杂度分析。应该指出的是,相比基于矩阵分解(MF)的SocialMF和SocialReg,SocialNMF在3个数据集上保持更好的可扩展性,因为SocialNMF开发了可控大小的关系网络(实验中Epinions的新用户关系网络规模比原有的用户关系网络增加了约1倍,而Netflix5m3k和Flixster的新用户关系网络规模比原有用户关系网络缩小了约10倍)。

表 2 运行时间比较
数据集 方法 训练时间均值/s 预测时间均值/s
Epinions UserKNN 5 213.5 1 373.5
PMF 1.0 1.0
BiasedMF 1.0 2.0
SocialMF 104.0 3.0
SocialReg 2.0 3.0
SocialNMF 34.5 8.0
Flixster UserKNN 430 745.0 71 071.0
PMF 17.0 15.0
BiasedMF 9.0 40.0
SocialMF 2 028.0 33.0
SocialReg 22.5 31.5
SocialNMF 289.5 79.0
Netflix5m3k UserKNN 1 135.0 227.0
PMF 1.0 1.0
BiasedMF 1.0 1.0
SocialMF 16 911.0 1.0
SocialReg 16.5 1.0
SocialNMF 35.0 8.5

总之,在3个数据集的实验结果显示出SocialNMF明显减轻了数据稀疏和冷启动问题,而复杂性分析和运行结果表明SocialNMF获得了良好的可扩展性,尤其是对较密集的数据集。

4 结 论

本文设计和评估了经由定制关系网络改进的基于矩阵分解的社会化推荐模型SocialNMF,处理了在物品推荐时大数据集导致的数据稀疏性、冷启动和可扩展性问题。在3个不平衡数据集的实验结果显示,在处理以上问题时,相比现有的基于MF的社会化推荐方法,SocialNMF获得更好的预测精度和可扩展性。

正如很多基于MF的协同过滤技术[26],SocialNMF是非凸的。但本文的实验显示SocialNMF易于发现局部最优解。此外,本文主要关注了用户之间的结构性信息,忽略了物品之间的结构信息以及其他推荐上下文信息对推荐结果的影响。下一步将研究如何将更多的上下文信息加入到社会化推荐模型中。

参考文献
[1] Koren Y. Factorization meets the neighborhood:A multifaceted collaborative filtering model[C]//Proc ACM SIGKDD'08. Las Vegas, NE, USA:ACM, 2008:426-434. http://www.scirp.org/reference/ReferencesPapers.aspx?ReferenceID=1356846
[2] Su X, Khoshgoftaar T. A survey of collaborative filtering techniques[J]. Advances in Artificial Intelligence , 2009 (2009) : 421–425.
[3] Tavakolifard M, Almeroth K C. Social computing:an intersection of recommender systems, trust/reputation systems, and social networks[J]. Network, IEEE , 2012, 26 (4) : 53–58. DOI:10.1109/MNET.2012.6246753
[4] Xin J C, Wang Z Q, Qu L X, et al. Elastic extreme learning machine for big data classification[J]. Neuro computing , 2015 (149) : 464–471.
[5] Jamiy E L, Daif A, Azouazi M, et al. The potential and challenges of Big data-Recommendation systems next level application[J]. International Journal of Computer Science Issues , 2014, 11 (5) : 21–26.
[6] Pagare R, Patil S A. Study of collaborative filtering recommendation algorithm-scalability issue[J]. International Journal of Computer Applications , 2013, 67 (25) : 10–15. DOI:10.5120/ijca
[7] McPherson M, Smith-Lovin L, Cook J. Birds of a feather:Homophily in social networks[J]. Annual review of sociology , 2001, 27 : 415–444. DOI:10.1146/annurev.soc.27.1.415
[8] Marsden P, Friedkin N. Network studies of social influence[J]. Sociological Methods and Research , 1993, 22 (1) : 127–151. DOI:10.1177/0049124193022001006
[9] Liu LY, Medob M, Yeung CH, et al. Recommender systems[J]. Physics Reports , 2012, 59 (1) : 1–49.
[10] Ma H, Yang H, Lyu M R, et al. SoRec:Social recommendation using probabilistic matrix factorization[C]//Proc ACM IKM'08. Napa Valley, CA, USA:ACM, 2008:931-940.
[11] Ma H, King I, Lyu M R. Learning to recommend with social trust ensemble[C]//Proc ACM SIGIR'09. Boston, MA, USA:2009:203-210. http://dl.acm.org/citation.cfm?id=1571941.1571978
[12] Ma H, Zhou D, Liu C, et al. Recommender systems withsocial regularization[C]//Proc ACM WSMD'11. Hong Kong, China:ACM, 2011:287-296.
[13] Jamali M, Ester M. Trustwalker:a random walk model for combining trust-based and item-based recommendation[C]//Proc ACM SIGKDD'09. Paris, France:ACM, 2009:397-406.
[14] Jamali M, Ester M. A matrix factorization technique with trust propagation for recommendation in social networks[C]//Proc ACM RecSys'10. Barcelona, Spain:ACM, 2010:135-142.
[15] Symeonidis P, Tiakas E, Manolopoulos Y. Product recommendation and rating prediction based on multi-modal social networks[C]//Proc ACM RecSys'11. Chicago, IL, USA:ACM, 2011:61-68.
[16] Yuan Q, Chen L, Zhao S. Factorization vs. regularization:fusing heterogeneous social relationships in top-n recommendation[C]//Proc ACM RecSys'11. Chicago, IL, USA:ACM, 2011:245-252.
[17] Yang X, Steck H, Liu Y. Circle-based recommendation in online social networks[C]//Proc ACM SIGKDD'12. Beijing, China:ACM, 2012:1267-1275.
[18] Noel J, Sanner S, Tran K N, et al. Objective functions for social collaborative filtering[C]//Proc WWW'12. Lyon, France, 2012:859-868.
[19] Yan S R, Zheng X L, Chen D R, et al. Exploiting two-faceted web of trust for enhanced-quality recommendations[J]. Expert Systems with Applications , 2013, 40 (17) : 7080–7095. DOI:10.1016/j.eswa.2013.06.035
[20] Chen C, Zheng X, Wang Y, et al. Context-aware collaborative topic regression with social matrix factorization for recommender systems[C]//Proc AAAI'14. Québec City, QU, Canada, 2014:9-15.
[21] Tang J, Hu X, Liu H. Social recommendation:A review[J]. Social network analysis and mining , 2013, 3 (4) : 1113–1133. DOI:10.1007/s13278-013-0141-9
[22] Colombo-Mendoza L O, Valencia-García R, Rodríguez-González A, et al. RecomMetz:A context-aware knowledge-based mobile recommender system for movie show times[J]. Expert Systems with Applications , 2015, 42 (3) : 1202–1222. DOI:10.1016/j.eswa.2014.09.016
[23] Liu X, Aberer K. SoCo:A social network aided context-aware recommender system[C]//Proc www'13. Rio de Janeiro, Brazil, 2013:781-802.
[24] 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
[25] Salakhutdinov R, Mnih A. Probabilistic matrix factorization[J]. Advances in neural information processing systems , 2008, 20 (1) : 1257–1264.
[26] Menon A K, Elkan C. A log-linear model with latent features for dyadic prediction[C]//Proc ICDM'10. Sydney, Australia:IEEE, 2010:364-373.
[27] Yan S R, Zheng X L, Chen D R, et al. User-centric trust and reputation model for personal and trusted service selection[J]. International Journal of Intelligent Systems , 2011, 26 (8) : 687–717. DOI:10.1002/int.v26.8
[28] Yan S R, Zheng X L, Wang Y, et al. Graph-based comprehensive reputation model:Exploiting the social context of opinions to enhance trust in social commerce[J]. Information Sciences , 2015, 318 : 51–72. DOI:10.1016/j.ins.2014.09.036
[29] Gantner Z, Rendle S, Freudenthaler C, et al. MyMediaLite:A Free Recommender System Library[C]//Proc ACM RecSys'11. Chicago, IL, USA:ACM, 2011:305-308.
[30] Wang J, Zhang Y. Utilizing marginal net utility for recommendation in e-commerce[C]//Proc ACM SIGIR'11. Beijing, China:ACM, 2011:1003-1012.
[31] Wang J, Zhang Y. Opportunity model for e-commerce recommendation:Right product; right time[C]//Proc ACM SIGIR' 13. Dublin, Ireland:ACM, 2013:303-312.