（计算机应用技术专业论文）基于dbscan算法的相似重复记录检测方法研究.pdf

哈尔滨工程大学硕士学位论文 摘要 随着信息技术的飞速发展，决策人员在进行决策分析时对各方面信息和 数据的依赖性越来越强，于是在数据库的基础上产生了满足决策分析所需要 的数据环境数据仓库。在构建数据仓库的过程中，其数据源是以异构形态 分布的，这就使得导入数据仓库的数据存在问题，致使应用于数据仓库前端 的决策支持系统的分析结果受到影响，从而影响决策支持系统的服务的质量。 因此，企业数据质量管理正在获得越来越多的关注，数据清洗也正在成为数 据仓库和数据挖掘乃至网络数据处理的一个重要课题，而相似重复记录的检 测是完成数据清洗的关键。 本文首先对数据清洗的知识进行了全面阐述，介绍了数据清洗的概念、 意义和国内外研究现状，并对数据清洗技术的原理、方法、评价标准以及基 本流程进行了分析和总结。在此基础上，论文详细讨论了相似重复记录检测 所用到的相关知识和基本算法，对字段匹配和记录的相似性进行了深入的研 究，并针对各步中存在的问题进行了改进，相似重复记录检测过程中，应用 d b s c a n 聚类算法对数据集中的记录进行聚类，d b s c a n 具有聚类快，抗 噪声能力强，能够发现任意形状簇的优势，但在对记录中的字符型变量转换 为空间中的向量坐标时，用到了字符的a s c i i 码，这样就会把本来不重复的 记录归为一类，而且该聚类的特点，是根据区域的连通性来逐渐聚类，所以 也会把一些记录区别比较大的记录也聚在同一个类中，在这种情形下采用 p a i r - w i s e 比较算法对聚类之后的每个类中的记录进行一次记录比较，以便更 加准确的发现相似重复记录。 用d b s c a n 聚类算法和p a i r - w i s e 算法( 称为改进的算法) 对一个大的 数据集进行测试，结果表明准确率有了一定的提高 在本文的结尾，对所做的工作进行了总结，并提出了下一步的研究重点。 关键词：数据清洗；d b s c a n 聚类；相似重复记录；p a i r - w i s e 哈尔滨工程大学硕士学位论文 a b s t r a c t ， w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e e l a n o l o g y , o r g a n i z a t i o n a l m 锄g e 舟m o 坞a n dm o l ed e p e n do nd a t at om a k et h e i rd c e i s i o m o nt h e f o u n d a t i o no fd a t a b a s et h e r ea p p e a r sd a t aw a r e h o u s ew l a i e l a 啪s i l p p o l td e c i s i o n a n a l y s i s b u td u r i n gt h ee o n s t r u e t i o o fd a t aw a r e h o u s e ，d a t af r o md i f f e r e n td a t a t l o i l i c 器撇i n p u t t e d i n t ot h ed a t aw a r e l a o u , t l a c r cm a yo x i s tm a l a yd a t a q u a l i t a t i v ep r o b l e m ，r c 锄l ti nf a l s ed e c i s i v ea n a l y s i sa n di n f l u e n tq u a l i t yo f i n f o r m a t i o ni 嘲 v j c c t h e r e f o r ee t a p r i s o sm a n a g e m e n tl h 砒i sb a s e do nq u a l i t yi s o b t a i n i n gm o l ea n d i l l o l r ea t t e n t i o n s ow h e ne x t r a c t i n ga l lk i n d so f h e t e r o g e n e o u s d a t at od a t aw a r e h o u s e , a l ld a t ai l o u r c i 强n e e db ec l e a n e d a c c o r d i n gt ot l a c p r o b l e m st h a t g a r b a g ei n , g a r b a g eo u t i nt h ef o r m ( = d e c i s i o ns y s t e m , a n dw i t l a t l a ep u l p o f l et os 1 1 p p o l r tt h em i n i n g , d a t at ob ep i o s s e d 躺s u p p o s e dt ob e r e l i a b l e s ot h a te 玎舳i sa sl i t t l ea l lp o s s i b l e d a t ae l e a n i a gi sb e c o m i n ga l l i m p o r t a n tq u e s t i o no fd a t aw a r e l a o u s ea n dd a t am i n i n ga n dn e td a t ap r o c e s s i n g , d e t e c t i o no f a p p r o x i m a t ed u p l i c a t er e c o r d si sv e r yi m p o r t a n tq u e s t i o n i nt h i sp l p l 盯，a u t h o rd e p l e t e dt l a ek n o w l e d g eo fd a t ac l e a m i n gi nd e t a i l i t i n t r o d u c e dt h ee o n c e r l t , m e a n i n ga n d r r c n t 懿哼砌趾da p p l i c a t i o ns i t u a t i o n h o m ea n da b r o a do fd a t ae l e a m i n g t ts u m m a r i z e da n dd o w n b e dt h et h e o r i e s , m e t h o d s ，e v a l u a t i n gs t a n d a r d sa n db a s i cw o r k f l o wo f d a t ae l c 螂i n & i td i s c u s s e d t h ec o r r e l a t i o nk n o w l e d g ea n da l g o r i t h m s0 1 1t h eb a s i so fa n a l y s i sa n ds u m m a r y d e e p l y , a n di tr e s e a r c h e df i e l dm a t e l a i n ga n dr e c o r d sc o m p a r a b i l i t ya e e p l y a tt l a e s 锄et i m ew eg a v eo l l ra d v a n c e da l g o r i t h m st oi m p r o v et l a el i m i t a t i o no fo r i g i n a l o n e si ne a e l as t e p ，i na l 琅r o x i m a t ed u p l i e a t er e c o r d sd e t e c t i o np r o c e s s ，d b s c a n c l u s t e r i n ga l g o r i t h mi su s e dt oe l u s t 盯r e c o r d si nd a t a s c t , t h i sa l g o r i t h mh a v e 缸 a d v a n t a g eo ff a s td u s t e r , s t r o n g e rt l a ea n t i - o i s ea b i l i t y w l a a ae x c h a n g i n ge l a a r v a r i a n c et os p a c ev e c t o rc o o r d i n a t eb yu s i n ga s c i ic o d c s o n l t ：l e l 咖- d sw h i e l a 躺 n o td u p l i c a t ea 阳c l u s t e r e di n 也es a m ec l a s s a n df o rt l a ec l u s t e r i n ge h a r a e t e r i s t i e , c l u s t e r i n gw i t hr e g i o nc o n n e c t i v i t y , p a i r - w i s ea l g o r i t h mw f l , su s e dt oc o m p a r e r e c o r d st h a th a v eb e e nc l u s t e r e d , t of i n do u tt h ea p p r o x i m a t ed u p l i c a t er e c o r d s 哈尔滨工程大学硕士学位论文 m o r ee x a c t l y d a t a s e ta r et e s t e dw i t ht h i sa d v a n c e da l g o r i t h m ，r e s u l ts h o w st h i sa l g o r i t h m i si m p r o v e di np r e c i s i o n ， a tt h ee n do f t h ep a p e r , a u t h o rs u m m a r i z e dt h er e s e a r c hw o r ka n dp r e s e n t e d t h ee m p h a s e so f n e x tr e s e a r c h k e y w o r d s ：d a t ac l e a n i n g ；d b s c a nc l u s t e r ；, a p p r o x i m a t ed u p l i c a t er e c o i d ； p a i r - w i s e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 ， 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 、 日期：嘶2 t 月巧e t 哈尔滨工程大学硕士学位论文 第1 章绪论 本章简单介绍了数据清洗问题提出的背景，有关数据质量的知识，数据 清洗技术在不同的应用领域中的不同定义，以及国内外数据清洗技术的研究 现状，最后介绍了本文的研究内容和各章节安捧。 1 1 问题的提出 随着数据库技术和信息技术的发展，以及大型信息系统的建立，为了满 足信息需求，人们越来越多的对各异构数据库进行集成、合并，以便形成一 个综合、面向分析的环境，以更好地支持决策分析，从而形成数据中心但 是即使进行了良好的设计和规划，也不能保证在所有情况下，所存放的数据 的质量都能满足要求。用户录入错误、企业合并以及企业环境随着时间的推 移而改变，这些都会影响所存放数据的质量。由于每个数据源都是按特定的 需要建立起来的，所以在把各个的异构的数据库集成到数据中心之前，需要 导入大量的数据，这些数据存在录入错误、数据存在遗漏、数据格式不同和 不完整以及同一对象在不同的数据源中的表示不同等质量问题。根据。进去 的是垃圾，出来的也是垃圾”的原理，错误的数据会导致昂贵的操作费用和 漫长的响应时间，影响从数据集中抽取的模式的正确性和导出规则的准确性， 使得决策支持系统产生错误的分析结果，将会误导决策，影响信息服务的质 量。如在大型的超市系统里，超市要分析客户的来源及不同收入水平的客户 的消费情况，就要对顾客群体进行分析统计，但是客户在填写记录时，大多 数情况下是不认真的，所以导致记录格式等有很大的差异，这样对顾客的分 析必然产生很大的错误，因此要对数据记录进行清洗，消除数据中的错误和 不一致信息，以保证数据的正确性，从而保证决策分析的质量。 下面的应用例子直观地展示了数据清洗的必要性m ： 市场交流：无效的地址或者错误的姓名拼写导致商品目录无法投递或 者向同一客户重复地发送商品居录。 外部数据与内部数据的合并：可能出现产品名称、用户姓名或者地理 i 哈尔滨工程大学硕士学位论文 名词的不匹配。 零售业：在大型的零售药店，一个药品的目录表示为“l o z e n g e ( 止咳 糖) ”，但是“l o z e n g e ”这个词在不同的商品文件中可能有2 0 种不同 的拼写方式 目标市场：客户信息的完整性和正确性是关键。 1 ，2 数据质量问题 1 2 1 数据质量问题的概述 目前学术界对数据质量还没有一个固定的一成不变的定义。许多学者倾 闷于把数据质量视为信息系统中数据视图与实际数据的一致性测度。文献 2 h 形式化的方法定义了数据的一致性( c o n s i s t e n c y ) 、正确性( c o r r v c m c s s ) 、 完整性( c o m p l e t e n e s s ) 和最小性( m i n i m a l i t y ) ，而数据质量被定义为这4 个 抒标在信息系统中得到满足的程度。文献 3 提出了数据工程中数据质量的需 薄分析和模型，认为存在很多候选的数据质量衡量指标，用户应根据应用的 鲟求选择其中一部分，指标分为两类：数据质量指示器和数据质量参数，前 着是客观的信息，比如数据的收集时间、来源等，而后者是主观性的，比如 辩据来源的可信度( c r e d i b i l i t y ) 、数据的及时性( t i m e l i n e s s ) 等。 1 2 2 数据质量问题的分类。 ， 根据处理的是单数据源还是多数据源以及问题出在模式层还是实例层， 墓献 4 将数据质量问题分为4 类( 如图i 1 所示) ：单数据源模式层问题、单 翘据源实例层问题、多数据源模式层问题和多数据源实例层问题。 l l 啦q 叫k y 印曲蛔璐 “ - s i n s k 钟峨曲l 嘣m u l d 蛐雠曲i 瞄 。 s d l 啪l o v d h 础眦l c v d s c 胁a 1 0 ih 蝌a l i 刚 西徽霉产然勰? ， 讲翟嚣篙( o 鲥v 懈一咖m m 抽d k t ，m g 蚶“如掣一m i s s p c l i 盎 “”蛔删a n d i 咖抽) 一u i i - q i h 燃c o r , s w a 娃 一r e d u t l d 柚c y ，d i i p l ；幽- - n m 岫e c e & l i c m- - i t , c o n s i s t e n t a g g r 鳓 一矗螗蛳t 触蛔k 霉哪一。柚f a d 咖v a l t 岱一s a u c m d n n 蛔一i i 啪惜阳n t i l i l i 雌 图1 1 数据质量问题的分类 2 哈尔滨工程大学硕士学位论文 单数据源模式层问题包括：缺少完整性约束，糟糕的模式层设计，唯一 性约束，引用约束；单数据源实铆层问题包括：数据录入错误，拼写错误， 重复记录，属性值互相矛盾；多数据源模式层问题包括：异构的数据模型和 数据模式，命名冲突，结构冲突；多数据源实例层问题包括：数据冗余相互 不一致，不一致汇总，不一致时间点选择。 ， 从图1 1 可以看出，模式有关的问题主要是命名冲突( n a m i n g c o n f l i c t ) 和 结构冲突( s t r u c t u r a lc o n f l i c t ) ，命名冲突主要是同名异义和异名同义，前者 是指同一名称代表不同的对象，后者则相反，即不同的名称代表同一对象。 结构冲突主要是有在不同的数据源中不同的对象表示引起的，例如，类型冲 突、依赖冲突、关键字冲突和动作冲突，糟糕的模式设计、缺少完整性约束 的定义以及多个数据源之间异质的数据模型等，都属于模式层的问题，可以 通过改进模式设计、模式转化和模式集成来解决模式层的问题。除了摸式冲 突，更多的问题与数据本身有关。主要的问题如下：数据不完整，数据不正 确及数据不一致。通常，信息只含有部分冗余，各个数据源可以通过提供关 于实体额外的信息来相互补充。若要获得和现实世界中的实例一致的视图则 就需要清除重复的信息、合并补充的信息，解决这些问题的过程被称为数据 清洗过程。 一 单数据源情形中出现的问题在多数据源的情况下会变得更加严重( 图1 1 对多数据源没有列出在单数据源情形中就已经出现的问题) 。模式层的问题 也会体现在实伪层，实例层的问题在模式层不可见，一些可能的情况有数据 拼写错误、无效的数据值、重复记录等。本文主要考虑实例层的问题，其中 最为重要的就是相似重复记录的检测消除。 检测和消除相似重复记录是数据清洗和提高数据质量要解决的主要问题 之一。所谓相似重复记录是指客观上表示现实世界中同一实体，但由于表述 方式不同或拼写问题而使d b m s 不能识别其为重复的记录。例如，由于输入 错误和表达方式的不同，同一客户在商店两次购物后，该商店的客户表中出 现了两条不同的记录一 周小兰，长宁，上海，中国，2 0 0 0 5 1 和 周小兰，长 宁区，沪，中国，2 0 0 0 5 1 ，而实际上这两条记录表示的是同一个客户。这样 的重复信息可能导致建立错误的数据挖掘模型。 ， 数据清洗过程一般情况下要满足如下几个条件：不论是单数据源还是多 3 哈尔滨工程大学硕士学位论文 数据源，都要检测并且除去数据中所有明显的错误和不一致；尽可能地减小 人工干预和用户的编程工作量，而且要容易扩展到其他数据源。 1 3 数据清洗的研究现状 1 3 1 国外的研究现状 国外对数据清洗技术的研究，最早出现在美国，是从对全美的社会保险 号的错误纠正开始的，美国信息业和商业的发展，刺激了这方面技术的研究 进步。 ( 1 ) 检测并合并消除数据集中的相似重复对象啪，这在数据仓库等大型 的数据集环境下非常重要，这是因为在各个不同组织结构的数据集合并时会 产生的最为常见的情况。消除数据集中的相似重复记录问题是目前数据清洗 领域研究的最多的。为了检测合并相似重复记录，国外的许多研究人员进行 了大量的研究，最为基本的是捧亭合并算法，如j a , o m ，有的研究人员对 记录的相似性匹配方法进行了大量的研究。一些研究人员提出了数据清洗的 模型和语言，在s q l 基础上扩展了新的数据清洗操作，如m e r g e , c l u s t e r 等 6 1 1 f j 嗍，有的框架模型采用了分层抽象的方法，最上层是逻辑层，可以用来定义 数据清洗的流程，不需要关心具体采用的算法，最下面是物理实现层，这一 层根据用户定义的逻辑流程，采用合适的算法和参数，对算法的优化过程也 是在这一层完成的。 ( 2 ) 对数据集进行的异常检测 7 1 。主要用到的方法包括；采用数理统计 的思想来检测数值型属性，计算属性值的均值和标准差，计算每一个属性的 置信区问来识鄹异常属性和记录，采用基于距离的聚类的方法来识剐异常的 记录，采用基于模式的方法来发现不符合数据集中现存模式的异常记录，采 用关联规则的方法来发现数据集中不符合具有高置信度和支持度的规则的异 常数据。 ， ( 3 ) 对缺失数据的清洗，大部分学者采用最近似的值替换缺失值的方法， 包括神经网络、。贝叶斯网络、粗集理论等，这些方法大都需要判断缺失记录 与完整记录之间的记录相似性。 绝大部分相关领域的研究人员认为，要很好的完成数据清洗过程，一定 4 啥尔滨工程大学硕士学位论文 要结合特定应用领域的知识，因此，人们通常将领域知识用规则的形式表示 出来。有研究入员提出专家系统的外壳，以方便规则的表示和荦j 用。在清洗 过程中，需要专家的干预。 1 3 2 国内研究现状 目前国内对于数据清洗技术的研究，还处在一个开始的阶段。尽管在一 些学术期刊和学术会议上也能见到一些有关这方面的文章，但是数量不多。 银行、保险和证券等对客户数据的准确性要求很高的行业，在做自己的客户 数据的清洗工作，都是针对自己的具体应用开发软件，且很少有理论性的文 章公布 在相似重复记录检测方面，复旦大学的周傲英、邱越峰等人，以记录的 n g r a m 值 7 1 作为排序键先对记录进行捧序，然后再利用优先队列进行聚类， 通过把各个记录的n g r a m 值映射到物理记录，再跟优先队列中的记录进行比 较，这样记录的相似度小于某个阈值的就放在一起，这样相似的记录就被聚在 一起。 文献【8 】中提到了非线性k - 均值聚类算法，通过抽取应用相关的特征描 述，应用非线性k 一均值聚类算法对相似重复记录进行聚类。但是该方法对噪 声、孤立点处理能力不强。，4 在文献 9 1 0 l o p 提到了多语言文本的相似重复记录检测，多语言一般包 括中文、英文。对于英文来说，排序多是根据字符在字符集中的次序排列， 而中文存在多种排列，要先建立中文识别的序值文件来解决中文的排列问题。 文献【1 1 】提出了图论中的最小张树方法。利用属性集和属性测度理论， 建立了一种快速的聚类算法，该算法的缺点是当模糊类的数目不明确时以及 模式类之间存在覆盖的情况下，聚类的效果就会变的比较差。 目前市场上的数据清洗软件有商业上的以及各大学和研究机构开发的清 洗软件。商业上的主要有： s a si n s t i t u t e 公司的s a sw a r e h o u s e a d m i n i s t r a t o r h e l p 憋y s t e m s 公司的m a t c h i t d a t aj u n c t i o nc o r p o r a t i o n 公司的d a t aj u n c t i o n s a g c n t 、q m s o r w a r e 公司的m e r g e p u g e l i b r a l l y 5 哈尔滨工程大学硕士学位论文 p l a t i u mt e c h n o l o g y 公司的l n f o r e f i n e r w m p u r el t d 公司的w i n p u r e e d d 公司的d a i a c l e a n s e r 各大学研究机构的数据清洗软件有： 加州b e r k e l e y 大学分校的p o t e r sw h e e la - b c ，一个交互式的清理工 具用c 语言，p e r l 语言提供的宏语言来写转换规则。 新加坡国立大学的h t c l l i c l c a a 。一个基于知识的智能数据清洗工具。 使用了一个j a v a 语言的专家系统外壳。 现在有许多支持数据仓库的e t l 处理，如e x t r a c t ( e t i ) 、 d a t a s t a g e ( i n f o r m i “a r d e n t ) 等，它们大都使用建立在d b m s 上的知识库以 同一的方式来管理所有关于数据源、目标模式、映射等的原数据。模式和数 据通过本地文件和d b m s 网关、o d b c 等标准接口从操作型数据源收取数据。 这些工具提供规则语言和预定义的转换函数来指定映射步骤。他们也提供接 口来支持已有的转换方法，例如外部的c 程序转换过程要么在运行时，有 解释特定转换的引擎执行，要么是通过编译代码来完成。 e t l 工具很少内置数据清洗的功能，但是允许用户通过a p i 指定清洗功 能。通常这些工具没有用数据分析来支持自动探测错误数据和数据不一致。 然而，用户可以通过维护原数据和运用集合函数( s u m , c o u n t , m i l l , m a x 等) 决 定内容的特征等办法来完成这些工作这些工具提供的转换工具库包含了许 多数据转换和清洗所需的函数，例如数据类转变，字符串函数，数学、科学 和统计的函数等。规则语言包含i f - t h e n 并l c a s e 结构来处理例外情况，例如，错 误拼写、缩写，丢失或者含糊的值和越界值。 1 4 数据清洗应用的基本领域 数据清洗在英文中有d a t ac l e a n i n g 、d a t ac l e a n s i n g 等，中文在语言表达 上有三种不同的方式：数据净化、数据清洗、数据清理，由于数据清洗在不 同的应用领域中有不同的要求，对它的定义还没有统一的表述，但是数据清 洗应用最广的领域是数据仓库( 数据中心) ，也就是多个数据源集成之后的一 个大的数据集。 数据清洗一般是应用在几个数据库合并或者多个数据源进行集成时，最 6 哈尔滨工程大学硕士学位论文 初，数据清洗过程应用在数据仓库应用之前，目的是为了提高数据的质量， 这样后继的数据挖掘应用才可能得到正确的结果，决策支持系统才能够辅助 管理者作出正确的决策。通常表示同一个实体的记录在不同的数据源中以不 同的格式表示或被错误的表示，这样在合并后的数据库中就会出现相似重复 的记录。在这种情况下，数据清洗目的就是要把这些重复的记录识别出来并 消除它们。在不同的文献中出现这样的过程大部分描述为：记录连接( r c x 斌d l i n k a g e ) 、实例识别或者对象识别问题。其中在文献 1 2 1 中提到，数据清洗并 不仅是简单地用好的数据去更新记录，彻底的数据清洗需要对数据进行分解 和重新组合，文献中给出了一个客户的地址进行清洗的过程的实例，其中把 数据清洗过程分为6 个步骤：元素化、标准化、校验、匹配、是否是同一人 和文档化文献【1 3 】中提到，数据清洗是指消除数据中的错误和不一致，并 解决对象识别闯题的过程。文献【1 4 】中把合并清除问题定义为数据清洗问 题，并提到了基本的排序近邻方法文献 1 5 1 d p 把数据清洗定义为一种使用 计算机化的方法来检查数据库，检测丢失的和不正确的数据并纠正错误的过 程。 1 5 本文的工作和内容组织 数据清洗涉及的问题比较多，并且涉及很多不同的处理策略和技术，本 论文主要集中讨论数据清洗中的相似重复记录的检测方法，包括已经存在的 方法和自己在该方面的一些见解。 第l 章介绍了数据清洗问题提出的背景，有关数据质量的基本知识，数 据清洗技术在数据仓库应用领域中的不同定义，以及国内外数据清洗技术的 研究现状，最后介绍了本文的研究内容和各章节安捧。 第2 章介绍了检测相似重复记录之前的简单处理工作以及两个记录之间 进行记录匹配的知识，目前用的比较多的匹配方法以及数据清洗的一些基本 方法，主要是谈到目前在处理检测相似重复记录时用到的一些方法和相似度 度量方法，并简单介绍了清洗效果的评价标准。 第3 章简单介绍了目前聚类方法的主要分类和每个划分下比较经典的聚 类算法，以及聚类之前的数据准备工作，着重讨论了d b s c a n 聚类算法的理 论实质。在本章的最后用伪码给出了该算法的过程实现。 7 哈尔滨工程大学硕士学位论文 第4 章介绍了d b s c a n 算法在相似重复记录检测中存在的一些问题和 p a i r - w i s e 比较算法，该算法针对d b s c a n 算法聚类之后存在的一些小的问 题，对问题的进一步处理，改进了由于字符的交换而造成的聚类错误，提高 相似重复记录的检测精度。 第5 章介绍了相似重复记录检测的实现过程，包括数据结构的需求分析 和定义，与数据库的底层连接和数据交换。详细的介绍了d b s c a n 聚类过程 实现，接着给出了一个用该算法实现的简单数据集的聚类图。最后结合 p a i r - w i s e 算法实现了相似重复记录的检测，并通过实验验证该方法的可行性， 该算法中用到的思想是分步处理的思想。 在最后，对本论文的工作给出了总结，并提出了下一步研究的重点 8 哈尔滨工程大学硕士学位论文 第2 章数据清洗中相似重复记录知识 本章主要介绍了相似重复记录的基本知识，首先介绍了相似重复记录的 基本类型，记录的匹配知识，接着简单介绍了检测相似重复记录的一些算法。 最后给出了清洗结果的评价标准。 2 。1 相似重复记录概述 同一个现实实体在数据集合中用多条不完全相同的记录来表示，由于它 们在格式、拼写上的差异导致数据库管理系统不能正确识别，这些记录称作 “相似重复记录”，在前面的章节中已经提到，相似重复记录是一种常见的 多记录型脏数据。这种状况造成了以下问题： ( 1 ) 损害信息的一致性：相似重复记录的信息可能互为补充，但存在冗 余，甚至互相矛盾。当现实世界中的某个实体发生状态改变时，可能这些相 似重复记录中的某个代表记录会发生改变，而其余的记录往往得不到同步更 新，这样会更进一步损害信息的一致性。 ( 2 ) 资源浪费：相似重复记录不仅会造成数据库中的数据冗余，浪费存 储空间，更可能的是会造成数据挖掘的严重偏差，而做出错误的决策。例如， 超市为了维持良好的客户关系，经常会邮寄给客户许多促销资料，如果信息 系统中的客户数据存在相似重复记录，则有些资料会找不到收信人，而有些 客户会因此收到多份重复资料。 解决相似重复记录问题就是要对数据集合中的记录作对象识别，即根据 记录所包含的各种描述信息来确定与之相对应的现实实体。如果数据记录具 有这样的属性集( 或者属性) 。它总能够惟一标识一个现实实体，这时只要对 两个记录集在该属性集上作等值连接，兢可以完成对象识别过程。如果不存 在这样的键属性集，而且数据中可能还存在各种各样的错误时，精确的记录 匹配算法就没有太多意义，因此必须引入记录的相似匹配技术，并且结合记 录的语义信息来提高匹配的精度，这也是许多研究者将数据集成中相似重复 记录的解决过程称作语义数据集成的主要原因。 9 哈尔滨工程大学硕士学位论文 现在来看一下数据中经常存在的情形脚，见表2 1 。 对于第1 种情形，由于在数据输入时不知道电话号码字段的具体值，所 表2 1 实例层上数据质量的典型例子 问题 脏数据原因 缺少值 p h o n e 一9 9 9 9 9 9 9 9 9 9 9 9 数据录入时，未提供 拼写错误 c i t y = b e i p i n 录入时引入的错误 不同的缩写e x p c d c n c e = b , o c c u p a t i o n = d b 自由格式字符串 n a m c = j s m i t h b e i j i n g ” 单一字符多种值 值与字段名不符c i t y = c h i n a 字段值不对应 c i t y = z h u c h c n g , z i p = 2 1 2 2 0 0 城市与邮编不对应 词移位 n a m e l = j s m i 血 , n a m e 2 = m i l l e ， 字段无固定格式 相似重复记录r l = ( n a m c = 3 0 h ns m m - r )两记录同一个实体 r 2 - - ( n a m c = j s m i t h ) 矛盾的记录r l = ( n a m e = ：”j o h ns m i t h , b i t = 1 2 1 1 7 9 )同一实体但属性有 r 2 - - ( n a m e = j s m r r h jb i t = - 1 2 1 2 7 9 )个不同的值 错误的记录 e m p = ( n a m e = j o h ns m i t h j g = b e i j i n g ) j s m i t h 不在北京 以该记录中存在一个无效值针对这种情形，定义一个规则存放在数据清洗 库中，就能够根据这条规则判断出哪些是无效值。一 第2 种情形出现了拼写错误，需要在清洗库中建立一个存放所有城市名 的查找表，通过与该表中的城市名相比较，就可以判断出数据库中存放的是 哪个城市。 对于第3 种情况，一般也需要利用外部的查找表才能检测出来并加以改 正。在数据清洗工具中，一些典型的查找表应该是内建的，此外也应该具备 可扩展性，允许用户加入新的查找表。 对于第4 种情形，在一个自由格式的文本类型的字段里包括了很多部分， 每个部分都可以单独作为一个字段。如果每个部分的先后顺序一定，且互相 之间有分隔符或者保留字，比如s u e c t 、r o a d 等等，就比较容易处理。但是， 实际中的情况往往不是这样，因此要通过机器学习或者其他办法来解决，由 领域专家选定学习样本( 相对于所要处理的数据集，样本数量少得多) 来训练 1 0 哈尔滨工程大学硕士学位论文 该系统，等训练好了以后，再由系统自动处理大规模的数据集。由于采用机 器学习的办法，因此一般来说，需要折衷考虑记忆率和准确率。 第6 种情形的问题是字段之间不相对应，为了改正，需要知道哪些字段更 可信，这必须利用其他信息才能决定第8 种和第9 种情形表示的是相似重复 记录的情形。在第8 种情形里，一个记录的n a m e 没有简写，而另一个记录的 n a m e 被简写了，通过定义合适的编辑距离函数，或者内建常用的缩写规则， 情洗工具可以检测出这类重复记录。在第9 种情形中，同一个现实实体( 两个” 记录的n a m e 值相同) ，但是两个记录的b o a t e 值不一样，在合并这两条记录时， 如何选择一个合适的b d 蹴值，是一个棘手的问题。相似重复记录的匹配和合 并，是数据清洗过程中一个很重要的问题。总得来说，选择一个好的距离函 数是非常重要的。 2 2 记录的匹配知识 ， 消除相似重复的记录可以针对多个数据集或者一个合并后的数据集。在 本文中用到的数据集就是合并之后的数据集。在r r 最为发达的北美，信息重 复对数据质量的影响平均要达到6 3 ，最高要达到2 2 5 。数据仓库中的重 复记录就更为常见，所以如何检测和合并相似重复检测是数据清洗相关研究 中的一项重要课题。消除重复记录的基本方法是挥序、匹配与合并，匹配算 法的核心是字段匹配。首先，器要识别出标识同一个现实实体的相似重复记 录，即记录匹配过程。判定记录是否重复是通过比较记录对应的字符串之间 的相似度来决定记录是否表示现实世界中的同一实体。与领域无关的记录匹 配方法是利用记录间的相似度来判定两条记录是否相似。如果两条记录的相 似度大于某个预先设定的阈值，那么就判定这两条记录为重复，反之就不是“- m 。无论将整条记录看作一个字符串计算它们之间的相似度，还是独立计算 记录的字段之间的相似度，之后再按某些规则合成得到记录的文本相似度， 计算记录的文本相似度的基础是字符串匹配函数。 造成相似重复记录的原因可以分为两类嗍，一类是拼写错误造成的，如 表2 2 所示，从表中可看出，记录r l 和r 2 是重复的记录，只是在r 2 中出 现了4 种最常见的拼写错误：插入( d e p a r t m e n r t ) ，交换( s c i e n c e ) ，删除 ( u n i v e r s i y ) 和单词未知的变换( f o m p u t e rs c i e n c ed e p a r t m e n t ) 还有一类 i l 哈尔滨工程大学硕士学位论文 是同一实体但是表述方式不同，例如，在产品中经常用“w i n x p p r o ”来表示 “w i n d o w sx pp r o f e s s i o n a l ”。 表2 2 相似重复记录的例子。 为了描述方便，先定义下面几个概念： ( 1 ) 记录的特征：根据记录的内容并参照全局统计信息而计算出的一 个表示记录特征的整数值。 ： ( 2 ) 记录之间的距离d ：根据两记录的内容而计算出的一个表示两记录 相似重度的整数值。d 越小则两记录相似程度越高，若胁咄则两记录完全相 同。 在检测相似重复记录之前，一般需要先对数据进行一些处理。典型的处 理操作包括： ( 1 ) 字段分裂：从自由格式的文本字段中抽取结构，分离各个部分 ( 2 ) 验证和改正：根据查找表来验证字段值的正确性，若发现错误，则 加以改正如果提供合适的领域知识，该过程也可以验证字段之间的依赖关 系。 ( 3 ) 数据标准化：将同一类型的数据用统一的格式来表示，比如日期、 电话号码、性别等。 ( 4 ) 缺失值数据处理：当包含缺损数据的记录占整个数据集的比重较小 ( 如低于2 ) ，或者用户对缺损算法的精度没有太高要求( 如利用数据集作某 种近似推断) 时，可以利用简单处理算法来解决缺损数据问题，而且实践证明 针对少量缺损数据作简单处理，效果非常理想。简单缺损处理常用的方法有 以下几种： 1 丢失法：缺损数据较少且对结果影响不大时，将这些记录直接删除。 2 最大最小值填充法：选择数据集中的最大( 小) 值对缺损数据进行填 充。 3 任意值填充法：选择最大与最小值中间的随机数对缺损数据进行填充。 1 2 哈尔滨工程大学硕士学位论文 4 平均值最大概率值填充法：选择数据集中属性的平均值、中位数或出 现次数最多的值对缺损数据进行填充 2 2 1 足巨离函数 。 距离是测量相似性的一个手段，从点a 到点b 的距离，记为d ( 气b y ：” 距离有四个主要的性质：， ， ( 1 ) 定义明确：在两点之间的距离是确定的，d b ) o 。 ( 2 ) 同一性：从一个点到它本身的距离总是零，d ( a j 3 ) = 0 。 ( 3 ) 可交换性：方向不会有任何差别，a 到b 的距离与b 到a 点的距离 相同，即d ( a j 3 ) - - - - d ( b ，a ) ( 4 ) 满足三角不等式：两点之间直线距离最短，d ( a j 3 ) 其中，表示“一”在字符串s 中出现的次数。 例如，如果s = “r e c o r d ”，那么s 对应的t r i g r a m 向量包含四个分量：。r e c ”， 哈尔滨工程大学硕士学位论文 “e c o ”，“c o r ”和“o r d ”。如果“r e c ”在这个字符串中出现两次的话，那 么口一= 2 。有字符串比较算法将两个字符串对应的t r i g r m n 量相减，将相减 后得到的结果向量的大小和一个很小的值相比较，如果结果向量的大小小于 这个很小的阈值，那么则说明这两个字符串是相同的，反之，则不同。 二般地，向量j 和口相减得到地结果向量地大小可以由下面公式得出： = ( 国一6 f ) 2 ( 2 _ 7 ) ，。 i l = a a a 在这个算法中，产生t r i g r a m 的前提是将所用的字符串都变成小写并且忽 略空格以及标点符号。文献 7 中由具体试验得出最佳的极限值公式为： t = 2 4 8 6 + 0 0 2 5 n 7 ： 一 ( 2 8 ) 其中n 为进行比较的两个字符串对应的t r i g r a m 的总和。从公式( 2 8 ) 中可 以看出这里的极限值是动态取值的 下面给出一个具体的例子，对字符串“m a c h i n ev i s i o n ”和“m a c h i n e v i s i o n ”进行比较。向量万中包含8 个仃i g r a m ，所以西的大小为2 8 2 8 ，而极限 阈值为2 8 6 1 ，所以可以认为两个字符串相同 s t - - m a c h i n ev i s i o n 血l - m a c , a c h , c h i ，h i n ，i n e , e v ，v i s , i s i ，s i o ，i o n 鼢“m a c h i n e nv i s i o n ”以2 = m a c , a c h , c h i ，h i e ，i e n , n e v , e n v , e v i , i o n d = 彳矾- a * 2 = h i n ，h i e , h l e , i e n , l l e v , e n v , e v i , 1 3 v i l 蜊= 拉鬲再再两陌可= 2 8 2 8 s 2 4 8 臼旬0 2 5 1 5 = 2 8 6 1 2 2 4 编辑距离( e d i td i s t a n c e ) 编辑距离又被称为l e v e n s h t e i n 距离删，它表示为从一个字符串变换到另 一个字符串的最少插入、删除、替换操作的数目。它是一种常用的字符串距 离衡量方法，在确定两个字符串的相似性时，有广泛的应用。例如： 源字符串s 为“t e s t ”，目标字符串t 为“t e s t ”，那么从s 和t 之间的编辑 距离为0 ，因为这两个字符串是相同的，不需要任何转换操作。 源字符串s 为“t e s t ”，目标字符串t