區(qū)間值決策表中基于相對知識粒度的屬性約簡

唐鵬飛，莫智文，謝 鑫

(四川師范大學 a.數(shù)學科學學院；b.智能信息與量子信息研究所， 成都 610066)

粗糙集理論是不確定性分析與智能計算的有效數(shù)學工具[1]。在粗糙集理論中，屬性約簡是核心內(nèi)容與研究熱點，其主要是在保持相同分類能力的前提下進行冗余屬性刪除，從而達到數(shù)據(jù)表的優(yōu)化處理。知識粒度廣泛用于不確定性測量、屬性約簡、機器學習。針對經(jīng)典信息(決策)表，文獻[2-3]提出基于知識粒度的屬性約簡，而文獻[4-7]在不同決策信息系統(tǒng)下推廣并改進基于知識粒度的屬性約簡；文獻[8]從多粒度視角提出基于知識粒度的增量屬性約簡。尋找最小屬性約簡問題是NP難題[9]，因此啟發(fā)式約簡算法構(gòu)建成為一種有效優(yōu)化策略。例如文獻[10]提出鄰域近似條件熵來構(gòu)建啟發(fā)式約簡算法；文獻[11]利用粗糙集理論設(shè)計基于依賴計算的啟發(fā)式約簡算法；文獻[12]提出近似質(zhì)量來構(gòu)建啟發(fā)式約簡算法；文獻[13]引入廣義決策保持相似度構(gòu)建啟發(fā)式約簡算法。可見，知識粒度與啟發(fā)式算法是決策表進行屬性約簡的重要手段，值得推廣使用。

區(qū)間值決策表[14]是經(jīng)典決策表的一種擴展，其屬性值為區(qū)間值(即用上下邊界來表示一個不確定概念)，從而能更好地刻畫不確定性對象，當前具有深入研究。例如，文獻[15]基于相似關(guān)系，將近似精度和近似粗糙度推廣到區(qū)間值決策表中，研究了不確定性度量問題；文獻[16]基于信息熵研究了區(qū)間值信息(決策)系統(tǒng)的屬性約簡，并提出2個啟發(fā)式約簡算法；文獻[17]針對不完備區(qū)間值信息系統(tǒng)，提出基于弱相似關(guān)系的不確定性度量；文獻[18]提出區(qū)間值決策系統(tǒng)的特定類分布屬性約簡；文獻[19]針對區(qū)間值信息系統(tǒng)，基于相似等價關(guān)系提出一種非監(jiān)督的屬性約簡算法。特別地，文獻[20]從代數(shù)角度，提出基于正域的區(qū)間值決策表屬性約簡及其啟發(fā)式約簡算法。

綜上，區(qū)間值決策表的屬性約簡研究是有意義的，但基本的相對知識粒度較少被涉及，而其相關(guān)引入可以提供直接而有效屬性約簡手段。由此，本文基于相似關(guān)系[15]，定義區(qū)間相對知識粒度及區(qū)間屬性重要度等概念，建立基于區(qū)間相對知識粒度的屬性約簡及其啟發(fā)式約簡算法，并提供實例分析。相關(guān)工作將推廣相對知識粒度的使用，并從粒計算視角提供一種新的屬性約簡策略。

1 預(yù)備知識

本節(jié)首先復習基于相對知識粒度的經(jīng)典決策表屬性約簡，再預(yù)備區(qū)間值決策表的基本概念。

1.1 基于相對知識粒度的經(jīng)典決策表屬性約簡

經(jīng)典決策表DT={U，AT=C∪d，V,f}，其中U為一個有限非空對象集合，稱為論域；AT為屬性集，其中C為有限條件屬性集，d為有限決策屬性集，C∩d=φ；屬性值域V=∪a∈ATVa，其中Va為任意屬性a∈AT的值域；一個映射函數(shù)滿足f∶U×C→Va滿足對于?xi∈U，在屬性a上的值為f(xi，a)∈Va。對任意條件屬性子集B?C，定義U上等價關(guān)系：IND(B)={(xi，xj)∈U2|f(xi，a)=f(xj，a)，?a∈B}它誘導論域U的一個知識劃分，即U/IND(B)或U/B。設(shè)決策屬性d所誘導的決策劃分U/d={D1，…，Dm}，其中Dh(1≤h≤m)表示決策類。此外，本文用|·|表示集合的基數(shù)。

定義1[3]設(shè)任意一個條件屬性子集B?C所誘導的劃分U/B={X1，X2，…，Xn}，那么決策表中B相對于d的相對知識粒度為

(1)

定義2[3]屬性子集B?C，B為C的一個屬性約簡，若它滿足2個條件

(s)RG(B;d)=RG(C;d);

(n) ?a∈B，RG(B;d)≠RG(B-{a};d)。

定義3[3]?a∈C，a在決策表中的屬性重要度為

Sig(a，C，d)=RG(C-{a};d)-RG(C;d)

(2)

定義1提供相對知識粒度，其能夠直接表征知識劃分對決策劃分的分辨能力。由此，定義2提出基于相對知識粒度的屬性約簡，相應(yīng)的屬性重要度(定義3)可以用于設(shè)計啟發(fā)式約簡算法。

1.2 區(qū)間值決策表

區(qū)間值決策表IVDT={U，AT=C∪d，V,f}，其中U與屬性集C，d類似于上述經(jīng)典情況；屬性值域V=∪a∈ATVa，其中Va為任意屬性a∈AT的值域；信息函數(shù)f:U×C→Va滿足對于?xi∈U，在屬性a上的值為f(xi，a)∈Va是一個區(qū)間值。決策屬性值仍為單值型。

定義4[15]屬性子集B?C，閾值δ∈[0，1]，則關(guān)于B的相似關(guān)系為

(3)

(4)

所有的相似類構(gòu)成一個對應(yīng)于元素的|U|維粒化結(jié)構(gòu):

(5)

命題1[15]設(shè)屬性子集B?C，0≤δ1≤δ2≤1，則有：

定義4提供了對應(yīng)于元素的|U|維粒化結(jié)構(gòu)，其由相似類進行組建，并通過屬性集子集關(guān)系及閾值大小關(guān)系來實現(xiàn)知識粒化(命題1)。考慮到相對知識粒度能夠直接表征知識劃分對決策劃分的分辨能力，下面基于相似關(guān)系誘導的粒化結(jié)構(gòu)，將其引入?yún)^(qū)間值決策表中，提出一種新的屬性約簡方法。

2 基于區(qū)間相對知識粒度的屬性約簡

經(jīng)典相對知識粒度能夠刻畫知識的粗細程度及反映知識劃分對決策劃分的解釋能力，但不適用于區(qū)間值決策表。因此，本節(jié)在相似關(guān)系[15]的基礎(chǔ)上，建立基于區(qū)間相對知識粒度的屬性約簡及其啟發(fā)式約簡算法。并且針對一致區(qū)間值決策表，證明區(qū)間相對知識粒度約簡與代數(shù)約簡是等價的。

2.1 區(qū)間相對知識粒度

定義5設(shè)IVDT={U，AT=C∪d，V,f}是一個區(qū)間值決策表，B?C，閾值δ∈[0，1]。則B相對于d的區(qū)間相對知識粒度為

(6)

命題2RG(δ;B;d)=

(7)

引理1

1)f(g1，g2，…，gm-1，gm)=2(g1g2+g1g3+…+gm-1gm)。

2) 若0≤g1≤t1，0≤g2≤t2，…，0≤gm≤tm，則f(g1，g2，…，gm-1，gm)≤f(t1，t2，…，tm-1，tm)。

證明1)是顯然的。而對于2)有

f(t1，t2，…，tm-1，tm)-f(g1，g2，…，gm-1，gm)=

2(t1t2+t1t3+…+tm-1tm)-

2(g1g2+g1g3+…+gm-1gm)=

2[(t1t2-g1g2)+(t1t3-g1g3)+…+

(tm-1tm-gm-1gm)]≥0

當且僅當g1=t1，g2=t2，…，gm=tm時等號成立。

命題3設(shè)IVDT={U，AT=C∪d，V,f}是一個區(qū)間值決策表，A，B?C，閾值δ∈[0，1]。則以下結(jié)論成立：

1) 若A?B，則RG(δ;B;d)≤RG(δ;A;d)；

2) 若0≤δ1≤δ2≤1，則RG(δ2;B;d)≤RG(δ1;B;d)。

證明1)

由命題2，關(guān)于B和A的區(qū)間相對知識粒度簡化為

因此，RG(δ;B;d)≤RG(δ;A;d)。

2) 與1)的證明類似。

命題3表明，區(qū)間相對知識粒度具有關(guān)于屬性與閾值的雙重粒化單調(diào)性。進而，命題4給出相應(yīng)的值域與最值條件。接下來，給出屬性的必要性和獨立性定義以及屬性約簡構(gòu)建。

定義6設(shè)IVDT={U，AT=C∪d，V,f}是一個區(qū)間值決策表，?a∈C，若RG(δ;C-a;d)=RG(δ;C;d)，則稱a為C中d不必要的屬性，否則稱a為C中d必要的屬性。

定義8設(shè)IVDT={U，AT=C∪D，V,f}是一個區(qū)間值決策表，屬性集B?C，B為C的一個屬性約簡，若它滿足2個條件

(s)RG(δ;B;d)=RG(δ;C;d);

(n) ?a∈B，RG(δ;B;d)≠RG(δ;B-{a};d)。

這里，屬性約簡模擬傳統(tǒng)情況，主要依托區(qū)間相對知識粒度這一核心度量及其粒化單調(diào)性。特別地，區(qū)間相對知識粒度的粒化單調(diào)性可以引導啟發(fā)式搜索；由此，下面提出對應(yīng)的屬性重要度。

定義9設(shè)IVDT={U，AT=C∪d，V,f}是一個區(qū)間值決策表，?a∈C，a關(guān)于C相對于d的區(qū)間屬性內(nèi)重要度為

Siginner(δ;a，C，d)=RG(δ;C-{a};d)-RG(δ;C;d)

(8)

B?C，?a∈C-B，a關(guān)于B相對于d的區(qū)間屬性外重要度為

Sigouter(δ;a，B，d)=RG(δ;B;d)-RG(δ;B∪{a};d)

(9)

區(qū)間屬性內(nèi)重要度Siginner(δ;a，C，d)描述屬性a從屬性集C去除之后導致的區(qū)間相對知識粒度增加量，區(qū)間屬性外重要度Sigouter(δ;a，B，d)描述屬性a添加到屬性集B之后導致的區(qū)間相對知識粒度減少量。相關(guān)度量變化越大，則說明該屬性越重要，因此兩者提供了快速約簡的屬性選擇機制。根據(jù)核屬性概念(定義7)，下面利用區(qū)間內(nèi)屬性重要度構(gòu)造了一個求核方法。

命題5設(shè)IVDT={U，AT=C∪d，V,f}是一個區(qū)間值決策表，?a∈C，則a為C中d必要的屬性?Siginner(δ;a，C，d) > 0，從而

(10)

證明若a為C中d必要的屬性，則RG(δ;C-{a};d)≠RG(δ;C;d)，由區(qū)間相對知識粒度的粒化單調(diào)性知，RG(δ;C-{a};d)>RG(δ;C;d)。

因此，Siginner(δ;a，C，d)>0。反之，若Siginner(δ;a，C，d)>0，則RG(δ;C-{a};d)>RG(δ;C;d)，從而RG(δ;C-{a};d)≠RG(δ;C;d)。由定義6知，a為C中d必要的屬性，故式(10)成立。

2.2 基于區(qū)間相對知識粒度的啟發(fā)式屬性約簡算法

依據(jù)以上分析，本小節(jié)以區(qū)間屬性內(nèi)與外重要度為啟發(fā)式信息，開發(fā)一個以核為約簡起點的啟發(fā)式約簡算法，從而快速獲取一個屬性約簡。其中，核充當基礎(chǔ)，這是因為(鑒于粒化單調(diào)性)核在每個屬性約簡中，這點與傳統(tǒng)情況類似不再詳述。具體算法步驟如下：

算法1基于區(qū)間相對知識粒度的啟發(fā)式屬性約簡算法

輸入 區(qū)間值決策表IVDT及閾值δ。

輸出 IVDT的一個約簡R。

步驟1 計算C相對于d的區(qū)間相對知識粒度RG(δ;C;d)。

步驟3計算R相對于d的區(qū)間相對知識粒度。若RG(δ;R;d)=RG(δ;C;d)，則轉(zhuǎn)向步驟5，否則轉(zhuǎn)向下述步驟4；

步驟4?a∈(C-R)，計算區(qū)間屬性外重要度Sigouter(δ;a，R，d)，選擇區(qū)間屬性外重要度最大的條件屬性a*并入R中，即進行更新R←R∪{a*}。如果此時有RG(δ;R;d)>RG(δ;C;d)，則重復該步驟的選擇與更新過程，直到達到條件RG(δ;R;d)=RG(δ;C;d)，則進入步驟5；

步驟5 輸出R。

算法1的時間復雜度分析如下：

步驟1計算RG(δ;C;d)的時間復雜度為：

O(|U|2·|C|·|U/D|)

步驟2要對每個屬性計算區(qū)間屬性內(nèi)重要度Siginner(δ;a，C，d)，所以時間復雜度為：

O(|U|2·|C|2·|U/D|)

步驟3計算RG(δ;R;d)的時間復雜度為：

O(|U|2·|R|·|U/D|)

步驟4每添加一個屬性到約簡集R中，需對|U-R|個屬性計算區(qū)間屬性外重要度Sigouter(δ;a，R，d)，其時間復雜度為：

O(|U|2·|R|·|C-R|·|U/D|)

所以，考慮其最壞情況下，步驟4時間復雜度為：

O(|U|2[|C|×1+(|C|-1|)×2+

(|C|-2|)×3+…+

3×(|C|-2)+2×(|C|-1|)+

1×|C|]|U/d|)

而該式的時間復雜度不超過

因此，整個算法1的時間復雜度為：

而文獻[20]給出的基于正域的啟發(fā)式約簡算法的時間復雜度為O(|U|2·|C|3·|U/D|)，對比可見，本文所提算法1運行效率優(yōu)于文獻[20]。

2.3 區(qū)間相對知識粒度約簡與代數(shù)約簡等價性證明

文獻[20]提出基于正域的區(qū)間值決策表屬性約簡(即代數(shù)約簡)，其滿足正域相等與獨立性2個條件，而本文定義的基于區(qū)間相對知識粒度的屬性約簡同樣滿足兩個條件：區(qū)間相對知識粒度相等與獨立性條件。下面證明在一致區(qū)間值決策表中，區(qū)間相對知識粒度約簡與代數(shù)約簡是等價的。在此之前，先給出一致區(qū)間值決策表的定義如下。

命題6設(shè)IVDT={U，AT=C∪d，V,f}是一個區(qū)間值決策表，則IVDT是一致區(qū)間值決策表，當且僅當RG(δ;C;d)=0。

所以，RG(δ;C;d)=0。

命題6表明，區(qū)間相對知識粒度能夠刻畫區(qū)間值決策表的一致性。

命題7表明，在一致區(qū)間值決策表中，區(qū)間相對知識粒度與文獻[20]中正域的定義是等價的。因此，基于區(qū)間相對知識粒度的屬性約簡與代數(shù)約簡的定義是等價的。

3 實例分析

為驗證區(qū)間相對知識粒度性質(zhì)的正確性及算法1的有效性，選擇一個已知其約簡的區(qū)間值決策表實例進行說明。文獻[20]從代數(shù)角度分析了表1所示區(qū)間值決策表的屬性約簡，其屬性約簡結(jié)果為R1={a1，a2}和R2={a2，a3}，此時δ=0.65。

例1區(qū)間值決策表IVDT如表1[20]所示，其中U={x1，x2，x3，x4，x5，x6，x7，x8，x9，x10}表示10個對象，C={a1，a2，a3，a4}表示條件屬性集，d為決策屬性集。

表1 區(qū)間值決策表

設(shè)閾值δ=0.65，構(gòu)造屬性增鏈如下：

A1={a1}?A2={a1，a2}?

B={a1，a2，a3}?

C={a1，a2，a3，a4}

取屬性增鏈中的鏈元B，構(gòu)造閾值增鏈如下：

δ1=0.55<δ2=0.65<δ3=0.75<

δ4=0.85<δ5=0.95

下面計算區(qū)間相對知識粒度：

1) 對于屬性增鏈有

RG(0.65;A1;d)=0.64>RG(0.65;A2;d)=0.34≥

RG(0.65;B;d)=0.34≥RG(0.65;C;d)=0.34

2) 對于閾值增鏈有

RG(0.55;B;d)=0.34≥RG(0.65;B;d)=

0.34>RG(0.75;B;d)=0≥

RG(0.85;C;d)=0≥

RG(0.95;B;d)=0

上述2個不等式驗證了區(qū)間相對知識粒度關(guān)于屬性與閾值的雙重粒化單調(diào)性(命題3)。所有度量值均隸屬理論雙界范圍[0，|U|-1](命題4)。

最后根據(jù)算法1求解該區(qū)間值決策表的一個屬性約簡。首先設(shè)置閾值δ=0.65，執(zhí)行步驟1，計算C相對于d的區(qū)間相對知識粒度：

RG(0.65;C;d)=1.17-0.83=0.34

Siginner(0.65;a1，C，d)=0.34-0.34=0，

Siginner(0.65;a2，C，d)=0.64-0.34=0.30，

Siginner(0.65;a3，C，d)=0.34-0.34=0，

Siginner(0.65;a4，C，d)=0.34-0.34=0，

執(zhí)行步驟3，計算R關(guān)于d的區(qū)間相對知識粒度：

RG(0.65;R={a2};d)=0.84>0.34=RG(0.65;C;d)

執(zhí)行步驟4，?a∈C-R，計算每個屬性關(guān)于R相對于d的區(qū)間屬性外重要度：

Sigouter(0.65;a1，R，d)=0.84-0.34=0.50，

Sigouter(0.65;a3，R，d)=0.84-0.34=0.50，

Sigouter(0.65;a4，R，d)=0.84-0.84=0，

基于最大值選取一個屬性并入R中，因?qū)傩詀1與a3的區(qū)間屬性外重要度相同，為不失一般性，對a1與a3都進行檢驗，即分別檢驗R={a1，a2}，R={a2，a3}，可得：

RG(0.65;R={a1，a2};d)=0.34=RG(0.65;C;d)，

RG(0.65;R={a2，a3};d)=0.34=RG(0.65;C;d)；

執(zhí)行步驟5，輸出R={a1，a2}或R={a2，a3}。

可見，通過算法1求解的約簡結(jié)果與文獻[20]基于正域的約簡結(jié)果相同，即本文所提算法可以有效獲取區(qū)間值決策表的屬性約簡。

4 結(jié)論

1) 引入?yún)^(qū)間相對知識粒度等概念，構(gòu)建基于區(qū)間相對知識粒度的屬性約簡及其啟發(fā)式約簡算法。

2) 針對一致區(qū)間值決策表，證明區(qū)間相對知識粒度表示與代數(shù)表示是等價的。

3) 通過具體實例驗證了區(qū)間相對知識粒度性質(zhì)的正確性及算法1的有效性。

4) 所得結(jié)果深化了知識學習與特征優(yōu)化，對區(qū)間值決策表的知識發(fā)現(xiàn)具有重要意義。

5) 在現(xiàn)實生活中，屬性值有可能產(chǎn)生缺失的情況，因此下一步將對基于區(qū)間相對知識粒度的不完備區(qū)間值決策表屬性約簡進行研究。