一种基于二分图最优匹配的重复记录检测算法

1、一种基于二分图最优匹配的重复记录检测算法计算机科学与技术学院：李默涵 指导教师：王宏志摘 要： 信息集成系统中存在重复记录，重复记录的存在为数据处理和分析带来了困难。重复记录检测已经成为当前数据库研究中的热点问题之一。目前的方法主要集中在计算具有同样数据类型属性的相似性上，而现实系统中存在大量具有不同数据类型、不同模式的记录。本文针对具有多种类型不同模式的数据的重复记录检测问题，提出了一种基于二分图的最优匹配的记录相似度计算方法，并基于这种记录相似性提出了重复记录检测算法。理论分析和实验结果都表明了方法的正确性和有效性。关键词：信息集成；重复检测；记录相似度；异构记录Abstract： In

2、information integration systems, duplicate records brings challenges for data processing and analysis. The duplicate record detection has become one of the hot issues in database research. Most current methods focus on computing the similarity of the data with same data type. However, there are a la

3、rge number of records with different data type and schema in real system. In this paper, we focus on duplicate records which have different schemas with multiple data types. A method based on optimal matching of bipartite graph is proposed to compute the similarity of the records. Further more, an a

4、lgorithm based on this kind of similarity is proposed to detect the duplicate records. Theoretical analysis and experimental results show that the method proposed in this paper is correct and effective.Keywords： Information integration; Duplicate record detection; Record similarity1 引 言随着信息技术的发展，信息集

5、成系统在许多领域得到了广泛的应用。在信息集成系统中通常存在大量表达相同含义的记录，称为相似重复记录。直接提交包含重复记录的数据会造成数据的冗余，从而造成网络带宽、存储空间等资源的浪费，还会使用户从系统中查询到无用的重复结果，降低系统的可用性。鉴于重复记录带来的危害，需要对其进行检测，并将检测出的重复记录聚为一类，作为一个单元进行处理。重复记录的检测工作带来了技术上的挑战。主要体现在两个方面：一方面，来自于不同数据库中相同含义的数据存在异构表达，表达的异构可能体现在以下三个方面：1）数据物理存储顺序差异，即两条相同记录的同一属性可能存储在记录的不同位置，例如表达同一个学生的姓名和国籍的信息对应着

6、不同记录(J.Smith，England)和(England, J.Smith)。2）数据丢失，即由于模式的不同，有的属性不同时存在于所有数据库；3）个别字符的录入差异，即同样的属性取值可能在录入时存在误差。另一方面，数据源的模式可能不一致，甚至存在数据源模式未知的情况，这使得人们在检测重复记录时很难精确地将两条记录的表达同一含义的属性对应起来。当前的计算记录相似度的方法主要是将整条记录当做是一个整体，然后通过编辑距离等基于字符串比较的属性相似度计算方法得出记录的相似度1。但是这种方法在处理数据的异构表达时存在着一些问题。首先，现有的方法并不能有效的处理数据物理存储顺序差异，例如，记录R1(0

7、07, J.Smith, England)和R2(007, England, J.Smith)是两条完全相同的记录，但是如果将每条记录都当作一个整体计算字符串相似度（如编辑距离），则会低估两条记录的相似度。其次，个别字符不同可能导致整条记录意义的改变，比如记录（J.Smith, M）和（J.Smith, F），当M和F表示性别时，两条记录相似性很高，但表示的是两个重名但是不同性别的学生的信息，这时传统方法又会高估记录的相似度。为了弥补传统的方法上述缺点，本文以关系数据库为基础，提出了快速有效的重复记录检测方法。本文的贡献可以归纳为以下3点：1）研究了在存在异构模式的信息集成系统中进行重复记录检

8、测的问题；2)提出了一种考虑到不同模式、不同类型的记录相似度定义，能够有效表达具有异构模式记录的相似性；3）在本文定义的相似度基础上，提出了一种适用于大规模数据的重复记录检测算法；4）本文从理论和实验两方面验证了本文提出方法的正确性和有效性。本文组织结构如下。第2节介绍重复记录检测的相关工作。第3节对本文研究的重复记录检测问题进行定义。第4节定义属性和记录的相似度。第5节描述本文提出的重复记录检测方法。第6节通过实验验证本文提出的方法。最后给出结论。2 相关工作由于其重要性，当前有一系列检测重复记录检测技术提出。1是对早期重复记录检测工作的综述。文5用记录的相关字段构成键，按照键对相关字段进行

9、排序，并使用滑动窗口的方法进行相似重复记录检测；文6把每条记录看成一个字符串，对记录进行排序，然后使用固定大小的优先队列来顺序扫描所有的已排序的记录，并将它们聚类；文7给每条记录赋予一个N-gram值，将记录排序后使用优先队列对记录聚类；文8将每个字段值分解成多个tokens，对tokens进行排序，进而对记录进行排序，使用滑动窗的方法来比较临近范围的记录。这些工作都未考虑记录的模式异构，不适用于处理具有异构模式的信息集成系统中的重复记录检测。3 问题定义信息集成系统中存在来自多个数据源的数据，不同记录可能具有不同模式和信息表示方式。例如两条来自不同的关系数据库的本科学生信息记录：R1（007

10、，John_Smith，19，England）和R2（007，J.Smith， 19）。R1的模式是Student（id，name，age，nationality），R2的模式是Undergraduate（id，name， age）。R1与R2是重复记录，但它们在多方面存在着不同：它们所在表名分别是Student和Undergraduate；姓名John_Smith在R2中缩写为J.Smith；R2中没有记录学生的国籍信息。此外，对于某些数据源，我们仅能获得记录的内容，却无法获取相应的模式信息。在上述情况下，无法利用简单的并、交、差等运算归类重复记录，而需要对记录的内容加以分析，根据内容的相似

11、程度，确定其是否重复。并且把重复的记录划归一类。本文一共解决3个问题：1)根据内容定义属性的相似度；2)根据属性的相似度定义记录的相似度；3)根据记录相似度对原始数据集合进行重复检测。4 相似度的确定本节介绍属性和记录相似度的定义及计算方法。4.1节定义了属性相似度。4.2节提出基于二分图最优匹配的记录相似度定义和计算记录相似度的算法，并给出算法的复杂性分析。4.1 属性的相似度由于编辑距离2广泛适用于各种类型的属性，我们以编辑距离为基础定义两个属性A1和A2的相似度。在此定义中，编辑距离越大的属性其相似性越小，并且属性的编辑距离被映射到了0,1区间，从而更清晰地表示记录相似的程度。相似度定义

12、如下：将A1和A2看做字符串，其编辑距离为d(A1,A2)、字符串长度分别为len(A1)和len(A2)，则其相似度属性相似度可以利用2中方法计算得的字符串编辑距离求得。时间复杂性为O(len(A1)len(A2)。4.2 记录的相似度基于4.1中定义的属性相似性，本节提出记录的相似性及其高效计算方法。考虑到数据的异构表达，在定义记录相似性时需要首先匹配记录中相同或相似的属性，利用属性的相似度定义记录的相似度。基于这种考虑，提出了一种基于二分图最优匹配的相似度定义，方法如下。根据待比较两条记录Ri和Rj生成一个完全有权二分图B=(V1V2, E, W)，其中V1中每个节点u代表的Ri的一个属

13、性ui，V2中每个节点v代表的Rj的一个属性vj，E=V1×V2, 权函数W:E0,1定义为W(u,v)=Sim(ui, vj), 其中Sim(ui, vj)是4.1中定义的属性相似性。M=(V,E)是B的最优匹配，其中VV1V2，EE。则记录R1和R2的相似度定义为：其中m, n分别代表R1和R2的属性个数。上述方法定义相似度在0,1区间内，使得具有各种长度记录间相似性在同一区间内，从而得以比较，并且有助于用户确定所需要的相似度阈值。计算记录的相似度的关键是求二分图的最优匹配。KuhnMunkras算法3,4（KM算法）是一种求二分图的最优完备匹配的有效算法，通过给属性个数较少的元

14、组添加几个虚拟属性并让和其邻接的所有边的权值都为0，KM算法可以用来计算记录相似性。下面给出算法的具体流程如算法1和算法2所示。算法1描述了由两条记录构造完全二分图的算法。算法2描述了由式(2)计算出记录R1和R2的相似度的方法。其中attribute_similarity(R1i,R2j )返回R1第i个属性和R2第j个属性的相似度。optimal_match(B,w,m)使用KM算法求出二分图的最优匹配，返回最优匹配中所有边权值之和，其中B表示完全二分图，w是B的权值矩阵，m是w的阶。算法1：两条记录中抽象出带权的完全二分图record_to_ bipartite(R1, R2)/ R1,

15、 R2是两条记录1.mR1的属性个数2.nR2的属性个数3.Foreach i, jdo4.wi, j 0/ w 是二分图的权值矩阵5.Foreach i, jdo6./Ri 是R的第i个属性7. wi,jattribute_similarity(R1i, R2j )8. X R1的所有属性, Y R2的所有属性9. if m < n then 向X中加入n-m 个点10.else 向Y中加入m-n个点11. E X中的每个点到Y中所有点均有边12. B (XY, E)13. return （w , B, maxm, n）算法2：计算记录相似度record_similarity (R1,

16、 R2)1. (w,B,m)record_to_bipartite (R1, R2)2. sum optimal_match(B,w,m)3. Sim(R1,R2) sum/m4. return Sim(R1, R2) 图4-1 两条记录生成的权值矩阵及二分图 图4-2 对原始记录集合进行划分例如记录R1(007, John_Smith, England)和R2(008, England, Jane_Smith)，其二分图权值矩阵及完全有权二分图如图4-1所示，二分图中虚线表示的边权值都为0。求出最优匹配，得到两条记录的相似度为0.79。record_to_bipartite(R1, R2)的

17、时间复杂度为O(m2max|A1|A2|)，其中m是两条记录中属性较多的记录的属性数，A1是R1的属性，A2是R2的属性。KM算法的时间复杂度为O(m4)。所以算法的时间复杂度为O(maxm2max|A1|A2|, m4)。算法中最大的空间开销为权值矩阵的开销，空间复杂度为O(m2)。实际数据中，记录中不同属性的重要性不同，如主属性要比非主属性重要。考虑到这个特点，可以给不同的属性赋予不同的属性权值，在计算二分图边权值时将属性权值作为系数。设在记录Ri中，属性v的权值为tv, 在记录Rj中属性u的权值tu, 则考虑到属性权重的代价W(v, u)=W(v, u)×tv×tu。

18、由于仅有边的权发生改变，属性权重的记录相似性计算方法和原来的方法完全相同，这种方法可以提高相似度计算的准确性。其中属性的重要性可以由用户指定。5 重复记录的检测算法本节提出基于第4节中记录相似度的重复记录检测算法以及实现策略。5.1节对重复记录检测进行定义。5.2节提出了集合划分的算法，并在章节的末尾对算法进行优化。5.1 重复记录的定义在一个记录集合中，不能简单根据记录相似性定义记录重复。考虑下面情况，对于记录R1(23, England, 007, J.Smith)、R2(007, J.Smith)和R3(23, England)，R1和R2、R1和R3的相似度都较高，但是R2和R3完全不

19、同。这种情况下，如果简单根据相似性将R1和R2看成重复记录，R1和R3看成重复记录，则R2和R3也应当是重复记录，然而他们并不相似，出现了矛盾。为了避免这种矛盾，只有一个任两条记录的相似度都足够大的聚类中的记录才可以看成是重复对象。于是，数据集合的重复检测可以转化为这样的问题：将原始记录集合R划分成若干不相交的子集（聚类），每个子集中任两条记录都具有较大的相似度。我们给出问题的形式化定义：定义1：给定一个记录集合R=R1,R2,Rm。R上的重复检测定义为：由用户给定一个相似度阈值。将R划分成若干不相交的子集合S1,S2,Sn，满足如下3条性质：1)对于任意子集Si，其中每两条记录的相似度都不小

20、于；2)对于 Si,Sj，ij，有SiSj=；3)对于 Si,Sj，ij，有SiSj不满足条件1）。5.2 记录集合R的划分算法算法的基本思想是顺序扫描记录集合，每次将扫描到的记录归到可能的类中，如果该记录不属于当前的任何类，则建立一个新类。算法使用栈保存已经生成的类，栈中的每个元素对应一个桶，存储该类中的记录。算法的流程如图4-2所示，算法的伪代码在算法3中：初始情况下栈为空（行1），算法每次从记录集合获得一条记录（行2），并从栈顶开始向下搜索与当前记录满足相似度要求的栈内记录（行3-6），每找到一条满足条件的栈内记录，则将当前记录与找到的栈中记录对应的桶内的每条记录比较，如果当前记录和桶中

21、的所有记录相似度都满足要求，则当前记录投入桶，并将相应的栈内记录移至栈顶（行7-10）。否则继续在栈内向下搜索满足条件的记录（行11）。如果在搜索完栈内的所有记录后，当前记录仍没有被投入桶，则将当前记录入栈，置于栈顶（行13）。算法3：对原始记录集合R进行划分Divide_R(R, )1.stack 2.For each Rk R do3. nowstack.top4. Ristacknow5. do6. if Sim(Rk , Ri) >= then7. if 对RjRibucket有Sim(Rk, Ri) >=8.then Rk投入Rj对应的桶;9.将stacknow移至栈顶1

22、0.break11. else now now112.while now = -113. if now=-1 then stack.push(Ri)14. return （stack, buckets）算法结束后，每条栈内记录（称为标志性记录）及其对应桶中记录划归一个集合，所有这样的集合形成对R的一个满足条件的划分。我们仍以集合R=R1(007, John_Smith, M, 19, England)，R2(008, Jane_Smith, F, 18, England)，R3(007, J.Smith, M, 19)，R4(007, J.Smith, M, 18)为例说明划分算法的过程。设=

23、0.6，过程如下：栈初始为空；当前记录为R1，在栈中寻找与R1相似度不小于0.6的记录，由于栈为空，所以找不到满足条件的记录，将R1压入栈，建立新类，置R1对应的桶为空；当前记录为R2，在栈中寻找满足相似度要求的记录，此时栈中为R1，和栈顶的R1比较，不满足，继续在栈中向下寻找，栈中仅有一条记录，找不到满足条件的记录，将R2压入栈，建立新类，置R2对应的桶为空；当前记录为R3，在栈中寻找满足相似度要求的记录，此时栈中为R2 , R1，和栈顶的R2比较，不满足相似度要求，继续在栈中向下寻找，栈中下一条记录为R1，R3和R1比较相似度，满足相似度要求，将R3与R1对应的桶中记录比较，此时R1对应的

24、桶为空，所以R3直接被投入桶，将R1移至栈顶；当前记录为R4，在栈中寻找满足相似度要求的记录，此时栈中元素为R1 , R2，和栈顶的R1比较，满足相似度要求，将R4与R1对应的桶中记录比较，此时R1对应的桶中为R3，R4和R3比较，也满足相似度要求，所以R4被投入R1对应的桶，此时R1已经在栈顶，无需进一步操作；记录集合中的所有记录均被处理，最后的划分结果是两个集合，分别为R2和R1 , R3 , R4。算法的正确性基于以下定理：定理1：算法3可以从记录集合得到满足定义1的划分。证明：根据算法中将元素加入类的条件，划分结果显然满足定义1的性质1）和2）。现在用反证法证明满足性质3）。如果算法得

25、到的结果不满足性质3），则存在Si,Sj，ij，SiSj满足条件1），不妨设Si的标志性记录先于Sj的标志性记录入栈，那么Sj的标志性记录在入栈时一定会被投入Si对应的桶，从而Si和Sj对应相同的桶，而由ij 可以推出Si和Sj有不同的桶，矛盾。所以性质3）也一定满足。正确性得证。（证毕）注意到这个划分可能不唯一，在现实中这是合理的，考虑记录集合R1(23, England, 007, J.Smith)、R2(007, J.Smith)和R3(23, England)，当用户定义=0.5时，此集合上的划分就不唯一，R1既可以划归到R2所在的集合又可以划归到R3所在的集合。对R进行划分时，最坏情

26、况是划分结果中每条记录单独属于一个分类，或者所有记录属于同一分类，在这两种情况下需要O(|R|2)时间。但是，通常情况所需的时间要比最坏情况少的多，因为如果当前记录和栈内的标志性记录的相似度小于时是不需要和相应桶内的记录比较的，所以，通常情况下，记录只需要在栈内进行很少的比较就可以投入正确的桶。算法空间复杂度为O(|R|)。从上面的分析可以看出，算法的瓶颈在于，每条记录入桶时都要经过多次相似度比较。因此对算法效率的优化主要着眼于减少记录相似度的比较次数。精确分类在数据量不大的情况下可以达到不错的效果，但当数据量非常大时，执行效率受到影响。在这种情况下，我们可以以精度换取效率，可以通过多遍分类，

27、逐步细化的策略来提高速度。基本思想是：先对元组进行一遍扫描，将其粗糙的分为若干类，再在这些粗糙分类中进行精确的分类。这样，每次精确分类只需要在这些粗糙分类中进行，使得精确分类要判定的元组数目大大减少，从而提高算法的运行速度。具体的做法类似于算法3。设当前正在检测的记录记为Rk，从栈顶开始，依次和栈内标志性记录（记为Rs）比较相似度，若Rk和Rs的相似度不小于，则投入Rs对应的桶。这样一遍扫描后，桶内记录形成一个粗糙分类。如果得到的粗糙分类仍很大，则在已有粗糙分类基础上再进行多遍粗糙分类。事实上，在记录集合里的记录两两相似度比较大的情况下，也可以仅使用粗糙分类来实现快速分类。逐步细化分类的缺点是

28、最终结果可能会不满足定义1中的性质3）。为了弥补这一缺点，我们可以把标志性记录相似度高的类关联起来，如果用户在当前分类中得不到想要的记录，则可以在与其相关联的分类中寻找需要的记录。此外，重复记录的某些属性(如主键)相似的可能性要比其他属性大。从不同的数据源收集到哪些属性更有可能相似，再根据这些属性对原始记录集合进行排序，在算法执行时可以减少很多的无用比较。6 实验分析本节对第4节和第5节描述的算法进行实验，验证其效率和有效性。6.1说明了实验配置。6.2给出记录相似度计算的实验结果及其分析。6.3给出了原始记录集合R上重复检测的实验结果及其分析。6.1 实验配置实验采用的硬件环境为AMD Se

29、mpron 3000+，内存512M，操作系统为Windows XP，程序代码用Visual C+实现。我们采用自己编写数据生成工具和噪声引入工具来产生实验数据。两条重复的记录可能存在的差异有：1）数据物理存储顺序差异；2）数据丢失；3）个别字符的录入差异。我们针对这三种差别定义了三种修改操作：改变属性的物理存储顺序、随机删除若干属性以及随机改变记录中的若干字符。我们用数据生成工具来产生基准记录，对于一条给定的基准记录，使用上述三种修改操作引入噪声，生成重复记录。6.2 记录相似度计算实验结果及其分析这一节我们通过实验比较本文的记录相似度计算方法和传统的记录相似度计算方法的准确度。基于二分图匹

30、配的方法简记为bi_sim，传统的将记录看做是一个属性的记录相似度比较方法简记为ed_sim。实验使用噪声引入工具对每条记录引入不同的数据差异，生成100条重复记录，分别使用bi_sim和ed_sim来计算每两条记录的相似度，得出平均相似度。实验结果如表1所示：表6-1：不同数据集合上两种方法求得的平均相似度数据编号存在的差别平均相似度bi_simed_sim11）1.00000.779121）和2）0.86000.661531）、2）和3）0.69700.6362由以上数据可以看出，在仅存在物理存储顺序差异时，我们的方法可以准确的计算出1.0000的相似度，传统的方法仅0.7791，高出传统

31、方法0.2209；在物理存储顺序差异的基础上随机增加了至多为50%的数据丢失差异之后，我们的方法得出的相似度仍然高出传统方法0.1985；再随机增加不超过50%的字符录入差异后，我们的方法高出传统方法0.0602，这时准确率略有下降，这是因为在同时存在三种差异时记录本身的差别已经比较大了，很难判定两条记录是不是真正重复。综上来看，我们的相似度计算方法准确性要优于传统的方法。6.3 原始记录集合R重复记录检测实验分析对原始记录集合进行重复检测时，共有3个重要参数：相似度阈值、基准记录数(NR)和每条基准记录对应的重复记录数（ND）。共进行3次实验，每次仅改变一个参数，用平均比较次数来测试重复检测

32、算法的执行效率。对所有记录在被投入正确的桶之前经过的比较次数进行加和，然后除以记录总数，得到平均比较次数。实验结果如表2、3、4所示：表6-2：改变时平均比较次数（NR=100，ND=50）数据编号的取值数据集合大小（|R|）最终得到的分类数目平均比较次数10.3500040类81.1680次20.55000258类16.2186次30.950001192类21.4196次表6-3：NR改变时平均比较次数（=0.5，ND=50）数据编号NR的取值数据集合大小（|R|）最终得到的分类数目平均比较次数11050032类14.0620次2502500192类9.5736次31005000357类10.2918次表6-4：ND改变时平均比较次数（=0.5，NR=100）数据编号ND的取值数据集合大小（|R|）最终得到的分类数目平均比较次数1550095类2.6240次2252500215类7.7716次3505000354类10.4666次从实验结果看来，每条记录只需要经过很少次的比较就可以被投入正确的桶，算法的实际效率要远高于最坏情况。结 论本文研究了具有多种类型不同模式的数据的重复记录检测问题，提出了一种基于二分图的最优匹配的记录相似度计算方法，并基于这种记录相似性提出了重复记录检测算法。理论分析和实验结果表明，这种方法是正确并且有效的。参考文献1. Elm