一種改進(jìn)的基于差別矩陣的求核屬性算法

陸 光，李 想

(東北林業(yè)大學(xué) 信息與計(jì)算機(jī)工程學(xué)院，哈爾濱 150040)

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

1 粗糙集理論基本知識(shí)

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

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

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

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

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

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

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

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

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

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

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

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

?為如果論域中兩個(gè)對(duì)象的決策值不同，但屬性值全部相同，說明兩個(gè)對(duì)象所對(duì)應(yīng)的決策是不相容的；

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

在一個(gè)相容決策表中，決策表的相對(duì)D核等于該差別矩陣中所有單個(gè)屬性組成的集合。差別矩陣會(huì)占用很大的存儲(chǔ)空間，邏輯運(yùn)算量很大。

HU對(duì)Skowron分辨矩陣進(jìn)行改進(jìn)，定義如下：

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

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

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

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

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

張振林等改進(jìn)的差別矩陣算法中，省去了一些不必要的元素，減少了矩陣中非空元素的個(gè)數(shù)，減少了計(jì)算代價(jià)，降低了差別矩陣的復(fù)雜度。

2 改進(jìn)的求核方法

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

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

輸出：屬性核CORE。

Step1：判斷數(shù)據(jù)是否為適合操作的數(shù)據(jù)形式，如果不是，則概化系統(tǒng)數(shù)據(jù)，即用相應(yīng)的數(shù)字代替，并令CORE=?。

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

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

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

Step5：CORE={α}，算法結(jié)束。

3 實(shí)例分析

下面以一個(gè)不相容的交易決策表表1為例，對(duì)該算法進(jìn)行解釋說明。

決策信息表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/)={{1},{2,4},{3},{5},{6},{7},{8,9}}；

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

U/(C/j5i0abt0b)={{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)，所以，核屬性為。

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

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

表2 差別矩陣表

表3 約簡(jiǎn)差別矩陣

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

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

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

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

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

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

表4 分級(jí)矩陣(1)

表4 分級(jí)矩陣(2)

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

4 實(shí)驗(yàn)分析

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

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

求核屬性的結(jié)果見表6。

表6 求核屬性結(jié)果

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

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

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

【參 考 文 獻(xiàn)】

[1] 張國(guó)清，鄭雪峰，張明德，等.粗糙集中不同核的比較研究[J]，小型微型計(jì)算機(jī)系統(tǒng)，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] 王國(guó)胤，于 洪，楊大春.基于條件信息熵的決策表[J].計(jì)算機(jī)學(xué)報(bào)，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ìn)金.變精度粗糙集β下近似屬性約簡(jiǎn)？[J]山東大學(xué)學(xué)報(bào)(理學(xué)版)2011.46(11)：17-21.

[9] 黃國(guó)順，曾凡智.不一致決策表各種屬性約簡(jiǎn)的不一致性分析與轉(zhuǎn)化[J].小型微型計(jì)算機(jī)系統(tǒng)，2008，29(4)：703-708.

[10] 張迎春，王宇新，郭 禾.基于有序差別集和屬性重要性的屬性約簡(jiǎn)[J].計(jì)算機(jī)科學(xué)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] 王 玨.粗糙集理論及其應(yīng)用研究[D]，西安：西安電子科技大學(xué)2005：1-5.

[13] 苗奪謙，李道國(guó).粗糙集理論、算法與應(yīng)用[M].清華大學(xué)出版社，2008.

[14] 王國(guó)胤.Rough理論與知識(shí)獲取.西安交通大學(xué)出版社.2001.

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

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

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

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