（计算机应用技术专业论文）deep+web数据源下重复记录识别模型的研究.pdf

，) i 、 ； at h e s i sf o rt h ed e g r e eo fm a s t e ri n c o m p u t e ra p p l i c a t i o nt e c h n o l o g y r e s e a r c ho nd u p l i c a t er e c o r d si d e n t i f i c a t i o n m o d e li nd e e pw e b b yl i ul i n a n s u p e r v i s o r ：p r o f e s s o rs h e nd e r o n g n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 z ， j一 川 。o一 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写 过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表 示谢意。 学位论文作者签名：玉l 而争甬 日期：如彦7 。 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。、 、 如 、 作者和导师同意网上交流的时间为作者获得学位后： 、 半年i一年口一年半口两年口 学位论文作者签名：l 而梅 导师签名： 崎协蕾 签字日期：j 棚孑- 7 签字日期：函蝴p 、毋i 鲺i，- ，、丫、l 东北大学硕士学位论文摘要 d e e pw e b 数据源下重复记录识别模型的研究 摘要 w o r l dw i d ew e b ( 简称w w w ，或w e b 网) 自2 0 世纪9 0 年代发明以来就一直呈现 蓬勃发展之势，到今天为止其蕴含着海量的丰富资源，包罗万象，是人类一笔宝贵的 知识财产。w e b 网按其分布状况可以分为“表层网( s u r f a c ew e b ) 和“深层网( d e e p w e b ) 。d e e pw 曲指那些存储在网络数据库里、不能通过超链接访问而需要通过动 态网页技术访问的资源集合。根据调查，d e e pw e b 中包含的信息量超过s u r f a c ew e b 上千倍，而且这个比例仍在持续地上升。 为了能够有效利用d e e p w 曲中丰富的信息，建立d e e p w 曲数据集成系统成为了 当前最迫切的需求。由于w e b 数据库的异质性和自主性，对从各个w 曲数据库中抽 取结果的合并是一项十分具有挑战性的工作。为了对抽取结果进行清洗和去重，重复 记录识别则是数据合并过程中的一个必不可少的环节。 本文概要介绍了重复记录识别( 即数据清洗和去重) 问题及其应用，详细地阐述 了实现重复记录识别的不同方法以及它们所应用的结构。针对已有的大多数的数据清 洗方法主要是基于结构化的关系数据的局限性，本文提出一种处理从d e e pw e b 数据 源中抽取出的半结构化数据的重复记录识别模型。本模型主要由数据预处理模块、同 构记录处理模块和异构记录处理模块组成。 “d e e pw e b 数据源下重复记录识别模型 利用数据集成过程中的基于特定领域的 全局模式来分析不同数据源的实体记录值间的匹配关系，进而大大提高了计算实体记 录间的相似度的准确性。在计算来自不同数据源的实体记录间的相似度时，本模型提 供了一个可扩展的相似度算法库，并且在计算的过程中支持不同相似度算法相结合。 在该模型中，新的相似度方法可以根据需要添加到相似度算法库中，并且针对不同领 域可以制定不同的相似度计算策略和选择不同的相似度计算方法。 实验表明，这种重复记录识别模型在d e e pw e b 环境下是可行且有效的。 关键词：重复记录；深层w e b ；数据清洗；半结构化数据；全局模式 一 l r 东北大学硕士学位论文a b s t r a c t r e s e a r c ho nd u p l i c a t er e c o r d si d e n t i f i c a t i o n m o d e li nd e e pw e b a b s t r a c t w o r l dw i d ew e b ( r e f e r r e dt ow 州o rw e bn e t w o r k ) i sg r o w i n ga tap r o d i g i o u sr a t e s i n c e19 9 0 s u pt on o w , i tc o n t a i n sam a s so fr i c hr e s o u r c e s ，w h i c hi sav a l u a b l ei n t e l l e c t u a l p r o p e r t y a c c o r d i n gt ot h ed e p t ho ft h ei n f o r m a t i o n ，t h ew e bc a nb ed i v i d e di n t ot w o c a t e g o r i e s ：s u r f a c ew e ba n dd e e pw e b d e e pw e br e f e r st ot h ed a t as o u r c e st h a ta r es t o r e d i nd a t a b a s e sa n dc a nn o tb ea c c e s s e db yh y p e r - l i n k sb u to n l yb yd y n a m i cw e bp a g e a c c e s s i n g s o m es t a t i s t i c sh a v es h o w nt h a ti n f o r m a t i o no nd e e pw e ba n di t sa c c e s s i n g a m o u n ta sw e l la st h ei n c r e a s i n gs p e e di sf a rh i g h e rt h a ns u r f a c ew e b i no r d e rt ou s et h ei n f o r m a t i o no fd e e pw e ba se f f e c t i v e l ya sp o s s i b l e ，i ti sa nu r g e n t n e e dt ob u i l dad a t ai n t e g r a t i o ns y s t e mo fd e e pw e b b e c a u s eo ft h eh e t e r o g e n e i t ya n dt h e a u t o n o m yo ft h ew e bd a t a b a s e ，i ti sac h a l l e n g et om e r g et h eq u e r yr e s u l t se x t r a c t e df r o m v a r i o u sw e bd a t a b a s e s a n dd u p l i c a t er e c o r d si d e n t i f i c a t i o ni sa ne s s e n t i a lp a r to fd a t a i n t e g r a t i o nd u r i n gt h ec l e a n i n go ft h ee x t r a c t e dr e s u l t s i nt h i st h e s i s ，ab r i e fd e f i n i t i o no fd u p l i c a t ei d e n t i f i c a t i o np r o b l e m ( i e d a t ac l e a n i n g a n dd e d u p l i c a t e ) i sg i v e nf i r s t l y , t h e nad e t a i l e dd e s c r i p t i o no ft h ee x i s t e dm e t h o d sa n d m o d e l sa r ep r e s e n t e d f o rt h em o s to fc u r r e n td u p l i c a t e si d e n t i f i c a t i o ni sb a s e do nt h e s t r u c t u r e dr e l a t i o n a lm o d e l ，t h ed u p l i c a t er e c o r d si d e n t i f i c a t i o nm o d e li sp r e s e n t e di n t h i s t h e s i sb a s e do nt h es e m i - s t r u c t u r e dd a t a t h ed u p l i c a t er e c o r d si d e n t i f i c a t i o nm o d e lm a i n l y c o m p r i s e so ft h ed a t ap r e p r o c e s s i n gm o d u l e ，h o m o g e n e o u sr e c o r d sp r o c e s s i n gm o d u l ea n d h e t e r o g e n e o u sr e c o r d sp r o c e s s i n gm o d u l e t h em o d e la n a l y z e st h em a t c h i n go ft h ee n t i t yr e c o r d se x t r a c t e df r o md i f f e r e n td a t a r e s o u r c e sb a s e do nt h eg l o b a ls c h e m ao fs p e c i f i cd o m a i n ，a n di t g r e a t l yi m p r o v e st h e a c c u r a c yo fs i m i l a r i t yb e t w e e nt w oe n t i t yr e c o r d s i nt h ec a l c u l a t i o no ft h es i m i l a r i t yo ft h e e n t i t yr e c o r d se x t r a c t e df r o md i f f e r e n td a t a b a s e s ，t h em o d e lp r o v i d e sas c a l a b l es i m i l a r i t y a l g o r i t h ml i b r a r y , a n di tc o u l dc o m b i n ed i f f e r e n ta l g o r i t h m sd u r i n gt h ec a l c u l a t i o n i nt h e m o d e l ，t h en e ws i m i l a r i t ya l g o r i t h mc o u l db ea d d e dt ot h es i m i l a r i t ya l g o r i t h ml i b r a r y , a n d t h es t r a t e g i e sa n dt h ea l g o r i t h m so fs i m i l a r i t yc a l c u l a t i n gc o u l db ec h a n g e db a s e do nt h e - i i i - - 东北大学硕士学位论文 a b s t r a c t s p e c i f i cd o m a i n t h ee x p e r i m e n tr e s u l t ss h o wt h ed u p l i c a t er e c o r d si d e n t i f i c a t i o nm o d e li sf e a s i b l ea n d e f f i c i e n t k e yw o r d s ：d u p l i c a t er e c o r d s ；d e e pw e b ；d a t ac l e a n i n g ；s e m i - s t r u c t u r e dd a t a ；g l o b a l s c h b e i i l a 一一 一 l ， i l 。j ， 东北大学硕士学位论文目录 目录 独创性性声明i 气 摘要。i i a b s t r a c t 。i i i 第1 章绪论1 1 1 弓i 言1 1 2d e e pw c b 国内外研究现状。4 1 3 本文解决的主要问题7 1 4 本文组织结构8 第2 章相关概念及关键技术9 2 1 重复记录识别9 2 2 重复记录识别的研究现状l o 2 2 1 基于关系数据的重复记录识别1 0 2 2 2 基于x m l 数据的重复记录识别一1 2 2 2 3e t l 1 3 2 3 全局模式1 4 2 4 技术简介1 4 2 4 1h t m l 15 2 4 2x m l 1 6 2 4 3i ) o m 18 2 5 本章小结1 9 第3 章重复记录识别模型体系结构2 l 3 1 重复记录模型的提出2 1 3 2 重复记录识别模式体系结构2 2 3 3 本章小结2 4 第4 章基于全局模式的同构记录处理2 5 4 1 数据预处理过程2 5 一v v o 。-。 东北大学硕士学位论文目录 4 1 1d o m 树的创建2 5 4 1 2 实体记录的创建2 7 4 2 同构记录的处理2 9 4 2 1 实体记录属性值匹配关系的确定3 0 4 2 2 全局模式属性权重的确定3 3 4 3 本章小结3 4 第5 章基于多相似度估算器的异构记录处理3 5 5 1 异构记录的处理过程3 5 5 2 多种相似度估算器3 5 5 2 1 应用多种相似度估算器的优势3 5 5 2 2 已实现的多种相似度估算器3 6 5 2 3 实体记录间相似度的确定4 2 5 2 4 不确定相似记录的处理4 3 5 3 重复记录集的确定4 3 5 4 生成重复记录集的算法复杂度4 5 5 5 本章小结4 6 第6 章实验结果及分析4 7 6 1 重复记录识别模型的实现4 7 6 2 实验及结果分析4 9 6 3 本章小结5 2 第7 章总结与展望5 3 参考文献5 5 致谢5 9 攻读硕士期间发表的论文6 0 一v i 一 二一 一j 。 ， y 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 引言 随着w o r l dw i d ew e b 的飞速发展，其中蕴含了海量的信息可供我们利用。w e b 中 的信息主要通过网页的形式对外发布，而由文本和超链接构成的网页有其独特之处：数 量惊人，信息丰富；由不同的个人或群体开发，形式与内容有很大的差异；分布在地球 上i n t e m e t 连接的每一个角落。这就造成了w e b 数据的异质性和缺乏结构性。 整个w e b 看似杂乱无章，但如果按其所蕴涵信息的“深度 可划分为s u r f a c ew e b 和d e e p w e b 两大部分。s u r f a c e w e b 是指可以通过超链接被传统的搜索引擎索引到的页 面的集合；而d e e pw e b 最初由d r l j i l le l l s w o r t h 于1 9 9 4 年提出，指那些由普通搜索引 擎难以发现其信息内容的w e b 页面。2 0 0 1 年，c h r i s ts h e r m a n 、g a r yp r i c e 对d e e pw 曲 定义为：虽然通过互联网可以获取，但普通搜索引擎由于受技术限制而不能或不作索引 的那些文本页、文件或其它通常是高质量、权威的信息。 ( 1 ) d e e p w e b 的概念 1 9 9 4 年，美国学者d r j i l le l l s w o r t h 首次提出“i n v i s i b l ew e b ”这一概念，用来指那 些通过普通搜索引擎搜索不到的网络信息，但直到2 0 0 0 年以后，才有相关的研究论文 和成果发表，并迅速得到重视。2 0 0 0 年，b r i g h t p l a n e t 公司首创了“d e e p w 曲 【1 】术语， 用来表述那些存储于在线数据库中，且只能通过提交表单才能访问的数据。可见，“d e e p w e b ”和“i n v i s i b l ew e b ”指的是统一事物，但“d e e pw e b ”在内涵上略胜一筹。首先， “d e e pw e b 是相对于“s u r f a c ew e b 的，这样整个i n t e m e t 的构成就清晰了。 其次，“d e e pw e b ”是表明用户或搜索引擎获取这部分信息有一定的难度，普通用 户往往需要填写详细的表单( 如“a d v a n c es e a r c h ) 才能在海量信息中找到自己的所需， 对于d e e pw e b 搜索引擎来说要克服普通搜索引擎的不足，也就是要具备一定的智能， 如能够发现d e e pw 曲，能够进行表单仿真【2 】，也就是分析表单，表单求值，填写表单， 提交表单的整个过程，能够从响应页面自动提取查询结果，对获取的数据进行集成等。 不管是“i n v i s i b l ew e b ”、“d e e pw 曲 还是“h i d d e nw e b ”，主要都是相对于搜索引擎来 说的，所指的事物是一致的。虽然目前很难用专业术语准确定义，但人们都能从“是什 么 、“为什么存在 、“特点和重要性 以及“检索途径和方法 等方面来感性的认识它， 目前关键是要加强对d e e pw 曲的研究，充分挖掘和利用网络资源。 ( 2 ) d e e pw e b 的产生原因 d e e pw e b 产生的原因包括技术因素，如搜索引擎无法索引动态页面、无法访问网 一1 一 。1 东北大学硕士学位论文第1 章绪论 络数据库( w e b d a t a b a s e ，w d b ) 站点( 是d e e pw e b 信息资源的主要组成部分) 和注 册站点，又有非技术因素，如知识产权保护的负面影响、搜索引擎的负面限制等。这些 因素造成了深网资源的多样性。 i n t e r n e t 上的信息早已处于“信息泛滥”、“信息爆炸的状态，据致力于d e e pw e b 研究的b r i g h tp l a n e t 公司的报告显示，相对于s u r f a c ew e b ，d e e pw e b 资源有着多不可 比拟的优点： 数量大、发展快：d e e pw e b 资源在2 0 0 0 年大约有7 5 t b ，是当时s u r f a c ew e b 资源总和的4 0 0 - - 5 5 0 倍。用常规搜索 - 3 i 擎只能找到大约1 6 的s u r f a c ew e b 信息资源， 其余8 4 属于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 中大约存在3 5 0 0 0 0 多个可搜索数据库，其中大约1 5 0 0 0 0 个数据库内容是独一无二的。这些数据库所存储的信息都是与特定专业领域高度相关 的。 成本低廉：9 5 的d e e pw e b 资源都是免费的，无需交费或订阅。 便于处理：d e e pw e b 中的信息格式常常是容易用应用软件处理的，例如统计信 息和财政信息可用电子制表软件( 如e x c e l ) 或者统计分析软件( 如s p s s ) 来处理。 ( 3 ) d e e pw 曲的类型 。 按数据库结构化程度分类 按照d e e pw e b 数据库中信息的结构化程度，可以分为结构化数据库和非结构化数 据库，结构化数据库中存储的信息是多个字段组成的记录、非结构化数据库中存储的是 文档信息和非文本文件。关系数据库表格中存储的信息属于结构化信息，科研文献网站 存储的信息属于文档信息( 如：w w w n c b i n l m g o v ) ，非文本文件主要包括多媒体文件、 图像文件、软件和特定格式的信息( 如h t t p ：n i x n a s a g o v ) 。结构化程度的不同对相关查 询技术和数据集成技术的要求差别很大。 按数据库的访问权限分类 d e e pw e b 上的在线数据库按访问权限可以分为直接访问的、需要注册的、对搜索 引擎限制访问页面的、禁止浏览器生成缓冲拷贝的网站直接访问的站点一般是数据可以 公开提供的站点( 如上文提到的2 个d e e pw e b ) ；需要注册的站点在注册之后，用户可 以通过输入用户名和密码登陆，才能访问数据库( 如：w w w w a n f a n g d a t a c o m o n ) 对爬 虫限制访问的站点，主要是通过文件r o b o t s t x t 进行限定，不管是普通搜索引擎爬虫还 是d e e pw e b 爬虫在访问该站点时，首先应该载入r o b o t s t x t 文件，读取机器人禁止访问 一2 一 ( ， 一 - y _ p 一 寸 、 _ _ 东北大学硕士学位论文第1 章绪论 的区域，否则会涉及法律问题；禁止浏览器生成缓冲拷贝的网站，响应页面是在客户端 浏览器上通过执行j a v a s c r i p t ，v b s c r i p t 等脚本程序生成的，用户虽然可以看到查询结 果，但在存储在本地机器上的响应页面( h t m l 文件) 中，看不出查询结果的相关信息 ( 如：h t t p ：a c m 1 i b t s i n g h u a e d u c n ) 。 按网页动态类型分类 时效型动态网页包含时间敏感的动态内容，如，关于股票资料的数据库，关于各地 气象云图的数据库，关于时政新闻的数据库等。对根据时间动态变化的网页，在不同时 间点上发出的请求将得到不同的内容。目前的普通搜索引擎爬虫能爬行时效型动态网 页，爬行这样的网页的关键问题是刷新，也就是说，需要和网站上最新内容进行比较， 从而确定一个如何更新已爬行数据集的尺度。这方面的分析和爬行策略在文献 3 】中有详 细介绍。 个性化动态网页包含的内容根据特定客户端( 或用户) 定制产生的，就是个性化的 问题。w e b 服务器定制客户端的网页( 视觉外观和内容) ，来满足特定的用户或团体用 户的需求。这要求w e b 服务器能在工作中，利用客户端的c o o k i e 或外在的注册登陆信 息( 用户名和口令) 来确定特定用户，在此基础上产生网页。由于基于客户端动态网页 的内容是定制的，爬行这样的网页对于普通搜索引擎的爬虫来说是没什么用的，因为普 通搜索引擎面对的是各种类型的用户，然而，对某种受限爬虫( 在一个固定站点上进行 爬行) 来说，需要附带必要的c o o k i e s 信息或登陆信息。 输入型动态网页的内容依赖用户的输入称之为输入型动态网页。这种网页的典型例 子是w e b 服务器为响应用户提交的表单，而产生的响应页面。如，通过表单对在线数 据库的查询会产生一个或多个包含查询结果的响应页面。所有这些响应页面都属于输入 型动态网页。一般来说，d e e pw e b 中所有响应页面都是输入动态型的。 在实际情况下，许多动态网页是上述这些动态类型的组合，例如，a m a z o n 站点的 欢迎页面既有基于客户端的个性化动态( 基于用户兴趣和外形产生的推荐列表) 内容， 也有时效型动态( 如，最新畅销书列表) 内容。 按网页生成机制分类 服务器端程序程序在服务器上执行，产生整个h t m l 网页并把它传送给客户。这 是产生动态网页最古老和最普通的机制。有一种可采用的规范来控制w e b 服务器和产 生这个网页的程序之间的交互( 如，c g i ) 。这种服务器端的程序通常用来处理用户提交 的表单，并产生响应页面，也就是产生输入型动态网页。 服务器端嵌入式代码在服务器上的动态网页，既包括静态h t m l 文本，也包含嵌 入的代码片段。当收到该网页的请求时，代码片段在服务器上执行并产生输出来代替网 页上的实际代码。不像服务器端程序，产生整个h t m l 网页作为输出，这些代码片段 一3 一 东北大学硕士学位论文第1 章绪论 只是产生网页的一部分，可用不同的脚本语言来产生这些代码片段。 客户端嵌入式代码正如上一种情况，网页内容包括静态的h t m l 文本和嵌入式代 码( 它们是指无论在哪里都可以获取的代码) 。然而不同的是，现在是客户端将它们下 载到本地再执行，一般来说，它们的执行控制环境是由浏览器提供的。j a v as e r v l e t s 和 a c t i v e x 控件技术就是支持这种动态生成机制的例子。 那些通过服务端程序或嵌入代码在服务器端执行，生成的动态网页，对爬虫不会引 起任何特殊的挑战，因为它们都是以完整网页的形式被爬虫抓取的，爬虫可以按照处理 静态网页同样方式，简单地接收h t m l 网页并处理就行了。然而，需要客户端的执行 才能将内容从服务器抽出来的情况，需要特定的运行环境( 如，j a v a 的虚拟机) 来执行 嵌入式代码，让爬虫装备必要的环境将大大增加设计和实现的复杂性。 d e e pw 曲研究中处理的动态网页，主要是以前两种生成机制产生，以第三种生成 机制产生的动态网页也有，但对d e e pw e b 爬虫技术的要求会大大提高。 虽然整个d e e pw c b 中几乎包含了我们所需要的任何信息，但实际上，能真正被应 用的w e b 信息却很少，尤其是d e e pw e b 数据信息。因为w c b 上信息以多种形式存在， 并且要想以手工的方式对其加以有效的利用在实际当中是一件非常困难的事情。目前对 w e b 信息的利用主要是基于如g o o g l e 、百度这样的搜索引擎进行查询，返回含有关键 字的u r i 导航信息的页面提供给用户。用户可以通过逐一点击的方式获取需要的信息， 然而，这样所得到的信息都是部分信息，并且收集到可能存在很多重复信息和无效的信 息，并且需要用户参与，进行信息筛选，导致获取的信息不完备，且效率低。为此，人 们希望通过一个统一的获取信息的门户，能按需为用户提供整合的信息。这样，可大大 节省大量的人力，提高查询的效率和知识的利用率。可见，对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 的研究，典型的有：d e e pw e b 数据源 发现与分类，查询页面接口抽取与查询接口间映射，响应页面抽取实例信息等等，并取 得了一定的进展。但目前人们对d e e pw e b 的研究主要还只是处于探索性阶段，还不存 在一个比较成熟完善d e e pw e b 数据库集成和检索系统，付诸于应用还有一段距离。为 支持d e e pw e b 信息整合，还存在许多挑战性工作。 1 2 d e e pw 曲国内外研究现状 目前国内外对d e e pw 曲技术的研究主要集中在对后台数据库的访问，即对态网页 一4 一 。一t - 、 信 东北大学硕士学位论文第1 章绪论 的访问，这主要靠爬行表单并自动提交表单来实现。就国外而言，最著名有h i d d e nw e b e x p o s e r ( h i w e ) 1 4 】，这是斯坦福大学研的一个项目，设计了一种可以抽取d e e pw 曲 内容的c r a w l e r 。在此系统中c r a w l e r 管理器负责管理搜集过程。它对下载的w e b 页面进 行分析，包含表单的页面被送到表单处理器中专门处理。表单处理器先从页面中抽取出 表单，再从预先准备好的数据集中选择数据自动地完成表单的填写，然后将合成的u r l 提交c r a w l e r 处理器去下载相应的结果页面。由于需要系统自动完成表单填写，所以要 求用户事先准备相应的表单数据集。h i w e 只能面向特定的领域使用，而且必须在人工 帮下完成。 另外，哥伦比亚大学的p a n a g i o t i sg i p e i r o t i s 等人在文章中【5 】讨论自动地将w 曲网 页所连接的后台数据库进行分类的方法。它首先使用机器学习技术生成一套基于规则的 分类器( c l a s s i f i e r ) 。然后将分类器转变成查询u r l ，对台数据库进行查询，计算查询 结果。他们的算法最后根据查询结果对数据库进行分类，但只针对文本数据库的分类上 面。 就国内而言，目前国内对d e e pw e b 方面的研究尚处于学习、跟踪和探索阶段【6 】。 上海交通大学宋晖等人【7 】提出基于标记树的对象抽取( t a g t r e e b a s e do b j e c te x t r a c t i o n ) 方法自动地从w e b 页面中抽取h i d d e nw e b 信息，然后在此基础上给出了结构化的 h i d d e nw 曲信息查询算法。 另外苏州大学的郑冬冬，赵朋朋等人也对d e e pw 曲的访问进行了相关的研究，在 “爬虫研究与设计”【8 l 文中提出使用启发式规则集和领域本体知识库来自动发现相关 表单、填写表单，同时识别和收集相关结果页面。 对d e e pw 曲的信息抽取，有着很大的商业前景，有许多商业网站提供了获取d e e p w e b 部分信息的方法。如i n v i s i b l e w e b c g ) m 建立了一个包括约1 0 0 0 0 个数据库的目录， 这些数据库通过标准搜索引擎是无法获取的。b r i g h t p l a n e t c o m 则索引了大约4 0 0 0 0 个包 含d e e pw 曲信息的数据库。这些商业服务都声称他们采用了半自动的技术来索引d e e p w e b ，但是由于商业秘密，这些技术都没有在公开的资料中进行探讨。 目前国内还没有专门的文章对这方而的内容进行讨论，国外有一些大学在研究中进 行了很多有益的探索。本章介绍的s h o p b o t 、w i e n 、s o f l m e a l y 和s t a l k e r 系统是就 目前而言技术比较成熟的d e e pw e b 网页信息抽取系统，这类系统专门用来从网站数据 库所生成的网页中抽取信息，主要采用分隔符作为抽取规则，无需用到句法和语义知识， 局限于处理比较结构化的数据。 s h o p b o t l 9 1 是一个比价代理系统，专门从网上卖家的网站上抽取信息，用于比价购物， 所抽取的产品信息按价格排序，因此，局限性比较大。其算法主要针对以表单形式提供 查询的页面，而且返回的搜索结果是以表格形式显示的产品信息页面，以启发式搜索、 一5 一 东北大学硕士学位论文第1 章绪论 模式匹配和归纳式学习的方法从结果页面中抽取相关信息。 w i e n 9 】( w r a p p e ri n d u c t i o ne n v i r o n m e n t ) “分装器归纳生成环境”是辅助分装器生 成的工具，为网页的自动分析而设计，受到s h o p b o t 的影响。不过，它是第一个提出分 装器归纳生成这一术语的。其方法不只局限于某一领域，适用于所有包含表格信息的结 构化文本，也不只是用于h t m l 文本。 s o f l m e a l y 9 】力图改进w i n e 的分装器归纳算法。s o f t m e a l y 是一个通过“学 - - j 分装 器 学习从半结构化网页中抽取信息的系统。其分装器被称为“非确定有限自动机 ( n o n d e t e r m i n i s t i cf i n i t ea u t o m a t a ) 。这种表达模式和学习算法据说可以处理缺失值、一 栏多值和变量( p e r m u t a t i o n s ) 的情况。 s t a l k e r 9 】被用来抽取不同网站上的餐厅信息，如餐厅名称、菜肴种类、价格、烹 调方法、地址、电话和评价。s t a l k e r 采用指导学习的算法归纳抽取规则。训练例子 由用户提供，用户需选择若干样例页面并把有用的数据( 即所谓“e c 树”的叶子) 标 记出来。页面被标记好后，系统可生成一个符号序列( t h es e q u e n c eo ft o k e n s ) ，用来表 示页面的内容，还生成代表信息点开始的符号索引。符号系列( 字、h t m l 标记) 和通 配符被作为定位标志，用于找到页面上的数据。分装器归纳算法产生抽取规则并表示为 简单的标志语法( 1 a n d m a r k g r a m m a s ) 最后以这些简单的标志为基础从网页中抽取所需 的信息。 网页信息抽取技术可以发挥作用的地方有许多。不过，最成功的要数比价购物最近 两年来，比价购物系统己经投入商用。其中比较出色的是j u n d l e e 、j a n g o 、m y s i m o n 。 j u i l d l e e 【9 1 是1 9 9 6 年斯坦福大学的研究生们创建的。j u n d l e e 使用的是一种成为虚拟 数据库( v i r t u a ld a t a b a s e ，v d b ) 的技术，并利用h t m l 和x m l 的混合形式表示从多 个网站中获取信息。v d b 把分散的数据收集下来，规范化并整合在起，为程序员提供 个单一数据库的界面。分装器负责与数据源对接，把数据转换成数据库。v d b 有两 个主要组成部分：数据整合系统和数据发布系统。前者完数据的抽取，后者定期完成数 据库更新。数据整合系统有三个组成部分：一组分装器、一个影射器和一个抽取器。分 装器提供对不同网站的统一接口，用描述性编程语言建造，特别针对网站结构和链接网 站间的特点而设计。影射器用预定义的影射规则，把抽取出来的数据转换成统一的格式。 抽取器用字典和语言学规从非结构化的文本中归纳出其组织结构。两者都采用了特殊设 计的语言来编写规则，针对每个网站都有一个单独的分装器，而抽取器则针对所有类似 网站。在线进行抽取，用机器学习方法学得网站结构。 j a n g o 9 】的前身是s h o p b o t 是n e l l ) o t 的产品。发源于华盛顿大学的研究者加 o r e n e t z i o n i 和d a n w e l d 的研究成果。j a n g o 由四部分组成：一个自然语言前端，能将用 户请求转换成产品描述的逻辑表示：一个查询路由器( q u e r y r o u t e r ) ，能判定产品类别， 一6 一 p _ q ，t i t ， 、 i 东北大学硕士学位论文第1 章绪论 找出相关的一系列网站；_ 个集成引擎，能平行向选定的网站提交查询：一个过滤器， 能用类似于s h o p b o t 的方法，把信息抽取出来。在学习阶段，j a n g o 根据网上商店首页 的u r l 和产品领域知识，学习如何在网站上购物，能学得每个商店产品描述的格式， 获取价格等产品属性。在购物阶段，这些学得的描述将被用于抽取用户指定的产品信息。 信息抽取是在线平行进行，结果以价格排序显示给用户。 m y s i m o n 【9 】，是m i c h a e ly a n g 和y e o g i r ly u n 在1 9 9 5 年4 月一起创建的。一种被称 为虚拟学习代理( v i r t u a ll e a r n i n ga g e n t - v l a ) 的技术由y e o g i r l y u n 开发并用于网站的 学习中。v a l 生成若干智能代理，能模仿人的采购行为，经过练可从任何一个购物网站 上抽取信息。代理的训练过程是通过一个图形界面进行的，训练者无须是编程人员。在 浏览网上商店的同时，系统会复制其获得的信息。根据训练者的操作行为和复制的信息， 系统会生成能使代理运行的编码。 1 3 本文解决的主要问题 在w e b 数据库集成系统中，最终要把从各个w e b 数据库获得的数据合并到二个统 一的模式下。实际上，各个w e b 数据库的数据经常存在大量的重复，因此在合并过程 中必须要解决的一个重要问题是数据的去重，即重复记录识别。由于这些数据描述的是 现实世界的实体，如果能从实体的角度把重复的数据加以识别将会有效地达到去重的目 的。重复记录识别问题其实普遍存在于对多个数据源集成的领域中，由于从各个网站中 抽取出的数据信息主要是用x m l 或h t m l 标签描述的，这些数据大都是半结构或无结 构的，并且其所对应的结构化的信息事先不可知。为此，本文提出了一种重复记录识别 模型，针对从d e e pw e b 中抽取出的半结构或无结构的数据，利用全局模式分析所抽取 数据的属性间的匹配关系，并采用多种相似度估算器的方法来计算记录间的相似度，进 行重复记录识别。 从d e e pw e b 各数据源中抽取出的实体记录，通常是属性名称及匹配关系未知的， 这为准确的识别重复记录带来了挑战，针对这一问题，本文利用数据集成过程中的基于 特定领域的全局模式来分析不同数据源的实体记录值间的匹配关系，进而大大提高了计 算实体记录间的相似度的准确度。 在计算来自不同数据源的实体记录间的相似度时，本文提供了一个可扩展的相似度 算法库，并且在计算的过程中支持不同相似度算法相结合。在该模型中，新的相似度方 法可以