基于MapReduce的出租車停泊點智能推薦算法
2016-03-17 03:51:44蔣鴻玲
計算機應用與軟件 2016年2期
蔣鴻玲 張 楠 李 克 田 昊 葛 偉
(中國航天科技集團公司物聯網技術應用研究院 北京 100094)
?
基于MapReduce的出租車停泊點智能推薦算法
蔣鴻玲張楠李克田昊葛偉
(中國航天科技集團公司物聯網技術應用研究院北京 100094)
摘要現有解決打車難問題的研究工作大部分是集中式地調度出租車，且大多方法在單一服務器上運行串行算法分析海量出租車GPS數據，計算量大，會遇到計算時間和計算資源的瓶頸。為此提出一種基于MapReduce的出租車停泊點智能推薦算法，為司機或乘客推薦更容易接到乘客或打到車的地點。算法通過挖掘大量出租車GPS軌跡數據，檢測出停泊點，并生成停泊點知識庫。再利用推薦模型為司機或乘客推薦最佳停泊點。實驗分析了北京市真實出租車GPS軌跡數據，結果表明該算法能有效為司機和乘客推薦出停泊點，且在大數據量下具有較高的效率。
關鍵詞出租車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引言
目前打車難成為城市交通的普遍問題。乘客常打不到車，而很多出租車在路上盲目空載行駛，不僅浪費時間給城市交通帶來額外的負擔，而且浪費能源，影響城市的環境。現有一些研究關注出租車調度系統和出租車GPS數據分析。文獻[1]綜述了現有出租車GPS數據分析的研究方向，包括分析城市人群流動情況、分析不同地區和時段的交通擁堵情況、為乘客和出租車司機提供服務等。文獻[2]調度空車去乘客數期望最高的地點。文獻[3]用概率模型分析司機和乘客選擇不同策略時的成本及風險，并為司機或乘客推薦停泊點及路徑。文獻[4]給司機提供時空收益圖，提高司機的收入減少巡航時間。
現有研究工作主要是面向司機，通過分析出租車GPS數據為司機提供增加收益的策略。但出租車GPS數據量很大，以每輛車平均一分鐘產生一條GPS記錄來計算，一天產生上千條記錄，上萬輛車則有上千萬條記錄，而傳統的單服務器上運行串行算法的分析效率很低。與現有研究不同，本文的停泊點智能推薦模型不僅面向司機也面向乘客，并采用基于MapReduce的并行算法分析GPS數據，提高了分析效率。本文的停泊點是指出租車司機經常停泊的等乘客的地點，通常是最容易接到乘客的地點，如火車站、購物中心、酒店等。一個有經驗的司機通常知道什么時間火車到站，什么時間哪個購物中心打車的乘客多。本文對以往北京市出租車GPS軌跡數據進行分析，利用Hadoop[5,6]平臺存儲大量GPS軌跡數據，并設計了基于MapReduce[7,8]的并行停泊點檢測、聚類等算法，得到停泊點知識庫。最后利用停泊點知識庫進行在線推薦，為司機和乘客分別推薦不同時段的最佳停泊點。
本文主要貢獻：(1)提出了基于MapReduce的停泊點檢測算法，能夠在GPS軌跡數據量較大時快速有效地檢測出停泊點；(2)設計了基于MapReduce的DBSCAN聚類模型對停泊點聚類并計算停泊點簇的屬性，進而生成停泊點知識庫；(3)利用北京市真實出租車GPS軌跡數據驗證本文停泊點智能推薦算法的有效性，并實現了停泊點推薦的原型系統。
1停泊點智能推薦模型與算法
圖1是出租車停泊點智能推薦模型框架。該模型分為離線挖掘和在線推薦兩部分。離線挖掘在Hadoop平臺上運行基于MapReduce的并行算法，主要分3步。(1)對原始GPS軌跡數據預處理，刪除噪聲，保留對挖掘有意義的數據。(2)檢測出租車停泊點。(3)對停泊點聚類形成停泊點簇，進而生成停泊點知識庫。在線推薦部分則利用停泊點知識庫，設計面向司機和面向乘客的推薦模型，分別為司機和乘客進行推薦。
圖1 出租車停泊點智能推薦模型框架
2離線挖掘
2.1GPS軌跡數據預處理
首先刪除經緯度異常和完全重復的數據。然后統計每輛出租車每天采集GPS記錄的持續時間和記錄個數。根據持續時間和GPS記錄個數的數據分布情況，對原始GPS軌跡數據進行過濾，保留對挖掘有意義的數據。
2.2檢測停泊點
出租車在停泊點等待乘客時，GPS軌跡數據中相鄰軌跡點之間的距離很小，且逗留的時間較長。因而停泊點是一組距離較小并且逗留時間較長的GPS點集。本文首先檢測候選停泊點，然后對候選停泊點過濾，最后計算停泊點中的所有GPS點集的平均經緯度等，將GPS點集抽象為一個停泊點。
檢測候選停泊點的過程即找出一組滿足距離和時間閾值的連續GPS點集的過程。給定一個出租車行駛軌跡P1,P2, …,Pn，Pi表示一條GPS記錄。依次檢測每個點Pi和其后面的點Pi+1,Pi+2,…,Pj的距離是否小于距離閾值Dth，如果小于Dth且時間間隔大于時間閾值Tth，則將點Pi到Pj加入到候選停泊點集合中。然后從下一個點Pi+1開始重復上述過程，直到候選停泊點集合不再加入新的點為止。
圖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開始重復上述過程，如圖2(D)(E)。 (5) 直到D中不再加入新點，dist(P7,P8)>Dth，如圖2(F)，則檢測出一個候選停泊點D，D是一組GPS點集，包括P3至P7。 圖2 檢測候選停泊點示例 檢測出候選停泊點后，對候選停泊點進行過濾，去掉等待時間過長的點(停泊點對應的GPS點集中第一個點和最后一個點時間間隔大于Tmax的點)，如司機在家休息時則會長時間停留。由于停泊點是一組GPS點集，為對停泊點進行高效聚類，需要對停泊點進行處理，用一個點代表一組GPS點集。設停泊點D={P1,P2,…,Pn}，其中，P1到Pn是停泊點中的點集，Pi用經度、緯度、日期、時間表示，即(Loni,Lati,Ri,Ti)。停泊點D用集合中所有點的平均經/緯度表示，并記錄第一個和最后一個點的日期和時間，則D可表示為(aLon,aLat,sDate,sTime,eDate,eTime)。aLon/aLat表示D中所有點的平均經/緯度，sDate,sTime,eDate,eTime分別是第一個和最后一個點的日期和時間。 2.3生成停泊點知識庫 離線挖掘的目的是通過分析挖掘GPS軌跡數據生成停泊點知識庫，供在線推薦時使用。停泊點的聚類是將距離相近的停泊點聚到一起。這樣做是因為：第一，在同一個熱點區域，如地鐵站、飛機場等，不同出租車停泊點相近，可以近似為一個大點，以便靈活地對司機和乘客推薦；第二，由于GPS存在誤差，不同出租車的停泊點可能在地理位置上是一個點。因此，要對距離相近的停泊點聚類。考慮到距離相近的點形成的簇不一定是球狀，可能是任意形狀。基于密度的DBSCAN算法生成不規則簇的效果較好，且不需事先確定簇的個數，因而本文采用該算法對停泊點聚類。 由于不同時間段的停泊點不盡相同，因此本文根據時間段對停泊點聚類。將時間從0到23點平均分為12個時間段，第1個時間段的ID為1，從0:00到2:00，第2個時間段的ID為2，從2:00到4:00，以此類推。同時考慮工作日和周末的情況。停泊點數據集按照是否是工作日和時間段被分為24個子集。聚類過程用MapReduce并行算法處理，Map階段根據時間將數據集劃分為24個子集，Reduce階段用DBSCAN算法對每個子集分別聚類。 停泊點聚類完成后，對聚類結果進行處理，以生成停泊點知識庫。該過程主要計算停泊點簇的屬性，考慮以下四方面因素：(1)在該簇內停泊的出租車個數。一個司機在此處停泊不一定說明該處打車的乘客多，而多個司機在此處停泊一定程度上說明該處打車的乘客多。(2)等待時間，即出租車在停泊點等待乘客的時間。簇的等待時間為簇中所有停泊點等待時間的平均值。(3)簇中點的緊密程度。如果簇中各停泊點之間的距離越近，說明該簇中的停泊點較緊密，推薦的地點更明確，反之亦然。緊密程度取簇中所有停泊點到簇中心點的距離的平均值。(4)停泊點簇的位置。為司機或者乘客推薦時，要考慮司機或者乘客當前位置到推薦點的距離。用一個點代表停泊點簇，即簇中心點。簇中心點的經緯度為簇中所有點的平均經緯度。據以上分析，停泊點簇的屬性包括：出租車的個數、等待時間、到簇中心點距離的平均值、簇中心點的經緯度。 2.4停泊點檢測及其知識庫生成的MapReduce算法 停泊點檢測及其知識庫生成的MapReduce過程分4個Job完成，如圖3所示。Job1和Job2檢測停泊點，Job3和Job4生成停泊點知識庫。Hadoop自動將預處理后的GPS軌跡文件分為若干個split塊，每個split塊大小為64 MB。每個MapReduce任務由Map階段和Reduce階段構成，分別用Map函數和Reduce函數實現[9]。 下面分別介紹各MapReduce任務。Job1檢測候選停泊點并對其過濾得到停泊點。Job1的輸入是預處理后的出租車GPS記錄，包括出租車編號(taxiID)、日期(date)、時間(time)、unix時間，即當前時間到1970年1月1日0點的時間之差(unixtime)、經緯度(lon/lat)。Map1輸出的key和value中都包含unixtime，這樣可利用MapReduce的Shuffle階段的排序功能，按taxiID分組按unixtime排序，進而提高算法的速度。Reduce1根據2.2節所述過程檢測每輛車的停泊點。Reduce1在輸出結果前進行過濾，去掉等待時間大于閾值Tmax的停泊點。 圖3 停泊點檢測及其知識庫生成的MapReduce過程 Job2計算停泊點屬性，即GPS點集中所有點的平均經緯度、開始/結束時間、時間間隔。Map2的輸出按出租車ID(taxiID)和停泊點ID(DID)分組，按停泊點中GPS記錄的ID(pIDs)排序。Reduce2計算停泊點的屬性并輸出。Reduce2輸出key是 Job3對不同時間段的停泊點進行DBSCAN聚類。Map3判斷每條輸入記錄是否是工作日并計算時間段ID。Map3輸出key中isWorkDay表示是否是工作日，timeID表示時間段ID。value中dur是停泊點的等待時間。Reduce3采用DBSCAN算法對不同時間段的停泊點聚類。Reduce3輸出value中cID是聚類后該停泊點所屬的簇的ID。 Job4處理聚類結果，輸出停泊點知識庫。Map4的輸出以 3停泊點在線推薦 停泊點在線推薦的目的是為司機和乘客推薦最佳的停泊點。對于司機和乘客，最佳的標準不同，如司機關注是否可以快速接到乘客，即在停泊點等待時間的長短；而乘客關注是否步行較短的路程就可以到達推薦的停泊點。因而，要針對司機和乘客設計不同的推薦模型。 停泊點知識庫中存儲了停泊點簇的位置及其屬性。根據2.3節所述，推薦主要考慮出租車個數、平均等待時間、簇的緊密程度和位置。因此，一個停泊點簇C可以用特征向量表示，如下式所示： C={C1,C2,C3,C4} (1) C1到C4分別表示出租車個數、平均等待時間、簇中停泊點到簇中心點距離的平均值、停泊點距司機或乘客當前點的距離。由于C1到C4的值差別較大，因此要對特征向量歸一化處理。將當前每個特征值除以其最大值，使每個特征值的取值范圍在[0, 1]內。歸一化后的特征向量如式(2)，CMaxi(i=1,2,3,4)表示特征Ci的最大值。 (2) 得到歸一化的特征向量后，分別針對司機和乘客，計算每個簇C的分數Sc，如式(3)，w1到w4是每個特征的權值，取值范圍為[-1,1]，且w1到w4的和為0。按Sc從大到小對停泊點簇排序，分數越大的停泊點簇越優先推薦給司機或乘客。 (3) 如果是司機，主要考慮在該處停泊的出租車是否較多，多說明該處是一個真正的停泊點，因此w1取大于0的值；司機希望等待較短的時間即可接到乘客，并且簇越緊密，距離越短越好，因此，w2到w4取小于0的值。如果是乘客，該停泊點出租車越多越好，出租車等待時間越長越好，因此，w1和w2取大于0的值；對于乘客簇越緊密并且步行的路程越短越好，因此，w3和w4取小于0的值。 4實驗 4.1數據集及預處理 實驗數據來自微軟亞洲研究院公開的出租車GPS軌跡數據[10,11]，是北京地區從2008/2/2到2008/2/8的出租車GPS軌跡數據，共10 357輛車。每輛車的GPS軌跡存儲于一個文本文件中，一行表示一條GPS記錄，包括出租車ID、時間、經緯度。 分析挖掘前要先對原始GPS軌跡數據預處理。原始GPS記錄共17 662 984條，去掉經緯度異常的(如經度或緯度為0的)和各列完全相同的重復數據后，最終記錄有15 358 023條。對這些數據做如下統計分析，以刪除對挖掘沒有意義的數據。 首先統計出租車每天采集GPS記錄的持續時間。由圖4可見，各出租車采集GPS記錄持續時間差別較大。持續時間最小的為0，即只有1條GPS記錄，這樣的數據將會刪除。持續時間最大的為86 399秒，即一天的時間。說明有的車全天24小時都在采集GPS信息，而有的車不是全天采集的。 圖4 出租車每天采集GPS記錄持續時間統計 然后統計每輛出租車每天采集的GPS記錄個數。由圖5可見，少量車每天采集的GPS記錄個數不到100。大部分是在103數量級，平均1分鐘采集一次。最大的每天采集27 306條GPS記錄，平均3.16秒采集一次。 圖5 每天采集的GPS記錄個數統計 根據上述統計分析可以看出，大部分車每天采集上千條GPS記錄，有的車一天24小時都在采集，有的一天采集幾個小時。在分析GPS數據時，要刪除GPS記錄個數少的，因為只有一定規模的數據才能挖掘出停泊點知識庫。本文實驗中刪除了每天采集GPS記錄個數小于60的出租車GPS軌跡數據，對余下的數據進行分析。刪除后共15 078 142條GPS記錄，9593輛出租車。 4.2實驗及結果分析 數據預處理后，將在Hadoop平臺下對預處理后的GPS軌跡數據進行離線挖掘，生成停泊點知識庫。實驗中Hadoop平臺的環境配置如下：4臺服務器，其中1個Master節點，3個Slaver節點。Master節點是雙核CPU，2.40 GHz，內存32 GB，硬盤1 TB。3個Slaver節點的配置相同，雙核CPU，2.13 GHz，內存32 GB，硬盤1 TB。Hadoop平臺版本為1.0.3。 為取得較好的推薦效果，實驗分析了DBSCAN算法的距離閾值和最小密度變化時停泊點簇個數和噪聲比。噪聲比即聚類后沒有被分到任何簇中的噪聲個數和所有停泊點個數的比例。 圖6為距離閾值變化時的簇個數和噪聲比。實驗分別取非工作日和工作日中時間段ID為0、4、10的三組數據進行了比較。n0、n4、n10、w0、w4、w10分別表示非工作日和工作日時間段在0:00-2:00, 8:00-10:00, 20:00-22:00范圍內的數據。實驗中最小密度固定為3，距離閾值從50增大到200(單位：米)。從圖6可見，距離閾值增大時，簇個數有增大的趨勢，工作日時距離閾值取100時簇個數最大。工作日時距離閾值大于100時，簇個數有減小趨勢。由于工作日的GPS數據量比非工作日大，因而工作日的簇個數較多。距離閾值增大時，噪聲比逐漸減小。考慮到距離閾值越大，停泊點簇的范圍越大，推薦的范圍也會增大，乘客需要步行較長距離。綜合上述分析，實驗中距離閾值取100。 圖6 距離閾值變化時的簇個數和噪聲比 圖7是最小密度變化時簇個數和噪聲比。n0、n4、n10、w0、w4、w10的含義如上所述。實驗中距離閾值取100，最小密度分別取2、3、4、5。從圖7可見，最小密度越大，簇個數越小，噪聲比越大，和預期結果相同。為達到較好的推薦效果，即簇個數越大，噪聲比越小越好。綜合考慮，實驗中最小密度取3。 圖7 最小密度變化時的簇個數和噪聲比 停泊點檢測及其知識庫生成的MapReduce算法效率用加速比su評估。加速比是指數據集固定，不斷增大計算節點個數時算法并行的性能[12]，如式(4)。p是計算節點個數，T1和Tp分別是1個和p個節點時的運行時間。 (4) 圖8分析了數據集大小不同時算法的加速比。共4個數據集，分別記為D1、D2、D3、D4，其中出租車個數分別為100、1000、5000和9593。Tp取3次實驗的平均值。理想情況下加速比是呈線性的，但實際的加速比要低于理想狀態。D1的加速比最小，因為數據量小時Hadoop集群中部分節點處于空閑狀態。數據集越大加速比越接近線性。加速比沒有達到線性是因為節點通信、任務啟動、調度等開銷。該實驗證實了本文基于MapReduce的停泊點挖掘算法更適用于處理大規模數據集。 圖8 加速比 接下來的實驗比較了傳統串行算法和本文的MapReduce算法檢測停泊點并生成停泊點知識庫的運行時間。圖9為傳統算法和MapReduce算法的對比圖。當數據量較小時傳統算法運行時間略小。當數據量增大時傳統算法運行時間上升得很快，而MapReduce算法的運行時間上升較緩，且遠低于傳統方法。可見本文算法提高了停泊點挖掘效率，數據量較大時效果更明顯。 圖9 傳統算法和MapReduce算法對比 為驗證本文出租車停泊點智能推薦算法的有效性，設計并實現了一套原型系統，利用Hadoop平臺挖掘出的停泊點知識庫和司機乘客的推薦模型實現在線推薦。原型系統中司機/乘客可以輸入當前點位置、時間、最遠距離(用戶能接受距離當前位置最遠多少米范圍內的停泊點)、最多推薦的停泊點數。當前位置也可在地圖上通過點擊鼠標選擇。系統將根據輸入條件推薦出最佳的停泊點。系統推薦的停泊點是一個區域而不是一個點，這樣使推薦更加靈活，用戶在進入該區域的路上也可能發現乘客或打到車。 5結語 本文提出了基于MapReduce的出租車停泊點智能推薦算法。首先對原始GPS軌跡數據預處理，然后利用MapReduce模型設計并行算法檢測停泊點并對其聚類，最終生成停泊點知識庫，利用推薦模型實現司機和乘客的在線推薦。通過實驗確定了DBSCAN算法的最佳距離閾值和最小密度，以達到更好的推薦效果。實驗分析了本文MapReduce算法的加速比，比較了傳統算法和MapReduce算法的效率，結果表明本文算法在數據量增大時運行時間上升緩慢，效率明顯高于傳統算法。實驗中利用真實出租車GPS軌跡數據，生成停泊點知識庫。設計并實現了停泊點智能推薦的原型系統，驗證了本文停泊點推薦算法可以有效推薦出較容易接到乘客或打到車的地點。本文的研究工作為緩解出租車和乘客的供需矛盾奠定了基礎。未來工作將進一步細化停泊點檢測算法，如GPS軌跡預處理時考慮軌跡和路網匹配問題等。 參考文獻 [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平臺下計算模型中調度策略的研究[J]．計算機應用與軟件，2013,30(9):208-210,214. [7] 趙輝, 楊樹強,陳志坤,等.基于MapReduce模型的范圍查詢分析優化技術研究[J].計算機研究與發展,2014,51(3):606-617. [8] 林彬, 李姍姍,廖湘科,等.Seadown: 一種異構 MapReduce 集群中面向 SLA 的能耗管理方法[J].計算機學報,2013,36(5):977-987. [9] 慈祥, 馬友忠, 孟小峰.一種云環境下的大數據Top-K查詢方法[J].軟件學報,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的僵尸網絡在線檢測算法[J].電子與信息學報,2013, 35(7):1732-1738. 中圖分類號TP391 文獻標識碼A DOI:10.3969/j.issn.1000-386x.2016.02.059 收稿日期：2014-08-06。河北省科技廳項目(13210707)。蔣鴻玲，博士，主研領域：數據挖掘，大數據。張楠，高工。李克，高工。田昊，工程師。葛偉，工程師。
