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

李 政，祝 利，韋 偉

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

0 引 言

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

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

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

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

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

1.1 相關(guān)概念

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

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

1.1.2 支持度與置信度

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

1.1.3 頻繁項(xiàng)集

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

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

根據(jù)式（1），A?B的支持度與置信度很容易從A、B和A∪B的支持度計(jì)數(shù)中得出，也就是說(shuō)一旦確定A、B和A∪B的支持度計(jì)數(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é)為確定頻繁項(xiàng)集。

1.2 典型算法

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

1.2.1 Apriori算法

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

1.2.2 FP－growth算法

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）確定初始頻繁項(xiàng)集

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

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

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

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

圖1 FP－tree

（4）挖掘頻繁項(xiàng)集

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

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

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

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

首先，對(duì)于每個(gè)頻繁項(xiàng)集l產(chǎn)生其所有非空子集m。

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

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

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

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

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

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

序列挖掘采用和關(guān)聯(lián)規(guī)則挖掘類似的過(guò)濾算法，所需的數(shù)據(jù)格式與靜態(tài)關(guān)聯(lián)規(guī)則挖掘算法相同，可采用R語(yǔ)言和Statistica等軟件進(jìn)行實(shí)現(xiàn)。除支持度、置信度、提升度等指標(biāo)外，進(jìn)行關(guān)聯(lián)模式挖掘需要注意的還有最大間隔指標(biāo)，該指標(biāo)表示關(guān)聯(lián)規(guī)則中2個(gè)目標(biāo)出現(xiàn)時(shí)間的最大間隔［5］。該值若設(shè)置過(guò)大，則難以體現(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ù)進(jìn)行仿真。該批數(shù)據(jù)中共有A、B、C、D、E5個(gè)電子對(duì)抗目標(biāo)，時(shí)間以1 s為1段，共計(jì)2 220 s，分別以支持度5%、10%、15%、20%，置信度60%進(jìn)行挖掘，仿真發(fā)現(xiàn)支持度為10%時(shí)可以獲得一定數(shù)目有價(jià)值的關(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ī)則

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

［1］Jiawei Han.Data Mining Concept and Techniques［M］.北京：機(jī)械工業(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］馬青霞，李廣水，孫梅.頻繁模式挖掘進(jìn)展及典型應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（15）：138－142.

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