海量数据的相似重复记录检测算法
作者：周典瑞　周莲英
来源：《计算机应用》2013年第08期
        摘 要：针对海量数据下相似重复记录检测算法的低查准率和低效率问题，采用综合加权法和基于字符串长度过滤法对数据集进行相似重复检测。综合加权法通过结合用户经验和数理统计法计算各属性的权重。基于字符串长度过滤法在相似检测过程中利用字符串间的长度差异提前结束编辑距离算法的计算，减少待匹配的记录数。实验结果表明，通过综合加权法计算的权重向量更加全面、准确反映出各属性的重要性，基于字符串的长度过滤法减少了记录间的比对时间，能够有效地解决海量数据的相似重复记录检测问题。
        关键词：海量数据；相似重复记录；综合加权法；编辑距离
        中图分类号： TP311
        文献标志码：A
        0 引言
        高质量的数据是保证企业发展的重要前提，因此为了满足业务的需求，需要整合不同的数据源，由于整合的过程会产生一些语法上相同或相似并且代表同一现实实体的相似重复记录，这样会直接影响数据的质量，因此相似重复记录的清除成为提高数据质量的重要步骤。
        记录间的相似性检测实质上是表征记录的各属性的相似性检测，由于各个属性对于记录之间的差异性贡献不同，应根据属性的重要程度为各个属性赋予相应的权重，以提高检测的精度。海量数据下的数据检测需要使用大量的时间和资源。
        为了检测相似重复记录，目前采用的方法主要有：基本的字段匹配算法[1]、递归的字段匹配算法[2]、基于“排序&合并”方法[3]、采用距离函数模型的方法[4]、基于qgram算法[5]、基于聚类的算法[6]和基于人工智能的算法[7]等。传统的方法在进行相似重复记录检测时，需进行大量的磁盘I/O操作，这将导致时间和空间复杂度很高，基于聚类的算法计算量较大，准确率较低；而基于人工智能的算法推理过程复杂。李星毅等[8]为了提高查全率和检测的精度，采取多趟检测的技术和主观的等级赋权法，增加了大量的检测时间。传统方法多采用滑
动窗口保存重复记录集，窗口的大小指定不合理，导致有些相似重复记录无法正确检测，降低了查全率。
        为了克服以上缺陷，本文对传统的检测方法进行改进，首先采用既考虑主观方面的用户经验又结合客观方面的数理统计方法的综合加权法计算各属性的权重，然后把各属性值作为关键字，利用多线程对数据集并行排序，最后在各线程中采用文献[9]中的优先队列技术依次检测各记录，检测过程中采用基于字符串长度过滤法（加速法）减少不必要记录对之间的比对时间，最终合并检测结果集。
        2 算法设计
        2.1 综合加权方法研究与设计
        记录之间的相似性检测，实质上是属性的相似性检测。由于各个属性对于记录之间的差异性贡献不同，因此应该根据属性的重要程度，为各个属性赋予相应的权重，提高检测的精度。组合赋权的基本思想为：结合主观的用户经验和客观的数理统计方法，全面考虑属性的重要程度，生成合理的权重向量。
        主观方面：李星毅等[8]采用等级法确定等级向量，即首先各用户根据相关经验为各个属性指定一定等级；然后根据均值法计算属性的最终统一等级，生成如表1所示的属性等级表；最后，根据统一等级生成等级向量。
        2.2 多线程并发应用
        海量数据的检测，必须考虑检测时间，如果顺序地对记录集的每一个属性进行排序和相似重复记录检测，势必会浪费大量的时间。本文考虑到共享加载到内存的数据集，采用多线程并发执行相似重复记录检测算法。这样，不仅充分利用计算机资源，同时又能大幅度提高算法的执行效率和相似重复记录的查全率。当所有的数据加载到内存后，如果按照多轮次检测算法，即第一次按照权重最高的属性排序，然后进行检测；如果效果不好，再按照权重次之的属性排序，接着再进行检测；反复进行操作，势必浪费时间。采用多线程的相似检测算法就是按照属性个数开启有限个线程，每个线程中按照属性进行排序，然后执行相同的检测算法，这样既可以减少多轮次检测的时间，又可以保证较高的查全率。
        2.4 优先队列
        传统的记录相似检测采用固定窗口大小的滑动窗口顺序扫描记录集，比较当前记录与滑动窗口中的记录之间的相似性，这样大大减少了记录的比对次数，提高了比对的时间效率。但是由于窗口的大小固定，势必引起漏查或者重复比对的问题。同时，窗口的记录只是单一的一条记录，不能代表某类重复记录的所有特征，同样也会导致漏查现象的存在。针对以上缺陷，采用使用重复记录聚类思想的优先队列代替固定窗口大小的滑动窗口。
        使用优先队列对排序后的记录集进行相似记录检测的思想： 假如当前记录为Ri，优先队列的第一个聚类项代表为Rj，通过计算两者的相似性判断当前记录是否属于该聚类项，如果不相似，则直接与优先队列中的下一聚类项代表记录Rj+1进行比较，直到优先队列的最后一个聚类项代表；如果一直都不相似，则把记录Ri作为一个新的聚类项代表添加到优先队列的头部；如果此时队列中的记录总数超过优先队列上限，则根据“最久未使用”原则，删除优先队列中末尾聚类项。
        如果Ri与Rj相似，说明该记录具有代表性，应该把该记录添加到当前以Rj为代表的聚类项中，并且将Ri作为新聚类项的聚类代表记录，同时把Ri添加到重复记录集中，然后对Ri之后的记录Ri+1继续进行相似检测。每次记录进行比对时，对比较过的聚类项元素进行标记，
如果长时间某些聚类项没有被比较过，说明此聚类项在以后被比较的概率也比较小。因此有必要从优先队列中删除此类聚类项，减少优先队列中的记录，从而减少下一次的比对次数，实现了优先队列的自适应性元素删除功能。
        通过使用优先队列对记录集进行相似重复检测，大大减少记录的比对次数；同时采用聚类思想，避免了因为单条记录不能代表多条重复记录而漏查的现象。该方式不受数据规模的限制，特别适合海量数据的相似检测。
        2.5 算法流程
        首先计算属性的权重，确定每一属性对于记录相似性检测的重要性；然后，多线程并发检测记录集，每个线程针对一个属性对记录集进行排序；最后在每个线程中检测相似重复记录并且合并所有的检测结果。属性相似检测的核心是字符相似度计算，字符相似度的计算通常采用编辑距离算法，由于编辑距离必然大于两字符的长度之差，为了提高检测效率，采用基于字符串长度的过滤策略，即因两字符长度相差较大而相似性较小，省略计算其编辑距离的策略。为了提高检测精度，利用综合加权法计算各属性的权值；并通过多线程并发执行检测算法，有效地提高查全率。
        算法描述如下：
        步骤1
        用户根据属性实际重要程度给各属性指定等级，根据均值法计算各属性的最终统一等级；在各个属性中随机选取一定数目的记录计算其属性取值的种类数，生成属性取值种类数向量，最终把属性等级向量和属性取值种类数向量进行统一化处理，生成属性的权重向量。
        步骤2
        根据属性的个数创建多个线程。
        步骤3
        在每个线程中，按照属性值进行排序。采用优先队列顺序扫描记录集，计算当前记录与队列中记录的相似度；然后根据相似阈值判断记录是否相似，并添加到重复记录集中。
        步骤4
        合并各个线程中的重复记录集。
        3 实验分析
        3.1 实验设计
        实验环境：Intel I3 370 2.40GHz CPU，物理内存2GB，硬盘空间320GB，操作系统Windows 7，数据库软件为Oracle11g，编程语言为Java语言。实验数据来源于镇江市市民信息的采集数据，包括社保的数据、部分试点事业单位的采集数据、财政局的数据等，由于来源广泛、职业的变换导致采集到的数据必然存在大量的重复。度量相似检测算法有效性的三个主要标准包括查全率R（Recall）、查准率P（Precision）和运行时间T（Time）。为了检验论文中检测算法的有效性，设计以下实验。
        文献[8]提出的等级分组方法是一种比较优秀的相似重复记录识别算法，该算法首先根据等级法确定属性的权重，然后选择关键字对数据集进行聚类，最后在各个小的数据集中检测相似重复记录，为了避免漏查，采用多趟查技术。该算法设计简单，时间复杂度小，检测精度较高。因此，选择等级分组方法作为本文所采用方法的参照。为了便于处理，等级分组方法称为RGM，本文的算法称为IWM。分别从数据源中提取四组数据，对两种算法进行比较，四组数据量分别为534万、98.1万、126.2万和153.7万，通过软件和人工等方式对上数
据分别处理，使之分别包含0.46万、0.85万、1.31万和1.44万条相似重复记录。
        4 结语
        针对海量数据下相似重复记录检测问题，本文采取了多种有效策略。首先采用主观因素和客观因素综合考虑的综合加权法计算各属性的权重，然后采用多线程依据各属性对数据集并行排序，使用加速法提前结束记录比对算法；最后合并检测结果集。实验结果表明， 该方法是一个合理、有效的相似重复数据检测方法。本文方法仍有许多未解决的问题，例如：记录之间的相似度阈值大小是根据经验设定的。由于它对记录的检测精度有一定的影响，所以将在以后的工作中继续研究阈值的设定问题。
        参考文献：
        [1]MONGE A E， ELKAN C P. The field matching problem： algorithms and applications [C]// Proceedings of the 2nd Conference on Knowledge Discovery and Data Mining. Cambridge： AAAI， 1996：267-270.
字符串长度统计        [2]MINTON S N， NANJO C， KNOBLOCK C A， et al. A heterogeneous field matchi
ng method for record linkage [C]// Proceeding of the 5th IEEE International Conference on Data Mining. Piscataway： IEEE， 2005： 314-321.
        [3]HERNANDEZ M， STOLFO S. The merge/purge problem for large databases [C]// Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1995：127-138.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。