（计算机软件与理论专业论文）案例知识检索算法与应用研究.pdf

摘要 在日常生活中，人们经常需要检索历史经验知识作为解决当前问题的参考。而人类 在认知过程中所积累的经验和方法，大都以非结构化的文本案例形式保存。可见，文本 案例的检索已经成为了信息时代的需求。 本文重点研究文本案例检索算法及其应用，完成的主要工作包括： 1 ) 文本案例的表示。根据文本案例本身的粒度特性，参照信息粒化的过程对文本 案例进行粒化分析，应用粒度计算思想中从不同层次观察问题的策略，结合人类以句子 为单位理解语言的特点，提出用句子向量空间模型对文本案例进行向量化的表示，将表 示粒度从词提高到句子，并加入简单的语义信息。 2 ) 文本案例检索算法的研究。通过对案例检索中粒度原理的分析研究，将案例检 索过程抽象为粒度计算的过程，提出基于句子向量空间模型的文本案例检索算法，经实 验证明该算法可行并改善了检索效果。 3 ) 文本案例检索算法的改进。首先针对文本案例中信息冗余量过大从而影响检索 效率和检索速度的问题，借鉴8 0 2 0 法则提出关键句提取的思想，并应用该思想对检索 算法进行改进，经实验证明改进算法在提高检索速度的同时改善了检索效果；其次在检 索过程中加入领域知识，提出构建领域关键词库的思想，对文本案例检索算法进行再次 改进，经实验证明改进后的算法提高了检索效率。 4 ) 检索速度的提高。由于案例知识库较为庞大，导致检索过程时间消耗大。本文 基于m p i 并行计算平台设计并实现了文本案例检索算法的并行化，提高了检索速度。 5 ) 文本案例知识检索系统的实现。在文本案例检索算法研究的基础上，给出系统 的总体架构和工作流程，对主要功能模块的设计和实现进行详细说明，最终给出系统实 现原型，验证了本文研究的模型和算法的可行性。 关键词：句子向量空间模型，文本案例检索，关键句，领域关键词库，并行计算 a b s t r a c t i nd a i l yl i f e ，p e o p l eo f t e nn e e dt or e t r i e v et h es i m i l a rh i s t o r i c a le x p e r i e n c ea n d k n o w l e d g et ob et h er e f e r e n c eo fs o l v i n gc u r r e n tp r o b l e m s a n dt h ee x p e r i e n c ea n dm e t h o d s i nh u m a nc o g n i t i v ep r o c e s sm o s t l ys a v e da st e x t s o ，t e x t u a lc a s er e t r i e v eh a sb e c o m et h e d e m a n do fi n f o r m a t i o nt i m e s t h i sp a p e rm a i n l ys t u d i e st e x t u a lc a s er e t r i e v ea l g o r i t h m sa n da p p l i c a t i o n s ，t h em a i n w o r k sa r ea sf o l l o w s ： 1 ) t h er e p r e s e n t a t i o no ft e x t u a lc a s e a c c o r d i n gt ot h ep a r t i c l eg r a n u l a r i t yc h a r a c t e r i s t i c s o ft h et e x t u a lc a s e , a n a l y s i st h eg r a n u l a t i o no ft e x t u a lc a s er e f e rt ot h ep r o c e s so fi n f o r m a t i o n g r a n u l a t i o n ，b s ct h es t r a t e g yo fo b s e r v i n gt h ep r o b l e mf r o md i f f e r e n tl e v e l s ，c o m b i n e dw i t h t h ec h a r a c t e r i s t i c so fh u m a nu n d e r s t a n d i n gm o d ew h i c hi su s i n gt h es e n t e n c ea sau n i t ，t h e s e n t e n c ev e c t o rs p a c em o d e li sc a r r i e do u tt oq u a n t i f yt h ee x p r e s s i o no ft e x t u a lc a s e t h e e x p r e s s i o ns i z eo ft e x t u a lc a s ei si n c r e a s e df r o mw o r dt os e n t e n c e ，a n ds i m p l es e m a n t i c i n f o r m a t i o ni sc o n s i d e r e d 2 ) t e x t u a lc a s er e t r i e v ea l g o r i t h m s t h ep r o c e s so ft e x t u a lc a s er e t r i e v ei sa b s t r a c t e da s g r a n u l a rc o m p u t i n gt h r o u g ht h ea n a l y s i so fg r a n u l a r i t yp r i n c i p l ei nt e x t u a lc a s er e t r i e v e ，a n d t h et e x t u a lc a s er e t r i e v ea l g o r i t h m sb a s e do ns e n t e n c ev e c t o rs p a c em o d e li sp r o p o s e d ，w e c o n f i r m e dt h a tt h ea l g o r i t h mi sf e a s i b l ea n di m p r o v i n gt h es e a r c hr e s u l t st h r o u g he x p e r i m e n t 3 i m p r o v e m e n to ft e x t u a lc a s er e t r i e v ea l g o r i t h m s f i r s t , r e d u n d a n c yi nt e x t u a lc a s e i m p a c t st h er e t r i e v a le f f i c i e n c ya n ds p e e d ，s ot h ek e ys e n t e n c e si d e ai sp r o p o s e du s i n gt h e 8 0 2 0r u l ea n du s e dt oi m p r o v et h et e x t u a lc a s er e t r i e v ea l g o r i t h m s ，a n dt h ee x p e r i m e n ts h o w s t h a tt h ea l g o r i t h mi n c r e a s e st h er e t r i e v a ls p e e dw h i l ei m p r o v e st h es e a r c hr e s u l t s s e c o n d ， d o m a i nk n o w l e d g ei sc o n s i d e r e di np r o c e s so ft e x t u a lc a s er e t r i e v e ，t h ei d e ao fc o n s t r u c t i n g t h ed o m a i nk e y w o r d sl i b r a r yi sp r o p o s e d ，t h et e x t u a lc a s er e t r i e v ea l g o r i t h m si si m p r o v e d a g a i n t h ee x p e r i m e n tp r o v e st h a tt h em e t h o d i sf e a s i b l e 4 ) i n c r e a s e ds p e e do fr e t r i e v a l t e x t u a lc a s er e t r i e v a la l g o r i t h mp a r a l l e l i z a t i o ni s p r o p o s e db e c a u s et h ec a s ek n o w l e d g eb a s ei s s ol a r g et h a tt h er e t r i e v a lt a k e st o ol o n gt i m e t h ep a r a l l e lc o m p u t i n gi sr e a l i z e db a s e do nm p ip a r a l l e lc o m p u t i n gp l a t f o r m ，a n di n c r e a s e d s p e e do f r e t r i e v a l 1 1 l 5 ) t h ei m p l e m e n t a t i o no ft e x t u a lc a s er e t r i e v a ls y s t e m b a s e do nt h eo d i t ca c a d e m i c i d e a so ft h i sp a p e ra n dt h ed e s i g ni d e a , w ei n t r o d u c et h eo v e r a l ls t r u c t u r ea n dw o r k f l o w , a n d d e s c r i b et h ed e s i g na n di m p l e m e n t a t i o no fm a i nm o d u l e s a tl a s t ，p r o t o t y p es y s t e mi sg i v e n t ov 耐矽t h em o d e la n da l g o r i t h mp r o p o s e di nt h i sp a p e r k e y w o r d s - s a l t c ev e c t o rs p a c em o d e l ，t e x t u a lc a s er e t r i e v e ，k e ys e n t e n c e ， d o m m nk e y w o r d sl i b r a r y , p a r a l l e lc o m p u t i n g l v 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：参堕丝 眵 一 指导教师签名：丞三二 劢乃年6 月况扫扣年舌月溯 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。据我所知，除了文中特别加以标注和 致谢的地方外，本论文不包含其他人已经发表或撰写过的研究成 果，也不包含为获得西北大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：恕峻弦 2 痧汐年石月z 日 西北大学硕士学位论文 1 1 研究背景 第一章绪论 在实际生活应用中，人们经常需要检索类似的病例、案情、文章等同类或近似主题 的信息，目的是借助已积累的经验知识作为解决当前问题的参考。可见，随着信息技术 的发展，以案例为基础的信息检索要求也已经成为时代的需求 1 】。 人类在认知过程中积累的经验和方法大多是以文档形式来保存的【2 】，因此案例大多 也是以文本形式来表示的，即文本案例。针对如何有效地管理和利用文本案例，提出了 文本案例推_ 理( t e x t u a lc a s e b a s e dr e a s o n i n g ，t c b r ) p j 。 文本案例推理的研究目标【4 】是能够直接、智能化地对用文本描述的案例知识进行处 理。文本案例推理的主体是自然语言表示的文档【5 】。文本案例推理的主要目标并不是解 决问题，而是提取对用户解决问题有帮助的信息。当前较为成功的t c b r 应用是一个在 线问答系统f a l l q ，该系统的推理过程为：由用户提出问题，在案例库中检索与该问 题最为相似的文本案例作为解答，如果用户对解答不满意，可对其进行适当的修正，最 后将该问题以及解决方法作为新的文本案例存入案例库。 文本案例推理的研究从提出到现在已经取得了一定的进展，但是其核心问题，怎样 评价文本案例之间的相似性即文本案例的检索仍然是研究的难点和重点 6 1 。 早期的文本案例检索是基于信息检索技术来研究的【6 】。1 9 9 7 年提出的第一个t c b r 系统( f a q 探测者) 采用基于向量空间模型的标准信息检索技术【6 1 ，将所有文本案例表 示成词向量空间上的多个向量，通过计算向量间的距离得到文本案例间的相似度；但是 向量空间模型忽略词出现的顺序、上下文结构和语义特征，这样既带来了计算和操作上 的方便，同时也损失了大量的文本结构信息，导致计算出来的相似度不是很准确。而当 前较为成功的t c b r 应用( 在线问答系统f a l l q ) 则采用案例检索网 6 】，它将案例知 识库表示为信息实体的节点，通过计算信息实体间的相关度来获得文本案例间的相似 度；该方法结构灵活、效率较高，但是其中信息实体的构建过程存在很多潜在的问题， 如同义词和近义词的表达等，且信息实体与实例本身相关度的设置依赖于人工理解程 度，难免会产生误差。 本文正是针对当前文本案例检索研究中存在的问题，分析并提出了新的文本案例检 索模型和方法。 第一章绪论 1 2 文本案例检索的研究现状 由于信息系统的发展，全球曾经掀起了研究案例知识检索的狂潮1 1 。近年来，随着 文本案例推理的提出，文本案例检索成为了一个新的研究方向。 文本案例检索的过程主要分为特征识别、案例匹配和最佳案例选择 7 1 ，如图1 ： 用户 检索结果反 嚣爱雾算h 最紫择h 检篓 -_p-hm 一 似度计算l l一排序i 【 一 图1 文本案例检索过程图 1 ) 特征识别，指将当前查询的问题用自然语言表示，通过分析、辨识，进而提取 其中主要的信息特征。 2 ) 案例匹配，指根据提取的问题特征，计算查询问题与案例知识库中所有文本案 例的相似度，生成一组候选的文本案例。 3 ) 最佳案例选择，指将所有候选的文本案例按相似度从高到低排序，选取与查询 问题相似度最高的一个或几个文本案例作为检索结果。 目前，文本案例检索是作为文本案例推理的一部分来研究的，尚未见到将其单独作 为研究内容的文献。因此，通过查阅文本案例推理研究方面的相关文献，总结当前文本 案例检索的研究现状如下： 就研究进展而言，国内对文本案例检索的研究还比较少，可检索到的论文和研究成 果都很少，应用也处于初级阶段，这和国外大量的论文、更优化的应用1 1 都存在着一 定的差距。 就研究内容而言，国内外都大致相同，主要是针对文本案例的检索模型和检索方法 的研究。 1 2 1文本案例检索模型的研究现状 当前国内外常用的文本案例检索模型有向量空间模型和案例提取网模型，对其研究 现状总结如下： 1 ) 向量空间模型( v s m ，v e c t o rs p a c em o d a l ) ，由g s a l t o n 等人于1 9 7 5 年提出【1 2 1 ， 该模型假设词与词之间不相关，将文本形式化的表示成多维词空间中的一个向量，具体 用文本中特征词及其权重的向量形式表示，把检索即文本间的相似度计算简化为求词向 2 两北大学硕士学位论文 量空间中两个向量间的距离，通常用向量之间的夹角余弦公式来计算。这样可大大降低 计算的复杂性，而且便于对检索结果进行排序。 向量空间模型优缺点分析。优点：将知识表示向量化；考虑了文本案例中特征词的 权重问题；将复杂的检索过程简化为向量间的夹角余弦值的计算；通过定量分析来进行 案例匹配，便于进行检索结果排序。缺点：忽视词之间的相关性，可能导致检索结果的 可靠性出现问题；而且在向量化的过程中只考虑特征词的出现次数而忽略了特征词的出 现顺序及上下文语义，损失了在自然语言中至关重要的大量文本信息结构，导致检索结 果的准确性降低。 2 ) 案例提取网模型( c r n ，c a s er e t r i e v a ln e t s ) ，由案例节点和信息实体( i e s ) 节 点组成，它们之间通过有权重的弧连接，根据不同的检索问题形成不同的网状结构模型。 c r n 案例检索过程【1 3 】： 将检索问题解析为信息实体的一个子集； 计算c r n 中各i e s 之间的相似度，根据i e s 对应的属性及其值的相似程度来具体 判定，最终得到i e s 的集合m ； 计算检索问题与案例知识库中文本案例的相似度，通过集合m 中各i e s 与相应案 例的相关性来计算； 提取相似度最高的一个或几个文本案例作为检索结果。 c r n 模型优缺点分析1 4 】。优点：可以在不损失效率的情况下，对只包含所给问题 部分信息的案例进行检索；新属性的加入不会对旧的案例产生影响；案例的表示可人为 改变，通过与不同的属性集相关联来实现；i e s 间的相关性也可通过调整相应弧的权重 值而动态改变；检索是通过传播激活而逐渐完成的一个过程。缺点：i e s 间的相关性度 量很难全部在案例知识库初始化的时候完成；激活过程中，全部相关的i e s 都会被逐步 激活包括相关度很低的i e s ，这样会产生效率方面的问题；c r n 构建过程中，i e s 的逐 步激活无时序性；c r n 中i e s 是原子结构，而在实际检索过程中某些i e s 要求进一步细 分。 1 2 2 文本案例检索方法的研究现状 文本案例检索的关键是检索方法，它直接决定着案例检索的准确性、有效性和检索 的效率。目前，国内外常用的文本案例检索方法有三种【7 】：最近邻法( n e a r e s tn e i g h b o r ) 、 归纳索引法( i n d u c ei n d e x i n g ) 、知识导引法( k n o w l e d g eg u i d e d ) ，其研究现状总结如下： 3 第一章绪论 1 ) 最近邻法，通过计算两个文本案例在特征空间中的距离来衡量它们之间的相似 性，距离越小则两文本案例间相似度越大。最近邻法首先要给出文本案例间的距离定义， 根据距离的定义来计算两文本案例间的相似度。常见的距离定义有夹角余弦值，欧式距 离( e u c l i d e a n ) 等。 目前，最近邻法被应用在大多数的文本案例检索中1 5 】，该方法简单有效，缺点是检 索时间会随着案例知识库规模的扩大而线性增长。 2 ) 归纳索引法，通过基于决策树的学习方法来实现，主要过程是不断地从案例中 识别并提取包括能与别的案例作明显区分的案例组成部分的主要特征，根据提取的特征 将案例组织成类似于判别树的层次结构，采用判别树搜索策略进行案例检索。 归纳索引法层次结构清晰，可对案例进行自动客观的分析并提取特征。但是该方法 只适用于特定案例知识库的检索，因为大量的案例归纳过程增加了案例知识库的构建时 间，导致系统开销大，而且当案例知识库中加入新案例时，需要重新归纳学习。 3 ) 知识导引法，是基于知识的检索。通常根据已有的相关案例的知识来引导和确 定当前案例在检索过程中必须的重要特征，并利用该特征完成检索。 知识导引法基于现有的知识，耗时较小，但由于通常要求知识能够代码化且构造知 识的过程较为复杂，所以也存在其局限性，常与其他检索方法结合使用。 具体的文本案例检索策略除上述三种外，常见的还有： 神经网络检索，建立案例知识库的并行分布式神经网络模型，根据用户所给问题搜 索该案例知识库网络； 分类网检索，将案例知识库从概化到特化建立层次结构，检索时从上到下逐层查找 相似度最高的案例； 粗糙集检索，从所给问题的描述集合出发，寻找问题的内在规律，最终实现检索； 基于聚类算法的检索，首先对案例知识库进行聚类分析产生聚类集，接着在聚类集 的基础上对待处理案例进行检索，最后在检索得到的某个聚类上对此待处理案例进行二 次检索得到最相似案例，即为检索结果。 1 3 存在的问题 对文本案例检索的研究现状进行分析，发现当前文本案例检索的研究仍然存在问 题，总结如下： 1 ) 案例知识的表示。案例知识的表示是检索的基础，现有的文本案例大都是基于 4 西北大学硕士学位论文 向量空间模型、用特征词来表示，该方法忽略词序信息、上下文结构和语义，无法贴切 对文本案例进行表示，从而无法对文本案例进行层次化、多方位的分析和处理。 2 ) 检索算法的效率。实际应用中需要精确全面的检索结果，但是现有检索算法由 于文本案例本身存在与主题无关的大量冗余信息，且当前的案例表示方法存在缺陷，导 致设计的算法影响了检索结果的准确度。 3 ) 领域知识的支撑。现有的检索算法大都是通过基于特征词的案例间相似度计算 来完成，没有充分利用领域知识的支撑作用来提高检索效率。 4 ) 检索系统时间和空间的开销。现有检索算法的速度常常随案例知识库容量的扩 增而大幅度下降，而且检索过程中会产生的大量中间结果需要存储，这些对实际应用系 统来说都是难以接受的。 1 4 研究的目标及意义 1 4 1 研究目标 在当前文本案例检索研究的基础上，针对现有的问题和不足，拟从实际应用的需求 出发，对文本案例知识的表示、文本案例检索算法的研究及其改进，文本案例检索速度 的提高和文本案例检索系统的实现进行研究。 具体的研究目标如下： 1 ) 研究文本案例知识的表示，句子向量空间模型。 2 ) 研究文本案例检索的算法，基于句子向量空间模型的文本案例检索算法。 3 ) 研究文本案例检索算法的改进，提取关键句并加入领域知识。 4 ) 研究提高文本案例检索速度，实现并行计算。 5 ) 研究文本案例知识检索系统的实现。 1 4 2 研究意义 随着信息技术的发展，以案例为基础的信息检索要求已经成为人们日常生活的需 求。而人类在认知过程中所积累的经验和方法中，以非结构化的文本形式保存的占很大 比例，可见文本案例的检索已经成为了信息时代的需求。因此，本课题的研究具有社会 意义。 本文研究的文本案例检索面向专业领域，可应用于企业案例知识管理中的某些实际 问题案例的检索。因此，本课题的研究具有实用价值。 5 第一章绪论 本文对文本案例检索的研究在一定程度上解决了当前文本案例检索研究中存在的 部分问题，推进了文本案例检索研究的发展；介于文本案例检索是文本案例推理的核心 步骤，所以也在一定程度上推进了文本案例推理技术研究的发展。 1 5 论文结构安排 全文围绕文本案例检索的关键技术和应用研究展开，分为五章，论文的整体架构如 图2 ： 图2 论文整体架构图 各章具体内容分述如下： 第一章：绪论。首先介绍文本案例检索的研究背景；其次概述当前国内外文本案例 检索的研究现状，主要包括文本案例的检索模型和检索方法；然后总结目前文本案例检 索研究中存在的问题，并针对问题提出了本文的研究目标和意义；最后给出论文的整体 架构图和各章的研究内容。 第二章：相关基础知识。首先介绍本文中文本案例检索的思想方法粒度计算， 包括粒度计算的定义、粒度计算的基本问题和现有的几种粒度计算模型；其次介绍本文 在提高案例检索速度的实现手段并行计算，包括并行计算的定义、当前研究的主要 问题、设计实现、评价标准和现有的并行计算平台。 第三章：句子向量空间模型。首先分析文本案例本身的粒度特性，并参照信息粒化 的过程对文本案例进行粒化；其次基于上述分析，应用粒度思想中从不同层次观察问题 6 西北大学硕士学位论文 的策略提出用句子向量空间模型形式化的表示文本案例。 第四章：基于句子向量空间模型的案例知识检索算法。本章是全文的理论核心，首 先分析案例检索中的粒度原理，将案例检索过程抽象为粒度计算的过程，提出基于句子 向量空间模型的文本案例检索算法；其次对该算法进行改进，提取关键句并加入领域知 识；最后实现检索过程的并行计算。 第五章：案例知识检索系统的设计与实现。为了验证本文研究的理论思想，首先给 出案例检索系统的总体架构；其次介绍该系统的工作流程、类图设计和主要模块功能的 设计；然后介绍系统开发平台及运行环境；最后开发的系统界面介绍案例知识检索系统 的实际应用。 7 诬北大学硕士学位论文 第二章相关基础知识 本章主要介绍本文中文本案例检索算法提出的思想依据粒度计算，以及检索过 程快速有效执行的实现手段并行计算。 2 1 粒度计算概述 2 1 1 粒度计算定义 信息粒度( i n f o r m a t i o ng r a n u l a r i t y ) 的概念最早在2 0 世纪7 0 年代由美国数学家 z a d e h 1 6 - 1 8 1 提出。此后，粒度计算( g r a n u l a r c o m p u t i n g ) 引起了国内外学者的广泛关注， 被公认为是一种新的信息处理的概念和方法，从而成为人工智能领域的一个重要研究方 向。 但是到目前为止，粒度计算还没有一个精确统一的定义。z a d e h 根据人类的认知过 程，提出了三个主要概念，包括粒化( g r a n u l a r i t y ) 、组织( o r g a n i z a t i o n ) 和因果 ( c a u s a t i o n ) 。其中，粒化为将整体按一定的规则划分成若干个部分，组织为将各个部 分按某种方式集合起来构成一个整体，因果即为原因和结果之间的关联。根据这三个概 念z a d e h 进一步提出了，粒度计算是一种新的用来处理信息的概念和计算范式，它涵盖 了所有粒度的理论、方法论、技术和工具及其相关内容的研究。因此，所有采用分组、 分层、分类和聚类方法来分析问题和解决问题的理论和方法都属于粒度计算的范畴。 综上所述，粒度计算是一种看待客观世界的世界观和方法论f 1 9 ，它强调从多层次、 多角度去分析和解决问题，并能在各层次和角度之间灵活的切换( 层次和角度即为粒 度) 。采用粒度计算的方法能够更加真实准确的对客观世界中的复杂问题进行描述，从 而将复杂问题简单化。 2 1 2 粒度计算的问题 粒度计算的关键在于怎样建立一个合适的信息粒度，以及如何在这个粒度世界中解 决实际问题，即包括以下两个基本问题： 1 ) 信息粒度的构建 人们在解决和处理包含大量复杂信息的问题时，通常会按照特征或性能，将这些信 息划分成若干个较为简单的块，把被每个划分成的块看作是一个粒，那么，这种处理信 息的过程就是信息粒度的构建过程。 9 第二章相关基础知识 信息粒度构建的内容包括： 构建信息粒度的准则。用来规定什么样的个体可以放到同一个粒中。信息粒度的 粗细直接影响着问题求解的复杂度和效率，过粗可能造成求解失败，过细则会造成信 息的冗余而降低求解效率。所以信息粒度的构建准则很必要也很重要。 信息粒度的构建方法。解决怎样将不同的个体放到同一个粒中的算法。 信息粒度的表示。不同的信息粒度必须用某种语言来表述和区分，可以用数学公 式形式化地表示，也可用范围区分不同层次的粒度。 信息粒度的解释。对信息粒度进行定性、定量的分析，如度量信息粒度间的相似 度等。 2 ) 用信息粒度求解实际问题 用信息粒度求解实际问题，即将信息粒度作为对象进行运算和推理，最终求得问题 的解。具体内容包括： 信息粒度层间的映射：我们用映射来形容不同信息粒度层之间的联系。信息粒度 层之间的映射关系表现为，同一问题可在不同粒度层次上用不同的信息粒度进行表示。 信息粒度间的转换：粒度计算的本质是在多种信息粒度层上对所求问题进行观 察、分析、最终得解，该过程要求实现不同信息粒度之间的灵活转换。信息粒度间转换 的依据是信息粒度层之间的映射，不同层次上的信息粒度间的转换包括从粗到细和从细 到粗两种。 信息粒度上的操作：包括从粗到细的粒度转换和从细到粗的粒度转换。 性质保持性：即可以用不同的信息粒度描述同一问题的不同细节，前提是该问题 的某些性质必须能在所有粒度上都可以表示且被体现。 上述只是目前粒度计算的基本问题，随着研究的进一步深入，还会不断出现新的问 题和情况。 2 1 3 主要的粒度计算模型 粒度计算从被提出发展到现在，有很多模型方法，如模糊集、粗糙集、集合论和区 间分析、决策树、聚类分析、证据理论【2 1 1 等。这些大多数是独立提出并发展的，各模 型之间并没有统一的粒度计算方法。我们主要介绍其中三种主要模型： 1 ) 基于模糊集合论的词计算模型 z a d e h 认为人类用语言来思考、判断和推理，语言包含不同的词，不同的词就代表 l o 西北大学硕士学位论文 不同的粒度，针对怎样用这些不同的粒度进行模糊推理判断的问题，提出了模糊集 ( f u z z ys e t s ) 的概念。并于1 9 9 6 年正式提出“词计算模型【1 6 】 即模糊粒度化理论的正 式提出。 z a d c h 也提出了基于模糊集合论的粒度计算的通用框架叫，其中粒的定义和构造使 用广义约束的概念，从而将用自然语言描述的问题转换成约束的集合。在这之后，z a d e h 又提出了根据模糊图或i f t h e n 规则来表示粒之间的关系，如：i fai s 凡t h e nbi sc ， 表示某论域上的粒度a 被r 约束，则推出b 被c 约束，这种关联计算方法就是词计算。基 于词计算的推理判断方式最贴近人类的思维形式，将模糊词看做是一个基本信息粒，即 可用粒计算来实现词计算。 2 ) 基于粗糙集理论的粒度计算模型 粗糙集理论【2 2 。2 5 1 由波兰学者z p a w l a k 于1 9 8 2 年提出，该理论可用来对不完整数据、 不精确知识、不确定信息进行表达、学习和归纳。粗糙集理论直接从所给问题的描述集 出发，不需要提供任何其他的先验知识，通过观察和测量数据提取有用特征，从而简化 了信息处理过程。粗糙集理论用已有的知识库来( 近似) 刻画不精确、不确定或不完整 的知识，通过等价关系给定所求问题的近似域，找到内在规律，最后得到问题的解。 它是处理信息的有效技术，也是当前人工智能的研究热点，作为一种新的科学逻辑 和研究方法，已经被成功地应用在了各个领域。 3 ) 基于商空间的粒度计算模型 商空间理论【2 6 2 7 】由张钹院士和张铃教授提出，它基于不同的粒度世界及其转换，用 商集来表示不同粒度世界的对象模型。 商空间理论用一个三元组( x ，t f ) 来表述问题，x 是问题的论域，t 是论域的拓扑 结构( 论域中各元素问的关系) ，f 表示论域的属性。在论域x 上给定该3 元组一个等 价关系r ，得到对应等价关系r 的商集u ，商集u 中各等价类构成一个新的空间即粒 度世界。不同的等价关系对应了不同粒度的问题表示，从而将问题论域划分成不同的粒 度世界，同时实现了不同粒度层次之间的转换。商空间理论强调将同一个问题放在不同 的粒度世界中，得到不同角度的分析，简化问题，最终解决问题。 目前商空间理论的研究已经成功应用在案例推理【2 8 1 、文本分类【2 9 1 、文本聚类【3 明等 领域。 1 ) 三种模型间的关系 词计算、粗糙集理论和商空间理论，都是以集合论为基础的具体的粒度计算模型， 1 1 第二章相关基础知识 即都把论域的子集看做粒，但三者各有侧重点。词计算着重于粒度的表示问题，用模糊 集理论描述的“词 来表示；商空间理论主要研究不同粒度世界之间的关系及其相互转 换，侧重在描述空间关系；粗糙集理论重在粒度的表示，以及粒度间的关系。 总之，三种模型虽各有侧重，但都是从不同粒度去思考和解决问题。 2 2 并行计算概述 2 2 1 并行计算的定义 并行计算【3 1 3 2 1 ( p a r a l l e lc o m p u t i n g ) 是指将一个问题求解的过程分解为多个子任务， 分别分配给不同的处理机，处理机之间通过相互协作，并行的执行子任务，从而达到加 快求解速度，或者提高求解应用问题规模的目的。 并行计算的主要目的是：提高问题求解的速度，即减少时间复杂度，这主要通过增 加处理器的个数( 空间复杂度) 来完成的；提高求解问题的规模。如单处理机只能计算 1 0 万个网格，当问题规模要求计算1 0 0 0 万个网格时就可以借助并行计算来实现。综上 所述，并行计算旨在满足不断增长的应用问题对速度和内存资源的需求。 2 2 2 并行计算研究的主要问题 1 ) 并行计算机的高性能特征抽取。充分理解并抽取当前并行计算机体系结构中潜 在的高性能特征，提出适当的方法，用来指导并行算法的设计和并行程序的实现。 2 ) 并行算法的设计与分析。针对实际要求解的问题进行分析，根据问题本身的并 行性将其分解为多个可同时执行的子任务，对该算法的可行性进行分析并计算执行效 率，最终设计出高效率的并行算法。 3 ) 并行实现技术。包括并行程序的设计和并行性能的优化。并行程序的设计指基 于并行编程环境，设计并行算法，编程并运行该程序，求得问题的解。并行性能的优化 指应用并行计算机的高性能特征和实际求解问题的特点，不断的对并行程序的性能进行 优化。 4 ) 并行应用。通过对并行程序的正确性和效率进行验证和确认，将其进一步发展 为并行应用软件，用于实际问题的求解。针对实际问题求解过程中不断出现的问题，对 并行算法和程序进行改进。 综合上述研究点，并行计算机的高性能特征抽取是并行计算研究的基础，并行算法 的分析、设计和实现技术是研究的核心，而并行应用是研究并行计算的最终目的。 1 2 谣北大学硕士学位论文 2 2 3 并行计算的设计方法 并行算法的设计方法大体上分为三种： 1 ) 现有串行算法并行化。对原有的串行算法进行检测和分析，开发其原有的并行 性，直接将其并行化。这种方法代价小而且易于实现，但也存在缺陷，串行算法内部可 能存在着顺序性，导致并行化难以完成，因此盲目的将串行算法并行化常常会导致失败。 2 ) 借用已有并行算法。寻找求解问题与已有并行算法的某种内在联系，借用已有 的并行算法完成所求问题。这种方法依赖于已有的并行算法，适用范围受到一定的限制。 3 ) 全新设计。从所给问题的本质出发，研究该问题的特点，最终设计全新的并行 算法。一般全新设计的难度较大，可考虑借助已有串行算法的设计思想，着重于实现并 行化的设计。 2 2 4 并行计算的评价标准 串行算法一般将执行时间作为性能评价标准。但是在并行算法中，执行时间包括从 进程开始执行到所有进程执行完毕，可分解为程序执行的c p u 时间、通信时间、同步 开销时间等，因此执行时间不能单独作为并行算法评价的标准。其他衡量标准例有： 1 ) 并行算法的成本。定义为该算法的执行时间与使用处理器数目的乘积。并行算 法的成本是否最优，取决于该成本是否在数量级上不大于最坏情况下串行算法求解同一 问题的执行时间。 2 ) 加速比。是衡量并行算法性能的重要参数，定量描述了串行程序通过并行化减 少执行时间而获得的性能。加速比有两种形式：若一个并行系统包含多台处理机，多处 理器的加速度比定义为：单处理机和多处理机( 要求各处理机的结构完全一致) 求解同 一问题所需时间的比；并行算法相对于串行算法的加速比定义为：串行算法和并行算法 求解同一问题所需的时间比。 3 ) 并行效率。反映了并行计算的代价，即处理器对提高加速比的贡献。并行效率 定义为算法加速比同使用处理机( 要求各处理机的体系结构完全一致) 数目的比值，这 两个值越接近效率越高，当效率等于1 时称算法最优。实际上效率接近1 是很难的，因 为往往处理器的增加会导致算法中并行度低、缺乏负载平衡、同步时间的开销大等。 4 ) 可扩展性。用来度量并行算法有效地利用增加的多处理机的能力。并行算法的 可扩展性取决于效率曲线随处理机增加的变化程度，如果基本不变或略微下降则认为可 扩展性良好，如果下降很快则认为可扩展性铰差。 1 3 第二章相关基础知识 2 2 5 现有的并行计算平台 并行计算平台一般指在操作系统上实现的，支持并行计算程序的软件集。下面介绍 当前应用较为广泛的p v m 和m p i 。 1 ) p v m ( p a r a l l e lv i r t u a lm a c h i n e ) p v m 3 3 1 是基于局域网、基于消息传递的并行计算环境，是美国的o a kr i d g e 国家 实验室于1 9 8 9 年推出的一个实验性网络计算环境。p v m 是用来进行网络并行计算的软 件包，它通过连接异构的计算机网络，形成类似单一且功能强大的并行计算机，节点间 的通信方式包括消息传递和远程过程调用两种。 p v m 包括监控进程( p v m d ，p v m 的核心) 、接口库( p v ml i b ) 、控制台进程( 交 互式地与用户工作) 三个组成部分，采用主从结构的工作模式【州，如图3 ： 图3p v m 工作模式图 p v m 支持多用户、多任务的运行机制。p v m 支持多种并行计算模型，支持以消 息传递的方式编写并行程序，程序执行时以任务为单位( 任务等价于进程) ，给每个任 务设置唯一的标识符，任务间可通信和同步，任务在哪个节点上加载和运行对用户透明， 方便用户编程。p v m 可充分利用网络中适于求解问题的硬件结构，并提供函数库方便 用户设计并行程序，可支持c 、f o r t r a n 语言。 综上所述，p v m 具有良好的可移植性、通用性强、系统规模小、易于管理和编程 等，因此已被广大用户所接受。 2 ) m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) m p i 的目标是开发一个广泛使用的消息传递程序标准3 5 。3 7 】。具体实现包括m p i c h 1 4 西北大学硕士学位论文 ( m p i 的重要实现) 、l a mm p i ( 面向集群) 、m p i p r o ( m p i 标准的具体实现) 。 m p i 作为标准，主要用于监管基于消息传递的并行程序的开发，从而为用户提供实 际可用的、灵活高效且可移植的消息传递接口库【3 8 1 。 一个m p i 并行程序由一组运行在相同或不同计算机计算节点上的进程或线程构 成。这些进程或线程可运行在相同或不同的处理机上。m p i 中的一个进程定义为一个独 立参与通信的个体。一个m p i 并行程序中部分或全部的进程的有序集合被定义为进程 组。进程间的通信、同步由通信器来完成，通信器被定义为所包含的进程组和先关联的 一组属性。进程间的通信通过消息的收发或同步操作完成。进程间进行的一次数据交换 定义为消息。在m p i 中，消息由通信器、源地址、目的地址、消息标签和数据组成。 m p i 程序的各个进程通过调用m p i 函数进行通信，协同完成一项计算任务。m p i 系统 提供标准的消息传递函数库，该库支持c 、f o r t r a n 语言。进程间的数据交换和同步通信 可通过调用消息传递函数库中的函数来实现，用户调用时只需学习各函数的标准接口即 可。常用的七种功能函数分别是，点到点通信、聚合通信、通信器、进程拓扑结构、并 行、环境管理和用户自定义数据类型。 一个m p i 并行程序主要由三部分组成：首先进入并行环境，包括在指定的计算机 或节点上启动并构建程序的所有进程及其初始通信环境；接着执行并行任务，是并行程 序的主体也是实质部分，实现并行算法的执行过程；最后退出并行环境，即执行结束。 总之，m p i 可提供应用程序编程接口、提供通信效率、可在异构环境下提供实现、 提供可靠的通信接口等。m p i 因移植性好、功能强大和效率高等优势，也已经成为基于 消息传递的重要的并行编程工具之一。 2 3 本章小结 本章主要介绍了文本案例检索算法用到的基础知识和相关技术。首先介绍了粒度计 算的思想，包括粒度计算的定义、粒度计算研究的问题和粒度计算常用的三种模型以及 它们之间的关系；其次介绍了并行计算技术，包括并行计算的定义、并行计算研究的主 要问题、并行计算的设计方法、并行计算的评价标准和现有的两种并行计算平台p v m 、 m p i 。其中，粒度计算是本文案例知识检索算法设计的思想方法，而并行计算是案例检 索快速有效执行的实现手段。 1 5 西北大学硕士学位论文 第三章句子向量空间模型 本章从文本案例出发，对文本案例进行粒化分析及粒度划分，应用粒度计算思想中 从不同层次观察问题的策略，结合人类以句子为单位理解语言的特点，提出并研究用句 子向量空间模型表示文本案例。 3 1 文本案例及其粒化分析 本文研究的案例知识检索算法主要面向专业领域，领域中的很多历史经验和方法都 是用非结构化的文本形式保存的，也称为文本案例。因此，本文检索算法的研究针对文 本案例进行。文本案例属于以非结构化形式表示的案例知识的一种重要形式。本文基于 粒