划分序乘积空间基于划分的粒计算模型

徐 怡1,2 姚一豫3

1(计算智能与信号处理教育部重点实验室(安徽大学) 合肥 230039)2(安徽大学计算机科学与技术学院 合肥 230601)3 (里贾纳大学计算机科学系 加拿大里贾纳 S4S0A2)

粒计算(granular computing)通过粒结构实现复杂问题求解. 现有对粒结构中粒化方法的研究,主要是分别基于多层次的粒化方法和基于多视角的粒化方法,没有将多层次粒化方法和多视角粒化方法结合起来.基于多层次的粒化方法得到的粒结构由一个满足线性序关系的多个层构成,即单视角多层次.基于多视角的粒化方法得到的粒结构具有多个视角,但是每个视角仅有一个层.为了更全面地理解和描述问题,从而可以更有效和合理地解决问题,给定一个论域,使用划分作为粒化方法,将多层次的粒化方法和多视角的粒化方法相结合,定义划分序乘积空间.首先,使用论域上的一个划分定义一个层.其次,使用一个嵌套的划分序定义一个多层次,表示为一个视角,层和层之间具有线性序关系.最后,给定多个视角,则定义了多个线性序关系,基于多个线性序关系的乘积,定义划分序乘积空间.划分序乘积空间给出了一种基于划分的粒计算模型.通过实例说明了划分序乘积空间在实际应用中的优越性.

关键词 粒结构;粒化;多层次;多视角;乘积

粒计算(granular computing)是用系统的、结构化的理解和方法来解决复杂问题的新理论、新技术和新方法[1-5],被用于很多领域[6-10].粒计算的基本思想是在问题求解过程中通过构造信息粒,形成粒结构,基于粒结构从不同角度、不同层次上对现实问题进行描述、推理与求解[2,11-12].对复杂问题的全面理解通常是多视角的,从每一个视角着眼的理解又是多层次的,它的结果表现为一个多视角、多层次的粒结构.多层次强调对问题多个粒度层次的理解和描述.根据具体问题,不同的层次体现为不同的尺度、不同的复杂度、不同的抽象、不同的控制、不同的细节.多视角强调从多个不同的角度对问题进行描述和处理.从人类问题求解的角度看,对于同一个问题,不同的人会有不同的观点.人脑对于同一个问题有着不同的理解和处理方式.因此单视角对问题理解具有一定的局限性,需要多视角从全局的角度理解问题.多视角有2个优点:1)通过对问题的多样性描述,我们可以寻找解决问题的可能存在的最优化方法;2)多视角的组合可以给出任何一个单视角得不到的结果.粒计算的核心任务之一是通过信息粒化,构建多层次、多视角的粒结构[13].

粒、层和多层次是粒结构中的3个基本要素.粒是整体的一部分,可视为我们当前感兴趣的焦点,或者用于描述和表示的元素、概念、观念等,例如论域的子集、问题的子问题、系统的子系统等.一个层由一簇粒构成,层是粒化的结果.粒化是产生具有不同粒度层的过程,是建立粒结构的基础.粒化的程度通过粒度来刻画,表示层对问题观察或描述的抽象程度.多个层按照线性序关系组织起来构成了多层次.

对于不同的实际问题,信息粒化的方法多种多样.划分是一种常用的信息粒化方法.基于划分,姚一豫[13]提出了基于划分的粒计算模型.Pawlak[14]提出的粗糙集模型,张铃和张钹[15-16]提出的商空间模型都是基于划分的粒计算模型.但是现有对粒化方法的研究,主要是分别基于多层次的粒化方法和基于多视角的粒化方法,没有将多层次粒化方法和多视角粒化方法结合起来.基于多层次的粒化方法,粒化结果是一个多层次,多个层之间具有线性序关系.基于多视角的粒化方法,粒化结果是多个视角,但是每个视角仅有一个层.所以在本文中,为了更全面地理解和描述问题,从而可以更有效和合理地解决问题,给定一个论域,我们使用划分作为粒化方法,将多层次的粒化方法和多视角的粒化方法相结合,定义划分序乘积空间.首先,使用论域上的一个划分定义一个层.其次,使用一个嵌套的划分序定义一个多层次,表示为一个视角,层和层之间具有线性序关系.最后,给定多个视角,则定义了多个线性序关系,基于多个线性序关系的乘积,定义划分序乘积空间.划分序乘积空间给出了一种基于划分的粒计算模型.

在多层次粒化方法中,通常基于嵌套的属性序列或者嵌套的属性值序列来构建嵌套的划分序,即多层次.Marek和Rasiowa[17]基于递减的等价关系序列研究了集合的渐进近似.Pomykala[18]使用容差关系序列构建多层次.姚一豫[19]提出基于一个嵌套的等价关系序列诱导出多层次粒结构和层次粗糙集近似.粗糙集的属性约简,也是从一个嵌套的属性序列中找出一个最小的属性子集,使其分类能力和属性全集的分类能力相同,本质上也是一种多层次粒化方法[14,20].Hong等人[21]基于粗糙集,提出了从具有层次属性值的数据中学习多层次确定规则和可能规则的算法.Feng等人[22]研究了具有层次属性值的层次信息系统,提出了从不同的属性概念层自上而下的策略挖掘层次决策规则.Wu等人[23-24]从粒计算的角度研究了多尺度决策表,每个对象在每个属性下的属性值表示为具有不同粒度的多个尺度值.Ye等人[25]基于属性概念层次树,提出了多层次粗糙集模型.基于多层次粒结构,姚一豫[26]提出的序贯三支决策是一种有效且快速的决策策略.

基于多视角的粒化方法主要有以下研究工作.Qian等人[27-28]用一簇等价关系取代一个等价关系对论域进行分类和近似未知概念,提出了多粒度粗糙集模型.由于这一簇等价关系之间不存在线性序关系,所以这些等价关系不能构成多层次,因此多粒度粗糙集模型本质上是基于多视角的粒化方法,每个粒度对应一个视角.姚一豫等人[6]对已有的多粒度研究进行分类比较,提出了多粒度空间中粗糙集近似的统一框架,讨论了4种不同类型的粗糙集近似.Xu等人[29]基于支持特征函数和信息层,研究了广义多粒度粗糙集的上下近似集,给出了如何在广义多粒度粗糙集中选择最优粒度层的方法.利用多源近似空间表示多粒度空间,Khan和Banerjee[30]提出了强和弱上下近似集的概念.Sang等人[31]提出了基于多源决策系统的决策粗糙集模型,每个信息源对应问题的一个视角.Chen等人[32]基于多种形式的数据操作,提出了智能数据分析的多视角框架.

1 划分和划分序

划分是一种常用的信息粒化方法,划分通常可以由等价关系诱导得出.本节介绍和划分相关的基本概念[1-5].

定义1. 划分.给定一个论域U,是对象的非空有限集合,U上的一个非空子集簇π={A1,A2,…,Ak}称为U上的划分,若AiAj=∅(ij),并且其中每个子集Ai称为划分π的一个块.

定义2. 细化.给定一个论域Uπ1π2是定义在U上的2个划分,π1={A1,A2,…,Ak},π2={B1,B2,…,Bt},如果∀Biπ2,∃Ajπ1,满足BiAj,则称π2π1细,或反之π1π2粗,记为π2π1.如果π2π1并且π2π1,则称π2π1真细,记为π2π1.

定义3. 划分序.给定一个论域UP是定义在U上的一簇划分,P={π1,π2,…,πn},如果其满足πnπn-1⪯…⪯π1,则称P为一个嵌套的划分序.

划分可以由等价关系诱导得出.等价关系定义如下:

定义4. 等价关系.给定一个论域UEU×UU上的一个等价关系,如果E是自反、对称且传递的.其中U×U表示UU的笛卡儿积.[x]E={yU|(x,y)∈E}表示对象xU在等价关系E下的等价类,简记为[x].

定理1. 给定一个论域UEU上的一个等价关系,则E可以诱导出U上的一个划分π,记为π=UE={[x]E|xU}.

定理2. 给定一个论域UE1E2是定义在U上的2个等价关系,由E1E2诱导出的2个划分记为π1π2,其中,π1=UE1={[x]E1|xU},π2=UE2={[x]E2|xU}.如果E2E1,则π2π1,且∀xU,[x]E2⊆[x]E1.

定理2说明等价关系之间的包含关系对应于划分之间的细化关系,基于一个细的等价关系产生的等价类比基于一个粗的等价关系产生的等价类小.

定义5. 等价关系序.给定一个论域UR是定义在U上的一簇等价关系,R={E1,E2,…,En},如果其满足EnEn-1⊆…⊆E1,则称R为一个嵌套的等价关系序.

定理3. 给定一个论域UR是定义在U上的一个嵌套的等价关系序,R={E1,E2,…,En},满足EnEn-1⊆…⊆E1,则由R可以诱导出U上的一个嵌套的划分序P={π1,π2,…,πn},满足πnπn-1⪯…⪯π1.

从定理3可以看出,一个嵌套的等价关系序可以诱导出一个嵌套的划分序.

注意:由于划分和等价关系是一一对应的,所以我们在本文中不加区分的使用这2个概念.

2 基于划分序乘积空间的粒计算模型

信息粒化是建立粒结构的基础.但是现有对粒化方法的研究,主要是分别基于多层次的粒化方法和基于多视角的粒化方法,没有将多层次粒化方法和多视角粒化方法结合起来.所以在本文中,为了更全面地理解和描述问题,从而可以更有效和合理地解决问题,给定一个论域,我们使用划分作为粒化方法,将多层次的粒化方法和多视角的粒化方法相结合,定义划分序乘积空间.划分序乘积空间给出一种基于划分的粒计算模型.

2.1 粒结构的3要素

粒、层和多层次是粒结构的3个基本要素.粒是整体的一部分,可视为我们当前感兴趣的焦点,或者用于描述和表示的元素、概念、观念等.一个层由一簇粒构成,每个层通过具有相似粒度的一簇粒对问题进行理解和表示.多个层按照线性序关系组织起来构成了多层次,即视角.在较粗的粒度层,我们通过忽略一些细节,对问题的表示较抽象和简洁,因此对问题的求解速度较快,但是精度较低.在较细的粒度层,我们对问题的表示较具体和详细,因此对问题的求解速度较慢,但是精度较高.

在粒结构的3要素中,层起到承上启下的作用.层是粒化的结果.对于不同的实际问题,粒化的方法多种多样.常用的粒化方法有基于划分或等价关系的粒化方法、基于覆盖的粒化方法、基于二元关系的粒化方法、基于模糊划分的粒化方法等.

但是现有的这些粒化方法,都是从多层次的角度和多视角的角度分别进行粒化,即对多层次的粒化方法和多视角的粒化方法分别进行研究,没有将二者结合起来.基于多层次的粒化方法,通常使用一个多层次来描述和解决问题,每个层对应论域的一个粒化结果,多个层之间具有线性序关系.基于多视角的粒化方法,通常使用多个视角来描述和解决问题,但是每个视角仅有一个层.因此导致现有的粒结构不能从多层次和多角度2个方面更全面系统地理解和描述问题,从而不能有效合理地解决问题.

2.2 基于划分的粒结构

在2.1节中我们给出了粒结构的一般描述,指出粒、层和多层次是粒结构的3个基本要素,粒化是建立粒结构的基础.但是没有考虑粒化的具体实现方法,因此粒、层和多层次缺乏具体的意义和解释.

如第1节所述,给定一个论域,划分和等价关系可以作为粒化方法对论域进行粒化.一个对论域的划分对应一个层,一个嵌套的划分序对应一个多层次,层和层之间的线性序关系可以解释为嵌套的划分序之间的细化关系.

因此,本节采用划分作为粒化方法,定义基于划分的粒结构.给出粒结构中构造粒、层和多层次的具体实现方法,从而赋予粒、层和多层次具体的意义和解释.

在基于划分的粒结构中,其3个要素具体描述为:

1) 粒.一个划分块(等价类)表示一个粒,记为[x],xU.

2) 层.一个对论域的划分对应一个层,记为π={[x]|xU}.

3) 多层次.一个嵌套的划分序(一个嵌套的等价关系序),对应一个多层次,表示一个视角,记为P={π1,π2,…,πn}.

一般粒结构中的3要素和基于划分的粒结构中的3要素之间的对应关系如图1所示:

Fig. 1 Three elements of granular structure and partition based granular structure
图1 粒结构和基于划分的粒结构中的3要素

在基于划分的粒结构中,多层次对应的线性序关系是基于划分定义的细化关系,或者是基于等价关系定义的集合包含关系.

2.3 划分序乘积空间

为了更全面地理解和描述问题,从而可以更有效和合理地解决问题,给定一个论域,我们使用划分作为粒化方法,将多层次的粒化方法和多视角的粒化方法相结合,定义划分序乘积空间.

首先,使用论域上的一个划分定义一个层.其次,使用一个嵌套的划分序定义一个多层次,表示为一个视角,层和层之间具有线性序关系.最后,给定多个视角,则定义了多个线性序关系,基于多个线性序关系的乘积,定义划分序乘积空间.划分序乘积空间给出了一种基于划分的粒计算模型.

为了简单起见,我们首先定义包含2个视角的划分序乘积空间,然后再定义包含多个视角的划分序乘积空间.

定义6. 2个视角的划分序乘积空间.给定一个论域U,假设P1P2是定义在U上的2个嵌套的划分序,满足⪯…⪯⪯…⪯定的视角V1V2分别记为全序集合(P1,⪯)和(P2,⪯).假设对于每个视角Vi,其层次数为ni,第i个视角的第j个层次表示为由2个视角构成的划分序乘积空间POPS2定义为(P1,⪯)和(P2,⪯)的乘积,POPS2=(P1×P2,⪯P),其中集合P1P2的笛卡儿积的计算公式为:偏序关系⪯P定义为:∀当且仅当

在定义6中,2个嵌套的划分序P1P2,定义了2个视角V1V2,我们将其表示为2个全序集,全序集中的元素是层,全序关系是层和层之间的粗化细化关系.2个视角的划分序乘积,定义了包含2个视角的划分序乘积空间.

定义7. 多个视角的划分序乘积空间.给定一个论域U,假设Pi是定义在U上的一个嵌套的划分序,满足⪯…⪯则由Pi确定的视角Vi记为全序集合(Pi,⪯).假设对于每个视角Vi,其层次数为ni,第i个视角的第j个层次表示为m个视角构成的划分序乘积空间POPSm定义为(Pi,⪯)的乘积,P),其中集合P1,P2……Pm的笛卡儿积的计算公式为:偏序关系⪯P定义为:∀当且仅当∀通常,可以将P)简记为POPSm=(×Pi,⪯P).

POPSmm个视角的乘积构成,不同视角提供了对问题不同角度的理解和描述.每个视角又可以从多个粒度层次上对问题进行理解和描述.因此划分序乘积空间提供了对问题多层次多视角的理解和描述.

定理4. 划分序乘积空间POPSm=(×Pi,⪯P)是一个格结构.

证明. 基于定义7,⪯P是一个偏序关系,其满足自反性、反对称性和传递性.因此,POPSm是一个偏序集.为了进一步证明POPSm是一个格结构,我们只需要证明对于POPSm中任意2个元素,它们有上确界和下确界.

故∀jm2nm.假定minj1=min{j11,j12},minj2=min{j21,j22},minjm=min{jm1,jm2},maxj1=max{j11,j12},maxj2=max{j21,j22},maxjm=max{jm1,jm2},则的上确界,的下确界.因此POPSm是一个格结构,定理1成立.

证毕.

在划分序乘积空间中,其问题求解空间为一个格结构,格中的每一个节点对应一个问题求解层,定义如下:

定义8. 问题求解层.给定一个由m个视角Vi构成的划分序乘积空间POPSm=(×Pi,⪯P),∀称为一个问题求解层.

每个问题求解层,一方面通过多视角给出了对问题的多样性描述,另一方面基于每个视角,我们可以得到一个问题求解结果.因此,基于每个问题求解层,在实际求解问题时有3种处理策略:

1) 首先融合多个视角对问题的描述,然后基于融合后的描述结果进行最终的问题求解,我们称之为多视角问题描述的融合.

2) 首先分别基于单个视角对问题进行求解,然后融合多个视角对问题求解的结果进行最终的问题求解,我们称之为多视角问题求解结果的融合.

3) 在多视角问题求解过程中,同时对问题描述和求解结果进行融合,我们称之为多视角问题求解过程的融合.

例如在划分序乘积空间中,我们可以对每一个视角从顶层到底层按照粒度递减的顺序来寻找一个合适的层进行问题求解,然后融合多个视角下各个层的求解结果进行最终的问题求解,即为多视角问题求解结果的融合.在多粒度粗糙集模型中,Qian等人[27-28]提出了基于求同存异的乐观融合策略和求同排异的悲观融合策略,张明等人[33-34]提出了基于可变多粒度的融合策略,都属于多视角问题求解结果的融合.

注意:当划分序乘积空间中视角的个数为1时,划分序乘积空间退化为现有的多层次的粒结构.当划分序乘积空间中每个视角的层数为1时,划分序乘积空间退化为现有的多视角的粒结构.

划分序乘积空间采用划分作为粒化方法.当我们采用其他粒化方法时,可以得到各种类型的序乘积空间,如覆盖序乘积空间、邻域序乘积空间、模糊序乘积空间等.

2.4

本节中我们通过一个例子来说明划分序乘积空间在实际应用中的优越性.

例1. 表1从3个视角给出了8位病人的描述信息,论域U={x1,x2,x3,x4,x5,x6,x7,x8}.为了简化问题的讨论,每个视角仅采用一个属性来描述.3个视角分别为血压视角V1、年龄视角V2、血糖视角V3.最终的决策为是否患有心脏病.在每一个视角Vi下,基于等价关系,利用嵌套的属性值序列来构建嵌套的划分序,从而形成视角Vi的全序集合(Pi,⪯),第i个视角的第j层定义为例如,对于年龄视角,其属性值有3个粒度b1b2b3,由粗到细分别为{≤50,>50},{18~30,31~50,51~100},{18~30,31~40,41~50,51~65,66~100}.基于这3个属性值粒度,可以形成对论域的3个划分层次.对于血压视角,其属性值有2个粒度,用a1a2表示.对于血糖视角,其属性值有2个粒度,用c1c2表示.表1中N(normal)表示正常,AN(abnormal)表示不正常.

Table 1 Information of Patients
表1 病人信息表

UBlood Pressure (V1)Age (V2)Blood Glucose (V3)a1a2b1b2b3c1c2HeartDiseasex1N90-120≤5018-3018-30N<6Nox2N90-120≤5018-3018-30AN>7.5Yesx3AN>120≤5031-5031-40AN6-7.5Yesx4N90-120≤5031-5031-40AN>7.5Nox5AN>120≤5031-5041-50N<6Yesx6AN>120>5051-10051-65AN>7.5Yesx7AN<90>5051-10066-100AN6-7.5Yesx8AN<90>5051-10066-100N<6No

Note: N means normal; AN means abnormal.

表1中,视角V1有2层,记为视角V2有3层,记为视角V3有2层,记为对于每一个视角Vi,(Pi,⪯)是Vi的全序集合,1≤i≤3,则这3个视角构成划分序乘积空间POPSm=(×Pi,⪯P).

对于V1,其2个层描述为

对于V2,其3个层描述为

对于V3,其2个层描述为

我们可以看出,视角V1中的层满足:对应的等价类序列满足:视角V2中的层满足:对应的等价类序列满足:视角V3中的层满足:对应的等价类序列满足:也就是说,对于每个视角,从顶层到底层,粒逐渐变小,粒度逐渐变细.

由3个视角构成的划分序乘积空间POPSm=(×Pi,⪯P)构成的格结构如图2所示:

Fig. 2 Partition order product space with three views
图2 由3个视角构成的划分序乘积空间

通过图2可以看出,划分序乘积空间同时考虑了多层次的粒化方法和多视角的粒化方法,共有12个问题求解层.因此,医生在实际诊断病人时,不仅可以从多个层次上处理问题,还可以从多个角度处理问题,根据实际问题求解的需要,可以在不同视角和同一视角的不同层次之间灵活选择和变换,从而使得对疾病的诊断更加有效和合理.在实际问题求解中,如何在划分序乘积空间中找到合适的问题求解层,将是一个值得研究的方向.

3

粒计算研究有效的粒结构用于问题求解和信息处理,多层次和多视角是其2个重要的粒化原则.但是现有对粒结构中粒化方法的研究,主要是分别基于多层次的粒化方法和基于多视角的粒化方法,没有将两者结合起来.所以在本文中,为了更全面地理解和描述问题,从而可以更有效和合理地解决问题,给定一个论域,我们使用划分作为粒化方法,将多层次的粒化方法和多视角的粒化方法相结合,定义划分序乘积空间.首先,使用论域上的一个划分定义一个层.其次,使用一个嵌套的划分序定义一个多层次,表示为一个视角,层和层之间具有线性序关系.最后,给定多个视角,则定义了多个线性序关系,基于多个线性序关系的乘积,定义划分序乘积空间.证明了划分序乘积空间是一个格结构.已有的基于多层次的粒化方法得到的粒结构和基于多视角的粒化方法得到的粒结构是划分序乘积空间的特殊情况.

划分序乘积空间给出了一种新的粒计算模型,在此基础上,我们可以研究基于划分序乘积空间的三支决策模型、基于划分序乘积空间的粗糙集模型、基于划分序乘积空间的概念格模型等,从而给出各种多层次多视角的问题求解策略和方法.在以后的工作中,我们将进一步研究划分序乘积空间的拓扑结构和相关性质.

参考文献

[1]Hobbs J R. Granularity[C] //Proc of the 9th Int Joint Conf on Artificial Intelligence (IJCAI). San Francisco: Morgan Kaufmann, 1985: 542-545

[2]Bargiela A, Pedrycz W. Toward a theory of granular computing for human-centered information processing[J]. IEEE Transactions on Fuzzy Systems, 2008, 16(2): 320-330

[3]Bargiela A, Pedrycz W. Human-Centric Information Processing Through Granular Modeling[M]. Berlin: Springer, 2009: 841-846

[4]Keet C M. A taxonomy of types of granularity[C] //Proc of IEEE Int Conf on Granular Computing. Piscataway, NJ: IEEE, 2006: 106-111

[5]Yao Yiyu. A triarchic theory of granular computing[J]. Granular Computing, 2016, 1(2): 145-157

[6]Yao Yiyu, She Yanhong. Rough set models in multigranula-tion spaces[J]. Information Sciences, 2016, 327(C): 40-56

[7]Li Jinhai, Huang Chenchen, Qi Jianjun, et al. Three-way cognitive concept learning via multi-granularity[J]. Information Sciences, 2017, 378(1): 244-263

[8]Savchenko A V. Fast multi-class recognition of piecewise regular objects based on sequential three-way decisions and granular computing[J]. Knowledge-Based Systems, 2016, 91: 252-262

[9]Li Jinhai, Mei Changlin, Xu Weihua, et al. Concept learning via granular computing: A cognitive viewpoint[J]. Information Sciences, 2015, 298(1): 447-467

[10]Liang Jiye, Wang Feng, Dang Chuangyin, et al. An efficient rough feature selection algorithm with a multi-granulation view[J]. International Journal of Approximate Reasoning, 2012, 53(6): 912-926

[11]Yao Jingtao. Novel Developments in Granular Computing: Applications for Advanced Human Reasoning and Soft Computation[M]. Hershey, PA: IGI Global, 2010: 1-15

[12]Yao Yiyu. Integrative levels of granularity[M] //Human-Centric Information Processing Through Granular Modelling. Berlin: Springer, 2009: 31-47

[13]Yao Yiyu. A partition model of granular computing[M] //Transactions on Rough Sets I. Berlin: Springer, 2004: 232-253

[14]Pawlak Z. Rough sets[J]. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356

[15]Zhang Ling, Zhang Bo. Problem Solving Theory and Its Application: Theory of Quotient Granularity Computing and Its Application[M]. Beijing: Tsinghua University Press, 2007 (in Chinese)

(张铃, 张钹. 问题求解理论及应用: 商空间粒度计算理论及其应用[M]. 北京: 清华大学出版社, 2007)

[16]Zhang Yanping, Yao Yiyu, Miao Duoqian, et al. Review and Development of Granular Computing, Quotient Space and Three-way Decision[M]. Beijing: Science Press, 2017 (in Chinese)

(张燕平, 姚一豫, 苗夺谦, 等. 粒计算、商空间及三支决策的回顾与发展[M]. 北京: 科学出版社, 2017)

[17]Marek W, Rasiowa H. Gradual approximating sets by means of equivalence relations[J]. Bulletin of Polish Academy of Sciences Mathematics, 1987, 35(1): 233-238

[18]Pomykala J A. A remark on the paper by Rasiowa H and Marek W:“Gradual approximating sets by means of equivalence relations”[J]. Bulletin of Polish Academy of Sciences Mathematics, 1988, 36(7): 509-512

[19]Yao Yiyu. Information granulation and rough set approxima-tion[J]. International Journal of Intelligent Systems, 2001, 16(1): 87-104

[20]Jensen R, Tuson A, Shen Qiang. Finding rough and fuzzy-rough set reducts with SAT[J]. Information Sciences, 2014, 255: 100-120

[21]Hong Tzungpei, Lin Chune, Lin Jiannhorng, et al. Learning cross-level certain and possible rules by rough sets[J]. Expert Systems with Applications, 2008, 34(3): 1698-1706

[22]Feng Qinrong, Miao Duoqian, Cheng Yi. Hierarchical decision rules mining[J]. Expert Systems with Applications, 2010, 37(3): 2081-2091

[23]Wu Weizhi, Leung Y. Theory and applications of granular labelled partitions in multi-scale decision tables[J]. Information Sciences, 2011, 181(18): 3878-3897

[24]Wu Weizhi, Leung Y. Optimal scale selection for multi-scale decision tables[J]. International Journal of Approximate Reasoning, 2013, 54(8): 1107-1129

[25]Ye Mingquan, Wu Xindong, Hu Xuegang, et al. Multi-level rough set reduction for decision rule mining[J]. Applied Intelligence, 2013, 39(3): 642-658

[26]Yao Yiyu. Granular computing and sequential three-way decisions[C] //Proc of the 8th Int Conf on Rough Sets and Knowledge Technology. Berlin: Springer, 2013: 16-27

[27]Qian Yuhua, Liang Jiye, Yao Yiyu, et al. MGRS: A multi-granulation rough set[J]. Information Sciences, 2010, 180(6): 949-970

[28]Qian Yuhua, Li Shunyong, Liang Jiye, et al. Pessimistic rough set based decisions: A multigranulation fusion strategy[J]. Information Sciences, 2014, 264(6): 196-210

[29]Xu Weihua, Li Wentao, Zhang Xiantao. Generalized multigranulation rough sets and optimal granularity selection[J]. Granular Computing, 2017, 2(4): 271-288

[30]Khan M A, Banerjee M. Formal reasoning with rough sets in multiple-source approximation systems[J]. International Journal of Approximate Reasoning, 2008, 49(2): 466-477

[31]Sang Binbin, Guo Yanting, Shi Derong, et al. Decision-theoretic rough set model of multi-source decision systems[J]. International Journal of Machine Learning and Cybernetics, 2018, 9(11): 1941-1954

[32]Chen Yaohua, Yao Yiyu. A multiview approach for intelligent data analysis based on data operators[J]. Information Sciences, 2008, 178(1): 1-20

[33]Zhang Ming, Tang Zhenmin, Xu Weiyan, et al. Variable multigranulation rough set model[J]. Pattern Recognition and Artificial Intelligence, 2012, 25(4): 709-720 (in Chinese)

(张明, 唐振民, 徐维艳, 等. 可变多粒度粗糙集模型[J]. 模式识别与人工智能, 2012, 25(4): 709-720)

[34]Zhang Ming, Xu Weiyan, Yang Xibei, et al. Incomplete variable multigranulation rough sets decision[J]. Applied Mathematics & Information Sciences, 2014, 8(3): 1159-1166

Partition Order Product Space: Partition Based Granular Computing Model

Xu Yi1,2 and Yao Yiyu3

1(Key Laboratory of Intelligent Computing and Signal Processing(Anhui University), Ministry of Education, Hefei 230039)2(School of Computer Science and Technology, Anhui University, Hefei 230601)3(Department of Computer Science, University of Regina, Regina, Canada S4S0A2)

Abstract Granular computing solves complex problem based on granular structure. The existing studies on the granulation methods in granular structures mainly focus on multilevel granulation methods and multiview granulation methods respectively, without combining multilevel granulation methods and multiview granulation methods. Granular structure based on multilevel granulation methods is composed of a linearly ordered family of levels, which only provides one view with multiple levels. Granular structure based on multiview granulation methods provides multiple views, but each view only consists of one level. In order to understand and describe problem in a more comprehensive way, and then solve the problem more effectively and reasonably, given a universe, we take partition as the granulation method. Combining multilevel granulation methods with multiview granulation methods, we propose partition order product space. Firstly, using a partition on the universe to define a level. Secondly, using a nested sequence of partitions to define a hierarchy, which represents a view with linearly ordered relation. Finally, given a number of views determining a number of linearly ordered relations, based on the product of multiple linearly ordered relations, we propose partition order product space, which gives a granular computing model based on partition. Example demonstrates the superiority of partition order product space in real application.

Key words granular structure; granulation; multilevel; multiview; product

(xuyi1023@126.com)

中图法分类号 TP18

收稿日期2018-04-30;

修回日期:2018-07-23

基金项目国家自然科学基金项目(61402005);安徽省自然科学基金项目(1308085QF114);安徽省高等学校省级自然科学基金项目(KJ2013A015);安徽大学计算智能与信号处理教育部重点实验室课题项目(2014)

This work was supported by the National Natural Science Foundation of China (61402005), the Natural Science Foundation of Anhui Province of China (1308085QF114), the Higher Education Natural Science Foundation of Anhui Province of China (KJ2013A015), and the Open Foundation of Key Laboratory of Intelligent Computing and Signal Processing at Anhui University of Ministry of Education of China (2014).

Xu Yi, born in 1981. PhD. Associate professor. Member of CCF. Her main research interests include intelligent information processing, granular computing and three way decision.

Yao Yiyu, PhD. Professor. His main research interests include three way decision and granular computing.