車輛軌跡地圖匹配異常成因辨識方法

暨育雄， 陳丹璐，2， 鄭玉靖， 沈 煜

（1. 同濟大學 交通運輸工程學院，上海 201804；2. 浙江數(shù)智交院科技股份有限公司，浙江 杭州 310030）

車輛軌跡數(shù)據(jù)由有序軌跡點組成，描述車輛運動過程的位置變化。地圖匹配將軌跡數(shù)據(jù)關(guān)聯(lián)到電子地圖路網(wǎng)，識別車輛軌跡點所在的道路和位置，并將軌跡點序列轉(zhuǎn)換為地圖坐標下的路段序列。地圖匹配是道路交通運行態(tài)勢判別［1-2］、車輛智能調(diào)度［3］、路徑選擇行為解析［4］等研究和實踐的重要基礎(chǔ)。

常用的地圖匹配算法可分為四類。基于道路幾何信息的算法直接將軌跡點匹配到距離最近的路段上［5］；基于道路拓撲信息的算法進一步考慮路網(wǎng)連通性，從而提升匹配路段序列的合理性［6］；針對軌跡數(shù)據(jù)低采樣率和噪聲等問題，基于概率的算法假設(shè)定位誤差分布已知，通過軌跡點與周邊多條候選路段的匹配概率確定最佳匹配路段［7］；綜合匹配算法依托數(shù)據(jù)挖掘、機器學習等先進算法，考慮上述信息和其他先驗知識，提高復雜路網(wǎng)環(huán)境下的匹配準確率，如模糊邏輯［8］、卡爾曼濾波［9］和隱馬爾科夫模型［10］等。其中隱馬爾可夫模型（Hidden Markov Model， HMM）是實踐應(yīng)用較廣且準確度較高的高級地圖匹配算法。該算法將軌跡點位置視為觀測狀態(tài)，車輛實際經(jīng)過的路段位置視為隱含狀態(tài)，根據(jù)觀測概率和隱含狀態(tài)轉(zhuǎn)移概率，采用Viterbi算法［11］，求解概率最大的隱含狀態(tài)序列，即地圖匹配結(jié)果。

地圖匹配異常指軌跡點被匹配到不合理路段，其主要成因可歸納為：物理遮擋，如高樓、橋隧等設(shè)施影響；地圖路段缺失；復雜路網(wǎng)，如主輔路、高架路等。針對上述成因，諸多學者提出定制化地圖匹配算法，降低匹配異常產(chǎn)生的概率。例如，Zhang 等［12］和Hsueh等［13］分別通過識別轉(zhuǎn)折點和增加備選路段的手段，提高物理遮擋下軌跡數(shù)據(jù)匹配準確率。針對路段缺失問題，Torre等［14］和Haunert和Budig［15］通過識別軌跡“越野”現(xiàn)象，輔助地圖匹配并同時補全缺失路段。部分研究利用道路寬度［16］、級別［17］、限速［18］、駕駛行為［19］等信息，標定地圖匹配算法參數(shù)，從而降低軌跡在復雜路網(wǎng)中的匹配異常概率。然而，目前尚無方法可全面解決上述成因造成的地圖匹配異常問題。

本文提出一種數(shù)據(jù)驅(qū)動的地圖匹配異常成因辨識方法，可實現(xiàn)大規(guī)模的匹配異常軌跡段快速識別和成因歸類。

1 地圖匹配異常數(shù)據(jù)特征

基于實測數(shù)據(jù)挖掘分析，總結(jié)不同成因?qū)е碌钠ヅ洚惓?shù)據(jù)特征。典型的異常匹配結(jié)果如圖1所示。

圖1 地圖匹配異常成因及表現(xiàn)特征示意Fig.1 Causes of abnormal map matching and their characteristics

物理遮擋（如圖1a）指高樓等物理設(shè)施導致定位信號漂移，軌跡點與車輛實際經(jīng)過路段偏差較大，可能將軌跡點匹配到錯誤路段。即使軌跡點被匹配到正確路段，軌跡點與匹配路段的距離一般較大。此類匹配異常通常表現(xiàn)為，車輛軌跡方向和速度變化頻繁，軌跡點與匹配路段和周邊地圖路段均存在較大距離。

路段缺失指地圖更新滯后導致地圖上部分路段缺失，引起地圖匹配結(jié)果異常。根據(jù)缺失道路的類型不同，路段缺失可分為連接路段缺失（如圖1b）和社區(qū)路段缺失（如圖1c）：

（1） 連接路段缺失：由于新建道路未及時更新，地圖中兩點間的路段缺失，導致實際經(jīng)過該路段和前后路段的車輛軌跡點被匹配到其他路段上。此類異常通常表現(xiàn)為，軌跡點與匹配路段距離較大，且周邊沒有其他鄰近地圖路段。

（2） 社區(qū)路段缺失：由于地圖缺少小區(qū)、公園等內(nèi)部道路信息，導致經(jīng)過這些道路的車輛軌跡點被匹配到外部較高等級道路上。此類異常通常表現(xiàn)為，車輛軌跡常呈環(huán)形或L型分布，軌跡點與匹配路段和周邊地圖路段的距離較大，車輛速度較低。

復雜路網(wǎng)（如圖1d）指地圖匹配算法無法適應(yīng)所有復雜路網(wǎng)結(jié)構(gòu)，如高架與地面道路并行、主輔路并行、多進出口立交等區(qū)域，難以準確判定軌跡所在路段。此類異常通常表現(xiàn)為，車輛軌跡較為平順，部分軌跡段與匹配道路距離較大，但貼合周邊其他鄰近地圖路段。另外，與高樓密集區(qū)域、新建道路或社區(qū)道路車速相比，高架或立交周邊車輛運行速度一般較高。

2 地圖匹配異常識別與分類

本文提出一種數(shù)據(jù)驅(qū)動的地圖匹配異常識別與分類算法，流程框架如圖2 所示。算法以地圖匹配結(jié)果為輸入，通過軌跡點指標計算、匹配異常軌跡段識別和成因分類3 個步驟，最終輸出匹配異常成因分類結(jié)果。

圖2 算法流程Fig.2 Flowchart of the Algorithm

2.1 軌跡點特征指標計算

地圖匹配結(jié)果包括地圖路網(wǎng)、原始軌跡點和匹配后的軌跡點-路段對應(yīng)關(guān)系。地圖路網(wǎng)由各路段信息構(gòu)成，路段集合記為S。一條軌跡P=［p1， …，pi， …，pI］由I個有序軌跡點構(gòu)成，每個軌跡點pi包含4項信息（lon， lat， head， speed），分別為經(jīng)度、緯度、航向角（行進方向與正北方向的夾角）和車速。軌跡P的匹配路段序列記為Q=［q1， …，qi， …，qI］（qi∈S）。

基于地圖匹配結(jié)果，根據(jù)前文總結(jié)的不同成因的匹配異常特征，針對每條軌跡P的每個軌跡點pi，獲取匹配距離、路網(wǎng)鄰近距離、方向角變化率和速度指標，分別反映軌跡點與匹配路段的接近程度、軌跡點與周邊路網(wǎng)的貼合程度、車輛軌跡平順程度和車輛行駛快慢，作為匹配異常軌跡段識別和成因分類的依據(jù)。

指標1：匹配距離，為原始軌跡點與其匹配路段的距離，如式（1）。其中，函數(shù)fh表示軌跡點到路段的距離。

指標2：路網(wǎng)鄰近距離，為軌跡點到路網(wǎng)中最近路段的距離，如式（2）。

指標3：方向角變化率，為車輛行進方向的偏轉(zhuǎn)角度，如式（3）。其中，mod表示取余函數(shù)。

指標4：速度，直接由軌跡點數(shù)據(jù)得到，如式（4）。

2.2 匹配異常軌跡段識別

研究主要關(guān)注軌跡點與匹配路段距離較大的異常。為避免數(shù)據(jù)噪聲對后繼算法的影響，以軌跡段為基本單元進行匹配異常識別和成因辨識。提出一種可行的匹配正常和異常軌跡段分段流程，如圖3所示：

圖3 軌跡分段方法示意圖Fig.3 Trajectory segmentation method

步驟1：匹配點標記。基于式（1），計算所有軌跡點的匹配距離，結(jié)合設(shè)備定位誤差，通過前序數(shù)據(jù)分析、預實驗和經(jīng)驗判定等方法，定義閾值TD，將匹配距離超過閾值的軌跡點劃分為匹配異常點，其他為匹配正常點。

步驟2：匹配正常軌跡段提取。定義參數(shù)TN，匹配正常軌跡段由連續(xù)出現(xiàn)超過TN個匹配正常點構(gòu)成。

步驟3：匹配異常軌跡段提取。定義參數(shù)TU，在其余軌跡段（由剩余所有匹配異常點和連續(xù)個數(shù)不超過TN的匹配正常點構(gòu)成）中，將包含軌跡點個數(shù)超過TU的軌跡段識別為匹配異常軌跡段。其余較短軌跡段中的匹配異?？烧J為由數(shù)據(jù)隨機誤差導致，在本文未予考慮。

2.3 匹配異常軌跡段分類

基于2.1 定義的特征指標，生成匹配異常軌跡段的特征向量，作為成因分類的依據(jù)。一條匹配異常軌跡段包含若干軌跡點，根據(jù)式（1）～式（4）計算其中所有軌跡點的匹配距離、路網(wǎng)鄰近距離、方向角變化率和速度4項指標，統(tǒng)計各自均值、中位數(shù)和方差，作為該匹配異常軌跡段的12個特征值。

本文采用隨機森林算法進行匹配異常成因歸類。隨機森林是一種集成學習算法，其基本思想是將多個決策樹集成，每棵決策樹都是一個分類器。對一個輸入樣本，每棵決策樹均會產(chǎn)生一個分類投票，隨機森林集成所有的分類投票結(jié)果，將該樣本歸為投票次數(shù)最多的類別。隨機森林算法在分類任務(wù)中具備如下優(yōu)勢［20］：訓練速度較快，且具備抗噪能力，能夠高效應(yīng)用于大規(guī)模數(shù)據(jù)集；能夠處理高維特征的輸入樣本，無需預先降維；具有較高的準確率。

基于隨機森林的匹配異常軌跡段分類流程如下：

（1）訓練集標定。記匹配異常軌跡段的訓練集為X，每個樣本xk含12項特征值。通過人工標定得到成因類別yk∈Y，其中Y表示異常成因集合，包括物理遮擋、連接路段缺失、社區(qū)路段缺失、復雜路網(wǎng)4類。

（2）樣本抽樣。隨機且有放回地從訓練集X 中抽取n個訓練樣本，形成決策樹訓練集。在12 個特征指標中隨機且無放回地選取m個特征指標，構(gòu)建決策樹特征集。

（3）決策樹生成。從根節(jié)點開始不斷分裂形成新的節(jié)點。如節(jié)點包含的樣本屬于同一成因，則節(jié)點不可分，稱為葉節(jié)點。如節(jié)點可分，選取最優(yōu)特征及其閾值，將該節(jié)點樣本集Xv二分為X+和X—，形兩個子節(jié)點，特征a及其閾值的選取基于信息增益最大原則。當所有節(jié)點均不可分，決策樹構(gòu)建完成。信息增益G（Xv，a）定義如式（5）所示，其中，Xv表示當前節(jié)點樣本集，a表示特征及其取值，H（·）表示樣本集的信息熵。記樣本集Xv中成因y的樣本比例為rv，y，則H（·）如式（6）所示。

（4）隨機森林構(gòu)建。重復（2）和（3），隨機生成N棵形態(tài)不同的獨立決策樹，完成分類器訓練。

（5）分類器應(yīng)用。輸入待分類匹配異常軌跡段的特征向量X*后，每棵決策樹根據(jù)自身節(jié)點判定條件對其分類并投票，記N棵決策樹分類結(jié)果為{y*1，y*2，...，y*N}。分類器最終輸出投票次數(shù)最多的類別。

3 案例分析

3.1 標定數(shù)據(jù)集

本文采用的原始軌跡數(shù)據(jù)來源于上海市某出租車公司。數(shù)據(jù)集由16 022 輛出租車2016 年單日產(chǎn)生的479 353條營運軌跡組成，每條軌跡表示出租車空車或重車的行駛過程。車載設(shè)備每10s 實時上傳車輛信息，包括車輛編號、時間、載客狀態(tài)、經(jīng)度、緯度、航向角、速度等。地圖數(shù)據(jù)來自開放街道地圖（OpenStreetMap）［21］，以上海市全域為研究范圍。案例采用基于HMM 的地圖匹配算法［10］，得到原始軌跡對應(yīng)的路段序列，即軌跡數(shù)據(jù)的地圖匹配結(jié)果。

案例采用2.2的匹配異常軌跡段識別算法，通過預實驗（采用不同閾值參數(shù)獲取多組識別結(jié)果，與人工判定結(jié)果對比）選取合適參數(shù)，定義TN=TU=25，TD=20m，識別出12 373條匹配異常軌跡段。結(jié)合軌跡形態(tài)、路網(wǎng)結(jié)構(gòu)、車速等信息，人工標定匹配異常的成因，共標定出物理遮擋類1 719條、連接路段缺失489條，社區(qū)路段缺失3 179條和復雜路網(wǎng)類6 986條。

不同成因的匹配異常軌跡段的特征值具有明顯差異性。圖4展示了各類匹配異常軌跡段12項特征值的中位數(shù)，圖中特征值均已做最大值歸一化處理?？梢钥闯觯锢碚趽躅惖钠ヅ渚嚯x和路網(wǎng)鄰近距離均較小，速度和方向變化頻繁；連接路段缺失類的匹配距離較大，且路網(wǎng)鄰近距離變化頻繁；社區(qū)路段缺失類的原始軌跡整體速度較低，方向角變化較大，且遠離周邊路網(wǎng)，符合車輛在社區(qū)中行駛的特征；復雜路網(wǎng)類最顯著的特征是軌跡與周邊路段距離較近，但與匹配路段距離較遠，且行駛速度比其他3 類較快。

圖4 不同類型匹配異常軌跡段指標統(tǒng)計結(jié)果Fig.4 Median of indicators for different types of abnormal matching results

不同成因的匹配異常軌跡段的空間分布如圖5所示。物理遮擋類主要分布于市區(qū)中心（圖5a）；路段缺失類分布較為均衡，其中社區(qū)路段缺失（圖5c）顯著多于連接路段缺失（圖5b）；復雜路網(wǎng)類主要分布于高架路、橋梁和隧道等基礎(chǔ)設(shè)施附近（圖5d）。

圖5 不同類型匹配異常軌跡分布Fig.5 Spatial distribution of different types of abnormal matching results

以上海虹橋樞紐區(qū)域為例，該區(qū)域路網(wǎng)復雜，高架和地面道路交疊。在該區(qū)域，共識別出889 條匹配異常軌跡段，通過人工標定成因，復雜路網(wǎng)類占93.5%（831 條），物理遮擋、連接路段缺失和社區(qū)路段缺失導致的異常分別占5.3%（47 條），0.8%（7條）和0.4%（4條）。圖6展示了該區(qū)域的一條軌跡，包含匹配正常和異常的軌跡段。軌跡起點應(yīng)為虹橋火車站北側(cè)出發(fā)層，卻被異常匹配到鄰近的地面輔道上；后續(xù)的匹配結(jié)果為正常匹配。

圖6 上海虹橋樞紐區(qū)域匹配異常/正常軌跡段實例Fig.6 Example of abnormal/normal matching results in the vicinity of Hongqiao Transportation Hub, Shanghai

3.2 算法驗證

隨機抽取全市匹配異常軌跡段的80%（9 898條）為訓練集，其余軌跡段（2 475條）為測試集，驗證2.3所述成因分類算法的有效性。本文設(shè)定隨機森林分類器生成200棵決策樹，每棵樹隨機抽取的樣本個數(shù)與測試集規(guī)模相同，通過隨機4個特征值進行訓練，即，N=200，n=9 898，m=4。表1展示了隨機森林算法分類結(jié)果，并與CART決策樹算法［22］（括號中數(shù)據(jù)）進行對比。結(jié)果表明，隨機森林算法輸出的各類精確率和召回率均高于決策樹算法，驗證了其有效性。隨機森林算法可有效區(qū)分匹配異常軌跡段的成因，尤其是物理遮擋、社區(qū)路段缺失和復雜路網(wǎng)類，總體準確率達93.5%，單項精確率和召回率均超過87%。

表1 隨機森林（括號中對比CART決策樹）算法分類結(jié)果混淆矩陣Tab. 1 Confusion matrix of classification results of the random forest (decision tree) algorithm

然而，算法在判定連接路段缺失導致的匹配異常時表現(xiàn)不佳，精確率為74.2%，召回率為43.4%。一方面是由于該類異常數(shù)據(jù)量較?。ㄖ徽伎倶颖镜?%左右），分類器難以得到充分訓練從而識別這類異常特征；另一方面，這類異常在案例中的表現(xiàn)形式多樣。如圖7 所示，軌跡段A、B、C 均由于連接路段缺失導致匹配異常，其中A的異常成因被正確分類，而B和C分別被識別為復雜路網(wǎng)和物理遮擋類。軌跡段A 所在的長段道路缺失，分類特征值符合圖4規(guī)律，因此被正確歸類；軌跡段B所在路段存在部分缺失，但卻導致整段軌跡匹配到其他道路上，對匹配結(jié)果產(chǎn)生較大影響，導致路網(wǎng)鄰近距離較小而匹配距離較大，同時車速較快，與圖4中的復雜路網(wǎng)類異常特征相近；軌跡段C 所在的缺失道路與匹配道路距離較小，同時軌跡方向角變化幅度較大，與圖4中物理遮擋類異常特征相近。

圖7 連接路段缺失類異常示例Fig.7 Examples of abnormal matching results caused by missing connecting roads

圖8展示了12項匹配異常軌跡段分類特征值的影響權(quán)重。可以看出，路網(wǎng)鄰近距離的中位數(shù)和均值是分類任務(wù)中最為關(guān)鍵的指標，其影響權(quán)重分別達26.8%和19.9%；匹配距離中位數(shù)、方向角變化率方差和速度方差對分類的影響較低，權(quán)重均低于3%。

圖8 隨機森林分類器中每個特征項的權(quán)重Fig. 8 The weight for each feature element in the random forest classifier

3.3 算法區(qū)域可遷移性

為驗證算法的區(qū)域可遷移性，分別定義訓練集和測試集的區(qū)域，方案如表2所示。方案A和B以上海市中環(huán)快速路為邊界，將城市劃分為中心區(qū)和外圍區(qū)，分別基于中心和外圍區(qū)數(shù)據(jù)訓練算法，應(yīng)用于外圍和中心區(qū)的成因分類；方案C和D以黃浦江為界，將城市劃分為浦西和浦東，分別基于浦西和浦東匹配異常數(shù)據(jù)訓練算法，應(yīng)用于浦東和浦西的成因分類。

表2 算法區(qū)域可遷移性驗證實驗設(shè)計和結(jié)果Tab. 2 Settings and results of the experiments for validating the spatial suitability of the algorithm

表2表明算法具有較好的區(qū)域可遷移性。在考慮區(qū)域數(shù)據(jù)差異性的情況下，各驗證方案的分類準確率均較高，超過90%。除連接路網(wǎng)導致的異常外，其余各類成因辨識單項召回率均高于88%，單項精確率均高于75%。

4 結(jié)語

本文基于大量數(shù)據(jù)的挖掘分析，歸納了物理遮擋、路段缺失（連接路段或社區(qū)路段缺失）和復雜路網(wǎng)導致的地圖匹配異常特征，據(jù)此提出了相應(yīng)的表征指標，并建立了基于隨機森林的匹配異常軌跡段識別和成因辨識方法。案例分析驗證了方法的有效性。實例驗證表明，方法可有效辨識物理遮擋、社區(qū)路段缺失和復雜路網(wǎng)成因，準確率達93.5%，單項精確率和召回率均超過87%。此外，方法具有較好的區(qū)域可遷移性，基于某區(qū)域數(shù)據(jù)訓練算法，應(yīng)用于其他區(qū)域的匹配異常成因辨識時，準確率超85%，單項精確率和單項召回率分別超88%和75%。分析表明，在選取的特征值中，路網(wǎng)鄰近距離均值和中位數(shù)對隨機森林分類器影響較大，影響權(quán)重分別達到26.8%和19.9%。本文提出的方法實現(xiàn)了地圖匹配異常結(jié)果的批量快速篩選和成因辨識，可作為地圖匹配實踐應(yīng)用的前序步驟，支撐后續(xù)的地圖修復、定制化算法研發(fā)和應(yīng)用、路側(cè)輔助定位設(shè)備布設(shè)等研究和實踐。

后續(xù)研究方向包括：選取適當特征值，提高連接路段缺失類異常的識別有效性；構(gòu)建標準化評價體系，基于地圖匹配異常結(jié)果和成因，分析不同地圖匹配算法的有效性；探索不同成因?qū)е碌牡貓D匹配異常的修正方法。

作者貢獻聲明：

暨育雄：概念提出、研究計劃制定、論文撰寫；

陳丹璐：試驗設(shè)計與開展、結(jié)果分析與可視化；

鄭玉靖：研究計劃制定、試驗設(shè)計與開展、論文撰寫；

沈煜：結(jié)果分析與可視化。