基于MapReduce的出租車停泊點智能推薦算法

蔣鴻玲　張　楠　李　克　田　昊　葛　偉

(中國航天科技集團(tuán)公司物聯(lián)網(wǎng)技術(shù)應(yīng)用研究院　北京 100094)

?

基于MapReduce的出租車停泊點智能推薦算法

蔣鴻玲張楠李克田昊葛偉

(中國航天科技集團(tuán)公司物聯(lián)網(wǎng)技術(shù)應(yīng)用研究院北京 100094)

摘要現(xiàn)有解決打車難問題的研究工作大部分是集中式地調(diào)度出租車，且大多方法在單一服務(wù)器上運行串行算法分析海量出租車GPS數(shù)據(jù)，計算量大，會遇到計算時間和計算資源的瓶頸。為此提出一種基于MapReduce的出租車停泊點智能推薦算法，為司機(jī)或乘客推薦更容易接到乘客或打到車的地點。算法通過挖掘大量出租車GPS軌跡數(shù)據(jù)，檢測出停泊點，并生成停泊點知識庫。再利用推薦模型為司機(jī)或乘客推薦最佳停泊點。實驗分析了北京市真實出租車GPS軌跡數(shù)據(jù)，結(jié)果表明該算法能有效為司機(jī)和乘客推薦出停泊點，且在大數(shù)據(jù)量下具有較高的效率。

關(guān)鍵詞出租車GPS聚類MapReduce停泊點推薦

TAXI PARKING POINT RECOMMENDATION ALGORITHM BASED ON MAPREDUCE

Jiang HonglingZhang NanLi KeTian HaoGe Wei

(Internet of Things Technology Application Institute, China Aerospace Science and Technology Corporation, Beijing 100094,China)

AbstractMost researches on solving the problem of hard to take a taxi are for dispatching taxi centrally. The majority of approaches have huge computation and may encounter the bottlenecks of computation time and calculation resources, because they need to analyse a large amount of GPS data on a single server operating the serial algorithm. So the paper proposes a MapReduce-based taxi parking point intelligence recommendation algorithm. It recommends for drivers and passengers the places where the passengers or taxis are more likely to be met or taken. By mining a large amount of taxi GPS trace data, the algorithm detects the parking points and generates the knowledge base of parking points. Then it uses recommendation models to recommend the best parking points for drivers and passengers. The experiments analysed actual taxi GPS trace data in Beijing. Results showed that the algorithm could effectively recommend parking points for drivers and passengers, and had higher efficiency in large amount of data.

KeywordsTaxiGPSClusterMapReduceParking pointRecommendation

0引言

目前打車難成為城市交通的普遍問題。乘客常打不到車，而很多出租車在路上盲目空載行駛，不僅浪費時間給城市交通帶來額外的負(fù)擔(dān)，而且浪費能源，影響城市的環(huán)境?，F(xiàn)有一些研究關(guān)注出租車調(diào)度系統(tǒng)和出租車GPS數(shù)據(jù)分析。文獻(xiàn)[1]綜述了現(xiàn)有出租車GPS數(shù)據(jù)分析的研究方向，包括分析城市人群流動情況、分析不同地區(qū)和時段的交通擁堵情況、為乘客和出租車司機(jī)提供服務(wù)等。文獻(xiàn)[2]調(diào)度空車去乘客數(shù)期望最高的地點。文獻(xiàn)[3]用概率模型分析司機(jī)和乘客選擇不同策略時的成本及風(fēng)險，并為司機(jī)或乘客推薦停泊點及路徑。文獻(xiàn)[4]給司機(jī)提供時空收益圖，提高司機(jī)的收入減少巡航時間。

現(xiàn)有研究工作主要是面向司機(jī)，通過分析出租車GPS數(shù)據(jù)為司機(jī)提供增加收益的策略。但出租車GPS數(shù)據(jù)量很大，以每輛車平均一分鐘產(chǎn)生一條GPS記錄來計算，一天產(chǎn)生上千條記錄，上萬輛車則有上千萬條記錄，而傳統(tǒng)的單服務(wù)器上運行串行算法的分析效率很低。與現(xiàn)有研究不同，本文的停泊點智能推薦模型不僅面向司機(jī)也面向乘客，并采用基于MapReduce的并行算法分析GPS數(shù)據(jù)，提高了分析效率。本文的停泊點是指出租車司機(jī)經(jīng)常停泊的等乘客的地點，通常是最容易接到乘客的地點，如火車站、購物中心、酒店等。一個有經(jīng)驗的司機(jī)通常知道什么時間火車到站，什么時間哪個購物中心打車的乘客多。本文對以往北京市出租車GPS軌跡數(shù)據(jù)進(jìn)行分析，利用Hadoop[5,6]平臺存儲大量GPS軌跡數(shù)據(jù)，并設(shè)計了基于MapReduce[7,8]的并行停泊點檢測、聚類等算法，得到停泊點知識庫。最后利用停泊點知識庫進(jìn)行在線推薦，為司機(jī)和乘客分別推薦不同時段的最佳停泊點。

本文主要貢獻(xiàn)：(1)提出了基于MapReduce的停泊點檢測算法，能夠在GPS軌跡數(shù)據(jù)量較大時快速有效地檢測出停泊點；(2)設(shè)計了基于MapReduce的DBSCAN聚類模型對停泊點聚類并計算停泊點簇的屬性，進(jìn)而生成停泊點知識庫；(3)利用北京市真實出租車GPS軌跡數(shù)據(jù)驗證本文停泊點智能推薦算法的有效性，并實現(xiàn)了停泊點推薦的原型系統(tǒng)。

1停泊點智能推薦模型與算法

圖1是出租車停泊點智能推薦模型框架。該模型分為離線挖掘和在線推薦兩部分。離線挖掘在Hadoop平臺上運行基于MapReduce的并行算法，主要分3步。(1)對原始GPS軌跡數(shù)據(jù)預(yù)處理，刪除噪聲，保留對挖掘有意義的數(shù)據(jù)。(2)檢測出租車停泊點。(3)對停泊點聚類形成停泊點簇，進(jìn)而生成停泊點知識庫。在線推薦部分則利用停泊點知識庫，設(shè)計面向司機(jī)和面向乘客的推薦模型，分別為司機(jī)和乘客進(jìn)行推薦。

圖1　出租車停泊點智能推薦模型框架

2離線挖掘

2.1GPS軌跡數(shù)據(jù)預(yù)處理

首先刪除經(jīng)緯度異常和完全重復(fù)的數(shù)據(jù)。然后統(tǒng)計每輛出租車每天采集GPS記錄的持續(xù)時間和記錄個數(shù)。根據(jù)持續(xù)時間和GPS記錄個數(shù)的數(shù)據(jù)分布情況，對原始GPS軌跡數(shù)據(jù)進(jìn)行過濾，保留對挖掘有意義的數(shù)據(jù)。

2.2檢測停泊點

出租車在停泊點等待乘客時，GPS軌跡數(shù)據(jù)中相鄰軌跡點之間的距離很小，且逗留的時間較長。因而停泊點是一組距離較小并且逗留時間較長的GPS點集。本文首先檢測候選停泊點，然后對候選停泊點過濾，最后計算停泊點中的所有GPS點集的平均經(jīng)緯度等，將GPS點集抽象為一個停泊點。

檢測候選停泊點的過程即找出一組滿足距離和時間閾值的連續(xù)GPS點集的過程。給定一個出租車行駛軌跡P1,P2, …,Pn，Pi表示一條GPS記錄。依次檢測每個點Pi和其后面的點Pi+1,Pi+2,…,Pj的距離是否小于距離閾值Dth，如果小于Dth且時間間隔大于時間閾值Tth，則將點Pi到Pj加入到候選停泊點集合中。然后從下一個點Pi+1開始重復(fù)上述過程，直到候選停泊點集合不再加入新的點為止。

圖2是檢測候選停泊點示例。GPS軌跡依次為P1,P2,…,P8。檢測候選停泊點集合的過程如下：

(1)P1到P2距離dist(P1,P2)>Dth，如圖2(A)。

(2) 檢測下一個點P2，dist(P2,P3)>Dth，如圖2(B)。

(3) dist(P3,P4)

(4) 從P4開始重復(fù)上述過程，如圖2(D)(E)。

(5) 直到D中不再加入新點，dist(P7,P8)>Dth，如圖2(F)，則檢測出一個候選停泊點D，D是一組GPS點集，包括P3至P7。

圖2　檢測候選停泊點示例

檢測出候選停泊點后，對候選停泊點進(jìn)行過濾，去掉等待時間過長的點(停泊點對應(yīng)的GPS點集中第一個點和最后一個點時間間隔大于Tmax的點)，如司機(jī)在家休息時則會長時間停留。由于停泊點是一組GPS點集，為對停泊點進(jìn)行高效聚類，需要對停泊點進(jìn)行處理，用一個點代表一組GPS點集。設(shè)停泊點D={P1,P2,…,Pn}，其中，P1到Pn是停泊點中的點集，Pi用經(jīng)度、緯度、日期、時間表示，即(Loni,Lati,Ri,Ti)。停泊點D用集合中所有點的平均經(jīng)/緯度表示，并記錄第一個和最后一個點的日期和時間，則D可表示為(aLon,aLat,sDate,sTime,eDate,eTime)。aLon/aLat表示D中所有點的平均經(jīng)/緯度，sDate,sTime,eDate,eTime分別是第一個和最后一個點的日期和時間。

2.3生成停泊點知識庫

離線挖掘的目的是通過分析挖掘GPS軌跡數(shù)據(jù)生成停泊點知識庫，供在線推薦時使用。停泊點的聚類是將距離相近的停泊點聚到一起。這樣做是因為：第一，在同一個熱點區(qū)域，如地鐵站、飛機(jī)場等，不同出租車停泊點相近，可以近似為一個大點，以便靈活地對司機(jī)和乘客推薦；第二，由于GPS存在誤差，不同出租車的停泊點可能在地理位置上是一個點。因此，要對距離相近的停泊點聚類?？紤]到距離相近的點形成的簇不一定是球狀，可能是任意形狀。基于密度的DBSCAN算法生成不規(guī)則簇的效果較好，且不需事先確定簇的個數(shù)，因而本文采用該算法對停泊點聚類。

由于不同時間段的停泊點不盡相同，因此本文根據(jù)時間段對停泊點聚類。將時間從0到23點平均分為12個時間段，第1個時間段的ID為1，從0:00到2:00，第2個時間段的ID為2，從2:00到4:00，以此類推。同時考慮工作日和周末的情況。停泊點數(shù)據(jù)集按照是否是工作日和時間段被分為24個子集。聚類過程用MapReduce并行算法處理，Map階段根據(jù)時間將數(shù)據(jù)集劃分為24個子集，Reduce階段用DBSCAN算法對每個子集分別聚類。

停泊點聚類完成后，對聚類結(jié)果進(jìn)行處理，以生成停泊點知識庫。該過程主要計算停泊點簇的屬性，考慮以下四方面因素：(1)在該簇內(nèi)停泊的出租車個數(shù)。一個司機(jī)在此處停泊不一定說明該處打車的乘客多，而多個司機(jī)在此處停泊一定程度上說明該處打車的乘客多。(2)等待時間，即出租車在停泊點等待乘客的時間。簇的等待時間為簇中所有停泊點等待時間的平均值。(3)簇中點的緊密程度。如果簇中各停泊點之間的距離越近，說明該簇中的停泊點較緊密，推薦的地點更明確，反之亦然。緊密程度取簇中所有停泊點到簇中心點的距離的平均值。(4)停泊點簇的位置。為司機(jī)或者乘客推薦時，要考慮司機(jī)或者乘客當(dāng)前位置到推薦點的距離。用一個點代表停泊點簇，即簇中心點。簇中心點的經(jīng)緯度為簇中所有點的平均經(jīng)緯度。據(jù)以上分析，停泊點簇的屬性包括：出租車的個數(shù)、等待時間、到簇中心點距離的平均值、簇中心點的經(jīng)緯度。

2.4停泊點檢測及其知識庫生成的MapReduce算法

停泊點檢測及其知識庫生成的MapReduce過程分4個Job完成，如圖3所示。Job1和Job2檢測停泊點，Job3和Job4生成停泊點知識庫。Hadoop自動將預(yù)處理后的GPS軌跡文件分為若干個split塊，每個split塊大小為64 MB。每個MapReduce任務(wù)由Map階段和Reduce階段構(gòu)成，分別用Map函數(shù)和Reduce函數(shù)實現(xiàn)[9]。

下面分別介紹各MapReduce任務(wù)。Job1檢測候選停泊點并對其過濾得到停泊點。Job1的輸入是預(yù)處理后的出租車GPS記錄，包括出租車編號(taxiID)、日期(date)、時間(time)、unix時間，即當(dāng)前時間到1970年1月1日0點的時間之差(unixtime)、經(jīng)緯度(lon/lat)。Map1輸出的key和value中都包含unixtime，這樣可利用MapReduce的Shuffle階段的排序功能，按taxiID分組按unixtime排序，進(jìn)而提高算法的速度。Reduce1根據(jù)2.2節(jié)所述過程檢測每輛車的停泊點。Reduce1在輸出結(jié)果前進(jìn)行過濾，去掉等待時間大于閾值Tmax的停泊點。

圖3　停泊點檢測及其知識庫生成的MapReduce過程

Job2計算停泊點屬性，即GPS點集中所有點的平均經(jīng)緯度、開始/結(jié)束時間、時間間隔。Map2的輸出按出租車ID(taxiID)和停泊點ID(DID)分組，按停泊點中GPS記錄的ID(pIDs)排序。Reduce2計算停泊點的屬性并輸出。Reduce2輸出key是，value包括點集的平均經(jīng)緯度、開始日期、開始時間、結(jié)束日期、結(jié)束時間和時間間隔。

Job3對不同時間段的停泊點進(jìn)行DBSCAN聚類。Map3判斷每條輸入記錄是否是工作日并計算時間段ID。Map3輸出key中isWorkDay表示是否是工作日，timeID表示時間段ID。value中dur是停泊點的等待時間。Reduce3采用DBSCAN算法對不同時間段的停泊點聚類。Reduce3輸出value中cID是聚類后該停泊點所屬的簇的ID。

Job4處理聚類結(jié)果，輸出停泊點知識庫。Map4的輸出以分組以taxiID排序。這樣可在Reduce4中實現(xiàn)只對value遍歷一次，即可計算出每輛車的停泊點信息。Reduce4計算簇的屬性，形成停泊點知識庫。Reduce4輸出value包括：簇中所有停泊點所屬的車的總數(shù)(taxiNum)、該簇中心點的經(jīng)緯度(cLon/cLat)、簇中停泊點的等待時間的平均值(aDur)和到簇中心點的平均距離(aDist)。

3停泊點在線推薦

停泊點在線推薦的目的是為司機(jī)和乘客推薦最佳的停泊點。對于司機(jī)和乘客，最佳的標(biāo)準(zhǔn)不同，如司機(jī)關(guān)注是否可以快速接到乘客，即在停泊點等待時間的長短；而乘客關(guān)注是否步行較短的路程就可以到達(dá)推薦的停泊點。因而，要針對司機(jī)和乘客設(shè)計不同的推薦模型。

停泊點知識庫中存儲了停泊點簇的位置及其屬性。根據(jù)2.3節(jié)所述，推薦主要考慮出租車個數(shù)、平均等待時間、簇的緊密程度和位置。因此，一個停泊點簇C可以用特征向量表示，如下式所示：

C={C1,C2,C3,C4}

(1)

C1到C4分別表示出租車個數(shù)、平均等待時間、簇中停泊點到簇中心點距離的平均值、停泊點距司機(jī)或乘客當(dāng)前點的距離。由于C1到C4的值差別較大，因此要對特征向量歸一化處理。將當(dāng)前每個特征值除以其最大值，使每個特征值的取值范圍在[0, 1]內(nèi)。歸一化后的特征向量如式(2)，CMaxi(i=1,2,3,4)表示特征Ci的最大值。

(2)

得到歸一化的特征向量后，分別針對司機(jī)和乘客，計算每個簇C的分?jǐn)?shù)Sc，如式(3)，w1到w4是每個特征的權(quán)值，取值范圍為[-1,1]，且w1到w4的和為0。按Sc從大到小對停泊點簇排序，分?jǐn)?shù)越大的停泊點簇越優(yōu)先推薦給司機(jī)或乘客。

(3)

如果是司機(jī)，主要考慮在該處停泊的出租車是否較多，多說明該處是一個真正的停泊點，因此w1取大于0的值；司機(jī)希望等待較短的時間即可接到乘客，并且簇越緊密，距離越短越好，因此，w2到w4取小于0的值。如果是乘客，該停泊點出租車越多越好，出租車等待時間越長越好，因此，w1和w2取大于0的值；對于乘客簇越緊密并且步行的路程越短越好，因此，w3和w4取小于0的值。

4實驗

4.1數(shù)據(jù)集及預(yù)處理

實驗數(shù)據(jù)來自微軟亞洲研究院公開的出租車GPS軌跡數(shù)據(jù)[10,11]，是北京地區(qū)從2008/2/2到2008/2/8的出租車GPS軌跡數(shù)據(jù)，共10 357輛車。每輛車的GPS軌跡存儲于一個文本文件中，一行表示一條GPS記錄，包括出租車ID、時間、經(jīng)緯度。

分析挖掘前要先對原始GPS軌跡數(shù)據(jù)預(yù)處理。原始GPS記錄共17 662 984條，去掉經(jīng)緯度異常的(如經(jīng)度或緯度為0的)和各列完全相同的重復(fù)數(shù)據(jù)后，最終記錄有15 358 023條。對這些數(shù)據(jù)做如下統(tǒng)計分析，以刪除對挖掘沒有意義的數(shù)據(jù)。

首先統(tǒng)計出租車每天采集GPS記錄的持續(xù)時間。由圖4可見，各出租車采集GPS記錄持續(xù)時間差別較大。持續(xù)時間最小的為0，即只有1條GPS記錄，這樣的數(shù)據(jù)將會刪除。持續(xù)時間最大的為86 399秒，即一天的時間。說明有的車全天24小時都在采集GPS信息，而有的車不是全天采集的。

圖4　出租車每天采集GPS記錄持續(xù)時間統(tǒng)計

然后統(tǒng)計每輛出租車每天采集的GPS記錄個數(shù)。由圖5可見，少量車每天采集的GPS記錄個數(shù)不到100。大部分是在103數(shù)量級，平均1分鐘采集一次。最大的每天采集27 306條GPS記錄，平均3.16秒采集一次。

圖5　每天采集的GPS記錄個數(shù)統(tǒng)計

根據(jù)上述統(tǒng)計分析可以看出，大部分車每天采集上千條GPS記錄，有的車一天24小時都在采集，有的一天采集幾個小時。在分析GPS數(shù)據(jù)時，要刪除GPS記錄個數(shù)少的，因為只有一定規(guī)模的數(shù)據(jù)才能挖掘出停泊點知識庫。本文實驗中刪除了每天采集GPS記錄個數(shù)小于60的出租車GPS軌跡數(shù)據(jù)，對余下的數(shù)據(jù)進(jìn)行分析。刪除后共15 078 142條GPS記錄，9593輛出租車。

4.2實驗及結(jié)果分析

數(shù)據(jù)預(yù)處理后，將在Hadoop平臺下對預(yù)處理后的GPS軌跡數(shù)據(jù)進(jìn)行離線挖掘，生成停泊點知識庫。實驗中Hadoop平臺的環(huán)境配置如下：4臺服務(wù)器，其中1個Master節(jié)點，3個Slaver節(jié)點。Master節(jié)點是雙核CPU，2.40 GHz，內(nèi)存32 GB，硬盤1 TB。3個Slaver節(jié)點的配置相同，雙核CPU，2.13 GHz，內(nèi)存32 GB，硬盤1 TB。Hadoop平臺版本為1.0.3。

為取得較好的推薦效果，實驗分析了DBSCAN算法的距離閾值和最小密度變化時停泊點簇個數(shù)和噪聲比。噪聲比即聚類后沒有被分到任何簇中的噪聲個數(shù)和所有停泊點個數(shù)的比例。

圖6為距離閾值變化時的簇個數(shù)和噪聲比。實驗分別取非工作日和工作日中時間段ID為0、4、10的三組數(shù)據(jù)進(jìn)行了比較。n0、n4、n10、w0、w4、w10分別表示非工作日和工作日時間段在0:00-2:00, 8:00-10:00, 20:00-22:00范圍內(nèi)的數(shù)據(jù)。實驗中最小密度固定為3，距離閾值從50增大到200(單位：米)。從圖6可見，距離閾值增大時，簇個數(shù)有增大的趨勢，工作日時距離閾值取100時簇個數(shù)最大。工作日時距離閾值大于100時，簇個數(shù)有減小趨勢。由于工作日的GPS數(shù)據(jù)量比非工作日大，因而工作日的簇個數(shù)較多。距離閾值增大時，噪聲比逐漸減小?？紤]到距離閾值越大，停泊點簇的范圍越大，推薦的范圍也會增大，乘客需要步行較長距離。綜合上述分析，實驗中距離閾值取100。

圖6　距離閾值變化時的簇個數(shù)和噪聲比

圖7是最小密度變化時簇個數(shù)和噪聲比。n0、n4、n10、w0、w4、w10的含義如上所述。實驗中距離閾值取100，最小密度分別取2、3、4、5。從圖7可見，最小密度越大，簇個數(shù)越小，噪聲比越大，和預(yù)期結(jié)果相同。為達(dá)到較好的推薦效果，即簇個數(shù)越大，噪聲比越小越好。綜合考慮，實驗中最小密度取3。

圖7　最小密度變化時的簇個數(shù)和噪聲比

停泊點檢測及其知識庫生成的MapReduce算法效率用加速比su評估。加速比是指數(shù)據(jù)集固定，不斷增大計算節(jié)點個數(shù)時算法并行的性能[12]，如式(4)。p是計算節(jié)點個數(shù)，T1和Tp分別是1個和p個節(jié)點時的運行時間。

(4)

圖8分析了數(shù)據(jù)集大小不同時算法的加速比。共4個數(shù)據(jù)集，分別記為D1、D2、D3、D4，其中出租車個數(shù)分別為100、1000、5000和9593。Tp取3次實驗的平均值。理想情況下加速比是呈線性的，但實際的加速比要低于理想狀態(tài)。D1的加速比最小，因為數(shù)據(jù)量小時Hadoop集群中部分節(jié)點處于空閑狀態(tài)。數(shù)據(jù)集越大加速比越接近線性。加速比沒有達(dá)到線性是因為節(jié)點通信、任務(wù)啟動、調(diào)度等開銷。該實驗證實了本文基于MapReduce的停泊點挖掘算法更適用于處理大規(guī)模數(shù)據(jù)集。

圖8　加速比

接下來的實驗比較了傳統(tǒng)串行算法和本文的MapReduce算法檢測停泊點并生成停泊點知識庫的運行時間。圖9為傳統(tǒng)算法和MapReduce算法的對比圖。當(dāng)數(shù)據(jù)量較小時傳統(tǒng)算法運行時間略小。當(dāng)數(shù)據(jù)量增大時傳統(tǒng)算法運行時間上升得很快，而MapReduce算法的運行時間上升較緩，且遠(yuǎn)低于傳統(tǒng)方法?？梢姳疚乃惴ㄌ岣吡送２袋c挖掘效率，數(shù)據(jù)量較大時效果更明顯。

圖9　傳統(tǒng)算法和MapReduce算法對比

為驗證本文出租車停泊點智能推薦算法的有效性，設(shè)計并實現(xiàn)了一套原型系統(tǒng)，利用Hadoop平臺挖掘出的停泊點知識庫和司機(jī)乘客的推薦模型實現(xiàn)在線推薦。原型系統(tǒng)中司機(jī)/乘客可以輸入當(dāng)前點位置、時間、最遠(yuǎn)距離(用戶能接受距離當(dāng)前位置最遠(yuǎn)多少米范圍內(nèi)的停泊點)、最多推薦的停泊點數(shù)。當(dāng)前位置也可在地圖上通過點擊鼠標(biāo)選擇。系統(tǒng)將根據(jù)輸入條件推薦出最佳的停泊點。系統(tǒng)推薦的停泊點是一個區(qū)域而不是一個點，這樣使推薦更加靈活，用戶在進(jìn)入該區(qū)域的路上也可能發(fā)現(xiàn)乘客或打到車。

5結(jié)語

本文提出了基于MapReduce的出租車停泊點智能推薦算法。首先對原始GPS軌跡數(shù)據(jù)預(yù)處理，然后利用MapReduce模型設(shè)計并行算法檢測停泊點并對其聚類，最終生成停泊點知識庫，利用推薦模型實現(xiàn)司機(jī)和乘客的在線推薦。通過實驗確定了DBSCAN算法的最佳距離閾值和最小密度，以達(dá)到更好的推薦效果。實驗分析了本文MapReduce算法的加速比，比較了傳統(tǒng)算法和MapReduce算法的效率，結(jié)果表明本文算法在數(shù)據(jù)量增大時運行時間上升緩慢，效率明顯高于傳統(tǒng)算法。實驗中利用真實出租車GPS軌跡數(shù)據(jù)，生成停泊點知識庫。設(shè)計并實現(xiàn)了停泊點智能推薦的原型系統(tǒng)，驗證了本文停泊點推薦算法可以有效推薦出較容易接到乘客或打到車的地點。本文的研究工作為緩解出租車和乘客的供需矛盾奠定了基礎(chǔ)。未來工作將進(jìn)一步細(xì)化停泊點檢測算法，如GPS軌跡預(yù)處理時考慮軌跡和路網(wǎng)匹配問題等。

參考文獻(xiàn)

[1] Castro P, Zhang D, Chen C, et al. From taxi GPS traces to social and community dynamics: a survey[J].ACM Computing Surveys,2013,46(2):1-17.

[2] Yamamoto K, Uesugi K, Watanabe T. Adaptive routing of cruising taxis by mutual exchange of pathways[C]//Proceedings of Knowledge-Based Intelligent Information and Engineering Systems, Zagreb,Croatia,2010:559-566.

[3] Yuan N J, Zheng Y, Zhang L, et al.T-finder: a recommender system for finding passengers and vacant taxis[J].Knowledge and Data Engineering, IEEE Transactions on,2013,25(10):2390-2403.

[4] Powell J, Huang Y, Bastani F, et al. Towards reducing taxicab cruising time using spatio-temporal profitability maps[C]//Proceedings of the 12th International Symposium on Advances in Spatial and TemporalDatabases,Minneapolis, MN, United states,2011:242-260.

[5] Lei L. Towards a high performance virtual Hadoop cluster[J].Journal of Convergence Information Technology,2012,7(6):292-303.

[6] 曹旭, 張云華. Hadoop平臺下計算模型中調(diào)度策略的研究[J]．計算機(jī)應(yīng)用與軟件，2013,30(9):208-210,214.

[7] 趙輝, 楊樹強(qiáng),陳志坤,等.基于MapReduce模型的范圍查詢分析優(yōu)化技術(shù)研究[J].計算機(jī)研究與發(fā)展,2014,51(3):606-617.

[8] 林彬, 李姍姍,廖湘科,等.Seadown: 一種異構(gòu) MapReduce 集群中面向 SLA 的能耗管理方法[J].計算機(jī)學(xué)報,2013,36(5):977-987.

[9] 慈祥, 馬友忠, 孟小峰.一種云環(huán)境下的大數(shù)據(jù)Top-K查詢方法[J].軟件學(xué)報,2014,25(4):813-825.

[10] Yuan J, Zheng Y, Xie X, et al. Driving with knowledge from the physical world[C]//Proceedings of SIGKDD. New York, UNITED STATES, 2011:316-324.

[11] Yuan J, Zheng Y, Zhang C, et al. T-drive: driving directions based on taxi trajectories[C]//Proceedings of Sigspatial. New York, UNITED STATES, 2010:99-108.

[12] 蔣鴻玲, 邵秀麗, 李耀芳.基于MapReduce的僵尸網(wǎng)絡(luò)在線檢測算法[J].電子與信息學(xué)報,2013, 35(7):1732-1738.

中圖分類號TP391

文獻(xiàn)標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.059

收稿日期：2014-08-06。河北省科技廳項目(13210707)。蔣鴻玲，博士，主研領(lǐng)域：數(shù)據(jù)挖掘，大數(shù)據(jù)。張楠，高工。李克，高工。田昊，工程師。葛偉，工程師。