白瑞陽,吳曉燕,陳永興,卜祥偉,姚春明

(空軍工程大學(xué) 防空反導(dǎo)學(xué)院，陜西 西安　710051)

?

基于數(shù)據(jù)挖掘的仿真模型驗證*

白瑞陽,吳曉燕,陳永興,卜祥偉,姚春明

(空軍工程大學(xué) 防空反導(dǎo)學(xué)院，陜西 西安710051)

摘要：針對復(fù)雜系統(tǒng)輸出具有數(shù)據(jù)量大、高度復(fù)雜性、非線性和非平穩(wěn)等特點，將數(shù)據(jù)挖掘思想和有關(guān)方法引入到導(dǎo)彈系統(tǒng)仿真模型模型驗證，通過對仿真數(shù)據(jù)和試驗數(shù)據(jù)進行模式表示和特征提取，將2時序數(shù)據(jù)的模式距離作為評價指標來衡量模型的有效性。仿真分析表明，該方法相比傳統(tǒng)方法計算量小，但意義明確，具有一定的實用性和參考價值。

關(guān)鍵詞：數(shù)據(jù)挖掘；模型驗證；模式表示；模式距離

0引言

隨著系統(tǒng)仿真技術(shù)的發(fā)展，模型的可信性越來越受到人們的關(guān)注，可信性評估已成為建模與仿真的關(guān)鍵技術(shù)之一[1]。模型的可信性需要通過校核與驗證(verification and validation，V&V)來度量，而模型驗證一直是V&V方法研究的重點和難點，它指從模型預(yù)期使用的角度出發(fā)，確定模型和有關(guān)數(shù)據(jù)代表真實世界正確程度過程。模型驗證最主要的方法就是考察在相同輸入條件下，仿真模型輸出結(jié)果與真實系統(tǒng)輸出的一致性程度[2]。

然而復(fù)雜系統(tǒng)輸出數(shù)據(jù)量大，具有高度復(fù)雜性，同時輸出中通常隱含系統(tǒng)本身的某些特征或模式。若用傳統(tǒng)驗證方法進行復(fù)雜仿真系統(tǒng)模型的驗證會帶來以下問題[3]：一是計算量大，傳統(tǒng)驗證方法無論時域方法還是頻域方法都注重點距離的匹配，這無疑會大大增加計算量；二是存在一定的風險，仿真模型不可能在所有層面與被仿真系統(tǒng)一一對應(yīng)，仿真數(shù)據(jù)與試驗數(shù)據(jù)很難具有高度一致性，單從數(shù)據(jù)一致性的角度來評價復(fù)雜系統(tǒng)仿真模型的可信性存在一定的風險。模型用戶更關(guān)心的是一段時間內(nèi)的變化模式和規(guī)律而非單個序列點的值，因此如何高效地對復(fù)雜系統(tǒng)輸出時間序列進行降維處理，從中提取有關(guān)系統(tǒng)運動的模式，再根據(jù)模式的匹配程度來確定時間序列的一致性程度，成為當前仿真模型驗證研究的新方向之一。

復(fù)雜系統(tǒng)輸出時間序列的模式提取可以通過數(shù)據(jù)挖掘的思想和有關(guān)方法來解決。數(shù)據(jù)挖掘是20世紀80年代末興起的一種從數(shù)據(jù)庫中發(fā)現(xiàn)知識的方法[4]，是從大量的實際應(yīng)用數(shù)據(jù)中提取人們感興趣的、潛在有用的知識的過程，提取的知識可以表達為概念、規(guī)則、規(guī)律、模式等形式，且已經(jīng)在金融時間序列分析、水紋時間序列分析和地震預(yù)報等方面得到廣泛的應(yīng)用。

本文將數(shù)據(jù)挖掘理論引入仿真模型驗證中，首先對2組時間序列(仿真數(shù)據(jù)和試驗數(shù)據(jù))進行降維處理得到基于特征點的分段線性模式表示，在此基礎(chǔ)上提取模式的表征特征：線段長度l和斜率k，通過計算時間序列之間的斜率偏離距離Dbias和動態(tài)模式匹配距離Ddpm來衡量仿真模型的有效性，為復(fù)雜仿真系統(tǒng)模型驗證提供了新方法。

1時間序列的模式表示

時間序列的模式表示是其數(shù)據(jù)挖掘的先決條件和關(guān)鍵問題之一，用來壓縮數(shù)據(jù)刻畫時間序列的主要形態(tài)而忽略微小細節(jié)。設(shè)有時間序列為X=(x1,x2,…，xn)，則其模式表示為

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

(1)

式中：ω為模式；f(ω)為模式表示；e(t)表示時間序列與其模式表示之間的誤差。

近年來對時間序列的模式表示進行了大量的研究，提出了許多不同的方法，歸結(jié)起來大致分為兩大類：①通過變換將時間序列由時域映射到頻域來研究；②直接在時域上進行各種不同的特征提取來研究相似性問題。

1.1頻域方法

通過映射函數(shù)，將時間序列由時域映射到頻域進行相似性研究。常用的有離散傅里葉變換(discrete fourier transform， DFT)、離散小波變換(discrete wavelet transform， DWT)等一些正交變換方法。如Agrawal等人提出采用離散傅里葉變換提取時間序列的特征[5]，Chan和Fu將離散小波變換用于時間序列的模式提取和相似性度量[6]。

1.2時域方法

時域方法有2種：①將長時間序列分割成若干較小的子序列；②對時間序列進行適當?shù)淖儞Q或表示，提取其特征或模式，然后基于特征進行相似性比較。文獻[7-8]分別探討了時間序列模式表示的奇異值分解法和符號化近似法，這些方法都有一定的局限性：奇異值分解法算法的時間復(fù)雜度很大，符號化近似法的離散化方法和字符表的大小難以選擇。為了保留時間序列的主要形態(tài)，快速方便地得到其模式表示，本文采用基于特征點的時間序列分段線性表示方法，其主要原理如下：

1.2.1基于特征點的分段線性方法

時間序列的分段線性表示是時間序列的模式表示方法中研究最早最多的方法，其基本思想就是用K條首位相連的直線段來近似長度為n的時間序列。線段的數(shù)目決定了對原始序列的近似程度。

對于時間序列X=(x1,x2,…，xn)，其線性分段模式表示為

(2)

式中：ωi為分段后的第i個模式；fi(t,ωi)為連接模式ωi兩端點的線性函數(shù)；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,…).

由上述條件可以看出，時間序列的起點和終點必為特征點，前后兩數(shù)據(jù)點之差不小于R的也是特征點(其中，R為可選參數(shù)，R值的大小決定了時間序列線段化描述的粗細程度)。對于仿真模型驗證而言，模式就是連接相鄰兩特征點的直線段，其特征是線段的長度l和斜率k，模型的可信性取決于仿真數(shù)據(jù)和參考數(shù)據(jù)時間序列的模式匹配程度。

假設(shè)求得原時間序列X的特征點為XC=(xi1,xi2,…，xik-1,xik)，則其基于特征點的模式表示為

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

(3)

式中：L為連接相鄰兩特征點的線性函數(shù)。

（3）教學(xué)課程形式的愿望。在希望開設(shè)課程的學(xué)生中，有498人（30.9%）最喜歡合作學(xué)習式，539人（33.5%）最喜歡案例教學(xué)式，356人（22.1%）最喜歡自學(xué)—輔導(dǎo)式，115人（7.1%）最喜歡傳遞—接受式，僅有103人（6.4%）最喜歡現(xiàn)象分析式，且不同年級、性別、任職的學(xué)生對教學(xué)形式愿望的差異有顯著性（P=0.018，P=0.034，P=7.427×10-5）。

(4)

2時間序列的模式距離

距離度量是進行仿真模型驗證的主要方向之一。模式距離是表示具有相同保持時間長度的2個模式的距離，時間序列的模式距離是表示具有相同長度的2個序列趨勢的差異程度，是模式距離在時間序列上的應(yīng)用[9]，即時間序列的模式距離既能有效地度量序列變化趨勢的相似程度，也能表示序列趨勢的相反程度，這正是基于點距離的分析方法諸如TIC(theil′ inequality coefficient)不等式系數(shù)法、灰色關(guān)聯(lián)分析法所不具備的。針對仿真模型的特點，本文采用斜率偏離距離和動態(tài)模式匹配距離作為模式距離度量，具體定義如下：

2.1斜率偏離距離

文獻[10]研究了時間序列的斜率距離，但在此距離定義中，若時間序列中出現(xiàn)高頻擾動時即表現(xiàn)為斜率的多次瞬時突變，導(dǎo)致序列間的斜率保持相對較小，有時可能與實際不符。文獻[11]定義了時間序列的斜率偏離距離，主要原理如下：

設(shè)X，Y表示2個等長的、在線性分段基礎(chǔ)上以斜率集表示的時間序列：

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

定義X，Y的初始斜率距離(initial slope distance)為

(5)

不難看出，初始斜率距離物理意義明確，符合人的直覺判斷，計算量小，而且還滿足時間序列相似性度量的基本準則：對稱性、自相似性、非負性和三角不等式。

(6)

從斜率偏離度的表達式中可以看出，如果曲線在某個時刻的斜率發(fā)生突變，相應(yīng)的偏離度會增大，隨著曲線維數(shù)的增加2條曲線的斜率偏離度會逐步穩(wěn)定在一定范圍內(nèi)。

2.2動態(tài)模式匹配距離

Berndt和Clifford]將動態(tài)時間彎曲[12](dynamic time warping, DTW)距離引入到時間序列相似性度量中，解決了時間序列發(fā)生時間軸彎曲和伸縮后的相似性度量問題。設(shè)時間序列X=(x1,x2,…，xm)和Y=(y1,y2,…，yn)，它們之間的動態(tài)時間彎曲距離為

(7)

在前面線性分段表示的基礎(chǔ)上，引入動態(tài)模式匹配(dynamic pattern matching，DPM)距離作為時間序列的相似性度量標準，步驟如下：

(1) 定義模式

從時間序列中抽取模式特征，將時間序列變換到特征空間，得到時間序列的模式表示。對于分段線性表示來說，模式就是時間序列子段的插值線段，特征就是線段的長度l、斜率k。

(2) 定義模式之間的距離，計算模式的匹配程度

模式的距離可以用歐氏距離或其他方法來定義。

給定模式p1=(l1,k1)和p2=(l2,k2)，定義它們之間的距離為

(8)

(3) 在模式距離的基礎(chǔ)上定義動態(tài)模式匹配距離

通過模式自我復(fù)制，使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之間的動態(tài)模式匹配距離為

(9)

3基于數(shù)據(jù)挖掘的模型驗證

綜上所述，基于數(shù)據(jù)挖掘的仿真模型驗證的基本思路為：首先得到模型仿真數(shù)據(jù)和參考數(shù)據(jù)基于特征點的分段線性模式表示，然后此基礎(chǔ)上定義模式之間的距離，用模式距離來代替點距離來描述模型與真實系統(tǒng)的接近程度，衡量模型的有效性。主要步驟如下：

(1) 得到仿真數(shù)據(jù)序列X的線性分段模式表示

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

(10)

(2) 得到參考數(shù)據(jù)序列Y的線性分段模式表示

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

(11)

(3) 分別計算仿真數(shù)據(jù)X和參考數(shù)據(jù)Y的斜率偏離距離Dbias和動態(tài)模式匹配距離Ddpm。若隨著分段數(shù)的增加，Dbias趨向于一個比較穩(wěn)定的值，則模型可信度就比較高；Ddpm越小，表明仿真模型與真實系統(tǒng)的一致性越好。

4仿真分析

以某型導(dǎo)彈系統(tǒng)的仿真模型驗證為例，彈道參數(shù)是導(dǎo)彈飛行性能的重要參數(shù)，在這里以彈道參數(shù)為研究對象，基于數(shù)據(jù)挖掘理論分析在相同初始條件下仿真模型輸出與真實系統(tǒng)輸出的一致性。圖1為X1和X2仿真模型在某次仿真試驗中的彈道輸出時間序列和飛行試驗彈道輸出時間序列。

圖1　彈道參數(shù)輸出時間序列Fig.1　Time series of ballistic parameter output

從圖1中可以看出，導(dǎo)彈彈道參數(shù)時間序列數(shù)據(jù)量大，類型復(fù)雜，另外序列還具有非線性、非平穩(wěn)等特點，若采用傳統(tǒng)的模型驗證方法會導(dǎo)致計算量大，且可信度不高。因此，將數(shù)據(jù)挖掘中的時間序列相似性度量引入到仿真模型驗證中，首先對仿真數(shù)據(jù)和試驗數(shù)據(jù)進行降維約簡處理，得到其分段線性的模式表示，計算其模式距離。在計算彈道參數(shù)輸出時間序列的模式表示中，可控參數(shù)R分別取1，2，3，相應(yīng)的分段數(shù)分別為31，23和16。不同分段數(shù)的彈道參數(shù)仿真時間序列和飛行試驗時間序列的模式距離計算結(jié)果見表1。

表1　模式距離計算結(jié)果

隨著分段數(shù)的增加，仿真數(shù)據(jù)和試驗數(shù)據(jù)的斜率偏離度趨向于一個比較穩(wěn)定的值，這說明2組序列的總體趨勢具有較高的一致性。此外，兩者的動態(tài)模式匹配距離隨著分段數(shù)的增加都保持在一個很小的范圍內(nèi)，說明2組序列在空間的彎曲距離及相似程度都很接近。由此說明，此仿真模型與實際系統(tǒng)具有很高的一致性，具有一定的可信性。

5結(jié)束語

模型驗證方法研究是模型VV&A工作的最重要內(nèi)容。本文提出的基于數(shù)據(jù)挖掘的仿真模型驗證方法，從系統(tǒng)建模的實際出發(fā)，認為仿真模型不可能完全再現(xiàn)真實系統(tǒng)，對仿真數(shù)據(jù)和實驗數(shù)據(jù)進行模式表示和特征提取，將模式距離作為兩者一致性程度的評價指標，有效解決了復(fù)雜系統(tǒng)的模型驗證問題。但本文的研究還不夠全面、深入，比如提取模式都是分段的線性函數(shù)，沒有將多項式或其他非線性函數(shù)考慮在內(nèi)，這方面還有待繼續(xù)研究。

參考文獻：

[1]黃柯棣,查亞兵.系統(tǒng)仿真可信性研究綜述[J].系統(tǒng)仿真學(xué)報,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]宋承齡.關(guān)于仿真模型驗證[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，F(xiàn)U 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].計算機工程與應(yīng)用,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在時序數(shù)據(jù)挖掘中的應(yīng)用研究[J].計算機工程與應(yīng)用,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].浙江大學(xué)學(xué)報：工學(xué)版,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]張建業(yè),潘泉,張鵬.基于斜率表示的時間序列相似性度量方法[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]梁建海,張建業(yè),楊峰，等.時間序列度量的斜率偏離距離方法研究[J].計算機工程與應(yīng)用,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號空軍工程大學(xué)防空反導(dǎo)學(xué)院研1隊E-mail：brynuaa@163.com

作者簡介：白瑞陽(1991-)，男，甘肅慶陽人。碩士生，主要研究方向為系統(tǒng)建模與仿真。

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