事件社交网中基于有向标签图及用户反馈的活动推荐方法

单晓欢，张志国，宋宝燕，任成林

（辽宁大学信息学院，沈阳110036）

0 引言

近年来，信息技术及互联网技术的飞速发展，推动了社交网络的广泛应用，其中以Meetup［1］、Plancast［1］、Douban［2］和Google+Event［3］等为代表的基于事件的社交网络（Event-Based Social Network，EBSN）［4］作为一种新型的社交网络应用得到了快速的发展。用户可以在EBSN 平台上注册、创建、发布和组织社交活动，如篮球、音乐会、社团活动、公益招募等，用户可以根据自己的需求通过限制某些条件在线搜索并在线下参加其选择的活动。

EBSN平台会不定期地发布各种活动，同时也会将过期的活动下线。随着社交网络的不断兴起，EBSN上活跃用户数以及活动数量日益增长。因此，用户找到其感兴趣的活动变得越来越困难，研究有效的EBSN 活动推荐方法以提高推荐质量将面临巨大的挑战。

为此，本文提出一种EBSN 上基于有向标签图及用户反馈的活动推荐方法。因为EBSN 是一种异构的复杂社交网络，因此本文利用活动发生的时间先后顺序将平台上的活动抽象为有向标签图，其中节点表示活动，有向边则表示两个活动发生的先后以及发生地之间的距离，活动的属性（如活动类型，发生的时间、地点等）则通过节点标签进行表示，两个活动是否同一天进行等属性则通过边标签表示。同时将EBSN 上的活动推荐转换成子图查询问题进行研究。本文的主要内容如下：

1）提出一种有向图结构特征（Directed Graph Structure Feature，DGSF）索引，该索引由节点属性特征（Node Property Feature，NPF）索引、有向边属性特征（Directed Edge Property Feature，DEPF）索引以及时间特征（Time Feature，TF）索引构成。利用NPF索引，根据时间、节点的入度及出度等信息过滤掉无效节点，以获得较小的节点候选集；同理，利用DEPF 索引及TF索引，根据边标签属性以及活动发生的时间过滤掉无效边，以获得较小的边候选集。

2）提出基于DGSF 索引的多属性候选集过滤策略，利用时间、节点的入度、出度、标签类型以及相隔天数等特征的限制，实现对查询图候选集的进一步剪枝，避免过多的冗余计算。

3）在获得的候选集基础上，提出一种带有用户反馈的改进UCB（Upper Confidence Bound）活动推荐算法——EN_UCB（Elastic Net UCB），在UCB 算法中引入弹性网回归，根据多影响因素计算用户对活动的兴趣值，并按兴趣值从大到小向用户进行推荐，同时接收用户的反馈，实现有效的在线活动推荐。

1 相关工作

随着EBSN 中发布的活动越来越多，为用户找到最符合其兴趣的活动变得越来越困难［5］，同时EBNS中的活动推荐具有冷启动、实时、容量限制及冲突限制等特性，这导致传统的协同过滤、矩阵分解等推荐方法无法直接应用于EBSN 的活动推荐。

文献［6］在进行活动推荐时，通过分析用户的社会角色以及位置属性，对现有的协同过滤算法进行扩展，定义了四种活动类别，提出一种基于社交及位置属性的活动分类机制。一旦不同的类别被确定，利用适当的排名为新用户进行推荐，解决了冷启动问题。文献［7］提出了一种EBSN 中基于上下文的推荐方法，该方法利用用户的喜好和位置关系等多种信息进行综合评估，进而推荐出最合适的活动。文献［8］分析用户对某个主题相关的活动感兴趣，那么其有可能会参加该主题相关的后续活动，通过分析时间、空间等特征，对用户进行监督学习，根据提取的特征进行活动推荐。该算法明确了每个特征对参与活动的影响，算法相对简单，但是它忽略了用户间的社会属性关系对活动推荐的影响。为解决活动推荐的冷启动问题，一种贝叶斯泊松分解模型CBPF（Collective Bayesian Poisson Factorization）［9］被提出，其将贝叶斯泊松因式分解作为基本单元，用于建模用户对活动、社会关系以及活动内容的响应；然后利用标准矩阵分解模型的思想进一步连接这些基本单位。此外，该模型中活动内容、组织者以及位置信息被用来表示预测用户对冷启动活动的响应。SIARS（Social Infor⁃mation Augmented Recommender System）［10］充分利用活动组织者及群组成员的社会影响力，并结合基本的上下文信息进行活动推荐。该系统结合EBSN 及其他社交网络的信息描绘活动组织者的社会影响力，并考虑群组成员之间的互动以进行活动推荐。此外，文献［10］还提出了一种利用主题模型寻找活动所属最相似主题的内容感知推荐模型，该模型结合地点知名度及其分布的位置进行活动推荐。该方法考虑了活动的组织者和群组成员的社会影响力对活动的影响，寻找与活动属性相似的主题并结合地点分布进行活动推荐，提高了活动推荐的准确性；然而该模型未考虑活动冲突、活动容量等影响因素。

上述推荐方法虽然考虑了部分约束条件，但仍未达到全局最优推荐，同时忽略了用户是否接受推荐活动对后续推荐的影响。文献［11］考虑了活动冲突、位置信息以及活动开销等因素，提出了一种启发式算法，考虑多种因素对活动推荐的影响，提高了活动安排的效率；然而该算法没有考虑在线互动安排。文献［12］提出了两种利用剪枝技术的近似算法及精确算法解决不同活动之间存在冲突的问题，从而避免冗余安排，该算法实现了线上活动推荐。文献［13］考虑了诸多限制因素，实现了线上活动推荐，同时为解决现有方法衡量事件属性仅利用单个值和少量属性的线性组合、权重采用预定义和固定值以及不考虑用户是否接受推荐活动等问题，提出了一种新的在线活动推荐策略，引入MAB（Multi-Armed Bandit）问题［14］，分别利用TS（Thompson Sampling）算法、UCB 算法［15］以及eGreedy算法进行活动推荐。

2 有向图结构特征索引

2.1 EBSN与有向标签图转换

本文将EBSN 抽象成有向标签图G(V，E，LV，LE)，其中将EBSN 中活动抽象为图中节点，V 表示节点集合；活动发生的先后顺序则通过有向边表示，E 则为边集合；活动的属性，如活动类型、举办时间、地点等抽象为节点标签，LV 则为节点标签属性集合；两个活动之间的距离以及举办时间利用边标签表示，LE 为边标签属性集合。本文将满足距离小于等于m（单位：m）的活动按举办时间的先后进行连边，先举办的活动指向在其之后举办的活动。

在EBSN 平台中，不同的活动之间可能存在一定的冲突，如两活动在同一时间举办或时间存在交叉等，为避免在后续查询推荐过程中进行冲突检测等操作，本文将EBSN 抽象为有向标签图的过程中已对冲突事件进行过滤，有效提高了查询效率。

下面以列举的15 个活动为例，如表1 所示，将其抽象为15个节点，同时按活动类型分为足球A、电影B、音乐会C。其中如v3与v6因时间有交集，则认为两活动为冲突活动，无边相连。转换后的有向标签图如图1（a）所示。

图1 有向标签图及查询图示例Fig.1 Examples of directed label graph and query graph

表1 节点属性标签表Tab.1 Node property label table

用户在进行活动搜索时，可以根据用户的查询限制条件，将活动搜索转换为查询图表示，以实现将推荐活动转换为子图查询。例如，用户要系统为其推荐2019-03-17—2019-03-23期间的足球、音乐会和电影活动，同时足球和电影活动要相差一天。根据查询需求可转换为图1（b）所示的6 种查询图表示，其中边上的属性b 表示活动不在同一天进行，“1”则表示相差一天。

2.2 DGSF索引

2.2.1 NPF索引

本文有向标签图中节点的类型、时间、出入度等属性标签具有一定的标志性和可辨别性，因此遍历有向图，获取节点的属性标签信息构建NPF 索引。该索引由两级结构构成：顶层结构索引节点类型，由〈节点类型，所属类型数量〉构成；底层结构则由〈节点编号，入度，日期，时间，出度，活动容纳人数〉构成，通过广度优先遍历，统计各个节点的上述信息。以图1为例，有向标签图G中包含了A、B、C三种类型的节点，其NPF索引如图2 所示，其中：id 表示节点编号，ind 表示节点入度，date 表示活动举办日期，time 表示时间，og 表示节点出度，su则表示活动能容纳的用户数量。

图2 NPF索引示意图Fig.2 Schematic graph of NPF index

2.2.2 DEPF索引

DEPF 索引同样包含两级结构：顶层结构为边标签类型；底层结构则为每种边标签类型所包含的边，由〈id1，id2〉构成。值得注意的是，因为本文研究的是有向图，所以AB和BA不是同一种类型。仍以图1 为例，图G 包含AA、AB、AC、BA、BB、BC、CA、CB、CC 共9 种类型的边，其DEPF 索引如图3 所示，其中id1、id2表示边的两个端点编号。

图3 DEPF索引示意图Fig.3 Schematic graph of DEPF index

2.2.3 TF索引

TF 索引的两级结构中：顶层结构用于判断活动是否为同一天举办，相同则为a，反之则为b；底层结构由〈端点1，端点2，相距时间〉构成。仍以图1 为例，TF 索引如图4 所示，其中id1、id2表示边的两个端点，ti 表示相距时间（单位：min），day表示相距天数。

图4 TF索引示意图Fig.4 Schematic graph of TF index

3 基于DGSF索引的多属性候选集过滤

子图查询效率与索引及节点、边的过滤程度密切相关，因此本文提出了基于DGSF 索引的多属性候选集过滤策略，其中包括节点过滤及边过滤。

3.1 多属性候选节点集过滤

本文的多属性候选节点集过滤将利用时间及度进行两次过滤，以得到最终的节点候选集。

在时间过滤中，根据用户给出的日期限制（可以是具体日期也可以是日期范围）以及活动类型，利用NPF索引将不满足日期的节点进行剪枝，以获得初步候选集。

度过滤中，根据查询节点类型及出入度，利用DNF 索引，保证候选集中各节点的出入度不小于查询节点，以获得最后节点候选集。

3.2 多属性候选边集过滤

利用多属性候选节点集过滤策略可以有效剪枝不满足条件的节点，获得相对较少的节点候选集。本节在候选节点集的基础上，利用DEPF索引和TF索引，提出了多属性候选边集过滤策略。

该策略首先在查询图中根据边的类型检索DEPF 索引，找到类型相同且两端点在对应节点候选集中的边，获得一步候选边集；然后根据用户对时间的限制，利用TF 索引过滤掉不满足时间限制的边，获得二步候选集；最后将一、二步候选集中具有相同连接节点的边进行连接，得到查询候选集。

4 具有用户反馈的改进UCB 算法

UCB 算法为解决MAB 问题提供了理论保证，它适用于解决不同的MAB 变形问题。UCB 解决MAB 问题的思路是利用置信区间，即不确定程度，置信区间越宽，则越不确定，反之亦然。每个臂的兴趣均值都有个置信区间，随着实验次数的增加置信区间会变窄，每次选择前，都根据已有实验的结果重新估计每个臂的均值和置信区间，选择置信区间上最大的那个臂。

由于一个活动有多个特征属性，但无法准确判断哪个特征属性影响大，为此本文提出一种带有用户反馈的改进UCB算法，即EN_UCB 算法。该算法在UCB 算法中引入了弹性网回归，弹性网回归既能实现岭回归对重要特征选择的目的，又能像Lasson 回归那样，删除对因变量影响较小的特征。具体算法如算法1所示。

算法1 EN_UCB。

在算法1中，输入参数中：λ1表示初始化单位矩阵系数；α表示EN_UCB 算法对活动推荐探索系数；Vsum表示利用DGSF索引得到的活动候选集，Vsin则是候选集的一个子集，其活动数由用户选择接纳活动的数量决定；v表示某一活动。输出参数At则是最终推荐的活动结果集。该算法利用一个d×d 的矩阵Y 存储每个活动通过反馈不断修正的属性值变化，利用一个d×1 的向量b 存储活动获得的奖励变化，该处奖励为用户反馈接受推荐活动与否对活动的影响，用一个随机变量的期望进行表示，即。算法中基于弹性网回归更新Y 和b，如第5）行所示，并利用更新后的Y 和b 来计算权向量。利用先验知识，计算每个活动的奖励值，如第8）行所示。计算候选子集的奖励值，如第10）行所示，同时每次更新，并按其进行排序，将排序靠前的活动推荐给用户，如第11）行所示。用户可以选择接受或是拒绝，用户的反馈结果将影响后续的推荐。

5 实验与结果分析

5.1 实验环境及配置

本文实验环境为Intel Core i7-8550U CPU@1.80 GHz 2.00 GHz处理器，16 GB 内存，256 GB SSD+1 TB 硬盘，编程语言为Java。

实验分别在真实数据集和仿真数据集上完成。真实数据集来自Meetup 社交网站中美国旧金山附近用户及其相关活动的数据，时间范围是2016-08-31—2018-06-31。其中用户数据包含了用户的位置、偏好等信息，活动数据包括活动的属性、举办日期、时间、举办人、地点等信息。在仿真数据集中，产生的ˆ符合正态分布，特征向量符合正态分布和均匀分布，生成一个具有16维的特征。实验具体参数配置如表2所示。

表2 实验参数配置Tab.2 Experimental parameter configuration

5.2 结果分析

本节将从接受率、遗憾率［12］以及查询时间等方面进行实验，验证本文方法的有效性和可行性。

如图5所示，k=103，随着用户数量的增加，接受率在逐渐上升而遗憾率逐渐降低，这是因为算法的估计θ经过若干次修正后变得更加精准。TS 算法性能最差，其接受率较低而遗憾率很高，这是因为在具有特征的MAB的情况下，所有活动通过共享θ相关联，TS不能通过前期推荐的活动而预估其对后续活动的影响。eGreedy算法虽然会在每次推荐后，改善其后续推荐，但由于小于参数ε时，活动是随机安排的，这导致用户的接受率和遗憾率会相对低于UCB。本文EN_UCB 算法引入弹性网回归对特征进行筛选，提高了推荐的准确性，因此用户接受率更高。在仿真数据集及真实数据集中，接受率及遗憾率出现突然下降的情况，这是受活动容量限制的影响；同时接受率与遗憾率出现上升或下降的波动则是受用户反馈的影响。

图6 显示了各算法的运行时间对比情况，随着活动数的增加，运行时间逐渐增加。其中：UCB 算法最耗时，这是因为它需要为每个活动计算置信区间；TS 算法则需要通过采样获得θ，同样需要花费一定的时间；当活动数量较少时，eGreedy算法运行速度较快，这是因为当小于参数ε 时，活动随机安排；本文构建有向标签图以及DGSF 索引的过程均在线下进行，因此不计入EN_UCB 算法的运行时间，EN_UCB 算法仅在过滤后的较小候选集上进行查询，因此运行时间最短。

图5 不同数据集上接受率及遗憾率对比Fig.5 Comparison of accept and regret rates on different datasets

图6 不同算法在不同数据集上的的运行时间对比Fig.6 Running time comparison of different algrithms on different datasets

6 结语

本文针对EBSN 上的活动推荐问题展开研究，首先将EBSN转换为有向标签图，并在转换过程中对冲突活动进行过滤；其次，提取节点及边的属性特征信息，构建DGSF 索引；然后，提出基于DGSF 索引的多属性候选集过滤策略，利用时间等特征限制进行剪枝过滤，以获得查询候选集；提出一种具有用户反馈的改进UCB 活动推荐算法，引入弹性网回归以提高推荐准确性，同时接收用户反馈，以优化后续活动推荐。实验结果表明，本文提出的方法能快速准确地为用户推荐活动，具有一定的实际应用价值。

然而，在本文的研究中未考虑EBSN 中活动动态变化的情况，因此在未来工作中将对动态变化下的索引维护问题进行研究，使得本文方法更加完善。