基于Apriori算法的戰術數據鏈層次關系挖掘

王 敏，李萬春，扶彩霞，郭昱寧

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

0 引言

戰術數據鏈是無線網絡通信在軍事方面的典型應用，典型數據鏈如Link16。戰場環境下數據鏈網絡根據不同作戰任務和功能，形成一個層次化網絡，包括指揮平臺、作戰平臺、傳感探測平臺。數據鏈層次分析可以獲得區域內各個電磁激勵源之間的多層次的網絡關系，從而掌握區域內電磁綜合狀態、作戰進程和效果評估，最終把握空間網絡中的目標承載、通聯關系與拓撲結構。數據鏈網絡中的拓撲關系研究已經成為網絡對抗領域的熱門研究方向之一。在實際場景中，由于各個輻射源的通信行為、不同區域不同輻射源協同作戰情況動態變化，因此從一個無中心節點的數據鏈網絡中挖掘不同節點的層次關系就顯得十分重要[1-4]。

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

早期學者們對數據鏈拓撲關系的研究主要集中在移動自組網(mobile ad hoc network，簡稱MANET)上，它是一種不依賴任何固定設施的無線網絡，且與戰術數據鏈網絡相比有較大區別，網絡拓撲采用節點隨機分布的方式，沒有體現數據鏈網絡層次化的特點[11]。因此本文提出一種基于Apriori算法的網絡層次拓撲發現方法，該方法結合數據挖掘與聚類方法，揭示隱含的數據鏈網絡層次關系，能夠體現戰場環境下節點層次化特征，實現在網絡節點隨機分布情況下挖掘出不同節點之間的層次關系和關聯程度。

1 相關概念

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

(1)

頻繁項集：支持度大于等于某個閾值的項集。置信度：數據集中包含A事務的同時包含B事務的百分比。置信度表示規則的強度。

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

(2)

發現關聯規則要求項集必須滿足的最小支持閾值，稱為項集的最小支持度，記為supmin。支持度大于或等于supmin的項集稱為頻繁項集，簡稱頻繁集，反之稱為非頻繁集。通常k項集如果滿足supmin，稱為k頻繁集，記為Lk。強關聯規則：如果規則R滿足：

support(R)≥supminconfidence(R)≥confmin

(3)

則稱關聯規則R為強關聯規則，否則稱關聯規則R為弱關聯規則。在挖掘關聯規則時，產生的關聯規則要經過supmin和confmin的衡量。另外，Apriori算法的2個重要性質如下：性質1：頻繁項集的子集必為頻繁項集。性質2：非頻繁項集的超集一定是非頻繁的。

2 基于Apriori算法的數據鏈層次關系挖掘算法

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

表1 Apriori算法與Link16數據鏈術語對比

定義節點之間的關聯規則：設最小支持度為support(R)，最小置信度為confidence(R)，當節點之間的消息序列集合的最小支持度和最小置信度滿足：

support(R)≥supminconfidence(R)≥confmin

(4)

認為節點之間一定存在從屬關系?；谝陨厦枋?，數據鏈網絡層次關系挖掘算法描述如下：算法名稱：基于Apriori算法的數據鏈層次關系挖掘算法。輸入：最小支持度，最小置信度和仿真消息序列。輸出：數據鏈網絡的層次拓撲關系。Step 1: 在多層次的網絡中，為每個節點分配時隙，并設定最小支持度和最小置信度；Step 2: 統計每個節點發送消息的頻率，將頻率大于等于最小支持度的節點構成頻繁k-2項集；Step 3: 對獲得的頻繁k-1項集中節點集合進行掃描計數，統計每個節點集合發送消息的頻率，將頻率不小于最小支持度的節點構成頻繁k-2項集；Step4: 重復上述過程，直到獲得頻繁k維項目集；Step 5:根據獲得的k維頻繁項目集，計算置信度，根據置信度得出節點之間的從屬關系，獲得不同節點之間的層次關系。Step 2的具體步驟為：從多個節點中選擇一個節點的時隙作為分隔條件，從而統計出各個節點的發送消息的頻率，再將頻率不小于最小支持度的節點構成頻繁k-1項集。

圖1 節點層次關系拓撲圖

圖2 8個平臺的消息時序圖

3 算法仿真

在實際環境中，一般一個作戰集群都會有一個最高的指揮節點，向下繼續拓展會有次級指揮節點直到普通的作戰單元。如圖1所示為8個節點的層次拓撲圖。為了評估方法性能，設定如下簡化場景進行仿真。在某確定的Link16數據鏈網絡中，I={A,B,C,D,E,F,G,H}為該網絡的節點，其中A是一級指揮平臺，B是次級指揮平臺，C,D是無人機偵察平臺，E,F,G,H是作戰平臺。下面將通過仿真驗證本文算法得到的層次拓撲與設定網絡完全一致。根據Link16數據鏈時隙分配規則，給圖1中的8個節點分配時隙。并假設設置Psend=0.8，supmin=0.6，confmin=0.6，8個節點的消息序列服從泊松分布，根據戰術數據鏈分配規則，給8個節點分配時隙，8個節點的消息時序如圖2所示。用A節點的消息作為分隔條件，就可以得到如表2所示的數據表。

表2 數據表

圖3 各個平臺的支持度

圖4 候選頻繁k-2項集支持度

圖5 候選頻繁k-2項集置信度

所以可以認為該數據鏈的層次拓撲中有A→B→C和A→B→D的關系。因為層次比較低的節點在以A時隙為分割點的情況下不滿足：

support(R)≥supmin

圖6 平臺B-H的消息時序圖

圖7 頻繁k-1項集的支持度

圖8 頻繁k-2項集的支持度

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

表3 置信度

從表3中可以看出置信度滿足條件，即存在層次關系{C→E}，{C→F}，{D→G}，{D→H}。總結以上過程，通過該算法迭代得到層次拓撲關系為{A→B→C→E}、{A→B→C→F}、{A→B→D→G}、{A→B→D→H}，與設定的網絡完全一致。從上述過程也可以看出，在層次拓撲圖中層次越高，k-1、k-2項集支持度越高；層次拓撲中2個節點越相近，置信度越高；置信度反映了關聯規則的強弱，置信度越高從屬關系越明顯。當2個節點跨層次時(如AC)，置信度反而下降。當節點在特定協議下組網，那么消息可能會沿著拓撲圖的邊向下傳遞，在時間上形成屬于該集群的消息序列集合。由于消息的應答和傳遞存在一定的概率P，導致了在層次關系上最接近的節點的關聯程度最高，跨級之間的關聯度隨之減小，這符合實際作戰情況。

4 結束語

本文提出一種基于Apriori算法的層次拓撲挖掘方法，解決了數據鏈網絡在無中心節點的情況下準確找到節點的層次拓撲關系的途徑。通過迭代得到k項集，找出滿足支持度和置信度的候選集，同時滿足最小支持度和最小置信度的候選集為頻繁項集，找出頻繁項集的節點之間的從屬關系。仿真實驗表明，該算法能有效挖掘數據鏈網絡的層次關系。該算法的下一步研究方向，是適應大型的、實際的非合作戰場網絡?！?/p>