褚龍現(xiàn) 李文堅

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

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

中圖分類號：TP311? ? ?文獻標(biāo)識碼：A

文章編號：1009-3044（2019）21-0001-02

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

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

2 出租車軌跡

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

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

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

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

2.2 載客軌跡提取

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

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

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

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

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

3 基于MapReduce的載客軌跡提取

3.1 MapReduce

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

3.2 并行處理算法

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

3.3 聯(lián)合鍵

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

3.4 自定義分區(qū)

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

3.5 自定義比較和分組

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

3.6 Map和Reduce處理

1）Mapper定義

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

2）Reducer定義

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

4 實驗與分析

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

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

實驗結(jié)果如下表1所示。

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

5 結(jié)論

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

參考文獻：

[1] 李婷，裴韜，袁燁城，等.人類活動軌跡的分類、模式和應(yīng)用研究綜述[J]. 地理科學(xué)進展， 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]. 計算機應(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ù)時代城市時空間行為研究方法[J]. 地理科學(xué)進展，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

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