第6期 王因胤，等：粒计算研究综述 ·13· 论已是处理模糊、不精确和不完备问题的重要数学 属函数的基础上，利用同一等价类中的元素具有相 工具.它在机器学习、知识获取、决策分析、数据库的 同的隶属函数的思想，探讨了知识粒的结构和粒度 知识发现、专家系统、决策支持系统、归纳推理、矛盾 问题.Polkowski和Skowron等人Is)使用Rough 归结、模式识别、模糊控制和医疗诊断等应用领域取 Mereology方法和神经网络技术，基于知识粒化思 得了不少成果，业己成为粒计算研究的主要工具 想，提出了一个Rough神经计算(RNC)模型，将粗 之一 糙集的知识基（划分块）和神经网络相结合，形成一 经典的粗糙集理论主要是针对完备信息系统 种高效的神经计算方法.Sko wron!s4在文献[83]的 的，即处理对象的所有属性值都是已知的.为了使粗 基础上，进一步完善了基于粗糙集的神经计算方法， 糙集理论适用于对不完备信息系统的处理，目前有 并在一个参数化的近似空间上，讨论了信息粒的语 2种主要途径：一是补齐不完备的数据，二是扩充经 法、语义、分解和合成问题，给出了粒语言的概念，提 典的Rough集模型，至少可以从3个方面扩展粗糙 出了在分布式系统中关于信息粒结构的模式.但是 集理论6]：1)等价关系的泛化；2)基本知识粒度的 他没有提出一套行之有效的粒计算系统，也未涉及 构造和知识的表示方法的拓广：3)粗糙集的代数 分布式环境下基于粒计算的多Agent推理中的冲 方法 突问题，对信息粒结构模式中的参数也没有提出有 等价关系的泛化问题实质是将满足等价关系的 效的优化技术.Peters等人Is]使用不分明关系将实 3个条件（自反、对称、传递）根据实际问题进行组 数划分成多个子区间，将一个全域划分成若干个网 合，得到不同的二元关系，再根据这些二元关系得到 格单元，每个网格单元被视为一个粒，提出了2个信 不同的模型.如Kryszkiewiczl71提出的基于容差关 息粒之间的邻近关系和包含关系的度量，但其提出 系的扩充粗糙集模型，Stefanowski等人川提出的 的方法只能局限于单个传感器的样本数据.Peters 基于非对称相似关系的扩充粗糙集模型和基于量化 等人6]综述了关于RNC模型的主要研究线索 容差关系的扩充粗糙集模型.王国胤81分析了前面 LinB.基于二元关系提出了邻域Rough系统，建 2种扩充模型的不足，提出了基于限制容差关系的 立了粒计算模型，并使用Rough集中的近似空间作 粗糙集模型，并发现：容差关系和非对称相似关系是 为信息粒结构，定义了粒隶属函数，从而提出了粒 对不可分辨关系扩充的2个极端，即容差关系的条 Fzy集，并得出了一些重要的性质8).Yao等8s) 件太松，非对称相似关系的条件太紧，而限制容差关 利用粗糙集粒计算模型来学习分类规则，用粒网格 系介于二者之间.张清华等人]根据不完备信息的 来表示学习所得的分类知识，提出了粒之间关联性 特点，利用模糊聚类的思想，将非等价关系转化为等 的度量公式，通过搜索粒来归纳分类规则，给出了构 价关系，从而用经典的粗糙集模型来处理不完备的 造粒网格的算法.在研究Rough推理的基础上，刘 信息系统，这种方法的优势在于可以得到变精度的 清等人28·0对粒逻辑进行了探讨 正域以及上下近似.总之，粗糙集理论在不完备信息 3.3商空间理论模型 系统中的应用，是将粗糙集理论进一步推向实用的 张钹和张铃在研究问题求解时，提出了商空间 关键之一，因为现实数据可能在一定程度上是不完 理论12]，他们指出“人类智能的公认特点，就是人 备的 们能从极不相同的粒度上观察和分析同一问题.人 基本知识粒度的构造和知识表示方法的拓广实 们不仅能在不同粒度的世界上进行问题求解.而且 质是将粗糙集的商集扩展成一个拓扑空间，以此保 能够很快地从一个粒度世界跳到另一个粒度的世 证运算的封闭性，即用o(U/R)代替U/R,它是布尔 界，往返自如，毫无困难.这种处理不同世界的能力， 代数2”，~，n,U)的一个子代数，(U,o(U/)构成 正是人类问题求解的强有力的表现”如果能够将人 一个拓扑空间 类的这种能力形式化，并使计算机也具备类似的能 张文修等人)详细讨论了一般关系下的粗糙 力，对于开发机器智能来讲，意义十分重大.商空间 集模型，粗糙集代数的公理化方法以及粗糙集系统 粒计算理论的主要内容包括复杂问题的商空间描 的代数结构等问题，对变精度的粗糙集模型、概率粗糙 述、分层递阶结构、商空间的分解与合成、商空间的 集模型模糊粗糙集模型和随机集粗糙集模型等进行 粒计算粒度空间关系的推理以及问题的启发式搜 了系统的阐述进一步推广了经典的粗糙集理论， 索等).商空间理论建立了一种商结构的形式化体 近期，基于Rough集理论来研究粒计算的工作 系，给出一套解决信息融合、启发式搜索、路径规划 尤为突出s).Pawlak21在不分明关系和Rough隶 和推理等领域问题的理论和算法，并己有一些相关 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
论已是处理模糊、不精确和不完备问题的重要数学 工具. 它在机器学习、知识获取、决策分析、数据库的 知识发现、专家系统、决策支持系统、归纳推理、矛盾 归结、模式识别、模糊控制和医疗诊断等应用领域取 得了不少成果 ,业已成为粒计算研究的主要工具 之一. 经典的粗糙集理论主要是针对完备信息系统 的 ,即处理对象的所有属性值都是已知的. 为了使粗 糙集理论适用于对不完备信息系统的处理 ,目前有 2 种主要途径 :一是补齐不完备的数据 ,二是扩充经 典的 Rough 集模型. 至少可以从 3 个方面扩展粗糙 集理论[63 ] :1) 等价关系的泛化 ;2) 基本知识粒度的 构造和知识的表示方法的拓广 ; 3) 粗糙集的代数 方法. 等价关系的泛化问题实质是将满足等价关系的 3 个条件 (自反、对称、传递) 根据实际问题进行组 合 ,得到不同的二元关系 ,再根据这些二元关系得到 不同的模型. 如 Kryszkiewicz [76 ] 提出的基于容差关 系的扩充粗糙集模型 ,Stefanowski 等人[77 ] 提出的 基于非对称相似关系的扩充粗糙集模型和基于量化 容差关系的扩充粗糙集模型. 王国胤[78 ] 分析了前面 2 种扩充模型的不足 ,提出了基于限制容差关系的 粗糙集模型 ,并发现 :容差关系和非对称相似关系是 对不可分辨关系扩充的 2 个极端 ,即容差关系的条 件太松 ,非对称相似关系的条件太紧 ,而限制容差关 系介于二者之间. 张清华等人[79 ]根据不完备信息的 特点 ,利用模糊聚类的思想 ,将非等价关系转化为等 价关系 ,从而用经典的粗糙集模型来处理不完备的 信息系统 ,这种方法的优势在于可以得到变精度的 正域以及上下近似. 总之 ,粗糙集理论在不完备信息 系统中的应用 ,是将粗糙集理论进一步推向实用的 关键之一 ,因为现实数据可能在一定程度上是不完 备的. 基本知识粒度的构造和知识表示方法的拓广实 质是将粗糙集的商集扩展成一个拓扑空间 ,以此保 证运算的封闭性 ,即用σ(U/ R) 代替 U/ R ,它是布尔 代数(2 U ,～ , n ,U) 的一个子代数 , (U ,σ(U/ R) ) 构成 一个拓扑空间. 张文修等人[ 80 ] 详细讨论了一般关系下的粗糙 集模型 ,粗糙集代数的公理化方法以及粗糙集系统 的代数结构等问题 ,对变精度的粗糙集模型、概率粗糙 集模型、模糊粗糙集模型和随机集粗糙集模型等进行 了系统的阐述 ,进一步推广了经典的粗糙集理论. 近期 ,基于 Rough 集理论来研究粒计算的工作 尤为突出[81 ] . Pawlak [82 ] 在不分明关系和 Rough 隶 属函数的基础上 ,利用同一等价类中的元素具有相 同的隶属函数的思想 ,探讨了知识粒的结构和粒度 问题. Polkowski 和 Skowron 等人[83 ] 使用 Rough Mereology 方法和神经网络技术 ,基于知识粒化思 想 ,提出了一个 Rough 神经计算( RNC) 模型 ,将粗 糙集的知识基(划分块) 和神经网络相结合 ,形成一 种高效的神经计算方法. Skowron [84 ] 在文献[ 83 ]的 基础上 ,进一步完善了基于粗糙集的神经计算方法 , 并在一个参数化的近似空间上 ,讨论了信息粒的语 法、语义、分解和合成问题 ,给出了粒语言的概念 ,提 出了在分布式系统中关于信息粒结构的模式. 但是 , 他没有提出一套行之有效的粒计算系统 ,也未涉及 分布式环境下基于粒计算的多 Agent 推理中的冲 突问题 ,对信息粒结构模式中的参数也没有提出有 效的优化技术. Peters 等人[85 ] 使用不分明关系将实 数划分成多个子区间 ,将一个全域划分成若干个网 格单元 ,每个网格单元被视为一个粒 ,提出了 2 个信 息粒之间的邻近关系和包含关系的度量 ,但其提出 的方法只能局限于单个传感器的样本数据. Peters 等人[86 ] 综述了关于 RNC 模型的主要研究线索. Lin [ 3 - 4 ]基于二元关系提出了邻域 Rough 系统 ,建 立了粒计算模型 ,并使用 Rough 集中的近似空间作 为信息粒结构 ,定义了粒隶属函数 ,从而提出了粒 Fuzzy 集 ,并得出了一些重要的性质[87 ] . Yao 等[88 ] 利用粗糙集粒计算模型来学习分类规则 ,用粒网格 来表示学习所得的分类知识 ,提出了粒之间关联性 的度量公式 ,通过搜索粒来归纳分类规则 ,给出了构 造粒网格的算法. 在研究 Rough 推理的基础上 ,刘 清等人[ 28 - 30 ]对粒逻辑进行了探讨. 313 商空间理论模型 张钹和张铃在研究问题求解时 ,提出了商空间 理论[11 - 12 ] ,他们指出“人类智能的公认特点 ,就是人 们能从极不相同的粒度上观察和分析同一问题. 人 们不仅能在不同粒度的世界上进行问题求解 ,而且 能够很快地从一个粒度世界跳到另一个粒度的世 界 ,往返自如 ,毫无困难. 这种处理不同世界的能力 , 正是人类问题求解的强有力的表现”. 如果能够将人 类的这种能力形式化 ,并使计算机也具备类似的能 力 ,对于开发机器智能来讲 ,意义十分重大. 商空间 粒计算理论的主要内容包括复杂问题的商空间描 述、分层递阶结构、商空间的分解与合成、商空间的 粒计算、粒度空间关系的推理以及问题的启发式搜 索等[11 ] . 商空间理论建立了一种商结构的形式化体 系 ,给出一套解决信息融合、启发式搜索、路径规划 和推理等领域问题的理论和算法 ,并已有一些相关 第 6 期 王国胤 ,等 :粒计算研究综述 · 31 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·14 智能系统学报 第2卷 研究和应用31,4,89.41 是模糊的.这深刻地揭示了模糊和清晰的关系」 商空间理论模型可用一个三元组来表示，即 近几年来，基于商空间的粒度计算模型的应用 (X,F,).其中，X是论域，F是属性集，T是X上 也得到推广1.34,9.95，这些利用商空间理论来解决 的拓扑结构.当取粗粒度时，即给定一个等价关系R 实际问题的例子说明，当人们在面对实际复杂、难于 (或说一个划分)，得到一个对应于R的商集记为 准确求解的问题，或者求精确解的代价很大，以及实 [X),它对应于三元组(IX],[F1,[T),称之为对 际不需要精确解的问题时，通常不是采用系统的、数 应于R的商空间.商空间理论就是研究各商空间之 学的精确的方法去追求问题的精确解或最优解，而 间的关系、各商空间的合成、分解和在商空间中的推 是通过粒化的思想，将实际问题的解空间转化为商 理.在这个模型下，可建立对应的推理模型，并满足 空间，再在商空间上继续求解问题，最终利用商空间 2个重要的性质：“保假原理”和“保真原理”所谓 理论的“保真”、“保假”2个原理，得到符合实际问题 “保假原理”是指若一个命题在粗粒度空间中是假 的较优解.人类就是采用这种自顶向下，形成一个分 的，则该命题在比它细的商空间中也一定为假.所谓 层递阶的解空间结构，使得解空间的复杂度由相乘 “保真原理”，是指若一个命题在2个较粗粒度的商 变相加，避免了计算复杂度高的困难，使得看似难于 空间中是真的，则在一定条件下在其合成的商空间求解的问题迎刃而解.但是，商空间理论同样缺乏实 中对应的问题也是真的.这2个原理在商空间模型 现粒度与粒度之间、粒度与粒度世界之间、粒度世界 的推理中起到了很重要的作用.设在2个较粗空间 与粒度世界之间转换的高效方法 X、X2上进行求解，得出对应的问题有解，利用“保 3.4其他相关粒计算模型 真原理”可得，在其合成的空间X3上问题也有解 词计算模型、粗糙集模型和商空间模型是3个 设X、的规模分别为1”，因为一般情况下，X 主要的粒计算模型.在这3个模型的基础上，人们提 的规模最大可达到12.于是将原来要求解规模为 出了很多新的模型，如基于划分的粒计算模型，基于 2空间中的问题，化成求解规模分别为s、2的2 覆盖的粒计算模型，基于概念格的粒计算模型和基 个空间中的问题.即将复杂性从“相乘”降为“相加” 于相容关系的粒计算模型等 张铃又将统计学上的一些方法移植到商空间粒度分 3.4.1基于划分的粒计算模型 析上来，得到了“弱保假原理”，即：若在某商空间上 Yao在讨论了粒计算的基本原理和基本问题 问题无解，则在X上问题无解的概率大于1-α并 的基础上，从语义和算法2个方面研究了粒计算方 指出，若在X上有解的可信度等于d,则在[X]上对 法中粒子的构建、描述和表达，以及利用粒子进行计 应的问题有解的可信度大于或等于d.为了将精确 算和推理的规则等问题，提出了基于集合论的划分 粒度下的商空间的理论和方法推广到模糊粒度计算 粒计算模型.该模型对一个有限集进行划分得到相 中，张䥽和张铃51又将模糊集合论引入商空间，证 应的粒子，这些粒子互不相交，通过子集的包含关 明了利用模糊等价关系可以将原来的商空间理论推 系，不同粒度上的粒子之间形成了格的层次结构.他 广成模糊商空间理论.他们还指出，所有模糊等价关 构建了2个算子：Zoomingin和Zoomingout.利用 系构成一个完备半序格.这些结论为粒计算提供了 这2个算子，不同粒层之间的粒子可以相互转化 有力的数学模型和工具.模糊商空间理论能够更好 3.4.2基于覆盖的粒计算模型 地反映人类处理不确定问题的若干特点，即信息的 Lin以邻域系统为工具，研究了二元关系下的 确定与不确定、概念的清晰与模糊都是相对的，都与 粒计算模型31]，对粒计算的结构、表示和应用进 问题的粒度粗细有关.因此，构造合理的分层递阶的 行了系统的诠释.他研究的粒计算模型是一个典型 粒结构，可以高效地求解问题和处理信息.他们提出 的覆盖模型.Zhu6.97小等人从覆盖约简这个概念出 扩展模糊商空间理论的途径，即可从3个方向推广 发，讨论了2个覆盖生成相同覆盖广义粗集的判别 商空间理论成为模糊商空间理论： 条件，解决了覆盖的冗余问题，并设计了计算覆盖约 1)研究的论域是模糊空间X: 简的算法，建立了覆盖下近似运算的公理化体系和 2)研究的结构T是模糊拓扑， 上近似运算公理化体系.胡军等人]研究了覆盖粒 3)研究的等价关系是模糊等价关系 计算模型的不确定度量.马建敏等人[]提出了基于 并得出结论：任何一个模糊的概念必存在一个相应 集合论覆盖原理的粒计算模型，该模型是基于一个 的粒度空间，在其上该概念是清晰的：任何一个清晰 有限集合上的一个自反二元关系，并利用Zooming 的概念必存在一个相应的粒度空间，在其上该概念 in和Zooming-out2个算子来实现不同粒层上粒子 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
研究和应用[31 ,34 ,89 - 94 ] . 商空间理论模型可用一个三元组来表示 ,即 ( X , F, T) . 其中 , X 是论域 , F 是属性集 , T 是 X 上 的拓扑结构. 当取粗粒度时 ,即给定一个等价关系 R (或说一个划分) ,得到一个对应于 R 的商集 (记为 [ X ]) ,它对应于三元组 ([ X ] ,[ F] , [ T ]) ,称之为对 应于 R 的商空间. 商空间理论就是研究各商空间之 间的关系、各商空间的合成、分解和在商空间中的推 理. 在这个模型下 ,可建立对应的推理模型 ,并满足 2 个重要的性质 :“保假原理”和“保真原理”. 所谓 “保假原理”是指若一个命题在粗粒度空间中是假 的 ,则该命题在比它细的商空间中也一定为假. 所谓 “保真原理”,是指若一个命题在 2 个较粗粒度的商 空间中是真的 ,则在一定条件下在其合成的商空间 中对应的问题也是真的. 这 2 个原理在商空间模型 的推理中起到了很重要的作用. 设在 2 个较粗空间 X1 、X2 上进行求解 ,得出对应的问题有解 ,利用“保 真原理”可得 ,在其合成的空间 X3 上问题也有解. 设 X1 、X2 的规模分别为 s1 、s2 ,因为一般情况下 , X3 的规模最大可达到 s1 s2 . 于是将原来要求解规模为 s1 s2 空间中的问题 ,化成求解规模分别为 s1 、s2 的 2 个空间中的问题. 即将复杂性从“相乘”降为“相加”. 张铃又将统计学上的一些方法移植到商空间粒度分 析上来 ,得到了“弱保假原理”,即 :若在某商空间上 问题无解 ,则在 X 上问题无解的概率大于 1 - a. 并 指出 ,若在 X 上有解的可信度等于 d ,则在[ X ]上对 应的问题有解的可信度大于或等于 d. 为了将精确 粒度下的商空间的理论和方法推广到模糊粒度计算 中 ,张钹和张铃[35 ] 又将模糊集合论引入商空间 ,证 明了利用模糊等价关系可以将原来的商空间理论推 广成模糊商空间理论. 他们还指出 ,所有模糊等价关 系构成一个完备半序格. 这些结论为粒计算提供了 有力的数学模型和工具. 模糊商空间理论能够更好 地反映人类处理不确定问题的若干特点 ,即信息的 确定与不确定、概念的清晰与模糊都是相对的 ,都与 问题的粒度粗细有关. 因此 ,构造合理的分层递阶的 粒结构 ,可以高效地求解问题和处理信息. 他们提出 扩展模糊商空间理论的途径 ,即可从 3 个方向推广 商空间理论成为模糊商空间理论 : 1) 研究的论域是模糊空间 X ; 2) 研究的结构 T 是模糊拓扑; 3) 研究的等价关系是模糊等价关系. 并得出结论 :任何一个模糊的概念必存在一个相应 的粒度空间 ,在其上该概念是清晰的;任何一个清晰 的概念必存在一个相应的粒度空间 ,在其上该概念 是模糊的. 这深刻地揭示了模糊和清晰的关系. 近几年来 ,基于商空间的粒度计算模型的应用 也得到推广[31 ,34 ,89 - 95 ] ,这些利用商空间理论来解决 实际问题的例子说明 ,当人们在面对实际复杂、难于 准确求解的问题 ,或者求精确解的代价很大 ,以及实 际不需要精确解的问题时 ,通常不是采用系统的、数 学的、精确的方法去追求问题的精确解或最优解 ,而 是通过粒化的思想 ,将实际问题的解空间转化为商 空间 ,再在商空间上继续求解问题 ,最终利用商空间 理论的“保真”“、保假”2 个原理 ,得到符合实际问题 的较优解. 人类就是采用这种自顶向下 ,形成一个分 层递阶的解空间结构 ,使得解空间的复杂度由相乘 变相加 ,避免了计算复杂度高的困难 ,使得看似难于 求解的问题迎刃而解. 但是 ,商空间理论同样缺乏实 现粒度与粒度之间、粒度与粒度世界之间、粒度世界 与粒度世界之间转换的高效方法. 314 其他相关粒计算模型 词计算模型、粗糙集模型和商空间模型是 3 个 主要的粒计算模型. 在这 3 个模型的基础上 ,人们提 出了很多新的模型 ,如基于划分的粒计算模型 ,基于 覆盖的粒计算模型 ,基于概念格的粒计算模型和基 于相容关系的粒计算模型等. 31411 基于划分的粒计算模型 Yao [17 ]在讨论了粒计算的基本原理和基本问题 的基础上 ,从语义和算法 2 个方面研究了粒计算方 法中粒子的构建、描述和表达 ,以及利用粒子进行计 算和推理的规则等问题 ,提出了基于集合论的划分 粒计算模型. 该模型对一个有限集进行划分得到相 应的粒子 ,这些粒子互不相交 ,通过子集的包含关 系 ,不同粒度上的粒子之间形成了格的层次结构. 他 构建了 2 个算子 :Zooming2in 和 Zooming2out. 利用 这 2 个算子 ,不同粒层之间的粒子可以相互转化. 31412 基于覆盖的粒计算模型 Lin 以邻域系统为工具 ,研究了二元关系下的 粒计算模型[3 - 10 ] ,对粒计算的结构、表示和应用进 行了系统的诠释. 他研究的粒计算模型是一个典型 的覆盖模型. Zhu [96 - 97 ]等人从覆盖约简这个概念出 发 ,讨论了 2 个覆盖生成相同覆盖广义粗集的判别 条件 ,解决了覆盖的冗余问题 ,并设计了计算覆盖约 简的算法 ,建立了覆盖下近似运算的公理化体系和 上近似运算公理化体系. 胡军等人[ 98 ] 研究了覆盖粒 计算模型的不确定度量. 马建敏等人[99 ] 提出了基于 集合论覆盖原理的粒计算模型 ,该模型是基于一个 有限集合上的一个自反二元关系 ,并利用 Zooming2 in 和 Zooming2out 2 个算子来实现不同粒层上粒子 · 41 · 智 能 系 统 学 报 第 2 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net