寧進 陳雷霆 周川 張磊

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

關鍵詞：聚合解聚;觸發(fā)機制;時序離群點檢測;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]是多分辨率建模的關鍵技術之一，在軍事仿真系統(tǒng)、列車控制系統(tǒng)和大型游戲等應用中發(fā)揮重要作用，其主要思想是：通過聚合操作，實現(xiàn)由高分辨率模型向低分辨率模型的轉換;通過解聚操作，實現(xiàn)由低分辨率模型向高分辨率模型的轉換;通過模型聚合解聚的觸發(fā)機制，管理聚合解聚操作，最終實現(xiàn)多分辨建模。

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

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

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

1 基于關注近鄰的關注域劃分算法

1.1 相關概念

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

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

2）Ei，Ej：E中的任意兩個實體。

3）Ei.x：表示實體Ei的位置橫坐標。

4）Ei.y：表示實體Ei的位置縱坐標。

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

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標記每個點是否已經(jīng)被安排簇。算法從關注近鄰最小的點開始劃分，滿足關注域條件（定義3）即完成該點的劃分，直到所有點都被安排了關注域。

2 基于關注域的多實體時序離群點檢測算法

2.1 相關描述

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

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

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

3 實驗結果與分析

3.1 數(shù)據(jù)集描述及評價方法

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

3.2 效果對比及復雜度分析

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

4 結語

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

參考文獻 （References）

[1] 李明忠，畢長劍，劉小荷，等.空軍作戰(zhàn)仿真模型聚合與解聚研究[J].系統(tǒng)仿真學報，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].系統(tǒng)仿真學報，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] 朱敏潔，周深根.多分辨率模型轉換的觸發(fā)機制[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.