海量数据相似重复记录检测的研究

论文摘要

随着数据库技术的快速发展和广泛应用,各行各业积累的数据量越来越大。在建立数据仓库的过程中,需要从各种异构的数据源导入大量的数据。这些数据来源于不同的渠道导致相似重复记录增多,严重影响了数据利用率和决策质量。因此,相似重复记录的检测和清洗已经成为数据仓库、数据挖掘等领域的热点研究问题。本文详细阐述了数据清洗的相关理论,分析了数据清洗的必要性以及国内研究现状。重点针对海量数据中相似重复记录检测的原理、方法、评价标准以及基本流程进行了深入分析和总结。主要研究工作如下:（1）针对DBSCAN算法聚类时会把相似重复记录聚在较少的几个类中这一问题,通过在随机抽取的样本中引入动态随机函数不断调整密度半径找出最优的全局半径,改进了算法性能。（2）针对海量数据的相似重复记录检测问题,给出了基于熵特征优选分组聚类相似重复记录检测的方法。通过构造一个基于对象间相似度的熵度量,对原始数据集中各属性进行重要性评估,筛选出关键属性集,并依据关键属性将数据划分为不相交的小数据集,在各小数据集中用改进的DBSCAN聚类算法进行相似重复记录的检测。实验表明此算法有较高的检测效率,但检测精度不够理想。（3）给出基于N-Gram的二次聚类方法,提高相似重复记录检测的精确度。首先对每个DBSCAN聚类产生的相似重复记录簇进行二次聚类,然后对每个簇中的记录进行两两分别互相比较,清除了不正确的相似重复记录,实验分析表明二次聚类方法有效地提高了检测精度。（4）搭建了一个基于多Agent的三层数据清洗系统模型。讨论了模型的通信和运行过程。这一模型弥补了传统数据清洗的缺陷和不足,而且分层管理不同任务的工作,在很大程度上提高了数据清洗的智能性和高效性,减少了人工的参与。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 国内外研究现状
• 1.2.1 国外研究现状
• 1.2.2 国内研究现状
• 1.3 课题来源和主要研究内容
• 1.4 论文的组织结构
• 第二章 相似重复记录检测技术与方法
• 2.1 相似重复记录概述
• 2.1.1 相似重复记录介绍
• 2.1.2 相似重复记录清洗过程
• 2.2 记录排序
• 2.3 记录相似性度量方法
• 2.3.1 编辑距离
• 2.3.2 距离函数相似性度量
• 2.3.3 按权相加相似度度量
• 2.3.4 N-gram 字符串匹配算法
• 2.3.5 N-gram 层次空间相似性度量
• 2.4 相似重复记录检测算法
• 2.4.1 优先权队列算法
• 2.4.2 Smith-Waterman 算法
• 2.4.3 近邻排序算法SNM
• 2.4.4 多趟近邻排序（MPN）算法
• 2.4.5 CURE 层次聚类方法
• 2.5 相似重复记录清除方法和评价标准
• 2.5.1 相似重复记录清除方法
• 2.5.2 相似重复记录清洗评价标准
• 2.6 本章小结
• 第三章 DBSCAN 密度聚类算法及改进
• 3.1 DBSCAN 聚类算法介绍
• 3.1.1 聚类及其分类
• 3.1.2 DBSCAN 算法的相关介绍
• 3.1.3 DBSCAN 算法描述及实现步骤
• 3.2 DBSCAN 算法存在的问题及改进
• 3.2.1 DBSCAN 算法在相似重复检测中存在的问题
• 3.2.2 DBSCAN 算法的改进
• 3.3 IDBS 算法的实现
• 3.3.1 IDBS 算法流程
• 3.3.2 IDBS 算法数据结构定义
• 3.3.3 数据库连接和记录的加载
• 3.3.4 IDBS 算法的实现
• 3.4 实验结果及分析
• 3.5 本章小结
• 第四章 基于熵特征优选分组聚类的相似重复记录检测
• 4.1 基于熵特征优选分组聚类算法
• 4.1.1 熵的介绍
• 4.1.2 熵度量对象间的相似度
• 4.1.3 基于熵特征优选分组聚类算法
• 4.2 FSGC 算法的实现和实验对比
• 4.2.1 FSGC 算法流程
• 4.2.2 数据的预处理
• 4.2.3 实验环境
• 4.2.4 实验结果及分析
• 4.3 本章小结
• 第五章 基于N-Gram 算法的二次聚类检测
• 5.1 二次聚类检测的可行性分析
• 5.2 N-Gram 聚类算法及其实现
• 5.2.1 N-Gram 聚类算法思想
• 5.2.2 N-Gram 算法的实现
• 5.3 二次聚类相似重复记录检测
• 5.4 二次聚类后实验分析对比
• 5.5 本章小结
• 第六章 基于多Agent 的三层数据清洗系统模型的设计
• 6.1 Agent 技术及多Agent 系统
• 6.2 多Agent 的三层数据清洗系统模型框架的设计
• 6.2.1 数据清洗中的主要问题
• 6.2.2 基于多Agent 的三层数据清洗系统模型
• 6.2.3 模型系统的通信和工作机制
• 6.3 本章小结
• 第七章 结论与展望
• 7.1 论文总结
• 7.2 未来工作展望
• 参考文献
• 致谢
• 作者在攻读硕士期间主要研究成果