周世杰,娄渊胜

(河海大学计算机与信息学院，江苏 南京 211100)

1 引言

随着社会工业化和信息化水平的不断提高，存储在数据仓库中的数据迅速增加。通过数据挖掘可在这些海量的数据中找出蕴含的重要信息，这些信息往往对信息决策支持系统有重要作用，但挖掘的前提是有高质量的数据。高质量的数据是充分发挥其蕴含的效能的前提和基础，而低质量的数据可能对决策产生不利的影响[1,2]。数据清洗可以对存储在数据仓库中的“问题”数据进行剔除或改正[3]，从而提高数据质量，为决策分析提供数据支撑。数据清洗的主要清洗对象是不完整数据、冲突数据和重复数据[4]，其中需要解决的主要问题是对相似重复数据的查找与去除。相似重复数据是指对于现实世界的同一或类似实体，由于在各数据源存储时可能出现的格式或拼写错误、结构或表述不同等问题，数据库管理系统DBMS(Database Management System)不能准确识别而存储的多条不完全相同的记录[5]。在信息管理系统中，重复数据的存在会影响存储效率，造成数据冗余，识别和消除无用数据可以提高数据质量,保证决策数据的可靠性。

清除相似重复记录常用“排序-合并”的方式，其思想是将待检测的数据集按照某个或某些属性排序，使得数据集中的相似重复记录彼此靠近，然后通过比对邻近位置的记录判断是否为相似重复记录。常见的排序-合并算法包括邻近排序算法SNM(Sorted-Neighborhood Method)[6]、多趟邻近排序算法MPN (Multi-Pass Sorted Neighborhood)[7]和优先队列算法[8]等。……