基于社会信任的协同过滤算法研究综述

秦凯 吴家丽 宋益多 乔晨蕊

摘 要：随着推荐技术的不断发展，研究发现用户更加偏好于相信熟人或者权威人士的推荐，因此，基于信任的推荐方法成为研究热点。本文从社会网络信任特征和基于信任的协同过滤算法研究情况进行分析总结，为未来对个性推荐方法和基于信任的协同过滤算法进行深入研究奠定基础。文章最后针对目前基于信任的协同过滤算法研究现状，对未来的发展方向进行展望。

关键字：个性化推荐；协同过滤；信任

中图分类号：TP391.41 文献标识号：A 文章编号：2095-2163（2015）04-

A Review of Collaborative Filtering Algorithm Based on Social Trust Relationships

QIN Kai， WU Jiali， SONG Yiduo， QIAO Chenrui

（School of Computer Science and Technology ，Harbin Engineering University， Harbin 150001， China ）

Abstract ：With the rapid development of recommendation technology， people have realized that users prefer to believe the recommendations from acquaintances or authorities. Recommended approaches based on social trust relationships have only recently been given research attention. This paper summarizes the feature of social trust networks and analysis collaborative filtering （CF） based social recommender systems. These lay the foundation for the research of individualization recommended technology and collaborative filtering algorithm based on social trust relationships. Facing to the research status of collaborative filtering algorithm based on social trust relationships， the paper prospects the future development directions.

Keywords： Personalized Recommendation； Collaborative Filtering； Trust

0 引 言

近年来随着社会网络的发展和网络设备承载能力的提升，信息量急速增长，面对海量的数据，用户很难在其中找到自己想要的信息，推荐系统应运而生。社会网络的飞速兴起为推荐技术发展带来了前所未有的机遇和挑战[1]。社会网络促使网络信息剧增，这使得用户从中搜取需要的信息更加困难；另一方面，社会网络将用户的属性、习惯更好地展现出来，便于从数据中挖掘出潜在的信息以用于个性化推荐，提高推荐准确度和效率。社会网络中的用户信任关系为个性化推荐算法研究开辟了一个新的领域[2-3]。

协同过滤算法是目前使用非常广泛的个性化推荐算法之一。传统的协同过滤算法主要分为两类：基于用户的协同过滤算法和基于项目的协同过滤算法。基于用户的协同过滤算法是通过假设拥有相似兴趣的用户会对相似项目感兴趣。例如，A和B曾经对很多相同的电影给予了相似的打分评价，那么如果A喜欢电影1，很大程度上B也可能喜欢电影1，以此为依据将电影1推荐给B。基于项目的协同过滤算法是假设同一个用户可能会对具有相似特征的项目具有相似偏好。例如，用户A对电影m、n、o、p、q都给予了很高的评价，其中m、n、o、p都具有外国、喜剧、滑稽的特征，那么算法将推测其偏爱外国滑稽喜剧类电影，可以将同为外国滑稽喜剧电影s推荐给A。协同过滤算法是利用集体智慧进行个性推荐的典型方法，相比于基于内容的推荐方法，解决了基于内容的推荐方法存在的特征抽取困难、过度拟合和难以跨领域等问题，但是协同过滤算法存在数据稀疏、用户冷启动、恶意推荐的问题，这些问题一定程度上制约着协同过滤算法的发展[2]。

社会网络的兴起、发展为协同过滤算法的发展提供了新思路。社会网络可以提供与目标用户有着直接或者间接社会关系的用户信息，而用户更倾向于相信朋友，利用这些有效的社会关系寻找目标用户的最近邻，可以有效缓解基于项目的协同过滤算法的冷启动和恶意推荐问题。针对社会网络中用户间信任关系的传递性、非对称性、主观性等特点，学者从不同角度分析用户间的信任关系以及信任关系对兴趣相似度的相关性，以此进行结合社会信任的协同过滤算法研究[4-8]。

1 社会网络信任和协同过滤算法

传统协同过滤算法通过用户-项目的历史评分数据寻找兴趣相似的用户，根据相似用户的选择结果实施推荐。社会网络信任关系为寻找相似兴趣用户提供了一个新的角度，符合用户偏爱信任的人推荐的心理，同时也弥补了用户-项目评分数据稀疏和选取最近邻用户依据单一的不足。社会网络信任和传统协同过滤算法是基于社会信任的协同过滤算法研究的两个关键点，下面将逐一进行阐述。

1.1社会网络信任

信任最初是一个社会学概念，描述一个主体假设另一个主体的行为与自己对其的预期刚好相同，表示第一个主体信任第二个主体。信任在不同的领域，概念稍有差别，社会网络中的信任是指一个用户通过依据其他用户所做的选择而形成占优策略的程度。在推荐系统中，可以利用信任来衡量一个用户在多大程度上依赖其他用户给出的推荐做出选择[9-10]。

社会网络中的信任具有主观性、非对称性、动态性、可传递性、自适应性等性质。信任的主观性是指用户对其他用户的信任与否具有主观性，一个用户对不同用户的信任评价不同，不同用户对于同一个用户的评价也可能存在差异。信任的非对称性是指交互双方的信任关系是不对称的，用户a对用户b的信任和用户b对用户a的信任无必然联系。信任的动态性表现在用户之间的信任不会一成不变，会随着时间、环境、上下文等影响变化[11]。信任还具有一定的弱传递性，假设a、b用户之间存在信任关系，b、c用户之间存在信任关系，那么a、c用户之间可能也存在信任关系，信任的弱传递关系如图1所示[12-14]。信任具有一定的自适应性，随着信任的动态变化，其能够自适应地更新。

图1 信任弱传递关系示意图

Fig.1 Weak trust transitive relation between nodes

根据信任的多个特性从不同角度对信任进行分类，具体描述如下：

局部信任与全局信任[14-15]：局部信任是指在系统中，目标用户对邻居用户的信任度，全局信任是指用户在整个系统中的可信度。局部信任是一个相对量，在同一个系统中，用户之间的间接信任度是不同的，主要取决于目标用户的位置，而每个用户只有一个整体信任度。

初始信任与成熟信任：根据信任建立的时间，可以将信任分为初始信任和成熟信任。未进行过交互的用户之间的信任关系称为初始信任，用户之间通过积累多次交互而得到的信任称为成熟信任。

显性信任与隐性信任[6、16]：根据信任获取的方式的不同，信任分为显性信任和隐性信任。用户明确表明对其他用户的信任声明，这样的信任为显性信任，用户之间没有明确表明信任关系，需要通过用户的操作行为或者交互过程得到信任来判定信任关系的则定义为隐性信任。

直接信任与间接信任[17]：根据信任的可传递性，可将信任分为直接信任和间接信任。直接信任是指用户通过交互或者关注等行为建立的直接信任关系，间接信任是指用户间的间接关联关系，需要通过数个具有直接信任关系的用户传递建立的间接信任关系。

针对基于社会信任的协同过滤算法使用的不同场景，研究者选取在该场景下对用户间信任关系影响较大的特性进行分析研究，将相关信任特性对用户选择带来的影响添加进传统协同过滤算法中，以得到最符合算法使用场景，推荐效果更好的算法。

1.2协同过滤算法

协同过滤算法的思想是模拟现实生活中人与人之间“口口相传”形式的信息推荐，其中假设拥有相似兴趣的用户可能会喜欢相似的项目或者用户可能对相似的项目表现相似的偏好程度。结合信任的协同过滤算法主要是以基于用户的协同过滤算法为基础，故本文着重介绍基于用户的协同过滤算法。

基于用户的协同过滤算法一般分为三个步骤（如图2所示）：

（1） 建立用户模型

用户模型是一个用户对项目的评分矩阵，可以用Rm*n表示，其中m表示用户数，n表示项目数。Rm*n的值表示用户对某个项目的评分，即以评分高低描述用户对项目的喜好程度，用户对某些项目没有评分则用0填充。

（2） 计算用户相似度并寻找最近邻

通过用户模型计算用户相似度一般有两种方法：Pearson相关系数法和夹角余弦相似度法。Pearson相关系数法在计算相似性的过程中主要是以用户平均分为标准，比较目标用户和邻居对项目评分偏离平均评分的程度。通过偏离程度判断用户相似度。夹角余弦在基于用户的方法中，把用户的评分看作向量，通过比较两个向量的夹角余弦判断用户和邻居的评分相似度。根据计算的相似度寻找目标用户的最近邻，常用的有固定值法和阈值法，选择与目标用户相似度较高的一部分邻居用户。

（3） 评分预测给出推荐列表

通过最近邻对于项目的评分情况，预测目标用户的评分，将评分由高到低排序，选择评分高的项目产生推荐列表，进行推荐。

图2 传统协同过滤算法流程图

Fig.2 Flow chart of traditional collaborative filtering algorithms

2 基于社会信任的协同过滤算法发展

结合信任的协同过滤算法较传统的协同过滤算法更符合人们实际生活中的对于推荐结果的选择规律，具有更好的推荐精确度。目前，结合信任的协同过滤算法研究从使用信任关系的角度看主要分为三类：其一是在建立用户模型时使用信任关系，利用目标用户与其他用户的信任关系筛选出目标用户的用户-项目评分矩阵，缓解了矩阵稀疏性问题的同时降低了评分矩阵的维度，增加计算效率；其二是在计算用户相似度和寻找最近邻时使用信任关系，可以利用信任关系和用户模型共同计算用户相似度，也可以根据用户信任关系筛选目标用户的最近邻；其三是综合以上两种方法，建立多维度的协同过滤算法。

2.1用户模型中的信任研究

用户模型是协同过滤算法的基础，旨在建立一个用户-项目评分矩阵，以便后续根据评分矩阵提供的用户评分关系得到相似用户。通常情况下，推荐系统中用户和项目的数量都很庞大，然而用户对项目的评分参与度不高，矩阵稀疏，这将导致建立用户模型计算量较大并且有效数据量小，计算结果可用度不高。用户模型中结合信任关系的研究是使用社会网络中收集到的用户信任关系图构造用户信任关系矩阵，通过用户信任关系矩阵和用户-项目评分矩阵组合得到信任用户-项目评分矩阵。以信任用户-项目评分矩阵替代传统算法中用户-项目评分矩阵计算用户之间的相似性，进而预测用户项目评分，给出推荐列表。引入信任关系进行用户模型的数据筛选，能够有效地改善传统算法中构造用户模型存在的问题[18]。算法流程如图3所示。

图3 在用户模型中的结合信任算法流程

Fig. Flow chart of the CF algorithms based on trust in user model

在建立用户模型过程中集合信任机制，根据信任的特性也会有不同的解决方案。文献[19]利用静态信任值构建信任用户-项目评分矩阵，只有被目标用户所信任的用户给出的项目评分会被纳入推荐过程中，同时利用信任的动态性，动态地更新信任值。文献[20]提出基于初始信任的协同过滤方法，综合考虑了信任的动态性和可传递性因素构造出用户信任评分矩阵。文献[21]通过特征学习的方法确认相似用户，综合社会信任关系得到推荐模型。

2.2 用户相似度计算和寻找最近邻中的信任研究

随着协同过滤算法的深入发展，用户概貌注入攻击给仅靠用户-项目评分矩阵得到用户相似性进而预测评分的传统算法带来了极大挑战。将用户相似度和用户间信任度结合共同作为邻居选取的双重依据，有效地解决了推荐系统的安全问题，也提高了推荐质量[22-24]。算法流程图如图4所示。

图4 用户相似度结合信任值算法流程图

Fig.4 Flow chart of the CF algorithms based on trust in computing user similarity

文献[25]采用的融合用户可疑度的多维信任模型，计算得到目标用户对每个兴趣相似用户的信任度，并以此作为选取可信邻居用户集的依据。文献[17]在基于信任的协同过滤算法中从全局信任、局部信任和直接信任、间接信任的角度计算信任值，将信任度和相似度结合，得到最近邻。文献[26]在从直接信任和间接信任的角度基础上，考虑直接信任的时间衰减因素，更符合实际情况，并且提出动态确认相似邻居阈值的方法，提升了推荐算法的准确性和鲁棒性。

2.3 多维度的信任研究

上面两节描述的都是只在构建用户模型或者用户相似度计算过程中使用用户间的信任关系，还有一些研究者发现，根据推荐使用的情景，在不同步骤考虑信任的不同特性，既使用信任值来筛选用户又用作计算评价时的合并权重，给协同过滤算法提出了新的解决思路。

文献[27]中引入帕雷托最优理论，以信任度为基础结合用户相似矩阵降低稀疏性，并且根据用户信任度、相似度和可行度多维重构信任网络。以重构信任网络信任度和用户相似度计算项目预测评分。文献[28]提出了结合信任和相似度的多视图过滤方法，利用概率统计方法有效地解决了算法的冷启动问题，同时提高了推荐的准确率和覆盖率。文献[25]提出的基于可靠用户的top-N推荐方法，在使用用户信任度筛选可靠用户集，基于有效用户的评分信息采用多维度项目选取方法选取项目，最后采用均值的方法得到项目的预测评分。文献[29]通过重启动随机游走度量用户间信任，将用户间信任情况作为用户间相似性计算的一部分；然后利用相关性作为项目评分的权重，预测目标用户对位置项目的喜爱程度，进行推荐。

3未来研究方向

协同过滤算法的研究在学者的不断努力下逐步走向成熟。结合社会信任的协同过滤算法在一定程度上缓解了算法的冷启动、稀疏性等问题，但是社会信任关系纷繁复杂，影响因素较多，现有算法仍存在着安全性差、推荐效果不佳等问题。因此，大数据背景下，基于信任的协同过滤算法在某些方面仍有待完善，未来的研究方向如下。

3.1 算法安全性[30]

随着互联网应用日益广泛，用户的真实信息越来越多地暴露在网络上，这些信息有利于系统给用户提供个性化的服务和推荐，但是网上的信息越贴近用户隐私遭受窃取的危险越大。在很多领域，推荐结果会引起不同的商业价值，这也使得一部分人深入研究推荐算法原理，通过恶意编造数据等方法力图修改推荐结果，由此即违背了推荐系统设计的本意和推荐的公平性。社会网络中的信任关系在一定程度上缓解了推荐的安全性问题，但是算法的安全性问题仍然需要给予更多的关注。

3.2 考虑现实社会关系[31-32]

社交网络中用户之间的信任关系通常以“好友”、“关注”等方式刻画，人们通常认为信任度和兴趣相似度具有正相关性。但是信任具有方向性，社会关系不同会对信任关系带来影响。在微博中，商家用户会关注普通用户，这两者之间构成了信任关系，但是普通用户跟商家用户的兴趣相似度其实并不高。同时，社会关系纷繁复杂，在不同情境下，信任度和兴趣相似度也不是时刻均为正相关。例如，同事之间的信任关系和家人之间的信任关系对用户的兴趣影响就各有不同[33]。社交网络中的关键用户的影响力对推荐也会起到至关重要的作用，如何区分用户社会关系，合理确定不同信任影响的权重研究有待进一步深化。

3.3 算法时效性[11]

信任具有动态性，信任度和兴趣相似度会随着时间变化或者因为某一次推荐结果而变化[34]。而且用户的偏好会随着外部环境不同而发生变化，如何在不同情境下动态地计算得到信任值，进而得到信任变化对用户兴趣的影响，实时更新推荐结果也有待于研究者的深入探索与挖掘。

3.4 基于情感的推荐

基于情感的服务是下一代互联网服务的发展方向之一，情感分析能够分析用户对事物的喜好、厌恶程度，从更深层次了解用户，为用户提供最优质的服务。目前，基于情感的推荐研究多集中在用户标签分析和基于内容的分析上，其中存在着计算数据量大，分析结果不准确等问题，社会信任关系和情感分析结合的研究方法至今仍处于萌芽阶段。如何结合社会信任和情感分析技术，构建新型推荐框架将是推荐算法研究的一个重要领域。

4 结束语

本文总结了目前基于信任的协同过滤算法的研究现状，通过描述信任的特性和传统的协同过滤算法对课题的研究背景进行展现。同时，从结合信任关系的角度，重点介绍了基于信任的协同过滤算法发展方向，最后针对当前课题的发展过程中出现的不足和挑战，提出了社会网络中协同过滤推荐算法未来的研究方向，为协同过滤算法研究者工作方向提供指引作用。

参考文献：

[1] YANG X， GUO Y， LIU Y， et al. A survey of collaborative filtering based social recommender systems[J]. Computer Communications， 2014， 41（5）：1–10.

[2] ADOMAVICIUS A， GEDIMINAS T. Toward the next generation of recommender systems： A survey of the state-of-the-art and possible extensions[J]. IEEE Transactions on Knowledge & Data Engineering， 2005， 17（6）：734-749.

[3] 黄仁， 孟婷婷. 个性化推荐算法综述[J]. 中小企业管理与科技， 2015 （8）： 271-273.

[4] KONSTAS I， STATHOPOULOS V， JOSE J M. On social networks and collaborative recommendation[C]// Proceedings of the 32nd International ACM SIGIR Conference on Research and development in Information Retrieval， Boston， Massachusetts：ACM，2009：195-202.

[5] BOBADILLA J， ORTEGA F， HERNANDO A， et al. Recommender systems survey[J]. Knowledge-Based Systems， 2013， 46（1）：109–132.

[6] CHEN C， ZENG J， ZHENG X， et al. Recommender system based on social trust relationships[C]//e-Business Engineering （ICEBE）， 2013 IEEE 10th International Conference on ，Coventry： IEEE， 2013： 32-37.

[7] 李慧， 马小平， 胡云，等. 融合社会网络与信任度的个性化推荐方法研究[J]. 计算机应用研究， 2014， 31（3）： 808-810.

[8] KONSTAS I， STATHOPOULOS V， JOSE J M. On social networks and collaborative recommendation[C]//Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval，Boston， Massachusetts：ACM， 2009： 195-202.

[9] LIU F， LEE H J. Use of social network information to enhance collaborative filtering performance[J]. Expert Systems with Applications， 2010， 37（7）：4772–4778.

[10]PHAM M C， CAO Y， KLAMMA R， et al. A clustering approach for collaborative filtering recommendation using social network analysis[J]. Journal of Universal Computerence， 2011， 17（4）：583-604.

[11]LIU D， LAI C， CHIU H. Sequence-based trust in collaborative filtering for document recommendation.[J]. International Journal of Human-Computer Studies，2011， 69（9）：587–601.

[12] 冯萍萍. 融合双重信任网络的协同过滤推荐算法研究[D]. 秦皇岛：燕山大学，2014.

[13] Agarwal V， Bharadwaj K K. Trust-enhanced recommendation of friends in web based social networks using genetic algorithms to learn user preferences[M]//Trends in Computer Science， Engineering and Information Technology. Berlin Heidelberg： Springer ， 2011： 476-485.

[14]XU X W， WANG F D .Trust -based collaborative filtering algorithm [C]//International Symposium on Computational Intelligence and Design 2012，Hangzhou：IEEE，2012：321-324

[15]CHENG J， ZHOU J， ZHANG Y. Preference-based top-K influential nodes mining in social networks[C]//Trust Security & Privacy in Computing & Communications IEEE International，Changsha： IEEE， 2011：1512-1518.

[16] 李湛. 基于社会信任网络的协同过滤推荐方法研究[D]. 大连：大连理工大学， 2013.

[17]吴慧， 卞艺杰， 赵喆等. 基于信任的协同过滤算法[J]. 计算机系统应用， 2014， （7）：131-135.

[18]GHAZARIAN S， NEMATBAKHSH M. Enhancing memory-based collaborative filtering for group recommender systems[J]. Expert Systems with Applications， 2015，42（7）：3801-3812

[19]刘英南. 在线社会网络中基于动态信任的推荐机制研究[D]. 上海：华东师范大学，2014.

[20]刘世光. 基于初始信任的协同过滤方法研究[D].秦皇岛： 燕山大学，2014.

[21] MA H， KING I， LYU M R. Learning to recommend with social trust ensemble[C]// Proceedings of International Acm Sigir Conference on Research & Development in Information Retrieval， Boston， Massachusetts：ACM，2009：203-210.

[22]Cai X， Bain M， Krzywicki A， et al. Collaborative filtering for people to people recommendation in social networks[M]// Advances in Artificial Intelligence. Berlin Heidelberg：Springer， 2011： 476-485.

[23]BOBADILLA J， SERRADILLA F， HERNANDO A. Collaborative filtering adapted to recommender systems of e-learning[J]. Knowledge-Based Systems， 2009， 22（4）：261–265.

[24]Liu Q， Gao Y， Peng Z. Advances in Swarm Intelligence[M]. Germany： Springer Berlin Heidelberg， 2012：164-174.

[25]贾冬艳. 基于多维信任模型的可信推荐方法研究[D]. 秦皇岛：燕山大学， 2013.

[26] XIE Shengjun. A collaborative filtering recommendation algorithm improved by trustworthiness[J]. International Journal of Future Generation Communication and Networking， 2014，7（2）：35-46.

[27] AZADJALAL M M， MORADI P， ABDOLLAHPOURI A. Application of game theory techniques for improving trust based recommender systems in social networks[C]//Computer and Knowledge Engineering （ICCKE）， 2014 4th International eConference on， Mashhad： IEEE， 2014： 261-266.

[28] GUO G， ZHANG J， YORKE-SMITH N. Leveraging multiviews of trust and similarity to enhance clustering-based recommender systems[J]. Knowledge Based Systems， 2015， （9）：14–27.

[29] 俞琰， 邱广华. 融合社会网络的协同过滤推荐算法研究[J]. 现代图书情报技术， 2012， （6）：54-59

[30]DOKOOHAKI N， KALELI C， POLAT H， et al. Achieving optimal privacy in trust-aware social recommender systems[J]. Lecture Notes in Computer Science， 2010， 6430：62-79.

[31]WEI C， KHOURY R， FONG S. Web 2.0 Recommendation service by multi-collaborative filtering trust network algorithm[J]. Information Systems Frontiers， 2013， 15（4）：533-551.

[32]朱强，孙玉强. 一种基于信任度的协同过滤推荐方法[J]. 清华大学学报（自然科学版），2014，03：360-365.

[33]武春岭， 胡云冰， 鲁先志. 基于个人和社会隐含因子的社会化推荐[J]. 计算机应用与软件， 2014， （9）：98-101. DOI：10.3969/j.issn.1000-386x.2014. 09.025.

[34]MOGHADDAM M G， MUSTAPHA N， MUSTAPHA A， et al. AgeTrust： A New Temporal Trust-Based Collaborative Filtering Approach[C]//International Conference on Information Science & Applications， Seoul， South Korea：IEEE， 2014：1 - 4.