基于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项集，找出满足支持度和置信度的候选集，同时满足最小支持度和最小置信度的候选集为频繁项集，找出频繁项集的节点之间的从属关系。仿真实验表明，该算法能有效挖掘数据链网络的层次关系。该算法的下一步研究方向，是适应大型的、实际的非合作战场网络。■