（计算机应用技术专业论文）数据仓库与数据挖掘中数据清洗的研究.pdf

华北电力大学硕士学位论文摘要 摘要 随着计算机网络和数据库技术的飞速发展以及人们获取数据手段的多样 化，我们所拥有的数据量急剧增加。但是基于劣质数据的决策是不可信的，数 掘质量问题是制约数掘仓库应用的“瓶颈”之一。数据仓库是数据挖掘和决策 分析的基础，数据清洗就是纠f 数据错误、降低决策风险的重要一环。该文介 绍了数据质量的概念和按其类型进行的分类，并概述了数据清洗的原理和方法 步骤。给出了基于规则的交互数掘清洗模型，并对各部分进行了定义。最后详 细阐述了数据清洗过程中的关键问题重复记录的识别和异常值的检测问题。在 现有方法的基础上给出了进一步的优化，提出了增量式的重复记录识别方法， 最后对其方法进行了测试和验证，在数据模式与匹配规则不变的前提下，增量 式重复记录识别方法大大节省了执行时间与空间的开销。 关键词：数据清洗，重复记录检测，s n m ，记录匹配 a b s t r a c t z h a n gj u n p e n g ( c o m p u t e ra p p l i e dt e c h n o l o g y ) d i r e c t e db ya s s o c i a t ep r o f h a nf e n g k e yw o r d s ：d a t a c l e a n i n g ，r e p e a t e dr e c o r de x a m i n a t i o n ，s n m ，r e c o r dm a t c h 一一一一一一 = 罴黛瓣 黧=抵呻?裟川暴裂豢溉 一一一一一一一一 麓善纛篆兰兰黑 声明 本人郑重声明：此处所提交的硕士学位论文数据仓库与数据挖掘中数据清洗 的研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工 作和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名： 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或 其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校 可以学术交流为目的，复制赠送和交换学位论文：同意学校可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 日期 导师签名塑丞 日期：皇盟l ! 生! ；o骋占 率如 辞一 华北电力大学硕士学位论文 第一章前言 本章对数据清洗和数掘质量的概念、研究内容及研究现状做了简单的介绍， 是全文研究工作的出发点。其中第一节对数据清洗问题的提出和概念进行了定义。 第二节说明了数据质量问题。第三节介绍了数据清洗工作的研究发展现状。第四节 介绍了本文的工作和全文的组织。 1 1 课题来源 随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的数 据资源日益丰富，数据量急剧增加，企业信息化的要求越来越迫切，其中一个很重 要的方面就是企业数据的管理。为了解决“进去的是垃圾，出来的也是垃圾 ( g a r b a g e in ，g a r b a g eo u t ) ”问题，支持f 确决策，就要求所管理的数据可靠， 没有错误，准确地反映企业的实际情况。因此，企业数据质量的管理正在获得越来 越多的关注。在很长一段时间里，数据挖掘的前期数据准备工作并没有得到足够的 重视。 建立挖掘数据库广f 1 数据清洗l 辛| 数据预处理 满意 知识描述与解释 数据挖掘 决策表约简 集台近似 逻辑推理 生成规则 生成可辨识矩阵 输出 编辑 图1 1d m 和k d d 的处理流程 图1 1 给了数据挖掘和知识发现中的处理流程，事实上，如果输入数据的质量 很差，那么数据挖掘返回的结果多半也是令人失望的。数据仓库和知识发现已经从 理论走向了实际应用，世界5 0 0 强企业中有9 9 使用了数据仓库进行信息辅助决策， 数据清洗( 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 ) 就是要解决这些 “脏数据( d i r t yd a t a ) ”的问题，保证信息源的数据质量，从而保证了辅助决策的 原始数据的正确性和准确性。没有数据清洗，很可能导致错误的决策，因此数据清 洗是构建数据仓库和知识发现的必要因素，有相当部分责任应该由数据清洗来承 担，即如何使得“进去的”不是“垃圾”。据统计，大型数据集中的错误率一般在 华北电力人学硕十学位论文 5 左右或者更高，需要有强大的工具能在大型的数据集中进行自动的数据清沈。 1 2 数据质量 对于政府而言，许多日常政务都将通过各种信息系统来实行，因此信息的质量 将极大地影响政府工作的效率和效果。而个人是大多数信息的最终接受者，毫无疑 问信息质量对丌人们的日常生活有着重大的影响。数据是各种信息系统提供信息服 务的基石，如果数据质量不符合或达不到要求，那么很难指望信息服务的质量能够 满足人们的要求。数据质量问题，是创建数据仓库以及进行数据集成工作中的致命 性问题。如果没有深刻地分析数据中存在的问题，就盲目进行玎发、集成，造成的 后果不仅是数据仓库创建失败的经济损失，更有可能造成严重的决策失误。数据质 量的基本要素：正确性( c o r r e c t n e s s ) 、一致性( c o n s is t e n c y ) 、完整性 ( c o m p e t e n e s s ) 和可靠性( r e l i a b i l i t y ) ，而数据质量被定义为这4 个指标在信息 系统中得到满足的程度”。在进行大量数据集成时，由于录入数据源的复杂性，其 中包括滥用缩写词、惯用语，数据输入错误、数据中的内嵌控制信息、重复记录、 丢失值、拼写变化、不同的计量单位和过时的编码等，给数据集成和数据仓库的创 建与维护都带来非常大的困难，往往导致数据仓库创建失败。 1 3 数据清洗的定义 数据清洗相对来说是一个比较新的领域，这个过程计算量较大，因此很难用传 统的一些算法操作，数据清洗领域有很多问题值得研究者去探索。 对于数据清洗的定义目前还没有共识。对于应用于不同领域中的数据清洗有 不同的解释。目前，数据清洗主要应用于三个领域：数据仓库( d w ) ，数掘库中的 知识发现( k d d ) 和数据质量管理( t d q m ) 。 在数据仓库领域中，数据清洗一般是应用在几个数据库合并时或多个数据源 进行集成时。指代同一个实体的记录，在合并后的数据库中就会出现重复的记录。 数据清洗过程就是要把这些重复的记录识别出来并消除它们，也就是所说的合并 清洗( m e r g e p u r g e ) 问题。这个问题的实例字面可称作记录链接、语义集成、实例 识别或对象标识问题。 从这个方面讲，数据清洗可有几种定义：数据清洗是消除数据的错误和不一 致和解决对象标识问题的过程：数据清洗是归并清洗问题。数据清洗并不是简单 地用优质数据更新记录，它还涉及数据的分解与重组。 t d q m 是一个学术界和商业界都感兴趣的领域。有很多论文提到数据质量及其 集成问题，但是很少涉及到数据清洗问题。有些文章从数据质量的角度论及过程管 理问题。在数据生命周期中，数据的获取和使用周期包括系列活动：评估、分析、 华北电力大学硕士学位论文 调整、丢弃数据。如果将数据清洗过程和数据生命周期循环集成起来，这一系列步 骤就从数据质量的角度给数据清洗下了定义。 最近，学术界有人将数据清洗视作k d d 过程的预备阶段，但是没有一个精确 的定义。不同的k d d 和数据挖掘以特定的方式执行数据清洗活动。有人利用信息的 模式来发现垃圾模式( 无意义的模式) ，并以此来执行一种数据清洗。在字符分类 问题可将机器学习技术应用于数据清洗过程。用数掘挖掘技术可帮助识别一系列错 误类型。至此，我们初步给出数据清洗定义：执行检查数据库，通过规则发现、数 据分析和数据校正来进行数据库信息模式重整、归并的过程。 数据清理定义为发现和清除数据中的错误和不一致来提高数据的质量。1 ，那么 数据清洗的任务就是通过各种措施从准确性、一致性、无冗余、符合应用的需求等 方面提高已有数据的质量。大多数数据质量问题可以在数据录入的初期阶段发现并 解决，称之为预防阶段。处理目标通常情况只是单一记录，因此只要具有充分的业 务规则就能基本保障录入数据的质量，然而我们面临的一个更为迫切的问题是如何 充分利用已经存在的大量历史数据和各种原始信息源中的数据。数据采集和数据库 技术的快速发展产生了大量的历史数据库，这些数据库的数据往往由同样年代久远 的信息系统产生和维护。由于这些信息系统本身的设计和当时各种技术的局限性， 使得这些历史数据库中的数据质量不能满足现在的现种应用程序的要求，因此就必 需采取一定的措施处理这些数据，使之符合新的应用场景。数据仓库和数据挖这样 海量数据的应用正是为了满足这样的需求。而建立数据仓库的过程中往往需要集成 历史数据、现行数据、以及来自不同数据源的各种数据。据统计在建立数据仓库的 过程中7 5 的工作量将投入到类似数据准备和数据装载这样的后端事务中。数据仓 库中数据质量的好坏是数据仓库应用成功与否的关键因素。许多数据仓库项目的失 败就是因为对导入数据仓库的各种数据质量缺乏足够的重视。因此建立数据仓库的 过程中，需要有效的技术手段和工具来提高导入数据仓库的数据质量。 数据清洗是一个非常复杂的任务，并且包含着一些互相关联的问题。一方面转 换必须尽可能具有通用性而且不依赖大量的编程工作，也就是支持在多领域内的 多种错误检测算法；另一方面，系统需要支持一种简单的接口定义来进行错误检测 和数据转换。因此，需要在现有的算法和功能基础上，设计相应的数据清洗系统， 使它具有相对的通用性和可交互性。通用性的主要实现技术有数据标准化、术语化、 通用的接口标准，即通用的过程描述语言，通用的数据结构以支持用户进行扩展。 可交互性支持用户通过系统反馈的检测统计图表，实时地修改转换过程，避免用户 与系统的隔离。 华北电力大学硕士学位论文 1 4 数据清洗研究的发展 针对数据质量的现状，很多学者提出了数据清洗的框架。但是数据清洗是一个 领域相关性非常强的工作，而且数据质量问题非常零散、复杂、不一致，到目前为 止没有形成通用的国际标准，只能根据不同的领域制定不同的清洗算法。目前的清 洗算法的优良性衡量标准有以下几个方面：返回率( r e c a l l ) ( 重复数据被正确识别 的百分率) ；f a l s e p o s i t iv ee r r o r ( 错误地作为重复数据记录的百分比) ：精确度 ( p r e c is i o n ) ( 算法识别的重复记录中的正确的重复记录的百分比) ；计算公式 ( p r e c i s i o n = 1 0 0 一f a ls e p o s i t i v ee r r o r ) 。 数据清洗主要分为检测和清洗两个步骤“。国内外的相关研究主要有以下几个 方面：( 1 ) 提出高效的数据异常检测算法，来避免扫描整个庞大的数据集： ( 2 ) 在自动检测数据异常和进行清洗处理的步骤间增加人工判断处理，咀防止对正确数 据的错误处理；( 3 ) 数据清洗时对数据集文件的处理；( 4 ) 如何消除合并后数据 集中的重复数据：( 5 ) 建立一个通用的领域无关的数据清洗框架：( 6 ) 关于模式 集成的问题。 目前已经提出一些数据清洗的模型川，如：基于粗糙集理论数据清沈“、基于 聚类模式数据清洗”1 、基于模糊匹配数据清洗模型、基于遗传神经网络数据清洗、 基于专家系统体系结构等数据清洗模型等。但这些模型都有着其不同程度的弊端。 以基于聚类模式的数据清洗为例： ( 1 ) 已有的聚类算法对直接检测异常作用不大。在对整个记录空间运用聚类算 法时能发现异常时所产生的聚类能作为下述两种方法的检测空间。其主要缺陷是耗 时，特别在记录条数多时，不适于检测异常。 ( 2 ) 在运用聚类算法的基础上，使用给予模式的方法( 每个字段使用欧式距离 采用k - m e a n 算法，k = 6 ) ，仅检测到了少量记录( o 3 ) 满足超过9 0 字段的模式。 ( 3 ) 经典的( 布尔型) 关联规则难以发现异常，但数量型关联规则、率规则 ( r a t i 0r u l e s ) 、序数关联规则能较好地检测异常与错误。 1 5 本文工作 在全面考察了数据质量和数据清洗技术的研究现状之后，本文针对数据质量问 题和单数据源与多数据源不同的脏数据情况提出了数据清洗的一般步骤和相关技 术，给出了交互型的数据清洗模型，并对清洗规则给出了详细的定义。针对数据清 洗研究中的核心关键f 0 7 题：重复记录的识别和异常值的检测进行了细致的阐述。并 在此基础上提出了增量式重复记录的检测方法，进行了试验，证明了其优点。 华北电力大学硕士学位论文 第二章数据清洗问题 本章中我们首先对数据质量问题的进行了分类介绍，并对单数据源和多数据源 不同情形的脏数据进行了举例，然后概括了数据清洗的原理，实现通常的步骤和方 法。最后对目前的数据清沈工具进行了介绍和总结。 2 1 数据质量问题的分类 根据处理的是单数据源还是多数据源以及问题出在模式层还是实例层，将数据 质量问题分为4 类” 。：六 穴二：! 六 s c h e m al e v e l n s t a n c el e v e ls c h e m al e v e ls c h e m al e v e l ( l a c k o f i n t e g r i t y ( d a t ae n t r ye r r o r s ) ( h e t e r o g e n e o u s d a t a ( o v e r l a p p i n g c o n s t r a i n t s ，p o o r - m i s s p e l l i n g m o d e l sa n ds c h e m a c o n t r a d i c t i n g a n d s c h e m ad e s i g n ) 。r e d u n d a n c y ，d u 州c a t e sd e s i g n s ) i n c o n s i s t e n td a t a ) - u n i q u e n e s sc o n s t r a i n t 一c o n t r a d i c t o r yv a l u e s n a m i n gc o n f l i c t s - i n c o n s i s t e n t r e f e r e n t i a li n t e g r i t y s t r u c t u r a lc o n f l i c t s a g g r e g a t i n g 图2 1 数据质量问题的分类 1 “。o 5 。mt i m i n g 在提高数据质量的过程中，通常面临着如下问题”1 ：( 1 ) 数据标准化：在不同的 数据源中，相同类型的信息可能表现为不同的格式，因此存在数据标准化的问题： ( 2 ) 数据结构和粒度问题：有些数据粒度太粗，比如地址信息既包括了城市、街道 信息，又包括了邮编等信息。因此需要通过分析，使其具有较好的粒度，结构性更 强：( 3 ) 数据不完整：比如地址信息中只有城市没有省份，缺少邮政编码，或者电 话号码不含区号：( 4 ) 数据重复问题：来自于多个数据源的数据对同个现实事物 可能存在着不一致的表示，因此数掘集成后可能有多条记录对应着同个现实中的 实体，但这些记录的数据不完全一样。如何识别出这些相似重复记录是一个非常重 要的问题。 2 1 1 单数据源问题 单个数据源中的数据质量问题主要有数据本身错误、数据冗余不一致、数据间 关联错误“3 。后两者主要是由于应用系统设计不合理，特别是数据模式设计不合理产 生的。前者通常是由用户使用时的人为错误引起的( 以下的叙述请参考表2 。2 的例 子) 。 华北电力大学硕士学f ：i ) ：论文 ( 1 ) 数据冗余的不一致。系统设计时为了用户使用的方便性或为了提高响应 速度，可能将同种数据分别在多地保存，分别进行维护，使这些数据之间一致性的 缺乏保证，导致一地数据的修改无法在另外一地的同一数据中得到反映，造成两地 数据的不一致，而且最终无法确定哪一部分的数据才是正确的。 ( 2 ) 数据之间关联错误。数据之间存在关联性：一种情况是一个数据实体中的 属性依赖关联，两个属性分别可以由对方推导计算出来( 实际上这也是一种冗余) ； 另外一种情况实体依赖关联，实体间使用关联属性来关联连接。前一种情况会产生 两个数据之间的不一致，后一种情况可能会丢失实体间关联性或者出现实体关联错 误。这通常由于数据库模式设计得不够合理造成的。 ( 3 ) 数据本身错误。数据本身的错误产生的原因有两个：没有进行数据的约束 设计和用户输入的人为错误。前者是在系统设计时没有对用户的输入进行约束，使 得用户可以输入不满足要求的数据。后者是由于很多数据都是以字符串来存储，无 法使用约束来保证数据的f 确性，需要用户f 确地输入相应的数据，但是用户输入 时往往会拼写出错或者录入完全错误的数据。 表2 2 单数据源数据质量举例 问题 7 脏数据描述 客户l = ( 姓名= “张强”，出生日客户1 和客户2 分别存储 期= 1 9 8 2 2 7 )在不同的地方，但是表示 数据冗余的不一致客户2 = ( 姓名= “张强”，出生日同一个学生，由于不同的 期= 19 8 2 3 7 )维护产生两个不一致的出 生日期 年龄= 2 7 ，出生日期= 1 9 8 2 2 7人的出生同期与年龄属性 属性依赖关联错误( 当前时间= 2 0 0 5 1 0 - 9 )可以相互导出，两者分别 出现会产生不一致 客户= ( 姓名= “张强”，城市= 1 2 )客户与城市是两个实体， 城市= ( 城市编号= 1 2 ，城市名称= 两个实体通过城市属性来 “b a o d i n g ”)关联。当城市实体中城市 实体依赖关联错误编号为1 2 的记录的城市名 称被改或记录被删除，客 户实体中的客户l 所在城 市的信息就丢失或者错误 出生日期= 1 9 8 2 一1 3 7这是一个错误的日期，可 未加约束造成的数以通过约束来保证正确 据输入错误性，出现这种错误是由于 系统中没有进行约束 城市名称= “b a o d i n ”城市名称本身使用一个字 未经校正的数据输 符串来存储，正确的 入错误 “b a o d i n g ”被错误的输入 为“b a o d i n ”，这种错误无 法使用约束来进行保证 华北电力大学硕士学位论文 2 1 2 多数据源问题 多个数据源中由于各个系统设计时是完全独立的而且是针对不同的应用需求 的，存在比单数据源中更多的数据质量问题。除了各个数据源中本身的数据存在错 误和不一致外，不同数据源之间存在模式的冲突和数据语义的不一致，数据的冗余 和冲突。模式冲突是模式的不一致，相同的信息对象采用了不同的结构( 结构冲突) 或者使用相同的结构但不同的名称来命名( 命名冲突) 。模式冲突可以有以下几种： ( 1 ) 命名冲突，即同一实体或属性使用了不同的名字( 2 ) 属性类型冲突，即同实体 属性使用不同的数据类型描述；( 3 ) 属性定义冲突，即同一实体中部分信息使用不同 的属性定义来描述；( 4 ) 结构冲突，即同一信息在一个数据源中使用多个实体通过关 联来描述，但在另个数据源中却使用一个实体来描述，或者一个对象在一个数据 源中表示为属性，而在另外一个数据源中表示为对象。如表2 3 所示。 表2 3模式冲突 问题数据源1数据源2描述 客户和顾客实体都表示 客户( 姓名，出顾客( 姓名，出客户的信息，出生日期和 命名冲突 生日期)生年月)出生年月属性都表示职 工的出生日期 客户( ，邮政编码客户( 邮政编码 相同的邮政编码属性一 属性类型冲突个被定义为数值型，另一 ( 数值型) ，)( 字符串) ，) 个被定义为字符串 地址信息在一个源中使 客户( ，地客户( ，省，市，用地址属性，另外一个使 属性定义冲突 址，)街道，门牌，)用省、市、街道、门牌四 个属性来描述 客户( ，城市编 客户信息在数据源l 中 客户( ，城号，) ，城市( 城 使用了一个实体表达，而 结构冲突数据源2 使用两个实体， 市，)市编号，城市名 通过一个关联属性来连 称) 接来描述 语义定义不一致是数据实例上的不一致( 值域不同) ，主要是因为系统设计是对 现实世界进行抽象。不同的设计者采用了不同的描述方法，常会造成同一个事物被 表达为不同的形式或者不同的事物表达为相同的形式( 表2 3 ) 。 华北电力大学硕士学位论文 表2 3 语义定义不一致 司题数据源1 数据源2描述 一个数据源中性别使用m f 表 性别( m f ) 性别( 1 o ) 示，另一个数据源中使用i 0 语义 表示 语 不一致 同样一个客户编号数据源1 中 义 客户编号客户编号 使用两位年份+ 区号+ 5 位内序 疋 9 6 0 3l2 0 0 2 8 5 0 3 1 2 1 9 9 6 0 0 2 8 5 号数据源2 中使用区号+ 四位 义年份+ 5 位内序号 不 数据源1 消费额指当年消费 不同客户消费( 。客户消费( ， 致 时间点 消费额，)消费额，) 额，数据源2 中的消费额是指 自客户开始至今的消费总额 不同 评估客户( ，数据源1 中的消费额是指月 月份，消费额， 评估客户( ，季 信息层 度，消费额，) 度消费额，而数据源2 中的消 费额是指季度消费额 数据的冗余冲突是由于各个数据源中保存了相同的数据信息，这些数据有可能 只是简单的重复，也可能是重复的数据还存在冲突。对于重复且冲突需要先进行冲 突消除，然后在集成的时候进行消除重复项。 无论是单数据源还是多数据源，数据清洗过程都要检测并且除去数据中所有明 显的错误和不一致，尽可能地减少人工干预和用户的编程量，而且要容易扩展到其 他数据源，应该和数据转化相结合，要有相应的描述语言来指定数据转化和数据清 洗操作。我们在下面的章节中将详细地给出介绍。 2 2 数据清洗过程 在了解了单数据源和多数据源中存在的各种数据质量问题之后，我们对数据清 洗的原理、实现方式和步骤进行一个大致的介绍。 2 2 1 数据清洗原理 数据清理原理“”：利用有关技术如数理统计、数据挖掘或预定义的清理规则将 脏数据转化为满足数据质量要求的数据，如表2 4 所示。 同一值的不同表示 无 7 脏数据 i 披a - 7 颤韬精埋策峪、列则r 一 i 满足数据质量要求的数据 表2 4 数据清理原理 不合法值 空值 异常检测 重复处理 华北电力大学硕士学位论文 数据清洗的第一个原则：面向主题。比如说做一个卫生健康情况的入户调查， 则姓名就不是重要的属性，可以舍弃。但如果是要做客户分析，则姓名就是重要信 息，必须采取措施进行处理。第二个原则：将数据处理成有意义的。如果某个属性 是身份证号，那有重复值将是毫无意义的，既不能做键值。也不能从中提出任何有 价值的信息因此要么舍弃，要么修复。第三个原则：不起坏作用的。如果某个数 据项在挖掘过程中具有显著意义，但在处理过程中又无法恢复其原有面貌，应该采 取措施让其保持“中庸”，即不干扰其它信息的分析。如年龄属性，如果用全部记 录的平均值将噪声数据替换掉，是一种可选的处理方法。第四个原则：效率原则。 尽管对挖掘型数据库的响应时间没有对操作型数据库的要求高，效率还是必需的。 处理的周期要尽可能快，数据挖掘的速度要尽可能快，零、低反应时间的数据更新 在企业的信息构架蓝图中将占主导地位。这一原则将体现在数据分割、数据约简等 一些处理过程中。 2 2 2 数据清洗的实现方式 按数据清理的实现方式与范围，可分为4 种情况1 ： ( 1 ) 手工实现，通过人工检查，只要投入足够的人力物力财力，也能发现所有错 误，但效率低下。在大数据量的情况下，几乎是不可能的。 ( 2 ) 通过专门编写的应用程序，这种方法能解决某个特定的问题，但不够灵活， 特别是在清理过程需要反复进行( 一般来说，数据清理一遍就达到要求的很少) 时， 导致程序复杂，清理过程变化时，工作量大。而且这种方法也没有充分利用目前数据 库提供的强大数据处理能力。 ( 3 ) 解决某类特定应用域的问题，如根据概率统计学原理查找数值异常的记录， 对姓名、地址、邮政编码等进行清理。这是目前研究得较多的领域，也是应用最成功 的一类。如商用系统：t r i l l i u ms o f t w a r e ，s y s t e mm a t c h m a k e r 等。 ( 4 ) 与特定应用领域无关的数据清理，这一部分的研究主要集中在清理重复的 记录上“，如d a t a c l e a n s e rd a t a b l a d em o d u l e ，i n t e g r i t y 系统等。 这4 种实现方法，由于后两种具有某种通用性，较大的实用性，引起了越来越多 的注意。但是不管哪种方法，大致都由三个阶段组成：( 1 ) 数据分析、定义错误类型； ( 2 ) 搜索、识别错误记录；( 3 ) 修正错误。第一阶段，尽管已有一些数据分析工具，但 仍以人工分析为主。根据数据错误类型分为两大类：单数据源与多数据源，并将它们 又各分为结构级与记录级错误。这种分类非常适合于解决数据仓库中的数据清理问 题。第二阶段，有两种基本的思路用于识别错误：一种是发掘数据中存在的模式，然 后利用这些模式清理数据：另一种是基于数据的，根据预定义的清理规则，查找不匹 配的记录。后者用得更多。第三阶段，某些特定领域能够根据发现的错误模式，编制 程序或借助于外部标准源文件、数据字典一定程度上修正错误：对数值字段，有时能 9 华北电力火学硕士学位论文 根据数理统计知识自动修正，但经常须编制复杂的程序或借助于人工干预完成“。我 们将在下一节中给出更加具体的介绍。 2 2 3 数据清洗的一般步骤 数据清理方法需要满足几个需求：首先发现和清除单个数据源中的错误数据和 不一致，其次在集成中，基于元数据和数据模式转换一起执行，将多个数据源中的数 据集成到统一的模式中。前一个需求主要是针对单数据源的数据质量问题，后一个 需求主要是针对多数据源集成中的数据质量问题。数据清理需要做的首先是分析数 据源中存在的质量问题，然后将所有的问题映射到预先定义好的错误类型上，使用 定义好的数据清理规则去描述如何清理这些错误不一致，然后使用数据清理工具按 照定义好的清理规则将错误和不一致清除修正。一般的数据清理被分成几个阶段来 完成1 ： ( 1 ) 数据分析阶段。分析各个数据源中数据的问题，包括单个数据源中的错误 和不一致，以及多个数据源中的模式冲突，语义定义不一致。数据分析一般使用两种 方法：数据剖析和数据挖掘。数据剖析主要用于自动地发现数据实例的错误和问 题。数据挖掘可以通过聚类分析和关联分析发现模式上的错误和不一致。这两种方 法主要用于自动发现数据源中的错误和不一致，很多错误和不一致无法通过自动的 方法来发现，需要让用户通过交互式的分析来定义。数据分析的结果是一些数据质 量问题描述，被保存到问题元数据库中，这样可以在下一个阶段中针对不同质量问 题定义相应的清理方式。 ( 2 ) 定义清理阶段。分析数据质量问题之后就是定义这些问题的清理方法。不 同的问题类型需要使用不同的方法去清理，有些清理过程还要定义一些必需的辅助 数掘。清理的方法主要有七种：格式化、合并、分割、选择、过滤、关联修正、聚 集。格式化主要针对于数据实例清理，用于错误数据清除和语义定义不一致数据的 替换，这种方法需要使用替换列表来将整个数据或者其中部分数据映射替换为正确 的数据。替换过程中首先需要发现原值中需要替换的项，然后搜索替换列表中的替 换项。合并主要针对数据冗余冲突的消除，检查整个模式是否有冗余的数据项，消去 这些冗余项。合并一般需要先使用格式化来清除错误数据或语义替换。分割主要是 为消除模式冲突，可以将单个属性分割成多个属性或者将多个属性的合并成一个属 性，也可以和选择结合将一个表中属性分割成几个不同意义的属性( 值不变) 或者分 割到几个表的属性中。选择主要针对模式的冲突，选择一个数据对象中的几个属性 组成另外一个对象，一般与合并、分割一起使用。过滤主要与分割一起使用，可以通 过某些属性的值来获取所需要的数据行。关联修正是专门针对数据值之间的关联错 误的，主要检查关联属性的值是不是错误，让用户自己进行选择替换。聚集主要针对 语义定义不一致中的不同层次上的信息冲突，使用聚集将低一层的数据信息聚集成 1 0 华北电力大学硕士学位论文 高一层的数据信息。为每一个错误选择清理方法后需要使用一种描述方法来描述， 同时将这些表述放到执行描述库中，以便清理执行机可以自动的执行这些清理。清 理方法的描述主要有两种方法：使用对象方法描述错误，使用清理函数描述： 使用类似于s o l 语句的方法描述。前者比较简洁容易让机器自动生成，后者比较熟 悉，语义比较明了，可以让用户自己进行编写。 ( 3 ) 执行清理阶段。根据定义好的清理过程自动执行，记录清理的过程和清理 中出现的问题，以及提供出现问题的处理措施。一般的清理过程可以认为是一个工 作流，清理需要与数据模式的转换一起工作，每一个步骤之间存在先后顺序。清理实 际的处理有两种方法”：使用程序模块执行：使用d b m s 提供的操作功能执 行。前者可以完成任何一种清理，但是开发工作量比较大，而且如果没有好的算法， 效率无法得到保证。后者可充分使用d b m s 提供高效的选择、排序、过滤、简单替 换、分割、聚集的功能，但是有些处理效率很低，比如有些字符串的替换，有些功能 无法实现比如根据条件替换，关联修正。所以可采用这两种方法的结合来处理，充分 使用d b m s 提供的功能，使用另外编制的程序模块来弥补d b m s 功能的不足。 数据清洗过程的步骤按顺序如下“：1 检查拼写错误。2 去掉重复的 ( o u p l i c a t e ) 记录。3 补上不完全的( i n c o m p l e t e ) 记录。4 解决不一致的 ( i u c o n s is t e n t ) 记录。5 用测试查询来验证数据。6 根据验证结果反复迭代上述 步骤。数据清洗是一个领域相关性非常强的工作，而且数据质量问题非常零散、复 杂、不一致，到目前为止没有形成通用的国际标准，只能根据不同的领域制定不同 的清洗算法。 2 2 4 数据清洗相关技术概述 与关系数据库不同，数据仓库并没有严格的数学理论基础，它更偏向于工程。 随着信息量的成倍增长，数据仓库存储了超大量的数据( t e r a b y t e 兆兆级) ，这些数 据可能来源于不同的数据源( o l t p 数据库、外部文件、历史数据等) 。不可避免地， 这些数据中存在很多异常，其中许多数据是冗余的、不完整的，甚至是错误的，如， 元数据的说明不完备或者丢失、缺少完整性约束、数据值不唯一、拼写错误、数据 输入错误和数据项不完整等。除内部数据的质量外，还有外部数据的质量问题，可 以说，数据质量问题是制约数据仓库应用的“瓶颈”之一。因此构建一个数据仓库 的重要步骤是将数据从源数据集中提取出来、排除噪声、减少冗余经过一系列的转 换、累积、关键字处理、结构转变以及聚集处理，装入数据仓库。针对不同的数据 质量问题数据清洗的方法有很多种，主要包括以下几种： 空缺值处理 目前的有关数据仓库的研究大多认为数据是完全的，但是，实际数据库( 如， 商业数据库和医院数据库) 中的数据很少是完全的：丢失的数据、观测不到的数据、 华北电力人学硕士学位论文 隐藏的数据、录入过程中发生错误的数据以及原始数据的不完善和错误等等是实际 数据库的常见弊病。数据仓库中的数据清洗过程必须接受数据不完善的挑战。基于 上述情况，人们提出了许多解决方法。 ( 1 ) 忽略元组：当类标号缺少时经常这样做。但是除非记录的多个属性都缺少 值，否则这个办法并不是很有效。因为虽然记录的某个属性缺少值，但是其他属性 的值可能是有用的。 ( 2 ) 人工填写空缺值：一般的说，这种方法很费时，并且数据集很大，缺少很多 的值的时候，该方法可能根本行不通。 ( 3 ) 使用一个全局常量填充空缺值：将空缺的属性值用同一个常数( 如 ”u n k n o w n ”) 替换。如果空缺值都用“u n k n o w n ”替换，挖掘程序可能误以为他们形 成了一个有趣的概念，因为他们都具有相同的值。因此，这种方法虽然简单，我们 并不推荐它。 ( 4 ) 使用属性的平均值填充空缺值。 ( 5 ) 使用与给定的记录属于同一类的所有样本的平均值。 ( 6 ) 使用最可能的值填充空缺值：可以用回归，基于推导的使用贝叶斯形式化方 法的工具或判定树归纳确定。、例如，利用数据集中其它顾客的属性，可以构造一颗 判定树来预测i n c o m e 的空缺值。 异常值检测 异常在聚类算法中的定义是嵌于聚类其中的背景噪声。异常点又叫做孤立点。 而异常探测算法对异常的定义是，异常是既不属于聚类也不属于背景噪声的点，它 们的行为与正常的行为有很大不同。异常值可能是度量或者执行错误所导致的。例 如，一个人的年龄为9 9 9 可能是程序对未记录的年龄缺省设置所产生的。另外，异 常值也可能是固有的数据变异性的结果。例如，一个公司的首席执行官的工资自然 远远高于公司其他雇员的工资，成为一个异常值。 数据异常的检测算法多种多样，大体可分为基于统计( s t a t i s t i c a l b a s e d ) 的方法、基于距离( d is t a n c e b a s e d ) 的方法、基于偏差( d e v i a t i o n b a s e d ) 的方法、 基于密度( d e n s i t y b a s e d ) 的方法和序数关联规则方法等。 基于统计的方法对给定的数据集合假设了一个分布或概率模型( 例如一个正态 分布) ，然后根据模型采用不一致性检验( d i s c o r d a n e yt e s t ) 来确定异常值。该检 验要求知道数据集参数( 例如假设的数据分布) 、分布参数( 例如平均值和方差) 和预 期的异常值个数。这个方法的主要缺点就是绝大多数检验都是针对单个属性的，而 许多数据挖掘问题要求在多位空间中发现异常值。而且，统计学方法要求关于数据 集合参数的知识，例如数据分布。但是在许多情况下，数据分布可能是未知的。当 没有特定的检验时，统计学方法不能确保发现所有的异常值，或者观察到的分布不 能恰当地被任何标准的分布来模拟。 1 2 华北电力大学硕士学位论文 为了解决统计学方法带来的一些限制，引入了基于距离( d is t a n c e b a s e d ) 的孤 立点的概念。如果数据集合s 中对象至少有p 部分与对象o 的距离大于d ，则对象o 是 一个带参数p 和d 的基于距离的( d b ) 孤立点，即d b ( p ，d ) 。换句话说，不依赖于统计 检验，我们可以将基于距离的异常点看作是那些没有足够多的邻居的对象，这里的 邻居是基于距给定对象的距离来定义的。目前己经开发了若干个高效的挖掘基于距 离的异常点的算法，概述如下： ( 1 ) 基于索引的算法：给定一个数据集合，基于索引的算法采用多维索引结构 ( 例如r 树或者k - d 树) ，来查找每个对象o 在半径d 范围内的邻居。设m 是一个孤立点 的d 领域内的最大对象数目。因此，一旦对象o 的m + 1 个邻居被发现，o 就不是孤立点。 这个算法在最坏的情况下的复杂度为0 ( k x 2 ) ，这里k 是维数，n 是数据集合中对象 的数目。 ( 2 ) 嵌套一循环算法：嵌套一循环算法和基于索引的算法有相同的计算复杂度， 但它避免了索引结构的构建，试图最小化i o 次数。它把内存的缓冲空问分为两半， 把数据集合分为若干个逻辑块。通过精心选择逻辑块装入每个缓冲区域的顺序，i 0 效率能够得到改善。 ( 3 ) 基于单元( c e l l 一b a s e d ) 的算法：为了避免0 ( n 2 ) 的计算复杂度，为驻留内存 的数据集合开发了基于单元的算法。它的复杂度是0 ( c + ”) ，这里c a 依赖于单元数 目的常数，k 是维数。在该方法中，数据空间划分为边长等于的单元窖每个单 元有两个层围绕着它。第一个层的厚度是一个单元，而第二个层的厚度是l2 t 一1 i 。 该算法逐个单元地对孤立点计数，而不是逐个对象地进行计数。对一个给定的单元， 它累计三个计数一单元中对象的数目，单元和第一层对象的数目，以及单元和两个 层次中的对象的数目。让我们把这些计数分别称为c e l l c o u n t ， c e l l 一+ | 一l a y e r c o u n t ，c e l l - w l a y e r c o u n t 。设m 是一个孤立点的d 一邻域内的最 大对象数目。在当前单元中的一个对象o 被认为是孤立点，仅当 c e l l + | l a y e r c o u n t 小于或者等于m 。如果这个条件不成立，那么该单元中所有的 对象可以从考察中清除。如果c e l l 一十一l a y e r c o u n t d , 于或者等于m ，那么单元中所 有的对象被认为是孤立点。否则，那么这个单元中的某些对象可能是孤立点。为了 探测这些孤立点，逐个对象进行处理。对单元中的每个对象o ，o 的第二层中的对象 被检查。对单元中的对象，只有那些d 一邻域内有不超过m 个点的对象是孤立点。 基于距离的异常点检测要求用户设置参数p 和d 。寻找这些参数的合适设置可能 涉及多次的试探和错误。基于偏离的异常值检测( d e v i a t i o n b a s e d ) 不采用统计检 验或基于距离的度量值来确定异常对象。相反，它通过检查一组对象的主要特征来 确定异常值，与给出的描述“偏离”的对象被称为是异常点。 序数型关联规则的方法，由于经典布尔关联规则不能提供足够的定量的和定性 的信息，必须进行扩展。序数型关联规则，用来发现给出更多信息的规则，定义如 l3 华北电力大学硕+ 学位论文 f ： 令b 2 碱，6 z ，一b n ) 是一个数据集，其中任一条记录b ，是数据项( 字段) 的集合。 ，2 f ，f z ，屯 是k 个数据项的集合。每个数据项有相同的取值范围d ( i i d ) 。如果 ( 1 ) i l 和，2 在 条记录的至少s 条中同时发生，其中s 是规则的支持度。 ( 2 ) 在i l 和i2 同时发生的记录的c 中，i l o p i 2 为真，其中c 为规则的置信 度：那么i 1 ，f2 = i l o pi2 ，其中o p 5 s ，2 ，2 j 是一个序数关联规则。该定义很容 易扩展到j = ，o pj 2o p j m o p ，。 ，5 1 ，) ，j2 t ，：，。，j m 是一个 项集，j ， 使用序数关联规则识别数据集中潜在的错误的过程可分为：( 1 ) 应用a p r i o r i 算 法的变形算法来生成有最小置信度c 的序数关联规则。( 2 ) 发现不符合这个规则的数 据项，它们可以被认为是异常点( 潜在的错误) 。 数据的分布会极大的影响数据错 误的识别过程，但序数关联规则的方法并不容易受到数据分布的影响，被证明更具 有强壮性。 重复记录元组检测 随着我们所能获得数据的逐渐增加，我们越来越渴望在任何可能的情况下对数 据进行集成。比如说，一个数据源中包含着有关己经发表的科学论文的参考文献的 数据，而另外的一个数据源包含着有关人们网页服务的信息。通过集成这两个数据 源，人们就可以直接通过作者的主页获得有关作者最近的文章的信息。但是在数据 集成的过程中，由于数据输入错误，不标准的缩写或者多数据源间有关纪录的细节 模式的差异，数据仓库中可能包含有关于同一客观实体的重复记录。数据清理的核 心就是近似重复记录的识别，所谓的重复记录是指表现形式下同，但语义上相同的 对象，从狭义的角度来看，如果两条记录在某些字段上的值相等或足够相似，则认 为这两条记录近似重复，简称重复记录元组。 为了消除数掘仓库中的重复记录，首先要考虑怎么样来确定两个记录是重复 的? 我们需要比较记录来确定他们之间的相似度( s i m i l a r i t y ) ，进而确定他们是否 是对同一客观实体的重复描述。记录匹配算法根据他们所包含的领域知识的多少而 不同。很多的算法使用基于指定领域知识的产品规则。产生这些规则需要很长的时 间而且当新的不符合原来的规则的数据加入时还要不断的更新”“。这些基于领域知 识的规则的另外一个缺点就是他们只能判断两个记录是或者不是重复记录，而无法 对相似记录进行检测。等价有的时候可能是一个程度问题，所以一个匹配算法应该 返回一个介于1 代表完全匹配和o 代表完全不匹配之间的小数“。每个特定的应用根 据自己的需要指定一个阈值，超过这个阈值的我们就可以认为是重复记录。 华北电力大学硕士学位论文 2 3 目前的数据清洗工具 2 3 1 特定的清洗工具 特定的清洗工具主要处理特殊的领域问题，例如姓名和地址数据的清洗，或者 消除重复。 ( 1 ) 特殊领域的清洗：姓名和地址在很多数据库都有记录而且有很大的基数。 他们提供抽取和转换姓名和地址信息到标准元素，与在基于清洗过的数据基础上的 工具相结合柬确认街道名称、城市和邮政编码。表2 5 3 出了在特殊领域的目前已 有的清洗工具列表。 工具名称厂商 i d c e n t r i cf ir s t l o g i c p u r e i n t e g r a t eo r a c l e q u i c k a d d r e s s q a s s y s t e m r e u n i o np it h e y b o w e s t r i l l i u m t r i l l i u ms o