李金海 周新然

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

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

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

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

1 相關(guān)知識(shí)

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

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

定義2[1]在形式背景K=(G,A,I)中，對(duì)于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給出一個(gè)信息系統(tǒng)C=(G,A)，其中G={g1,g2,g3,g4,g5,g6}，gi(i=1,2，…，6)表示某高校的6名即將畢業(yè)的大四學(xué)生，A={a1,a2,a3}，a1表示綜合平均績(jī)點(diǎn)，a2表示六級(jí)成績(jī)，a3表示數(shù)學(xué)建模比賽獲獎(jiǎng)情況，其中綜合平均績(jī)點(diǎn)和六級(jí)成績(jī)的單位均為分?jǐn)?shù)，屬性a1、a2、a3的取值形成多值集合.

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

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

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

定義4[23]設(shè)F=(G,A,I,D,J)為決策形式背景，對(duì)于?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，對(duì)于?g∈G，若存在g*B*B?g*D*D，稱B為F的協(xié)調(diào)集.進(jìn)一步，若?E?B，存在g∈G，使得g*E*E?g*D*D，稱B為F的約簡(jiǎn)集.

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

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

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

2)相對(duì)必要屬性：

3)絕對(duì)不必要屬性：

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

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

2.1 多粒度決策形式背景

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

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

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

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

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

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

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

MnkM(n-1)k…M1k，

則稱

為多粒度形式背景.

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

定義11[42]設(shè)

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

定義12[8]設(shè)

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

為一個(gè)多粒度決策形式背景.

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

例3 將表2中的屬性進(jìn)一步細(xì)化.首先，將屬性b1分為2個(gè)子屬性：c1為綜合平均績(jī)點(diǎn)4.0分及以上，c2為綜合平均績(jī)點(diǎn)介于3.5分到3.9分之間；將屬性b3也分為2個(gè)子屬性：c4為六級(jí)成績(jī)介于425分到450分之間，c5為六級(jí)成績(jī)451分及以上；將屬性b5分為2個(gè)子屬性：c7為數(shù)學(xué)建模比賽獲得國(guó)獎(jiǎng)，c8為數(shù)學(xué)建模比賽獲得省獎(jiǎng)，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è)劃分，均為(G,A2,I2)的類屬性塊.由定義9及例3的討論可知，M13和M23同屬數(shù)學(xué)建模比賽獲獎(jiǎng)情況這一類別，但M13比M23粒度更粗.

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

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

定義13對(duì)于多粒度決策形式背景

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

定義14對(duì)于多粒度決策形式背景

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

定義15對(duì)于多粒度決策形式背景

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

CIE(D|Ai)=

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

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

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

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

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

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

必要性.若CIE(D|Bi)=0，則對(duì)于?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)境是為了進(jìn)一步研究協(xié)調(diào)粒度層的平均條件信息熵及屬性約簡(jiǎn)問題.

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

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

3.1 基于平均條件信息熵的屬性約簡(jiǎn)

定義16設(shè)

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

定義17設(shè)

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

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

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

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

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

為部分協(xié)調(diào)的多粒度決策形式背景，Bi?Ai，則(B1,B2,…,Bh)為Π的協(xié)調(diào)粒度層協(xié)調(diào)集當(dāng)且僅當(dāng)在各協(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個(gè)，C1,C2,…,Ch分別為各協(xié)調(diào)粒度層下的屬性真子集，則在每一粒度層下Mi?Ai-Ci相對(duì)于Ci的外重要度記為

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

定義19設(shè)

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

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

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

例4 將表3中的六級(jí)分?jǐn)?shù)及數(shù)學(xué)建模獲獎(jiǎng)情況進(jìn)一步細(xì)分，具體將c5分為2個(gè)子屬性：e5為六級(jí)分?jǐn)?shù)介于451～480分之間，e6為六級(jí)分?jǐn)?shù)在481分及以上；將c7分為2個(gè)子屬性：e8為獲得數(shù)學(xué)建模比賽國(guó)家級(jí)一等獎(jiǎng)，e9為獲得數(shù)學(xué)建模比賽國(guó)家級(jí)二等獎(jiǎng)，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)

此時(shí)，

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

為了更好地利用平均條件信息熵得到多粒度決策形式背景的協(xié)調(diào)粒度層約簡(jiǎn)集，將表4進(jìn)一步細(xì)分，具體將屬性e5分為2個(gè)子屬性: f5為六級(jí)成績(jī)?cè)?51～465分之間, f6為六級(jí)成績(jī)?cè)?66～480分之間；將屬性e6分為2個(gè)子屬性: f7為六級(jí)成績(jī)?cè)?81～500分之間, f8為六級(jí)成績(jī)?cè)?01分及以上， 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)成一個(gè)部分協(xié)調(diào)的多粒度決策形式背景.

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

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

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

當(dāng)去掉第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.

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

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

的信息粒滿足

的條件信息熵為

同理，去掉類屬性塊

M43={f10, f11, f12, f13}

的條件信息熵為

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

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

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

定義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)集； 進(jìn)一步，若對(duì)于?Ecor?Bcor，有

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

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

定義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，使得在最細(xì)協(xié)調(diào)決策形式背景中的條件信息熵滿足

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

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

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

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

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

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

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

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

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

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

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

3.3 多粒度決策形式背景的屬性約簡(jiǎn)算法

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

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

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

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

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

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

否則

即

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

因?yàn)镕cor是協(xié)調(diào)的，所以

CIE(D|Acor)=0，

那么

必要性.當(dāng)

時(shí)，可得

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

因?yàn)樵谧畲至６葘酉碌臎Q策形式背景Fcor是協(xié)調(diào)的，故

CIE(D|Acor)=0，

所以

也就是說，存在某個(gè)對(duì)象g0，使得不等式

那么

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

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

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

定義24設(shè)

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

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

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

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

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

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

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

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

step4 若

則Bi←Bi∪Mij.

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

step6 若Mit?Ai-Bi且

則Bi←Bi∪Mit.

step7 若

返回step6，直至

為止.

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

step9 若

則Bi←Bi-Mij.

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

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

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

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

輸出約簡(jiǎn)集Bcor

step1 初始化Corecor(Acor)=?.

step2 遍歷屬性集Acor中每個(gè)類屬性塊Mj，計(jì)算其內(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，計(jì)算每類屬性塊Mj的內(nèi)重要度.

step8 若

則Bcor←Bcor-Mj.

step9 輸出約簡(jiǎn)集Bcor.

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

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

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

表6 實(shí)驗(yàn)數(shù)據(jù)集

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

為了方便討論，將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ù)本文算法分別對(duì)數(shù)據(jù)集1～數(shù)據(jù)集5的最粗粒度層和最細(xì)粒度層進(jìn)行屬性約簡(jiǎn)，找出它們的冗余屬性.同時(shí)，計(jì)算5個(gè)數(shù)據(jù)集的協(xié)調(diào)粒度層平均條件信息熵，得到它們的協(xié)調(diào)粒度層約簡(jiǎn)集，并對(duì)約簡(jiǎn)集結(jié)果進(jìn)行對(duì)比分析.

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

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

4.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 束 語

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

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