（计算机软件与理论专业论文）基于形式概念分析与关键词加权的用户查询词扩展研究.pdf

西华大学学位论文独创性声明 | 1 i i ii ii ii iii i iii i iii i y 18 8 4 8 0 8 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体己经发表的研究成果，也不包含其他己申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：丑鄙 日期： a 7 彖7 西华大学学位论文版权使用授权 本学位论文作者完全了解学校有关保留、使用学位论文的规定，在校 攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文。( 保密的论文在解 密后遵守此规定) 学位论文作者签名：王孥 日期：文7 7 、6 , 7 指导教师签名： 日期 莎夕ij 6 夕 西华大学硕士学位论文 要 随着信息技术的飞速发展，互联网上新的网页每天以惊人的速度在增长；这为满足 用户检索信息提供了足够大的空间，但是想找到满足需求的信息也越来越成为困扰用户 的一个问题。搜索引擎作为一种网上信息服务系统，为用户在i n t e r n e t 上查找信息提供 了方便。 用户在使用搜索引擎进行信息查找时，通常都是向搜索引擎提交一系列的查询词， 但是由于自然语言的模糊性，用户提交的这些初始查询词并没有被搜索引擎准确理解， 导致搜索引擎返回的信息中有些与用户的查询意图是不相关的，甚至有些还会严重偏离 用户的搜索主题。解决词不匹配问题成为信息检索领域中十分重要的研究课题，查询扩 展是解决词不匹配问题的有效技术。为了更好地解决查询词扩展技术存在的问题，论文 结合形式概念分析( f o r m a lc o n c e p ta n a l y s i s ) 与关键词加权进行了查询词扩展的研究。 论文的主要研究内容归纳如下： 1 提出一种对查询扩展源进行优化的方法。优化的基本思想是：首先分别对用户相 关反馈过程中得到的文档和由搜索引擎返回的文档集中那些不同于用户相关反馈过程 中得到的文档进行分析，运用形式概念分析的知识建立两个概念格( c o n c e p tl a t t i c e ) ， 为了区分，就把这两个概念格分别称之为“用户概念格 和“挖掘概念格”，然后通过 计算概念相似值，在“挖掘概念格 中找出与“用户概念格 相似度较高的概念，最后 抽取出这些概念的外延，并将它们加入到用户选择的文档集合中去，达到优化查询扩展 源的目的。 2 提出一种通过给关键词加权进行查询词扩展的方法。在这种方法中，首先把用户 初始查询和查询扩展源中的文档转化为向量，通过计算向量之间的相似度得到文档与查 询的相似权值，接着分别在单个文档和整个文档集中分析词的权重，然后把这些权重值 进行合理的结合得到词的最终权重，最后选取那些权重值大的词作为查询扩展词。借助 这种方法，可以在整个文档集中抽取出质量较高的词作为查询扩展词。 论文最后通过2 0 组不同主题的用户查询词以及搜索引擎对每组查询词返回的前5 0 个网页进行实验验证。实验数据表明：论文提出的方法具有较大的实际应用价值，它能 够明显地提高搜索引擎的准确率和召回率。 关键词：搜索引擎；查询词扩展；形式概念分析；关键词加权 基于形式概念分析与向量加权的用户查询词扩展研究 a b s t r a c t a st h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , t h ew e bp a g e sa r ei n c r e a s i n ga ta s u r p r i s i n gs p e e do nt h ei n t e r a c t t h i sp r o v i d e sl a r g ee n o u g hr e t r i e v i n gs p a c e sf o rt h eu s e r s ， h o w e v e rt h ep r o b l e m st h a tp u z z l et h eu s e r sa r eh o wt of i n dt h ei n f o r m a t i o n 也e yf a c t u a l l y n e e d s e a r c he n g i n e sa st h eo n l i n ei n f o r m a t i o ns e r v i n gs y s t e ma i dt h eu s e r st ol o o kf o rt h e d e s i r e di n f o r m a t i o nc o n v e n i e n t l y w h e nu s e r ss e a r c hf o r i n f o r m a t i o nt h e yc a r e ，t h e ys u b m i tas e r i e so fs e a r c ht e r m st ot h e s e a r c he n g i n e h o w e v e r , t h ei n i t i a lq u e r yt e r m sc a n tb eu n d e r s t o o dc o r r e c t l yd u et ot h e a m b i g u i t yo ft h en a t u r a ll a n g u a g ea n dm a n yr e s u l t sr e t u m e db yt h es e a r c he n g i n ea r en o t r e l e v a n tt ot h eu s e r i n t e n t i o n ，e v e nd e v i a t ef r o mt h eu s e r t o p i c s o h o wt os o l v e t h em i s m a t c ho ft h e q u e r y - i sb e c o m i n gav e r yi m p o r t a n tr e s e a r c ht o p i ci ni n f o r m a t i o n r e t r i e v a l q u e r ye x p a n s i o ni so n eo ft h ee f f e c t i v em e t h o d st os o l v et h i sp r o b l e m i no r d e rt o s o l v et h ep r o b l e me x i s t i n gi nq u e r ye x p a n s i o n ，t h ep a p e rm a k e sas t u d yo nq u e r ye x p a n s i o n c o m b i n i n gf c a ( f o r m a lc o n c e p ta n a l y s i s ) a n dt e r mw e i g h r i n g t h em a i n j o bs u m m a r i z e da sf o l l o w s ： 1 1 1 1 ep a p e rp r o p o s e sam e t h o do fo p t i m i z i n gt h eq u e r ye x p a n s i o ns o u r c e 1 1 1 eb a s i c i d e ai s ：f i r s t ，w ea n a l y z et h ed o c u m e n t sc h o s e nd u r i n gu s e rf e e d b a c ka n dt h ed o c u m e n t sn o t c h o s e nb yu s e rb u tr e t u r n e db yt h es e a r c he n g i n e t h e nt h ek n o w l e d g eo ff c ai sa p p l i e dt o t h ep r o c e s sa n dt w ot y p e so f1 a t t i c e sa r ee s t a b l i s h e d ，n a m e d “u s e rc o n c e p tl a t t i c c a n d “m i n i n gc o n c e p tl a t t i c e s e p a r a t e l y t h ef o l l o w i n gi san o v e lm e t h o di sp r e s e n t e dt oc a l c u l a t e t h es i m i l a r i t yb e t w e e nc o n c e p t s ，f i n a l l yw es e l e c tt h ec o n c e p t sw i t hm u c hh i g h e rs i m i l a r i t i e s i nt h em i n i n gc o n c e p tl a t t i c ea n de x t r a c tt h ee x t e n to ft h ec o n c e p t sa n da d dt h e mt ot h ei n i t i a l d o c u m e n t s b yt h i sw ea c h i e v et h ep u r p o s eo fo p t i m i z i n gq u e r ye x p a n s i o ns o u r c e 2 at e r m r e w e i g h t i n gm e t h o df o rq u e r ye x p a n s i o ni s p r o p o s e d t h ef i r s ts t e p i s p r e s e n t i n gu s e r i si n i t i a lq u e r i e sa n dt h ed o c u m e n t si nq u e r ye x p a n s i o ns o u r o ei n t ov e c t o r s r e s p e c t i v e l y ，a n d 也es i m i l a r i t yi sc a l c u l a t e da n do r d e r e db yt h es i m i l a r i t yb e t w e e nt h ev e c t o r s t h es e c o n ds t e pi sa n a l y z i n gt h ew e i g h to fe a c ht e r mi nt h es i n g l ed o c u m e n ta n dt h ew h o l e d o c u m e n ts e tr e s p e c t i v e l y a n dt h e nw ec o m b i n et h et w oi nar e a s o n a b l ew a yt oo b t a i n i n gt h e f i n a lw e i g h to ft h et e r m t h et h i r ds t e pi ss e l e c t i n gt h et e r m sw i t hh i g h e rw e i g h tt ob eq u e r y e x p a n s i o nw o r d s a n dh i 曲- q u a l i t yk e y w o r d sa r ee x t r a c t e da sq u e r ye x p a n s i o nw o r d sf r o m t h ew h o l ed o c u m e n ts e tw i t ht h eh e l po ft h em e t h o d f i n a l l y , 2 0g r o u p so fu s e r s q u e r i e so nd i f f e r e n tt o p i c sa r es u b m i t t e dt os e a r c he n g i n e a n dt h et o p5 0p a g e sr e t u r n e db yt h es e a r c he n g i n ea r ee x p l o i t e dt ov a l i d a t et h ee x p e r i e n c e i i t h ee x p e r i e n c es h o w sg r e a tv a l u ei np r a c t i c ea n dc a l l i m p r o v et h ep r e c i s i o na n dt h er e c a l l o b v i o u s l y k e yw o r d s ：s e a r c he n g i n e ；q u e r ye x p a n s i o n ；f o r m a lc o n c e p ta n a l y s i s ； t e r m r e w e i g h i n g i i i 基于形式概念分析与向量加权的用户查询词扩展研究 目录 摘 要i a b s t r a o t i i 1 绪论1 1 1 国内外研究现状l 1 1 1 搜索引擎发展现状1 1 1 2 查询词扩展技术研究现状3 1 2 查询词扩展技术存在的问题5 1 3 研究背景和意义5 1 4 论文主要内容与结构一：。6 2 基于形式概念分析的查询词扩展源优化策略一7 2 1 形式概念分析7 2 2 优化查询词扩展源9 2 3 概念相似度计算方法：l o 2 3 1 基于距离的概念相似度计算方法1 1 2 3 2 基于概念内涵和外延的相似度计算方法一1 1 2 3 3 本文提出的概念相似度计算方法1 2 2 4 查询扩展源优化效果验证j 1 6 2 5 本章小结1 9 3 基于关键词加权的查询词提取策略2 0 3 1 停用词2 0 3 2 关键词加权一2 0 3 3 查询词的提取2 2 3 3 1 查询词提取过程2 2 3 3 2 查询词提取算法2 3 3 3 3 向量相似度计算方法一2 4 3 4 本章小结2 6 4 实验及结果分析2 7 4 1 系统实现2 7 4 1 1 开发环境一2 7 西华大学硕士学位论文 4 1 2 数据结构及典型实现代码一2 7 4 2 实验过程3 2 4 2 1实验数据3 2 4 2 2 实验步骤3 3 4 3实验结果3 6 4 3 1 实验评价指标3 6 4 3 2 实验参数设置3 6 4 3 3实验效果对比一3 8 4 4 本章小结4 1 5 结论与展望4 2 5 1 本文结论4 2 5 2 研究展望4 2 参考文献孕4 攻读硕士期间发表论文及科研项目一4 8 致谢5 0 v 西华大学硕士学位论文 1 绪论 互联网已成为人们日常生活中的重要信息来源，搜索引擎在一定程度上能够满足人 们的搜索需求。第2 7 次中国互联网络发展状况统计报告显示，截至2 0 1 0 年1 2 月 底，我国网民规模达到4 5 7 亿，比2 0 0 9 年底增加7 3 3 0 万人，而且网民数量依然保持快 速增长的势头，同时搜索引擎的使用率达高达8 1 9 【。 随着互联网技术的不断发展及其应用的日益普及，互联网上的信息正以指数级的速 度在增长，但是如何满足用户快速、准确获取信息的要求，己经成为搜索引擎需要解决 的一大难题。事实上，在搜索引擎返回的结果中都包含了与用户查询意图不相关的信息， 用户为了找到需要的信息，还要进行再次查找，这无疑是不受欢迎的。 在信息检索领域，查询词扩展技术是提高系统查询精度的有效途径，有些搜索引擎 也采用查询扩展技术来提高引擎的查询精度，但是由于自然语言的模糊性，现有的查询 词扩展技术已经不能满足互联网用户的需求，因此对现有查询词扩展技术的创新和改进 成为了一个热点问题【2 】。 1 1国内外研究现状 1 1 1搜索引擎发展现状 搜索引擎是互联网发展的产物，在互联网发展的早期，由于互联网上信息量较少， 用户在互联网上检索信息比较容易，但是随着互联网技术的发展，互联网上的信息以指 数级的速度在增长，此时若还是依靠早期的检索方式来进行信息查找，就远远不能满足 用户的搜索要求，搜索引擎的问世改变了这一现状。 1 9 9 0 年，世界上第一个自动索引互联网上匿名f t p 网站文件的系统由加拿大麦吉 尔大学的学生开发完成，并且给该系统起名为“a r c h i e ”( a r c h i ef a q ) ，a r c h i e 能够 定期搜集和分析f t p 服务器上的文件信息，也提供对不同f t p 主机上文件的查找，用 户在使用时必须向系统输入精确的文件名。虽然a r c h i e 搜集的信息是来自网站，而不是 网页，但是其和搜索引擎的基本工作方式是一样的，所以，a r c h i e 被公认为是现代搜索 引擎的鼻祖睁1 。 随着搜索引擎技术的发展，机器人( r o b o t ) 程序在搜索领域也开始暂露头角，其 中专门用于给搜索引擎提供服务的机器人程序称为网络蜘蛛( w e bs p i d e r ) 或网络爬行 虫( w e bc r a w l e r ) ，世界上第一个s p i d e r 程序是m i tm a t t h e wg r a y 完成的，该s p i d e r 程序刚开始时只用来统计互联网上的服务器数量，后来经过不断的发展，该s p i d e r 程序 也能实现捕获网址的功能【3 1 。 基于形式概念分析与关键词加权的用户查询词扩展研究 1 9 9 3 年，当基于网络蜘蛛的搜索引擎出现时，现代意义上的搜索引擎才真正浮出水 面。其中比较著名的有c o l o r a d o 大学的t h ew o r l dw i d ew e b 删w o r m 4 j 和n a s a 的r e p o s i t o r y - b a s e ds o f t w a r ee n g i n e e r i n g ( r b s e ) s p i d e r t 5 1 。w w ww o r m 只是以搜索工 具在数据库中找到匹配信息的先后次序来完成对搜索结果的排列，而没有涉及信息之间 的关联度，r b s es p i d e r 是第一个索引h t m l ( 超文本标记语言) 文件的搜索引擎，也是 第一个在搜索引擎返回的结果排列中引入关键字串匹配程度概念的搜索引擎。 1 9 9 4 年，斯坦福大学的两名博士生创办了雅虎。雅虎的出现，成功的让网络信息搜 索概念深入人心。随着雅虎访问量和收录网页数量的飞速增长，雅虎目录开始支持简单 的数据库搜索。同年，华盛顿大学的w e b c r a w l e r 正式亮相，w e b c r a w l e r 是互联网上第 一个支持搜索文件全部文字的全文搜索引擎。 1 9 9 5 年，元搜索引擎( m e t as e a r c he n g i n e ) 出现了，用户使用元搜索引擎进行信 息查询时只需提交一次查询请求，元搜索引擎能够将用户的请求经过处理后提交给多个 预先选定的独立搜索引擎，最后再将这些搜索引擎返回的查询结果进行集中处理，并把 最后的处理结果返回给用户巾j 。 1 9 9 8 年，g o o g l e 的问世给搜索引擎带来了新的定义。g o o g l e 在p a g e r a n k 、网页快 照、多语言支持、用户界面等方面都有较大革新。一直到2 0 0 6 年，g o o g l e 宣布其中文 名称为“谷歌”，这是g o o g l e 第一个在非英语国家起的名字。 2 0 0 0 年，具有强大f t p 搜索功能的北大天网搜索引擎问世。北大天网搜索引擎是 中国最早的搜索引擎，它由北京大学网络与分布系统实验室开发并维护运行，其搜集了 中国范围内大量的网络信息资源，尤其是较全面的覆盖了中国教育科研网内的资源。同 年，百度公司在北京中关村创立，2 0 0 1 年百度公司发布b a i d u 搜索引擎。 2 0 0 4 年，搜狐公司推出自主技术研发的中文搜索引擎，它以种人工智能的算法， 分析和理解用户可能的查询意图，通过这种算法的分析，给用户提供“搜索提示 。在 用户查询和搜索引擎返回结果的交互过程中，引导用户快速准确定位其需要检索的信 息。 2 0 0 5 年，微软公司推出了m s n 搜索引擎。当时的m s n 搜索引擎只是提供了网页、 图像、新闻等搜索功能。四年后，微软公司正式推出功能强大的搜索引擎b i n g ( 必应) ， b i n g 具有全新的搜索结果导航模式、创新的相关搜索和分类搜索等功能。 2 0 0 6 年，腾讯公司发布并开始运营s o s o 搜索引擎。该搜索引擎提供综合、网页、 图片、论坛、音乐、搜吧等搜索服务。 2 西华大学硕士学位论文 2 0 0 7 年，网易推出有道搜索引擎，有道搜索引擎采用了完全分布式的数据处理的模 式，同时对搜索的技术进行大幅升级，这主要表现在索引量更新速度、精确性和交互界 面等方面。 虽然搜索引擎从问世到现在只有十几年的历史，但是它在互联网上的地位是不可怀 疑的。随着互联网技术的发展，搜索引擎在质量、性能和服务方式等方面的提高空间都 很巨大，相关的研究成果更是层出不穷。 1 1 2 查询词扩展技术研究现状 查询词扩展技术是利用计算机语言学、信息学等技术，把与用户原查询相关的词或 与用户原查询语义相关联的概念以逻辑或的方式添加到用户原查询中去，然后用得到的 比原查询更长的新查询去检索信息，以改善信息检索的查全率和查准率【7 1 。在查询词扩 展过程中，查询扩展技术的核心问题是如何设计和利用查询词扩展源【8 - 9 1 。 在1 9 8 6 年，v a nr i j s b e r g e n 指出仅依靠用户原始查询词来提高系统的检索性能是有 限的，必须对原查询进行修改以提高检索性制m 】。随后十几年来，查询扩展技术获得了 巨大的成功，它已成为改善信息检索系统中查全率和查准率的关键技术之一，倍受学者 的重视和关注，有许多不同的学者从不同的领域提出各种各样的查询扩展模型，有基于 自然语言处理，有基于数据挖掘技术，有基于机器学习算法【1 1 0 5 】等等。如b i l l e r b e c k 提 出了一种通过关联查询来实现查询扩展的方法【l6 1 ，c u i 提出了一种使用用户查询日志的 概率查询扩展方法【1 7 】，j i i l 提出了一种基于词的相似树模型进行查询扩展方法【1 8 】，l i n 提 出了通过挖掘附加的查询词作为查询扩展词的方法【1 9 】，m a r t ib a u t i s t a 提出了一种通过挖 掘网络文档来获取查询扩展词的方法【2 们，s a f a r 提出了一种基于领域本体和概念结构的 查询扩展的方澍2 1 】等等。 查询扩展需要基于相关属性调整用户输入的查询字段，在此基础上，修改后的查询 字段会被重新提交给搜索引擎。传统的查询扩展是基于语义库来完成概念层次上的扩 展，而没有考虑概念之间的相关程度。目前的查询词扩展技术主要分为两类：全局分析 和局部分析。 较早出现的全局分析技术是具有较好实用价值的查询扩展方法，全局分析方法的思 想是对系统所有文档中的关键词或关键词之间的关联程度进行分析，通过计算每对关键 词或关键词组间的关联程度，将与用户原始查询词相似度高或者关联程度高的词加入到 用户的原始查询中生成新的查询词。目前较为常见的全局分析方法包括潜性语义标引、 统计词典和相似性词典等 2 2 也5 1 。 随着研究的深入，有很多研究学者在实验中发现传统的全局分析方法并不适应处理 逐渐增大的信息量，于是就有了局部分析的方法。 基于形式概念分析与关键词加权的用户查询词扩展研究 局部分析方法最早是由a t t a r 和f r a e n k d 2 6 】提出，其主要是利用首次查询结果文档 中与原始查询词最相关的n 篇文档作为扩展词的来源。局部分析的查询词扩展方法分为 相关反馈( r e l e v a n c ef e e d b a c k ) 和局部反馈( l o c a lf e e d b a c k ) 两类【2 7 。 相关反馈是最常见的查询词扩展方法，其主要思想是从用户认为相关的文档集中选 出重要的词语，然后在新的查询表达式中不断提高这些词语的重要程度，目的是在新的 查询表达中能够明显区分哪些文档是与用户查询意图相关的，哪些文档与用户查询意图 是不相关的【2 8 - 3 0 】。可以发现，相关反馈方法的缺点是过于依赖用户，如果用户的反馈有 误则搜索引擎的性能会大大降低。为了减少用户的参与，s j u n g 等提出将用户点击的网 页作为隐含的相关反馈，基于人工标注的相关网页数据集的实验表明，如果将所有点击 网页看作是用户的相关反馈，那么系统将会获得较好的准确率和召回率【3 。o l g a v e c h t o m o v a 在文献 3 2 1 中提出了两种基于用户反馈的查询词扩展方法，一种是要求用户 选择一定数量的可以代表文档的句子，另一种是展示给用户一个从初始文档集中抽取的 名词短语的列表。 在局部分析的基础上，研究人员运用各种技术，考虑影响查询词扩展技术的更多因 素，不断地提出了许多新的查询词扩展方法。r o e e h i o 提出了一种基于向量空间模型的 查询扩展方法【3 3 1 。这种查询扩展方法利用到了相关反馈的技术，其基本思想是重构查询， 以便更接近于相关文档的词语一权值向量空间。g r e f e n s t e t t e 设计了一个可以抽取词与词 之间的依据造句法关系的系统。这个系统的前提是假设同时出现在相同上下文中的词具 有相关性【3 4 】，这个假设在以后的查询词扩展研究中起到了非常重要的影响，此后的大量 研究都建立在这个假设之上。r i l am a n d a l a 提出的使用不同的词典扩展查询词的方法， 这种方法不仅从多种词典中提取扩展词，而且根据用户查询词为扩展词分配了权型 。 x u 和c r o f t 提出了局部上下文分析方法【3 6 - 3 7 ，从某种程度上讲，局部上下文分析方法在 整体上是一种局部分析方法，这种方法是基于名词词组而不是基于简单的关键词，同时 在这种方法中是把名词词组作为文档的概念，从排序靠前的文档中选择出一些与查询词 语同时出现的概念。 局部反馈的方法自动将用户初始查询结果中的前n 篇文档作为查询扩展源，并没有 经过用户的干预。r y e n 提出一种被命名为实时查询词扩展( r t q e ) 的交互式查询词扩展 方法【3 8 】，当用户在界面的文本框中输入查询词时，r t q e 提供一个建议添加的查询词的 列表，它为形成新的查询提供有效的可选查询扩展词。f a g r o o t j e n 提出了一种混合的 方法，设计一个基于全局信息的初始查询结果，同时产生一个局部概念上的总结，通过 这种方法提取得到的概念被作为查询词扩展的候选词p 引。a f o r m i c a 提出了一种利用本 体计算概念相似度来提取查询扩展词的方法，其思想是用本体中关键词的词频来计算属 4 西华大学硕士学位论文 性相似度m 。多数实验表明局部分析方法优于全局分析方法，因而当前的查询扩展 技术研究主要集中在与之对应的局部分析方法上。 1 2 查询词扩展技术存在的问题 查询词扩展技术是信息检索领域中一种有效提高系统查询效率的技术，其通过将与 用户查询词相关的词或短语加入到用户查询中去，目的是去除用户查询词的多义性，以 准确地表达用户的搜索意图。虽然查询词扩展技术有很大的发展，但是当前的查询词扩 展技术仍存在着以下些问题【4 2 4 3 】： l 、依赖性强 相关反馈被认为是查询词扩展中较好的方法，但是搜索引擎返回的结果较为依赖于 用户干涉，如果在相关反馈过程中，用户的“干涉”出现了主观性的偏差，那么搜索引 擎的返回结果在系统召回率和系统准确率上就会有明显降低。所以在相关反馈过程中如 何减少用户的“干涉”是搜索引擎需要亟待解决的问题。 2 、语义性弱 传统的查询扩展技术是以用户查询词为中心，主要是在符号匹配层次上进行简单的 查询扩展，而在查询词语义及查询词概念间关联程度上没有太多的关注。这样就会导致 搜索引擎对用户的查询意图没有充分的表达，更不能消除用户查询意图与检索结果间的 语义偏差。同样的，搜索引擎在处理用户提交的查询时，目前主要采用用户查询词与文 档中的关键词进行直接匹配的方式，通过这种直接匹配的方式在系统数据库中查找信 息，最后把查找的结果以文档的形式返回给用户 4 4 刚】。 鉴于传统查询词扩展技术的各种局限，论文运用查询词扩展源优化策略及向量加权 进行查询词扩展，目的就是解决查询扩展技术中的依赖性强、语义性弱等缺点，完善传 统查询词扩展的不足。 1 3 研究背景和意义 搜索引擎作为一种互联网信息服务系统，为用户在互联网上查找信息提供了方便。 用户在使用搜索引擎进行信息查找时，提交的初始查询词在某种程度上代表了其搜索意 图，但是由于自然语言的模糊性，用户提交的这些初始查询词并没有被搜索引擎准确的 理解，导致搜索引擎返回的信息中有些是与用户的查询意图不相关的，甚至有些严重偏 离了用户的搜索主题，这种现象称之为“查询漂移”r 瑚】。 查询词扩展是提高搜索引擎查准率与召回率的有效方法，在查询词扩展过程中，查 询词扩展源的获取对查询词的扩展非常重要，因为查询扩展词是在查询词扩展源中提取 5 基于形式概念分析与关键词加权的用户查询词扩展研究 的，查询词扩展源的质量直接影响到查询扩展词的质量，从而也影响到搜索引擎的查准 率和召回率。 论文第一步的研究是利用形式概念分析对查询扩展源进行优化，优化的目的是得到 高质量的查询词扩展源，第二步是在优化后查询扩展源中进行对查询扩展词的提取，使 得提取出的查询词更能代表用户的搜索意图，从而提高搜索引擎的搜索质量。 1 4 论文主要内容与结构 论文首先将借助形式概念分析的知识来对查询扩展源进行优化，接下来，在优化查 询扩展源的基础上，把查询扩展源中的网页和用户的初始查询分别转化为向量，利用向 量相似性来计算关键词在整个扩展源中的权重，通过计算，将综合权值大的关键词作为 查询词扩展词。 论文的主要结构如下： 第一章：介绍搜索引擎的发展现状、查询词扩展技术研究现状、查询词扩展技术存 在的问题、课题的研究背景和意义以及论文的主要内容与组织结构。 第二章：叙述形式概念分析中的相关概念，提出一种基于形式概念分析的查询扩展 源优化策略。 第三章：提出一种基于向量加权的查询词提取策略。 第四章：实验，主要通过实验平台的搭建和实验结果的展示进行叙述。 第五章：对论文进行总结，并展望下一步的研究工作。 6 两华大学硕士学位论文 2基于形式概念分析的查询词扩展源优化策略 概念是人类进行思维的最基本的单位，是用来组织成为诸如判断、结论等更为复杂 思想的基础，是人类进行知识表述的一种有效手段。形式概念分析的提出给人们带来了 一个利用概念处理问题的方法。 形式概念分析的数学基础是格论，用它可以建立对象与属性之间的二元关系，根据 其建立的二元关系可以揭示对象间的潜在语义联系。概念格是形式概念分析理论的核心 数据结构，它已经广泛应用到计算机学的多个领域，如数据挖掘、软件工程等【4 8 】。 2 1 形式概念分析 形式概念分析( f c a ：f o r m a lc o n c e p ta n a l y s i s ) 是在2 0 世纪8 0 年代初由德国w i l l e 教授提出的一种用来进行概念数据分析和知识处理的数学方法，它为形式概念分析奠定 了数学基础，是规则获取和知识表示的重要方法【4 8 铘】。 下面就论文涉及到的形式概念分析知识进行简要的叙述。 定义2 1 一个形式背景( f o r m a lc o n t e x t ) 是一个三元组k = ( o ，a ，r ) ，其中。是 对象集合，a 是属性集合，r o x a 是0 和a 之间的二元关系，o r a 表示0 0 与a 彳 之间存在关系r 。 为了表达形式背景中的一个形式概念( a ，b ) ，w i l l e 教授定义了两个集合函数： v a c _ g4 下：= m mlvg ea ：( g ，m ) r ) v b _ c m 艿+ ：= g e g iv m b ：( 岛m ) r ， 定义2 2 形式背景l o ( g ，m ，r ) 的个形式概念是一个对象与属性对( 0 ，a ) ，其 中0 下= a ，爿j = 0 。集合o 称为概念的外延，集合a 称为概念的内涵。 可以看出，概念的内涵是概念外延中所有对象的共同属性的集合，对应地，概念的 外延是概念内涵可以确定的最大的对象集合。 定义2 3 在概念节点之间能够建立起一种偏序关系。对于给定g = ( 4 ，属) 和 c 2 = ( 4 ，岛) ，则c l c 2 蜀c 岛434 ，领先次序意味着c 1 是c 2 的父节点或称 泛化。若概念c l = ( 4 ，墨) 和c 2 = ( 4 ，岛) 满足鸣c4 ，且不存在概念( a ，b ) 使得 4 cac 4 ，则称c i 是c 2 的直接超概念，c 2 是c 1 的直接子概念，记为( 4 ，4 ) ( 鸣，垦) 。 根据这种偏序关系所诱导出的格为概念格。 7 基于形式概念分析与关键词加权的用户查询词扩展研究 例2 1 用户给搜索引擎提交一个查询词纸，把搜索引擎返回的前1 0 个网页看成一 个集合，其标记为o = l ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，集合a = 虬，缸，2 ，虬， 。，吒) 是集合o 所指向网页中的关键词集合，它们的二元关系见表2 1 ，其中符号v 表示关键词在对应的网页中出现，没有任何标记的就表示关键词在对应的网页中没有出 现。 表2 1形式背景下的二元关系 t a b 2 1t h ei n c i d e n c er e l a t i o no ft h ef o r m a lc o n t e x t 誊键词纸 k lk 2 k 3 k tx 5 网页 1 _0t- 2 _ 3 - 40_ 5_ 6- 7 8 t 9 0 0- 1 0 - 形式概念分析的核心是概念格，概念格的每个节点是一个概念，它是外延和内涵的 统一体。图2 1 就是利用表2 1 中的二元关系构建得到的概念格。概念格在本质上描述 了对象和属性之间的联系，概念格中的每一个节点都表示一个概念，每个概念都由两部 分组成，即内涵和外延。内涵表示对概念的描述，它刻画了实例的共同特征，外延表示 概念所代表的实例。概念格是形式概念分析的重要组成部分，它能够实现概念的形式化 描述。概念的形成依赖于一定的背景知识，这种背景知识就是对象集和属性集的集合。 由于每一个概念都对应背景中一个子集，而每一个子集中的所有对象都具有共同的属 性。因此，概念格刻画了背景中对象和属性之间的联系。 8 西华大学硕士学位论文 图2 1 利用表2 1 中的二元关系构建得到的概念格 f i g 2 1u s i n gt h ei n c i d e n c er e l a t i o ni nt a b 2 1t oc o n s t r u c tc o n c e p tl a t t i c e 2 2 优化查询词扩展源 当在用户选择的文档集合中选择那些出现频率最高的词或短语作为查询扩展词时， 由于用户选择的文档集合中文档数量较少，通过这种方法选出来的词或短语并不非常适 合作为查询扩展词。 假设用户在一次搜索过程中，某一单词出现的频率在用户选择的文档集合中是最高 的，但是该单词只是出现在用户选择文档集合中的某一个文档中，在其它文档中部没有 出现。如果按照相关反馈中的选取扩展词的方法，这个词是会被选择作为扩展词的。实 际上这个单词并不适合做扩展词，虽然该词的词频在用户选择的文档集合中是最高的， 但是它没有在整体上( 用户的标记的整个文档集合) 代表用户的搜索意图。如果在查询 扩展中选择了这个单词，则可能会出现查询漂移的现象。所以，在用户相关反馈的情况 下，从标记文档中选取扩展词时需要考虑两个方面，一方面需要考虑词或短语在标记文 档集合中的出现频率；另一方面需要考虑词或短语在标记文档集合中的分布情况。一般 而言，在进行查询词扩展之前需要对扩展源进行处理，间接地讲就是去优化这些被用作 查询扩展的文档集合，以便从这些文档集合中抽取出的扩展词更能体现用户的搜索意 图，从而避免上面例子中的极端情况。 本章主要考虑如何去高效的优化更能代表用户搜索意图的查询扩展源。优化查询扩 展源的过程如图2 2 所示，该过程主要由以下几个步骤完成。 第一步：构建“用户概念格 在这一步中，对用户在相关反馈过程中标注的文档进行分析，建立概念格。由于这 9 基于形式概念分析与关键词加权的用户查询词扩展研究 个概念格是基于用户标注的文档，所以在论文中把这个概念格称之为“用户概念格 。 第二步：“挖掘概念格”的构建 在这一步中，首先在搜索引擎返回的文档集中找出一些不同于用户相关反馈过程 中选择的文档，把这些文档组成的集合标记为“挖掘文档集”，然后对“挖掘文档集 中的文档进行分析，建立另外一个概念格，并且把这个概念格标记为“挖掘概念格”。 第三步：计算概念相似度 在前两步构建得到的概念格的基础上，利用论文提出的一种计算概念相似度的方法 去计算“挖掘概念格 中每一个概念与“用户概念格”的概念相似值。 第四步：抽取概念外延 对在第三步中计算得到的“挖掘概念格 中每个概念与“用户概念格”的概念相似 值进行排序，找出相似度较高的概念，并抽取出这些概念的外延，将它们加入到用户标 注的文档集合中去，完成查询扩展源的优化。 图2 2 优化查询扩展源的过程 f i g 2 2 t h ep r o c e s so fo p t i m i z eq u e r ye x p a n s i o ns o u r c e 2 3 概念相似度计算方法 当前计算概念相似度的方法有很多，但是整体上主要包括两类：第一类是利用概念 在h a s s e 图的层次位置来量化概念间的距离，再将距离转化为概念相似度；另一类通过 1 0 两华大学硕士学位论文 领域知识，利用概念的外延和内涵计算概念间的相似度。 2 3 1基于距离的概念相似度计算方法 在文献 s 2 中作者提出了一种计算节点距离的方法( g c s mg e n e r a l i z e dc o s i n e s i m i l a r i t ym e a s u r e ) ，其思想是两个节点的距离主要由它们自己所处的深度和共同父概 念的深度来决定。如果概念的深度越大，那么该概念所表达的意思就越明确，如果两个 概念与它们共同父概念的距离越短，那么这两个概念之间的关系就越紧密。该方法的计 算公式如下： d i s ( m ，) ：望! 翌! 垒!