區(qū)間值序信息系統(tǒng)中差別信息樹的屬性約簡*

楊 蕾，張曉燕，徐偉華

1.重慶理工大學(xué) 理學(xué)院，重慶 400054

2.西南大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，重慶 400715

1 引言

波蘭數(shù)學(xué)家Pawlak[1]在1982年提出了粗糙集理論用以解決不精確、不完備數(shù)據(jù)問題，它的一個主要課題是屬性約簡[2-8]。屬性約簡即去掉知識庫中冗余的屬性之后其數(shù)據(jù)的分類能力保持不變，從而達(dá)到數(shù)據(jù)表降維的目的，減少了冗余數(shù)據(jù)，簡化了規(guī)則。不少學(xué)者已經(jīng)在不同的粗糙集背景下根據(jù)不同的屬性約簡思想提出了不同的屬性約簡方法[9]。自從Skowron等人[10]提出通過差別矩陣來求取屬性約簡的思想之后，差別矩陣因?yàn)槠渥陨淼闹庇^簡明性被廣大學(xué)者關(guān)注和研究。蔣瑜、王燮等人[11]提出了基于差別矩陣的Rough集屬性約簡算法，他們主要分析了不同的差別矩陣對求取屬性約簡效率的影響，然后定義一種新的差別矩陣來減少矩陣中非空差別信息的個數(shù)從而達(dá)到提高效率的目的。蔣瑜、王鵬等人[12]提出了基于差別矩陣的屬性約簡的完備算法，它們結(jié)合的屬性重要度以及迭代的思想來求取決策表的最小約簡；王兵和陳善本[13]也給出了一種基于差別矩陣的屬性約簡完備算法，該算法的特別之處在于迭代過程中對各類屬性的處理。但是在通過差別矩陣來求取屬性約簡的這些算法當(dāng)中，要想獲得約簡就必須使用差別矩陣中所有的非空元素。Skowron等[10]提出在求決策表的屬性約簡時將決策表所對照的差別矩陣中的所有非空元素進(jìn)行合取即可，但在使用合取運(yùn)算的時候相同（重復(fù)）元素和父集元素對屬性約簡時沒有任何作用，但這些重復(fù)元素和父集元素卻占用了大量的存儲空間，同時也增加了求取約簡的時間。為了消除差別矩陣中重復(fù)元素的出現(xiàn)，文獻(xiàn)[14]提出了一種新的差別矩陣存儲方法（C-Tree）實(shí)現(xiàn)了差別矩陣的壓縮儲存，但是該方法還存在一定的弊端，當(dāng)父集元素和子集元素同時出現(xiàn)的時候它保留了父集元素，從而使該樹中還存在一定數(shù)量的冗余元素；為了消除差別矩陣中冗余的父集元素，蔣瑜[15]給出了一種基于差別信息樹的屬性約簡算法,該算法不僅能消除差別矩陣中的重復(fù)元素，在大多數(shù)情況下亦能消除父集元素的影響，實(shí)現(xiàn)對差別矩陣的壓縮儲存。但是蔣瑜所提出的差別信息樹是通過等價關(guān)系下的差別矩陣獲得的，而基于等價關(guān)系的差別矩陣是對稱的，因此在求約簡時只用差別矩陣中的上三角元素或者下三角元素即可。現(xiàn)在在區(qū)間值序信息系統(tǒng)的背景下考慮屬性約簡，其差別矩陣便失去了對稱性，因此基于差別信息樹的屬性約簡并不一定適用于區(qū)間值序信息系統(tǒng)下的屬性約簡。

本文在區(qū)間值序信息系統(tǒng)的背景下，結(jié)合了蔣瑜提出的差別信息樹的優(yōu)點(diǎn)，提出了基于可分辨矩陣的差別信息樹，并在此基礎(chǔ)上給出區(qū)間值序信息系統(tǒng)的基于差別信息樹的完備的屬性約簡方法。最后在第4章給出了實(shí)證分析，驗(yàn)證了該方法的可行性以及有效性。

2 預(yù)備知識

本章主要講述了有關(guān)區(qū)間值序信息系統(tǒng)下求取屬性約簡的理論基礎(chǔ)以及差別信息樹等相關(guān)知識。

定義1[16]稱三元組I=(U,A,F)為信息系統(tǒng)，其中：U是有限的對象集；A是有限的條件屬性集；F是U與A的關(guān)系集；Va為a的有限值域。若?f∈F,a∈A和xi∈U都有f(xi,a)=[aL(xi),aU(xi)]。

那么稱I=(U,A,F)為區(qū)間值信息系統(tǒng)，其中aL(xi)和aU(xi)都是實(shí)數(shù)且滿足aL(xi)≤aU(xi)；f(xi,a)為對象xi在屬性a下的屬性值且f(xi,a)是一個區(qū)間數(shù)。當(dāng)aL(xi)=aU(xi)時，屬性值f(xi,a)為一個實(shí)數(shù)，因此區(qū)間值信息系統(tǒng)是單值信息系統(tǒng)的推廣。

定義2[16]設(shè)I=(U,A,F)是一個區(qū)間值信息系統(tǒng)，對?a∈A，可以對區(qū)間值信息系統(tǒng)中的屬性值進(jìn)行比較，定義：

定義4[16]設(shè)I≥=(U,A,F)為區(qū)間值序信息系統(tǒng)，辨矩陣。特別地，對 ?xi,xj∈U，有Dis≥A(xi,xi)=? 并且得到：

定義6[16]設(shè)I≥=(U,A,F)為區(qū)間值序信息系統(tǒng)，M≥A=∧{∨{a|a∈Dis≥A(xi,xj)}}所對應(yīng)的極小析取范式為：記Bk={as|s=1,2,…,qk}，則 {Bk|k=1,2,…,p}是區(qū)間值信息系統(tǒng)I≥的所有約簡的集合。

定義7[15]差別信息樹是一棵有序樹，其中序體現(xiàn)在：它的條件屬性的排列順序是按照原信息系統(tǒng)中條件屬性的順序從左到右進(jìn)行排列，順序不能顛倒或者改變。差別信息樹有如下幾個特征：

（1）差別信息樹中的每個節(jié)點(diǎn)最多存在|A|個子節(jié)點(diǎn)，其中|A|代表信息表中條件屬性的個數(shù)。

（2）差別信息樹中的每一個節(jié)點(diǎn)涵蓋了4個方面的信息，分別為：前綴指針、后繼指針、節(jié)點(diǎn)名、同名指針。其中：前綴指針指向該節(jié)點(diǎn)的父親節(jié)點(diǎn)，后繼指針指向該節(jié)點(diǎn)的孩子節(jié)點(diǎn)，節(jié)點(diǎn)名記錄了該節(jié)點(diǎn)所對應(yīng)的條件屬性名稱，同名指針則指向差別信息樹中與該節(jié)點(diǎn)具有相同條件屬性名的其他路徑當(dāng)中的節(jié)點(diǎn)。

（3）差別信息樹的子樹也是一棵有序樹，其中條件屬性的排列順序同樣不能顛倒或者改變。

3 區(qū)間值序信息系統(tǒng)中基于差別信息樹的屬性約簡方法

本章將通過差別信息樹的概念，給出區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹的算法，并通過相關(guān)定理來證明由該差別信息樹得到區(qū)間值序信息系統(tǒng)屬性約簡的合理性。

首先，根據(jù)差別信息樹的定義和蔣瑜提出的差別信息樹的設(shè)計與實(shí)現(xiàn)過程給出區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹的構(gòu)建過程：

算法1區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹的構(gòu)建方法

輸入：區(qū)間值序信息系統(tǒng)I≥=(U,A,F)。

輸出：區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹。

1.創(chuàng)建區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹的根節(jié)點(diǎn)TN，并令TN為null；

2.根據(jù)Dis≥A(xi,xj)={a∈A|(xi,xj)?R≥a}求出任意(xi,xj)所對應(yīng)的可分辨屬性集Dis≥A(xi,xj)，從而得到可分辨矩陣Dis≥A=(Dis≥A(xi,xj))|U|×|U|。設(shè)B?A滿足B=Dis≥A(xi,xj)(?xi,xj)且B中元素的順序按區(qū)間值信息系統(tǒng)中條件屬性的順序進(jìn)行排列。

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

從算法1可以看出：在區(qū)間值序信息系統(tǒng)下構(gòu)建基于可分辨矩陣的差別信息樹時運(yùn)用了不擴(kuò)展路徑策略以及刪除子樹策略，即所構(gòu)建的差別信息樹具有如下幾個特征：

（1）將相同的分配可辨識屬性集映射到同一條路徑當(dāng)中；

（2）將具有相同前綴的可分辨屬性集映射到最小的可分辨屬性集所對應(yīng)的路徑當(dāng)中；

（3）可分辨矩陣中的屬性集存在共享前綴。

因此，在區(qū)間值序信息系統(tǒng)下構(gòu)建的基于可分辨矩陣的差別信息樹實(shí)現(xiàn)了對分配可辨識矩陣的壓縮儲存，從而減少了構(gòu)建基于可分辨矩陣的差別信息樹的時空復(fù)雜度。

區(qū)間值序信息系統(tǒng)下基于可分辨矩陣的差別信息樹的相關(guān)定理如下：

定理1區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹中包含了獲得區(qū)間值序信息系統(tǒng)的屬性約簡所需要的所有屬性。

證明設(shè)區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹中所有路徑的可分辨屬性集存放在集合DS中，可分辨矩陣中所有元素存放在集合Dis≥A中。由算法1所對應(yīng)的基于可分辨矩陣的差別信息樹的構(gòu)建過程有：DS?Dis≥A，對于?(xi,xj)有Dis≥A(xi,xj)∈Dis≥A,?Dis≥AT(xi′,xj′)∈DS,s.t.Dis≥AT(xi′,xj′)?Dis≥AT(xi,xj),由運(yùn)算公理可知：Dis≥AT(xi,xj)與Dis≥AT(xi′,xj′)作合取運(yùn)算得到的結(jié)果還是Dis≥AT(xi′,xj′)。從而，區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹中包含了獲得區(qū)間值序信息系統(tǒng)的屬性約簡所需要的所有屬性。

定理2區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹中所有僅含一個節(jié)點(diǎn)的路徑所對應(yīng)的單元素可分辨屬性集的并組成了該區(qū)間值序信息系統(tǒng)中條件屬性集的核core(A)。

證明通過在區(qū)間值序信息系統(tǒng)下構(gòu)建基于可分辨矩陣的差別信息樹的過程可知：假設(shè)該差別信息樹中存在一個節(jié)點(diǎn)名為a的節(jié)點(diǎn)，而且該樹中存在僅包含節(jié)點(diǎn)名為a的節(jié)點(diǎn)的路徑，則存在可分辨屬性集{a}與該路徑對應(yīng)。在可分辨矩陣中，若a∈A并且{a}為可分辨矩陣中的單元素集，則稱a為A中的必要屬性。A中所有必要屬性的集合構(gòu)成了A的核，即core(A)。

接下來，將分析算法1的時空復(fù)雜度。

對一個區(qū)間值序信息系統(tǒng)I≥=(U,A,F)來說，若存在|U|個對象、|A|個條件屬性，則在可分辨矩陣中最多可以得到|U|2個非空的條件屬性的子集（即差別信息），假設(shè)可分辨矩陣中實(shí)際的非空條件屬性的子集數(shù)為M（一般情況下，M＜＜|U|2）。由基于可分辨矩陣的差別信息樹的構(gòu)建過程可以看出，一棵差別信息樹最多可以有M條不同的路徑并且每一條路徑中最多可以有|A|個節(jié)點(diǎn)，因此，一棵差別信息樹中最多可以有M×|A|個節(jié)點(diǎn)，又由于在基于可分辨矩陣的差別信息樹中存在許多的路徑都存在共享前綴導(dǎo)致差別信息樹中的實(shí)際節(jié)點(diǎn)數(shù)遠(yuǎn)小于M×|A|。因此在最壞的情況下基于分配可辨識矩陣的差別信息樹的空間復(fù)雜度為O(|A|×|U|2)。

和文獻(xiàn)[11]提出的差別矩陣存儲方法（C-Tree）相比，在基于可分辨矩陣的差別信息樹的構(gòu)建中，當(dāng)父集元素和子集元素同時出現(xiàn)的時候，它保留了子集元素，消除差別矩陣中冗余的父集元素，更進(jìn)一步對差別矩陣進(jìn)行了存儲壓縮。在空間復(fù)雜度的比較上，基于可分辨矩陣的差別信息樹的空間復(fù)雜度小于C-Tree的空間復(fù)雜度。

為了驗(yàn)證算法1所提出的區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹的合理性以及有效性，給出了區(qū)間值序信息系統(tǒng)中基于該差別信息樹的屬性約簡方法。

算法2區(qū)間值序信息系統(tǒng)中基于可分辨矩陣差別信息樹的屬性約簡方法

輸入：區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹。

輸出：由差別信息樹得到的屬性約簡。

1.創(chuàng)建空集R；

2.將基于可分辨矩陣差別信息樹中只含單個節(jié)點(diǎn)的路徑，將這些節(jié)點(diǎn)對應(yīng)屬性名放在一個集合R′中；

3.若R′≠?，對所有a∈R′，在基于可分辨矩陣差別信息樹中刪掉所有含節(jié)點(diǎn){a}的路徑；

4.令R←R′；

5.從基于可分辨矩陣差別信息樹中選擇其根節(jié)點(diǎn)的最右孩子節(jié)點(diǎn)并假設(shè)該子節(jié)點(diǎn)所對應(yīng)的屬性名為b，此時令R←R?{b}，然后在得到的差別信息樹中去掉所有含節(jié)點(diǎn)b的路徑；

6.若基于可分辨矩陣的差別信息樹中僅含有根節(jié)點(diǎn)，輸出R，算法結(jié)束。

下面給出算法2的完備性證明：

對區(qū)間值序信息系統(tǒng)的可分辨矩陣來說，若R?A是一個完備約簡，同樣的R需要滿足兩個條件：（1）?Dis≥A(xi,xj)≠?，有Dis≥A(xi,xj)?R≠?；（2）?r∈R,?Dis≥A(xi,xj)，滿足Dis≥A(xi,xj)?(R-{r})=?。

由定理1知道：區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹中包含了獲得區(qū)間值序信息系統(tǒng)的屬性約簡所需要的所有屬性。因此對基于可分辨矩陣的差別信息樹來說，若R?A是一個完備約簡，R需要滿足兩個條件如下：

（1）?B∈DS，B?R≠?（其中DS為包含了基于可分辨矩陣差別信息樹的所有路徑所代表的可分辨屬性集的集合）；

（2）?r∈R，?B∈DS，滿足B?(R-{r})=?。

若算法2完備只需證明算法2輸出的R滿足條件（1）、（2）均可。

由算法2知，條件（1）顯然成立，下證條件（2）滿足。

由定理2可知：區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹中所有僅含一個節(jié)點(diǎn)的路徑所對應(yīng)的單元素可分辨屬性集的并組成了該區(qū)間值序信息系統(tǒng)中條件屬性集的核core(A)。

將算法2第二步得到的core(A)看作R的一部分并在基于可分辨矩陣差別信息樹中刪掉所有含有core(A)中元素的路徑。

令R′=R-core(A)。若r是R′中最右邊的一個元素，則在當(dāng)前的差別信息樹中，根節(jié)點(diǎn)最右邊的孩子節(jié)點(diǎn)的節(jié)點(diǎn)名一定是r，并且以該節(jié)點(diǎn)為根的子樹中一定不包含R′-{r}中任何屬性所對應(yīng)的節(jié)點(diǎn)，則對r∈R,?B∈DS滿足B?(R-{r})=?。可證R′中所有元素都滿足該條件。因此，算法2得到的約簡是完備約簡。

4 實(shí)證分析

給定一個區(qū)間值序信息系統(tǒng)I≥=(U,A,F)（表1），其中有限對象集U={x1,x2,…,x10}，有限屬性集為A={a,b,c,d,e}。

Table1 Interval valued sequence information systems表1 區(qū)間值序信息系統(tǒng)

先求取每個對象對的可分辨屬性集，從而獲得區(qū)間值序信息系統(tǒng)的可分辨矩陣。從而，表1所對應(yīng)的可分辨矩陣如表2所示。

Table2 Discernibility matrix of interval valued ordinal information systems in Table 1表2 表1對應(yīng)的區(qū)間值序信息系統(tǒng)的可分辨矩陣

注2可分辨矩陣中每一對對象對的可分辨屬性集均應(yīng)該為集合的形式，此處為了簡便寫成了如表2的形式。

根據(jù)極小析取范式可以求得表1所對應(yīng)的區(qū)間值序信息系統(tǒng)的約簡如下：

根據(jù)算法1給出表1所對應(yīng)的區(qū)間值序信息系統(tǒng)中基于可分辨矩陣的差別信息樹的具體構(gòu)建過程如下：

（1）首先創(chuàng)建根節(jié)點(diǎn)；然后求取各個對象對的可分辨屬性集，將可分辨屬性集中的屬性順序按區(qū)間值序信息系統(tǒng)中條件屬性從左至右的順序排列；最后得到可分辨矩陣如表2所示。

（2）構(gòu)建可分辨矩陣中第一個可分辨屬性集A={a,b,c,d,e}所對應(yīng)的路徑＜a,b,c,d,e＞，將此路徑插入到要構(gòu)建的基于可分辨矩陣的差別信息樹當(dāng)中。

（3）為第二個可辨識屬性集{a,b,c,e}創(chuàng)建其對應(yīng)的路徑＜a,b,c,e＞，其與路徑＜a,b,c,d,e＞具有相同的前綴＜a,b,c＞。

（4）對于第三個可分辨屬性集A，因?yàn)榛诳煞直婢仃嚨牟顒e信息樹中已經(jīng)存在A所對應(yīng)的路徑＜a,b,c,d,e＞，所以不構(gòu)建新的路徑。同理，將所有相同的可分辨屬性集映射到同一個子集中。

（5）構(gòu)建可分辨屬性集{a,c}對應(yīng)的路徑＜a,c＞，它與路徑＜a,b,c,d,e＞和＜a,b,c,e＞具有相同的前綴＜a＞。

依此類推，最后得到區(qū)間值序信息系統(tǒng)(表1)中基于可分辨矩陣的差別信息樹如圖1所示。

Fig.1 Difference information based on discernibility matrix(Table 2)圖1 基于可分辨矩陣（表2）的差別信息

根據(jù)如圖1所示的區(qū)間值序信息系統(tǒng)的基于可分辨矩陣的差別信息樹以及算法2給出求取表1所對應(yīng)的區(qū)間值序信息系統(tǒng)約簡的過程：

（1）創(chuàng)建空集R。

（2）從區(qū)間值序信息系統(tǒng)的基于可分辨矩陣的差別信息樹中選擇僅含單個節(jié)點(diǎn)的路徑＜d＞，將屬性d存放在集合R中，然后刪去樹中有d的所有路徑。

（3）此時選擇差別信息樹的根節(jié)點(diǎn)的最右子節(jié)點(diǎn){b}令R=R?{b}，然后刪去信息樹中含有節(jié)點(diǎn)名為b的全部路徑。

（4）此時差別信息樹只余下一條路徑＜a,c＞，此時選擇差別信息樹的根節(jié)點(diǎn)的子節(jié)點(diǎn){a}，令R=R?{a}，最后輸出R={d,b,a}，算法結(jié)束。于是{d,b,a}就是通過基于可分辨矩陣差別信息樹求得的一個約簡。

5 結(jié)束語

本文提出了區(qū)間值序信息系統(tǒng)的一種新的約簡方法：首先構(gòu)建區(qū)間值序信息系統(tǒng)的基于可分辨矩陣的差別信息樹，然后通過該差別信息樹求取該信息系統(tǒng)的屬性約簡。通過該差別信息樹，實(shí)現(xiàn)了對可分辨矩陣的壓縮儲存，從而縮短了求取區(qū)間值序信息系統(tǒng)屬性約簡的空間復(fù)雜度。但從差別信息樹的構(gòu)建過程可知，往該差別信息樹中插入的可分辨屬性集當(dāng)中的屬性順序是按信息表中屬性的原始順序，沒有考慮屬性重要度對信息樹構(gòu)建的影響。因此接下來的工作可以考慮結(jié)合屬性重要度去實(shí)現(xiàn)對差別信息樹的構(gòu)建，看是否能對可分辨識矩陣進(jìn)一步壓縮儲存。