黃麗萍

(閩南師范大學 計算機學院，福建 漳州 363000；數(shù)據(jù)科學與智能應用福建省高等學校重點實驗室，福建 漳州 363000；福建省粒計算及其應用重點實驗室，福建 漳州 363000)

0 引言

粗糙集理論自提出后就被廣泛地應用，進行了多方面的研究．其中屬性約簡是粗糙集理論研究的主要內容．在對約簡的研究中，利用二進制求約簡是一個重要分支．二進制辨識矩陣是對skowron辨識矩陣[1]的改進，采用二進制表示形式，使計算更加簡單直觀．因此，采用二進制辨識矩陣進行屬性約簡具有一定的意義.

Hu等人在1995年提出了基于skowron矩陣的核屬性求解算法[2]．Felix等人[3]在1999年提出了只由0和1構成的二進制可辨識矩陣．文獻[4]利用Felix提出的二進制可辨識矩陣計算核屬性并得出相應的屬性約簡方法．文獻[4，5]指出Felix沒有考慮決策表的不一致性，給出了二進制分辨矩陣的新定義和求解核屬性的方法，并驗證了該方法的正確性．王錫懷等[6]利用二進制差別矩陣構造了適用于一致和不一致決策表的廣義信息表，提出了一種啟發(fā)式算法，該算法可以計算各個屬性的重要性，但沒有對不兼容的情況進行考慮．文獻[7，8]分別從上近似和下近似對二進制可辨矩陣進行定義，利用這兩個矩陣可以得到屬性核和約簡結果．文獻給出了一種廣義二進制辨識矩陣用于處理不完備信息系統(tǒng)的約簡．二進制辨識矩陣從最初的分別只對辨識矩陣的行或列[10]方向考慮并度量屬性重要度，到現(xiàn)在同時從行和列兩個角度對屬性重要度進行判斷[11，12]．

為了更加方便、直觀地得到屬性約簡，本文對二進制辨識矩陣的求解算法進行改進，首先運用文獻[12]的方法得到簡化的二進制辨識矩陣；然后在文獻[11，12]的基礎上給出一種新的二進制辨識矩陣約簡算法，算法同時從二進制辨識矩陣行和列的角度對屬性的重要度進行度量，在獲取約簡屬性的同時對二進制辨識矩陣已經(jīng)能被區(qū)分的對象進行刪減，從而有效地提高算法效率，并得到最小屬性約簡.文獻[13，14]利用布爾矩陣求取了決策信息系統(tǒng)屬性核、絕對不必要屬性和相對必要屬性.本文從二進制辨識矩陣的角度在求取約簡的同時，求出當約簡集中含有某一屬性后，對決策表的對象沒有進一步的區(qū)分能力的相對不必要屬性和絕對不必要屬性，并通過實例和實驗來說明算法是正確的和有效的．

1 理論基礎

定義2[14]給定S=〈U，C∪D，V，f〉和P?C∪D，P在U上的不可辨識關系定義為：

IND(P)={(x，y)|(x，y)∈U×U∧(?b∈P，b(x)=b(y))}．

定義3[12]設決策表S=〈U，C∪D，V，f〉，其中U={u1，u2，…，un}，C={c1，c2，…，cn}，D=syggg00，則決策表S的二進制分別矩陣BM=(BM(i，j，ck))l，其中l(wèi)≤n(n-1)/2×m．

其中BM((i，j)，ck)表示若兩個樣本的決策屬性的值不同，決策表的第i和第j個對象是否能夠通過第k個條件屬性區(qū)分出，若能區(qū)分則BM(i，j，ck)=1，否則BM(i，j，ck)=0．

2 約簡算法

本節(jié)主要給出一種基于二進制矩陣的屬性約簡和不必要屬性的求解算法方法．先把決策信息系統(tǒng)轉換為二進制辨識矩陣; 然后通過行和列中1的個數(shù)對屬性重要性進行判定; 最后根據(jù)所得的屬性重要性進行約簡屬性的選擇，得到?jīng)Q策信息系統(tǒng)的屬性約簡．通過判斷是否存在某列的取值全0來獲取絕對不必要屬性或相對不必要屬性．

定理1[12]S=〈U，C∪D，V，f〉為一致的決策表，BMn×m為S的二進制辨識矩陣，若存在唯一的屬性k∈{1，2，…，m}，使得BM(i，j，ck)=1，而對于?a∈{1，2，…，k-1，k+1，…，m}，均有BM(i，j，ca)=0，則k所在的列為S的核屬性．

對于屬性k∈{1，2，…，m}，使得BM(i，j，ck)=1，而對于?a∈{1，2，…，k-1，k+1，…，m}，均有BM(i，j，ca)=0，則刪除k列中屬性值為1的行，表示這些對象已經(jīng)可以通過屬性k區(qū)分開來，不需要進一步地區(qū)分．

定理2S=〈U，C∪D，V，f〉為一致的決策表，BMn×m為S的二進制辨識矩陣，若ck所在的列，對于?i∈{1，2，…，n}和?j∈{1，2，…，m}均有BM(i，j，ck)=0，則ck為不必要屬性．

若ck所在的列，對于?i∈{1，2，…，n}和?j∈{1，2，…，m}均有BM(i，j，ck)=0，表示該ck不能進一步辨識任何對象，ck為相對不必要屬性．相對于前面獲取的約簡屬性而言ck為不必要屬性，若獲取的約簡屬性為核，則ck為絕對不必要屬性.

針對文獻[11，12]中算法的不足，給出改進的BIRD算法：

輸入：決策信息系統(tǒng)S=〈U，C∪D，V，f〉；

輸出：C相對于D的一個約簡Red和不必要屬性集Noneed;

步驟1：構造簡化二進制辨識矩陣BM.

步驟2：初始化屬性約簡Red=?.

步驟3：計算BM中每一行元素的和，若存在和為1的行，則選擇這些行中1對應的屬性k，加入到約簡集中，Red={k}．若不存在和為1的值，則選擇Rmin對應屬性中max(C(c))的列k為約簡集Red={k}．

步驟4：刪除k中屬性列值為1的行獲得刪減后的二進制矩陣BM′，計算BM′的每一列的和，若存在和為0 的列w，則Noneed={w}．

步驟5：重復步驟3和4直到BM′中所有的屬性列的和為0或步驟4中無可刪除行．

3 實例分析

給定決策信息表S=〈U，C∪D，V，f〉如表1[14]所示，其中論域U={x1，x2，x3，x4}，條件屬性C={a1，a2，a3，a4}，決策屬性D=syggg00．

表1 決策信息表

S的二進制辨識矩陣如表2所示.計算各行的和為3，3，2，3，1根據(jù)定理1，可得該決策信息表的核為core={a3}．刪除屬性列a3為1的行，即這些對象在a3的取值為1，表示這些對象能由a3區(qū)分，可以刪除這些對象.從而得到約簡后的表，如表3所示.

表2 二進制辨識矩陣

從表3可以看出a4的取值為0，它不能進一步區(qū)分余下的對象.a4為不必要屬性，因為其對于核屬性是不必要的，所以為絕對不必要屬性.在其余的對象中a1或a2都可以區(qū)分它們，所以該決策表的約簡為Red1={a3，a1}和Red2={a3，a2}同文獻[15]．

表3 刪除a3取值為1的行后的矩陣

給定決策信息表S=〈U，C∪D，V，f〉如表4[13]所示，其中論域U={x1，x2，x3，x4，x5，x6}，條件屬性C={a1，a2，a3，a4，a5，a6}，決策屬性D=syggg00．

表4 決策信息表

S的二進制辨識矩陣如表5所示.

表5 二進制辨識矩陣

該決策表無核屬性，計算各行的和為2，4，4，2，3，5，6，5選取Rmin=2的行，分別為第1和第4行．選擇Rmin的值為最小的行，表示這些對象用了最少的必要屬性來區(qū)分，這些屬性是必要屬性.第1行中值為1的屬性列中1的和分別為f(a2)=6，f(a6)=6；第4行中值為1的屬性列中1的和分別為f(a2)=4，f(a6)=5．選取屬性max(C(c))=a2為約簡的屬性，選擇1中最少的行后接下來選擇列中1最多的個數(shù)表示其能區(qū)分的對象越多，屬性越重要．從而選擇約簡屬性Red={a2}．

刪除a2中屬性值為1的行得到如表6所示.

同理可得：表6中各行的和為4，2選取Rmin=2的行，第2行．計算該行中屬性列為1的和為f(a3)=2，f(a4)=1，選取屬性max(C(c))=a3為約簡的屬性．Red={a2，a3}．因a3列中沒有屬性值為0的行，所以算法結束．Red={a2，a3}．本文算法的約簡個數(shù)同文獻[13]，為最小約簡.

表6 刪除a6取值為1的行后的矩陣

4 實驗仿真測試及結果分析

為了進一步驗證BIRD算法，本文從UCI(University of California Irvine)中選取了5個數(shù)據(jù)集，各數(shù)據(jù)集的描述如表7所示.

表7 數(shù)據(jù)集信息

本文算法BRID、文獻[13]算法1，2和文獻[14]的算法3約簡結果如表8所示.

表8 約簡結果

其中約簡長度是用使用 RSES2粗糙集軟件計算出來的結果5～7表示約簡結果的屬性個數(shù)范圍為5～7，33表示有33個約簡集．從表8可以看出，BIRD在屬性約簡(表8中的Red)個數(shù)上取得了較好的結果，可得最小約簡，而文獻[12]中給出的方法在Zoo，Spectf，Spect和lymn上沒有得到最小約簡，是由于算法1，2只從列的角度來度量屬性的重要度.

用Zoo數(shù)據(jù)集合來說明本文的BRID算法對不必要屬性(表8中的Noneed)求解的正確性．求得的約簡過程如下：求得核屬性為6，13后，去掉核屬性中為1的行后，屬性列為0 的屬性列為2，5，15，即2，5，15為絕對不必要屬性；REST的約簡結果集是從下標0開始的從圖1可以看出屬性2，5，15，即a1，a4，a14不在Zoo的約簡集中，為絕對不必要屬性，與本文的算法一致．繼續(xù)添加約簡屬性為3，該屬性沒有相對不必要屬性，可以從表10可以看出a2可以和其他屬性構成屬性約簡，添加屬性8后，該屬性的相對不必要屬性為7，從圖2可以看出所有的約簡集合包含a7的屬性就沒有a6，也與本文的算法一致．

使用REST軟件對Zoo約簡得到相應的結果如下圖1，2所示：

綜上所述，本文算法在不需要求取全體約簡集的情況下可以獲得最小約簡集、絕對不必要屬性或相對不必要屬性.

5 結束語

本文給出了一種新的決策信息系統(tǒng)屬性約簡的二進制辨識矩陣方法，該方法根據(jù)屬性對對象的區(qū)分度作為重要性進行屬性選擇，獲取決策信息系統(tǒng)的約簡屬性．實驗表明該約簡集是最小約簡集．并在求取約簡集的同時，根據(jù)二進制辨識矩陣對對象的區(qū)分特性進一步求取決策信息系統(tǒng)的絕對不必要屬性或相對不必要屬性．