李欣

(中原經(jīng)濟區(qū)“三化”協(xié)調(diào)發(fā)展河南省協(xié)同創(chuàng)新中心∥河南財經(jīng)政法大學(xué)資源與環(huán)境學(xué)院，河南 鄭州450046)

多源傳感器獲取的位置信息產(chǎn)生了海量具備時空屬性的軌跡數(shù)據(jù)，此類數(shù)據(jù)真實而全面地反映了人群和車輛的流動行為。傳統(tǒng)的軌跡數(shù)據(jù)，主要應(yīng)用在宏觀分析整個研究區(qū)域的交通運行狀態(tài)，及微觀刻畫和表達目標個體或群組的移動規(guī)律上。而，多源采集的軌跡數(shù)據(jù)具有大數(shù)據(jù)的4V特征，對其進行清洗、索引、存儲和挖掘的難度大大增加。因此，必須利用更加有效的大數(shù)據(jù)平臺和挖掘算法，從中準確提取移動群組的流動規(guī)律，從而實現(xiàn)發(fā)現(xiàn)同類群體或檢測頻繁路徑等功能。

目前，已有一些關(guān)于伴隨模式的研究。如：Flock方法[1-2]利用連續(xù)時間節(jié)點和圓形空間范圍作為判定伴隨模式的時空約束條件；Convoy方法[3-4]將空間約束條件擴展為密度可達；Swarm方法[5]將時間約束條件擴展為可以不連續(xù)；Platoon方法[6]通過時間分段、閾值細化實現(xiàn)了局部或全局時段的伴隨模式挖掘。以上方法主要針對靜態(tài)交通流軌跡數(shù)據(jù)。對于實時采集的無邊界流式軌跡數(shù)據(jù)而言，其時空約束條件設(shè)置難度較大，且該種算法處理效率低、挖掘能力不足。詞向量[7](Word2 Vec)原本用于語法語義規(guī)律的挖掘[8-11]，其特征之一是能夠準確描述相似關(guān)系。許多學(xué)者認為：在一定拓撲空間內(nèi)的交通流或軌跡數(shù)據(jù)同樣存在上下游相關(guān)關(guān)系[12-15]。因此，詞向量曾被用于解決智能交通系統(tǒng)中的聚類分析和網(wǎng)絡(luò)預(yù)測等問題，如：解決網(wǎng)絡(luò)分類的網(wǎng)絡(luò)節(jié)點詞向量訓(xùn)練[16]、網(wǎng)絡(luò)聚類和路徑預(yù)測的鏈路詞向量表示[17-18]及城市功能區(qū)劃分的區(qū)域詞向量表示[19]等。但以上研究對于交通流軌跡的時空異質(zhì)性考慮不夠全面[20-22]，還需對詞向量模型進行有針對性的優(yōu)化，以適應(yīng)伴隨模式挖掘的需要。

本文擬提出一種基于時空Hausdorff距離切分和詞向量相似性的伴隨模式挖掘方法。首先，建立交通流軌跡數(shù)據(jù)的清洗、索引、存儲和查詢框架[23]；然后利用時空Hausdorff距離和時間滑動窗口對軌跡進行切分，建立軌跡段和詞句的類比關(guān)系；并使用詞向量模型完成軌跡整體相似度的計算，實現(xiàn)伴隨模式挖掘，達到為智能交通中的群組移動模式提供理論基礎(chǔ)的目的。

1 伴隨模式的數(shù)據(jù)挖掘

交通流軌跡大數(shù)據(jù)的挖掘算法分為以下幾個步驟：1)通過多源傳感器采集移動對象定位信息，并按照時序組合為軌跡數(shù)據(jù)；利用孤立點檢測算法[24]完成數(shù)據(jù)清洗、構(gòu)建時空索引，配置負載均衡規(guī)則并入庫。2)輸入伴隨模式的挖掘條件，通過語義解析提取挖掘請求中的時空約束條件；利用索引快速從海量軌跡數(shù)據(jù)中提取符合條件的數(shù)據(jù)，并記錄為中間數(shù)據(jù)集。3)利用詞向量模型訓(xùn)練歷史軌跡數(shù)據(jù)集，得到軌跡向量語料庫。4)計算中間數(shù)據(jù)集中所包含的軌跡記錄的時空Hausdorff距離，并利用滑動窗口將其切分為重疊和非重疊子軌跡段，生成子軌跡段集合。5)根據(jù)切分結(jié)果構(gòu)建軌跡段和詞句之間的類比關(guān)系，利用語料庫將軌跡段表達為詞向量，計算單詞相似度；根據(jù)軌跡段在整條軌跡中的長度比例確定權(quán)重，然后利用詞向量模型中的“語句”結(jié)構(gòu)相似度計算方法，得到定量化的軌跡相似度，并判定軌跡間是否呈伴隨模式，最后返回伴隨對象集合和可視化結(jié)果。具體流程如下：

圖1 伴隨模式的數(shù)據(jù)挖掘流程圖Fig.1 Data mining process of accompanying patterns

1.1 時空Hausdorff距離與相似軌跡切分

在以往的研究中，對軌跡定位時間和定位位置分別進行判斷，導(dǎo)致了軌跡的真實特征被人為拆分。本文采用時空Hausdorff距離(spatial-time Hausdorff distance)，將時間和空間因素同時引入軌跡段的距離計算，能較好體現(xiàn)軌跡段之間的時空相似程度。

1.1.1 軌跡對象時空Hausdorff距離計算 在實際應(yīng)用中，移動目標的軌跡在空間上可能是部分相似的，如圖2所示。圖2中，虛線框中的軌跡在空間上差異很小，可以認為此部分是重疊或相似的，但其他部分并不相似。在進行伴隨模式的挖掘時，需要將重疊和非重疊軌跡段進行切分；并根據(jù)重疊部分的多少以及軌跡分段后的結(jié)構(gòu)特征，結(jié)合軌跡的時空異質(zhì)性，計算整條軌跡的相似程度。

圖2 相似軌跡示意圖Fig.2 Schematic diagram of similar trajectories

軌跡由定位點組合而成，而Hausdorff距離主要用于計算兩個無序點集之間的距離。因此，Hausdorff距離可度量兩條軌跡之間的距離。設(shè)存在兩個無序點集P={p1,p2,,pi,,pn}和Q={q1,q2,,qi,,qn}，則Hausdorff距離為：

H(P,Q)=max(h(P,Q),h(Q,P))

(1)

(2)

(3)

其中，dist(pi,qj)為點pi到點qj的歐氏距離。公式(1)為雙向Hausdorff距離，它是Hausdorff距離的基本形式，度量了兩個點集間的最大不匹配程度。公式(2)為從P到Q的單向Hausdorff距離，即計算集合P中的每個點pi到距離此pi點最近的qj點的歐氏距離，并取其中的最大值作為h(P,Q)的值。公式(3)與公式(2)的性質(zhì)類似。

Hausdorff距離雖然度量了兩個點集的最大不匹配程度，但因軌跡定位點還存在時序?qū)傩?，須對其公式進行擴展改進，以適應(yīng)伴隨模式的挖掘需要。為了體現(xiàn)軌跡對象的時空屬性，本文提出了一種基于時間序列的一對三軌跡的Hausdorff距離。已知在某一時間段內(nèi)，兩個移動目標的定位頻率一致，坐標對隨時序一一對應(yīng)。設(shè)某條軌跡中的一個定位點p的時空結(jié)構(gòu)為p(x,y,t)，則軌跡P表達式為：TRp={p1,p2,pi,,pn} 。其中，n>3，x和y為經(jīng)緯度坐標，t為定位時刻。同理，軌跡Q的表達式為：TRq={q1,q2,,qi,qn}。則，改進后的Hausdorff距離公式為：

H(TRp,TRq)

=max(h(TRp,TRq),h(TRq,TRp))

(4)

h(TRp,TRq)

(5)

h(TRq,TRp)

(6)

式中，pi∈TRp，i≠1且i≠n。dist(pi,(qi-1,qi,qi+1))為pi到三點qi-1、qi、qi+1所確定平面的距離。

相比于一對多或一對一的Hausdorff距離，時間序列的一對三的Hausdorff距離具有能體現(xiàn)定位點的時序性和相關(guān)性的特點。三種軌跡的Hausdorff距離計算方法如圖3所示。

圖3 三種軌跡的Hausdorff距離示意圖Fig.3 Schematic diagram of three track Hausdorff distance calculation methods

圖3(b)中，計算的是軌跡上的每個定位點與另一條軌跡上對應(yīng)時刻的定位點之間的距離，滿足了時間排序的要求，但沒有體現(xiàn)軌跡Q上其他點對該點的影響。圖3(c)中，計算的是軌跡P的定位點pi與軌跡Q的定位點qi、以及前后兩點qi-1和qi+1所確定的平面之間的距離。該算法不僅體現(xiàn)了時刻順序和對應(yīng)時刻前后兩點的相關(guān)性，而且單個定位點的計算量大大減少，提高了算法的運行效率。

1.1.2 基于時間滑動窗口的軌跡切分 在進行整條軌跡的相似性度量之前，需要進行切分，得到重疊和非重疊子軌跡集合；然后，使用詞向量度量軌跡的整體相似性。本文使用時間滑動窗口對軌跡進行切分，其原理如圖4所示。

圖4 基于時間滑動窗口的軌跡切分Fig.4 Trajectory segmentation based on time sliding window

在切分過程中，輸入項為目標軌跡TRp={p1,p2,,pi,,pm}、待判定軌跡TRq={q1,q2,,qi,,qn}、最小時間滑動窗口k(3≤k≤min(m,n))和子軌跡Hausdorff距離閾值h；輸出項為重疊和非重疊子軌跡集合。具體步驟為：

(2)計算待判定軌跡起始位置最小時間滑動窗口k內(nèi)子軌跡段的Hausdorff距離，并判斷其距離是否小于閾值h。

(3)若小于閾值，則將時間滑動窗口增加一個單位長度，直至距離超過閾值；并將小于閾值的子軌跡段切分，記錄為重疊子軌跡段。

(4)若時間滑動窗口k的長度增加后，子軌跡的Hausdorff距離超出閾值，則從時間滑動窗口末端開始重新以最小窗口k掃描剩余軌跡。

(5)掃描剩余軌跡時，最小窗口k內(nèi)子軌跡的Hausdorff距離超出閾值，則將最小窗口向后平移一個單位長度，繼續(xù)掃描剩余軌跡，同時記錄超出閾值的子軌跡段作為非重疊子軌跡段。

(6)整條軌跡掃描結(jié)束后，即可得重疊和非重疊子軌跡集合。

1.2 基于詞向量的軌跡相似性度量

1.2.1 詞向量模型與軌跡段類比 詞向量技術(shù)設(shè)計的初衷是為了實現(xiàn)機器對人類自然語言的語義理解，計算“詞”和“句”的相似性，度量目標詞與上下文之間的相關(guān)關(guān)系。詞向量模型又分為CBOW(continuous bag of word)和Skip-gram兩種模型架構(gòu)[2]，二者均可通過訓(xùn)練語料庫表達詞的相關(guān)關(guān)系，而差異在于CBOW通過上下文計算目標詞出現(xiàn)概率，Skip-gram根據(jù)目標詞計算可能出現(xiàn)的上下文。其原理如圖5所示。

圖5 CBOW模型和Skip-gram模型原理圖[2]Fig.5 CBOW model and Skip-gram model[2]

由于伴隨模式挖掘的目標是度量整條軌跡的相似性，因此為了體現(xiàn)對象在移動過程中的分段伴隨狀態(tài)，可以將子軌跡段類比為單詞，整條軌跡類比為語句，利用詞向量模型計算語句的相似性，實現(xiàn)軌跡的伴隨模式挖掘。通過目標詞計算可能出現(xiàn)的上下文信息的Skip-gram模型更加適用。

1.2.2 軌跡相似性度量方法 利用詞向量的語句結(jié)構(gòu)和單詞上下文，可以體現(xiàn)軌跡的分段結(jié)構(gòu)和上下游特征?；谠~向量的軌跡相似性度量方法，主要考慮整條軌跡的長度，以及重疊和非重疊子軌跡段的結(jié)構(gòu)特征，對詞向量語句相似度計算方法進行改進，從而實現(xiàn)伴隨模式的挖掘。其流程如圖6所示。

圖6 基于詞向量的軌跡相似性度量方法Fig.6 Trajectory similarity measurement based on word vector

由于城市交通軌跡幾乎全部運行在路網(wǎng)中，因此可以按照路網(wǎng)中的路段訓(xùn)練詞向量語料庫，并進行軌跡相似性度量。具體步驟如下：

(1)訓(xùn)練詞向量語料庫。將路段類比為詞，每一條軌跡類比為語句，利用地圖匹配算法可以將軌跡映射為由路段序列組成的路徑，然后使用Python第三方庫中的“gensim”工具即可從大量軌跡路徑中實現(xiàn)Word2 Vec語料庫訓(xùn)練，語料庫中包含路網(wǎng)中的各個路段(詞)及其對應(yīng)的實數(shù)向量。

(2)利用語料庫度量任意一條軌跡段的詞向量與其他軌跡段之間的相似性。向量相似性高說明：詞的共現(xiàn)頻率高或語句的上下文結(jié)構(gòu)相似，軌跡的時空特征也相似。

(3)基于Hausdorff距離和時間滑動窗口對軌跡進行切分。從備查軌跡數(shù)據(jù)集中提取兩條軌跡P和Q，利用前述1.1.2節(jié)的方法，得到重疊和非重疊子軌跡集合。

(7)

(5)計算軌跡的整體相似度。計算得到每一個子軌跡段的向量相似度后，結(jié)合該子軌跡段在整條軌跡中所占權(quán)重比例，即可得到軌跡整體相似度。

(8)

其中，ki為該子軌跡段在整條軌跡中所占權(quán)重，可以使用其長度百分比進行賦值。

最后，得到兩條軌跡的整體相似性指標SimTra(P,Q)。整體相似性指標不僅通過Hausdorff距離體現(xiàn)了軌跡定位的時序性和相關(guān)性特征，而且通過子軌跡段的詞向量相似性、對應(yīng)的長度權(quán)重體現(xiàn)了軌跡的分段結(jié)構(gòu)特征。因此，通過伴隨模式挖掘得到的結(jié)果更加符合移動對象的實際伴隨規(guī)律。

2 實驗結(jié)果與分析

2.1 實驗數(shù)據(jù)與運行環(huán)境

本文的實驗數(shù)據(jù)是鄭州市主城區(qū)內(nèi)8萬輛浮動車的定位數(shù)據(jù)，采集時間為2018年5月1日至31日，浮動車的定位頻率為60 s。每條數(shù)據(jù)的記錄包含車輛ID、經(jīng)緯度坐標、速度、方向和時間等信息。

實驗環(huán)境基于Spark框架構(gòu)建[23]，設(shè)備為5臺服務(wù)器，配置均為Intel xeonE5-2640 2.6 GHz、8核、16 GB內(nèi)存。其中，4臺為分布式數(shù)據(jù)處理節(jié)點，負責(zé)對浮動車數(shù)據(jù)進行清洗、預(yù)處理、按照車輛ID和定位時序構(gòu)成軌跡數(shù)據(jù)，并對其進行索引存儲。另外1臺服務(wù)器為中心管理節(jié)點，完成軌跡數(shù)據(jù)的分布式語義查詢、進行軌跡切分、度量軌跡整體相似性，從而完成伴隨模式挖掘。

2.2 軌跡切分實驗

實驗中分別使用了一對多、一對三和一對一的Hausdorff距離進行軌跡差異計算和切分。隨機選取一個移動對象連續(xù)31 d中每天17:30-19:00的軌跡數(shù)據(jù)，距離閾值分別取10、20、30、40和50 m，統(tǒng)計運用三種軌跡切分方法計算Hausdorff距離所耗費的時間。圖7為三種方法的計算效率。

圖7 三種計算方法的效率Fig.7 Efficiency of three calculating methods

從圖7可以看出，不同的距離閾值對計算效率影響不大；而，三種方法的計算耗時順序為一對多>一對三>一對一。設(shè)兩條軌跡都包含n個定位點，則一對多的計算次數(shù)為2n2次，一對三和一對一的計算次數(shù)都是2n次。因此，一對三和一對一的計算量遠小于一對多，所耗費時間也更少。一對三方法為了體現(xiàn)軌跡上定位點之間相關(guān)性，計算的距離為某定位點到另一條軌跡上三個點所形成的面的距離，和一對一方法的兩點間歐氏距離算法相比較為復(fù)雜，因此耗時稍多。

選取鄭州市某時段內(nèi)10 000條軌跡作為待挖掘數(shù)據(jù)集，對其進行軌跡切分，并統(tǒng)計伴隨軌跡數(shù)量，進行三種方法的準確性對比實驗。統(tǒng)計結(jié)果如表1所示。

表1 三種時空Hausdorff距離挖掘準確性對比Table 1 Accuracy comparison of three spatial-time Hausdorff distance mining

根據(jù)表1的統(tǒng)計結(jié)果并結(jié)合人工檢查，可以發(fā)現(xiàn)：一對三的伴隨軌跡數(shù)量少于一對多的。這是因為一對多并不體現(xiàn)定位點的時序；一對三法挖掘的伴隨軌跡數(shù)量多于一對一的。這是因為一對一的方法雖然體現(xiàn)了定位時序，但并未考慮上下游定位點之間的相關(guān)關(guān)系。因此，相比于一對多而言，一對三的方法排除了反向軌跡；相比于一對一而言，一對三的方法挖掘出了隱藏的伴隨關(guān)系。

2.3 伴隨模式挖掘?qū)嶒?/h3>

對軌跡進行切分后，使用詞向量方法建立“子軌跡段—詞”、“軌跡—語句”的類比關(guān)系，并利用語句中的結(jié)構(gòu)模擬軌跡中的子軌跡段結(jié)構(gòu)，實現(xiàn)整條軌跡在結(jié)構(gòu)上的相似性度量。基于相似性度量指標可實現(xiàn)移動對象的伴隨模式挖掘，圖8為所挖掘的部分伴隨軌跡的效果圖。

圖8 伴隨軌跡的可視化效果圖Fig.8 Visualization of accompanying trajectories

從圖8中可以看出，軌跡A、B和C在相同時段內(nèi)，部分子軌跡段運行規(guī)律一致；但由于駕駛員對于道路的熟悉程度不同、偏好不同、中途點不同等因素的影響，有部分子軌跡段并非重疊；利用本文的詞向量方法，可分析出的大部分子軌跡段具有共同的上下游。因此，它們在分段結(jié)構(gòu)上具有較高的相似性，可以判斷它們的運動規(guī)律符合伴隨模式。

圖9為鄭州市三環(huán)范圍內(nèi)主要道路的伴隨對象統(tǒng)計圖。路段顏色越深，單位時間內(nèi)符合伴隨模式的移動對象數(shù)量越多。在圖9中，城市主干道和快速路上挖掘到的伴隨對象多于其他一般道路。這是因為：一方面受到道路等級和承載能力的限制，高等級的主干道交通流量較大，承載的移動對象較多；另一方面，次級道路的交通流一般呈現(xiàn)向主干道匯集的趨勢，上下游路段在空間位置和方向上也具有一定的相關(guān)性。因此，移動對象的運動軌跡呈現(xiàn)的趨勢為：起點和終點附近的子軌跡段匹配在次級道路上，而大部分移動軌跡匹配在主干道上。

圖9 伴隨對象的統(tǒng)計圖Fig.9 The statistical thematic maps of accompanying pattern mining

表2為工作日7:30-9:00、10:00-11:30、14:30-16:00和17:30-19:00四個時段的伴隨對象統(tǒng)計表。如表2所示，早高峰時段7:30-9:00和晚高峰時段17:30-19:00的伴隨對象數(shù)量明顯高于另外兩個平峰時段，這是因為高峰時段交通流量較大，符合伴隨模式的移動對象數(shù)量較多。因此，通過本文設(shè)計的方法得到的符合伴隨模式的移動對象在時間維度上的分布符合實際規(guī)律。

表2 不同時段伴隨對象數(shù)量統(tǒng)計表Table 2 Statistics on the number of accompanying objects at different times

3 結(jié) 語

本文針對移動對象伴隨模式的挖掘問題，設(shè)計了一種基于時空Hausdorff距離切分和詞向量相似性度量的方法。發(fā)現(xiàn)：

1)在進行軌跡結(jié)構(gòu)切分時，時空Hausdorff距離的計算采用了一對三的方法。此方法不但體現(xiàn)了軌跡定位點的時序特征，而且反映了上下游定位點之間的空間相關(guān)關(guān)系，可以排除反向軌跡，挖掘隱藏的伴隨軌跡。其分析結(jié)果比一對多和一對一的方法更為準確，而且經(jīng)過時間滑動窗口切分，將軌跡的分段特征提取出來，為詞向量結(jié)構(gòu)的相似性度量建立了基礎(chǔ)。

2)在進行軌跡相似性度量時，將切分后的子軌跡段類比為詞，整條軌跡類比為語句，利用詞向量方法對軌跡段上下游結(jié)構(gòu)相似性進行了計算。

此方法可以較為準確的度量伴隨軌跡的相似程度，同時體現(xiàn)軌跡的空間、方向和時間異質(zhì)性。通過實驗驗證，發(fā)現(xiàn)該方法挖掘到的伴隨軌跡數(shù)量及其分布符合交通流的實際運行規(guī)律，可為發(fā)現(xiàn)同類群體或檢測頻繁路徑等應(yīng)用提供理論支撐。