第39卷  计  算  机  学  报  Vol.39 2016 论文在线出版号  No.175  CHINESE JOURNAL OF COMPUTERS  Online Publishing No.175 ——————————————— 本课题得到国家自然基金（61472289）,湖北省自然科学基金  (2015CFB254)资助.  潘一腾，男，1988年生，博士研究生，主要研究领域为推荐系统、深度学习. E-mail: panyiteng@whu.edu.cn.何发智（通信作者），男，1968年生，博士，教授，计算机学会(CCF)会员，主要研究领域为CAD图形图像、协同计算、数据挖掘. E-mail: fzhe@whu.edu.cn.  于海平，女，1978年生，博士研究生，主要研究领域为图像处理、图像分割. E-mail: seaping@whu.edu.cn.  一种基于信任关系隐含相似度的社会化推荐算法 潘一腾1),2)  何发智1),2)  于海平1),2) 1)(武汉大学软件工程国家重点实验室,  武汉市  430072)  2)(武汉大学计算机学院，武汉  430072)*  摘  要  推荐算法已经成为许多电子商务网站必不可少的组成部分.  基于用户历史评价数据的协同过滤推荐算法通常面临着数据稀疏的问题，即用户评分过于稀疏导致推荐质量下降.  为了解决这一问题，结合辅助数据成为一种必然的趋势.  因此，随着社交媒体的发展，基于信任关系的社会化推荐算法被证明一种有效的解决方法.  这些算法利用社交网络信息对用户偏好进行建模，并进行推荐.  然而，目前大部分算法直接利用社交网络的二值信任关系来提高推荐质量，从而没有考虑用户对每个好友信任强度的差异.  为了解决这一问题，本文提出了一种新的基于信任关系隐含相似度的度量方法，并与协同推荐算法相结合，获得更高的推荐质量.  与之前的方法不同，在考虑评分相似度的基础上，本文专注于研究利用社交信息来估计信任强度并提出了信任关系隐含相似度.  首先，本文考虑了用户间的间接影响，即通过分解社交矩阵得到隐含间接影响的用户社交偏好，并基于此得到了信任关系隐含相似度；其次，鉴于用户在作为信任者和被信任者时的偏好并不相同，本文提出的信任关系隐含相似度分别考虑了这两种情况；进一步，考虑到评分和社交数据都非常稀疏，我们同时考虑了评分相似和信任相似对每组用户间信任强度的影响，得到一个更加精确的社会化推荐模型；最后，不同于直接计算信任强度的算法，本文基于评分和社交数据，提出一种自适应相似度计算的模型.  本文在Epinions和Ciao数据集上进行了丰富的实验，并与多种前沿的算法进行了性能对比.  文中同时采用基于误差的指标（MAE、RMSE）和排序类指标（精度,  召回率和NDCG）对算法性能的性能进行度量，结果表明本文算法对于评分预测和Top-N项目推荐任务都能得到鲁棒的表现.  文中还展示了对于评分和信任数据稀疏用户的性能表现，结果仍优于以往的算法.  概括来说，文中算法充分挖掘了用户在评分和社交数据中的隐含信息，从而有效提高了社会化推荐算法的精度.   关键词  推荐系统；  协同过滤算法；  社会推荐算法；  潜在矩阵分解；  信任关系传播；隐含相似度 中图法分类号  TP391  论文引用格式 潘一腾,何发智,于海平，一种基于信任关系隐含相似度的社会化推荐算法，2016，Vol.39：在线出版号  No.175 Pan Yi-Teng,He Fa-Zhi,Yu Hai-Ping，Social Recommendation Algorithm Using Implicit Similarity in Trust，Chinese Journal  of Computers,2016, Vol.39: Online Publishing No.175  Social Recommendation Algorithm Using Implicit Similarity in Trust  Pan Yi-Teng1),2)  He Fa-Zhi1),2)  Yu Hai-Ping1),2) 1)( State Key Laboratory of Software Engineering, Wuhan University, Wuhan, 430072) 2) (School of Computer Science, Wuhan University, Wuhan, 430072)  网络出版时间：2016-11-25 23:25:52网络出版地址：http://www.cnki.net/kcms/detail/11.1826.TP.20161125.2325.006.html2  计  算  机  学  报  2016年  Abstract  Recommendation  system  is  becoming  one  of  the  most important  components  in  many  e-commerce websites and web applications. In the past decades, collaborative filtering (CF) is the most success approach to handle the recommendation task, which leverage users’ historical rating data to model users and items preference. As an early approach, the CF algorithm is seriously affected by the data spare problem, which means that most users  rate  only  a  few  items.  This  problem distinctly degenerates  the  performance  of  CF-based  methods. To address this problem, introducing auxiliary information for CF algorithm becomes a necessary trend to improve recommendation accuracy. Therefore, with the development of social media, social recommendation algorithms have been proposed and presented as a potential way to solve this problem. These methods utilizing users’ social information to help modeling user preference for recommendation. However, most of them simply make use of the social network information with binary format directly, and thus ignore the fact that the trust degrees between each pair of users are full of variety. In this paper, we propose a new method to measure trust degrees, i.e., how much degrees  will  users  trust  in  other  users,  and  to  integrate  these  degrees  for  social  recommendation. Advancing previous works, in additional of rating similarity, we focus on the social information to estimate trust degrees and propose the implicit similarity in trust. Specially, we take the indirect social influence of users into account  to  estimate  trust  degrees  between  each  pair of  users. We obtain  the  social  preferences which  contains indirect  influence  by  factorizating  the  social  matrix.  Based  on  these  preferences,  we  propose the  implicit similarity in trust for users, which exactly reflect social relations. In addition, based on the intuition that a user plays different preferences with role of truster and trustee, our proposed implicit similarity in trust is consist of two  parts:  users  as  truster  and  as  trustee. Moreover,  on  account  of  the  fact  that  both  rating  and  social  data are very  spare,  we take  both  rating  and  social  data  into  account  to enhance  the  evaluation  of trust  degrees. In  this way, after synthesizing both rating similarity and implicit similarity in trust for each pair of users, we establish an  accurate  social  recommendation  model.  Furthermore, instead  of  directly  estimating  the  trust  degrees, we propose an adaptive similarities learning model based on both rating similarity and implicit similarity in trust to evaluate trust degrees for  recommender  system. We conduct  several  experiments  on  both  Epinions  and  Ciao datasets, and compared our model with several state of the art algorithms. The experiments demonstrate that the proposed approach fully exploits implicit information in rating data and social network, and efficiently improves the performance of social recommendation. Specially, the results is evaluated in terms of two error based metrics (MAE  and  RMSE)  and rank-sensitive  metrics (precision,  recall  and  NDCG), and  indicate  that  our  approach  is robust in both tasks of rating prediction and top-n recommendation tasks. We also demonstrate the results in case of  sparse  rating  data or  spare  social  data,  which outperforms  previous  works. In  summary,  our  approach, fully exploiting implicit information in rating and social data, can efficiently improve recommendation accuracy.  Key words  recommendation system; collaborative filtering; social recommendation; latent matrix factorization; trust propagation; implicit similarity  1  引言 在日常生活中，随着网络信息的不断发展，信息过载问题变得越来越严重.  如何从海量的数据中获得有效的信息，对于普通用户来说是一个巨大的挑战.  推荐算法是解决这一问题的重要手段之一，通过对用户的历史行为建模，主动向用户提供满足用户潜在偏好的产品.  对于用户来说，推荐系统能够帮助他们在海量的信息中快速找到满意的信息；对于商家来说，推荐系统不仅能帮助决定向特定用户推销那些产品，同时能够通过更满意的服务增加用户的忠诚度.  推荐系统广泛应用于大量的电子商务网站中，比如淘宝、京东、亚马逊等，已经成为网络应用的重要组成部分之一[1-5].   尽管近年来推荐算法在各种应用中都取得了巨大的成功[6-11]，然而数据稀疏问题仍然是影响算法性能的重要瓶颈之一.  推荐算法通常基于用户的历史数据对用户偏好进行建模，然后根据用户的偏好从海量的数据中找到合适的产品推荐给用户.  而当这些数据并不足以反映用户或产品的属性时，推荐性能就会受到影响.  具体来说，在一般情论文在线出版号  No.175  潘一腾等：一种基于信任关系相似度的社会化推荐算法  3   况下，大多数用户由于精力有限或个人隐私等原因，并不会对所有的产品进行评价，相反，只会选择少量的产品进行评分，从而所获得的评分矩阵只有少量是已知的，而其他大量的未知评分则是推荐算法的预测目标.  此时，这少量的评分数据只能反映用户非常少的有用信息，而基于此所建立的模型也难以准确把握用户真正的喜好，进而导致推荐精度下降，这一问题被称为数据稀疏问题.   围绕着数据稀疏的问题，许多学者提出了有效的解决方法[7,12-17].  包括引入辅助数据、综合跨域信息或挖掘数据中的更多的隐含规律，比如，利用项目特征辅助提高推荐算法处理数据稀疏问题的能力[6,7,12,18]，考虑将不同信息源的数据进行结合得到跨域推荐结果[19,20]，挖掘数据中的隐含反馈信息[17,21]，充分利用用户提供的信息[22]或者结合社交关系信息[23-25]等. 其中，结合社交信息的推荐算法是解决数据稀疏问题的有效手段之一.  一方面，在生活中，人们在做出决定之前通常会向他的好友咨询，并受到好友的影响；另一方面，人们总是倾向于与他爱好相似的人结为好友关系[26,27]. 因此，社交网络数据在一定程度上揭示了用户的偏好相似性，这对提高推荐算法的质量提供了新的机会.  特别是在处理数据稀疏问题上，社会化推荐算法能显著提高稀疏用户的推荐性能，从而提升用户体验和忠诚度[3].  近年来，社会化推荐算法吸引了越来越多研究人员的关注，成为推荐算法的热门研究领域之一[6,10,13,23,24,28-33].   基于用户与好友偏好相似的假设，为了更有效的对用户之间的社交关系进行建模，充分挖掘社交好友对用户偏好的影响，很多工作对此做出了有益的探索.  比如，Ma等人[23]采用概率矩阵分解的方法对社交信息建模，Jamali 等人[25]将信任传播引入到社会化推荐算法当中，Yang等人[34]则对用户作为信任者和被信任者的情况进行了建模.   考虑到用户对每个好友的信任强度并不相同，如何估计用户之间的信任度，成为影响社会化推荐算法进一步提高的重要问题之一.  该相似度可以从评分或信任数据的角度进行度量，即基于具有相似的评分行为或信任关系的用户之间具有相似的兴趣偏好的假设，可以用评分或信任相似度量用户之间的信任度.  比如，Ma等人[35]利用评分相似度函数计算用户之间的信任强度，Yao等人[36]从信任关系的角度对信任强度进行估计，Wang等人[37]则考虑了用户的评分和信任相似度并进行加权.   这些对信任强度进行探索的工作，很好的挖掘了社交关系中的隐含信息，然而这一问题并没有完全解决，不能很好的处理评分和信任数据稀疏的情况.  具体来说，文中主要针对这些工作的以下两个不足之处进行研究.   首先，这些工作对信任相似的估计都是基于共同好友集合的相似函数进行计算，这在信任数据稀疏的情况下，不能得到有效的结果.  比如，在只有零个或很少共同好友时，得到零或很小的相似度，而这并不能反映用户之间的真实关联情况.   其次，已有的工作表明评分相似和信任相似都能在一定程度上揭示用户之间的信任强度，然而，大部分工作[35,36]都仅考虑了其中一方面的影响.  虽然Wang等人[37]从评分和信任相似的角度进行了建模，然而，没有对每组用户间的信任强度综合两方面的信息.   为此，文中算法在社会化推荐算法SocialMF 的基础上，提出一种基于信任关系隐含相似度的推荐算法.  本文的贡献点主要包括：（1）提出一种信任关系隐含相似的度量方法，不仅包含用户间的直接关联信息，而且隐含了用户间的间接社交关联，进而提高了推荐精度；（2）提出分别计算用户作为信任者和被信任者时的信任关系隐含相似度，从而更为全面的利用了信任关系中的隐含信息；（3）综合考虑了评分相似和信任关系隐含相似对每组用户之间信任度的影响，得到了更精确的信任度量和推荐模型.   2  相关工作 传统的推荐算法主要专注于充分利用用户的历史评价数据进行推荐，这类算法称为协同过滤推荐算法.  然而，这些算法始终面临着用户历史数据非常稀疏的问题，导致推荐质量下降.   为了解决这一问题，在算法中引入辅助数据或挖掘数据中更多规律是有效的方法.  例如，Wang等人[7]利用LDA算法提取文本特征提高推荐算法处理冷启动和稀疏用户的能力，Koren等人[17]通过挖掘数据中的隐含反馈从而提高推荐精度，黄创光等人[16]则动态结合用户和产品的相似性从而提高算法处理稀疏数据的能力，以及其他许多学者提出一系列结合社交关系的推荐算法解决冷启动和稀疏问题[15,23-25,29,35,38]. 其中结合了社交关系的协同过滤算法称为社会化推荐算法.  得益于社交媒体应用的发展，用户之间在网络上的交流越来越频繁，逐渐成为人们日常生活的一部分，使得社交关系数据的获取越来越快捷方便.  因此，基于社交的推荐也逐渐成为推荐算法不可或缺的一部分.  社会化推荐算法研究重点在于如何更有效的将社交信息与评价信息有机融合.   大多数社会化推荐算法主要专注于解决两个问题：如4  计  算  机  学  报  2016年  何将社交信息有效的集成到推荐算法中？如何估计用户之间的信任度以提高算法精度？ 针对第一个问题，许多工作尝试从不同的角度对社交信息进行建模.  例如，Jamali 等人[38]提出一种在评分网络和社交网络中随机游走的TrustWalker算法.  该算法在不需要预先训练的情况下，通过在历史数据中游走得到结果，但是在数据量比较大的时候，查询时间往往过大.  Ma 等人[23]提出Sorec算法，假设用户在评价网络和社交网络中共享相同的偏好向量，并采用概率矩阵分解的方式进行约束，最终获得考虑用户好友因素的推荐结构.  相比于之前的工作，他们的算法获得更高的精度.  随后他们又提出将评价信息和社交网络进行集成的推荐算法RSTE [24]，该算法假设用户的评价由个人偏好和好友影响共同决定，并存在一个平衡.  Jamali 等人[25]将信任传播的方法引入到推荐算法中（SocialMF），通过约束用户与其好友的平均偏好相似来传播信任关系，从而得到更准确的结果.   以上这些工作假设每个好友对用户的影响是相同的. 而现实中，用户对每个好友的信任度并不相同[39]，甚至有可能完全不信任（即有可能仅仅出于礼貌而添加好友关系）. 实际上，用户间的信任关系受多种因素的影响，有的是由于爱好相似，有的是由于相同的社交圈子，有的则仅仅是出于礼貌.  简单的二值信任网络并不能反映出用户之间的影响力大小，也不能充分挖掘社交网络中隐含的用户偏好信息，由此引出了第二个问题的研究，即如何估计用户之间的信任度？ 因此，Ma等人[35]考虑了用户评分相似度对信任强度的影响，将社交网络作为正则约束项来学习用户偏好，得到更加精确的结果.  郭磊等人[40]利用对评分矩阵进行概率矩阵分解得到的潜在向量计算用户与好友之间的相似性，提高了算法精度.  他们同时提出充分利用对象间的关系提高推荐精度[41].   但是，当用户评分数据稀疏时，根据评分计算得到的相似度并不能准确反映用户的喜好，而基于此得到的用户信任度也不可靠，从而对推荐算法的精度产生不利的影响.   所以，人们继续从社会关系的角度进行挖掘.  Yao 等人[36]则考虑了用户作为信任者和被信任者时的不同情况，分别计算两种情况的信任相似度，以此约束用户偏好向量的学习，然后对这两种情况下的用户向量进行加权并对评分结果产生影响.  不过，这没有考虑到用户评分偏好和社交偏好并不共享相同的潜在空间，基于此，Wang等人[42]提出通过线性映射的方法建立用户评分偏好和社交偏好的关系，并采用修正的信任强度约束用户之间的关系.  为了进一步提高精度，Wang等人[37]则同时从评分和信任数据的角度对用户之间的信任强度进行估计，分别提出了用户的能力度量函数和可信赖度量函数，并通过自适应加权的方式与评分相似函数结合得到估计的用户偏好，并在此基础上构建了一个更为精确推荐模型.   以上这些算法从评分或信任数据的角度对用户之间的信任强度进行了研究，相比于将每个好友对用户的影响视为等同的算法，取得了明显的提高.  然而，对这一问题的研究仍然存在一些问题.  针对引言中提到的具体问题，我们提出了一种基于信任关系隐含相似度的社会化推荐算法.   首先，我们采用概率矩阵分解的方法获得用户作为信任者和被信任者时的潜在向量，并以此来计算用户分别作为信任者和被信任者时的相似度.  与之前的工作[36,37,42]相比，我们的信任相似度计算并不依赖于用户之间的共同好友集合或用户好友数量，即使在信任数据比较稀疏或共同好友集合为零的情况也能得到稳定可靠的计算结果.  同时，这一方法通过将用户社交行为映射到低维子空间，得到的用户向量不仅包含了用户之间的直接关联，而且隐含了用户之间的间接联系.  具体来说，如果两个用户之间没有建立社交关系，而这两个用户的好友集合之间有很多关联，那么他们的用户向量之间也会具有很强的联系.  因此，我们得到了一个更为精确的信任度量模型.   其次，我们综合考虑了评分和信任相似对用户间信任强度的影响.  大部分已有的工作都仅单独考虑了这两者对信任强度的影响[35,36]，而他们的工作表明，这两者对于信任强度的估计都是有益的，因此，有必要综合两者信息从而得到一个更精确的模型.  基于此，Wang等人在[37]与我们的工作比较接近，也同时考虑了评分和信任数据中的信息. 他们从信任近邻和评分近邻集合的角度对两者进行建模，然而，这两个集合并不是相等的，则对于只存在于其中一个集合的近邻而言，仅利用了其中一方面的信息；同时，他们也没有考虑两个用户都作为信任者或被信任者时的信任关系隐含相似度.  与他们的工作[37]相比，我们对于每一组用户间的信任估计都综合了两方面的信息，并且考虑了信任关系隐含相似度，进而得到更为精确的信任度量.   最终，我们得到一个综合考虑评分和信任相似的推荐法模型，不仅提高了算法处理稀疏数据的能力，而且通过挖掘数据中的隐含关联信息，进一步提高了模型的精度.   3  社会化推荐算法 本节主要介绍与本文直接相关的两个经典算法.  首先对社会化推荐的问题进行形式化定义和描述，然后分别回顾两个已有的相关工作，包括基于概率矩阵分解的推荐算法PMF[43]和基于信任传播的社会化推荐算法SocialMF[25].   3.1 问题描述 论文在线出版号  No.175  潘一腾等：一种基于信任关系相似度的社会化推荐算法  5   我们假设推荐系统中含有N个用户组成的集合1{ ,..., }nU u u =和M个产品组成的集合1{ ,..., }MI i i =，以及用户对产品的评价矩阵,[]u i N M ´= RR.  在评价矩阵中, uiR表示用户u对产品i 的评分.  评分矩阵中通常隐含了用户的潜在偏好信息，是推荐算法采用的主要数据 在社交网络中，每个用户有uN个好友，, uvt表示用户u和v的好友关系，0表示非直接好友，1表示直接好友，从而得到用户的信任矩阵,[]u v N N ´= TT.  用户的社交关系通常只能获得二值的数据，然而并非所有的好友对用户的影响都是一样的，因此，本文主要研究如何结合信任关系隐含相似度来提高推荐算法的质量.   社会化推荐算法的基本目标是，在给定评价矩阵R和信任关系T的情况下，预测用户u对未评价项目i的评分情况.  研究表明，结合社交信息的推荐算法能够有效缓解数据稀疏的问题.  目前，如何高效的挖掘社交关系中隐藏的用户偏好信息是社会化推荐算法的研究重点.   3.2 概率矩阵分解 传统的协同过滤推荐算法通常只采用用户历史评价数据对用户建模，进而对用户未来的评价和选择进行预测，包括基于记忆[44]和基于模型[43,45]两种类型.  其中，基于概率矩阵分解的协同过滤算法PMF[43]（Probabilistic  Matrix Factorization）是一种经典的推荐算法模型，该算法假设每个用户和产品的潜在属性都用一维向量表示，而用户对于特定产品的评价则由对应的两个向量的点积获得.  与基于记忆的推荐算法相比，该模型可以更有效的处理大规模数据和稀疏数据，不需要花费大量的查询时间，从而很快的生成推荐结果.   假设KN´Î UR和KM´Î VR分别表示用户和产品的潜在矩阵，其中uU和iV分别表示用户u和产品i 的K维潜在向量.  概率矩阵分解的目的就是从评分中学习到这些向量.   那么，评分矩阵R的条件概率为： , 22,11( | , , ) [ ( | ( ), )]RuiNMI TR u i u i ruip N g ss===ÕÕ R U V R U V(1) 其中2( | , ) Nxms是以m为均值，2s为方差的正态分布. ,RuiI是指示函数，当用户u对i 有评价时为1，否则为0. 而函数() gx是逻辑斯蒂函数( ) 1 / (1 )xg x e-=+，将用户评分映射到[0,1]范围内.  同时，为了防止过拟合，算法假设用户和产品的潜在向量满足高斯分布： 221221( | ) ( | 0, ),( | ) ( | 0, )Nu u UuNV i VipNpNssss====ÕÕU U IV V I    (2) 最终，通过贝叶斯推断，用户和产品的潜在特征U和V的后验概率可以由下式获得： ,2 2 22 2 22,1122 11( , | , , , )( | , , ) ( | ) ( | )[ ( | ( ), )]( | 0, ) ( | 0, )RuiR U VR U VNMI Tu i u i ruiNMu U i Vuipp p pNgN U I N Is s ss s ssss=====´´ÕÕÕÕU V RR U V U VR U VV∝      (3) 在公式(3)的基础上，利用用户评分矩阵，可以学习到用户和产品的潜在向量，从而进行预测.   3.3 SocialMF推荐算法 Ma等人提出的SocialMF[25]算法将信任传播与概率矩阵分解模型相结合，充分利用了社交网络中隐含的信息.   由于社交关系的影响，用户的行为受到它的直接好友的影响.  换句话说，用户的潜在偏好向量与他的所有相关好友相似，即用户的潜在向量可以用他的所有好友偏好的平均值表示： µ,,,uuuu v v u v vv N v Nu v uvNNÎÎÎ==åååT U T UUT     (4) 其中µU表示在给定好友的情况下估计的用户偏好向量.  同时，将信任矩阵进行归一化处理，使得,1uNuvvN Î= å T，于是得到： µ,uu v vvN Î=å U T U        (5) 与公式(3)相似，通过贝叶斯推断，可以得到如下关于用户和产品的潜在向量的后验概率： 6  计  算  机  学  报  2016年  ,2 2 2 22 2 2 22,2,122 11( , | , , , , , )( | , , ) ( | , , ) ( | )[ ( | ( ), )]( | , )( | 0, ) ( | 0, )RuiuR T U VR U T VI Tu i u i rNu u v v TvN uNMu U i Vuipp p pNgNNNs s s ss s s sssssÎ ===µ=´´´ÕÕå ÕÕÕU V R TR U V U T VR U VU T U IU I V I   (6)   其概率模型如图1所示，  图 1  基于信任传播的社会化推荐算法图模型 为了便于求解，取log 对数后验概率，如下所示： 2 2 2 2,, 2112211,, 2122 ,112ln ( , | , , , , , )1( ( ))211 221(( ) ( ))211( ) ln (( ) ln22 ( ) ln ( ) luuR T U VNMRT u i u i u iui RNNTT u u i iuu UVNTu u v v u u v vu v N v NTNMRu i R UuiVpgNKM K N Ks s s ssssssss===== Î Î===----- - -- - ´+ ´ + ´ååååå å åååU V R TI R U VU U V VU T U U T UI2n)TC s + (7)   最大化公式(7)相当于最小化如下的损失函数： 2,,1111,, 11( , , , ) ( ( ))222(( ) ( ))2uuNMRT u i u i u iuiNNTT UVu u i iuu NT Tu u v v u u v vu v N v NLglll===== Î Î=-+++ - -ååååå å åR T U V I R U VU U V VU T U U T U  (8)   在上式中，22/U R Ul s s =，22/V R Vl s s =，以及22/T R Tl s s =.  我们可以通过梯度下降法求得公式(8)的局部最优解： ,, 1,,, { | }( )( ( ) )()()uvvMR T Tu i i u i u i u iiuU u T u u v vvNT v u v v w wv u N w Ngglll=ÎÎζ¢=- ¶+ + ---ååååLI V U V U V RUU U T UT U T U    (9),, 1( )( ( ) )NR T Tu i v u i u i u i u iiigg l=¶¢ = - +¶ åLI U U V U V R VV (10) 其中，() gx¢是逻辑斯蒂函数的导数，相当于2( ) / (1 )xx g x e e-- ¢ =+. U和V的初始值是由均值为0的标准正态分布生成，在每次迭代中根据(9)(10)计算更新步进，最终得到局部最优解.   4  一种基于信任关系隐含相似度的社会化推荐算法 本节主要介绍文中所提出算法的模型推导和理论分析. 首先从信任者和被信任者的角度对用户进行建模，然后分析提出我们的信任关系隐含相似度，最终通过概率方法综合到同一代价函数当中.  除此之外，我们还给出了算法的梯度求解方法、伪代码以及算法复杂度分析.   4.1 信任者和被信任者 社会学的相关研究表明[46]，用户之间的信任是非对称的，即如果A信任用户B，并不能保证B也对A具有同样程度的信任.  也就是说，用户在作为信任者和被信任者时所表现出的偏好并不相同.   如图2中所示，A、B表示两个用户，I 表示产品. A 作为信任者接受其他用户的影响时，与B的信任关系强度为0.2，而他作为被信任者影响其他用户时，与B的信任关系强度为0.8. 如图2(a)所示，当已知B对I 的评价为5时，从信任关系强度的角度，我们可以根据A受B的影响程度，估计A对I 的评价为相似度较低的1分，反之，如图2(b)则估计B对A的评价为较相似的4分.   论文在线出版号  No.175  潘一腾等：一种基于信任关系相似度的社会化推荐算法  7    图 2   用户的信任者和被信任者示意图 我们可以看到用户作为信任者和被信任者时表现出不同的特性，因此，文中采用KMP´ÎR和KMW´ÎR分别表示用户作为信任者和被信任者时的K维偏好矩阵.   4.2 信任关系隐含相似度 社会学和计算机科学共同研究表明[36,42,47]，如果用户信任相同的对象或被相同的对象信任，那么他们之间就存在一定的潜在关联.  比如，关注或信任同一个健身专家的两个用户，有可能都在学习健身的相关知识，那么他们之间的经验就可以相互学习并进行推荐.   尽管已有文献对用户作为信任者和被信任者的情况进行建模分析[36,37,42]，并且根据信任关系中的信息对用户偏好向量进行约束.  然而，这些算法仍然存在一些不足之处需要进一步研究.   这些研究对该隐含信息的挖掘都是基于共同的信任与被信任集合，这没有考虑到间接社交关系的影响.  导致在这些集合的数量非常少（小于5）或者为0时，计算得到的信任关系隐含相似度不能准确反映用户之间的信任强度；另外，这些算法对该信息的研究没有综合考虑用户分别作为信任者和被信任者时的关联，而这使得对于信任关系的挖掘不够全面.   如图所示，A、B、C、D、E表示社交关系网络中的五个用户.  我们要从信任者的角度估计A对B的信任强度，那么，在只考虑直接的信任集合时，图3(a)和图3(b)中得到的估计值是相同的；而如果我们同时考虑了间接的社交影响，则在图3(a)中，用户A和B通过C和E的连接产生相互影响，从而AB在图3(a)中的信任强度要大于图3(b).   图 3   间接信任的影响示意图 当然，现实中的连接情况更复杂多样.  Ma 在文献[47]中的研究也表明了，用户之间的关联强度与他们之间的子图连接情况有关，而子图连接反映了用户的间接连接强度.  该研究中展示了许多复杂拓扑连接时的统计分析，虽然可以直接通过分析关系子图的情况来统计分析信任强度，然而如Ma[47]所述，各种子图的情况非常多，而且每一种连接图的信任强度都不同，这不利于对子图情况的精确建模.   因此，为了充分挖掘信任关系中的信息，我们提出一种信任关系隐含相似度的计算方法，不仅充分考虑用户同时或分别作为信任者和被信任者时的关联，而且隐含了用户之间的间接社交关联.   首先，我们采用概率矩阵分解的方法，对信任关系数据T进行分解，建立用户分别作为信任者和被信任者时的关系.  然后，根据获得的向量计算用户同时作为信任者或被信任者时的相似度.  值得注意的是，这些向量反映了社交网络中用户之间相互关系情况，不仅包含了直接联系，同时也隐含了全体社交网络的间接影响.  具体如图3(a)，在目标子空间中，A被约束与C的相关，而C与E相关，同样E与B的距离也是相关的，那么通过这样的约束，隐含的建立了A与B的间接关联.  基于此，我们计算得到了更为精确的信任关系隐含相似度.   为了建立用户分别作为信任者和被信任者时的关系，假设信任关系T由关于用户的信任向量P和W的正态分布生成.  则T的条件概率分布如下： 22,1( | , , ) [ ( | ( ), )]uNNTF u v u v Fu v Np T N g ss=Î=ÕÕ P W T P W(11)   其中，  我们采用逻辑斯蒂函数( ) 1 / (1 )xg x e-=+将TPW映射到[0,1]的范围内，以符合信任关系T的取值范围. 2,( | ( ), )Tu v u v TNg s T P W表示, uvT是由以()Tuv gPW为均值，2Fs为方差的高斯分布生成.   同时，为了防止过拟合，假设信任向量和被信任向量分别满足均值为0，方差为2Ps和2Ws的高斯分布： 221221( | ) ( | 0, ),( | ) ( | 0, )NP u PuNW v WvpNpNssss====ÕÕP P IW W I    (12)   从而，根据贝叶斯公式，可以得到信任向量和被信任向量的后验概率分布如下： 8  计  算  机  学  报  2016年  2 2 22 2 22,122 11( , | , , , )( | , , ) ( | ) ( | )[ ( | ( ), )]( | 0, ) ( | 0, )uF P WT P WNNTu v u v Fu v NNNu P v Wuvpp p pNgNNs s ss s ssss=Î===´´ÕÕÕÕP W TT P W P VT P VP I W I∝   (13)   我们对上式取对数，可以得到对数后验概率分布： 2 2 22,21221122 12ln ( , | , , , )1() 211 2211ln (( ) ln22( ) ln )uuF P WNTuvu v NTNNTT u u v vuv PW NFP u v NWpNKN K Cs s sssssss=Î===Î=- ---- - ´+ ´ +ååååååP W TT P WP P W W   (14) 在保持方差参数不变的情况下，最大化对数后验概率分布相当于最小化如下的损失函数： 2,111( , , ) ( )222uNT FF u vu v NNNTTW Pu u v vuvLll l=Î===-++ååååP W T T P WP P W W  (15) 通过梯度下降法求解得到用户的信任向量P和被信任向量W.   根据上面获得的结果，我们可以计算用户u和用户v的信任关系隐含相似度.  为了全面的利用用户的社交信息，我们分别考虑用户作为信任者和被信任者时的信任关系隐含相似度，并且综合起来提升推荐算法的精度.   用户u和用户v都作为信任者时的信任关系隐含相似度： ,PTu v u v= S P P          (16) 以及都作为被信任者时的信任关系隐含相似度： ,WT u v u v= S W W          (17) 由此，我们得到了用户分别同时作为信任者和被信任者时，用户u和v之间的信任关系隐含相似度，包括,PuvS和,WuvS.   从公式可以看出，我们的信任关系隐含相似度计算具有以下优点：（1）综合考虑了用户同时及分别作为信任者和被信任者时的关联，更加全面的利用了信任关系中的信息；（2）并不依赖于用户之间的共同好友集合，即使在没有共同好友的情况下也能计算出可靠的结果；（3）所有用户向量在计算中隐含考虑了整体的信息，即包含了间接的社交关联.  因此，我们得到了一个精确的信任关系隐含相似度量的方法.   4.3 信任强度估计 已有的工作表明[34,36,37,42]，评分和信任数据都能够在一定程度上揭示用户之间的信任强度.  然而，这些工作并没有综合考虑到两者信息对于每组用户信任强度的影响. 虽然Wang等人[37]进行了一些相关的探索，然而，他们并没有对每组信任强度都综合考虑两者信息.  为了更加精确的估计用户间的信任强度，我们提出一种综合考虑评分相似度和信任关系隐含相似度的信任强度估计方法.   我们首先计算用户u和v之间的评分相似度,RuvS，由用户的评分向量uU和vU计算得到： ,RTu v u v= S U U        (18) 我们假设用户间的信任强度矩阵为S，由关于评分相似度,RuvS、信任关系隐含相似度,PuvS和,WuvS的正太分布生成，则S的条件概率分布为： 2,,,2, , , ,1( | , , , )[ ( | ( ), )]uR P Wu v u v u v SNNR P Wu v u v u v u v Su v NpNgss=Î= + + ÕÕS S S SS S S S (19)   其中2Ss表示该高斯分布的方差，也可以理解为估计值的噪声情况.  对(19)取对数，得到对数后验概率分布： 2,,,2, , , , 2121ln ( | , , , )1( ( ))21ln2uuR P Wu v u v u v SNR P Wu v u v u v u vu v NSNSu v Npgsss=Î=Î= - - + +-ååååS S S SS S S S  (20) 为了最大化  (20)，我们需要最小化如下的损失函数： 2, , , ,12,1( , , , )ˆ( ( ))2ˆ( ( ))2uuSNR P W Su v u v u v u vu v NNT T T Su v u v u v u vu v NLggll=Î=Î= - + += - + +ååååS U P WS S S SS U U P P W W  (21) 论文在线出版号  No.175  潘一腾等：一种基于信任关系相似度的社会化推荐算法  9   显然，当,ˆuvS等于,,, ()R P Wu v u v u vg ++ SSS时，取得最小值0. 但是为了同时兼顾其他因素，我们将  (21)作为关于信任强度矩阵ˆS的正则化约束项，与(8)进行结合，得到最终有效的估计值.  值得注意的是，  (21)作为正则化项时，当Sl ® +¥，,ˆuvS将完全等于,,, ()R P Wu v u v u vg ++ SSS；但考虑到即使融合了评分和信任关系隐含相似度，得到的信任强度估计仍然存在噪声误差，我们将在实验中选择表现最好的参数作为最终结果.   4.4 算法模型 在以上分析的基础上，为了充分挖掘社交关系中的隐含信息，本文提出一种基于信任关系隐含相似度的社会化推荐算法SocialIT（Social Recommendation Algorithm based on Implict Similarity in Trust）.   首先，采用概率矩阵分解PMF[43]的方法对评分进行建模，并且考虑了用户和产品偏置的影响[17]： ,ˆ()UVu i u i u ig = + + R U V b b      (22) 其中，Uub和Vib分别表示用户u和产品i的评分偏置.   然后，本文采用与SocialMF[25]算法相同的假设，即用户偏好与他的信任好友的平均值相似，如公式(4)所示.  不同之处在于，文中使用估计的信任强度矩阵ˆS代替信任矩阵T：  µ,*,,ˆuuuu v vvNuu v vvNuvvNÎÎÎ==åååSUU S US          (23) 其中，*, , ,ˆ ˆ ˆuu v u v u v vN Î= å S S S表示归一化的信任强度.   因此，基于SocialMF[25]算法的公式(8)，我们综合考虑了评分相似和信任关系隐含相似度的影响，结合公式(15)、 (21)、    (22)和(23)，得到我们的代价函数为： 2, , ,1111**,, 12,12,111ˆ() 222(( ) ( ))2( ( ))2( ( ))222uuuuNMRu i u i u iuiNNTT UVu u i iuu NT Tu u v v u u v vv N v NuNT T T Su v u v u v u vu v NNT Fu v u vu v NNTTW Pu u uuEIggllllll l====ÎÎ ==Î=Î==-+++ - -+ - + ++-++ååååå å ååååååRRU U V VU S U U S US U U P P W WT P WP P W W1Nuu=å (24) 通过最小化代价函数(24)，我们可以得到用户和产品的评分向量U和V，然后根据公式    (22)对用户评分进行预测.   SocialIT算法的代价函数(24)对应的概率图模型如图4所示，文中算法SocialIT与SocialMF[25]算法相比，主要有以下特点：(1)  SocialIT 并不是将每个好友对用户的影响视为等同，而是采用估计的信任强度矩阵S代替信任矩阵T；(2)  SocialIT利用概率矩阵分解的方法得到信任者和被信任者向量，并给予此计算信任关系隐含相似度，从而隐含了用户间的间接社交影响；(3)SocialIT 同时考虑了评分相似和信任关系隐含相似度对每组用户间信任强度的影响，得到更为精确的估计结果，进而提高了推荐精度.    图 4   SocialIT算法示意图 4.5 问题求解 文中采用梯度下降法求解得到公式(24)的局部最优解，具体的计算过程如算法1所示，各变量的梯度计算如下： 10  计  算  机  学  报  2016年  , , , ,1*,**,, { | }, , ,, , ,{ | }ˆ ˆ( )( ( ) )()()ˆ ˆ[( ( )) ( ) ]ˆ ˆ[( ( )) ( ) ]uvvuvMRu i i u i u i u iiuU u T u u v vvNT v u v w v vwNv u NS u v u v u v vvNS v u v u v u vv u NEgggggglllll=ÎÎÎÎζ¢=- ¶+ + ---¢ +-¢ +-ååååååI V R R RUU U S US U S US S S US S S U   (25) ,, 1( )( ( ) )NR T Tu i v u i u i u i u iiiEgg l=¶¢ = - +¶ åI U U V U V R VV     (26) *, , ,,,,2,ˆ( ( )) ( )()uuuuS u v u v T u u v vvNuvv u v u v vv N v NuvvNEg llÎÎÎζ= - + -¶-ååååS S U S USU S S US(27) , , ,, , ,,ˆ ˆ( ( )) ( )ˆ ˆ( ( )) ( )( ( )) ( )uS u v u v u v vuS v u v u v u vTT F u v u v u v vvNPuEggggggllllζ¢ =- ¶¢ +-¢ +-+åS S S PPS S S PT P W P W WP   (28) , , ,, , ,,ˆ ˆ( ( )) ( )ˆ ˆ( ( )) ( )( ( )) ( )uS u v u v u v vuS v u v u v u vTT F u v u v u v vvNWuEggg g Wggllllζ¢ =- ¶¢ +-¢ +-+åS S S WWS S ST P W P W PW   (29) 其中，为了简洁起见，我们用,ˆuvS表示T T Tu v u v u v ++ U U P P W W，*, uvS  表示归一化的信任强度*, , ,uu v u v u v vN Î= å S S S.   算法1.    SocialIT 算法 输入：用户-产品评分数据R，用户-用户社交数据T，潜在特征维数K，正则化系数Ul、Vl、Tl、Sl、Pl和Wl，学习率a，迭代次数L.   输出：用户评分偏好向量U，产品特征向量V，用户和产品偏置Ub和Vb，用户信任者向量P，用户被信任者向量W，用户信任强度矩阵S.   BEGIN 1. 初始化：随机初始化U，V，P，W，Ub和Vb（我们采用方差为0.1的标准正态分布进行初始化），信任强度矩阵S的元素全部初始化为1.  2. WHILE lL<  DO： 3.       FOR ALL , uir ÎR，DO: 4.      uuuEa¶¬-¶UUU，iiiEa¶¬-¶VVV   5.      UUuu UuEa¶¬-¶bbb， VVii ViEa¶¬-¶bbb 6.      uuuEa¶¬-¶PPP  ，uuuEa¶¬-¶WWW 7.      ,,,u v u vuvEa¶¬-¶SSS 8.       END FOR 9.      1 ll¬+ 10. End WHILE END 4.6 SocialIT算法复杂度分析 文中算法SocialIT的求解过程中，最主要的计算代价在于损失函数E以及每个变量对应梯度的计算.   对于损失函数E，根据文献[25]的分析，其对应的时间复杂度为() O NrK NtK +.  其中，N表示用户数量，K表示算法维度，r表示用户平均评分数量，表示用户平均信任关系数量.  由于评分和信任数据通常是稀疏的，比如表1所示，r、t和K的值都比较小.  因此，损失函数E的计算是非常快的，且与总的用户数量N和算法维度K成线性正比关系.   相对应的，梯度计算的复杂度的时间复杂度为2() O NrK MrK Nt K NtK + + +，其中M表示产品数量. 由于r、t和K的值都比较小，因此，梯度的计算复杂度也不算高，且与N成线性正比关系.   综上，文中算法SocialIT的算法复杂度主要受用户数量N和产品数量M的影响，适合于大数据情况下的应用.   5  实验结果和分析 本节主要展示SocialIT 算法的与其他相关算法的实验结果.  我们首先介绍实验采用了数据集和评价方法，然后设计了四组实验从不同的角度对比分析了本文算法的性能情况.   论文在线出版号  No.175  潘一腾等：一种基于信任关系相似度的社会化推荐算法  11   5.1 数据集 为了避免实验的偏向性，我们选择两个独立的数据集1进行算法验证，Epinions和Ciao. 这两个公开数据集同时包含了评分数据和在线社交数据，该数据集由Tang等人[48]在2011年收集并公开.   Epinions2和Ciao3是两个著名的大众消费点评网站，主要市场分别在美国和欧洲.  在这两个网站上，任何用户都可以在注册后对所有的商品进行评分和评论，同时也可以浏览其他用户对商品的评分和评价，进而帮助用户做出更加有利的决定.  与此同时，用户可以与信任的用户建立好友关系，从而建立社交关系网络.   Tang等人[48]在这两个网站上爬取了从1999年至2011年的评分和社交数据，时间范围非常广泛，是最新的公开社交数据集之一[48-50].    这两个网站的评分范围为1~5（1表示“不喜欢”，5表示“喜欢”），用户之间的信任关系是二值的，即只能取1或0，分别对应信任或非信任关系.  文中研究的目的就是估计用户之间的潜在信任度，从而提高推荐精度.   在我们的实验中，采用与Wang等人[37]类似的预处理. 即过滤掉评分数量小于5 的用户和产品，并且在信任数据也只保留相对应的用户.   表1  Epinions数据集的统计特性 数据集  Epinions  Ciao 用户数量  22166  7375 产品数量  296277  106797 评分记录  922267  284086 信任记录  300548  111781 用户平均评分数量  41.61  38.52 商品平均评分数量  3.11  2.66 用户平均信任数量  13.56  15.16 评分稀疏度  0.99986  0.99964 信任稀疏度  0.9988  0.9959 5.2 评价方法 本文算法的任务之一是预测用户对产品的评分，通常希望算法越精确越好.  为了评估本文算法的性能，我们选择两种流行的精确度指标[51]，平均绝对误差（Mean  Absolute Error，MAE）和均方根误差(Root  Mean  Squared  Error，RMSE). MAE和RMSE适合于预测的场景，反映了算法预测评分的准确度.  在仅考虑准确度的情况下，他们的值越低，算法的性能越好.                                                                    1 http://www.jiliang.xyz/trust.html 2 https://en.wikipedia.org/wiki/Epinions 3 https://en.wikipedia.org/wiki/Ciao_%28website%29 平均绝对误差MAE的计算公式为： µ,,( , )1||ijiji j IMAE R RN Î=-å            (30)   其中，N表示预测评分的数量，I 表示所有测试集的数据，µ, ij R表示预测评分，, ijR表示真实评分.   相对应的，均方根误差RMSE的计算公式为： µ 2,,( , )()ijiji j IRRRMSENÎ-=å         (31)   很多推荐系统领域的研究表明[21]，反映评分预测能力的误差率指标（MSE，RMSE）并不能完全地表征算法的推荐性能.  而与实际场景更为相关的是Top-N项目推荐性能. 因此，为了更加全面的验证本文算法的性能，我们将SocialIT算法与面向Top-N项目推荐任务的BPR算法相结合[21]，并采用三种反映击中率性能的指标进行度量，包括精确率（Precision）、召回率（Recall）和排序指标NDCG（Normalized Discounted Cumulative Gain）.      采用uLI¢  表示用户u的项目推荐序列，以及uLI表示用户u在测试数据中预测的项目推荐序列，TestU  表示待测试的用户集合，则可以得到Precision和Recall的计算公式分别为： | | / | | @Testu u uuULI L Precision I LI nÎ= ¢¢ å I  (32) Re @ | | / | |Testu u uuULI L ca LI ll n I΢ = ¢ å I    (33) 相对应的，排序指标@ NDCG n的计算公式表示为： 121 2 1@log ( 1)iTesttkiuU uNDCG nYi=Î-=+åå    (34)   其中，uY表示用户u的最大@ DCG n值. 1it =表示击中，否则0it =.   5.3 实验设计         为了全面的测试算法在一般情况和稀疏数据时的表现，我们的实验设计与Yao等人[36]类似，采用以下三种不同的策略从不同的角度对算法进行测试，以验证文中算法的有效性.   （1）全局测试：我们验证算法在一般情况下的表现.  采用交叉验证的方法测试算法性能.  具体来说，就是将数据集12  计  算  机  学  报  2016年  随机分成5等份，每次测试将其中4份作为训练数据，剩下一份作为测试数据.  总共进行5次测试，保证所有的数据都被测试一次.  最终得到的平均精度作为算法的评估标准，从而保证算法验证的可靠性. （2）不同评分稀疏度的测试：采用与（1）相同的设定，但在验证测试集时，我们分别验证具有不同评分数量（即稀疏程度）的用户表现，从而得到算法在不同评分稀疏度时的性能情况.   （3）不同信任稀疏度的测试：采用与（1）相同的设定，但在验证测试集时，分别验证具有不同信任关系数量用户的表现，从而得到算法在不同信任稀疏度时的性能情况.   （4）Top-N项目推荐测试：验证算法预测的最符合用户偏好的项目与用户真实偏好项目的差别，为此，我们采用Precision、Recall和NDGC对算法性能进行度量.  并且也采用（1）中描述的交叉验证方法，进行5次测试，保证测试的可靠性.   5.4 比较算法及参数设定 为了对比说明本文算法在评分预测和项目推荐中的性能，我们选择两组算法分别进行对比与分析.   对于评分预测任务，我们选择了经典的推荐算法PMF[43]以及其他社会化推荐算法： 1) PMF[43]：采用概率矩阵分解的方法，将用户和产品映射到低维向量空间，提高了算法处理大量数据的能力和精度.   2) Sorec[23]：由Ma等人[23]提出的采用概率矩阵分解的方法建立用户偏好与社交好友之间的关联.   3) SocialMF[25]：由Jamali等人[25]提出的基于信任传播的社会化推荐算法.  该算法假设每个好友对用户的影响力相同，本文算法在此基础上，综合考虑了用户评分和信任关系隐含相似度的影响. 4) Soreg[35]：由Ma等人[35]提出，采用评分相似作为用户间的信任度量，并且改进了SocialMF中的均值传播方式.   5) TrustMF[36]：由Yao等人[36]提出，对于用户作为信任者和被信任者时的情况进行分别建模，并进行集成得到推荐结果.   6) TS_MF[37]：由Wang等人[37]提出，考虑了用户评分相似和信任关系中隐含信息的影响.   对于项目推荐任务，我们选择PMF算法以及其他面向排序的推荐算法进行对比： 1) PMF[43]：概率矩阵分解方法，将用户和产品映射到低维空间，并以此预测用户对其他产品的喜好程度.   2) BPR[21]：Rendle等人将排序学习算法应用于推荐系统，通过学习用户对一对产品间的偏好关系，从而预测用户最有可能偏好的产品 3) GBPR[52]：Pan等人在该工作中结合了社交群体对于用户偏好的影响，从而提高了项目推荐质量.   4) SBPR[53]：Zhao等人考虑了用户与社交好友选择的产品之间的直接关联，有效利用了社交关系对于项目推荐的影响.   为了更为得出更为可靠的对比结果，我们根据作者推荐的参数值以及多次参数调优的结果，分别选择最优的参数作为最终的对比结果，并且验证了算法在特征向量维度分别为5、10和20时的表现.  本文实验代码在公开的算法库Librec1的基础上进行改进，该算法库对SocialMF进行了实现，文中运行结果与其给出的实验结果一致. 5.5 实验结果与分析 实验1. 全局测试. 为了使测试不失偏向性，我们在Epinions和Ciao数据集上进行了测试，并且验证了算法在维度为5、10和20精度.  在表2中展示了各种算法在Epinions和Ciao数据集中的实验结果，从中我们可以看出： (1)  社会化推荐算法（如SocialMF、Soreg等）在MAE和RMSE上都优于仅依赖于用户评分的概率矩阵分解方法PMF，这表明充分利用社交关系中隐含的用户偏好信息能够有效提升推荐算法的精度.   (2)  本文算法SocialIT相比于其他社会化推荐算法，在MAE和RMSE上有明显的提高.  值得注意的是，考虑了用户间信任强度的算法（Soreg和TS_MF）以及考虑了信任者和被信任者关系的算法（TrustMF 和TS_MF）都优于SocialMF 算法，可见对用户间信任强度以及用户角色（信任者和被信任者）进行建模都能提高社会化推荐算法的结果.  而文中算法更进一步，利用了信任者和被信任者向量对用户间信任强度进行修正，从而得到了更优的推荐质量.   (3)  本文算法在Epinions和Ciao数据集上都能有效提升推荐精度.  可见，文中算法对于独立收集的不同数据集，也能保持良好的性能，进而验证了文中算法提出的信任关系隐含相似度具有可靠的鲁棒性，并不对特定的数据集有明显的偏向性.   (4)  本文算法SocialIT在维度增加的时候，性能有一定程度的退化，但相比于其他算法仍然具有明显的竞争优势. 这是由于文中算法对每个用户从三个维度进行了建模，包括（评分者、信任者和被信任者），从而实际上每个用户的维度是单个向量维度的3倍，这增强了算法的拟合能力的同时也增加了过拟合的风险.  从表2也可以看出，在维度为5时的性能比其他维度都更优.  因此，本算法更为适合采用较低                                                                 1 http://www.librec.net 论文在线出版号  No.175  潘一腾等：一种基于信任关系相似度的社会化推荐算法  13   的向量维度.   实验2.  不同评分稀疏度的测试 为了测试算法对于评分稀疏度的鲁棒性，图5中展示了各种算法对于不同评分稀疏度（评分数量）的表现.  不失一般性，我们分别统计了Epinions和Ciao的结果，其中，横轴表示用户评分数量，纵轴表示MAE和RMSE. 从图5中我们可以看出： (1)  在不同评分稀疏的情况下，SocialIT算法的精度始终明显优于其他算法.  这表明，对于不同评分数量的用户，文中算法都能够有效挖掘社交数据中的隐含信息，从而提高算法的推荐精度，也使得算法对于各种评分数量用户都具有良好的鲁棒性.     (2)  对于评分数据稀疏（评分数量<20）的情况，SocialIT算法相比于其他算法有明显的提高.  随着评分数量的增加，SocialIT在MAE上与其他算法的差距有所减小，但依然优于其他算法.  这表明，在评分稀疏的情况下，文中算法利用信任关系隐含相似度能够有效的修正推荐结果，得到更好的推荐精度.   (3)  对于评分数据稠密（评分数量>100）的情况，相比于仅采用评分数据的PMF算法，SocialIT有明显的提高，而其他社会化推荐算法则提高较少.  这表明，随着数据量的增多，SocialIT算法依然能够提取社交网络中的有效信息，从而提高推荐质量.     实验3.  不同信任稀疏度的测试 为了测试算法对于信任稀疏度的鲁棒性，图6中展示了各种算法对于不同信任稀疏度（信任数量）的表现.  从图中可以看出： (1)  在不同信任稀疏的情况下，SocialIT算法的精度始终明显优于其他算法.  这表明，通过融合评分相似和信任关系隐含相似度，能够有效的提高社会化推荐算法对于不同信任稀疏度时的鲁棒性.     (2) 在信任数据稀疏（信任数量<10）时，SocialIT算法在MAE和RMSE精度上明显好于其他算法.  这表明，在信任稀疏的情况下，SocialIT算法通过评分相似度和信任关系隐含相似度修正对信任强度的估计，得到了更为精确的信任强度估计以及推荐结果.   (3)  随着信任数量的增加，SocialIT的MAE精度与其他算法的差距有所减小，RMSE仍然明显优于其他算法.  特别是在信任数量大于100时，其他社会化推荐算法的RMSE精度与PMF相比差别非常小，而SocialIT依然能够有效的提高算法精度.  对于稠密社交数据，用户间的直接和间接交互信息更加丰富.  相比于其他算法，SocialIT算法通过信任关系隐含相似度，能够更为有效地挖掘和提取，进而提高推荐精度.   实验4. Top-N项目推荐测试 为了测试算法对于项目推荐任务的表现，我们将本文算法SocialIT与BPR算法进行结合，得到一个面向项目推荐任务的推荐算法，并与其它算法进行对比.  在表3中展示了各算法在精确率（Precision）、召回率（Recall）和排序指标NDCG（Normalized Discounted Cumulative Gain）上的表现.   从中我们可以看出： (1)  在这些指标上直接面向排序预测的算法（BPR、GBPR、SBPR及BPR+SocialIT）明显好于面向评分预测的算法（PMF）.  这是由于排序类算法学习的目标就是获得更好的排序预测，这与Top-N项目预测任务的目标更加吻合. 而评分预测类算法则先预测评分，再根据评分预测排序，这样一个间接预测的过程使得该类算法的排序预测表现远不如排序类算法.  因此，本文采用排序算法BPR与SocialIT算法相结合，进而产生Top-N项目推荐结果.   (2)  我们的算法BPR+SocialIT相对于其它利用社会关系信息的算法（GBPR和SBPR）有明显的提升，尤其在Ciao数据集中提升明显.  这表明，文中算法综合考虑评分相似和信任关系隐含相似度，能够有效的提升Top-N项目推荐的准确率.   (3)  各算法在Epinions数据集的表现远不如Ciao数据集.  这是由于Epinions数据集的候选项目数量远大于Ciao（见表1），使得在该数据集进行Top-N项目推荐任务更为困难.   (4)  BPR+SocialIT 算法在Epinions中的提高程度相比Ciao有所下降，但仍然优于其他算法.  这说明，文中算法在候选项目数量非常大的情况下（大于2万），对于算法质量的提高有一定的影响，但是通过挖掘社交关系中的隐含信息，也能够一定程度上提高排序推荐质量.  因此，本算法更为适合于候选数量较小的情况.          14  计  算  机  学  报  2016年  表2  在Epinions和Ciao数据集的精度表现 数据集  度量  PMF  Sorec  SocialMF  Soreg  TrustMF  TS_MF  SocialIT  提高 Epinions K=5 MAE  0.9095  0.8406  0.8714  0.8332  0.8282*  0.8467  0.8046  2.85% RMSE  1.1347  1.0758  1.0809  1.0674*  1.0722  1.0811  1.0403  2.54% Epinions K=10 MAE  0.9098  0.8463  0.8549  0.8396*  0.8428  0.8463  0.8086  3.69% RMSE  1.1491  1.1047  1.0904  1.1109  1.1208  1.0804*  1.0420  3.55% Epinions K=20 MAE  0.9164  0.8829  0.8730  0.8839  0.8934  0.8461*  0.8156  3.60% RMSE  1.1581  1.2260  1.1932  1.2399  1.2893  1.0806*  1.0485  2.97% Ciao K=5 MAE  0.8214  0.7987  0.7831  0.7781  0.7534*  0.7555  0.7370  2.08% RMSE  1.0483  1.0308  1.0087  0.9924  0.9794*  0.9819  0.9605  1.93% Ciao K=10 MAE  0.8179  0.8273  0.7849  0.7632  0.7520*  0.7559  0.7414  1.41% RMSE  1.0438  1.0645  1.0100  1.0011  1.0030  0.9823*  0.9729  0.96% Ciao K=20 MAE  0.8196  0.8482  0.7815  0.7665  0.7736  0.7550*  0.7440  1.46% RMSE  1.0455  1.1620  1.0060  1.0970  1.1452  0.9812*  0.9773  0.40%   表3  在Epinions和Ciao数据集的Top-N项目推荐测试 数据集  算法  Precision@5  Precision@10  Recall@5  Recall@10  NDCG@10 Epinions  PMF  0.007704  0.006017  0.006905  0.010602  0.009350 BPR  0.011383  0.008993  0.011025  0.016731  0.015029 GBPR  0.011437  0.009058  0.011133  0.016878  0.015046 SBPR  0.010388  0.007971  0.010206  0.015143  0.013100 BPR+SocialIT  0.011558  0.009128  0.011277  0.016936  0.015127 提高  1.06%  0.78%  1.30%  0.94%  0.81% Ciao  PMF  0.019619  0.012283  0.017029  0.021918  0.021108 BPR  0.023968  0.019158  0.020578  0.032457  0.027824 GBPR  0.024999*  0.019932*  0.020382  0.033383*  0.028091* SBPR  0.022064  0.017557  0.020544*  0.032184  0.027405 BPR+SocialIT  0.025329  0.020961  0.022685  0.036399  0.031064 提高  1.32%  5.16%  10.4%  9.03%  10.6%  论文在线出版号  No.175  潘一腾等：一种基于信任关系相似度的社会化推荐算法  15    图 5   各算法在不同评分稀疏度情况下的精度  图 6   各算法在不同信任稀疏度情况下的精度 6  结论与工作展望 为了更精确的度量用户与社交好友的相似度，本文提出了一种基于信任关系隐含相似度的社会化推荐算法.  与现有算法相比，本文首先对信任矩阵进行分解，避免了皮尔逊相关或余弦距离必须要有共同对象的要求，同时，充分考虑信任关系隐含相似对用户相似度的直接影响，提高了算法对16  计  算  机  学  报  2016年  于数据稀疏问题的精度，最后，本文共同考虑了评分相似和信任关系隐含相似对用户相似度的影响，进一步提高了推荐精度.   在Epinions数据集上的实验表明，本文算法能够有效提高推荐精度，特别是，对于稀疏用户，能够取得明显的提高.   本文重点考虑了信任关系隐含相似度对社会化推荐算法的提升.  其他相关问题，比如有向信任传递、时间漂移、产品特征等，将在今后的工作中进一步探索.   参 考 文 献 [1]    Tang  J,  Hu  X,  Liu  H.  Social  recommendation:  a  review.  Social Network Analysis and Mining, 2013, 3(4): 1113-1133 [2]   Ambulkar  H  D,  Pathan  A.  Recommender  System  Challenges  and Methodologies  in  Social  Network:  Survey.  International  Journal  of Science and Research, 2015, 4(11): 286-289 [3]  Yang X, Guo Y, Liu Y, et al. A survey of collaborative filtering based social  recommender  systems.  Computer  Communications,  2014,  41: 1-10 [4]   Koren  Y,  Bell  R:  Advances  in  Collaborative  Filtering,  Recommender Systems Handbook. Berlin, Germany: Springer, 2015: 77-118 [5]  Ning  X,  Karypis  G:  Recent  Advances  in  Recommender  Systems  and Future  Directions, Proceedings  of  the International  Conference  on Pattern  Recognition  and Machine  Intelligence, Warsaw, Poland, 2015: 3-9 [6]  Wang X,  Wang  Y.  Improving  content-based  and  hybrid  music recommendation  using  deep  learning.  Proceedings  of  the  ACM International  Conference  on  Multimedia,  Orlando, USA, 2014: 627-636 [7]   Wang  C,  Blei  D  M.  Collaborative  topic  modeling  for  recommending scientific articles. Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, San Diego, USA 2011: 448-456 [8]  Hu L, Cao J, Gu Z. Service Discovery and Recommendation in Rough Hierarchical  Granular  Computing.  Proceedings  of  the  2010  IEEE Asia-Pacific  Services  Computing  Conference  (APSCC),  Hangzhou, China, 2010: 191-198 [9]   Pan  W,  Xia  S,  Liu  Z,  et  al.  Mixed  factorization  for  collaborative recommendation  with  heterogeneous  explicit  feedbacks.  Information Sciences, 2016, 332: 84-93 [10]  Ji  K,  Sun  R,  Li  X,  et  al.  Improving  matrix  approximation  for recommendation  via  a  clustering-based  reconstructive  method. Neurocomputing, 2016, 173: 912-920 [11] Sun  Z:  Exploiting  Item  and  User  Relationships  for  Recommender Systems,  Proceedings  of  the  International  Conference  on  User Modeling,  Adaptation,  and  Personalization,  Dublin,  Ireland, 2015: 397-402 [12]  Wang  H,  Wang  N,  Yeung  D-Y.  Collaborative  Deep  Learning  for Recommender  Systems.  Proceedings  of  the  21th  ACM  SIGKDD International  Conference  on  Knowledge  Discovery  and  Data  Mining, Sydney, Australia, 2015: 1235–1244 [13] Guo  G.  Improving  the  Performance  of  Recommender  Systems  by Alleviating the Data Sparsity and Cold Start Problems. Proceedings of the  Twenty-Third  International  Joint  Conference  on  Artificial Intelligence. Beijing, China, 2013: 3217–3218 [14] Chen C C, Wan Y-H, Chung M-C, et al. An effective recommendation method  for  cold  start  new  users  using  trust  and  distrust  networks. Information Sciences, 2013, 224: 19-36 [15] Chen  KeHan,  Han  PanPan,  Wu  Jian,  User  Clustering  Based  Social Network  Recommendation.  Chinese  Journal  of  Computers,  2013, 36(2): 349-359 (in chinese) (陈克寒,  韩盼盼,  吴健.  基于用户聚类的异构社交网络推荐算法. 计算机学报, 2013, 36(2): 349-359) [16] Huang ChuangGuang, Yin Jian, Wang Jing, et al. Uncertain Neighbors' Collaborative Filtering Recommendation Algorithm.  Chinese Journal of Computers, 2010, 33(8): 1369-1377 (in chinese) (黄创光,  印鉴,  汪静,  et  al.  不确定近邻的协同过滤推荐算法.  计算机学报, 2010, 33(8): 1369-1377) [17]  Koren  Y.  Factorization  meets  the  neighborhood:  a  multifaceted collaborative  filtering  model. Proceedings  of  the 14th  ACM SIGKDD international conference on Knowledge discovery and data mining, Las Vegas, USA, 2008: 426-434 [18]  Lu  Yijing,  Cao  Jian.  Topic  Model  Based  Hierarchical  Service Recommendation.  Journal  of  Chinese  Computer  Systems,  2015, 36(11): 2457-2461 (in chinese) (陆怡静,  曹健.  基于主题模型的多层次服务推荐.  小型微型计算机系统, 2015, 36(11): 2457-2461) [19]  Tang  J,  Wu  S,  Sun  J,  et  al.  Cross-domain  collaboration recommendation. Proceedings of the 18th ACM SIGKDD international conference  on  Knowledge  discovery  and data  mining, Beijing,  China, 2012: 1285-1293 [20] Gao  S,  Luo  H,  Chen  D,  et  al.:  Cross-domain  recommendation  via cluster-level  latent  factor  model,  Proceedings  of  the Joint  European Conference  on  Machine  Learning  and  Knowledge  Discovery  in Databases, Prague, Czech Republic, 2013: 161-176 [21]  Rendle  S,  Freudenthaler  C,  Gantner  Z,  et  al.  BPR:  Bayesian personalized  ranking  from  implicit  feedback.  Proceedings  of  the Twenty-Fifth  Conference  on  Uncertainty  in  Artificial  Intelligence,   论文在线出版号  No.175  潘一腾等：一种基于信任关系相似度的社会化推荐算法  17   Montreal, Canada, 2009: 452-461 [22] Li  S,  Kawale  J,  Fu  Y.  Deep  Collaborative  Filtering  via  Marginalized Denoising  Auto-encoder. Proceedings  of  the  24th  ACM  International on  Conference  on  Information  and  Knowledge  Management, Melbourne, Australia, 2015: 811-820 [23] Ma  H,  Yang  H,  Lyu  M  R,  et  al.  Sorec:  social  recommendation  using probabilistic  matrix  factorization.  Proceedings  of  the  17th  ACM conference  on  Information  and  knowledge  management, Napa  Valley, USA, 2008: 931-940 [24] Ma  H,  King  I,  Lyu  M  R.  Learning  to  recommend  with  social  trust ensemble.  Proceedings  of  the  32nd  international  ACM  SIGIR conference  on  Research  and  development  in  information  retrieval,   Boston, USA, 2009: 203-210 [25]  Jamali  M,  Ester  M.  A  matrix  factorization  technique  with  trust propagation for recommendation in social networks. Proceedings of the fourth  ACM  conference  on  Recommender  systems, Barcelona,  Spain, 2010: 135-142 [26]  Mcpherson  M,  Smith-Lovin  L,  Cook  J  M.  Birds  of  a  feather: Homophily in social networks. Annual review of sociology, 2001, 27: 415-444 [27] Lazer D, Pentland A S, Adamic L, et al. Life in the network: the coming age of computational social science. Science, 2009, 323(5915): 721 [28] Chen  C,  Li  D,  Zhao  Y,  et  al.  WEMAREC:  Accurate  and  Scalable Recommendation  Through  Weighted  and  Ensemble  Matrix Approximation.  Proceedings  of  the  38th  International  ACM  SIGIR Conference  on  Research  and  Development  in  Information  Retrieval. Santiago, Chile, 2015: 303–312 [29] Moradi P, Ahmadian S. A reliability-based recommendation method to improve  trust-aware  recommender  systems.  Expert  Systems  with Applications, 2015, 42(21): 7386-7398 [30] Fang H, Guo G, Zhang J. Multi-faceted trust and distrust prediction for recommender systems. Decision Support Systems, 2015, 71: 37-47 [31] Guo  G,  Zhang  J,  Yorke-Smith  N.  Leveraging  multiviews  of  trust  and similarity  to  enhance  clustering-based  recommender  systems. Knowledge-Based Systems, 2015, 74: 14-27 [32] Fazeli S, Loni B, Bellogin A, et al. Implicit vs. Explicit Trust in Social Matrix  Factorization.  Proceedings  of  the  8th  ACM  Conference  on Recommender Systems. Foster City, USA, 2014: 317–320 [33] Choo  E,  Yu  T,  Chi  M,  et  al.  Revealing  and  Incorporating  Implicit Communities  to  Improve  Recommender  Systems.  Proceedings  of  the Fifteenth ACM Conference on Economics and Computation. Palo Alto, USA, 2014: 489–506 [34] Yang  B,  Lei  Y,  Liu  D,  et  al.  Social  collaborative  filtering  by  trust. Proceedings  of  the  Twenty-Third  international  joint  conference  on Artificial Intelligence, Beijing, China, 2013: 2747-2753 [35] Ma  H,  Zhou  D,  Liu  C,  et  al.  Recommender  systems  with  social regularization. Proceedings of the fourth ACM international conference on Web search and data mining, Hong Kong, China, 2011: 287-296 [36] Yao  W,  He  J,  Huang  G,  et  al.  Modeling  dual  role  preferences  for trust-aware  recommendation.  Proceedings  of  the  37th  international ACM  SIGIR  conference  on  Research  &  development  in  information retrieval, Gold Coast, Australia, 2014: 975-978 [37] Wang  M,  Ma  J.  A  novel  recommendation approach based on users’ weighted  trust  relations  and  the  rating  similarities.  Soft  Computing, 2015, 20(10): 3981–3990 [38] Jamali M, Ester M. Trustwalker: a random walk model for combining trust-based  and  item-based  recommendation. Proceedings  of  the  15th ACM SIGKDD international conference on Knowledge discovery and data mining, Paris, France, 2009: 397-406 [39] Au Yeung C-M, Iwata T. Strength of social influence in trust networks in  product  review  sites. Proceedings  of  the  fourth  ACM  international conference on Web search and data mining, Hong Kong, China, 2011: 495-504 [40]  Guo  Lei,  Ma  Ju,  Chen  Zhumin.  Trust  Strength  Aware  Social Recommendation  Method.  Journal  of  Computer  Research  and Development, 2015, 50(9): 1805-1813 (in chinese) (郭磊,  马军,  陈竹敏.  一种信任关系强度敏感的社会化推荐算法. 计算机研究与发展, 2015, 50(9): 1805-1813) [41] Guo Lei, Ma Ju, Chen Zhumin, et al. Incorporating Item Relations for Social  Recommendation. Chinese  Journal  of  Computers,  2014,  37(1): 219-228 (in chinese) (郭磊,  马军,  陈竹敏,  et  al.  一种结合推荐对象间关联关系的社会化推荐算法.  计算机学报, 2014, 37(1): 219-228) [42] Wang T, Jin X, Ding X, et al. User Interests Imbalance Exploration in Social Recommendation: A Fitness Adaptation. Proceedings of the 23rd ACM  International  Conference  on  Conference  on  Information  and Knowledge Management, Shanghai, China, 2014: 281-290 [43]  Mnih  A,  Salakhutdinov  R.  Probabilistic  matrix  factorization. Proceedings of the Advances in neural information processing systems, Vancouver, Canada, 2007: 1257-1264 [44]  Sarwar  B,  Karypis  G,  Konstan  J,  et  al.  Item-based collaborative filtering  recommendation  algorithms.  Proceedings  of  the  10th international  conference  on  World  Wide  Web,  Hong  Kong,  China, 2001: 285-295 [45] Koren  Y,  Bell  R,  Volinsky  C.  Matrix  factorization  techniques  for recommender systems. Computer, 2009, (8): 30-37 [46]  Castelfranchi  C,  Falcone  R.  Trust  theory:  A  socio-cognitive  and computational model. New York, USA: John Wiley & Sons, 2010   18  计  算  机  学  报  2016年  [47] Ma H. On measuring social friend interest similarities in recommender systems. Proceedings of the 37th international ACM SIGIR conference on  Research  &  development  in  information  retrieval, Gold  Coast, Australia, 2014: 465-474 [48] Tang  J,  Gao  H,  Liu  H.  mTrust:  discerning  multi-faceted  trust  in  a connected  world.  Proceedings  of  the  fifth  ACM  international conference  on  Web  search  and  data  mining, Seattle,  USA, 2012: 93-102 [49] Massa P, Avesani P. Trust-aware recommender systems. Proceedings of the  2007  ACM  conference  on  Recommender  systems, Minneapolis, USA, 2007: 17-24 [50] Richardson M,  Domingos P. Mining  knowledge-sharing sites  for  viral marketing.  Proceedings  of  the  eighth  ACM  SIGKDD  international conference  on  Knowledge  discovery  and  data  mining, Edmonton,   Canada, 2002: 61-70 [51]  Shani  G,  Gunawardana  A:  Evaluating  recommendation  systems, Recommender  systems  handbook.  Berlin,  Germany: Springer,  2011: 257-297 [52] Pan W, Chen L. GBPR: Group Preference Based Bayesian Personalized Ranking  for  One-Class  Collaborative  Filtering.  Proceedings  of  the Twenty-Third  international  joint  conference  on  Artificial  Intelligence, Beijing, China, 2013: 2691-2697 [53] Zhao T, Mcauley J, King I. Leveraging Social Connections to Improve Personalized  Ranking  for  Collaborative  Filtering.  Proceedings  of  the 23rd ACM International Conference on Conference on Information and Knowledge Management. Shanghai, China, 2014: 261–270    PAN Yi-Teng, born in 1988，PH.D. candidate, His research interests include data mining and deep learning.       HE Fa-Zhi, born in 1968, PH.D., professor. His research interests include, CAD graphics, collaborative computing and data mining. YU Hai-Ping, born in 1978, PH.D. candidate. His research interests include image processing and image segmentation.   Background With the  rapid  development  of  internet  technology, information overloading is becoming a serious problem, which makes  adverse  impact on  user  experience.  As  one  of  the potential  solutions,  Recommendation  system  has  been  wildly used  in  many  web  applications  and e-commerce  web  sides, aims to recommend items that fit user's preference by modeling user's historical behaviour. These algorithms always suffer from the cold start and data sparsity problem, which means that most users  rates  for  only  a  few  items  and  causing  performance degradation. Utilizing users’ social information is  one  of  the efficient  ways  to  alleviate  this  problem  and  attract  increasing attention  in recent years.  However,  most  of  them  direct  make use  of  the  social  network  information  on  binary  format, and ignore the  fact  that  a  user  trusts  in  his  friends  with  different degrees.  In this paper, we focus on the problem of estimating trust degrees  between  each  pair  of  users  for  recommendation systems. Naturally, both ratings and social links could be used to  answer  this  question.  Based  on  the  assumption  that  users may  trust  some  social  friends  with  similar  ratings  or  social links  in  high  degree,  there  are  several  methods  have  been proposed.  To  further  obtains  a  more  accurate  recommendation model, we proposed a new  method to tackle this problem, and focus  on  two  aspects:  (1)  Previous  works  estimated  trust degrees  in  social  links  based  on  the  common  sets  of  social friends, but doesn’t model the indirect relation between users in social  networks;  (2)  Moreover,  they  didn’t  make  full  use  of both  ratings  and  social links  for each  pair  of  users,  while  they both  show  great  potential  for  estimating  trust  degree. We  first factored  the  matrix  social links,  and  obtain  the  social  latent vector  of  users which  imply  contain  indirect  relation  between users.  Based  these  latent  vectors,  we  calculated  the implicit similarity in  trust,  and  then  integrated it  into  traditional  social recommendation  algorithm. Finally,  we  achieved  our  accurate social  recommendation  model  with  implicit  similarity  in  trust, named  as  SocialIT.  The experiment on  both  rating  prediction and  item  recommendation  demonstrated  that  this  model  could achieve  a  more  accurate  result  compared  to  previous  works, 论文在线出版号  No.175  潘一腾等：一种基于信任关系相似度的社会化推荐算法  19   especially for users with sparse rating data. This  work  is  supported  by  the  National  Natural  Science Foundation  of  China  (No.61472289), the  Natural  Science Foundation of Hubei Province (2015CFB254).