（计算机软件与理论专业论文）数据清洗算法的研究与应用(1).pdf

摘要 随着信息技术的毪速发展，组织的管理人员进行决策分析时对数据的依赖性越 来越强。于是在数据库的基础上产生了能够满足决策分析所需要的数据环境一数据 仓库。但是在构建数据仓库的过程中，从异构的数据源中导入的数据中存在各种质 量问题，使得应用于数据仓库前端的决策支持系统产生错误的分析结果，影响信息 服务的质量。所以必须对其进行数据清洗来提高其质量。数据清洗正在成为数据仓 库和数据挖掘领域，乃至网络数据处理的一个重要课题。 本文首先对数据清洗的知识进行了全面和详细的描述，介绍了数据清洗的概念、 意义和国内外研究与应用的现状。对数据清洗技术的原理、方法、评价标准以及基 本流程进行了分析和总结。其中重点对属性清洗及重复记录清洗所用到的技术和各 种算法进行了深入的研究，并提出了相应的改进算法。 在属性清沈中，简单介绍了属性清沈的基本知识和方法，重点研究了如何应用 统计分析和人工智能的技术自动检测数据集中属性值的错误，并给出了在数据集上 的实验结果及结论。 在重复记录清洗中，首先介绍了重复记录清洗的相关知识和基本流程，然后分 别就流程中各个步骤所涉及的关键算法进行了深入的研究，并针对各步中算法的缺 陷进行了改进。主要包括：预处理步骤中，改进的排序关键字对数据集排序的方法； 重复记录检测步骤中，针对中文字段值的特点提出的基于编辑距离的字段匹配算 法和缩写发现算法；提出了利用有效权值和长度过滤的优化算法进行记录匹配，减 少重复记录的检测时问，提高算法的效率；在数据库级上对重复记录进行聚类的 步骤中，针对传统的s n m 方法的两个缺陷提出了改进的s n m 算法，实验结果表明，改 进的s n m 算法要优于传统的算法。 最后，为解决构建青岛市港务局数据仓库的过程中遇到的数据质量和数据清洗 问题，结合前面进行的研究工作设计了一个实验性的数据清洗工具。设计该工具的 目的是对这些数据进行数据清洗，同时对本文中提出的改进的算法的有效性进行检 验和验证。结果表明改进的算法有较好的效果，基本上能达到实际应用的要求。 在本文的结尾，对所做的工作进行了总结，并对未来数据清洗技术的研究方向 i 差行了展望。 关键词：数据清洗；属性清洗；重复记录清洗；字段匹配：编辑距离； 缩写发现 a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，o r g a n i z a t i o n a lm a n a g e r s d e p e n do nd a t am o r ea n dm o r ew h e nm a k i n gt h e i rd e c i s i o n s o nt h ef o u n d a t i o no f d a t a b a s et h e r ea p p e a r sd a t aw a r e h o u s ew h i c hc a ns u p p o r td e c i s i o na n a l y s i s b u td u r i n g t h ec o n s t r u c t i o no fd a t aw a r e h o u s e ，d a t af r o md i f f e r e n td a t as o u r c e sa r ei n p u t t e di n t ot h e d a t aw a r e h o u s e ，t h e r em a ye x i s tm a n yd a t aq u a l i t a t i v ep r o b l e m s ，r e s u l ti nf a l s ed e c i s i v e a n a b r s i sa n di n f l u e n tq u a l i t yo f i n f o r m a t i o ns e r v i c e t h e r ei sas t r o n gn e e dt oc a r r yo u ta d a t ac l e a n s i n g p r o c e s s t o i m p r o v et h e d a t aq u a l i t y d a t ac l e a n s i n gi s b e c o m i n ga n i m p o r t a n tt o p i ci nd a t a w a r e h o u s ea n dd a t a m i n i n g ，a sw e l l a sw e bd a t a p r o c e s s i n gf i e l d s i nt h i sp a p e r , w ed e p i c t e dt h ek n o w l e d g eo fd a t ac l e a n s i n gi nd e t a i l w ei n t r o d u c e d t h ec o n c e p t ，m e a n i n ga n d l c u r r e n tr e s e a r c ha n d a p p l i c a t i o ns i t u a t i o nh o m e a n da b r o a do f d a t a c l e a n s i n g w es u m m a r i z e d a n dd e s c r i b e dt h et h e o r i e s ，m e t h o d s ，e v a l u a t i n gs t a n d a r d s a n db a s i cw o r k f i o wo fd a t ac l e a n s i n g e s p e c i a l l yo u rr e s e a r c h i n ge m p h a s i si so nt h e t e c h n i q u e sa n da l g o r i t h m so f f i e l dc l e a n s i n ga n d d u p l i c a t er e c o r d sc l e a n s i n g ，a n dw ep u t f o r w a r dt h er e l e v a n ta d v a n c e d a l g o r i t h m s i nf i e l dc l e a n s i n g ，w e s i m p l y i n t r o d u c e db a s i ck n o w l e d g ea n dm e t h o d so ff i e l d c l e a n s i n g w em a i n l yr e s e a r c h e dh o w t oa p p l yt h et e c h n i q u e so f s t a t i s t i c a la n a l y s i sa n d a r t i f i c i a li n t e l l i g e n c et oa u t o m a t i e a u yd e t e c te r r o r so f f i e l dv a l u e w eg i v e0 1 2 1 e x p e r i m e n t a lr e s u l t sa n d c o n c l u s i o n so nar e a lw o r l dd a t a s e t i nd u p l i c a t er e c o r d sc l e a n s i n g ，w ei n t r o d u c e di t sb a s i ck n o w l e d g ea n dw o r k f l o w , d e p i c t e dt h em a i nt e c h n i q u e sa n da l g o r i t h m s i nd e t a i li ne a c hs t e pr e s p e c t i v e l y a tt h e s a m et i m ew e g a v eo u ra d v a n c e da l g o r i t h m s t oi m p r o v et h el i m i t a t i o no f o r i g i n a lo n e si n e a c hs t e p 1 1 1 e ym a i n l yi n c l u d et h ef o l l o w i n g ：t h ea d v a n c e dm e t h o du s i n gs o r t e dk e yt o s o r tt h ed a t a s e t i nd u p l i c a t er e c o r d sd e t e c t i o n ，w e p u tf o r w a r d t h ef i e l dm a t c h a l g o r i t h m a n da b b r e v i a t i o n - d i s c o v e r e d a 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 ec a m e u p w i t ht h eo p t i m i z e dm e t h o d u 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 e r u n t i m e o f o r i g i n a la l g o r i t h m a n di m p r o v ei t se f f i c i e n c y i nc l u s t e r i n gt h ed u p l i c a t e r e c o r d so nd a t a b a s el e v e l ，w ea m e n d e dt w ol i m i t a t i o n so f t r a d i t i o n a ls n m ( s o r t e d - n e i g h b o r h o o dm e t h o d ) a n dg a v e t h ea d v a n c e ds n m a tl a s tw e p r o v i d e d t h e c o m p a r e o f a d v a n c e da n do r i g i n a la l g o r i t h mo nt h er t m t i m ea n de f f i c i e n c y f i n a l l y , i no r d e rt or e s o l v et h ed a t ac l e a n s i n gp r o b l e m sd u r i n gt h e c o n s t r u c t i o n p r o c e s so f d a t aw a r e h o u s ef o rq i n gd a oh a r b o rb u r e a u , w ed e s i g n e da l le x p e r i m e n t a ld a t a c l e a n s i n gt o o lb a s e do np r e v i o u sr e s e a r c hw o r k t h ea i mt od e s i g ns u c hat o o l i st o c l e a n s et h ed a t a ，a n da tt h es a m et i m et ov e r i f ya n dv a l i d a t eo u rc l e a n s i n gs c h e m e s f e a s i b i l i t y a n dm e r i t so fa d v a n c e da l g o r i t h m t h ee x p e r i m e n t a lr e s u l t si n d i c a t eg o o d p e r f o r m a n c e o fa d v a n c e d a l g o r i t h m s a n dn e w m e t h o d s ，b a s i c a l l y a c h i e v e dt h e r e q u i r e m e n t o f r e a l a p p l i c a t i o n a tt h ee n do ft h ep a p e r , w es u m m a r i z e dt h er e s e a r c hw o r ki nt h i sp a p e ra n dg a v ea f u t u r e v i e w a b o u tr e s e a r c h d i r e c t i o n o f d a t a c l e a n s i n g t e c h n o l o g y , k e y w o r d s ：d a t ac l e a n s i n g ；f i e l dc l e a n s i n g ；d u p l i c a t e r e c o r d sc l e a n s i n g ；f i e l dm a t c h ； e d i td i s t a n c e ；a b b r e v i a t i o nd i s c o v e r y 第一章概述 第一章概述 本章简单介绍了数据清洗问题提出的背景，有关数据质量的知识，数据清洗技 术在不同的应用领域中的不同定义，以及国内外数据清洗技术的研究现状，最后介 绍了本文的研究内容和各章节安排。 1 1 问题的提出 当建立一个信息系统时，即使进行了良好的设计和规划，也不能保证在所有情 况下，所存放数据的质量都能满足要求。用户录入错误、企业合并以及企业环境随 着时间的推移而改变，这些都会影响所存放数据的质量。这些数据过去一直在许多 系统中存在着，我们并没对其多加注意，这是因为它们的存在并没有影响到事务处 理系统的正常运行。随着数据库技术的应用和发展，为满足组织的管理人员对决策 分析的需要，在数据库的基础上产生了能够满足决策分析所需要的数据环境一数据 仓库。这样对数据的需求就发生了改变，要求数据不仅支持事务处理型系统，也要 支持决策分析型系统。在构造数据仓库的过程中，需要从各种异构的数据源导入大 量的数据。这些数据存在录入错误、数据存在遗漏和不完整以及同一对象在不同的 数据源中的表示各异等质量问题。据统计，大型数据仓库中数据的错误率一般在5 左右或者更高 1 。要在基于历史的、现存的数据的基础上去为将来的企业发展作决 策和预测时，数据的质量问题就变的很关键。根据“垃圾进，垃圾出( g a r b a g ei n ， g a r b a g eo u t ) ”的原理，错误的数据会导致昂贵的操作费用和响应时间，影响从数 据集中抽取的模式的正确性和导出规则的准确性，使得应用于数据仓库前端的决策 支持系统产生错误的分析结果，将会误导决策，影响信息服务的质量。因此数据仓 库构造过程中的一个重要的任务就是通过数据清洗，消除数据中的不一致和错误， 将数据转换为一致的格式，保证数据的正确性，保证决策的质量。 近年来，数据挖掘领域的算法研究日趋成熟，但其中许多算法研究的重点是方 法和模型，把方法和模型建立在理想的数据而不是现实的数据集上，而现实数据的 性质通常并不是理想的，这样归纳出的规则和知识就和实际应用存在一定的差距， 使得理论上的算法不能很好得应用于实际中。因此有必要通过数据清洗来缩小数据 挖掘理论上的算法和实际应用之间的差距。只有保证完整的数据质量，利用数据挖 掘技术作为决策支持工具来提取知识和规则才能有可靠的保证。 青岛大学硕士学位论文 1 2 数据质量 1 2 1 数据质量的描述 目前学术界对数据质量还没有一个固定的一成不变的定义。许多学者倾向于把 数据质量视为信息系统中数据视图与实际数据的一致性测度。大型的真实世界数据 集的数据质量，其正确性、一致性、完整性和可用性由很多的因素决定。文献【2 】中 以形式化的方法定义了数据的一致性( c o n s i s t e n c y ) 、正确性( c o r r e c t n e s s ) 、完整性 ( c o m p l e t e n e s s ) 和可用性( u s a b i l i t y ) ，而数据质量被定义为这4 个指标在信息系统中得 到满足的程度。我们认为数据质量作为衡量数据好坏的指标，它表明了数据满足商 业信息需求的程度。 1 2 2 数据质量问题的分类 根据处理的是单数据源还是多数据源以及问题出在模式层还是实例层，可以将 数据质量问题分为4 类( 如图1 1 所示) ：单数据源模式层问题、单数据源实例层问 题、多数据源模式层问题和多数据源实例层问题。 单数据源情形中出现的问题在多数据源的情况下会变得更加严重。( 图1 1 对多 数据源没有列出在单数据源情形中就已经出现的问题) 。模式层的问题也会体现在实 例层。糟糕的模式设计、缺少完整性约束的定义以及多个数据源之间异质的数据模 型、命名和结构冲突等，都属于模式层的问题。可以通过改进模式设计、模式转化 和模式集成来解决模式层的问题。实例层的问题在模式层不可见，一些可能的情况 有数据拼写错误、无效的数据值、重复记录等。本文主要考虑实例层的问题。 图1 1 数据质量问题的分类 第一章概述 1 3 数据清洗定义与简介 在英文中，数据清洗有d a t ac l e a n i n g 、d a t ac l e a n s i n g 和d a t as c r u b b i n g 三种说 法，翻译成中文有数据净化，数据清洗，数据清理三种译文。尽管在英文中三者的 具体含义有微小差别，但对于三种中文译法，研究者一般都将其看作是一个意思。 除了在语言表达上有几种不同的方式以外，由于数据清洗在不同的应用领域中有不 同的要求，对其定义还没有统一的表述。包含数据清洗过程有三个主要领域：数据 仓库，数据库中的知识发现( k d d ，又称为数据挖掘) 和数据信息质量管理( 如， 全面数据质量管理t d q m ) 。下面分别介绍在这三个应用领域中对数据清洗技术的 定义： 1 3 1 数据仓库应用中的数据清洗定义 在数据仓库领域中数据清洗一般是应用在几个数据库合并时或多个数据源进 行集成时。指代同一个实体的记录在不同的数据源中以不同的格式表示或被错误的 表示，这样在合并后的数据库中就会出现重复的记录。数据清洗过程就是要把这些 重复的记录识别出来并消除它们，也就是所说的合并清除( m e r g e p u r g e ) 问题。在 文献中出现的这样的过程的一般称为：记录连接、语义整合、实例识别或对象识别 问题。根据这个观点，数据仓库领域对数据清洗的定义主要有：文献【3 】中，数据清 洗是指消除数据中的错误和不一致，并解决对象识别问题的过程。文献【4 】中把合并 清除问题定义为数据清洗问题，并提出了基本的排序邻居方法。文献【5 】提出，数据 清洗并不仅仅是简单地用好的数据去更新记录，彻底的数据清洗需要对数据进行分 解和重新组合，文中给出了一个对客户地址进行清洗的过程的实例，把数据清洗过 程分为6 个步骤：元素化、标准化、校验、匹配、是否为一家人和文档化( 写入元 数据存储中心) 。 1 3 2k d d 应用中的数据清洗定义 在数据库中的知识发现领域，数据清洗被认为是k d d 过程的第一个步骤，即 对数据进行预处理的过程。各种不同的k d d 和d m 系统都是针对特定的应用领域 进行数据清洗的。文献 6 1 q b ，信息的模式被用于发现“垃圾模式”( 没有意义的或 错误的模式) ，属于数据清洗的一种。在字符分类问题中应用机器学习的技术来进行 数据清洗。文献【7 】中数据清洗被定义为一种使用计算机化的方法来检查数据库，检 测丢失的和不正确的数据并纠正错误的过程。 1 3 3 数据信息质量管理应用中的数据清洗定义 全面数据质量管理解决整个信息业务过程中的数据质量及其集成问题。在该领 3 青岛大学硕士学位论文 域中，没有直接定义数据清洗过程，文献【8 】中所提出的应用于数据获取和数据使用 周期质量的数据生命周期模型( 包括数据的评价、分析、调整和丢弃) ，是从数据质 量的角度，把数据清洗过程和数据生命周期集成在一起。因此数据清洗过程被定义 为，一个评价数据正确性并改善其质量的过程。 本文主要考虑数据仓库应用中的数据清洗问题，认为数据清洗是通过各种措施 从准确性、一致性、无冗余以及符合应用的需求等方面提高已有的数据质量的过程。 数据清洗的目的是检测数据中存在的错误、不一致数据和重复记录，并消除或改正 它们，从而提高数据的质量，保证应用于数据仓库前端的决策支持系统产生正确的 决策分析结果。主要所涉及的内容有结构清洗、属性清洗与重复记录清洗。本文以 属性清洗和重复记录清洗为研究重点，结构清洗通过手工实现而没有进行详细的论 述。 1 4 数据清洗技术研究现状 尽管目前数据仓库、k d d ( 数据挖掘) 、客户关系管理等在理论和应用上都获 得了极大的发展，但数据清洗作为其重要的、必不可少的组成部分，直接针对这方 面的研究并不多，下面将国内外有关数据清洗技术的研究现状概述如下： 1 4 1 国外研究现状 国外对数据清洗技术的研究，最早出现在美国，是从对全美的社会保险号错误 的纠正开始的【3 】。美国信息业和商业的发展，刺激了对这方面技术的研究。研究内 容主要涉及： 1 对数据集进行异常检测，是指对数据集的记录属性的清洗。主要有下列方法 9 ：采用统计学的方法来检测数值型属性，计算字段值的均值和标准差。考虑每一 个字段的置信区间来识别异常字段和记录。还把人工智能的方法引入到数据清洗中， 主要有：采用基于距离的聚类的方法来识别异常的记录。采用基于模式的方法 来发现不符合数据集中现存模式的异常记录。采用关联规则的方法来发现数据集 中不符合具有高置信度和支持度的规则的异常数据。 对值为字符型的属性利用了属性问的约束关系、模式识别技术等，难度较大。 属性清洗可以针对具体问题具体分析，也可针对某类问题提供解决方案。如果清洗 方案能自动发掘规则，则属于自适应性属性清洗，实现难度非常大，这种方案较少 见。 z 识别并消除数据集中的近似重复对象，也就是重复记录的清洗【3 ，4 ，6 1 。它在 数据仓库环境下特别重要，因为在集成不同的系统时会产生大量的重复记录。消除 4 第一章概述 数据集中的近似重复的记录问题是目前数据清洗领域研究的最多的内容。为了从数 据集中消除重复记录，首要的问题就是如何判断两条记录是否是近似重复。其核心 问题是字段的匹配问题，目前常用的算法有：递归式字段匹配算法、s m i t h w a t e r m a n 算法和r s w 算法。在数据集级识别重复记录的经典方法是基本近邻排序方法。针 对这种算法的缺陷，研究者提出了各种改进的算法，主要包括多趟近邻排序方法， 优先权队列清洗策略等。针对召回率一精确度两难问题提出了一个基于知识管理的智 能型数据清洗系统的框架，该框架采用专家系统，用规则来表示领域知识，实现了 知识的高效表示和灵活管理。通过指定有效的规则，并且在传递闭包的计算过程中 引入不确定因子，在一定程度上解决了召回率一精确度两难问题。 3 在数据仓库应用中，数据清洗必须考虑数据集成，主要是将数据源中的结构 和数据映射到目标结构与域中。在这方面已做了大量的研究工作。 4 不少数据清洗方案和算法都是针对特定应用问题的，只适用于较小的范围。 通用的，与应用领域无关的算法和方案较少。绝大部分数据清洗方案【3 ，4 ，l o 】提供了 接口用于编制清洗程序。它们一般来说包括很多耗时的排序、比较、匹配过程，且 这些过程往往多次反复，用户必须等待较长时间。为了方便用户进行清洗，许多工 具还通过提供描述性语言降低用户编程复杂度，解决用户友好性。例如a r k l d s 方 案提供了x a d l 语言( 一种基于预定义的d t d 的x m l 语言) 与s a d l s a d l 语言 【l o ，a j a x 提供了一套宏操作( s q l 语句及外部函数组成) 【4 】，【3 】提供了一种 s q l l i k e 命令语言，这些描述性语言都在一定程度上减轻了用户的编程难度，但各 系统一般不具有互操作性不能通用。 5 近几年，国外的数据清洗技术发展的很快，从市场上存在的数据清洗软件数 目看出来，其中包括商业上的数据清洗软件，也有各大学和研究机构开发的数据清 洗软件【1 1 ，1 2 1 。 商业上的数据清洗软件主要有： 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 cd i g i t a ld o c u m en t s ；i n c 公司的d a t a c 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 el t d 公司的w i n p u r e 各大学研究机构的数据清洗软件主要有： 加州b e r k e l e y 大学分校的p o t e r sw h e e la - b c ，一个交互式的清理工具。用 5 青岛大学硕士学位论文 c 语言，p e r l 语言或者工具提供的宏语言来写转换规则。 新加坡国立大学的i n t e l l i c l e a n 。一个基于知识的智能数据清理工具。使用 了一个j a v a 语言的专家系统外壳。 法国i n r i a 研究机构的a j a x ，一个可扩展的数据清理工具。 需要说明的是，上述所描述的国外的研究现状都是针对英文的数据清洗。 1 4 2 国内研究现状 目前国内对于数据清洗技术的研究，还处在一个开始的阶段。尽管在一些学术 期刊及学术会议上也能见到一些有关这方面的理论性文章，但直接针对数据清洗， 特别是针对中文数据清洗的论文并不多。大多是在数据仓库、决策支持、数据挖掘 的研究中，对其做一些比较简单的阐述。银行、保险和证券等对客户数据的准确性 要求很高的行业，都在做自己的客户数据的清洗工作，针对自己的具体应用而开发 软件，且很少有理论性的东西公布出来。 中文数据清洗在理论研究上的欠缺，也使得在市场上几乎看不到有关中文数据 清洗的软件工具。需求刺激技术的发展，随着数据仓库、数据挖掘、客户关系管理 等在企业中的大量应用，必然要求高质量的企业数据集的支持，同时也将带动在项 目的实施过程中对提高数据质量的方法和中文数据清洗技术的研究，以及高效实用 的中文数据清洗工具的开发。 1 5 本文的研究内容与章节安排 第一章介绍了数据清洗问题提出的背景，有关数据质量的知识，数据清洗技术 在不同的应用领域中的不同定义，以及国内外数据清洗技术的研究现状，最后介绍 了本文的研究内容和各章节安排。 第二章主要研究了数据清洗技术的原理和方法，以及数据清洗过程的基本流程， 最后简单介绍了数据清洗效果的评价标准。 第三章主要介绍了有关数据清洗中的属性清洗的基本知识，包括属性清洗的对 象和用于属性清洗的各种方法，重点研究了如何使用统计分析和人工智能的技术自 动检测数据集中属性值的错误，并给出了在数据集上的实验结果及结论。 第四章是本文工作的重点，首先介绍了重复记录清洗的相关知识和基本流程， 然后分别就流程中各个步骤所涉及的关键算法进行了深入地研究，并针对各步中算 法的缺陷进行了改进。主要包括：预处理步骤中，改进的排序关键字对数据集排序 的方法；重复记录检测步骤中，针对中文字段值的特点提出的基于编辑距离的字 6 第一章概述 段匹配算法和缩写发现算法；提出了利用有效权值和长度过滤的优化算法进行记录 匹配，减少重复记录的检测时间，提高算法的效率：在数据库级上对重复记录进 行聚类的步骤中，针对传统的s n m 方法的两个缺陷提出了改进的s n m 算法，实验结果 表明，改进的s n m 算法要优于传统的算法。最后研究了冲突处理，即重复记录的合并 或删除过程的冲突解决机制。 第五章给出了一个为解决在实际构建数据仓库过程中遇到的数据清洗问题，结 合前面进行的研究工作设计的实验性数据清洗工具。主要介绍了该工具设计的应用 背景，源数据中存在的问题，工具的框架结构和操作流程，最后简单评价了工具的 优缺点。 第六章总结了本文所做的研究工作，并对进一步工作的研究方向进行了展望。 第二章数据清洗知识 第二章数据清洗知识 本章主要研究了数据清洗的原理和方法，以及数据清洗过程的基本流程，最后 简单介绍了数据清洗的评价标准。 2 1 数据清洗的原理和方法 2 1 1 数据清洗的原理 数据清洗的原理，就是通过分析“脏数据”的产生原因和存在形式，利用现有 的技术手段和方法去清洗“脏数据”，将“脏数据”转化为满足数据质量或应用要求 的数据，从而提高数据集的数据质量。数据清洗主要利用回溯的思想，从脏数据产 生的源头上开始分析数据，对数据集流经的每一个过程进行考察，从中提取数据清 洗的规则和策略。最后在数据集上应用这些规则和策略发现“脏数据”和清洗“脏 数据”。这些清洗规则和策略的强度，决定了清洗后数据的质量。图2 1 表明了数据 清洗的原理： 拼写错误+ 命名习惯- 数理统计技术卜 数据挖掘技术， 脏数据 i数据清洗策略、规则 i 满足数据质量要求的数据 不合法值 空值 属性清洗 重复记录清洗 图2 1 数据清洗的原理 2 1 2 数据清洗的方法 数据质量问题主要有两类，一类是与数据模式有关，另一类则是和实例即数据 有关。数据清洗的对象和方法也因模式层和实例层而有所不同。 青岛大学硕士学位论文 第一、模式层的数据清洗方法 模式层的数据质量问题主要是由于结构设计不合理和缺乏属性间的完整性约束 造成的。主要包括命名冲突( n a m i n gc o n f l i c t ) 和结构冲突( s t r u c t u r a lc o n f l i c t ) 。命 名冲突主要是同名异义和异名同义，前者是指同一名称代表不同的对象，后者则相 反，既不同的名称代表同一对象。结构冲突主要是由在不同的数据源中不同的对象 表示引起的。例如，类型冲突，依赖冲突、关键字冲突和动作冲突等。 模式层问题可以通过设计程序，由程序自动去发现，但由于模式设计更多的涉 及到对数据本身的理解，对应用数据所属的领域的认识，所以当发现模式问题时， 并不表示很容易能够解决问题。一般需要在理解数据意义和应用领域的基础上去做 修改，从而很难用计算机自动地对模式结构进行修改。一般情况下，模式层问题都 需要由人工手工去实现清洗。在此过程中，也能够利用到一些计算机的结构转换函 数，例如对列操作的c o p y ，s p l i t ，d i v i d e ，a d d ，d r o p 等函数，以减轻手工 纠正的劳动强度。现在研究者也在研究自动化的模式级问题清洗工具，但还很不成 熟。 第二、实例层的数据清洗方法 实例层的脏数据清洗方法主要分为以下两种情况： 1 属性清洗方法 脏数据最多的表现形式就是属性值中的脏数据。属性值脏数据的清洗方法主要 有： ( 1 ) 空值的清洗方法 空值是数据清洗经常遇到的问题。一般的空值问题可分为两种：一是缺失值， 二是空值。缺失值是指值实际存在，但没有存入值所属宇段，如成年人都有身份证， 如果某个成年人身份证号属性值为空，就属于缺失值；空值指因实际并不存在而空 的值，如未成年人没有身份证，因此他们的身份证号属性为空。数据清洗所处理的 是缺失值。处理方法有： 某些缺失值可以从本数据源或其他数据源推导出来。 可用平均值、中间值、最大值、最小值或更为复杂的概率统计函数值代替缺 失的值，但准确性比较低。 人工输入一个可接受的值。 ( 2 ) 错误值的检测及清洗方法 用统计分析的方法识别可能的错误值或异常值。 9 第二章数据清洗知识 使用简单规则库( 常识性规则，业务特定规则等) 检测和修正错误。 使用不同属性间的约束检测和修正错误。 使用外部数据检测和修正错误。 ( 3 ) 不一致数据的解决方法 不一致数据的产生主要是由于系统和应用造成的不同的数据类型、格式、制式、 粒度和编码方式等，另外由于错误的输入，硬件或软件故障，不及时更新造成的数 据库状态改变等。解决的方法，主要是在分析不一致性数据产生原因的基础上，应 用多种变换函数、格式函数、汇总分解函数和标准库函数去实现清洗。 2 重复记录的清洗方法 在有关数据质量的各种问题中，多数据源合并以及其他各种原因造成的重复信 息是最关键的问题之一。在r r 最发达的北美，信息重复对数据质量的影响平均要达 到6 3 ，而最高要达到2 2 5 1 5 1 。数据仓库中重复记录现象十分普遍，如何检测 和合并重复检测是数据清洗相关研究中的一项重要课题。消除重复记录的基本方法 是匹配与合并，匹配算法的核心是字段匹配。本文的第四章对重复记录的清洗方法 进行了重点研究。 2 2 数据清洗的基本流程 一般情况下，数据清洗的基本流程包括： 1 数据分析：数据分析是数据清洗的前提与基础，通过详尽的数据分析来检测 数据中的错误或不一致情况，除了手动检查数据或者数据样本之外，还可以使用分 析程序来获得关于数据属性的元数据，从而发现数据集中存在的质量问题。 一般情况下，模式中反映的元数据对于判断一个数据源的数据质量是远远不够 的。因此分析具体实例来获得有关数据属性和不寻常模式的元数据就变得很重要。 这些元数据可以帮助发现数据质量问题，也有助于发现属性闯的依赖关系，根据这 些依赖关系实现数据转换的自动化。 数据分析主要有两种方法：数据派生和数据挖掘。数据派生主要对单独的某个属 性进行实例分析。数据派生可以得到关于属性的很多信息，比如，数据类型、长度、 取值区间、离散值和他们的出现频率、不同值的个数，出现空缺值的次数，和典型 的字符串模式等。通过对数据应用领域的理解以及应用数理统计技术，可以得到属 性值的平均值、中间值、最大值、最小值和标准差等统计值。 数据挖掘帮助在大型数据集中发现特定的数据模式。可以通过数据挖掘来发现 属性问的一些完整性约束，如，函数依赖或者一些特定应用的商业规则等。它们可 1 0 青岛大学硕士学位论文 以用来填充缺失值，纠正不正确的值和确定多数据源间的重复记录。比如一个有着 很高的置信度的关联规则可以暗示出凡是违背它的数据都可能含有某些数据质量问 题，需要进一步的检查。 2 定义清洗转换规则与工作流：根据上一步进行数据分析得到的结果来定义 清洗转换规则与工作流。根据数据源的个数，数据源中不一致数据和“脏数据”多 少的程度，需要执行大量的数据转换和清洗步骤。要尽可能的为模式相关的数据清 洗和转换指定一种查询和匹配语言，从而使转换代码的自动生成变成可能。 3 验证：定义的清洗转换规则和工作流的正确性和效率应该进行验证和评估。 可以在数据源的数据样本上进行清洗验证，当不满足清洗要求时要对清洗转换规则、 工作流或系统参数进行调整和改进。真正的数据清洗过程中往往需要多次迭代的进 行分析，设计和验证，直到获得满意的清洗转换规则和工作流。它们的质量决定了 数据清洗的效率和质量。 4 清洗数据中存在的错误：在数据源上执行预先定义好的并且己经得到验证 的清洗转换规则和工作流。当直接在源数据上进行清洗时，需要备份源数据，以防 需要撤销上一次或几次的清洗操作。清洗时根据脏数据存在形式的不同，执行一系 列的转换步骤来解决模式层和实例层的数据质量问题。为处理单数据源问题并且为 其与其他数据源的合并做好准备，一般在各个数据源上应该分别进行几种类型的转 换，主要包括： 从自由格式的属性字段中抽取值( 属性分离) ：自由格式的属性一般包含着很 多的信息，而这些信息有时候需要细化成多个属性，从而进一步支持后面重复记录 的清洗。 确认和改正：这一步骤处理输入和拼写错误，并尽可能地使其自动化。基于字 典查询的拼写检查对于发现拼写错误是很有用的。 标准化：为了使实例匹配和合并变得更方便，我们应该把属性值转换成一个一 致和统一的格式。 5 干净数据的回流：当数据被清洗后。干净的数据应该替换数据源中原来的“脏 数据”。这样可以提高原系统的数据质量，还可避免将来再次抽取数据后进行重复 的清洗工作。 数据清洗的流程见图2 2 。 第二章数据清洗知识 2 3 数据清洗的评价标准 图2 2 数据清洗流程图 数据仓库中的数据清洗过程应能检测出并解决单数据源中或者多数据源集成过 程中存在的所有主要的数据质量问题，高效地处理大批量的数据，提高数据质量， 满足数据仓库对数据的要求，这是评价数据清洗效果的主要标准。可以下面三个方 面对数据清洗进行评价。 2 3 1 成本效益 在进行数据清洗之前考虑成本效益这个因素是很必要的。因为数据清洗是一项 十分繁重的工作，需要投入大量的时间、人力和物力。在进行数据清洗之前要考虑 其物质和时间开销的大小，是否会超过组织的承受能力。通常情况下大数据集的数 据清洗是一个系统性的工作，需要多方配合以及大量人员的参与，需要多种资源的 支持。 1 2 青岛大学硕士学位论文 2 3 2 数据质量 数据仓库中数据清洗的目的是提高数据质量，可以将数据清洗的结果一数据质 量，用来作为对数据清洗评价的标准。下面给出数据仓库中高质量的数据的参考特 征 1 7 ，1 8 】： ( 1 ) 数据的可访问性。例如一个属性字段中包括嵌入值时必须将其分解( 嵌入值 具有较差的可访问性) ( 2 ) 数据必须具有域完整性。也就是说数据值必须在定义范围之内。 ( 3 ) 数据必须是精确的。例如一个人的身份证号码尽管满足身份证编码规则( 具 有域完整性) ，但可能是另一个人的，此时仍然是不精确的。 ( 4 ) 数据必须被合适的集成以满足实体完整性。必须有一个属性或属性集识别实 体( 如客户或产品) 。例如：如果有关系某个客户的属性有1 5 个值存在，而仅能识 别1 4 个，则不具有实体完整性，查询该客户的业务会得到错误的信息。 ( 5 ) 数据必须遵守业务规则。 ( 6 ) 数据必须满足业务需求。 ( 7 ) 数据必须正确的定义参照完整性，防止被意外的破坏或改变。 ( 8 ) 数据必须一致。标准化的编码、格式及简写等简化了数据集成，有利于数据 在不同的系统、部门、业务流或业务伙伴之间的使用。 ( 9 ) 数据是适时的。 数据冗余是有目的的。例如，在数据仓库中为了提高性能存储了不同粒度的 统计数据，其它的冗余数据必须去除。 2 3 3 数据集成 数据仓库与一般应用系统的不同就在于它是一个支持管理决策过程的，面向主 体的、集成的、稳定的和随时间不断交化的数据集合【1 3 】。数据仓库环境下进行数 据清洗的另一个重要目的就是使其满足集成性的要求，主要体现在下述几方面： 清洗了不同系统的外部数据源中的数据。 数据被转换成一致的格式。 重复记录( 同一实体的不同的表现形式) 被识别出来，进行合并或删除。 证实数据有效合并成单一的、综合的和精确的商业视图。 第三章属性清洗 第三章属性清洗 本章主要介绍了数据清洗中属性清洗的基本知识，包括属性清洗的对象和属性 清洗的各种方法，重点研究了如何应用统计分析和人工智能技术自动检测数据集中 属性值的错误，并给出了在现实数据集上的实验及结果分析。 3 1 属性清洗的对象 属性清洗需要解决的数据质量问题主要有空值问题，错误值问题和不一致的数 据等，具体表现为下面的一些形式 1 9 ，2 0 】： 1 不精确值或错值：数据不能正确代表客观实体的状况。 2 拼写错误。 3 空值：包括缺失值与默认值。空值需要补上，默认值有时也需要用真实值代 替。 4 违反业务规则：属性值或者属性值之间的关系不遵循业务规则。例如：年龄 与出生日期不匹配。 5 同属性值的不同表现形式：属性值表示形式( 如格式和单位等) 随时间改 变或数据源的不同而不同。例如：性别的表示形式可以有0 1 、m f 和m a l e f e m a l e 等。 6 语义变化：属性值的语义随时间改变或数据源的不同而不同( 虽然值没有 变) 。例如：s a l a r y = “1 0 ”在1 9 9 0 年前指的是工资，而s a l a r y = “1 0 ”在1 9 9 0 年后 指的是工资的百分比。 7 嵌入值：一个属性值包含多个组成成分。例如：a d d r e s s = “青岛市宁夏路3 0 8 号青岛大学信息工程学院”，就可以分解为a d d r e s s = “青岛市宁夏路3 0 8 号”，s c h o o l = “青岛大学”，c o l l e g e = “信息工程学院”。 8 一个值分布在不同属性中：有时固定长度字段值被分布在两个或多个属性中 ( 一般由于字段长度限制所致或由多个字段信息生成一个更完整的字段时) 。例如： c i t y = “青岛市”，a d d r e s s = “宁夏路3 0 8 号”，那么整个地址信息由“青岛市宁夏路 3 0 8 号”表示。 3 2 属性清洗的基本方法 3 。2 1 缺失值的清洗方法