張靜

（江蘇科技大學(xué) 計算機科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003）

粗糙集 （Rough Set）理論由波蘭學(xué)者Z.Pawlak于1982年提出，是一種處理不精確、不相容和不完全數(shù)據(jù)的新的數(shù)學(xué)工具[1]。它已經(jīng)在決策與分析、故障診斷、模式識別、數(shù)據(jù)挖掘、系統(tǒng)建模、動態(tài)目標(biāo)識別及跟蹤等領(lǐng)域取得了很大的成功[2]。屬性約簡是粗糙集理論的核心內(nèi)容之一。目前已經(jīng)出現(xiàn)了很多屬性約簡的方法，例如基于正區(qū)域的屬性約簡[3]、基于差別矩陣的屬性約簡[4]、基于信息熵的屬性約簡[5]、基于分布的屬性約簡及基于近似的屬性約簡[6]、基于云模型的約簡方法[7]、基于相對粒度的約簡算法發(fā)[8]等。本文通過將決策信息系統(tǒng)樹形化，并定義了在此樹形結(jié)構(gòu)上的屬性約簡，發(fā)現(xiàn)屬性可約簡并不需要再次求得下上近似集，可直接由等價類所包含的決策屬性來決定，由此可增加屬性約簡的效率。進而給出了一種基于編碼解空間結(jié)構(gòu)的求粗糙集屬性約簡最優(yōu)解的算法，并發(fā)現(xiàn)編碼解空間結(jié)構(gòu)對求取最優(yōu)解及次優(yōu)解均有好處。

1 粗糙集中屬性約簡滿足的條件

粗糙集的主要研究對象是決策表，一個決策表就是一個決策信息系統(tǒng)。下面是Pawlak關(guān)于決策表以及下上近似集的定義：

定義 1:五元組 S=（U，C，D，V，f）是一個決策表，其中 U={x1，x2，x3，…，xn}表示研究對象的非空有限集；D 表示決策屬性C∪D→V是一個信息函數(shù)，它給U中每一個對象的所有屬性賦予信息值，即對?x∈U，a∈C∪D，有 f（x，a）∈Va；每一個屬性子集P?（C∪D）決定了一個二元不可分辨關(guān)系：

IND（P）={（x，y）|（x，y）∈U×U，?a∈P∧f（x，a）=f（y，a）}（1）

關(guān)系 IND（P）構(gòu)成了 U的一個劃分，用 U/IND（P）表示，簡記為 U/P，U/P 中的元素[x]p={y|?a∈P，f（x，a）=f（y，a）}稱為 U關(guān)于P的等價類。

定義 2:在決策表 S=（U，C，D，V，f） 中， 設(shè)?R?C∪D，X?U 記 U/R={R1|R2，…，RL}，則稱 R（X）=U{Ri|Ri∈U/R，Ri?X}為 X 關(guān)于 R 的下近似集，R （X）=∪{Ri|Ri∈U/R，Ri∩X≠φ}為X關(guān)于R的上近似集。

根據(jù)下上近似集的定義可以得出下面兩種基于統(tǒng)計意義的推理規(guī)則：如果對象x在R上的值滿足某個條件，x就屬于X（規(guī)則1）；如果對象x在R上的值滿足某個條件，x就不屬于 X（規(guī)則 2）。

考慮到這個因素，給出了下面兩個粗糙集屬性約簡的定義：

定義 3:在決策表中 S=（U，C，D，V，f），若?B?C，并且B（X）=C（X），B（X）=C（X）；?b∈B 均有（B-）（D）≠C（D）或者（B-）（D）≠C（D），則稱 B 是 C 相對于 D 的強屬性約簡。 所有C相對于D的屬性強約簡的集合記為StrongReduct（C，D）。

定義 4:在決策表中 S=（U，C，D，V，f），若?B?C，并且B（X）=C（X）；?b∈B 均有（B-）（D）≠C（D），則稱 B 是 C 相對于D的弱屬性約簡。所有C相對于D的屬性弱約簡的集合記為 WeakReduct（C，D）。

強屬性約簡可以保證約簡后這兩個規(guī)則都不變，而弱屬性約簡只能保證約簡后規(guī)則1不變。為了得到通過等價類判斷屬性是否可被約簡的規(guī)則，首先給出了決策信息系統(tǒng)的樹形表示，以及樹形表示約簡算法。

2 決策信息系統(tǒng)的樹形表示以及此樹形表示約簡的求解

決策信息系統(tǒng)的樹形表示：

圖1 決策信息系統(tǒng)樹形表示圖Fig.1 A tree representation of decision information system

此樹（如圖1所示）是依據(jù)不可分辨關(guān)系建立的。從上往下，除最后一層分別代表屬性層，大寫字母代表屬性（為了以示和屬性集合的區(qū)別用小一號的大寫字母表示），小寫字母代表屬性的值。最后一層代表對象層，d代表此對象的決策屬性值。根據(jù)此表示方法易得，從上至下的每一條路徑pi（如…c1b1a2）代表著一個等價類。dd代表等價類的決策屬性值。?R?C，U/R={R1，R2，…，RL}表示由條件屬性集R對論域U的劃分，則根據(jù)不可分辨關(guān)系可建立雙射pc:P→U/R，其中P={pi}。 dd（pi）=1 代表著等價類 pc（pi），pc（pi）?R（X）；dd（pi）=2 代表著等價類 pc（pi），pc（pi）?R（X）；dd（pi）=0 代表著等價類 pc（pi），pc（pi）?R（XC）。 若 x 是決策信息系統(tǒng)中的一個對象（處于決策信息系統(tǒng)樹形圖的最底層），則 dd（x）=d（x）。

決策信息系統(tǒng)的樹形表示約簡算法：

定義 5:在決策表 S=（U，C，D，V，f）中，A∈C，pi是一條路徑且最后一個節(jié)點是屬性A中的值如:

令Path（A）最后一個節(jié)點是屬性A中的值得路徑的集合，?pi，pj∈Path（A），則 handle（pi，A）=handle（pj，A）。

易證，?pi，pj∈Path（A），pc（pi）?pc（handle（pi，A））并 且pc（pj）?pc（handle（pj，A））。 下面給出由 dd（pi）和 dd（pj）求dd（handle（Path（A）））的算法，如圖 2 所示（易證）：

圖 2 dd（handle（path（A）））的取值表Fig.2 Value table of dd（handle（path（A）））

其中 2 的情況會同時縮?。–-{A}）（X）和（C-{A}）（XC）（如圖 3 所示）；3 的情況會縮小 （C-{A}）（XC）；4 的情況會縮?。–-{A}）（X）；只有 1 的情況是滿足約簡條件的（如圖 4）。所以當(dāng)滿足2、3、4的時候?qū)傩圆豢梢员粡娂s簡，只有滿足①的情況屬性A才能被強約簡。這個結(jié)論也是易證的。有了這個結(jié)論我們就可以僅僅通過等價類和決策屬性就可以判斷在此樹形表示中是否可被約簡。

圖3 屬性A不可被強約簡圖Fig.3 Unable to be strong reduction graph of A

圖4 屬性A可被強約簡圖Fig.4 Can be strong reduction graph of A

根據(jù)樹形表示與等價類之間的關(guān)系可得若某屬性在此表示下可被強約簡則，它必可在決策信息系統(tǒng)中也可被強約簡；若某屬性在此表示下不可被強約簡則，它必可在決策信息系統(tǒng)中也不可被強約簡。

對每一個屬性強約簡（RE，C-RE），其中C-RE是強約簡掉的屬性，RE是保留下來的屬性。Random（RE）是保留下來的屬性的隨機排列，Random（C-RE）是強約簡掉的屬性的隨機排列（Random（RE），Random（C-RE））。 根據(jù)排列可以畫出一個屬性強約簡的樹形圖，并根據(jù)此樹形圖的屬性約簡又可得到最終的屬性約簡。（易證）

3 樹形表示屬性約簡分析

定義 6:在決策表 S=（U，C，D，V，f） 中，C 相對于 D 屬性強約簡的核集定義為

在依據(jù)決策系統(tǒng)樹形圖的屬性約簡中，令C相對于D第一次不可被強約簡的屬性的集合為NStrongfirst（C，D）。

證明：①?NSfi∈NStrongfirst（C，D）?NSfi∈StrongCore（C，

使用反證法：若?NSfi?∩REj，則?j，NSfi?REj即 NSfi可以被約簡，由于屬性的約簡與順序無關(guān)。所以NSfi可被第一次約簡。矛盾所以式子成立。

②?SCi∈StrongCore（C，D）?SCi∈NStrongfirst（C，D）

若?SCi∈StrongCore（C，D），SCi不可被任何約簡，自然不可被第一次約簡，即SCi∈NStrongfirst（C，D）。 定理證明完畢。

定義 7:在決策表 S1=（U1，C1，D1，V1，f1）中，A1?C1，B1?C1且 A1∪B1=C1，其中 B1={b1，b2，…，bn}。 在決策表 S2=（U2，C2，D2，（V1）bn}，?x∈U2，若 a∈A1∪D1， f2（x，a）=f1（x，a）；若 a=b，f2（x，b）=（ f1（x，b1），f1（x，b2），…，f1（x，bn））。向這樣通過 S1定義 S2的過程稱為決策表 S1的屬性合并， 記為 S2=AmalAttr（S1，B，b）。其中b是由B合并的屬性。

定理二：有決策表 S1=（U1，C1，D1，V1，f1）、決策表 S2=（U2，C2，D2，V2，f2） 以及屬性集合 A1、B， 其中 A1?C1，B?C1，A1∪B=C1，S2=AmalAttr（S1，B，b），則 C2=A1∪b，IND（S1）=IND（S2）。由決策表的屬性合并的定義以及不可分辨關(guān)系的定義很容易證。

由上面兩條定理可得如下推論：

推論 1：有決策表 S=（U，C，D，V，f），以及屬性集合 A?C和B?C，其中A?B，如果A不可被約簡，則B也不可被約簡。

證明：S1=AmalAttr （S，A，a）=（U1，C1，D1，V1，f1）， 其中 C1=（C-A）∪{a}。 由定理二可知 IND（S）=IND（S1）。 根據(jù)上下近似集的定義可知 C（X）=C1（X），C（X）=C1（X）。 由于 C1-{a}=C-A，根據(jù)屬性合并的定義可知 （C1-{a}）（X）=（C-A）（X），（C1-{a}）（X）=（C-A）（X）。由屬性約簡的定義可知若A在S中不可約，則 a 在 S1中不可約。那么 a∈NStrongfirst（C1，D1）。根據(jù)定理一可知 a∈StrongCore（C1，D1），所以在 S1中任何包含 a 的屬性集都不可約。所以（B-A）∪{a}在S1中不可約。根據(jù)屬性合并的定義可知（C1-（B-A）∪{a}）（X）=（C-B）（X），（C1-（B-A）∪{a}）（X）=（C-B）（X）。 又由于 C（X）=C1（X），C（X）=C1（X），根據(jù)屬性約簡的定義可知若（B-A）∪{a}在S1中不可約，則B在S中不可約。證畢。

通過以上的分析可知，某一個屬性子集是否可被強約簡可通過在此信息系統(tǒng)中將此屬性子集合并后得到的信息系統(tǒng)中，由此屬性子集生成的新的屬性在該信息系統(tǒng)樹形表示中是否可被第一次強約簡決定。由于在信息系統(tǒng)樹形表示中屬性的約簡只由等價類和決策屬性就可以決定了，所以在信息系統(tǒng)中也可以通過等價類以及決策屬性就可以決定了。

若這個屬性子集不可被強約簡，則包含它的屬性子集也不可被強約簡（即可被剪枝，假設(shè)屬性只有ABCD，則屬性子集的剪枝過程如圖5所示）。若在信息系統(tǒng)樹形表示中不能被第一次強約簡，則該屬性屬于信息系統(tǒng)屬性強約簡的核中。核是不可被約簡的屬性，除核之外的屬性都是可被約簡的屬性。

圖5 屬性子集剪枝過程圖Fig.5 Attribute subset pruning process diagram

4 結(jié) 論

屬性約簡在粗糙集理論研究中發(fā)揮著巨大的作用。本文從樹形結(jié)構(gòu)考慮給出了決策信息系統(tǒng)的樹形表示。基于本文提出的樹形結(jié)構(gòu)文中進一步的得出了一個判斷屬性是否可被約簡的好的方法，通過理論分析，本文提出的屬性約簡算法可以大大的減少屬性搜索的步驟從而降低屬性約簡所需要的時間。

[1]Pawlak Z.Rough Sets-theoretical aspects of reasoning about data[M].Kluwer Acadamic Publisher，1991.

[2]Pawlak Z.A rough set view on Bayes’theorem[J].International Journal of Intelligent Systems，2003，18（5）:487-498.

[3]Pawlak Z.Rough set[J].Communication of the ACM，1995，38（11）:89-95.

[4]Skowron A，Rauszer C.The discernibility matrices and functions in information systems[M].Intelligent Decision Support Handbook of Applications and Advances of the Rough Sets Theory.Kluwer Academic Publishers，1992.

[5]Wang G Y，Yu H，Yang D C.Decision table reduction based on conditional information entropy[J].Chinese Journal of Computer，2002，25（7）:759-766.

[6]Zhang W X，Mi J S，Wu W Z.Knowledge reductions in inconsistent information systems[J].Chinese Journal of Computer，2003，26（1）:12-18.

[7]代勁，何中市.基于云模型的決策表規(guī)則約簡[J].計算機科學(xué)，2010，37（6）:265-267.DAI Jin，HE Zhong-shi.Rules reduction for decision table based on cloud model[J].Computer Science，2010，37（6）:265-267.

[8]徐久成，史進玲，孫林.一種基于相對粒度的決策表約簡算法[J].計算機科學(xué)，2009，36（3）:205-207.XU Jiu-cheng，SHI Jin-ling，SUN Lin.Attribute reduction algorithm based on relative granularity in decision tables[J].Computer Science，2009，36（3）:205-207.