基于動態(tài)窗口的灰色加權(quán)填充算法及應(yīng)用*

王　澤,程　愷,董　坤,王家騰

(解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院仿真與數(shù)據(jù)中心,江蘇南京　210007)

?

基于動態(tài)窗口的灰色加權(quán)填充算法及應(yīng)用*

王澤,程愷,董坤,王家騰

(解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院仿真與數(shù)據(jù)中心,江蘇南京210007)

摘要:為解決復(fù)雜系統(tǒng)中單屬性缺失數(shù)據(jù)填充困難問題,提出了基于動態(tài)窗口的灰色加權(quán)填充算法。該算法通過建立雙向灰色預(yù)測模型,并采用模型精度評價系數(shù)加權(quán)填充缺失數(shù)據(jù),有效增強(qiáng)了算法的準(zhǔn)確性;提出基于灰色模型評價系數(shù)反饋的動態(tài)伸縮窗口概念,尋找產(chǎn)生最優(yōu)模型的訓(xùn)練數(shù)據(jù)序列,使算法具有良好的魯棒性和適應(yīng)性。實驗結(jié)果表明,該方法在RMSE和MA兩項指標(biāo)上均優(yōu)于傳統(tǒng)的雙向灰插值、灰插值、多項式插值等方法。

關(guān)鍵詞:動態(tài)窗口;灰色預(yù)測;加權(quán)系數(shù);缺失值填充;軍事訓(xùn)練數(shù)據(jù)

在現(xiàn)實數(shù)據(jù)分析挖掘中,數(shù)據(jù)缺失是一個普遍存在的現(xiàn)象:廣泛用于機(jī)器學(xué)習(xí)的UCI基準(zhǔn)數(shù)據(jù)庫有接近40%的數(shù)據(jù)集存在數(shù)據(jù)缺失問題[1-2];在軍事訓(xùn)練演習(xí)數(shù)據(jù)中,幾乎每一個數(shù)據(jù)表格都存在不同程度的數(shù)據(jù)缺失[3]。導(dǎo)致缺失現(xiàn)象的原因很多,如設(shè)備故障、輸入丟失等,如果不對缺失值進(jìn)行處理或者處理不充分,得出的分析結(jié)果會存在偏差或得出的模型不具備普遍性[4-6],缺失數(shù)據(jù)填充已然成為了一項必不可少的數(shù)據(jù)預(yù)處理技術(shù)。

缺失值填充方法包括簡單填充、屬性填充和實例填充三種類型,本文主要研究屬性填充方式。屬性填充依賴原始數(shù)據(jù)的單一或少量屬性維度,利用屬性間的關(guān)系或?qū)傩詽撛诘囊?guī)則對缺失值進(jìn)行填充。常用的屬性填充方法有:基于回歸分析[7]、信息增益[8]、灰色預(yù)測[9-10]的方法和EM算法[6]等。基于回歸分析的填充方法通過擬合回歸數(shù)學(xué)模型計算缺失值,該方法僅適用于滿足確定數(shù)學(xué)模型的數(shù)據(jù)集;基于信息增益的方法，依據(jù)與缺失數(shù)據(jù)關(guān)聯(lián)密切的屬性對缺失值進(jìn)行填充,該方法針對標(biāo)稱型數(shù)據(jù)效果良好，但不適用于數(shù)值型數(shù)據(jù);序列缺失數(shù)據(jù)的灰插值推理方法通過引入灰色預(yù)測模型擬合單屬性函數(shù),插值填充缺失值,取得了良好的效果,然而該算法限制了訓(xùn)練模型,可伸縮性不強(qiáng);基于EM模型的填充方法認(rèn)為數(shù)據(jù)服從含參分布,算法經(jīng)過多次迭代收斂填充缺失數(shù)據(jù),得到的填充效果良好但迭代方式很大程度地加大了算法復(fù)雜性,限制了方法的實際應(yīng)用。

軍事訓(xùn)練演習(xí)數(shù)據(jù)產(chǎn)生于訓(xùn)練演習(xí)系統(tǒng)中的各個要素,由于訓(xùn)練演習(xí)信息系統(tǒng)十分龐大,是典型的復(fù)雜系統(tǒng),產(chǎn)生的數(shù)據(jù)具有多源性、關(guān)聯(lián)性和動態(tài)性等特征[11-12]。軍事訓(xùn)練演習(xí)數(shù)據(jù)的缺失值填充存在兩方面問題亟待解決,首先復(fù)雜系統(tǒng)各屬性數(shù)據(jù)之間的關(guān)系尚不明確,其次某些屬性數(shù)據(jù)的相關(guān)要素?zé)o法采集或不能量化,因此大量依賴相關(guān)屬性的缺失值填充方法無法滿足這一特殊背景。

綜上所述,為滿足算法性能需求和特定應(yīng)用背景,本文針對灰色系統(tǒng)中單屬性數(shù)據(jù)缺失問題,提出基于動態(tài)窗口的灰色加權(quán)填充方法,通過建立滑動窗口雙向灰色預(yù)測模型,對缺失數(shù)據(jù)進(jìn)行加權(quán)填充,增強(qiáng)算法準(zhǔn)確性;提出基于灰色模型評價反饋的動態(tài)窗口概念,優(yōu)化灰色模型累加數(shù)列,改善算法的魯棒性。

1相關(guān)基礎(chǔ)理論

1.1灰色預(yù)測模型GM(1,1)[10]

設(shè)原始數(shù)據(jù)序列為:x(0)=(x(0)(1),x(0)(2),…,x(0)(n)),累加序列為x(1)=(x(1)(1),x(1)(2),…,x(1)(n)),其中x(1)(t)為前幾項數(shù)據(jù)之和:

(1)

建立關(guān)于x(1)(t)的一階線性微分白化方程:

(2)

通過最小二乘法求解參數(shù)向量A,得

(3)

將式(3)得出的結(jié)果代入式(2),并對微分方程求解可得

(4)

(5)

1.2灰色模型評價指標(biāo)

灰色模型的評價指標(biāo)包括三種:相對誤差q,方差比C,小誤差概率P。相對誤差q是原始值與預(yù)測值的殘差與原始值之比,反映了預(yù)測值與原始值的偏離程度,計算公式如式(6):

(6)

方差比C表示殘差序列的方差與原始數(shù)據(jù)方差之比,設(shè)原始數(shù)據(jù)序列均值為μ(0),殘差序列均值為μ(q),則

(7)

小誤差概率P表示殘差小于殘差序列方差的概率,如式(8):

(8)

2基于動態(tài)窗口的灰色填充方法

基于動態(tài)窗口的灰色填充方法首先找到數(shù)據(jù)序列中缺失值的位置;之后根據(jù)缺失值所在位置設(shè)定初始填充窗口,并建立雙向灰色預(yù)測模型;然后動態(tài)調(diào)整窗口大小,使得模型達(dá)到一定步長范圍內(nèi)的最優(yōu);最后根據(jù)最優(yōu)雙向預(yù)測模型得到的結(jié)果對缺失數(shù)據(jù)進(jìn)行預(yù)測填充。具體概念和步驟如下。

2.1雙向灰色預(yù)測模型

圖1　窗口示意

2.2動態(tài)窗口模型

雙向預(yù)測模型較大程度地提高了算法的填充精準(zhǔn)度,然而在沒有先驗知識幫助下難以確定窗口步長大小,而不同步長的數(shù)據(jù)序列產(chǎn)生的模型預(yù)測效果差別明顯,因此固定的窗口步長限制了算法的應(yīng)用。針對這一問題,本文提出動態(tài)窗口概念,使用灰色模型精度檢驗指標(biāo)作為反饋系數(shù),動態(tài)調(diào)整左右窗寬,改善算法的魯棒性和適應(yīng)性。

表1　灰色模型精度檢驗表[10]

2.3加權(quán)系數(shù)

由雙向灰色預(yù)測模型得到的結(jié)果包括前向預(yù)測結(jié)果和后向預(yù)測結(jié)果,而不同的模型訓(xùn)練數(shù)據(jù)會產(chǎn)生不同的預(yù)測結(jié)果,若對兩個預(yù)測值進(jìn)行簡單的綜合,不具備說服力且效果不理想。本文針對這一問題,對兩個預(yù)測模型得到的結(jié)果采用反饋系數(shù)加權(quán)策略,以提高算法準(zhǔn)確性。

(9)

本文基于模型的擬合程度越高,得到的預(yù)測結(jié)果越精確這一原則,并根據(jù)精度綜合考慮模型貢獻(xiàn)程度,提出組合系數(shù)λ的計算方法:

(10)

其中,ε表示前后灰色模型共同保存的比例,al表示前向預(yù)測模型精度的等級,ar表示后向預(yù)測模型精度的等級。式(10)既考慮了前后向模型的精準(zhǔn)程度,又有效防止了過擬合現(xiàn)象。

2.4算法過程及復(fù)雜度分析

基于動態(tài)窗口的灰色填充方法具體步驟如下:第一步,找到數(shù)據(jù)序列內(nèi)中缺失值所在位置;第二步,在缺失值前后定義初始窗口;第三步,針對窗口內(nèi)前后向序列分別采用動態(tài)窗口模型調(diào)整步長,直到找到最優(yōu)雙向預(yù)測模型出現(xiàn);第四步,在最優(yōu)窗口基礎(chǔ)上得到加權(quán)預(yù)測值作為填充值。算法流程圖如圖2所示。

圖2　算法流程圖

算法存在兩次循環(huán),即尋找缺失值和調(diào)整窗口步長,設(shè)步長變化為常數(shù)C(最大步長與最小步長之差),則時間復(fù)雜度為:O(Cn);算法的模型建立在矩陣運(yùn)算的基礎(chǔ)上,矩陣運(yùn)算的開銷為1,因此算法的總時間開銷為O(Cn),其中C?n。與其他屬性填充方式相比較,本文算法處于優(yōu)勢地位。

3實驗與結(jié)果分析

實驗運(yùn)行環(huán)境:CPU為CORE i7,內(nèi)存為8G,系統(tǒng)為Windows 7,算法運(yùn)行工具為Matlab 2012a。分別在多個軍事訓(xùn)練演習(xí)數(shù)據(jù)集上使用本文算法、多項式插值、灰插值、雙向灰插值[9]等四個算法進(jìn)行性能測試,并做出對比分析。

3.1評價指標(biāo)

(11)

(12)

當(dāng)填充效果越好時,RMSE的值越小,同時MA越接近于1。

3.2數(shù)據(jù)集說明

為驗證算法的可行性與有效性,本文使用軍事訓(xùn)練演習(xí)數(shù)據(jù)庫中,某模擬器材在仿真戰(zhàn)場演習(xí)環(huán)境中某時段的瞬時機(jī)動速度數(shù)據(jù)(Instantaneous velocity,IV)和某網(wǎng)關(guān)在某時段的信息流量數(shù)據(jù)(Gateway traffic,GT)作為實驗數(shù)據(jù)。圖3(a)表示IV數(shù)據(jù)集,橫坐標(biāo)為117個時間采樣點,縱坐標(biāo)表示在某一時刻的瞬時速度;圖3(b)表示GT數(shù)據(jù)集,橫坐標(biāo)為4628個時間采樣點,縱坐標(biāo)表示在某一時刻的單位流量。

圖3　數(shù)據(jù)集圖示

對兩個數(shù)據(jù)集的特征描述如表2,在軍事訓(xùn)練演習(xí)信息系統(tǒng)中,機(jī)動速度和網(wǎng)關(guān)流量兩個數(shù)據(jù)集均為單屬性數(shù)值型時序數(shù)據(jù),與其相關(guān)的要素多而復(fù)雜,而且從表中可以發(fā)現(xiàn)數(shù)據(jù)的波動十分大,GT數(shù)據(jù)集的離散系數(shù)達(dá)到了62.86%,因此很難使用某一種確定的模型來準(zhǔn)確地預(yù)測填充缺失數(shù)據(jù)。

表2　數(shù)據(jù)集特征

3.3實驗結(jié)果比較分析

3.3.1不同數(shù)據(jù)集上的對比實驗

為驗證算法針對不同特征數(shù)據(jù)集的適應(yīng)性,本文針對IV數(shù)據(jù)集,隨機(jī)選取6個時間采樣點數(shù)據(jù)作為缺失數(shù)據(jù),并分別使用本文算法、雙向灰插值、灰插值、多項式插值等方法進(jìn)行填充。在實驗參數(shù)選取上,本文算法設(shè)置最大窗口為20,其余方法均設(shè)置窗口大小為16,得到的實驗結(jié)果如表3所示。針對GT數(shù)據(jù)集,本文隨機(jī)選取20個時間采樣點數(shù)據(jù)作為缺失數(shù)據(jù),設(shè)置窗口大小為30并采用同樣的方式對缺失數(shù)據(jù)進(jìn)行填充,得到的實驗結(jié)果如表3所示。

表3　實驗結(jié)果

表2顯示了四種不同屬性填充方法對兩個時序數(shù)據(jù)集的填充效果,不論是小型的階段性序列數(shù)據(jù)還是大量序列數(shù)據(jù),本文算法在均方根誤差和平均填充精度兩個評價指標(biāo)上都優(yōu)于其余方法。圖4顯示了原始數(shù)據(jù)圖像(藍(lán)色線條)與本文算法填充的單個數(shù)據(jù)點(紅色“+”形狀)的對比,從圖中可以看出填充的數(shù)據(jù)幾乎與原始數(shù)據(jù)一致。分析數(shù)據(jù)和實驗結(jié)果,本文使用典型復(fù)雜系統(tǒng)中的單屬性數(shù)據(jù),難以確定數(shù)據(jù)趨勢中的數(shù)學(xué)模型,且存在波動大而頻繁的現(xiàn)象,符合灰色模型的使用范圍。同時通過動態(tài)調(diào)整訓(xùn)練窗口大小,使用雙向加權(quán)預(yù)測,使得預(yù)測模型更加準(zhǔn)確,故能得到很好的填充效果。

圖4　填充數(shù)據(jù)與原始數(shù)據(jù)對比

3.3.2同一數(shù)據(jù)集上不同缺失率的對比實驗

為驗證算法對不同缺失比例的適應(yīng)性,本文針對含有4628個時間采樣點的數(shù)據(jù)集GT,分別選取5%,15%,25%,35%的數(shù)據(jù)作為缺失數(shù)據(jù),在實驗參數(shù)選取上,與上文一樣。得到實驗結(jié)果如圖5所示。

圖5　針對不同缺失比例數(shù)據(jù)集的實驗效果

圖5(a)展示了四種不同算法對不同缺失比例數(shù)據(jù)集填充效果的RMSE評價指標(biāo)對比,圖5(b)則展示了MA評價指標(biāo)的對比。從圖中可以得出以下幾點結(jié)論:隨著數(shù)據(jù)集缺失比例的提高,各類型算法的填充效果都會降低;灰色填充的整體效果明顯優(yōu)于多項式填充,原因在于數(shù)據(jù)波動性較大,難以尋找一個準(zhǔn)確的數(shù)學(xué)模型來擬合數(shù)據(jù)發(fā)展趨勢;本文算法在綜合了動態(tài)伸縮窗口和雙向加權(quán)填充方法的條件下,效果明顯優(yōu)于其余方法;同時圖中出現(xiàn)了一個有趣的現(xiàn)象,在含有694個缺失點的條件下,單向灰色預(yù)測效果優(yōu)于雙向預(yù)測,原因在于右側(cè)數(shù)據(jù)的波動對雙向預(yù)測產(chǎn)生了不良影響,但是在大多數(shù)情況下,雙向預(yù)測模型效果更好。

4結(jié)束語

本文提出了一種基于動態(tài)窗口的雙向灰色加權(quán)填充算法。該方法建立了雙向灰色預(yù)測模型,通過前后向灰色模型的精度指標(biāo)加權(quán)填充缺失數(shù)據(jù),在提高填充準(zhǔn)確度的同時制效避免了過擬合現(xiàn)象;提出基于灰色模型評價反饋的動態(tài)窗口方法,通過尋找最優(yōu)窗口提高預(yù)測模型的準(zhǔn)確性,有效改善了算法的魯棒性和適應(yīng)性。

應(yīng)用實驗表明,算法具有較優(yōu)的性能,能夠適應(yīng)波動大、趨勢不明顯、缺失率高的單屬性缺失數(shù)據(jù);同時算法時間復(fù)雜度低,能夠面臨大數(shù)據(jù)集的壓力。然而,算法沒有充分利用屬性間關(guān)系,針對屬性關(guān)系密切的數(shù)據(jù)填充效果達(dá)不到最佳,如何將屬性間關(guān)系綜合到動態(tài)窗口的灰色加權(quán)模型中來,是下一步的努力方向。

參考文獻(xiàn):

[1]武森, 馮小東, 單志廣. 基于不完備數(shù)據(jù)聚類的缺失數(shù)據(jù)填補(bǔ)方法[J]. 計算機(jī)學(xué)報, 2012, 35(8):1726-1738.

[2]García-Laencina P J, Sancho-Gómez J L, Figueiras-Vidal A R, et al. K nearest neighbours with mutual information for simultaneous classification and missing data imputation [J]. Neurocomputing, 2009, 72(s 7-9):1483-1493.

[3]張宏軍, 郝文寧. 基于作戰(zhàn)行動的訓(xùn)練演習(xí)實況數(shù)據(jù)編輯方法[J]. 軍事運(yùn)籌與系統(tǒng)工程, 2013, 27(3):10-14.

[4]Wu, X:Knowledge Acquisition From Database[M].Ablex Publishing, 1995.

[5]Han J, Kamber M, Pei J. Data mining: concepts and techniques (third edition)[M]. Morgan Kaufmann Publishers, 2012.

[6]García S, Luengo J, Herrera F. Data Preprocessing in Data Mining[M]. Springer International Publishing, 2015.

[7]Cooper L G, Leeuw J D, Sogomonian A G. An imputation method for dealing with missing data in regression[J]. Applied Stochastic Models & Data Analysis, 1991, 7(3):213-235.

[8]張紅霞. 缺失值填充:基于信息增益的方法[J]. 計算機(jī)工程與設(shè)計, 2006, 27(24):4810-4812.

[9]金義富, 朱慶生, 邢永康. 序列缺失數(shù)據(jù)的灰插值推理方法[J]. 控制與決策, 2006, 21(2):236-240.

[10]鄧聚龍. 灰預(yù)測與灰決策[M]. 武漢：華中科技大學(xué)出版社, 2002.

[11]胡曉峰. 戰(zhàn)爭復(fù)雜系統(tǒng)建模與仿真[M]. 北京:國防大學(xué)出版社,2005.

[12]張宏軍,等.作戰(zhàn)指揮訓(xùn)練模擬系統(tǒng)[M].北京：解放軍出版社,2011.

[13]Zhang S, Jin Z, Zhu X. Missing data imputation by utilizing information within incomplete instances[J]. Journal of Systems & Software, 2011, 84(3):452-459.

Grey Weighted Imputation Method Based on Dynamic Window and Its Application

WANG Ze, CHENG Kai, DONG Kun, WANG Jia-teng

(Center of Simulation &Data, Institute of Command and Information System,PLA University of Science and Technology, Nanjing 210007, China)

Abstract:In order to solve the difficulty of single attribute missing values imputation in complex systems, a grey weighted imputation algorithm based on dynamic window is proposed. The algorithm imput missing values with two-way grey prediction model and model accuracy evaluation coefficient weighting method, which enhanced the algorithm precision effectively. It introduces a dynamic flexible window concept based on grey model evaluation coefficient feedback for finding the optimal model, which makes the algorithm be robust and adaptable. Numerical experiments results show that comparing several existing method, the algorithm can achieve better performance on root-mean-square error and mean accuracy.

Key words:dynamic window; grey predict; weighted coefficient; missing value imputation; military training data

中圖分類號:TJ630.3+4；E917

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

DOI:10.3969/j.issn.1673-3819.2016.02.010

作者簡介：王澤(1991-),男,湖南長沙人,碩士研究生,研究方向為模式識別和數(shù)據(jù)挖掘。

*基金項目：江蘇省自然科學(xué)基金(BK20150720)

收稿日期：2016-01-08

文章編號：1673-3819(2016)02-0043-05

修回日期： 2016-02-27

程愷(1983-),男,博士,講師。

董坤(1992-),男,碩士研究生。

王家騰(1991-),男,碩士研究生。