一种融合信息网络结构的数据增强行为预测算法

傅晨波，夏镒楠，岳昕晨，俞山青，闵 勇

1(浙江工业大学 信息工程学院，杭州 310000) 2(浙江工业大学 网络空间安全研究院，杭州 310000)

1 引 言

人类的移动行为预测一直是经济、社会领域的关注热点，从预测病毒传播、个性化推荐到城市规划等众多应用领域都依赖于人们预测移动行为的能力[1-3].通过预测人们未来的移动行为，政府可以设计更好的交通规划来缓解交通堵塞的压力；美团，Yelp等商业平台也可以通过预测用户的移动行为为用户提供优质服务，如推荐餐馆等.随着近些年这类基于用户移动行为数据应用的增长，了解并研究用户的移动模式已成为一种迫切需求.

早期对于人类移动数据建模的研究主要从单一信息源的角度出发，例如基于矩阵分解的预测算法(Matrix Factorization，MF)[4]和基于马尔科夫链的预测算法(Markov Chains，MC)[5]，这些算法主要通过对人群的总体偏好和用户的行为转移特征对人类的移动行为进行预测.随着人们在互联网上存留信息的多样化，如用户行为历史和评论信息等，许多工作开始利用额外的用户相关信息来提高模型的预测性能，特别是当用户数据包含了用户的社交关系时[6-8].例如，Yang等人[9]设计了一种同时对用户移动数据以及社交关系进行嵌入的方法，在社交关系嵌入的基础上加入用户移动行为映射得到新的向量嵌入，结果显示该算法无论在用户朋友预测还是位置预测任务上都获得了较好的表现.Lian等人[10]提出了一种名为Collaborative Exploration and Periodically Returning(CEPR) 的模型，该方法通过学习用户社交网络和地理因素的特征在位置预测任务上获得了较好的效果.这些研究结果都说明了在使用多源数据后预测效果能够得到进一步提升.

除了添加额外用户信息外，随着网络科学理论技术[11]的逐渐成熟，研究者们开始将网络图分析的方法应用到序列数据的相关研究[12]中.相比较于直接学习用户序列信息的模型，将用户行为序列转为网络结构化数据能更直观地展现序列中的隐藏信息.Lacasa等人[13]提出了一种可视图构建网络(Visibility Graph，VG) 的方法，将序列数据转换为网络图数据，并利用所构建的图的拓扑特征来表征原始序列的特征.之后，Yan等人[14]利用VG方法构建流量网络并提取网络特征用以区分流量状态.同时，Gao等人[15]也提出了多尺度有限穿透水平可见性图，并证明了该方法是一种从网络角度分析非线性时间序列的有效方法.

将序列信息构建成网络的方式除了能更好的建模用户自身的行为特性外，还能找出信息传递过程中发挥重要作用的潜在因素.这种通过对转换后的网络进行分析挖掘的研究在信息论的基础理论[16]，音乐理论[17]，社会和信息网络[18]等工作中均有所涉及.最近Lynn等人[19]研究发现，序列数据转成的信息网络模块度越高，人们就越容易接收该信息.这个结果意味着用户的行为一方面取决于自身的兴趣爱好，另一方面也与接收到的好友信息有关，例如用户在网站上浏览好友上传信息的过程就可视为用户在接收好友对其的影响.好友的信息网络模块度越高，用户对其印象就越深，从而越有可能做出和该好友类似的行为，比如去该好友去过餐馆等.

此外，虽然目前对用户的行为预测提出了很多方法，但是数据稀疏性问题一直未能得到改善.与主动采样的交通数据集不同，从大多数网站上获得的用户移动数据是非常稀疏的[20].例如在Yelp数据集中，用户会出于习惯或对个人隐私的考虑而只存留少量的在线数据，如多次访问餐馆却只写一次评论.对移动预测模型来说，在这种稀疏数据集上，模型很难捕获到用户的有效特征.从而在一些优秀的预测模型上也只能得到一个较低的预测精度.

为了缓解数据稀疏问题，本文结合上述工作，提出了一种融合信息网络结构的数据增强行为预测算法.针对用户当前的某一个行为，我们通过用户好友的行为信息网络来度量用户接收该好友信息的程度，并将好友的行为数据嵌入到用户数据中，从而实现对用户进行数据增强.据我们所知，目前还未有研究从用户行为网络传递效率的角度出发来对用户的行为进行预测.实验结果显示，本文提出的方法在Yelp数据集上可以使算法性能得到极大的提升，从而为解决稀疏数据集上行为预测性能低的问题提供了新的可行方法.

2 RNN预测模型

Recurrent Neural Network(RNN)[21]是一类具有循环结构和内部记忆单元的神经网络模型，它可以有效捕获序列信息特征，在推荐系统、移动预测等诸多领域都取得了成功[22-26].本小节将介绍 RNN 模型及其变种的工作原理.

2.1 模型描述

RNN模型种类繁多，其中应用较为广泛的是Long Short-Term Memory(LSTM)[27]和 Gated Recurrent Unit(GRU)[28].LSTM 由一个记忆单元和3个控制门组成，这些组件可以用来保持和更新循环单元的状态.根据当前输入和前一个循环单元的状态，LSTM 首先使用输入门，遗忘门以及候选记忆单元来更新记忆单元.然后，LSTM 根据记忆单元以及输出门来得到当前单元的状态.GRU 是 LSTM 的一个流行变种，它将遗忘门和输入门用一个重置门来替代.GRU 的更新公式如下：

ft=σ(Wfxxt+Wfhht-1+bf)

(1)

rt=σ(Wrxxt+Wrhht-1+br)

(2)

ct=tanh(Wcxxt+rt⊙(Wchht-1)+bc)

(3)

ht=(1-ft)⊙ct+ft⊙ht-1

(4)

其中xt是时刻t时的输入，ht-1是 GRU 单元前一次的输出，b是不同部分中的偏执向量，⊙ 元素按位乘法，ft是更新权重，rt是重置门，ct是候选状态，ht是输出结果.根据 Chung等人[29]的描述，GRU 在多分类任务中使用较少的计算量达到了和 LSTM 相似的性能.

2.2 预测性能指标

在本实验中，使用了 3 个公认的评估指标来评估模型的预测性能：MeanAccuracy@N，MeanRecall@N和MeanF1@N.这些指标被广泛应用于评估模型的预测性能[30-32].假设测试集中的用户行为集合为G，则预测性能指标计算公式如下：

1)MeanAccuracy@N： 表示测试集中被预测正确的地点所占总地点数的比例.定义为公式(5)：

(5)

其中isCorrect(g，Top@N) 函数用来判断用户访问的位置g是否包含在Top@N预测列表里面，如果是，那么返回 1，否则返回 0.

2)MeanRecall@N： 表示用户数据中预测正确的活动占用户总活动的比例.记Gi为用户i的行为，那么MeanRecall@N可以表示为公式(6)：

(6)

3)MeanF1@N： 是预测性能的综合度量.通过计算MeanPrecision@N[公式(7)]，MeanF1@N可以表示为公式(8)：

(7)

(8)

一般来说，预测精度越高，代表着模型的预测性能越好.

3 融合信息网络结构的数据增强算法

现实生活中，用户出于习惯或隐私考虑可能不会向平台提供所有行为记录，这可能会使数据集更加的稀疏，同时让基于RNN 的模型学习到错误的潜在表达而导致性能下降.为了缓解该问题，本文提出了一种融合信息网络结构的数据增强行为预测算法.该算法从用户行为信息网络结构的角度出发，挑选出用户朋友中信息传递效率高的朋友，并从中抽取有用信息，以增强用户的行为数据.我们的算法包含3个步骤，如图1所示.

图1 融合行为信息网络结构的数据增强行为预测算法Fig.1 Data enhanced behavior prediction algorithm based on information network structure

3.1 问题定义

3.2 用户行为信息网络的构建

用户行为信息网络可以挖掘信息传递过程中的潜在因素.本文根据水平可视化图 HVG 方法[13，34]来构建用户的行为信息网络.这样我们不仅考虑了用户行为的潜在时间序列特征，还能将用户的偏好编码在网络连边权重中.例如，如果一个用户的活动事件分布是随机分布的，则构建出来的行为信息网络为随机网络，同样的，如果用户的活动事件服从幂律分布，那么所构建的网络为无标度网络.

本文采用的可视性规则如图2所示，具体地，图2(a)展示的是移动行为序列及其评分，其中{vt1，vt2，…，vtq}代表用户就餐行为的活动序列，{Rt1，Rt2，…，Rtq}代表用户在对应时刻给的评分值，直方图的高度代表该用户在Yelp上对该餐馆所给出的评分，范围是1～5.当条形柱可以相互“看见”时，它们就建立了一条连边.举例来说，如果在 [ta，tb] 内的所有点vti满足Rta>Rti&Rtb>Rti(ta

图2 用户行为信息网络的构建Fig.2 Construction of user behavior information network

3.3 网络传递效率的计算

最近的研究[19]发现，人类接收信息的方式是离散的，比如阅读一段文本，或是听一首歌.这些序列信息可以抽象为节点和边组成的网络，从而编码了用户信息的结构.该行为信息网络决定了人们彼此之间的交互方式.此外，人们感知信息的效率主要依赖于行为信息网络的拓扑结构，而非序列所产生的信息.模块化程度高的信息代表该信息传播效率高，从而更容易被人们所接收.

在现实世界中，用户的移动行为一方面取决于用户自己的兴趣爱好，另一方面则会受到其朋友的影响[40].以Yelp网站的用户为例，人们可能会在Yelp平台上浏览好友访问餐馆的数据，该过程可以被视作是接收信息的过程.如果好友的历史餐馆访问信息在用户行为信息网络中以高模块度的结构呈现，那么该用户会更容易接受此好友的信息，这也意味着该用户更容易受到此好友的影响.为此，本文在上一小节构建用户行为信息网络的基础上，进一步计算了用户好友的模块度，用以衡量用户对每个好友的信息接收程度.网络模块度的计算方式见公式(9)：

(9)

其中E表示了用户行为信息网络中边的数量.Aij表示节点i到节点j的连边权重.ki表示节点i的度值，kj表示节点j的度值，ci代表节点i所属的社团.1[ci=cj]代表了指示函数，当ci=cj时，返回为1，否则为0.

3.4 用户数据增强算法

用户的社交关系中包含了大量的用户个人信息，甚至在社交平台上，使用少量朋友在社交网络上发表的内容就可以预测用户未来发表的言论[41].然而如何高效地提取社交朋友数据一直是个难题.为此，本文设计了一种数据增强算法，利用用户的社交关系，以用户朋友的信息传递效率为采样概率，对用户朋友数据进行采样，用以增强用户数据，从而使得模型的预测性能进一步提升.具体地，假设需要填充用户在时间段 [t1，t2] 内的行为数据，我们选择用户朋友的模块度P作为选择概率选取出一个朋友，然后将该朋友在 [t1，t2] 内的行为数据填充到用户数据中.为了使数据量更为充足，在处理时首先对用户的朋友进行了预筛选，确保选取的朋友在 [t1，t2] 内是存在行为数据的.下面的算法伪代码选择了uj作为数据采集对象，填充目标用户u1在 [t1，t2] 内的缺失行为数据.

算法1.数据采集算法

u1的朋友集合F

1.初始化概率累加值L←0

2.foruj∈Fdo：

4.F1.add(uj)

5.L←L+Puj

6. end

7.end

8.生成随机数W∈(0，L]

9.初始化累加值Q←0

10.foruj∈F1do

11.Q←Q+Puj

12. ifW≤Qdo

14. end

15.end

4 实验和结果

4.1 数据集描述

本文将公开数据集Yelp作为实验对象.Yelp数据集主要包含两部分数据：餐馆信息和用户信息.其中餐厅信息包括餐厅所在的经纬度、所属城市、营业时间、总体评分等信息.用户信息包括用户的历史行为序列、兴趣爱好、社交关系等内容.研究用户移动行为需要知道用户的位置信息，Yelp数据集有两部分数据包含位置信息，即签到信息(check-ins) 和评论信息(reviews).由于签到行为是最近几年才开始流行的，所以信息的总体数据量偏少.幸运的是，用户的评论信息中也包含了地理信息，因此本文选择使用评论信息来代替签到信息.考虑到用户就餐行为较少发生在城市间，本文只关注城市范围内的用户行为，在实验中，选取了用户数量最多的两个城市(Las Vegas 和 Toronto)，这两个城市的数据总结如表1所示，两个城市的用户评论数分布如图3所示，其中图3(a)显示了Las Vegas的评论数分布，图3(b)显示了Toronto的评论数分布.从图中我们可以发现这两个城市的用户评论数均呈现幂律分布.这意味着在Yelp数据集上，用户的就餐评论行为是非常稀疏的，大部分用户的评论数量少于10条.

图3 用户的评论数分布Fig.3 Distribution of users′ reviews

表1 数据集总结Table 1 Dataset summary

此外，Yelp 原始数据集的时间跨度有 10 年之久，远远大于部分餐馆的存在历史.因此为了确保数据的有效性，本文只取了数据量最大的两年(2016年1月～2018年1月)数据来进行实验.过少的用户数据量无论是在训练还是在测试中都会对模型的结果造成较大的影响.因此本文只考虑那些相对活跃的用户(评论记录大于15条，朋友数量大于0个).值得注意的是，由于数据的异质特性，大部分用户在筛选后的行为分布还是稀疏的.筛选之后，Las Vegas数据集包含来自7，031家餐馆上的1，592个用户的62，976条评论数据以及相应的用户社交网络.Toronto数据集包含来自4，152家餐馆上的881个用户的34，122条评论数据以及相应的用户社交网络.

4.2 实验设置

为了显示本文提出方法的通用性能，将采样得到的数据集与原始数据集在基准预测模型上进行对比实验.所有基准模型的参数均和原始论文中的一致.此外，数据集上每个用户的前80%的行为历史被用作训练，剩余20%的数据被用作测试.基准模型如下：

1)RNN[21]：RNN是一种高效的序列预测方法，已经被广泛地应用于词嵌入和广告点击预测任务.

2)GRU[28]：GRU是RNN模型的一种变种模型，它配备了两个门用于控制信息流的流动.

3)LSTM[27]：LSTM是RNN模型的另一种变种模型，它在处理序列数据方面表现出了强大的能力，能够学习记忆长期的特征.

4)DEEPMOVE[20]：该方法利用注意力机制从用户的行为历史中学习用户的长期偏好，然后使用RNN来学习用户的短期偏好.

4.3 实验结果与分析

表2和表3分别显示了我们提出的采样算法和4个基准模型方法结合后在Las Vegas和Toronto数据集上的性能.从表中可以明显看到在对数据集进行数据增强之后，所有模型的预测性能都得到了大幅的提升.特别地，在Las Vegas数据集上，GRU模型的预测性能提升了约43倍.这意味着仅仅将原先有的数据集进行数据增强，即可使一些表现不好的模型重新得到应用.这有助于提升大部分模型的兼容性，降低数据采集的成本.此外，还观察到Toronto数据集的预测效果不如Las Vegas数据集，这是由于Toronto的有效用户数量仅为Las Vegas的一半，在进行用户数据采集的时候，获取的朋友信息相对较少，从而导致预测性能的下降.

表2 Las Vegas数据集上的预测结果Table 2 Prediction results on the Las Vegas city dataset

表3 Toronto数据集上的预测结果Table 3 Prediction results on the Toronto city dataset

4.4 参数敏感性分析

图4显示了在Las Vegas和Toronto数据集上模型性能与采样次数的关系，这可以为提供有关参数选择的启迪.从图4(a)中可以发现模型的预测性能随着采样次数的增加而逐渐呈现下降趋势，这在图4(b)中也有所体现.这说明采样过多的朋友数据会引入太多的噪声，从而导致深度模型无法有效的学习到用户本身的特征，最终影响模型的预测性能.此外，过多的采样在增加数据量的同时会导致计算量成倍的增加，因此需要在数据量和计算效率上做一定的权衡.通常来说，采样一次即可得到近似最优的采样效果.

图4 采样次数对预测性能的影响Fig.4 Influence of sampling number on prediction performance

5 结 语

本文提出了一种融合信息网络结构的数据增强行为预测算法，该方法包括构建用户行为信息网络，度量网络信息传递效率以及用户数据增强3个步骤.实验结果表明，本文提出的方法能够大幅提升基于RNN的序列预测模型的性能，解决了这些模型因数据稀疏而导致性能下降的问题.除此之外，本文提出的方法参数少，能快速的应用到各类预测模型中去，显示出了不错的扩展性与兼容性.当前研究中各类基于RNN的预测方法层出不穷，我们的方法能让这些RNN预测模型应用到更小更稀疏的数据集中，使其能够在改动极小的情况下，提升预测算法的性能.在未来的工作中，将在本文提出方法的基础上研究如何将时间因素以及空间因素融入到采样算法中，使得用户数据的增强更为充分.