不完备信息系统中多粒度概率粗糙集的规则提取
Rule Extraction of Multi-Granularity Probabilistic Rough Sets in Incomplete Information Systems
摘要: 本文基于不完备多粒度信息系统,主要讨论了概率粗糙集的上下近似和精度的变化,以及基于优劣关系的规则提取。首先,对不完备信息系统中多粒度粗糙集关于乐观(悲观)的上下近似进行了简单的介绍。其次,基于相似关系优势关系和劣势关系,对不完备信息系统中的多粒度概率粗糙集从乐观(悲观)的角度对其上下近似进行了讨论,得出了近似精度随α, β的变化而变化的规律。最后,讨论了基于优劣关系随参数γ变化的概率粗糙集的规则提取。
Abstract: Based on incomplete multi-granularity information system, this paper mainly discusses the upper-lower approximation and approximate accuracy of probabilistic rough sets, and the rules extraction based on dominance-disadvantage relationship. Firstly, the optimistic (pessimistic) multi-granularity rough approximation in incomplete multi-granularity information systems is introduced. Secondly, it discusses the optimistic (pessimistic) multi-granularity lower-upper approximation of probabilistic rough sets based on the similar relation, dominance relation and disadvantage relation respectively, the rule of approximate accuracy variation with α, β is given. Finally, it discusses rule extraction of probabilistic rough sets based on the variation of dominance and disadvantage relationship with parameter γ.
文章引用:石孝安, 傅丽. 不完备信息系统中多粒度概率粗糙集的规则提取[J]. 应用数学进展, 2020, 9(8): 1298-1308. https://doi.org/10.12677/AAM.2020.98152

1. 引言

粗糙集是1982年英国数学家Pawlak提出的理论 [1],该理论是一种处理不确定的,不精确信息的数学工具。自提出以来,得到了很多学者的关注和研究,并已应用到了决策分析模式识别数据挖掘等领域 [2] [3] [4]。

经典粗糙集模型是一种可以被要求利用信息是完全性的一种模型,却忽略了随机,文献 [5] 提出了多粒度概率粗糙集模型集,解决了经典的粗糙集中下近似过于严格和上近似过于宽松的问题。但是,却没有考虑到信息系统缺失属性值的情况。文献 [6],在不完备的决策信息系统中定义了粒度的属性缺失,粒度组合重要度。文献 [7],根据乐观和悲观的角度,对贝叶斯决策进行了讨论并对决策信息系统进行了约简的讨论。文献 [8],对经典的不完备信息系统进行了讨论和约简。文献 [9],对多粒度粗糙集的粒度约简算法进行了讨论。文献 [10] [11],分别从容差关系模型拓展领域等角度对不完备信息系统进行了研究。

本文是基于不完备信息系统进行的讨论,主要讨论了概率粗糙集的优劣关系及规则提取。在本文当中,第二部分介绍了相关概念;第三部分我们基于相似关系,对多粒度概率粗糙集进行了讨论;第四部分基于劣势关系和优势关系分别从乐观和悲观的角度对不完备的多粒度概率粗糙集进行了讨论,并给出了随 α , β 的变化规律与精度变化的规律。第五部分,讨论了基于优劣关系随参数 γ 变化的概率粗糙集的规则提取。

2. 相关概念

定义1 [5]:设 S = ( U , C D , V , f ) 为一个决策信息系统,其中U为论域; A = C D 为有限属性集合;C为条件属性集合,D为决策属性集合 V = a A V a V a 为属性 a A 的值域; f : U × A V 是一个信息函数, a A , x U , f ( x , a ) V a 。在缺失部分条件属性值的状况下(用*表示),被称为不完备的决策信息系统;否则,S是一个完备决策信息系统。

定义2 [5]:设 S = ( U , C D , V , f ) 为一个不完备决策信息系统, A = { A 1 , A 2 , , A m } 是C的m个属性的子集族。 X U ,X关于A的

(1) 乐观多粒度上(下)近似定义:

i m A i o ( X ) _ = { x : T Λ 1 ( x ) X T Λ 2 ( x ) X T Λ m ( x ) X , x U }

i = 1 m A i o ( X ) ¯ = ~ ( i = 1 m A i o ( ~ X ) )

(2) 悲观多粒度下(上)近似分别定义:

i = 0 m A i p ( X ) _ = { x : T A 1 ( x ) X T A 2 ( x ) X T A m ( x ) X , x U }

i = 1 m A i p ( X ) ¯ = ~ ( i = 1 m A i p ( ~ X ) _ )

定义3 [8]:设 I = ( U , A , F ) 是一个不完备信息系统,称 R B 为其相似关系,如果满足

R B = { ( x , y ) U U | a B , a ( x ) = a ( y ) a ( x ) = * a ( y ) = * }

相似关系 R B 是自反而且满足对称性,但通常不满足传递性。记作 S B ( x ) = { y U | ( x , y ) R B } ,则 S B ( x ) 被称为x关于 R B 的相似类;记 U / R B 是构成U的一个划分。

定义4 [8]:设 I = ( U , A , F ) 是不完备信息系统

(1) 称 R A 为优势关系,当满足

R A = { ( y , x ) U U | V a A , f a ( y ) f a ( x ) f a ( x ) = * f a ( y ) = * }

时,可以利用优势类关系归类: U / R A = { [ x ] A | x U } ,其中: [ x ] = { y U | ( y , x ) R A } [ x ] = { y U | ( x , y ) R A } [ x ] A 表示在属性A上优于x的优势类, [ x ] A 表示在属性A上劣于x的劣势类。

(2) 称 R A 为劣势关系,当满足

R A = { ( y , x ) U U | V a A , f a ( y ) f a ( x ) f a ( x ) = * f a ( y ) = * }

时,可以利用劣势类关系归类: U / R A = { [ x ] A | x U } ,其中: [ x ] = { y U | ( y , x ) R A } [ x ] = { y U | ( x , y ) R A } [ x ] A 表示在属性A上优于x的优势类, [ x ] A 表示在属性A上劣于x的劣势类。

注:(1) 下文中的所有讨论基于不完备信息系统进行讨论,小标题中不在体现。

(2) 根据定义2中悲观多粒度的上下近似,在下面的文章中,可类似于乐观多粒度概率粗糙集的上下近似的讨论方式得出其相关定理和性质,本文不再给出。

3. 基于相似关系的多粒度概率粗糙集模型

定义5:设 M I S = U , A T , V , f 为一个不完备多粒度信息系统, x U X U 0 β 0.5 < α 1

则X在相似关系 R B 上依参数 α , β 的乐观(悲观)多粒度概率粗糙集下近似 i = 1 m A i o _ α ( X ) 和上近似 i = 1 m A i o β ¯ ( X )

分别定义:

i = 1 m A i o _ α ( X ) = { x U : p ( X | [ x ] A 1 S B ) α P ( X | [ x ] A 2 S B ) α P ( X | [ x ] A m S B ) α }

i = 1 m A i o β ¯ ( X ) = ~ i = 1 m A i o _ 1 β ( ~ X )

通过定义5,可以得到在不完备系统中,乐观多粒度概率粗糙集的边界域集合:

B n d i = 1 m A i ( α , β ) o = i = 1 m A i o β ¯ ( X ) i = 1 m A i o _ α ( X )

二元组 i = 1 m A i o _ α ( X ) , i = 1 m A i o β ¯ ( X ) 称作是X基于相似关系 R B 关于粒度 A i ( i = 1 , 2 , , m ) 的乐观多粒度概率粗糙集。

定理3.1:设 M I S = U , A T , V , f 为一个不完备的多粒度信息系统, x U X U 0 β 0.5 < α 1 A T = { A 1 , A 2 , , A m }

i = 1 m A i o β ¯ ( X ) = { x U : p ( X | [ x ] A 1 S B ) > β P ( X | [ x ] A 2 S B ) > β P ( X | [ x ] A m S B ) > β }

证明: i = 1 m A i o β ¯ ( X ) = ~ i = 1 m A i o _ 1 β ( ~ X ) = { x U : p ( ~ X | [ x ] A 1 S B ) 1 β P ( ~ X | [ x ] A 2 S B ) 1 β P ( ~ X | [ x ] A m S B ) 1 β } = { x U : 1 p ( X | [ x ] A 1 S B ) 1 β 1 P ( X | [ x ] A 2 S B ) 1 β 1 P ( X | [ x ] A m S B ) 1 β } = { x U : | ~ X [ x ] A 1 S B | | [ x ] A 1 S B | 1 β | ~ X [ x ] A 2 S B | | [ x ] A 2 S B | 1 β | ~ X [ x ] A m S B | | [ x ] A m S B | 1 β } = { x U : 1 | X [ x ] A 1 S B | | [ x ] A 1 S B | 1 β 1 | X [ x ] A 2 S B | | [ x ] A 2 S B | 1 β 1 | X [ x ] A m S B | | [ x ] A m S B | 1 β } = { x U : p ( X | [ x ] A 1 S B ) > β P ( X | [ x ] A 2 S B ) > β P ( X | [ x ] A m S B ) > β }

定义6:设 M I S = U , A T , V , f 为一个不完备的多粒度信息统, x U X U A T = { A 1 , A 2 , , A m } 0 β 0.5 < α 1 ,X在相似关系 R B 上依参数 α , β 的乐观(悲观)多粒度概率粗糙集近似精度 λ o ( α , β ) 分别定义为:

λ o ( α , β ) = | i m A i _ α o ( X ) | | i m A i ¯ β o ( X ) | λ p ( α , β ) = | i m A i _ α p ( X ) | | i m A i ¯ β p ( X ) |

例1:S是一个不完备的多粒度信息系统,(如表1所示), A 1 = { a 1 } A 2 = { a 2 } A 3 = { a 3 , a 4 } U = { x 1 , x 2 , , x 8 } x 1 , x 2 , , x 8 是8个对象, a 1 , a 2 , a 3 , a 4 是四个条件属性,D是决策性, A = { A 1 , A 2 , A 3 } 是粒度空间。

Table 1. Incomplete information system S

表1. 不完备信息系统S

U / d = { { x 1 , x 2 , x 3 , x 8 } , { x 4 , x 5 , x 6 , x 7 } }

根据定义4基于相似关系,当 α 变小, β 变大时,求得在不完备多粒度信息系统中概率粗糙集在不同决策类型的乐观(悲观)多粒度上(下)近似集(如表2所示):

Table 2. Optimistic (pessimistic) upper and lower approximate sets of incomplete multi-granularity probability rough sets based on similarity relations

表2. 基于相似关系的不完备多粒度概率粗糙集的乐观(悲观)上下近似集

得到近似精度为:

λ o ( 0.8 , 0.1 ) ( D 1 ) = 0 ; λ o ( 0.8 , 0.1 ) ( D 2 ) = 0 ; λ p ( 0.8 , 0.1 ) ( D 1 ) = 0 ; λ p ( 0.8 , 0.1 ) ( D 2 ) = 0 ;

λ o ( 0.7 , 0.1 ) ( D 1 ) = 0 ; λ o ( 0.7 , 0.1 ) ( D 2 ) = 0 ; λ p ( 0.7 , 0.1 ) ( D 1 ) = 1 2 ; λ p ( 0.7 , 0.1 ) ( D 2 ) = 1 2 ;

λ o ( 0.6 , 0.4 ) ( D 1 ) = 0 ; λ o ( 0.6 , 0.4 ) ( D 2 ) = 0 ; λ p ( 0.6 , 0.4 ) ( D 1 ) = 2 8 ; λ p ( 0.6 , 0.4 ) ( D 2 ) = 3 8

通过例1,可以发现在不完备信息系统中,基于相似关系对缺省的值进行分类;会出现在乐观的情况下所有的上(下)近似和精度都为空的情况,并且在完备的信息系统中近似精度所满足的性质此时也都不在满足。由此,我们在接下来的文章中基于优劣关系进行讨论。

4. 基于优势(劣势)关系的多粒度概粗糙集模型

定义7:设 M I S = U , A T , V , f 为一个不完备的多粒度信息系统, x U X U 0 β 0.5 < α 1 ,则

(1) 在优势关系 R A i 上,依参数 α , β 的乐观(悲观)多粒度概率粗糙集下近似 i = 1 m A i o _ α ( X ) 和上近似 i = 1 m A i o β ¯ ( X ) 分别定义:

i = 1 m A i o _ α ( X ) = { x U : p ( X | [ x ] A 1 ) α P ( X | [ x ] A 2 ) α P ( X | [ x ] A m ) α }

i = 1 m A i o β ¯ ( X ) = ~ i = 1 m A i o _ 1 β ( ~ X )

通过定义,可以得到在不完备系统中,乐观(悲观)多粒度概率粗糙集的边界域集合如下:

B n d i = 1 m A i ( α , β ) o = i = 1 m A i o β ¯ ( X ) i = 1 m A i o _ α ( X )

二元组 i = 1 m A i o _ α ( X ) , i = 1 m A i o β ¯ ( X ) 是一个被称作是X基于优势关系 R A i 关于粒度 A i ( i = 1 , 2 , , m ) 的乐

观多粒度概率粗糙集。

(2) 在劣势关系 R A i 上,依参数 α , β 的乐观(悲观)多粒度概率粗糙集下近似 i = 1 m A i o _ α ( X ) 和上近似 i = 1 m A i o β ¯ ( X ) 分别定义:

i = 1 m A i o _ α ( X ) = { x U : p ( X | [ x ] A 1 ) α P ( X | [ x ] A 2 ) α P ( X | [ x ] A m ) α }

i = 1 m A i o β ¯ ( X ) = ~ i = 1 m A i o _ 1 β ( ~ X )

通过定义,可以得到,在不完备系统中,乐观多粒度概率粗糙集的边界域集合:

B n d i = 1 m A i ( α , β ) o = i = 1 m A i o β ¯ ( X ) i = 1 m A i o _ α ( X )

二元组 i = 1 m A i o _ α ( X ) , i = 1 m A i o β ¯ ( X ) 称作是X基于劣势关系关于粒度 A i ( i = 1 , 2 , , m ) 的乐观多粒度概率粗糙集。

定理4.1:设 M I S = U , A T , V , f 为一个不完备的多粒度信息系统, X U x U 0 β 0.5 < α 1 ,则上近似可以表示为

i = 1 m A i 0 ¯ = { x U : p ( X | [ x ] A 1 ) > β P ( X | [ x ] A 2 ) > β P ( X | [ x ] A m ) > β }

证明: i = 1 m A i o β ¯ ( X ) = ~ i = 1 m A i o _ 1 β ( ~ X ) (其余等式证明可类似定理3.1可证)。

注:(1) 同理可得,悲观的上近似有如下性质

i = 1 m A i p β ¯ = { x U : p ( X | [ x ] A 1 ) > β P ( X | [ x ] A 2 ) > β P ( X | [ x ] A m ) > β }

(2) 同理基于劣势关系也可得出如上定理。

定义8:设 M I S = U , A T , V , f 为不完备多粒度信息系统 x U X U 0 β 0.5 < α 1 ,因此X在优势关系 R A i (劣势关系 R A i )上依参数 α , β 的乐观(悲观)多粒度概率粗糙集近似精度 λ o ( α , β ) 分别定义为:

λ o ( α , β ) = | i m A i _ α o ( X ) | | i m A i ¯ β o ( X ) | λ p ( α , β ) = | i m A i _ α p ( X ) | | i m A i ¯ β p ( X ) |

例2 不完备多粒度信息系统为例1中给出的(如表1)我们基于优势关系进行讨论,得到在优势关系下

的归类: U / R A i = { [ x 1 ] A i , [ x 2 ] A i , , [ x 8 ] A i }

根据定义7,当 α 变小, β 变大时,基于优势关系求得在不完备多粒度信息系统中概率粗糙集在不同决策类的乐观(悲观)多粒度上(下)近似集(如表3所示):

Table 3. Optimistic (pessimistic) upper and lower approximations of incomplete multi-granularity probability rough sets under dominance relations

表3. 优势关系下的不完备多粒度概率粗糙集的乐观(悲观)上下近似

得到近似精度为:

根据定义7,当变小,变大时,基于劣势关系求得在不完备多粒度信息系统中概率粗糙集在不同决策类的乐观(悲观)多粒度上(下)近似集(如表4所示):

Table 4. Optimistic (pessimistic) upper and lower approximations of incomplete multi-granularity probability rough sets under the inferiority relationship

表4. 劣势关系下的不完备多粒度概率粗糙集的乐观(悲观)上下近似

基于劣势关系得到近似精度为:

定理4.2:设为不完备多粒度信息系统,,因此基于优势关系和劣势关系的的近似精度应有如下性质:

(1)

(2)

注:在相似关系中上述性质一般不成立。

通过例1和例2的比较,可以发现在不完备系统中,基于优劣关系对缺省的值进行分类;这样可以避免依据相似关系分类时造成的信息偏差,和在乐观情况下所有的上(下)近似和精度都为空的情况。根据乐观和悲观,可以在不完备的多粒度概率粗糙集中通过调整值,得到不同的近似精度,并有如下变化规律:

(1) 在相同的值下,基于劣势关系得到了更大的近似精度。

(2) 当值同时变小时,上下近似会同时变增大;

(3) 当值同时变时,上下近似会同时变递减。

(4) 当逐渐减小,逐渐增大时,可以得到较大的下近似和较小的上近似,并且相应的不完备多粒度概率粗糙集的近似精度会增大。相反,则会减小。

5. 基于优劣势关系的多粒度概率粗糙集的决策规则

定义9 [8]:是一个不完备多粒度决策信息系统,d是决策属性,d把U分类为有序的:,对于任意,当时,中的对象优于中的对象,于是这些有序的决策类用向上联合与向下联合近似来表示:,当时,表示x至于属于决策类;而当时,表示x至多属于决策类。

定义10:设为一个不完备多粒度信统,在优势关系上的下近似与上近似表示:

的边界为:

则可能的决策规则有:

(1) 确定的规则:若,则

(2) 可能的规则:若,则x可能属于

(3) 确定的规则:若,则

(4) 可能的规则:若,则x可能属于

例3:s是一个不完备的多粒度决策信息系统(如下表5所示),是8个对象,是四个条件属性,是决策属性,是粒度间,

Table 5. Incomplete information system

表5. 不完备信息系统

从表中得到决策类,其中:

由于只有两个决策类,得到向下联合与向上联合,于是当,取时,得到下近似,上近似和边界为

时,得到下近似,上近似和边界为

因此,可以将不完备信息中的多粒度层整体考虑来得到规则:

,支持这个决策规则的对象有

,支持这个决策规则的对象有

,支持这个决策规则的对象有

,支持这个决策规则的对象有

,支持这个决策规则的对象有

,支持这个决策规则的对象有

,规则全部可能是确定的决策规则,也有可能是决策规则。

时,规则时确定的决策规则,,可能是决策规则,但是也有可能是确定的决策规则。

由此,可以发现当值越大,则得到的确定性规则越多,反之会越少。这样我们就可以根据决策者的不同要求来获取更为有用的规则。

6. 结论及展望

本文是基于不完备信息系统进行的研究。在本文开始,介绍了不完备系统中的多粒度粗糙集理论和乐观粗糙集近似和悲观多粒度粗糙集近似的定义;第三部分给出了不完备信息系统中基于相似关系的多粒度概率粗糙集的相关定义及性质,讨论了其上下近似和近似精度。第四部分基于优势关系劣势关系分别讨论了多粒度概率粗糙集的上下近似和近似精度,并做了对比,通过调整参数的值来得到更高的近似精度,讨论了近似精度满足的性质和变化规律。最后在第五部分提出了不完备信息系统中的多粒度概率粗糙集基于优劣关系的规则提取。

每个相关的定义都给出了具体实例验证,进一步探讨概率粗糙集模型基于优劣关系的规则提取的有效性,接下来的工作将针对这些规则的给出,尝试给出更为高效的约简及其规则提取的算法。

基金项目

青海省自然科学基金(2018-ZJ-911);青海民族大学科研创新团队专项经费支助。

NOTES

*通讯作者。

参考文献

[1] Pawlak, Z. (1982) Rough Sets. International Journal of Computer and Information Sciences, 11, 341-356.
https://doi.org/10.1007/BF01001956
[2] 张文修, 吴伟志, 梁吉业, 等. 粗糙集理论与方法[M]. 北京: 科学出版社, 2001-2007, 36(6): 1237-1240.
[3] 李金海, 吕跃进. 决策系统的快速属性约简算法[J]. 电子科技大学学报, 2007, 36(6): 1237-1240.
[4] 覃丽珍, 姚炳学, 李金海. 基于信息量的完备覆盖约简算法[J]. 计算机科学, 2012, 39(10): 235-239.
[5] 陈青梅. 多粒度概率粗糙集若干问题研究[D]: [硕士学位论文]. 南宁: 广西大学, 2014.
[6] 胡善忠, 徐怡, 何明慧, 王冉. 不完备系统中的一种多粒度粗糙集粒度约简算法[J]. 微电子学与计算机, 2018, 35(6): 41-46.
[7] 桑妍丽, 钱宇华. 多粒度决策粗糙集中的粒度约简方法[J]. 计算机科学, 2017, 44(5): 199-205.
[8] 张文修, 仇国芳. 基于粗糙集的不确定决策[M]. 北京: 清华大学出版社, 2005.
[9] 胡善忠. 多粒度粗糙集的粒度约简算法研究[D]: [硕士学位论文]. 合肥: 安徽大学, 2018.
[10] 许韦, 吴陈, 杨习贝. 基于容差关系的不完备可变精度多粒度粗糙集[J]. 计算机应用研究, 2013, 30(6): 1712-1715.
[11] 翟永健. 不完备信息系统中多粒度粗糙集理论与约简研究[D]: [博士学位论文]. 南京: 南京理工大学, 2014.