帶權決策表的屬性約簡

李 旭，榮梓景，任 艷

1.新疆財經大學 信息管理學院，烏魯木齊830012

2.北京語言大學 信息科學學院，北京100083

1 引言

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

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

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

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

2 基本概念

為便于進一步對決策表的屬性約簡進行研究，本章將介紹關于決策表的相關概念、正域約簡及其對應的辨識矩陣。

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

文獻[11]給出了基于辨識矩陣計算上近似、下近似約簡的算法，并將其推廣至關系決策表中的上近似、下近似約簡。

引理1[1]設(U,C)是信息系統(tǒng)，若RC是U上的等價關系，對于X?U,有，其中，～X是X的補集。

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

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

定義4設(U,C?D)為決策表，U是論域，C是條件屬性集，D是決策屬性集，RC、RD分別是條件屬性集，決策屬性集確定的U上的等價關系，決策屬性確定的商集為U/D={D1,D2,…,Dl}，正域為POSC(D)=，對于B?C時，若B滿足下列兩條件：

稱B是C關于D的正域約簡[1-2]。

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

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

3 帶權決策表的正域約簡

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

表1 決策表

表2 經過轉化的帶權決策表

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

對于帶權決策表(U,C?D,W)，其正域約簡對應的辨識矩陣為M′=(m′ij)s×n：

定理1設(U,C?D),W為帶權決策表，若?≠B?C時，則下列兩個條件等價：

證明 (7)?(8)，若m′ij≠?，有且( xi,xj)?RD。利用反證法，m′ij?B=?。對于?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≠?，當時，需證。對于任意xj,(xi,xj)?RD,即xj?[]xiD。由條件（8）知m′ij?B≠?，則存在Rl∈m′ij?B使得(xi,xj)?RB，即

推論1設(U,C?D,W)為帶權決策表，當B?C時，B是C關于D的正域約簡當且僅當B為C中滿足m′ij?B≠?的最小子集。

算法1帶權決策表中正域約簡算法

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

輸出：全部約簡。

步驟1計算條件等價類[x]C和決策等價類[x]D。

步驟2計算正域。

步驟3構造辨識矩陣M′。

算法結束。

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

4 帶權決策表的近似分類精度約簡

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

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

引理4設(U,C?D,W)為帶權決策表，當B?C時，對于πD?U/D，的充要條件是

定義5設(U ,C?D,W)為帶權決策表，對于πD?U/D，對于近似分類精度αC，若B?C時，若滿足下列兩條件：

稱B是關于πD的近似分類精度約簡。

定理2設(U,C?D,W)為帶權決策表，當B?C,πD?U/D時，則的充要條件是且

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

其中，n是論域的基。

定理3設(U,C?D,W)為帶權決策表，當B?C時，πD?U/D，則下列兩條件等價：

推論2設(U,C?D,W)為帶權決策表，當B?C時，πD?U/D，B是關于πD的近似分類精度約簡當且僅當B為C中滿足sij?B≠?的最小子集。

算法2帶權決策表的近似分類精度約簡算法

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

輸出：全部約簡。

步驟2構造辨識矩陣S。

算法結束。

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

表3 帶權決策表

5 實驗分析

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

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

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

表5 算法約簡結果對比

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

表6 近似分類精度約簡結果

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

6 結束語

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