基于深度学习的数据库重复记录检测算法

陶姿邑

(陕西中医药大学 信息化建设管理处， 陕西 咸阳 712046)

0 引言

随着数据挖掘技术不断发展，每天都会出现大量的数据，为了对这些数据进行有效管理，出现了数据管理系统，由于数据的规模越来越大，数量也急剧增大，出现了一些大型数据库[1]。在数据库管理系统的实际应用中，由于数据库本身的冗余特性，存在一些重复的记录，当重复记录数量过大时，导致数据库存储的空间变大，成本增加，同时对数据库中的记录查询和检索产生不利影响，无法在有效的时间内找到用户真正需要的记录，因此如何减少重复记录是当前数据库管理系统中的一个关键研究问题[2-3]。

数据库重复记录检测是减少重复记录数量的关键技术，为此，许多学者和研究机构对其进行分析，最初学者们引入文本分析方法实现数据库重复记录检测，但是相对于普通文本，数据库记录有自身的特殊性，因此数据库重复记录检测错误率比较高[4]。近年来，一些学者将数据库重复记录检测问题看作是一种二分类问题，即将数据库记录划分为重复和不重复两类，通过引入灰色模型、人工神经网络、支持向量机等建立数据库重复记录检测的分类器[5-7]，灰色模型是一种线性建模方法，而数据库重复记录检测具有较高的非线性变化特点，使得数据库重复记录检测时间长，而且数据库重复记录检测精度低，人工神经网络虽然是一种非线性学习算法，但是其易收敛到局最优解，使得数据库重复记录检测结果出现过拟合或者欠学习现象，导致数据库重复记录检测结果不可靠[8]。支持向量机是一种深度学习算法，具有学习速度快、拟合精度高等优点，在数据库重复记录检测中得到了广泛的应用，但是其参数直接影响数据库重复记录检测结果，目前参数优化问题还没有得到有效的解决[9]。

为了提高数据库重复记录检测效果，提出了基于深度学习的数据库重复记录检测算法。引入支持向量机对数据库重复记录检测进行建模，并采用量子粒子群算法优化支持向量机参数，最后通过数据库重复记录检测仿真实验验证了本文算法的性能。

1 深度学习的数据库重复记录检测算法

1.1 深度学习算法

支持向量机是新型的深度学习算法，相对于传统深度学习算法，其泛化能力更强，学习结果更加可靠，根据工作原理，支持向量机可以划分为两类：一类是支持向量分类机，其用于对一些分类问题进行求解；另一类是支持向量回归机，主要用于预测问题的建模与分析，而数据库重复记录检测是一种分类问题，因此采用支持向量分类机进行。支持向量机的分类原理，如图1所示。

在图1中，中间粗线为所有样本的最优分类平面，黄色矩形的两边为样本和最优分类平面之间的最近距离，两类样本应该处于黄色矩形之外。

图1 支持向量分类机的工作原理

设数据库重复记录检测训练样本集合为：{xi,yi}，xi∈Rn，i=1,2,…,l，xi为数据库重复记录检测的输入向量，yi为数据库重复记录检测的输出，那么基于支持向量机的数据库重复记录检测的最优分类平面，如式(1)。

y=ωTΦ(x)+b=ω·φ(x)+b

(1)

式中，ω和b为权值和偏向量。

要找到数据库重复记录检测的最优分类平面，首先确定最合理的ω和b值，通常情况下，对式(1)无法求解，因为求解的时间相当长，有时难以实现。为了简化ω和b值的求解过程，通过采用松弛因子ξi对式(1)进行相应的转换，得到式(1)的等价形式，如式(2)。

s.t.yi(ω·Φ(xi)+b)≥1-ξi

ξi≥0,i=1,2…,n

(2)

式中，C表示支持向量机的惩罚参数，主要用于评价数据库重复记记录检测结果误差和计算时间的复杂度。

为了进一步优化式(1)求解过程，引入拉格朗日乘子(αi)对式(2)进行变换，如式(3)。

s.t.

(3)

式中，l表示数据库重复记录检测的训练样本数量。

通过对式(3)的求解，可以得到ω的计算公式，如式(4)。

ω=∑αiyi(Φ(xi)·Φ(x))

(4)

支持向量机的数据库重复记录检测分类形式，如式(5)。

f(x)=sgn(αiyi(Φ(xi)·Φ(x))+b)

(5)

式中，Φ(xi)·Φ(x)表示点积运算，sgn()表示符号函数。

当数据库重复记录检测具有随机性、非线性变化特点，Φ(xi)·Φ(x)运行过程十分复杂，这样影响数据库重复记录检测效率，为此采用核函数k(x,xi)代替Φ(xi)·Φ(xj)，加快数据库重复记录检测的速度，如式(6)。

f(x)=sgn(αiyik(x,xi)+b)

(6)

式中，k(x,xi)的表达式，如式(7)。

(7)

式中，σ表示核宽度。

支持向量机的数据库重复记录检测过程中，参数C和σ直接影响建模效果，传统方法采用经验方式确定它们的值，这样难以获得高正确率的数据库重复记录检测结果，为此本文引入量子粒子群算法确定参数C和σ的最优值。

1.2 量子粒子群算法

量子粒子群算法是一种改进粒子群算法，量子粒子群的当前最优位置为mbest，式(8)[10]。

(8)

第i个粒子的d维坐标，如式(9)。

(9)

式中，uid为一个随机数，Kid计算方式，如式(10)

Kid(t)=2β(t)|mbestid(t)-xid(t)|

(10)

式中，t表示迭代次数。

粒子位置更新方式，如式(11)。

xid(t+1)=rid±β(t)×|mbest(t)-Xid(t)|×

ln(1/uid(t))

(11)

式中，β为收缩扩张系数。

当前粒子的最优位Ri，如式(12)。

(12)

式中，f()为目标函数。

1.3 量子粒子群算法优化支持向量机参数步骤

Setp1：初始量子粒子群算法的量子，将参数C和σ的初始值作为粒子；

Setp2：确定量子粒子群的适应度函数值，并根据适应度函数值确定当前粒子和量子粒子群的最优位置；

Setp3：迭代次数增加，并对量子粒子群的个体位置进行更新；

Setp4：计算新种群个体的适应度函数值，并根据适应度函数值对当前粒子和量子粒子群的最优位置进行更新操作；

Setp5：如果达到最大迭代次数，就终止近代，不然返回到Setp3；

Setp6：根据量子粒子群的最优位置得到参数C和σ的最优值。

1.4 深度学习的数据库重复记录检测算法的工作原理

深度学习的数据库重复记录检测算法的工作原理为：首先采用数据库重复记录检测数据，并从中提取记录的特征，采用人工方法对数据库记录类型进行标记，产生数据库重复记录检测的学习样本；然后引入量子粒子群算法确定参数C和σ的最优值，最后采用支持向量机对数据库重复记录检测的学习样本进行训练，建立数据库重复记录检测模型，如图2所示。

图2 深度学习的数据库重复记录检测原理

2 仿真实验

2.1 实验环境

为了分析本文设计的数据库重复记录检测算法的有效性，采用仿真实验环境为CPU(AMD 锐龙R5-3550)，内存为16 GB，硬盘为512 GB SSD，操作系统为Win10，编程软件为Matlab 2017。采用一个大型数据库作为实验对象，共进行5次仿真实验，随机从中选择部分记录进行仿真测试，它们均存在一定数量的重复记录，记录总数量，如表1所示。

表1 五次仿真实验的记录数量

2.2 数据库重复记录检测正确率分析

在相同实验环境下，选择量子粒子算法优化BP神经网络(QPSO-BP)、支持向量机(SVM)，其参数采用随机方式确定，作为参比模型，将表1中的数据库记录根据5∶1的方式划分为训练样本集和测试样本集，统计3种算法的数据库重复记录检测正确率，如图3所示。

图3 数据库重复记录检测正确率对比

对图3进行分析可以得到如下结论。

(1) QPSO-BP的数据库重复记录检测正确率要低于本文算法，这是因为虽然两者都采用量子粒子群算法对参数进行了优化，但是由于BP神经网络本身的缺陷，使得QPSO-BP无法建立最优的数据库重复记录检测模型，导致QPSO-BP的数据库重复记录检测错误率较高。

(2) SVM的数据库重复记录检测正确率同样低于本文算法，这是因为SVM采用随机方式确定参数，而本文算法采用量子粒子群算法对参数进行了优化，建立了更优的数据库重复记录检测模型，减少了数据库重复记录检测错误率，对比实验结果体现了本文算法的优越性。

2.3 数据库重复记录检测效率分析

由于当前数据库向超大规模方向进行发展，重复记录数量相当大，使得数据库重复记录检测效率十分关键，成为算法的一个重要评价标准，统计3种算法的数据库重复记录检测时间，如图4所示。

图4 数据库重复记录检测效率对比

从图4的数据库重复记录检测时间可以看出，本文算法的数据库重复记录检测时间要明显少于对比算法，大幅度提升了数据库重复记录检测效率，可以用于大型数据库重复记录检测，具有更高的实际应用价值。

3 总结

重复记录检测对于提升数据库检索效率，找到用户真正需要的数据具有重要意义，针对当前方法检测重复记录时检测结果不理想的问题，提出基于深度学习的数据库重复记录检测和优化方法，仿真实验结果表明，本文算法是一种精度高、效率快的数据库重复记录检测算法，为解决大型数据库重复记录问题提供了一种新的研究工具。