（计算机系统结构专业论文）信息检索中的排序与相关度计算研究.pdf

山东大学硕士学位论文 摘要 随着社会信息化进程的不断发展，人们对信息的需求和依赖程度越来越高， 如何从海量信息中快速有效的获取有用信息，已经成为人们研究的焦点。信息检 索的研究可以帮助人们有效的找到感兴趣的信息，帮助用户发现对自己有用的知 识。 信息检索的核心问题就是预测文档的相关度，并按照其相关度对文档进行排 序，般而言，排在最顶端的文档被认为最相关。因此，相关性的计算和排序算 法就成为信息检索的核心。传统的信息检索主要采用向量空间模型计算相关度， 该模型也多用于w e b 信息检索。但w e b 网页与普通文档相比，有很多独特的特征， 如单个w e b 网页具有u r l 、h t m lt a g 、a n c h o rt e x t 、入度：同时w e b 网页之间具 有超链接，分析这种超链接关系，可以改进检索结果的排序效果。而d e e pw e b 是 一种特殊的w e b 资源，其信息存储在数据库中，用户只能通过一些含表单的网页对 其访问，但是这些网页中所含内容较少，网页之间链接关系较少，若采用一般的 w e b 检索相关度计算方法，会得到很差的效果。 本文的研究主要着眼于w e b 和d e e pw e b 信息检索领域，有以下几个方面的贡 献： 1 实现了一个基于向量空间模型的全文检索系统，对如何利用w e b 网页的 h t m l 标签、锚文本、入度特征来改进相关度计算进行了研究。并针对w e b 网页 的u r l 特征，给出了对检索结果重排序的方法。该系统在国内文本检索会议( s e w m 2 0 0 7 ) 中表现较好，取得了一定的成绩。 2 针对w e b 网页之间的链接特征，提出了一种面向主题的页面重要度计算方 法，新算法基于p a g e r a n k 超链接分析算法，考虑了网页内容与主题的相关度、主 题信息对网页间链接的分类和w e b 页面自身重要度等因素对网页重要度计算的影 响。实验证明针对具体领域，该算法在p l o 和用户满意度等方面优于p a g e r a n k 算法。 3 给出了计算d e e pw e b 数据库之间语义相关度的两种算法。第一个算法基于 向量空间模型，但在计算数据库表之间的语义相关度时，综合考虑了含有数据库 表的网页内容和数据库表之间的语义距离。且利用模糊分层集合，把同义和近义 山东大学硕士学位论文 的标记词进行归一，依据新的词频计算方法产生对数据库表的向量表示。第二个 算法采用本体和模糊集理论，将向量表示的数据库表转化为概念模糊集的形式， 利用模糊集的匹配度来计算数据库表之间的语义相关度。分别采用分类算法和聚 类算法来检验两种算法的效果。实验表明，两种新的语义相关度算法比余弦相似 度算法表现好。 关键词：相关度计算；链接分析；排序；语义相关度；匹配度 l i 山东大学硕士学位论文 竺! ! = ! ! ! ! = ! ! ! ! = = = ! i = = = i ! ! ! ! ! ! ! ! ! ! = ! ! ! ! ! ! ! ! ! ! ! ! ! ! = ! ! = a b s t r a c t 晰t 1 1t h ec o n t i n u o u sd e v e l o p m e n to fs o c i a li n f o r m a t i z i n gc o u r s e ，t h ei n f o r m a t i o n n e e d so fp e o p l ea r ei n c r e a s i n g h o wt oa c c e s su s e f u li n f o r m a t i o nf a s ta n de f f i c i e n t l yh a s b e c o m ef o c u so fp e o p l e 1 1 1 er e s e a r c ho ni n f o r m a t i o nr e t r i e v a lc a l lh e l pp e o p l ef i n d i n t e r e s t i n gi n f o r m a t i o ne f f e c t i v e l y ，a n dh e l pt h e mg e tu s e f u lk n o w l e d g e t h ec o r ei s s u eo fi n f o r m a t i o nr e t r i e v a li st h ep r e d i c t i o no ft h er e l e v a n c eo f d o c u m e n t s ，a n dt h er a n k i n go fd o c u m e n t sa c c o r d i n gt ot h e i rr e l e v a n c e i ng e n e r a l ，t h e o n eo nt h et o pi sc o n s i d e r e dt h em o s tr e l e v a n t t h e r e f o r e t h ec a l c u l a t i o no fr e l e v a n c e a n dr a n k i n ga l g o r i t h mh a sb e c o m et h em a i ni s s u eo fi n f o r m a t i o nr e t r i e v a l t r a d i t i o n a l i n f o r m a t i o nr e t r i e v a lm a i n l yu s e dv e c t o rs p a c em o d e l 。w h i c hi sa l s ou s e di n 溉6 i n f o r m a t i o nr e t r i e v a l ，t oc a l c u l a t et h er e l e v a n c e b u tc o m p a r e dt oo r d i n a r yd o c u m e n t s ， w e bp a g e sh a v el o t so fu n i q u ef e a t u r e s ，s u c ha su r l ，h t m lt a g ，a n c h o rt e x t , i nd e g r e e m e a n w h i l e ，t h e r e r eh y p e r l i n k sb e t w e e nw e bp a g e s ，a n a l y z i n gt h el i n k sc a ni m p r o v et h e r a n k i n go fs e a r c hr e s u l t s 1 h ed e e pw e b i sas p e c i a lk i n do fw e br e s o u r c e s ，w h o s e i n f o r m a t i o ni ss t o r e di nd a t a b a s e s ，u s e r sc a l lv i s i tt h e s ed a t a b a s e sj u s tt h r o u g hs o m e p a g e sw i t h d a t a b a s ef o r m s ，b u tt h et e x tc o n t e n ti nt h e s ep a g e si sl e s s ，a n dt h el i n k s b e t w e e nt h ep a g e sa r ef e w e r ，i fw es t i l lu s er e l e v a n c em e t h o df o rg e n e r a lw e bp a g e s ， w ew i l lg e tv e r yp o o rr e s u l t s 1 1 1 i sp a p e rf o c u s e dp r i m a r i l yo nw - e ba n dd e e pw e bi n f o r m a t i o nr e t r i e v a lf i e l d , f o c u s e do nt h e s ef o l l o w i n ga s p e c t s ： 1 w 色b u i l taf 试l - t e x tr e t r i e v a ls y s t e m , b a s e do nv e c t o rs p a c em o d e l w et e s t e d h o wt ou s eh n 皿。t a g ，a n c h o rt e x t , i n - d e g r e ef e a t u r e st oi m p r o v et h e c a l c u l a t i o no fr e l e v a n c eo nt h i ss y s t e m a n dw ea n a l y z e dt h eu r lf e a t u r eo f w e bp a g e s ，d e v e l o p e dar e r a n k i n gm e t h o do fs e a r c h r e s u l t s t h es y s t e m p e r f o r m e dw e l li ns e w m 2 0 0 7 2 f o rt h ef e a t u r eo fl i n k sb e t w e e nw e bp a g e s ，at o p i co r i e n t e dp a g er a n k a l g o r i t h mi sp r o p o s e d t h en e wa l g o r i t h mt a k e st h ef o l l o w i n gf a c t o r si n t o a c c o u n t , i e t h er e l a t i v i t yb e t w e e nt h ec o n t e n to faw e bp a g ea n dt h et o p i c ，t h e c l a s s i f i c a t i o no ft h el i n k so fw e bp a g e sb a s e do nt o p i c s ，a n dt h ei m p o r t a n c eo f t h ew e b p a g e st h e m s e l v e s e x p e r i m e n t ss h o wt h a tf o rt w og i v e nt o p i c st h en e w a l g o r i t h mi sb e t t e rt h a np a g e r a n ka l g o r i t h mi nt e r m so fp i oa n du s e r s a c c 印t a n c e i i i 山东大学硕士学位论文 3 t w om e t h o d so fc a l c u l a t i n gs e m a n t i cr e l e v a n c eb e t w e e nd e e pw e bd a t a b a s e s a r ep r o p o s e d 1 1 l el 札m e t h o di sb a s e do i lv e c t o rs p a c em o d e l ，b u tt h es e m a n t i c d i s t a n c eb e t w e e nt w od m a b a s o sa r ec a l c u l a t e db a s e do nb o t ht h ed i s t a n c e s b e t w e e nt h ec o n t e n tt e x t so ft h eh t p a g e sa n dt h e d i s t a n c eb e t w e e n d a t a b a s ef o r m se m b e d d e di nt h ep a g e s h i e r a r c h i c a lf u z z ys e t sa r eu s e d , a n da n u n i f i c a t i o np r o c e s s i n gf o rd a t a b a s ea t t r i b u t e si sp r o p o s e d , t h ep r o c e s s i n gi st o l e tt h ea t t r i b u t el a b e l st h a ta r oc l o s e ds e m a n t i c a l l yb er e p l a c e dw i t hd e l e g a t e s 1 1 1 e2 们m e t h o di sb a s e do nt h e o r yo fo n t o l o g ya n df u z z ys e t s ，t h ed a t a b a s e f o r m sa r et r a n s l a t e df r o mv e c t o r st oc o n c e p tf u z z ys o t sa n dt h es i m i l a r i t y b e t w e e nd a t a b a s e sa r ec a l c u l a t e db yn e c e s s i t yd e g r e eo fm a t c h i n gb e t w e e n f u z z ys e t s c a t e g o r i z i n ga n dc l u s t e r i n ga l g o r i t h mi su s e dr e s p e c t i v e l yt ot e s tt h e n e wm e t h o d s e x p e r i m e n t ss h o wt h a tt h et w on e ws e m a n t i cm e t h o d sp e r f o r m b e t t e rt h a nt r a d i t i o n a lo n e s k e yw o r d s ：r e l e v a n c ec a l c u l a t i o n ；l i n ka n a l y s i s ； r a n k i n g ； s e m a n t i c s i m i l a r i t y ；d e g r e eo fm a t c h i n g i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： ：a 邀：= e t 期：聊吕、歹 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：a 3 美导师签名 山东大学硕士学位论文 第一章绪论 1 1 研究背景及意义 在信息数字化的今天，当用户有了获取特定信息的需求时，首先想到的是信 息检索。用户把他的需要用查询词的形式表达出来，检索系统根据查询词返回可 能的相关文档。最初的信息检索系统是图书馆中的文献检索系统，这些检索系统 大都采用了基于文本内容的关键字匹配技术。这样的检索系统在文本规模较小时 还能较好的完成用户的检索需求，少量与检索不相关的文档不会对用户阅读检索 结果造成太大的影响，但是w e b 的出现改变了这一切。 互联网上信息的急剧膨胀，为用户提供海量信息的同时，也带来了大量的噪 声，用户已经无法忍受大量的无关信息淹没了自己所需要的信息，而且w e b 用户一 般只关注靠前的结果，因此，提高信息检索系统对检索w e b 数据的准确率，改进检 索结果的排序算法，使得用户可以尽早看到与自己相关的信息势在必行。 随着w e b 相关技术的日益成熟和w e b 数据库所蕴含信息量的快速增长，通过 对w e b 数据库的访问逐渐成为获取信息的主要手段，这便引发了对d e e pw e b 的 研究。但w 曲数据库内容较难获得，一般通过含表单的网页对其进行访问。而这 些网页中表的属性标记词数量比较少，且由于数据库系统是面向不同的用户和独 立实现的，即使是相似的数据库，表的属性标记词可能完全不同。当把语义相同 的词作为不同的词处理时，会严重地影响d e e pw - e b 数据库表网页检索的准确性。 因此，研究数据库表标记词的语义，改进相关度计算，具有十分重要的意义。 1 2 相关研究及发展 w 曲信息检索，是在传统信息检索理论上发展起来的，但是根据w e b 页面的 特征，具有独特的文本相关度计算方法，很多研究 1 3 】指出锚文本在w e b 信息检 索中起到重大的作用。张敏【4 】等人提出对w e b 文档信息特征进行分析，提出w e b 文档主特征词、主特征域和主特征空间的概念，在该空间上使用文档频度d f 5 】 ( d o c u m e n tf r e q u e n c y ) 信息而非传统意义上的m f 5 】( i n v e r s ed o c u m e n tf r e q u e n c y ) 信 息进行权值计算，并给出一个改进的相似度计算模型。 除了上述文本特征外，w e b 页面之间具有链接特性，利用这种特征的典型的 山东大学硕士学位论文 便有p a g e r a n k 6 、h i t s 7 、s a l s a s l 等算法，这些算法引入了网页权威值的概 念，将该值和文本相似度结合，对网页进行排序。这些算法在出现之初，极大的 改进了检索效果。但随着面向主题的w e b 检索逐渐流行，它们显现了一个极大的 弱点，即：很容易出现主题漂移。即具有较高权威值的页面是体现的一种普遍权 威值，在给定主题上的权威值却并不一定高。h a v e l i w a l a 提出t o p i c s e n s i t i v e p a g e r a n k 9 算法，利用了o d p 1 0 这种目录知识，但是只是一种粗粒度的文本和 链接信息的结合。r i c h a r d s o n 11 1 等人将链接和内容信息结合，对原始的p a g e r a n k 进行改进，在传递页面权威值时考虑了页面和查询间的主题相关性，使得和查询 相关度大的链出页面传递的权威值多些。这些方法都是在原有的算法上引入了文 本相关度计算，使得和主题相关度较大的得到较大的页面权威值，但是普遍性均 不是很好。c a i d e n g 等人将网页的粒度降低，采用v i p s 1 2 算法将网页分割成许多 语义独立的块，并提出基于块的链接评价算法 1 3 1 ，但是每块的重要度只是通过其 布局位置来衡量，并没有考虑文本内容。秦拯等人提出基于分块的p a g e r a n k 算法 【1 4 】，采用h t m ld o m 树将网页分块，且结合了文本相关性的考虑，但是相关性是 以块和词语的相似性来衡量，只用于信息采集的过程。 随着w 曲相关技术的日益成熟和w 曲数据库所蕴含信息量的快速增长，通过 对w e b 数据库的访问逐渐成为获取信息的主要手段，这又引出了d e e pw e b 的研 究。目前的研究主要集中在对d e e pw e b 数据库的检索和对d e e pw e b 数据库的组 织 1 5 ，1 6 】。对前者的研究主要集中在元搜索引擎设计 1 7 - 1 9 和面向d e e pw e b 的 网路爬虫的设计与实现 2 0 1 ：而对后者的研究则主要是对搜索到的d e e pw e b 数据 库资源信息进行分类或聚类【2 1 2 3 】。对d e e pw e b 数据库进行分类或聚类需要考虑 数据库之间相关度的计算。文献【2 l 】核心思想是把包含数据库表的网页中的文本信 息作为数据库内容的上下文。然而，文献 2 1 l o p 对网页和表的处理过于简单，只是 把表的标记和h t m l 的全部词变成文本，然后利用信息检索技术中的词频分析法 ( t f i d f ) 5 ，把表的标记和h t m l 的全部词的文本用向量表示，然后采用k m e a n s 算法进行聚类。这样存在的问题是，当网页中含有噪音信息，如公告、导航、修 饰、版权等，会严重地影响聚类的效果。另外，该方法对数据库的属性标记词缺 乏语义分析。 2 山东大学硕士学位论文 1 3 本文的工作 对w e b 检索的研究需建立在一个现有的文本检索系统上。在第三章，给出了一 个基于向量空间模型的全文检索系统的实现。我们在本系统上，对如何利用w e b 网页的h t m lt a g 、a n c h o rt e x t 、入度特征来改进相关度计算进行了研究。并针对 w e b 网页的u r l 特征，给出了对检索结果重排序的方法。该系统在国内文本检索会 议( s e w m 2 0 0 7w e bt r a c k 2 4 ) q b 表现较好，取得了一定的成绩。 p a g e r a n k 算法利用网页链接关系评价网页重要度，它用于g o o g l e 搜索引擎中， 在w e b 检索的排序上有很好的表现。但针对某一具体领域或主题的检索，该算法 很容易出现主题漂移。因此，在第四章中提出了一种面向主题的页面重要度计算 方法，新算法基于p a g e r a n k 超链接分析算法，考虑了网页内容与主题的相关度、 主题信息对网页间链接的分类和w e b 页面自身重要度等因素对网页重要度计算的 影响。实验表明，该算法比p a g e r a n k 算法在面向主题的排序方面有较好表现。 d e e pw e b 是指w e b 上的数据库资源，一般可以通过数据库表对其进行访问， 但数据库表中的标记词的数量比较少，当把语义相同的词作为不同的词处理时， 会严重地影响d e e pw e b 数据库表网页检索的准确性。因此，在第五章给出了计算 d e e pw e b 数据库的语义相关度的两种方法，前者利用模糊分层集合，把同义和近 义的标记词进行归一，依据新的词频计算方法产生对数据库表的向量表示。后者 采用本体和模糊集理论，将数据库表的表示方式从词语向量转化为概念的模糊集， 从而用模糊集的匹配度计算语义相关度。实验表明，两种语义相关度计算方法比 传统方法分别在分类、聚类上有较好表现。 1 4 本文的组织 全文共分六章，第一章说明了研究的背景和意义，相关的研究和发展，以及 本文的内容和组织。第二章叙述了信息检索的基本概念，阐述了向量空间模型的 相关度计算方法，并给出了分类、聚类、w e b 信息检索和d e e pw e b 信息检索的概 念。第三章阐述了我们参加国内文本检索会议w e bt r a c k 竞赛( s e w m2 0 0 7 ) 的经验 总结。第四章提出了一种面向主题的页面重要度计算方法。第五章给出了计算d e e p w e b 数据库的语义相关度的两种方法。第六章对本文的工作进行总结。 山东大学硕士学位论文 2 1 引言 第二章信息检索 信息检索( i n f o r m a t i o nr e t r i e v a l ) 这个术语产生于c a l v i nm o o e r s1 9 8 4 年在 m i t 的硕士论文。i n f o r m a t i o nr e t r i e v a l ( i r ) ：简单地说是从文档集合中返回满足用 户需求的相关信息的过程。作为- f 学科，是研究信息的获取( a c q u i s i t i o n ) 、表示 ( r e p r e s e n t a t i o n ) 、存储( s t o r a g e ) 、组织( o r g a n i z a t i o n ) 和访问( a c c e s s ) 的- f 学问。从本质上讲，信息检索是把信息按照一定的方式组织和存储起来，并能根 据用户的信息需要找出其中相关信息的过程。 本章主要介绍信息检索的基本概念，包括信息检索的基本原理、模型、评价 指标等，并对w e b 与d e e pw e b 信息检索做一个简单的介绍。 2 2 信息检索的基本原理 现实生活中，虽然人们获取信息的方式和途径各式各样，使用的设施或者工 具千差万别，但是处理过程的基本原理是相同的，都是用户需求与信息集合按照 一定的准则进行选择和匹配的结果，如图2 1 所示。 图2 - 1 信息检索的基本原理 1 信息资源及信息集合 信息资源的概念可以从广义和狭义两个方同上理解。广义的信息资源是信息 活动中各种要素的总称，既包含信息本身，也包含与信息相关的人员、设备、技 术和资金等；狭义的信息资源只限于信息本身。 现实世界中已产生和积累的信息资源的数量是非常庞大的，必须经过筛选、 组织、加工才能形成供用户访问和检索的对象，即信息集合。信息集合的获取和 形成是进行各种信息处理的前提和基础。 2 用户需求及需求集合 用户的信息需求是用户的一种心理活动或反映，它是一个取决于各种主、客 4 山东大学硕士学位论文 观因素的动态量值。主观因素是指用户的文化背景、工作能力、个人习惯等方面 的差异，客观因素则来源于用户的工作领域和社会职能。用户的信息需求可以分 成四个层次【2 5 】： 1 ) 真实需求：这是用户需求的最原始状态，在这种状态下，用户往往不能完 全确定自己需要何种信息以及通过何种途径来获得信息。 2 ) 感知信息：用户通过调动自己的主观积极性，对面临问题的认识进行深入 了解。 3 ) 请求：用户以口头或书面语言的形式将自己的信息需求明确表达出来。 4 ) 提问：用户进入某信息检索系统进行具体的查询操作，把已经用自然语言 表达出的信息请求转化成符合检索系统语法要求的提问式。 从这种层次划分可以看出，信息检索过程中处理的需求集合是用户明确表达 出来的并经过形式化的信息提问，与用户的真实需求、感知需求和请求可能存在 一定的差异。 3 选择与匹配 面对信息集合与需求集合，要在二者之间建立起联系和沟通的桥梁，就需要 提供某种选择与匹配机制。这种机制的主要功能在于：能够把信息集合与需求集 合依据某种相关性指标进行比较和判断，进而选择出符合用户需要的信息。 2 3 信息检索模型 从2 2 节可知，用户通过查询阐明自己的信息需求，信息系统则检索与用户查 询最为匹配( 接近) 的文档。另外，信息系统还可能借助某种相关性指标对检出 的文档进行排序。这一排序作业在用户信息需求的满足过程中至关重要，是信息 检索建模的主要目标【2 6 】。因此，本小节将对信息检索模型进行介绍。 定义2 - l ：信息检索模型是一个四元组 d ，q ，础( g f ，d j ) ) 5 】，其中 1 ) d 是文档集中的一组文档逻辑视图( 表示) ，称为文档表示； 2 ) q 是一组用户信息需求的逻辑视图( 表示) ，称为查询； 3 ) f 是一种机制，用于构建文档表示、查询及它们之间关系的模型； 4 ) r ( q p d ，) 是排序函数，该函数输出一个与查询q ，o 和文档表示d i d 有 关的实数，这样就在文档之间根据查询g ，定义了一个顺序。 山东大学硕士学位论文 下面就几个基本概念做一下详细说明： 文档( d o c u m e n t ) ：信息检索系统检索的对象。在信息检索领域，文档往往是 无结构的，是自然语言生成的蚊子。在w e b 信息检索中，文档指的是w e b 上的页 面( p a g e ) ，而页面往往是具有一定的结构的。 查询( q u e r y ) ：信息检索系统据以检索的对象。查询由用户生成，往往也是 自然语言描述的用户信息需求。除了布尔模型之外的其他检索模型，往往把查询 也看成一个文档，检索的过程就是找到与查询文档最相关文档的过程。 数据集( c o l l e c t i o n ) ：一定数目文档的集合，也称为知识库( r e p o s i t o r y ) 、语 料库( c o r p u s ) 。数据集对信息检索有特别的意义，检索必须在一个有限的集合内 进行，同时标准的数据集( 如c w t 数据集 2 4 】) 可以对不同的检索算法进行比较、 评测。 标引词( t e r m ) 也称为项、标记词、索引项( i n d e xt e r m ) 或特征项。当文 档或查询的内容被简单地看作是由它所包含的基本语言单位( 字、词、短语等) 构成的集合时，这些基本语言单位统称为标引词。可以为标引词设定权值( w e i g h t ) ， 该值描述了标引词与文档或查询的相关程度。 相关度( r e l e v a n c e ) ：文档与查询相关程度的性质。相关性是文档满足用户需 求的性质。信息检索系统的主要目标就是检索出所有与用户查询相关的文档。 排序( r a n k i n g ) 检索结果往往是一个文档的列表，对大部分检索模型而言， 这个列表是经过相关度排序的，相关度高的文档排在前面，最先呈现给用户。 信息检索的核心问题就是预测哪些文档相关，哪些文档不相关 5 】。给定查询 q ，信息检索系统从文档集合c 中计算每篇文档d 与q 的相关度并排序( r a n k i n g ) 。 因此，相关性的概念和排序算法就成为信息检索的核心。 相关性的计算方法因采用的信息检索模型而异，而信息检索模型有多种。应 用较为广泛的有布尔模型、概率模型和向量空间模型。本节简要介绍前两者，着 重介绍向量空间模型。 1 布尔模型 布尔模型采用布尔代数和集合论的方法，用布尔表达式表示用户提问，通过 对文档表示和查询的逻辑运算来检索文档。常用的布尔逻辑匹配运算符有：逻辑 与( 刎v d ) 、逻辑或( 锨) 、逻辑非( d r ) 。在该模型中，标引词的状态只有两种 6 山东大学硕士学位论文 情况：存在和不存在。假设用w 表示标引词的权值，如果标引词存在，它的值就 为“l ”，否则值为“0 ”，即w o ，1 ) 。 用户查询q 都可以表示成一个标引词的布尔表达式。例如，对于一个表示为 q = i io rf ，1 2a n d 厶夕的查询式，如果文档中含有标引词 ，或者同时含有标引词如 和厶，该文档即为和查询相关。 布尔模型简单且容易理解，可以处理结构化查询。然而由于它所采用的标准 匹配策略过于僵硬，构造一个好的布尔表达式比较困难。另外，由于标引词的状 态只有两种情况，无法反映项在文档中出现的频率，不能实现区别对待每篇文档。 再者，检索输出完全依赖于布尔表达式与文档的匹配情况，输出量较难控制，容 易造成零输出或输出过多。为了克服上述缺陷，人们对传统的布尔模型进行改进 和扩展，建立了一些新的模型。 2 概率模型 概率模型试图在概率的框架下解决信息检索的问题，其基本思想是：给定一 个用户查询，存在一个文档集合，该集合只包含完全相关的文档而不包括其他不 相关的文档，这个文档集合被称为理想结果集。根据结果集中文档与查询的相关 概率来排序输出。 概率模型的主要优点在于：从理论上讲，文档根据它们相关的概率按递减的 顺序排列。而缺点在于，需要最初把文档分成相关的集合和不相关的集合：该方 法不考虑标引词在文档中出现的频率，即同布尔模型一样，所有的权值都是二元 的。 3 向量空间模型 向量空间模型最重要的贡献是把文档用向量来表示，使得文档本身可以直接 参与运算。向量的每一维可以是词、短语，也可以是n g r a m 或者是一个概念，统 称为标引词。 1 ) 向量表示形式 为了将文档划分成向量中的标引词，一般需要采取以下步骤： 分词：英语等西方语言中，词与词之间有空格作为分隔符。但是，中文等语 言必须有这一步骤。多采用基于词典的方式，对文档进行分词，匹配时有正向匹 配、逆向匹配等形式【2 6 】。分词的质量决定了检索的质量。 7 山东大学硕士学位论文 去停用词：有些词出现频率很高，几乎会在所有文档中反复出现，如，汉语 中的助词“的”“地”“得”，这些词不会对检索有积极的帮助，反而会占用大量的 索引空间。在文档处理时应把这些词去掉。 处理词干：英语等西方语言，有很多时态、词性、单复数的变化，一个词可 以衍生出很多新词，这些词往往具有类似的含义。将这些衍生词还原到词干，可 以减少索引的大小。 经过如上处理，每篇文档可以变成向量形式，每个标引词就是向量的个维 度，而所有的标引词组成了所有文档可能的向量空间，每个文档就是这个空间内 的一个向量。 例如，文档集合中的第f 篇文档用d f _ 亿，厶，纠表示，其中，乃，厶，厶为系 统中所有标引词集合：查询集合中的第个查询用9 = m ，厶，圳表示；h 表示文 档向量或查询向量中的第k 个分量，即文档表示或查询式中所含的第k 个项或标引 词、索引项。标引词厶常常被赋予一个数值w 膏，表示它在文档中的重要程度，称 为标引词厶的权值，取值大多在【o ，1 1x e f 日q 。 2 ) 词的权重 词与文档的相关程度体现了词的重要程度，很明显，不同的词重要性是不同 的。与标引词的重要性相关的两个因素是频率t f ( t e r mf r e q u e n c y ) 和反文档频率i a f ( i n v e r s ed o c u m e n tf r e q u e n c y ) 。 去除停用词之后，一般而言，在文档中出现频率高的索引词，显然与文档主 题更相关。因此，标引词的文档频率，简称历是一个重要的衡量因素。 但是，仅仅采用矿来估算权值过于片面。有些索引词出现在不同的主题中， 而有些词索引仅在特定主题的文档中出现，出现在较少文档中的索引词显然拥有 更显著的区分能力。因此，s a l t o n 提出彬的概念： i d 弧= l 0 9 2 ( n n o ( 2 - 1 ) 其中，是文档总数，刀是标引词k 在其中出现的文档数，称为标引词的文档频率。 谚表示了一个索引词在整个文档集中的分布情况，而矿表示了一个索引词在一 篇文档中的分布情况，两者结合起来可以完整的表示索引词在文档中的区分能力， 也即重要程度： w 庐靠死娠 ( 2 - 2 ) 8 山东大学硕士学位论文 其中，吮表示标引词瑶在文档d ，中的频率，协表示t k 的反文档频率。此外， 文档的长度因素也必须考虑，否则文档越长，越容易被检索到。可以按下述规范 化公式得以解决。 w 啦2 面矿丽k x i d f k ( 2 - 3 ) 3 ) 相似度计算 根据上文的讨论，d l - m ，如，驯可以表示成历= 一j ，w 2 , ，w j ，；) ，这样形成一个 向量空间，文档间的相似度可以借助于向量间的某种距离来计算，通常采用向量 之间的内积或夹角余弦。设d l = w 1 2 , ，w ，伤= 拍w 2 2 ，w 2 , 0 ，则 内积公式： s i m ( d l ，d g = e w 。w ：。 ( 2 - 4 ) 己w l k w 2 k 夹角余弦公式： s i m ( d ，驯= s 目= 1 尘生一 ( 2 - 5 ) j e w ：, 2 在实际系统中，一般多采用两个向量之间夹角的余弦值来计算相似度。文档 与查询的匹配过程也以同样方式计算。当全部文档向量与某个查询向量的相似度 都计算完毕后，系统就把相似度超过一定阈值的文档( 或者根据预定要检出的文 档数量) 按相似度大小降序排列输出。因此，排在最前面的文档从理论上讲是和 查询最相关的文档。 与布尔模型相比，向量模型有以下几个特色： 1 ) 标引词加权，标引词的权值可以在【0 ，1 】闭区间中取值，改进了检索效果； 2 ) 采用余弦公式计算相似度，可以从量的角度判断文档命中与否，从而使检 索结果更加合理。 3 ) 检索结果可按与查询的相关度排序输出。 但向量模型存在不足：标引词被认为彼此之间相互独立，但是在现实中，很 多词语如：“电脑”“计算机”之间存在语义相关性，将其认为独立对检索效果会 造成不利的影响。但此模型简单，对于一般集合，该模型检索效果较好，常用在 目前的网络资源检索系统中，如搜索引擎。 9 山东大学硕士学位论文 2 4 信息检索应用 信息检索可以用于很多具体的领域，本小节将介绍分类、聚类、w e b 检索、 d e e pw e b 检索的概念，并给出较为经典的k n n 分类【2 7 】和k m e f l l l s 聚类【2 7 】算法 的描述。 2 4 1 分类与聚类 信息检索系统的文本信息库可能是相当庞大的，同时用来表示文本内容的词 汇数量又是成千上万的。文本分类系统可以对文本集进行有序的组织，把相似的、 相关的文本组织在一起。它作为知识的组织工具，为信息检索提供了更高效的搜 索策略和更准确的查询结果。 文本分类是指在分析文本内容的基础上( 一般被转化为向量形式) ，按一定的 策略，把文本归入一个或者多个合适的类别的应用技术。根据是否有固定的类别 体系可以分为有监督( s u p e r v i s e d ) 的分类( 也成为自动分类) 和无监督( u n s u p e r v i s e d ) 的分类( 也称为自动聚类) 。 文本分类中一般按照文档之间的相似度，对文档进行归类。对应不同性质的 数据，人们给出了不同的相似性度量标准。主要有以下两类函数：相似系数【2 7 】 ( 如夹角余弦函数) ，及距离函数 2 7 】( 如欧几里德距离) 。 1 自动分类 自动分类是先抽取待分类文本的特征，将其与各类别中文本所具有的共同特 征或一定的分类标准、分类参数进行比较，然后将待分类文本划归为特征相近的 类，并赋予相应的分类号。它一般分为训练和测试两个阶段，训练阶段所用到的 文本集合由属于预先定义好类别体系的文本组成，分类系统先通过训练文本集学 习分类知识，然后在测试阶段根据所学的知识为待分类的文本确定一个或多个合 适的类别。 文本被转化为向量形式，经过特征提取之后，便可以进行自动分类，也称特 征匹配。常用的分类算法有：最近邻分类，朴素贝叶斯分类，决策树，支持向量 机分类等。下面主要介绍最近邻分类。 最近邻分类( n e a r e s tn e i g h b o r ) ：近邻算法存在很多变种，但其一般思路是， 首先存储全部或部分训练文档，对于测试文档，通过相似性函数计算它与所存储 的训练文档的距离以决定类别的归属。也就是说，近邻学习算法在训练过程中并 1 0 山东大学硕士学位论文 不产生类的描述。k n n 是近邻学习算法的一个例子，采用k n n 方法进行文档分 类的过程如下： 对于某一给定的测试文档d ，在训练文档集中，通过相似度找到与之最相似的 k 个训练文档。在此基础上，给每一个文档类别打分，分值为k 个训练文档中属于 该类的文档与测试文档之间的相似度之和。也就是说，如果在这k 个训练中，有 多个文档同属于一个类，则该类的分值为这些文档与测试文档之间的相似度之和。 对每个文档类别的分值统计完毕之后，按分值进行排序。还应当选定一个阈值， 只有分值超过闽值的类别才予以考虑。若为单类问题，测试文档属于超过阈值的 分值最高的类。若为多类分类问题，则属于超过阈值的多个类。k n n 的决策规则 可以形式化表示为： s c o r e ( d ，q ) = s i m ( d ，a j ) y ( a ，c i ) 一6 l ( 2 6 ) d i 烈n 其中，y ( j ，c t ) o ，1 ) ：如果文档弓属于类别白，则y ( d j ，q ) = l ，否i , jy ( a j ，c f ) = 0 。 s i m ( d ，d j ) 为测试文档d 与训练文档巧之间的相似度，b ，为阈值。对于某一特定类 来说，b i 是一个有待优化选择的值，一般可以通过一个验证文档集来进行调整。 k n n 分类算法的优点是易于快速实现，分类效果好。但也存在一些限制：首 先，需要存储训练集中全部文档，如果训练集较大，分类器的分类速度可能太慢 且不实用。其次，相似性计算的问题，一般采用余弦公式计算相似度，但有时向 量中含有一些无关属性，使得相似度计算不准确。 2 自动聚类 自动聚类首先从文本中抽取有关特征，再根据一定的法则将具有相同或相近 特征的文本定义为一类，划分出的类别是不确定的，要求同一类内文本内容的相 似度尽可能大，而不同类间的相似度尽可能地小。 聚类分析是基于这样一个认识：每一类别对象之间较为相似，而类间对象之 间应该具有较大差异。聚类算法主要可以划分为 2 7 1 ：层次法、划分法、基于密度 法、基于网格法和基于模型法等。k m e a n s 方法属于划分法的一种，主要思想是， 对一个有n 个对象的数据集，构造k 个分组，每个分组代表一个类。指定k ，首先 给出一种初始的分组方法，然后通过反复迭代来改变分组，使每一次改进之后的 分组方案都比前次的好。 山东大学硕士学位论文 k - m e a l l s 聚类算法的步骤为： ( 1 ) 随机选择k 个对象，每个对象初始地代表了一个分组的聚类中心( 质心) 。 ( 2 ) 对剩余的每个对象，计算它和每个分组质心的距离，将它赋给最近的类。 ( 3 ) 重新计算每个类中对象的平均值，用对象的均值点作为新的质心。 ( 4 ) 重复执行步骤2 3 ，直到准则函数收敛。 一般采用误差平方和准则函数作为目标函数，最佳聚类结果对应于