（计算机科学与技术专业论文）定题检索中相关性比较算法的研究和实现.pdf

国防科学技术大学研究生院学位论文 摘要 f 随着i n t e r n e t 的迅猛发展，搜索引擎已成为人们在网上搜索信息的主要工 具，能对自然语言进行理解的智能搜索引擎更成为搜索引擎发展的重要方向。智 能搜索引擎中的相关性分析算法面向的对象是用户句和网页旬，它的主要功能是 将用户句和网页句进行比较并得出它们相关程度口本文以概念背景网和句型分类 树为依托，在限定领域中，实现了面向句子的相关性比较算法。 本文在理论上所做的工作主要有： l 、为了提高搜索的查准率和查全率，我们提出概念背景网来表达领域知识。它 模拟用户的多视角，从多个角度来表示领域知识；为了描述领域知识间的内 在联系，它采用多种概念关系来描述领域概念之间的关系。这样就将用户与 领域知识、领域知识内部的关系结合在一起。 2 、我们借鉴了h n c ( 概念层次网络) 理论中的作用效应链思想，根据网页摘要 句对领域知识不同侧面的描述，将搜索中的重要句型进行分类。形成一棵以 匹! 大句类为第一级结点，他们包含的句类为下级结点，以句型为叶结点的句 型分类树。 3 、提出对句子进行比较的相关性比较算法。用户旬和网页句是以类似于语法树 的中间结构提交给相关性比较算法的，算法在充分利用概念背景网和句型分 类树的基础上，对两个树状结构进行了比较。 在工程实现上所做的工作主要有： l 、完成概念背景网、句型分类树和地域分类树( 对不同地域进行分类) 的编码 工作。能对它们进行刨建、删除、显示等操作；能对它们包含的侧面和概念 进行添加、修改、删除等操作。 2 、完成相关性比较算法，能对用户旬中间结构和网页中间结构进行基于词、基 于逻辑关系、基于句子及其修饰属性的相关性比较。基于词的相关性比较只 对领域概念进行关键词的匹配；基于逻辑关系的相关性比较对用户句中领域 概念的逻辑检索式进行处理：基于句子及其修饰属性的相关性比较对以领域 概念为结点的句型树进行树状结构的比较。 关键词：自然语言理解，人工智能，搜索引擎 第l 页 国防科学技术大学研究生院学位论文 a b s t r a c t w i t ht h er a p i dp r o g r e s so fi n t e m e t ，s e a r c he n g i n e sb e c o m et h em a i nt o o lf o r p e o p l et os e a r c hi n f o r m a t i o ni nt h ei n t e r n e t a n di nt h e d o m a i no fs e a r c he n g i n e s ，i ti s a ni m p o r t a n tt r e n dt or & d i n t e l l i g e n ts e a r c he n g i n e sw h i c hc a r l u n d e r s t a n dn a t u r a l l a n g u a g e t h ea r i t h m e t i co fc o r r e l a t i v ec o m p a r i s o n d e a l sw i t hs e n t e n c e sc o m i n gf r o m u s e ra n dh o m e p a g e s ；i tc o m p a r e st h es e n t e n c e sa n do b t a i n st h ec o r r e l a t i v i t yb e t w e e n t h e mi nt h ea r t i c l e w eb r i n gf o r t ht h en e to fn o t i o n a lb a c k g r o u da n dt h ec l a s s i f i e d t r e eo fs e n t e n t i a lt y p e si nv i r t u eo ft h et w os t r u c t u r e s ，w ep a r t l yr e a l i z et h ea r i t h m e t i c w h i c h c o m p a r e b e t w e e ns e n t e n c e s t h ea u t h o rh a sm a d es o m et h e o r e t i c a lr e s e a r c h e si nt h ef o l l o w i n ga s p e c t s t h e a u t h o rh a s 1 b r o u g h tf o r t han e wn o t i o n a lr e p r e s e n t a t i o n ，c a l l e dt h en e to fn o t i o n a lb a c k g r o u d ， w h i c hs i m u l a t e su s e r st oo b s e r v et h ed o m a i n i a lk n o w l e d g ef r o mm a n yf a c e s ；w h i c h d e v e l o p sm a n yn o t i o n s l c o n t a c t st o e x p r e s s t h ei n h e r e n tr e l a t i o n s a m o n gt h e d o m a i n s ik n o w l e d g ef u r t h e r m o r e t h en e tc o m b i n e st h ec o n t a c t sb e t w e e nu s e r s a n dd o m a i n i a lk n o w l e d , 2 ea n dr e l a t i o n sa m o n gt h ed o m a i n i a lk n o w l e d g e 2 b r o u g h t f o r t ht h ec l a s s i f i e dt r e eo fs e n t e n t i a l t y p e s b a s e do nt h e t h e o r y o f h n c ( h i e r a r c h i c a ln e t w o r ko fc o n c e p t s ) a n di m p o r t a n c eo f s e n t e n t i a lt y p e sa c to n d o m a i n i a i k n o w l e d g e w ec l a s s i f y t h es e n t e n t i a l t y p e s i nt h es e a r c h e n g i n e s d o m a i ni n t oac l a s s i e dt r e e 3 b r o u g h tf o r t ht h ea r i t h m e t i co fc o r r e l a t i v ec o m p a r i s o n ，w h i c hc o m p a r e st h et r e e l i k e di n t e r c o n s t r u c t u r e sf r o mu s e ra n dh o m e p a g e s a n da l s om a k e st h eb e s to ft h e n e to fn o t i o n a lb a c k g r o t t da n dt h ec l a s s i f i e dt r e eo fs e n t e n t i a lt y p e s t h ea t , t h o rh a sm a d es o m ep r a c t i c a lr e s e a r c h e sa sb e l l o w s t h ea u t h o rh a s l d e s i g n e da n di m p l e m e n t e dt h en e to fn o t i o n a lb a c k g r o u d 、t h ec l a s s i f i e d t r e eo f s e n t e n t i a lt y p e sa n dt h ec l a s s i f i e dt r e eo f r e g i o n s w ec a r lc r e a t e 、d e l e t ea n dd i s p l a y t h e m ，a n da l s oc a na d d 、m o d i f ya n dd e l e t et h ef a c e sa n dn o t i o n si nt h e m 2 d e s i g n e d a n di m p l e m e n t e dt h ea r i t h m e t i co fc o r r e l a t i v e c o m p a r i s o n w e c a n c o m p a r et h eu s e r si n t e r c o n s t r u c t u r ew i t hh o m e p a g e s b a s e d o nk e yw o r d 、l o g i s t i c r e l a t i o na n ds e n t e n t i a lc o n s t r u c t u r e t h ek e y w o r d - b a s e dc o m p a r i s o no n l ym a t c h e s t h en o t i o n a lk n o w l e d g e ；t h el o g i s t i c r e l a t i o n b a s e dc o m p a r i s o nt r e a t sw i t hl o g i s t i c e x p r e s s i o no fn o t i o n a lk n o w l e d g e ；t h es e n t e n t i a lb a s e dc o m p a r i s o nc e , p b p a r e st h e t r e e 1 i k e di n t e r c o n s t r u c t u r e s k e y w o r d s ： n l p ( n a t u r a ll a n g u a g ep r o c e s s i n g ) ，s e a r c he n g i n e ，a i ( a r t i f i c i a li n t e l l i g e n c e ) 第2 页 国防科学技术大学研究生院学位论文 第一章绪论 1 1 搜索引擎的产生 时代的变迁衍生出许多不同时尚和潮流，上网已成为世纪末最为耀眼的时 尚和潮流之一。据悉，i n t e r n e t 已经发展成为当今世界最大的信息库，而且成 为全球范围内传播信息的最主要渠道之，其中w w w 的发展最为迅速。自从1 9 9 1 年诞生以来，w w w 已经发展成拥有约1 亿用户和近千万个站点、6 0 0 g 信息容量 的巨大分布式信息空间，而且这些数字仍在不断地增加。如何快速、准确地从 浩瀚的信息资源中寻找到所需的信息己经成为困扰网络用户的一大难题。搜索 引擎就是针对此问题而发展起来的一项新技术。 1 2 智能搜索引擎的产生 搜索引擎旨在为用户在页面的海洋中导航，可是现有的搜索引擎( 例如 y a h o o ) 没有一个可以完全有效地检索网络资源的。输入一项检索请求的网络用 户会被数以干计的回答弄得不知所措。检索结果常常涉及一些无关的网址，却 漏掉了那些存有重要资料的其它网址。可以说我们现在已经拥有了一个桌面上 的图书馆，但却无法有效地使用它。 人工智能( a i ) 注定要在网络时代扮演重要的角色。a i 的研究已经进行了 四十年，在许多人的心目中它似乎并没有完成它当初的承诺。的确，a i 在许多 领域中都遇到了困难，各种各样的专家系统显得过于脆弱。但是w e b 对于根植 于问题求解与知识处理的a i 来说无疑是一个绝好的环境。 w w w 网上智能信息搜索研究的目标是构造一个智能搜索程序，以便在 n t e r n e t 网上能自动寻找用户关心的信息。这一研究的动机来自于以下三个方 面： ( 1 ) 提高软件的智能化程度是软件发展的潮流。今后的软件将更加注重方便用 户使用、可识别语音图像、可理解自然语言。 i n t e r n e t 网为人工智能技术的验证提供了一个实际的环境。为了适应 i n t e r n e t 网上信息的迅速增长与变化，需要信息检索与人工智能技术相结合。 人工智能技术的验证标准可以从人为构造的有限实例验证走向面向 n t e r n e t 的 实用验证标准。 ( 2 ) 目前的主要浏览器和信息检索工具还没有智能搜索功能，像y a h o o 、 a l t a v i s t a 。例如，当用户仅输入“人工智能+ 搜索引擎”这个检索式，他的 目的是得到“人工智能”应用于“搜索引擎”领域的信息( 如“智能搜索引 擎”的相关信息) 。但是他只能得到出现“人工智能”和“搜索引擎”这两 个关键词的一些网页，却得不到他想得到的与“智能搜索引擎”相关的网页。 第3 页 国防科学技术大学研究生院学位论文 1 3 1 问题提出 1 3 文章的研究思路 智能搜索引擎在传统的搜索引擎中加入了人工智能技术，使搜索过程更快 捷、结果更符合用户需求。从下一章中我们可以看出智能搜索引擎是以后搜索 引擎发展的重要方向。但是现有的人工智能技术一般都是在某一特定范围内、 针对某一特定问题的解决方案，所以在通用搜索引擎中应用人工智能技术的潜 力不大。本课题研究的对象是“定题检索系统”。所谓“定题”就是特定领域的 意思，但是我们研究的目的是不仅要把针对某一个固定领域的智能搜索引擎做 好，而且这种技术还能应用到其它的特定领域。我们的研究目的就决定了我们 必须总结用户查询领域知识的一般规律。 现今的很多搜索引擎的人机界面是基于关键字的检索式。用户很难仅用几 个关键词就能准确、完整地表达他的需求；而且构造基于关键字检索式的思维 方式也不符合大多数用户的思维习惯，用户往往得挖空心思地考虑如何构造一 个高效且准确的逻辑检索式。人们在日常生活中是用自然语言的语句来表达自 己的思想，所以我们的智能搜索引擎的目标就是能理解自然语言，用自然语言 的语句来实现人机交互。 相关性比较模块是搜索引擎的重要组成部分，它的优劣在很大程度上决定 了搜索引擎速度的快慢和搜索结果的好坏。在我们的搜索引擎中，相关性比较 算法不仅需要追求高效率，而且还要充分利用我们随领域知识和自然语言的理 解，提高搜索引擎的查准率和查全率。 这一节主要说明了我们研究的三大目标：一、研究如何在限定领域搜索引 擎中表达领域知识，而且这种表达方式应该具有良好的可扩展性；二、研究如 何在限定领域搜索引擎中理解自然语言：三、研究相关性比较算法，使之能够 充分利用领域知识，最终实现以句子为单位的搜索流程。 1 3 2 解决思路 1 3 2 1 在限定领域搜索引擎中表达领域知识 现今智能搜索引擎在其固定领域上，针对这一领域的固有规律，采用专家 系统的方法，往往可以做得很好。但是很难把系统移植到其它的领域。因为在 一般情况下，知识库中的推理规则只适用于产生这些规则的那个领域。由于我 们要求我们的搜索引擎能够很方便地从一个领域移植到另一个的领域，所以我 们对领域知识的组织不能拘泥于某一个具体的领域，应该从所有的领域产生、 发展规律入手来考虑。通过思索、研究，我们总结出的规律是： a 般领域知识的产生类似于符号系统，在定的公理、基础概念、推理等基 础上不断地向深度和宽度方向上发展。 b 深度方向是指：1 针对特定问题不断地进行细化、分割研究；2 本领域内 第4 页 国防科学技术大学研究生院学位论文 部的概念进行交叉结合。 c 宽度方向是指：本领域与其它领域进行交叉结合( 这与符号系统不同) 。 那么我们的领域知识就可根据该领域的基本概念自顶向下进行分类，对于 领域内概念的交叉，采用某些概念关系来表达，对领域间的交叉，采用另一些 概念关系来表达。这样就形成一棵以基本概念为结点的树，也可以叫做网，因 为树中还存在多种概念关系。 搜索引擎主要是为网上用户服务的，所以我们不仅需要从领域自身发展的 规律来分析领域知识的结构，而且需要从用户的角度来思考和观察领域知识。 同一句话由不同的人说出就代表不同的含义，这说明搜索需求与用户的类 别有关。虽然搜索引擎面向的用户数目可多可少，但是用户的类别是相对固定 的。也就是说，我们有可能对用户进行分类。下一个问题就是从什么角度分类， 应把用户分为几类? 这个问题就与领域面向的用户群有关了。总的原则是用户 数目越大，用户越重要，分类就越细致。至于具体的分类方式，应具体问题具 体分析。 从领域的发展规律，我们可以得到一些不同领域专家的分类。从用户的角 度，我们又可以得到一个分类。现在的问题就是如何把领域专家的分类和用户 视点的分类结合在一起? 在这儿，我们借鉴了软部件库的多面分类法，把整个 领域用多个侧面来表示( 比如一个侧面是领域专家从应用理论方面的分类， 个侧面是领域专家从应用方面的分类，一个侧面是抽象方面的分类) ，每个用 户的视角就由这些侧面组成的向量来表示。具体这个向量在每个侧面的权值， 就由用户所属的用户群( 如该用户属于应用方面的软件用户群) 以及与用户以 往交互的结果来动态决定。 1 3 2 2 在限定领域搜索引擎中理解自然语言 自然语言理解是人工智能的一个老、大、难问题，很多学者在这方面做了 大量有益的工作。我们在考察他们的成果后，对h n c ( 概念层次网络) 这种自 然语言表示机制很感兴趣。近年提出的h n c 在继承了这几十年来自然语言研究 成果的基础上有所创新，是是目前广受业内人士关注和称赞的理论体系。它是 我们搜索引擎中自然语言理解的理论基础。 自然语言理解在搜索引擎中的应用与在机器翻译和语音识别等领域中的应 用有所区别。在机器翻译等领域中对理解的要求比较高，它要求完全理解一个 句子中的所有成分以及形成包含句子所有成分的句子框架：而在面向领域的搜 索旬中最重要的是领域概念和句子对这些概念不同侧面的描述，也就是说，并 不需要理解句子中的所有成分。 根据搜索引擎中自然语言理解的特点，我们对用户旬理解程度的要求是： 1 得出领域概念及其修饰成分；2 用户句表达的是领域概念的哪些侧重。 在课题组中的另一模块一用户处理模块，可以将句子处理成一棵句法树， 在句法树中表面了句子的成分和领域概念的位置。那么，现在我们的问题就变 为：1 领域概念的修饰成分修饰的是领域概念的哪些侧面? 2 整个句子又是 着重于领域概念的哪些方面? 针对第一个问题，我们采用h n c 对抽象概念的表达方式来进行表示和理解。 对第二个问题：由于我们重点是理解整个句子随领域概念的总体描述，所以不 能采用一般自然语言理解中的句类分类方式。为此，我们对网页和用户句进行 第5 页 国防科学技术大学研究生院学位论文 了统计，参照c 理论中的作用效应链思想，提出了句型分类树，我们用它来 将搜索中的重要句型分类。 10 3 2 3 有效的相关性比较算法 在我们解决了领域知识的表达和对搜索中旬子的部分理解后，我们就致力 于把这些表示机制融合在相关性比较算法中。我们提出对树状结构进行比较的 相关性比较算法。用户句和网页句以类似于语法树的中间结构提交给相关性比 较算法，算法充分利用概念背景网和句型分类树，对树状结构进行比较并返回 网页句的排序结果。 在加入领域知识和自然语言理解后，我们的搜索引擎在分词词典、网页分 类、相关性比较等方面于其它的搜索引擎有很大的不同。 我们在分词词典中加入了领域知识在概念背景网中的地址信息，也加入了 地域分类词、句型分类词、抽象概念等信息，使分词的同时就能得出词的语义 信息。我们虽然把网页随机地放入数据库中，但是网页组织的逻辑结构实际上 却存在于概念背景网内；我们把网页位置信息放在与网页相关的领域概念下， 换句话说，网页是以领域知识为中心组织的。 与一般搜索引擎不同的是我们的相关性比较算法不是基于关键词的，它的 比较单位是简化句型树( 定义参见5 1 2 ) ，它是基于句子的比较。简化句型树 中的结点是由一个或者多个有修饰成分的概念集合构成的，而且结点间可能还 存在多种关系( 如修饰关系) 。所以我们在相关性比较时，不仅要考虑到结点之 间的比较，还要考虑到结点间关系是否相似。为此，我们的比较算法是分步进 行的。第一步是基于词的比较，由关键词是否相似过滤掉部分网页。这一步是 出于对比较时间考虑的，如果对每个网页都进行树状结构的比较，效率会很低 的，因为大部分网页不是用户所需要的网页。第二部是基于逻辑关系的比较。 我们件领域概念之间的各种关系转化为逻辑关系，即用与、或、非来连接领域 概念，通过逻辑表达式的比较来限制调无关网页。第三步是基于句子的树状结 构的比较，因为第二部已经处理了概念之间的关系，所以这一步只针对对应结 点进行比较。 10 4 本文的主要内容 作者研究的课题“智能搜索引擎中的相关性分析”是“定题检索系统”课 题的子课题。在搜索引擎中，相关性分析的对象是用户句和w w w 上的网页。通 过相关性分析，我们应该得出它们是否相关以及它们的相关度是多少。由于我 们研制的是面向领域的搜索引擎，所以与其它的通用搜索引擎相比，我们可以 做得更好。在本文中，我们将阐述对“智能搜索引擎中的相关性分析”这个问 题的解决方案。 第一章绪论提出了课题要面临的主要矛盾和我们解决这个问题的总体思 路。 第二章对国内外现有的通用和专用搜索引擎进行概述，并对其中使用的关 其体定义参觅第五章 第6 页 国防科学技术大学研究生院学位论文 键技术作了较为详细的阐述，并且可以得出智能搜索引擎是搜索引擎发展方向 的结论。 由于我们专用搜索引擎研究的主要方向是能对自然语言进行语义理解，所 以在第三章中介绍了一个较为有效的自然语言处理机制洲c ( 概念层次网络) ， 我们的搜索引擎用到了其中的作用效应链思想和对抽象概念的表达机制。 第四章介绍了概念背景网的组织思想、结构和功能，它采用一种全新的网 状结构来表达领域知识之间的关系和用户与领域知识的关系，它是相关性比较 的基础结构。 第五章从相关性比较的角度介绍了我们定题检索相同的体系结构，重点着 墨于与其它搜索引擎不同的部分。在体系结构中提出了句型分类树这种新的句 子分类结构和相关性比较算法的理论流程。 第六章叙述了相关性比较算法在工程中的实现流程，对其中的重要流程作 了较为详细的描述，并举出一个相关性比较的例子。 第七章是不仅总结了整篇论文，而且提出了本文的适用范围和有待完善的 部分。 第7 页 国防科学技术大学研究生院学位论文 第二章国内外发展现状 搜索引擎分为通用搜索引擎和面向限定领域( 即定题) 的搜索引擎。在这 一章中将分别介绍它们的发展现状。 2 1 通用搜索引擎中的关键技术 要设计和实现一个好的搜索引擎主要要解决以下问题：如何从网上获取网 页并随时更新这些网页? 如何对数据库中的网页进行分类，使之更有效地组织 并便于查询? 采用什么样的算法从数据库中最快、最好地获取用户需要的网页? 这一节中将讨论通用搜索引擎中是怎么解决这些问题的。 总的来说，目前的通用搜索引擎主要的特点如下： 信息发现一般采用r o b o t 技术。 检索模型一般采用向量空间模型、概率模型、布尔模型。 文本分类方法常用人工分类、布尔法、概率法、矩阵变换法。 许多搜索系统提供了一些方便用户的功能。如i n f o s e e k 允许用户定制新闻， a l t a v i s t a 以流程图的方式显示搜索结果。 目前的系统一般是基于关键词，很少有系统提供自然语言查询。根据第二 届搜索引擎评测结果，i n f o s e e k 和e x e i t e 提供自然语言查询。对于中文搜 索系统，几乎没有系统能够提供自然语言查询功能。 反馈信息基本上是网址加上网页初始的一句或一段，用户从反馈信息对 网页内容不可能有较全面的认识。 为了找到所需的文档，一般方法是运行一个称为r o b o t 的搜寻程序。r o b o t 是一个能利用h t t p 读取w e b 页面并沿着h n 儿文档中的超链在w 啊上进行自动 漫游的程序，也被称为s p i d e r 、w o r m 、c r a w l e r 。它按照用户的要求自动访问w w w 资源，并将判断结果返回给用户。但在信息量巨大的而且飞速增长的w w w 上， 每个用户都使用该方法是不现实的，通常采用的方法是由特定站点负责对网络 信息资源进行系统、广泛的遍历j 并建立相应的索引数据库，用户直接在索引 数据库中进行查询，以确定相关文档的位置，这就是现在广为使用的网络检索 站点，如y a h o o 、a l t a v i s t a 、s o u h u 等所实现的主要功能。 要建立全面的索引数据库，必须对w w w 进行系统而全面的遍历。我们可将w w w 作为一个有向图处理，将每一个页面看作图中的节点，将页面中的超链看作图 中的有向边。因此，我们可以使用有向图遍历算法( 深度优先算法或广度优先 算法) 对其进行遍历。因为w w w 是一个典型的c l i e n t s e r v e r 结构系统，所以 可以在一台或几台主机上完成胃删的遍历。对w 删的遍历一般采用如下的三种 方法： ( 1 ) 给r o b o t 设定一个子u r l ，r o h o t 提取其中的超链? 并利用深度优先算法 第8 页 国防科学技术大学研究生院学位论文 或广度优先算法完成对唧w 的遍历。 ( 2 ) 选定一组不同类别、被访问频率高的u r l ，r o b o t 从这些u r l 开始遍历。 ( 3 ) 根据域名或地域代码或i p 地址将厢w 空间划分为多个子空间，运行多个 r o b o t 程序，并行地在不同的子空间中进行遍历。 2 1 2 文档的识别与分类 判断所读取的w e b 文档是否满足用户的要求，最终可归结为一个文本的分 类问题，即判断文档是否属于用户所需的类别。许多w w w 索引系统( 如y a h o o 、 l y o o s ) 在对下载的w e b 文档进行索引前，需要对文档进行分类处理，以便于用 户的查找和提高检索效率。较为常用的文本分类方法有布尔法、向量空间法、 概率法、实例映射法等。下面介绍其中两种较为典型且分类正确率较高的分类 方法：n a i v eb a y e s 法和矩阵变换法。 ( 1 ) n a i v eb a y e s 分类法 n a i v eb a y e s 分类法是一种概率方法，虽然对文本的分类处理作了很多简化， 但n a i v eb a y e s 法仍然能得到较高的分类正确率。 n a i v eb a y e s 分类法假设所有词条在文档中出现概率是相对独立的。假设 集合为文本类的集合，判断一个文档d 是否属于某个类别c 。，可通过计算p ( c d ) 的概率完成，即给定文档d + 属于文档类c 。的概率是多少。n a i v eb a y e s 法 的判别原则就是将d 指定到使p ( c 。 d ) 达到最大概率的类c 。中，即求解a r g m a x ，( c id ) = p ( c d ，) po i d 。) p ( c ，l d 7 ) 。p ( c ，id ) 可根据文档的长度l 进行分解： 根据b a y e s 定律可得： 尸( c 川。) = 亭孚苷苦号手旨幽* c - v , c 其中p ( c ，l l ) 是给定长度为l 的文档属于类c ，的先验概率。我们可假 设文档所属的类戤同它的长度无关，因此p ( c 。 l ) = p ( c ；) 。p ( c 。) 的概率可以从 训练文本的统计得到( 其中| c ，1 表示训练文本中属于c 。的文档数，i d i 表示所 有的训练文档数) 。 根据所有词条的出现是相互独立的和文档的类别同长度无关两项假设， 我们可同样得到p ( d i c 。，l ) 的值( 其中w 。为文档中的词条，i d | 为文档d 的词 条数，f 为训练文档中所有词条，t f ( w ，c ，) 为词条w 在所有属于c ，类的训练文 档中的出现的次数) ： l 。 p ( d ic ，) * li p ( w ，ic ，) 鼻cw 小加高书蔫 w 一 e i fi 根据l ；上上两式即可求出满足8 2 - g n l a xp ( c 。i d ) 中的文档类。 第9 页 国防科学技术大学研究生院学位论文 ( 2 ) 矩阵变换分类法 矩阵变换分类法的主要思想是分别建立文档和文档类的向量空间，文档空 间和文档类空间都用矩阵来表示；两个向量空间采用不同的项，文档空间的项 选用文档中的词，而文档类空间的项则根据不同的情况，分别选用文档格式符 或描述词；再建立从文档向量到文档类向量的映射关系，这样就可以把分类问 题转化为矩阵变换的数学问题来解决。例如，可以用最d , - - 乘法求得近似的变 换矩阵。 下面用一个例子说明矩阵变换分类法的分类过程。假设文档集中共有4 篇 训练文档d 。、巩、d 。、矾，文档分别属于4 个文档类c ，、c 。、c 。、c 。，其中d ，( c 。、 c 。) 、d 2 g 、c 3 、q ) 、d 3 c 】、c 4 ) 、9 。 c ，、c 。】。矩阵a 表示文档空间， a 中的行表示一篇文档，a 中的列为文档集中出现的词，矩阵a 的一个元素a ； 表示词条t ，在文档d 。中的权重。矩阵b 表示文档类空间，b 中的行表示a 中相 d l a ：d 2 d 3 见 d l b ：d 2 d 3 现 c lc 2 00 01 10 10 c j c 4 11 11 01 1o 应文档所属的类别，b 中列为文档类标识符，b 中的元素表示文档是否属于此类， 若d j 属于c j ，则b j j = l ；若d l 不属于c j 则b j ，= o 。a 、b 矩阵如下所示： 矩阵a 、b 之间的关系可用矩阵变换的方式表示：f - - b 7 ，矩阵f 可用奇 异值分解法求得： f = b 7 u s 一1 v = 0 1 9 80 0 2 0 0 0 0 1一o0 0 100 0 20 0 0 5 00 0 0 300 2 00 0 1 200 5 900 0 8 00 0 30 0 2 8 一00 0 1 00 0 100 2 3 40 0 0 0 l0 0 0 500 8 20 0 4 90 0 0 100 3 2 矩阵f 反映了文档词条和文档类之间的相关性。f 中的行对应于文档类向 量，列对应于文档向量，f ，；反映了文档类和词条间的相关度。求得转换矩阵f 后，即可用它来进行文档分类。对任意的文档向量x = ( x 。x 。，x 。) ，它在文档 类空间的投影y = ( y 。，y 2 ，y ) ，可由f 导出：y = ( f x 7 ) 7 。y 中的各分量y 。，y 。，y 。 反映了x 与各文档类c ，、c 2 、c - 的相关度，将这些值从大到小排序，就可 得到文档的所属分类。 2 1 3 检索模型 文档的索引与检索模型是w w w 索引与检索系统的核心，检索模型的优劣直 接影响到系统的效果。现今搜索引擎中使用较多的检索模型有布尔检索模型、 向量空间模型与概率模型。 第l o 页 露孓孓孓c=正牝铊咖铊 ，4 9 9 9 07禾令小n ，3 1 1 1 0 z&n 正d d d d 7 o o 0 o叭眦孓 国防科学技术大学研究生院学位论文 ( 1 ) 布尔模型 布尔模型是一种简单的严格匹配模型( e x a c tm a t c hm o d e l ) 它定义了一个二 值变量集合来表示文档，这些变量对应于文档中的特征项，一般由训练文档集 中的词条或短语组成。如果词条对文档内容有贡献，则赋予t r u e ，否则置为 f a l s e 。检索时，根据用户提交的检索条件在文档表示中的逻辑关系是否满足， 将检索文档分为两个集合：匹配集和非匹配集。因匹配结果的二值性，无法在 匹配的结果集中对查询结果进行相关性排序。 布尔模型实现简单，检索速度快，在许多检索系统中得到应用，y a h o o 、s o u h u 等诸多著名网络检索站点均采用了布尔检索模型。但布尔模型的文档表示能力 差，无法区分特征项对文档内容贡献的重要程度，而且逻辑表达式过于严格， 往往会因为一个条件未满足而忽略了其它全部特征，造成大量的漏检。 p 范数模型是对布尔模型的扩展，它克服了简单布尔模型匹配函数漏检率高 的致命缺陷。在p 范数模型中，假设文档d 可表示为d ：( d ，d ，d 。) ，用 户查询可表示为q = ( q 。，q 2 ，q n ) ，其中d ，和q ；分别表示第i 个特征词条对 文档内容和查询内容的贡献程度，d ，、q ，在【0 ，1 的区间上取值。定义文档与 l g ，( 1 一d ) ， m ( d ，q ) = 1 一j “l f f io ，l 查询间的相似度： 1 p o c 。根据具体应用改变d 。、q 。和p 的取值即可达到不同的检索效果。当p = 。c ，且d ，的取值为0 或1 ，q l = q 2 - - = q n ：l 时，p 范数模型则退化为简单布尔 模型。在实际使用中p 的取值由实验得出，取值范围一般为 2 ，5 。 ( 2 ) 向量空间模型 向量空间模型( v s f ：v e c t o rs p a c eh l o d e l ) 是近年来使用较多且效果较好的 一种信息检索模型。在v s m 中，将文档看作是由相互独立的词条组( t ，l t 。) 构成，对于每一词条t 。都根据其在文档中的重要程度赋以一定的权值w 。，并将 t 】，t 2 t 。看成一个n 维坐标系中的坐标轴，w ，w 2o w 。为对应的坐标值。这样 由( t ，t 。t n ) 分解而得的正交词条矢量组就构成了一个文档向量空间，文档则 映射成为空间中的一个点。对于所有文档和用户查询都可映射到此文本向量空 间，用词条矢量( t 。，w 。，t 2 ，w 2 ，t n ，w n ) 来表示，从而将文档信息的匹配 问题转化为向量空间中的矢量匹配问题。假设用户查询为q ，被检索文档为d ， 两者的相似程度可用向量之间的夹角来度量，夹角越小，说明相似度越高，相 似度计算公式如下： s i t ( q ，d ) = c o s ( q ，d ) = 表示矢量中词条t 及其权值w 的选取被称为特征提取，特征提取是利用向 量空间模型进行信息检索的关键步骤。在自然语言文档中，各词条在不同内容 的文档中所显现纳壤事分南最不同彝虬因此可根据词条的频率特征用统计的方 第1 1 页 谤执声 国防科学技术大学研究生院学位论文 法进行特征提取。在文档中，词条的重要性与词条在文档内的频率成正比，与 向量文档集中出现该词条的文档频数成反比，因此可构造词条权值评价函数： 其中t f 表示词条t 在文档d 中的出现频数，n 表示用于特征提取的全部向 量文本的文档总数，n 表示词条t 的文档频数。在实际用于中，为避免因文档 长度引起的频数变化，还应对词条中的评价函数作规范化的处理： h 。；矿】。g ( n + 05 ) h w*= ( 3 ) 概率模型 布尔模型和向量空间模型都将文档表示词条视为相互独立的项，忽略了表 示词条间的关联性，而概率模型则考虑到了词条、文档的内在联系，利用词条 间和词条与文档间的概率相依性进行信息检索。 二值独立检索模型( b i r ：b i n a r yi n d e p e n d e n c er e t r i e v a l ) 是实现简单且效 果较好的概率检索模型。在b i r 中，假设文档d 和用户查询q 都可用二值词条 向量( x i ，x 2 ，人，x 。) 表示，如果词条t f 属于d ，则x 。= 1 ，否则x ；= 0 。利用b a y e s 公式并经过简化后可得文档与用户查询间的相关函数： 盛m c 。，q ，= - o g j j 气 其中p ：= r 。r ，q i = ( f t - r 。) ( f 叶) ，f 表示训练文档集中文档总数，r 表示训 练文档集中与用户查询相关的文档数，表示在训练文档集这包含词条t 。的文 档数，r 。表示r 个相关文档中包含词条t 。的文档数。 ( 4 ) 概率推理网络 概念推理网络是近年被提出并深受重视的一种新型检索模型。推理网络模 拟人脑的推理思维模式，将文档内容与用户查询匹配的过程转化为一个从文档 到查询的推理过程。基本的文本检索推理网络包含文本网络与用户查询网络两 部分，如下图所示。图中每个节点表示一个文档、一个查询或者一个概念，其 中d ；为文本节点，t ；为文本表示节点，r ；为文本概念节点，c ，为提问概念节点， q ；为用户查询节点，有向边表示节点间的概率相依性。网络中文档节点与查询 节点间的相关性可以表示为：只要给定文档节点的先验概率和中间节点的条件 概率，就可计算出查询节点的后验概率。如要估算用户查询q 与文档d ；间的概 率相关性p ( rj q ，d 。) 则应先将文档节点d 。置为t r u e ，然后依次计算p ( q ：t r u e ) 的相依节点的概率即可。 推理网络同其他概率模型相比有很多优点，推理网络能够将其他许多概率 模型映射到网络中，并能够采用多种检索形式和其他知识源得到的统计数据或 经验数据，进行综合检索。 第1 2 页 国防科学技术大学研究生院学位论文 ( 5 ) 基于用户兴趣的学习算法 在实际浏览过程中，有时候用户并不能准确地输入自己的兴趣，这就要根据 用户对信息的选择来逐步明确用户的兴趣，于是便需要研究学习用户兴趣的算 法。准确地把握用户的兴趣涉及到机器学习中的分类方法，如判定树、最小距离 算法、b a y e s 信念网络以及神经网络等。其目的是通过文本抽取自动地或在用 户控制下进一步明确用户兴趣的内容，更准确地判断搜索到的网页与用户兴趣的 相似性。该过程在信息检索中被称为相关反馈，是信息检索领域的一个主要研究 问题。在用户控制下，根据向量表示法，相关反馈的一种简单方式可以按如下所 示的方法进行处理： 若用户对得到的每个网页v i 给出一个评价值e i ，那么，用户兴趣u 可用下 面的公式更新： u = y ，一， ，# l 在自动反馈过程中，可以采用最小距离和b a y e s 信念网络来扩展用户的兴 趣，一般要求用户兴趣的扩展部分与u 具有相关性，而相关性的学习过程随具体 的表示方法和学习算法而有所不同。 也可以把用户控制和自动反馈相结合，搜索程序自动建立一个链接，用户 进行评判，形成一个交互式的渐进过程。 在一个有多个用户访问的网点上，学习的目的就是获得用户对当前网页中 某个链接选择的可能性，即学到一个从p a g e i n t e r e s t l i n k 到 0 ，1 上的函数 f ，f 可通过统计用户的访问来获得。其中p a g e 是网页的集合，i n t e r e s t 是用户 兴趣，l i n k 是链接的集合。通过激励学习( r e i n f o r m e n tl e a r n i n g ) 可进一步提 高f 的准确度。 在上述已有的用户兴趣的表示中仅表示了用户兴趣的要素，没有反映出这 第1 3 页 国防科学技术大学研究生院学位论文 些要素之间的关系。假如一个用户输入他的兴趣”w o r ka n de n e r g y ”( 功和能) ， 他可能得到许多与物理学无关的内容，因为”w o r k ”也可以理解为工作、著作等。 那么，解决这个问题的方案就是在用户兴趣的表示中加入反映关键词之间关系 的描述。在上述例子中，就可以加入“w o r k ”和“e n e r g y ”都属于物理学范畴这 一关系来进一步限定用户的兴趣。 2 1 4 著名w w w 检索站点采用的技术 ( 1 ) 检索软件组成 现在在i n t e r n e t 上有许多孵查询站点，如y a h o o 、a l t a v i s t a 、w e b c r a w l e r 、 搜狐( s o u h u ) 等。这些站点的结构与工作原理都很近似，一般都是由搜索r o b o t s 、 搜索引擎、文档索引库和查询服务等四大模块组成，如下图所示。 ( 1 ) r o b o t s ：r o b o t s 用于嗍的漫游与网页的下载。 ( 2 ) 搜索引擎：搜索引擎是搜索引擎站点的核心，它协调各r o b o t s 的工作， 并对下载的网页进行索引与组织。 ( 3 ) 索引数据库：r o b o t s 采集到的网页索引和相关描述信息全部存储在索 引数据库中。不同的检索站点记录的内容是不同的，有些记录了网页的全部内 容，有的只记录网页的地址、标题、关键词、摘要等信息。标题的检索站点数 据库的规模也不同，例如嗍w o r m 记录了8 0 0 0 万个网页。数据库的规模直接 影响了系统查询的查全率。 ( 4 ) 查询服务：查询服务子系统负责接收用户的查询请求和根据用户查询进 行数据库检索，并将查询结果按相关度反馈给用户。 ( 2 ) 检索工具与检索服务 按照工作方式，可将现有的检索站点分为两大类：检索工具站点和检索服 第1 4 页 国防科学技术大学研究生院学位论文 务站点。 一、检索工具站点 拥有自己的搜索引擎、r o b o t 、索引数据库，按照自己的目的和遍历策略与 索引算法建立w w w 信息索引库，向用户提供基于自身索引库的查询服务。根据 浏览方式、索引技术、查询语言、查询匹配算法等又可将搜索根