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

唐鵬飛，莫智文，謝 鑫

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

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

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

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

1 預(yù)備知識

本節(jié)首先復(fù)習(xí)基于相對知識粒度的經(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上等價(jià)關(guān)系：IND(B)={(xi，xj)∈U2|f(xi，a)=f(xj，a)，?a∈B}它誘導(dǎo)論域U的一個知識劃分，即U/IND(B)或U/B。設(shè)決策屬性d所誘導(dǎo)的決策劃分U/d={D1，…，Dm}，其中Dh(1≤h≤m)表示決策類。此外，本文用|·|表示集合的基數(shù)。

定義1[3]設(shè)任意一個條件屬性子集B?C所誘導(dǎo)的劃分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è)計(jì)啟發(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|維?；Y(jié)構(gòu):

(5)

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

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

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

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

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

當(dāng)且僅當(dāng)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)性。進(jìn)而，命題4給出相應(yīng)的值域與最值條件。接下來，給出屬性的必要性和獨(dú)立性定義以及屬性約簡構(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)性可以引導(dǎ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去除之后導(dǎo)致的區(qū)間相對知識粒度增加量，區(qū)間屬性外重要度Sigouter(δ;a，B，d)描述屬性a添加到屬性集B之后導(dǎo)致的區(qū)間相對知識粒度減少量。相關(guān)度量變化越大，則說明該屬性越重要，因此兩者提供了快速約簡的屬性選擇機(jī)制。根據(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ā)一個以核為約簡起點(diǎn)的啟發(fā)式約簡算法，從而快速獲取一個屬性約簡。其中，核充當(dāng)基礎(chǔ)，這是因?yàn)?鑒于?；瘑握{(diào)性)核在每個屬性約簡中，這點(diǎn)與傳統(tǒng)情況類似不再詳述。具體算法步驟如下：

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

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

輸出 IVDT的一個約簡R。

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

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

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

步驟5 輸出R。

算法1的時間復(fù)雜度分析如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

而該式的時間復(fù)雜度不超過

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

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

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

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

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

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

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

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

3 實(shí)例分析

為驗(yàn)證區(qū)間相對知識粒度性質(zhì)的正確性及算法1的有效性，選擇一個已知其約簡的區(qū)間值決策表實(shí)例進(jìn)行說明。文獻(xiàn)[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

下面計(jì)算區(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個不等式驗(yàn)證了區(qū)間相對知識粒度關(guān)于屬性與閾值的雙重?；瘑握{(diào)性(命題3)。所有度量值均隸屬理論雙界范圍[0，|U|-1](命題4)。

最后根據(jù)算法1求解該區(qū)間值決策表的一個屬性約簡。首先設(shè)置閾值δ=0.65，執(zhí)行步驟1，計(jì)算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，計(jì)算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，計(jì)算每個屬性關(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都進(jìn)行檢驗(yàn)，即分別檢驗(yàn)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é)果與文獻(xiàn)[20]基于正域的約簡結(jié)果相同，即本文所提算法可以有效獲取區(qū)間值決策表的屬性約簡。

4 結(jié)論

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

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

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

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

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