一种基于MapReduce的车辆轨迹提取方法

褚龙现 李文坚

摘要：针对从海量出租车GPS位置点数据中提取载客轨迹问题，在分析位置点数据存储结构的基础上，提出一种基于MapReduce的分布式处理算法，实现出租车载客轨迹的分布式提取。通过自定义联合键、分区和分组，有效利用MapReduce的二次排序功能实现按出租车标识提取载客轨迹。实验表明，提出的分布式算法较好地解决了海量数据的并行提取。

关键词：轨迹;MapReduce;分布式;出租车数据;载客

中图分类号：TP311     文献标识码：A

文章编号：1009-3044（2019）21-0001-02

开放科学（资源服务）标识码（OSID）：

Abstract： Aiming at the problem of extracting passenger trajectory from mass taxi GPS location data， a distributed processing algorithm based on MapReduce is proposed to realize the distributed extraction of taxi passenger trajectory on the basis of analyzing the storage structure of location data. By using self-defined union keys， partitions and groupings， the second sorting function of MapReduce is effectively used to extract passenger trajectories according to taxi identification. Experiments show that the proposed distributed algorithm solves the parallel extraction of massive data.

Key words： trajectory; MapReduce; distributed; taxi data; passenger

1 引言

随着GPS技术的不断发展和智能定位设备的广泛应用， 促使基于位置的信息服务迅猛发展，众多应用的普及积累了海量GSP位置数据[1-2]。目前，城市出租车基本都安装有GPS定位装置，每隔5s-10s采集一次位置数据[3]，包括位置点的经度、纬度、瞬时速度、载客状态、采集时间和车辆标识等信息。通过对海量轨迹点数据进行挖掘和分析，可以得出多种出行规律[4-6]，从而进一步研究路径规划[7]、路网匹配[8]、智能交通[9]和城市计算[10]等。对出租车轨迹数据进行挖掘的首要任务是从海量位置点数据中提取车辆的行程，一方面要考虑借助大数据处理技术进行分布式计算，另一方面要考虑车辆行程的划分。

由于出租车位置点数据中包括空车和载客两种不同状态，所以轨迹可以划分为空车轨迹和载客轨迹。本文主要研究载客轨迹的提取，提出利用MapReduce分布式计算框架，有效解决海量位置点数据的并行处理。通过自定义联合键和分组，实现二次排序功能，分别设计Map端和Reduce端处理算法，最终完成载客轨迹分布式提取。

2 出租车轨迹

2.1 轨迹数据

定义1（GPS位置点）由GPS采集到的出租车位置信息，由车辆标识（id）、状态（status）、记录时间（t）、经度（lng）、纬度（lat）、速度（v）和方向（dir）等7个属性组成，表示为：

定义2（出租车轨迹） 在一定时间内，由于出租车位置变化采样得到的一个随时间顺序记录的GPS位置点集合，车辆标识为id的轨迹表示为：

定义3（载客轨迹） 出租车轨迹中，一段时间内车辆状态为1的GPS位置点集合，车辆标识为id的载客轨迹表示为：

2.2 载客轨迹提取

根据出租车运营状态的变化可以从出租车轨迹中提取载客轨迹，轨迹提取步骤如下：

1）获取指定出租车（标识为id）轨迹数据GP（id）;

2）逐一判断GP（id）包含的GPS位置点gpi，當出租车GPS位置点的运营状态由0变为1，即表示载客运营开始，记录一条新的载客轨迹;

3）载客运营期间，该状态保持为1，将GPS位置点添加到载客轨迹中;

4）当运营状态由1变为0，一次载客轨迹记录结束。算法流程如图1所示。

3 基于MapReduce的载客轨迹提取

3.1 MapReduce

MapReduce是Hadoop平台的分布式计算框架，通过MapReduce框架首先将大数据处理任务分解成多个单任务并在集群中并行执行，然后再把这些单任务的计算结果合并到指定节点计算最终结果[11]。MapReduce规范中分别使用map和reduce函数实现分布式处理，map函数负责对数据执行分区、排序和合并，reduce函数负责处理map提交的数据并计算最终结果。

3.2 并行处理算法

出租车位置点信息除了包含经纬度外，还包括采集时间，通过采集时间先后可以判断出租车的载客轨迹。相同出租车的轨迹需要按照时间排序，所以MapReduce既要按照出租车分组，同时同一出租车按照时间先后顺序排列GPS位置点。借助二次排序实现并行处理的框架如图2所示。

3.3 联合键

为了获取出租车的载客轨迹，首先需要把GPS数据按照出租车标识分组，同一辆出租车的GPS位置点再按照时间先后顺序排列。为了借助MapReduce框架的排序功能，在MapReduce中设计联合键CombineUnionKey，实现接口WritableComparable。该类包含gp.id和gp.t，主要用于实现对key的两次排序。

3.4 自定义分区

map的输出结果需要进行分区操作，MapReduce默认按照联合键进行分区。根据轨迹提取实际需要，map的结果按照出租车标识（联合键的第一排序属性）分区，自定义分区规则：

3.5 自定义比较和分组

map输出结果分区后，出租车标识相同的数据需要进行第二次比较，即按照记录时间升序排列。设计比较器，继承WritableComparator;在reduce阶段，出租车标识相同的数据应属于同一个组，为此构造比较器，实现将同一出租车的GPS轨迹数据放在一个value迭代器。

3.6 Map和Reduce处理

1）Mapper定义

继承Mapper，map函数中首先获取gp.id和gp.t，构造联合键CombineUnionKey对象;接着获取gp.lng、gp.lat和gp.status封装为position对象;最后输出的key为联合键CombineUnionKey，输出的value为自定义Position。

2）Reducer定义

继承Reducer，reduce函数中将gp.status为1的轨迹点的经纬度串联在一起，key为gp.id，value为经纬度按时间先后顺序连接。

4 实验与分析

在云平台搭建4个节点组成的Hadoop HA集群，每台节点CPU2.6GHZ，内存8G，操作系统为64位的CentOS6.6;Hadoop版本为2.6.4，Zookeeper版本为3.4.6。

实验数据使用北京市2012年11月9日出租车GPS位置点数据集，每条数据包含车辆标识、触发事件、运营状态、采集时间、经度、纬度、速度、方向和GPS工作状态等。数据示例：

实验结果如下表1所示。

实验结果表明，通过MapReduce的二次排序设计，有效地解决了海量GPS位置点数据中载客轨迹的提取问题。

5 结论

本文结合出租车GPS位置点数据特点，提出一种基于MapReduce的载客轨迹数据提取算法，设计了组合键并有效借助MapReduce的排序功能，完成二次排序，并实现了海量数据的分布式处理。实验验证了本文提出算法的有效性，下一步将如何提高分布式处理效率作为研究方向。

参考文献：

[1] 李婷，裴韬，袁烨城，等.人类活动轨迹的分类、模式和应用研究综述[J]. 地理科学进展， 2014，33（7）：93 8-948.

[2] Zheng Y . Trajectory Data Mining： An Overview[J]. ACM Transactions on Intelligent Systems and Technology， 2015， 6（3）：1-41.

[3] 吴家皋，夏轩，刘林峰. 基于MapReduce的轨迹压缩并行化方法[J]. 计算机应用， 2017（5）：1282-1286，1330.

[4] Jeung H， Man L Y， Jensen C S. Trajectory Pattern Mining[M]. Computing with Spatial Trajectories. 2011：330-339.

[5] Sanaullah I ， Quddus M ， Enoch M . Developing Travel Time Estimation Methods Using Sparse GPS Data[J]. Journal of Intelligent Transportation Systems， 2016，20（6）.

[6] 秦萧，甄峰，熊丽芳，等. 大数据时代城市时空间行为研究方法[J]. 地理科学进展，2013，32（9）：1352-1361.

[7] Yuan J， Zheng Y， Xie X， et al. T-Drive： Enhancing Driving Directions with Taxi Drivers' Intelligence[J]. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（1）：220-232.

[8] 段宗涛， 霍明生， 康军. 一种改进的轨迹地图匹配算法[J]. 测绘通报， 2018，494（05）：80-84.

[9] Yuan W，Deng P，Taleb T， et al. An Unlicensed Taxi Identification Model Based on Big Data Analysis[J]. IEEE Transactions on Intelligent Transportation Systems， 2016，17（6）： 1703–1713.

[10] Pan G， Qi G， Wu Z， et al. Land-Use Classification Using Taxi GPS Traces[J]. IEEE Transactions on Intelligent Transportation Systems， 2013，14（1）：113-123.

[11] Yang G . The Application of MapReduce in the Cloud Computing[C].International Symposium on Intelligence Information Processing & Trusted Computing. IEEE， 2011：154-156

【通聯编辑：梁书】