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

数据清理关键技术及其软件平台的研究与应用第一章绪论1.1引言我国目前正在大力推广信息技术，实施各行各业的信息化工程。随着信息化建设的不断深入，企事业单位积累了大量的电子数据，这些数据非常重要。为了使信息系统中的数据更准确、一致，能支持正确决策，就要求所管理的数据准确、可靠。因此，企业数据质量的管理正在获得越来越多的关注。但是，由于各种原因，如数据录入错误、不同来源数据引起的不同表示方法、数据间的不一致等，导致企业现有系统数据库中存在这样或那样的脏数据，主要表现为：不正确的字段值、重复的记录、拼写问题、不合法值、空值、不一致值、缩写词的不同，不遵循引用完整性等。根据“进去的是垃圾，出来的也是垃圾（garbagein，garbageout）”这条原理，若不进行清理，这些脏数据会扭曲从数据中获得的信息，影响信息系统的运行效果，也为企业构建数据仓库、建立决策支持系统、应用商务智能带来隐患。显见，数据清理问题的重要性是不言而喻的。另外，从市场上众多的相关产品，也可以明白这一点。然而，由于数据清理本身的一些特点，比如：数据清理是具体应用问题，经常要具体问题具体分析，难于归纳出通用方法；数据清理问题的数学建模困难。因此，目前在学术界，数据清理并没有得到足够的关注，针对这方面的研究也少，有些人甚至认为数据清理是一个需要大量劳动力的过程，而且往往过于依赖特定应用领域。其实不然，对于数据清理有很多内容值得研究，比如：在数据清理的研究中，尽管检测相似重复记录受到最多的关注，采取了许多措施，但检测效率与检测精度并不令人满意。特别是在数据量非常大时，耗时太多，有待于更好的方法。作者在文献中做了一些这方面工作，在相似重复记录检测中采用长度过滤方法优化相似检测算法，避免了不必要的编辑距离计算，从而提高了相似重复记录的检测效率；在数据清理的相关研究中，数据清理整体框架的研究正逐渐成为研究的热点。对此，作者在文献[7]中提出一个可扩展的数据清理软件平台，该软件平台具有开放的规则库和算法库，通过在规则库中定义清理规则以及从算法库中选择合适的清理算法，可使该软件平台适用于不同的数据源，从而使其具有较强的通用性和适应性；目前，对数据清理的研究主要集中在结构化数据上。由于半结构化数据XML（ExtensibleMarkupLanguage，可扩展标识语言）的快速增长以及广泛应用，其在数据清理中越来越重要。为了使XML数据源中的数据更准确、一致，如何清理这些XML相似重复数据，都是值得研究的，作者在文献[8]中做了一些这方面工作；另外，关于数据清理在一些业务领域中的应用也是值得研究，作者在文献[9]、[10]中做了一些这方面的工作。当然，对任何现实世界中的数据源，人工完成数据清理是没有问题的。一些单位每年要花费上百万元来查找数据错误，手工清理是劳累的、费时的和易出错的。对于少量数据的数据源来说，采用人工清理就可以了，但对于规模较大的数据源，手工清理是不可行的，必须借助信息技术，采用自动清理方法。当然，在自动清理的过程中，仍需要人来参与，我们要做的就是尽可能减少人的参与。总之，在信息化建设过程中，数据清理是一个非常重要，而且较新的课题，有很多东西值得我们去研究。作为全文的引言，本章主要介绍数据质量的相关概念、数据清理的原理、数据清理软件平台的意义以及本文的内容安排。1.2数据质量1.2.1数据质量概念及分类目前，数据质量问题已引起广泛的关注。什么是数据质量呢？数据质量问题并不仅仅是指数据错误。文献[22]把数据质量定义为数据的一致性（consistency）、正确性（correctness）、完整性（completeness）和最小性（minimality）这4个指标在信息系统中得到满足的程度，文献[23]则把“适合使用”作为衡量数据质量的初步标准。一般说来，评价数据质量最主要的几个指标是：准确性（Accuracy）准确性是指数据源中实际数据值与假定正确数据值的一致程度；完整性（Completeness）完整性是指数据源中需要数值的字段中无值缺失的程度；一致性（Consistency）一致性是指数据源中数据对一组约束的满足程度；唯一性（Uniqueness）唯一性是指数据源中记录以及编码是否唯一；适时性（Timeliness）适时性是指在所要求的或指定的时间提供一个或多个数据项的程度；有效性（Validity）有效性是指维护的数据足够严格以满足分类准则的接受要求。当建立一个信息系统的时候，即使进行了良好的设计和规划，也不能保证在所有情况下，信息系统中数据的质量都能满足用户的要求。用户录入错误、企业合并以及企业环境随着时间的推移而改变，这些都会影响所存放数据的质量。信息系统中可能存在的数据质量问题有很多种，总结起来主要有以下几种：重复的记录重复的记录是指在一个数据源中有指现实世界同一个实体的重复信息，或在多个数据源中有指现实世界同一个实体的重复信息。不完整的数据由于录入错误等原因，字段值或记录未被记入数据库，造成信息系统数据源中应该有的字段或记录缺失。不正确的数据由于录入错误，数据源中的数据未及时更新，或不正确的计算等，导致数据源中数据过时，或者一些数据与现实实体中字段的值不相符。无法理解的数据值无法理解的数据值是指由于某些原因，导致数据源中的一些数据难以解释或无法解释，如伪值、多用途域、古怪的格式、密码数据等。不一致的数据数据不一致包括了多种问题，比如，由不同数据源来的数据很容易发生不一致；同一数据源的数据也会因位置、单位以及时间不同产生不一致。在以上这些问题中，前三种问题在数据源中出现的最多。根据数据质量问题产生的原因，数据质量问题可分成单数据源问题和多数据源问题两个方面，其分类如图1.1所示。1.2.2单数据源数据质量问题单数据源数据质量问题可以分成模式级和实例级两类问题进行分析，如图1.1所示。一个数据源的数据质量很大程度上决定于控制这些数据的模式和完整性约束的等级。没有模式的数据源，如文件，它对数据的输入和保存没有约束，于是出现错误和不一致的可能性就很大。因此，出现模式相关的数据质量问题是因为缺少合适的特定数据模型和特定的完整性约束，如差的模式设计，或者因为仅定义了很少一些约束来进行完整性控制。特定实例问题相关错误和不一致，如拼写错误，不能在模式级预防。另外，不唯一的模式级特定约束不能防止重复的实例，如关于同一现实实体的记录可能会以不同的字段值输入两次。无论是模式级问题还是实例级问题，可以分成字段、记录、记录类型和数据源四种不同的问题范围，分别说明如下：字段：这类错误仅仅局限于单个字段的值。记录：这类错误表现在同一条记录中不同字段值之间出现的不一致。记录类型：这类错误表现在同一个数据源中不同记录之间的不一致关系。数据源：这类错误表现在数据源中的某些字段值和其它数据源中相关值的不一致关系。四种不同情况的例子如表1.1和表1.2所示。表1.1单数据源中模式级的数据质量问题表1.2单数据源中实例级的数据质量问题1.2.3多数据源集成时数据质量问题当多个数据源集成时，发生在单数据源中的这些问题会更加严重。这是因为每个数据源都是为了特定应用，单独开发、部署和维护的，这就很大程度上导致数据管理系统、数据模型、模式设计和实际数据的不同。每个数据源都可能含有脏数据，多数据源中的数据可能会出现不同表示、重复、冲突等现象。在模式级，模式设计的主要问题是命名冲突和结构冲突。命名冲突主要表现为不同的对象可能使用同一个命名，而同一对象可能使用不同的命名；结构冲突存在很多种不同的情况，一般是指在不同数据源中同一对象有不同表示，如不同的组成结构、不同的数据类型、不同的完整性约束等。除了模式级的冲突，很多冲突仅出现在实例级上，即数据冲突。由于不同数据源中数据的表示可能会不同，单数据源中的所有问题都可能会出现，比如重复的记录、冲突的记录等。此外，在整个数据源中，尽管有时不同的数据源中有相同的字段名和类型，仍可能存在不同的数值表示，如对性别的描述，一个数据源中可能用“0/1”来描述，另一个数据源中可能会用“F/M”来描述，或者对一些数值的不同表示，如一个数据源中度量单位制可能用美元，另一个数据源中可能会用欧元。此外，不同数据源中的信息可能表示在不同的聚集级别上，如一个数据源中信息可能指的是每种产品的销售量，而另一个数据源中信息可能指的是每组产品的销售量。多数据源集成中的数据清理问题也是信息化建设中面临的一个重要问题。对于这个问题，作者会在第五章进行研究。1.3数据清理内涵及原理通过以上对数据质量问题的分析，可以看出：数据质量问题是信息化建设中的一个重要问题，为了提高信息系统的数据质量，研究数据清理非常重要。数据清理（datacleaning）也称数据清洗。数据清理的三个主要领域包括：数据仓库（DataWarehouse，DW）、数据库中的知识发现（KnowledgeDiscoveryinDatabases，KDD）和综合数据质量管理（TotalDataQualityManagement，TDQM）。数据清理在不同的应用领域其要求不完全相同，如在数据仓库环境下，数据清理是ETL（Extraction抽取、Transition转换、Load加载，ETL）过程的一个重要部分，要考虑数据仓库的集成性与面向主题的需要，包括数据的清理及结构转换；在KDD中，数据清理主要是提高数据的可利用性，如去除噪声、无关数据、空值，考虑时间顺序和数据的变化等，但主要内容还是一样的。目前，对于数据清理没有统一的定义。文献[30]认为数据清理是一个消除数据中的错误和不一致，解决对象识别问题的过程，文献[31]则把数据清理定义为重复记录的合并/清理问题。一般来说，从广义上讲，数据清理是将数据库精简以除去重复记录，并使剩余部分转换成标准可接收格式的过程；而狭义上的数据清理是特指在构建数据仓库和实现数据挖掘前对数据源进行处理，使数据实现准确性、完整性、一致性、唯一性、适时性、有效性以适应后续操作的过程。本文的研究是以信息化建设为背景，研究的重点是提高信息系统的数据质量，故作者本人认为：凡是有助于提高信息系统数据质量的处理过程，都可认为是数据清理。所以，数据清理可简单看成就是从数据源中清除错误数值和重复记录，即利用有关技术如数理统计、数据挖掘或预定义的清理规则等，从数据源中检测和消除错误数据、不完整数据和重复数据，从而提高信息系统的数据质量。一般说来，数据清理包括以下几个步骤：数据分析数据分析是指从数据中发现控制数据的一般规则，比如字段域、业务规则等。通过对数据的分析，可定义出数据清理的规则，并选择合适的清理算法。数据检测数据检测是指根据预定义的清理规则及相关数据清理算法，检测数据是否正确，比如是否满足字段域、业务规则等，或检测记录是否是重复记录。数据修正数据修正是指手工或自动地修正检测到的错误数据或处理重复的记录。对于数据清理应该满足：数据清理应该能检测和消除所有主要的错误和不一致，包括单数据源和多数据源集成时；数据清理方法能被这样的工具支持，人工检测和编程工作要尽可能少，并具有可扩展性。根据以上分析，数据清理的原理可总结为如图1.2所示1.4数据清理研究现状分析1.4.1国外研究动态数据清理的相关研究最早可追溯到1959年。自那时起，合并来自不同数据源的数据是一直被认为是一个重要而且很困难的问题，这些问题被作为记录连接、实例识别、对象识别等问题来研究。它们曾经是医疗、商业、税务领域中的研究重点之一，在流行病的研究、欺骗检测等方面都起到重要作用。这些问题的研究可以看成是数据清理的源头。近年来，随着信息化的进展，国外开始系统地研究数据清理问题。目前，在数据清理算法、方法和商用系统上都取得了一些成果。主要成果可分类如下：特殊域清理特殊域清理工具主要解决某类特定应用域的数据清理问题，大多数是姓名和地址数据。比如：根据概率统计学原理查找数值异常的记录；对姓名、地址、邮政编码等进行清理等，这是目前研究得较多的领域，也是应用最成功的一类。如商用系统：TrillinmSoftware、PureIntegrate（Oracle）、QuickAddress（QASSystems）等。它们用一个匹配工具抽取被清理的数据，并把姓名和地址信息转换成单个标准元素、有效的街道名、城市和邮政编码。它们具体表现为用一个大的预定义的规则库，来处理在清理过程中发现的问题。比如，TrillinmSoftware的抽取和匹配模型包含二十多万个商业规则。这些工具也提供了针对特定应用，使用户自定义规则来定制或扩展规则库的工具。与特定应用领域无关的数据清理与特定应用领域无关的数据清理研究主要集中在清理重复的记录上，其主要工具包括：DataBladeModule，ChoiceMaker，Integrity，Merge/PurgeLibrary（Sagent/QMSoftware），MatchIT（HelpITSystems），MasterMerge（PitneyBowes），DataCleanser（EDD）等。数据清理框架为了使数据清理具有一定的通用性，近年来，关于数据清理的框架也有了一些研究。文献[44]提出了一个数据清理框架，该框架清晰地分离逻辑规范层和物理实现层。用户可以在逻辑层设计数据处理流程，确定清理过程需要执行的数据转化步骤；在物理层实现这些数据转化操作，并对它们进行优化。例如，用户为了计算记录之间的相似度，对输入数据集指定执行匹配操作，而在物理层，数据清理系统会根据实际数据的特点，选择一个特定的实现方法。该算法可以进行优化，它无须计算所有记录对的相似度，而同时又不会损害所要求的结果。除了分离逻辑层和物理层以外，文献[44]还提出了一种描述性语言，该描述性语言可以在逻辑层上指定数据清理过程所需采取的数据转化操作，并指定何时可以弹出例外，要求用户的交互。该描述性语言还可以指定一些数据转化操作的参数，比如记录匹配操作所使用的距离函数等。在[44]研究的基础上，文献[30,45]实现了一个可扩展的数据清理工具AJAX。文献[3,46]提出了一个关于数据清理的交互式系统框架，该框架把数据转化和差异检测（discrepancydetection）紧密地集成在一起。用户面对表单风格的界面，能够以直观的图形化方式逐步建立起整个数据转化过程。在此过程中，用户可以执行或者撤消转化操作，而且操作的结果马上就可以在屏幕上看到。后台进程以增量方式检测转化后数据中存在的问题，如果检测到，则及时报告给用户。用户利用系统提供的基本数据转化操作，无须书写复杂的程序就能够完成数据清理任务，而且用户能够随时看到每一步转化操作后的结果，没有很长的延迟。因此，该系统框架具有较好的交互性。再来看一下其它一些与数据清理有关的工具。市场上有很多工具都支持数据转换和数据清理工作，特别是针对数据仓库。数据分析工具数据分析工具能处理实例数据、识别数据错误和不一致，从而得到相应的清理转换。数据分析工具可分成数据剖析和数据挖掘工具。EvokeSoftware公司的MigrationArchitect是少数商用数据剖析工具的一种，它能分析出每一个字段的元数据，比如：数据类型、长度、集的势、离散值和它们的百分比、最小和最大值、缺失值、以及独特性。MigrationArchitect对开发数据迁移的目标模式也有所帮助。数据挖掘工具，如WizSoft公司的WizRule和InformationDiscovery公司的DataMiningSuite能推断字段和它们的值之间的关系，并计算出一个置信度来指示符合条件的记录。WizRule能显示三种规则：数据公式、IF-THEN规则，以及能指示姓名拼写错误的基于拼写的规则。WizRule也能自动地把那些偏离发现规则集的数据指定为可疑错误。数据再工程工具数据再工程工具也能处理实例数据、识别数据错误和不一致，从而得到相应的清理转换。比如，Vality的Integrity可以利用检测模型和规则执行清理转换。ETL工具ETL是数据仓库系统中数据处理的关键操作。ETL操作的实质就是根据数据处理的需要，将源数据对象经过ETL处理后加载到目标数据对象中。很多商业工具在很多方面支持数据仓库的ETL过程，如DataStage（Ardent）、DataTransformationService（Microsoft）、WarehouseAdministrator（SAS）、PowerMart（Informatica）等。这些工具在关系数据库系统上建立一个存储器，以统一的方式管理关于数据源、目标模式、映射、脚本程序等所有元数据。通过文件、关系数据系统、以及标准接口，比如ODBC（OpenDatabaseConnectivity，开放式数据库连接），可以从操作型数据源中抽取模式和数据。数据转换用一个容易使用的图形界面来定义。为了指定单个的映射步骤，需要提供一个单独的规则语言和一个全面的预定义转换规则的库。虽然这些ETL工具能够提供大量数据的抽取、转换和集成操作，但往往只能提供有限的数据清理支持。也就是说，ETL工具并不是完全针对数据清理。1.4.2国内研究动态由于发达国家的信息化程度较高，各种信息系统的使用范围广、时间长，因此对数据清理的需求显得较为迫切，所以关于数据清理的研究大多都集中在国外，而国外关于数据清理的研究主要是针对西文表示的数据，这些数据清理方法不一定完全适用于中文表示的数据。随着国内信息化建设的快速发展，数据质量问题也越来越受到关注，对数据清理的研究也逐步展开，并取得了一定的成果，主要研究情况如下：复旦大学以周傲英教授为首的研究小组较早地认识到数据清理研究的重要价值，并已开始了数据清理的研究工作，目前他们取得的主要成果有：提出了一个可扩展数据清洗框架的定义该清洗框架以术语模型、处理描述文件、共享库等概念和技术实现了模块功能的可定制、系统的开放性和可扩展性。提出了一种基于N-Gram的相似重复记录检测方法该方法先计算各记录的N-Gram值，然后以各记录的N-Gram值为排序键进行排序，再通过采用一种高效的应用无关的Pair-wise比较算法，通过计算两记录中单词间的编辑距离来判断记录的相似与否，并采用一种改进的优先队列算法来准确地聚类相似重复记录。该方法在一定程度上有效地解决了相似重复记录的检测问题，但当数据量大，错误多，单词间有互相影响时，该方法的初步聚类效果就会受到很大的影响。此外，该方法主要针对西文数据库环境，不适用于中文数据库环境。研究了一种检测多语言数据重复记录的综合方法该方法充分考虑了中文数据库的环境，有效地解决了多语言数据记录的初步聚类和记录比较问题。北京大学对数据清理也做了一些相关研究，他们主要解决了针对于客户关系管理中客户数据集成时重复记录的数据清理问题。东南大学以董逸生教授为首的研究小组也对数据清理做了一些研究，他们主要是针对数据仓库化过程中的数据清理问题进行研究。对于数据清理，作者本人在信息化实践的基础上，根据信息化建设的实际需要，也做了系统的研究，并取得了一些研究成果，相关内容会在后面的章节中做具体的论述。1.4.3存在的问题目前，从国内外关于数据清理的研究现状来看，主要体现在以下几个方面的不足：数据清理属于一个较新的研究课题，直接针对这方面的研究并不多。此外，数据清理的研究目前主要集中在西文数据库上，中文数据清理与西文数据清理有较大的不同，如很多排序方法并不完全适用于中文数据库，中文数据清理没有引起重视。数据清理的研究主要集中在字符型数据上，识别数值型字段之间的关系异常很不成熟与实用，数据挖掘算法在数据清理中的应用需要加强。尽管检测重复记录受到很大的关注，采取了许多措施，但检测效率与检测精度问题并不令人满意。特别是在数据量比较大时，耗时太多，有待于更好的检测算法。多数数据清理工具都是针对特定的领域，其应用受到一定的限制。在将来，特定领域的数据清理仍将是应用重点，但较通用的清理方案会受到越来越多的关注。国产的数据清理工具还很少，少量的国产数据清理工具主要研究了重复记录的清理问题，目前还很少研究关于不完整数据、错误数据的清理问题，还没有利用孤立点检测的方法来检测数据源中的错误数据。目前，数据清理的研究主要集中在结构化数据上。半结构化的数据，如XML数据已受到越来越多的重视，特别是由于XML自身所具有的特点，如通用性、自描述性，其在数据清理中应受到重视。1.5数据清理软件平台的意义为了完成数据清理的任务，满足信息化建设的需要，必须研制一个数据清理工具。由于数据清理的复杂性，数据清理涉及多种不同的清理算法以及清理规则，对数据清理工具有以下要求：对数据源进行数据清理时，清理相似重复记录和清理错误数据的方法是不同的，针对不同的数据质量问题，应采用相应的清理方法有针对性的进行清理。因此，必须提供多种清理功能才能很好地完成数据源的清理工作。数据清理工具不但要能清理重复数据，不完整数据、错误数据也要能清理，这样才能全面提高信息系统的数据质量。对于错误数据的清理，由于每种方法的适用范围不同，故要尽可能的采用多种方法。所以，数据清理工具应能够提供多种错误数据清理方法，并能够扩充。对不同的数据源，清理相似重复记录时，相似度阈值δ和字段权重w的取值会对清理效果有较大的影响，所以要能根据具体的数据源灵活地选取δ和w的值。对不同的数据源，要求有不同的数据清理规则，能灵活地定义和修改数据清理规则很重要；在相似重复记录检测中，如果数据源数据量较小，就没有必要对记录进行排序，可以对所有记录进行比较，这就要求数据清理工具对数据源中数据量的大小要有较好的适应性。由前文分析可知，目前国内外已根据某种算法开发出一些各具特点的应用系统，或者开发出一些针对特定应用领域的清理软件。但是，由于数据清理的复杂性，对不同的数据源，要求数据清理适应不同的数据类型、数据量以及具体业务，一种数据清理算法无论它采用多有效的措施，不可能在所有问题上表现出好的清理效果，不可能依靠一种或少数几种算法普遍良好地解决各种数据清理问题。有必要提供一种包含一系列数据清理算法以及辅助算法（用于数据预处理和可视化）并能利用具体业务知识、可不断扩展的软件，为不同背景下的数据清理提供算法方面的支持。为了有别于其它数据清理工具，作者称之为数据清理软件平台。实现一个包含丰富算法的数据清理软件平台有助于利用问题的先验知识在不同算法间取长补短，从而提高数据清理算法在不同应用中的清理效果。此外，虽然国外已经提出一些具有通用性的数据清理框架，并研制了相应的清理工具，但这些工具主要是针对西文数据库，而我们的数据库中数据往往以中文为主，这些工具对中文数据库并不能完全适用。故此，本文提出一种可扩展的数据清理软件平台，该软件平台具有开放的规则库和算法库，并提供大量的数据清理以及其它辅助算法。当对数据源进行清理时，根据具体的业务分析，通过预定义清理规则和选择合适的算法，来清理数据源中的种种错误，具有较强的通用性和适应性，并大大提高了数据清理的综合效果。1.6论文研究目的与内容安排第二章单数据源中相似重复记录的清理2.1引言由于数据输入错误、不标准的缩写词，或其它原因，数据库中可能包含关于现实世界同一实体的重复记录。虽然关系数据库系统不允许含有重复主键值的记录输入，但是，由于数据输入错误，不管主键的值是否被这些错误影响，关系数据库不能再保证不存在重复的记录。因此，在数据清理中，相似重复记录的检测与清除是一个重要问题。什么是相似重复记录呢？首先列举两个典型的重复记录实例，如表2.1和表2.2所示。表2.1为某ERP系统中关于供应商信息的四条记录。表中编号为G02001和G02003的两条记录看起来不一样，但实际上两条记录除了“地址”略有不同之外，指的是同一个供应商。因此，这两条记录可称为相似重复记录。而表中编号为G02002和G02004的两条记录除了“供应商编号”不同外，其它字段完全相同。因此，这两条记录可称为完全重复记录。表2.2为某高校学生管理信息系统中关于学生信息的三条记录，该系统中的数据用的是英文表示。在表2.2中，学号为B01051和B01053的这两条记录看起来不一样，但这两条记录除了姓名的格式不同、所在学院数据中包含了最常见的拼写错误：插入（Corllege）、删除（Mecanical）、交换（Electircal）、替换（Engeneering）之外，但实际上指的是同一个学生。根据以上分析，数据源中的重复记录可分成完全重复记录和相似重复记录，分别定义如下：定义2.1完全重复记录完全重复记录是指在数据表中除了主键外，其它各字段完全相同的记录，或者是在那些设计差的数据库中，没有主键，所有字段完全相同的记录。定义2.1相似重复记录相似重复记录是指那些客观上表示现实世界同一实体的，但是由于在格式、拼写上有些差异而导致数据库系统不能正确识别的记录。一般情况下，对几个记录可能指同一现实世界实体的这种情况较感兴趣，而不是在语句构成上相同的记录。为了减少数据源中的冗余信息，重复记录的清理是一项重要的任务。因此，本章主要研究如何清除数据源中的相似重复记录，具体内容组织如下：第2节分析了相似重复记录清理的相关研究；第3节给出了一种有效的相似重复记录清理方法；在此方法的基础上，第4节研究了一种提高相似重复记录检测精度的方法；为了提高该方法中相似重复记录的检测效率，第5节提出了一种提高相似重复记录检测效率的方法；第6节介绍了作者研制的记录生成器，该生成器为第7节的实验提供了条件；第7节通过实验验证了改进算法的效果；第8节总结了本章的工作。需要指出的是，本章的研究主要针对中文数据库。2.2相似重复记录清理的相关研究要想清理数据源中的相似重复记录，必须要先通过某种方法检测出相似重复记录，然后采取一定的策略清除这些重复记录，从而达到清理的目的。在相似重复记录的检测方面已经有了一些成果。在一个数据表中，完全重复记录的标准检测方法是先将数据库中的记录排序，然后，通过比较邻近记录是否相等来检测完全重复记录。完全重复记录不管以记录的哪一个部分进行分类，在分类排序后，都能保证互相相邻。这种方法可被扩展后用来检测相似重复记录，研究人员在此基础上提出了很多方法，比如，文献[62]将整条记录作为一个字符串进行排序，通过计算整个字符串的编辑距离来检测记录是否相似；文献[31]中提出的Sorted-Neiberhood方法以用户定义的健作为排序键进行排序，然后，通过一组规则定义的相等理论判定记录是否相似，其基本思想可描述如下：按照用户定义的排序键对整个数据表进行排序，将可能匹配的记录排列在一起。当然，按照某个排序键排一次序往往是不够的，需要按照不同的排序键对数据多次排序，再将结果结合起来。具体说来，Sorted-Neiberhood算法分为三步：创建排序键抽取记录中重要的字段或字段的一部分组成每条记录的排序键，排序键的选择对于检测结果的准确性至关重要。记录排序用第一步生成的排序键对记录排序。合并定义一个固定大小的窗口，在记录列表上移动，比较窗口内的记录是否相似，如图2.1所示。如果窗口的大小为L（2≤L≤N），那么每条最新进入窗口的记录与前面的L-1条记录逐一比较以找到匹配记录。窗口中第一条记录滑出窗口。至于说如何叫相似，由用户定义的规则指定，例如：假设R1、R2为两条记录IFR1中的字段Lastname等于R2中的字段LastnameANDR1中的字段Firstname等于R2中的字段FirstnameAND两记录的Address字段差别很小THENR1和R2相似ENDIF其中，“字段的差别”是通过将距离函数的计算结果与阈值比较确定的。距离函数一般包括：字符串编辑距离，语音距离和打字机距离，用户也可以自己定义距离函数。Sorted-Neiberhood算法的时间复杂度与定义的窗口大小有关，窗口大小为2时，复杂度为O(NlogN)，窗口大小为N时，复杂度为O(N2)。在目前常用的相似重复记录清理方法中，Sorted-Neiberhood算法是较为流行的匹配与合并算法，并且该算法已被应用到几个关于数据清理的软件之中。文献[55]先计算各记录的N-Gram值，然后以各记录的N-Gram值为排序键进行排序，再通过采用一种高效的应用无关的Pair-wise比较算法，通过计算两记录中单词间的编辑距离来判断记录的相似与否，并采用一种改进的优先队列算法来准确地聚类相似重复记录,该算法使用固定大小的优先队列顺序扫描已排序的记录,通过比较当前记录和队列中记录的距离来聚类相似重复记录；文献[56]在文献[55]的基础上提出了一种检测多语言数据重复记录的综合方法。上述这些方法的基本思想可以总结为：先对数据表中的记录排序，然后用某种方式检测相邻记录是否为重复记录，不同之处是所采用的排序方法和相似检测方法不同。本章在对这些方法研究的基础上，吸收这些方法的思想，来解决相似重复记录的清理问题，并对算法的关键环节进行改进，提高了相似重复记录的检测效率和检测精度。为了后文论述的方便，首先给出相似重复记录清理中的几个相关定义：定义2.3记录之间的相似度S记录之间的相似度S是根据两条记录的内容而计算出的一个表示两记录相似程度的数值，0<S<1。S越小，则两记录相似程度越高；若S=0，则表示两条记录为完全重复记录。定义2.4记录相似检测记录相似检测是指通过计算两条记录之间的相似度S，来判定两记录是不是重复记录。2.3相似重复记录的清理方法2.3.1相似重复记录清理方法总体描述根据以上分析，本文采用的相似重复记录清理方法的原理可以总结为如图2.2所示。由图2.2可以看出，相似重复记录的清理过程可总结为：记录排序→记录相似检测→相似重复记录合并/清除。其清理过程可描述如下：首先，把数据源中需要清理的数据通过JDBC（JavaDataBaseConnectivity,Java数据库连接）接口调入到系统中来；然后，执行数据清理，记录排序模块从算法库中调用排序算法，执行记录之间的排序；在记录已排序的基础上，记录相似检测模块从算法库中调用相似检测算法，作邻近范围内记录间的相似检测，从而计算出记录间的相似度，并根据预定义的重复识别规则，来判定是否为相似重复记录。为了能检测到更多的重复记录，一次排序不够，要采用多轮排序，多轮比较，每次排序采用不同的键，然后把检测到的所有重复记录聚类到一起，从而完成重复记录的检测；最后，对所检测出的每一组相似重复记录根据预定义的合并/清除规则，完成相似重复记录的合并处理。由图2.2可以看出，记录排序和记录相似检测是相似重复记录清理过程中的两个重要步骤，下面分别讨论这两个步骤中的关键技术。2.3.2记录排序为了能查找到数据源中所有的重复记录，必须比较每一个可能的记录对，如此以来，检测相似重复记录是一个很昂贵的操作，当数据源中数据量很大时，这会导致是一个无效和不可行的方案。为了减少记录之间的比较次数，提高检测效率，常用的方法是仅比较相互距离在一定范围的记录，即先对数据表中的记录排序，然后对邻近记录进行比较。比如，在文献[31]中，作者在整个分类后的数据表中通过移动一个固定大小的窗口，比较附近的记录。一个大小为W的窗口，在数据库中一次移动一个记录，新记录和这个窗口中的其它W-1个记录相比较。这样，记录比较的次数从O（T2）减少到O（TW），其中，T为数据库中记录的总数。因此，当数据源中数据量很大时，应该采用记录排序方法。对于记录排序方法，文献[33]使用某种应用相关的键来将相似记录聚类到邻近位置。文献[63]根据用户定义的键值来重排表记录，并采用滑动窗口来Pair-wise比较窗口内的记录。文献[55]是先计算记录的N-Gram值，然后按该值进行排序；文献[56]针对多语言文本的情况，采用序值表的方法来进行排序。由于本文的研究主要是针对中国信息化的现状，所以作者主要考虑采用中文表达的记录。根据对各种排序方法的分析，作者采用序值表的方法来对记录进行排序，该方法说明如下：对于西文字符，排序就是按西文字符的字典序排列，但对于汉字来说，存在多种排序方式。在国标GB2312-80中共收集汉字6763个，分成两级，一级汉字字库包括汉字3755个，按拼音字母排序，二级汉字字库包括汉字3008个，按部首排序。由此可见汉字本身的编码不满足任何一种统一的序值规则，不适合作序值使用。为了解决序值不统一的问题，采取建立序值文件的方式。目前，汉字通常有以下三种排序方式：拼音序、笔划序、部首序。对于汉字各种不同的排序方式，分别建立对应于GB2312-80汉字基本集的序值表。序值表中序值的存放按对应的汉字在汉字基本集中出现的顺序进行。因此，根据汉字的内码（0XB0A1-0XF7FE）可以直接计算出序值表中存放对应序值的入口地址，计算公式如下：其中，c1为汉字内码的第一个字节（区码）；c2为汉字内码的第二个字节（位码）；N为序值编码的长度，N=2（用两个字节来存放序值）；headoffset是序值表中存放第一个汉字（“啊”字的编码OXBOA1）的位置。序值表相当于自定义的一种编码，不同的排序方式对应各自的序值表。序值表的大小只有几十K，可以存放在内存中。根据上述公式，汉字的内码可直接映射为获取序值的地址索引，非常便于使用。对于要排序的字段，根据以上方法把该字段中所有的字符转换成相应的序值，然后，采快速排序算法可以对记录进行排序。在此排序的基础上，再采用相似重复记录检测算法对相邻记录进行检测，从而提高了检测效率。按以上方法重排记录后，相似记录被放在较接近的位置，从而可以在相对集中的范围内作记录的相似检测。但是由于排序时对错误的位置非常敏感，不能保证排序后的重复记录都在一起。因此这种方法也有一定的局限性。此外，对整个数据库记录进行重排的开销也很大。因此，从实用的角度考虑，在实际应用中，对于小批量数据，如记录总数小于5万时，没有必要采用复杂的记录排序算法，可以直接进行记录的比较，从而提高相似重复记录的查全率。2.3.3记录相似检测由图2.2可以看出，记录相似检测是相似重复记录清理过程中的一个重要步骤，通过记录相似检测，可以判断两条记录是不是相似重复记录。对于记录相似检测，一般采用Pair-wise比较算法，它是一种比较成熟的方法。本文吸收Pair-wise比较算法的思想，所采用的记录相似检测算法的伪码描述如下：算法略过2.3.4相似重复记录检测算法2.3.5相似重复记录的合并/清除当完成相似重复记录的检测之后，对检测出的重复记录要进行处理。对于一组相似重复记录，一般有两种处理方法：第一种处理方法第一种处理方法是把一组相似重复记录中的一个记录看成是正确的，其它记录看成是含有错误信息的重复记录。于是，任务就是删除数据库中的重复记录。在这种情况下，一些常用的处理规则是：人工规则人工规则是指由人工从一组相似重复记录中选出一条最准确的记录保留，并把其它重复记录从数据库中删除掉，这种方法最简单。随机规则随机规则是指从一组相似重复记录中随机地选出一条记录保留，并把其它重复记录从数据库中删除掉。最新规则在很多情况下，最新的记录能更好地代表一组相似重复记录。比如，越接近当前日期的信息准确性可能越高，经常使用账户上的地址要比退休账户上的地址权威一些。基于这种分析，最新规则是指选择每一组相似重复记录中最新的一条记录保留，并把其它重复记录从数据库中删除掉。完整规则完整规则是指从一组相似重复记录中选择最完整的一条记录保留，并把其它重复记录从数据库中删除掉。实用规则因为重复率越高的信息可能越准确一些，比如，如果三条记录中两个供应商的电话号码是相同的，那么重复的电话号码可能是正确的。基于这种分析，实用规则是指从一组相似重复记录中选择与其它记录匹配次数最多的一条记录保留，并把其它重复记录从数据库中删除掉。可以把以上方法定义成规则，存放在规则库中，供用户根据具体的业务要求选择使用。第二种处理方法第二种处理方法是把每一条相似重复记录看成是信息源的一部分。于是，目的就是合并一组重复记录，产生一个具有更完整信息的新记录。该方法一般要由人工进行处理。以上给出了常用的几种处理相似重复记录的方法，至于在执行相似重复记录的清理过程中采用什么样的处理方法，要根据具体的数据源以及用户要求来确定。2.4相似重复记录检测精度提高方法2.4.1等级法的使用在2.3.3节中研究了如何比较记录的相似性，其过程为：先比较两条记录中每个字段的相似度；然后对每个字段赋予不同的权重，计算出两条记录的相似度，从而判定两条记录是不是相似重复记录。由此可见各个字段所赋予的权重对检测精度影响很大，合适的赋值能提高记录相似检测的精度。文献[55]在进行记录比较时，没有考虑各记录中各字段的权重；文献[56]虽然考虑到了字段权重的重要性，但没有给出一个合适的权重选取方法。本节在对相关方法研究的基础上，采用一种计算字段权重的有效方法——等级法来计算各字段的权重。当进行相似重复记录检测时，根据对具体业务的分析，采用该方法来计算相应字段的权重，然后，对不同的字段使用不同的权重，从而提高相似重复记录检测的精度。等级法是一种计算记录字段权重的方法，它是让用户根据数据表中各个字段的重要程度来划分等级，即最重要字段的等级指定为1，第二重要的字段等级指定为2，等等。然后，根据记录各字段的等级，计算其相应的权重。文献[72，73]都表明采用等级法不但效果好，而且容易使用。表2.4和表2.5为使用等级法时所用的两种表，其中，表2.4是交给每个操作用户的表，操作用户根据自己的认识，在这张表上给各字段划分等级；表2.5是分析员用来综合所有操作用户意见的等级表。在表2.4和2.5中，Yk表示数据表中记录的K个字段，Suk是操作用户u为字段Yk所指定的等级，Sk表示各个字段最终统一的等级，k∈{1,2….K}，u∈{1,2….N}。表2.4中的“字段说明”用来补充说明字段的作用及意义，便于操作用户准确地为各字段指定等级。表2.5中汇集了不同操作用户给各个字段指定的等级值，根据每个操作用户所给的等级值，可以计算出各个字段最终统一的等级。2.4.2等级转变成权重的方法2.4.3利用权重提高检测精度在运行相似重复记录检测的过程中，首先采用等级法来获取记录中不同字段的等级，并采用RC方法生成各字段相应的权重。然后，在记录相似检测过程中对不同字段指定不同的权重，这样可提高相似重复记录的检测精度，从而更好地识别重复记录。采用等级法生成的权重存放在规则库中，供运行数据清理时调用。在第七章的实例中，作者会采用这种方法来检测相似重复记录，通过实例来验证这种方法的有效性。2.5相似重复记录检测效率提高方法2.5.1提高检测效率的方法分析快速完成数据清理是很重要的，因此，必须提高相似重复记录的检测效率。从前面的分析可以看出：在相似重复记录检测过程中，记录间的相似检测是一个重要问题，其关键步骤是记录中各字段的相似检测，其效率直接影响整个算法的效率，记录中大多字段采用编辑距离算法来检测，由于编辑距离算法的复杂度为O(m×n)，当数据量很大时，如不采用一种高效的过滤方法来减少不必要的编辑距离计算，则会导致相似检测时间过长。因此，为了提高相似重复记录的检测效率，本文提出了一种优化相似重复记录检测效率的方法，该方法采用长度过滤方法减少不必要的编辑距离计算。实验证明：长度过滤方法能有效地减少不必要的编辑距离计算，降低相似检测时间，从而提高了相似重复记录的检测效率。由于作者提出的这种优化方法用于记录相似检测模块中，所以，不管记录相似检测过程中是否进行记录排序，这种优化方法都适用。2.5.2长度过滤方法2.6实验准备—记录生成器的研制2.6.1记录生成器的作用2.6.2记录生成器的原理及实现2.7改进算法检测效果的实验验证2.7.1度量相似重复记录检测效果的标准2.7.2长度过滤方法有效性的实验检测2.7.3实验结果分析2.8本章小结如何消除数据源中的重复信息是数据清理研究中的一个热门课题。本章在研究了相似重复记录清理相关技术的基础上，给出了一种相似重复记录清理的综合方法，并对该方法进行了改进，从而提高了该方法的检测精度和检测效率。本文中的方法和文献[39，55，56]中所描述的相似重复记录检测方法相比，从两种重要的途径上进行了改进：第一个改进是为了提高相似重复记录的检测精度，采用等级法为记录字段指定合适的权重，从而提高了相似重复记录的检测精度；第二个改进是提出了一种提高相似重复记录检测效率的方法，该方法采用长度过滤方法优化相似重复记录检测中的相似检测算法，避免了不必要的编辑距离计算，从而提高了相似重复记录的检测效率。这两种改进可以用于任何相似重复记录检测算法之中。此外，作者还构造了合适的实验环境，作了大量的检测实验，翔实的实验结果验证了改进方法的科学性及效果。第三章单数据源中不完整数据的清理3.1引言数据不完整是产生数据质量问题的一个重要因素，简单地说，数据不完整是指数据源中字段值的缺失问题。表3.1是ERP系统中“检验单”数据表中的一些数据，表中给出了一些不完整数据的例子。在这个表中，由于种种原因，记录中的一些字段值缺失，如第一条记录中字段“送检日期”的值为空，第二条记录中字段“状态”的值为空，第三条记录中字段“送检部门编号”的值为空。这种现象在数据源中会常常出现，然而并未引起人们的注意，一般也只是对它做一些简单的处理。但是，不完整数据的存在不但会影响信息系统的运行效果，还会引起决策错误，特别是数值数据中出现不完整数据。故必须要解决数据源中的数据不完整问题。在多数情况下，数据源之间的字段值并不是相互独立的。所以，通过识别字段值之间的关系可以推断出缺失的字段值。基于以上分析，为了清理数据源中的不完整数据，本章提出了一种有效的清理方法，该方法首先检测记录的可用性，然后删除不可用的记录，最后，对可用记录通过选用合适的方法来处理该记录的缺失值，从而完成数据源中不完整数据的清理。主要内容组织如下：第2节论述了作者所提出的不完整数据清理方法；第3节给出了如何采用K-最临近算法来估算缺失字段值；第4节总结了本章的工作。3.2不完整数据的清理方法3.2.1不完整数据清理方法总体描述对于数据源中不完整数据的清理，可分成以下三步来处理：检测数据源中的不完整数据要清理数据源中的不完整数据，首先要做的就是把数据源中的不完整数据检测出来，以便于下一步的处理。判断数据的可用性如果一条记录中字段值缺失的太多，或者剩余的字段值中根本就不包含关键信息，就没有必要花费精力去处理该记录。因此，对于检测出的不完整数据，要根据每一条记录的不完整程度以及其它因素，来决定这些记录是保留还是删除。判断数据的可用性就是完成这一工作。推断缺失字段的值推断缺失字段的值是指对那些要保留的记录，要采取一定的方法来处理该记录中缺失的字段值。根据以上分析，作者提出一种不完整数据清理方法，其原理如图3.1所示。采用该方法清理数据源中不完整数据的过程简要描述如下：首先，把数据源中需要清理的数据通过JDBC接口调入到系统中来，不完整数据检测模块调用算法库中的检测算法，来判定每条记录是否完整。如果记录完整，则无须清理，直接将该记录通过JDBC接口导入到数据源中，如果记录不完整，则把该记录导入到记录可用性检测模块中来；记录可用性检测模块从算法库中调用可用性检测算法，执行记录的可用性检测，然后根据规则库中预定义的规则，来判定该记录是否可用；如果记录不可用，则直接删除该记录，如果记录可用，则不完整数据处理模块从算法库中调用相关算法来处理该记录中缺失的字段值；最后，处理完的数据经JDBC接口导入到数据源中。在以上这种不完整数据清理方法中，通过在规则库中定义合适的阈值，能灵活、合理地确定记录的取舍；对于要保留的记录，又可以通过选用合适的不完整数据处理方法来处理该记录，可见这种不完整数据清理方法具有较强的通用性和灵活性。所以，该方法能较好地完成不完整数据的清理工作。3.2.2不完整数据的可用性检测从图3.1中可以看出，记录的可用性检测是不完整数据清理过程中的一个重要步骤。如果一条记录字段值缺失的太多，或者剩余的字段值中根本就不包含关键信息，就没有必要花费精力去处理该记录。因此，要解决数据的不完整问题，判断记录的可用性非常重要。判断记录的可用性也就是根据每一条记录的不完整程度及其它因素，来决定该记录是保留还是删除。对于记录的可用性检测，作者采用的方法是：先评估每一条记录的不完整程度，也就是先计算每一条记录中缺失字段值的百分比，再考虑其它因素，如记录剩余的字段值中关键信息是否存在，然后决定记录的取舍。由于当一条记录某字段取值为缺省值时，意味着该字段值已缺失，所以，我们把字段值为缺省值的也作为缺失值来处理。评估一条记录不完整程度的方法如下：3.2.3缺失字段值的处理在完成记录可用性检测之后，对那些要保留的不完整数据记录R，要采取一定的方法来处理该记录中缺失的字段值，一般采取以下几种处理方法：人工处理法对一些重要数据，或当不完整数据的数据量不大时应该采用这种方法。常量值替代法常量替代法就是对所有缺失的字段值用同一个常量来填充，比如用“Unknown”或“MissValue”，这种方法最简单。但是，由于所有的缺失值都被当成同一个值，容易导致错误的分析结果。平均值替代法平均值替代法就是使用一个字段的平均值来填充该字段的所有缺失值。常见值替代法常见值替代法就是使用一个字段中出现最多的那个值来填充该字段的所有缺失值。估算值替代法估算值替代法是最复杂，也是最科学的一种处理方法。采用这种方法处理缺失字段值的过程为：首先采用相关算法，如回归、判定树归纳、K-最临近等算法预测该字段缺失值的可能值，然后用预测值填充缺失值。以上给出了常用的几种处理记录中缺失字段值的方法，至于在执行不完整数据的清理过程中采用什么样的处理方法，要根据具体的数据源以及用户要求来确定。由于采用估算值替代法最复杂，本章后半部分给出了如何采用K-最临近算法来估算缺失字段值。由于本文提出的不完整数据清理方法具有可扩展性，其它更好的估算值替代法也可以用于其中。3.3采用K-最临近算法估算缺失字段值3.3.1K-NN算法的特点3.3.2采用K-NN算法估算缺失字段值的过程3.3.3K-NN算法中距离函数的分析3.3.4采用距离权重优化K-NN算法3.4本章小结不完整数据的清理是数据清理中的一个重要问题。本章针对数据源中出现的不完整数据，提出一种有效的清理方法，该方法首先检测记录的可用性，然后删除不可用的记录，最后，对可用记录通过选用合适的算法来处理该记录的缺失值，从而完成数据源中不完整数据的清理。此外，本章还给出了如何采用K-NN算法来估算缺失字段值。在第七章，把这种不完整数据清理方法加入到作者研制的数据清理软件平台中去，成为数据清理的一种有效工具。需要指出的是，对于检测出的不完整数据，在条件许可的情况下，最好采取人工处理的方法，特别是对一些关键数据。但是，在有些情况下，也可以采用K-NN等算法来推断出缺失值的最可能值。第四章单数据源中错误数据的清理4.1引言在三种重要的数据质量问题上，数据错误是最重要的数据质量问题。简单地说，数据错误是指数据源中记录字段的值和实际的值不相符。表4.1是ERP系统中“检验单”数据表中的一些数据，表中给出了一些错误数据的例子。在这个表中，由于种种原因，记录中含有一些错误数据，比如：第一条记录中“确认日期”比“送检日期”早，但实际上，“送检日期”应该比“确认日期”早；由于录入错误，检测单J0302已经检验过，在数据表其字段“状态”的值应该为“R”，但实际上却还是“I”；第三条记录中，编号为G99032的供应商已不存在，可能是操作员在录入数据时录错了“供应商编号”这个字段的值。如果信息系统中包含错误数据，记录重复问题和数据不完整问题则会更难清理。故必须要清理数据源中的错误数据。对于重复记录清理问题，已经在第二章进行了研究，对于不完整数据清理问题，已经在第三章进行了研究，本章主要研究如何通过清理数据源中的错误数据来达到提高数据质量的目的。对于错误数据的清理，有两种相联系的方法：第一种通过检测数据表中单个字段的值来发现错误数据这种方法主要是根据数据表中单个字段值的数据类型、长度、取值范围等，来发现数据表中的错误数据，如表4.2中列出了几种检测单个字段值中错误数据的方法。第二种通过检测字段之间以及记录之间的关系来发现错误数据这种方法主要是通过在大量数据中发现特定的数据格式，如几个字段之间的关系，从而得到字段之间的完整性约束，如采用函数依赖或特定应用的业务规则来检测并改正数据源中的错误数据。另外，采用一个具有高置信度的关联规则能够检测违反这一规则的数据质量问题，比如，一个置信度为99%的关联规则“总数＝数量×单价”表明1%记录不遵守这一规则，需要对记录做进一步的检查。对于这一方面，一些数据挖掘工具，如WizSoft公司的WizRule和InformationDiscovery公司的DataMiningSuite，能通过推断字段和它们的值之间的关系，计算出一个置信度来指示符合条件的记录。针对以上分析，本章主要研究如何清理数据源中的错误数据，从而达到提高数据质量的目的。内容组织如下：第2节研究了如何采用基于孤立点检测的方法来检测数据源中的错误数据，并给出了一种有效的孤立点检测方法；第3节提出了一种基于业务规则的错误数据检测方法，该方法能有效地检测数据源中的错误数据；第4节总结了本章的工作。4.2基于孤立点检测的错误数据清理4.2.1基于孤立点检测的错误数据清理方法在数据源中经常含有一定数量的异常值，它们与数据源的其它部分不同或不一致，这样的数据常常被称为孤立点（Outlier）。Hawkins给出了孤立点本质性的定义：孤立点是在数据源中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。孤立点可能是度量或执行错误所导致，也可能是固有的数据变异性的结果，例如，一个人的年龄为999，可能是程序对数据表记录中年龄字段的缺省设置所产生的；一个公司总经理的工资，自然远远高于公司其他雇员的工资，成为一个孤立点；如果一个整型字段99%的值在某一范围内，则剩下1%的不在此范围内的记录可以认为是异常。孤立点检测是数据挖掘中的一个重要方面，用来发现数据源中显著不同于其它数据的对象，它常常应用在电信和信用卡欺骗检测、贷款审批、气象预报和客户分类等领域中。由于数据错误往往表现为孤立点，所以，通过检测并去除数据源中的孤立点可以达到数据清理的目的，从而提高数据源的数据质量。但是，并非所有的孤立点都是错误的数据，所以，在检测出孤立点后还应结合领域知识或所存储的元数据，从中找出相应的错误数据。基于以上分析，为了清理数据源中的错误数据，作者提出一种基于孤立点检测的错误数据清理方法，其原理如图4.1所示。采用该方法清理数据源中错误数据的过程简要描述如下：首先把数据源中需要清理的数据通过JDBC接口调入到系统中来，执行数据清理。数据预处理模块调用算法库中的相应算法对数据源进行预处理，如标准化数据记录格式，并根据预定义的规则，把数据记录中的相应字段转化成同一格式。孤立点检测模块从算法库中调用孤立点检测算法，执行记录的孤立点检测，然后根据规则库中预定义的错误识别规则，来判定记录中是否含有孤立点；如果记录中没有孤立点，则直接将该记录经JDBC导入到数据源中。如果检测到记录中有孤立点，则调用规则库中的相关规则，或者由人工来判定该孤立点是否为错误数据，如果不是错误数据，则直接将该记录经JDBC导入到数据源中；如果是错误数据，则错误清理模块从规则库中调用相关规则来改正该记录中的错误字段值，处理完的数据经JDBC导入到数据源中。由于本文提出的解决方法具有较强的通用性，由于任何孤立点检测算法都适用于其中，从而使该方法具有较强的适应性；通过在规则库中合理定义错误识别规则，能准确地检测出数据源中的孤立点。4.2.2孤立点检测的相关方法通过以上分析可以看出，如何检测数据源中的孤立点是基于孤立点检测的错误数据清理方法中的一个关键步骤，本节分析常用的孤立点检测算法。从20世纪80年代起，孤立点检测问题就在统计学领域里得到广泛研究。通常用户用某个统计分布对数据点进行建模，再以假定的模型，根据点的分布来确定是否异常。目前，已经研究出若干种检测孤立点的方法，大多数方法建立在统计学的基础上，这些方法大致可以分为4类：基于分布的、基于深度的、基于距离的和基于密度的，每种方法都给出了相应的孤立点的定义。基于分布的方法基于分布的方法对给定的数据集合假定一个分布或概率模型，如一个正态分布，然后根据模型对数据集中的每个点进行不一致性测试，如果与分布不符合，就认为它是一个孤立点。这种方法的缺陷是：要求知道数据集参数（如假设的数据分布）、分布参数（如平均值和方差）和预期的孤立点的数目。然而，在许多情况下，用户并不知道数据集合参数的知识，况且现实数据也往往不符合任何一种理想状态的数学分布。基于距离的方法基于距离（Distance-based，DB）的孤立点的概念是由Knorr和Ng在1998年提出的。他们认为如果一个点与数据集中大多数点之间的距离都大于某个阈值，那么这个点就是一个孤立点。也就是说，不依赖于统计检验，可以将基于距离的孤立点看作是那些没有“足够多”邻居的对象，这里的邻居是基于给定对象的距离来定义的。基于距离的孤立点定义如下：如果数据集合S中对象至少有p部分与对象O的距离大于d，则对象O是一个带参数p和d的基于距离（DB）的孤立点，即DB（p，d）。与基于分布的方法相比，基于距离的孤立点检测包含并扩展了基于分布的思想，当数据集不满足任何标准分布时，基于距离的方法仍能有效地发现孤立点。而且，这种方法能够处理任意维的数据。但不足的是，该方法要求用户必须合理地设置参数p和d，这就需要用户反复输入p和d进行测试，以确定一个满意解，这种情况需要用户拥有相当的领域知识。基于密度的方法基于密度的孤立点的定义是在基于距离的基础上建立起来的，这种方法将数据点之间的距离和某一给定范围内的数据点的个数这两个参数结合起来，得到密度的概念，根据密度来判断一个点是否是孤立点。基于深度的方法在基于深度的方法中，每个数据对象被映射为k维空间中的一个点，并赋予一个特定定义的深度，根据不同的深度将数据划分成不同层次。根据统计学结论，异常数据往往存在于较浅的层次中，深度小的数据对象是孤立点的可能性比较大。基于深度的方法对二维和三维空间上的数据比较有效，但对四维空间及四维以上的数据，处理效率比较低。4.2.3基于模糊集理论的孤立点检测根据上一节对常用孤立点检测方法的分析，可以看出这些方法不是太复杂，就是有一定的局限性。文献[96]给出一种简单、易用的孤立点检测方法，该方法使用模糊集理论来模仿人工检测异常值，采用独立的过程来分别检测离散型数据和连续型数据中的孤立点，它适用于单变量分布数据。本章中，作者把这种方法应用到基于孤立点检测的错误数据清理方法中，来检测数据源中的孤立点。该检测算法的原理说明如下：为了检测数据源中的孤立点，该检测算法通过检测字段值的一致性来判定一个字段值是不是孤立点，即：首先要定义出字段值的一致性；然后，根据所定义的一致性去检测各个字段值；如果是一致的，则不是孤立点，否则就是孤立点。由于在数据源中，离散型变量和连续型变量是不一样的，所以，把孤立点的检测分成离散型变量和连续型变量两部分分别来完成。离散型变量是指字段值的个数是有限的；连续型变量是指字段值的个数是无限的。在实际应用中，二者并没有严格的区别。这里，离散型变量主要是指布尔型变量，或者是指所包含的值有限的数值变量。4.3基于业务规则的错误数据清理4.3.1业务规则的重要性在进行数据清理时，如能利用具体的业务知识，则能更好地完成数据清理。比如在表4.3中，错误数据的出现是因为数据违反了业务规则。通过检测记录中各字段的值是否符合业务规则，比如是否超出了该字段的数值范围，可以判断该字段值是否正确。使用业务规则来清理数据源中存在的错误数据是最简单、最有效的方法，如数值越界问题，可以通过给定数值的范围，即上下界，通过比较就可以检测出来；如属性依赖冲突，可以简单地通过给出一个属性之间的对照检查表来解决，如表4.4所示的数据表可用来检测地方名与邮政编码之间的正确与否。此外，通过业务规则还可以用来查找不标准的零件名称。对于检测出来的错误数据，清理也非常简单。然而，多数关于数据清理的研究“过分地”追求清理方法与具体业务的无关性，而没有考虑、也不想考虑利用具体的业务知识，故不能很好地完成数据源的清理工作。本节研究如何利用具体的业务规则来清理错误数据，在此基础上，把该方法应用到作者研制的数据清理软件平台中去，通过在规则库中预定义业务规则来检测数据是否满足字段域、业务规则等，从而检测出数据源中的错误数据。这种方法的清理效果取决于对具体业务的分析以及定义规则的数目。4.3.2基于业务规则的错误数据清理方法根据上一节的分析，作者提出一种基于业务规则的错误数据清理方法，其原理如图4.2所示。采用该方法清理数据源中错误数据的过程简要描述如下：首先，根据具体业务分析，在规则库中定义业务规则；然后，把数据源中需要清理的数据通过JDBC接口调入到系统中来，执行错误数据清理。对于数据源中的每条记录，规则库检索模块检索规则库中的业务规则，根据业务规则，对每条记录作以下检测：第一阶段，对一条记录的每个字段进行检测，这一阶段主要是根据字段的域来检测；第二阶段，对每条记录的多个字段进行检测，这一阶段主要是根据同一记录中字段之间的关系来检测，比如函数依赖关系，业务规则等。通过以上过程可以判定每条记录是否符合所定义的业务规则；如果记录符合所定义的业务规则，则直接将该记录经JDBC导入到数据源中。如果记录不符合所定义的业务规则，则该记录含有错误数据，错误清理模块从规则库中调用相关规则来改正该记录中的错误字段值，如果没有合适的处理规则，则由人工来处理。处理完的数据经JDBC导入到数据源中。由以上分析可以看出，这种方法的清理效果取决于对具体业务的分析以及定义规则的数目。4.3.3业务规则4.3.3.1业务规则的定义与分类在本文中，业务规则是指符合业务的某一数值范围、一个有效值的集合，或者是指某一种数据模式，如地址或日期。业务规则根据其规则内容，可分成通用业务规则和特定业务规则。通用业务规则是指对多数信息系统都适用的业务规则，如工资必须大于或等于零，如果在数据表中Salary=“-100”，则表示无效的工资。特定业务规则是指针对某一种特定行业信息系统的业务规则，如在ERP的库存管理系统中，物料的出库日期要比入库日期早，这种规则就属于特定业务规则。规则的表示方式在进行数据清理时，要根据对具体业务的分析，在规则库中定义相应的业务规则，然后，用这些业务规则来完成相应的数据清理工作。在基于业务规则的数据清理中，存在着确定性业务规则的和不确定性业务规则。因此，在规则库中，业务规则的表示也相应地分成确定性业务规则表示和不确定性业务规则表示，分别说明如下：4.3.3.3业务规则库的优化策略基于业务规则的错误数据检测的工作过程，就是不断搜索规则库，并对数据源中的记录进行检查，看记录是否符合所定义的业务规则，从而检测出错误数据。由于整个规则库中所包含的规则数目较多，搜索空间较大，势必会降低检测效率。为了提高检测效率和系统运行的可靠性，根据对业务规则的分类，作者把业务规则库分成两个子规则库，即通用业务规则子规则库和特定业务规则子规则库。在完成某个清理任务时，除了需要到通用业务规则子规则库中搜索外，具体业务只需要到该任务相关的特定业务规则子规则中搜索，这样可以大大减小搜索空间。4.4错误数据的处理对于数据源中检测出的孤立点，一般先要采用人工方法来判定该数据是否为错误数据。如果是错误数据，再对该数据进行处理。一般说来，从数据源中检测出的错误数据数量不大，所以，对于检测出的错误数据，可以直接由人工来处理。当然，对于一些不重要的错误数据，也可以采取类似于不完整数据的处理方法，比如：常量替代法常量替代法就是对所有错误数据用同一个常量来填充，比如用“Error”或“WrongValue”，这种方法最简单，但是不能从根本上解决问题。平均值替代法平均值替代法就是使用一个字段的平均值来填充该字段的所有错误数据。最常见值替代法最常见值替代法就是使用一个字段中出现最多的那个值来填充该字段的所有错误数据。估算值替代法采用估算值替代法处理错误数据的过程为：首先采用相关算法，如回归、判定树归纳等算法预测该错误数据的可能值，然后用预测值替代错误数据。4.5本章小结数据错误是最重要的数据质量问题。本章研究了如何采用孤立点检测和业务规则这两种方法来检测数据源中的错误数据，这两种错误数据清理方法的原理分别总结如下：基于孤立点检测的错误数据清理方法由于数据错误往往表现为孤立点，所以，通过检测孤立点的方法可以检测数据源中的错误数据，从而达到数据清理的目的。基于这种思想，本章提出了一种基于孤立点检测的错误数据清理方法，并在对常用孤立点检测算法进行比较、分析的基础上，采用一种有效的孤立点检测方法来检测数据源中的孤立点。后面把这种检测孤立点的方法应用到作者研制的数据清理软件平台中，使之成为一种有效、实用的数据清理的方法。基于业务规则的错误数据清理方法在进行数据清理时，如能利用具体的业务知识，则能更好地完成数据清理。故此，本章提出了一种基于业务规则的错误数据清理方法，该方法具有简单、易用、清理准确度高等优点。但是，这种方法具有一定的局限性：它需要用户非常熟悉具体的业务，而且数据源的业务规则也比较容易获得。所以，这种方法只能用于业务规则容易获得的数据源中。但是，从某种程度上来说，这种方法也不失为是一种好的错误数据清理方法。在第七章，把这种数据清理方法应用到作者研制的数据清理软件平台中去，通过在规则库中预定义业务规则来检测数据源中的数据错误，从而成为一种有效的数据清理辅助工具。值得指出的是：对于错误数据的清理，由于每种方法的适用范围不同，故需要尽可能采用多种清理方法，多种方法能提高错误数据清理的综合效果。作者在有限的篇幅中仅研究了部分有效的错误数据清理方法，其它方法仍有待于进一步的研究。第五章多数据源集成中的数据清理5.1引言前面的章节研究了单数据源中数据清理的关键技术。随着信息化的进展，企事业单位存在很多自治（Heterogeneous）、独立（Autonomous）的数据源需要集成。其中，自治数据源指那些具有不同的数据模型、模式、数据表示以及接口等的数据源；独立的数据源是指每个数据源都是单独开发的，没有考虑其它数据源的存在，它们由不同的组织来维护。正是由于每个数据源都是为了特定应用，单独开发、部署和维护的，这就很大程度上导致数据管理系统、数据模型、模式设计和实际数据的不同。比如：在两个数据源中，同一个相同的字段可能有不同的命名，或者两个不同的字段可能有相同的命名；在一个数据源中，一个字段可能由两列构成，而在另一个数据源中，一个字段可以仅由一列构成。由于多个数据源中的数据可能会出现不同表示、重复、冲突等现象，另外，每个数据源都可能含有脏数据，当多个数据源集成时，发生在单数据源中的这些问题会更加严重。故此，多数据源集成时的数据清理问题也应当引起我们的重视。为了更好地理解多数据源集成中数据清理的重要性，首先，以ERP系统中的“供应商”信息为例来说明多数据源的数据集成问题。在表5.1和5.2中，两个表示供应商信息的数据表分别来自两个不同的数据源，这两个数据源都是关系数据库格式的，但存在模式和数据冲突。在模式级上，有命名冲突，如在表5.1中供应商编号用“ID”表示，而在表5.2中供应商编号用“NO”表示；数据表结构不同，如在表5.1中没有“信用等级”和“Email”这两个字段，而在表5.2中没有“传真”这个字段。在实例级上，在表5.1中，“城市”这个字段的数据是用具体城市名来表示的，而在表5.2中，“城市”这个字段的数据是用代号来表示；字段“联系电话”的数据格式不同：在表5.1中格式为“××××-×××××××”、而在表5.2中格式为“(××××)×××××××”；关于“冻结标志”的数据表示也不同：在表5.1中用“0/1”表示、而在表5.