屬性重要性的啟發(fā)式屬性約簡算法

何 英，何 丹

HE Ying1，HE Dan2

（1.南昌航空大學(xué) 現(xiàn)代教育技術(shù)中心，南昌 330063；2.南昌航空大學(xué) 信息中心，南昌 330063）

0 引言

Rough集理論自80年代初由波蘭學(xué)者Z.Pawlak提出以來，是一種迅速發(fā)展的既有理論又有應(yīng)用的研究領(lǐng)域[1]。粗糙集理論[2,3]是Pawlak 等人提出的一種處理不精確、不完全信息的新型數(shù)學(xué)工具。由于二進制的可實現(xiàn)性，很多學(xué)者將其引入屬性約簡算法中，文獻[5,6]用二進制可辨矩陣設(shè)計了基于正域的屬性約簡算法，但都沒有解決當(dāng)二進制可辨矩陣列的屬性頻率出現(xiàn)次數(shù)相同的情況下選取加入到約簡中的順序問題。本文在文獻[5-7]的基礎(chǔ)上，提出了以屬性頻率和屬性關(guān)于U/D正域之和為啟發(fā)式信息的二進制可辨識矩陣列的屬性約簡算法，解決了當(dāng)二進制可辨識矩陣列的屬性頻率相同的情況下的屬性選取問題。

1 屬性約簡基本概念

定義1 一個信息系統(tǒng)S，表示為S=（U,A,V,f），其中U={X1,X2,…,Xn}是論域；A是屬性集合；V=∪va，a∈A，va表示屬性的值域；f=U×A→V是一個信息函數(shù)，對x∈U，a∈A，有f（x,a）∈va。若A可分為條件屬性集C和決策屬性集D，即A =C∪D，C∩D=φ，則該信息系統(tǒng)稱為決策表。

定義2 設(shè)R是一個等價關(guān)系族，r∈R，如果IND（R）=IND（R-{r}），則稱r在R中是可被約去的知識；如果P=R-{r}是獨立的，則P是R中的一個約簡。

定義3 在信息系統(tǒng)S中,若P,Q∈A，則Q的P正域POSP（Q）定義為：

其中P_X為X的P下近似。Q的P正域是U中所有根據(jù)分類U/P的信息可以準確地劃分到關(guān)系Q的等價類中去的對象集合。

2 二進制可辨矩陣[8]

定義4 設(shè)決策表為T=（U,C,D,V,f），其中U={u1,u2,…,un}，C={c1,c2,…,cm}，D=j5i0abt0b則決策表T相應(yīng)的二進制可辨矩陣MT構(gòu)造為：矩陣的每一列對應(yīng)一個條件屬性，共有m列，每一行對應(yīng)一對論域中的對象（up,uq），有n（n-1）/2行。設(shè)矩陣中一元素m（（p,q）,i）所在行對應(yīng)的應(yīng)對象對（up,uq），所在列對應(yīng)條件屬ci，則

這樣得到的一個矩陣，稱之為相應(yīng)于決策表T=（U,C,D,V,f）的二進制可辨矩陣。

命題1 若二進制可辨矩陣中某一行只有一個元素為1其余元素均為0，則元素1所在列對應(yīng)某個屬性，所有這樣的屬性構(gòu)成信息系統(tǒng)的核或決策表的相對核。若沒有這樣的行，則核或相對核為空。

3 屬性重要性的度量方法

對于決策表T=（U,C,D,V,f）：用P（ci）（ci∈C,1≤i≤|C|）表示ci在二進制可辨識矩陣中的屬性頻率；用MAX（P（c））表示二進制可辨識矩陣中屬性c出現(xiàn)的最大頻率；用NMAX表示二進制可辨識矩陣中屬性出現(xiàn)的頻率等于最大頻率的屬性總數(shù)，NMAX=|{ci|P（ci）=MAX（P（c））,1≤i≤|C|}|；條件屬性ci∈C（1≤i≤|C|）的重要性可以用ci的屬性頻率P（ci）和U/{ci}關(guān)于U/D正域POSU/{ci}（U/D）來度量，用Gci表示，則Gci可通過公式1給出，如下所示。

4 屬性重要性的啟發(fā)式屬性約簡算法

在二進制可辨矩陣中，對于那些只有一個元素為1其余元素均為0的行，元素1所在列的屬性一定屬于核，而對于那些有多個元素為1的行，在這些元素為1所在的列中，那些所含1的個數(shù)最多的列對應(yīng)的屬性雖未必是核屬性，但具有很強的分辨能力，因此這樣的屬性在形成約簡，尤其是最小約簡的過程中具有重要地位。

算法 二進制可辨矩陣屬性重要性的啟發(fā)式屬性約簡。

輸入：決策表T=（U,C,D,V,f）

輸出：決策表T屬性約簡

1）根據(jù)給定的決策表T=（U,C,D,V,f）產(chǎn)生二進制可辨矩陣M，將M中全為1和0的行刪除，得到新的Mnew。置矩陣MA←Mnew，用Reduction表示屬性約簡，初始值為Reduction=φ。

2）對每一行，若該行只有一個元素為1，則將該元素所對應(yīng)的屬性為核屬性，并將該屬性加入到Reduction，即Reduction←Reduction∪{ci}，其中ci∈C,1≤i≤|C|。

3）從MA中刪除各行只有一個元素為1的行及該行元素1所對應(yīng)的列值為1的行，將得到的新矩陣MAnew再賦給MA。如果MA=φ，則轉(zhuǎn)到7），否則到4）。

4）將MA的各列縱向相加，并將結(jié)果存入相應(yīng)col[ci]中，其中ci∈C,1≤i≤|C|。

5）用一維數(shù)組G[|C|]表示屬性的重要性，初始值為G[ci]=0，其中ci∈C,1≤i≤|C|。根據(jù)公式1計算屬性重要性；在MA中將屬性重要性最大的屬性ci列及ci列上值為1的元素所對應(yīng)的行去掉；將得到的新矩陣再賦給MA，并將Reduction←Reduction∪{ci}。

6）將MA中行全為1和0的行刪除，將得到的新矩陣再賦給MA。如果MA≠φ，則轉(zhuǎn)到4）。

4）輸出一個約簡Reduction。

5 實例分析

表1中C={a,b,c,d}為條件屬性，D={e}為決策屬性，A=C∪D，對表1建立二進制可辨矩陣如表2所示。

表1 決策表T=（U,C,D,V,f）

表2 決策表T的二進制可辨矩陣

將表2中去掉（1,7）、（2,4）及（5,6）三行，并將屬性c中為1的行去掉，得表3。

表3 化簡后的二進制可辨矩陣

表3中a,b,d各列的屬性頻率都為6，根據(jù)公式（1）計算屬性的重要性，計算過程如下：

U/{e}={Y1,Y2,Y3} ,Y1=（1,3,6,7）,Y2=（2,5）,Y3=（4）；U/{a}={X1a,X2a},X1a=（1,3,7）,X2a=（2,4,5,6）

U/={X1b，X2b},X1b=（1,5,6,7）,X2b=（2,3,4）；U/j5i0abt0b={X1d,X2d},X1d=（1,2,4,5,7）,X2d=（3,6）

由以上公式可得：G[a]=1+3/4=1.75,G[b]=1+0= 1,G[d]=1+2/4=1.5?？芍猘的屬性的重要性最大，即Reduction={a,c}。將表3中a列及a列值為1的行去掉，再將行都為1的行刪除，得到的表為空，因此Reduction={a,c}為最后這個決策表的約簡集。

6 復(fù)雜度分析

設(shè)決策表中有m個條件屬性，n個對象，在最壞情況下，構(gòu)造二進制可辨矩陣需要比較mn（n-1）/2次，復(fù)雜度為O（mn2）；根據(jù)文獻[9]的計算正域的方法，計算正域的最大的時間復(fù)雜度為O（（|C | + 1）| U |log | U |）= O（mnlogn），而計算MAX（P（ci））的最大的時間復(fù)雜度為O（n2）,所以算法第7步的時間復(fù)雜度為MAX（O（（mnlogn）,O（n2））。因此本算法的時間復(fù)雜度為O（mn2）。

通過上述分析，可見本算法在文獻[5-7]的基礎(chǔ)上，并解決了當(dāng)二進制可辨識矩陣列的屬性頻率相同的情況下的屬性選取問題。當(dāng)決策表的復(fù)雜程度較高時，它使得求解的復(fù)雜程度大大降低，是一種獲得屬性約簡的簡單而有效的方法。

[1]劉清.Rough集及Rough推理[M].第一版.北京：科學(xué)出版社,2001.

[2]Pawlak Z.Rough sets and intelligent data analysis[J].Information Sciences：2002,147：1-12.

[3]Pawlak Z,Skowron A.Rough sets：Some extensions[J].Infor mation Sciences：2007,177：41-73.

[4]支天云,苗奪謙.二進制可辨別矩陣的變換及高效屬性約簡算法的構(gòu)造[J].計算機科學(xué)：2002,29（2）：140-142.

[5]錢文彬,徐章艷,黃麗宇等.基于信息熵的二進制差別矩陣屬性約簡算法[J].計算機工程與應(yīng)用：2010,46（6）：120-123.

[6]任小康等.基于可辮識矩陣的屬性頻率約簡算法[J].蘭州大學(xué)學(xué)報：2003,43（1）：138-140.

[7]Felix R,Ushio T.Rough Sets-based Machine Learning Using a Binary Discernibility Matrix.IPMM99 published：1999：299-305.

[8]劉少輝,盛秋戩,吳斌,等.Rough集高效算法研究[J].計算機學(xué)報：2003,26（5）：524-529.