摘要:粒度计算是新近兴起的人工智能研究领域的一个方向,本文简单介绍粒度计算的主要三个方法,以及之间的关系。

关键词:粒度计算、模糊逻辑、商空间理论、粗糙集理论。

一.引言

人们在思考问题时,或者是先从总体进行观察,然后再逐步深入地研究各个部分的情况;或先从各个方面对同一问题进行不同侧面的了解,然后对它们进行综合;或是上面两种方法的组合,即时而从各侧面对事物进行了解,然后进行综合观察,时而综合观察后,对不甚了解的部分再进行观察……总之,根据需要从不同侧面、不同角度反复对事物进行了解、分析、综合、推理.最后得出事物本质的性质和结论.

人工智能研究者对人类这种能力进行了深入地研究,并建立了各种形式化的模型.本文要介绍的粒度计算,就是对上述问题的研究的一个方面.

人工智能最主要的目的是,为人类的某些智能行为建立适当的形式化模型,以便利用计算机能再显人的智能的部分功能。什么是人类的最主要的智能,或者说智能的最重要表现形式是什么。各家有不同的看法,如Simon等认为人的智能表现为,对问题求解目标的搜索(Search)能力。比如学生在证明一道平面几何题目时,进行思考,“聪明的小孩”能很快地找到证明该结论的有关的定理性质,并很快地应用上去,从而就得到证明。“数学能力差的学笨赡芏椅餮埃也坏胶鲜实亩ɡ砗托灾剩评慈迫ィ艿貌坏街っ鞯囊欤籔awlak[P1]则认为人的智能表现为对事物(事件、行为、感知等)的分类(Classification)能力。如平时我们说某医生本事大,就是这位医生能从病人的症状中,正确地诊断出病人是患什么病(分类能力!分出患什么病来)等等。我们认为“人类智能的公认特点,就是人们能从极不相同的粒度(Granularity)上观察和分析同一问题。人们不仅能在不同粒度的世界上进行问题求解,而且能够很快地从一个粒度世界跳到另一个粒度的世界,往返自如,毫无困难。这种处理不同世界的能力,正是人类问题求解的强有力的表现”[ZH1]。还有很多不同的理解,人们正是从这些不同的理解分别建立各自的模型和相关的理论和方法。

粒度计算目前国际上有三个主要的模型和方法,下面简单进行介绍。

二. 三种不同的模型

下面简单介绍有关“粒度计算”的三个不同的模型和方法。

什么是粒度,顾名思义,就是取不同大小的对象。也就是说,将原来“粗粒度”的大对象分割为若干“细粒度”的小对象,或者把若干小对象合并成一个大的粗粒度对象,进行研究。

最近Zadeh在[ZA1]-[ZA3]中,讨论模糊信息粒度理论时,提出人类认知的三个主要概念,即粒度(granulation)、组织(organization)、因果(causation)(粒度包括将全体分解为部分,组织包括从部分集成为全体,因果包括因果的关联)。并进一步提出粒度计算。他认为,粒度计算是一把大伞它覆盖了所有有关粒度的理论、方法论、技术和工具的研究。指出:“粗略地说,粒度计算是模糊信息粒度理论的超集,而粗糙集理论和区间计算是粒度数学的子集”。

Zadeh 的工作激起了学术界对粒度计算研究的兴趣,Y.Y.Yao和他的合作者对粒度计算进行了一系列的研究[Y1]-[Y3]并将它应用于数据挖掘等领域,其工作的要点是用决策逻辑语言(DL-语言)来描述集合的粒度(用满足公式f元素的集合,来定义等价类m(f)),建立概念之间的IF-THEN关系与粒度集合之间的包含关系的联系,并提出利用由所有划分构成的格,来求解一致分类问题。这些研究为知识挖掘提供了一些新的方法和角度。

按Zadeh粒度计算的定义,我们提出的商空间理论和Pawlak的粗糙集理论都属于“粒度计算”范畴。

目前有关粒度计算的理论与方法,主要有三个。一是Zadeh的“词计算理论”(Theory of Works Computing),一是Pawlak的“粗糙集理论”(Theory of Rough Set),另一个是我们提出的“商空间理论”(Theory of Quotient Space)。

下面简单介绍三者的内容:

1. 词计算理论:

Zadeh认为人类在进行思考、判断、推理时主要是用语言进行的,而语言是一个很粗的“粒度”,如我们说“九寨沟的风景很美”,其中“很美”这个词就比较“庞统”,也就是说其粒度很粗,如何利用语言进行推理判断,这就是要进行“词计算”,早在二十世纪六十年代Zadeh提出模糊集理论,就是“词计算”的雏型。沿Zadeh的模糊集论的方向,用模糊数学的方法进行有关粒度计算的方法和理论的研究,就构成“粒度计算”的一个非常重要的方法和方向。这也是人们比较熟悉的一个方法。

2. 粗糙集理论:

波兰学者Pawlak[P1]在二十世纪八十年代,提出的粗糙集理论,他提出一个假设:人的智能(知识)就是一种分类的能力,这个假设可能不是很完备,但却非常精练。在此基础上提出,概念可以用论域中的子集来表示,于是在论域中给定一组子集族,或说给定一个划分(所谓划分,是指将X分成两两不相交的子集之并)。从数学上知道,给定X上的一个划分,等价于在X上给定一个等价关系R。Pawlak称之为在论域上给定了一个知识基(X,R)。然后讨论一个一般的概念x(X中的一个子集),如何用知识基中的知识来表示,就是用知识基中的集合的并来表示。对那些无法用(X,R)中的集合的并来表示的集合,他借用拓扑中的内核和闭包的概念,引入R-下近似R-(x)(相当于x的内核)和R-上近似R-(x)(相当于x的闭包),当R-(x)1R-(x)时,就称x为粗糙集.从而创立了“粗糙集理论”。目前粗糙集理论已被广泛应用于各个领域,特别是数据挖掘领域,并获得成功。

3.基于商空间的粒度计算.

我们认为概念可以用子集来表示,不同粒度的概念就体现为不同粒度的子集,一簇概念就构成空间的一个划分----商空间(知识基),不同的概念簇就构成不同的商空间. 故粒度计算,就是研究在给定知识基上的各种子集合之间的关系和转换.以及对同一问题,取不同的适当的粒度,从对不同的粒度的研究中,综合获取对原问题的了解.这种对粒度的理解与模糊集对粒度的理解不完全一样.

下面简单介绍基于商空间的粒度计算。

3.1商空间模型下的推理模型

商空间的模型用一个三元组来表示,即(X,F,T),其中X是论域,F是属性集,T是X上的拓扑结构.当我们取粗粒度时,即给定一个等价关系R (或说一个划分),于是我们说得到一个对应于R的商集记为[X],它对应于的三元组为([X],[F],[T]),称之为对应于R的商空间.商空间理论就是研究各商空间之间的关系、各商空间的合成、综合、分解和在商空间中的推理。

在这个模型下,可建立对应的推理模型,并有如下的性质.

A. 商空间模型中推理的“保假原理”(或“无解保持原理”).

B. 商空间模型中推理合成的“保真原理”.

所谓“保假原理”是指若一命题在粗粒度空间中是假的,则该命题在比它细的商空间中一定也无解。

所谓“保真原理”,是指,若命题在两个较粗粒度的商空间中是真的,则(在一定条件下),在其合成的商空间中对应的问题也是真的。

这两个原理在商空间模型的推理中起到很重要的作用,如若我们要对一个问题进行求解,当问题十分复杂时,常先进行初步分析,即取一个较粗粒度商空间,将问题化成在该空间上的对应的问题,然后进行求解,若得出该问题在粗粒度空间中是无解,则由“保假原理”,立即得原问题是无解的。因为粗粒度的空间规模小,故计算量也少,这样我们就可以以很少的计算量得出所要的结果,达到“事半功倍”的目的。

同样利用“保真原理”也可达到降低求解的复杂性目的,设在两个较粗空间X1、X2上进行求解,得出对应的问题有解.利用“保真原理”可得,在其合成的空间X3上问题也有解。设X1、X2的规模分别为s1、s2。因为一般情况下,X3的规模最大可达到s1s2。于是将原来要求解规模为s1s2空间中的问题,化成求解规模分别为s1、s2的两个空间中的问题。即将复杂性从“相乘”降为“相加”。

四.商空间理论、粗糙集理论和模糊集理论之间的关系

4.1在模型上

三者都是描述人类能按不同粒度来处理事物的能力的模型.

商空间理论、粗糙集理论认为概念可以用子集来表示,不同粒度的概念可以用不同大小的子集来表示,所有这些表示可以用等价关系来描述。

词计算理论认为概念是用“词”来表示,而描述“词”的有效的方法就是模糊集理论。

4.2.研究的对象

商空间理论、粗糙集理论、词计算理论都将所讨论的对象的集合构成论域,但讨论对象之间的关系时,却各有不同。

粗糙集理论的原型估计是由关系数据库抽象而得的,故其模型为(X,F)(其中X是论域,F是属性集),即通过元素的不同属性值,来描述元素之间的关系,并用元素按不同属性进行的分类来表示不同的概念粒度。

商空间理论的原型是分层递阶方法,故其模型为(X,F,T)(其中X是论域,F是属性集,T是X上的拓扑结构)即除了元素的属性外,还引入元素之间的关系T(用拓扑来描述),从这个意义上来说,粗糙集理论是商空间理论的一个简单的特例。当然各自研究的着重点和侧重点不同。

当给定一个等价关系时,粗糙集理论认为是给定一个知识基,然后讨论任给的一个概念(集合)在这个知识基上如何被表示为知识基上集合之并,以及之间的关系。粗糙集理论主要利用集合的基数(元素个数)之间的关系,来描述概念之间的隶属关系,这样在一定程度上与模糊集概念联系起来。另外,粗糙集理论还讨论如何利用属性来最简单地表示所对应的知识基,这就是所谓“简约”问题。但因模型缺乏描述元素之间的相互关系的手段,故很难提取有结构论域中有关结构所提供的信息。当然结构在一定意义下也可以看成是元素的某种属性,但这种属性是多元属性(要用多元函数来表达),一般不能表示为f(x),而要用f(x,y,..)表示,如距离要用d(x,y)表示.

商空间理论着重点不同,它不是只针对给定的商空间(知识基)来讨论知识的表达问题,而是在所有可能的商空间中,找出最合适的商空间,利用从不同商空间(从不同角度)观察同一问题,以便得到对问题不同角度的理解,最终综合成对问题总的理解(解).它的求解过程是在“由所有商空间组成的半序格”中运动转换的过程.故可看成是宏观的粒度计算.而粗糙集理论是在给定的商空间中的运动,故可看成是微观的粒度计算.

词计算理论与商空间理论、粗糙集理论稍为不同,它主要研究(从粒度计算的观点来看它)如何描述由词界定的不同粒度的对象,它更擅长描述由形容词、副词表达的不同粒度的概念,如非常好、很好、好、很不错、还好,…等等. 因为这些词有程度不同的差别,故在一定意义下,词计算理论也给出了描述元素之间的关系,但只限于由属性的强弱程度不同所形成的关系.

从理论上说,将商空间理论、粗糙集理论看成是“精确”的粒度计算,那么都可在其模型上引入模糊的概念,得模糊的商空间理论,和模糊的粗糙集理论.

在[ZH2]中我们证明:模糊的等价关系,等价于在某个商空间上的归一等腰距离。即,可将它化成有结构的商空间。于是这三者都可统一地用多尺度的商空间理论来表示.如设商空间理论中原来的结构是一距离d1(x,y),这个d1是元素在空间”位置”关系的描述, 而由模糊概念引入的距离d2,可以看成是元素之间的属性关系的描述.

属性是对元素个体性质的描述,而尺度是对元素之间关系的描述(当然也可看成是多元属性).

若属性值是取值于一个良序集上时,多可用模糊集来描述.

将三者有机地结合起来,对发展粒度计算将有重大意义。

4.3. 结构的重要性

最后阐述在粒度计算中结构的重要性,在问题求解时,人们多从一组前提出发,希望由它通过一系列的推导,得到结论。若将每个步骤用箭头相连,则得到由前提到目标的一条有向路。或更一般,问题求解可看成是在某有结构的空间中,求一条由前提到目标的有向路(或一条路径),于是当空间的结构是拓扑空间时,关于问题求解的解的存在性问题,就等价于在空间中回答“前提与目标是否处在同一线连通成份中”。而求解问题,就是在有解情况下,求从前提到目标的一条有向路径。

利用商空间中粗空间对细空间的“保假性”,(即:若问题在粗空间中无解,则在比它细的空间一定也无解)通过合理的分层递阶,可大大降低问题求解的复杂性。

我们对常遇到的结构如:半序结构、距离结构以及一般拓扑结构,其对应的商空间的构成及不同商空间的综合都给出有效的构造性的算法。

对什么情况下分层递可以降低计算复杂性,能降低多少等,我们在[Z1]中也进行了详细地论述。

在[ZH3]中还把统计推断方法引入商空间模型,为多层信息综合、不确定推理、定性推理等,建立数学模型和相应算法,有效降低了计算复杂性。

有结构的模型在实际问题求解中是经常遇到的,如地理信息中其地理位置之间的关系就是一个距离结构;在数据仓库中各数据之间的关系可用半序来描述,它也是一种结构;又在路径规划中对象所处空间的位置关系,就是一种距离的结构;在数据挖掘中的规则发现,所有的规则全体按其包含关系就构成半序结构等等。在这些有结构的对象中进行问题求解利用基于商空间理论的粒度计算将是很有效的。

商空间的方法与目前流行的“粗糙集”方法相同之处在于:都是利用等价类来描述“粒度”,都是用“粒度”来描述概念。但讨论的着重点有所不同,我们的着重点是研究不同粒度世界之间的互相转换、互相依存的关系,是描述空间关系学的理论;而目前的粒度计算(如粗糙集理论等)主要是研究粒度的表示、刻划和粒度与概念之间的依存关系。更主要的不同在于:我们的理论是在论域元素之间存在有拓扑关系的情况下进行研究的,即论域是一个拓扑空间,而现在的粗糙集理论,其论域只是简单的点集,元素之间没有拓扑关系(只是商集理论,而不是商空间理论),故它们讨论的是无结构的特殊情况。

另外,粗糙集是在给定的知识基上求解对应的问题,如求集合的R-上近似和R-下近似,我们是在(X,T)中讨论各商空间之间的关系,求相应的(各种意义下)上近似空间和下近似空间。从这个角度看,可以说粗糙集是微观的粒度计算,商空间理论是宏观的粒度计算。这两个理论都是建立在等价关系之上,所有可以将两者结合起来。

Zadeh 所讨论的粒度计算与Pawlak和我们所讨论的粒度问题又有些不同,他主要是讨论粒度的表示问题,他们认为人类是用语言进行各种思考和推理的,不同的词就表示不同的粒度,那么如何表示它们呢?一般来说用“语言”、“词(word)”来表示的概念,牵涉到“词计算”问题。而词计算,现在最流行的方法是“模糊数学”的方法,于是他得出的结论是:模糊数学应是粒度计算的主要工具之一。

依Zadeh的看法,Pawlak和我们讨论的粒度是“清晰的粒度”,而他自己讨论的是“模糊粒度”。

如何将模糊集的方法引入商空间理论中来,这可从几方面着手进行,一是在论域X上引入模糊集;二是在结构T上引入模糊拓扑结构;三是对我们的核心概念等价关系,引入模糊概念。

以上简单介绍了商空间理论、词计算理论、粗糙集等粒度计算方法之间的关系。可以看出这三个不同的粒度计算理论,从思考问题的出发点和解决问题的任务,都不尽相同,各有千秋。但是三者都有一个共同的特点,那就是都考虑到人类智能中,有从不同粒度思考问题的这一特点。如何将三者的优点结合起来,形成更强有力的粒度计算的方法和理论,是今后一个重要的研究课题。一个明显可进行的研究是:将商空间理论与粗糙集方法相结合,或说将粗糙集方法引入商空间理论中来,或说在商空间理论中同时讨论微观的粒度计算问题,将微观和宏观的粒度计算统一起来,构成一个更加完整的粒度计算理论和方法,将会更有效的。

参考文献

[P1] Z. Pawlak, Rough Sets Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, Boston, London, 1991.

[Y1] Y. Y. Yao, Granular Computing: basic issues and possible solutions. Proc. of fifth Joint Conference on Information Sciences, Vol.I, Atlantic City, New Jersey, USA, 2000:186-189.

[Y2] Y.Y. Yao, and X. Li, Comparison of rough-set and interval-srt models for uncertain reasoning, Fundamental Informatics, 27,1996:289-298.

[Y3] Y.Y. Yao and Ning Zhong, Granular Computing Using Information Table, in T.Y. Lin, Y.Y Yao, and L. A. Zadeh (editors) Data Miming, Rough Sets and Granular Computing, Physica-Verlag, 2000:102-124.

[ZA1] L. A. Zadeh, Fuzzy logic=computing with words, IEEE Transactions on Fuzzy Systems, 4, 1996:103-111.

[ZA2] L. A. Zadeh, Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy Sets and Systems, 19, 1997:111-127.

[ZA3] L. A. Zadeh, Announcement of GrC, 1997, http://www.cs.uregina.ca/~yyao/GrC/

[ZH1] 张钹,张铃《问题求解的理论及应用》,清华大学出版社,1990)(英文版. Bo Zhang and Ling Zhang, Theory and Application of Problem Solving, North-Holland, Elsevier Science Publishers B.V. 1992)

[ZH2] 张铃 张钹 模糊商空间理论(模糊粒度计算方法)“软件学报”,14(4)2003:770-776.

[ZH3] Zhang Ling,Zhang Bo,Statistical Genetic Algorithm, Chinese Journal of Software Vol.8,No.5:335-344(张铃,张钹,统计遗传算法《软件学报》8(5),1997:335-344。