知识粗化细化时决策规则集变化趋势研究
摘要：针对大型动态数据集的决策信息系统，该文基于粗糙集理论研究了当知识粗化细化(属性增加、删除)时决策信息系统的近似集的变化情况，进而给出了知识粗化细化时所起引的决策规则集变化趋势，并以实例给予了验证。
关键词：知识粗化细化;近似集;规则集;
0、引言
粗糙集理论是波兰数学家Pawlak 于1982 年提出的一种数据分析理论[1]，它是一种处理不确定和不精确性问题的数学工具，它研究的重要内容就是分类与约简，目的是在决策信息系统中获取良好的规则集合，在海量数据系统中挖掘出有用的知识，它在数据挖掘与知识发现中的应用已经取得了较大的进展。
粗糙集理论是基于等价关系对事物进行分类，由等价关系引入粗糙集理论的基本概念上近似、下近似及边界域等。在大型决策信息系统中，数据集随着外部信息世界的变化而不断地增加、删除、修改，是动态变化的.当属性集中单个属性或多个属性增加删除时，会起引对象的分类变化，进而引起近似集的变化，相应地，对决策规则产生一定的影响，该文研究的是当知识变化时，决策规则的变化趋势。文章的组织结构如下：第一部分介绍粗糙集理论的基本概念及相关知识;第二部分给出知识粗化细化概念及其引起的近似集变化情况;第三部分知识粗化细化时决策规则变化趋势。第四部分给全文做了总结。
1、相关知识在定义 1~3 中引入了张文修、苗夺谦先生的工作[29]。
约定：U 是有限论域，R是U 上的一个等价关系，[x]是U 上的 R ?等价类( R ?知识).属性、等价关系、知识等概念，不加区分直接使用。
定义 1 (集合的下近似和上近似) 给定知识库(近似空间)K = (U, S)，其中，U为论域， S 表示论域U 上等价关系簇，则?X ?U 和论域U 上的一个等价关系R∈IND(K)，定义子集(概念或信息粒)X 关于知识R上的下近似和上近似分别为( ) { |( ) ([ ] )} { |( ) ( )}, R R X = x ?x∈U ∧ x ? X =∪ Y ?Y ∈U R ∧ Y ? X (5)( ) { |( ) ([ ] ) } { |( ) ( )}. R R X = x ?x∈U ∧ x ∩ X ≠ ? =∪ Y Y ∈U R ∧ Y ∩ X ≠ ? (6)集合( ) ( ) ( ) R bn X = R X ? R X 称为X 的R 边界域; ( ) ( ) R pos X = R X 称为X 的R 正域;( ) ( ) R neg X =U ? R X 称为X 的R负域。显然， ( ) ( ) ( ) R R R X = pos X ∪bn X 。
定义 2 (近似分类的上近似和下近似) 设给定一个论域U 和论域U 上的一个等价关系(知识)R ，以及论域U 的一个划分(或称完备分类) 1 2 ( ) { , , , } ( ) n π U = X X ?? X ∈Π U ，且这个划分独立于R 。其中，子集( 1,2, , ) i X i = ?? n 是划分π (U)的.等价类。π (U)的R下近似和上近似分别为：
1 21( ( )) ( ) ( ) ( ) ( )nn iiR π U R X R X R X R X== ∪ ∪??∪ =∪1 21( ( )) ( ) ( ) ( ) ( )nn iiR π U R X R X R X R X== ∪ ∪??∪ =∪定义 3 (决策信息系统) 一个决策信息系统以四个元组S = (U,C ∪D,V, f )表示，其中， 1, 2, , : { ... }n U U = x x x 为对象的非空有限集合，称为论域;C ∪D:C ={α |α ∈C}称为条件属性集，每个(1 ) j α ∈C ≤ j ≤ m 称为C的一个简单属性;D ={d | d ∈D}称为决策系统属性集，且C ∩D = ?,C ≠ ?,D ≠ ?;: ( , ) ( ) c d V V V V c C d D V C D α = ∪ ? ∈ ∈ = ∪ ?α ∈ ∪ 是信息函数f 的值域，而Vα 表示值域;f : f { f | f :U C D} α α = →?α ∈ ∪ 表示决策系统的信息函数，fα 为属性α 的信息函数。
1 2 ( ) { , , , } n U C = X X ?? X 表示条件等价类集合， 1 2 ( ) { , , , } n U D = Y Y ?? Y 表示决策等价μ μ∩= ? ≤当 ( , ) 1 i j μ X Y = 时， ij r 是确定性规则;当0 ( , ) 1 i j ? μ X Y ? 时， ij r 是不确定规则，或者说是近似规则。( , ) i j μ X Y 可解释为论域中给定对象属于i X 时，该对象属于j Y 的概率。
规则的确定因子反映了粗糙规则的精确程度,规则集合的规则确定因子值越高,规则集合的一致性就好,精确度也高,相反不确定性较大。
命题 1 给定决策信息系统T ={U,C ∪ D,V, f } ，设条件属性集C 的所有为1 2 ( ) { , , } c m π U = X X ??X 等价类[ ]c x 的个数为( ) c π U ，决策属性集D 的所有为1 2 ( ) { , , } D n π U = Y Y ??Y 等价类[ ]D x 的个数为( ) D π U ，所有条件属性集C的等价类[ ]c x 被包含在决策属性集D的等价类[ ]D x 的集合为1 2 c ( ) { , , , k} r D = Z Z ?? Z ，个数为c ( ) r D ，所有条件属性集C 的等价类( ) c π U 中去掉被包含在决策属性集D的等价类所剩余的等价类集合记为dv ， 1 2 c ( ) c ( ) { , l} dv =π U ? r D = W W ??W ，所剩余的等价类集合元素个数为dv 。
1.若dv =0，则决策系统是协调的决策系统，只有确定性决策规则集。
2.若dv ?? 0，则决策系统是不协调的决策系统。当0 ( ) c ? dv ? π U 时既有确定性决策规则集也有非确定性规则集;当( ) c dv = π U ，只有非确定性决策规则集，即对人们所做决策起不大作用。
确定性决策规则集( ) i r d 条数： c ( ) m = r D ;不确定性决策规则集( ) ur d 条数：n = dv 为类集元集l W 与j Y 的交集不为空的集合对的个数。
例 1：表1 给出了一个关于某些病人的知识表达系统，其中U ={1,2,3,4,5,6,7,8}，1 2 3 C ={C ,C ,C }，D ={d}.令1 C = 头痛， 2 C = 肌肉痛， d = 流感2 知识粗化细化在粗糙集模型中，粒度化准则是不可分辨关系或等价关系。相应地，不可分辨类或等价类被看作是基本粒，任意给定的一个属性子集都可以诱导出对象集上的一个等价关系。一般来说，从粗粒度层次到细粒度层次的转换可以通过减少该属性子集中的元素来实现，而通过向该属性子集增添新的属性则可以实现从细粒度层次到粗粒度层次的转换。
下面的例子解释在知识粗化细化的概念及定理1~2：
设 1 2 3 4 5 6 7 8 , , , , , , , x x x x x x x x 是U 上的8 位全职教师;依据给定属性1α = 全职，得到元素等价类1 () 12345678[x] {x,x,x,x,x,x,x,x}
α=;在属性1 α的条件下，1 2 3 4 5 6 7 8 x , x , x , x , x , x , x , x 是不可分辨的(因为这些都是全职教师)。如果增加一个属性2 α = 博导，则在1 8 x ? x 中存在1 3 6 x , x , x ; 1 3 6 , , x x x 既具有属性1α 又具有属性2 α 。依据1α ，2 α 得到元素等价类( 1, 2 ) 1 3 6 [x] {x , x , x } α α = ;在属性1α ， 2 α 的条件下1 3 6 x , x , x 是不可分辨的。
容易得到( 1, 2 ) 1 3 6 1 2 3 4 5 6 7 8 ( 1 ) [x] {x , x , x } {x , x , x , x , x , x , x , x } [x] α α α = ? = ;如此等等。我们可以得知：依赖于属性1α ， 2 α 的元素等价类( 1, 2 ) [x] α α k 是依赖于属性1α 的元素等价类( 1 ) [x] α的一个分解类。随着属性α 的增加或者对属性集α 中属性的增加，以[x]α 为基础能够得到[x]α 的多个不同的元素分解类，称为属性的细化。反之，对属性集α 中属性的删除，称为属性的粗化。
定义 6 设R是U 上的属性集，R ?U ，R 是U 上的一个知识，存在有不可分辨关系： ( )S RIND R S∈= ∩ 。对于单元素r ，r∈U ，r也是U 上的一个属性，将r添加到R中，称为知识细化，记作R r+←，并且有card(R r) card(R)+← ≤定义 7 设R是U 上的属性集，R ?U ，R 是U 上的一个知识，存在有不可分辨关系： ( )S RIND R S∈= ∩ 。对于单元素r ，r∈U ，r也是U 上的一个属性，将R中的r删除，称为知识粗化，记作R r?→，并且有card(R r) card(R)?
→ ≥定 理 1 设1 2 , , t α α ??α 是属性集， 1 2 t α ?α ????α ; 若i j α ?α ， 则有( ) ( ) [ ] [ ] j i x x α α ? .
定理 2 设( 1 ) ( 2 ) ( 1 ) ( ) [ ] ,[ ] , ,[ ] ,[ ] t t x x x x α α α ? α ?? 是属性1 2 1 , , , , t t α α α α ?? ? 决定的元素等价类，若( 1 ) ( 2 ) ( 1 ) ( ) [ ] [ ] [ ] [ ] t t x x x x α α α ? α? ???? ? ，则有1 2 1 ( ) ( ) ( ) ( ) t t card α card α card α card α ? ≤ ≤??≤ ≤ .
知识的粗化细化能够表达出知识的分辨能力。
3、知识粗化细化时规则集变化趋势当属性增加删除时可能会起引近似集的变化，由粗糙集理论的基本概念定义我们知道，近似集与决策规则集存在一定的关系，近似集的变化势必引起决策规则集的变化。
首先，先讨论一下当属性增加删除时，决策信息系统近似集的变化情况：
属性增加是对知识的细化，此时有引理 1 设给定一个论域U 和论域U 上的一个等价关系(知识) R ，以及论域U 的一个划分(或称完备分类) 1 2 ( ) { , , , } ( ) n π U = X X ?? X ∈Π U ，且这个划分独立于R。其中，子集( 1,2, , ) i X i = ?? n 是划分π (U)的等价类。属性r 增加(知识细化)，π (U)的近似集的变化情况为：
R(π (U))? R′(π (U))，R(π (U))?R′(π (U))可以得出，属性增加时，下近似集元素数及上近似集元素数是单调增加的。
属性删除是对知识的粗化，此时有引理 2 设给定一个论域U 和论域U 上的一个等价关系(知识) R ，以及论域U 的一个划分(或称完备分类) 1 2 ( ) { , , , } ( ) n π U = X X ?? X ∈Π U ，且这个划分独立于R。其中，子集( 1,2, , ) i X i = ?? n 是划分π (U)的等价类。属性r 删除(知识粗化)，π (U)的近似集的变化情况为：
R(π (U))? R′(π (U))，R(π (U))? R′(π可以得出，属性删除时，下近似集元素数及上近似集元素数是单调减少的。
定理 1，2，推论1~3，由定义8，直接得到，证明略。
在决策信息系统中，通过条件属性C 预测或表示决策属性集D。通过对决策系统的粗分析之后，希望得到一系列的决策规则。
当属性增加删除时可能会起引近似集的变化，由粗糙集理论的基本概念定义我们知道，近似集与决策规则集存在一定的关系，近似集的变化势必引起决策规则集的变化在决策系统T = (U,C ∪ D,V, f ) ，决策属性集D 往往是固定的， X ? C 变量，IND(X ) ?U ×U 是条件属性也是预测或表达属性。IND(D) ?U ×U 是决策属性也是被预测或被表达的属性。依条件属性近似分类的下近似集是精确包含在依决策属性集近似分类的子集中，即，下近似集对应着决策系统的确定性规则，边界域对应着不协调决策系统的不确定性规则。在决策信息系统中，属性集变化时决策规则集的变化分为以下四种情况：
约定：R(π (U)) ↑表示下近似集变大， R(π (U)) ↓ 表示下近似集变小， ( ) i r d ↑ 表示确定性决策规则集变大， ( ) i r d ↓表示确定性决策规则集变小，c ( ) r D ↓ 表示所有条件属性集C的等价类[ ]c x 被包含在决策属性集D的等价类[ ]D x 的集合元素减少， c ( ) r D ↑ 表示所有条件属性集C 的等价类[ ]c x 被包含在决策属性集D的等价类[ ]D x 的集合元素增加.
第一种情况：条件属性集变化，决策属性集固定不变。
1.在决策系统T = (U,C ∪ D,V, f )中，当条件属性增加，C c+←，决策属性D不变时有，R(π (U)) ↑? ( ) i r d ↑2.在决策系统T = (U,C ∪ D,V, f )中，当条件属性减少，C c?→，决策属性D不变时有，R(π (U)) ↓? ( ) i r d ↓例2 表2 是一个关于气象信息的决策表。论域U 由14 个对象---气象状态组成，属性共有5 个，其中包含4 个条件属性，分别为景象(Outlook)、温度(Temperature)、湿度(Humidity)、刮风(Windy);1 个决策属性(d),表示是否适合在室外打网球。这些对象可以用知识来描述，属性集的大小对论域的对象描述使得知识库粗细不同。{1, 2,6,8,14}, 2 Y = {3,4,5,6,7,9,10,11,12,13}.
( 1 ) 设初始条件属性集1 1 C = {α }，得1 1 2 3 U /C = {X , X , X }; (1)其中 1 X ={1, 2,8,9,11}, 2 X = {3,7,12,13}, 3 X ={4,5,6,10,14}
并且有 1 IND(C ) ? IND(D)，所以此时决策表是协调的，只有确定性规则，1 2 C (π (U))={X }, (5)决策规则集条件数为1，确定性规则有22 1 r : (α ,Overcast)→(d,P) .
当条件属性集1 C 中添加属性元素2 α ，此时2 1 2 C ={α ,α },得2 1 2, 3 4 5 6 7 8 U /C ={X , X X , X , X , X , X , X } (2)其 中 ，1 X = {1, 2} , 2 X ={8,11} , 3 X = {9} , 4 X = {3,13} , 5 X ={7} , 6 X ={12} , 7 X ={4,10,14} ,8 X ={5,6}
并且有 1 IND(C ) ? IND(D)，所以此时决策表是协调的，只有确定性规则，C2(π (U)) ={X1,X3,X4 ,X5,X6} , (6)决策规则集条数为5，确定规则有42 1 2 r : (α ,Overcast) ∧ (α ,Hot)→(d, P) .
52 1 2 r : (α ,Overcast) ∧ (α ,Cool)→(d, P) .
62 1 2 r : (α ,Overcast) ∧ (α ,Mild)→(d, P) .
11 1 2 r : (α , Sunny) ∧ (α ,Hot)→(d, N) .
32 1 2 r : (α , Sunny) ∧ (α ,Cool)→(d, P) .
(3)当条件属性集2 C 中添加属性元素3α ，此时3 1 2 3 C ={α ,α ,α },得3 1 2 3 4 5 6 7 8 9 10 11 U /C ={X , X , X , X , X , X , X , X , X , X , X } (3)其中， 1 X = {1, 2}， 2 X = {8}， 3 X ={11}， 4 X = {9}， 5 X ={3}， 6 X ={13}， 7 X ={7}，8 X ={12}， 9 X ={4,14}， 10 X ={10}， 11 X = {5,6}，并且有1 IND(C ) ? IND(D)，所以此时决策表是协调的，只有确定性规则，C3(π (U)) ={X1,X2 , X3 , X4 , X5 , X6 ,X7 , X8 , X10 , X11} , (7)决策规则集条数为10，确定性规则不再一一列出。
(4)当条件属性集3 C 中添加属性元素4 α ，此时4 1 2 3 4 C ={α ,α ,α ,α },得4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 U /C ={X , X , X , X , X , X , X , X , X , X , X , X , X , X } (4)类集合。
当IND(C) ? IND(D)时，则称决策系统是协调的(一致的或相容的)，其中IND(C)，IND(D)分别表示条件等价类和决策等价类。
定义 4 (决策规则) 设S = (U,C ∪D,V, f )是一个决策信息系统，令i X 和j Y 分别代表U (C)与U (D)中的各个等价类， ( ) i des X 表示对等价类的描述，即等价类i X 对于各条件属性值的特定取值; ( )j des Y 表示对等价类的描述，即等价类j Y 对于各决策属性值的特定取值，则决策规则如下：
: ( ) ( ) ij i j r des X →des Y ， j i Y ∩ X ≠φ定义 5 (规则的确定因子) 给定决策信息系统S = (U,C ∪D,V,F) ，( ) i X ∈U IND C ， ( ) j Y ∈U IND D ，有其中，X1 = {1}， 2 X = {8}， 3 X ={11}， 4 X = {9}， 5 X ={3}， 6 X ={13}， 7 X ={7}，8 X ={12}， 9 X ={4}， 10 X ={10}， 11 X ={5}， 12 X ={2}， 13 X ={6}， 14 X ={14}，并且有1 IND(C ) ? IND(D)，所以此时决策表是协调的，只有确定性规则，C3(π (U)) ={X1,X2 ,X3,X4 ,X5,X6 ,X7 ,X8 ,X10 ,X11} , (8)决策规则集条数为14，确定性规则不再一一列出。
综上，由(1)~(4)式，有1 1 2 1 2 3 1 2 3 4 {α }?{α ,α }?{α ,α ,α }?{α ,α ,α ,α }从而得出1 1 2 1 2 3 1 2 3 4 U /{α }?U /{α ,α }?U /{α ,α ,α }?U /{α ,α ,α α }满足定理1和定理2。
由(5)~(8)式可以得知，当决策属性固定不变，随着条件属性的增加，下近似集单调增加的，决策规则集也是单调增加的。
第二种情况：条件属性集固定不变，决策属性集变化。
在决策系统T = (U,C ∪ D,V, f )中,当决策属性增加，D d+←，条件属性C 不变时有，R(π (U)) ↓?ri (d) ↓在决策系统T = (U,C ∪ D,V, f ) 中，当决策属性减少，D d?→，条件属性D 不变时有，R(π (U)) ↑? ( ) i r d ↓第三种情况：条件属性集和决策属性集同时变化。
在决策系统T = (U,C ∪ D,V, f )中，当条件属性增加，C c+←，决策属性减少D d?→时有，R(π (U)) ↑? ( ) i r d ↑在决策系统T = (U,C ∪ D,V, f )中，当条件属性减少，C c?→，决策属性增加D d+←有，R(π (U)) ↓? ( ) i r d ↓在决策系统T = (U,C ∪ D,V, f )中，当条件属性和决策属性同时增加，C c+←，D d+←时有，若 ( ) c r D ↓，R(π (U)) ↓? ( ) i r d ↓若 ( ) c r D ↑，R(π (U)) ↑? ( ) i r d ↑在决策系统T = (U,C ∪ D,V, f )中，当条件属性和决策属性同时减少，C c?→，D d?→有，若 ( ) c r D ↓，R(π (U)) ↓? ( ) i r d ↓若 ( ) c r D ↑，R(π (U)) ↑? ( ) i r d ↑在决策信息系统中，当属性增加删除时会引起近似集和边界域的变化，对于下近似集的变化会引起确定性的规则集的规律性变化，边界域对应不确定性规则集，属性集的变化对边界域的变化没有一定的规律可循，从而也不能进一步得出当属性增加删除时不确定性规则集的变化趋势。
4、结论
本文给出了大型动态决策信息系统在属性集变化时所引起的决策规则集的变化趋势，以后需要深入研究在属性集动态变化时如何及时有效地获取决策规则，辅助各应用领域作出更好的决策。
[参考文献] (References)
[1] 张文修. 粗糙集理论与方法[M]. 北京：科学出版社，2001.
[2] 苗夺谦，李道国. 粗糙集理论、算法与应用[M]. 北京：清华大学出版社，2008.
【知识粗化细化时决策规则集变化趋势研究】相关文章：
2.游学趋势变化
5.日语口语变化规则