基于社会网络的协同推荐方法

) JJournalofYantzeUniversitaturalScienceEditionun.2015,Vol.12No.16gy(N

[引著格式]汪千松,蒋胜,王忠群.基于社会网络的协同推荐方法[].长江大学学报(自科版),2):2J015,12(169~33.

·29·

基于社会网络的协同推荐方法

汪千松,蒋胜,王忠群

(安徽工程大学现代教育中心,安徽芜湖2)41000

[摘要]针对传统协同过滤推荐算法存在推荐精度低的问题,提出了一种基于社会网络的协同推荐方法。该方法融合了社会网络中用户的相似度与信任度,首先计算用户间的评分相似度;再由直接信任度与间接信任度加权得出用户信任度;最后综合用户相似度与信任度得出用户间的推荐权重,并以推荐权重来选取最近邻居集,为目标用户形成推荐。试验结果证明,该方法可有效提高推荐系统的推荐精度。[关键词]社会网络;协同过滤;推荐精度;信任度;推荐权重[中图分类号]TP391

[)1文献标志码]A [文章编号]16731409(20156002905

随着信息技术与电子商务的飞速发展,商品信息数据的爆发式增长导致人们淹没于信息数据的海洋之中,如何快速、有效地找出用户的兴趣偏好信息并给予相应地推荐这一问题,成为近年来人们研究的热点。推荐技术可有效地缓解信息过载为人们带来的困扰,但仍然存在推荐精度低的问题。

]利用社会学原理,从用户信任网络出发,兼顾用户群体间针对推荐技术精度低的问题,文献[1

]通过引入了信任支持度的概念来准确表述兴趣偏好,通过信任的可传递性来提高推荐效率;文献[2信任网络中的客户信任关系,提出了一种信任度与信任支持度相结合的客户信任模型;文献[3]采用

随机游走的方式选取最优的邻居集,以云模型相似度方法计算项目间的相似度,该方法提高了算法的效]采用了正反相结合的方式,提出了基于信任与不信任关系的推荐方法;文献[]为了提率;文献[45

高推荐结果的准确性以及可靠性,提出了一种结合语义Web和用户信任网络的协同过滤推荐模型;文]为了在节点之间建立信任关系,从而提出了一种基于群组的信任管理模型。献[6

最近邻居集的选取作为协同过滤推荐技术的关键步骤,其准确性直接影响系统的推荐准确性。较早

7~9]

,可见推荐的准之前就有学者研究表明,用户往往更加倾向于接受熟人、好友而非推荐系统的推荐[

确性不仅仅与目标用户的兴趣偏好相关,还与其在社会网络中的用户信任有更加紧密的联系。为此,笔者通过融合目标用户在社会网络中的相似度与信任度,提出了一种基于社会网络的协同推荐方法。

1 理论与方法

1.1 基于用户项目评分的相似度计算

,商品项目集合为I={1)建立用户项目集 定义用户集合为U={u1,u2,…,un}ii1,2,…,

;,当用户无行为时r;所有用户对如购买或评分行为)iri的行为(n}u,i表示用户u对项目u,i则记为0

项目的行为可以表示为一个m×n的矩阵,记为Rm×n。

)用户项目评分相似度计算 目前相似度的计算方法主要余弦相似度、修正的余弦相似度及2Pearson相关相似度度量方法,笔者采用修正的余弦相似度计算方法:

sim(a,b)=

i∈Iar∑(

i∈Ia,b∑

()(b,i-r)rr􀭵􀭵a,i-arb2

)-r􀭵aa,ii∈Ibr∑(

b,i2

)-r􀭵b()1

[收稿日期]20150227

);安徽省高校省级自然科学研究项目(K)。 [基金项目]教育部人文社科规划项目(13YJA630098J2012B022

:q [作者简介]汪千松(1978),男,硕士,工程师,现主要从事网络信息安全与电子商务方面的教学与研究工作;E-mailswang@

。ahu.edu.cnp

式中,sim(a,b)表示用户a、b之间的相似度;Ib共同评分的项目集;ra,b表示用户a、a,i表示用户

、、;a、a对项目i的评分;rIb􀭵􀭵b分别表示用户a、arb分别表示用户ab对其评分项目集的平均评分I各自评分项目集。

1.2 基于社会网络的用户信任度计算

传统协同过滤推荐算法主要是依据相似用户具有相似的偏好兴趣,但由于用户的评分数据较为稀、;并且在以往的历史推荐里,用户u、在某个推荐数据集中,2个用户uubc均属于用户ua的邻居集b,由用户uuua各推荐了10次。通过用户u0次结果中只有2次结果符合用户c对c的反馈得知b推荐的1,这表明用户uua的兴趣;而由uc产生的推荐符合ua兴趣偏好的结果有8次a对uc给出的推荐信任度

。而在现实环境中,人们更加倾向于采纳亲戚或好友给出的推荐,即在社会要远远高于ub给出的推荐网络中,信任度的高低对目标用户的购买决策具有较大的影响作用。

因此,笔者在用户评分相似度的基础之上,利用社会网络中用户间的信任关系作为选取最近邻居的另一个根据。信任在社会网络中的传递涉及到直接和间接信任2个方面:直接信任即是2个网络用户节2个网络用户节点之间并没有直接的联接关系,但是由网络中的其他节点联接起来,这体现了信任的可

传递性。

)直接信任 定义用户直接信任度如图1所示,其中1

item1,item2,…,itemn表示用户ua与uc共同评分的项目

(,),a,n表示用集,tudirac表示用户ua与c的直接信任度r户utemn的评分。a对项目i对用户uc,且j∈Ic:c所有评价项目集合I()irrm(a,c)􀭵c,c×sj- pa,j=r􀭵a+

sim(a,c)||

点之间直接可以建立联系,笔者的研究中表示为2个用户之间有一定数量的共同评价项目;间接信任即

]10

。假设疏,导致在计算用户相似度时,存在较大的偶然因素,无法较为准确地度量用户间的相似性[

·30· 理工上旬刊*计算机科学与电子信息工程2015年6月

()2

式中,pa,j表示用户uc对目标用户ua在项目j上的预测评

、;c,j表示u。分;rru􀭵􀭵a与c分别表示uac的平均评分rc对j的评分

(,) tdirac= pre

ja,c 图1 社会网络中直接信任关系图

依据预测评分与真实评分之间的误差,可以得出用户之间的直接信任计算公式:

∑

I||c0 其他j式中,preuua在项目j上的预测能a,c表示用户c对目标用户力估计值;pa,j表示用户uc对用户ua在项目j上的预测评分;表示用户urj的真实值;常数μ为用户直接a,a对项目j信任度参考值,笔者取μ=1.0。

)间接信任 社会网络中,用户间的间接信任反映出2

、信任具有可传递性的特点。假设在用户uubc之间并没有共同评分项目,那么用户间直接信任度为0;但这显然对用户信任度的描述是不完全正确的。因此,笔者定义用户信任度是综合了直接信任与间接信任。在社会网络中用户的间接

=

{

且|pa,j-r1 r≤μa,a,j≠0j|

I|c|

i=1

jprea,c()3()4

、信任关系图如图2所示,其中集合UB表示用户uuac共同

(,)。 图2 社会网络中用户间接信任关系图的邻居集,tindac表示用户ua对用户uc的间接信任度

基于以上分析,在社会网络中,只考虑2步可达信任关系,即只通过一个中间用户建立2个直接信任度为零的用户。因此用户间接信任度计算公式为:

第12卷第16期

汪千松等:基于社会网络的协同推荐方法

UB||

(,i)(i,},即UB表示所有由用户u式中,UB={utc)u≠0且t≠0i|diraudirua节点到用户c节点2步

可达的用户集合。

)用户综合信任度的计算 用户u(,)3a对用户uc的综合信任度Tac是综合了直接信任与间接信任,其计算公式如下:

(,)(χ)(,) T(a,c)tt=χdirac+1-indac),取χ=0χ表示直接信任的被重视程度,χ∈(式中,0,1.8。

(,) tindac=

b∈UB∑t ·31·

dir

((,)a,b)t×dirbc()5

()6

2 基于社会网络的协同过滤推荐算法

由于人们通常更加倾向于接受好友或亲戚熟人的推荐,即使用户之间的兴趣偏好相似度较高的邻居用户,由于信任度的差异,最终的推荐结果也会有不同。融合用户偏好的相似度与用户间信任度对提升算法的推荐结果准确性具有重要意义。因此,笔者提出一种基于社会网络的协同过滤推荐算法,其推荐过程示意图如图3所示。

图3 社会网络中用户间接信任关系图

重计算方法如下:

图3基于社会网络的推荐系统框架将引入推荐权重来综合用户偏好相似度及用户信任度,推荐权

()7

UK。得出目标用户预测评分计算公式:

r'r􀭵a,i=a+

c∈UK式中,w(a,c)表示用户uc与目标用户ua的推荐权重。

依据上述推荐权重w(a,c)的计算结果,选择权值最大的K个用户作为目标用户的最近邻居集

2sim(a,c)a,c)×T( w(a,c)=

sim(a,c)a,c)+T(

r∑(

c,i)(,)-r􀭵c×wac。选出评分高的tuo-N个项目推荐给用户,推荐完成。pc对项目的平均评分

、、式中,r'i的预测值;ri的评分值;r􀭵􀭵a,i表示用户ua对项目c,i为用户uc对项目arc分别为用户uac∈UKa,c)|∑|w(

()8

3 算法描述及复杂度分析

3.1 算法描述

输入:目标用户uT,用户评分项目矩阵Rm×n,用户信任矩阵Tm×m,邻居数k;输出:To-N推荐结果。p推荐步骤如下:

Ste1 对每个用户u,找到同目标用户uT共同评分过的项目,将其记录在items中;p

·32·

)计算用户间的间接信任度,并通过式(Ste4 根据式(56)计算用户间的集成信任度,并将其p

结果存入矩阵Tm×m中;

)得出用户间的推荐权重;Ste5 融合用户相似度与信任度,由式(7p

)计算得出目标用户uT的所有项目的预测评分;Ste6 根据式(8p

)计算用户评分间的相似度s;Ste2 依据用户评分矩阵Rm×n,使用式(1im(a,b)p

)得出预测评分与真实评分之间的偏差值,然后由式()得出用户间的直接信任度;Ste3 由式(23p

理工上旬刊*计算机科学与电子信息工程2015年6月

Ste7 为目标用户uT生成To-N推荐。pp

3.2 复杂度分析

根据算法描述,假设用户数为m,项目数为n,最近邻居数目为k,则:

)S;3te3计算预测评分与真实评分之间的偏差大小,复杂度为O(n2)p)S;4te4计算用户间的间接信任度,复杂度为O(m2)p

)S;1te1系统初始化阶段,遍历目标用户与其他用户间共同评分过的项目,因此其复杂度为O(n)p)S;2te2由矩阵计算目标用户与其他用户之间的相似度,复杂度为O(m2)p

)S5te5、Ste6、Ste7阶段为用户推荐阶段,主要的时间是在项目的排序上,因此复杂度最差为ppp。O(m2)

虽然推荐计算量会随着用户评分数据和标签数据的增加而有所增加,但是相比较传统的协同过滤算法,新方法在提高推荐准确度的同时并没有增加算法的推荐时间,具有一定的可行性。

4 试验结果与分析

4.1 数据集及试验环境

采用来源于美国明尼达苏大学GrouLens研究小组提供的MovieLens站点100K公开数据集。其p内容主要包括来自943个用户对1682部电影的大约100000个评价分数信息,每个注册用户均对其观看试验过程中,整个数据集被随机分出20%当作试验的测试集,其余的80%当作试验的训练集。

过得电影进行评价并给出评分值且都至少评价了2不喜0部电影;评分值在1到5之间;“1”表示“

、“”表示“、“”表示“、“”表示“、“。欢”不太喜欢”一般喜欢”比较喜欢”非常喜欢”2345”表示“,4验证。试验环境为IntelCorei5处理器,CPU主频为2.5GHzG内存的PC机,Windows7操作系统,dk版本为1.7。j

笔者采用Java实现了基于社会网络的协同推荐方法,并设计了若干试验对该方法的推荐效率进行

4.2 评价指标

考虑推荐算法优劣程度,可以由很多指标来评价。笔者通过系统的平均排序分、平均绝对误差2个指标验证算法的效率及其性能。

)平均绝对误差(1MAE) 通过计算测试集中用户实际评分和利用推荐算法预测出来的评分间的绝

[]1

。对误差值来度量推荐系统的推荐准确度。当MAE的值越小,表明推荐结果的精度越高,反之,则越低1,而真实的用户评价集记为{,则平假设预测用户评价集记为{1,2,…,p1,p2,…,pN}qqqN}

均绝对误差MAE的计算公式为:

MAE=

i=1

n;i为数据集中的真实评分值。式中,n为被评分项目的数量;pi为系统预测评分值q]12

)平均排序分 通过计算项目在列表中位置度量系统推荐的精准性。其计算公式[如下:2

∑|pni-qi|

()9

Li() r10i=

N式中,N为未被评分的项目数;Li为i在推荐列表中的序号。

当系统排序分越小,那么表明推荐结果能够较好地符合用户的兴趣偏好。对全部用户项目对的排

第12卷第16期

汪千松等:基于社会网络的协同推荐方法

4.3 结果分析

)算法的准确率对比 为了验证笔者提出算法在推荐结果精确度方面较其他类似算法具有的优势,1、基于项目的协同推荐算法(把其与基于用户的协同推荐算法(CF-USER)CF-ITEM)及其他基于信

2]

(任的推荐方法[信任支持度)进行了对比,结果如图4所示。由图4可以看出,相同数量用户邻CF-居集下,笔者提出算法的MAE值均低于其他几种算法,且当最近邻居数为40时,该算法推荐精度达

到最优;继续增大邻居数量可以发现,该方法推荐精度逐渐地趋向于平稳。

)算法的平均排序分对比 各算法平均排序分试验结果如图5所示。由图5中可以发现,随着数2

据集中训练集占的比重逐渐增加,算法的平均排序分也慢慢地减小,笔者提出算法计算得出的平均排序分要低于另外3个算法。综上所述,该方法在推荐精度上要高于其他几个方法。

序分计算均值,即为平均排序分rr􀭵,通过以该数值来衡量推荐方法精确度,􀭵越小,算法效率越高。

·33·

图4 推荐算法的MAE比较 图5 算法的平均排序分

5 结语

推荐系统作为解决信息过载的一种有效手段,如何提高其推荐精度已成为非常重要的研究问题。在社会网络中考虑推荐信任对推荐准确性的提高具有重要的意义。但人们对推荐技术的满意度不仅仅体现在推荐结果的准确性上,下一步的主要工作是提出有效的算法来提高用户对推荐系统的满意度,包括推荐结果的覆盖率、多样性等等。

[参考文献]

[]M1assaP,AvesaniP.Trust-AwareCollaborativeFilterinorRecommenderSstems[A].ProcofFederatedIntConferenceonthegfy

:,MovetoMeaninfulInternetCoois[C].SrinerBerlinHeidelber2004:492~508.gppgg[]丛丽辉,王科,夏秀峰,等.利用信任支持度构建客户信任网络[]):12J.计算机工程与应用,2012,48(610~113.

[],,[],:():朱丽中徐秀娟刘宇基于项目和信任的协同过滤推荐算法计算机工程3.J.201339158~66.

[]V,]4ictorCornelisP,CockC,etal.Trust-andDistrust-BasedRecommendationsforControversialReviews[J.IntellientSstemsgy

):4IEEE,2011,26(18~55.1714~1718.

[]施荣华,幸晶晶.一种基于群组的P]):262P网络信任管理模型[J.计算机应用研究,2010,27(7638~2640.[]张富国.基于社交网络的个性化推荐技术[]):17J.小型微型计算机系统,2014,35(7470~1476.

[]徐守坤,孙德超,李宁,等.一种结合语义W]:5eb和用户信任网络的协同过滤推荐模型[J.计算机应用研究,2014,31(6)

[]B]8huianT.Asurventherelationshietweentrustandinterestsimilaritnonlinesocialnetworks[J.JournalofEmerinyyopbyigg

,):2TechnoloiesinWebIntellience2010,2(491~299.gg[]黄创光,印鉴,汪静,等.不确定近邻的协同过滤推荐算法[]):19J.计算机学报,2010,33(8369~1377.

[]乔秀全,杨春,李晓峰,等.社交网络服务中一种基于用户上下文的信任度计算方法[]:210J.计算机学报,2011,34(12)403~2413.[]]:e,11ZhouT,JianSuRQ,etal.Effectofinitialconfiurationonnetwork-basedrecommendation[J.ElurohsicsLettersgLL,gppy

):12008,81(55~18.[]赵琴琴,鲁凯,王斌.]):612SPCF:一种基于内存的传播史协同过滤推荐算法[J.计算机学报,2013,36(371~676.

[编辑] 洪云飞