區(qū)間值決策信息系統(tǒng)中基于正域的屬性約簡

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

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

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

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

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

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

定義2[11]設(shè)S=(U,AT,V,f)為一個信息系統(tǒng)，對任意的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)。

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

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

它表示論域U中所有根據(jù)RA分類的信息，可以準確劃分到?jīng)Q策屬性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必要的原始關(guān)系構(gòu)成的集合。

2 區(qū)間值決策信息系統(tǒng)中基于正域的屬性約簡方法

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

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

其中：ρ(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]設(shè)I1=[l1,r1]和I2=[l2,r2]為兩個區(qū)間數(shù)，則I1大于I2的概率定義為

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

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

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

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

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

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

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

在實際應(yīng)用中要找到一個信息系統(tǒng)的所有約簡并不是一件簡單的事情，有時只需找到一個約簡即可，因此可設(shè)計啟發(fā)式算法來尋找滿足條件的約簡。而設(shè)計啟發(fā)式算法需要設(shè)計一個合適的起點以及找到一個恰當(dāng)?shù)膯l(fā)式信息，通常采用分類質(zhì)量來度量某一個條件屬性對正域的影響。

定義7設(shè)S=(U,AT∪D,V,f)為一個區(qū)間值決策信息系統(tǒng)，對任意的A?AT，δ∈(0,1]，則D關(guān)于A的分類質(zhì)量為：

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

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

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

算法1 區(qū)間值決策信息系統(tǒng)中基于正域的的啟發(fā)式屬性約簡算法

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

輸出：該信息系統(tǒng)的一個約簡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 實例分析

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

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

表1 某區(qū)間值決策信息系統(tǒng)

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

則

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

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

δ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關(guān)于決策屬性分為兩類，即U/D={D1,D2}，q且

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

D2={x2,x3,x7,x9}

通過定義6可以得到?jīng)Q策屬性D關(guān)于條件屬性集AT的正域為

則

進一步可以得到D關(guān)于AT的分類質(zhì)量為

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

Sig(a1,AT,D)=0

Sig(a2,AT,D)=0.33

Sig(a3,AT,D)=0,

Sig(a4,AT,D)=0

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

Red(AT)={a2}

進一步檢驗，有

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

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

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

4 結(jié)束語

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