摘 要 屬性約簡是粗糙集理論中核心內容之一，本文首先分析了區分矩陣的特性，給出經典的區分矩陣算法。然後，鑑於區分矩陣存在的空間複雜度高的缺點，提出一種基於區分鏈表的屬性約簡改進算法，將對象數爲n的區分矩陣大小由n(n-1)/2至少壓縮到|U/R|*（|U/R|-1）/2，降低了算法的空間複雜度，更適用於大數據量的情況。
關鍵詞 粗糙集；區分矩陣；屬性約簡；區分線性表
1 引言
粗糙集(Rough Set ,RS) 理論是 ak 提出的一種處理不一致、不完整數據和不精確知識表達等各種不完備資訊的數學理論[1] 。其中屬性約簡是粗糙集理論中核心內容之一，現已證明是典型的NP難題[2，3]。所謂屬性約簡是指在保證資訊系統分類能力或決策能力不變的條件下，刪除屬性集中的冗餘屬性。屬性約簡在分類學習及分類數據挖掘中具有重要的作用，目前國內外學術界在屬性約簡方面已經做了大量研究，並得到了許多有效的算法[4~6]。[4] 深入分析了算法低效性的根源,給出了高效的約簡算法；文獻[5]給出了基於資訊論的方法；文獻[6]利用正區域的啓發式資訊給出了兩種屬性相對約簡算法；其中應用較多的是基於華沙大學數學家Skowron提出差別矩陣[7]以及在此基礎上的一些改進[9~11]，由於這種基於區分矩陣方法易於解釋和核屬性,同時也便於約簡，該方法爲屬性約簡算法提供了一種很好的思路。然而，基於區分矩陣的屬性約簡算法對對象數爲n的區分矩陣大小爲n(n-1)/2，不適用於大數據量的情況，所以本文給出了一種改進算法，將空間複雜度至少壓縮到|U/R|*（|U/R|-1）/2，該算法大大降低了算法的空間複雜度，適用於大數據量的情況。
2 基本概念
定義1[2]：設U爲一個有限的非空論域，R爲U上的等價關係。等價關係R 把集合U 劃分爲多個互不相交的子集，每一個子集稱爲一個等價類，用[x]R表示，[x]R={y∈U| xRy}，其中x∈U，x∈y稱爲關於R 的等價關係，論域U上的所有等價類的集合用U/ R來表示。 定義2[2]：令R爲一族等價關係，r R,如果 IND(R)= IND(R-{r}),則稱r爲R中不必要的；否則r爲R中必要的[2]，若R中任意一個等價關係r都是必要的，則稱R是獨立的，否則稱R是依賴的。 定義3[8]：設 ，若Q是獨立的，且IND(Q)=IND(P)，則Q是等價關係族P的一個約簡。 定義4[8]：設P和Q是論域U上的等價關係，Q的P正域記作POSP(Q)，定義爲： Q的P正域是U中所有根據U/P的資訊準確分類到關係Q的等價關係中去的對象構成的集合。 定義5[8]：設P和Q是論域U上的等價關係，R∈P，若 POSP(Q) =POS(P-{R})(Q) 則稱R爲P中Q不必要的，否則稱R爲P中Q必要的。 若P中任意一關係R都是Q必要的，則稱P是Q獨立的(相對於Q獨立的)。 定義6[2]：設 SP，S爲P的Q約簡，當且僅當S是P的Q是獨立的子集，且POSS(Q) =POSP(Q). P的Q約簡稱爲相對約簡。 定義7：區分矩陣是華沙大學數學家Skowron[7]提出的，對於系統S=(U,A),其中A=C∪D, a(x)是x在屬性a上的值,區分矩陣M爲：
同時分辨矩陣中的核就是組合數爲1的'屬性。
3 基於區分鏈表的屬性約簡改進算法
區分矩陣的空間複雜度爲n(n-1)/2,儲存着論域中兩兩對象的可區分屬性.在論域關於屬性集劃分中，同一個等價類的對象兩兩在區分矩陣中的元素爲空，而且與其他等價類的對象所構成的區分矩陣中的元素完全相同，因此從每一個等價類中只取一個對象構造的新的論域，其約簡與原來的相同,而空間複雜度最多爲|U/R|*（|U/R|-1）/2. 區分矩陣Matrix的某元素Matrix[i][j]，是區分對象U[i]與U[j]的條件屬性集，由於在合取吸取運算中，參數i、j並沒有實際價值，因此改用區分鏈表List來取代區分矩陣。在構造區分鏈表前，先定義存儲核屬性的變量core，可區分兩對象的條件屬性集若只有一個屬性Ri，則屬性Ri是核屬性，那麼Ri存儲到變量core，在接下來的區分鏈表的構造過程中，若區分屬性集包括已經提取出來的核屬性，直接約去，不插入到區分鏈表中；否則，插入到區分鏈表的表尾。爲減少區分鏈表的大小，可以在每產生一個核屬性Rj，進入變量core後，化簡區分鏈表List，若List中的元素List[k]包含屬性Rj則直接刪除元素List[k]。對應算法如下： for(p=U;p->next !=NULL;p=p->next) for(q=p->next;q!=NULL;q=q->next) { x= 對象p、q的可區分屬性集； if（|x|==1） 則x進入核變量core； else if（x不包含核變量core中已有的任何一個核屬性） (x); } 在得到了核和區分鏈表後，首先，將核加入到候選約簡中；然後，統計區分鏈表中各屬性出現的次數，將出現次數最多的屬性R加入到侯選約簡中，刪除區分鏈表中出現R的所有節點，依次循環，直到區分鏈表爲空，此時侯選約簡就是所求約簡。對應算法如下： C_reduce=core; While(1) { if(List=Null) break; else { 遍歷List,統計各條件屬性出現的次數； 選擇出現次數最多的那個屬性R； C_reduce=C_reduce {R}; 刪除List中所有出現R的的節點； } }
4 實例分析
設如下表1[12]給定的決策表，求所有約簡及核。 而應用本文給出的算法,區分線性表只有{b,c}一個元素,過程如下:首先得到區分屬性集{a}，a進入核變量，在隨後生成的區分屬性集中只要含有a，則直接約掉，{b,c}進入區分線性表，採用啓發式算法，可得到約簡{a,b}。而基於區分矩陣的屬性約簡算法構造的區分矩陣如下：
本算法相對於傳統方法，大大減少了區分矩陣所需要的存儲空間。
5 結論
近年來Rough 集理論以其獨特的優勢正贏得越來越多的專家學者關注,在理論研究方面日趨成熟,並在許多領域取得了較爲成功的應用，屬性約簡算法是粗糙集理論的核心內容之一，其中，區分矩陣作爲屬性約簡的主要方法之一已經受到越來越多的學者關注，因此，本文深入研究分析了區分矩陣算法，基於區分線性表，提出一種改進的屬性約簡算法。
[1] Pawlak Z. Rough Sets(J). International Journal of Computer and Information Science, 1982, 11(5): 341-356 [2] 張文修,吳偉志. 粗糙集理論介紹和研究綜述[J ] . 模糊系統與數學,2000 ,15 (4) :1-12 [3] 王國胤. Rough 集理論與知識獲取[M] . 西安:西安大學出版社,2001 [4] 劉少輝. Rough集高效算法的研究. 計算機學報(J), 2003,26(5):524-529 [5] 王國胤, 於 洪, 楊大春. 基於條件資訊熵的決策表約簡(J) . 計算機學報 ,2002, 25( 7 ): 759-766 [6] 張騰飛, 肖健梅, 王錫淮. 粗糙集理論中屬性相對約簡算法. 學報(J) ,2005, 33(11):2080-2083 [7] Skowron A. Rauszer C. The Discerni-bility Matrics and Functions in Information System(J), Intelligent Decision Support Handbook of Applications and Advances of the Rough Sets Theory Dordrecht: Kluwer Academic Publishers, 1992: 331-362 [8] 李雄飛, 李君. 數據挖掘與知識發現[M]. 高等出版社,2003 [9] 範 敏,劉文奇.基於粗集可辨識矩陣的屬性約簡算法[J ].計算機工程與應用,2004 ,38 (13) :79 - 80 [10] WANGJue ,WANGJu. Reduction Algorithm Based on Disernibility Matrix: The Ordered Attributes Method [ J ] . J . Comput . Sci . &Technol ,2001 ,16 (6) :489 - 504 [11] 王兵,陳善本.一種基於差別矩陣的屬性約簡完備算法[J ].上海交通大學學報,2004,38(1):43- 46