薛小燕，趙生光，程 剛*，劉宏偉

(1.華北科技學(xué)院計算機學(xué)院，河北廊坊 065201；2.燕京理工學(xué)院，河北廊坊 065201；3.青海民族大學(xué)土木與交通學(xué)院，青海西寧 810007)

1 引言

網(wǎng)絡(luò)數(shù)據(jù)存儲量的急速上升與用戶需求的復(fù)雜化令數(shù)據(jù)庫建設(shè)規(guī)模與使用范圍大幅提升[1]。在此大環(huán)境下，不同數(shù)據(jù)庫攻擊方法層出不窮，由數(shù)據(jù)庫攻擊或計算機網(wǎng)絡(luò)中的軟、硬件故障以及網(wǎng)絡(luò)故障等導(dǎo)致數(shù)據(jù)庫被破壞，數(shù)據(jù)庫內(nèi)數(shù)據(jù)丟失的問題屢見不鮮[2]。數(shù)據(jù)庫中數(shù)據(jù)的可靠性與準(zhǔn)確性是數(shù)據(jù)庫構(gòu)建的基礎(chǔ)要求，為保障數(shù)據(jù)庫內(nèi)數(shù)據(jù)的可靠性與準(zhǔn)確性，研究一種用于數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)的方法極為重要。

文獻[3]提出分布式數(shù)據(jù)庫用戶丟失數(shù)據(jù)恢復(fù)重構(gòu)仿真，通過遺傳算法計算出丟失數(shù)據(jù)的最優(yōu)參數(shù)，利用熵值的思想計算加權(quán)系數(shù)，最終獲得分布式數(shù)據(jù)庫丟失數(shù)據(jù)的填充值。實驗證明該方法對于數(shù)據(jù)恢復(fù)的精度較高。但目前該領(lǐng)域使用最為普遍的數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)方法為構(gòu)建丟失數(shù)據(jù)判斷模型，利用判斷模型判斷丟失重聚，實現(xiàn)丟失數(shù)據(jù)恢復(fù)重構(gòu)。文獻[4]提出基于改進壓縮感知算法的方法通過構(gòu)建完備字典，生成丟失數(shù)據(jù)丟失項取樣矩陣，將其作為壓縮感知框架的測量矩陣，通過正則化正交匹配追蹤實現(xiàn)數(shù)據(jù)恢復(fù)重構(gòu)。文獻[5]提出基于模態(tài)傅里葉-支持向量機優(yōu)化的方法構(gòu)建粒子群優(yōu)化最小二乘支持向量機模型，利用傅里葉修正集合模態(tài)分解的數(shù)據(jù)序列取得更佳的擬合效果。但上述數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)方法實際應(yīng)用過程中直接應(yīng)用在隨機丟失模式下，導(dǎo)致恢復(fù)重構(gòu)準(zhǔn)確率較低，不適用于大規(guī)模數(shù)據(jù)集。

基于此提出基于遺傳優(yōu)化的數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)方法，并通過仿真驗證所提方法的性能優(yōu)勢。

2 數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)方法

2.1 支持向量機輸入輸出確定及處理

以實現(xiàn)數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)為目的，綜合考慮數(shù)據(jù)庫內(nèi)丟失數(shù)據(jù)與時間、空間等不同因素的相關(guān)性[6]，構(gòu)建支持向量機多輸入單輸出判斷模型，用于恢復(fù)重構(gòu)數(shù)據(jù)庫內(nèi)某一時刻丟失的數(shù)據(jù)。

支持向量機判斷模型內(nèi)的多個輸入主要有：丟失數(shù)據(jù)前一時刻的數(shù)據(jù)、丟失數(shù)據(jù)所在的矩陣的行和列等。支持向量機判斷模型內(nèi)的單個輸出為數(shù)據(jù)庫丟失數(shù)據(jù)判斷值。利用數(shù)據(jù)庫內(nèi)數(shù)據(jù)訓(xùn)練支持向量機判斷模型，獲取模型并保存輸入自變量與輸出因變量間的非線性映射相關(guān)性，將其作為數(shù)據(jù)庫丟失數(shù)據(jù)判斷器。在數(shù)據(jù)庫出現(xiàn)數(shù)據(jù)丟失現(xiàn)象時，在判斷模型內(nèi)輸入相關(guān)數(shù)據(jù)，即可完成數(shù)據(jù)庫丟失數(shù)據(jù)的恢復(fù)重構(gòu)性判斷。

在利用數(shù)據(jù)庫內(nèi)相關(guān)數(shù)據(jù)訓(xùn)練支持向量機判斷模型獲取丟失數(shù)據(jù)判斷值前需對相關(guān)數(shù)據(jù)實施歸一化處理[7]，公式如式(1)

(1)

式(1)內(nèi)，y和x分別表示歸一化后的數(shù)據(jù)和歸一化前的數(shù)據(jù)，ymax和ymin分別表示設(shè)定的歸一化后數(shù)據(jù)上限值和下限值，xmax和xmin分別表示數(shù)據(jù)庫內(nèi)數(shù)據(jù)的上限值和下限值。如果xmax值與xmin值完全一致，也就是數(shù)據(jù)庫內(nèi)數(shù)據(jù)一致，即可確定y值與ymin值一致。經(jīng)由數(shù)次測試后確定，設(shè)置輸入自變量的歸一化波動范圍和輸出因變量的歸一化波動范圍分別為1與-1之間和1與0之間，支持向量機判斷模型的判斷結(jié)果更符合實際情況。

2.2 支持向量機核函數(shù)選取

作為初始數(shù)據(jù)樣本空間到特征空間的隱式映射，支持向量機核函數(shù)的核心是實現(xiàn)初始空間內(nèi)線性不可分問題與高維特征空間內(nèi)線性可分問題的轉(zhuǎn)換[8]。在支持向量機處理回歸判斷問題過程中，核函數(shù)設(shè)定是否恰當(dāng)直接影響支持向量機判斷結(jié)果的準(zhǔn)確性。相關(guān)文獻研究結(jié)果顯示在求解非線性多因素判斷問題過程中，支持向量機判斷模型采用RBF核函數(shù)(Radial Basis Function Kernel，徑向基函數(shù))進行判斷時所得結(jié)果的準(zhǔn)確性顯著高于其它核函數(shù)?；诖?，在利用支持向量機判斷模型判斷數(shù)據(jù)庫丟失數(shù)據(jù)過程中，支持向量機判斷模型的核函數(shù)選取RBF核函數(shù)，具體公式描述如式(2)

(2)

2.3 支持向量機參數(shù)尋優(yōu)

支持向量機判斷模型中懲罰函參數(shù)ξ、核函數(shù)參數(shù)γ與不敏感損失函數(shù)參數(shù)φ等選擇對于最終獲取結(jié)果產(chǎn)生直接影響，為獲取最優(yōu)支持向量機判斷模型參數(shù)，采用遺傳優(yōu)化算法優(yōu)化模型參數(shù)。

作為全局優(yōu)化算法，遺傳算法的性能尤為優(yōu)越，但傳統(tǒng)遺傳算法在實際應(yīng)用過程中存在計算量較大，實時性較差等缺陷。針對傳統(tǒng)遺傳算法應(yīng)用中的缺陷，利用Nelder-Mead單純形法對傳統(tǒng)遺傳算法進行優(yōu)化。

作為一種典型的確定性局部尋優(yōu)算法，Nelder-Mead單純形法可通過較快的速度收斂至局部極小點[9]。為實現(xiàn)Nelder-Mead單純形法對傳統(tǒng)遺傳算法的優(yōu)化，將Nelder-Mead單純形法的初始值設(shè)定為傳統(tǒng)遺傳算法進化至某代的最優(yōu)個體，在傳統(tǒng)遺傳算法進化過程中引入Nelder-Mead單純形法，將其作為局部搜索算子。利用Nelder-Mead單純形法優(yōu)化傳統(tǒng)遺傳算法的詳細(xì)過程：

在傳統(tǒng)遺傳算法進化至一定代數(shù)SGen的條件下，在群體的最優(yōu)個體周邊利用Nelder-Mead單純形法實施局部搜索，若Nelder-Mead單純形法搜索過程中未獲取更優(yōu)點，即定義搜索完成完成，返回進化過程；若Nelder-Mead單純形法搜索過程中發(fā)現(xiàn)更優(yōu)點，即視此更優(yōu)點為一個個體，以其取代群體內(nèi)的最差個體[10]。之后，遺傳算法進化過程依據(jù)此局部搜索算子融入的方式繼續(xù)進行，直至滿足終止條件。

遺傳優(yōu)化算法主要操作過程：

過程1：選取實數(shù)編碼方式對個體實施編碼。

在數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)過程中，單個個體由M個基因組成，M為自適應(yīng)權(quán)值，即待優(yōu)化參數(shù)的數(shù)量。不同基因值可通過0～2π范圍內(nèi)的實數(shù)描述。在初始化過程中，不同基因取值范圍均在這一區(qū)間內(nèi)[11]。

過程2：利用確定式采樣選擇方式選擇算子。

用Qs表示群體內(nèi)不同個體在下一代群體內(nèi)的期望生存數(shù)目，公式描述如式(3)

(3)

過程3：利用非均勻算術(shù)較差法確定交叉算子，通過兩個個體的線性組合獲取兩個新的個體。

(4)

(5)

式(4)和式(5)內(nèi)，δ表示以參數(shù)，其取值范圍為[0，1]。

過程4：利用高斯變異方法確定變異算子。

通過高斯變異的方法確定變異算子能夠優(yōu)化傳統(tǒng)遺傳算法對重點搜索區(qū)域的局部搜索性能。高斯變異的方法即變異操作過程中利用滿足正態(tài)分布的隨機數(shù)取代當(dāng)前基因值[12]。

過程5：設(shè)定優(yōu)化過程終止條件

群體內(nèi)的最佳適應(yīng)度滿足設(shè)定標(biāo)準(zhǔn)，或算法迭代次數(shù)達到設(shè)定上限值。

依據(jù)上述過程中的遺傳操作，設(shè)計如圖1所示的遺傳優(yōu)化算法流程。

圖1 遺傳算法優(yōu)化流程

2.4 丟失數(shù)據(jù)判斷

利用遺傳優(yōu)化算法確定支持向量機判斷模型最優(yōu)參數(shù)后，可將優(yōu)化后的懲罰函參數(shù)ξ、核函數(shù)參數(shù)γ與不敏感損失函數(shù)參數(shù)φ等與訓(xùn)練集代入訓(xùn)練函數(shù)實施訓(xùn)練，由此構(gòu)建支持向量機判斷模型。構(gòu)建測試集與訓(xùn)練集，利用測試集對此判斷模型實施測試評價，實現(xiàn)數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)性判斷。通過該模型實現(xiàn)恢復(fù)重構(gòu)性判斷過程中，測試集不同樣本內(nèi)前一時刻的數(shù)據(jù)屬性為上一樣本的數(shù)據(jù)判斷結(jié)果，也就是根據(jù)前一時刻的數(shù)據(jù)判斷結(jié)果，結(jié)合當(dāng)前時刻其它屬性判斷當(dāng)前時刻數(shù)據(jù)值，該問題可理解為一個典型時間序列判斷問題。

圖2所示為基于遺傳優(yōu)化的數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)算法流程。

圖2 數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)流程

3 實驗分析

實驗為測試本文所提出的基于遺傳優(yōu)化的數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)方法的綜合使用性能，采用仿真的方式進行數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)測試，同時對比本文方法與其它兩種對比方法(文獻[4]方法為對比方法1，文獻[5]方法為對比方法2)的性能。數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)實驗選取某實驗室環(huán)境檢測信息數(shù)據(jù)庫為仿真對象，以Windows XP和Matlab R 2009A 軟件分別作為仿真環(huán)境與仿真平臺。數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)實驗所使用的計算機CPU和內(nèi)存分別為E7500 2.93GHz和4GB。得出具體仿真過程與仿真結(jié)果。

3.1 仿真參數(shù)設(shè)定

所提方法中利用遺傳優(yōu)化算法選取支持向量機判斷模型最優(yōu)參數(shù)的過程對于最終丟失數(shù)據(jù)恢復(fù)重構(gòu)結(jié)果產(chǎn)生重要影響。相關(guān)參數(shù)設(shè)定如表1所示。

表1 參數(shù)設(shè)定

3.2 參數(shù)尋優(yōu)仿真

選取5折交叉驗證。通過測試確定最優(yōu)判斷模型對應(yīng)支持向量機參數(shù)尋優(yōu)結(jié)果為：懲罰參數(shù)、核函數(shù)參數(shù)和不敏感損失函數(shù)分別為31.879、0.117和0.046。表2所示為參數(shù)尋優(yōu)進化過程。

表2 參數(shù)尋優(yōu)進化過程

分析表2得到，采用所提方法進行數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)時，遺傳優(yōu)化算法進化前期獲取的最優(yōu)目標(biāo)函數(shù)值相較于平均目標(biāo)函數(shù)值具有明顯差異；進化后期的獲取的最優(yōu)目標(biāo)函數(shù)值同平均目標(biāo)函數(shù)值相比較為接近。產(chǎn)生這種現(xiàn)象的主要原因在于所提方法中在設(shè)計適應(yīng)度函數(shù)時引入Metropolis判斷標(biāo)準(zhǔn)的選擇復(fù)制策略。在進化前期，各染色體相對的適應(yīng)度函數(shù)值一致度較高，具有較強的劣質(zhì)解接收能力，可確保遺傳優(yōu)化過程中的種群多樣性，防止出現(xiàn)早熟問題。在進化后期，優(yōu)質(zhì)染色體對應(yīng)的適應(yīng)度函數(shù)值顯著提升，可提升所提方法參數(shù)尋優(yōu)過程的收斂速度。

3.3 丟失數(shù)據(jù)恢復(fù)重構(gòu)仿真結(jié)果

將上一實驗中獲取的最優(yōu)懲罰參數(shù)、最優(yōu)核函數(shù)參數(shù)、最優(yōu)不敏感損失函數(shù)和訓(xùn)練集代入訓(xùn)練函數(shù)，通過訓(xùn)練后得到支持向量機判斷模型。利用該模型進行數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)，所得結(jié)果如圖3所示。

圖3 丟失數(shù)據(jù)恢復(fù)重構(gòu)仿真結(jié)果

分析圖3得到，采用所提方法恢復(fù)重構(gòu)仿真對象內(nèi)丟失數(shù)據(jù)，可較好的地擬合訓(xùn)練集，均方誤差控制在0.01%。

采用訓(xùn)練好的模型對驗證測試集，選取相對誤差作為丟失數(shù)據(jù)恢復(fù)重構(gòu)性能的評價指標(biāo)。測試集仿真結(jié)果如圖4所示。

圖4 測試集仿真結(jié)果

分析圖4得到，所提方法對測試集中丟失數(shù)據(jù)實施恢復(fù)重構(gòu)時，相對誤差上限值為5.58%，相對誤差下限值為0.00%，平均相對誤差為1.76%。以上仿真結(jié)果充分說明所提方法能夠有效、準(zhǔn)確恢復(fù)重構(gòu)仿真對象中丟失數(shù)據(jù)。

3.4 仿真結(jié)果對比

對比所提方法、方法1與方法2針對仿真對象中丟失數(shù)據(jù)的恢復(fù)重構(gòu)結(jié)果，以此說明本文方法的性能優(yōu)勢。

圖5所示為所提方法、方法1與方法2進行仿真對象丟失數(shù)據(jù)恢復(fù)重構(gòu)過程中，不同方法各項評價對標(biāo)對比結(jié)果。

圖5 不同方法仿真結(jié)果對比

分析圖5得到，采用所提方法對仿真對象內(nèi)丟失數(shù)據(jù)實施恢復(fù)重構(gòu)的結(jié)果與兩種對比方法相比，誤差更小，更接近與仿真軟件模擬的仿真對象實際數(shù)據(jù)，由此說明本文方法恢復(fù)重構(gòu)的丟失數(shù)據(jù)準(zhǔn)確度更高。

4 結(jié)論

所提方法基于遺傳優(yōu)化進行數(shù)據(jù)庫丟失數(shù)據(jù)恢復(fù)重構(gòu)，構(gòu)建用于丟失數(shù)據(jù)恢復(fù)重構(gòu)的判斷模型，利用遺傳優(yōu)化算法獲取模型最優(yōu)參數(shù)。仿真結(jié)果顯示所提方法不僅能夠有效恢復(fù)重構(gòu)數(shù)據(jù)庫內(nèi)丟失數(shù)據(jù)且顯著提升丟失數(shù)據(jù)恢復(fù)重構(gòu)的準(zhǔn)確度，具有較大推廣價值。但由于條件限制，存在一定局限性，后續(xù)工作可以提升優(yōu)化參數(shù)對復(fù)雜數(shù)據(jù)的處理效率，豐富該領(lǐng)域的研究。