模型聚合解聚的智能觸發(fā)機(jī)制

寧進(jìn) 陳雷霆 周川 張磊

摘 要：針對(duì)現(xiàn)有模型聚合解聚（AD）觸發(fā)機(jī)制人工依賴性高、頻繁聚合解聚的問題，提出了一種基于關(guān)注域的多實(shí)體時(shí)序離群點(diǎn)檢測(cè)算法的智能觸發(fā)機(jī)制。首先，基于關(guān)注近鄰劃分關(guān)注域;然后，計(jì)算關(guān)注域中實(shí)體的k距離離群值，得到關(guān)注域的離群值;最后，結(jié)合一種基于最強(qiáng)關(guān)注域閾值判定方法，構(gòu)建聚合解聚觸發(fā)機(jī)制。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的單實(shí)體時(shí)序離群點(diǎn)檢測(cè)算法相比，所提算法在指標(biāo)Precision、Recall和綜合指標(biāo) F1-score上均提升了10個(gè)百分點(diǎn)以上，不僅能及時(shí)地判斷聚合解聚操作的觸發(fā)時(shí)機(jī)，而且能使得仿真系統(tǒng)智能地檢測(cè)出發(fā)生突發(fā)情況的仿真實(shí)體，滿足了多分辨率建模的要求。

關(guān)鍵詞：聚合解聚;觸發(fā)機(jī)制;時(shí)序離群點(diǎn)檢測(cè);k距離;多分辨率建模

中圖分類號(hào)： TP181

文獻(xiàn)標(biāo)志碼：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]是多分辨率建模的關(guān)鍵技術(shù)之一，在軍事仿真系統(tǒng)、列車控制系統(tǒng)和大型游戲等應(yīng)用中發(fā)揮重要作用，其主要思想是：通過聚合操作，實(shí)現(xiàn)由高分辨率模型向低分辨率模型的轉(zhuǎn)換;通過解聚操作，實(shí)現(xiàn)由低分辨率模型向高分辨率模型的轉(zhuǎn)換;通過模型聚合解聚的觸發(fā)機(jī)制，管理聚合解聚操作，最終實(shí)現(xiàn)多分辨建模。

聚合解聚的觸發(fā)機(jī)制決定了仿真系統(tǒng)何時(shí)進(jìn)行聚合操作，何時(shí)進(jìn)行解聚操作，以及哪些模型需要進(jìn)行解聚操作。然而，目前聚合解聚觸發(fā)機(jī)制主要依靠專家來制定[4]，具體方法是：事先制定聚合解聚觸發(fā)規(guī)則，并在實(shí)際過程中靠專家（例如軍事指揮員、導(dǎo)播）實(shí)時(shí)指導(dǎo)聚合解聚觸發(fā)過程。這種人工操作的方式很容易錯(cuò)過重大激戰(zhàn)，造成不可挽回的指揮混亂，且受限于頻繁聚合解聚和可移植性差等問題。尤其是，在現(xiàn)代對(duì)戰(zhàn)仿真系統(tǒng)中，傳統(tǒng)的觸發(fā)機(jī)制呈現(xiàn)出明顯的復(fù)雜性特點(diǎn)，嚴(yán)重影響了仿真的效率。模型聚合解聚的觸發(fā)機(jī)制需要滿足專家的關(guān)注度的變化和突發(fā)狀況，根據(jù)這個(gè)特點(diǎn)，本文以多分辨率建模中的模型聚合解聚技術(shù)為背景，以多分辨率模型中的仿真實(shí)體（也稱作仿真對(duì)象，例如戰(zhàn)場中的飛機(jī)、大型游戲中的角色）為研究的基本單位，首次將時(shí)序離群點(diǎn)檢測(cè)技術(shù)應(yīng)用在聚合解聚技術(shù)中。

模型聚合解聚觸發(fā)時(shí)機(jī)具有以下特性：1）時(shí)變多實(shí)體。仿真實(shí)體位置不斷改變導(dǎo)致解聚關(guān)系也在不斷變化，使得解聚實(shí)體的選擇更加復(fù)雜。2）狀態(tài)復(fù)雜性。仿真實(shí)體狀態(tài)在時(shí)刻改變，無明顯周期特性，無法提前對(duì)所有情況制定規(guī)則。3）實(shí)時(shí)性要求。需要保證及時(shí)為專家提供重要信息，更好地發(fā)揮仿真系統(tǒng)的作用。根據(jù)模型聚合解聚觸發(fā)時(shí)機(jī)的特點(diǎn)，將時(shí)序離群點(diǎn)檢測(cè)算法引入模型聚合解聚觸發(fā)機(jī)制中。時(shí)序離群點(diǎn)檢測(cè)[5-7]是一種檢測(cè)時(shí)序數(shù)據(jù)中與大多數(shù)數(shù)據(jù)點(diǎn)不一致的少部分“離群點(diǎn)、異常點(diǎn)、新穎點(diǎn)”的算法，根據(jù)離群點(diǎn)的離群模式，可以分為離群序列檢測(cè)[8-13]和離群點(diǎn)檢測(cè)[14-15]。Zheng等[11]將統(tǒng)計(jì)方法和模糊集技術(shù)協(xié)同結(jié)合，以解決時(shí)序離群點(diǎn)檢測(cè)技術(shù)中的控制限值和多參數(shù)問題，并且顯著提高了檢測(cè)的效果;但是這種方法屬于事后檢測(cè)，不具有實(shí)時(shí)性。Zeng等[12]通過對(duì)動(dòng)態(tài)變量和權(quán)重的線性組合來動(dòng)態(tài)設(shè)置基于自回歸積分滑動(dòng)平均模型（AutoregRessive Integrated Moving Average model， ARIMA）時(shí)序離群點(diǎn)檢測(cè)中的警戒閾值，提高了檢測(cè)準(zhǔn)確率;但這種方法適用于具有周期特性的數(shù)據(jù)集，受限于本文仿真實(shí)體的狀態(tài)復(fù)雜性。Na等[13]改進(jìn)了基于局部離群指數(shù)（Local Outlier Factor， LOF）的時(shí)序離群點(diǎn)檢測(cè)算法中的歷史數(shù)據(jù)抽樣技術(shù)，并且提出了檢測(cè)序列離群點(diǎn)的策略，該算法具有內(nèi)存空間占用少、執(zhí)行效率高的優(yōu)點(diǎn);但是這種方法只針對(duì)了單實(shí)體時(shí)序離群點(diǎn)檢測(cè)。Wang等[14]針對(duì)組合時(shí)序序列的離群點(diǎn)檢測(cè)問題，提出了一種新的基于分離度模型的自適應(yīng)區(qū)間構(gòu)造方法，減弱了傳統(tǒng)算法的參數(shù)依賴問題，具有較好的檢測(cè)效果;但是這種方法依賴全局?jǐn)?shù)據(jù)，不符合模型聚合解聚的實(shí)時(shí)性要求。

如果直接將已有的時(shí)序離群點(diǎn)算法應(yīng)用于模型聚合解聚的觸發(fā)機(jī)制中，仍然會(huì)有時(shí)變多實(shí)體問題，更會(huì)帶來檢測(cè)效果差、頻繁聚合解聚的問題。針對(duì)這些問題，本文改進(jìn)基于距離的單實(shí)體時(shí)序離群點(diǎn)檢測(cè)算法，提出了基于關(guān)注域的多實(shí)體時(shí)序離群點(diǎn)檢測(cè)算法。首先，提出了關(guān)注域的概念以及基于互近鄰的關(guān)注域劃分方法;然后利用k距離計(jì)算關(guān)注域內(nèi)實(shí)體的離群值，得出關(guān)注域的離群值。該算法解決了已有時(shí)序離群點(diǎn)檢測(cè)算法對(duì)模型聚合解聚的觸發(fā)機(jī)制不適用的問題，在真實(shí)數(shù)據(jù)集上具有更好的檢測(cè)效果。最后，構(gòu)建了聚合解聚觸發(fā)機(jī)制，主要包括關(guān)注域劃分、基于關(guān)注域的時(shí)序離群點(diǎn)檢測(cè)、聚合解聚時(shí)機(jī)判定。該機(jī)制填補(bǔ)了目前模型聚合解聚技術(shù)中的非人工技術(shù)的空缺，也為多分辨率建模提供了一種有效的保證。

1 基于關(guān)注近鄰的關(guān)注域劃分算法

1.1 相關(guān)概念

為了更方便地引入關(guān)注域的概念，以二維對(duì)戰(zhàn)仿真中的多分辨率建模為背景，二維對(duì)戰(zhàn)是指仿真過程中的仿真單位處于同一水平面，比較典型的是陸地對(duì)戰(zhàn)仿真。首先，作如下規(guī)定：

1）E={E1，E2，…，En}：表示二維對(duì)戰(zhàn)仿真中低分辨率下的仿真實(shí)體（后面簡稱為實(shí)體）的集合，集合大小為n。

2）Ei，Ej：E中的任意兩個(gè)實(shí)體。

3）Ei.x：表示實(shí)體Ei的位置橫坐標(biāo)。

4）Ei.y：表示實(shí)體Ei的位置縱坐標(biāo)。

5）顯示窗口：二維對(duì)戰(zhàn)仿真中低分辨率下需要進(jìn)行解聚操作的一個(gè)位置區(qū)域，可以根據(jù)實(shí)際解聚要求來設(shè)置顯示窗口的尺寸。

6）wide：表示顯示窗口的長度。

7）high：表示顯示窗口的寬度。

1.2 關(guān)注域

定義1? 關(guān)注近鄰（Focus Nearest Neighbor， FNN）。實(shí)體Ei的關(guān)注近鄰（FNN）是指在仿真實(shí)體集合E中，與實(shí)體Ei可在同一顯示窗口中的實(shí)體的集合，定義如下：

1.3 關(guān)注域劃分算法

基于互近鄰的關(guān)注域劃分算法的偽代碼如算法1所示，算法中符號(hào)描述為：neighbor_List標(biāo)識(shí)每個(gè)點(diǎn)的關(guān)注近鄰;sortedIndicies表示每個(gè)點(diǎn)的關(guān)注近鄰大小;FS_list存儲(chǔ)搜索到的關(guān)注域;FS_flag標(biāo)記每個(gè)點(diǎn)是否已經(jīng)被安排簇。算法從關(guān)注近鄰最小的點(diǎn)開始劃分，滿足關(guān)注域條件（定義3）即完成該點(diǎn)的劃分，直到所有點(diǎn)都被安排了關(guān)注域。

2 基于關(guān)注域的多實(shí)體時(shí)序離群點(diǎn)檢測(cè)算法

2.1 相關(guān)描述

2.3 模型聚合解聚智能觸發(fā)機(jī)制流程

本文所提出的模型聚合解聚智能觸發(fā)機(jī)制適用于大部分多分辨率建模場景中，如圖2所示，整個(gè)機(jī)制包含輸入層、算法層和判定層。輸入層接收戰(zhàn)場上所有仿真實(shí)體的實(shí)時(shí)數(shù)據(jù)、實(shí)時(shí)位置直接用作劃分新的關(guān)注域，并和其他屬性一起進(jìn)行標(biāo)準(zhǔn)化處理，得到每個(gè)實(shí)體的實(shí)時(shí)特征向量。算法層在前面部分已詳細(xì)介紹，經(jīng)過本文算法模塊的處理，得到仿真系統(tǒng)中實(shí)時(shí)關(guān)注域離群值。

判定模塊判定最強(qiáng)關(guān)注域的離群值是否超過閾值解聚α：如果超過閾值，且當(dāng)前仿真系統(tǒng)為非該區(qū)域的高分辨率狀態(tài)，那么判定為需要解聚操作，將關(guān)注域中的仿真實(shí)體進(jìn)行解聚;如果未超過閾值，且當(dāng)前仿真系統(tǒng)為高分辨率狀態(tài)，那么判定為需要聚合操作。α的取值越大，則系統(tǒng)判定的離群狀態(tài)越少，解聚操作越少;反之，判定的離群狀態(tài)越多，解聚操作越多。實(shí)際應(yīng)用中可根據(jù)聚合解聚操作的頻繁要求來調(diào)整α的取值。本文智能觸發(fā)機(jī)制中，采用一元正態(tài)分布方法[16]來確定α的值：設(shè)置為歷史關(guān)注域離群值的均值，上浮3倍方差。這種閾值判定方式相比傳統(tǒng)的基于規(guī)則的方式更加簡單有效，避免了頻繁聚合解聚的問題。最強(qiáng)關(guān)注域的計(jì)算和解聚操作的判定函數(shù)描述如下。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 數(shù)據(jù)集描述及評(píng)價(jià)方法

為了驗(yàn)證本文方法的有效性，使用2018年英雄聯(lián)盟職業(yè)聯(lián)賽（League of Legends Pro League， LPL）春季賽季后賽RNG vs. WE[17]的對(duì)戰(zhàn)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)源是一場時(shí)長38min的比賽數(shù)據(jù)，共包含10個(gè)對(duì)戰(zhàn)實(shí)體（英雄），從第20min開始到第30min，每隔5s記錄每個(gè)實(shí)體的位置、血量百分比和藍(lán)量百分比，并且用比賽導(dǎo)播標(biāo)注的放大區(qū)域來標(biāo)注解聚操作的標(biāo)簽。

3.2 效果對(duì)比及復(fù)雜度分析

將本文算法與已有的單實(shí)體時(shí)序離群點(diǎn)檢測(cè)算法[18-19]：基于距離、基于密度、一類支持向量機(jī)（oneclass-Support Vector Machine， oneclass-SVM）作對(duì)比。其中，基于距離和基于密度的方法需要預(yù)先設(shè)置參數(shù)k的值，本實(shí)驗(yàn)采用文獻(xiàn)[20]中的算法來設(shè)置參數(shù)k，這是一種通過尋找數(shù)據(jù)集的穩(wěn)定狀態(tài)來選擇k值的方法，具有較好的效果。

4 結(jié)語

針對(duì)傳統(tǒng)的模型聚合解聚觸發(fā)機(jī)制的人工依賴性高、頻繁聚合解聚和可移植性差的問題，本文提出了一種智能觸發(fā)機(jī)制。實(shí)驗(yàn)結(jié)果顯示，所提出的基于關(guān)注域的時(shí)序離群點(diǎn)檢測(cè)算法和聚合解聚判定策略較為成功地解決了模型聚合解聚觸發(fā)時(shí)機(jī)問題。此外，相較于傳統(tǒng)的單實(shí)體時(shí)序離群點(diǎn)檢測(cè)算法，本文方法有效地提高了多實(shí)體時(shí)序離群點(diǎn)檢測(cè)的性能。在一些大型應(yīng)用場景中，包含更大的實(shí)體數(shù)量、更復(fù)雜的實(shí)體狀態(tài)，傳統(tǒng)的時(shí)序離群點(diǎn)檢測(cè)算法將會(huì)面臨巨大的挑戰(zhàn)。之后的工作中，需要針對(duì)這些挑戰(zhàn)進(jìn)一步研究，尤其是需研究將基于深度學(xué)習(xí)的時(shí)序離群點(diǎn)檢測(cè)算法應(yīng)用到該機(jī)制中。

參考文獻(xiàn) （References）

[1] 李明忠，畢長劍，劉小荷，等.空軍作戰(zhàn)仿真模型聚合與解聚研究[J].系統(tǒng)仿真學(xué)報(bào)，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] 李鳳霞，盧兆涵，雷正朝，等.基于隊(duì)形的聚合解聚方法研究[J].系統(tǒng)仿真學(xué)報(bào)，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] 朱敏潔，周深根.多分辨率模型轉(zhuǎn)換的觸發(fā)機(jī)制[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職業(yè)聯(lián)賽.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.