（计算机软件与理论专业论文）deep+web查询接口模式匹配技术的研究与应用.pdf

南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开人学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 箧巫星 2 0 1 0 年5 月3 1 日 南开大学研究生学位论文作者信息 论文题目 d e e pw e b 查询接口模式匹配技术的研究与应用 姓名侯乐彩学号 21 2 0 0 7 0 3 0 7 答辩日期2 0 l o 年5 月2 1 日 论文类别博七口学历硕士硕十专业学位口高校教师口同等学力硕士口 院系所信息技术科学学院 专业 计算机软件与理论 联系电话 1 3 6 6 2 1 8 2 5 0 7e m a i l h o u l e c a i m a i l n a n k a i e d u c a 通信地址( 邮编) ：天津市南开人学两区公寓5 3 - 3 0 6 ( 3 0 0 0 7 1 ) 备注：是否批准为非公开论文否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 9洲61 伽4mmjim 8 iiil-y 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所 取得的研究成果。除文中已经注明引用的内容外，本学位论文的研究成果不包 含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本 学位论文原创性声明的法律责任由本人承担。 学位论文作者签名：送压受2 0 1 0 年5 月3 1 日 非公开学位论文标注说明 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申 请和相关部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本 说明为空白。 论文题目 申请密级 口限制( 2 年)口秘密( 1 0 年)口机密( 2 0 年) 保密期限 2 0 年月日至2 0年月日 审批表编号批准日期 2 0 年月日 限制2 年( 最长2 年，可少于2 年) 秘密1 0 年( 最长5 年，可少于5 年) 机密2 0 年( 最长1 0 年，可少于1 0 年) 摘要 摘要 如何自动搜索、抽取、挖掘互联网上分布的w e b 数据库中的信息是w e b 搜 索的研究热点。d e e pw e b 数据集成的主要研究内容之一是如何通过一个统一的 接口访问所有分布的w e b 数据源，获得质量优结构好的信息。因此，具有很好 的研究和应用价值。 查询接口是获得w e b 数据库信息的唯一途径，因此它是d e e pw e b 数据集 成的核心难点问题。为了完成查询接口集成，首先要完成查询接口间的模式匹 配，因为模式匹配是发现异构数据源属性的语义对应的关键一步。 在深入分析研究现有d e e pw 曲模式匹配技术的基础上提出了一种新的模式 匹配方法整体模式匹配方法，该方法通过数据挖掘的方法一次性发现多个 模式间的复杂匹配。该方法将成组属性看作正相关的，通过在输入模式集的属 性信息上进行正相关挖掘发现成组属性，然后将同义属性( 即匹配) 看作负相 关的，在属性和成组属性的基础上进行负相关挖掘发现不同模式问属性的匹配。 在借鉴d c m 框架中的相关度度量方法的基础上做了一些改进，主要对度量 两个属性的正相关度的方法做了修改，使得成组属性发现更为准确，避免发现 大量的伪成组属性，从而使得同义属性发现更为准确和高效。 设计实现了包括查询接口模式抽取、查询接口模式匹配、查询接口集成三 部分在内的d e e p w e b 集成系统。其中，查询接口模式包括查询接口的网址、提 交方法、属性、元素、元素值域等信息的采集，对此采用了人工介入配置形成 所需信息，从而保证基础研究的模式信息的准确性。 在完成了模式匹配给出输入模式集的属性问的同义匹配结果的基础上，提 出了d e e pw 曲接口集成方法。根据源查询接口的属性出现频率和属性模式匹配 结果，选择全局查询接口的属性，然后生成属性对应的表单元素，从而生成全 局的查询接口。 最后在分别在b a m m 数据集上和手工抽取的接口模式上应用了整体模式匹 配算法，并实际应用于d e e pw - e b 图书搜索系统，运行结果表明该算法在发现复 杂模式匹配方面显示出良好的准确性，也验证了其可行性和有效性。 关键字：d e e pw r e b ，复杂匹配，数据挖掘，整体模式匹配，查询接口集成 i a b s t r a c t a b s t r a c t i ti sah o ts p o tt os t u d yt h a th o wt oa u t o m a t i c a l l ys e a r c h ，e x t r a c ta n dm i n et h e i n f o r m a t i o no nt h e d i s t r i b u t e dw e bd a t a b a s e s d e e pw e bd a t ai n t e g r a t i o n , w h o s e p u r p o s ei sa c c e s s i n ga l l t h ed i s t r i b u t e dw e bd a t a b a s e sv i aag l o b a lq u e r yi n t e r f a c et o g e tt h ei n f o r m a t i o nw h i c h h a sg o o ds t r u c t u r ea n de x c e l l e n tq u a l i t y , t h u sh a sv e r yg o o d v a l u ef o rb o t ho fs t u d ya n da p p l i c a t i o n q u e r yi n t e r f a c ei st h eo n l yp a t h t og e tt h ei n f o r m a t i o no ft h ew e bd a t a b a s e s ，s oi t i st h ec o r ea n dd i f f i c u l t yo fd e e pw e bd a t ai n t e g r a t i o n t oe n a b l eq u e r yi n t e r f a c e i n t e g r a t i o n ，s c h e m am a t c h i n gb e t w e e nq u e r y i n t e r f a c e sm u s tb ei m p l e m e n t e d ， b e c a u s ei ti sac r i t i c a ls t e pf o rd i s c o v e r i n gs e m a n t i cc o r r e s p o n d e n c e so fa t t r i b u t e s a c r o s sh e t e r o g e n e o u ss o u r c e s b a s e do na n a l y z i n ga n ds t u d y i n gc u r r e n tt e c h n o l o g yf o rs c h e m am a t c h i n g ，an e w a p p r o a c hn a m e db yh o l i s t i cs c h e m am a t c h i n gi sp r o p o s e d t h i sa p p r o a c hd i s c o v e r s t h en - r a yc o m p l e xm a t c h e sb e t w e e nm u l t i p l es c h e m a sa tt h es a m et i m eb ym i n i n gt h e s c h e m ad a t a t h i sa p p r o a c hv i e w st h eg r o u p i n ga t t r i b u t e sa sp o s i t i v e l yc o r r e l a t e d a t t r i b u t e s ，s oi td i s c o v e r sg r o u p i n ga t t r i b u t e sb ym i n i n gt h ep o s i t i v ec o r r e l a t i o no v e r i n p u ts c h e m a s i tv i e w st h es y n o n y ma t t r i b u t e s ( i e m a t c h ) a sn e g a t i v e l yc o r r e l a t e d a t t r i b u t e s ，s oi td i s c o v e r ss y n o n y ma t t r i b u t e sb ym i n i n gt h en e g a t i v ec o r r e l a t i o no v e r a t t r i b u t e sa n dg r o u p so ft h ei n p u ts c h e m a s t h eh m e a s u r ei nd c mf r a m e w o r ki si n t r o d u c e da n di m p r o v e d t h em e a s u r e f o rp o s i t i v ec o r r e l a t i o ni si m p r o v e d ，s ot h eg r o u p i n ga t t r i b u t e sd i s c o v e r i n gi sm o r e a c c u r a t ea n dt h e r ei sn o ts om a n yf a l s eg r o u p sd i s c o v e r e d ，t h u s t h es y n o n y m a t t r i b u t e sd i s c o v e r i n gi sm o r ea c c u r a t ea n de f f e c t i v e ad e e pw e bi n t e g r a t i o ns y s t e mc o n t a i n i n gq u e r yi n t e r f a c es c h e m ae x t r a c t i o n , q u e r yi n t e r f a c es c h e m am a t c h i n ga n dq u e r yi n t e r f a c ei n t e g r a t i o n i sd e s i g n e da n d i m p l e m e n t e d i nt h i ss y s t e m ，q u e r yi n t e r f a c es c h e m a i sc o m p o s e do ft h eu r l ，a c t i o n ， m e t h o d ，a t t r i b u t e s ，e l e m e n t s ，e l e m e n tv a l u e sa n ds oo n t oe n s u r et h ea c c u r a c yo ft h e f u n d a m e n t a li n f o r m a t i o no fs c h e m a , t h e s es c h e m ad a t a a r ee x t r a c t e db ym a n u a l c o n f i g u r i n g i i 一a b s t r a c t 一 一 a f ；【e rs c h e m am a t c h i n g ，t h er e s u l to fs y n o n y mm a t c h i n g o v e ra t t r i b u t e so f1 n p u t s c h e m a si so b t a i n e d b a s e do nt h i sr e s u l t ，t h e g l o b a lq u e r yi n t e r f a c e 1 sm t e 笋a t e d a c c o r d i n gt ot h ef r e q u e n c yo fe v e r ya t t r i b u t e a n dt h es y n o n y mi 耐o m a t l o no v e r a 缸b u t e s ，t h ea 仕m u t e so ft h eg l o b a lq u e r yi m e r f a c e c a nb es e l e c t e d ，a n dt h e nt h e i r f o 腿c o n 仃o l sa n do p t i o n s c a i lb eg e n e r a t e d ，t h u st h eg l o b a l q u e r y i n t e r f a c e1 s g e n e r a t e d 。 f i i l a l l v ，t h eh s ma l g o r i t i 皿i s e v a l u a t e ds e p a r a t e l yo nb a m m d a t a s e ta i l d m a n u a l l ye x t r a c t e d i n t e r f a c e s ，a n df u r t h e r a na p p l i c a t i o nf o rd e e p w e bb o o k s e a r 出n gs y s t e mi sd e v e l o p e d t h e r e s u l t ss h o wg o o da c c u r a c yf o r d i s c o v e r i n g c o m p l e xm a t c h e s ，a n dt h e ya l s op r o v e t h a tt h ea l g o r i t h mi sp r a c t i c a b i ea n d v a l l d k e yw 。r d s ：d e e pw e b ，c 。m p l e x m a t c h i n g ，d a t am i n i n g ，h o l i s t i c s c h e m m a t c h i n g ，q u e r yi n t e r f a c ei n t e g r a t i o n i i i 目录 目录 第一章绪论1 第一节d e e pw e b 研究背景1 第二节国内外研究现状。3 第三节主要研究内容和结构安排5 第二章系统架构的设计7 第一节d e e pw e b 数据集成框架概述7 第二节系统架构的设计。9 第三节相关术语的定义1 1 第四节d e e pw e b 系统的重点问题分析1 3 第三章基于数据挖掘的整体模式匹配方法1 9 第一节匹配发现1 9 3 1 1 整体模式匹配算法基本流程一2 0 3 1 2 挖掘算法设计2 1 3 1 3 匹配发现详细流程一2 4 第二节匹配构建2 6 3 2 1 匹配排列一2 7 3 2 2 匹配筛选2 8 第三节相关性度量方法的改进3 1 3 3 1s m e a s u r e ：；1 3 3 2 采样不变性3 8 第四章接口模式抽取和查询接口集成4 0 第一节人工接口模式抽取4 0 4 1 1 配置信息。4 0 4 1 2 数据顶处理一4 2 第二节基于匹配结果的全局接口集成4 4 4 2 1 属性选择4 4 4 2 2 表单元素生成4 4 i v 目录 4 2 3 值域生成4 5 4 2 4 集成接口4 6 第五章应用结果与分析4 7 第一节实验数据集4 7 第二节召回率和正确率的测试4 7 第三节模式匹配算法的实验结果分析4 9 第四节d e e pw e b 图书搜索系统实际应用情况5 1 第六章总结与展望。5 5 第一节总结5 5 第二节展望5 6 参考文献5 8 致谢61 个人简历、学术论文与研究成果6 2 v 第一章绪论 第一章绪论 第一节d e e pw e b 研究背景 随着w o r l dw i d ew e b 的飞速发展，其中蕴含了海量的信息可供我们利用， 网络已经成为一个名副其实的巨大的信息资源库。如果按其所蕴涵信息的“深 度，可以划分为s u r f a c ew e b 和d e e pw e b 两大部分。s u r f a c ew e b 是指通过超 链接可以被传统搜索引擎索引到的页面的集合，s u r f a c ew e b 页面通常由静态链 接产生，由于其对传统的搜索引擎是相对可见的，又称为v i s i b l ew e b ；d e e pw e b 是指w e b 中不能被传统的搜索引擎索引到的那部分内容，又称为i n v i s i b l ew e b 。 1 9 9 4 年，d r j i ue l l s w o r t h 在互联网领域首次提到了不可见网络( i n v i s i b l e w e b ) 一词。但是真正的d e e pw r e b 研究起始于1 9 9 8 年，当时两位美国信息管理 专家l a w r e n c e 和g i l e s 提出网络信息利用率问题，意识到通用搜索引擎的覆盖 率较低，鉴于网络信息资源没有得到充分的开发和利用，他们提出了开发深层 网络信息资源的想法。2 0 0 1 年，不可见网络：挖掘搜索引擎不能看见的资源 的作者c h r i ss h e r m a n 和g a r yp r i c e 把不可见网络定义为：通过万维网可以获得 的文本网页、文件或其它高质量、具有权威性的信息资源，但是由于技术限制 或者特定选择的原因，使得通用搜索引擎不能或不愿把这些信息加入网页索引 数据库中。广义上来说，d e e pw e b 的内容主要包含4 个方面： ( 1 ) 通过填写表单形成对后台在线数据库的查询而得到的动态页面； ( 2 ) 由于缺乏被指向的超链接而没有被搜索引擎索引到的页面，大约占整 个比例的2 1 3 ； ( 3 ) 需要注册或其它限制才能访问的内容； ( 4 ) w e b 上可访问的非网页文件，比如图片文件、p d f 和w o r d 文档等。 而在实际中应用中，由于d e e pw e b 中的第一部分内容对结构化数据的集成 更有意义，可以采用的技术也更丰富，所以人们更关注这部分内容。d e e pw e b 数据集成也主要是指对结构化信息的集成。本文中的d e e pw e b 就是指这部分内 容。 与s u r f a c ew e b 相比，d e e pw e b 蕴藏了更加丰富，更加“专业”( 专注于某 一领域) 的信息。近年来的研究成果表明【1 1 1 2 1 3 】： 1 第一章绪论 ( 1 ) 访问量d e e pw e b 蕴含的信息量是s u r f a c ew e b 的4 0 0 - - 5 5 0 倍，截止 到2 0 0 4 年，大约有3 0 7 0 0 0 个站点，4 5 0 0 0 0 个后台数据库和1 2 5 8 0 0 0 个查询接 口。 ( 2 ) 对d e e pw e b 数据的比s u r f a c ew e b 要高出1 5 。 ( 3 ) d e e pw e b 整体质量至少比s u r f a c ew e b 高1 0 0 0 到2 0 0 0 倍，d e e pw e b 中的后台数据库大多是结构化的，其中结构化的是非结构化得3 4 倍之多。 ( 4 ) d e e pw e b 的增长速度要远大于s u r f a c ew e b ，从2 0 0 0 年到2 0 0 4 年增 长了6 倍多，并且仍在增长。 ( 5 ) 超过5 0 的d e e pw e b 的内容是特定于某个领域的，即面向某个领域。 ( 6 ) 整个d e e pw e b 覆盖了现实世界中的各个领域，比如商业、教育、政 府等等。 ( 7 ) d e e pw e b 上9 5 的信息是可以公开访问的，即免费获取。 ( 8 ) w e b 数据库查询接口往往位于站点浅层，9 4 之多的大量w e b 数据库 查询接口可以在站点前3 层发现。 具体到国内的情况，2 0 0 8 年1 月c n n i c ( 中国互联网络信息中心) 发布了 第二十一次中国互联网络发展状况统计报告1 4 1 ，报告显示：截至2 0 0 7 年1 2 月， 我国网民人数达到了2 1 亿，网站数量达1 5 0 万个，比去年同期增长了6 6 万个， 增长率达到7 8 4 。中国网页总数有8 4 7 亿个。年增长率达到8 9 4 。这些网页 中，动静态的比例为0 9 2 ：1 ，动态网页的比重在逐年增高。 综上所述，d e e pw e b 具有信息量大、价值高、质量优、结构化好等特点， 然而由于目前w e b 数据库存在规模大、自治性、异质性、动态性等问题，要想 全面而准确的搜索出d e e pw e b 中的信息是一件迫切需要而又非常困难的事情。 因此对于d e e pw e b 的研究日益成为研究热点。目前主要关注于以下几个关键问 题：d e e pw e b 站点的发现和分类、查询接v i 集成、数据抽取、实体识别、结果 合并等。 模式匹配是查询接口集成至关重要的步，也是今后研究信息集成和信息 挖掘的基础，必将成为下一代信息集成技术和搜索引擎技术研究的一个起点。 因此d e e pw e b 模式匹配技术研究在d e e pw e b 研究领域中有着重要的地位。 本文着重对d e e pw e b 模式匹配技术进行研究，并在此基础上提出查询接口 全局模式的建立，希望为人们获取和利用d e e pw e b 资源提供一些方法。 2 第一章绪论 第二节国内外研究现状 一个模式由一组元素组成，这里的元素可以是表、列、类、属性等。模式 匹配问题是：对于一个模式s l ( 比如全局模式) 和一个模式s 2 ( 比如数据源模 式) ，在这两个模式的相应元素之间找出某些语义上相同或相似的关系，由此产 生s l 与s 2 的匹配关系。当前，一般是采用人工方式解决这些异构性问题的模式 匹配。这个人工过程是冗长的、费时的，容易出错的，因而代价很高。这就需 要一种劳动强度相对较小的方法。这种方法应该支持自动辨别同义关系，并且 能够在源模式和全局模式之间生成映射。2 0 0 1 年e r h a r dr a b m 【5 1 对模式匹配技术 做了详细综述，文中提出一个模式匹配方法的分类框架，分别从匹配过程需要 利用的信息类型角度( 如模式和实例、元素层和结构层、语言和语义约束信息 等) 对匹配方法做了划分，如图1 1 所示。 图1 1 模式匹配方法分类 有关模式匹配理论的研究按照基于知识的不同主要分为两类：第一类是基 于待匹配模式元素的标签和模式自身的结构信息进行语义匹配关系推理：第二 3 第一章绪论 类是针对大量的模式信息集和对应的数据实例集进行统计分析，以推理出语义 模式匹配关系 第一类具有代表性的研究工作主要有：( 1 ) m i c r o s o f t 的c u p i d 方法【6 j ：基于 模式结构信息进行匹配推理，并应用辅助信息处理同义词、缩略词、首字母缩 写等。( 2 ) l e i p z i g 大学的c o m a ( as y s t e mf o rf l e x i b l ec o m b i n a t i o no fs c h e m a m a t c h i n ga p p r o a c h e s ) 方法【7 】：采用复合式方法，灵活地组合不同的匹配算法及结 果，以显著地提高匹配效率。( 3 ) s t a n f o r d 大学的s i m i l a r i t yf l o o d i n g 方法瞄j ：基 于相邻元素之间的相似传递性进行推理，如果两个模式元素的邻近元素相似， 它们就趋于相似。( 4 ) w a s h i n g t o n 大学的g l u e 方法【9 】：基于机器学习实现模式 匹配，并采用多策略学习方法自动合并不同匹配器的匹配结果。( 5 ) l s d 方法l l u j ： 基于机器学习实现新数据源模式到全局模式之间的映射。( 6 ) i b m 的c l i o 方法 【1 1 1 ：半自动化的模式匹配系统，此类方法的主要优点是基于模式自身携带的有 限结构信息挖掘模式匹配关系。 但是，模式自身携带语义信息的有限性决定了最后匹配结果具有一定的局 限性，主要表现为：( 1 ) 当模式元素匹配对信息量不足或模式元素匹配对之间 的区分度较小时，匹配效果会急剧下降。( 2 ) 匹配的前提是相邻匹配对彼此相 互影响，当候选匹配对之间缺乏绝对层次关系时，比如h t m l 页面表单中的两个 标签元素在语义上有相邻关系但在模式文本中的距离却相距很远时，此类方法 无法有效处理。( 3 ) 只能对一对一型匹配关系挖掘，没有考虑一对多匹配关系， 而在实际的模式匹配中存在着大量的一对多甚至多对多匹配关系。 第二类匹配方法主要是基于大数据量模式集合、重复实例元组及组合已有 的模式匹配技术进行模式匹配的研究，代表性的工作有：( 1 ) c o r p u s 方法1 1 2 j ： 应用信息检索中的方法对大数据量文本集进行分析，挖掘模式元素之间的语义 关联关系。( 2 ) 应用统计分析方法对大量模式知识进行分析( h y p o t h e s i sm o d e l i n g ， g e n e r a t i o n ，s e l e c t i o n ，简称m g s ) 1 3 】，挖掘模式中“隐含 的对象模型，并基 于此模型进行模式匹配。( 3 ) 双重相关关联挖掘方法( d u a lc o r r e l a t i o nm i n i n g ， 简称d c m ) 1 4 】【”】：利用属性是否总是同时出现或从不同时出现的信息挖掘成组 属性和同义属性，从而形成m n 复杂匹配。( 4 ) 全体采样和投票方法( e n s e m b l e s a m p l i n ga n dv o t e ，简称e s v ) 1 4 1 1 6 l ：多次采样，多次试验，最后综合运用多种 聚合策略【1 7 】【1 8 1 对结果进行聚合，消除自动抽取的模式数据中的“噪音 数据对 匹配结果的影响。( 5 ) 基于聚类的交互式方法( i n t e r a c t i v ec l u s t e r i n g b a s e d ) i l 刿： 4 第一章绪论 把接口模式看作层次型的有序树结构，在此基础上通过“搭桥 ( b r i d g i n g ) 的方 式对查询接口的属性实现更准确的匹配聚类。让用户参与到参数的调整设置中， 交互式的设置使得匹配更加精确，而且可以处理一些不确定的匹配，比如同名 异义、同义异名等。( 6 ) d u p l i c a t e s 方法【2 0 】【2 l 】：对大量的数据集进行深度挖掘， 并使用数据集中重复的数据列实例挖掘模式之间的语义匹配关系。( 7 ) s e m i n t 方法【2 2 】：应用从关系数据库系统中得到的元数据和从实例数据获得的统计信息 强化匹配效果。 此类方法的主要优点是针对大量模式知识进行分析处理，能够挖掘出隐藏 较深并具有普遍意义的匹配知识。此类方法存在的主要不足有：( 1 ) 不易获取 正确的匹配训练数据集，其工作量不亚于人工进行模式匹配处理；( 2 ) 一对多 型匹配关系的挖掘规则难以确定；( 3 ) 只能针对特定领域进行处理，不具有通 用性：( 4 ) 阈值难以确定。 综上所述，已有的模式匹配方法各具优点，同时也存在着一些亟待解决的 问题。从以上对当前w e b 数据集成中的模式匹配主要技术分析与比较中，可以 得出：要想既能进行大规模复杂匹配，又不依赖于过于复杂的接口抽取技术， d c m 方法是很好的选择，但是它太依赖于关联度量标准，而且挖掘出的成组属 性中有大量的伪属性组，这在很大程度上影响同义属性的挖掘效果，如果改进 成组属性的度量标准，将能寻求到一些突破。本章的分析与比较正是期望对探 求更多更好的模式匹配方法提供帮助。 第三节主要研究内容和结构安排 从上文的国内外研究现状可以看出，d e e pw e b 模式匹配技术研究是一项极 富挑战性的工作，主要有以下几方面的难点： ( 1 ) 模式匹配首先要有待匹配的对象，即模式，而d e e pw e b 数据源是相当 自治的，它们描述数据的数据模型多种多样，如何规范统一的存储这些异构的 模式不太容易。 ( 2 ) 不同的d e e pw 曲数据源中的模式，可能存在语义冲突、命名冲突、结 构冲突等，这就给准确的模式匹配加大了难度。同时，由于模式是大量存在的， 如何自动高效的进行模式匹配也是一个很大的挑战。 ( 3 ) 全局模式的建立是数据集成查询处理的前提条件，如何通过匹配技术 5 第一章绪论 来构造领域d e e pw e b 全局模式，并且使得这个全局模式的查询能力、结构化程 度等皆达到最优，仍是一个难题。 为了解决这些问题，本文做了以下几方面的工作： ( 1 ) 从互联网上搜集某个领域( 如图书) 的查询接口，通过人工配置的方 式抽取查询接口的模式数据，包括网址信息、所包含的属性、元素、元素值等， 存储在关系数据库中供模式匹配和后续的查询接口集成使用。 ( 2 ) 比较和分析传统模式匹配技术和当前主要模式匹配技术，在总结它们 各自的优缺点的基础上，提出一种基于关联挖掘技术的整体模式匹配方法。在 应用挖掘算法之前，首先进行数据预处理，简化属性名称，尽量减少同一领域 内属性实体的数目，这样的数据更适于挖掘。然后利用正相关关联挖掘和负相 关关联挖掘，着重处理复杂匹配，力求匹配结果更准确、效率更高。 ( 3 ) 设计一种基于匹配结果构建d e e pw e b 全局模式的方法，根据属性在 模式中出现的频率是属性间的同义信息选择属性，再根据属性在源w e b 查询接 口中对应的元素类型、元素数目、可选元素值生成属性的表单控件极其值域， 构建查询效率高、界面结构化程度好的全局接口。 本文共分6 章，各章节安排如下： 第一章介绍d e e pw e b 的研究背景，以及国内外研究现状，并给出主要研 究内容和结构安排。 第二章首先概述一般的d e e pw e b 数据集成框架，在此基础上给出系统架 构设计，简单概括所要解决的问题。 第三章阐述基于数据挖掘的整体性模式匹配方法的原理和具体实现步骤， 重点论述相关挖掘的关键问题相关度的度量方法，包括两个数据项之间的 相关度度量方法和多个数据项之间的相关度的度量方法。 第四章介绍系统架构的另外两个模块查询接口模式抽取和基于模式 匹配结果的查询接口集成的工作，其中查询接口模式抽取采用人工配置的方式 实现，查询接口集成主要依据属性在模式中出现的概率和属性间的同义信息。 第五章对提出的方法和技术进行实验设计和应用，并通过实验数据的分析 和应用效果验证，评价所提出的算法的可行性和有效性。 第六章对所做的工作进行总结，并对后续研究进行展望。 6 第二章系统架构的设计 第二章系统架构的设计 在d e e pw e b 中，大量的在线数据库通过查询接口提供动态的基于查询的数 据访问，而非静态的u r l 链接。每个查询接口通过自己的查询模式( 如a l t l a z o n 的t i t l e ，a u t h o r ，s u b j e c t ，) 接受查询。为了获得自己需要的信息( 比如某一 本书、购买机票等) ，用户常常需要在同一领域的不同查询接口中输入信息进 行搜索。如果存在这样一个统一的查询接口，用户只要输入一次查询信息，就 可以获得不同数据源提供的信息，这将在很大的程度上减轻用户的输入负担， 也将大大提升用户的互联网体验。为了得到这样一个统一的查询接口，不同查 询接口间的模式匹配是一个亟待解决的问题。 本文主要研究d e e pw e b 查询接口的模式匹配技术，为了验证所提出的算法 的可行性和有效性，开发出了一个d e e pw e b 搜索原型系统。由于重点关注模式 匹配，接口抽取及以i j 的工作都由人工配置获得，详细配置工作将在4 1 节给出。 本章给出这个原型系统的设计架构，并在此基础上重点介绍有关模式匹配的工 作。 2 1 节简单介绍一般的d e e pw e b 数据集成框架，2 2 节给出本文原型系统的 设计架构，2 3 节介绍相关的概念定义，2 4 节则重点描述了模式匹配的工作。 第一节d e e pw e b 数据集成框架概述 d e e pw e b 研究目的是为用户提供一个统一的访问途径以自动获取和利用分 布在w e b 上的一些d e e pw e b 的信息。尽管d e e pw e b 中几乎包含了所有我们需 要的信息，但是要想以人工方式利用这些信息实际上是一件非常困难的事情， 而d e e pw - e b 数据集成正是为了以尽可能自动的方式来达到对w e b 数据库中信息 有效利用的目的。在d e e pw | e b 数据集成领域中存在着许多待研究的问题，当前 已有的工作主要集中在以下问题上：w e b 数据库的发现、查询接口模式的抽取、 w e b 数据库的分类、查询接口的集成、查询转换、查询结果的抽取、查询结果 的注释等。有些问题已经得到了较多的研究，而另一些问题还处在研究的初步 阶段。文献【2 3 j 提出了d e e pw | e b 数据集成框架，如图2 1 所示。该框架共分为三 个主要模块：查询接口集成模块、查询处理模块和查询结果处理模块。每个模 7 第二章系统架构的设计 块又分为若干子模块，可以看作具体的研究问题并分别完成特定功能。 图2 1d e e pw e b 数据集成框架 其中： ( 1 ) 集成查询接口生成模块：集成查询接口生成模块为用户提供一个统一 的查询接口，使其可以同时向多个同一领域内的查询接口提交查询，即达到同 时访问同一领域不同w e b 站点后台数据库的目的。这部分共有4 个主要的子模 块：w e b 数据源的发现、查询接口模式的抽取、基于领域w e b 数据源的分类和 查询接口集成。w e b 数据源的发现是指从w e b 中发现具有真正w e b 后台数据库 的网站，然后从中发现可访问这个后台数据库的查询接口。查询接口模式的抽 取是指对前一步获得的查询接口中所包含的属性进行分析和抽取，获取一个查 询接口的模式信息。w e b 数据源的分类是根据已经得到的查询接口的模式信息 确定其对应的w e b 数据源所属的领域，即按照领域对w e b 数据源进行分类。查 询接口的集成是对属于同一个领域的查询接口模式进行集成，得到一个全局的 查询接口，亦即一个统一的查询接口。 ( 2 ) 查询处理模块：查询处理模块将用户在全局的查询接口上填写的查 询转换为到各个w e b 数据源本地查询接口的查询。该部分包含3 个子模块：w e b 数据源的选择、查询转换和查询提交。w e b 数据源的选择指为一个给定的用户 查询从所集成的w e b 数据源中选择合适的数据源进行查询。查询转换是将用户 在集成查询接口上提交的查询转化为到w e b 数据源本地查询接口的查询。查询 提交是指自动地将转换好的查询进行提交。 8 第二章系统架构的设计 ( 3 ) 查询结果处理模块：查询结果处理模块将各个w e b 数据源返回的结果 抽取并合并到一个统一的结构化的模式下，呈现给用户。此部分包括结果抽取、 结果注释和结果合并。查询结果的抽取指从w e b 数据源返回的结果页面中抽取 出真正的有效的查询结果。结果的注释是由于抽取的结果通常缺少足够的语义， 因此要为缺少语义的数据项进行语义注释。查询结果的合并是指把从各个w e b 数据源得到的查询结果进行有效的合并去重，存储在一个统一的模式下。 可见，在上述d e e pw e b 数据集成框架中，有三个方面涉及到模式匹配问题： 查询接口集成、查询转换和结果合并。 本文主要关注图2 1 中的查询接口集成中的模式匹配，研究d e e pw e b 数据 集成中查询接口模式匹配的特点，解决查询接口模式间的复杂匹配问题，给出 基于数据挖掘的整体模式匹配方法，从而实现一次性匹配特定领域的多个模式， 形成n 元复杂匹配( 定义将在后文给出) ，同时此模式匹配的结果对查询转换具 有指导作用。 第二节系统架构的设计 本文将特定领域( 如图书领域) 的多个w e b 查询接口页面作为输入，从查 询接口中抽取模式信息。然后通过数据挖掘的方式进行模式间的复杂匹配，这 个复杂匹配挖掘过程主要包含的处理功能有：数据预处理( d a t ap r e p r o c e s s i n g ) ， 匹配发现( m a t c h i n gd i s c o v e r i n g ) 和匹配构建( m a t c h i n gc o n s t r u c t i o n ) 。最后基 于匹配结果生成全局的查询接口，从而完成查询接口集成。系统的架构如图2 2 所示。其中： ( 1 ) 查询接口模式抽取：主要完成从h t m l 格式的w e b 查询接口中抽取模 式信息的功能。由于作为系统输入的w e b 查询接口页面是h t m l 格式的，而且包 含许多接口外的无用信息，所以在进行模式匹配之前，需要设计一个接口抽取 器，它用于实现从各个参与d e e p w e b 的接口中抽取模式信息。在本文设计的d e e p w e b 搜索原型系统中，采用了人工获取这些接口信息，并配置各种所需要抽取 的模式信息，包括属性信息、元素信息、元素值域、查询接口网址。 ( 2 ) 查询接口模式匹配：对于人工抽取出的原始模式数据( 例如图3 3 所 示接口模式包含属性信息为商品名、著译者、出版社、类别、卓越价、折扣、 出版时间) 进行模式匹配，方法是：首先对这些模式数据在( 主要属性名) 进 9