基于時(shí)空切分和詞向量相似性的軌跡伴隨模式挖掘

李欣

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

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

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

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

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

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

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

1.1 時(shí)空Hausdorff距離與相似軌跡切分

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

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

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

軌跡由定位點(diǎn)組合而成，而Hausdorff距離主要用于計(jì)算兩個(gè)無(wú)序點(diǎn)集之間的距離。因此，Hausdorff距離可度量?jī)蓷l軌跡之間的距離。設(shè)存在兩個(gè)無(wú)序點(diǎn)集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)為點(diǎn)pi到點(diǎn)qj的歐氏距離。公式(1)為雙向Hausdorff距離，它是Hausdorff距離的基本形式，度量了兩個(gè)點(diǎn)集間的最大不匹配程度。公式(2)為從P到Q的單向Hausdorff距離，即計(jì)算集合P中的每個(gè)點(diǎn)pi到距離此pi點(diǎn)最近的qj點(diǎn)的歐氏距離，并取其中的最大值作為h(P,Q)的值。公式(3)與公式(2)的性質(zhì)類(lèi)似。

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

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

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

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

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

圖4 基于時(shí)間滑動(dòng)窗口的軌跡切分Fig.4 Trajectory segmentation based on time sliding window

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(7)

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

(8)

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

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

2.2 軌跡切分實(shí)驗(yàn)

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

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

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

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

表1 三種時(shí)空Hausdorff距離挖掘準(zhǔn)確性對(duì)比Table 1 Accuracy comparison of three spatial-time Hausdorff distance mining

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

2.3 伴隨模式挖掘?qū)嶒?yàn)

對(duì)軌跡進(jìn)行切分后，使用詞向量方法建立“子軌跡段—詞”、“軌跡—語(yǔ)句”的類(lèi)比關(guān)系，并利用語(yǔ)句中的結(jié)構(gòu)模擬軌跡中的子軌跡段結(jié)構(gòu)，實(shí)現(xiàn)整條軌跡在結(jié)構(gòu)上的相似性度量?；谙嗨菩远攘恐笜?biāo)可實(shí)現(xiàn)移動(dòng)對(duì)象的伴隨模式挖掘，圖8為所挖掘的部分伴隨軌跡的效果圖。

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

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

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

圖9 伴隨對(duì)象的統(tǒng)計(jì)圖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四個(gè)時(shí)段的伴隨對(duì)象統(tǒng)計(jì)表。如表2所示，早高峰時(shí)段7:30-9:00和晚高峰時(shí)段17:30-19:00的伴隨對(duì)象數(shù)量明顯高于另外兩個(gè)平峰時(shí)段，這是因?yàn)楦叻鍟r(shí)段交通流量較大，符合伴隨模式的移動(dòng)對(duì)象數(shù)量較多。因此，通過(guò)本文設(shè)計(jì)的方法得到的符合伴隨模式的移動(dòng)對(duì)象在時(shí)間維度上的分布符合實(shí)際規(guī)律。

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

3 結(jié) 語(yǔ)

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

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

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

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