ETL转换与清洗相关论文

巍

＿与＃★信带＿Ｉ｜息＊

孽

近似重复记录的增量式识别算法

许向阳佘春红

（华中科技大学计算机学院数据库与多媒体技术研究所，武汉４３００７４）

Ｅ－ｍａｉｌ：ｅｈｕｎｈｏｎｇ＠ｐｕｂｌｉｅ．ｗｈ．ｈｂ．ｃｎ

摘蒌数据清理是敷据仓库中的一个重要研究内容，近似重复记录的识剐爰其中的一个技术难点。文章介绍了近邻排

序方法．并以此为基础，研究了在敷据模式与匹配规则不变的前提下．数据源动态增加时近似重复记录识别问题，提出了一种增量式算法ＩＭＰＮ（１ｎｅｒｅｍｅｎｔｔｄＭｕｌｔｉ—Ｐａｓｓｓｏｒｔｅｄ—Ｎｅｉｇｈｂｏｒｈｏｏｄ）。文章最后给出了实验结果。关键词

数据清理

近似重复记录

增量式识别

特征记录

中图分类号ＴＰ３ｌｌ１３

文章编号１００２—８３３１一（２００３）１２－０１９１—０３文献标识码Ａ

ＩｎｃｒｅｍｅｎｔａｌＡｌｇｏｒｉｔｈｍｆｏｒＤｅｔｅｃｔｉｎｇＡｐｐｒｏｘｉｍａｔｅｌｙ

ＤｕｐｌｉｃａｔｅＤａｔａｂａｓｅＲｅｃｏｒｄｓ

ＸｕＸｉａｎｇｙａｎｇ

ＳｈｅＣｈｕｎｈｏｎｇ

（Ｄｅｐｔ．ｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＨｕａｚｈｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆ

Ｓｃｉｅｎｃｅ

Ａｂｓｔｒａｃｔ：Ｄａｔａ

ｏｎｅ

ａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７４）

ｏｆｄａｔａ

ｗａｒｅｈｏｕｓｅ．Ｄｅｔｅｃｔｉｎｇ

ａｐｐｒｏｘｉｍａｔｅｌｙｄｕｐｌｉｃａｔｅｄａｔａｂａｓｅ

ｏｉｌ

ｃｌｅａｎｉｎｇ

ｉｓ

ａｌｌ

ｉｍｐｏｒｔａｎｔ

ａｒｅａ

ｒｅｃｏｒｄｓｉｓ

ｏｆ

ｔｅｃｈｎｏｌｏｇｙ

ｄｉｆｆｉｃｕｈｉｅｓＴｈｉｓ

ｐａｐｅｒｉｎｔｒｏｄｕｃｅｓｓｏｒｔｅｄ—ｎｅｉｇｈｂｏｒｈｏｏｄｍｅｔｈｏｄ．Ｂａｓｅｄ

ｒｅｃｅｉｖｉｎｇｉｎｃｒｅｍｅｎｔｓ

ｏｆ

ｄａｔａ

ｔｈｉｓ

ｎｏ

ｉｄｅａ，ｉｔ

ｓｔｕｄｉｅｓｔｈｅｐｍｂ—

ｄａｔａｔｈｅ

ｓｅｈｅｎｌａｅｘｐｅｒｌ—

ｌｅｍ缸ｒｄｅｔｅｃｔｉｎｇａｐｐｒｏｘｉｍａｔｅｌｙｄｕｐｌｉｃａｔｅｒｅｃｏｒｄｓｗｈｉｌｅａｎｄｍａｔｃｈｉｎｇｍｅｌｌｔａｌｒｅｓｕｌｔｓ．

ｒｕｌｅ—ｓｅｔ．ａｎｄ

ｐｒｅｓｅｎｔｓ

ａｎ

ｗｉｔｈ

ｃｈａｎｇｅｓｉｎ

ｇｉｖｅｓ

ｏｕｔ

ｉｎｃｒｅｍｅｎｔａｌａｌｇｏｒｉｔｈｍｆｏｒｄｅｔｅｃｔｉｎｇｔｈｅ

ｒｅｃｏｒｄｓ．Ｆｉｎａｌｌｙ，ｉｔ

Ｋｅｙｗｏｒｄｓ：Ｄａｔａｃｌｅａｎｉｎｇ，Ａｐｐｒｏｘｉｍａｔｅｌｙｄｕｐｌｉｃａｔｅｒｅｃｏｒｄｓ，Ｉｎｃｒｅｍｅｎｔａｌ

ｄｅｔｅｃｔｉｏｎ，Ｒｅｐｒｅｓｅｎｔａｔｉｖｅｒｅｃｏｒｄ

ｌ引言

在建造数据仓库过程中，需要从各种数据源导人大量数

ｂｏｒｈｏｏｄ，ＭＰＮ）和Ｍｏｎｇｅ提出的优先队列策略（ＰｒｉｏｒｉｔｙＱ．ｅｕｅＳｔｒａｔｅｇｙ，ＰＱＳ）在不影响识别精度的情况下。对记录比较和排序

进行改进，提高了响应时间，更适于识别莺复记录。

据。这些数据中存在数据录入错误、同一对象在不同数据源中

的表示各异等质量问题，使得应用于数据仓库前端的决策支持系统产生错误的分析结果而误导决策，影响信息服务的质量。

上述重复记录识别算法均以一个输入数据集为前提。如果系统接受到一个新的数据集．必须将其与早期已处理的数据集进行拼接，再对拼接后的整个数据集进行处理。该文主要考虑在数据模式与匹配规则不变的前提下，输人数据集动态增加时

重复记录识别问题，提出了一种增量式莺复记录识别算法．在识别精度基本保持不变的情况下，该算法大大节省了执行时间与空间的开销。

文章其余部分的结构如下：在下一节将描述基本的邻近排

因此数据仓库构建中的一个重要的任务是通过数据清理，将数

据转换为一致的形式．保证数据的正确性。

数据清理主要涉及到数据的映射（ｍａｐｐｉｎｇ）、匹配（ｍａｔｃｈ．ｉｎｇ）和合并（ｍｅｒｇｉｎｇ／ｐｕｒｇｉｎｇ）。通过映射，将数据格式标准化；通过匹配，发现重复的对象；通过合并，保留或生成一个完整的对象。数据清理活动的核心是近似重复对象的识别。所谓近似重复对象是指表现形式不同但语义上相间的对象”Ｉ，从狭义的

序和多趟邻近排序方法；第３节提出增量式算法．并介绍两种两处理策略；第４常给出对比实验及结果；第５节对全文进行

总结。

角度来看．如果两条记录在某些字殷上的值相等或足够相似．刚认为这两条记录互为近似重复．该支仅考虑狭义的近似熏复

记录，并简称为重复记录。

识别重复记录的直观方法是采取排序一合并方式，将每一

条￣己录与数据库中其他记录进行比较．该方法的识别精度相当高，但在大数据量的情况下。其处理时间难以忍受。Ｈｅｒｎａｎｄｅｚ

２近邻排序方法

近邻排序算法首先对数据集进行排序，然后根据排序的顺序，对范围相对较小的邻近记录应用一些具体的匹配规则进行比较，找出莺复记录。基于这样一个观察：一个简单的关键字在

等人提出的多趟近邻排序方法…１（Ｍｕｌｔｉ—Ｐａｓｓ

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

基金项目：国家科技攻关计划项目“科技部科技电子政务系统关键技术厦应用系统的研究”（编号：２００１ＢＡＩｌＯＢ０１】作者简介：许向阳，副教授．主要研究领域为数据库．数据仓库技术。余春红．硕士研究生，主要研究顿域为数据仓库技术。

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

１９１