一种针对关系数据库记录的相似重复记录检测算法

马可 郑广海

摘要：在大数据处理分析中，需要对数据记录进行相似重复记录检测并消除，可以提高数据记录的质量。邻近排序算法（SNM算法）是对数据库所有记录进行排序比对，新记录和旧记录都需要比对，而旧记录的相互比是已经做过的，这就造成了一定的计算浪费。在考虑尽量减少这种计算浪费的基础上，提出了一种针对关系数据库记录的相似重复记录检测算法，算法首先创建记录属性关系表，设定属性的相应权重和相似度阈值，通过属性关系表计算记录和其他记录的相似度，从而完成对相似重复记录的检测。实验表明新的算法的效率比SNM算法有一定提高。

关键词：相似重复记录；snm算法；检测

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2018）13-0025-04

1引言

隨着移动互联网、物联网的迅速发展，大数据时代正在不同程度影响着我们的生活。企业收集、处理的数据越来越多，各类应用数据库中存在着大量的脏数据，这些数据可能与业务无关或错误格式或不规范描述甚至相似重复的数据。这些不正确的记录，影响企业数据统计分析利用的效率与准确性，甚至可能对企业的决策过程起到错误的帮助。这些相似重复记录是不正确的，相似重复记录严重损害了数据的一致性，造成了一定程度上的数据冗余，产生了资源的浪费，对数据的准确性产生了影响。如何处理这些脏数据是我们面临的挑战。

要处理这些相似重复记录，可以通过常用算法，如聚类算法，N-Grams算法[1]，字段匹配算法等识别出相似重复记录，随后通过人工或代码进行清除处理；也可以通过基于排序和合并的算法对数据库相似重复记录进行识别，并找出的重复记录进行删除或合并操作。基于排序和合并的常用算法有邻近排序算法（SNM算法），多趟近邻排序算法（MPN算法）等[2-7]。

针对邻近排序算法，张建中[8]提出来对滑动窗口的大小采取动态变化和窗口的移动速度进行动态变化，使得改进后SNM算法比传统SNM算法的效率得到了提升；余肖生[9]提出了对记录进行字符串单词化处理，较好地弥补了传统算法的缺陷，得到了比传统SNM算法更好的效果；李军[10]提出了对数据进行预处理，使记录格式更加规范，采用预处理后算法性能得到提升。殷秀叶[11]针对记录的属性，提出了同级属性的概念，利用同级属性进行检测大大缩短了检测时间，提高了检测的效率。郭文龙[12]针对客户关系数据库提出了一种清洗算法，获得了较好的效果。刘雅思[13]提出来基于长度过滤和动态容错的SNM改进算法，使得准确率和时间效率获得了显著提升。宋兴国[14]利用R-树检索提出了DRR算法，获得了更高的准确率和时间效率。杨巧巧[15]提出来基于聚类分组和属性综合权值的SNM改进算法，获得了查全率和查准率的提升。

从上述文献的论述中，我们可以看出存在这样一个问题，关系数据库记录量往往不是一成不变的，随时间变化而变化。在添加了新记录后，使用SNM算法对所有记录进行排序比对时，不仅要对新记录和旧记录进行比对，还有在旧记录之间相互比对，这些旧记录的相互比对往往是过去已经做过的，这样就造成了一定的计算浪费。在此基础上，本文在SNM算法基础上提出了一种改进算法，一种针对关系数据库记录的相似重复记录检测算法即ISNM算法（improved sorted-neighborhood method）。SNM算法是通过对记录按照一定要求方法进行排序，从而进行附近比较，而改进ISNM算法在SNM算法基础上添加了一定的记忆功能，对记录进行分类存储，通过调取在同一分类的记录进行比对而不是原本的附近比对，使得改进算法不用对已经处理过的记录进行重复比对。

2 算法描述

2.1相关定义

我们提出的ISNM算法，是基于SNM算法，在SNM算法中添加记忆信息，以减少比对次数，称为记忆邻近排序算法。算法具体处理过程是先将记录按照属性创建属性关系表，把记录按照每个属性的属性值进行分类，查找具有相同属性值的其他记录进行相似度检测，从而找出相似重复记录。为了描述方便，我们给出如下定义：

定义1 设数据库记录一共有n个属性。每个属性都有一定的判读可能性即权重

2.2构建亲属记录

考虑到记录可能没有唯一标识的主键，或者姓名身份证号码作为主键时可能这些主键有错误内容。根据数据库记录，创建唯一表示记录的属性编号，编号属性权重为0。可以通过编号找到该记录，也方便存储。按照记录创建属性关系表，把所有属性分成不同的属性库，每个属性库记录该属性所有的属性值表，每个属性值表里存放着具有该属性值的所有记录的编号。如果手动输入，大量记录的工作量十分巨大，考虑代码输入记录。首先创建属性库，这些属性库创建后都是空库。按照编号从小到大的顺序依次读取数据库记录，对属性库进行访问，查询该记录的属性值对应的属性库的属性值表。如果存在该属性值表，就在该属性值表加入该记录；如果不存在，就在属性库中添加该属性值表，并在属性值表里存入该记录编号。读取完记录后，属性库和属性值表填充完毕。

2.3 ISNM算法

改进算法简单地说就是对于新纪录和所有旧记录的比对，如果一一比对，计算量是非常大的。而两个记录在某属性是非亲属记录，其相对于的相对相似度为0，那么只要找出相对相似度不为0的相对相似度求其和就是两个记录的相似度。相对相似度不为0只有亲属记录，可以通过属性关系表，找到这些亲属记录，利用亲属记录求记录的相似度。亲属记录相对所有记录来说是非常少的，利用亲属记录可以大量减少计算量。

步骤如下：

Input（R，W，U）

For（a= 0；a

For（b=0；b

SimR（Ra，Rb）=0；//初始化所有相似度

For（s=0；s

{For（p=1；p<=n；p++） //n表示属性个数

{

//根据s记录的第p属性的属性值，

//读取属性关系表s记录的第p属性的所有亲属记录

Select p属性 from 属性关系表s记录 where s记录的第p属性值=亲属记录

Insert into 亲属记录表

Simp（Rs，Ri）=Wp；

//i是亲属记录是数据库第i个记录

SimR（Rs，Ri）+= Simp（Rs，Ri）；

If（SimR（Rs，Rj） > U）

output（Rs，Rj）

SimR（Rs，Rj）=0；//赋值为0，防止重复出现该对相似重复记录

}

}

3 实验分析

3.1实验方案和配置

在同样实验环境条件下使用ISNM算法和传统SNM算法对同一数据集进行处理。实验数据来自某地区的数据库，8万条左右记录，8个属性。实验中随机提取2万，4万，6万，8万条记录进行测试，对提取的这些记录进行处理使其成为包括187，259，337，421条相似重复记录的数据集。使用人工方式统计检测出来的相似重复记录和正确识别的相似重复记录。在总数据集为8万条记录的基础上，每次随机提取1万条，2万条，4万条，8万条作为数据集的新纪录，分别计算两种算法消耗的时间。

本文实验计算机配置：处理器Inel（R）i-4210M CPU @ 2.60GHz 双核，8GB内存，1T硬盘；操作系统：windows8.1；软件mysql+vs2013。

要验证改进算法的优劣，通常的标准是计算查重的查准率RZ和查全率RQ。查准率表示检测出来正确的相似重复记录在所有检测出来的相似重复记录的比例，数据记录的查全率表示检测出来正确的相似重复记录在数据库里实际存在的相似重复记录的比例。设MSJ表示数据库实际存在的相似重复记录，MZQ表示检测出来正确的相似重复记录，MJC表示检测出来的所有相似重复记录。则查准率RZ和查全率RQ的计算公式如下：

查准率RZ=MZQ /MJC，查全率RQ=MZQ /MSJ。

3.2结果与分析

根据上面的内容，在相同的实验条件下，使用SNM算法和ISNM算法对同一数据集进行对比实验 。实验的结果如图1-图2所示。图1表示了利用SNM算法和ISNM算法得出的查准率RZ。图2表示了利用SNM算法和ISNM算法得出的查全率RQ。

从图1可以看出，ISNM算法的查准率始终高于传统SNM算法，提高了检测相似重复记录的效率，虽然随着数据量的增加，二者的准确率都有一定程度的下降，但是ISNM算法依然保持较高的准确度，而且其下降趋势也小于传统SNM算法。

从图2可以看出，ISNM算法显著提高了查全率。传统SNM算法因为排序规则导致一些相似重复记录无法被检测到。而ISNM算法使用相对合适的阈值U，其查全率几乎达到了100%，解决了传统SNM算法可能因为排序规则导致一些记录无法被检测的问题。

从图3可以看出，往数据集添加新数据后，ISNM算法处理时间小于传统SNM算法。传统SNM算法要对所有记录进行排序比对，不仅有新纪录之间的比对，新旧记录的比对，还有大量旧记录之间的比对。而ISNM算法不会包含旧记录之间的比对，减少了大量的计算量。ISNM算法仅对新数据记录进行检测，从数据库调取新记录的亲属记录进行处理。虽然可能处理某些新数据记录消耗的时间比使用传统SNM算法要高，但不会像传统SNM算法对所有记录进行处理，只对新纪录进行处理，在时间效率上得到提升。对于现代企业数据库来说，增加的记录和自身总数据量相比很小，使用ISNM算法比使用传统SNM算法消耗的时间要小很多。

4 小结

在数据库中存放在大量的数据记录，一些记录因为现实收集处理中的可能存在的错误，使得这些记录构成了相似重复记录，通过一定的算法可以对这些相似重复记录进行检测，方便数据库维护人员进行修改，提高了数据库记录的准确性和有效性。本文提出的ISNM算法对数据库记录进行处理，检测相似重复记录，取得了较好的效果。然而也存在一些不足之处，如果处理完全是新的记录集，没有过去的记录集，消耗的时间与传统SNM算法消耗的时间没多少差别，极端情况下甚至更高。而且凭经验设置属性权重和相似度值，现实使用中应设置多大没有进行讨论以及减少物理内存地址占用，这将是接下来研究的工作。

参考文献：

[1]邱越峰，田增平，季文贇，等.一种高效的检测相似重复记录的方法[J].计算机学报，2001（1）：69-77.

[2]Zhang， Zhongnan，He， Ling，Tan， Yize，Liao， Minghong. A Heuristic Approximately Duplicate Records Detection Algorithm Based on Attributes Analysis[J]. EN，2012，6（4）.

[3]WenfeiFan，ShuaiMa，NanTang，Wenyuan Yu. Interaction between Record Matching and Data Repairing[J]. Journal of Data and Information Quality （JDIQ），2014，4（4）.

[4]he merge purge problem for large databases. Mauricio A H，Salvatore J S. Proceedings of the ACM SIGMOD International Conference on Management of Data， 1995

[5]李堅，郑宁.对基于MPN数据清洗算法的改进[J].计算机应用与软件，2008（2）：245-247.

[6]郭文龙.一种改进的相似重复记录检测算法[J].计算机应用与软件，2014，31（1）：293-295.

[7]郭文龙，董建怀.基于模糊综合评判的相似重复记录清洗方法[J].北京信息科技大学学报（自然科学版），2017，32（4）：59-63.

[8]张建中，方正，熊拥军，等.对基于SNM数据清洗算法的优化[J].中南大学学报（自然科学版），2010，41（6）：2240-2245.

[9]余肖生，胡孙枝.基于SNM改进算法的相似重复记录消除[J].重庆理工大学学报（自然科学），2016，30（4）：91-96.

[10]李军.一种相似重复记录检测算法的改进与应用[J].成都工业学院学报，2017，20（2）：17-20.

[11]殷秀叶.大数据环境下一种高效的重复记录检测方法[J].洛阳师范学院学报，2014，33（11）：52-54.

[12]郭文龙.一种客户关系数据库相似重复记录清洗算法[J].衡水学院学报，2014，16（1）：15-17.

[13]刘雅思，程力，李晓.基于长度过滤和动态容错的SNM改进算法[J].计算机应用研究，2017，34（1）：147-150+155.

[14]宋国兴，周喜，马博，等.基于R-树索引的高维相似重复记录检测改进算法[J].微电子学与计算机，2017，34（9）：97-102.

[15]杨巧巧，郭振波，王开西.基于聚类分组和属性综合权值的SNM改进算法[J].工业控制计算机，2017，30（9）：27-28+31.