帶權(quán)決策表的屬性約簡

李 旭，榮梓景，任 艷

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

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

1 引言

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

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

帶權(quán)決策表是一種特殊形式的決策表。由論域、條件屬性集、決策屬性集等要素構(gòu)成決策表的基礎(chǔ)上，通過增加一列元素（權(quán)）來形成帶權(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)值，來描述某種機(jī)械故障的樣本數(shù)量。當(dāng)發(fā)生某種機(jī)械故障時(shí)，通過構(gòu)建帶權(quán)決策表可以為專家分析研究問題提供理論依據(jù)。因此，關(guān)于帶權(quán)決策表的屬性約簡在故障診斷、醫(yī)療診斷等領(lǐng)域具有比較重要的現(xiàn)實(shí)意義。

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

2 基本概念

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

在粗糙集模型中，當(dāng)研究對(duì)象是一個(gè)二元信息表，稱其為信息系統(tǒng)。設(shè)(U,C)是信息系統(tǒng)[1]，若B?C，等價(jià)關(guān)系，其中，a(x)表示對(duì)象x在a上的屬性值，稱RB是U上的等價(jià)關(guān)系[1]。若關(guān)系R是U上的等價(jià)關(guān)系時(shí)，R在U上具有自反性，對(duì)稱性和傳遞性。記[x]B是RB在U上的等價(jià)類。若y∈[x]B時(shí)，恒有( x,y)∈RB。若信息系統(tǒng)中屬性集是由條件屬性集C和決策屬性集D構(gòu)成的，稱其為決策表，記為(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ì)算上近似、下近似約簡的算法，并將其推廣至關(guā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的近似分類精度[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滿足下列兩條件：

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

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

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

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

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

表1 決策表

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

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

對(duì)于帶權(quán)決策表(U,C?D,W)，其正域約簡對(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的正域約簡當(dāng)且僅當(dāng)B為C中滿足m′ij?B≠?的最小子集。

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

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

輸出：全部約簡。

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

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

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

算法結(jié)束。

在通常的決策表中，基于辨識(shí)矩陣的正域約簡算法需要消耗大量時(shí)間。但本章將決策表轉(zhuǎn)化為帶權(quán)決策表后，利用對(duì)象權(quán)值比方法，一定程度上優(yōu)化了時(shí)間復(fù)雜度，能夠有效提高約簡的效率。本文將決策表轉(zhuǎn)化為帶權(quán)決策表的過程時(shí)間復(fù)雜度為帶權(quán)決策表中條件類的時(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)決策表的近似分類精度約簡

在帶權(quán)決策表中，近似分類精度概念描述了條件屬性集對(duì)帶權(quán)的對(duì)象分類時(shí)，可能的決策中正確決策的百分比，刻畫為下近似基與上近似基的比值。在帶權(quán)決策表(U ,C?D,W)中，決策屬性確定的商集為U/D=，存在πD?U/D=，需要說明的是π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ì)于近似分類精度αC，若B?C時(shí)，若滿足下列兩條件：

稱B是關(guān)于πD的近似分類精度約簡。

定理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的近似分類精度約簡當(dāng)且僅當(dāng)B為C中滿足sij?B≠?的最小子集。

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

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

輸出：全部約簡。

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

算法結(jié)束。

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

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

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

帶權(quán)決策表中，針對(duì)正域約簡和近似分類精度約簡，本章通過實(shí)驗(yàn)對(duì)提出的算法進(jìn)行了驗(yàn)證?，F(xiàn)從UCI數(shù)據(jù)集中選取Iris，Wine，Statlog（Heart）等3個(gè)數(shù)據(jù)集（表4），來說明算法的有效性和可行性。程序運(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ì)比說明，兩者所得約簡相同，同時(shí)相較于后者，算法1的運(yùn)行效率相對(duì)較高。屬性個(gè)數(shù)是約簡的基，約簡集數(shù)是相同的基下的約簡個(gè)數(shù)。對(duì)于Wine數(shù)據(jù)集（表5），共有78個(gè)約簡，其中，當(dāng)約簡的基等于2時(shí)有47個(gè)約簡，例如{a1,a2}，{a3,a9}。當(dāng)約簡的基等于3時(shí)有31個(gè)約簡，例如{a4,a5,a12}，{a5,a6,a12}。

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

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

表6 近似分類精度約簡結(jié)果

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

6 結(jié)束語

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