基于可分辨矩陣的屬性集依賴度計算方法

謝 科

(阿壩師范高等專科學(xué)校計算機(jī)科學(xué)系,中國 汶川 623002 )

粗糙集理論[1]于1982年由波蘭學(xué)者Pawlak提出，現(xiàn)已被廣泛應(yīng)用于機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域[2-6]，其核心研究內(nèi)容就是依據(jù)決策表或者信息表的條件屬性集、決策屬性集以及對象集，進(jìn)行知識約簡從而獲得最具代表性的屬性約簡集以及最簡分類規(guī)則集[7-10]．知識約簡包括屬性約簡和分類規(guī)則約簡，目前國內(nèi)外學(xué)者主要在屬性約簡方面進(jìn)行研究[11]．

在屬性約簡中，衡量某個屬性的重要程度一般是根據(jù)決策屬性對該屬性的依賴程度來做出判斷，依賴度為1，則完全依賴；依賴度為0，則完全不依賴，其余則部分依賴[12]．對于那些依賴度為0的屬性，一般認(rèn)為并不影響決策表分類的結(jié)果，在屬性約簡時可以直接刪除[13-14]．但是，這樣不但會在某種程度上造成知識損失，而且還割斷了該屬性與其他屬性的聯(lián)系，從而造成更大程度的損失．

為此，本文在可分辨矩陣的基礎(chǔ)上，研究屬性集依賴度，提出了一種屬性集依賴度計算方法，并用實(shí)例驗證了該方法具有較好的有效性和較低的時間復(fù)雜度．

1 基本理論

設(shè)S=(U,A,V,f)是一個決策信息系統(tǒng)．其中：U是非空有限對象集，A=C∪D是屬性集，C和D分別是條件屬性集和決策屬性，f:U×A→V是一個信息函數(shù)．

定義1[11]等價族.基于條件屬性集B?C不可分辨關(guān)系的等價族表示為U|B=(X1,…,Xp)，其中Xj是由在屬性集B上的屬性值相等的對象xi構(gòu)成的集合；基于決策屬性D不可分辨關(guān)系的等價族表示為U|D=(Y1,…,Yq)，其中Yj(j=1,2,…,q)是由決策屬性值相等的對象xi構(gòu)成的集合．

定義2[11]正域.對于一個決策信息系統(tǒng)S=(U,A,V,f)，設(shè)根據(jù)條件屬性B?C劃分的等價族為Xi,i=1,2,…,p，根據(jù)決策屬性D劃分的決策屬性等價族為Yj,j=1,2,…,q，則定義Yj的下近似集為：

P-(Yj)=∪{Xi∈U|Xi?Yj}，

(1)

其中i=1,2,…,p;j=1,2,…,q.

定義3[11]D的B正域表示為POSB(D)，即：

POSB(D)=∪P_(Yj),j=1,2,…,q.

(2)

系統(tǒng)的知識可以用決策屬性D表達(dá)，也可以由條件屬性C描述，這取決于數(shù)據(jù)庫中函數(shù)之間的依賴性關(guān)系．

定義4[11]依賴度.設(shè)S=(U,A,V,f)是一個決策信息系統(tǒng)，A=C∪D是屬性集，C和D分別是條件屬性集和決策屬性，基于條件屬性集B?C描述決策屬性D表達(dá)的知識，其可導(dǎo)性定義為知識的依賴性，表達(dá)為

(3)

稱其為D以依賴度k(0≤k≤1)依賴于B，記作B?D，這里card()表示集合的基數(shù)．

定義5[11]可分辨矩陣.設(shè)S=(U,A,V,f)是一個決策信息系統(tǒng)，U={x1,x2,…,xn}為對象集,包含n條記錄,A=C∪D是屬性集，C={a1,a2,…,am}和D=j5i0abt0b分別是條件屬性集和決策屬性，包含m個條件屬性和1個決策屬性．對于任意2個對象xi和xj，定義可分辨矩陣的元素為

(4)

性質(zhì)1當(dāng)任一條件屬性集B包含于分辨矩陣中的某個元素，即B?Mij，則決策表中的對象xi、xj?POSB(D)．

證因為B?Mij，根據(jù)可分辨矩陣的定義，對象xi和xj的決策屬性不同，即d(xi)≠d(xj)，但對于任意條件屬性ak∈B，xi和xj的屬性值相等，即ak(xi)=ak(xj)．根據(jù)正域的定義，即可得xi、xj?POSB(D)．

定義6[11]屬性集依賴度.設(shè)S=(U,A=C∪D,V,f)是一個決策信息系統(tǒng)，B?C為一個條件屬性集(該屬性集由1個以上的屬性組成)，此時D對B的依賴度稱為屬性集依賴度．

2 本文所提屬性集重要度評價方法

在一個決策信息系統(tǒng)中，如果存在多個條件屬性的依賴度相等時，就無法判斷哪個屬性更重要．在這種情況下，就需要與其他條件屬性(2個或2個以上)構(gòu)成屬性集并計算該屬性集的依賴度，以此大小來分辨該屬性的重要程度．文獻(xiàn)[15]給出了一個屬性集依賴度計算方法，具體算法描述如下：

Begin://劃分等價類

for each 條件屬性的組合

fori=1 ton

forj=i+1 ton

比較xi和xj的條件屬性，屬性值相同的歸為一個等價類；

end

end

end

nCount=0；

for 每個等價簇

如果該簇中全部對象的決策屬性值都相同,那么

nCount=nCount+該類對象數(shù)；

end for

return nCount/對象總數(shù)//返回屬性依賴度

End

為克服上述算法的不足，本文在定義5的基礎(chǔ)上，提出一個新的屬性集依賴度計算方法，其描述如下：

Begin:

根據(jù)定義5求出分辨矩陣M；

A={x1,x2,…,xn}； //生成對象集

對于任意的屬性集B

for eachA中的對象xi

if 分辨矩陣的第i行存在一個元素Mij，使得xk?Mij；

從A中刪除xi和xj；

end if

end for

returnA中的對象個數(shù)/對象總數(shù)； //返回屬性依賴度

End

如果有m個條件屬性，n個對象，本文方法時間復(fù)雜度由以下2個部分組成：①分辨矩陣時間復(fù)雜度為O(m×n2)；②其余時間復(fù)雜度為O(m2×n)．則總的時間復(fù)雜度為O(m×n2+m2×n)，這同文獻(xiàn)[15]方法的時間復(fù)雜度相比具有一定的優(yōu)勢．

3 實(shí)例驗證

實(shí)驗運(yùn)行環(huán)境為2.00 GHz，1.99 GB RAM，Windows XP操作系統(tǒng)．為了全面地驗證本文算法，選擇如下6個實(shí)驗數(shù)據(jù)集進(jìn)行實(shí)驗：①文獻(xiàn)[15]中的1個決策信息表，具體如表1所示，共有8個對象，條件屬性集C由屬性{a,b,c,d}組成，決策屬性為D．

表1 取自文獻(xiàn)[15]的決策表

②California大學(xué)提供的UCI知識庫中的Chess End-Game數(shù)據(jù)集，該數(shù)據(jù)集包括36個條件屬性，1個決策屬性，共3 196項記錄．③California大學(xué)提供的UCI知識庫中的Diabetes數(shù)據(jù)集，該數(shù)據(jù)包括8個條件屬性，2個決策屬性，共798項記錄．

④California大學(xué)提供的UCI知識庫中的Segmentation數(shù)據(jù)集，該數(shù)據(jù)集包括19個條件屬性，7個決策屬性，共2 932項記錄．

⑤California大學(xué)提供的UCI知識庫中的Breast數(shù)據(jù)集，該數(shù)據(jù)集包括9個條件屬性，2個決策屬性，共817項記錄．

⑥California大學(xué)提供的UCI知識庫中的Bupa數(shù)據(jù)集，該數(shù)據(jù)集包括6個條件屬性，5個決策屬性，共428項記錄．

為了便于表達(dá)，本文算法簡稱NM，文獻(xiàn)[15]算法簡稱OM，其實(shí)驗結(jié)果如表2所示：

表2 NM和OM算法實(shí)驗結(jié)果對比

從表2可以看出，對于本文算法和文獻(xiàn)[15]算法，在各個實(shí)驗數(shù)據(jù)集上，各屬性依賴度的計算結(jié)果都近似一致，但本文算法的耗時較低，尤其是數(shù)據(jù)集較大的時候，這個優(yōu)勢更加明顯．

4 結(jié)束語

在信息表中，那些依賴度等于0的屬性也可能對其他屬性產(chǎn)生影響.在這種情況下，屬性集依賴度就更能反映現(xiàn)實(shí)情況．為此，本文提出了一個新型基于辨識矩陣的屬性集重要度評價方法，實(shí)例驗證了該方法的有效性和較低的時間復(fù)雜度，從而使得本文方法在屬性約簡中有一定的實(shí)用價值．

參考文獻(xiàn)：

[1] 朱顥東,鐘 勇.基于優(yōu)化的文檔頻和粗糙集的特征選擇方法[J].湖南師范大學(xué)自然科學(xué)學(xué)報, 2009,32(3):27-31.

[2] CHEN D G, HU Q H, YANG Y P. Parameterized attribute reduction with Gaussian kernel based fuzzy rough sets[J]. Int J Inform Sci, 2011,181(23):5169-5179.

[3] 黃媛玉,毛 弋.基于主成分分析法的遺傳神經(jīng)網(wǎng)絡(luò)模型對電力系統(tǒng)的短期負(fù)荷預(yù)測[J].湖南師范大學(xué)自然科學(xué)學(xué)報, 2011,34(5):26-31.

[4] 胡 強(qiáng).優(yōu)化的互信息特征選擇方法[J].湖南師范大學(xué)自然科學(xué)學(xué)報, 2010,33(3):28-31.

[5] KIYOSHI H, MICHAUD K, MASAMOTO A. Application of data mining to quantitative structure-activity relationship using rough set theory[J].Int J Chem Intell Lab Sys, 2009,99(1):66-70.

[6] MICHAEL N, GUDRUN S, GERHARD S. Adapted variable precision rough set approach for EEG analysis[J].Int J Artif Intell Med, 2009,47(3):239-261.

[7] 馬建敏,張文修,朱朝暉. 基于信息量的序信息系統(tǒng)的屬性約簡[J]. 系統(tǒng)工程理論與實(shí)踐, 2010,30(9)：1679-1683.

[8] FAN T F, LIAU C J, LIU D R. A relational perspective of attribute reduction in rough set-based data analysis[J].Eur J Opera Res, 2011,213(1):270-278.

[9] QIAN Y H, LIANG J Y, PEDRYCZ W. An efficient accelerator for attribute reduction from incomplete data in rough set framework[J].Pattern Recog, 2011,44(8):1658-1670.

[10] HE Q, WU C X, CHEN D G,etal. Fuzzy rough set based attribute reduction for information systems with fuzzy decisions[J]. Knowledge-Based Sys, 2011,24(5):689-696.

[11] 胡壽松,何亞群. 粗糙決策理論與應(yīng)用[M]. 北京:北京航空航天大學(xué)出版社, 2006.

[12] YAO Y Q, MI J S, LI Z J. Attribute reduction based on generalized fuzzy evidence theory in fuzzy decision systems[J].Fuzzy Sets Sys, 2011,170(1):64-75.

[13] QIAN Y H, LIANG J Y, PEDRYCZ W. Positive approximation: an accelerator for attribute reduction in rough set theory[J].Artif Intell, 2010,174(9):597-618.