基于集成樸素貝葉斯模型的在線地圖匹配方法

韓京宇，陳可佳，劉茜萍

（南京郵電大學 計算機學院 計算機技術研究所，江蘇 南京210003）

0 引 言

交通路網(wǎng)上移動對象追蹤是智能交通、實時導航等位置相關服務的關鍵技術。其中地圖匹配即移動對象實時采集的GPS經(jīng)緯度坐標準確映射到電子地圖上，是實現(xiàn)路網(wǎng)上移動對象跟蹤或交通流分析的前提。由于GPS誤差（幾米到十幾米）和地圖數(shù)據(jù)本身的誤差，準確的地圖匹配是一個難點問題［1］。目前地圖匹配分成離線全局算法和在線局部算法。前者根據(jù)軌跡上的觀測點序列來匹配最可能的交通路網(wǎng)［1－4］，這類方法不僅具有較高的計算復雜度，而且不能滿足在線地圖匹配的要求。在線局部算法主要根據(jù)前一個已經(jīng)匹配的路網(wǎng)點和當前的觀測點來匹配路網(wǎng)［1，3，5－7］。目前這些方法主要根據(jù)各種空間距離相似度、拓撲結構等來判斷匹配的路網(wǎng)，不能夠?qū)Ψ强臻g因素和歷史匹配軌跡加以利用，匹配精度不夠理想。

歷史是最好的老師，本文提出根據(jù)歷史軌跡訓練樸素貝葉斯模型，充分量化各種非確定因素，實現(xiàn)在線地圖的概率匹配。同時，為了克服數(shù)據(jù)噪聲和單個模型假設的偏差，采用集成學習（ensemble learning）技術訓練多個匹配器，通過投票來確定最可能匹配的路網(wǎng)。本方法不僅考慮了空間、時間、拓撲等可直接觀測因素，同時考慮了各種隱含因素對道路選擇的影響，可以取得更好的匹配效果。

1 移動對象的地圖匹配框架

一個典型的移動對象應用中，成千上萬的移動對象在路網(wǎng)上運動，每個移動對象根據(jù)一定的位置匯報策略，不斷將其當前觀測點信息發(fā)送到服務器。服務器進行在線地圖匹配，并存儲和索引移動對象的軌跡，以響應從客戶端發(fā)來的各種查詢［8－10］。整個系統(tǒng)如圖1所示。在這個系統(tǒng)中涉及到如下基本概念。

圖1 路網(wǎng)上的移動對象管理框架

定義1 GPS軌跡：GPS軌跡T＝（g1，…，gi，…，gn）是一個GPS觀測點序列，每個觀測點gi＝（lat，lng，v，st），其中l(wèi)at是觀測點緯度，lng 是觀測點經(jīng)度，v 是觀測點瞬時速度，st是觀測點時間。

定義2 交通路網(wǎng)：交通路網(wǎng)G 定義為G＝（R，J），其中R 是路段集合，J 是路口結點集合。

定義3 路段：路段r＝（rid，start，end，len，geo），其中，rid 是道路標志，start是起點，end 是終點，len 是道路長度。geo是道路幾何形狀，用一條折現(xiàn)pl來表示，即pl＝（pi－1，pi）i＝1n，其中p0是pl的起點，pn是道路的終點，每個pi－1pi是一個線段。

定義4 結點：結點j 定義為j＝（jid，loc），其中jid是路網(wǎng)結點標志，loc＝（x，y）是j的地理位置坐標。

定義5 路徑：給定路網(wǎng)上的兩個點vi和vj，從點vi到點vj的一條路徑ph 是前后相連的路段序列ph＝r1→r2→…→rn，其中r1.start＝vi，rn.end＝vj。

在移動對象運動中，給定移動對象當前GPS 觀測點gi、前一個觀測點gi－1和其匹配的路網(wǎng)位置點pi－1，地圖匹配計算gi在路網(wǎng)上的位置點pi。

本文提出根據(jù)歷史GPS軌跡的對應路徑，采用集成學習策略訓練多個樸素貝葉斯分類器進行地圖匹配，最大程度地減小可能的誤差。方法框架如下所述：

（1）對歷史軌跡進行離線訓練，采用集成學習技術，確定多個樸素貝葉斯分類器。

（2）對路網(wǎng)進行預處理，建立網(wǎng)格 （grid）索引GI［10］，以支持在線地圖匹配中對觀測點附件路段的快速檢索。

（3）根據(jù)上一個匹配點pi－1和當前觀測點gi，取pi－1和gi的歐式距離為搜索半徑，在網(wǎng)格索引GI上以gi為圓心檢索所有可能匹配的路段｛r1，r2，…，rn｝。然后，根據(jù)多個貝葉斯分類器的投票結果來預測最可能匹配的邊。

在上述計算過程中，經(jīng)常度量觀測點到一個路段的距離，定義如下。

定義6 點線投影：給定一個GPS觀測點gi和一個待匹配路段rj，gi在rj上的投影點pi應當滿足

式中：dist（ck，gi）——ck和gi的歐氏距離。

定義7 點線垂直距離：給定一個GPS觀測點gi和一個待匹配的邊rj，gi到rj的垂直距離是gi到其在rj上投影點的歐氏距離。

2 地圖匹配算法

本文綜合考慮天氣（wea）、時間段（time）、道路等級（level）、垂直距離（ds）、偏離夾角（di）、行程速度（sp）進行路網(wǎng)匹配。各因素含義如下：

（1）wea表示天氣狀況，取晴天、陰天和雨雪3 個不同的離散值。不同的天氣，車輛傾向于選擇不同的路段。

（2）time代表當前時間段，取離散值。不同的時間段由于作息規(guī)律、日照、燈光等原因，車輛對道路有不同的選擇傾向。

（3）level代表道路等級，是離散變量，分成快速路、主干路、次干路和支路。一般來說，用戶傾向于選擇寬敞、快速的高等級路段。

（4）ds代表當前觀測點到匹配路段的垂直距離，即點線垂直距離。一般來說，點線垂直距離越短，匹配該路段的概率越大。

（6）sp 代表從前一個觀測點到當前觀測點時間內(nèi)的平均行駛速度。不同道路有不同的規(guī)定行駛速度。假設從pi－1到pi的路程為s，則s／（ti－ti－1）應該以高的概率擬合pi所在路段的規(guī)定速度。該變量充分考慮時間因素。

除上述可直接觀測因素外，道路選擇還受安全狀況、擁堵狀況、周邊環(huán)境等因素的影響。這些因素很難以直接觀測，但會通過大量的路徑選擇體現(xiàn)出來。為此，通過對歷史軌跡的分析，獲得道路選擇的概率模型。

2.1 樸素貝葉斯模型的應用和訓練

對歷史GPS軌跡匹配進行挖掘分析，確定不同天氣和時間段的樸素貝葉斯模型參數(shù)庫，記為B。bp（wea＝a，time＝b）∈B 表示天氣為a，時間段為b的樸素貝葉斯模型。確定了針對不同天氣和時間段的模型參數(shù)后，對各個天氣和時間段的GPS觀測點按照算法1進行地圖匹配。

算法1：matchBySingleBayes

輸入：已經(jīng)匹配的路徑p0，…，pi－1；觀測數(shù)據(jù)G＝（w，t，g），w、t、g 分別代表天氣、時間段和GPS觀測點；模型庫B；索引GI；匹配半徑ρ

輸出：觀測點G.g 的匹配點pi

（1）以GPS觀測點g 為圓心，根據(jù)半徑ρ查詢GI 索引，獲得m 條可能匹配路段｛r1，…，rk，…，rm｝。

（2）針對每個可能匹配路段rk計算level，ds，di，sp這4個特征變量（levelk，dsK，dik，spK），記為Xk＝（x1，…，x4）。

（3）在B 中選取滿足bp.wea＝w 并且bp.time＝t的樸素貝葉斯模型。根據(jù)bp 和g，計算各個條件概率p（xj｜rk）（1≤j≤4，1≤k≤m）。

（5）在m 個路段中，選取滿足p（rd｜g）≥p（rw｜g）（1≤w≤m）的路段rd。

（6）返回g 在rd的投影點。

道路等級參數(shù)學習：車輛行駛時，以不同的概率選擇不同的道路等級。對相同的天氣、時間段的所有GPS匹配路網(wǎng)進行如下統(tǒng)計：

（1）針對某類相同的天氣和時間段，假設所有匹配的路徑共包含n個點（p1，…，pn），將其分割成n－1個相鄰匹配對（pi－1，pi）（2≤i≤n）。

（2）用ym和yn分別表示匹配點pi－1和pi的道路等級，可得

垂直距離參數(shù)學習：給定一個GPS觀測點g，其到路段r的垂直距離按照定義7計算。距離越短，觀測點屬于r的概率越大。對相同的天氣和時間段，匹配r 的點到r 的垂直距離服從高斯分布

這里x＝dist（g，r）代表g 到路段r 的垂直距離，u取0。方差在歷史數(shù)據(jù)上挖掘獲得，其無偏估計為

這里xi表示訓練樣本上觀測點到匹配路段的垂直距離，?。?。

這里夾角期望取uθ＝0，在訓練樣本上學習：針對相同天氣和時間段，根據(jù)每一個路段上的所有匹配點，計算的無偏估計量。

行程速度參數(shù)學習：相對前一個匹配點pi－1，g 的n個可能的匹配點產(chǎn)生n 條可能的路徑。在時間ti－ti－1內(nèi)移動對象行駛的路程以高的概率擬合其行駛的速度。具體計算步驟如下：

（1）對于每一個可能的匹配點pi，采用改進的A＊算法在線計算pi－1pi的最短路徑［11］，進而確定其行駛的路程，記為s。計算最短路徑時，為了避免搜索過度，在grid索引上，以g為圓心，在vmax（ti－ti－1）半徑范圍內(nèi)采用A＊算法進行搜索，其中vmax＝max（vi－1，vi）。

（2）計算可能匹配路段上的平均速度v＝s／（ti－ti－1）。

（3）在各個路段r上，速度分布符合高斯分布

這里uv代表該路段的速度期望，δ2v為該路段的速度方差。

不同的天氣和時間段，不同的路段會有不同的速度期望和方差。針對不同天氣和時間段，計算各個路段上的速度參數(shù)：uv和的無偏估計分別是和

2.2 集成學習算法設計

為了克服數(shù)據(jù)噪聲和單個分類假設的偏差，在訓練樣本集合上，對不同樣本賦予不同的權重，學習多個分類假設。算法如下所示。

算法2：ensembleLearningClassifier

輸入：樸素貝葉斯匹配器個數(shù)M，訓練樣本Ω＝｛（E1，c1），…，（EN，cN）｝

輸出：匹配器集合｛CF1，…，CFM｝，匹配器的權重向量wc

返回分類器集合｛CF1，…，CFM｝和權重向量wc；

算法輸入中Ei代表訓練樣本特征即（wea，time，level，ds，di，sp），ci表示匹配結果。首先賦予每個樣本初始權重1／N，這里N 代表訓練樣本數(shù)目。在樣本集合上訓練得到第一個分類器CF1。在測試過程，這個匹配器會將有些GPS軌跡點正確匹配，有些錯誤匹配。為了提高匹配精度，在新一輪迭代中，提高被錯誤匹配的樣本的權重，同時降低正確匹配的樣本的權重，產(chǎn)生匹配器CF2。如此程持續(xù)，產(chǎn)生M 個匹配器。

給定一個觀測點g，M 個匹配器依據(jù)權重投票決定匹配路段，從而獲得準確魯棒的匹配結果。

3 實 驗

以南京市區(qū)地圖為基礎，分別在實際軌跡數(shù)據(jù)和模擬軌跡數(shù)據(jù)上實驗。南京市區(qū)地圖從openmap 上下載（http：／／www.openstreetmap.org／），有732條道路，2432個交叉路口。道路等級通過人工確認標注，分成快速路、主干路、次干路和支路。實際的車輛在南京市道路上跑，對10輛安裝了GPS的車輛附加了用單片機燒寫的位置更新協(xié)議。收集了30天的實際數(shù)據(jù)，選取其中涉及40 條道路的軌跡數(shù)據(jù)，人工進行匹配確認。天氣數(shù)據(jù)從http：／／www.weather.com.cn／上獲得。模擬軌跡數(shù)據(jù)在南京市區(qū)地圖上產(chǎn)生。具體模擬過程如下：100個移動對象在路網(wǎng)上不間斷地運行48個小時，每隔30～60秒取一個GPS觀測點。不同天氣｛晴天、陰天、雨雪｝、時間段（一天分成12 個等長的時間段）和道路等級采用不同的速度參數(shù)。對每個GPS觀測點根據(jù)高斯函數(shù)產(chǎn)生垂直距離、方向角偏差。不同的交叉路口采用不同的路段選擇概率。表1給出了模擬數(shù)據(jù)的參數(shù)設置。

表1 模擬GPS軌跡參數(shù)

地圖匹配精度prec定義如下

3.1 地圖匹配性能分析

（1）搜索半徑ρ對性能的影響

地圖匹配時每次以ρ為半徑在索引上查找可能匹配的路段，半徑ρ越大，可能匹配的路段數(shù)目越多。設定ρ＝100，200，300，400，500，600米。圖2 顯示了在實際數(shù)據(jù)集和模擬數(shù)據(jù)集上隨著搜索半徑的增大，匹配精度的變化。從圖2可以看出隨著半徑的增大，匹配精度起初線性提高。隨后，伴隨搜索半徑的增大，精度提高迅速衰減。當達到一定數(shù)值后，隨著半徑增大，精度幾乎沒有變化。這是由于當搜索半徑很小時，某些本該匹配的路段會丟失。隨著搜索半徑的增大，丟失的概率會變小，從而取得更高的匹配精度。但當半徑達到一定程度后，新增加的備選路段一般不會是匹配的路段，因此精度不會再繼續(xù)提高。

圖2 匹配精度隨搜索半徑變化（實際和模擬數(shù)據(jù)）

（2）匹配器數(shù)目M 對精度的影響

該實驗驗證了集成多個匹配器的效果。圖3顯示了在實際數(shù)據(jù)集和模擬數(shù)據(jù)集上匹配精度隨M 的變化。從圖上可以看出，隨著M 的增大，路網(wǎng)匹配的精度隨之提高。在實際數(shù)據(jù)集上當M 達到6以后，在模擬數(shù)據(jù)集上M 增大到8以后，隨著M 的增大，匹配精度基本上趨于穩(wěn)定。

圖3 匹配精度隨M 變化（實際和模擬數(shù)據(jù)）

3.2 相關工作比較

本文方法，記為BA 和文獻［1］中的greedy算法進了比較。文獻［1］中根據(jù)垂直距離和偏離夾角來判斷最可能匹配的路段。兩種方法在不同的數(shù)據(jù)規(guī)模上取10次匹配精度的平均值，圖4匯報了在實際數(shù)據(jù)和模擬數(shù)據(jù)上的匹配精度比較。從圖上可以看出本文提出的方法穩(wěn)定地優(yōu)于文獻［1］中提出的方法。主要原因在于本文方法不僅考慮了各種不能直接觀測到的影響因素。而且針對不同天氣和時間段，利用歷史數(shù)據(jù)來訓練概率模型，針對不同路段獲得精準的模型參數(shù)，從而獲得更好的匹配效果。

4 結束語

圖4 性能比較（實際和模擬數(shù)據(jù)）

本文根據(jù)歷史數(shù)據(jù)訓練地圖匹配的樸素貝葉斯模型；同時，為了克服數(shù)據(jù)噪聲和單個模型的偏差，采用集成學習策略訓練多個匹配器。在線地圖匹配時，多個匹配器投票確定地圖匹配點。本文的主要貢獻在于：①提出根據(jù)歷史數(shù)據(jù)訓練樸素貝葉斯模型進行在線地圖匹配，給出了各個概率參數(shù)的計算方法。②采用集成學習技術來提高匹配的精度和魯棒性。

在實際數(shù)據(jù)和模擬數(shù)據(jù)上的實驗表明該方法可以獲得好的在線地圖匹配性能。下一步研究將結合軌跡衍生模型進一步提高地圖匹配性能。

［1］Matt Weber，Liu Ling，Kipp Jones，et al.On map－matching of wireless positioning data：A selective look－ahead approach［C］／／Proc of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems，2010：290－299.

［2］Lou Yin，Zhang Chengyang，Zheng Yu，et al.Map－matching for low－sampling－rate GPS trajectories ［C］／／Proc of 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，2009：352－361.

［3］Paul Newson，John Krumm.Hidden Markov map matching through noise and sparseness ［C］／／Proc of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，2009：336－343.

［4］Stefan funke，sabine storandt.Path shapes：An alternative method for map matching and fully autonomous self－localization［C］／／Proc of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，2011：319－328.

［5］Ahmed Jawad，Kristian Kersting.Kernelized map matching［C］／／Proc of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems，2010：454－457.

［6］Adel Javanmard，Maya Haridasan，Li Zhang.Poster：Multitrack map matching ［C］／／Proc of the 10th International Conference on Mobile Systems，Applications，and Services，2012：503－504.

［7］SHEN Bin，JIANG Changjun，ZHANG Zhaohui，et al.Design and realization of a distributed map－matching system for massive GPS data［J］.Journal of Chinese Computer Systems，2007，28 （3）：479－481 （in Chinese）. ［沈斌，蔣昌俊，章昭輝，等.一種基于海量GPS 數(shù)據(jù)的分布式地圖匹配系統(tǒng)的設計與實現(xiàn) ［J］.小型微型計算機系統(tǒng)，2007，28 （3）：479－481.］

［8］DING Zhiming.Data model，query language，and real－time traffic flow analysis in dynamic transportation network based moving objects databases［J］.Journal of Software，2009，20（7）：1866－1884 （in Chinese）. ［丁治明.移動對象數(shù)據(jù)庫模型、查詢語言及實時交通流分析 ［J］.軟件學報，2009，20（7）：1866－1884.］

［9］Nguyen T，He Z，Zhang R.Boosting moving object indexing through velocity partitioning ［C］／／Proceedings of the VLDB Endowment，2012，5 （9）：860－871.

［10］ZHOU Aoying，YANG Bin，JIN Cheqing，et al.Locatonbased service：Architecture and progress ［J］.Chinese Journal of Computers，2011，34 （7）：1155－1171 （in Chinese）.［周傲英，楊彬，金澈清，等.基于位置的服務：架構與進展［J］.計算機學報，2011，34 （7）：1155－1171.］