基于排名學習和多源信息的地圖匹配方法

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

（1.合肥工業大學 計算機與信息學院,安徽合肥230601；2.浙江大學 計算機科學與技術學院,浙江 杭州310058）

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

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

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

通過學習評分函數來確定計算模型,隱式地使用數據的幾何特征、拓撲特征、概率特征及軌跡的時空關系來完成地圖匹配,而非事先定義的計算公式。因此，本方法可用于特定類型數據及拓展數據的情形。本文的主要貢獻包括:（1）設計了一個數據驅動的地圖匹配框架；（2）基于RankNet 設計了適用于地圖匹配任務的排名學習方法；（3）設計了用于學習道路評分函數的神經網絡；（4）提出了一種GPS 軌跡數據標注方法；（5）通過公開數據集,驗證了方法的有效性。

1 相關工作

1.1 地圖匹配

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

引入新理論方法，依據所用的模型及理論可分為基于幾何特征、拓撲特征、概率論和高級技術等方法[5]。基于幾何特征的方法，利用點線距離、Fréchet距離、行駛方向與道路方向的夾角等幾何特征,確定GPS數據所對應的道路[9-10]。基于拓撲特征的方法，將路網抽象成圖等拓撲結構，實現地圖匹配[11]。概率法，運用歷史數據或專家知識建立概率模型,來判斷GPS數據的對應道路[12]。高級技術法[13-15]，在數據的幾何、拓撲、概率法的基礎上建立運算模型,如機器學習模型,通過這些模型，綜合數據的幾何、拓撲、概率特征得到地圖匹配的結果。常用的高級技術包括貝葉斯理論[12]、模糊理論[16]、隱馬爾科夫模型(hidden Markov model,HMM)[13-14,17]、蟻群算法[15]等。此外,根據實時性,現有的地圖匹配方法還可分為局部方法和全局方法。局部方法[16,18-19]，利用軌跡中幾個GPS數據點完成匹配，具有實時性；全局匹配方法[10,13,15]，利用整條軌跡的數據點完成匹配，不具實時性。本文提出的屬于局部方法。

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

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

1.2 神經網絡和排名學習

基于幾何、拓撲、粗糙集的地圖匹配方法表明，GPS數據與路網之間的關系可能由一個并不復雜的、難以確定具體表達式的函數確定，深度學習是解決這類問題的重要方法[22]。然而地圖匹配問題和深度學習解決的問題并不相似，深度學習解決的基本問題是分類和回歸。分類時，將一條道路判斷為匹配結果，會影響對另一條道路是否為匹配結果的判斷,因此，不能簡單地用分類的思路解決地圖匹配問題。回歸問題的輸出為連續量，而地圖匹配的輸出是對應道路的編號，是一個離散量，因而無法簡單地使用回歸解決地圖匹配問題。借鑒信息檢索的思路，引入排名學習以解決連續變量到離散變量的映射問題。

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

2 相關定義及數據表示

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

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

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

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

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

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

定義4地圖匹配是將GPS 軌跡數據T映射到路網，并找到對應的數字路徑的過程。

圖2 霍格海姆路網Fig.2 The road network of Hockenheim

3 基于排名學習的地圖匹配方法

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

（1）候選道路選擇。首先搜索GPS數據點的所有可能道路，以使排名網絡只需對有限的數據進行評分，降低問題的復雜度。

圖3 基于排名學習的地圖匹配方法Fig.3 The pipeline of our method

（2）候選道路評分。使用學習所得評分函數對所有候選道路進行相關度評分。評分網絡先逐層提取路網和軌跡的時空特征，再根據提取的特征對候選道路進行評分。

（3）選擇匹配結果。選擇所有候選道路中相關度評分最高的道路作為匹配結果，并將前一個結果到當前結果的最短路徑作為數字路徑。

3.1 候選道路選擇

在地圖匹配任務中，路網數據往往很大，導致匹配問題的搜索空間很大。故應先剔除無關道路，減輕計算負擔。文獻[3]指出,GPS數據相對于真實位置偏差的距離近似服從正態分布，該分布可表示為

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

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

由于經緯度坐標不能無失真地投影在二維空間中，因此用以下海倫公式計算GPS點到道路的距離：

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

3.2 候選道路評分

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

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

用深度神經網絡通過排名學習法學習評分函數，該函數可輸出D中每個道路與pi的相關性評分。設神經網絡的輸入為uj=(qi,mj)，則評分函數可表示為F:uj?R，其中，i為GPS數據點的編號，j為道路的編號。由文獻[24]，用以下損失函數作為優化目標：

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

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

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

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

3.3 評分網絡的訓練

圖5 評分網絡結構Fig.5 The structure of scoring network

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

圖6 訓練評分網絡Fig.6 Training scoring network

訓練步驟:

（1）對每一個GPS數據點生成候選道路集D；

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

（3）將數據按圖6所示的結構進行計算，得到損失值；

（4）利用梯度下降法等優化方法更新評分網絡的參數；

（5）對每個GPS點重復以上4 步,直至網絡收斂。

當訓練完成后，即可用評分函數對候選道路和軌跡上某一點的相關性進行評分，評分最高的那條候選道路為地圖匹配結果。

3.4 算法復雜度分析

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

4 實驗分析

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

4.1 數據說明

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

圖7 路網數據Fig.7 The data of road network

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

4.2 實驗環境及評判標準

測試時使用的實驗設備為Core i7-8550U,1.80 GHz的CPU;內存為8 GB，操作系統為Windows 10，開發語言為python，神經網絡用pytorch 搭建。地圖數據以geohash 索引的方式存儲在redis數據庫中，用lua 腳本語言實現快速檢索。為保證算法運行結果的合理性，僅用lua 腳本實現數據的檢索，神經網絡、HMM 及粗糙邏輯均用python實現。

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

實驗采用在地圖匹配研究領域普遍使用的正確的段標識(correct segment identification，CSI)作為地圖匹配方法準確率的評判標準，公式為

4.3 實驗結果

4.3.1 搜索半徑r的選擇

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

4.3.2 信息融合

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

表1 信息融合結果Table1 The result of information fusion

4.3.3 與其他方法的比較

采樣頻率與算法CIS有關，本文采用下采樣法降低軌跡的采樣頻率以獲取實驗所需數據。為保證采樣頻率降低后點數不變，當采樣頻率降至原來的后，原軌跡也就被等分成了n個子軌跡，軌跡總數增大為原來的n倍，總的GPS數據點數目不變。圖9為各方法在不同采樣間隔下CIS的變化情況，發現本文方法取得了與基于HMM的地圖匹配方法相當的效果，同時本文方法無須HMM 方法所需的大量未來軌跡數據，具有實時性優勢。當采樣時間增大時，本文方法的基于最短路徑數據的版本的準確率會收斂至無額外屬性版本。

圖9 CIS與采樣間隔的關系Fig.9 The relationship between CIS and sampling period

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

圖10 運行時間與軌跡點數的關系Fig.10 The relationship between run time and the number of points of a trajectory

5 結 語

提出了一種基于數據驅動思路的地圖匹配方法，該方法將地圖匹配問題轉換為信息檢索問題，并用排名學習和深度神經網絡直接從數據中學習地圖匹配規則，無須建立具體明確的計算表達式，可快速融合新數據，適合需要融合多源信息的地圖匹配問題。實驗表明，該方法易于融合新數據，在準確率方面接近目前最準確的地圖匹配算法——基于HMM的地圖匹配方法，且運行速度更快，運行時間接近基于夾角特征和基于距離特征的地圖匹配方法。

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