（计算机应用技术专业论文）提高数据质量的若干关键技术研究.pdf

论文摘要 数据质最是保证数据能够有效地发挥作用的关键。数据质量的保证贳穿于数据的整个生 命周期，它是一个系统过程，是一个质量评估分析和各种数据清洗方法相结合的不断反复的 过程。本研究在e t l ( e x t r a c t , t r a n s f o r m ，l o a d ) 系统开发和研究的基础上，提出了一个迭代式 的数据质链提高框架，井对涉及到的若干关键技术进行了深入探索，主要有以下内容： ( 1 ) 数据质鼍评估：研究了如何有效地评估数据质量的问题，提出数据质量是一个背景 依赖的问题，不同数据源的数据可以在一定背景范围内相互比较确定一个量化比较的标准； 另一方面，通过衡单数据传达的信息量多少对数据质鼍中若干重要维度进行量化，从而为如 何有效地、客观地评估数据质昔提供了一条新的途径。 ( 2 ) 数据规格化：研究了如何实现数据规格化的问题，提出采用基丁：特征的马尔可夫模 埤i 解决特定戍州的数据规格化问题，它能够充分地利用数据中的重替特征，综合数据中的统 计规律和特征来实现数据的规格化，具有盘了的推。应瑁前景。 ( 3 ) 结构化数据重复对象识别：研究了关系数据序数据的重复记录识别问题，提出一种 基于q - g r a m ( g 个近续字符组成的子字符串) 层次空间的聚类识别算法。这种方法不仅能避免 火量外排序引起的高频度的i o 操作，而且根据q - g r a m 层次空间固有的分辨率层次通过逐 步细化聚类米识别相似重复记录，可以克服排序不能保证将相似记录排在邻近位置的缺陷， 能取得更好的精度。 ( 4 ) x m l 文档中重复元素识别：研究了x m l 格式的重复数据元素的特点，提出对于特 定应用领域，在具体的上下文环境中学习x m l 重复元素的识别规则。通过结构转换，将结 构不尽相同的x m l 数据映射成结构一致的数据，并通过学习不同层次数据元素间的依赖关 系权重米获得匹配规则。晟后根据学习得到的转换和匹配规则，给出了一种有效的重复x m l 元素检测算法。 关键字：数据质攀，数据清洗，q - g r a m ，重复记录，马尔可夫模型，聚类，x m l a b s t r a c t d a t aq u a i l t yi st h em a i nf a c t o rt h a td m e r m i n e sw h e t h e ra ni n f o r m a t i o ns y s t e mm a yp l a yi t sr o l e q u a l i t ym a i n t e n a n c ea n di m p r o v e m e n ti sa l o n gw i t ht h el i f ec y c l eo fd a t a d a t aq u a l i t yi sa s y s t e m a t i ce n g i n e e r i n g ，w h i c hi s a l li t e r a t i v e p r o c e s sc o m b i n gq u a l i t ye v a l u a t i o na n dd a t a c l e a n s i n g o u rr e s e a r c hi sm o t i v a t e db yo u re t l ( e x t r a c t ，t r a n s f o r ma n dl o a d ) s u i r ed e v e l o p m e n t p r o j e c t a ni 钯m w eq u a f f t ye n g i n e e r i n gf r a m e w o r ki sp r o p o s e da n dw i t h i nt h i sf r a m e w o r kw e f o c u so ns o m ek e yt e c h n o l o g i e si n v o l v e d ( 1 ) d a t aq u a l i t ye v a l u t a t i o n ：w ep r o p o s et h a td a t aq u a l i t yc a l lb ee f f e c t i v e l ye v a l u a t e dw i t h i na n a v a i l a b l ec o n t e x t f o re x a m p l e ，i nc o o p e r a t i v ei n f o r m a t i o ns y s t e m ( c l s ) e n v i r o n m e n tq u a l i t y o fe a c hi n d i v i d u a ld a t ac a nb e u n i q u e l y e v a l u t e da g a i n s ta l lr e l a t e dd a t a w i t h i nt h i s f r a m e w o r kq u a l i t yi si n t e r p r e t e d t h ed e g r e et ow h i c hi n f o r m a t i o ni sc o n v e y e db yd a t a b y b o r r o w i n ge n t r o p yc o n c e p tf r o mi n f o r m a t i o nt h e o r y , an e wa p p r o a c hi sg i v e nt oe s t i m a t et h e t w om o s ti m p o r t a n td a t aq u a l i t yd i m e n s i o n s ：a c c u r a c ya n dc o m p l e t e n e s s t h u s ，d a t aq u a l i t y c a nb eq u a n t i f i e do b j e c t i v e l y ( d a t as t a n d a r d i z a t i o n ：af e a t u r e b a s e dm a r k o vm o d e li sp r o p o s e df o rd a t as t a n d a r d i z a t i o n t h i sa p p r o a c he x p l o i t e so v e r l a p p e df e a t u r e st oi d e n t i f yc o r r e s p o n d i n gs t a t eo fd a t ai t e m s o u r m o d e lm a yt a k ea d v a n t a g eo fb o t hs t a t i s t i c a la n df e a t u r ep r o p e r t i e so fd a t aa n di ti sa p r o m i s i n gw a yf o r d a t as t a n d a r d i z a t i o n ( 3 ) d e d u p l i c a t i o nf o rr e l a t i o n a ld a t a ：a ne f f i c i e n tm e t h o df o rd e t e c t i n gs i m i l a rd u p l i c a t er e c o r d s o fr e l a t i o n a ld a t ai s p r e s e n t e d ：ah i e r a r c h yq - g r a ms p a c ei sp u tf o r w a r d t h e n ，t a k i n g a d v a n t a g eo f t h ei n h e r e n th i e r a r c h yp r o p e r t yo f q g r a ms p a c ea l lt h es i m i l a rd u p l i c a t er e c o r d s w i l lb ed e t e c t e db yh i e r a r c h i c a lc l u s t e r i n g o no n eh a n d ，i tc a ng r e a t l yr e d u c ee x p e n s i v ed i s k 1 ( 3c o s tb ya v o i d i n ge x t e r n a ls o r t i n g o nt h eo t h e rh a n d ，i to v e r c o m e st h es h o r t c o m i n go f s o r t & m e r g e t h a tt h es i m i l a rd u p l i c a t er e c o r d sm a yf a l lf a rf r o me a c ho t h e r , t h e r e b ys i m i l a r d u p l i c a t er e c o r d sc a l l tb ef o u n di nt h es u c c e e d i n gm e r g ep h a s e s o ，o u ra p p r o a c hw i l l p e r f o r mw e l l ( 4 ) d e d u p l i c a t i o nf o rx m ld a t a ：b ys t u d y i n gc h a r a c t e r i s t i c so fd u p l i c a t ex m ld a t a , w ep r o p o s e t h a tf o ra s p e c i f i ca p p l i c a t i o n , a c t i v e m a c h i n el e a r n i n gm e t h o di s a p p l i e d t og l e a n t r a n s f o r m a t i o nr u l e sa n dm a t c h i n gr o l e st o a c c u r a t e l yi d e n t i d u p l i c a t ex m le l e m e n t s t r a n s f o m a r i o nr o l e sa r eu s e dt oe l i m i n a t et h es t r u c t u r a ld i v e r s i t i e sa m o n ge l e m e n t sa n d m a t c h i n gr u l e sa r eu s e dt oi d e n t i f yt h er e l a t i o n s h i p sb e t w e e np a r e n ta n dc h i l dn o d e s i nt o m ， d u r i n gt h e d e t e c t i o np h a s ea ne f f i c i e n ta l g o r i t h mi s p r o p o s e d t or e d u c e c o m p u t a t i o n a l c o m p l e x i t y k e y w o r d s ：d a t aq u a l i t y , d a t ac l e a n s i n g , q - g r a m ，d u p l i c a t er e c o r d ，m a r k o vm o d e l ，h i e r a r c h i c a l c l u s t e r i n g , x m l 表2 一l 企业信息示例( 地税局) 表2 2 企业信息示例( 国税局) 表2 3 企业信息示例( f 商局) 表2 4 不同数据集中属性映射关系 表2 - - 5 熵著计算结果 表2 6 属性的完整性 表3 一1 日期时间数据示例 表3 2 文献引j j 示例 表3 3 日期时间数据特征示例 表3 4 日期时间数据上精度比较 表3 5 文献引_ i j 数据特祉示例 表3 6 文献引州数据上精度比较 表4 1 q - g r a m 方法示例数据 表索引 n 也：j n蠊d加加”勰勰勰 t a b i el n d e x t a b2 - 1c o m p a n yi n f o r m a t i o ne x a m p l e ( 1 0 c a lt a xb u r e a u ) t a b2 - 2c o m p a n yi n f o r m a t i o ne x a m p l e ( s t a t et a xb u r e a u ) t a b2 - 3c o m p a n yi n f o r m a t i o ne x a m p l e ( b u s i n e s sb u r e a u ) t a b2 - 4a t t r i b u t em a p p i n g sa m o n gd i f f e r e n td a t as e t s t a b2 - 5e n t r o p yd i f f e r e n c e t a b2 - 6c o m p l e t e n e s so f a t t r i b u t e s t a b3 - 1e x a m p l eo f d a t ea n dt i m e s t a m pd a t a t a b 3 - 2b i b l i o g r a h i ci n s t a n c e t a b3 - 3e x a m p l eo f t i m e s t a m pd a t a f e a t u r e s t a b3 - 4a c c u r a c yc o m p a r i s o no nd a t ed a t a t a b3 - 5i n s t a n c eo f f e a t u r e sf o rb i b l i g r a p h i cd a t a t a b3 - 6a c c u r a c yc o m p a r i s o n0 1 1b i b l i o g r a p h i cd a t a t a b4 - 1e x a m p l ed a t a n 心：j n n拇加加嚣勰勰勰 图索引 图卜一1 数据生命周期中的质晕维护活动 图1 - - 2x m l 重复元素示例 图2 - - 1 数据质颦评估体系图 图2 - - 2 数据和实体对应关系 图2 3 一个应用域模型示例 图3 1 日期时间元素层次关系 图3 2 样本学习效果( 5 0 0 ) 图3 3 样本学习效果( 3 0 0 0 ) 图4 - - 1 数据源1 数据k 度分布 幽4 2 数据源2 数据长度分布 图4 - - 3 与m e r g e p u r g e 方法精度比较 图4 - - 4 与m e r g e p u r g e 方法精度比较 图5 1 x m l 重复元素示例 图5 - - 2 x m l 清洗过程 图5 3 描述b o o k 的d t d 图5 4 测试集1 的学习效果 图5 5 测试集4 的学习效果 图5 6 哈婀过滤效果比较 6 ，m n n毖”凹勰勰鼻；钟铊盼钾秒钟 f i g u r ei n d e x 6 91 - id a t aq u a l i t ya c t i v i t i e sd u r i n gd a t al i f ec y c l e f i g1 2d u p l i c a t i o no f x m l e l e m e n t 堍2 - 1d a t aq u a i l t yd i m e n s i o n s f i g2 - 2d a t aa n de n t i t yr e l a t i o n s h i p s f i g2 - 3a ne x a m p l eo f a p p l i c a t i o nm o d e l 堍3 - id a t ea n dt i m e s t a m pd a t ah i e r a r c b y f i g3 - 2a c c u r a c yv s t r a i n i n gi n s t a n c es i z e ( 5 0 0 ) f i g3 - 3a c c u r a c yv s t r a i n i n gi n s t a n c es i z e ( 3 0 0 0 ) f i g4 - 1d a t al e n g t hd i s t r i h u t i o no f d a t a s o u r c e1 f i g4 - 2d a t al e n g t hd i s t r i b u t i o no f d a t as o u r c e2 f i g4 - 3a c c u r a c yc o m a r i s o nw i t hm e r g e p u r g e f i g4 - 4t i m ec o m p a r i s o nw i t hm e r g e ，p u r g e 堍5 - ix m ld u p l i c a t ee l e m e n te x a m p l e f i g5 - 2x m l c l e a np r o c e s s f i g5 3d t d f o rb o o ke l e m e n t f i g5 - 4t r a i n i n ga c c u r a c yo f d a t as e t l f j g5 5t r a i n i n ga c c u r a c yo f d a t as e t4 f i g5 - 6h a s hf i l t e r i n ge f f b c t 0 7 m n n托”勰勰势昌；蛐舵的婀盼轴 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：日期： 第一章绪论 1 1 研究背景 第一章绪论 随着信息处理技术的不断发展以及数据库管理系统( d a t a b a s em a n a g e m e n ts y s t e m ， d b m s ) 的广泛席并i ，各行各业已建立了很多不同的计算机信息系统，积累了大晕的数据。 为了使数据能够有效地支持组织的日常运作和决策，要求数据可靠无误，能够准确地反映现 实世界的状况。数据是信息的载体，因此好的数据质量是各种数据分析如0 l a p 分析、数据 挖掘等能够得到有意义结果的基本条件。人彳f 常常抱怨所谓的“数据丰富，信息贫乏”，其 中个原因是缺乏有效的数据分析技术，而另一个重要的原因则是数据质餐不高，如数据残 缺不全、数据不一致、数据重复等，导致数据不能有效地被利用。如果数据不能对客观世界 如实地反映，建立在其上的分析结果也将是没有意义的，甚至会产生误导。2 0 0 2 年数据仓 库研究机构d a t a f l u x 提供的一份统计报告显示美国每年由于数据质量问题导致的商业损失 达6 0 亿美元。数据挖掘的实践和研究表明，数据分析活动约3 0 到8 0 的时间花费在保证 数据质颦上。可见数据质越问题是信息系统面临的一个基本问题。 组织中的数据通常分成不同的层次，数据质鼍问题在各个层次都会出现，并且越高层次 的数据，数据质擘问题往往越突出。我f j 以企业信息系统为例，简单回顾一下不同层次上的 数据质母问题。一个典犁的企业环境下，数据可以被划分成操作层数据和分析层数据。不同 层次数据对麻不同类型的应用，而各个层次数据质龋问题引起的后果也具有不同的严重程 度。操什层数据是日常例行的事务数据，支持日常的业务运行和管理，这个层次的数据质阜 问题主要表现为个别事州描述上的差异，只影响局部，不会影响全局。而面向分析的数据通 常是不同粒度的汇总数据，都是从操作层数据汇总获得的，许多个体数据的问题在汇总数据 时就会集中显现出来，要么就根本无法汇总，要么犯总出米的数据存在重人偏著变得毫无意 义。可见，数据质量问题伴随组织数据量的增长和信息化群度的逐步加深会日盏凸现。 例如，某地税局在长期的数据利用过稃中数据质晕问题逐渐暴露出来。在最初几年，数 据主要是为了支持日常的业务奇询，例如税款征收、稽查等，这个时期数据质量问题主要表 现为个别用户的记录出错。在这个阶段数据质簟问题尚未引起足够的重视，也没有采取具体 的解决措施。后来数据草积累到一定规模后，在建设决策支持系统的过稃中，发现分析数据 的时候经常出现问题，人们才逐渐意识到数据质量问题很重要的。地税局面临的几个比较典 犁的数据质鼍问题简述如f ： ( 1 ) 为了满足数据分析的需要，地税局和国税局要进行数据共享，共享时面临的一个 基本问题是同一纳税人记录的识别。如果不进行重复记录的剔除，则共享数据中不仅会有大 量冗余，且会引起许多不一致。 ( 2 ) 由丁j 数据中经常存在错误或缺失值，导致或者无法汇总结果或者汇总的结果经常 出现抵触。 ( 3 ) 地税局的数据质苗的蚶坏没有一个可行而具体的评估方法，缺乏对数据质量状况 的晕化把握。 ( 4 ) 对丁如何有效地保证和提高数据质域缺乏系统的方案。 东南丈学博十学位论文 我们应当看到，地税局面临的数据质晕问题，是具有普遍性的，各个不同的组织都会面 临各种各样的数据质鼙问题。因此数据质量问题的研究具有理论意义和现实意义。 数据质茸尽管与信息系统息息相关但对它的研究尚没有引起足够的重视。它在以下几 个方面亟待进一步探索： ( i ) 数据质草问题在不同的应朋中采用不同的技术方案来解决，目前人f j 对数据质量问 题的认识往往停留在针对具体问题的解决方案，而缺乏一套系统的分析解决思路，导致数据 质鼍问题的解决往往采取事后补救式，缺乏完档的监控和提高机制。 ( 2 ) 数据质管评估是解决数据质鼍问题时必须面对的问题，对此人们尚缺乏有效的评估 机制。 ( 3 ) 在多年的研究和实践中，人们对一个具体的数据质茸问题积累了一些解决方法，但 许多方法的有效性和效果尚待改进。 1 2 研究现状 一般认为【o l 9 3 i ，数据质量主要指一个信息系统在多大程度上实现了模式( s c h e m a ) 和数 据实例( i n s t a n c e ) 的一致性，及模式和数据实例在多大程度上实现了正确性( c o r r e c t n e s s ) 、一 致性( c o n s i s t e n c y ) 、完帮性( c o m p l e t e n e s s ) 和最小性( m i n i m a l i t y ) 。数据质最的管理主要 包括数据质晕评估和监控、数据清洗活动。数据质越的研究大致也是围绕这两个方面展开的。 数据质蕈评估和监控是解决数据质餐问题的个源头性问题，主要研究如何具体评估数 据质晕的好坏 e c s 0 4 1 7 ”6 j 【”1 1 w 0 4 】 a 1 9 6 t a s ”0 2 1 以及如何有效地发现数据质量问题 d u d 3 l r r 0 2 l l r r ”。其中数据质鬣评估主要采用专家评估的方法 c c b 0 4 y r 9 6 i w 0 3 w 0 4 j ，这是目前 数据质荤评估方法的土流。 数据清洗研究的是提高数据质晕的具体技术手段，它的研究土要集中住以f 四个方面 1 、重复对象的识别问题 现实付界中的实体在不同的数据源中常常有多个表达，在数据集成的时候经常要判断不 同数据源中的表达是否代表现实世界中的同一实体“”“”1 ，它是数据质量问题研究 的一个重要方面。这类问题主要集中于采用数据库和人r 智能的方法自动化地解决 “1 1 。它的研究历史由来以久，主要分成两大类：一类是确定性的方法“”1 ，一类是 基丁概率的方法。目前对这个问题的研究仍方兴未艾”。 2 、异常数据的识别和纠上e 数据中的异常一般是由两种原阅造成的，其一是由于系统本身的固有因素造成的，另外 一种状况则可能是由丁二脏数据“”1 造成。在分析数据质量问题时，必须对异常数据进 行芙注，并尽可能自动化地发现异常。数据概化( d a t a p r o f i l i n g ) 、数据审计( d a t a a u d i t i n g ) 是解决这类问题的思路。这类方法一般首先采_ l f j 数理统计的方法对数据的分布进行概化 ( p r o f i l i n g ) ，然后针对某一特定的数据质晕问题进行挖掘，如用关联规则挖掘的方法发现 数据异常”“。 3 、缺火数据的处理( m i s s i n gv a l u e ，m i s s i n gd a t a ) 由于各种各样的原因，实际的数据集中经常会存在缺失数据，常常会对分析结果有很大 2 第一章绪论 的影响。“。如何尽可能合理地将缺失数据填补是一个重要的问题。 4 、数据阃的逻辑关系 实际的信息系统都是面向某一个应用领域的，对于一个具体的应用如何采用自动化的方 法来解决数据中不符合业务逻辑的错误是一个有实际虑用价值的问题“。这类问题 是数据编辑修正( e d i t i n ga n di m p u t a t i o n ) 所研究的主要内容，其思路是根据应用依赖的 领域知识建立规则体系来自动处理。 我们虑当看到。数据质鼍的研究尽管在许多方面积累了许多成果。但在数据质鼍评估以 及某些具体的数据清洗技术方面仍有许多问题有待于进一步探索。下面对数据质_ 耸研究所涉 及的若干关键问题加以综述。 1 2 1 数据质量评估 数据质晕评估是数据质晕研究中一个源头性的问题1 ，如何客观有效地评估数据质晕一 直是业界所关注的问题，但这方面仍没有统一的认识。目前数据质量评估主要有两类策略： 一类是定性的策略，一类是定最的策略，下面分别叙述。 定性的策略是目前数据质颦评估的主流，定性的策略主要有两种方法：一种是将数据质 量分解为各个维度“1 ”“”，如准确性、完移性、一致性、最小性、适时性等，从 各个维度的角度对数据质鼍进行分析；另外一种认为数据质晕评估必须依赖于具体的应用。 数据质晕定义为数据满足用户特定需求的程度一1 。但这两种评估方法都主要依靠专家评估 对数据质簟进行评级，缺乏定晕的分析，具有很大的主观性。 定量的策略主要集中在对关系数据序数据的质量评估。文献 a s v 9 9 1 【a s v 0 2 】【a 1 9 6 等提 出了对关系数据库数据进行量化的质量评估方法，这些评估方法或者假定有一个理想的参照 数据集，或者靠人一r 逐一验证，但这在现实中是很砸实现的。因此，如何有效地、客观地评 估数据质草仍是一个有挑战性的问题。 1 2 2 数据规格化 数据规格化常常是数据清洗的第一个必需步骤，例如文本字段的排序处理、地由卜日期的 格式统一等，它是后续的重复对象识别、缺失值填写的先决条件。目前这一问题主要是采用 人一l 识别或对于特定应用定义规则的方式来处理【”s , h o ! ，例如a u t o s t a n 采用人工定义解析 和转换规则的方法米解决这一问题”，但这类方法豹手工工作蹙很大。如何自动化地实现 数据规格化是值得关注的，如t i m 等首次提出对人名、地卅的规格化采用基r 字典的隐马 尔可夫模型米处理【t p k 0 2 ，这种方法的主要不足在于它是一种统计模萼! ! ，而数据特征如拼写 格式、上下文特征、数据长度等对状态的决定作用在这种模型中得不刽体现，有待于进一步 改进。 1 2 3 结构化数据的重复对象识别 诰法上相同绒相似的不同记录可能代表现实世界中的同一实体，因此结构化数据的相似 重复记录识躺是数据清洗研究中的一个重要问题。目前相似重复记录识别主要有四类方法： 排序& 合升的方法【m 5 9 5 a c 9 ”、建索引的方法【”3 j 【5 ”o ”、机器学习的方法1 5 a 0 a ”3 m 2 w 0 3 ”和 基于特定领域知识的方法i ”1 】【“v 0 2 1 。 东南大学博1 。学位论文 传统的排序合并方法是一种通用的，不依赖丁：特定麻用领域的识别算法：文献 h s 9 5 采用排序合并的方法，根据用户选定的若干个属性字符串作为键进行排序后，采用i 古l 定大 小的滑动窗口进行聚类来识别相似重复记录：文献 a c 9 7 根据不同的属性进行多次排序合 并。并采用优先队列取代吲定人小的滑动窗口来进行聚类。这两种方法对字符串外排序引起 的高频度的i 0 ，是很耗资源的，另外由于字符串排序对字符位置和单词位置太敏感，并不 一定能保证将相似的重复记录放在邻近的位置，导致随后的聚类操作不一定能将相似重复记 录识别出来。 采用r 树建索引的方法“”1 首先依据f a s t m a p 方法“1 选取若干个字符串作为轴 ( p i v o t ) ，各个记录依据这若干个轴计算它在多维空间中的坐标，然后采用r 树进行多维相 似性连接米实现相似重复记录的识别。由于f a s t m a p 方法本身不是可缩的( c o n t r a c t i v e ) i q m - 3 j t 风此这种映射方法会造成大量的“错误丢弃”( f a l s ed i s s i m a l ) ，且由于“维度灾难” ( c u r s eo fd i m e n s i o n a l i t y ) 决定了维度不能过高，使得这种方法不具有通圳性。 文献 s a 0 2 提出采h j 土动学习的方法学习不同属性的相似度函数来识别相似重复记录， 文f t i r i m r w 0 3 m r 0 3 提出通过学习不同类璎的字符串记录的相似性度颦函数平相似度阕值 来提高重复识别的精度。文i 城 w m t 0 1 提出了一种根据特定领域知识建立规则米识别相似 重复记录的框架，这种方法的土要问题在于为了识别相似重复记录，必须建立相应领域的规 则库，对领域知识的要求比较高。 上述四类方法解决相似重复记录的识别各有优缺点，其中排序合并的方法是大家通用的 方法，但其精度和效率都需要进步改进。 1 2 4 半结构化数据的重复对象识别 x m l 数据作为只有代表性的半结构化数据”】，已成为网上数据传输和交换的标准，例 如现在涌现山的人封r s s 数据都是x m l 格式的。当多个不同数据源以x m l 格式米描述现 实，h = 界的实体时，格式和内容不尽相同的元素可能代表现实世界中的同一实体。 相比较于传统的戈系数据席数据，识别层次状的x m l 数据中的重复元素时，要面临着 两个挑战性的问题：其一是结构的多样性【”“l ，不同于具有严格数据模式的关系数据库数据， 同一类删的实体可能采片j 不尽相同结构的元素来描述；另一方面，不同丁：平面关系数据库数 据，层次状的x m l 数据只有复杂的元素和子元素问的依赖关系。这些使得识别重复的x m l 元素成为一个更贝有挑战性的问题。 文献 m f 0 4 中给出了一种在x m l 文档中识别重复x m l 元素的方法，为了解决x t 4 l 元素多 样性的问题，它采刚x q u e r y 语言将具有不同子树结构的x m l 元素变换成统一的结构，并将 同层次的x m l 元素的内容合升为个元素来处理。但这种方法由于混淆了具有不同标签( 元 素名) 的数据进行相似性计算，会损失精度。文献 c j 0 4 提出将具有相似结构的x m l 元素进 行合并的方法。它提出了二类启发式聚类算法米实现相似重复元素的合并：全部比较聚类、 选择比较聚类、m 树聚类方法米实现重复元素的有效合并。其主要不足在于它没有解决x m l 数据结构多样性的问题。与此相关的一个重要的研究问题是x m l 文档的聚类。“。1 ， 但这类研究主要着眼于从树结构的角度判别相似性，没有考虑内容。 归结起来，x m l 数据清洗还有三个方面的问题有待于进一步的探索：( 1 ) 如何有效地处 理结构多样性的问题；( 2 ) 捌l 数据是一种层次状的数据，如何发现复杂的父元素和子元素 间的依赖笑系；( 3 ) 如何有效地降低计算的复杂度。 4 第一章绪论 1 2 5 与业务规则相结合的数据清洗方法 通h j 的数据清洗算法可以应_ j 于各个领域，且如果和某一特定的领域相结合，利用该领 域的知识背景则会取得更好的清洗效果。如生物。”“、制造业、医疗行业1 的数据清洗都 有其各自的特点。总之，任何一种数据鹿_ e j 都有共性和个性这两方面，两方面结合考虑会产 生更加有效的数据清洗算法，这是数据质量研究中应注意的问题。 1 3 研究目标 数据质封的好坏是决定信息系统成败的关键。本文在充分分析数据质量问题的表现以及 影响质颦问题的土要困素的基础上，运用数据库技术以及人- 智能、信息检索的相关理论对 数据质督问题进行深入研究，以期达到以f 目标： ( 1 ) 寻求一种可鼙化的数据质量评估方法，克服常用的专家定性评估所带来的主观性和 随意性。 ( 2 ) 拟从数据本身的特征中寻找数据规格化的解决方案，使方法具有更好的鲁棒性。 ( 3 ) 对丁笑系数据库数据库中火数据鼍的相似重复记录识别，本文力图从避免排序的角 度设计更为高效的算法来解决这类问题。 ( 4 ) 对于半结构化矾l 数据，由丁二结构的多样性和嵌套元素依赖的复杂性导致重复元素 难以识别，本文将探索一种更为有效的识别算法。 1 4 研究框架和内容 在整个数据生命周期中，原有的数据质量问题解决了往往还会发现有新的质量问题，这 图1 一l 数据生命周期中的质鼙维护活动 主要表现为两点：其一是质阜问题的某些“症状”会随着另外一些“症状”的解决而显现： 其二二是随着时间的推移和数据的演化，会有新的数据质蛙问题产生。因此，数据质昔的保证 东南大学博t 学位论文 和提高遵循这样一个过程：数据质最分析一 发现问题一 应用独立清洗一 应用依赖清洗一 数据质草分析。在这个不断反复的过稃中数据中的问题逐步铍发现解决，从而使数据质荤得 剑逐步提高。这个过程周而复始，伴随着数据的整个生命周期。 1 4 1 研究框架 本论文嗣绕数据生命周期中的质颦维护活动来展开相关研究( 如图1 一l 所示) 。数据质 晕的提高过稃是一个系统的过稗，是质簟分析评估和各种清洗活动( 数据规格化、重复检测 处理和其它清洗) 不断反复的过程。本文的1 ：作主要集中在质量分析评估、数据规格化、重 复检测处理部分( 灰体) 。 1 4 2 研究内容 围绕数据生命周期中的质培维护活动，论文r 作主要从以下几个方面展开 l 、数据质餐的茸化评估 目前对数据质阜的评估土要还是采用专家评估的方式，缺少客观罩化的评价方法1 。本 文对于如何量化评估的问题，提出数据质晕评估时的参照应植根于本体的基础上，应当在可 得的( a v a i l a b l e ) 参照数据源中获取被描述的实体对象的“逼近”，用“逼近”来作为数据质 量评估的参照。同时数据质昔决定了数据能够传达的信息茸的多少，冈此采用信息论的相关 方法对数据质最进行营化，这将为数据质量评估提供了一种可行的解决方案。 2 、数据规格化 数据规格化是数据清洗中实施重复数据对象识别、不一致检测、缺失值填充等步骤的先 决条件。例如w e b 数据、文本数据集成时，经常会出现属于不同域( d o m a i n ) 的值缺失或排 序不一致的情况须要处理。例如对于一个地i 卜数据项序列“u s a ，n e wy o r k ，a 3 4 5 ”，要将 其准确划分剑c o u n t r y ，s t a t e ，c i t y ，p o s t c o d e 等荐个不同字段。目前这个问题的解决有手 r 和自动化两种方式，其中自动化的方式主要采_ j 建立一阶隐马尔可夫模型来处理，但这种 模刭只利川数据的统计规律，即通过各个字段间的转换概率和状态一观测概率来确定数据项 序列对应的最人可能的状态序列，从而确定箨个数据项对应的字段。它没有充分利刚数据中 相且重叠的特征1 这种方法的效果并不理想。为此，本文拟提出基于特征的晟大熵马尔 可夫模犁米解决这个问题，以期取得更好的效果。 3 、关系数据库数据库中相似重复记录识别 目前对关系数据库数据进行相似重复记录识别主要采用排序合并的方法1 “1 ，但这种方 法由丁排序时字符位置敏感并不能保证将相似记录字符串排在临近的位置，导致后来的聚类 不能有效地将相似重复记录识别出来。为此针对关系数据库数据，提出一种基于q - g r a m ” 层次空间的聚类检测方法，它首先将数据映射成q - g r a m 空间中的点，并根据q - s t a m 空间中 的分辨率层次采_ j 层次聚类方法将相似的重复记录识别出来。这种方法不仅能取得更高的识 别精度，且避免了大数簟外排序引起i o 代价过大的问题。理论分析和实验表明这是一种解 决大数据草重复记录识别的有效方法。 4 、x m l 重复元素识别方法 x m l 数据中的重复元素识别已成为数据清洗研究中的一个重要问题。它土要面l 临着两个 6 第一章绪论 方面的挑战：一方面是元素结构的多样性，即同一类犁或同一实体在不同的数据源中描述时 可能会采川不尽相同的刍! i 构。如图1 - - 2 所示两个数据源中的两个b o o k 元素就具有不同的予 树结构，但显然它们代表相同的实体。另一方面，嵌套的父元素和子元素问具有复杂的依赖 关系，例如，图卜2 所示的例子中c o m m e n t 元素的值应当更多地是由s p e c i a l i s t 的评价决 定的，而b o o k 元素的相似性判断可能更多地是由t i t l e 元素和la u t h o r s 元素决定的。这种 关系的识别对于重复瑚l 元素的识别具有重要意义。 图1 - - 2x m l 重复元素示例 本文提出对于特定的麻刚领域，可以采用学习转换规则的方法来解决结构多样性的问 题，并自底向上地依次确定各个不同子元素在父元素中的权重以获得匹配规则。这种方法能 够有效地解决结构多样性的问题。 1 5 主要创新点 本文研究l ：什的创新点主要有： ( 1 ) 提出采用被描述对象的完美表达的逼近来作为质晕评估的参照，从而使数据质量的 评估可以鼍化计算；同时论证了数据质量可通过数据所能传达的信息最多少来衡量，并提出 了具体的计算方法。 ( 2 ) 提出基于数据本身的特征建立最大熵马尔可夫模犁实现数据规格化，这种方法能够 充分利_ h j 数据中的数据犄征和统计规律来解决数据规格化问题，具有更好的精度。 ( 3 ) 提出一种在q - g r a m 层次空间中的相似重复记录聚类检测方法。首先阐述了一种 q - g r a m 层次空间的数据模删，然后在q - g r a m 空间中采取凝聚式层次聚类将相似重复记录逐 步识别出来。它能够避免传统的排序合并方法由于对字符位置敏感不能保证将相似记录排 序到邻近何置的不足，取得好的识别精度。同时这种方法可以有效地避免外排序操作引起的 高频度的磁盘i 0 ，在大数据鲑时这种方法只有明显的效率优势。 ( 4 ) 研究了x g l 文档中重复元素的特点，提出采用主动学习的方法获得识别重复元素的 转换规则和匹配规则。前者用来将结构不尽相同的元素结构进行转换，使其结构一致。后者 用来确定父子元素间的依赖关系。利用这种依赖笑系可以准确识别出各个不同叶予元素对根 节点元素的决定群度，从而能有效地解决x m l 元素的重复识别。 7 东南大学博 学位论文 1 6 本文组织结构 本论文中其余各章的内容是这样安排的： 第二章主要介绍了在可得的背景范同内进行数据质母评估的方法。首先介绍了应用域模 型和背景范同的确立，然后采用信息论中熵的概念对若干重要数据质量维度从不同的粒度给 出了具体的封化评估方法。 第三章介绍了基于特征的数据规格化方法。首先，对数据规格化时用到的特征进行提取， 然后给出了基于特征的最人熵马尔可夫模型的学习过程，最后给出了根据学习得到的模型进 行数据规格化的算法。 第四章介绍了种在q - g r a m 层次空间进行相似重复记录识别的方法。首先我们提出了 关系数据序数据记录的建模方法，即将任何一条记录看作q - g r a m 高维空间中的点，并论证 了这个高维空间中具有的分辨率层次。然后采_ i j 凝聚式( a g g l o m e r a t i v e ) 层次聚类算法逐步 将相似重复记录检测出来。 第五章介绍了x m l 数据的重复元素识别方法。针对x m l 元素在清洗时面临结构多样性和 元素间依赖关系复杂的问题，提出对于特定的应用领域采用主动学习的方法来获得转换规则 和匹配规则以精确地识别重复的x m l 元素，弗