楊 蕾，張曉燕，徐偉華

(1.重慶理工大學(xué) 理學(xué)院 重慶 400054；2.西南大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 重慶 400715)

0 引言

粗糙集理論是由波蘭數(shù)學(xué)家Pawlak[1]提出的，它是一種用來處理不精確、不完全數(shù)據(jù)問題的一種理論，其研究的主要內(nèi)容之一是屬性約簡(知識約簡)[2-6].所謂屬性約簡，就是在保持知識庫的數(shù)據(jù)分類能力不變的條件下，刪除其中不相關(guān)或不重要的屬性，從而達(dá)到減少冗余數(shù)據(jù)和簡化規(guī)則的目的，實(shí)現(xiàn)了知識的簡化.在Pawlak粗糙集的背景之下,不同的學(xué)者根據(jù)不同的約簡思想,已經(jīng)給出了不同的屬性約簡算法[7].文獻(xiàn)[8]提出了基于差別矩陣的屬性約簡算法,因差別矩陣的直觀簡明性而受到了廣大學(xué)者的關(guān)注.文獻(xiàn)[9]給出了基于差別矩陣的Rough集屬性約簡算法以及屬性約簡的完備算法.文獻(xiàn)[10]也給出了一種基于差別矩陣的屬性約簡完備算法.不僅如此，根據(jù)差別矩陣的不同定義，人們也提出了很多有效的關(guān)于屬性約簡的啟發(fā)式算法，但是這些算法要想得到約簡就必須用到差別矩陣中所有的非空元素.文獻(xiàn)[8]指出，每一個(gè)信息系統(tǒng)對應(yīng)的差別矩陣中所有非空元素的合取構(gòu)成了該信息系統(tǒng)的屬性約簡集，由合取運(yùn)算可知，差別矩陣的重復(fù)元素和父集元素在求取屬性約簡時(shí)起不到任何作用，但這些元素卻占用了大量的存儲空間，同時(shí)也增加了求取約簡的時(shí)間.為了消除差別矩陣中重復(fù)元素的出現(xiàn)，文獻(xiàn)[11]提出了一種新的差別矩陣存儲方法，實(shí)現(xiàn)了差別矩陣的壓縮儲存.為了消除差別矩陣中冗余的父集元素，文獻(xiàn)[12]給出了一種基于差別信息樹的屬性約簡算法,該算法不僅能消除差別矩陣中的重復(fù)元素,而且在大多數(shù)情況下亦能消除父集元素的影響,實(shí)現(xiàn)對差別矩陣的壓縮儲存.

由于差別信息樹是在等價(jià)關(guān)系下差別矩陣的基礎(chǔ)上提出的，而等價(jià)關(guān)系下的差別矩陣是一個(gè)對稱矩陣.因此，在求信息系統(tǒng)的約簡時(shí)可以只用差別矩陣中的上三角元素或者只用下三角元素.當(dāng)研究序信息系統(tǒng)時(shí)，因?yàn)橛尚蛐畔⑾到y(tǒng)得到的差別矩陣具有非對稱性，所以基于差別信息樹的屬性約簡并不一定適用于不協(xié)調(diào)序決策信息系統(tǒng)下的屬性約簡.本文在差別信息樹的基礎(chǔ)上提出了基于分配可辨識矩陣的差別信息樹,給出了適用于不協(xié)調(diào)序決策信息系統(tǒng)的分配約簡算法.

1 預(yù)備知識

定義1[13]設(shè)一個(gè)決策信息系統(tǒng)為四元組I=(U,AT∪DT,F,G),而三元組I=(U,AT,F)為信息系統(tǒng),其中:U={x1,x2,…,xn}是有限對象集；AT={a1,a2,…,ap}是有限條件屬性集；DT={d1,d2,…,dq}是有限決策屬性集,且AT∩DT=?；F={f|U→Va,a∈AT}是U與AT的關(guān)系集,Va為a的有限值域；G={g|U→Vd,d∈DT}是U與DT的關(guān)系集,Vd為d的有限值域.

定義5[13]設(shè)I≥=(U,AT∪h573pf3,F,G)為不協(xié)調(diào)序決策信息系統(tǒng),記

?σAT(xj)}，

分配可辨識公式的極小析取范式中的所有合取式是不協(xié)調(diào)序決策信息系統(tǒng)的分配約簡.

所以表1中不協(xié)調(diào)序決策信息系統(tǒng)的分配約簡為{a1,a3}與{a2,a3}.

表1 一個(gè)不協(xié)調(diào)序決策信息系統(tǒng)Tab.1 An uncoordinated ordinal decision information system

表2 分配可辨識矩陣Tab.2 Assignment identifiable matrix

2 基于分配可辨識矩陣的差別信息樹的設(shè)計(jì)與實(shí)現(xiàn)

定義7[12]差別信息樹是一棵有序樹,其中序體現(xiàn)在它的條件屬性的順序是一個(gè)從左到右的序列,其順序不能更改或顛倒.

差別信息樹的特征有以下幾個(gè)方面:① 差別信息樹的每個(gè)節(jié)點(diǎn)最多有|AT|個(gè)孩子節(jié)點(diǎn),其中|AT|為帶決策的信息系統(tǒng)中條件屬性的個(gè)數(shù).② 差別信息樹的每個(gè)節(jié)點(diǎn)由前綴指針、后繼指針、節(jié)點(diǎn)名、同名指針組合而成.其中前綴指針指向該節(jié)點(diǎn)的前綴節(jié)點(diǎn)(即父親節(jié)點(diǎn))，后繼指針指向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)(即孩子節(jié)點(diǎn))，節(jié)點(diǎn)名標(biāo)記了該節(jié)點(diǎn)所對應(yīng)的條件屬性名，同名指針指向該差別信息樹中與該節(jié)點(diǎn)具有相同節(jié)點(diǎn)名的其他路徑中的節(jié)點(diǎn).③ 差別信息樹的子樹同樣是一棵有序樹，其中條件屬性的順序同樣不能更改或顛倒.

算法1序決策信息系統(tǒng)中基于分配可辨識矩陣的差別信息樹的構(gòu)建算法.

輸入： 一個(gè)不協(xié)調(diào)序決策信息系統(tǒng)I≥=(U,AT∪5flvtzr,F,G)；

輸出： 該序決策信息系統(tǒng)所對應(yīng)的差別信息樹.

getDI-tree(decision tableI≥)

{

(1) 創(chuàng)建差別信息樹的根節(jié)點(diǎn)TN，并令TN為null；

While(B≠?)

{

A.選擇B中最左邊的元素為a；

B.if(TN所有子節(jié)點(diǎn)中存在屬性名為a的子節(jié)點(diǎn)N)

{

如果N是一葉子節(jié)點(diǎn)，則采用不擴(kuò)展路徑策略，不構(gòu)建B中剩余屬性對應(yīng)的節(jié)點(diǎn)；

如果a為B中最后一個(gè)元素，則采取刪除子樹策略，從差別信息樹中刪除以節(jié)點(diǎn)N為根的子樹,但保留節(jié)點(diǎn)N；

否則令TN=N；

}

else

{

a) 創(chuàng)建一新節(jié)點(diǎn)N′，節(jié)點(diǎn)N′作為TN一子節(jié)點(diǎn)，同時(shí)初始N′的屬性名為a，并通過該節(jié)點(diǎn)的同名指針連接到與該節(jié)點(diǎn)具有相同屬性名的節(jié)點(diǎn)上，從而構(gòu)成了一個(gè)同名屬性節(jié)點(diǎn)鏈；

b) 令TN=N′；

}

C.令B?B-{a}；

}

}

例2根據(jù)算法1及表2給出該序決策信息系統(tǒng)中基于分配可辨識矩陣的差別信息樹的構(gòu)建過程：

1) 創(chuàng)建序決策信息系統(tǒng)基于分配可辨識矩陣的差別信息樹的根節(jié)點(diǎn).根據(jù)分配可辨識矩陣中的每一個(gè)條件屬性子集，將子集中的屬性次序按序決策信息系統(tǒng)中條件屬性從左到右的順序排列.

2) 構(gòu)建分配可辨識矩陣中第一個(gè)屬性子集{a1,a3}所對應(yīng)的路徑〈a1,a3〉,將該路徑插入到要構(gòu)建的差別信息樹中.

3) 根據(jù)可辨識矩陣中第二個(gè)屬性子集{a3}創(chuàng)建另一條新的路徑〈a3〉.

4) 對于第三個(gè)與第五個(gè)屬性子集{a1,a3}，因?yàn)樗鼈兣c第一個(gè)屬性子集完全相同，所以第三個(gè)與第五個(gè)屬性子集{a1,a3}所對應(yīng)的路徑也映射到〈a1,a3〉上.

5) 同4)，將第四個(gè)、第六個(gè)與第九個(gè)屬性子集{a3}所對應(yīng)的路徑映射到〈a3〉上.

6) 對于第七個(gè)屬性子集A={a1,a2,a3}，創(chuàng)建另一條新的路徑〈a1,a2,a3〉，它與屬性{a1,a3}共享前綴〈a1〉.

7) 對于第八個(gè)屬性子集{a1,a2}，因?yàn)閧a1,a2}?A，采用刪除子樹策略，從路徑〈a1,a2,a3〉中刪除a2之后的所有節(jié)點(diǎn)，即路徑〈a1,a2,a3〉被修改為〈a1,a2〉.

圖1給出了所構(gòu)建的基于分配可辨識矩陣的差別信息樹.在構(gòu)建過程中采用不擴(kuò)展路徑策略以及刪除子樹策略，將相同的分配可辨識屬性集映射到同一條路徑中.將具有相同前綴的分配可辨識屬性集{a1,a2}與{a1,a2,a3}映射到同一條路徑〈a1,a2〉中.分配可辨識矩陣中屬性集{a1,a2,a3}與{a1,a3}共享前綴〈a1〉,達(dá)到對分配可辨識矩陣的壓縮儲存，從而減少了構(gòu)建基于分配可辨識矩陣的差別信息樹的時(shí)空復(fù)雜度.

圖1 基于分配可辨識矩陣的差別信息樹Fig.1 Discernibility information tree based on assignment identifiable matrix

定理1基于分配可辨識矩陣的差別信息樹中包括了能夠獲得不協(xié)調(diào)序決策信息系統(tǒng)的分配約簡所需要的所有屬性.

定理2基于分配可辨識矩陣的差別信息樹中，所有只有一個(gè)節(jié)點(diǎn)的路徑所對應(yīng)的分配可辨識屬性集，構(gòu)成了該序決策信息系統(tǒng)中條件屬性集的核cored(A).

證明由基于分配可辨識矩陣的差別信息樹的構(gòu)建過程可知:假設(shè)該信息樹中某一節(jié)點(diǎn)的屬性名為a,并且該樹中存在某一條路徑僅包含屬性名為a的節(jié)點(diǎn),則存在分配可辨識屬性集{a}與該路徑對應(yīng).在分配可辨識矩陣中,若a∈A且{a}為分配可辨識矩陣中的一個(gè)非空元素,則稱a相對d在A中是必要的.A的所有必要屬性的集合構(gòu)成了A相對d的核,即cored(A).

定理3設(shè)R是基于分配可辨識矩陣的差別信息樹中根節(jié)點(diǎn)的所有子節(jié)點(diǎn)所代表的條件屬性集合,則σR(x)=σA(x)成立.

基于定理3,只要刪除R中所有不必要的條件屬性,就可以得到該序決策信息系統(tǒng)的一個(gè)完備約簡.

給定一個(gè)不協(xié)調(diào)的帶決策的序信息系統(tǒng)I≥=(U,A∪tnb5zhz,F,G),如果該序信息系統(tǒng)中有|U|個(gè)對象以及|A|個(gè)條件屬性,則在分配可辨識矩陣中最多可以得到|U|2個(gè)非空的條件屬性的子集(即差別信息).假設(shè)分配可辨識矩陣中實(shí)際的非空條件屬性的子集數(shù)為M(一般情況下M?|U|2)，由例2的構(gòu)建過程可以看出，一棵差別信息樹最多可以有M條不同的路徑,并且每一條路徑中最多可以有|A|個(gè)節(jié)點(diǎn)，所以一棵差別信息樹中最多可以有M|A|個(gè)節(jié)點(diǎn)，又由于在基于分配可辨識矩陣的差別信息樹中，許多路徑都存在共享前綴，導(dǎo)致差別信息樹中的實(shí)際節(jié)點(diǎn)數(shù)遠(yuǎn)小于M|A|.因此，在最壞的情況下，基于分配可辨識矩陣的差別信息樹的空間復(fù)雜度為O(|A|*|U|2).

另外，在構(gòu)建基于分配可辨識矩陣的差別信息樹的過程中，向差別信息樹中插入路徑的次數(shù)最多為|U|2次，并且在構(gòu)建路徑的過程中最多比較并插入|A|個(gè)節(jié)點(diǎn)，刪除Mi(其中i∈{1,2,…,|U|2})個(gè)節(jié)點(diǎn).因此，基于分配可辨識矩陣的差別信息樹的時(shí)間復(fù)雜度為|A|*|U|2+(M1+M2+…+M|U|2).已知在一棵差別信息樹中最多可以有|A|*|U|2個(gè)節(jié)點(diǎn)，則M1+M2+…+M|U|2的值至多為|A|*|U|2.綜上所述，基于分配可辨識矩陣的差別信息樹的時(shí)間復(fù)雜度也為O(|A|*|U|2).

3 基于分配可辨識矩陣的差別信息樹的分配約簡算法

為了驗(yàn)證所提出的序決策信息系統(tǒng)中基于分配可辨識矩陣的差別信息樹的有效性，算法2給出了基于該差別信息樹的分配約簡完備算法.

算法2序決策信息系統(tǒng)中基于分配可辨識矩陣的差別信息樹的分配約簡算法.

輸入： 序決策信息系統(tǒng)中基于分配可辨識矩陣的差別信息樹;

輸出： 不協(xié)調(diào)序決策信息系統(tǒng)的一個(gè)分配約簡.

Step1創(chuàng)建一個(gè)空集R.

Step2獲取基于分配可辨識矩陣的差別信息樹中只有一個(gè)節(jié)點(diǎn)的路徑，將這些節(jié)點(diǎn)對應(yīng)屬性名放在一個(gè)集合R′ 中.

Step3如果R′≠?，則對于?a∈R′，在由分配可辨識矩陣得到的差別信息樹中刪除包含屬性a的所有路徑.

Step4令R?R′.

Step5如果由分配可辨識矩陣得到的差別信息樹中只含有根節(jié)點(diǎn)，則轉(zhuǎn)Step 7.

Step6在由分配可辨識矩陣得到的差別信息樹中,選擇根節(jié)點(diǎn)最右邊的子節(jié)點(diǎn),假設(shè)該子節(jié)點(diǎn)為b,令R?R∪,并從由分配可辨識矩陣得到的差別信息樹中刪除含有節(jié)點(diǎn)的路徑,轉(zhuǎn)Step 5.

Step7輸出R，算法結(jié)束.

例3基于圖1，算法2的求解過程如下:

1) 創(chuàng)建一個(gè)空集R.

2) 從基于分配可辨識矩陣的差別信息樹中獲取只含有一個(gè)節(jié)點(diǎn)的路徑〈a3〉，令R?{a3}，然后刪除信息樹中含有屬性名為a3的全部路徑.

3) 此時(shí)基于分配可辨識矩陣的差別信息樹中僅含有一條路徑〈a1,a2〉，選取根節(jié)點(diǎn)最右邊的子節(jié)點(diǎn)a1，令R?R∪{a1}，然后刪除信息樹中含有屬性名為a1的全部路徑.

4) 此時(shí)圖1給出的基于分配可辨識矩陣的差別信息樹只剩下根節(jié)點(diǎn)，輸出R?{a3,a1}，算法結(jié)束.因而{a3,a1}即為通過基于分配可辨識矩陣的差別信息樹所求得的一個(gè)約簡.

4 結(jié)論

在差別信息樹的基礎(chǔ)上提出了一種能壓縮儲存分配可辨識矩陣的數(shù)據(jù)結(jié)構(gòu)，即基于分配可辨識矩陣的差別信息樹.和直接通過分配可辨識公式的極小析取范式求分配約簡相比，通過該差別信息樹可以大大縮短求取不協(xié)調(diào)序信息系統(tǒng)的分配約簡的時(shí)空復(fù)雜度.但是從基于分配可辨識矩陣的構(gòu)建過程可知，將分配可辨識屬性集插入到差別信息樹中用到的條件屬性的順序是決策表中屬性的原始順序，沒有考慮屬性重要度以及核屬性對基于分配可辨識矩陣的差別信息樹在構(gòu)建過程中的影響，并且通過該差別信息樹只能得到?jīng)Q策表的一個(gè)約簡.下一步的工作是結(jié)合屬性重要度以及核屬性來完善該差別信息樹的構(gòu)建，看能否實(shí)現(xiàn)對分配可辨識矩陣的進(jìn)一步壓縮儲存.