1.2 粒计算

近年来，在以模糊集为基础的模糊计算和以粗糙集为基础的粗糙计算的基础上，世界各国的学者又发展了粒计算（Granular Computing，GrC），它是一种新的软计算方法。

Lotfi A.Zadeh于1979年研究了模糊集与信息粒度（Information Granularity）的关系问题[61]。Stanford大学教授J.R.Hobss于1985年发表于在美国Los Angeles举行的国际人工智能联合会议上的论文“Granularity”，直接用粒度这个词作论文题目。

20 世纪90年代中期，随着模糊集与粗糙集理论的深入研究，信息颗粒（Information Granules）和粒计算的研究开始兴起，波兰科学家Andrzej Skowron于1992年研究了信息颗粒的规则抽取方法，随后Andrzej Skowron及其合作者又提出了信息颗粒的构造方法，对信息颗粒与近似空间的关系，信息颗粒的计算和粗糙公理方法等问题进行了深入的探讨[62～66]；Lotfi A.Zadeh又于20世纪90年代中后期先后发表文章研究了模糊图、粗糙集与信息粒度的关系，探讨了信息粒度化、模糊逻辑与粗糙集的关系以及模糊逻辑与词计算的关系，分析了模糊信息颗粒化（Fuzzy Information Granulation）及其在人工推理（Human Reasoning）与模糊逻辑（Fuzzy Logic）中的理论与应用等问题。在此期间，Zadeh提出人类认知的三个主要概念，即粒度（Granulation，包括将全体分解为部分）、组织（Organization，包括从部分集成全体）和因果（Causation，包括因果的关联），并进一步研究了粒计算。他认为，粒计算是一把大伞，它覆盖了所有有关粒度的理论、方法论、技术和工具的研究。他指出“粗略地说，粒计算是模糊信息粒度理论的超集，而粗糙集理论和区间计算是粒度数学的子集。”[67～70]

T.Y.Lin教授于1996年在UC-Berkeley大学Zadeh的重点实验室做客座教授时，向Zadeh提出作“Granular Computing”课题的研究。当时Zadeh称“Granular Mathematics”，T.Y.Lin改称“Granular Computing”后，立即得到Zadeh的认可，并且缩写成GrC。所以“Granular Computing”成为今天的一个热门研究领域。T.Y.Lin发表系列论文研究了二元关系的粒计算、粒化模糊集、利用粒化方法进行关联规则的挖掘，以及与信息颗粒、颗粒计算有关的关系数据库的面向机器的数据挖掘建模理论问题[71～77]，提出了利用信息颗粒的位表示来进行数据挖掘的思想，他主要的工作是把该思想用于真实世界的建模、数据挖掘的建模和各种关联规则的发现，其研究方法为数据挖掘提供了一种新的思路。

他们的工作激起了学术界对粒度计算研究的兴趣，加拿大学者Y.Y Yao也先后发表论文研究了分层的粗糙集与粒计算、粗糙集与邻近系统（Neighborhood Systems）和粒计算的关系、信息粒化与粗糙集近似、信息表的粒计算、使用粒化计算进行数据挖掘建模等专题[78～86]，并将其应用于数据挖掘等领域。其工作要点是，用决策逻辑语言（DL-语言）来描述集合的粒度（用满足公式f元素的集合来定义等价类m（f）），建立概念之间的if-then关系与粒度集合之间的包含关系的联系，并提出利用由所有划分构成的格来求解一致分类问题。所有这些研究都为知识挖掘提供了新的方法和角度。

粒计算是一门飞速发展的新学科，它融合了粗糙集、模糊集及人工智能等多种学科的研究成果。人们对粒计算的描述是建立在对它的知觉认识上的：粒计算是研究基于多层次结构的思维方式、问题求解方法、信息处理模式及其相关理论、技术和工具的学科[87]。

在我国，粒计算的研究已引起众多学者的关注与兴趣。其研究论题包括：基于商空间理论的粒计算模型、模糊商空间及粒计算的商闭包空间模型；粒计算的覆盖模糊、粗糙集与粒计算的交叉问题的研究；粒、规则与例外的关系；粒计算的理论、模型与方法的探讨；基于Dempster-Shafer证据理论和粗糙集的近似和知识约简；几种基于覆盖粗糙集的粒计算模型；粒逻辑及其归结原理；基于关系的粒计算模型，粒计算在进化计算、机器学习中的应和使用粒计算进行知识获取的方法；基于泛系理论的粒计算模型；使用粒分析来描述和刻画粒计算的思考等[87]。

粒计算借助于其他学科的哲学思想和方法论，并将它们抽象成为与具体领域无关的方法和策略。它的独特性体现在用系统和结构化的理解和方法来解决复杂问题。对复杂问题的全面理解通常是多视角的，从每一个视角着眼的理解又是多层次的。由此可以得出，粒计算的过程就是对复杂问题的求解过程。它的结果表现为一个多视角和多层次的粒结构。这个粒结构是对此复杂问题的系统且近似的描述和解答。

对粒计算的研究应该着眼于三个观点：粒计算的哲学思想观点、方法论观点及计算模式观点。从哲学思想观点考虑，粒计算试图将人类的认知方式抽象化和形式化，从而提炼出结构化的思维模式；从方法论观点考虑，粒计算着重研究系统化的方法和技术，将问题求解的过程规范为结构化的、自上而下的逐步求精过程；从计算模式观点考虑，粒计算关注结构化的信息处理。粒计算的三个观点可以用三角形来表示，也可以用层次结构或三维空间模型来描述。

1.2.1 信息粒

按照Lotfi A.Zadeh的观点，信息粒（Information Granule）是通过不可分辨性（Indistinguish Ability）、相似性（Similarity）、近似性（Proximity）或功能性（Functionality）等来划分的对象的集合。一般来说，人类的认知的有三个基本的概念：粒度（Granulation，也称粒化）、组织（Organization）和因果（Causation），粒化把整体分解为部分，组织则是把部分集成为整体，而原因则涉及事物之间的关联[70]。

“Granule”被解释为中文词意“基本粒”，在英汉词典中被说成是紧紧凝结在一起的“颗粒”和“块”等，“Information Granules”是研究将信息集切割成互不相交的“片”和“块”等，或划分成互不相交的“子集”、“组”、“类”和“群”等，实质上是“划分”（Partition）的意义，表示颗粒之间是清晰、互不相交的。可见粒计算是研究信息划分的。

“Granulation”被译为“粒”。Lotfi A.Zadeh于1997年发表的论文：“Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzylogic”中 用 了“Granulation”，“Information Granulation”意思是将信息切割或分成可能两两有交的“类”和“块”等，他从模糊集观点讨论，所以被分成的颗粒可能是模糊或不清晰边缘的“块”。所以，粒计算是研究信息分类，被分成的块是两两分离的划分还是两两可能有交的模糊分割；研究分成的粒度大小，不同粒度层之间的关系，粒度分解和合并等。

定义1.4[64] 一个定制的近似空间为一个系统AS#，S=(U，I#，vS)，其中：

U为对象的非空有限集；

I#：U→P（U），P（U）表示U 的幂集，是一个不确定函数，不确定函数对每个对象x定义了一个相似对象的集合；

vS：P（U）×P（U）→[0，1]是一个粗糙包含函数。

定义1.5[64]（信息粒）：称序对IS=（U，A）为信息系统，其中U 为论域，A 为有限属性集，a∈A，一个基本的信息粒定义为EFB(x)，这里EFB为a=a(x)的选择子的连接，||EFB(x)||IS=||∧a∈Ba=a(x)||IS，其中B⊆A，x∈U，||●||为公式集Φ 到幂集P（U）的映射函数。

从本质上讲，“粒”即基本元素，信息粒是在基本集中具有相同或相似属性值的对象集合，一个基本粒相当于粗糙集的一个等价类，等价类也称为等价粒，如决策规则的前件、后件和规则本身等就是一种粒。

定义1.6[64] 设信息系统IS=（U，A），假设S为一粒序列，且IS中||●||IS的语义及其元素已被定义，扩展||●||IS到S 上，定义为||S||IS={||g||IS：g∈S}。

定义1.7[64]（粒集） 设信息粒集G 以及IS中的G 的粒||●||IS已经被定义，扩展||●||IS到集合H⊆G为||H||IS={||g||IS：g∈H}。

对于信息粒来说，有两个基本的度量：粒的包含度（Inclusion）和接近度（Closeness），下面对它们进行简要介绍。

两个信息粒G，G＇的包含度至少为P 记为vP(G，G＇)，类似地，两个信息粒G，G＇的接近度至少为P记为clP(G，G＇)。

在信息系统IS=（U，A）中，粒由EFB(x)定义，这里EFB为a=a(x)的选择子的连接，||EFB(x)||IS=||∧a∈Ba=a(x)||IS，其中B⊆A，x∈U，设G={EFB(x)：B⊆A&x∈U}，设α、β∈G={EFB(x)：B⊆A&x∈U}，α，β之间的精确包含的定义为：||α||IS⊆||β||IS，这里||α||IS，||β||IS分别为满足α，β的对象的集合，而非精确描述，如知识发现的关联规则里，可以通过两个阈值t与t＇来定义：

supportIS (α、β)=card(||α∧β||IS)≥t且

accuracyIS 。

在一个给定的信息系统中，基本的信息粒包含可以按照不同的方式进行定义，例如：

vI，S (，)t t αβ＇ 成立当且仅当supportIS(α，β)≥t&accuracyIS(α，β)≥t＇。

基本粒的接近度可以定义为：

成立，当且仅当成立且成立。

1.2.2 信息粒化

粒化是人类理解认识问题的一个内在的自然活动，信息的粒化相当于把原始复杂的问题分解为多个可定义的子问题，这样可以降低原始问题的计算复杂性。粒化问题随处可见，它是许多学科的共同研究课题，如：可以把时间信息粒化形成时间信息粒——可定义的时间间隔。

在很多计算机系统模型中，往往把内存资源粒化为内存页的概念来做为它的基本操作单位。

尽可能地粒化数字图像为基本单元——个体像素，这样便于对一些大的实体进行处理和分析。

在处理问题时，往往趋向于构造规则（if-then描述），这其实已经将问题粒化。

在一个确定的程度上进行数据压缩也是信息粒化的一个范例。

对于信息的粒化，有两点需要说明：

（1）信息的粒化是一个自然分层的结构，可以把时间粒化为年、月、日、小时和分钟这样一个分层结构。

（2）不同的理论进行粒化的方法是不同的：

集合论使用间隔（区间）分析进行粒化，它的基本粒是定义在实轴上的间隔（Intervals），其形式化的模型为：集合A 定义为给定的论域U（实数R 的子集）到{0，1}上的二值映射：A：U→{0，1}，这里A（u）为A的特征函数。

模糊集为集合概念的泛化，模糊集基于元素对于模糊集合的隶属程度。模糊集通过它们的隶属函数来形式化地描述：A：U→[0，1]，其隶属值越大，给定的元素x 对于模糊集的附属程度越强。

粗糙集是给定实验数据中近似概念的合成。粗糙集中的基本粒是按照等价关系定义的等价类。给定定义在U×U 上的不可分辨关系R，则一个粗糙集由下近似和上近似构成，从根本上说，上、下近似的差别越大，则边界越明显，粗糙度越大。

1.2.3 粒计算概念

信息粒度与信息粒是不同且相关的两个概念。

文献[88，89]使用一个三元组（U，F，Γ）来描述一个问题，其中：

U 表示问题的论域，也就是要考虑的基本元素的集合；设F为属性函数，定义为F：U→Y，Y 表示基本元素的属性集合；Γ 表示论域的结构，定义为论域上各个基本元素之间的关系。

从一个较粗的角度看问题，实际上是对U进行简化，把性质相近的元素看成是等价的，把它们归为一类，整体上做为一个新元素，这样就形成一个粒度较大的论域[U]，从而把原始问题（U，F，Γ）转化为新层次上的问题（[U]，[F]，[Γ]）。

粒计算是一种新的软计算方法，它的基本成分是论域的子集、类和簇。在粒化计算中，主要涉及的问题有粒的描述、粒之间的关系和粒的计算等，它们可以用于很多领域，如聚类分析、概念的形式化、机器学习和数据挖掘等。

目前粒计算的研究主要从粒的构造和粒的计算两个方面展开。粒的构造包括粒的形式化、表示和解释。粒的形式化与表示粒构造的算法描述；粒的解释一般指粒构造的语义，它表明了为什么两个对象能够归为同一个粒，进一步说，信息的粒化依赖于可用的知识。粒的计算则指在解决问题中粒的利用，它也是从语义解释及算法描述两方面入手：一方面，人们需要解释粒之间的不同关系，如相近性（Closeness）、依赖性（Dependency）、关联性（Association）、定义与解释粒的操作；另一方面，人们需要设计粒计算的方法与工具，如近似性（Approximation）、推理（Reasoning）和推论（Inference）[84]。

粒计算与数据挖掘的关系可以从概念的形式化与概念关系的确定两方面来说明。在概念的形式化研究中，一般认为概念由内涵与外延构成：概念的内涵由相关的属性或特征构成，它表明了对象应用的有效性，概念的外延指相应的对象集，外延中的对象具有相同的特征或属性，也就是说，外延构成了对象具体的实例。从粒化计算的观点看，每个粒可以作为概念的一个实例。一旦概念被构造和描述，人们便可用粒构造相应的计算方法。特别地，人们可以根据概念的内涵与外延研究概念之间的关系，比如子概念（Sub-concept）、无关性（Disjoint）、重叠概念（Overlap Concept）和部分子概念（Partial Sub-Concept）等，这些关系可以按照规则或关联度量来方便地表示[84]。

粒计算的操作对象是信息粒，而信息粒按照粒度的不同展现出不同的层次，即一种分层结构。按照所处理的问题，通常把相同或相似“尺寸”（粒度）的粒划为一层，如果需要了解更多的细节，则把它们划为较小的粒，而这些粒则处于另外一层，这样，按照粒度的不同，信息粒呈现一种自然的分层结构，如上面偏序格结构一样。

1.2.4 粒计算的研究方法与方向

粒计算的形成和发展积累了多种思想、模型、技术及方法论，对粒计算的研究可以从不同观点着手。现有的粒计算研究可以概括为三个主要观点：结构化思维、结构化问题求解和结构化信息处理，它们相互关联，又自成体系，形成了粒计算特有的三角形[87]。

1.粒计算三角形

在粒计算三角形中，哲学思想偏重思维的结构化，方法论注重问题求解的结构化，计算模式强调信息处理的结构化。多层次粒结构把这三个观点紧密地结合在一起，形成了研究粒计算的三个观点，如图1-1所示。

结构化思维强调了对粒计算的哲学思想的研究。思维本身既是问题求解的必经过程和必要手段，也是人脑对信息进行筛选、分类比较、整理归纳的复杂处理。结构化思维是人类智能的重要体现形式。

结构化问题求解研究粒计算的方法论。张钹和张铃教授对这个问题有系统和详细的论述。从粒计算三角形的角度来看，抽象思维与哲学思想有关，抽象技能与方法论有关。问题求解是一个逻辑化和结构化的思维过程，它需要解决两个问题：一是构建问题的粒结构；二是在此粒结构中进行问题求解。在某些情况下，这两个任务的界限并不明显，需要放在一起综合考虑。

结构化信息处理注重以计算为主的问题求解。Bargiela和Pedrycz在文献中对该问题有详细系统的描述。最近，Wing提出了计算思维的观点，将结构化思维和结构化信息处理紧密联系在一起，她认为计算机科学家所采用的计算思维方式可以推广和应用到不同学科，这就需要不同抽象层次的思维。信息处理是问题求解的一个特例，它本身并不一定需要由计算机完成。信息处理至少可以分成抽象的、人脑中的和计算机中的信息处理三种形式。其中抽象的信息处理与粒计算哲学思想密切关联，构建对信息的粒结构分析；人脑中的信息处理遵循粒计算的普遍方法论，涉及诸如信息粒化的原则；计算机信息处理强调信息在计算机中的存储、计算、显示和传递[87]。

2.粒计算的三个层次

粒计算的三个研究观点之间还存在着层次关系。其中，结构化思维作为其哲学思想指导处于最高、最抽象的层次；结构化问题求解作为方法论处于中间层次；结构化问题求解可以进一步用结构化信息处理实现，因而结构化信息处理位于阶梯层次的底部，如图1-2所示。

这样的层次结构反映了哲学思想、方法论及计算模式的关系。如果把粒计算研究作为一个实际问题，那么它也可以从以上三个层次求解。

对粒计算的研究方兴未艾，它的数学基础与理论还很不成熟，有许多问题还值得深入研究。