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

劉建樹(shù) 李健維 劉 霖

（中國(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］引入一類(lèi)旋轉(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)線(xiàn)上緯度差1°對(duì)應(yīng)的實(shí)際距離約是111km，在除赤道外的其他緯線(xiàn)上，經(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得到的成沒(méi)有重復(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滿(mǎn)足：

則判定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。這兩條推理的支持度和置信度都分別滿(mǎn)足支持度閾值和置信度閾值的限制，因此都會(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ā)生是排斥的。

可見(jiàn)，僅僅利用支持度和置信度很容易挖掘出實(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)題，引入一種被廣泛使用的稱(chēng)為提升度的概念。

提升度（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ú)立，沒(méi)有相關(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)題，引入了一種稱(chēng)為改進(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)性稱(chēng)為可能。

下文中即使用改進(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ù)，稱(chēng)之為項(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ò)程見(jiàn)文章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)性更緊密，可見(jià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)表示不同的船舶。可以看到挖掘出的三條船舶的航跡相似度很高，可見(jiàn)該算法的有效性和實(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)確，可信度更高。