二進(jìn)制辨識(shí)矩陣的屬性約簡(jiǎn)及不必要屬性的求解

黃麗萍

(閩南師范大學(xué) 計(jì)算機(jī)學(xué)院，福建 漳州 363000；數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，福建 漳州 363000；福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室，福建 漳州 363000)

0 引言

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

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

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

1 理論基礎(chǔ)

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

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

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

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

2 約簡(jiǎn)算法

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

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

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

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

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

針對(duì)文獻(xiàn)[11，12]中算法的不足，給出改進(jìn)的BIRD算法：

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

輸出：C相對(duì)于D的一個(gè)約簡(jiǎn)Red和不必要屬性集Noneed;

步驟1：構(gòu)造簡(jiǎn)化二進(jìn)制辨識(shí)矩陣BM.

步驟2：初始化屬性約簡(jiǎn)Red=?.

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

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

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

3 實(shí)例分析

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

表1 決策信息表

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

表2 二進(jìn)制辨識(shí)矩陣

從表3可以看出a4的取值為0，它不能進(jìn)一步區(qū)分余下的對(duì)象.a4為不必要屬性，因?yàn)槠鋵?duì)于核屬性是不必要的，所以為絕對(duì)不必要屬性.在其余的對(duì)象中a1或a2都可以區(qū)分它們，所以該決策表的約簡(jiǎn)為Red1={a3，a1}和Red2={a3，a2}同文獻(xiàn)[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=j5i0abt0b．

表4 決策信息表

S的二進(jìn)制辨識(shí)矩陣如表5所示.

表5 二進(jìn)制辨識(shí)矩陣

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

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

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

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

4 實(shí)驗(yàn)仿真測(cè)試及結(jié)果分析

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

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

本文算法BRID、文獻(xiàn)[13]算法1，2和文獻(xiàn)[14]的算法3約簡(jiǎn)結(jié)果如表8所示.

表8 約簡(jiǎn)結(jié)果

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

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

使用REST軟件對(duì)Zoo約簡(jiǎn)得到相應(yīng)的結(jié)果如下圖1，2所示：

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

5 結(jié)束語(yǔ)

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