馮衛(wèi)兵　張　梅

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

?

基于核與改進(jìn)的條件區(qū)分能力的反向刪除屬性約簡(jiǎn)算法

馮衛(wèi)兵張梅

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

摘要粗糙集理論的布爾矩陣表示形式具有直觀、易于理解的優(yōu)點(diǎn)，它的引入為研究粗糙集的理論提供了一個(gè)新的思路。在對(duì)布爾矩陣性質(zhì)研究的基礎(chǔ)上，針對(duì)已有的基于布爾矩陣算法沒(méi)有考慮到核屬性在濃縮布爾矩陣時(shí)的重要性的不足，將屬性重要性與改進(jìn)的條件區(qū)分能力相結(jié)合，提出基于核與改進(jìn)的條件區(qū)分能力的屬性約簡(jiǎn)算法，借助反向刪除確保約簡(jiǎn)集的完備性。實(shí)例表明改進(jìn)后的算法在條件區(qū)分能力上更加準(zhǔn)確，并且使約簡(jiǎn)結(jié)果更具有較強(qiáng)的完備性。

關(guān)鍵詞布爾矩陣條件區(qū)分能力屬性約簡(jiǎn)完備算法

0引言

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

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

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

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

1.1布爾矩陣的構(gòu)造

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

其中，如上述對(duì)應(yīng)方法，(Xk,Xp)對(duì)應(yīng)的是第i個(gè)集對(duì)，屬性Cj對(duì)應(yīng)的標(biāo)號(hào)為j。

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

1.2布爾矩陣的基本性質(zhì)

布爾矩陣CA中，列和越大的屬性的區(qū)分能力越強(qiáng)并且區(qū)分的集對(duì)數(shù)目也就越多；布爾矩陣行元素和越小，該行中元素值為1對(duì)應(yīng)的屬性在區(qū)分對(duì)象時(shí)就越重要。

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

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

上述定理以及推論的提出主要是為了保證下文屬性約簡(jiǎn)集不會(huì)存在冗余屬性，從而得到一個(gè)屬性約簡(jiǎn)的最簡(jiǎn)集，保證每一個(gè)算法結(jié)果的完備性。命題1是通過(guò)對(duì)屬性集R反向刪除過(guò)程，逐步實(shí)現(xiàn)最優(yōu)約簡(jiǎn)的目的。

2屬性約簡(jiǎn)算法的改進(jìn)

2.1基于條件區(qū)分能力的屬性約簡(jiǎn)算法

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

算法1[16]基于條件區(qū)分能力的屬性約簡(jiǎn)算法

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

輸出：約簡(jiǎn)集R；

Step1由S構(gòu)造相應(yīng)的布爾矩陣CA；

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

Step3

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

2) 在CAR中，同時(shí)刪除屬性a所在列中值1對(duì)應(yīng)的行元素和a所在的列元素，更新a；

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

該算法將條件區(qū)分能力d(a,R)作為尋找最小屬性約簡(jiǎn)的啟發(fā)式信息，算法簡(jiǎn)單，易于實(shí)現(xiàn)。但是在選取最大d(a,R)時(shí)具有任意性，會(huì)導(dǎo)致其最終約簡(jiǎn)結(jié)果不準(zhǔn)確。接下來(lái)對(duì)算法1進(jìn)行改進(jìn)。

2.2基于改進(jìn)的條件區(qū)分能力的屬性約簡(jiǎn)算法

在布爾矩陣的定義中，cij=1是指第i行中出現(xiàn)的1所對(duì)應(yīng)的屬性cj能區(qū)分開(kāi)集對(duì)XpXq。設(shè)行和為：

S越小，說(shuō)明越少的屬性就能區(qū)分開(kāi)XpXq；相反，需要更多屬性才能區(qū)分開(kāi)集對(duì)XpXq。特別地，如果XpXq對(duì)應(yīng)的行只有cij=1，則說(shuō)明只有cj才能區(qū)分開(kāi)這兩個(gè)對(duì)象?；诖朔治觯槍?duì)算法1在選取最大d(a,R)時(shí)具有任意性缺點(diǎn)，提出了基于改進(jìn)的條件區(qū)分能力屬性約簡(jiǎn)算法，其改進(jìn)思想為：當(dāng)同時(shí)有多個(gè)列和最大時(shí)，應(yīng)該在列和最大的這幾個(gè)屬性選取使行和S(pi)最小而且出現(xiàn)頻率最高的屬性。

算法2[16]具體步驟：

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

輸出：約簡(jiǎn)集R；

Step1由S構(gòu)造矩陣CA；

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

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

Step4同時(shí)刪除屬性a所在列中值1對(duì)應(yīng)的所有行元素和屬性a所在的列元素，更新矩陣為CAR。

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

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

3基于核與改進(jìn)的條件區(qū)分能力的反向刪除屬性約簡(jiǎn)算法

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

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

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

算法3基于核與改進(jìn)的條件區(qū)分能力的反向刪除屬性約簡(jiǎn)算法

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

輸出：最優(yōu)約簡(jiǎn)集R；

Step1由決策系統(tǒng)S屬性值構(gòu)造矩陣CA；

Step2令R=?，則CAR=CA；

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

Step4判斷CAR=?是否成立，若成立，則轉(zhuǎn)Step9；

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

Step6同時(shí)刪除a所在列中值為1對(duì)應(yīng)的所有行和a所在的列，更新得矩陣CAR；

Step7若CAR≠?，轉(zhuǎn)Step5；反之,轉(zhuǎn)Step8；

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

Step9輸出約簡(jiǎn)集R。

相對(duì)于算法1和算法2，改進(jìn)后的算法通過(guò)行和和列和的同時(shí)限制找出必要屬性，從而在條件區(qū)分能力選擇上更加精確。改進(jìn)后的算法在算法1和算法2的基礎(chǔ)上考慮了核屬性對(duì)約簡(jiǎn)的重要性，在約簡(jiǎn)的開(kāi)始先進(jìn)行核屬性的判斷，并對(duì)約簡(jiǎn)結(jié)果重新構(gòu)造布爾矩陣，算法中Step8再利用反向刪除法進(jìn)行冗余性檢查，從而確保了改進(jìn)后的算法更加準(zhǔn)確、有效和完備。

4實(shí)例分析

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

表1　決策表

先對(duì)表1進(jìn)行數(shù)據(jù)預(yù)處理，具體為冗余性檢查，如果存在屬性完全相同的對(duì)象，對(duì)其進(jìn)行刪除，只保留其中一個(gè)，接著matlab程序?qū)θ哂嘈詣h除后的決策表進(jìn)行計(jì)算，得到如下的布爾矩陣：

(1) 按算法1進(jìn)行約簡(jiǎn)

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

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

(2) 按照算法2進(jìn)行約簡(jiǎn)

先計(jì)算CA各列的和，即d(a,R)=8、d(b,R)=6、d(c,R)=8、d(d,R)=4、d(e,R)=4?？芍猘和c的列和最大，但行和最小且出現(xiàn)次數(shù)最多的屬性為a。此時(shí)，更新矩陣CAR；

重復(fù)以上操作，直至CAR=?，則可得到約簡(jiǎn)結(jié)果R={a,c,e}，R={a,b,e}，R={a,d,e}。

(3) 按照改進(jìn)后的算法(算法3)進(jìn)行屬性約簡(jiǎn)

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

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

重復(fù)以上操作，直至CAR=?，則可得到約簡(jiǎn)結(jié)果R={a,b,e}，R={a,c,e}，R={a,d,e}。

再根據(jù)約簡(jiǎn)結(jié)果分別重新構(gòu)造新的布爾矩陣，分別去掉各自屬性后均出現(xiàn)零行，因此，最后得到約簡(jiǎn)集為R={a,c,e}，R={a,b,e}，R={a,d,e}。

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

表2　三種算法約簡(jiǎn)結(jié)果

表3　算法對(duì)比分析

經(jīng)過(guò)對(duì)三種算法的計(jì)算結(jié)果對(duì)比分析可以看出，① 算法1的約簡(jiǎn)結(jié)果并不是期望結(jié)果，算法2和算法3明顯優(yōu)于算法1；② 算法2和算法3的主要區(qū)別在于是否考慮每個(gè)屬性對(duì)整個(gè)論域的重要性，通過(guò)核屬性的計(jì)算可以初步刪除冗余信息，從而減少論域的數(shù)據(jù)量，濃縮信息系統(tǒng)的規(guī)模。因此在做約簡(jiǎn)前，考慮核屬性顯得非常關(guān)鍵。另一方面也說(shuō)明改進(jìn)后的算法更適合一般信息系統(tǒng)的屬性約簡(jiǎn)。③ 在實(shí)際問(wèn)題中，對(duì)象個(gè)數(shù)N相對(duì)來(lái)說(shuō)比較大，屬性個(gè)數(shù)M一般較小，因此盡管改進(jìn)后的模型在時(shí)間復(fù)雜度上略有增加，但改進(jìn)后的算法準(zhǔn)確性明顯提高，因此這種改進(jìn)是值得的。

上面實(shí)例中算法2和算法3約簡(jiǎn)結(jié)果是相同的，然而并不是所有的實(shí)例算法2和算法3約簡(jiǎn)結(jié)果是相同的。接下來(lái)再通過(guò)一個(gè)實(shí)例對(duì)三種算法進(jìn)行比較，該信息系統(tǒng)經(jīng)過(guò)matlab計(jì)算得到其布爾矩陣為：

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

表4　三種算法約簡(jiǎn)結(jié)果

由約簡(jiǎn)結(jié)果可知，算法1的約簡(jiǎn)結(jié)果存在多個(gè)并且其中兩個(gè)約簡(jiǎn)結(jié)果存在冗余的屬性。算法2得到的約簡(jiǎn)集也存在冗余屬性，其冗余性檢驗(yàn)可以利用命題1證明。接下來(lái)對(duì)算法3的約簡(jiǎn)結(jié)果{a,d}進(jìn)行分析。首先，利用命題1進(jìn)行冗余性檢驗(yàn)，重新構(gòu)造一個(gè)新的布爾矩陣CR如下所示：

可以看出刪除任何一個(gè)屬性{a}或者vh5tlb3都會(huì)出現(xiàn)零行，所以這兩個(gè)屬性都是必要屬性必須同時(shí)保留；其次，任何一個(gè)屬性約簡(jiǎn)的算法都期望利用最少的屬性個(gè)數(shù)來(lái)代替原屬性集合對(duì)信息系統(tǒng)進(jìn)行分類?；谏鲜龇治隹傻贸鏊惴?得到的約簡(jiǎn)結(jié)果{a,d}是本實(shí)例期望得到的最優(yōu)屬性約簡(jiǎn)集。

兩個(gè)實(shí)例均表明，改進(jìn)后的算法在條件區(qū)分能力上更加準(zhǔn)確，并且使約簡(jiǎn)結(jié)果更具有較強(qiáng)的完備性。

5結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

[4] 李秀紅,史開(kāi)全.一種基于知識(shí)粒度的屬性約簡(jiǎn)算法[J].計(jì)算機(jī)應(yīng)用,2006,33(11):169-170.

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

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

[7] 李龍星,運(yùn)士偉,楊炳儒.基于布爾矩陣表示的粗糙集屬性約簡(jiǎn)啟發(fā)式算法[J].計(jì)算機(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] 苗奪謙,胡桂榮.知識(shí)約簡(jiǎn)的一種啟發(fā)式算法[J].計(jì)算機(jī)研究與發(fā)展,1999,36(6):681-684.

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

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

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

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

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

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

[17] 陳媛,楊棟.基于信息熵的屬性約簡(jiǎn)算法及應(yīng)用[J].重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版,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。國(guó)家自然科學(xué)基金項(xiàng)目(11402194)。馮衛(wèi)兵，副教授，主研領(lǐng)域：數(shù)據(jù)知識(shí)管理，軟件工程與理論。張梅，碩士生。

中圖分類號(hào)TP301.6

文獻(xiàn)標(biāo)識(shí)碼A

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