面向重复记录检测的数据清洗算法的研究

发布时间：2020-04-10 13:00

【摘要】：在现今社会的信息发展过程中,各种来源的数据不断累积,但是原始累积的数据往往含有脏数据,例如错误的、相似重复的和缺失的数据等,对于脏数据进行清洗的一个关键点在于去除数据集中的重复数据。本文主要对相似重复记录检测的相关算法进行了研究与创新。相似重复记录检测是指准确地检测出源数据集中的重复数据,以达到清洗数据的目的。在真实情景中,数据规模庞大,数据来源多样,这都增加了重复数据检测的难度。虽然存在一些解决这类问题的优秀算法,例如近邻排序算法和多趟近邻排序算法等,但是已有的算法在解决实际应用中的重复记录检测问题时,仍存在不足之处。本文首先研究了传统的多趟近邻排序算法,并对该算法的缺点进行改进,提出了优化的多趟近邻排序算法(OMPN),以适用于实际问题;然后,通过研究基于遗传神经网络求解重复检测问题的算法,将OMPN算法与神经网络相结合,得到准确度更高的A-OMPN算法和BP-OMPN算法;最后,将本文提出的OMPN算法应用于“航天情报信息管理系统”的数据清洗模块,该算法在实际应用中得到了较好的效果。本文的主要内容如下:1.优化的多趟近邻排序算法(OMPN)。传统的多趟近邻排序算法首先对数据集中的记录依据预先选取的排序关键字进行排序,使得相似重复记录排序后位置相近,然后使用固定大小的滑动窗口对排序后的数据进行判等。但是,该过程不仅需要依赖专家经验知识进行关键字的选取,而且需要人工选择判等字段,也没有考虑真实数据可能存在数据缺失的问题,同时,固定大小的滑动窗口不仅会导致对重复数据的检测不全面的问题,而且会导致对非重复数据的冗余检测。本文在多趟近邻排序算法的基础上,提出基于字段区分度的关键字选取方法,根据数据的统计特点进行关键字的选取,同时,在判等过程中,同样根据字段区分度为字段赋予不同权值,避免了人为干扰;然后,采用自适应大小的滑动窗口对排序后的记录进行检测,减少了漏检记录数量和冗余操作;最后,对源数据中存在缺失值的记录进行标记和单独检测。通过实验验证,本文所提出的改进的多趟近邻排序算法具有较高的查全率,且更适用于真实问题场景。2.基于神经网络的多趟近邻排序算法(A-OMPN和BP-OMPN)。基于遗传神经网络进行相似重复记录检测的算法效果较好,但是该算法时间复杂度较大,耗时严重。本文将多趟近邻排序算法与遗传神经网络相结合,提出了基于遗传神经网络的增强的多趟近邻排序算法,记作A-OMPN,使得神经网络可以仅对同一个滑动窗口内的记录进行判等,避免了传统的遗传神经网络对数据全集上的任意两个不同的记录进行判等,极大地提高了算法的运行效率。同时,考虑到遗传神经网络训练速度慢的缺点,本文尝试使用单一的神经网络执行判等操作,得到了基于单一神经网络的多趟近邻排序算法,记作BP-OMPN。作为OMPN算法和传统遗传神经网络算法的结合,实验结果表明,A-OMPN算法和BP-OMPN算法能得到比OMPN算法更高的查准率,并且比传统的遗传神经网络算法的运行效率更高。3.本文所提出的OMPN算法在“航天情报信息管理系统”中的应用。本文主要完成了该系统的数据清洗模块和移动端模块的开发。在真实业务场景中,航天情报管理系统的数据清洗模块需要实现对源数据的去重和清洗,因为该系统所使用的数据是真实的不带标签的数据,且数据规模相对较小,所以综合分析OMPN算法、A-OMPN算法与BP-OMPN算法的优势与适用场景,最终采用OMPN算法实现该系统的数据清洗模块。
【图文】：

示意图,流程,示意图

验证流程示意图

示意图,哈希,示意图,路径

图 2.4 Merkle 树哈希值计算示意图树进行完整性证明时，需要获取目的节点的遍历路径e 树的根节点的哈希值，并与存储的根节点的哈希值整性[52]。遍历路径是指由根节点到达目的节点的路径路径是指由根节点到目的节点的路径上所有节点的兄示，，每一个叶子节点存储对应数据块的哈希值，M确性。以2h ( x)节点为例，该叶子节点的认证路径为{径和节点存储的哈希值的关系来计算 MHT 的根节2)|| h ( x ))|| h ( D )|| h ( B))成立。根据 Hash 函数的单向性储的根节点 Root 值就可以判断 MHT 结构的正确性需要更新该节点的遍历路径上的所有节点值即可。性检测方法[52]是为了获得数据完整性证明中所需要历路径和认证路径。用 flag 表示当前节点的访问状还未被访问；若 flag=1，则表示该节点已被访问过
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13

【参考文献】