屬性重要性的啟發式屬性約簡算法

何 英，何 丹

HE Ying1，HE Dan2

（1.南昌航空大學 現代教育技術中心，南昌 330063；2.南昌航空大學 信息中心，南昌 330063）

0 引言

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

1 屬性約簡基本概念

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

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

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

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

2 二進制可辨矩陣[8]

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

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

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

3 屬性重要性的度量方法

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

4 屬性重要性的啟發式屬性約簡算法

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

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

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

輸出：決策表T屬性約簡

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

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

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

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

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

6）將MA中行全為1和0的行刪除，將得到的新矩陣再賦給MA。如果MA≠φ，則轉到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，根據公式（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/{b}={X1b，X2b},X1b=（1,5,6,7）,X2b=（2,3,4）；U/g0gggggg={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。可知a的屬性的重要性最大，即Reduction={a,c}。將表3中a列及a列值為1的行去掉，再將行都為1的行刪除，得到的表為空，因此Reduction={a,c}為最后這個決策表的約簡集。

6 復雜度分析

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

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

[1]劉清.Rough集及Rough推理[M].第一版.北京：科學出版社,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]支天云,苗奪謙.二進制可辨別矩陣的變換及高效屬性約簡算法的構造[J].計算機科學：2002,29（2）：140-142.

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

[6]任小康等.基于可辮識矩陣的屬性頻率約簡算法[J].蘭州大學學報：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].計算機學報：2003,26（5）：524-529.