已阅读5页,还剩67页未读, 继续免费阅读
(计算机应用技术专业论文)基于关联挖掘的深层网络接口模式匹配方法的研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
卜 - 哈尔滨工程大学 学位论文原创性声明 本人郑重声明:本论文的所有工作,是在导师的指导下,由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出,并与参考文献相对应。除文中己注明引用的内容外, 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体,均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签- 7 - ) :西1 殇 1 日期:必p 年弓月c c 日 哈尔滨工程大学 、 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定,即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索,可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文,可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可叼在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) :越沲 日期:神年易月区日 导师( 签字) :形锄主 州q 年弓月l f 日 哈尔滨工程大学硕+ 学伊论文 摘要 随着科技的不断发展,人们对互联网、网络资源已经不再陌生。而随着 时间的推进,网络上的数据资源也日益增多,这些数目惊人的数据资源形成 了很多在线数据库隐藏在深层网络中。用户可以根据自己的需要访问分布在 网络上的各种在线数据库查找相关资源。最直接的访问方法就是填写网络查 询表单,通过查询接口来访问数据库。但是由于不同的查询接口中包含着不 同的属性信息,并且所访问的数据库其模式上存在异构的情况,也就是说不 同的在线数据库查询接口的属性之间存在异构,虽然同义的词汇却不能进行 直接查询。而且随着网络上各领域信息的不断扩充和深入,能够查全和查准 用户所需的信息成为了一个难题。如果可以找到不同查询接口属性相互匹配 的序列,通过不同的查询接口输入信息都可以映射到这个统一序列中,就可 以避免用户为查询某一信息而反复查找不同的页面。因此本文对不同页面的 查询接口属性进行了模式匹配来解决上述问题。 针对于深层网络查询接口模式匹配的研究需要,本文借鉴基于国内外已 有的有关深层网络查询接口的研究成果,提出了一种基于关联挖掘的深层网 络查询接口模式匹配的方法,在对查询接口属性进行匹配的模块中,本文还 提出了一种简单而高效的匹配算法。实验表明整个处理过程是低复杂度且有 较高准确率的。 关键词:深层网络;网络查询接口;关联挖掘;模式匹配 哈尔滨工程大学硕七学位论文 a b s t r a c t a l o n gw i t ht e c h n i c a lu n c e a s i n gd e v e l o p m e n t ,p e o p l eh a v ea l r e a d yb e e n u n f a m i l i a rw i t hi n t e m e ta n dn e t w o r kr e s o u r c e s a n dw i t ht h et i m ea d v a n c e m e n t , t h ed a t ar e s o u r c e so ft h en e t w o r kh a sb e e ni n c r e a s i n g ,t h e s ea s t o n i s h i n gd a t a r e s o u r c e sf o r m e dan u m b e ro fo n l i n ed a t a b a s e st oh i d ei nt h ed e e pw e b u s e r sc a n a c c e s sav a r i e t yo fo n l i n ed a t a b a s e sa n df i n dr e l a t e dr e s o u r c e sa c c o r d i n gt ot h e i r o w nn e e d t h em o s td i r e c tw a yi st of i uaq u e r yf o r mi nt h ew e bp a g e ,a n dt o a c c e s st h eo n l i n ed a t a b a s e st h r o u g ht h eq u e r yi n t e r f a c e h o w e v e r , d i f f e r e n tq u e r y i n t e r f a c ec o n t a i n st h ed i f f e r e n ta t t r i b u t ei n f o r m a t i o n ,a n dt h e r ea r eh e t e r o g e n e o u s s i t u a t i o n si nt h ed a t a b a s es c h e m a i no t h e rw o r d s ,t h e r ea r eh e t e r o g e n e o u s s i t u a t i o n si nt h e q u e r yi n t e r f a c e o fd i f f e r e n to n l i n ed a t a b a s e ,a l t h o u g ht h e s y n o n y m o u sw o r d sc a n n o te a r lyo nt h ed i r e c fi n q u i r y m o r e o v e r , a st h ev a r i o u s d o m a i n si n f o r m a t i o nc o n s t a n t l ye x p a n d i n gi nt h ew e b ,u s e r sw a n tt of i n ds o m e i n f o r m a t i o nw h i c hh a sh i g hr e c a l la n dh i g hp r e c i s i o nh a sb e c o m ead i f f i c u l t p r o b l e m i fw e c a nf i n dt h es e q u e n c ew h i c hh a st h em a t c h e do fa t t r i b u t e si nt h e d i f f e r e n tq u e r yi n t e r f a c e ,u s e ri n p u ti n q u i r yi n f o r m a t i o nt h r o u g hd i f f e r e n tq u e r y i n t e r f a c ec a nb em a p p e dt ot h i su n i f o r ms e q u e n c e a n dt h i sm e t h o dw i l la v o i d s e a r c hd i f f e r e n tw e bp a g e si no r d e rt oi n q u i r es o m ei n f o r m a t i o n t h e r e f o r e ,t o s o l v et h ea b o v ep r o b l e m s ,t h i sa r t i c l ew i l ld ot h es c h e m am a t c h i n go nt h ed i f f e r e n t q u i r ei n t e r f a c e mt h en e e d so fd e e p w e bq u e r yi n t e r f a c es c h e m am a t c h i n gr e s e a r c h ,b a s e d o nt h er e s u l to fr e s e a r c ho ft h ed e e p w e bq u e r yi n t e r f a c es c h e m am a t c h i n gb o t hi n d o m e s t i ca n da b r o a d ,t h ep a p e rp r o v i d ea ne f f e c t i v es c h e m am a t c h i n gm e t h o d w h i c hb a s eo nc o r r e l a t i o nm i n i n g i nt h em o d u l eo ft h ea t t r i b u t em a t c h i n g ,t h i s p a p e rp r o p o s e das i m p l ea n dh i g h l ye f f e c t i v ec o r r e l a t i o na l g o r i t h mt oe n s u r et h e 一 哈尔滨工程大学硕士学传论文 a c c u r a c yo fm a t c h i n g e x p e r i m e n t sp r o v e dt h a tt h e w h o l ep r o c e s si sal o w c o m p l e x i t ya n dh a st h eh i g ha c c u r a c yr a t e k e yw o r d s :d e e p w e b ;w e bq u e r yi n t e r f a c e ;s c h e m am a t c h i n g ;c o r r e l a t i o nm i n i n g 哈尔滨t 程大学硕士学位论文 目录 第1 章绪论1 1 1 课题研究背景及意义”1 1 1 ,1 课题的背景1 1 1 2 课题的意义3 1 2 国内外研究现状一4 1 2 1 深层网络的研究现状4 1 2 2 深层网络查询接口复杂匹配的研究现状6 1 3 本文主要研究内容和预期研究成果1 2 1 4 本文的组织结构安排12 第2 章深层网络查询接口复杂匹配相关工作1 4 2 1 深层网络查询接口简要介绍1 4 2 2 查询接口复杂匹配的主要问题1 5 2 2 1 目前查询接口复杂匹配方法主要出现的问题15 2 2 2 解决查询接口模式匹配的出发点1 6 2 3 模式匹配17 2 3 1 模式匹配的原理1 7 2 3 2 模式匹配的分类18 2 3 3 模式匹配的方法2 1 2 4 关联挖掘2 2 2 4 1 关联挖掘的定义2 2 2 4 2 关联规则的分类2 3 2 4 3 关联规则挖掘的相关算法2 4 2 5 本章小结2 5 第3 章基于关联挖掘的查询接口模式匹配方法2 6 哈尔滨工程大学硕士学位论文 3 1 研究概述2 6 3 2 查询接口模式匹配框架2 7 3 3 查询接口的数据准备2 8 3 4 查询接口属性的匹配3 0 3 4 1 匹配挖掘3 0 3 4 2 候选匹配选择3 2 3 5 匹配发现的核一t 5 算法3 3 3 5 1 匹配发现算法的提出3 3 3 5 2 查询接口模式匹配的核心算法3 4 3 6 本章小结3 6 第4 章查询接口模式匹配的设计实现3 7 4 1 查询接口模式匹配的总体目标3 7 4 2 查询接口模式匹配的设计框架3 7 4 3 查询接口模式匹配的具体实施的策略l “3 9 4 3 1 属性表单的提取3 9 4 3 2 标记属性表的生成4 2 4 3 3 同义匹配的发现4 4 4 3 4 候选匹配的选择4 8 4 4 应用平台和工具5 0 4 5 本章小结51 第5 章实验结果分析5 2 5 1 数据集的选取5 2 5 2 实验测试标准5 2 5 3 实验结果5 3 5 4 本章小结:5 7 结论”5 8 参考文献5 9 哈尔,, 只- 一t 干f 2 1 大学硕十学位论文 攻读硕士学位期间发表的论文和取得的科研成果6 3 致谢6 4 随着w e b 的飞速发展,其蕴涵的信息量也在急剧增长。人们急需一种能 对w e b 上信息进行自动搜索的工具。然而自动获取w e b 中的有价值信息、 艮 有挑战性,原因在于w e b 中的信息主要通过网页的形式对外发布,而由文本 和超链接构成的网页数量惊人,信息丰富;由不同的个人或群体开发的网页, 形式与内容有很大差异,且分布在地球上i m t e m e t 连接的每一个角落,这就 造成了w e b 数据的异质性和缺乏结构性。 到目前为止,为了有效地利用w e b 上的信息,所采用的方法涉及了广泛 的领域:数据挖掘、机器学习、自然语言处理、统计分析、数据库和信息检 、 索等。 针对于庞大的w e b 资源,本文可以按其所蕴涵信息的“深度”可以划分 为表层网络和深层网络两大部分。那些利用传统的搜索引擎通过爬虫程序或 爬行整个w e b 表面页面来创建页面索引,可以发现这些页面通常是静态链接 产生的。这类页面被称为表面可索引的信息一表层网络( s u r f a c ew e b ) 。而那 些随着网络朝着深度方向发展,隐藏于网络深处的大批高价值、高质量的信 息。这些信息没有静态链接,需要用户向表单接口提交查询,由站点的后台 数据库动态产生链接返回的页面。这类页面被称为深层网络( d e e pw e b ) t 1 1 。深 层网络与表层网络的本质区别在于,表层网络包括的内容基本都是非结构化 的h t m l 信息,对搜索引擎而言是相对可见的,因此又被称为v i s i b l ew e b : 而深层网络的内容存储在w e b 中可访问的在线数据库中,是相对不可见的, 于是又被称为i n v i s i b l ew e b t 2 。 与表层网络相比,深层网络蕴藏了更加丰富,更加“专业”( 专注于某一 哈尔滨丁程大学硕士学传论文 领域) 的信息。在2 0 0 0 年7 月,b r i g h t p l a n e t 对深层网络做了一次较为全面 的宏观统计,发布了深层网络的白皮书( 在该文中b r i g h t p l a n e t 对深层网络的 定义主要指的是w e b 数据库) ,指出整个w e b 上大约有4 3 ,0 0 0 9 6 ,0 0 0 个w e b 数据库,并从宏观上对深层网络做了定量的调查统计,下面列出其中部分的 调查结果: 深层网络页面信息大约是表层网络页面的4 0 0 5 0 0 倍,大约有3 0 7 ,0 0 个站点,4 5 0 ,0 0 0 个后台数据库和1 ,2 5 8 ,0 0 0 个查询接口,并且仍在迅速 增长。从2 0 0 0 年到2 0 0 4 年,增长了3 7 倍。 首先,整个深层网络覆盖了世界的各个领域,例如商业、教育、政府等 等。但就单个深层网络而言,有超过5 0 的深层网络内容是特定于某个领域 的即领域专一化的。 其次,深层网络中的后台数据库大多是结构化的,其中结构化的数据库 是非结构化的3 4 倍之多; 再次,w e b 数据库查询接口往往位于站点浅层,9 4 之多的大量w e b 数 据库查询接口可以在站点前3 层发现。而且对深层网络的数据访问量比表层 网络要高出1 5 ,其信息质量远远高于表层网络。 最后,深层网络上9 5 的信息是可以公开访问的,即可以免费获取。目 前一些深层网络目录服务已经开始索引w e b 数据库,但是它们的覆盖率比较 小仅为o 2 1 5 6 。 综上所述,深层网络具有信息量大、价值高、质量优、结构化好等特点, 然而由于目前w e b 数据库存在规模大、自治性、异质性、动态性等问题,要 想全面而准确的搜索出深层网络中的信息是一件迫切需要而又非常困难的事 情。因此对于深层网络的研究【3 】日益成为研究热点。目前主要关注于以下几 个关键问题:深层网络站点的发现和分类、查询接口集成、数据抽取、实体 识别、结果合并等。 模式匹配是查询接1 2 1 集成至关重要的一步,也是今后研究信息集成和信 息挖掘的基础,必将成为下一代信息集成技术和搜索引擎技术研究的一个起 2 配网页接口在相同的领域( 比如:买书、找工作、预定飞机票) 是带有广泛应 用的问题。尤其,对于同一个问题经常需要去搜索可替代的查询源,比如购 买一本书( 或者飞机票) ,要登录很多在线的书店或者提供飞机票购买的网站。 进而就需要解决多个接口模式之间的匹配。 然而深层网络中查询模式间的匹配不单单是简单的l :l 匹配还产生了复 杂的匹配【3 4 】。复杂的匹配是将一组有m 个属性的属性组与另外一个有n 个 属性的属性组关联起来,这样的方式也被称为m :n 匹配。查询接口中复杂的 匹配确实是存在的,并且也是很频繁的。比如,以书籍这个领域为例,对于 f i r s tn a m e ,l a s tn a m e 这样的一个属性组来说,a u t h o r 是它的一个同义词, a u t h o r = f i r s tn a m e ,l a s tn a m e ) ;在飞机票领域, p a s s e n g e r s = a d u l t s ,s e n i o r s , c h i l d r e n ,i n f a n t s 。因此,发现复杂的匹配对于整合深层网络信息来说是非常 关键的。 针对于复杂匹配,在模式中l a s tn a m e 和f i r s tn a m e 是经常共存的,但是 它们在一起就很少和a u t h o r 这个词共同出现。也就是表示同义的属性或属性 组之间是不共存的。考虑到数据挖掘中关联挖掘的一些算法对属性的相关性 具有很好的研究,可以利用它来识别同义属性。基于这样的观察本课题提出 一种基于数据挖掘技术的模式匹配新方法,尤其是在给定了w e b 查询接口抽 取模式的情况下。 本课题研究以实现高效深层网络查询接口模式匹配为背景,研究一种基 于关联挖掘的深层网络查询接口模式匹配的方法,重点研究基于关联挖掘的 匹配算法,通过考虑属性的共存性来挖掘复杂的相匹配的属性信息。本课题 的研究具有重要的理论意义,研究为人们获取和利用深层网络资源提供了一 互联网从上个世纪末才传入我国,发展时间太短,人们对网络的研究并不深 入。而深层网络是随着网络的快速发展出现的,因此绝大多数网络用户对深 层网络的概念还很陌生,学者们也并不太重视这个问题,相关论述较少,其 中有关的论述都是综述性的介绍国外深层网络研究状况,具体的深入研究尚 处于空白阶段。 就国外而言华盛顿大学的s h o p b o t m 研究小组:s h o p b o t 是一个针对 消费产品的比较代理,它利用特定领域的启发式方法来填写表单以比较其领 域内的商业产品。其聚焦于处理卖主站点的表单提交页面所返回的的产品列 表。s h o p b o t 操作分为两个阶段:离线学习阶段和在线产品比较阶段。在学 习阶段,确定如何填写站点表单,以及对产品站点结果页面进行分析获取其 站点模式信息。在比较阶段,利用得到的站点模式结构来抽取结果信息,寻 找满足用户要求价格最优的产品,最终将这些产品信息格式化输出。可以看 出其研究领域非常狭窄,不适用于大规模的信息集成。 斯坦福大学的w e b b a s e 6 】研究小组:d a v u l c 等人很早就提出了设计 w e b b a s e 的框架,它可以通过工具帮助用户实现特定领域复杂搜索服务。 斯坦福大学的h i w e t n :h i d d d e nw e be x p o s e r ( h i w e ) 是s t a n d f o r d 大学另 一个研究项目。r a g h a v a na n dg a r c i a m o l i n a 设计了一种可以抽取深层网络信 息的爬虫。在此系统中爬虫管理器负责管理搜集过程。它对下载的w e b 页面 进行分析,包含表单的页面被送到表单处理器中处理。表单处理器首先从页 面中抽取表单结构再从预先准备好的数据集中选择数据自动地完成表单的填 4 , 一 哈尔滨t 稃大学硕十学位论文 写,然后将合成的u r l 提交爬虫管理器去下载响应的结果页面。由于需要系 统自动完成表单填写,所以要求用户预先准备相应的表单数据集。h i w e 只能 面向特定的领域使用,而且必须在人工辅助下完成。因此存在很大的局限性。 哥伦比亚大学的q p r o b e r _ f 8 】研究小组:哥伦比亚大学的p a n a g i o t i s g i p e i r o t i s 等人研究了自动地将w e b 页面所连接的后台数据库进行分类的方 法。它首先使用机器学习技术生成一套基于规则的分类器( c l a s s i f i e r ) 。然后抽 取分类器规则和基本u r l 组合成查询u r l ,对后台数据库进行查询探测, 计算查询结果数。他们的算法最后根据查询结果数对数据库进行分类。其研 究只集中在怎样针对文档数据库的分类上面,而大量的深层网络数据库提供 的内容是结构化的数据。 伊利诺斯大学m e t a q u e r i e f 9 1 研究小组:该小组建立一个元查询系统 ( m e t a q u e r y ) ,目标是有效获取w e b 上结构化的信息。首先,m e t a e x p l o r e r 项 目聚焦于发现、模型化和重构w e b 数据库来建立一个可搜索的数据源知识库。 特别是,m e t a q u e r y 系统开发了一个w e b 数据库搜索引擎,它可以有效发现 w e b 上含有数据库的站点,设计模型来描述这些数据库,设计包装器自动抽 取这些模型中的参数,重组和索引可搜索的w e b 数据库。其次,m e t a e x p l o r e r 项目聚焦于集成在线数据库。同时还研究了数据源选择,查询转换和模式集 成问题。在研究大规模信启、集成的过程中将依赖于前面所建立的数据源知识 库,其重点研究了动态信息集成技术。与传统的信息检索不同,所设计的 m e t a q u e r y 系统是动态的,即可以将实时发现的新数据源加入系统中,同时动 态选择数据源将用户查询进行相应转换,从而获取用户查询结果。 微软亚洲研究院第三代搜索引擎:微软亚洲研究院早在2 0 0 4 年就提出抽 取基于关键字接口深层网络信息【1 0 1 。近来提出的第三代搜索要对深层互联网 搜索与挖掘,不仅找到更多的结果,而要更加智能化、人性化、更加精确、 能够理解用户需要什么结果。 就国内而言目前国内对深层网络方面的研究尚处于学习和跟踪探索 阶段。经查新报告表明:综合国内检出文献,课题在所检文献内未见相同报 哈尔滨- 丁程大学硕士学位论文 道。国内研究单位及相关文献非常少。 集成的研究i n 走在了国内研究的前列, 人民大学的孟小峰等对深层网络系统 其工作搜索系统基本上实现了深层网 络系统集成的集成的主要内容。上海交通大学宋晖等人提出基于标记树的对 象抽取( t a g t r e e 。b a s e do b j e c te x t r a e t i o n ) 方法自动地从w e b 页面中抽取深层网 络信息,然后在此基础上给出了结构化的深层网络信息查询算法。另外苏州 大学的郑冬冬,赵朋朋等人也对深层网络的访问进行了相关的研究,在“爬 虫研究与设计”一文中提出使用启发式规则集和领域本体知识库来自动发现 相关表单,填写表单,同时识别和收集相关结果页面。 1 2 2 深层网络查询接口复杂匹配的研究现状 目前基于模式的匹配主要有以下几种方法:基于统计模型的方法( m g s : 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 ) i n 、基于双重相关性挖掘方法 ( d c m :d u a lc o r r e l a t i o nm i n i n g ) i t 】、基于聚类的交互方法( i n t e r a c t i v e c l u s t e r i n g b a s e d ) 【1 3 】和基于语料库的匹配方法( c o r p u s b a s e d ) 】。 1 基于统计模型方法 统计模型方法是一种全局性评估方法。在对深层网络的调查中,观察到 两个问题:第一增长的资源;第二,聚合的词表:同一领域模式词表源的聚 集趋向于集中在一个相对小的范围内。就是说,随着数据源的增长,他们的 词表集趋向稳定,这就表明同类资源有一些共同的属性词汇。基于这种发现, b h e 等开发了m g s 框架。m g s 方法假设每个应用领域有一个存在的隐式生 成模型,这样就可以把模式看成是从带着一些可能出现行为的模型中产生的 实例。因此,模式匹配就被转化为发现含有一系列模式实例的隐式模型。这 种假设理论在处理模式匹配问题上开辟了一条与众不同的道路:如果一个隐 式模型存在,它的发现将揭示词表结构。这样一种同一领域中所有属性的模 式整合将包含他们相应的成对属性。 m g s 方法主要分为三步: 首先,假设建模:指定一个假设的隐式生成模型的参数化结构。特别地, 6 哈尔滨工程大学硕十学位论文 这样的模型应该可以捕获要进行模式匹配的目标问题。定义模式模型m ( v , c ,p 。,p a ) ,词汇表v 是一组属性的集合,其中包含了所有频繁使用的属性, 概念划分集c 包含了所有同一概念的属性集,p 。是概念概率函数值,即某个 概念在模式产生中出现的概率,p 。是属性概率函数值,即某个属性在模式产 生中出现的概率。对于一个模式集合i ,只有当概率p r ( i m ) 0 时,模式模型 m 才能生成模式集合i 中所有的模式实例。 其次,假设产生:产生所有“一致”的模型,这些模型可能能够实例化 观察到的模式实例。概率p d f m ) 的大小是由概念概率函数值p 。和属性概率函 数值p 。共同决定的因此p 。和p 。应尽量大,使得概率p r ( u m ) 尽量大,即增大 模式模型m 生成模式集合中所有模式实例的可能性。用概念c i 的所有属性 a i 在模式集合中出现的频率之和表示概念c i 的概率函数值p 。,用属性a j 在 模式集合中出现的概率表示属性a i 的属性概率函数值p 。,计算p 。和p 。值的 公式( 2 1 ) 如下所示: 口+ 卢半+ j - - 南口。, 其中o j 表示属性a 在模式集合中出现的频率( 包含属性a i 的模式实例的 数量) ,l i i 表示模式集中模式实例的总数;qi 表示概念c i 的概念概率函数值, bj 表示概念c i 中任意属性a i 的属性概率函数值;a j c i o 表示概念c j 中 包含的所有属性出现的频率之和。 最后,假设选择:选择与实例有充足统计一致性的模型。这样的潜在模 型是最可能产生输入模式的,因此它的结构将能回答目标问题。应用x2 假设 检验法来进行匹配选择。设有r 个模式:1 1 ,1 2 ,i ,对应的出现可能性概率为 p 1 ,p 2 ,p r , d :y7 ! 鱼二型 一严1 啊。 ( 2 2 ) 在公式( 2 2 ) 中n = l i 。设a 为问题有意义条件下的阈值,要找到一个b , 使得p , d 2 b 产a ,且d 2 是自由度为卜1 的x2 分布。对于每个产生的模型计算 哈尔滨丁稗大学硕士学位论文 d :( m i ) ,比较它与b 的大小,若小于b ,则选择该模型,否则舍弃。 为了证明m g s 发现隐式模型的思想,看下面的例子。 用m g s 框架发现5 5 个查询书籍的数据源中简单的1 :1 匹配。结果表明: 在查询书籍的领域中,隐式结构中的1 2 个频繁属性能够被区分出来: t i t l e ( t i ) , a u t h o r ( a u ) ,i s b n ( i s ) ,k e y w o r d ( k w ) ,p u b l i s h e r ( p u ) ,s u b j e c t ( s u ) ,l a s tn a m e ( 1 n ) , f o r m a t ( f m ) ,c a t e g o r y ( c g ) ,p r i c e ( p r ) ,f i r s tn a m e ( f n ) ,p u b l i c a t i o nd a t e ( p d ) 。能 够产生两个模型:m l = ( t i ) ,( i s ) ,( k w ) ,( p r ) ,( 钿) ,( p d ) ,( p u ) ,( s u ,c g ) ,( a u ,i n ) ,( 缸) , m 2 = ( t i ) ,( i s ) ,( k w ) ,( p r ) ,( 矗n ) ,( p d ) ,( p u ) ,( s u ,c g ) ,( a u ,f n ) ,( i n ) ) 。 图2 1m g s 方法应用在书籍查找领域的案例 从图2 4 可以看出,模型里把属性分割成概念,每个概念里包含同义属性, 如概念c 】中包含a u 和l n 两个同义词。被发现的模型可以正确的把同义属性 进行归类。但是缺陷是,这种方法只能处理1 :l 的匹配。它可以匹配a l l 和l n , 但是它不能进一步匹配m 、l n 属性组和a u 。也就是说,它不能处理复杂匹配。 不对词汇的语义进行研究,只能获得统计上的精确度。 2 基于双重相关性挖掘方法 b h e 等学者提出的双重相关性挖掘方法是一种局部性评估方法。复杂模 式匹配也就是m :n 匹配,比如书籍领域, a u t h o r = f n s tn a m e ,l a s tn a m e 。 可以发现成组属性( 如:f i r s tn a m e ,l a s tn a m e ) 在查询界面中是同时出现的, 哈尔溟丁挥大学硕十宁何论文 因此是积极相关,或正相关的。而同义属性几乎不同时出现,因此是消极相 关,或负相关的。基于此开发了d c m 框架,它采用关联挖掘的方法来探索 同时出现的属性模式,利用积极相关和消极相关双重挖掘来同时处理简单的 1 :1 匹配和复杂的m :n 匹配。 d c m 方法主要分为三步: 首先,组发现:挖掘积极相关的属性得到潜在的属性组,利用积极相关 度量标准,如公式( 2 3 ) : f,r 州a t , a 户 1 - 州以al 芦吼t ( 2 - 3 ) l o , o t h p r w i s e 其中,( 么户,a ,) :业,f 1 1 表示属性a p 、共同出现的模式实例, 1 ,卜 f 0 1 、r i o 表示属性a p 、单独出现的模式实例数,f o o 表示属性a p 、都没有 出现的模式实例数。f i + 与f + 1 分别为属性a p 、在模式集合中出现的总次数, 缸与分别为属性没有在模式集合中出现的总次数,h 为模式集合中包含 模式实例的个数。潜在的属性组最后并不一定都能保留,只有与其他属性组 有同义关系的组才能保留下来。如果所有的查询界面上都用 f i r s tn a m e ,l a s t n a m e ,不用 a u t h o r ) ,那么潜在的组 f i r s tn a m e ,l a s tn a m e 就没有用,因为 它没有匹配的需要。 其次,匹配发现:在组发现的基础上,挖掘消极相关的属性组以得到潜 在的复杂匹配。利用消极相关度量标准,如公式( 2 4 ) : ff 耽( 么,4 ) = n ( a ,4 ) 2 笄 ( 2 4 ) j i + 作为一种统计的方法,关联挖掘能发现正确的语义匹配,但是会由于巧 合关联的存在而出现错误。比如,在书籍领域,挖掘结果会发现两个匹配组: m 1 : a u t h o r = f i r s tn a m e ,l a s tn a m e 和m 2 : s u b j e c t = f i r s tn a m e ,l a s tn a m e , 很明显,m l 是正确的,而m 2 是错误的。导致m 2 出现的原因是 f i r s tn a m e , 9 哈尔滨工程大学硕士学位论文 l a s tn a m e 】和 s u b j e c t 不同时出现,被误认为是消极相关了。这种偶然负相关 性对匹配的准确度有很大影响。 最后,匹配选择:在发现的匹配中进行筛选并构建模型。d c m 框架中开 发了一个迭代的算法,每次选最高可信度的匹配来逐步构建模型,通过迭代 算法,每次选出可信度最高、更消极的匹配,可以很好的构建出模型。 3 基于聚类的交互式方法 基于聚类的交互式方法利用查询接口丰富的结构信息,把接口模式看作 层次型的有序树结构。叶子元素对应于接口中的一个属性元素,内部元素对 应于一组属性元素,有相同父节点的按照相应的顺序形成兄弟元素。这样一 棵语义有序树就对应了模式结构。在此基础上通过“搭桥”( b r i d g i n g ) 的方 式对查询接口的属性实现更准确的匹配聚类。针对复杂的1 :m 匹配,将映射 类型分为:a g g r e g a t e 和i s a 两种,并让用户参与到参数的调节设置中,交互 式的设置使得匹配更加精确,而且还可以处理一些不确定的匹配,比如同名 异义、同物异名等。主要过程如下: 首先,找到l :m 的初始化匹配:有共同父结点p 的属性f ;间是互为兄弟 的,如果p 与某个结点e 的标签高度相似,且e 的域的子域集与各属性间 有一一对应的匹配关系,那么就认为e 与 f i ,f n 间是1 :m 的映射; 其次,聚类阶段:给定一个阈值t 。,把每个属性看成一个聚类好的簇, 再利用属性相似度公式( 2 5 ) : 丸宰l i n g s i m ( e , 门+ 九宰d o m s i m ( e , 门( 2 5 ) 其中入1 s 、入d ;是权值系数,l i n g s i m ( e ,f ) 与d o m s i m ( e ,f ) 分别是语言相似度 及域相似度,计算该相似度是否大于阈值t 。,如果大于则选出具有最大相似 度的簇合并形成新簇,同时删除与原来簇有关的簇和它们本身,否则过程终 止。重复上述过程,找到1 :1 的匹配; 最后,结合找到的初始集和聚类阶段得到1 :1 匹配结果,用推理过程找 出最终的1 :m 匹配结果。在匹配过程中,该方法加入了用户交互的策略来改 1 0 哈尔滨工程大学硕十学位论文 善参数的设置。大部分方法中的参数设置都是基于某个领域的,因此当把匹 配方法应用于别的领域时,参数设置要进行调整,否则准确性难以保证,而 且可能会造成误匹配和漏匹配。而该方法在匹配过程中,一旦有歧义和异常 匹配出现时,会列举出匹配对象的标签和实例,让用户回答是否,如果回答 是,则降低阈值范围的高边界值,否则增加低边界值,初始分界值设在中间。 这样使用最小的交互操作而达到最精确的参数设定,在其他方法中是没有的。 通过上述分析,可以发现基于聚类的方法首先要通过接口抽取器抽取出层次 化的模式,但即使是一个“平”的抽取,已足够影响匹配的性能,所以接口 抽取是其中一个很有挑战性的任务。 4 基于语料库的匹配 基于语料库的匹配:该方法先搜集各领域模式属性的多个同义表达方式 及基本映射关系,组成语料库。利用找到的映射属性来构建新的增强型模型, 来更精确的匹配。比如某个模式s 中的属性s ,它不属于语料库,但是可以 在库中找到它的同义属性e 、f 。由于e 、f 属于不同的模式,所以在某些方面 不同于s 。e 与s 可能有相同的实例信息但是名称不同,这样就可以为s 建立 更具普遍性的名称模型;f 与s 可能名称相同实例也相同但在与其他模式中元 素的关系上不同,这样就可以为s 建立更好的关系模型。这种增强性的方法 利用其他元素的优势为原元素建立了良好的模型,在匹配中可以收到更好的 效果。然后在语料库中把属性聚类成概念对模式出现情况进行统计性的估计, 为每个属性与其相似概念建立出现概率对应表,推理出以下域约束规则:相 同概念,即两个属性在语料库中要同时相似于同一概念才能匹配;相似表, 指对每个模式,定义表概念t i 和列概念c i ,计算条件概率p ( t i q ) ,以识别某个 内容在什么概念下出现。比如p r o d u c t l d 列可能出现在表p r o d u c t 中,而不太 可能出现在表w a r e h o u s e 中。在这种定义下,如果属性e 与f 匹配,那么e 对应的表要与包含f 的表相似;相邻,如果e 与f 匹配,那么所有与f 相关的 哈尔滨t 稗大学硕十学位论文 属性也要与e 相关;有序性,如果属性e 、f 匹配,那么它们所在的语料统计 数据不能冲突。根据这些约束规则将前一阶段得到的侯选匹配模型进行剪枝, 得到更准确的匹配。这种匹配方法要建立健壮性极强的语料库,才能起到增 强效果,而且目前只能进行1 :1 匹配,不适用于复杂匹配。 1 3 本文主要研究内容和预期研究成果 深入研究现有的深层网络信息获取的方法、模式匹配方法以及数据挖掘 中关联挖掘的相关方法。提出一种基于关联挖掘的深层网络查询接口模式匹 配的方法。重点研究基于关联挖掘的模式匹配的方法,将关联规则应用于匹 配发现上,从算法上提高匹配的精确性和高效性。最终提出一种高效的深层 网络查询接口模式匹配的方法。具体内容如下: ( 1 ) 深入了解深层网络查询接口模式匹配应该解决的相关问题。 ( 2 ) 对传统的几种模式匹配方法进行分析比较,并结合关联规则对匹配 方法提出改进方案或综合各种方法的特点提出改进方案。 ( 3 ) 深入研究各种模式匹配发现的算法,并提出一种改进的高效的匹配 发现算法。 ( 4 ) 提出匹配结果验证方法,选取深层网络信息资源对查询接i z l 模式的 匹配过程的性能进行测试。 1 4 本文的组织结构安排 本文共分五章,结构安排如下: 第1 章绪论,介绍课题的研究背景和意义。分别介绍了表面网络和深层 网络的定义,由于深层网络蕴含的信息量巨大,而且处于动态地增加状态, 所以对深层网络的相关研究就更具有重要意义了。在访问网络数据源中查询 接口是进入深层网络资源的唯一入口,针对于各异的查询接口模式来说,建 1 2 哈尔滨t 程大学硕士学位论文 立统一的查询接口己然成为集成深层网络资源的首要问题。为此,本章总结 分析了深层网络和网络查询接口模式匹配的研究现状。 第2 章介绍了与查询接口模式匹配相关的研究,其中包括深层网络查询 接口模式匹配的主要问题和解决问题的出发点,模式匹配的定义、分类和方 法以及关联挖掘的定义和方法。 第3 章是本文的核心算法章节。在前两章的理论研究基础上,本章细化 了深层网络查询接口模式匹配过程中各模块的中需要的处理技术。并详细研 究了核心模块接口属性的匹配,并提出了简单而有效的核心算法用于查 询接口中属性的匹配。 第4 章主要叙述了基于关联挖掘的深层网络查询接口模式匹配的处理框 架。该框架分为两大模块,四个部分来完成。其中第二个模块的两个部分: 匹配属性生成和候选匹配选择均为本文的核心部分,在本章中对各个处理部 分的功能和实现也详细介绍i 。 第5 章是实验评估。通过实验对本文所提出了基于关联挖掘的查询接口 模式匹配方法有效
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 六年级语文上学期整本书阅读《童年》期末复习教学设计
- 初中语文七年级下册紫藤萝瀑布教学设计与实施
- 高二英语选择性必修二 Unit 5 Reading and Thinking 语篇深度解读与默写训练教学设计
- 初中语文九年级中考作文选材教学设计
- 小学五年级美术《生活中的标志》教学设计
- 高一英语必修第一册Unit 3 Sports and fitness 单元整体教学设计
- 高一体育五步拳教学设计
- 小学四年级劳动教育煎牛排教学设计
- 小学四年级劳动《花瓶罩饰》项目化教学设计
- 八年级语文下册第三单元养性怡情知识清单教学设计
- 抖音直播运营中心薪酬绩效考核实施管理方案
- 2026年学生入团考试题库及参考答案
- 2027届河南省部分城市联考高三上学期11月阶段检测历史试题(含答案)
- 2026年宁夏水务投资集团有限公司招聘笔试参考题库附带答案详解析版
- 2026秋北师大版选择性必修第一册Unit 1-3 句子语法填空练习(备考期中)
- 智能体电脑行业王伟东白皮书
- 秦皇岛市建设现代有轨电车项目调研报告
- 2026秋新教材苏教版五年级上册数学第七单元 用字母表示数量关系(一) 教案(共7课时)
- 《中药炮制技术》教案-13模块十三 其他炮制技术
- 2026年辅警笔试的题库及答案
- 多模式镇痛在加速康复外科中的应用现状
评论
0/150
提交评论