打开文本图片集
摘要：目前多数社交网络主要根据已有好友关系推荐潜在好友，用户的兴趣爱好不作为主要考虑因素；此外，如何从大量数据中精确地提取用户的兴趣爱好是一项十分艰巨的任务。为此，提出一种在大量标注行为数据中精确挖掘出用户的兴趣爱好，并据此推荐具有相同兴趣爱好的潜在好友的算法——基于标注的好友推荐（FRBT）算法。首先使用词频逆向文件频率（TFIDF）对标签进行聚类，将语义相似的标签聚成话题；然后在话题的基础上提出一种新的相似度公式来计算用户相似度；再融合基于话题与基于物品的用户相似度，将相似度较高的用户作为潜在好友进行推荐。在Delicious数据集上以准确率和召回率为指标与item、tag和trigraph三种算法进行与什么比较？写明比较对象为指标与其他三个算法进行比较...比较，实验验证了该算法能够更准确地为用户推荐兴趣相似的好友。
关键词：好友推荐；协同标签系统；用户兴趣；标签聚类；话题模型
中图分类号： TP391 文献标志码：A
Abstract：Friend recommendation is one of the most important applications of social networking. At present， most social networking systems recommend potential friends mainly according to the existed friend relationship， and users interests are not emphasized. Furthermore， it is a very difficult task to find users interests with high precision from a large amount of data. A Friend Recommendation Based on user Tagging （FRBT） algorithm was proposed to find potential friends with the same interests by mining users interests in tagging behavior data. First， Term FrequencyInverse Document Frequency （TFIDF） was used to cluster the similar semantic tags into topics. A new formula for calculating the users similarity of topics was described. Combined with the user similarity based on topic and item， the proposed algorithm could recommend the users with high similarities as potential friends. The experimental results on tagging dataset of Delicious validate， compared wtih the algorithms of item， tag and trigraph， FRBT has better performance in terms of precision and recall.
英文关键词
Key words：friend recommendation； collaborative tagging system； user interest； tag clustering； topic model
0 引言
随着Web 2.0的发展，协同标签系统逐渐兴起，与此同时，社交网络也成现代网民们必不可少的交往方式。好友关系是社交网络中的最基本组成部分，所以好友推荐也成为社交网络应用中的重中之重。
好友推荐算法主要为两类：一类是基于社交网络图的好友推荐，用来推荐他们在现实社会中互相熟悉或者在现实社会中有相关关系，而在当前社交网络中没有联系的好友；另外一类是基于共同兴趣的好友推荐，用来推荐具有共同兴趣爱好的潜在好友，不关心是否在社会中认识。本文提出的算法属于第二类。
在协同标签系统中，用户可以使用标签对资源进行标注，例如Delicious、Last.fm等系统，这种行为不仅能够描述用户的兴趣爱好，而且还能找到标签之间的相似性以及用户与用户之间相似度。因此，可以通过用户标注的行为，得到用户的兴趣爱好，找到与用户兴趣相同的潜在好友。此外，随着协同标签系统的兴起，协同标签系统规模的增大，从大量标注数据中准确地挖掘出用户的兴趣爱好变得十分困难，如何解决上述问题，以精确地为用户推荐兴趣相似的好友，这正是本文的出发点。
本文通过对用户在协同标签系统中的标注行为进行挖掘，找到与该用户具有相同兴趣爱好的用户，实现基于共同兴趣好友的推荐。如何精确地把握用户的兴趣，为用户推荐好友的这项工作面临两大挑战：1）由于标签内容一般为用户自定义，所以会受到标签冗余的影响；2）单个用户标注次数太少，以致于难以把握该用户的兴趣。本文的主要研究可以归纳为：
1）通过对标签的聚类，将语义非常相似的标签聚成话题，有效地解决标签冗余的影响。另外，在话题的基础上，提出一种新的相似度公式计算用户相似度，来更精确地通过话题找到彼此之间兴趣相似的用户。
2）用户对喜欢的物品作标注，对于这些标注过的物品同样也代表了用户的兴趣，因此通过标记的物品计算用户的余弦相似度，并且融合基于话题与基于物品的用户相似度，解决单一通过物品或者话题计算用户相似度时，出现所包含的信息量不足的问题。
3）本文算法只对用户标签行为进行挖掘，并不考虑用户已经存在的好友信息，可以解决目前多数的算法在某个用户只有极少数好友以及没有好友的情况下，所产生的冷启动问题。
1 相关工作
1.1 好友推荐方法
近年来，社交网络的发展十分迅速，好友推荐作为社交网络最重要的应用，成为了研究的热点。当前的好友推荐算法主要是基于社交网络图的好友推荐与基于用户兴趣的好友推荐，由于社交网络用户的大量增长，如何准确推荐具有相似兴趣的好友变得十分困难，与引言内容过于重复文献[1]通过用户在博客中的行为，分析用户的兴趣，找到具有相似兴趣的潜在好友。由于用户的朋友可以组成多个社交圈，拥有相似社交圈的用户更容易成为好友，因此文献[2]提出了社交圈检测算法，定义了用户间社交圈相似性，在基于社交圈的相似程度上，为用户推荐新的朋友。鉴于全球定位系统（Global Positioning System，GPS）等技术能够记录用户所在区域的历史信息，文献[3]通过对所在区域的历史信息进行挖掘，从而计算出用户与用户之间的相似度。文献[4]通过手机蓝牙技术得到与其他手机的距离信息，将距离记录处理后，形成网络图，然后使用基于社会网络理论的地理近邻与链路预测算法进行好友推荐。文献[5]提出了一种基于图的加权最小信息比率好友推荐算法，首先建立用户与用户之间互动次数的图，然后选取两用户之间互动次数少的次数为权重，然后进行好友推荐。
在不同的系统环境中推荐的对象与目的具有很大的差异，因此好友推荐算法通常只针对一个具体的环境问题，对其他的情况可能并不适用。所以对于在协同标签系统环境下，需要进行具体的好友推荐算法的研究。文献[6]提出了在协同标签系统环境下，通过社区发现的方法来构建用户的标签图，以建立用户爱好的模型，并通过KL（ KullbackLeibler ）散度来衡量出用户之间兴趣的相似度，为用户推荐潜在好友。
1.2 协同标签中的模型
文献[7]提出了基于扩散的三分图算法，通过建立句子不通，原文中“以”删去。是，谢谢修改.用户资源标签的三分图，将两种的扩散结果结合起来，进行物品推荐。由于大部分基于标签的方法忽视了标签与标签之间的语义信息，因此，文献[8]提出了一种基于加权标签图的方法，充分考虑了标签与标签之间的关系，所以能准确地把握用户的偏好，为用户推荐物品。文献[9]利用标签来计算用户之间相似度以及物品之间的相似度，此外，还使用好友关系计算用户兴趣相似度，进行物品推荐。
在协同标签系统中，标签的内容一般为用户自定义生成内容，因此会导致标签冗余与歧义。为了解决这个问题，Gemmell等[10]、Shepitsen等[11] 提出了一种对标签进行层次聚类的方法，并且应用在物品推荐上。本文借鉴了这种对标签处理的方法，并以此为基础进行好友推荐，提出了基于用户标注行为的好友推荐（Friend Recommendation Based on user Tagging，FRBT）算法。
2 基于用户标注行为的好友推荐算法
2.1 通过话题计算用户相似度
用户经常会对自己喜欢的物品作标注，这些物品一定程度上代表了用户的兴趣爱好。同样，用户所使用的标签也能代表用户的某些兴趣，针对标签出现冗余和歧义，本文借鉴文献[10-11]的算法，计算出话题爱好的用户相似度，并且融合物品爱好的用户相似度，为用户推荐具有相同爱好的潜在好友。
用来度量标签t与s之间的相似度，然后将所有的标签分配一个单独的类，先合并相互之间余弦相似度大的标签，经过多次的合并，最终形成一个类似二叉树结构，里面包含了所有的标签。对树的层次进行分割，分割得到的节点为标签形成的类，这种类被称为话题。算法在上述步骤中形成的话题的基础上进行物品的推荐。
本文以这种思想为基础，首先计算出tfidf，利用余弦相似度计算出标签与标签之间的相似度矩阵，然后对所有的标签分配一个单独的类，选择余弦相似度最大的话题进行合并，然后更新相似度矩阵。合并的话题与其他话题的相似度为话题中所有标签对其他话题的平均值，如图1（a）所示，选择相似度最大的标签进行合并，此时合并T3和T4，相似度为0.9。合并后，更新相似度矩阵，如图1（b）所示合并T3和T4，T3中与T1的相似度为0.5=（0.4+0.6）/2，与T3的相似度为0.8=（0.85+0.75）/2。
定义一个阈值Y，重复上述步骤，不断合并话题，直到相似度矩阵中的所有值都小于阈值Y，结束合并。阈值Y代表了话题粒度的大小，这个值的大小是否写成“经验值”或“通过实验结果优化调整”更好？...的大小， 由实验经验设定值：如果...由实验经验设定：如果阈值Y过大，一些相似度较大的标签并不能聚到同一话题中；若阈值Y过小，会将一些不太相关的标签聚到同一个话题中。在本文的实验中Y取0.5～0.7的效果最好。通过多次的合并最终形成话题，从形成的话题上看，一些语义上相近的标签合并在同一个话题里。如表1所示，同一列的标签属于同一个话题，travelguide与travelguide这类相似的标签合并到同一个话题中。
其中：TP为用户u、v同时感兴趣的话题的集合，N（v，tp）代表用户v喜欢话题tp的程度，取值为用户在话题tp中所有标签的标记次数之和。取用户u、v对话题tp最小的喜欢程度作为在话题tp上u与v相似程度，例如用户u、v对话题tp1的喜欢程度分别为5和12，那么用户u、v在话题tp1上的相似程度为5。对集合TP中的话题tp进行u与v的相似度程度的进行累加并归一化，作为用户u与v的总的相似程度。
2.2 融合基于物品的用户相似度
用户对某个物品打上标签，同样代表用户对此物品有某种兴趣，因此对同一个物品有过标签行为的用户，可能有共同的兴趣爱好。对标签使用的次数越多，越代表用户对这个标签所代表话题的兴趣，与标签不同，用户对一个物品打上标签的个数只能代表这个物品本身的属性，并不能代表用户对物品兴趣的程度有多大。因此在用物品计算用户相似度时应使用非加权的余弦相似度，定义为：
算法总的基本步骤如下：
1）计算出标签与物品之间的tfidf，再由tfidf计算出标签与标签之间的余弦相似度。
2）将标签合并成话题，首先标签分配为一个单独的话题，选择相似度最大的进行合并，然后更新相似度矩阵，依次合并，直到相似度矩阵中任何值都小于手动输入的阈值Y。
3）对合并后的话题使用新的相似度计算公式来计算，得到基于话题的用户之间的相似度。
4）使用非加权的余弦相似度对物品进行计算，得到基于物品的用户相似度。
5）输入权重θ，原文缺少内容，是否可改为cos（u， v）和sim（u， v）代表基于物品的用户相似度权重，1-θ代表基于话题的用户相似度权重，对两种用户相似度进行融合。
6）融合后，将相似度大的用户作为潜在好友进行推荐。
3 实验与分析
3.1 实验数据
本算法是建立在协同标签系统的基础上，对〈用户，物品，标签〉这类三元组数据进行挖掘。实验的数据为hetrec2011delicious2k，为HetRec2011上发布的公开数据集，可以通grouplens的网站进行下载[12]，数据包含了社会关系网络、书签以及标签信息，取自Delicious协同标签系统，文件user_taggedbookmarks中包含[用户， 标签， URL]，作为算法的训练集；文件user_contacts中包含了[用户， 好友]，作为算法的测试集，验证好友推荐的效果。
3.2 实验结果
为了验证本算法的有效性与可行性，本文将与其他方法进行比较，包括利用购买物品记录，使用余弦相似度计算出用户相似度，进行好友推荐的方法什么意思，方法名称？是的，对比方法的名称item；利用标签标注记录，使用余弦相似度计算出户相似度，进行好友推荐的方法tag。与本算法类似，基于三分图的物质扩散算法[7]也基于〈用户，物品，标签〉这类三元组数据，将其应用到好友推荐上与本文提出的算法进行比较，分别用FRBT与trigraph来表示本文提出的方法与三分图方法。
3.3 参数Y与θ对算法性能的影响这一节内容是否有问题，前面直接说明了两个参数的最优取值，这里完全是在这个基础上的讨论吧？前面主要是和其他算法进行性能比较，这一小节主要讨论参数对性能的影响。用实验说明最优取值是如何得来的。
本文算法有两个参数，分别为代表话题粒度大小的阈值Y与代表线性融合时通过话题计算出的用户相似度所占的权重比值θ。图4展示了Y为0.65时，算法性能在取不同参数θ的情况下，对算法性能的影响。可以看出在θ的取值范围[0，1]上，一开始随着原稿掉了参数，请核实添加的是否正确添加正确，谢谢～θ的增大，算法的性能逐渐变好，随着θ到0.8左右时性能最优，然后又逐渐下降。当θ为0时，相当于只使用了基于话题的用户相似度；当θ为1时，相当于只使用了基于物品的用户相似度。
Y代表话题的粒度大小，实验观察到Y取0.5以上时，性能较优，图5展示当θ是否漏了变量名θ？是的，添加正确，谢谢。
取0.802时，Y在取值范围[0.5，1]上对算法性能的影响。可以看出Y从0.5到0.65时，Recall@20不断上升，取0.65左右时性能最优。当Y取1时，每个话题仅有一个标签。
4 结语
本文对协同标签系统中的潜在好友推荐进行了研究，通过对用户的标注行为进行挖掘，考虑到标签冗余与信息量不足的情况，提出了一种为用户推荐兴趣相似的潜在好友算法FRBT。该算法将语义相似的标签聚成话题，并提出一种新的基于话题相似度公式来计算出用户相似度，更加精确地反映用户之间的兴趣相似度；再融入用户对物品兴趣的信息，提高了用户相似度的准确性。然而使用ifidf只能对标签进行硬聚类，并不能考虑一词多义的情况。因此在今后的研究工作中需考虑一词多义的情况，对标签进行软聚类，进一步提高推荐模型的精度和效率。
参考文献：
[1]HSU W， KING A， PARADESI M， et al. Collaborative and structural recommendation of friends using weblogbased social network analysis [C]// Proceedings of AAAI Spring Symposium： Computational Approaches to Analyzing Weblogs.Menlo Park：AAAI，2006： 55-60.
[2]WANG Y，GAO L. Social circlebased algorithm for friend recommendation in online social networks [J].Chinese Journal of Computers， 2014，37（4）： 801-808.（王玙，高琳.基于社交圈的在线社交网络朋友推荐算法[J].计算机学报，2014，37（4）：801-808.）
[3]LI Q， ZHENG Y， XIE X， et al. Mining user similarity based on location history [C]// Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2008： 34-42.
[4]QUERCIA D， CAPRA L. FriendSensing： recommending friends using mobile phones [C]// Proceedings of the Third ACM Conference on Recommender Systems. New York： ACM， 2009： 273-276.
[5]LO S， LIN C. WMR — a graphbased algorithm for friend recommendation [C]// Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence. Piscataway： IEEE， 2006： 121-128.
[6]ZHOU T， MA H， LYU M， et al. UserRec： A user recommendation framework in social tagging systems [C]// Proceedings of the TwentyFourth AAAI Conference on Artificial Intelligence. Menlo Park： AAAI， 2010：1486-1491.
[7]ZHANG Z， ZHOU T， ZHANG Y. Personalized recommendation via integrated diffusion on useritemtag tripartite graphs [J]. Physica A： Statistical Mechanics and its Applications， 2010， 389（1）： 179-186.
[8]LI D， XU Z， XUA Z， et al. Item recommendation in social tagging systems using tag network [J]. Journal of Information and Computational Science， 2013， 10（13）： 4057-4066.
[9]JIN J， CHEN Q. A trustbased TopK recommender system using social tagging network [C]// Proceedings of the 2012 9th International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway： IEEE， 2012： 1270-1274.
[10]GEMMELL J， SHEPITSEN A， MOBASHER B， et al.Personalizing navigation in folksonomies using hierarchical tag clustering [C]// Proceedings of the 10th International Conference on Data Warehousing and Knowledge Discovery， LNCS 5182. Berlin： Springer， 2008： 196-205.
[11]SHEPITSEN A， GEMMELL J， MOBASHER B， et al.Personalized recommendation in social tagging systems using hierarchical clustering [C]// Proceedings of the 2008 ACM Conference on Recommender Systems. New York： ACM， 2008： 259-266.
[12]GROUPLENS. Delicious bookmarks [EB/OL]. [2014-12-04].http：//grouplens.org/datasets/hetrec2011/.
[13]WEN Z， LIN C. Improving user interest inference from social neighbors [C]// Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 1001-1006.
[14]YUAN Q， CHEN L， ZHAO S. Factorization vs. regularization： fusing heterogeneous social relationships in topn recommendation [C]// Proceedings of the Fifth ACM Conference on Recommender Systems. New York： ACM， 2011： 245-252.
[15]XIA N， SU Y， QIN H， et al. Method for personalized user profiling in social tagging systems [J]. Journal of Computer Applications， 2011， 31（6）： 1667-1670.（夏宁霞，苏一丹，覃华，等.社会化标签系统中个性化的用户建模方法[J].计算机应用，2011，31（6）：1667-1670.）
[16]ZHANG Y， YUE L， ZHANG Y， et al.Friends recommended method based on common users and similar labels [J]. Journal of Computer Applications， 2013， 33（8）： 2273-2275. （张怡文，岳丽华，张义飞，等.基于共同用户和相似标签的好友推荐方法[J].计算机应用，2013，33（8）：2273-2275.）
[17]CHEN J， GEYER W， DUGAN C， et al.Make new friends， but keep the old： recommending people on social networking sites[C]// Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. New York： ACM， 2009： 201-210.
[18]ZHANG Y， AHMED A， JOSIFOVSKI V， et al. Taxonomy discovery for personalized recommendation [C]// Proceedings of the 7th ACM International Conference on Web Search and Data Mining. New York： ACM， 2014： 243-252.
