第6期 王因胤，等：粒计算研究综述 ·19· 程度的形式化数学模型，将是一个非常有意义的工 6.4高效的粒计算方法 作.如从粒化的复杂度、合成的复杂度以及在粒子上 粒计算方法的初衷就是求解复杂问题.而用传 求解的复杂度等多方面建立一个求解最优粒化程度 统的方法来解决实际的复杂问题，不管是时间复杂 的数学模型.该模型的建立将有效地推进粒计算在 度，还是空间复杂度，往往都非常高.粒计算方法要 各类复杂问题求解中的应用.另外，在粒化程度己知 得到广泛的推广和应用，其复杂度应该低于现有的 时，粒化的方法将直接决定粒化的效率.如粗糙集模 传统方法.虽然目前的粒计算方法在计算效率上较 型采用等价关系进行粒化，商空间模型利用等价关 传统方法有一定的优势，但它们处理问题的时间复 系建立分层递阶的问题空间模型，而词计算用模糊 杂度都大于或等于O().因此，研究高效粒计算方 集得到粒子.尽管在粒计算的各种模型中，一些算法 法是一个重要的课题.如果能获得解决问题的时间复 在某些具体实例上获得了成功，但是这些方法缺乏 杂度为O(h)或O(dg,甚至更低的粒计算算法 通用性.粒计算的粒化算法设计是一个复杂的问题， 将有助于提高用粒计算方法解决复杂问题的效率 迄今为止，还没有一套较成熟的方法.如果能够借鉴 6.5新的粒计算模型 现有的相关理论设计出粒计算的粒化算法，逐步形 词计算模型、粗糙集理论模型和商空间理论模 成一套算法体系.如用王国胤提出的自主式知识获 型在处理复杂问题时表现出不同的优势，也表现出 取方法31.1321，利用数据本身的特点来驱动问题空 某些方面的不足.例如，粗糙集理论的优势在于对知 间的粒化，力争实现自主式的粒化过程，从而获得符 识的表示，而商空间理论的特色在于对问题结构的 合实际问题的粒化算法，可能是解决这一问题的有 讨论，而形式概念分析具有良好的层次结构等特色 如何将不同的粒计算模型有机地结合起来，发挥各 效方法 自的优势，弥补各自的缺陷，从而寻求一个更有效的 6.3粒层之间的转换 粒计算模型，是目前粒计算工作中的一个重要研究 不同粒层次之间的转换是粒计算的一个主要问 课题.张铃和张钹将商空间理论和模糊集理论结合 题.首先，不同粒层之间必须能够自由的转换，往返 起来得到的模糊商空间理论表现出良好的性能，它 自如.其次，在能够转换的基础上，确保问题的主要 能够更好地反映人类处理不确定问题的若干特 性质不变.例如商空间理论中的“保真”、“保假”原 点B).将模糊集理论和粗糙集理论结合形成模糊粗 理，是确保商空间理论能够解决复杂问题的关键.模 糙集理论和粗糙模糊集理论的文献很多，并在处理 糊集理论模型中截集具有某些性质的不变性.粗糙 不确定信息时表现出更好的性能s..但关于如 集理论模型中的核属性是属性约简的不变属性.在 何将粗糙集理论与商空间模型有机地融合起来，以 基于划分模型的粒计算模型和基于覆盖的粒计算模 及如何将粗糙集理论和形式概念分析2种智能数据 型中，不同层次之间通过Zoomingin和Zooming 分析方法融合起来，形成更有效的粒计算模型的研 out2个算子来实现粒层之间的转换.但在这些粒计 究工作很少.另外，关于论域空间上代数运算的讨 算模型中，粒层之间的转化方法各不相同，且在转换 论，在粗糙集理论和商空间理论中都不是很多，如果 过程中，如何确保主要性质不变，以及属性不变的程 能将代数中的商代数理论移植到商空间理论中，问 度等问题没有一个统一的标准.当然，不同复杂问 题求解的商空间理论的内涵将得到丰富.总之，发现 题其方法不同，主要属性不变的要求程度也可能不 更有效的粒计算模型将是研究者追求的目标 同.但如果能够建立一个用于计算不同模型的“保 6.6动态粒计算模型 性”程度的形式化数学模型，将有助于粒计算模型不 目前，绝大多数粒计算模型都是基于静态数据 同粒层之间的相互转化.虽然张钹和张铃从定性的 (信息)的处理.而很多实际问题的信息都是随着时 角度提出了商空间理论中的“保真”和“保假”原理以 间的变化而动态变化的.如网络数据、入侵检测数据 及“弱保真”和“弱保假”原理，但如何从定量的角度 和卫星检测数据等都是动态数据.如何构建基于动 去分析不同粒层之间相互转换后重要属性的不变性 态数据处理的粒计算模型是一个具有广泛应用前景 的研究工作，目前还没有研究人员对之进行讨论.如 的课题 果能够从定量的角度去研究问题在不同粒层上表现 6.7自主式粒计算模型 出来的“保真”和“保假”程度，将有利于实现不同粒 在没有领域先验知识条件下的不确定知识的主 层之间的相互转化，有助于提高用粒计算方法求解 动式学习是机器学习领域中新兴的热点问题.对于 复杂问题时的收敛速度 不确定性问题的处理，现在还没有一个能够摆脱先 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net程度的形式化数学模型 ,将是一个非常有意义的工 作. 如从粒化的复杂度、合成的复杂度以及在粒子上 求解的复杂度等多方面建立一个求解最优粒化程度 的数学模型. 该模型的建立将有效地推进粒计算在 各类复杂问题求解中的应用. 另外 ,在粒化程度已知 时 ,粒化的方法将直接决定粒化的效率. 如粗糙集模 型采用等价关系进行粒化 ,商空间模型利用等价关 系建立分层递阶的问题空间模型 ,而词计算用模糊 集得到粒子. 尽管在粒计算的各种模型中 ,一些算法 在某些具体实例上获得了成功 ,但是这些方法缺乏 通用性. 粒计算的粒化算法设计是一个复杂的问题 , 迄今为止 ,还没有一套较成熟的方法. 如果能够借鉴 现有的相关理论设计出粒计算的粒化算法 ,逐步形 成一套算法体系. 如用王国胤提出的自主式知识获 取方法[131 - 132 ] ,利用数据本身的特点来驱动问题空 间的粒化 ,力争实现自主式的粒化过程 ,从而获得符 合实际问题的粒化算法 ,可能是解决这一问题的有 效方法. 613 粒层之间的转换 不同粒层次之间的转换是粒计算的一个主要问 题. 首先 ,不同粒层之间必须能够自由的转换 ,往返 自如. 其次 ,在能够转换的基础上 ,确保问题的主要 性质不变. 例如商空间理论中的“保真”、“保假”原 理 ,是确保商空间理论能够解决复杂问题的关键. 模 糊集理论模型中截集具有某些性质的不变性. 粗糙 集理论模型中的核属性是属性约简的不变属性. 在 基于划分模型的粒计算模型和基于覆盖的粒计算模 型中 ,不同层次之间通过 Zooming2in 和 Zooming2 out 2 个算子来实现粒层之间的转换. 但在这些粒计 算模型中 ,粒层之间的转化方法各不相同 ,且在转换 过程中 ,如何确保主要性质不变 ,以及属性不变的程 度等问题没有一个统一的标准. 当然 ,不同复杂问 题 ,其方法不同 ,主要属性不变的要求程度也可能不 同. 但如果能够建立一个用于计算不同模型的“保 性”程度的形式化数学模型 ,将有助于粒计算模型不 同粒层之间的相互转化. 虽然张钹和张铃从定性的 角度提出了商空间理论中的“保真”和“保假”原理以 及“弱保真”和“弱保假”原理 ,但如何从定量的角度 去分析不同粒层之间相互转换后重要属性的不变性 的研究工作 ,目前还没有研究人员对之进行讨论. 如 果能够从定量的角度去研究问题在不同粒层上表现 出来的“保真”和“保假”程度 ,将有利于实现不同粒 层之间的相互转化 ,有助于提高用粒计算方法求解 复杂问题时的收敛速度. 614 高效的粒计算方法 粒计算方法的初衷就是求解复杂问题. 而用传 统的方法来解决实际的复杂问题 ,不管是时间复杂 度 ,还是空间复杂度 ,往往都非常高. 粒计算方法要 得到广泛的推广和应用 ,其复杂度应该低于现有的 传统方法. 虽然目前的粒计算方法在计算效率上较 传统方法有一定的优势 ,但它们处理问题的时间复 杂度都大于或等于 O( n 2 ) . 因此,研究高效粒计算方 法是一个重要的课题. 如果能获得解决问题的时间复 杂度为 O( n 1. 5 )或 O( nlg n) ,甚至更低的粒计算算法 , 将有助于提高用粒计算方法解决复杂问题的效率. 615 新的粒计算模型 词计算模型、粗糙集理论模型和商空间理论模 型在处理复杂问题时表现出不同的优势 ,也表现出 某些方面的不足. 例如 ,粗糙集理论的优势在于对知 识的表示 ,而商空间理论的特色在于对问题结构的 讨论 ,而形式概念分析具有良好的层次结构等特色. 如何将不同的粒计算模型有机地结合起来 ,发挥各 自的优势 ,弥补各自的缺陷 ,从而寻求一个更有效的 粒计算模型 ,是目前粒计算工作中的一个重要研究 课题. 张铃和张钹将商空间理论和模糊集理论结合 起来得到的模糊商空间理论表现出良好的性能 ,它 能够更好地反映人类处理不确定问题的若干特 点[35 ] . 将模糊集理论和粗糙集理论结合形成模糊粗 糙集理论和粗糙模糊集理论的文献很多 ,并在处理 不确定信息时表现出更好的性能[108 - 111 ] . 但关于如 何将粗糙集理论与商空间模型有机地融合起来 ,以 及如何将粗糙集理论和形式概念分析 2 种智能数据 分析方法融合起来 ,形成更有效的粒计算模型的研 究工作很少. 另外 ,关于论域空间上代数运算的讨 论 ,在粗糙集理论和商空间理论中都不是很多 ,如果 能将代数中的商代数理论移植到商空间理论中 ,问 题求解的商空间理论的内涵将得到丰富. 总之 ,发现 更有效的粒计算模型将是研究者追求的目标. 616 动态粒计算模型 目前 ,绝大多数粒计算模型都是基于静态数据 (信息) 的处理. 而很多实际问题的信息都是随着时 间的变化而动态变化的. 如网络数据、入侵检测数据 和卫星检测数据等都是动态数据. 如何构建基于动 态数据处理的粒计算模型是一个具有广泛应用前景 的课题. 617 自主式粒计算模型 在没有领域先验知识条件下的不确定知识的主 动式学习是机器学习领域中新兴的热点问题. 对于 不确定性问题的处理 ,现在还没有一个能够摆脱先 第 6 期 王国胤 ,等 :粒计算研究综述 · 91 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net