移动轨迹挖掘算法设计与系统实现

高瑞+周彩兰+朱荣

摘 要： 为了提高有效地识别不同交通方式的精确度，根据采取的交通方式GPS定位轨迹特征，构建一套适用于识别不同交通方式的精确度预测优化算法模型，研究内容包括轨迹转换点分段、移动轨迹转预测计算、结果精度分析三个部分。采用对交通堵塞及多种交通方式的情况提出转换点分段方法的算法，挖掘用户的移动行为，将GPS原始轨迹划分成为交通方式单一的子轨迹段，有效地识别不同交通方式，达到的效果较为理想。实验结果表明，统一时间的分段方法与转换点的识别方法相比，统一时间分段方法的整体精确度要低于转换点识別方法，高级特征的精确度均高于基本特征的精确度。

关键词： 移动轨迹； 挖掘算法； 交通堵塞； GPS定位

中图分类号： TN967.1?34； TP391 文献标识码： A 文章编号： 1004?373X（2017）01?0134?03

Abstract： In order to improve the identification accuracy of different transportation modes， an accuracy forecasting optimization algorithm model suitable for the identification of different transportation modes was constructed according to the traffic mode to locate the GPS trace features. The segmentation of track transition point， moving track prediction and calculation， and result accuracy analysis are studied. The algorithm of using the transition point segmentation method to deal with the traffic jam and various transportation modes is adopted to mine the user movement behavior， and divide the GPS original trajectory into the sub?trajectory with single transportation mode， which can identify different transportation modes effectively， and achieve the satisfied effect. The experimental results show that the overall accuracy of the transition point identification method is higher than that of the unified time segmentation method， and the accuracy of the advanced feature is higher than that of the basic feature.

Keywords： mobile trajectory； mining algorithm； traffic jam； GPS location

0 引 言

随着GPS定位技术、无线通信技术和电子技术的发展，使得人们可以对移动对象如乘坐不同交通方式、车辆等进行跟踪定位，与移动对象管理密切相关的是移动对象的跟踪、定位、记录、查询等，用户移动模式的有效支持才能使这些功能有效的实现。挖掘用户的移动模式可以为移动对象管理服务，还可以在交通管理、安全和旅游等基于位置的服务中具有非常广泛的应用前景。

在定位技术中，GPS定位是精度最高的定位技术之一，目前GPS定位研究最多的是通过内置客户端获得用户的连续轨迹。本文通过转换点分段方法的算法，对交通堵塞及多种交通方式，将GPS原始轨迹划分成为交通方式单一的子轨迹段，有效地识别不同交通方式，达到的效果较为理想。

1 相关定义

为了方便讨论，首先引进如下符号说明，移动对象的移动产生一个连续的运动轨迹，该运动轨迹可以由位置、时间描述。表示轨迹，表示数据点，表示纬度，表示经度，表示时间。在轨迹的边上标记一个连续的自然数列，移动对象的轨迹可描述为：

GPS轨迹定义：GPS轨迹是由一系列随着时间变化，轨迹位置也在空间上发生变化的许多数据点形成的，采用经纬度的形式表示位置信息。由于对象的移动行为往往是一个周而复始的过程，所以上述轨迹是一个有向标记图，每个连续的运动轨迹对应一个有向标记图。

转换点定义：转换点是指子轨迹之间的某一特定范围内停留时间在速度保持较低状态下超过某一阈值的数据点。

子轨迹定义：子轨迹是指经过转换点分段之后的一段轨迹，由许多数据点形成，并且这些数据点是连续的、相对的和紧密的，且每段子轨迹代表一种交通方式，不同的子轨迹中相邻数据点间的间隔是不同的。如轨迹子轨迹其中

2 转换点的轨迹

2.1 转换点的描述

通常情况下，人们在转换交通方式前一个时间段一般保持着较低速度在运动，利用转换点将GPS的轨迹进行不同交通方式的分段，每一段交通方式称为子轨迹，每一段子轨迹都只允许有一种交通工具。如图1所示，用户轨迹由12个数据点构成，点为转换点，转化点将轨迹分为三段子轨迹。

2.2 正常情况下的转换点

由于交通堵塞或间断性停车使得转换点的识别出现两种情况，即交通堵塞或交通正常。正常是指未发生交通堵塞情况，只有在换乘另一种交通工具时，人才发生停顿。速度小于某一阈值的点要通过GPS轨迹中每个数据点的速度才能计算出，如图2所示。

2.3 低速点的出现

多个低速点会出现在交通堵塞导致不间断的停顿的状况中，这些低速点把交通方式相同的子轨迹段划分为更小的子轨迹。人在坐公交车和步行的过程中，必然会出现多个低速度点，如点一种交通方式下的子轨迹被它们又分成了好几段的子轨迹，如具体见图3。

3 移动轨迹转换算法

算法1描述了如何识别转换点的具體步骤，其中分别表示子轨迹段的长度、时间和平均速度。

4 算法分析

本文从三个方面对算法进行分析，第一是对每段的子轨迹抽取与速度相关的基本特征，并抽取与速度无关的高级特征，然后进行训练；第二是当处理一段GPS原始轨迹时，先计算轨迹中每一个点的速度，然后抽取对应的每一个子轨迹段上的基本特征，并抽取对应的每一个子轨迹段上的高级特征，推断模型的输入数据就是这些特征；第三是对每一个子轨迹段的交通方式进行识别，识别的根据由推断模型的这些特征确定。

5 实验结果与分析

为了验证转换点分段交通识别方法，记录40个被测试人员在160天的上班路线，每个试验者都携带一个带有GPS功能的设备记录自己的位置信息，以随机抽样的方法从每个试验者的GPS轨迹中选择一部分数据作为训练集，其余作为测试集，对方法进行验证。为了比较转换点和统一时间两种不同的分段方法，分别选择相同的几组数据集进行反复实验。

图4为三组不同数据点转换点的分段方法曲线图，从图4可以看出，三组数据点在转换点的分段方法曲线图上的速度均为2.2 m/s时，分段精确度达到最高，三组数据点250，1 540，3 520对应的分段精确度分别为87%，86%，90%。

图5为三组不同数据点统一时间的分段方法曲线图，由图5可以看出，统一时间的识别方法三组数据点均在时间为155 s时达到最高的分段精确度，三组数据点250，1 540，3 520对应的分段精确度分别为30%，38%，51%，三组数据点整体精确度较小，均低于60%，效果较差。与转换点的识别方法相比，转换点的识别方法的整体精确度要高于统一时间的分段方法。

6 精确度比较

本试验分别随机抽取了所有数据中的6组数据，为了确保试验的准确性，对抽取的每组数据特征进行多次的反复实验，比较不同特征在识别交通方式时精确度的差别。

基本特征与高级特征精确度比较如图6所示，从图6可以看出，6组数据高级特征精确度均高于基本特征的精确度，其中第一组数据与第六组数据基本特征与高级特征精确度差距较小；第二组数据与第五组数据基本特征与高级特征精确度差距较大，由于基本特征受速度影响，导致识别精确度不理想。在实际应用中，利用高级特征进行识别比利用基本特征识别精确度更高，更接近实际。

7 结 论

本文对交通堵塞及多种交通方式的情况提出转换点分段方法的算法，将GPS原始轨迹划分成为交通方式单一的子轨迹段，有效地识别不同交通方式，达到的效果较为理想。对比转换点的识别方法与统一时间的分段方法，前者的整体精确度要高于后者，高级特征精确度均高于基本特征的精确度。

参考文献

[1] 熊妍，罗泽，阎保平.GPS位置历史挖掘和移动轨迹异常检测系统的设计与实现[J].计算机应用研究，2013，30（9）：2704?2707.

[2] 彭茗菁，马传香，李伟亮.基于MAP/REDUCE的移动目标连续轨迹模式挖掘的研究[J].物联网技术，2014，4（10）：59?61.

[3] 刘雨露，方刚.基于二进制的挖掘算法在移动计算中的应用[J].计算机工程与设计，2009，30（14）：3319?3322.

[4] 吴信才，刘少雄.基于邻接关系的空间数据挖掘[J].计算机工程，2002，28（7）：89?91.

[5] 李国徽，程远国.传感器网络中频繁移动模式挖掘算法研究[J].小型微型计算机系统，2008，29（6）：1015?1020.

[6] 贺然，张钢，刘春凤，等.车载网络中基于移动轨迹预测的快速邻居发现算法[J].计算机应用研究，2015，32（9）：2737?2742.

[7] 赵德伟，高江锦，徐正巧.基于K?means算法的Web日志挖掘在移动学习中的实现[J].电脑编程技巧与维护，2012（16）：92?94.