基于貝葉斯網絡的稀疏出租車GPS軌跡路徑還原方法

李廣耀, 黃正鋒, 樓樂依

基于貝葉斯網絡的稀疏出租車GPS軌跡路徑還原方法

李廣耀, 黃正鋒*, 樓樂依

（寧波大學 海運學院, 浙江 寧波 315832）

為提高出租車GPS大數據的可用性, 提出一種基于貝葉斯網絡研究稀疏出租車GPS軌跡路徑還原的方法. 與傳統僅基于時空變量的研究方法不同, 新算法同時考慮天氣條件、駕駛員特性、車輛行駛特性與出租車的載客狀態等因素來進行路徑還原預測. 以寧波市體育中心周圍的路網為例, 將出租車服務信息管理平臺的GPS軌跡數據作為測試對象, 驗證本文方法的適用性. 結果顯示, 基于多因素的貝葉斯網絡方法在還原精度方面(達到91.4%)優于Logit選擇模型. 此外, 新算法尤其適用于出租車軌跡數據缺失率較高的場景, 比如缺失軌跡點跨度在5min左右.

稀疏出租車GPS數據; 貝葉斯網絡; 多因素; 軌跡還原; 缺失率

隨著信息通訊手段的進步和車載導航儀、智能手機等設備的普及, 移動出行數據的獲取變得更加容易. 以出租車為例, 其移動出行數據(主要是GPS數據)蘊含著豐富的車輛狀態信息, 如經緯度坐標、車牌號、時間、車輛載客狀態、實時車速、路段名稱等. 通過對這些數據進行處理, 可以挖掘出用戶的行為信息[1]. 例如, 通過出行者位置與路網的匹配工作, 實現出行者路徑軌跡判斷, 可以進一步獲知出行者路徑選擇行為特征[2-4]. 針對密集GPS軌跡數據, 通過地圖匹配將軌跡點位映射至路網, 可以較為容易地判斷行走軌跡. 然而由于定位設備質量、周邊環境干擾以及數據傳輸不確定性等問題, 造成出租車GPS數據缺失率較高. 當采樣率較低時, 通過點位數據來還原車輛行走軌跡就變得異常困難. 比如一輛50km·h-1的汽車若在2 min內沒有GPS數據更新, 會致使1.6km區間內的車輛行駛軌跡無法直接重現; 如果此區間內有多個交叉口, 則所選擇路徑就有多種可能, 而如何準確還原其行走路徑就是個難題. 從另一層面來看, 若能夠有效解決此問題, 則將降低數據采集與存儲成本.

針對稀疏軌跡路徑還原問題, 常用方法有以下幾種: (1)最短路徑法; (2)平均弗雷歇距離法(Average Fréchet Distance, AFD); (3)隱馬爾科夫模型(Hidden Markov Model, HMM)相關方法; (4)其他評估優化方法.

最短路徑法是較早被用來還原稀疏GPS行走路徑的方法. 如Bierlaire等[5]在研究路網較稀疏、可能的行走路徑數量較少時, 使用最短路徑法來還原實際行走軌跡, 其精度較高, 但當面向密集復雜的城市路網卻不一定合適. Brakatsoulas等[6]提出一種基于曲線相似度的地圖匹配算法, 使用AFD衡量GPS序列和候選路段序列的匹配度, 將匹配度最高的路徑作為最終匹配路徑, 但應用較為復雜. 現今應用較多的是基于HMM的一系列地圖匹配方法[7]. Lou等[8]基于HMM提出ST-Matching算法, 其還原精度與運行時間均優于AFD法. 同時在路徑還原中還涉及到許多混合型HMM方法[9-10],但這些方法一般不適用于GPS高缺失率的情形. 對于更低頻GPS采樣數據的路徑還原問題, 一些研究則采用評估優化相關方法. 王龍飛等[11]在考慮多種因素的基礎上, 利用逼近理想解排序的TOPSIS法獲取最優軌跡, 但其局限性表現在要求路網為方格形狀. Shuaidong等[12]則提出了一種分布式魯棒優化方法來軌跡還原, 但數據存在與現實情況不一致的問題.

以上諸多研究方法都未將區域交通運行特征、駕駛人路徑選擇行為特征、其他環境因素等納入考慮, 因此, 這些方法不一定適用于GPS軌跡缺失率較高的路網場景. 本文主要針對數據缺失率較高(無軌跡點位時間達到5min及以上)的情形, 在采集城市出租車GPS數據基礎上, 綜合考慮時間、空間、司機特性、環境特性、營運特性等因素, 結合實際路網情況重建路徑軌跡. 具體來說, 本文利用密集GPS數據集結合駕駛員、天氣狀況等相關屬性數值, 采用貝葉斯網絡模型進行樣本訓練, 從而建立路徑還原的貝葉斯網絡, 利用建立的貝葉斯網絡對稀疏GPS軌跡路徑進行還原.

1 問題描述

2 貝葉斯網絡模型

貝葉斯網絡模型的構建主要包括特征因素提取、結構學習、求解參數、網絡推理四步, 其中結構學習是最關鍵的步驟. 最常見方法是基于評分搜索算法, 其原理是在所有節點的結構空間內, 按照一定搜索策略和評分準則找出最佳的貝葉斯網絡結構. 應用于貝葉斯網絡結構學習的評分函數主要有基于貝葉斯統計的評分函數和基于信息論的評分函數, 前者精度較高; 當樣本數據量非常龐大時, 則可以考慮后者.

基于評分搜索的算法主要有窮舉搜索法、K2算法和爬山算法等[13-19], 其中K2算法應用較為廣泛. 本文網絡節點和樣本數據量適中, 因此, 選用貝葉斯評分函數作為結構學習的評分函數, 應用K2算法獲得貝葉斯網絡結構, 相應貝葉斯評分函數公式具體如下:

3 數據來源與處理

稀疏GPS軌跡實際上是一條等時GPS軌跡丟失了一些點位后的軌跡鏈信息, 其還原工作的難點在于如何還原最大時距相鄰軌跡點對之間的路徑. 本文構造稀疏GPS軌跡點時, 并非將完整的GPS軌跡點進行隨機打斷操作, 而是特意選定相距較遠的2個GPS點對, 將中間GPS點位舍棄, 由此構造出相對較大的時距軌跡點對場景. 通過寧波市出租車服務信息管理平臺, 特別選取了密集出租車GPS軌跡數據(采樣周期為15s)與駕駛員的基本信息, 定位好起終路段, 將一部分樣本作缺失處理, 保留離路段中心點位置最近的GPS點位作為起終點, 并將中途軌跡點作丟棄處理, 形成稀疏GPS軌跡, 然后將另一部分未處理的樣本作為輸入數據, 最后對處理過的稀疏GPS軌跡路徑進行還原.

圖1 調查范圍與軌跡路徑示意圖

本文選定寧波市體育中心周圍的路網作為研究范圍(圖1), 起終點分別為6和7,6和7點位之間的時間差在5min左右. 通過剔除異常數據, 最終獲得有效數據數15248條, 有效率為90%, 時間分布區間為2017年12月9日~2018年12月31日, 日均有效數據41條, 應用ARCGIS軟件將這些數據匹配至路網, 與軌跡路徑相關聯, 獲得18種可選路徑. 為合理選取有限條路徑作為備選集, 根據數據分布規律設置以下原則: 生成最多7條備選路徑, 當實際軌跡路徑超過7條時, 將選擇概率較小的路徑都納入第7條名義路徑. 本文在備選路徑中一共設置7條, 除了最高選擇比的6條路徑, 最后1條為剩余路徑集合, 具體如圖1所示.

車輛在通過設定起終點路段時, 鑒于各自GPS點位不可能完全重合, 因此需要將上下游路段起終GPS點位都映射到一個具有參考性的位置來進行操作, 才有利于在換算通行時間、速度等數值時, 保證相關輸入數據的一致性. 文中使用路段中心點作為統一參考位置, 將上下游路段GPS點位都映射到路段中心點. 由于映射過程中需要對起終點時間戳進行修正, 因此具體以圖2為例對修正方法進行說明.

圖2 起始路段車輛點位示意圖

計算車輛在路段中心點處的時間戳修正結果如下:

4 路徑還原影響因素選擇

針對稀疏GPS軌跡, 總結與路徑選擇行為關聯的各類因素如下:

(1)營運特性. 車輛的不同載客狀態能夠影響路徑選擇結果. 空載車輛一般優先選擇途徑熱點區域的路段, 載客車輛則無此考慮[14]. 另外, 空載車輛駕駛員出于巡視路邊揚招乘客的需求, 其運行車速相對較慢.

(2)車速特性. 路段與路徑間的交通狀態存在空間關聯性[15]. 起點路段與終點路段作為出租車選擇路徑必經路段, 其車速可以不同程度反映各條路徑的交通狀態. 比如某路段與相應路徑的流量關聯性較大, 若在離散時段(如5min)范圍內, 采集途徑該路段所有出租車速度平均值, 則該值大小能在很大程度上反映相應路徑的出行時長.

(3)環境特性. 天氣狀況對路徑選擇結果有重要影響. 在惡劣天氣下, 不確定因素增加, 道路能見度、安全狀況有所變化, 駕駛員有可能根據個體偏好及出行經驗調整出行路徑[16](本文天氣數據來自網絡: http://www.tianqihoubao.com/lishi/).

(4)駕駛員特性. 外部環境相同時, 駕駛員的自身特性(如年齡、駕齡、性別等)差異也能夠影響路徑決策結果. 張衛華等[20]通過Logit建模發現, 年輕、短駕齡特性的駕駛員傾向于靈活擇路, 而年長、長駕齡特性的駕駛員則容易堅持常開路徑.

營運、車速、環境三類數據與路徑選擇結果的直觀影響關系如圖1所示, 在選取的7個樣本中可以發現, 不同路徑選擇所對應的因素取值有所差異.

本文結合相關文獻與專家經驗, 經進一步的相關性分析, 篩選得到10個節點變量. 以影響司機路徑選擇的因素作為網絡輸入節點, 相關變量為車輛載客狀態(1)、天氣狀況(2)、是否工作日高峰時段(3)、通過整條路徑時長(4)、起點路段車速(5)、終點路段車速(6)、司機駕齡(7)、司機年齡(8)、司機性別(9), 并將供司機選擇的有效備選路徑作為根節點(10).

5 因素特征提取

特征提取在對因素取值區間進行界定以及對相關連續值進行離散化處理時, 會對軌跡還原模型的準確性有較大影響. 因此, 本文在考慮的相關因素中, 將車輛載客狀態(1)、天氣狀況(2)、是否工作日高峰時段(3)、司機性別(9)、備選路徑(10)為屬性變量, 而通過路徑的時長(4)、起點路段的車速(5)、終點路段的車速(6)、司機駕齡(7)、司機年齡(8)為作數量變量. 為滿足貝葉斯網絡的建模要求, 將屬性變量編碼處理為虛擬變量, 同時將部分連續變量編碼處理為離散變量. 離散化即將數值按值域劃分為不相交的若干個值區間, 每個區間對應一個離散值, 將原始數據更新為離散值. 結合數據分布情況對數據進行離散化, 得到表1的分類數據.

由表1可見, 所有樣本中的各類因素取值及占比都較為合理, 與現實情況沒有過大反差. 車輛載客狀態方面, 由于調查區域為城市核心區, 重車比為74%, 因此略高于市區平均值. 部分數據取值會比較低, 比如惡劣天氣(雨雪、臺風、大霧)、高峰時段、女出租車司機占比. 剩余一些數據分布都較為平均, 比如各類出行時間、起終點路段車速、駕齡、司機年齡.

針對不同路徑的樣本做歸類, 在每條路徑選擇樣本中, 發現各類因素特征都有取值, 比如在路徑2的樣本中, 運行時長分別占比為12.3%、17.0%、12.8%和57.9%. 這種現象體現了GPS軌跡路徑還原問題不能僅用單一因素或少量幾個因素進行分析, 應該多類因素共同建模判斷.

6 基于路徑還原問題的貝葉斯網絡模型結果

為校驗貝葉斯網絡模型精度, 將樣本數據依照3:1的比例劃分為訓練集和測試集, 劃分結果為11436和3812個樣本. 利用專家知識和K2算法相融合方法獲得貝葉斯網絡結構, 以樣本數據為基礎, 利用各變量與選擇路徑待關注參量相關性大小進行排序, 確定各變量的輸入節點順序為天氣、司機年齡、司機性別、是否工作日高峰時段、終點路段車速、司機駕齡、車輛狀態、起點路段車速、路徑通過時長、選擇路徑, 設置網絡中任一節點最大父節點數量不超過4, 應用K2算法在Matlab軟件中的BNT工具箱完成程序編程, 進行稀疏數據車輛軌跡還原貝葉斯網絡結構學習, 以訓練集作為數據源, 最終得到貝葉斯網絡結構(圖3).

圖3 貝葉斯網絡構建結果

根據圖3可以直觀地看到各個節點之間的變量關系, 其中終點路段車速是起點路段車速的父節點, 可以從兩個角度理解這個結果. 由于案例研究范圍的起終點距離不是特別遠, 起終點路段交通流存在一定聯系, 因此車速也具有一定的關聯性. 起點路段車速與終點路段車速相比, 它與路徑選擇的相關性更大, 成為了子節點, 其原因可能是駕駛員在起點路段時, 根據當下路段交通狀況對前方各條路徑有預判, 對路徑選擇具有一定指導性; 而終點路段車速無此特征, 從而起點路段的交通狀況與車輛選擇路徑的相關性更大.

7 模型結果檢驗

7.1 精度驗證

利用貝葉斯網絡在Matlab軟件中的BNT工具箱來完成程序編程, 進行貝葉斯網絡參數學習, 獲得對應的條件概率表集合, 而后根據網絡結構與對應的條件概率表對測試集的樣本進行選擇路徑預測, 并根據預測結果計算查全率(模型對特定目標的識別能力)和查準率(模型區分特定樣本與其他樣本的能力), 最終得到駕駛員路徑選擇識別混淆矩陣(表2).

由表2數據可見, 測試集預測駕駛員選擇路徑的準確度(模型預測結果的精度)達到91.4%, 查全率與查準率均高于86.7%, 其中其他路徑樣本的查全率和查準率都超過了93.2%. 由此可得, 該模型預測精度較高, 較為合理.

表1 路徑選擇的影響因素分類及占比統計情況(訓練集)

注: 工作日高峰時段為7:00~8:30以及16:30~18:30.

表2 貝葉斯網絡模型與多項Logit回歸模型預測還原路徑精度對比表

為驗證本文建立的路徑還原貝葉斯網絡模型在軌跡數據缺失較為嚴重時, 其還原軌跡路徑的相對優越性, 采用與多項Logit回歸模型進行比較的方法. 先對問題進行分析建模, 然后應用SPSS統計軟件使用最大似然估計法對參數進行標定, 再進行多項Logit回歸分析, 最終得到模型的預測結果(表2). 從表2數據可見, 多項Logit回歸的總體預測準確率為71.7%, 相比貝葉斯網絡模型差距明顯, 查全率與查準率最小值僅為11.2%和45.3%, 其他路徑樣本的查全率和查準率為94.0%和85.5%, 略低于貝葉斯網絡模型. 從模型預測精度矩陣分布上看, 貝葉斯網絡模型在各類選擇上的預測能力遠優于多項Logit回歸模型, 在用于不同樣本時, 其預測能力更為穩定. 由此可見, 在稀疏軌跡數據的路徑還原領域方面, 貝葉斯網絡建模方式的預測準確性更高.

7.2 ROC曲線分析

利用SPSS軟件計算出各個閾值下的假陽性率與真陽性率, 真陽性率表示被模型識別為指定路徑樣本數占實際為該路徑樣本數的比例, 假陽性率表示被模型錯誤識別為指定路徑樣本數占實際非該路徑樣本數的比例. 分別對7條路徑繪制出7條ROC曲線, 最后對這7條ROC曲線取平均, 得到總ROC曲線(圖4). 經計算, 貝葉斯網絡模型的AUC值(曲線下方面積, Area Under Curve)為0.875, 根據ROC曲線評價標準可知, 貝葉斯網絡預測模型預測精度為良好. 由此可見, 應用貝葉斯網絡模型來還原軌跡路徑的方法具有優勢.

圖4 貝葉斯網絡的ROC曲線分析

從圖4的ROC曲線還可以看出, 其他路徑的ROC曲線最為貼近左上角, 說明模型對其他路徑的預測精度最高. 原因在于其涵蓋的路徑均存在一定繞行情況, 通過時長顯著高于占比較大的其他6條路徑, 區分較為明顯. 其次則為路徑1和路徑6的ROC曲線. 通過對統計數據的分析, 選擇路徑6的司機駕齡絕大部分在15a及以上, 推測經驗豐富的駕駛員傾向將該路徑作為避開擁堵路段的一大選擇, 而選擇路徑1的司機駕齡大多數集中在10a以上和5a以下, 這些取值的聚集特征使得路徑1和6的預測精度較高.

7.3 敏感性分析

利用互信息值檢驗貝葉斯網絡的推理結果, 計算出各因素與選擇路徑的互信息值, 以觀察各因素對選擇路徑的影響程度, 如果互信息值越大, 則表明影響程度越大. 由圖5可見, 對路徑選擇影響程度較大的因素主要有時長(0.28bit)、司機駕齡(0.16bit)、車輛載客狀態(0.12bit)以及起點路段車速(0.10bit).

①時長; ②駕齡; ③車輛載客狀態; ④起點車速; ⑤司機年齡; ⑥終點車速; ⑦司機性別; ⑧是否工作日高峰時段; ⑨天氣.

7.4 軌跡數據缺失時間對模型預測精確度的影響

為了進一步研究軌跡數據缺失時間變化對模型還原精度的影響, 則將研究范圍逐步擴大, 如圖6所示, 將研究范圍由區域1逐步擴展至區域2區域3區域4, 終點由2逐步擴展至345, 在分別抹去2個點位之間的軌跡點位信息, 數據缺失時間分別為81215min左右, 參照上文步驟繪制ROC曲線(圖7), 最終得到ROC曲線的AUC值分別是0.8250.787和0.560. 可見, AUC值隨著研究范圍的逐漸擴大而逐漸降低, 當數據缺失時間達到15min時, 即研究范圍擴展到區域4時, 由于選擇路徑的不確定性增強, 模型預測精度下降, 此時的評價為一般, 甚至接近于差.

圖6 不同數據缺失時間研究范圍示意圖

圖7 不同缺失時間數據下模型ROC曲線

8 結論

提出了一種基于稀疏出租車GPS軌跡數據的路徑還原方法, 綜合考慮了包含駕駛員特性、天氣與車輛狀態等多種因素, 結合寧波市體育中心周圍路網的出租車數據對其進行檢驗. 結果表明, 這些因素對于軌跡路徑還原精度具有較大影響, 新模型的精度優于多項Logit回歸模型.

(1)通過K2算法從訓練集數據中學習得到路徑還原的貝葉斯網絡結構, 再對預測集數據進行預測檢驗, 91.4%以上的準確率表明司機特性等因素與駕駛員選擇路徑高度相關.

(2)通過對不同缺失率樣本數據情況下得到的模型ROC曲線圖分析, 證實在本文的研究案例中, 該方法適用于5min以上的數據缺失時間, 但是當數據缺失時間達到15min時, 本方法就不具有明顯優勢.

[1] Yuan N J, Zheng Y, Xie X, et al. Discovering urban functional zones using latent activity trajectories[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(3):712-725.

[2] Chen M, Liu Y, Yu X. Predicting next locations with object clustering and trajectory clustering[C]//Pacific- Asia Conference on Knowledge Discovery and Data Mining. Springer International Publishing, Singapore, 2015.

[3] Mori U, Mendiburu A, álvarez M, et al. A review of travel time estimation and forecasting for advanced traveller information systems[J]. Transportmetrica, 2015, 11(2):119-157.

[4] Lü L, Chen M, Liu Y, et al. A plane moving average algorithm for short-term traffic flow prediction[C]// Advances in Knowledge Discovery and Data Mining. Springer International Publishing, Singapore, 2015.

[5] Bierlaire M, Chen J, Newman J. A probabilistic map matching method for smartphone GPS data[J]. Transportation Research Part C: Emerging Technologies, 2013, 26(1):78-98.

[6] Brakatsoulas S, Pfoser D, Salas R, et al. On map-matching vehicle tracking data[C]//Proceedings of the 31st International Conference on Very Large Data Bases. Trondheim, Norway, 2005.

[7] 高文超, 李國良, 塔娜. 路網匹配算法綜述[J]. 軟件學報, 2018, 29(2):225-250.

[8] Lou Y, Zhang C Y, Zheng Y, et al. Map-matching for low-sampling-rate GPS trajectories[EB/OL]. [2020-03- 05]. https://www.researchgate.net/publication/221589740.

[9] Ozdemir E, Topcu A E, Ozdemir M K. A hybrid HMM model for travel path inference with sparse GPS samples[J]. Transportation, 2016, 45:233-246.

[10] Taguchi S, Koide S, Yoshimura T. Online map matching with route prediction[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(1):338-347.

[11] 王龍飛, 陳紅, 李楊, 等. 車輛出行軌跡調查分析中的丟點軌跡還原[J]. 計算機應用研究, 2014, 31(1):162- 165.

[12] Shuaidong Z, Kuilin Z. A distributionally robust optimization approach to reconstructing missing locations and paths using high-frequency trajectory data[J]. Transportation Research Part C: Emerging Technologies, 2019, 102:316-335.

[13] Cooper G F, Herskovits E. A Bayesian method for the induction of probabilistic networks from data[J]. Machine Learning, 1992, 9(4):309-347.

[14] 肖光年, 雋志才, 張春勤. 基于貝葉斯網絡和GPS軌跡數據的出行方式識別[J]. 統計與決策, 2017(6):75- 79.

[15] Marcot B G, Steventon J D, Sutherland G D, et al. Guidelines for developing and updating Bayesian belief networks applied to ecological modeling and conservation[J]. Canadian Journal of Forest Research, 2006, 36(12):3063-3074.

[16] Pearl J. Fusion, propagation, and structuring in belief networks[J]. Artificial Intelligence, 1986, 29(3):241-288.

[17] 韓勇, 樊順, 周林, 等. 基于聚類算法的出租載客點時空分布特征研究[J]. 中國海洋大學學報(自然科學版), 2019, 49(S1):155-162.

[18] 劉康, 仇培元, 劉希亮, 等. 利用詞向量模型分析城市道路交通空間相關性[J]. 測繪學報, 2017, 46(12):2032- 2040.

[19] 趙曉華, 任貴超, 陳晨, 等. 不良天氣下駕駛行為研究綜述[J]. 交通信息與安全, 2017, 35(5):70-75; 98.

[20] 張衛華, 李夢凡. 不同交通信息誘導下駕駛員路徑選擇行為研究[J]. 重慶交通大學學報(自然科學版), 2018, 37(10):86-93.

Bayesian network-based GPS path restoration for sparse taxi trajectories

LI Guangyao, HUANG Zhengfeng*, LOU Leyi

( Faculty of Maritime and Transportation, Ningbo University, Ningbo 315832, China )

In order to improve the availability of taxi GPS big data, a method based on Bayesian network for sparse taxi GPS path restoration is proposed. Different from the traditional research that is only based on spatiotemporal variables, the algorithm takes into account the weather conditions, driver characteristics, vehicle driving characteristics and taxi load status to calculate path restoration prediction. The applicability of the presented method is verified by taking the road network around Ningbo sports center as an example combined with GPS trajectory data collected from the taxi service information management platform for the testing purposes. The case study results show that the Bayesian network method based on multi factors is superior to the Logit selection model in restoration accuracy (up to 91.4%). In addition, the algorithm is especially suitable for the situation with high missing rate of taxi track data, such as the track points of about 5-minute missing span.

sparse taxi GPS data; Bayesian network; multiple factors; trajectory restoration; missing rate

U491.1

A

1001-5132（2021）02-0017-08

2020?07?06.

寧波大學學報（理工版）網址: http://journallg.nbu.edu.cn/

寧波市自然科學基金（2019A610040）; 國家自然科學基金（51408321）; 浙江省自然科學基金（LY18E080009）.

李廣耀（1995－）, 男, 山東青島人, 在讀碩士研究生, 主要研究方向: 交通運輸規劃與管理. E-mail: 1518432988@qq.com

黃正鋒（1986－）, 男, 浙江金華人, 博士/副教授, 主要研究方向: 交通運輸工程. E-mail: huangzhengfeng@nbu.edu.cn

（責任編輯 章踐立）