- 相關推薦
知識粗化細化時決策規則集變化趨勢研究
摘要：針對大型動態數據集的決策信息系統，該文基于粗糙集理論研究了當知識粗化細化(屬性增加、刪除)時決策信息系統的近似集的變化情況，進而給出了知識粗化細化時所起引的決策規則集變化趨勢，并以實例給予了驗證。
關鍵詞：知識粗化細化;近似集;規則集;
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 =5vajrimf.令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.
【知識粗化細化時決策規則集變化趨勢研究】相關文章：
粗決策樹動態規則提取算法研究及應用09-22
企業治理的概念化趨勢研究08-24
企業設備治理市場化決策研究10-20
企業管理的概念化趨勢研究10-22
區域經濟集團化趨勢研究10-24
全球化、知識化時代的旅游市場營銷07-25
粗集方法在KDD系統中的應用與研究07-05
品牌延伸的決策研究05-17
全球化背景下公司治理演進趨勢研究06-28