基于核與改進的條件區分能力的反向刪除屬性約簡算法

馮衛兵　張　梅

(西安科技大學理學院　陜西 西安 710054)

?

基于核與改進的條件區分能力的反向刪除屬性約簡算法

馮衛兵張梅

(西安科技大學理學院陜西 西安 710054)

摘要粗糙集理論的布爾矩陣表示形式具有直觀、易于理解的優點，它的引入為研究粗糙集的理論提供了一個新的思路。在對布爾矩陣性質研究的基礎上，針對已有的基于布爾矩陣算法沒有考慮到核屬性在濃縮布爾矩陣時的重要性的不足，將屬性重要性與改進的條件區分能力相結合，提出基于核與改進的條件區分能力的屬性約簡算法，借助反向刪除確保約簡集的完備性。實例表明改進后的算法在條件區分能力上更加準確，并且使約簡結果更具有較強的完備性。

關鍵詞布爾矩陣條件區分能力屬性約簡完備算法

0引言

1982年,波蘭科學家Pawlak提出Rough理論[1],它是一種關于數據分析和推理的理論。自粗糙集理論提出以來,屬性約簡一直是粗糙集研究領域的熱點內容之一。國內外學者已經提出了許多算法,典型的有：基于屬性重要度的屬性約簡、基于正區域的屬性約簡[14]、基于信息熵的屬性約簡、基于差別矩陣的屬性約簡算法等[4,5,13,17]。然而,已有的約簡算法在約簡結果精度、效率低和算法完備性等方面還有待進一步改進。

相對于用代數形式表示粗糙集理論的概念與運算,布爾矩陣表示有一定的優勢：第一，直觀性強；第二，使用布爾矩陣的表示更易于理解粗糙集理論的概念與運算的本質。因此，布爾矩陣的引入為研究粗糙集的理論提供了一個新的思路。從上個世紀90年代以來，國內外學者對布爾矩陣表示的屬性約簡問題做了大量的研究，取得了許多成果[6-11,14]。文獻[7]中運用布爾矩陣的方法來表示粗糙集的概念與運算；并在此基礎上證明了屬性約簡在布爾矩陣和代數這兩種不同的表示下是等價的；文獻[6]在此基礎上提出了以屬性的條件區分能力為基礎，構造了一種求屬性約簡的啟發式算法。文獻[3]利用布爾代數通過改進Skowron可辨識矩陣中存在的問題，從而對布爾矩陣進行濃縮。文獻[11]提出一種根據決策表提供的信息來生成布爾可辨矩陣的方法；文獻[12]通過將布爾矩陣的初等行變換把系數矩陣化為最簡矩陣提高約簡效率。

已有的算法均是以d(a,R)作為屬性約簡的啟發式信息，在條件區分能力選擇上比較精確，但是沒有考慮到核屬性對于簡化決策表，刪除布爾矩陣冗余信息的重要性。本文針對已有算法沒有考慮到核屬性在濃縮布爾矩陣時的重要性的不足進行了改進，將屬性重要性與改進的條件區分能力相結合，提出了基于核與改進后條件區分能力的啟發式屬性約簡算法，借助反向刪除確保約簡集的完備性。實例表明改進后的算法在條件區分能力上更加準確，并且使約簡結果更具有較強的完備性。

1基于布爾矩陣的概念和定理

1.1布爾矩陣的構造

定義1[6,7]設S=(U,A,V,f)是一個信息系統。論域U在屬性集A=C∪D={C1,C2,…,Cn}∪g0gggggg下的劃分為X={X1,X2,…,Xm}，針對所有的集對X={Xk,Xp}(1≤k≤p≤m)，給定唯一一個編號i與之對應：

其中，如上述對應方法，(Xk,Xp)對應的是第i個集對，屬性Cj對應的標號為j。

定義2[7,15]設信息系統S=(U,A,V,f)，屬性集R?A，布爾矩陣CA中同時刪除R中的屬性對應的列中值1對應的行和這些列，將剩下的元素重新構造得到的矩陣記為CAR。設d(a,R)表示屬性CAR在條件a下的區分能力, 其值為矩陣CAR中屬性a所對應列的所有元素的和,其中?a∈AR。

1.2布爾矩陣的基本性質

布爾矩陣CA中，列和越大的屬性的區分能力越強并且區分的集對數目也就越多；布爾矩陣行元素和越小，該行中元素值為1對應的屬性在區分對象時就越重要。

命題1[15]設決策表某次約簡集為R，CR為R中的全部屬性對應的布爾矩陣，若去掉屬性a所在的列后其對應的布爾矩陣增加新的零行，則a為必要屬性并且需要保留；否則，a為冗余屬性直接刪除。

證明設CR為約簡屬性R所重新構造的一個布爾矩陣，對于R中任意屬性a，設去掉屬性a的列后的布爾矩陣為CR-{a}。若刪除屬性a所在的列元素而并不增加新的零行(元素全為0的行)，表明CR和CR-{a}的非零行數相同，即a在R中為冗余屬性需要刪除。相反的情況可得，a為必要屬性需要保留，定理得證。

上述定理以及推論的提出主要是為了保證下文屬性約簡集不會存在冗余屬性，從而得到一個屬性約簡的最簡集，保證每一個算法結果的完備性。命題1是通過對屬性集R反向刪除過程，逐步實現最優約簡的目的。

2屬性約簡算法的改進

2.1基于條件區分能力的屬性約簡算法

在布爾矩陣屬性約簡性質的基礎上，提出了基于條件區分能力的屬性約簡算法，其基本思想為：首先，對CAR中的每列求和，記為d(a,R)；其次，對d(a,R)進行大小比較，找出最大的d(a,R)和其對應的屬性a，接著將屬性a所對應的列中值為1的行逐一刪除；并且去掉a所在的列。獲得新矩陣CAR′，判斷CAR′=?是否成立，若成立則算法結束，否則繼續迭代。具體步驟如下：

算法1[16]基于條件區分能力的屬性約簡算法

輸入：S=(U,A,V,f)；

輸出：約簡集R；

Step1由S構造相應的布爾矩陣CA；

Step2初始化R=?，CAR=CA；

Step3

1) 計算CAR中列元素和d(a,R)，選出d(a,R)的最大值對應的屬性a加入屬性集R中，如果有多個屬性同時滿足條件，則任取出一個加入R中，令R=R∪{a}；

2) 在CAR中，同時刪除屬性a所在列中值1對應的行元素和a所在的列元素，更新a；

Step4判斷CAR=?是否成立，若成立，輸出R；否則，轉Step3。

該算法將條件區分能力d(a,R)作為尋找最小屬性約簡的啟發式信息，算法簡單，易于實現。但是在選取最大d(a,R)時具有任意性，會導致其最終約簡結果不準確。接下來對算法1進行改進。

2.2基于改進的條件區分能力的屬性約簡算法

在布爾矩陣的定義中，cij=1是指第i行中出現的1所對應的屬性cj能區分開集對XpXq。設行和為：

S越小，說明越少的屬性就能區分開XpXq；相反，需要更多屬性才能區分開集對XpXq。特別地，如果XpXq對應的行只有cij=1，則說明只有cj才能區分開這兩個對象。基于此分析，針對算法1在選取最大d(a,R)時具有任意性缺點，提出了基于改進的條件區分能力屬性約簡算法，其改進思想為：當同時有多個列和最大時，應該在列和最大的這幾個屬性選取使行和S(pi)最小而且出現頻率最高的屬性。

算法2[16]具體步驟：

輸入：S=(U,A,V,f)，A=C∪D，C∩D=φ，C和D分別為條件屬性集和決策屬性集；

輸出：約簡集R；

Step1由S構造矩陣CA；

Step2初始化R=φ，CAR=CA；

Step3對CAR每一列求和，找出d(a,R)中的最大值，此時，當同時有多個列和最大時，在列和最大的這幾個屬性選取使行和S(pi)最小而且出現頻率最高的屬性加入到約簡集中，即R=R∪{a}；

Step4同時刪除屬性a所在列中值1對應的所有行元素和屬性a所在的列元素，更新矩陣為CAR。

Step5判斷CAR≠?是否成立，若成立，轉Step3；否則，直接輸出約簡集R=R-{a}。

算法通過行和與列和的同時限制d(a,R)，選出其中的必要屬性，從而在條件區分能力選擇上該算法表現更加精確。但是，不足之處是沒有考慮到核屬性在濃縮布爾矩陣時的重要性。接下來對算法2進行改進。

3基于核與改進的條件區分能力的反向刪除屬性約簡算法

命題2[6,7,16]若布爾矩陣中某一行和為1，則1所在的列對應的屬性稱為核屬性；若不存在這樣的行，則核屬性為空。

布爾矩陣可以同時反映出各個屬性對論域的重要性和其中每個屬性對各個集對的分辨情況。在一個確定的布爾矩陣中，元素cij為1(0)意味著第j個屬性可區分開(不可區分開)第i個集對(Xk,Xl)；布爾矩陣行元素中1的數目決定著能把同一集對區分開來的屬性的數目，1的數目越少說明1所對應的屬性越重要。列中1的數目決定著此屬性可區分的集對數，1的數目越多則此屬性區分的能力就越強；

上述算法1和算法2都是以d(a,R)作為屬性約簡的啟發式信息，但是，都并沒有考慮到核屬性對于簡化決策表，刪除布爾矩陣冗余信息的重要性。接下來，針對算法1、2都沒對核屬性進行考慮的不足之處進行改進，提出了一個新的啟發式屬性約簡算法，并對算法的運行結果利用反向刪除確保約簡集的完備性。其實現思想為：首先，刪除布爾矩陣CA有相同對象的行和不相容的行，相同對象的行僅保留一個；接著，尋找核屬性加入到約簡集R中；然后，更新布爾矩陣CAR，進而以改進的條件區分能力為啟發式信息，進行屬性約簡；若布爾矩陣的某一行全為1，直接對其進行刪除，消除冗余信息，對布爾矩陣進行濃縮。最后利用命題1思想，通過對屬性集R反向刪除過程，逐步實現最優約簡的目的。

算法3基于核與改進的條件區分能力的反向刪除屬性約簡算法

輸入：決策系統S=(U,A,V,f)；

輸出：最優約簡集R；

Step1由決策系統S屬性值構造矩陣CA；

Step2令R=?，則CAR=CA；

Step3先求核屬性，即選取行和為1的元素a。令R=R∪{a}，更新對應的CAR；

Step4判斷CAR=?是否成立，若成立，則轉Step9；

Step5對CAR每一列求和，找出區分能力d(a,R)中的最大值，此時，當同時有多個列和最大時，在列和最大的這幾個屬性選取使行和S(pi)最小而且出現頻率最高的屬性加入到約簡集中，即R=R∪{a}；

Step6同時刪除a所在列中值為1對應的所有行和a所在的列，更新得矩陣CAR；

Step7若CAR≠?，轉Step5；反之,轉Step8；

Step8對于初步得到的約簡集R，以其全部屬性構造布爾矩陣，若去掉其中某個屬性所在的列后其對應的布爾矩陣增加新的零行，則該屬性為必要屬性，并且保留該屬性；否則，該屬性為冗余屬性,將其刪除；

Step9輸出約簡集R。

相對于算法1和算法2，改進后的算法通過行和和列和的同時限制找出必要屬性，從而在條件區分能力選擇上更加精確。改進后的算法在算法1和算法2的基礎上考慮了核屬性對約簡的重要性，在約簡的開始先進行核屬性的判斷，并對約簡結果重新構造布爾矩陣，算法中Step8再利用反向刪除法進行冗余性檢查，從而確保了改進后的算法更加準確、有效和完備。

4實例分析

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

表1　決策表

先對表1進行數據預處理，具體為冗余性檢查，如果存在屬性完全相同的對象，對其進行刪除，只保留其中一個，接著matlab程序對冗余性刪除后的決策表進行計算，得到如下的布爾矩陣：

(1) 按算法1進行約簡

先計算CA各列的和分別為d(a,R)=8、d(b,R)=6、d(c,R)=8、d(d,R)=4、d(e,R)=4。接下來按照算法1的步驟選擇一個列和最大的屬性加入到核屬性R中，則約簡R有兩種結果分別為R={a}或者R={c}，然后更新CAR；

若選擇R={a}，重復以上操作，直至CAR=?，則可得到約簡結果R={a,c,e}，R={a,d,e}，R={a,b,e}；若選擇R={c}，重復以上操作，直至CAR=?，則可得到約簡集R={c,b,e}，R={a,c,e}。因此由于第一步的選擇不同將會導致多種結果。

(2) 按照算法2進行約簡

先計算CA各列的和，即d(a,R)=8、d(b,R)=6、d(c,R)=8、d(d,R)=4、d(e,R)=4。可知a和c的列和最大，但行和最小且出現次數最多的屬性為a。此時，更新矩陣CAR；

重復以上操作，直至CAR=?，則可得到約簡結果R={a,c,e}，R={a,b,e}，R={a,d,e}。

(3) 按照改進后的算法(算法3)進行屬性約簡

首先通過選取行和為1的元素求出核屬性e，令R={e}，并更新CAR得到如下：

進而運用算法3中的步驟4、5進行計算，計算得各列的和分別為d(a,R)=5、d(b,R)=4、d(c,R)=5、d(d,R)=3，可知屬性a和c的列和最大，但行和最小且出現次數最多為屬性a，此時，得到新矩陣CAR；

重復以上操作，直至CAR=?，則可得到約簡結果R={a,b,e}，R={a,c,e}，R={a,d,e}。

再根據約簡結果分別重新構造新的布爾矩陣，分別去掉各自屬性后均出現零行，因此，最后得到約簡集為R={a,c,e}，R={a,b,e}，R={a,d,e}。

接下來，將改進后的算法(算法3)與已有算法1、算法2進行對比分析，如表2和表3所示。

表2　三種算法約簡結果

表3　算法對比分析

經過對三種算法的計算結果對比分析可以看出，① 算法1的約簡結果并不是期望結果，算法2和算法3明顯優于算法1；② 算法2和算法3的主要區別在于是否考慮每個屬性對整個論域的重要性，通過核屬性的計算可以初步刪除冗余信息，從而減少論域的數據量，濃縮信息系統的規模。因此在做約簡前，考慮核屬性顯得非常關鍵。另一方面也說明改進后的算法更適合一般信息系統的屬性約簡。③ 在實際問題中，對象個數N相對來說比較大，屬性個數M一般較小，因此盡管改進后的模型在時間復雜度上略有增加，但改進后的算法準確性明顯提高，因此這種改進是值得的。

上面實例中算法2和算法3約簡結果是相同的，然而并不是所有的實例算法2和算法3約簡結果是相同的。接下來再通過一個實例對三種算法進行比較，該信息系統經過matlab計算得到其布爾矩陣為：

分別利用上述三種算法求解如表4所示。

表4　三種算法約簡結果

由約簡結果可知，算法1的約簡結果存在多個并且其中兩個約簡結果存在冗余的屬性。算法2得到的約簡集也存在冗余屬性，其冗余性檢驗可以利用命題1證明。接下來對算法3的約簡結果{a,d}進行分析。首先，利用命題1進行冗余性檢驗，重新構造一個新的布爾矩陣CR如下所示：

可以看出刪除任何一個屬性{a}或者g0gggggg都會出現零行，所以這兩個屬性都是必要屬性必須同時保留；其次，任何一個屬性約簡的算法都期望利用最少的屬性個數來代替原屬性集合對信息系統進行分類。基于上述分析可得出算法3得到的約簡結果{a,d}是本實例期望得到的最優屬性約簡集。

兩個實例均表明，改進后的算法在條件區分能力上更加準確，并且使約簡結果更具有較強的完備性。

5結語

屬性約簡是粗糙集研究核心之一。本文通過將核與條件區分能力相結合，在對布爾矩陣進行濃縮的基礎上，構造了以核和改進的條件區分能力為啟發式信息的屬性約簡算法。另外，為了能找到一個更優或者最優的屬性約簡，在算法中增加了反向刪除過程。實例表明改進后的算法在條件區分能力上更加準確，并且使約簡結果更具有較強的完備性。本文的不足之處是當決策表的規模很大時，其復雜度將會明顯增加，所以下一步，將借助布爾矩陣的性質，比如通過子串、偏序關系等概念對布爾矩陣進行初等行變換、壓縮等[13]，對文中算法繼續進行改進。

參考文獻

[1] Pawlak.Rough Set[J].International Journal of Information and Computer Science,1982,11(5):341-365.

[2] 運士偉,劉慶偉,舒云星.決策表中粗糙集的布爾矩陣表示[J].計算機工程與應用,2007,43(10):177-224.

[3] 殷志偉,張健沛.基于濃縮布爾矩陣的屬性約簡算法[J].哈爾濱工程大學學報,2009,30(3):307-311.

[4] 李秀紅,史開全.一種基于知識粒度的屬性約簡算法[J].計算機應用,2006,33(11):169-170.

[5] 吳強,周文,劉宗田,等.基于粗糙集理論的概念格屬性約簡及算法[J].計算機科學,2006,33(6):179-181.

[6] 李龍星,運士偉,楊炳儒.粗糙集及概念與運算的布爾矩陣表示[J].計算機工程,2005,31(14):16-17.

[7] 李龍星,運士偉,楊炳儒.基于布爾矩陣表示的粗糙集屬性約簡啟發式算法[J].計算機工程,2007,33(10):205-206.

[8] Wong S K,Ziarko W.On optimal decision rules in decision tables[J].Bulletin of polish Academy of Sciences,1985,33(11-12):693-696.

[9] Ziako W.Introduction to the Special Issue on Rough Sets and Knowledge Discovery[J].International Journal of Computational Intelligence,1995,11(2):223-226.

[10] 苗奪謙,胡桂榮.知識約簡的一種啟發式算法[J].計算機研究與發展,1999,36(6):681-684.

[11] 周海巖.采用布爾矩陣不完備信息系統的屬性約簡[J].計算機工程與應用,2010,46(1):119-121.

[12] 王道林.基于布爾矩陣的初等行變換的知識約簡算法[J].計算機應用,2007,27(9):2267-2269.

[13] 高學軍,丁軍.基于簡化差別矩陣的屬性約簡算法[J].系統工程理論與實踐,2006,20(6):101-107.

[14] 劉文軍,谷云東,馮艷賓,等.基于可辨別矩陣和邏輯運算的屬性約簡算法[J].模式識別與人工智能,2004,17(1):119-123.

[15] 高婷,劉文奇.一種基于布爾矩陣的新的屬性約簡完備算法[J].計算機工程與科學,2009,31(8):60-62.

[16] 童新安,運士偉,張永勝.基于布爾矩陣表示的粗糙集屬性約簡算法[J].洛陽理工學院學報:自然科學版,2009,19(1):69-71.

[17] 陳媛,楊棟.基于信息熵的屬性約簡算法及應用[J].重慶理工大學學報:自然科學版,2013,27(1):42-46.

CONVERSE DELETE ATTRIBUTE REDUCTION ALGORITHM BASED ON CORE AND IMPROVED CONDITION DISTINGUISHING ABILITY

Feng WeibingZhang Mei

(CollegeofSciences,Xi’anUniversityofScienceandTechnology,Xi’an710054,Shaanxi,China)

AbstractThe Boolean matrix representation of rough set theory is intuitive and easy to understand, the introduction of it provides a new train of thought for the research of rough set theory. This paper, based on studying some properties of Boolean matrix, and in view of the deficiency of existing Boolean matrix-based algorithm that it does not consider the importance of core attributes in enrichment of Boolean matrix, combines the attribute importance with the improved conditions distinguish ability, and proposes an attribute reduction algorithm which is based on core and improved condition distinguishing ability, thus ensures the completeness of the reduction set with the help of converse deletion. Examples show that the improved algorithm is more accurate in conditions distinguishing ability, and makes the reduction results have stronger completeness.

KeywordsBoolean matrixCondition distinguishing abilityAttribute reductionComplete algorithm

收稿日期：2015-07-13。國家自然科學基金項目(11402194)。馮衛兵，副教授，主研領域：數據知識管理，軟件工程與理論。張梅，碩士生。

中圖分類號TP301.6

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.063