基于海量公交軌跡數(shù)據(jù)挖掘的地圖匹配算法

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

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

0 引言

隨著全球定位系統(tǒng)(Global Positioning System, GPS)技術(shù)的普及，基于車載GPS設(shè)備的軌跡數(shù)據(jù)挖掘已成為城市智能交通系統(tǒng)和定位服務(wù)研究的熱點(diǎn)。尤其是海量的GPS軌跡數(shù)據(jù)為許多智能交通服務(wù)(如路徑規(guī)劃、實(shí)時(shí)導(dǎo)航和流行路線查詢等應(yīng)用)提供了數(shù)據(jù)支撐。然而實(shí)現(xiàn)上述各種服務(wù)的一個(gè)前提是能夠?qū)PS軌跡數(shù)據(jù)準(zhǔn)確地與數(shù)字地圖上的道路相匹配(地圖匹配)，即使用車輛產(chǎn)生的GPS軌跡數(shù)據(jù)與底層道路拓?fù)渚W(wǎng)絡(luò)相關(guān)聯(lián)以獲得車輛行駛的準(zhǔn)確路線。

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

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

1 相關(guān)工作

1.1 相關(guān)概念與定義

定義1 道路距離。道路兩點(diǎn)之間沿地球表面的實(shí)際路面距離。

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

圖1 道路類型

(1)

圖2 曲度計(jì)算

(2)

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

圖3 偏離度

1.2 HMM地圖匹配算法

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

圖4 路徑搜索

2 公交路線地圖匹配

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

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

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

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

Gp,Gq,Gr，…∈PL

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

圖5 地圖匹配過程

圖6 道路插值

2.2 道路插值之模糊插值

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

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

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

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

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

圖7 候選軌跡點(diǎn)

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

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

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

CRPL←RS;

//初始化路線軌跡序列

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

//參數(shù)設(shè)置，λ為路段寬度，d為路段的道路距離

forriinRS所有路段do；

ifC<δdo；

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

forpijinPSido；

//PSi為路段ri上的軌跡點(diǎn)集合

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

//A、B為路段ri的兩端點(diǎn)，

//D為點(diǎn)pij的偏離度

CRPL+=pij；

//將點(diǎn)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)為點(diǎn)pij到路段ri的垂直距離

CRPL+=pij；

end if

end for

end else

returnCRPL；

2.3 道路插值之精準(zhǔn)剔除

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

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

(3)

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

算法2 道路插值之精準(zhǔn)剔除算法。

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

//算法1的輸出

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

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

//設(shè)置參數(shù)

whilet>0 do;

forGiinCRPL所有軌跡點(diǎn)do;

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

ifGi+1，Gi+2not stopid do;

//非公交站點(diǎn)

delGi+1，Gi+2;

//刪除錯(cuò)序點(diǎn)

updateCRPL;

end if

end if

if ‖GiGi+2‖

ifGi+2not stopid do;

delGi+2;

//刪除過于密集的點(diǎn)

updateCRPL;

end if

end if

end for

t--;

RPL=CRPL;

returnRPL;

2.4 基于HMM的地圖匹配

“模糊插值”實(shí)現(xiàn)了將相距一定距離的軌跡點(diǎn)插入到對(duì)應(yīng)的路段之間，保證路段之間的插入點(diǎn)基本有序?！熬珳?zhǔn)剔除”將路段之間錯(cuò)序的軌跡點(diǎn)和異常點(diǎn)剔除，重復(fù)該過程直至路段的軌跡序列保持有序。經(jīng)過上述兩個(gè)過程之后，得到高質(zhì)量的高頻有序軌跡序列，將其作為輸入數(shù)據(jù)應(yīng)用于1.2節(jié)說明的基于隱馬爾可夫模型(HMM)地圖匹配算法，得到最終的地圖匹配路線，具體算法如算法3。

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

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

//算法2的輸出

Output:MapRoute為地圖匹配路線。

MapRoute← ?;

forpiinRPLdo;

map_point=Alg_HMM(pi,parameters);

MapRoute+=map_point;

//加入匹配后的點(diǎn)

end for

returnMapRoute;

3 實(shí)驗(yàn)結(jié)果及分析

3.1 數(shù)據(jù)說明與分析

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

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

本文所擁有的實(shí)際數(shù)據(jù)中，由于公交路線數(shù)量過多且沒有用于直接計(jì)算的路線標(biāo)簽數(shù)據(jù)。為此，本文提出如下方法進(jìn)行驗(yàn)證算法的效果與性能。

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

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

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

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

其中l(wèi)i,i+1,…，i+j-1表示連續(xù)路段i，i+1，…，i+j-1的距離之和，當(dāng)j取不同值時(shí)，表示每j個(gè)路段作為一個(gè)距離計(jì)算單位。如圖8所示，展示了隨機(jī)選擇的4條不同公交路線隨著路段數(shù)j的增加而變化的MARE值，右上角圖例中的數(shù)字代表公交路線編號(hào)。

圖8 不同j值對(duì)指標(biāo)值的影響

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

圖9 j=2、3、4時(shí)部分公交路線匹配結(jié)果的指標(biāo)值

以某度地圖顯示的路線結(jié)果為參考標(biāo)準(zhǔn)，從精確度達(dá)90%+的公交路線中隨機(jī)抽取幾條路線匹配結(jié)果與某度地圖顯示的路線圖相比較，路線匹配結(jié)果幾乎一致，如圖10～11所示，這表明，上述提出的度量指標(biāo)在無(wú)路線標(biāo)簽數(shù)據(jù)條件下，對(duì)匹配結(jié)果的度量與驗(yàn)證表現(xiàn)出很強(qiáng)的合理性。

圖10 3路公交路線匹配結(jié)果

3.3 算法性能與效率分析

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

圖11 36路公交路線匹配結(jié)果

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

表2j=2時(shí)地圖匹配算法精確度對(duì)比%

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

公交路線編號(hào)MARE經(jīng)挖掘處理未經(jīng)挖掘處理34A_13.849.45201_15.0213.65172_112.7015.8266_215.2919.10170X_219.6325.57

4 結(jié)語(yǔ)

針對(duì)現(xiàn)有地圖匹配算法對(duì)于低頻軌跡數(shù)據(jù)匹配效果不理想的難題，本文提出的基于海量數(shù)據(jù)驅(qū)動(dòng)的高頻軌跡數(shù)據(jù)挖掘方法，為實(shí)現(xiàn)準(zhǔn)確地圖匹配提供可行、有效的數(shù)據(jù)輸入，取得了比傳統(tǒng)基于HMM地圖匹配算法更好的匹配效果，為在缺少標(biāo)簽驗(yàn)證數(shù)據(jù)情況下的地圖匹配結(jié)果提供了一種較合理的度量指標(biāo)與驗(yàn)證方案。在得到準(zhǔn)確公交路線的地圖匹配結(jié)果后，將進(jìn)一步研究車輛速度的估算以及車輛到站的時(shí)間預(yù)估等應(yīng)用。