（计算机软件与理论专业论文）集成数据中实体统一技术的研究.pdf

原创性声明和关于论文使用授权的说明1 1 i i i i ，i l l 了i i 1 1 l l l 8 l l l 9 l l i 1 1 1 l l l 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：沈未娟 日 期：加d 。争。夕 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：? 酶娟 导师签名：蓄目乏 日 期：w 舣牛 山东大学硕士学位论文 目录 摘要】 a b s t r a c t i i i 第一章绪论1 1 1 研究背景1 1 2 目前的研究现状2 1 3 研究内容和主要贡献4 1 4 本文的组织结构5 第二章实体统一的相关理论研究7 2 1 相关概念定义7 2 2 属性相似度8 2 2 1 基于字符串的相似度8 2 1 2 基于标记的相似度1 1 2 1 3 数字的相似度1 2 2 3 上下文相似度12 2 4 本章小结1 3 第三章一种领域无关的基于权值分级的实体统一方法1 4 3 1 问题引入1 4 3 2 基本思想及算法1 4 3 2 1 形式定义15 3 2 2 分级法计算权值1 6 3 2 3 数据分组1 7 3 2 4 字段匹配算法2 0 3 2 5 整体算法描述一2 l 3 3 实验结果与分析2 2 3 3 1 实验环境及数据准备2 2 3 3 2 实验结果与分析2 3 3 4 本章小结2 5 第四章一种领域相关的整体式实体统一方法2 6 4 1 问题引入2 6 4 2 主要思想及算法2 8 4 2 1 主要思想2 9 4 2 2 基于聚类的实体统一算法2 9 4 3 相似度度量方法3l 4 3 1 基于属性的相似度计算方法3l 4 3 2 基于上下文相似度的计算方法3 2 4 3 3 基于拟团相似度的计算方法3 2 4 4 实验结果与分析3 4 4 4 1 实验环境及数据准备3 4 【i i 东大学硕士学位论文 4 4 2 实验结果及分析3 5 4 5 小结3 7 第五章总结和展望3 8 5 1 总结3 8 5 2 展望3 9 参考文献4 0 致谢4 4 攻读学位期间发表的学术论文目录4 5 攻读学位期间参与科研项目情况4 6 山东大学硕士学位论文 c o n t e n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h i l l c h a p t e r1e x o r d i u m 1 1 1r e s e a r c hb a c k g r o u d 1 1 2c u r r e n ta c t u a l i t y 2 1 3r e s e a r c ha r e aa n dm a j o rc o n t r i b u t i o n 4 1 4o r g a n i z a t i o n a ls t r u c t u r e 5 c h a p t e r2t h e o r yo f e n t i t yr e s o l u t i o n 6 2 1c o n c e p ta n dd e f i n i t i o n 6 2 2a t t r i b u t i o ns i m i l a r i t y 7 2 2 1s i m i l a r i t yb a s e do nc h a r a c t e r 7 2 1 2s i m i l a r i t yb a s e do nt o k e n 11 2 1 3n u m b e rs i m i l a r i t y 11 2 3c o n t e x ts i m i l a r i t y 11 2 4c h a p t e rs u m m a r y 12 c h a p t e r3d o m a i n - i n d e p e n d e n te n t i t yr e s o l u t i o nb a s e do nw e i g h t r a n k 14 3 1i n t r o d u c t i o n 1 4 3 2b a s i ci d e aa n dd e f i n i t i o n 1 4 3 2 1b a s i cd e f i n i t i o n 15 3 2 2w e i g h tc a c u l a t eb yr a n k i n g 16 3 2 3d a t ag r o u p i n g 17 3 2 4f i e l dm a t c h i n ga l g o r i t h m ：! ( ) 3 2 5a l g o r i t h md e s c r i p t i o n 21 3 3e x p e r i m e n te v a l u a t i o n ：1 2 3 3 1e x p e r i m e n te n v i r o n m e n ta n dd a t a s e t 2 2 3 3 2e x p e r i m e n t a lr e s u l ta n da n a l y s i s 2 3 3 4c h a p t e rs u m m a r y 2 5 c h a p t e r4d o m a i n s p e c i f i cc o l l e c t i v ee n t i t yr e s o l u t i o n 。2 6 4 1i n t r o d u c t i o n ：1 6 4 2b a s i ci d e aa n da l g o r i t h m 2 8 4 2 1b a s i ei d e a 2 9 山东大学硕士学位论文 4 2 2e n t i t yr e s o l u t i o na l g o r i t h mb a s e do nc l u s t e r 2 9 4 3s i m i l a r i t ym e t r i c s 3 1 4 3 1s i m i l a r i t ym e a s u r eb a s e do na t t r i b u t e 31 4 3 2s i m i l a r i t ym e a s u r eb a s e do nc o n t e x t 3 2 4 3 3s i m i l a r i t ym e a s u r eb a s e do nq u a s i - c l i q u e 3 2 4 4e x p e r i m e n te v a l u a t i o n 3 4 4 4 1e x p e r i m e n te n v i r o n m e n ta n dd a t a s e t 3 4 4 4 2e x p e r i m e n t a lr e s u l ta n da n a l y s i s 3 5 4 5c h a p t e rs u m m a r y 3 7 c h a p t e r5c o n c l u s i o na n do u t l o o k 3 9 5 1c o n c l u s i o no f t h i sp a p e r 3 9 5 2o u t l o o ko f f u t u r ew o r k 4 0 r e f e r e n c e 4 1 a c k n o w l e d g e m e n t s 4 5 a c a d e m i cp a p e rp u b l i s h e d 4 6 w o r k s 4 7 山东大学硕士学位论文 摘要 日益发展的网络和飞速膨胀的信息给人们带来了很多的便利，人们已经开始 习惯于上网发布信息，查找资料，网上科研。各种各样的应用系统和w e b 服务 出现了丰富的数据资源。为了能有效利用这些现有资源，必须进行数据集成或者 数据挖掘。但是，由于数据源种类繁多，而且信息更新快，很多数据由于各种原 因得不得及时更新形成了大量过时数据，加之各数据源的异构性，使得集成数据 中含有大量的“脏数据”，即存在数据质量问题；主要表现为：拼写问题、录入 错误、不合法值、空值、不一致值、简写、同一实体的多种表示( 重复) 、不遵 循引用完整性等。由于不同数据库之间对数据表示的差异或者因为录入错误等人 为的原因导致集成后的数据库中同一实体对应多条记录，这些重复的记录可能导 致建立错误的数据挖掘模型，给后期数据的决策分析产生很大的影响。因此，判 断两条记录是否相似重复在数据集成、数据仓库中很重要。实体统一( e n t i t y r e s o l u t i o n ，e r ) 是用来判断多条记录是否指向相同的实体的问题，则上述的检 测这些重复数据即是进行实体统一。 实体统一是数据整合和数据清理的重要组成部分，通过消除冗余，为分析、 挖掘提供高质量的数据支持。本文据现有研究存在的问题，提出了两种实体统一 的方法，一是提出基于权值分级的实体统一方法。根据分级法计算每个字段的权 值，按照分级思想，选择某关键字段或字段某些位将大数据集分割成许多不相交 的小数据集，再在各个小数据集中进行实体统一，并引入多趟查找算法反复进行 实体统一：二是提出了领域相关的整体式实体统一方法，综合运用了属性，上下 文，和关系这三种相似度度量方法，来处理相似度，然后放入本文提出的整体式 聚类算法中进行实体统一。其主要贡献： ( 1 ) 在分析现有重复记录检测实体统一方法的基础上，提出领域无关的基 于权值分级的实体统一的算法。算法运用分级划分思想，即把大的数据集分割成 很多不相交的小数据集，再在小数据集中分别查找重复记录，即采用了分而治之 的思想，并进行多趟查找，实验证明这种方法提高了实体统一检测的精度和效率。 ( 2 ) 针对待统一实体本身之间具有丰富关系的场景，比如文献、社会关系 网等领域，提出了一个领域相关的整体式实体统一的方法。该方法综合运用了属 l 【j 东大学硕士学位论文 性，上下文，和关系这三种相似度度量方法，来处理相似度，并用本文提出的聚 类的实体统一算法来处理，比较全面的准确的计算出相似度，对几个数据集试验 评价表明该方法查准率高、效率好。 ( 3 ) 实体表象之间的紧密关联暗示了潜在团体的存在。为了度量这个紧密 关联的程度，我们引入数据结构拟团，定义了拟团相似度，用来衡量和计算关 系相似度；从而提高了整体式实体统一方法检测的查准率。 关键字：数据集成；数据仓库；实体统一；聚类；拟团 l j j 东大学硕士学位论文 a b s t r a c t w i t ht h eg r o w i n gn e t w o r k sa n de x p a n d i n gr a p i d l yi n f o r m a t i o n ，p e o p l eg e tal o t o fc o n v e n i e n c e p e o p l ef o re x a m p l e ，a r eu s e dt op u b l i s h i n g i n f o r m a t i o no n l i n e ， f i n d i n gi n f o r m a t i o n ，o n l i n er e s e a r c h av a r i e t yo fa p p l i c a t i o n sa n dw e bs e r v i c e sh a v e al a r g eo fd a t ar e s o u r c e s i no r d e rt ou s et h e s ee x i s t i n gr e s o u r c e se f f e c t i v e l y , d a t a i n t e g r a t i o no rd a t am i n i n gi sn e e d e d h o w e v e r , b e c a u s eo fal a r g eo f d a t af r o mv a r i o u s s o u r c e sa n df a s tu p d a t e dd a t a , al o to fd a t am a yn o tb eu pt od a t ef o rv a r i o u sr e a s o n s ； i n t e g r a t e dd a t ac o n t a i n sa l o to f ”d i r t yd a t a ”n a m e l yt h e r ei ss o m ew r o n ge x i s t e n c ei n d a t aq u a l i t y t h e s et h i n g sa r em a i n l y 淞f o l l o w s ：s p e l l i n gp r o b l e m s ，e r r o ri n p u t ，i l l e g a l v a l u e n u l lv a l u e ，i n c o n s i s t e n tv a l u e s ，u s eo fa b b r e v i a t i o n s ，d i f f e r e n tn a m i n g c o n v e n t i o n sd u p l i c a t e ，a n ds oo n t h ed a t ae x p r e s s i o nd i f f e r e n c e se x i s ti nd i f f e r e n t d a t 刁l b a s e s s ot h a te n t i t i e sh a v et w oo rm o r er e p r e s e n t a t i o n si nd a t a b a s e s t h e s e d u p l i c a t er e c o r d sm a yr e s u l ti nt h ee s t a b l i s h m e n to ft h ew r o n gd a t am i n i n gm o d e l ， w h i c hw i l lc a u s et ot h ew r o n gd e c i s i o na n a l y s i s t h e r e f o r e ，i ti sp a r t i c u l a r l yi m p o r t a n t t od e t e c tt w od u p l i c a t er e c o r d si nt h ed a t aw a r e h o u s ea n dd a t ai n t e g r a t i o n t oi m p r o v e t h er e l i a b i l i t ya n da v a i l a b i l i t yo fi n t e g r a t e dd a t a , i ti si m p o r t a n t t od e t e c tt h ed u p l i c a t e s a n dt om e r g et h e m t h i sp r o b l e mi sn a m e da se n t i t yr e s o l u t i o n t h i si s an e w c h a l l e n g ef o rr e s e a r c h e r si nt h ed o m a i no f d a t ai n t e g r a t i o na n dd a t aw a r e h o u s e t h eg o a lo fe n t i t yr e s o l u t i o ni st or e c o n c i l ed a t ar e f e r e n c e sc o r r e s p o n d i n gt ot h e s a m er e a lw o r l de n t i t y i ti sac r i t i c a lc o m p o n e n to fd a t ai n t e g r a t i o na n dd a t ac l e a n i n g o nt h eb a s i so ft h ee x i s t i n gp r o b l e m ，t w om e t h o d sa r ep r o p o s e di nt h i sp a p e r t h ef i r s t o n ei st h ef i e l d - i n d e p e n d e n tm e t h o db a s e do nw e i g h t e dg r a d ef o re n t i t yr e s o l u t i o n a n o t h e ro n ei sc o l l e c t i v ee n t i t yr e s o l u t i o nu s i n gq u a s i - c l i q u es i m i l a r i t ym e a s u r e t h e n e wi d e a si nt h em e a s u r e si sf o l l o w i n g ： 1 a c c o r d i n gt ot h et h o u g h to fg r o u p i n g ，c h o o s es o m ec e r t a i nk e yf i e l do rs o m e w o r d so ft h ef i e l dt od i v i d el a r g ed a t as e ti n t om a n yn o n - - i n t e r s e c t e ds m a l ld a t as e t s ， a n dt h e nd e t e c ta n de l i m i n a t ea p p r o x i m a t e l yd u p l i c a t e dr e c o r d si ne a c hs m a l ld a t a s e t ，w i t ht h ei n t r o d u c t i o no ft h ea b o v es t e p st h a ts h o u l db er e p e a t e dw i t ho t h e rk e y f i e l do rs o m ew o r d so ft h ef i e l d t h ee x p e r i m e n ts h o w st h a ts u c ha l g o r i t h mn o to n l y h a sag o o dd e t e c t i n gp r e c i s i o n ，b u ta l s oh a sb e t t e re f f i c i e n c yo ft i m e 2 i nm a n yd o m a i n s ，s o m eu n d e r l y i n ge n t i t i e sh a v es t r o n gt i e st oc e r t a i no t h e r t t i 山东大学硕士学位论文 e n t i t i e s f o ri n s t a n c e ，p e o p l eo f t e ni n t e r a c tw i t ht h e i rc l o s ef r i e n d si nas o c i a ln e t w o r k ， w h i l ei nb i b l i o g r a p h yd o m a i n ，r e s e a r c h e r sw h oh a v ec l o s ei n t e r e s t sc o n s t i t u t ea r e l a t i v es t a b l ec o m m u n i t yw h e r et h e yc o n t a c tf r e q u e n t l y t h ec o m p a c t n e s so ft h e c o m m u n i t yc a l le x p r e s sb ya k i n do fg r a p h 一一q u a s i c l i q u e 3 i nt h i sp a p e rw ep r o p o s eac o l l e c t i v ee n t i t yr e s o l u t i o nm e t h o d w h i c h c o m p r e h e n s i v e l y u t i l i z e st h e t h r e em e t h o d si n c l u d i n ga t t r i b u t e - b a s e ds i m i l a r i t y , c o n t e x t b a s e ds i m i l a r i t ya n dq u a s i - c l i q u es i m i l a r i t y i np a r t i c u l a r , w em e a s u r e r e l a t i o n s h i ps i m i l a r i t yu s i n gq u a s i - c l i q u ew h i c hr e d u c e se f f e c t i v e l y f a l s ep o s i t i v e c a s e sa n di m p r o v e st h e a c c u r a c yo fe n t i t y r e s o l u t i o n f o raf e we x p e r i m e n t a l e v a l u a t i o no fad a t as e tt h a th i g hp r e c i s i o n ，t h ee f f i c i e n c yo ft h em e t h o di sp e r f e c t k e yw o r d s ：d a t ai n t e g r a t i o n ；d a t aw a r e h o u s e ；e n t i t yr e s o l u t i o n ；c l u s t e r i n g ； q u a s i - c l i q u e i v 山东大学硕士学位论文 1 1 研究背景 第一章绪论 日益发展的网络和飞速膨胀的信息给人们带来了很多的便利，人们已经开始 习惯于上网发布信息，查找资料，网上科研。各种各样的应用系统和服务出现了 丰富的数据资源，这些资源不仅包括传统的数据库，如关系数据库和面向对象数 据库，还包括w e b 上应用广泛的h t m l ，x m l 等半结构化资源。为了更有效的 利用这些数据，需要在一个统一的平台上对这些数据进行集成和访问。但是，由 于这些数据分布在不同的服务器站点上，各数据源采用本地策略对数据实施操 作，并且各数据源采用不同的存储方式，以及使用不同的概念、属性和关系来表 达数据，造成了多层面的数据共享与互操作的困难。如何将上述的多个分布异构 数据源集成在一起，可以进行灵活的互操作，并在此基础上实现高效的查询、检 索和比较，乃至数据挖掘、知识发现等信息应用已经成为当前所关注的问题。由 于数据源种类繁多，而且信息更新快，很多数据由于各种原因得不得及时更新， 使得集成数据中含有大量的“脏数据”：拼写问题、录入错误、不合法值、空值、 不一致值、简写、同一实体的多种表示( 重复) 、不遵循引用完整性等【1 1 】，严重 影响了数据的可信度和可用性，现实世界中的数据极易受噪声数据、空缺数据和 不一致性数据的侵扰。对于这样的数据，如果不进行数据处理，数据质量就会很 差，对应的一些应用，如商业或者其他行业的情报分析、决策判定、数据报表等 也就成了无根之树，没有意义了，即成了“进去的是垃圾，出来的也是垃圾 ( g a r b a g ei n ，g a r b a g eo u t ) 。因此，数据质量的提高正在获得越来越多的关注。 在有关数据质量的各种问题中，检测重复的记录，是最关键的问题之一。为了检 测这些重复数据，判断两条记录是否相似重复，以防影响集成数据的可信度和可 用性，我们引入了实体统一技术来解决。在数据集成过程中，由于不同数据库之 间对数据表示的差异或者因为人为的差异导致集成后的数据库中同一实体对应 多条记录，这些重复的记录可能导致建立错误的数据挖掘模型，给后期数据的决 策分析产生很大的影响。因此，实体统一技术在数据集成，及集成后的数据挖掘 中尤为重要。 l 【j 东大学硕士学位论文 由于实体统一可以准确的识别一个或者多个数据源中的重复记录，在客户关 系管理、欺诈预防、医疗卫生和信用管理等行业具有广泛的应用。这里指的实体 可以是个人，公司，地理位置，家庭，建筑物等，也可以是某一个概念对应的记 录，例如所有网站出售的九阳豆浆机。在应用中，识别出描述同一个现实实体的 所有记录是非常重要的。例如，用户可能会在一个商业网站上进行多次注册，商 业公司在分发广告单时，如果不进行实体统一，就会给这个用户发送多份广告单， 造成浪费。可见，在数据仓库中，实体统非常重要。 因此，实体统一在数据集成，数据仓库中非常重要。对数据集成和数据仓库 的数据进行实体统一是给研究者提出的一个新的挑战。完成实体统一以后，每一 个对象对应一个u n i q u ei d ，系统可以正确的聚类某一对象的全部数据，去掉重 复记录和重复属性。所以利用实体统一可以提高数据的完备性( c o m p l e t e n e s s ) 和简洁性( c o n c i s e n e s s ) 。 1 2 目前的研究现状 实体统一技术用来判断多条记录( r e f e r e n c e ) 是否指向相同实体的技术。由 于用户录入错误、信息集成和数据随着时间而改变等原因，数据库中经常出现一 个现实实体由多个不完全相同的记录来表示的情况。通常情况下，指向同一个现 实实体的多条记录的信息是部分冗余的，他们的数据互为补充。因此，通过合并， 能够更准确得反映该实体，这就是实体统一的一个非常重要的组成部分。但在本 文中，主要研究多条记录是否指向同一个现实中的实体。 目前，与特定应用领域无关的实体统一研究主要集中在冗余重复的记录上， 其主要工具包括：d a t ab l a d em o d u l e ，c h o i c em a k e r ，i n t e g r i t y ，m e r g e p u r g e l i b r a r y ( s a g e n t q ms o f t w a r e ) ，m a t c hi t ( h e l pi ts y s t e m s ) ，m a s t e rm e r g e ( p i t n e y b o w e s ) ，d a t ac l e a n s e r ( e d d ) 等。数据质量是影响数据挖掘效果的关键因素之一。 为提高被挖掘数据源的数据质量，实体统一就变得很重要，不同数据源数据集成 的一个重要问题是语法上相同或相似的不同记录可能代表现实世界中的同一实 体，因此相似重复记录的检测成为实体统一中的一个关键环节。 针对拥有海量数据的数据仓库和集成数据，以及随后的数据挖掘工作，传统 的实体统一主要采用距离函数模型、标准的字符串度量方法【2 1 ，基于q - g r a m 算 2 山东大学硕士学位论文 法【1 3 】和“排序& 合并”的方法【4 5j 来检测重复记录，这些传统方法做实体统一时， 会涉及很大的时间复杂度和空间复杂度，并且排序时由于字符位置敏感性并不能 保证相似的记录排在邻近的位置，导致基于q - g r a m 算法和聚类算法( 如“滑动窗 口”或“优先队列聚类”) 【4 5 】应用与大规模数据时，时间复杂度不理想，需要进一 步做优化工作。 传统实体统一的优化工作可以分成两个部分：( 1 ) 提高实体统一的准确率， 优化两条记录相似度的计算公式( 2 ) 提高实体统一的效率，减少需要比较的记 录对数目。在处理大的数据集时，进行实体统一是一个非常耗时的过程。因为是 模糊匹配，所以整个过程相当于要对两个记录源作笛卡尔积，每两条记录都需要 进行比较。假设数据源a 有m 条记录，数据源b 有m 条记录，数据源b 中的 条记录都是数据源a 中的m 条记录的潜在匹配对象。理论上共有d 个记录 对需要进行判断。为了提高实体统一的速度，大量的研究工作集中在如何减少需 要比较的记录对数目上，多采用将数据库中记录排序，然后通过比较临近记录是 否相似来进行实体统一。 在传统的实体统一研究中，人们主要在解决如下两个问题：( 1 ) 如何计算记 录对的相似度( 2 ) 如何减少需要进行相似度计算的记录对数目。w e w i n k l e r 在文酬6 j 中综述了当时与实体统一相关的研究工作。几年过去了，实体统一领 域的研究又取得了很大的进展，而且最近几年出现了一些新的模型和方法，突破 了传统实体统一中基于两条记录计算相似度的思想一即整体式( c o l l e c t i v e ) 思想。 由于数据来自于不规范的各种数据源，对同一对象描述的详尽程度各不相 同，存在大量属性值缺失的现象。因而，难以保证存在足够的“证据”来判断记录 的重复。如何设计重复探测算法以适应这种情况是一个待解决的问题。通常，重 复探测都是比较耗时的，传统方法大都需要一定量的训练数据或者人工参与。如 何设计快速的重复探测算法是另一个待解决的问题。 传统的重复探测技术是考虑同一类的两个模式的记录对之间的对应，然后通 过传递闭包来匹配其它模式的记录，它需要两个模式之间存在若干对应的属性， 而这些属性所对应的值集存在着一定量的重复或者具有较大的相似度。而根据前 面的分析，w e b 数据集成环境下传统的重复探测技术显然不太适合了。而另一方 面，实例之间存在的大量的关联关系。而这些关联关系可以通过诸如链接、出现 在同一页面等明显的信息得到。这给出了非常有益的启示。 3 山东大学硕士学位论文 数据分类是一种非常重要的方法。当人们面对海量的数据时，首先要对这些 数据进行分类，然后再对较小的数据集进行分析研究。这符合人类遇到复杂问题 时采取的“分而治之”的策略。现在有一种基于n g r a m 的相似重复记录检测方法 【7 1 ，该方法先计算各记录的n g r a m 值，然后以各记录的n g r a m 值为排序键进行 排序，再通过采用一种高效的应用无关的p a i r - w i s e 比较算法，通过计算两条记录 中单词间的编辑距离来判断记录的相似与否，并采用一种改进的优先队列算法来 准确地聚类相似重复记录。该方法在一定程度上有效地解决了相似重复记录的检 测问题，但当数据量大，错误多，单词间互相影响时，该方法的初步聚类效果就 会受到很大的影响。 在文献【8 1 研究了一种检测多语言数据重复记录的综合方法，该方法充分考虑 了中文数据库的环境，有效地解决了多语言数据记录的初步聚类和记录比较问 题。另外，北京大学对实体统一也做了一些相关研究，他们主要解决了关系数据 库中，针对客户数据集成时重复记录的数据清洗问题f 9 】。东南大学以董逸生教授 为首的研究小组也对数据统一做了一些研究，他们主要是针对数据仓库化过程中 的数据清洗问题进行研究【1 0 1 。 1 3 研究内容和主要贡献 实体统一在数据仓库和数据集成中意义重大，这引起了国内外对实体统一的 研究的关注，我做的主要的工作如下： 一是在分析现有重复记录检测算法的基础上，提出基于权值分级的实体统一 方法。根据分级法计算每个字段的权值，按照分级思想，选择某关键字段或字段 某些位将大数据集分割成许多不相交的小数据集，再在各个小数据集中检测相似 重复记录，并引入多趟查找算法，实验表明此算法能快速、准确检测重复记录。 二是提出了领域相关的整体式实体统一方法，该方法首先利用属性计算方法 计算，利用成对的p a i r w i s e 方法比较两表象对应属性值之间的相似度，然后利 用上下文的相似度计算方法计算，对每对表象对判断一个分类，当该分类为是的 时候，则认为两表象指向同一现实世界中的实体，反之，则两表象指向不同的实 体，然后用拟团相似度作为关系相似度的度量计算相似度，然后放入聚类算法里。 也即，综合运用了属性，上下文，和关系这三种相似度度量方法，来处理相似度， 然后放入本文提出的整体式聚类算法。 4 l l j 东大学硕士学位论文 与目前已有的工作相比，我的主要贡献在于： ( 1 ) 提出领域无关的基于权值分级的相似重复记录检测算法。算法运用分 级划分思想，即把大的数据集分割成很多不相交的小数据集，再在小数据集中分 别查找重复记录，即采用了分而治之的思想，并进行多趟查找，提高了检测精度 和效率。 ( 2 ) 针对待统一实体本身之间具有丰富关系的场景，比如文献、社会关系 网等领域，提出了一个领域相关的整体式实体统一的方法。该方法综合运用了属 性，上下文，和关系这三种相似度度量方法，来处理相似度，并用本文提出的聚 类的实体统一算法来处理，比较全面的准确的计算出相似度，对几个数据集试验 评价表明高查准率，验证了该方法的效率。 ( 3 ) 实体表象之间的紧密关联暗示了潜在团体的存在。为了度量这个紧密 关联的程度，我们引入数据结构拟团，定义了拟团相似度，用来衡量和计算关 系相似度。从而提高了实体统一检测的查准率。 1 4 本文的组织结构 本文一共分为五个章节。 第一章是本文的绪论部分。该章讨论了实体统一的研究现状，通过对国内外 对于实体统一技术的总结对比了已有成果的优点和不足。同时该章还概括了本课 题的研究内容以及本文所做的主要工作。 第二章介绍了实体统一的相关理论研究。为了行文方便，定义了一下概念。 研究了几个相似度的计算方法。 第三章在分析现有重复记录检测的实体统一方法的基础上，提出领域无关的 基于权值分级的实体统一的方法。根据划分法计算每个字段的权值，按照划分思 想，选择某关键字段或字段某些位将大数据集分割成许多不相交的小数据集，再 在各个小数据集中检测相似重复记录，并引入多趟查找算法，实验表明此算法能 快速准确检测重复记录。 第四章针对待统一实体本身之间具有丰富关系的场景，比如文献、社会关系 网等领域，提出了一个领域相关的整体式实体统一的方法。该方法综合运用了属 性，上下文，和关系这三种相似度度量方法，来处理相似度，并用本文提出的聚 类的实体统一算法来处理，其中关系相似度的度量使用了拟团 5 山东大学硕士学位论文 第五章对全文进行总结，总述了本文的主要贡献以及不足，并对该领域将来 的研究进行了展望。 6 山东大学硕士学位论文 第二章实体统一的相关理论研究 实体统一在不同的领域里有不同的称呼，在数据库被称为：m e r g e p u r g e t l i l 、 d a t ar e d u p l i c a t i o n 12 1 、i n s t a n c ei d e n t i f i c a t i o n 1 3 】在人工智能领域里也被称为d a t a b a