基于活动的社交网络中的群组推荐算法设计①

朱成纯,张 谧

(复旦大学 计算机科学技术学院,上海 200203)

基于活动的社交网络中的群组推荐算法设计①

朱成纯,张 谧

(复旦大学 计算机科学技术学院,上海 200203)

在基于活动的社交网络(EBSN)中,群组中聚集了具有相似兴趣的用户,并为用户组织并举办线下活动,在社区的发展中起到了至关重要的作用,因而理解用户加入群组的原因和群组形成的过程在社交网络的研究中是一个重要的议题.本文通过基于活动的社交网络中的一些相关内容信息,比如社交网络中的标签信息和地理位置信息,来辅助推荐系统更好地为用户预测对于群组的偏好.本文提出了SEGELER(pair-wiSE Geo-social Event-based LatEnt factoR)模型,并使用这些社交网络中的信息,来为用户的兴趣进行预测.通过在真实的EBSN数据集上进行实验与验证,本文的模型不仅可以有效提升对于用户偏好的预测,也可以缓解冷启动问题.

社交网络;推荐系统;群组推荐;贝叶斯个性化排序;潜在因子

在社交网络中,群组是一个基本的组成部分,并在用户社交行为的参与中起到了非常重要的作用.Charles Horton Cooley提出,线下的社交群组可以被归类为一级组,二级组和用组,而对于线上的社交网络而言,由于其相对更快速的用户变化和活动举办,对线上群组的分类是一个更加复杂的问题.在线上社交网络中,用户可以以不同的兴趣和理由加入不同的群组.例如,用户会加入一个产品交流讨论组来为想购买的产品寻求建议和讨论,而同时用户也因自己的阅读兴趣而加入了阅读小组.而关于群组形成的研究[1,2],以及预测用户对群组偏好的研究[3]在社交网络中已经成为了非常重要的研究课题.

本文研究在特定社交网络——基于活动的社交网络(EBSN)中预测用户对群组偏好.用户,群组,活动是EBSN中三种最基本的实体.用户可以加入不同的群组,并且参加由不同群组举办的不同活动.所以在EBSN中,用户之间的关系和联系也通过用户加入的群组和参与的群组活动所建立.因而在EBSN中,预测用户对群组的偏好对于帮助用户发现自己的兴趣和想参加的活动是非常有帮助的.

EBSN研究中很重要的一方面就是纳入并应用相关的信息.很多相关的研究提出了一些使用相关信息的方法,比如具有普适性的相关信息应用方法[4,5],和针对特定相关信息的应用方法,例如地点推荐研究[6]和活动推荐研究[7,8].其他一些研究标签信息的相关工作的效果[3]和活动位置信息[9]的效果也被研究与提出,但这些方法并没有考虑到活动的情况,因而无法很好的使用这些相关信息.

在ESBN社交网络中拥有很多相关信息,例如标签信息、地理位置信息、时间信息等等,其中地理位置信息作为ESBN中的重要信息,用于帮助判断用户活动范围;而标签信息作为对用户和群组的补充描述也有助于了解用户的兴趣.本文同时纳入并使用了两种社交网络中的相关信息——用户和群组的标签信息和地理位置的活动信息,来帮助更好的预测用户对EBSN社交群组的偏好.本文提出了基于ESBN社交网络中地理位置信息和标签信息的SEGELER (pairwiSE Geo-social Event-based LatEnt factoR)模型,通过利用标签信息和地理位置信息来判断用户的行为.标签的语义相似度信息和近邻影响在模型中被考虑,而pairwise的目标函数也被提出用于最大化用户对群组的偏好.对于EBSN经常受缺少负例的影响,例如只有用户参与群组的信息被记录下来,而用户讨厌或不喜欢群组的信息则会相对而言较少甚至缺失,本文也提出了有效的算法来解决这一问题.

本文通过在真实的EBSN大数据集meetup上进行实验验证得出SEGELER模型比其他的算法有明显的提升,而推荐系统中冷启动问题也可以通过使用这些社交网络中的信息来得到缓解.

1 符号定义

基于活动的社交网络(EBSN)通常拥有标签信息与地理位置的活动信息,EBSN的数据可以被定义为集合{U,G,E,T,L},其中分别代表了群组集合,用户集合,活动集合,标签集合与地点集合.活动E可以被群组G举办,而用户U可以参与不同的群组G,并根据自己的兴趣参加群组举办的活动.对于用户u,他/她所加入的群组的集合记为而他/她不感兴趣的群组的集合记为其中用户u和群组g所拥有的标签分别记为用户u所居住的地点记为表示群组g举办的活动集合,表示用户u参与的活动集合,活动e的地点记为用户,群组和活动通常由其用户ID,群组ID和活动ID来表示,而标签由有意义的描述用户和群组的词语组成,地点则由其经纬度来表示.图1展示了一个EBSN的数据结构.

图1 基于活动的社交网络基本结构

本文定义每一个用户和群组的活动范围为用户和群组去过的地点的集合:

2 SEGELER 模型

对于预测用户感兴趣的群组的问题而言,准确预测用户最感兴趣的前几位群组是非常重要的,因而本文使用排序的目标函数来优化此问题,即需要把用户感兴趣的群组排序高于用户不感兴趣的群组.

对于排序问题而言之前的研究提出了许多排序的方法,例如 pairwise 排序[10]和 listwise[11]排序.由于在本问题中只需要将感兴趣的群组排序靠前,本文使用pairwise排序的方法使用户感兴趣的群组排序高于用户不感兴趣的群组.即对于每一个用户u,以及u感兴趣的群组集合和不感兴趣的群组集合需要使的排序高于.本文基于贝叶斯个性化排序(BPR)[12]方法提出本文的pairwise排序目标函数来提取用户对群组的偏好特征,通过最大化如下的后验概率(MAP):

其中θ表示相关的模型参数,这些参数会在后面的章节进行详细解释表示用户u对群组g的估计偏好值,此值越大表示用户u对群组g的偏好越大.是 sigmoid 函数Pr(θ)表示SEGELER模型中参数的高斯先验概率分布,这部分会在后面进行详述.用户感兴趣的群组与不感兴趣的群组之间的预测值之间的差距应当变大.下一章将会详细地阐述的具体模型.

2.1 算法设计

潜在因子模型(LFM)假设用户和群组对每一个隐式因子都有偏好.对于每一个用户u和群组g,代表u与g的隐式向量表示,即u与g在这个隐式因子下的偏好.的乘积表示用户u对群组g的偏好即u对于g的偏好可以表示为:

考虑标签信息和活动范围信息之后,本文提出公式(3)以更好的预测用户对群组的偏好:

此外,David[13]提出拥有相似标签/活动范围的用户更有可能出现在相同的群组中,因此本文定义另两个隐式向量表示以考虑用户的近邻对用户的影响:

将公式(6)合并入公式(2),用户对群组偏好的式子可以延伸为:

2.2 参数学习

为求得公式(1)中的参数,本文采用了SGD(随机梯度下降)算法来最大化公式(1).在每一轮SGD迭代中,通过随机选择一个用户u,用户感兴趣的正例群组gp,与用户不感兴趣的负例群组gn,组成一个三元组{u,gp,gn},并使用梯度下降法来求解参数θ:

在SGD学习的过程中,对于每一个用户,本文只随机选取一小部分的负例(u,gn)来减少计算的复杂度,这样算法的计算复杂度为O(|D|(|L|+|T|)),其中|D|是训练集的大小.在实验中,对于每一个用户u和u感兴趣的正例群组gp,本文选取c个u不感兴趣的负例群组gn,加入训练集.c 值越大,模型训练与收敛时间越长,效果越好.通过平衡训练时间与最后的模型效果,最终本文设置参数c=5作为选取负例的数量.

在EBSN中,负例即用户不喜欢的群组很少被记录下来,这对SEGELER模型的学习和参数优化提出了很大的挑战.本文提出了一个有效的策略来选择潜在负例.此外,考虑到标签w和标签t之间拥有语义相似度,本文为入了一个相应的先验概率,标签u和标签t之间的语义相似度由WordNet计算得到,表示和标签t相似度高的标签集合.

2.3 负例选择

由于用户加入不感兴趣的群组的概率较低,可以把一些偏好值较低的群组{(u,g)}作为负例,本文提出了如下的相似度计算方法来得到用户对群组的的偏好值:

这个策略在试验中被证明十分有效,并比其他的策略效果,比如 Kabbur[14]和 Cheng[6]更好.本文在实验中设定ξ=0.015作为选取负例的阈值.

3 实验与分析

3.1 数据集介绍

本文在真实的EBSN大数据集Meetup[15]中验证了模型的效果,Meetup是一个在线社交活动网站,帮助用户发布和参与到线下的活动中.由于只有1.7%的活动是跨城市的活动,本文从Meetup中选取了三个大城市 LA(洛杉矶),SF(旧金山)和 NYC(纽约)作为三个数据集来验证SEGELER模型.

3.2 对比算法介绍

本文采用并实现了六个推荐系统领域的算法作为对比算法.

基于用户的协同过滤算法(UBCF)通过将用户的邻居信息考虑其中来预测用户对群组的偏好.由于在EBSN中,用户行为容易受到邻居影响,UBCF很适合作为这个问题的对比算法.

SVD++把用户的隐式反馈加入了考虑中,在矩阵分解中提供了额外的考虑信息.在EBSN中,用户的隐式反馈对于预测群组偏好也是很有帮助.

概率矩阵分解(PMF)是一个基于概率的因子算法,在EBSN中效果很好并被广泛应用.

NSVD是一个基于物品-物品因子的协同过滤算法,NSVD使用了用户的过往记录和相关信息.

BPR-MF是一个潜在因子协同过滤算法,通过使用BPR优化来针对个性化的排序问题.

PTARMIGAN(PTA)是一个pairwise的基于标签信息和特征的矩阵分解算法,PTA使用了诸如标签信息和地理位置信息的相关信息来预测用户对群组的偏好,PTA也是为EBSN进行特定设计的预测算法.

3.3 评价指标介绍

本文使用了三个评价指标——准确率(precision),召回率(recall)以及NDCG,来为所有方法的top-k预测进行衡量与评价.

对于每一个数据集,本文随机选择了80%的用户和与之相关的群组/活动/标签作为训练集,而将剩下的作为测试集.公式(1)中的λ在[0,0.02]中取值,所有模型的实验都经过了交叉验证.

3.4 SEGELER实验结果分析

本文在三个数据集LA,SF和NYC上将SEGELER模型与六个对照模型进行了比对.图2与图3列出了所有模型的准确率,召回率以及NDCG值.

图3的结果可以得出,SEGELER模型在三个数据集下的NDCG值的评价指标下明显超过了其他的对照算法.例如,SEGELER模型在LA数据集上的NDCG值相较其他对照算法至少17%.而图2中准确率和召回率的结果也验证了SEGELER模型相较其他模型拥有非常大的提升.这说明通过利用好标签信息和地理位置信息.并且最大化用户喜欢的群组和不喜欢的群组间的不同,SEGELER模型可以将用户喜欢的群组排序更高,从而得到更好的预测结果.

图2 各个模型的 Precision 和 Recall值

图3 各个模型的 NDCG 值

3.5 冷启动问题分析

本文也同样针对冷启动用户的预测效果进行了实验研究.在此实验中,本文将参与群组数较少的用户定义为“冷启动用户”.由于在数据集中,每一个用户平均参与了40个群组,本文中将参与少于10个群组的用户和少于15个群组的用户定义为两种情况下的“冷启动用户”.图4展示了在LA数据集上top-3准确率上不同算法的结果.从图4中可以看出,在两种情况下,SEGELER模型都比其他对照算法效果更好,并取得了至少48.21%的提升.这说明通过对于相关标签信息和地理位置信息的挖掘,SEGELER算法可以更好的帮助新用户来选择感兴趣的群组.

3.6 负例选取方法实验分析

最后本文比较不同的负例选择方法对实验结果产生的影响.本文将本文提出的负例选择算法与随机负例选择法,只通过标签信息计算得到的标签策略,只通过活动信息计算得到的活动策略,以及只通过地理位置信息计算得到的地点策略进行比较.图5展示了在LA数据集上不同负例选择方法的效果,从图5中可以得知,本文的负例选择算法相较其他算法对最后结果有更大的提升.这也说明了在EBSN中,用户通常更喜欢更相似的群组,这个相似度可以通过不同方面来计算,诸如相似的标签或相似的地点.

图4 SEGELER 模型在冷启动用户上的 Precision

图5 不同负例选取策略的 Precision 值

4 结语

本文研究在社交网络中为用户预测对群组的偏好的问题,并利用了EBSN中的标签信息以及地理位置信息来提升预测的效果.本文提出了SEGELER(pairwiSE Geo-social Event-based LatEnt factoR)模型将这些相关信息进行使用来更好地分析用户偏好,并提出了基于贝叶斯个性化排序的目标函数来优化预测用户在社交网络中喜欢的群组对于社交网络中负例缺失的问题,本文提出了有效的算法来解决这一问题.通过EBSN数据集Meetup上的实验,验证了提出的算法在效果上的提升,同时可以缓解冷启动问题.在未来工作中,作者会继续分析并纳入更多社交网络中相关信息,诸如时间信息和情感信息,来提升预测的效果.同时除了预测准确度之外,其他的评价标准诸如预测区分度也将进行研究.

1 Sun YZ,Tang J,Han JW,et al.Co-evolution of multi-typed objects in dynamic star networks.IEEE Trans.on Knowledge and Data Engineering,2014,26(12):2942–2955.[doi:10.1109/TKDE.2013.103]

2 Dong YX,Zhang J,Tang J,et al.CoupledLP:Link prediction in coupled networks.Proc.of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Sydney,NSW,Australia.2015.199–208.

3 Zheng N,Li QD,Liao SC,et al.Flickr group recommendation based on tensor decomposition.Proc.of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval.Geneva,Switzerland.2010.737–738.

4 Rendle S,Gantner Z,Freudenthaler C,et al.Fast contextaware recommendations with factorization machines.Proc.of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval.Beijing,China.2011.635–644.

5 Pham TAN,Li XT,Cong G,et al.A general graph-based model for recommendation in event-based social networks.Proc.of 2015 IEEE the 31st International Conference on Data Engineering.Seoul,South Korea.2015.567–578.

6 Cheng C,Yang HQ,Lyu M R,et al.Where you like to go next:Successive point-of-interest recommendation.Proc.of the 23rd International Joint Conference on Artificial Intelligence.Beijing,China.2013.2605–2611

7 Ji XC,Qiao Z,Xu MZ,et al.Online event recommendation for event-based social networks.Proc.of the 24th International Conference on World Wide Web.Florence,Italy.2015.45–46.

8 Qiao Z,Zhang P,Cao YN,et al.Combining heterogenous social and geographical information for event recommendation.Proc.of the 28th AAAI Conference on Artificial Intelligence.Québec City,Québec,Canada.2014.145–151.

9 Zhang W,Wang JY.A collective bayesian poisson factorization model for cold-start local event recommendation.Proc.of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Sydney,NSW,Australia.2015.1455–1464.

10 Sellamanickam S,Garg P,Selvaraj SK.A pairwise ranking based approach to learning with positive and unlabeled examples.Proc.of the 20th ACM International Conference on Information and Knowledge Management.Glasgow,Scotland,UK.2011.663–672.

11 Cao Z,Qin T,Liu TY,et al.Learning to rank:From pairwise approach to listwise approach.Proc.of the 24th International Conference on Machine Learning.Corvalis,Oregon,USA.2007.129–136.

12 Rendle S,Freudenthaler C,Gantner Z,et al.BPR:Bayesian personalized ranking from implicit feedback.Proc.of the 25th Conference on Uncertainty in Artificial Intelligence.Montreal,Quebec,Canada.2012.452–461.

13 Crandall DJ,Backstrom L,Cosley D,et al.Inferring social ties from geographic coincidences.Proc.of the National Academy of Sciences of the United States of America,2010,107(52):22436–22441.[doi:10.1073/pnas.1006155107]

14 Kabbur S,Ning X,Karypis G.Fism:Factored item similarity models for top-n recommender systems.Proc.of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Chicago,Illinois,USA.2013.659–667.

15 Liu XJ,He Q,Tian YY,et al.Event-based social networks:Linking the online and offline social worlds.Proc.of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Beijing,China.2012.1032–1040.

Predicting User Preferences for Groups in Event-Based Social Networks

ZHU Cheng-Chun,ZHANG Mi
(School of Computer Science and Technology,Fudan University,Shanghai 200203,China)

In event-based social networks (EBSN),groups that aggregate users with similar interests for sharing events play important roles in community development.Understanding why people join a group and how groups are formed is particularly an interesting issue in social science.In this paper,we study predicting users’ preferences on social groups by considering content information in EBSN,i.e.,geographic-social event-based recommendation.Specifically,we consider two types of content information,i.e.,the tags and geographical event locations about users/events.We propose the SEGELER (pair-wiSE Geo-social Event-based LatEnt factoR)to model the users behavior considering the information.Experiments on a real-world EBSN social network validate the effectiveness of our proposed approach for both normal users and cold start users.

social network;recommender system;group recommendation;Bayesian personalized ranking;latent factor

朱成纯,张谧.基于活动的社交网络中的群组推荐算法设计.计算机系统应用,2017,26(9):103–108.http://www.c-s-a.org.cn/1003-3254/5940.html

2016-12-14;采用时间:2017-01-16