（计算机应用技术专业论文）搜索引擎中自动分类关键技术研究.pdf

摘要 摘要 搜索引擎是网络信息检索的重要工具，但现有搜索引擎检索到的结果 太多，用户很难找到真正想要的资料。如何提高搜索引擎的查准率是其亟 待解决的问题。文本自动分类技术是自然语言处理的一个重要的应用领域， 是替代传统的繁杂人工分类方法的有效手段和必然趋势。将计算机文本自 动分类引入搜索引擎，可以有效地提高搜索引擎的检索精度，为用户提供 高质量、高相关度的查询结果。 首先，对向量空间模型的概念，涉及的相关技术进行了详细的介绍。 在透彻分析网页结构特点的基础上，结合网页的特性，对t f i d f 特征权重 计算公式进行了改进，体现了处于w e b 文本结构中不同位置的特征词对文 本类别的不同区别能力。 其次，对文本自动分类中的特征选择这一关键技术进行了研究。在对 特征选择步骤和常用特征选择算法进行分析的基础上，对互信息算法进行 了深入分析，考虑类别比例不同和负值情况下隐藏的影响较大的特征信息， 对其进行改进，使文本之间的相似度更为准确。 然后，对分类系统中的分类算法这一核心技术进行了深入研究。在介 绍现有的常用分类算法，并详细分析了k n n 算法实质的基础上，针对k n n 的不足，考虑合并对分类有相同贡献的词，及特征词的关联与共现等因素， 对其进行了改进。 最后，采用2 0测试集和 分类器，对上述研究技术n e w s g r o u p s l i b s v m 进行了实验及分析，并对今后的研究工作进行了展望。 关键字搜索引擎；文本自动分类；向量空间模型；特征选择；分类算法 燕山大学工学硕士学位论文 a b s t r a c t n 圮s e a r c he n g i n ei st h en e t w o r ki n f o r m a t i o nr e t r i e v a li m p o r t a n tt o o l , b u t t h ee x i s t i n gs e a r c he n g i n er e t r i e v e sr e s u rt o om a n y , i ti sv e r yd i f f i c u l tt of m dt h e m a t e r i a lw h ow a n t e dt r u l y h o wt oe r l h a n c et h ea c c u r a c yr a t i oo ft h es e a r c h e n g i n ei saq u e s t i o nw a i t e d t oh es o l v e du r g e n t l y a u t o m a t i ct e x tc l a s s i f i c a t i o ni s a ni m p o r t a n ta p p l i c a t i o nf i e l do fn a t u r a ll a n g u a g ep r o c e s s ，a ne f f i c i e n tm e a n s a n dn e c e s s a r yt r e n dt os u b s t i t u t et h et r o u b l e dt r a d i t i o n a lm a n u a lc l a s s i f i c a t i o n i n t r o d u c i n gt h ec o m p u t e ra u t o m a t i ct e x tc l a s s i f i c a t i o ni n t os e a r c he n g i n em a y e n h a n c ee f f e c t i v e l yt h er e t r i e v a lp r e c i s i o no ft h es e a r c he n g i n e ，p r o v i d eu s e r s h i g hg r a d ea n dh i g hd e g r e eo f c o r r e l a t i o ni n q u i r yr e s u r f i r s t l y ，t h ev e c t o rs p a c em o d e lc o n c e p ta n dt h er e l a t e dt e c h n o l o g ya r e i n t r o d u c e di nd e t a i l o nf o u n d a t i o no fa n a l y z i n gt h ew e bp a g ec h a r a c t e r i s t i c t h o r o u g h l y , a ni m p r o v e m e mt oc h a r a c t e r i s t i cw e i g h tf o r m u l at f i d ft h r o u g h u n i o nt h ew e bp a g ec o n s t r u c tc h a r a c t e r i s t i ci sm a d e ，i tm a n i f e s t st h ed i f f e r e n t a b i l i t yo ft h ed i f f e r e n tc h a r a c t e r i s t i c w o r d si nt h ew e bt e x tt ot h et e x t c l a s s i f i c a t i o n s e c o n d l y ，t h ef e a t u r es e l e c t i o na l g o r i t h mw h i c hi sa ne s s e n t i a lt e c h n o l o g y i nt h ea u t o m a t i ct e x tc l a s s i f i c a t i o ni sr e s e a r c h e d t h ef e a t u r es e l e c t i o ns t e p sa n d t h ec o m m o n l yu s e df e a t u r es e l e c t i o na l g o r i t h m sa l et a k e na na n a l y s i s o nt h i s f o u n d a t i o n , at h o r o u g ha n a l y s i so nt h em u t u a li n f o r m a t i o na l g o r i t h mi sc a r r i e d o n , t h e ni si m p r o v e dc o n s i d e r i n gt h ed i f f e r e n tc a t e g o r yp r o p o r t i o na n dt h e n e g a t i v ev a l u es i t u a t i o nw h i c hh i d e db i gi n f l u e n c et of e a t u r ei n f o r m a t i o n , i t m a k e st h es i m i l a r i t yt ob em o r ea c c u r a t eb e t w e e nt h et e x t s t h i r d l y , t h ec a t e g o r i z a t i o na l g o r i t h mw h i c h i st h ec o r ep a r tt ot h ea u t o m a t i c t e x tc a t e g o r i z a t i o ns y s t e mi sr e s e a r c h e dd e 印l y t ke x i s t i n gc o m m o n l yu s e d c a t e g o r i z a t i o na l g o r i t h m sa r ei n t r o d u c e d a n do n t h ef o u n d a t i o no f a n a l y z i n gt h e a b s t r a c t e s s e n c eo fk n e a r e s tn e i g h b o r , i nv i e wo fi t si n s u f f i c i e n c y , a l li m p r o v e m e n tt o t h ek - n e a r e s tn e 培h b o rc l a s s i f i c a t i o na l g o r i t h mi sm a d ec o n s i d e r i n gt h em e 唱e t h ew o r d sw h i c hh a v et h es a m ec o n t f i b u t i o nt 0t h ec l a s s i f i c m i o i la n dt h e c h a r a c t e r i s t i cw o r d sc o n n e c t i o nw i t ha l t o g e t h e rp r e s e m l ya n ds oo nt h ef a c t o r s f i n a l l y , t h ee x p e r i m e n tt ot h ea b o v er e s e a r c ht e c h n o l o g yi sc a r r i e do nu s i n g t h e2 0 _ n e w s g r o u p st e s tc o l l e c t i o na n dt h el i b s v ms y s t e m , a n dt h e nt h e e x p e r i m e n t a lr e s u l t sa r ea n a l y z e d a tl a s t ，t h ef o r e c a s tt ot h en e x tr e s e a r c hw o r k a r ec a r d e do i l k e y w o r d ss e a r c he n g i n e ；a u t o m a t i ct e x tc l a s s i f i c a t i o n ；v e c t o rs p a c em o d e l ； f e a t u r es e l e c t i o n ；c a t e g o r i z a t i o na l g o r i t h m 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于本体的个性化用户 模型研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行 研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人 已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集 体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字于q 队 日期：删, f f - i z , 92 7 日 燕山大学硕士学位论文使用授权书 基于本体的个性化用户模型研究系本人在燕山大学攻读硕士学位 期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所 有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全 了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山 大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全 部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密囤。 ( 请在以上相应方框内打“”) 作者签名：彳歙 日期：懈忙月研日 撕鹕：狰唧醐撇碉f 第1 章绪论 1 1 研究背景和意义 第1 章绪论 随着计算机的普及以及互联网w w w ( w o r l dw i d ew e b ) 的迅猛发展， 大量的信息以电子文档的形式出现在人们面前，人们已经进入了网络信息 时代。信息的发布与共享不再受到时空的限制，网络资源每年都在以指数 级的速度增长，信息资源变得极为丰富。w w w 自从1 9 9 1 年产生以来， 已经发展成为一个全球化的信息空间，为用户提供了一个前所未有的资源 共享和信息共享的平台【i 】。 然而，由于i n t e m e t 的开放性，与传统的信息资源相比，w e b 信息资 源具有以下显著的特点 2 , 3 1 。 ( 1 ) 动态性w e b 上的信息时刻都处于变化之中，新页面不断出现，旧 的页面也在不断更新和删除( 包括内容的改变、位置的移动等1 。 ( 2 ) 半结构化或无结构化w e b 上的信息通常是无组织的，没有关系数 据库中数据的结构化特性，或者是只有有限的结构特性，这使得信息的索 引变得很困难。 ( 3 ) 异构性信息分布在不同的平台上，站点结构各异，通过不同的协 议( 如t c p i p 、h t t p 等) 相互连接，信息结构形式也各不相同，多语种、 多类型的信息交织在一起，杂乱无序。 基于w e b 信息的这些特点，人们要在浩瀚的网络信息资源海洋中高效 准确地定位自己感兴趣的信息，找到符合自己需求的资源，就需要强有力 的信息检索系统来支持。搜索引擎( s e a r c he n g i n e ) 正是在这种情况下应运而 生的【4 j 。它以一定的策略在互联网中发现、搜集信息，对搜集来的信息进 行理解、提取、组织和处理，为用户提供检索服务，从而起到信息导航的 作用。搜索引擎的出现有效地缓解了人们在浩瀚的i n t e r n e t 信息海洋中获 取信息困难的问题。 燕山大学工学硕士学位论文 但随着搜索引擎的发展，他带来的问题也日益明显，现有搜索引擎的 检索技术己很难满足用户的要求，它最大的缺点是搜索到的结果太多，用 户面临着“信息过剩”和“信息迷向”问题，即用户很难找到真正想要的 资料。如何提高检索精度，为用户提供高质量、高相关度的查询结果，是 信息检索领域中重要的有待解决的问题。 目前的搜索引擎主要分为两大类：目录式的搜索引擎和关键字式的搜 索引擎 5 1 。前者如：y a h o o ! ，s o h u 等，它们主要是通过具有专业知识的编 辑人员对网页进行人工分类，因为加入了人的智能，这类搜索引擎搜索的 准确率是相当高的，而其不足之处也在于它用人工进行分类的机制，所以 维护量大、信息量少、信息更新不及时。显然分类目录式搜索引擎对文档 分类的自动化程度越高，信息整理所需要的人工劳动就越少，效率越高。 后者如：g o o g l e ，北大天网等，它们由一个称为蜘蛛( s p i d e r ) 的机器人程序 以某种策略自动地在互联网中搜集和发现信息，由索引器为搜集到的信息 建立索引，由检索器根据用户的查询输入检索索引库，并将查询结果进行 相关度排序返回给用户。这类系统索引的网页规模巨大，并且能够定期重 新收集网页，更新索引库的内容，向用户提供最新的w e b 网页信息，查全 率要比目录式搜索引擎高的多。但是，该类搜索引擎返回的结果虽然经过 了相关度排序，相关和不相关的文档仍然相互混杂，用户必须逐个浏览结 果列表以找到相关文档，花费了大量的精力，当返回的结果数目众多时， 这个问题更为突出。因此提高此类搜索引擎的查准率成为迫切需要解决的 问题之一。如果将网页按类分别建立相应的数据库1 6 “，可对分类数据库进 行查询，提高搜索引擎查准率，并且建立自动的分类信息资源，后面的相 关性排序将更客观，从而极大限度地保证搜索出的结果与用户的查询串相 一致。 因此，研究网页的自动分类就成为实现搜索引擎的一个很重要的环节。 1 2 当前研究概述 自动分类研究始于5 0 年代末，h p l u l m 在这一领域进行了开创性的 2 第1 章绪论 研究。1 9 6 0 年，m a r o n 在j o u r n a lo f a s m 上发表了有关自动分类的第一篇 论文o n r e l e v a n c e ，p r o b a b i l i s t i ci n d e x i n ga n di n f o r m a t i o nr e t r i e v a l 。1 9 6 2 年， 博科( h b o r k o ) 等人提出利用因子分析法进行文献的自动分类方法。其后， i c s p a r c k ，g s a k o n ，r m n e e d h a m ，m e l e s k 以及k s j o n e s 等众多学者 在这一领域进行了卓有成效的研究工作。概括起来，他们主要从文本的词 频统计分析、句法分析和语义分析等三个层次上进行研究。其中，以基于 词频统计分析的自动分类试验较为成功。自动聚类多限于理论上的探讨， 很少投入实际应用。 到目前，自动分类在国外经历了三个发展阶段：第一阶段( 1 9 5 8 - - 1 9 6 4 ) 主要进行自动分类的可行性研究，第二阶段( 1 9 6 5 - - 1 9 7 4 ) 进行自动分类的 实验研究，第三阶段( 1 9 7 5 一至今) 进入实用化阶段。我国的自动分类工作 始于8 0 年代初期，大体上经历了从可行性探讨辅助分类系统自动 分类系统三个发展阶段。 我国开展自动分类研究起步较晚。1 9 8 1 年，侯汉清对计算机在文献分 类工作中的应用作了探讨，并介绍了国外在计算机管理分类表、计算机自 动分类、计算机编制分类表等方面的概况。此后，我国陆续研究出一批计 算机辅助分类系统和自动分类系统。 进入9 0 年代以后，由于人工智能技术的不断成熟，研究者开始把专家 系统技术引入到自动分类领域。专家系统是一种在某特定领域以人类专家 的水平去解决该领域问题的计算机程序，一般由知识库和推理机两大基础 部分组成。知识库储存了从专家那儿获得的关于某领域的专门知识。推理 机具有推理的能力，即根据知识推导出结论，而不仅仅简单地搜索现成的 答案。正因为专家系统的这些特点，使其在自动分类领域具有良好的应用 前景。 信息检索领域中使用分类技术的系统有： n o r t h e m l i g h 信息检索系统和早期用于x e r o x - p a r c 的信息检索系统 s c a r e r 和g a t h e r ，这两个系统都是在用户查询信息前提前对文档进行分类。 前者是由图书管理专家提前将文档集进行分类，共分1 7 0 0 0 多个子类，后 者使用平面划分法对文档集进行分类。当用户查询信息时，系统首先对查 燕山大学工学硕士学位论文 询条件进行分析，然后以簇类的方式只返回与用户查询条件相关主题的文 档集合。 伍尔弗汉普顿网络图书馆w w l i b ( w o l v e r h a m p t o nw e bl i b r a r y ) 是使用 了自动分类技术的网络信息检索系统【1 0 1 。它提供的检索途径有关键词检 索、分类号检索、浏览类目下收录的网页等。w w l i b 也支持布尔逻辑检索 和截词检索。检索结果分为两行，第一行为分类号、网页标题，第二行是 网页内容摘要。w w l i b 主要的问题是数据库规模太小，但是它的方法对于 今后大规模网页的自动分类仍然有一定的借鉴意义。 g r o u p e r 是o r e nz a m i r 和o r e n e t z i o n i 研制的一个自动聚类系统，它的 主要作用是对h u s k y s e a r c l l ( 这是他们开发的一个元搜索引擎) 返回的结果 进行自动聚类。他们在c r r o u p e r ：a d y n a m i cc l u s t e r i n g i n t e r f a c e t o w e bs e a r c h r e s u l t s 一文中详细描述了它的原理和功能，很遗憾的是随着o r e nz a m i r 和 o r e ne t z i o n i 的毕业离校，这两个系统也停止了对外服务，但是g r o u p e r 还 是具有很大的参考价值。 v i v i s i m o 是个元搜索引擎，它调用a l t a v i s t a ，m s n ，n e t s c a p e ，l y c o s ， l o o k s m a r t ，f i n d w h a t 等搜索引擎的结果( 用户在它的高级检索中可以选择 具体调用哪一个或哪一些搜索引擎) ，对其进行自动聚类后返回给用户【1 1 1 。 v i v i s i m o 已经连续两年( 2 0 0 2 年2 0 0 3 年) 被搜索引擎观察( s e a r c he n g i n e w a t c h ) 的专家评为“最好的元搜索引擎( b e s t m e t a - s e a r c he n g i n e ) ”，英国物 理学会出版社( i n s t i t u t eo f p h y s i c sp u b l i s h i n g ) 也选择了v i v i s i m o 来提供检索 结果的自动聚类，以加强他们的电子期刊服务工作。 另外，g o o g l e 搜索引擎根据网址特点提供了“类似网页”；最大的中 文搜索引擎b a i d u 也在检索结果中根据网址提供了同一网站下的“更多的 结果”，这两个搜索引擎都在返回结果文档链接的基础上实现了一定意义上 的聚类。 国内从九十年代中期开始自动文本分类领域的研究，复旦大学和中科 院计算所对t r e e 测试中的分类任务进行了长期跟踪和研究，北京大学和清 华大学较早在搜索引擎“天网”和“网络指南针”上研究网页分类技术【1 2 1 。 但由于条件的限制，中文自动文本分类一直缺乏标准的测试语料，因此很 4 第l 章绪论 难对研究结果进行严格的评价。 1 3 本课题的研究内容 因为搜索引擎中文本多为网页结构，所以本文研究内容是网页自动分 类技术。网页分类首先要对待分类的网页进行文本表示，本课题选择现在 普遍采用的向量空间模型v s m ( v e c t o rs p a c em o d e d 进行文本表示。v s m 的表示方法引发一个严重的问题，就是维数过高，使文本分类的性能急剧 下降，因此迫切需要通过特征权重法和特征降维两大技术优化文本的向量 表示以帮助提高文本分类的性能。得到文档的特征子集后便可运用分类算 法生成分类器。本文在一些文献的基础上，重点作了四方面的工作。 ( 1 ) 特征权重传统的t f i d f ( t e r mf r e q u e n c y , i n v e r s ed o c u m e n tf r e q u - e n e y ) 特征权重计算公式是针对普通文本的，只利用了特征词的出现频率信 息。本文在详尽分析网页结构特点的基础上，结合网页的特性，对特征权 重计算公式t f i d f 进行改进，体现了处于w e b 文本结构中不同位置的特 征词对文本类别的不同区别能力。 ( 2 ) 特征选择特征选择是文本自动分类的一个关键步骤。在对特征选 择算法中的互信息m l ( m u t u a li n f o r m a t i o n ) 公式进行深入分析的基础上，考 虑类别比例不同和负值情况下隐藏的影响较大的特征信息，对其进行改进， 降低向量维度和稀疏度，并在一定程度上删除噪音特征项，节约计算开销， 并使文本之间的相似度更为准确，提高了互信息公式在w e b 信息的处理中 特征提取的准确性。 ( 3 ) 分类算法分类算法是分类系统的核心部分。本文在向量空间法的 基础上，通过分析k - 近邻k n n ( k - n e a r e s tn e i g h b o r s ) 方法的实质，针对其 不足，在特征选择的基础上，进一步考虑对分类有相同贡献的词，把对分 类有相同贡献的词合并，进一步降低特征向量维数，然后恰当地考虑特征 词的关联与共现等因素，对k n n 分类算法进行改进，提高分类的准确率。 ( 4 ) 测试分析对改进算法进行测试评价，得到一个经过优化的分类 器。本文采用2 0 _ n e w s g r o u p s 标准测试集和l i b s v m 分类器分别对改进的特 整些奎兰三兰翌主堂垡笙苎 征权重和特征降维两大文本优化技术以及改进的k n n 分类算法进行了测 试验证。实验证明，改进算法是可行的。 1 4 本文的组织结构 全文共分5 章，从第2 章开始具体的章节安排内容如下。 第2 章首先介绍了信息检索系统中搜索引擎的发展现状、分类、主要 技术与发展动向。其次对自动分类的定义、分类、关键技术进行了介绍。 为后面关键技术的研究打下基础。 第3 章首先详细介绍了文本表示采用的向量空间模型的概念，分析了 向量空间模型表示后特征权重法和降维两大技术优化向量表示的重要性。 其次详细介绍了现在常用t f i d f 特征权重表示法，并对其进行了改进。 然后详细介绍了特征降维中的特征选择的必要性，对常用特征选择算法进 行了分析评价，重点分析了互信息特征选择算法并对其改进。 第4 章首先对现有的分类算法进行介绍分析，然后对k n n 算法的原 理、优点和缺点进行了深入分析，并对其进行了改进。 第5 章首先介绍了分类器评价方法和标准，其次对实验环境进行了说 明，然后对本文改进算法进行了实验验证及分析。 最后对全文进行了总结，并对未来工作进行了展望。 6 第2 章相关基础知识介绍 第2 章相关基础知识介绍 2 1 搜索引擎技术 随着因特网在全世界的普及和发展，网页信息已经成为因特网上最重 要的信息资源。并且，因特网每时每刻都在发生着变化。由于网上的信息 是极其无序的，信息量越大，越难被利用。而且，没有人对因特网上信息 的有效性和有序性负责，用户要在信息海洋里查找信息，就像大海捞针一 样困难，因此如何获取和利用因特网上的信息就成了一个大问题。网络搜 索引擎就是在这种情况下发展起来的为用户提供信息检索服务的技术【1 3 】。 搜索引擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提 取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的。搜 索引擎提供的导航服务已经成为互联网上非常重要的网络服务，搜索引擎 站点也被美誉为“网络门户”。因而搜索引擎技术成为计算机工业界和学术 界争相研究、开发的对象。 2 1 1 搜索引擎分类 按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三 大类1 舢。 ( 1 ) 目录式搜索引擎以人工方式或半自动方式搜集信息，由编辑员查 看信息之后，人工形成信息摘要，并将信息置于事先确定的分类框架中。 信息大多面向网站，提供目录浏览服务和直接检索服务。该类搜索引擎优 点是因为加入了人的智能，所以信息准确、导航质量高，缺点是需要人工 介入、维护量大、信息量少、信息更新不及时。这类搜索引擎的代表是： y a h o o ! ，l o o k s m a r t ，s o h u ，新浪等。 ( 2 ) 关键字搜索引擎又称为机器人搜索引擎，由一个称为蜘蛛的机器 人程序以某种策略自动地在互联网中搜集和发现信息，由索引器为搜集到 7 燕山大学工学硕士学位论文 的信息建立索引，由检索器根据用户的查询输入检索索引库，并将查询结 果返回给用户。服务方式是面向网页的全文检索服务。该类搜索引擎的优 点是信息量大、更新及时、毋需人工干预，缺点是返回信息过多，有很多 无关信息，用户必须从结果中进行筛选。这类搜索引擎的代表是：g o o g l e ， a l t a v i s t a ，b a i d u ，北大天网等。 ( 3 ) 元搜索引擎这类搜索引擎没有自己的数据，而是将用户的查询请 求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处 理后，作为自己的结果返回给用户。这类搜索引擎的优点是返回结果的信 息量更大、更全，缺点是不能够充分使用所使用搜索引擎的功能，用户需 要做更多的筛选。这类搜索引擎的代表是i n f o s p a c e ，v i v i s i m o 等【i 卯。 2 1 2 性能指标 可以将w e b 信息的搜索看作一个信息检索问题，即在由w e b 网页组 成的文档库中检索出与用户查询相关的文档。所以可以用衡量传统信息检 索系统的性能参数查全率( r e c a l l ) 和查准率( p r e c i s i o n ) 衡量一个搜索引 擎的性能。 查全率是检索出的相关文档数和文档库中所有的相关文档数的比率； 查准率是检索出的相关文档数与检索出的文档总数的比率。对于一个检索 系统来讲，查全率和查准率不可能两全其美：查全率高时，查准率低；查 准率高时，查全率低。对于搜索引擎系统来讲，因为没有一个搜索引擎系 统能够搜集到所有的w e b 网页，所以查全率很难计算。目前的搜索引擎系 统都非常关心查准率。 2 1 3 搜索引擎主要技术 一般而言，一个搜索引擎一共由搜索器、索引器、检索器和用户接口 等四个部分组成 1 6 , 1 - q 。 ( 1 ) 搜索器搜索器的功能是在互联网中漫游，发现和搜集信息。它常 常是一个网络蜘蛛程序去自动地在互联网中搜索信息。个典型的网络蜘 蛛工作的方式，是查看一个页面，并从中找到相关信息，然后它再从该页 8 第2 章相关基础知识介绍 面的所有链接出发，继续寻找相关的信息，以此类推，直至穷尽。网络蜘 蛛要求尽可能多、尽可能快地搜集各种类型的新信息，同时因为互联网上 的信息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死连接 和无效连接。 ( 2 ) 索引器索引器的功能是理解搜索器所搜索的信息，从中抽取出索 引项，用于表示文档以及生成文档库的索引表【1 8 1 。 索引项有客观索引项和内容索引项两种：客观项与文档的语意内容无 关，如作者名，u r l ，更新时间、编码、长度等等；内容索引项是用来反 映文档内容的，如关键词及其权重、短语、单字等等。索引表一般使用某 种形式的倒排表( i n v e r s i o n l i s t ) 【1 9 】，即由索引项查找相应的文档。索引表也 可能要记录索引项在文档中出现的位置，以便检索器计算索引项之间的相 邻或接近关系。 索引器可以用集中式索引算法或分布式索引算法。当数据量很大时， 必须实现即时索弓l ( i n s t a n ti n d e x i n g ) ，否则不能够跟上信息量急剧增加的速 度，不能保证信息的及时性。索引算法对索引器的性能( 如大规模峰值查询 时的响应速度) 有很大的影响。一个搜索引擎的有效性在很大程度上取决于 索引的质量。 ( 3 ) 检索器检索器的功能是根据用户的查询在索引库中快速检索出 文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实 现某种用户相关性反馈机制。这是对前两个过程的检验，检验该搜索引擎 能否给出最准确、最广泛的信息，检验该搜索引擎能否迅速地给出用户最 想得到的信息。 在搜索引擎结果排序方法中，用到相似度计算，最简单的相似度计算 方法是直接计算查询串与文档的点积，比较常用的是余弦表示法，在该方 法中考虑到了文本的长度和查询串的长度。在此值得提到的是g o o g l e 的 p a g e - r a n k 技术。p a g e r a n k 的基本思想是：如果一个页面被多次引用，那 么这个页面很可能是重要的；如果一个页面尽管没有被多次引用，但却被 一个重要的页面引用，那么这个页面可能是重要的，一个页面的重要性被 均分并传递到它所引用的页面。 9 燕山大学工学硕士学位论文 h ) 用户接口用户接口的作用是输入用户查询、显示查询结果、提供 用户相关性反馈机制。主要的目的是方便用户使用搜索引擎，高效率、多 方式地从搜索引擎中得到有效、及时的信息。用户接口的设计和实现使用 人机交互的理论和方法，以充分适应人类的思维习惯。 用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供用 户输入查询串的文本框；复杂接口可以让用户对查询进行限制，如逻辑运 算( 与、或、非) 、相近关系( 相邻，n e a r ) 、域名范围( e d u ，c o m ) 、出现位 置( 如标题、内容) 、信息时间、长度等等。 2 1 4 搜索引擎未来动向 搜索引擎已成为一个新的研究、开发领域。因为它要用到信息检索、 人工智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、 自然语言处理等多领域的理论和技术，所以具有综合性和挑战性。又由于 搜索引擎有大量的用户，有很好的经济价值，所以引起了世界各国计算机 科学界和信息产业界的高度关注，目前的研究、开发十分活跃，并出现了 很多值得注意的动向吨2 1 。 ( 1 ) 提高检索结果的精度和有效性用户在搜索引擎上进行信息查询 时，并不十分关注返回结果的多少，而是看结果是否和自己的需求吻合。 对于一个查询，传统的搜索引擎动辄返回几十万、几百万篇文档，用户不 得不在结果中筛选。 解决查询结果过多的现象目前出现了几种方法：一是通过各种方法获 得用户没有在查询语句中表达出来的真正用途，包括使用智能代理跟踪用 户检索行为，分析用户模型；使用相关度反馈机制，使用户告诉搜索引擎 哪些文档和自己的需求相关及其相关的程度，哪些不相关，通过多次交互 逐步求精。二是用文本自动分类a t c ( a u t o m a t i ct e x tc a t e g o r i z a t i o n ) 技术将 文档分类，将网页按类分别建立相应的数据库，可对分类数据库进行查询， 提高搜索引擎查准率：文档按类别组织管理又可以使用可视化技术显示分 类结构，用户可以只浏览自己感兴趣的类别。本课题就是针对此研究动向 提出来的。 l o 第2 章相关基础知识介绍 ( 2 ) 基于智能代理的信息过滤和个性化服务信息智能代理是另外一 种利用互联网信息的机制。它使用自动获得的领域模型( 如w e b 知识、信 息处理、与用户兴趣相关的信息资源、领域组织结构) 、用户模型( 如用户 背景、兴趣、行为、风格) 知识进行信息搜集、索引、过滤( 包括兴趣过滤 和不良信息过滤) ，并自动地将用户感兴趣的、对用户有用的信息提交给用 户。智能代理具有不断学习、适应信息和用户兴趣动态变化的能力，从而 提供个性化的服务。智能代理可以在用户端进行，也可以在服务器端运行。 ( 3 ) 重视交叉语言检索的研究和开发交叉语言信息检索是指用户用 母语提交查询，搜索引擎在多种语言的数据库中进行信息检索，返回能够 回答用户问题的所有语言的文档。如果再加上机器翻译，返回结果可以用 母语显示。该技术目前还处于初步研究阶段，主要的困难在于语言之间在 表达方式和语义对应上的不确定性。但对于经济全球化、互联网跨越国界 的今天，无疑具有很重要的意义。 2 2 自动分类技术 文本分类指的是按照预先定义的主题类别，为文档集合中的每个文档 确定一个类别。这样，用户不但能够方便地浏览文档，而且可以通过限制 搜索范围来使文档的查找更为容易。 文本的人工分类过程，首先是由人类专家来将它们分类，然后被保存 于适合的记录材料，像计算机形式或硬拷贝。在这期间需要大量工作，并 且要求分类人员具有较多经验和专门知识。然而，分类质量有时得不到保 证，周期长、费用高、效率低、不易满足实际需要。因此，在人工分类文 本中存在大量问题，都是关于精确度和管理代价的。目前，y a h o o ! 通过 人工来对w 曲上的文档进行分类，这大大影响了索引的页面数目( y a h o o ! 索引的覆盖范围远远小于a l t a - v i s t a 等搜索引擎) 。 文本自动分类就是利用计算机对文本集( 或其它实体或对象) 按照一定 的分类体系或标准进行自动分类标记，属于同一类别的文本被标上相同的 类别标记，为文本信息的检索提供系统化的解决方案。 燕山大学工学硕士学位论文 2 2 i自动分类方法类型 根据分类知识的获取方法不同，可以将文本自动分类方法分为三大类 型【2 3 1 。 ( 1 ) 词匹配法词匹配法又可以分为简单词匹配法和基于同义词的词 匹配法两种。简单词匹配法是最简单、最直观的文档分类算法，它根据文 档和类名中共同出现的词决定文档属于那些类。很显然，这种算法的分类 规则过于简单，分类效果也很差。基于同义词的词匹配法是对简单词匹配 法的改进，它先定义一张同义词表，然后根据文档和类名已积累的描述中 共同出现的词( 含同义词) 决定文档属于哪些类。这种分类算法扩大了词的 匹配范围，在性能上要优于简单词匹配法。不过，这种算法的分类规则仍 然非常机械，而且同义词表的构成是静态的，对文档的上下文不敏感，无 法正确处理文档中其具体含义依赖于上下文的词，分类的准确度也很低。 ( 2 ) 基于知识工程的方法基于知识工程的文档分类方法主要依赖语 言学知识，需要知识工程师根据语言学手工地编制大量的推理规则作为分 类知识，这些规则通常面向具体的领域，当处理不同领域的分类问题时， 需要不同领域的专家制定不同的推理规则，而分类质量严重依赖于推理规 则的质量。此实现相当复杂，而且其开发费用相当昂贵。这方面的系统有 卡内基集团为路透社开发的c o n s t r u e 系统。 ( 3 ) 统计学习法统计学习法和词匹配法在分类机制上有着本质的不 同。它的基本思路是先搜集一些与待分类文档同处一个领域的文档作为训 练集，并由专家进行人工分类，保证分类的准确性，然后分析这些已经分 好类的文档，从中挖掘关键词和类之间的联系，最后再利用这些学到的知 识对文档分类，而不是机械地按词进行匹配。因此，这种方法通常忽略文 档的语言学结构，而用关键词来表示文档，通过有指导的机器学习来训练 分类器，最后利用训练过的分类器对待分类的文档进行分类。 这种基于统计的经验学习法由于具有较好的理论基础、简单的实现机 制，以及较好的文档分类质量等优点，目前实用的分类系统基本上都是采 用这种分类方法。 1 2 第2 章相关基础知识介绍 基于统计的分类方法主要可以分为两类：自动归类和自动聚类【2 4 】。 自动归类是根据某种特定的分类结构，通过训练集进行训练后提取分 类特征，然后对索引库中的所有文档进行预先分类。自动聚类是根据文档 向量之间的相似性，通过确定聚类中心对文档进行分类，所生成的分类结 构因检索结果的不同而不同。 自动聚类和自动归类的主要区别就是自动归类需要预先确定好类别体 系，并且要为每个类别提供一批预先分好的对象作为训练文集，分类系统 先通过训练文集学习分类知识，在实际分类时，再根据学习到的分类知识 为需要分类的文献确定一个或者多个类别，处理起来比较复杂。自动聚类 不需要事先定义好分类体系，比较好实现，但分类结构不确定，难以形成 准确的类别标识。这两种方法各有利弊，可根据具体情况来选择不同的分 类方法。 本文研究是自动归类技术，在很多文献中，也将自动归类称为自动分 类，在此规定，无特别说明，本论文中提到的自动分类和自动归类为一个 概念。 2 2 2自动分类关键技术 ( 1 ) 文本表示因为文本数据库中存储最多的是半结构化数据，并且文 档内容是人类所使用的自然语言，计算机很难理解其语义。所以首先要将 文本数据库中的文本转化为计算机能够处理的形式，为文本建立恰当的数 学模型。文档表示模型有多种，常见的有：布尔逻辑模型、向量空间模型、 概率模型、模糊集合模型等，以及在此基础上的扩展模型和混和模型【2 5 0 6 1 。 现在各种分类算法中文本的表示普遍采用向量空间模型。v s m 是由s a l t o n 等人在六十年代末到七十年代初期提出的模型，v s m 是由一组规范化正交 词条矢量所张成的向量空间，每一个文档映射向量空间的一点，向量间的 距离表示文档之间的相似度，通过这种模型可以将给定的文档以向量的形 式表示在v s m 中，从而将文档之间的相似性这一抽象的问题转化为具体 的空间的点与点的距离问题，通过计算出任意两个向量之间的近似程度， 从而来反映所对应的文档间的相似性。由于本文研究的自动分类关键技术 燕山大学工学硕士学位论文 与其有密切的联系，本文将在下面的3 1 节对向量空间模型进行详细介绍。 ( 2 ) 特征降维和加权文本用向量空间模型进行初步表示以后，表示文 本的向量空间的维数还很大，数量过大的特征项一方面导致分类算法的代 价过高，另一方面导致无法准确地提取文档的类别信息，造成分类效果不 佳。因此，需要在不牺牲分类质量的前提下尽可能地降低特征项空间的维 数【2 7 2 8 1 。它具有简化计算，正确分类，便于计算机处理等作用。为了使计 算机能够更有效地处理网页特征，必须对网页特征进行特征加权，将网页 特征表示成计算机能够处理的数学向量。网页数据是一种半结构化的数据， 要比文本复杂的多。在网页表示中，对任一特征而言，有两个影响它权值 的因素 2 9 , 3 0 1 。一是该词的词频，另一个是该词在网页中出现的位置，在网 页中不同位置出现的语词的价值是不同的。 ( 3 ) 分类算法对网页进行特征词的提取和表示以后，就可以对网页运 用分类算法进行分类了。选择适合的分类策略和算法是提高分类效率和准 确性的关键。所以分类算法是分类系统的核心部分【3 ”。 2 3 本章小结 本章首先对搜索引擎的分类情况、性能指标、主要技术和未来动向进 行了分析，引出搜索引擎中的重要研究内容，即自动分类。其次对自动分 类的定义、方法类型和关键技术进行了介绍。全章为后继章节研究的展开 起到一定的铺垫作用。 1 4 第3 章特征权重和特征降维 第3 章特征权重和特征降维 3 1向量空间模型 向量空间模型是s a l t o n 等人于2 0 世纪6 0 年代末提出的，并且在著名 的s m a r t ( s y s t e mf o rt h em a n i p u l a t i o na n dr e t r i e v a lo ft e x t ) 系统得到成功 的应用，从此以后，该模型及其相关技术，包括项的选择、加权策略等在 文本检索、自动索引、关键词自动提取等许多领域得到广泛的应用。特别 是随着网上信息的迅速膨胀，它还被广泛地应用到搜索引擎、个人信息代