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

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

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

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

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

引言

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

1.系統功能的實現

1.1 功能模塊實現

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

1.2 數據處理實現

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

1.3 系統性能優化

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

（1）區域映射機制[7][8]

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

（2）Cache緩沖機制

Cache優化：綜合考慮內存消耗大小以及加載速度的問題，對路段、節點和停靠點進行一次性加載，對平均速度采取按照時間段進行分次加載，有效的減少訪問數據庫次數，加快系統整體的響應時間。

（3）多線程并行機制

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

2.系統測試

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

（1）數據正確性測試

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

（2）處理時間測試

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

（3）系統功能測試

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

表1 Oracle和Hadoop處理時間比較

3.結束語

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