區間值決策信息系統中基于正域的屬性約簡

陳華峰，龍建武，瞿先平,

(1.重慶電訊職業學院 基礎部， 重慶 402247；2.重慶理工大學 計算機科學與工程學院， 重慶 400054)

粗糙集理論作為一種有效的數據挖掘工具，自20世紀80年代由波蘭數學家Pawlak[1]提出以來，其對知識的自動獲取、機器學習以及模式識別等多個科學研究領域的發展都起到了積極的推動作用。該理論主要是基于一個等價關系對論域進行劃分，然后通過一對上、下近似算子來描述任意對象集的近似范圍，以此從數據庫挖掘出以規則形式進行表達的知識。隨著粗糙集理論研究及實際應用的不斷深入，經典的Pawlak 粗糙集模型存在著一定的不足之處，為此大量的學者對廣義粗糙集模型進行了深入的研究[2-4]。常見的方法是將經典粗糙集模型中的等價關系推廣為一般二元關系，也即是將等價關系所需滿足的3條(自反性、對稱性、傳遞性)刪除1條或多條，從而構造滿足特定要求的二元關系，以此建立基本信息粒結構[5-6]。也有通過鄰域來建立基本信息粒的，即按照某一度量方式得到小于給定的閾值的對象構成的集合為一個基本信息粒[7-8]。還有學者結合實際問題的需要，提出了多粒度粗糙集方法[9-10]，這些方法常用于不完備信息系統或廣義值信息系統的知識發現研究中。

信息系統作為數據描述的基本形式，是基于粗糙集理論研究的基礎[11]。隨著數據的多元化和復雜化，用簡單的實數值來描述對象和屬性之間的關系明顯不夠，為此學者們分別對模糊值信息系統[12]、模糊決策序信息系統[13]、直覺模糊信息系統[14-15]、基于覆蓋的決策信息系統[16]等進行了系統的研究。這些廣義的信息系統的研究以及應用極大地推動了粗糙集理論的發展，讓粗糙集理論在解決實際問題時展現出了強大的應用能力。由于在數據采集過程中不可避免地會有許多不必要的或者冗余知識混入其中，直接對大規模復雜數據進行研究，不僅會對資源造成大量的浪費，甚至有可能是一項不可能完成的任務，因此如何對數據進行必要的篩選，在保持數據所蘊含的知識不變或極小損失的同時，盡可能地降低數據規模，是一個值得研究的課題[17]。

屬性約簡是粗糙集理論研究的核心問題之一，可以簡單理解為在保持知識庫分類能力不變的情況下，刪除其中的一些不相關或不要的屬性，從而達到降低數據規模的目的[18]。由于尋找屬性約簡是NP-hard問題，解決這類問題的一般是采用啟發式搜索，通過在算法中加入啟發式信息，縮小問題的搜索空間，進而獲得最優解或近似解，因此啟發式約簡方法被廣泛應用于各類基于粗糙集的屬性約簡問題中[19-21]。對于決策信息系統來講，決策規則是研究者最關注的話題，其中又尤以確定性規則最為重要，那么如何以盡可能少的條件屬性獲取相當水平的確定性規則，即基于正域的屬性約簡值得研究。為此，本文將對區間值決策信息系統中基于正域的屬性約簡方法進行討論，并設計相應的啟發式屬性約簡算法，然后結合案例分析對模型建立以及利用算法搜尋約簡的過程進行演示。

1 預備知識

本節介紹一些研究所需要基本知識，包括信息系統與粗糙集的基本定義，以及屬性約簡的相關概念等。

設四元組S=(U,AT,V,f)為一個信息系統，其中U={x1,x2,…,xn}為論域，是非空有限對象集，AT={a1,a2,…,am}為非空有限屬性集，V為有限值域，f:U×AT→V一個信息函數，它給定U中的任意對象x的屬性值。對任意的A?AT可以得到一個不可分辨關系，即

IND(A)={(x,y)∈U×U∶?a∈A,f(x,a)=f(y,a)}

則U中關于屬性A所有與x具有不可分辨關系IND(A)的對象的集合為

[x]A={y∈U,(x,y)∈IND(A)}

即x關于屬性集A的等價類。顯然IND(A)為一個等價關系，通常簡寫為RA或R。基于這一基本劃分，建立經典的粗糙集模型如下：

定義1[1]設S=(U,AT,V,f)為一個信息系統，對任意的X?U和A?AT，則可得X關于屬性集A的上、下近似集分別為：

基于這一對近似算子可以得到其他的粗糙集區域，其中正域為

在決策分析中正域有著極為突出的地位，是一個廣受關注的研究課題。一個信息系統S中如果加入決策屬性，則稱之為一個決策信息系統即S=(U,AT∪D,V,f)，其中AT∩D=?。更一般地，如果對象關于條件屬性的取值不是一個單一的實數值，而是一個區間數(即f(x,a)=I=[l,r]，其中l≤r)，則稱之為區間值決策信息系統，本文將在該信息系統中展開討論。對于一個信息系統來講，不同屬性的重要性是不一樣的，其中不免有一些不重要甚至冗余的屬性，常通過基于屬性構造的二元關系來衡量屬性是否必要。

定義2[11]設S=(U,AT,V,f)為一個信息系統，對任意的A?AT且a∈A，如果

IND(A)=IND(A-{a})

則稱a在A中是不必要的屬性，否則稱a為A中是必要的屬性，不可以約簡。如果A中的每一個屬性都是必要的，則稱A是獨立的，否則稱為依賴的。基于此可以得到，對任意的屬性集B?A，若B是獨立的，且IND(B)=IND(A)，則稱B為A的一個約簡，記作Red(A)。對于一個屬性集A來說，約簡一般不是唯一的但一定存在，所有約簡的核的交集稱為核，記作Core(A)。

在決策信息系統中，需要研究條件屬性的分類和決策屬性分類之間的關系，此時需要對相對約簡和相對核進行討論。

定義3[11]設S=(U,AT∪D,V,f)為一決策信息系統，對任意的A?AT，則D關于條件屬性集A的正域為：

它表示論域U中所有根據RA分類的信息，可以準確劃分到決策屬性D的等價類中去的對象的集合。類似地，可以定義任意的a∈A是否必要，如果

posA(D)=posA-{a}(D)

則稱a為A中D不必要的，否則稱a為A中D必要的。如果A中的每一個屬性都是D必要的，則稱A為D獨立的。對任意的B?A，如果B是D獨立的，且posA(D)=posB(D)則稱B為A的D約簡。而A的所有D約簡的交集稱為A的D核，記為CoreA(D)，它所描述的是A中所有D必要的原始關系構成的集合。

2 區間值決策信息系統中基于正域的屬性約簡方法

本節將在區間值決策信息系統討論基于正域的屬性約簡方法。由于在區間值決策信息系統基于等價關系的劃分已不再有效，因此在對象之間建立相似性度量，并設定一個閾值以此得到一個鄰域，然后展開本文的討論。

對于任意的兩個區間數，其相似性度量方式有多種，文獻[22]利用包含度定義了任意兩個區間數之間的關系。設I1=[l1,r1]和I2=[l2,r2]為兩個區間數，則I1關于I2的區間包含度為

其中：ρ(I1)=r1-l1，I1∩I2=[max{l1,l2}, min{r1,r2}]。

特別地，如果max{l1,l2}≥min{r1,r2}，則ρ(I1∩I2)=0。此外，Dai從另外一個角度定義了I1相對I2相似度，也正是本文所采用的定義方式。

定義4[22]設I1=[l1,r1]和I2=[l2,r2]為兩個區間數，則I1大于I2的概率定義為

基于這一度量，Dai給出了I1和I2之間的相似性度量，即

s(I1,I2)=1-|P12-P21|

該度量是自反的，即s11=1,對稱的s12=s21。基于這一度量，如果給定一個閾值δ∈(0,1]，則可以得到相應的δ領域。

定義5設S=(U,AT∪D,V,f)為一個區間值決策信息系統，對任意的A?AT，給定閾值δ∈(0,1]，則任意的x∈U關于條件屬性集A的δ鄰域為：

δA(x)={y∈U:sa(x,y)≤δ,?a∈A}

其中sa(x,y)表示對象x和y關于條件屬性a的值之間的相似度，利用定義4所得。利用類似于經典的粗糙集模型的方法在區間值決策信息系統中建立粗糙集模型。

定義6設S=(U,AT∪D,V,f)為一個區間值決策信息系統，對任意的A?AT，給定閾值δ∈(0,1]，則Dj∈U/D基于鄰域的下、上近似集分別為：

在實際應用中要找到一個信息系統的所有約簡并不是一件簡單的事情，有時只需找到一個約簡即可，因此可設計啟發式算法來尋找滿足條件的約簡。而設計啟發式算法需要設計一個合適的起點以及找到一個恰當的啟發式信息，通常采用分類質量來度量某一個條件屬性對正域的影響。

定義7設S=(U,AT∪D,V,f)為一個區間值決策信息系統，對任意的A?AT，δ∈(0,1]，則D關于A的分類質量為：

定義8設S=(U,AT∪D,V,f)為一個區間值決策信息系統，對任意的δ∈(0,1]，A?AT且a∈A，則屬性a在屬性A中關于決策屬性D的相對重要度為：

對任意的屬性a∈A有Sig(a,A,D)∈[0,1]。當Sig(a,A,D)=0時，意味著a在D決策中是不必要的，因此可以得到決策值信息系統中基于正域的屬性約減。即滿足如下2個條件的屬性集：

在設計搜尋一個約簡的啟發式算法時，從空集出發，以屬性的相對重要度為啟發式信息設計啟發式算法，如算法1所示。

算法1 區間值決策信息系統中基于正域的的啟發式屬性約簡算法

輸入：一個區間值決策信息系統S=(U,AT,V,f)，以及閾值δ；

輸出：該信息系統的一個約簡Red(AT)

1. let Red(AT)=?; //初始化約簡為空

2. for eacha∈ATdo

3. compute:Sig(a,AT,D);

4. end

7. Red(AT)=Red(AT)∪{b};

8. end

9. for eacha∈Red(AT) do

11. Red(AT)=Red(AT)-{a};

12. end

13. end

16. return：Red(AT).

3 實例分析

基于以上討論，本節用1個實例來展現在區間值信息系統的粗糙集建模，以及各個度量的具體計算方式，并按照算法1求解給定區間值決策信息系統的1個約簡。本案例分析中所采用的數據改編自文獻[23]。

例1給定一個區間值決策信息系統S，其中U={x1,x2,…,x10}表示10個對象，AT={a1,a2,a3,a4}表示條件屬性，D為決策屬性，有關該決策信息系統的具體數據如表1所示。

表1 某區間值決策信息系統

由定義4的相似度定義可以計算任意兩個對象關于任意屬性的相似度。為不失一般性，選取x1和x2關于屬性a1為例，即I1=[0.5,0.8]，I2=[0.4,0.7]，則可得

則

s(I1,I2)=1-|0.67-0.33|=0.66

即x1和x2關于屬性a1的相似度為0.66。類似地，可以得到任意的兩個對象關于所有屬性的相似度。如果在實際應用中給定一個閾值δ∈(0,1]，則可以由定義5得到一個鄰域。在接下來的研究中不妨取δ=0.65，則可以得δAT(x)對任意的x∈U，結果如下：

δAT(x1)={x1,x2,x4,x5,x6,x8,x10}

δAT(x2)={x1,x2,x5,x6}

δAT(x3)={x3,x7,x9}

δAT(x4)={x1,x4,x5,x8}

δAT(x5)={x1,x2,x4,x5,x6,x8}

δAT(x6)={x1,x2,x5,x6}

δAT(x7)={x3,x7,x9}

δAT(x8)={x1,x4,x5,x8}

δAT(x9)={x3,x7,x9}

δAT(x10)={x1,x10}

由表1可知論域U關于決策屬性分為兩類，即U/D={D1,D2}，q且

D1={x1,x4,x5,x6,x8,x10}

D2={x2,x3,x7,x9}

通過定義6可以得到決策屬性D關于條件屬性集AT的正域為

則

進一步可以得到D關于AT的分類質量為

基于以上的計算，進一步計算每一個屬性的相對重要性為

Sig(a1,AT,D)=0

Sig(a2,AT,D)=0.33

Sig(a3,AT,D)=0,

Sig(a4,AT,D)=0

接下來利用分類質量來對屬性集進行檢測。顯然空集不是一個約簡，因此選取屬性度重要度最大的屬性a2，即

Red(AT)={a2}

進一步檢驗，有

由計算結果知{a1,a2}和{a2,a3}都有可能是約簡，接下來進行算法9～13行的檢驗，有

顯然都是不可進一步去掉的屬性，也就是說{a1,a2}和{a2,a3}都是在閾值δ=0.65時保持關于決策屬性正域的約簡，即

由于啟發式算法的目的是找到一個滿足條件的約簡即可，因此該區間值決策信息系統可能還存在其他的約簡，一般可以基于辨識矩陣的方法求解。但當只需要找到一個約簡的時候，啟發式約簡算法更為簡潔有效。因此，在實際應用中如果只需搜尋一個滿足條件的約簡時，可以將本算法作為參考。

4 結束語

本文在區間值決策信息系統基于鄰域建立了粗糙集模型，為了刪除在數據采集過程中存在的一些不必要的或冗余的條件屬性，本文基于決策屬性關于條件屬性的正域，設計了一種啟發式屬性約簡算法。通過一個案例的求解，對區間值決策信息系統的粗糙集建模過程，以及基于本文所設計的啟發式屬性約簡算法過程進行了演示。實驗結果表明：給定一個區間值信息系統，本文所給出的方法可以找到一個基于正域得到的屬性約簡。在接下來的研究中，將進一步討論區間值決策信息系統中的其他約簡方法，并在帶模糊決策的區間值信息系統的研究屬性約簡方法。