基于数据挖掘的仿真模型验证*

白瑞阳,吴晓燕,陈永兴,卜祥伟,姚春明

(空军工程大学 防空反导学院，陕西 西安　710051)



基于数据挖掘的仿真模型验证*

白瑞阳,吴晓燕,陈永兴,卜祥伟,姚春明

(空军工程大学 防空反导学院，陕西 西安710051)

摘要：针对复杂系统输出具有数据量大、高度复杂性、非线性和非平稳等特点，将数据挖掘思想和有关方法引入到导弹系统仿真模型模型验证，通过对仿真数据和试验数据进行模式表示和特征提取，将2时序数据的模式距离作为评价指标来衡量模型的有效性。仿真分析表明，该方法相比传统方法计算量小，但意义明确，具有一定的实用性和参考价值。

关键词：数据挖掘；模型验证；模式表示；模式距离

0引言

随着系统仿真技术的发展，模型的可信性越来越受到人们的关注，可信性评估已成为建模与仿真的关键技术之一[1]。模型的可信性需要通过校核与验证(verification and validation，V&V)来度量，而模型验证一直是V&V方法研究的重点和难点，它指从模型预期使用的角度出发，确定模型和有关数据代表真实世界正确程度过程。模型验证最主要的方法就是考察在相同输入条件下，仿真模型输出结果与真实系统输出的一致性程度[2]。

然而复杂系统输出数据量大，具有高度复杂性，同时输出中通常隐含系统本身的某些特征或模式。若用传统验证方法进行复杂仿真系统模型的验证会带来以下问题[3]：一是计算量大，传统验证方法无论时域方法还是频域方法都注重点距离的匹配，这无疑会大大增加计算量；二是存在一定的风险，仿真模型不可能在所有层面与被仿真系统一一对应，仿真数据与试验数据很难具有高度一致性，单从数据一致性的角度来评价复杂系统仿真模型的可信性存在一定的风险。模型用户更关心的是一段时间内的变化模式和规律而非单个序列点的值，因此如何高效地对复杂系统输出时间序列进行降维处理，从中提取有关系统运动的模式，再根据模式的匹配程度来确定时间序列的一致性程度，成为当前仿真模型验证研究的新方向之一。

复杂系统输出时间序列的模式提取可以通过数据挖掘的思想和有关方法来解决。数据挖掘是20世纪80年代末兴起的一种从数据库中发现知识的方法[4]，是从大量的实际应用数据中提取人们感兴趣的、潜在有用的知识的过程，提取的知识可以表达为概念、规则、规律、模式等形式，且已经在金融时间序列分析、水纹时间序列分析和地震预报等方面得到广泛的应用。

本文将数据挖掘理论引入仿真模型验证中，首先对2组时间序列(仿真数据和试验数据)进行降维处理得到基于特征点的分段线性模式表示，在此基础上提取模式的表征特征：线段长度l和斜率k，通过计算时间序列之间的斜率偏离距离Dbias和动态模式匹配距离Ddpm来衡量仿真模型的有效性，为复杂仿真系统模型验证提供了新方法。

1时间序列的模式表示

时间序列的模式表示是其数据挖掘的先决条件和关键问题之一，用来压缩数据刻画时间序列的主要形态而忽略微小细节。设有时间序列为X=(x1,x2,…，xn)，则其模式表示为

X(t)=f(ω)+e(t)，

(1)

式中：ω为模式；f(ω)为模式表示；e(t)表示时间序列与其模式表示之间的误差。

近年来对时间序列的模式表示进行了大量的研究，提出了许多不同的方法，归结起来大致分为两大类：①通过变换将时间序列由时域映射到频域来研究；②直接在时域上进行各种不同的特征提取来研究相似性问题。

1.1频域方法

通过映射函数，将时间序列由时域映射到频域进行相似性研究。常用的有离散傅里叶变换(discrete fourier transform， DFT)、离散小波变换(discrete wavelet transform， DWT)等一些正交变换方法。如Agrawal等人提出采用离散傅里叶变换提取时间序列的特征[5]，Chan和Fu将离散小波变换用于时间序列的模式提取和相似性度量[6]。

1.2时域方法

时域方法有2种：①将长时间序列分割成若干较小的子序列；②对时间序列进行适当的变换或表示，提取其特征或模式，然后基于特征进行相似性比较。文献[7-8]分别探讨了时间序列模式表示的奇异值分解法和符号化近似法，这些方法都有一定的局限性：奇异值分解法算法的时间复杂度很大，符号化近似法的离散化方法和字符表的大小难以选择。为了保留时间序列的主要形态，快速方便地得到其模式表示，本文采用基于特征点的时间序列分段线性表示方法，其主要原理如下：

1.2.1基于特征点的分段线性方法

时间序列的分段线性表示是时间序列的模式表示方法中研究最早最多的方法，其基本思想就是用K条首位相连的直线段来近似长度为n的时间序列。线段的数目决定了对原始序列的近似程度。

对于时间序列X=(x1,x2,…，xn)，其线性分段模式表示为

(2)

式中：ωi为分段后的第i个模式；fi(t,ωi)为连接模式ωi两端点的线性函数；ek(t)为时间序列各分段部分与其模式表示之间的误差。

基于特征点的分段线性表示方法就是将一系列特征点作为连接每两个模式的分割点，而特征点就是在时间序列变换中视觉上有着相对重要影响的观测点，定义满足如下条件的为特征点xm(1≤m≤n)：

(1)m=1或m=n；

(2)xm-xm+i≥R(i=1,2,…)；

(3)xm-xm-i≥R(i=1,2,…).

由上述条件可以看出，时间序列的起点和终点必为特征点，前后两数据点之差不小于R的也是特征点(其中，R为可选参数，R值的大小决定了时间序列线段化描述的粗细程度)。对于仿真模型验证而言，模式就是连接相邻两特征点的直线段，其特征是线段的长度l和斜率k，模型的可信性取决于仿真数据和参考数据时间序列的模式匹配程度。

假设求得原时间序列X的特征点为XC=(xi1,xi2,…，xik-1,xik)，则其基于特征点的模式表示为

L(X)={L(xi1,xi2),L(xi2,xi3),…,L(xik-1,xik)},

(3)

式中：L为连接相邻两特征点的线性函数。

（3）教学课程形式的愿望。在希望开设课程的学生中，有498人（30.9%）最喜欢合作学习式，539人（33.5%）最喜欢案例教学式，356人（22.1%）最喜欢自学—辅导式，115人（7.1%）最喜欢传递—接受式，仅有103人（6.4%）最喜欢现象分析式，且不同年级、性别、任职的学生对教学形式愿望的差异有显著性（P=0.018，P=0.034，P=7.427×10-5）。

(4)

2时间序列的模式距离

距离度量是进行仿真模型验证的主要方向之一。模式距离是表示具有相同保持时间长度的2个模式的距离，时间序列的模式距离是表示具有相同长度的2个序列趋势的差异程度，是模式距离在时间序列上的应用[9]，即时间序列的模式距离既能有效地度量序列变化趋势的相似程度，也能表示序列趋势的相反程度，这正是基于点距离的分析方法诸如TIC(theil′ inequality coefficient)不等式系数法、灰色关联分析法所不具备的。针对仿真模型的特点，本文采用斜率偏离距离和动态模式匹配距离作为模式距离度量，具体定义如下：

2.1斜率偏离距离

文献[10]研究了时间序列的斜率距离，但在此距离定义中，若时间序列中出现高频扰动时即表现为斜率的多次瞬时突变，导致序列间的斜率保持相对较小，有时可能与实际不符。文献[11]定义了时间序列的斜率偏离距离，主要原理如下：

设X，Y表示2个等长的、在线性分段基础上以斜率集表示的时间序列：

X={(k1,t1),(k2,t2),…,(kn-1,tn-1)},

定义X，Y的初始斜率距离(initial slope distance)为

(5)

不难看出，初始斜率距离物理意义明确，符合人的直觉判断，计算量小，而且还满足时间序列相似性度量的基本准则：对称性、自相似性、非负性和三角不等式。

(6)

从斜率偏离度的表达式中可以看出，如果曲线在某个时刻的斜率发生突变，相应的偏离度会增大，随着曲线维数的增加2条曲线的斜率偏离度会逐步稳定在一定范围内。

2.2动态模式匹配距离

Berndt和Clifford]将动态时间弯曲[12](dynamic time warping, DTW)距离引入到时间序列相似性度量中，解决了时间序列发生时间轴弯曲和伸缩后的相似性度量问题。设时间序列X=(x1,x2,…，xm)和Y=(y1,y2,…，yn)，它们之间的动态时间弯曲距离为

(7)

在前面线性分段表示的基础上，引入动态模式匹配(dynamic pattern matching，DPM)距离作为时间序列的相似性度量标准，步骤如下：

(1) 定义模式

从时间序列中抽取模式特征，将时间序列变换到特征空间，得到时间序列的模式表示。对于分段线性表示来说，模式就是时间序列子段的插值线段，特征就是线段的长度l、斜率k。

(2) 定义模式之间的距离，计算模式的匹配程度

模式的距离可以用欧氏距离或其他方法来定义。

给定模式p1=(l1,k1)和p2=(l2,k2)，定义它们之间的距离为

(8)

(3) 在模式距离的基础上定义动态模式匹配距离

通过模式自我复制，使2条时间序列的模式匹配距离总和到最小。

序列X=(x1,x2,…，xn),Y=(y1,y2,…，yn)的模式表示分别为P(X)=(px1,px2,…，pxu)和P(Y)=(py1,py2,…，pyv)，其中pxi=(lxi,kxi)，pyj=(lyj,kyj)，1≤i≤u，1≤j≤v，X和Y之间的动态模式匹配距离为

(9)

3基于数据挖掘的模型验证

综上所述，基于数据挖掘的仿真模型验证的基本思路为：首先得到模型仿真数据和参考数据基于特征点的分段线性模式表示，然后此基础上定义模式之间的距离，用模式距离来代替点距离来描述模型与真实系统的接近程度，衡量模型的有效性。主要步骤如下：

(1) 得到仿真数据序列X的线性分段模式表示

P(X)=(px1,px2,…，pxu).

(10)

(2) 得到参考数据序列Y的线性分段模式表示

P(Y)=(py1,py2,…，pyv).

(11)

(3) 分别计算仿真数据X和参考数据Y的斜率偏离距离Dbias和动态模式匹配距离Ddpm。若随着分段数的增加，Dbias趋向于一个比较稳定的值，则模型可信度就比较高；Ddpm越小，表明仿真模型与真实系统的一致性越好。

4仿真分析

以某型导弹系统的仿真模型验证为例，弹道参数是导弹飞行性能的重要参数，在这里以弹道参数为研究对象，基于数据挖掘理论分析在相同初始条件下仿真模型输出与真实系统输出的一致性。图1为X1和X2仿真模型在某次仿真试验中的弹道输出时间序列和飞行试验弹道输出时间序列。

图1　弹道参数输出时间序列Fig.1　Time series of ballistic parameter output

从图1中可以看出，导弹弹道参数时间序列数据量大，类型复杂，另外序列还具有非线性、非平稳等特点，若采用传统的模型验证方法会导致计算量大，且可信度不高。因此，将数据挖掘中的时间序列相似性度量引入到仿真模型验证中，首先对仿真数据和试验数据进行降维约简处理，得到其分段线性的模式表示，计算其模式距离。在计算弹道参数输出时间序列的模式表示中，可控参数R分别取1，2，3，相应的分段数分别为31，23和16。不同分段数的弹道参数仿真时间序列和飞行试验时间序列的模式距离计算结果见表1。

表1　模式距离计算结果

随着分段数的增加，仿真数据和试验数据的斜率偏离度趋向于一个比较稳定的值，这说明2组序列的总体趋势具有较高的一致性。此外，两者的动态模式匹配距离随着分段数的增加都保持在一个很小的范围内，说明2组序列在空间的弯曲距离及相似程度都很接近。由此说明，此仿真模型与实际系统具有很高的一致性，具有一定的可信性。

5结束语

模型验证方法研究是模型VV&A工作的最重要内容。本文提出的基于数据挖掘的仿真模型验证方法，从系统建模的实际出发，认为仿真模型不可能完全再现真实系统，对仿真数据和实验数据进行模式表示和特征提取，将模式距离作为两者一致性程度的评价指标，有效解决了复杂系统的模型验证问题。但本文的研究还不够全面、深入，比如提取模式都是分段的线性函数，没有将多项式或其他非线性函数考虑在内，这方面还有待继续研究。

参考文献：

[1]黄柯棣,查亚兵.系统仿真可信性研究综述[J].系统仿真学报,1997,9(1):4-9.

HUANG Ke-di, ZHA Ya-bing. A Survey on the Credibility of System Simulation[J].Journal of System Simulation, 1997,9(1):4-9.

[2]SARBENT R G. Verification and Validation of Simulation Models[C]∥Proceedings of the 2011 Winter Simulation Conference. Orlando, FL:IEEE press, 2011:183-184.

[3]宋承龄.关于仿真模型验证[J].计算机仿真,2000,17(4):8-11.

SONG Cheng-ling. On the Validation of Simulation Models[J]. Computer Simulation,2000,17(4):8-11.

[4]AGRAWAL R, MAMNNILA H, SRIKANT R, et al. Fast Discovery of Association Rules[J]. In: Fayyad M, Piatetshy-Shapiro G, Smyth P eds. Advanced in Knowledge Discovery and Data Mining, Menlo Park, California: AAAI/MIT Press, 1996：307-328.

[5]AGRAWAL R, FALOUTSOS C,SWAMI A. Efficient Similarity Search in Sequence Databases[J]. Foundations of Data Organization and Algorithms, Lecture Notes in Computer Science Volume 730, 1993：69-84.

[6]CHAN K P，FU W C. Efficient Time Series Matching by Wavelrt[C]∥Proceedings of the International Conference on Data Engineering. Washington: IEEE Computer Society, 1999:126-133.

[7]毛保红,张凤鸣,冯卉.基于奇异值分解的飞行动作评价方法研究[J].计算机工程与应用,2008,44(32):240-242.

MAO Bao-hong, ZHANG Feng-ming, FEN Hui. Research on flight Maneuver Based on SVD[J]. Computer engineering and applications, 2008,44(32):240-242.

[8]刘懿,鲍德沛,杨泽红，等.符号化近似SAX在时序数据挖掘中的应用研究[J].计算机工程与应用,2006,2(27):191-193.

LIU Yi, BAO De-pei, YANG Ze-hong, et al. Application Research of a New Symbolic Approximation Method-SAX in Time Series Mining[J]. Computer Engineering and Applications, 2006,2(27):191-193.

[9]王达,荣冈.时间序列的模式距离[J].浙江大学学报：工学版,2004,38(7):795-798.

WANG Da, RONG Gang. Pattern Distance of Time Series[J]. Journal of Zhejiang University：Engineering Science ed, 2004,38(7):795-798.

[10]张建业,潘泉,张鹏.基于斜率表示的时间序列相似性度量方法[J].模式识别与人工智能,2007,20(2):271-274.

ZHANG Jian-ye, PAN Quan, ZHANG Peng. Similarity Measuring Method in Time Series Based on Slope[J]. Pattern Recognition and Artificial Intelligence, 2007,20(2):271-274.

[11]梁建海,张建业,杨峰，等.时间序列度量的斜率偏离距离方法研究[J].计算机工程与应用,2009,45(22):4-6.

LIANG Jian-hai, ZHANG Jian-ye, YANG Feng, et al. Study of Distance-Measuring Method of Time Series Based on Slope Departure[J]. Computer Engineering and Applications, 2009,45(22):4-6.

[12]BERNDT D J, CLIFFORD J. Using Dynamic Time Warping to Find Patterns in Time Series[C]∥In Proceedings of the KDD Workshop, Seattle, WA. 1994:359-370.

Validation of Simulation Model Based on Data Mining

BAI Rui-yang，WU Xiao-yan，CHEN Yong-xing，BU Xiang-wei，YAO Chun-ming

(AFEU，Air and Missile Defense School，Shaanxi Xi′an 710051,China)

Abstract:Aiming at the situation that the output of complex system are huge in data, complicated in structure, nonlinearity and smoothness, the idea and relevant method of data mining are introduced into model validation of missile system. Based on mining the pattern and feature of simulation and experiment data, the validity of model is measured by pattern distance between the two time series. The simulation analysis shows that the given method is simple in computation but specific in significance, practical and valuable of reference.

Key words:data mining; model validation; pattern representation; pattern distance

中图分类号：TP391.9

文献标志码：A

文章编号：1009-086X(2015)-01-0168-05

doi:10.3969/j.issn.1009-086x.2015.01.028

通信地址：710051陕西省西安市长乐东路甲字1号空军工程大学防空反导学院研1队E-mail：brynuaa@163.com

作者简介：白瑞阳(1991-)，男，甘肃庆阳人。硕士生，主要研究方向为系统建模与仿真。

收稿日期：2013-12-23；
修回日期：2014-03-05