基于改進(jìn)譜聚類算法的航路辨識(shí)

李爽　史國友　高邈　陳曉　吳京霖

摘要：

為解決船舶自動(dòng)識(shí)別系統(tǒng)（automatic?identification?system，?AIS）數(shù)據(jù)挖掘不夠充分，對(duì)航路辨識(shí)分析不夠全面等問題，提出一種基于改進(jìn)譜聚類算法的數(shù)據(jù)挖掘方式。利用Sliding?Window算法對(duì)船舶軌跡AIS數(shù)據(jù)進(jìn)行壓縮，減少數(shù)據(jù)冗余提高聚類效率。改進(jìn)親和距離函數(shù)，提出新的親和矩陣的標(biāo)準(zhǔn)，提高聚類的穩(wěn)定性，進(jìn)一步對(duì)數(shù)據(jù)去噪，減少噪聲敏感。通過優(yōu)化初始中心對(duì)k均值算法進(jìn)行改進(jìn)，優(yōu)化全局搜索能力，緩解初始值的選取對(duì)聚類效果的影響。以天津港AIS數(shù)據(jù)為樣本進(jìn)行算法驗(yàn)證。結(jié)果表明，該聚類算法能準(zhǔn)確提取和劃分某水域船舶主要航跡段，算法消耗系統(tǒng)資源少，計(jì)算速度快。改進(jìn)后的算法可為航路辨識(shí)、分道通航制定等提供理論支持。

關(guān)鍵詞：

航路辨識(shí);?譜聚類;?船舶自動(dòng)識(shí)別系統(tǒng)（AIS）;?大數(shù)據(jù);?k均值算法

中圖分類號(hào)：U675.7

文獻(xiàn)標(biāo)志碼：A

收稿日期：?2019-01-05

修回日期：?2019-04-12

基金項(xiàng)目：

國家自然科學(xué)基金（51709165）;遼寧省自然科學(xué)基金（20170540090）

作者簡介：

李爽（1995—），女，山東菏澤人，碩士研究生，研究方向?yàn)榻煌ㄟ\(yùn)輸工程，（E-mail）641094939@qq.com;

史國友（1968—），男，安徽桐城人，教授，博導(dǎo)，博士，研究方向?yàn)榇爸悄鼙芘觯‥-mail）sgydmu@dlmu.edu.cn

Route?identification?based?on?improved?spectral?clustering?algorithm

LI?Shuanga，b，?SHI?Guoyoua，b，?GAO?Miaoa，b，?CHEN?Xiaoa，b，?WU?Jinglina，b

（

a.?Navigation?College;?b.?Key?Laboratory?of?Navigation?Safety?Guarantee?of?Liaoning?Province，

Dalian?Maritime?University，?Dalian?116026，?Liaoning，?China）

Abstract：

In?order?to?solve?the?problem?that?automatic?identification?system?（AIS）?data?mining?is?not?enough?and?the?analysis?of?route?identification?is?not?comprehensive?enough，?a?data?mining?method?based?on?the?improved?spectral?clustering?algorithm?is?proposed.?The?Sliding?Window?algorithm?is?used?to?compress?AIS?data?of?ship?trajectory?so?as?to?reduce?data?redundancy?and?improve?the?clustering?efficiency.?The?affinity?distance?function?is?improved，?a?new?affinity?matrix?standard?is?proposed?to?improve?the?stability?of?clustering，?and?the?data?denoising?is?carried?out?to?reduce?the?noise?sensitivity.?The?k-means?algorithm?is?improved?by?optimizing?the?initial?center?so?as?to?optimize?the?global?search?ability?and?alleviate?the?impact?of?the?initial?value?selection?on?the?clustering?effect.?The?AIS?data?of?Tianjin?Port?is?taken?as?a?sample?to?verify?the?algorithm.?The?results?show?that，?the?clustering?algorithm?can?accurately?extract?and?divide?the?main?track?segments?of?ships?in?a?certain?water?area，?and?the?algorithm?consumes?less?system?resources?and?has?faster?calculation?speed.?The?improved?algorithm?can?provide?theoretical?support?for?route?identification，?traffic?separation，?and?so?on.

Key?words：

route?identification;?spectral?clustering;?automatic?identification?system?（AIS）;?big?data;?k-means?algorithm

0?引?言

云計(jì)算、無人化、智能化等新技術(shù)、新概念的發(fā)展，為工作人員處理海量船舶自動(dòng)識(shí)別系統(tǒng)（automatic?identification?system，AIS）數(shù)據(jù)中包含的各種信息提供了可能。《國際海上人命安全公約》（SOLAS公約）規(guī)定，所有300總噸及以上的國際航行船舶，非國際航行的500總噸及以上的貨船和不論大小的客船應(yīng)按要求配備AIS。隨著各國AIS基站網(wǎng)絡(luò)的建立和星載AIS群的出現(xiàn)，AIS數(shù)據(jù)的收集也得到了解決，AIS已成為實(shí)時(shí)的全球海上交通信息來源[1]。AIS數(shù)據(jù)為多元多維數(shù)據(jù)，包含各種船舶信息，AIS軌跡數(shù)據(jù)可描述船舶的空間位置和其他時(shí)空屬性。

聚類算法是數(shù)據(jù)挖掘中描述數(shù)據(jù)狀態(tài)的重要算法。傳統(tǒng)聚類方法主要有基于劃分的算法、基于密度的算法和基于層次的算法。基于劃分的算法，如k均值算法、k中心點(diǎn)算法和EM算法等，適用于數(shù)據(jù)量較小的凸集。張玉芳等[2]基于取樣的劃分思想，提出一種改進(jìn)的k均值算法，在一定程度上避免了聚類結(jié)果陷入局部解的現(xiàn)象，減少了原始k均值算法因采用誤差平方和準(zhǔn)則函數(shù)而將大的聚類簇分割開的情況;TAHIRI等[3]提出將一次計(jì)算距離矩陣用在每個(gè)迭代步驟中尋找新的中間體的新的k中心點(diǎn)算法;何彬彬等[4]提出基于EM和Delaunay三角網(wǎng)的船舶軌跡劃分，排除了空間聚類的隨機(jī)性?；诿芏鹊乃惴ㄖ饕蠨BSCAN和OPTICS等。DBSCAN算法[5]可以根據(jù)密度劃分聚類，構(gòu)建任意聚類簇，但是參數(shù)設(shè)置依賴大量實(shí)驗(yàn)且需自主定義。OPTICS算法是ANKERST等[6]為解決DBSCAN算法參數(shù)設(shè)置問題而提出的自動(dòng)交互式聚類算法，但該類算法占用內(nèi)存空間大，運(yùn)行效率低，無法解決非凸問題。EDLA等[7]提出選取網(wǎng)格的新方法，但是網(wǎng)格算法主要依賴網(wǎng)格劃分單元的質(zhì)量，對(duì)聚類效果影響較大?；趯哟蔚乃惴ㄓ蠦IRCH[8]、CURE[9]等，適用于任何聚類形狀和聚類層次，但是計(jì)算時(shí)間較長，算法終止條件很難確定。

譜聚類的思想來源于譜圖劃分理論，通過設(shè)計(jì)數(shù)據(jù)點(diǎn)集、建立無向加權(quán)圖、進(jìn)行圖論劃分構(gòu)造特征矩陣和特征向量，從而進(jìn)行低維矩陣的聚類，使同一類子圖之間劃分相關(guān)性最大，不同類子圖之間劃分相關(guān)性最小，是一種依靠相關(guān)性的親和聚類方式[10]。傳統(tǒng)的譜聚類算法主要用于VLSI設(shè)計(jì)、計(jì)算機(jī)視覺、圖像分割、文本挖掘和生物信息挖掘等領(lǐng)域[11]，目前已經(jīng)發(fā)展出SM算法、NJW算法等經(jīng)典的譜聚類算法，但是這些算法大多只能用于解決特例問題，不存在解決各種實(shí)際問題的通用算法。

關(guān)于譜聚類算法：ZOU等[12]將約束條件引入相似矩陣求解中，但是未考慮在低維子空間內(nèi)k均值算法受k值和初始值的影響;NG等[13]提出NJW算法;ZHOU等[14]提出基于約束的譜聚類算法，該算法考慮無監(jiān)督學(xué)習(xí)時(shí)聚類目標(biāo)產(chǎn)生的目標(biāo)函數(shù)不適用于實(shí)際問題的情況;曹妍妍等[15]提出了一種改進(jìn)Hausdroff距離和譜聚類的車輛軌跡模式學(xué)習(xí)方法，得到符合實(shí)際情況的聚類結(jié)果，但是未應(yīng)用在復(fù)雜路口的軌跡聚類。在航海領(lǐng)域，國內(nèi)外學(xué)者主要基于AIS數(shù)據(jù)進(jìn)行譜聚類分析：馬文耀等[16]改進(jìn)了譜聚類中的相似距離，采用單向距離進(jìn)行軌跡相似度度量，得到船舶運(yùn)動(dòng)模式，降低噪聲容忍度。然而，上述譜聚類算法未考慮低維空間聚類處理時(shí)k均值算法對(duì)初始值敏感、易陷入局部最優(yōu)等情況。

本文采用基于改進(jìn)譜聚類算法的數(shù)據(jù)挖掘方式，利用Sliding?Window算法對(duì)船舶軌跡AIS數(shù)據(jù)進(jìn)行壓縮，減少數(shù)據(jù)冗余，提高聚類效率;通過改進(jìn)親和距離函數(shù)，減少噪聲敏感;通過優(yōu)化初始中心對(duì)k均值算法進(jìn)行改進(jìn)，優(yōu)化全局搜索能力，緩解初始值的選取對(duì)聚類效果的影響，從而提高聚類技術(shù)在航路辨識(shí)方面的能力。

1?譜聚類算法模型

本文對(duì)NG等[13]提出的多路譜聚類下的NJW算法進(jìn)行改進(jìn)，主要步驟如下：

步驟1?構(gòu)造親和距離函數(shù)，建立親和矩陣，使數(shù)據(jù)由點(diǎn)集到圖論進(jìn)行轉(zhuǎn)化，建立無向加權(quán)圖。

步驟2?基于準(zhǔn)則或鄰近準(zhǔn)則稀疏化無向加權(quán)圖。

步驟3?建立度函數(shù)，構(gòu)造拉普拉斯矩陣，獲得規(guī)則的矩陣形式的數(shù)據(jù)關(guān)系。

步驟4?求解拉普拉斯矩陣前k個(gè)特征向量，其特征值λi從大到小排列，建立k階矩陣，k=arg?max|λi+1-λi|。

步驟5?對(duì)矩陣行向量做k均值算法聚類處理，得到劃分聚類結(jié)果。

通過對(duì)AIS數(shù)據(jù)進(jìn)行樣本間相似處理，得到樣本間的親和距離以進(jìn)行相似度衡量，從而得到相似度函數(shù)，即親和距離函數(shù)：

s（xi，xj）=exp-D2δxiδxj

（1）

式中：D為馬氏距離;

尺度參數(shù)δ表示相似性與距離之間的增減關(guān)系。在對(duì)尺度參數(shù)的選取中，應(yīng)充分考慮：當(dāng)尺度參數(shù)過小時(shí)，噪聲的影響過大;當(dāng)尺度參數(shù)過大時(shí)，親和矩陣變量振蕩較大，難以進(jìn)行有效選取。因此，對(duì)尺度參數(shù)的選取應(yīng)十分謹(jǐn)慎。本文采用信息熵確定尺度參數(shù)。

對(duì)聚類對(duì)象，構(gòu)造親和矩陣

[WTHX]S[WTBX]=（sij）n×n，

s[WTBX]ij=0，i=j

s（xi，xj），i≠j（2）

在聚類中，對(duì)k的選取引入本征間隙的概念。本征間隙是相鄰特征值的差值（|λt+1-λt|，t=1，2，…，k），第一個(gè)極大本征間隙的存在即表示聚類數(shù)目的存在。這是因?yàn)楦鶕?jù)矩陣攝動(dòng)理論，本征間隙與子空間的穩(wěn)定性成比例關(guān)系，間隙越大穩(wěn)定性越高。因此，計(jì)算聚類數(shù)目k值的問題轉(zhuǎn)化為找尋拉普拉斯矩陣最大本征間隙的問題。通過該方法，可以避免對(duì)k值的選擇，得到較為合適的k值。當(dāng)k值過小時(shí)，聚類簇較少，聚類劃分粗糙，不易識(shí)別人工難以識(shí)別的航路，不易區(qū)分密度可達(dá)情況;當(dāng)k值過大時(shí)，聚類劃分中噪聲比例增大，影響對(duì)可研究航路的辨識(shí)。

2?改進(jìn)的譜聚類算法

本文運(yùn)用上述譜聚類算法模型，通過改進(jìn)馬氏距離對(duì)船舶數(shù)據(jù)距離進(jìn)行采集，得出親和距離模型和親和矩陣表達(dá)方式，得出度矩陣和拉普拉斯矩陣，計(jì)算得出運(yùn)動(dòng)模式k的值，最后運(yùn)用改進(jìn)k均值聚類初始中心的算法得到最終聚類結(jié)果。改進(jìn)譜聚類航路辨識(shí)流程見圖1。

2.1?數(shù)據(jù)處理的改進(jìn)

為解決龐大的AIS數(shù)據(jù)難以有效集成、收集和存儲(chǔ)等問題，使用數(shù)據(jù)壓縮處理辦法，在合理的有效閾值范圍內(nèi)減少計(jì)算量，進(jìn)行矩陣降維處理。處理后得到的數(shù)據(jù)更為精簡，且有效數(shù)據(jù)得以保留。

Sliding?Window算法是經(jīng)典數(shù)據(jù)壓縮算法之一，其主要思想是采用逐步壓縮的形式，始終對(duì)3個(gè)點(diǎn)

進(jìn)行壓縮。設(shè)定P1為特征點(diǎn)，當(dāng)P2與P1、P3點(diǎn)連線的歐氏距離小于閾值時(shí)，舍棄中間點(diǎn)，加入P4，以此類推。高邈等[17]應(yīng)用改進(jìn)的Sliding?Window算法，考慮風(fēng)流壓差角，確定距離閾值、角度閾值，建立了有效的船舶軌跡數(shù)據(jù)價(jià)值評(píng)價(jià)模型，在對(duì)大數(shù)據(jù)進(jìn)行壓縮時(shí)可有效利用推薦閾值進(jìn)行選擇，保留船舶軌跡細(xì)節(jié)，達(dá)到AIS數(shù)據(jù)處理片段化的目的。

本文采用改進(jìn)的Sliding?Window算法對(duì)數(shù)據(jù)進(jìn)

行壓縮。該算法可降低壓縮風(fēng)險(xiǎn)、提高壓縮效率，在數(shù)據(jù)持續(xù)更新狀態(tài)下一直保持壓縮狀態(tài)。該算法充分考慮船舶航行中船舶姿態(tài)等因素對(duì)船舶軌跡的影響，失真率較低，且時(shí)間復(fù)雜度為O（n+1）（n為數(shù)據(jù)點(diǎn)數(shù)量），算法運(yùn)行有較大優(yōu)勢(shì)。

選取2015年12月天津港水域（38°09′30″～39°08′56″N，117°23′40″～120°03′06E）的AIS數(shù)據(jù)進(jìn)行壓縮，壓縮前為20?971?520個(gè)，壓縮后為1?048?576個(gè)。壓縮前后船舶軌跡對(duì)比見圖2。

a）壓縮前

b）壓縮后

2.2?親和距離的改進(jìn)

對(duì)于譜聚類算法來說，親和距離的計(jì)算是關(guān)鍵一步，是構(gòu)造親和矩陣的基礎(chǔ)。當(dāng)前基于船舶軌跡的聚類方法主要有歐氏距離、Hausdorff距離、結(jié)構(gòu)化距離等，其中：歐氏距離適用于計(jì)算距離下限，但是缺少量綱轉(zhuǎn)化，僅適用于矩陣密集、密度均勻的數(shù)據(jù)和同等船長的船舶中，大數(shù)據(jù)使用效果不佳;Hausdorff距離處理過程中雖然不添加軌跡噪聲，但對(duì)已存在的噪聲缺乏敏感性;結(jié)構(gòu)化距離處理過程中易忽視船舶軌跡自身黏性粘連，易陷入局部最優(yōu)，忽略軌跡聚類簇中集中聚類等慣性問題。馬氏距離

是歐幾里得空間內(nèi)非均勻分布的歸一化距離，不用考慮各特征參數(shù)的量綱，可以將整個(gè)空間內(nèi)的特征分布情況作為判斷依據(jù)，表征特征數(shù)據(jù)間的耦合關(guān)系，排除樣本間相關(guān)性的影響。因此，本文采用改進(jìn)的馬氏距離建立親和矩陣。

設(shè)

式中：上標(biāo)H表示對(duì)矩陣的共軛轉(zhuǎn)置。

改進(jìn)的馬氏距離可重新定義為

2.3?改進(jìn)k均值算法模型建立

傳統(tǒng)譜聚類算法主要

利用k均值算法進(jìn)行最后的低維子空間的聚類處理，雖然更便于得到結(jié)果，但是k均值算法對(duì)初始聚類劃分簇選取敏感，初始值不同可能導(dǎo)致聚類效果不同，容易陷入局部最優(yōu)，導(dǎo)致維度災(zāi)難。本文采取一種改進(jìn)初始聚類中心[21]的k均值算法來解決對(duì)初始值敏感和局部最優(yōu)問題。

初始聚類中心的選取對(duì)聚類的結(jié)果影響很大，若初始中心的選取存在問題，則會(huì)導(dǎo)致聚類結(jié)果不準(zhǔn)確。本文提出基于核心點(diǎn)的密度初始中心的選取方法，采用點(diǎn)集密度的思想，借鑒DBSCAN基于密度的算法思想，設(shè)定核心密度半徑（即鄰域半徑）r和核心極域集（即最小密度點(diǎn)數(shù)）f，選取核心點(diǎn)內(nèi)的中心點(diǎn)作為聚類初始中心的位置，補(bǔ)充其算法中局部最優(yōu)和對(duì)初始值敏感的問題。具體概念如下：

核心點(diǎn)密度ρ：以點(diǎn)集內(nèi)任意一點(diǎn)為中心，以r為半徑作球體模擬，球體內(nèi)包含的所有點(diǎn)集稱為核心點(diǎn)密度ρ，r為核心密度半徑。球體內(nèi)的點(diǎn)越多，核心點(diǎn)密度就越大，反之就越小。

核心極域集f：以半徑為r的高維球體組成核心域，J（p，q）為p與q兩個(gè)對(duì)象間的距離，這里采用歐氏距離表示。設(shè)f=intm/25，?int函數(shù)為取整函數(shù)，m為數(shù)據(jù)集的數(shù)量，此處取f=20。

核心密度半徑r：設(shè)定V為數(shù)據(jù)集的容積，n為維度數(shù)量，ε為閾值，Γ為伽馬函數(shù)，則

核心點(diǎn)：R區(qū)域內(nèi)的點(diǎn)集d，對(duì)于得到的r和f，當(dāng)d>f時(shí)，定義d為核心點(diǎn)集，反之，定義d為非核心點(diǎn)集。

綜上所述，改進(jìn)k均值聚類算法模型建立流程如下：

1）根據(jù)特征向量構(gòu)造特征矩陣

的每行看作待改進(jìn)的k均值空間內(nèi)的一點(diǎn)。

2）根據(jù)核心極閾集f計(jì)算核心密度半徑r。

3）根據(jù)r計(jì)算遍歷每個(gè)點(diǎn)，計(jì)算點(diǎn)集之間的距離，得出相似度矩陣

4）遍歷第一個(gè)點(diǎn)到所有點(diǎn)的距離，找到在半徑r范圍內(nèi)的點(diǎn)，根據(jù)|[WTHX]d[WTBX]|的大小，區(qū)分核心點(diǎn)與非核心點(diǎn)，得到核心點(diǎn)集。

5）遍歷所有核心點(diǎn)，取核心點(diǎn)中心點(diǎn)作為改進(jìn)后的k均值的聚類中心，當(dāng)聚類中心閾值小于設(shè)定值時(shí)聚類結(jié)束。

6）完成k均值最終聚類。

3?實(shí)驗(yàn)與驗(yàn)證

本文基于Python語言與Spyder的集成開發(fā)環(huán)境平臺(tái)，編寫基于AIS數(shù)據(jù)的常規(guī)航路特征提取程序并進(jìn)行實(shí)驗(yàn)。

相較于傳統(tǒng)聚類算法，譜聚類算法對(duì)初始輸入數(shù)據(jù)不敏感，具有識(shí)別非凸數(shù)據(jù)的能力，且理解簡單，時(shí)間復(fù)雜度較低。目前在航海領(lǐng)域使用較多的聚類算法是DBSCAN算法，但是該算法的聚類效果重度依賴輸入的參數(shù)，聚類結(jié)果波動(dòng)幅度較大，對(duì)初始數(shù)據(jù)比較敏感，未考慮軌跡特征的整體形狀，且內(nèi)存占用較大，運(yùn)行較慢;k均值算法是聚類算法中的一種簡單、快速的算法，在大型數(shù)據(jù)集處理中，可保持優(yōu)質(zhì)的數(shù)據(jù)伸縮效率，但是該算法易導(dǎo)致局部最優(yōu)，不適用于非凸集，對(duì)噪聲較為敏感，在譜聚類中一般用于已做高維處理的低維矩陣聚類的處理。本文將改進(jìn)譜聚類算法與DBSCAN算法對(duì)比，從聚類簇?cái)?shù)、時(shí)間和聚類精度上進(jìn)行分析，對(duì)比結(jié)果見圖3。

a）DBSCAN算法

b）改進(jìn)譜聚類算法

根據(jù)圖3，采用DBSCAN算法得到的聚類簇為456條，而采用本文提出的經(jīng)過Sliding?Window壓縮改進(jìn)后的譜聚類算法得到的聚類簇為312條。因?yàn)樗写暗暮叫信c陸地上車輛的行駛不同，船舶航行的水域沒有明確的航道，所以單純考慮密度可達(dá)。采用DBSCAN算法得到的可聚類簇?cái)?shù)多于本文算法，但是其中有很多無效類簇;本文算法可在改進(jìn)數(shù)據(jù)處理時(shí)舍棄大量無效數(shù)據(jù)，減少無關(guān)類簇對(duì)聚類結(jié)果的影響。在算法消耗時(shí)間方面，采用本文算法的計(jì)算時(shí)間為32?min，而采用DBSCAN算法的計(jì)算時(shí)間長達(dá)117?min。

在算法復(fù)雜度方面，譜聚類在構(gòu)建相似度時(shí)需要的時(shí)間復(fù)

雜度為O（n2），在計(jì)算特征值對(duì)應(yīng)特征向量時(shí)其時(shí)間復(fù)雜度為O（m3）+（O（nm）+O（nt））·O（p（m-k）），其中：p是算法每次執(zhí)行時(shí)迭代的次數(shù)，參數(shù)m的取值為k的幾倍大小。對(duì)特征矩陣運(yùn)行k均值算法，時(shí)間復(fù)雜度為O（lnk2），其中l(wèi)為k均值算法迭代次數(shù)。分析可得，構(gòu)建相似度環(huán)節(jié)是時(shí)間復(fù)雜度最高的環(huán)節(jié)，求解拉普拉斯矩陣的前k個(gè)特征向量也需要相當(dāng)長的時(shí)間和相當(dāng)多的內(nèi)存。本文通過使用Sliding?Window壓縮算法壓縮AIS數(shù)據(jù)，改善了譜聚類算法中相似矩陣處理環(huán)節(jié)資源占用、運(yùn)行困難的情況，可在數(shù)據(jù)規(guī)模不斷增長的情況下，保持聚類的質(zhì)量和速度;DBSCAN算法的時(shí)間復(fù)雜度為O（nlog?n）[22]。

在算法精度對(duì)比方面，以船舶通過分道通航區(qū)域A為例，采用DBSCAN算法只能提取到A、B兩種航路特征模式（見圖4），采用本文算法可提取到A1、A2、B1、B2四種航路特征模式（見圖5）。

由圖4可知DBSCAN算法的密度可達(dá)性，當(dāng)只有一個(gè)核心對(duì)象時(shí)DBSCAN算法可成功識(shí)別該類

簇，當(dāng)在其鄰域內(nèi)有多個(gè)核心對(duì)象時(shí)導(dǎo)出最大的密度相連集合，DBSCAN算法就僅識(shí)別一類簇，因此DBSCAN算法不可識(shí)別船舶在航行中存在交叉航路和疊加航路等情況。譜聚類算法[23]可克服DBSCAN算法的這一弊端，可發(fā)現(xiàn)船舶航行過程中產(chǎn)生的多組聚類簇，獲得更合理的航路辨識(shí)效果。

4?結(jié)?論

譜聚類可以克服其他聚類需要設(shè)置參數(shù)、消耗內(nèi)存大、運(yùn)行速率慢、聚類效果差、聚類劃分粗糙等弊端;通過改進(jìn)親和距離，優(yōu)化相似度，避免DBSCAN密度可達(dá)導(dǎo)致的初始點(diǎn)相同但整體不同仍被分為一類的情況;改進(jìn)k均值中初始值選取的準(zhǔn)確性，使聚類劃分更為合理。經(jīng)過改進(jìn)后的譜聚類算法，能夠發(fā)現(xiàn)人工無法發(fā)現(xiàn)的異同，計(jì)算結(jié)果較為合理。該算法可應(yīng)用在船舶習(xí)慣航路的識(shí)別，可以為航路辨識(shí)、航路規(guī)劃、分道通航制定和異常行為數(shù)據(jù)識(shí)別提供理論支持。目前，在AIS數(shù)據(jù)挖掘、航路特征提取方面還面臨很多挑戰(zhàn)，聚類參數(shù)的選取有待改進(jìn)，對(duì)聚類結(jié)果的評(píng)價(jià)仍沒有統(tǒng)一的標(biāo)準(zhǔn)，這是今后需要重點(diǎn)研究的問題。

參考文獻(xiàn)：

[1]

GAO?Miao，?SHI?Guoyou，?LI?Shuang.?Online?prediction?of?ship?behavior?with?automatic?identification?system?sensor?data?using?bidirectional?long?short-term?memory?recurrent?neural?network[J].?Sensors，?2018，?18（12）.?DOI：?10.3390/s18124211.

[2]張玉芳，?毛嘉莉，?熊忠陽.?一種改進(jìn)的k-means算法[J].?計(jì)算機(jī)應(yīng)用，?2003，?23（8）：?31-33.

[3]TAHIRI?N，?WILLEMS?M，?MAKARENKOV?V.?A?new?fast?method?for?inferring?multiple?consensus?trees?using?k-medoids[J].?BMC?Evolutionary?Biology，?2018，?18（1）：?48.?DOI：?10.1186/s12862-018-1163-8.

[4]何彬彬，?方濤，?郭達(dá)志.?基于不確定性的空間聚類[J].?計(jì)算機(jī)科學(xué)，?2004，?31（11）：?196-198.?DOI：?10.3969/j.issn.1002-137X.2004.11.053.

[5]TRAN?T?N，?DRAB?K，?DASZYKOWSKI?M.?Revised?DBSCAN?algorithm?to?cluster?data?with?dense?adjacent?clusters[J].Chemometrics?and?Intelligent?Laboratory?Systems，?2013，?120（15）：?92-96.?DOI：?10.1016/j.chemolab.2012.11.006.

[6]ANKERST?M，?BREUNING?M?M，?KRIEGEL?H，?et?al.?OPTICS：?ordering?points?to?identify?the?clustering?structure[C]//ACM?SIGMOD99?International?Conference?on?Management?of?Data.?ACM?SIGMOD?Record，1999，?28（2）：?49-60.

[7]EDLA?D?R，?JANA?P?K.?A?grid?clustering?algorithm?using?cluster?boundaries[C]//Information?&?Communication?Technologies.?IEEE，?2013：?254-259.?DOI：?10.1109/WICT.2012.6409084.

[8]TIAN?Z，?RAMAKRISHNAN?R，?LIVNY?M.?BIRCH：?a?new?data?clustering?algorithm?and?its?applications[J].?Data?Mining?&?Knowledge?Discov-ery，?1997，?1（2）：?141-182.?DOI：?10.1023/a：1009783824328.

[9]LATHIYA?P，?RANI?R.?Improved?CURE?clustering?for?big?data?using?Hadoop?and?Mapreduce[C]//International?Conference?on?Inventive?Computation?Technologies.?Coimbatore.?IEEE，?2017：?1-5.?DOI：?10.1109/INVENTIVE.2016.7830238.

[10]朱光輝，?黃圣彬，?袁春風(fēng).?SCoS：?基于Spark的并行譜聚類算法設(shè)計(jì)與實(shí)現(xiàn)[J].?計(jì)算機(jī)學(xué)報(bào)，?2018，?41（4）：?868-885.?DOI：?10.11897/SP.J.1016.2018.00868.

[11]王貝貝，?楊明，?燕慧超.?基于改進(jìn)譜聚類算法在圖像分割中的應(yīng)用[J].?河北工業(yè)科技，?2018，?35（1）：?55-60.?DOI：?10.7535/hbgykj.2018yx01010.

[12]ZOU?Haishuang，?ZHOU?Weida，?ZHANG?Li，?et?al.?A?new?constrained?spectral?clustering?for?SAR?image?segmentation[C]//Asian-Pacific?Conference?on?Synthetic?Aperture?Radar.?IEEE，?2010：?680-683.?DOI：?10.1109/APSAR.2009.5374114.

[13]NG?A?Y，?JORDAN?M?I，?WEISS?Y.?On?spectral?clustering：?analysis?and?an?algorithm[J].?Advances?in?Neural?Information?Processing?Systems，?2002，?2（14）：?849-856.

[14]ZHOU?Zhiping，?JIA?Xuan，?ZHAO?Xiaoxiao.?A?new?constraint?spectral?clustering?algorithm[C]//Control?&?Decision?Conference.?IEEE，?2017：?6664-6668.?DOI：?10.1109/CCDC.2017.7978376.

[15]曹妍妍，?崔志明，?吳健，?等.?一種改進(jìn)Hausdorff距離和譜聚類的車輛軌跡模式學(xué)習(xí)方法[J].?計(jì)算機(jī)應(yīng)用與軟件，?2012，?29（5）：?38-40.?DOI：?10.3969/j.issn.1000-386X.2012.05.011.

[16]馬文耀，?吳兆麟，?楊家軒，?等.?基于單向距離的譜聚類船舶運(yùn)動(dòng)模式辨識(shí)[J].?重慶交通大學(xué)學(xué)報(bào)（自然科學(xué)版），?2015，?34（5）：?130-134.?DOI：?10.3969/j.issn.1674-0696.2015.05.26.

[17]高邈，?史國友，?李偉峰.?改進(jìn)的Sliding?Window在線船舶AIS軌跡數(shù)據(jù)壓縮算法[J].?交通運(yùn)輸工程學(xué)報(bào)，?2018，?18（3）：?218-227.

[18]XIANG?Shiming，?NIE?Feiping，?ZHANG?Changshui.?Learning?a?Mahalanobis?distance?metric?for?data?clustering?and?classification[J].?Pattern?Recognition，?2008，?41（12）：?3600-3612.?DOI：?10.1016/j.patcog.2008.05.018.

[19]KATSIKIS?V?N，?PAPPAS?D，?PETRALIAS?A.?An?improved?method?for?the?computation?of?the?Moore-Penrose?inverse?matrix[J].?Applied?Mathematics?&?Computation，?2011，?217（23）：?9828-9834.?DOI：?10.1016/j.amc.2011.04.080.

[20]張小波.?Moore-Penrose逆的表示及擾動(dòng)分析[D].?上海：?上海師范大學(xué)，?2016.

[21]楊艷，?許道云.?優(yōu)化加權(quán)核k-means聚類初始中心點(diǎn)的SLIC算法[J].?計(jì)算機(jī)科學(xué)與探索，?2018，?12（3）：?494-501.?DOI：?10.3778/j.issn.1673-9418.1708034.

[22]YUAN?Guan，?SUN?Penghui，?ZHAO?Jie，?et?al.?A?review?of?moving?object?trajectory?clustering?algorithms[J].?Artificial?Intelligence?Review，?2017，?47（1）：?123-144.?DOI：?10.1007/s10462-016-9477-7.

[23]牟軍敏，?陳鵬飛，?賀益雄.?船舶AIS軌跡快速自適應(yīng)譜聚類算法[J].?哈爾濱工程大學(xué)學(xué)報(bào)，?2018，?39（3）：?428-432.?DOI：?10.11990/jheu.201609033.

（編輯?賈裙平）