多粒度決策形式背景的屬性約簡

李金海 周新然

Wille[1]提出概念格，成為形式概念分析的核心數(shù)據(jù)結(jié)構(gòu)，該方法通過形式化的方式表現(xiàn)組成概念的對象、屬性及其結(jié)構(gòu)關(guān)系等信息.隨著相關(guān)研究的深入，一些學者將粒計算[2-6]、多粒度[7-9]及粗糙集[10]等理論與形式概念分析緊密結(jié)合.同時，概念格也被應(yīng)用到機器學習[11]、數(shù)據(jù)挖掘[12]及知識發(fā)現(xiàn)[13-16]等具有廣闊應(yīng)用前景的領(lǐng)域[17-20].

形式概念分析通過引入誘導算子、定義概念的內(nèi)涵和外延作為基礎(chǔ)，研究誘導算子性質(zhì)、數(shù)據(jù)拆分合并關(guān)系、概念知識代數(shù)結(jié)構(gòu)、概念格構(gòu)造、概念格規(guī)則提取及消除冗余屬性等問題.屬性約簡作為形式概念分析研究的主要內(nèi)容之一，已受到越來越多學者的關(guān)注.張文修等[21-22]借鑒粗糙集理論中的屬性約簡思想，在概念格中引入可辨識屬性矩陣及在協(xié)調(diào)近似表示空間上給出屬性協(xié)調(diào)集的判定定理，實現(xiàn)概念格的屬性約簡.Wu等[23]基于信息粒協(xié)調(diào)結(jié)構(gòu)關(guān)系,提出粒約簡與粒規(guī)則的概念.魏玲等[24]在決策形式背景中進一步建立概念格屬性約簡理論，研究基于強協(xié)調(diào)決策形式背景和弱協(xié)調(diào)決策形式背景的屬性約簡.Li等[25]在決策形式背景中構(gòu)造可辨識矩陣及布爾函數(shù)，在非冗余規(guī)則提取意義下實現(xiàn)知識約簡.李進金等[26]引入交并可約元的概念，完成形式背景的屬性約簡.

Shannon等[27]提出信息熵的概念，解決度量信息不確定性問題.粗糙集理論中廣泛利用各種信息熵研究目標對象的近似質(zhì)量、信息的刻畫精度及屬性的重要性程度等問題，學者們通過這些有用的工具又研究信息系統(tǒng)的知識約簡[28-33]，主要側(cè)重于約簡集的快速計算.因為各種度量方法被提出，啟發(fā)式搜索屬性約簡集更容易實現(xiàn).王國胤等[34]在粗糙集中基于條件信息熵，提出決策表知識約簡的快速實現(xiàn)算法.此外，信息熵在形式概念分析中也得到重視.陳東曉等[35]在協(xié)調(diào)決策形式背景中利用條件信息熵研究屬性約簡問題，具體是通過其約簡過程中引起互信息的變化，以此計算屬性約簡集.Li等[36]和Singh等[37]給出基于信息熵的加權(quán)概念格屬性約簡方法.

但是，上述研究都是在單一粒度層下進行的數(shù)據(jù)分析及屬性約簡，隨著形式概念分析研究逐漸發(fā)展到多層次、多維度、多粒度的復雜環(huán)境，出現(xiàn)多粒度決策形式背景的屬性約簡方法.基于上述討論，本文以現(xiàn)有的單粒度決策形式背景的屬性約簡方法為基礎(chǔ)，基于條件信息熵，討論多粒度決策形式背景的屬性約簡.具體地，本文在多粒度決策形式背景中定義信息熵和條件信息熵，度量屬性重要度.根據(jù)刪除冗余類屬性塊的不同需求，提出3種多粒度決策形式背景屬性約簡方法，即協(xié)調(diào)粒度約簡方法、最粗協(xié)調(diào)粒度約簡方法和最細協(xié)調(diào)粒度約簡方法，并通過實驗說明它們的有效性.

1 相關(guān)知識

為了給出多粒度決策形式背景的有關(guān)概念，下面先介紹形式背景及其概念誘導算子.

定義1[1]三元組K=(G,A,I)稱為形式背景，其中G=(g1,g2,…,gp)為一個非空有限對象集，A=(a1,a2,…,aq)為一個非空有限屬性集，I為笛卡爾積G×A上的二元關(guān)系.(g,a)∈I表示對象g擁有屬性a，記為gIa.

定義2[1]在形式背景K=(G,A,I)中，對于X?

G，B?A，定義算子：

X*={a∈A|?g∈X,gIa}，
B*={g∈G|?a∈B,gIa}.

如果X*=B，B*=X，稱序?qū)?X,B)為形式概念，X為概念的外延,B為概念的內(nèi)涵.

定義3[38]設(shè)(G,A,I)和(G,D,J)為形式背景且A∩D=?，稱五元組F=(G,A,I,D,J)為決策形式背景，其中，A為條件屬性，D為決策屬性，(G,A,I)為F的條件子背景,(G,D,J)為F的決策子背景.

例1 表1給出一個信息系統(tǒng)C=(G,A)，其中G={g1,g2,g3,g4,g5,g6}，gi(i=1,2，…，6)表示某高校的6名即將畢業(yè)的大四學生，A={a1,a2,a3}，a1表示綜合平均績點，a2表示六級成績，a3表示數(shù)學建模比賽獲獎情況，其中綜合平均績點和六級成績的單位均為分數(shù)，屬性a1、a2、a3的取值形成多值集合.

先把信息系統(tǒng)轉(zhuǎn)換成多個單粒度形式背景，再并置且添加決策屬性,得到多粒度決策形式背景，詳見表2.具體地，將信息系統(tǒng)中的多值屬性a1分成2個子類:b1為綜合平均績點3.5分及以上,b2為綜合平均績點3.5以下；將多值屬性a2分成2個子類:b3為六級成績425分及以上,b4為六級成績425分以下；將多值屬性a3分成2個子類:b5為參加數(shù)學建模比賽且獲獎,b6為參加數(shù)學建模比賽并未獲獎.D={d1,d2}，d1表示獲得國家級或省級獎學金，d2表示獲得研究生推免資格.在該數(shù)據(jù)集中，數(shù)字1表示該學生符合所在列的條件，0表示不符合.

表1 信息系統(tǒng)C=(G,A)

表2 決策形式背景(G,A1,I1,D,J)

定義4[23]設(shè)F=(G,A,I,D,J)為決策形式背景，對于?g∈G，若存在g*A*A?g*D*D，稱F為協(xié)調(diào)決策形式背景.

定義5[23]設(shè)F=(G,A,I,D,J)為協(xié)調(diào)決策形式背景且B?A，對于?g∈G，若存在g*B*B?g*D*D，稱B為F的協(xié)調(diào)集.進一步，若?E?B，存在g∈G，使得g*E*E?g*D*D，稱B為F的約簡集.

定義6[23]設(shè)F=(G,A,I,D,J)為協(xié)調(diào)決策形式背景，對于?g∈G，稱g*A→g*D為F的一條粒規(guī)則.

定義7[24]設(shè)F=(G,A,I,D,J)為協(xié)調(diào)決策形式背景，{Bi|Bi是約簡集，i∈τ}(τ為指標集)為F的全體約簡集，記

1)絕對必要屬性(核心屬性)：

2)相對必要屬性：

3)絕對不必要屬性：

2 多粒度決策形式背景的條件信息熵

信息熵在粗糙集中被廣泛應(yīng)用于度量屬性的重要性[34,39-40]，本節(jié)參考形式背景的信息熵，提出多粒度決策形式背景的條件信息熵.

2.1 多粒度決策形式背景

定義8[8]設(shè)K=(G,A,I)為形式背景，

M={a1,a2,…,am}?A，

若每個屬性ai(i∈{1,2,…,m})擁有的對象組成的集合為Iai，全體Iai(ai∈M)構(gòu)成G的一個劃分，且M中所有的布爾屬性在語義上屬于同一類別，則稱M為(G,A,I)的一個類屬性塊.

上述定義說明類屬性塊實質(zhì)上是一些同類布爾屬性組成的集合，它們構(gòu)成論域G的劃分，換言之，每個對象在不同類屬性塊下取值可能相同，但在同一類屬性塊下取值必唯一.

例2 以表2中的條件子背景K=(G,A1,I1)為例，因為{Ib1,Ib2}構(gòu)成G的一個劃分，且都是綜合平均績點的布爾屬性，所以M11={b1,b2}為(G,A1,I1)的一個類屬性塊.同理，M12={b3,b4}，M13={b5,b6}也是(G,A1,I1)的類屬性塊.

定義9[8]設(shè)(G,A1,I1)和(G,A2,I2)為2個不同粒度的形式背景，屬性集分別劃分為M11,M12,…,M1s和M21,M22,…,M2s，若單粒度類屬性塊M2k的布爾屬性由M1k合并產(chǎn)生，則稱M1k比M2k的粒度細，記作M1kM2k.若對?k∈{1,2,…,s}，都有M1kM2k，則稱(G,A1,I1)比(G,A2,I2)的粒度細，記作(G,A1,I1)(G,A2,I2).

定義10[8]對于n個單粒度形式背景(G,Ai,Ii)(i∈{1,2,…,n})，假設(shè)Ai的類屬性塊為Mi1,Mi2,…,Mis，其中M1k,M2k,…,Mnk(k∈{1,2,…,s})為不同粒度下的同類別類屬性塊，若

MnkM(n-1)k…M1k，

則稱

為多粒度形式背景.

實際上，現(xiàn)實中得到多粒度形式背景的方法很多，如屬性?；痆7]、樂觀悲觀分類[41].

定義11[42]設(shè)

進一步，將多粒度形式背景與單粒度決策背景進行并置，可引入多粒度決策形式背景.

定義12[8]設(shè)

為多粒度形式背景，(G,D,J)為單粒度形式背景，則稱

為一個多粒度決策形式背景.

如果多粒度決策形式背景Π中存在某一粒度層，使得(G,Ai,Ii,D,J)是協(xié)調(diào)的，那么稱Π是部分協(xié)調(diào)的.下文主要討論部分協(xié)調(diào)的多粒度決策形式背景，因為完全不協(xié)調(diào)的多粒度決策形式背景毫無全局協(xié)調(diào)性可言，而本文關(guān)注的又是全局協(xié)調(diào)性意義下的屬性約簡，所以暫不考慮完全不協(xié)調(diào)的情況.

例3 將表2中的屬性進一步細化.首先，將屬性b1分為2個子屬性：c1為綜合平均績點4.0分及以上，c2為綜合平均績點介于3.5分到3.9分之間；將屬性b3也分為2個子屬性：c4為六級成績介于425分到450分之間，c5為六級成績451分及以上；將屬性b5分為2個子屬性：c7為數(shù)學建模比賽獲得國獎，c8為數(shù)學建模比賽獲得省獎，c3、c6、c9分別與b2、b4、b6保持一致.那么，表2又可轉(zhuǎn)化為如表3所示的決策形式背景(G,A2,I2,D,J).

表3 決策形式背景(G,A2,I2,D,J)

令

M21={c1,c2,c3}， M22={c4,c5,c6}，
M23= {c7,c8,c9}，

則M21、M22、M23構(gòu)成A2的一個劃分，均為(G,A2,I2)的類屬性塊.由定義9及例3的討論可知，M13和M23同屬數(shù)學建模比賽獲獎情況這一類別，但M13比M23粒度更粗.

2.2 多粒度決策形式背景的條件信息熵

文獻[43]給出單粒度(決策)形式背景的信息熵(條件信息熵)，本節(jié)將其推廣到多粒度決策形式背景，討論屬性約簡問題.

定義13對于多粒度決策形式背景

第i粒度層Ki=(G,Ai,Ii)的信息粒度定義為

定義14對于多粒度決策形式背景

第i粒度層Ki=(G,Ai,Ii)的信息熵定義為

定義15對于多粒度決策形式背景

決策子背景(G,D,J)關(guān)于第i粒度層下的條件子背景(G,Ai,Ii)的條件信息熵定義為

CIE(D|Ai)=

性質(zhì)1對于多粒度決策形式背景

應(yīng)用本文的方法，對2018年4月30日進行的GPS車載定位實測數(shù)據(jù)進行處理。利用Novatel公司的雙頻商用接收機采集多組衛(wèi)星數(shù)據(jù)，設(shè)置采樣頻率1 Hz。對于GPS載波相位數(shù)據(jù)，在大多數(shù)應(yīng)用情況下，選取0.001%的誤警率是可行的。而對于動態(tài)情況下應(yīng)用的低成本接收機，相位噪聲的標準偏差為1 cm。設(shè)置:PFA=10-5，PMD=10-4，σ=1 cm。針對設(shè)定的參數(shù)判斷各衛(wèi)星截止高度角下的可用性，結(jié)果如表1所示。

Bi?Ai，則Bi為第i粒度層(G,Ai,Ii,D,J)的協(xié)調(diào)集當且僅當CIE(D|Bi)=0.

證明充分性.由于Bi為(G,Ai,Ii,D,J)的協(xié)調(diào)集，所以決策形式背景(G,Bi,IBi,D,J)是協(xié)調(diào)的，那么根據(jù)定義4可知，對于?g∈G，有

g*Bi*Bi?g*D*D，

故由定義15可得CIE(D|Bi)=0.

必要性.若CIE(D|Bi)=0，則對于?g∈G，有

g*Bi*Bi?g*D*D，

因此由定義5可得，Bi為(G,Ai,Ii,D,J)的協(xié)調(diào)集.

也就是說，部分協(xié)調(diào)的多粒度決策形式背景必存在某一粒度層，使決策子背景關(guān)于該粒度層條件子背景的條件信息熵為零.需要指出的是，多粒度決策形式背景的信息熵或條件信息熵與單粒度的情況是類似的，推廣到多粒度環(huán)境是為了進一步研究協(xié)調(diào)粒度層的平均條件信息熵及屬性約簡問題.

3 部分協(xié)調(diào)的多粒度決策形式背景的屬性約簡

本節(jié)針對部分協(xié)調(diào)的多粒度決策形式背景，基于平均條件信息熵、最粗協(xié)調(diào)決策形式背景條件信息熵及最細協(xié)調(diào)決策形式背景條件信息熵，提出3種屬性約簡方法，并給出相應(yīng)的實現(xiàn)算法.

3.1 基于平均條件信息熵的屬性約簡

定義16設(shè)

(i=1,2,…,h)，則Π的協(xié)調(diào)粒度層平均條件信息熵定義為

定義17設(shè)

為部分協(xié)調(diào)的多粒度決策形式背景，協(xié)調(diào)粒度層有h個，在每個協(xié)調(diào)粒度層下，均存在Bi?Ai，使得協(xié)調(diào)粒度層平均條件信息熵

則稱(B1,B2,…,Bh)為多粒度決策形式背景Π的協(xié)調(diào)粒度層協(xié)調(diào)集；進一步，若?i∈{1,2,…,h}，有Ei?Bi，且存在Ej?Bj使得

則稱(B1,B2,…,Bh)為Π的協(xié)調(diào)粒度層約簡集.

需要指出的是，具體進行約簡時，Bi相對于Ai(i=1,2,…,h)被約掉的信息需為同一類別的類屬性塊，從而實現(xiàn)在每一粒度層下去掉相同的冗余類屬性塊信息.這樣做的目的是可解決信息系統(tǒng)的屬性約簡問題，即被約掉的類屬性塊在每一粒度層下都是冗余的.

性質(zhì)2設(shè)

為部分協(xié)調(diào)的多粒度決策形式背景，Bi?Ai，則(B1,B2,…,Bh)為Π的協(xié)調(diào)粒度層協(xié)調(diào)集當且僅當在各協(xié)調(diào)粒度層下Bi均為(G,Ai,Ii,D,J)的協(xié)調(diào)集.

證明充分性.若(B1,B2,…,Bh)為多粒度決策形式背景Π的協(xié)調(diào)粒度層協(xié)調(diào)集，則

由于條件信息熵CIE(D|Bi)≥0，所以CIE(D|Bi)=0，根據(jù)性質(zhì)1可得在各粒度層下Bi均為(G,Ai,Ii,D,J)的協(xié)調(diào)集.

必要性.若在各粒度層下Bi均為(G,Ai,Ii,D,J)的協(xié)調(diào)集，則由性質(zhì)1可得CIE(D|Bi)=0，因此

即(B1,B2,…,Bh)為多粒度決策形式背景Π的協(xié)調(diào)粒度層協(xié)調(diào)集.

定義18設(shè)

為部分協(xié)調(diào)的多粒度決策形式背景，協(xié)調(diào)粒度層有h個，C1,C2,…,Ch分別為各協(xié)調(diào)粒度層下的屬性真子集，則在每一粒度層下Mi?Ai-Ci相對于Ci的外重要度記為

那么在多粒度決策形式背景Π中這些新添加屬性集的協(xié)調(diào)粒度層平均外重要度定義為

定義19設(shè)

為部分協(xié)調(diào)的多粒度決策形式背景，A1,A2,…,Ah為各協(xié)調(diào)粒度層下的屬性全集，Mi為第i粒度層下的屬性集Ai中任一屬性子集，則每一粒度層下Mi相對于Ai的內(nèi)重要度記為

那么在多粒度決策形式背景Π中這些被刪除屬性集的協(xié)調(diào)粒度層平均內(nèi)重要度定義為

在實際應(yīng)用中，通常刪除和添加屬性集都是以類屬性塊為單位進行的，在此前提下當這些類屬性塊同屬一個類別時，即可實現(xiàn)信息系統(tǒng)的屬性約簡.下文使用Coreave(A1,A2,…,Ah)表示所有核心類屬性塊組成的集合，即使得協(xié)調(diào)粒度層平均內(nèi)重要度大于零的那些類屬性塊.

例4 將表3中的六級分數(shù)及數(shù)學建模獲獎情況進一步細分，具體將c5分為2個子屬性：e5為六級分數(shù)介于451～480分之間，e6為六級分數(shù)在481分及以上；將c7分為2個子屬性：e8為獲得數(shù)學建模比賽國家級一等獎，e9為獲得數(shù)學建模比賽國家級二等獎，e1、e2、e3、e4、e7、e11分別與c1、c2、c3、c4、c6、c8、c9保持一致.那么，表3可轉(zhuǎn)化為如表4所示的決策形式背景(G,A3,I3,D,J).

表4 決策形式背景(G,A3,I3,D,J)

此時，

構(gòu)成一個部分協(xié)調(diào)的多粒度決策形式背景，即第3粒度層下的決策形式背景(G,A3,I3,D,J)是協(xié)調(diào)的.對于第1位學生g1,對應(yīng)的粒規(guī)則e1e5e9→d1d2，語義解釋為：如果某學生綜合平均績點4.0分及以上、六級成績介于451～480分之間且數(shù)學建模比賽獲得國家級二等獎，那么該學生獲得國家級獎學金且具有研究生推免資格.

為了更好地利用平均條件信息熵得到多粒度決策形式背景的協(xié)調(diào)粒度層約簡集，將表4進一步細分，具體將屬性e5分為2個子屬性: f5為六級成績在451～465分之間, f6為六級成績在466～480分之間；將屬性e6分為2個子屬性: f7為六級成績在481～500分之間, f8為六級成績在501分及以上， f1、 f2、 f3、 f4、 f9、 f10、 f11、 f12、 f13分別與e1、e2、e3、e4、e7、e8、e9、e10、e11保持一致.那么決策形式背景(G,A3,I3,D,J)可轉(zhuǎn)化為表5所示的數(shù)據(jù)集.

表5 決策形式背景(G,A4,I4,D,J)

不難發(fā)現(xiàn)，第4粒度層下的決策形式背景(G,A4,I4,D,J)也是協(xié)調(diào)的，即

也構(gòu)成一個部分協(xié)調(diào)的多粒度決策形式背景.

例5 計算表2～表5組成的部分協(xié)調(diào)多粒度決策形式背景

的協(xié)調(diào)粒度層約簡集.具體過程如下：根據(jù)例3和例4的討論，Π的第1粒度層和第2粒度層是不協(xié)調(diào)的，但在第3粒度層和第4粒度層下均是協(xié)調(diào)的.因此

CIE(D|A3)=0， CIE(D|A4)=0.

當去掉第3粒度層下形式背景K3=(G,A3,I3)中的類屬性塊M31={e1,e2,e3}后，條件子背景

的信息粒滿足

的條件信息熵為

的條件信息熵為

CIE(D|(A4-M41))=0.

的條件信息熵為

CIE(D|(A3-M32))=0；

去掉類屬性塊

M42={f4, f5, f6, f7, f8, f9}

的條件信息熵為

CIE(D|(A4-M42))=0.

當去掉第3粒度層下形式背景K3=(G,A3,I3)

中的類屬性塊M33={e8,e9,e10,e11}后，條件子背景

的信息粒滿足

的條件信息熵為

同理，去掉類屬性塊

M43={f10, f11, f12, f13}

的條件信息熵為

CIE(D|(A4-M43))=0.

3.2 最粗(細)協(xié)調(diào)決策形式背景下屬性約簡的判定

下面討論的多粒度決策形式背景提及的最粗協(xié)調(diào)決策形式背景，意指比它粒度更粗的決策形式背景均是不協(xié)調(diào)的；最細的決策形式背景是指多粒度決策形式背景中最細的粒度層.

定義20在部分協(xié)調(diào)的多粒度決策形式背景

中，若存在Bcor?Acor，使得在最粗協(xié)調(diào)決策形式背景

Fcor=(G,Acor,Icor,D,J)

中的條件信息熵滿足

CIE(D|Bcor)=CIE(D|Acor)，

則稱Bcor為多粒度決策形式背景Π的最粗協(xié)調(diào)粒度層協(xié)調(diào)集； 進一步，若對于?Ecor?Bcor，有

CIE(D|Ecor)≠CIE(D|Acor)，

則稱Bcor為多粒度決策形式背景Π的最粗協(xié)調(diào)粒度層約簡集.

定義21在部分協(xié)調(diào)的多粒度決策形式背景

中，設(shè)在最粗協(xié)調(diào)粒度層

Fcor=(G,Acor,Icor,D,J)

下去掉任一屬性集M?Acor后，得到的決策形式背景為

定義屬性集M在Π中的內(nèi)重要度為

定義22在部分協(xié)調(diào)的多粒度決策形式背景

中，若存在Bfin?Afin，使得在最細協(xié)調(diào)決策形式背景中的條件信息熵滿足

CIE(D|Bfin)=CIE(D|Afin)，

則稱Bfin為多粒度決策形式背景Π的最細協(xié)調(diào)粒度層協(xié)調(diào)集；進一步，若對于?Efin?Bfin，有

CIE(D|Efin)≠CIE(D|Afin)，

則稱Bfin為多粒度決策形式背景Π的最細協(xié)調(diào)粒度層約簡集.

定義23在部分協(xié)調(diào)的多粒度決策形式背景

中，設(shè)在最細協(xié)調(diào)粒度層

Ffin=(G,Afin,Ifin,D,J)

下去掉任一屬性集M?Afin后得到的決策形式背景為

定義屬性集M在Π中的內(nèi)重要度為

性質(zhì)3設(shè)

性質(zhì)3給出最粗協(xié)調(diào)粒度層約簡集與最細協(xié)調(diào)粒度層約簡集之間在特定條件下相互轉(zhuǎn)化的規(guī)律，進一步揭示這兩種協(xié)調(diào)粒度層約簡集之間的關(guān)系.另外，最粗協(xié)調(diào)粒度層約簡集和最細協(xié)調(diào)粒度層約簡集均是協(xié)調(diào)粒度層約簡集的2種具體形式，對于同一數(shù)據(jù)集，協(xié)調(diào)粒度約簡方法的約束條件比最粗協(xié)調(diào)粒度約簡方法和最細協(xié)調(diào)粒度約簡方法的約束條件更嚴格.

3.3 多粒度決策形式背景的屬性約簡算法

為了給出部分協(xié)調(diào)的多粒度決策形式背景的屬性約簡算法，先討論如下性質(zhì).下文將影響決策形式背景協(xié)調(diào)性的類屬性塊稱為核心類屬性塊，否則稱為非核心類屬性塊.

性質(zhì)4設(shè)

為部分協(xié)調(diào)的多粒度決策形式背景，

Fcor=(G,Acor,Icor,D,J)

為最粗協(xié)調(diào)決策形式背景，則對于?M?Acor，M為Π的核心類屬性塊當且僅當

證明充分性.若M為Π的核心類屬性塊，則

否則

即

CIE(D|(Acor-M))-CIE(D|Acor)=0.

因為Fcor是協(xié)調(diào)的，所以

CIE(D|Acor)=0，

那么

必要性.當

時，可得

CIE(D|(Acor-M))-CIE(D|Acor)>0.

因為在最粗粒度層下的決策形式背景Fcor是協(xié)調(diào)的，故

CIE(D|Acor)=0，

所以

也就是說，存在某個對象g0，使得不等式

那么

故Acor-M不是Fcor的協(xié)調(diào)集.換言之，刪除屬性集M改變Fcor的協(xié)調(diào)性，所以M為核心類屬性塊.

類似地，性質(zhì)4對于最細協(xié)調(diào)決策形式背景也是成立的.為了方便，將影響最粗協(xié)調(diào)決策形式背景和最細協(xié)調(diào)決策形式背景的所有核心類屬性塊組成的集合分別記為Corecor(Acor)和Corefin(Afin)，那么通過性質(zhì)4可計算所有的核心類屬性塊.

此外，類似于協(xié)調(diào)粒度層平均外重要度，在最粗(細)協(xié)調(diào)決策形式背景中引入外重要度的概念.

定義24設(shè)

為部分協(xié)調(diào)的多粒度決策形式背景，Bj?Aj，則Mj?Aj-Bj相對于Bj的最粗(細)協(xié)調(diào)粒度層外重要度定義為

需要指出的是，通過內(nèi)重要度和外重要度可得到協(xié)調(diào)粒度層的約簡集，具體如下：首先計算內(nèi)重要度得到多粒度決策形式背景的所有核心類屬性塊Ci(一般不是約簡集)；再計算各個候選類屬性塊的外重要度，將外重要度最大的類屬性塊不斷添加到Ci中，直至得到協(xié)調(diào)粒度層協(xié)調(diào)集Ei為止；最后，利用內(nèi)重要度去掉協(xié)調(diào)集Ei中的冗余類屬性塊，得到協(xié)調(diào)粒度層約簡集Bi.

為了敘述清楚，分2種算法給出多粒度決策形式背景的屬性約簡過程，詳見算法1和算法2.

算法1基于協(xié)調(diào)粒度層平均條件信息熵的約簡

輸入多粒度決策形式背景Π及其協(xié)調(diào)粒度層

輸出約簡集(B1,B2,…,Bh)

step1 初始化(B1,B2,…,Bh)=(?,?,…,?).

step3 遍歷協(xié)調(diào)粒度層下的各個屬性集Ai，計算去掉類屬性塊M1j,M2j,…,Mhj后的多粒度決策形式背景的平均條件信息熵

step4 若

則Bi←Bi∪Mij.

step5 若j小于類屬性塊個數(shù)，返回step3；否則轉(zhuǎn)step7.

step6 若Mit?Ai-Bi且

則Bi←Bi∪Mit.

step7 若

返回step6，直至

為止.

step8 遍歷協(xié)調(diào)集(B1,B2,…,Bh)，計算各個類屬性塊Mij的內(nèi)重要度.

step9 若

則Bi←Bi-Mij.

step10 輸出約簡集(B1,B2,…,Bh).

算法2最粗協(xié)調(diào)決策形式背景下的約簡

輸入多粒度決策形式背景中的最粗協(xié)調(diào)決策形

式背景Fcor=(G,Acor,Icor,D,J)

輸出約簡集Bcor

step1 初始化Corecor(Acor)=?.

step2 遍歷屬性集Acor中每個類屬性塊Mj，計算其內(nèi)重要度.

Corecor(Acor)←Corecor(Acor)∪Mj.

step4 設(shè)Acor-Corecor(Acor)中包含的類屬性塊為M1,M2,…,Mr，令Bcor=Corecor(Acor).

step5 若

則 Bcor←Bcor∪Mt.

step6 若

CIE(D|Bcor)≠CIE(D|Acor)，

返回step5，直至

CIE(D|Bcor)=CIE(D|Acor)

為止.

step7 遍歷協(xié)調(diào)集Bcor，計算每類屬性塊Mj的內(nèi)重要度.

step8 若

則Bcor←Bcor-Mj.

step9 輸出約簡集Bcor.

注意，算法2也適用于計算多粒度決策形式背景在最細協(xié)調(diào)決策形式背景下的約簡集，只需將上下標涉及cor的字母全部替換為上下標為fin的字母即可.

4 實驗及結(jié)果分析

4.1 實驗數(shù)據(jù)集

為了驗證本文提出的屬性約簡方法的性能，從UCI數(shù)據(jù)集(http://archive.ics.uci.edu/ml/index.php)中選取5個公開數(shù)據(jù)集，分別為Bank Marketing、Forest Fires、Wine Quality、Estimation of Obesity Levels Based on Eating Habits and Physical Condition(簡稱EOL)和Chess(King-Rook vs.King).詳細信息如表6所示.

表6 實驗數(shù)據(jù)集

由于原始數(shù)據(jù)集的屬性不是標準的0-1布爾值形式，為了得到實驗中所需的部分協(xié)調(diào)的多粒度決策形式背景，首先將實驗中的5個數(shù)據(jù)集均轉(zhuǎn)化為決策形式背景，核心思想是根據(jù)原始數(shù)據(jù)集的不同形式，采取不同方法將其轉(zhuǎn)化為0-1布爾值屬性.具體操作如下.1)若原始數(shù)據(jù)集的屬性取值是連續(xù)的，進行分段處理，每個分段區(qū)間被看作一個新的布爾屬性，實驗中針對不同數(shù)據(jù)集的屬性取值，分段方式會有所不同.如在[0,20]區(qū)間上連續(xù)取值的情形，可將其分為[0,5),[5,10),[10,15),[15,20].2)若原始數(shù)據(jù)集的屬性并非連續(xù)型，而是多值屬性，則將每個屬性取值看作一個新的布爾屬性.在此基礎(chǔ)上，將每個類屬性塊下的相鄰屬性進行適當合并，把實驗中的5個數(shù)據(jù)集均處理成包含4個粒度層的部分協(xié)調(diào)決策形式背景，其中前4個數(shù)據(jù)集的后2層為協(xié)調(diào)決策形式背景，最后一個數(shù)據(jù)集的最后一層為協(xié)調(diào)決策形式背景.具體地，每個數(shù)據(jù)集上任一粒度層下的類屬性塊記為A(1,2，…,j)，其中大寫英文字母表示每個數(shù)據(jù)集中的各個類屬性塊，每類屬性塊下的各個布爾屬性依次使用正整數(shù)表示，那么將該粒度層下的相鄰布爾屬性進行適當合并得到更粗粒度的決策形式背景，對應(yīng)的類屬性塊記為A(1-i,(i+1)-t,…,k-j)，這里的區(qū)間1-i,(i+1)-t,…,k-j構(gòu)成{1,2，…,j}的一個劃分.

為了方便討論，將Bank Marketing、Forest Fires、Wine Quality、EOL、Chess(King-Rook vs.King)數(shù)據(jù)集經(jīng)過上述預(yù)處理后得到的數(shù)據(jù)集記為數(shù)據(jù)集1～數(shù)據(jù)集5，具體的屬性預(yù)處理過程如表7所示，預(yù)處理后得到的數(shù)據(jù)集見表8.

最后，根據(jù)本文算法分別對數(shù)據(jù)集1～數(shù)據(jù)集5的最粗粒度層和最細粒度層進行屬性約簡，找出它們的冗余屬性.同時，計算5個數(shù)據(jù)集的協(xié)調(diào)粒度層平均條件信息熵，得到它們的協(xié)調(diào)粒度層約簡集，并對約簡集結(jié)果進行對比分析.

表7 屬性預(yù)處理過程

表8 預(yù)處理后的數(shù)據(jù)集

4.2 實驗結(jié)果

在多粒度決策形式背景的最粗(細)協(xié)調(diào)粒度層Fcor=(G,Acor,Icor,D,J)(或Ffin=(G,Afin,Ifin,D,J))中，對于同一屬性集Acor(Afin)，對象集G的屬性約簡集為B1，B2為擴展對象集G′(G?G′)的屬性約簡集，且B2是B1通過添加類屬性塊后再去掉冗余類屬性塊得到的屬性約簡集.本文在計算G′的屬性約簡集時，盡可能保留B1中的類屬性塊.這種做法是為了觀察對象變化后屬性約簡集之間存在的關(guān)聯(lián)，進一步評估約簡方法的靈敏性.

計算平均條件信息熵進行屬性約簡的結(jié)果如表9所示.

表9 基于平均條件信息熵的屬性約簡結(jié)果

由表9可看出，在多粒度決策形式背景中，計算平均條件信息熵可得到屬性約簡集，這種約簡方法是有效的.具體地，對于實驗中的數(shù)據(jù)集1，在屬性不變的情況下，取不同范圍的對象可實現(xiàn)有包含關(guān)系的屬性約簡.對于實驗中的數(shù)據(jù)集2～數(shù)據(jù)集5，雖然也可實現(xiàn)屬性約簡，但在取不同范圍的對象時，屬性約簡集基本保持不變，說明這種約簡方法的約束條件太強.

在多粒度決策形式背景中基于最粗(細)協(xié)調(diào)粒度層計算屬性重要度，得到屬性約簡集的情況，如表10和表11所示.由表10和表11可看出，基于多粒度決策形式背景的最粗(細)協(xié)調(diào)粒度層的屬性約簡結(jié)果較理想，當取不同范圍的對象時基本都實現(xiàn)有包含關(guān)系的屬性約簡，說明這2種約簡方法是有效的，約束條件相對寬松.因此，從屬性約簡條件的寬松與否而言，最粗協(xié)調(diào)粒度約簡方法和最細協(xié)調(diào)粒度約簡優(yōu)于協(xié)調(diào)粒度約簡方法.

此外，通過表9～表11還可得到如下結(jié)論.

1)根據(jù)刪除冗余布爾屬性的強度，最細協(xié)調(diào)粒度層約簡方法優(yōu)于最粗協(xié)調(diào)粒度層約簡方法，而最粗協(xié)調(diào)粒度層約簡方法又優(yōu)于協(xié)調(diào)粒度層約簡方法.

2)多粒度決策形式背景中的對象個數(shù)越多，屬性約簡集包含的屬性個數(shù)越多.

3)對于對象個數(shù)較多的多粒度決策形式背景，其屬性約簡集可包含對象個數(shù)較少的多粒度決策形式背景的屬性約簡集，這3種屬性約簡方法刪除的類屬性塊實際上是在每一粒度層下去掉相同的塊信息.

表10 基于最粗粒度層的屬性約簡結(jié)果

表11 基于最細粒度層的屬性約簡結(jié)果

5 結(jié) 束 語

對于概念格屬性約簡，現(xiàn)有研究都是基于單粒度形式背景的信息熵或保持代數(shù)結(jié)構(gòu)進行研究，本文是基于多粒度決策形式背景的條件信息熵探討屬性約簡，具體在多粒度決策形式背景中基于平均條件信息熵及最粗(細)協(xié)調(diào)粒度層的條件信息熵計算屬性約簡集，并對提出的3種屬性約簡方法進行對比分析.本文是在多粒度決策形式背景中通過刪除各協(xié)調(diào)粒度層下的類屬性塊的方式實施屬性約簡，當這些類屬性塊來源于同一類別時，可實現(xiàn)信息系統(tǒng)的屬性約簡.相比現(xiàn)有方法，基于類屬性塊的屬性約簡將粒計算的多粒度思想應(yīng)用于形式概念分析，能從多個水平研究多粒度數(shù)據(jù)的屬性冗余問題.此外，本文的結(jié)果有助于今后對多粒度決策形式背景的屬性約簡進行進一步研究.

盡管本文為探究多粒度決策形式背景的屬性約簡提出協(xié)調(diào)粒度約簡方法、最粗協(xié)調(diào)粒度約簡方法和最細協(xié)調(diào)粒度約簡方法，但仍存在一些不足：1)本文討論的屬性約簡是在假定各多粒度類屬性塊的重要程度均等的情況下進行的，即不考慮類屬性塊的權(quán)重因素，但實際應(yīng)用中某些屬性會被特殊對待，所以類屬性塊代價敏感問題值得繼續(xù)探討.2)由于多粒度決策形式背景中會存在多個屬性約簡集的情況，所以如何找到最優(yōu)的約簡集也是一個有意義的研究課題，特別是設(shè)計快速高效的實現(xiàn)算法.3)多粒度決策形式背景的屬性約簡能否像單粒度決策形式背景那樣，研究如何得到合適的類屬性塊以提升數(shù)據(jù)分類精度也是一個重要的問題.