宋茂林， 吴伟志,2

(1.浙江海洋大学 信息工程学院,浙江 舟山 316022； 2.浙江省海洋大数据挖掘与应用重点实验室,浙江 舟山 316022)

粒计算(granular computing，GrC)是智能信息处理领域中大规模复杂问题求解的有效范式，它模拟人类思考问题的自然模式，是专门研究基于粒结构的思维方式、问题求解方法、信息处理模式的理论、方法、技术和工具的学科[1].粒计算的基本思想是在问题求解过程中从不同角度、不同层次上对现实问题进行描述、推理与求解.它以粒(granule)为基本计算单位，以处理大规模复杂数据集和信息等建立有效的计算模型为目标，以近似满意解替代传统的精确解使计算和决策更加高效.粒计算主要研究粒的构造、解释、表示、最优粒度的选择以及用规则形式所描述的粒与粒之间关系等[2-3].目前粒计算已成为智能信息处理领域一个非常活跃的研究方向，并且有望为大数据挖掘提供一条极具前途的崭新途径[1-2，4].

在众多粒计算研究方法中，粗糙集数据分析对粒计算研究的推动和发展起着重要的作用.粗糙集数据分析中的典型数据描述结构称为信息系统(information system)[5]，又称为信息表或对象-属性值表[3,6]，原始的Pawlak粗糙集理论利用数据样本集上的等价类来描述“粒”，用等价关系所诱导的划分来粒化数据的样本空间，用“粒”代替样本对数据进行处理，并通过计算所定义的约简(使得矛盾样本集不改变的极小属性集合)对数据集进行特征提取，最终获取聚类或分类规则或排序决策[5,7].传统的粗糙集数据分析所处理的信息系统中的每个对象在每个属性中只取唯一的值，这样的系统称为单尺度信息系统[6-8]，但在很多实际生活的数据处理中，人们要在多粒度或者多尺度环境下进行问题求解和决策[3].因此，单一粒度或单一尺度框架下的知识表示与数据处理方法已远远不能满足实际应用的需求[1,3].近年来，“多粒度”环境下的数据建模成为粒计算研究的重要方向[1,3,9-15].在基于粗糙集的多粒度数据分析建模中，主要有从属性选择可以引起多粒度的角度提出的多粒化粗糙集(multi-granulation rough set)模型[9-10]和从对象的邻域半径的大小可以引起多粒度的角度提出的多粒度邻域粗糙集(multi-granularity neighborhood rough set)模型[11-12].另一方面，Wu等[13]认为对象的属性取值的多尺度是引起论域的多粒度粒化的一个重要原因，为此提出了多尺度粗糙集数据分析的粒计算模型.数据的描述结构称为多尺度信息系统(multi-scale information system)(又称为多粒度标记信息系统[14])，这个数据处理模型被文献称为Wu-Leung模型[15].

多尺度粗糙集数据分析的主要思想是，根据决策目标对每个属性选择一个合适的尺度或者粒度构成一个新的单尺度信息系统，然后在保持相同目标约束的前提下进行属性约简(特征选择)、决策规则提取及相应的不确定性分析[6-8,13].因此，保持某种性质(可以是定性的也可以是定量的)不变意义下选择最粗的尺度标记(称为最优尺度选择或最优粒度选择)成为多尺度决策数据中知识获取的一个关键问题[3,6-8,13-16].近年来，最优尺度选择成为多尺度粗糙集数据分析的一个主要方向，并取得了很多研究成果[14-29].

迄今为止，关于多尺度决策系统中最优尺度选择的研究所针对数据系统的决策属性大多数是单尺度的，文献[30]首次提出了决策是多尺度信息系统的最优尺度选择问题，给出了协调的决策是多尺度的完备信息系统的最优尺度选择方法.现实生活中存在大量缺省或信息不完整的数据，在粗糙集数据分析中称为不完备信息系统[31-32].针对不完备数据，Wu等[14,33]提出了不完备多尺度决策系统的最优尺度选择和决策规则提取方法.本文中，笔者结合文献[30]和文献[28-29]，讨论决策是多尺度的广义不完备信息系统(简称决策多尺度不完备信息系统)的最优尺度选择问题.

1 预备知识

设U是非空论域，对于A⊆U，A在U中的补集记为～A，即～A={x∈U|x∉A}.本节简介下文要用到的一些基本概念与知识.

1.1 不完备信息系统

一个信息系统[5]为一个二元组(U,A)，其中U={x1,x2,…,xn}为一个非空有限对象集，称为论域，A={a1,a2,…,am}为一个非空有限属性集，使得∀a∈A，满足a:U→Va，即a(x)∈Va,x∈U，称Va={a(x)|x∈U}为属性a的值域.

若一个信息系统(U,A)中的某些属性值是缺省的或未知的，则称该系统为不完备信息系统[31]，用符号“*”表示未知值或缺省值，即如果a(x)=*，那么就认为对象x在属性a上的值是未知的.

对于给定的一个不完备信息系统(U,A)，B⊆A，记

RB={(x,y)∈U×U|∀a∈B,a(x)=a(y)或a(x)=*或a(y)=*}.

显然，RB是自反和对称的，即RB是相似关系，但一般是非传递的[14,31],记:

SB(x)={y∈U|(x,y)∈RB}，x∈U.

SB(x)称为对象x关于RB的相似类，记U/RB={SB(x)|x∈U}.

设(U,A)是一个不完备信息系统，B⊆A，X⊆U，X关于RB的下近似与上近似定义如下[31]：

一个二元组S=(U,C∪{d})称为决策表[5]，又称为决策系统，其中(U,C)是一个信息系统，C称为条件属性集，d∉C称为决策属性，它可以看作映射d:U→Vd.不失一般性，假设Vd={1,2,…,r}，则由决策属性d可确定U上的等价关系：

Rd={(x,y)∈U×U|d(x)=d(y)}.

它将U划分成互不相交的决策类：

U/Rd={D1,D2,…,Dr}，

其中Dj={x∈U|d(x)=j}，j∈Vd={1,2,…,r}.

称决策系统S=(U,C∪{d})是不完备的[32]，若(U,C)是一个不完备信息系统.对于不完备决策系统S=(U,C∪{d})，如果RC⊆Rd，那么称系统S=(U,C∪{d})是协调的，否则称S是不协调的[31].

1.2 广义不完备多尺度信息系统与尺度组合

在一个传统的信息系统(U,A)中，每一个对象x∈U在一个属性a∈A上只取唯一确定的值，这样的一个信息系统称为单尺度信息系统，又称为单粒度标记信息系统[3].若信息系统(U,A)中每一个对象在同一个属性上，根据不同的尺度标记层面可以取不同的值，则(U,A)是一个多尺度信息系统[13]或多粒度标记信息系统[14].Wu等在文献[13]中首次提出了多尺度信息系统的概念.

定义1[13]称S=(U,A)为一个多尺度信息系统或多粒度标记信息系统，其中，U={x1,x2,…,xn}为非空有限对象集，称为论域，A={a1,a2,…,am}为非空有限属性集，且每个属性aj∈A是一个多尺度属性，即对于U中的同一对象，属性aj在不同的尺度上可以取不同的值.

假设所有的属性都有I个相同的等级尺度，则一个多尺度信息系统可以表示为

上述系统中假设不同属性有相同的尺度标记个数，但在实际生活中，各个属性的尺度标记个数可能不一样，针对这种情形，Li等在文献[15]中提出了一种基于不同属性可以取不同尺度标记个数的多尺度信息系统，称之为广义多尺度信息系统[7-8,14].

定义2[7,15]称(U,A)是一个(广义)多尺度信息系统，其中U={x1,x2,…,xn}是一个非空有限对象集，称为论域，A={a1,a2,…,am}是一个非空有限属性集，且每个属性都是多尺度属性.假设属性aj有Ij个尺度标记，则一个多尺度信息系统可以表示为

其中k=1,2,…,Ij-1，x∈U，j=1,2,…,m.

可以验证，(L,⪯)是一个偏序集，即⪯是L上的一个偏序关系(自反、传递和反对称的关系).若进一步定义

则(L,⪯,∧,∨)是一个有界格，显然它是一个完备格，其中最小元是(1,1,…,1)，最大元是(I1,I2,…,Im)，并且

K1⪯K2⟺K1∧K2=K1⟺K1∨K2=K2.

对于B⊆A和K=(l1,l2,…,lm)∈L，记K在属性子集B上的限制为KB，并记LB={KB|K∈L }，即LB是子多尺度信息系统(U,B)的尺度组合全体.

对于B⊆A和K=(l1,l2,…,lm)∈L，记：

RBK={(x,y)∈U×U|∀al∈BKB,al(x)=al(y)或al(x)=*或al(y)=*},

则RBK是不完备多尺度信息系统S在尺度标记层面K=(l1,l2,…,lm)上由属性集B导出的一个相似关系[14]，特别地，对于a∈A，记RaK=R{a}K.令

SBK(x)={y∈U|(x,y)∈RBK}，x∈U.

SBK(x)称为对象x关于BK的相似类[14].记

U/RBK={SBK(x)|x∈U}，

则U/RBK构成了U的一个覆盖.

定义5[14]设U为非空集，A与B是U的2个覆盖，若对于任意A∈A ，存在B∈B使得A⊆B，则称A比B细或B比A 粗，记作A⊆B.

1)K1⪯K2⟹RBK1⊆RBK2；

2)K1⪯K2⟹SBK1(x)⊆SBK2(x),∀x∈U；

3)K1⪯K2⟹U/RBK1⊆U/RBK2；

4)B⊆C⊆A⟹RBK⊆RCK,∀K∈L；

对于X⊆U,B⊆A,K∈L ，X关于RBK的下近似和上近似定义如下:

2 决策多尺度不完备信息系统

本节介绍具有多尺度决策属性的广义多尺度信息系统的相关概念.

这样的一个系统可以表示为

若d被固定在第t个尺度，则S退化为具有单尺度决策属性的广义不完备多尺度决策系统，记

dt+1(x)=ht,t+1(dt(x))，x∈U，

称ht,t+1为决策属性d的信息粒度变换，如图1所示给出由决策属性d所对应的粒度变换关系.

图1 决策属性的信息粒度变换

表1 尺度变换过程

Q1⪯Q2⟺Q1∧Q2=Q1⟺Q1∨Q2=Q2.

Rdt={(x,y)∈U×U|dt(x)=dt(y)}，

则Rdt是U上的一个等价关系，它将U划分成互不相交的决策类：

U/Rdt={[x]dt|x∈U}，

其中 [x]dt={y∈U|dt(x)=dt(y)}={y∈U|(x,y)∈Rdt}.

1)t1≤t2⟹Rdt1⊆Rdt2，

2)t1≤t2⟹[x]dt1⊆[x]dt2，x∈U，

3)t1≤t2⟹U/Rdt1⊆U/Rdt2.

3 决策多尺度不完备信息系统的最优尺度选择

在多尺度决策系统知识获取中，从系统中提取决策规则之前，首先要选择保持某个或者某些量(或者性质)不变的一个合适的尺度(称为最优尺度)，它对应于一个决策表，然后在所选的尺度所对应的决策系统上继续进行保持相应量不变的属性约简，包括系统约简和局部约简，最终得到蕴含在系统中的决策规则.因此，最优尺度选择是多尺度决策系统知识获取的关键问题.Huang等在文献[30]讨论了决策多尺度完备信息系统的最优尺度选择问题，沿着文献[30]的思路，以下讨论决策多尺度不完备信息系统的最优尺度选择问题.

证由SQ2=(U,CK2∪{dt2})是协调的可知，RCK2⊆Rdt2.因为Q1⪯Q2，从而K1⪯K2且t2≤t1，从而分别由定理1和定理4得，RCK1⊆RCK2且Rdt2⊆Rdt1，于是

RCK1⊆RCK2⊆Rdt2⊆Rdt1.

即SQ1=(U,CK1∪{dt1})是协调的.

证由定理5和定义11即得.

1)若SK是协调的，则S是协调的；

2)若存在t∈{1,2,…,N}使得SK关于决策属性dt是协调的，则SK是协调的，从而S也是协调的.

证由定义10、定义11和定理1即得.

1) 若对于任意t′∈{1,2,3,…,N}，满足t′

2) 若对于任意K′∈L，满足KK′，则SK′,t=(U,CK′∪{dt})是不协调的，则称Q=(l1,l2,…,lm,t)为S的一个最优尺度选择.

表2 一个决策多尺度不完备信息系统

L1=(1,1)，L2=(2,1)，L3=(3,1)，L4=(1,2)，L5=(2,2)，L6=(3,2).

图2 尺度选择的格结构

经计算

U/Rd1={{x1,x2},{x3,x4,x5},{x6},{x7},{x8}}，

U/Rd2={{x1,x2,x7},{x3,x4,x5,x6,x8}}.

U/RCL1={{x1,x2},{x3,x4,x5},{x6},{x7},{x8}}，

U/RCL2={{x1,x2},{x3,x4,x5},{x6},{x7},{x8}}，

U/RCL3={{x1,x2},{x3,x4,x5},{x6},{x7,x8}}，

U/RCL4={{x1,x2,x3},{x3,x4,x5},{x3,x6},{x7},{x8}}，

U/RCL5={{x1,x2,x3.x4,x5},{x3,x6},{x7},{x8}}，

U/RCL6={{x1,x2,x3,x4,x5},{x3,x6},{x7,x8}}.

4 结 论

最优尺度选择是多尺度信息系统与多尺度决策系统的知识表示与知识获取的一个关键问题.迄今为止，对于决策属性是多尺度的多尺度信息系统的研究成果还很少，初步研究了决策属性是多尺度的广义不完备多尺度信息系统(简称决策多尺度不完备信息系统)的最优尺度选择问题.引进了决策多尺度不完备信息系统的尺度选择的概念，给出了尺度选择的一些基本性质，定义了协调的决策多尺度不完备信息系统的最优尺度选择概念，并用示例解释了最优尺度选择的计算.这样的一个最优尺度选择所对应的协调决策表主要被用于提取蕴含在系统中具有较好泛化能力的确定性规则集，因此本文成果是进一步从相应数据集进行决策规则提取的基础性工作.今后将进一步研究不协调的决策属性是多尺度的各种多尺度信息系统的最优尺度选择及相应的知识发现问题.