基于貝葉斯網(wǎng)絡(luò)的稀疏出租車GPS軌跡路徑還原方法

李廣耀, 黃正鋒, 樓樂(lè)依

基于貝葉斯網(wǎng)絡(luò)的稀疏出租車GPS軌跡路徑還原方法

李廣耀, 黃正鋒*, 樓樂(lè)依

（寧波大學(xué) 海運(yùn)學(xué)院, 浙江 寧波 315832）

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

稀疏出租車GPS數(shù)據(jù); 貝葉斯網(wǎng)絡(luò); 多因素; 軌跡還原; 缺失率

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

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

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

以上諸多研究方法都未將區(qū)域交通運(yùn)行特征、駕駛?cè)寺窂竭x擇行為特征、其他環(huán)境因素等納入考慮, 因此, 這些方法不一定適用于GPS軌跡缺失率較高的路網(wǎng)場(chǎng)景. 本文主要針對(duì)數(shù)據(jù)缺失率較高(無(wú)軌跡點(diǎn)位時(shí)間達(dá)到5min及以上)的情形, 在采集城市出租車GPS數(shù)據(jù)基礎(chǔ)上, 綜合考慮時(shí)間、空間、司機(jī)特性、環(huán)境特性、營(yíng)運(yùn)特性等因素, 結(jié)合實(shí)際路網(wǎng)情況重建路徑軌跡. 具體來(lái)說(shuō), 本文利用密集GPS數(shù)據(jù)集結(jié)合駕駛員、天氣狀況等相關(guān)屬性數(shù)值, 采用貝葉斯網(wǎng)絡(luò)模型進(jìn)行樣本訓(xùn)練, 從而建立路徑還原的貝葉斯網(wǎng)絡(luò), 利用建立的貝葉斯網(wǎng)絡(luò)對(duì)稀疏GPS軌跡路徑進(jìn)行還原.

1 問(wèn)題描述

2 貝葉斯網(wǎng)絡(luò)模型

貝葉斯網(wǎng)絡(luò)模型的構(gòu)建主要包括特征因素提取、結(jié)構(gòu)學(xué)習(xí)、求解參數(shù)、網(wǎng)絡(luò)推理四步, 其中結(jié)構(gòu)學(xué)習(xí)是最關(guān)鍵的步驟. 最常見(jiàn)方法是基于評(píng)分搜索算法, 其原理是在所有節(jié)點(diǎn)的結(jié)構(gòu)空間內(nèi), 按照一定搜索策略和評(píng)分準(zhǔn)則找出最佳的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu). 應(yīng)用于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的評(píng)分函數(shù)主要有基于貝葉斯統(tǒng)計(jì)的評(píng)分函數(shù)和基于信息論的評(píng)分函數(shù), 前者精度較高; 當(dāng)樣本數(shù)據(jù)量非常龐大時(shí), 則可以考慮后者.

基于評(píng)分搜索的算法主要有窮舉搜索法、K2算法和爬山算法等[13-19], 其中K2算法應(yīng)用較為廣泛. 本文網(wǎng)絡(luò)節(jié)點(diǎn)和樣本數(shù)據(jù)量適中, 因此, 選用貝葉斯評(píng)分函數(shù)作為結(jié)構(gòu)學(xué)習(xí)的評(píng)分函數(shù), 應(yīng)用K2算法獲得貝葉斯網(wǎng)絡(luò)結(jié)構(gòu), 相應(yīng)貝葉斯評(píng)分函數(shù)公式具體如下:

3 數(shù)據(jù)來(lái)源與處理

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

圖1 調(diào)查范圍與軌跡路徑示意圖

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

車輛在通過(guò)設(shè)定起終點(diǎn)路段時(shí), 鑒于各自GPS點(diǎn)位不可能完全重合, 因此需要將上下游路段起終GPS點(diǎn)位都映射到一個(gè)具有參考性的位置來(lái)進(jìn)行操作, 才有利于在換算通行時(shí)間、速度等數(shù)值時(shí), 保證相關(guān)輸入數(shù)據(jù)的一致性. 文中使用路段中心點(diǎn)作為統(tǒng)一參考位置, 將上下游路段GPS點(diǎn)位都映射到路段中心點(diǎn). 由于映射過(guò)程中需要對(duì)起終點(diǎn)時(shí)間戳進(jìn)行修正, 因此具體以圖2為例對(duì)修正方法進(jìn)行說(shuō)明.

圖2 起始路段車輛點(diǎn)位示意圖

計(jì)算車輛在路段中心點(diǎn)處的時(shí)間戳修正結(jié)果如下:

4 路徑還原影響因素選擇

針對(duì)稀疏GPS軌跡, 總結(jié)與路徑選擇行為關(guān)聯(lián)的各類因素如下:

(1)營(yíng)運(yùn)特性. 車輛的不同載客狀態(tài)能夠影響路徑選擇結(jié)果. 空載車輛一般優(yōu)先選擇途徑熱點(diǎn)區(qū)域的路段, 載客車輛則無(wú)此考慮[14]. 另外, 空載車輛駕駛員出于巡視路邊揚(yáng)招乘客的需求, 其運(yùn)行車速相對(duì)較慢.

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

(3)環(huán)境特性. 天氣狀況對(duì)路徑選擇結(jié)果有重要影響. 在惡劣天氣下, 不確定因素增加, 道路能見(jiàn)度、安全狀況有所變化, 駕駛員有可能根據(jù)個(gè)體偏好及出行經(jīng)驗(yàn)調(diào)整出行路徑[16](本文天氣數(shù)據(jù)來(lái)自網(wǎng)絡(luò): http://www.tianqihoubao.com/lishi/).

(4)駕駛員特性. 外部環(huán)境相同時(shí), 駕駛員的自身特性(如年齡、駕齡、性別等)差異也能夠影響路徑?jīng)Q策結(jié)果. 張衛(wèi)華等[20]通過(guò)Logit建模發(fā)現(xiàn), 年輕、短駕齡特性的駕駛員傾向于靈活擇路, 而年長(zhǎng)、長(zhǎng)駕齡特性的駕駛員則容易堅(jiān)持常開(kāi)路徑.

營(yíng)運(yùn)、車速、環(huán)境三類數(shù)據(jù)與路徑選擇結(jié)果的直觀影響關(guān)系如圖1所示, 在選取的7個(gè)樣本中可以發(fā)現(xiàn), 不同路徑選擇所對(duì)應(yīng)的因素取值有所差異.

本文結(jié)合相關(guān)文獻(xiàn)與專家經(jīng)驗(yàn), 經(jīng)進(jìn)一步的相關(guān)性分析, 篩選得到10個(gè)節(jié)點(diǎn)變量. 以影響司機(jī)路徑選擇的因素作為網(wǎng)絡(luò)輸入節(jié)點(diǎn), 相關(guān)變量為車輛載客狀態(tài)(1)、天氣狀況(2)、是否工作日高峰時(shí)段(3)、通過(guò)整條路徑時(shí)長(zhǎng)(4)、起點(diǎn)路段車速(5)、終點(diǎn)路段車速(6)、司機(jī)駕齡(7)、司機(jī)年齡(8)、司機(jī)性別(9), 并將供司機(jī)選擇的有效備選路徑作為根節(jié)點(diǎn)(10).

5 因素特征提取

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

由表1可見(jiàn), 所有樣本中的各類因素取值及占比都較為合理, 與現(xiàn)實(shí)情況沒(méi)有過(guò)大反差. 車輛載客狀態(tài)方面, 由于調(diào)查區(qū)域?yàn)槌鞘泻诵膮^(qū), 重車比為74%, 因此略高于市區(qū)平均值. 部分?jǐn)?shù)據(jù)取值會(huì)比較低, 比如惡劣天氣(雨雪、臺(tái)風(fēng)、大霧)、高峰時(shí)段、女出租車司機(jī)占比. 剩余一些數(shù)據(jù)分布都較為平均, 比如各類出行時(shí)間、起終點(diǎn)路段車速、駕齡、司機(jī)年齡.

針對(duì)不同路徑的樣本做歸類, 在每條路徑選擇樣本中, 發(fā)現(xiàn)各類因素特征都有取值, 比如在路徑2的樣本中, 運(yùn)行時(shí)長(zhǎng)分別占比為12.3%、17.0%、12.8%和57.9%. 這種現(xiàn)象體現(xiàn)了GPS軌跡路徑還原問(wèn)題不能僅用單一因素或少量幾個(gè)因素進(jìn)行分析, 應(yīng)該多類因素共同建模判斷.

6 基于路徑還原問(wèn)題的貝葉斯網(wǎng)絡(luò)模型結(jié)果

為校驗(yàn)貝葉斯網(wǎng)絡(luò)模型精度, 將樣本數(shù)據(jù)依照3:1的比例劃分為訓(xùn)練集和測(cè)試集, 劃分結(jié)果為11436和3812個(gè)樣本. 利用專家知識(shí)和K2算法相融合方法獲得貝葉斯網(wǎng)絡(luò)結(jié)構(gòu), 以樣本數(shù)據(jù)為基礎(chǔ), 利用各變量與選擇路徑待關(guān)注參量相關(guān)性大小進(jìn)行排序, 確定各變量的輸入節(jié)點(diǎn)順序?yàn)樘鞖狻⑺緳C(jī)年齡、司機(jī)性別、是否工作日高峰時(shí)段、終點(diǎn)路段車速、司機(jī)駕齡、車輛狀態(tài)、起點(diǎn)路段車速、路徑通過(guò)時(shí)長(zhǎng)、選擇路徑, 設(shè)置網(wǎng)絡(luò)中任一節(jié)點(diǎn)最大父節(jié)點(diǎn)數(shù)量不超過(guò)4, 應(yīng)用K2算法在Matlab軟件中的BNT工具箱完成程序編程, 進(jìn)行稀疏數(shù)據(jù)車輛軌跡還原貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí), 以訓(xùn)練集作為數(shù)據(jù)源, 最終得到貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)(圖3).

圖3 貝葉斯網(wǎng)絡(luò)構(gòu)建結(jié)果

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

7 模型結(jié)果檢驗(yàn)

7.1 精度驗(yàn)證

利用貝葉斯網(wǎng)絡(luò)在Matlab軟件中的BNT工具箱來(lái)完成程序編程, 進(jìn)行貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí), 獲得對(duì)應(yīng)的條件概率表集合, 而后根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)與對(duì)應(yīng)的條件概率表對(duì)測(cè)試集的樣本進(jìn)行選擇路徑預(yù)測(cè), 并根據(jù)預(yù)測(cè)結(jié)果計(jì)算查全率(模型對(duì)特定目標(biāo)的識(shí)別能力)和查準(zhǔn)率(模型區(qū)分特定樣本與其他樣本的能力), 最終得到駕駛員路徑選擇識(shí)別混淆矩陣(表2).

由表2數(shù)據(jù)可見(jiàn), 測(cè)試集預(yù)測(cè)駕駛員選擇路徑的準(zhǔn)確度(模型預(yù)測(cè)結(jié)果的精度)達(dá)到91.4%, 查全率與查準(zhǔn)率均高于86.7%, 其中其他路徑樣本的查全率和查準(zhǔn)率都超過(guò)了93.2%. 由此可得, 該模型預(yù)測(cè)精度較高, 較為合理.

表1 路徑選擇的影響因素分類及占比統(tǒng)計(jì)情況(訓(xùn)練集)

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

表2 貝葉斯網(wǎng)絡(luò)模型與多項(xiàng)Logit回歸模型預(yù)測(cè)還原路徑精度對(duì)比表

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

7.2 ROC曲線分析

利用SPSS軟件計(jì)算出各個(gè)閾值下的假陽(yáng)性率與真陽(yáng)性率, 真陽(yáng)性率表示被模型識(shí)別為指定路徑樣本數(shù)占實(shí)際為該路徑樣本數(shù)的比例, 假陽(yáng)性率表示被模型錯(cuò)誤識(shí)別為指定路徑樣本數(shù)占實(shí)際非該路徑樣本數(shù)的比例. 分別對(duì)7條路徑繪制出7條ROC曲線, 最后對(duì)這7條ROC曲線取平均, 得到總ROC曲線(圖4). 經(jīng)計(jì)算, 貝葉斯網(wǎng)絡(luò)模型的AUC值(曲線下方面積, Area Under Curve)為0.875, 根據(jù)ROC曲線評(píng)價(jià)標(biāo)準(zhǔn)可知, 貝葉斯網(wǎng)絡(luò)預(yù)測(cè)模型預(yù)測(cè)精度為良好. 由此可見(jiàn), 應(yīng)用貝葉斯網(wǎng)絡(luò)模型來(lái)還原軌跡路徑的方法具有優(yōu)勢(shì).

圖4 貝葉斯網(wǎng)絡(luò)的ROC曲線分析

從圖4的ROC曲線還可以看出, 其他路徑的ROC曲線最為貼近左上角, 說(shuō)明模型對(duì)其他路徑的預(yù)測(cè)精度最高. 原因在于其涵蓋的路徑均存在一定繞行情況, 通過(guò)時(shí)長(zhǎng)顯著高于占比較大的其他6條路徑, 區(qū)分較為明顯. 其次則為路徑1和路徑6的ROC曲線. 通過(guò)對(duì)統(tǒng)計(jì)數(shù)據(jù)的分析, 選擇路徑6的司機(jī)駕齡絕大部分在15a及以上, 推測(cè)經(jīng)驗(yàn)豐富的駕駛員傾向?qū)⒃撀窂阶鳛楸荛_(kāi)擁堵路段的一大選擇, 而選擇路徑1的司機(jī)駕齡大多數(shù)集中在10a以上和5a以下, 這些取值的聚集特征使得路徑1和6的預(yù)測(cè)精度較高.

7.3 敏感性分析

利用互信息值檢驗(yàn)貝葉斯網(wǎng)絡(luò)的推理結(jié)果, 計(jì)算出各因素與選擇路徑的互信息值, 以觀察各因素對(duì)選擇路徑的影響程度, 如果互信息值越大, 則表明影響程度越大. 由圖5可見(jiàn), 對(duì)路徑選擇影響程度較大的因素主要有時(shí)長(zhǎng)(0.28bit)、司機(jī)駕齡(0.16bit)、車輛載客狀態(tài)(0.12bit)以及起點(diǎn)路段車速(0.10bit).

①時(shí)長(zhǎng); ②駕齡; ③車輛載客狀態(tài); ④起點(diǎn)車速; ⑤司機(jī)年齡; ⑥終點(diǎn)車速; ⑦司機(jī)性別; ⑧是否工作日高峰時(shí)段; ⑨天氣.

7.4 軌跡數(shù)據(jù)缺失時(shí)間對(duì)模型預(yù)測(cè)精確度的影響

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

圖6 不同數(shù)據(jù)缺失時(shí)間研究范圍示意圖

圖7 不同缺失時(shí)間數(shù)據(jù)下模型ROC曲線

8 結(jié)論

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

(1)通過(guò)K2算法從訓(xùn)練集數(shù)據(jù)中學(xué)習(xí)得到路徑還原的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu), 再對(duì)預(yù)測(cè)集數(shù)據(jù)進(jìn)行預(yù)測(cè)檢驗(yàn), 91.4%以上的準(zhǔn)確率表明司機(jī)特性等因素與駕駛員選擇路徑高度相關(guān).

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

[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] 高文超, 李國(guó)良, 塔娜. 路網(wǎng)匹配算法綜述[J]. 軟件學(xué)報(bào), 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] 王龍飛, 陳紅, 李楊, 等. 車輛出行軌跡調(diào)查分析中的丟點(diǎn)軌跡還原[J]. 計(jì)算機(jī)應(yīng)用研究, 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] 肖光年, 雋志才, 張春勤. 基于貝葉斯網(wǎng)絡(luò)和GPS軌跡數(shù)據(jù)的出行方式識(shí)別[J]. 統(tǒng)計(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] 韓勇, 樊順, 周林, 等. 基于聚類算法的出租載客點(diǎn)時(shí)空分布特征研究[J]. 中國(guó)海洋大學(xué)學(xué)報(bào)(自然科學(xué)版), 2019, 49(S1):155-162.

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

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

[20] 張衛(wèi)華, 李夢(mèng)凡. 不同交通信息誘導(dǎo)下駕駛員路徑選擇行為研究[J]. 重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版), 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.

寧波大學(xué)學(xué)報(bào)（理工版）網(wǎng)址: http://journallg.nbu.edu.cn/

寧波市自然科學(xué)基金（2019A610040）; 國(guó)家自然科學(xué)基金（51408321）; 浙江省自然科學(xué)基金（LY18E080009）.

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

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

（責(zé)任編輯 章踐立）