（管理科学与工程专业论文）基于语义的网络知识获取相关技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 伴随着i n t e m e t 的飞速发展，w e b 上出现了海量、异构、半结构化、动态的信 息资源，并且在这些w e b 信息中有8 0 以上的信息是以w e b 文本的形式存在的。 如何从这些浩如烟海的w e b 信息资源中寻找并获取有价值的信息和知识模式，已 经成为信息处理领域一个亟待解决的问题。基于语义的网络知识获取有助于解决 上述问题，它可以提高用户网上信息搜索的效率，可以将搜索结果分门别类，帮 助用户快速定位目标知识，并且从中抽取有价值的知识。 本文在分析网络知识获取相关技术的研究现状和存在问题的基础上，研究了 概念语义生成技术、文本分类方法、典型用户会话模板生成方法以及基于概念的 近似查询技术，主要取得以下研究成果： ( 1 ) 借助n m f 算法的分解结果具有实现上的简便性以及分解形式和分解结 果可解释性的优点，提出一种基于n m f 的概念语义生成方法。类比图像分解的思 想，将一个向量文本对应一幅图像，一个特征项数值对应一个象素点灰度值，应 用n m f 提取文本向量的概念语义，从而为大规模文本处理提供了一种新途径。实 验结果以及相关工作比较分析表明n m f 生成的概念语义能准确反映样本的局部特 征，有助于解决自然语言表示中固有的歧义问题。 ( 2 ) 将n m f 生成的概念语义向量用于w e b 文本分类。由于n m f 生成的局 部概念语义向量能和样本的特征直接对应，体现了各个分类中文本各自的特点， 因此比体现所有文本共同特征的全局概念语义向量具有更强的区分能力。实验对 比分析了局部概念语义空间和全局概念语义空间的构建对文本分类结果的影响， 实验结果表明在n m f 生成的局部概念语义空间中进行分类更精确。 ( 3 ) 根据n m f 算法分解大规模文本矩阵的特点，提出了一种基于n m f 的典 型用户会话模板发现方法。应用n m f 算法分解项文本矩阵来获取项之间的相关 性，在此基础上，引入语义向量和权重向量的概念，并通过定义语义向量的类别 紧密度来提取用户模板。从确保概念语义向量正交，减少概念语义向量冗余的角 度出发，选择n m f 的变体l n m f 进行降维，设计了一种基于l n m f 的典型用户 会话模板提取算法。由于l n m f 得到的概念语义向量是尽可能正交的，实验分析 表明，l n m f 方法的聚类效果好，适合于发现典型用户会话模板。 ( 4 ) 针对基于概念最小上界和最大下界求本体概念近似查询的不足，定义了 概念的最佳近似。利用复杂概念间的蕴涵关系，引入多元界和最简多元界的概念。 通过相关性质和定理证明了借助多元界可以求得概念的最佳近似，从而将求概念 最佳近似的问题转化为求概念的最简多元界问题。在此基础上，提出基于概念最 简多元界的本体概念近似查询方法，可以有效消除查询重写冗余，提高近似查询 第i 页 国防科学技术大学研究生院博士学位论文 的质量和查询重写效率。 ( 5 ) 给出了一个求概念最简多元最小上界的算法。详细讨论利用迭代递增的 过程和概念层次减少搜索空间、优化算法效率的措施，给出算法正确性和完备性 的证明，分析了算法的有效性。 主题词：概念语义，n m f ，文本分类，信息抽取，用户模板构造，近似查询 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t p a c t a l o n g 谢mt h er a p i dd e v e l o p m e n to fi n t e r n e t ，t h e r ea r ea b u n d a n t ，i s o m e r i c ， s e m i s t r u c t u r e da n dd y n a m i ci n f o r m a t i o nr e s o u r c e so nw e b a m o n gt h e s ew e b i n f o r m a t i o n ，a b o v e8 0p e r c e n te x i s ti nt h ef o r mo fw e bt e x t h o wt os e e ka n dg a i nt h e v a l u a b l ei n f o r m a t i o na n dk n o w l e d g em o d e lf r o mt h e s ev a s tw e bi n f o r m a t i o nr e s o u r c e s h a v ea l r e a d yb e c o m et h eq u e s t i o nu r g e n t l ya w a i t e dt ob e s o l v e di nt h ei n f o r m a t i o n p r o c e s s i n gd o m a i n t h eq u e s t i o n sm e n t i o n e da b o v ec a nb er e s o l v e de f f e c t i v e l yb yw e b k n o w l e d g ea c q u i r a t i o n i tc a nc l a s s i f ys e a r c hr e s u l t s ，w h i c hn o to n l ye n h a n c e st h e e f f i c i e n c yo fs e a r c hf o rw e bu s e r s ，b u ta l s oi m p r o v e st h ea b i l i t yo fl o c a l i z a t i o nt og o a l k n o w l e d g e ，a n de x t r a c t st h ev a l u a b l ek n o w l e d g e o nb a s i so fa n a l y z i n gt h ep r e s e n tr e s e a r c hs i t u a t i o na n de x i s t i n gq u e s t i o no fw e b k n o w l e d g ea c q u i s i t i o n ，t h i sd i s s e r t a t i o nm a i n l ys t u d i e st h ee s s e n t i a lt e c h n o l o g i e so f c o n c e p ts e m a n t i cg e n e r a t i o n , t h ec o m m o nt e x tc l a s s i f i c a t i o nm e t h o d s ，u s e rp r o f i l e c o n s t r u c t i o na n da p p r o x i m a t eq u e r yt e c h n i q u eb a s e do nc o n c e p t n l em a i nr e s e a r c h w o r k sa r es h o w na sf o l l o w s ( 1 ) w i 也t h ea i do fr e a l i z e so ns i m p l e ，e x p l a i n a b l em e t r i c sf r o mt h en m f a l g o r i t h m sd e c o m p o s i t i o nr e s u l t ，ac o n c e p ts e m a n t i cg e n e r a t i o nm e t h o di sp r o p o s e d i n a n a l o g y 、析t 1 1i m a g ed e c o m p o t i o n , t h en m f i sa p p l i e dt oe x t r a c tt h ec o n c e p ts e m a n t i c s f r o mt e x tv e c t o r ，p r o v i d i n go n en e ww a yf o rt h e l a r g e s c a l et e x tp r o c e s s i n g t h e e x p e r i m e n t a lr e s u l t sa sw e l la st h er e l a t e dw o r kc o m p a r i s o ni n d i c a t et h a tt h ec o n c e p t s e m a n t i c sf r o mt h ea p p l i c a t i o no fn m fc a nr e f l e c ta c c u r a t e l yt h ep a r t i a lc h a r a c t e r i s t i c o ft h es a m p l e ，w h i c hh e l pt os o l v et h en a t u r a ll a n g u a g ee x p r e s s i o np r o b l e m ( 2 ) mm e c h a n i s mo ft e x tc a l l a s i f i c a t i o nb a s e do nn m fi ss t u d i e d t h el o c a l c o n c e p ts e m a n t i c sv e c t o rf r o mn m fh a ss t r o n g e rc l s s i f i c a t i o nc a p a c i t yt h a nt h a to f g l o b a lc o n c e p ts e m a n t i c s ，b e c a u s et h ef r o m e rc a nc o r r e s p o n dd i r e c t l y 谢廿lt h es a m p l e c h a r a c t e r i s t i c ，w h i c hm a n i f e s t se a c hc l a s s i f i e dt e x tr e s p e c t i v ec h a r a c t e r i s t i c e x p e r i m e n t t oc o m p a r et h ei n f l u e n c eo fl o c a lc o n c e p ts e m a n t i c ss p a c ea n dt h eg l o b a lc o n c e p t s e m a n t i c ss p a c ec o n s t r u c t i o nt ot h et e x tc l a s s i f i c a t i o nr e s u l ti sc o n d u c t e d t h e e x p e r i m e n tr e s u l t si n d i c a t et h a tt h ec l a s s i f i c a t i o ni nt h el o c a lc o n c e p ts e m a n t i c ss p a c e b yn m f i sm o s tp r e c i s e ( 3 ) t a k i n ga d v a n t a g eo ft h ed e c o m p o s i o ne f f i c i e n c yo ft h el a r g e s c a l et e x tm a t r i x b yn m f ，am e t h o db a s e do n 黼f o rc o n s t r u c t i o nt y p i c a lu s e rc o n v e r s a t i o np r o f i l ei s p r e s e n t e d a c c o r d i n gt on m f ，t h et e r m t e x tm a t r i xi sd e c o m p o s e dt oc a p t u r et h e r e l a t i o n sb e t w e e nt e r m s t h e n , t h ec o n c e p t so fs e m a n t i cv e c t o r sa n dw e i g h tv e c t o r sa r e i n t r o d u c e d f u t h e r m o r e ，t h et h e c l a s sc l o s e n e s sd e g r e ei sd e f i n e dt oe x t r a c tt h eu s e r p r o f i l e f r o mt h ep o i n to fg u a r a n t i n gt h ec o n c e p ts e m a n t i c sv e c t o ro r t h o g o n a l ，r e d u c i n g t h ec o n c e p ts e m a n t i c sv e c t o rr e d u n d a n c y ，l n m fi sc a r r i e do nt h ed i m e n s i o n a l i t y 第i i i 页 国防科学技术大学研究生院博士学位论文 r e d u c f i o n b e c a u s el n m fo b t a i n st h ec o n c e p ts e m a n t i c sv e c t o ri sa sf a ra sp o s s i b l e o r t h o g o n a l ，t h ee x p e r i m e n tr e s u l ts h o w st h ein m f m e t h o dn o to n l yi m p r o v ef i l t e r i n g p r e c i s i o nm a r k e d l y ，b u ta l s oh a st h em e r i t so fa g g r e g a t i o n ( 4 ) t od e a l 谢t l lq u e r yr e f o r m u l a t i o n ，a l lo n t o l o g yc o n c e p ta p p r o x i m a t eq u e r y m e 也o db a s e do nm o s tc o n c i s em u l t i d i m e n s i o n a lc o n c e p ti sp r o p o s e d f i r s t l y ，t h em o s t a p p r o x i m a t ec o n c e p ti sd e f i n e d u s i n gt h ei m p l i c a t i o nr e l a t i o n sb e t w e e nt h ec o m p l e x c o n c e p t s t h em u l t i d i m e n s i o n a la n dt h em o s tc o n c i s em u l t i d i m e n s i o n a lc o n c e p ta r e d e f i n e d ，w h i c hm a k e si tp o s s i b l et oo b t a i nt h em o s ta p p r o x i m a t ec o n c e p tf r o mt h e m u l t i - d i m e n s i o n a lc o n c e p t s ot h eq u e s t i o nt og e tm o s ta p p r o x i m a t ec o n c e p ti s 仃a n s f o r m e dt og e tt h em o s tc o n c i s em u l t i d i m e n s i o n a lc o n c e p t r e l a t e dp r o p e r t i e sa n d t h e o r e m ss h o wt h a t t h em e t h o dc a nr e d u c et h eq u e r yr e f o r m u l a t i o nr e d u n d a n c y e f f e c t i v e l ya n di m p r o v et h ea p p r o x i m a t eq u e r yq u a l i t ya n de f f i c i e n c y ( 5 ) a na l g o r i t h mt og e tt h em o s tc o n c i s em u l t i d i m e n s i o n a ll e a s tu p p e rc o n c e p ti s p r o p o s e d 1 1 1 ed e t a i l e dp r o c e d u r ea n dm e t h o dt o r e d u c es e a r c hs p a c ea n di m p r o v e e m c i e n c ya r ed i s c u s s e d 。l a s tb u tn o tt h el e a s t ，t h ea l g o r i t h ma c c u r a c ya n dc o m p l e t e n e s s i sp r o v e d k e yw o r d s ：c o n c e p ts e m a n t i c s ，n m f ，t e x tc l a s s i f i c a t i o n ，i n f o r m a t i o n e x t r a c t i o n ，u s e rp r o f i l ec o n s t r u c t i o n ，a p p r o x i m a t eq u e r y 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1 新浪“体育竞技风暴”专栏文本数据类别分布2 8 表2 2k = 1 0 时，n m f 欧氏距离算法生成的各概念语义中前1 8 个特征项2 8 表2 3 表2 2 中各特征项对应的权值2 9 表3 1 类别和网页数量4 5 表3 2 在s v d 生成的全局概念语义空间中的分类精度4 6 表3 3 在n m f 生成的全局概念语义空间中的分类精度4 6 表3 4 在s v d 生成的局部概念语义空间中的分类精度4 6 表3 5 在n m f 生成的局部概念语义空间中的分类精度4 6 表4 1 基于n m f 的聚类结果5 6 表4 2 基于u 心伍的聚类结果5 6 表4 3 典型用户会话模板5 7 第v i i i 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1n m f 提取面部特征1 7 图2 1 不同约束下两个基向量的线性组合2 7 图2 2 不同约束下三个基向量的线性组合2 7 图2 3 实验结果3 2 图2 4s v d 和n m f 抽取的概念语义向量3 4 图2 5 概念语义向量矩阵3 5 图3 1 分词过程4 1 图3 2 在各种空间中分类精度的比较4 7 图4 1 两种方法聚类结果中类数目比较5 7 图4 2 两种方法聚类结果“紧密度”比较5 7 图5 1 本体映射和本体集成6 0 图5 2 复杂蕴涵关系的例子6 1 图5 3 最小上界和最大下界6 5 图6 1 算法6 1 的流程图7 6 图6 2 算法6 1 的伪代码。7 8 图6 3 函数f m d l 0 8 0 图6 4 函数g e n e r a t e 0 8 3 图6 5 函数f r e d 0 8 4 图6 6 函数v a l i d a t e 0 。8 5 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者擀：兰灶 日期：t 1 年p 月二1 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅：可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 圭f 杰 作者指导教师签名： 日期：砷年i 。月2 e t 日期：山吵年，口月2 z 日 国防科学技术大学研究生院博士学位论文 第一章绪论弟一早瑁下匕 现有w e b 是由大量的h t m l 页面组成，它的内容对人而言是可读、可理解的， 对于计算机而言则是不可理解的，这使得w e b 上的内容难以由计算机做有意义的 自动处理。而w e b 上的内容数量极其庞大且不断在增长，这又迫切要求w e b 上的 内容是计算机可理解的，可以由计算机做有意义的自动处理。本文围绕基于语义 的网络知识获取技术，主要进行四方面的研究：提出基于n m f ( n o n n e g a t i v em a t r i x f a c t o r i z a t i o n ，非负矩阵分解) 的概念语义生成方法；提出基于n m f 的文本分类 方法；提出基于n m f 的用户会话模板发现方法；对比分析研究目前常见的本体概 念近似查询技术，提出基于概念最简多元界的本体概念近似查询方法和相关算法。 本章综述了相关研究背景与现状，在阐述现有网络知识获取相关技术的基础上分 析了相关工作存在的不足，并介绍了本文的主要工作与全文结构。 1 1 研究背景 1 9 9 9 年n a t u r e 杂志上发表的一份研究报告表明，全球目前的网页数目超过8 亿，而且这个数字仍以每4 6 个月翻一番的速度增加。目前，w e b 已经成为一个 巨大的信息与资源中心，它已经深入到社会生活的方方面面；w e b 的目的不仅仅 是为了帮助人和人交流信息，还要让机器能够最大限度地参与和帮助人类的工作 【1 1 。到现在为止网络发展可以大致分为三个时代： ( 1 ) 手工编写网络内容( 如h t m l 页面) 。这种网页的特点是可以简单地用 统一的界面访问；需要巨大的创作和维护费用；难以处理动态变化的内容；大部 分页面是为了显示给人阅读而设计。 ( 2 ) 由机器生成页面，通常是动态的页面。在一个站点内部，信息以数据库 等形式组织起来。服务器根据数据库的内容和用户的需求，基于模板生成动态的网 页显示给用户。 ( 3 ) 语义网( s e m a n t i cw e b ) ，语义网的目标是实现机器自动处理信息，信 息的表示形式不仅可以供人阅读，也可以被机器自动处理。 目前网络上的大部分内容是针对人的阅读习惯设计的，无法让计算机程序按 照语义进行操作。同时网络上的数据通常分布在不同站点上，用不同方法和格式 表达，没有一个全局的系统，不利于进行集成和处理。随着网络内容的急剧增长， 用人工的方法来处理其中的大量信息越来越不可能，而机器又很难正确地处理这 些供人阅读的异构信息。人们在享受w e b 提供极大便利和丰富信息资源的同时， 对w e b 知识获取的准确性、无冗余性也提出了更高的要求【2 j 。 第1 页 国防科学技术大学研究生院博士学位论文 w e b 知识获取通常包括三个方面：从文件内容及其描述中获取有用的知识； 从w e b 的存取模式中获取有价值的知识，比如从相应站点的日志文件和相关数据 来获取该站点上的浏览者和顾客的行为模式；从链接结构中获取有用的知识。w e b 知识获取需要考虑w e b 自身的特点：( 1 ) w e b 上的数据通常是海量、分布、动 态和异质的w e b 文档，其信息存储不同于结构化的数据库；( 2 ) w e b 在逻辑上 是一个由文档节点和超链接构成的图，因此w e b 获取所得到的模式可能是关于 w e b 内容的，也可能是关于w e b 结构的；( 3 ) w e b 数据的非结构化或半结构化 特征使得这些信息数据难以清楚地用数据模型加以表示，且缺乏机器可理解的语 义。这些特点使得w e b 知识获取面临以下困难【3 叫： ( 1 ) 难以准确获得所需要的知识 w e b 上存在海量的数据，但由于w e b 是无结构的、动态的，为用户准确查找 和定位所需要的知识带来了极大困难，目前还存在返回的数据冗余性大、非相关 信息比重大以及搜索和查询的范围有限等问题。用户在w e b 上浏览或检索信息时， 往往通过使用门户网站所提供的搜索引擎工具。但目前的搜索引擎普遍存在精度 低和召回率低的问题。精度低表现在当用户输入关键词检索信息时，返回的查询 结果动辄成百上千条，更有甚者会达到几十万乃至上百万条，而其中大多数是一 些与检索内容无关的信息，也包括一些死链接，使查询者无所适从；召回率低是 由于w e b 上大量的信息未被索引或未被正确索引，因此导致搜索引擎返回的查询 结果并不全面。 ( 2 ) 难以获得信息之间潜在的知识 多样、海量的w e b 数据中蕴含着许多有用的、潜在的、但不容易被发现的知 识和模式，用户迫切需要发现这些知识和模式的方法和工具。比如w e b 个性化的 信息服务，一方面，对于不同层次、不同爱好和使用目的的浏览者需要个性化的 信息服务；另一方面，这个问题涉及到w e b 门户站点的管理、组织和经营。w e b 站点的经营和管理者为提高网站的声誉和效益，需要了解用户的需要和目的，其 中包括根据大多数用户的共同兴趣，开展有针对性的信息服务，以及对特定的用 户开展个性化的信息服务和电子商务活动。 ( 3 ) 难以在不同的异构系统间获取知识 w e b 上不同的系统可能使用不同的概念集或称本体来表示知识，这就会产生 异构问题。异构问题给信息系统之间的知识获取带来很大困难：一个查询由用户 的概念表达，但系统可能无法理解这些概念，因而无法回答这个查询。w e b 的分 布特性决定了即使是同一个领域，也可能存在多个异构概念集，用户或者系统不 可能理解和掌握所有的概念。因此如何在异构系统间进行查询是网络知识获取中 的一个关键问题l7 1 。 第2 页 国防科学技术大学研究生院博士学位论文 综上所述，从浩如烟海的w e b 数据中快速、准确地获取知识，是一个集统计 学、人工智能、模式识别、并行计算、机器学习和数据库等技术于一体的交叉性 研究领域。如何更好地抽取和表达样本语义和用户兴趣特征，以及如何在用户和 系统使用不同概念集的情况下进行查询成为当前网络知识获取领域研究中的核心 内容。本文围绕基于语义的网络知识获取的几项关键技术展开研究。 1 2 相关领域及研究现状 与网络知识获取密切相关的领域有以下几个：网络信息抽取、文本分类方法、 本体映射和n m f 理论与应用。论文将参考借鉴这些领域的大量研究成果，并应用 于论文的研究。 1 2 1 网络信息抽取 信息抽取( i n f o r m a t i o ne x t r a c t i o n ，m ) 就是从大量的文档中抽取出相关的信 息。信息抽取针对现有的信息驱动系统中预先以用户观点确定抽取内容，不仅仅 为用户提供所需要的网页，还抽取用户关心的数据，通过抽取的数据和源文档之 间的链接使得用户迅速找到需要的内容【8 】。信息抽取通过文本分析、语义分析、结 构化生成等过程抽取出有效的语义内容。 与复杂的自然语言理解技术不同，信息抽取技术并不需要全面理解整篇文档， 只是采用浅层的文本分析技术对文档中包含的相关信息进行分析，提取出设计者 关注的特定主题的信息。信息抽取技术对于从大量的文档中抽取需要的特定事实 来说是非常有用的。 w e b 信息抽取技术有多种分类方式【8 1 ，例如根据自动化程度就可分为人工方式 的信息抽取、半自动方式的信息抽取和全自动的信息抽取3 大类。根据各种工具 所采用的原理则可将现有的w e b 信息抽取技术分为以下4 大类：基于自然语言处 理方式的信息抽取、包装器归纳方式的信息抽取、基于h t m l 结构的信息抽取和 基于w e b 查询的信息抽取。 ( 1 ) 基于自然语言处理方式的信息抽取 这类信息抽取主要是用于源文档中包含大量文本的情况( 特别针对合乎文法 的文本) ，在一定程度上借鉴了自然语言处理技术，利用子旬结构，短语和子句 间的关系建立基于语法和语义的抽取规则实现信息抽取，目前采用这种原理的典 型系统有r a p i e r e 9 1 ，s r v t l 0 1 ，w h i s k 1 1 1 。下面具体介绍w h i s k 系统。 w h i s k 系统既适用于结构化、半结构化的文本也适用于自由文本。结构化和 半结构化的文本，一般不符合文法，所以系统主要是根据语义项的上下文实现感 兴趣信息的定位。此时基本上没有利用到自然语言处理技术，对这种情况不作详 第3 页 国防科学技术大学研究生院博士学位论文 细分析，对自由文本，系统首先根据分割符将源文档分割成多个实例( 每个实例 是一个语义相关的文本块，如，在一个房地产广告的页面中，每一则广告称为一 个实例) 。在交互式的环境下，系统每次呈现给用户一组实例。用户在可视化的 环境下根据系统提供的实例标记出 兴的信息并定义模式。系统使用语法分析 器和语义类分析器，分析出用户标记信息的语法成分和对应的语义类，生成基于 语法和语义类标记的抽取规则，实现信息抽取。 系统采用了先模式的方式，对于结构化和半结构化的文本，规则采用正则表 达式的形式描述了兴语义项的上下文及语义项间的分割符，利用这些信息达 到识别兴语义项的目的。对于自由文本，在一定程度上利用了自然语言处理 技术的思想。信息抽取的实质是根据语义相对应的语义类、语义项的上下文和所 处的句子成分实现信息的定位，即根据语义和语法的双重约束实现信息抽取。 这种基于自然语言理方式的信息抽取技术，将w e b 文档视为文本进行处理 ( 主要用于含有大量文本的w e b 页面) ，抽取的实现没有利用w e b 文档的层次特 性，获得有效的抽取规则需要大量的样本学习，需要用户对文本进行语法标注， 系统的实现比较复杂，并且抽取速度 。 ( 2 ) 包装器归纳方式的信息抽取 包装器归纳方式的信息抽取根据事先由用户标记好的样本实例应用机器学习 方式的归纳算法，生成基于定界符的抽取规则。其中定界符实质上是对兴语 义项上下文的描述，即根据语义项的左右边晃来定位语义项。该类信息抽取方式 和基于自然语言理方式的信息抽取技术最大的不同在于仅使用定界符和语义项 的上下文来定位信息并没有使用语言的语法约束。采用这种原理的典型的系统有 s t a l k e r e l 2 1 ，s o f t m e a l y 13 1 ，w i e n 1 4 1 ，下面根据具体的系统详细分析这类信 息抽取技术。 s t a l k e r 系统根据用户事先标记的样本页面和用户以嵌入式分类树 ( e m b e d d e dc a t a l o gt r e e ) 形式提供的页面的结构信息，应用逐步盖算法 ( s e q u e n t i a lc o v e r i n ga l g o r i t h m ) ，逐步归纳生成基于定界符的精确的信息抽取， 实现层次的信息抽取。 嵌入式分类树是s t a l k e r 系统中的一个重要概念，它是用户根据页面结构 定义的嵌套模式，该树型结构一方面描述了页面的逻辑结构，另一方面提供了模 式信息和语义信息( 树中节点的名称) 。嵌入式分类树中有3 种类型的节点：根 节点( 表示个文档) 、内部非叶节点( 称为l i s t 节点，表示多个同类对象的列 表) 、叶节点( 表示对象的语义项) 。系统为每个叶节点生成普通的抽取规则， 即用来定位语义项；为l i s t 节点生成普通抽取规则和迭代规则，其中普通抽取规 则用来定位多个对象组成的信息块，然后再应用迭代规则实现单个对象的定位。 第4 页 国防科学技术大学研究生院博士学位论文 该系统之所以称为层次的信息抽取是因为抽取时根据嵌入式分类树的层次进行， 并且某一节点的抽取规则是对其定界符的抽取结果执行的。下面说明信息抽取过 程：系统遍历嵌入式分类树，若根节点的孩子为l i s t 节点则在源文档中应用普通 规则抽取出多个对象组成的信息块，然后再在获得的信息块中应用迭代规则实现 单个对象的定位，若该l i s t 节点的孩子为叶节点，则系统在上一步获得的单个对 象构成的信息块中执行叶节点对应的抽取规则获得单个语义项。 该系统中语义的附加和模式的定义是在用户定义嵌入式分类树阶段完成的， 属于先模式的定义。信息定位的实质是使用左右边界实现兴信息的识别。其 他使用左右边界定位信息的系统一般是在个文档中应用各语义项的左右边界识 别出各语义项，然后再将各语义项组装成一个对象。而该系统在一定程度上是按 结构抽取和按文本抽取的结合。根据嵌入式分类树先获得高层次节点对应的大文 本块，然后再应用底层次节点对应的抽取规则，逐步获得想要的信息。该系统是 在上次的结果中使用左右边界实现信息的定位，并不是在个文档中，所以抽取 规则的形式相对简单，而且抽取的准确率相对高一些，另外由于使用嵌入式分类 树描述模式，所以可以抽取复杂的对象，但是规则中的定界符不仅仅是由h t m l 标记组成，而且还有某类网页经常出现的关词组成。所以该类信息抽取不但对 页面的结构有所依赖，而且对网页的内容也有所依赖j 要想获得精确的抽取规则 必须进行大量的样本训练。 w i e n 系统中事先由用户标记样本页面，系统根据页面逻辑结构的不同，使用 不同的启发式归纳算法生成不同的包装器。例如，如果某页面具有h l r t 结构( 页 面有h e a d ，b o d y ，t a i l 三部分，其中b o d y 由多个可使用左右标记分割的纪录的 列表组成) ，则产生一个h l r t 包装器。w i e n 系统语义和模式信息是用户附加 的。通过兴信息的左右边界实现信息的定位，方式和s t a l k e r 系统类似， 只是w i e n 对复杂对象不做处理。 ( 3 ) 基于h t m l 结构的信息抽取 该类信息抽取技术的特点是，根据w e b 页面的结构定位信息，在信息抽取之 前通过析器将w e b 文档析成语法树，通过半自动化的方式产生抽取规则，将 信息抽取转化为对语法树的作实现信息抽取。其中典型系统有l i x t o 1 s , 1 6 1 ， x w r a p 1 7 , 1 s ，r o a d r u n n e r 1 9 】和w 4 f t 2 0 】等，下面对具有代表性的系统进行分析。 x w r a p 通过交互式的方式，由用户在样本页中指定抽取区域的起始位置，系 统确定个抽取区域，并确定区域的类型，然后通过可视化的方式，由用户在样 本页中制定语义项( 如表头) 及与之对应的实例，系统自动产生抽取规则实现信 息抽取，最后系统利用启发信息或数据间的层次结构关系，生成，文档。 x w r a p 采用用户在网页中制定语义项的方式附加语义信息，即将网页的部分 第5 页 国防科学技术大学研究生院博士学位论文 内容作为语义项，对于不同的区域类型( 如t a b l e 、l i s t 等) 采用不同抽取规则提 高系统的灵活性和效率。但是x w r a p 只适合对含有明显区域结构( 如t a b l e 、l i s t ) 的网页进行信息抽取，不支持对普通网页的抽取，模式的表达能力也非常有限， 在学习阶段用户参与太多。 l i x t o 允许用户以可视化、交互式的方式对样本页面中的信息进行标记，系 统通过记录用户标记的信息，生成抽取规则，实现对相似结构网页的信息抽取。 用户无需具备与系统相关的专业知识，就可以完成对数据源的包装。l i x t o 中的 语义信息是由用户在样本学习阶段加入的，采用了先模式的方式，事先由用户在 可视化的界面中定义模式，抽取出的数据最终以x m l 格式存放，其中使用用户定 义的语义项作为x m l 文档中的元素类型名。l i x t o 在一定程度上简化了信息抽 取的步骤，增强了信息抽取的实用性。该系统的不足之处在于它的抽取规则使用 基于d a t a l o g 的e l o g 语言描述，实现和优化比较困难，另外抽取规则中对抽取信 息的描述不够丰富，而且对网页中的超链接不做处理，不支持图像信息和文献信 息的处理。 r o a d r u n n e r 通过对2 个或多个样本网页结构的比较，获得一个利用正则表达 式表示的该类网页面的通用结构模式，然后根据结构模式实现对相似页面的信息 抽取，系统根据结构模式中h t m l 标记间的关系，以嵌套的形式组织抽取出的数 据。r o a d r t m n e r 实现了全自动的信息抽取。结构模式确定的数据都抽取出来( 可 能包含用户不感兴趣的信息) 。抽取出的数据仍然没有语义信息，如果要利用的 话可以采用后模式的方式为其附加语义。另外该系统需要大量的训练文本，对网 页结构要求较多。 ( 4 ) 基于w e b 查询的信息抽取 该技术将w e b 信息抽取转化为使用标准的w e b 查询语言对w e b 文档的查询， 具有通用性。其中的典型系统有w e b o q l l 2 1 , 2 2 】以及p q a g e n t 2 l 2 4 】。 w e b o q l 是类似于s q l 语句的w e b 查询语言，它具有定位感兴趣信息和结构 重构的功能。系统利用w e b o q l 语言提出了一种通用的h t m l 包装器框架。系 统首先将输入的w e b 文档解析成一棵抽象的h t m l 语法树h y p e r t r e e ，然后用户 在信息抽取之前根据页面的结构和标记写出合适的查询语句实现信息抽取。 p q a g e n t 采用交互式的方式，用户首先选定样本页面，然后在可视化的界面 中，对样本页面进行标记，系统通过学习生成基于x q u e r y 2 5 】的抽取规则，利用生 成的抽取规则实现对相似结构页面的信息抽取。通过预先处理将源文档转化为符 合帆语法规范的文档，可直接利用x q u e r y 引擎执行x q u e r y 查询语句实现信息 抽取。 p q a g e n t 采用了先模式的方式，事先由用户附加语义并确定模式。抽取规则 第6 页 国防科学技术大学研究生院博士学位论文 以x q u e r y 的形式表示。应用抽取规则可直接定位到对象。x q u e r y 是w 3 c 的推荐 标准，主要用于x m l 文档查询，该系统将信息抽取转化成为利用x q u e r y 对w e b 页面的查询，因此相对于前面的系统，p q a g e n t 的抽取规则健壮性强，并且具有 很强的表达力。此外，p q a g e n t 统一了h t m l 和x m l 查询，不仅便于最终用户 使用，也便于作为包装器由应用程序调用，这是其他方法无法比拟的，但是p q a g e n t 对网页结构依赖性比较强，尽管抽取的范围相对广泛，但仍需迸一步扩大。 1 2 2 文本分类方法 1 文本分类方法研究现状 在w e b 出现之前，人们已经对文本自动分类问题进行了大量的研究，形成了 文档自动分类技术。随着w e b 上海量的文本信息的增加，文档自动分类技术的处 理对象从普通的文档扩展到了w e b 文本。很显然，文档自动分类技术也成为w e b 文本分类技术的基础。 国外对于文本自动分类的研究开展较早，5 0 年代末，l u h nhp 在这个领域进 行了开创性的研究，提出了基于词频统计思想的文本自动分类方法【2 6 】。1 9 6 0 年， m a r o n 发表了关于自动分类算法的第一篇论文口7 1 ，随后以s p a r kk 、s a l t o ng 以及 j o n e sks 等人为代表的众多学者也在这一领域进行了