基于Apriori算法的戰(zhàn)術(shù)數(shù)據(jù)鏈層次關(guān)系挖掘

王 敏，李萬(wàn)春，扶彩霞，郭昱寧

(電子科技大學(xué)信息與通信工程學(xué)院，四川 成都 611731)

0 引言

戰(zhàn)術(shù)數(shù)據(jù)鏈?zhǔn)菬o(wú)線(xiàn)網(wǎng)絡(luò)通信在軍事方面的典型應(yīng)用，典型數(shù)據(jù)鏈如Link16。戰(zhàn)場(chǎng)環(huán)境下數(shù)據(jù)鏈網(wǎng)絡(luò)根據(jù)不同作戰(zhàn)任務(wù)和功能，形成一個(gè)層次化網(wǎng)絡(luò)，包括指揮平臺(tái)、作戰(zhàn)平臺(tái)、傳感探測(cè)平臺(tái)。數(shù)據(jù)鏈層次分析可以獲得區(qū)域內(nèi)各個(gè)電磁激勵(lì)源之間的多層次的網(wǎng)絡(luò)關(guān)系，從而掌握區(qū)域內(nèi)電磁綜合狀態(tài)、作戰(zhàn)進(jìn)程和效果評(píng)估，最終把握空間網(wǎng)絡(luò)中的目標(biāo)承載、通聯(lián)關(guān)系與拓?fù)浣Y(jié)構(gòu)。數(shù)據(jù)鏈網(wǎng)絡(luò)中的拓?fù)潢P(guān)系研究已經(jīng)成為網(wǎng)絡(luò)對(duì)抗領(lǐng)域的熱門(mén)研究方向之一。在實(shí)際場(chǎng)景中，由于各個(gè)輻射源的通信行為、不同區(qū)域不同輻射源協(xié)同作戰(zhàn)情況動(dòng)態(tài)變化，因此從一個(gè)無(wú)中心節(jié)點(diǎn)的數(shù)據(jù)鏈網(wǎng)絡(luò)中挖掘不同節(jié)點(diǎn)的層次關(guān)系就顯得十分重要[1-4]。

數(shù)據(jù)鏈網(wǎng)絡(luò)層次發(fā)現(xiàn)屬于數(shù)據(jù)挖掘領(lǐng)域。數(shù)據(jù)挖掘是從大量的、不完全、有噪聲、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中，提取隱含在其中、人們事先不知道的但又是有用的信息和知識(shí)的過(guò)程[5]。數(shù)據(jù)挖掘是一項(xiàng)交叉學(xué)科，目前主要作為一種新的商業(yè)信息處理技術(shù)，其主要特點(diǎn)是對(duì)商業(yè)數(shù)據(jù)庫(kù)中的大量業(yè)務(wù)數(shù)據(jù)進(jìn)行抽取、轉(zhuǎn)換、分析和其他模型化處理，從中提取輔助決策的關(guān)鍵性數(shù)據(jù)[6-8]。數(shù)據(jù)挖掘可以描述為：按照既定的業(yè)務(wù)目標(biāo)，對(duì)大量數(shù)據(jù)按照一定的算法進(jìn)行探索和分析，揭示隱藏的、未知的或驗(yàn)證已知的規(guī)律性。在目前關(guān)聯(lián)規(guī)則算法中最成熟的是Apriori算法[9-10]。

早期學(xué)者們對(duì)數(shù)據(jù)鏈拓?fù)潢P(guān)系的研究主要集中在移動(dòng)自組網(wǎng)(mobile ad hoc network，簡(jiǎn)稱(chēng)MANET)上，它是一種不依賴(lài)任何固定設(shè)施的無(wú)線(xiàn)網(wǎng)絡(luò)，且與戰(zhàn)術(shù)數(shù)據(jù)鏈網(wǎng)絡(luò)相比有較大區(qū)別，網(wǎng)絡(luò)拓?fù)洳捎霉?jié)點(diǎn)隨機(jī)分布的方式，沒(méi)有體現(xiàn)數(shù)據(jù)鏈網(wǎng)絡(luò)層次化的特點(diǎn)[11]。因此本文提出一種基于Apriori算法的網(wǎng)絡(luò)層次拓?fù)浒l(fā)現(xiàn)方法，該方法結(jié)合數(shù)據(jù)挖掘與聚類(lèi)方法，揭示隱含的數(shù)據(jù)鏈網(wǎng)絡(luò)層次關(guān)系，能夠體現(xiàn)戰(zhàn)場(chǎng)環(huán)境下節(jié)點(diǎn)層次化特征，實(shí)現(xiàn)在網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布情況下挖掘出不同節(jié)點(diǎn)之間的層次關(guān)系和關(guān)聯(lián)程度。

1 相關(guān)概念

Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。比如著名的購(gòu)物籃分析案例：70%購(gòu)買(mǎi)了牛奶的顧客將傾向于同時(shí)購(gòu)買(mǎi)面包；在超市中與尿布一起被購(gòu)買(mǎi)最多的商品竟然是啤酒。算法使用逐層搜索的迭代方法，“k-1項(xiàng)集”用于探索“k項(xiàng)集”，尋找最大項(xiàng)目集需要對(duì)數(shù)據(jù)集進(jìn)行多次迭代處理。該算法的核心思想是通過(guò)候選集生成和向下封閉檢測(cè)來(lái)挖掘頻繁項(xiàng)集。算法的相關(guān)概念如下。關(guān)聯(lián)規(guī)則:反應(yīng)一個(gè)事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果2個(gè)或者多個(gè)事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個(gè)事物就能夠通過(guò)其他事物預(yù)測(cè)到。事務(wù)：訪(fǎng)問(wèn)并可能更新數(shù)據(jù)庫(kù)中各種數(shù)據(jù)項(xiàng)的一個(gè)程序執(zhí)行單元。項(xiàng)集：項(xiàng)目的集合稱(chēng)為項(xiàng)目集合，簡(jiǎn)稱(chēng)為項(xiàng)集。其元素個(gè)數(shù)稱(chēng)為項(xiàng)集的長(zhǎng)度，長(zhǎng)度為k的項(xiàng)集稱(chēng)為k項(xiàng)集。支持度：項(xiàng)集中包含項(xiàng)目A∪B的百分比，支持度表示在規(guī)則中出現(xiàn)的頻度。support(A→B)=P(A∪B)

(1)

頻繁項(xiàng)集：支持度大于等于某個(gè)閾值的項(xiàng)集。置信度：數(shù)據(jù)集中包含A事務(wù)的同時(shí)包含B事務(wù)的百分比。置信度表示規(guī)則的強(qiáng)度。

confidence(A→B)=P(A∪B)/P(A)confidence(B→A)=P(A∪B)/P(B)

(2)

發(fā)現(xiàn)關(guān)聯(lián)規(guī)則要求項(xiàng)集必須滿(mǎn)足的最小支持閾值，稱(chēng)為項(xiàng)集的最小支持度，記為supmin。支持度大于或等于supmin的項(xiàng)集稱(chēng)為頻繁項(xiàng)集，簡(jiǎn)稱(chēng)頻繁集，反之稱(chēng)為非頻繁集。通常k項(xiàng)集如果滿(mǎn)足supmin，稱(chēng)為k頻繁集，記為L(zhǎng)k。強(qiáng)關(guān)聯(lián)規(guī)則：如果規(guī)則R滿(mǎn)足：

support(R)≥supminconfidence(R)≥confmin

(3)

則稱(chēng)關(guān)聯(lián)規(guī)則R為強(qiáng)關(guān)聯(lián)規(guī)則，否則稱(chēng)關(guān)聯(lián)規(guī)則R為弱關(guān)聯(lián)規(guī)則。在挖掘關(guān)聯(lián)規(guī)則時(shí)，產(chǎn)生的關(guān)聯(lián)規(guī)則要經(jīng)過(guò)supmin和confmin的衡量。另外，Apriori算法的2個(gè)重要性質(zhì)如下：性質(zhì)1：頻繁項(xiàng)集的子集必為頻繁項(xiàng)集。性質(zhì)2：非頻繁項(xiàng)集的超集一定是非頻繁的。

2 基于Apriori算法的數(shù)據(jù)鏈層次關(guān)系挖掘算法

根據(jù)Link16通信協(xié)議，所有節(jié)點(diǎn)在所屬的時(shí)隙內(nèi)發(fā)送消息，任何節(jié)點(diǎn)都可以在不發(fā)送消息的時(shí)隙內(nèi)接收消息。那么就導(dǎo)致大量的未知信息，接收消息節(jié)點(diǎn)未知使得發(fā)現(xiàn)數(shù)據(jù)鏈通連關(guān)系的難度變大。再者，Link16屬于無(wú)中心網(wǎng)絡(luò)，相比于Link11有中心網(wǎng)絡(luò)，Link16節(jié)點(diǎn)的發(fā)送順序沒(méi)有規(guī)律性，帶有很大的隨機(jī)性。針對(duì)戰(zhàn)術(shù)數(shù)據(jù)鏈偵察消息量大、節(jié)點(diǎn)隨機(jī)分布的特點(diǎn)，在偵察信息先驗(yàn)知識(shí)基礎(chǔ)上，本文利用數(shù)據(jù)挖掘算法的思想，把對(duì)應(yīng)的層次拓?fù)洚?dāng)做頻繁項(xiàng)集來(lái)進(jìn)行關(guān)聯(lián)規(guī)則挖掘。如果節(jié)點(diǎn)在Link16的協(xié)議下組網(wǎng)，高級(jí)指揮平臺(tái)發(fā)送命令控制類(lèi)消息給次級(jí)指揮平臺(tái)，次級(jí)指揮平臺(tái)會(huì)在一定概率Psend下作出反應(yīng)，可能會(huì)發(fā)送消息給次級(jí)平臺(tái)，也可能會(huì)發(fā)送應(yīng)答消息。那么消息可能會(huì)沿著拓?fù)鋱D中的邊向下傳遞，在時(shí)間上形成屬于該集群的消息序列集合。由于消息的應(yīng)答與傳遞存在一定的概率Psend，導(dǎo)致了在層次關(guān)系上最接近的節(jié)點(diǎn)的關(guān)聯(lián)程度support最高，跨級(jí)之間的關(guān)聯(lián)度support隨之減小，因此support大的節(jié)點(diǎn)具有層次關(guān)系。結(jié)合流量統(tǒng)計(jì)數(shù)據(jù)等先驗(yàn)知識(shí)，先選取流量最大的節(jié)點(diǎn)對(duì)消息序列做分割；將每個(gè)時(shí)間段內(nèi)不同平臺(tái)的消息作為Apriori算法中每次交易項(xiàng)目集中的項(xiàng)目；分割所得的消息集合作為項(xiàng)目集，2種關(guān)系對(duì)比如表1所示。

表1 Apriori算法與Link16數(shù)據(jù)鏈術(shù)語(yǔ)對(duì)比

定義節(jié)點(diǎn)之間的關(guān)聯(lián)規(guī)則：設(shè)最小支持度為support(R)，最小置信度為confidence(R)，當(dāng)節(jié)點(diǎn)之間的消息序列集合的最小支持度和最小置信度滿(mǎn)足：

support(R)≥supminconfidence(R)≥confmin

(4)

認(rèn)為節(jié)點(diǎn)之間一定存在從屬關(guān)系?；谝陨厦枋?，數(shù)據(jù)鏈網(wǎng)絡(luò)層次關(guān)系挖掘算法描述如下：算法名稱(chēng)：基于Apriori算法的數(shù)據(jù)鏈層次關(guān)系挖掘算法。輸入：最小支持度，最小置信度和仿真消息序列。輸出：數(shù)據(jù)鏈網(wǎng)絡(luò)的層次拓?fù)潢P(guān)系。Step 1: 在多層次的網(wǎng)絡(luò)中，為每個(gè)節(jié)點(diǎn)分配時(shí)隙，并設(shè)定最小支持度和最小置信度；Step 2: 統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)發(fā)送消息的頻率，將頻率大于等于最小支持度的節(jié)點(diǎn)構(gòu)成頻繁k-2項(xiàng)集；Step 3: 對(duì)獲得的頻繁k-1項(xiàng)集中節(jié)點(diǎn)集合進(jìn)行掃描計(jì)數(shù)，統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)集合發(fā)送消息的頻率，將頻率不小于最小支持度的節(jié)點(diǎn)構(gòu)成頻繁k-2項(xiàng)集；Step4: 重復(fù)上述過(guò)程，直到獲得頻繁k維項(xiàng)目集；Step 5:根據(jù)獲得的k維頻繁項(xiàng)目集，計(jì)算置信度，根據(jù)置信度得出節(jié)點(diǎn)之間的從屬關(guān)系，獲得不同節(jié)點(diǎn)之間的層次關(guān)系。Step 2的具體步驟為：從多個(gè)節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)的時(shí)隙作為分隔條件，從而統(tǒng)計(jì)出各個(gè)節(jié)點(diǎn)的發(fā)送消息的頻率，再將頻率不小于最小支持度的節(jié)點(diǎn)構(gòu)成頻繁k-1項(xiàng)集。

圖1 節(jié)點(diǎn)層次關(guān)系拓?fù)鋱D

圖2 8個(gè)平臺(tái)的消息時(shí)序圖

3 算法仿真

在實(shí)際環(huán)境中，一般一個(gè)作戰(zhàn)集群都會(huì)有一個(gè)最高的指揮節(jié)點(diǎn)，向下繼續(xù)拓展會(huì)有次級(jí)指揮節(jié)點(diǎn)直到普通的作戰(zhàn)單元。如圖1所示為8個(gè)節(jié)點(diǎn)的層次拓?fù)鋱D。為了評(píng)估方法性能，設(shè)定如下簡(jiǎn)化場(chǎng)景進(jìn)行仿真。在某確定的Link16數(shù)據(jù)鏈網(wǎng)絡(luò)中，I={A,B,C,D,E,F,G,H}為該網(wǎng)絡(luò)的節(jié)點(diǎn)，其中A是一級(jí)指揮平臺(tái)，B是次級(jí)指揮平臺(tái)，C,D是無(wú)人機(jī)偵察平臺(tái)，E,F,G,H是作戰(zhàn)平臺(tái)。下面將通過(guò)仿真驗(yàn)證本文算法得到的層次拓?fù)渑c設(shè)定網(wǎng)絡(luò)完全一致。根據(jù)Link16數(shù)據(jù)鏈時(shí)隙分配規(guī)則，給圖1中的8個(gè)節(jié)點(diǎn)分配時(shí)隙。并假設(shè)設(shè)置Psend=0.8，supmin=0.6，confmin=0.6，8個(gè)節(jié)點(diǎn)的消息序列服從泊松分布，根據(jù)戰(zhàn)術(shù)數(shù)據(jù)鏈分配規(guī)則，給8個(gè)節(jié)點(diǎn)分配時(shí)隙，8個(gè)節(jié)點(diǎn)的消息時(shí)序如圖2所示。用A節(jié)點(diǎn)的消息作為分隔條件，就可以得到如表2所示的數(shù)據(jù)表。

表2 數(shù)據(jù)表

圖3 各個(gè)平臺(tái)的支持度

圖4 候選頻繁k-2項(xiàng)集支持度

圖5 候選頻繁k-2項(xiàng)集置信度

所以可以認(rèn)為該數(shù)據(jù)鏈的層次拓?fù)渲杏蠥→B→C和A→B→D的關(guān)系。因?yàn)閷哟伪容^低的節(jié)點(diǎn)在以A時(shí)隙為分割點(diǎn)的情況下不滿(mǎn)足：

support(R)≥supmin

圖6 平臺(tái)B-H的消息時(shí)序圖

圖7 頻繁k-1項(xiàng)集的支持度

圖8 頻繁k-2項(xiàng)集的支持度

所以此時(shí)要想獲得{{E}，{F}，{G}，{H}}的層次關(guān)系，就需要使分割點(diǎn)的層級(jí)級(jí)別降低并去除比新分割節(jié)點(diǎn)層次高的節(jié)點(diǎn)。例如，再選擇B節(jié)點(diǎn)的時(shí)隙作為時(shí)隙分割點(diǎn)，那么就需要先去除A節(jié)點(diǎn)的時(shí)隙信息，避免增加挑選頻繁項(xiàng)集的復(fù)雜度。以B的時(shí)隙作為時(shí)隙分割點(diǎn)，得到剩余節(jié)點(diǎn)的時(shí)隙序列，如圖6所示。得到頻繁k-1項(xiàng)集的支持度，如圖7所示。由于所有平臺(tái)的支持度都滿(mǎn)足最小支持度的要求，所以繼續(xù)求解頻繁k-2項(xiàng)集的支持度，由于從第一次求解過(guò)程中已經(jīng)求得節(jié)點(diǎn)B和節(jié)點(diǎn)CD的關(guān)系，所以在本次迭代過(guò)程中可以不求B節(jié)點(diǎn)和節(jié)點(diǎn)CD的關(guān)系。得到的曲線(xiàn)圖如圖8所示。從圖8中可以看出{CE}，{CF}，{DG}，{DH}的支持度滿(mǎn)足條件，那么將{{CE}，{CF}，{DG}，{DH}}作為候選頻繁k-2項(xiàng)集。得到的置信度如表3所示。

表3 置信度

從表3中可以看出置信度滿(mǎn)足條件，即存在層次關(guān)系{C→E}，{C→F}，{D→G}，{D→H}?？偨Y(jié)以上過(guò)程，通過(guò)該算法迭代得到層次拓?fù)潢P(guān)系為{A→B→C→E}、{A→B→C→F}、{A→B→D→G}、{A→B→D→H}，與設(shè)定的網(wǎng)絡(luò)完全一致。從上述過(guò)程也可以看出，在層次拓?fù)鋱D中層次越高，k-1、k-2項(xiàng)集支持度越高；層次拓?fù)渲?個(gè)節(jié)點(diǎn)越相近，置信度越高；置信度反映了關(guān)聯(lián)規(guī)則的強(qiáng)弱，置信度越高從屬關(guān)系越明顯。當(dāng)2個(gè)節(jié)點(diǎn)跨層次時(shí)(如AC)，置信度反而下降。當(dāng)節(jié)點(diǎn)在特定協(xié)議下組網(wǎng)，那么消息可能會(huì)沿著拓?fù)鋱D的邊向下傳遞，在時(shí)間上形成屬于該集群的消息序列集合。由于消息的應(yīng)答和傳遞存在一定的概率P，導(dǎo)致了在層次關(guān)系上最接近的節(jié)點(diǎn)的關(guān)聯(lián)程度最高，跨級(jí)之間的關(guān)聯(lián)度隨之減小，這符合實(shí)際作戰(zhàn)情況。

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

本文提出一種基于Apriori算法的層次拓?fù)渫诰蚍椒?，解決了數(shù)據(jù)鏈網(wǎng)絡(luò)在無(wú)中心節(jié)點(diǎn)的情況下準(zhǔn)確找到節(jié)點(diǎn)的層次拓?fù)潢P(guān)系的途徑。通過(guò)迭代得到k項(xiàng)集，找出滿(mǎn)足支持度和置信度的候選集，同時(shí)滿(mǎn)足最小支持度和最小置信度的候選集為頻繁項(xiàng)集，找出頻繁項(xiàng)集的節(jié)點(diǎn)之間的從屬關(guān)系。仿真實(shí)驗(yàn)表明，該算法能有效挖掘數(shù)據(jù)鏈網(wǎng)絡(luò)的層次關(guān)系。該算法的下一步研究方向，是適應(yīng)大型的、實(shí)際的非合作戰(zhàn)場(chǎng)網(wǎng)絡(luò)。■