（模式识别与智能系统专业论文）基于概念格的检索系统中概念挖掘技术的研究.pdf

北京邮电大学硕士学位论文 基于概念格的检索系统中概念挖掘技术的研究 摘要 “基于概念格的检索查询扩展系统与已有的查询扩展方法不 同，其主要特色是试图通过文本概念挖掘、文本间的概念关系、概念 格构建算法的综合利用，从概念的角度为用户提供自动查询扩展。 本课题以此为指导，主要在“基于概念格的检索查询扩展系统 的背景下，研究文本概念挖掘的方法。“基于概念格的检索查询扩展 系统，以概念为基础，以初始查询串为中心，并结合用户的主观调 节，给用户提供全面而清晰的查询扩展方向。本文的主要研究工作和 成果有： 1 ，基于传统的信息检索系统，增加了查询扩展分支。以形式概 念分析为理论基础，参考概念格在信息检索中的应用模式，设计并实 现了基于概念格的检索查询扩展模块。以文档概念间的关系，建立查 询扩展的方向，为用户提供以概念为基础的扩展建议；同时，图形化 的概念格图也有效提高了系统与用户之间的交互性，使得系统能更好 的利用用户对初次查询结果的反馈信息。 2 ，本文以文本的概念抽取为研究重点，完成了建格预处理模块 的实验性设计、实现与测试。尝试从信息熵的角度来评价特征对文本 的贡献度，用特征熵取代传统的i d f 。经过实验证明，基于特征熵的 文本概念抽取效果与c m 统计方法的效果相当，但效率上却得到了 较大的提高。 3 ，基于以上理论基础，又引入了领域词典的知识背景，使得特 征项的权值具有时间演变性，查询扩展的推荐词能够在内容相关性的 基础上具备时间相关性；其次，加入w e b 文档结构信息的应用，考 虑了特征项的位置权重。实验证明，以上措施可以在不影响计算效率 的前提下较好地提高概念抽取的效果。 关键词概念格查询扩展概念抽取特征熵 北京邮电大学硕士学位论文 t h es t u d yo fc o n c e p t 心i n gi ni n f o r l a t i o n r e t r i e 、j = f 气ls y s t e mb a s e do nc o n c e p tl a r t i c e a b s t r a c t t h es y s t e mo fa u t o m a t i cq u e r ye x p a n s i o nb a s e do nc o n c e p tl a t t i c e ( a q e c l ) h a st h ed i f f e r e n tw a yf r o mt h et r a d i t i o n a lm e t h o do fq u e r y e x p a n s i o n a q e c la t t e m p t st ou s et h et e c h n o l o g yo ft e x tc o n c e p tm i n i n g ， t e x tc o n c e p tr e l a t i o n ，a n dt h ea l g o r i t h mo fc o n c e p tl a t t i c ec o n s t r u c t i o nt o p r o v i d ea u t o m a t i cq u e r ye x p a n s i o nf r o mt h ec o n c e p tp o i n to fv i e w f o l l o w e dt h et h e o r yo ff o r m a lc o n c e p ta n a l y s i s ( f c a ) ，t h i st h e s i s w i l lf o c u so nt h ea l g o r i t h mo ft e x tc o n c e p te x t r a c t i o n ，w h i c hi so n eo ft h e m o s ti m p o r t a n ts t e p si na q e c l w i t ht h eb a s i so fc o n c e p t ，t h ec e n t e ro f o r i g i n a lq u e r y , a n dt h ea c t i v em o d i f i c a t i o n ，a q e c lc a l lp r o v i d e s a l l a r o u n da n dc l e a rs u g g e s t i o n st ou s e r s m a j o rw o r k si n c l u d e ： 1 ，an e wm o d u l eo fq u e r ye x p a n s i o ni sa d d e dt ot h et r a d i t i o n a li r s y s t e m f o l l o w i n gf c a a n dt h ea p p l i c a t i o nd i r e c t i o no fc o n c e p tl a t t i c e ，a m o d u l eo fq u e r ye x p a n s i o n , b a s e do nc o n c e p tl a t t i c ei sd e s i g n e da n d r e a l i z e d t h i sn e wm o d u l ew i l lp r o v i d e st h ew a yo fq u e r ye x p a n s i o nv i a t h ec o n s t r u c t i o no ft e x tc o n c e p tr e l a t i o n a tt h es a m et i m e ，t h en e w m o d u l ec a l la l s op r o v i d et h eh a s s eg r a p h i c s ，w h i c hw i l li m p r o v et h e e x c h a n g eb e t w e e n u s e r sa n do u ri rs y s t e m 2 ，t h ef o c u so ft h i st h e s i si st e x tc o n c e p te x t r a c t i o n ，a n dad e m o s y s t e mf o rt h ep r e p r o c e s sm o d u l ei si m p l e m e n t e di na q e c l ，a n d o r i g i n a lt e s t i n gh a sb e e nf i n i s h e d t h ec o n c e p to f t e r me n t r o p y ( t e ) ，f r o m i n f o r m a t i o ne n t r o p yp o i n to fv i e w , i su s e dt oe v a l u a t et e r mw e i g h ，i n s t e a d o ft h et r a d i t i o n a li d eo r i g i n a lt e s t i n gh a sp r o v e dt h a t ，t h em e t h o do ft e c a nb ec o m p a r e dt oc h i ；h o w e v e r , t ew i l li m p r o v et h ec o m p u t i n g e f f i c i e n c yt os o m ee x t e n t 3 ，a tt h es a m et i m e ，k n o w l e d g eb a c k g r o u n do fd o m a i nl e x i c o ni st h e a d d e da f t e rt h ep r e p r o c e s sm o d u l et om a k et h et e r mw e i g h ti sc o r r e l a t i v e m 北京邮电大学硕士学位论文 t ot i m e a d d i t i o n a l l y , t h es t r u c t u r ei n f o r m a t i o no fw e bt e x ti sa l s ob e e n t a k e ni n t oa c c o u n t f r o mt h er e s u l t so fo r i g i n a lt e s t i n g ，t h e s ea t t e m p t sc a l l i m p r o v e t h ep r e c i s i o no f c o n c e p te x t r a c t i o nw i t h o u te x p e n s eo fe f f i c i e n c y k e yw o r d s ：c o n c e p tl a t t i c e ，q u e r ye x p a n s i o n ，c o n c e p te x t r a c t i o n ， t e r me n t r o p y i v 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期：2 丝埠五业一一 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：杰鱼 导师签名：日期：墨! 堡：! ：进 北京邮电大学硕士学位论文 1 1 研究背景 第一章绪论 随着i n t e m e t i n t r a n e t 的快速发展与计算机的普及，我们已经进入了网络信息 时代。信息的发布与共享不再受时空的限制，网络资源以指数规律快速增长，特 别是w w w 的飞速发展，使i n t e r n e t 网络成为全球最大的分布式信息库，为用户 提供了一个快速方便的资源共享和信息共享的平台和前所未有的应用与开发潜 力。 当网络规模越来越大，信息越来越多时，信息的查找与获取也变得越来越困 难。对于每个纳秒都在扩张的知识资源，人们面临着如何获取和消化的烦恼，而 且无用信息无处不在。很多时候，面对庞大的信息资源，人们感到无所适从。如 何迅速、高效地检索和访问各领域的信息资源以促进信息的交流与共享已经成为 一个重要的急需解决的问题。人们迫切需要高效、准确的信息查找工具，来快速 定位自己感兴趣的信息和知识。传统的i n t e r n e t 服务为用户使用i n t e m e t 资源提 供了一些可行的途径，例如：搜索引擎。然而，相对于巨大、无序的i n t e m e t 信 息空间，目前基于关键词匹配的网络信息检索技术还很难满足这种要求，而且， 搜索引擎返回的结果往往成百上千，其中包含了大量与用户兴趣无关的信息。因 此研究具有语义理解能力、能够进行自动查询扩展的智能检索系统已经成为当务 之急。 1 2 问题提出 虽然搜索引擎基本解决了在庞大的i n t e r n e t 的信息库中为用户搜索所需要的 信息的问题，但其在资源覆盖度、检索精度、检索结果可视化、可维护等诸多方 面还远远不能令人满意。总的来说，当前的搜索引擎有以下几个方面的不足： 1 ) 个性化能力太差 现在的搜索引擎对所有用户都是一种模式，用相同的关键词查询得到的结果 是一样的，即查询不涉及用户的背景知识、兴趣特征，没有对单个用户的浏览模 北京邮电大学硕士学位论文 式和浏览行为进行分析的功能，因而不具有提取用户兴趣的能力和根据用户兴趣 变化调整搜索策略的能力。简言之，目前的搜索引擎针对的是一般的共性用户而 不能适应单个用户的查询要求。 2 ) 关键词的标引不符合语义理解的需要 几乎所有现有的搜索引擎都只具有关键词接口。虽然关键词接口在检索方面 给人们带来了很大的方便，但它并不科学。不能很好的表达用户的检索要求。搜 索引擎用抽取的关键词来标引文档，由于不同的词可以来表达同一个概念，同一 个词在不同的语义环境中可以表示不同的语义，所以关键词标引和检索方式既容 易脱离文档的语义内容，也容易脱离用户的领域知识和背景。只有提供自然语言 接口或采用语义、概念标引的方法才能使用户更好地表达自己地需求，使检索结 果更加准确。 3 ) 返回结果的显示方式过于简单 搜索引擎返回的检索结果中一般只包含文档的u r l 以及文献标题和摘要等 少量附加信息。用户要在众多的检索结果中确定自己所需要的信息，必须逐个浏 览，这是一项及其费时费力的工作。所谓的“信息过载 就是指的这种情况。研 究表达，用户只浏览检索结果中返回的前3 5 个页面所显示的信息，而对于之 后的页面很少进行浏览的，所以改善搜索引擎返回结果显示方式，给用户提供多 角度多层次的浏览，也是提高搜索引擎性能的重要途径。 当前搜索引擎对于用户提交的每一个查询请求，都只是顺序性地返回上百或 上千个网页，对搜索结果缺乏必要的组织，视图单一。不能动态地显示检索结果， 或者根据用户的需求对检索结果进行层次性的聚类、组合使用户能从多层次多视 角来浏览选择结果。 4 ) 用户与系统的交互过于简单，没有考虑以用户的反馈提高查询结果 并不是所有的用户一开始都有一个较为明确的查询目标。一方面，由于缺乏 良好的查询接口，用户不能准确地表达自己的查询请求，而搜索引擎又没有边查 询边修正查询关键词的功能，用户无法通过不断细化或精确化查询词来达到准确 表达自己的需求的目的。另一方面，系统只负责返回给用户，并不关心用户对返 回结果的选择和评价，没有充分利用用户的反馈来进一步提高系统的性能。 5 ) 没有有效的适应信息源变化的机制 由于i n t e m e t 的开放性及其动态性，新的信息在不断增加，旧的信息在不断地 更新变化，搜索引擎的更新和维护难以跟得上信息源的发展变化。死链接或不可 获得的网页链接经常出现在检索结果列表中。如何提供有效的适应信息源变化的 机制也是一个值得研究的课题。 6 ) 不能访问动态生成的页面 北京邮电大学硕士学位论文 搜索引擎只能访问“可索引打的网页、而对于由c g i 程序产生的动态网页就 无能为力了。然而，随着应用c g i 、p h p 、a s p 等的网站越来越多，动态网页生 成工具的使用已经是大趋势。大量的动态网页中蕴涵着丰富的有用信息，如果不 能索引这些网页，搜索引擎将丢失很多可以利用的信息。 智能信息检索系统试图从语义上理解和索引文档，并根据用户相关信息智能 化地理解用户的信息需求，实现概念检索，而不是简单的字符串匹配。真正的智 能信息检索系统应具有以下几个方面的特征： 1 在信息收集归类方面，除了用关键词来标引文档之外，还要能利用文档的 尽可能多的其他信息进行索引，给用户提供尽可能多的检索方式。更为重要的是 系统能在语义层次上理解文档内容，对文档进行归类索引，从而实现语义索引， 这是提高检索准确性的核心技术所在。 2 在提供查询服务方面，能使用自然语言处理、机器学习和信息推送等技术， 为用户提供更加准确、可靠和方便的信息服务。 3 在处理用户需求方面，能自动记录用户的各种要求，建立用户模型，并能 收集、分析用户的反馈信息，根据用户的反馈调整用户的领域模型和兴趣模型， 也就是说，系统应能够通过各种学习机制如遗传算法、符号归纳以及统计等各种 推理自动分析和抽取用户的信息需求以达到准确描述用户需求的目的。 4 系统应具有良好的自适应能力和更高的智能程度，能根据各种领域知识不 断地提高服务质量。例如对不同领域的文档采取不同的索引方式和组织；根据不 同的文档特征或用户喜好选择适当的显示方式；自行提高分类精度，相关度的计 算更为科学，等。 在分析了现有搜索引擎存在的不足后，本文提出了一种基于概念格的检索查 询扩展系统。考虑到关键词标引法不符合语义理解的需要，该系统从概念的角度 去表示文档，并建立文档之间的联系；为了增强用户与系统的交互，最大化利用 用户的反馈，系统在提供初步检索结果的基础上，为用户进一步的精细化查询提 供了扩展方向；再次，基于概念格的检索查询扩展系统不仅可以返回普通的基于 相关度排序的文字链结果，同时还提供了图形化的概念节点h a s s e 图，使得检索 结果图形化，进一步提高用户参与系统互动的积极性。 1 3 概念格检索查询扩展系统中的概念挖掘 用户在使用信息检索系统的时候，需要将自己的信息需求与系统提供的查询 语言的表示方式表示出来，对于信息检索系统来说，就是指定一个符合系统规则 的关键词的集合。一般说来，查询包含那些可以表示用户需求的关键词。但是用 北京邮电大学硕士学位论文 户在检索信息的时候，他的兴趣有可能很难表达或者这种兴趣包含的内容太宽 泛，这样所检索的信息在很多情况下就很难满足用户的需求。正如1 2 节所描述， 基于关键词匹配的检索系统，一方面由于无法正确标引大量同义词和多意词，导 致较低的查全率；另一方面用户提交的查询词往往不够规范、完整，或者与文档 索引使用的词存在很大差别，造成了较低的准确率。 针对上述缺点，人们提出查询扩展的方法，以便细化、精准化查询需求，为 用户找到所需资源。源于概念格理论和应用的发展【1 】【2 】f 3 1 ，概念格在信息检索领 域引起了越来越多的研究者的关注。基于概念格的检索查询扩展系统中，希望挖 掘文本中的语义信息，找出能够代表文本主题和区分其他文本的概念串，并通过 构建文档集中概念与概念之间的关系，来描绘出一幅查询扩展的全方向导航图。 由此可看出，基于概念格的检索查询扩展系统，其效果优劣的重点就在于文档概 念的挖掘是否准确、是否具有足够的代表性。 查询扩展系统中的概念挖掘要求与分类系统中特征选择的要求类似，一方面 要求选取的概念能够保留原文的信息，并足以和其他文档区分开来；另一方面希 望能够用尽量少的词或词组来解决文本特征空间高维性的特点，为之后的文本挖 掘应用奠定较好的基础。因此，本文将按照文本分类中特征选择的要求完成概念 挖掘的任务，其效果的好坏也将根据分类效果的好坏来评估。具体的概念挖掘模 块的流程设计以及算法实现将在第四章中介绍。 1 4 理论支撑 1 4 1 信息检索模型 信息检索( i r ，i n f o r m a t i o nr e t r i e v a l ) ，通常指文本信息检索，包括信息的 存储、组织、表现、查询、存取等各个方面，其核心为文本信息的索引和检索。 研究信息检索首先要量化检索的对象( 文本、w 曲页面、邮件等) ，并设计“相 关 的数学定义和相关度计算方法，再根据相关度由大到小给出有序结果。这一 过程就是对信息检索的建模过程。这个领域有三大经典的模型，分别是：布尔模 型、向量模型、概率模型。这些经典模型都将文档看作是词的集合，其中有一些 词比较有代表性，相比其他的词能够更好地反映文档的内容，因此经典模型认为 每篇文档都可以由一组有代表性的关键词来描述，这些关键词称为索引项。根据 每个索引项对于描述这篇文档作用的不同，每个索引项分配有一个权重。定义如 北京邮电大学硕士学位论文 f ： 设系统中索引项的总个数为t ，毛是其中一个索引项。k = 毛，毛) 是所 有索引项的集。文档d ，的电索引项的权重为嘞 o 。文档d j 中没有出现磅，则 = o 。因此任一文档d ，都关联一个t 维索引项向量d ，表示为 哆= ( m 比w ，) 。进一步，令为一个函数，对任意f 维的向量返回索引 项匆的权重，如：蜀( d ，) = m ，称为权重计算函数【4 1 。 在以上定义的公共基础上，三大经典模型在权重嵋，的确定，相关度的计算 等方面有所不同。以下将分别叙述三个模型的具体思想，都以上述定义为基础。 1 布尔模型 布尔模型是基于集合论和布尔逻辑建立的模型。布尔模型使用二进制数来表 示权重和相关度。索引项存在则权重为l ，不存在则权重为o ，查询和文档或者相 关，或者不相关。查询g 是布尔表达式，为查询g 的或连接形式，q c cq d n f 中任意一个组，若存在一个，其中的每个索引项的权重都与文档d 中相应索 引项的权重相同，则d 与g 相关，相关度为1 ，否则d 与鼋不相关，相关度为0 。 文档d ，与查询g 的相似度可以表示为： j i m ( d j , q ) ： 1 若 | g ”l ( g 彬) ( v 岛，( 嘭) 2 昌( g * ) ) 式( 1 1 ) 【0 其它 如果s 砌( d ，g ) = l 那么布尔模型认为文档d ，与查询g 相关，反之则不相关。 由以上定义可见，布尔模型是一种非常简单的模型。 2 向量模型 在一篇文档中，每个词对表达文章内容所作的贡献有所不同，布尔模型的二 进制权重认为所有出现的索引项贡献都为l ，这样的二进制权重不足以区分不同 索引项。因此向量模型提出了一种不完全匹配的机制，为查询和文档中的索引项 分配非二进制的权重。 定义如下：令m 。，为与二元组【毛，d ，】关联的权重，河为与二元组【颤，g 】关联的权 重，。叮o 。那么查询g - h 就可定义为孑：( m 田，心” 啡，) ，其中f 是系统中 索引项的总数。文档嘭仍然定义为乃= ( m w 2 ，w ，) 。这样文档哆和查询g 就表示成两个t 维的向量，文档和查询的相似度就由向量d ，和g 的关系来确定。 计算两个t 维向量的关系有许多方法，比较典型的一种就是计算两个向量的夹角 余弦： 北京邮电大学硕士学位论文 州砌2 晶d j q 2一ei=wl,ywfq ， 向量模型相比布尔模型有了较大的改进。从权重上将一篇文档的索引项分出 了主次关系，是一种更接近现实世界的模型。 3 概率模型 概率模型基于概率理论对信息检索建立模型，从直观上，用户提供查询g ， 检索到文档d ，d ，与查询g 的相关度取决于用户对d ，的感兴趣程度。所以对于给 定的查询g 和文档d ，概率模型试图估计用户会对d ，文档感兴趣的概率，也就 是将相似度计算转变为概率计算。 假设：1 、相关度仅取决于查询g 和文档表示； 2 、对于每一个查询都有一个文档集的子集作为答案集，称为理想答案集， 标记为r ，r 能够最大化与用户查询相关的概率； 定义：令索引项权重为二进制变量，即w ， 0 , 1 ) ，w t ，。 o ，1 ，查询g 是索引项 的子集。令r 为已知( 或者事先假定) 与g 相关的文档集合。则p ( r l d ，) 为文 档d ，与查询g 相关的概率，p ( r i d ，) 为文档d ，与查询g 不相关的概率。那么文档 d ，与查询g 的相似度定义为： 、p ( rid f ) 砌( d j 珂户币焉 引1 3 ) 根据贝叶斯公式，有： s i m ( d j , q ) = = p ( d j i r ) p ( r ) 式( 1 4 ) p ( d ，lr ) 尸( r ) 其中p ( d ，lr ) 表示从相关文档集合r 中选出文档d ，的概率。p ( r ) 表示从所有 文档中随机挑出一篇文档是相关文档的概率。 三种经典模型中，布尔模型被认为是最弱的模型。而概率模型是否比向量模 型更好尚无定论。从经典模型中又发展出了几个比较主要的模型。其中布尔模型 引申出了模糊集模型和扩展布尔模型；向量模型引申出了无特征向量模型、语义 索引模型、神经网络模型；概率模型则有推理网络模型和主要网络模型两个引申 模型。 北京邮电大学硕士学位论文 1 4 2 形式概念分析的理论基础 在哲学中，概念被理解为外延和内涵两个部分所组成的思想单元。基于概念 的这一哲学理解，德国的w i l l e 教授【5 】提出了形式概念分析，用于概念的发现、 排序和显示。在形式概念分析中，概念的外延被理解为属于这个概念的所有对象 的集合，而内涵则被认为是所有这些对象所共有的特征或属性集，这实现了对概 念的哲学理解的形式化。所有的概念连同它们之间的泛g 例化关系构成一个概 念格。概念格结构模型是形式概念分析理论中的核心数据结构，它本质上描述了 对象和特征之间的联系，表明了概念之间的泛化与例化关系，其相应的h a s s e 图 则实现了对数据的可视化。 先介绍一下形式背景的定义，更详尽的描述请参考文献【6 】：形式背景定义为 一个三元组k = ( g ，m ，j ) ，其中，g 是对象结合，m 是属性集合，g x m 是 g 与m 之间的一个二元关系。若( g ，朋) i ，读作“对象g 具有属性棚一。 形式背景通常用交叉表( c r o s st a b l e ) 来表示。在交叉表中一行代表一个对象， 一列代表一个属性，第g 行和第m 列的交叉点有一个“x 一，当且仅当( g ，册) i 。 对象集合的每个子集彳gg ，定义导出算子烈彳) 求出集合彳中所有对象的共 有属性： 认彳) = 切miv g a ，( g ，册) i 记为彳式( 1 5 ) 对称地，对属性集合的每个子集b m ，定义导出算子少( 曰) 求出具有集合b 中 所有属性的对象集合： 少( b ) = g giv m b ，( g ，m ) i ，记为b 式( 1 - 6 ) 形式背景k = ( g ，m ，) 上的一个形式概念定义为一个二元组( 么，b ) ，且满足： 彳g ，口s 肘，a - b ，b - a 式( 1 7 ) 其中，彳称为概念( 彳，b ) 的外延，丑称为概念( 么，召) 的内涵。 ( 彳，口) 和( c ，d ) 是形式背景k = ( g ，m ，d 上的任何两个概念，称( 4 曰) 是( g d ) 的 超概念，当且仅当bgd ，记为( c d ) ( 彳，b ) 。即： ( c ，d ) ( 么，口) b d ( 营c 彳) 式( 1 8 ) 概念格是所有形式概念在子概念和超概念下的序列。因此，概念格可以图形 化表示为其所对应的h a s s e 图。这使得给定数据背景的概念格构变得清晰和易于 理解，从而实现了概念格的可视化的显示，有利于给用户提供直观的图形的推荐 和信息交互。 北京邮电大学硕士学位论文 labcde 1 1 o o l o g - 一 o l 1 0 1 办f l g3 4 5 1o 1o 1o o1 o1 1oo 1oo o1o 1oo ool 1o o1 o1 10 oo 图1 - 1 一个形式背景的例子 o 嘲啊掣 图1 - 2 基于形式背景的h a s s e 图 图1 1 和图1 2 是一个形式背景及其相应的h a s s e 图的例子。图i - 2 中每个 节点都表示着一个概念，节点之间的边代表着概念之间的有序关系。h a s s e 图中 的每个概念都由外延和内涵组成；概念的外延由其所有子概念上标识的对象组 成；概念的内涵由其所有超概念上标识的属性组成。 对于某形式背景的任何两个形式概念( 4 ，马) 和( 4 ，垦) ，定义( 4 ，b ) 和 ( 4 ，岛) 的最大公共子概念为： ( 4 ，且) ( 4 ，垦) = ( 4 广、4 ，( 垦u 易) )式( 1 9 ) 北京邮电大学硕士学位论文 定义( 4 ，b i ) 和( 4 ，垦) 的最小公共超概念为： ( 4 ，且) v ( 4 ，b 2 ) = “4u 4 ) 。，墨n 垦)式( 1 - 1 0 ) 通常，将“最小公共超概念 称为上确界，将“最大公共子概念 称为下确 界。并且，每个概念集合都有一个上确界和一个下确界。因此，概念格是一个完 备格。 此外，作为数据分析和知识处理的形式化工具，形式概念分析已经获得了广 泛而成功的应用。在数据挖掘领域，由于形式概念分析以概念格的形式使数据有 机地组织起来，概念节点体现了概念内涵和外延的统一，因此非常适合于用来发 现规则性知识。概念格还被成功地应用于信息检索、知识库组织等诸多领域 7 1 。 g o d i n 等【8 】对使用概念格结构的信息检索进行了实验，并和两种较为传统的检索 方法一在手工建立层次分类系统中导航和使用索引项的布尔查询，做了比较实 验。结果标名，在布尔查询和概念格检索方法之间并没有显著的性能差异；然而 层次分类系统检索的查全率要明显低于其它两种方法。因此得出结论，基于概念 格结构的检索使非常有效的，因为它将主题搜索的良好性能和浏览的潜力结合在 了一起。 1 4 3 文本特征选择算法 文本特征选择的过程即是文档标引的过程，选择合适的词汇描述文档，不仅 可以让计算机更好的理解这些非结构化的文本资源，而且最终能够使信息检索平 台为用户提供更加精准的检索结果。 目前基于关键字匹配的搜索引擎技术并不是十分完善，其原因一方面是由于 用户无法准确描述所需信息；另一方面，由于不同的词可以来表达同一个概念， 同一个词在不同的语义环境中可以表示不同的语义，所以关键词标引和检索方式 既容易脱离文档的语义内容，也容易脱离用户的领域知识和背景。当前主流的搜 索引擎所应用的文档索引方法，只是从词的角度来表示一篇文档，没有做到语义 标引和概念表示，使得计算机没有从人的角度去理解和掌握文档含义。对于这些 非结构化的文本，只有通过文本挖掘技术，才能更充分地利用信息资源。 文本特征空间的高维性，使得文本特征选择过程不可避免地要进行大量的运 算，但由实际经验可知，文档集合中并非所有词条都具有代表文档主题的作用； 众多词条中，代表文档语义信息的功能强弱也均不相同。我们必须找出语义信息 强、具有类别区分度的词条，滤除那些不具备语义信息或类别区分度较低的词， 从而减轻后续文档挖掘的运算量。最终目的是在保证特征选择质量的同时，大幅 北京邮电大学硕士学位论文 度提高运算的效率。 基于概念格的检索查询扩展系统中的文本概念抽取正式要借鉴文本特征选 择的思路，从概念的角度去标引文档，从概念间包含与被包含的关系来建立文档 间的联系。文本特征选择算法是本文重点学习和研究的理论基础，关于此方面的 具体描述将在第三章中给出。 1 5 本文的研究重点 由于传统的信息检索工具存在查询词“表达差异修等诸多问题，本文在现有 的理论知识基础上，针对查询扩展问题，提出了一种基于概念格的检索查询扩展 的方法，并将其中的文本概念挖掘作为研究重点。本文的主要研究内容如下： 1 基础理论的研究 基于概念格的检索查询扩展系统的设计与实现依靠现有理论知识的支撑，其 中包括信息检索模型、形式概念分析和文本特征选择算法。对于这些理论知识的 学习和研究是发现问题和解决问题的必须前提。作为基于概念格的检索查询扩展 系统理论支撑，本文也对这些重要的理论知识做了简单的阐述。 2 基于概念格的检索查询扩展系统的设计 在信息检索模型和形式概念分析理论的基础上，参考概念格在信息检索中的 应用实例，完善了基于概念格的检索查询扩展系统的设计思路，并对系统总体结 构进行了设计。 3 检索查询扩展系统中文本概念的挖掘 深入研究文本特征选择的多种算法，针对概念格查询扩展系统的需求，提出 了一种基于熵的特征权值评估函数，这种评估方法的效果和c h i 统计的效果相 当，但其计算量却相比小得多，适应了检索系统中的性能要求：其次，引入了领 域词典的概念，进一步提高了特征选择的效果；此外，特征权值评估函数中还考 虑了w e b 文档结构的隐含信息，精细化了传统的文档词频。 1 6 论文的结构框架 本论文由五章组成： 第一章绪论 对当前互联网信息膨胀的背景和检索工具的缺陷做了初步分析，在信息检索 模型、形式概念分析，以及文本特征选择算法的理论基础上提出了本文的研究目 北京邮电大学硕士学位论文 标和研究重点，并对本文的研究对象和主要内容进行了界定。 第二章基于概念格的检索查询扩展系统的设计与实现 根据信息检索模型以及概念格的理论知识，描述了基于概念格的检索查询扩 展系统的设计思路、系统模型的总体设计，以及其中一些模块的流程设计图。最 后并给出了该查询扩展系统的效果展示图。 第三章文本预处理技术 介绍了文本特征选择的一些关键技术，包括文本表示方法、中文分词技术、 多文档特征选择和单文档特征选择技术。为第四章的特征选择模块的设计奠定了 理论基础。 第四章基于概念格的文本概念抽取系统的设计与实现 在文本预处理的理论基础上，对基于概念格的检索查询扩展系统中的文本特 征选择模块进行了设计和实现。详细描述了中文分词过程和特征权值计算公式选 择与改进，最后对特征模块进行了实验和效果评估。 第五章总结与展望 对课题研究进行了全面的总结，提出了局限性和下一步研究方向。 论文的总体框架： 北京邮电大学硕士学位论文 展系统中概念挖掘模块的 设计与实现 结论与展望 领域背景信息的应用 w e b 文本结构信息的引入 实验对比与效果评估 图1 - 3 论文总体框架图 1 2 北京邮电大学硕士学位论文 第二章基于概念格的检索查询扩展系统的设计与实现 2 1 引言 基于概念格的信息检索查询扩展系统是针对信息检索中存在的查询词“表达 差异问题，提出的一种基于概念的查询扩展方法【9 1 。一方面在初步检索的结果 文档中进行概念挖掘和概念格的建立，为用户提供不同概念方向的查询扩展选 择；另一方面引入概念图作为查询导航，更加直观地表达查询串与各概念节点的 关系，供用户手动调节查询中心词进行查询扩展，以达到查询优化的目的。本章 将简单介绍一下基于概念格的检索查询扩展系统的设计思路和大体框架。 2 2 基于概念格的检索查询扩展 查询扩展解决短查询和词的不匹配问题的一种方案，传统的查询扩展方法主 要分为全局分析方法和局部分析方法【1 0 1 。 全局分析方法的基本思想是对全部文档中的词或词组进行相关性分析，计算 每对词或词组间的关联程度【l 。当一个新的查询到来时，则根据预先计算的词间 相关关系，将与查询用词关联程度较高的词及词组加入原查询以生成新的查询。 主要的技术有聚类算法、潜在语义索引、相似性词典等【1 2 1 。这种方法可以最大限 度地挖掘词间关系，并在词间关系词典建立之后以较高的效率进行查询扩展。但 当文档集合非常大时，建立全局的词间关系词典在时间和空间上往往是不可行 的，并且在文档集合改交后的更新代价也非常之大，不具备灵活的可扩展性和切 实可行的可维护性【1 3 1 。 局部分析利用两次查询的方法解决查询扩展问题。局部分析的思想是将初次 查询的前n 篇文章认为是相关文章，并以此为依据对查询进行扩展。局部分析 主要技术有局部聚类、相关反馈和局部反馈等，相对于全局分析，局部分析的计 算量比较小。这种方法在目前的应用最为广泛，并在一些实际的信息检索系统中 得以应用。但是，当初次查询后排在前面的文档与原查询相关度不大时，局部分 析会把大量无关的词加入查询，从而越来越偏离用户的查询初衷，严重降低了查 北京邮电大学硕士学位论文 询精度【1 4 l 。 基于概念格的检索查询扩展系统，是以概念为基础，以初始查询串为中心， 并结合用户的主观调节，给用户提供全面而清晰的查询扩展方向，引导用户正确 表达查询串以便进一步细化检索需求，充分提高了查全率及查准率并改善了检索 效果和用户体验。 系统利用由初始查询串和一般的检索平台得到初步的检索结果；之后对这些 检索结果文档集合进行解析和语义挖掘，提取出文本中的概念；并根据文本所含 概念间的逻辑关系建立文档与文档问的联系；最后以概念格h a s s e 图的形式将查 询扩展的方案提供给用户；h a s s e 图的中心即是初始查询串，与中心点相连接的 若干概念节点便是系统提供给用户的查询扩展方向；用户可根据自己的查询需 求，选择与初衷较为贴近的扩展方向，以便准确的表达自己的需求并获取较高准 确率的检索结果。 2 2 1 设计思路 基于概念的查询扩展方法的基本思想是：在用户初始查询的基础上抽取概念 来建立用户查询空间，以保证加入的扩展词不在局限于相似度高或者同时出现频 率高的词；同时为了给用户提供更加全面和清晰的扩展方向，提出了概念图的思 想，由用户主动选择扩展方向，选择进一步查询所使用的查询串，用户手工扩展 的查询串是一个概念串，这个概念串同时包含关联词和区分词的思想，为精确查 询打下基础。 基于概念格的检索系统将给用户提供两部分的结果：第一部分是与当前流行 搜索引擎风格类似的经过排序的链接记录，第二是概念格可视化部分，概念格的 可视化将给用户带来更加直观的候选查询词推荐，这些候选词按照“概念 聚 类，能够帮助用户确定精确的q u e r y ，并返回更加符合用户需求的检索结果。下 面分别以两种结果为主线，说明系统的设计思路。 1 传统检索结果的流程设计 图2 - 1 传统检索结果流程 接收用户q u e r y 后，i rm a t c h 模块在文档库中找到相关度在一定门限之内的 北京邮电大学硕士学位论文 文档，并根据一定的p a g er a n k 算法，将这些r e t r i e v e dd o c s 进行相关度排序， 最后将排序后的检索结果提供给用户。 2 基于概念格的q u e r y 候选词推荐的流程设计 由搜索引擎得到与q u e r y 相关的文档后，由建格预处理模块对r e t r i e v e dd o c s 进行处理，其详细过程将在系统模型中具体描述。利用预处理模块的输出结果一 一相关文档集的形式背景，以及一定的建格算法，构建概念格。最后以q u e r y c o n c e p t 为中心，将概念格可视化，给用户提供查询扩展的建议。 2 2 2 系统模型 图2 - 2 基于概念格的q u e r y 候选词推荐的流程 综合2 2 1 小节所描述的设计思路，整合两种检索结果及呈现方式，一方面 给用户提供基本的检索结果；另一方面，将以q u e r yc o n c e p t 为中心的概念扩展 关系可视化，提供基于概念的查询扩展方案。 鉴于以上的思路，基于概念格的检索查询扩展系统的总体设计如下： 北京邮电大学硕士学位论文 图2 - 3 基于概念格的查询扩展系统结构 用户通过u s e ri n t e r f a c e 输入最初的查询串q u e r y ，i rm a t c h 模块相当于传统 的检索平台，通过计算q u e r y 与索引库中文档的相关性，提供初步检索结果 r e t r i e v e dd o c s 。p a g er a n k 模块将根据文档与q u e r y 相关度的高低，将r e t r i e v e d d o c s 进行排序，并将最终的排序结果以文字链的方式展现在结果页面上。与此 同时，初步检索结果r e t r i e v e dd o c s 将会送入p r e p r o c e s s o r 模块，为概念格的构 建进行前期处理准备，抽取出文档集中的概念，并将概念抽取结果组织成建格模 块所需的形式。c o n c e p tl a t t i c ec o n s t r u c t i o n 模块得到文档集及相应概念串后，就 可以根据建格算法构建概念关系。随后，c o n c e p tm a t c h i n g 模块将得到q u e r y 经 过q u e r yc o n c e p t 模块处理后的概念，并将q u e r yc o n c e p t 与之前得到的概念关 系进行匹配和定位。最终，c o n c e p tv i s u a l i z a t i o n 模块可以提供以q u e r yc o n c e p t 为中心的概念关系扩展视图。 从功能划分和系统实现的角度，可以将该系统分为三个主要模块：信息检索 模块( i rm o d u l e - - - i n f o r m a t i o nr e t r i e v a l ) 、概念提取模块( c em o d u l e - - c o n c e p t e x t r a a i o n ) 和建格模块( l cm o d u l e - - - l a t t i c ec o n s t r u c t i o n ) 。i rm o d u l e 的作用在于 应用传统的信息检索模型给出与用户q u e r y 最相关的n 个结果文档。该模块的关 键技术在于结果排序( r a n k i n g ) 。c em o d u l e 的作用在于对i rm o d u l e 返回的前n 个结果进行文档净化、中文分词、词性标注和特征选择。其目的是用m 个元素 来表示一篇文档的概念。该模块的关键技术在于特征选择算法。l cm o d u l e 的作 用在于对c em o d u l e 产生的若干元素和文档的关系进行分析，并行程以概念为 节点的概念格。该模块的关键技术在于建格算法的实现。下面将分别介绍这三个 北京邮电大学硕士学位论文 模块的设计思路。 2 2 3 信息检索模块( i rm o d u l e ) 信息检索模块，即是传统的搜索引擎功能模块，用于网页的抓取、预处理、 索引，接受来自查询接口的查询词，进行查询词和网页的相关度计算，并最终给 出按相关度排序的文字链结果。该模块输入是q u e r y ，背景是索引文档库，输出 的是初步检索结果和概念格备选文档。 现有的信息检索平台非常成熟，在这里我们嵌入现有的搜索引擎，比如百度、 谷歌等，来构建自己的信息检索模块，通过整合去重几个搜索引擎的前n 篇文 档得到概念格候选文档集合。 2 2 4 概念抽取模块( c em o d u l e ) 文档概念抽取( c o n