（计算机应用技术专业论文）关系数据库数据清理技术研究.pdf

长奋t 业人学硕j 。学位论文 摘要 在当今世界，企业信息化的要求越来越迫切，其中一个重要的方面就是企业的数 据的管理。根据“进去的是垃圾，出来的也是垃圾”这条原理，为了支持正确决策， 就要求所管理的数据可靠，没有错误，能准确地反映企业的实际情况，因此企业数据 质量的管理正在获得越来越多的关注。 在现实中，数据一般都存在各种各样数据质量问题，含有各种类型脏数据。数据 清理是提高数据质量的重要途径。针对这一课题，论文包括如下几个方面的研究工作： 相似重复记录清理 对于相似重复记录的清理，本文着重从重复记录识别和相似记录检测两方面进行 了研究。重复记录识别本文主要研究了基本邻近排序方法和优先队列算法；相似记录 匹配本文分析了几种核心的字段匹配算法，针对字段值的特点采用基于编辑距离的字 段匹配算法，同时设计了利用有效权值和长度过滤的优化算法进行记录匹配，减少相 似重复记录的检测时间，提高算法的效率。 空缺数据清理 对于空缺数据的清理，本文设计了一种清理方案。首先分析数据的可用性；然后 删除不可用记录；最后，对可用记录通过选用填充空缺值的方法来处理该记录的空缺 数据，从而完成数据源中空缺数据的清理。 空缺数据，并对判定树归纳法进行了变形。 度也较高。 错误数据清理 本文着重分析了判定树归纳的方法来处理 实验证明，判定树归纳变形算法速度快精 针对数据源中出现的错误数据，研究了如何采用业务规则这种方法来检测错误数 据的重要性，并设计了将数据分类与平滑结合的算法去除噪声。这种算法既能对数据 进行平滑，减少孤立点出现的可能，又不会出现因为进行平滑而改变了数据所处类的 问题。 数据清理框架 结合以上所分析和研究的算法，本文设计了一种数据清理框架。它是集成了一系 列数据清理方法，并能利用具体业务知识、可扩展的数据清理工具框架。这样方便使 用者从丰富的数据清理工具中选择适合领域问题的清理方法，从而提高数据清理算法 在不同应用中的清理效果。 k 春丁业大学硕j 学位论文 关键词：数据清理相似重复记录空缺数据清理错误数据清理数据清理框 架 i i 长春t 业大学硕 学位论文 a b s t r a c t n o w a d a y s ，t h ed e m a n do fi n f o r m a t i o nl e v e lo fe n t e r p r i s ei sm o r ea n dm o r eu r g e n t ，t h e m a n a g e m e n tf o rt h ee n t e r p r i s ei n f o r m a t i o ni s o n ei m p o r t a n ta s p e c t a c c o r d i n gt ot h e p r i n c i p l eo f “g a r b a g ei n ，g a r b a g eo u t , i tn e e d st h ee n t e r p r i s eh a sr e l i a b l ed a t a , t r u ed a t a w h i c hr e f l e c ta c t u a lc i r c u m s t a n c eo ft h ee n t e r p r i s ew i t ht h eo b j e c to fs u p p o r t i n gd e c i s i o n m a k i n g t h e r e f o r e , t h er e s e a r c hp a y sc l o s ea t t e n t i o nt ot h em a n a g e m e n to f d a t aq u a l i t yo f t h e e n t e r p r i s e i nr e a l i t y , t h ed a t au s u a l l ye x i s ta l lk i n d so fp r o b l e m sf o rd a t aq u 丑l i t y , a n dh a v ea v a r i e t y o fd i r t yd a t a d a t ac l e a n i n gi sa ni m p o r t a n tm e t h o df o ri m p r o v i n gd a t aq u a l i t y a i m i n ga t t h i s ，t h ep a p e rc o n t a i n st h er e s e a r c ho f s o m ea s p e c ta sf o l l o w s ： 。c l e a na p p r o x i m a t e l yd u p l i c a t e dr e c o r d s i no r d e rt oc l e a na p p r o x i m a t e l yd u p l i c a t e dr e c o r d s ，t h ep a p e r m a i n l yr e s e a r c h e so nr e c o r d s o r ta n dr e s e m b l er e c o r dd e t e c t i n g r e c o r ds o r t a n l y s e ss o r t e dn e i b e r h o o ds t r a t e g y , p r i o r i t yq u e u es t r a t e g y r e s e m b l er e c o r dd e t e c t i n gs t u d i e sf o rt h em a t c hp r o b l e m sb e t w e e n f i e l d s w ep u tf o r w a r dt h ef i e l dm a t c ha l g o r i t h ma n da b b r e v i a t i o n - d i s c o v e r e da l g o r i t h m b a s e do ne d i td i s t a n c e i nr e c o r dm a t c h , w ea l s oc a m eu pw i t ht h eo p t i m i z e dm e t h o du s i n g v a l i dw e i g h tv a l u ea n dl e n g t hf i l t e r i n gt or e d u c et h er a n t i m eo f 硎酬a l g o r i t h ma n d i m p r o v ei t se f f i c i e n c y c l e a ne m p t yd a t a i no r d e rt oc l e a ne m p t yd a t a , w ed e s i g nac l e a ns c h e m e f i r s t ，d e t e c t sw h e t h e re a c hr e c o r d i nd a t as e ti su s e f u l ，a n dt h e nd e l e t e st h eu s e l e s sr e c o r d f i n a l l y ，t h em i s s i n gd a t ai nu s e f u l r e c o r di sd i s p o s e du s i n ga p p r o p r i a t em e t h o d t h u s ，e m p t yd a t ai sc l e a n e d t h ep a p e rm a i n l y a n a l y s e sd e c i s i o nt r e ed e d u c t i o nm g o f i s mt oc l e a ne m p t yd a t a ，a n di m p r o v eo ni t a c c o r d i n g t ot h ee x p e r i m e n t ，t h ei m p r o v e da l g o r i s mh a sb e t t e rs p e e d ，b e t t e rp r e c i s i o n c l e a ni n c o r r e c t n e s sd a t a i no r d e rt oc l e a ni n c o r r e c t u e s sd a t a , b u s i n e s sr u l e st od e t e c ti n c o r r e c t n e s sd a t ai ss t u d i e d t h ep a p e rp u t sf o r w o r dam e t h o dt h a tc o m b m e sd a t as o r tm e t h o dw i t hs m o o t h n e s sm e t h o d t ow i p eo f f “y a w p ”i tc a nn o to n l ys m o o t hd a t a , r e d u c ea p p e a r a n c eo fi s o l a t e dp o i n t s b u t a l s oa v o i dt h ep r o b l e mo f m i s t a k e sf o rd a t ac l a s s i f i n g d a t ac l e a n i n gf i a l n e i nt h ee n d ，t h ep a p e rd e s i g n sad a t ac l e a n i n gf l a m e i ti sae x t e n s i b l ef r a m et h a tc o n t a i n sa s e r i e so fd a t ac l e a n i n ga l g o r i s m s ，a n dm a k e su s eo fb u s i n e s sr o l e i tl e tt h eu s e r sc h o o s e i i i k 备1 二业人学硕i ：学位论文 a p p r o p r i a t em e t h o d s t h u si i l c r e a s ed a t ac l e a n i n ge f f e c t s k e yw o r d s ：d a t ac l e a n i n g ，a p p r o x i m a t e l yd u p l i c a t e dr e c o r d s ，e m p t yd a t a ，i n c o r r e c t n e s s d a t a , d a t ac l e a n i n gf l a m e l 乏备t 业人学硕 学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体己经 发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均己在文中 以明确方式标明。本声明的法律结果由本人承担。 5 8 论文作者签名：痞乙哿 日期：，绅7 年弓月fe l 长备工业人学颂1 1 学位论文 第一章绪论 1 1 论文选题的背景 随着数据库量的迅猛增长向科学家、工程师和销售人员提出了一个挑战：在大量 的数据中，是不是会隐藏着有价值的东西呢? 如何充分有效地使用这些数据进行科学 研究、系统优化以及发现商业数据内在关系及其可说明的问题，便成为一个很重要的 课题。此外，作为全球信息系统的万维网的流行，己经将我们淹没在数据和信息的汪 洋大海中。存储数据的爆炸性增长业已激起对新技术和自动工具的需求，以便帮助我 们将海量数据转换成信息和知识。数据挖掘技术因此应运而生。 目前尚无关于数据挖掘的精确学科划定，从广义上来讲，数据挖掘( d a t a m i n i n g ，叫) 是从巨大的数据体系或数据库里提炼出我们感兴趣的东西( 可能在我们意 料之中，也可能在我们的意料之外) ，或者说，从庞大的观察数据集中提炼并分析出不 能轻易察觉或断言的关系，最后给出一个有用的并可以理解的结论。简单地说，数据 挖掘就是在数据中发现模式、知识，或数据问的关系。 数据挖掘也常被称为知识发现( k n o w l e d g ed i s c o v e r y ，k d ) “3 ，所以许多知识发现 中的算法，比如人工智能，常常被使用于数据挖掘的过程中。1 9 8 9 年，在第1 1 届国际 人工智能的专家研讨会上，学者们首次提出了基于数据挖掘的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，l ( d d ) 概念。1 9 9 5 年在美国计算机年会上，一些学者开始把数 据挖掘视为数据库知识发现的一个基本步骤或两者视为近义词讨论。 数据挖掘步骤可以与用户和知识库交互，有趣的模式提供给用户，或作为新的知 识存放在知识库中。根据这种观点，数据挖掘只是整个过程的一步。因此，我们可以 得出数据挖掘的广义定义“1 ：数据挖掘是从存放在数据库、数据仓库或其他信息库中的 大量数据中挖掘有趣知识的过程。 1 2 本课题的提出 随着电子数据的不断累积，人们越来越希望从大量的数据中提取出有用的信息供 决策使用，但是由于各种各样的原因，如数据输入错误、不同来源数据引起的不同表 示方法，数据间的不一致等。1 ，导致现有的数据中存在这样或那样的脏数据( 即存在数 据质量问题”1 ) 。它们主要表现为：拼写问题、录入错误、不合法值、空值、不一致值、 简写、同一实体的多种表示( 重复) 、不遵循引用完整性等“1 。由于“垃圾进、垃圾出” “1 ，在某些应用系统，特别是数据仓库、k d d 及t d q m ( 综合数据质量管理) 中，必须对 数据进行清理。数据清理保证信息源的数据质量，从而保证了辅助决策的原始数据的 正确性和准确性。没有数据清理，很可能就会导致错误的决策，因此数据清理是构建 k 眷t 业人学碗i 。学位论文 数据仓库和知识发现的必要因素。它直接关系到获取的知识的质量和数据挖掘算法的 效率。因此，对这方面做一些研究是不言而喻的。数据清理处理的对象都是大型的数 据源，因而它的计算量非常大，手工来做这个工作几乎是不可能的。所以其研究重点 一般放在数据清理框架。 1 3 数据质量描述 数据清理的工作是去提高数据的质量。不同领域对数据质量的要求不同。数据质 量一般都体现为一系列规则，按符合规则的程度，来判断数据的质量。领域不同，定 义的规则也就不完全相同，但有一些规则是任何领域都需要的。准确的、高质量的数 据必须满足以下几个规则： 数据是准确的。数据值与客观实体相一致。 数据与定义的数据类型相一致。二维表属性( f i e l d s 或a t t r i b u t e s ) 定义了某 种数据类型( 数值型、字符型、整型等) ，元组( t u r p l e s 或r e c o r d s ) 必须与它一 致。 数据有完整性定义。必须正确定义参照完整性，防止数据被意外的破坏和改变。 数据是一致的。数据形式和内容应该一致。数据可以在多个部门( 通过多个应 用和多个平台) 之间集成和共享。 数据是唯一的。数据记录( 及其码值) 是唯一的。 数据遵守商业规范。比如贷款余额从来不会是负数，这个规则来自商业，定义 数据时必须遵守它。 数据是适时的。适时性是主观的，只能由用户来决定。对用户指定的时间都能 提供相应的数据。 数据是有效的。维护的数据足够严格以满足分类准则的接受要求。 数据是完整的。非空值的属性中没有缺失值的情况。 为了提高数据的质量，就尽可能全面的定义限制数据的规则。通常，规则不可能 一次定义好。工作中根据对数据理解的深入，应该不断加强对规则定义的完善。在我 们日常的应用中，有许多应用规则控制数据质量的例子。例如，各种级别数据库上的 类型、大小范围、关键字等数据约束，以及触发器等更进一步的约束。就连w o r d 办公 处理软件也有拼写检查、语法检查等。一个企业，如果有一个完善的对数据定义的规 范，并在数据进入的时候进行规范检查，则数据的质量就比较高，从而为以后的对数 据的利用提供了方便。 长奋工业人学硕1 ：学位论史 1 4 数据清理研究的主要领域 到目前为止，数据清理并没有一个明确的、公认的定义。不同的应用领域对数据 清理有不同的定义。有三个领域把数据清理作为它们处理过程重要的一部分，这三个 领域分别是：数据仓库( d a t aw a r e h o u s i n g ) 领域、知识发现( k d d ) 过程和总体数据 质量管理系统( t d q m ) 6 3 。 1 4 1 数据仓库中的数据清理 数据仓库是一种面向决策主题，由多数据源集成，拥有当前及历史总结数据，以 读为主的数据库系统”1 。因为是面向决策层，在把数据装载进数据仓库前，必须保证数 据的准确性和一致性，所以要先进行数据清理。数据仓库模式如图1 1 所示。 数据源n 图1 1 数据仓库的模式 数据分析工具 在数据仓库领域中，当多个数据库集成的时候，可能会出现这样的情况：表示同 一实体的记录在不同的数据库中却以不同的格式出现，或者由于一些原因，数据出现 了错误，如果不对其进行数据清理的处理，集成后的数据库中必将出现重复的记录。 针对这个问题，数据清理的处理就是首先从多个数据源中合并那些表示形式可能不一 致，但实际上却表示同一实体的记录，识别出合并后的重复记录，并将它们删除。我 们一般把这个处理称为合并清理( m e r g e p u r g e ) 问题”1 ，也有文献称之为记录连接、 语义整合( s e m a n t i ci n t e g r a t i o n ) 、实例识别( i n s t a n c ei d e n t i f i c a t i o n ) 、或对 象识别问题( o b j e c ti d e n t i t yp r o b l e m ) 等。 k 奋t 业夫学硕l ：o 位论文 1 4 2 知识发现过程中的数据清理 在知识发现过程中，总是事先假设所利用的数据对象是正确的，其实这是一种理 想的情况。现实数据存在很多的错误、噪声，数据的丢失、遗漏，以及数据经常会出 现不一致的情况，所以一般把数据清理当作知识发现过程的第一步骤。 是乒日一 数据清理 数据选择数据预处理 数据采掘结果表示 _ l 日日_ l 【二l _ l 吕口_ l 数据源数据兴趣数据目标数据 模式知识 图1 2 知识发现的过程 在知识发现( k d d ) 领域，数据清理没有明确的定义和观点，因为它所进行的数据清 理处理一般都与具体的专业领域知识有关。如文 9 ，通过数据清理去掉垃圾模式( 一 种无意义的或容易让人产生误解的模式) 。知识发现领域中清理数据错误的处理与数据 仓库领域中的基本相同。 1 4 3 数据质量管理系统中的数据清洗 这个领域是从数据质量观点来阐述数据清理的处理。文 1 0 提供了数据质量管理 系统中数据清理研究的综述。在文 1 1 ，研究了数据清理处理提高数据质量的议题， 并提出了数据生命周期的模式。在这个模式中，数据的获取和使用包含了一系列的过 程：数据的评价，数据分析，数据的调整，数据的丢弃。另一个数据质量管理系统的 框架“”提出了描述数据质量的四个测度：准确性，通用性，完备性和一致性。 1 5 数据清理原理和基本步骤 数据清理就是利用有关技术如数理统计、数据挖掘或预定义的清理规则将脏数据 转化为满足数据质量要求的数据“，其原理可总结为如图1 3 所示： 4 k 存t 业人学硕j 学位论立 拼写错误 命名习惯 数据统计技术 数据挖掘技术 同一值不同的表示 图1 3 数据清理原理 不合法值 卒佰 异常检测 荤售处珲 一般说来，数据清理包括以下几个步骤“： 数据分析、定义错误类型 尽管已有一些数据分析工具，但仍以人工分析为主。在文献 1 5 中，作者将错误 类型分为两大类：单数据源与多数据源，并将它们又各分为结构级与记录级错误。这 种分类非常适合于解决数据仓库中的数据清理问题。 搜索、识别错误记录 有两种基本的思路用于识别错误：一种是发掘数据中存在的模式，然后利用这些 模式清理数据；另一种是基于数据的，根据预定义的清理规则，查找不匹配的记录。 后者用得更多。 修正错误 某些特定领域能够根据发现的错误模式，编制程序或借助于外部标准源文件、数 据字典一定程度上修正错误；对数值字段，有时能根据数理统计知识自动修正，但经 常须编制复杂的程序或借助于人工干预完成。 1 6 数据清理研究现状 1 6 1 国外对数据清理研究现状 国外对数据清理的研究已有十几年了，最初可以从美国对全美国的社会保险号码 的错误纠正开始。需求刺激技术的发展，c r m 、d w 、d m 、k d d 等在企业的快速应用，都 要求高质量的企业数据集的支持，从而带动在项目的实施过程中对提高数据质量方法 的研究。近几年，国外的数据清理技术发展的很快，这可以从市场上存在的数据清理 软件数目看出来。有商业上的数据清理软件，也有各大学和研究机构开发的数据清理 由 长存t 业人学硕 ：学位论j ： 软件。 商业上的数据清理软件主要有： s a si n s t i t u t e 公司的s a sw a r e h o u s ea d m i n i s t r a t o r e l e c t r o n i c di g i t a l do c l m en t s ，i n c 公司的d a t ac l e a n s e r d a t aj u n c t i o nc o r p o r a t i o n 公司的d a t aj u n c t i o n p l a t i u mt e c h n o l o g y 公司的i n f o r e f i n e r v a l i t yt e c h n o l o g y 公司的i n t e g r i t yd a t ar e e n g i n e e r i n ge n v i r o n m e n t w i n p u r e l t d 公司的w i n p u r e p o t t e r sw h e e l 1 6 1 是美国加利弗尼亚大学开发的一个交互式数据清理系统，它在 一个界面上同时整合了数据的转换过程和错误的检测过程。用户在一个类似表单的界 面进行数据的转换，转换的结果立即在屏幕上显示出来，如果用户对结果不满意，可 以很容易地撤消不满意的数据转换。数据错误的检测过程是在系统底层自动完成的， 当发现有错误数据的时候，就给这些数据打上标记，并通过上述的表单显示出来。此 时用户就根据这些标记做数据的转换。这个系统所涉及的数据转换主要指数据格式和 数据库模式的转换。 1 6 2 国内数据清理研究现状 国内关于数据仓库领域的研究都是以理论为主，涉及实例层次的研究很有限。 由于发达国家的信息化程度较高，各种信息系统的使用范围广、时间长，因此对 数据清理的需求显得较为迫切，所以关于数据清理的研究大多都集中在国外，而国外 关于数据清理的研究主要是针对西文表示的数据，这些数据清理方法不一定完全适用 于中文表示的数据。随着国内信息化建设的快速发展，数据质量问题也越来越受到关 注，对数据清理的研究也逐步展开，并取得了一定的成果，主要研究情况如下： 复旦大学以周傲英教授为首的研究小组较早地开始了数据清理的研究工作，目前 他们取得的主要成果有：提出了一个可扩展数据清洗框架o7 1 的定义。该清洗框架以术 语模型、处理描述文件、共享库等概念和技术实现了模块功能的可定制、系统的开放 性和可扩展性。 国内比较成熟的数据清理软件是d b p u t 2 0 通用数据转换工具。d b p u t 是一款比较 实用的数据转换软件。使用方法简单，但功能不多，不需掌握任何程序设计技术或s q l 语法，最多只需要掌握d b p u t 的几个关键功能和一些常用的函数，通过图形化的设计 界面，就可以将复杂的数据转换成所需格式的数据。 d b p u t 2 0 的特点： 支持o r a c l e 直接连接、0 d b c 连接，能直接读取文本格式数据。 6 长存t 业人学硕l 。学位论文 支持图形化的数据转换规则模型编辑方式。 通过任务模型编辑器模块，可设计出比较复杂的数据转换规则模型。 任务运行调试。可设置任务的调试断点，并能单步运行或暂停，可监控任务执 行过程中的数据抽取、计算结果和装载情况。 1 7 数据清理存在的问题 目前，从国内外关于数据清理的研究现状来看，主要体现在以下几个方面的不足： 数据清理属于一个较新的研究课题，直接针对这方面的研究并不多。此外，数据 清理的研究目前主要集中在西文数据库上，中文数据清理与西文数据清理有较大的不 同，如很多排序方法并不完全适用于中文数据库，中文数据清理应该引起更大的重视。 数据清理的研究主要集中在字符型数据上，识别数值型字段之间的关系异常很不 成熟与实用，数据挖掘算法在数据清理中的应用需要加强。尽管检测重复记录受到很 大的关注，采取了许多措施，但检测效率与检测精度问题并不令人满意。特别是在数 据量比较大时，耗时太多，有待于更好的检测算法。 多数数据清理工具都是针对特定的领域，其应用受到一定的限制。在将来，特定 领域的数据清理仍将是应用重点，但较通用的清理方案会受到越来越多的关注。 国产的数据清理工具还很少，少量的国产数据清理工具主要研究了重复记录的清 理问题，目前关于不完整数据、错误数据的清理问题不是很多。 1 8 论文的内容安排 本文内容安排如下： 第一章介绍课题所基于的背景知识，对数据挖掘技术做了简要的描述，分析了数 据清理中的数据质量，研究了数据清理研究的主要领域、数据清理研究现状；讨论了 数据清理原理和基本步骤。 第二章研究重复记录清理。对重复记录的识别研究了s o r t e d n e i b e r h o o d 方法和 优先队列方法；重点分析了记录相似检测，着重解析字段匹配问题，针对字段值的特 点采用了基于编辑距离的字段匹配算法，同时设计了利用有效权值和长度过滤的优化 算法进行记录匹配。 第三章研究空缺值清理。系统分析了空缺值的处理办法，重点研究了判定树归纳 方法的思想，算法，并对判定树归纳算法进行了变形。 第四章着重从两个方面研究了错误数据处理。首先是噪声( n o i s e ) 的清理方法， 重点研究分箱平滑的算法，并在此基础上设计了一种将判定树归纳算法和分箱平滑算 长春丁业人学硕j 学位论史 法结合的改进算法，来提高分箱平滑的效率。其次是对异常数据处理方法进行了探讨， 最后对应用业务规则进行数据清理描述其重要性。 第五章进行了大数据集数据清理技术研究，并针对该问题提出下一步研究的方 向。 第六章是在前几章数据清理研究的基础上，设计了基于这些关键技术的一个数据 清理框架设计。 最后在结束语部分做了总结，说明了本文主要完成的工作，并对未来的研究工作 进行了展望。 长存t 业人学硕l 学位论文 第二章相似重复记录清理 由于数据输入错误、不标准的缩写词，或其它原因，数据库中可能包含关于现实 世界同一实体的重复记录。虽然关系数据库系统不允许含有重复主键值的记录输入， 但是，由于数据输入错误，不管主键的值是否被这些错误影响，关系数据库不能再保 证不存在重复的记录。因此，在数据清理中，相似重复记录的检测与清除是一个重要 问题。 2 1 相似重复记录定义 所谓相似重复对象是指表现形式不同但语义上相同的对象“”，从狭义的角度来看， 如果两条记录在某些字段上的值相等或足够相似，则认为这两条记录互为相似重复。 在完成大部分的数据转化和其他清理步骤以后，就可以执行相似重复记录的匹配和合 并了。 相似重复记录清理的一般过程如下：首先，需要识别同一个现实实体的相似重复 记录，即记录匹配过程；随后，将相似重复记录合并成一个包含该实体的更多属性且 没有冗余信息的记录。 2 2 相似重复记录清理方法总体描述 相似重复记录的清理过程可总结为：记录排序、记录相似检测、相似重复记录合 并清除。其清理过程可描述如下： 首先，把数据源中需要清理的数据通过j d b c ( j a v ad a t a b a s ec o n n e c t i v i t y ，j a v a 数 据库连接) 接口调入到系统中来； 然后，执行数据清理，调用排序算法，执行记录之间的排序；在记录已排序的基 础上，调用相似检测算法，作邻近范围内记录间的相似检测，从而计算出记录间的相 似度，并根据预定义的重复识别规则，来判定是否为相似重复记录。为了能检测到更 多的重复记录，通常需要采用多轮排序，多轮比较，每次排序采用不同的键，然后把 检测到的所有重复记录聚类到一起，从而完成重复记录的检测； 最后，对所检测出的每一组相似重复记录根据预定义的合并清除规则，完成相似 重复记录的合并处理。 9 长春t 业人学硕j 。学位论文 2 3 记录排序 为了在有限的时间内完成重复记录的检测，同时还要保证检测结果具有较好的准 确率和查全率，必须采取某种技术手段限制记录匹配的范围，因此在进行记录匹配操 作之前，通常需要采取某种方法将潜在的可能的重复记录调整到一个相邻的位置空间， 从而对于特定的记录可以将记录匹配对象限制在一定的范围之内。由此可见，。排序 合并”算法思想是很有效的。本文主要研究了下面两种排序方法。 1 s o r t e d - n c i b c r h o o d 方法 以用户定义的键作为排序键进行排序，然后，通过一组规则定义的相等理论判定 记录是否相似，其基本思想可描述如下： 按照用户定义的排序键对整个数据表进行排序，将可能匹配的记录排列在一起。 当然，按照某个排序键排一次序往往是不够的，需要按照不同的排序键对数据多次排 序，再将结果结合起来。具体说来，s o r t e d - n e i b e r h o o d 算法“”分为三步： 创建排序键 ， 抽取记录中重要的字段或字段的一部分组成每条记录的排序键，排序键的选择对 于检测结果的准确性至关重要。 记录排序 用第一步生成的排序键对记录排序。 、 合并 定义一个固定大小的比较窗口，在记录列表上移动，比较窗口内的记录是否相似， 如图2 1 所示。如果窗口的大小为l ( 2 l n ) ，那么每条最新进入窗口的记录与前面的 l 一1 条记录逐一比较以找到匹配记录。窗口中第一条记录滑出窗口。 其中，“字段的差别”是通过将距离函数的计算结果与阈值比较确定的。距离函 数一般包括：字符串编辑距离，语音距离和打字机距离，用户也可以自己定义距离函 数。本文将在后面主要分析编辑距离算法。 0 长春t 业人学硕i 学位论文 当 前 窗 口 的 记 录 l l 图2 1s o r t e d n e i b e r h o o d 方法原理 下 个 窗 口 的 记 录 2 优先队列方法 ( 1 ) 优先队列策略嘲 优先队列策略借用邻近排序算法的思想，对数据集进行排序，根据排序的顺序， 对范围相对较小的邻近记录进行匹配比较，找出重复记录。具体策略是抽取一个或多 个字段构成关键字进行排序，然后寻找数据库中各条记录在一个长度固定的子集队列 中的匹配记录。通过匹配操作寻找出需要合并的子集，计算其传递闭包，然后合并它 们，最后得到若干个近似重复记录集。基于这样一个观察：一个简单的关键字在排序 后不能完全将重复记录聚集在一起，因此一趟优先队列算法可能遗漏一些重复记录。 为避免这种情况，我们提出实行多趟优先队列算法，每次采用一个不同的关键字进行 排序。 ( 2 ) 优先队列相关概念 优先队列 所谓优先队列是一种队列元素具有不同优先级且长度固定的队列。我们将队列中 的元素看作集合，这些集合中的元素是与u m o n f i n d 对应的重复聚类的特征记录，每个 这样的集合也具有与u n i o n f i n d 结构中对应集合的聚类表示。 u n i o n - f i n d 结构 该结构最早用于不相交集合的并操作，主要有以下两个原子操作： u n i o n ( r l ，r 2 ) ：将以r 1 、r 2 作为节点的两个集合合并成一个新的集合，返回新生成 的节点。 长存t 业人学硕l 。学位论史 f i n d ( x ) ：查找节点x 所在的集合。 在优先队列算法中，我们利用该结构保存识别动作所产生的重复记录聚类，每个 聚类以集合的形式存在，且有一个重复聚类表示。初始情况下，将每条记录看作一个 集合。在记录的比较过程中，一旦判定两条记录为重复记录，就执行u n i o n 操作。 ( 3 ) 优先队列算法思想 优先队列识别重复记录的具体方法是抽取一个或多个字段构成关键字进行排序， 然后寻找各条记录在优先队列中的匹配记录。假定当前考察的记录为硒，如果砌己在 优先队列的某个集合中，则将该集合的优先级设为最高，继续考察数据集中的下一条 记录。否则，按优先级的高低，砌逐个与各个聚类的特征记录进行启发式的匹配比较。 若匹配成功，则通过u n i o n 操作合并两者所在的聚类；若没有成功的匹配，表明r j 所在 的聚类在优先队列中没有出现，这时将础作为新的聚类且优先级设为最高加入优先队 列，采用类似l r u 算法淘汰优先级最低的聚类，并继续考察数据集中的记录，直至结 束。最终u n i o n - f i n d 的结果即为输入数据集中的重复记录聚类。假定记录的近似重复具 有传递性，即记录扁与r ：互为重复记录，r ：与船互为重复记录，则月z 与届互为重复 记录。 2 4 记录相似检测 记录相似检测是指通过计算两条记录之间的相似度s ，来判定两记录是不是重复记 录。 定义l 记录之间的相似度s 记录之间的相似度s 是根据两条记录的内容而计算出的一个表示两记录相似程度 的数值，0 s 6 ) ( r e t u r nf a l s e ： 如果两记录任意字段间相似度大于6 ，则它们不是相似重复记录 1 4 k 存t 业人学硕卜学位论立 l o ) e l s e r s i m i l a r = r s i m i l a r + w e i 曲t i * s i m i l a r ： 否则，记录相似度变量r s i m i l a r 相应增加w e i g h t i * s i m i l a r w e i g h t s u m = w e i g h t s u m + w e i g h t i ： 计算非空字段的权重和 1 1 ) ( 4 ) ) ( 5 ) r s i m i l a r = r s i m i l a r w e i g h t s u m ； ( 6 ) i f ( r s i m i l a r = o ) d e l e t e 月1 ： 如果记录间相似度为零，则它们是完全重复记录，删除其中的一个即可 ( 7 )l ( 8 ) i f ( r s i m i l a r 6 ：) f r e t u r nt r u e ：如果记录问相似度小于6 。，则认为它们是相似重复记录 ) ( 9 ) e l s e r e t u r nf a l s e ：否则，不是相似重复记录 ( 1 0 ) ) 在记录相似检测的过程中，判定两记录是否相似由以下两个阈值来定： 6 ：用来判定两条记录中同一字段是否相似。如果两个字段的相似度大于6 ，则 两字段不相似，从而也判定两记录不是相似重复记录； 6 ：用来判定两条记录是否是相似重复记录。记录的相似度为对应字段的相似度 之和，如果两条记录的相似度大于赴，则两记录不是相似重复记录。 由以上算法可以看出：记录间的相似检测依赖于记录中每个字段的相似检测，因 此字段的相似检测是一个相当重要的原子操作，其效率直接影响整个算法的效率。 s ( r - f i e l d i ，r 2 f i e l d i ) 计算两记录中相同类型字段r 1 f i e l d i 和r 2 f i e l d 【i 】的相似 度。对不同类型的字段，采用不同的计算方法： 布尔型字段相似度计算方法 对于布尔型字段，如果两字段相等，则相似度取0 ，如果不同，则相似度取l 。 数值型字段相似度计算方法 对于数值型字段，可采用计算数字的相对差异算法： s ( s s ：) ： 照二列 ( 2 3 ) m a x ( ，屯) 1 5 k 軎t 业人学硕f 。学位论文 2 4 3 字段匹配问题 在数据库中，记录由字段组成，因此，相似重复记录清理的一个重要研究领域就 是字符串的相似检测。字符串的相似检测是计算机科学中一个最重要的研究问题。 字段匹配。1 是记录匹配的基础，可以分为字符型字段匹配和数值型字段匹配。对 于数值型字段的匹配，用到的基本上都是精确匹配理论，一般直接进行简单的相等比 较。但字符型匹配一般用到的是模糊匹配知识，其中很大程度和字符的类型有关，且 不同语言下的字符型匹配算法有较大的区别。例如英文中的缩写、简写、姓名表示方 式、地址表示方式等，同汉语有很大差异。汉语和英文之间存在的诸多差异，使得字 符型字段匹配算法，两者基本上不能通用。考虑到大部分的字段值都是字符型的，且 重复记录之