褚龍現(xiàn) 李文堅(jiān)

摘要：針對(duì)從海量出租車(chē)GPS位置點(diǎn)數(shù)據(jù)中提取載客軌跡問(wèn)題，在分析位置點(diǎn)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上，提出一種基于MapReduce的分布式處理算法，實(shí)現(xiàn)出租車(chē)載客軌跡的分布式提取。通過(guò)自定義聯(lián)合鍵、分區(qū)和分組，有效利用MapReduce的二次排序功能實(shí)現(xiàn)按出租車(chē)標(biāo)識(shí)提取載客軌跡。實(shí)驗(yàn)表明，提出的分布式算法較好地解決了海量數(shù)據(jù)的并行提取。

關(guān)鍵詞：軌跡;MapReduce;分布式;出租車(chē)數(shù)據(jù);載客

中圖分類(lèi)號(hào)：TP311? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）21-0001-02

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（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技術(shù)的不斷發(fā)展和智能定位設(shè)備的廣泛應(yīng)用， 促使基于位置的信息服務(wù)迅猛發(fā)展，眾多應(yīng)用的普及積累了海量GSP位置數(shù)據(jù)[1-2]。目前，城市出租車(chē)基本都安裝有GPS定位裝置，每隔5s-10s采集一次位置數(shù)據(jù)[3]，包括位置點(diǎn)的經(jīng)度、緯度、瞬時(shí)速度、載客狀態(tài)、采集時(shí)間和車(chē)輛標(biāo)識(shí)等信息。通過(guò)對(duì)海量軌跡點(diǎn)數(shù)據(jù)進(jìn)行挖掘和分析，可以得出多種出行規(guī)律[4-6]，從而進(jìn)一步研究路徑規(guī)劃[7]、路網(wǎng)匹配[8]、智能交通[9]和城市計(jì)算[10]等。對(duì)出租車(chē)軌跡數(shù)據(jù)進(jìn)行挖掘的首要任務(wù)是從海量位置點(diǎn)數(shù)據(jù)中提取車(chē)輛的行程，一方面要考慮借助大數(shù)據(jù)處理技術(shù)進(jìn)行分布式計(jì)算，另一方面要考慮車(chē)輛行程的劃分。

由于出租車(chē)位置點(diǎn)數(shù)據(jù)中包括空車(chē)和載客兩種不同狀態(tài)，所以軌跡可以劃分為空車(chē)軌跡和載客軌跡。本文主要研究載客軌跡的提取，提出利用MapReduce分布式計(jì)算框架，有效解決海量位置點(diǎn)數(shù)據(jù)的并行處理。通過(guò)自定義聯(lián)合鍵和分組，實(shí)現(xiàn)二次排序功能，分別設(shè)計(jì)Map端和Reduce端處理算法，最終完成載客軌跡分布式提取。

2 出租車(chē)軌跡

2.1 軌跡數(shù)據(jù)

定義1（GPS位置點(diǎn)）由GPS采集到的出租車(chē)位置信息，由車(chē)輛標(biāo)識(shí)（id）、狀態(tài)（status）、記錄時(shí)間（t）、經(jīng)度（lng）、緯度（lat）、速度（v）和方向（dir）等7個(gè)屬性組成，表示為：

定義2（出租車(chē)軌跡） 在一定時(shí)間內(nèi)，由于出租車(chē)位置變化采樣得到的一個(gè)隨時(shí)間順序記錄的GPS位置點(diǎn)集合，車(chē)輛標(biāo)識(shí)為id的軌跡表示為：

定義3（載客軌跡） 出租車(chē)軌跡中，一段時(shí)間內(nèi)車(chē)輛狀態(tài)為1的GPS位置點(diǎn)集合，車(chē)輛標(biāo)識(shí)為id的載客軌跡表示為：

2.2 載客軌跡提取

根據(jù)出租車(chē)運(yùn)營(yíng)狀態(tài)的變化可以從出租車(chē)軌跡中提取載客軌跡，軌跡提取步驟如下：

1）獲取指定出租車(chē)（標(biāo)識(shí)為id）軌跡數(shù)據(jù)GP（id）;

2）逐一判斷GP（id）包含的GPS位置點(diǎn)gpi，當(dāng)出租車(chē)GPS位置點(diǎn)的運(yùn)營(yíng)狀態(tài)由0變?yōu)?，即表示載客運(yùn)營(yíng)開(kāi)始，記錄一條新的載客軌跡;

3）載客運(yùn)營(yíng)期間，該狀態(tài)保持為1，將GPS位置點(diǎn)添加到載客軌跡中;

4）當(dāng)運(yùn)營(yíng)狀態(tài)由1變?yōu)?，一次載客軌跡記錄結(jié)束。算法流程如圖1所示。

3 基于MapReduce的載客軌跡提取

3.1 MapReduce

MapReduce是Hadoop平臺(tái)的分布式計(jì)算框架，通過(guò)MapReduce框架首先將大數(shù)據(jù)處理任務(wù)分解成多個(gè)單任務(wù)并在集群中并行執(zhí)行，然后再把這些單任務(wù)的計(jì)算結(jié)果合并到指定節(jié)點(diǎn)計(jì)算最終結(jié)果[11]。MapReduce規(guī)范中分別使用map和reduce函數(shù)實(shí)現(xiàn)分布式處理，map函數(shù)負(fù)責(zé)對(duì)數(shù)據(jù)執(zhí)行分區(qū)、排序和合并，reduce函數(shù)負(fù)責(zé)處理map提交的數(shù)據(jù)并計(jì)算最終結(jié)果。

3.2 并行處理算法

出租車(chē)位置點(diǎn)信息除了包含經(jīng)緯度外，還包括采集時(shí)間，通過(guò)采集時(shí)間先后可以判斷出租車(chē)的載客軌跡。相同出租車(chē)的軌跡需要按照時(shí)間排序，所以MapReduce既要按照出租車(chē)分組，同時(shí)同一出租車(chē)按照時(shí)間先后順序排列GPS位置點(diǎn)。借助二次排序?qū)崿F(xiàn)并行處理的框架如圖2所示。

3.3 聯(lián)合鍵

為了獲取出租車(chē)的載客軌跡，首先需要把GPS數(shù)據(jù)按照出租車(chē)標(biāo)識(shí)分組，同一輛出租車(chē)的GPS位置點(diǎn)再按照時(shí)間先后順序排列。為了借助MapReduce框架的排序功能，在MapReduce中設(shè)計(jì)聯(lián)合鍵CombineUnionKey，實(shí)現(xiàn)接口WritableComparable。該類(lèi)包含gp.id和gp.t，主要用于實(shí)現(xiàn)對(duì)key的兩次排序。

3.4 自定義分區(qū)

map的輸出結(jié)果需要進(jìn)行分區(qū)操作，MapReduce默認(rèn)按照聯(lián)合鍵進(jìn)行分區(qū)。根據(jù)軌跡提取實(shí)際需要，map的結(jié)果按照出租車(chē)標(biāo)識(shí)（聯(lián)合鍵的第一排序?qū)傩裕┓謪^(qū)，自定義分區(qū)規(guī)則：

3.5 自定義比較和分組

map輸出結(jié)果分區(qū)后，出租車(chē)標(biāo)識(shí)相同的數(shù)據(jù)需要進(jìn)行第二次比較，即按照記錄時(shí)間升序排列。設(shè)計(jì)比較器，繼承WritableComparator;在reduce階段，出租車(chē)標(biāo)識(shí)相同的數(shù)據(jù)應(yīng)屬于同一個(gè)組，為此構(gòu)造比較器，實(shí)現(xiàn)將同一出租車(chē)的GPS軌跡數(shù)據(jù)放在一個(gè)value迭代器。

3.6 Map和Reduce處理

1）Mapper定義

繼承Mapper，map函數(shù)中首先獲取gp.id和gp.t，構(gòu)造聯(lián)合鍵CombineUnionKey對(duì)象;接著獲取gp.lng、gp.lat和gp.status封裝為position對(duì)象;最后輸出的key為聯(lián)合鍵CombineUnionKey，輸出的value為自定義Position。

2）Reducer定義

繼承Reducer，reduce函數(shù)中將gp.status為1的軌跡點(diǎn)的經(jīng)緯度串聯(lián)在一起，key為gp.id，value為經(jīng)緯度按時(shí)間先后順序連接。

4 實(shí)驗(yàn)與分析

在云平臺(tái)搭建4個(gè)節(jié)點(diǎn)組成的Hadoop HA集群，每臺(tái)節(jié)點(diǎn)CPU2.6GHZ，內(nèi)存8G，操作系統(tǒng)為64位的CentOS6.6;Hadoop版本為2.6.4，Zookeeper版本為3.4.6。

實(shí)驗(yàn)數(shù)據(jù)使用北京市2012年11月9日出租車(chē)GPS位置點(diǎn)數(shù)據(jù)集，每條數(shù)據(jù)包含車(chē)輛標(biāo)識(shí)、觸發(fā)事件、運(yùn)營(yíng)狀態(tài)、采集時(shí)間、經(jīng)度、緯度、速度、方向和GPS工作狀態(tài)等。數(shù)據(jù)示例：

實(shí)驗(yàn)結(jié)果如下表1所示。

實(shí)驗(yàn)結(jié)果表明，通過(guò)MapReduce的二次排序設(shè)計(jì)，有效地解決了海量GPS位置點(diǎn)數(shù)據(jù)中載客軌跡的提取問(wèn)題。

5 結(jié)論

本文結(jié)合出租車(chē)GPS位置點(diǎn)數(shù)據(jù)特點(diǎn)，提出一種基于MapReduce的載客軌跡數(shù)據(jù)提取算法，設(shè)計(jì)了組合鍵并有效借助MapReduce的排序功能，完成二次排序，并實(shí)現(xiàn)了海量數(shù)據(jù)的分布式處理。實(shí)驗(yàn)驗(yàn)證了本文提出算法的有效性，下一步將如何提高分布式處理效率作為研究方向。

參考文獻(xiàn)：

[1] 李婷，裴韜，袁燁城，等.人類(lèi)活動(dòng)軌跡的分類(lèi)、模式和應(yīng)用研究綜述[J]. 地理科學(xué)進(jìn)展， 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]. 計(jì)算機(jī)應(yīng)用， 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] 秦蕭，甄峰，熊麗芳，等. 大數(shù)據(jù)時(shí)代城市時(shí)空間行為研究方法[J]. 地理科學(xué)進(jìn)展，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ìn)的軌跡地圖匹配算法[J]. 測(cè)繪通報(bào)， 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

【通聯(lián)編輯：梁書(shū)】