基于CSSN算法的重复记录检测研究

摘要

重复记录检测问题已有半个世纪的研究历史，这个问题所具有的重要实际意义以及挑战性使得其一直是一个非常热门的研究方向，吸引了包括统计学、生物学、数据挖掘、机器学习、人工智能、信息检索、知识工程、数据库等等领域的大量专家学者。本文对重复记录检测算法进行了研究，主要工作有:
　　(1)对重复记录检测领域进行了广泛调研并详细综述了相关研究成果。首先将重复记录检测工作分为三个阶段，然后对各个阶段使用的技术和算法进行了归类整理，最后归纳总结了重复记录检测的评价标准和检测框架。
　　(2)针对一个典型的基于聚类的CSSN重复记录检测算法进行了算法效率改进。首先对CSSN算法的功能性能进行了实验验证，并详细分析了算法各步骤的时间复杂度，然后在分析基础上来降低算法的时间复杂度。实验表明，效率改进后的CSSN算法可以在基本不影响算法准确度的情况下将算法的时间复杂度从原来平方级的降低至近似线性的。
　　(3)对效率提高后的CSSN算法进行了通用性扩展。首先对CSSN算法的通用性局限进行了深入分析和实验验证，然后在实验分析基础上提出了模糊紧密集合等五方面的通用性改进措施。实验表明，通用性改进后的CSSN算法在各种重复度的数据集下均可达到很高的查准率和查全率。

目录

摘要

图目录

表目录

第1章 绪论

1．1 研究背景

1．2 研究现状

1．3 本文研究意义

1．4 本文研究内容

1．5 本文组织结构

第2章 重复记录检测综述

2．1 重复记录检测问题

2．2 选取记录对进行相似度比较的算法

2．2．1 分块

2．2．2 滑动窗口

2．2．3 聚类

2．2．4 基于物化相似表的方法

2．3 字段匹配算法

2．3．1 基于字符的相似性度量

2．3．2 基于Token的相似性度量

2．4 重复记录匹配算法

2．4．1 基于概率模型的方法

2．4．2 有监督机器学习方法

2．4．3 主动学习方法

2．4．4 基于距离度量的方法

2．4．5 基于规则的方法

2．4．6 无监督机器学习方法

2．5 重复记录聚类算法

2．5．1 传递性划分聚类算法

2．5．2 中心聚类算法

2．5．3 Star聚类算法

2．5．4 基于紧密集合和稀疏近邻原则的聚类算法

2．6 重复记录检测算法评价标准

2．7 重复记录检测框架

2．8 本章小结

第3章 CSSN重复记录检测算法效率改进

3．1 CSSN重复记录检测算法

3．1．1 CSSN算法核心概念

3．1．2 CSSN算法流程描述

3．1．3 CSSN算法实现描述

3．2 CSSN重复记录检测算法功能和性能验证实验

3．2．1 重复记录检测实验设置

3．2．2 查准率、查全率实验结果与分析

3．2．3 算法运行时间实验结果与分析

3．3 CSSN重复记录检测算法的效率改进分析

3．3．1 第一阶段：生成每条记录的近邻信息

3．3．2 第二阶段： 基于紧密集合和稀疏近邻原则对记录进行聚类

3．4 CSSN重复记录检测算法的效率改进实现

3．4．1 第一阶段：生成每条记录的近邻信息

3．4．2 第二阶段：基于紧密集合和稀疏近邻的原则进行聚类

3．5 CSSN重复记录检测算法效率改进后的实验与分析

3．5．2 算法运行时间实验结果与分析

3．6 本章小结

第4章 CSSN重复记录检测算法通用性扩展

4．1 CSSN重复记录检测算法的通用性问题

4．1．1 CSSN算法通用性局限分析

4．1．2 CSSN算法通用性局限验证实验

4．1．3 通用性局限验证实验结果与分析

4．2 CSSN重复记录检测算法的通用性改进分析

4．2．1 相似度近邻列表查找标准的改进：K与Θ共同约束

4．2．2 近邻评判标准的改进：相似度近邻的相似程度

4．2．3 紧密集合评判标准的改进：模糊紧密集合

4．2．4 紧密集合查找顺序的改进：从中心到边缘

4．2．5 稀疏近邻条件的改进：渗透稀疏近邻

4．3 CSSN重复记录检测算法的通用性改进实现

4．3．1 第一阶段：每条记录的近邻列表计算

4．3．2 第二阶段：基于模糊紧密集合原则进行聚类

4．4 CSSN重复记录检测算法通用性改进后的实验与分析

4．4．1 仿真数据集上的实验结果与分析

4．4．2 真实数据集上的实验结果与分析

4．5 本章小结

第5章 总结与展望

5．1 工作总结

5．2 研究展望

参考文献

致谢