基于歸并的粗集約簡分析

摘 要：粗糙集理論研究的重要內容是分類與約簡。在對分類與歸并性質充分研究的基礎上，探討了條件分類、約簡與核的層次關系。基于歸并的思想，描述了條件類歸并對決策表一致性的影響，證明了代數核屬性的充要條件。

關鍵詞：粗糙集； 約簡； 歸并

中圖法分類號：TP18 文獻標識碼：A 文章編號：1001-3695(2006)10-0025-02

Rough Set Reduction Analysis Based on Merging

WANG Jiayang， CHEN Songqiao， LUO An

（College of Information Science Engineering， Central South University， Changsha Hunan 410083， China）

Abstract:The classification and reduction are the important objectives of rough set theory. According to the properties of partition and merging， the hierarchy relation among condition classification， reduction and core is studied. Based on merging thought， the impact of condition class merging to consistence of decision table is described， then the sufficient and necessary condition about algebra core attributes is proved.

Key words:Rough Set; Reduction; Merging

1 引言

粗糙集理論于20世紀作為一種數學方法提出，它超越了傳統知識處理和模糊邏輯的約束與限制，以集合的整體直接逼近的方式完成非確定不完整信息條件下的知識推理，在基于粗糙集的知識理論中，知識被認為是一種對對象進行分類的能力[1]。由不可分辨關系來定義粗糙集合是粗糙集研究者的早期研究，隨著近似空間由決策信息系統來表示，擴展到在一個決策信息系統上用屬性來定義粗糙集合。

決策信息系統通常描述為一個四元組S=(U，Q，V，F)，其中U≠Φ為對象的非空有限集合；Q≠Φ為屬性集，分為條件屬性集C和決策屬性集D，Q=C∪D，C∩D=Φ；V是所有屬性值的并集V=∪q∈QVq，Vq是屬性q的值域；F是一個信息函數F∶U×Q→V，為每個對象的每個屬性賦值，對所有x∈U，每個q∈Q均有F(x， q)∈Vq。

2 分類與約簡

決策信息系統約簡的主要目的在于去除冗余信息，同時保留原決策信息系統的分類能力不變。約簡后的決策信息系統產生新的決策規則，這類決策規則的前提信息與結論信息可能不同于約簡前的任何一條決策規則，但它們經推理能得到相同或相近的結果。

定義1 決策信息系統S=(U，C∪D)，U為論域，C為條件屬性集合，D為決策屬性集合，由條件屬性和決策屬性定義的不可分辨關系對U產生不同的分類。

(1)根據條件屬性集C對U的分類稱為條件分類，表示為U/C={X1，X2，…，X|U/C|}，其中每一個成員Xi為一個條件類。

(2)根據決策屬性集D對U的分類稱為決策分類，表示為U/D={Y1，Y2，…，Y|U/D|}，其中每一個成員Yj為一個決策類。

定義2 決策信息系統S=(U，Q=C∪D，V，F)，決策屬性集D對條件屬性集C的依賴度或論域U的分類率γ(C，D)定義[2]為

γ(C，D)=|POS(C，D)|/|U|

其中，POS(C，D)=∪Y∈U/DCY=∪{X|XY∧X∈U/C∧Y∈U/D}。

POS(C，D)表示了U/C在U/D中的正區域(或稱D的C正區域)，定義了一個分類關于另一個分類的區域包含性。

分類率是決策信息系統一致性的衡量，數據不一致性使分類率小于1。不一致性是由于存在條件屬性相同，而決策屬性不同的矛盾對象。

定義3 決策信息系統S=(U，Q=C∪D，V，F)，條件屬性集合C的約簡B是C的一個非空子集合，滿足[3]

（1）POS(B，D)=POS(C，D)；

（2）對任意a∈B，POS(B-{a}，D)≠POS(C，D)。

由約簡的定義可知，屬性集BC是決策信息系統S的一個約簡，當且僅當B中的每一個屬性對于D均是不可缺少的，說明B是一個滿足條件（1）的最小屬性集合。

條件屬性集從C到B的約簡是一個屬性逐步被約簡的過程，而一個屬性能否被約簡可根據屬性重要性來評判。

定義4 決策信息系統S=(U，Q=C∪D，V，F)，BC，對屬性a∈B，在經典粗糙集理論下的屬性重要性定義為

SGF(a，B，D)=γ(B，D)－γ(B－{a}，D)

SGF(a，B，D)反映了將屬性a加入屬性集B中后B和D之間依賴程度的改變，從而體現出屬性a對決策的重要程度。屬性重要性可作為屬性集合C逐步約簡的重要啟發信息。代數約簡的思想認為，一個屬性可被約簡，當且僅當其屬性重要性為0。

定理1 決策信息系統S=(U，Q=C∪D，V，F)，BC，隨著屬性移出集合B，分類率γ(B，D)單調減少，即有

a∈(C－B)→γ(B，D)≤γ(B∪{a}，D)

證明：根據條件屬性不可分辨關系的定義，顯然有IND(B∪{a})IND(B)，也就是U/IND(B∪{a})細分U/IND(B)。

對任意Y∈U/D，由細分概念有BY(B∪{a})Y，即|BY|≤|(B∪{a})Y|。從而，

∑Y∈U/D|BY|≤∑Y∈U/D|(B∪{a})Y|

|POS(B，D)|≤|POS(B∪{a}，D)|

所以，γ(B，D)≤γ(B∪{a}，D)。

證畢。

約簡過程是逐步進行的，代數約簡的思想是基于屬性約簡過程中保持正區域的不變性。隨著屬性的逐步被約簡，由條件屬性決定的條件分類的粒度增大，由定理1可知，依賴度呈下降趨勢，具有非嚴格單調遞減性。

3 屬性約簡整體性質

約簡在實質上即為一個泛化過程，隨著屬性被約簡掉，約簡過程中伴隨著條件類的歸并，使得條件分類的粒度增大，分類率整體呈下降趨勢。

決策信息系統S=(U，Q=C∪D，V，F)，其中U={u1，u2，…，u|U|}，C={a1，a2，…，a|C|}，S的所有約簡構成的集合為RED(S)={C1，C2，…，CK}，CiC，1≤i≤k，由屬性核的概念可知，S的核為Core(S)=∩RED(S)。

根據定理1，約簡過程為條件分類中條件類不斷歸并的過程，形成粒度更大的條件分類，可表示為條件分類劃分的細分層次關系。

顯然，所有約簡的條件分類為U/C1，U/C2，…，U/CK，它們均被U/C所細分，而所有約簡的條件分類U/C1，U/C2，…，U/CK細分S的核條件分類U/CORE(S)，如圖1所示。

細分層次關系圖中節點為根據條件屬性對U的某一層次條件分類劃分，由右至左，每一分類細分其左邊層次的任一分類，同時也是分類的歸并過程。

定理2 決策信息系統S=(U，Q=C∪D，V，F)，則S的所有約簡條件分類的和為核條件分類U/CORE(S)。

證明：對任意C′，C″C，由定義1，顯然有U/C′細分U/C″，當且僅當C′C″。

根據核的定義[2]可知，C1CORE(S)，C2CORE(S)，…，CKCORE(S)。U/CORE(S)被U/C1，U/C2，…，U/CK所細分，而CORE(S)=C1∩C2∩…∩CK，即核CORE(S)是被C1，C2，…，CK包含的最大屬性集合，從而U/CORE(S)為被U/C1，U/C2，…，U/CK所細分的最大劃分。所以，U/CORE(S)為U/C1，U/C2，…，U/CK的和。

證畢。

該定理表明，核是被U/C1，U/C2，…，U/CK細分的最大屬性集合。

定理3 決策信息系統S=(U，Q=C∪D，V，F)，則S的所有約簡條件分類的積為所有約簡的并集。

證明：對任意C′，C″C，由定義1，顯然有U/C′細分U/C″，當且僅當C′C″。

令C*=C1∪C2∪…∪CK，則可知U/C1，U/C2，…，U/CK被U/C*所細分。又由RED(S)*定義可知，RED(S)*是包含C1，C2，…，CK的最小屬性集合，從而U/C*為細分U/C1，U/C2，…，U/CK的最小劃分，所以，U/C*為U/C1，U/C2，…，U/CK的積。

證畢。

由定理可知，C－C*中的屬性不包含于任一約簡中，是可以完全被約簡的屬性。積與和的概念通過層次細分關系體現了一個決策信息系統中所有屬性整體約簡的性質。

4 歸并分析

根據類的歸并，約簡后條件分類對正區域的影響可通過類的歸并來描述。

性質1 決策信息系統S=(U，Q=C∪D，V，F)，U為論域，C為條件屬性集合，D為決策屬性集合。

（1）被同一決策類完全包含的任意兩個條件類合并，正區域不變。

設Xi，Xj∈U/C，Yk∈U/D，使P(Yk/Xi)=1且P(Yk/Xj)=1，則Xi與Xj合并后，正區域不變。

證明：由P(Yk/Xi)=1，有|Yk∩Xi|/|Xi|=1，故XiYk，同理，XjYk，則Xi∪XjYk，|Yk∩(Xi∪Xj)|/|Xi∪Xj|=1，P(Yk/(Xi∪Xj))=1。

所以，Xi與Xj合并后正區域不變。

（2）屬于邊界區域的任意兩個條件類合并，正區域不變。

設Xi，Xj∈U/C，對Yk∈U/D，P(Yk/Xi)＜1且P(Yk/Xj)＜1，則Xi與Xj合并后，只對邊界區域有影響，正區域不變。

證明：由P(Yk/Xi)＜1，有|Yk∩Xi|/|Xi|＜1，故存在a∈U∧a∈Xi，但aYk，同理，存在b∈U∧b∈Xj，但bYk。因Xi∩Xj=Φ，有(a，b∈U)∧(a，b∈Xi∪Xj)，|Yk∩(Xi∪Xj)|/|Xi∪Xj|＜1，故P(Yk/(Xi∪Xj))＜1，所以Xi與Xj合并后正區域不變。

直觀地來說，屬于邊界區域的條件類Xi，Xj的合并沒有改變Xi和Xj中的決策不一致性，它們還是構成邊界區域，對正區域沒有影響。

（3）其他情況下，兩個條件類的合并都將使正區域發生變化。其表現在：①屬于正區域的條件類與屬于邊界區域的條件類合并，產生的新條件類仍然具有原有決策的不一致性；②包含于不同決策類的正區域條件類的合并，由于兩者決策屬性的不一致性，新的條件類產生了新的決策不一致性。這兩種情況都必然使正區域縮小。

歸并分析說明了約簡過程中一個屬性能否被約簡的根本原因，這一概念化模式實際上可以推廣到各種推廣的粗糙集合模型中，只有復雜程度和描述性質的差別。

5 屬性的約簡性

對決策信息系統S=(U，Q=C∪D，V，F)，設條件屬性集合C={c1，c2，…，cn}，計算各個條件屬性的固有重要性SGF(ci，C，D)，1≤i≤n。不失一般性，設定：

SGF(ci，C，D)≠0，1≤i≤p

SGF(ci，C，D)=0，p+1≤i≤n

定理4 決策信息系統S=(U，Q=C∪D，V，F)，U為論域，C為條件屬性集合，D為決策屬性集合，條件屬性a∈C是S的核屬性的充要條件為SGF(a，C，D)≠0。

證明：

（1）必要性。條件屬性a∈C是S的核屬性，若有SGF(a，C，D)=0，則a可被約簡，與它是核屬性矛盾，所以SGF(a，C，D)≠0。

（2）充分性。條件屬性a∈C，SGF(a，C，D)≠0，這說明從C中約簡屬性a必然產生新的不一致性。假定是由Xi，Xj∈U/C兩個條件類的歸并引起的，這同時也表明了Xi和Xj兩個條件類除了在屬性a上具有不同值，在C-{a}內的屬性上具有相同值。

由此看來，在隨后的約簡過程中，無論何時屬性a被約簡掉都將導致Xi和Xj的歸并，從而產生新的不一致性。

所以，屬性a在整個約簡過程中均是不能被約掉的。

證畢。

該定理也說明了固有屬性重要性不為0的屬性，在從C開始的根據屬性重要性進行的任何約簡過程中都不能被約簡，它們為核屬性。

參考文獻：

[1]Pawlak Z. Rough Sets[J]. International Journal of Computer and Information Sciences，1982，11(5):341-356.

[2]Pawlak Z. Rough Set: Theoretical Aspects of Reasoning about Data[M]. Dordrecht: Kluwer Academic Publishers， 1991.

[3]Pawlak Z， GrzymalaBusse J， Slowinski R， et al. Rough Sets[J]. Communications of ACM， 1995，38(11):89-95.

作者簡介：

王加陽(1963-)，男，主要研究方向為智能計算與決策支持；陳松喬(1945-)，男，教授，主要研究方向為智能信息系統與決策支持；羅安(1956-)，男，教授，主要研究方向為電力系統與決策支持。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文