数据清洗中重复记录清洗算法的研究.doc

数据清洗中重复记录清洗算法的研究.doc数据清洗中重复记录清洗算法的研究摘要: 介绍了数据清洗中的 SNM 算法和全文索引技术, 通过引入全文索引技术对 SNM 算法进行了改进, 以此提高了重复记录查找的速度和准确率,从而较好地提升了 SNM 算法的性能。关键词:数据清洗;全文索引;重复记录;清洗算法中图分类号: TM399 文献标识码: A 1 引言( Introduction ) 数据清洗( Data Clean )就是将错误的、不一致的、冗余的数据在装入数据仓库之前进行删除或修正,[1] 。此项工作中检查并清除重复记录数据是数据清洗要解决的重要问题之一。重复记录就是指现实世界中同一个实体的不同数据记录, 由于表述方式不同或者是因为拼写不同等使得 DBMS 不能识别它们为重复记录。如果这些记录不去掉, 有可能导致数据模型建立的不准确, 从而影响以后的数据决策分析。所以,在数据清洗中,检测并清除掉重复记录是非常重要的。近邻排序算法( Sorted-Neighborhood Method , SNM )是数据清洗过程中的经典算法,而 SNM 算法却需要对数据集进行先期的排序[2] ,全文索引是一种特殊的基于标记的功能性索引, 两者结合, 可以在提高排序速度的同时有效的消除重复记录。 2 SNM 算法( SNM algorithm ) SNM 算法是当前比较流行的一类匹配与合并算法,而且该算法目前已被一些数据清洗工具所采用。目前采用比较普遍的方法是基于近邻排序算法[3] ,它的设计步骤可以分为下面三步: (1 )创建排序关键字,即从数据集中抽取记录属性中的一个属性值或者是子集序列的字串作为关键字, 为数据记录集中每一条记录计算出关键字的键值。(2 )排序。根据该排序关键字对整个数据记录集进行排序。排序中应尽可能地使可能的重复记录排列到一个邻近的区域内, 使得特定的记录可以将进行记录匹配的对象调整到在一定的范围之内。(3 )重复检测。排序后,就可以在排序后的数据记录集上滑动固定大小的窗口, 滑动时, 最先进入窗口内的记录将滑出窗口, 最后一条记录的下一条记录将移入窗口, 数据记录集中新进入的记录与窗口内的记录进行比较。如果窗口的大小为 W 条记录, 则每条新进入到窗口内的记录就要与先前进入窗口的 W-1 条记录进行逐一比较, 以此来检测重复记录, 如不重复, 则把此信进入的第 W 条记录作为下一轮比较对象, 以此类推, 直到完成所有记录集中记录得比较,如图 1 所示。 SNM 算法采用的滑动窗口比较检测重复记录的方法,每次只比较窗口中的 W 条记录, 采用滑动窗口提高了比较速度, 从而有效地提高了匹配效率。但 SNM 算法也存在一些不足:(1 )对排序关键字的依赖性较大。 SNM 算法检测重复记录的精度某种程度上受到创建的排序关键字的限制, 关键字的好坏直接影响了匹配的效率和精度。而且关键字的选取还依赖于应用领域。当选取关键字不当时, 就有可能使得本来是重复记录的两条记录在排序后物理位置相距较远,可能永远不会同时位于同一个滑动窗口内,也就不能被识别出是重复记录,即在重复检测时会漏掉很多重复记录。(2) 滑动窗口的大小 W 的选取也不好选择。 W 较大时比较次数会增多,而有些比较是没有必要的;当W 较小时可