基于改进标签传播算法的目标分群方法

武海涛 刘洋 张永夫

1．国防大学联合作战学院北京100091

作战态势评估是对战场上敌我双方态势要素的定性及定量描述,并在此基础上动态分析、理解和预测战场情况和事件的过程,是指挥员科学、合理决策的基础. 美国心理学家Endsley 将态势评估分为态势察觉、态势理解和态势预测3 个阶段[1]. 目标分群是态势察觉阶段的重要内容, 它根据战场上获知的作战目标信息, 按照一定规则将作战目标抽象成能够一定程度上反映敌方作战体系结构和组织关系的目标群体[2]. 目标分群能够帮助指挥员理解敌方作战力量结构和所担负的作战任务, 为指挥员下一步分析敌方作战目标体系结构与运行规律, 并实施有效火力打击提供了重要支撑.

当前,目标分群方面的研究有不少,一些学者抽取目标的空间坐标、功能属性、敌我关系等信息,对作战目标进行相似度分析, 最后使用聚类算法对目标进行分群. Blackman 研究目标分群较早,在研究群体跟踪问题时,使用聚类分析将直接目标聚类,实现分群[3]. Bakert 等提取目标个体属性,基于贝叶斯网络进行证据推理, 得到多个互斥的作战目标集合[4].李伟楠等抽取目标空间坐标, 提出了一种基于流形距离的密度值搜索算法, 通过计算目标空间相似度实现将目标划分为若干作战空间群的目的[5]. 樊振华等为了解决目标分群中存在的类数未知与阈值欠缺的问题, 提出了一种基于改进空间划分的目标分群方法[6]. 张绪亮等提出一种改进的K-means 算法实现在敌方兵力集群相互交错时的目标分群[7]. 赵昀瑶提出了一种最大最小距离的聚类算法, 克服了目标分群中的类数未知以及聚类结果依赖初始重心的缺陷[8]. 赵鹏等提出了一种基于多Agent 的目标分群方法, 考虑了Agent 的地形、机动性能等因素,解决了在地形分割时出现的目标分群错误的问题[9].熊红强等使用高维空间的相似度函数对作战目标进行相似度分析,实现按层次分群的目的[10]. 毕鹏在深入分析层次聚类算法的基础上,将改进的Chameleon算法引入目标分群[11]. 这类方法具有分群精度高、可理解性强等特点, 但是难以反映目标体系结构以及各个目标之间的关系, 所以更多用于实现战术层面的目标分群.

另一些学者从目标体系的角度出发, 使用复杂网络方法构建目标体系网络, 通过社团检测算法对目标体系进行分群. 龙真真等基于复杂网络方法构建了目标体系网络, 使用复杂网络算法(Clausetnewman-moore, CNM)实现对目标体系网络的划分[12]. 李赟基于敌方目标体系网络模型,通过对网络拓扑结构的分析, 使用遗传算法计算网络节点的相似度,并分别实现了目标独立分群和重叠分群[13]. 这类方法借鉴了社交网络分析中的社区检测方法, 能够反映目标体系结构, 可以在目标属性获知较少的情况下对大规模目标进行分群, 但是这类方法的分群结果往往具有不小的误差.

标签传播算法属于基于复杂网络社团检测的半监督学习算法,该算法的时间复杂度接近线性、执行时间短、分类效果好,非常适合解决大规模目标分群问题.基于标签传播算法思想,提出一种基于改进标签传播算法的目标分群方法. 该方法综合考虑了目标在作战过程中的重要度、目标之间的物理空间关系以及信息关联等方面, 弥补了标准标签传播算法分群结果误差大的不足, 提高了目标分群结果的准确性和稳定性,实现了快速有效分群.

1 标签传播算法概述

1.1 标签传播算法

标签传播算法(Label Propagation Algorithm,LPA)由Raghavan 于2007年首先提出[14], 该算法的基本思想是: 标签信息可以通过邻居节点之间的连续传播在全局网络中得到更新, 因为社区内部联系紧密而社区之间关联稀疏, 所以标签更容易在联系紧密的社区内部传播, 标签经过多次迭代传播后不再发生变化,传播至此结束. 标签传播算法主要步骤如下:

1)节点标签初始化. 为每一个节点随机设置一个初始的唯一标签.

2)确定节点更新顺序. 随机对网络中所有节点进行排序,并按顺序更新节点标签.

3)节点标签传播.对于每个节点,将邻居节点中出现次数最多的标签作为该节点更新的标签. 若邻居节点中个数最多的标签不唯一时, 则从中随机选择一个节点标签进行更新.

4)标签传播迭代过程. 当所有节点标签不再改变时算法结束.

标签传播具体过程如图1 所示. 图中有1、2、3、4 个节点,随机赋予每个节点一个唯一的标签,分别为A、B、C、D.随机对4 个节点的标签进行排序,按顺序更新节点. 假设更新顺序为1、2、3、4,则先从节点1 开始更新,因为节点1 邻居节点2、3、4 中标签出现分别为B、C、D,都出现一次,所以随机选择标签D 作为节点1 的标签进行更新, 此时节点1的标签变为D.更新节点2 标签,因为此时节点2 的邻居节点中, 标签D 出现2 次, 次数最多, 所以将标签D 作为节点2 的标签进行更新. 按照此过程不断迭代,最终群体内部的节点都具有了相同的标签,图中所有节点的标签都更新为D, 每个节点的标签均不再改变,此时算法结束.

图1 标签传播具体过程图Fig.1 Label propagation process

1.2 标签传播算法的改进思路

标签传播算法时间复杂度接近线性、执行时间短、分类效果好,适合大型网络的社区检测, 得到了广泛的应用[15−16]. 但是标签传播算法仍然存在一些不足: 1)标签传播算法将网络中所有节点视为同质节点,所以在更新标签时采取随机更新策略,因为先更新的节点传播更快, 可能造成度数较小的节点影响度数较大的节点,使得算法需要更多次迭代,并可能导致分群结果的错误; 2)当邻居节点中个数最多的标签不唯一时, 算法随机选择其中一个标签进行更新, 这可能造成每一次分群结果都不相同且差异较大, 使得算法稳定性难以保证. 此外, 标签传播算法单纯依靠网络拓扑结构进行分群, 缺少对目标个体属性的分析, 在具体应用过程中分群结果具有不小的误差. 例如目标的群体类别除了与网络拓扑关系有关还与目标之间的物理空间距离有关, 作战目标在一定物理空间内距离相对越近, 越有可能同属一个群体.

所以算法的改进可以从以下几个方面入手:

1)目标体系网络构建. 目标体系网络有其自身特点. 目标体系网络中具有许多不同类型和功能的目标节点,它们在目标体系中发挥着不同的作用. 可以据此将目标节点划分侦察、决策和火力3 类. 根据作战体系的运行机制, 目标体系网络的中作战信息流转具有一定的规律.例如:雷达产生的探测信息会流向指挥所, 指挥所进行分析研判后会将决策指令传达到指定部队. 所以可以根据OODA 循环理论的思想,通过计算节点参与OODA 循环的占比衡量节点的重要度.

2)节点更新策略. 因为先更新的节点标签传播更快,如果随机对网络中的节点进行更新,可能会导致度数较小的节点影响度数较大的节点, 进而影响分群结果的准确性, 虽然在迭代的过程中会不断修正分群结果, 但是这些不必要的更新操作会耗费大量的运算时间,影响算法效率,尤其当网络规模非常大时这种影响更加明显. 根据目标体系网络的特点计算节点的重要度, 按照重要度由大到小对节点进行更新可以解决这个问题.

3)标签选择策略. 标签传播算法在标签更新过程时, 如果邻居节点中出现次数最大的标签不只一个, 待更新节点会从中随机选择一个标签作为自己的标签,具有一定的随机性,会导致算法结果的不稳定. 传统标签选择策略所想表达的是将对待更新节点影响最大的标签作为自己的标签来更新. 考虑到邻居节点中相同标签出现的次数越多、邻居节点与待更新节点相似度越高、邻居节点的重要度越大,标签的影响力就越大. 所以将邻居节点中相同标签出现的次数、邻居节点与待更新节点的相似度以及邻居节点的重要度结合起来形成标签影响力值, 根据标签影响力值选择标签.

2 基于改进标签传播算法的目标分群

2.1 目标体系网络构建

敌方目标体系具有复杂网络的特征, 可以使用复杂网络方法进行构建. 这方面的相关研究国内外已经有不少,具有代表性的有Cares 提出的信息化作战网络模型, 该模型使用网络邻接矩阵描述作战体系, 将实体抽象为目标、传感、决策、响应4 类[17];陈丽娜等在传统规则树形网络的基础上, 通过一定规则在节点之间随机建立连接, 生成网络化战争模型[18]; 刘忠等将节点抽象为侦察、指挥控制和火力3 类,构建了基于属性层和结构层相统一的超网络模型[19];国防大学胡晓峰等构建了由交战网、指控网、信息网组成的作战体系超网络模型[20].

本文借鉴前人对作战体系网络构建的经验, 对目标体系网络构建如下:

1)目标节点描述

根据作战目标本身属性以及其网络特征可以将其抽象为侦察节点Vs、决策节点Vd和火力节点Vf3 类体目标节点,形式化描述如下:

其中,UNIQUE_ID表示作战目标唯一序列识别;NAME表示作战目标名称;CATEGORY表示作战目标类别, 如雷达、机场以及地面部队等等;AT-TRIBUTE表示目标的其他属性集合, 包括目标的坐标位置、机动能力、作战能力等;TYPE_ID表示作战目标所属群体的标签.

2)边描述

边反映了作战目标间的信息交互, 形式化描述如下:

当E(Vi,Vj)= 1 时,节点i和节点j之间产生信息交互,E(Vi,Vj)= 0 时节点i和节点j之间无信息关联.

3)目标体系网络模型描述

根据前述内容, 可以将敌方目标体系网络形式化描述如下:

其中,V= {v1,v2,··· ,vn}为目标节点集合,n为节点数量,为边集合,表示节点i和节点j之间产生的信息关联情况.

2.2 节点更新策略

作战环理论是20 世纪70年代由美军上校Boyd提出的理论, 该理论将作战过程抽象简化为OODA循环过程[21],即侦察系统发现目标,将目标信息传送指挥中心,指挥中心经过分析后做出决策,命令打击单位对目标实施打击, 而后侦察系统对打击效果进行感知, 指挥中心据此作出新一轮决策. 打击链是OODA 作战循环在目标体系网络中的体现, 可以将其定义为:目标体系网络G(V,E)中由侦察节点Vs、决策节点Vd和火力节点Vf组成的能够执行完整作战任务的路径.

目标节点的重要度Ri可以用目标参与打击链的数量与网络中打击链总数量Nac的占比衡量,表示为:

打击链数量计算可以理解为图路径搜索问题,即从图中搜索所有符合条件的路径. 图路径搜索一般有广度优先搜索和深度优先搜索两种策略,其中,深度优先搜索可以用于解决打击链的计算问题, 其思想是从起始节点出发, 沿着图中的某一条路径一直探索,直到不能探索为止.当不能探索后沿着相反的方向寻找到新分支,然后沿着新路径继续探索,直到将图遍历完毕.

具体搜索过程为:如图2 所示,以节点1 为起始节点开始搜索. 首先从节点1 的邻居节点2 和3 中任选一个节点向下搜索, 假设此处选节点2; 然后继续从节点2 的邻居节点4 和5 中任选一个节点向下搜索,假设此处选节点4; 然后继续从节点4 的邻居节点7 和8 中任选一个节点向下搜索,假设此处选节点7; 搜索到节点7 时无法继续向下搜索, 则返回至节点4,发现尚未搜索的节点8,继续向下搜索;搜索到节点8 时无法继续向下搜索, 则返回节点4, 发现邻居节点已经搜索完毕, 则返回节点2, 发现尚未搜索的节点5,继续向下搜索. 重复以上过程直至将图搜索完毕,节点的搜索顺序为:1、2、4、7、8、5、3、6.

图2 深度优先搜索具体过程图Fig.2 Depth-firs search process

由打击链的定义可知, 打击链以侦察节点为起始节点, 中间包含若干决策节点, 终止于火力节点.所以可以根据打击链的特点对深度优先搜索算法进行改进, 通过判别条件过滤掉深度优先搜索算法中不符合打击链特征的路径,以提高算法的效率.下面给出基于深度优先搜索的打击链数量Nac算法的具体流程.

表1 基于深度优先搜索的打击链数量算法Table 1 A strike chains algorithm based on depth-firs search

根据以上算法得到打击链的数量, 进而可以计算每个节点的Ri值,按照Ri值由大到小对节点进行排序,最终确定目标节点的更新顺序.

2.3 标签选择策略

标签传播算法在标签更新过程时, 如果邻居节点中出现次数最大的标签不只一个, 待更新节点会从中随机选择一个标签作为自己的标签, 具有一定的随机性,会导致算法结果的不稳定. 标签选择策略所想表达的是将对待更新节点影响最大的标签作为自己的标签来更新. 考虑到邻居节点中相同标签出现的次数越多、邻居节点与待更新节点相似度越高、邻居节点的重要度越大,标签的影响力就越大.所以将邻居节点中相同标签出现的次数、邻居节点与待更新节点的相似度以及邻居节点的重要度结合起来计算标签影响力,可以表示如下:

其中,为待更新节点j的标签为l邻居节点的集合,Ri为节点重要度,St为节点与待更新节点的网络结构相似度,Sd为节点之间的空间距离相似度,w代表节点网络结构相似度和节点空间距离相似度在标签影响力中占的权重,一般可以取0.5.

网络结构相似性可以使用Jaccard 相似度进行计算:

其中,Ni、Nj分别表示节点i与节点j的邻居节点集合,表示节点i与节点j的邻居节点交集的节点数量,表示节点i与节点j的邻居节点并集的节点数量;Jaccard 值介于0-1 之间,该值越接近1, 表示节点vi和节点vj之间的网络结构相似度越高.

空间距离相似度可以用欧式距离表示, 通过隶属度函数对空间距离划分, 得到的空间距离相似度可以表示为:

其中,x,y,z为目标节点的空间坐标,d1,d2,d3为区分隶属度的阈值, 一般可以根据目标体系网络中节点之间的最大距离dmax以及目标的实际分布情况划分取值.Sd取0、0.25、0.75、1 分别表示两节点之间在物理空间的距离远、较远、较近、近.

综合上述内容可以算得待更新节点邻居节点的各个标签的影响力, 选择影响力最大的标签作为自己的标签来更新.

2.4 方法流程

基于改进标签传播算法的目标分群方法的具体步骤描述如表2 所示.

表2 基于改进标签传播算法的目标分群方法具体流程Table 2 The process of target clustering based on improved label propagation algorithm

2.5 目标分群结果评价

较为常用的一种复杂网络社团划分质量评价指标是由Newman 和Girvan 提出的模块度(Q modularity)[22],它可以在网络划分没有标准的结果时评价社团质量划分的优劣,模块度的取值在0 ～1,模块度的值越接近1,社团划分质量越高. 本文使用模块度来评价目标分群结果.模块度的计算表达式如下:

其中,Aij表示节点i和节点j的连边情况,如果节点i和节点j之间存在连边则Aij= 1, 否则Aij= 0,m表示网络中连边的总数,ki和kj表示节点i和节点j的度,δ(ci,cj)的取值为:如果点i和节点j在一个社团,即ci=cj时,δ(ci,cj)=1,否则δ(ci,cj)=0.

3 实验验证

3.1 实验说明

实验分析的主要目的是为了验证基于改进标签传播算法的目标分群方法的有效性. 文献[23-24]对基于复杂网络的作战体系网络的生成方法进行了描述, 其主要思想是首先根据军事指挥理论按照传统指挥关系构建树状作战体系网络, 然后根据联合作战的思想在同一指挥层级以及跨指挥层级之间建立指挥关系, 形成最终的作战体系网络. 根据文献[23-24]中作战体系网络的生成步骤, 结合文献[25]提出的防空系统模型构建了包含侦察、决策、火力3类节点的防空目标体系网络,如图3 所示. 该网络共包含341 个目标节点,其中,决策目标节点85 个(用圆形表示)、侦察节点126 个(用正方形表示)、火力节点130 个(用三角形表示), 包含指挥关系541 条.目标体系网络共包含4 个能够相对独立执行防空任务的目标群体(用虚线框区分),且按照群体内各个作战目标相对距离较近的原则部署.

图3 目标体系网络示意图Fig.3 Target system networks

3.2 实验结果分析

根据本文提出的基于改进标签传播算法的目标分群方法,计算各个目标节点的重要度,得到重要度排序节选如表3 所示.

表3 节点重要度排序表(节选)Table 3 Node importance ranking table(excerpt)

从表3 中可以看出, 决策节点参与打击链的占比较多、排序靠前, 代表其节点重要度较大,与实际情况相符合, 所以可以根据该节点重要度排序确定节点更新顺序.其次节点计算Jaccard 相似度与空间距离相似度,结合节点重要度得到节点影响力值,以此来选择标签进行更新, 经过4 次迭代后标签不再发生变化,得到目标分群结果如图4 所示.

从图4 中可以看出经过4 次迭代后,网络中仅存标签1、2、3、5,将目标体系网络划分为4 个相对独立的防空目标群体(用虚线框区分),结果与实际目标体系网络部署情况相符合,计算得到模块度Q 值为0.63,表明目标分群质量较好,因此,可以验证本文提出的基于改进标签传播算法的目标分群方法能够相对合理的对作战目标进行分群. 为了进一步验证算法的稳定性, 在相同的目标体系网络中分别使用本文所提目标分群方法和标准标签传播算法进行目标分群实验,得到200 次实验结果,其中,本文所提方法得到的分群结果一致,表明算法稳定性较好,而使用标准标签传播算法得到的结果各不相同, 稳定性相对较差,因此,可以验证本文提出的基于改进标签传播算法的目标分群方法具有较好的稳定性.

图4 改进标签传播算法目标分群结果示意图Fig.4 Target clustering results of improved label propagation algorithm

4 结论

根据目标体系的特点构建目标体系网络, 基于复杂网络社区探测的标签传播算法思想, 提出了一种基于改进标签传播算法的目标分群方法, 以防空目标体系网络为例, 对该方法的有效性和稳定性进行了实验验证. 该方法综合考虑了目标在作战过程中的重要度、目标之间的物理空间关系以及信息关联等方面, 弥补了现有研究中单纯依靠目标个体属性或网络体系结构的不足. 针对传统标签传播算法结果不稳定的问题, 从节点更新策略和标签选择策略两个方面对算法进行了改进, 实现对目标体系快速有效分群,为下一步目标选择提供支撑.