（计算机应用技术专业论文）模糊商空间下的不确定性问题研究.pdf

太原理工大学硕士研究生学位论文 模糊商空间下的不确定性问题研究 摘要 在不同的抽象层次上观察、理解、表示现实世界问题连同其解，并进 行分析、综合、推理，是人类问题求解过程的一个明显特征，也是人类问 题求解能力的强有力的表现。从一定意义上来说，这就是人类问题求解过 程中智能之所在。针对人类问题求解的这种能力和特征，人工智能研究者 对其进行了深入的研究，并建立了各种形式化的模型。作为一种正在兴起 的人工智能研究领域，粒计算的目的就是建立一种体现人类问题求解特征 的一般模型，其基本思想是在不同的粒度层次上进行问题求解。 商空间理论，用三元组伍，厂，r ) 描述一个所要解决的问题。其中x 表示 问题的论域；，：x _ y 表示论域的属性；丁是论域的结构，即指论域中各元 素的相互关系。分析或求解问题僻，r ) ，就是对论域x 及其有关的结构、 属性进行分析、研究。 很大一类推理问题都可以归结为一个对应的与或图上的搜索过程。商 空间理论描述的与或图推理模型对于信息的不确定性，是通过建立不同粒 度层次的方式来解决的。但是很多情况下需要研究的粒度层次会出现无法 避免的不确定性。于是，就需要对原有模型进行扩展，构建对于不确定性 粒度的描述方式，形成推广的与或图推理模型。 本文将模糊集理论中对粒度描述的方法引入到商空间描述的与或图推 理模型( 皑，d ) ，( ，g ) ，墨e ，最，p ) ) 中。用模糊的粒度描述4 、p ，代替清晰的 粒度描述a 、p ，在此基础上构建适当的属性函数，f 和推理函数g ，形成 太原理工大学硕士研究生学位论文 模糊与或图推理模型( 皤，d ) ，( 丘，g ，) ，韪五，最，p ，) ) 。同时，证明了模糊的与 或图推理模型在商空间理论下的投影与合成的可行性。对于商空间下的推 理模型( 僻，d ) ，( ，g ，) ，譬e ，五，似，办) ) ，构造论域x 的商集五。可以证明按照商 空间理论的基本原理，能够推导出原模型的投影模型 ( ( 墨，d 1 ) ，( ，。，g 。) ，墨，e ，e ，0 4 ，。，p ，。) ) 。对于两个与或结构的商空间模型 ( ( j r l ，d 1 ) ，( a - 。，g ，。) ，墨，互，e ，。，p r 。) ) ，( ( 砭，d 2 ) ，( ，：，g ，：) ，恕，五，e ，0 4 ，：，办：) ) 可以使用 首先将与或图化成某种对应的或图进行合成，然后再将合成的或图变换到 对应的与或图的方法，求解出原模型的合成推理模型 ( ( x ，d 3 ) ，( ，g ，) ，甄，e ，2 ，( 4 ，p ，) ) o 在此基础上，利用构造的模糊商空间下的与或图推理模型，求解皮肤 敏感试验模拟问题。通过对求解问题构建商空间的描述，将问题转化为在 模糊粒度描述的与或图上搜索节点的过程。在求解过程中利用商空间下的 投影与合成理论，在不同的商空间上变换，使用模糊集的粒度描述方法， 解决了问题中的不确定性因素，最终解决问题。不仅验证了构建的模糊商 空间下的与或图推理模型的正确性，同时也为医学上对头孢菌素复方药物 的过敏性研究提供了一种处理不确定性因素的模型与思路。 关键词：商空间，模糊集，推理模型，不确定性，粒计算 太原理工大学硕士研究生学位论文 r e s e a r c ho nu n c e r t a i np r o b l e m u n d e rf u z z y q u o t i e n ts p a c et h e o r y a b s t r a c t o b s e r v a t i o n ，u n d e r s t a n d i n ga n dr e p r e s e n t a t i o n ，a s w e l la s a n a l y s i s ， s y n t h e s i sa n dr e a s o n i n g ，o fr e a lw o r l dp r o b l e mt o g e t h e rw i t hi t ss o l u t i o na t d i f f e r e n tl e v e l so fg r a n u l a r i t y , i sa no b v i o u sf e a t u r ei nt h ep r o c e s so fh u m a n p r o b l e ms o l v i n g ，a n di ta l s oe m b o d i e st h eo u t s t a n d i n ga b i l i t yo fh u m a np r o b l e m s o l v i n g i nas e n s e ，i ti st h ei n t e l l i g e n c ei nt h ep r o c e s so fh u m a np r o b l e m s o l v i n g c o n s i d e r i n gs u c ha b i l i t yo fh u m a n ，r e s e a r c h e r so f a r t i f i c i a li n t e l l i g e n c e h a v em a d es o m ef u r t h e ri n v e s t i g a t i o na n d p r e s e n t e dm a n yf o r m a lm o d e l s a sa n e m e r g i n gr e s e a r c hs u b f i e l do f a r t i f i c i a li n t e l l i g e n c e ，g r a n u l a rc o m p u t i n g ，w h o l e p h i l o s o p h yi st oi m p l e m e n tt h ep r o b l e ms o l v i n ga td i f f e r e n tl e v e l so fg r a n u l a r i t y , a i m st oe s t a b l i s hm u c hm o r eg e n e r a lm o d e lr e f l e c t i n gt h ep r o c e s so fh u m a n p r o b l e ms o l v i n g i nq u o t i e n ts p a c et h e o r y , t r i p l e t ( x ，f ，r ) i sp r o p o s e dt od e s c r i b eap r o b l e m s p a c e ，w h e r e d e n o t e st h eu n i v e r s e ；f ：x - c y i n d i c a t e st h ea t t r i b u t e s ( o r f e a t u r e s ) o fu n i v e r s ex ；a ndti st h es t r u c t u r eo fu n i v e r s ex ，n am e l yt h e r e l a t i o n s h i po fd i f f e r e n ti t e m sa tu n i v e r s ex t h er e s o l v i n gp r o b l e m ( 工，f ，r ) i st h ep r o c e s so fa n a l y z i n ga n dr e s e a r c h i n gt h eu n i v e r s ez ，t h ea t t r i b u t e s f i i i 太原理工大学硕士研究生学位论文 a n dt h es n l l c t u r et a g r e a ts o r to f p r o b l e m sc a n b es u m m e du pa sap r o c e s so fs e a r c h i n gn o d e s o nac o r r e s p o n d i n ga n d o rg r a p h i c a n d o rr e a s o n i n gm o d e lu n d e rq u o t i e n t s p a c es o l v e su n c e r t a i n t yo fi n f o r m a t i o nt h o u g h t h ea p p r o a c ho fs e t t i n gd i f f e r e n t g r a n u l el e v e l s b u tm a n yt i m e s ，s o m e u n c e r t a i n t i e so ft h eg r a n u l e sw h i c hn e e d t ob es t u d i e dc a n n o tb ea v o i d e d t h ef o r e g o i n gm o d e ln e e d st ob ee x t e n d e dt oa n e wo n ew h i c hi sc a p a b l eo fd e s c r i b i n gu n c e r t a i ng r a n u l e s t h i sp a p e ri n t r o d u c e st h ea p p r o a c ho fd e s c r i b i n gg r a n u l e si nf u z z ys e ti n t o p r o c e s s i n ga n d o rg r a p h i cr e a s o n i n gm o d e lu n d e rq u o t i e n ts p a c et h e o r y u s e s f u z z yd e f i n i t i o n sa ，a n dp f i n s t e a do faa n dp b a s e do nt h i s ，c o n s t r u c t s c o r r e s p o n d i n gp r o p e r t yf u n c t i o n f a n dr e a s o n i n gf u n c t i o ng f ，f o r mt h e i n t e g r a t e d f u z z y a n d o r r e a s o n i n g m o d e l “x ，d ) ，( 丘，g f ) ，3 ，e ，e ，( 4 ，p f ) ) m e a n w h i l e ，t h ep a p e ri m p r o v e sf u z z ya n d o r g r a p h i cr e a s o n i n gm o d e li sc a p a b l eo fp r o j e c t i n ga n dc o m b i n i n gi n d i f f e r e n t q u o t i e n ts p a c e s l e v e l s f o r r e a s o n i n gm o d e l ( ( 丘d ) ，( 磊，g f ) ，墨e ，e ，( 4 f ，p a ) ， d e f i n e s x l a st h eq u o t i e n ts e to fu n i v e r s e 工，a n dt h ep r o j e c t i o nm o d e l ( c ，d 0 ，o l ，g f l ) ，3 i ，巧，最，口”佛1 ) ) c a n b eb u i l t f o rt w or e a s o n i n gm o d e l s ( ，d 1 ) ，坼。，g 。) ，s 。，e ，e ，( 一。p 。) ) a n d ( m ，d 2 ) ，坼：，g f ：) ，o ：，e ，e ，：，所z ) ) ， t r a n s f o r m st h ea n d o rg r a p h i c st ot h ec o r r e s p o n d i n go rg r a p h i c s ，c o m b i n e st h e m t oan e wm o d e l ，a n dt r a n s f o r m si ti n t oac o r r e s p o n d i n ga n d o rg r a p h i c ，t h e n c o n s t r u c t st h ec o m b i n a t i o nm o d e l “肖，b ) ，( 厶3 ，g f 3 ) ，s 3 ，e ，最，( 彳m p f 3 ) ) f i n a l l y , b a s e do nf u z z ya n d o rg r a p h i cr e a s o n i n gm o d e lu n d e rq u o t i e n t 太原理工大学硕士研究生学位论文 s p a c et h e o r y , t h ep a p e rs o l v e sa s i m u l a t i v ed e r m a ls e n s i t i v i t yt e s t q u e s t i o n t h r o u g hc o n s t r u c t sq u o t i e n ts p a c ed e s c r i p t i o no ft h eq u e s t i o n ，t r a n s f o r m s t h e q u e s t i o n i n t oap r o c e s so fs e a r c h i n gf u z z yn o d e so na n d o rg r a p h i c t h e a p p r o a c hs o l v e su n c e r t a i n t yb yu t i l i z i n gt h ep r o j e c t i o na n dc o m b i n a t i o no f f u z z ya n d o rg r a p h i cm o d e lb e t w e e nd i f f e r e n tq u o t i e n ts p a c e s n o to n l yt e s t i f i e s v a l i d i t yo ff u z z ya n d o rg r a p h i cr e a s o n i n gm o d e l ，b u ta l s op r o v i d e san e wm o d e o fd i s p o s i n gu n c e r t a i n t yi nm e d i c a lr e s e a r c ho nc e p h a l o s p o r i na l l e r g y k e y w o r d s ：q u o t i e n ts p a c e ，f u z z ys e t ，r e a s o n i n gm o d e l ，u n c e r t a i n t y , g r a n u l a r c o m p u t i n g v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体。均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：篮妾型e t l t 月：2 翌21 ! 堕l 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) o 签 名： 导师签名：j 塑日期：丛 太原理工大学硕士研究生学位论文 1 1 课题研究背景 1 1 1 问题求解理论 第一章绪论 作为人工智能的基础研究领域之一，问题求解始终是人们普遍重视的方向。对于传 统的人工智能问题，任何比较复杂的求解技术都离不开两方面的内容：表示和搜索。问 题的求解是建立在对问题的正确表示基础上的“1 。 人们在观察问题时，有时需要从全貌到细节，有时需要从细节到全貌，也有时是上 面两种方法的组合，即时而从各侧面对事物进行了解，然后进行综合观察，时而综合观 察后，对不甚了解的部分再进行观察，总之，根据需要从不同侧面、不同角度反复对事 物进行了解、分析、综合、推理，最后得出事物本质的性质和结论。1 。这正是人类求解 问题效率高的原因。 在解决一个实际问题时，首先要面对的是如何对该问题做出正确的、形式化的描述， 正确、快捷、有效的求解是建立在正确、有效的问题描述基础之上的。同样，为了建造 具备智能的计算机，也需要首先对问题的求解过程进行形式化描述。人工智能中常用的 两种问题描述方法分别是状态空间法和问题归约法。这两种问题描述方法可以描述相当 广泛的问题求解过程。 状态空间法是用两个基本要素来描述要解决的问题，状态空间以船指示，其可表 示为一个二元组卵( s ，d ) ： s 在问题求解过程中所有可达的合法状态构成的集合； d 一操作算子的集合，操作算子的执行导致状态的变迁。 状态空间可描述为一个有向图，结点指示状态，结点间的有向弧表示状态变迁，弧 上的标签指示导致状态变迁的操作算子。对问题的求解过程就是对状态图的搜索过程， 通过问题的控制策略求得目标点或一条搜索路径。 而问题归约法是把一个复杂的问题分解为若干子问题，这些子问题一般比原问题简 单。然后分别求解子问题，子问题又可进一步分解为更简单的子问题，直到可以解决为 太原理工大学硕士研究生学位论文 止。这种描述方法把问题的求解变为与或图的搜索。它往往搜索的是一个目标子图。 人类智能的一个公认特点是能从极不相同的粒度上观察和分析同一问题，而且还能 很快地从一个粒度世界跳到另一个粒度世界，往返自如，毫无困难。这种处理不同粒 度世界的能力，正是人类问题求解的强有力表现。 例如，一位正在思考公司经营规划的计划人员，如图卜1 。当他考虑全公司的经营 计划时，他立即忽略掉公司的许多具体细节：产品来源渠道、运输方式、销售人员安排 等等。这时，公司在他看来只不过是由若干个部门组成的“方块图”而已，即他以很粗 的粒度来描述公司。随着计划的深入，当不能不考虑销售细节，如有多少个销售人员， 各货源来源方式时，他又进入一个较细的粒度的世界来观察和分析问题。一旦需要重新 考虑某个全局性的问题时，他又马上返回公司的粗粒度世界。总之，他可以在不同粒度 的世界里来去自如。 1 1 2 粒度计算研究概况 图1 - 1 公司销售计划关系 f i g1 - 1m e r c h a n d i s ep l a n n i n gf i g u r e 粒是计算的最基本的原语，可以简单地把粒理解为把若干个体“捏合”在一起而形 成的一个新个体。按照z a d e h 。“”的定义，粒是一簇点( 对象、物体) ，这些点由于难以 区别，或相似、或接近、或某种功能而结合在一起。例如，人头的粒为额头、鼻子、耳 朵、眼睛等。粒计算是一把大伞，它覆盖了所有有关粒的理论、方法论、技术和工具的 研究；粒计算是模糊信息粒理论的超集，而粗糙集理论和区间计算是粒计算的子集。 从狭义上看，粒计算可以理解为在不同粒度层次上以粒作为运算对象进行计算和推 理。从广义上看，作为一种术语，粒计算可以理解为在问题求解过程中使用粒的理论、 2 太原理工大学硕士研究生学位论文 方法论、技术和工具的统称嘲“1 。在这个统一的框架内考虑已经存在的研究并抽取它们 的共性，可以建立发展一种更一般的问题求解理论。 粒计算问题可以从两大方面来进行研究：粒的构造和使用粒的计算m 。前者处理粒 的形成、表示和解释，后者处理在问题求解中运用粒。粒的构造是指将对象空间分解为 许多子空间，或是基于有用的信息和知识，将空间中的个体聚集成不同的类，每一个类 称为一个粒，粒中的元素可以理解为对应概念的实例。粒计算可以和概念生成、知识发 现和数据挖掘联系起来，因为概念生成的目的之一是对具有某些概念的粒表示、特征化、 描述和解释。粒计算中这两方面都同等重要。 通俗的讲，粒计算的语义研究侧重“为什么”这类问题”1 ，侧重于粒的解释，如为 什么两个对象会在同一个粒之中，为什么不同的粒相关。一般来讲，每一个粒中的元素 满足不可分辨关系、相似性、邻近性或泛函性，同时信息粒化也基于这些关系。由于对 论域不同的分类标准( 等价、相容、泛序、异同等关系) 可能会形成不同粒的结构，因 此有必要研究这些关系的语义解释，如相似性、关联性、依赖性。粒的结构不同对论域 的任一子集的近似集和对这些基本粒的操作会有所不同，并导致算法的时间、空间复杂 度有很大差别，因此粒度构造要根据实际问题的需要进行。 粒计算的算法研究关注“如何”这类问题，即如何进行粒化和如何进行基于粒的计 算。很有必要研究粒计算的方法学和工具( 如近似、推理等机制) 。针对粒的分解与合 并方法的研究，是构建任何粒度体系结构的本质要求。 粒度计算是信息处理的一种新的概念和计算范式，覆盖了所有有关粒度的理论、方 法、技术和工具的研究叫，现己逐步成为人工智能领域研究的热点之一。 1 1 3 粒度计算模型及应用 目前在国际研究中粒度计算有三个主要的模型和方法。 1 1 3 1 基于模糊集合论的词计算模型 z a d e h 。“”认为人类在进行思考、判断、推理时主要是用语言进行的，而语言是一个 很粗的粒度，如何利用语言进行推理判断，也就是要进行“词计算”。狭义的模糊词计 算理论是指利用通常意义下的数学概念和运算，诸如加、减、乘、除等构造的带有不确 定或模糊值的词计算的数学体系。它借助模糊逻辑概念和经典的群、环、域代数结构， 构造出以词为定义域的类似结构。例如，模糊数及其运算。尽管这种数值型模糊粒度的 太原理工大学硕士研究生学位论文 理论体系，在模糊控制、图像识别、语言处理、故障诊断、信息检索、人工智能等领域 获得了较大的成功。但是由于自身存在的不足限制了它的应用范围。广义的模糊词计算 理论统指用词进行推理、用词构建原型系统和用词编程。总之，基于词计算理论的推理、 决策和识别方式是最贴近人类的思维形式来求解问题，它对复杂的系统的信息处理有着 广阔的应用前景。 1 1 3 2 基于粗糙集理论的粒度计算模型 波兰学者p a w l a k “”“”在二十世纪八十年代，提出粗糙集理论。他提出一个假设：人 的智能( 知识) 就是一种分类的能力，这个假设可能不是很完备，但却非常精练。在此 基础上提出，概念可以用论域中的子集来表示，于是在论域中给定一组子集族，或者说 给定一个划分( 所谓划分，是指将x 分成两两不相交的子集之并) 。从数学上可知，给 定论域z 上的一个划分，等价于在x 上给定一个等价关系r 。p a w l a k 称之为在论域上 给定了一个知识基何，r ) 。然后讨论一个一般的概念z ( x 中的一个子集) ，如何用知 识基中的知识来表示，就是用知识基中的集合的并来表示。对那些无法用【x ，月) 中的集 合的并来表示的集合，他借用拓扑中的内核和闭包的概念，引入r 下近似r 一“) ( 相当于 x 的内核) 和r 上近似r o ) ( 相当于x 的闭包) ，当尺一o ) ，r 一0 ) 时，就称x 为粗糙集。 从而创立了“粗糙集理论”，如图卜2 。目前粗糙集理论己被广泛应用于各个领域，特 别是数据挖掘领域，并获得成功 图1 - 2 粗糙近似 f i g1 - 2r o u g ha p p r o x h n a t i o n 但它同样存在着“瓶颈”问题“”，诸如： ( 1 ) 知识表示依赖于论域上的关系； ( 2 ) 缺少有效处理现实问题的代数运算体系 ( 3 ) 缺乏基本粒度的语义解释： 4 太原理工大学硕士研究生学位论文 ( 4 ) 缺乏描述粒度之间结构信息的方法等。 1 1 3 3 基于商空间的粒度计算模型 张钹院士和张铃教授“”在研究问题求解时，独立的提出了商空间理论。该模型使用 一个三元组( x ，厂，丁) 描述一个所要解决的问题。其中x 表示问题的论域；，：z l ，表示 论域的属性，可以是单值的，也可以是多值的；丁是论域的结构，即指论域中各元素的 相互关系。在该模型中，论域的一种粒度化就等同于给定一个等价关系尺或一个划分， 于是得到一个对应于r 的商集瞄】，对应的三元组为( 瞵】，【，】，口】) ，称之为对应于尺的 商空间。商空间理论就是研究各商空间之间的关系、合成、综合、分解和推理。它的最 重要的性质是同态原则，即保真原理( 或保假原理) 。当面对一个复杂问题时，常先将 问题化成在一个较粗粒度商空间对应的问题进行初步分析，若得出该问题在粗粒度空间 中无解，则由“保假原理”立即得原问题是无解的。这样就可以以很少的计算量得出所 要的结果，达到“事半功倍”的目的。同样利用“保真原理”也可达到降低求解的复杂 性目的。在此基础上建立了“粒度世界模型”以及一整套理论和相应的算法，并将其应 用于启发式搜索、路径规划等方面，取得一定成效。他们又将模糊集合论引入商空间， 利用模糊等价关系实现了商空间模型的推广。这必将有助于粒度计算的发展，能够更好 地反映人类处理不确定问题的若干特点，诸如信息的确定与不确定、概念的清晰与模糊 等。同时，商空间理论同样缺少实现粒度与粒度之间、粒度与粒度世界之间、粒度世界 与粒度世界之间转换的手段和技术方法。如果能够探索出有效的技术和方法来解决这个 问题，将会拓宽商空间的应用范围，极大丰富粒度计算的理论。 1 1 3 4 商空间粒度模型与其它模型的比较 三者都是描述人类能按不同粒度来处理事物的能力的模型o “。商空间理论、粗糙集 理论认为概念可以用子集来表示，不同粒度的概念可以用不同大小的子集来表示，所有 这些表示可以用等价关系来描述。词计算理论认为概念是用“词”来表示，而描述 “词”的有效的方法就是模糊集理论。 商空间理论、粗糙集理论、词计算理论都将所讨论的对象的集合构成论域，但讨论 对象之间的关系时，却各有不同。 粗糙集理论的原型是由关系数据库抽象而得的，故其模型为( x ，) ( 其中z 是论 域，f 是属性集) ，即通过元素的不同属性值，来描述元素之间的关系，并用元素按不 太原理工大学硕士研究生学位论文 同属性进行的分类来表示不同的概念粒度。 商空间理论的原型是分层递阶方法，故其模型为( x ， r ) ( 其中z 是论域，厂是属 性集，r 是z 上的拓扑结构) 即除了元素的属性外，还引入元素之间的关系r ( 用拓扑 来描述) ，从这个意义上来说，粗糙集理论是商空间理论的一个简单的特例。当然各自 研究的着重点和侧重点不同。 当给定一个等价关系时，粗糙集理论认为是给定一个知识基，然后讨论任给的一个 概念( 集合) 在这个知识基上如何被表示为知识基上集合之并，以及之间的关系。粗糙 集理论主要利用集合的基数( 元素个数) 之间的关系，来描述概念之间的隶属关系，这 样在一定程度上与模糊集概念联系起来。另外，粗糙集理论还讨论如何利用属性来最简 单地表示所对应的知识基，这就是所谓“简约”问题。但因模型缺乏描述元素之间的 相互关系的手段，故很难提取有结构论域中有关结构所提供的信息。当然结构在一定意 义下也可以看成是元素的某种属性，但这种属性是多元属性( 要用多元函数来表达) ， 一般不能表示为f ( x ) ，而要用f ( x ，弘) 表示，如距离要用d ( x ，y ) 表示。 商空间理论着重点不同，它不是只针对给定的商空间来讨论知识的表达问题，而是 在所有可能的商空间中，找出最合适的商空间，利用从不同商空间( 从不同角度) 观察 同一问题，以便得到对问题不同角度的理解，最终综合成对问题总的理解。它的求解过 程是在“由所有商空间组成的半序格”中运动转换的过程。故可看成是宏观的粒度计算。 而粗糙集理论是在给定的商空间中的运动，故可看成是微观的粒度计算。 词计算理论与商空间理论、粗糙集理论稍有不同，它主要研究o a 粒度计算的观点 来看它) 如何描述由词界定的不同粒度的对象，它更擅长描述由形容词、副词表达的不 同粒度的概念，如，非常好、很好、好、很不错、还好等等因为这些词有程度不同的 差别，故在一定意义下，词计算理论也给出了描述元素之间的关系，但只限于由属性的 强弱程度不同所形成的关系。 1 2 国内外研究现状 1 2 1 粒度计算研究现状 2 0 世纪6 0 年代，美国著名数学家z a d e h ”提出模糊集合论，在此基础上，于1 9 7 9 年 6 太原理工大学硕士研究生学位论文 首次提出并讨论了模糊信息粒度化问题，推动了模糊逻辑理论及其应用的发展，但在当 时未引起足够的重视。接着，z a d e h 在1 9 9 6 年提出“词计算理论”，标志着模糊粒度化 理论的诞生。其旨在解决利用自然语言，进行模糊推理和判断，以实现模糊智能控制。 随后，美国多特蒙德大学的h e l m u tt h i e l e 教授“”于1 9 9 8 年发表了“词计算理论的语义 模型”，促进了词计算理论的发展。词计算理论对因特网上的海量信息资源的高效利用 有着深远的影响。基于z a d e h 的模糊集论，进行粒度计算理论和方法的研究，已成为“粒 度计算”的重要研究方向之一。 波兰学者p a w l a k “”于1 9 8 2 年提出了粗糙集理论。由于粗糙集理论具有很强的定性分 析能力，能够有效地表达不确定的或不精确的知识，善于从数据中获取知识，并能利用 不确定、不完整的经验知识进行推理等，因此在知识获取、机器学习、规则生成、决策 分析、智能控制等领域获得了广泛应用，特别是在数据挖掘领域获得了巨大成功，也己 成为粒度计算研究领域的主要方向之一。加拿大r e g i n a 大学教授y y y a o 在研究粗糙集 理论的基础上，提出了基于邻域系统的粒度计算模型“”，并成功应用于知识发现领域。 粒度计算作为专门的术语，首次出现于z a d e h 的文献 1 7 3 中。后来，t y l i n 、y y y a o 和z a d e h 又在文献 1 8 中描述了粒度计算的重要性，这激发了人们对它的研究兴趣。随 后，大量的关于粒度计算研究的文献相继发表，而且在国际上形成了专门的研究群体， 定期召开关于粒度计算的国际研讨会。 在国内，张铃和张钹两位教授在文献 1 中提出了基于商空间的粒度计算模型。它 利用子集来表示概念，不同粒度的概念就体现为不同粒度的子集，一簇概念就构成空间 的一个划分商空间，不同的概念簇就构成不同的商空间。而粒度计算问题，也就等 价于研究在给定知识基上的各种子集合之间的关系和转换。对同一问题，可以采取不同 的粒度，通过对不同的粒度的分析，综合获取对原问题的求解。在此基础上，张铃、张 钹于2 0 0 3 年提出了模糊商空间理论“”啪1 。总的来看，粒度计算的研究在国内属于起步阶 段，尚未引起广泛关注。但有理由相信，不久的将来会有越来越多的学者加入到该领域 的研究中来。 1 2 2 商空间理论研究现状 商空间理论的研究，最初是由张铃、张钹“”1 两位教授在1 9 9 0 年前后提出的，他们 利用该理论有效的解决了启发式搜索、路径规划领域等相关问题。张燕平“o 结合商空间 7 太原理工大学硕士研究生学位论文 理论和构造性知识发现理论，在分类问题和关联规则方面给出了一些新的思路。此外， 关泽群等人将商空间理论成功的应用于遥感信息处理领域。目前，商空间理论在数据 挖掘领域的分类算法、关联规则算法及聚类算法的研究都方兴未艾。2 0 0 3 年张铃、张钹 又提出了模糊商空间理论“”啪1 ，为商空间理论的研究开拓了新的思路与空间。 1 3 论文内容安排 1 3 1 主要内容 本文以粒度计算研究为背景，详述商空间理论模型、模糊集理论模型研究方法。以 此为基础，对商空间理论描述下的与或图推理模型，进行扩展。将模糊集理论中对粒度 描述的方法引入到商空间描述的与或图推理模型( ( x ，d ) ，盯，g ) ，3 ，e ，e ，似，p 中用模 糊的粒度描述4 、p ，代替清晰的粒度描述_ 、p ，在此基础上构建适当的属性函数矗 和推理函数孙，形成模糊的与或图推理模型( ( z ，d ) ，( 五，踟) ，3 ，巧，e ，( 4 ，p ，) ) 。同时， 证明对于商空间下的推理模型( ( z d ) ，o i ，g ，) ，s ，e ，e ，( 4 ，所) ) ，构造论域x 的商集五， 能够推导出原模型的投影模型( ( 五，d 1 ) ，( j ，g ，。) ，3 ，e ，五，( 4 。，诈。) ) 对于与或结构的商 空间模型( ( 五，d 1 ) ，c 厅，卧。) ，3 。，石，e ， ，。，所，) ) ，( c 墨，d 2 ) ，c 厅：，舴：) ，墨，e ，e ，( 4 ：，p p ：) ) 可 以求解出原模型的合成推理模型( c 墨，d 3 ) ，( ，矗，g ，) ，3 ，e ，e ，( 4 ，p ，) ) 在此基础上，利用构造的模糊商空间下的与或图推理模型，求解皮肤敏感试验模拟 问题。通过对求解问题构建商空间的描述，将问题转化为在模糊粒度描述的与或图上搜 索节点的过程。在求解过程中利用商空间下的投影与合成理论，在不同的商空间上变换， 使用模糊集的粒度描述方法，解决问题中的不确定性因素，最终解决问题。验证了构建 的模糊商空间下的与或图推理模型的正确性，为医学上对头孢菌素复方药物的过敏性研 究提供了种处理不确定性因素的模型与思路。 1 3 2 结构安排 第一章，概述部分，介绍本课题研究的背景，即粒度计算研究的基本理论、基本模 8 太原理工大学硕士研究生学位论文 型及研究现状和商空间理论研究的现状。 第二章，商空间理论，介绍商空间理论研究模型，商空问下粒度的选择与调整，粒 度性质的保持性等商空间理论基础。 第三章，模糊集理论，介绍模糊集的基本理论，模糊集的构造、计算，隶属函数的 确定与使用等知识。 第四章，模糊商空间下的与或图推理模型，首先介绍由商空间理论描述的与或图推 理模型的构造。在此基础上引入了模糊集的概念描述不确定性问题，通过对模糊粒度的 构造方式的引入，将与或图的推理扩展至模糊商空间，构造模糊商空间下的与或图推理 模型，证明了模型在商空间下的投影与合成的正确性。 第五章，提出了基于皮肤敏感试验的模拟问题，利用构造出的模糊商空间下的与或 图推理模型，处理与解决了模拟问题中的不确定性，为模拟问题的研究提供了良好的模 型与解决方法。 太原理工大学硕士研究生学位论文 第二章商空间理论 层次划分的思想在日常生活中应用极为广泛，大到一个国家，小到一个部门、机构， 无一不具备自己的层次结构。实践证明：好的层次划分会极大的提高工作效率。而人类 在思考问题时，也常常是先将问题分解或简化，忽略其中细节，从一个较为高的层次分 析问题，得到一些结论以后再一层层的深入其中的细节，或者先从不同的角度对问题进 行分析，之后再将各方面的结果加以综合得到对问题的全面的了解。人类这样做的目的 就在于提高问题求解的效率。这也从一方面证明了分层递阶的重要性。 商空间理论正是一种分层递阶的数学模型理论，利用它可以有效的描述粒度世界， 描述不同粒度世界的关系。而要建立分层递阶的数学模型，就必须首先解决两部分问题： 投影和合成。 投影是指：由低层空间来构造高层空间，实现对原问题的抽象、简化，从而可以站 在一个较粗的粒度世界分析问题。主要内容是实现对原问题层次的划分，建立不同层次 粒度世界的关系，它也是求解问题的关键，好的层次划分直接有利于求解的效率的提高。 合成与投影刚好相反，是投影逆过程。是指对已经得到的问题的两个不同粒度世界 的描述，采取一定的方法来实现结果的综合，得到原问题的较为全面的理解。 2 1 商空间模型 人类智能的一个公认特点是能从极不相同的粒度上观察和分析同一问题，而且还能 很快地从一个粒度世界跳到另一个粒度世界，往返自如，毫无困难。这种处理不同粒度 世界的能力，正是人类问题求解的强有力表现。如果能够把人类的这种能力形式化，并 使计算机也具备类似能力，对于开发机器智能来讲其意义是十分重大的。商空间理论正 是基于上述出发点，借助数学上的商结构得到的。 商空间理论用三元组( x ，r ) 描述一个所要解决的问题。其中x 表示问题的论域； ，：z 畸r 表示论域的属性，可以是单值的，也可以是多值的；t 是论域的结构，即指论 域中各元素的相互关系。分析或求解问题( x ， r ) ，就是对论域x 及其有关的结构、属 性进行分析、研究。 1 0 太原理工大学硕士研究生学位论文 设一代表论域中最细的粒度，若对z 进行简化，产生一个较粗粒度的论域】，那 么就把原问题皤，r ) ，变成新层次上的问题( 瞄】， ，】，【列) ，这就得到了原问题的较粗 粒度世界的描述。 这个简化过程与数学中的商集概念完全相同：设x 是论域，在x 上给定一个等价 关系r ，对应于r 得到商集瞵】，然后将陋1 当作新的论域，对它进行讨论。这样，不 同粒度的世界与数学上的商集概念统一起来，或者说可以以商集作为不同粒度世界的数 学模型。 不同粒度的选择，表现为对论域的不同划分，也就是问题的不同粒度表示对应不同 的等价关系。例如：对于一个工厂，可以把车间看成一个等价类，那么车工、铣工、钳 工同属于一个车间，看成一个等价类。若再细分，如以工段为等价类，则在细的粒度下， 车工、铣工、钳工各为一个等价类，三者为不同的元素。当然，车工还可细分为粗车、 精车等更细的粒度。 总之，根据等价关系r ，可以将原论域划分为不同的等价类，将这些等价类看作新 的元素，可以构成一个新的论域，即商集【x 】，也可以说是将z 进行了化简，产生了一 个较粗的粒度，于是原问题( z ，r ) 就变成了新的粒度空间的问题( f 】，【，】，【r 】) 。通过对 等价关系尺的不同选择便可以得到对同一问题的不同粒度世界的新描述。 2 2 粒度的选择与调整 2 2 1 粒度的投影 投影的目的是根据原问题( 工，r ) 按照一定的标准得到高层次的问题( 陋】，【厂】，旷1 ) ， 必须保证投影得到的新问题描述应当能够保持原问题中我们感兴趣的性质。 2 2 1 1x 到【x 】的投影 这是由等价关系r 决定的，论域的划分是一个复杂的问题，通常是由提出的目标而 定的，并且与具体的论域有关。常用的方法包括： 太原理工大学硕士研究生学位论文 属性划分法 即将属性相同或相似的元素归为一类。 设厂：j 哼l ，是属性函数，若，是单值的，则可利用，来定义划分。一般来讲，y 的 结构比较清楚，所以可以利用y 的分类来定义x 中对应的分类。设 z ) 是y 的一个划分， 定义2 1 ：x i = 缸l ，( 工) j 】： ， ( 2 1 ) 则( z 是x 的一个划分。 投影划分法 若元素x 的属性函数是多维的，如有甩个属性函数分量_ ，；， 。若暂不考虑其中f 个属性石，五z ，将丘。，丘：。z 属性相同的元素归为一类，称为投影划分法a 结构划分法 把结构上或功能上关系密切的元素分为一类。如一部机器或一个大系统，按功能或 作用不同，分为不同的部件或子系统。 约束划分法 设有疗个约束条件q ，c ：。 o n ，那么可按q 进行划分。如由约束条件q 将x 分为满足q 与不满足c 1 的两大类，进而对每一个又按是否满足乞条件又分为两个子类，如此下去， 将x 分为一个2 叉树结构。 当然，还可以列出其它各种不同的划分方法。在实际问题求解中，粒度的划分有时 是动态的，即先进行一次分类，在这个粒度上进行推理与分析，得到一定的性质，问题 初步明朗后，再进一步分类，直至问题的解决。 2 2 i 2t i l l 口】的投影 上面讨论了论域x 与 x 】的关系，说明不同粒度的论域能够形成完备半序格。但对 于一个具体对象( z ，乃，结构r 也是很重要的。当一个论域x 被划分之后，其结构也 发生了变化，一般来讲是被简化了。应当关心的是，简化后的结构需保持某些我们感兴 趣的性质，所以必须讨论不同粒度世界之间性质的保持问题。 一般的讲，结构很广泛、很复杂，要统一起来讨论有一定的困难。下面将以一种常 见的情况进行讨论。( 工，厂，刁是拓扑空间，其中r 是x 的拓扑。 1 2 太原理工大学硕士研究生学位论文 定义2 2 ：设x 是一集合，r 是x 上的一个子集族。若r 满足以下三条，则称r 是x 上的一个拓扑，称僻，r ) 为一个拓扑空间： ( 1 ) 中，x e t ； ( 2 ) 若一，, t 2 r ，贝0 ( 地n p 2 ) r ； ( 3 ) 若心口丁，则旦心e t ，其中，是指标集，i 的势可以是任意的。 z 上可以有许多不同的拓扑，即拓扑不是唯一的。在一个集合x 上给定一个拓扑， 就给出x 中各元素之间的一个相互关系的结构。有不少论域x ，如机器人路径规划等， 其元素之间的相互关系可以用拓扑结构来描述，这些论域就可以利用拓扑这一数学工具 来研究。 定义2 3 ：设x 上的等价关系r 及对应的商集瞵】，在畔】上定义由t 诱导出的拓扑， 记为口1 【t 】= 恤l p “ ) r ，u c 【x 】) ( 2 2 ) 其中p ：x 一瞄】是自然投影，其定义是 p o ) = m x ( 2 3 ) p - 1 以) 一协l p 0 ) “) ( 2 4 ) 称【卅为商拓扑，( 瞵】，【丁】) 为商拓扑空问。 由拓扑学的原理可知，从商拓扑空间的结构可以了