一種改進的基于差別矩陣的求核屬性算法

陸 光，李 想

(東北林業大學 信息與計算機工程學院，哈爾濱 150040)

粗糙集是一個強大的數據分析工具，能表達和處理不完備信息，目前已被廣泛應用于數據挖掘和智能決策等各個領域[1]，其表現為能提高對不完整數據進行分析和學習的能力。求核、屬性約簡、規則提取都是粗糙集理論中非常重要的研究課題。眾所周知，通過屬性約簡刪除冗余屬性，可以提高系統潛在知識的清晰度。由文獻[2-3]可知，最常見的約簡模型有：基于正域的屬性約簡模型[4]，基于條件屬性熵的屬性約簡模型[5]，基于skowron的差別矩陣的屬性約簡模型[6]，基于分配的屬性約簡模型[7]，以及基于近似的屬性約簡模型[8]等。對于大多數約簡模型，其算法一般要先求出其核，然后再根據核，通過啟發式知識加入其它屬性，擴展到最小約簡。基于skowron的差別矩陣是一種非常經典的的求核方法，很多學者通過改進其方法，使其得到的結果最優，其中，Hu提出將改進的skowron的差別矩陣方法應用在決策表的屬性約簡中，得到基于差別矩陣的Hu屬性約簡[6]。現有研究結果表明基于正區域的屬性約簡模型的核，基于Skowron差別矩陣的屬性約簡的核和基于信息熵的求核模型得到的結果是不完全等價的[3，9]，因此，改進Hu差別矩陣方法是當前研究的熱點[10]，張振林等提出了改進的差別矩陣方法，大大減少了數據存儲空間。本文基于張振林等的改進的差別矩陣方法基礎上提出分決策屬性“D集”的求核方法。

1 粗糙集理論基本知識

有關粗糙集的相關基礎知識請參考文獻[4，11]，不同書籍或文獻對粗糙集的概念描述有所不同，如粗糙集方法是一種能有效地分析和處理不精確、不一致、不完整等各種不確定性信息的數據分析工具；粗糙集的研究對象是由一個多值屬性(特征、癥狀、特性等)集合描述的一個對象(觀察、病例等)集合[12]；粗糙集理論的觀點是，“知識(人的智能)就是一種對對象進行分類的能力”[13]。粗糙集理論對事物的表述不需要任何假設的先驗知識，只依賴于給定的知識表達系統。知識約簡在智能信息或數據的處理中占有十分重要的地位，也是粗糙集理論的核心內容之一。知識表達系統中有一種叫決策系統，也稱決策表，即含有決策屬性的知識表達系統。

定義1[13]設在決策表S=(U，C，D，V，f)中，記U={x1,x2,…,xn}，為對象的非空有限集合，稱為論域；C={α|α∈C}稱為條件屬性集，每個αj∈C(1≤∈j≤m)稱為C的一個簡單屬性；D={d|d∈D}稱為決策屬性集，且C∩D=?，C=?，D=?；V=UVα(?α∈C∪D)是信息函數f的值域，而Vα表示值域；f={fα：U→Vα,α∈C∪D}表示決策表的信息函數，fα為屬性α的信息函數。

定義2[13]決策表S=(U,C,D,V,f)，?α∈C∪和?x∈U，定義dx：C∪D→V,α|→dx(α)=α(x)為決策表的決策函數。

dx|C表示決策函數dx被限制為只能在條件屬性集C上取值，稱為dx的條件；

dx|D表示決策函數dx被限制為只能在決策屬性集D上取值，稱為dx的決策；

?y∈U，且y≠x，如果有dx|C=dy|C?dx|D=dy|D成立，則稱決策dx是相容的，也稱一致的，否則為不相容或不一致的；若?x∈U,dx是相容的，則稱決策表是相容的。相容決策表中有一個頗為重要的性質，即POSC(D)=U。

核是粗糙集理論中所有屬性約簡的交集，意味著核包含在知識的每一個約簡中，是約簡的最基礎部分。基于相對正域的一般求核方法，思想是求出決策屬性在整個條件屬性集上的正域，記為POSC(D)，再去掉一個條件屬性在整個條件屬性集上的正域，記為POSC(D)，若POSC(D)≠POSC(D)，則稱去掉的這個屬性為核屬性。定義如下：

定義3[11]在決策表S=(U,C,D,V,f)中，若?B?C,POSB(D)=POSC(D)；?b∈B均有POSB-|b|(D)≠POSC(D)，則稱B是C相對于D的基于正區域的屬性約簡，記其所有的屬性約簡為PREDD(C)。稱Core(C)=∩B?PREDD(C)(B)，為正區域屬性約簡模型的核，簡稱為正區域的核。

基于正域的求核方法，有時不會那么盡如人意，雖然會得到核集，但是不排除得到的核集就是屬性全集，如果采用深度或者寬度優先等策略可以得到所有可能的約簡結果，但是文獻[14]中證明了窮盡的搜索花費的時間和空間代價是非常高的，是一個NP-hard問題。

差別矩陣的概念由波蘭華沙大學數學家Skowron于1992年提出，方法是通過矩陣求得約簡，再由所有的約簡交集得到核屬性[15]。

定義4設S=(U,C,D,V,f)是一個決策表，其中，論域是對象的一個非空有限集合U={x1,x2,…,xn}，|U|=n，則定義：

為決策表的差別矩陣，其中，i,j=1,2,…,n。

?為如果論域中兩個對象的決策值不同，但屬性值全部相同，說明兩個對象所對應的決策是不相容的；

“-”為如果論域中兩個對象的決策值相同，則沒有必要考慮它們存在的差異；

在一個相容決策表中，決策表的相對D核等于該差別矩陣中所有單個屬性組成的集合。差別矩陣會占用很大的存儲空間，邏輯運算量很大。

HU對Skowron分辨矩陣進行改進，定義如下：

定義5[6]在決策表S=(U，C，D，V，f)中，設M=(mij)是HU的差別矩陣，?B?C，若B滿足：

(1)??≠mij∈M，有B∩mij≠?。

(2)?b∈B,B-(b)不滿足(1)，則稱B是C相對于D的基

于HU的差別矩陣的屬性約簡.記其所有的屬性約簡為PREDD(C).稱Core(C)=∩B?PREDD(C)(B)，為改進的基于skowron的差別矩陣屬性約簡的核。

葉東毅，楊明，孫志揮等，對Hu的方法進行糾正[16-17]，其中，楊明教授在文獻中提出了一種核屬性判定定理，張振林等學者基于此提出了一個新的簡潔的核屬性判定定理，以此為依據，提出了新的改進的差別矩陣及求核方法[18]，定義如下：

張振林等改進的差別矩陣算法中，省去了一些不必要的元素，減少了矩陣中非空元素的個數，減少了計算代價，降低了差別矩陣的復雜度。

2 改進的求核方法

上述求核方法中，基于相對正域的一般求核方法，其缺點是有時得不到單個的核屬性，即使得到的是核集，也有可能是屬性全集；Skowron提出的基于差別矩陣的求核方法，由于把所有屬性相交的結果均存儲，所以會占用較大的存儲空間，并且對所有項進行計算，其計算量很大；HU對Skowron分辨矩陣改進的算法中，有時會有得不到核屬性的情況出現；張改進的差別矩陣求核算法，由于省略了部分元素的計算，矩陣的規模縮減了很多，減少了存儲空間占用，降低了差別矩陣的復雜度，但是在某些不相容決策表中，差別矩陣會存在兩種情況：差別矩陣中并非存在單個屬性，此時，得不到核屬性；可能存在單個屬性，但所有單個屬性的并集為整個屬性集，此時和基于正域的求核屬性可能得到的結果一樣，差別矩陣并未起到求核的作用。張的方法，差別矩陣中行和列的確定是比較模糊的，當決策屬性有兩種取值時，能輕松的得到行列的數據，而有些時候，決策屬性值并非兩種，此時，差別矩陣是不好確定的。基于此，本文提出了一種分級策略的求核屬性方法，即根據決策屬性的值提出分級策略，構成分級差別矩陣，通過本文方法，彌補了其他求核方法中得不到核屬性的缺點，同時，通過決策值的分級策略，得到的分級矩陣，有效壓縮差別矩陣中的空值元素，能減少存儲空間。算法描述如下：

輸入：一個決策系統S=(U，C，D，V，f)。

輸出：屬性核CORE。

Step1：判斷數據是否為適合操作的數據形式，如果不是，則概化系統數據，即用相應的數字代替，并令CORE=?。

Step2：求U/C={X1,X2,…,Xn}和U/D={Y1,Y2,…,Ym,},POSC(D).如果POSC(D)=U，轉到Step4；否則轉到Step3。

Step3：α∈C,β∈C，如果α(xi)=β(xi)，則可以去掉α或者β,此時U=U-1,令U1=POSC(D)，U2=U/U1，構建差別矩陣M1，其中行由U1構成，列由U2構成：形成如下形式的矩陣：

如果差別矩陣中存在單個屬性，且所有單個屬性的并集并非屬性全集，則為核，轉到Step5.

Step5：CORE={α}，算法結束。

3 實例分析

下面以一個不相容的交易決策表表1為例，對該算法進行解釋說明。

決策信息表S=(U,C,D,V,f)，其中，U={{1}，{2}，{3}，{4}，{5},{6},{7},{8},{9}}c={a,b,c,d},D={e},Va={0,1,2},Vb={0,1,2,3},Vc={0,1,2},Vd={0,1,2,3}

表1 決策信息表

(1)基于正域的求核方法：

U/C={{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8，9}}

U/D={{1，2}，{3，4，8}，{5，6，7，9}

U/(C/{a})={{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8，9}；

U/(C/{b})={{1},{2,4},{3},{5},{6},{7},{8,9}}；

U/(C/{c})={{1},{2},{3},{4},{5},{6},{7},{8,9}}；

U/(C/g0gggggg)={{1},{2},{3,4},{5},{6},{7},{8,9}}；

POSC(D)={{1},{2},{3},{4},{5},{6},{7}}

POSC/(a)(D)={{1},{2},{3},{4},{5},{6},{7}}

POSC/(b)(D)={{1},{3},{5},{6},{7}}

POSC/(c)(D)={{1},{2},{3},{4},{5},{6},{7}}

POSC/(d)(D)={{1},{2},{3},{4},{5},{6},{7}}

由上可知，POSC/(b)(D)≠POSC(D)，所以，核屬性為{b}。

(2)張振林等提出的改進的求核算法如下：

由上述可知，POSC(D)={{1},{2},{3},{4},{5},{6},{7}}≠U，此時，U1={{1},{2},{3},{4},{5},{6},{7}}，U2=U/U1={{8,9}}，得到差別矩陣見表2。

表2 差別矩陣表

表3 約簡差別矩陣

上述矩陣中不存在單個屬性，所以得不到核屬性，并且，很容易看出，由于{8,9}∈U/C，所以，差別矩陣中，得到的兩列數據是重復的，此時，會占用一定的存儲空間，同時增加了計算量。

(3)本文改進的基于差別矩陣的分級策略求核算法處理如下：

Step1：由表1可知，決策信息表為適合挖掘的形式，不用再概化。

Step2：根據(1)中描述，POSC(D)≠U，則轉到Step3。

Step3：由計算可知{8,9}∈U/C，則可以得到差別矩陣見表3，得不到單個的屬性，即得不到核值，所以轉Step4。

Step4：決策屬性分級[D]i，此例中i=1,2,3，[D]1={1,2}，[D]2={3,4,8}，[D]3={5，6，7，9}，此時U也得到了分級，U1={1，2}，U2={3，4，8}，U3={5，6，7，9}，差別矩陣見表4。

表4 分級矩陣(1)

表4 分級矩陣(2)

由于決策屬性取值分級為3，則可以形成如上的兩個矩陣，兩矩陣之間并不存在交叉重復的情況，從分級矩陣(1)中可看出，單個屬性b,d，則核集CORE={b,d}，上述三種方法中，基于正域的核提取，本例中順利得到核{b}；張振林等的方法，可以處理不相容決策表，但是構建的差別矩陣，沒有對所有對象進行兩兩對比，可能會遺漏信息，同時差別矩陣的形成的數據可能是冗余的，如上述情況所示，當兩個對象對應的所有取值都是一樣時，既占用數據存儲空間，又降低算法的運行效率和時間代價，也會有得不到單個屬性的時候；本文提出的方法，不僅可以處理相容決策表，也能處理不一致決策表，避免了差別矩陣中出現冗余的數據。

4 實驗分析

選擇數據庫中的6個數據集進行實驗，實驗數據為林農對林業保險的需求影響因素，其中條件屬性包括林業生產損失程度、林木種植的最大風險類型、是否考慮用保險來分擔風險、林農對風險的感知程度等，決策屬性為林農是否愿意參加林業保險。具體信息見表5。計算機硬件配置Intel(R)Core(TM)i3 CPU M330 2.13GHz，內存2GB，開發平臺為Myeclipse，用java語言實驗本文的算法。

表5 數據集信息表

求核屬性的結果見表6。

表6 求核屬性結果

上述實驗中，因為差別矩陣的方法適用于不完備的決策信息表，所以用“-”代表決策表是完備的。從實驗結果可以看出，本文的算法和基于正域的求核屬性算法得到的核幾乎完全相同，只有部分數據由于去除了單個屬性后，仍然得不到核約簡，但是通過D集的運算，可以得到核集，說明了D集的可用性。數據集2中可以明顯的看出，決策表是適用于差別矩陣方法的，但是得不到核，而正域的方法也同樣得不到核，經過D集算法的運算，可以得到核，說明算法的有效性。同理可以得到，數據集3和6，不適用于差別矩陣的方法，D集方法和正域方法得到的核是一樣的，再次說明了D集算法的有效性。

5 結束語

在完備決策表中，用基于正域方法相對來說是比較有效的，但是不免有得不到核屬性的情況；在不完備決策表中，通常用差別矩陣求核屬性的方法是比較好的，但是對有些數據集，此方法就顯得不那么有效。本文從一致到不一致的角度，全面考慮決策表的特點，提出了一種基于D集的差別矩陣的求核方法，即在一致表時直接用D集和在不一致表時用差別矩陣、當差別矩陣得不到核屬性時再用D集來求核的方法。實驗結果表明，該算法能更有效的對決策系統進行約簡，獲得較好的核結果。

【參 考 文 獻】

[1] 張國清，鄭雪峰，張明德，等.粗糙集中不同核的比較研究[J]，小型微型計算機系統，2012，1(1)121-122.

[2] Deng D，Huang H，Li X.Comparision of various types of reductions in inconsistent systems[J].ACTA Electronica Sinica，2007，35(2)：252-255.

[3] Xu Z，Yang B，Song W，et al.Comparative research of different attribute reduction definitions[J].Journal of Chinese Computer System，2008，29(5)：848-853.

[4] Pawlak Z.Rough set[J].Communication of the ACM，1995，38(11)：89-95.

[5] 王國胤，于 洪，楊大春.基于條件信息熵的決策表[J].計算機學報，2002，75(7)：759-766.

[6] Hu X，Cercne N.Learning in relational databases：a rough set approach[J].International Journal of Computional Intelligence，1995，11(2)：323-338.

[7] Zhang W，Mi J，Wu W.Knowledge reductions in inconsistent information systems[J].Chinese Journal of Computer，2003，26(1)：12-18.

[8] 余承依，李進金.變精度粗糙集β下近似屬性約簡？[J]山東大學學報(理學版)2011.46(11)：17-21.

[9] 黃國順，曾凡智.不一致決策表各種屬性約簡的不一致性分析與轉化[J].小型微型計算機系統，2008，29(4)：703-708.

[10] 張迎春，王宇新，郭 禾.基于有序差別集和屬性重要性的屬性約簡[J].計算機科學2011，38(10)：243-246.

[11] Pawlak Z.Rough set theory and its application to data analysis[J].Cybernetics and Systems，1998，29(7)：661-668.

[12] 王 玨.粗糙集理論及其應用研究[D]，西安：西安電子科技大學2005：1-5.

[13] 苗奪謙，李道國.粗糙集理論、算法與應用[M].清華大學出版社，2008.

[14] 王國胤.Rough理論與知識獲取.西安交通大學出版社.2001.

[15] 張文修.粗糙集理論與方法.北京：科技出版社，2001.

[16] 葉東毅，陳昭炯.一個新的差別矩陣及其求核方法[J].電子學報，2002，30(7)：1086-1088.

[17] 楊 明，孫志揮.改進的差別矩陣及其求核方法[J].復旦學報(自然科學版)，2004，43(5)：865-869.

[18] 張振琳，黃 明.改進的差別矩陣及其求核方法[J].大連交通大學學報，2008，29(4)：79-82.