- 相關(guān)推薦
知識粗化細化時決策規(guī)則集變化趨勢研究
摘要：針對大型動態(tài)數(shù)據(jù)集的決策信息系統(tǒng)，該文基于粗糙集理論研究了當知識粗化細化(屬性增加、刪除)時決策信息系統(tǒng)的近似集的變化情況，進而給出了知識粗化細化時所起引的決策規(guī)則集變化趨勢，并以實例給予了驗證。
關(guān)鍵詞：知識粗化細化;近似集;規(guī)則集;
0、引言
粗糙集理論是波蘭數(shù)學家Pawlak 于1982 年提出的一種數(shù)據(jù)分析理論[1]，它是一種處理不確定和不精確性問題的數(shù)學工具，它研究的重要內(nèi)容就是分類與約簡，目的是在決策信息系統(tǒng)中獲取良好的規(guī)則集合，在海量數(shù)據(jù)系統(tǒng)中挖掘出有用的知識，它在數(shù)據(jù)挖掘與知識發(fā)現(xiàn)中的應用已經(jīng)取得了較大的進展。
粗糙集理論是基于等價關(guān)系對事物進行分類，由等價關(guān)系引入粗糙集理論的基本概念上近似、下近似及邊界域等。在大型決策信息系統(tǒng)中，數(shù)據(jù)集隨著外部信息世界的變化而不斷地增加、刪除、修改，是動態(tài)變化的.當屬性集中單個屬性或多個屬性增加刪除時，會起引對象的分類變化，進而引起近似集的變化，相應地，對決策規(guī)則產(chǎn)生一定的影響，該文研究的是當知識變化時，決策規(guī)則的變化趨勢。文章的組織結(jié)構(gòu)如下：第一部分介紹粗糙集理論的基本概念及相關(guān)知識;第二部分給出知識粗化細化概念及其引起的近似集變化情況;第三部分知識粗化細化時決策規(guī)則變化趨勢。第四部分給全文做了總結(jié)。
1、相關(guān)知識在定義 1~3 中引入了張文修、苗奪謙先生的工作[29]。
約定：U 是有限論域，R是U 上的一個等價關(guān)系，[x]是U 上的 R ?等價類( R ?知識).屬性、等價關(guān)系、知識等概念，不加區(qū)分直接使用。
定義 1 (集合的下近似和上近似) 給定知識庫(近似空間)K = (U, S)，其中，U為論域， S 表示論域U 上等價關(guān)系簇，則?X ?U 和論域U 上的一個等價關(guān)系R∈IND(K)，定義子集(概念或信息粒)X 關(guān)于知識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 上的一個等價關(guān)系(知識)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 (決策信息系統(tǒng)) 一個決策信息系統(tǒng)以四個元組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}稱為決策系統(tǒng)屬性集，且C ∩D = ?,C ≠ ?,D ≠ ?;: ( , ) ( ) c d V V V V c C d D V C D α = ∪ ? ∈ ∈ = ∪ ?α ∈ ∪ 是信息函數(shù)f 的值域，而Vα 表示值域;f : f { f | f :U C D} α α = →?α ∈ ∪ 表示決策系統(tǒng)的信息函數(shù)，fα 為屬性α 的信息函數(shù)。
1 2 ( ) { , , , } n U C = X X ?? X 表示條件等價類集合， 1 2 ( ) { , , , } n U D = Y Y ?? Y 表示決策等價μ μ∩= ? ≤當 ( , ) 1 i j μ X Y = 時， ij r 是確定性規(guī)則;當0 ( , ) 1 i j ? μ X Y ? 時， ij r 是不確定規(guī)則，或者說是近似規(guī)則。( , ) i j μ X Y 可解釋為論域中給定對象屬于i X 時，該對象屬于j Y 的概率。
規(guī)則的確定因子反映了粗糙規(guī)則的精確程度,規(guī)則集合的規(guī)則確定因子值越高,規(guī)則集合的一致性就好,精確度也高,相反不確定性較大。
命題 1 給定決策信息系統(tǒng)T ={U,C ∪ D,V, f } ，設條件屬性集C 的所有為1 2 ( ) { , , } c m π U = X X ??X 等價類[ ]c x 的個數(shù)為( ) c π U ，決策屬性集D 的所有為1 2 ( ) { , , } D n π U = Y Y ??Y 等價類[ ]D x 的個數(shù)為( ) D π U ，所有條件屬性集C的等價類[ ]c x 被包含在決策屬性集D的等價類[ ]D x 的集合為1 2 c ( ) { , , , k} r D = Z Z ?? Z ，個數(shù)為c ( ) r D ，所有條件屬性集C 的等價類( ) c π U 中去掉被包含在決策屬性集D的等價類所剩余的等價類集合記為dv ， 1 2 c ( ) c ( ) { , l} dv =π U ? r D = W W ??W ，所剩余的等價類集合元素個數(shù)為dv 。
1.若dv =0，則決策系統(tǒng)是協(xié)調(diào)的決策系統(tǒng)，只有確定性決策規(guī)則集。
2.若dv ?? 0，則決策系統(tǒng)是不協(xié)調(diào)的決策系統(tǒng)。當0 ( ) c ? dv ? π U 時既有確定性決策規(guī)則集也有非確定性規(guī)則集;當( ) c dv = π U ，只有非確定性決策規(guī)則集，即對人們所做決策起不大作用。
確定性決策規(guī)則集( ) i r d 條數(shù)： c ( ) m = r D ;不確定性決策規(guī)則集( ) ur d 條數(shù)：n = dv 為類集元集l W 與j Y 的交集不為空的集合對的個數(shù)。
例 1：表1 給出了一個關(guān)于某些病人的知識表達系統(tǒng)，其中U ={1,2,3,4,5,6,7,8}，1 2 3 C ={C ,C ,C }，D =4wgiu7j.令1 C = 頭痛， 2 C = 肌肉痛， d = 流感2 知識粗化細化在粗糙集模型中，粒度化準則是不可分辨關(guān)系或等價關(guān)系。相應地，不可分辨類或等價類被看作是基本粒，任意給定的一個屬性子集都可以誘導出對象集上的一個等價關(guān)系。一般來說，從粗粒度層次到細粒度層次的轉(zhuǎn)換可以通過減少該屬性子集中的元素來實現(xiàn)，而通過向該屬性子集增添新的屬性則可以實現(xiàn)從細粒度層次到粗粒度層次的轉(zhuǎn)換。
下面的例子解釋在知識粗化細化的概念及定理1~2：
設 1 2 3 4 5 6 7 8 , , , , , , , x x x x x x x x 是U 上的8 位全職教師;依據(jù)給定屬性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 α 。依據(jù)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]α 為基礎(chǔ)能夠得到[x]α 的多個不同的元素分解類，稱為屬性的細化。反之，對屬性集α 中屬性的刪除，稱為屬性的粗化。
定義 6 設R是U 上的屬性集，R ?U ，R 是U 上的一個知識，存在有不可分辨關(guān)系： ( )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 上的一個知識，存在有不可分辨關(guān)系： ( )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、知識粗化細化時規(guī)則集變化趨勢當屬性增加刪除時可能會起引近似集的變化，由粗糙集理論的基本概念定義我們知道，近似集與決策規(guī)則集存在一定的關(guān)系，近似集的變化勢必引起決策規(guī)則集的變化。
首先，先討論一下當屬性增加刪除時，決策信息系統(tǒng)近似集的變化情況：
屬性增加是對知識的細化，此時有引理 1 設給定一個論域U 和論域U 上的一個等價關(guān)系(知識) 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))可以得出，屬性增加時，下近似集元素數(shù)及上近似集元素數(shù)是單調(diào)增加的。
屬性刪除是對知識的粗化，此時有引理 2 設給定一個論域U 和論域U 上的一個等價關(guān)系(知識) 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′(π可以得出，屬性刪除時，下近似集元素數(shù)及上近似集元素數(shù)是單調(diào)減少的。
定理 1，2，推論1~3，由定義8，直接得到，證明略。
在決策信息系統(tǒng)中，通過條件屬性C 預測或表示決策屬性集D。通過對決策系統(tǒng)的粗分析之后，希望得到一系列的決策規(guī)則。
當屬性增加刪除時可能會起引近似集的變化，由粗糙集理論的基本概念定義我們知道，近似集與決策規(guī)則集存在一定的關(guān)系，近似集的變化勢必引起決策規(guī)則集的變化在決策系統(tǒng)T = (U,C ∪ D,V, f ) ，決策屬性集D 往往是固定的， X ? C 變量，IND(X ) ?U ×U 是條件屬性也是預測或表達屬性。IND(D) ?U ×U 是決策屬性也是被預測或被表達的屬性。依條件屬性近似分類的下近似集是精確包含在依決策屬性集近似分類的子集中，即，下近似集對應著決策系統(tǒng)的確定性規(guī)則，邊界域?qū)粎f(xié)調(diào)決策系統(tǒng)的不確定性規(guī)則。在決策信息系統(tǒng)中，屬性集變化時決策規(guī)則集的變化分為以下四種情況：
約定：R(π (U)) ↑表示下近似集變大， R(π (U)) ↓ 表示下近似集變小， ( ) i r d ↑ 表示確定性決策規(guī)則集變大， ( ) i r d ↓表示確定性決策規(guī)則集變小，c ( ) r D ↓ 表示所有條件屬性集C的等價類[ ]c x 被包含在決策屬性集D的等價類[ ]D x 的集合元素減少， c ( ) r D ↑ 表示所有條件屬性集C 的等價類[ ]c x 被包含在決策屬性集D的等價類[ ]D x 的集合元素增加.
第一種情況：條件屬性集變化，決策屬性集固定不變。
1.在決策系統(tǒng)T = (U,C ∪ D,V, f )中，當條件屬性增加，C c+←，決策屬性D不變時有，R(π (U)) ↑? ( ) i r d ↑2.在決策系統(tǒng)T = (U,C ∪ D,V, f )中，當條件屬性減少，C c?→，決策屬性D不變時有，R(π (U)) ↓? ( ) i r d ↓例2 表2 是一個關(guān)于氣象信息的決策表。論域U 由14 個對象---氣象狀態(tài)組成，屬性共有5 個，其中包含4 個條件屬性，分別為景象(Outlook)、溫度(Temperature)、濕度(Humidity)、刮風(Windy);1 個決策屬性(d),表示是否適合在室外打網(wǎng)球。這些對象可以用知識來描述，屬性集的大小對論域的對象描述使得知識庫粗細不同。{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)，所以此時決策表是協(xié)調(diào)的，只有確定性規(guī)則，1 2 C (π (U))={X }, (5)決策規(guī)則集條件數(shù)為1，確定性規(guī)則有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)，所以此時決策表是協(xié)調(diào)的，只有確定性規(guī)則，C2(π (U)) ={X1,X3,X4 ,X5,X6} , (6)決策規(guī)則集條數(shù)為5，確定規(guī)則有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)，所以此時決策表是協(xié)調(diào)的，只有確定性規(guī)則，C3(π (U)) ={X1,X2 , X3 , X4 , X5 , X6 ,X7 , X8 , X10 , X11} , (7)決策規(guī)則集條數(shù)為10，確定性規(guī)則不再一一列出。
(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)時，則稱決策系統(tǒng)是協(xié)調(diào)的(一致的或相容的)，其中IND(C)，IND(D)分別表示條件等價類和決策等價類。
定義 4 (決策規(guī)則) 設S = (U,C ∪D,V, f )是一個決策信息系統(tǒng)，令i X 和j Y 分別代表U (C)與U (D)中的各個等價類， ( ) i des X 表示對等價類的描述，即等價類i X 對于各條件屬性值的特定取值; ( )j des Y 表示對等價類的描述，即等價類j Y 對于各決策屬性值的特定取值，則決策規(guī)則如下：
: ( ) ( ) ij i j r des X →des Y ， j i Y ∩ X ≠φ定義 5 (規(guī)則的確定因子) 給定決策信息系統(tǒng)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)，所以此時決策表是協(xié)調(diào)的，只有確定性規(guī)則，C3(π (U)) ={X1,X2 ,X3,X4 ,X5,X6 ,X7 ,X8 ,X10 ,X11} , (8)決策規(guī)則集條數(shù)為14，確定性規(guī)則不再一一列出。
綜上，由(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)式可以得知，當決策屬性固定不變，隨著條件屬性的增加，下近似集單調(diào)增加的，決策規(guī)則集也是單調(diào)增加的。
第二種情況：條件屬性集固定不變，決策屬性集變化。
在決策系統(tǒng)T = (U,C ∪ D,V, f )中,當決策屬性增加，D d+←，條件屬性C 不變時有，R(π (U)) ↓?ri (d) ↓在決策系統(tǒng)T = (U,C ∪ D,V, f ) 中，當決策屬性減少，D d?→，條件屬性D 不變時有，R(π (U)) ↑? ( ) i r d ↓第三種情況：條件屬性集和決策屬性集同時變化。
在決策系統(tǒng)T = (U,C ∪ D,V, f )中，當條件屬性增加，C c+←，決策屬性減少D d?→時有，R(π (U)) ↑? ( ) i r d ↑在決策系統(tǒng)T = (U,C ∪ D,V, f )中，當條件屬性減少，C c?→，決策屬性增加D d+←有，R(π (U)) ↓? ( ) i r d ↓在決策系統(tǒng)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ǒng)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ǒng)中，當屬性增加刪除時會引起近似集和邊界域的變化，對于下近似集的變化會引起確定性的規(guī)則集的規(guī)律性變化，邊界域?qū)淮_定性規(guī)則集，屬性集的變化對邊界域的變化沒有一定的規(guī)律可循，從而也不能進一步得出當屬性增加刪除時不確定性規(guī)則集的變化趨勢。
4、結(jié)論
本文給出了大型動態(tài)決策信息系統(tǒng)在屬性集變化時所引起的決策規(guī)則集的變化趨勢，以后需要深入研究在屬性集動態(tài)變化時如何及時有效地獲取決策規(guī)則，輔助各應用領(lǐng)域作出更好的決策。
[參考文獻] (References)
[1] 張文修. 粗糙集理論與方法[M]. 北京：科學出版社，2001.
[2] 苗奪謙，李道國. 粗糙集理論、算法與應用[M]. 北京：清華大學出版社，2008.
【知識粗化細化時決策規(guī)則集變化趨勢研究】相關(guān)文章：
粗決策樹動態(tài)規(guī)則提取算法研究及應用09-22
智能決策支持系統(tǒng)中的知識表示及基于粗集的知識推理10-04
企業(yè)治理的概念化趨勢研究08-24
企業(yè)設備治理市場化決策研究10-20
企業(yè)管理的概念化趨勢研究10-22
全球化、知識化時代的旅游市場營銷07-25
品牌延伸的決策研究05-17
全球化背景下公司治理演進趨勢研究06-28