软件导刊·２００７·２月号Web 数据清洗研究
刘
华，胡
燕，王
涛
（武汉理工大学计算机科学与技术学院，湖北武汉４３００７０）
作者简介：刘华（１９７７－），武汉理工大学计算机科学与技术学院研究生，研究方向为数据挖掘；胡燕（１９６５－），女，武汉理工大学副教授，研究方向为人工
智能、数据挖掘；王涛（１９７９－），男，武汉理工大学计算机科学与技术学院研究生，研究方向为网络数据库。
摘
要：随着时代的发展，越来越多的数据来源于网络。但是由于Ｗｅｂ数据的特点，从网上信息抽取得来的
数据存在着大量“脏数据”，并不能直接使用，因而有必要进行数据清洗，消除“脏数据”，转化为可直接使用的数据。针对实例层次的数据质量问题系统分析了Ｗｅｂ数据清洗的方法
关键字：Ｗｅｂ数据；数据清洗；相似重复记录中图分类号：ＴＰ３９３．０１
文献标识码：Ａ
文章编号：１６７２－７８００（２００７）０２－００７５－０３
０前言
随着Ｗｅｂ的迅速普及，网站的数量
越来越多，越来越多的机构和个人在网络上发布信息、查信息，网络成为人们获得信息的必要途径和重要手段。一家网站不可能提供全面的信息，人们所需求的数据分散在多家网站的Ｗｅｂ网页上。网页信息抽取和Ｗｅｂ数据挖掘越来越成为研究的重点。由于Ｗｅｂ数据的特点，从Ｗｅｂ上得到的数据中有可能存在着大量的脏数据，引起的主要原因有：滥用缩写词、惯用语、数据输入错误、重复记录、丢失值、拼写变化、不同的计量单位和过时的编码等。如果其中存在着大量的脏数据，那么这些数据也是没有任何意义的，因为“垃圾进，垃圾出”（ｇａｒｂａｇｅｉｎ，ｇａｒｂａｇｅｏｕｔ），根本就不可能为决策分析系统提供任何支持。为了清除脏数据，获得有用的数据必须进行数据清洗。
１数据清洗的原理
数据清洗（ｄａｔａｃｌｅａｎｓｉｎｇ／ｄａｔａｃｌｅａｎ－
ｉｎｇ／ｄａｔａｓｃｒｕｂｉｎｇ）是一个减少错误和不一
致性、解决对象识别的过程。数据清洗有三个主要领域：数据仓库，数据仓库中的知识发现（ＫＤＤ，又称为数据挖掘）和数据／信息质量管理（如，全面数据质量管理
ＴＤＱＭ）。１．１
数据质量
学术界目前对数据质量还没有一个固定的一成不变的定义，目前倾向的定义为数据的一致性（ｃｏｎｓｉｓｔｅｎｃｙ）、
正确性（ｃｏｒ－ｒｅｃｔｎｅｓｓ）、
完整性（ｃｏｍｐｌｅｔｅｎｅｓｓ）和最小性（ｍｉｎｉｍａｌｉｔｙ）这４个指标在信息系统中得到
满足的程度。根据处理的是单数据源还是多数据源以及问题是模式层的还是实例层的，数据质量问题分为４类：单数据源模式层问题（如缺少完整性约束、糟糕的模式设计等）、单数据源实例层问题（如数据输入错误）、多数据源模式层问题（如异构数据模型和模式设计等）、多数据源实例层问题（如冗余、冲突、不一致的数据等）。
单数据源中出现的问题在多数据源中也有可能出现，模式层次上的问题也会体现在实例层次上。模式层次的问题可以通过改进模式设计、模式转化和模式集成来解决。但实例层次的问题在模式层次上是不可见的。所以本文的数据清洗主要针对实例层次的数据质量问题。
１．２数据清洗原理
数据清洗就是利用有关技术如数理统计、数据挖掘或预定义的数据清洗规则将脏数据转化成满足数据质量要求的数据。按数据清洗的实现方式与范围，可将
数据清洗分为４种：①手工实现方式：用人工来检测所有的错误并改正，这只能针对小数据量的数据源。②通过专门编写的应用程序：通过编写程序检测／改正错误。但通常数据清洗是一个反复进行的过程，这就导致清理程序复杂、系统工作量大。
③某类特定应用领域的问题，如根据概率
统计学原理查数值异常的记录。④与特定应用领域无关的数据清洗，这一部分的研究主要集中于重复记录的检测／删除。
２ＸＭＬ在Ｗｅｂ数据清洗中的作用
２．１
Ｗｅｂ数据的特点
由于Ｗｅｂ的开发性，使得Ｗｅｂ上的信息与日俱增，而且其信息还在不断地发生更新，各网站每天都在更新各自的页面，相应的链接信息和数据库中的信息也在频繁地更新。因此Ｗｅｂ数据具有海量性、动态性的特点。
Ｗｅｂ上的每个站点视作一个数据源。
由于每个站点间的信息和组织不同，即每个数据源都是异构的，因而互联网形成了一个巨大的异构数据集成环境。和传统数据库数据不同，Ｗｅｂ的数据都非常复杂，是一种非完全结构化的数据，这也被称之为半结构化数据。因此Ｗｅｂ数据具有异构性、半结构化的特点。
２．２ＸＭＬ在数据情洗中的作用
７５
软件导刊·２００７·２月号
Ｗｅｂ上数据的特点使得进行Ｗｅｂ数
据清洗时，首先要有一个模型来清晰地描述Ｗｅｂ上的数据，还需要一种半结构化模型抽取技术，因为Ｗｅｂ上的数据清洗是以信息抽取技术为前提。ＸＭＬ的简单而又灵活的标准格式，为基于Ｗｅｂ的应用提供了一个描述数据和交换数据的有效手段，它的可扩展性和自描述性特点非常适用于不同数据源的信息交互。因此，选定ＸＭＬ作为数据交换的中间平台，通过包装器将Ｗｅｂ数据转化为ＸＭＬ文档，然后将ＸＭＬ文档映射到数据库中，利用关系数据库的特点进行数据清洗，得到符合我们使用数据。图１给出了基于ＸＭＬ数据清洗的流程图。
３
基于Ｗｅｂ教学知识的数据清洗
３．１
Ｗｅｂ信息的抽取
目前国内外对Ｗｅｂ数据挖掘的研究
主要集中在电子商务、网站设计和搜索引擎等方面的应用研究，而针对某学科领域的学科知识和专家知识的Ｗｅｂ数据挖掘应用不多，针对教学领域的教学专家知识的Ｗｅｂ数据挖掘更少。随着教育的信息化，网上资源日益丰富，从Ｗｅｂ中获得学科领域知识也是今后的发展方向。以《数据机构》课程为例，通过在百度输入“数据机构”搜索到网页ｈｔｔｐ：／／ｗｗｗ．ａｈｕｔ．ｅｄｕ．ｃｎ／
ｊｐｋｃ／ｓｊｊｇ／ｊｉａｏａｎ，将网页内容通过Ｗｒａｐｐｅｒ
的抽取转化为ｘｍｌ文档
＜计算机教学＞
＜课程名＞数据结构＜／课程名＞＜章＞第二章线性表＜／章＞＜节＞基本概念＜／节＞
＜知识点＞线性表是由ｎ（ｎ≥０）个类
型相同的数据元素组成的有限序列＜／知识点＞
＜／计算机教学＞３．２
ＸＭＬ与关系数据库的映射
为了在数据库与ＸＭＬ文档之间传递数据，必须在ＸＭＬ文档结构和数据库结构之间建立映射，实际转换中作为映射的方式，一般有以下２种：①以模板驱动映射：通过在ＸＭＬ文档中嵌入可以被中间层功能代理支持的ｓｑｌ指令来实现数据的映射。②以模型驱动映射：通过在ＤＴＤ／
Ｓｃｈｅｍａｓ中定义数据模型的方法，建立数
据库中数据与ＸＭＬ文档中数据的映射。将３．１中的ＸＭＬ文档映射为表中一条记录Ｒ１。
４
相似重复记录的消除
４．１
重复记录的定义
数据质量问题中的一种常见情况是
一个现实实体可能由多个不完全相同的记录来表示，这样的记录被称作相似重复记录（ａｐｐｒｏｘｉｍａｔｅｌｙｄｕｐｌｉｃａｔｅｄｒｅｃｏｒｄｓ）。检测和消除相似重复记录是数据清洗和提高数
据质量要解决的主要问题之一。探测相似重复记录的过程也被称为记录匹配过程。网上的信息过于丰富，难免会有重复信息，如在ｈｔｔｐ：／／１６６．１１１．４．５４：２０００／网页通过信息抽取得到记录Ｒ２。
记录Ｒ１和记录Ｒ２可以被认为是相似重复记录
４．２
重复记录清洗的基本过程
（１）预处理：①属性选择。选择用于记录匹配的属性。②初步聚类。主要是对数据库中的记录进行排序。③分配属性的权重。根据属性在决定两条记录相似性中重要程度的不同，为每个属性分配不同的权重。
（２）重复记录检测。该阶段要解决的问题包括字段匹配问题和记录匹配问题。
（３）数据库级的重复记录聚类。在数据库级应用检测重复记录的算法对整个数据集中的重复记录进行聚类。
（４）冲突处理。根据一定的规则合并或者删除检测出的同一重复记录聚类中的重复记录，只保留其中正确的那条记录。
４．３字段的匹配
字段匹配问题就是来确定两个字段值是否是表示同一个语义实体的句法上的可替换者。如果两个字段表示的是同一个语义，那么这两个字段是等价的。常见的方法有：编辑距离方法、
文本相似度度量方法、基于Ｎ－ｇｒａｍ的字符串匹配方法和
ｃｏｓｉｎｅ相似度方法．本文主要讲述编辑距
离算法。
４．３．１编辑距离的定义
两个字符串ｘ和ｙ之间的编辑距离
ｄ（ｘ，ｙ）定义为：把一个字符串转换成另一
个字符串时在单个字符上所需要的最小编辑操作（比如：插入、删除、代替）的代价数。假设Ａ是一个有限的符号字母表，Ａ＊是Ａ上所有字符串的集合；ε表示空符号，ｘ表示字符串ｘ的长度，ε＝０。编辑操作定义为ａ→ｂ为一个代替操作（如果
ａ＝ｂ，则ａ→ｂ称为一个同一的代替操
作），ａ→ε为一个删除操作，ε→ａ为一个插入操作。代价函数定义是对每个编辑操作指派一个非负实数值的函数。令ｃ（ａ→
ｂ）表示代替操作ａ→ｂ的代价，ｃ（ａ→ε）
表示删除操作ａ→ε的代价，ｃ（ε→ａ）表示插入操作ε→ａ的代价，假设Ｓ＝ｅ１，ｅ２，．．．，ｅｋ为一个编辑操作的序列，它的代价被定义为ｃ（Ｓ）＝
Ｋ
Ｉ＝１
#ｃ（ｅｉ
）：
根据以上定义，两个字符串ｘ和ｙ的编辑距离ｄ（ｘ，ｙ）可被定义为转换ｘ到ｙ所需的最小操作序列的代价数，即：ｄ（ｘ，ｙ）＝
ｍｉｎ｛ｃ（Ｓ）｝其中，Ｓ是一个转换ｘ到ｙ的编辑
操作序列。
课程名章节
知识点
数据结构
线性表
概念线性表是线性结构是
一个数据元素的有序（次序）集
表２记录Ｒ２
课程名章节
知识点
数据结构
线性表
基本概念线性表是由ｎ（ｎ≥０）个类型相同的数据元
素组成的有限序列
图１基于ＸＭＬ的Ｗｅｂ数据清洗框架
表１记录Ｒ１
７６
４．３．２基于编辑距离的字段匹配算法计算编辑距离ｄ（ｘ，ｙ）可以通过动态规划（ＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｇ）ＤＰ的方法来计算。对于有两个字符串ｘ和ｙ，其中ｘ＝ｘ１…ｘｎ；ｙ＝ｙ１…ｙｍ；其编辑距离ｅｄ（ｘ，ｙ）利用下面的递归公式，计算有一个［（ｎ＋１）×（ｍ＋１）］个元素的二位编辑矩阵Ｄ（ｉ，ｊ），
（１）Ｄ（０，０）＝０；
（２）Ｄ（０，ｊ）＝Ｄ（０，ｊ－１）＋Ｃ（ε→ｙｊ）ｊ＝１．．．ｍＤ（ｉ，０）＝Ｄ（ｉ－１，０）＋Ｃ（ｘｉ→ε）ｉ＝１．．．ｎ
（３）Ｄ（ｉ，ｊ）＝ｍｉｎ
Ｄ（ｉ－１，ｊ－１）＋Ｃ（ｘｉ→ｙｉ）Ｄ（ｉ－１，ｊ）＋Ｃ（ｘ
ｉ
→ε）
Ｄ（ｉ，ｊ－１）＋Ｃ（ε→ｙ
ｊ
"
$
$
$$
#
$
$
$$
%
）ｉ＝１．．．ｎ，ｊ＝１．．．ｍ
最后得出编辑距离ｅｄ（ｘ，ｙ）＝Ｄ（ｎ，ｍ）即为两字段的相似度。对如Ｒ１和Ｒ２的中的字段“概念”与“基本概念”的编辑距离ｅｄ＝２，当误差水平为３时，可以认定它们是匹配的。
４．４记录的匹配
记录匹配是以字段匹配位基础的，在利用字段匹配算法比较记录的各对应字段，计算其相似度之后，再进行记录的匹配。一种比较成熟的记录匹配算法Ｐａｉｒ－ｗｉｓｅ比较算法，其思想描述如下：其中δ１定义为两字段相似度的阈值，δ２定义为两记录相似度的阈值。
Ｂｅｇｉｎ
ＲＳｉｍｉｌａ＝０；／／ＲＳｉｍｉｌａ为所计算的Ｒ１，Ｒ２相似度字符串长度web
ＳＷｅｉｇｈｔ＝０；／／Ｗｅｉｇｈｔ为Ｒ１，Ｒ２有效权重之和
ｎ＝ＧｅｔＦｉｅｌｄＮｕｍ（Ｒ１）；／／ｎ为记录的字段数
Ｆｏｒｉ＝１ｔｏｎｄｏ
Ｄｉｓｔ［ｉ］＝ｅｄ（Ｒ１．Ｆｉｅｌｄ［ｉ］，Ｒ２．Ｆｉｅｌｄ［ｉ］）
ＩＦ（Ｄｉｓｔ［ｉ］＞δ１）ＴｈｅｎｒｅｔｕｒｎＦａｌｓｅ；／／如
果Ｒ１，Ｒ２两记录任意字段间的距离大于
δ１，则不为重复记录
Ｅｌｓｅ
ＲＳｉｍｉｌａ＝ＲＳｉｍｉｌａ＋Ｄｉｓｔ［ｉ］＊Ｗｅｉｇｈｔ［ｉ］；
ＳＷｅｉｇｈｔ＝ＳＷｅｉｇｈｔ＋Ｗｅｉｇｈｔ［ｉ］；
ＥｎｄＩＦ
ＥｎｄＦｏｒ
ＲＳｉｍｉｌａ＝ＲＳｉｍｉｌａ／ＳＷｅｉｇｈｔ；；
ＩＦＲＳｉｍｉｌａ＜δ２；／／／如果Ｒ１，Ｒ２两记录
相似度小于δ２，则为重复记录
４．５重复记录的检测
重复记录的检测最简单的方法就是
所有记录之间进行两两比较，以此来确定
有无重复记录，其计算复杂为Ｏ（ｎ２），现在
消除相似重复记录的基本思想是“排序和
合并”。目前比较普遍采用的方法是邻接
排序算法（Ｓｏｒｔｅｄ－ＮｅｉｇｈｂｏｒｈｏｏｄＭｅｔｈｏｄ），
它的基本算法如下：
（１）创建关键字：抽取记录属性相关
的字段，构造记录排序关键字。
（２）排序：用第一步产生的关键字对
数据集进行排序，尽可能使潜在的可能的
重复记录调整到一个邻近区域内。
（３）合并：在排序后的数据集上滑动
一个固定大小的窗口，数据集中每条记录
仅与窗口内的记录进行比较。如果窗口的
大小是ｗ条记录，则每条新进入窗口的记
录与窗口内先前ｗ－１条记录进行匹配比
较，最先进入窗口内的记录滑出窗外，最
后记录的下一条记录进入窗口，直至记录
集的最后。
５实验
笔者选用ｊａｖａ编程语言，ｅｃｌｉｐｓｅ为开
发工具，对网上信息抽取的关于数据结构
的教学知识２０００条记录进行了数据清
洗，取得不错的效果，其中查全率达到
８５％，笔者下一步的计划是对记录匹配过
程中的知识点匹配引入中文分词的方法，
进一步改进算法。
６结束语
当前Ｗｅｂ数据量迅速增长，对Ｗｅｂ
搜索引擎返回的结果进行清洗也是一个
有价值的问题。但是目前的数据清洗都是
建立在关系数据库或数据仓库的基础上
的，随着ＸＭＬ数据处理标准的日臻完善，
如何定义ＸＭＬ文档数据的质量标准以及
如何直接针对ＸＭＬ文档的数据清洗是我
们以后研究的方向。
参考文献：
［１］郭芝懋．数据质量和数据清洗研究综述［Ｊ］．
软件学报，２００２，（１１）．
［２］刘芳数．数据仓库清洗技术讨论［Ｊ］．青海师
范大学学报（自然科学版），２００５，（４）．
［３］邓中国，周奕辛．数据清洗技术研究［Ｊ］．山
东科技大学学报（自然科学版），２００４，（６）．
［４］张永等．数据仓库ＥＴＬ中相似重复记录的检
测方法及应用［Ｊ］．计算机应用，２００６，（４）．
［５］佘春红，许向阳．关系数据库中近似重复记
录的识别［Ｊ］．计算机应用研究，２００３，（９）．
（责任编辑：杜能钢）
ＲｅｓｅａｒｃｈｏｆｔｈｅＷｅｂＤａｔａＣｌｅａｎｉｎｇ
ＬＩＵＨｕａ，ＨＵＹａｎ，ＷＡＮＧＴａｏ
（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７０，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｌｏｎｇｗｉｔｈｔｈｅｔｉｍｅｄｅｖｅｌｏｐｍｅｎｔ，ｍｏｒｅａｎｄｍｏｒｅｄａｔａｏｒｉｇｉｎａｔｅｓｆｒｏｍｔｈｅｎｅｔｗｏｒｋ．ＢｕｔａｓａｒｅｓｕｌｔｏｆｔｈｅＷｅｂ
ｄａｔａｃｈａｒａｃｔｅｒｉｓｔｉｃ，ｔｈｅｉｎｆｏｒｍａｔｉｏｎｅｘｔｒａｃｔｅｄｆｒｏｍｔｈｅｎｅｔｈａｓｔｈｅｐｒｏｂｌｅｍｏｆ“ｄｉｒｔｙｄａｔａ”，ａｎｄｃａｎｕｓｅｎｏｔｄｉｒｅｃｔｌｙ，ｓｏｉｔ
ｉｓｎｅｃｅｓｓａｒｙｔｏｃａｒｒｙｏｎｔｈｅｄａｔａｃｌｅａｎｉｎｇ，ｅｌｉｍｉｎａｔｅｓｔｈｅｄｉｒｔｙｄａｔａ，ａｎｄｕｓｅｄａｔａｄｉｒｅｃｔｌｙ．
ＫｅｙＷｏｒｄｓ：ｗｅｂｄａｔａ；ｄａｔａｃｌｅａｎｉｎｇ；ａｐｐｒｏｘｉｍａｔｅｌｙｄｕｐｌｉｃａｔｅｄｒｅｃｏｒｄｓ
７７
软件导刊·２００７·２月号

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。