第2卷第6期 智能系统学报 Vol.2 Na6 2007年12月 CAAI Transactions on Intelligent Systems Dec.2007 粒计算研究综述 王国胤12，张清华2，胡军13 (1.重庆邮电大学计算机科学与技术研究所，重庆400065；2.西南交通大学信息科学与技术学院，四川成都610031； 3.西安电子科技大学电子工程学院，陕西西安710071) 摘要：粒计算(granular computing)是当前计算智能研究领域中模拟人类思维和解决复杂问题的新方法.它覆盖了 所有有关粒度的理论、方法和技术，是复杂问题求解、海量数据挖掘、模糊信息处理的有效工具.首先回顾了粒计算 研究和发展状况，介绍了粒计算的基本组成和问题，综述了粒计算的基本模型和方法，并讨论了它们之间的相互关 系，最后探讨了构建统一的粒计算模型、复杂问题空间的粒化、粒层之间的转换、高效的粒计算方法、新的粒计算模 型、动态粒计算模型、自主粒计算模型粒计算方法的模糊化以及粒计算模型的应用和推广等几个方面的关键问题 关键词：粒计算；数据挖掘，智能信息处理；粗糙集，模糊集；商空间 中图分类号：TP18文献标识码：A文章编号：1673-4785(2007)060008-19 An overvie w of granular computing WANG Guo-yin'2,ZHANG Qing-hua'2,HU Jun'3 (1.Institute of Computer Science&Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065, China;2.School of Information Science Technology,Southwest Jiaotong University,Chengdu 610031,China;3.School of Electronic Engineering,Xidian University,Xi'an 710071,China) Abstract:In the field of computational intelligence,granular computing(GrC)is a new way to simulate hu- man thinking to help solve complicated problems.GrC involves all the theories,methodologies and tech- niques of granularity,providing a powerful tool for the solution of complex problems,massive data min- ing,and fuzzy information processing.In this paper,first the current situation and the development pros- pects of GrC are introduced,then the fundamental and existing problems related to GrC are presented and its basic models and methods summarized.Finally,some future research topics about GrC are presented, such as,uniform granular computing model,granulation of complex problem space,transformation be- tween granule spaces,efficient granular computing algorithm,novel granular computing model,dynamic granular computing model,data-driven granular computing model,fuzzy granular computing method,and the applications of granular computing models,etc. Keywords granular computing;data mining;intelligent information processing;rough sets;fuzzy sets; quotient space 自Zadeh1979年发表论文“Fuzzy sets and im- 控制中的“不确定性”、区间分析里的“区间数运算”、 formation granularity'”以来，研究人员对信息粒 以及DS证据理论中的“证据”都与信息粒密切相 度化的思想产生了浓厚的兴趣.Zadeh认为很多领 关.Hobss在1985年直接用“粒度(granularity)”作 域都存在信息粒的概念，只是在不同领域中的表现 为论文题目发表论文)，讨论了粒的分解和合并，以 形式不同.自动机与系统论中的“分解与划分”、最优 及如何得到不同大小的粒，并提出了产生不同大小 粒的模型.Lin在1988年提出邻域系统并研究了邻 收稿日期：2007-04-02. 基金项目：国家自然科学基金资助项目(60573068)：重庆市教委 域系统与关系数据库之间的关系31.1996年，他在 科学技术研究资助项目(3060517) UC-Berkeley大学访问时，向Zadeh提出作“granu- 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
收稿日期 :2007204202. 基金项目 :国家自然科学基金资助项目(60573068) ;重 庆 市 教 委 科 学 技 术 研 究 资 助 项 目( KJ060517) . 第 2 卷第 6 期 智 能 系 统 学 报 Vol. 2 №. 6 2007 年 12 月 CAAI Transactions on Intelligent Systems Dec. 2007 粒计算研究综述 王国胤1 ,2 ,张清华1 ,2 ,胡 军1 ,3 (1. 重庆邮电大学 计算机科学与技术研究所 ,重庆 400065 ; 2. 西南交通大学 信息科学与技术学院 ,四川 成都 610031 ; 3. 西安电子科技大学 电子工程学院 ,陕西 西安 710071) 摘 要 :粒计算(granular computing)是当前计算智能研究领域中模拟人类思维和解决复杂问题的新方法. 它覆盖了 所有有关粒度的理论、方法和技术 ,是复杂问题求解、海量数据挖掘、模糊信息处理的有效工具. 首先回顾了粒计算 研究和发展状况 ,介绍了粒计算的基本组成和问题 ,综述了粒计算的基本模型和方法 ,并讨论了它们之间的相互关 系 ,最后探讨了构建统一的粒计算模型、复杂问题空间的粒化、粒层之间的转换、高效的粒计算方法、新的粒计算模 型、动态粒计算模型、自主粒计算模型、粒计算方法的模糊化以及粒计算模型的应用和推广等几个方面的关键问题. 关键词 :粒计算 ;数据挖掘 ;智能信息处理 ;粗糙集 ;模糊集 ;商空间 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0620008219 An overview of granular computing WAN G Guo2yin 1 ,2 ,ZHAN G Qing2hua 1 ,2 , HU J un 1 ,3 (1. Institute of Computer Science & Technology , Chongqing University of Posts and Telecommunications , Chongqing 400065 , China ;2. School of Information Science & Technology , Southwest Jiaotong University , Chengdu 610031 ,China ; 3. School of Electronic Engineering , Xidian University , Xi’an 710071 ,China) Abstract :In t he field of comp utational intelligence , granular comp uting ( GrC) is a new way to simulate hu2 man t hinking to help solve complicated problems. GrC involves all the t heories , met hodologies and tech2 niques of granularity , providing a powerf ul tool for t he solution of complex problems , massive data min2 ing , and f uzzy information processing. In t his paper , first t he current sit uation and t he development pros2 pects of GrC are introduced , t hen t he f undamental and existing problems related to GrC are presented and its basic models and met hods summarized. Finally , some f uture research topics about GrC are p resented , such as , uniform granular comp uting model , granulation of complex problem space , transformation be2 tween granule spaces , efficient granular comp uting algorit hm , novel granular comp uting model , dynamic granular comp uting model , data2driven granular comp uting model , f uzzy granular comp uting met hod , and t he applications of granular comp uting models , etc. Keywords :granular comp uting ; data mining ; intelligent information processing ; rough sets; f uzzy sets ; quotient space 自 Zadeh 1979 年发表论文“Fuzzy sets and in2 formation granularity”以来[1 ] ,研究人员对信息粒 度化的思想产生了浓厚的兴趣. Zadeh 认为很多领 域都存在信息粒的概念 ,只是在不同领域中的表现 形式不同. 自动机与系统论中的“分解与划分”、最优 控制中的“不确定性”、区间分析里的“区间数运算”、 以及 D2S 证据理论中的“证据”都与信息粒密切相 关. Hobss 在 1985 年直接用“粒度 (granularity) ”作 为论文题目发表论文[2 ] ,讨论了粒的分解和合并 ,以 及如何得到不同大小的粒 ,并提出了产生不同大小 粒的模型. Lin 在 1988 年提出邻域系统并研究了邻 域系统与关系数据库之间的关系[3 ] . 1996 年 ,他在 UC2Berkeley 大学访问时 ,向 Zadeh 提出作“granu2 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第6期 王因胤，等：粒计算研究综述 lar computing”的研究，Zadeh称之为“granular 认识和推广，2003年张铃和张钹将模糊概念与商空 mathematics'”,Lin改称为“granular computing”,并 间理论结合，提出模糊商空间理论，为粒计算提供了 缩写成GC.他发表了一系列关于粒计算与邻域系 新的数学模型和工具，并成功应用于数据挖掘等领 统的论文o1,主要是研究二元关系（邻域系统、 域3135).2002年苗夺谦等人[361对知识的粒计算进 Rough集和信任函数)下的粒计算模型，论述基于 行探讨，引入属性的重要度，并在求最小属性约简方 邻域系统的粒计算在粒结构、粒表示和粒应用等方 面得到应用.王飞跃等人3刃对词计算和语言动力学 面的问题，讨论了粒计算中的模糊集和粗糙集方法， 进行了探讨，以词计算为基础，对问题进行动态描 并将粒计算方法引入数据挖掘和机器发现.依据人 述、分析和综合，提出了设计、控制和评估的语言动 们在解决问题时能从不同的粒度世界去分析和观察 力学系统.王国胤等人.提出了基于容差关系的 同一问题，并且很容易地从一个粒度世界转到另一 粒计算模型，利用属性值上的容差关系给出了不完 个粒度世界，张钱和张铃在1990年针对复杂问题求 备信息系统的粒表示、粒运算规则和粒分解算法，同 解，建立了一种复杂问题求解的商结构形式化体系， 时结合粗糙集中的属性约简问题，提出了不完备信 给出了一套解决信息融合、启发式搜索路径规划和 息系统在粒表示下属性必要性的判定条件，对粒计 推理等问题的理论和算法1.)，1997年，Zadeh进 算方法在规则提取方面进行了探索.郑征等人5.4列 一步指出]，世上有3个基本概念构成人类认知的 提出了相容粒度空间模型，并在图像纹理识别和数 基础：粒化、组织及因果关系.其中，粒化是整体分解 据挖掘中取得了成功，他们认为，人类具有根据具体 为部分，组织是部分结合为整体，而因果关系则涉及 的任务特性把相关数据和知识泛化或者特化成不同 原因与结果间的联系.物体的粒化产生一系列的粒 程度、不同大小的粒的能力，以及进一步根据这些粒 子，每个粒子即为一簇点（物体），这些点难以区别， 和粒之间的关系进行问题求解的能力.卜东波等 或相似、或接近、或以某种功能结合在一起.一般来 人4s1从信息粒度的角度剖析聚类和分类技术，试图 说，粒化在本质上是分层次的，时间可粒化为年、月、 使用信息粒度原理的框架来统一聚类和分类，指出 日、小时、分、秒就是大家熟悉的例子 从信息粒度的观点来看，聚类是在一个统一的粒度 在Lin的研究基础上，Yao结合邻域系统对粒 下进行计算，而分类却是在不同的粒度下进行计算 计算进行了详细的研究4.161，发表了一系列研究成 并根据粒度原理设计了一种新的分类算法，大规模 果72！，并将它应用于知识挖掘等领域，建立了概 中文文本分类的应用实践表明，这种分类算法有较 念之间的if-then规则与粒度集合之间的包含关系， 强的泛化能力.Zhang等人9.so1对粒神经网络进行 提出利用由所有划分构成的格求解一致分类问题， 了探讨，并在高效知识发现中得到很好的应用.李道 为数据挖掘提供了新的方法和视角，结合粗糙集理 国等人5川研究了基于粒向量空间的人工神经网络 论，Yao探讨了粒计算方法在机器学习、数据分析、 模型，在一定程度上提高了人工神经网络的时效性、 数据挖掘、规则提取、智能数据处理和粒逻辑等方面 知识表达的可理解性.杜伟林等人52]根据概念格[53] 的应用.Yao给出了粒计算的3种观点22]： 与粒度划分在概念聚类的过程中都是基于不同层次 1)从哲学角度看，粒计算是一种结构化的思想 的概念结构来进行分类表示，而且粒度划分本身构 方法； 成一个格结构的特点，研究了概念格与粒度划分格 2)从应用角度看，粒计算是一个通用的结构化 在概念描述与概念层次转换之间的联系，通过对概 问题求解方法； 念的分层递阶来进行概念的泛化与例化，使概念在 3)从计算角度看，粒计算是一个信息处理的典 递阶方面忽略不必要的冗余信息.YagerIs4探讨了 型方法 基于粒计算的学习方法和应用.Lin51在2006年粒 随着粒计算研究的发展，近年来国内外又有很 计算国际会议上提出了新的研究思路“infrastruc- 多学者加入到了粒计算研究的领域.为了探讨粗糙 tures for AFengineering”.同时，Bargiela和Pe 集理论在各种环境下的应用，Skowron2s.刃以包含 dryczls61也从各个侧面对粒计算的根源和实质进行 度概念来研究粒近似空间上的Rough下近似和 了详细的探讨和总结.Yager指出，发展信息粒的操 Rough上近似.刘清I28.01在Rough逻辑的基础上， 作方法是当前粒计算研究的一个重要任务5 提出了粒-逻辑的概念(G逻辑)，构造了这种逻辑 1 的近似推理系统，并应用于医疗诊断.近几年来，在 粒计算的基本组成 掀起粒计算研究的热潮中，商空间理论被人们广泛 粒计算的基本组成主要包括3部分：粒子粒层 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved http://www.cnki.net
lar comp uting”的研 究 , Zadeh 称 之为“granular mat hematics”,Lin 改称为“granular comp uting”,并 缩写成 GrC. 他发表了一系列关于粒计算与邻域系 统的论文[4 - 10 ] ,主要是研究二元关系 (邻域系统、 Rough 集和信任函数) 下的粒计算模型 ,论述基于 邻域系统的粒计算在粒结构、粒表示和粒应用等方 面的问题 ,讨论了粒计算中的模糊集和粗糙集方法 , 并将粒计算方法引入数据挖掘和机器发现. 依据人 们在解决问题时能从不同的粒度世界去分析和观察 同一问题 ,并且很容易地从一个粒度世界转到另一 个粒度世界 ,张钹和张铃在 1990 年针对复杂问题求 解 ,建立了一种复杂问题求解的商结构形式化体系 , 给出了一套解决信息融合、启发式搜索、路径规划和 推理等问题的理论和算法[11 - 12 ] . 1997 年 ,Zadeh 进 一步指出[13 ] ,世上有 3 个基本概念构成人类认知的 基础 :粒化、组织及因果关系. 其中 ,粒化是整体分解 为部分 ,组织是部分结合为整体 ,而因果关系则涉及 原因与结果间的联系. 物体的粒化产生一系列的粒 子 ,每个粒子即为一簇点 (物体) ,这些点难以区别 , 或相似、或接近、或以某种功能结合在一起. 一般来 说 ,粒化在本质上是分层次的 ,时间可粒化为年、月、 日、小时、分、秒就是大家熟悉的例子. 在 Lin 的研究基础上 , Yao 结合邻域系统对粒 计算进行了详细的研究[14 - 16 ] ,发表了一系列研究成 果[17 - 22 ] ,并将它应用于知识挖掘等领域 ,建立了概 念之间的 if2t hen 规则与粒度集合之间的包含关系 , 提出利用由所有划分构成的格求解一致分类问题 , 为数据挖掘提供了新的方法和视角. 结合粗糙集理 论 , Yao 探讨了粒计算方法在机器学习、数据分析、 数据挖掘、规则提取、智能数据处理和粒逻辑等方面 的应用. Yao 给出了粒计算的 3 种观点[22 ] : 1) 从哲学角度看 ,粒计算是一种结构化的思想 方法 ; 2) 从应用角度看 ,粒计算是一个通用的结构化 问题求解方法 ; 3) 从计算角度看 ,粒计算是一个信息处理的典 型方法. 随着粒计算研究的发展 ,近年来国内外又有很 多学者加入到了粒计算研究的领域. 为了探讨粗糙 集理论在各种环境下的应用 ,Skowron [23 - 27 ] 以包含 度概念来研究粒近似空间上的 Rough 下近似和 Rough 上近似. 刘清[ 28 - 30 ]在 Rough 逻辑的基础上 , 提出了粒 - 逻辑的概念( G2逻辑) ,构造了这种逻辑 的近似推理系统 ,并应用于医疗诊断. 近几年来 ,在 掀起粒计算研究的热潮中 ,商空间理论被人们广泛 认识和推广 ,2003 年张铃和张钹将模糊概念与商空 间理论结合 ,提出模糊商空间理论 ,为粒计算提供了 新的数学模型和工具 ,并成功应用于数据挖掘等领 域[31 - 35 ] . 2002 年苗夺谦等人[36 ] 对知识的粒计算进 行探讨 ,引入属性的重要度 ,并在求最小属性约简方 面得到应用. 王飞跃等人[ 37 ]对词计算和语言动力学 进行了探讨 ,以词计算为基础 ,对问题进行动态描 述、分析和综合 ,提出了设计、控制和评估的语言动 力学系统. 王国胤等人[38 - 44 ]提出了基于容差关系的 粒计算模型 ,利用属性值上的容差关系给出了不完 备信息系统的粒表示、粒运算规则和粒分解算法 ,同 时结合粗糙集中的属性约简问题 ,提出了不完备信 息系统在粒表示下属性必要性的判定条件 ,对粒计 算方法在规则提取方面进行了探索. 郑征等人[45 - 47 ] 提出了相容粒度空间模型 ,并在图像纹理识别和数 据挖掘中取得了成功 ,他们认为 ,人类具有根据具体 的任务特性把相关数据和知识泛化或者特化成不同 程度、不同大小的粒的能力 ,以及进一步根据这些粒 和粒之间的关系进行问题求解的能力. 卜东波等 人[48 ]从信息粒度的角度剖析聚类和分类技术 ,试图 使用信息粒度原理的框架来统一聚类和分类 ,指出 从信息粒度的观点来看 ,聚类是在一个统一的粒度 下进行计算 ,而分类却是在不同的粒度下进行计算 , 并根据粒度原理设计了一种新的分类算法 ,大规模 中文文本分类的应用实践表明 ,这种分类算法有较 强的泛化能力. Zhang 等人[49 - 50 ]对粒神经网络进行 了探讨 ,并在高效知识发现中得到很好的应用. 李道 国等人[ 51 ]研究了基于粒向量空间的人工神经网络 模型 ,在一定程度上提高了人工神经网络的时效性、 知识表达的可理解性. 杜伟林等人[52 ]根据概念格[53 ] 与粒度划分在概念聚类的过程中都是基于不同层次 的概念结构来进行分类表示 ,而且粒度划分本身构 成一个格结构的特点 ,研究了概念格与粒度划分格 在概念描述与概念层次转换之间的联系 ,通过对概 念的分层递阶来进行概念的泛化与例化 ,使概念在 递阶方面忽略不必要的冗余信息. Yager [54 ] 探讨了 基于粒计算的学习方法和应用. Lin [55 ] 在 2006 年粒 计算国际会议上提出了新的研究思路“infrastruc2 t ures for AI2engineering”. 同 时 , Bargiela 和 Pe2 drycz [56 ] 也从各个侧面对粒计算的根源和实质进行 了详细的探讨和总结. Yager 指出 ,发展信息粒的操 作方法是当前粒计算研究的一个重要任务[ 57 ] . 1 粒计算的基本组成 粒计算的基本组成主要包括 3 部分 :粒子、粒层 第 6 期 王国胤 ,等 :粒计算研究综述 ·9 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·10· 智能系统学报 第2卷 和粒结构」 以及在一个层次结构中的不同层次.虽然一个粒子 1.1粒子 在某个粒层上被视为一个整体，但粒子内部元素（子 粒子是构成粒计算模型的最基本元素5.s),是 粒子)的结构在问题求解时也很重要，因为它能提供 粒计算模型的原语.一个粒可以被解释为许多小颗 粒子更为详细的特性.而在同一层上的粒子之间也 粒构成的一个大个体，现实生活中，粒子无处不在， 具有某种特殊的结构，它们可能是相互独立，或者部 如在地图上观察洲、国家、海洋、大陆和山脉等是一 分包含.如果同一粒层上的粒子之间的独立性越好 些粗的粒子（大的粒子），观察省、市、区等是一些中 可能问题求解后合并起来越方便；反之，如果粒子之 等的粒子，而观察街道、饭店、机场等是一些相对较 间的相关性越好，则问题求解后的合并工作相对越 小的粒子.一个粒子可以被同时看作是由内部属性 繁杂.粒子网的层次结构是对整个问题空间的概括， 描述的个体元素的集合，以及由它的外部属性所描 它的复杂性在一定程度上决定了问题求解的复杂 述的整体.一个粒子的存在仅仅在一个特定的环境 程度 中才有意义.一个粒子的元素可以是粒子，一个粒子 也可以是另外一个粒子的元素.而衡量粒子“大小” 2粒计算的基本问题 的概念是粒度，一般来讲，对粒子进行“量化”时用粒 粒计算中存在2个最基本的问题，即粒化和粒 度来反映粒化的程度5) 的计算.问题空间的粒化是指将问题空间分解为许 1.2粒层 多子空间，或是基于有用的信息和知识将问题空间 按照某个实际需求的粒化准则得到的所有粒子 中的个体聚集成不同的类，这些类称之为粒.粒中的 的全体构成一个粒层，是对问题空间的一种抽象化 元素可以理解为对应概念的实例.可以把粒计算和 描述.根据某种关系或算子，问题空间产生相应的粒 概念生成、知识发现和数据挖掘联系起来，因为概念 子.同一层的粒子内部往往具有相同的某种性质或 生成的目的之一是对具有某些概念的粒的表示、特 功能.由于粒化的程度不同，导致同一问题空间会产 征化、描述和解释，而知识发现和数据挖掘就是在粒 生不同的粒层.粒层的内部结构是指在该粒层上的 之间建立关联和因果等联系 各个粒子组成的论域的结构，即粒子之间的相互关 2.1粒化 系.在问题求解中，选择最合适的粒层对于问题求解 粒化是问题求解空间的一个构造性过程，它可 尤为关键，因为，在不同粒层求解同一问题的复杂度 以简单理解为在给定粒化准则下得到一个粒层的过 往往不同.在高一级粒层上的粒子能够分解成为下 程，是粒计算基础单元的构建，包括粒子、粒视图、粒 一级粒层上的多个粒子（增加一些属性），在低一级 网和层次结构.在不同的粒化准则下就得到多个粒 粒层上的多个粒子可以合并成高一级粒层上的粒子 层，进而得到粒层的网络结构.通常的粒化方法有自 (忽略一些属性).粒计算模型的主要目标是能够在 顶而下通过分解粗粒子得到细粒子的方法，和自底 不同粒层上进行问题求解，且不同粒层上的解能够 向上将细粒子通过合并得到粗粒子的方法.粒化过 相互转化. 程是粒计算的必要过程.问题空间的粒化过程主要 1.3粒结构 涉及粒化准则、粒化算法（方法）粒子和粒结构的表 一个粒化准则对应一个粒层，不同的粒化准则 示（描述）以及粒子和粒结构的定性（定量）描述等问 对应多个粒层，它反应了人们从不同角度、不同侧面 题).粒化准则主要是语义方面的问题，解决为什 来观察问题、理解问题、求解问题.所有粒层之间的 么2个对象能放进同一个粒子内的问题.它是根据 相互联系构成一个关系结构，称为粒结构2】.粒结 实际问题求解的具体需求和具体精度要求得到的 构给出了一个系统或者问题的结构化描述.通过从 粒化准则的一个基本要求是忽略掉那些无关紧要的 系统思维、复杂系统理论和层次结构理论（技术）中 细节，从而达到降低问题求解复杂度的目的.粒化方 得到的启发至少需要确定一个粒结构网2)中3个 法面对实际问题，回答如何对问题空间进行粒化，采 层次的结构：粒子的内部结构、粒子集结构和粒子网 用什么算法或工具实现粒层的构造，它属于算法方 的层次结构.粒子集的集体结构可以看作是全部层 面的问题.如在粗糙集理论中，如何对对象集进行划 次结构中一个层次或者一个粒度视图中的结构.它 分产生粒层，如何高效实现属性的约简等问题.粒子 本身可以看作是粒的内部连接网络.对于同一个系 的结构描述主要是用粒化方法得到的粒子，如何用 统或者同一个问题，许多解释和描述可能是同时存 形式化的语言表述出来，以便后面进行计算.例如在 在的.所以，粒结构需要被模型化为多种层次结构， 粗糙集理论模型中，粒子的表示可能是一个子集而 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.ne
和粒结构. 111 粒 子 粒子是构成粒计算模型的最基本元素[58 - 59 ] ,是 粒计算模型的原语. 一个粒可以被解释为许多小颗 粒构成的一个大个体 ,现实生活中 ,粒子无处不在 , 如在地图上观察洲、国家、海洋、大陆和山脉等是一 些粗的粒子(大的粒子) ,观察省、市、区等是一些中 等的粒子 ,而观察街道、饭店、机场等是一些相对较 小的粒子. 一个粒子可以被同时看作是由内部属性 描述的个体元素的集合 ,以及由它的外部属性所描 述的整体. 一个粒子的存在仅仅在一个特定的环境 中才有意义. 一个粒子的元素可以是粒子 ,一个粒子 也可以是另外一个粒子的元素. 而衡量粒子“大小” 的概念是粒度 ,一般来讲 ,对粒子进行“量化”时用粒 度来反映粒化的程度[59 ] . 112 粒 层 按照某个实际需求的粒化准则得到的所有粒子 的全体构成一个粒层 ,是对问题空间的一种抽象化 描述. 根据某种关系或算子 ,问题空间产生相应的粒 子. 同一层的粒子内部往往具有相同的某种性质或 功能. 由于粒化的程度不同 ,导致同一问题空间会产 生不同的粒层. 粒层的内部结构是指在该粒层上的 各个粒子组成的论域的结构 ,即粒子之间的相互关 系. 在问题求解中 ,选择最合适的粒层对于问题求解 尤为关键 ,因为 ,在不同粒层求解同一问题的复杂度 往往不同. 在高一级粒层上的粒子能够分解成为下 一级粒层上的多个粒子 (增加一些属性) ,在低一级 粒层上的多个粒子可以合并成高一级粒层上的粒子 (忽略一些属性) . 粒计算模型的主要目标是能够在 不同粒层上进行问题求解 ,且不同粒层上的解能够 相互转化. 113 粒结构 一个粒化准则对应一个粒层 ,不同的粒化准则 对应多个粒层 ,它反应了人们从不同角度、不同侧面 来观察问题、理解问题、求解问题. 所有粒层之间的 相互联系构成一个关系结构 ,称为粒结构[20 ] . 粒结 构给出了一个系统或者问题的结构化描述. 通过从 系统思维、复杂系统理论和层次结构理论 (技术) 中 得到的启发至少需要确定一个粒结构网[20 ] 中 3 个 层次的结构 :粒子的内部结构、粒子集结构和粒子网 的层次结构. 粒子集的集体结构可以看作是全部层 次结构中一个层次或者一个粒度视图中的结构. 它 本身可以看作是粒的内部连接网络. 对于同一个系 统或者同一个问题 ,许多解释和描述可能是同时存 在的. 所以 ,粒结构需要被模型化为多种层次结构 , 以及在一个层次结构中的不同层次. 虽然一个粒子 在某个粒层上被视为一个整体 ,但粒子内部元素(子 粒子) 的结构在问题求解时也很重要 ,因为它能提供 粒子更为详细的特性. 而在同一层上的粒子之间也 具有某种特殊的结构 ,它们可能是相互独立 ,或者部 分包含. 如果同一粒层上的粒子之间的独立性越好 , 可能问题求解后合并起来越方便 ;反之 ,如果粒子之 间的相关性越好 ,则问题求解后的合并工作相对越 繁杂. 粒子网的层次结构是对整个问题空间的概括 , 它的复杂性在一定程度上决定了问题求解的复杂 程度. 2 粒计算的基本问题 粒计算中存在 2 个最基本的问题 ,即粒化和粒 的计算. 问题空间的粒化是指将问题空间分解为许 多子空间 ,或是基于有用的信息和知识将问题空间 中的个体聚集成不同的类 ,这些类称之为粒. 粒中的 元素可以理解为对应概念的实例. 可以把粒计算和 概念生成、知识发现和数据挖掘联系起来 ,因为概念 生成的目的之一是对具有某些概念的粒的表示、特 征化、描述和解释 ,而知识发现和数据挖掘就是在粒 之间建立关联和因果等联系. 211 粒 化 粒化是问题求解空间的一个构造性过程 ,它可 以简单理解为在给定粒化准则下得到一个粒层的过 程 ,是粒计算基础单元的构建 ,包括粒子、粒视图、粒 网和层次结构. 在不同的粒化准则下就得到多个粒 层 ,进而得到粒层的网络结构. 通常的粒化方法有自 顶而下通过分解粗粒子得到细粒子的方法 ,和自底 向上将细粒子通过合并得到粗粒子的方法. 粒化过 程是粒计算的必要过程. 问题空间的粒化过程主要 涉及粒化准则、粒化算法(方法) 、粒子和粒结构的表 示(描述) 以及粒子和粒结构的定性(定量) 描述等问 题[59 ] . 粒化准则主要是语义方面的问题 ,解决为什 么 2 个对象能放进同一个粒子内的问题. 它是根据 实际问题求解的具体需求和具体精度要求得到的. 粒化准则的一个基本要求是忽略掉那些无关紧要的 细节 ,从而达到降低问题求解复杂度的目的. 粒化方 法面对实际问题 ,回答如何对问题空间进行粒化 ,采 用什么算法或工具实现粒层的构造 ,它属于算法方 面的问题. 如在粗糙集理论中 ,如何对对象集进行划 分产生粒层 ,如何高效实现属性的约简等问题. 粒子 的结构描述主要是用粒化方法得到的粒子 ,如何用 形式化的语言表述出来 ,以便后面进行计算. 例如在 粗糙集理论模型中 ,粒子的表示可能是一个子集. 而 · 01 · 智 能 系 统 学 报 第 2 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第6期 王因胤，等：粒计算研究综述 ·11 在概念格理论中，粒子的表述就是一个概念，它包括 间3)，基于概念格产生概念信息粒和概念知识 概念的外延（一个对象子集）和内涵（一个属性子集） 粒]，基于邻域系统产生邻域粒子1等等 2部分.粒结构的描述往往形式多样，在商空间理论 总之，粒计算是一个多准则学科，它从许多领域 模型中，粒结构是一种分层递阶的结构，在概念格模 中获得其基本的思想、准则和方法，是基于不同层次 型中，粒结构是一种Hasse图.粒子和粒结构的定 粒度和细节的问题求解的一般性理论.在粒计算的 性、定量描述主要指粒子和粒结构的大小（主要是指 “大伞”下进行统一的研究，可以发现不同学科之间 粒度的结果)和复杂性度量.当前，成功的粒化方法 原理的关联，它与具体的学科研究是相互独立 往往都是以将解空间形成划分空间为主要的目标， 的，.一旦掌握了粒计算中的结构化思维和结构化 这样便于将子空间上的解合成原问题空间的解，商 问题求解的抽象思想，就可以很容易地在任何领域 空间理论就是这样一个成功的实例.当然，如果用某 中运用 种粒化方法形成的解空间不是划分（如覆盖），这将 3粒计算的主要模型与理论方法 增加合成的复杂度 2.2粒的计算 3.1词计算模型 以粒子为运算对象进行问题的求解或推理，是 高标准的精确表达，普遍存在于数学、化学、工 狭义的粒计算.粒计算可以通过系统访问粒结构来 程学和另外一些“硬”科学之中，而不精确表达却普 解决问题，包括在层次结构中向上和向下2个方向 遍存在于社会、心理、政治、历史、哲学、语言、人类 的交互，以及在同一层次内的移动，主要分为2 学、文学、文艺及相关的领域中.针对复杂且非明 种51：同一粒层上粒子之间相互转换和推理，不同 晰定义的现象，无法用精确的数学方法来描述，但可 粒层上粒子之间的转换或推理.不同粒层之间的联 以用一些程度词语，如不很可能、十分不可能、极不 系可以由映射来表示，在不同粒层上同一问题以不 可能等，来对某些模糊概念进行修饰.尽管普通的精 同的粒度、不同的细节表示，粒层之间的映射就建立 确方法（如数学）在某些科学领域应用相当广泛，也 了同一问题的不同细节描述之间的关系.商空间理 一直尝试着应用到人文学科中，但人们在长期的实 论模型就是通过自然投影建立了分层递阶的商空间 践中已经清楚地认识到精确的方法应用到人文学科 链式结构.粒计算的主要特点是同一问题的解可以 有很大的局限性.面对巨大而又复杂的人文学科系 在不同粒层之间自由转化.正是基于这一点，人们才 统，区别于传统方法的新方法模糊计算方法被 能用粒计算方法高效地实现复杂问题的求解.模糊 Zadeh提出.在人类的认识中，粒的模糊性直接源于 商空间上的分层递阶结构可以通过模糊等价关系的 无区别相似性、接近性以及功能性等这些概念的模 截关系建立相应的转化联系；粗糙集理论中的划分 糊性.人类具有在不精确性、部分知识、部分确定以 粒度可以通过属性的增加或删减来控制；而概念格 及部分真实的环境下作出合理决策这一不同寻常的 理论模型中的概念粒子的相互转化可以通过改变概 能力，而模糊信息粒化正是这种能力的基础.在模糊 念的内涵来实现.这些转化虽然方式不同，但一个共 逻辑中，模糊信息粒化是语言变量、模糊“if-then”规 同的特点是在转化的过程中，问题求解的重要性质 则以及模糊图的基础 必须能在不同粒层上表现出来，这也是评价粒化方 词计算(computing with words)是用词语代替 法好坏的一个重要指标.如果在粒化后粒层之间的 数进行计算及推理的方法62！.如何利用语言进行推 相互转化过程中，某些重要属性不能体现出来，这不 理判断，这就要进行词计算.信息粒化为词计算提供 但不利于问题的求解，反而会导致问题求解过程发 了前提条件，词计算在信息粒度、语言变量和约束概 散，从而增加问题求解的复杂度.商空间理论模型中 念上产生了自己的理论与方法，意在解决模糊集合 的“保真”和“保假”原理使得粒化后形成的商空间具 论的数值化隶属度函数表示法的局限性、表达的概 有“保序”性，使得问题求解的搜索空间大大减少，复 念缺乏前后联系、逻辑表达和算子实现的复杂性等 杂度由相乘变为相加 问题，使它们能够更符合人类的思维特点.词计算有 粒计算的2个基本问题中，粒化是关键，它直接 狭义和广义2个方面的概念.狭义的模糊词计算理 决定粒计算的成功与否.因此，粒化方法是人们研究 论是指利用通常意义下的数学概念和运算（如加、 的热点问题.目前，粒化方法很多，如基于等价关系 减、乘、除等)构造的带有语义的模糊数值型的词计 的划分产生粒子)，基于模糊集产生模糊信息 算的理论体系；广义的词计算理论统指用词进行推 粒口，基于模糊等价关系截集产生分层递阶粒空 理、用词构建原型系统和用词编程，前者是后者的基 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
在概念格理论中 ,粒子的表述就是一个概念 ,它包括 概念的外延(一个对象子集) 和内涵(一个属性子集) 2 部分. 粒结构的描述往往形式多样 ,在商空间理论 模型中 ,粒结构是一种分层递阶的结构 ,在概念格模 型中 ,粒结构是一种 Hasse 图. 粒子和粒结构的定 性、定量描述主要指粒子和粒结构的大小(主要是指 粒度的结果) 和复杂性度量. 当前 ,成功的粒化方法 往往都是以将解空间形成划分空间为主要的目标 , 这样便于将子空间上的解合成原问题空间的解 ,商 空间理论就是这样一个成功的实例. 当然 ,如果用某 种粒化方法形成的解空间不是划分 (如覆盖) ,这将 增加合成的复杂度. 212 粒的计算 以粒子为运算对象进行问题的求解或推理 ,是 狭义的粒计算. 粒计算可以通过系统访问粒结构来 解决问题 ,包括在层次结构中向上和向下 2 个方向 的交互 ,以及在同一层次内的移动 ,主要分为 2 种[59 ] :同一粒层上粒子之间相互转换和推理 ,不同 粒层上粒子之间的转换或推理. 不同粒层之间的联 系可以由映射来表示 ,在不同粒层上同一问题以不 同的粒度、不同的细节表示 ,粒层之间的映射就建立 了同一问题的不同细节描述之间的关系. 商空间理 论模型就是通过自然投影建立了分层递阶的商空间 链式结构. 粒计算的主要特点是同一问题的解可以 在不同粒层之间自由转化. 正是基于这一点 ,人们才 能用粒计算方法高效地实现复杂问题的求解. 模糊 商空间上的分层递阶结构可以通过模糊等价关系的 截关系建立相应的转化联系 ;粗糙集理论中的划分 粒度可以通过属性的增加或删减来控制 ;而概念格 理论模型中的概念粒子的相互转化可以通过改变概 念的内涵来实现. 这些转化虽然方式不同 ,但一个共 同的特点是在转化的过程中 ,问题求解的重要性质 必须能在不同粒层上表现出来 ,这也是评价粒化方 法好坏的一个重要指标. 如果在粒化后粒层之间的 相互转化过程中 ,某些重要属性不能体现出来 ,这不 但不利于问题的求解 ,反而会导致问题求解过程发 散 ,从而增加问题求解的复杂度. 商空间理论模型中 的“保真”和“保假”原理使得粒化后形成的商空间具 有“保序”性 ,使得问题求解的搜索空间大大减少 ,复 杂度由相乘变为相加. 粒计算的 2 个基本问题中 ,粒化是关键 ,它直接 决定粒计算的成功与否. 因此 ,粒化方法是人们研究 的热点问题. 目前 ,粒化方法很多 ,如基于等价关系 的划分产生粒子[17 ] , 基于模糊集产生模糊信息 粒[1 ] ,基于模糊等价关系截集产生分层递阶粒空 间[35 ] ,基于概念格产生概念信息粒和概念知识 粒[60 ] ,基于邻域系统产生邻域粒子[3 ]等等. 总之 ,粒计算是一个多准则学科 ,它从许多领域 中获得其基本的思想、准则和方法 ,是基于不同层次 粒度和细节的问题求解的一般性理论. 在粒计算的 “大伞”下进行统一的研究 ,可以发现不同学科之间 原理的关联 , 它与具体的学科研究是相互独立 的[59 ] . 一旦掌握了粒计算中的结构化思维和结构化 问题求解的抽象思想 ,就可以很容易地在任何领域 中运用. 3 粒计算的主要模型与理论方法 311 词计算模型 高标准的精确表达 ,普遍存在于数学、化学、工 程学和另外一些“硬”科学之中 ,而不精确表达却普 遍存在于社会、心理、政治、历史、哲学、语言、人类 学、文学、文艺及相关的领域中[61 ] . 针对复杂且非明 晰定义的现象 ,无法用精确的数学方法来描述 ,但可 以用一些程度词语 ,如不很可能、十分不可能、极不 可能等 ,来对某些模糊概念进行修饰. 尽管普通的精 确方法(如数学) 在某些科学领域应用相当广泛 ,也 一直尝试着应用到人文学科中 ,但人们在长期的实 践中已经清楚地认识到精确的方法应用到人文学科 有很大的局限性. 面对巨大而又复杂的人文学科系 统 ,区别于传统方法的新方法 ———模糊计算方法被 Zadeh 提出. 在人类的认识中 ,粒的模糊性直接源于 无区别、相似性、接近性以及功能性等这些概念的模 糊性. 人类具有在不精确性、部分知识、部分确定以 及部分真实的环境下作出合理决策这一不同寻常的 能力 ,而模糊信息粒化正是这种能力的基础. 在模糊 逻辑中 ,模糊信息粒化是语言变量、模糊“if2then”规 则以及模糊图的基础. 词计算(comp uting with words) 是用词语代替 数进行计算及推理的方法[62 ] . 如何利用语言进行推 理判断 ,这就要进行词计算. 信息粒化为词计算提供 了前提条件 ,词计算在信息粒度、语言变量和约束概 念上产生了自己的理论与方法 ,意在解决模糊集合 论的数值化隶属度函数表示法的局限性、表达的概 念缺乏前后联系、逻辑表达和算子实现的复杂性等 问题 ,使它们能够更符合人类的思维特点. 词计算有 狭义和广义 2 个方面的概念. 狭义的模糊词计算理 论是指利用通常意义下的数学概念和运算 (如加、 减、乘、除等) 构造的带有语义的模糊数值型的词计 算的理论体系 ;广义的词计算理论统指用词进行推 理、用词构建原型系统和用词编程 ,前者是后者的基 第 6 期 王国胤 ,等 :粒计算研究综述 · 11 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·12 智能系统学报 第2卷 础631.模糊逻辑在词计算中起中心作用，它可以近 (linguistic dynamic systems,LDS),并通过融合几 似地被认为与词计算相同21.在词计算中存在2个 个不同领域的概念和方法)，提出基于词计算的语 核心问题：模糊约束的表现问题和模糊约束的繁殖 言动力学系统的计算理论框架，根据这个计算理论 问题，它们是模糊信息粒化的基本准则 框架，利用常规或传统数值动力学系统中己有的成 信息粒化(information granulation)是粒化的 熟概念和方法，对语言动力学系统进行动力学分析、 一种形式.在众多的信息粒化中，非模糊粒化的方法 设计控制和性能评估.这些研究的目的是建立连接 很多，如将问题求解空间形成划分空间，每个粒子都 人类的语言知识表示与计算机的数字知识表示的桥 是精确的.但这种粒化方法不能解决很多现实问题， 梁，成为下一代智能化人机交互的理论基础之一 如将人的头部粒化为脸、鼻子、额头、耳朵、头盖、脖 总之，词计算理论和方法对于复杂信息系统的 子等粒子，这些粒子之间没有明确的分界线，它们都 模糊推理和控制非常重要，但由于自身的局限性，它 是模糊的粒子.模糊信息粒化是传统信息粒化的一 必须和其他理论体系相结合，才能更有效地处理复 种推广.模糊信息粒化理论I6.6s1(theory of fuzzy 杂信息 information granulation,TFIG建立在模糊逻辑和 3.2粗糙集模型 信息粒化方法基础之上，是从人类利用模糊信息粒 一个对象属于某个集合的程度随着属性粒度的 化方式中获得的启发，其方法的实质是数学 不同而不同，为了更好地刻画集合边界的模糊性，波 Zadeh指出6)，除模糊逻辑外，没有一种方法 兰学者Pawlak3]在20世纪80年代提出了粗糙集 能提供概念框架及相关技术，它能在模糊信息粒化 理论，其本质思想是利用不可分辨关系（等价关系） 起主导作用.继Zadeh之后，许多学者开始了有关词 来建立论域的一个划分，得到不区分的等价类（即不 计算的研究工作，Wang61编写了词计算一书.广义 同属性粒度下的概念粒)，从而建立一个近似空间 词计算理论的研究工作，中国刚刚起步，李征等 (由不同大小的概念粒形成).在近似空间上，用2个 人676通过研究模糊控制器的结构，认为模糊控制 精确的集合（上近似集和下近似集）来逼近一个边界 实际上是应用了信息粒化和词计算技术，但却只是 模糊的集合如果近似空间的粒度较粗，被近似的集 应用了该技术的初级形式，而基于信息粒化和词计 合的边界域较宽，而如果近似空间的粒度较细，被近 算(IGCW)的模糊控制系统，将具有更强的信息处 似集合的边界域较窄 理和推理判断能力，是对人类智能更高程度的模拟. 给定集合X上的一个划分等价于在X上给定 他们指出，基于信息粒化和词计算的模糊控制系统 一个等价关系R.X/R表示U上由R导出的所有等 是通过信息粒化和重组、多层次的思维决策，动态地 价类，[x]r表示包含元素x的等价类，其中x∈U. 改变下层控制器的参数和推理方法或控制规则，因 Pawlak称之为在论域上给定了一个知识基(X,R) 而使控制器具有变结构和多模态的特性.信息太多 然后讨论一个一般的概念X(U中的一个子集)如何 会延误推理计算的时间，给系统带来不必要的处理 用知识基中的知识来表示.对那些无法用(X,中 任务；而信息太少，则会降低推理结果的完善性.因 的集合的并来表示的集合，借用拓扑中的内核和闭 此，提出了合理重新组织信息的研究课题.随着近年 包的概念，引入下近似和上近似的概念：R.X)= 来智能信息处理的不断深入与普及，特别是处理复 {xU[x]R∈X?和R(X)=fx∈U川[x]R∩X卡 杂系统分析与评估时的迫切需要，人们越来越发现 .当R.(X)≠R°()时，就称X为粗糙集，从而 排除自然语言的代价太大了，首先，从应用角度来 创立了“粗糙集理论”.粗糙集理论是一种软计算方 看，人类已习惯于用自然语言描述和分析事物，特别 法.软计算(soft computing)概念是由模糊集创始人 是涉及社会、政治、经济和管理中的复杂过程.人类 Zadea提出的，6s.传统的计算方法即所谓硬计 可以方便地利用以自然语言表示的前提进行推理和 算，使用精确、固定和不变的算法来表达和解决问 计算，并得到用自然语言表达的结果；其次，从理论 题：而软计算的指导原则是利用所允许的不精确、不 角度来看，不利用自然语言，现有的理论很难甚至不 确定性和部分真实性得到易于处理、鲁棒性强和成 能够处理感性信息，而只能处理测度信息.感性信息 本较低的解决方案，以便更好地与现实系统相协调」 或知识通常只能用自然语言来描述，由于人类分辨 粗糙集理论的研究，己经经历了20多年的时 细节和存储信息的认知能力的内在限制，感性信息 间，无论是在系统理论、计算模型的建立和应用系统 在本质上是不精确的9.2！.Wang利用自然语言知 的研制开发上，都已经取得了很多成果，也建立了一 识和信息，建立以词计算为基础的语言动力学系统 套较为完善的粗糙集理论体系74.5).目前粗糙集理 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
础[63 ] . 模糊逻辑在词计算中起中心作用 ,它可以近 似地被认为与词计算相同[62 ] . 在词计算中存在 2 个 核心问题 :模糊约束的表现问题和模糊约束的繁殖 问题 ,它们是模糊信息粒化的基本准则. 信息粒化 (information granulation) 是粒化的 一种形式. 在众多的信息粒化中 ,非模糊粒化的方法 很多 ,如将问题求解空间形成划分空间 ,每个粒子都 是精确的. 但这种粒化方法不能解决很多现实问题 , 如将人的头部粒化为脸、鼻子、额头、耳朵、头盖、脖 子等粒子 ,这些粒子之间没有明确的分界线 ,它们都 是模糊的粒子. 模糊信息粒化是传统信息粒化的一 种推广. 模糊信息粒化理论[64 - 65 ] (t heory of f uzzy information granulation ,TFIG) 建立在模糊逻辑和 信息粒化方法基础之上 ,是从人类利用模糊信息粒 化方式中获得的启发 ,其方法的实质是数学. Zadeh 指出[64 ] ,除模糊逻辑外 ,没有一种方法 能提供概念框架及相关技术 ,它能在模糊信息粒化 起主导作用. 继 Zadeh 之后 ,许多学者开始了有关词 计算的研究工作 ,Wang [66 ]编写了词计算一书. 广义 词计算理论的研究工作 ,中国刚刚起步 ,李征等 人[67 - 68 ]通过研究模糊控制器的结构 ,认为模糊控制 实际上是应用了信息粒化和词计算技术 ,但却只是 应用了该技术的初级形式 ,而基于信息粒化和词计 算 (IGCW) 的模糊控制系统 ,将具有更强的信息处 理和推理判断能力 ,是对人类智能更高程度的模拟. 他们指出 ,基于信息粒化和词计算的模糊控制系统 是通过信息粒化和重组、多层次的思维决策 ,动态地 改变下层控制器的参数和推理方法或控制规则 ,因 而使控制器具有变结构和多模态的特性. 信息太多 会延误推理计算的时间 ,给系统带来不必要的处理 任务 ;而信息太少 ,则会降低推理结果的完善性. 因 此 ,提出了合理重新组织信息的研究课题. 随着近年 来智能信息处理的不断深入与普及 ,特别是处理复 杂系统分析与评估时的迫切需要 ,人们越来越发现 排除自然语言的代价太大了. 首先 ,从应用角度来 看 ,人类已习惯于用自然语言描述和分析事物 ,特别 是涉及社会、政治、经济和管理中的复杂过程. 人类 可以方便地利用以自然语言表示的前提进行推理和 计算 ,并得到用自然语言表达的结果 ;其次 ,从理论 角度来看 ,不利用自然语言 ,现有的理论很难甚至不 能够处理感性信息 ,而只能处理测度信息. 感性信息 或知识通常只能用自然语言来描述 ,由于人类分辨 细节和存储信息的认知能力的内在限制 ,感性信息 在本质上是不精确的[69 - 72 ] . Wang 利用自然语言知 识和信息 ,建立以词计算为基础的语言动力学系统 (linguistic dynamic systems ,LDS) ,并通过融合几 个不同领域的概念和方法[37 ] ,提出基于词计算的语 言动力学系统的计算理论框架 ,根据这个计算理论 框架 ,利用常规或传统数值动力学系统中已有的成 熟概念和方法 ,对语言动力学系统进行动力学分析、 设计、控制和性能评估. 这些研究的目的是建立连接 人类的语言知识表示与计算机的数字知识表示的桥 梁 ,成为下一代智能化人机交互的理论基础之一. 总之 ,词计算理论和方法对于复杂信息系统的 模糊推理和控制非常重要 ,但由于自身的局限性 ,它 必须和其他理论体系相结合 ,才能更有效地处理复 杂信息. 312 粗糙集模型 一个对象属于某个集合的程度随着属性粒度的 不同而不同 ,为了更好地刻画集合边界的模糊性 ,波 兰学者 Pawlak [73 ]在 20 世纪 80 年代提出了粗糙集 理论 ,其本质思想是利用不可分辨关系 (等价关系) 来建立论域的一个划分 ,得到不区分的等价类(即不 同属性粒度下的概念粒) ,从而建立一个近似空间 (由不同大小的概念粒形成) . 在近似空间上 ,用 2 个 精确的集合(上近似集和下近似集) 来逼近一个边界 模糊的集合. 如果近似空间的粒度较粗 ,被近似的集 合的边界域较宽 ,而如果近似空间的粒度较细 ,被近 似集合的边界域较窄. 给定集合 X 上的一个划分等价于在 X 上给定 一个等价关系 R . X/ R 表示 U 上由 R 导出的所有等 价类 ,[ x ] R 表示包含元素 x 的等价类 ,其中 x ∈U. Pawlak 称之为在论域上给定了一个知识基 ( X , R) , 然后讨论一个一般的概念 X (U 中的一个子集) 如何 用知识基中的知识来表示. 对那些无法用 ( X , R) 中 的集合的并来表示的集合 ,借用拓扑中的内核和闭 包的概念 ,引入下近似和上近似的概念 : R - ( X) = { x ∈U| [ x ] R Α X}和 R - ( X) = { x ∈U| [ x ] R ∩X ≠ Φ} . 当 R - ( X) ≠R - ( X) 时 ,就称 X 为粗糙集 ,从而 创立了“粗糙集理论”. 粗糙集理论是一种软计算方 法. 软计算(soft comp uting) 概念是由模糊集创始人 Zadea 提出的[61 - 65 ] . 传统的计算方法即所谓硬计 算 ,使用精确、固定和不变的算法来表达和解决问 题;而软计算的指导原则是利用所允许的不精确、不 确定性和部分真实性得到易于处理、鲁棒性强和成 本较低的解决方案 ,以便更好地与现实系统相协调. 粗糙集理论的研究 ,已经经历了 20 多年的时 间 ,无论是在系统理论、计算模型的建立和应用系统 的研制开发上 ,都已经取得了很多成果 ,也建立了一 套较为完善的粗糙集理论体系[ 74 - 75 ] . 目前粗糙集理 · 21 · 智 能 系 统 学 报 第 2 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第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
第6期 王国胤，等：粒计算研究综述 ·15 的相互转化 分，即知识的分解，二是泛化，即知识的综合.对于确 3.43基于容差关系的粒计算模型 定的知识，没有必要进行泛化和细化，但对于不确定 粗糙集能有效地分析和处理不精确、不一致和 性知识，利用外延内涵算子和内涵外延算子可以将 不完整等各种不完备信息，并能从中揭示潜在的规 知识进行泛化和例化.结合包含度理论在不同的泛 律，近年来在机器学习、数据挖掘等多个领域得到了 化和例化知识系统上发现知识，这种方法与粒计算 广泛应用.在对粗糙集理论的研究中，对不完备信息 的思路完全一致.因此，知识系统的泛化和例化是粒 系统的传统处理方法是先进行补齐，然后再用粗糙 计算的一种特殊形式，它与Yao)提出的基于划分 集的方法来进行处理，由于补齐的过程导致了原始 的粒计算模型（即采用逻辑决策语言(DL~语言）来 系统信息的变化，所得到的结果不一定反映原始系 描述集合的粒（用满足公式中元素的集合来定义等 统的真实情况.因而有必要扩充不完备信息系统的 价类m(,构建粒世界的逻辑框架，并应用于构建 理论与方法，直接从不完备信息系统中获取知识.王 粒网络和分析了相关规则、例外规则和特殊规则)非 国胤等人38·以容差关系为基础，提出了不完备信 常相似.曲开社等人51在概念信息粒格上建立了 息系统的粒计算方法.使用属性值上的容差关系给出 3个偏序集：G偏序集、M偏序集和GM偏序集，并 不完备信息系统的粒表示、粒运算规则和粒分解算法， 将包含度的概念引入到这3个偏序集上，证实了概 同时结合粗糙集中的属性约简问题，提出了不完备信 念信息系统中的内涵、外延和蕴涵规则均可归结为 息系统在粒表示下属性必要性的判定条件.郑 偏序集上的序表示及包含度表示.近几年来，人们进 征6.7列等人根据人类具有依据具体的任务特性把相 一步对概念知识粒和概念信息粒的转化进行了研 关数据和知识泛化或者例化成不同程度、不同大小的 究2.1o),加快了概念格粒计算模型的发展 粒的能力，以及进一步依据这些粒和粒之间的关系进 随着粒计算研究工作的飞速发展，粒计算模型 行问题求解的能力提出了相容粒度空间模型 的种类层出不穷，如基于神经网络的粒计算模 3.44基于概念格的粒计算模型 型490！基于进化计算的粒计算模型o6等等.限于 概念格，也称形式概念分析，最早由Wlle于 篇幅，不再一一列举 1982年提出o1,它几乎与粗糙集理论一起被提出， 4 并都为数据分析提供了有效的研究方法.它是根据 粒计算模型之间的关系 二元关系提出的一种概念层次结构.从数据集中生 基于模糊集合论的词计算模型、基于粗糙集理 成概念格的过程，实际上是一种概念聚类的过程，它 论的粒计算模型和基于商空间理论的粒计算模型都 的每个节点被称为一个概念，概念的外延表示为属 是描述人类能按不同粒度处理事物的能力的模型. 于这个概念的所有对象的集合，而内涵则表示为所 商空间理论模型和粗糙集理论模型认为概念粒子可 有对象所共有的属性的集合，概念格在本质上描述 以用子集来表示，不同粒度下的粒子用不同大小的 了对象和属性之间的联系，表明了概念之间的泛化 子集来描述，所有的粒子都通过等价关系获得划分 和例化关系，它的Hasse图则实现了对数据的可视 产生.而词计算模型认为表示知识的粒子用一个 化，作为数据分析和知识处理的形式化工具.概念格 “词”（即模糊子集）来表示，不同程度的知识可以通 理论已被广泛地应用于软件工程、知识工程、数据挖 过不同的程度词进行刻画.从研究对象上看，3种模 掘、信息检索等领域.仇国芳2.]等人在概念 型都是在有限的集合论域上研究，只是各自的侧重 格的基础上，提出概念知识格，以及概念信息粒格， 点不同 讨论了概念信息粒之间的蕴含关系，以及由概念信 粗糙集理论的研究对象是由一个多值属性集合 息粒生成的不确定规则的方法，扩充了概念格的研 描述的一个对象集合对于每个对象及其属性都有 究内容 一个值作为其描述符号.对象、属性和描述符是表述 张文修等人1]认为：知识是人类认知的成果 决策问题的3个基本要素.关于对象可得到的信息 和结晶，包括经验知识和理论知识.经验知识可以理 不一定足以划分其成员类型，这种不精确性导致了 解为从大量现象中归纳的共同特征，数据库知识发 对象的不可分辨性.给定对象间的一个等价关系，即 现即是这种思维方式的程序化；而理论知识是对事 导致由等价类构成的近似空间的不分明关系，粗糙 务因果的探索，是对经验知识的理性概括.但任何知 集就用不分明对象类形成的上近似和下近似来描 识都不是孤立存在的，都存在于相互关联的知识系 述.它能够解决重要的分类问题，所有冗余对象和属 统中，对于知识的深层次认识有2种方法：一是细 性的约简包含属性的最小子集，能够很好地近似分 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
的相互转化. 31413 基于容差关系的粒计算模型 粗糙集能有效地分析和处理不精确、不一致和 不完整等各种不完备信息 ,并能从中揭示潜在的规 律 ,近年来在机器学习、数据挖掘等多个领域得到了 广泛应用. 在对粗糙集理论的研究中 ,对不完备信息 系统的传统处理方法是先进行补齐 ,然后再用粗糙 集的方法来进行处理 ,由于补齐的过程导致了原始 系统信息的变化 ,所得到的结果不一定反映原始系 统的真实情况. 因而有必要扩充不完备信息系统的 理论与方法 ,直接从不完备信息系统中获取知识. 王 国胤等人[38 - 39 ]以容差关系为基础 ,提出了不完备信 息系统的粒计算方法 ,使用属性值上的容差关系给出 不完备信息系统的粒表示、粒运算规则和粒分解算法 , 同时结合粗糙集中的属性约简问题 ,提出了不完备信 息系统在粒表示下属性必要性的判定条件. 郑 征[46 - 47 ,59]等人根据人类具有依据具体的任务特性把相 关数据和知识泛化或者例化成不同程度、不同大小的 粒的能力 ,以及进一步依据这些粒和粒之间的关系进 行问题求解的能力提出了相容粒度空间模型. 31414 基于概念格的粒计算模型 概念格 ,也称形式概念分析 ,最早由 Wille 于 1982 年提出[100 ] ,它几乎与粗糙集理论一起被提出 , 并都为数据分析提供了有效的研究方法. 它是根据 二元关系提出的一种概念层次结构. 从数据集中生 成概念格的过程 ,实际上是一种概念聚类的过程 ,它 的每个节点被称为一个概念 ,概念的外延表示为属 于这个概念的所有对象的集合 ,而内涵则表示为所 有对象所共有的属性的集合. 概念格在本质上描述 了对象和属性之间的联系 ,表明了概念之间的泛化 和例化关系 ,它的 Hasse 图则实现了对数据的可视 化 ,作为数据分析和知识处理的形式化工具. 概念格 理论已被广泛地应用于软件工程、知识工程、数据挖 掘、信息检索等领域[101 ] . 仇国芳[102 - 103 ] 等人在概念 格的基础上 ,提出概念知识格 ,以及概念信息粒格 , 讨论了概念信息粒之间的蕴含关系 ,以及由概念信 息粒生成的不确定规则的方法 ,扩充了概念格的研 究内容. 张文修等人[104 ] 认为 :知识是人类认知的成果 和结晶 ,包括经验知识和理论知识. 经验知识可以理 解为从大量现象中归纳的共同特征 ,数据库知识发 现即是这种思维方式的程序化 ;而理论知识是对事 务因果的探索 ,是对经验知识的理性概括. 但任何知 识都不是孤立存在的 ,都存在于相互关联的知识系 统中. 对于知识的深层次认识有 2 种方法 :一是细 分 ,即知识的分解 ;二是泛化 ,即知识的综合. 对于确 定的知识 ,没有必要进行泛化和细化 ,但对于不确定 性知识 ,利用外延内涵算子和内涵外延算子可以将 知识进行泛化和例化. 结合包含度理论在不同的泛 化和例化知识系统上发现知识 ,这种方法与粒计算 的思路完全一致. 因此 ,知识系统的泛化和例化是粒 计算的一种特殊形式 ,它与 Yao [17 ] 提出的基于划分 的粒计算模型 (即采用逻辑决策语言 (DL2语言) 来 描述集合的粒(用满足公式φ元素的集合来定义等 价类 m (φ) ,构建粒世界的逻辑框架 ,并应用于构建 粒网络和分析了相关规则、例外规则和特殊规则) 非 常相似. 曲开社等人[105 ] 在概念信息粒格上建立了 3 个偏序集 : G偏序集、M 偏序集和 GM 偏序集 ,并 将包含度的概念引入到这 3 个偏序集上 ,证实了概 念信息系统中的内涵、外延和蕴涵规则均可归结为 偏序集上的序表示及包含度表示. 近几年来 ,人们进 一步对概念知识粒和概念信息粒的转化进行了研 究[102 - 103 ] ,加快了概念格粒计算模型的发展. 随着粒计算研究工作的飞速发展 ,粒计算模型 的种类层出不穷 , 如基于神经网络的粒计算模 型[49 - 50 ] 、基于进化计算的粒计算模型[106 ]等等. 限于 篇幅 ,不再一一列举. 4 粒计算模型之间的关系 基于模糊集合论的词计算模型、基于粗糙集理 论的粒计算模型和基于商空间理论的粒计算模型都 是描述人类能按不同粒度处理事物的能力的模型. 商空间理论模型和粗糙集理论模型认为概念粒子可 以用子集来表示 ,不同粒度下的粒子用不同大小的 子集来描述 ,所有的粒子都通过等价关系获得划分 产生. 而词计算模型认为表示知识的粒子用一个 “词”(即模糊子集) 来表示 ,不同程度的知识可以通 过不同的程度词进行刻画. 从研究对象上看 ,3 种模 型都是在有限的集合论域上研究 ,只是各自的侧重 点不同. 粗糙集理论的研究对象是由一个多值属性集合 描述的一个对象集合 ,对于每个对象及其属性都有 一个值作为其描述符号. 对象、属性和描述符是表述 决策问题的 3 个基本要素. 关于对象可得到的信息 不一定足以划分其成员类型 ,这种不精确性导致了 对象的不可分辨性. 给定对象间的一个等价关系 ,即 导致由等价类构成的近似空间的不分明关系 ,粗糙 集就用不分明对象类形成的上近似和下近似来描 述. 它能够解决重要的分类问题 ,所有冗余对象和属 性的约简包含属性的最小子集 ,能够很好地近似分 第 6 期 王国胤 ,等 :粒计算研究综述 · 51 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
16 智能系统学报 第2卷 类，得到可以接受的分类质量.另外，它还可以用决 得到一定的粗略或梗概的性质，根据实际的需求，再 策规则集合的形式表示最重要属性和特定分类之间 进一步分类，直至问题的解决.一般说来，商空间理 的所有重要关系).所以，粗糙集研究的是离散的 论中粒度的选择与划分，与问题所属的领域的具体 对象集，针对属性值的差异对对象进行分类，从而形 知识密切相关，它依赖一个有序的拓扑空间或半序 成集合的上、下近似，获得相应的规则，而对象之间 空间.如当问题空间是半序结构时，通常希望所构造 没有结构关系或拓扑关系」 的商空间也是半序空间，但一般情况下商空间未必 商空间理论的着重点不同，它不是只针对给定 是半序空间，此时通过忽略一些次要的因素（可能这 的商空间（知识基）来讨论知识的表达问题，而是在 个因素在粗糙集方法中是核属性)，适当地选取粒 所有可能的商空间中，找出最合适的商空间，利用从 度，通过商空间的合并法和分解法，使得到的商空间 不同商空间（从不同角度）观察同一问题，以便得到 成为半序空间.这样有利于快速寻找到问题的解（可 对问题不同角度的理解，最终综合成对问题总的理 能不是精确解). 解（解）.它的求解过程是在“由所有商空间组成的半 基于模糊集的词计算理论与商空间理论、粗糙 序格”中转换的过程，故可看成是宏观的粒计算.而 集理论稍有不同，词计算模型主要讨论粒度的表示 粗糙集理论是在给定的商空间中运动，故可看成是 问题，即当人类进行各种思考和推理时，都离不开粒 微观的粒计算1.商空间理论是讨论不同粒度空 度，这些粒度一般就是用语言、词来表示，然后利用 间之间的表示转换和相互依存等问题，与粗糙集理 模糊逻辑进行词计算的推理和计算.这种方法与人 论相同，都是利用等价类来描述“粒子”，用“粒度”来 们的主观因素有密切的关系，对于处理复杂的人文 描述概念，但侧重点有所不同.粗糙集理论研究在给 系统非常有效. 定的空间（知识基）上不同概念的表示、转换和相互 商空间理论、粗糙集理论是“精确”的粒计算方 依存问题，其论域是点集，元素之间没有拓扑关系， 法，而词计算理论是模糊的粒计算方法.将词计算模 故是无拓扑结构情况的商空间特例.商空间理论就 型的基本方法（模糊数学）应用到粗糙集模型中就形 是将问题在不同的粒度世界与数学上集合论的商集 成了模糊粗糙集和粗糙模糊集理论.模糊集和粗糙 概念统一起来表示对象模型的方法，即以商集作为 集理论在处理不确定性和不精确性问题方面推广了 不同粒度世界的数学模型的方法.问题的不同粒度 经典集合论，这2个理论的比较和融合是人们感兴 表示对应于不同的等价关系，也就是不同的粒度，是 趣的话题1].模糊粗糙集理论模型的建立和发展 对论域进行不同的划分.因此，划分就是构成不同粒 成为粗糙集理论推广的主要方向之一.从Dubois等 度世界的方法，这与粗糙集理论相同.但商空间理论 人1提出模糊粗糙集理论，到后来的各种广义模 方法提出的商空间描述法与状态空间、问题规约等 糊粗糙集理论、公理化的模糊粗糙集理论0！，使 方法相比具有更强的表达能力.它不仅可以描述论 该理论的发展达到了一个相对完善的状态.张铃等 域中的元素、元素之间的不同结构（关系），而且可以 人35]将模糊集理论应用到商空间理论得到模糊商 定义多种不同的属性函数或运算，它利用拓扑空间 空间理论，利用模糊商空间理论建立了从大量的事 和偏序（半序）空间，为不同粒度世界提供了形式描 物（数据）中获取具有粒度结构（层次）的知识的方 述的手段.商空间模型主要论述的是，当人们面临一 法，然后对各商空间提取相应的知识.从而实现了从 个很复杂的问题时，通常从比较“粗”的粒度层次来 模糊信息粒结构到分层递阶结构再到具有粒度结构 分析问题，再根据问题的需求粒化问题空间，在不同 的知识的相互转化.毛军军等人21从商空间理论 的商空间上寻求问题的解.常见的思路就是分类讨 和信息粒度原理角度出发，引入模糊商空间形成的 论的问题.例如二次方程求解，首先将问题粒化为3 分层递阶结构，将Fuy聚类分析应用于实例.与粗 个商空间：判别式大于0、判别式等于0和判别式小 糙集理论相比]，商空间理论对分类界线不确定 于0.再利用相应的定理（即附加的信息）在相应的 (或是模糊的情况)也可以求解 商空间上求解，直到问题得到确定解 虽然商空间理论、词计算理论和粗糙集理论等 粗糙集理论根据属性形成划分.属性一旦确定， 粒计算模型从解决问题的初衷和解决问题的目标不 划分就确定下来.任何一个核属性都会对划分产生 尽相同，各有特色，但是三者都有一个共同的特点 影响，即使影响并不大，也不能忽略它.但在用商空 就是在处理实际复杂问题时，不一定去追求问题的 间理论求解实际问题时，粒度的划分可以是动态的， 完美解或精确解，而是根据实际需求，得到近似的较 即先进行一次分类，在这个粒度上进行推理与分析， 优解.如果将三者结合起来，充分发挥它们各自的优 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
类 ,得到可以接受的分类质量. 另外 ,它还可以用决 策规则集合的形式表示最重要属性和特定分类之间 的所有重要关系[75 ] . 所以 ,粗糙集研究的是离散的 对象集 ,针对属性值的差异对对象进行分类 ,从而形 成集合的上、下近似 ,获得相应的规则 ,而对象之间 没有结构关系或拓扑关系. 商空间理论的着重点不同 ,它不是只针对给定 的商空间(知识基) 来讨论知识的表达问题 ,而是在 所有可能的商空间中 ,找出最合适的商空间 ,利用从 不同商空间(从不同角度) 观察同一问题 ,以便得到 对问题不同角度的理解 ,最终综合成对问题总的理 解(解) . 它的求解过程是在“由所有商空间组成的半 序格”中转换的过程 ,故可看成是宏观的粒计算. 而 粗糙集理论是在给定的商空间中运动 ,故可看成是 微观的粒计算[107 ] . 商空间理论是讨论不同粒度空 间之间的表示、转换和相互依存等问题 ,与粗糙集理 论相同 ,都是利用等价类来描述“粒子”,用“粒度”来 描述概念 ,但侧重点有所不同. 粗糙集理论研究在给 定的空间(知识基) 上不同概念的表示、转换和相互 依存问题 ,其论域是点集 ,元素之间没有拓扑关系 , 故是无拓扑结构情况的商空间特例. 商空间理论就 是将问题在不同的粒度世界与数学上集合论的商集 概念统一起来表示对象模型的方法 ,即以商集作为 不同粒度世界的数学模型的方法. 问题的不同粒度 表示对应于不同的等价关系 ,也就是不同的粒度 ,是 对论域进行不同的划分. 因此 ,划分就是构成不同粒 度世界的方法 ,这与粗糙集理论相同. 但商空间理论 方法提出的商空间描述法与状态空间、问题规约等 方法相比具有更强的表达能力. 它不仅可以描述论 域中的元素、元素之间的不同结构(关系) ,而且可以 定义多种不同的属性函数或运算. 它利用拓扑空间 和偏序(半序) 空间 ,为不同粒度世界提供了形式描 述的手段. 商空间模型主要论述的是 ,当人们面临一 个很复杂的问题时 ,通常从比较“粗”的粒度层次来 分析问题 ,再根据问题的需求粒化问题空间 ,在不同 的商空间上寻求问题的解. 常见的思路就是分类讨 论的问题. 例如二次方程求解 ,首先将问题粒化为 3 个商空间 :判别式大于 0、判别式等于 0 和判别式小 于 0. 再利用相应的定理(即附加的信息) ,在相应的 商空间上求解 ,直到问题得到确定解. 粗糙集理论根据属性形成划分. 属性一旦确定 , 划分就确定下来. 任何一个核属性都会对划分产生 影响 ,即使影响并不大 ,也不能忽略它. 但在用商空 间理论求解实际问题时 ,粒度的划分可以是动态的 , 即先进行一次分类 ,在这个粒度上进行推理与分析 , 得到一定的粗略或梗概的性质 ,根据实际的需求 ,再 进一步分类 ,直至问题的解决. 一般说来 ,商空间理 论中粒度的选择与划分 ,与问题所属的领域的具体 知识密切相关 ,它依赖一个有序的拓扑空间或半序 空间. 如当问题空间是半序结构时 ,通常希望所构造 的商空间也是半序空间 ,但一般情况下商空间未必 是半序空间 ,此时通过忽略一些次要的因素(可能这 个因素在粗糙集方法中是核属性) ,适当地选取粒 度 ,通过商空间的合并法和分解法 ,使得到的商空间 成为半序空间. 这样有利于快速寻找到问题的解(可 能不是精确解) . 基于模糊集的词计算理论与商空间理论、粗糙 集理论稍有不同 ,词计算模型主要讨论粒度的表示 问题 ,即当人类进行各种思考和推理时 ,都离不开粒 度 ,这些粒度一般就是用语言、词来表示 ,然后利用 模糊逻辑进行词计算的推理和计算. 这种方法与人 们的主观因素有密切的关系 ,对于处理复杂的人文 系统非常有效. 商空间理论、粗糙集理论是“精确”的粒计算方 法 ,而词计算理论是模糊的粒计算方法. 将词计算模 型的基本方法(模糊数学) 应用到粗糙集模型中就形 成了模糊粗糙集和粗糙模糊集理论. 模糊集和粗糙 集理论在处理不确定性和不精确性问题方面推广了 经典集合论 ,这 2 个理论的比较和融合是人们感兴 趣的话题[108 ] . 模糊粗糙集理论模型的建立和发展 , 成为粗糙集理论推广的主要方向之一. 从 Dubois 等 人[109 ]提出模糊粗糙集理论 ,到后来的各种广义模 糊粗糙集理论、公理化的模糊粗糙集理论[110 - 111 ] ,使 该理论的发展达到了一个相对完善的状态. 张铃等 人[35 ]将模糊集理论应用到商空间理论得到模糊商 空间理论 ,利用模糊商空间理论建立了从大量的事 物(数据) 中获取具有粒度结构 (层次) 的知识的方 法 ,然后对各商空间提取相应的知识. 从而实现了从 模糊信息粒结构到分层递阶结构再到具有粒度结构 的知识的相互转化. 毛军军等人[112 ] 从商空间理论 和信息粒度原理角度出发 ,引入模糊商空间形成的 分层递阶结构 ,将 Fuzzy 聚类分析应用于实例. 与粗 糙集理论相比[ 113 ] ,商空间理论对分类界线不确定 (或是模糊的情况) 也可以求解. 虽然商空间理论、词计算理论和粗糙集理论等 粒计算模型从解决问题的初衷和解决问题的目标不 尽相同 ,各有特色 ,但是三者都有一个共同的特点 , 就是在处理实际复杂问题时 ,不一定去追求问题的 完美解或精确解 ,而是根据实际需求 ,得到近似的较 优解. 如果将三者结合起来 ,充分发挥它们各自的优 · 61 · 智 能 系 统 学 报 第 2 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第6期 王因胤，等：粒计算研究综述 ·17 势，将形成更加有效的粒计算方法和理论.目前，模 解模糊关系方程最大解的快速方法，减少了图像重 糊粗糙集，粗糙模糊集和模糊商空间对于处理复杂 构的运算量.修保新等人181)给出了基于模糊信 问题都表现出比单一模型更好的优势，得到较好的 息粒化思想的图像边缘检测方法，并在基于图像模 发展.但如何将粗糙集与商空间有效地结合起来，还 糊粒化思想进行图像插值的基础上，提出了具体的 没有进一步的研究成果 基于图像模糊粒化结构的插值方法.刘仁金等 基于划分的粒计算模型是粗糙集理论模型的一 人31,14,2o1通过对粒度概念及粗糙集、模糊集等粒 种特例.它将概念知识分为内涵和外延，在外延上利 计算理论的比较研究以及对图像分割概念分析及对 用集合论上的交并等运算来合成粒子或分解粒子， 现有的图像分割方法系统分析，提出了图像分割中 在内涵上采用属性的多少来控制粒子的大小.基于 的商空间粒度原理和基于粒度合成技术原理的纹理 覆盖的粒计算模型是比基于划分粒计算模型更广的 图像分割算法，成功设计出纹理图像的分割算法 一种粒计算模型，是广义粗糙集理论模型的一种特 5.2海量数据挖掘 例.这2个模型都是通过某种二元关系（等价关系或 随着计算机及网络的日益普及，丰富的数据与 非等价关系)产生邻域，再通过Zooming-in和Zoo~ 贫乏的知识问题日见突出.不同领域的人们都期待 ming out2个算子（或其他类似的算子）来实现不同 着从这些数据中得到自己的答案，将信息变为知识， 粒层上粒子之间的相互转化.基于容差关系的粒计 数据挖掘就是从大型数据库或数据仓库中储存的大 算模型和基于相容关系的粒计算模型实质是同一个 量的、不完整的、有噪声的数据中发现潜在的、有价 模型，都是基于自反和对称的二元关系，只是各自的 值的、有趣知识的过程.面对海量数据处理，人们提 侧重点不同.基于概念格的粒计算模型是一种层次 出了各式各样的挖掘方法.粒计算方法凭借自身的 结构模型，它的粒子之间通过包含关系形成偏序关 优势在数据挖掘中显示出较大的优势 系，构成一个完备格.在知识系统中，概念信息粒和 基于模糊集的词计算模型是较早提出的粒计算 概念知识粒之间的相互转化为概念的形成奠定了基 模型，在数据挖掘中有非常成功的应用.模糊集在数 础，也为概念知识的获取提供了方法.而结合神经网 据挖掘中应用最多的是聚类分析.聚类分析是通过 络形成的神经网络粒计算模型在知识获取方面表现 相似性将用户或数据记录进行分组，从而获得相应 出较大的优势9.0] 的规则.与分类不同，聚类是一种无导师的学习，它 将论域中的所有对象划分为簇，同一簇中的对象具 5 粒计算的应用研究 有很高的相似性，不同簇中的对象则很不相似，即差 粒计算方法的应用越来越广泛，己经渗透到自 异很大4].将模糊集引入聚类分析的思想，是首先 然科学和社会科学的很多领域.这里作一个简单的 由Bellman、Kalaba和Zadeh等人于1966年提出 介绍 的，后来有许多研究者对模糊聚类进行了研究，提出 5.1图形图像处理 了基于摄动的模糊聚类方法等新的模糊聚类算法 图像分割是图像分析和处理技术的重要手段， 近年来聚类方法层出不穷，文献[48]从信息粒度的 是模式识别、图像处理、计算机视觉等领域的一个基 角度剖析了聚类和分类技术，试图使用信息粒度原 础环节.一个图像分析系统是否成功，很大程度上依 理的框架来统一聚类和分类.从信息粒度的观点来 赖于分割的质量31,1.随着数学理论特别是应用数 看，聚类是在一个统一的粒度下进行计算，而分类却 学理论的发展，人们借助新的数学理论，对图像分割 是在不同的粒度下进行计算 问题进行研究，并提出了图像分割的许多方法.基于 粗糙集理论是一种研究不完整、不确定知识和 粗糙集的粒计算方法在适当降低精确度为代价的条 数据的表达、学习、归纳的理论方法.由于它是建立 件下可以解决这一问题.Zadeh提出了模糊信息粒 在分类机制基础之上的方法，因而它在数据挖掘分 理论研究的一般框架后，Pedrycz等人s1深入研究 类问题中的应用很多.粗糙集理论在分类问题中的 了信息粒间的结合问题，并结合数字化图像可粒化 应用大致可以分为2类2)：一是利用粗糙集理论的 的特点，讨论了利用图像的内容信息和空间信息进 属性约简、值约简及核属性，直接从数据表中获取分 行粒化的问题.后来，Hirota和Pedrycz6]用模糊 类规则：二是将粗糙集理论与其他方法结合起来进 关系来描述一幅静态灰度图像，提出了基于模糊关 行分类22.124 系计算的图像压缩方法，将模糊信息粒化思想运用 商空间理论是研究不同粒度世界的数学工具， 到图像压缩领域.Nobuhara等人I提出了一种求 在面对数据仓库中海量数据挖掘时，可以针对要处 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
势 ,将形成更加有效的粒计算方法和理论. 目前 ,模 糊粗糙集 ,粗糙模糊集和模糊商空间对于处理复杂 问题都表现出比单一模型更好的优势 ,得到较好的 发展. 但如何将粗糙集与商空间有效地结合起来 ,还 没有进一步的研究成果. 基于划分的粒计算模型是粗糙集理论模型的一 种特例. 它将概念知识分为内涵和外延 ,在外延上利 用集合论上的交并等运算来合成粒子或分解粒子 , 在内涵上采用属性的多少来控制粒子的大小. 基于 覆盖的粒计算模型是比基于划分粒计算模型更广的 一种粒计算模型 ,是广义粗糙集理论模型的一种特 例. 这 2 个模型都是通过某种二元关系(等价关系或 非等价关系) 产生邻域 ,再通过 Zooming2in 和 Zoo2 ming2out 2 个算子(或其他类似的算子) 来实现不同 粒层上粒子之间的相互转化. 基于容差关系的粒计 算模型和基于相容关系的粒计算模型实质是同一个 模型 ,都是基于自反和对称的二元关系 ,只是各自的 侧重点不同. 基于概念格的粒计算模型是一种层次 结构模型 ,它的粒子之间通过包含关系形成偏序关 系 ,构成一个完备格. 在知识系统中 ,概念信息粒和 概念知识粒之间的相互转化为概念的形成奠定了基 础 ,也为概念知识的获取提供了方法. 而结合神经网 络形成的神经网络粒计算模型在知识获取方面表现 出较大的优势[49 - 50 ] . 5 粒计算的应用研究 粒计算方法的应用越来越广泛 ,已经渗透到自 然科学和社会科学的很多领域. 这里作一个简单的 介绍. 511 图形图像处理 图像分割是图像分析和处理技术的重要手段 , 是模式识别、图像处理、计算机视觉等领域的一个基 础环节. 一个图像分析系统是否成功 ,很大程度上依 赖于分割的质量[ 31 ,114 ] . 随着数学理论特别是应用数 学理论的发展 ,人们借助新的数学理论 ,对图像分割 问题进行研究 ,并提出了图像分割的许多方法. 基于 粗糙集的粒计算方法在适当降低精确度为代价的条 件下可以解决这一问题. Zadeh 提出了模糊信息粒 理论研究的一般框架后 ,Pedrycz 等人[115 ] 深入研究 了信息粒间的结合问题 ,并结合数字化图像可粒化 的特点 ,讨论了利用图像的内容信息和空间信息进 行粒化的问题. 后来 , Hirota 和 Pedrycz [116 ] 用模糊 关系来描述一幅静态灰度图像 ,提出了基于模糊关 系计算的图像压缩方法 ,将模糊信息粒化思想运用 到图像压缩领域. Nobuhara 等人[ 117 ] 提出了一种求 解模糊关系方程最大解的快速方法 ,减少了图像重 构的运算量. 修保新等人[118 - 119 ] 给出了基于模糊信 息粒化思想的图像边缘检测方法 ,并在基于图像模 糊粒化思想进行图像插值的基础上 ,提出了具体的 基于图像模糊粒化结构的插值方法. 刘仁金等 人[31 ,114 ,120 ]通过对粒度概念及粗糙集、模糊集等粒 计算理论的比较研究以及对图像分割概念分析及对 现有的图像分割方法系统分析 ,提出了图像分割中 的商空间粒度原理和基于粒度合成技术原理的纹理 图像分割算法 ,成功设计出纹理图像的分割算法. 512 海量数据挖掘 随着计算机及网络的日益普及 ,丰富的数据与 贫乏的知识问题日见突出. 不同领域的人们都期待 着从这些数据中得到自己的答案 ,将信息变为知识. 数据挖掘就是从大型数据库或数据仓库中储存的大 量的、不完整的、有噪声的数据中发现潜在的、有价 值的、有趣知识的过程. 面对海量数据处理 ,人们提 出了各式各样的挖掘方法. 粒计算方法凭借自身的 优势在数据挖掘中显示出较大的优势. 基于模糊集的词计算模型是较早提出的粒计算 模型 ,在数据挖掘中有非常成功的应用. 模糊集在数 据挖掘中应用最多的是聚类分析. 聚类分析是通过 相似性将用户或数据记录进行分组 ,从而获得相应 的规则. 与分类不同 ,聚类是一种无导师的学习 ,它 将论域中的所有对象划分为簇 ,同一簇中的对象具 有很高的相似性 ,不同簇中的对象则很不相似 ,即差 异很大[ 48 ] . 将模糊集引入聚类分析的思想 ,是首先 由 Bellman、Kalaba 和 Zadeh 等人于 1966 年提出 的 ,后来有许多研究者对模糊聚类进行了研究 ,提出 了基于摄动的模糊聚类方法等新的模糊聚类算法. 近年来聚类方法层出不穷 ,文献[ 48 ]从信息粒度的 角度剖析了聚类和分类技术 ,试图使用信息粒度原 理的框架来统一聚类和分类. 从信息粒度的观点来 看 ,聚类是在一个统一的粒度下进行计算 ,而分类却 是在不同的粒度下进行计算. 粗糙集理论是一种研究不完整、不确定知识和 数据的表达、学习、归纳的理论方法. 由于它是建立 在分类机制基础之上的方法 ,因而它在数据挖掘分 类问题中的应用很多. 粗糙集理论在分类问题中的 应用大致可以分为 2 类[121 ] :一是利用粗糙集理论的 属性约简、值约简及核属性 ,直接从数据表中获取分 类规则 ;二是将粗糙集理论与其他方法结合起来进 行分类[ 122 - 124 ] . 商空间理论是研究不同粒度世界的数学工具. 在面对数据仓库中海量数据挖掘时 ,可以针对要处 第 6 期 王国胤 ,等 :粒计算研究综述 · 71 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net