模型聚合解聚的智能触发机制

宁进 陈雷霆 周川 张磊

摘 要：针对现有模型聚合解聚（AD）触发机制人工依赖性高、频繁聚合解聚的问题，提出了一种基于关注域的多实体时序离群点检测算法的智能触发机制。首先，基于关注近邻划分关注域;然后，计算关注域中实体的k距离离群值，得到关注域的离群值;最后，结合一种基于最强关注域阈值判定方法，构建聚合解聚触发机制。在真实数据集上的实验结果表明，与传统的单实体时序离群点检测算法相比，所提算法在指标Precision、Recall和综合指标 F1-score上均提升了10个百分点以上，不仅能及时地判断聚合解聚操作的触发时机，而且能使得仿真系统智能地检测出发生突发情况的仿真实体，满足了多分辨率建模的要求。

关键词：聚合解聚;触发机制;时序离群点检测;k距离;多分辨率建模

中图分类号： TP181

文献标志码：A

Abstract： Aiming at high manual dependence and frequent Aggregation and Disaggregation （AD） of existing model AD trigger mechanisms， an intelligent trigger mechanism based on focus-area multi-entity temporal outlier detection algorithm was proposed. Firstly， the focus-areas were divided based on attention neighbors. Secondly， the outlier score of focus-area was obtained by calculating the k-distance outlier score of entities in a focus-area. Finally， a trigger mechanism for AD was constructed based on strongest-focus-area threshold decision method. The experimental results on real dataset show that， compared with the traditional single-entity temporal outlier detection algorithms， the proposed algorithm improves the performance of Precision， Recall and F1-score by more than 10 percentage points. The proposed algorithm can not only judge the trigger time of the AD operation in time， but also enable the simulation system to intelligently detect the simulation entities with emergency situation and meet the requirements of multi-resolution modeling.

Key words： aggregation and disaggregation; trigger mechanism; temporal outlier detection; k-distance; multi-resolution modeling

0 引言

模型聚合解聚（Aggregation and Disaggregation， AD）[1-3]是多分辨率建模的关键技术之一，在军事仿真系统、列车控制系统和大型游戏等应用中发挥重要作用，其主要思想是：通过聚合操作，实现由高分辨率模型向低分辨率模型的轉换;通过解聚操作，实现由低分辨率模型向高分辨率模型的转换;通过模型聚合解聚的触发机制，管理聚合解聚操作，最终实现多分辨建模。

聚合解聚的触发机制决定了仿真系统何时进行聚合操作，何时进行解聚操作，以及哪些模型需要进行解聚操作。然而，目前聚合解聚触发机制主要依靠专家来制定[4]，具体方法是：事先制定聚合解聚触发规则，并在实际过程中靠专家（例如军事指挥员、导播）实时指导聚合解聚触发过程。这种人工操作的方式很容易错过重大激战，造成不可挽回的指挥混乱，且受限于频繁聚合解聚和可移植性差等问题。尤其是，在现代对战仿真系统中，传统的触发机制呈现出明显的复杂性特点，严重影响了仿真的效率。模型聚合解聚的触发机制需要满足专家的关注度的变化和突发状况，根据这个特点，本文以多分辨率建模中的模型聚合解聚技术为背景，以多分辨率模型中的仿真实体（也称作仿真对象，例如战场中的飞机、大型游戏中的角色）为研究的基本单位，首次将时序离群点检测技术应用在聚合解聚技术中。

模型聚合解聚触发时机具有以下特性：1）时变多实体。仿真实体位置不断改变导致解聚关系也在不断变化，使得解聚实体的选择更加复杂。2）状态复杂性。仿真实体状态在时刻改变，无明显周期特性，无法提前对所有情况制定规则。3）实时性要求。需要保证及时为专家提供重要信息，更好地发挥仿真系统的作用。根据模型聚合解聚触发时机的特点，将时序离群点检测算法引入模型聚合解聚触发机制中。时序离群点检测[5-7]是一种检测时序数据中与大多数数据点不一致的少部分“离群点、异常点、新颖点”的算法，根据离群点的离群模式，可以分为离群序列检测[8-13]和离群点检测[14-15]。Zheng等[11]将统计方法和模糊集技术协同结合，以解决时序离群点检测技术中的控制限值和多参数问题，并且显著提高了检测的效果;但是这种方法属于事后检测，不具有实时性。Zeng等[12]通过对动态变量和权重的线性组合来动态设置基于自回归积分滑动平均模型（AutoregRessive Integrated Moving Average model， ARIMA）时序离群点检测中的警戒阈值，提高了检测准确率;但这种方法适用于具有周期特性的数据集，受限于本文仿真实体的状态复杂性。Na等[13]改进了基于局部离群指数（Local Outlier Factor， LOF）的时序离群点检测算法中的历史数据抽样技术，并且提出了检测序列离群点的策略，该算法具有内存空间占用少、执行效率高的优点;但是这种方法只针对了单实体时序离群点检测。Wang等[14]针对组合时序序列的离群点检测问题，提出了一种新的基于分离度模型的自适应区间构造方法，减弱了传统算法的参数依赖问题，具有较好的检测效果;但是这种方法依赖全局数据，不符合模型聚合解聚的实时性要求。

如果直接将已有的时序离群点算法应用于模型聚合解聚的触发机制中，仍然会有时变多实体问题，更会带来检测效果差、频繁聚合解聚的问题。针对这些问题，本文改进基于距离的单实体时序离群点检测算法，提出了基于关注域的多实体时序离群点检测算法。首先，提出了关注域的概念以及基于互近邻的关注域划分方法;然后利用k距离计算关注域内实体的离群值，得出关注域的离群值。该算法解决了已有时序离群点检测算法对模型聚合解聚的触发机制不适用的问题，在真实数据集上具有更好的检测效果。最后，构建了聚合解聚触发机制，主要包括关注域划分、基于关注域的时序离群点检测、聚合解聚时机判定。该机制填补了目前模型聚合解聚技术中的非人工技术的空缺，也为多分辨率建模提供了一种有效的保证。

1 基于关注近邻的关注域划分算法

1.1 相关概念

为了更方便地引入关注域的概念，以二维对战仿真中的多分辨率建模为背景，二维对战是指仿真过程中的仿真单位处于同一水平面，比较典型的是陆地对战仿真。首先，作如下规定：

1）E={E1，E2，…，En}：表示二维对战仿真中低分辨率下的仿真实体（后面简称为实体）的集合，集合大小为n。

2）Ei，Ej：E中的任意两个实体。

3）Ei.x：表示实体Ei的位置横坐标。

4）Ei.y：表示实体Ei的位置纵坐标。

5）顯示窗口：二维对战仿真中低分辨率下需要进行解聚操作的一个位置区域，可以根据实际解聚要求来设置显示窗口的尺寸。

6）wide：表示显示窗口的长度。

7）high：表示显示窗口的宽度。

1.2 关注域

定义1  关注近邻（Focus Nearest Neighbor， FNN）。实体Ei的关注近邻（FNN）是指在仿真实体集合E中，与实体Ei可在同一显示窗口中的实体的集合，定义如下：

1.3 关注域划分算法

基于互近邻的关注域划分算法的伪代码如算法1所示，算法中符号描述为：neighbor_List标识每个点的关注近邻;sortedIndicies表示每个点的关注近邻大小;FS_list存储搜索到的关注域;FS_flag标记每个点是否已经被安排簇。算法从关注近邻最小的点开始划分，满足关注域条件（定义3）即完成该点的划分，直到所有点都被安排了关注域。

2 基于关注域的多实体时序离群点检测算法

2.1 相关描述

2.3 模型聚合解聚智能触发机制流程

本文所提出的模型聚合解聚智能触发机制适用于大部分多分辨率建模场景中，如图2所示，整个机制包含输入层、算法层和判定层。输入层接收战场上所有仿真实体的实时数据、实时位置直接用作划分新的关注域，并和其他属性一起进行标准化处理，得到每个实体的实时特征向量。算法层在前面部分已详细介绍，经过本文算法模块的处理，得到仿真系统中实时关注域离群值。

判定模块判定最强关注域的离群值是否超过阈值解聚α：如果超过阈值，且当前仿真系统为非该区域的高分辨率状态，那么判定为需要解聚操作，将关注域中的仿真实体进行解聚;如果未超过阈值，且当前仿真系统为高分辨率状态，那么判定为需要聚合操作。α的取值越大，则系统判定的离群状态越少，解聚操作越少;反之，判定的离群状态越多，解聚操作越多。实际应用中可根据聚合解聚操作的频繁要求来调整α的取值。本文智能触发机制中，采用一元正态分布方法[16]来确定α的值：设置为历史关注域离群值的均值，上浮3倍方差。这种阈值判定方式相比传统的基于规则的方式更加简单有效，避免了频繁聚合解聚的问题。最强关注域的计算和解聚操作的判定函数描述如下。

3 实验结果与分析

3.1 数据集描述及评价方法

为了验证本文方法的有效性，使用2018年英雄联盟职业联赛（League of Legends Pro League， LPL）春季赛季后赛RNG vs. WE[17]的对战数据进行实验。该数据源是一场时长38min的比赛数据，共包含10个对战实体（英雄），从第20min开始到第30min，每隔5s记录每个实体的位置、血量百分比和蓝量百分比，并且用比赛导播标注的放大区域来标注解聚操作的标签。

3.2 效果对比及复杂度分析

将本文算法与已有的单实体时序离群点检测算法[18-19]：基于距离、基于密度、一类支持向量机（oneclass-Support Vector Machine， oneclass-SVM）作对比。其中，基于距离和基于密度的方法需要预先设置参数k的值，本实验采用文献[20]中的算法来设置参数k，这是一种通过寻找数据集的稳定状态来选择k值的方法，具有较好的效果。

4 结语

针对传统的模型聚合解聚触发机制的人工依赖性高、频繁聚合解聚和可移植性差的问题，本文提出了一种智能触发机制。实验结果显示，所提出的基于关注域的时序离群点检测算法和聚合解聚判定策略较为成功地解决了模型聚合解聚触发时机问题。此外，相较于传统的单实体时序离群点检测算法，本文方法有效地提高了多实体时序离群点检测的性能。在一些大型应用场景中，包含更大的实体数量、更复杂的实体状态，传统的时序离群点检测算法将会面临巨大的挑战。之后的工作中，需要针对这些挑战进一步研究，尤其是需研究将基于深度学习的时序离群点检测算法应用到该机制中。

参考文献 （References）

[1] 李明忠，毕长剑，刘小荷，等.空军作战仿真模型聚合与解聚研究[J].系统仿真学报，2008，20（14）：3679-3684.（LI M Z， BI C J， LIU X H， et al. Research on model aggregation and disaggregation for air force combat simulation [J]. Journal of System Simulation， 2008， 20（14）： 3679-3684.）

[2] 李鳳霞，卢兆涵，雷正朝，等.基于队形的聚合解聚方法研究[J].系统仿真学报，2013，25（10）：2308-2313.（LI F X， LU Z H， LEI Z Z， et al. Aggregation and disaggregation methods research based on formation [J]. Journal of System Simulation， 2013， 25（10）： 2308-2313.）

[3] GOU C X， CAI B G. Multi-resolution entities aggregation and disaggregation method for train control system modeling and simulation based on HLA [C]// ITSC 2014： Proceedings of the 2014 17th International IEEE Conference on Intelligent Transportation Systems. Piscataway， NJ： IEEE， 2014： 2367-2372.

[4] 朱敏洁，周深根.多分辨率模型转换的触发机制[J].指挥控制与仿真，2015，37（5）：44-47.（ZHU M J， ZHOU S G. Multi-resolution combat model triggering mechanism [J]. Command Control & Simulation， 2015， 37（5）： 44-47.）

[5] AGGARWAL C C. Outlier Analysis [M]. 2nd ed. Berlin： Springer， 2016： 286.

[6] KATHAREIOS G， ANGHEL A， MATE A， et al. Catch it if you can： real-time network anomaly detection with low false alarm rates [C]// ICMLA 2017： Proceedings of the 16th IEEE International Conference on Machine Learning and Applications. Piscataway， NJ： IEEE， 2017： 924-929.

[7] BENKABOU S E， BENABDESLEM K， CANITIA B. Unsupervised outlier detection for time series by entropy and dynamic time warping [J]. Knowledge and Information Systems， 2018， 54（2）： 463-486.

[8] YANG C L， LIAO W J. Adjacent Mean Difference （AMD） method for dynamic segmentation in time series anomaly detection [C]// SII 2017： Proceedings of the 2017 IEEE/SICE International Symposium on System Integration. Piscataway， NJ： IEEE， 2017： 241-246.

[9] KHA N H， ANH D T. From cluster-based outlier detection to time series discord discovery [M]// LI X L， CAO T， LIM E P， et al. Trends and Applications in Knowledge Discovery and Data Mining， LNCS 9441. Cham： Springer， 2015： 16-28.

[10] REN H R， LIU M M， LI Z W， et al. A piecewise aggregate pattern representation approach for anomaly detection in time series [J]. Knowledge-Based Systems， 2017， 135： 29-39.

[11] ZHENG D Q， LI F H， ZHAO T J. Self-adaptive statistical process control for anomaly detection in time series [J]. Expert Systems with Applications， 2016， 57： 324-336.

[12] ZENG J， ZHANG L， SHI G T， et al. An ARIMA based real-time monitoring and warning algorithm for the anomaly detection [C]// ICPADS 2017： Proceedings of the 2017 IEEE 23rd International Conference on Parallel and Distributed Systems. Piscataway， NJ： IEEE， 2017： 469-476.

[13] NA G S， KIM D H， YU H. DILOF： effective and memory efficient local outlier detection in data streams [C]// KDD 2018： Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York： ACM， 2018： 1993-2002.

[14] WANG L， XU L Y， XUE Y L， et al. Group behavior time series anomaly detection in specific network space based on separation degree [J]. Cluster Computing， 2016， 19（3）： 1201-1210.

[15] AHMAD S， LAVIN A， PURDY S， et al. Unsupervised real-time anomaly detection for streaming data [J]. Neurocomputing， 2017， 262： 134-147.

[16] HAN J， KAMBER M， PEI J. Data Mining： Concepts and Techniques [M]. 3rd ed. San Francisco， CA： Morgan Kaufmann Publishers， 2011： 351-376.

[17] LPL職业联赛.2018LPL春季赛季后赛 RNG vs WE 第二局[EB/OL].[2018-09-12]. https：//v.qq.com/x/cover/191162cgjvuzbxm/p00261fyo6v.html.（League of Legends Pro League. Royal Never Give Up vs. Team WE： LPL 2018 Spring Playoffs — Round 2 [EB/OL]. [2018-09-12]. https：//v.qq.com/x/cover/191162cgjvuzbxm/p00261fyo6v.html.）

[18] SATHE S， AGGARWAL C C. Subspace outlier detection in linear time with randomized hashing [C]// ICDM 2016： Proceedings of the 2016 IEEE 16th International Conference on Data Mining. Piscataway， NJ： IEEE， 2016： 459-468.

[19] MARTINS H， PALMA L， CARDOSO A， et al. A support vector machine based technique for online detection of outliers in transient time series [C]// ASCC 2015： Proceedings of the 10th Asian Control Conference. Piscataway， NJ： IEEE， 2015： 1-6.

[20] NING J， CHEN L T， ZHOU C， et al. Parameter k search strategy in outlier detection [J]. Pattern Recognition Letters， 2018， 112： 56-62.