徐文進(jìn),管克航,馬 越,黃海廣

(1.青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院,山東 青島 266061; 2.中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院,山東 青島 266100;3.溫州大學(xué)計(jì)算機(jī)與人工智能學(xué)院,浙江 溫州 325000)

0 引 言

海上船舶通過(guò)船舶自動(dòng)識(shí)別系統(tǒng)(Automatic Identification System, AIS)終端和衛(wèi)星終端將海量的船舶定位數(shù)據(jù)通過(guò)AIS基站、衛(wèi)星通訊等方式傳輸至數(shù)據(jù)中心[1]。雖然中心根據(jù)數(shù)據(jù)可以簡(jiǎn)單地查找出漁船的信息，如位置、船舶的狀態(tài)等，但是對(duì)于軌跡數(shù)據(jù)熱點(diǎn)的尋找是非常欠缺的。文獻(xiàn)[2-3]論述了漁船數(shù)據(jù)的收集和系統(tǒng)的開(kāi)發(fā)，但是缺少了對(duì)數(shù)據(jù)的挖掘?，F(xiàn)階段通過(guò)漁船軌跡數(shù)據(jù)追尋捕魚(yú)熱點(diǎn)面臨著3個(gè)迫切需要解決的重要問(wèn)題。首先，海量的數(shù)據(jù)無(wú)法處理，對(duì)于漁船數(shù)據(jù)來(lái)說(shuō)，每個(gè)小時(shí)的數(shù)據(jù)記錄量已經(jīng)達(dá)到了十幾萬(wàn)條，這對(duì)于數(shù)據(jù)的實(shí)時(shí)處理是非常重要的；其次，選取部分?jǐn)?shù)據(jù)作為研究對(duì)象缺乏依據(jù)，比如選取哪些數(shù)據(jù)可以代表一批次的漁船活動(dòng)的軌跡等，數(shù)據(jù)的選取完全是人工選定，缺乏客觀性；最后是熱點(diǎn)追蹤技術(shù)的研究，一般是使用熱力圖的方式查看熱點(diǎn)的區(qū)域，當(dāng)數(shù)據(jù)量達(dá)到幾百萬(wàn)、幾千萬(wàn)時(shí)，熱力圖的計(jì)算開(kāi)銷(xiāo)非常大，難以實(shí)現(xiàn)熱點(diǎn)的定位。文獻(xiàn)[4-5]開(kāi)展了一種基于時(shí)空數(shù)據(jù)場(chǎng)與復(fù)雜網(wǎng)絡(luò)的城市熱點(diǎn)提取的研究，主要是把軌跡點(diǎn)與現(xiàn)實(shí)中的道路和區(qū)域相符合然后根據(jù)行政區(qū)域之間的時(shí)空演變來(lái)進(jìn)行熱點(diǎn)的挖掘；文獻(xiàn)[6]開(kāi)展了一種行為識(shí)別與時(shí)空分布的研究，分析了交接班事件的時(shí)空分布特征；由于漁船在海洋中行駛，并沒(méi)有線路、站點(diǎn)、區(qū)域的劃分，所以在漁船軌跡中以上的熱點(diǎn)挖掘算法是無(wú)法實(shí)現(xiàn)的?；貧w到熱點(diǎn)挖掘的本質(zhì)，其實(shí)就是對(duì)經(jīng)?；顒?dòng)的區(qū)域做出聚類(lèi)操作。本文嘗試使用K-means這種經(jīng)典算法進(jìn)行對(duì)漁船軌跡熱點(diǎn)的挖掘。K-means作為一種經(jīng)典的聚類(lèi)算法，它是給定K值，然后隨機(jī)地初始化K個(gè)中心點(diǎn)，計(jì)算其他點(diǎn)到各個(gè)中心點(diǎn)的距離，把該點(diǎn)劃分到該類(lèi)之下；然后進(jìn)行中心點(diǎn)迭代。雖然隨著研究的深入，對(duì)于K-means算法本身在初始化中心點(diǎn)以及確認(rèn)K值策略上有了很大的進(jìn)步，如文獻(xiàn)[7]為了降低K-means算法對(duì)于初始化中心點(diǎn)的依賴(lài)性，選擇K個(gè)相互距離較遠(yuǎn)的樣本點(diǎn)作為中心點(diǎn)進(jìn)行聚類(lèi)；文獻(xiàn)[8]運(yùn)用密度指針的方式進(jìn)行聚類(lèi)的初始化；文獻(xiàn)[9]提出了一種基于最近鄰接距離的方式確認(rèn)K值等方法。綜上，改進(jìn)的算法只是在小樣本的數(shù)據(jù)中表現(xiàn)很好，對(duì)于上萬(wàn)條或百萬(wàn)條數(shù)據(jù)而言，一般的改進(jìn)聚類(lèi)算法都是無(wú)法滿(mǎn)足需求。以上的改進(jìn)K-means算法根據(jù)給出的數(shù)據(jù)完成聚類(lèi)的操作，無(wú)法實(shí)現(xiàn)對(duì)數(shù)據(jù)進(jìn)行處理，比如按照一定的規(guī)則選出信息價(jià)值較高的數(shù)據(jù)，然后進(jìn)行聚類(lèi)。對(duì)于漁船軌跡數(shù)據(jù)而言主要的問(wèn)題是，數(shù)據(jù)量較大、數(shù)據(jù)具有時(shí)間維度特性，一般的改進(jìn)聚類(lèi)無(wú)法完成相應(yīng)的聚類(lèi)操作。

本文提出的熱點(diǎn)挖掘算法，利用文獻(xiàn)[4]中的時(shí)間序列的思想，來(lái)查看在時(shí)間間隔T下的軌跡的變化。設(shè)置置信水平系數(shù)，作為選取數(shù)據(jù)的依據(jù)，并引入KL散度作為評(píng)判數(shù)據(jù)是否具有合法性的判斷，最后通過(guò)K-means聚類(lèi)方法進(jìn)行數(shù)據(jù)的聚類(lèi)。對(duì)于原始K-means算法需要輸入K值的問(wèn)題，文獻(xiàn)[9]提出了一種聚類(lèi)有效性度量的方法。本文參考其處理的辦法，從而整體上實(shí)現(xiàn)了熱點(diǎn)定位。

1 K-means算法概述

類(lèi)算法在1975年于《Clustering Algorithms》著作中論述到，它是Hartigan編寫(xiě)的首個(gè)關(guān)于類(lèi)算法的書(shū)籍。在后來(lái)的發(fā)展中，學(xué)術(shù)界又進(jìn)行了積極的探討和挖掘，聚類(lèi)分析延伸出了多種基于不同原則的聚類(lèi)算法，在這其中就包含了以層級(jí)法及劃分法為代表具有較好聚類(lèi)效果的算法[7]。同時(shí)人們?cè)诓粩嗟奶剿飨?，為了彌補(bǔ)聚類(lèi)算法的缺點(diǎn)，提升聚類(lèi)的效果，使用了其他的方法與之結(jié)合，促進(jìn)了聚類(lèi)算法在其他領(lǐng)域中的應(yīng)用，比如免疫算法、遺傳算法等。

K-means算法作為一種常用的聚類(lèi)算法，它有聚類(lèi)方法簡(jiǎn)單、效率高的特點(diǎn)。該算法目的是：把所有的樣本分為K個(gè)不同的組，K值的確定是人工選定的。其過(guò)程是，算法根據(jù)人工設(shè)定的K值，隨機(jī)初始化K個(gè)中心點(diǎn)。通過(guò)公式(1)，計(jì)算剩余點(diǎn)距離各個(gè)中心點(diǎn)的距離。把該樣本點(diǎn)劃分給距離最近的核心點(diǎn)，直至劃分完所有的點(diǎn)。

I(i)=‖x(i)-x(j)‖2

(1)

對(duì)比查出最小的I值，將點(diǎn)劃分到距離最小的那簇類(lèi)，直至完成所有的數(shù)據(jù)點(diǎn)，最后運(yùn)用公式(2)計(jì)算新的中心點(diǎn)，直到中心點(diǎn)不再改變時(shí)結(jié)束[9]：

(2)

K-means算法的步驟如下：

步驟1 初始化并設(shè)置K值，初始化一個(gè)S簇，其中S簇包含了所有的樣本。

步驟2 在所有的樣本中隨機(jī)選擇K個(gè)不同的值，作為算法的初始中心點(diǎn)。

步驟3 根據(jù)公式(1)計(jì)算剩下樣本點(diǎn)與各個(gè)簇中心點(diǎn)的距離。

步驟4 遍歷所有的樣本，利用公式(2)更新各個(gè)簇的中心點(diǎn)。

步驟5 查看此次的中心點(diǎn)是否發(fā)生了變化，如果是則重復(fù)執(zhí)行步驟3～步驟5，否則執(zhí)行步驟6。

步驟6 算法結(jié)束。

根據(jù)算法的整體描述，可以看出，K-means在處理數(shù)據(jù)時(shí)，只是給出了聚類(lèi)的方式[10]，不會(huì)對(duì)數(shù)據(jù)進(jìn)行任何處理，而且K值需要人工設(shè)定，在漁船軌跡數(shù)據(jù)進(jìn)行聚類(lèi)時(shí)，發(fā)現(xiàn)由于軌跡數(shù)據(jù)具有時(shí)間序列性以及數(shù)據(jù)量大的特點(diǎn)，原始的K-menas算法無(wú)法進(jìn)行有效聚類(lèi)以及熱點(diǎn)定位。本文以此為切入點(diǎn)，提出一種基于K-means的漁船軌跡數(shù)據(jù)熱點(diǎn)挖掘算法。

2 基于K-means的漁船軌跡數(shù)據(jù)熱點(diǎn)挖掘算法

在研究漁船軌跡熱點(diǎn)捕捉的過(guò)程中，K-means算法雖然在聚類(lèi)方面表現(xiàn)優(yōu)異，但處理漁船數(shù)據(jù)這種具有時(shí)間序列性、數(shù)量大的數(shù)據(jù)時(shí)無(wú)法準(zhǔn)確進(jìn)行熱點(diǎn)聚類(lèi)。所以本文利用時(shí)間維度、KL散度和聚類(lèi)有效性度量的方法來(lái)改進(jìn)K-means算法,使其具有可以處理漁船軌跡數(shù)據(jù)的能力。

2.1 時(shí)間維度處理軌跡數(shù)據(jù)

為了解決漁船軌跡數(shù)據(jù)具有時(shí)序性、數(shù)據(jù)量大的問(wèn)題，本文提出時(shí)間維度處理漁船軌跡數(shù)據(jù)的方法。在介紹時(shí)間維度獲取數(shù)據(jù)之前，需要簡(jiǎn)述置信度、置信區(qū)間以及KL散度的概念。

在統(tǒng)計(jì)學(xué)中，置信度(可靠度)與置信系數(shù)多被用來(lái)判定樣本選用是否合理的依據(jù)。本文簡(jiǎn)略地介紹一下關(guān)于統(tǒng)計(jì)值、參數(shù)值的一般概念。對(duì)于樣本來(lái)說(shuō)，其統(tǒng)計(jì)值與參數(shù)值是不同的，對(duì)于統(tǒng)計(jì)值來(lái)說(shuō)，它是描述關(guān)于樣本在某一方面特征的信息，具體而言，統(tǒng)計(jì)值是關(guān)于樣本的某一個(gè)具體屬性的均值的概念。對(duì)于參數(shù)值來(lái)說(shuō)，它是對(duì)樣本整體的一個(gè)具體屬性真實(shí)的描述。置信度是指全體樣本的參數(shù)值落到所選樣本統(tǒng)計(jì)值區(qū)間([1-a,1+a],其中a一般取0.5)中的概率是多少。置信度是評(píng)價(jià)樣本選擇是否合理的重要參數(shù)值，置信區(qū)間是描述樣本與整體樣本之間的差異值是多少，是評(píng)價(jià)樣本對(duì)于整體樣本來(lái)說(shuō)是否是精確的指標(biāo)。KL散度是用來(lái)衡量2種數(shù)據(jù)分布之間的相似性的指標(biāo)，KL計(jì)算的值越接近0，說(shuō)明2種數(shù)據(jù)的分布越相似。

時(shí)間維度處理軌跡數(shù)據(jù)的思想，借用了置信度與分布相似性的思想。按照時(shí)間間隔T把具有時(shí)間序列化的數(shù)據(jù)進(jìn)行切片，按照時(shí)間順序排列數(shù)據(jù)塊，依次取出數(shù)據(jù)塊，與該塊前面的數(shù)據(jù)作對(duì)比，取出數(shù)據(jù)塊交集的部分，直到計(jì)算交集部分?jǐn)?shù)據(jù)滿(mǎn)足設(shè)定的置信度和局部最小值KL值。具體操作如圖1所示。

如圖1所示，漁船數(shù)據(jù)的初始化操作，首先A單元中裝有所有的已經(jīng)按照時(shí)間順序排列的軌跡數(shù)據(jù)，按照時(shí)間間隔T進(jìn)行切片。在初始化階段，B單元中沒(méi)有數(shù)據(jù)，如圖1(b)所示，數(shù)據(jù)塊直接放入B中。

如圖2所示，漁船數(shù)據(jù)對(duì)比取數(shù)據(jù)操作，當(dāng)初始化完成后，再?gòu)腁中取出一個(gè)T間隔的數(shù)據(jù)塊，與B中所有的數(shù)據(jù)作對(duì)比，交集的數(shù)據(jù)放入C中，然后將數(shù)據(jù)塊Ti裝入B中，直到C中的數(shù)據(jù)滿(mǎn)足置信度與KL散度條件為止。對(duì)于漁船軌跡數(shù)據(jù)置信度的計(jì)算如下：

圖2的C單元中的數(shù)據(jù)為{A1,…,Ak}，每個(gè)數(shù)據(jù)包括經(jīng)度值xk和緯度值yk。則置信區(qū)間(把圖2的C單元中每個(gè)數(shù)據(jù)看成圖2的B單元中總體數(shù)據(jù)的參數(shù)值，根據(jù)顯著水平參數(shù)設(shè)置置信區(qū)間)包括k個(gè)置信區(qū)間，分別為：

第1個(gè)置信區(qū)間為[(x1(1-α),y1(1-α))，(x1(1+α),y1(1+α))]。

…

第k個(gè)置信區(qū)間為[(xk(1-α),yk(1-α))，(xk(1+α),yk(1+α))]。

統(tǒng)計(jì)圖2的B單元中落入置信區(qū)間的個(gè)數(shù)，其過(guò)程為：從圖2的B單元中拿出數(shù)據(jù)，判斷是否在圖2的C單元數(shù)據(jù)的置信區(qū)間內(nèi)，遍歷圖2的B單元中的所有數(shù)據(jù)，找出能夠落入以上置信區(qū)間的數(shù)據(jù)的個(gè)數(shù)n(如果圖2的B單元中的數(shù)據(jù)可以落入多個(gè)圖2的C單元中的置信區(qū)間，該數(shù)據(jù)只統(tǒng)計(jì)一次)。

(3)

其中，N為圖2的B單元中的個(gè)數(shù)，n為落入圖2的C單元的置信區(qū)間內(nèi)的個(gè)數(shù)，a為設(shè)置的顯著水平參數(shù)。

當(dāng)滿(mǎn)足了公式(3)后，需要再滿(mǎn)足KL散度到達(dá)局部的最小值，取數(shù)據(jù)操作才完成。其中KL的散度計(jì)算過(guò)程如下：

河谷平原孔隙潛水與地表水水力聯(lián)系密切，徑流條件良好，枯季多為地下水補(bǔ)給地表水，汛期是地表水補(bǔ)給地下水，上游地下徑流在下游多以地表徑流出現(xiàn)。

計(jì)算KL散度需要確定圖2的C單元中數(shù)據(jù)的分布情況，利用公式(4)計(jì)算圖2的C單元每個(gè)數(shù)據(jù)的分布情況：

(4)

同理計(jì)算圖2的B單元中的數(shù)據(jù)分布情況為計(jì)算圖2的B單元里與圖2的C單元重合的那部分?jǐn)?shù)據(jù)的分布情況，實(shí)際上就是交集單元的數(shù)據(jù)在并集單元里的分布情況，其公式為：

(5)

分布散度計(jì)算公式為：

D(P‖Q)=H′ (j)-H(j)

(6)

其中，D(P‖Q)代表分布散度。求出所選出的數(shù)據(jù)，分析在圖2的C單元和圖2的B單元中的分布情況是否相同，當(dāng)數(shù)據(jù)越小時(shí)，說(shuō)明B、C單元中的數(shù)據(jù)分布越相同。

通過(guò)時(shí)間維度獲取數(shù)據(jù)的方法，當(dāng)滿(mǎn)足KL散度和置信度條件的時(shí)刻下，該時(shí)刻的全部數(shù)據(jù)可由其部分重要的數(shù)據(jù)代替表示。可以認(rèn)為，對(duì)這一部分?jǐn)?shù)據(jù)操作可以代表對(duì)全部的數(shù)據(jù)的操作。

2.2 聚類(lèi)有效性度量

簇類(lèi)內(nèi)的距離之和值Sin的計(jì)算公式為:

(7)

簇類(lèi)間的值Sout的計(jì)算公式為：

(8)

把G定義為判定聚類(lèi)效果優(yōu)劣程度的標(biāo)準(zhǔn)，計(jì)算公式為：

(9)

當(dāng)G越小時(shí)說(shuō)明聚類(lèi)效果越好。使用聚類(lèi)有效性度量的技術(shù)，可以實(shí)現(xiàn)算法自動(dòng)地尋找K值，不需要人工設(shè)置，使得本文的算法更加便于使用。

2.3 本文算法流程

本文提出的基于K-means的漁船軌跡熱點(diǎn)挖掘算法實(shí)現(xiàn)的具體步驟如下：

步驟1 輸入總的軌跡數(shù)據(jù)，設(shè)置參數(shù)T和a，其中，T為取數(shù)據(jù)的時(shí)間間隔，a為顯著水平參數(shù)，G=0、K=1。

步驟2 總的軌跡數(shù)據(jù)中每隔時(shí)間間隔T的數(shù)據(jù)構(gòu)成一個(gè)數(shù)據(jù)塊Si，其中，S1代表第1個(gè)時(shí)間間隔T的數(shù)據(jù)塊，S2代表第2個(gè)時(shí)間間隔T的數(shù)據(jù)塊，以此類(lèi)推；將S1和S2這2個(gè)數(shù)據(jù)塊取交集，即S1∩S2，獲得交集數(shù)據(jù)存入交集單元；將S1和S2這2個(gè)數(shù)據(jù)塊取并集，即S1∪S2，獲得并集數(shù)據(jù)存入并集單元。

步驟3 利用交集單元中的數(shù)據(jù)獲取置信區(qū)間，獲取并集單元中落入置信區(qū)間的數(shù)據(jù)個(gè)數(shù)n，并集單元中總數(shù)據(jù)個(gè)數(shù)為N，判斷n/N是否大于等于1-a，若不滿(mǎn)足則執(zhí)行步驟4；若滿(mǎn)足則計(jì)算交集單元里的數(shù)據(jù)分布情況和并集單元里的數(shù)據(jù)分布情況，再計(jì)算分布散度；判斷分布散度是否接近0，若滿(mǎn)足則執(zhí)行步驟5，若不滿(mǎn)足則執(zhí)行步驟4。

步驟4 取下一個(gè)時(shí)間間隔T的數(shù)據(jù)塊，將下一個(gè)時(shí)間間隔T的數(shù)據(jù)塊與并集單元取交集，更新交集單元；將下一個(gè)時(shí)間間隔T的數(shù)據(jù)塊與并集單元取并集，更新并集單元；返回步驟3。

步驟5 將獲得的交集單元中的數(shù)據(jù)作為樣本點(diǎn)，進(jìn)行K-means聚類(lèi)，計(jì)算聚類(lèi)有效性度量，是否小于G：如果是執(zhí)行步驟6；否則執(zhí)行步驟7。

步驟6 將G賦予聚類(lèi)有效性度量，K=K+1,執(zhí)行步驟5。

步驟7k=k-1,進(jìn)行K-means聚類(lèi)輸出。

以上步驟是本文熱點(diǎn)挖掘算法的整個(gè)流程，步驟1～步驟4的操作是為了從大量的數(shù)據(jù)中選出部分信息量比較高的數(shù)據(jù)。步驟5～步驟7是為了對(duì)選出來(lái)的數(shù)據(jù)進(jìn)行聚類(lèi)，確定熱點(diǎn)的分類(lèi)。本文算法數(shù)據(jù)流程如圖3所示。

3 試驗(yàn)仿真

本文的數(shù)據(jù)來(lái)源于浙江省海洋與漁業(yè)局，浙江省海洋與漁業(yè)局的數(shù)據(jù)中心可以雙向訪問(wèn)北斗衛(wèi)星、海事衛(wèi)星運(yùn)營(yíng)商并且匯集浙江省所有的AIS基站的數(shù)據(jù)[3]。本文實(shí)驗(yàn)首先進(jìn)行數(shù)據(jù)的預(yù)處理，通過(guò)檢驗(yàn)數(shù)據(jù)的合法性與合理性2個(gè)方面進(jìn)行數(shù)據(jù)的預(yù)處理，即數(shù)據(jù)是否有缺失情況，以及經(jīng)緯度是否出現(xiàn)很大的偏差。具體的數(shù)據(jù)格式如表1所示。

表1 數(shù)據(jù)格式

圖4展示了某一天的浙江舟山漁船軌跡數(shù)據(jù)，隨機(jī)選取一個(gè)經(jīng)緯度的數(shù)據(jù)塊作為本文算法的實(shí)驗(yàn)數(shù)據(jù)，本文選取了第14個(gè)區(qū)域的數(shù)據(jù)，如圖4(b)所示，數(shù)據(jù)范圍為經(jīng)度:[124°，126°]，緯度:[30°,31°]。

實(shí)驗(yàn)通過(guò)與原始K-means算法的對(duì)比顯示本文算法的優(yōu)越性；由于熱力圖以特殊高亮的形式顯示出訪問(wèn)的熱點(diǎn)區(qū)域，所以采用熱力圖做參照實(shí)驗(yàn)來(lái)顯示本文算法的正確性。

表2 本文算法設(shè)定的參數(shù)與結(jié)果表

表2為本文算法所設(shè)置的時(shí)間間隔和顯著水平值以及在該設(shè)置下所達(dá)到的置信度和KL散度值。

圖5所示為在00:00—03:10時(shí)段，此時(shí)漁船軌跡數(shù)據(jù)為8696條，圖5(a)使用原始的K-means算法進(jìn)行的聚類(lèi)操作，無(wú)法聚類(lèi)出熱點(diǎn)區(qū)域。圖5(b)使用熱力圖進(jìn)行數(shù)據(jù)的展示，其中高亮的部分為漁船熱點(diǎn)訪問(wèn)區(qū)域，也是捕魚(yú)熱點(diǎn)區(qū)域。

(a) 數(shù)據(jù)A棧的初始化 (b) 數(shù)據(jù)B棧的初始化

(a) 數(shù)據(jù)對(duì)比圖 (b) 數(shù)據(jù)對(duì)比完成后的操作

圖3 本文算法流程圖

(a) 漁船軌跡的可視化展示 (b) 第14區(qū)域的軌跡數(shù)據(jù)展示

(a) 原始的K-means數(shù)據(jù)進(jìn)行聚類(lèi) (b) 數(shù)據(jù)的熱點(diǎn)位置

(a) 計(jì)算出的置信度與KL散度值 (b) 本文算法進(jìn)行聚類(lèi)

圖6(a)展示了本文算法在設(shè)置參數(shù)a與T后，每個(gè)時(shí)間段下的KL值與置信度的變化，圖6(b)是在03：10時(shí)，數(shù)據(jù)滿(mǎn)足設(shè)置條件時(shí)的算法進(jìn)行聚類(lèi)的結(jié)果圖，該圖是從8696個(gè)原始數(shù)據(jù)中選出837個(gè)重要數(shù)據(jù)進(jìn)行了聚類(lèi)操作。通過(guò)圖5(a)與圖6(b)進(jìn)行對(duì)比可以看出，本文算法可以有效地處理具有時(shí)序性的漁船軌跡數(shù)據(jù)；通過(guò)圖5(b)與圖6(b)參照實(shí)驗(yàn)可以看出，本文算法找出的熱點(diǎn)形態(tài)基本符合熱力圖熱點(diǎn)部分。

(a) 原始的K-means數(shù)據(jù)進(jìn)行聚類(lèi) (b) 數(shù)據(jù)的熱點(diǎn)位置

圖7為04:00—08:40時(shí)間段下在漁船軌跡數(shù)據(jù)量為10184條時(shí)的聚類(lèi)效果圖，其中原始K-means算法的聚類(lèi)效果如圖7(a)所示，由于軌跡數(shù)據(jù)雜亂無(wú)序，無(wú)法看出該時(shí)間段的漁船軌跡熱點(diǎn)活動(dòng)區(qū)域。在圖7(b)中顯示了熱點(diǎn)區(qū)域的形態(tài)。

(a) 計(jì)算出的置信度與KL散度值 (b) 本文算法進(jìn)行聚類(lèi)

圖8(a)是本文算法[13-14]在每個(gè)時(shí)間段下的KL值與置信度的數(shù)值。當(dāng)置信度滿(mǎn)足的前提下，從出現(xiàn)KL第一最小值時(shí)到08:40時(shí)為止算法進(jìn)行取數(shù)據(jù)操作，然后把選取的數(shù)據(jù)進(jìn)行聚類(lèi)操作。通過(guò)本文算法自動(dòng)找尋K值發(fā)現(xiàn)，聚類(lèi)個(gè)數(shù)為6時(shí)，聚類(lèi)效果最好，如圖8(b)所示。通過(guò)圖7(a)與圖8(b)對(duì)比可知本文算法有效地去除了無(wú)用數(shù)據(jù)，并且很好地完成了聚類(lèi)操作。通過(guò)圖7(b)與圖8(b)參照可知，本文算法在一定程度上保證了正確性，可以很好地找出熱力圖中熱點(diǎn)的位置。

表3為原始K-means算法與本文提出的算法進(jìn)行對(duì)比。如表3所示，K-means算法是靜態(tài)的聚類(lèi)，并未對(duì)數(shù)據(jù)進(jìn)行任何操作。而本文提出的算法，可以選出原始數(shù)據(jù)中信息量比較高的數(shù)據(jù)，并能根據(jù)簇內(nèi)與簇間的差異值尋找合適的K值，從而完成漁船軌跡熱點(diǎn)的挖掘工作。

表3 原始K-means與本文算法對(duì)比結(jié)果表

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

本文立足于普通的聚類(lèi)算法無(wú)法滿(mǎn)足漁船軌跡數(shù)據(jù)熱點(diǎn)捕捉的情況下[15]，提出了一種熱點(diǎn)挖掘算法，來(lái)自主挖掘漁船活動(dòng)軌跡中的熱點(diǎn)凸顯的位置。其主要的思想是[16-18]：以置信度和KL散度為衡量標(biāo)準(zhǔn)，使用時(shí)間維度處理數(shù)據(jù)的方法，從大量雜亂的漁船軌跡數(shù)據(jù)中找出信息量比較高的數(shù)據(jù)，然后利用聚類(lèi)有效性度量的方式改進(jìn)K-means算法K值需要手動(dòng)輸入的情況[19-23]，從而實(shí)現(xiàn)整個(gè)軌跡數(shù)據(jù)熱點(diǎn)捕捉。通過(guò)與原始算法的對(duì)比實(shí)驗(yàn)看出本文算法在處理漁船軌跡數(shù)據(jù)上的優(yōu)越性，并通過(guò)與熱力圖參照實(shí)驗(yàn)說(shuō)明算法在一定程度上的正確性。