ETL转换与清洗相关论文

排序后不能完全将重复记录聚集在一起．因此一趟近邻排序算

重复记录。图２描述了一个两趟式的近邻排序扫描方法ｃ

法町能遗漏一些重复记录。为避免这种情况，实行多趟邻近排

序算法，每次采用一个不同的关键字进行排序。下面加以具体介绍。

２

ｌ

基本近邻排序算法（Ｓｏｒｔｅｄ—Ｎｅｉｇｈｂｏｒｈｏｏｄ

Ｍｅ—

ｔｈｏｄ．ＳＮＭ）

给定一个或多个关系表，首先将它们拼接成一个含Ⅳ条记录的数据集，然后采用ＳＮＭ方法。ＳＮＭ方法口ｒ总结为以下三步：

（１）创建戈键字：抽取相关的字段，构造关键字。关键字的选择需要考虑应用的背景．ＳＮＭ执行的精度与关键字的抽取密切相关。

（２）排序：用第一步产生的关键字对数据集进行排序。（３）台，｛：：在排序的数据集上滑动固定大小的窗口．数据集中每条记录仪与窗几内的记录进行比较。如果窗ｕ的大小是ｗ条ｉＬ录，刚每条新进人窗口的记录与窗门内先前＂一ｌ条记录进ｆｊ旺酣比较．最先进入窗口内的记录滑出窗外，如图１所示。

雾

Ｅｉ，＃

ｏ口臼

曰

圈２多趟邻近扫描算法Ｃ以两趟为例

３增量式重复记录识别算法

２

２节描述的ＭＰＮ方法是以一个输入数据集为前提的。

日部分数据集通过重复记录识别处理，分割成一些相似记录聚类后．若再获得模式相同的新的数据集．则必须在执行ＭＰＮ算法之前重新将所有的数据集拼接。ＭＰＮ方法的关键是数据排序，并在整个排序的数据集上进行窗【１扫描．由于完成近邻排

：／

当时亩

口

序扫描的时间正比于输入数据集的大小．将新的数据与已处理的数据进行拼接．将导致数据集的急剧增长．大人增加总的执

行时间，这在时间和空间卜邯是不可取的；而日当数据集增加时．以前的一些重复记录聚类可能消失，这是因为排序后新增加的记录可能插在那些以前他丁＝问

窗口内的柏似ｉｄ录之间．

下。０一

圉１滑动窗口扫描排序数据集示意圈

使得原柬两条相似记录物理位置相距很远，而不能被识别，

在对拼接的数据重新进行处理时．太部分时间花在对已经产牛的聚炎的重新计算Ｅ。如果用于叭配ｉ己录的规则１：变．观察别仅最近到达的增嚣数据可眦改１受当前的聚类，这个结论足增量式重复记录识别处理的棱心。对于每条新增加的记录有以

２

２多趟近邻排序算法（Ｍｕｌｔｉ—Ｐａｓｓ

Ｓｏｒｔｅｄ—Ｎｅｉｇｈ—

Ｆ两种处理：第一，加人一个已存在的聚类；第＿二，创建一十新的聚类。由此，笔者提出增量式ＭＰＮ方法（１ｎｃｒｅｍｅｎｌａｌＭＰＮ，

ＩＭＰＮ）。

ｂ（）ｒｈｏｏｄ。ＭＰＮ）

ＳＮＭ方法汉别重复记录的精度很大程发上依赖于排序所选择的关键字。在数据清理巾．一个关键字不足以将所有重复记录聚集在一起，如果记录中充当或部分充当关键字的字段出现错溟，那么该ｆｄ录很少有机会获得成功的重复记录匹配，例如模式为（ＩｄＣａｒｄ，Ｎａｍｅ，Ａｇｅ，Ｓｅｘ，Ａｄｄｒｅｓｓ）的两条记录，一条

３．１算法描述

ＩＭＰＮ采用ＭＰＮ方法聚类输八数据。ＩＭＩ’Ｎ和ＭＰＮ的最大

区别足前者在多趟近邻扫描前需要进行预处理。在第一次进行

重复记录识别处理时，利用ＭＰＮ方法聚娄数据，然后，每当数据增量到达时，就从上一次产生的每个聚类中选卅一些记录，这些记录表示它们所在聚类的特征信息，称为特征记录或“聚类重心”。这衅特征记录与增量记录进行拼接．再利用ＭＰＮ方法进行处理。最终结果是为每条增量记录指定

个聚类．这些

记求的ｌｄＣａｒｄ值是４２２４００７加２１３００２，另一条记录的ＩｄＣａｒｄ

值是２４２４００７２０２１３００２（最左边的两位数位置颠倒）．若选择ｌｄＣａＴｄ作为关键字，排序后这两条记录物理位置相距较远．不会同时位于较小的滑动窗［１内．因此不能教识别成重复记录。为解决这个问题，可以独立地执行多趟ＳＮＭ算法，每趟使用不同的关键字和相对较小的窗口。最后台并每趟扫描产阜的重复记录。存台并时假定记录的重复具有传递性，即著记录ＲＩ与Ｒ２互为重复记录，Ｒ２与Ｒ３互为重复＇庀录．则Ｒｌ与Ｒ３互为

新的聚类和老的罪类合并冉一起，构成最终识别结粜，图３描述了这一过程。

图４给出了ＩＭＰＮ的算法描述。该算法由一个循环组成，每次循环系统接受一个增量数据集，增量数据集与特征记录拼

—＋

蜘蛆输＾数据羹

臼Ｂ

曰

臼曰

曰

田３增量式ＭＰＮ示意圈

１９２

２００３．１２计算机工程与应用