基于遗传优化的数据库丢失数据恢复重构仿真

薛小燕，赵生光，程 刚*，刘宏伟

(1.华北科技学院计算机学院，河北廊坊 065201；2.燕京理工学院，河北廊坊 065201；3.青海民族大学土木与交通学院，青海西宁 810007)

1 引言

网络数据存储量的急速上升与用户需求的复杂化令数据库建设规模与使用范围大幅提升[1]。在此大环境下，不同数据库攻击方法层出不穷，由数据库攻击或计算机网络中的软、硬件故障以及网络故障等导致数据库被破坏，数据库内数据丢失的问题屡见不鲜[2]。数据库中数据的可靠性与准确性是数据库构建的基础要求，为保障数据库内数据的可靠性与准确性，研究一种用于数据库丢失数据恢复重构的方法极为重要。

文献[3]提出分布式数据库用户丢失数据恢复重构仿真，通过遗传算法计算出丢失数据的最优参数，利用熵值的思想计算加权系数，最终获得分布式数据库丢失数据的填充值。实验证明该方法对于数据恢复的精度较高。但目前该领域使用最为普遍的数据库丢失数据恢复重构方法为构建丢失数据判断模型，利用判断模型判断丢失重聚，实现丢失数据恢复重构。文献[4]提出基于改进压缩感知算法的方法通过构建完备字典，生成丢失数据丢失项取样矩阵，将其作为压缩感知框架的测量矩阵，通过正则化正交匹配追踪实现数据恢复重构。文献[5]提出基于模态傅里叶-支持向量机优化的方法构建粒子群优化最小二乘支持向量机模型，利用傅里叶修正集合模态分解的数据序列取得更佳的拟合效果。但上述数据库丢失数据恢复重构方法实际应用过程中直接应用在随机丢失模式下，导致恢复重构准确率较低，不适用于大规模数据集。

基于此提出基于遗传优化的数据库丢失数据恢复重构方法，并通过仿真验证所提方法的性能优势。

2 数据库丢失数据恢复重构方法

2.1 支持向量机输入输出确定及处理

以实现数据库丢失数据恢复重构为目的，综合考虑数据库内丢失数据与时间、空间等不同因素的相关性[6]，构建支持向量机多输入单输出判断模型，用于恢复重构数据库内某一时刻丢失的数据。

支持向量机判断模型内的多个输入主要有：丢失数据前一时刻的数据、丢失数据所在的矩阵的行和列等。支持向量机判断模型内的单个输出为数据库丢失数据判断值。利用数据库内数据训练支持向量机判断模型，获取模型并保存输入自变量与输出因变量间的非线性映射相关性，将其作为数据库丢失数据判断器。在数据库出现数据丢失现象时，在判断模型内输入相关数据，即可完成数据库丢失数据的恢复重构性判断。

在利用数据库内相关数据训练支持向量机判断模型获取丢失数据判断值前需对相关数据实施归一化处理[7]，公式如式(1)

(1)

式(1)内，y和x分别表示归一化后的数据和归一化前的数据，ymax和ymin分别表示设定的归一化后数据上限值和下限值，xmax和xmin分别表示数据库内数据的上限值和下限值。如果xmax值与xmin值完全一致，也就是数据库内数据一致，即可确定y值与ymin值一致。经由数次测试后确定，设置输入自变量的归一化波动范围和输出因变量的归一化波动范围分别为1与-1之间和1与0之间，支持向量机判断模型的判断结果更符合实际情况。

2.2 支持向量机核函数选取

作为初始数据样本空间到特征空间的隐式映射，支持向量机核函数的核心是实现初始空间内线性不可分问题与高维特征空间内线性可分问题的转换[8]。在支持向量机处理回归判断问题过程中，核函数设定是否恰当直接影响支持向量机判断结果的准确性。相关文献研究结果显示在求解非线性多因素判断问题过程中，支持向量机判断模型采用RBF核函数(Radial Basis Function Kernel，径向基函数)进行判断时所得结果的准确性显著高于其它核函数。基于此，在利用支持向量机判断模型判断数据库丢失数据过程中，支持向量机判断模型的核函数选取RBF核函数，具体公式描述如式(2)

(2)

2.3 支持向量机参数寻优

支持向量机判断模型中惩罚函参数ξ、核函数参数γ与不敏感损失函数参数φ等选择对于最终获取结果产生直接影响，为获取最优支持向量机判断模型参数，采用遗传优化算法优化模型参数。

作为全局优化算法，遗传算法的性能尤为优越，但传统遗传算法在实际应用过程中存在计算量较大，实时性较差等缺陷。针对传统遗传算法应用中的缺陷，利用Nelder-Mead单纯形法对传统遗传算法进行优化。

作为一种典型的确定性局部寻优算法，Nelder-Mead单纯形法可通过较快的速度收敛至局部极小点[9]。为实现Nelder-Mead单纯形法对传统遗传算法的优化，将Nelder-Mead单纯形法的初始值设定为传统遗传算法进化至某代的最优个体，在传统遗传算法进化过程中引入Nelder-Mead单纯形法，将其作为局部搜索算子。利用Nelder-Mead单纯形法优化传统遗传算法的详细过程：

在传统遗传算法进化至一定代数SGen的条件下，在群体的最优个体周边利用Nelder-Mead单纯形法实施局部搜索，若Nelder-Mead单纯形法搜索过程中未获取更优点，即定义搜索完成完成，返回进化过程；若Nelder-Mead单纯形法搜索过程中发现更优点，即视此更优点为一个个体，以其取代群体内的最差个体[10]。之后，遗传算法进化过程依据此局部搜索算子融入的方式继续进行，直至满足终止条件。

遗传优化算法主要操作过程：

过程1：选取实数编码方式对个体实施编码。

在数据库丢失数据恢复重构过程中，单个个体由M个基因组成，M为自适应权值，即待优化参数的数量。不同基因值可通过0～2π范围内的实数描述。在初始化过程中，不同基因取值范围均在这一区间内[11]。

过程2：利用确定式采样选择方式选择算子。

用Qs表示群体内不同个体在下一代群体内的期望生存数目，公式描述如式(3)

(3)

过程3：利用非均匀算术较差法确定交叉算子，通过两个个体的线性组合获取两个新的个体。

(4)

(5)

式(4)和式(5)内，δ表示以参数，其取值范围为[0，1]。

过程4：利用高斯变异方法确定变异算子。

通过高斯变异的方法确定变异算子能够优化传统遗传算法对重点搜索区域的局部搜索性能。高斯变异的方法即变异操作过程中利用满足正态分布的随机数取代当前基因值[12]。

过程5：设定优化过程终止条件

群体内的最佳适应度满足设定标准，或算法迭代次数达到设定上限值。

依据上述过程中的遗传操作，设计如图1所示的遗传优化算法流程。

图1 遗传算法优化流程

2.4 丢失数据判断

利用遗传优化算法确定支持向量机判断模型最优参数后，可将优化后的惩罚函参数ξ、核函数参数γ与不敏感损失函数参数φ等与训练集代入训练函数实施训练，由此构建支持向量机判断模型。构建测试集与训练集，利用测试集对此判断模型实施测试评价，实现数据库丢失数据恢复重构性判断。通过该模型实现恢复重构性判断过程中，测试集不同样本内前一时刻的数据属性为上一样本的数据判断结果，也就是根据前一时刻的数据判断结果，结合当前时刻其它属性判断当前时刻数据值，该问题可理解为一个典型时间序列判断问题。

图2所示为基于遗传优化的数据库丢失数据恢复重构算法流程。

图2 数据库丢失数据恢复重构流程

3 实验分析

实验为测试本文所提出的基于遗传优化的数据库丢失数据恢复重构方法的综合使用性能，采用仿真的方式进行数据库丢失数据恢复重构测试，同时对比本文方法与其它两种对比方法(文献[4]方法为对比方法1，文献[5]方法为对比方法2)的性能。数据库丢失数据恢复重构实验选取某实验室环境检测信息数据库为仿真对象，以Windows XP和Matlab R 2009A 软件分别作为仿真环境与仿真平台。数据库丢失数据恢复重构实验所使用的计算机CPU和内存分别为E7500 2.93GHz和4GB。得出具体仿真过程与仿真结果。

3.1 仿真参数设定

所提方法中利用遗传优化算法选取支持向量机判断模型最优参数的过程对于最终丢失数据恢复重构结果产生重要影响。相关参数设定如表1所示。

表1 参数设定

3.2 参数寻优仿真

选取5折交叉验证。通过测试确定最优判断模型对应支持向量机参数寻优结果为：惩罚参数、核函数参数和不敏感损失函数分别为31.879、0.117和0.046。表2所示为参数寻优进化过程。

表2 参数寻优进化过程

分析表2得到，采用所提方法进行数据库丢失数据恢复重构时，遗传优化算法进化前期获取的最优目标函数值相较于平均目标函数值具有明显差异；进化后期的获取的最优目标函数值同平均目标函数值相比较为接近。产生这种现象的主要原因在于所提方法中在设计适应度函数时引入Metropolis判断标准的选择复制策略。在进化前期，各染色体相对的适应度函数值一致度较高，具有较强的劣质解接收能力，可确保遗传优化过程中的种群多样性，防止出现早熟问题。在进化后期，优质染色体对应的适应度函数值显著提升，可提升所提方法参数寻优过程的收敛速度。

3.3 丢失数据恢复重构仿真结果

将上一实验中获取的最优惩罚参数、最优核函数参数、最优不敏感损失函数和训练集代入训练函数，通过训练后得到支持向量机判断模型。利用该模型进行数据库丢失数据恢复重构，所得结果如图3所示。

图3 丢失数据恢复重构仿真结果

分析图3得到，采用所提方法恢复重构仿真对象内丢失数据，可较好的地拟合训练集，均方误差控制在0.01%。

采用训练好的模型对验证测试集，选取相对误差作为丢失数据恢复重构性能的评价指标。测试集仿真结果如图4所示。

图4 测试集仿真结果

分析图4得到，所提方法对测试集中丢失数据实施恢复重构时，相对误差上限值为5.58%，相对误差下限值为0.00%，平均相对误差为1.76%。以上仿真结果充分说明所提方法能够有效、准确恢复重构仿真对象中丢失数据。

3.4 仿真结果对比

对比所提方法、方法1与方法2针对仿真对象中丢失数据的恢复重构结果，以此说明本文方法的性能优势。

图5所示为所提方法、方法1与方法2进行仿真对象丢失数据恢复重构过程中，不同方法各项评价对标对比结果。

图5 不同方法仿真结果对比

分析图5得到，采用所提方法对仿真对象内丢失数据实施恢复重构的结果与两种对比方法相比，误差更小，更接近与仿真软件模拟的仿真对象实际数据，由此说明本文方法恢复重构的丢失数据准确度更高。

4 结论

所提方法基于遗传优化进行数据库丢失数据恢复重构，构建用于丢失数据恢复重构的判断模型，利用遗传优化算法获取模型最优参数。仿真结果显示所提方法不仅能够有效恢复重构数据库内丢失数据且显著提升丢失数据恢复重构的准确度，具有较大推广价值。但由于条件限制，存在一定局限性，后续工作可以提升优化参数对复杂数据的处理效率，丰富该领域的研究。