基于UWB定位的郵輪乘員伴隨關系發(fā)現算法*

嚴思迅 吳 兵 商 蕾，3 呂潔印 汪 洋▲

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

0 引 言

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

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

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

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

1 室內乘員軌跡相似性度量模型

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

1.1 軌跡點鄰近度計算

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

根據UWB定位技術的特點，郵輪內小型的活動場所如乘客艙室可以采用零維定位基站，走廊通道等帶狀空間可以采用一維定位基站，大廳、影院等較大面積的凸狀場所可以采用二維定位基站，這些區(qū)域之間依據船舶的空間布局會形成不同的差異性或相似性。在郵輪空間，乘員之間的相似程度不僅與歐式距離有關，也與這些乘員所處的區(qū)域之間的鄰近程度有關。本文在描述乘員之間的相似度時將每個乘員看成質點，引入區(qū)域相似度和歐式距離，并給出點鄰近度的概念。

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

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

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

對軌跡點鄰近度的計算，有如下幾種情形。

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

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

1.2 改進的Hausdorff距離軌跡相似度計算

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

圖1 郵輪室內空間軌跡序列

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

根據上述對軌跡時空序列的表達，可以將軌跡的坐標點序列和位置語義序列描述為

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

式中：θ∈(0,1)。

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

2.1 DBSCAN軌跡聚類算法

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

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

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

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

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

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

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

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

2.2 聚類質量評價指標

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

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

3 基于LSTM的乘員伴隨關系預測

前述聚類算法可以將記錄的軌跡進行聚類，接下來研究利用LSTM神經網絡，根據已有相似度序列，預測2名乘員間相似度未來的時序變化趨勢，與聚類結果對比，進行乘員的伴隨關系驗證。

3.1 循環(huán)神經網絡與LSTM

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

圖3 RNN的結構及隱藏層展開Fig.3 Structure of RNN and its unfolded hidden layer

LSTM神經網絡是RNN的1種變體，神經元結構由輸入門、遺忘門、記憶門以及輸出門組成，見圖4。這些門結構決定了數據信息的輸入、存儲、遺忘以及輸出。

圖4 LSTM細胞結構Fig.4 Cell structure of LSTM

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

3.2 伴隨關系趨勢預測與對比驗證

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

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

根據軌跡聚類結果，篩選出可能存在伴隨關系的對象，將軌跡相似度計算時的點鄰近度序列當做輸入，利用LSTM對其點鄰近度變化趨勢進行預測，分析乘員伴隨關系的演變，同時對比驗證軌跡聚類結果的有效性。

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

4 實驗分析

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

4.1 實驗數據

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

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

表2 行人軌跡數據樣本Tab.2 Samples of pedestrian trajectory data

4.2 實驗結果

4.2.1 歸一化相似度矩陣

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

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

4.2.2 軌跡聚類結果

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

圖5 聚類結果可視化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條軌跡被聚類成多個簇，每1個簇中包含著疑似伴隨關系的軌跡對象，因此本文提出的算法能夠有效的發(fā)現可能存在伴隨關系的乘員。由于乘客在郵輪內活動路徑的選擇具有較大隨機性，整體軌跡分布規(guī)律通常會呈現多種模式，也就導致存在眾多伴隨關系對象組，因而聚類也呈現出伴隨關系簇的個數較多的結果，這與郵輪乘員室內移動軌跡的一般規(guī)律是相符合的。

4.2.3 基于LSTM預測相似度

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

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

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

圖9 非伴隨乘員軌跡訓練誤差值變化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

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

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

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

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

圖13為訓練結果和測試結果與真實值的對比。圖14將測試集與真實數據單獨進行對比，可以看出，訓練與測試結果中相似度的變化趨勢，與圖14中2軌跡伴隨關系的演變趨勢基本一致，因此在更大的數據文獻[15]的LTCRLS算法和文獻[16]的improved_ANGES量中LSTM神經網絡的預測結果也比較準確，且與軌跡聚類結果比較吻合。

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

圖14 伴隨乘員軌跡點鄰近度的預測結果Fig.14 Points similarity prediction of accompanying crews

4.2.4 算法性能評價

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

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

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

5 結束語

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