康瑞部落

在大数据时代，位置数据成为各方都亟待挖掘的数据宝藏，比如在城市交通基建规划、商业选址、线下广告等场景中，都是以位置数据为重要基础。但在此过程中，隐私问题一直未得到有效解决，如何在保护原始数据不被泄露同时，更好地服务于各种城市应用呢？

本文将介绍南洋理工大学与SAP联合在IJCAI 2018上发表的论文《A Non-Parametric Generative Model for Human Trajectories》，文章通过真实轨迹学习城市人群的出行分布来生成轨迹，生成轨迹可以代替包含用户隐私信息的真实轨迹，来达到相近数据分析、上层业务建设的效果，避免位置信息外泄。文章有效地学习了轨迹的位置序列Embedding，进而，通过对抗式生成网络(GAN)来学习轨迹分布并生成模拟轨迹。

一、问题背景

想要建模城市中的人群移动特性是很有挑战的：1）轨迹状态空间很大；2）轨迹具有很强的独一无二性，很难找到两个轨迹完全相同的人；3）人群的轨迹具有相似的隐式语义，比如上班、下班、旅游，需要用有效的表征刻画出这些相似的语义来；4）轨迹序列内的位置相关性与轨迹间的相关性难以显式定义。

图1 算法框架

为了解决上述挑战，论文首先将轨迹映射到空间网格中，转为矩阵，每个网格包含了轨迹的访问该网格时间与驻留该网格时长信息；然后，通过对抗式生成网络来学习上述矩阵化后的轨迹数据，并生成相似轨迹。实验验证了生成轨迹对个体轨迹特征、轨迹统计特征有较好的保留，并与真实轨迹难以区分。

二、问题定义

我们记一条轨迹Traj为经纬度时序序列

其中(x, y)_t表示轨迹在时刻经过坐标(x, y)。给定轨迹数据，问题定义为学习轨迹数据的分布函数，即p(Traj)。

在轨迹长度很大时，想要学出Traj的分布是非常困难的。作者认为，马尔科夫模型的有限阶依赖关系无法学习长轨迹的先后位置关联关系；而基于循环神经网络如LSTM的做法，由于也被发现在长序列生成中会出现偏离[1]，也不能很好适用于轨迹生成。

三、轨迹表征

这里介绍论文的轨迹表征方式。不同于往常用时间序列来表示轨迹（就如问题定义中介绍那样），作者从空间视角出发，将轨迹时间序列转化为矩阵形式。

具体来说，首先城市被划分为N₁×N₂的网格，并将输入轨迹Traj转为大小为N₁×N₂的矩阵M。M_i,j = (t, d)包含了计算轨迹与每个网格的两项信息，其中t, d分别为：轨迹进入该网格的时间，与轨迹在网格内停留的时间。例如，下图a的城市网格中，图b的轨迹在5:00出现在网格0，一个小时后进入网格3，然后经过两小时在8:00进入网格4直到9:00。图c是以一小时位精度的矩阵化的结果，以网格3对应位置，即为例M_1,0，由于轨迹在6:00开始进入网格3，所以，且在8:00离开，期间经过2小时，所以d = 2。

图 2 轨迹表征实例

上述方法还需考虑一种情况——轨迹多次访问某一个网格。论文的做法是将矩阵扩展为三维张量M_i,j,k = (t, d)∈ R² ，以记录轨迹第K次访问的时间与停留时长。

四、对抗式生成模型GAN及其训练

区别于需要人工设定目标分布形式的参数化分成模型，对抗式生成模型使用深度神经网络来学出目标分部形式，避免人工设定，来达到无参数化的目的。作者利用了对抗式生成模型的这一优势，来学习轨迹数据的分布。

作者直接采用了梯度较为稳定的WGAN-GP的框架进行模型训练。形式化来说，若给定真实轨迹数据，GAN同时学习用于生成轨迹的生成网络和用于辨别轨迹是否真实（而非人造）的辨别网络。和均采用卷积网络CNN来处理矩阵化的轨迹数据，以丰富轨迹局部特征的提取。训练的损失函数为

其中P_z是简单随机分布如均匀分布、高斯分布等；p_x^~通过真实数据与生成数据G(z)的凸组合得到。优化目标分为三项，A项为辨别人工轨迹的损失，B项为辨别真实轨迹的损失，C项是避免梯度异常的惩罚项，以表示惩罚权重。

注意不同于常规模型训练仅更新参数来缩小损失函数值，对抗式生成模型的训练过程会反复地通过先更新G来最大化辨别误差，以欺骗D；再更新D来最小化辨别误差，以破解G。详细过程可以参考GAN相关文献。

五、实验结果

1.实验设定

轨迹时序数据具有高维特点，直接验证生成轨迹的概率分布是否符合真实数据，在计算量上可行性较差。为此，作者选了四项统计量，通过验证统计量分布是否一致来验证轨迹分布是否一致，这里列出两项p(r, d)：p(r, t)，分别表示网格与停留时长的联合分布，和网格r与进入网格时间的联合分布。分布差的通过常用的琴森香农散度(JSD)来衡量：

2.准确度效果

实验将原始轨迹数据对半分成训练数据和测试数据，并在每一轮训练后生成轨迹。如下图所示，生成轨迹与训练数据、测试数据分别计算JSD值，分别以蓝、红表示。

图3 训练过程

3.生成轨迹语义真实性

作者同时对生成轨迹的语义进行分析，判断生成轨迹是否还原了真实轨迹的语义。这包含了两项验证：常访问位置真实度和相对语义真实度。

图4 常访问位置top50准确性

在常访问位置真实度验证中，作者分别用论文方法与马尔科夫方法生成了轨迹，并统计top50的常访问地，与真实top50常访问位置进行比较计算精确度。如上图所示，论文方法比马尔科夫方法更准确地反映了真实top50访问位置，并达到至少70%的精度。

在相对语义真实度验证中，作者采用了pair-wise轨迹语义距离的分布作为评价指标。首先作者采用了一种常用的轨迹语义距离公式：

然后对生成轨迹与真实轨迹分别提取1000个轨迹pair计算pair-wise距离，得到了生成轨迹与真实轨迹的语义距离样本集，并对比生成距离样本与真实距离样本的分布，下图展示了两组样本的各分位数对比情况，验证了生成轨迹在相对语义分布上与真实轨迹相似。

图5 相对语义距离分布的分位数对比

六、小结

本文主要介绍了一篇比较有代表性的，在已有轨迹城市生成人造轨迹的论文。在智慧城市建设中，这些人造轨迹在避免用户位置信息被泄露同时，可以为城市交通基建规划、商业选址、线下广告投等业务提供数据支撑。技术上，本论文在发表当时的创新的点在于对轨迹的矩阵化表征、和GAN的应用，将来会分享更多轨迹生成和城市流动性建模的相关研究或观点。