張玉虎,鄭皎凌,蒲 良,田 超

(1.成都信息工程大學(xué) 軟件工程學(xué)院，成都 610225;2.中鐵電氣化局集團(tuán)有限公司，北京 100036)

0 引言

在城市不斷發(fā)展的今天，每時(shí)每刻都在不斷產(chǎn)生車(chē)輛軌跡數(shù)據(jù)，海量的軌跡數(shù)據(jù)能夠挖掘城市車(chē)輛移動(dòng)特性[1],具有很大的研究?jī)r(jià)值，能夠?yàn)樵S多應(yīng)用領(lǐng)域提供有效信息。例如紅綠燈優(yōu)化[2]、路網(wǎng)預(yù)測(cè)[3-4]、交通擁堵分析[5-6]等。

現(xiàn)有車(chē)輛軌跡數(shù)據(jù)廣泛采用基于位置的服務(wù)來(lái)記錄移動(dòng)數(shù)據(jù)，然而用戶(hù)可能不會(huì)允許服務(wù)提供者連續(xù)地收集移動(dòng)位置信息，服務(wù)提供商之間的數(shù)據(jù)共享也存在很高的障礙，這些記錄下來(lái)的移動(dòng)數(shù)據(jù)非常稀疏且記錄的時(shí)間分布不均勻，將會(huì)不可避免的使得下游應(yīng)用的性能下降，即使這些數(shù)據(jù)具有較高的用戶(hù)覆蓋率和很長(zhǎng)的追蹤時(shí)間[7]。例如由于數(shù)據(jù)的稀疏性問(wèn)題，用戶(hù)只會(huì)訪(fǎng)問(wèn)少數(shù)幾個(gè)地點(diǎn)，這樣就無(wú)法判斷用戶(hù)的興趣位置[8]，且這類(lèi)使用基于位置服務(wù)的數(shù)據(jù)往往局限于某一個(gè)領(lǐng)域[9]，無(wú)法覆蓋到道路上所有的車(chē)輛數(shù)據(jù)，所以迫切需要一個(gè)更加豐富且可訪(fǎng)問(wèn)的車(chē)輛移動(dòng)數(shù)據(jù)。

隨著城市道路卡口覆蓋率不斷提高，每天將會(huì)產(chǎn)生海量的車(chē)輛移動(dòng)數(shù)據(jù)。如此豐富的車(chē)輛移動(dòng)數(shù)據(jù)，推動(dòng)著研究人員去使用城市道路卡口收集的大規(guī)模數(shù)據(jù)來(lái)重構(gòu)車(chē)輛軌跡。然而使用城市道路卡口產(chǎn)生的車(chē)輛移動(dòng)數(shù)據(jù)來(lái)恢復(fù)車(chē)輛軌跡仍然十分具有挑戰(zhàn)性，因?yàn)檐?chē)輛在城市道路中穿行的過(guò)程中并不一定會(huì)被道路卡口攝像頭連續(xù)拍攝，這樣記錄下來(lái)的車(chē)輛移動(dòng)軌跡仍然稀疏且用戶(hù)在前后2個(gè)卡口攝像頭之間的移動(dòng)軌跡具有非常大的不確定性?，F(xiàn)有的解決方法是使用卡口收集的大規(guī)模視頻和圖像數(shù)據(jù)，通過(guò)對(duì)視頻中的車(chē)輛圖片聚集來(lái)還原車(chē)輛的移動(dòng)軌跡[10]。然而由于卡口視頻和圖像數(shù)據(jù)中包含了大量的用戶(hù)隱私數(shù)據(jù)，大多時(shí)候無(wú)法直接處理原始數(shù)據(jù)，而是通過(guò)對(duì)原始數(shù)據(jù)脫敏處理后生成的車(chē)輛移動(dòng)的文本數(shù)據(jù)來(lái)還原車(chē)輛軌跡。

研究發(fā)現(xiàn)，車(chē)輛軌跡數(shù)據(jù)往往具有一定的周期性和重復(fù)性特征。通過(guò)分析長(zhǎng)期的歷史軌跡數(shù)據(jù)能有助于預(yù)測(cè)用戶(hù)的下一個(gè)位置[11]。但是現(xiàn)實(shí)生活中的歷史數(shù)據(jù)的周期性特征往往無(wú)法有效從大量的歷史車(chē)輛移動(dòng)數(shù)據(jù)中提取。一種方法是從多個(gè)歷史軌跡中篩選出最常訪(fǎng)問(wèn)的位置作為候選位置[12]，但是歷史上最受歡迎的位置不一定是所有時(shí)間上都缺少的地點(diǎn)，車(chē)輛的流動(dòng)具有很強(qiáng)的不確定性，無(wú)法使用一個(gè)固定的位置代表車(chē)輛缺少的地點(diǎn)。

針對(duì)上述問(wèn)題，本文提出了一種基于卡口上下文和全局時(shí)間嵌入[13]的車(chē)輛軌跡重構(gòu)方法，使用多頭自我注意力[14]和動(dòng)態(tài)卷積[15]組成的混合注意力學(xué)習(xí)卡口上下文之間的關(guān)系,將語(yǔ)言表示模型引入到軌跡處理當(dāng)中。靈感來(lái)源于Bert (bidirectional encoder representation from transformers)中引入的掩碼語(yǔ)言模型(masked language model,MLM)[16]，通過(guò)使用上下文所提供的單詞預(yù)測(cè)被掩蓋單詞。車(chē)輛移動(dòng)數(shù)據(jù)中包含了車(chē)輛通過(guò)每一個(gè)卡口的數(shù)據(jù)，其中每一條車(chē)輛軌跡中的卡口和車(chē)輛軌跡之間的關(guān)系類(lèi)似于單詞和句子之間的關(guān)系。

1 問(wèn)題描述

車(chē)輛軌跡還原模型的主要步驟包括：① 獲取城市道路卡口記錄的車(chē)輛數(shù)據(jù)生成車(chē)輛歷史軌跡，并掩蓋掉其中部分卡口數(shù)據(jù)；② 對(duì)車(chē)輛軌跡數(shù)據(jù)中的上下文進(jìn)行學(xué)習(xí)；③ 推測(cè)出其中被掩蓋的真實(shí)卡口編號(hào)數(shù)據(jù)以重構(gòu)車(chē)輛軌跡。即根據(jù)輸入的車(chē)輛歷史軌跡[t1,t2,t3,t4,…,tn]，通過(guò)動(dòng)態(tài)掩蓋其中部分卡口數(shù)據(jù)生成車(chē)輛軌跡[t1,,t2,t3,,…,tn]，恢復(fù)被掩蓋位置，即位置的卡口編號(hào)Sid，以重構(gòu)車(chē)輛的完整軌跡。

城市道路卡口和車(chē)輛軌跡中的其他卡口關(guān)聯(lián)性可以定義為：

(1)

其中，Context(ti)={t1,…,ti-1,ti+1,…,tn}表示和卡口ti出現(xiàn)在同一條軌跡中的其他卡口。然后，利用最大對(duì)數(shù)似然對(duì)軌跡建模，目標(biāo)函數(shù)為:

F=logp(ti|Context(ti))

(2)

在此模型中，對(duì)于每一條軌跡中被掩蓋的卡口ti，都希望F最大。

定義1(車(chē)輛歷史軌跡)。車(chē)輛歷史軌跡定義為T(mén)j={ti|i=1,2,3,…,n},1≤j≤n，其中ti={Cid,Sid,Lon,Lat,Time}，Cid為車(chē)輛編號(hào)，Sid表示卡口編號(hào)，Lon表示卡口經(jīng)度坐標(biāo)，Lat表示卡口緯度坐標(biāo)，j為時(shí)間步大小。

由于卡口生成的車(chē)輛移動(dòng)數(shù)據(jù)是一系列按照時(shí)間順序排序且攜帶了車(chē)輛編號(hào)、卡口編號(hào)、地理坐標(biāo)和被拍攝時(shí)間信息的軌跡點(diǎn)，這些數(shù)據(jù)在時(shí)間上是連續(xù)的，為了生成符合模型的輸入，需要將車(chē)輛移動(dòng)數(shù)據(jù)按照不同的時(shí)間步長(zhǎng)將連續(xù)時(shí)間車(chē)輛移動(dòng)數(shù)據(jù)拆解，如果在同一個(gè)時(shí)間步長(zhǎng)內(nèi)具有多個(gè)卡口數(shù)據(jù)，使用在這個(gè)時(shí)間步長(zhǎng)內(nèi)的第一個(gè)卡口數(shù)據(jù)。例如T1是指將卡口生成的車(chē)輛移動(dòng)數(shù)據(jù)按照以1分鐘為時(shí)間步長(zhǎng)取每一個(gè)時(shí)間步長(zhǎng)內(nèi)的第一個(gè)卡口數(shù)據(jù)生成的車(chē)輛軌跡,T1中的ti是編號(hào)為Cid的車(chē)輛在時(shí)間為T(mén)ime經(jīng)過(guò)經(jīng)緯度為L(zhǎng)on，Lat的編號(hào)為Sid的卡口。

定義2(車(chē)輛掩蓋軌跡)。給定一個(gè)目標(biāo)車(chē)輛Cid的歷史軌跡[t1,t2,t3,t4,…,tn],被掩蓋后的車(chē)輛軌跡則可能為[t1,，〈masked〉,t2,t3,〈masked〉,…,tn]。其中〈masked〉指代被掩蓋的卡口數(shù)據(jù)。

卡口生成的車(chē)輛軌跡在輸入模型進(jìn)行學(xué)習(xí)前，需要將車(chē)輛軌跡中的部分卡口數(shù)據(jù)進(jìn)行隨機(jī)掩蓋，為了實(shí)現(xiàn)更多的掩蓋策略，本文使用動(dòng)態(tài)掩碼方式對(duì)車(chē)輛軌跡進(jìn)行掩蓋。在訓(xùn)練前生成固定數(shù)量和方式的掩蓋策略無(wú)法覆蓋多樣的缺失卡口序列，改為在每一次向模型輸入一個(gè)新的序列之前隨機(jī)生成一個(gè)新的掩蓋策略，則能覆蓋更多序列。

2 模型

針對(duì)車(chē)輛移動(dòng)軌跡中的周期性、重復(fù)性特征和城市道路卡口上下文關(guān)系構(gòu)建的系統(tǒng)框圖如圖1所示。將歷史車(chē)輛卡口軌跡中的卡口向量化表示，為了模擬更多的軌跡缺失片段，使用動(dòng)態(tài)掩蓋方法對(duì)卡口生成的車(chē)輛移動(dòng)軌跡進(jìn)行遮蓋。為了捕獲車(chē)輛軌跡的周期性和重復(fù)性特征，使用局部時(shí)間嵌入和全局時(shí)間嵌入獲取局部時(shí)序信息和全局時(shí)序信息，這樣可以更好地重構(gòu)車(chē)輛軌跡。最后，使用混合注意力學(xué)習(xí)軌跡上下文中已知卡口的序列來(lái)預(yù)測(cè)被掩蓋的卡口信息。

圖1 算法流程框圖

2.1 時(shí)間嵌入模塊

車(chē)輛在每一天中的相同時(shí)間從起點(diǎn)卡口到終點(diǎn)卡口的選擇很有可能會(huì)是相似的，且車(chē)輛移動(dòng)軌跡數(shù)據(jù)中記錄的車(chē)輛通過(guò)每一個(gè)卡口的時(shí)間數(shù)據(jù)代表了車(chē)輛軌跡中的時(shí)間信息，通過(guò)獲取不同卡口和時(shí)間之間的關(guān)系，將有助于恢復(fù)缺失的卡口，然而車(chē)輛軌跡中時(shí)間信息和不同卡口之間往往存在著復(fù)雜的時(shí)間關(guān)聯(lián)性，無(wú)法簡(jiǎn)單的通過(guò)規(guī)則來(lái)描述其中的關(guān)系，為了將不同時(shí)間的卡口上下文情景區(qū)分開(kāi)，獲取車(chē)輛移動(dòng)數(shù)據(jù)中的周期性和重復(fù)性特征，使用局部時(shí)間編碼和全局時(shí)間編碼，將車(chē)輛軌跡中所有時(shí)間數(shù)據(jù)嵌入。

2.1.1局部時(shí)間嵌入

沿用自然語(yǔ)言處理中單詞的上下文說(shuō)法形容車(chē)輛軌跡中不同卡口之間的關(guān)系。由于車(chē)輛軌跡中卡口上下文之間存在先后的關(guān)系，為了表示每一條車(chē)輛軌跡中卡口的局部上下文關(guān)系，將其中的局部位置進(jìn)行編碼嵌入。具體來(lái)說(shuō)，對(duì)于每一條車(chē)輛移動(dòng)數(shù)據(jù)使用固定位置嵌入，使用Transformer[14]中的位置編碼 (position embedding,PE)對(duì)車(chē)輛移動(dòng)數(shù)據(jù)中的局部時(shí)間進(jìn)行編碼，計(jì)算公式如下:

(3)

其中，pos表示卡口數(shù)據(jù)在整個(gè)車(chē)輛軌跡中的位置，1jd,j代表第j個(gè)維度，d代表嵌入的維度。將車(chē)輛中所有卡口的位置進(jìn)行嵌入，使得原始的輸入數(shù)據(jù)獲得更多的上下文信息。

2.1.2全局時(shí)間嵌入

為了獲取車(chē)輛軌跡中的周期性和重復(fù)性特征，單一使用局部時(shí)間嵌入不能捕獲長(zhǎng)時(shí)間車(chē)輛移動(dòng)數(shù)據(jù)的全部特征，因?yàn)樵诓煌瑫r(shí)間下每一個(gè)卡口的語(yǔ)義和上下文信息是不同的，為了捕獲長(zhǎng)時(shí)間車(chē)輛軌跡中的特征，本文使用全局時(shí)間嵌入將層次時(shí)間信息進(jìn)行嵌入，其中每一個(gè)全局時(shí)間嵌入使用一個(gè)可學(xué)習(xí)且詞典大小有限的時(shí)間嵌入 (time embedding,TE)表示，當(dāng)類(lèi)別為小時(shí)時(shí)，詞典大小為24。例如軌跡中的一個(gè)卡口記錄時(shí)間在早上7點(diǎn)，則將7隨機(jī)初始化為詞典大小為24、嵌入維度為d的嵌入向量并隨模型的學(xué)習(xí)不斷更新，計(jì)算公式如下:

(4)

其中,p代表的是某一個(gè)類(lèi)型的全局時(shí)間戳。在長(zhǎng)時(shí)間的車(chē)輛移動(dòng)數(shù)據(jù)中，不同的時(shí)間戳類(lèi)型，如小時(shí)、周、月、節(jié)假日等數(shù)據(jù)，將車(chē)輛移動(dòng)軌跡中不同位置、不同時(shí)間類(lèi)型的時(shí)間戳嵌入后相加，使得每一個(gè)卡口數(shù)據(jù)中包含的更多時(shí)間信息被充分利用。在使用全局時(shí)間嵌入時(shí)，本文使用一天中的某一個(gè)小時(shí)和一周中的某一天2種時(shí)間戳進(jìn)行嵌入。將卡口編號(hào)Sid隨機(jī)初始化為維度為d、字典大小為576的向量u，學(xué)習(xí)模塊輸入計(jì)算如圖2所示。

將卡口編號(hào)嵌入后的向量、局部時(shí)間嵌入和全局時(shí)間嵌入結(jié)合，得到輸入到學(xué)習(xí)模塊中的向量，計(jì)算方式如下:

xi=ui+PE(i, j)+vi

(5)

其中，1≦i≦n，1≦j≦d,xi為卡口ti輸入到學(xué)習(xí)模塊中的向量。

圖2 學(xué)習(xí)模塊輸入向量

2.2 學(xué)習(xí)模塊

2.2.1自我注意力

自注意力機(jī)制能夠有效地從時(shí)間序列數(shù)據(jù)中學(xué)習(xí)復(fù)雜的模式和變化，例如通過(guò)使用Transformer模型學(xué)習(xí)流感疾病的時(shí)間序列來(lái)預(yù)測(cè)流感疾病在未來(lái)的變化[17]。本文為了還原車(chē)輛軌跡中被掩蓋卡口的Sid數(shù)據(jù)，使用Transformer中的編碼模塊讓卡口學(xué)習(xí)不同上下文的關(guān)系,以提高車(chē)輛軌跡還原的準(zhǔn)確性。單個(gè)頭下的軌跡注意力機(jī)制如圖3所示。

圖3 單個(gè)頭下的軌跡注意力機(jī)制

本文使用雙向注意力機(jī)制計(jì)算不同時(shí)隙之間的相關(guān)性。例如，當(dāng)前車(chē)輛軌跡生成嵌入向量中的時(shí)隙q和時(shí)隙p在h頭下的相關(guān)性計(jì)算方式如下:

(6)

(7)

(8)

其中，Wv∈Rdk×d同樣是一個(gè)變換矩陣。雙向自我注意力機(jī)制能夠獲取車(chē)輛軌跡中前后卡口信息，從而更精準(zhǔn)地推斷缺失位置的卡口信息。但是車(chē)輛軌跡中含有多種復(fù)雜的關(guān)系，通過(guò)使用多頭注意力機(jī)制進(jìn)行計(jì)算能夠獲取多種關(guān)系的信息，計(jì)算方式如下:

(9)

其中,‖是concatenation(·)方法，H是總的頭部的數(shù)量。通過(guò)在每一個(gè)頭下學(xué)習(xí)到不同的關(guān)系，并將每一個(gè)頭下面的注意力機(jī)制都組合起來(lái)，得到能表達(dá)更多車(chē)輛軌跡信息的數(shù)據(jù)。最后計(jì)算所有輸入車(chē)輛軌跡中的時(shí)隙和同一軌跡中的其他時(shí)隙的相關(guān)性，更新時(shí)隙的嵌入向量，雙向自我注意力中有H個(gè)自我注意的頭，則Q、K和V嵌入向量被均勻地分割為dk=d/H維度，輸入向量的雙向自我注意力輸出計(jì)算方式如下:

(10)

2.2.2混合注意力

多頭注意力模塊中，所有注意力頭的查詢(xún)都作用于整個(gè)輸入序列，從全局角度生成注意力聚焦的信息。但在車(chē)輛軌跡中每一個(gè)時(shí)間步的卡口和相鄰時(shí)間步的卡口關(guān)系顯然更加緊密，卷積操作能夠有效提取局部上下文信息[18-20]，使得預(yù)測(cè)的結(jié)果更加準(zhǔn)確。本文使用動(dòng)態(tài)卷積提取卡口之間的局部關(guān)系，動(dòng)態(tài)卷積如圖4所示。

圖4 動(dòng)態(tài)卷積

將輸入的維度從d映射到2d，然后使用門(mén)控線(xiàn)性激活函數(shù)計(jì)算輸入，將一半的輸入使用sigmoid函數(shù)計(jì)算后和剩下的一半輸入進(jìn)行點(diǎn)積操作。使用輕量級(jí)卷積建模局部的依賴(lài)關(guān)系，輕量級(jí)卷積是參數(shù)共享的深度卷積,輕量級(jí)卷積將權(quán)重和通道維度綁定,可以將卷積核簡(jiǎn)化為W∈Rk，輕量級(jí)卷積計(jì)算公式如下:

(11)

其中，卷積核被記為W∈Rk，x為輸入向量，即車(chē)輛軌跡的嵌入向量，k為卷積核的寬度，i為深度卷積輸出的第i個(gè)位置，c為輸出的維度數(shù)，輕量級(jí)卷積計(jì)算時(shí)，卷積核的參數(shù)都是固定的，不利于獲取卡口的多樣性，但可以利用函數(shù)動(dòng)態(tài)生成卷積核，動(dòng)態(tài)卷積的計(jì)算公式如下:

(12)

其中，x為輸入向量，在計(jì)算位置i時(shí)使用了一個(gè)位置相關(guān)的卷積核Wf=f(xi)，f是一個(gè)具有可學(xué)習(xí)權(quán)重的線(xiàn)性模型，最后使用Softmax歸一化每一個(gè)卡口的每一維。為了將全局信息和局部信息結(jié)合，使用concatenation方法將多頭自我注意力生成的全局信息和動(dòng)態(tài)卷積信息結(jié)合生成混合注意力信息，如圖5所示。

計(jì)算公式如下:

(13)

其中，‖是concatenation(·)方法，SelfAttn(·)為自我注意力模塊的輸出，DynamicConv(·)為動(dòng)態(tài)卷積模塊的輸出，最后將生成的混合注意力信息輸入到前饋層進(jìn)行處理。

圖5 混合注意力

2.2.3前饋網(wǎng)絡(luò)

為了保持每一個(gè)位置的原有信息，在之后加入一個(gè)標(biāo)準(zhǔn)的殘差連接并使用層歸一化將網(wǎng)絡(luò)中的隱藏層變?yōu)闃?biāo)準(zhǔn)的正態(tài)分布。最后使用兩層線(xiàn)性映射并在中間加上激活函數(shù)進(jìn)行計(jì)算，計(jì)算方式如下:

X=Relu(XW1+b1)W2+b2

(14)

其中，X為混合注意力網(wǎng)絡(luò)的結(jié)果輸出,W1∈Rd×dff,W2∈Rdff×d是變換矩陣，Relu(z)=max(0,z)是非線(xiàn)性激活函數(shù)。

通過(guò)疊加多個(gè)Transformer的編碼結(jié)構(gòu)，學(xué)習(xí)車(chē)輛軌跡中不同卡口之間的上下文關(guān)系和卡口之間的相關(guān)性，用于獲取不同時(shí)間、不同位置的卡口語(yǔ)義信息。

在最后一層編碼器的輸出上加入一個(gè)全連接的Softmax層，計(jì)算出被掩蓋位置的卡口，輸出所有卡口Sid是被掩蓋的真實(shí)卡口Sid的概率，將概率最高的卡口選為被掩蓋位置的輸出。最后僅在被掩蓋位置上的輸出概率分布和真實(shí)標(biāo)簽之間使用交叉熵?fù)p失函數(shù)計(jì)算損失，計(jì)算方式如下:

(15)

其中，N為樣本總數(shù)，M為卡口總數(shù)，a為被掩蓋真實(shí)卡口的編號(hào)。當(dāng)a=s時(shí)，yas= 1，否則yas= 0，pas為第a個(gè)還原軌跡中被掩蓋的卡口編號(hào)屬于s的預(yù)測(cè)概率。同時(shí)使用Adam優(yōu)化器[21]進(jìn)行梯度優(yōu)化，通過(guò)小批量的隨機(jī)訓(xùn)練得到梯度的變化并優(yōu)化模型的權(quán)重。

2.3 算法流程

通過(guò)對(duì)原始的卡口數(shù)據(jù)進(jìn)行處理得出，車(chē)輛在2個(gè)相鄰卡口的通行時(shí)間在2 min以?xún)?nèi)的數(shù)據(jù)占比為61.91%，表明絕大多數(shù)車(chē)輛能在2 min以?xún)?nèi)通過(guò)2個(gè)相鄰卡口。本文在生成階段使用以2 min為間隔獲取卡口，將總數(shù)大于6的卡口集合作為車(chē)輛的原始軌跡。實(shí)驗(yàn)使用算法1計(jì)算原始的車(chē)輛軌跡，算法1詳細(xì)如下:

算法1:生成車(chē)輛軌跡

輸入:城市道路卡口記錄的數(shù)據(jù)

輸出:車(chē)輛軌跡T2

1:TList← 城市道路卡口記錄的數(shù)據(jù)

2:TList← 城市道路卡口記錄的數(shù)據(jù)按照Cid聚集

3:fori(iinTList)do

4:i← 將聚集的卡口記錄數(shù)據(jù)按照時(shí)間排序

5:time← {i中第一個(gè)卡口記錄的時(shí)間,0}

6:k← 0

8: forj(jini) do

9: iftime[1]< 2 do

10:time[1]←j中記錄的時(shí)間-time[0]

11: end if

12: iftime[1]> 2 andtime[1]< 4 do

14:time← {j中記錄的時(shí)間,0}

15: end if

16: iftime[1]>2 andtime[1]> 4 do

18:k←k+ 1

20: end if

23: end if

24:time← {j中記錄的時(shí)間,0}

25: end if

26: end for

27: end for

在學(xué)習(xí)階段，通過(guò)掩蓋其中的卡口來(lái)學(xué)習(xí)車(chē)輛原始軌跡中的卡口和前后卡口之間的聯(lián)系，在真實(shí)預(yù)測(cè)階段使用Argmax計(jì)算最終輸出中概率最大的卡口的Sid為被掩蓋卡口的Sid。還原出來(lái)的車(chē)輛軌跡中的卡口集合使用Hidden Markov map matching算法[22]，將卡口集合和實(shí)際地圖匹配，還原出車(chē)輛的真實(shí)地圖軌跡。車(chē)輛軌跡重構(gòu)算法詳細(xì)如下:

算法2：GT-Recovery

輸入：城市道路卡口記錄的數(shù)據(jù)

輸出：被掩蓋的卡口Sid數(shù)據(jù)

1:T2← 使用算法1生成車(chē)輛軌跡

2:TTrain←T2中前21天數(shù)據(jù)為訓(xùn)練集

3:TTest,←T2中后7天數(shù)據(jù)為測(cè)試集

4: 使用多頭注意力和動(dòng)態(tài)卷積實(shí)現(xiàn)混合注意力

5:學(xué)習(xí)模型編碼層數(shù)為3，混合注意力中頭數(shù)為4

6:Train← 將TTest按照每一次的訓(xùn)練的大小隨機(jī)抽取其中的車(chē)輛軌跡生成學(xué)習(xí)模型的訓(xùn)練集

7: fori(iinTrain) do

8: 使用動(dòng)態(tài)掩蓋生成軌跡i的掩蓋策略

9:X← 通過(guò)式(5)計(jì)算車(chē)輛的輸入向量

10: forj(jin 3) do

11:MixAttn← 通過(guò)式(13)計(jì)算混合注意力網(wǎng)絡(luò)的輸出

12:X← 使用殘差連接和歸一化計(jì)算混合注意力網(wǎng)絡(luò)的輸出

13:X← 通過(guò)式(15)計(jì)算前饋網(wǎng)絡(luò)輸出

14:X← 使用殘差連接和歸一化計(jì)算混合注意力網(wǎng)絡(luò)的輸出

15:X← 使用Softmax計(jì)算每一個(gè)卡口是掩蓋卡口的可能性。計(jì)算的結(jié)果中可能性最大的卡口Sid為目標(biāo)結(jié)果。

16: 使用式(16)計(jì)算損失

17: 使用Adam進(jìn)行梯度優(yōu)化

18: end for

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

3.1 數(shù)據(jù)集

使用中國(guó)四川某市的576個(gè)城市交通卡口攝像頭所采集的車(chē)輛移動(dòng)數(shù)據(jù)。數(shù)據(jù)記錄了2020年10月所有卡口拍攝到的記錄。由于卡口攝像頭拍攝的視頻數(shù)據(jù)含有海量的敏感信息，所有的視頻數(shù)據(jù)都被處理為結(jié)構(gòu)化的文本數(shù)據(jù)，每天所采集的過(guò)車(chē)數(shù)據(jù)量大小為106級(jí)，車(chē)輛移動(dòng)數(shù)據(jù)如表1所示。由于道路上攝像頭經(jīng)緯度的敏感性，其中經(jīng)緯度信息不做展示。

表1 車(chē)輛移動(dòng)數(shù)據(jù)

在將數(shù)據(jù)投入模型進(jìn)行訓(xùn)練之前，對(duì)車(chē)輛移動(dòng)數(shù)據(jù)進(jìn)行預(yù)處理。首先，由于城市道路卡口大多安置在交叉路口上，車(chē)輛在通過(guò)卡口時(shí)可能會(huì)被多次記錄，因此，在預(yù)處理時(shí)只保留車(chē)輛軌跡中相鄰且重復(fù)的最后一個(gè)卡口數(shù)據(jù)。其次，將車(chē)輛軌跡中速度異常的卡口進(jìn)行刪除。最后，以2 min為時(shí)間步選擇出車(chē)輛軌跡中卡口數(shù)量大于6的車(chē)輛軌跡來(lái)進(jìn)行軌跡還原。本文經(jīng)過(guò)預(yù)處理后共有420 000條車(chē)輛軌跡。

3.2 實(shí)驗(yàn)設(shè)置

3.2.1實(shí)驗(yàn)環(huán)境

本文模型使用Tensorflow實(shí)現(xiàn),在Linux服務(wù)器上訓(xùn)練。該服務(wù)器的具體配置參數(shù)為:Ubuntu 18.04 LTS操作系統(tǒng)，GPU型號(hào)為I7-7700K，2條12 G顯存的Nvidia RTX 2080Ti顯卡。

3.2.2實(shí)驗(yàn)細(xì)節(jié)

實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)是根據(jù)被還原的卡口來(lái)進(jìn)行計(jì)算的，使用Recall@k作為標(biāo)準(zhǔn)[9,12]，如果正確的卡口能以最大概率恢復(fù)，則Recall@1等于1，否則等于0。最終的Recall@k是所有測(cè)試用例的平均值，Recall@k值越大，表明模型的性能越好。

為了評(píng)估性能，遮住部分車(chē)輛軌跡中的卡口數(shù)據(jù)，并將遮住的卡口作為真實(shí)值進(jìn)行恢復(fù)，屏蔽其中30%的位置，掩蓋車(chē)輛軌跡中1到6個(gè)卡口進(jìn)行車(chē)輛軌跡的恢復(fù)。數(shù)據(jù)集按照時(shí)間劃分，將最后一周中的82 000條車(chē)輛軌跡作為測(cè)試集，前面的338 000條車(chē)輛軌跡作為訓(xùn)練集。模型訓(xùn)練時(shí)隨機(jī)讀取車(chē)輛軌跡進(jìn)行學(xué)習(xí)。使用的模型由3層含有混合注意力的編碼器構(gòu)成，卡口嵌入維度為256，每一個(gè)編碼器由4頭自我注意力和動(dòng)態(tài)卷積組成。

3.3 算法還原性能

3.3.1不同算法性能

Top算法[12]是一種簡(jiǎn)單的基于計(jì)數(shù)的方法，在恢復(fù)時(shí)將其中最流行的位置用于恢復(fù)軌跡。

History算法[11]使用歷史軌跡的每個(gè)時(shí)間段中最常被訪(fǎng)問(wèn)的位置來(lái)恢復(fù)軌跡。

RF算法[11]使用基于特征的機(jī)器學(xué)習(xí)方法。提取各軌跡的缺失時(shí)隙，并將缺失時(shí)隙的前后位置作為特征，訓(xùn)練隨機(jī)森林分類(lèi)器來(lái)進(jìn)行恢復(fù)。

為了方便表達(dá)，使用GT-Recovery表示本文中的模型。從表2中可以分析出，傳統(tǒng)的基于規(guī)則的模型均無(wú)法達(dá)到較高的準(zhǔn)確率，雖然直覺(jué)上歷史數(shù)據(jù)中經(jīng)常被訪(fǎng)問(wèn)的地點(diǎn)有助于恢復(fù)車(chē)輛的移動(dòng)軌跡，但是由于車(chē)輛移動(dòng)的不確定性，傳統(tǒng)的方法無(wú)法準(zhǔn)確捕獲車(chē)輛復(fù)雜的移動(dòng)規(guī)律，單純基于規(guī)則就無(wú)法準(zhǔn)確恢復(fù)車(chē)輛軌跡。通過(guò)使用混合注意力機(jī)制編碼層，可以更好地捕獲車(chē)輛軌跡的移動(dòng)特征，并較為準(zhǔn)確地還原車(chē)輛軌跡中缺少的卡口。通過(guò)實(shí)驗(yàn)對(duì)比，使用基于卡口上下文學(xué)習(xí)和全局時(shí)間嵌入的模型能更好地還原車(chē)輛軌跡，證明了本文提出的方法能更有效地捕獲車(chē)輛的移動(dòng)方式、周期性特征和重復(fù)性特征。

表2 實(shí)驗(yàn)結(jié)果指標(biāo)

3.3.2消融實(shí)驗(yàn)

測(cè)試了所有模塊對(duì)最終結(jié)果準(zhǔn)確率的影響，將模型中不同模塊去掉，觀察準(zhǔn)確率的變化情況，結(jié)果如表3所示。其中GT-Recovery-G表示減去全局時(shí)間的結(jié)果，GT-Recovery-D表示減去動(dòng)態(tài)掩蓋后的結(jié)果，GT-Recovery-M表示減去局部上下文信息后的結(jié)果。分析可知，GT-Recovery優(yōu)于所有的去掉模塊后的結(jié)果，其中去掉全局時(shí)間后下降最多。對(duì)比GT-Recovery模型和GT-Recovery-G模型發(fā)現(xiàn)，在車(chē)輛軌跡嵌入時(shí)加入時(shí)間信息能夠降低最后恢復(fù)的不確定性，提高還原的準(zhǔn)確性。然而比較GT-Recovery-M模型和GT-Recovery模型，可以發(fā)現(xiàn)加入局部上下文信息后的提升有限，這是由于軌跡中的卡口數(shù)量較少，主要依賴(lài)軌跡全局信息恢復(fù)軌跡中缺失的卡口。

表3 消融實(shí)驗(yàn)結(jié)果指標(biāo)

3.3.3不同缺失程度下的性能

通過(guò)測(cè)試模型在不同卡口缺失率下的恢復(fù)被掩蓋卡口的性能，驗(yàn)證模型是否能夠處理不同缺失率的情況，分別研究了卡口被掩蓋的概率在30%～50%、50%～70%和70%～90%時(shí)的卡口恢復(fù)情況，掩蓋其中的卡口時(shí)不會(huì)掩蓋第一個(gè)和最后一個(gè)卡口數(shù)據(jù)。通過(guò)表4可以看出，隨著車(chē)輛卡口缺失率的上升，卡口還原的準(zhǔn)確率在不斷下降，但還原準(zhǔn)確率下降的趨勢(shì)卻不明顯。一是為保證軌跡的原始通行信息，本文保留了車(chē)輛軌跡的起點(diǎn)卡口和終點(diǎn)卡口，且能被卡口連續(xù)記錄的車(chē)輛軌跡較少，通過(guò)計(jì)算測(cè)試數(shù)據(jù)得出，車(chē)輛卡口軌跡中的卡口數(shù)量在6～8時(shí)占比為82.26%，在保留車(chē)輛起點(diǎn)卡口和終點(diǎn)卡口后，卡口缺失率在30%～90%的實(shí)際缺失的卡口數(shù)量差距并不明顯。二是由于大多數(shù)車(chē)輛在通過(guò)具有相同起點(diǎn)和終點(diǎn)的卡口對(duì)時(shí)選擇的路徑是相似的，但實(shí)驗(yàn)結(jié)果表明，通過(guò)嵌入車(chē)輛軌跡的周期性和重復(fù)性特征，使用本文的模型還原車(chē)輛軌跡中缺失的卡口數(shù)據(jù)時(shí)，在數(shù)據(jù)缺失率增大的情況下，仍然具有更好的還原準(zhǔn)確性。

表4 不同缺失率下的實(shí)驗(yàn)結(jié)果指標(biāo)

3.3.4不同嵌入維度下的性能

本文研究了嵌入維度數(shù)d、多頭自我注意力機(jī)制的頭數(shù)H和基于混合注意力機(jī)制的編碼層數(shù)L對(duì)于車(chē)輛軌跡還原性能的影響，圖6中顯示了不同的嵌入維度在車(chē)輛軌跡還原中準(zhǔn)確率的變換，在嵌入維度不斷增加的情況下，還原的準(zhǔn)確率也在逐步提高，在嵌入維度大于256后，最終的還原性能趨于穩(wěn)定，使用大于256維度的嵌入，準(zhǔn)確率將不會(huì)有巨大的提高，所以選擇256作為模型的嵌入維度。圖7中顯示了不同自我注意力機(jī)制的頭部數(shù)量和不同數(shù)量的編碼層對(duì)于模型性能的影響，從圖中可以得到，使用頭部數(shù)量的多少對(duì)于最終還原的準(zhǔn)確率影響不大，但使用更多的基于混合注意力機(jī)制的編碼層能獲得更好的還原準(zhǔn)確率。通過(guò)對(duì)最終還原效果和效率的權(quán)衡，本文模型在訓(xùn)練時(shí)使用3層由4個(gè)頭部數(shù)量的多頭自我注意力模塊和動(dòng)態(tài)卷積模塊組成的混合注意力模塊構(gòu)成的編碼層。

圖6 不同嵌入維度下的還原準(zhǔn)確率

圖7 不同頭數(shù)和編碼層數(shù)下的還原準(zhǔn)確率

4 結(jié)論

利用城市中覆蓋率不斷提升的卡口攝像頭生成的數(shù)據(jù)，對(duì)車(chē)輛軌跡進(jìn)行還原，提出了一種基于卡口上下文和全局時(shí)間嵌入的城市車(chē)輛軌跡還原方法。使用全局時(shí)間嵌入和局部時(shí)間嵌入結(jié)合的方法，捕獲車(chē)輛軌跡移動(dòng)中的周期性特征，使用動(dòng)態(tài)掩碼語(yǔ)言模型模擬車(chē)輛軌跡在不同缺失率情況下的數(shù)據(jù)，將嵌入后的數(shù)據(jù)通過(guò)編碼層中的混合注意力對(duì)車(chē)輛軌跡中的卡口上下文進(jìn)行分析和學(xué)習(xí)。最后對(duì)比生成的結(jié)果和被掩蓋結(jié)果，結(jié)果表明，模型能夠更加有效地捕獲車(chē)輛的復(fù)雜移動(dòng)特征并能夠較為準(zhǔn)確地將被掩蓋的車(chē)輛軌跡進(jìn)行還原。但是由于城市卡口在記錄通行車(chē)輛時(shí)具有很大的不確定性，車(chē)輛無(wú)法在一定時(shí)間步長(zhǎng)內(nèi)被多個(gè)卡口連續(xù)記錄，使得車(chē)輛軌跡數(shù)據(jù)量不夠大。在未來(lái)的工作中，將會(huì)考慮更多不同數(shù)據(jù)對(duì)于車(chē)輛軌跡還原的影響，探尋影響車(chē)輛移動(dòng)模型的更多因素。