一種基于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

【通聯編輯：梁書】