2. 航空工业自控所, 陕西 西安 710065
态势估计通过感知战场环境和敌我目标信息, 推理敌方意图, 预测敌方行动, 从而辅助指挥人员做出正确决策, 奠定战场胜局[1]。然而, 现代战争中存在数量众多、种类繁杂、属性多样的敌我战场目标, 这些都导致了信息量激增, 从而对态势估计提出了挑战。而目标分群能够根据目标自身属性、目标间的空间关系, 将目标分类合并为互不相交的空间群体, 大大减少冗余信息, 从而降低态势估计难度, 提高决策效率。
战场目标分群问题具备以下特点:①空间群数量未知。由于战场敌方目标部署情况未知, 而我方目标部署又可能针对敌方发生改变, 因而敌我双方目标分群的空间群数量是未知的。②目标属性多样。目标具备多种属性, 如位置、速度、航向等, 使得目标分群面对的数据往往是高维的。③目标分群动态性。战场战况瞬息万变, 目标的状态也在时刻改变, 从而导致目标所属空间群的改变。目标分群问题不单是对应某一时刻的静态分群, 还是对应一段时间甚至整场战争的动态分群。
针对战场目标分群问题, 文献[2-3]对目标属性如位置、速度等建立相似度函数, 然后构建空间相似度矩阵来进行目标分群。然而, 多个相似度函数中引入了相似度计算阈值, 空间相似度矩阵中又引入了相似度判定阈值。过多的阈值, 会因为某些阈值取值不当而影响算法效果。文献[4-6]将目标分群看作聚类问题, 分别利用k-means算法和chameleon算法进行求解。然而, 文献[4]在确定空间群个数时, 需要人为指定合理分群数的上限。但是在一些复杂战况下, 指挥人员可能无法指定该上限; 文献[5-6]则是在合并相邻群时, 必须人为指定相对互连性和相对近似性所需要满足的阈值, 但文中并未给出指定的依据或方法。最后, 上述文献都只是对某时刻战场目标进行静态分群, 并未进行动态分群仿真。
本文结合目标分群问题的特点, 提出了一种基于M-CFSFDP算法的目标分群方法来将战场目标划分为空间群。首先, 建立战场目标分群问题模型, 并将其转化为数据集聚类问题。其次, 目标分群的特点要求聚类算法能够在类别数量未知的前提下, 解决高维数据的动态聚类问题。CFSFDP算法[7]能够自动搜索与发现聚类中心, 且可以对高维数据进行聚类, 并且已经被用于目标分群问题中[8], 故选择CFSFDP算法来实现聚类。再次, 针对CFSFDP算法中的欧氏距离无法正确衡量目标之间相似性的问题, 提出引入流形距离将CFSFDP改进为M-CFSFDP。最后, 应用M-CFSFDP算法对人工数据集和UCI数据集进行聚类仿真实验, 并对战场目标进行静态与动态目标分群仿真实验, 仿真结果证明了M-CFSFDP算法的正确性与可行性。
1 问题描述目标分群的输入为战场中的各目标的状态信息, 如位置、速度、航向等。某时刻战场目标集合可表示为:
(1) |
式中, Oi表示一个目标, n为目标的数量。对于一个目标Oi, 其状态属性可表示为一个多元组:
(2) |
式中, xij表示第i个目标的第j个属性值, m为属性的数量, 即一个目标对应m维空间的一个点, T对应m维空间一个具有n个点的点集。
本文所需解决的问题, 就是根据战场中所有目标的自身属性值, 以及目标之间的时空关系, 将它们分解到多个互不相交的空间群中, 即
(3) |
式中, ψi表示一个空间群, N为空间群的数量。每个空间群由至少一个目标组成。
2 基于流形距离的CFSFDP算法 2.1 CFSFDP算法CFSFDP算法针对聚类中心提出了2点假设:①聚类中心的局部密度大于其近邻点; ②聚类中心距高于其局部密度的点较远。这2点假设实际上描述了聚类中心所具备的2条特性:自身局部密度大, 以及聚类中心之间的距离远。而非聚类中心的样本点则只具备其中一个特性, 或者都不具备。
1) 局部密度
对于数据集X=[x1, x2, …xn]中的一个点xi, 其局部密度定义如(4)式所示:
(4) |
式中,dij为数据点xi与xj之间的欧氏距离, dc为截断距离, χ(·)为核函数。核函数可选择3种形态[9]:
(1) 截断核
(5) |
(2) 高斯核
(6) |
(3) 指数核
(7) |
由此可见, 以数据点xi为中心, 以截断距离dc为半径所划出的一个区域, 该区域在二维或三维空间对应一个圆形或球体, 在高维空间对应一个超球体。核函数则决定了xi以外的点处于该区域内的概率。局部密度实际上是概率的和, 表示了点xi周围近邻点的密集程度。
2) 高密度近邻点距离
高密度近邻点距离定义如下:
(8) |
对于点xi, xj是所有局部密度大于该点且与该点距离最近的点。xi与xj之间的欧氏距离即为高密度近邻点距离。如果xi是局部密度最大的点, 其高密度近邻点距离为:
(9) |
3) 截断距离的求取
在求取局部密度时, 关键问题就是截断距离dc的取值。文献[7]仅给出dc的经验性取值范围。然而该范围过大, 需要人工筛选, 不利于算法的自动化; 与此同时, 对于某些数据集, 合适的dc甚至不在该范围内。文献[10-11]中介绍了数据场的概念并应用在数据聚类中, 文献[12]则在数据场的基础上利用信息熵给出了自动求取dc的方法。
该方法将数据集等价为一个数据场, 将数据点的局部密度ρi等价为该点在数据场中的势能函数φi, 其定义如下
(10) |
式中, 影响因子σ即为截断距离dc。
然后, 利用信息熵H来度量整个数据集的不确定性, 其定义如(11)式所示
(11) |
信息熵与数据集的分布相对应, 熵值越小, 不确定性越小, 数据集越符合其真实的分布方式。当σ从0到+∞增加时, H先从Hmax=log(n)减小, 在某个σ处达到最小值, 然后又增大到Hmax。在H达到最小值时对应的σ, 即为最优dc。
综上所述, CFSFDP首先计算各个数据点的局部密度ρi以及高密度近邻点距离δi, 然后构建ρ-δ决策图来快速寻找和发现聚类中心, 最后指定剩余点的类别, 其类别与高于该点局部密度且距该点最近的点相同[13]。
2.2 基于流形距离的CFSFDP算法改进 2.2.1 CFSFDP算法的缺陷CFSFDP算法搜寻聚类中心时主要依靠ρi和δi, 而δi的求取则依赖于ρi。因此, ρi的正确求解直接决定了CFSFDP算法聚类结果的正确性。在求取ρi时, 其核心为首先利用数据点xi与xj间的欧氏距离来衡量xi与xj的相似性, 然后通过核函数将相似性转化为ρi。因此, 数据点间的欧氏距离越小, 相似性越大, ρi越接近1;反之, 欧氏距离越大, 相似性越小, ρi越接近0。然而, 对于很多数据集, 尤其是高维数据, 欧氏距离却无法正确衡量数据点之间的相似性。某数据集一部分数据空间分布如图 1所示:
由图 1可知, a与c属于同一类, 而b属于另一类。然而, a与b之间的欧氏距离dab为0.209, a与c之间的欧氏距离dac为0.458, 且dab < dac。这时依据欧氏距离的大小, 会得出a与b更加相似的结论, 继而令a与b划分在同一类的概率大于a与c划分在同一类的概率。实际上, 许多数据集都存在如图 1中的问题。如果对这些数据集使用CFSFDP算法进行聚类, 会因为欧氏距离无法正确衡量数据点间的相似性, 使得ρi与δi的结果不符合实际情况, 从而导致聚类中心的搜索偏差, 其余数据点的归类错误, 最终获得不理想甚至是完全错误的聚类结果。
究其根本原因, 是由于数据集的样本点在空间内不再是简单且彼此隔离的球状簇集, 而是形成一个个彼此相连的复杂结构, 统称为流形[14]。针对流形结构明显的数据, 数据点之间的最短距离并非欧氏距离, 而是测地距离, 即流形距离。此时, 只有采用流形距离才能正确衡量数据点之间的相似性。
2.2.2 M-CFSFDP空间上xi与xj之间的流形上的线段长度定义如下[15]:
(12) |
式中, dl(xi, xj)为xi与xj之间的欧氏距离, ρ>1为伸缩因子, 此处可取e3。
将数据点xi与xj看作是图G=(V, E)的顶点, 令p={p1, p2, …pl}∈V表示图上一条连接点p1与pl的路径, 其中边(pk, pk+1)∈E, 1≤k≤l-1。令Pij表示连接数据xi与xj的所有路径集合, 则xi与xj之间的流形距离定义如下[15]
(13) |
式中, L(a, b)表示两点间流形上的线段长度。
由流形距离的定义可以看出, 它不像欧氏距离直接计算两点间的空间距离, 而是首先将数据点作为图的顶点, 将近邻点连线作为图的边, 然后从起点开始搜索最短边来寻找下一个最近邻点直至终点为止, 最后计算所有最短边流形上的线段长度并加和便得到流形距离。收缩因子使得流形距离相比欧氏距离, 放大了位于不同流形的点间距离, 缩小了相同流形内的点间距离, 如图 1所示。
a与b之间的流形距离D(a, b)为0.872 4, a与c之间的流形距离D(a, c)为a至c共16个最短边的集合(最短边流形距离见表 1), 其大小为0.106 1。此时, 流形距离可以正确衡量数据点间相似性。
(pk, pk+1) | D(pk, pk+1) |
(a, d) | 0.002 9 |
(d, e) | 0.014 3 |
(e, f) | 0.007 8 |
(f, g) | 0.008 8 |
(g, h) | 0.006 3 |
(h, i) | 0.000 7 |
(i, j) | 0.004 2 |
(j, k) | 0.000 03 |
(k, l) | 0.000 7 |
(l, m) | 0.005 2 |
(m, n) | 0.006 0 |
(n, o) | 0.016 9 |
(o, p) | 0.003 5 |
(p, q) | 0.005 7 |
(q, r) | 0.001 8 |
(r, c) | 0.021 3 |
综上所述, M-CFSFDP算法首先计算数据点之间的流形距离, 然后在流形距离的基础上计算所有数据点的ρi和δi, 再然后建立ρ-δ决策图来搜索聚类中心, 最后指定剩余数据点类别, 获得聚类结果。
下面给出M-CFSFDP的算法流程:
输入:待聚类数据集
输出:聚类结果
1) 数据标准化。采用min-max标准化将各维数据映射到[0, 1]之间。
2) 计算流形距离。首先计算数据点之间的欧式距离; 然后指定近邻点个数n, 一般可取3~5;再然后将每个数据点与其近邻点连接生成图; 最后依据(12)~(13)式计算各数据点之间的流形距离。
3) 求取截断距离。依据(11)式计算信息熵H, 取H最小时对应的影响因子σ为截断距离dc。
4) 计算局部密度ρi和高密度近邻点距离δi。计算方法依据公式(7)~(9)。
5) 寻找聚类中心。构建ρ-δ决策图来寻找聚类中心。
6) 非中心数据点归类。归类原则为:对于数据点xi, 寻找高于该点局部密度的所有点, 选择其中距该点最近的点xj, 则xi与xj的类别一致。
3 仿真实验 3.1 人工数据集和UCI数据集聚类本文同时利用CFSFDP算法和M-CFSFDP算法, 来对人工数据集和UCI标准数据库中的数据集进行聚类实验, 以期验证M-CFSFDP算法的正确有效, 且聚类结果优于CFSFDP算法。实验数据基本信息如表 2所示。图 2~5是人工数据集的仿真结果。
数据集 | 数据个数 | 数据维数 | 类别数 |
threecircles | 299 | 2 | 3 |
lineblobs | 266 | 2 | 3 |
jain | 373 | 2 | 2 |
spiral | 312 | 2 | 3 |
iris | 150 | 4 | 3 |
seeds | 210 | 7 | 3 |
wine | 178 | 13 | 3 |
图 2~4表示4种人工数据集聚类结果, 其中a)、b)分别表示CFSFDP算法和M-CFSFDP算法的ρ-δ决策图, 用于确定聚类中心; c)、d)分别表示2种算法的聚类结果。对于图 2数据集, 图 2a)显示CFSFDP算法只能寻找到一个正确的聚类中心, 无法准确寻找到其余2个聚类中心, 从而导致图 2c)聚类结果完全错误; 而图 2b)显示M-CFSFDP算法可以准确搜寻3个聚类中心, 图 2d)聚类结果也将所有数据正确分为3类。对于图 3、4数据集, 虽然CFSFDP算法可以找到聚类中心, 然而由于欧氏距离无法正确衡量数据点间的相似性, 使得数据点的ρi和δi计算结果出现偏差, 从而导致部分数据点的聚类错误, 图 3c)和图 4c)都显示有数据点被错分。而流形距离可以正确衡量数据点间的相似性, 故图 3d)和图 4d)中M-CFSFDP算法聚类结果未出现错分数据点。对于图 5数据集, 决策图与聚类结果表明, CFSFDP能够正确聚类时, M-CFSFDP也能够正确聚类。此外, 对比上述所有数据集的决策图, 发现M-CFSFDP能够更加明确地反映出聚类中心。正是由于流形距离的作用, 使得M-CFSFDP搜索聚类中心的能力以及聚类效果都优于CFSFDP。
对于高维数据, 本文以UCI数据库中的wine数据集为例, 对比2种的聚类结果, 如图 6所示:
由图 6a)可知, CFSFDP算法只能找到2个聚类中心, 而图 6b)中M-CFSFDP算法能够正确搜索3个聚类中心。而图中ρi很小而δi很大的点为单独孤立点, 故不算作聚类中心。由于UCI数据集都为高维数据, 聚类结果不便以图形表示, 故表 3给出聚类结果对比。
由表 3可知, 对于iris数据集, M-CFSFDP能够显著提高聚类正确率; 对于wine数据集, 原方法甚至无法准确搜索聚类中心, 确定聚类类别数。M-CFSFDP不但能准确搜索聚类中心, 而且能够得到较为理想的聚类结果。对于seeds数据集, M-CFSFDP算法的聚类正确率仅是略微提高, 这是由于数据集自身特性导致, 说明该数据集仅通过CFSFDP算法就可以获得较高的聚类正确率。尽管聚类正确率提高有限, M-CFSFDP依然得到了较高的正确率, 且优于CFSFDP算法。通过对人工数据集与UCI数据集的聚类仿真结果, 可以充分证明M-CFSFDP算法的正确有效, 且优于CFSFDP算法。
3.2 战场目标分群在实际战场中, 目标不断运动, 其状态不断变化, 从而导致目标之间所形成的空间群也会有所改变。一般来说, 战场目标群体会存在诸如分裂、合并、单独成群等情况, 这对于目标分群方法提出了更高的要求。下面通过一组战场我方目标的任务执行过程, 来验证本文目标分群方法的正确性、有效性与可行性。
我方目标任务执行过程如图 7所示:
1) 起始时刻, 目标1~3向北偏东30°方向飞行, 执行侦查任务; 目标4~7向北偏东60°方向飞行, 执行侦查任务; 目标8~10由北向西逆时针执行巡逻任务。
2) 当到达t1时刻, 目标3, 5, 6接到突发任务安排, 目标3与目标1, 2分裂并单独成群, 目标5, 6与目标4, 7分裂为2个空间群。其余目标仍执行原任务。
3) 当到达t2时刻, 目标3与目标5, 6合并成一个群, 并开始向远处执行攻击任务。其余目标仍执行原任务。
下面应用本文提出的目标分群方法, 来对上述任务执行过程中的所有目标进行分群。
1) 某时刻目标静态分群结果
t时刻目标状态信息如表 4所示:
目标号 | x/m | y/m | z/m | ϕ/(°) | V/(m·s-1) |
1 | 9 145 | 17 109 | 5 500 | 30 | 850 |
2 | 9 441 | 16 625 | 5 560 | 30 | 860 |
3 | 13 758 | 11 403 | 4 549 | 50 | 1 020 |
4 | 18 110 | 7 229 | 4 500 | 70 | 950 |
5 | 15 220 | 12 345 | 4 650 | 30 | 1 000 |
6 | 15 190 | 11 465 | 4 665 | 30 | 1 000 |
7 | 18 892 | 6 755 | 4 440 | 70 | 954 |
8 | 3 714 | 6 777 | 8 000 | 56 | 370 |
9 | 3 303 | 6 566 | 7 985 | 56 | 360 |
10 | 4 126 | 7 039 | 8 015 | 56 | 380 |
其中, x, y, z表示目标的位置信息; ϕ表示目标的航迹方位角; V表示目标的速度。
由图 8~10可知, t时刻目标被分为5个空间群, 如表 5:
由图 8~10可知, 如果仅仅参考目标之间的位置, 可以明显得出目标1, 2, 目标4, 7以及目标8, 9, 10各自成为一个空间群。然而, 本文目标分群方法将目标3, 5, 6分为2个空间群, 则证明了该方法在分群时能够结合目标各属性, 切合实际地正确分群。图 11表示各目标由起始时刻到达该时刻的航迹, 航迹末端为该时刻目标所处位置。
结合图 11可知:目标1, 2维持原航线, 为空间群1;而目标3已经分裂出去并单独成群, 为空间群4;目标4~7此时也已分裂为2个群体, 目标5, 6为空间群2, 目标5, 7为空间群4;目标8~10为空间群3。
(2) 全时段目标分群结果
任务执行全时段目标分群结果如下所示:
由图 12可知, 在起始时刻, 目标1~3属于空间群1, 目标4~7属于空间群2, 目标8~10属于空间群3;经过一段时间后, 目标3与目标1, 2分裂并单独成群, 为空间群4。目标4, 7与目标5, 6分裂, 为空间群5;最后, 目标3与目标4, 7又合并成空间群4。
图 13以全程航迹的形式表现了目标分群结果。上述分群结果与设计的任务执行过程吻合, 并且对于目标分裂、合并以及单独成群等特殊情况都可以正确分群, 充分说明了本文目标分群方法对于动态分群的正确性与可行性。
4 结论本文针对战场目标分群问题, 提出了一种基于M-CFSFDP算法的目标分群方法。该方法利用流形距离替代欧氏距离以期正确衡量目标之间的相似度, 并在此基础上对CFSFDP算法进行改进。通过对人工数据集和UCI数据集进行仿真, 验证了M-CFSFDP算法搜索聚类中心与聚类效果均优于CFSFDP算法; 同时应用该方法对战场目标进行静态与动态分群, 仿真结果表明该方法能够在起始空间群数量未知的前提下, 对具有高维属性的战场目标既可以进行某时刻的静态空间分群, 又可以获得整个任务执行过程的正确分群结果。
[1] | Endsley M R. Toward a Theory of Situation Awareness in Dynamic Systems[J]. Human Factors the Journal of the Human Factors & Ergonomics Society, 1995, 37(1): 32-64. |
[2] |
林洪文, 杨绍清. 一种空中目标空间分群算法[J]. 舰船电子工程, 2012, 32(6): 43-45.
Lin Hongwen, Yang Shaoqing. Space Aggregation Method of Aerial Targets[J]. Ship Electronic Engineering, 2012, 32(6): 43-45. (in Chinese) DOI:10.3969/j.issn.1627-9730.2012.06.015 |
[3] |
王新为, 杨绍清, 林洪文, 等. 海战场目标分群技术研究[J]. 舰船电子工程, 2013, 33(11): 25-27, 111.
Wang Xinwei, Yang Shaoqing, Lin Hongwen, et al. Target Clustering Technology in Sea Battlefield[J]. Ship Electronic Engineering, 2013, 33(11): 25-27, 111. (in Chinese) DOI:10.3969/j.issn.1627-9730.2013.11.009 |
[4] |
张绪亮, 张宏军, 綦秀利, 等. 基于改进K-means算法的陆战场机动目标分群方法[J]. 信息技术, 2016(3): 128-131.
Zhang Xuliang, Zhang Hongjun, Qi Xiuli, et al. A Clustering Method of Land Battlefield Maneuvering Targets Based on Improved K-Means Algorithm[J]. Information Technology, 2016(3): 128-131. (in Chinese) |
[5] |
黄雷, 郭雷. 一种面向态势估计中分群问题的聚类方法[J]. 计算机应用, 2006, 26(5): 1109-1110, 1129.
Huang Lei, Guo Lei. Method of Clustering about Situation Assessment[J]. Journal of Computer Applications, 2006, 26(5): 1109-1110, 1129. (in Chinese) |
[6] |
袁德平, 郑娟毅, 史浩山, 等. 一种多作战编队下的目标编群算法[J]. 计算机科学, 2016, 43(2): 235-238, 244.
Yuan Deping, Zheng Juanyi, Shi Haoshan, et al. Target Grouping Algorithm Based on Multiple Combat Formations[J]. Computer Science, 2016, 43(2): 235-238, 244. (in Chinese) |
[7] | Rodriguez A, Laio A. Machine learning Clustering by Fast Search and Find of Density Peaks[J]. Science, 2014, 344(6191): 1492-1496. DOI:10.1126/science.1242072 |
[8] |
邢晨.飞行态势感知中目标分群方法研究[D].天津: 中国民航大学, 2017 Xing Chen. Research on the Method of Object Grouping in Flight Situation Awareness[D]. Tianjin, Civil Aviation University of China, 2017 http://cdmd.cnki.com.cn/Article/CDMD-10059-1017720404.htm |
[9] |
淦文燕, 刘冲. 一种改进的搜索密度峰值的聚类算法[J]. 智能系统学报, 2017, 12(2): 229-236.
Gan Wenyan, Liu Chong. An Improved Clustering Algorithm that Searches and Finds Density Peaks[J]. CAAI Transactions on Intelligent Systems, 2017, 12(2): 229-236. (in Chinese) |
[10] | Li D, Wang S, Gan W, et al. Data Field for Hierarchical Clustering[J]. International Journal of Data Warehousing & Mining, 2011, 7(4): 43-63. |
[11] | Wang S, Li Y, Wang D. Data Field for Mining Big Data[J]. Geo-Spatial Information Science, 2016, 19(2): 106-118. DOI:10.1080/10095020.2016.1179896 |
[12] | Wang S, Wang D, Li C, et al. Clustering by Fast Search and Find of Density Peaks with Data Field[J]. Chinese Journal of Electronics, 2016, 25(3): 397-402. DOI:10.1049/cje.2016.05.001 |
[13] |
戴娇, 张明新, 郑金龙, 等. 基于密度峰值的快速聚类算法优化[J]. 计算机工程与设计, 2016, 37(11): 2979-2984.
Dai Jiao, Zhang Mingxin, Zheng Jinlong, et al. Optimization of Fast Clustering Algorithm Based on Density Peaks[J]. Computer Engineering and Design, 2016, 37(11): 2979-2984. (in Chinese) |
[14] | Joshua B Tenenbaum, Vin de Silva, John C Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction[J]. Science, 2000, 290(5500): 2319-2323. DOI:10.1126/science.290.5500.2319 |
[15] |
马萌.基于流形距离的聚类算法研究及其应用[D].西安: 西安电子科技大学, 2010 Ma Meng, The Study and the Application of Clustering Algorithm based on Manifold Distance[D]. Xi'an, Xidian University, 2010(in Chinese) http://cdmd.cnki.com.cn/Article/CDMD-10701-2010128478.htm |
2. AVIC Xi'an Flight Automatic Control Research Institute, Xi'an 710065, China