一種基于改進(jìn)的DBSCAN的面向海量船舶位置數(shù)據(jù)碼頭挖掘算法＊

丁兆穎，姚 迪，吳 琳，畢經(jīng)平，趙瑞蓮

（1.北京化工大學(xué)信息學(xué)院，北京100029；2.中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京100190）

1 引言

船舶目標(biāo)跟蹤方法有很多種，比如國(guó)際海事衛(wèi)星C系統(tǒng)、北斗衛(wèi)星、Argos衛(wèi)星、AIS（Automatic Identification System）等。不同方法各有優(yōu)劣，比如國(guó)際海事衛(wèi)星C 系統(tǒng)是全天候、全球范圍、穩(wěn)定可靠的，但是終端價(jià)格和通信費(fèi)稍高；北斗衛(wèi)星技術(shù)速度快，但目前只是區(qū)域性，且終端尚不夠穩(wěn)定；AIS方法成本低廉，無(wú)需通信費(fèi)，可以分布式建設(shè)。隨著《SOLAS公約》第五章新規(guī)則對(duì)船舶自動(dòng)識(shí)別系統(tǒng)（AIS）［1］強(qiáng)制性裝備的要求，所有300總噸及以上從事國(guó)際航行船舶、不從事國(guó)際航行的500總噸及以上的貨船和不論大小的客船，應(yīng)按要求配備自動(dòng)識(shí)別系統(tǒng)AIS。AIS在全球范圍內(nèi)廣泛使用。各類岸基AIS設(shè)備以及衛(wèi)星AIS設(shè)備每天接收到的船只動(dòng)態(tài)、靜態(tài)AIS實(shí)時(shí)報(bào)文數(shù)量數(shù)以億計(jì)，為船舶軌跡研究提供了豐富的數(shù)據(jù)源。這些豐富的海量船舶數(shù)據(jù)中，隱藏著大量對(duì)水運(yùn)事業(yè)管理、規(guī)劃、安全等具有非常重大的意義的內(nèi)容。

在水運(yùn)行業(yè)中，港口作為運(yùn)輸樞紐，是各類交通工具轉(zhuǎn)換中心。碼頭、錨地的作用是供船舶進(jìn)出、停泊，是港口水域的重要組成部分。各類碼頭對(duì)城市經(jīng)濟(jì)的發(fā)展、區(qū)域經(jīng)濟(jì)的發(fā)展都起著非常重要的作用。近年來(lái)新建碼頭層出不窮，而中國(guó)海圖的更新間隔按照區(qū)域的熱度更新間隔長(zhǎng)達(dá)3個(gè)月、6個(gè)月、12個(gè)月不等的時(shí)間，存在嚴(yán)重的滯后性，并且海圖中缺乏碼頭的空間信息。本文提出的碼頭挖掘的研究工作可以有效、及時(shí)地更新碼頭空間數(shù)據(jù)。碼頭的空間信息可以進(jìn)一步應(yīng)用到船舶進(jìn)出港通知，不僅如此，碼頭的挖掘成果，也可以作為船舶數(shù)據(jù)其他研究領(lǐng)域的數(shù)據(jù)支撐，比如碼頭間航道挖掘、船舶行為異常監(jiān)測(cè)等。

DBSCAN（Density－Based Spatial Clustering of Applications with Noise）算法是一種具有噪聲的基于密度的聚類分析算法，它可以將數(shù)據(jù)集分成若干組，并有效地處理噪聲點(diǎn)，過(guò)濾低密度區(qū)域。其基本思想是在含有噪聲的數(shù)據(jù)空間中，通過(guò)不斷擴(kuò)展有足夠高密度的區(qū)域來(lái)進(jìn)行聚類，發(fā)現(xiàn)任意形狀的高密度多簇點(diǎn)集。但是，由于應(yīng)用DBSCAN算法時(shí)有eps和MinPts兩個(gè)參數(shù)需要人工提前確定，且算法對(duì)這兩個(gè)參數(shù)非常敏感，這一缺點(diǎn)普遍存在于實(shí)際的計(jì)算當(dāng)中。

本文提出一種針對(duì)海量數(shù)據(jù)優(yōu)化參數(shù)的DBSCAN 算法，可以根據(jù)不同的實(shí)際應(yīng)用場(chǎng)景、數(shù)據(jù)集特征，選取合適的算法參數(shù)。將其應(yīng)用在碼頭挖掘場(chǎng)景中，根據(jù)實(shí)際的停泊點(diǎn)數(shù)據(jù)規(guī)模和分布特征，自動(dòng)優(yōu)化停泊點(diǎn)聚類參數(shù)，聚類出停泊點(diǎn)密集的停泊區(qū)，去除停泊點(diǎn)稀疏區(qū)域的停泊點(diǎn)。再通過(guò)融合岸基結(jié)構(gòu)物等空間數(shù)據(jù)，對(duì)停泊區(qū)域中的錨區(qū)和臨時(shí)停泊區(qū)域等進(jìn)行排除，獲取碼頭的空間信息，解決了碼頭空間數(shù)據(jù)實(shí)時(shí)更新問題。

本文第2節(jié)介紹了位置數(shù)據(jù)和DBSCAN 算法的相關(guān)研究工作；第3 節(jié)介紹自動(dòng)優(yōu)化DBSCAN算法參數(shù)的方法，及將改進(jìn)的DBSCAN 算法應(yīng)用于碼頭挖掘思路；第4節(jié)實(shí)驗(yàn)及結(jié)果分析；第5節(jié)總結(jié)全文并展望下一步研究工作。

2 相關(guān)工作

聚類在數(shù)據(jù)挖掘領(lǐng)域的研究比較多。聚類算法主要分為四種策略：（1）劃分聚類方法，如kmeans［2］，需指定聚類個(gè)數(shù)，不適用于發(fā)掘未知信息；（2）分層聚類方法，如BIRCH［3］，計(jì)算量大，算法復(fù)雜度高，耗時(shí)較長(zhǎng)，不適合應(yīng)用于海量數(shù)據(jù)；（3）基于密度的聚類方法，如DBSCAN［4］和OPTICS［5］，復(fù)雜度低，基于數(shù)據(jù)密度分布特征，對(duì)數(shù)據(jù)集聚類，比較適合本文所提的碼頭挖掘研究；（4）基于柵格的聚類方法，如STING［6］，處理時(shí)間與每維空間所劃分的單元數(shù)相關(guān)，一定程度上降低了聚類的質(zhì)量和準(zhǔn)確性。

目前，DBSCAN 聚類算法應(yīng)用在實(shí)際場(chǎng)景中的研究國(guó)內(nèi)外已有很多，比如交通事故多發(fā)區(qū)域的挖掘等。通過(guò)不斷地搜索臨近點(diǎn)來(lái)使核心對(duì)象周圍的密度逐漸增加，尋找到一個(gè)區(qū)域內(nèi)所查找點(diǎn)或?qū)ο竺芏却蟮牡胤健Ｋ惴ㄖ兴芯康狞c(diǎn)可以描述為交通事故多發(fā)的地點(diǎn)。由于應(yīng)用DBSCAN 算法時(shí)有eps和MinPts兩個(gè)參數(shù)需要人工提前確定，且算法對(duì)參數(shù)敏感，研究者在原始算法的基礎(chǔ)上提出了很多改進(jìn)，來(lái)提高算法的效率。Han J等［7］通過(guò)計(jì)算數(shù)據(jù)集的信息熵，給出一個(gè)最優(yōu)參數(shù)的范圍。Karami A 等［8］提出了一種高效的混合聚類方法，命名為bde－dbscan，結(jié)合了二進(jìn)制差分進(jìn)化算法和DBSCAN 算法。這些方法都能很好地解決DBSCAN 算法的參數(shù)敏感問題，但是復(fù)雜度較高，且需要人工觀察，不適用在大數(shù)據(jù)量級(jí)的數(shù)據(jù)處理中。

目前國(guó)內(nèi)外很少有對(duì)船舶停泊點(diǎn)的分析研究，特別是基于停泊點(diǎn)的碼頭挖掘研究。Le Guillarme N 等［9］提出了一個(gè)船舶位置數(shù)據(jù)挖掘框架，從數(shù)據(jù)中提取航道和停泊點(diǎn)，對(duì)停泊點(diǎn)進(jìn)行聚類，聚類出密集區(qū)域定義為港口、捕魚點(diǎn)等船只的目的地，沒有進(jìn)一步地劃分，也沒有解決聚類算法對(duì)參數(shù)敏感的問題。

3 碼頭挖掘算法

3.1 碼頭挖掘算法思路

船舶位置數(shù)據(jù)，即船舶某個(gè)時(shí)間點(diǎn)所在位置的經(jīng)緯度。停泊點(diǎn)數(shù)據(jù)即是船舶在某個(gè)點(diǎn)附近停留時(shí)間超過(guò)一定閾值的點(diǎn)。面向海量船舶位置數(shù)據(jù)的碼頭挖掘算法主要分為兩步。第一步是從船舶位置原始數(shù)據(jù)中提取出停泊點(diǎn)數(shù)據(jù)。一般船舶停泊的地方主要集中在碼頭、錨區(qū)或臨時(shí)停泊區(qū)，在這些區(qū)域船舶停泊點(diǎn)密度較大。除此之外還有很多分散停泊在這些區(qū)域外的船只，對(duì)于停泊區(qū)挖掘來(lái)說(shuō)，這些數(shù)據(jù)屬于噪聲數(shù)據(jù)。第二步針對(duì)使用數(shù)據(jù)集，確定適應(yīng)停泊點(diǎn)數(shù)據(jù)聚類的參數(shù)。DBSCAN 算法是基于密度聚類的聚類算法，可以有效去掉停泊點(diǎn)噪聲數(shù)據(jù)，將船舶位置數(shù)據(jù)分成多組任意形狀的停泊區(qū)。然而，針對(duì)不同的數(shù)據(jù)，聚類算法的參數(shù)也不盡相同。本文提出一種優(yōu)化DBSCAN 算法參數(shù)的方法，自動(dòng)對(duì)比聚類后類中心密度變化，自動(dòng)選取合適的參數(shù)，以提高停泊區(qū)挖掘的準(zhǔn)確度。確定聚類參數(shù)后，對(duì)停泊點(diǎn)數(shù)據(jù)進(jìn)行聚類。單純的聚類結(jié)果還不能確定碼頭，需要通過(guò)融合外部數(shù)據(jù)，如岸基結(jié)構(gòu)物等，確定碼頭的位置和區(qū)域。碼頭挖掘流程如圖1所示。

Figure 1 Flow chart of dock mining圖1 碼頭挖掘流程圖

本節(jié)的第2部分介紹海事船舶數(shù)據(jù)的預(yù)處理工作，從船舶自動(dòng)識(shí)別系統(tǒng)采集的原始海事船舶數(shù)據(jù)，提取出本文需要的船舶停泊點(diǎn)數(shù)據(jù)。第3部分介紹DBSCAN 算法思想及優(yōu)化參數(shù)的方法。第4部分介紹聚類方法結(jié)果和融合外部數(shù)據(jù)的方法。

3.2 停泊點(diǎn)提取

基于帶有時(shí)間戳的船舶位置數(shù)據(jù)分析船舶海洋行為，需要對(duì)數(shù)據(jù)進(jìn)行劃分。其中基于分層數(shù)據(jù)融合的數(shù)據(jù)劃分方法是最適用于處理海量數(shù)據(jù)的方法，且該算法的計(jì)算復(fù)雜度是O（n）。劃分方法將數(shù)據(jù)劃分為兩層，AIS原始數(shù)據(jù)經(jīng)過(guò)L1層處理得到子航段。子航段數(shù)據(jù)經(jīng)過(guò)L2 層融合得到航段及停泊點(diǎn)［8］。原始數(shù)據(jù)處理流程如圖2所示。

L1層處理：分析單艘船時(shí)間序列上的數(shù)據(jù)。時(shí)間連續(xù)的AIS數(shù)據(jù)首尾相連，構(gòu)成一個(gè)向量，根據(jù)如下兩個(gè)條件判斷是否劃分子航段：

其中，O為起始點(diǎn)，Pi表示AIS原始數(shù)據(jù)中第i個(gè)點(diǎn)，T1、T2為兩個(gè)閾值，分別表示起始向量與第i個(gè)向量夾角閾值，第i個(gè)向量與第i－1 個(gè)向量夾角閾值。超過(guò)閾值時(shí)開始下一個(gè)子航段劃分。

L2層處理：基于規(guī)則挖掘出單艘船的子航段。根據(jù)船舶行為特點(diǎn)確定停泊點(diǎn)，停泊點(diǎn)的定義是船舶子航段端點(diǎn)處停留時(shí)間超過(guò)一定閾值的點(diǎn)。

Figure 2 Flow chart of raw data processing圖2 原始數(shù)據(jù)處理流程圖

3.3 停泊點(diǎn)聚類算法

3.3.1 DBSCAN 算法

定義1eps鄰域：給定半徑eps（ε），以特定點(diǎn)為圓心，以eps為半徑的圓內(nèi)的點(diǎn)集稱為該停泊點(diǎn)的鄰域。

定義2 核心點(diǎn)：鄰域內(nèi)的停泊點(diǎn)數(shù)大于或等于MinPts，則該點(diǎn)成為核心停泊點(diǎn)。

定義3 直接密度可達(dá)：給定停泊點(diǎn)集合D，如果點(diǎn)p在q的鄰域內(nèi)，且q是核心停泊點(diǎn)，則稱點(diǎn)p到q直接密度可達(dá)。

定義4 密度可達(dá)：給定停泊點(diǎn)集合D，如果存在停泊點(diǎn)子集p1，p2，p3，…，pn，pi（1≤i≤n）∈D，pi＋1是從pi關(guān)于ε和MinPts直接密度可達(dá)，則停泊點(diǎn)p是從q關(guān)于ε和MinPts密度可達(dá)。

定義5 密度相連：如果存在停泊點(diǎn)k∈D，使點(diǎn)p和q是關(guān)于ε和MinPts密度可達(dá)，那么p到q是關(guān)于ε和MinPts密度相連。

算法1 基于DBSCAN 算法的碼頭挖掘算法

輸入：一組停泊點(diǎn)（經(jīng)緯度）集合D＝｛p1，p2，p3，…，pn｝（n是停泊點(diǎn)集合的數(shù)量）、鄰域半徑ε和最小鄰域點(diǎn)數(shù)MinPts；

輸出：labels整數(shù)集合，標(biāo)記每個(gè)點(diǎn)的類名。

functionDBSCAN（D，ε，MinPts）

clusterId＝0；

標(biāo)記所有點(diǎn)為未分類點(diǎn)；

其中找出核心點(diǎn)的最大密度相連集合函數(shù)如下：

3.3.2 DBSCAN 參數(shù)優(yōu)化

DBSCAN 算法依賴聚類最小點(diǎn)數(shù)MinPts，聚類內(nèi)部最長(zhǎng)距離eps兩個(gè)參數(shù)。因此，對(duì)不同分布的數(shù)據(jù)需要調(diào)整不同的MinPts和eps，以達(dá)到好的聚類效果。本文采用聚類個(gè)數(shù)和類中心密度（Cluster Center Density）作為聚類效果的評(píng)價(jià)指標(biāo)，分別確定MinPts及eps，不斷迭代直到MinPts和eps穩(wěn)定。

由于DBSCAN 是基于密度的聚類算法，因此該算法在一定程度上對(duì)參數(shù)不敏感。即由一個(gè)確定的MinPts可能有多個(gè)連續(xù)的eps與之對(duì)應(yīng)，即一個(gè)eps的區(qū)間對(duì)應(yīng)，因此尋找最優(yōu)參數(shù)即尋找最優(yōu)的MinPts區(qū)間與eps區(qū)間。區(qū)別于傳統(tǒng)的優(yōu)化問題，本問題找不到一個(gè)可以形式化表示的損失函數(shù)。參數(shù)優(yōu)化算法如下：

算法2 DBSCAN 參數(shù)確定算法

輸 入：數(shù) 據(jù) 集，MinPts初 始 值p0，eps初 始 值e0，MinPts變化率；

輸出：最優(yōu)參數(shù)區(qū)間p，e。

當(dāng)eps值確定時(shí)，搜索不同MinPts值，計(jì)算不同MinPts產(chǎn)生的聚類個(gè)數(shù)。首先確定MinPts搜索間隔，記錄MinPts對(duì)應(yīng)的聚類個(gè)數(shù)。聚類個(gè)數(shù)的變化一定是遞減的過(guò)程，選取聚類個(gè)數(shù)達(dá)到最大穩(wěn)定時(shí)對(duì)應(yīng)的MinPts值作為最佳MinPts值。實(shí)現(xiàn)方法為計(jì)算不同MinPts值對(duì)應(yīng)的聚類個(gè)數(shù)計(jì)算橫坐標(biāo)為MinPts值，縱坐標(biāo)為聚類個(gè)數(shù)確定的點(diǎn)中，每一個(gè)點(diǎn)與下一個(gè)點(diǎn)相連直線的斜率。

設(shè)第n次搜索得到的點(diǎn)為Pn（MinPtsn，Cn），其中MinPtsn為聚類最小點(diǎn)數(shù)，Cn為聚類個(gè)數(shù)。對(duì)每一步記錄kPn－1Pn。搜索的終止條件為：

其中，

Δeps為搜索步長(zhǎng)，是一個(gè)常數(shù)；m為穩(wěn)定條件，即有m步斜率接近于零則判定為穩(wěn)定，并記錄MinPts的值。

3.4 融合岸基結(jié)構(gòu)物篩選碼頭

根據(jù)上述算法，可以將停泊點(diǎn)數(shù)據(jù)聚成一個(gè)個(gè)停泊區(qū)域，對(duì)不同的停泊區(qū)域肯定需要參照其地理位置信息對(duì)其分類。本文通過(guò)融合岸基結(jié)構(gòu)物數(shù)據(jù)，根據(jù)碼頭的形狀位置特征從停泊區(qū)域中篩選出碼頭，并將篩選出的碼頭與已有碼頭分布的區(qū)域比對(duì)，驗(yàn)證算法挖掘出碼頭的準(zhǔn)確性。

海岸線延伸出大陸架的部分稱為陸地的岸基結(jié)構(gòu)物，碼頭一定是貼近岸基結(jié)構(gòu)物建造的。本文用到的岸基結(jié)構(gòu)物由google KML文件標(biāo)準(zhǔn)定義，定義結(jié)構(gòu)如圖3所示。

Figure 3 Raw data of the shore structures圖3 岸基結(jié)構(gòu)物原始數(shù)據(jù)

可以看出，岸基結(jié)構(gòu)物是通過(guò)一條條線定義的，通過(guò)計(jì)算聚類區(qū)域到線的距離即可判斷停泊區(qū)域是否是一個(gè)碼頭。

設(shè)類核心點(diǎn)為P，首先提取以P為中心、以r為半徑區(qū)域內(nèi)的岸基結(jié)構(gòu)物線段數(shù)據(jù)，設(shè)定碼頭距岸基閾值rt，如果r＜rt即判定該區(qū)域?yàn)榇a頭區(qū)域，否則不是碼頭區(qū)域。

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

4.1 實(shí)驗(yàn)場(chǎng)景

本文實(shí)驗(yàn)基于2012年4月至2014年4月的滾裝船位置數(shù)據(jù)，實(shí)現(xiàn)了改進(jìn)的DBSCAN 算法和挖掘碼頭算法，挖掘出國(guó)內(nèi)滾裝船碼頭，通過(guò)對(duì)比人工識(shí)別碼頭判斷算法準(zhǔn)確率。同樣用本文提出的算法，挖掘出國(guó)際滾裝船碼頭。實(shí)驗(yàn)表明本文方法具有很高的準(zhǔn)確性和很強(qiáng)的可擴(kuò)展性。本實(shí)驗(yàn)使用的語(yǔ)言是Python 2.7版本，在普通的電腦上執(zhí)行程序，具體實(shí)驗(yàn)環(huán)境參數(shù)和實(shí)驗(yàn)數(shù)據(jù)如表1和表2所示。

Table 1 Experimental environment表1 實(shí)驗(yàn)環(huán)境

Table 2 Experimental dataset表2 實(shí)驗(yàn)數(shù)據(jù)

表2是從AIS采集到大量船舶靜態(tài)和動(dòng)態(tài)數(shù)據(jù)，包括船位、航向、航速、類型等中提取出的滾裝船位置數(shù)據(jù)。其中靜態(tài)數(shù)據(jù)表示船舶的條數(shù)，國(guó)內(nèi)54艘滾裝船，國(guó)際有279艘。

4.2 DBSCAN 算法參數(shù)選取

碼頭挖掘算法第二步，首先要針對(duì)使用數(shù)據(jù)集，確定適應(yīng)停泊點(diǎn)數(shù)據(jù)聚類的參數(shù)。按照本文參數(shù)優(yōu)化方法，首先確定MinPts值。給出DBSCAN算法兩個(gè)參數(shù)最小點(diǎn)數(shù)MinPts和聚類內(nèi)部最長(zhǎng)距離eps的初始值10和0.000 3，ΔMinPts為1，m取值為5，即有5步斜率接近于零則判定為穩(wěn)定，并記錄MinPts的值。分別計(jì)算特定eps值時(shí)，計(jì)算不同MinPts產(chǎn)生的聚類個(gè)數(shù)。如圖4所示，橫坐標(biāo)是MinPts值，縱坐標(biāo)代表聚類的個(gè)數(shù)。

本文算法的執(zhí)行結(jié)果中，當(dāng)eps＝0.000 3時(shí)，MinPts值取32，當(dāng)eps＝0.000 6時(shí)，MinPts值取31，當(dāng)eps＝0.000 8時(shí)，MinPts值取34，當(dāng)eps＝0.001 0 時(shí)，MinPts值 取32。確 定MinPts值 為32。

確定MinPts值后，需要根據(jù)得到的MinPts值確定eps。在聚類核心點(diǎn)中隨機(jī)選取25個(gè)點(diǎn)。計(jì)算并記錄不同eps值時(shí)，每個(gè)點(diǎn)所在類中的類中心密度即最大密度相連集合內(nèi)點(diǎn)總數(shù)。如圖5所示。

Figure 4 The number of clusters based on different eps changing with MinPts value圖4 不同eps聚類個(gè)數(shù)隨MinPts值變化曲線圖

當(dāng)eps取0.000 68時(shí)，所有點(diǎn)類中心密度達(dá)到穩(wěn)定，即確定eps值為0.000 68，從而最終確定eps值為0.000 68，MinPts值為32。如圖5所示。

Figure 5 The class center density of core points varying with the eps value圖5 核心點(diǎn)的類中心密度隨eps值變化曲線圖

4.3 國(guó)內(nèi)滾裝船碼頭挖掘?qū)嶒?yàn)

根據(jù)上一步實(shí)驗(yàn)，挖掘國(guó)內(nèi)滾裝船碼頭算法的兩個(gè)參數(shù)eps和MinPts的值分別確定為0.000 68和32，挖掘國(guó)內(nèi)滾裝船碼頭。 本文利用googleMap展現(xiàn)國(guó)內(nèi)滾裝船碼頭的挖掘結(jié)果。挖掘出的碼頭位置用圓點(diǎn)表示，共挖掘出國(guó)內(nèi)滾裝船停泊區(qū)40個(gè)，篩選出碼頭29個(gè)。圖6為使用本文提出的算法挖掘出的碼頭與真實(shí)碼頭的對(duì)比圖，三角標(biāo)志是人工標(biāo)記的真實(shí)碼頭。

Figure 6 Result of dock mining for Chinese Ro Ro vessels圖6 國(guó)內(nèi)滾裝船碼頭挖掘結(jié)果

圖7是放大的上海外高橋碼頭區(qū)域，深色部分是岸基結(jié)構(gòu)物，可以看到融合岸基結(jié)構(gòu)物后可以清晰地區(qū)分出碼頭與非碼頭。從圖7可以看出，碼頭都在岸基結(jié)構(gòu)物附近，非碼頭區(qū)域離岸基較遠(yuǎn)。圖中黑色圓點(diǎn)是已公布的滾裝船碼頭位置。人工識(shí)別標(biāo)記的滾裝船碼頭有27個(gè)，本文算法挖掘出的碼頭有29個(gè)，正確率達(dá)93%。以此可見本文提出的算法能有效、準(zhǔn)確地挖掘出碼頭的位置。此處挖掘出的非碼頭區(qū)域?yàn)樯虾４a頭附近的錨區(qū)。其作用是供船舶停靠等待裝卸貨物。此類停泊區(qū)域在本文中不做深入闡述。

Figure 7 Shanghai Waigaoqiao dock area combined with shore structures圖7 上海外高橋碼頭區(qū)域結(jié)合岸基結(jié)構(gòu)物

4.4 國(guó)際滾裝船碼頭挖掘?qū)嶒?yàn)

本文利用國(guó)際滾裝船位置數(shù)據(jù)進(jìn)行測(cè)試，與國(guó)內(nèi)滾裝船數(shù)據(jù)同時(shí)間段的國(guó)際船舶位置數(shù)據(jù)有51 985條。利用本文挖掘碼頭算法，共挖掘出244個(gè)停泊區(qū)。如圖8所示。

Figure 8 Dock mining result for international Ro Ro vessels圖8 國(guó)際滾裝船碼頭挖掘結(jié)果

對(duì)比地形結(jié)構(gòu)發(fā)現(xiàn)，通過(guò)本文方法挖掘出的滾裝船碼頭大部分與地形相符，表明本文提出的算法對(duì)不同的數(shù)據(jù)集有較好的可擴(kuò)展性。

5 結(jié)束語(yǔ)

本文提出的優(yōu)化參數(shù)的DBSCAN 算法，根據(jù)待聚類數(shù)據(jù)特征，自動(dòng)優(yōu)化確定DBSCAN 算法的兩個(gè)參數(shù)，有效地解決了DBSCAN 算法對(duì)參數(shù)敏感問題。本文又提出一種基于船舶位置數(shù)據(jù)挖掘碼頭的算法，第一步先挖掘出停泊區(qū)域，再一步，融合岸基結(jié)構(gòu)物數(shù)據(jù)，篩選出碼頭區(qū)域。本文選取2012年4月至2014年4 月國(guó)內(nèi)滾裝船位置數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，本文算法能夠針對(duì)特定數(shù)據(jù)集的分布特征及規(guī)模，自動(dòng)確定DBSCAN 算法參數(shù)，并聚類出停泊區(qū)。再融合岸基結(jié)構(gòu)物數(shù)據(jù)篩選出碼頭區(qū)域，對(duì)比本文挖掘出的碼頭位置和人工標(biāo)注的碼頭位置數(shù)據(jù)，本文算法正確率達(dá)到93%。下一步工作，在完善碼頭挖掘工作的同時(shí)，分析非碼頭停泊區(qū)域的特點(diǎn)，融合多樣化的數(shù)據(jù)，挖掘出更多有用的知識(shí)。

［1］ Wang Yong.AIS technology application in the navigation practice analysis［J］.Science Technology and Enterprise，2013（22）：158.（in Chinese）

［2］ Loyd S.Least squares quantization in PCM［J］.IEEE Transactions on Information Theory，1982，28（2）：129－137.

［3］ Zhang T，Ramakrishnan R，Livny M.BIRCH：An efficient data clustering method for very large databases［J］.ACM SIGMOD Record，1996，25（2）：103－114.

［4］ Dai B R，Lin I.Efficient map/reduce－based DBSCAN algorithm with optimized data partition［C］∥Proc of 2012IEEE 5th International Conference on Cloud Computing（CLOUD），2012：59－66.

［5］ Shi X，Chen Y，Tan Z，et al.Numerical simulation of adaptive optics correction system［C］∥Proc of 2011IEEE 3rd International Conference on Communication Software and Networks（ICCSN），2011：293－296.

［6］ Wang W，Yang J，Muntz R R.STING：A statistical information grid approach to spatial data mining［C］∥Proc of the 23rd International Conference on Very Large Data Bases，1997：186－195.

［7］ Lee J G，Han J，Whang K Y.Trajectory Clustering：A partition－and－group framework［C］∥Proc of SIGMOD，2007：593－604.

［8］ Karami A，Johansson R.Choosing DBSCAN parameters automatically using differential evolution［J］.International Journal of Computer Applications，2014，91（7）：1－11.

［9］ Le Guillarme N，Lerouvreur X.Unsupervised extraction of knowledge from S－AIS data for maritime situational awareness［C］∥International Conference on Information Fusion，2013：2025－2032.

附中文參考文獻(xiàn)：

［1］ 王勇.AIS技術(shù)在航海實(shí)踐中的應(yīng)用分析［J］.科技與企業(yè)，2013（22）：158.