（应用数学专业论文）智能搜索引擎导航器的研究和设计.pdf

河南大学研究生硕士学位论文第1 页 摘要 目前搜索引擎返回查询词的结果数量巨大，而用户所需要的只是其中很少一 部分内容，人们想准确地获取自己想要查询的知识越来越难。这就促使信息检索 技术进一步发展。本文的中心问题是研究、开发一种新的搜索引擎导航系统为用 户提供范围更小的、更接近用户需求的搜索结果。 对搜索结果的导航是让用户获得更精确搜索结果，有效缩小搜索范围的一个 重要手段。本文对于导航系统的研究思想是运用形式概念分析( f c a ) 方法，建 立一个层次清晰的分类体系以便于用户充分利用搜索结果，并在搜索结果之间建 立起它们的关联。通过提供精确的摘要让用户快速把握页面信息，对页面价值做 出判断。通过对搜索结果的导航，让用户更迅速获得自己想要的搜索结果，有效 缩小搜索范围。 基于这个思想，本文做了以下研究： 利用f c a 对搜索结果进行二次处理，建立一个分类系统来组织搜索结果。在 系统中，以文档为对象，以这些页面检索词为属性造格，通过导航树把这些关系 映射到页面的导航系统中。对于搜索结果数量巨大的查询词来说，该系统能让用 户缩小查找范围，可以更准确的查找到自己所需要的内容。这种分类是信息组织 的重要方法和手段，对信息资源内容具有充分的揭示作用，给搜索结果建立一个 层次清晰的分类体系以便于充分利用。 通过对f c a 在搜索引擎中的应用研究，我们课题组实现了基于f c a 的搜索 引擎，在该搜索引擎中，所有的网页都以对象的形式在格中组织。本文的任务是 研究和实现基于f c a 搜索引擎的导航系统。该导航系统的思想是对数据所在的格 进行搜索。利用节点中最小上确界，格的理想和滤子的特征在格中对检索词所在 概念进行确定，提取出含有搜索关键词节点集合所在的理想。搜索结果以理想的 方式组织返回，既可以有效的缩小搜索范围保持应返回的搜索内容，也可以保存 各搜索结果( 节点) 之间的关系。这个导航具有可以扩大缩小搜索内容的功能。 这个导航系统中，可以将搜索结果的扩大和缩小揭示本类的内容范围，既可以浏 览找到自己想要的知识也可以发现新的知识，揭示隐藏较深的内容。 在结果的导航中，为了让用户对页面的价值进行迅速有效的判断，本文研究 了文本信息摘要的自动提取，并提出了篇章结构和统计相结合的自动摘要系统。 在这种方法中，把对摘要的提取和现阶段网页中文章的结构相结合，通过对网页 或者文档中语句等信息位置的判定和统计出的句子所包含的词汇等共同计算句子 第1 i 页河南大学研究生硕士学位论文 权重，以供提取摘要。该系统得到了实现，并且此方法的优良性得到了验证。 在搜索引擎的导航方面，本文主要的贡献是： ( 1 ) 对搜索结果的自动分类，并验证了用f c a 自动分类的有效性； ( 2 ) 设计基于f c a 的概念搜索引擎搜索结果的导航系统； ( 3 ) 设计了一种统计和篇章结构相结合的摘要的自动提取方法，实现并验证 了其有效性。 关键词：形式概念分析，智能引擎，自动摘要，导航 河南大学研究生硕士学位论文第1 li 页 a b s t r a c t a tp r e s e n t ，t h er e t u r n e ds e a r c hr e s u l t sb ys e a r c he n g i n e sa r ei nag r e a tq u a n t i t y ； h o w e v e r w h a tu s e r sn e e da r eo n l yf e wo ft h e m t h i sm a k e si tm o r ea n dm o r ed i f f i c u l t f o rp e o p l et oo b t a i nt h en e e d e di n f o r m a t i o na c c u r a t e l y ，a n dt h e nm a k e st h ei n f o r m a t i o n s e a r c ht e c h n o l o g yd e v e l o pf u r t h e r t h es t u d yf o c u so fo u rw o r ki st op r o v i d em o r e c o n f i n e da n de u s t o m i z e ds e a r c hr e s u l t sf o ru s e r sb ys t u d y i n gt h es e a r c he n g i n e n a v i g a t i o ns y s t e m t h en a v i g a t i o no fs e a r c hr e s u l t si sa l li m p o r t a n tw a yf o ru s e r st og a i nt h er e s u l t s t l l e yn e e da n dt on a r r o ws e a r c hs c o p ee f f e c t i v e l y i nt h i sp a p e r , t h es m d yo ft h e n a v i g a t i o ns y s t e mi st ob u i l das y s t e mo fc l e a rc a t e g o r i z a t i o ns ot h a tu s e r sc a nm a k e f i l l l u s eo fs e a r c hr e s u l t sa n db u i l dr e l a t i o n sb e t w e e ns e a r c hr e s u l t s ；a n dt op r o v i d et h e s i m p l e s ta n dt h em o s ta c c u r a t ea b s t r a c ts ot h a tu s e r sc a ng e tt h ei n f o r m a t i o nq u i c k l ya n d t h e nj u d g et h ev a l u eo fw e bp a g e s t h r o u g ht h en a v i g a t i o no fs e a r c hr e s u l t s ，u s e r sc a n g a i nt h es e a r c hr e s u l t st h e yn e e dm o r eq u i c k l ya n dt h es e a r c hs c ei sa l s on a r r o w e d e f f e c t i v e l y b a s e do nt h i si d e a ，t h ef o l l o w i n gs t u d i e sa r em a d ei nt h i sp a p e r ： b yu s i n gf c a t h es e a r c hr e s u l t sa r ep r o c e s s e df o rt h es e c o n dt i m e ，d u r i n gw h i c ha c a t e g o r i z a t i o ns y s t e mi sb u i l tt oo r g a n i z et h e s er e s u l t s i nt h i ss y s t e m ，d o c u m e n t sa r et h e o b j e c tw h i l el a t t i c e sa r em a d ew i t ht h ed o c u t e r mo fw e bp a g e sa sa t t r i b u t e s ，a n dt h e n t h e s er e l a t i o n sa r em a p p e di n t ot h en a v i g a t i o ns y s t e mo fw e bp a g e sb yt h en a v i g a t i o n f r e e f o rd o c u t e l mw h i c hh a sag r e a tn u m b e ro fs e a r c hr e s u l t s m i ss y s t e mc a l lh e l p u s e r st 0f i n do u tw h a tt h e yn e e dm o r ea c c u r a t e l yb yn a r r o w i n gt h es e a r c hs c o p e t h i s k i n do fc a t e g o r i z a t i o ni sa ni m p o r t a n tm e t h o do fo r g a n i z i n gi n f o r m a t i o n ，w h i c hf u l l y r e v e a l st h ec o n t e n to fi n f o r m a t i o nr e s o u r c e sa n dm a k e ss e a r c hr e s u l t sp r e p a r e df o rb e s t u s eb yb u i l d i n gas y s t e mo f c l e a rc a t e g o r i z a t i o n t h r o u g hf u r t h e rs t u d yo nt h ea p p l i c a t i o no ff c a i ns e a r c he n g i n e s ，o u rt a s kg r o u p r e a l i z e dt l l es e a r c he n g i n eb a s e do nf c a i nt h i ss e a r c hn a v i g a t i o n a 1 1o ft h ew e b s i t e s a r eo r g a n i z e di nt h el a t t i c ei nt h ef o r mo fo b j e e l s 砚et a s ko ft h i sp a p e ri st os t u d ya n d r e a l i z et h en a v i g a t i o ns y s t e mb a s e do nt h ef c as e a r c he n g i n e t h ei d e ao f t h es y s t e mi s t os e a r c hi nt h el a t t i c ew h e r et h ed a t ai s a n dt od e t m et h ec o n c e p tw h e r et h ed o c u t e r m b e l o n g sb ym a k i n gn s eo ft h ec h a r a c t e r i s t i c so ft h eu p p e rd e f f m i t el i m i 钯dt h ei d e na n d t h ef i l t e ri nt h en o d e s 1 1 1 es e a r c hr e s u l t s a r eo r g a n i z e da n dr e t u r n e di nt h ew a yo fi d e a w h i c hc a l ln o to n l yn a r r o wt h es e a r c hs c o p ea n dk e e dt h es e a r c hc o n t e n tw h i c hs h o u l d b er e t u r n e d , b u ta l s ok e e p 也er e l a t i o n sb e t w e e ne a c hs e a r c hr e s u l t ( n o d e ) t h i s n a v i g a t i o nc a ne n l a r g eo rn a l t o wt h es e a r c hc o n t e n t i nt h i ss y s t e m ，t h es e a r c hr e s u l tc a n b ee n l a r g e da n dn a r r o w e dt oo p e no u tt h ec o n t e n to f i t sc a t e g o r y , b yw h i c hu s e r sc a nn o t 第1 v 页河南大学研究生硕士学位论文 o n l yf i n do u tt h ek n o w l e d g em e yw a n tb u ta l s of i n do u tt h ed e e p h i d d e nc o n t e n tw h i c h t l l e va r en o tc o n s c i o u so f i no r d e rt om a k eu s e r sh a v eaq u i c ka n de f f e c t i v e u d g m e n to ft h ev a l u eo fw e b p a g e si nt h en a v i g a t i o no f r e s u l t s ，t h i sp a p e rs t u d i e st h ea u t o m a t i ca b s t r a c t i o no f t h et e x t a b s t m c ta n do f f e r sa na u t o m a t i ca b s t r a c t i o ns y s t e mb a s e do nt h ec o m b i n a t i o no ft e x t s t r u c t u r ea n ds t a t i s t i c s f o rt h i sm e t h o d ，t h ea b s t r a c t i o no fa b s t r a c t sa n dt h et e x t s t r u c t u r eo fw e bp a g e si np r e s e n ts t a g ea r ec o m b i n e dt o g e t h e r , a n dt h ew e i g h i n go f s e n t e n c e sa r ec a l c u l a t e db yj u d g i n gt h ei n f o r m a t i o np o s i t i o no fs e n t e n c e si nw e bp a g e s o rt e x t sa n db yc a l c u l a t i n gw o r d si n c l u d e di ns e n t e n c e s ，b o t ho fw h i c ha r ep r e p a r e df o r a b s t r a c t i n ga b s t r a c t s t h i ss y s t e mh a sb e e nr e a l i z e da n dt h ec h o i c e n e s so ft h i sm e t h o d h a sb e e np r o v e d ， n em a i nc o n t r i b u t i o n so ft h i sp a p e rt ot h en a v i g a t i o no fs e a r c he n g i n e sa r ea s f o l l o w s ： ( 1 ) a u t o m a t i c a l l yc a t e g o r i z es e a r c hr e s u l t s a n dp r o v et h ee f f e c t i v e n e s so f a u t o m a t i cc a t e g o r i z a t i o nb a s e do nf c a ： ( 2 ) m a k eh en a v i g a t i o i lo fs e a r c he n g i n er e s u l t sb a s e do nt h es e m a n t i cm a d e o n f c a ： ( 3 ) d e s i g nan e wm e t h o do fa u t o m a t i ca b s t r a c t i o nb a s e do ns t a t i s t i c s a n d d i s c o u r s es t r u c t u r ea n da l s or e a l i z ea n dp r o v et h ee f f e c t i v e n e s so fi t k e yw o r d s ：f c a ，i n t e l l i g e n te n g i n e ，a u t o m a t i ca b s t r a c t , n a v i g a t i o n 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交酌学位论文是 本人在导师的指导下独立完成酌，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过酌材料。与我一同工作的，熙素戚瘫龋琥所做的任何贡献均已在论文中作 了明 了解 图书 太知 学术发展和进行学术交流等皤溺蕊爆嬲学k 缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 甄质文本和电子文本) 。 ( 涉及保密内睿酌学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名：二壬室逄 2 0o 学位论文指导教师签名： 7 年月1 3 目 趱曰 河南大学研究生硕士学位论文第1 页 第1 章绪论 搜索引擎出现在1 9 9 4 年，搜索引擎的出现是计算机技术和网络技术不断发展 的结果，也是为了满足人们对知识精益求精的要求。目前，搜索引擎已经成为人 们查询获取知识的重要手段，并且在入们的知识获取中起着越来越重要的作用。 传统的搜索引擎技术虽然满足了人们的一定需要，但是由于其通用的性质，仍然 满足不了不同背景，不同专业，不同时期人们对信息检索的要求【l 】。并且，目前 搜索引擎返回查询词的结果数量巨大，而用户所需要的只是其中很少的一部分内 容，一般来说，用户很少翻很多页，都是翻前几页，因此用户点击u r l 有很强的 局部性。所以，如何向用户提供更精确更有效的结果一直是搜索引擎开发所努力 的方向。 1 1 论文的研究背景 搜索引擎是向用户提供检索信息服务的工具。目前按照搜索引擎的体系结构 和工作原理可以把它们大致归纳为三类： 第一类是目录式搜索引擎。此类搜索引擎是通过人工分类的方式把网页进行 分类，分别链接到分属的各类目录下，提供目录服务。这种搜索引擎由于人工的 参与，所以其信息的准确性比较高，但是缺点是由于经过了人工处理，其信息的更新 速度比较慢。这种搜索弓1 琴见的倒予有y a h o o ( h t t p ：s e a r e h y a h o o ，c 0 1 ) ， s o h u ( h t t p ：w w w s o h u e o m ) ； 第二类是导航式w e b 搜索引擎。关键字w e b 搜索引擎是互联网上常用的一 种搜索引擎，一般都是由网络机器人( r o b o t ) 或者网络蜘蛛( s p i d e r ) 把网络信 息采集到一个数据库中，建立文档集合，再由本地的服务器进行分类索引。然后 用户进行查询，这种搜索引擎更新很快，但是查准率不高。目前常见的有 g o o g l c ( h t t p ：w w w g o o g l e c o m ) ，百度( h t t p ：w w w b a i d u c o r n ) ； 第三类是元搜索引擎。元搜索引擎不建立自己的数据库，当用户向其提交查 询关键词的时候，它把关键词提交给其它类型的搜索引擎，然后将其它搜索引擎 返回的结果中重复的去除。这类搜索引擎比较有代表性质的有 d o g p i l e o a t t p ：w w w d o g p i l e c o r n ) 国内比较有代表性的有搜星 ( h t t p ：w w w $ o 漱n c o t r ) 和优客( 1 a t t p ：w w w y o k c o m ) 。愿其他的像新浪 ( h t t p ：w w w s i n a c o r n ) 网易( h t t p ：m y w1 6 3 c o m ) 也是调用其他搜索引擎的结果， 或者在其搜索结果的基础上进行了再次开发。 第2 页河南大学研究生硕士学位论文 就目前而言，目录式搜索引擎占据了搜索引擎市场的主流，以我国为例：艾 瑞市场咨询的2 0 0 5 年数据显示中国网民常用的搜索引擎中百度独占鳌头，占中文 搜索市场份额的4 8 5 ，而排名第二的g o o g l e 占2 9 8 ，雅虎仅为3 2 其它几 个常用搜索引擎所占的市场份额分别是，新浪为3 ，7 网易为1 3 搜狐为1 5 【2 。 从这组数据我们可以看出，目前搜索引擎的主流是目录式搜索引擎。 但是目录式搜索引擎的缺点也很突出，就是出于其通用性，往往会返回数量 巨大的搜索结果，让人很难在其中把自己希望得到的结果都准确找出来，满足不 同的专业和兴趣爱好，为用户提供范围更小的，更接近用户需求的搜索结果，让 用户更准确的获得自己想要的结果是第三代搜索引擎发展的方向。 因此对搜索结果的导航是让用户获得自己想要的搜索结果有效缩小搜索范 围的一个重要手段【4 】。搜索结果的导航是让用户获得自己想要的搜索结果，有效 缩小搜索范围，建立一个层次清晰的分类体系以便于用户充分利用搜索结果，通 过提供最简单精确的摘要让用户快速把握页面信息，对页面价值做出判断。 1 2 论文研究目的和课题来源 建立搜索引擎导航系统主要目的是缩小搜索范围，并在搜索结果之间建立起 它们的关联，使用户通过这些关联发现新的知识。通过提供精确的摘要让用户快 速把握页面信息，对页面价值做出判断。通过对搜索结果的导航，让用户更迅速 获得自己想要的搜索结果，有效缩小搜索范围。下面列举本文研究目的： ( t ) 对搜索结果的自动分类： 目的：分类是信息组织的重要方法和手段 3 , 4 1 ，好的分类对信息资源内容具有 充分的揭示作用，给搜索结果建立一个层次清晰的分类体系以便于充分利用 意义：利用f c a 对搜索结果进行二次处理的分类方法。对于搜索结果数量巨 大的查询词来说，能让用户缩小查找范围，可以更准确的查找到自己所需要的内 容。 ( 2 ) 对f c a 做的基于概念的搜索引擎搜索结果的导航； 这个是对于我们研究组所做的基于f c a 的搜索引擎的结果导航，因为f c a 的搜索引擎具有基于概念和在整体上是若干个格构造的特点口t 母，因此这个导航也 有具有可以扩大缩小搜索内容，在予格搜索，结果组织以格的形式的特点。 目的；利用格的理想和滤子的特征忉在格上对检索词进行搜索结果的扩大和 缩小，在一食大格中能提取出对搜索结果最有效的子格州。 意义：返回模拟人对概念的理解来对搜索结果进行扩大和筛选。 ( 3 ) 文本信息摘要的自动提取 河南大学研究生硕士学位论文第3 页 目的：以提供信息内容梗概为目的，不加评论和补充解释，简明确切地记述 信息重要内容。 意义：可以使用户快速把握页面信息，对页面价值做出判断 s , 9 , t o j 。 本文的课题来源于河南省自然科学基金项目“分布式概念格模型和知识发现 ( 0 3 1 1 0 1 1 7 0 0 ) 。该项目的目的是建立并实现分布式的知识模型和计算模型，开发 一个原型系统，支持用户从各种常见的数据源中获取知识视图，并进行浏览和数 据分析。 1 3 国内外研究现状 在搜索引擎的导航方面，重点做了分类，导航，和摘要的自动提取三个方面 的研究，对于这些方面现在国内外的研究现状如下文所述： 1 3 1 搜索结果分类的研究 分类是信息组织的重要方法和手段，好的分类对信息资源内容具有充分的揭 示作用，给搜索结果建立一个层次清晰的分类体系以便于充分利用。利用f c a 对 搜索结果进行二次处理的分类方法。对于搜索结果数量巨大的查询词来说，能让 用户缩小查找范围，可以更准确的查找到自己所需要的内容。 从另一方面来说，分类是人类一种最基本的认知形式。所谓“文本分类”( t e x t c l a s s i f i c a t i o n t e x tc a t e g o r i z a t i o n ) ，其含义是指在给定的分类体系下，根据文本的内 容( 自动) 确定文本所属类别的过程。由于事先已存在关于这些文本信息的可以 使用的分类表( 一般是由领域专家事先制定的，或者经过聚类处理来获取) ，所以， 文本的分类处理常被研究人员看作是一种“有监督的学习”【5 2 】( s u p e r v i s i o n l e a r n i n g ) ，它的特点可以概括为“先有类( 表) 后有文档”。文本分类是一种组织 和管理信息的有力手段。传统的文献分类历史悠久，其研究活动有着丰富的研究 成果和相当的实用水平。随着文本信息的快速增长，特别是w w w 在线文本信息 的激增，一方面增加了对于快速自动的文本分类技术的迫切需要：另一方面也为 文本分类试验研究准备了充足的资源。对于自动分类技术而言，长期以来，占主 导地位的分类方法是由专业人员手工编写分类规则来指导分类试验；后来各种基 于统计方法的文本分类技术逐渐发展起来。而f c a 是一种基于内涵的聚类方法， 其造格的过程就是对象聚类的过程，通过f c a 的方式来对文档进行聚类，是一种 对文本分类的新方法。 在现代，对文本进行分类的方法主要有以下几种： 第4 页河南大学研究生硕士学位论文 ( 1 ) k n n 分类方法：k n n ( k n e a r e s tn e i g h b o u r s ) 法是一种简单而常用的文 本分类方法。该分类方法的基本思想是：给定一个经过分类的训练集合，在对新 文档( 待分类文档) 进行分类时，首先从训练文档集合中找出与测试文档最相关 的k 篇文档，然后按照这k 篇文档所属的类别信息来对该测试文档进行分类处理。 k n n 分类法优点是不需要预先学习，分类精度较高，不存在漏识问题。缺点 是分类速度与彭f 练文档库中文档的个数有关 1 ”。 ( 2 ) n a v i eb a y e s 分类方法：n b 法是将概率模型应用于自动分类，是一种 简单而又有效的分类方法，它的分类思想是使用贝叶斯公式，通过先验概率和类 别的条件概率来估计文档d 对类别e 的后验概率，以此实现对文档d 的类别归属 判断。n b 的优点是是n b 在文档分类过程中很快趋于稳定，通常只要扫描一遍 文档即可完成分类处理，速度较快。缺点是n b 法分类假定在给定分类变量的情 况下所有的特征项都是相互独立的，这在文本分类中是不现实的【1 2 1 。在搜索结果 中，各分类特征的关联尤其多，所以不适于用于特征关联密切的文档分类。 ( 3 ) s v m 分类法：s v m 是s u p p o r t v e c t o r m a c h i n e s ( 支撑向量积) 的简称， 它是在统计学理论上发展起来的优点在于通用性好，分类速度快，精度高，缺 点是实现过于复杂【l ”。 1 3 2 对搜索结果的导航 对搜索结果的导航最集中的体现就是为数众多的目录搜索引擎。导航式搜索 引擎在建立数据库时是根据从网页提取出的检索词相同或者相似对网页进行组织 的。所以导航式搜索引擎只是对关键词匹配后进行排序。目录式搜索引擎在建立 自己的数据库时对网页是分类组织，但是它们在组织之前已经定下了类别的数日 和名称，只是把网页放到已经固定下的类别，由于类别是固定的，所以网页和网 页间的关系也是固定的。如果把网页比做学生，把学校比作导航式引擎和目录式 引擎的数据库，对某一个学生张三甲进行搜索，导航式引擎返回的是张三甲以及 张三乙等，并且结果中并不表明这些学生的关系。如果用目录式的搜索引擎，则 会把这个学生属于某个学院，及这个学院的学生一起显示出来，但是如果张三甲 在这个学生参加了某几个社团，或者张三甲的弟弟同在这所学校，这些与之有关 的关系是不存在于搜索结果中的。 我们为什么要用形式概念分析的知识做智能搜索引擎。因为概念格在其定义 中已经表明了，各个概念之间所形成的是一种偏序关系，除了两顶点之外，每个 节点都有自己的子节点和超节点。通过子节点和超节点的定义我们可以看出，每 个节点和它的子节点是包含关系，该节点的属性少于子节点的。和它的超节点是 河南大学研究生硕士学位论文第5 页 被包含关系，该节点拥有多于超节点的属性。因为概念格上的节点是对具有相同 属性对象的聚合，其反映的关系在某种程度上甚至多于人对概念的理解，因此， 以格的方式对网页进行组织，有利于反映和发现网页之间的各种关系。用概念格 的方法组织数据源，把形式概念分析一些理论方法运用到导航中去可以帮助用户 发现更多关联，更多知识。 1 3 3 文本信息的自动摘要 导航的另外一方面要向用户提供网页的信息摘要，使用户对网页价值有判断 的依据。摘要是以提供信息内容梗概为目的，不加评论和补充解释，简明、确切 地记述信息重要内容的短文。自动摘要就是利用计算机自动编写和生成摘要的过 程。 文本信息摘要是指对文本信息内容进行概括，提取主要内容进而形成摘要的 过程。到目前为止，现有的文本自动摘要系统大致可以分为两大类，即基于统计 的自动摘要系统和给予理解的自动摘要系统，基于统计的自动摘要系统方法简单， 实现容易，但是产生的摘要结果不尽如入意。基于理解的自动摘要系统是在对文 本信息理解的基础上进行的，比较接近于人的思维和编制摘要的过程，所得的摘 要一般较好，但是难度较大【1 4 】。 计算机自动摘要是美国的h e l u l m 提出来的。他的主要思想是：将待摘文本 信息输入计算机，不迸行预编辑，根据禁用词表去除禁用词，记录余下词汇，将 内容词以字母顺序进行排列，对拼写方式相似的词进行统一合并然后提取高频词， 根据高频词抽取句子，计算句子权重，把权重高的句子作为摘要旬抽取，然后按 它们在文章中出现的先后次序排序输出。 国外关于自动摘要的研究比较早，最早的系统是上世纪5 0 年代末l u l m 设 计的a u t o e x t r a c t ss t a t i s t i c a ls y s t e m ，7 0 年代产生了面向领域的自动摘要系统，8 0 年代有学者将人工智能( 如认知学) 中一些理论应用在自动摘要中，9 0 年代开始 基于统计的自然语言处理方法再次兴起【1 5 】，受此影响，自动摘要系统中统计方法 的研究逐渐增多。目前的自动摘要系统研究多采用混合方法。国内的自动摘要研 究起步较晚，1 9 8 8 年上海交大研制了“汉语文献自动编制文献实验系统”，该系 统己能对科技文献进行摘要并取得了一定效果。经过这些年的发展，中文自动摘 要技术已经取褥了长足的发展，1 9 9 5 年上海交通大学得到国家“8 6 3 ”办公室的 资助，1 9 9 6 年4 月其成果“o a 中文文献自动摘要系统”通过了专家鉴定，该系 统的主要功能为提供主题摘要，偏重摘要和定题摘要【1 6 1 。 第6 页河南大学研究生硕士学位论文 本文针对文本自动摘要的问题进行讨论和分析，重点研究了i n t e m e t 上文本 自动摘要技术。n t e m e t 的发展使用户在线可获取的资源呈指数级增长。在w e b 信息检索中。人们有时仅从检出文档的标题和分类无法判断其是否符合要求。如果 能进一步给出文档的摘要、关键词，那么用户不必浏览全文就可以作出相关性判断， 这无疑将提高检索的效果和效率【1 7 1 。此外，用户还能通过关键词和摘要来检索所需 文档。可见，w e b 文档的自动摘要在智能化检索系统中占有相当重要的地位。目前， 自动摘要技术总体上分为两类：基于统计的机械摘要方法【t o i t s 和基于知识的理解 摘要方法。机械摘要使用统计方法来获取文档的关键词 嘲，并结合提示词、位置等 启发信息，从文档中挑选出一些合适的句子，进行润色后得到文档的摘要【1 0 # 0 0 1 0 2 1 ， 例如：k u p i c e c 等人开发的“t r a i n a b l ed o c u m e n t ss u m m a r i z e r ，复旦大学完成的“复 旦中文自动文摘系统”、上海交通大学的“o a 中文文献自动摘要系统”忙剐等。机 械摘要具有速度快、领域不受限的特点，但生成的摘要质量较差，存在反映内容不够 全面、语句冗余等问题。理解摘要期望利用各种知识和形式化理论，在理解文档概 念内容的基础上生成文摘【2 3 1 ( 对原文的概括或浓缩) 。与机械摘要相比，理解摘要质 量较好，具有简洁精炼、全面准确、可读性强等优点。但是，理解摘要不仅要求计算 机具有自然语言理解和生成能力阻2 5 0 6 1 ，还需要表达和组织各种背景、领域知识 口”。这些工作的难度十分巨大，迄今为止进展甚微，因此，理解摘要方法的使用比 较少见，仅限于非常狭小的应用领域中。例如：哈尔滨工业大学实现了一个军事领 域的自动文摘实验系统，北京邮电大学研制的文摘系统l a d i e s 口引。 但是，搜索引擎的页面的摘要在如今却并不理想，如今搜索引擎自动摘要主 要有下两种形式肛叫： ( 1 ) 提供命中网站或者网页的前几行信息，其典型代表为雅虎中国网站，该 法易于实现，但反映信息不全面，无法概括网页主题信息，有用信息少。 ( 2 ) 截取检索词周围的句子或文字，这是目前大多数搜索引擎采用的方法， 如g o o g e ，s i n a 等网站，这种方法方便动态处理，容易实现僵是内容杂乱。 搜索引擎的摘要处于起步阶段，效果并不理想，因此搜索引擎的自动摘要还 有大量的工作要做，所以本文在第五章节将介绍种统计和篇章结构相结合的摘 要系统。 4 4 论文的主要研究工作 本文对于导航系统的研究是运用形式概念分析( f c a ) 方法，建立一个层次 清晰的分类体系以便于用户充分利用搜索结果，并在搜索结果之间建立起它们的 关联。研究和实现基于f c a 搜索引擎的导航系统。实现了在格中的搜索和对子格 河南大学研究生硕士学位论文第7 页 的提取。提出了一种基于篇章结构和统计相结合的自动摘要系统。在这种方法中， 把对摘要的提取和现阶段网页中文章的结构耗结合，并验证了该方法的优良性。 1 4 1 论文研究的三个方面 ( 1 ) 对搜索结果的自动分类 通过f c a 的理论的研究，以文档为对象，以在文档中提取的检索词( 或者用 户自定义) 为属性建格【3 0 , 3 1 j 2 矧。利用f c a 对搜索结果进行二次处理，建立一个 分类系统来组织搜索结果。在系统中，以文档为对象，以这些页面检索词为属性 造格，通过导航树把这些关系映射到页面的导航系统中。对于搜索结果数量巨大 的查询词来说，该系统能让用户缩小查找范围，可以更准确的查找到自己所需要 的内容。这种分类是信息组织的重要方法和手段，对信息资源内容具有充分的揭 示作用，绘搜索结果建立一个层次清晰的分类体系以便于充分利用 ( 2 ) 对f c a 做的基于概念的搜索引擎搜索结果的导航 我们研究组根据概念格的聚类等性质，做出了基于f c a 的智能搜索引擎，该 搜索引擎在对数据源的组织上是以属性聚类的因此可以说是基于语义的一种智 能援索引擎。 对f c a 做的基于概念的搜索引擎搜索结果的导航是对f c a 的搜索引擎的结 果导航，在此搜索结果的导航上，我们通过因为f c a 的搜索引擎具有基于概念和 在整体上是若干个格构造的特点，因此对概念格提取理想或者滤子可以使导航器 具有扩大缩小搜索内容的功能。 在格的属性中搜索检索词，提取出含有搜索检索词节点的集合，这个导航系 统的目的是通过对搜索节点研究，利用节点中最小上确界，格的理想和滤子的特 征在格上对检索词所在概念进行确定，提取出子格。把提取出的子格映射到导航 树，结果组织则具有以格的形式的特点。因此，可以进行搜索结果的扩大和缩小。 该系统的意义在于模拟人对概念的理解来对搜索结果进行扩大和筛选，同时也建 立了搜索结果之间的关联。 ( 3 ) 文本信息摘要的自动提取 在结果的导航中，为了让用户对页面的价值进行迅速有效的判断，本文研究 了文本信息摘要的自动提取，并提出了基于篇章结构和统计相结合的自动摘要系 统。在这种方法中，把对摘要的提取和现阶段网页中文章的结构相结合，通过对 网页或者文档中语句等信息位置的判定和统 出的句子所包含的词汇等共同计算 句子权重，以供提取摘要。根据句子是否含有检索词，句子长度和句子在文章中 的位置来计算句子的权重，并按权重来对句子进行提取，该系统得到了实现并且 第8 页河南大学研究生硕士学位论文 此方法的优良性得n - ；验证。 1 4 2 论文的主要贡献 在搜索引擎的导航方面，本文主要的贡献是： ( i ) 对搜索结果的自动分类，将搜索结果用f c a 的方式进行组织并验证了 用f c a 自动分类的有效性； ( 2 ) 对f c a 做的基于概念的搜索引擎的导航系统进行设计； ( 3 ) 提出了一种统计和篇章结构相结合的新的自动摘要的提取方法，实现并 验证了这种方法的有效性。 1 5 内容组织 本文的主要研究对象是智能搜索引擎，主要研究内容是搜索引擎的导航系统。 本文内容组织如下： 第二章介绍了形式概念分析的部分理论基础，包括形式背景、形式概念、搜 索引擎分类和智能搜索引擎等内容。 第三章介绍了对搜索结果的自动分类，将搜索结果用f c a 盼方式进行组织并 分析了用f c a 自动分类的有效性； 第四章介绍了对f c a 做的基于概念的搜索引擎搜索结果的进行导航，介绍 了如何解决节点选取，提取子格，关系映射。 第五章介绍了搜索引擎摘要的自动提取，提出并实现了基于篇章结构和统计 相结合的自动摘要系统。通过比较和分析验证了其有效性。 第六章是全文的总结，对本文的主要研究工作进行简要的阐述，并探讨和展 望了在未来时间内应当完善的问题。 河南大学研究生硕士学位论文第9 页 第2 章基础知识 2 1 形式概念分析和概念格 概念是人类进行思维的最基本的单位，是用来组织成为诸如判断、结论等更 为复杂的思想的基础，是人类进行知识表述的一种有效手段，是一个哲学的范畴。 形式概念分析大约诞生于二十世纪八十年代，是一种对数据进行分析的工具 或者方法，特别是可以对给定的信息进行调查和处理。而数据应该是从人类有意 义的可以理解的思维单位概念中抽取而形成的形式化的单元。形式化表明的 是所处理的数据是形式化的数学实体，不必和人类思维中的概念完全相同，它同 时也指出形式概念分析处理的基本数据形式是形式背景，形式背景是人类背景知 识中的一小部分。 2 1 1 形式概念分析和概念格的定义 在哲学中，概念被理解为外延和内涵两部分所组成的思想单元，基于概念的 这一理解，德国的w i l l er 教授【5 】在1 9 8 2 年首先提出了形式概念分析理论，用于 概念的发现、排序和显示。概念格的每一个节点是一个形式概念，由两部分组成： 外延和内涵。外延，即概念所覆盖的所有对象的集合，内涵，则被认为这些对象 所拥有的共同特征的集合。概念格作为形式概念分析中核心的数据结构，本质上 描述了对象和特征之间的联系，表明了概念之间泛化和例化之间的关系，其相应 的h a s s e 图，则实现了对数据的可视化。 定义2 1 一个形式背景乜= ( g ，忆，) 由两个集合g 和m 以及g m 之间的 关系i e l gx m 组成，g 中的元素被称为形式背景的对象，m 中的元素被称为形式 背景的属性，若g l m 或者 聊) e l ，则表示“对象g 有属性m ”。 定义2 2 假定给定一个形式背景一个形式背景缸= ( g ，弛j ) ，其中g 为对 象集合，膨为属性集合，为它们之间的一个二元关系，则存在一个偏序集合与 之对应，并且这个偏序集合产生一种格结构，这种由背景一个形式背景( g ，j 】i 磊 d 所诱导的格l 就称为一个概念格。格三中的每一个节点是一个序偶( 即概念) 记为( x x7 ) ，其中x e g 称为概念的外延，x e m 称为概念的内涵。序偶 ( z x7 ) 关于关系r 是完备的，即有性质 第10 页河南大学研究生硕士学位论文 “o = h 肘卜z 胁)l f j q x = 卜gp 赡n 删 在概念格节点之间能建立一种偏序关系，给定o = ( xx7 ) ，c 2 = ( 屁x 27 ) ， 那么c 1 c 2 营恧 弼7 ，我们可以把这个偏序关系理解为亚概念一超概念的关 系。根据偏序关系可以生成格的h a s s e 图，如果c 1 c 2 ，并且不存在另外一个元 素c 3 ，使得c 1 c 3 c 2 ，那么从c l 到c 2 就存在一条边。这些介绍的是概念格的基 本知识，关于概念格的详细知识可以参考文献 5 , 3 0 , 3 t j 。 2 1 2 格的构造和显示 建格的过程是概念聚类的过程，在概念格中建格具有很重要的地位。对于同 一批数据，所生成的格是唯一的，即不受数据或者属性排列顺序的影响，这也是 概念格的优点之一。概念