李 旭，榮梓景，任 艷

1.新疆財(cái)經(jīng)大學(xué) 信息管理學(xué)院，烏魯木齊830012

2.北京語(yǔ)言大學(xué) 信息科學(xué)學(xué)院，北京100083

1 引言

粗糙集理論是由波蘭學(xué)者Pawlak[1]提出的，是一種處理不確定、不一致和模糊問(wèn)題的數(shù)據(jù)分析工具。近年來(lái)，粗糙集理論的研究成果豐碩，在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、決策支持與分析、醫(yī)療衛(wèi)生服務(wù)、物聯(lián)網(wǎng)等諸多領(lǐng)域中，取得了成功應(yīng)用。屬性約簡(jiǎn)是粗糙集研究的重要內(nèi)容之一，其主要思想就是根據(jù)特定規(guī)則要求，刪除冗余屬性，得到知識(shí)分類(lèi)最小屬性子集。

目前，屬性約簡(jiǎn)已取得了大量的理論研究成果。將決策表和不同應(yīng)用背景相結(jié)合，研究人員提出了正域約簡(jiǎn)[2-3]、變精度約簡(jiǎn)[4-5]、分配約簡(jiǎn)[2，6]、覆蓋約簡(jiǎn)[7-8]、分布約簡(jiǎn)[9]、局部約簡(jiǎn)[10-12]等多種類(lèi)型的約簡(jiǎn)。已有的研究已通過(guò)容差關(guān)系[13]、量化容差關(guān)系[14]、限制容差關(guān)系[15]等拓展了正域約簡(jiǎn)的應(yīng)用范圍。Liu[16]在一致決策表和不一致決策表上提出了一般關(guān)系，從而推廣了二元關(guān)系。文獻(xiàn)[11]在一般關(guān)系下，提出了上下近似的概念，并給出了嚴(yán)格證明。在決策表中，正域約簡(jiǎn)[3]研究已取得重要進(jìn)展?，F(xiàn)階段一般通過(guò)啟發(fā)式約簡(jiǎn)算法[17-19]和基于辨識(shí)矩陣[20-21]的算法等兩種方法進(jìn)行屬性約簡(jiǎn)。雖然啟發(fā)式約簡(jiǎn)算法能夠快速計(jì)算約簡(jiǎn)，但不能得到所有約簡(jiǎn)。基于辨識(shí)矩陣的算法數(shù)學(xué)論證嚴(yán)格，目前仍是得到所有約簡(jiǎn)的最好方法，本文中涉及的約簡(jiǎn)均是通過(guò)辨識(shí)矩陣的方法得到的。近似分類(lèi)精度[2]也稱(chēng)分類(lèi)精度，其表達(dá)了當(dāng)使用條件屬性集對(duì)對(duì)象進(jìn)行分類(lèi)時(shí)，可能的決策中正確決策的百分比。文獻(xiàn)[22]研究了區(qū)分能力和分類(lèi)能力之間的關(guān)系，更細(xì)致地描述了近似分類(lèi)概念。文獻(xiàn)[23]提出了求解近似質(zhì)量屬性約簡(jiǎn)的迭代約簡(jiǎn)算法。文獻(xiàn)[24]以屬性重要度來(lái)刻畫(huà)近似精度差，通過(guò)啟發(fā)式約簡(jiǎn)算法得到近似精度約簡(jiǎn)，然而該方法不能得到所有約簡(jiǎn)。目前，基于辨識(shí)矩陣討論分類(lèi)精度約簡(jiǎn)的研究討論較少。

帶權(quán)決策表是一種特殊形式的決策表。由論域、條件屬性集、決策屬性集等要素構(gòu)成決策表的基礎(chǔ)上，通過(guò)增加一列元素（權(quán)）來(lái)形成帶權(quán)決策表。在不同領(lǐng)域背景下，通常情況下決策表結(jié)構(gòu)不能夠很好地表示實(shí)際情況。例如，在大型機(jī)械設(shè)備故障診斷中，機(jī)械設(shè)備中的各子系統(tǒng)指標(biāo)構(gòu)成條件屬性集，不同的故障結(jié)果構(gòu)成決策屬性集。當(dāng)發(fā)生某種機(jī)械故障時(shí)，把各子系統(tǒng)中指標(biāo)參數(shù)出現(xiàn)的相同頻次作為權(quán)值，來(lái)描述某種機(jī)械故障的樣本數(shù)量。當(dāng)發(fā)生某種機(jī)械故障時(shí)，通過(guò)構(gòu)建帶權(quán)決策表可以為專(zhuān)家分析研究問(wèn)題提供理論依據(jù)。因此，關(guān)于帶權(quán)決策表的屬性約簡(jiǎn)在故障診斷、醫(yī)療診斷等領(lǐng)域具有比較重要的現(xiàn)實(shí)意義。

基于上述分析，關(guān)于帶權(quán)決策表的屬性約簡(jiǎn)研究討論相對(duì)較少。因此，本文提出了在帶權(quán)決策表中，通過(guò)計(jì)算對(duì)象權(quán)值比的方法得到正域，從而進(jìn)行正域約簡(jiǎn)，該算法的時(shí)間復(fù)雜度優(yōu)于文獻(xiàn)[3]給出的正域約簡(jiǎn)算法的時(shí)間復(fù)雜度。同時(shí)，本文提出了近似分類(lèi)精度約簡(jiǎn)的算法，并進(jìn)行了嚴(yán)格的理論證明。

2 基本概念

為便于進(jìn)一步對(duì)決策表的屬性約簡(jiǎn)進(jìn)行研究，本章將介紹關(guān)于決策表的相關(guān)概念、正域約簡(jiǎn)及其對(duì)應(yīng)的辨識(shí)矩陣。

在粗糙集模型中，當(dāng)研究對(duì)象是一個(gè)二元信息表，稱(chēng)其為信息系統(tǒng)。設(shè)(U,C)是信息系統(tǒng)[1]，若B?C，等價(jià)關(guān)系，其中，a(x)表示對(duì)象x在a上的屬性值，稱(chēng)RB是U上的等價(jià)關(guān)系[1]。若關(guān)系R是U上的等價(jià)關(guān)系時(shí)，R在U上具有自反性，對(duì)稱(chēng)性和傳遞性。記[x]B是RB在U上的等價(jià)類(lèi)。若y∈[x]B時(shí)，恒有( x,y)∈RB。若信息系統(tǒng)中屬性集是由條件屬性集C和決策屬性集D構(gòu)成的，稱(chēng)其為決策表，記為(U,C?D)。定義1[1-2]設(shè)(U,C)是信息系統(tǒng)，其中U是論域，RC是由屬性集C決定在U上的等價(jià)關(guān)系，若?≠X?U時(shí)，關(guān)于X的上近似，下近似分別為：

文獻(xiàn)[11]給出了基于辨識(shí)矩陣計(jì)算上近似、下近似約簡(jiǎn)的算法，并將其推廣至關(guān)系決策表中的上近似、下近似約簡(jiǎn)。

引理1[1]設(shè)(U,C)是信息系統(tǒng)，若RC是U上的等價(jià)關(guān)系，對(duì)于X?U,有，其中，～X是X的補(bǔ)集。

定義2設(shè)(U ,C)是信息系統(tǒng)，對(duì)于任意X?U，若B?C時(shí)，X關(guān)于B的正域、邊界域[11]分別為：

定義3設(shè)(U,C)是信息系統(tǒng)，對(duì)于?≠X?U，若B?C時(shí)，X關(guān)于屬性集B的近似分類(lèi)精度[2]為：，其中，||?表示集合的基。

定義4設(shè)(U,C?D)為決策表，U是論域，C是條件屬性集，D是決策屬性集，RC、RD分別是條件屬性集，決策屬性集確定的U上的等價(jià)關(guān)系，決策屬性確定的商集為U/D={D1,D2,…,Dl}，正域?yàn)镻OSC(D)=，對(duì)于B?C時(shí)，若B滿(mǎn)足下列兩條件：

稱(chēng)B是C關(guān)于D的正域約簡(jiǎn)[1-2]。

正域約簡(jiǎn)相應(yīng)的辨識(shí)矩陣[3]為M=( mij)s×n：

在辨識(shí)矩陣M中，s= |POSC(D )|是正域的基，n= ||U是論域中對(duì)象數(shù)。

3 帶權(quán)決策表的正域約簡(jiǎn)

帶權(quán)決策表是一種決策表的形式變形。把決策表中的每行均作為一條決策規(guī)則時(shí)，將出現(xiàn)相同決策規(guī)則的次數(shù)稱(chēng)為權(quán)，因而可知本文定義的權(quán)值均為正整數(shù)?？紤]用權(quán)來(lái)表示決策規(guī)則在決策表中重復(fù)出現(xiàn)的次數(shù)，每條決策規(guī)則僅出現(xiàn)1次時(shí)，稱(chēng)決策表為帶權(quán)決策表，記為(U ,C?D,W)。其中，U是論域，C是條件屬性集，D是決策屬性集，W為對(duì)象的權(quán)，RC、RD分別是條件屬性，決策屬性確定的U上的等價(jià)關(guān)系。現(xiàn)通過(guò)表1和表2來(lái)說(shuō)明決策表到帶權(quán)決策表的構(gòu)建過(guò)程。決策表(U,C?D)（表1），論域U={ui|i=1,2,…,6}，條件屬性集C={a1,a2,a3}，決策屬性集D=syggg00。

表1 決策表

表2 經(jīng)過(guò)轉(zhuǎn)化的帶權(quán)決策表

由帶權(quán)決策表可知，若等價(jià)類(lèi)[x]C中的決策規(guī)則一致時(shí)，即，則等價(jià)類(lèi)[x]C必包含于正域。若等價(jià)類(lèi)[x]C中的決策規(guī)則不一致，即時(shí)，則等價(jià)類(lèi)[]xC任意對(duì)象必不屬于正域。

對(duì)于帶權(quán)決策表(U,C?D,W)，其正域約簡(jiǎn)對(duì)應(yīng)的辨識(shí)矩陣為M′=(m′ij)s×n：

定理1設(shè)(U,C?D),W為帶權(quán)決策表，若?≠B?C時(shí)，則下列兩個(gè)條件等價(jià)：

證明 (7)?(8)，若m′ij≠?，有且( xi,xj)?RD。利用反證法，m′ij?B=?。對(duì)于?a∈B,( xi,xj)∈RB。由條件（7）知：

因而與( xi,xj)?RD矛盾，得證。

(8)?(7)，因B?C，有POSB(D)?POSC(D)?，F(xiàn)證POSC(D)?POSB(D )。由引理知m′ij≠?，當(dāng)時(shí)，需證。對(duì)于任意xj,(xi,xj)?RD,即xj?[]xiD。由條件（8）知m′ij?B≠?，則存在Rl∈m′ij?B使得(xi,xj)?RB，即

推論1設(shè)(U,C?D,W)為帶權(quán)決策表，當(dāng)B?C時(shí)，B是C關(guān)于D的正域約簡(jiǎn)當(dāng)且僅當(dāng)B為C中滿(mǎn)足m′ij?B≠?的最小子集。

算法1帶權(quán)決策表中正域約簡(jiǎn)算法

輸入：帶權(quán)決策表(U ,C?D,W)。

輸出：全部約簡(jiǎn)。

步驟1計(jì)算條件等價(jià)類(lèi)[x]C和決策等價(jià)類(lèi)[x]D。

步驟2計(jì)算正域。

步驟3構(gòu)造辨識(shí)矩陣M′。

算法結(jié)束。

在通常的決策表中，基于辨識(shí)矩陣的正域約簡(jiǎn)算法需要消耗大量時(shí)間。但本章將決策表轉(zhuǎn)化為帶權(quán)決策表后，利用對(duì)象權(quán)值比方法，一定程度上優(yōu)化了時(shí)間復(fù)雜度，能夠有效提高約簡(jiǎn)的效率。本文將決策表轉(zhuǎn)化為帶權(quán)決策表的過(guò)程時(shí)間復(fù)雜度為帶權(quán)決策表中條件類(lèi)的時(shí)間復(fù)雜度為O(| C|× |U′|)。算法1在計(jì)算正域時(shí)，其時(shí)間復(fù)雜度為O(| U′|× |U′/C |)，而文獻(xiàn)[3]中計(jì)算正域的時(shí)間復(fù)雜度為O(| U|2)，因，因此，算法1的時(shí)間復(fù)雜度優(yōu)于原有算法的時(shí)間復(fù)雜度。

4 帶權(quán)決策表的近似分類(lèi)精度約簡(jiǎn)

在帶權(quán)決策表中，近似分類(lèi)精度概念描述了條件屬性集對(duì)帶權(quán)的對(duì)象分類(lèi)時(shí)，可能的決策中正確決策的百分比，刻畫(huà)為下近似基與上近似基的比值。在帶權(quán)決策表(U ,C?D,W)中，決策屬性確定的商集為U/D=，存在πD?U/D=，需要說(shuō)明的是πD至少包含一個(gè)Di(i=1,2,…,l)。

證明 利用反證法，若E＞G或F＜H時(shí)，由條件知F≤H,E≥G，則不成立。因而E=G且F=H成立。

引理4設(shè)(U,C?D,W)為帶權(quán)決策表，當(dāng)B?C時(shí)，對(duì)于πD?U/D，的充要條件是

定義5設(shè)(U ,C?D,W)為帶權(quán)決策表，對(duì)于πD?U/D，對(duì)于近似分類(lèi)精度αC，若B?C時(shí)，若滿(mǎn)足下列兩條件：

稱(chēng)B是關(guān)于πD的近似分類(lèi)精度約簡(jiǎn)。

定理2設(shè)(U,C?D,W)為帶權(quán)決策表，當(dāng)B?C,πD?U/D時(shí)，則的充要條件是且

現(xiàn)定義辨識(shí)矩陣S=(sij)n×n如下：

其中，n是論域的基。

定理3設(shè)(U,C?D,W)為帶權(quán)決策表，當(dāng)B?C時(shí)，πD?U/D，則下列兩條件等價(jià)：

推論2設(shè)(U,C?D,W)為帶權(quán)決策表，當(dāng)B?C時(shí)，πD?U/D，B是關(guān)于πD的近似分類(lèi)精度約簡(jiǎn)當(dāng)且僅當(dāng)B為C中滿(mǎn)足sij?B≠?的最小子集。

算法2帶權(quán)決策表的近似分類(lèi)精度約簡(jiǎn)算法

輸入：帶權(quán)決策表(U ,C?D,W)。

輸出：全部約簡(jiǎn)。

步驟2構(gòu)造辨識(shí)矩陣S。

算法結(jié)束。

由該辨識(shí)矩陣得辨識(shí)函數(shù)為f=(a2)( a1+a3)，得析取范式為f=( a1a2)+( a2a3)，得約簡(jiǎn)為{a1a2}和{a2a3}。

表3 帶權(quán)決策表

5 實(shí)驗(yàn)分析

帶權(quán)決策表中，針對(duì)正域約簡(jiǎn)和近似分類(lèi)精度約簡(jiǎn)，本章通過(guò)實(shí)驗(yàn)對(duì)提出的算法進(jìn)行了驗(yàn)證?，F(xiàn)從UCI數(shù)據(jù)集中選取Iris，Wine，Statlog（Heart）等3個(gè)數(shù)據(jù)集（表4），來(lái)說(shuō)明算法的有效性和可行性。程序運(yùn)行環(huán)境：Intel?CoreTMi5-2440 CPU 3.10 GHz，Windows10 64 bit，算法為Python代碼實(shí)現(xiàn)。

表4 數(shù)據(jù)集的有關(guān)信息

表5中，算法1和文獻(xiàn)[3]中提出的算法（記為GPAR算法）對(duì)比說(shuō)明，兩者所得約簡(jiǎn)相同，同時(shí)相較于后者，算法1的運(yùn)行效率相對(duì)較高。屬性個(gè)數(shù)是約簡(jiǎn)的基，約簡(jiǎn)集數(shù)是相同的基下的約簡(jiǎn)個(gè)數(shù)。對(duì)于Wine數(shù)據(jù)集（表5），共有78個(gè)約簡(jiǎn)，其中，當(dāng)約簡(jiǎn)的基等于2時(shí)有47個(gè)約簡(jiǎn)，例如{a1,a2}，{a3,a9}。當(dāng)約簡(jiǎn)的基等于3時(shí)有31個(gè)約簡(jiǎn)，例如{a4,a5,a12}，{a5,a6,a12}。

表5 算法約簡(jiǎn)結(jié)果對(duì)比

在選取3個(gè)數(shù)據(jù)集上，根據(jù)算法2得到帶權(quán)決策表的近似分類(lèi)精度約簡(jiǎn)結(jié)果如表6所示，其中，πD是決策屬性集在論域上確定的商集U/D的子集。在Iris數(shù)據(jù)集中，D1為屬性值為“Setosa”確定的等價(jià)類(lèi)，D2為屬性值為“Versicolour”確定的等價(jià)類(lèi)；在Wine數(shù)據(jù)集中，D1為屬性值為“1”確定的等價(jià)類(lèi)，D2為屬性值為“2”確定的等價(jià)類(lèi)；在Statlog（Heart）數(shù)據(jù)集中，D1為屬性值為“1”確定的等價(jià)類(lèi)，D2為屬性值為“2”確定的等價(jià)類(lèi)。

表6 近似分類(lèi)精度約簡(jiǎn)結(jié)果

表6中，對(duì)于Iris數(shù)據(jù)集，取πD=D1時(shí)，有3個(gè)約簡(jiǎn)，其中當(dāng)約簡(jiǎn)的基為3時(shí)，有1個(gè)約簡(jiǎn){a1,a2,a3}，當(dāng)約簡(jiǎn)的基為2時(shí)，有2個(gè)約簡(jiǎn)。取πD=D1?D2時(shí)，有5個(gè)約簡(jiǎn)，且5個(gè)約簡(jiǎn)的基均為2。通過(guò)實(shí)驗(yàn)進(jìn)一步說(shuō)明了本文提出的算法1和算法2具有可行性。

6 結(jié)束語(yǔ)

關(guān)于決策表中的約簡(jiǎn)研究取得了廣泛的研究成果。在通常的決策表中，可通過(guò)GPAR算法得到正域的全部約簡(jiǎn)。本文將決策表轉(zhuǎn)化為帶權(quán)決策表后，通過(guò)算法1進(jìn)行正域約簡(jiǎn)時(shí)發(fā)現(xiàn)，算法1的運(yùn)行時(shí)間優(yōu)于GPAR算法。同時(shí)，本文提出了一種關(guān)于近似分類(lèi)精度約簡(jiǎn)算法，并給出了證明。最后通過(guò)實(shí)驗(yàn)說(shuō)明本文提出算法的可行性和有效性。之后的工作中，通過(guò)帶權(quán)決策表模型，來(lái)解決更多類(lèi)型的約簡(jiǎn)問(wèn)題，例如將等價(jià)關(guān)系推廣至一般關(guān)系（即不要求關(guān)系滿(mǎn)足自反性、對(duì)稱(chēng)性、傳遞性）。