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

白瑞陽(yáng),吳曉燕,陳永興,卜祥偉,姚春明

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

?

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

白瑞陽(yáng),吳曉燕,陳永興,卜祥偉,姚春明

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

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

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

0引言

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

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

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

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

1時(shí)間序列的模式表示

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

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

(1)

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

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

1.1頻域方法

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

1.2時(shí)域方法

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

1.2.1基于特征點(diǎn)的分段線性方法

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

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

(2)

式中：ωi為分段后的第i個(gè)模式；fi(t,ωi)為連接模式ωi兩端點(diǎn)的線性函數(shù)；ek(t)為時(shí)間序列各分段部分與其模式表示之間的誤差。

基于特征點(diǎn)的分段線性表示方法就是將一系列特征點(diǎn)作為連接每?jī)蓚€(gè)模式的分割點(diǎn)，而特征點(diǎn)就是在時(shí)間序列變換中視覺上有著相對(duì)重要影響的觀測(cè)點(diǎn)，定義滿足如下條件的為特征點(diǎn)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í)間序列的起點(diǎn)和終點(diǎn)必為特征點(diǎn)，前后兩數(shù)據(jù)點(diǎn)之差不小于R的也是特征點(diǎn)(其中，R為可選參數(shù)，R值的大小決定了時(shí)間序列線段化描述的粗細(xì)程度)。對(duì)于仿真模型驗(yàn)證而言，模式就是連接相鄰兩特征點(diǎn)的直線段，其特征是線段的長(zhǎng)度l和斜率k，模型的可信性取決于仿真數(shù)據(jù)和參考數(shù)據(jù)時(shí)間序列的模式匹配程度。

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

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

(3)

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

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

(4)

2時(shí)間序列的模式距離

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

2.1斜率偏離距離

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

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

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

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

(5)

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

(6)

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

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

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

(7)

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

(1) 定義模式

從時(shí)間序列中抽取模式特征，將時(shí)間序列變換到特征空間，得到時(shí)間序列的模式表示。對(duì)于分段線性表示來(lái)說(shuō)，模式就是時(shí)間序列子段的插值線段，特征就是線段的長(zhǎng)度l、斜率k。

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

模式的距離可以用歐氏距離或其他方法來(lái)定義。

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

(8)

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

通過(guò)模式自我復(fù)制，使2條時(shí)間序列的模式匹配距離總和到最小。

序列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之間的動(dòng)態(tài)模式匹配距離為

(9)

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

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

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

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

(10)

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

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

(11)

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

4仿真分析

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

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

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

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1]黃柯棣,查亞兵.系統(tǒng)仿真可信性研究綜述[J].系統(tǒng)仿真學(xué)報(bào),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)于仿真模型驗(yàn)證[J].計(jì)算機(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]毛保紅,張鳳鳴,馮卉.基于奇異值分解的飛行動(dòng)作評(píng)價(jià)方法研究[J].計(jì)算機(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]劉懿,鮑德沛,楊澤紅，等.符號(hào)化近似SAX在時(shí)序數(shù)據(jù)挖掘中的應(yīng)用研究[J].計(jì)算機(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]王達(dá),榮岡.時(shí)間序列的模式距離[J].浙江大學(xué)學(xué)報(bào)：工學(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è),潘泉,張鵬.基于斜率表示的時(shí)間序列相似性度量方法[J].模式識(shí)別與人工智能,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è),楊峰，等.時(shí)間序列度量的斜率偏離距離方法研究[J].計(jì)算機(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

中圖分類號(hào)：TP391.9

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-086X(2015)-01-0168-05

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

通信地址：710051陜西省西安市長(zhǎng)樂東路甲字1號(hào)空軍工程大學(xué)防空反導(dǎo)學(xué)院研1隊(duì)E-mail：brynuaa@163.com

作者簡(jiǎn)介：白瑞陽(yáng)(1991-)，男，甘肅慶陽(yáng)人。碩士生，主要研究方向?yàn)橄到y(tǒng)建模與仿真。

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