暨育雄, 陳丹璐,2, 鄭玉靖, 沈 煜
(1. 同濟(jì)大學(xué) 交通運(yùn)輸工程學(xué)院,上海 201804;2. 浙江數(shù)智交院科技股份有限公司,浙江 杭州 310030)
車輛軌跡數(shù)據(jù)由有序軌跡點(diǎn)組成,描述車輛運(yùn)動(dòng)過程的位置變化。地圖匹配將軌跡數(shù)據(jù)關(guān)聯(lián)到電子地圖路網(wǎng),識(shí)別車輛軌跡點(diǎn)所在的道路和位置,并將軌跡點(diǎn)序列轉(zhuǎn)換為地圖坐標(biāo)下的路段序列。地圖匹配是道路交通運(yùn)行態(tài)勢(shì)判別[1-2]、車輛智能調(diào)度[3]、路徑選擇行為解析[4]等研究和實(shí)踐的重要基礎(chǔ)。
常用的地圖匹配算法可分為四類。基于道路幾何信息的算法直接將軌跡點(diǎn)匹配到距離最近的路段上[5];基于道路拓?fù)湫畔⒌乃惴ㄟM(jìn)一步考慮路網(wǎng)連通性,從而提升匹配路段序列的合理性[6];針對(duì)軌跡數(shù)據(jù)低采樣率和噪聲等問題,基于概率的算法假設(shè)定位誤差分布已知,通過軌跡點(diǎn)與周邊多條候選路段的匹配概率確定最佳匹配路段[7];綜合匹配算法依托數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等先進(jìn)算法,考慮上述信息和其他先驗(yàn)知識(shí),提高復(fù)雜路網(wǎng)環(huán)境下的匹配準(zhǔn)確率,如模糊邏輯[8]、卡爾曼濾波[9]和隱馬爾科夫模型[10]等。其中隱馬爾可夫模型(Hidden Markov Model, HMM)是實(shí)踐應(yīng)用較廣且準(zhǔn)確度較高的高級(jí)地圖匹配算法。該算法將軌跡點(diǎn)位置視為觀測(cè)狀態(tài),車輛實(shí)際經(jīng)過的路段位置視為隱含狀態(tài),根據(jù)觀測(cè)概率和隱含狀態(tài)轉(zhuǎn)移概率,采用Viterbi算法[11],求解概率最大的隱含狀態(tài)序列,即地圖匹配結(jié)果。
地圖匹配異常指軌跡點(diǎn)被匹配到不合理路段,其主要成因可歸納為:物理遮擋,如高樓、橋隧等設(shè)施影響;地圖路段缺失;復(fù)雜路網(wǎng),如主輔路、高架路等。針對(duì)上述成因,諸多學(xué)者提出定制化地圖匹配算法,降低匹配異常產(chǎn)生的概率。例如,Zhang 等[12]和Hsueh等[13]分別通過識(shí)別轉(zhuǎn)折點(diǎn)和增加備選路段的手段,提高物理遮擋下軌跡數(shù)據(jù)匹配準(zhǔn)確率。針對(duì)路段缺失問題,Torre等[14]和Haunert和Budig[15]通過識(shí)別軌跡“越野”現(xiàn)象,輔助地圖匹配并同時(shí)補(bǔ)全缺失路段。部分研究利用道路寬度[16]、級(jí)別[17]、限速[18]、駕駛行為[19]等信息,標(biāo)定地圖匹配算法參數(shù),從而降低軌跡在復(fù)雜路網(wǎng)中的匹配異常概率。然而,目前尚無(wú)方法可全面解決上述成因造成的地圖匹配異常問題。
本文提出一種數(shù)據(jù)驅(qū)動(dòng)的地圖匹配異常成因辨識(shí)方法,可實(shí)現(xiàn)大規(guī)模的匹配異常軌跡段快速識(shí)別和成因歸類。
基于實(shí)測(cè)數(shù)據(jù)挖掘分析,總結(jié)不同成因?qū)е碌钠ヅ洚惓?shù)據(jù)特征。典型的異常匹配結(jié)果如圖1所示。
圖1 地圖匹配異常成因及表現(xiàn)特征示意Fig.1 Causes of abnormal map matching and their characteristics
物理遮擋(如圖1a)指高樓等物理設(shè)施導(dǎo)致定位信號(hào)漂移,軌跡點(diǎn)與車輛實(shí)際經(jīng)過路段偏差較大,可能將軌跡點(diǎn)匹配到錯(cuò)誤路段。即使軌跡點(diǎn)被匹配到正確路段,軌跡點(diǎn)與匹配路段的距離一般較大。此類匹配異常通常表現(xiàn)為,車輛軌跡方向和速度變化頻繁,軌跡點(diǎn)與匹配路段和周邊地圖路段均存在較大距離。
路段缺失指地圖更新滯后導(dǎo)致地圖上部分路段缺失,引起地圖匹配結(jié)果異常。根據(jù)缺失道路的類型不同,路段缺失可分為連接路段缺失(如圖1b)和社區(qū)路段缺失(如圖1c):
(1) 連接路段缺失:由于新建道路未及時(shí)更新,地圖中兩點(diǎn)間的路段缺失,導(dǎo)致實(shí)際經(jīng)過該路段和前后路段的車輛軌跡點(diǎn)被匹配到其他路段上。此類異常通常表現(xiàn)為,軌跡點(diǎn)與匹配路段距離較大,且周邊沒有其他鄰近地圖路段。
(2) 社區(qū)路段缺失:由于地圖缺少小區(qū)、公園等內(nèi)部道路信息,導(dǎo)致經(jīng)過這些道路的車輛軌跡點(diǎn)被匹配到外部較高等級(jí)道路上。此類異常通常表現(xiàn)為,車輛軌跡常呈環(huán)形或L型分布,軌跡點(diǎn)與匹配路段和周邊地圖路段的距離較大,車輛速度較低。
復(fù)雜路網(wǎng)(如圖1d)指地圖匹配算法無(wú)法適應(yīng)所有復(fù)雜路網(wǎng)結(jié)構(gòu),如高架與地面道路并行、主輔路并行、多進(jìn)出口立交等區(qū)域,難以準(zhǔn)確判定軌跡所在路段。此類異常通常表現(xiàn)為,車輛軌跡較為平順,部分軌跡段與匹配道路距離較大,但貼合周邊其他鄰近地圖路段。另外,與高樓密集區(qū)域、新建道路或社區(qū)道路車速相比,高架或立交周邊車輛運(yùn)行速度一般較高。
本文提出一種數(shù)據(jù)驅(qū)動(dòng)的地圖匹配異常識(shí)別與分類算法,流程框架如圖2 所示。算法以地圖匹配結(jié)果為輸入,通過軌跡點(diǎn)指標(biāo)計(jì)算、匹配異常軌跡段識(shí)別和成因分類3 個(gè)步驟,最終輸出匹配異常成因分類結(jié)果。
圖2 算法流程Fig.2 Flowchart of the Algorithm
地圖匹配結(jié)果包括地圖路網(wǎng)、原始軌跡點(diǎn)和匹配后的軌跡點(diǎn)-路段對(duì)應(yīng)關(guān)系。地圖路網(wǎng)由各路段信息構(gòu)成,路段集合記為S。一條軌跡P=[p1, …,pi, …,pI]由I個(gè)有序軌跡點(diǎn)構(gòu)成,每個(gè)軌跡點(diǎn)pi包含4項(xiàng)信息(lon, lat, head, speed),分別為經(jīng)度、緯度、航向角(行進(jìn)方向與正北方向的夾角)和車速。軌跡P的匹配路段序列記為Q=[q1, …,qi, …,qI](qi∈S)。
基于地圖匹配結(jié)果,根據(jù)前文總結(jié)的不同成因的匹配異常特征,針對(duì)每條軌跡P的每個(gè)軌跡點(diǎn)pi,獲取匹配距離、路網(wǎng)鄰近距離、方向角變化率和速度指標(biāo),分別反映軌跡點(diǎn)與匹配路段的接近程度、軌跡點(diǎn)與周邊路網(wǎng)的貼合程度、車輛軌跡平順程度和車輛行駛快慢,作為匹配異常軌跡段識(shí)別和成因分類的依據(jù)。
指標(biāo)1:匹配距離,為原始軌跡點(diǎn)與其匹配路段的距離,如式(1)。其中,函數(shù)fh表示軌跡點(diǎn)到路段的距離。
指標(biāo)2:路網(wǎng)鄰近距離,為軌跡點(diǎn)到路網(wǎng)中最近路段的距離,如式(2)。
指標(biāo)3:方向角變化率,為車輛行進(jìn)方向的偏轉(zhuǎn)角度,如式(3)。其中,mod表示取余函數(shù)。
指標(biāo)4:速度,直接由軌跡點(diǎn)數(shù)據(jù)得到,如式(4)。
研究主要關(guān)注軌跡點(diǎn)與匹配路段距離較大的異常。為避免數(shù)據(jù)噪聲對(duì)后繼算法的影響,以軌跡段為基本單元進(jìn)行匹配異常識(shí)別和成因辨識(shí)。提出一種可行的匹配正常和異常軌跡段分段流程,如圖3所示:
圖3 軌跡分段方法示意圖Fig.3 Trajectory segmentation method
步驟1:匹配點(diǎn)標(biāo)記?;谑剑?),計(jì)算所有軌跡點(diǎn)的匹配距離,結(jié)合設(shè)備定位誤差,通過前序數(shù)據(jù)分析、預(yù)實(shí)驗(yàn)和經(jīng)驗(yàn)判定等方法,定義閾值TD,將匹配距離超過閾值的軌跡點(diǎn)劃分為匹配異常點(diǎn),其他為匹配正常點(diǎn)。
步驟2:匹配正常軌跡段提取。定義參數(shù)TN,匹配正常軌跡段由連續(xù)出現(xiàn)超過TN個(gè)匹配正常點(diǎn)構(gòu)成。
步驟3:匹配異常軌跡段提取。定義參數(shù)TU,在其余軌跡段(由剩余所有匹配異常點(diǎn)和連續(xù)個(gè)數(shù)不超過TN的匹配正常點(diǎn)構(gòu)成)中,將包含軌跡點(diǎn)個(gè)數(shù)超過TU的軌跡段識(shí)別為匹配異常軌跡段。其余較短軌跡段中的匹配異??烧J(rèn)為由數(shù)據(jù)隨機(jī)誤差導(dǎo)致,在本文未予考慮。
基于2.1 定義的特征指標(biāo),生成匹配異常軌跡段的特征向量,作為成因分類的依據(jù)。一條匹配異常軌跡段包含若干軌跡點(diǎn),根據(jù)式(1)~式(4)計(jì)算其中所有軌跡點(diǎn)的匹配距離、路網(wǎng)鄰近距離、方向角變化率和速度4項(xiàng)指標(biāo),統(tǒng)計(jì)各自均值、中位數(shù)和方差,作為該匹配異常軌跡段的12個(gè)特征值。
本文采用隨機(jī)森林算法進(jìn)行匹配異常成因歸類。隨機(jī)森林是一種集成學(xué)習(xí)算法,其基本思想是將多個(gè)決策樹集成,每棵決策樹都是一個(gè)分類器。對(duì)一個(gè)輸入樣本,每棵決策樹均會(huì)產(chǎn)生一個(gè)分類投票,隨機(jī)森林集成所有的分類投票結(jié)果,將該樣本歸為投票次數(shù)最多的類別。隨機(jī)森林算法在分類任務(wù)中具備如下優(yōu)勢(shì)[20]:訓(xùn)練速度較快,且具備抗噪能力,能夠高效應(yīng)用于大規(guī)模數(shù)據(jù)集;能夠處理高維特征的輸入樣本,無(wú)需預(yù)先降維;具有較高的準(zhǔn)確率。
基于隨機(jī)森林的匹配異常軌跡段分類流程如下:
(1)訓(xùn)練集標(biāo)定。記匹配異常軌跡段的訓(xùn)練集為X,每個(gè)樣本xk含12項(xiàng)特征值。通過人工標(biāo)定得到成因類別yk∈Y,其中Y表示異常成因集合,包括物理遮擋、連接路段缺失、社區(qū)路段缺失、復(fù)雜路網(wǎng)4類。
(2)樣本抽樣。隨機(jī)且有放回地從訓(xùn)練集X 中抽取n個(gè)訓(xùn)練樣本,形成決策樹訓(xùn)練集。在12 個(gè)特征指標(biāo)中隨機(jī)且無(wú)放回地選取m個(gè)特征指標(biāo),構(gòu)建決策樹特征集。
(3)決策樹生成。從根節(jié)點(diǎn)開始不斷分裂形成新的節(jié)點(diǎn)。如節(jié)點(diǎn)包含的樣本屬于同一成因,則節(jié)點(diǎn)不可分,稱為葉節(jié)點(diǎn)。如節(jié)點(diǎn)可分,選取最優(yōu)特征及其閾值,將該節(jié)點(diǎn)樣本集Xv二分為X+和X—,形兩個(gè)子節(jié)點(diǎn),特征a及其閾值的選取基于信息增益最大原則。當(dāng)所有節(jié)點(diǎn)均不可分,決策樹構(gòu)建完成。信息增益G(Xv,a)定義如式(5)所示,其中,Xv表示當(dāng)前節(jié)點(diǎn)樣本集,a表示特征及其取值,H(·)表示樣本集的信息熵。記樣本集Xv中成因y的樣本比例為rv,y,則H(·)如式(6)所示。
(4)隨機(jī)森林構(gòu)建。重復(fù)(2)和(3),隨機(jī)生成N棵形態(tài)不同的獨(dú)立決策樹,完成分類器訓(xùn)練。
(5)分類器應(yīng)用。輸入待分類匹配異常軌跡段的特征向量X*后,每棵決策樹根據(jù)自身節(jié)點(diǎn)判定條件對(duì)其分類并投票,記N棵決策樹分類結(jié)果為{y*1,y*2,...,y*N}。分類器最終輸出投票次數(shù)最多的類別。
本文采用的原始軌跡數(shù)據(jù)來源于上海市某出租車公司。數(shù)據(jù)集由16 022 輛出租車2016 年單日產(chǎn)生的479 353條營(yíng)運(yùn)軌跡組成,每條軌跡表示出租車空車或重車的行駛過程。車載設(shè)備每10s 實(shí)時(shí)上傳車輛信息,包括車輛編號(hào)、時(shí)間、載客狀態(tài)、經(jīng)度、緯度、航向角、速度等。地圖數(shù)據(jù)來自開放街道地圖(OpenStreetMap)[21],以上海市全域?yàn)檠芯糠秶?。案例采用基于HMM 的地圖匹配算法[10],得到原始軌跡對(duì)應(yīng)的路段序列,即軌跡數(shù)據(jù)的地圖匹配結(jié)果。
案例采用2.2的匹配異常軌跡段識(shí)別算法,通過預(yù)實(shí)驗(yàn)(采用不同閾值參數(shù)獲取多組識(shí)別結(jié)果,與人工判定結(jié)果對(duì)比)選取合適參數(shù),定義TN=TU=25,TD=20m,識(shí)別出12 373條匹配異常軌跡段。結(jié)合軌跡形態(tài)、路網(wǎng)結(jié)構(gòu)、車速等信息,人工標(biāo)定匹配異常的成因,共標(biāo)定出物理遮擋類1 719條、連接路段缺失489條,社區(qū)路段缺失3 179條和復(fù)雜路網(wǎng)類6 986條。
不同成因的匹配異常軌跡段的特征值具有明顯差異性。圖4展示了各類匹配異常軌跡段12項(xiàng)特征值的中位數(shù),圖中特征值均已做最大值歸一化處理??梢钥闯?,物理遮擋類的匹配距離和路網(wǎng)鄰近距離均較小,速度和方向變化頻繁;連接路段缺失類的匹配距離較大,且路網(wǎng)鄰近距離變化頻繁;社區(qū)路段缺失類的原始軌跡整體速度較低,方向角變化較大,且遠(yuǎn)離周邊路網(wǎng),符合車輛在社區(qū)中行駛的特征;復(fù)雜路網(wǎng)類最顯著的特征是軌跡與周邊路段距離較近,但與匹配路段距離較遠(yuǎn),且行駛速度比其他3 類較快。
圖4 不同類型匹配異常軌跡段指標(biāo)統(tǒng)計(jì)結(jié)果Fig.4 Median of indicators for different types of abnormal matching results
不同成因的匹配異常軌跡段的空間分布如圖5所示。物理遮擋類主要分布于市區(qū)中心(圖5a);路段缺失類分布較為均衡,其中社區(qū)路段缺失(圖5c)顯著多于連接路段缺失(圖5b);復(fù)雜路網(wǎng)類主要分布于高架路、橋梁和隧道等基礎(chǔ)設(shè)施附近(圖5d)。
圖5 不同類型匹配異常軌跡分布Fig.5 Spatial distribution of different types of abnormal matching results
以上海虹橋樞紐區(qū)域?yàn)槔?,該區(qū)域路網(wǎng)復(fù)雜,高架和地面道路交疊。在該區(qū)域,共識(shí)別出889 條匹配異常軌跡段,通過人工標(biāo)定成因,復(fù)雜路網(wǎng)類占93.5%(831 條),物理遮擋、連接路段缺失和社區(qū)路段缺失導(dǎo)致的異常分別占5.3%(47 條),0.8%(7條)和0.4%(4條)。圖6展示了該區(qū)域的一條軌跡,包含匹配正常和異常的軌跡段。軌跡起點(diǎn)應(yīng)為虹橋火車站北側(cè)出發(fā)層,卻被異常匹配到鄰近的地面輔道上;后續(xù)的匹配結(jié)果為正常匹配。
圖6 上海虹橋樞紐區(qū)域匹配異常/正常軌跡段實(shí)例Fig.6 Example of abnormal/normal matching results in the vicinity of Hongqiao Transportation Hub, Shanghai
隨機(jī)抽取全市匹配異常軌跡段的80%(9 898條)為訓(xùn)練集,其余軌跡段(2 475條)為測(cè)試集,驗(yàn)證2.3所述成因分類算法的有效性。本文設(shè)定隨機(jī)森林分類器生成200棵決策樹,每棵樹隨機(jī)抽取的樣本個(gè)數(shù)與測(cè)試集規(guī)模相同,通過隨機(jī)4個(gè)特征值進(jìn)行訓(xùn)練,即,N=200,n=9 898,m=4。表1展示了隨機(jī)森林算法分類結(jié)果,并與CART決策樹算法[22](括號(hào)中數(shù)據(jù))進(jìn)行對(duì)比。結(jié)果表明,隨機(jī)森林算法輸出的各類精確率和召回率均高于決策樹算法,驗(yàn)證了其有效性。隨機(jī)森林算法可有效區(qū)分匹配異常軌跡段的成因,尤其是物理遮擋、社區(qū)路段缺失和復(fù)雜路網(wǎng)類,總體準(zhǔn)確率達(dá)93.5%,單項(xiàng)精確率和召回率均超過87%。
表1 隨機(jī)森林(括號(hào)中對(duì)比CART決策樹)算法分類結(jié)果混淆矩陣Tab. 1 Confusion matrix of classification results of the random forest (decision tree) algorithm
然而,算法在判定連接路段缺失導(dǎo)致的匹配異常時(shí)表現(xiàn)不佳,精確率為74.2%,召回率為43.4%。一方面是由于該類異常數(shù)據(jù)量較?。ㄖ徽伎倶颖镜?%左右),分類器難以得到充分訓(xùn)練從而識(shí)別這類異常特征;另一方面,這類異常在案例中的表現(xiàn)形式多樣。如圖7 所示,軌跡段A、B、C 均由于連接路段缺失導(dǎo)致匹配異常,其中A的異常成因被正確分類,而B和C分別被識(shí)別為復(fù)雜路網(wǎng)和物理遮擋類。軌跡段A 所在的長(zhǎng)段道路缺失,分類特征值符合圖4規(guī)律,因此被正確歸類;軌跡段B所在路段存在部分缺失,但卻導(dǎo)致整段軌跡匹配到其他道路上,對(duì)匹配結(jié)果產(chǎn)生較大影響,導(dǎo)致路網(wǎng)鄰近距離較小而匹配距離較大,同時(shí)車速較快,與圖4中的復(fù)雜路網(wǎng)類異常特征相近;軌跡段C 所在的缺失道路與匹配道路距離較小,同時(shí)軌跡方向角變化幅度較大,與圖4中物理遮擋類異常特征相近。
圖7 連接路段缺失類異常示例Fig.7 Examples of abnormal matching results caused by missing connecting roads
圖8展示了12項(xiàng)匹配異常軌跡段分類特征值的影響權(quán)重。可以看出,路網(wǎng)鄰近距離的中位數(shù)和均值是分類任務(wù)中最為關(guān)鍵的指標(biāo),其影響權(quán)重分別達(dá)26.8%和19.9%;匹配距離中位數(shù)、方向角變化率方差和速度方差對(duì)分類的影響較低,權(quán)重均低于3%。
圖8 隨機(jī)森林分類器中每個(gè)特征項(xiàng)的權(quán)重Fig. 8 The weight for each feature element in the random forest classifier
為驗(yàn)證算法的區(qū)域可遷移性,分別定義訓(xùn)練集和測(cè)試集的區(qū)域,方案如表2所示。方案A和B以上海市中環(huán)快速路為邊界,將城市劃分為中心區(qū)和外圍區(qū),分別基于中心和外圍區(qū)數(shù)據(jù)訓(xùn)練算法,應(yīng)用于外圍和中心區(qū)的成因分類;方案C和D以黃浦江為界,將城市劃分為浦西和浦東,分別基于浦西和浦東匹配異常數(shù)據(jù)訓(xùn)練算法,應(yīng)用于浦東和浦西的成因分類。
表2 算法區(qū)域可遷移性驗(yàn)證實(shí)驗(yàn)設(shè)計(jì)和結(jié)果Tab. 2 Settings and results of the experiments for validating the spatial suitability of the algorithm
表2表明算法具有較好的區(qū)域可遷移性。在考慮區(qū)域數(shù)據(jù)差異性的情況下,各驗(yàn)證方案的分類準(zhǔn)確率均較高,超過90%。除連接路網(wǎng)導(dǎo)致的異常外,其余各類成因辨識(shí)單項(xiàng)召回率均高于88%,單項(xiàng)精確率均高于75%。
本文基于大量數(shù)據(jù)的挖掘分析,歸納了物理遮擋、路段缺失(連接路段或社區(qū)路段缺失)和復(fù)雜路網(wǎng)導(dǎo)致的地圖匹配異常特征,據(jù)此提出了相應(yīng)的表征指標(biāo),并建立了基于隨機(jī)森林的匹配異常軌跡段識(shí)別和成因辨識(shí)方法。案例分析驗(yàn)證了方法的有效性。實(shí)例驗(yàn)證表明,方法可有效辨識(shí)物理遮擋、社區(qū)路段缺失和復(fù)雜路網(wǎng)成因,準(zhǔn)確率達(dá)93.5%,單項(xiàng)精確率和召回率均超過87%。此外,方法具有較好的區(qū)域可遷移性,基于某區(qū)域數(shù)據(jù)訓(xùn)練算法,應(yīng)用于其他區(qū)域的匹配異常成因辨識(shí)時(shí),準(zhǔn)確率超85%,單項(xiàng)精確率和單項(xiàng)召回率分別超88%和75%。分析表明,在選取的特征值中,路網(wǎng)鄰近距離均值和中位數(shù)對(duì)隨機(jī)森林分類器影響較大,影響權(quán)重分別達(dá)到26.8%和19.9%。本文提出的方法實(shí)現(xiàn)了地圖匹配異常結(jié)果的批量快速篩選和成因辨識(shí),可作為地圖匹配實(shí)踐應(yīng)用的前序步驟,支撐后續(xù)的地圖修復(fù)、定制化算法研發(fā)和應(yīng)用、路側(cè)輔助定位設(shè)備布設(shè)等研究和實(shí)踐。
后續(xù)研究方向包括:選取適當(dāng)特征值,提高連接路段缺失類異常的識(shí)別有效性;構(gòu)建標(biāo)準(zhǔn)化評(píng)價(jià)體系,基于地圖匹配異常結(jié)果和成因,分析不同地圖匹配算法的有效性;探索不同成因?qū)е碌牡貓D匹配異常的修正方法。
作者貢獻(xiàn)聲明:
暨育雄:概念提出、研究計(jì)劃制定、論文撰寫;
陳丹璐:試驗(yàn)設(shè)計(jì)與開展、結(jié)果分析與可視化;
鄭玉靖:研究計(jì)劃制定、試驗(yàn)設(shè)計(jì)與開展、論文撰寫;
沈煜:結(jié)果分析與可視化。