- 1 -
中国科技论文在线
基于信任和兴趣聚类的协同过滤算法
侯成龙1,2，孟祥武1,2**
作者简介：侯成龙(1990-)，男，硕士研究生，主要研究方向：社会化网络推荐系统
通信联系人：孟祥武（1966-），男，教授，博士生导师，主要研究方向：网络服务，智能信息处理
（1. 北京邮电大学智能通信软件与多媒体北京市重点实验室 北京 100876；
2. 北京邮电大学计算机学院 北京 100876） 5
摘要：伴随着 Web 技术及各类社交网站的快速发展，社会化网络中的个性化服务受到越
来越多的关注。为了提供高质量的社会化网络推荐，本文提出了一种基于信任和兴趣聚类的
协同过滤推荐算法。该算法首先综合考虑用户信任度和用户兴趣相似性,利用融合后的相似
度对用户进行聚类，然后判断目标用户所属聚类并在其中搜索目标用户的近似邻居，最后根
据近似邻居对项目的评分预测未知的项目评分。实验结果表明该算法在一定程度上提高了社10
会化网络推荐的响应速度和推荐的精度。
关键词：计算机应用；社会化网络；推荐系统；协同过滤
中图分类号：TP393
Collaborative Filtering Recommendation Algorithm Based 15
on Trust and Interest Clustering
Hou Chenglong1,2, MENG Xiangwu1,2
(1. Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing
University of Posts and Telecommunications, Beijing 100876;
2. School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 20
100876)
Abstract: With the development of Web and kinds of social networking sites, personalized services
in social network received more and more attention. In order to provide high quality social
recommendation, a collaborative filtering algorithm based on trust and interest clustering is proposed in
this paper. Firstly, the algorithm takes synthetieally into account users’ trust degree and the similarity 25
of interest and users are clustered based on the composite similarity. Then we find out the nearest
neighbours of target user in his cluster and predict the unknown user rates. Finally, experimental results
show that the proposed method can obtain more accurate social recommendation as well as improving
the real-time performance to some extent.
Key words: computer application; social network; recommend system;collaborative filtering 30
0 引言
作为一种必不可缺的信息过滤技术，推荐系统[1]在过去的一段时间内取得了很大的发
展。相关的推荐技术在信息检索、机器学习和数据挖掘领域得到了广泛的研究。由于其巨大
的商业价值，推荐系统也已经成功应用到各行各业，例如 Amazon 的商品推荐、iTunes 的音35
乐推荐以及 Netflix 的电影推荐。随着 Web 技术及各类社交网站（facebook、twitter、人
人网）的快速发展，传统推荐系统也迎来了新的挑战。
传统的推荐系统中，当用户有足够多的评分记录并且与其他用户对共同项目进行评分，
协同过滤算法[2]是最有效的，但是它忽视了用户之间的社会化关系。在现实生活中，当我们
向朋友咨询优秀的电子产品或者动人的电影时，我们其实是在请求社会化推荐。社会化推荐40
每天都在发生，我们经常需要向朋友咨询建议。另外，协同过滤算法对所谓的冷启动用户[3]
- 2 -
中国科技论文在线
（那些因为罕有可以利用的行为信息而很难给出精确推荐的新用户）表现的差强人意。然而，
只要将新用户关联到一个大的社会化网络中，基于社会化网络的推荐系统利用用户的社会化
关系自然就能够产生推荐，从而在一定程度上缓解了传统推荐系统的冷启动问题。因此，为
了促进推荐系统的发展和提高个性化推荐结果的准确性及有效性，如何融合社会化关系实现45
有效的推荐已经成为当今社会化网络服务的一个重要课题。
本文在现有社会化网络推荐系统的研究基础上，融合了用户信任度和兴趣相似度并据此
对用户聚类，提出了一种基于信任和用户兴趣聚类的协同过滤算法。本文第1节介绍了协同
过滤算法、融入社会化关系推荐算法等方面的相关工作，第2节提出了社会化网络中基于信
任和兴趣聚类的协同过滤算法，第3节在公开数据集上进行实验并对实验结果进行分析，最50
后给出结论。
1 相关工作
协同过滤算法
协同过滤是目前应用最普遍、最成功的推荐算法。此类算法可以分为两类：基于记忆
（memory-based）的方法和基于模型（model-based）的方法。 55
基于记忆的推荐算法可以概括为两步：(1)采用相似度计算方法计算用户或者项目之间
的相似度，构造相似度矩阵；(2)采用相应的算法估计评分，并据此为用户进行推荐。该类
方法可为目标用户估计对某一特定项目的评分，也可产生一个推荐列表。常用的相似度计算
方法包括：皮尔森相关性(pearson correlation)、余弦相似度(cosin similarity)、调整余弦相似
度(adjust cosin similarity)，它们都是基于用户对共同项目的评分来计算。其中皮尔森相关性60
使用最多，计算方法如下：
,
, ,
, ,
22
, ,
( , )
i i j j
u ui j
i i j j
u u u ui j i j
u s u u s u
s S
i j
u s u u s u
s S s S
R R R R
Sim u u
R R R R
（1-1）
其中， ,u ui jS 为用户 iu 和 ju 共同评过分的项目集合， ,iu sR 表示用户 iu 对项目 s的评分， iuR
表示用户 iu 的平均评分。
基于模型的推荐方法[4]采用统计学、机器学习、数据挖掘等方法，根据用户历史数据为65
用户建立模型，并据此产生合理的推荐。这类方法其在一定程度上解决了用户—项目评分矩
阵的稀疏性问题。下面给出了一个简单的评分模型：
1
(u, i) (u, r) r
n
i
R pro
(r 1,2...5) （1-2）
其中， (u,i)R 表示用户u 对项目 i 的评分估计（评分等级为1到5之间的整数）， (u, r)pro
表示用户u 打 r分的概率。基于模型的算法可以借助分类、线性回归和聚类等机器学习实现。 70
融入社会化关系的推荐算法
随着 web 的发展，用户在网站上产生的信息除了用户对项目的评分信息外，还有用
户提供的社会关系信息，如同学关系、朋友关系、信任关系等。近年来，一些融合社会关系
到协同过滤的推荐算法不断涌现。
2006 年，Golbeck 等[5]采用社会信任网络信息，根据目标用户信任的用户对项目的评分75
- 3 -
中国科技论文在线
来估计目标用户对项目的评分值。2007 年，Avesani 等[6]基于用户的社会信任网络，采用有
限步长的信任传播方法，得到目标用户对其他用户的估计信任值，基于信任估计值产生评分
估计，与文献[5]相同，该方法同样只考虑了用户间的信任关系而没有通过计算用户对项目
的评分信息得到用户兴趣相似度.。文献[7]引进用户之间的朋友关系、用户参加的群组信息
及用户选择项目的信息，构建包含三种节点类型的图，采用基于图的随机游走方法产生推荐80
结果。为了获得足够的评分信息，又不受到噪音数据的影响，文献[8]提出了一种叫做
Trustwalker 的随机游走模型，它将基于信任网络的推荐算法和基于项目协同过滤进行了融
合，吸取了两种算法各自的优点。2010 年，Jerbrin 等[9]通过用户之间的信任信息和用户对项
目的评分信息来计算每个用户的“全局信誉”值，基于“全局信誉”值较高的用户对项目的
评分来估计目标用户对项目的评分。以上方法的实验结果表明在评分估计的精确性和推荐的85
准确性方面都优于传统协同过滤方法。
2 算法设计
问题描述
推荐系统中，用户集 1 2{ , , , }mU u u u ，项目集 1 2 n{ , , , }I i i i ，每个用户u对一个项
目集 1 2{ , , , }nu u u uI i i i 进行评分，用户u对项目 i的评分表示为 uir 。 uir 一般用 1, ,5 的90
整数表示。在一个基于信任度的系统中，我们有一个用户之间的信任网络。如果用户u信任
v ,则 uvt 表示u对 v的信任度，最简单情况下取值范围为 0,1 。0表示不信任，1表示完全信
任。社会化网络可以定义为一个图结构， ,G U TU ，其中 {( , ), , }TU u v u U v U ，
每个结点对应于一个用户，每条边对应于一个信任关系。一般情况下推荐的任务为预测给定
用户u对未评分项目 i的评分 uir 。 95
用户信任度计算
社会化网络中存在以下两种信任关系[10]：
（1）直接信任关系：表现为两个用户为直接好友关系。定义 ,i jDT u u 为用户 iu 和用
户 ju 的直接信任度。最简单的情况下 ,i jDT u u 取值为0、1，0代表两个用户不存在直接好
友关系，1代表两个用户存在直接好友关系。 100
（2）间接信任关系：如果两个用户不存在直接好友关系，但拥有共同好友，则认为用
户间存在间接信任关系。定义 ,i jIT u u 为用户 iu 和用户 ju 的直接信任度。本文将衰减因
子引入到信任度计算中，认为信任度在用户之间传递过程中是呈衰减趋势的。在计算间接信
任度时，由于两个用户间可能存在多个共同好友，可以通过信任合成的方式计算间接相似度。
设信任衰减的过程中的信任衰减因子为D且 0,1D ，以用户 iu 和 ku 为例，设用户节点 ju105
为它们的共同好友，则用户 iu 通过 ju 与用户 ku 的间接信任度可以表示为下式所示： , , , , ,i j k i j i kIT u u u D Min DT u u DT u u （2-1）
经过信任融合处理后，移动用户 iu 和 ku 的间接信任度可以表示为如式（3-2）所示。
- 4 -
中国科技论文在线
, ,,
C
i j kj
i k
IT u u u
IT u u
C
（2-2）
其中C 是用户 iu 和 ku 之间的有效路径数目。 110
通过对社会化网络用户关系进行挖掘得到用户信任度矩阵T 。其中 ijT 的计算方法是：
若用户 iu 和 ku 的直接信任度 , 0i jDT u u ，则 ,ij i jT DT u u ，否则 ,ij i jT IT u u 。
用户融合相似性计算
在传统的协同过滤算法中，选择目标用户的邻居用户时仅考虑用户评分相似性，而在社
会化网络推荐中，还需要考虑用户的社会化关系，即用户间的信任度。本文通过对用户兴趣115
相似性（即评分相似性） ,r i jSim u u 和用户信任度 ,t i jSim u u 进行线性组合得到用户融
合相似性 ,i jSim u u ，计算公式如下所示：
( , ) , (1 ) ,r ti j i j i jSim u u Sim u u Sim u u （2-3）
其中，用户兴趣相似性 ,r i jSim u u 通过公式（1-1）计算，用户信任度 ,t i jSim u u 为
上一小节计算得到的用户信任度矩阵T 中的相应元素值。 为调和权重参数，用来调节用120
户兴趣相似性和用户信任度之间的平衡。
基于信任和兴趣聚类的协同过滤算法
根据上述计算得到的用户融合相似性，可以对用户进行聚类。聚类是数据挖掘中的经典
问题，它的目的是将数据对象分成多个类（聚类），使得同一个聚类中对象之间具有较高的
相似性，而不同聚类中的对象差别较大。本文通过K-means聚类算法对用户进行聚类，简称125
为UserClusteringByKMeans。传统的K-means聚类算法的初始聚类中心是随机选取的，研究
发现，在社会化网络中，直接好友关系最多的用户可以有效代表一部分用户，所以将这些用
户作为聚类中心具有更好的代表性。UserClusteringByKMeans算法具体步骤如下：
步骤一：设定聚类数目k；
步骤二：从用户集合U中选取直接好友关系最多的k个用户作为初始聚类中心，记为集130
合 1 2 k{cc ,cc , , cc }CC ；
步骤三：k个聚类 1 2 kc , c , , c 均初始化为空，记为集合 1 2 k{c ,c , , c }C ；
步骤四：对每一个用户 iu ，根据公式（2-3）计算与聚类中心集合CC中所有用户的融合
相似性，得到相似性最大的聚类中心 mcc ，将用户 iu 加入到相应聚类 mc 中；
步骤五：针对每个聚类重新选取聚类中心，将聚类中与其他用户融合相似性平均差异最135
小的用户作为新的聚类中心；
步骤六：重复步骤四和步骤五，直到k个聚类中的成员和上一次循环中聚类结果相同。
确定了用户u所属聚类后，根据目标用户与所属聚类中的用户之间的融合相似性，把相
似性最高的n个用户作为目标用户的邻居用户，记为相似邻居集合 uN 。目标用户u对项目 i
的预测评分 uiR 可通过如下公式计算： 140
vi, v
u
ui u v
v N
R R k Sim u R R
（2-4）
- 5 -
中国科技论文在线
其中， uR 和 vR 表示用户u和 v对项目的平均评分，k为标准化因子，
1
u, v
uv N
k
Sim
。
3 实验及结果分析
本文采用的实验平台为：Windows 7（32 位）操作系统，2GB 内存，Intel Core(TM) 2 Duo
CPU ；开发环境为 Java 7 开发语言和 MySQL 数据库。 145
数据集选择
大多数用于推荐的实验数据集都不包含社会化网络用户之间的关系。Epinions 数据集是
一个目前公开可用的包含信任网络和用户评分数据的数据集。本文使用的 Epinions 数据集[11]
非常稀疏，它包含 49290 个用户至少有一次评分，超过 24000 用户是冷启动用户（一般认为，
少于 5 个评分的用户为冷启动用户），有 139738 个项目的 664823 评分数据，以及 487182150
个用户对之间的信任数据。为了使每个用户既有评分信息又有信任关系，本文在进行实验时
对数据集进行了预处理，只取用户评分数据和信任数据中的共同用户集合，最后剩下 40162
个用户的 624811 条评分记录以及他们之间的 442943 个信任关系。
评估标准
在推荐领域，MAE(Mean Absolute Error)一直被很多研究者用来衡量预测评分与用户实155
际评分之间的绝对偏差，评估推荐系统的效率[12]。MAE 是通过计算预测结果中的用户评分
和实际的用户评分之间的偏差来度量预测结果的准确性。如果 MAE 值越小，则说明预测的
准确度越高，反之，则说明预测的准确性越低。假设通过预测得到的评分集合表示为
1 2 3, , , nP P P P…, ，与之相对应的实际评分集合表示为 1 2 3, , , nR R R R…, ，则 MAE 可以表
示为如下式所示。 160
1
n
i i
i
P R
MAE
n
（3-1）
实验及结果分析
本文设计了两组实验，实验中用户聚类数目 k均设定为30。
第一组实验：确定公式（3-3）中调和权重参数 。
参数 用来调节用户兴趣相似性和用户信任度之间的平衡，因此 的取值会影响推荐165
的准确率。实验采用本文提出的基于信任和用户兴趣聚类的协同过滤算法， 取值从0开始，
每次增加，直到变为，实验结果如图1所示。
- 6 -
中国科技论文在线
图 1 不同参数 的 MAE 值
Fig. 1 MAE of different values 170
从图1可以看出， 取值时推荐效果最好。
实验二：将本文的改进算法和下列两种算法比较，并评估算法的性能。
（1）传统的CF Pearson算法；
（2）文献[5]中Golbeck提出的TidalTrust算法；
根据实验一的的结论 取值，图2比较了不同邻居数情况下三种算法的MAE值。 175
图 2 不同算法的 MAE 值比较
Fig. 2 MAE of different algorithms
从实验结果的图示中可以看出，本文提出基于信任和用户兴趣聚类的协同过滤算法相对
于传统的协同过滤算法（CF Pearson算法）和基于信任度的协同过滤算法（TidalTrust算法）180
具有较小的MAE值，即提出的算法在推荐准确性上有所改善。在社会化网络推荐中，CF
Pearson算法没有考虑用户的社会化关系数据，而TidalTrust算法缺少了来自传统基于项目评
分相似性的用户数据。本文提出的改进算法不仅在计算用户相似性时同时考虑了兴趣相似性
和用户信任度，而且对相似用户进行聚类，减小了用户最近邻居的搜索空间，所以推荐的响
应速度和推荐的精度均有所改善。 185
4 结论
本文在现有社会化网络推荐系统的研究基础上，提出了一种基于信任和用户兴趣聚类的
协同过滤算法。算法首先计算用户信任度和兴趣相似度并将两者结合，利用结合后的调和相
似度对用户进行聚类。当需要进行推荐时，判断目标用户所属聚类，再在对应聚类中搜索目
- 7 -
中国科技论文在线
标用户的最近邻居，从而在尽量小的用户空间上搜索目标用户的最近邻居，最后根据最近邻190
居对项目的评分预测目标用户对项目的评分并产生推荐列表。通过在真实数据集上进行实验
对比，表明该算法可以得到更小的 MAE 值，从而提供更准确的社会化网络推荐。
[参考文献] (References)
[1] 许海玲, 吴潇, 李晓东. 互联网推荐系统比较研究[J]. 软件学报, 2009, 20(2): 350-362.
[2] 王立才, 孟祥武, 张玉洁. 上下文感知推荐系统[J]. 软件学报, 2012, 23(1): 1-20. 195
[3] LIN J G, ZHOU T, WANG B H. Personalized recommender systems: A survey of the state-of-the-art[J].
Chinese Journal of Progress in Natural Science, 2009, 19(1): 1-15.
[4] Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the
state-of-the-art and possible extensions[J]. Knowledge and Data Engineering, 2005, 17(6):734-749.
[5] Golbeck JA. Computing and applying trust in web-based social networks[D]. Washington .: University of 200
Maryland at College Park, 2005.
[6] Avesani P, Massa P, Tiella R. A trust-enhanced recommender system application: Molesking[C]. In
Proceedings of the 2005 ACM symposium on applied computing, Santa, 2005: 1589-1593.
[7] Yuan Q, Zhao SW, Li chen. Augmenting collaborative recommender by fusing explicit social relationships[C].
In ACM Conference on Recommender System workshop on Recommender Systems and the Social Web, New 205
York, 2009: 49-56.
[8] Jamali M, Ester M. Trustwalker. A random walk model for combining trust-based and item-based
recommendation[C]. In KDD' 09: Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery
and Data Mining, 2009: 397-406.
[9] Jebrin AS, Williams MA. Credibility-aware Web-based Social Network Recommender: Follow the Leader[C]. 210
In Proceedings of the 2nd ACM RecSys'10 Workshop on Recommender System and the Social Web, Barcelona,
2010.
[10] 黄武汉, 孟祥武, 王立才. 移动通信网中基于用户社会化关系挖掘的协同过滤算法[J]. 电子与信息学
报, 2011, 33(12): 3002-3007.
[11] Donovan J, Smyth B. Trust in recommender systems［C]. Proceedings of the 10th International Conference on 215
Intelligent User Interfaces, 2005: 167-174.
[12] Herlocker J L, Konstan J A, Terveen L G. Evaluating collaborative filtering recommender systems[J]. ACM
Transactions on Information Systems, 2004, 22(1): 5-53.
