（模式识别与智能系统专业论文）基于条件概率图模型的deep+web数据抽取与集成研究.pdf

摘要 摘要 目前，大量的结构化数据蕴藏在d e e pw e b 中，但是由于w e b 网页的半结构性、 w e b 超链接的自由无序性以及d c e pw e b 数据的海量性、异构性、多样性、动态性 等特点，使得d e e pw e b 数据抽取与集成成为当前砸待解决的研究课题。概率图学 习模型是机器学习领域当前异常活跃的研究热点之一。它在数据挖掘、信息抽取、 信息检索等领域得到了广泛而成功的应用。本文将条件随机场，一种序列条件概 率无向图模型，引入到d e e pw e b 数据抽取和集成的研究中，对其中的查询接口发 现、分类、集成以及查询结果数据的抽取和重复记录检测等多个具有挑战性的实 际问题进行了系统和深入地研究。针对不同问题提出了改进的条件随机场模型、 新的算法或新的实现策略，主要工作概括如下： ( 1 ) 针对d e e pw e b 查询接口自动搜索和发现问题，提出了基于条件随机场的 网页链接路径学习模型，给出了使用增强学习技术对超链接进行评分的算法。实 验结果表明，搜索查询表单的性能明显优于其它袁单爬虫。 ( 2 ) 使用条件最大熵模型处理d e e pw e b 查询接口识别和领域分类问题。提 出了一种仅利用表单结构特征来识别在线数据库查询接口的通用方法。此外，利 用最大熵分类器的优点，融合查询表单的结构、内容等多种特征来实现查询表单 的领域分类。实验结果表明。该方法分类准确率高。 ( 3 ) 利用有序树模型来表示抽取的查询接口中查询项、字段和属性问的层次 关系。提出了一种层次序列条件随机场模型，通过对查询表单中的查询元素进行 联合标注分类，实现异构查询接口模式匹配。实验结果表明，该方法具有较高的 匹配准确率和跨领域通用特性。 ( 4 ) 提出了_ 种基于标记树的网页区域分割方法，并且结合网页聚类和跨网 页数据区域匹配技术来识别网页中的动态数据区域。针对多源w e b 记录语义标注和 集成问题，提出一种混合跳链条件随机场模型。该模型通过将最大熵和线性链条 件随机场混合，能够利用相关数据库中的记录作为训练样本识别抽取数据的语义 标注，从而减少了对手工标注样本的依赖：此外增加对跳边的支持，使得模型能 够处理状态变量问的长距离依赖。 ( 5 ) 最后，针对重复w e b 记录检测问题。提出种条件训练字符串编辑距离 模型，可以从训练样本数据中自动学习字符串对的相似函数。此外，使用支持向 量机联合多字段相似度实现重复记录检测。实验结果表明。避免了采用固定距离 度量函数可能引起的字段相似度估计偏差，并且提高了重复记录检测的鲁棒性。 关键词：d e e pw e b 条件随机场 信息抽取数据集成 概率图学习模型 摘要 a b s t r a c t n o w a d a y s t r e m e n d o u ss t r u c t u r e dd a t ai sh i d d e n e di nt h ed e e pw e bw h i c hc a nj u s tb e o b t a i n e di nt h ed y n a m i cw e bp a g e sg e n e r a t e da c c o r d i n gt ot h eq u e r i e ss u b m i t t e dt ot h e w e bq u e r yi n t e r f a c e s d u et ot h ep o o rs t r u c t u r eo fw e bp a g e sa n dt h ei n s t a b i l i t ya n d l a r g es c a l eo fd e e pw e b ，i ti sac h a l l e n g et h a ti n t e g r a t et h ed a t aa u t o m a t i c a l l ya n d c o n s u m ei te f f e c t i v e l y p r o b a b i l i s t i cg r a p h i c a ll e a r n i n gi sah o tr e s e a r c ht o p i ci nt h e d o m a i no fm a c h i n el e a r n i n gw h i c hh a db e e n u s e dw i d e l ya n ds u c c e s s f u l l yi nd a t a m i n i n g ，i n f o r m a t i o ne x t r a c t i o n ，i n f o r m a t i o nr e t r i e v a l ，e t e s e v e r a le n h a n c e dm o d e l so f c o n d i t i o n a lr a n d o mf i e l d ( c r f ) ，at y p eo fp r a b a b i t i s t i cu n d i r e c t e dg r a p h i c a lm o d e l ，a n d p r a c t i c a la p p r o a c ha r cp r o p o s e dt os o l v es o m ec h a l l e n g i n gi s s u e si nd e e pw e bd a t a e x t r a c t i o na n di n t e g r a t i o n t h em a i nc o n t r i b u t i o n so f t l l i sd i s s e r t a t i o na l ea sf o i l o w s ： t h ef a c tt h a td e e pw e br e s o u r c e sa r ev e r ys p a r s e l yd i s t r i b u t e dm a k e st h ep r o b l e mo f l o c a t i n gt h e me s p e c i a l l yc h a l l e n g i n g i no r d e rt oc r a w lt h ed e e pw e bq u e r yi n t e r f a c e s q u i c k l yw i t h i nt h er e l e v e n tw e b s i t e s ，am o d e lo fc r f i st r a i n e do v e rt h es a m p l e so f i l s c r sn a v i a g t i o np a t ht h r o u g he x p l o i tav a r i e t yo ff e a t u r e sa 盯o u n dt h eh y p e r l i n k s t h e n al i n ks c o r i n ga l g o r i t h mb a s e do nr e i n f o r c e m e n tl e a r n i n ga n dt h et r a i n e dc r fm o d e li s u s e dt oa s s i g ne a c hh y p e r l i n ki nt h ec u r r e n t l yv i s i t e dp a g e sb yt h ec r a w l e rap r i o r i t y t h ea i mi st og u i d et h ec r a w l e rt h r o u g hao p t i m a lp a t h sl e a d i n gt ot a r g e tp a g e s e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ep r o p o s e dc r a w l e rc l e a r l yo u t p e r f o r m so t h e rf o r m c r a w l e r s t w om a x i m u me n t r o p yb a s e dc l a s s i f i e r sa r ep r o p o s e dt oa u t o m a t i c a l l ya n d a c c u r a t e l yi d e n t i f yt h eq u e r yf o r m so fo n l i n ed a t a b a s e sa n dt h e i rt o p i cc a t e g o r y r e s p e c t i v e l y t h ec l a s s i f e rf o rd i s t i n g u i s hq u e r yf o r m si so n l ye x p l o r et h et h es t r u c t u r e f e a t u r e so f w e bf o r m s w h i l et h eo t h e rc o r p o r a t ea l lt h ef e a t u r e so f c o n t e n ta n ds t r u c t u r e i nt h ec o n t e x to fw e bf o r m s e x p e r i m e n t si n d i c a t et h a tt h et o p i cc l a s s i f i e r sl e a dt oh i g h a c c u r a c y a st h ee l e m e n t so faw e bf o r ma r cn o tn e c e s s a r i l yl i n e a r l yl a i d - o u t , ah i e r a r c h i c a l s e q u e n t i a lc r f ( h s c r f ) m o d e li sp r o p o s e dt ob e t t e ri n c o r p o r a t ed e p e n d e n c i e sa c r o s s t h e h i e r a r c h i c a l l y l a i d - o u ti n f o r m a t i o n m e t h o d sf o rp e r f o r m i n gt h et a s k so f m o d e l - p a r a m e t e re s t i m a t i o na n d l a b e li n f e r e n e e eo fah s c r fm o d e lh a v e b e e n p r o p o s e d e x p e r i m e n t a l r e s u l t si n d i c a t et h a tt h ep r o p o s e dm o d e la c h i e v eg o o d p e r f o r m a c eo ns c h e m am a t c h i n gb e t w e e nh e t e r o g e n o u sw e bq u e r yi n t e r f a c e s ， 4 熏王篷件概率图模型的d e e pw e b 数据抽取j 集成研究 a i m p r o v e da p p r o a c hf o rf i n d i n gd a t ar e g i o n se m b e d d e di nah t m lw e bp a g ei s p r e s e n t e d a f t e rt h a t , ap o l i c yi sp r o p o s e dt oi d e n t i f yt h ed y n a m i c a lw e bd a t ar e g i o n s w h i c hc o m b i n e st h et e c h n i q u e so fw e bp a g ec l u s t e r i n ga n dc r o s s p a g ed a t ar e g i o n a n a l y s i s e x p e r i m e n t a lr e s u l t ss h o wt h eg i v e na p p r o a c h se f f e c t i v e n e s s m o r e o v e r , a n i m p r o v e ds e q u e n c el a b e l i n gm o d e ln a m e dm i x e ds k i p c h a i nc r fm o d e li su s e dt o i n t e g r a t ew e br e c o r d se x t r a c t e df r o mm u l t i p l es i t e s i n t or e l a t i o n a ld a t a b a s e t h e p r o p o s e dm o d e lc a nb et r a i n e do nt h em i x e ds a m p l e ss e ti n c l u d i n gl a b e l e ds a m p l e sa n d u n l a b e l e dd a t a b a s er e c o r d s ，t h e r e b yr e d u c et h ed e p e n d e n c eo nm a n u a l l yl a b e l e dt r a i n i n g d a t a m o r e o v e r , i tp r o v i d e san o v e lw a yt oi n c o r p o r a t et h el o n g - d i s t a n c ed e p e n d e n c i e s b e t w e e nd i f f e r e n ts t a t ev a r i a n t s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e dm o d e lc a n i m p r o v e t h ea c c u r a c yo f a t t r i b u t el a b e l i n gs i g n i f i c a n t l y af i n i t es t a t ec o n d i t i o n a lr a n d o mf i e l dm o d e if o re d i ts e q u e n c eb e t w e e ns t r i n g si s p r e s e n t e d u n l i k eg e n e r a t i v em o d e l s ，h o w e v e r , t h em o d e li st r a i n e do nb o t hp o s i t i v ea n d n e g a t i v ei n s t a n c e so f s t r i n gp a i r s f i n a l l y , as u p p o r tv e c t o rm a c h i n et r a i n e do ns e l e c t e d s a m p l e si su s e dt oc l a s s i f ye a c ho ft h er e c o r dp a i r si nd u p l i c a t eo rn o n - d u p l i c a t eo n e e x p e r i m e n t a lr e s u l t so nar a n g eo fd a t a s e t ss h o wt h a tt h ep r o p o s e da p p r o a c hc a n i m p r o v ed u p l i c a t ea c c u r a c yo v e rt r a d i t i o n a lt e c h n i q u e sa n dh a sag o o da b i l i t yo fn o i s y d a t ac o n s t t a i n t k e y w o r d a ：d e e pw e b i n f o r m a t i o ne x t r a c t i o n d a t ai n t e g r a t i o nc o n d i t i o n a lr a n d o mf i e l d s p r o b a b i l i s t i cg r a p h i c a ll e a r n i n gm o d e l s 创新性( 独创性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：董燮日期：一主哆! ! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本人签名： 导师签名： 兹缱斌 日期： 立竺2 ：! ：! ! 日期：丝翌! ! ! ! ! f 。 第一皋绪论 第一章绪论 1 1 研究背景和意义 在飞速发展的互联网( i n t e m e t ) 上，处于应用层的万维嗍( w o r l dw i d ew e b ， w w w ) 由于其可用性而获得了巨大的成功。目前，越来越多的个人、团体、企业 和组织在w e b 上建立自己的主页，对外发布自己感兴趣或与之业务相关的各种信 息。这些信息主要以半结构化的形式嵌入h t m l 网页中，不同网页和资源之间通 过超链接相互关联，从而构成了一个巨大的信息网络。经过多年的积累和更新， w e b 中已经存放了涵盖各个领域的海量的信息资源，成为当今人们发布和获取信 息的主要途径之一。据d f e t t e r l y 等人调查发现，2 0 0 3 年整个w e b 中的信息量已 经超过了2 0 0 ，0 0 0 t b ( t e r a b y t e s ，l t b = 1 0 0 0 千兆) ，而且仍在快速的增长。但是， 目前与w e b 数据处理相关的研究和应用还处于比较低的水平。由于w e b 网页的半 结构性、w e b 网贞链接的自南无序性、w e b 规模的急剧膨胀以及w e b 内容的海量 性、异构性、多样性和动态性等特点，使得自动从中获取有价值的信息成为当前 一项极具挑战性的课题。 搜索引擎的出现【2 】，如y a h o o 、g o o g l e 、百度等，一定程度上满足了用广迅速、 全面，准确查找信息的需求，它们通常使用蜘蛛( s p i d e r ) 或爬虫( c r a w l e r ) 程 序根据网页间的超链接关系对静态嘲页进行抓取、存储、分类和索引。但是，传 统搜索引擎采用简单的关键词匹配的方法，只要提交的关键词相同，查询的结果 总是一一样，并且查询返回的结果巾包含大量重复的或者与查询需求无关的网页， 需要用户进一步甄别和筛选。此外，研究表明即使是当前最好的搜索引擎索引的 信息量也仅占可访蜘信息总量的1 6 芹右，这还不包括那些无法被传统搜索引擎 索引的w e b 信息，如果加卜这些信息，那么一般搜索引擎仅能搜索到w e b1 - 大约 o 0 3 的信息。这种状况的出现除了与传统搜索引擎的信息搜索和索引算法尚不完 善有关以外，一个重要的原因在于互联网的信息发布方式在不停的变化与发展。 随着动态网页技术的发展，大量的网站利用存放在关系数据库中的数据来动态产 生与用户查询匹配的信息网页，而传统的搜索引擎很难发现和索引这螳“隐藏” 的信息1 3 , 4 1 。 因此，为了更好的处理w e b 上的信息资源，研究人员开始关注如何有效检索 那些隐藏在后台数据库i j 的数据。2 0 0 1 年，c s h e r m a n 和gp r i c e 5 j 将d e e pw e b 定义为：虽然通过互联网可以获取，但普通搜索引擎由于受技术限制而不能或不 作索引的那些文本嘲页、文件或其它高质量、权威的信息。这个定义以搜索引擎 基于条件概率图模型的d e e pw e b 数据抽取i 集成研究 的搜索能力为参照来阐述d e e pw e b 的概念，并没有给d e e pw e b 一个明确的界定， 很难得到一致的认同。其后，研究人员发现，多数的搜索引擎由于担心爬虫会陷 入巨量动态网页库而浪费网络带宽资源和存储资源，以及由于搜索技术的限制， 传统的搜索引擎一般只索引表层w e b 中由超链接町以到达的静态网页、文件等资 源，而无法索引或很少索引d e e pw e b - _ i 的资源。于是按照w e b 的分布状现及信 息存放的“深度”将其分为“表层w e b ”( s u r f a c ew e b ) 和“深层w e b ”( d e e pw e b ， 亦称h i d d e n w e b 或l n v i s i b l e w e b ) 并给出了各自明确的定义1 6 j 。所谓s u r f a c e w e b 指的是存储在w e b 空间，由超链接连接起来的静态网页、文件等资源，一般通过 超链接就可以访问到这些资源。所渭d e e pw e b 是指w e b 中可访问的在线数据库 ( a c c e s s i b l eo n l i n ed a t a b a s e s ) ，本文简称为w e b 数据库或w e b d b ，其内容存储在 真正的关系数据库中。d e e pw e b 中的信息只有在被查询时才会由w e b 服务器动态 生成含查询结果记录的网页并返回给用户，因此没有超链接直接指向这些网页， 这是它与那些可以被直接访问的静态网页的根本区别。 一二霖 教妈产晶也脯硬件游戏软件 _ ：- ：一：。 ? ? 麓震j j j 。 三，t # 7 呼一一二 、妇龋r i i ：j 重鼍，蔫薹曼塞曼? j 图i id e e p w e b 弼站 d e e pw e b 由四个基本要素组成：网站、数据库、查询接c i 和超链接。一个d e e p w e b 网站是一个w e b 服务器，它维护一个或多个后台数据库，用来保存可在线访 问的信息。每个后台数据库可以通过一个或多个h t m l 表单( f o r m ) 来进行查询， 这些查询表单构成了其查询接口( q u e r yi n t e r f a c e ) 。例如，图i - l 显示的 w w w i t s o g o n e t 是一个保存i t 产品信息的d e e pw e b 网站，它提供对些与i t 相 关的w e b 数据库中信息的访问，例如数码产品、电脑硬件、游戏软件等。 目前，获取d e e pw e b 信息的主要途径是通过对刚站中所提供的查询接口提交 查询来获得，图1 2 给出了高校图书馆网站提供的一个馆藏图书查询表单。每个查 询接口支持在若干个属性t ：进行查询，比如要奇询某一本图书，可以根据书名、 作者、出版社等属性进行搜索。这些字段、属性连同一些语义标签就构成了查询 接口的模式( s c h e m a ) 信息 第一章绪论 翁鞫i i 簌毒宇岿世需 蕾t 书且巷童 i 一，。固 语麟姐羹墨：o 所膏书刊。中立爵丰王。西文蕾书。中姗qo 西：x l 噼t l ! 融择柱薰赛矗：矗名 v 诩琏撵检索覆盂：囝舫一曩。完全日0o 任t 匹配箍薰毽度轻1 i 辱页墨示记囊稚：2 0 括果辨腻咀：x , j b qv ( ) 井庠刊聃捧列 结墨墨矛的方式：$ 洋细曼示。瞄置示 垃霉个培蠢地：强露匿圈瘠锵 图1 2 查询接u 示例 从w e b 数据库中获取数据的过程如陶1 3 所示，用户通过在以上查询表单与 后台数据库进行交互，通过提交用户查询请求，获得包含所有满足用户查询的后 台数据信息的网页。 ： ：藿由接口： 结不见一! 嗣萱鼍 幽1 3 从w e b 数据库中获取数据的过程 d e e pw e b 数据发现与传统w e b 信息搜索有很大区别。首先，传统w e b 信息 搜索的结果是网页，而d e e pw e b 中的搜索结果是结构化的数据记录，因此d e e p w e b 数据获取的粒度更小，不需要用户人工进行再检索且能更好地满足川户的需 求：其次，d e e pw e b 通常带有复杂的领域查询接1 ；3 ，而搜索引擎的查询接口是通 用的且较为简单，一般只接受一个或多个关键字输入，复杂的查询表单能够提高 用户查询的准确性；此外，搜索引擎对查询结果是按照预定的评价标准计算网页 与查询的相似度由大到小排序，而d e e pw e b 的查询结果可以按多种方式进行统计 分析和排列。 d e e pw e b 中的信息容量有多大，包含哪些内容，质量如何呢? 据b r i g h tp l a n e t 公司技术2 0 0 0 年发布的白皮书n e d e e p w e b ：s u r f a c i n g t h eh i d d e nv a l u e ) ) i ) j 显 示，d e e pw e b 中的资源容量比s u r f a c ew e b 大数百倍，而且包含着更多有价值的 4 摹于条件概率罔模型的d e e pw e b 数据抽取j 集成研究 资源，简而言之，其研究包含以下结论： ( i ) d e e p w e b 中的信息容量人 d e e pw e b 中包含的可访问公共信息容量是人家熟知的s u r f a c ew e b 的4 0 0 5 5 0 倍：d e e pw e b 中包含约7 5 0 0 t b 到9 i ，8 5 0 t b 的信息，而s u r f a c ew e b 包含的 信息容量只有1 9 t b ；相比s u r f a c ew e b 中包含的约i o 亿个独立文档而言，d e e pw e b 包含约5 5 0 0 亿个独立文档。 ( 2 ) d e e pw e b 发展迅猛 现有的d e e pw e b 站点估计超过2 0 0 ，0 0 0 个，站点平均的月访问量比s u r f a c e w e b 站点高出5 0 。并且与s u r f a c ew e b 站点相比含有更多的链接。然而那些典型 的大型d e e pw e b 站点在互联网搜索领域却不知名。而且d e e pw e b 是可= 联网新信 息增长的最大来源： ( 3 ) 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 包含的高质量内容的总量至少是s u r f a c ew e b 的1 0 0 0 到2 0 0 0 倍。而 且超过一半的d e e pw e b 内容都保存在属于特定领域的专业数据库中： ( 4 ) 可公开访问 9 5 的d e e pw e b 信息都足面向公共开放访问的，而无需付费或订阅。 2 0 0 4 年，美国伊利诺伊大学( u i u c ) 的研究入员b h e 和k e v i nc c c h a n g 等发表了其对整个d e e pw e b 更为深入的研究报告( a c c e s s i n gt h ed e e pw e b ：a s u r v e y 吼他们的研究表明，整个w e b 上约有3 0 7 ，0 0 0 个提供w e b 数据库的网 站，4 5 0 0 0 0 个w e b 数据库和1 , 2 5 8 ，0 0 0 个查询接口，比b r i g h tp l a n e t 公司在2 0 0 1 年估计网站的数目增长了6 倍多 表1 id e e pw e b 目录的覆盖率 网站w e b 数据库的数目覆盖率 c o m p l e t e p l a n e t c o r n 7 0 0 0 01 5 6 l i i o r g 1 4 0 0 03 1 t u r b o l 0 ，c o m2 3 0 0o 5 i n v i s i b l e w e b n e ti o o o0 2 d e e pw e b 中的w e b 数据库不但数量众多，而且几乎覆盖了现实世界的各个领 域。c o m p l e t e p l a n e t 、l n v i s i b l e w e b 等一些专门的机构，手工构建了d e e pw e b 目录， 按现实世界的领域对d e e pw e b 的内容做了分类，主要包括：商业与经济、计算机 与互联网、新闻媒体、娱乐等i 。几个类别。在这些宏观分类的下面还有更细致的 分类，比如科学可以继续分为社会科学与自然科学，而自然科学又可分为若干学 科。表1 1 列出了其中一些网站目录中收录的w e b 数据库的数量和覆盖率，从中 可以看出。尽管这些网站对w e b 数据库进行了分类，但所列出的w e b 数据库仅仅 第章绪论 只是整个w e b 数据库的很小的一个比例，即使最大的c o m p t e t e p l a n e t 也只有l5 6 。 因此，通过搜索软件自动从网上寻找d e e p w e b 数掭库的查询接口并对它们进行 自动分类是十分迫切而且必要的工作 由此可见d e e pw e b 包含数量巨大，高质量、结构化的数据，这些数据传统 搜索引擎技术无法对其进行有效检索，田而研究针对d e e p w e b 数据资源的自动芨 现抽取和集成技术对于提高互联网信息搜索的覆盖率和准确率有着非常重要的 意义。从应用角度来讲，随着d e e p w e b 信息搜索和集成技术的发展会产生很多新 的w e b 应用。对于提供网卜商务信息、销售，代理，拍丈的各类商务网站来说， 通用d e e p w e b 数据搜索平台可以获得更为实用的数据，从而提供更加实用的网上 服务例如：从多个电子商务网站获取产品信息从而提供比价购物服务等。对于 互联网信息服务门户网站来说可以利用d e e pw e b 数据搜索平台来收集、存贮、 分类和索引各类信息，为用户提供更加争抛和个性化的w e b 信息搜索服务。可见， d e e p w e b 数据挖捌研究会产生可观的经济j ；f 日社会效益，这项技求会引领w e b 应用 向更加深入的方向发展。 1 2d e e pw e b 数据抽取与集成的研究进展与现状 针对d e e pw e b 的研究始于美国斯坦福大学的sr a g h a v a n 和hg a r e i a - m o l i n a 在2 0 0 1 年的v l d b 会议上发表的一篇题为“c r a w l i n g t h eh i d d e nw e b ”的论文”j 。 返篇论文详细描述了d e e pw e b 的特点和研究意义，并给出了一个d e e pw e b 搜索 原型系统h i w e 的实现原理及涉及的关键问题。 目前，d e e pw e b 数据抽取与集成己引起世界很多国家的研究人员的关注，在 近几年召开的w w w 、v l d b 、i c d e 等顶缓国际会议上部有关于这方面的研究成 果发表。国际上关于d e e pw e b 有影响的研究计划主要有以下几个： ( 1 ) 美国伊利诺伊大学( u i u c ) 的k e v i nc c c h a n g 提出的m e t a q u e r i e r ( h t t p ：m e l a q u e r i e r c s u i u e e d u ) p 1 研究计划，致力丁。建设一个统一的有效访问 i n t e m e t 上结构化信息源的w e b 信息检索系统。该汁划分为两个子项口： m e t a e x p l o r e r 项目集中在发现在线w e b 数据库，建立一个可搜索的源仓库； m e l a i n t e g m t o r 项目集中在集成在线数据源，为用户提供访问分布式w e b 数据的统 一接口。该项目的实施对于整个d e e p w e b 的研究起到了巨大的推动作用。 ( 2 ) 纽约州立大学( s l r n yb i n g h a m t o n ) 的w e i y im e n g 教授与伊利诺伊大学 ( u i c ) 的c l t m e my u 教授合作提出的w e b 敬据库集成的研究项目 ( 逝世鲤盥g ：蛳b 出a 盟鲤d 墨丛g 生堕蝉盟m s 垦b 蜘i ) 。该研究计划的目标是开芨提供 集成访问w e b 数据库的技术，包含自动发现和分类w e b 数据库、集成w e b 数据 库的查询接口，用户查询转换、查询结果的抽取和处理等。并开发了两个软件工 6 基于条件概率罔模型的d e e pw e b 数掘抽取j 集成研究 具w i s e - i n t e g r a t o r 、w i s e - i e x t r a c t o r 分别用于查询接口的聚类和查询接口的抽取。 ( 3 ) 佐治亚理工学院( g i t ) 的l i n gl i u 教授提出的t h o r 研究计划 ( h t t p ：w w w c s b i n g h a m t o n e d u - m e n g d m s e h t m l ) 。t h o r 是一个d e e pw e b 数据 抽取引擎，集中在抽取动态产生的w e b 网页q a p a g e l e t s 中的查询结果网页中的 数据记录。 ( 4 ) 美国犹他大学j u l i a n af r e i r e ( h t t p ：f l e i x e i r a s 二c s u t a h , e d u w e b d b ) 领导的 研究小组也正在针对查找、检索、查询和集成d e e p w e b 数据进行研究，目标是找 到能够快速查找和展示d e e pw e b 内容的技术。 在国内，香港大学的j i y i n gw a n g 首先对w e b 数据抽取和d e e pw e b 查询接口 模式匹配进行了探索性的研究。中国人民大学信息学院孟小峰教授领导的“网络 与移动数据管理实验室”对d e e pw e b 数据集成系统的实现进行了深入的研究1 1 0 。 他们以招聘信息集成查询为范例，开发了一个“工作通”( j o b t o n g ) 原型系统【“】， 旨在通过对招聘信息的集成进行研究，总结出一套w e b 数据集成的解决方案，包 括产品、服务和研究等方面。目前，j o b t o n g 的原型系统( w w w j o b t o n g c n ) 已经在 网上公布，它集成了包括5 l j o b 、中华英才网、智联招聘等国内大型工作信息网站 的招聘信息。利用这个搜索引擎，用户可以查找多种职位信息。不过该项日在很 多方面还不成熟，集成的信息量还很小、没有针对用户的个性化指导，用户界面 过于简单，因此距离真正的实用阶段还有较大差距。此外，北京大学、上海交通 大学、苏州大学等科研机构也有学者正在从事这个领域的研究【1 2 ，1 3 】。 查询接n 集成 图1 4o e e pw e b 数据集成系统的一般框架 图i a 驻示了当前d e e p w e b 数据集成系统的般框架。查询接口集成通常分 为数据源的发现、查询接口的抽取、查询接口的匹配与集成、查询提交、查询转 换，结果抽取、结果合并等几个步骤。当前，针对d e e pw e b 数据抽取与集成的研 第一章绪论 究主要集中在以下几个方面： 1 可访问在线w e b 数据库的自动发现 此项研究的目标是自动搜索可访问的在线w e b 数据库及其查询接口。由于查 询接口是w e b 数据库的入口点，为了适应大规模d e e pw e b 数据集成的需要，首 先必须能够自动收集主题相关的d e e pw e b 资源领域查询接口。目前，这个问题尚 没有得到深入的研究。实现这个功能主要分为以下_ 二个步骤：一、找到w e b 数据 库所在的网站：二、从获得的网站中发现能够对w e b 数据库查询的查询接口。比 较全面而准确的把它们从w e b 中搜索出来是一件非常困难而又耗时的事情，其原 因有三：首先由于目前w e b 中存在数量巨大的可访闷w e b 数据库，这些自主的、 相互独立的w e b 数据库分布在万维嘲的各个角落，虽然对w e b 数据库做了一些搜 集与整理，但其中只覆盖了全部w e b 数据库的很少部分；其次w e b 是动态的、 不断变化的，w e b 数据库也是如此，不断有新的产牛和旧的消失，即使现存的w e b 数据库内容和规模也处于不断变化之中：第三。查询接口在网页上都是以h t m l 语言的f o r m 元素所形成的表单的形式展现，但并不是说由f o r m 元素所形成的表 单都是查询接口，比如网站中用户的注册、b b s 讨论组、写发邮件，还有搜索引 擎和元搜索引擎也都是表单的表现形式，要能够从中准确地识别出真正的w e b 数 据库的查询接口相当困难。 因此，查询接口的自动发现有两个关键问题需要解决：首先，通常一个网站 包含上千甚至更多的网页，通过遍历所有网页的方法来找出其中的查询表单显然 代价太大：其次，需要从所有f o r m 表单中准确的识别出哪些是查询接口。k c 一c c h a n g 等 6 1 4 1 中通过大量的现察提出了一个用来解决前一个问题的方法，即从网站 的主页开始以宽度优先遍历所形成的树，查询接口在这棵树中的深度不会超过5 ， 而且9 4 的查询接口不会超过3 ，这样搜索空间就会大大降低。最近，l b a r b o s a 等 1 5 , 1 6 】提出了一种利用聚焦爬行技术来定位d e e p w e b 入口点的策略，取得了较高 的收获率。针对后一个问题，人们尝试使用分类器技术来实现查淘表单的自动过 滤。j c o p e 等利用查询接口中特有的文字特征，用c 4 5 决策树实现了对查询接 口的识别。 2 查询接口模式的抽取和理解 查询接口的模式是一组领域相关的字段和属性的集合，通过对其中若干字段 的赋值形成一个对该查询接口对应的后台w e b 数据库的查询。因此，查询接口的 模式可以被看作是建立在对应w e b 数据库上的一个视图。查询接口模式的抽取是 指对查询接口属性的获取与分析，这样可以获得一个查询接口的查询领域和功能， 其主要目的是为了下一步的w e b 数据库分类和查询接口集成打基础。因此，查询 基于条件概率图模型的d e e pw e b 数据抽耿j 集成研究 接口抽取的同时还要理解查询接口所包含的各个字段和属性的准确语义内涵。 z z h a n g 等m i 提出了以文法分析的方式来完成对查询接口模式的抽取。该方 法首先通过观察与统计提出了这样一个假设：所有查询接口都足由隐藏的文法构 建面成。为了能够准确地从一个具体的查询接口中将表示属性的各个元素组合方 式识别出来，通过构建解析树对整个查询接口进行解释，并确定各元素的语义角 色。虽然宣称精度达到8 0 、召回率达到8 9 ，但是显然未能达到实际应用的程 度。h h e 等设计了一个w e b 查询接口自动抽取工具w i s e i e x t r a c t o r l l 9 2 0 ，可以 自动抽取查询接口中的属性和语义标签。 查询表单抽取完成后，需要把查啕接口形式化地表现出来以便于为下一步的 工作提出模型化的解决方案。h h e 等1 2 1 , 2 2 1 给出了一种形式化的表达方式，描述了 一个查询接口中的属性的布局位置、域类型、缺省值、值的类型等很多细节信息， 为下一步w e b 数据库的分类和查询接口的集成提供各种特征和信息。 3 w e b 数据库的分类 为了有效的利用w e b 数据库中的信息，需要将其按领域进行分类。手工完成 对所有w e b 数据库的分类是个庞大而费时的工程，因此需要以尽可能自动的方式 来完成对w e b 数据库的分类。在查询接口上提交查询是获取w e b 数据库信息的主 要途径，对w e b 数据库的分类多数采用对查询接口进行分类的方法。q p e n g 等1 2 习 针对电子巍务( e - 0 3 t r t m e r e c ) 领域的w e b 数据库提出了一种有效的分类方法。这 种方法是一种非监督层次聚类方式，主要利用了电子商务w e b 数据库查询接口所 在的网页中可用的特征信息，包括接口中出现的频繁词和商品的价格特征。其实 验结果表明按这种分类方式进行分类，精度和召回牢都在9 0 左