基于改進(jìn)興趣度的船舶關(guān)聯(lián)規(guī)則挖掘?

劉建樹 李健維 劉 霖

（中國(guó)人民解放軍海軍工程大學(xué) 武漢 430000）

1 引言

時(shí)空數(shù)據(jù)挖掘作為當(dāng)前數(shù)據(jù)挖掘研究的前沿領(lǐng)域之一，備受學(xué)術(shù)界和工商界的關(guān)注。目標(biāo)的時(shí)空數(shù)據(jù)能夠反映對(duì)象的運(yùn)動(dòng)模式與規(guī)律，利用這些數(shù)據(jù)能夠挖掘出目標(biāo)實(shí)體的行為模式，并且可以根據(jù)這些模式來(lái)預(yù)測(cè)其下一步的行為，因此在各個(gè)領(lǐng)域中有著重要的應(yīng)用［1～10］。

其中，AIS作為一種包含豐富的船舶航行信息的數(shù)據(jù)載體，集合了大量船舶的海上交通信息。通過(guò)對(duì)這些海量信息進(jìn)行挖掘，能夠獲取其中蘊(yùn)藏著的海上交通特征，發(fā)現(xiàn)船舶之間行為的內(nèi)在關(guān)聯(lián)性或者船舶本身活動(dòng)的規(guī)律性。將這些行為模式作為發(fā)掘出的知識(shí)整合規(guī)約并存儲(chǔ)，就能夠形成重點(diǎn)船舶的行動(dòng)模式數(shù)據(jù)庫(kù)。為此，本文選用部分南海海域的船舶AIS數(shù)據(jù)，采用算法對(duì)船舶之間的關(guān)聯(lián)規(guī)則進(jìn)行挖掘，試圖提取出它們之中具有時(shí)空關(guān)聯(lián)關(guān)系的船舶集群。

2 關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則挖掘主要研究空間對(duì)象隨時(shí)間發(fā)生變化的規(guī)律，即在傳統(tǒng)關(guān)聯(lián)分析的基礎(chǔ)上加上了時(shí)間和空間約束，以發(fā)現(xiàn)時(shí)空數(shù)據(jù)中處于一定時(shí)間間隔和空間位置的關(guān)聯(lián)規(guī)則。發(fā)現(xiàn)這些關(guān)聯(lián)模式具有重要的應(yīng)用價(jià)值，如發(fā)現(xiàn)購(gòu)物中商品之間的關(guān)聯(lián)性、群體性行動(dòng)的團(tuán)體成員之間的聯(lián)系性等。

關(guān)于時(shí)空關(guān)聯(lián)規(guī)則的挖掘更注重實(shí)體之間的時(shí)空關(guān)系，維度的增加也導(dǎo)致其研究方法相對(duì)普通的關(guān)聯(lián)規(guī)則挖掘來(lái)說(shuō)更為復(fù)雜多用。Tao等［11］提出一種基于時(shí)空索引和簡(jiǎn)圖技術(shù)的方法來(lái)加快搜索數(shù)據(jù)的速度，以獲得準(zhǔn)確度更高的關(guān)聯(lián)規(guī)則；Verhein等從區(qū)域面積以及時(shí)間間兩個(gè)角度出發(fā)，引入了目標(biāo)在時(shí)域上跨區(qū)移動(dòng)的時(shí)空關(guān)聯(lián)規(guī)則挖掘方法 STAR-Miner［12～13］，此后，又進(jìn)一步引入了序列時(shí)空關(guān)聯(lián)模式在這一領(lǐng)域進(jìn)行了更為深入的研究［14～16］；Lee等［17］提出一種可以挖掘多層次粒度的時(shí)空關(guān)聯(lián)規(guī)則的算法；Gidfalvi等［18］引入一類旋轉(zhuǎn)方法將挖掘工作劃歸為為傳統(tǒng)購(gòu)物籃問(wèn)題實(shí)現(xiàn)了時(shí)空關(guān)聯(lián)規(guī)則挖掘；Yang等［19］在解決蛋白質(zhì)折疊軌跡的過(guò)程中提出了兩種時(shí)空關(guān)聯(lián)框架；Leong等［20］則提出一種能夠探測(cè)多種動(dòng)態(tài)模式的關(guān)聯(lián)規(guī)則挖掘方法。

3 面向船舶海洋時(shí)空數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘算法

3.1 事務(wù)集生成

3.1.1 基于時(shí)空塊的數(shù)據(jù)分割

為了使用Apriori算法對(duì)船舶數(shù)據(jù)進(jìn)行挖掘，首先要利用原始AIS數(shù)據(jù)形成可供算法處理的事務(wù)集。本文采用一種劃分時(shí)空塊的方式來(lái)實(shí)現(xiàn)這一功能。

將整個(gè)數(shù)據(jù)集按照經(jīng)度0.02°、緯度0.02°、時(shí)間間隔1200s的分度值進(jìn)行劃分，可以得到若干個(gè)數(shù)據(jù)塊。選取如上分度值的理由如下：在赤道上經(jīng)度差1°對(duì)應(yīng)的實(shí)際距離是111km，在經(jīng)線上緯度差1°對(duì)應(yīng)的實(shí)際距離約是111km，在除赤道外的其他緯線上，經(jīng)度差1°對(duì)應(yīng)的實(shí)際距離是111*cos（緯度）。假設(shè)船舶的平均速度為15海里每小時(shí)，則同一時(shí)空塊內(nèi)的兩船背向航行時(shí)，兩船的最遠(yuǎn)距離約為13*0.33*1.8*2+111*0.02=17.6km，約為目視距離極限。考慮到地球曲率問(wèn)題和不同的海洋情況，取此分度值較為合適。

每一數(shù)據(jù)塊內(nèi)的AIS數(shù)據(jù)所代表的船舶號(hào)歸為同一個(gè)事務(wù)中，即形成初始事務(wù)，相同時(shí)空塊內(nèi)出現(xiàn)的船之間具有可能具有某種關(guān)聯(lián)關(guān)系。

3.1.2 事務(wù)中的相同船舶去重

在一個(gè)時(shí)空塊中，會(huì)存在某條船有多條數(shù)據(jù)的情況。利用實(shí)測(cè)數(shù)據(jù)得到的結(jié)果中也能夠發(fā)現(xiàn)這種情況較為普遍，由于不同船舶之間的關(guān)聯(lián)關(guān)系是求解問(wèn)題的重點(diǎn)，因此在之后的處理中只需要知道同一事務(wù)內(nèi)不同的船舶編號(hào)即可，因此對(duì)于同一時(shí)空塊內(nèi)相同的船舶編號(hào)予以刪除。

3.1.3 生成事務(wù)集布爾矩陣

定義事務(wù)集布爾矩陣如下：設(shè)經(jīng)過(guò)Step2得到的成沒有重復(fù)船舶編號(hào)的事務(wù)共有N條，所包含的船舶共有M個(gè)。則生成一個(gè)N×M的布爾矩陣，矩陣的每行表示一個(gè)事務(wù)，矩陣的列編號(hào) j對(duì)應(yīng)船舶編號(hào) j。若第i條事務(wù)包含船舶 j，則事務(wù)集的布爾矩陣 C中的元素 C(i，j)=1，反之C(i，j)=0 。

3.2 基于改進(jìn)興趣度的關(guān)聯(lián)模式挖掘

3.2.1 基于支持度和置信度的關(guān)聯(lián)規(guī)則挖掘

一般來(lái)說(shuō)，傳統(tǒng)的判定某個(gè)推理是否是關(guān)聯(lián)規(guī)則的指標(biāo)有兩個(gè)，分別為支持度和置信度。

支持度（Support）表示同時(shí)包含A和B的事務(wù)占所有事務(wù)的比例。如果用P（A）表示使用A事務(wù)的比例，那么Support=P（A&B）。

置信度（Confidence）表示使用包含A的事務(wù)中同時(shí)包含B事務(wù)的比例，即同時(shí)包含A和B的事務(wù)占包含A事務(wù)的比例，那么Confidence=P（A&B）/P（A）。

傳統(tǒng)方法設(shè)置了兩個(gè)閾值，分別為最小支持度閾值min-sup和最小置信度閾值min-conf。若某個(gè)推理A-＞B滿足：

則判定A-＞B是一條強(qiáng)關(guān)聯(lián)規(guī)則。

但是，實(shí)際上僅僅通過(guò)上述兩個(gè)指標(biāo)判斷得出的關(guān)聯(lián)規(guī)則會(huì)出現(xiàn)兩個(gè)問(wèn)題，下面舉例說(shuō)明。其一，當(dāng)假設(shè)某個(gè)事務(wù)集中發(fā)生了下列項(xiàng)集的出現(xiàn)情況。

表1 例事物集

按照上邊的計(jì)算方法可以計(jì)算出二者置信度 ：Confidence（?A→?B）=0.66，Confidence（A→?B）=0.75。這兩條推理的支持度和置信度都分別滿足支持度閾值和置信度閾值的限制，因此都會(huì)被判定為關(guān)聯(lián)規(guī)則。但實(shí)際上這兩條規(guī)則顯然是互相矛盾的。

其二，當(dāng)將A、B、?A 、?B當(dāng)作四個(gè)不相關(guān)的獨(dú)立事務(wù)時(shí)，B事務(wù)發(fā)生的概率為0.3，而A事務(wù)發(fā)生并且B事務(wù)發(fā)生的概率為0.25，也就是說(shuō)如果設(shè)置了A事務(wù)發(fā)生這個(gè)條件，那么B事務(wù)出現(xiàn)的比例反而降低了。這就說(shuō)明A事務(wù)的發(fā)生和B事務(wù)的發(fā)生是排斥的。

可見，僅僅利用支持度和置信度很容易挖掘出實(shí)際上并不相關(guān)的“虛假的”關(guān)聯(lián)規(guī)則，這顯然是十分致命的問(wèn)題。為此，就需要引入新的度量標(biāo)準(zhǔn)來(lái)解決這一問(wèn)題。

3.2.2 基于提升度的關(guān)聯(lián)規(guī)則挖掘

為了解決上述兩項(xiàng)問(wèn)題，引入一種被廣泛使用的稱為提升度的概念。

提升度（Lift）：表示“包含A的事務(wù)中同時(shí)包含B事務(wù)的比例”與“包含B事務(wù)的比例”的比值。公式表 達(dá) ：Lift=（P（A&B）/P（A））/P（B）=P（A&B）/P（A）/P（B）。

提升度反映了關(guān)聯(lián)規(guī)則中的A與B的相關(guān)性，提升度＞1且越高表明正相關(guān)性越高，提升度＜1且越低表明負(fù)相關(guān)性越高，提升度=1表明表示X與Y相互獨(dú)立，沒有相關(guān)性。

利用此定義再次省視上一節(jié)提到的問(wèn)題，可以發(fā)現(xiàn)：Lift（?A→?B）=0.95，Lift（A→?B）=1.07。顯然，此時(shí)由于A→?B的提升度大于1，A和?B具有正相關(guān)關(guān)系，因此A→?B被選擇為關(guān)聯(lián)規(guī)則為，?A→?B則被刪去，從而消除了規(guī)則之間互相矛盾的問(wèn)題。

但是，在本文所解決的問(wèn)題中，由于AIS數(shù)據(jù)庫(kù)生成的事務(wù)較多，因此計(jì)算求得的Lift都普遍較大。雖然從定義上講，這些關(guān)聯(lián)規(guī)則的Lift可能都大于1，因此關(guān)聯(lián)規(guī)則的前后項(xiàng)都具有正相關(guān)關(guān)系，但是如果想要進(jìn)一步提高Lift的閾值標(biāo)準(zhǔn)來(lái)尋找更可信的關(guān)聯(lián)規(guī)則時(shí)，閾值設(shè)定就成為了困難。為此，需要進(jìn)一步尋找更實(shí)用的評(píng)價(jià)指標(biāo)對(duì)關(guān)聯(lián)規(guī)則的相關(guān)性進(jìn)行評(píng)判。

3.2.3 基于改進(jìn)興趣度的關(guān)聯(lián)規(guī)則挖掘

為了解決3.2.2中提出的問(wèn)題，引入了一種稱為改進(jìn)興趣度（Interest）的概念［21］。其表達(dá)式為

改進(jìn)興趣度（Inerest）將Lift映射為一個(gè)有界的數(shù)值，從而能夠給定閾值實(shí)現(xiàn)更有效的規(guī)則篩選，此外，Lift越大其對(duì)應(yīng)的改進(jìn)興趣度越大，因此利用改進(jìn)興趣度判定規(guī)則的相關(guān)性稱為可能。

下文中即使用改進(jìn)興趣度來(lái)衡量關(guān)聯(lián)規(guī)則的可信程度。換言之，本文判定A→B為關(guān)聯(lián)規(guī)則的判據(jù)如下：

3.3 算法求解流程

選用Apriori算法作為基礎(chǔ)算法對(duì)AIS數(shù)據(jù)進(jìn)行挖掘處理。

3.3.1 相關(guān)定義

定義1：事務(wù)

事務(wù)由若干個(gè)項(xiàng)目組成，在此問(wèn)題中項(xiàng)目表示船舶的編號(hào)。形如Ij=｛X1，X2，X3，…｝，Ij表示第j個(gè)事務(wù)。

定義2：事務(wù)集

事務(wù)集由全體事務(wù)組成D=｛I1，I2，…，Ij，…，In｝，Ij表示第j個(gè)事務(wù)。

定義3：支持度

事務(wù)集D中包含項(xiàng)集X的事務(wù)個(gè)數(shù)，稱之為項(xiàng)集X的支持?jǐn)?shù)，用count（X）表示。而項(xiàng)集X的支持度用sup（X）表示，公式如下：

其中，n表示事務(wù)集D中事務(wù)的總數(shù)。

定義4：置信度

包含項(xiàng)集X1的事務(wù)中同時(shí)包含項(xiàng)集X2的事務(wù)的比例，即同時(shí)包含項(xiàng)集X1和項(xiàng)集X2的事務(wù)占包含項(xiàng)集X1的事務(wù)的比例，用con（X1→X2）表示，公式如下：

3.3.2 算法步驟

具體算法步驟如下。

Step1：數(shù)據(jù)預(yù)處理，生成事務(wù)集

詳細(xì)處理過(guò)程見文章4.3.2。最后得到01矩陣，即附件中的SW矩陣。初始化迭代值K=0。

Step2：生成候選項(xiàng)集

對(duì)于候選1項(xiàng)集，根據(jù)不同船舶號(hào)數(shù)量直接生成單位矩陣作為其候選項(xiàng)集。

對(duì)于候選1+K（K＞0）項(xiàng)集的生成，算法采用對(duì)表示不同事務(wù)的K項(xiàng)頻繁集矩陣的行向量?jī)蓛蛇M(jìn)行或運(yùn)算，再進(jìn)行篩選，留下只有1+K項(xiàng)的事務(wù)行，組成新的候選項(xiàng)集。

Step3：生成頻繁項(xiàng)集

Matlab中使用find函數(shù)找出候選K項(xiàng)集的每一個(gè)事務(wù)行向量值為1的列數(shù)，取出SW矩陣中對(duì)應(yīng)列向量，對(duì)其每一行進(jìn)行篩選和計(jì)數(shù)，其行向量值全為1時(shí)計(jì)數(shù)1次，得到count（X1∪X2∪…）。

然后分別根據(jù)兩種情況篩選出符合條件的頻繁1+K項(xiàng)集。一是根據(jù)最小支持?jǐn)?shù)min_count=9（本實(shí)驗(yàn)采用的最小支持?jǐn)?shù)為9），從中篩選出符合條件的頻繁1+K項(xiàng)集，及支持?jǐn)?shù)大于等于9時(shí)，取其值生成頻繁項(xiàng)集。

Step4：迭代

如果新生成的頻繁項(xiàng)集不為空，令K變?yōu)镵+1，轉(zhuǎn)到Step2，否則轉(zhuǎn)到Step5。

Step5：生成關(guān)聯(lián)規(guī)則

根據(jù)最小置信度和最小改進(jìn)興趣度判定每個(gè)推理是否是強(qiáng)關(guān)聯(lián)規(guī)則。

對(duì)于包含全部頻繁項(xiàng)集的矩陣Z，取其行向量?jī)蓛上啾容^，若兩矩陣的數(shù)值和不相等，則對(duì)其兩行向量進(jìn)行異或運(yùn)算，再對(duì)得到的行向量做求和運(yùn)算，若其值小于原兩個(gè)行向量的其中某一行向量數(shù)值求和值，則能推出相應(yīng)的關(guān)聯(lián)規(guī)則。

求出所有關(guān)聯(lián)規(guī)則后，輸出結(jié)果，算法結(jié)束。

4 檢測(cè)結(jié)論

4.1 實(shí)驗(yàn)環(huán)境

程序運(yùn)算平臺(tái)為聯(lián)想ZX50筆記本電腦；操作系統(tǒng)為 Window10；CPU 為 core i7-4720；內(nèi)存為16GB；程序處理軟件為Matlab R2014B。

4.2 數(shù)據(jù)準(zhǔn)備

選取一份船舶AIS記錄，提取每條記錄的經(jīng)度、緯度、時(shí)間戳和船舶號(hào)數(shù)據(jù)，存入excel中，作為挖掘用的源數(shù)據(jù)。選用的數(shù)據(jù)中共包含393條船，70萬(wàn)條AIS記錄，經(jīng)度跨度為東經(jīng)109.94°～110.2°，緯度跨度為北緯20.11351°～20.193665°，時(shí)間跨度為2675816s。

4.3 實(shí)驗(yàn)結(jié)論

4.3.1 基于支持度和置信度的關(guān)聯(lián)規(guī)則挖掘結(jié)果

設(shè)置最小支持度為9，最小置信度為0.6，利用上面的數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，共得到11條關(guān)聯(lián)規(guī)則，結(jié)果如下：

表2 基于支持?jǐn)?shù)置信度的關(guān)聯(lián)規(guī)則挖掘結(jié)果

觀察表2可以發(fā)現(xiàn)，表2中1～3行的關(guān)聯(lián)規(guī)則是三條船舶之間的關(guān)聯(lián)規(guī)則，它們之間兩兩都能推出第三條船；4～6行及7～9行也是相同的情況。

4.3.2 基于動(dòng)態(tài)閾值和改進(jìn)興趣度的關(guān)聯(lián)規(guī)則挖掘結(jié)果

設(shè)置最小支持度為動(dòng)態(tài)閾值V，最小改進(jìn)興趣度為0.99，利用上面的數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，共得到6條關(guān)聯(lián)規(guī)則，結(jié)果如下：觀察表2可以發(fā)現(xiàn)，原本表1中第7行之后的關(guān)聯(lián)規(guī)則被刪去，只保留了前6條關(guān)聯(lián)規(guī)則。

表3 基于改進(jìn)興趣度的關(guān)聯(lián)規(guī)則挖掘結(jié)果

算法比較結(jié)果顯示，相對(duì)于使用傳統(tǒng)的基于支持度和置信度的算法而言，基于改進(jìn)改進(jìn)興趣度的關(guān)聯(lián)規(guī)則得出的結(jié)果數(shù)量更少，船舶的關(guān)聯(lián)性更緊密，可見算法的有效性。

4.3.3 可視化分析

選擇算法中挖掘得到的改進(jìn)興趣度最大的關(guān)聯(lián)規(guī)則包含的船舶，做出其航跡，如下圖所示。

圖1 關(guān)聯(lián)規(guī)則中的船舶航跡

其中，橫坐標(biāo)為東經(jīng)，縱坐標(biāo)為北緯，上圖中不同顏色的點(diǎn)表示不同的船舶?？梢钥吹酵诰虺龅娜龡l船舶的航跡相似度很高，可見該算法的有效性和實(shí)用性。

5 結(jié)語(yǔ)

本文以改進(jìn)的Apriori算法為基礎(chǔ)，對(duì)AIS數(shù)據(jù)進(jìn)行預(yù)處理后生成的事務(wù)集進(jìn)行挖掘分析以求取船舶之間的關(guān)聯(lián)規(guī)則。首先將AIS記錄提取后分塊，并將結(jié)果轉(zhuǎn)換成了能夠更快運(yùn)算的01矩陣模式；然后，在Apriori算法運(yùn)行過(guò)程中，引入了改進(jìn)興趣度指標(biāo)，消除了可能存在的誤判問(wèn)題，使最終的關(guān)聯(lián)規(guī)則結(jié)果更加準(zhǔn)確，可信度更高。