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

袁紅麗，陳志佳

（陸軍工程大學(xué)石家莊校區(qū)裝備模擬訓(xùn)練中心，石家莊050003）

0 引言

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

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

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

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

1.1 算法思想

本算法為了解決文獻(xiàn)[3]、文獻(xiàn)[4]未考慮決策屬性以及基于核與改進(jìn)的條件區(qū)分能力的反向刪除屬性約簡算法中沒有考慮到?jīng)Q策屬性重要性的基礎(chǔ)上，在以下幾個(gè)方面做了改進(jìn)：

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

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

（2）改進(jìn)了相對核的計(jì)算

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

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

（3）改進(jìn)了相對約簡的計(jì)算

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

1.2 算法

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

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

Begin

計(jì)算pos（C），pos（D），posC（D）

求出C 的布爾矩陣matrix

求出D 的布爾矩陣B

計(jì)算matrix 矩陣中每行的和

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

If（B 中對應(yīng)的行是不是1）

如果是，則把matrix 矩陣的該行l(wèi) 中值為1 所對應(yīng)的屬性加入到Core 中

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

End

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

End

Red（core，yy，BB，matr）;

End

Red（core，yy，BB，matr）

{

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

{

求出matrix 矩陣中各列的和；

找出和值最大的列號n1;

For i=1：m

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

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

將matrix 該行保留；

end

end

}

}

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

2 仿真實(shí)驗(yàn)

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

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

表1 決策表

（1）算法1、算法2 進(jìn)行約簡

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

（2）使用本文算法進(jìn)行約簡

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

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

首先計(jì)算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}}，然后計(jì)算差別矩陣，搜索差別矩陣，從中找出單屬性元素，并將其賦值給相對核，得到相對核為：Core={a ,d} ，相對約簡為：Red={a ,b,d}，{a,c,d}。

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

表2 四種算法約簡結(jié)果

3 實(shí)驗(yàn)結(jié)果

基于以上的研究，該文選用UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的4 個(gè)數(shù)據(jù)庫和表1 在PC（Intel Core i5-5200U CPU@2.2Hz，內(nèi)存8.00G，64 位）上進(jìn)行試驗(yàn)，分別采用算法1、算法2 和該文提出的約簡算法進(jìn)行屬性約簡，所有算法均在MATLAB 2014b 的基礎(chǔ)上實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果如表3。

表3 約簡算法的比較

由表3 可見，本文提出的基于布爾矩陣的屬性約簡算法在4 個(gè)數(shù)據(jù)集上的屬性約簡效果要優(yōu)于其他算法。

4 結(jié)語

本文將條件屬性C 與決策屬性D 的依賴關(guān)系與條件區(qū)分能力相結(jié)合，在構(gòu)建條件屬性布爾矩陣matrix和決策屬性布爾矩陣β 的基礎(chǔ)上，構(gòu)造了基于布爾矩陣的決策表屬性約簡算法。實(shí)例表明，該算法具備很好的完備性，能夠得到?jīng)Q策表的最優(yōu)約簡。本文研究的是決策屬性只有一個(gè)的情況下，多個(gè)決策屬性的研究是下一步的研究方向。