基于單向距離的譜聚類船舶運動模式辨識

馬文耀，吳兆麟，楊家軒，李偉峰

(1. 大連海事大學 航海學院，遼寧 大連 116026；2. 廣東海洋大學 航海學院，廣東 湛江 524000)

?

基于單向距離的譜聚類船舶運動模式辨識

馬文耀1，2，吳兆麟1，楊家軒1，李偉峰1

(1. 大連海事大學 航海學院，遼寧 大連 116026；2. 廣東海洋大學 航海學院，廣東 湛江 524000)

利用海事大數據辨識船舶運動模式，能夠發現高級別情景意識，提高海事監管技術的效率。提出了一種基于單向距離的譜聚類船舶運動模式辨識方法，充分利用單向距離抗干擾特點，構建了基于單向距離的軌跡相似性度量，得到了軌跡相似度矩陣；以無監督學習方式采用譜聚類算法學習軌跡的空間分布，獲取船舶的正常運動模式；以瓊州海峽實測AIS數據為樣本，研究了進入?？谛阌⒏鄣拇斑\動模式，并分別統計了各模式內及模式之間的距離，獲取的4種船舶運動模式與實際相符。實驗結果表明：該方法聚類精度高，可以適用于沿海港口、狹水道和船舶交通復雜的區域的船舶運動模式辨識。

交通運輸工程；運動模式；單向距離；譜聚類；相似性度量

0 引 言

隨著海事云服務和大數據時代的來臨，以及全球岸基AIS(Automatic Identification System, AIS)網絡的建立，形成了海量船舶運動的數據庫。利用海量數據來識別船舶運動模式[1]和挖掘高層次的情境感知，將有助于理解交通模式的季節性差異。聚類的航線能反映出不同船舶類型的船舶日常模式和航行時間等信息的差異，這些知識能提高目標船舶跟蹤和海事監管效率。

影響船舶運動模式識別的兩個重要方面是高效的模型和時空軌跡聚類算法。目前國內外許多學者多針對道路交通的運動目標進行研究，提出了各種從目標軌跡中獲取運動模式的算法。馮宏祥等[2]利用基于AIS的元胞自動機船舶交通流模型模擬再現船舶交通流，獲得船舶運動模式。胡宏宇等[3]利用改進的Hausdorff距離和譜聚類算法學習車輛軌跡的空間分布，提取運動目標的典型運動模式。聞佳等[4]設計了一種考慮到運動車輛軌跡方向性和運動性等特征的加權矢量Hausdorff距離公式，獲取車輛運動模式，該方法需計算軌跡的運動特性，計算較為復雜。Lin Bin等[5]采用單向距離對運動目標的軌跡相似性進行計算，對軌跡分類，取得良好效果。N.Johnson等[6]和N.Sumpter等[7]采用自組織特征映射神經網絡的方法對軌跡空間模式學習進行建模。W.Hu等[8]采用模糊自組織神經網絡對目標軌跡的運動模式進行學習?；谏窠浘W絡的方法在構建網絡方面較為復雜，學習速度較慢，且在學習過程中需要大量的數據學習參數。

無監督聚類算法也廣泛應用，S.Atev等[9]和F.I.Bashir等[10]利用K均值聚類對軌跡空間模式進行學習；W.Hu等[8]利用模糊均值聚類的方法獲取目標運動模式。但這幾種方法需要對軌跡的長度進行標準化，損失了軌跡的部分原始狀態信息。D.Biliotti等[11]采用層次聚類對軌跡進行分類，而層次聚類方法中某一層次的分解(合并)誤差會導致整體模式學習效果的下降。另外，N.Junejo等[12]采用圖分割將軌跡集合劃分為多個子集以獲取運動行為模式；L.Wang等[13]采用譜聚類方法學習目標軌跡運動模式。

道路交通中運動模式辨識方法一般先選擇適當的距離來度量軌跡相似性，再利用分類或聚類算法，對運動軌跡進行劃分，從而獲得車輛運動模式。與道路交通相比，海上交通有其獨特性。在開闊海域船舶與公路網絡中移動車輛不同，其在空間上移動幾乎無約束，船舶運動軌跡分布較廣。而在港口、狹水道和交通復雜區域，船舶通航密度大，軌跡從而相對密集，同時船舶交通還受到陸域、航道、水深和交通管制等因素限制，使其呈現出與道路交通相似的規則性運動模式。因此，筆者參照道路交通中的運動模式辨識方法提出基于單向距離的譜聚類船舶運動模式辨識算法，即先采用單向距離度量船舶軌跡之間的相似性，再利用譜聚類算法[13]獲取船舶軌跡的時空分布，從而提取船舶運動模式。

1 船舶軌跡的相似性

1.1 船舶軌跡數據的預處理

船舶的軌跡主要由船載自動識別系統設備獲得。AIS設備以不同發送時間間隔(范圍從3 min～2 s不等)發送本船的船位、船速、航向、船名、船長、船寬、國際海事組織(IMO)編號和海上移動業務識別碼(MMSI)等信息。有時由于船舶發送AIS消息超出岸臺AIS接收范圍導致該船舶軌跡不全、或存在船舶AIS設備故障導致軌跡中出現部分錯誤或軌跡缺失等問題。這些因素，都會影響到船舶軌跡的分類、識別及后期的行為分析等。因此，在進行軌跡聚類前，必須對船舶的軌跡進行預處理。

1.2 船舶軌跡的相似性度量

運動軌跡劃分的基礎在于合理度量軌跡之間的相似性。目前軌跡的相似性度量方法有基于歐氏距離ED(Euclidean Distance)的方法、基于最長公共子序列的方法、基于動態時間彎曲距離的方法和基于Hausdorff距離的方法。歐式距離僅用于計算等長船舶間軌跡的相似性；最長公共子序列、Hausdorff距離和單向距離能用于不同長度船舶軌跡的相似性計算；而單向距離還能克服Hausdorff距離對噪聲不敏感的缺陷。因此，筆者采用單向距離來度量軌跡空間的相似程度。

1.3 單向距離度量軌跡相似性

點p到軌跡T的距離定義為：

d(p,T)=minq∈TdED(p,q)

(1)

式中：q是軌跡T中的點；dED(p,q)表示點p到點q的歐氏距離。

軌跡T1到T2的單向距離定義為：

(2)

式中：NT1為軌跡T1中點的個數，該距離是有向距離(即dowd(T1,T2)和dowd(T2,T1)通常情況下是不等的)，軌跡T1到T2的距離使用dowd(T1,T2)和dowd(T2,T1)的平均距離表示。

(3)

從式(2)可以看出，單向距離實際上是一條軌跡上各個點到另一條軌跡中點的最小距離的平均值，所以對軌跡點中的噪聲具有較強抗干擾能力。軌跡T1，T2之間的相似度函數定義為：

s(T1,T2)=e-[d(T1,T2)/(2σ2)]

(4)

式中：σ為尺度參數，表示相似性隨著距離增大而衰減的程度，可采用信息熵計算得到。軌跡間距離越大，其相似性就越低。

2 基于譜聚類的船舶軌跡學習

基于所定義的軌跡之間的相似度表達，筆者采用譜聚類算法將軌跡按照空間相似度進行劃分，獲取目標軌跡的空間分布。譜聚類算法建立在譜圖理論基礎上，具有全局收斂的優點，能對任意形狀的樣本空間進行聚類且收斂于全局最優解。該算法把前面定義得到的相似度矩陣映射到親合矩陣，并計算親和矩陣的特征值和特征向量，得到運動模式的數目，使用K-means算法聚類出船舶運動模式?；谧V聚類的船舶軌跡學習算描述如下。

Step1：對于包含n條有效運動軌跡的集合T={T1，T2，…，Tn}，用單向距離對軌跡間空間相似性進行描述，構建n×n的相似度矩陣：

(5)

Step2：由相似度矩陣S和度矩陣D計算Laplacian矩陣L，并對其進行特征分解。

Step3：將特征分解得到的特征值由小到大排序，則運動模式的個數k取為：

k=argimax|λ(i+1)-λi|

Step4：計算k個最小特征值所對應的特征向量，x1，x2，…，xk，構建矩陣X=[x1，x2，…，xk]；將X的每一行進行歸一化，得到特征向量空間矩陣Y：

(6)

Step5：軌跡Ti對應Y中第i個行向量。將Y中每一行看作k維空間中的一個向量，使用K-means算法進行聚類，將軌跡劃分為k類。

上述算法能對軌跡的空間分布進行有效學習，從而將軌跡集合中的軌跡樣本劃分為相應的軌跡簇，即船舶運動模式。為了簡潔地描述運動模式，使用軌跡簇的中心軌跡表征運動模式。對于第k個軌跡簇中任意一條軌跡Ti計算其與該簇中其他軌跡的平均距離：

(7)

(8)

通過式(7)可以得到包含nk條軌跡的第k個軌跡簇的中心軌跡Tm，Tm與該簇中其他軌跡的平均距離最小，也可表征某交通場景下運動目標的第k個運動模式。

3 實驗分析

為驗證筆者提出方法的有效性，使用實測AIS數據辨識船舶運動模式，并與實際交通進行比較。數據樣本為瓊州海峽2013年某月份的AIS數據記錄，研究的水域范圍為20°01′N～20°18′N，109°55′E～110°32′E。研究水域及船舶運動軌跡分布如圖1。

圖1 瓊州海峽船舶運動軌跡分布Fig.1 Ship motion trajectory distribution of Qiongzhou strait

對AIS數據進行數據清洗，消除錯誤和缺失的軌跡數據，并選取進入?？诟鄣拇败壽E，得出有效船舶運動軌跡364條。使用筆者提出的算法進行空間聚類后，得到4種船舶運動模式，如圖2。每類軌跡運行的所在區域恰好與瓊州海峽內通航分道和進港航道區域一一對應。如果船舶進入海口秀英港(不考慮異常行為)，在該海域會有4種典型運動模式，即海安港至秀英港模式，與圖2(a)表示的軌跡簇對應；海安新港至秀英港模式，與圖2(b)表示的軌跡簇對應；海峽東入口至秀英港模式，與圖2(c)表示的軌跡簇對應；海峽西入口至?？诟勰Ｊ?，與圖2(d)表示的軌跡簇對應。

圖2 船舶運動模式Fig.2 Motion patterns of vessels

聚類實驗結果與實際情況符合，表明了該方法進行船舶軌跡聚類的可行和準確性，4種船舶運動模式軌跡聚類情況統計如表1～表4。表中，d1～d4分別表示類內距離平均值、類內距離最大值、類間距離平均值和類間距離最小值，距離單位為n mile。

表1 進入秀英港船舶模式

表2 類內距離的平均值(d1)和最大值(d2)

表3 類間距離的平均值(d3)

表4 類間距離的最小值(d4)

從表2中看出4種模式中類內平均距離(d1)全都小于0.3 n mile，表明各模式中軌跡之間相互接近，且距離較??；P3和P4模式的最大的類內距離(d2)分別為0.38和0.34 n mile，均小于通航分道寬度(1.3 n mile)的1/2。P3和P4模式分別表示海峽東入口至秀英港和西入口至秀英港模式，屬于該模式的船舶運動軌跡都處于通航分道內，且軌跡間最大距離小于通航分道寬度的1/2，表明通過瓊州海峽的船舶都幾乎航行在通航分道的中間，且分布較為集中。

表3和表4中得出模式P1與模式P2的類間平均距離(d3)小于1.36 n mile，且最小類間距離僅為0.76 n mile，表明這兩類運動模式極為類似。從圖2中容易看出海安港到秀英港的模式(P1)與海安新港到秀英港的模式(P2)相似，大多數船舶軌跡互相接近，但出發港位置不同。其它軌跡簇之間的類間距離大于4 n mile，很容易區分出運動模式。

4 結 語

筆者提出了一種基于單向距離的譜聚類船舶運動模式辨識方法，使用單向距離度量船舶軌跡之間的相似性，構建得到了船舶軌跡間相似性矩陣，并映射到譜聚類中的親合矩陣，以無監督學習方式利用譜聚類算法識別出船舶運動模式。使用瓊州海峽得實測AIS數據，以?？谛阌⒏蹫檠芯繉ο?，對進入該港的船舶運動模式進行辨識，聚類出了4種運動模式，并統計了各模式內及模式之間的距離，聚類結果與實際相符，實驗結果表明該方法聚類精度高，可以適用于沿海港口、狹水道和船舶交通復雜的區域的船舶運動模式辨識。

[1] 朱飛祥,張英俊,高宗江.基于數據挖掘的船舶行為研究[J].中國航海,2012,35(2):50-54. Zhu Feixiang,Zhang Yingjun,Gao Zongjiang.Research on ship behaviors based on data mining [J].Journal of Navigation of China,2012,35(2):50-54.

[2] 馮宏祥,孔凡邨,肖英杰,等.基于AIS的元胞自動機模型的船舶交通流特征參數分析[J].武漢理工大學學報:交通科學與工程版,2014,38(2):324-328. Feng Hongxiang,Kong Fancun,Xiao Yingjie,et al.Parameters characteristics analysis of ship traffic flow with cellular automata model on AIS-based [J].Journal of Wuhan University of Technology:Transportation Science & Engineering,2014,38(2):324-328.

[3] 胡宏宇,王慶年,曲昭偉,等.運動目標空間模式辨識與異常交通行為檢測[J].吉林大學學報,2011,41(6):1598-1602. Hu Hongyu,Wang Qingnian,Qv Zhaowei,et al.Spatial pattern recognition and abnormal traffic behavior detection of moving object [J].Journal of Jilin University,2011,41(6):1598-1602.

[4] 聞佳,崔維.實時視頻中的車輛運動軌跡的提取和聚類[J].計算機工程與應用,2010,46(11):155-157. Wen Jia,Cui Wei.Extraction and clustering of vehicle’s trajectories from live video [J].Computer Engineering and Applications,2010,46(11):155-157.

[5] Lin Bin,Su Jianwen.One way distance:for shape based similarity search of moving object trajectories [J].Journal of Geo-informatics,2008,12(2):117-142.

[6] Johnson N,Hogg D.Learning the distribution of object trajectories for event recognition [J].Image and Vision Computing,1996,14(8):609-615.

[7] Sumpter N,Bulpitt A J.Learning spatial-temporal patterns for predicting object behavior [J].Image and vision Computing,2000,18(9):697-704.

[8] Hu W,Xie D,Tan T,et al.Learning activity patterns using fuzzy self-organizing neural network [J].IEEE Transactions on Systems,machinery and Cybernetics Part B:Cybernetics,2004,34(3):1618-1626.

[9] Atev S,Masoud O,Papanikolopoulos N.Learning traffic patterns at intersections by spectral clustering of motion trajectories [C]//IEEE International Conference on Intelligent Robots and Systems.Beijing:[s.n.],2006.

[10] Bashir F I,Khokhar A A,Schonfeld D.Object trajectory-based activity classification and recognition using hidden Markov models [J].IEEE Transactions on Image Processing,2007,16(7):1912-1919.

[11] Biliotti D,Antonimi G,Thiran J P.Multi-layer hierarchical clustering of pedestrian trajectories for automatic counting of people in video sequences [C]//Proceedings-IEEE Workshop on Motion and Video Computing.Breckenridge,Colorado:[s.n.],2007.

[12] Junejo N,Javed O,Shah M.Multi-feature path modeling for video surveillance [C]//Proceedings of the 17th International Conference on Pattern Recognition.Washington,D.C.,USA:[s.n.],2004.

[13] Wang L,Hu W M,Tan T N.Recent developments in human motion analysis [J].Pattern Recognition,2003,36(3):585-601

Vessel Motion Pattern Recognition Based on One-Way DistanceSpectral Clustering Algorithm

Ma Wenyao1, 2, Wu Zhaolin1, Yang Jiaxuan1, Li Weifeng1

(1. Navigation College, Dalian Maritime University, Dalian 116026, Liaoning, China; 2. Navigation College, Guangdong Ocean University, Zhanjiang 524000, Guangdong, China)

The vessel motion pattern recognition from marine large data can discovery high-level situational awareness, which improves the efficiency of maritime surveillance technology. Therefore, a motion pattern of vessel recognition methods based on one-way distance spectral clustering algorithm was proposed. The anti-interference of the one-way distance measurement was fully used to form the similarity value of trajectory based on one-way distance, and then the similarity matrix of the trajectory was also obtained. The regular motion patterns of vessels were extracted from the trajectories spatial distribution learnt by the spectral clustering algorithm in unsupervised learning way. Finally, the motion patterns for vessels entering into Xiuying port were analyzed by using real AIS data sample in Qiongzhou strait. And distance of inner pattern class and distance between of pattern class were calculated separately. Four obtained typical patterns were in consistence with those of the real traffic. The experiment results demonstrate that the proposed clustering methods is of good performance and well fit for identifying motion patterns of vessel in areas, such as coastal ports, narrow channels and complicated traffic zones.

transportation engineering; motion pattern; one-way distance; spectral clustering; similarity measure

10.3969/j.issn.1674-0696.2015.05.26

2014-05-28；

2014-08-29

國家自然科學基金項目(61073134)；中央高校基本科研業務費項目(3132013015)

馬文耀(1980—)，男，湖北潛江人，副教授，博士研究生，主要從事海上交通工程及交通信息工程及控制方面的研究。E-mail: wenyaoma1980@163.com。

U672.5

A

1674-0696(2015)05-130-05