（计算机软件与理论专业论文）基于商空间的构造性学习算法研究.pdf

太原理工大学硕士研究生学位论文 基于商空间的构造性学习算法研究 摘要 粒计算的目的是建立一种体现人类问题求解特征的一般模型，其基本 思想是在不同的粒度层次上进行问题求解。粒是粒计算的最基本的原语， 它是一簇点( 对象、物体) 由于难以区别，或相似、或接近、或某种功能而 结合在一起所构成的。 从粒计算的角度来看，问题求解的商空间理论用拓扑来描述论域的结 构，用等价关系来完成粒化，借助于自然映射实现在不同粒度层次上的转 换。 商空间理论作为一种问题求解的方法，有着坚实的理论基础，它采用 多侧面、多角度的问题求解方法，可以在解决问题时缩小求解难度，降低 计算量。商空间理论把定性的思维和定量的分析有机地统一起来，合理地 对复杂问题进行粒度描述，把复杂问题分解为可求解的、不同粒度的学习 规则，然后再合成相关的规则，最终得到复杂问题的综合规则。 传统的基于距离或相似度的聚类算法一般都基于“特征矢量”的方法， 这种方法并不适宜用来处理个体数据。往往由于进行了数据矢量转化操作 而造成信息丢失，最终可能会导致聚类结果的不准确。 覆盖方法最优之处在于覆盖领域完全真实地反映了样本的分布情况， 本文中分析了覆盖算法中需要进一步研究的三个问题：第一个是对该算法 识别的正确率与泛化能力之间矛盾的解决，第二个是如何改进覆盖方法， 太原理工大学硕士研究生学位论文 第三是如何提高泛化能力。 基于商空间理论，作者提出了对于覆盖算法的改进思想，它能在基本 保持分类能力的前提下，提高分类的速度和识别的精度。从对平面双螺旋 线数据的实验结果可以看出，与交叉覆盖聚类算法对比，改进的算法的正 确识别率显著提高，随着训练样本数据的增加，拒识率为0 ，若不计训练时 间，那么改进的算法是可行的。 作为一种正在兴起的智能计算方法，商空间理论和覆盖算法本身还有 许多地方有待发展和完善。 关键词：粒计算，商空间，构造性学习方法，覆盖算法 太原理工大学硕士研究生学位论文 t h er e s e a r c ho fs t r u c t u ra i ，l e a r n l n g m e t h o db a s e do nq u o t i e n ts p a c e a b s t r a c t a sa ne m e r g i n gr e s e a r c hs u b f i e l do fa r t i f i c i a l i n t e l l i g e n c e ，g r a n u l a r c o m p u t i n g ，w h o s ep 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 t l 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 e p r o c e s so f h u m a n p r o b l e ms o l v i n g g r a n u l e ，ac l u m p o f p o i n t s ( o b j e c t s ) d r a w nt o g e t h e rb yi n d i s t i n g u i s h a b i l i t y , s i m i l a r i t y , p r o x i m i t y o r f u n c t i o n a l i t y ，i st h ep r i m i t i v en o t i o no f g r a n u l a rc o m p u t i n g q u o t i e n ts p a c et h e o r yo fp r o b l e ms o l v i n gi sg e n e r a l i z e df r o mt w o d i r e c t i o n s ，n a m e l yt h es l n j c n l r eo ft h eu n i v e r s eo fd i s c o u r s ea n dg r a n u l a t i o n c r i t e r i a i nt h el i g h to fg r a n u l a rc o m p u t i n g q u o t i e n ts p a c et h e o r yo fp r o b l e m s o l v i n ge x p l o i t st o p o l o g yt od e s c r i b et h es r e o ft h eu n i v e r s eo fd i s c o u r s e ， a n du t i l i z e se q u i v a l e n c er e l a t i o nt oi m p l e m e n tg r a n u l a t i o n ，a n dr e l i e so nt h e n a t u r a lm a p p i n gt or e a l i z et h et r a n s l a t i o n sa m o n gd i f f e r e n tl e v e l so fg r a n u l a r i y a sam e t h o do fp r o b l e ms o l v i n g ，q u o t i e n ts p a c et h e o r y ，b a s e do n s u b s t a n t i a lt h e o r y ，c o n s i d e r i n gt h ep r o b l e mf r o md i f f e r e n ta s p e c t sa n d m u l t i - h i e r a r c h yi nt h ep r o c e s so f p r o b l e ms o l v i n g ，i sak i n do f p o w e r f u lt o o li n t h a ti tc a nd e c r e a s et h ed i f f i c u l t yo ft h ep r o b l e ma n dr e d u c et h ec o m p u t a t i o n a l c o s t u n i f y i n gt h eq u a n t i t a t i v ea n a l y s i sa n dt h eq u a l i t a t i v ea n a l y s i sb yu t i l i z i n g i i i 太原理工大学硕士研究生学位论文 q u o t i e n ts p a c et h e o r y ，co m p l e xp r o b l e m sa r er e p r e s e n t e db yd i f f e r e n tg r a n u l e s b a s e dq u o t i e n ts p a c e a f t e rl e a r n i n gr u l e so fd i f f e r e n tg r a n u l e sa c h i e v e d ， i n t e g r a t er u l e so ft h ec o m p l e x p r o b l e mc a nb eg a i n e db yc o m p o s i n gr e l a t i v e r u l e s t h et r a d i t i o n a lc l u s t e r i n ga l g o r i t h m sb a s e do nd i s t a n c eo rs i m i l a r i t ya l e v e c t o r - b a s e d ，t h e s em e t h o d sa r eu n f kf o ri n d i v i d u a lb e h a v i o r a ld a t a ，th e r ew i l l b eal o to fi n f o r m a t i o nl o s ta n dw i l ll e a dt ot h ec l u s t e r i n gi n a c c u r a t e d i r e c t e db yt h et h e o r yo fq u o t i e n ts p a c e ，ai m p r o v e da l g o r i t h mo fc o v e r i n g a l g o r i t h mi sp r e s e n t e d i tc a nk e 印t h es o r t i n ga c c u r a c ya n dc u td o w nt h e o c c u p y i n go f m e m o r y a n dt h ec o s to f d a t ac o l l e c t i n g t h es i m u l a t i o ne x p e r i m e n t a b o u td u a ls p i r a ld a t as h o w st h ef e a s i b i l i t yo ft h ei m p r o v e da l t e r n a t i v ec o v i n g a l g o r i t h mp r o p o s e d a b o v e a sam e a n so ft h er i s i n ga r t i f i c i a li n t e l l i g e n c e ，q u o t i e n ts p a c et h e o r ya n d c o v e r i n ga l g o r i t h mi t s e l f n e e dm o r ed e v e l o p m e n t a n dc o n s u m m a t e k e yw o r d s ：g r a n u l a rc o m p u t i n g ，q u o t i e n ts p a c et h e o r y ，s t r u c t u r a l l e a r n i n gm e t h o d ，c o v e r i n ga l g o r i t h m i v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下。 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均己在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：必垦e l i ： 兰2 ：查：! 鱼 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定。其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) o 签名：童鳖垦垦e t i 朝：1 2 ：兰鱼 导师签名：垒! 送日期：丝z 三：! ! 太原理工大学硕士研究生学位论文 第一章概述 研究粒计算对于设计和实现智能系统具有重要意义，在不同的粒度层次上求解问题 是人类问题求解过程中所固有的一个特征，是人类智能的重要体现。粒计算可以使得人 们在求解问题时只关心与当前兴趣有关的内容，而忽略掉一些无关紧要的细节，缩小了 对问题的解的搜索范围，从而降低了问题求解的复杂度，提高问题求解的效率。 在实际应用中由于各方面的原因，人们所获得的信息是不完备的、不确定的或者是 含糊的，在这种条件下，完全区分不同的元素是很困难的，而考虑粒则是一种比较合适 的选择。即使可以获得详细、完全、精确的信息，但有些实际问题根本就不需要最优解 而只需要一个好的近似解即可，这正如模糊逻辑( f u z z yl o g i c ) 的指导性原则所要体现的： “e x p l o i tt h et o l e r a n c ef o ri m p r e c i s i o nu n c e r t a i n t ya n dp a r t i a lt r u t ht oa c h i e v et ot r a c t a b i l i t y r o b u s t n e s s ，l o ws o l u t i o nc o s ta n db e t t e rr a p p o r tw i t hr e a l i t y ”。 从具体应用上来看，区间分析、分治法、p s 证据理论、词计算、粗糙集理论和 商空间理论在各自的领域都取得了成功，它们都是具体的粒计算模型。因此，研究粒计 算具有重要的应用意义，尤其是融合不同具体粒计算模型的优点可以得到更有力的粒计 算模型。另一方面，研究粒计算模型又可以带动一些基础学科的进展。如粗糙集理论的 研究需要以拓扑学、数理逻辑、格论、概率论、证据理论、信息论等作为基础，反过来 又带动了这些理论的发展，给这些领域带来新的活力，丰富了这些领域的内涵。 1 1 商空间及粒度分析 张钹和张铃两位教授认为“，：“人类智能的公认特点，就是人们能从极不相同的粒度 上观察和分析同一问题。人们不仅能在不同粒度的世界上进行问题求解，而且能够很快 地从二个粒度世界跳到另一个粒度世界，往返自如，毫无困难。这种处理不同世界的能 力，正是人类问题求解的强有力的表现。”，商空间理论就是基于上述逻辑出发点、借助 于数学上的商结构而得到的。 在商空间理论中用一个三元组( x ，厂，r ) 来描述问题，其中x 是论域，r 是x 上的结 构，确切地说是拓扑结构，是属性( 向量) 函数。给定三元组( x ，r ) 上的一个等价关 系r ( 或者等价地说是一个划分) ，商空间理论所讨论的投影问题就是考虑在由等价关系 太原理工大学硕士研究生学位论文 r 所决定的商集合上的商结构和商属性函数，即( 【z 】，【门，f r 】) 的构造问题，实际是从细 粒度层次到粗粒度层次的转换。若给定两个( 或若干个) 粗粒度层次 ( 】。，【门，旷】，) ，f 沩下标集，商空间理论所讨论的合成问题就是如何找到一个合适 的粒度层次并构造该粒度层次上的结构和属性，使得在该层次上对问题具有客观、全面 的描述。 在商空间模型下，可建立对应的推理模型。由于考虑到论域的结构，借助于拓扑中 连通性以及映射的连续性，可以得到该推理模型具有如下的性质： ( 1 ) 商空间模型中推理的“保假原理”( 或“无解保持原理”) ( 2 ) 商空间模型中推理合成的“保真原理” 所谓“保假原理”是指若一命题在粗粒度空间中是假的，则该命题在比它细的商 空间中一定也无解；所谓“保真原理”，是指若命题在两个较粗粒度的商空间中是真的， 则( 在一定条件下) ，在其合成的商空间中对应的问题也是真的。 这两个原理在商空间模型的推理中起到很重要的作用。若我们要对一个问题进行求 解，当问题十分复杂时，常先进行初步分析，即取一个较粗粒度商空间，将问题化成在 该空间上的对应的问题，然后进行求解。如果得出该问题在粗粒度空间中是无解，则由 “保假原理”，立即得原问题是无解的。因为粗粒度的空间规模小，故计算量也少，这 样就可以以很少的计算量得出所要的结果，达到“事半功倍”的目的。同样，利用“保 真原理”也可达到降低求解的复杂性目的。设在两个较粗空蜀、互上进行求解，得出 对应的问题有解。利用“保真原理”可得，在其合成的空间墨上问题也有解。设置、j ，2 的规模分别为岛、岛。因为一般情况下，五的规模最大可达到毛屯。于是将原来要求 解规模为是s ：空间中的问题，化成求解规模分别为砖、是的两个空间中的问题，即将 复杂性从“相乘”降为“相加”。 商空间理论就是研究各商空间之间的关系、商空间的分解、合成和在商空间中的推 理，其中对论域结构的讨论是商空间理论的重要特色。商空间理论己经被成功应用于时 间表安排、空问路径规划、遥感图象处理、模式识别等领域。 1 2 模式识别与机器学习 波兰学者p a w l a k 提出一个假设嘲：人的智能( 知识) 就是一种分类的能力，这个假 设可能不是很完备，但却非常精练。人们为了掌握事物，按事物的相似程度组成类别。 模式识别的作用和目的就在于面对某一具体事物时将其正确地归入某一类别。要进行归 2 太原理工大学硕士研究生学位论文 类，首先要有类存在。通常我们设计模式识别系统时，分类标准是人为地从系统外给定 的，通过设计或有监督的学习过程使系统能完成特定的识别任务。与此不同的是，人的 模式识别过程具有极强的学习能力，通过学习，人不仅能学会归类，而且能创造新的类 别。 采用通过事例学习策略的计算机系统，事先完全没有完成任务的任何规律性的信 息，所得到的只是一些具体的工作例子及工作经验。系统需要对这些例子及经验进行分 析、总结和推广，得到完成任务的一般性规律，并在进一步的工作中验证或修改这些规 律，因此需要较多的推理过程。 一个能够通过学习生成新特征的系统，必须拥有足够丰富的待选择特征作为基础。 这些特征也可以通过相同的学习方法逐层建立起来，但最终总有一些底层的特征是需要 事先给定的。为了分别讨论特征不同的生成方式，可以将特征粗略地分为底层、中层、 高层三个层次。 1 3构造性学习理论和方法 机器学习的目的是挖掘出尽可能多的、正确的知识，作为实现这一目的的人工神经 网络来说，学习似乎是它与生俱来的能力，这种能力可以促使人工神经网络不断地调整 网络的结构和参数，以便更准确的反映样本空间与类别之间的映射关系。 作为人工神经网络的基石，早在1 9 4 3 年由心理学家m e c u l l o e h 和数理逻辑学家p i t t s 提出了单个神经元的m c c u l l o e h p i t t s 模型( 简称m - p 模型) 跚。m - p 模型的数学表达式 为： 只= s g n ( ( 吻一谚) ) 其中，包是阈值，是权系数，s g a 是符号函数。当净输入超过阈值时，儿取+ l ， 反之为1 。一个m - p 神经元的功能，可看作是由一个超平面划分的空间位置的识别器。 如果将多个神经元( 超平面) 组合起来，就可以实现对复杂问题的分类。r o s e n b l a t t 根 据m p 模型提出了感知器的概念川”，把m - p 神经元组成为一个自适应的学习机。 在实际的分类问题中，由于样本分布情况未知，只能根据己知的有限个样本信息来 构造分类器，事实上分类器构造的关键是判断边界。因此，人工神经网络的构造可分为 两个步骤，第一步是构造出可满足需要的分类器，第二步则需构造出在已知信息条件下 的最优分类器，但这往往是一个求解最优化解的问题。 传统的人工神经网络模型，如b p 算法，主要实现上述的第一步，其目标之一是算 3 太原理工大学硕士研究生学位论文 法收敛，即确定出合理的边界。b p 算法本质上是以网络误差之平方和为目标函数，按 梯度法求其目标函数达到最小值的算法。推导此算法的困难在于，各隐含层的误差难于 表达，因为各隐含层的理想值预先是不知道的。b p 类算法均采用梯度下降的权值调整 方法，很容易导致局部极小、收敛缓慢以及泛化能力低等问题。其次，网络的拓扑结构， 即隐层数目、每个隐层的节点数目、节点之间的拓扑连接关系等，不容易事先确定嘲。 由于b p 算法自身的不足，研究人员提出了各种改进方法，特别是加强调对网络结 构而非权值的调整，从直接构造的角度来设计人- r e , 经网络，特别是前馈神经网络。张 铃教授提出了基于超球面上领域覆盖的构造性前馈神经网络构造模型，用三层神经网络 构造分类器，等价于求出一组领域，这组领域能将不同类的点分隔开来，并进一步提出 了具体的交叉覆盖算法来实现网络的构造【6 1 口】【8 】。 1 4本文的研究工作和文章组织结构 用人工神经网络的构造性学习方法进行数据挖掘，不仅要用商空间法来合理地对复 杂问题进行粒度描述，分解复杂问题为可求解的问题，得到不同粒度的学习规则，进而 合成相关的规则作为复杂问题的综合规则，而且还涉及到学习样本的选择、网络参数的 调整和网络结构的调整等问题，目标是设计出学习速度快、收敛性好、推广能力强的学 习机器。 传统的神经网络学习方法是将整个网络看作一个“黑盒”，根据学习误差驱动和梯 度下降原则来使网络收敛，因而遇到了存在局部极小、收敛速度慢等问题。构造性人工 神经网络由于自身具有构造能力，因此在网络参数和结构调整上更有优势，本论文就是 在商空间模型下用一种基于覆盖的构造性学习方法的基础上，通过对聚类算法的分析研 究，寻找一种识别精度更高的算法。 论文第二章先主要介绍了粒计算理论，研究三种粒计算模型：词计算理论、粗糙集 理论和商空间理论并加以对比。分析了商空间模型的对象分析和表示、结构性质，说明 如何利用商空间理论进行粒度的确定和合成，着重探讨商空间理论的理论模型和应用前 景。 第三章介绍了传统聚类分析的概念和方法。介绍了两种比较典型的聚类方法：系统 聚类法和动态聚类法。通过对聚类步骤地一般分析，指出了需要进一步改进的不足之处。 第四章分析了基于覆盖的构造性学习算法的概念和方法。通过覆盖的表示和覆盖领 域集合意义的说明，根据b p 神经网络不足之处，引入了构造性的神经网络，进一步分 4 太原理工大学硕士研究生学位论文 析了几种覆盖算法的流程，分析如何对构造性覆盖算法进行改进，最后采用改进算法来 对平面双螺旋曲线进行试验分析 最后的结论部分总结了本论文的主要工作和结果，并对进一步的研究和需要解决的 问题做出预测和展望。由于作者水平有限，时间仓促，所作的工作欠缺在所难免，希望 得到大家的指教。 5 太原理工大学硕士研究生学位论文 第二章粒计算理论与商空间模型 2 1粒计算理论 上个世纪5 0 年代中期，著名的科学家j m c c a r t h y 召集会议讨论人工智能未来的 发展方向，从那时起，人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 这一术语正式确立。 后来，人工智能逐渐发展成为包括了问题求解、专家系统、规划、自然语言理解、计算 机视觉、机器学习、智能控制、智能机器人等若干子领域的学科。人工智能最主要的目 的是，针对人类问题求解的能力和特征，为人类的某些智能行为建立适当的形式化模型， 以便利用计算机再现人类智能的部分功能。 粒计算( g r a n u l a rc o m p u t i n g ，g r c ) ，作为一种正在兴起的人工智能研究领域，目的 就是建立一种体现人类问题求解特征的一般模型，其基本思想是在不同的粒度 ( g r a n u l a r i t y ) 层次上进行问题求解“m m 州1 ”。 2 2 1 粒计算的发展 粒计算这一术语最初是由t y l i n ”1 建议使用的，然而，关于什么是粒计算，迄 今为止还没有统一、无争论的严格定义，也不存在统一的模型，因为不同领域都以不同 的方式体现了粒计算的基本思想“”“”，如区间分析( i n t e r v a la n a l y s i s ) 、分治法( d i v i d e a n dc o n q u e r ) 、聚类分析( c l u s t e r a n a l y s i s ) 、词计算( c o m p u t i n g w i t h w o r d s ) ，沪s 证据理论( ( d e m p s t e r - s h a f e rt h e o r yo fb e l i e ff u n c t i o n ) 、粗糙集理论( r o u g hs e t t h e o r y ) 、问题求解的商空间理论( q u o t i e n ts p a c et h e o r yo fp r o b l e ms o l v i n g ) 等； 粒( g r a n u l e ) 是粒计算的最基本的原语，可以简单地把粒理解为把若干个体“捏合” 在一起而形成的一个新个体。按照z a d e h 的定义9 “1 ，粒是一簇点( 对象、物体) ，这些 点由于难以区别，或相似、或接近、或某种功能而结合在一起。z a d e h 还指出，粒计算 是一把大伞，它覆盖了所有有关粒的理论、方法论、技术和工具的研究；粒计算是模糊 信息粒理论的超集，而粗糙集理论和区间计算是粒数学的子集。 从狭义上看，粒计算可以理解为在不同粒度层次上以粒作为运算对象进行计算和推 6 太原理工大学硕士研究生学位论文 理。从广义上看，作为一种术语，粒计算可以理解为在问题求解过程中使用粒的理论、 方法论、技术和工具的统称“羽n ”。在这个统一的框架内考虑已经存在的结果并抽取它们 的共性，从而建立发展一种更一般的问题求解理论。 1 9 6 5 年z a d e h 提出模糊集理论“”，1 9 7 9 年提出了信息粒化的概念眦”1 ，引入元素属 于给定概念( 信息粒) 的隶属程度，为后来的模糊信息粒化理论奠定基础。 早在1 9 8 2 年p a w l a k 就提出了粗糙集理论( r o u g hs e tt h e o r y ) o 州埘。由于种种原因， 直到上世纪9 0 年代中期才得到国际学术界的注意，并掀起了粗糙集研究的热潮。从一 定程度上说，正是由于粗糙集的研究与成功应用，才使得粒计算得到广泛的认可与重视。 1 9 8 5 年，h o b b s 提出一种粒度理论“”，在a i 中将一个表示待求解的整体问题的逻 辑公式用粒度理论分成若干小目题或子公式，然后分别对这些子公式求解并最后合并成 整体公式的解。h o b b s 的这个模型实质上是把较大的整体粒度拆成较小的局部粒度，反 过来又从较小的粒度解合并成整体粒度解。但在该文没有给出粒度计算规则，只是用谓 词或函数项定义了粒度和划分粒度。 1 9 9 0 年，张钹、张铃两位教授在多年从事时间规划和空问路径规划的基础上提出了 问题求解的商空间理论理论及应用。商空间理论用商集表示不同的粒度层次，具体讨论 了投影、性质保持、合成及商空间模型下的推理。应该说，借助于拓扑对论域结构的讨 论是商空间理论的最具特色的内容，由此所得到的“保真原理”和“保假原理”在降低 问题求解的复杂度方面具有极其重要的指导意义，而其他不考虑论域结构的模型很难得 出这样的结论。 1 9 9 7 - 1 9 9 8 年，z a d e h 在讨论模糊信息粒化理论( t h e o r yo ff u z z yi n f o r m a t i o n g r a n u a l t i o n ) 的论文中呲埘，提出人类认知的三个主要概念：粒化( g r a n u l a t i o n ) 、组织 ( 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 的工作进一步激起了学术界对粒计算研究的兴趣。在其后的几年里，国际学 术界有关粒计算的高水平论文越来越多，同时出现了关于粒计算的专著，粒计算的国际 会议也在召开。目前，粒计算己经成为智能计算领域的研究热点之一，越来越多的研究 者投入到这一领域的理论与应用研究之中。 研究粒计算对于设计和实现智能系统具有重要意义。首先，如前面所述，在不同的 粒度层次上对问题求解是人类问题求解过程中所固有的一个特征，是人类智能的重要体 7 太原理工大学硕士研究生学位论文 现。其次，粒计算可以使得人们在求解问题时只关心与当前兴趣有关的内容，而忽略掉 一些无关紧要的细节，缩小了对问题的解的搜索范围，从而降低了问题求解的复杂度， 提高问题求解的效率。最后，在实际应用中由于各方面的原因，人们所获得的信息是不 完备的、不确定的或者是含糊的，在这种条件下，完全区分不同的元素是很困难的，而 考虑粒则是一种比较合适的选择。即使可以获得详细、完全、精确的信息，但有些实际 问题根本就不需要最优解而只需要一个好的近似解即可，这正如模糊逻辑( f u z z yl o g i c ) “o 的指导性原则所要体现的：“e x p l o i tt h et o l e r a n c ef o ri m p r e c i s i o nu n c e r t a i n t ya n dp a r t i a l t r u t ht oa c h i e v et ot r a c t a b i l i t yr o b u s t n e s s ，l o ws o l u t i o nc o s ta n db e t t e rr a p p o r tw i t hr e a l i t y ”。 2 2 2 粒计算模型的基本组成 一、粒 粒是构成一个粒计算模型的最基本元素，一簇点( 对象、物体) ，这些点或者是由于 难以区别，或者说是粒计算模型的原语。粒是或相似、或接近、或某种功能而结合在一 起，可以把粒理解为由若干小的“颗粒”遵循某个规则结合在一起而构成一个大的“颗 粒”，该规则称为粒化准则，而按照粒化准则形成粒的过程称为粒化。 一般来说，按照一个粒化准则可以得到一簇粒。在商空间理论、粗糙集理论、聚类 分析中，粒化准则通常就是等价关系，而相应的等价类就是粒，它是原来论域的一个子 集。 粒度( g r a n u l a r i t y ) 。一般来说粒度是用来对粒的“尺寸”进行量化分析的。同样， 采用何种“测度”也应该是与具体应用相关的。 粒的内部结构。按照某个粒化准则得到的粒也应该有其内部的结构，如按照等价关 系所得到的等价类，其内部各个元素构成一个完全图，而构成每个粒的所有组成元素有 其固有的结构。 综上所述，粒是按照某个粒化准则对原来世界进行抽象所得到结果，是粒计算模型 中最基本的元素。 二、粒层 按照某个粒化准则所得到的粒的全体构成一个粒层，称之为一个粒世界，是对现实 世界的一种抽象化描述。 粒层的内部结构。粒层的内部结构是指该层上的各个粒所组成的论域的结构，即粒 相互之间的关系。作为原来论域的子集来说，粒与粒之间可以是两两不相交的，如商空 间理论、经典的粗糙集理论中；也可以是有交叉的，如基于模糊数学的词计算、关系广 8 太原理工大学硕士研究生学位论文 义粗糙集模型、覆盖广义粗糙集模型。粒层的内部结构也可以把原来论域上的结构“继 承”过来。 粒层上的运算。这里提及两类，一类是代数运算而另一类是函数。某个论域上的一 个代数运算可以简单地描述为参与若干个运算的对象以及运算的结果都是该论域上的 元素，等价地可以用多元关系描述，实际上也可以看成是该论域上的一种结构。函数通 常是指以一个论域上的若干个元素为自变量而函数值在另外一个论域上，当函数值域还 是原来论域时就是代数运算。 ， 三、所有粒层构成的结构 粒层之间的关系。粒层与粒层之间可以按照集合的包含关系自然构成一个偏序集， 甚至是完备格，商空间理论和经典的粗糙集理论都是在这个格上进行讨论的，不过前者 重在寻求在一个合适的粒层上进行问题求解，而后者则强调在某个粒层上完成对未知知 识的表示。 粒层之间的通讯。遍历所有粒层的基本问题是编码和解码问题。两个粒层之间的编 码和解码应该满足的理想条件是两者的合成是恒同映射，实际上往往不能满足而是取某 种最优解。数模、模数转换是上述思想的典型例子。 构造新的粒层。若给定一个粒世界，可以对它进行细分以得到抽象程度更底的粒层， 例如，基于模糊等价关系的商空间理论，通过由小到大选取一组水平值，就可以得到一 个分层递阶结构。若给定两个或者若干个粒层，实际是得到对现实世界的不同侧面的理 解，粒世界的合成考虑就是这个问题，比如在商空间理论中讨论了上界合成和下界合成。 2 2 3 粒计算基本问题 粒计算主要有两个方面的问题：粒化和以粒作为运算对象的运算、推理。对于每个 问题都可以从语义和算法两个方面来进行研究。 一、粒化 粒化是一个构造性的过程，粒化可以简单地理解为在给定的粒化准则下得到一个粒 层，给定多个粒化准则得到多个粒层，进而得到所有粒层构成的结构。通常的方法可以 是自顶而下通过分解粗粒度的粒得到更细的粒，或者自底而上通过合成得到更粗粒度的 粒。粒化是下一步执行粒计算的前提。 粒化准则。粒化准则考虑的是语义方面的问题，回答为什么两个对象被放进同一个 粒内的问题。关于粒化准则的一般要求有：粒化的结果使得对问题的本质方面有更深入 的理解，同时抛弃那些无关紧要的细节，从而可以达到降低闯题求解复杂度的目的。 9 太原理工大学硕士研究生学位论文 粒化方法。粒化回答如何进行粒化的问题。在给定粒化准则的前提下，采用何种方 法来实现粒层的构造，是属于算法方面的问题。涉及到粒化的其他问题还包括对粒化结 果的表示和描述以及对粒化结果进行定性、定量分析等。 二、以粒为运算对象的运算和推理 以粒为运算对象的运算和推理，也就是前面所说的狭义上的粒计算。粒计算一般要 涉及到粒、粒层和所有粒层构成的层次结构，也可以从语义和算法这两个方面来研究。 不同粒层之间的映射。由粒化得到的不同粒层之间的联系可以由映射来表示。在不 同粒层上同一个闯题以不同的粒度、不同的细节表示，粒层之闻的映射就建立了同一问 题不同细节描述之间的关系。在商空间理论中，分层递阶结构实际是一个商空间链，自 然投影具有连接各个层的作用，而且任何三个层次之闻的自然投影满足合成律，这样就 实现了对同一个问题在不同细节上的描述。 不同粒度之间的转换。在不同粒度上观察、分析、求解问题并且实现在不同粒度间 的自由转换，是粒计算的根本任务。考虑粗糙集模型，若等价关系由信息表的属性子集 决定，则对属性子集增加或者减少若干属性一般来说可以实现在不同粒度之间的转换。 在商空间理论中，由两个( 或者若干个) 商空间出发进行合成，得到上界商空间和下界商 空间，也完成不同粒度之间的转换。 性质保持性。粒化允许同一问题在不同的细节上表示，一个自然的要求就是该问题 的某些关键的性质必须能够在不同粒度上体现出来，这也是衡量粒化准则好坏的一个标 准。商空间理论中关于连通性、序的讨论都体现了这一点，其关键是自然投影( 同时也 可以看作是粒化方法，集值映射) 的连续性。特别是由连通性所得到的保假原理，可以 大大地缩小问题求解的搜索空间，在推理模型中尤为重要。 2 2 4 三种主要的粒计算模型 粒计算模型可以简单地分为模糊的粒计算模型和分明的( c r i s p ) 粒计算模型，前者 以词计算理论为代表，而后者以粗糙集理论和商空间理论为代表。 一、词计算模型 上个世纪六十年代z a d e h 提出模糊集理论，其出发点在于概念可以由论域上的子集 来表示，但概念通常没有明确的边界，因此把每个元素是否属于一个概念进行程度化。 沿着模糊集理论的方向，用模糊数学的方法进行有关粒计算的方法和理论的研究，构成 粒计算的一个非常重要的方法和方向。 z a d e h 认为人类在进行思考、判断、推理时主要是用语言进行的。，而语言是一个 1 0 太原理工大学硕士研究生学位论文 很粗的粒，如何利用语言进行推理判断，这需要由词计算来完成。其中，在广义约束的 基础上定义、构造粒，粒之间的关系由模糊图或模糊i f - t h e n 规则来表示，相应的粒计 算方法被称之词计算。 设】【是在论域u 上取值的一个变量，对x 取值的一个广义约束表示为：xi s rr 。 其中r 是约束关系，i s r 为变量系词，r 是一个离散变量，其取值决定r 用何种方式约 束x 。约束的主要类型以及定义这些类型的r 值包括：等式约束( r = e ) ；可能约束( r 取 值为空) ；真实约束( r = v ) ；概率约束( r - p ) 等等。引入这些广义约束后，根据约束的不 同可以得到不同类型的粒，从简单粒出发借助子约束的组合可以得到卡氏粒。利用自然 语言来标记( 1 a b e l ) 粒，从而建立了词计算的基础。 作为模糊逻辑的一个核心组成部分，词计算主要处理形如： i fxi s r iat h e nyi s r 2b 的模糊i f - t h e n 规则，其中r 。和b ，可以表示相同类型的约束，也可以是不同类型 的约束。 二、粗糙集理论 波兰学者p a w l a k 提出一个假设：人的智能( 知识) 就是一种分类的能力。列。上世纪 8 0 年代初，他在上述假设的基础上提出了粗糙集理论。该理论认为知识或者概念可以用 论域中的子集来表示，给定论域的一簇子集，就相当于给定一组知识。由于论域上的每 个对象都关联于一些信息、或知识，在可用的信息范围内由相同的信息所刻画的那些对 象是不可分辨的。不可分辨性关系在数学上等同于等价关系，因此给定论域上的一个等 价关系( 或论域的一个划分) 就相当于给定一些基本知识或基本概念。 给定论域u 上的一个等价关系r ，p a w l a k 称绘定了一个知识基( u ，r ) 。对于一般的 概念x ，即论域u 上的一个子集，粗糙集理论试图利用知识基中的知识来表示它，也就 是用等价类的并集来表示x 。如果x 可以写成若干个等价类的并的形式，则称它是可定 义的，否则就是不可定义的，或者称为粗糙的。对于那些不可定义集，p a w l a k 通过近似 地方式来描述它。具体地说，就是引入r 上近似集与及下近似集来描述它，而两者之间 的差称为是边界集。实际上，以商集( 即等价类的全体) 为基可以构造出一个拓扑，而x 的r 上近似集和r 下近似集分别就是x 在该拓扑空间中的闭包和内核。这样，租糙集理 论通过上近似集和下近似集实现了对于未知知识的表示，也实现了逻辑学家f r e g e 提出 的边界线思想。 粗糙集理论在其刚出现时并没有引起人们的足够重视，直到上个世纪九十年代， 随粗糙集理论在数据挖掘、知识发现等领域的成功应用，才引起国际学术界的重视，并 太原理工大学硕士研究生学位论文 产生了粗糙集热的现象。目前粗糙集理论已被应用于很多领域并获得成功，尤其是数据 挖掘领域。 三、商空间理论 张钹和张铃两位教授认为：“人类智能的公认特点，就是人们能从极不相同的粒度 上观察和分析同一问题。人们不仅能在不同粒度的世界上进行问题求解，而且能够很快 地从一个粒度世界跳到另一个粒度世界，往返自如，毫无困难。这种处理不同世界的能 力，正是人类问题求解的强有力的表现”，商空间理论就是基于上述逻辑出发点，借助 于数学上的商结构而得到的。 在商空间理论中用一个三元组( z ，厂，r ) 来描述问题，其中x 是论域，r 是x 上的结 构，确切地说是拓扑结构，f 是属性( 向量) 函数。给定三元组( x ，r ) 上的一个等价关 系r ( 或者等价地，一个划分) ，商空间理论所讨论的投影问题就是考虑在由等价关系r 所决定的商集防】上的商结构和商属性函数，即( i x ，f 门，【r ) 的构造问题，实际是从缅 粒度层次到粗粒度层次的转换。若给定两个( 或若干个) 粗粒度，商空间理论所讨论的合 成问题就是如何找到一个合适的粒度层次并构造该粒度层次上的结构和属性，使得在该 层次上对问题具有客观、全面的描述。在商空间模型下，可建立对应的推理模型。由于 考虑到论域的结构，借助于拓扑中连通性以及映射的连续性，可以得到该推理模型具有 的两个非常重要性质： p l ，商空间模型中推理的“保假原理”( 或“无解保持原理”) p 2 ：商空间模型中推理合成的“保真原理” 所谓“保假原理”是指若一命题在粗粒度空间中是假的，则该命题在比它细的商空 间中一定也无解；所谓“保真原理”，是指，若命题在两个较粗粒度的商空间中是真的， 则( 在一定条件下) ，在其合成的商空间中对应的问题也是真的。 这两个原理在商空间模型的推理中起到很重要的作用。若我f f 要对一个问题进行求 解，当问题十分复杂时，常先进行初步分析，即取一个较粗粒度商空间，将问题化成在 该空闯上的对应的问题，然后进行求解。如果得出该问题在粗粒度空间中是无解，则由 “保假原理”，立即得原问题是无解的。因为粗粒度的空间规模小，故计算量也少，这 样就可以以很少的计算量得出所要的结果，达到“事半功倍”的目的。 商空间理论就是研究各商空间之间的关系、商空间的分解、合成和在商空间中的推 理，其中对论域结构的讨论是商空间理论的重要特色。商空间理论己经被成功应用于时 问表安排、空问路径规划、遥感图象处理、模式识别等领域。 四、商空问理论、粗糙集理论和词计算之间的关系 1 2 太原理工大学硕士研究生学位论文 商空间理论、粗糙集理论和词计算都是粒计算这把大伞下的具体的粒计算模型，而 且都是在集合论这个大的框架下讨论粒计算的，即它们都把粒看作是论域的子集。这三 者不是相互排斥的，只不过各自的侧重点不同而己叫1 。下面就简单地讨论三者之间的关 系。 1 、从模型上来看。三者都是描述人类能按不同粒度来处理事物的能力的模型。商 空间理论、粗糙集理论认为概念可以用子集来表示，不同粒度的概念可以用不同大小的 子集来表示，所有这些表示可以用等价关系来描述。而词计算理论认为概念是用“词” 来表示，而描述“词”的有效的方法就是模糊集理论。 2 、从研究的对象来看。商空间理论、粗糙集理论、词计算理论都将所讨论的对象 的集合作为论域，但讨论对象之间的关系时，却又各有不同。 粗糙集理论的原型是由关系数据库抽象而得的，通过元素的不同属性值，来描述元 素之间的关系，并用元素按不同属性进行的分类来表示不同的概念粒度。商空间理论的 原型是分层递阶方法，除了元素的属性外，还引入元素之间的关系( 用拓扑来描述) 。 商空间的方法与租糙集方法都是利用等价类来描述粒，利用粒来描述概念，但讨论 的着重点有所不同。商空间理论