随着社交网络服务的兴起, 越来越多的人选择使用在线社交媒体系统分享信息.凭借着在内容生成方式、用户参与的广泛性与即时性、信息扩散模式与速度等方面的优势, 社交媒体用户量在近些年呈现出爆发式的增长, 每天都有海量的消息被用户发布.除了发布消息, 用户也会采用不同的交互行为与其他用户进行在线交互.以Twitter(https://twitter.com/)为例, 用户可以“回复”和“转发”消息; 为消息添加“标签”; 以“@用户名”的方式在消息中“提及”其他用户; 或者“关注”“订阅”感兴趣的人等等.这其中, 得益于在缓解信息过载方面的优势^{[1, 2]}, 社交媒体中的“提及”机制(mention mechanism)正在成为用户在线交互和网络信息传播的主要功能载体.对这一独特的用户在线交互行为的分析和研究能够揭示用户的隐式偏好与其显式交互行为之间的联系, 为信息传播监控^{[3, 4]}、商业智能^[5-8]、个性化推荐^[9]等应用提供新的数据支撑.

当前, 社交媒体系统的活跃用户规模日渐庞大.2016年末的统计显示(http://about.twitter.com/company/), Twitter的月活跃用户量已超过3亿且平均每位用户拥有208位直接社交朋友.因此, 当用户(即当前用户)需要在消息中提及其他用户(即目标用户)时, 庞大的候选目标群会使得当前用户很难在短时间内找到其需要的目标用户.此时, 为当前用户提供一个短小的、包含其最有可能提及的目标用户组成的列表, 可以有效地帮助用户识别目标、节省搜索时间.目前, 主流的社交媒体服务, 如Twitter、新浪微博(https://weibo.com/)和Facebook(https://facebook.com/)等, 会在用户输入提及符号“@”时, 根据用户的部分输入内容和提及历史为其生成一个候选目标用户列表.然而, 由于没有准确挖掘用户的提及行为偏好, 其建议内容往往不符合用户的实际期望.例如, 图 1展示了新浪微博的目标用户建议的一个例子.可以看到, 尽管输入内容中已明确指向了目标用户“2018年俄罗斯世界杯”, 但其用户名仍未出现在微博给出的top-10推荐列表中.

当前, 对用户提及行为数据的分析和使用吸引了来自人工智能及数据挖掘等不同领域研究者的广泛关注^{[2-4, 8]}.然而, 大多数当前研究仅聚焦于提及机制的信息传播属性, 如寻找能够将消息更快散播的目标用户.事实上, 社交媒体中的提及功能既是一个网络信息传播渠道, 也是一个普通用户交互工具.直观上看, 相对于少数的媒体工作者和广告商, 提及功能的用户交互属性对占大多数的普通用户来说更为重要.从普通用户角度来看, 提及功能更广义的作用应是通知目标用户“查看”而不是“传播”某条消息^[9].此外, 已有研究表明, 社交媒体中信息传播更多地依赖于用户的转发而非提及行为, 寻找合适的转发者可以更加有效地提高消息在社交媒体中的扩散速度和深度^[10-13].因此在本文中, 我们通过对影响普通用户提及行为的因素进行分析以挖掘隐藏的用户行为偏好, 并基于学习到的知识模型构建一个推荐系统, 帮助当前用户搜索和识别目标用户.

尽管文本内容信息对于目标用户推荐的重要性已得到许多研究的证明^{[3, 4, 8, 9]}, 但尚未有工作调查其他影响用户目标选择的上下文因素.近年来, 得益于可定位移动设备的普及, 地理维度的信息正在社交媒体中迅速扩散, 这为我们更好地理解用户的在线行为与其物理活动之间的关系提供了宝贵的资源.换句话说, 用户物理维度的信息可以帮助我们更准确地捕捉用户的在线行为偏好^{[5, 7]}.因此在本文中, 我们探索用户提及活动的空间上下文信息对其目标用户选择的影响.通过对两个大型真实社交媒体数据集的分析(第2.1节)我们发现, 被同一用户提及的目标用户呈现出地理聚集的趋势.这揭示了当前用户和目标用户之间的空间关联, 激发了对空间上下文感知的用户提及行为建模和目标用户推荐的研究需求.

在本文中, 我们从普通用户的角度研究社交媒体中的目标用户推荐问题.即, 当用户需要在一条消息中提及其他用户时, 本文研究如何找到最有可能被其提及的目标用户并生成推荐.具体而言, 本文通过分析用户空间上下文感知的在线提及行为来研究该问题.我们提出一个联合概率生成模型JUMBM(joint user mention behavior model), 通过综合考虑语义和空间因素来模拟用户提及活动的生成(如图 3所示).由于用户的提及行为受其语义和空间上下文因素的联合影响, JUMBM引入了两个关键的潜在主题变量——语义主题和地理区域, 分别负责生成用户活动的语义属性(如文本词语)和地理属性(如地理坐标).此外, 不同于当前研究假设用户语义兴趣是固定不变的, JUMBM利用目标用户的地理聚集区域来发掘当前用户空间依赖的语义兴趣.通过这种方式, JUMBM能够统一地进行语义和空间感知的用户提及行为建模, 从而发掘用户的移动模式、地理区域依赖的语义兴趣及其目标用户的地理聚集模式.此外, 为了应对推荐中遇到的“维数灾难”问题并加快系统对在线查询的响应速度, 本文提出一种混合剪枝算法对项目和属性空间进行综合剪枝, 实现了高维大候选空间内的快速精确项目检索.

本文的主要贡献如下.

(1) 从普通用户角度对用户的提及行为进行了学习, 并提出了一个概率生成模型来发掘语义和空间上下文因素对用户提及行为的联合影响.据我们所知, 本文是第一个从普通用户角度进行空间感知的用户提及行为建模的工作.

(2) 设计了一种高效的混合剪枝算法, 通过对项目和属性空间进行同时剪枝, 实现了对在线查询的快速响应.

(3) 在两个大型真实社交媒体数据集上构建了一系列的实验.实验结果证明了在解决提及目标推荐问题时考虑用户空间上下文因素的必要性.同时, 本文提出的方法在推荐有效性和效率方面均优于其他目标用户推荐方法.

本文第1节对相关工作的研究现状进行总结.第2节首先对本文使用的符号和研究问题做出形式化定义, 然后对模型背后的研究动机进行描述, 最后详细阐述JUMBM的模型结构和模型推理过程.第3节介绍如何基于学习到的知识进行高效率的目标用户推荐.本文在真实数据集上进行实验, 在第4节中对提出的方法进行评估.最后, 在第5节中对本文工作做出总结.

1 相关工作

本文的研究内容主要涉及到3个主题:(1)社交网络用户交互行为分析; (2)空间上下文感知的主题模型; (3)社交媒体目标用户推荐.本文将分别总结相关工作的研究现状, 并对其与本文方法的区别进行阐述.

1.1 社交网络用户交互行为分析

对用户在线交互模式的分析能够揭示用户的隐藏意图和真实行为之间的相关性.这种高层次的信息可以用于诸如内容传播分析、信息监控以及个性化推荐等等一系列应用.近年来, 越来越多的研究者开始关注社交网络用户的在线交互行为.例如, Xu等人的研究^[14]关注于用户的在线消息“发布(posting)”行为.他们发现用户的“发布”行为主要受到网络突发消息、个人社交邻居的历史记录和用户本身兴趣的影响.Qiu等人^[15]调查了用户与其生成文本间的交互行为, 并提出一个概率模型发掘用户的主题兴趣和交互模式.Yin等人^[16]则关注社交媒体用户对项目的评分行为, 其研究发现, 用户的评分行为受到个人兴趣和公众集体倾向的共同影响.由于社交媒体上的用户“转发”行为往往指示了网络信息的流向, 近年来对用户“转发”行为的研究也在不断涌现^{[10, 17-24]}.如Chen等人^[10]通过分析Twitter用户的转发模式构建了一个个性化的Tweet推荐系统.Bi等人的研究^[17]则聚焦于社交媒体中信息转发网络, 他们发现, 考虑用户间的转发关系能够使得基于文本的模型更准确地推理用户个人兴趣.除此之外, 当前研究也关注于其他类型的用户交互行为, 如“标签”^[21-23]和“提及”^{[2, 4, 8, 24]}.与这些研究相比, 本文基于不同的研究目标, 构建社交媒体用户的提及行为模型, 通过挖掘用户的行为偏好为目标用户推荐提供知识模型.

1.2 空间上下文感知的主题模型

在过去的几十年里, 主题模型(topic model)在文本挖掘、信息检索及自然语言处理领域得到了广泛的应用.主题模型不但可以发掘文本集合中隐藏的语义结构, 还能有效地分析多种类型的离散数据.当前, 主题模型已发展出了很多变体, 如概率潜在语义分析(PLSA)、潜在狄利克雷分配(LDA)、层次狄利克雷过程(HDP)等等.当前, 一些研究开始通过分析用户、位置和主题之间的关系来挖掘社交媒体中的地理知识^{[5, 12, 25-37]}.例如, Kurashima等人^[31]将主题模型和Markov模型进行了结合, 根据用户上传照片的位置标签来推理一个摄影师访问该位置的概率.Hu等人^[5]则综合考虑了社交媒体消息的空间和文本内容, 提出ST模型对用户移动模式、用户兴趣和地理位置的语义功能间的联系进行推理.Yin等人^[25]提出了一个位置-内容感知的概率主题模型, 在空间项目推荐过程中对本地偏好和项目语义模式进行了量化.由Wang等人^[29]提出的Geo-SAGE模型根据地理项目的内容和共现模式, 将用户在特定区域内的个人兴趣和公众在区域的本地偏好进行了综合, 提高了地理项目推荐精确度. Fang等人^[30]在其提出的时空上下文感知的推荐框架STCAPLRS中, 对用户个人兴趣、本地偏好及时空上下文等因素进行了集成, 为特定地理区域内的用户提供位置推荐.与上述工作相比, 本文的主要工作是通过综合考虑用户提及交互行为活动的语义和上下文信息构建一个概率主题模型, 对用户的提及行为偏好进行推理.

1.3 社交媒体目标用户推荐

当前, 目标用户推荐正在成为社交媒体用户个性化推荐领域的一个研究热点.举例来说, Wang等人^[4]将这个任务视为一个学习-排序问题, 通过抽取用户兴趣、内容依赖的用户关系以及用户影响力等特征来训练一个学习排序方法.他们的主要研究目的是通过寻找合适的目标用户来加快一条Tweet在Twitter中的传播.Zhou等人^[2]则从信息过载的角度研究了目标用户的排序问题.通过探索文本内容特征和用户个人吸引力、社区权威和对话内容等因素来构建一个排序模型来寻找合适的目标用户以减缓社交媒体信息过载问题.由Tang等人^[8]开发的CAR推理框架在提取内容、社交、位置和时间这4种类型特征的基础上, 采用支持向量机(SVM)模型来实现目标推荐.该工作关注的问题是如何在用户发表促销相关的消息时为其推荐合适的目标受众, 从而为社交媒体中的市场工作者寻找具有高回应率的用户群.与之不同, 本文从普通用户的在线交互角度, 研究如何找到当前用户最有可能提及的目标用户.此外, CAR使用了学习-排序方法来形式化并解决问题.而本文则基于概率生成方法来挖掘用户提及偏好并为目标推荐提供知识模型.最近, Gong等人^[9]提出了一个同时考虑了当前内容及目标用户的内容历史的主题翻译模型A-UUTTM以对用户行为偏好进行推理.该方法能够有效地识别目标用户名, 是目前用于目标用户推荐效果最好的方法.但是, A-UUTTM仅考虑了文本内容驱动的用户语义模式, 忽略了空间因素对用户提及行为的影响.与之相比, 本文提出的JUMBM模型则对用户地理区域依赖的语义兴趣、移动模式及目标用户的地理聚集模式进行了统一的建模和推理.第4.4.1节的实验结果则表明了在解决提及目标推荐问题时考虑用户空间上下文因素的必要性和JUMBM模型在挖掘用户提及偏好方面的有效性.

本文提出的方法与已有工作的区别总结如下.首先, 本文旨在从普通用户的角度探索目标用户推荐问题, 即寻找最有可能被当前用户通知“查看”当前消息的目标用户.也就是说, 本文关注的社交媒体提及机制不再局限于其对某条消息传播速度的影响, 而是其广义上的用户交互属性.其次, 本文不仅基于消息内容, 同时结合用户提及活动的空间上下文信息对用户的提及行为进行空间感知的联合建模.实验结果(第5.3.1节)表明, 增加对用户提及活动空间上下文信息的考虑能够显著提升推荐系统的性能.第三, 本文尝试提供一个可部署的快速目标用户推荐系统, 能够快速响应在线查询.为解决该推荐效率问题, 本文设计了一种混合剪枝算法对在线检索空间进行剪枝.实验结果(第5.3.3节)表明了该剪枝算法的有效性.

2 空间上下文感知用户提及行为建模

本节首先对本文使用的符号和研究问题给出形式化定义, 然后对本文对用户提及行为建模过程背后的研究动机进行描述, 最后详细介绍本文提出的JUMBM模型结构、生成过程和参数推理过程.

2.1 问题定义

表 1列举了用于JUMBM模型输入数据的符号.本文使用的数据结构定义如下.

定义1(当前用户和目标用户).如果用户u在至少一条消息中提及了用户m, 则u被称为当前用户, m则称为目标用户.显然, 本文中的“当前用户”和“目标用户”是两个相对的概念.一个用户既可以是一个提及实例的当前用户, 也可以是另一个提及实例的目标用户.本文中, 目标用户拥有两个属性:标识符m及其居住位置l_m.

注意, 社交媒体用户可以选择是否在其“个人资料”中公开其居住位置.对于那些提供了准确居住地点描述(例如GPS坐标或详细的位置描述)的用户, 该位置将直接用作他们的居住位置.而对于那些没有明确给定居住地点或者对其居住位置描述过于粗糙的用户, 我们采用一种当前广泛使用的ground-truth用户位置获取方法, 为每个目标用户分配一个位置点(GPS坐标)作为其居住位置(参见第4.1节).

定义2(位置标记的用户提及活动).本文使用一个五元组(u, W_d, l_d, M_d)表示一条位置标记的用户提及活动d即, 当前用户u在发表于地点l_d的由词语W_d组成的消息中提及了目标用户M_d.注意, 由于用户可以在一条消息中采取多次提及行为, 此处的M_d表示一个目标用户集合而非单个的目标用户.此外, 我们使用${L_{{M_d}}}$表示M_d中用户的居住位置集合.

定义3(用户活动文档).对于当前用户u, 其活动文档D_u是u的位置标记提及活动的集合.数据集D则由所有用户的提及活动文档组成, 即$D = \left\{ {{D_u}} \right\}_{u = 1}^U.$L_D表示所有提及活动文档的发生位置集合, 即${L_D} = \left\{ {{l_d}} \right\}_{d = 1}^D.$L_M则表示所有目标用户的居住位置集合, 即${L_M} = \left\{ {{L_{{M_d}}}} \right\}_{d = 1}^D.$

本文的研究问题可定义如下.

问题(目标用户推荐).给定一个用户活动文档集D和一条由用户u_q在位置l_q处发表的由词语W_d组成的查询q, 即q={u_q, l_q, W_q}, 本文为u_q推荐其最有可能提及的top-k个目标用户组成的列表, 见表 1.

2.2 JUMBM建模动机

(1) 目标用户地理分布.为了学习空间上下文信息对用户提及行为的影响, 我们对采集自新浪微博的由14万位用户发布的59万条消息, 以及采集自Twitter的由13万位用户发布的超过55万条消息组成的大型数据集进行了统计分析.数据集中的每一条消息都附加了一个位置标签且含有至少一个提及实例.同时, 每一位目标用户均被分配了一个地理坐标(经度/维度)作为其居住位置.统计发现, 被同一当前用户提及的目标用户呈现出地理聚集的趋势.具体来说, 在Ye等人的启发下^[38], 我们首先计算了所有被同一用户提及的目标用户两两之间的地理间距, 然后计算出每个目标用户对在特定地理间距上被提及的概率并绘制概率-间距直方图, 如图 2所示.我们发现, 目标用户对被提及概率呈现出幂律分布的趋势, 且大部分目标用户对之间的地理间距都较短.该现象可以用以下理论倾向进行解释.首先, 计算社会科学方向的研究^[39]已经证实, 在线社交关系往往形成于地理间距较短的节点间.McGee等人的调查^{[40, 41]}也表明, 用户与其大多数社交媒体朋友间的物理距离都较短.这些研究显示, 用户主要与相近物理距离内的其他用户线上交互, 且物理间距较短的用户之间的在线交互更加地频繁.这一结论与已有工作的研究结果是一致的^{[42, 43]}.其次, 地理范围聚焦的在线社区的演化加速了物理临近用户的在线聚集^{[39, 44, 45]}.同属一个地理范围聚焦的在线社区中的用户针对同一地理范围内有着相似的兴趣.因此, 用户有可能对新的地理聚焦的社区产生兴趣, 即使该社区关注的地理范围与用户所在位置距离较远.总的来说, 这一地理现象揭示了当前用户和目标用户间的空间关联, 激发了对空间上下文感知的社交媒体用户提及行为建模的研究需求.

(2) 用户位置感知的语义兴趣.前期工作已证实, 文本内容表征的用户的语义兴趣是其选择提及目标的一个主要依据^{[2, 8, 9]}.因此, 用户的历史消息文本对目标用户推荐来说至关重要.当前, 对用户交互行为的研究多假设用户的语义兴趣是固定不变的^{[2, 8, 10, 11]}.然而, 关于社交媒体用户移动模式的研究发现, 用户在不同的位置有不同的语义偏好^[46-49].也就是说, 用户所在的地理区域不同, 其发布消息的语义兴趣也不同.举例来说, 某用户在其居住城市发布的历史消息显示其语义兴趣偏向于“生活”或者“健身”, 而当其到达一个新的城市时, 其语义兴趣可能更偏向于“旅游”或者“美食”.自然地, 用户语义兴趣的转变也会引起其在线交互行为模式的变化.因此, 相对于基于历史内容的用户语义兴趣推理, 发掘当前用户在其目标用户地理聚集区域内的语义兴趣, 对目标用户推荐来说更加重要.

2.3 模型结构

为了研究内容和空间上下文信息对用户提及行为的联合影响, 本文提出了一个联合概率模型JUMBM, 通过综合考虑语义和空间因素模拟用户提及活动的生成过程.图 3给出了JUMBM的图模型表示.其中, 模型的观察变量, 如词语w使用阴影圆圈表示, 隐藏变量, 如主题z则使用无阴影圆圈表示.此外, N、V、K、R分别表示当前用户、词语、主题和区域的数量, |D_u|、|M_d|、|W_d|则分别表示u的提及活动文档数量、d包含的目标用户数量以及d包含的词语数量.表 2介绍了模型使用的参数符号及其含义.

由于用户的提及行为受到语义和空间上下文因素的联合影响, JUMBMs引入了两个潜在变量——语义主题和地理区域, 分别负责生成用户提及活动的语义属性(如文本词语)和地理属性(如地理坐标).基于这两个潜在变量, JUMBM以一种统一的方式对用户地理区域依赖的语义兴趣、移动模式以及目标用户的地理聚集模式进行建模.接下来, 我们将分别从这3个方面对JUMBM的模型结构进行阐述.

首先, 基于研究动机1, “目标用户地理聚集”现象表明被同一当前用户提及的目标用户呈现出地理聚集的趋势.该现象揭示了在线交互的用户之间的空间相关性.因此, 在用户提及行为模型中融合对目标用户的地理聚集区域的建模是十分必要的.在本文中, 我们首先将所有目标用户的居住位置划分进R个地理区域.此外, JUMBM基于连续的地理位置点将一个区域g建模为一个地理高斯分布, 从而避免了采用多项式分布引起的位置点分布过于稀疏的现象.也就是说, JUMBM将目标用户m的居住地点l_m形式化为${l_m}\sim \mathcal{N}({\mu _g}, {\Sigma _g}), $其中, μ_g和Σ_g分别表示区域g的均值向量和协方差矩阵.即:

$P\left( {{l_m}|{\mu _g}, {\Sigma _g}} \right) = \frac{1}{{2{\rm{ \mathsf{ π} }}\det \left( {{\Sigma _g}} \right)}}\exp \left( { - \frac{1}{2}{{\left( {{l_m} - {\mu _g}} \right)}^T}\sum\nolimits_g^{ - 1} {\left( {{l_m} - {\mu _g}} \right)} } \right)$

(1)

此外, 我们使用一个地理区域上的多项式分布表示${\phi _u}$对u所对应的目标用户地理聚集区域分布.

其次, 研究表明, 用户的语义兴趣对其目标用户选择来说至关重要^{[2, 8, 10, 11]}.受当前关于用户兴趣建模研究的启发^{[18, 50, 51]}, 本文采用潜在的主题变量来表征用户的语义兴趣.传统的主题模型为文档中的每一个词语分配一个主题, 不能有效处理长度较短且高噪声的社交媒体文本数据^{[9, 13, 21]}.因此对于一条提及活动d, JUMBM假设W_d中的所有词语具有相同的主题z.此外, 根据研究动机2, JUMBM基于潜在的主题和区域来揭示用户空间依赖的语义兴趣.即, JUMBM根据D_u的内容信息和u对应的目标用户的地理分布来推理u在特定区域g内对一组主题的兴趣分布θ_{u, g}.通过这种方式, 我们将主题建模和地理聚集过程进行了统一.此外, 在JUMBM建模过程中, 如何提高主题的质量对于准确推理用户的语义兴趣来说至关重要.与传统的基于LDA模型的方法相比, 主题翻译模型^{[9, 21, 52]}结合了主题模型和翻译模型的优点, 能够在从短文本和非标准文本数据中发掘隐藏的语义模式的同时, 有效地应对社交媒体提及消息中存在的词典缺口问题.我们在建模过程中遵循基本的文本翻译建模机制, 即将目标用户的生成过程看作是从内容到目标用户名的翻译过程.因此, JUMBM中的主题z将同时负责生成词语W_d和其关联的目标用户M_d.换句话说, JUMBM中的每个主题z不仅与一个词语分布${\vartheta _z}$相关联, 还与一个目标用户分布ψ_{z, w}相关联.此外, JUMBM引入一个联合潜在因素(主题-区域), 按照主题翻译过程生成目标用户名.因此, JUMBM将每一个主题-词语(z, w)与一个目标用户上的分布ψ_{z, w}相关联.

第三, 在以新浪微博、Twitter和Facebook为代表的社交媒体服务中, 用户可以选择在发表的消息中添加位置或者兴趣点(point of interest, 简称POI)标签来实现签到(check-in)功能.关于社交媒体用户空间移动模式的研究^{[13, 26]}表明, 用户的签到活动呈现出较强的语义规则性.而在本文研究的问题中, 用户位置标记的提及行为可以视为其签到行为在用户在线交互方面的扩展.也就是说, 用户位置标记的提及活动中隐藏着与其签到活动类似的用户移动模式.在本文中, 我们基于潜在主题来挖掘该用户移动模式.具体来说, 主题$z$将负责用户提及活动的位置标签的生成, 且每一个主题都与一个标签位置(即当前用户的当前位置)上的分布π_z相关联.基于该设计, 我们对当前用户语义模式和移动模式的建模过程进行了结合, 也使得主题和位置挖掘过程在一个统一的框架下相互影响和提高.

2.4 生成过程

JUMBM假设用户u发出的提及活动d的生成过程如下.首先, u根据其目标用户的地理分布${\phi _u}$选择一个区域g.然后, u根据其主题偏好θ_{u, g}选择一个区域g上的主题z.给定主题后, 组成文本内容的一系列词语W_d由主题-词语分布${\vartheta _z}$或备用词语分布${\vartheta _b}$生成.在主题和词语生成结束后, 根据主题z、词语W_d及概率分布$P(.\left| {z, W, {\psi _{z, w}}} \right.)$选择目标用户M_d.同时, 每个目标用户m(m∈M_d)的居住位置l_m(${l_m} \in {L_{{M_d}}}$)则根据区域g上的地理分布$\mathcal{N}({\mu _g}, {\Sigma _g})$生成.最后, 根据标签位置上的多项式分布${\pi _{z, a}}$生成d的位置l_d.模型的生成过程如算法1所示.

算法1. JUMBM生成过程.

1.提取ρ~Beta(λ₁, λ), ${\vartheta _b}\sim Drichlet(\beta); $

2. for each u∈do

3.   抽样u对区域的分布 $\phi_{u} \sim {Dirchlet}(. | \eta) $;

4.    for each g∈G do

5.     抽样u在区域g上对主题的分布$\theta_{u, g} \sim {Dirchlet}(\cdot | \alpha)$;

6. end for

7. end for

8. for each z∈T do

9.   抽样一个词语上的分布$\vartheta_{z} \sim {Dirichelt}(\cdot | \beta)$;

10.     for each w∈W do

11.       抽样一个主题和词语上的分布${{\psi }_{z, w}}\tilde{\ }Dirichlet(.|\gamma)$;

12.     end for

13. end for

14. for each D_u∈D do

15.     for each d∈D_u do

16.      抽样一个目标用户聚集区域$g \sim {Multi}\left(\cdot | \phi_{u}\right); $

17.      抽样一个主题$z_{d} \sim {Multi}\left(\cdot | \theta_{u, g}\right)$;

18.       for each w∈W_d do

19.         抽样一个开关变量${{y}_{w}}\tilde{\ }Bernoulli(\rho)$;

20.         if y_w=0 then

21.           抽样一个词语$w\tilde{\ }Multi(.\left| {{\vartheta }_{z}} \right.); $

22.         else

23.           抽样一个词语$w\tilde{\ }Multi(.\left| {{\vartheta }_{b}} \right.); $

24.         end if

25.       end for

26.         for each m∈M_d do

27.           抽样一个目标用户$m\tilde{\ }P(.\left| {{z}_{d}}, {{W}_{d}}, {{\psi }_{z, w}} \right.); $

28.           抽样m的居住位置${{l}_{m}}\tilde{\ }\mathcal{N}({{\mu }_{g}}, {{\Sigma }_{g}}); $

29.         end for

30.         抽样u的当前位置${{l}_{d}}\tilde{\ }Multi(.\left| {{\pi }_{z}} \right.); $

31.     end for

32. end for

3.5 模型推理

通常来说, 对潜变量概率模型进行模型参数推理需要计算使得观察变量的边缘概率最大的参数集, 而该边缘分布的计算是与模型中的隐藏变量相关的.但是, 由于隐藏变量间的耦合, 精确地计算该边缘分布通常是不可实现的.因此, 本文采用基于收缩吉布斯抽样^[53]的近似学习方法来最大化公式(2)中的联合概率分布.本文假设JUMBM中除β外的所有先验变量均服从对称Dirichlet分布, 而β则服从Beta分布.也就是说, 模型中的先验变量均为多项式分布或Bernoulli分布的共轭先验.通过这种方式, 我们可以在对参数θ、$\phi $、π、ψ、μ、Σ、$\vartheta $和${\vartheta _b}$进行推理的同时挖掘它们之间的不确定性关联.受前期研究的启发^{[12, 53]}, 我们将模型中的超参数设置成固定值以节省计算成本, 即α=50/K、η=50/R、β=γ=ξ=0.01、λ₁=λ₂=0.5.根据算法1中的描述, JUMBM的观察和隐藏变量的联合概率分布可分解为

$\begin{array}{l} \mathit{\boldsymbol{P}}\left( {\mathit{\boldsymbol{z}}, \mathit{\boldsymbol{g}}, {\mathit{\boldsymbol{W}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}, \mathit{\boldsymbol{y}}, {\mathit{\boldsymbol{l}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{L}}_{{\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}}}|\alpha , \lambda , \beta , \gamma , \eta , \xi , \mathit{\boldsymbol{\mu }}, \mathit{\boldsymbol{ \boldsymbol{\varSigma} }}} \right)\\ = \mathit{\boldsymbol{P}}(\mathit{\boldsymbol{g}}|\eta )\mathit{\boldsymbol{P}}(\mathit{\boldsymbol{z}}|\mathit{\boldsymbol{g}}, \alpha )\mathit{\boldsymbol{P}}(\mathit{\boldsymbol{y}}|\lambda )\mathit{\boldsymbol{P}}({\mathit{\boldsymbol{W}}_\mathit{\boldsymbol{d}}}|\mathit{\boldsymbol{z}}, \mathit{\boldsymbol{y}}, \beta )\mathit{\boldsymbol{P}}({\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}|\mathit{\boldsymbol{z}}, \mathit{\boldsymbol{W}}, \mathit{\boldsymbol{y}}, \gamma )\mathit{\boldsymbol{P}}({\mathit{\boldsymbol{L}}_{{\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}}}|\mathit{\boldsymbol{g}}, \mathit{\boldsymbol{\mu }}, \mathit{\boldsymbol{ \boldsymbol{\varSigma} }})\mathit{\boldsymbol{P}}({\mathit{\boldsymbol{l}}_\mathit{\boldsymbol{d}}}|\mathit{\boldsymbol{z}}, \xi ) \end{array}$

(2)

使用吉布斯抽样方法进行参数推理需要抽样每一条提及活动中潜在变量z、g和y的后验概率分布.因此, 我们首先根据条件概率$P({g_{(u, d)}} = x|{\mathit{\boldsymbol{g}}_{\neg (\mathit{\boldsymbol{u}}, \mathit{\boldsymbol{d}})}}, \mathit{\boldsymbol{z}}, {\mathit{\boldsymbol{W}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}, \mathit{\boldsymbol{y}}, {\mathit{\boldsymbol{l}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{L}}_{{\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}}}, \mathit{\boldsymbol{u}} \cdot)$对区域g进行抽样.其中, (u, d)表示用户u的提及活动d.受篇幅所限, 下文省略了具体的推理过程.根据贝叶斯规则, 潜在变量g的抽样概率可以计算为

$\begin{gathered} P({g_{(u, d)}} = x|{\mathit{\boldsymbol{g}}_{\neg (\mathit{\boldsymbol{u}}, \mathit{\boldsymbol{d}})}}, \mathit{\boldsymbol{z}}, {\mathit{\boldsymbol{W}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}, \mathit{\boldsymbol{y}}, {\mathit{\boldsymbol{l}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{L}}_{{\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}}}, \mathit{\boldsymbol{u}} \cdot ) \\ \propto \frac{{n_{\neg (u, d)}^{u, x} + \eta }}{{\sum\nolimits_{g' \in G} {\left( {n_{\neg (u, d)}^{u, g'} + \eta } \right)} }}\frac{{n_{\neg (u, d)}^{u, x, z} + \alpha }}{{\sum\nolimits_{z' \in T} {\left( {n_{\neg (u, d)}^{u, x, z'} + \alpha } \right)} }}\prod\nolimits_{m \in {M_d}} {P\left( {{l_m}|{\mu _g}, {\Sigma _g}} \right)} \\ \end{gathered} $

(3)

其中, n^{u, x}是用户u生成的目标用户聚集区域为x的数目, n^{u, x, z}表示给定区域x之后主题z是根据用户u在区域x上的多项式分布生成的次数, $\neg (u, d)$表示所有的计数均未计入当前实例.此外, μ_g表示区域g的均值向量, Σ_g表示区域g的协方差矩阵, 可根据如下公式抽样:

${\mu _g} = E(g) = \frac{1}{{\left| {{C_g}} \right|}}\sum\nolimits_{m \in {C_g}} {{l_m}} $

(4)

${\Sigma _g} = D(g) = \frac{1}{{\left| {{C_g}} \right| - 1}}\sum\nolimits_{m \in {C_g}} {\left( {{l_m} - {\mu _g}} \right){{\left( {{l_m} - {\mu _g}} \right)}^T}} $

(5)

其中, C_g表示被分配到区域g的目标用户集合.

在抽样区域g之后, 我们可根据如下公式为同一条提及活动抽样出区域g依赖的主题分配:

$\begin{gathered} P\left( {{z_{(u, d)}} = k|{\mathit{\boldsymbol{z}}_{\neg (\mathit{\boldsymbol{u}}, \mathit{\boldsymbol{d}})}}, \mathit{\boldsymbol{g}}, {\mathit{\boldsymbol{W}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}, \mathit{\boldsymbol{y}}, {\mathit{\boldsymbol{l}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{L}}_{{\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}}}, \mathit{\boldsymbol{u}} \cdot } \right) \\ \propto \frac{{n_{\neg (u, d)}^{u, g, k} + \alpha }}{{\sum\nolimits_{z' \in T} {\left( {n_{\neg (u, d)}^{u, g, z'} + \alpha } \right)} }}\frac{{n_{\neg (u, d)}^{k, {l_d}} + \xi }}{{\sum\nolimits_{l' \in {L_D}} {\left( {n_{\neg (u, d)}^{k, l'} + \xi } \right)} }}\prod\nolimits_{w \in {W_d}} {\frac{{n_{\neg (u, d)}^{k, w} + \beta }}{{\sum\nolimits_{w' \in W} {\left( {n_{\neg (u, d)}^{k, w'} + \beta } \right)} }}} \\ \;\;\;{\kern 1pt} \times \prod\nolimits_{m \in {M_d}} {\sum\nolimits_{w \in {W_d}} {\frac{{n_{\neg (u, d)}^{m, k, w} + \gamma }}{{\sum\nolimits_{m' \in M} {\left( {n_{\neg (u, d)}^{m', k, w} + \gamma } \right)} }}} } \\ \end{gathered} $

(6)

其中, g为已抽样的区域, n^{u, g, k}则表示用户u的提及活动中区域为g且主题为k的数目, ${n^{k, {l_d}}}$为位置l_d在给定主题k后根据位置多项式分布抽样生成的次数, n^{k, w}是词语w由主题为k的主题-词语分布抽样生成的次数, $\neg (u, d)$表示所有的计数均未计入当前实例.

此外, 潜在开关变量y可根据如下后验概率抽样:

$\begin{gathered} P\left( {{y_{(u, d, w)}} = 0|{\mathit{\boldsymbol{y}}_{\neg (\mathit{\boldsymbol{u}}, \mathit{\boldsymbol{d}}, \mathit{\boldsymbol{w}})}}, \mathit{\boldsymbol{z}}, \mathit{\boldsymbol{g}}, {\mathit{\boldsymbol{W}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{l}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{L}}_{{\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}}}, \mathit{\boldsymbol{u}} \cdot } \right) \\ \propto \frac{{n_{\neg (u, d, w)}^{y = 0} + \lambda }}{{\sum\nolimits_{y' \in \left[ {0, 1} \right]} {\left( {n_{\neg (u, d, w)}^{y = y'} + \lambda } \right)} }}\frac{{n_{\neg (u, d, w)}^{z, w, y = 0} + \beta }}{{\sum\nolimits_{w' \in W} {\left( {n_{\neg (u, d, w)}^{z, w', y = 0} + \beta } \right)} }} \\ \end{gathered} $

(7)

$\begin{gathered} P\left( {{y_{(u, d, w)}} = 1|{\mathit{\boldsymbol{y}}_{\neg (\mathit{\boldsymbol{u}}, \mathit{\boldsymbol{d}}, \mathit{\boldsymbol{w}})}}, \mathit{\boldsymbol{z}}, \mathit{\boldsymbol{g}}, {\mathit{\boldsymbol{W}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{l}}_\mathit{\boldsymbol{d}}}, {\mathit{\boldsymbol{L}}_{{\mathit{\boldsymbol{M}}_\mathit{\boldsymbol{d}}}}}, \mathit{\boldsymbol{u}} \cdot } \right) \\ \propto \frac{{n_{\neg (u, d, w)}^{y = 1} + \lambda }}{{\sum\nolimits_{y' \in \left[ {0, 1} \right]} {\left( {n_{\neg (u, d, w)}^{y = y'} + \lambda } \right)} }}\frac{{n_{\neg (u, d, w)}^{b, w, y = 1} + \beta }}{{\sum\nolimits_{w' \in W} {\left( {n_{\neg (u, d, w)}^{b, w', y = 1} + \beta } \right)} }} \\ \end{gathered} $

(8)

其中, n^y=0表示词语由主题-词语分布生成的次数, n^y=1表示词语由备用词语分布生成的次数, n^{z, w, y=0}表示词语w被分配为主题词语的次数, n^{b, w, y=1}则表示w被分配为备用词语的次数, ${n_{\neg (u, d, w)}}$意味着所有计数均未计入文档(u, d)的当前词语w.

经过足够次数的迭代后, 即可通过统计z和g分配给提及活动的次数得到的近似后验概率来估计模型的参数.同时, 我们可根据收缩吉布斯抽样方法得到如下对JUMBM参数的估计:

${\theta ^{u, g, z}} = \frac{{{n^{u, g, z}} + \alpha }}{{\sum\nolimits_{z' \in T} {\left( {{n^{u, g, z'}} + \alpha } \right)} }}$

(9)

${\phi ^{u, g}} = \frac{{{n^{u, g}} + \eta }}{{\sum\nolimits_{g' \in G} {\left( {{n^{u, g'}} + \eta } \right)} }}$

(10)

${\vartheta ^{z, w}} = \frac{{{n^{z, w}} + \beta }}{{\sum\nolimits_{w' \in W} {\left( {{n^{z, w'}} + \beta } \right)} }}$

(11)

${\psi ^{z, w, m}} = \frac{{{n^{z, w, m}} + \gamma }}{{\sum\nolimits_{m' \in M} {\left( {{n^{z, w, m'}} + \gamma } \right)} }}$

(12)

${\pi ^{z, {l_d}}} = \frac{{{n^{z, {l_d}}} + \xi }}{{\sum\nolimits_{l' \in {L_D}} {\left( {{n^{z, l'}} + \xi } \right)} }}$

(13)

3 目标用户推荐

在本节中, 我们介绍如何将学习到的JUMBM模型(即参数集$\hat \Phi = \left\{ {\hat \theta, \hat \vartheta, \hat \psi, \hat \phi, \hat \pi, \hat \mu, \hat \Sigma } \right\}$)应用到目标推荐任务中.根据JUMBM的建模过程, 给定一个查询q=(u_q, l_q, W_q), u_q提及目标用户$m$的概率$P\left({m|{u_q}, {l_q}, {W_q}, \hat \Phi } \right)$可计算为

$P\left( {m|{u_q}, {l_q}, {W_q}, \hat \Phi } \right) = \frac{{P\left( {m, {l_q}|{u_q}, {W_q}, \hat \Phi } \right)}}{{\sum\nolimits_{m' \in M} {P\left( {m', {l_q}|{u_q}, {W_q}, \hat \Phi } \right)} }} \propto P\left( {m, {l_q}|{u_q}, {W_q}, \hat \Phi } \right)$

(14)

其中, 概率$P\left({m, {l_q}|{u_q}, {W_q}, \hat \Phi } \right)$可进一步分解为

$P\left( {m, {l_q}|{u_q}, {W_q}, \hat \Phi } \right) = \sum\nolimits_{g \in G} [ P\left( g \right)P\left( {{l_m}|g, \hat \Phi } \right)P\left( {m, {l_q}|g, {u_q}, {W_q}, \hat \Phi } \right)]$

(15)

其中, 区域g的先验概率P(g)可计算为

$P\left( g \right) = \sum\nolimits_{u \in U} {P\left( {g|u} \right)P\left( u \right)} = \sum\nolimits_{u \in U} {P\left( u \right){{\hat \phi }_{u, g}}} $

(16)

$P\left( u \right) = \frac{{\left| {{D_u}} \right| + \varepsilon }}{{\sum\nolimits_{u' \in U} {\left( {\left| {{D_{u'}}} \right| + \varepsilon } \right)} }}$

(17)

其中, P(u)为u的先验概率; $\left| {{D_u}} \right|$表示u的提及活动数量.同时, 我们在计算P(u)时使用一个Dirichlet先验参数作为平滑参数, 从而避免了过拟合现象的产生^{[12, 13]}.接下来, 概率$P\left({m, {l_q}|g, {u_q}, {W_q}, \hat \Phi } \right)$可进一步分解为

$P\left( {m, {l_q}|g, {u_q}, {W_q}, \hat \Phi } \right) = \sum\nolimits_{z \in T} [ P\left( {z|g, {u_q}, \hat \Phi } \right)P\left( {{l_q}|z, \hat \Phi } \right)\prod\nolimits_{w \in {W_q}} {P\left( {w|{W_q}} \right)P\left( {m|{W_q}, z, \hat \Phi } \right)} ]$

(18)

其中, P(w|W_q)表示词语w在W_q中的权重, 在本文中我们使用词语的反文档频率(inverse documentfrequency, 简称IDF).此外, 由于${\psi _{_{m, z, w}}}$(即$P\left({m|{W_q}, z, \hat \Phi } \right)$)矩阵的规模非常大(潜在的大小为K·V·N_M), 为了减轻数据稀疏性带来的参数估计困难, 受Gong等人的启发^{[9, 21]}, 我们使用与主题无关的词对齐概率p(m|w)对${\psi _{_{m, z, w}}}$进行平滑操作, 即:

$\psi _{m, z, w}^* = \sigma {\psi _{m, z, w}} + \left( {1 - \sigma } \right)p\left( {m\left| w \right.} \right)$

(19)

其中, σ是一个平滑参数且σ∈[0, 1]；p(m|w)表示词w和目标用户m间的主题无关的词对齐概率, 在本文中我们使用经典的IBM翻译模型1^[32]来计算.

根据公式(14)~公式(19), u_q提及用户m的概率可通过公式(18)计算.通过这种方式, 即可将计算得到的top-k概率值最大的目标用户作为推荐结果.

$ P\left( {m|{u_q}, {l_q}, {W_q}, z, \hat \Phi } \right) \\ \propto \sum\nolimits_{g \in G} [ \sum\nolimits_{z \in T} [ P\left( g \right)P\left( {{l_m}|g, \hat \Phi } \right)P\left( {z|g, {u_q}, \hat \Phi } \right)P\left( {{l_q}|z, \hat \Phi } \right)\prod\nolimits_{w \in {W_q}} {P\left( {w|{W_q}} \right)P\left( {m|{W_q}, z, \hat \Phi } \right)} ]] \\ = \sum\nolimits_{g \in G} {\sum\nolimits_{z \in T} {\left[ {P\left( g \right)P\left( {{l_m}|{{\hat \mu }_g}, {{\hat \Sigma }_g}} \right){{\hat \theta }_{z, g, {u_q}}}{{\hat \pi }_{{l_q}, z}}\prod\nolimits_{w \in {W_q}} {P\left( {w|{W_q}} \right){{\hat \psi }^*}_{m, z, w}} } \right]} } \\ $

(20)

3.1 高效top-k推荐

为了加快系统对在线查询的响应速度, 基于公式(18), 我们将目标用户m针对查询q的得分S(q, m)的计算过程分成在线评分O(q, t)计算和线下评分F(t, m)计算两个部分:

$S\left( {q, m} \right){\rm{ }} = \sum\nolimits_{t \in \left( {z, a} \right)} {O\left( {q, t} \right)F\left( {t, m} \right)} = \left\| {\vec q} \right\|\left\| {\vec m} \right\|\cos \left( {{\Delta _{\vec q, \vec m}}} \right) \propto \cos \left( {{\Delta _{\vec q, \vec m}}} \right)$

(21)

$O\left( {q, t} \right) = {\hat \theta _{z, g, {u_q}}}{\hat \pi _{{l_q}, z}}\prod\nolimits_{w \in {W_q}} {P\left( {w|{W_q}} \right){{\hat \psi }^*}_{m, z, w}} $

(22)

$F\left( {t, m} \right) = P\left( g \right)P\left( {{l_m}|{{\hat \mu }_g}, {{\hat \Sigma }_g}} \right)$

(23)

其中, t表示T×G集中的一个属性(即t=(z, g), z∈T且g∈G), F(t, m)表示线下计算的一个目标用户m关于属性t的分数, O(q, t)则表示在线计算的查询q在属性t上的权重.可以看到, 除了F(t, m), O(q, t)中的主要部分, 如${\hat \theta _{z, g, {u_q}}}, $${\hat \pi _{{l_q}, z}}$和${\hat \psi ^*}_{m, z, w}$也是通过线下计算的方式获得的.给定一个查询, O(q, t)的计算仅仅是对这些已得到的数值进行了线上整合.

一个直接的目标用户生成方法即通过扫描所有候选目标用户, 基于公式(19)将k个得分最高的目标用户作为推荐结果.然而, 该方法对于每一位候选用户均扫描一遍属性集, 这会产生严重降低系统的在线推荐效率.在本文中, 目标用户针对查询的得分是通过计算查询向量和目标用户向量的内积得到的(如公式(19)所示), 且模型中的所有目标用户向量都具有相同的长度.因此, 一个直观的针对该最大内积检索(maximum inner product search, 简称MIPS)问题的高效率解决方案, 即首先通过一些数学转换方法^[35]将该MIPS问题转化为一个k近邻(k-nearest neighbors, 简称KNN)检索问题, 然后使用一些高效率近似KNN检索算法^{[6, 7, 34]}来寻找推荐结果.然而, JUMBM模型潜变量分布的高维度问题会严重降低大多数低维检索算法的效率(即“维数灾难”问题).尽管一些高维检索框架基于不同的空间-文本索引在一定程度上减轻了高维度带来的检索困难, 但其仅能应用于基于关键字的文本检索任务, 不能很好地处理本文中的高语义相关度的用户活动检索问题^{[6, 20]}.此外, 这些算法都是针对近似而非精确检索任务设计的, 直接应用在目标用户推荐中会严重降低检索准确率.近来, Yin等人设计了基于聚类的分支定界算法CBB^[13]和属性剪枝算法AP^[12]以降低高维数据检索中的时间消耗, 可以在仅扫描一部分项目(在本文的推荐任务中, 项目即候选目标用户)或者属性的情况下找到使得最终得分最大的top-k个项目.具体来说, AP算法通过筛选具有较低查询偏好和项目相关性的属性来约束属性检索空间, CBB算法则通过选择在每个属性具有较高的上限得分项目组来对项目空间进行剪枝.但是, 即使AP算法只扫描每个项目的一部分属性, 其仍然需要遍历所有项目; CBB算法则必须扫描每个选定项目的所有属性来计算完整的得分.换句话说, AP和CBB算法仍需扫描大部分的项目或者属性空间来确定最终的推荐得分.

受CBB算法^[13]和AP算法^[12]的启发, 我们设计了一种混合剪枝算法HPA(hybrid pruning algorithm), 以实现对项目和属性检索空间的联合剪枝.HPA算法基于两个基本的观察事实:(1)由于向量$\vec q$和向量$\vec m$的模是两个常量, 其内积大小仅与两个向量的方向有关, 如公式(19)所示; (2)只有当查询q在属性t上的权重较高, 且m关于属性t的分数也较高时, 其对应的O(q, t)F(t, m)值才会对最终得分有足够的影响.因此在本文中, 我们首先使用球面K-means算法^[36]根据目标用户向量的方向将目标用户聚类进B组中.然后, 对每个桶$b \in B$计算一个上限向量$\vec a, $使其在每一个属性上的F(t, m)值最大(即$F(t, a) = {\max _{m \in b}}F(t, m)$).显然, 由于O(q, t)的值非负, S(q, a)即为桶b中所有目标用户的上限得分.同时, 对于每一个属性t_i($i \in [1, K \cdot R]$)计算一个目标用户排序列表${L_{{t_i}}}$, 使其包含k个F(t_i, m)值最高的目标用户.而对每个目标用户m, 我们根据F(t_i, m)的值对其对应的属性进行降序排序.注意, 所有上述计算和排序工作都是以线下计算的方式进行的.

给定一个在线查询q, HPA的在线处理流程如算法2所示.具体来说, HPA首先根据向量$\vec q$和每个桶的上限向量$\vec a$的内积S(q, a)的值对所有的桶进行排序(第2行).然后, 基于查询和目标用户在属性上的权重找到k个候选目标用户(第4行~第15行).在此过程中, 我们首先选择top-N个具有最小N值且覆盖了绝大部分的查询偏好的属性, 即选择$\sum\nolimits_{i = 1}^n {O\left({q, {t_i}} \right) > 0.9\sum\nolimits_{j = 1}^{T \times G} {O\left({q, {t_j}} \right)} } $(第4行).对于每一个top-N属性t, 我们从L_t中选择得分最高的目标用户作为候选用户(第5行~第14行).此外, HPA采用二叉最小堆来实现列表L, 使得L的根项m′(即堆顶)在L中具有最小的最终得分.此后, HPA顺序地扫描所有的桶.对于一个未扫描的桶b, 若S(q, m′)不小于b的上限得分S(q, a), 则HPA不再扫描后续桶, 算法提前终止(第18行~第20行).否则, HPA顺序扫描b中每一个目标用户来计算得分(第21行~第37行).在此过程中, 对于每一个需要计算得分的目标用户m, 我们基于Zhao等人提出的区域剪枝技术^[37]来检查能否避免遍历m对应的所有属性.具体来说, 假设HPA已遍历了属性{t₁, t₂, ..., t_i}, 则可知这些属性对应的部分得分S_p的值为$\sum\nolimits_{j = 1}^{i - 1} {O\left({q, {t_j}} \right)F\left({{t_j}, m} \right)}.$而对于第i项属性t_i, 其对目标用户m的上限得分为${S_p} + \sum\nolimits_{j = i}^{T \times G} {O\left({q, {t_j}} \right)F\left({{t_j}, m} \right)}.$由于HPA按照F(t, m)值降序遍历所有的属性, 则$\{ {t_{i + 1}}, ..., {t_{K \times R}}\} $中的任一属性t对应的F(t, m)值都比F(t_i, m)值要小.也就是说, 属性$\{ {t_{i + 1}}, ..., {t_{K \times R}}\} $对应的部分得分值应小于等于$\sum\nolimits_{j = i}^{T \times G} {O\left({q, {t_j}} \right)F\left({{t_j}, m} \right)}.$因此, m对应的所有属性的得分值S(q, m)的上限即为${S_p} + \sum\nolimits_{j = i}^{T \times G} {O\left({q, {t_j}} \right)F\left({{t_j}, m} \right)}.$当堆顶m′对应的得分值小于该上限得分时, HPA将不再需要扫描任何$\{ {t_{i + 1}}, ..., {t_{K \times R}}\} $中的属性(第26行~第29行).否则, HPA将扫描m′对应的所有属性来计算m′的得分(第31行~第36行).

算法2.混合剪枝算法HPA.

输入:

M:分成B个桶的目标用户集合

q:查询, q=(u_q, l_q, W_q)

L_t:每一个属性对应的有序目标用户列表

输出:

$L$:具有最高得分的top-k目标用户列表

1.  根据S(q, a_b)的大小对所有的桶进行排序;

2.   根据O(q, t)的大小对所有的属性进行排序;

3.   找到top-N满足$N \leftarrow \min \left({\left\{ {n|\sum\nolimits_{i = 1}^n {O\left({q, {t_i}} \right) > 0.9\sum\nolimits_{j = 1}^{T \times G} {O\left({q, {t_j}} \right), T \times G} } } \right\}} \right)$的属性;

4.   for each t∈N do

5.    for each m∈L_t且$m \notin L$ do

6.     if L.size() < k then

7.       L.insert(〈m, S(q, m)〉);

8.     else

9.      $m' \leftarrow L.top()$;

10.      if S(q, m) > S(q, m′) then

11.        L.deleteTop();

12.        L.insert(〈m, S(q, m)〉);

13.      end if

14.     end if

15.   end for

16.   for each b∈B do

17.     $m' \leftarrow L.top()$;

18.     if S(q, m′)≥S(q, a_b) then

19.       break;

20.     else

21.      for each m∈b且$m \notin L$ do

22.        ${S_p} \leftarrow 0$; ${O_p} \leftarrow 0$, $Skip \leftarrow {\rm{false}}$;

23.       while对于m存在未扫描的属性then

24.         ${S_p} \leftarrow {S_p} + O\left({q, t} \right)F\left({t, m} \right); $

25.         ${O_p} \leftarrow {O_p} + O\left({q, t} \right)$;

26.        if ${S_p} + \left({\sum\nolimits_{i = 1}^{T \times G} {O\left({q, {t_i}} \right) - OP} } \right)F\left({t, m} \right) \le S\left({q, m'} \right)$ then

27.          $Skip \leftarrow {\rm{true}}$;

28.          break;

29.        end if

30.       end while

31.       if $Skip = {\rm{false}}$ then

32.        if S(q, ′) > S(q, m′) then

33.         L.deleteTop();

34.         L.insert(〈m, S(q, m)〉);

35.        end if

36.       end if

37.     end for

38.    end if

39.   end for

40.   逆排序L;

41. return L;

4 实验与分析

为了定量地分析JUMBM的性能, 我们在两个真实数据集上构建了实验.本节将详细介绍实验构造和过程, 并对实验结果进行展示和分析.

4.1 数据采集与实验设定

本文的实验构建在采集自新浪微博和Twitter的数据集上.数据集的采集策略如下.

微博数据集.受Gong和Wang等人^{[9, 49]}的启发, 我们采用雪球抽样方法, 从5个约有1 000个粉丝的初始用户开始, 按照用户间的关注关系(即following-follow关系)抽取中国微博用户的个人信息和历史消息(受新浪微博API的限制, 我们仅能采集每个用户的前1 000位关注用户).该采集策略能够保证得到微博完整数据图谱的一个子图, 覆盖包括普通用户、明星用户、媒体工作者、微博广告商在内的全部微博用户类型, 从而最大程度地降低数据采集偏置性.为了保证得到足够的位置数据, 我们选择至少发布过3条带有位置标签的消息的用户.从2014年1月~2014年7月, 我们共抽取了1 701 286条用户个人信息和26 994 838条带有位置标签的消息.为了构建用户间的提及关系网络, 我们抽取包含一个以上“@”实例的消息.然后, 使用一种简单、有效的用户定位方法为所有可定位的目标用户分配一个居住位置(经度/维度).最终, 我们得到由147 621名用户发布的594 187条带有位置标签和提及实例的消息, 以及251 054名已知居住位置的目标用户构成的数据集.

Twitter数据集.我们使用同样的抽取策略获得Twitter上美国用户的个人信息和历史消息来构建Twitter数据集.从2016年10月15日~2017年3月15日, 我们得到了一个由1 620 081名用户发表的35 219 791条带有位置标签的消息组成的原始数据集.在进行用户提及关系网络构建及可定位目标用户抽取处理之后, 最终的Twitter数据集包含553 145条带有位置标签和提及实例的消息, 以及由807 330条提及关系关联着的133 625位当前用户和187 843位居住位置已知的目标用户.表 3列取了对本文数据集的统计信息.

需要注意的是, 大多数微博和Twitter用户并未在其个人信息中公开居住位置, 或者仅对其进行了粗粒度的描述(如居住城市).因此, 我们采用一个被广泛使用的^{[40, 42, 43]}ground-truth用户位置推理方法为每一位目标用户分配一个居住位置(经度/维度).具体来说, 对于用户u, 我们首先计算出${L_{{D_u}}}$中所有位置确定的l₁-多元几何中心点^[36]作为u的初始位置.注意, 我们选择使用几何中心点而非区域的中位点的原因是其对位置异常值是鲁棒的, 尤其是当用户有在远离其通常活动的区域的活动历史时.然后, 我们筛选出历史移动轨迹不正常的用户.具体来说, 我们仅保留至少发布过3条且发布自15km地理半径范围内的消息的用户.同时, 我们根据消息标记的时间戳和位置筛选出移动时速超过1 000km/h的用户.此外, 对于指定了详细家庭位置(例如, GPS坐标或详细位置描述)的用户, 我们通过检索地理数据库获得其对应的位置点.本文中, 我们使用GeoName数据库(http://www.geonames.org/)和高德地理编码API(http://lbs.amap.com/api/javascript-api/guide/map-data/geocoding)将用户对位置的描述转化为经纬度坐标.

此外, 对于一条用户提及活动d=(u, W_d, l_d, M_d), 有|M_d|≥1.因此, 我们将d中每一条(u, W_d, l_d, m), m∈M_d视为一条训练/测试用例.也就是说, 本文数据集中的训练/测试用例的数量是由数据集包含的提及实例的数量而不是消息的数量决定的.受Gong等人^[9]研究的启发, 我们采用基于时间的分割方法将数据集分割为训练集和测试集.即, 首先根据发表时间的先后将所有提及活动进行排序, 然后按照80/20的比例对数据集进行划分.

4.2 评估指标

对于测试集中的一条测试用例(u, W_d, l_d, m), L_k包含k个具有最高得分的目标用户.对于一个ground-truth目标用户m^*, 若有m^*∈L_k, 则计数为一个命中(hit), 否则计数为一个未命中(miss).然后, 我们采用准确率Accuracy@ $k$来评估推荐的质量, 即:

$Accurcy@k = \frac{{Hits@k}}{{{N_{testcase}}}}$

(24)

其中, Hits@k表示对于给定的k值, 系统在测试集上的命中次数; N_testcase则表示所有测试用例的数目.除此之外, 我们采用评估推荐系统性能常用的精确率(precision)、召回率(recall)和F1值(F1-meature)指标对目标推荐结果进行评估.同时, 采用平均逆序排名(mean reciprocal rank, 简称MRR)来评估结果列表的排序效果.

4.3 对比方法

本文从推荐有效性和推荐效率两个方面对所有方法进行性能评估.

4.3.1 推荐有效性

在推荐有效性方面, 我们采用以下方法作为对比方法.

(1) HIS.HIS是一种基于用户提及历史的基准目标用户推荐方法^{[8, 9]}.给定一条查询, HIS方法推荐训练集中被当前用户提及次数最多的目标用户.

(2) CAR.CAR^[8]是一个内容感知的目标用户推荐框架.通过抽取内容、社交、位置和时间信息相关的特征, CAR使用学习排序(learning-to-rank)方法为一条促销类的消息推荐有高回应率的目标用户.在本文中, 我们使用与原文^[8]相同的特征集来实现CAR框架.因此, 我们额外抽取了每一位目标用户在数据集限定的日期内发表的全部历史消息以及用户间的交互历史(用户间的提及与转发历史)来丰富我们的原始数据集.

(3) A-UUTTM.A-UUTTM是由Gong等人提出的基于翻译模型的潜变量主题模型^[9].该模型同时考虑了当前消息的内容和目标用户的内容历史, 是目前用于目标用户推荐效果最好的方法.由于目标用户的内容历史对A-UUTTM来说至关重要, 我们抽取了原始数据集中所有目标用户在被“@”时间之前发表的最新的4条消息.同时, 我们使用与文献[9]相同的参数设置来实现A-UUTTM.

此外, 本文设计了3种baseline方法以验证在建模过程中分别考虑用户语义模式、目标用户的地理聚集区域以及当前用户的移动模式情况下的系统性能.

(1) JUMBM-NT.JUMBM-NT是本文提出的JUMBM模型的一个变种, 其仅考虑空间因素而忽略了用户的语义模式对其提及行为的影响, 即在建模过程中忽略了用户提及活动中的文本词语W.在JUMBM-NT模型中, 给定一个主题, 当前用户根据一个主题-目标用户分布来选择目标用户.

(2) JUMBM-NA.与JUMBM相比, JUMBM-NA模型去除了对目标用户地理聚集区域的建模过程.在JUMBM-NA模型中, 对于一条用户提及活动d, 主题z负责生成词语W_d、目标用户m∈M_d和位置l_d, 且每一个目标用户m∈M_d都依据基本的主题-翻译过程生成.

(3) JUMBM-NP.JUMBM-NP是JUMBM模型的另一个变种.JUMBM-NP不考虑用户的移动模式对用户提及行为的影响, 即对于一条用户提及活动中的位置d, JUMBM-NP忽略了对用户当前位置l_d的建模过程.

4.3.2 推荐效率

为了评估本文提出的HAP算法的效率, 我们将HAP与以下4种算法进行比较.

(1) Brute Force Algorithm(BF).对于给定的查询, BF算法通过扫描每个目标用户的所有属性来计算目标用户针对查询的得分, 然后统计得分最高的k个目标用户作为推荐结果.BF也是第4.3.1节中提到的对比方法HIS、CAR和A-UUTTM使用的推荐算法.

(2) Threshold Algorithm(TA).TA算法^[26]是对传统的基于阈值的方法的一个扩展, 是当前效果较好的低维度检索算法.

(3) Clustering-based Branch and Bound Algorithm(CBB).CBB算法^[13]是一种项目搜索空间剪枝算法, 能够在不扫描所有项目的情况下找到正确的top-k结果.

(4) Attribute Pruning Algorithm(AP).AP算法^[12]是一种用于属性空间剪枝的分支界定算法.对于一个项目, AP算法能够在仅扫描部分属性的情况下确定该项目是否为正确的top-k结果.

4.4 结果与分析 4.4.1 推荐有效性

本节中, 我们从推荐有效性方面对JUMBM进行评估.经过多次前期实验, 将参数K和R的值设置为K=70, R=90, 以展现JUMBM的最优性能(参见第4.4.3节).此外, 参照前期研究^{[9, 21]}, 我们在实验中将平滑参数σ设置为σ=0.8.表 4和表 5分别列取了在微博和Twitter数据集上, 各方法在精确率、召回率、F1值、MRR、Accuracy@3和Accuracy@5等指标下的性能表现.图 4显示了不同推荐目标用户数量, 即不同$k$值下的各种方法的实验精确率、召回率和F1值.注意, 图 4中仅列出了k∈[1,7]范围的结果值, 这是因为, 当k > 7时各指标下的实验结果值已不再显著变化.

微博数据集上的推荐.在微博数据集上, 本文提出的方法在所有评价指标下均取得了最优的实验结果.如表 4所示, JUMBM的推荐精确率为0.647, 召回率为0.634, F1值为0.641.与当前用于目标用户推荐效果最好的A-UUTTM方法相比, 本文提出的基于JUMBM的推荐方法分别在精确率、召回率、F1值上取得了11.2%、13.6%和12.5%的相对提高.此外, Accuracy@3和Accuracy@5的结果值显示, 66.1%的ground-truth目标用户能够在top-3结果中找到, 68.9%的ground-truth目标用户出现在了top-5结果中.同时, JUMBM在MRR值方面也取得了最优结果, 这表明, JUMBM不仅能够生成准确的推荐, 也能生成良好的推荐结果排序.图 4所示的实验结果显示, 随着被推荐目标用户的增多, JUMBM方法的性能有所下降, 但仍然在所有指标上均优于对比方法.当为一条消息推荐最佳目标用户时, JUMBM可以获得最佳的F1值.如果想获得最高的召回率, 则可使用JUMBM推荐更多的目标用户.

从实验结果中可以观察到:

(1) HIS方法在所有指标上均落后于其他方法.这表明, 仅基于历史的目标用户建议方法可能会导致不准确的推荐结果.

(2) 与CAR、A-UUTTM和JUMBM相比, JUMBM-NT的性能表现最差.这说明, 使用用户提及活动的语义模式来挖掘用户提及行为偏好的必要性.与其他方法相比, JUMBM-NT仅基于用户的提及活动的空间上下文信息来捕捉其行为偏好, 忽略了文本内容信息的影响.

(3) JUMBM和A-UUTTM的表现均优于CAR, 证明了一个严格设计的概率生成模型相对于一般的基于特征的学习-排序方法在表征用户提及行为方面的优势.

(4) 尽管A-UUTTM同时考虑了当前用户和目标用户的内容信息, 但JUMBM仍然在所有指标上均取得了更好的结果, 表明了引入用户提及活动空间上下文因素对其提及行为建模的必要性.与A-UUTTM相比, JUMBM考虑了目标用户的地理分布和当前用户的移动模式, 能够更好地表征和发掘用户的行为偏好, CAR和A-UUTTM均忽略了这两个地理因素对用户提及行为的影响.

(5) 在我们的实验中, 综合考虑了内容和空间因素的方法, 其性能表现均优于仅考虑了单个因素的推荐方法.例如, 当k=5时, JUMBM的推荐准确率为0.689.这一结果与仅考虑空间上下文因素的JUMBM-NT相比提高了62.5%, 与仅基于内容信息的A-UUTTM相比提高了6.2%.显示出在建模过程中综合考虑内容和空间因素对准确挖掘用户提及行为偏好的必要性.

Twitter数据集上的推荐.从表 5和图 4可以看出, Twitter数据集上的实验与微博数据集上的实验有相同的结果趋势, 即JUMBM在所有指标上一惯地优于对比方法.但是, 在Twitter数据集上, 各方法的性能表现均稍低于其在微博数据集上的性能表现.这可能是因为Twitter数据集中的用户平均提及活动数量较少, 导致模型对用户提及行为偏好的推理不够准确.

4.4.2 各因素对推荐性能的影响

通过比较JUMBM及其变种模型的实验结果, 我们可以进一步评估当前用户的语义模式(C)、目标用户的地理分布(G)以及当前用户的移动模式(S)等因素对JUMBM推荐性能的影响.表 6和表 7分别展示了JUMBM及其变种模型在微博和Twitter数据集上的实验top-k推荐准确率.其中, 方法的推荐准确率越高, 则各变种模型的缺失因素越不重要.注意, 表 6和表 7仅展示了k小于10时各方法的性能表现.

因为对于本文研究的推荐任务来说, 更大的k值是没有意义的.从结果中可以看到, 每个因素对推荐准确率的影响是不同的.总的来看, 各因素对目标用户推荐性能影响程度的顺序为$C \succ G \succ S$.具体而言, 首先, 语义模式在目标用户推荐性能方面起着主导作用.例如, 仅考虑了两个空间因素(G和S)的JUMBM-NT, 比基于同样的空间因素但同时考虑内容信息的JUMBM的推荐准确率低50%以上.这一结果与Chen、Tang和Zhou等人的研究^{[2, 8, 10]}是一致的.其次, 考虑目标用户的地理分布对提高目标用户推荐准确率来说十分必要.例如, 与JUMBM- NA相比, JUMBM对目标用户的地理聚集区域进行了建模, 这使其在微博数据集上的实验推荐准确率提高了约9%(k=9时).第三, 考虑了当前用户移动模式的方法的推荐性能表现略优于未考虑这一因素的方法.如表 6所示, 对用户移动模式建模的JUMBM方法相比于未考虑用户移动模式的JUMBM-NP方法的推荐精确率提高了约3.5%(k=9时).

4.4.3 参数敏感性分析

我们构建了一系列的实验来研究模型参数的改变对推荐结果的影响.在JUMBM中, 最重要的两个参数即主题数量K和区域数量R.本节我们仅展示使用不同参数的JUMBM在微博数据集上的实验结果, 因为在Twitter数据集上的实验结果与之是相似的.

具体来说, 我们展示了在主题数量K∈[50,90]和区域数量R∈[70,110]时JUMBM在Accuracy@5指标下的性能变化, 见表 8.对于模型中的超参数, 受前期研究的启发^{[12, 53]}, 我们将其设置成固定值以节省计算成本, 即α=50/K、η=50/R、β=γ=ξ=0.01、λ₁=λ₂=0.5.表 8展示了不同K和R值下的Accuracy@5结果.可以看到, 在K和R值较小时, JUMBM的推荐精确率随着K和R值的增加而迅速增大, 但当其超过一定的阈值, 即K=70且R=90时, JUMBM的推荐精确率不再显著变化.这是因为, 在JUMBM中, 主题和区域的数量代表了模型的复杂度.当K和R值较小时, 模型对数据的描述能力有限.相对地, 当K和R增大到一定程度时, 模型已复杂到足够处理当前数据.此后, 随着$K$和$R$的进一步增大, 数据稀疏性问题会变得越来越严重, 继而导致模型过拟合并使得模型学习到的参数不再可靠.因此, 在构造第4.4.1节中的实验时, 我们采用设置K=70、R=90作为推荐有效性和推荐效率间的一个折衷.

4.4.4 推荐效率

通过与第4.3节中提出的4种算法进行比较, 我们在微博数据集上对本文提出的HPA算法的在线推荐效率进行评估.我们使用Java语言(JDK 1.7)实现所有在线检索算法, 并将所有程序运行在一台配置了Intel Xeon E5处理器(2.4 GHz)、128 G内存、操作系统为Windows Server 2008 R2的PC上.

我们在6 300维(即K=70, R=90)的检索情况下, 将k分别设置为1、3、5、7和9来展示各算法的性能.同时, 我们使用数据集中的所有查询对算法进行测试.此外, 经过若干次的预先实验, 我们将HPA算法使用的桶的数量B设置为430以达到算法的最佳性能.图 5给出了BF、CBB、AP和HPA算法的平均在线查询处理时间.注意, 我们没有在图 5中列出TA的处理时间.这是因为相比于其他算法, TA的时间消耗过于严重.在我们的实验中, TA需要8 464.3ms来产生top-1结果, 同时需要近11 000ms来产生正确的top-5结果.TA效率如此低下的原因是其作为一种单层次检索算法, 必须频繁地更新阈值并维护排序列表的动态优先级队列, 使其仅能处理低维数据检索问题.如图 5所示, 本文提出的HPA算法在推荐效率方面显著优于所有对比方法.例如, HPA算法在296.1ms内从超过25万名的候选目标用户集合中找到了正确的top-5结果.这仅相当于TA算法时间消耗的2.7%、BF算法的38.04%、CBB算法的54.8%以及现有最高效的AP算法的59.03%.在我们的实验中, 当k=5时, HAP平均仅需扫描643个属性(约占全部属性的10.2%).最终的统计结果显示, 需要遍历所有属性来计算得分的候选目标用户数量为11 046, 仅占全部候选目标用户的4.4%.尽管随着被推荐目标用户数量的增加, HPA算法的推荐效率有所下降, 但即使在k=9的情况下HPA算法仍能以相对其他算法更快的速度响应在线查询.可以看出, 在数据维度很高的情况下, 本文提出的HPA算法比遍历检索算法BF、低维检索算法TA、空间剪枝算法CBB和当前效率最高的检索算法AP的计算效率都更高.

5 总结

当前, 社交媒体中的提及机制正在用户在线交互和网络信息传播方面扮演着重要角色.本文从普通用户的在线交互角度着手, 通过对用户提及行为的分析和建模构建一个推荐系统, 为给定的消息自动生成候选目标用户, 从而帮助用户识别目标、节省搜索时间.通过对大型真实社交媒体数据集的分析发现, 用户的提及行为受其提及活动的语义和空间上下文因素的联合影响.针对此, 本文提出一个联合隐式概率生成模型JUMBM来模拟用户提及活动的生成过程.JUMBM通过一种统一的方式进行语义和空间上下文感知的用户提及行为联合建模, 发掘用户的移动模式、地理区域依赖的语义兴趣及目标用户的地理聚集模式.同时, 本文提出一个混合剪枝算法HPA, 用以应对推荐中遇到的"维数灾难"问题并加快推荐系统对在线top-k查询的响应速度.在大型真实数据集上的实验结果表明, 本文提出的方法在推荐有效性和推荐效率方面均优于对比方法.