基于海量公交軌跡數據挖掘的地圖匹配算法

陳 輝，蔣圭峰，姜桂圓，武繼剛

(1.廣東工業大學 計算機學院，廣州 510006； 2.南洋理工大學 計算機科學與工程學院，新加坡 新加坡 639798)(*通信作者電子郵箱1164115502@qq.com)

0 引言

隨著全球定位系統(Global Positioning System, GPS)技術的普及，基于車載GPS設備的軌跡數據挖掘已成為城市智能交通系統和定位服務研究的熱點。尤其是海量的GPS軌跡數據為許多智能交通服務(如路徑規劃、實時導航和流行路線查詢等應用)提供了數據支撐。然而實現上述各種服務的一個前提是能夠將GPS軌跡數據準確地與數字地圖上的道路相匹配(地圖匹配)，即使用車輛產生的GPS軌跡數據與底層道路拓撲網絡相關聯以獲得車輛行駛的準確路線。

由于多種物理因素和現實原因，通過GPS獲得的軌跡數據與實際道路之間存在偏差，造成了軌跡匹配的不確定性。導致這些不確定的因素有很多，如測量誤差、采樣誤差、傳感器故障或傳輸錯誤導致的數據丟失，因此正確識別行駛路段的地圖匹配變得具有挑戰性。Lu等[1]首先研究了基于軌跡匹配的不確定性，并提出了一種可視化方法來分析軌跡的不確定性。GPS設備精度導致的測量誤差以及低采樣率引起的采樣誤差使得地圖匹配算法在處理低頻軌跡數據方面面臨困難。針對低頻軌跡數據，目前主流算法大致可分為基于隱馬爾可夫模型(Hidden Markov Model， HMM)[2]和考慮時空因素的基于時空匹配模型(Time and Space Matching Model， TSMM)[3]。Jan-Henrik等[4]在行人軌跡匹配場景中基于HMM提出了針對道路數據不完整情景的匹配方案，充分利用行人軌跡特點，應用HMM對轉移概率和表現概率直接建模，簡單有效，但匹配效果不甚理想且只針對特定應用場景，有一定的局限性。Liu等[5]提出一種全局時空地圖匹配方法——時空條件隨機場(Space-Time Conditional Random Field， STCRF)，結合了時空信息，條件隨機場模型解決了標注偏置問題，去除了HMM中兩個不合理的假設，但模型變得復雜，效率也降低。Hu等[6]提出了一種使用多元復合信息(在經度、緯度、時間戳信息的基礎上添加了速度、方向信息)描述移動物體的地圖匹配模型，融合了多種相關信息，但需要更多更全面的軌跡數據；Yuan等[7]進一步研究了基于時空的匹配算法——基于交互式投票的地圖匹配(Interactive Voting Map Matching， IVMM)，它考慮了GPS軌跡的上下游位置信息的關系等其他因素。上述兩文獻在綜合信息的前提上取得不錯的匹配效果，但數據的信息維度過于全面和復雜，不適用于公交軌跡路線的匹配。

與上述研究相比，本文充分考慮了公交車線路與其他車輛的軌跡路線的不同之處：行車路線固定、多車同路線、運營時間規律、不間斷、沿線路車站位置固定準確等特點，利用少量的數據信息維度(公交站點、軌跡點)，通過一種基于海量軌跡數據挖掘的方法獲得匹配軌跡序列，最后采用較為簡單高效的HMM，取得良好效果。尤其需要指出的是，在處理低頻軌跡數據的地圖匹配時，現有方法試圖構造最短連通道路以連接2個相距較遠的軌跡節點，這種方法并不適用于公交軌跡數據，這是因為公交車線路并非刻意穿越最短旅行的路徑，相反的，公交車線路為了方便更多的乘客會選擇較長的路徑。在公交軌跡數據挖掘中，融合多車同路線的不同時刻的軌跡數據面臨諸多挑戰：軌跡點的雜亂無序(不同時刻不同車輛采集得到)、數據存在測量誤差、有較多異常數據等。為此，本文還將結合幾何圖形學、拓撲結構、模糊處理等理論方法。最后在實驗部分，本文還提出了一種針對無標簽數據驗證的情況下，度量公交路線地圖匹配結果精確度的可行方案。

1 相關工作

1.1 相關概念與定義

定義1 道路距離。道路兩點之間沿地球表面的實際路面距離。

現實公交路線中路況比較復雜，根據路段的形狀，大致可分為直線型、折線型、曲線型等，根據車道類別一般還可分為單向道、雙向道，如圖1所示。

圖1 道路類型

(1)

圖2 曲度計算

(2)

偏離度D表征了道路外的一點與該道路的靠近程度，該點越靠近道路偏離度越低；反之離道路越遠偏離度越高。

圖3 偏離度

1.2 HMM地圖匹配算法

地圖匹配算法以物體移動的位置序列為輸入，得到物體移動過程所走過的連續道路序列。由于各種誤差帶來的噪聲點，單純地匹配每個點離它最近的道路將導致非常不合理，甚至出現循環行駛路徑。HMM地圖匹配算法以一定規則平滑地整合噪聲數據，結合道路網絡的連通性控制約束條件，計算多條可能路徑的匹配概率，進而從中選擇出一條最佳旅行路徑。主要思想如下(如圖4)：對于t1時刻的待匹配點P，離它較近的有三條路段(實際候選路段)，分別標記為R1、R2、R3(實心圓表示)；t2時刻待匹配點P附近有兩條可匹配路段R1、R2，t3時刻待匹配點P附近有一條可匹配路段R1。從t1到t3時刻車輛的真實行駛路段的可能情況就有6種：R1t1→R1t2→R1t3，R1t1→R2t2→R1t3，R2t1→R1t2→R1t3，R2t1→R2t2→R1t3，R3t1→R1t2→R1t3，R3t1→R2t2→R1t3。HMM地圖匹配算法考慮所有路段Ri以及道路段之間的所有過渡情況，然后找到與實際行駛路徑可能性最大的一條路徑作為t1到t3時刻的最終行駛路徑(具體算法細節請參閱文獻[2])。

圖4 路徑搜索

2 公交路線地圖匹配

2.1 公交路線地圖匹配完整過程與思路

為更清晰地描述本文設計的基于海量公交歷史軌跡數據挖掘的地圖匹配算法，首先給出公交路線地圖匹配過程的完整流程示意圖，如圖5所示。圖5中，構建“高頻、有序軌跡序列”是本文重點研究內容，即從海量低頻、無序軌跡數據中構建出高質量的高頻有序軌跡序列，其包含“模糊插值、精準剔除”兩大處理過程。

由于公交站點序列具有有序且站點地理位置準確的特性，本文以有序公交站點作為公交路線軌跡序列的序列骨架，從大量無序的公交歷史軌跡點中提取出數量足夠、分布均勻且有序的公交軌跡點填充于序列骨架之中，形成用于公交路線地圖匹配的完整有序軌跡序列。為方便描述，令BSL=〈S1,S2,…,Si,…,Sn〉表示稀疏而有序的公交站點序列——“序列骨架”，PL={G1,G2,…,Gj,…,Gm}表示公交車歷史軌跡點的集合。據前所述：序列骨架BSL有序且稀疏，具有有序、低頻的特性；PL是軌跡點集合，具有海量、無序的屬性。精準的地圖匹配需要高質量的高頻、有序的軌跡序列點。本文從海量、無序的歷史軌跡點集合PL中選取適量的、高質量軌跡點，將其正確地插入到序列骨架BSL中，得到有序的軌跡序列RPL：

RPL=〈S1,Gp,S2,…,Gq,…,Si,…,Gr,…,Sn〉;

Gp,Gq,Gr，…∈PL

在構建RPL的過程中，需要解決的挑戰性問題包括:1)如何從海量無序的公交歷史軌跡點集合中篩選、提取出適量且高質量的軌跡點；2)如何將選取到的軌跡點插入到序列骨架BSL的正確位置上，使之成為高頻、有序的軌跡序列。本文將針對問題1)、2)所采取的處理過程稱為“道路插值”，示意圖如圖6。

圖5 地圖匹配過程

圖6 道路插值

2.2 道路插值之模糊插值

對2.1節提出的挑戰性問題，首先利用數據分析與處理技術，將海量原始數據經過提取、轉換、去重、重組等手段為每一路公交路線生成數量足夠的歷史軌跡點數據。將公交路線以站點作為切分點，將公交路線切分為若干路段，站與站之間的路段作為獨立考察的“路段”。根據1.1節定義2中曲度(C)概念，設置系數δ∈[1,+∞)，將路段統一聚類劃分為“近直線型”路段和“曲線型”路段。根據曲度值的大小動態設置各個路段上插入點的數量，曲度越大的路段需要更多的插入點，以保證尋得完整的軌跡路線。

“模糊插值”理論分析如下(具體算法如算法1)。

條件1 ‖AB‖=max{‖AB‖，‖OA‖，‖OB‖}；

條件1 ‖AB‖=max{‖AB‖，‖OA‖，‖OB‖}；

條件2 點O到直線|AB|的距離范圍為0≤h(O⊥|AB| )<α,α∈(0，‖AB‖/2)。

圖7 候選軌跡點

算法1 道路插值之模糊插值算法。

Input:RS表示以公交站點為節點劃分的路段集合，包含路段寬度、道路距離等信息；PS為各路段海量軌跡點集合。

Output:CRPL表示高頻、基本有序軌跡序列。

CRPL←RS;

//初始化路線軌跡序列

setδ← [1,+∞);ξ← (0，λ/d);α← (0，d/2)；

//參數設置，λ為路段寬度，d為路段的道路距離

forriinRS所有路段do；

ifC<δdo；

//ri為直線型路段，C為路段ri曲度值

forpijinPSido；

//PSi為路段ri上的軌跡點集合

if ‖AB‖=max{‖AB‖，‖pijA‖，‖pijB‖} and 0≤D(pij,ri)<ξdo；

//A、B為路段ri的兩端點，

//D為點pij的偏離度

CRPL+=pij；

//將點pij插入路段軌跡序列中

end if

end for

end if

else do；

//ri為曲線型路段

forpijinPSido；

if ‖AB‖=max{‖AB‖，‖pijA‖，‖pijB‖} and 0≤h(pij⊥ri)<αdo;

//h(pij⊥ri)為點pij到路段ri的垂直距離

CRPL+=pij；

end if

end for

end else

returnCRPL；

2.3 道路插值之精準剔除

2.2節“模糊插值”過程中，“曲線型”路段上被選中的部分不屬于該路段的軌跡插入點會造成該路段軌跡序列錯序，且由于現實原因，搜集到的軌跡點中必定存在異常值。這會導致僅經過一次“模糊插值”過程無法得到完全正確有序的軌跡序列。為此，在“模糊插值”之后，還需要“精準剔除”處理，理論分析如下(具體算法如算法2)。

‖didk‖=max{‖didj‖,‖djdk‖,‖didk‖}

(3)

成立。依據式(3)，便可剔除由“模糊插值”過程產生的路段軌跡序列中不符合條件的異常點和錯序點。根據曲度值的大小設置路段軌跡插入點的數量，刪除距離非常近的軌跡點以減小地圖匹配時的計算代價，使基本正確、有序的軌跡序列最終成為高頻、有序軌跡序列。

算法2 道路插值之精準剔除算法。

Input:CRPL表示高頻、基本有序軌跡序列;

//算法1的輸出

Output:RPL表示高頻、有序軌跡序列。

setd← [1,10];t← [1,5];

//設置參數

whilet>0 do;

forGiinCRPL所有軌跡點do;

if ‖GiGi+2‖≠max{‖GiGj‖,‖GjGk‖,‖GiGk‖} do;

ifGi+1，Gi+2not stopid do;

//非公交站點

delGi+1，Gi+2;

//刪除錯序點

updateCRPL;

end if

end if

if ‖GiGi+2‖

ifGi+2not stopid do;

delGi+2;

//刪除過于密集的點

updateCRPL;

end if

end if

end for

t--;

RPL=CRPL;

returnRPL;

2.4 基于HMM的地圖匹配

“模糊插值”實現了將相距一定距離的軌跡點插入到對應的路段之間，保證路段之間的插入點基本有序。“精準剔除”將路段之間錯序的軌跡點和異常點剔除，重復該過程直至路段的軌跡序列保持有序。經過上述兩個過程之后，得到高質量的高頻有序軌跡序列，將其作為輸入數據應用于1.2節說明的基于隱馬爾可夫模型(HMM)地圖匹配算法，得到最終的地圖匹配路線，具體算法如算法3。

算法3 基于HMM地圖匹配算法。

Input:RPL表示高頻、有序軌跡序列;

//算法2的輸出

Output:MapRoute為地圖匹配路線。

MapRoute← ?;

forpiinRPLdo;

map_point=Alg_HMM(pi,parameters);

MapRoute+=map_point;

//加入匹配后的點

end for

returnMapRoute;

3 實驗結果及分析

3.1 數據說明與分析

本文批量處理的有效城市公交數量多達400多條，數據來源于新加坡陸路交通管理局提供的數據接口。包含兩大數據集(以下簡稱“數據集A”“數據集B”)。數據集A是每間隔2 min對所有運行公交收集一次的相關信息，數據集A包含了海量的公交車軌跡數據，具有很大潛在的價值；然而其所包含的位置信息具有一定的測量誤差、冗余數據和異常值，并且是無序的。數據集B是包含所有公交路線的站點有序序列信息，以及該公交車站距離始發站的實際路面距離(Distance/km)。數據集B的優點是有序且位置準確，缺點是過于稀疏。

3.2 地圖匹配精確度的度量方法

本文所擁有的實際數據中，由于公交路線數量過多且沒有用于直接計算的路線標簽數據。為此，本文提出如下方法進行驗證算法的效果與性能。

假設某一公交路線有n個車站，路線的道路總長度為L，地圖匹配后得到的有序軌跡序列為：

RPL=〈S1,G1,G2,…,Gp,S2,Gp+1,Gp+2,…,Gq,

…,Si,…,Gr,…,Sn〉

其中：Gp，Gq，Gr，…為路段上的點，Si(i∈[1,n])為公交車站。

其中li,i+1,…，i+j-1表示連續路段i，i+1，…，i+j-1的距離之和，當j取不同值時，表示每j個路段作為一個距離計算單位。如圖8所示，展示了隨機選擇的4條不同公交路線隨著路段數j的增加而變化的MARE值，右上角圖例中的數字代表公交路線編號。

圖8 不同j值對指標值的影響

為此，選擇j=2、3、4作為路線匹配精確度的度量指標，如圖9所示，展示了隨機選擇的20條公交路線匹配后的指標值(為方便觀察，對j=2時的MARE值作了排序)，從中可以看出，當選擇j=2、3、4時，指標具有一致的趨勢，隨著j值的增加指標值會稍有降低，j=2時指標值最差，但它的度量能力最強，更能反映地圖匹配的精確度與細節匹配的吻合度。統計所有公交路線的匹配結果得出如下結論：當j=2時，接近50%的公交路線匹配結果的精確度達到90%+，80%的公交路線匹配結果的精確度達到80%+。

圖9 j=2、3、4時部分公交路線匹配結果的指標值

以某度地圖顯示的路線結果為參考標準，從精確度達90%+的公交路線中隨機抽取幾條路線匹配結果與某度地圖顯示的路線圖相比較，路線匹配結果幾乎一致，如圖10～11所示，這表明，上述提出的度量指標在無路線標簽數據條件下，對匹配結果的度量與驗證表現出很強的合理性。

圖10 3路公交路線匹配結果

3.3 算法性能與效率分析

本文完整模型算法的實現包含三大子算法(算法1、2、3)：數據挖掘算法(算法1、2)是在Ubuntu系統下使用Python平臺實現；地圖匹配算法(算法3)的實現使用了barefoot開源庫(https://github.com/bmwcarit/barefoot)以及Open Street Map開源地圖服務平臺。海量公交歷史軌跡數據經過數據挖掘算法處理之后，得到少量高質量、高頻軌跡數據，大幅度減小了匹配算法在地圖匹配時的數據規模及匹配時間(如表1)。如表2所示，隨機選擇了5條公交路線的匹配結果作展示，以3.2節提出的地圖匹配精確度指標作為衡量標準，將挖掘算法得到的高頻軌跡數據作為地圖匹配算法的輸入，與未經過挖掘算法處理的單車輛低頻軌跡數據的匹配結果相比，公交路線地圖匹配的精確度均有顯著提高。

圖11 36路公交路線匹配結果

Tab. 1 Comparison of various indexes before and after trajectory data mining

表2j=2時地圖匹配算法精確度對比%

Tab. 2 Precision comparison of map matching algorithms whenj=2 %

公交路線編號MARE經挖掘處理未經挖掘處理34A_13.849.45201_15.0213.65172_112.7015.8266_215.2919.10170X_219.6325.57

4 結語

針對現有地圖匹配算法對于低頻軌跡數據匹配效果不理想的難題，本文提出的基于海量數據驅動的高頻軌跡數據挖掘方法，為實現準確地圖匹配提供可行、有效的數據輸入，取得了比傳統基于HMM地圖匹配算法更好的匹配效果，為在缺少標簽驗證數據情況下的地圖匹配結果提供了一種較合理的度量指標與驗證方案。在得到準確公交路線的地圖匹配結果后，將進一步研究車輛速度的估算以及車輛到站的時間預估等應用。