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

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

3 碼頭挖掘算法

3.1 碼頭挖掘算法思路

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

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

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

3.2 停泊點提取

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

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

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

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

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

3.3 停泊點聚類算法

3.3.1 DBSCAN 算法

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

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

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

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

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

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

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

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

functionDBSCAN（D，ε，MinPts）

clusterId＝0；

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

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

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

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

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

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

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

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

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

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

其中，

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

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

根據(jù)上述算法，可以將停泊點數(shù)據(jù)聚成一個個停泊區(qū)域，對不同的停泊區(qū)域肯定需要參照其地理位置信息對其分類。本文通過融合岸基結(jié)構(gòu)物數(shù)據(jù)，根據(jù)碼頭的形狀位置特征從停泊區(qū)域中篩選出碼頭，并將篩選出的碼頭與已有碼頭分布的區(qū)域比對，驗證算法挖掘出碼頭的準(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)物是通過一條條線定義的，通過計算聚類區(qū)域到線的距離即可判斷停泊區(qū)域是否是一個碼頭。

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

4 實驗及分析

4.1 實驗場景

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

Table 1 Experimental environment表1 實驗環(huán)境

Table 2 Experimental dataset表2 實驗數(shù)據(jù)

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

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

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

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

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

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

當(dāng)eps取0.000 68時，所有點類中心密度達到穩(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 核心點的類中心密度隨eps值變化曲線圖

4.3 國內(nèi)滾裝船碼頭挖掘?qū)嶒?/h3>

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

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

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

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

4.4 國際滾裝船碼頭挖掘?qū)嶒?/h3>

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

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

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

5 結(jié)束語

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

［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.

附中文參考文獻：

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