大数据量的高效重复记录检测方法

1、第38卷 第2期2010年 2月 华 中 科 技 大 学 学 报(自然科学版)J.HuazhongUniv.ofSci.&Tech.(NaturalScienceEdition)Vol.38No.2 Feb. 2010大数据量的高效重复记录检测方法庞雄文 姚占林 李拥军122(1华南师范大学计算机学院,广东广州510300;2华南理工大学计算机科学与工程学院,广东广州510640)摘要:针对目前重复记录检测方法不能有效处理大数据量的问题,提出了一种高效的重复记录检测方法.根据概念依赖图计算表的关键属性,并根据关键属性值将数据划分为记录集,在划分后的记录集中进行重复记录检测,大大减少需要

2、比较的记录数,提高算法的效率;在记录集内进行重复记录检测时,将已匹配的记录合并后和已有的记录重新比较,提高了算法的准确度和效率.实验数据显示在大数据量情况下,计算效率提高47%.关 键 词:数据处理;重复记录检测;检测方法;概念依赖图;数据清洗中图分类号:TP274 文献标识码:A 文章编号:1671-4512(2010)02-0008-04EfficientduplicaterecordsdetectionmethodformassivedataPangXiongwen YaoZhanlin LiYongjun122(1ComputerSchool,SouthChinaNormalUnive

3、rsity,Guangzhou510300,China;2CollegeofComputerEngineeringandScience,SouthChinaUniversityofTechnology,Guangzhou510640,China)Abstract:Atpresent,theduplicaterecordsofmassivedatacannotbedetectedeffectivelybycurrentmethods.Thusanefficientduplicaterecordsdetectionmethodformassivedataispresented.Themethodf

4、irstlypartitionsrecordsaccordingtothekeyattributeswhicharecalculatedusingconceptde-pendencygraph,andthendetectsduplicaterecordsineachclassofkeyattributevalues;itcanreducethenumberofrecordcomparisonsgreatlyandimprovetheefficiencyofduplicatedetection.Toim-provetheperformanceofduplicatedetection,themet

5、hodfirstlymergesthematchingrecordsintoanewrecord,andthenre-comparesthisrecordwithrecordsintherecordset.Weexperimentallyevalu-atethemethodwithactualdataandrevealthattheexecuteefficiencyisimprovedupto47%formas-sivedata.Keywords:dataprocessing;duplicaterecordsdetection;detectionmethod;conceptdependency

6、graph;datacleaning目前重复记录检测中记录级的匹配方法主要可以分为3类1,2:机器学习方法;领域知识方法;基于距离函数的方法.一般常用的方法是排序-合并算法3和二次聚类算法4,5.这些方法在大数据量的情况下效率比较低.针对目前重复记录检测方法不能有效处理大数据量的问题,本文提出了一种高效的重复记录检测方法.在记录集内进行重复记录检测时,将已收稿日期:2009-06-25.作者简介:庞雄文(1972-),男,博士,E-mail:augepang.基金项目:广东省安全生产科研专项资金资助项目(x2jsB2080910);广东省自然科学基金资助项目(9451063101002213)

7、.匹配的记录合并后和已有的记录重新比较,以提高算法的准确度和效率.1 关键属性1.1 概念依赖图用概念依赖图来计算表的关键属性6,7.定义1 概念依赖图.设C为关系表名,有N第2期 庞雄文等:大数据量的高效重复记录检测方法#9#个属性,ai表示C中第i个属性,C的依赖图使用方阵M来表示:M=(mij),其中mij=K(ai,aj)(iN,jN).在方阵M中,K(ai,aj)为属性ai和aj之间的互信息,若i=j,则表示属性ai的信息熵.所以在方阵中,节点为信息熵,节点之间的边为两个节点之间的互信息.互信息和自信息的计算公式为H(s)=-K(s,t)=xIs关键属性的确定是以计算属性的互信息为基

8、础,因此计算表C关键属性的算法复杂度为O(abk),其中a=1,b为C中属性个数,k为C的记录数量,在大数据量情况下k很大,不可能使用全部数据来计算关键属性;实际使用时可将数据先抽样,用抽样后的数据来计算关键属性.计算表的关键属性后,再按照关键属性值将大记录集划分为小记录集,在小记录集中进行重复记录检测.Ep(x)logp(x);(1)xIsEEp(x,y)yIt2,(2)p(x)p(y)式中:p(x)为数据属性s的实例x在s的整个取值范围内分布的概率;p(y)为数据属性t的实例y在t的整个取值范围内分布的概率;p(x,y)为数据属性s和t的一个实例对在s,t的整个取值范围内分布的概率.假设关

9、系表包括A,B,C,D4个属性,则关子表的依赖图如图1所示.位于节点左(右)的数据表示节点的自信息,两节点之间的数字表示两节点之间的互信息.2 重复记录检测方法在重复记录检测中,对于检测出的重复记录,一般有以下2种处理方法:a.保留一条记录作为主记录,其他重复记录删除;b.保留一条记录作为主记录,其他重复记录中的信息合并到主记录后删除.在此采用第2种处理方法.2.1 基本概念设R为关系表(该表有有限个属性),记录集I=r1,r2,rn,则匹配函数M定义为RR上的一个布尔函数,该函数用于判断记录集I中的两条记录r1和r2是否重复.若M(r1,r2)为真,则表示r1和r2是重复记录,记为r1Ur2

10、;否则不是重复记录.文中并不涉及采用何种方法判断两条记录是否相似.合并函数L是RR上的一个偏序函数,用于合并两条重复记录,合并后的记录中包含两条原始记录的内容.r1和r2是重复记录,r12是r1和r2合并后的记录,记为3r1,r24;合并函数L只能定义在已经配对的重复记录上.合并函数L具有结合性和传递性,具体如下:图1 关系表的依赖图定义2 依赖图中节点的权值.对依赖图中某一个属性节点ai权值H(ai)=K(ai,ai)+j=1,jXiEnK(ai,aj)-(3)k=1m=1,mXknEEnnnK(ak,am)n,式中:j=1EK(ai,aj)为该节点和其他节点的互信,jXi息之和;kEEK(

11、ak,am)为依赖图中所有节点=1m=1,mXk与其他节点的互信息之和.定义3 属性的权重.关系表中某一属性的权重等于在依赖图中该属性对应的节点权值与所有节点权值和的百分比,即Ai=H(ai)i=1na.合并函数的结合性.Pr1,r2,r3,若有3r1,3r2,r344且33r1,r24,r34存在,则3r1,3r2,r344=33r1,r24,r34.b.合并函数的传递性.若r3=3r1,r24,则Pr4满足r1Ur4,r3Ur4.2.2 重复记录检测方法两条记录之间的比较需要比较该记录的所有属性字段以及计算各属性字段的权重,算法复杂度很高;若能减少记录之间的比较次数,则可以提高算法的效率8

12、.若r1和r2是重复记录,则将合并后的新记录3r1,r24添加到结果集中,因3r1,r24包含r1和r2的内容,故可以从记录集中删除r1和r2,同时停止该记录和其他记录的比较.据此可描述重复(EH(a).in(4)1.2 关键属性识别定义4 关系表的关键属性.设C为关系表名,有N个属性,Ai为C中第i个属性的权重,先将属性按照权重大小排序(倒排),权重之和大于0.#10#华 中 科 技 大 学 学 报(自然科学版) 第38卷输入:按关键属性值划分的记录集;输出:无重复记录的结果集.算法程序如下:IczªM赋初值为空whileI!=doM对I中每条记录循环currentRecordza

13、recordfromIM取当前记录removecurrentRecordfromIM将当前记录从结果集I中删除buddyznullM中间变量赋初值forallrecordsrcinIcdoM对Ic中每一个记录rc循环处理ifM(currentRecord,rc)=truethenM若Ic中当前记录和I中当前记录是重复记录buddyzrcM暂存rcexitforM退出比较,不执行剩余比较endifendforifbuddy=nullthenaddcurrentRecordtoIcM未找到重复记录,将I中当前记录增加到Ic中elserdz3currentRecord,buddy4M合并重复记录re

14、movebuddyfromIcM从Ic中删除原记录addrdtoIM将合并后的记录增加到原始结果集I中endifendwhilereturnIcM返回删除重复记录后的Ic根据算法的执行过程(限于篇幅,算法执行过程略),假设记录集中记录数为N,重复记录数为J,则算法复杂度最大为(N-1)2-(J-1)(J-2)/2,可见算法的复杂度和重复记录数有关,重复记录数越大,算法的复杂度越小;在重复记录检测算法中,记录集是按照记录的关键属性值划分的,该记录中的所有记录具有相同的关键属性值,重复记录数较多,因此该重复记录检测算法需要比较的记录数很少,算法复杂度小,效率高.2.3 带限制规则的重复记录检测方法

15、在以上算法中,只要两条记录匹配就可以合并,但实际上由于数据来源不同导致同一记录的相同属性存在相反(相斥)的值,如表1所示.记录r12是r1和r2合并后记录,可以看出性别属性存在两个值(男和女),实际上不可能一个人既是男1r2,记录号r1r2r12表1 重复记录及其合并记录姓名证件号电话性别男女男女PXBNo10288342222PB888322090612333PXBNo100288342222PB888322090612333能合并,因为合并后的新纪录违反了实际情况.为了处理这种情况,引入了限制规则9,10.定义5 限制规则.判断记录集中一条记录或者多条记录是否一致的规则称为限制规则.限制规

16、则:a.一元规则.判断一条记录r是否有效的规则称为一元规则.例如判断表1中r12是否有效,若r无效,则记为r3X4r;若有效,则记为rr.b.二元规则.判断两条记录r1和r2是否可以合并的规则称为二元规则.若r1和r2不能合并,则记为r13X4r2;反之记为r1r2.当属性的值是多选一且属性相斥时,就为该属性定义一个一元规则;典型的一元规则:性别不可能同时出现男女两个性别.典型的二元规则:一个人不能有两个身份证号码,记录合并时,若证件类型是身份证且号码相同,则违反该规则.限制规则具有传递性和交换性.交换性定义为:Pr1,r2,若r13X4r2,则r23X4r1.传递性定义为:a.一元规则的传递

17、性,若r13X4r1且r3=3r1,r24,则r33X4r3;b.二元规则的传递性,若r13X4r2且3r1,r34Xr2,则3r1,r343X4r2.根据以上讨论,可描述出带限制规则的重复记录检测方法.3 实验分析3.1 实验设置实验数据来自某航空公司的会员信息表(30个属性,500万条记录),由于业务系统中允许一个会员申请多张会员卡,在数据挖掘过程中为了准确表达一个会员的行为,需要将有多张会员卡(重复记录)的会员找出来,并清除重复记录.实验步骤为:a.识别该表的关键属性.使用抽样数据(将会员按照省份分组、每组取1%的数据)进行计算.b.识别出的关键属性为证件号、英文名称/拼音.c.按照关键

18、属性将数据划分为小记录集,在每一个小记录集中进行重复记录检测,记录之间的相似性采用Jaccard距离来度量.d.设置的限制规则包括:一个会员不能有两个性别;一个会员不能有两个级别;若两个记录是重复记录,则身.第2期 庞雄文等:大数据量的高效重复记录检测方法#11#(%)3.2 实验结果采用文献3中的排序合并算法作为对比.在商业的重复记录检测方法中SQL2008中的模糊分组方法是有代表性的产品,所以采用模糊分组法来检测重复记录,并以其作为对比方法.3.2.1 执行时间比较本文算法执行时间和其他算法的比较如表2所示,实验数据显示在大数据量情况下(300万行),SQL2008的执行时间是232min

19、,本文算法的执行时间是124min,计算效率提高47%.这是因为本文算法先是按照关键属性将数据集划分为小的分组,然后在小的分组中进行重复记录检测,大大减少了记录之间的比较次数,缩短了算法的执行时间,这也正是本文算法的最大优点.表2 执行时间比较执行时间/s行数/100.11.010.0100.0200.0300.0表4 查准率比较行数/1040.1模糊分组本文算法001.010.0100.0200.0300.0100.00100.0097.6496.4395.41100.00100.099.0399.0598.97本文算法主要适用于大数据量重复记录所占比例较小的情况.下一步的工作是修改算法以适

20、应大数据量下重复记录所占比例很大的情况.参考文献1AhmedK,PanagiotisG,Vassilos,etal.Duplicaterecorddetection:asurveyJ.IEEETransactionsonKnowledgeandDataEngineering,2007,19(1):1-16.2AnestisSitas,SarantosKapidakis.Duplicatedetec-tionalgorithmsofbibliographicdescriptionsJ.L-ibraryHiTech,2008,26(2):287-301.3韩京宇,徐立臻,董逸生.一种大数据量的相似

21、记录检模糊分组0.150.937.2276.57139.80232.41排序合并本文算法0.171.01测方法J.计算机研究与发展,2005,42(12):2206-2212.4McCallumA,NigamK,UngarLH.Efficientclus-teringofhigh-dimensionaldatasetswithapplicationtoreferencematchingCMSixthACMSIGKDDIntclConfKnowledgeDiscoveryandDataMining.NewYork:ACMPress,2000:169-178.5ChaudhuriS,Ganjam,K,GantiV,etal.RobustandefficientfuzzymatchforonlinedatacleaningCMACMSIGMODInternationalConferenceonManagementofData.NewYork:ACM,2003:313-324.6JaewooKang.Towardthescalableintegrationofin-ternetinformationsourcesD.Madison:ComputerSciencesD