基于改進興趣度的船舶關聯規則挖掘?

劉建樹 李健維 劉 霖

（中國人民解放軍海軍工程大學 武漢 430000）

1 引言

時空數據挖掘作為當前數據挖掘研究的前沿領域之一，備受學術界和工商界的關注。目標的時空數據能夠反映對象的運動模式與規律，利用這些數據能夠挖掘出目標實體的行為模式，并且可以根據這些模式來預測其下一步的行為，因此在各個領域中有著重要的應用［1～10］。

其中，AIS作為一種包含豐富的船舶航行信息的數據載體，集合了大量船舶的海上交通信息。通過對這些海量信息進行挖掘，能夠獲取其中蘊藏著的海上交通特征，發現船舶之間行為的內在關聯性或者船舶本身活動的規律性。將這些行為模式作為發掘出的知識整合規約并存儲，就能夠形成重點船舶的行動模式數據庫。為此，本文選用部分南海海域的船舶AIS數據，采用算法對船舶之間的關聯規則進行挖掘，試圖提取出它們之中具有時空關聯關系的船舶集群。

2 關聯規則挖掘

關聯規則挖掘主要研究空間對象隨時間發生變化的規律，即在傳統關聯分析的基礎上加上了時間和空間約束，以發現時空數據中處于一定時間間隔和空間位置的關聯規則。發現這些關聯模式具有重要的應用價值，如發現購物中商品之間的關聯性、群體性行動的團體成員之間的聯系性等。

關于時空關聯規則的挖掘更注重實體之間的時空關系，維度的增加也導致其研究方法相對普通的關聯規則挖掘來說更為復雜多用。Tao等［11］提出一種基于時空索引和簡圖技術的方法來加快搜索數據的速度，以獲得準確度更高的關聯規則；Verhein等從區域面積以及時間間兩個角度出發，引入了目標在時域上跨區移動的時空關聯規則挖掘方法 STAR-Miner［12～13］，此后，又進一步引入了序列時空關聯模式在這一領域進行了更為深入的研究［14～16］；Lee等［17］提出一種可以挖掘多層次粒度的時空關聯規則的算法；Gidfalvi等［18］引入一類旋轉方法將挖掘工作劃歸為為傳統購物籃問題實現了時空關聯規則挖掘；Yang等［19］在解決蛋白質折疊軌跡的過程中提出了兩種時空關聯框架；Leong等［20］則提出一種能夠探測多種動態模式的關聯規則挖掘方法。

3 面向船舶海洋時空數據的關聯規則挖掘算法

3.1 事務集生成

3.1.1 基于時空塊的數據分割

為了使用Apriori算法對船舶數據進行挖掘，首先要利用原始AIS數據形成可供算法處理的事務集。本文采用一種劃分時空塊的方式來實現這一功能。

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

每一數據塊內的AIS數據所代表的船舶號歸為同一個事務中，即形成初始事務，相同時空塊內出現的船之間具有可能具有某種關聯關系。

3.1.2 事務中的相同船舶去重

在一個時空塊中，會存在某條船有多條數據的情況。利用實測數據得到的結果中也能夠發現這種情況較為普遍，由于不同船舶之間的關聯關系是求解問題的重點，因此在之后的處理中只需要知道同一事務內不同的船舶編號即可，因此對于同一時空塊內相同的船舶編號予以刪除。

3.1.3 生成事務集布爾矩陣

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

3.2 基于改進興趣度的關聯模式挖掘

3.2.1 基于支持度和置信度的關聯規則挖掘

一般來說，傳統的判定某個推理是否是關聯規則的指標有兩個，分別為支持度和置信度。

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

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

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

則判定A-＞B是一條強關聯規則。

但是，實際上僅僅通過上述兩個指標判斷得出的關聯規則會出現兩個問題，下面舉例說明。其一，當假設某個事務集中發生了下列項集的出現情況。

表1 例事物集

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

其二，當將A、B、?A 、?B當作四個不相關的獨立事務時，B事務發生的概率為0.3，而A事務發生并且B事務發生的概率為0.25，也就是說如果設置了A事務發生這個條件，那么B事務出現的比例反而降低了。這就說明A事務的發生和B事務的發生是排斥的。

可見，僅僅利用支持度和置信度很容易挖掘出實際上并不相關的“虛假的”關聯規則，這顯然是十分致命的問題。為此，就需要引入新的度量標準來解決這一問題。

3.2.2 基于提升度的關聯規則挖掘

為了解決上述兩項問題，引入一種被廣泛使用的稱為提升度的概念。

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

提升度反映了關聯規則中的A與B的相關性，提升度＞1且越高表明正相關性越高，提升度＜1且越低表明負相關性越高，提升度=1表明表示X與Y相互獨立，沒有相關性。

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

但是，在本文所解決的問題中，由于AIS數據庫生成的事務較多，因此計算求得的Lift都普遍較大。雖然從定義上講，這些關聯規則的Lift可能都大于1，因此關聯規則的前后項都具有正相關關系，但是如果想要進一步提高Lift的閾值標準來尋找更可信的關聯規則時，閾值設定就成為了困難。為此，需要進一步尋找更實用的評價指標對關聯規則的相關性進行評判。

3.2.3 基于改進興趣度的關聯規則挖掘

為了解決3.2.2中提出的問題，引入了一種稱為改進興趣度（Interest）的概念［21］。其表達式為

改進興趣度（Inerest）將Lift映射為一個有界的數值，從而能夠給定閾值實現更有效的規則篩選，此外，Lift越大其對應的改進興趣度越大，因此利用改進興趣度判定規則的相關性稱為可能。

下文中即使用改進興趣度來衡量關聯規則的可信程度。換言之，本文判定A→B為關聯規則的判據如下：

3.3 算法求解流程

選用Apriori算法作為基礎算法對AIS數據進行挖掘處理。

3.3.1 相關定義

定義1：事務

事務由若干個項目組成，在此問題中項目表示船舶的編號。形如Ij=｛X1，X2，X3，…｝，Ij表示第j個事務。

定義2：事務集

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

定義3：支持度

事務集D中包含項集X的事務個數，稱之為項集X的支持數，用count（X）表示。而項集X的支持度用sup（X）表示，公式如下：

其中，n表示事務集D中事務的總數。

定義4：置信度

包含項集X1的事務中同時包含項集X2的事務的比例，即同時包含項集X1和項集X2的事務占包含項集X1的事務的比例，用con（X1→X2）表示，公式如下：

3.3.2 算法步驟

具體算法步驟如下。

Step1：數據預處理，生成事務集

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

Step2：生成候選項集

對于候選1項集，根據不同船舶號數量直接生成單位矩陣作為其候選項集。

對于候選1+K（K＞0）項集的生成，算法采用對表示不同事務的K項頻繁集矩陣的行向量兩兩進行或運算，再進行篩選，留下只有1+K項的事務行，組成新的候選項集。

Step3：生成頻繁項集

Matlab中使用find函數找出候選K項集的每一個事務行向量值為1的列數，取出SW矩陣中對應列向量，對其每一行進行篩選和計數，其行向量值全為1時計數1次，得到count（X1∪X2∪…）。

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

Step4：迭代

如果新生成的頻繁項集不為空，令K變為K+1，轉到Step2，否則轉到Step5。

Step5：生成關聯規則

根據最小置信度和最小改進興趣度判定每個推理是否是強關聯規則。

對于包含全部頻繁項集的矩陣Z，取其行向量兩兩相比較，若兩矩陣的數值和不相等，則對其兩行向量進行異或運算，再對得到的行向量做求和運算，若其值小于原兩個行向量的其中某一行向量數值求和值，則能推出相應的關聯規則。

求出所有關聯規則后，輸出結果，算法結束。

4 檢測結論

4.1 實驗環境

程序運算平臺為聯想ZX50筆記本電腦；操作系統為 Window10；CPU 為 core i7-4720；內存為16GB；程序處理軟件為Matlab R2014B。

4.2 數據準備

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

4.3 實驗結論

4.3.1 基于支持度和置信度的關聯規則挖掘結果

設置最小支持度為9，最小置信度為0.6，利用上面的數據進行關聯規則挖掘，共得到11條關聯規則，結果如下：

表2 基于支持數置信度的關聯規則挖掘結果

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

4.3.2 基于動態閾值和改進興趣度的關聯規則挖掘結果

設置最小支持度為動態閾值V，最小改進興趣度為0.99，利用上面的數據進行關聯規則挖掘，共得到6條關聯規則，結果如下：觀察表2可以發現，原本表1中第7行之后的關聯規則被刪去，只保留了前6條關聯規則。

表3 基于改進興趣度的關聯規則挖掘結果

算法比較結果顯示，相對于使用傳統的基于支持度和置信度的算法而言，基于改進改進興趣度的關聯規則得出的結果數量更少，船舶的關聯性更緊密，可見算法的有效性。

4.3.3 可視化分析

選擇算法中挖掘得到的改進興趣度最大的關聯規則包含的船舶，做出其航跡，如下圖所示。

圖1 關聯規則中的船舶航跡

其中，橫坐標為東經，縱坐標為北緯，上圖中不同顏色的點表示不同的船舶。可以看到挖掘出的三條船舶的航跡相似度很高，可見該算法的有效性和實用性。

5 結語

本文以改進的Apriori算法為基礎，對AIS數據進行預處理后生成的事務集進行挖掘分析以求取船舶之間的關聯規則。首先將AIS記錄提取后分塊，并將結果轉換成了能夠更快運算的01矩陣模式；然后，在Apriori算法運行過程中，引入了改進興趣度指標，消除了可能存在的誤判問題，使最終的關聯規則結果更加準確，可信度更高。