嚴(yán)思迅 吳 兵 商 蕾，3 呂潔印 汪 洋▲

（1.武漢理工大學(xué)國家水運(yùn)安全工程技術(shù)研究中心 武漢 430063；2.武漢理工大學(xué)交通與物流工程學(xué)院 武漢 430063；3.武漢理工大學(xué)船海與能源動力工程學(xué)院 武漢 430063；4.深圳中集智能科技有限公司 廣東 深圳 518057）

0 引 言

室內(nèi)定位技術(shù)和基于位置的服務(wù)（location-based service，LBS）的發(fā)展與應(yīng)用[1-3]使得室內(nèi)用戶的軌跡數(shù)據(jù)不斷增長，從宏觀角度來看，海量的軌跡數(shù)據(jù)中不僅蘊(yùn)含了群體對象的泛在移動模式與規(guī)律，例如，人群的移動與活動特征、擁堵規(guī)律等，還揭示了交通演化的內(nèi)在機(jī)理[4]。郵輪內(nèi)部空間作為1種特別的室內(nèi)環(huán)境，大量乘客在其中活動產(chǎn)生復(fù)雜的軌跡網(wǎng)絡(luò)。準(zhǔn)確發(fā)現(xiàn)乘客伴隨關(guān)系有利于識別乘員活動軌跡中蘊(yùn)含的群組關(guān)系，在郵輪中兒童、老年人等應(yīng)受監(jiān)護(hù)的乘客出現(xiàn)異常行蹤時(shí)提供及時(shí)預(yù)警。

伴隨關(guān)系對象是指2個(gè)或2個(gè)以上移動目標(biāo)在一段運(yùn)動時(shí)間內(nèi)的距離不超過一定閾值的移動對象組。軌跡伴隨關(guān)系的發(fā)現(xiàn)涉及到相似性度量，它是時(shí)空軌跡數(shù)據(jù)挖掘的基礎(chǔ)。經(jīng)典軌跡相似性度量方法包括歐氏距離（Euclidean distance）、動態(tài)時(shí)間規(guī)整（dynamic time warping，DTW）、編輯距離（edit distance，ED）、弗雷歇距離度量（Fréchet distance）、豪斯多夫距離（Hausdorff distance）、最長公共子序列（longest common sub-Sequence，LCSS）等[5-6]。伴隨模式挖掘是指從大量軌跡中識別具有伴隨關(guān)系的移動對象，代表性的伴隨模式主要有companion，convoy，swarm，gathering，partner，group等[7]。

無論是針對行人軌跡數(shù)據(jù)，還是車輛、船舶軌跡數(shù)據(jù)，現(xiàn)有文獻(xiàn)中已有大量的研究與分析工作。馮慧芳等[8]提出了基于時(shí)空相似性聚類的熱點(diǎn)載客路徑挖掘算法，從出租車的GPS軌跡數(shù)據(jù)中提取出載客軌跡及其核心軌跡，根據(jù)提出的核心軌跡時(shí)空相似性度量方法結(jié)合DBSCAN聚類算法對載客軌跡進(jìn)行聚類；唐爐亮等[9]為了識別立體交叉口中不同的行駛規(guī)則，利用隨機(jī)森林特征選擇方法分析車輛軌跡數(shù)據(jù)特征并聚類，獲得最優(yōu)聚類結(jié)果下的行駛規(guī)則聚類簇，并構(gòu)建聚類簇范圍約束的狄洛尼三角網(wǎng)；周洋等[10]利用手機(jī)等智能移動終端獲取個(gè)體出行GPS軌跡數(shù)據(jù)，提出1種新的時(shí)空聚類算法AT-DBSCAN識別軌跡中的停駐點(diǎn)，并定義出行次數(shù)一致性、出行起止時(shí)刻誤差、停駐點(diǎn)時(shí)長誤差、停駐點(diǎn)中心偏移距離4個(gè)算法驗(yàn)證指標(biāo)，彌補(bǔ)了傳統(tǒng)查全率、查準(zhǔn)率等忽略停駐點(diǎn)時(shí)空信息準(zhǔn)確性的不足；Faisal Orakzai等[11]提出1種分布式算法（DMC）以挖掘運(yùn)動對象的Convoy模式，該算法相比于傳統(tǒng)算法有更高的效率；周于濤等[12]針對現(xiàn)有軌跡預(yù)測方法預(yù)測精度不高，對行人交互信息利用不充分等問題，提出了1種結(jié)合自注意力機(jī)制和結(jié)伴行為特征的行人軌跡預(yù)測模型；連靜等[13]針對行人軌跡預(yù)測具有復(fù)雜、擁擠的場景和社會交互問題，基于長短時(shí)記憶網(wǎng)絡(luò)（long short-term memory network,LSTM）對行人與車輛、行人與其他行人的交互進(jìn)行建模，提出1種基于人車交互的行人軌跡預(yù)測模型（VP-LSTM），該模型同時(shí)考慮了行人與行人的交互、行人與車輛的交互，更適用于復(fù)雜的交通場景；賽斌等[14]使用基于自標(biāo)檢蜒的多自標(biāo)跟蹤算法對地鐵站出口、商場出口等場景中的行人移動軌跡進(jìn)行提取，針對行人軌跡的特點(diǎn)結(jié)合點(diǎn)密度聚類算法提出并實(shí)現(xiàn)了基于軌跡相似度的軌跡聚類方法；夏英等[15]充分考慮室內(nèi)移動軌跡的空間和語義特征，提出1種基于RFID位置語義的室內(nèi)移動軌跡聚類方法,該方法從空間形狀和位置語義2個(gè)方面加權(quán)計(jì)算軌跡相似度，采用改進(jìn)的層次聚類方法進(jìn)行室內(nèi)軌跡聚類。Huang等[16]提出了1種基于改進(jìn)AGNES算法的室內(nèi)運(yùn)動目標(biāo)軌跡分析和數(shù)據(jù)聚類算法，實(shí)現(xiàn)了室內(nèi)運(yùn)動目標(biāo)軌跡的提取與分析。陳建偉等[17]提出基于長短時(shí)記憶（long short term memory，LSTM）神經(jīng)網(wǎng)絡(luò)的編碼器-解碼器模型來預(yù)測人群移動軌跡；張宇等[18]基于圖卷積（graph convolution network,GCN）和LSTM模型，提出顧及橫向相似用戶軌跡特征以及縱向歷史規(guī)律性特征的個(gè)體位置預(yù)測算法。

基于以上分析可知，多數(shù)軌跡相似性度量算法是從時(shí)間和空間形狀相似性的角度提出，并直接或加以改進(jìn)后應(yīng)用于軌跡相似性計(jì)算，較少從位置語義相似性的維度考慮，并且軌跡數(shù)據(jù)的來源多以車載GPS數(shù)據(jù)和視頻監(jiān)控?cái)?shù)據(jù)為載體，以其他定位技術(shù)獲得的軌跡數(shù)據(jù)集也比較少。筆者提出1種利用UWB定位技術(shù)的Hausdorff-DBSCAN算法以發(fā)現(xiàn)郵輪內(nèi)部空間乘員之間的伴隨關(guān)系，該算法為解決傳統(tǒng)的Hausdorff距離無法解決相似度計(jì)算時(shí)時(shí)序一致性的問題，引入位置語義改進(jìn)度量模型使其更準(zhǔn)確，以室內(nèi)乘員移動軌跡相似性度量與DBSCAN軌跡聚類算法為框架，并利用LSTM神經(jīng)網(wǎng)絡(luò)對疑似伴隨關(guān)系對象進(jìn)行相似度變化趨勢的預(yù)測。

1 室內(nèi)乘員軌跡相似性度量模型

UWB室內(nèi)定位設(shè)備獲取的行人軌跡數(shù)據(jù)記錄了一系列軌跡點(diǎn)的空間和時(shí)間信息。移動對象在一段時(shí)間t1～tn內(nèi)走過的時(shí)空軌跡序列可由{(p1,t1),(p2,t2),…,(pn,tn)}表示。

1.1 軌跡點(diǎn)鄰近度計(jì)算

上述時(shí)空軌跡序列的表達(dá)適用于一般室外空間的軌跡數(shù)據(jù)，但郵輪室內(nèi)空間更狹小，設(shè)備采樣頻率更高，對象可能在一段時(shí)間內(nèi)經(jīng)過多個(gè)位置區(qū)域，如艙室→餐廳→游戲廳→超市，這種位置語義序列尤其反映出對象的移動行為特征。為此，計(jì)算2條移動軌跡相似性時(shí)，除了要考慮坐標(biāo)序列的相似性外，位置語義序列的相似性也不可忽視。

根據(jù)UWB定位技術(shù)的特點(diǎn)，郵輪內(nèi)小型的活動場所如乘客艙室可以采用零維定位基站，走廊通道等帶狀空間可以采用一維定位基站，大廳、影院等較大面積的凸?fàn)顖鏊梢圆捎枚S定位基站，這些區(qū)域之間依據(jù)船舶的空間布局會形成不同的差異性或相似性。在郵輪空間，乘員之間的相似程度不僅與歐式距離有關(guān)，也與這些乘員所處的區(qū)域之間的鄰近程度有關(guān)。本文在描述乘員之間的相似度時(shí)將每個(gè)乘員看成質(zhì)點(diǎn)，引入?yún)^(qū)域相似度和歐式距離，并給出點(diǎn)鄰近度的概念。

定義1。將零維區(qū)域記為，其中i∈(1,2,…,N0)，N0為室內(nèi)空間零維區(qū)域的數(shù)量；將一維區(qū)域記為，其中i∈(1,2,…,N1)，N1為室內(nèi)空間一維區(qū)域的數(shù)量；將二維區(qū)域記為，其中i∈(1,2,…,N2)，N2為室內(nèi)空間二維區(qū)域的數(shù)量。

定義2。不同位置區(qū)域的相似性用區(qū)域相似度表示，記為,其中a,b∈(0,1,2)，i1,i2確定區(qū)域信息，值由連接該區(qū)域的路徑長度給出，由于室內(nèi)空間區(qū)域的布局是固定的（假設(shè)路徑是規(guī)則的），因此各區(qū)域之間的路徑長度是確定常數(shù)，即a,b,i1,i2的取值一旦確定，的值就可以確定，且假定區(qū)域信息已經(jīng)涵蓋了移動對象所在的樓層信息。

定義3。軌跡點(diǎn)鄰近度(pi,pj)，其中，pi,pj分別為區(qū)域中的軌跡點(diǎn)，E(pi,pj)為pi,pj的歐式距離。

對軌跡點(diǎn)鄰近度的計(jì)算，有如下幾種情形。

1）當(dāng)a=b且i1=i2時(shí)，點(diǎn)pi,pj位于同一區(qū)域，令，則有?(pi,pj)=E(pi,pj)，此時(shí)定義如下3種情形：①若a=b=0，表示pi,pj在同1個(gè)零維定位區(qū)域，2點(diǎn)位置信息均由“1”表示存在，無法直接計(jì)算2點(diǎn)間的歐式距離，但有理由相信這2點(diǎn)已經(jīng)具有比較高的相似度，此時(shí)?(pi,pj)=E(pi,pj)=l，l是1個(gè)較小的常數(shù)；②若a=b=1，表示pi,pj在同1個(gè)一維定位區(qū)域，2點(diǎn)位置信息由(xi,yi)表示，計(jì)算2點(diǎn)一維距離代替歐式距離，此時(shí)?(pi,pj)=；③若a=b=2，表示pi,pj在同1個(gè)二維定位區(qū)域，2點(diǎn)位置信息由(xi,yi)表示，可以計(jì)算其歐式距離，此時(shí)?(pi,pj)=E(pi,pj)。

2）當(dāng)點(diǎn)pi,pj位于不同的區(qū)域，，由于假設(shè)空間路徑是規(guī)則的，有如下2種定義：①當(dāng)pi,pj所在區(qū)域能夠由較簡單的路徑連通時(shí)，依據(jù)其幾何中心的固定距離值計(jì)算軌跡點(diǎn)鄰近度?(pi,pj)=，c為常數(shù)，dab為當(dāng)pi,pj處于不同定位維度區(qū)域時(shí)，不便計(jì)算歐式距離所設(shè)計(jì)的歐式距離修正值，其值為常數(shù)；②當(dāng)pi,pj所在區(qū)域很難連通，1種典型情況是pi,pj幾何距離很近，但分隔在墻壁的兩邊，則這2點(diǎn)的鄰近度是很小的。此時(shí)令?(pi,pj)=M，對上述所有情形的點(diǎn)鄰近度值，有?(pi,pj)≥M。

1.2 改進(jìn)的Hausdorff距離軌跡相似度計(jì)算

由于傳統(tǒng)的Hausdorff距離計(jì)算無法篩選具有相反方向的軌跡，為了保證本文所定義的軌跡伴隨關(guān)系聚類的準(zhǔn)確性，在傳統(tǒng)的方法基礎(chǔ)上引入軌跡位置語義維度擴(kuò)展軌跡原始數(shù)據(jù)形式，假設(shè)1名乘員在郵輪中移動軌跡見圖1，那么該軌跡時(shí)空序列可以表示為

圖1 郵輪室內(nèi)空間軌跡序列

Fig.1 Trajectory sequence in the indoor space of the cruise

根據(jù)上述對軌跡時(shí)空序列的表達(dá)，可以將軌跡的坐標(biāo)點(diǎn)序列和位置語義序列描述為

其中：pi為軌跡序列Sp的第i個(gè)坐標(biāo)點(diǎn)；Ri為位置語義序列中的第i個(gè)區(qū)域，對應(yīng)pi所在的區(qū)域，這個(gè)區(qū)域由上述定義的表示。那么由坐標(biāo)和位置語義構(gòu)成的乘員軌跡點(diǎn)可以由向量v={xi,yi,Ri}來描述，則目標(biāo)軌跡序列可以表示為：tr={v1,v2,…,vn}。其中，n為1條軌跡序列包含的軌跡點(diǎn)個(gè)數(shù)。由此，軌跡序列tri與trj的距離可由雙向Hausdorff距離來計(jì)算。

式中：θ∈(0,1)。

2 基于Hausdorff-DBSCAN的乘員伴隨關(guān)系發(fā)現(xiàn)

2.1 DBSCAN軌跡聚類算法

DBSCAN算法是基于密度的聚類算法，被廣泛應(yīng)用于軌跡數(shù)據(jù)的聚類中，其核心思想是將樣本數(shù)據(jù)當(dāng)作質(zhì)點(diǎn)，基于1組鄰域參數(shù)(ε,Minpts)刻畫樣本空間的密度分布。DBSCAN算法理論上能找出任意形狀的類簇，且在聚類時(shí)無須事先確定聚類簇的個(gè)數(shù)，適用于本研究所描述的伴隨關(guān)系發(fā)現(xiàn)問題，因此選用該算法來實(shí)現(xiàn)乘員軌跡的聚類，本文將傳統(tǒng)DBSCAN算法中核心點(diǎn)的定義轉(zhuǎn)換成核心軌跡，以適應(yīng)研究需要。給定軌跡數(shù)據(jù)集D={tr1,tr2,…,trm}，有關(guān)定義如下。

定義4。ε-鄰域：對tri∈D，其ε-鄰域包含樣本集D中與tri的距離不大于ε的樣本，即

定義5。核心軌跡（core trajectory）：若trj的ε-鄰域至少包含Minpts個(gè)樣本，即Nε(trj)≥Minpts，則trj是1條核心軌跡。

定義6。密度直達(dá)（directly density-reachable）：若trj位于tri的ε-鄰域中，且tri是核心軌跡，則稱trj由tri密度直達(dá)。

定義7。密度可達(dá)（density-reachable）：對tri與trj，若存在樣本序列e1,e2,…,en，其中e1=tri，en=trj且ei+1由ei密度直達(dá)，則稱trj由tri密度可達(dá)。

定義8。密度相連（density-connected）：對tri與trj，若存在trk使得tri與trj均由trk密度可達(dá)，則稱tri與trj密度相連。

為解決基于定位軌跡數(shù)據(jù)的乘員伴隨關(guān)系發(fā)現(xiàn)問題，算法框架主要分為構(gòu)建軌跡相似性度量模型和聚類算法2個(gè)部分。為計(jì)算郵輪空間中乘員軌跡的相似性提出基于改進(jìn)Hausdorff距離的軌跡相似度計(jì)算方法，并利用DBSCAN算法聚類軌跡，將可能具有伴隨關(guān)系的乘員軌跡放入同1個(gè)聚類簇中。改進(jìn)的Hausdorff-DBSCAN算法發(fā)現(xiàn)伴隨關(guān)系的流程見圖2。

圖2 基于改進(jìn)Hausdorff-DBSCAN的算法流程Fig.2 Work flow of improved Hausdorff-DBSCANAlgorithm

2.2 聚類質(zhì)量評價(jià)指標(biāo)

為了反映伴隨關(guān)系發(fā)現(xiàn)算法的聚類質(zhì)量，選取精確度（precision）、召回率（recall）、F1值作為聚類質(zhì)量評價(jià)指標(biāo)。具體見式（6）～（8）。

式中：TP為同1個(gè)簇中的相似軌跡數(shù)；FP為同1個(gè)簇中的非相似軌跡數(shù)；FN為未正確聚類的相似軌跡數(shù)。

3 基于LSTM的乘員伴隨關(guān)系預(yù)測

前述聚類算法可以將記錄的軌跡進(jìn)行聚類，接下來研究利用LSTM神經(jīng)網(wǎng)絡(luò)，根據(jù)已有相似度序列，預(yù)測2名乘員間相似度未來的時(shí)序變化趨勢，與聚類結(jié)果對比，進(jìn)行乘員的伴隨關(guān)系驗(yàn)證。

3.1 循環(huán)神經(jīng)網(wǎng)絡(luò)與LSTM

RNN即循環(huán)神經(jīng)網(wǎng)路，與DNN、CNN不同，它不僅考慮前一時(shí)刻的輸入，而且賦予網(wǎng)絡(luò)對歷史信息的記憶功能。RNN中1個(gè)序列當(dāng)前的輸出與前面的輸出有關(guān)，其隱藏層之間的節(jié)點(diǎn)是有連接的，隱藏層的輸入不僅包括輸入層的輸出還包括上一時(shí)刻隱藏層的輸出。RNN的主要功能是處理、分析時(shí)序數(shù)據(jù)，其結(jié)構(gòu)見圖3。

圖3 RNN的結(jié)構(gòu)及隱藏層展開Fig.3 Structure of RNN and its unfolded hidden layer

LSTM神經(jīng)網(wǎng)絡(luò)是RNN的1種變體，神經(jīng)元結(jié)構(gòu)由輸入門、遺忘門、記憶門以及輸出門組成，見圖4。這些門結(jié)構(gòu)決定了數(shù)據(jù)信息的輸入、存儲、遺忘以及輸出。

圖4 LSTM細(xì)胞結(jié)構(gòu)Fig.4 Cell structure of LSTM

基于LSTM的伴隨關(guān)系對象相似度預(yù)測是1個(gè)無監(jiān)督模型，對于2個(gè)存在伴隨關(guān)系可能性的乘員，利用靠前的時(shí)間步的點(diǎn)鄰近度序列來預(yù)測后續(xù)的點(diǎn)鄰近度值。模型的輸入為1個(gè)定長時(shí)間窗口的點(diǎn)鄰近度序列，輸出則是下1個(gè)時(shí)間點(diǎn)的點(diǎn)鄰近度值。

3.2 伴隨關(guān)系趨勢預(yù)測與對比驗(yàn)證

假設(shè)有z名乘員，對某些軌跡數(shù)據(jù)記錄節(jié)點(diǎn)比較少的對象經(jīng)過插值處理補(bǔ)全，使每1名位乘員移動軌跡的時(shí)間節(jié)點(diǎn)數(shù)相同（均為n），且在Anylogic中設(shè)置記錄數(shù)據(jù)的起止時(shí)間、采樣頻率保持一致（保證時(shí)間同步性），數(shù)據(jù)記錄見表1。

表1 t1時(shí)刻各乘員位置記錄Tab.1 Position records of each passenger at time t1

根據(jù)軌跡聚類結(jié)果，篩選出可能存在伴隨關(guān)系的對象，將軌跡相似度計(jì)算時(shí)的點(diǎn)鄰近度序列當(dāng)做輸入，利用LSTM對其點(diǎn)鄰近度變化趨勢進(jìn)行預(yù)測，分析乘員伴隨關(guān)系的演變，同時(shí)對比驗(yàn)證軌跡聚類結(jié)果的有效性。

乘員i和j的點(diǎn)鄰近度序列，按1.1中的定義3計(jì)算，得到鄰近度數(shù)據(jù)后，將數(shù)據(jù)集劃分為訓(xùn)練集和測試集，將點(diǎn)鄰近度序列前75%的數(shù)據(jù)作為訓(xùn)練集，后25%的數(shù)據(jù)作為測試集。

4 實(shí)驗(yàn)分析

本研究實(shí)驗(yàn)環(huán)境為2.30 GHz GPU，16 GB RAM，Windows10系統(tǒng)，在Anaconda 3.5和Python 3.8環(huán)境中進(jìn)行實(shí)驗(yàn)，用到的深度學(xué)習(xí)框架為Tensorflow，Python工具庫有Sklean、pandas、numpy、scipy等，仿真軟件為Anylogic。

4.1 實(shí)驗(yàn)數(shù)據(jù)

由于現(xiàn)實(shí)因素沒有條件在郵輪中安裝定位設(shè)備進(jìn)行試驗(yàn)采集數(shù)據(jù)，研究采用Anylogic構(gòu)建郵輪室內(nèi)環(huán)境模型進(jìn)行乘員仿真，采集乘員軌跡數(shù)據(jù)。

原始數(shù)據(jù)格式為：編號、時(shí)間點(diǎn)、橫向距離、縱向距離、區(qū)域。從仿真試驗(yàn)中獲取了200條軌跡數(shù)據(jù)，一共12 111個(gè)軌跡點(diǎn)，其中單條軌跡最大節(jié)點(diǎn)數(shù)為113。數(shù)據(jù)集中的部分?jǐn)?shù)據(jù)見表2。

表2 行人軌跡數(shù)據(jù)樣本Tab.2 Samples of pedestrian trajectory data

4.2 實(shí)驗(yàn)結(jié)果

4.2.1 歸一化相似度矩陣

經(jīng)計(jì)算，各軌跡之間歸一化相似度見表3，對角線的值為1，表示每條軌跡與其自身的相似度，表格中值越大表示相似度越高。根據(jù)軌跡數(shù)據(jù)的聚類，無法100%確定同一類簇中的乘員是伴隨關(guān)系，其存在伴隨關(guān)系的概率由他們之間的歸一化軌跡相似度來確定。

表3 軌跡間歸一化相似度Tab.3 Normalized similarity between trajectories

4.2.2 軌跡聚類結(jié)果

經(jīng)過軌跡聚類，仿真試驗(yàn)中的200條郵輪空間乘員軌跡被劃分成20類。圖5為200條乘員軌跡的聚類可視化結(jié)果，表4中列出了軌跡聚類的部分簇劃分和每類中的乘員編號。郵輪建模的原型為“海洋量子號”第4層，見圖6。圖7為單個(gè)類簇軌跡的可視化結(jié)果。

圖5 聚類結(jié)果可視化Fig.5 Visualization of clustering results

表4 部分聚類簇及其簇間元素Tab.4 Partial clusters and the elements among them

圖6 “海洋量子”號郵輪第4層模型Fig.6 The 4th floor model of Quantum of the Seas

圖7 類簇0，7和9中的軌跡可視化Fig.7 Visualization of trajectories in Cluster 0，7 and 9

可以看出，200條軌跡被聚類成多個(gè)簇，每1個(gè)簇中包含著疑似伴隨關(guān)系的軌跡對象，因此本文提出的算法能夠有效的發(fā)現(xiàn)可能存在伴隨關(guān)系的乘員。由于乘客在郵輪內(nèi)活動路徑的選擇具有較大隨機(jī)性，整體軌跡分布規(guī)律通常會呈現(xiàn)多種模式，也就導(dǎo)致存在眾多伴隨關(guān)系對象組，因而聚類也呈現(xiàn)出伴隨關(guān)系簇的個(gè)數(shù)較多的結(jié)果，這與郵輪乘員室內(nèi)移動軌跡的一般規(guī)律是相符合的。

4.2.3 基于LSTM預(yù)測相似度

在LSTM神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程中，時(shí)間窗口長度time_window=3，輸入的數(shù)據(jù)維度data_dim=1，初始學(xué)習(xí)率α=0.01，迭代次數(shù)為100，神經(jīng)網(wǎng)絡(luò)中選取Relu函數(shù)為激活函數(shù)，優(yōu)化器為Adam，訓(xùn)練誤差計(jì)算采用均方誤差（MSE）。

圖8為1組非伴隨關(guān)系乘員的運(yùn)動軌跡，圖9為他們相似度序列訓(xùn)練過程的誤差變化，當(dāng)?shù)螖?shù)到達(dá)40次以后，誤差值趨于穩(wěn)定且達(dá)到較小的值，約為3%，可以得知LSTM算法對非結(jié)伴關(guān)系乘員相似度變化趨勢的預(yù)測具有較高的準(zhǔn)確性。圖10為訓(xùn)練結(jié)果和測試結(jié)果與真實(shí)值的對比。若相似度閾值取為0.6，可以看到一開始2名乘員相似度較高，40個(gè)時(shí)刻后相似度開始下降，最后又有上升的趨勢，這與圖8所示情況基本一致，可以判斷這2名對象在這段時(shí)間內(nèi)大概率為非伴隨關(guān)系，但也有可能是原來具有伴隨關(guān)系的乘員，只是因某種原因分離了一小段時(shí)間，由此可知，LSTM神經(jīng)網(wǎng)絡(luò)的預(yù)測結(jié)果是比較準(zhǔn)確的。

圖8 非伴隨關(guān)系的2條軌跡Fig.8 Non-accompanying relationship of two trajectories

圖9 非伴隨乘員軌跡訓(xùn)練誤差值變化Fig.9 Training loss variation of the non-accompanying trajectories

圖10 LSTM模型輸出與真值對比Fig.10 Comparison of the output and the true value of LSTM model

上述非伴隨關(guān)系的2名乘員運(yùn)動時(shí)間步較短，為防止較大誤差，進(jìn)一步驗(yàn)證LSTM模型的準(zhǔn)確性，增加仿真時(shí)長、提高采樣頻率以擴(kuò)大軌跡點(diǎn)數(shù)量再進(jìn)行訓(xùn)練。圖11為2條整體相似度比較高的軌跡，均由1 000個(gè)軌跡點(diǎn)構(gòu)成。由圖11可見：這1條軌跡總是保持很近的距離，因此可以判斷對應(yīng)的2名乘客極大可能是伴隨關(guān)系，對具有這種伴隨關(guān)系的乘客位置信息的準(zhǔn)確發(fā)現(xiàn)與識別，在群組中有乘員行蹤異常時(shí)提供預(yù)警，對郵輪乘客安全管理有重要意義。

圖11 具有伴隨關(guān)系的2條軌跡Fig.11 Accompanying relationship of two trajectories

由圖12可知：這2條軌跡的點(diǎn)鄰近度序列訓(xùn)練誤差值在迭代40次后逐漸收斂到1個(gè)較低的值，約為4%，證實(shí)了LSTM算法對具有伴隨關(guān)系乘員相似度演變趨勢預(yù)測的準(zhǔn)確性。

圖12 伴隨乘員軌跡訓(xùn)練誤差值值變化Fig.12 Training loss variation of the accompanying trajectories

圖13為訓(xùn)練結(jié)果和測試結(jié)果與真實(shí)值的對比。圖14將測試集與真實(shí)數(shù)據(jù)單獨(dú)進(jìn)行對比，可以看出，訓(xùn)練與測試結(jié)果中相似度的變化趨勢，與圖14中2軌跡伴隨關(guān)系的演變趨勢基本一致，因此在更大的數(shù)據(jù)文獻(xiàn)[15]的LTCRLS算法和文獻(xiàn)[16]的improved_ANGES量中LSTM神經(jīng)網(wǎng)絡(luò)的預(yù)測結(jié)果也比較準(zhǔn)確，且與軌跡聚類結(jié)果比較吻合。

圖13 LSTM模型輸出與真值對比Fig.13 Comparison of the output and the true value of LSTM model

圖14 伴隨乘員軌跡點(diǎn)鄰近度的預(yù)測結(jié)果Fig.14 Points similarity prediction of accompanying crews

4.2.4 算法性能評價(jià)

為了評價(jià)聚類質(zhì)量，將此算法與文獻(xiàn)中常見的聚類算法進(jìn)行對比，4種算法分別為DTW-DBSCAN[19]，improved-ANGES[16]，Grid-based[20]，Hausdorff-DBSCAN，選定參數(shù)值ε=0.7，對比分析結(jié)果見表5。

表5 不同聚類算法性能對比Tab.5 Performance comparison of different clustering algorithms

從表5中可以看出，無論是precision，recall，還是F1指標(biāo)，本文提出的改進(jìn)的Hausdorff-DBSCAN算法相比于其他算法均有顯著提升。其中，improved-ANGES算法準(zhǔn)確性最低，原因是其在計(jì)算相似度時(shí)未考慮軌跡方向和位置時(shí)序的問題，在計(jì)算時(shí)可能將相似度差異較大的軌跡劃分到一類。本文提出的算法在相似度計(jì)算時(shí)增加了位置語義的維度，在聚類時(shí)以單條軌跡作為核心，準(zhǔn)確性也有較大提升，相比于improved-ANGES算法，precision，recall和F1分別提升了5.7%，8.0%和6.7%，相對于Gridbased算法，precision，recall和F1分別提升了8.2%，21.8%和14.9%，說明改進(jìn)的Hausdorff-DBSCAN算法通過將乘客軌跡的時(shí)序位置和軌跡方向考慮進(jìn)軌跡相似度計(jì)算，能夠更準(zhǔn)確地完成軌跡聚類和伴隨關(guān)系發(fā)現(xiàn)。

5 結(jié)束語

為發(fā)現(xiàn)擁有相似移動規(guī)律或模式的郵輪內(nèi)乘員，綜合考慮室內(nèi)環(huán)境結(jié)構(gòu)和UWB定位技術(shù)的特點(diǎn)，研究了郵輪內(nèi)乘員伴隨關(guān)系發(fā)現(xiàn)算法。該方法從郵輪內(nèi)部乘客的軌跡相似性度量和軌跡聚類入手，以基于改進(jìn)Hausdorff距離的軌跡相似性度量和DBSCAN算法為框架進(jìn)行軌跡聚類。實(shí)驗(yàn)結(jié)果表明，該方法能有效評價(jià)室內(nèi)移動軌跡相似性，在解決伴隨關(guān)系對象組的發(fā)現(xiàn)問題中取得了較好的聚類效果和效率。另外，利用LSTM神經(jīng)網(wǎng)絡(luò)對伴隨關(guān)系對象的相似度趨勢變化進(jìn)行驗(yàn)證和預(yù)測，取得了很好的效果。但是仍存在數(shù)據(jù)集不夠，更細(xì)致的室內(nèi)環(huán)境因素未考慮在內(nèi)的不足之處，基于此，在后續(xù)工作中，本文會進(jìn)一步擴(kuò)充數(shù)據(jù)集與考慮更多室內(nèi)環(huán)境信息，同時(shí)未來計(jì)劃研究伴隨關(guān)系中的異常行為檢測問題，如個(gè)體的偏移行為或由于偏移或重聚導(dǎo)致的伴隨關(guān)系趨勢演變等問題