粒计算研究现状及展望

龙源期刊网粒计算研究现状及展望作者：谢刚刘静来源：《软件》2011年第03期摘要：在信息处理中，粒计算是一种新的概念和计算范式,其本质是透过合适粒度的层次来对问题进行求解,并且在此过程中去除繁冗，降低实现的复杂度。本文主要对粒计算提出的背景、概念、研究现状及发展趋势进行论述，同时也给出了作者自己的评论，最后探讨了粒计算的进一步发展方向。关键词：粒计算;粗糙集;模糊集;商空间中图分类号：TP18,TP206文献标识码Adoi:10.3969/j.issn.1003-6970.2011.03.002AReviewofthePresentStudyingStateandProspectofGranularComputingXIEGang,LIUJing(CollegeofInformationEngineering,TaiyuanUniversityofTechnology,Taiyuan030024,China)【Abstract】Granularcomputing(GrC)isanemergingconceptualandcomputingparadigmofinformationprocessing,whichitsoughtessentiallyproblemsofabetterandapproximatesolutiontoreducethecomplexityofproblemsolvingbytherightchoiceofgranularity.Inthispaper,theproposedbackground,thepresentstudyingstateanditsdevelopingdirectionofgranularcomputingaresummarized.【Keywords】granularcomputing;roughset;fuzzyset;quotientspace0引言“概念必须有明确的边界。没有明确边界的概念，将对应于一个在周围没有明确界线的区域。”这是谓词逻辑的创始人Frege曾经说过的话，在此基础上他提出了概念的“含糊性”和“边界”问题[1]。由此1965年L.A.Zadeh创立了模糊集理论，突破了经典集合简单的“是”与“否”的“明确边界”，为模拟人类思维、处理模糊信息提供了新的工具。20世纪70年代到80年代初,人们将物理学中把大型物质划分为颗粒、分子、原子的思想引入到信息领域，用于处理现实世界中的不精确、不完整的海量信息以实现智能系统或智能控制。1979年Zadeh发表的论文“模糊集与信息粒度”，成为世界上第一篇专门论述“信息粒度”的论文[2]。粗糙集的创始人ZdzislawPawlak于1982年也提出了信息的“粒度性”概念[3]。在1985年的国际人工智能联合会上，Hobss直接用粒度(Granularity)这个词作为论文题目发表论文[4]，并进一步探讨了不同层次的粒度和不同大小颗粒，粒度的分解与合并等问题。1988年T.Y.Lin教授提出邻域系统并研龙源期刊网究了邻域系统与关系数据库之间的关系[5]，并在1996年正式提出“granularcomputing”的概念,缩写成GrC。据此他提出使用领域作为粒计算的表达，发表了一系列关于粒计算与邻域系统的论文[6-12]。之后粒计算的研究的迅速发展起来，目前已形成专门的研究群体。国内粒计算的研究也迅速延伸到各个研究领域[13-33]，这对于解决复杂的实际问题有重大意义。笔者从中国知网的CNKI检索关于“粒计算”的文献，以1994年至2010年为时间段，整理每年在CNKI收录的相关文章篇数如图1所示。由下面图1可知我国高校和研究机构从2002年起对粒计算研究的关注度逐年增高，发表的相关文献也是逐年递增。粒计算已经形成了一个新兴的热门研究领域，成为信息科学的研究热点并且粒计算方法的应用也日趋广泛[34,35]。图1至2011年1月国内CNKI检索到的“粒计算”方面的相关研究成果Fig.1TillJan.,2011theyieldedachievementsinGrCbyCNKI1粒计算理论1.1粒计算的基本概念从多粒度计算[36,37]的角度看,该计算模型大体由粒子、粒层和粒结构三个部分组成。粒计算模型构成的最基本元素是粒子[38,39],它是粒计算模型的原语。每个粒子都可被同时看作是由内部属性描述的个体元素的集合和由它的外部属性所描述的整体，以及由它的环境属性描述的对外界动态变化环境的回应。粒度是将性质相似的元素归结为一个新元素，用来衡量粒子“尺度”的概念，它反映了粒子进行“量化”时的粒化程度[39]。粒层是按照粒化准则得到的所有粒子的全体,是对现实空间的一种抽象化描述。根据具体的关系或算子,问题空间产生相应的粒子。同一层的粒子内部具有某些相同的性质或功能.但是粒化程度的不同,也会导致同一问题空间产生不同的粒层.在问题求解中,选择最合适的粒层对于问题求解尤为关键。在不同粒层上进行问题求解,并且不同粒层上的解能够相互跳转是粒计算模型的主要目标。一个粒化准则对应一个粒层,不同的粒化准则对应多个粒层。粒结构就表示了所有粒层之间相互联系的关系结构[40]，即一个系统或者问题的结构化描述,它反映了人们从不同角度、不同侧面来观察、理解、求解问题，同时粒结构还关系到问题求解的速度。1.2粒计算的基本问题龙源期刊网粒化和粒的计算是粒计算存在的两个最基本问题。粒化是构造问题求解空间的过程,即在给定粒化准则下将对象划分为一系列信息粒的过程,由不可分辨关系、相似性或泛函性聚集而成的对象集合(抽象)构建,包括粒子、粒网和层次结构。不同的粒化准则下可得到多个粒层,进而得到粒层的网络结构。通常有自顶而下的分解和自底向上的聚合两种粒化方法。粒化过程是粒计算的必要过程。问题空间的粒化过程主要包括粒构造的标准、粒构造算法(方法)和粒结构的表示及描述以及粒子和粒结构的定性(定量)描述等问题[41]。常用的粒化方法有：基于模糊集理论、基于拓扑理论、基于逻辑理论、基于商空间理论和基于决策逻辑语言。以粒子为运算对象进行问题的求解或推理,是狭义的粒计算。粒计算可以通过系统访问粒结构来解决问题,包括在层次结构中向上和向下两个方向的交互，以及在同一层次内的移动，即同一粒层上粒子之间相互转换和推理,不同粒层上粒子之间的转换或推理。不同粒层之间的联系可以由映射来表示,在不同粒层上同一问题以不同的粒度、不同的细节表示,粒层之间的映射就建立了同一问题的不同细节描述之间的关系。人们利用粒计算对同一问题的解可以在不同粒层之间自由转化的特点高效地实现复杂问题的求解。2粒计算的主要模型粒计算模型是一种概念模型或数学模型，是用来体现和描述论域(现实原型)的各种因素形式以及数量关系的一种数学结构，使用粒的概念和有关运算符号建立模型。目前使用最多的三种粒计算模型是:基于商空间理论的粒计算模型[42-55]、基于粗糙集理论的粒计算模型[56-61]和基于模糊词计算的粒计算模型[62-72]。2.1商空间理论的粒计算模型商空间理论主要是研究求解复杂问题的空间关系理论。其中主要包括复杂问题的商空间描述、分层递阶结构、商空间的分解与合成、商空间的粒度计算、粒度空间关系的推理以及问题的启发式搜索、路径规划和推理等[43，45,46]。近几年，基于商空间的粒度计算模型的应用得到了广泛的推广[43-48]。张铃教授指出人类智能的主要特征：演绎和归纳能力，即从整体(不同粒度、层次上)分析问题的能力(演绎)，从底层事物(数据)中总结规律的能力(归纳)，两种能力交替自如。在处理问题时人们对应的两个模型:粒度的商空间模型——宏观分析问题的能力，知识自动获取的学习模型——微观归纳规律的能力。这些为“商空间框架下的机器学习方法”的提出提供了理论基础。目前在商空间理论中，利用两个(或若干个)商空间的合成得到上、下界商空间，以实现极不相同粒度世界之间的转换。如果能够有效地解决极不相同粒层之间相互转换后的重要属性的不变程度，将会拓宽商空间的应用范围，且丰富粒计算的理论。龙源期刊网商空间理论的原型是分层递阶方法，其模型用一个三元组(X,f,T)表示所要研究的对象，论域X,论域X上的每个元素x,对应的属性函数值f(x),即在X上由属性函数f:X→Y(Y可以是多维，各维可是实数域，也可是其他的集合），用X上的拓扑T来描述X中各元素之间的关系-各个粒度的相互转换、依存关系。给定一等价关系R，由R得到对应的商集[X]，然后由[X]构造对应的商空间([X]，[f]，[T]),这是最常用的方法。商空间理论主要研究各商空间之间的关系、各商空间的合成、分解和在商空间中的推理。在商空间模型下建立对应的推理模型，并且满足“保假原理”和“保真原理”，因为这两个重要的性质可以使问题求解的搜索空间缩小、复杂度从“相乘”降为“相加”[49]。商空间理论的重点不仅限于在给定的商空间中讨论表达知识的问题，而是从所有不同商空间找出对同一问题不同角度的理解合成问题的最终解。商空间的求解过程是在一个合适的粒层上的所有商空间组成的划分格中运动转换的过程，可以看作是宏观的粒度计算。而粗糙集理论则不同，它是在给定的商空间中讨论问题求解，故可看作是微观的粒度计算[50-55]。2.2粗糙集理论的粒计算模型1982年代初，波兰华沙大学逻辑学家ZdzislawPawlak教授领导的小组，在研究信息系统的逻辑特性中，围绕着“人的知识就是一种分类的能力”这个观点对上述问题的方法论进行了探讨，提出了处理数据的数学理论—粗糙集理论。粗糙集理论从新的视角定义知识，认为知识是对事物的识别与分类能力。提出知识具有“粒度性”(granularity，颗粒状)的概念，即知识、概念或数据的模糊性被定义为它们具有不精确的“边界”。在信息处理中，把那些无法确认的样本归属于不明确划分的“边界区”；边界区是“上近似集”和“下近似集”之差集，有确定的数学公式描述，完全由数据决定，所以更有客观性(不同于模糊集隶属度的主观色彩)。当分类存在矛盾(同一事物既属于、又不属于某类)，导致不确定划分，可用粗糙度度量。这种方法为处理带噪声、不精确或不完全数据分类问题提供了一套严密的数学工具，对知识能够进行严密分析和操作。根据事物的属性不同对事物进行判别分类(决策)得出存放在信息系统中的知识的决策表，当某些条件满足时，可对数据进行约简，使表格简化，剔除不必要的信息。粗糙集理论为数据挖掘、知识发现提供了一种崭新的工具和深刻的理论基础。传统的粗糙集理论是基于单一粒定义的，即静态粒。Hobbs提出“人类问题求解的基本特征之一就是多粒度计算的思想,具有从不同的粒度上观察世界,且很容易地在不同的抽象层次间转换的能力,即分层次地处理它们(Oneofthebasiccharacteristicsofhumanproblemsolvingistheabilitytoconceptualizetheworldatdifferentgranularitiesandtranslatefromoneabstractionleveltotheotherseasilyi.e.,dealwiththemhierarchically)”的思想[56]。降低处理复杂问题的复杂性是多粒度计算的精髓，因此多粒度计算与不确定性问题相结合的道路是必然[57]。人们还提出了多粒运龙源期刊网(multigranulationsroughset)[58-60],使粗糙集理论由单粒运算推广到多粒运算。文献[1-3]主要讨论了集合在粒度P和Q的P+Q、P∩Q运算下的上下近似集合，文献[61]进一步对多粒度运算下的粗糙集模型进行了讨论，并将其与单粒度下的粗糙集模型进行比较；同时将多粒运算下的粗糙集模型与组合粒度