關(guān)聯(lián)規(guī)則挖掘在電子對抗目標(biāo)分析中的應(yīng)用

李 政，祝 利，韋 偉

（電子工程學(xué)院，合肥 230037）

0 引 言

信息化戰(zhàn)場上的電子對抗目標(biāo)之間、電子對抗目標(biāo)與其它武器系統(tǒng)、作戰(zhàn)行動之間往往是相互聯(lián)系的。掌握這種關(guān)聯(lián)關(guān)系，可以更加準(zhǔn)確地把握電子對抗目標(biāo)的活動規(guī)律，并對其活動進行預(yù)測，為電子對抗作戰(zhàn)和其它作戰(zhàn)預(yù)案的制定提供依據(jù)。

對于電子對抗目標(biāo)的關(guān)聯(lián)分析，目前主要基于先驗知識的人工判斷。隨著電子對抗目標(biāo)增多及其活動規(guī)律日益復(fù)雜，上述方法愈加難以實現(xiàn)。如何從海量偵察數(shù)據(jù)中使用自動化方法對電子對抗目標(biāo)進行關(guān)聯(lián)分析，成為一個亟待解決的問題。

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

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的一個重要領(lǐng)域，是模式挖掘的一種基本形式，其目的是挖掘和搜索數(shù)據(jù)集中反復(fù)出現(xiàn)的聯(lián)系。關(guān)聯(lián)規(guī)則有些是常識、經(jīng)驗性的，而另一些則是啟發(fā)性的。

隨著可分析數(shù)據(jù)量的增大，關(guān)聯(lián)規(guī)則挖掘越來越受到重視。例如在商業(yè)領(lǐng)域，從大量交易數(shù)據(jù)中發(fā)現(xiàn)相關(guān)聯(lián)系，可以為產(chǎn)品促銷、超市貨架規(guī)劃、顧客購買習(xí)慣分析提供決策支持。

1.1 相關(guān)概念

1.1.1 關(guān)聯(lián)規(guī)則

設(shè)I＝｛i1，i2，…，im｝為項集，D是數(shù)據(jù)庫事務(wù)的集合，其中每個事務(wù)T是一個非空項集且T?I。設(shè)A是一個項集，包含于事務(wù)T中。關(guān)聯(lián)規(guī)則形如A?B，其中A?I，B?I，A≠?，B≠?，并且A∩B≠?［1］。關(guān)聯(lián)規(guī)則表示某一類或幾類項目與另一類項目之間存在的單向影響關(guān)系。關(guān)聯(lián)規(guī)則的典型案例是購物籃模型，例如通過對顧客購物籃內(nèi)貨物的分析，可以發(fā)現(xiàn)牛奶和面包等某幾種貨物總是頻繁地一起出現(xiàn)。這個例子中，“購買牛奶的顧客更傾向于買面包”即是一條關(guān)聯(lián)規(guī)則，可以表示為：

1.1.2 支持度與置信度

支持度s表示A∪B在事務(wù)D中所占的百分比，即s（A?B）＝P（A∪B）。置信度c表示D包含A的事務(wù)的同時包含B的事務(wù)的百分比，即c（A?B）＝P（B｜A）。支持度和置信度是對于規(guī)則的2種度量，分別表示規(guī)則的普適程度和確定程度。最終挖掘的結(jié)果與挖掘算法中最小支持度與置信度閾值的取值有很大關(guān)系，若取值過高，難以發(fā)現(xiàn)關(guān)聯(lián)規(guī)則，若取值較低，關(guān)聯(lián)規(guī)則的參考價值就會大打折扣，且其數(shù)目會過多。在上述“牛奶與面包”的例子中，若關(guān)聯(lián)規(guī)則的支持度為5%，置信度為60%，可以表示為：

1.1.3 頻繁項集

若項集I滿足設(shè)定的最小支持度閾值，則稱I為頻繁項集。上述例子中，由于牛奶和面包總是頻繁地一起出現(xiàn)在購物籃中，若其滿足相應(yīng)的支持度與置信度條件，則＜牛奶，面包＞構(gòu)成了一個頻繁項集。根據(jù)支持度與置信度的定義，置信度與支持度有如下關(guān)系：

式中：s＿count（）為支持度計數(shù)。

根據(jù)式（1），A?B的支持度與置信度很容易從A、B和A∪B的支持度計數(shù)中得出，也就是說一旦確定A、B和A∪B的支持度計數(shù)s＿count（A）、s＿count（B）和s＿count（A∪B），就能確定關(guān)聯(lián)規(guī)則A?B或B?A。因此，關(guān)聯(lián)規(guī)則的挖掘可以最終歸結(jié)為確定頻繁項集。

1.2 典型算法

關(guān)聯(lián)規(guī)則挖掘一般可以分為2個步驟：第一是找出所有的頻繁項集，第二是由頻繁項集確定關(guān)聯(lián)規(guī)則。典型的關(guān)聯(lián)規(guī)則挖掘算法基本上按照上述步驟進行挖掘。

1.2.1 Apriori算法

Apriori算法于1994年由Agrawal和R.Srikant提出，是一種多候選產(chǎn)生類布爾型關(guān)聯(lián)規(guī)則挖掘算法。由于該算法采用逐層搜索的迭代方法，每次找出一組頻繁項集就要對數(shù)據(jù)進行一次掃描，為了減少計算量，采用“頻繁項集的所有非空子集也是頻繁項集”這一先驗性質(zhì)壓縮掃描空間［2］。

1.2.2 FP－growth算法

由于Apriori算法需要產(chǎn)生大量的候選集以便從中尋找頻繁項集，并需要重復(fù)多次掃描數(shù)據(jù)庫，影響了算法的效率。針對這些問題，Jiawei Han于2000年提出頻繁模式增長（FP－growth）算法。該算法首先將數(shù)據(jù)集構(gòu)建成1棵頻繁模式樹（FP－tree），再基于頻繁模式樹對頻繁項集進行挖掘。該算法僅需對數(shù)據(jù)集進行2次完整的掃描，且可以明顯地壓縮所要搜素的數(shù)據(jù)集的大小，因此得到了廣泛應(yīng)用。1.2.3 序列規(guī)則挖掘算法

序列規(guī)則是在普通關(guān)聯(lián)規(guī)則基礎(chǔ)上添加時間信息，對于每一個時間段，都有在該時間段收集到的數(shù)據(jù)與之對應(yīng)，即有多少時間段就有多少數(shù)據(jù)集［3］。在序列規(guī)則挖掘中，時間段代替了普通關(guān)聯(lián)規(guī)則挖掘中的“購物籃”。典型的序列規(guī)則挖掘算法有基于FP－tree的高效數(shù)據(jù)流頻繁項集挖掘算法FPStream和針對滑動時間窗口的FTP－DS頻繁項集挖掘算法等［4］。

2 基于關(guān)聯(lián)規(guī)則的電子對抗目標(biāo)關(guān)聯(lián)分析

戰(zhàn)場上，電子對抗目標(biāo)之間、電子對抗目標(biāo)與武器系統(tǒng)及作戰(zhàn)行動之間的關(guān)聯(lián)關(guān)系表現(xiàn)為2種模式：

一是電子對抗目標(biāo)、武器系統(tǒng)、其它作戰(zhàn)力量同時活動，體現(xiàn)出協(xié)同關(guān)系，例如多部雷達同時對同一目標(biāo)進行探測；

二是電子對抗目標(biāo)、武器系統(tǒng)、作戰(zhàn)力量依次活動，體現(xiàn)出時序關(guān)系。例如防空導(dǎo)彈對敵機進行攔截時，預(yù)警探測雷達往往先于制導(dǎo)火控雷達工作。

對于這2種模式，分別對其采用靜態(tài)關(guān)聯(lián)規(guī)則挖掘算法和序列規(guī)則挖掘算法進行分析。

2.1 靜態(tài)關(guān)聯(lián)規(guī)則挖掘

針對電子對抗目標(biāo)、武器系統(tǒng)、作戰(zhàn)力量同時活動的情況，采用包含時間信息的FP－growth算法對其中的關(guān)聯(lián)規(guī)則進行挖掘。挖掘過程主要有以下步驟：

（1）數(shù)據(jù)處理

常規(guī)的FP－growth算法的數(shù)據(jù)中并沒有時間信息，為了體現(xiàn)目標(biāo)同時出現(xiàn)的情況，將常規(guī)算法中的事務(wù)T設(shè)為時間段，即用時間段代替“購物籃”，將時間段盡量設(shè)小，以體現(xiàn)目標(biāo)出現(xiàn)的同時性。

電子對抗偵察數(shù)據(jù)中重要的參數(shù)是目標(biāo)的出現(xiàn)和消失時間，對其進行關(guān)聯(lián)規(guī)則挖掘時只需關(guān)注目標(biāo)編號和目標(biāo)活動時間這2個參數(shù)。在此將偵察數(shù)據(jù)整理成表1所示的形式，即每個時間段及在該時間段內(nèi)出現(xiàn)的目標(biāo)編號。

表1的時間段設(shè)定成1 s。需要注意的是，目標(biāo)編號處不僅可以是電子對抗目標(biāo)，也可以是其他武器系統(tǒng)或作戰(zhàn)行動。

（2）確定初始頻繁項集

對數(shù)據(jù)集進行完整掃描，對目標(biāo)Ii出現(xiàn)的次數(shù)計數(shù)，確定支持度計數(shù)不小于最小支持度閾值的目標(biāo)集合L，并按支持度計數(shù)遞減排序。這里舉例設(shè)：

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

（3）構(gòu)造FP－tree

首先創(chuàng)造樹的根節(jié)點，記為n。對數(shù)據(jù)集進行掃描，創(chuàng)建樹的分枝。例如t1時間段包含I1、I2、I53項，其在L中的次序是I2、I1、I5。將I2作為根節(jié)點的子節(jié)點鏈接到n，I1鏈接到I2，I5鏈接到I1。t1時間段包含I2、I4項，其中I2鏈接到n，I4鏈接到I2。由于之前已經(jīng)創(chuàng)建節(jié)點I2，因此I4與t1時間段共享節(jié)點I2。依此法構(gòu)造FP－tree（如圖1所示），就可將頻繁項集挖掘問題轉(zhuǎn)化為FP－tree挖掘問題。

圖1 FP－tree

（4）挖掘頻繁項集

FP－tree的挖掘過程如下：首先由長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造其條件模式基，然后構(gòu)造其FP－tree并對其進行遞歸挖掘。

以上面構(gòu)建的FP－tree為例，首先考慮I5，I5出現(xiàn)在2個分支中，分別為路徑 〈I2，I1，I5：1〉和〈I2，I1，I3，I5：1〉。以I5為后綴，其前綴路徑為 〈I2，I1：1〉和〈I2，I1，I3：1〉構(gòu)成I5的條件模式基。使用上述條件模式基構(gòu)建 FP－tree，該樹僅具有 〈I2：2，I1：2〉1個分支，因為I3的支持度計數(shù)不滿足最小支持度閾值。因此，該路徑包含的頻繁模式為依此法對其它目標(biāo)進行頻繁項集挖掘，即可確定所有項集模式。

（5）確定關(guān)聯(lián)規(guī)則

挖掘出所有頻繁項集后，可以直接由其產(chǎn)生滿足最小支持度和置信度的強關(guān)聯(lián)規(guī)則：

首先，對于每個頻繁項集l產(chǎn)生其所有非空子集m。

其次，對于非空子集m，如果tmin＿c，則 產(chǎn) 生 關(guān) 聯(lián) 規(guī) 則m?（l－m）。 其 中s＿count（）為支持度計數(shù)，tmin＿c為最小置信度閾值。

（6）評估關(guān)聯(lián)規(guī)則

由于置信度有時不能完全反應(yīng)A、B相關(guān)性的實際強度，尤其是支持度閾值較低或關(guān)聯(lián)規(guī)則較長時。因此必須采用其它指標(biāo)對關(guān)聯(lián)規(guī)則進行評估，在這里選用提升度指標(biāo)：

若提升度小于1，表示A、B是負(fù)相關(guān)，而提升度大于1則表示A、B正相關(guān)。對前面挖掘出的關(guān)聯(lián)規(guī)則使用提升度進行評估后，即可得到最終有價值的關(guān)聯(lián)關(guān)系。

2.2 序列關(guān)聯(lián)規(guī)則挖掘

序列挖掘是對相對次序或時間出現(xiàn)頻率高的模式進行發(fā)現(xiàn)的方法。上述對于電子對抗目標(biāo)的靜態(tài)關(guān)聯(lián)規(guī)則挖掘雖然數(shù)據(jù)集包含時間信息，但在挖掘中沒有體現(xiàn)，挖掘的內(nèi)容是電子對抗目標(biāo)、武器系統(tǒng)、作戰(zhàn)單位同時活動時的關(guān)聯(lián)規(guī)則。序列關(guān)聯(lián)規(guī)則挖掘在上述方法的基礎(chǔ)上加上了時間因素，能夠反映電子對抗目標(biāo)、武器系統(tǒng)、作戰(zhàn)單位依次活動時的規(guī)律。

序列挖掘采用和關(guān)聯(lián)規(guī)則挖掘類似的過濾算法，所需的數(shù)據(jù)格式與靜態(tài)關(guān)聯(lián)規(guī)則挖掘算法相同，可采用R語言和Statistica等軟件進行實現(xiàn)。除支持度、置信度、提升度等指標(biāo)外，進行關(guān)聯(lián)模式挖掘需要注意的還有最大間隔指標(biāo)，該指標(biāo)表示關(guān)聯(lián)規(guī)則中2個目標(biāo)出現(xiàn)時間的最大間隔［5］。該值若設(shè)置過大，則難以體現(xiàn)目標(biāo)的關(guān)聯(lián)性。

3 關(guān)聯(lián)規(guī)則挖掘仿真與分析

3.1 基于FP－growth的靜態(tài)關(guān)聯(lián)規(guī)則挖掘的仿真

下面以2 220條模擬偵察數(shù)據(jù)進行仿真。該批數(shù)據(jù)中共有A、B、C、D、E5個電子對抗目標(biāo)，時間以1 s為1段，共計2 220 s，分別以支持度5%、10%、15%、20%，置信度60%進行挖掘，仿真發(fā)現(xiàn)支持度為10%時可以獲得一定數(shù)目有價值的關(guān)聯(lián)規(guī)則，剔除關(guān)聯(lián)規(guī)則中提升度不大于1的數(shù)據(jù)，得到關(guān)聯(lián)規(guī)則如表2所示。

表2 部分挖掘的關(guān)聯(lián)規(guī)則

從表格中可見，目標(biāo)B、C關(guān)聯(lián)性較強，目標(biāo)C出現(xiàn)時B出現(xiàn)的頻率以及B出現(xiàn)時C出現(xiàn)的支持度都達到了65%以上。另外，目標(biāo)A、B出現(xiàn)時目標(biāo)C出現(xiàn)的次數(shù)雖然不多，但置信度和提升度最高，可見該規(guī)則具有很高的參考價值，在偵察活動中若發(fā)現(xiàn)A、B目標(biāo)同時活動，應(yīng)重點關(guān)注C目標(biāo)。將目標(biāo)活動情況進行可視化顯示（如圖2所示），從中可以發(fā)現(xiàn)B、C目標(biāo)活動規(guī)律的關(guān)聯(lián)性十分明顯，但是對于其它關(guān)聯(lián)的活動規(guī)律難以通過人工判斷進行挖掘，而采用FP－growth靜態(tài)關(guān)聯(lián)規(guī)則挖掘算法就能很好地對其進行分析，體現(xiàn)出該方法的有效性。

圖2 目標(biāo)活動規(guī)律

3.2 序列關(guān)聯(lián)規(guī)則挖掘的仿真

仿真時使用R語言arulesSequences程序包對一批模擬偵察數(shù)據(jù)進行挖掘，數(shù)據(jù)集中有A、B、C、D、E、F、G、H共8個電子對抗目標(biāo)，每個時間段劃分為1 min，支持度分別設(shè)為5%、10%、15%、20%，置信度為60%，最大時間間隔為10 min，仿真發(fā)現(xiàn)支持度為20%時可以獲得一定數(shù)目有價值的關(guān)聯(lián)規(guī)則，如表3所示。

表3 部分挖掘的關(guān)聯(lián)規(guī)則

從表中結(jié)果可見，目標(biāo)F在目標(biāo)A之后10 min之內(nèi)出現(xiàn)的支持度達到了45%，在偵察中若發(fā)現(xiàn)目標(biāo)A活動，應(yīng)及時在目標(biāo)B的頻段對其進行控守。序列｛B，F(xiàn)｝、｛A，B｝支持度也較高，值得關(guān)注。

4 結(jié)束語

本文針對電子對抗目標(biāo)之間、電子對抗目標(biāo)與武器系統(tǒng)及作戰(zhàn)行動之間的2種關(guān)聯(lián)模式，分別采用了包含時間信息的FP－growth靜態(tài)關(guān)聯(lián)規(guī)則挖掘算法和序列關(guān)聯(lián)規(guī)則挖掘算法進行挖掘。仿真結(jié)果表明，通過上述方法可以揭示電子對抗目標(biāo)之間、電子對抗目標(biāo)與武器系統(tǒng)及作戰(zhàn)行動之間同時活動和依次活動2種關(guān)聯(lián)關(guān)系，能夠為電子對抗及其它作戰(zhàn)行動提供決策參考，具有一定的實用價值。

［1］Jiawei Han.Data Mining Concept and Techniques［M］.北京：機械工業(yè)出版社，2012.

［2］Rakesh Agrawal，Ramakrishnan Srikant.Mining sequential patterns［A］.Proceedings of The Eleventh International Conference on Data Engineering［C］.Washington D C，USA：IEEE Computer Society，1995：3－14.

［3］王星.大數(shù)據(jù)分析：方法與應(yīng)用［M］.北京：清華大學(xué)出版社，2013.

［4］馬青霞，李廣水，孫梅.頻繁模式挖掘進展及典型應(yīng)用［J］.計算機工程與應(yīng)用，2011，47（15）：138－142.

［5］閆明月，侯忠生，高穎.一種面向布爾時間序列的關(guān)聯(lián)規(guī)則挖掘算法［J］.控制與決策，2012（10）：1147－1151.