（应用数学专业论文）基于概念格的语义相关度计算及应用.pdf

；- i 南大学硕士研究生学位论文第1 页 摘要 搜索引擎系统作为互联网信息检索工具，其使用率变得越来越高。然而在网 络用户想要精确查找所需的资料的过程中，由于传统的搜索引擎系统大都是基于 关键字匹配的检索技术，使得用户在检索时经常得到大量与查询无关的结果。为 了提高用户对检索系统的满意度，可以通过扩展搜索系统对语义查询和动态查询 的支持来实现。 词语语义相关度反映的是词语之间相互关联的程度。其相关的研究已经广泛 地应用于自然语言处理领域。词语相关度在信息检索中的查询扩展，歧义的消除， 提高信息检索的精度和召回率等都有着重要的实用价值。将语义相关度计算引入 信息检索技术的研究中，正是为了提高检索系统对用户查询信息的语义处理能力， 从而提高检索效率，使系统更具智能性。 本文首先从搜索引擎的现状谈起。分析了现有搜索引擎系统的特点和不足，提 出了改进搜索性能的手段，从而引入智能搜索技术，得出查询扩展在搜索引擎系统 中设计和实现的必要性。 其次介绍了关于语义相关度计算的方法以及其优缺点。目前的相关度计算都 是建立在词语相似度计算的基础上的。语义相似度计算的方法大致可以分为两种： 一种基于世界知识的方法；一种是基于大规模语料库的方法。 最后提出了一种基于概念格的语义相关度计算方法，阐述了该方法的设计流 程及其在f c a 搜索引擎系统中的实现。该方法利用了概念格对信息聚类的特性， 突破了传统方法相关度计算方法的设计思路，拓宽了概念格的应用范围。- 本文主要贡献如下： 1 研究了汉语词语语义相关度及其算法，分析了语义相关度计算的实现及应 用。 2 提出了一种基于概念格的语义相关度计算方法，该方法利用了概念格对知 识进行聚类的结构特点，并通过实验证明，该方法计算相关度是有效的。 3 将该方法应用到f c a 搜索引擎系统中，为该系统提供了查询扩展功能支 持。 关键词：概念格，语义相关，搜索引擎，查询扩展 第l i 页河南大学硕士研究生学位论文 a b s 仃a c t s e a r c he n g i n es y s t e m ，a sa l li n t e r a c ti n f o r m a t i o nr e t r i e v a lt o o l ，o fw h i c ht h e u t i l i z a t i o nr a t ei sg e t t i n gh i g h e ra n dh i g h e r h o w e v e r , i nt h ep r o c e s so fg e t t i n ga c c u r a t e i n f o r m a t i o n , u s u a l l yt h ev a s ta m o u n t so fu n r e l a t e dr e s u l t sa r es e a r c h e df o rt h eu s e r s ， s i n c et h et r a d i t i o n a ls e a r c he n g i n es y s t e m sa r ea l lb a s e d0 1 1k e y w o r dm a t c h i n gs e a r c h t e c h n o l o g y t oe n h a n c eu s e r s s a t i s f a c t i o nt o w a r d st h er e t r i e v a ls y s t e m ，t h ee x p a n s i o n o f s e m a n t i c q u e r ya n d t h es u p p o r t o f d y n a m i cq u c r y i s t o b ea c h i e v e d i n t h es y s t e m s e m a n t i cr e l a t i v i t yr e f l e c t st h ei n t e r c o n n e c t e 血e s sd e g r e e so ft w ow o r 出t h e r e l a t e dr e s e a r c hh a sb e e nw i d e l ya p p l i e di nt h ef i e l do f n a t u r a ll a n g u a g ep r o c e s s i n g t h e a p p l i c a t i o n so fs e m a n t i cr e l a t i v i t yc a l c u l a t i o nh a v e a ni m p o r t a n t p r a c t i c a lv a l u ei nm a n y f i e l d s s u c ha s i n f o r m a t i o nr e t r i e v a lq u e r ye x p a n s i o n ，t h ee l i m i n a t i o no fa m b i g u i t y , i m p r o v i n gi n f o r m a t i o nr e t r i e v a lp r e c i s i o na n dr e c a l lr a t e se t c i t su s a g ei nt h er e s e a r c h o fi rs y s t e m sc a l lr a i s et h es e m a n t i ci n f o r m a t i o np r o c e s s i n gc a p a b i l i t yt ot h eq u e r y , t h e r e b yi tw i l li m p r o v et h ee f f i c i e n c yo f r e t r i e v a l ，a n dm a k et h es y s t e mm o r ei n t e l l i g e n t f i r s t ，t h i sp a p e rd e s c r i b e sc u r r e n ts i t u a t i o n so f s e a r c he n g i n e s ，a n a l y z e st h ef e a t u r e s a n ds h o r t c o m i n g so fe x i s t i n gs e a r c he n g i n es y s t e m s ，a n dp r e s e n t st m p r o v m gm e t h o d s i n t r o d u c e di n t e l l i g e n ts e a r c ht e c h n e l e g y , w ek n o wt h a tt h ed e s i g na n di m p l e m e n t a t i o n o f q u e r ye x p a n s i o ni nt h es e a r c he n g i n es y s t e mi sn e c e s s a r y ， s e c o n d t h i sp a p e ri n t r o d u c e ss e m a n t i cr e l a t i v i t yc a l c u l a t i o nm e t h o d sa sw e l la st h e a d v a n t a g e sa n dd i s a d v a n t a g e so f t h e m a tp r e s e n t t h er e l a t i v i t yc a l c u l a t i o ni sb a s e d o n t h em e t h o d so f w o r ds i m i l a r i t yc a l c u l a t i o n s e m a n t i cs i m i l a r i t yc a l c u l a t i o nm e t h o d sc a l l b er o u g h l yd i v i d e di n t ot w oc a t e g o r i e s ：aw o r l dk n o w l e d g e b a s e dm e t h o c t , t h eo t h e ri s t h em e t h o db a s e do nl a r g e s c a l ec o r p u s l a s t as e m a n t i cr e l a t i v i t yc a l c u l a t i o nm e t h o db a s e do nc o n c e p tl a r t i c ei sp r o p o s e d t h i sp a p e rd e s c r i b e st h ei m p l e m e n t a t i o np r o c e s sa n dd e s i g no ft h em e t h o di nt h ef c a s e a r c he n g i n es y s t e m t h i sm e t h o db r e a k st h r o u g ht h et r a d i t i o n a ld e s i g ni d e a s ，f o rt h e u s a g eo fi n f o r m a t i o nc l u s t e r i n go fc o n c e p tl a t t i c ec h a r a c t e r i s t i c s a n di ta l s ob r o a d e n s t h ea p p l i c a t i o no f c o n c e p tl a r i c e s t h ec o n t r i b u t i o n so f t h i sp a d e l a r ea sf o l l o w s ： 1 r e s e a r c h i n gs e m a n t i cr e l a t i v i t y c a l c u l a t i o no fc h i n e s ew o r d sa n dr e l a t e d a l g o r i t h m s ，a n a l y z i n g t h ei m p l e m e n t a t i o na n d a p p l i c a t i o n o ft h e r e l a t i v i t y c a l c u l a t i o n 2 p r o p o s i n gas e m a n t i cr e l a t i v i t yc a l c u l a t i o nm e t h o db a s e do nc o n c e p tl a t t i c e ，m w h i c hk n o w l e d g ec l u s t e r i n gs t r u c t u r ei su s e d t h em e t h o di sp r o v e dt o b e p r a c t i c a b l et h r o u g ht h ee x p e r i m e n t s 3 a p p l y i n gi n t h ef c as e a r c he n g i n es y s t e m ，t h em e t h o dp r o v i d e sq u e r y e x p a n s i o nf u n c t i o nf o rt h es y s t e m k e yw o r d s ：c o n c e p ti a t t i c e ；s e m a n t i cr e l a t i v i t y ；s e a r c he n g i n e ；q u e r ye x p a n s t o n 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成酌，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢酌地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构酌学住或证书而 段保存、汇编学位论文( 纸质克本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名： - 勉每 2 0 学位论文指导教师签名 2 0d 7 年6 月 j a 河南大学硕士研究生学位论文第1 页 第1 章绪论 随着i n t c r n c t 这个信息平台在人们的日常生活和工作中发挥着越来越重要的作 用，作为互联网信息检索工具的搜索引擎系统的使用率变得越来越高。然而，伴 随着互联网信息爆炸性的发展，普通网络用户想要精要精确找到所需的资料简直 如同大海捞针。为了很好地满足用户的需求，必须对传统搜索引擎技术做比较大 的改进。所以，在新一代搜索引擎的研究中采用了许多新的检索技术，一些其它 相关领域的研究成果也被引入到检索技术的改进当中。本章主要介绍了搜索引擎 的现状和不足，以及语义相关度计算研究现状，提出用相关度计算支持搜索引擎 的语义处理。 1 1 搜索引擎的技术现状及发展趋势 1 1 1 搜索引擎的技术现状 在互联网络日益渗入我们日常生活的今天，海量的贮存和科学的搜索是人们 信息行为中两样最重要的能力。搜索引擎以一定的策略在互联网中搜集、发现信 息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信 息导航的目的。目前互联网上的搜索引擎大体可以分为两大类：目录式搜索引擎 以及基于关键词的搜索引擎。 1 目录式搜索引擎 目录式搜索引擎的工作原理 目录式搜索引擎的数据库建立在人工编辑的基础上，由专业人员对网上信息 进行选择、标引、分类，合理地将不同学科、专业、行业或区域的网络信息，按 照分类或主题目录的形式组织起来，编制成为等级式的主题指南或主题目录，供 用户浏览和寻找感兴趣的信息内容。 目录式搜索引擎的典型代表y a h o o y a h o o 的信息组织方式具有以下特点：完备分类体系，归纳网上信息。它将 传统的分类思想移植于网上信息的组织，在此思想的指导下，结合网络信息源的 特点，构筑类目体系。在1 4 个基本大类之下又以拥有信息的多寡及知识组织的需 要程度，将每一基本大类细分成不同层次的次类目。层次越深，主题越专指，从 而形成了一个由类目、子类目构成的可供浏览的相当详尽的目录等级结构，为网 第2 页河南大学硕士研究生学位论文 上丰富的信息资源归类，特别是确切归类提供了保障。 以人工方式为主，保证加工质量。采用分面分析原理，由信息专家编制主题 目录，将人的智力投入到信息的选择与加工过程中，从而保证了目录编制的质量。 同时，以人工为主，对提交的网页按主题目录进行筛选、归类和组织，克服了单 纯由搜索软件自动分类所带来的缺陷，增强了分类的合理性，提高了检索的准确 性。 目录式搜索引擎的不足 覆盖率有限：网络信息增长迅速，使得采集信息的速度远远跟不上信息增长 的速度，更不用说编制主题索引的速度了；分类困难：不同搜索引擎的体系结构 不同，分类体系的建立缺乏统一的标准，使得同一内容的信息在不同搜索引擎中 经常会被归入不同类目，造成用户的困扰；成本高，时效差。随着网络应用技术 的发展，用户不再满足于这种对网站分类和摘要的简单查找，更希望对内容进行 查找，于是就出现了基于关键词查询的搜索引擎。 2 基于关键词的搜索引擎 目前互联网上的搜索引擎大多数都采用了基于关键词的查询技术，其典型代 表为g o o g l e 和百度，内容可以覆盖互联网上的绝大多数网页内容。基于关键词的 搜索引擎一般由搜索器、索引器、检索器和用户接口等四个部分组成。 基于关键词的搜索引擎的排序算法 基于关键词的搜索引擎通过程序收集并索引的信息资源量极其庞大，而用户 的提问式却大多由几个词组成，这种情况会导致数量庞大的检索结果，用户需要 花费巨大的精力进行浏览筛选。搜索引擎采用的排序算法包括以下几种：基于词 频统计的排序算法。早期很多搜索引擎采用的排序算法是基于词频统计的，词权 的计算一般把该词在h t m l 网页中出现的位置考虑进来，例如在标题中出现的词 比在正文中的词权值高。但是由于网络资源的数量巨大，词频相同的两个网页质 量却可能相差很远，因此这种算法的局限性很明显。 基于超链分析的排序算法 传统情报检索理论中的引文分析方法是确定学术文献权威性的重要方法之 一，即根据引文的数量来确定文献的权威性。g o o g l e 所采用的p a g e g a n k 即借鉴了 这一思想。p a g e r a n k 的发明者对网络超链接结构和文献引文机制的相似性进行了 研究，把引文分析思想借鉴到网络文档重要性的计算中来，利用网络自身的超链 接结构给所有的网页确定一个重要性的等级数，以此来帮助实现排序算法的优化。 但它存在着偏重旧网页和偏重综合站点的缺陷。 基于关键词的搜索引擎的不足 明显的不足表现为：结果多，相关性低；更新慢；对自然语言理解能力差； 河南大学硕士研究生学位论文第3 页 不支持个性化查询；对多媒体内容的检索尚不成熟。 1 1 2 搜索引擎的发展趋势 专家认为，搜索引擎技术未来的发展趋势将主要包括以下几个方面： 1 自然语言理解技术 从计算机科学特别是从人工智能的观点看，自然语言理解的任务是建立一种 计算机模型，这种计算机模型能够给出像人那样理解、分析并回答自然语言。以 自然语言理解技术为基础的新一代搜索引擎，被称之为智能搜索引擎。由于它将 信息检索从目前基于关键词层面提高到基于知识( 或概念) 层面，对知识有一定 的理解与处理能力，能够实现分词技术、同义词技术、概念搜索、短语识别以及 机器翻译技术等。因此，这种搜索引擎具有信息服务的智能化、人性化特征，允 许网民采用自然语言进行信息的检索，真正使搜索更方便、更确切。 2 p 2 p 对等网络 p 2 p 所包含的技术是使联网电脑能够进行数据交换，但数据是存储在每台电脑 里，而不是存储在既昂贵又容易受到攻击的服务器里。网络成员可以在网络数据 库里自由搜索、更新、回答和传送数据。所有人都共享了他们认为最有价值的东 西，这将使互联网上信息的价值得到极大地提升。 3 多媒体搜索引擎 随着宽带技术的发展，未来的互联网是多媒体数据的时代。开发出可查寻图 像、声音、图片和电影的搜索引擎是一个新的方向。 对于搜索引擎系统用户的一个特定查询，语义理解显得尤为重要。自然语言 理解的引入，可以弥补传统搜索系统中关键词匹配技术的不足，使用户的查询变 得更为明确，使得搜索结果更加符合用户的需要。基于这样的考虑，我们希望设 计出一种搜索引擎系统的模型。通过形式概念分析的应用，使该系统增加对查询 关键词的语义处理能力，从而使系统更具有智能性。 1 2 词语语义相关度计算 语义相关度反映的是文本或者词汇之间相互关联的程度。语义相关度的计算 可以应用于信息检索、句法消歧、文本分类、文本聚类等领域。在信息检索中， 语义相关度更多地是要反映的是文本或者用户查询在意义上的符合程度或者相互 关联程度。 第4 页河南大学硕士研究生学位论文 1 2 1 语义相关度计算方法 目前，词语语义相关度计算的研究都是建立在语义相似度计算的基础上【l 】。 词语相关度和词语相似度是有区别的。例如“医生”和“疾病”两个词语，其相似 度非常低，而相关度却很高。可以这么认为，词语相似性反映的是词语之间的聚 合特点，而词语相关性反映的是词语之间的组合特点。不过在应用当中，语义相 关度计算方法的研究大都借鉴了语义相似度计算方法。 语义相似度计算有两种常见的方法1 2 一】： 1 根据世界知识计算的方法 根据世界知识( o n t o l o g y ) 计算的方法需要计算词语语义距离，语义距离反映 的是词语之间相关度的大小。一般是利用一部同义词词典( t h e s a u r u s ) 。一般同义 词词典都是将所有的词组织在一棵或凡棵树状的层次结构中。我们知道，在一棵 树形图中，任何两个结点之间有且只有一条路径。于是，这条路径的长度就可以 作为这两个概念的语义距离的一种度量。 王斌【4 】采用这种方法利用同义词词林来计算汉语词语之间的相关度。有些 研究者考虑的情况更复杂，a g i r r e & r i g a u 5 1 在利w o r d n e t 计算词语的语义相关度 时，除了结点间的路径长度外，还考虑到了其他的一些因素。 2 大规模语料库统计的方法 以大规模的语料库为基础，用统计的方法计算词语之间的语义相关度。例如， 利用词语的相关性来计算词语的相关度。事先选择一组特征词，然后计算这一组 特征词与每一个词的相关性( 一般用这组词在实际的大规模语料中在该词的上下 文中出现的频率来度量) ，于是，对于每一个词都可以得到一个相关性的特征词向 量，然后利用这些向量之间的相关度( 一般用向量的夹角余弦来计算) 作为这两 个词的相关度。这种做法的假设是，凡是语义相近的词，他们的上下文也应该相 似。 李涓子 6 1 利用这种思想来实现语义的自动排歧；鲁松 7 1 研究了如何利用词语的 相关性来计算词语的相关度。d a g a n l 8 】使用了更为复杂的概率模型来计算词语的距 离。 1 2 1 语义相关度计算方法的优缺点 基于世界知识的方法简单有效，也比较直观、易于理解，但这种方法得到的 结果受人的主观意识影响较大，有时并不能准确反映客观事实。另外，这种方法 比较准确地反欢了词语之间语义方面的相关性和差异，而对于词语之间的句法和 语用特点考虑得比较少。 河南大学硕士研究生学位论文第5 页 基于语料库的方法比较客观，综合反映了词语在句法、语义、语用等方面的 相似性和差异。但是，这种方法比较依赖于训练所用的语料库，计算量大，计算 方法复杂，另外，受数据稀疏和数据噪声的干扰较大，有时会出现明显的错误 通过对语义相关度计算方法的研究，我们提出一种基于概念格的语义相关度 计算方法。该方法跳出了传统方法的思维定式，在一定程度上突破了传统方法的 局限，并能够为搜索引擎系统提供一定的语义处理支持，从而支持用户的查询扩 展。 1 3 课题来源及结构安排 1 3 1 课题来源 面对如今浩如烟海的各种信息，以往的搜索引擎系统表现出了不足。由于传 统的搜索引擎系统大都是基于关键字匹配的检索技术，使得用户在检索时经常得 到大量与查询无关的结果。为了用户对检索系统的满意度，可以通过扩展搜索系 统对语义查询和动态查询的支持来实现。将语义相关度计算引入信息检索技术的 研究中，正是为了提高检索系统对用户查询信息的语义处理能力，从而提高检索 效率，使系统更具智能性。 本文的课题来源于 f c a 搜索引擎系统”。该项目的目的是建立一个基于f c a 的搜索引擎原型模型，通过形式概念分析理论的引入，增加对搜索结果的聚类以 及对查询关键词的语义处理能力，从而弥补现有搜索引擎系统的某些不足。 在本系统中存在着两种数据实体：其中在搜索模块中，以搜索结果文档作为 对象，文档所包含的关键词为属性，对象和属性共同构成文档数据实体；在语义 处理模块中，以关键词作为对象，关键词所包含的义原为属性，对象和属性构成 关键词数据实体。 系统的工作原理是：首先，由数据源生成相应的数据实体，通过系统对数据 源的自动提取处理以及领域专家的帮助，分别得到两种数据实体，数据实体组织 成形式背景的形式：其次，由数据实体得到相对应的数据视图，系统将根据形式 背景生成相应的概念格并进行保存；最后，由数据视图建立最终的用户视图，系 统通过计算、组织等处理生成最终的用户界面，方便用户进行选择、浏览。 f c a 搜索引擎系统在支持关键词搜索的基础上，增加了对查询关键词的语义 理解以及对搜索结果的聚类。该系统是我们对搜索引擎发展以及f c a 应用的一种 探讨和研究。本文要解决的核心问题是，建立基于概念格的语义相关度计算模型 第6 页河南大学硕士研究生学位论文 以及利用该模型支持f c a 搜索引擎系统对关键词的语义理解，从而最终是系统具 有对查询关键词的扩展查询能力。 1 3 2 本文的结构安排 本文将围绕着基于概念格的语义相关度计算方法及其在f c a 搜索引擎系统中 的设计这两个核心内容展开论述。其结构安排如下： 第l 章，从搜索引擎的现状谈起，分析了现有搜索引擎系统的特点和不足，提出 了改进搜索性能的手段，从而引入智能搜索技术，得出语义相关搜索在搜索引擎系 统中设计和实现的必要性。介绍了国内外关于语义相关度计算的方法以及其优缺 点，弓i 出基于概念格的语义相关度计算方法。 ， 第2 章，介绍了计算方法实现所涉及到的部分形式概念分析的理论基础和实际 应用。 第3 章，阐述了用形式概念分析的理论来实现语义相关度计算的方法，并通过与 其他相关度计算方法的比较，证明该方法的可行性。 第4 章，介绍了基于概念格的语义相关度计算在搜索引擎系统中的具体实现以 及所涉及到的相关技术。 第5 章，简单介绍了f c a 搜索引擎系统的各模块的功能，展示了部分搜索结果。 最后是全文的总结，对本文所做的工作进行简单回顾，并探讨和展望了在以 后工作中需要完善的问题。 河南大学硕士研究生学位论文第7 页 第2 章概念格基础 概念格从提出至今已经发展了近2 0 年的时间，目前已经应用于许多领域。本 章首先围绕着概念格这一核心内容展开论述，介绍了形式概念分析中的一些基础 理论，为语义相关度计算方法的设计作一下理论铺垫；其次，介绍了概念格的一 些应用成果。 2 1 引言 概念是人类进行知识表达的一种手段。在哲学中，概念被认为是由外延和内 涵两部分构成。基于这样的理解，德国的w i l l e r 教授在1 9 8 2 年 9 1 提出了形式概念分 析理论，用于概念的发现、排序和显示。 形式概念分析中的概念是对哲学中概念的一种数学表示，是对人们认知的知 识的一种数学化描述。在形式概念分析中，概念的外延被理解为属于这个概念的 所有对象的集合，而内涵则被认为是所有这些对象所共有的特征或属性集，这实 现了对概念的哲学理解的形式化。所有的概念连同它们之间的泛化例化关系则构 成一个概念格。概念格的数学基础是序论和格论。概念格结构模型是形式概念分 析理论中的核心数据结构，它本质上描述了对象和特征之间的联系表明了概念之 间的泛化与例化关系。概念格对应的h a s s e 图则实现了对数据的可视化。 。形式概念分析的研究主要涉及四个方面：基础理论的研究、概念格生成方法 的研究、概念格的可视化以及概念格的应用研究。形式概念分析作为一种形式化 的数学方法，和人工智能、数据库技术、软件工程等其它领域的计算机科学有着 紧密的联系，但同时又相对独立。目前，形式概念分析理论已经成功地应用于软 件工程、数据挖掘、信息检索等多个领域。 2 2 概念格的相关定义 2 2 1 概念格的数学基础 概念格的数学基础是序论和格语。概念格首先是一个格，它必须要满足格的 第8 页河南大学硕士研究生学位论文 定义和关系运算。 定义2 1 设( 一，) 是一个偏序集，如果a 中任意两个元素都有最小上界和最 大下界，则称( 。) 为格。 定义2 2 设( 丘) 是一个格，如果在4 上定义两个二元运算v 和a ，使得对 于任意的口，b o a ，a v b 等于瘌6 的最小上界，a a b 等于口和b 的最大下界，那么，就 称( 彳。v ， ) 为由格( 4 ，) 所诱导的代数系统。二元运算v 和a 分剐称为并运算和 交运算。 通常用a v b 来代替s u p ( a , 6 ) ，黼代替i n f ( a , ) 。类似地分别用和 b 来代替s u p ( b ) 和i n f ( b ) 。 定义2 3 设( 一，) 是一个偏序集如果对于任意非空的集合踺d ，都存在有v s ， 则( 彳，) 被称为是一个完全并半格。类似地，如果对于任意非空的集合s 崮都存 在有心，则( 4 ，蔓) 被称为是一个完全交半格。如果( a ，) 既是完全并半格，也是 完全交半格，则它是一个完全格。 2 2 ，2 形式概念分析基础 概念格是形式概念分析中的核心问题，而形式背景是其研究的出发点。我们 首先介绍形式背景的相关定义。 定义2 4 t 1 川一个形式背景肥= ( g m ，) 由集合g 、胞 及它们之间的关系，组 成，g 的元素称为对象( o b j e c t s ) ，枷g 元素称为属性( a t t r i b u t e s ) ，描述一个对象g 和 个属性r f l 之间的二元关系j ，可以写g 加或电m ) 厶表示“对象g 有属性聊”。 一个形式背景实际上表示的是对象集和属性集之间的二元关系，所以可以用 个交叉表来表示。表中各行用对象名标识，各列用属性名标识。g 行与i n 列的 交叉点表示对象“g 具有属性脚”。表2 一l 表示的是某个形式背景。 hdf h 1 110o0o1 o0 2l l00oo1 l 0 31 1 1o 00ll0 4 l0100 o1l1 5l lololo o0 6 l 1 l l01o00 7 1olll o000 8 l0ll0 。 l o 00 河南大学硕士研究生学位论文第9 页 定义2 5 t 1 0 1 形式背景( g m d 中的一个形式概念是一个对“，口) ，其中 a c _ g ，b l 以满足：47 = b 且b7 i 4 。a 、b 分别称为形式概念( 4 ，b ) 的外 延( e x t e n t ) 和内涵( i n t e n t ) 。b ( g ，m ，) 表示形式背景( g ，md 所有形式概 念的集合。 对于趾两个形式概念，历) 和，岛) ，如果4 l - - a 2 ，则称，局) 是( ，蕾2 ，岛) 的子概念，称0 2 ，历) 是0 1 ，历) 的超概念，记为乜“b 1 ) 乜2 ，历) 。一个概念格就 是由形式背景中的形式概念按照超概念一子概念这样的偏序关系得到一个格结构。 定义2 6 1 加】如果“l b 1 ) 和( a 2 ，b 2 ) 是一个形式背景的两个形式概念，如果 a 1 c _ a 2 ( 等同于岛b 1 ) ，那么o l ，b 1 ) 被称为( a 2 ，b 2 ) 的子概念，( 4 2 ，岛) 被 称为“l ，b 1 ) 的父概念，并且我们记为“l ，b 1 ) s ( 彳2 ，b 2 ) 。关系是形式概念 之间的序。按此方式有序的b ( g ，必d 所有形式概念的集合被表示为默g ，必d ， 即联g m d = ( b ( g ，m d ，匀，并且被称为形式背景取g ，必d 的概念格。 子概念父概念关系是b ( g m d 上的偏序关系，因为它满足自反性、反对称性 和传递性。通过这个关系，我们得到一个偏序集联g m d = ( b ( g ，必d ，匀，因为 对于b ( g md 任意非空子集s ，s 中的任意两个形式概念都有最小上界和最大下 界，所以偏序集垦( g ，m - 0 是一个完全格。 - 定理2 1 【1 川设k = ( g 磊d 为一形式背景，甄的= ( b ( g ，m d ，9 是形式背景k 的概念格，那么联回为一完全格，对于b ( g m - 0 的任意非空子集，其最小上界 s u p a 甄目) 和最大下界i n f t b ( k ) ) 分别为： v ( 互，g ( 蜀) ) = ( g 叭2 五) ) ，厂、g ) ) l 鼍t“。tel ，g 隅) ) = ( n 五，f c g c 2 9 ( x , ) ) ) ) 、 k ， 概念格可以图形化表示为有标号的线 ( 1 a b e l l e dl i n ed i a g r a m ) 。我们称之为 h a s s e 图生成图的方法如下：如果c l c 2 ，且格中没有元素c 3 使得c l c 3 口3 卢4 。后者反映了鼬”l 至l j s i m 4 对于总体相似度所起到的作用依次递减。由于第 一独立义原描述式反映了一个概念最主要的特征，所以应该将其权值定义得比较大， 一般应在0 5 以上。在以上a 、b 、c 的计算中，最后求加权平均时，各部分取相等的权 值。 经过义原语义距离和概念相似度的计算，两个概念之间的语义相似度计算就 完成了。 2 基于向量空间的方法 胡俊峰、俞士汶【2 羽提出了一种用向量空间模型计算相似度的方法，目的是为 诗词内容的信息检索提供语义支持。 根据唐宋诗语料其中绝大多数语句的长度在7 个汉字以内，同时句偶之间常常 存在对仗关系这些特点，采用了如下模型来描写词汇的上下文语境信息。在给定 的语料库口和词表艿中，特定词语x 在口上的语义定义为如下五元组： s ，= 上，r ，c x ，万，q 其中：厶为工的左同现词汇特征向量，熙为工的右同现词汇特征向量，c x 为对仗 词汇特征向量。特征向量的元素为特征词与特征值组成的二元组p ，) 。 玩，： ! 竺竖= ! ! 型2 l o g 夯l o g 痧 其中：氕劝，吵在对应的x 的相对位置上出现的频度( 同一句的左边、右边或对 仗位置上) 。x o , e 艿霹，y 分别是x ，y 在语料库口中出现的频度。 根据上面对词汇语义的统计模型的描述，两个词之间的语义相似度s i m ( x ，力 可以通过计算其在三个不同的词汇特征空间( k ，风，c x ) 中的距离来得到。距离越 小，相似度越大。其相似度计算公式如下： 盛加( z ，y ) = l 七l l 砂+ k 2 a m y + 七，a c x y ) 其中七l 、恕、岛是可以根据语料库实际情况进行调整的加权参数，而向量距离 的计算公式为： 厂一 a x y = 、f ( x k 一啦) 2 3 3 本文的方法 经过对相关度计算的研究发现：无论哪种相关度的计算方法，都是先对词汇 河南大学硕士研究生学位论文第1 7 页 有一个语义上的描述( 如：知网中的义原、向量空间模型中的特征向量) ，然后根 据这些描述计算词汇间的语义相关度。 3 3 1 基本思想 本文的基本思想是，在领域知识和领域专家的辅助下，用一些特征词来描述 领域里的关键词，并通过构造的概念格找出这些关键词之间蕴含的内在联系，从 而最终计算出关键词之间的语义相关度结合概念格的结构特点以及相关度计算 的基本思想，本文提出的相关度计算方法主要设计如下：根据领域知识生成形式 背景，再由形式背景构造概念格，最后根据概念格的层次结构计算对象( 关键词) 之间的语义相关度。基于概念格的语义相关度计算在设计上主要是利用了概念格 对知识聚类的特点。 3 3 2 方法设计 根据基本思想，基于概念格的语义相关度计算方法的设计可以分为以下三个 步骤： 1 形式背景的生成 对于确定的领域知识，可以确定一个相应的形式背景。形式背景生成的关键 是确定其对象集和属性集以及对象和属性间的二元关系。这样，我们首先给出基 于本文方法设计思想的形式背景定义。 定义3 1 一个领域知识的形式背景是一个三元组r g ，) ，其中g 是对象 ( 领域的关键词) 集， 是属性( 特征词) 集，是一个二元关系，它表明关键词 矿是否包含特征词m 的语义特征，如果包含，则记为g l m 或者( g ，m ) ，。 有了形式背景的定义之后，需要实际的去确定三元组c 中的三个集合：统计的 方法得到对象集，即对领域知识的文本信息做统计，从而选出能够表示该领域知 识的关键词，把选出来的关键词作为对象集；选出最能够反映对象集特征的特征 词构成属性集，借鉴本体构建中基于字典构建方法【2 9 】的思想，在一个关键词语义 词典和领域专家的共同作用下，确定其属性集；以1 和0 来表示对象和属性的二元 关系，即如果对象( 关键词) 包含属性( 特征词) 的语义，则用1 来表示厶否则 用0 表示。 例如，对于对象集g ，= 水蛭，鲤科鱼，青蛙，狗，菊科草，芦苇，豆，玉米 和属性集耵= 需要水，生活在水中，生活在陆地，叶绿素，四处移动，有肢，哺 第1 8 页河南大学硕士研究生学位论文 乳 ，我们可以得到如表3 i 的形式背景。 表3 1 形式背景示例 i 需要水生活在水中生活在陆地叶绿素四处移动有肢哺乳 水蛭l10ol00 鲤科鱼ll0ollo 青蛙lllo1lo 狗 1ololll 菊科草 ll0l0o0 芦苇1ll1o0d 且 lol1000 玉米 lol l0 o0 2 概念格的构造 ， 目前，概念格的构造算法可以分为三种：批处理算法，渐进式构造算法以及 并行算法。本文采用的是一种对渐进式g o d i n 算法 3 0 1 的改进算法【3 “。由于该算法的 思想比较成熟而且已经多次应用到概念格构造的应用中，这里就不做更多的叙述。 其相关内容在第4 章有详细论述。概念格的可视化表示为与其相对应的h a s s e 图，例 如由表3 1 构造的概念格如下图： 图3 - 1 概念格的h a s s e 图 3 语义相关度的计算 图3 1 中的路径1 - 2 7 - 1 2 - 1 6 j 2 篚j 形式概念有5 个，其中l = ( 水蛭，鲤科鱼，青 蛙，狗，菊科草，芦苇，豆。玉米) ， 需要水) ) ，2 _ ( 水蛭，鲤科鱼，青蛙，菊 河南大学硕士研究生学位论文第1 9 页 科草，芦苇 ，( 需要水，生活在水中) ) ，7 - ( 水蛭，鲤科鱼，青蛙 ， 需要水， 生活在水中，四处移动 ) ，1 2 = ( 鲤科鱼，青蛙 ， 需要水，生活在水中，四处 移动，有肢 ) ，1 6 = ( 口， 需要水，生活在水中，生活在陆地，叶绿素，四处移 动，有肢，哺乳 ) 。按照超概念子概念之间的关系，5 个形式概念之间的关系为： 1 6 1 2 7 立s l 。不难看出，子概念比它的超概念拥有更多的属性和更少的对象。也 就是说，h a s s e 图中自顶向下，形式概念中包含的对象数逐渐减少，但属性数逐渐 增加。这也就说明了，子概念的对象比其超概念的对象包含了更丰富的语义( 属 性) 。拿形式概念7 和形式概念1 2 为例：1 2 比7 多出“有肢”这个属性，那么就表明 “鲤科鱼”和“青蛙”的关系比它们和“水蛭”之间的关系更近了。 根据以上的论述，我们可以认为：形式概念越靠h 够s e 图的底端，包含在其中 的对象之间的相关度越大；而处在同一层次的形式概念( 可按属性数或者对象数 的多少分层，属性数或对象数相同的形式概念在图中的同一层) ，包含在其中的对 象之间的相关度是相同的。对于如何分层，下面会做详细论述。由此，引出形式 概念相关度和对象之间的相关度的定义如下： 定义3 2 概念格中的形式概念c 的相关度 r e l ( c ) = 坍n ， 其中行为h a s s e 图的层数。m 为形式概念c 所在的层号，朋甩。 定义3 3 对于概念格三，对象9 1 和9 2 之间的相关度 r e l ( g l ，9 2 ) = m a x ( r e l ( c ) ) ， 其中c - 上， g l ，9 2 c e x t ( c ) 。 r e l ( c ) 实际上体现的是形式概念c 中对象之间的相关度。显然，r e l ( c ) 是一个 在0 和1 之间的实数。定义3 3 中的e x t ( c ) 是表示c 中的外延。计算概念格三中的两个 对象g l 和9 2 的相关度r e l ( g l ，9 2 ) ，首先需要计算包含着两个对象的形式概念的相关 度r e l ( c ) ，然后取数值最大的r e l ( c ) 作为这两个对象的相关度。 分层的问题实际上属于h a s s e 图的构图问题，但它对相关度计算的结果起着重 要的影响。经过多次的试验我们发现：按照属性数相同分层，可能导致一些相关 度较高的概念由于其包含的属性数偏少而得到较低的值；按照对象数相同分层， 可能导致一些相关度较高的概念由于包含的对象数偏多而得到较低的值。解决办 法是：分别按属性数相同的方式和对象数相同的方式分层，计算, 9 , r e l a t t ( c ) ( 属性 数分层的结果) 和r e l o b j ( c ) ( 对象数分层的结果) ，把两个值的加权平均数作为形式 概念c 的相关度r e i ( c ) 按属性数分层的权值和按对象数分层的权值分别设为a 和 历其中计= 1 。实际计算中可以适当调节二值的大小以得到更精确的计算结果， 目前舐廊设定为0 5 。 综上所述，计算对象之间的相关度算法描述如下： 第2 0 页河南大学硕士研究生学位论文 算法3 1 ：计算r e l 哂，9 2 ) p r o c e d u r er e l c a l c u l a t e ( l ，自，9 2 ) 输入；概念格工中的对象g l ，9 2 输出：r e l ( g l ，9 9 b e g i n f o rl 中的每个形式概念cd o 计算r c l a t t ( o 计算r e l o b j ( d r c l ( q 七- 毋r e l a t t ( c ) + 伊r e l o b j ( c ) e n d f o r f o rl 中的每个形式概念cd o i f g l ，9 2 同时包含在c 的对象集中t t r e n i f r e l ( g i ，9 2 ) p e l ( c ) t h e n r e b ，9 2 ) 卜p e t ( c ) e n d i f e n d i f e n d f o r e n d 3 3 3 实验与分析 为验证本文提出的语义相关度计算方法的可行性，我们以“计算机硬件”为 领域构建形式背景，其中对象集萨f 金手指，显卡，声卡，显示器，内存，存储器， c a c h ，主存，外