基于布爾矩陣的決策表屬性約簡算法

袁紅麗，陳志佳

（陸軍工程大學石家莊校區裝備模擬訓練中心，石家莊050003）

0 引言

粗糙集（Rough Sets）是由Pawlak 提出的。該理論作為一個數學工具，可以用來處理不精確的、不一致的、不完整的信息和知識，目前其在機器學習、云計算等領域被廣泛應用。在實際應用中，屬性約簡是粗糙集理論研究的一個重要方向。

利用布爾矩陣的表示方法解決屬性約簡問題，為研究粗糙集理論提出了一個新思路。文獻[2]給出了布爾矩陣如何表示粗糙集理論中概念與運算，證明了布爾矩陣表示的屬性約簡與代數形式表示的屬性約簡是等價的；文獻[3]在文獻[2]基礎上提出了條件區分能力的概念，構造了一個屬性約簡啟發式算法；文獻[4]在研究文獻[3]的基礎上構造了基于核與條件區分能力、加權條件區分能力兩種屬性約簡算法，但是文獻[2-4]均未考慮有決策屬性的情況。文獻[5]給出了決策表信息系統中的粗糙集理論的布爾矩陣表示，證明了相對約簡在布爾矩陣表示形式下與代數表示下是等價的；文獻[6]針對傳統的Skowron 屬性約簡算法的不足之處，提出一種新的基于濃縮布爾矩陣的屬性約簡算法，文中并未提及決策屬性的分類重要性；文獻[10]提出了基于核與改進的條件區分能力的反向刪除屬性約簡算法，但是也未提及決策屬性的分類重要性。

本文針對現有算法中未提及決策屬性的分類重要性情況進行了改進，增加了決策屬性的布爾矩陣，修改了計算相對核、相對約簡的方法，提出了一種基于布爾矩陣的屬性約簡算法。

1 基于布爾矩陣的決策表屬性約簡算法

1.1 算法思想

本算法為了解決文獻[3]、文獻[4]未考慮決策屬性以及基于核與改進的條件區分能力的反向刪除屬性約簡算法中沒有考慮到決策屬性重要性的基礎上，在以下幾個方面做了改進：

（1）增加了決策屬性D 的布爾向量β

決策表信息系統的知識約簡就是指，在保持原始決策表中，條件屬性和決策屬性之間的依賴關系不發生變化的前提下，刪除冗余屬性和屬性值[11]，因此當決策表信息系統的條件屬性部分轉化為布爾矩陣的同時，決策屬性也需要轉化為布爾矩陣。增加決策屬性的布爾向量，b 的計算方法同布爾矩陣的計算方法，某行的值的和若大于等于1，表示(Xk,Xp)屬于同一個pos（d），即：CA中對應的該行中屬性值為1 的屬性的分類能力，對于區分不同的決策屬性起到了至關重要的作用，也就是說該屬性的不同，導致了決策屬性的不同，若為0，則說明該屬性的相同與否都對決策屬性不起作用。

（2）改進了相對核的計算

在本算法計算核的過程是：首先判斷布爾矩陣Mc中有無sum（Mc（i，j））=1 的行，如果有，則判斷向量β中對應行的元素的和是否大于等于1，如果是，則布爾矩陣Mc 中元素1 所在列對應的某個屬性即為相對核的一個屬性，循環判斷布爾矩陣Mc 中的所有行，所有這樣的屬性構成了決策表信息系統的相對核；若沒有這樣的行，則相對核為空。

在本算法中，除了考慮布爾矩陣MC中每行屬性值為1 的個數外，還要考慮向量中該行的值，解決了只考慮布爾矩陣MC中每行屬性值為1 的個數無法求決策表中相對核的問題。

（3）改進了相對約簡的計算

在本算法中，找到核及部分約簡，更新布爾矩陣Mc 時，首先刪除屬性R 對應的列中1 對應的行，其次刪除向量b 中對應的這些行，然后刪除屬性R 所在的列，同時刪除向量b 中值為0 的行和布爾矩陣Mc 中對應的這些行。循環判斷該決策表信息系統中的所有條件屬性，刪除這些冗余信息，對布爾矩陣快速濃縮，考慮了條件屬性與決策屬性的依賴關系的重要性，保證了相對約簡的正確性。

1.2 算法

輸入：決策表信息系統K=(U,C ∪D,V,f)，其中U是論域，C 為條件屬性集，D 為決策屬性集

輸出：決策表信息系統K 的布爾矩陣matrix、及核屬性Core、屬性約簡Red。

Begin

計算pos（C），pos（D），posC（D）

求出C 的布爾矩陣matrix

求出D 的布爾矩陣B

計算matrix 矩陣中每行的和

針對和為1 的行，逐行判斷

If（B 中對應的行是不是1）

如果是，則把matrix 矩陣的該行l 中值為1 所對應的屬性加入到Core 中

再將整個matrix 矩陣中，l 中值為1 的行全部置為0；

End

for jj=1：m將matrix 中所有l 列的值為1 的行刪掉，將l 列也刪掉，更新matrix

End

Red（core，yy，BB，matr）;

End

Red（core，yy，BB，matr）

{

While（matrix 矩陣中如果不是全0）

{

求出matrix 矩陣中各列的和；

找出和值最大的列號n1;

For i=1：m

將整個matrix 矩陣中，n1 列的值為1 所在的行置0；

If（B 中該行的值不為0 且matrix 矩陣中該行的值也不全是0）/*更新matrix 矩陣時，除了要考慮非0 行以外，還要考慮B 矩陣中該行元素的值，若為0 表示該行的屬性對決策表屬性沒有起作用，若為1 表示該分類對決策屬性起作用。*/

將matrix 該行保留；

end

end

}

}

最后將布爾矩陣matrix，及核屬性Core、屬性約簡Red 的結果輸出。

2 仿真實驗

基于布爾矩陣表示的粗集屬性約簡啟發式算法，只是以條件區分能力為啟發信息，并沒有考慮到核信息的作用，經證明其缺乏完備性[4]，在文獻[4]中，作者針對這種情況進行了改進，提出了兩個改進算法：基于核與條件區分能力的屬性約簡算法和基于加權條件區分能力的屬性約簡算法，為敘述方便，下文分別稱這兩種算法為算法1、算法2。

其決策表信息系統如表1 所示，其中條件屬性C={a,b,c,d}，決策屬性D={g}。

表1 決策表

（1）算法1、算法2 進行約簡

使用算法1 進行計算，得到核為：Core={ }a,b,c,d ，更新布爾矩陣matrix 后，matrix 為空，因此得到的約簡為Red={a,b,c,d}；使用算法2 進行計算，matrix 矩陣中，各個屬性的權值和，分別為：27.75，25.25，18.5833，19.4167，選取權值最高的屬性a，加入到Red 中，Red={a}，更新matrix，計算權值和，分別為：9.5，8，8.5，選取權值最高的屬性b，加入到Red 中，Red={a,b}，更新matrix，計算權值和，分別為：3，4，選取權值最高的屬性d，加入到Red 中，Red={a,b,d}，更新matrix，計算權值和，分別為：2，選取權值最高的屬性c，加入到Red中 ，Red={a,b,d,c} ，最 終 得 到 屬 性 約 簡為Red={a,b,c,d}。

（2）使用本文算法進行約簡

首先，計算布爾矩陣MC中每行的和，找到和為1的行，如果向量β 中對應該行的值為1，則將MC該行中1 對應的屬性加入到核中，最后得到核為：Core ={a ,d} ，更新布爾矩陣MC，刪除該屬性對應的列中1 所在的行包括向量β，以及該列；然后計算布爾矩陣MC中每列的和，選取列和最大的屬性加入到約簡中，更新布爾矩陣MC，直至MC為空。最后得到最優約簡為Red={a,b,d}。該算法只能得到最優約簡，不能得到全部約簡。

（3）使用基于Skowron 差別矩陣的決策表屬性約簡算法進行約簡。

首先計算pos（C）={{1}，{2}，{3}，{4}{5}{6}{7}，{8}，{9}，{10}，{11}，{12}，{13}，{14}}，pos（D）={{1，2，6，8，14}，{3，4，5，7，9，10，11，12，13}}，posc（D）={{1}，{2}，{3}，{4}{5}{6}{7}，{8}，{9}，{10}，{11}，{12}，{13}，{14}}，然后計算差別矩陣，搜索差別矩陣，從中找出單屬性元素，并將其賦值給相對核，得到相對核為：Core={a ,d} ，相對約簡為：Red={a ,b,d}，{a,c,d}。

由此可以看出，算法1 和算法2 未考慮決策屬性，所以結果并未體現出條件屬性與決策屬性的依賴關系。本文算法雖然得不到全部約簡，但是能得到最優約簡。歸納如表2。

表2 四種算法約簡結果

3 實驗結果

基于以上的研究，該文選用UCI 機器學習數據庫中的4 個數據庫和表1 在PC（Intel Core i5-5200U CPU@2.2Hz，內存8.00G，64 位）上進行試驗，分別采用算法1、算法2 和該文提出的約簡算法進行屬性約簡，所有算法均在MATLAB 2014b 的基礎上實現。實驗結果如表3。

表3 約簡算法的比較

由表3 可見，本文提出的基于布爾矩陣的屬性約簡算法在4 個數據集上的屬性約簡效果要優于其他算法。

4 結語

本文將條件屬性C 與決策屬性D 的依賴關系與條件區分能力相結合，在構建條件屬性布爾矩陣matrix和決策屬性布爾矩陣β 的基礎上，構造了基于布爾矩陣的決策表屬性約簡算法。實例表明，該算法具備很好的完備性，能夠得到決策表的最優約簡。本文研究的是決策屬性只有一個的情況下，多個決策屬性的研究是下一步的研究方向。