第2卷第6期 智 能 系 统 学 报 V ol.2 .62007年12月 CAAI T ransactions on Intelligent Systems D ec.2007
粒计算研究综述
王国胤1,2,张清华1,2,胡 军1,3
(1.重庆邮电大学计算机科学与技术研究所,重庆400065; 2.西南交通大学信息科学与技术学院,四川成都610031;3.西安电子科技大学电子工程学院,陕西西安710071)
摘 要:粒计算(gr anular computing)是当前计算智能研究领域中模拟人类思维和解决复杂问题的新方法.它覆盖了所有有关粒度的理论、方法和技术,是复杂问题求解、海量数据挖掘、模糊信息处理的有效工具.首先回顾了粒计算研究和发展状况,介绍了粒计算的基本组成和问题,综述了粒计算的基本模型和方法,并讨论了它们之间的相互关系,最后探讨了构建统一的粒计算模型、复杂问题空间的粒化、粒层之间的转换、高效的粒计算方法、新的粒计算模型、动态粒计算模型、自主粒计算模型、粒计算方法的模糊化以及粒计算模型的应用和推广等几个方面的关键问题.关键词:粒计算;数据挖掘;智能信息处理;粗糙集;模糊集;商空间
中图分类号:T P18 文献标识码:A 文章编号:1673 4785(2007)06 0008 19
An overview of granular computing
WAN G Guo yin 1,2,ZHANG Qing hua 1,2,HU Jun 1,3
(1.Institute of Comput er Science &T echno lo gy ,Cho ng qing U niversit y of Po st s and T eleco mmunications,Chong qing 400065,China;2.Scho ol of Infor matio n Science &T echnolog y,Southwest Jiao tong U niv ersit y,Chengdu 610031,China; 3.School of Electro nic Engineer ing,Xidian U niver sity,Xi an 710071,China)
Abstract:In the field of com putational intelligence,granular computing (GrC)is a new w ay to simulate hu m an thinking to help solve co mplicated problems.Gr C involv es all the theories,methodo logies and tech niques o f granularity,pr oviding a pow erful to ol for the so lution of complex problems,m assiv e data min ing,and fuzzy information pr ocessing.In this paper,first the current situation and the developm ent pros pects of GrC are introduced,then the fundamental and ex isting problem s r elated to GrC ar e presented and its basic models and metho ds summ arized.Finally,som e future research topics abo ut GrC are presented,such as,uniform granular co mputing mo del,granulation of complex pro blem space,transform ation be tw een granule spaces,efficient g ranular co mputing algor ithm,nov el g ranular co mputing model,dy namic granular co mputing m odel,data driven g ranular co mputing m odel,fuzzy gr anular co mputing method,and the applications of gr anular computing models,etc.
Keywords:g ranular computing;data m ining;intelligent inform ation processing;roug h sets;fuzzy sets;quotient space
收稿日期:2007 04 02.
基金项目:国家自然科学基金资助项目(60573068);新世纪优秀人才
支持计划;重庆市教委科学技术研究资助项目(KJ060517).
自Zadeh 1979年发表论文!Fuzzy sets and in form ation granularity ?以来[1],研究人员对信息粒度化的思想产生了浓厚的兴趣.Zadeh 认为很多领域都存在信息粒的概念,只是在不同领域中的表现形式不同.自动机与系统论中的!分解与划分?、最优
控制中的!不确定性?、区间分析里的!区间数运算?、以及D S 证据理论中的!证据?都与信息粒密切相关.H obss 在1985年直接用!粒度(granularity)?作为论文题目发表论文[2],讨论了粒的分解和合并,以及如何得到不同大小的粒,并提出了产生不同大小粒的模型.Lin 在1988年提出邻域系统并研究了邻域系统与关系数据库之间的关系
[3]
.1996年,他在
U C Berkeley 大学访问时,向Zadeh 提出作!granu
lar computing?的研究,Zadeh称之为!g ranular mathematics?,Lin改称为!granular co mputing?,并缩写成Gr C.他发表了一系列关于粒计算与邻域系统的论文[4-10],主要是研究二元关系(邻域系统、Rough集和信任函数)下的粒计算模型,论述基于邻域系统的粒计算在粒结构、粒表示和粒应用等方面的问题,讨论了粒计算中的模糊集和粗糙集方法,并将粒计算方法引入数据挖掘和机器发现.依据人们在解决问题时能从不同的粒度世界去分析和观察同一问题,并且很容易地从一个粒度世界转到另一个粒度世界,张钹和张铃在1990年针对复杂问题求解,建立了一种复杂问题求解的商结构形式化体系,给出了一套解决信息融合、启发式搜索、路径规划和推理等问题的理论和算法[11-12].1997年,Zadeh进一步指出[13],世上有3个基本概念构成人类认知的基础:粒化、组织及因果关系.其中,粒化是整体分解为部分,组织是部分结合为整体,而因果关系则涉及原因与结果间的联系.物体的粒化产生一系列的粒子,每个粒子即为一簇点(物体),这些点难以区别,或相似、或接近、或以某种功能结合在一起.一般来说,粒化在本质上是分层次的,时间可粒化为年、月、日、小时、分、秒就是大家熟悉的例子.
在Lin的研究基础上,Yao结合邻域系统对粒计算进行了详细的研究[14-16],发表了一系列研究成果[17-22],并将它应用于知识挖掘等领域,建立了概念之间的if then规则与粒度集合之间的包含关系,提出利用由所有划分构成的格求解一致分类问题,为数据挖掘提供了新的方法和视角.结合粗糙集理论,Yao探讨了粒计算方法在机器学习、数据分析、数据挖掘、规则提取、智能数据处理和粒逻辑等方面的应用.Yao给出了粒计算的3种观点[22]:
1)从哲学角度看,粒计算是一种结构化的思想方法;
2)从应用角度看,粒计算是一个通用的结构化问题求解方法;
3)从计算角度看,粒计算是一个信息处理的典型方法.
随着粒计算研究的发展,近年来国内外又有很多学者加入到了粒计算研究的领域.为了探讨粗糙集理论在各种环境下的应用,Skow r on[23-27]以包含度概念来研究粒近似空间上的Rough下近似和Rough上近似.刘清[28-30]在Roug h逻辑的基础上,提出了粒-逻辑的概念(G 逻辑),构造了这种逻辑的近似推理系统,并应用于医疗诊断.近几年来,在掀起粒计算研究的热潮中,商空间理论被人们广泛认识和推广,2003年张铃和张钹将模糊概念与商空间理论结合,提出模糊商空间理论,为粒计算提供了新的数学模型和工具,并成功应用于数据挖掘等领域[31-35].2002年苗夺谦等人[36]对知识的粒计算进行探讨,引入属性的重要度,并在求最小属性约简方面得到应用.王飞跃等人[37]对词计算和语言动力学进行了探讨,以词计算为基础,对问题进行动态描述、分析和综合,提出了设计、控制和评估的语言动力学系统.王国胤等人[38-44]提出了基于容差关系的粒计算模型,利用属性值上的容差关系给出了不完备信息系统的粒表示、粒运算规则和粒分解算法,同时结合粗糙集中的属性约简问题,提出了不完备信息系统在粒表示下属性必要性的判定条件,对粒计算方法在规则提取方面进行了探索.郑征等人[45-47]提出了相容粒度空间模型,并在图像纹理识别和数据挖掘中取得了成功,他们认为,人类具有根据具体的任务特性把相关数据和知识泛化或者特化成不同程度、不同大小的粒的能力,以及进一步根据这些粒和粒之间的关系进行问题求解的能力.卜东波等人[48]从信息粒度的角度剖析聚类和分类技术,试图使用信息粒度原理的框架来统一聚类和分类,指出从信息粒度的观点来看,聚类是在一个统一的粒度下进行计算,而分类却是在不同的粒度下进行计算,并根据粒度原理设计了一种新的分类算法,大规模中文文本分类的应用实践表明,这种分类算法有较强的泛化能力.Zhang等人[49-50]对粒神经网络进行了探讨,并在高效知识发现中得到很好的应用.李道国等人[51]研究了基于粒向量空间的人工神经网络模型,在一定程度上提高了人工神经网络的时效性、知识表达的可理解性.杜伟林等人[52]根据概念格[53]与粒度划分在概念聚类的过程中都是基于不同层次的概念结构来进行分类表示,而且粒度划分本身构成一个格结构的特点,研究了概念格与粒度划分格在概念描述与概念层次转换之间的联系,通过对概念的分层递阶来进行概念的泛化与例化,使概念在递阶方面忽略不必要的冗余信息.Yager[54]探讨了基于粒计算的学习方法和应用.Lin[55]在2006年粒计算国际会议上提出了新的研究思路!infrastruc tures for AI engineering?.同时,Bargiela和Pe dry cz[56]也从各个侧面对粒计算的根源和实质进行了详细的探讨和总结.Yag er指出,发展信息粒的操作方法是当前粒计算研究的一个重要任务[57].
1 粒计算的基本组成
粒计算的基本组成主要包括3部分:粒子、粒层
#
9
#
第6期 王国胤,等:粒计算研究综述
和粒结构.
1 1 粒 子
粒子是构成粒计算模型的最基本元素[58-59],是粒计算模型的原语.一个粒可以被解释为许多小颗粒构成的一个大个体,现实生活中,粒子无处不在,如在地图上观察洲、国家、海洋、大陆和山脉等是一些粗的粒子(大的粒子),观察省、市、区等是一些中等的粒子,而观察街道、饭店、机场等是一些相对较小的粒子.一个粒子可以被同时看作是由内部属性描述的个体元素的集合,以及由它的外部属性所描述的整体.一个粒子的存在仅仅在一个特定的环境中才有意义.一个粒子的元素可以是粒子,一个粒子也可以是另外一个粒子的元素.而衡量粒子!大小?的概念是粒度,一般来讲,对粒子进行!量化?时用粒度来反映粒化的程度[59].
1 2 粒 层
按照某个实际需求的粒化准则得到的所有粒子的全体构成一个粒层,是对问题空间的一种抽象化描述.根据某种关系或算子,问题空间产生相应的粒子.同一层的粒子内部往往具有相同的某种性质或功能.由于粒化的程度不同,导致同一问题空间会产生不同的粒层.粒层的内部结构是指在该粒层上的各个粒子组成的论域的结构,即粒子之间的相互关系.在问题求解中,选择最合适的粒层对于问题求解尤为关键,因为,在不同粒层求解同一问题的复杂度往往不同.在高一级粒层上的粒子能够分解成为下一级粒层上的多个粒子(增加一些属性),在低一级粒层上的多个粒子可以合并成高一级粒层上的粒子(忽略一些属性).粒计算模型的主要目标是能够在不同粒层上进行问题求解,且不同粒层上的解能够相互转化.
1 3 粒结构
一个粒化准则对应一个粒层,不同的粒化准则对应多个粒层,它反应了人们从不同角度、不同侧面来观察问题、理解问题、求解问题.所有粒层之间的相互联系构成一个关系结构,称为粒结构[20].粒结构给出了一个系统或者问题的结构化描述.通过从系统思维、复杂系统理论和层次结构理论(技术)中得到的启发至少需要确定一个粒结构网[20]中3个层次的结构:粒子的内部结构、粒子集结构和粒子网的层次结构.粒子集的集体结构可以看作是全部层次结构中一个层次或者一个粒度视图中的结构.它本身可以看作是粒的内部连接网络.对于同一个系统或者同一个问题,许多解释和描述可能是同时存在的.所以,粒结构需要被模型化为多种层次结构,以及在一个层次结构中的不同层次.虽然一个粒子在某个粒层上被视为一个整体,但粒子内部元素(子粒子)的结构在问题求解时也很重要,因为它能提供粒子更为详细的特性.而在同一层上的粒子之间也具有某种特殊的结构,它们可能是相互独立,或者部分包含.如果同一粒层上的粒子之间的独立性越好,可能问题求解后合并起来越方便;反之,如果粒子之间的相关性越好,则问题求解后的合并工作相对越繁杂.粒子网的层次结构是对整个问题空间的概括,它的复杂性在一定程度上决定了问题求解的复杂程度.
2 粒计算的基本问题
粒计算中存在2个最基本的问题,即粒化和粒的计算.问题空间的粒化是指将问题空间分解为许多子空间,或是基于有用的信息和知识将问题空间中的个体聚集成不同的类,这些类称之为粒.粒中的元素可以理解为对应概念的实例.可以把粒计算和概念生成、知识发现和数据挖掘联系起来,因为概念生成的目的之一是对具有某些概念的粒的表示、特征化、描述和解释,而知识发现和数据挖掘就是在粒之间建立关联和因果等联系.
2 1 粒 化
粒化是问题求解空间的一个构造性过程,它可以简单理解为在给定粒化准则下得到一个粒层的过程,是粒计算基础单元的构建,包括粒子、粒视图、粒网和层次结构.在不同的粒化准则下就得到多个粒层,进而得到粒层的网络结构.通常的粒化方法有自顶而下通过分解粗粒子得到细粒子的方法,和自底向上将细粒子通过合并得到粗粒子的方法.粒化过程是粒计算的必要过程.问题空间的粒化过程主要涉及粒化准则、粒化算法(方法)、粒子和粒结构的表示(描述)以及粒子和粒结构的定性(定量)描述等问题[59].粒化准则主要是语义方面的问题,解决为什么2个对象能放进同一个粒子内的问题.它是根据实际问题求解的具体需求和具体精度要求得到的.粒化准则的一个基本要求是忽略掉那些无关紧要的细节,从而达到降低问题求解复杂度的目的.粒化方法面对实际问题,回答如何对问题空间进行粒化,采用什么算法或工具实现粒层的构造,它属于算法方面的问题.如在粗糙集理论中,如何对对象集进行划分产生粒层,如何高效实现属性的约简等问题.粒子的结构描述主要是用粒化方法得到的粒子,如何用形式化的语言表述出来,以便后面进行计算.例如在粗糙集理论模型中,粒子的表示可能是一个子集.而
#
10
#智 能 系 统 学 报 第2卷
在概念格理论中,粒子的表述就是一个概念,它包括概念的外延(一个对象子集)和内涵(一个属性子集) 2部分.粒结构的描述往往形式多样,在商空间理论模型中,粒结构是一种分层递阶的结构,在概念格模型中,粒结构是一种H asse图.粒子和粒结构的定性、定量描述主要指粒子和粒结构的大小(主要是指粒度的结果)和复杂性度量.当前,成功的粒化方法往往都是以将解空间形成划分空间为主要的目标,这样便于将子空间上的解合成原问题空间的解,商空间理论就是这样一个成功的实例.当然,如果用某种粒化方法形成的解空间不是划分(如覆盖),这将增加合成的复杂度.
2 2 粒的计算
以粒子为运算对象进行问题的求解或推理,是狭义的粒计算.粒计算可以通过系统访问粒结构来解决问题,包括在层次结构中向上和向下2个方向的交互,以及在同一层次内的移动,主要分为2种[59]:同一粒层上粒子之间相互转换和推理,不同粒层上粒子之间的转换或推理.不同粒层之间的联系可以由映射来表示,在不同粒层上同一问题以不同的粒度、不同的细节表示,粒层之间的映射就建立了同一问题的不同细节描述之间的关系.商空间理论模型就是通过自然投影建立了分层递阶的商空间链式结构.粒计算的主要特点是同一问题的解可以在不同粒层之间自由转化.正是基于这一点,人们才能用粒计算方法高效地实现复杂问题的求解.模糊商空间上的分层递阶结构可以通过模糊等价关系的截关系建立相应的转化联系;粗糙集理论中的划分粒度可以通过属性的增加或删减来控制;而概念格理论模型中的概念粒子的相互转化可以通过改变概念的内涵来实现.这些转化虽然方式不同,但一个共同的特点是在转化的过程中,问题求解的重要性质必须能在不同粒层上表现出来,这也是评价粒化方法好坏的一个重要指标.如果在粒化后粒层之间的相互转化过程中,某些重要属性不能体现出来,这不但不利于问题的求解,反而会导致问题求解过程发散,从而增加问题求解的复杂度.商空间理论模型中的!保真?和!保假?原理使得粒化后形成的商空间具有!保序?性,使得问题求解的搜索空间大大减少,复杂度由相乘变为相加.
粒计算的2个基本问题中,粒化是关键,它直接决定粒计算的成功与否.因此,粒化方法是人们研究的热点问题.目前,粒化方法很多,如基于等价关系的划分产生粒子[17],基于模糊集产生模糊信息粒[1],基于模糊等价关系截集产生分层递阶粒空间[35],基于概念格产生概念信息粒和概念知识粒[60],基于邻域系统产生邻域粒子[3]等等.
总之,粒计算是一个多准则学科,它从许多领域中获得其基本的思想、准则和方法,是基于不同层次粒度和细节的问题求解的一般性理论.在粒计算的!大伞?下进行统一的研究,可以发现不同学科之间原理的关联,它与具体的学科研究是相互独立的[59].一旦掌握了粒计算中的结构化思维和结构化问题求解的抽象思想,就可以很容易地在任何领域中运用.
3 粒计算的主要模型与理论方法
3 1 词计算模型
高标准的精确表达,普遍存在于数学、化学、工程学和另外一些!硬?科学之中,而不精确表达却普遍存在于社会、心理、政治、历史、哲学、语言、人类学、文学、文艺及相关的领域中[61].针对复杂且非明晰定义的现象,无法用精确的数学方法来描述,但可以用一些程度词语,如不很可能、十分不可能、极不可能等,来对某些模糊概念进行修饰.尽管普通的精确方法(如数学)在某些科学领域应用相当广泛,也一直尝试着应用到人文学科中,但人们在长期的实践中已经清楚地认识到精确的方法应用到人文学科有很大的局限性.面对巨大而又复杂的人文学科系统,区别于传统方法的新方法???模糊计算方法被Zadeh提出.在人类的认识中,粒的模糊性直接源于无区别、相似性、接近性以及功能性等这些概念的模糊性.人类具有在不精确性、部分知识、部分确定以及部分真实的环境下作出合理决策这一不同寻常的能力,而模糊信息粒化正是这种能力的基础.在模糊逻辑中,模糊信息粒化是语言变量、模糊!if then?规则以及模糊图的基础.
词计算(com puting w ith w o rds)是用词语代替数进行计算及推理的方法[62].如何利用语言进行推理判断,这就要进行词计算.信息粒化为词计算提供了前提条件,词计算在信息粒度、语言变量和约束概念上产生了自己的理论与方法,意在解决模糊集合论的数值化隶属度函数表示法的局限性、表达的概念缺乏前后联系、逻辑表达和算子实现的复杂性等问题,使它们能够更符合人类的思维特点.词计算有狭义和广义2个方面的概念.狭义的模糊词计算理论是指利用通常意义下的数学概念和运算(如加、减、乘、除等)构造的带有语义的模糊数值型的词计算的理论体系;广义的词计算理论统指用词进行推理、用词构建原型系统和用词编程,前者是后者的基
#
11
#
第6期 王国胤,等:粒计算研究综述
础[63].模糊逻辑在词计算中起中心作用,它可以近似地被认为与词计算相同[62].在词计算中存在2个核心问题:模糊约束的表现问题和模糊约束的繁殖问题,它们是模糊信息粒化的基本准则.
信息粒化(infor mation granulation)是粒化的一种形式.在众多的信息粒化中,非模糊粒化的方法很多,如将问题求解空间形成划分空间,每个粒子都是精确的.但这种粒化方法不能解决很多现实问题,如将人的头部粒化为脸、鼻子、额头、耳朵、头盖、脖子等粒子,这些粒子之间没有明确的分界线,它们都是模糊的粒子.模糊信息粒化是传统信息粒化的一种推广.模糊信息粒化理论[64-65](theor y of fuzzy information g ranulation,TFIG)建立在模糊逻辑和信息粒化方法基础之上,是从人类利用模糊信息粒化方式中获得的启发,其方法的实质是数学.
Zadeh指出[64],除模糊逻辑外,没有一种方法能提供概念框架及相关技术,它能在模糊信息粒化起主导作用.继Zadeh之后,许多学者开始了有关词计算的研究工作,Wang[66]编写了词计算一书.广义词计算理论的研究工作,中国刚刚起步,李征等人[67-68]通过研究模糊控制器的结构,认为模糊控制实际上是应用了信息粒化和词计算技术,但却只是应用了该技术的初级形式,而基于信息粒化和词计算(IGCW)的模糊控制系统,将具有更强的信息处理和推理判断能力,是对人类智能更高程度的模拟.他们指出,基于信息粒化和词计算的模糊控制系统是通过信息粒化和重组、多层次的思维决策,动态地改变下层控制器的参数和推理方法或控制规则,因而使控制器具有变结构和多模态的特性.信息太多会延误推理计算的时间,给系统带来不必要的处理任务;而信息太少,则会降低推理结果的完善性.因此,提出了合理重新组织信息的研究课题.随着近年来智能信息处理的不断深入与普及,特别是处理复杂系统分析与评估时的迫切需要,人们越来越发现排除自然语言的代价太大了.首先,从应用角度来看,人类已习惯于用自然语言描述和分析事物,特别是涉及社会、政治、经济和管理中的复杂过程.人类可以方便地利用以自然语言表示的前提进行推理和计算,并得到用自然语言表达的结果;其次,从理论角度来看,不利用自然语言,现有的理论很难甚至不能够处理感性信息,而只能处理测度信息.感性信息或知识通常只能用自然语言来描述,由于人类分辨细节和存储信息的认知能力的内在限制,感性信息在本质上是不精确的[69-72].W ang利用自然语言知识和信息,建立以词计算为基础的语言动力学系统(linguistic dynamic system s,LDS),并通过融合几个不同领域的概念和方法[37],提出基于词计算的语言动力学系统的计算理论框架,根据这个计算理论框架,利用常规或传统数值动力学系统中已有的成熟概念和方法,对语言动力学系统进行动力学分析、设计、控制和性能评估.这些研究的目的是建立连接人类的语言知识表示与计算机的数字知识表示的桥梁,成为下一代智能化人机交互的理论基础之一.
总之,词计算理论和方法对于复杂信息系统的模糊推理和控制非常重要,但由于自身的局限性,它必须和其他理论体系相结合,才能更有效地处理复杂信息.
3 2 粗糙集模型
一个对象属于某个集合的程度随着属性粒度的不同而不同,为了更好地刻画集合边界的模糊性,波兰学者Paw lak[73]在20世纪80年代提出了粗糙集理论,其本质思想是利用不可分辨关系(等价关系)来建立论域的一个划分,得到不区分的等价类(即不同属性粒度下的概念粒),从而建立一个近似空间(由不同大小的概念粒形成).在近似空间上,用2个精确的集合(上近似集和下近似集)来逼近一个边界模糊的集合.如果近似空间的粒度较粗,被近似的集合的边界域较宽,而如果近似空间的粒度较细,被近似集合的边界域较窄.
给定集合X上的一个划分等价于在X上给定一个等价关系R.X/R表示U上由R导出的所有等价类,[x]R表示包含元素x的等价类,其中x%U. Paw lak称之为在论域上给定了一个知识基(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 computing)概念是由模糊集创始人Zadea提出的[61-65].传统的计算方法即所谓硬计算,使用精确、固定和不变的算法来表达和解决问题;而软计算的指导原则是利用所允许的不精确、不确定性和部分真实性得到易于处理、鲁棒性强和成本较低的解决方案,以便更好地与现实系统相协调.
粗糙集理论的研究,已经经历了20多年的时间,无论是在系统理论、计算模型的建立和应用系统的研制开发上,都已经取得了很多成果,也建立了一套较为完善的粗糙集理论体系[74-75].目前粗糙集理
#
12
#智 能 系 统 学 报 第2卷
论已是处理模糊、不精确和不完备问题的重要数学工具.它在机器学习、知识获取、决策分析、数据库的知识发现、专家系统、决策支持系统、归纳推理、矛盾归结、模式识别、模糊控制和医疗诊断等应用领域取得了不少成果,业已成为粒计算研究的主要工具之一.
经典的粗糙集理论主要是针对完备信息系统的,即处理对象的所有属性值都是已知的.为了使粗糙集理论适用于对不完备信息系统的处理,目前有2种主要途径:一是补齐不完备的数据,二是扩充经典的Rough集模型.至少可以从3个方面扩展粗糙集理论[63]:1)等价关系的泛化;2)基本知识粒度的构造和知识的表示方法的拓广;3)粗糙集的代数方法.
等价关系的泛化问题实质是将满足等价关系的3个条件(自反、对称、传递)根据实际问题进行组合,得到不同的二元关系,再根据这些二元关系得到不同的模型.如Kry szkiew icz[76]提出的基于容差关系的扩充粗糙集模型,Stefanow ski等人[77]提出的基于非对称相似关系的扩充粗糙集模型和基于量化容差关系的扩充粗糙集模型.王国胤[78]分析了前面2种扩充模型的不足,提出了基于限制容差关系的粗糙集模型,并发现:容差关系和非对称相似关系是对不可分辨关系扩充的2个极端,即容差关系的条件太松,非对称相似关系的条件太紧,而限制容差关系介于二者之间.张清华等人[79]根据不完备信息的特点,利用模糊聚类的思想,将非等价关系转化为等价关系,从而用经典的粗糙集模型来处理不完备的信息系统,这种方法的优势在于可以得到变精度的正域以及上下近似.总之,粗糙集理论在不完备信息系统中的应用,是将粗糙集理论进一步推向实用的关键之一,因为现实数据可能在一定程度上是不完备的.
基本知识粒度的构造和知识表示方法的拓广实质是将粗糙集的商集扩展成一个拓扑空间,以此保证运算的封闭性,即用 (U/R)代替U/R,它是布尔代数(2U,~,n,U)的一个子代数,(U, (U/R))构成一个拓扑空间.
张文修等人[80]详细讨论了一般关系下的粗糙集模型,粗糙集代数的公理化方法以及粗糙集系统的代数结构等问题,对变精度的粗糙集模型、概率粗糙集模型、模糊粗糙集模型和随机集粗糙集模型等进行了系统的阐述,进一步推广了经典的粗糙集理论.
近期,基于Rough集理论来研究粒计算的工作尤为突出[81].Paw lak[82]在不分明关系和Ro ug h隶属函数的基础上,利用同一等价类中的元素具有相同的隶属函数的思想,探讨了知识粒的结构和粒度问题.Polkow ski和Sko wr on等人[83]使用Roug h M er eo logy方法和神经网络技术,基于知识粒化思想,提出了一个Rough神经计算(RNC)模型,将粗糙集的知识基(划分块)和神经网络相结合,形成一种高效的神经计算方法.Skow ron[84]在文献[83]的基础上,进一步完善了基于粗糙集的神经计算方法,并在一个参数化的近似空间上,讨论了信息粒的语法、语义、分解和合成问题,给出了粒语言的概念,提出了在分布式系统中关于信息粒结构的模式.但是,他没有提出一套行之有效的粒计算系统,也未涉及分布式环境下基于粒计算的多Ag ent推理中的冲突问题,对信息粒结构模式中的参数也没有提出有效的优化技术.Peters等人[85]使用不分明关系将实数划分成多个子区间,将一个全域划分成若干个网格单元,每个网格单元被视为一个粒,提出了2个信息粒之间的邻近关系和包含关系的度量,但其提出的方法只能局限于单个传感器的样本数据.Peters 等人[86]综述了关于RNC模型的主要研究线索. Lin[3-4]基于二元关系提出了邻域Rough系统,建立了粒计算模型,并使用Rough集中的近似空间作为信息粒结构,定义了粒隶属函数,从而提出了粒Fuzzy集,并得出了一些重要的性质[87].Yao等[88]利用粗糙集粒计算模型来学习分类规则,用粒网格来表示学习所得的分类知识,提出了粒之间关联性的度量公式,通过搜索粒来归纳分类规则,给出了构造粒网格的算法.在研究Rough推理的基础上,刘清等人[28-30]对粒逻辑进行了探讨.
3 3 商空间理论模型
张钹和张铃在研究问题求解时,提出了商空间理论[11-12],他们指出!人类智能的公认特点,就是人们能从极不相同的粒度上观察和分析同一问题.人们不仅能在不同粒度的世界上进行问题求解,而且能够很快地从一个粒度世界跳到另一个粒度的世界,往返自如,毫无困难.这种处理不同世界的能力,正是人类问题求解的强有力的表现?.如果能够将人类的这种能力形式化,并使计算机也具备类似的能力,对于开发机器智能来讲,意义十分重大.商空间粒计算理论的主要内容包括复杂问题的商空间描述、分层递阶结构、商空间的分解与合成、商空间的粒计算、粒度空间关系的推理以及问题的启发式搜索等[11].商空间理论建立了一种商结构的形式化体系,给出一套解决信息融合、启发式搜索、路径规划和推理等领域问题的理论和算法,并已有一些相关
#
13
#
第6期 王国胤,等:粒计算研究综述
研究和应用[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的规模最大可达到s1s2.于是将原来要求解规模为s1s2空间中的问题,化成求解规模分别为s1、s2的2个空间中的问题.即将复杂性从!相乘?降为!相加?.张铃又将统计学上的一些方法移植到商空间粒度分析上来,得到了!弱保假原理?,即:若在某商空间上问题无解,则在X上问题无解的概率大于1- a.并指出,若在X上有解的可信度等于d,则在[X]上对应的问题有解的可信度大于或等于d.为了将精确粒度下的商空间的理论和方法推广到模糊粒度计算中,张钹和张铃[35]又将模糊集合论引入商空间,证明了利用模糊等价关系可以将原来的商空间理论推广成模糊商空间理论.他们还指出,所有模糊等价关系构成一个完备半序格.这些结论为粒计算提供了有力的数学模型和工具.模糊商空间理论能够更好地反映人类处理不确定问题的若干特点,即信息的确定与不确定、概念的清晰与模糊都是相对的,都与问题的粒度粗细有关.因此,构造合理的分层递阶的粒结构,可以高效地求解问题和处理信息.他们提出扩展模糊商空间理论的途径,即可从3个方向推广商空间理论成为模糊商空间理论:
1)研究的论域是模糊空间X;
2)研究的结构T是模糊拓扑;
3)研究的等价关系是模糊等价关系.
并得出结论:任何一个模糊的概念必存在一个相应的粒度空间,在其上该概念是清晰的;任何一个清晰的概念必存在一个相应的粒度空间,在其上该概念是模糊的.这深刻地揭示了模糊和清晰的关系.
近几年来,基于商空间的粒度计算模型的应用也得到推广[31,34,89-95],这些利用商空间理论来解决实际问题的例子说明,当人们在面对实际复杂、难于准确求解的问题,或者求精确解的代价很大,以及实际不需要精确解的问题时,通常不是采用系统的、数学的、精确的方法去追求问题的精确解或最优解,而是通过粒化的思想,将实际问题的解空间转化为商空间,再在商空间上继续求解问题,最终利用商空间理论的!保真?、!保假?2个原理,得到符合实际问题的较优解.人类就是采用这种自顶向下,形成一个分层递阶的解空间结构,使得解空间的复杂度由相乘变相加,避免了计算复杂度高的困难,使得看似难于求解的问题迎刃而解.但是,商空间理论同样缺乏实现粒度与粒度之间、粒度与粒度世界之间、粒度世界与粒度世界之间转换的高效方法.
3 4 其他相关粒计算模型
词计算模型、粗糙集模型和商空间模型是3个主要的粒计算模型.在这3个模型的基础上,人们提出了很多新的模型,如基于划分的粒计算模型,基于覆盖的粒计算模型,基于概念格的粒计算模型和基于相容关系的粒计算模型等.
3 4 1 基于划分的粒计算模型
Yao[17]在讨论了粒计算的基本原理和基本问题的基础上,从语义和算法2个方面研究了粒计算方法中粒子的构建、描述和表达,以及利用粒子进行计算和推理的规则等问题,提出了基于集合论的划分粒计算模型.该模型对一个有限集进行划分得到相应的粒子,这些粒子互不相交,通过子集的包含关系,不同粒度上的粒子之间形成了格的层次结构.他构建了2个算子:Zoom ing in和Zoom ing out.利用这2个算子,不同粒层之间的粒子可以相互转化.
3 4 2 基于覆盖的粒计算模型
Lin以邻域系统为工具,研究了二元关系下的粒计算模型[3-10],对粒计算的结构、表示和应用进行了系统的诠释.他研究的粒计算模型是一个典型的覆盖模型.Zhu[96-97]等人从覆盖约简这个概念出发,讨论了2个覆盖生成相同覆盖广义粗集的判别条件,解决了覆盖的冗余问题,并设计了计算覆盖约简的算法,建立了覆盖下近似运算的公理化体系和上近似运算公理化体系.胡军等人[98]研究了覆盖粒计算模型的不确定度量.马建敏等人[99]提出了基于集合论覆盖原理的粒计算模型,该模型是基于一个有限集合上的一个自反二元关系,并利用Zo oming in和Zo oming out2个算子来实现不同粒层上粒子
#
14
#智 能 系 统 学 报 第2卷
的相互转化.
3 4 3 基于容差关系的粒计算模型
粗糙集能有效地分析和处理不精确、不一致和不完整等各种不完备信息,并能从中揭示潜在的规律,近年来在机器学习、数据挖掘等多个领域得到了广泛应用.在对粗糙集理论的研究中,对不完备信息系统的传统处理方法是先进行补齐,然后再用粗糙集的方法来进行处理,由于补齐的过程导致了原始系统信息的变化,所得到的结果不一定反映原始系统的真实情况.因而有必要扩充不完备信息系统的理论与方法,直接从不完备信息系统中获取知识.王国胤等人[38-39]以容差关系为基础,提出了不完备信息系统的粒计算方法,使用属性值上的容差关系给出不完备信息系统的粒表示、粒运算规则和粒分解算法,同时结合粗糙集中的属性约简问题,提出了不完备信息系统在粒表示下属性必要性的判定条件.郑征[46-47,59]等人根据人类具有依据具体的任务特性把相关数据和知识泛化或者例化成不同程度、不同大小的粒的能力,以及进一步依据这些粒和粒之间的关系进行问题求解的能力提出了相容粒度空间模型.
3 4 4 基于概念格的粒计算模型
概念格,也称形式概念分析,最早由Wille于1982年提出[100],它几乎与粗糙集理论一起被提出,并都为数据分析提供了有效的研究方法.它是根据二元关系提出的一种概念层次结构.从数据集中生成概念格的过程,实际上是一种概念聚类的过程,它的每个节点被称为一个概念,概念的外延表示为属于这个概念的所有对象的集合,而内涵则表示为所有对象所共有的属性的集合.概念格在本质上描述了对象和属性之间的联系,表明了概念之间的泛化和例化关系,它的H asse图则实现了对数据的可视化,作为数据分析和知识处理的形式化工具.概念格理论已被广泛地应用于软件工程、知识工程、数据挖掘、信息检索等领域[101].仇国芳[102-103]等人在概念格的基础上,提出概念知识格,以及概念信息粒格,讨论了概念信息粒之间的蕴含关系,以及由概念信息粒生成的不确定规则的方法,扩充了概念格的研究内容.
张文修等人[104]认为:知识是人类认知的成果和结晶,包括经验知识和理论知识.经验知识可以理解为从大量现象中归纳的共同特征,数据库知识发现即是这种思维方式的程序化;而理论知识是对事务因果的探索,是对经验知识的理性概括.但任何知识都不是孤立存在的,都存在于相互关联的知识系统中.对于知识的深层次认识有2种方法:一是细分,即知识的分解;二是泛化,即知识的综合.对于确定的知识,没有必要进行泛化和细化,但对于不确定性知识,利用外延内涵算子和内涵外延算子可以将知识进行泛化和例化.结合包含度理论在不同的泛化和例化知识系统上发现知识,这种方法与粒计算的思路完全一致.因此,知识系统的泛化和例化是粒计算的一种特殊形式,它与Yao[17]提出的基于划分的粒计算模型(即采用逻辑决策语言(DL 语言)来描述集合的粒(用满足公式元素的集合来定义等价类m(),构建粒世界的逻辑框架,并应用于构建粒网络和分析了相关规则、例外规则和特殊规则)非常相似.曲开社等人[105]在概念信息粒格上建立了3个偏序集:G偏序集、M偏序集和GM偏序集,并将包含度的概念引入到这3个偏序集上,证实了概念信息系统中的内涵、外延和蕴涵规则均可归结为偏序集上的序表示及包含度表示.近几年来,人们进一步对概念知识粒和概念信息粒的转化进行了研究[102-103],加快了概念格粒计算模型的发展.
随着粒计算研究工作的飞速发展,粒计算模型的种类层出不穷,如基于神经网络的粒计算模型[49-50]、基于进化计算的粒计算模型[106]等等.限于篇幅,不再一一列举.
4 粒计算模型之间的关系
基于模糊集合论的词计算模型、基于粗糙集理论的粒计算模型和基于商空间理论的粒计算模型都是描述人类能按不同粒度处理事物的能力的模型.商空间理论模型和粗糙集理论模型认为概念粒子可以用子集来表示,不同粒度下的粒子用不同大小的子集来描述,所有的粒子都通过等价关系获得划分产生.而词计算模型认为表示知识的粒子用一个!词?(即模糊子集)来表示,不同程度的知识可以通过不同的程度词进行刻画.从研究对象上看,3种模型都是在有限的集合论域上研究,只是各自的侧重点不同.
粗糙集理论的研究对象是由一个多值属性集合描述的一个对象集合,对于每个对象及其属性都有一个值作为其描述符号.对象、属性和描述符是表述决策问题的3个基本要素.关于对象可得到的信息不一定足以划分其成员类型,这种不精确性导致了对象的不可分辨性.给定对象间的一个等价关系,即导致由等价类构成的近似空间的不分明关系,粗糙集就用不分明对象类形成的上近似和下近似来描述.它能够解决重要的分类问题,所有冗余对象和属性的约简包含属性的最小子集,能够很好地近似分
#
15
#
第6期 王国胤,等:粒计算研究综述
类,得到可以接受的分类质量.另外,它还可以用决策规则集合的形式表示最重要属性和特定分类之间的所有重要关系[75].所以,粗糙集研究的是离散的对象集,针对属性值的差异对对象进行分类,从而形成集合的上、下近似,获得相应的规则,而对象之间没有结构关系或拓扑关系.
商空间理论的着重点不同,它不是只针对给定的商空间(知识基)来讨论知识的表达问题,而是在所有可能的商空间中,找出最合适的商空间,利用从不同商空间(从不同角度)观察同一问题,以便得到对问题不同角度的理解,最终综合成对问题总的理解(解).它的求解过程是在!由所有商空间组成的半序格?中转换的过程,故可看成是宏观的粒计算.而粗糙集理论是在给定的商空间中运动,故可看成是微观的粒计算[107].商空间理论是讨论不同粒度空间之间的表示、转换和相互依存等问题,与粗糙集理论相同,都是利用等价类来描述!粒子?,用!粒度?来描述概念,但侧重点有所不同.粗糙集理论研究在给定的空间(知识基)上不同概念的表示、转换和相互依存问题,其论域是点集,元素之间没有拓扑关系,故是无拓扑结构情况的商空间特例.商空间理论就是将问题在不同的粒度世界与数学上集合论的商集概念统一起来表示对象模型的方法,即以商集作为不同粒度世界的数学模型的方法.问题的不同粒度表示对应于不同的等价关系,也就是不同的粒度,是对论域进行不同的划分.因此,划分就是构成不同粒度世界的方法,这与粗糙集理论相同.但商空间理论方法提出的商空间描述法与状态空间、问题规约等方法相比具有更强的表达能力.它不仅可以描述论域中的元素、元素之间的不同结构(关系),而且可以定义多种不同的属性函数或运算.它利用拓扑空间和偏序(半序)空间,为不同粒度世界提供了形式描述的手段.商空间模型主要论述的是,当人们面临一个很复杂的问题时,通常从比较!粗?的粒度层次来分析问题,再根据问题的需求粒化问题空间,在不同的商空间上寻求问题的解.常见的思路就是分类讨论的问题.例如二次方程求解,首先将问题粒化为3个商空间:判别式大于0、判别式等于0和判别式小于0.再利用相应的定理(即附加的信息),在相应的商空间上求解,直到问题得到确定解.
粗糙集理论根据属性形成划分.属性一旦确定,划分就确定下来.任何一个核属性都会对划分产生影响,即使影响并不大,也不能忽略它.但在用商空间理论求解实际问题时,粒度的划分可以是动态的,即先进行一次分类,在这个粒度上进行推理与分析,得到一定的粗略或梗概的性质,根据实际的需求,再进一步分类,直至问题的解决.一般说来,商空间理论中粒度的选择与划分,与问题所属的领域的具体知识密切相关,它依赖一个有序的拓扑空间或半序空间.如当问题空间是半序结构时,通常希望所构造的商空间也是半序空间,但一般情况下商空间未必是半序空间,此时通过忽略一些次要的因素(可能这个因素在粗糙集方法中是核属性),适当地选取粒度,通过商空间的合并法和分解法,使得到的商空间成为半序空间.这样有利于快速寻找到问题的解(可能不是精确解).
基于模糊集的词计算理论与商空间理论、粗糙集理论稍有不同,词计算模型主要讨论粒度的表示问题,即当人类进行各种思考和推理时,都离不开粒度,这些粒度一般就是用语言、词来表示,然后利用模糊逻辑进行词计算的推理和计算.这种方法与人们的主观因素有密切的关系,对于处理复杂的人文系统非常有效.
商空间理论、粗糙集理论是!精确?的粒计算方法,而词计算理论是模糊的粒计算方法.将词计算模型的基本方法(模糊数学)应用到粗糙集模型中就形成了模糊粗糙集和粗糙模糊集理论.模糊集和粗糙集理论在处理不确定性和不精确性问题方面推广了经典集合论,这2个理论的比较和融合是人们感兴趣的话题[108].模糊粗糙集理论模型的建立和发展,成为粗糙集理论推广的主要方向之一.从Dubois等人[109]提出模糊粗糙集理论,到后来的各种广义模糊粗糙集理论、公理化的模糊粗糙集理论[110-111],使该理论的发展达到了一个相对完善的状态.张铃等人[35]将模糊集理论应用到商空间理论得到模糊商空间理论,利用模糊商空间理论建立了从大量的事物(数据)中获取具有粒度结构(层次)的知识的方法,然后对各商空间提取相应的知识.从而实现了从模糊信息粒结构到分层递阶结构再到具有粒度结构的知识的相互转化.毛军军等人[112]从商空间理论和信息粒度原理角度出发,引入模糊商空间形成的分层递阶结构,将Fuzzy聚类分析应用于实例.与粗糙集理论相比[113],商空间理论对分类界线不确定(或是模糊的情况)也可以求解.
虽然商空间理论、词计算理论和粗糙集理论等粒计算模型从解决问题的初衷和解决问题的目标不尽相同,各有特色,但是三者都有一个共同的特点,就是在处理实际复杂问题时,不一定去追求问题的完美解或精确解,而是根据实际需求,得到近似的较优解.如果将三者结合起来,充分发挥它们各自的优
#
16
#智 能 系 统 学 报 第2卷
势,将形成更加有效的粒计算方法和理论.目前,模糊粗糙集,粗糙模糊集和模糊商空间对于处理复杂问题都表现出比单一模型更好的优势,得到较好的发展.但如何将粗糙集与商空间有效地结合起来,还没有进一步的研究成果.
基于划分的粒计算模型是粗糙集理论模型的一种特例.它将概念知识分为内涵和外延,在外延上利用集合论上的交并等运算来合成粒子或分解粒子,在内涵上采用属性的多少来控制粒子的大小.基于覆盖的粒计算模型是比基于划分粒计算模型更广的一种粒计算模型,是广义粗糙集理论模型的一种特例.这2个模型都是通过某种二元关系(等价关系或非等价关系)产生邻域,再通过Zoo ming in和Zo o m ing out2个算子(或其他类似的算子)来实现不同粒层上粒子之间的相互转化.基于容差关系的粒计算模型和基于相容关系的粒计算模型实质是同一个模型,都是基于自反和对称的二元关系,只是各自的侧重点不同.基于概念格的粒计算模型是一种层次结构模型,它的粒子之间通过包含关系形成偏序关系,构成一个完备格.在知识系统中,概念信息粒和概念知识粒之间的相互转化为概念的形成奠定了基础,也为概念知识的获取提供了方法.而结合神经网络形成的神经网络粒计算模型在知识获取方面表现出较大的优势[49-50].
5 粒计算的应用研究
粒计算方法的应用越来越广泛,已经渗透到自然科学和社会科学的很多领域.这里作一个简单的介绍.
5 1 图形图像处理
图像分割是图像分析和处理技术的重要手段,是模式识别、图像处理、计算机视觉等领域的一个基础环节.一个图像分析系统是否成功,很大程度上依赖于分割的质量[31,114].随着数学理论特别是应用数学理论的发展,人们借助新的数学理论,对图像分割问题进行研究,并提出了图像分割的许多方法.基于粗糙集的粒计算方法在适当降低精确度为代价的条件下可以解决这一问题.Zadeh提出了模糊信息粒理论研究的一般框架后,Pedrycz等人[115]深入研究了信息粒间的结合问题,并结合数字化图像可粒化的特点,讨论了利用图像的内容信息和空间信息进行粒化的问题.后来,H iro ta和Pedry cz[116]用模糊关系来描述一幅静态灰度图像,提出了基于模糊关系计算的图像压缩方法,将模糊信息粒化思想运用到图像压缩领域.N obuhar a等人[117]提出了一种求解模糊关系方程最大解的快速方法,减少了图像重构的运算量.修保新等人[118-119]给出了基于模糊信息粒化思想的图像边缘检测方法,并在基于图像模糊粒化思想进行图像插值的基础上,提出了具体的基于图像模糊粒化结构的插值方法.刘仁金等人[31,114,120]通过对粒度概念及粗糙集、模糊集等粒计算理论的比较研究以及对图像分割概念分析及对现有的图像分割方法系统分析,提出了图像分割中的商空间粒度原理和基于粒度合成技术原理的纹理图像分割算法,成功设计出纹理图像的分割算法.
5 2 海量数据挖掘
随着计算机及网络的日益普及,丰富的数据与贫乏的知识问题日见突出.不同领域的人们都期待着从这些数据中得到自己的答案,将信息变为知识.数据挖掘就是从大型数据库或数据仓库中储存的大量的、不完整的、有噪声的数据中发现潜在的、有价值的、有趣知识的过程.面对海量数据处理,人们提出了各式各样的挖掘方法.粒计算方法凭借自身的优势在数据挖掘中显示出较大的优势.
基于模糊集的词计算模型是较早提出的粒计算模型,在数据挖掘中有非常成功的应用.模糊集在数据挖掘中应用最多的是聚类分析.聚类分析是通过相似性将用户或数据记录进行分组,从而获得相应的规则.与分类不同,聚类是一种无导师的学习,它将论域中的所有对象划分为簇,同一簇中的对象具有很高的相似性,不同簇中的对象则很不相似,即差异很大[48].将模糊集引入聚类分析的思想,是首先由Bellman、Kalaba和Zadeh等人于1966年提出的,后来有许多研究者对模糊聚类进行了研究,提出了基于摄动的模糊聚类方法等新的模糊聚类算法.近年来聚类方法层出不穷,文献[48]从信息粒度的角度剖析了聚类和分类技术,试图使用信息粒度原理的框架来统一聚类和分类.从信息粒度的观点来看,聚类是在一个统一的粒度下进行计算,而分类却是在不同的粒度下进行计算.
粗糙集理论是一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法.由于它是建立在分类机制基础之上的方法,因而它在数据挖掘分类问题中的应用很多.粗糙集理论在分类问题中的应用大致可以分为2类[121]:一是利用粗糙集理论的属性约简、值约简及核属性,直接从数据表中获取分类规则;二是将粗糙集理论与其他方法结合起来进行分类[122-124].
商空间理论是研究不同粒度世界的数学工具.在面对数据仓库中海量数据挖掘时,可以针对要处
#
17
#
第6期 王国胤,等:粒计算研究综述
理的问题,在保证问题求解精度的前提下,选择合适的粒度空间,这样既可以得到所需的处理结果,又可以提高挖掘知识的效率.张等人[91]利用商空间粒度理论中将原问题变成商空间层次上的问题进行描述的方法,引入对数据库和数据仓库不同粒度问题处理,从不同粒度去考察数据库,得出了比较满意的结果.
经典的Apriori算法是一种宽度优先算法,通过对数据库的多次扫描来发现所有的频繁项目集.文献[125]提出了一种基于粒计算的关联规则挖掘算法.该算法使用粒的!与?计算来求项目集的支持度,而不用多次遍历数据库,避免了模式的匹配运算,还利用信息粒的!或?计算来求概念层次树上每个节点的信息粒.这样能简单有效地由包含数据项为孩子的支持度得到包含其双亲的支持度.
5 3 复杂问题求解
面对复杂的、难于准确把握的问题,人们通常不是采用系统的、精确的方法去追求问题的最佳解,而是通过逐步尝试的办法达到有限的合理的目标,也就是取得所谓足够满意的解.人类就是采用这种概略的、由粗到细、不断求精的多粒度分析法,避免了计算复杂度高的困难,使得原来看似非多项式难解的问题迎刃而解[95].对于复杂问题的描述方法,关键在于不同粒度世界的描述问题.商空间模型给出了描述不同粒度世界的分层递阶方法,再通过合成技术将不同角度、不同层次上得到的信息合成得到原问题的解.近年来,针对实际问题,很多学者将商空间理论进行了推广和应用[89-91,126-127].
基于粒计算的应用还有很多,如在模式识别中,因为基于精确数学模型的经典模式识别方法虽然取得了一些成果,但面对复杂的系统,传统的方法遇到了挑战[63].实践证明,越是复杂的控制系统、难以建立精确数学模型的智能系统、越难以实现精确定量计算的信息系统,基于粒计算的模式识别方法的作用就越大.在智能控制中,基于模糊集合论的模糊控制理论,在20世纪70年代取得了辉煌的成就,到了80年代,基于粗糙集理论的粗糙控制论得到了快速的发展.近年来,基于模糊商空间的智能控制又得到很好的应用[92-93].在医疗诊断系统中,刘清等人[30,128]依据血液粘稠度信息研制了一个诊断大出血的软件系统(DS BV S),它是一个基于粒计算的专家推理系统.在人工神经网络中,Zhang等人[49-50]对粒神经网络进行了探讨,并在快速知识发现中得到很好的应用.在知识获取中,胡军和王国胤等人[129]利用二进制编码技术来构造粒子,提出了一种新的属性约简方法.苗夺谦等人[130]利用粒计算的思想,结合Skow ron不分明矩阵,给出了粒计算方法在知识约简中的应用模型和实例.在语言动力学系统中,Wang[37]给出了基于词计算的语言动力学系统的计算理论框架.在生物信息处理中,毛军军等人[94]利用归一化距离度量和模糊等价关系,结合商空间理论,分析了生物信息序列之间比较的本质问题.
总之,粒计算的应用相当广泛,特别是在处理模糊的、不完整的、不精确的和不确定的海量数据挖掘等方面具有突出的优势,它的应用已经涉及到航空、生物、农业等相关领域,这里不再一一赘述.
6 粒计算研究的展望
粒计算的研究,虽然已经取得一定的成果,且在很多领域得到应用,并取得较好的效果.但是,作为一种正在兴起的智能计算方法,粒计算本身还有许多地方有待发展和完善,对粒计算的研究还存在很多有待进一步研究的问题.这里从以下几个方面进行讨论.
6 1 构建统一的粒计算模型
虽然词计算模型、粗糙集模型和商空间模型之间具有不同程度的联系,但处理实际问题时,人们往往根据问题的实际情况选择其中的某种模型求解.如对于信息表的约简、规则的提取、海量数据信息的挖掘问题,人们可能会选择粗糙集理论模型;对于具有偏序(半序)关系的对象集问题,人们可能会选择商空间理论模型;而对于模糊现象,人们可能会选择词计算模型.但人们很少将同一问题在不同模型下进行考虑.换句话说,如何去寻找解决实际问题的统一粒计算模型,是粒计算研究工作中可能长期存在的问题.这种统一模型的构建将可能深化粒计算的研究,便于人们探索综合利用各种理论模型的优点来解决复杂问题.
6 2 复杂问题空间的粒化
问题空间的粒化是进行粒计算的必要前提.面对具体的实际复杂问题,粒化的程度直接影响着问题求解的计算复杂度和效率.既要避免粒度过粗造成求解失败,也要避免粒度过细造成信息的冗余而导致求解效率低下.因此,对于具体的复杂问题,如何确定出粒化程度的标准是粒计算的关键问题.不同的问题,粒化程度的标准可能无法统一,但面临新的复杂问题,人们可能要尝试多种不同程度的粒化标准,快速寻找到实际问题的最优粒化程度是问题求解的关键.因此,如果能够建立一个求解最优粒化
#
18
#智 能 系 统 学 报 第2卷
程度的形式化数学模型,将是一个非常有意义的工作.如从粒化的复杂度、合成的复杂度以及在粒子上求解的复杂度等多方面建立一个求解最优粒化程度的数学模型.该模型的建立将有效地推进粒计算在各类复杂问题求解中的应用.另外,在粒化程度已知时,粒化的方法将直接决定粒化的效率.如粗糙集模型采用等价关系进行粒化,商空间模型利用等价关系建立分层递阶的问题空间模型,而词计算用模糊集得到粒子.尽管在粒计算的各种模型中,一些算法在某些具体实例上获得了成功,但是这些方法缺乏通用性.粒计算的粒化算法设计是一个复杂的问题,迄今为止,还没有一套较成熟的方法.如果能够借鉴现有的相关理论设计出粒计算的粒化算法,逐步形成一套算法体系.如用王国胤提出的自主式知识获取方法[131-132],利用数据本身的特点来驱动问题空间的粒化,力争实现自主式的粒化过程,从而获得符合实际问题的粒化算法,可能是解决这一问题的有效方法.
6 3 粒层之间的转换
不同粒层次之间的转换是粒计算的一个主要问题.首先,不同粒层之间必须能够自由的转换,往返自如.其次,在能够转换的基础上,确保问题的主要性质不变.例如商空间理论中的!保真?、!保假?原理,是确保商空间理论能够解决复杂问题的关键.模糊集理论模型中截集具有某些性质的不变性.粗糙集理论模型中的核属性是属性约简的不变属性.在基于划分模型的粒计算模型和基于覆盖的粒计算模型中,不同层次之间通过Zo oming in和Zoom ing out2个算子来实现粒层之间的转换.但在这些粒计算模型中,粒层之间的转化方法各不相同,且在转换过程中,如何确保主要性质不变,以及属性不变的程度等问题没有一个统一的标准.当然,不同复杂问题,其方法不同,主要属性不变的要求程度也可能不同.但如果能够建立一个用于计算不同模型的!保性?程度的形式化数学模型,将有助于粒计算模型不同粒层之间的相互转化.虽然张钹和张铃从定性的角度提出了商空间理论中的!保真?和!保假?原理以及!弱保真?和!弱保假?原理,但如何从定量的角度去分析不同粒层之间相互转换后重要属性的不变性的研究工作,目前还没有研究人员对之进行讨论.如果能够从定量的角度去研究问题在不同粒层上表现出来的!保真?和!保假?程度,将有利于实现不同粒层之间的相互转化,有助于提高用粒计算方法求解复杂问题时的收敛速度.6 4 高效的粒计算方法
粒计算方法的初衷就是求解复杂问题.而用传统的方法来解决实际的复杂问题,不管是时间复杂度,还是空间复杂度,往往都非常高.粒计算方法要得到广泛的推广和应用,其复杂度应该低于现有的传统方法.虽然目前的粒计算方法在计算效率上较传统方法有一定的优势,但它们处理问题的时间复杂度都大于或等于O(n2).因此,研究高效粒计算方法是一个重要的课题.如果能获得解决问题的时间复杂度为O(n1.5)或O(n lg n),甚至更低的粒计算算法,将有助于提高用粒计算方法解决复杂问题的效率.
6 5 新的粒计算模型
词计算模型、粗糙集理论模型和商空间理论模型在处理复杂问题时表现出不同的优势,也表现出某些方面的不足.例如,粗糙集理论的优势在于对知识的表示,而商空间理论的特色在于对问题结构的讨论,而形式概念分析具有良好的层次结构等特色.如何将不同的粒计算模型有机地结合起来,发挥各自的优势,弥补各自的缺陷,从而寻求一个更有效的粒计算模型,是目前粒计算工作中的一个重要研究课题.张铃和张钹将商空间理论和模糊集理论结合起来得到的模糊商空间理论表现出良好的性能,它能够更好地反映人类处理不确定问题的若干特点[35].将模糊集理论和粗糙集理论结合形成模糊粗糙集理论和粗糙模糊集理论的文献很多,并在处理不确定信息时表现出更好的性能[108-111].但关于如何将粗糙集理论与商空间模型有机地融合起来,以及如何将粗糙集理论和形式概念分析2种智能数据分析方法融合起来,形成更有效的粒计算模型的研究工作很少.另外,关于论域空间上代数运算的讨论,在粗糙集理论和商空间理论中都不是很多,如果能将代数中的商代数理论移植到商空间理论中,问题求解的商空间理论的内涵将得到丰富.总之,发现更有效的粒计算模型将是研究者追求的目标.
6 6 动态粒计算模型
目前,绝大多数粒计算模型都是基于静态数据(信息)的处理.而很多实际问题的信息都是随着时间的变化而动态变化的.如网络数据、入侵检测数据和卫星检测数据等都是动态数据.如何构建基于动态数据处理的粒计算模型是一个具有广泛应用前景的课题.
6 7 自主式粒计算模型
在没有领域先验知识条件下的不确定知识的主动式学习是机器学习领域中新兴的热点问题.对于不确定性问题的处理,现在还没有一个能够摆脱先
#
19
#
第6期 王国胤,等:粒计算研究综述
验知识,完全由原始数据自主决策的理论方法.如果能够摆脱学习过程中对先验知识的依赖,由数据自主地完成知识的获取过程,无疑将对机器学习理论的推广起到重要的推动作用.王国胤等人[131-132]通过研究决策表和决策规则的不确定性,建立基于粗糙集表示、度量和处理不确定性信息和知识的理论,并且结合Skow ron缺省规则获取算法,提出一种不确定性条件下的数据自主式学习模型和方法,并通过仿真实验,验证了该自主式学习方法的有效性.这个研究工作为知识的获取提供了一个新的研究方向.而面对复杂问题的求解,多数粒计算模型借助先验知识对问题空间进行粒化,如模糊集理论往往借助模糊关系的截集产生粒子(依赖隶属函数),而商空间理论和粗糙集理论模型借助等价关系产生粒子,但在不完备信息系统中这些粒计算模型无法借用等价关系,需要人为地增加辅助信息(如去掉等价关系的条件).这些模型从某种意义上讲都不是自主式的求解模型.因此,建立如何根据问题已有的信息,而不依靠先验知识获得问题解的粒计算模型具有非常重要的价值,可为真正的智能化数据挖掘提供理论依据.
6 8 粒计算方法的模糊化
在自然科学或社会科学研究中,存在着许多定义不很严格或者说具有模糊性的概念.各门学科,尤其是人文、社会学科及其他!软科学?无法用精确的数学描述.随着计算机、控制论、系统科学的迅速发展,要使计算机能像人脑那样对复杂事物具有识别能力,就必须研究和处理模糊性问题.从现有的集合论发展看来,精确的康托集不能描述的问题已经逐渐转化为由Zadeh提出的模糊集来描述,而康托集是模糊集的特殊情况.因此,原有的基于康托集的很多理论可以推广到模糊集理论,而原来用康托集无法解决的问题,用模糊集可能会得到解决.因此,基于经典集合论的粒计算方法,通过一定的转化可以推广为基于模糊集的粒计算方法.如模糊商空间理论、模糊粗糙集理论、模糊区间估计理论都是典型的模糊化的粒计算方法,而模糊概念格理论、模糊D S 证据理论和模糊神经网络等则是近年来人们提出的新的粒计算模型.由于粒计算方法的初衷就是解决复杂问题,而实际的复杂问题往往无法用精确的数据来刻画.比如,研究一个通过电话听筒声音辨别来电是谁这样一个简单的语音识别系统,就无法用精确数学刻画,必须借助模糊数学.尽管普通的精确方法(如数学、化学等)在某些科学领域应用相当广泛,也一直尝试着应用到人文学科中,但人们在长期的实践中,已经清楚地认识到精确的方法应用到人文学科有很大的局限性,传统方法过于精确的特点导致在某些人文系统中的应用出现异常和失败.为了求解巨大复杂的人文学科系统问题,如病虫测报、品种选育、图像识别、天气预报、地质地震、交通运输、医疗诊断、信息控制、人工智能等诸多领域,研究模糊化的粒计算方法是必然的趋势.因此,粒计算方法的模糊化是一个极具潜力的研究方向.通过对它的研究,可以清楚地揭示不同粒计算模型内在的本质特征.
6 9 粒计算模型应用的推广
粗糙集、模糊集和商空间理论各自的应用比较多见,但基于上述理论的粒计算模型的很多文章对粒计算的研究还停留在理论上,没有结合具体问题进行讨论.因此,一个当务之急的研究课题就是结合具体的问题来分析、讨论和应用粒计算模型的重要结论.图像处理、小波分析等是粒计算模型得以应用的很好领域.因为一幅图像的所有像素之间存在自然的结构,可以用拓扑或者闭包运算来描述这种结构,进而利用商空间理论解决数字图像的相关问题.虽然现在很多粒计算模型都应用在图像处理领域,但这方面的应用研究还应该进一步深入.张钹和张铃利用分层递阶的商空间结构提出网络推理模型,并把确定性推理和不确定性推理统一起来,成功应用在复杂问题的推理中.另外,商空间理论也在运动规划、时间规划和统计启发式搜索方面得到较广泛的应用.如何将现有的粒计算模型进行推广应用,逐渐形成求解复杂问题的有效粒计算模型方法,将有助于人们对复杂问题的求解.
粒计算方法的研究是近几年人工智能领域中崛起的一个新方向,它用可行的满意近似解替代精确解,改变了传统的计算观念,其主要思想是在不同的粒度层次上进行问题求解,在很大程度上体现了人类问题求解过程中的智能.虽然粒计算方法的应用已经逐渐得到人们的认可,但很多环节需要进一步的探讨和研究,如粒化标准、粒子的表述、合成的复杂度以及高效的实现等问题,这些工作都有待进一步解决.
7 结束语
粒计算是人工智能领域中的一种新理念和新方法,它覆盖了所有和粒度相关的理论、方法、技术和工具,主要用于对不确定、不精确、不完整信息的处理,对大规模海量数据的挖掘以及对复杂问题的求解.粒计算最本质的思想是通过合适粒度的选择,来寻找问题的一种较好的、近似的解决方案,从而降低
#
20
#智 能 系 统 学 报 第2卷
问题求解的复杂度.本文首先简要回顾了粒计算的基本发展情况,着重介绍了粒计算理论的几个基本组成和基本问题,论述了粒计算的基本模型和方法,并探讨了这些模型之间的差异和相互关系,最后提出了粒计算的进一步研究方向和问题.希望这些工作能够对粒计算的研究和推广提供借鉴和帮助.
参考文献:
[1]ZA DEH L A.F uzzy sets and infor matio n g ranulation.
adv ances in fuzzy set theo ry and applicatio ns[M].Am st erdam:N or th H o lland Publishing,1979.
[2]H OBBS J R.Gr anularit y[A].P ro ceedings of the Ninth
Internatio nal Joint Conference on A rtif icial Intellig ence
[C].L os A ng eles,CA,1985.
[3]L IN T Y.N eig hbor hood systems and r elatio nal database
[A].P roceedings of CSC88[C].N ew Y or k,1988.
[4]L IN T Y.G ranular computing o n binar y relatio ns I:data
mining and neig hbo rhoo d systems,II:ro ug h set r epr e sentations and belief funct ions,roug h set s in know ledge disco ver y[M].Physica V erlag,1998:107-140.
[5]L IN T Y.Data mining:g ranular computing appro ach
methodolo g ies for know ledge disco ver y and data mining
[A].P roceedings of P AK DD99[C].[S.l.],1999.
[6]L IN T Y.G ranular co mputing:fuzzy lo gic and r ough
sets.Co mputing w ith Wo rds in Infor matio n/Int elligent Systems[M].P hysica V erlag,1999.
[7]L IN T Y.Data mining and machine o riented modeling:a
g ranular com puting appro ach[J].Jo ur nal o f A pplied In
tellig ence,2000,13(2):113-124.
[8]L IN T Y.G ranular com puting:st ruct ur es,representa
tions,a pplicat ions and future directio ns[A].T he P ro ceedings of9th International Conference,R SFDG rC2003
[C].[S.l.],2003.
[9]L IN T Y.G ranular comput ing ro ug h set perspective[J].
T he N ewsletter of t he IEEE Co mputational Intellig ence Society,2005,2(4):1543-4281.
[10]L IN T Y.Gr anular computing:a problem solving para
dig m[A].T he P ro ceedings of the2005IEEE Inter na tional Conference o n Fuzzy Sy stems[C].[S.l],2005. [11]张 钹,张 铃.问题求解理论及应用[M].北京:清华
大学出版社,1990.
[12]Z HA N G B,ZH A NG L.T heor y and a pplicat ions of
pr oblem so lv ing[M].A mster dam:N ort h H olland Pub lishing,1992.
[13]ZA DEH L A.T ow ards a theory of fuzzy infor mation
g r anulation and its cent rality in human reasoning and
fuzzy lo gic[J].F uzzy Sets and Systems,1997,19:111 -127.
[14]Y A O Y Y.Relational inter pr etatio ns of neig hbo rhood
operato rs and ro ug h set appr ox imatio n o perat ors[J].
Informat ion Sciences,1998,111:239-259.
[15]Y A O Y Y.R ough sets,neig hbor hood sy st ems,and
g ranular computing[A].Pr oceeding s of the1999IEEE
Canadian Co nfer ence o n Electr ical and Computer Eng i neer ing[C].[S.l.],1999.
[16]Y AO Y Y.Gr anular comput ing using neig hbo rhoo d sys
tems,advances in soft co mputing:eng ineer ing desig n and manufacturing[A].T he3rd On line W or ld Co nf er ence on Soft Computing(WSC3)[C].Lo ndon,1999. [17]YA O Y Y.A partition mo del of gr anular co mputing
[J].L N CS T r ansactio ns on Rough Sets,2004(1):232 -253.
[18]Y AO Y Y.Str atified ro ug h sets and g ranular co mputing
[A].Pr oceeding s o f t he18th Inter nat ional Conference
of the N o rth A merican Fuzzy Info rmatio n P ro cessing Society[C].N ew Y or k,1999.
[19]Y AO Y Y.I nfo rmatio n g ranulatio n and r ough set ap
pr ox imatio n[J].Inter national Journal of Intellig ent Sys tems,2001,16(1):87-104.
[20]Y AO Y Y.G ranular computing fo r data mining[A].
Pr oceeding s of SPIE Conference on Data M ining,Intru sion Detectio n,Info rmation Assurance,and Data N et wo rks Security[C].K issimmee,U SA,2006.
[21]CH EN Y H,YA O Y Y.M ult iview intelligent data a
nalysis based on g ranular co mputing[A].Pr oceeding s o f 2006I EEE Int ernational Conference o n Gr anular Com puting[C].[S.l.],2006.
[22]Y AO Y Y.T hree per spectiv es of gr anula r co mputing
[J].Jour nal of Nanchang Inst itute of T echnolog y, 2006,25(2):16-21.
[23]SK OW RON A.T ow ard intellig ent systems:calculi of
infor mation g ranules[J].Bulletin of Inter national Ro ug h Set Society,2001(5):9-30.
[24]SKO WRO N A,ST EP AN IU K J.T ow ards disco very of
infor mation g ranules[A].Pr oceeding s o f PK DD99[C].
[S.l.],1999.
[25]SKO WR ON A,ST EPA N IU K https://www.doczj.com/doc/8814247929.html,r mation g r anules:
tow ards foundatio ns o f g ranular co mputing[J].Interna tional Jour nal of Intelligent Systems,2001,16:57-85.
[26]P OL K OW SKI L,SK OW RO N A.T ow ards adaptiv e
calculus of g ranules[A].Pr oceeding s of1998IEEE In ternational Co nfer ence o n F uzzy Sy stems[C].[S.l.], 1998.
[27]PO L KO WSK I L,SK OW RON A.Ro ugh sets in kno wl
edg e discov ery[M].H eidelberg:Phy sica Ver lag,1998.
[28]刘 清,黄兆华.G 逻辑及其归结推理[J].计算机学
报,2004,27(7):865-872.
L IU Q ing,H U AN G Zhao hua.G log ic and its r eso lu tion r easo ning[J].Chinese Journal of Computers,2004,
#
21
#
第6期 王国胤,等:粒计算研究综述
27(7):865-872.
[29]刘 清,刘 群.粒及粒计算在逻辑推理中的应用[J].
计算机研究与发展,2004,41(4):546-551.
L IU Q ing,L IU Q un.G ranules and appplicat ions of
g r anular computing in log ical r easoning[J].Journal of
Co mputer R esear ch and Dev elo pment,2004,41(4):546 -551.
[30]刘 清.Roug h集及Ro ug h推理[M].北京:科学出版
社,2001.
[31]刘仁金,黄贤武.图像分割的商空间粒度原理[J].计算
机学报,2005,28(10):1680-1685.
L IU Renjin,H U A N G Xianw u.T he g ranular theo rem o f quotient space in image segmentation[J].Chinese Jo ur nal of Computers,2005,28(10):1680-1685. [32]王国胤.Ro ug h集理论在不完备信息系统中的扩充[J].
计算机研究与发展,2002(10):11-15.
W A NG G uo yin.Extension o f ro ug h set under incom plete info rmatio n sy stems[J].Journal of Computer R e search and Development,2002(10):11-15.
[33]伞 冶,叶玉玲.粗糙集理论机器在智能系统中的应用
[J].智能系统学报,2007,2(4):40-47.
SA N Y e,Y E Yuling.R ough sets theo ry and its applica tion in the intelligent sy stems[J].CA A I T ransactions on
I ntelligent Systems,2007,2(4):40-47.
[34]ZH AN G L,ZH A N G B.A quotient space a ppro ximation
model o f multi r eso lutio n sig nal analysis[J].J Co mput Sci&T echnol,2005,20(1):90-94.
[35]张 铃,张 钹.模糊商空间理论(模糊粒度计算方法)
[J].软件学报,2003,14(4):770-776.
Z HA N G L ing,ZH A NG Bo.T heor y of fuzzy quotient space(methods of fuzzy gr anular co mputing)[J].Jour nal o f Softw are,2003,14(4):770-776.
[36]苗夺谦,范世栋.知识的粒度计算及其应用[J].系统工
程理论与实践,2002,22(1):48-56.
M IAO Duo qian,FA N Shidong.T he calculatio n of know ledge g ranulation and its application[J].Sy stems Eng ineer ing T heo ry&P ractice,2002,22(1):48-56.
[37]王飞跃.词计算和语言动力学系统的计算理论框架
[J].模式识别与人工智能,2001,14(4):377-384.
W A NG Feiyue.Co mputing w ith wo rds and a fr ame w or k fo r co mputatio na l ling uist ic dynamic systems[J].
Pattern Recog nitio n and Ar tificial Intellig ence,2001,14
(4):377-384.
[38]WA N G G Y,H U F,HU AN G H,et al.A gr anular
comput ing model based o n to ler ance r elation[J].T he Journal o f China U niversit ies of Posts and T eleco mmu nicat ions,2005,12(3):86-90.
[39]胡 峰,黄 海,王国胤,等.不完备信息系统的粒计
算方法[J].小型微型计算机系统,2005,26(8):1335-1339.
H U F eng,H U A NG Hai,WA N G Guoy in,et al.G ran
ular computing in inco mplete infor mation sy stems[J].
M ini micro Sy st ems,2005,26(8):1335-1339.
[40]邓 蔚,王国胤,吴 渝.粒计算综述[J].计算机科
学,2004,31(10):178-181.
DEN G W ei,W A NG G uo yin,WU Yu.A survey o f g ran ular computing[J].Comput er Science,2004,31(10): 178-181.
[41]邓 蔚,王国胤,吴 渝.粒计算对进化计算的一个改
进[J].计算机科学,2004,31(10):209-211.
DEN G W ei,W AN G G uo yin,WU Y u.An impro ved al go rithm of evolutionar y co mputation based o n g ranular computing[J].Computer Science,2004,31(10):209-211.
[42]安久江,甘 全,王国胤,等.一种基于粒计算的规则知
识获取算法[J].计算机科学,2005,32(8):137-140.
A N Jiujiang,GA N Q uan,WA N G Guoy in,et al.A n Al
go rithm fo r Rule and Know ledge A cquisit ion Based o n Gr anular computing,Co mputer Science,2005,32 (8A):137-140.
[43]邓 蔚,王国胤,吴 渝.基于近似分割的粒计算规则
获取算法[A].中国人工智能学会第11届学术年会论文集[C].武汉,2005.
DEN G W ei,W A NG Guoy in,W U Yu.A rule acquisitio n algo rithm o f gr anular computing based o n appro ximat e partition[A].Pro ceedings of2005N ational Conference on A rt ificial Intelligence[C].Wuhan,2005.
[44]A N J J,WA N G G Y,W U Y,et a l.A rule generatio n
alg or ithm based on g ranular co mputing[A].2005IEEE Internatio nal Conference on G ranular Comput ing[C].
Beijing,2005.
[45]Z HEN G Z,H U H,SH I Z Z.G ranulatio n based imag e
tex tur e recog nitio n[J].L ectur e N o tes in Co mputer Sci ence,2004,3066:659-664.
[46]ZH ENG Z,HU H,SH I Z Z.T o lerance relat ion based
infor mation g ranular space[J].L ectur e N ot es in Com puter Science,2005,3641:682-691.
[47]ZH EN G Z,HU H,SHI Z Z.T o ler ance g r anular space
and it s applications[A].IEEE Internatio nal Conference on Gr anular Comput ing[C].Beijing,2005.
[48]卜东波,白 硕,李国杰.聚类/分类中的粒度原理[J].
计算机学报,2002,25(8):810-816.
BU D ongbo,BA I Shuo,L I Guojie.P rinciple of gr anu lar ity in cluster ing and classificatio n[J].Chinese Jo ur nal of Computers,2002,25(8):810-816.
[49]ZH A NG Y Q,F RA SER M D,GA G LIA N O R A.G ran
ular neural netw or ks fo r numer ical linguistic data fusio n and know ledge discov ery[J].IEEE T r ansactio ns o n N eur al N etw or ks,2000(11):658-667.
[50]ZH AN G Y Q.Co nstr uctiv e gr anular sy stems w ith uni
#
22
#智 能 系 统 学 报 第2卷
v ersal appro ximat ion and fast know ledge disco very[J].
IEEE T rans o n F uzzy Systems,2005,13(1):48-57.
[51]李道国,苗夺谦,杜伟林.粒度计算在人工神经网络中的
应用[J].同济大学学报(自然科学版),2006,34(7): 960-964.
L I Dao guo,M IA O Duoqian,DU W eilin.A pplication of
g ranular computing to ar tificial neura l netw or k[J].
Jour nal of T ong ji U niver sity(N atural Science),2006,34
(7):960-964.
[52]齐 红.基于形式概念分析的知识发现方法研究[D].
吉林:吉林大学,2005.
QI H ong.Know ledg e discover y methods r esear ch based o n fo rmal concept analy sis[D].Jinlin:Jinlin U niv ersity, 2005.
[53]杜伟林,苗夺谦,李道国,等.概念格与粒度划分的相关
性分析[J].计算机科学,2005,32(1):182-187.
D U Weilin,M I AO Duoqian,L I D ao guo,et al.A na ly
sis on r elationship betw een concept lattice and gr anular par titio n lattice[J].Computer Science,2005,32(1): 182-187.
[54]Y AG ER R R.Some lear ning par adig ms fo r gr anular
comput ing[A].2006IEEE International Conference on Gr c[C].At lanta,U SA,2006.
[55]LI N T Y.Gr anular co mputing2:inf rastructures fo r
A I eng ineering[A].2006IEEE Inter national Co nfer ence
on Gr c[C].A tlanta,U SA,2006.
[56]BARG IEL A A,P EDR YCZ W.T he ro ots of gr anular
comput ing[A].P rocceding s of the2006IEEE Inter na tional Conference o n G ranular Computing(Gr C06)
[C].A tlanta,U SA,2006.
[57]Y A GER R R,F ILEV D.Operations for gr anular com
puting:mix ing w o rds and number s[A].IEEE Inter na tional Co nfer ence on Fuzzy Systems[C].[S.l.],1998.
[58]陈万里.基于商空间理论和粗糙集理论的粒计算模型研
究[D].安徽:安徽大学,2005.
CH EN W anli.R esear ch on mo dels of g ranular compu ting based o n quotient space theo ry and r ough set theor y
[D].A nhui:Anhui U niver sity,2005.
[59]郑 征.相容粒度空间模型及其应用研究[D].北京:中
国科学院研究生院,2006.
ZH EN G Zheng.T olerance gr anular space and its appli catio ns[D].Beijing:G raduate Schoo l o f the Chinese A cademy of Sciences,2005.
[60]仇国芳,陈 劲.概念知识系统与概念信息粒格[J].工
程数学学报,2005,22(6):963-969.
QIU Guofang,CH EN Jin.Concept know ledge system and co ncept infor matio n gr anula r lattice[J].Chinese Jo ur nal of Engineer ing M athematics,2005,22(6):963 -969.
[61]阮 达,黄崇福.模糊集与模糊信息粒理论[M].北京:
北京师范大学出版社,2000.
[62]ZA DEH L A.F uzzy log ic=co mputing w ith w ords[J].
IEEE T rans on Fuzzy Sy stems,1996(4):103-111. [63]李道国,苗夺谦,张东星,等.粒度计算研究综述[J].计
算机科学,2005,32(9):1-12.
L I Daog uo,M I AO Duoqian,ZH AN G Do ng x ing,et al.
A n o ver view of gr anular computing[J].Comput er Sci
ence,2005,32(9):1-12.
[64]ZA DEH L A.T o war ds a theor y o f fuzzy info rmatio n
gr anulat ion and its cent rality in human reaso ning and fuzzy lo g ic[J].Fuzzy Sets and Sy st ems,1997,19:111-
127.
[65]ZA DEH L A.So me reflections on so ft comput ing,
gr anular co mputing and their roles in the co nception, desig n and utilization of info rmatio n/intellig ent systems [J].Soft Comput ing,1998(2):23-25.
[66]W AN G P.Co mputing w it h w ords[M].N ew Y or k:John
Wiley&Sons,2001.
[67]李 征,邵世煌.基于信息粒化、语词计算模糊控制系统
中的信息重组[J].东华大学学报,2000,2(3):9-13.
LI Zheng,SH A O https://www.doczj.com/doc/8814247929.html, rmatio n r etrieval in fuzzy contr ol system based o n informat ion g ranulatio n and computing with w ords[J].Jour nal o f Do ng hua U ni v ersit y,2000,2(3):9-13.
[68]李 征,王维工.基于信息粒化和语词计算的模糊控制
器[J].辽宁工程技术大学学报(自然科学版),2001,20
(5):636-639.
L I Zheng,W A NG Weig ong.F uzzy co nt roller based o n infor mation g ranulatio n and computing w ith w or ds[J].
Journal of Liaoning T echnical U niversit y(Natur al Sci ence Edit ion),2001,20(5):636-639.
[69]WA N G F Y,T ON G L Y.Ling uistic dynamic systems
and co mputing w ith w or ds for complex sy st ems[A].
Pr oceeding s of I EEE Internatio nal Conference on Sys tems,M an,and Cybernetics[C].N ashv ille,U SA, 2000.
[70]W AN G F Y,LI N Y T.Ling uistic dy namic systems and
comput ing w ith w or ds fo r mo deling and simulat ion of complex systems,in discrete event modeling and simu lation technolog ies:a tapestr y of systems and AI based theor ies and metho do lo gies[M].[S.l.],1998.
[71]WA N G F Y.Co mputing with wo rds and ling uist ic dy
namic sy stems[M].Wo rld Scientific P ublishing Co, 2004.
[72]王飞跃.词计算和语言动力学系统的基本问题和研究
[J].自动化学报,2005,31(6):844-852.
WA N G F eiyue.F undamental issues in research of com puting with w or ds and linguistic dynamic systems[J].
A ct a Automat ica Sinica,2005,31(6):844-852.
[73]PA WL A K Z.Roug h sets[J].Internatio nal Jo urnal of
#
23
#
第6期 王国胤,等:粒计算研究综述
Computer and Infor mation Sciences,1982(11):341-
356.
[74]PA W LA K Z.R ough sets:T heor etical A spects o f R ea
so ning about Data[M].[S.l.]K luw er A cademic Pub lishers,Dor dr echt,1991.
[75]王国胤.Ro ug h集理论与知识获取[M].西安:西安交
通大学出版社,2001.
[76]KRY SZK EIWICZ M.Ro ug h set a ppro ach to incomplete
infor matio n systems[J].Info rmation Science,1998,112: 39-49.
[77]ST EFA N OW SKI J,T SO U K IA S A.O n the extension
of r ough sets under incomplete info rmatio n[A].Pr oc of the7th Internatio nal Wo rkshop on N ew Dir ect ions in Ro ug h Sets,Data M ining,and Gr anular Soft Compu ting[C].Berlin,1999.
[78]王国胤.R ough集理论在不完备信息系统中的扩充
[J].计算机研究与发展,2002,39(10):1238-1243.
W A NG G uo yin.Extension o f ro ug h set under incom plete info rmatio n sy stems[J].Journal of Computer R e search and Development,2002,39(10):1238-1243. [79]Z HA N G Q H,WA N G G Y,HU J,et al.Incomplete
info rmation systems pro cessing based on fuzzy clust e r ing[A].2006IEEE/WIC/ACM Inter national Confer ence o n W eb Intellig ence and I ntelligent Ag ent T echnol o gy[C].Ho ng K ong,China,2006.
[80]张文修,吴伟志,梁吉业,等.粗糙集理论与方法[M].
北京:科学出版社,2001.
[81]黄兆华,邓毅雄.粒计算及其应用的研究[J].华东交通
大学学报,2005,22(5):124-128.
H U A N G Zhaohua,DENG Y ix io ng.A n appr oach fo r
g r anular co mputing and its applicatio n[J].Jo ur nal of
East China Jiaotong U niv ersity,2005,22(5):124-128.
[82]PA WL A K Z.Gr anularit y of kno wledg e,indiscer nibili
ty and r ough sets[A].Pro ceedings of1998IEEE Inter natio nal Conference on Fuzzy Systems[C].[S.l.], 1998.
[83]POL K OW SKI L,SK OW RO N A.R ough neur o compu
ting[A].P roceeding s of the Seco nd Internatio nal Co n fer ence on Ro ug h Sets and Curr ent T rends in Compu ting[C].Ber lin:Spr inger V erlag,2005.
[84]SK O WRO N A.T ow ard intelligent sy stems:calculi of
informat ion gr anules[A].P roceeding s o f International Wor ksho p o n Rough Set T heo ry and G ranular Compu ting(RST GC2001)[C].M atsue,Shimane,Japan, 2001.
[85]P ET ERS J F,SK OW RO N A,SU RA J Z,et a l.M eas
ures o f inclusio n and closeness o f info rmation g ranules:a roug h set approach[A].P roceeding s of t he T hird Inter natio nal Conference on RSCT C2002[C].M alv ern, U SA:Spr inger,2002.[86]PET ERS J F,SZCZU K A M S.Rough neurocom put
ing:a sur vey o f basic mo dels of neur ocomputation[A].
Pr oceeding s of the T hir d Inter national Conference o n RSCT C2002[C].M alver n,U SA:Springer,2002. [87]L IN T Y.G ranular fuzzy sets:a view fo rm roug h set
and pr obability theor ies[J].I nter national Jo ur nal of Fuzzy Systems,2001,3(2):373-381.
[88]Y A O J T,Y AO Y Y.Inductio n of classification r ules
by g ranular computing[A].P ro ceedings of the T hird In ternatio nal Conference o n R SCT C2002[C].M alvern, U SA:Spring er,2002.
[89]徐 峰,张 铃,王伦文.基于商空间理论的模糊粒度计
算方法[J].模式识别与人工智能,2004,17(4):424-429.
XU Feng,ZHA N G L ing,W A NG L unw en.T he ap pr oach o f the fuzzy g ranular com puting based on the theory of quotient space[J].Patter n Recognit ion and
A rtif icial I ntelligence,2004,17(4):424-429.
[90]徐 峰,张 铃.基于商空间的非均匀粒度聚类分析
[J].计算机工程,2005,31(3):26-28.
XU F eng,ZH A N G Ling.A n analysis of uneven g ran ules clustering based on quo tient space[J].Co mputer Eng ineering,2005,31(3):26-28.
[91]张 ,吴 涛,王伦文,等.商空间粒度计算理论在数
据库和数据仓库中应用[J].计算机工程与应用,2003, 39(17):47-49.
ZH A NG M in,WU T ao,W A NG L unwen,et al.T he applicatio n o f gr anula rity of the quo tient space theo ry in dat abase and data w arehouse[J].Com puter Eng ineering and A pplicatio ns,2003,39(17):47-49.
[92]张持健,李 畅,张 铃.商空间理论(粒度计算方法)实
现高精度模糊控制[J].计算机工程与应用,2004,40
(11):37-39.
ZH A NG Chijian,LI Chang,ZH AN G Ling.R ealizing the hig h pr ecision fuzzy co nt ro l based o n the theo ry of quotient space(methods of g ranular computing)[J].
Computer Engineer ing and Applications,2004,40(11): 37-39.
[93]刘 岩,李友一,陈占军,等.基于商空间理论的模糊控
制在航空相机中的应用[J].南京航空航天大学学报, 2006,38(7):88-90.
L IU Yan,L I Yo uyi,CH EN Zhanjun,et al.A pplicatio n of fuzzy co ntro ller based on quo tient space theor y to aer ial camera[J].Jo ur nal of Nanjing U niv ersity of A er o nautics&A str onautics,2006,38(7):88-90.
[94]毛军军,郑婷婷,张 铃.基于商空间理论的生物序列比
较模型[J].计算机工程与应用,2004,40(34):15-17.
M A O Junjun,ZH EN G T ingting,ZH A N G L ing.Bio log ical sequence a lig nments based on quotient space[J].
Co mputer Eng ineering and A pplicat ions,2004,40(34):
#
24
#智 能 系 统 学 报 第2卷
15-17.
[95]张燕平,张 铃,吴 涛.不同粒度世界的描述法???商
空间法[J].计算机学报,2004,27(3):328-333.
ZH A N G Y anping,Z HA N G L ing,W U T ao.T he rep r esentatio n of differ ent g ranular w or lds:a quotient space [J].Chinese Journal of Computer s,2004,27(3):328-333.
[96]Z HU W,WA N G F Y.Reductio n and ax io mizat ion of
Co vering generalized r ough sets[J].Info rmatio n Sci ences,2003,152,217-230.
[97]祝 峰,何华灿.粗集的公理化[J].计算机学报,2000,
23(3):330-333.
Z HU Feng,H E H uacan.T he ax iomatization of the roug h set[J].Chinese Jour nal of computer s,2000,23
(3):330-333.
[98]H U J,W AN G G Y,ZH A N G Q H.U ncerta int y meas
ure o f cov ering g ener at ed roug h set[A].2006IEEE/ W IC/A CM Inter national Conference o n W eb Intelli
g ence and Intellig ent A gent T echnolog y[C].Ho ng
K o ng,2006.
[99]M A J M,ZH AN G W X,LI T J.A Co ver ing mo del of
g r anular comput ing[A].Pr oceeding of the Fo ur th In
ter national Conference on M achine Lear ning and Cyber netics[C].Guangzho u,China,2005.
[100]W ILL E R.Restructuring lattice theo ry:an appro ach based o n hierar chies of co ncepts[M].Reidel:D or
dr echt Boston,1982.
[101]胡可云,陆玉昌,石纯一.概念格及其应用进展[J].
清华大学学报(自然科学版),2000,40(9):77-81.
HU Key un,L U Y uchang,SH I Chunyi.Advances in
concept lat tice and its applicatio n[J].Journal of T sing
hua U niv ersit y(Science and T echnolog y),2000,40
(9):77-81.
[102]仇国芳,陈 劲.概念知识系统与概念信息粒格[J].
工程数学学报,2005,22(6):963-969.
Q IU Guofang,CHEN Jin.Concept know ledge system
and concept info rmatio n g ranular lattice[J].Chinese Journal o f Eng ineering M athematics,2005,22(6):963
-969.
[103]仇国芳,荆彦玲.粗糙集与概念格[M].西安:西安交通大学出版社,2006.
[104]张文修,仇国芳.基于粗糙集的不确定性决策[M].北京:清华大学出版社,2005.
[105]曲开社,翟岩慧.偏序集、包含度与形式概念分析[J].
计算机学报,2006,29(2):219-226.
Q U K aishe,ZH A I Y anhui.Posets,inclusion deg ree theor y and F CA[J].Chinese Journal of Computer s,
2006,29(2):219-226.
[106]蒙祖强,蔡自兴.一种新的计算方法:粒度进化计算[J].计算机工程与应用,2006,42(1):5-8.
M EN G Zuqiang,CA I Zixing.A new co mputing:g ran
ular evolut ionar y comput ing[J].Co mputer Eng ineering and Applications,2006,42(1):5-8.
[107]张 铃.浅谈粒度计算[EB/O B].http://w ww.ahcit.
com,2006-06-21.
[108]黄正华,胡宝清.模糊粗糙集理论研究进展[J].模糊系统与数学,2005,19(4):125-134.
H U A N G Zhenghua,H U Bao qing.T he studies of
fuzzy r ough sets theor y:a survey[J].Fuzzy Systems and M athematics,2005,19(4):125-134.
[109]DU BO IS D,PRA DE H.Ro ug h fuzzy sets and fuzzy roug h sets[J].Int ernational Jo urnal o f General Sys
tems,1990,17:91-109.
[110]GRECO S,M AT AR AZ ZO B,SL OW IFI SK I R.
Fuzzy similar ity relat ion as a basis fo r ro ugh appr ox i
mations[A].RSCT C98[C].H eidelberg:Spr inger
Ver lag,1998.
[111]R ADZ IKO WSK A A M,K ERRE E E.A co mpar ativ e study of fuzzy roug h sets[J].Fuzzy Sets and Systems,
2002,126:137-155.
[112]毛军军,张 铃,许义生.基于商空间和信息粒度的
F uzzy聚类分析[J].运筹与管理,2004,13(4):25-
29.
M AO Junjun,Z HA N G L ing,XU Y isheng.Fuzzy cluster ing analysis based o n quo tient space and infor
matio n g r anular ity[J].O peratio ns Resear ch and M an
ag ement Science,2004,13(4):25-29.
[113]张燕平,张 铃,夏 莹.商空间理论与粗糙集的比较[J].微机发展,2004,14(10):21-24.
ZH A N G Y anping,ZH A NG Ling,XI A Y ing.T o com par e the theor y o f quot ient space w ith roug h set
[J].M icro co mputer D ev elo pment,2004,14(10):21-
24.
[114]刘仁金,黄贤武,孟 静,等.基于商空间的纹理图像分割[J].计算机应用,2004,24(7):37-39.
L IU Renjin,H U A NG Xianw u,M ENG Jing,et al.
T exture imag e seg mentat ion based on quo tient space [J].Com puter A pplicatio ns,2004,24(7):37-39. [115]PEDRY CZ W,SM IT H M H,BA RG IELA A.A gr anular sig natur e o f data[A].Int Conf N AF IPS
2000[C].A tlanta,U SA,2000.
[116]H IRO T A H,P ED RY W.F uzzy r elatio nal compres sion[J].I EEE T rans Sy st,M an,Cybem,1999,29
(3):407-415.
[117]N OBU H AR A H,PEDRY EZ W,H IRO T A K.F ast soling method o f fur y relational equatio n and its appli
cation to image compression/reconstruction[J].IEEE
T r ans Fur y Syst,2000,8(3):325-334.
[118]修保新,吴孟达.图像模糊信息粒的适应性度量及其在边缘检测中的应用[J].电子学报,2004,32(2):
274-277.
X IU Bao xin,W U M eng da.Adapt abilit y measure to
#
25
#
第6期 王国胤,等:粒计算研究综述
fuzzy info rmatio n gr anule o n imag e and its application
to edge detect ion[J].A cta Electr onica Sinica,2004,32
(2):274-277.
[119]修保新,任双桥,张维明.基于模糊信息粒化理论的图像插值方法[J].国防科技大学学报,2004,26(3):34
-38.
XIU Bao x in,REN Shuang qiao,Z HA N G W eiming.
A n appro ach to image interpolatio n based o n the theor y
of fuzzy informat ion g ranulatio n[J].Journal of N atio n
al U niv ersity of D ef ense T echnolog y,2004,26(3):34
-38.
[120]刘仁金.基于商空间的纹理图像分割研究[D].合肥:安徽大学,2005.
L IU R enjin.Study o f textur e imag e seg mentation
based on the quotient space[D].Hefei:A nhui U niver
sity,2005.
[121]张丽娟,李舟军,陈火旺.粒度计算及其在数据挖掘中的应用[J].计算机科学,2005,32(12):178-180.
ZH A NG Lijuan,L I Zhoujun,CH EN H uo wang.
Gr anular comput ing and its applicat ions in data mining
[J].Computer Science,2005,32(12):178-180. [122]WEI J M.Rough set based appr oach to selection of no de[J].Inter national Jo urnal of Co mputational Cogni
t ion,2003,1(2):25-40.
[123]苗夺谦,王 珏.基于粗糙集的多变量决策树构造方法[J].软件学报,1997,8(6):425-431.
M IAO Duoqian,W AN G Jue.Ro ug h sets based ap
pro ach fo r multiv ariate decision tree construction[J].
Jour nal of Softw ar e,1997,8(6):425-431.
[124]JEL O N EK J.R ough set r eduction of attr ibutes and their doma ins fo r neur al netw orks[J].I nter J of Com
putatio nal Intellig ence,1995,11(2):339-347. [125]沈亚兰.基于粒度计算的数据挖掘方法的研究[D].沈阳:沈阳工业大学,2006.
SHEN Y alan.R esear ch on methods o f dat a mining
based on gr anula r comput ing[D].Shenyang:Sheny ang
U niver sity o f T echno log y,2006.
[126]张持健.商空间下模糊系统与模糊控制的问题求解
[D].合肥:安徽大学,2005.
ZH A NG Chijian.P roblem solving of fuzzy system&
fuzzy co ntr ol based o n t he theor y of quo tient space
[D].H eifei:A nhui U niv ersity,2005.
[127]张燕平.基于商空间的构造性数据控掘方法及应用
[D].合肥:安徽大学,2003.
ZH A NG Yanping.A structural metho d of data mining
based on quot ient space and its applicat ions[D].Heif
ei:A nhui U niversit y,2003.
[128]L IU Q,F EN G J,DEN G D Y.Desig n and implement for diag nosis sy st ems of hemo rheolog y on blo od v isco s
ity sy ndro me based on G rC[A].RSF DGr C2003[C].
Ber lin,2003.
[129]H U J,WA N G G Y,ZH AN G Q H,et a l.A ttr ibute
r eductio n based on gr anular computing[A].T he Fifth Inter national Conference o n Roug h Sets and Curr ent
T rends in Comput ing[C].[S.l.],2006.
[130]WEI L,M I AO D Q.A pplicat ion of g r anular co mpu t ing in know ledge r educt ion[A].F ir st Inter national
Co nfer ence RSK T2006[C].[S.l.],2006.
[131]王国胤,何 晓.一种不确定性条件下的自主式知识学习模型[J].软件学报,2003,14(6):1096-1102.
W A NG Guoy in,HE Xiao.A self learning mo del un
der uncerta in co ndition[J].Journal of Softw ar e,2003,
14(6):1096-1102.
[132]W A NG G Y.Doma in o riented data driven data mining based on r ough set[A].Pro c Int Fo rum o n T heo ry of
G rC fro m Roug h Set P erspective[C].[S.l.],2006.
作者简介:
王国胤,男,1970年生,教授,博士
生导师,博士,上海交通大学、西安交通
大学、西南交通大学、电子科技大学和西
安电子科技大学兼职教授,国际粗糙集
学会常务理事兼顾问委员会主席,IEEE
高级会员,中国人工智能学会常务理事
兼粗糙集与软计算专业委员会主任委
员,中国计算机学会人工智能与模式识别专业委员会常务理事,重庆计算机学会副理事长,重庆市人工智能学会副理事长,(T r ansactions o n R ough Sets)、(In ternatio nal Journal o f Co gnitive Info rmatics&N atural Intel ligence)、(计算机学报)等6种学术期刊的编委.王国胤教授组织召开了10个国际国内学术会议,并担任会议主席或共同主席,是10多个系列性国际学术会议的程序委员会委员,应邀在M SR AS2004、R SGrC2007、PReM I2007、IECT2007等国际会议,以及CR SSC2002、CAA I2005、CN NC2006等全国会议上作特邀报告.主持国家自然科学基金、国家863计划等20多项国家级、省部级科研项目.获重庆市自然科学二等奖、三等奖各1次,他领导的重庆邮电大学计算机科学与技术研究所2002年荣获首届!重庆市十大杰出青年群体?荣誉称号.在国内外主要学术刊物和学术会议上发表200多篇,其中被国际权威检索刊物SCI、EI等收录130多篇(次),论著被他人引用1400多次.出版学术专著2部.
E mail:w ang g y@https://www.doczj.com/doc/8814247929.html,.
cn.
张清华,男,1974年生,博士研究生,
主要研究方向为粒计算、模糊集理论、粗
糙集理论.
E mail:zhangqh@https://www.doczj.com/doc/8814247929.html,.
胡 军,男,1977年生,博士研究
生,主要研究方向为粒计算、粗糙集理
论、知识获取等.
E mail:hujun@https://www.doczj.com/doc/8814247929.html,.
#
26
#智 能 系 统 学 报 第2卷
1.什么是边缘计算？ 在IIoT的背景下，“边缘”是指靠近数据源的计算基础设施，例如工业机器（例如风力涡轮机，磁共振（MR）扫描仪，海底防喷器）），工业控制器如SCADA系统和时间序列数据库汇总来自各种设备和传感器的数据。这些设备通常远离云中可用的集中式计算。 边缘计算是在靠近物或数据源头的网络边缘侧，融合网络、计算、存储、应用核心能力的开放平台。边缘计算与云计算互相协同，共同助力各行各业的数字化转型。它就近提供智能互联服务，满足行业在数字化变革过程中对实时业务、业务智能、数据聚合与互操作、安全与隐私保护等方面的关键需求。 到目前为止，边缘计算的作用主要用于摄取，存储，过滤和发送数据到云系统。然而，我们正处于一个时间点，这些计算系统正在包装更多的计算，存储和分析功能，以消耗并对机器位置的数据采取行动。这种能力对于工业组织来说将是非常有价值的 - 这是不可或缺的。 2.这对工业带来的价值 行业权威人士已经计算出，数以千计的连接事物会从不同的来源产生大量的数据。根据国际电信联盟电信标准分局ITU-T的研究报告，到2020年，每个人每秒将产生的数据，IoT可穿戴设备的出货量将达到亿。IDC也发布了相关预测，到2018年，50%的物联网网络将面临网络带宽的限制，40%的数据需要在网络边缘侧分析、处理与储存，到2025年，这一数字将超过50%。管理咨询公司麦肯锡公司估计，到2025年，工业物联网（IIoT）将创造价值万亿的市场规模。工业物联网将思想和机器结合在一起，将人们与加速数字产业转型的机器数据相结合。 通过将大数据，高级分析和机器学习应用于运营，工业可以减少计划外停机时间，提高资产性能，降低维护成本，并为从机床数据中获取未开发价值的新业务模式开拓潜力。 过去几年来，工业组织已经开始将云计算融入业务，从大量数据中获取洞察力，帮助实现关键业务成果，包括减少意外停机，提高生产效率，降低能耗等。云计算仍然通过工业物联网来实现新的性能水平发挥关键作用，因为它需要大量的计算能力来有效地管理来自机器的庞大数据量。 但是随着更多的计算，存储和分析能力被捆绑到更靠近数据源的较小设备中，即工业机器 - 边缘计算将有助于边缘处理实现工业物联网的承诺。 虽然这个概念不是新的，但是有几个关键的驱动力使它成为今天更可行的现实：·计算和传感器的成本继续下滑， ·在较小尺寸的设备（如网关或传感器集线器）中执行的更多计算能力， ·来自机器和/或环境的日益增长的数据（例如天气或市场定价）， ·现代机器学习与分析。 这些因素有助于公司将大量数据转化为具有洞察力和智慧的行动。 对于工业组织来说，这种技术在以下用例中将变得至关重要： ·低/间歇连接（如远程位置） o将数据传输到云的带宽和相关的高成本 o低延迟，例如机器洞察和启动之间的闭环相互作用（即在机器上采取动作）
人工智能算法综述 人工智能算法大概包括五大搜索技术，包括一些早期的搜索技术或用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理，如遗传算法和模拟退火算法等。 1、盲目搜索 盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。包括图搜索策略，宽度优先搜索和深度优先搜素。 1、图搜索（GRAPH SERCH）策略是一种在图中寻找路径的方法。在有关图的表示方法中，节点对应于状态，而连线对应于操作符。 2、如果搜素是以接近其实节点的程度依次扩展节点的，那么这种搜素就叫做宽度优先搜素（breadth-first search 。 3、深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。 二、启发式搜索 盲目搜索的不足之处是效率低，耗费过多的时间和空间。启发信息是进行搜索技术所需要的一些有关具体问题的特性的信息。利用启发信息的搜索方法叫做启发式搜索方法。 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 3、博弈树搜索 诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的"二人零和、全信息、非偶然"博弈，其特征如下： (1 对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局。 (2 在对垒过程中，任何一方都了解当前的格局及过去的历史。
献给对P2P网络感兴趣的朋友们： Peer-to-Peer 计算综述 罗杰文 luojw@https://www.doczj.com/doc/8814247929.html, 中科院计算技术研究所 2005-4-25
1绪言 (3) 1.1研究的意义 (3) 1.2国内外P2P技术研究现状 (5) 1.3对研究内容有重大影响的几个方面 (12) 1.3.1度数和直径的折衷关系（TRADEOFF）对发现算法的影响 (13) 1.3.2 S MALL WORLD理论对P2P发现技术的影响 (14) 1.3.3语义查询和DHT的矛盾 (14) 1.4 P2P发现技术研究的成果与不足 (15) 2复杂P2P网络拓扑模型 (15) 2.1 I NTERNET拓扑模型 (15) 2.1.1随机网络与拓扑模型 (16) 2.1.2随机网络参数 (16) 2.1.3拓扑模型 (17) 2.2 S MALL W ORLD网络 (20) 3非结构化P2P搜索算法 (21) 3.1 B LIND SEARCH (21) 3.2 I NFORMED S EARCH M ETHODS (22) 3.2.1 C ACHE M ETHOD (22) 3.2.2 M OBILE A GENT BASED M ETHOD (23) 4主要P2P软件模型研究 (23) 4.1 N APSTER (23) 4.2 G NUTELLA (24) 4.3 K A Z AA (26)
1绪言 1.1研究的意义 最近几年，对等计算( Peer-to-Peer，简称P2P) 迅速成为计算机界关注的热门话题之一，财富杂志更将P2P列为影响Internet未来的四项科技之一。 根据被引用比较多的Clay Shirky的定义，P2P技术是在Internet现有资源组织和查找形式之外研究新的资源组织与发现方法，P2P技术最大的意义在于不依赖中心结点而依靠网络边缘结点自组织对等协作的资源发现（Discovery，Lookup）形式。 顾名思义，对等网络打破了传统的Client/Server模式，对等网络中的每个结点的地位都是对等的。每个结点既充当服务器，为其他结点提供服务，同时也享用其他结点提供的服务。P2P技术的特点体现在以下几个方面。 非中心化（Decentralization）：网络中的资源和服务分散在所有结点上，信息的传输和服务的实现都直接在结点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。 可扩展性：在P2P网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。整个体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 健壮性：P2P架构天生具有耐攻击、高容错的优点。由于服务是分散在各个结点之间进行的，部分结点或网络遭到破坏对其它部分的影响很小。P2P网络一般在部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。P2P网络通常都是以自组织的方式建立起来的，并允许结点自由地加入和离开。P2P网络还能够根据网络带宽、结点数、负载等变化不断地做自适应式的调整。 高性能/价格比：性能优势是P2P被广泛关注的一个重要原因。随着硬件技术的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增长。采用P2P架构可以有效地利用互联网中散布的大量普通结点，将计算任务或存储资料分布到所有结点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更低的成本提供更高的计算和存储能力。
云计算综述报告 姓名： 学号： 专业： 班级： 指导教师：
摘要 云计算(Cloud computing)已经成为了IT界的热门技术，甚至被视为将根本改变生活方式和商业模式的革命技术。借助云计算，网络服务提供者可以在瞬息之间，处理数以千万计甚至亿计的信息，实现和超级计算机同样的效能。云计算可以被视为网络计算和虚拟化的融合：即利用网格分布式计算处理能力，将IT资源构筑成一个资源池，再加上成熟的服务器虚拟化、存储虚拟化技术，是用户可以实时的监控和调配资源。 本文主要首先介绍云计算的概念和国内外的发展状况，然后介绍云计算的原理、核心技术，现状，最后是关于云计算的挑战及其展望。 关键词：云计算虚拟化云存储分布式计算 1 云计算的概念 计算机的应用模式大体经历了以大型机为主体的集中式架构、以PC机为主体的客户/服务器分布式计算架构、以虚拟化技术为核心面向服务的体系结构（SOA）及基于Web2.0应用特征的新型架构。计算机的应用模式、技术架构及实现特征的演变史云计算发展的时代背景。 云计算由英文Cloud computing直接翻译而来。这样通俗的得技术术语，却难以找到业界统一的定义。云概念这个术语的诞生和使用纯属偶然，在互联网技术发展的早期阶段，技术人员都习惯性的将互联网画成一朵“云”来代表，因为这样一来，人们就可以简化网络内部的技术细节和复杂机制来方便讨论新技术。 云计算的定义众多，目前广为认同的一点是，云计算是分布式处理、并行处理和网格计算的发展，或者说是这些计算机科学概念的商业实现。云计算是一种资源交付和使用模式，指通过网络获得应用所需的资源（硬件、软件、平台）。云计算将计算从客户终端集中到“云端”，作为应用通过互联网提供给用户，计算通过分布式计算等技术由多台计算机共同完成。用户只关心应用的功能，而不关心应用的实现方式，应用的实现和维护由其提供商完成，用户根据自己的需要选择相应的应用。云计算不是一个工具、平台或者架构，而是一种计算的方式。
人工智能的形成及其发展现状分析 冯海东 （长江大学管理学院荆州434023） 摘要：人工智能的历史并不久远，故将从人工智能的出现、形成、发展现 状及前景几个方面对其进行分析，总结其发展过程中所出现的问题，以及发展现状中的不足之处，分析其今后的发展方向。 关键词：人工智能，发展过程，现状分析，前景。 一．引言 人工智能最早是在1936年被英国的科学家图灵提出，并不为多数人所认知。 当时，他编写了一个下象棋的程序，这就是最早期的人工智能的应用。也有著名的“图灵测试”，这也是最初判断是否是人工智能的方案,因此，图灵被尊称为“人工智能之父”。人工智能从产生到发展经历了一个起伏跌宕的过程，直到目前为止，人工智能的应用技术也不是很成熟，而且存在相当的缺陷。 通过搜集的资料，将详细的介绍人工智能这个领域的具体情况，剖析其面临的挑战和未来的前景。 二．人工智能的发展历程 1. 1956年前的孕育期 (1) 从公元前伟大的哲学家亚里斯多德(Aristotle)到16世纪英国哲学家培根(F. Bacon)，他们提出的形式逻辑的三段论、归纳法以及“知识就是力量”的警句，都对人类思维过程的研究产生了重要影响。 （2）17世纪德国数学家莱布尼兹(G..Leibniz)提出了万能符号和推理计算思想，为数理逻辑的产生和发展奠定了基础，播下了现代机器思维设计思想的种子。而19世纪的英国逻辑学家布尔（G. Boole）创立的布尔代数，实现了用符号语言描述人类思维活动的基本推理法则。 （3） 20世纪30年代迅速发展的数学逻辑和关于计算的新思想，使人们在计算机出现之前，就建立了计算与智能关系的概念。被誉为人工智能之父的英国天才的数学家图灵（A. Tur-ing）在1936年提出了一种理想计算机的数学模型，即图灵机之后,1946年就由美国数学家莫克利（J. Mauchly）和埃柯特（J. Echert）研制出了世界上第一台数字计算机，它为人工智能的研究奠定了不可缺少的物质基础。1950年图灵又发表了“计算机与智能”的论文，提出了著名的“图灵测试”，形象地指出什么是人工智能以及机器具有智能的标准，对人工智能的发展产生了极其深远的影响。 （4） 1934年美国神经生理学家麦克洛奇(W. McCulloch) 和匹兹(W. Pitts )建立了第一个神经网络模型，为以后的人工神经网络研究奠定了基础。 2. 1956年至1969年的诞生发育期 (1)1956年夏季，麻省理工学院（MIT)的麦卡锡（J．McCarthy）、明斯基（M. Minshy）、塞尔夫里奇（O. Selfridge)与索罗门夫(R. Solomonff)、 IBM的洛
1.什么是边缘计算？ 在IIoT 的背景下，“边缘”是指靠近数据源的计算基础设施，例如工业机器（例如风力涡轮机，磁共振（ MR ）扫描仪，海底防喷器）），工业控制器如 SCADA 系统和时间序列数据库汇总来自各种设备和传感器的数据。这些设备通常远离云中可用的集 中式计算。 边缘计算是在靠近物或数据源头的网络边缘侧，融合网络、计算、存储、应用核 心能力的开放平台。边缘计算与云计算互相协同，共同助力各行各业的数字化转型。 它就近提供智能互联服务，满足行业在数字化变革过程中对实时业务、业务智能、数 据聚合与互操作、安全与隐私保护等方面的关键需求。 到目前为止，边缘计算的作用主要用于摄取，存储，过滤和发送数据到云系统。 然而，我们正处于一个时间点，这些计算系统正在包装更多的计算，存储和分析功能， 以消耗并对机器位置的数据采取行动。这种能力对于工业组织来说将是非常有价值的 - 这是不可或缺的。 2.这对工业带来的价值 行业权威人士已经计算出，数以千计的连接事物会从不同的来源产生大量的数 据。根据国际电信联盟电信标准分局 ITU-T的研究报告，到 2020 年，每个人每秒将产生1.7MB 的数据， IoT 可穿戴设备的出货量将达到 2.37 亿。 IDC 也发布了相关预测， 到2018 年，50%的物联网网络将面临网络带宽的限制，40%的数据需要在网络边缘侧分析、处理与储存，到2025 年，这一数字将超过50%。管理咨询公司麦肯锡公司估计，到2025 年，工业物联网（IIoT ）将创造价值7.5 万亿的市场规模。工业物联网将思想和机器结合在一起，将人们与加速数字产业转型的机器数据相结合。 通过将大数据，高级分析和机器学习应用于运营，工业可以减少计划外停机时间， 提高资产性能，降低维护成本，并为从机床数据中获取未开发价值的新业务模式开拓 潜力。 过去几年来，工业组织已经开始将云计算融入业务，从大量数据中获取洞察力， 帮助实现关键业务成果，包括减少意外停机，提高生产效率，降低能耗等。云计算仍 然通过工业物联网来实现新的性能水平发挥关键作用，因为它需要大量的计算能力来 有效地管理来自机器的庞大数据量。 但是随着更多的计算，存储和分析能力被捆绑到更靠近数据源的较小设备中，即 工业机器 - 边缘计算将有助于边缘处理实现工业物联网的承诺。 虽然这个概念不是新的，但是有几个关键的驱动力使它成为今天更可行的现实： 计算和传感器的成本继续下滑， 在较小尺寸的设备（如网关或传感器集线器）中执行的更多计算能力，
插值法综述 一、插值法及其国内外研究进展 1.插值法简介 插值法是一种古老的数学方法，它来自生产实践，早在一千多年前，我国科学家在研究历法上就应用了线性插值与二次插值，但它的基本理论却是在微积分产生之后才逐渐完善的，其应用也日益增多，特别是在计算机广泛使用之后，由于航空、机械加工、自动控制等实际问题的需要，使插值法在实践和理论上都显得更为重要，并得到了空前的发展。 2.国内外研究进展 ● 插值法在预测地基沉降的应用 ● 插值法在不排水不可压缩条件下两相介质的两重网格算法的应用 ● 拉格朗日插值法在地震动的模拟研究中的应用 ● 插值法在结构抗震可靠性分析中的应用 ● 插值法在应力集中应变分布规律实验分析中的应用 3.代表性文献 ● 不等时距GM(1%2c1)模型预测地基沉降研究 秦亚琼 武汉理工大学学报 (交通科学与工程版) 2008.2 ● 不排水不可压缩条件下两相介质的两重网格算法 牛志伟 岩土力学 2008.3 ● 基于拉格朗日插值法的地震动的模拟 白 可 山西建筑 2010.10 ● 响应表面法用于结构抗震可靠性分析 张文元 世界地震工程 1997 ● 小议应力集中应变分布规律的实验方法 查珑珑 淮海工学院学报 （自然科学版）2004.6 二、插值法的原理 【原理】 设有n+1个互不相同的节点（i x ，i y ） （i=0，1，2，...n ）则存在唯一的多项式： 2012()...(1)n n n L x a a x a x a x =++++
使得()(0,1,2,...)(2)n j j L x y j n == 证明：构造方程组 20102000201121112012......(3)...n n n n n n n n n n a a x a x a x y a a x a x a x y a a x a x a x y ?++++=?++++=??? ?++++=? 令：0 01 1111n n n n n x x x x A x x ??? ?? ?=???????? 01 n a a X a ??????=??????01n y y Y y ??????=?? ???? 方程组的矩阵形式如下：(4)AX Y = 由于1 10 ()0n n i j i j A x x -===-≠∏∏所以方程组（4）有唯一解。 从而2012()...n n n L x a a x a x a x =++++唯一存在。 三、常用插值法 3.1 Lagrange 插值法 3.1.1 Lagrange 插值法的一般提法 给定))(,(i i x f x ),,1,0(n i =，多项式 ∑∏ ∑=≠= =???? ? ??--==n i n i j j j i j i n i i i n x x x x y x l y x 000)()(? 称为)(x f 关于n x x x ,,,10 的n 次Lagrange 插值多项式。 3.1.2 Lagrange 插值多项式的构造 已知n+1个节点(,)(0,1, ,j j x y j n =其中j x 互不相同，不妨设
第３２卷Ｖ０１．３２第１４期 脑ｊ４ 计算机工程 ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ ２００６年７月 Ｊｕｌｙ２００６ ?安全技术?文章■号ｔｌ∞０＿—３４２８（２０嘶）１４．＿０ｌｌｌ—０３文献标识码ｌＡ中圈分类号ｔＴＰ３９１可信计算系统及其研究现状 秦中元，胡爱群 （东南大学无线电工程系，南京２１００９６） 搞要：可信计算是信息安全研究的一个新阶段，它通过在计算设备硬件平台上引入安全芯片架构，通过其提供的安全特性来提高整个系统的安全性。该文简要介绍了可信计算的起源和发展，重点分析了可信计算系统的体系结构和可信平台模块、可信根等关键技术，并对目前的研究现状作了总结。 关健诃：可信计算系统；可信平台模块；可信根 ＴｒｕｓｔｅｄＣｏｍｐｕｔｉｎｇＳｙｓｔｅｍａｎｄＩｔｓＣｕｒｒｅｎｔＲｅｓｅａｒｃｈ ＱＩＮＺｈｏｎｇｙｕａｎ，ＨＵＡｉｑｕｎ （ＤｅｐａｒｔｍｅｎｔｏｆＲａｄｉｏＥｎｇｉｎｅｅｒｉｎｇ，ＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１００９６） ［ＡｂｓｔｒａｃｔＩＴｒｕｓｔｅｄｃｏｍｐｕｔｉｎｇｉｓｔｈｅｎｅｗｓｔａｇｅｏｆｉｎｆｏｒｍａｔｉｏｎｓｅｃｕｒｉｔｙ．Ｉｔｂｒｉｎｇｓｓｅｃｕｒｉｔｙｃｈｉｐａｒｃｈｉｔｅｃｔｕｒｅｉｎｔｈｅｃｏｍｐｕｔｉｎｇｈａｒｄｗａｒｅｐｌａｔｆｏｒｍ，ａｎｄｔｈｅｗｈｏｌｅｓｙｓｔｅｍ’Ｓｓｅｃｕｒｉｔｙｉｓｇｒｅａｔｌｙｉｍｐｒｏｖｅｄｃｏｒｒｅｓｐｏｎｄｉｎｇｌｙ．Ｔｈｅｏｒｉｇｉｎａｎｄｄｅｖｅｌｏｐｍｅｎｔｏｆｔｒｕｓｔｅｄｃｏｍｐｕｔｉｎｇａｒｅｉｎｔｒｏｄｕｃｅｄ，ｅｓｐｅｃｉａｌｌｙｉｔｓａｒｃｈｉｔｅｃｔｕｒｅａｎｄｔｈｅｋｅｙｃｏｍｐｏｎｅｎｔｓｓｕｃｈａｓｔｈｅｔｒｕｓｔｅｄｐｌａｔｆｏｒｍｍｏｄｕｌｅ，ｒｏｏｔｏｆｔｒｕｓｔ，ｅｔｃ．Ｔｈｅｃｕｒｒｅｎｔｒｅｓｅａｒｃｈｈａｓａｌｓｏｂｅｅｎｃｏｎｃｌｕｄｅｄ． ［ＫｅｙｗｏｒｄｓｌＴｒｕｓｔｅｄｃｏｍｐｕｔｉｎｇｓｙｓｔｅｍ；Ｔｒｕｓｔｅｄｐｌａｔｆｏｒｍｍｏｄｕｌｅ；Ｒｏｏｔｏｆｔｒｕｓｔ １可信计算系统的起源和发展 计算机和通信技术的迅猛发展使得信息安全的地位日益显得重要。目前的信息安全技术主要依靠强健的密码算法与密钥相结合来确保信息的机密性、完整性，以及实体身份的惟一性和操作与过程的不可否认性。但是各种密码算法都并非绝对安全，而且很多用户并不清楚这些密码保护机制如何设置，更重要的是，这些技术虽然在一定程度上可以阻挡黑客和病毒的攻击，但是却无法防范内部人员对关键信息的泄露、窃取、篡改和破坏。 沈昌祥院士指出常规的安全手段只能是以共享信息资源为中心在外围对非法用户和越权访问进行封堵，以达到防止外部攻击的目的；对共享源的访问者源端不加控制；操作系统的不安全导致应用系统的各种漏洞层出不穷；恶意用户的手段越来越高明，防护者只能将防火墙越砌越高、入侵检测越做越复杂、恶意代码库越做越大。从而导致误报率增多、安全投入不断增加、维护与管理更加复杂和难以实施以及信息系统的使用效率大大降低。于是近年来信息安全学界将底层的计算技术与密码技术紧密结合，推动信息安全技术研究进入可信计算技术阶段。 １９９９年１０月，为了提高计算机的安全防护能力，Ｉｎｔｅｌ、微软、ＩＢＭ、ＨＰ和Ｃｏｍｐａｑ共同发起成立了可信计算平台联盟（ＴｒｕｓｔｅｄＣｏｍｐｕｔｉｎｇＰｌａｔｆｏｒｍＡｌｌｉａｎｃｅ，ＴＣＰＡ），并提出了“可信计算”（ｔｒｕｓｔｅｄｃｏｍｐｕｔｉｎｇ）的概念，其主要思路是增强现有ＰＣ终端体系结构的安全性，并推广为工业规范，利用可信计算技术来构建通用的终端硬件平台。２００３年４月，ＴＣＰＡ重新改组，更名为可信计算集团（ＴｒｕｓｔｅｄＣｏｍｐｕｔｉｎｇＧｒｏｕｐ，ＴＣＧ），并继续使用ＴＣＰＡ制定的“ＴｒｕｓｔｅｄＣｏｍｐｕｔｉｎｇＰｌａｔｆｏｒｍＳｐｅｃｉｆｉｃａｔｉｏｎｓ”。２００３年ｌＯ月，ＴＣＧ推出了ＴＣＧ１．２技术规范。到２００４年８月ＴＣＧ组织已经拥有７８个成员，遍布全球各大洲。２可信计算系统的体系结构 ２．１可信计算的概念 “可信计算”的概念由ＴＣＰＡ提出，但并没有一个明确的定义，而且联盟内部的各大厂商对“可信计算”的理解也不尽相同。其主要思路是在计算设备硬件平台上引入安全芯片架构，通过其提供的安全特性来提高系统的安全性。可信计算终端基于可信赖平台模块（ＴＰＭ），以密码技术为支持，安全操作系统为核心。计算设备可以是个人计算机，也可以是ＰＤＡ、手机等具有计算能力的嵌入式设备。 “可信计算”可以从几个方面来理解：（１）用户的身份认证，这是对使用者的信任；（２）平台软硬件配置的正确性，这体现了使用者对平台运行环境的信任；（３）应用程序的完整性和合法性，体现了应用程序运行的可信；（４）平台之间的可验证性，指网络环境下平台之间的相互信任。 圈１含有ＴＰＭ的ＰＣ平台 ２．２可信平台模块 可信平台模块（ＴｒｕｓｔｅｄＰｌａｔｆｏｒｏａＭｏｄｕｌｅ，ＴＰＭ）是可信计 作者倚介：秦中元（１９７４—），男，博士、讲师，主研方向：无线通信网络及其安全；胡爱群，教授、博导 收稿日期：２００５?０９－２３Ｅ?ｍａｉｌ：ｚｙｑｉｎ＠ｓｅｕ．ｅｄｕ．ｃｎ 万方数据
第一性原理计算的理论方法 随着科技的发展，计算机性能也得到了飞速的提高，人们对物理理论的认识也更加的深入，利用计算机模拟对材料进行设计已经成为现代科学研究不可缺少的研究手段。这主要是因为在许多情况下计算机模拟比实验更快、更省，还得意于计算机模拟可以预测一些当前实验水平难以达到的情况。然而在众多的模拟方法中，第一性原理计算凭借其独特的精度和无需经验参数而得到众多研究人员的青睐，成为计算材料学的重要基础和核心计算。本章将介绍第一性原理计算的理论基础，研究方法和ABINIT软件包。 1.1 第一性原理 第一性原理计算( 简称从头计算，the abinitio calculation) ，指 从所要研究的材料的原子组分出发，运用量子力学及其它物理规律，通过自洽计算来确定指定材料的几何结构、电子结构、热力学性质和光学性质等材料物性的方法。基本思想是将多原子构成的实际体系理解成为只有电子和原子核组成的多粒子系统，运用量子力学等最基本的物理原理最大限度的对问题进行”非经验”处理。【1】第一性原理计算就只需要用到五个最基本的物理常量即( m o.e.h.c.k b ) 和元素周期表中各组分元素的电子结构，就可以合理地预测材料的许多物理性质。用第一性原理计算的晶胞大小和实验值相比误差只有几个百分点，其他性质也和实验结果比较吻合，体现了该理论的正确性。
第一性原理计算按照如下三个基本假设把问题简化： 1．利用Born-Oppenheimer 绝热近似把包含原子核和电子的多粒子问题转化为多电子问题。 2．利用密度泛函理论的单电子近似把多电子薛定谔方程简化为比较容易求解的单电子方程。 3．利用自洽迭代法求解单电子方程得到系统基态和其他性质。以下我将简单介绍这些第一性原理计算的理论基础和实现方法：绝热近似、密度泛函理论、局域密度近似(LDA)和广义梯度近似(GGA)、平面波及赝势方法、密度泛函的微扰理论、热力学计算方法和第一性原理计算程序包ABINIT。 1．2量子力学与Born-Oppenheimer 近似固体是由原子核和核外的电子组成的，在原子核与电子之间，电子与电子之间，原子核与原子核之间都存在着相互作用。从物理学的角度来看，固体是一个多体的量子力学体系【2】，相应的体系哈密顿量可以写成如下形式： H (r,R) E H(r ,R) (1-1) 其中r,R 分别代表所有电子坐标的集合、所有原子核坐标的集合。在不计外场作用下，体系的哈密顿量日包括体系所有粒子( 原子核和电子) 的动能和粒子之间的相互作用能，即 H H e H N H e N (1-2) 其中，以是电子部分的哈密顿量，形式为： 22 1 e2 H e(r) r2i 1 e(1-3)
第8卷第5期2019$9月 Vol.8No.5网络新媒体技术Sep.2019 ?经典评述- 移动边缘计算技术概述! 洪德坚王雷 (中国科学技术大学信息学院合肥230026) 摘要：移动边缘计算技术MEC是未来5G技术提高服务平台应用能力的重要技术手段#首先介绍了MEC发展历程、优势及基本架构，然后对MEC的三大关键技术进行总结分析,并描述了MEC的三大类应用场景，最后探讨了MEC的发展趋势# 关键词：移动边缘计算，5G未来网，移动互联网应用 Overview of Mobile Edge Computing Technology HONG Dejian,WANG Lal (Universty oS Sciencc and Technology oS China,Hefei,230026,China) AbstracC:Mobile edge ccmputing technology----MEC is an important technical means for improving the application capability oS sere-ice platforms in the future5G technology.This paper first introduccs the development histo-,advantages and basic structure oS MEC, then summarizes and analyzes the three key technologies oS MEC,describes the three major application sccnarios oS MEC,and finally discusses the development trend oS MEC. Keywordt:Mobile edge ccmputing,5G future network,mobile internet application 0引言 随着互联网、移动互联网的飞速发展,用户对网络对流量的需求越来越大，要求也越来越高,为此网络面临的压力越来越大，为更快处理网络中用户需求，移动边缘计算技术(Mobile Edga Computing,MEC)应运而生，目前,MEC已成业界热点话题# MEC由国际标准组织ETSID(European Telecammunications Standards Institute)(欧洲电信标准协会)提出，是基于5G演进架构、将基站与互联网业务深度融合的技术。经过几年的推进，目前关于MEC业界已经形成共识：MEC将是建设5G网络边缘云的普遍模式，或将成为5G业务发展的“试金石”&1]o 本文将对MEC进行相关探讨。主要包括4部分内容，第1部分MEC研究现状和基本架构，第2部分是对MEC主要3大关键技术进行研究，第3部分内容是MEC典型的应用场景研究，第4部分内容是MEC未来发展和展望。 1MEC发展历程、优势及基本架构 移动边缘计算MEC概念最初于2013年出现。HM与Nokia Siemens网络当时共同推出了一款计算平台，可在无线基站内部运行应用程序，向移动用户提供业务。欧洲电信标准协会ETSI于2014年成立移动边 本文于2018-08-01收到，2018-08-16收到修改稿。 *基金项目：工信部"新一代宽带无线移动通信网”重大专项子课题(2017ZX03001019-004)
可信计算技术综述 08网络工程2班龙振业0823010032 摘要：可信计算是信息安全研究的一个新阶段，它通过在计算设备硬件平台上引入安全芯片架构，通过其提供的安全特性来提高整个系统的安全性。本文简要介绍了可信计算的起源和发展，阐述了可信性的起源与内涵。着重介绍了各种高可信保障技术，并对目前的应用现状做了总结。最后，探讨了可信计算的发展趋势。 关键字：可信性；可信计算；可信计算系统；可信计算应用 1.可信计算系统的起源和发展 计算机和通信技术的迅猛发展使得信息安全的地位日益显得重要。目前的信息安全技术主要依靠强健的密码算法与密钥相结合来确保信息的机密性、完整性，以及实体身份的惟一性和操作与过程的不可否认性。但是各种密码算法都并非绝对安全，而且很多用户并不清楚这些密码保护机制如何设置，更重要的是，这些技术虽然在一定程度上可以阻挡黑客和病毒的攻击，但是却无法防范内部人员对关键信息的泄露、窃取、篡改和破坏。 常规的安全手段只能是以共享信息资源为中心在外围对非法用户和越权访问进行封堵，以达到防止外部攻击的目的；对共享源的访问者源端不加控制；操作系统的不安全导致应用系统的各种漏洞层出不穷；恶意用户的手段越来越高明，防护者只能将防火墙越砌越高、入侵检测越做越复杂、恶意代码库越做越大。从而导致误报率增多、安全投入不断增加、维护与管理更加复杂和难以实施以及信息系统的使用效率大大降低。于是近年来信息安全学界将底层的计算技术与密码技术紧密结合，推动信息安全技术研究进入可信计算技术阶段。 1999年10月，为了提高计算机的安全防护能力，Intel、微软、IBM、HP和Compaq共同发起成立了可信计算平台联盟(Trusted Computing Platform Alliance，TCPA)，并提出了“可信计算”(t rusted computing)的概念，其主要思路是增强现有PC终端体系结构的安全性，并推广为工业规范，利用可信计算技术来构建通用的终端硬件平台。2003年4月，TCPA重新改组，更名为可信计算集团(Trusted Computing Group，TCG)，并继续使用 TCPA 制定的“Trusted Computing PlatformSpecifications”。2003年10月，TCG推出了TCG1.2技术规范。到2004年8月TCG组织已经拥有78个成员，遍布全球各大洲。 2. 可信计算的概念 “可信计算”的概念由 TCPA 提出，但并没有一个明确的定义，而且联盟内部的各大厂商对“可信计算”的理解也不尽相同。其主要思路是在计算设备硬件平台上引入安全芯片架构，通过其提供的安全特性来提高系统的安全性。可信计算终端基于可信赖平台模块(TPM)，以密码技术为支持，安全操作系统为核心。计算设备可以是个人计算机，也可以是 PDA、手机等具有计算能力的嵌入式设备。 “可信计算”可以从几个方面来理解：(1)用户的身份认证，这是对使用者的信任；(2)平台软硬件配置的正确性，这体现了使用者对平台运行环境的信任；(3)应用程序的完整性和合法性，体现了应用程序运行的可信；(4)平台之间的可验证性，指网络环境下平台之间的相互信任。
摘要：随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛，本文介绍了当前存在的一些智能计算方法，阐述了其工作原理和特点，同时对智能计算方法的发展进行了展望。关键词：人工神经网络遗传算法模拟退火算法群集智能蚁群算法粒子群算1什么是智能算法智能计算也有人称之为“软计算”，是们受自然（生物界）规律的启迪，根据其原理，模仿求解问题的算法。从自然界得到启迪，模仿其结构进行发明创造，这就是仿生学。这是我们向自然界学习的一个方面。另一方面，我们还可以利用仿生原理进行设计(包括设计算法)，这就是智能计算的思想。这方面的内容很多，如人工神经网络技术、遗传算法、模拟退火算法、模拟退火技术和群集智能技术等。 2人工神经网络算法“人工神经网络”(ARTIFICIALNEURALNETWORK，简称ANN)是在对人脑组织结构和运行机制的认识理解基础之上模拟其结构和智能行为的一种工程系统。早在本世纪40年代初期，心理学家McCulloch、数学家Pitts就提出了人工神经网络的第一个数学模型，从此开创了神经科学理论的研究时代。其后，FRosenblatt、Widrow和J.J.Hopfield等学者又先后提出了感知模型，使得人工神经网络技术得以蓬勃发展。神经系统的基本构造是神经元(神经细胞)，它是处理人体内各部分之间相互信息传递的基本单元。据神经生物学家研究的结果表明，人的一个大脑一般有1010～1011个神经元。每个神经元都由一个细胞体，一个连接其他神经元的轴突和一些向外伸出的其它较短分支——树突组成。轴突的功能是将本神经元的输出信号(兴奋)传递给别的神经元。其末端的许多神经末梢使得兴奋可以同时传送给多个神经元。树突的功能是接受来自其它神经元的兴奋。神经元细胞体将接受到的所有信号进行简单处理(如：加权求和，即对所有的输入信号都加以考虑且对每个信号的重视程度——体现在权值上——有所不同)后由轴突输出。神经元的树突与另外的神经元的神经末梢相连的部分称为突触。 2.1人工神经网络的特点人工神经网络是由大量的神经元广泛互连而成的系统，它的这一结构特点决定着人工神经网络具有高速信息处理的能力。人脑的每个神经元大约有103～104个树突及相应的突触，一个人的大脑总计约形成1014～1015个突触。用神经网络的术语来说，即是人脑具有1014～1015个互相连接的存储潜力。虽然每个神经元的运算功能十分简单，且信号传输速率也较低(大约100次/秒)，但由于各神经元之间的极度并行互连功能，最终使得一个普通人的大脑在约1秒内就能完成现行计算机至少需要数10亿次处理步骤才能完成的任务。人工神经网络的知识存储容量很大。在神经网络中，知识与信息的存储表现为神经元之间分布式的物理联系。它分散地表示和存储于整个网络内的各神经元及其连线上。每个神经元及其连线只表示一部分信息，而不是一个完整具体概念。只有通过各神经元的分布式综合效果才能表达出特定的概念和知识。由于人工神经网络中神经元个数众多以及整个网络存储信息容量的巨大，使得它具有很强的不确定性信息处理能力。即使输入信息不完全、不准确或模糊不清，神经网络仍然能够联想思维存在于记忆中的事物的完整图象。只要输入的模式接近于训练样本，系统就能给出正确的推理结论。 [!--empirenews.page--]正是因为人工神经网络的结构特点和其信息存储的分布式特点，使得它相对于其它的判断识别系统，如：专家系统等，具有另一个显著的优点：健壮性。生物神经网络不会因为个别神经元的损失而失去对原有模式的记忆。最有力的证明是，当一个人的大脑因意外事故受轻微损伤之后，并不会失去原有事物的全部记忆。人工神经网络也有类似的情况。因某些原因，无论是网络的硬件实现还是软件实现中的某个或某些神经元失效，整个网络仍然能继续工作。人工神经网络是一种非线性的处理单元。只有当神经元对所有的输入信号的综合处理结果超过某一门限值后才输出一个信号。因此神经网络是一种具有高度非线性的超大规模连续时间动力学系统。它突破了传统的以线性处理为基础的数字电子计算机的局限，标志着人们智能信息处理能力和模拟人脑智能行为能力的一大飞跃。 2.2几种典型神经网络简介 2.2.1多层感知网络(误差逆传播神经网络) 在1986年以Rumelhart和McCelland为首的科学家出版的《ParallelDistributedProcessing》一书中，完整地提出了误差逆传播学习算法，并被广泛
边缘云计算技术及标准化白皮书（2018） 编写单位：阿里云计算有限公司 中国电子技术标准化研究院 等 2018年12月12日联合发布
内容摘要 随着5G、物联网时代的到来以及云计算应用的逐渐增加，传统的云计算技术已经无法满足终端侧“大连接，低时延，大带宽”的需求。随着边缘计算技术的出现，云计算将必然发展到下一个技术阶段，将云计算的能力拓展至距离终端最近的边缘侧，并通过云边端的统一管控实现云计算服务的下沉，提供端到端的云服务，由此产生了边缘云计算的概念。为了积极引导边缘云计算技术和应用发展，以及边缘云计算相关标准的制定，我们编写本白皮书，其主要内容包括： 一、定义边缘云计算的概念。首先梳理了目前边缘计算的概念；其次对边缘云计算进行了定义和详细的描述；然后阐述了对边缘计算与边缘云计算之间的关系。 二、边缘云计算的典型应用场景。通过列举边缘云计算的典型应用场景，分析了边缘云计算技术在各个应用场景中关键成功因素。 三、边缘云计算的技术特点。边缘云计算具备6大特点，包括低延时、自组织、可定义、可调度、高安全和标准开放。 四、边缘云计算标准化需求以及标准化建议。通过对边缘云技术的分析，给出相应的标准化建议，包括5大类标准：基础标准、技术标准、管理标准、安全标准和行业及应用标准。
编写单位（排名不分先后） 阿里云计算有限公司 中国电子技术标准化研究院（工业和信息化部电子工业标准化研究院） 中国联合网络通信有限公司研究院 中移（苏州）软件技术有限公司 广州虎牙信息科技有限公司 参编人员 白常明朱松张大江陈志峰杨丽蕴王泽胜陈行 高莹姜倩刘晨杨鹏赵越鹏赵娇娇张瑞增 徐雷毋涛侯乐赵怡辛盛刘亚丹杨智林 于新林周升曹维国董陈强李静远王广芳曾林青 张毅萍熊鹰王文娟高俊富王政惠何云飞朱照远 杨敬宇 版权声明 本白皮书版权属于中国电子技术标准化研究院和阿里云计算有限公司，并受法律保护。转载、摘编或利用其它方式使用本白皮书文字或者观点的，应注明“来源：边缘云计算技术及标准化白皮书（2018）”。违反上述声明者，将追究其相关法律责任。
可信计算文献综述 学号：YJX1004023 姓名：平佳伟 一、引言 目前生活中，电脑和网络无处不在，一方面便利了我们的生活，但是随之而来的各种隐患也已经严重威胁到信息安全。 黑客与反黑客，间谍与反间谍是信息安全中永恒的话题。目前各种网络攻击越来越趋于隐蔽化, 攻击手法趋于复杂化, 并且新的攻击手段不断更新, 传统网络防护技术尽管也在不断发展, 但已显得力不从心。 在最初的信息安全建设中, 人们首先想到的是防止外部攻击以及本地网络 安全边界问题, 因而重点采用访问控制、入侵检测、网络隔离和病毒防范等方法来解决信息安全问题。之后认识到,终端是安全保障比较脆弱的地方, 也是安全解决方案所容易忽视的地方。 以被动防御为主导思想的传统安全技术已经无法抵御现今多种多样的攻击 入侵, 仅仅靠传统技术进行防、堵、卡解决不了问题, 更不能有效解决由隐患终端内部引起的安全威胁, 因此提出了可信计算的概念。 可信计算的思想是从内部入手, 从根源上防止各种安全隐患问题的发生。本文通过对多篇国内国外的论文的阅读，介绍国内外当前发展状况，综合描述了可信计算的相关概念，发展趋势已经与广阔应用前景。 二、可信计算的发展历史 1999年，由Intel、惠普、康柏、微软、IBM等业界大公司牵头，成立了可信计算平台联盟(TCPA)。并提出了“可信计算”(trusted computing)的概念，其主要思路是增强现有PC终端体系结构的安全性，并推广为工业规范，利用可信计算技术来构建通用的终端硬件平台[1]。 2003年4月TCPA改组为可信计算组织(Trusted Computing Group，TCG)，成员也扩大为200多个，遍布全球各大洲。其目的是在计算和通信系统中广泛使用
龙源期刊网 https://www.doczj.com/doc/8814247929.html, 粒计算研究现状及展望 作者：谢刚刘静 来源：《软件》2011年第03期 摘要：在信息处理中，粒计算是一种新的概念和计算范式,其本质是透过合适粒度的层次 来对问题进行求解,并且在此过程中去除繁冗，降低实现的复杂度。本文主要对粒计算提出的 背景、概念、研究现状及发展趋势进行论述，同时也给出了作者自己的评论，最后探讨了粒计算的进一步发展方向。 关键词：粒计算; 粗糙集; 模糊集; 商空间 中图分类号：TP18, TP206文献标识码Adoi: 10.3969/j.issn.1003-6970.2011.03.002 A Review of the Present Studying State and Prospect of Granular Computing XIE Gang, LIU Jing (College of Information Engineering, Taiyuan University of Technology, Taiyuan 030024, China) 【Abstract 】 Granular computing (GrC) is an emerging conceptual and computing paradigm of information processing, which it sought essentially problems of a better and approximate solution to reduce the complexity of problem solving by the right choice of granularity. In this paper, the proposed background, the present studying state and its developing direction of granular computing are summarized. 【Key words】granular computing; rough set;fuzzy set; quotient space 0引言 “概念必须有明确的边界。没有明确边界的概念，将对应于一个在周围没有明确界线的区域。”这是谓词逻辑的创始人Frege曾经说过的话，在此基础上他提出了概念的“含糊性”和“边界”问题[1]。由此1965年L.A.Zadeh创立了模糊集理论，突破了经典集合简单的“是”与“否”的“明确边界”，为模拟人类思维、处理模糊信息提供了新的工具。20世纪70年代到80年代初, 人们将物理学中把大型物质划分为颗粒、分子、原子的思想引入到信息领域，用于处理现实世界中的不精确、不完整的海量信息以实现智能系统或智能控制。1979年Zadeh发表的论文“模糊集与信息粒度”，成为世界上第一篇专门论述“信息粒度”的论文[2]。粗糙集的创始人Zdzislaw Pawlak于1982年也提出了信息的“粒度性”概念[3]。在1985年的国际人工智能联合会上，Hobss直接用粒度(Granularity)这个词作为论文题目发表论文[4]，并进一步探讨了不同层次的粒度和不同大小颗粒，粒度的分解与合并等问题。1988年T. Y .Lin教授提出邻域系统并研