海量数据相似重复记录检测算法

《海量数据相似重复记录检测算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、海量数据相似重复记录检测算法　　摘要：针对海量数据下相似重复记录检测算法的低查准率和低效率问题，采用综合加权法和基于字符串长度过滤法对数据集进行相似重复检测。综合加权法通过结合用户经验和数理统计法计算各属性的权重。基于字符串长度过滤法在相似检测过程中利用字符串间的长度差异提前结束编辑距离算法的计算，减少待匹配的记录数。实验结果表明，通过综合加权法计算的权重向量更加全面、准确反映出各属性的重要性，基于字符串的长度过滤法减少了记录间的比对时间，能够有效地解决海量数据的相似重复记录检测问题。关键词：海量数据；相似重复记录；综合加权法；编辑距离中图分类号：TP311文献标志码：A0引言高质量

2、的数据是保证企业发展的重要前提，因此为了满足业务的需求，需要整合不同的数据源，由于整合的过程会产生一些语法上相同或相似并且代表同一现实实体的相似重复记录，这样会直接影响数据的质量，因此相似重复记录的清除成为提高数据质量的重要步骤。9记录间的相似性检测实质上是表征记录的各属性的相似性检测，由于各个属性对于记录之间的差异性贡献不同，应根据属性的重要程度为各个属性赋予相应的权重，以提高检测的精度。海量数据下的数据检测需要使用大量的时间和资源。为了检测相似重复记录，目前采用的方法主要有：基本的字段匹配算法[1]、递归的字段匹配算法[2]、基于“排序&合并”方法[3]、采用距离函数模型的方法[

3、4]、基于qgram算法[5]、基于聚类的算法[6]和基于人工智能的算法[7]等。传统的方法在进行相似重复记录检测时，需进行大量的磁盘I/O操作，这将导致时间和空间复杂度很高，基于聚类的算法计算量较大，准确率较低；而基于人工智能的算法推理过程复杂。李星毅等[8]为了提高查全率和检测的精度，采取多趟检测的技术和主观的等级赋权法，增加了大量的检测时间。传统方法多采用滑动窗口保存重复记录集，窗口的大小指定不合理，导致有些相似重复记录无法正确检测，降低了查全率。9为了克服以上缺陷，本文对传统的检测方法进行改进，首先采用既考虑主观方面的用户经验又结合客观方面的数理统计方法的综合加权法计算各属性

4、的权重，然后把各属性值作为关键字，利用多线程对数据集并行排序，最后在各线程中采用文献[9]中的优先队列技术依次检测各记录，检测过程中采用基于字符串长度过滤法（加速法）减少不必要记录对之间的比对时间，最终合并检测结果集。2算法设计2.1综合加权方法研究与设计记录之间的相似性检测，实质上是属性的相似性检测。由于各个属性对于记录之间的差异性贡献不同，因此应该根据属性的重要程度，为各个属性赋予相应的权重，提高检测的精度。组合赋权的基本思想为：结合主观的用户经验和客观的数理统计方法，全面考虑属性的重要程度，生成合理的权重向量。主观方面：李星毅等[8]采用等级法确定等级向量，即首先各用户根据相关

5、经验为各个属性指定一定等级；然后根据均值法计算属性的最终统一等级，生成如表1所示的属性等级表；最后，根据统一等级生成等级向量。2.2多线程并发应用9海量数据的检测，必须考虑检测时间，如果顺序地对记录集的每一个属性进行排序和相似重复记录检测，势必会浪费大量的时间。本文考虑到共享加载到内存的数据集，采用多线程并发执行相似重复记录检测算法。这样，不仅充分利用计算机资源，同时又能大幅度提高算法的执行效率和相似重复记录的查全率。当所有的数据加载到内存后，如果按照多轮次检测算法，即第一次按照权重最高的属性排序，然后进行检测；如果效果不好，再按照权重次之的属性排序，接着再进行检测；反复进行操作，势

6、必浪费时间。采用多线程的相似检测算法就是按照属性个数开启有限个线程，每个线程中按照属性进行排序，然后执行相同的检测算法，这样既可以减少多轮次检测的时间，又可以保证较高的查全率。2.4优先队列传统的记录相似检测采用固定窗口大小的滑动窗口顺序扫描记录集，比较当前记录与滑动窗口中的记录之间的相似性，这样大大减少了记录的比对次数，提高了比对的时间效率。但是由于窗口的大小固定，势必引起漏查或者重复比对的问题。同时，窗口的记录只是单一的一条记录，不能代表某类重复记录的所有特征，同样也会导致漏查现象的存在。针对以上缺陷，采用使用重复记录聚类思想的优先队列代替固定窗口大小的滑动窗口。使用优先队列对排

7、序后的记录集进行相似记录检测的思想：假如当前记录为Ri，优先队列的第一个聚类项代表为Rj，通过计算两者的相似性判断当前记录是否属于该聚类项，如果不相似，则直接与优先队列中的下一聚类项代表记录Rj+1进行比较，直到优先队列的最后一个聚类项代表；如果一直都不相似，则把记录Ri作为一个新的聚类项代表添加到优先队列的头部；如果此时队列中的记录总数超过优先队列上限，则根据“最久未使用”原则，删除优先队列中末尾聚类项。9如果Ri与Rj相似，说明该记录具有代表性，应该把