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

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

?

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

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

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

利用海事大數(shù)據(jù)辨識船舶運動模式，能夠發(fā)現(xiàn)高級別情景意識，提高海事監(jiān)管技術(shù)的效率。提出了一種基于單向距離的譜聚類船舶運動模式辨識方法，充分利用單向距離抗干擾特點，構(gòu)建了基于單向距離的軌跡相似性度量，得到了軌跡相似度矩陣；以無監(jiān)督學(xué)習(xí)方式采用譜聚類算法學(xué)習(xí)軌跡的空間分布，獲取船舶的正常運動模式；以瓊州海峽實測AIS數(shù)據(jù)為樣本，研究了進(jìn)入海口秀英港的船舶運動模式，并分別統(tǒng)計了各模式內(nèi)及模式之間的距離，獲取的4種船舶運動模式與實際相符。實驗結(jié)果表明：該方法聚類精度高，可以適用于沿海港口、狹水道和船舶交通復(fù)雜的區(qū)域的船舶運動模式辨識。

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

0 引 言

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

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

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

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

1 船舶軌跡的相似性

1.1 船舶軌跡數(shù)據(jù)的預(yù)處理

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

1.2 船舶軌跡的相似性度量

運動軌跡劃分的基礎(chǔ)在于合理度量軌跡之間的相似性。目前軌跡的相似性度量方法有基于歐氏距離ED(Euclidean Distance)的方法、基于最長公共子序列的方法、基于動態(tài)時間彎曲距離的方法和基于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中點的個數(shù)，該距離是有向距離(即dowd(T1,T2)和dowd(T2,T1)通常情況下是不等的)，軌跡T1到T2的距離使用dowd(T1,T2)和dowd(T2,T1)的平均距離表示。

(3)

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

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

(4)

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

2 基于譜聚類的船舶軌跡學(xué)習(xí)

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

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

(5)

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

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

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

Step4：計算k個最小特征值所對應(yīng)的特征向量，x1，x2，…，xk，構(gòu)建矩陣X=[x1，x2，…，xk]；將X的每一行進(jìn)行歸一化，得到特征向量空間矩陣Y：

(6)

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

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

(7)

(8)

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

3 實驗分析

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

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

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

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

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

表1 進(jìn)入秀英港船舶模式

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

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

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

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

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

4 結(jié) 語

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

[1] 朱飛祥,張英俊,高宗江.基于數(shù)據(jù)挖掘的船舶行為研究[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的元胞自動機模型的船舶交通流特征參數(shù)分析[J].武漢理工大學(xué)學(xué)報:交通科學(xué)與工程版,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] 胡宏宇,王慶年,曲昭偉,等.運動目標(biāo)空間模式辨識與異常交通行為檢測[J].吉林大學(xué)學(xué)報,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].計算機工程與應(yīng)用,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

國家自然科學(xué)基金項目(61073134)；中央高?；究蒲袠I(yè)務(wù)費項目(3132013015)

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

U672.5

A

1674-0696(2015)05-130-05