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

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

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

0 引 言

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

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

1 K-means算法概述

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

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

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

(1)

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

(2)

K-means算法的步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

…

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

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

(3)

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

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

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

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

(4)

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

(5)

分布散度計算公式為：

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

(6)

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

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

2.2 聚類有效性度量

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

(7)

簇類間的值Sout的計算公式為：

(8)

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

(9)

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

2.3 本文算法流程

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

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

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

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

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

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

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

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

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

3 試驗仿真

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

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

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

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

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

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

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

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

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

圖3 本文算法流程圖

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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