（计算机应用技术专业论文）基于形式概念分析的网页文本匹配研究.pdf

西华大学硕士学位论文 基于形式概念分析的网页文本匹配研究 计算机应用技术 研究生邓波指导教师杜亚军 摘要 随着互联网上信息爆炸式的增长，互联网就像是变成了一本没有目录的巨 大百科全书，让人们无法找寻自己想要的信息。搜索引擎的出现，为这本百科 全书加上了目录和索引。在2 0 0 4 年，中国互联网络信息中心( c n m c ) 在京发 布的第十四次中国互联网络发展状况统计报告显示：搜索引擎是用户在互联网 上获取信息最主要的方式，通过搜索引擎查找相关的网站：7 1 9 ；直接访问已 知的网站：2 3 2 ；随意浏览网站网页：2 4 ；通过网站的相关链接：2 4 ； 其他：0 1 。搜索引擎的任务帮助用户在浩如烟海的网上信息中用尽可能少的 时间找到自己感兴趣的信息。 虽然现在搜索引擎技术已经有了很大发展，以谷歌、百度为代表的第二代 搜索引擎已经成为了世界上最大的搜索引擎，提供了最便捷的网上信息查询方 法。但是当我们在上网查询信息的时候还是经常会感觉到搜索引擎所返回的结 果并不是尽如人意，其中包含了大量的冗余网页，这主要是因为目前主流的搜 索引擎主要采用用户查询词与网页中的关键词精确匹配的方式来向用户返回结 果。因此改进和提高搜索引擎的匹配策略，提高查询的精确率就成了研究搜索 引擎技术的一个热点问题。 本文采用了形式概念分析的方法，研究网页文本的匹配，文中提出一个新 匹配的策略：使用更加精确和现实的概念以提高过去的基于关键词的匹配策略。 通常，在信息检索系统中“关键词”是网页表示的基本元素。然而，人们对自 然语义中概念的理解一般是有概念的外延和内涵定义的。本文使用自然语义的 第1 页 西华大学硕士学位论文 概念相似的形式概念作为网页表示的基本元素，根据从每个网页中提取出来的 概念分别为每个网页建立一个概念格，并使用双向联想记忆存储器来存储这个 概念格，用这些概念的外延作为形式背景的对象集合，用这些概念的内涵作为 形式背景的属性集合，这样，不仅可以操纵比较小的概念格，而且可以加强信 息检索系统对自然语言文本的理解能力。然后再提取这些形式概念的与查询的 关键词相关的对象与属性进行匹配操作。网页的概念格用双向联想记忆存储器 进行编码，这样不仅可以避免复杂的建格算法，还可以根据后续进程中对文档 的理解灵活的更新网页的表示形式。本文提出的模型还使用了学习策略，通过 接收用户反馈，对关键词权重进行修改，使相关文档间的相似性得以加强，不 相关的文档则减弱。 本文最后对提出的新匹配的策略进行了测试实验，并与布尔匹配模型进行 比较，对新的匹配方法进行验证。实验的数据集包括6 0 个中文网页和一组查询 词。从每个网页中提取出一组概念作为训练集，来训练双向联想记忆存储器存 储网页的概念格，以进行匹配操作。并且对学习前后的精确率和召回率进行了 分析。实验表明，比起布尔模型，新匹配的策略在精确率和召回率方面有更好 的表现，并且根据用户反馈进行的学习策略能够达到使得相关文档间的相似性 加强，不相关的文档的减弱的效果。 关键词：搜索引擎，信息检索，形式概念分析，双向联想存储器，网页文 本匹配 第1 i 页 r e s e a r c ho fw e b p a g em a t c hb a s e do n f o r m a l c o n c e p ta n a l y s i s c o m p u t e ra p p l i c a t i o nt e c h n o l o g y m a s t e rd e g r e ec a n d i d a t e ：b o d e n gs u p e r v i s o r ：d u y a j u n a b s t r a c t w i t ht h eg r o w t ho fi n f o r m a t i o ne x p l o s i o no nt h ei n t e m e t ，i n t e r n e ts e e m st o h a v eb e c o m eo n ee n o r m o u se n c y c l o p e d i aw i t h o u ta c a t a l o g u e i tm a k e st h a tt h e r ei s 1 1 0w a yf o rp e o p l et ol o o kf o rm ei n f o r m a t i o nt h a tt h e yw a n t i ti st h ec o m i n gi n t o b e i n go fs e a r c he n g i n et h a ta d d e dt h ec a t a l o g u ea n dt h ei n d e xf o rt h a te n c y c l o p e d i a o n2 0 0 4 ，t h es t a t i s t i c r e p o r to ft h e1 4 t hc h i n e s ei n t e r c o n n e c t i o nn e t w o r k d e v e l o p m e n ts i t u a t i o na n n o u n c e db yt h ec h i n e s ei n t e r n e tn e t w o r ki n f o n n a t i o n c e n t e r ( c n n i c ) i nb e i j i n gs h o w s ：s e a r c he n g i n ei st h em o s tm a i nw a yo fg e t t i n g i n f o r m a t i o nf o rt h ec o n s u m e ro ni n t e m e t u s es e a r c he n g i n et os e e kr e l e v a n tw e b s i t e ： 71 9 ；v i s i tt h ek n o w nw e b s i t e d i r e c t l y ：2 3 2 ；b r o w s ew e b s i t ew e bd a g ea t r a n d o m ：2 4 ；t h er e l e v a n c el i n k st h r o u g hw e b s i t e ：2 。4 ：o t h e r s ：0 1 t h e o b je c t i v eo fs e a r c he n g i n ei st h a ti th e l p sc o n s u m e rt of i n dt h ei n t e r e s t e di n f o r m a t i o n t h e m s e l v e si nt h ep o s s i b l el i t t l eo ft i m ea m o n gl a r g ea m o u n to f i n f o r m a t i o no nt h e i n t e r n e t t h o u g ht h es e a r c he n g i n et e c h n o l o g yh a sa l r e a d yg o td e v e l o p m e n tv e r yg r e a t l y n o w , t h es e c o n dg e n e r a t i o ns e a r c he n g i n e ，a st h er e p r e s e n t a t i v eg o o g l ea n db a i d u ， h a sb e c o m et h eb i g g e s ts e a r c he n g i n ei nt h ew o r l dw h i c hh a sp r o v i d e dt h em o s t c o n v e n i e n ta n dr a p i d e s to fi n f o r m a t i o nr e t r i e v a lm e t h o do nt h e1 1 1 t e m e t w - 1 1 e nw e 一一一一 第1 i i 页 西华大学硕士学位论文 i n q u i r yi n f o r m a t i o no nt h ei n t e r n e t ，w es t i l lo r e nf e e lt h a tt h er e s u l tr e t u r n e dt ob y s e a r c he n g i n ei sn o te n t i r e l y s a t i s f a c t o r y i nw h i c hc o n t a i n s l a r g e a m o u n to f r e d u n d a n c yw e bp a g ea m o n gt h e m t h i si sm a i n l yb e c a u s et h em a i n s t r e a ms e a r c h e n g i n ea tp r e s e n tr e t u r nt ot h er e s u l tt ot h ec o n s u m e rm a i n l ya d o p t e dt h ew a yo fu s e r r e t r i e v a la n dk e y w o r da c c u r a t em a t c hi nt h ew e bp a g e i m p r o v i n ga n dp r o v i d i n gt h e m a t c ht a c t i c so fs e a r c he n g i r et h e r e f o r e ，i m p r o v i n gi n q u i r yp r e c i s i o nh a sb e c o m ea h o ts p o tp r o b l e mo fs t u d y i n gs e a r c he n g i n et e c h n o l o g y t h i st h e s i sa d o p tt h em e t h o do ft h ef o r m a lc o n c e p ta n a l y s i s ，s t u d i e sw e b p a g e t e x tm a t c h an e wm a t c ht a c t i c si sp u tf o r w a r di nt h i st h e s i s ：u s em o r ea c c u r a t ea n d r e a lc o n c e p tt oi m p r o v ek e y w o r d b a s e dm a t c ht a c t i c sp a s t g e n e r a l l y , i ni n f o r m a t i o n r e t r i e v a ls y s t e m t h ek e y w o r d i st h ef u n d a m e n t a le l e m e n tt h a tw e b p a g ee x p r e s s e s b u tp e o p l eu n d e r s t a n dt h en a t u r a ls e m a n t i cc o n c e p tw h i c hi su s u a l l yd e f i n e db y t h ee x t e n s i o na n dc o n n o t a t i o no ft h ec o n c e p t w eu s ef o r mc o n c e p ts i m i l a rt o t h en a t u r a ls e m a n t i cc o n c e p t 嬲t h ef u n d a m e n t a l e l e m e n tt h a tw e bp a g ee x p r e s s e s ，s e tu pac o n c e p tl a t t i c ef o re a c hw e bp a g e r e s p e c t i v e l ya c c o r d i n gt oc o n c e p te x t r a c t i n gf r o me a c hw e bp a g e ，u s et w o w a y a s s o c i a t i v em e m o r yt os t o r et h i sc o n c e p tl a t t i c e ，u s et h e s ec o n c e p t u a le x t e n s i o na s o b j e c t s e to ff o r mb a c k g r o u n d ，u s et h e s e c o n c e p t u a lc o n n o t a t i o na sa t t r i b u t e a g g r e g a t i o no ff o r mb a c k g r o u n d ，s ow ec a nn o to n l ym a n i p u l a t et h es m a l l e rc o n c e p t l a t t i c e ，b u ta l s oe n h a n c et h eu n d e r s t a n d i n ga b i l i t yf o rn a t u r a ll a n g u a g et e x to f i n f o r m a t i o nr e t r i e v a ls y s t e m a n dt h e n ，w ee x t r a c tt h e s ef o r mc o n c e p t sa n dt h e o b j e c ta n da t t r i b u t er e l a t e dt ot h ei n q u i r yk e y w o r dt oc a r r yo u tt h em a t c ho p e r a t i o n t h ew e bp a g ec o n c e p tl a t t i c ew i l lu s eb i d i r e c t i o n a la s s o c i a t i v em e m o r yt oc a r r yo u t ac o d e ，s ot h ec o m p l i c a t e db u i l d i n gl a t t i c ea l g o r i t h mc a nb ea v o i d e d ，t h ee x p r e s s i o n f o r mo fw e b p a g ec a na l s ob eu p d a t e df l e x i b l ya c c o r d i n gt ot h eu n d e r s t a n d i n gt ot h e d o c u m e n ti nt h ef o l l o w i n gc o u r s e t h en e wm a t c hm o d e lh a sa l s ou s e ds t u d yt a c t i c s ， t h r o u g hr e c e i v i n gc o n s u m e rf e e d b a c k ，m o d i f yt h ew e i g h to nt h ek e y w o r d ，m a k et h e s i m i l a r i t ya m o n gt h er e l e v a n td o c u m e n tr e i n f o r c e ，t h ei r r e l e v a n td o c u m e n t i s w e a k e n e dt h e n 第页 t h en e wm a t c ht a c t i c sp u tf o r w a r da r eu s e dt oc a r r yo u tt e s t i n ga ne x p e r i m e n t a tt h ee n do ft h et h e s i s ，a n dm a k eac o m p a r i s o nw i t hb o o l e ，t h en e wm a t c hm e t h o d i s v e r i f i e d t h ed a t as e to fe x p e r i m e n ti n c l u d e s5 0c h i n e s ew e bp a g ea n dag r o u po f i n q u i r yw o r d s e x t r a c tag r o u pc o n c e p tf r o me a c hw e bp a g ea st h et r a i n i n gs e tt o t r a i nb i d i r e c t i o n a la s s o c i a t i v em e m o r yt os t o r et h ew e b p a g ec o n c e p tl a t t i c ef o r m a t c ho p e r a t i o n a n da n a l y s i st h ep r e c i s er a t ea n dr e c a l lr a t ea tt h ef r o n to fs t u d y i n g a n da tt h eb a c ko fs t u d y i n g t h ee x p e r i m e n ts h o wt h a tc o m p a r i n gw i t hb o o l em o d e l ， t h en e wm a t c ht a c t i c s ，a tt h ea s p e c to fp r e c i s i o nr a t ea n dr e c a l lr a t e ，h a v eb e t t e r p e r f o r m a n c e a n dt h es t u d y i n gt a c t i c sa c c o r d i n gt ot h ef e e d b a c ko ft h ec o n s u m e ri s a b l et or e i n f o r c et h es i m i l a r i t ya m o n gr e l e v a n td o c u m e n t s ，t h es i m i l a r i t yo f i r r e l e v a n t d o c u m e n tc a l lb ew e a k e n e d k e y w o r d s ：s e a r c he n g i n e ，i n f o r m a t i o nr e t r i e v a l ，f o r m a lc o n c e p ta n a l y s i s ， b i d i r e c t i o n a la s s o c i a t i v em e m o r y , w e bp a g em a t c h 第v 页 西华大学硕士学位论文 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此声明。 作者签名： 叩虬 2 d dg 年j 月2 上日 导师签名：j p 它 。栌王月巧日 第5 3 页 西华大学硕士学位论文 第1 章绪论 现在互联网已经成为了人们生活中的主要信息来源之一。互联网提供了即 时丰富的信息( 以及人与人沟通参与娱乐的平台) ，深层影响着现代人的生活。 但随着网站数量和内容的急增，互联网就像是没有目录的巨大百科全书，让人 们无法找寻自己想要的信息。如何让用户在如此浩瀚的信息海洋中准确有效地 找到需要的信息便成了一个关键问题。在这种情况下，搜索引擎( s e a r c he n g i n e ) 应运而生。作为一种检索工具，搜索引擎的出现，就好比为这本百科全书加上 了目录和索引。不论我们想从互联网中了解新闻资讯，还是寻找学校和企业的 网址、以及各种的图片，或者是其他我们想知道的信息，只需要在搜索框中敲 入关键词汇，就能够获得相关的信息或网址。 w w w 的迅速发展和广泛应用为搜索引擎的发展提供了广阔的发展空间， 搜索引擎迅速发展为i n t e r n e t 的一个新兴产业。在经过了十几年的发展后，搜索 引擎已经取得了较大的成就，很多搜索引擎相继面世，如著名的g o o g l e ，百度、 天网等中英文搜索引擎。 但是，网上信息量巨大并且信息结构和关系复杂，并呈飞速增长趋势，而 且人类的参与使数据和信息中存在大量的不确定性。即使是使用搜索引擎，想 在互联网上进行有效的查询成了一件越来越不容易的事情。很多搜索引擎返回 的结果中往往都包含了大量用户不感兴趣的网页，用户为了找到自己所信息， 经常不是在这些网页中进行再次查找，就是不断改变查询词重新进行查找。造 成这种困扰的重要原因就是这些搜索引擎在用户查询条件与网页的匹配方法上 存在着许多问题。现有搜索引擎使用的检索技术是一种精确的匹配，而网页和 用户查询本身是自然语言构成的文档，传统文本匹配部分没有从网页和用户查 询构成的语言基础来解决问题，其文本表示方法无法表示出文本中词与词的联 系和它们之间的结构关系，不厶匕r j l , l 徊l 哭好的表示自然语言文本的内容，导致信息检 索质量不高，成为制约搜索引擎发展的瓶颈。也正是因此，在信息检索领域中 网页和查询的匹配是及其重要的研究。 第l 页 西华大学硕士学位论文 目前网页和查询的匹配方法具体的有：向量模型、布尔模型、潜在语义索 引模型、概率模型等等，其中应用最广泛的是向量模型。但是如前所述，其查 询效果并不是十分理想。本文借助于形式概念分析，这一有力数学工具，对用 户查询与网页的匹配问题进行研究，提出一个本文提出的匹配策略：使用更加 精确和现实的概念以提高过去的基于关键词的匹配策略，从而提高搜索引擎的 信息检索质量。 1 1研究现状 1 1 1 搜索引擎的发展趋势 c o m p u t e rr o b o t 是指某个能以人类无法达到的速度不断重复执行某项任务 的自动程序。由于专门用于检索信息的r o b o t 程序象蜘蛛( s p i d e r ) 一样在网络间 爬来爬去，因此，搜索引擎的r o b o t 程序被称为s p i d e r ( s p i d e rf a q ) 程序。 搜索引擎的原理是由网络蜘蛛按照一定的方式和要求对网络资源进行搜 集，并将搜集到的网页信息存储到搜索引擎的临时数据库中，然后由索引器对 收集到的网页信息进行预处理，从中提取对检索或查询有用的信息，比如网页 关键词、网页的分类类别等，并对关键词进行权值计算，形成规范的索引文件 数据库，再由检索器来根据用户的查询需要按一定的方式检索索引数据库，提 取满足用户需要的信息，其中当用户使用搜索引擎进行查询时，人机交互是通 过用户接口实现的，比如输入用户查询、显示查询结果、提供用户相关性反馈 机制。 所有搜索引擎的祖先，是1 9 9 0 年由m o n t r e a l 的m c g i l lu n i v e r s i t y 学生a l a n e m t a g e 、p e t e rd e u t s c h 、b i l lw h e e l a n 发明的a r c h i e ( a r c h i ef a q ) t 1 1 。在19 9 0 年 以前，没有任何人能搜索互联网。a r c h i e 是第一个自动索引互联网上匿名f t p 网站文件的程序，但它还不是真正的搜索引擎。虽然当时w o r l dw i d ew e b 还未 出现，但网络中文件传输还是相当频繁的，由于大量的文件散布在各个分散的 f t p 主机中，查询起来非常不便，因此a l a ne m t a g e 等想到了开发一个可以用 文件名查找文件的系统，于是便有了a r c h i e 。a r c h i e 是一个可搜索的f t p 文件 第2 页 西华大学硕士学位论文 名列表，用户必须输入精确的文件名搜索，然后a r c m e 会告诉用户哪一个f t p 地址可以下载该文件。 世界上第一个s p i d e r 程序，是m i tm a t t h e wg r a y 的w o r l dw i d ew e b w a n d e 一2 1 ，用于追踪互联网发展规模。刚开始它只用来统计互联网上的服务 器数量，后来则发展为也能够捕获网址( u 也) 。 随着互联网的迅速发展，使得检索所有新出现的网页变得越来越困难，因 此，在w a n d e r e r 基础上，一些编程者将传统的s p i d e r 程序工作原理作了些改进。 其设想是：既然所有网页都可能有连向其他网站的链接，那么从一个网站开始， 跟踪所有网页上的所有链接，就有可能检索整个互联网。到1 9 9 3 年底，一些基 于此原理的搜索引擎开始纷纷涌现，其中最负盛名的三个是：s c o t l a n d 的 j u m p s t a t i o n 、c o l o r a d o 大学o l i v e rm c b r y a n 的t h ew o r l dw i d ew e bw o r m 例 ( f i r s tm e n t i o no fm c b r y a n sw o r l dw i d ew e bw o r m ) 、n a s a 的r e p o s i t o r y - b a s e d s o f t w a r ee n g i n e e r i n g ( p b s e ) s p i d e r 4 1 。j u m p s t a t i o n 和w w ww o r m 只是以搜索 工具在数据库中找到匹配信息的先后次序排列搜索结果，因此毫无信息关联度 可言。而r b s e 是第一个索引h t m l 文件正文的搜索引擎，也是第一个在搜索结 果排列中引入关键字串匹配程度概念的引擎。 1 9 9 4 年4 月，s t a n f o r du n i v e r s i t y 的两名博士生，美籍华人j e r r yy a n g ( 杨 致远) 和d a v i df i l o 共同创办了y a h o o 。随着访问量和收录链接数的增长，y a h o o 目录开始支持简单的数据库搜索。因为y a h o o ! 的数据是手工输入的，所以不能 真正被归为搜索引擎，事实上只是一个可搜索的目录。w a n d e r e r 只抓取u r l ， 但u r l 信息含量太小，很多信息难以单靠u r l 说清楚，搜索效率很低。y a h o o 中收录的网站，因为都附有简介信息，所以搜索效率明显提高。 1 9 9 4 年初，w a s h i n g t o n 大学c s 学生b r i a np i n k e r t o n 开始了他的小项目 w e b c r a w l e r ( b r i a np i n k e r t o na n n o u n c e st h ea v a i l a b i l i t yo fw e b c r a w l e r ) 。 w e b c r a w l e r 5 】正式亮相时仅包含来自6 0 0 0 个服务器的内容。w e b c r a w l e r 是互联 网上第一个支持搜索文件全部文字的全文搜索引擎，在它之前，用户只能通过 u r l 和摘要搜索。 随后c a r n e g i em e l l o nu n i v e r s i t y 的m i c h a e lm a u l d i n 将j o h nl e a v i t t 的s p i d e r 程序接入到其索引程序中，实现了l y c o s 。除了相关性排序外，l y c o s 还提供了 第3 页 西华大学硕士学位论文 前缀匹配和字符相近限制，在搜索结果中使用了网页自动摘要，它的最大优势 是：它的数据量远远胜过其它搜索引擎。 1 9 9 5 年，元搜索引擎( a m e t as e a r c he n g i n er o u n d u p ) 出现了。用户只需 提交一次搜索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独立 搜索引擎，并将从各独立搜索引擎返回的所有查询结果，集中起来处理后再返 回给用户。第一个元搜索引擎，是w a s h i n g t o n 大学硕士生e r i cs c l b c r g 和o r c n e t z i o n i 的m c t a c r a w l e 一6 1 。但元搜索引擎的搜索效果始终不理想。 a l t a v i s t a 是第一个支持自然语言搜索的搜索引擎，a l t a v i s t a 是第一个实现 高级搜索语法的搜索引擎( 如a n d ，o rn o t 等) 。用户可以用a l t a v i s t a 搜索 n c w s g r o u p s ( 新闻组) 的内容并从互联网上获得文章，还可以搜索图片名称中 的文字、搜索t i t l e s 、搜索j a v aa p p l e s 、搜索a c f i v c xo b j c c t s 。a l t a v i s t a 也声称 是第一个支持用户自己向网页索引库提交或删除u r l 的搜索引擎，并能在2 4 小时内上线。大量的创新功能使它迅速达到当时搜索引擎的顶峰。a l t a v i s t a 最 突出的优势是它的处理速度。 1 9 9 8 年9 月2 7 日，g o o g l e 的问世再一次永远改变了搜索引擎的定义。它 在p a g e r a n k 、动态摘要、网页快照、d a i l v r e 仔e s h 、多文档格式支持、地图股票 词典寻人等集成搜索、多语言支持、用户界面等方面都有巨大的革新。- 北大天网是由北大计算机系网络与分布式系统研究室开发，于1 9 9 7 年l o 月2 9 日正式在c e r n e t 上提供服务。2 0 0 0 年初成立天网搜索引擎新课题组， 收录网页约6 0 0 0 万，利用教育网优势，有强大的邱搜索功能。 2 0 0 0 年1 月，超链分析专利发明人、前i n f o s c c k 资深工程师李彦宏与好友 徐勇( 加州伯克利分校博士) 在北京中关村创立了百度( b a i d u ) 公司。2 0 0 1 年1 0 月2 2 日正式发布b f i d u 搜索引擎。b a i d u 虽然只提供中文搜索，但目前收录中 文网页超过9 0 0 0 万，可能是最大的的中文数据库。b f i d u 搜索引擎的其它特色 包括：网页快照、网页预览预览全部网页、相关搜索词、错别字纠正提示、新 闻搜索、f l a s h 搜索、信息快递搜索。2 0 0 2 年3 月闪电计划( b l i t z c np r o j e c t ) 开始 后，其技术升级明显加快。 2 0 0 4 年8 月3 日，国内知名门户网站搜狐正式推出全新独立域名专业搜索 网站“搜狗”( w w w s o g o u c o m ) 。搜狐首推的互动式搜索，在用户输入一个查 第4 页 西华大学硕士学位论文 询词时，尝试理解用户可能的查询意图，给与多个主题的搜索提示，引导用户 更快速准确定位自己所关注的内容。 2 0 0 5 年，软件巨头m i c r o s o f t 正式推出了m s n 搜索引擎。目前m s n 搜索 引擎提供了网页、新闻、图像、音乐和m i c r o s o f t 百科全书等搜索功能。 1 1 2 用户查询与网页文本匹配方法的研究现状 在信息检索和数据挖掘的研究领域中，文本匹配是及其重要的研究方向。 文本匹配的主要组成部分是：文本预处理，将文本信息分词进行词频统计等； 查询操作，这是信息检索的关键部分，先将网页文本和用户输入的查询文本按 照一定的方法进行表示，然后采用一定的机制将用户的查询和索引文件数据库 中的候选网页进行匹配，计算它们与用户查询的匹配程度；结果排序，将检索 到的网页按一定的方式进行排序，返回给用户。 目前文档的表示大都采用特征空间方法。文档被分解成一个个独立的词， 从中选出能够代表文档的词条作为特征向量。每个词条就是特征向量的一个分 量，每个文档由一个特征向量表示。 目前网页和查询的匹配方法具体的有： ( 1 ) 向量模型：1 9 7 5 年由s a l t o n 7 】，i s 】，【9 】等提出。向量模型中文档被看成一 组独立的n 维词条向量，对每个词条分量都赋予一个权值，文档和用户查询的 匹配问题可以转化为向量空间匹配问题，用两个向量的夹角余弦表示文档和用 户查询的匹配程度。 ( 2 ) 布尔模型：1 9 8 0 年由b o o k s t e i n 1 0 】提出。布尔模型是一种简单的匹配 模型，如果用户提交的查询词条在文档中出现就赋予t u r e 值，反之赋予f a l s e 值，用a n d ，o r ，n o t 等逻辑运算符将查询词条连成一个逻辑表达式。布尔模型 的检索速度快，并且易于实现，几乎所有的商业搜索引擎都支持该模型。但是 该模型要求过于严格，漏检比较严重，而且没有考虑到关键字的权重问题，使 得检索结果不够令人满意。 ( 3 ) 潜在语义索引模型：1 9 9 0 年由d e e r w e s t e r l l l 】提出。它利用特征词与 文档对象之间的内在关系形成信息的语义结构，来反映数据间最主要的联系模 第5 页 西华大学硕士学位论文 式，忽略了个体文档对词语的不同使用风格。 ( 4 ) 概率模型：概率模型【1 2 1 【1 3 】考虑了词条和文档之间的统计概率。根据 先前检索过程中得到的相关性先验信息，计算文档集合中每篇文档成为相关文 档的概率，然后根据统计决策理论决定输出标准来确定哪些文档可以输出。 ( 5 ) 基于命题逻辑的模型：它将文档和查询当成一个命题公式，用逻辑推 导的方法计算二者的相关性。此外还有神经网络模型：它将每个关键词作为输 入神经元，每篇文档作为输出神经元，通过查询激活相应的输入神经元，来获 得输出信号，即相关文档。神经网络模型具有学习能力，考虑了关键词之间的 相关性。但是在实际的信息检索系统中很少应用，因为实际中需要太多的神经 元表示数据库中的文档和关键词，并且会因此产生大量的计算。 1 1 3 形式概念分析的研究现状 概念是人类进行思维的最基本的单位，是用来组织成为诸如判断、结论等 更为复杂思想的基础，是人类进行知识表述的一种有效手段。它是一个哲学的 范畴。德国的w i l l e 教授提出的形式概念分析( f o r m a lc o n c e p t a n a l y s i s ，f c a ) 理论【1 4 】，【1 5 】，【1 6 】，【1 7 】，实现了对概念的形式化描述。概念格( c o n c e p tl a t t i c e ) 贝f j 是形 式概念分析理论的核心数据结构，也是知识发现和信息表示的有力数学工具。 它在信息检索、数字图书馆、软件工程和知识发现等方面得到了一定的应用。 构建概念格的算法主要分为两类：批处理算法和增量算法。 在己提出许多生成概念格的批处理算法中只有少数算法在建立概念格的同 时生成h a s s e 图。批处理算法根据构造格的方式不同主要分为三类，分别是自 项向下算法：首先构造格的最上层节点，再逐渐往下构建，如b o r d a t l l 8 l 算法、 o s h a m t l 9 】算法等；自底向上算法：先构建最底部节点，再向上构建，如c h e i n l 2 0 1 算法等：枚举算法：按一定顺序枚举格中所有结点，如g a n t e r t 2 1 】，【2 2 1 算法和 n o u r i n e 2 3 1 算法等。 增量算法则是将当前要插入的对象和格中所有概念的外延相交，根据交集 的结果采取不同的处理方式，典型的算法有g o d i n t 2 4 j ， 2 5 1 算法及c a p i n e t o 2 6 】，【2 7 】 算法等。 第6 页 西华大学硕士学位论文 19 9 9 年b 否l o h l d v e k 提出了使用双向联系存储器( b i d i r e c t i o n a la s s o c i a t i v e m e m o r y ，b a m ) 表示概念格的方法。 1 1 4 基于形式概念分析的用户查询与网页匹配方法的研究现状 目前f c a 的应用领域很多，信息检索和数据挖掘是其中的重要的应用方 面，并取得了相当大的成果。f c a 在信息检索中主要用来发展浏览机制，很多 学者在这方面做了大量的研究【2 8 】 2 9 】。 c a r p i n e t o 和r o m a n o t 3 0 】【3 1 1 使用形式概念分析的方法开发了表示数据库文 本结构的软件工具g a l o i s 2 6 】和对文档数据库进行导航的软件工具u l y s s e s 2 7 1 ， 2 0 0 4 年他们使用形式概念分析的方法开发了c r e d o 3 2 】系统软件工具，其功能在 于对数据库进行查询导航。 】19 9 5 年，l i n d i g ”】采用形式概念分析的方法，在软件工程领域为了实现控 件共享，研究了控件查询软件，其基本思想就是：将描述控件的关键词组成形 式背景并形成概念格，当程序员输入查询词时，将查询词与概念格上结点进行 匹配。 在以上的研究中一般都是将整个待查询数据库之中的文档作为形式概念分 析中的对象，表示该篇文档的关键词条就是这个文档对象所包含的属性，如此 为整个数据库建立一个大的概念格。其中形式概念分析主要是用于导航方面。 2 0 0 2 年至2 0 0 5 年r a j a p a k s e 3 4 】【3 5 】等人采用了f c a 方法，研究了用户查询与文 本间的匹配问题。主要思想是把待匹配的每一个文档和用户查询文本分别表示 成一个概念格，概念格中的每一个概念就代表文本中出现的一个自然语义的概 念，并且用上面提到的使用b a m 表示概念格的方法，分别用两个b a m 将网页 文档概念格和查询概念格存储起来，实现对网页和查询的表示。通过提取所有 的相关的网页概念和查询概念组成候选概念对( 将二者同时具有的单个属性( 或 单个对象) 分别输入其b a m 中得到各自的稳定点，也就是一对相关的概念，称 为候选概念对) 进行匹配操作，为了计算匹配的相似度，文中定义了概念匹配 和关键字匹配两种匹配情况下候选概念对的相似度的计算方法，统计所有候选 概念对相似度之和作为网页与查询的相似度。以机器学习的方法使与查询相关 的文档的匹配程度增加，使不相关的文档匹配程度减弱。 第7 页 西华大学硕士学位论文 1 2研究目的和意义 目前i n t e m e t 已经成为人们生活中主要的信息来源之一。如何在其中查找出 自己所需要的信息就成为了一个关键问题。随之发展起来的搜索引擎已经成为 了用户在互联网上最主要的信息获取方式。但即便是当今最著名的g o o g l e 、百 度等中英文搜索引擎的搜索结果，依然存在着大量的、令用户不满意的网页。 其中，最重要的原因在于用户查询条件与网页的匹配方法上存在着许多问题。 本文的主要目的是希望通过对搜索引擎中信息检索部分中文本匹配部分的研 究，借助于形式概念分析理论，对用户查询与网页文本的匹配策略进行修改， 提出一个基于形式概念的匹配策略，使用更加精确和现实的概念以提高过去的 基于关键词的匹配策略，从而提高搜索引擎的信息检索质量，使查询结果的精 确率和召回率得以提高。 随着计算机网络技术的发展，各行各业均可以将与其相关的信息以数据库 的方式存储并发布于互联网上。因此，网络文本信息量巨大( 海量信息) 并且 信息结构和关系复杂( 复杂系统) ，完全超出了人们所能理解的范围。同时，由 于人类的参与修改使得这些数据和信息中存在着大量的不确定因素。想在一定 时间内从被存储的信息中搜寻并显示与查询条件相匹配的文本信息是非常困难 的，必须要借助于已有的理论和方法才能做到，特别是人工智能领域知识表示 及获取的研究成果。 本文研究的意义在于采用形式概念分析这一有力的数学理论对搜索引擎中 的用户查询与网页的匹配问题进行研究，形成一套基于形式概念分析的用户查 询与网页匹配方法。 现有搜索引擎使用的检索技术是一种精确的匹配，必然会造成匹配结果存 在大量用户不满意的信息。网页和用户查询本身是有自然语言构成的文档，传 统文本匹配部分没有从网页和用户查询构成的语言基础来解决问题，其文本表 示方法无法表示出文本中词与词的联系和它们之间的结构关系，不能很好的表 示自然语言文本的内容。而文本表示是进行匹配的前提，如果在这一环节的工 作没有做好，后续工作自然就会受到影响，导致信息检索质