数据清理关键技术及其软件平台的研究与应用

数据清理关键技术及其软件平台的研究与应用第一章 绪 论1.1 引 言我国目前正在大力推广信息技术，实施各行各业的信息化工程。随着信息化建设的不断深入，企事业单位积累了大量的电子数据，这些数据非常重要。为了使信息系统中的数据更准确、一致，能支持正确决策，就要求所管理的数据准确、可靠。因此，企业数据质量的管理正在获得越来越多的关注。但是，由于各种原因，如数据录入错误、不同来源数据引起的不同表示方法、数据间的不一致等，导致企业现有系统数据库中存在这样或那样的脏数据，主要表现为：不正确的字段值、重复的记录、拼写问题、不合法值、空值、不一致值、缩写词的不同，不遵循引用完整性等。根据“进去的是垃圾，出来的也是垃圾（garbage in，garbage out） ”这条原理，若不进行清理，这些脏数据会扭曲从数据中获得的信息，影响信息系统的运行效果，也为企业构建数据仓库、建立决策支持系统、应用商务智能带来隐患。显见，数据清理问题的重要性是不言而喻的。另外，从市场上众多的相关产品，也可以明白这一点。然而，由于数据清理本身的一些特点，比如：1) 数据清理是具体应用问题，经常要具体问题具体分析，难于归纳出通用方法；2) 数据清理问题的数学建模困难。因此，目前在学术界，数据清理并没有得到足够的关注，针对这方面的研究也少，有些人甚至认为数据清理是一个需要大量劳动力的过程，而且往往过于依赖特定应用领域。其实不然，对于数据清理有很多内容值得研究，比如：3) 在数据清理的研究中，尽管检测相似重复记录受到最多的关注，采取了许多措施，但检测效率与检测精度并不令人满意。特别是在数据量非常大时，耗时太多，有待于更好的方法。作者在文献中做了一些这方面工作，在相似重复记录检测中采用长度过滤方法优化相似检测算法，避免了不必要的编辑距离计算，从而提高了相似重复记录的检测效率；4) 在数据清理的相关研究中，数据清理整体框架的研究正逐渐成为研究的热点。对此，作者在文献7中提出一个可扩展的数据清理软件平台，该软件平台具有开放的规则库和算法库，通过在规则库中定义清理规则以及从算法库中选择合适的清理算法，可使该软件平台适用于不同的数据源，从而使其具有较强的通用性和适应性；5) 目前，对数据清理的研究主要集中在结构化数据上。由于半结构化数据 XML（Extensible Markup Language，可扩展标识语言）的快速增长以及广泛应用，其在数据清理中越来越重要。为了使 XML 数据源中的数据更准确、一致，如何清理这些 XML 相似重复数据，都是值得研究的 ，作者在文献8 中做了一些这方面工作；6) 另外，关于数据清理在一些业务领域中的应用也是值得研究，作者在文献9、10 中做了一些这方面的工作。当然，对任何现实世界中的数据源，人工完成数据清理是没有问题的。一些单位每年要花费上百万元来查找数据错误，手工清理是劳累的、费时的和易出错的。对于少量数据的数据源来说，采用人工清理就可以了，但对于规模较大的数据源，手工清理是不可行的，必须借助信息技术，采用自动清理方法。当然，在自动清理的过程中，仍需要人来参与，我们要做的就是尽可能减少人的参与。总之，在信息化建设过程中，数据清理是一个非常重要，而且较新的课题，有很多东西值得我们去研究。作为全文的引言，本章主要介绍数据质量的相关概念、数据清理的原理、数据清理软件平台的意义以及本文的内容安排。1.2 数据质量1.2.1 数据质量概念及分类目前，数据质量问题已引起广泛的关注。什么是数据质量呢？数据质量问题并不仅仅是指数据错误。文献22把数据质量定义为数据的一致性 （consistency ） 、正确性（correctness） 、完整性（completeness ）和最小性（minimality）这 4 个指标在信息系统中得到满足的程度，文献23则把“适合使用”作为衡量数据质量的初步标准。一般说来，评价数据质量最主要的几个指标是：1) 准确性（Accuracy）准确性是指数据源中实际数据值与假定正确数据值的一致程度；2) 完整性（Completeness）完整性是指数据源中需要数值的字段中无值缺失的程度；3) 一致性（Consistency）一致性是指数据源中数据对一组约束的满足程度；4) 唯一性（Uniqueness）唯一性是指数据源中记录以及编码是否唯一；5) 适时性（Timeliness ）适时性是指在所要求的或指定的时间提供一个或多个数据项的程度；6) 有效性（Validity）有效性是指维护的数据足够严格以满足分类准则的接受要求。当建立一个信息系统的时候，即使进行了良好的设计和规划，也不能保证在所有情况下，信息系统中数据的质量都能满足用户的要求。用户录入错误、企业合并以及企业环境随着时间的推移而改变，这些都会影响所存放数据的质量。信息系统中可能存在的数据质量问题有很多种，总结起来主要有以下几种：1) 重复的记录重复的记录是指在一个数据源中有指现实世界同一个实体的重复信息，或在多个数据源中有指现实世界同一个实体的重复信息。2) 不完整的数据由于录入错误等原因，字段值或记录未被记入数据库，造成信息系统数据源中应该有的字段或记录缺失。3) 不正确的数据由于录入错误，数据源中的数据未及时更新，或不正确的计算等，导致数据源中数据过时，或者一些数据与现实实体中字段的值不相符。4) 无法理解的数据值无法理解的数据值是指由于某些原因，导致数据源中的一些数据难以解释或无法解释，如伪值、多用途域、古怪的格式、密码数据等。5) 不一致的数据数据不一致包括了多种问题，比如，由不同数据源来的数据很容易发生不一致；同一数据源的数据也会因位置、单位以及时间不同产生不一致。在以上这些问题中，前三种问题在数据源中出现的最多。根据数据质量问题产生的原因，数据质量问题可分成单数据源问题和多数据源问题两个方面，其分类如图 1.1 所示。1.2.2 单数据源数据质量问题单数据源数据质量问题可以分成模式级和实例级两类问题进行分析，如图 1.1 所示。一个数据源的数据质量很大程度上决定于控制这些数据的模式和完整性约束的等级。没有模式的数据源，如文件，它对数据的输入和保存没有约束，于是出现错误和不一致的可能性就很大。因此，出现模式相关的数据质量问题是因为缺少合适的特定数据模型和特定的完整性约束，如差的模式设计，或者因为仅定义了很少一些约束来进行完整性控制。特定实例问题相关错误和不一致，如拼写错误，不能在模式级预防。另外，不唯一的模式级特定约束不能防止重复的实例，如关于同一现实实体的记录可能会以不同的字段值输入两次。无论是模式级问题还是实例级问题，可以分成字段、记录、记录类型和数据源四种不同的问题范围，分别说明如下：1) 字段：这类错误仅仅局限于单个字段的值。2) 记录：这类错误表现在同一条记录中不同字段值之间出现的不一致。3) 记录类型：这类错误表现在同一个数据源中不同记录之间的不一致关系。4) 数据源：这类错误表现在数据源中的某些字段值和其它数据源中相关值的不一致关系。四种不同情况的例子如表 1.1 和表 1.2 所示。表 1.1 单数据源中模式级的数据质量问题表 1.2 单数据源中实例级的数据质量问题1.2.3 多数据源集成时数据质量问题当多个数据源集成时，发生在单数据源中的这些问题会更加严重。这是因为每个数据源都是为了特定应用，单独开发、部署和维护的，这就很大程度上导致数据管理系统、数据模型、模式设计和实际数据的不同。每个数据源都可能含有脏数据，多数据源中的数据可能会出现不同表示、重复、冲突等现象。在模式级，模式设计的主要问题是命名冲突和结构冲突。命名冲突主要表现为不同的对象可能使用同一个命名，而同一对象可能使用不同的命名；结构冲突存在很多种不同的情况，一般是指在不同数据源中同一对象有不同表示，如不同的组成结构、不同的数据类型、不同的完整性约束等。除了模式级的冲突，很多冲突仅出现在实例级上，即数据冲突。由于不同数据源中数据的表示可能会不同，单数据源中的所有问题都可能会出现，比如重复的记录、冲突的记录等。此外，在整个数据源中，尽管有时不同的数据源中有相同的字段名和类型，仍可能存在不同的数值表示，如对性别的描述，一个数据源中可能用“0/1”来描述，另一个数据源中可能会用“F/M”来描述，或者对一些数值的不同表示，如一个数据源中度量单位制可能用美元，另一个数据源中可能会用欧元。此外，不同数据源中的信息可能表示在不同的聚集级别上，如一个数据源中信息可能指的是每种产品的销售量，而另一个数据源中信息可能指的是每组产品的销售量。多数据源集成中的数据清理问题也是信息化建设中面临的一个重要问题。对于这个问题，作者会在第五章进行研究。1.3 数据清理内涵及原理通过以上对数据质量问题的分析，可以看出：数据质量问题是信息化建设中的一个重要问题，为了提高信息系统的数据质量，研究数据清理非常重要。数据清理（data cleaning）也称数据清洗。数据清理的三个主要领域包括：数据仓库（Data Warehouse，DW） 、数据库中的知识发现（ Knowledge Discovery in Databases，KDD）和综合数据质量管理（Total Data Quality Management，TDQM） 。数据清理在不同的应用领域其要求不完全相同，如在数据仓库环境下，数据清理是 ETL（Extraction 抽取、Transition 转换、Load 加载，ETL ）过程的一个重要部分，要考虑数据仓库的集成性与面向主题的需要，包括数据的清理及结构转换；在 KDD 中，数据清理主要是提高数据的可利用性，如去除噪声、无关数据、空值，考虑时间顺序和数据的变化等，但主要内容还是一样的。目前，对于数据清理没有统一的定义。文献30认为数据清理是一个消除数据中的错误和不一致，解决对象识别问题的过程，文献31则把数据清理定义为重复记录的合并 /清理问题。一般来说，从广义上讲，数据清理是将数据库精简以除去重复记录，并使剩余部分转换成标准可接收格式的过程；而狭义上的数据清理是特指在构建数据仓库和实现数据挖掘前对数据源进行处理，使数据实现准确性、完整性、一致性、唯一性、适时性、有效性以适应后续操作的过程。本文的研究是以信息化建设为背景，研究的重点是提高信息系统的数据质量，故作者本人认为：凡是有助于提高信息系统数据质量的处理过程，都可认为是数据清理。所以，数据清理可简单看成就是从数据源中清除错误数值和重复记录，即利用有关技术如数理统计、数据挖掘或预定义的清理规则等，从数据源中检测和消除错误数据、不完整数据和重复数据，从而提高信息系统的数据质量。一般说来，数据清理包括以下几个步骤：1) 数据分析数据分析是指从数据中发现控制数据的一般规则，比如字段域、业务规则等。通过对数据的分析，可定义出数据清理的规则，并选择合适的清理算法。2) 数据检测数据检测是指根据预定义的清理规则及相关数据清理算法，检测数据是否正确，比如是否满足字段域、业务规则等，或检测记录是否是重复记录。3) 数据修正数据修正是指手工或自动地修正检测到的错误数据或处理重复的记录。对于数据清理应该满足：数据清理应该能检测和消除所有主要的错误和不一致，包括单数据源和多数据源集成时；数据清理方法能被这样的工具支持，人工检测和编程工作要尽可能少，并具有可扩展性。根据以上分析，数据清理的原理可总结为如图 1.2 所示1.4 数据清理研究现状分析1.4.1 国外研究动态数据清理的相关研究最早可追溯到 1959 年。自那时起，合并来自不同数据源的数据是一直被认为是一个重要而且很困难的问题，这些问题被作为记录连接、实例识别、对象识别等问题来研究。它们曾经是医疗、商业、税务领域中的研究重点之一，在流行病的研究、欺骗检测等方面都起到重要作用。这些问题的研究可以看成是数据清理的源头。近年来，随着信息化的进展，国外开始系统地研究数据清理问题。目前，在数据清理算法、方法和商用系统上都取得了一些成果。主要成果可分类如下：1) 特殊域清理特殊域清理工具主要解决某类特定应用域的数据清理问题，大多数是姓名和地址数据。比如：根据概率统计学原理查找数值异常的记录；对姓名、地址、邮政编码等进行清理等，这是目前研究得较多的领域，也是应用最成功的一类。如商用系统：Trillinm Software、Pure Integrate（Oracle） 、Quick Address（QAS Systems）等。它们用一个匹配工具抽取被清理的数据，并把姓名和地址信息转换成单个标准元素、有效的街道名、城市和邮政编码。它们具体表现为用一个大的预定义的规则库，来处理在清理过程中发现的问题。比如，Trillinm Software 的抽取和匹配模型包含二十多万个商业规则。这些工具也提供了针对特定应用，使用户自定义规则来定制或扩展规则库的工具。2) 与特定应用领域无关的数据清理与特定应用领域无关的数据清理研究主要集中在清理重复的记录上，其主要工具包括：Data Blade Module，ChoiceMaker，Integrity，Merge/Purge Library（Sagent/QM Software） ，Match IT（Help IT Systems） ， Master Merge（Pitney Bowes） ，Data Cleanser （EDD）等。3) 数据清理框架为了使数据清理具有一定的通用性，近年来，关于数据清理的框架也有了一些研究。文献44提出了一个数据清理框架，该框架清晰地分离逻辑规范层和物理实现层。用户可以在逻辑层设计数据处理流程，确定清理过程需要执行的数据转化步骤；在物理层实现这些数据转化操作，并对它们进行优化。例如，用户为了计算记录之间的相似度，对输入数据集指定执行匹配操作，而在物理层，数据清理系统会根据实际数据的特点，选择一个特定的实现方法。该算法可以进行优化，它无须计算所有记录对的相似度，而同时又不会损害所要求的结果。除了分离逻辑层和物理层以外，文献44还提出了一种描述性语言，该描述性语言可以在逻辑层上指定数据清理过程所需采取的数据转化操作，并指定何时可以弹出例外，要求用户的交互。该描述性语言还可以指定一些数据转化操作的参数，比如记录匹配操作所使用的距离函数等。在44研究的基础上，文献 30,45实现了一个可扩展的数据清理工具 AJAX。文献3,46提出了一个关于数据清理的交互式系统框架，该框架把数据转化和差异检测（discrepancy detection）紧密地集成在一起。用户面对表单风格的界面，能够以直观的图形化方式逐步建立起整个数据转化过程。在此过程中，用户可以执行或者撤消转化操作，而且操作的结果马上就可以在屏幕上看到。后台进程以增量方式检测转化后数据中存在的问题，如果检测到，则及时报告给用户。用户利用系统提供的基本数据转化操作，无须书写复杂的程序就能够完成数据清理任务，而且用户能够随时看到每一步转化操作后的结果，没有很长的延迟。因此，该系统框架具有较好的交互性。再来看一下其它一些与数据清理有关的工具。市场上有很多工具都支持数据转换和数据清理工作，特别是针对数据仓库。1) 数据分析工具数据分析工具能处理实例数据、识别数据错误和不一致，从而得到相应的清理转换。数据分析工具可分成数据剖析和数据挖掘工具。Evoke Software 公司的 MigrationArchitect是少数商用数据剖析工具的一种，它能分析出每一个字段的元数据，比如：数据类型、长度、集的势、离散值和它们的百分比、最小和最大值、缺失值、以及独特性。Migration Architect 对开发数据迁移的目标模式也有所帮助。数据挖掘工具，如 WizSoft 公司的 WizRule 和 Information Discovery 公司的 Data Mining Suite 能推断字段和它们的值之间的关系，并计算出一个置信度来指示符合条件的记录。WizRule 能显示三种规则：数据公式、IF-THEN 规则，以及能指示姓名拼写错误的基于拼写的规则。WizRule 也能自动地把那些偏离发现规则集的数据指定为可疑错误。2) 数据再工程工具数据再工程工具也能处理实例数据、识别数据错误和不一致，从而得到相应的清理转换。比如，Vality 的 Integrity 可以利用检测模型和规则执行清理转换。3) ETL 工具ETL 是数据仓库系统中数据处理的关键操作。ETL 操作的实质就是根据数据处理的需要，将源数据对象经过 ETL 处理后加载到目标数据对象中。很多商业工具在很多方面支持数据仓库的 ETL 过程，如 Data Stage（Ardent） 、Data TransformationService（Microsoft） 、Warehouse Administrator（SAS） 、PowerMart（Informatica）等。这些工具在关系数据库系统上建立一个存储器，以统一的方式管理关于数据源、目标模式、映射、脚本程序等所有元数据。通过文件、关系数据系统、以及标准接口，比如 ODBC（Open Database Connectivity，开放式数据库连接） ，可以从操作型数据源中抽取模式和数据。数据转换用一个容易使用的图形界面来定义。为了指定单个的映射步骤，需要提供一个单独的规则语言和一个全面的预定义转换规则的库。虽然这些 ETL 工具能够提供大量数据的抽取、转换和集成操作，但往往只能提供有限的数据清理支持。也就是说，ETL 工具并不是完全针对数据清理。1.4.2 国内研究动态由于发达国家的信息化程度较高，各种信息系统的使用范围广、时间长，因此对数据清理的需求显得较为迫切，所以关于数据清理的研究大多都集中在国外，而国外关于数据清理的研究主要是针对西文表示的数据，这些数据清理方法不一定完全适用于中文表示的数据。随着国内信息化建设的快速发展，数据质量问题也越来越受到关注，对数据清理的研究也逐步展开，并取得了一定的成果，主要研究情况如下：复旦大学以周傲英教授为首的研究小组较早地认识到数据清理研究的重要价值，并已开始了数据清理的研究工作，目前他们取得的主要成果有：1) 提出了一个可扩展数据清洗框架的定义该清洗框架以术语模型、处理描述文件、共享库等概念和技术实现了模块功能的可定制、系统的开放性和可扩展性。2) 提出了一种基于 N-Gram 的相似重复记录检测方法该方法先计算各记录的 N-Gram 值，然后以各记录的 N-Gram 值为排序键进行排序，再通过采用一种高效的应用无关的 Pair-wise 比较算法，通过计算两记录中单词间的编辑距离来判断记录的相似与否，并采用一种改进的优先队列算法来准确地聚类相似重复记录。该方法在一定程度上有效地解决了相似重复记录的检测问题，但当数据量大，错误多，单词间有互相影响时，该方法的初步聚类效果就会受到很大的影响。此外，该方法主要针对西文数据库环境，不适用于中文数据库环境。3) 研究了一种检测多语言数据重复记录的综合方法该方法充分考虑了中文数据库的环境，有效地解决了多语言数据记录的初步聚类和记录比较问题。北京大学对数据清理也做了一些相关研究，他们主要解决了针对于客户关系管理中客户数据集成时重复记录的数据清理问题。东南大学以董逸生教授为首的研究小组也对数据清理做了一些研究，他们主要是针对数据仓库化过程中的数据清理问题进行研究。对于数据清理，作者本人在信息化实践的基础上，根据信息化建设的实际需要，也做了系统的研究，并取得了一些研究成果，相关内容会在后面的章节中做具体的论述。1.4.3 存在的问题目前，从国内外关于数据清理的研究现状来看，主要体现在以下几个方面的不足：1) 数据清理属于一个较新的研究课题，直接针对这方面的研究并不多。此外，数据清理的研究目前主要集中在西文数据库上，中文数据清理与西文数据清理有较大的不同，如很多排序方法并不完全适用于中文数据库，中文数据清理没有引起重视。2) 数据清理的研究主要集中在字符型数据上，识别数值型字段之间的关系异常很不成熟与实用，数据挖掘算法在数据清理中的应用需要加强。3) 尽管检测重复记录受到很大的关注，采取了许多措施，但检测效率与检测精度问题并不令人满意。特别是在数据量比较大时，耗时太多，有待于更好的检测算法。4) 多数数据清理工具都是针对特定的领域，其应用受到一定的限制。在将来，特定领域的数据清理仍将是应用重点，但较通用的清理方案会受到越来越多的关注。5) 国产的数据清理工具还很少，少量的国产数据清理工具主要研究了重复记录的清理问题，目前还很少研究关于不完整数据、错误数据的清理问题，还没有利用孤立点检测的方法来检测数据源中的错误数据。6) 目前，数据清理的研究主要集中在结构化数据上。半结构化的数据，如 XML 数据已受到越来越多的重视，特别是由于 XML 自身所具有的特点，如通用性、自描述性，其在数据清理中应受到重视。1.5 数据清理软件平台的意义为了完成数据清理的任务，满足信息化建设的需要，必须研制一个数据清理工具。由于数据清理的复杂性，数据清理涉及多种不同的清理算法以及清理规则，对数据清理工具有以下要求：1) 对数据源进行数据清理时，清理相似重复记