基于分块和滑窗技术的相似重复记录检测算法研究

陈 亮 杜 璐 胡 康

(西安工程大学计算机科学学院 陕西 西安 710048)

0 引 言

在大数据时代，数据成为有价值的公司资产，可以减少和消除企业经济活动中的风险，为企业的管理控制和科学决策提供合理依据，并预期给企业带来经济利益[1]。公司或企业为了更好地做出决策，往往需要高质量的数据[2]。但是由于各种原因，例如：重复输入、不同数据源中数据采用不同的表示方式、多数据源合并造成重复等数据质量问题，使数据中心中存在着很多的相似重复数据。这些“脏数据”导致了错误的分析结果，进而影响决策。因此数据清洗，尤其是数据清洗中的相似重复数据检测变得尤为重要。

相似重复记录检测就是识别一对记录是否表示为真实世界中的同一个实体。为了避免高代价的记录比对，减少无意义的数据比对次数，有学者提出了一种分区算法，将大量的数据分成更小的子集[3-11]。如果相似记录分布在同个子分区，在数据比对过程中仅与区中的记录比对而不是全部数据[3]。常用的技术是分块技术[4]和窗口技术[5]。其中，分块技术将数据集分成互不相关的子集，在较小的子集内数据聚类；窗口技术通过滑动窗口选中固定大小的数据依次与目标数据来进行记录比对。本文结合了分块技术和窗口技术，提出了一种相似重复检测算法，减少数据比较次数，提高算法运行效率。

1 相关工作

在相似重复记录的检测方面已经有了一些成果。传统的“排序&合并”算法先将数据库中记录排序，然后通过比较邻近记录是否相等来检测完全重复记录。在传统的“排序&合并”思想的基础上，有人提出了近邻排序算法SNM(Sorted Neighborhood Method)[5-15]、分块算法BLOCKING[4]和排序分块算法SBM(Sorted Blocks Method)[3]。

SNM算法根据选定的若干个属性字符串合并作为键对数据集排序，然后采用固定大小的滑动窗口进行聚类来识别相似重复记录。滑动窗口大小的选取难以控制，设定大了，势必增加比较的次数和时间，选取过小，又可能造成算法结果遗漏[6]。BLOCKING算法采用“化整为零”的分区思想对数据排序、分块和聚类，分块间不做相似重复检测。分块的划分直接影响到算法的结果，如果相似记录都划分在同分区，算法有着较高运行效率和满意的结果，反之，算法大部分时间都是无意义的数据比对。SBM算法结合了分块技术和窗口技术，利用滑动窗口选取数据分块并聚类。该算法能够通过滑动窗口技术改善了分块划分问题，但是仍存在一些问题：利用滑动窗口分块导致每个分块之间均有一定量的重复数据，导致了相同数据对多次比对的现象。

针对上述算法的问题，本文参考了MPN算法中滑动窗口思想和BLOCKING算法中的分块思想[12-17]，提出了多排序字段分块近邻匹配算法(MBNM)，目的是为了改善BNM算法中数据多次重复匹配现象，提高算法运行效率。

2 分块近邻匹配重复检测算法

由于多排序字段分块近邻匹配算法(MBNM)是基于分块近邻匹配重复检测算法(BNM)，所以简单介绍BNM算法是非常必要。分块近邻匹配重复检测算法基础思想是：将较大的数据集分为较小的分块，以分块为基础单位完成分块之间的相互比较。优先比较相似数据较多的分块，而从达到在较短时间得到较完整的检测结果的目标。BNM算法的计算过程如下：

(2) 将排好序的数据集分成若干个大小相同的分块bn，用ri来记录数据，分块尺寸为S。

(3) 分块间比较，存在相似重复记录记为1，否则记为0。返回分块间对比的相似重复记录数。

(4) 比较分块延展值，根据设定的阈值判断是否进行二次延展。否则，停止比较，返回相似重复记录数。

(5) 合并分块内相似重复记录结果，从而得到最终的检测结果。

(1)

在实际情况中，最好的排序字段总是不知道或者是难以找到，这样导致BNM算法检验相似重复记录的结果正确性不高。

3 多字段分块近邻匹配算法

3.1 算法介绍

“多趟(multi-pass)”执行方法很好地解决了排序字段难找问题，就是多次执行单字段重复检测算法，每次采用不同排序字段排序。算法如果选取了“不好”的字段，在使用该字段的迭代过程，不但得不到较好的结果，还增加了许多无意义的数据比较次数，浪费了大量的运行时间[6]。

图1展示了MBNM算法的实现过程。比如说第4行第5列的方块表示第4分块中的全部记录和第5个分块中的全部记录的比对，方块中的“9”数字代表存在9对相似重复记录对。分块对(2，2)和(5，5)的相似重复记录数最大，表示着该分块与邻近分块数据更有可能是相似重复记录。接着算法对(2，2)和(5，5)这两个较大的相似重复记录分块对延展。如图所示，算法选择上近邻块对和右近邻块对作为该分块对延展对，并比较新的分块对得到各分块对的相似重复记录数。重复上述过程直到所有的分块对比较结束。

图1 MBNM算法演示图

3.2 算法描述

参考“多趟”执行方法中多排序字段的思想，提出多字段分块近邻匹配算法MBNM(Multi-keys Blocking Neighbor Mapping)。改进算法也采用多个关键字段排序，但不是采用多趟执行的方式，而是多个排序字段一起执行。接下来结合伪代码详细介绍多字段分块近邻匹配算法(MBNM)的四个阶段：

(1) 数据预处理：

算法1数据预处理dataPre(set)算法

输入：原始数据集set

输出：处理后的数据集D

算法对属性进行预处理。它将空格和标点符号视为分隔符，将属性的字符串拆分为单词，并按词法对单词进行排序。

(2) 多关键字定义与排序：

算法2多关键字排序算法

sortData(D,Ks,N,w,LowThreshold)算法

输入：待处理的数据集D和排序字段集Ks

(2) flag=true

(3) for(int i=1;i

(4) for(int j=1;j<=w-1;j++)

(5) for(v=j+1;j<=w;j++)

(6) flag=match(Dj,Dv, LowThreshold)

(7) if(flag==false)

(8) return fales;

(9) else return true

(2)

bn={ri|i=1,2,3,…,w}

(3)

(4)

式中：enm表示n分块和m分块间的相似重复数据存在率，dnnm表示n分块和m分块间的相似重复数据，bcnm表示n分块和m分块间的数据比较次数。

(3) 滑动窗口选取:

分块近邻匹配重复检测算法(BNM)使用固定窗口，窗口大小的选取一直存在问题。窗口选择过小会使得检验的结果不准确，窗口选择过大会增加不必要的比较。新的算法(MBNM)使用自适应的滑动窗口。

首先，设置三个参数:窗口最小值、窗口最大值、阈值。本文定义wmin=4。窗口初始值w=wmin(wmin≤w≤wmax)。如果两个记录的相似度大于阈值，则表示对应窗口内的排序足够好。

(4) 分块比较:

算法3比较算法

compare(blocks,bPairs,order)

输入：待处理的数据集D和排序字段集Ks

输出：比较结果bPairs

(1) for(k=0;k<=|Ks|-1;k++){

(2) bPairs={<1,1,-1,k>,…, }

(3) order[k]=sort(D,Ks[k],S,bPairs)

(4) bPairs=bPairs∪pairs

(5) }

(6) blocks=loadblocks(bPairs,S,order)

(7) compare(blocks,bPairs,order)

(8) bPairs=bPairs∪pBPs

blocks集合保存着分块的数据；bPairs集合用于存放分块对信息，分块对信息采用一个三元组(分块1编号，分块2编号，相似重复记录对数)来表示。分块之间对比形成如图1的分块矩阵，分块矩阵存在对称性，因此只分析行列式的右上部分。采用二元组(bn,bm)表示分块之间的数据对比，相似重复记录用(ri,rj)表，Cnm表示分块n和分块m之间存在相似重复数。

(bn,bm)={(ri,rj)|ri∈bn,rj∈bm}

(5)

|(bn，bm)|=dnnm

(6)

先计算各分块内的相似重复数，得到初始分块对相似重复数据，即(bn,bn)，选取dnnn较大的分块对(bn,bn)并向旁边分块扩展生成新分块对，记作(bn，bm)+。

(bn，bm)+={(bn+1，bm),(bn，bm+1)}

(7)

为了确保分块对能有较高的相似重复数据，设置分块间隙R限制分块对的扩展，减少比较次数。 |n+1-m|≤R&|m+1-n|≤R。

对比新分块对得到各分块对的相似重复记录数。重复上述过程直到所有的分块对比对过。

(5) 计算传递闭包:

由于成对的记录的选取比对，导致运行的结果的不是关闭的，例如(ra,rb)和(rb,rc)被检测出是重复记录，但是最后的运行结果可能没有(ra,rc)。因此，在算法最后中用传递闭包技术不仅能得到较好的重复记录集，并能解决部分纰漏的问题。

3.3 算法复杂度分析

多字段分块近邻匹配算法得时间复杂度主要包括三部分，记作T1、T2、T3。T1表示多关键字选取的时间复杂度，根据检测目标来确定数据集DK，T1=O(N)；算法进行多次排序，排序后调用bPairs函数，因为DK的个数不大于k，T2≤(NlogN+2mw)，mlogN,T3=O(NlogN)。综上所述，MBNM算法的时间复杂度为Θ(n((m+2w)/4+logn))。其他算法时间复杂度[3]如表1所示。

表1 时间复杂度比较

改进算法根据不同的关键字段排序，为了节约内存，改进算法只保存排序后的数据的主键。改进算法在执行时优先选择相似重复率较高分块延展，降低了排序字段本身好坏对算法运行时间的影响。改进算法放弃延展过慢的分块，进一步减少算法中无意义的数据比较，从而提高算法的运行效率。

4 实验结果分析

4.1 实验环境

实验环境是 Lenovo PC CPU Inter(R)Core(TM)2 Duo E8400 @ 3.00 GHz，Ram 2.00 GB，Windows 7 32位操作系统。采用Eclipse Java编程工具实现算法，Java 环境Java 1.7以上。

实验数据来源于某市国家电网用户信息的采集数据，包括用户的用电数据、部分试点事业单位的采集数据等，由于来源广泛导致采集到的数据必然存在大量的重复。度量相似检测算法有效性的三个主要标准包括查全率、查准率和F值，评价算法复杂度的参考标准为运行时间。为了检验检测算法的有效性，设计以下实验。分别从数据源中提取四组数据，对四种算法进行比较，四组数据量分别为58.3、95.1、128.8和136.7万。通过软件和人工等方式对上数据分别处理，使之分别包含0.43、0.87、1.38和1.72万条相似重复记录。对数据集观察分析后，确定使用其中的“name”、“contacts”、“title”三个字段为关键排序字段。

评价标准采用了查全率(Recall)、查准率(Precision)、F值(F-score)和运行时间四个指标来比较四种算法。查全率，查准率，F值计算公式如下：

(1) 查准率:

(8)

(2) 查全率:

(9)

(3) F值(F-score):

(10)

其中TP为被正确识别的重复元组数，FP为错误识别出的重复元组数，FN未识别出的重复记录数。则TP+FP为识别出的重复元组数，包括正确识别的和错误识别的重复元组数。TP+FN为实际存在的重复元组总数。

4.2 相似重复检测算法对比

MBNM算法使用的多关键字排序和自适应滑动窗口来进行数据比较前的处理。由于分块大小和分块间隙对算法效率有直接影响。在保证四种不同算法的分析数据量相同的情况进行了比较实验。四种算法有着明显的差别，比较结果如下：

实验表明，SBM由于只采用传统的固定窗口，识别的结果受窗口大小影响较大。MPN算法由于固定滑动窗口，窗口选取过大或过小对查全率影响较大。由于MBNM采用自适应滑动窗口和多趟检测技术，大大减少记录比对时间和总体测时间，既保证查全率又在一定程度上减少检测时间，从而提高了查全率。如图2所示。

图2 查全率比较图

实验表明，MPN算法由于采用传递闭包，准确率明显较低。在数据量较小时，四者的查准率差异较小，但随着数量的增加，四者查准率都有一定程度的降低，最终趋于稳定。MBNM算法的查准率更加稳定且查准率较高。如图3所示。

图3 查准率比较图

MPN、SBM、BNM、MBNM四种算法的F值与数据量之间的关系如图4可以看出。算法的F值随着数据量的增加而降低，并且四种算法的F值之间的差异越来越大，MBNM略优于BNM算法。

图4 F值比较图

图5比较结果表明，在相同机器、相同数据下，MBNM算法在时间复杂度上有较好的表现。由于利用自适应滑动窗口降低了比较数据集，并利用K关键字多次排序一次执行加快了数据检测的效率。本文提出的算法的时间开销与相似重复记录的多少有关，相似重复记录数越多，则时间复杂度越低，反之越高。

图5 算法消耗时间比较图

综上所述，本文提出的多排序字段分块近邻匹配算法(MBNM)的运行效率优于其他算法。

5 结 语

本文研究了如何检测重复记录，结合了窗口技术和分块技术，提出了分块近邻匹配算法，该算法在限定的时间内提高了相似重复记录匹配的效率。算法通过实时的分块匹配结果动态地改变了匹配数据的顺序，优先对更有希望是重复的数据对进行匹配，并舍弃较差的分块对的比较。减少了算法的比较次数进而减少了算法的时间，并提出了多字段排序和自适应滑动窗口技术改进算法，多个字段同时和自适应滑窗进行分块比较。最后并通过实验和传统“排序&合并”思想中的其他两种算法比较验证了该算法的有效性。接下来的工作就是优化算法的某些过程，进一步缩短算法的运行时间和提高算法的效率并应用到实际中去。