基于海量出租車軌跡數據的智能推薦系統(tǒng)研究

徐小奇 同濟大學電子與信息工程學院

本文旨在通過對出租車歷史行駛軌跡進行機器學習，分析乘客的移動模式和出租車司機攬客行為模式，研究和設計一個智能推薦系統(tǒng)。該系統(tǒng)主要有離線數據挖掘部分和在線數據資源發(fā)布部分組成，離線數據挖掘采用Oracle結合Hadoop進行，以SQL存儲過程開發(fā)為主，在線數據資源發(fā)布采用Java Web編寫發(fā)布程序。實驗測試表明，本文設計的出租車服務智能推薦系統(tǒng)可為乘客推薦更容易找到空駛出租車的地點，為出租車司機推薦快速招攬到乘客的地點，并實現自適應實時路況的優(yōu)化路徑推薦。與傳統(tǒng)關系數據庫的方法比較，本文提出的Oralce與Hadoop結合的混合模式性能更高。

智能推薦；oracle；hadoop；數據挖掘；上客點；路段平均速度

引言

出租車是城市公共交通的重要組成,是以巴士、地鐵、輕軌為主的大規(guī)?？瓦\交通的合理補充，目前已投入運行的出租車調度管理系統(tǒng)效率比較低，不能適應城市交通狀況與客源的時空變化，無法有效平衡出租車服務的供需關系。本系統(tǒng)旨在服務于乘客和出租車司機，一方面幫助乘客快速的找到空載出租車，另一方面為出租車司機提供尋找乘客的建議，并給出路徑規(guī)劃。為提高出租車運營的管理水平和效率，迫切需要建設一套符合杭州交通狀況的出租車智能推薦系統(tǒng)。

1.系統(tǒng)功能的實現

1.1 功能模塊實現

在系統(tǒng)需求分析中，提出了系統(tǒng)中各個模塊的大致功能，下面對每個模塊的功能進行敘述：離線挖掘模塊,數據建模模塊和在線推薦模塊。

1.2 數據處理實現

離線數據處理包括預處理階段和處理階段，前者處理邏輯簡單，側重大數據的流式處理，后者分為?？奎c偵測和路段平均速度計算。?？奎c偵測采用潛在?？奎c過濾算法對空閑旅程進行預過濾，設置時間閾值和距離閾值來判斷該點是否為潛在停靠點。經過潛在停靠點算法過濾，相同路段上仍舊含有大量的點，接著使用聚類算法進行聚類，經過觀察，當k=3或者k=4時，曲線趨于直線，結果得到有效收斂。

1.3 系統(tǒng)性能優(yōu)化

數據挖掘過程，需要進行大量的運算，執(zhí)行時間的長短影響挖掘的進度。本文提出三種優(yōu)化機制，包括區(qū)域映射機制，Cache緩沖機制和多線程并行機制。

（1）區(qū)域映射機制[7][8]

區(qū)域優(yōu)化: 采用區(qū)域機制，每個GPS點可以o(1)映射到區(qū)域Id，根據區(qū)域Id一般含有5～20路段，只需要判斷200～400次，節(jié)省計算次數達到10～20倍。

（2）Cache緩沖機制

Cache優(yōu)化：綜合考慮內存消耗大小以及加載速度的問題，對路段、節(jié)點和?？奎c進行一次性加載，對平均速度采取按照時間段進行分次加載，有效的減少訪問數據庫次數，加快系統(tǒng)整體的響應時間。

（3）多線程并行機制

多線程優(yōu)化：單線程只能夠分段從數據庫中讀取數據，且單次讀取的數據不宜過多，否則加載數據會花費很長時間。多線程并行采用84個線程，每個線程處理1萬個旅程，分10次讀取，每次1000個旅程，同時寫入數據庫的過程采用Batch提交，能夠極大提高寫效率。

2.系統(tǒng)測試

本系統(tǒng)測試針對數據正確性測試，處理時間測試，功能測試等方面進行測試，其中數據正確性主要驗證Oracle存儲過程的處理邏輯，而時間處理性能則對數據挖掘部分的主要處理過程進行時間對比，最后測試系統(tǒng)功能路徑規(guī)劃。

（1）數據正確性測試

出租車行駛旅程轉換成潛在?？奎c，中間過程需要對相同路段上的潛在停靠點進行聚類。部分噪聲點包括在其中，利用點與路段方向間夾角的特性對算法進行優(yōu)化，聚類采用角度閾值進行過濾。

（2）處理時間測試

Hadoop集群(3臺)處理的時間大為縮短，將出租車原始GPS記錄從Oracle導入Hadoop集群的時間，Hadoop處理原始記錄的時間，將處理得到的上下客、旅程等結果回導到Oracle中的時間，分別為10分鐘、18分鐘、5分鐘，整體費時33分鐘，相比Oracle存儲過程需要200分鐘，時間縮小6倍多，隨著數據量的增大，Hadoop集群的優(yōu)勢會顯得更加明顯。

（3）系統(tǒng)功能測試

為了保證高度相似性，要求歷史行駛數據的時間段與查詢時間段相同，以及相同車輛不同天相同時間段行駛經過的路線，盡可能排除不同司機行駛行為習慣不一樣導致的誤差。如表格1所示。

表1 Oracle和Hadoop處理時間比較

3.結束語

本文工作首先對出租車智能推薦系統(tǒng)的背景進行研究，目前出租車調度管理系統(tǒng)使用對象以監(jiān)管部門為主,乘客與出租車司機受益程度低，本系統(tǒng)針對乘客和出租車司機，對出租車原始GPS軌跡記錄進行數據挖掘和數據建模，將信息發(fā)布供乘客和出租車司機使用。系統(tǒng)開發(fā)主要分成三部分，離線挖掘、數據建模和在線推薦。離線挖掘部分對出租車原始GPS記錄進行處理，得到上下客熱點以及路段的歷史行駛速度，前者可以幫助乘客尋找上車點，出租車司機尋找乘客，后者用來進行路徑規(guī)劃，幫助出租車司機盡快到達目的地。數據建模部分，利用離線挖掘的數據以及道路網絡信息可以完成路線的規(guī)劃。在線推薦則將信息發(fā)布到網絡上，方便乘客和出租車司機查詢使用。最后，本文對離線挖掘部分大數據處理進行了些測試，對Oracle和Hadoop處理大數據的時間進行對比，與傳統(tǒng)關系數據庫的方法比較，本文提出的Oralce與Hadoop結合的混合模式性能更高。

[1]Fielding R T. Architectural styles and the design of network-based software architectures[D]. University of California, 2000.

[2]翟娜.Dijkstra最短路徑算法改進研究及其在GIS-T仿真分析中的應用[J].測繪標準化,2010,(1);39-41.

[3]Jing Yuan , Yu Zheng , Liuhang Zhang , XIng Xie , Guangzhong Sun, Where to find my next passenger[C], Proceedings of the 13th international conference on Ubiquitous computing, September 17-21, 2011, Beijing, China

[4]Ankerst, Mihael, Markus M. Breunig, Hans-Peter Kriegel, and J?rg Sander. "OPTICS: ordering points to identify the clustering structure."[C] ACM SIGMOD Record 28, no. 2 (1999): 49-60.

[5]嚴寒冰,劉迎春.基于GIS的城市道路網最短路徑算法探討[J].計算機學報,2000,23(2):210-215.

[6]Krishna, K., and M. Narasimha Murty. "Genetic K-means algorithm."[C] Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on 29.3 (1999): 433-439.

[7]Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, andY. Huang. Map-matching for low-sampling-rate GPS trajectories[C]. In Proc. GIS. ACM, 2009.

[8]Powell J, Huang Y, Bastani F, et al. Towards reducing taxicab cruising time using spatio-temporal profitability maps[J]. Advances in Spatial and Temporal Databases, 2011: 242-260.