基于排名學(xué)習(xí)和多源信息的地圖匹配方法

盧家品，羅月童*，黃兆嵩，張延孔，陳為

（1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽合肥230601；2.浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,浙江 杭州310058）

全球定位系統(tǒng)(global positioning system,GPS)，利用多顆定位衛(wèi)星發(fā)射的定位信號,在全球范圍內(nèi)提供實(shí)時(shí)定位服務(wù)。近年來，越來越多的移動設(shè)備裝有GPS模塊,產(chǎn)生了海量的GPS 軌跡數(shù)據(jù)。這些數(shù)據(jù)不僅能提供諸如導(dǎo)航、重要目標(biāo)定位等基于地理位置的服務(wù)，而且還能用于基于可視化、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)技術(shù)的城市交通、人群流動及資源配給等問題的研究[1]。GPS 軌跡數(shù)據(jù)和地圖數(shù)據(jù)的準(zhǔn)確匹配是開展上述服務(wù)和研究的重要前提，但由于存在誤差，兩者間并不能準(zhǔn)確匹配。主要誤差有:(1)測量誤差，傳感器固有特性導(dǎo)致的測量誤差；(2)采樣誤差，由于受流量及設(shè)備功耗等限制[2],出現(xiàn)低頻、變頻的GPS數(shù)據(jù)，而低頻GPS數(shù)據(jù)將導(dǎo)致GPS點(diǎn)的間隔過大,無法有效確定它們之間的軌跡；(3)地圖誤差，由于測繪的不準(zhǔn)確、不及時(shí),造成一些地圖數(shù)據(jù)與實(shí)際地形不完全相符[3]。

地圖匹配(map matching)是對齊觀察到的用戶定位序列和數(shù)字地圖上路網(wǎng)的過程。是最重要的GPS 軌跡數(shù)據(jù)預(yù)處理步驟之一[4]。地圖匹配中，假設(shè)車輛或人只在道路上行走,所有道路之外的GPS數(shù)據(jù)點(diǎn)是不準(zhǔn)確的,需要將其匹配到道路上。由于存在平行道路、隧道、Y 型道路等復(fù)雜地形[5]，簡單地將GPS數(shù)據(jù)點(diǎn)映射到最近道路的做法常常會失效，對此有大量研究，相關(guān)方法可分兩大類:(1)構(gòu)建更合理的數(shù)學(xué)模型或理論模型來解決地圖匹配問題;(2)結(jié)合其他數(shù)據(jù)解決地圖匹配問題。這兩類方法都取得了較好效果,所用理論模型也與數(shù)據(jù)類型和（或）應(yīng)用場景密切相關(guān)。在面對高度數(shù)據(jù)[5]、基站數(shù)據(jù)[6]、陀螺儀、加速計(jì)[7]等新傳感器,行人[7]、機(jī)器人導(dǎo)航[8]等新應(yīng)用場景提供的新數(shù)據(jù)時(shí)，需要重新分析數(shù)據(jù)的特點(diǎn),建立相應(yīng)的數(shù)學(xué)模型，使得目前絕大多數(shù)地圖匹配方法只對特定的數(shù)據(jù)和場景有效,無法靈活地應(yīng)用到新的數(shù)據(jù)或場景中。

實(shí)際上,數(shù)據(jù)的變化并未改變地圖匹配方法的本質(zhì),即地圖匹配是利用環(huán)境數(shù)據(jù)和GPS 軌跡數(shù)據(jù)的時(shí)空特征,將GPS數(shù)據(jù)點(diǎn)映射到離散的路網(wǎng)數(shù)據(jù)的方法。因此,筆者從機(jī)器學(xué)習(xí)的思路,提出了一種基于排名學(xué)習(xí)(ranking learning)和深度神經(jīng)網(wǎng)絡(luò)(deep neural networks)的數(shù)據(jù)驅(qū)動的地圖匹配方法,以解決多源信息融合的地圖匹配問題?；谏疃壬窠?jīng)網(wǎng)絡(luò)通過排名學(xué)習(xí)的方法，從已獲取真實(shí)位置的GPS數(shù)據(jù)中有監(jiān)督地學(xué)習(xí)評分道路與GPS數(shù)據(jù)點(diǎn)相關(guān)度的評分函數(shù)；再利用評分函數(shù)對所有可能的道路與GPS數(shù)據(jù)的相關(guān)性進(jìn)行評分,選擇評分最高的道路作為匹配結(jié)果。

通過學(xué)習(xí)評分函數(shù)來確定計(jì)算模型,隱式地使用數(shù)據(jù)的幾何特征、拓?fù)涮卣?、概率特征及軌跡的時(shí)空關(guān)系來完成地圖匹配,而非事先定義的計(jì)算公式。因此，本方法可用于特定類型數(shù)據(jù)及拓展數(shù)據(jù)的情形。本文的主要貢獻(xiàn)包括:（1）設(shè)計(jì)了一個(gè)數(shù)據(jù)驅(qū)動的地圖匹配框架；（2）基于RankNet 設(shè)計(jì)了適用于地圖匹配任務(wù)的排名學(xué)習(xí)方法；（3）設(shè)計(jì)了用于學(xué)習(xí)道路評分函數(shù)的神經(jīng)網(wǎng)絡(luò)；（4）提出了一種GPS 軌跡數(shù)據(jù)標(biāo)注方法；（5）通過公開數(shù)據(jù)集,驗(yàn)證了方法的有效性。

1 相關(guān)工作

1.1 地圖匹配

目前地圖匹配的研究大致可分為2種:特定數(shù)據(jù)來源下，引入新的數(shù)學(xué)模型或理論模型；引入其他數(shù)據(jù)解決地圖匹配問題。

引入新理論方法，依據(jù)所用的模型及理論可分為基于幾何特征、拓?fù)涮卣?、概率論和高級技術(shù)等方法[5]?；趲缀翁卣鞯姆椒?，利用點(diǎn)線距離、Fréchet距離、行駛方向與道路方向的夾角等幾何特征,確定GPS數(shù)據(jù)所對應(yīng)的道路[9-10]?；谕?fù)涮卣鞯姆椒?，將路網(wǎng)抽象成圖等拓?fù)浣Y(jié)構(gòu)，實(shí)現(xiàn)地圖匹配[11]。概率法，運(yùn)用歷史數(shù)據(jù)或?qū)＜抑R建立概率模型,來判斷GPS數(shù)據(jù)的對應(yīng)道路[12]。高級技術(shù)法[13-15]，在數(shù)據(jù)的幾何、拓?fù)?、概率法的基礎(chǔ)上建立運(yùn)算模型,如機(jī)器學(xué)習(xí)模型,通過這些模型，綜合數(shù)據(jù)的幾何、拓?fù)洹⒏怕侍卣鞯玫降貓D匹配的結(jié)果。常用的高級技術(shù)包括貝葉斯理論[12]、模糊理論[16]、隱馬爾科夫模型(hidden Markov model,HMM)[13-14,17]、蟻群算法[15]等。此外,根據(jù)實(shí)時(shí)性,現(xiàn)有的地圖匹配方法還可分為局部方法和全局方法。局部方法[16,18-19]，利用軌跡中幾個(gè)GPS數(shù)據(jù)點(diǎn)完成匹配，具有實(shí)時(shí)性；全局匹配方法[10,13,15]，利用整條軌跡的數(shù)據(jù)點(diǎn)完成匹配，不具實(shí)時(shí)性。本文提出的屬于局部方法。

引入其他相關(guān)數(shù)據(jù)能顯著提高地圖匹配的精度，如行駛速度和行駛方向數(shù)據(jù)[13,19]。HU 等[8]引入了歷史行駛速度、周圍道路行駛速度等數(shù)據(jù)；QUDDUS 等[5]則引入了高度數(shù)據(jù)、水平位置精度因子等數(shù)據(jù)；對比相關(guān)研究[13-14,17]發(fā)現(xiàn)，利用豐富的數(shù)據(jù)較單純使用復(fù)雜的計(jì)算理論或模型更能大幅度提高地圖匹配的準(zhǔn)確率。但引入新的數(shù)據(jù)需要開展大量的數(shù)據(jù)建模工作,同時(shí)對數(shù)據(jù)的完整性有一定的要求[14]，這也限制了可應(yīng)用的數(shù)據(jù)范圍。本文提出的機(jī)器學(xué)習(xí)方法解決了該問題。

數(shù)據(jù)驅(qū)動的地圖匹配研究相對較少，ZHENG等[20]從歷史軌跡數(shù)據(jù)中挖掘軌跡模式,并用挖掘的軌跡模式來消除GPS數(shù)據(jù)的采樣誤差；GOH 等[21]提出使用SVM 學(xué)習(xí)一個(gè)函數(shù),根據(jù)數(shù)據(jù)的幾何度量和動量變化度量輸出候選道路的傳輸概率,再用HMM 綜合多種概率以獲得最終的匹配結(jié)果。然而,所有這些方法都不能直接從數(shù)據(jù)中學(xué)習(xí)地圖匹配規(guī)則,需要建立一定的數(shù)學(xué)模型,難以解決信息融合的地圖匹配問題。

1.2 神經(jīng)網(wǎng)絡(luò)和排名學(xué)習(xí)

基于幾何、拓?fù)洹⒋植诩牡貓D匹配方法表明，GPS數(shù)據(jù)與路網(wǎng)之間的關(guān)系可能由一個(gè)并不復(fù)雜的、難以確定具體表達(dá)式的函數(shù)確定，深度學(xué)習(xí)是解決這類問題的重要方法[22]。然而地圖匹配問題和深度學(xué)習(xí)解決的問題并不相似，深度學(xué)習(xí)解決的基本問題是分類和回歸。分類時(shí)，將一條道路判斷為匹配結(jié)果，會影響對另一條道路是否為匹配結(jié)果的判斷,因此，不能簡單地用分類的思路解決地圖匹配問題。回歸問題的輸出為連續(xù)量，而地圖匹配的輸出是對應(yīng)道路的編號，是一個(gè)離散量，因而無法簡單地使用回歸解決地圖匹配問題。借鑒信息檢索的思路，引入排名學(xué)習(xí)以解決連續(xù)變量到離散變量的映射問題。

排名學(xué)習(xí)是從數(shù)據(jù)中學(xué)習(xí)數(shù)據(jù)排名規(guī)則的過程[23]。根據(jù)每次學(xué)習(xí)用到的數(shù)據(jù)類型，排名學(xué)習(xí)方法可分為3類:單獨(dú)學(xué)習(xí)(pointwise)、成對學(xué)習(xí)(pair-wise)、列表學(xué)習(xí)(listwise)。已知數(shù)據(jù)的相關(guān)性評分時(shí)，可使用單獨(dú)學(xué)習(xí)法，如McRank[23]，直接從數(shù)據(jù)中學(xué)習(xí)相關(guān)性的評分規(guī)則。當(dāng)無法獲取數(shù)據(jù)的具體評分，只能獲取數(shù)據(jù)的優(yōu)劣比較時(shí)，可用成對學(xué)習(xí)法，如RankNet[24]、Lambda Rank[25]，訓(xùn)練一個(gè)數(shù)據(jù)優(yōu)劣的判斷器，間接學(xué)習(xí)評分規(guī)則。當(dāng)已知每次查詢的所有數(shù)據(jù)的排名時(shí)，可使用列表學(xué)習(xí)法，如ListNet[26]，學(xué)習(xí)一個(gè)排名列表生成器。本文選擇使用成對學(xué)習(xí)的排名學(xué)習(xí)方法。

2 相關(guān)定義及數(shù)據(jù)表示

圖1為地圖匹配問題示意圖，所示為莫斯科，比例尺為1:15 000，綠線表示路網(wǎng)，紅點(diǎn)表示未經(jīng)處理的GPS數(shù)據(jù)，藍(lán)線表示車輛的實(shí)際路徑。為便于說明，對問題涉及的數(shù)據(jù)和地圖匹配問題做形式化的定義。

定義1每條GPS 軌跡數(shù)據(jù)由一系列的GPS數(shù)據(jù)點(diǎn)構(gòu)成,表示為T:p1→p2→…→pn，其中，pi=(xi,ti,ai)，xi表示GPS數(shù)據(jù)pi的經(jīng)緯度，ti表示GPS數(shù)據(jù)pi的采樣時(shí)間，ai表示該時(shí)刻下的其他數(shù)據(jù)(如速度)。2個(gè)相鄰的GPS數(shù)據(jù)之間的時(shí)間間隔由GPS 接收設(shè)備的采樣間隔Δt=ti+1-ti決定。

圖1 地圖匹配問題示例Fig.1 Map-matching example

定義2路網(wǎng)可以表示為一個(gè)有向圖G(V,E)，其中V表示所有路段的起點(diǎn)和終點(diǎn)的集合，E={Vi?Vj|Vi,Vj?V}表示路網(wǎng)中所有路段的集合。

圖2所示為位于德國海德堡市的霍根海姆的路網(wǎng)，比例尺為1:30 000。

定義3一條數(shù)字路徑是指完全由路網(wǎng)中的邊組成的路徑，可表示為M:e1→e2→…→en，其中ei?E。

定義4地圖匹配是將GPS 軌跡數(shù)據(jù)T映射到路網(wǎng)，并找到對應(yīng)的數(shù)字路徑的過程。

圖2 霍格海姆路網(wǎng)Fig.2 The road network of Hockenheim

3 基于排名學(xué)習(xí)的地圖匹配方法

方法框架如圖3所示，由以下3 步組成:

（1）候選道路選擇。首先搜索GPS數(shù)據(jù)點(diǎn)的所有可能道路，以使排名網(wǎng)絡(luò)只需對有限的數(shù)據(jù)進(jìn)行評分，降低問題的復(fù)雜度。

圖3 基于排名學(xué)習(xí)的地圖匹配方法Fig.3 The pipeline of our method

（2）候選道路評分。使用學(xué)習(xí)所得評分函數(shù)對所有候選道路進(jìn)行相關(guān)度評分。評分網(wǎng)絡(luò)先逐層提取路網(wǎng)和軌跡的時(shí)空特征，再根據(jù)提取的特征對候選道路進(jìn)行評分。

（3）選擇匹配結(jié)果。選擇所有候選道路中相關(guān)度評分最高的道路作為匹配結(jié)果，并將前一個(gè)結(jié)果到當(dāng)前結(jié)果的最短路徑作為數(shù)字路徑。

3.1 候選道路選擇

在地圖匹配任務(wù)中，路網(wǎng)數(shù)據(jù)往往很大，導(dǎo)致匹配問題的搜索空間很大。故應(yīng)先剔除無關(guān)道路，減輕計(jì)算負(fù)擔(dān)。文獻(xiàn)[3]指出,GPS數(shù)據(jù)相對于真實(shí)位置偏差的距離近似服從正態(tài)分布，該分布可表示為

式(1)中，gti表示GPS數(shù)據(jù)點(diǎn)pi對應(yīng)的真實(shí)位置，σ是正態(tài)分布的方差表示根據(jù)兩坐標(biāo)經(jīng)緯度計(jì)算的大圓距離(great circle distance),即從pi出發(fā)沿著地球表面到gti的最短距離，詳情可參看文獻(xiàn)[27]。式(1)表明，當(dāng)?shù)缆返絧i的大圓距離很大時(shí)，該道路為真實(shí)位置所在道路的概率就很低，因此，可以將所有滿足的道路作為候選道路，其中cij，表示pi在第j條道路上的投影，r為閾值，其值的影響見實(shí)驗(yàn)部分。

例如,對于某條軌跡的某GPS數(shù)據(jù)點(diǎn)pi?Tk，有如圖4所示情況，其中ej,j=1,2,…,5表示路網(wǎng)中的5 條道路，cj表示點(diǎn)pi到道路ej上距離最短的點(diǎn)，黑色虛線表示以pi為圓心、r為半徑的圓。所有道路中，到pi的點(diǎn)線距離(如點(diǎn)pi到點(diǎn)c2、c3、c4的距離)或最小距離(如點(diǎn)pi到點(diǎn)c1、c5的距離)小于r的道路被選為候選道路。圖4中，點(diǎn)c2、c3、c4、c5位于半徑為r的虛線圓內(nèi)，故將道路e2、e3、e4、e5作為候選道路。

由于經(jīng)緯度坐標(biāo)不能無失真地投影在二維空間中，因此用以下海倫公式計(jì)算GPS點(diǎn)到道路的距離：

圖4 候選道路選擇Fig.4 The selection of candidate roads

3.2 候選道路評分

地圖匹配是從路網(wǎng)中選擇GPS數(shù)據(jù)點(diǎn)所在道路的過程，此過程也可看成是對路網(wǎng)中所有道路的排名。在實(shí)際中，容易確定GPS數(shù)據(jù)對應(yīng)的道路，即排名最高的道路，但難以獲得所有道路的完整排名，也難以獲得所有道路和GPS數(shù)據(jù)的相關(guān)性評分，因此，本文選擇成對排名學(xué)習(xí)法中的RankNet[24]作為學(xué)習(xí)方法。未經(jīng)處理的原始數(shù)據(jù)，如時(shí)序的經(jīng)緯度數(shù)據(jù)、路段起止點(diǎn)的經(jīng)緯度等不足以表達(dá)GPS和路網(wǎng)數(shù)據(jù)的時(shí)空特征，且會對后續(xù)排名學(xué)習(xí)的結(jié)果造成影響，因此，應(yīng)先對其進(jìn)行提煉。本文選擇深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)評分函數(shù)提煉數(shù)據(jù)特征，候選道路評分過程如圖3第3個(gè)流程所示。

設(shè)pi為需要匹配的GPS數(shù)據(jù)點(diǎn)，則pi可用n維特征向量qi? Rn表示。設(shè)集合D為pi的候選道路集合，則任意D中的道路ej可表示為m維特征向量，即mj? Rm。實(shí)際中，可根據(jù)已有數(shù)據(jù)的類型、數(shù)據(jù)的時(shí)空特性來選擇合適的原始數(shù)據(jù)作為特征向量。本文將在實(shí)驗(yàn)部分通過具體特征向量的選擇來說明方法的有效性。

用深度神經(jīng)網(wǎng)絡(luò)通過排名學(xué)習(xí)法學(xué)習(xí)評分函數(shù)，該函數(shù)可輸出D中每個(gè)道路與pi的相關(guān)性評分。設(shè)神經(jīng)網(wǎng)絡(luò)的輸入為uj=(qi,mj)，則評分函數(shù)可表示為F:uj?R，其中，i為GPS數(shù)據(jù)點(diǎn)的編號，j為道路的編號。由文獻(xiàn)[24]，用以下?lián)p失函數(shù)作為優(yōu)化目標(biāo)：

本文設(shè)計(jì)了圖5中的神經(jīng)網(wǎng)絡(luò)，命名為評分網(wǎng)絡(luò)。該網(wǎng)絡(luò)借鑒了殘差網(wǎng)絡(luò)[28](ResNet)、實(shí)例正則化[29](instance normalization,IN)、ReLU[30]等結(jié)構(gòu)的特點(diǎn)，使用全連接層 (fully connected neural networks,FC)來學(xué)習(xí)數(shù)據(jù)的多層表達(dá)。為了提高網(wǎng)絡(luò)對非線性關(guān)系的擬合能力，采用深層神經(jīng)網(wǎng)絡(luò)，為避免出現(xiàn)隨層數(shù)增加網(wǎng)絡(luò)性能惡化的問題，同時(shí)增強(qiáng)了網(wǎng)絡(luò)的學(xué)習(xí)能力，以加快收斂速度，降低訓(xùn)練所需數(shù)據(jù)量，本文在網(wǎng)絡(luò)中增加了殘差(residual)結(jié)構(gòu)。當(dāng)GPS數(shù)據(jù)量較少時(shí),易發(fā)生梯度消失，導(dǎo)致訓(xùn)練不收斂，本文采用實(shí)例正則化[29]解決此問題,實(shí)例正則化計(jì)算參見文獻(xiàn)[30]。由于某一區(qū)域的經(jīng)緯度數(shù)據(jù)僅在有限的幾位數(shù)字上變動，對于所有輸入神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)，本文將特征向量的每個(gè)分量的每位數(shù)單獨(dú)作為一個(gè)輸入單元。設(shè)輸入向量的維數(shù)為din，則輸入評分網(wǎng)絡(luò)的數(shù)據(jù)可表示為

式(5)中，uj? Rdin,qi為GPS數(shù)據(jù)向量，mj為某條候選道路的向量表達(dá)。設(shè)隱層神經(jīng)元數(shù)為dhid，則全連接層、ReLU層、IN層、殘差的復(fù)合函數(shù)為

式(6)中，hi為第i層神經(jīng)網(wǎng)絡(luò)的輸出，當(dāng)i為奇數(shù)時(shí)，殘差resi-2為第i-2層網(wǎng)絡(luò)的輸出，否則為零。首層全連接層W? Rdin′dhid，中間各全連接層W? Rdhid′dhid，最后一層全連接層W? Rdhid′4。經(jīng) 實(shí)驗(yàn)測試，設(shè)置評分網(wǎng)絡(luò)的隱層數(shù)dhid=64。網(wǎng)絡(luò)輸出的評分通常為一常量，為使網(wǎng)絡(luò)更易收斂，最后一層輸出四維向量，用激活函數(shù)將各維數(shù)值約束在[0,1]內(nèi)。按以下公式得到最后的評分：

式(7)中，F(xiàn)j為最后一層輸出向量的第j維分量。

3.3 評分網(wǎng)絡(luò)的訓(xùn)練

圖5 評分網(wǎng)絡(luò)結(jié)構(gòu)Fig.5 The structure of scoring network

在使用評分網(wǎng)絡(luò)前需要對其進(jìn)行有監(jiān)督的訓(xùn)練，訓(xùn)練過程如圖6所示，其中，ui、uj的定義與式(4)同。每次訓(xùn)練時(shí)，輸入ui與uj2個(gè)向量到評分網(wǎng)絡(luò)，其中一個(gè)向量的分量m對應(yīng)的道路為目標(biāo)實(shí)際所在道路，另一個(gè)對應(yīng)的為候選道路中的任意一條錯(cuò)誤道路。評分網(wǎng)絡(luò)分別輸出2個(gè)向量的相關(guān)度評分，2個(gè)相關(guān)度評分相減得oij。為了完成有監(jiān)督的神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程，需要確定正負(fù)樣本，本文采用以下做法標(biāo)記數(shù)據(jù):當(dāng)ui對應(yīng)的為目標(biāo)實(shí)際所在道路時(shí),則反之

圖6 訓(xùn)練評分網(wǎng)絡(luò)Fig.6 Training scoring network

訓(xùn)練步驟:

（1）對每一個(gè)GPS數(shù)據(jù)點(diǎn)生成候選道路集D；

（2）選取實(shí)際行駛的道路和D中任意一條非實(shí)際行駛的道路組成ui與uj對，其標(biāo)簽由本小節(jié)所述的標(biāo)記方法確定；

（3）將數(shù)據(jù)按圖6所示的結(jié)構(gòu)進(jìn)行計(jì)算，得到損失值；

（4）利用梯度下降法等優(yōu)化方法更新評分網(wǎng)絡(luò)的參數(shù)；

（5）對每個(gè)GPS點(diǎn)重復(fù)以上4 步,直至網(wǎng)絡(luò)收斂。

當(dāng)訓(xùn)練完成后，即可用評分函數(shù)對候選道路和軌跡上某一點(diǎn)的相關(guān)性進(jìn)行評分，評分最高的那條候選道路為地圖匹配結(jié)果。

3.4 算法復(fù)雜度分析

時(shí)間復(fù)雜度來自兩部分，一部分是候選道路提取，另一部分是額外信息ai的計(jì)算和神經(jīng)網(wǎng)絡(luò)輸出的計(jì)算。首先分析候選道路提取的算法復(fù)雜度。設(shè)某條GPS 軌跡有n個(gè)GPS數(shù)據(jù)點(diǎn)，對每個(gè)數(shù)據(jù)點(diǎn)需要遍歷路網(wǎng)中所有道路來尋找候選道路。設(shè)路網(wǎng)中有l(wèi)條道路，則候選道路提取的算法復(fù)雜度為O(nl)。接著再來分析另一部分的算法復(fù)雜度?？偣灿衝k個(gè)候選道路，對于每條道路可能需要最短路徑等額外信息，這部分的算法復(fù)雜度為O(llogl)。神經(jīng)網(wǎng)絡(luò)的計(jì)算復(fù)雜度是一個(gè)常量，因此第二部分的算法復(fù)雜度為O(nkllogl)，總的算法復(fù)雜度為O(nkllogl+nl)。若不計(jì)算最短路徑，則算法復(fù)雜度為O(nk+nl)，而基于HMM的地圖匹配方法的時(shí)間復(fù)雜度為O(nk2llogl)。因此，本文方法較該方法快了k倍，通常k值為20～200。

4 實(shí)驗(yàn)分析

為證明方法的有效性，將本文方法與目前公認(rèn)的效果最好的地圖匹配方法——基于HMM的地圖匹配方法[13]、速度最快的地圖匹配方法——基于夾角特征和基于距離特征的地圖匹配方法[9]進(jìn)行對比，分別從參數(shù)影響、信息融合、實(shí)際軌跡匹配結(jié)果三方面來說明。實(shí)驗(yàn)所用數(shù)據(jù)為文獻(xiàn)[32]提供的驗(yàn)證地圖匹配算法結(jié)果的公開數(shù)據(jù)，每次實(shí)驗(yàn)前，都會對照引文方法設(shè)置最佳參數(shù)。

4.1 數(shù)據(jù)說明

實(shí)驗(yàn)用數(shù)據(jù)來自莫斯科、霍普金斯、米興多夫等20個(gè)不同的城市，每個(gè)城市有且僅有一條軌跡數(shù)據(jù)。實(shí)驗(yàn)數(shù)據(jù)包含平行道路、Y 型道路、環(huán)形道路、立交橋、城市道路、鄉(xiāng)村道路等各類不同形狀的道路。路網(wǎng)數(shù)據(jù)來自O(shè)penStreetMap(OSM)提供的地圖數(shù)據(jù)。所有軌跡數(shù)據(jù)均由真實(shí)的車輛搭載GPS設(shè)備采集而來。每條軌跡含有1 500～3 000個(gè)GPS數(shù)據(jù)點(diǎn)，采樣間隔為1 s。為獲取這些軌跡的數(shù)字路徑，文獻(xiàn)[32]采用人工標(biāo)記方法標(biāo)記出了目標(biāo)的數(shù)字路徑。路網(wǎng)數(shù)據(jù)如圖7所示，由一系列首尾相連的線段組成的折線表示，每條線段有各自的編號。為便于檢索，將路網(wǎng)數(shù)據(jù)中所有長度大于60 m的線段劃分成數(shù)條小于60 m的線段。軌跡數(shù)據(jù)T是由一系列有序的數(shù)據(jù)點(diǎn)pi組成，每個(gè)數(shù)據(jù)點(diǎn)pi有3個(gè)屬性:經(jīng)度、緯度、記錄時(shí)間，數(shù)字路徑M :e1→e2→…→en由路網(wǎng)數(shù)據(jù)中一系列的路段編號組成，由于手工標(biāo)記的標(biāo)簽無GPS數(shù)據(jù)點(diǎn)所對應(yīng)的實(shí)際地理位置，只有數(shù)字路徑，本文將數(shù)字路徑中距離該GPS數(shù)據(jù)點(diǎn)最近的位置作為該GPS數(shù)據(jù)點(diǎn)的實(shí)際位置。選用pi的特征向量qi為軌跡中連續(xù)5個(gè)GPS數(shù)據(jù)點(diǎn)，即qi=(pi-2,pi-1,pi,pi+1,pi+2)，每個(gè)向量p帶有的額外屬性ai為時(shí)間戳，單位為m；選用某條候選道路上到pi的大圓距離最短的點(diǎn)作為該道路上的實(shí)際位置cj，候選道路的向量表示為mj=(A,B,cj,aj)。圖7左所示的A、B分別表示候選道路投影點(diǎn)cj所在路段的起止點(diǎn)，aj表示道路行駛方向等額外屬性。

圖7 路網(wǎng)數(shù)據(jù)Fig.7 The data of road network

采用5 折檢驗(yàn)法檢驗(yàn)匹配方法的性能。該方法以城市為單位，選擇所有城市中的80%及其中的軌跡為訓(xùn)練集，20%及其軌跡為驗(yàn)證集，訓(xùn)練集與驗(yàn)證集的軌跡、路網(wǎng)互不相交。

4.2 實(shí)驗(yàn)環(huán)境及評判標(biāo)準(zhǔn)

測試時(shí)使用的實(shí)驗(yàn)設(shè)備為Core i7-8550U,1.80 GHz的CPU;內(nèi)存為8 GB，操作系統(tǒng)為Windows 10，開發(fā)語言為python，神經(jīng)網(wǎng)絡(luò)用pytorch 搭建。地圖數(shù)據(jù)以geohash 索引的方式存儲在redis數(shù)據(jù)庫中，用lua 腳本語言實(shí)現(xiàn)快速檢索。為保證算法運(yùn)行結(jié)果的合理性，僅用lua 腳本實(shí)現(xiàn)數(shù)據(jù)的檢索，神經(jīng)網(wǎng)絡(luò)、HMM 及粗糙邏輯均用python實(shí)現(xiàn)。

訓(xùn)練時(shí),用Adadelta[33]優(yōu)化評分網(wǎng)絡(luò)，訓(xùn)練速度(learning rate)為0.1，batch size為80，rho為0.9，epsilon為10-6，使用L2 正則化項(xiàng)，大約迭代訓(xùn)練600次后收斂。這些超參數(shù)由優(yōu)化算法的類型決定，不影響評分網(wǎng)絡(luò)性能，訓(xùn)練耗時(shí)約1 h。若在GPU 下訓(xùn)練，將可大大縮短訓(xùn)練時(shí)間。

實(shí)驗(yàn)采用在地圖匹配研究領(lǐng)域普遍使用的正確的段標(biāo)識(correct segment identification，CSI)作為地圖匹配方法準(zhǔn)確率的評判標(biāo)準(zhǔn)，公式為

4.3 實(shí)驗(yàn)結(jié)果

4.3.1 搜索半徑r的選擇

參數(shù)r，即候選道路的搜索半徑，需要人工調(diào)節(jié)。前文3.1節(jié)提到，GPS數(shù)據(jù)與其真實(shí)位置的距離服從以0為中心的正態(tài)分布。當(dāng)r>3σ時(shí)，此時(shí)因搜索半徑導(dǎo)致的準(zhǔn)確率下降可忽略不計(jì)，而計(jì)算時(shí)間可顯著減少。本實(shí)驗(yàn)所用數(shù)據(jù)σ=21.2 m，r與準(zhǔn)確率和運(yùn)行時(shí)間的關(guān)系如圖8所示。隨著搜索半徑的增大，運(yùn)行時(shí)間先緩慢再顯著增長，準(zhǔn)確率先顯著再緩慢增長。當(dāng)搜索半徑r大于65 m時(shí)，隨著搜索半徑的繼續(xù)增大，準(zhǔn)確率不再顯著提高。實(shí)際中可根據(jù)數(shù)據(jù)估計(jì)σ，選擇合適的r來平衡計(jì)算時(shí)間和準(zhǔn)確率。本文選擇r=75。

4.3.2 信息融合

為驗(yàn)證本文方法在信息融合方面的表現(xiàn)及所設(shè)計(jì)的評分網(wǎng)絡(luò)的有效性，將本文方法與MLP 方法做了對比；為驗(yàn)證本文方法能夠有效融合新類型的數(shù)據(jù)，保持查詢向量qi不變，在候選道路的向量表示mi的額外屬性分量ai中依次增加道路行駛方向限制及上次匹配結(jié)果到該候選道路的最短路徑距離，并以CSI 作為結(jié)果的度量標(biāo)準(zhǔn)，實(shí)驗(yàn)結(jié)果如表1所示。結(jié)果表明,本文提出的評分網(wǎng)絡(luò)在地圖匹配問題上較直接使用MLP的準(zhǔn)確率更高。在面對新的數(shù)據(jù)時(shí)，本文方法無須重新設(shè)計(jì)新的算法，只需重新訓(xùn)練評分網(wǎng)絡(luò)。結(jié)果顯示，重新訓(xùn)練后準(zhǔn)確率有顯著提升。在不重新建模的前提下，當(dāng)?shù)缆沸旭偡较蛉笔r(shí)，基于距離特征和夾角特征的方法，只能簡單地刪除與道路行駛方向相關(guān)的公式，導(dǎo)致準(zhǔn)確率顯著降低；當(dāng)增加最短路徑距離特征時(shí)，必須重新建模來確立新舊特征關(guān)系，否則無法利用新的特征。當(dāng)缺失數(shù)據(jù)時(shí)，基于HMM 方法無法得到正確的結(jié)果。綜上所述，本文方法可以通過重新訓(xùn)練建立新的計(jì)算關(guān)系，當(dāng)數(shù)據(jù)缺失時(shí)，確保準(zhǔn)確率不會顯著降低；當(dāng)引入新數(shù)據(jù)時(shí)，能有效利用新數(shù)據(jù)提高準(zhǔn)確率。

表1 信息融合結(jié)果Table1 The result of information fusion

4.3.3 與其他方法的比較

采樣頻率與算法CIS有關(guān)，本文采用下采樣法降低軌跡的采樣頻率以獲取實(shí)驗(yàn)所需數(shù)據(jù)。為保證采樣頻率降低后點(diǎn)數(shù)不變，當(dāng)采樣頻率降至原來的后，原軌跡也就被等分成了n個(gè)子軌跡，軌跡總數(shù)增大為原來的n倍，總的GPS數(shù)據(jù)點(diǎn)數(shù)目不變。圖9為各方法在不同采樣間隔下CIS的變化情況，發(fā)現(xiàn)本文方法取得了與基于HMM的地圖匹配方法相當(dāng)?shù)男Ч?，同時(shí)本文方法無須HMM 方法所需的大量未來軌跡數(shù)據(jù)，具有實(shí)時(shí)性優(yōu)勢。當(dāng)采樣時(shí)間增大時(shí)，本文方法的基于最短路徑數(shù)據(jù)的版本的準(zhǔn)確率會收斂至無額外屬性版本。

圖9 CIS與采樣間隔的關(guān)系Fig.9 The relationship between CIS and sampling period

GPS數(shù)據(jù)點(diǎn)數(shù)目與算法運(yùn)行時(shí)間有關(guān)，圖10為各方法在不同GPS數(shù)據(jù)點(diǎn)數(shù)目下的運(yùn)行時(shí)間，從中可看出，本文方法相對基于隱馬爾科夫模型方法在運(yùn)算速度上具有顯著優(yōu)勢，接近于基于夾角特征和基于距離特征的地圖匹配方法，同時(shí),本文的不基于最短路徑屬性版本在耗時(shí)上和基于夾角特征與基于距離特征的地圖匹配方法相近。

圖10 運(yùn)行時(shí)間與軌跡點(diǎn)數(shù)的關(guān)系Fig.10 The relationship between run time and the number of points of a trajectory

5 結(jié) 語

提出了一種基于數(shù)據(jù)驅(qū)動思路的地圖匹配方法，該方法將地圖匹配問題轉(zhuǎn)換為信息檢索問題，并用排名學(xué)習(xí)和深度神經(jīng)網(wǎng)絡(luò)直接從數(shù)據(jù)中學(xué)習(xí)地圖匹配規(guī)則，無須建立具體明確的計(jì)算表達(dá)式，可快速融合新數(shù)據(jù)，適合需要融合多源信息的地圖匹配問題。實(shí)驗(yàn)表明，該方法易于融合新數(shù)據(jù)，在準(zhǔn)確率方面接近目前最準(zhǔn)確的地圖匹配算法——基于HMM的地圖匹配方法，且運(yùn)行速度更快，運(yùn)行時(shí)間接近基于夾角特征和基于距離特征的地圖匹配方法。

當(dāng)然，該方法仍有很多需要完善的方面。首先，沒有從路網(wǎng)本身出發(fā)去學(xué)習(xí)需要的信息，而是把路網(wǎng)抽象成路段的向量表示；其次，沒有完美解決兩相鄰GPS數(shù)據(jù)點(diǎn)之間的軌跡確定問題，目前采用的策略是默認(rèn)相鄰兩位置之間的軌跡是最短路徑。此外，該方法目前只用到了局部信息和增量信息，沒有用到全局信息。未來將著手研究如何利用軌跡的全局特征來提高地圖匹配的準(zhǔn)確率。