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

1、数据清理关键技术及其软件平台的研究与应用第一章 绪 论1.1 引 言我国目前正在大力推广信息技术，实施各行各业的信息化工程。随着信息化建设的不断深入，企事业单位积累了大量的电子数据，这些数据非常重要。为了使信息系统中的数据更准确、一致，能支持正确决策，就要求所管理的数据准确、可靠。因此，企业数据质量的管理正在获得越来越多的关注。但是，由于各种原因，如数据录入错误、不同来源数据引起的不同表示方法、数据间的不一致等，导致企业现有系统数据库中存在这样或那样的脏数据，主要表现为：不正确的字段值、重复的记录、拼写问题、不合法值、空值、不一致值、缩写词的不同，不遵循引用完整性等。根据“进去的是垃圾，出来的

2、也是垃圾（garbage in，garbage out）”这条原理，若不进行清理，这些脏数据会扭曲从数据中获得的信息，影响信息系统的运行效果，也为企业构建数据仓库、建立决策支持系统、应用商务智能带来隐患。显见，数据清理问题的重要性是不言而喻的。另外，从市场上众多的相关产品，也可以明白这一点。然而，由于数据清理本身的一些特点，比如：1) 数据清理是具体应用问题，经常要具体问题具体分析，难于归纳出通用方法；2) 数据清理问题的数学建模困难。因此，目前在学术界，数据清理并没有得到足够的关注，针对这方面的研究也少，有些人甚至认为数据清理是一个需要大量劳动力的过程，而且往往过于依赖特定应用领域。其实不然

3、，对于数据清理有很多内容值得研究，比如：3) 在数据清理的研究中，尽管检测相似重复记录受到最多的关注，采取了许多措施，但检测效率与检测精度并不令人满意。特别是在数据量非常大时，耗时太多，有待于更好的方法。作者在文献中做了一些这方面工作，在相似重复记录检测中采用长度过滤方法优化相似检测算法，避免了不必要的编辑距离计算，从而提高了相似重复记录的检测效率；4) 在数据清理的相关研究中，数据清理整体框架的研究正逐渐成为研究的热点。对此，作者在文献7中提出一个可扩展的数据清理软件平台，该软件平台具有开放的规则库和算法库，通过在规则库中定义清理规则以及从算法库中选择合适的清理算法，可使该软件平台适用于不同

4、的数据源，从而使其具有较强的通用性和适应性；5) 目前，对数据清理的研究主要集中在结构化数据上。由于半结构化数据 XML（Extensible Markup Language，可扩展标识语言）的快速增长以及广泛应用，其在数据清理中越来越重要。为了使 XML 数据源中的数据更准确、一致，如何清理这些 XML 相似重复数据，都是值得研究的，作者在文献8中做了一些这方面工作；6) 另外，关于数据清理在一些业务领域中的应用也是值得研究，作者在文献9、10中做了一些这方面的工作。当然，对任何现实世界中的数据源，人工完成数据清理是没有问题的。一些单位每年要花费上百万元来查找数据错误，手工清理是劳累的、费时

5、的和易出错的。对于少量数据的数据源来说，采用人工清理就可以了，但对于规模较大的数据源，手工清理是不可行的，必须借助信息技术，采用自动清理方法。当然，在自动清理的过程中，仍需要人来参与，我们要做的就是尽可能减少人的参与。总之，在信息化建设过程中，数据清理是一个非常重要，而且较新的课题，有很多东西值得我们去研究。作为全文的引言，本章主要介绍数据质量的相关概念、数据清理的原理、数据清理软件平台的意义以及本文的内容安排。1.2 数据质量1.2.1 数据质量概念及分类目前，数据质量问题已引起广泛的关注。什么是数据质量呢？数据质量问题并不仅仅是指数据错误。文献22把数据质量定义为数据的一致性（consis

6、tency）、正确性（correctness）、完整性（completeness）和最小性（minimality）这 4 个指标在信息系统中得到满足的程度，文献23则把“适合使用”作为衡量数据质量的初步标准。一般说来，评价数据质量最主要的几个指标是：1) 准确性（Accuracy）准确性是指数据源中实际数据值与假定正确数据值的一致程度；2) 完整性（Completeness）完整性是指数据源中需要数值的字段中无值缺失的程度；3) 一致性（Consistency）一致性是指数据源中数据对一组约束的满足程度；4) 唯一性（Uniqueness）唯一性是指数据源中记录以及编码是否唯一；5) 适时性（

7、Timeliness）适时性是指在所要求的或指定的时间提供一个或多个数据项的程度；6) 有效性（Validity）有效性是指维护的数据足够严格以满足分类准则的接受要求。当建立一个信息系统的时候，即使进行了良好的设计和规划，也不能保证在所有情况下，信息系统中数据的质量都能满足用户的要求。用户录入错误、企业合并以及企业环境随着时间的推移而改变，这些都会影响所存放数据的质量。信息系统中可能存在的数据质量问题有很多种，总结起来主要有以下几种：1) 重复的记录重复的记录是指在一个数据源中有指现实世界同一个实体的重复信息，或在多个数据源中有指现实世界同一个实体的重复信息。2) 不完整的数据由于录入错误等原

8、因，字段值或记录未被记入数据库，造成信息系统数据源中应该有的字段或记录缺失。3) 不正确的数据由于录入错误，数据源中的数据未及时更新，或不正确的计算等，导致数据源中数据过时，或者一些数据与现实实体中字段的值不相符。4) 无法理解的数据值无法理解的数据值是指由于某些原因，导致数据源中的一些数据难以解释或无法解释，如伪值、多用途域、古怪的格式、密码数据等。5) 不一致的数据数据不一致包括了多种问题，比如，由不同数据源来的数据很容易发生不一致；同一数据源的数据也会因位置、单位以及时间不同产生不一致。在以上这些问题中，前三种问题在数据源中出现的最多。根据数据质量问题产生的原因，数据质量问题可分成单数据

9、源问题和多数据源问题两个方面，其分类如图 1.1所示。1.2.2 单数据源数据质量问题单数据源数据质量问题可以分成模式级和实例级两类问题进行分析，如图 1.1 所示。一个数据源的数据质量很大程度上决定于控制这些数据的模式和完整性约束的等级。没有模式的数据源，如文件，它对数据的输入和保存没有约束，于是出现错误和不一致的可能性就很大。因此，出现模式相关的数据质量问题是因为缺少合适的特定数据模型和特定的完整性约束，如差的模式设计，或者因为仅定义了很少一些约束来进行完整性控制。特定实例问题相关错误和不一致，如拼写错误，不能在模式级预防。另外，不唯一的模式级特定约束不能防止重复的实例，如关于同一现实实体

10、的记录可能会以不同的字段值输入两次。无论是模式级问题还是实例级问题，可以分成字段、记录、记录类型和数据源四种不同的问题范围，分别说明如下：1) 字段：这类错误仅仅局限于单个字段的值。2) 记录：这类错误表现在同一条记录中不同字段值之间出现的不一致。3) 记录类型：这类错误表现在同一个数据源中不同记录之间的不一致关系。4) 数据源：这类错误表现在数据源中的某些字段值和其它数据源中相关值的不一致关系。四种不同情况的例子如表 1.1 和表 1.2 所示。表 1.1 单数据源中模式级的数据质量问题表 1.2 单数据源中实例级的数据质量问题1.2.3 多数据源集成时数据质量问题当多个数据源集成时，发生在

11、单数据源中的这些问题会更加严重。这是因为每个数据源都是为了特定应用，单独开发、部署和维护的，这就很大程度上导致数据管理系统、数据模型、模式设计和实际数据的不同。每个数据源都可能含有脏数据，多数据源中的数据可能会出现不同表示、重复、冲突等现象。在模式级，模式设计的主要问题是命名冲突和结构冲突。命名冲突主要表现为不同的对象可能使用同一个命名，而同一对象可能使用不同的命名；结构冲突存在很多种不同的情况，一般是指在不同数据源中同一对象有不同表示，如不同的组成结构、不同的数据类型、不同的完整性约束等。除了模式级的冲突，很多冲突仅出现在实例级上，即数据冲突。由于不同数据源中数据的表示可能会不同，单数据源中

12、的所有问题都可能会出现，比如重复的记录、冲突的记录等。此外，在整个数据源中，尽管有时不同的数据源中有相同的字段名和类型，仍可能存在不同的数值表示，如对性别的描述，一个数据源中可能用“0/1”来描述，另一个数据源中可能会用“F/M”来描述，或者对一些数值的不同表示，如一个数据源中度量单位制可能用美元，另一个数据源中可能会用欧元。此外，不同数据源中的信息可能表示在不同的聚集级别上，如一个数据源中信息可能指的是每种产品的销售量，而另一个数据源中信息可能指的是每组产品的销售量。多数据源集成中的数据清理问题也是信息化建设中面临的一个重要问题。对于这个问题，作者会在第五章进行研究。1.3 数据清理内涵及原

13、理通过以上对数据质量问题的分析，可以看出：数据质量问题是信息化建设中的一个重要问题，为了提高信息系统的数据质量，研究数据清理非常重要。数据清理（data cleaning）也称数据清洗。数据清理的三个主要领域包括：数据仓库（Data Warehouse，DW）、数据库中的知识发现（Knowledge Discovery in Databases，KDD）和综合数据质量管理（Total Data Quality Management，TDQM）。数据清理在不同的应用领域其要求不完全相同，如在数据仓库环境下，数据清理是 ETL（Extraction抽取、Transition 转换、Load 加载，

14、ETL）过程的一个重要部分，要考虑数据仓库的集成性与面向主题的需要，包括数据的清理及结构转换；在 KDD 中，数据清理主要是提高数据的可利用性，如去除噪声、无关数据、空值，考虑时间顺序和数据的变化等，但主要内容还是一样的。目前，对于数据清理没有统一的定义。文献30认为数据清理是一个消除数据中的错误和不一致，解决对象识别问题的过程，文献31则把数据清理定义为重复记录的合并/清理问题。一般来说，从广义上讲，数据清理是将数据库精简以除去重复记录，并使剩余部分转换成标准可接收格式的过程；而狭义上的数据清理是特指在构建数据仓库和实现数据挖掘前对数据源进行处理，使数据实现准确性、完整性、一致性、唯一性、适

15、时性、有效性以适应后续操作的过程。本文的研究是以信息化建设为背景，研究的重点是提高信息系统的数据质量，故作者本人认为：凡是有助于提高信息系统数据质量的处理过程，都可认为是数据清理。所以，数据清理可简单看成就是从数据源中清除错误数值和重复记录，即利用有关技术如数理统计、数据挖掘或预定义的清理规则等，从数据源中检测和消除错误数据、不完整数据和重复数据，从而提高信息系统的数据质量。一般说来，数据清理包括以下几个步骤：1) 数据分析数据分析是指从数据中发现控制数据的一般规则，比如字段域、业务规则等。通过对数据的分析，可定义出数据清理的规则，并选择合适的清理算法。2) 数据检测数据检测是指根据预定义的清

16、理规则及相关数据清理算法，检测数据是否正确，比如是否满足字段域、业务规则等，或检测记录是否是重复记录。3) 数据修正数据修正是指手工或自动地修正检测到的错误数据或处理重复的记录。对于数据清理应该满足：数据清理应该能检测和消除所有主要的错误和不一致，包括单数据源和多数据源集成时；数据清理方法能被这样的工具支持，人工检测和编程工作要尽可能少，并具有可扩展性。根据以上分析，数据清理的原理可总结为如图 1.2 所示1.4 数据清理研究现状分析1.4.1 国外研究动态数据清理的相关研究最早可追溯到 1959 年。自那时起，合并来自不同数据源的数据是一直被认为是一个重要而且很困难的问题，这些问题被作为记录

17、连接、实例识别、对象识别等问题来研究。它们曾经是医疗、商业、税务领域中的研究重点之一，在流行病的研究、欺骗检测等方面都起到重要作用。这些问题的研究可以看成是数据清理的源头。近年来，随着信息化的进展，国外开始系统地研究数据清理问题。目前，在数据清理算法、方法和商用系统上都取得了一些成果。主要成果可分类如下：1) 特殊域清理特殊域清理工具主要解决某类特定应用域的数据清理问题，大多数是姓名和地址数据。比如：根据概率统计学原理查找数值异常的记录；对姓名、地址、邮政编码等进行清理等，这是目前研究得较多的领域，也是应用最成功的一类。如商用系统：Trillinm Software、Pure Integrat

18、e（Oracle）、Quick Address（QAS Systems）等。它们用一个匹配工具抽取被清理的数据，并把姓名和地址信息转换成单个标准元素、有效的街道名、城市和邮政编码。它们具体表现为用一个大的预定义的规则库，来处理在清理过程中发现的问题。比如，Trillinm Software 的抽取和匹配模型包含二十多万个商业规则。这些工具也提供了针对特定应用，使用户自定义规则来定制或扩展规则库的工具。2) 与特定应用领域无关的数据清理与特定应用领域无关的数据清理研究主要集中在清理重复的记录上，其主要工具包括：Data Blade Module，ChoiceMaker，Integrity，Mer

19、ge/Purge Library（Sagent/QM Software），Match IT（Help IT Systems），Master Merge（Pitney Bowes），Data Cleanser（EDD）等。3) 数据清理框架为了使数据清理具有一定的通用性，近年来，关于数据清理的框架也有了一些研究。文献44提出了一个数据清理框架，该框架清晰地分离逻辑规范层和物理实现层。用户可以在逻辑层设计数据处理流程，确定清理过程需要执行的数据转化步骤；在物理层实现这些数据转化操作，并对它们进行优化。例如，用户为了计算记录之间的相似度，对输入数据集指定执行匹配操作，而在物理层，数据清理系统会根据实

20、际数据的特点，选择一个特定的实现方法。该算法可以进行优化，它无须计算所有记录对的相似度，而同时又不会损害所要求的结果。除了分离逻辑层和物理层以外，文献44还提出了一种描述性语言，该描述性语言可以在逻辑层上指定数据清理过程所需采取的数据转化操作，并指定何时可以弹出例外，要求用户的交互。该描述性语言还可以指定一些数据转化操作的参数，比如记录匹配操作所使用的距离函数等。在44研究的基础上，文献30,45实现了一个可扩展的数据清理工具 AJAX。文献3,46提出了一个关于数据清理的交互式系统框架，该框架把数据转化和差异检测（discrepancy detection）紧密地集成在一起。用户面对表单风格

21、的界面，能够以直观的图形化方式逐步建立起整个数据转化过程。在此过程中，用户可以执行或者撤消转化操作，而且操作的结果马上就可以在屏幕上看到。后台进程以增量方式检测转化后数据中存在的问题，如果检测到，则及时报告给用户。用户利用系统提供的基本数据转化操作，无须书写复杂的程序就能够完成数据清理任务，而且用户能够随时看到每一步转化操作后的结果，没有很长的延迟。因此，该系统框架具有较好的交互性。再来看一下其它一些与数据清理有关的工具。市场上有很多工具都支持数据转换和数据清理工作，特别是针对数据仓库。1) 数据分析工具数据分析工具能处理实例数据、识别数据错误和不一致，从而得到相应的清理转换。数据分析工具可分

22、成数据剖析和数据挖掘工具。Evoke Software公司的MigrationArchitect是少数商用数据剖析工具的一种，它能分析出每一个字段的元数据，比如：数据类型、长度、集的势、离散值和它们的百分比、最小和最大值、缺失值、以及独特性。Migration Architect 对开发数据迁移的目标模式也有所帮助。数据挖掘工具，如 WizSoft 公司的 WizRule和 Information Discovery 公司的Data Mining Suite能推断字段和它们的值之间的关系，并计算出一个置信度来指示符合条件的记录。WizRule 能显示三种规则：数据公式、IF-THEN 规则，以

23、及能指示姓名拼写错误的基于拼写的规则。WizRule 也能自动地把那些偏离发现规则集的数据指定为可疑错误。2) 数据再工程工具数据再工程工具也能处理实例数据、识别数据错误和不一致，从而得到相应的清理转换。比如，Vality 的 Integrity可以利用检测模型和规则执行清理转换。3) ETL 工具ETL 是数据仓库系统中数据处理的关键操作。ETL 操作的实质就是根据数据处理的需要，将源数据对象经过 ETL 处理后加载到目标数据对象中。很多商业工具在很多方面支持数据仓库的 ETL 过程，如 Data Stage（Ardent）、Data TransformationService（Micros

24、oft）、Warehouse Administrator（SAS）、PowerMart（Informatica）等。这些工具在关系数据库系统上建立一个存储器，以统一的方式管理关于数据源、目标模式、映射、脚本程序等所有元数据。通过文件、关系数据系统、以及标准接口，比如 ODBC（Open Database Connectivity，开放式数据库连接），可以从操作型数据源中抽取模式和数据。数据转换用一个容易使用的图形界面来定义。为了指定单个的映射步骤，需要提供一个单独的规则语言和一个全面的预定义转换规则的库。虽然这些 ETL 工具能够提供大量数据的抽取、转换和集成操作，但往往只能提供有限的数据清理

25、支持。也就是说，ETL 工具并不是完全针对数据清理。1.4.2 国内研究动态由于发达国家的信息化程度较高，各种信息系统的使用范围广、时间长，因此对数据清理的需求显得较为迫切，所以关于数据清理的研究大多都集中在国外，而国外关于数据清理的研究主要是针对西文表示的数据，这些数据清理方法不一定完全适用于中文表示的数据。随着国内信息化建设的快速发展，数据质量问题也越来越受到关注，对数据清理的研究也逐步展开，并取得了一定的成果，主要研究情况如下：复旦大学以周傲英教授为首的研究小组较早地认识到数据清理研究的重要价值，并已开始了数据清理的研究工作，目前他们取得的主要成果有：1) 提出了一个可扩展数据清洗框架的

26、定义该清洗框架以术语模型、处理描述文件、共享库等概念和技术实现了模块功能的可定制、系统的开放性和可扩展性。2) 提出了一种基于 N-Gram 的相似重复记录检测方法该方法先计算各记录的N-Gram值，然后以各记录的N-Gram值为排序键进行排序，再通过采用一种高效的应用无关的 Pair-wise 比较算法，通过计算两记录中单词间的编辑距离来判断记录的相似与否，并采用一种改进的优先队列算法来准确地聚类相似重复记录。该方法在一定程度上有效地解决了相似重复记录的检测问题，但当数据量大，错误多，单词间有互相影响时，该方法的初步聚类效果就会受到很大的影响。此外，该方法主要针对西文数据库环境，不适用于中文

27、数据库环境。3) 研究了一种检测多语言数据重复记录的综合方法该方法充分考虑了中文数据库的环境，有效地解决了多语言数据记录的初步聚类和记录比较问题。北京大学对数据清理也做了一些相关研究，他们主要解决了针对于客户关系管理中客户数据集成时重复记录的数据清理问题。东南大学以董逸生教授为首的研究小组也对数据清理做了一些研究，他们主要是针对数据仓库化过程中的数据清理问题进行研究。对于数据清理，作者本人在信息化实践的基础上，根据信息化建设的实际需要，也做了系统的研究，并取得了一些研究成果，相关内容会在后面的章节中做具体的论述。1.4.3 存在的问题目前，从国内外关于数据清理的研究现状来看，主要体现在以下几个

28、方面的不足：1) 数据清理属于一个较新的研究课题，直接针对这方面的研究并不多。此外，数据清理的研究目前主要集中在西文数据库上，中文数据清理与西文数据清理有较大的不同，如很多排序方法并不完全适用于中文数据库，中文数据清理没有引起重视。2) 数据清理的研究主要集中在字符型数据上，识别数值型字段之间的关系异常很不成熟与实用，数据挖掘算法在数据清理中的应用需要加强。3) 尽管检测重复记录受到很大的关注，采取了许多措施，但检测效率与检测精度问题并不令人满意。特别是在数据量比较大时，耗时太多，有待于更好的检测算法。4) 多数数据清理工具都是针对特定的领域，其应用受到一定的限制。在将来，特定领域的数据清理仍

29、将是应用重点，但较通用的清理方案会受到越来越多的关注。5) 国产的数据清理工具还很少，少量的国产数据清理工具主要研究了重复记录的清理问题，目前还很少研究关于不完整数据、错误数据的清理问题，还没有利用孤立点检测的方法来检测数据源中的错误数据。6) 目前，数据清理的研究主要集中在结构化数据上。半结构化的数据，如 XML数据已受到越来越多的重视，特别是由于 XML 自身所具有的特点，如通用性、自描述性，其在数据清理中应受到重视。1.5 数据清理软件平台的意义为了完成数据清理的任务，满足信息化建设的需要，必须研制一个数据清理工具。由于数据清理的复杂性，数据清理涉及多种不同的清理算法以及清理规则，对数据

30、清理工具有以下要求：1) 对数据源进行数据清理时，清理相似重复记录和清理错误数据的方法是不同的，针对不同的数据质量问题，应采用相应的清理方法有针对性的进行清理。因此，必须提供多种清理功能才能很好地完成数据源的清理工作。2) 数据清理工具不但要能清理重复数据，不完整数据、错误数据也要能清理，这样才能全面提高信息系统的数据质量。3) 对于错误数据的清理，由于每种方法的适用范围不同，故要尽可能的采用多种方法。所以，数据清理工具应能够提供多种错误数据清理方法，并能够扩充。4) 对不同的数据源，清理相似重复记录时，相似度阈值 和字段权重w的取值会对清理效果有较大的影响，所以要能根据具体的数据源灵活地选取

31、 和w的值。5) 对不同的数据源，要求有不同的数据清理规则，能灵活地定义和修改数据清理规则很重要；6) 在相似重复记录检测中，如果数据源数据量较小，就没有必要对记录进行排序，可以对所有记录进行比较，这就要求数据清理工具对数据源中数据量的大小要有较好的适应性。由前文分析可知，目前国内外已根据某种算法开发出一些各具特点的应用系统，或者开发出一些针对特定应用领域的清理软件。但是，由于数据清理的复杂性，对不同的数据源，要求数据清理适应不同的数据类型、数据量以及具体业务，一种数据清理算法无论它采用多有效的措施，不可能在所有问题上表现出好的清理效果，不可能依靠一种或少数几种算法普遍良好地解决各种数据清理问

32、题。有必要提供一种包含一系列数据清理算法以及辅助算法（用于数据预处理和可视化）并能利用具体业务知识、可不断扩展的软件，为不同背景下的数据清理提供算法方面的支持。为了有别于其它数据清理工具，作者称之为数据清理软件平台。实现一个包含丰富算法的数据清理软件平台有助于利用问题的先验知识在不同算法间取长补短，从而提高数据清理算法在不同应用中的清理效果。此外，虽然国外已经提出一些具有通用性的数据清理框架，并研制了相应的清理工具，但这些工具主要是针对西文数据库，而我们的数据库中数据往往以中文为主，这些工具对中文数据库并不能完全适用。故此，本文提出一种可扩展的数据清理软件平台，该软件平台具有开放的规则库和算法

33、库，并提供大量的数据清理以及其它辅助算法。当对数据源进行清理时，根据具体的业务分析，通过预定义清理规则和选择合适的算法，来清理数据源中的种种错误，具有较强的通用性和适应性，并大大提高了数据清理的综合效果。1.6 论文研究目的与内容安排第二章 单数据源中相似重复记录的清理2.1 引 言由于数据输入错误、不标准的缩写词，或其它原因，数据库中可能包含关于现实世界同一实体的重复记录。虽然关系数据库系统不允许含有重复主键值的记录输入，但是，由于数据输入错误，不管主键的值是否被这些错误影响，关系数据库不能再保证不存在重复的记录。因此，在数据清理中，相似重复记录的检测与清除是一个重要问题。什么是相似重复记录

34、呢？首先列举两个典型的重复记录实例，如表 2.1 和表2.2 所示。表 2.1 为某 ERP 系统中关于供应商信息的四条记录。表中编号为 G02001 和G02003 的两条记录看起来不一样，但实际上两条记录除了“地址”略有不同之外，指的是同一个供应商。因此，这两条记录可称为相似重复记录。而表中编号为 G02002和 G02004 的两条记录除了“供应商编号”不同外，其它字段完全相同。因此，这两条记录可称为完全重复记录。表 2.2 为某高校学生管理信息系统中关于学生信息的三条记录，该系统中的数据用的是英文表示。在表 2.2 中，学号为 B01051 和 B01053 的这两条记录看起来不一样，

35、但这两条记录除了姓名的格式不同、所在学院数据中包含了最常见的拼写错误：插入（Corllege）、删除（Mecanical）、交换（Electircal）、替换（Engeneering）之外，但实际上指的是同一个学生。根据以上分析，数据源中的重复记录可分成完全重复记录和相似重复记录，分别定义如下：定义 2.1 完全重复记录完全重复记录是指在数据表中除了主键外，其它各字段完全相同的记录，或者是在那些设计差的数据库中，没有主键，所有字段完全相同的记录。定义 2.1 相似重复记录相似重复记录是指那些客观上表示现实世界同一实体的，但是由于在格式、拼写上有些差异而导致数据库系统不能正确识别的记录。一般情况

36、下，对几个记录可能指同一现实世界实体的这种情况较感兴趣，而不是在语句构成上相同的记录。为了减少数据源中的冗余信息，重复记录的清理是一项重要的任务。因此，本章主要研究如何清除数据源中的相似重复记录，具体内容组织如下：第 2 节分析了相似重复记录清理的相关研究；第 3 节给出了一种有效的相似重复记录清理方法；在此方法的基础上，第 4 节研究了一种提高相似重复记录检测精度的方法；为了提高该方法中相似重复记录的检测效率，第 5 节提出了一种提高相似重复记录检测效率的方法；第 6 节介绍了作者研制的记录生成器，该生成器为第 7 节的实验提供了条件；第 7 节通过实验验证了改进算法的效果；第 8 节总结了

37、本章的工作。需要指出的是，本章的研究主要针对中文数据库。2.2 相似重复记录清理的相关研究要想清理数据源中的相似重复记录，必须要先通过某种方法检测出相似重复记录，然后采取一定的策略清除这些重复记录，从而达到清理的目的。在相似重复记录的检测方面已经有了一些成果。在一个数据表中，完全重复记录的标准检测方法是先将数据库中的记录排序，然后，通过比较邻近记录是否相等来检测完全重复记录。完全重复记录不管以记录的哪一个部分进行分类，在分类排序后，都能保证互相相邻。这种方法可被扩展后用来检测相似重复记录，研究人员在此基础上提出了很多方法，比如，文献62将整条记录作为一个字符串进行排序，通过计算整个字符串的编辑

38、距离来检测记录是否相似；文献31中提出的 Sorted-Neiberhood 方法以用户定义的健作为排序键进行排序，然后，通过一组规则定义的相等理论判定记录是否相似，其基本思想可描述如下：按照用户定义的排序键对整个数据表进行排序，将可能匹配的记录排列在一起。当然，按照某个排序键排一次序往往是不够的，需要按照不同的排序键对数据多次排序，再将结果结合起来。具体说来，Sorted-Neiberhood 算法分为三步：一、 创建排序键抽取记录中重要的字段或字段的一部分组成每条记录的排序键，排序键的选择对于检测结果的准确性至关重要。二、 记录排序用第一步生成的排序键对记录排序。三、 合并定义一个固定大小

39、的窗口，在记录列表上移动，比较窗口内的记录是否相似，如图 2.1 所示。如果窗口的大小为 L（ 2 LN），那么每条最新进入窗口的记录与前面的 L-1 条记录逐一比较以找到匹配记录。窗口中第一条记录滑出窗口。至于说如何叫相似，由用户定义的规则指定，例如：假设 R1、R2 为两条记录IF R1 中的字段 Last name 等于 R2 中的字段 Last name ANDR1 中的字段 First name 等于 R2 中的字段 First name AND两记录的 Address 字段差别很小THENR1 和 R2 相似END IF其中，“字段的差别”是通过将距离函数的计算结果与阈值比较确定的

40、。距离函数一般包括：字符串编辑距离，语音距离和打字机距离，用户也可以自己定义距离函数。Sorted-Neiberhood 算法的时间复杂度与定义的窗口大小有关，窗口大小为 2时，复杂度为 O ( NlogN)，窗口大小为 N 时，复杂度为O (N2)。在目前常用的相似重复记录清理方法中，Sorted-Neiberhood 算法是较为流行的匹配与合并算法，并且该算法已被应用到几个关于数据清理的软件之中。文献55先计算各记录的 N-Gram 值，然后以各记录的 N-Gram 值为排序键进行排序，再通过采用一种高效的应用无关的 Pair-wise 比较算法，通过计算两记录中单词间的编辑距离来判断记录

41、的相似与否，并采用一种改进的优先队列算法来准确地聚类相似重复记录,该算法使用固定大小的优先队列顺序扫描已排序的记录,通过比较当前记录和队列中记录的距离来聚类相似重复记录；文献56在文献55的基础上提出了一种检测多语言数据重复记录的综合方法。上述这些方法的基本思想可以总结为：先对数据表中的记录排序，然后用某种方式检测相邻记录是否为重复记录，不同之处是所采用的排序方法和相似检测方法不同。本章在对这些方法研究的基础上，吸收这些方法的思想，来解决相似重复记录的清理问题，并对算法的关键环节进行改进，提高了相似重复记录的检测效率和检测精度。为了后文论述的方便，首先给出相似重复记录清理中的几个相关定义：定义

42、 2.3 记录之间的相似度 S记录之间的相似度S 是根据两条记录的内容而计算出的一个表示两记录相似程度的数值， 0 < S <1。S 越小，则两记录相似程度越高；若 S =0，则表示两条记录为完全重复记录。定义 2.4 记录相似检测记录相似检测是指通过计算两条记录之间的相似度S ，来判定两记录是不是重复记录。2.3 相似重复记录的清理方法2.3.1 相似重复记录清理方法总体描述根据以上分析，本文采用的相似重复记录清理方法的原理可以总结为如图 2.2所示。由图 2.2 可以看出，相似重复记录的清理过程可总结为：记录排序记录相似检测相似重复记录合并/清除。其清理过程可描述如下：首先，把

43、数据源中需要清理的数据通过 JDBC（Java DataBase Connectivity,Java 数据库连接）接口调入到系统中来；然后，执行数据清理，记录排序模块从算法库中调用排序算法，执行记录之间的排序；在记录已排序的基础上，记录相似检测模块从算法库中调用相似检测算法，作邻近范围内记录间的相似检测，从而计算出记录间的相似度，并根据预定义的重复识别规则，来判定是否为相似重复记录。为了能检测到更多的重复记录，一次排序不够，要采用多轮排序，多轮比较，每次排序采用不同的键，然后把检测到的所有重复记录聚类到一起，从而完成重复记录的检测；最后，对所检测出的每一组相似重复记录根据预定义的合并/清除规则

44、，完成相似重复记录的合并处理。由图 2.2 可以看出，记录排序和记录相似检测是相似重复记录清理过程中的两个重要步骤，下面分别讨论这两个步骤中的关键技术。2.3.2 记录排序为了能查找到数据源中所有的重复记录，必须比较每一个可能的记录对，如此以来，检测相似重复记录是一个很昂贵的操作，当数据源中数据量很大时，这会导致是一个无效和不可行的方案。为了减少记录之间的比较次数，提高检测效率，常用的方法是仅比较相互距离在一定范围的记录，即先对数据表中的记录排序，然后对邻近记录进行比较。比如，在文献31中，作者在整个分类后的数据表中通过移动一个固定大小的窗口，比较附近的记录。一个大小为 W 的窗口，在数据库中

45、一次移动一个记录，新记录和这个窗口中的其它 W-1 个记录相比较。这样，记录比较的次数从 O（T2 ）减少到 O（TW ），其中，T 为数据库中记录的总数。因此，当数据源中数据量很大时，应该采用记录排序方法。对于记录排序方法，文献33使用某种应用相关的键来将相似记录聚类到邻近位置。文献63根据用户定义的键值来重排表记录，并采用滑动窗口来 Pair-wise比较窗口内的记录。文献55是先计算记录的 N-Gram 值，然后按该值进行排序；文献56针对多语言文本的情况，采用序值表的方法来进行排序。由于本文的研究主要是针对中国信息化的现状，所以作者主要考虑采用中文表达的记录。根据对各种排序方法的分析，

46、作者采用序值表的方法来对记录进行排序，该方法说明如下：对于西文字符，排序就是按西文字符的字典序排列，但对于汉字来说，存在多种排序方式。在国标 GB2312-80 中共收集汉字 6763 个，分成两级，一级汉字字库包括汉字 3755 个，按拼音字母排序，二级汉字字库包括汉字 3008 个，按部首排序。由此可见汉字本身的编码不满足任何一种统一的序值规则，不适合作序值使用。为了解决序值不统一的问题，采取建立序值文件的方式。目前，汉字通常有以下三种排序方式：拼音序、笔划序、部首序。对于汉字各种不同的排序方式，分别建立对应于 GB2312-80 汉字基本集的序值表。序值表中序值的存放按对应的汉字在汉字基

47、本集中出现的顺序进行。因此，根据汉字的内码（0XB0A1-0XF7FE）可以直接计算出序值表中存放对应序值的入口地址，计算公式如下：其中，c1 为汉字内码的第一个字节（区码）；c2 为汉字内码的第二个字节（位码）；N 为序值编码的长度，N=2（用两个字节来存放序值）；headoffset 是序值表中存放第一个汉字（“啊”字的编码 OXBOA1）的位置。序值表相当于自定义的一种编码，不同的排序方式对应各自的序值表。序值表的大小只有几十 K，可以存放在内存中。根据上述公式，汉字的内码可直接映射为获取序值的地址索引，非常便于使用。对于要排序的字段，根据以上方法把该字段中所有的字符转换成相应的序值，然

48、后，采快速排序算法可以对记录进行排序。在此排序的基础上，再采用相似重复记录检测算法对相邻记录进行检测，从而提高了检测效率。按以上方法重排记录后，相似记录被放在较接近的位置，从而可以在相对集中的范围内作记录的相似检测。但是由于排序时对错误的位置非常敏感，不能保证排序后的重复记录都在一起。因此这种方法也有一定的局限性。此外，对整个数据库记录进行重排的开销也很大。因此，从实用的角度考虑，在实际应用中，对于小批量数据，如记录总数小于 5 万时，没有必要采用复杂的记录排序算法，可以直接进行记录的比较，从而提高相似重复记录的查全率。2.3.3 记录相似检测由图2.2可以看出，记录相似检测是相似重复记录清理

49、过程中的一个重要步骤，通过记录相似检测，可以判断两条记录是不是相似重复记录。对于记录相似检测，一般采用 Pair-wise 比较算法，它是一种比较成熟的方法。本文吸收Pair-wise 比较算法的思想，所采用的记录相似检测算法的伪码描述如下：算法略过2.3.4 相似重复记录检测算法2.3.5 相似重复记录的合并/清除当完成相似重复记录的检测之后，对检测出的重复记录要进行处理。对于一组相似重复记录，一般有两种处理方法：1. 第一种处理方法第一种处理方法是把一组相似重复记录中的一个记录看成是正确的，其它记录看成是含有错误信息的重复记录。于是，任务就是删除数据库中的重复记录。在这种情况下，一些常用的

50、处理规则是：1) 人工规则人工规则是指由人工从一组相似重复记录中选出一条最准确的记录保留，并把其它重复记录从数据库中删除掉，这种方法最简单。2) 随机规则随机规则是指从一组相似重复记录中随机地选出一条记录保留，并把其它重复记录从数据库中删除掉。3) 最新规则在很多情况下，最新的记录能更好地代表一组相似重复记录。比如，越接近当前日期的信息准确性可能越高，经常使用账户上的地址要比退休账户上的地址权威一些。基于这种分析，最新规则是指选择每一组相似重复记录中最新的一条记录保留，并把其它重复记录从数据库中删除掉。4) 完整规则完整规则是指从一组相似重复记录中选择最完整的一条记录保留，并把其它重复记录从数

51、据库中删除掉。5) 实用规则因为重复率越高的信息可能越准确一些，比如，如果三条记录中两个供应商的电话号码是相同的，那么重复的电话号码可能是正确的。基于这种分析，实用规则是指从一组相似重复记录中选择与其它记录匹配次数最多的一条记录保留，并把其它重复记录从数据库中删除掉。可以把以上方法定义成规则，存放在规则库中，供用户根据具体的业务要求选择使用。2. 第二种处理方法第二种处理方法是把每一条相似重复记录看成是信息源的一部分。于是，目的就是合并一组重复记录，产生一个具有更完整信息的新记录。该方法一般要由人工进行处理。以上给出了常用的几种处理相似重复记录的方法，至于在执行相似重复记录的清理过程中采用什么

52、样的处理方法，要根据具体的数据源以及用户要求来确定。2.4 相似重复记录检测精度提高方法2.4.1 等级法的使用在 2.3.3 节中研究了如何比较记录的相似性，其过程为：先比较两条记录中每个字段的相似度；然后对每个字段赋予不同的权重，计算出两条记录的相似度，从而判定两条记录是不是相似重复记录。由此可见各个字段所赋予的权重对检测精度影响很大，合适的赋值能提高记录相似检测的精度。文献55在进行记录比较时，没有考虑各记录中各字段的权重；文献56虽然考虑到了字段权重的重要性，但没有给出一个合适的权重选取方法。本节在对相关方法研究的基础上，采用一种计算字段权重的有效方法等级法来计算各字段的权重。当进行相

53、似重复记录检测时，根据对具体业务的分析，采用该方法来计算相应字段的权重，然后，对不同的字段使用不同的权重，从而提高相似重复记录检测的精度。等级法是一种计算记录字段权重的方法，它是让用户根据数据表中各个字段的重要程度来划分等级，即最重要字段的等级指定为 1，第二重要的字段等级指定为2，等等。然后，根据记录各字段的等级，计算其相应的权重。文献72，73都表明采用等级法不但效果好，而且容易使用。表 2.4 和表 2.5 为使用等级法时所用的两种表，其中，表 2.4 是交给每个操作用户的表，操作用户根据自己的认识，在这张表上给各字段划分等级；表 2.5 是分析员用来综合所有操作用户意见的等级表。在表

54、2.4 和 2.5 中， Yk 表示数据表中记录的K 个字段，Suk 是操作用户 u 为字段Yk 所指定的等级，Sk表示各个字段最终统一的等级， k1 ,2.K ， u1 ,2.N 。表 2.4 中的“字段说明”用来补充说明字段的作用及意义，便于操作用户准确地为各字段指定等级。表 2.5 中汇集了不同操作用户给各个字段指定的等级值，根据每个操作用户所给的等级值，可以计算出各个字段最终统一的等级。2.4.2 等级转变成权重的方法2.4.3 利用权重提高检测精度在运行相似重复记录检测的过程中，首先采用等级法来获取记录中不同字段的等级，并采用 RC 方法生成各字段相应的权重。然后，在记录相似检测过程

55、中对不同字段指定不同的权重，这样可提高相似重复记录的检测精度，从而更好地识别重复记录。采用等级法生成的权重存放在规则库中，供运行数据清理时调用。在第七章的实例中，作者会采用这种方法来检测相似重复记录，通过实例来验证这种方法的有效性。2.5 相似重复记录检测效率提高方法2.5.1 提高检测效率的方法分析快速完成数据清理是很重要的，因此，必须提高相似重复记录的检测效率。从前面的分析可以看出：在相似重复记录检测过程中，记录间的相似检测是一个重要问题，其关键步骤是记录中各字段的相似检测，其效率直接影响整个算法的效率，记录中大多字段采用编辑距离算法来检测，由于编辑距离算法的复杂度为 O ( m×

56、; n)，当数据量很大时，如不采用一种高效的过滤方法来减少不必要的编辑距离计算，则会导致相似检测时间过长。因此，为了提高相似重复记录的检测效率，本文提出了一种优化相似重复记录检测效率的方法，该方法采用长度过滤方法减少不必要的编辑距离计算。实验证明：长度过滤方法能有效地减少不必要的编辑距离计算，降低相似检测时间，从而提高了相似重复记录的检测效率。由于作者提出的这种优化方法用于记录相似检测模块中，所以，不管记录相似检测过程中是否进行记录排序，这种优化方法都适用。2.5.2 长度过滤方法2.6 实验准备记录生成器的研制2.6.1 记录生成器的作用2.6.2 记录生成器的原理及实现2.7 改进算法检测

57、效果的实验验证2.7.1 度量相似重复记录检测效果的标准2.7.2 长度过滤方法有效性的实验检测2.7.3 实验结果分析2.8 本章小结如何消除数据源中的重复信息是数据清理研究中的一个热门课题。本章在研究了相似重复记录清理相关技术的基础上，给出了一种相似重复记录清理的综合方法，并对该方法进行了改进，从而提高了该方法的检测精度和检测效率。本文中的方法和文献39，55，56中所描述的相似重复记录检测方法相比，从两种重要的途径上进行了改进：第一个改进是为了提高相似重复记录的检测精度，采用等级法为记录字段指定合适的权重，从而提高了相似重复记录的检测精度；第二个改进是提出了一种提高相似重复记录检测效率的

58、方法，该方法采用长度过滤方法优化相似重复记录检测中的相似检测算法，避免了不必要的编辑距离计算，从而提高了相似重复记录的检测效率。这两种改进可以用于任何相似重复记录检测算法之中。此外，作者还构造了合适的实验环境，作了大量的检测实验，翔实的实验结果验证了改进方法的科学性及效果。第三章 单数据源中不完整数据的清理3.1 引 言数据不完整是产生数据质量问题的一个重要因素，简单地说，数据不完整是指数据源中字段值的缺失问题。表 3.1 是 ERP 系统中“检验单”数据表中的一些数据，表中给出了一些不完整数据的例子。在这个表中，由于种种原因，记录中的一些字段值缺失，如第一条记录中字段“送检日期”的值为空，第二条记录中字段“状态”的值为空，第三条记录中字段“送检部门编号”的值为空。这种现象在数据源中会常常出现，然而并未引