基于并行模式挖掘和路径匹配的用户位置预测

许贤泽, 谭盛煌, 刘 静, 施 元

(武汉大学 电子信息学院， 湖北 武汉 430072)

随着移动互联网的快速发展，智能手机已成为大众的必备工具.数据显示，2017年1～7月，我国智能手机的出货量达2.66亿部，智能手机用户规模也已达到6.55亿人，这些移动设备每天产生海量的位置数据，通过这些位置数据对移动用户的轨迹预测已成为近年来的研究热点之一.准确的轨迹预测在导航[1]、疾病预防[2]和城市规划[3-4]等诸多领域有着广泛应用.

当前轨迹预测方法主要分为以下三种:

1) 基于时间序列模型的位置预测方法[5].这类方法是通过对原有时间序列构建线性或非线性数学模型，该方法假设移动对象的运动轨迹较为平稳，移动速度、方向不会产生较大变化.在真实的城市交通中路况较为复杂，移动用户并不能产生时间序列模型所要求的平稳轨迹.

2) 基于机器学习的位置预测方法.该方法在目前位置预测中应用最为广泛，主要有Markov模型[6]、卡尔曼滤波模型[7]、贝叶斯模型[8]，其中以Markov模型应用最多.Markov模型主要是根据历史数据构建状态转移矩阵，当出现新用户或出现数据缺失时，位置预测准确性较低.

3) 基于频繁模式挖掘FP-GROWTH算法挖掘运动对象运动模式的方法[9].该方法从历史轨迹数据集中挖掘频繁轨迹模式，然后与当前路径进行匹配实现位置预测.由于传统的FP-GROWTH算法复杂度较高，无法处理大量的历史轨迹数据集.本文采用了一种并行FP-GROWTH算法与相斥度计算结合展开移动用户轨迹预测的方法，将传统的FP-GROWTH算法分布到Spark并行计算框架上，从而解决了大量数据的挖掘，同时改进了相似度计算方法，对缺失轨迹有更好的适用性.

1 问题描述

现有一移动用户轨迹数据集和某移动用户的当前轨迹，预测该用户的短期轨迹.设数据集X={X1,X2,…,Xw}其中:Xi=(ui,ti,pi)，i=1,2,…,w.ui是用户ID，ti是用户在该位置的时间，pi为用户所在位置的经纬度.假设有一个移动用户的位置数据集，该数据集是一个时间序列，包含了用户在一定时间段内的位置数据.首先对位置数据进行数据预处理，然后提取出用户的轨迹集Tui={(ti,li),i=1,2,…,x}，时间序列tui=t1,t2,…,tx，位置序列Lui=l1,l2,…,lx，其中ui表示任意移动用户.移动用户的位置预测问题可以描述如下:设ui是某一研究用户，已知该用户的移动轨迹集为T，预测出该用户下一步地点lx+1.

2 基于Spark的FP-GROWTH算法

使用传统的FP-GROWTH算法需要将所有的数据加载到单机内存，随着数据量的增大，FP-GROWHT算法构建的FP-Tree的广度、深度都会增大[10]，同时递归次数增加，导致挖掘效率变低.因此需要对原始的FP-GROWTH算法进行改进，利用分布式集群实现频繁项挖掘[11].

2.1 基本概念

设A=(a1,a2,…,an)为一个集合，集合A中的元素称为项，集合A称为项集A或事务A.在本文中，集合A表示一条轨迹，ai表示轨迹A上的采样点.

1) 支持度:事务A在事务集合中出现的次数与事务集合的大小的比值.

2)k-项集:长度为k的项集.

3) 1-项集的条件模式基:选择其中一个1-项集ai，对FP-Tree中每个ai节点向上回溯至根节点所得到的路径的集合，条件模式基可看成一个新的事务集合.

2.2 基于Spark的FP-GROWTH算法

首先对数据集进行划分，将分割数据集分布到集群的各个节点上分别进行频繁项集挖掘，最终将挖掘结果聚合到主节点上.

算法的实现主要包括四个部分:

1) 将数据集部署到分布式文件系统(Hadoop distributed file system，HDFS)上，扫描HDFS，并行计算各1-项集的支持度，将1-项集支持度计算结果聚合到主节点上，并根据支持度排序[11].

2) 修剪上述1-项集集合，删除支持度小于所设阈值的1-项集，记该1-项集集合为H_list.

3) 依据H_list对数据集进行划分，由于条件模式基大小并不一致，为了在分布式集群上提高计算速度，需要进行负载均衡处理[11].对于H_list中的一个1-项集H_list，i越小，H_list[i]所对应的条件模式基所含事务更少，事务长度更短，因此使用FP-GROWTH算法挖掘频繁项时速度更高.对条件模式基的频繁项集挖掘过程是一个对树的递归操作，因此本文采用H_list[i]的序号与支持度的乘积估算条件模式基的负载.以负载为权重将划分后的数据集分配到各个节点上.

4) 在各个节点上进行频繁模式挖掘[11]，最后将结果聚合到主节点上.

3 相斥度计算

本文针对基于同位序轨迹点欧式距离的轨迹相似度算法的不足[12]，提出一种基于计算当前点到历史轨迹距离加权和的相斥度(即两条轨迹的相离程度)计算方法.

3.1 点到轨迹的距离

定义1点到轨迹的距离:已知某条轨迹数据序列l={p1,p2,…,pm}和轨迹点qi，轨迹点qi到轨迹l的距离定义如下:

D(qi,l)=min(distance(qi,pjpj+1)).

其中distance(qi,pjpj+1)表示轨迹点qi到线段pjpj+1的距离，且1≤j≤m-1.

设存在轨迹序列l1={p1,p2,…,pm}和l2={q1,q2,…,qn}，计算轨迹l2的上各点到轨迹l1的最小距离.计算l2上各轨迹点到轨迹序列l1最短距离的过程中，精确求解需要计算qi到l2各轨迹段的距离.考虑到运动轨迹的渐变性，在计算上进行一定改进.

通过数据预处理后，若轨迹l1与l2相似，l2上起始点q1到l1各轨迹段距离先减小后增大，取其中极小值为q1点到轨迹l1最小值.若求解得l2上一轨迹点qi到l1的距离为qi到轨迹段(pj,pj+1)的距离，计算l2中qi的下一个轨迹点qi+1到轨迹l1的距离，计算过程如下.

尝试计算qi+1到(pk,pp+1),j≤k

3.2 轨迹相斥度

在用于预测的相似路径中，越靠近当前轨迹末端的点与预测点位拥有更高的相关性，对最终的预测结果影响越大[13]，因此对这些轨迹点赋予更高的权重，对相斥度作如下定义.

定义2轨迹相斥度:已知某条轨迹数据序列l1={p1,p2,…,pm}和轨迹数据序列l2={q1,q2,…,qn}，l1，l2轨迹相斥度定义为

其中wi表示轨迹点qi的权重.在相斥度计算中，设定一相斥度阈值threashold，当计算过程中相斥度大于threashold，认为l1和l2相斥，终止计算.

采用与被预测路径相斥度最低的频繁轨迹与被预测路径匹配，完成用户位置预测.

4 实验结果及算法性能分析

4.1 实验数据及其预处理

本文选用了由微软亚洲研究院发布的GeoLife GPS Trajectories数据集，该数据集由智能手机和其他包含有GPS的设备记录而成，从2007年4月到2012年8月期间182个用户的轨迹数据，包括经度、纬度和海拔.该数据集总共包含17 621条轨迹数据，记录总时长超过48 000 h，总距离超过120万km.

由于采样间隔比较密集，测量误差对相邻两点之间的相对位置影响很大，因此本文根据原数据集的特点，对原始数据集进行采样，采样频率为10.结合百度地图对数据进行基于POI点的停留点检测，用折中方法分割轨迹[14]，得到便于模式挖掘和相斥度计算的短序列.

式(7)中：ui为各面单元的轴向速度;为截面轴向平均速度;Ai为各面单元的面积。为便于与试验结果相对比，对0.15 m <0.45 m和0.15 m

4.2 实验结果与分析

4.2.1 Spark和MapReduce运行效率对比

为验证基于Spark的FP-GROWTH 算法在大量数据下的可用性，本实验选取了不同的数据集，分别在5个节点的MapReduce以及Spark运算框架上以FP-GROWTH算法进行频繁项挖掘，比较两种运算框架的运算效率.

FP-GROWTH算法计算内存开销较大，对于大型数据集，单机受内存限制无法运行.实验选取不同规模的数据集，通过合理的数据集分割，可以在不影响模式挖掘效果的前提下进行分布式运算[11].分别在Spark和MapReduce并行计算框架上进行频繁模式挖掘，实验结果如图1所示.

图1 Spark和MapReduce运算框架下运行时间对比

由图1可知，Spark运算框架相比MapReduce在不同的数据集大小下，运行时间更短，MapReduce框架比Spark运行时间增长更快.这是因为MapReduce从硬盘读写数据，计算时在内存中进行存储和运算.Spark直接基于内存处理，避免了与硬盘的IO传输.因此Spark运算框架上的FP-GROWTH算法拥有更高的运算效率.

4.2.2 轨迹预测算法性能对比

为验证模型的预测准确性，对马尔可夫模型、卡尔曼滤波模型及本文提出的基于模式挖掘与路径匹配的方法进行对比.将数据集随机分成20份，其中一份作为测试数据集用于轨迹预测，另外19份用于训练模型，每个实验采用交叉验证的方式进行20次，取平均结果作为最终预测值.

定义3预测精度[13]:在轨迹预测过程中，预测结果正确的概率.例如，对于n个需要预测位置，设定一个预测误差阈值，预测误差在阈值以内认为预测正确，有t个位置预测正确，则该预测结果的预测精度为Pa=t/n.

本文采用预测精度作为轨迹预测准确性的评价标准.分别采用马尔可夫模型、卡尔曼滤波模型以及本文的相斥度预测算法进行预测精度对比.

实验采用马尔可夫模型、卡尔曼滤波模型以及本文的相斥度预测算法进行不同长度轨迹的单步位置预测，即预测用户的下一个感兴趣的位置.图2为3种预测方法对不同长度轨迹单步预测结果.横轴表示当前轨迹长度，纵轴表示预测精度.

图2 不同长度轨迹单步位置预测精度对比

从图2可以看出，随着轨迹长度增加，三种预测方法预测精度保持上升，在轨迹长度为5时逐渐平稳.保持平稳之后，基于相斥度的轨迹预测算法相比于马尔可夫模型和卡尔曼滤波模型预测精度分别提升6.93%和6.98%.

在进行位置预测时，多步预测也是检验模型预测性能的指标之一，多步预测即连续预测多个点的位置.本文根据不同长度轨迹的单步预测实验的结果，设置待预测轨迹长度为5.采用三种方法对测试集中6个连续位置进行预测，计算不同位置平均预测精度，如图3所示.

图3 不同点位的预测精度对比

从图3可以看出，三种方法在步长增加时，预测精度有明显下降.相比于马尔可夫模型和卡尔曼滤波模型，本文使用的相斥度预测算法对不同步长的预测精度在各点平均预测精度提升分别为7.03%和7.35%.

从上面两个实验可以看出，本文采用的相斥度预测算法预测精度优于马尔可夫模型和卡尔曼滤波模型.原因在于马尔可夫模型是概率统计模型，对于运动状态不确定性较高的对象预测精度不高.卡尔曼滤波主要适用于线性离散系统，对轨迹点数据缺失情况适应性不佳.

5 结 论

1) 本文提出了一种基于并行模式挖掘和路径匹配的移动用户位置预测方法.对FP-GROWTH算法作了并行化处理，实现了对大量用户的移动模式提取.采用基于相斥度的轨迹预测算法进行用户位置预测，并与马尔可夫模型和卡尔曼滤波模型进行比较分析.

2) 使用分布式平台可以完成大规模的模式挖掘，且Spark平台相比MapReduce计算效率更高.

3) 相比于马尔可夫模型和卡尔曼滤波模型，相斥度预测算法在单步预测和多步预测中预测更为精准.