張群峰，張?zhí)煲?/p>

(1.河北大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，河北 保定 071002；2.河北大學(xué) 臨床醫(yī)學(xué)院，河北 保定 071000)

基于寬松下近似概念的連續(xù)型決策表的屬性約簡(jiǎn)方法

張群峰1，張?zhí)煲?

(1.河北大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，河北 保定 071002；2.河北大學(xué) 臨床醫(yī)學(xué)院，河北 保定 071000)

針對(duì)連續(xù)型決策表，利用模糊相容關(guān)系對(duì)樣例聚類產(chǎn)生模糊決策表,運(yùn)用寬松下近似概念定義屬性重要度,利用函數(shù)彈性概念定義決策屬性關(guān)于條件屬性的敏感度，將其作為屬性重要度的權(quán)重得到加權(quán)重要度，并以此為啟發(fā)式信息提出了一種連續(xù)型決策表的屬性約簡(jiǎn)方法.

決策表；屬性約簡(jiǎn)；模糊粗糙集

決策表是一種廣泛存在的信息系統(tǒng)，如何對(duì)其條件屬性進(jìn)行約簡(jiǎn)是機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)熱點(diǎn)問(wèn)題.表1是一個(gè)小型決策表的例子.

表1中，U={1,2,3,4,5,6}為論域，C={A1,A2,A3,A4,A5}為條件屬性集，D為決策屬性.因?yàn)閷傩灾悼梢允沁B續(xù)的實(shí)數(shù)，所以此決策表稱為連續(xù)型決策表.

連續(xù)型決策表的一般形式為四元組(U,C,D,f)，其中U={i|i=1,2,…,m}為論域，i=1,2,…,m為樣例的代號(hào);C={Aj|j=1,2,…,n}為條件屬性集合；D為決策屬性；f:U×(C∪D)→R,f(i,Aj)=Aj(i)=aij,f(i,D)=di,i=1,2,…,m,j=1,2,…,n為信息函數(shù)，其中R為實(shí)數(shù)集合.

所謂對(duì)連續(xù)型決策表進(jìn)行屬性約簡(jiǎn)，是指尋找條件屬性集的一個(gè)子集，并使其具有與整個(gè)條件屬性集合相同的分類能力[1].在模糊粗糙集理論中，條件屬性子集的分類能力可以用決策屬性對(duì)其依賴度表示，而依賴度指決策屬性相對(duì)該條件屬性子集的正域在論域中所占的比例.

表1 決策表的例

利用粗糙集理論計(jì)算決策表屬性約簡(jiǎn)的通常做法是，先找出對(duì)保持整個(gè)條件屬性集合分類能力必不可少的條件屬性組成屬性的核.若核具有與整個(gè)條件屬性集相同的分類能力，則核就是所求的屬性約簡(jiǎn)；否則，將核作為候選約簡(jiǎn)，然后依據(jù)某種啟發(fā)式信息選擇核外屬性不斷加入候選約簡(jiǎn)，直到候選約簡(jiǎn)具有與整個(gè)條件屬性集相同的分類能力.因此設(shè)計(jì)高效約簡(jiǎn)算法的關(guān)鍵是如何構(gòu)建這種啟發(fā)式信息.

常見(jiàn)的構(gòu)建啟發(fā)式信息的方法有2種.一種通過(guò)辨識(shí)矩陣[2]，另一種通過(guò)度量條件屬性對(duì)某屬性子集的分類能力的影響.第2種方法就是要計(jì)算去除或添加一個(gè)條件屬性所導(dǎo)致的決策屬性對(duì)該屬性子集依賴度的變化.由于依賴度概念由正域描述，而正域是決策類的下近似的并集，所以選用恰當(dāng)?shù)南陆聘拍钍堑?種方法的關(guān)鍵問(wèn)題.

對(duì)這個(gè)問(wèn)題，相關(guān)的文獻(xiàn)采取了不同的解決方法.文獻(xiàn)[3]采用了文獻(xiàn)[4]提出的下近似概念，這種下近似概念是單個(gè)條件屬性的模糊劃分對(duì)決策類的近似表示.但是，為了計(jì)算屬性約簡(jiǎn)，必須從單個(gè)條件屬性推廣到條件屬性子集的情形，這就需要計(jì)算屬性的模糊劃分的笛卡爾乘積[5]，從而引起計(jì)算量的指數(shù)式增加.在計(jì)算機(jī)科學(xué)中這種算法通常被認(rèn)為是不可取的.文獻(xiàn)[5]引用文獻(xiàn)[6]提出的基于模糊t-模和模糊蘊(yùn)含算子的下近似概念，避開(kāi)了模糊劃分概念，從而降低了計(jì)算的復(fù)雜性.

但是，如文獻(xiàn)[7]指出的那樣，文獻(xiàn)[5]利用的是通常意義下的下近似概念，其外延較小，作為決策概念的子集，沒(méi)有達(dá)到對(duì)模糊決策概念的最大逼近.同時(shí)，該方法所用下近似概念要求計(jì)算模糊相容關(guān)系的傳遞閉包，有時(shí)計(jì)算量較大.另外，該方法在產(chǎn)生模糊決策表時(shí)運(yùn)用了獨(dú)立于模糊粗糙集理論的模糊化方法產(chǎn)生模糊決策表，而沒(méi)有充分利用模糊粗糙集理論中模糊相容關(guān)系的信息.

文獻(xiàn)[3，5]均未考慮決策屬性對(duì)條件屬性的敏感性.敏感性的概念在機(jī)器學(xué)習(xí)的其他領(lǐng)域已得到充分重視，例如在神經(jīng)網(wǎng)絡(luò)中將敏感性作為訓(xùn)練過(guò)程中的重要啟發(fā)式信息.

基于以上分析，本文針對(duì)連續(xù)型決策表，首先根據(jù)模糊相容關(guān)系對(duì)樣例進(jìn)行聚類產(chǎn)生模糊決策表.其次，由于模糊粗糙集理論中的寬松下近似概念是建立在模糊相容關(guān)系基礎(chǔ)上，且比文獻(xiàn)[5]所用的下近似概念能更加準(zhǔn)確地逼近決策類，故本文引用寬松下近似概念來(lái)定義條件屬性的重要度.最后，本文引入新的屬性敏感度定義，將其作為條件屬性重要度的權(quán)重從而得到加權(quán)重要度，并以此作為啟發(fā)式信息對(duì)連續(xù)型決策表進(jìn)行屬性約簡(jiǎn).

1 預(yù)備知識(shí)

1.1模糊粗糙集的寬松下近似概念

設(shè)X為給定的論域，R為X上的模糊相容關(guān)系，即R滿足自反性R(i,i)=1,?i∈U和對(duì)稱性R(i,j)=R(j,i),?i,j∈U.用F(X)表示X上的全體模糊集合，則對(duì)于任意A∈F(X)，A的寬松下近似定義為[7]

(1)

而通常的下近似定義為

(2)

其中T為模糊t-模而I為模糊蘊(yùn)含算子.

一般地有R↓A?R↑↓A?A，下例說(shuō)明第1個(gè)集合可能是第2個(gè)集合的真子集[7],即包含關(guān)系中的等號(hào)可能不成立.

例 設(shè)X=[0,1]，A∈F(X)定義為A(x)=x，?x∈X,X上的模糊相容關(guān)系定義為

則對(duì)任何t-T和任意模糊蘊(yùn)含算子I有(R↓A)(0.95)=0.85，(R↑↓A)(0.95)=0.9，即(R↓A)(y)?(R↑↓A)(y).

1.2函數(shù)的彈性概念

在離散情形，若y=f(x)滿足yi=f(xi)，i=1,2,…,n,本文將彈性概念變形為差商形式

(3)

2 構(gòu)建模糊決策表

利用模糊粗糙集理論進(jìn)行屬性約簡(jiǎn)，首先要把連續(xù)型決策表轉(zhuǎn)換成模糊決策表.通常的模糊化方法事先人為指定模糊集的個(gè)數(shù)和形式，這樣難免帶有一定的主觀性.本文考慮到，2個(gè)樣例若有很高的相似性，則應(yīng)對(duì)同一個(gè)模糊集的隸屬度應(yīng)相近；否則，應(yīng)盡量歸于不同的模糊集.而模糊相容關(guān)系反映了樣例的相似程度，因此采取基于模糊相容關(guān)系的聚類方法產(chǎn)生模糊集.刻劃樣例之間的相似程度的模糊相容關(guān)系已得到詳細(xì)研究[8]，本文以如下模糊相容關(guān)系[5]為例進(jìn)行描述：

(4)

其中σAj為屬性Aj的屬性值的均方差.

選定模糊相容關(guān)系后，本文結(jié)合參考文獻(xiàn)[8]中所述聚類方法，提出如下產(chǎn)生模糊決策表的算法：

算法1 構(gòu)建模糊決策表

輸入：連續(xù)型決策表

輸出：模糊決策表

步驟1： 對(duì)每個(gè)屬性，計(jì)算其相似矩陣；

步驟2：依據(jù)相似矩陣的截集矩陣對(duì)樣例聚類；

步驟3： 對(duì)每個(gè)類計(jì)算其元素的平均相似度，將平均相似度最高的元素i作為聚類中心，并以Aj(i,k),k=1,2,…,n作為屬性Aj的一個(gè)模糊集.

例如，運(yùn)用上述算法對(duì)表1中條件屬性A3和決策屬性D分別模糊化的結(jié)果如表2和表3所示.

表2 條件屬性的模糊化

表3 模糊決策屬性的模糊化

3 利用模糊粗糙集理論進(jìn)行屬性約簡(jiǎn)

3.1決策屬性對(duì)條件屬性子集的依賴度

論域U={i|i=1,2,…,m}上模糊集合的全體記為F(U).根據(jù)定義式(1)，任意模糊集合X∈F(U)的RA-寬松下近似為

(5)

T(x,y)=min{x,y},

(6)

取I為L(zhǎng)ukasiewiz模糊蘊(yùn)含算子

I(x,y)=min{1-x+y,1},

(7)

進(jìn)而定義決策屬性D相對(duì)于條件屬性子集A的正域?yàn)?/p>

(8)

最后，定義決策屬性D相對(duì)于條件屬性子集A的依賴度為

(9)

3.2條件屬性的內(nèi)、外重要度

設(shè)A?C為條件屬性子集，A∈A，則A相對(duì)于A的內(nèi)部重要度定義為

(10)

設(shè)A?C為條件屬性子集，A∈C-A，則A相對(duì)于A的外部重要度定義為

(11)

3.3決策屬性相對(duì)于條件屬性的敏感度

若一個(gè)條件屬性的值的微小改變能引起決策屬性值的劇烈改變，則決策屬性對(duì)該條件屬性變化的反應(yīng)較靈敏；反之，較遲鈍.筆者認(rèn)為，反應(yīng)的靈敏或遲鈍是決策效率高低的表現(xiàn)，依賴度是決策的確定性程度的度量，依賴度具有本質(zhì)的意義，而靈敏度和依賴度是相輔相成的關(guān)系.因此，靈敏度可以作為屬性重要度的權(quán)重來(lái)構(gòu)造啟發(fā)式信息.

將連續(xù)型決策表的條件屬性看作自變量而將決策屬性看作因變量，則決策屬性對(duì)條件屬性的靈敏性可以用離散情形的彈性公式(3)來(lái)計(jì)算.值得注意的是，這里沒(méi)有像通常的神經(jīng)網(wǎng)絡(luò)敏感性分析中那樣用導(dǎo)數(shù)作為敏感性的度量.這是因?yàn)楹瘮?shù)的彈性反應(yīng)的是函數(shù)值對(duì)自變量的相對(duì)變化量，而導(dǎo)數(shù)反映的是函數(shù)值對(duì)自變量的絕對(duì)變化量，而且，彈性沒(méi)有量綱，更便于比較決策屬性關(guān)于不同條件屬性的敏感性的大小.

運(yùn)用式(4)可得表1中決策屬性關(guān)于各個(gè)條件屬性的彈性如表4所示.

表4 條件屬性的彈性

3.4模糊粗糙約簡(jiǎn)

首先，把整個(gè)條件屬性集中具有大于零的內(nèi)部重要度的條件屬性稱為核屬性.所有核屬性的集合稱為核，記作

(12)

其次，把能保持整個(gè)條件屬性集合的分類能力不變的條件屬性子集作為條件屬性集的模糊約簡(jiǎn).

計(jì)算屬性約簡(jiǎn)的流程如下：先計(jì)算各個(gè)條件屬性在整個(gè)條件屬性集合的內(nèi)部重要度，進(jìn)而求出條件屬性的核.若核不是約簡(jiǎn)，則將其作為候選約簡(jiǎn)，并加入相對(duì)于候選約簡(jiǎn)具有最大加權(quán)外部重要度的非核屬性形成新的候選約簡(jiǎn)，直到候選約簡(jiǎn)具有與整個(gè)條件屬性集有相同的分類能力為止.算法描述如下：

算法2 計(jì)算連續(xù)型決策表的屬性約簡(jiǎn)

輸入：模糊決策表

輸出：條件屬性集的模糊約簡(jiǎn)

步驟3：計(jì)算γRDT(D).若γRDT(D)=γC(D)，則轉(zhuǎn)第5步；

步驟5：輸出RDT，結(jié)束.

對(duì)前述決策表，經(jīng)計(jì)算可得CORE={A5}和屬性約簡(jiǎn)RDT={A1,A5}.

4 結(jié)論

本文針對(duì)連續(xù)型決策表的屬性約簡(jiǎn)問(wèn)題，提出了一種基于模糊粗糙集理論中寬松下近似概念的解決方法.相對(duì)于已有的方法，本文的方法立足模糊粗糙集理論，采用了更準(zhǔn)確的寬松下近似概念來(lái)逼近決策概念，并結(jié)合屬性敏感度構(gòu)造啟發(fā)式信息計(jì)算約簡(jiǎn)，下一步將考慮在約簡(jiǎn)的基礎(chǔ)上構(gòu)建模糊決策樹(shù).

[1]TSANG E C C, CHEN D G, YEUNG D S, et al. Attributes reduction using fuzzy rough sets[J]. IEEE Trans Fuzzy Syst, 2008, 16(5): 1130-1141.

[2]HE Qiang, WU Congxin, CHEN Degang, et al. Fuzzy rough set based attribute reduction for information systems with fuzzy decisions[J]. Knowledge-Based Systems, 2011(24):689-696.

[3]BHATT R B, GOPAL M. FRCT: fuzzy-rough classification trees[J]. Pattern Anal Applic, 2008, 11(1): 73-88.

[4]DUBOIS D, PRADE H. Rough fuzzy sets and fuzzy rough sets[J]. Int J Gen Syst, 1990(17 ): 191-208.

[5]JENSEN R, SHEN Q. New approaches to fuzzy-rough feature selection[J]. IEEE Transaction on Systems, 2009,17(4):824-838.

[6]RADZIKOWSKA A M, KERRE E E. A comparative study of fuzzy rough sets[J]. Fuzzy Sets System, 2002,126(2):137-155.

[7]CORNELIS C, COCK M D, RADZIKOWSKA A M. Fuzzy rough sets: from theory into practice [EB/OL].(2008-07-16)[2012-07-10] www.cwi.ugent.be.

[8]高新波. 模糊聚類分析及其應(yīng)用[M]. 西安：西安電子科技大學(xué)出版社，2004.

Reducingtheattributesofdecisiontableswithrealvaluesbasedonlooselowerapproximation

ZHANGQunfeng1,ZHANGTianyi2

(1.College of Mathematics and Computer Science, Hebei University, Baoding 071002, China;

2.College of Clinical Medicine, Hebei University, Baoding 071000, China)

To reduce the attributes of decision tables with real attribute values, a method based on loose lower approximation in fuzzy rough set theory is proposed. First, a fuzzy decision table is generated by using the fuzzy tolerance relation. Second, based on loose lower approximation, the inner importance degree and outer importance degree of condition attributes are defined. By utilizing a combination of importance degree and sensitivity of decision attributes, an algorithm for reducing the decision table is designed and an example is demonstrated.

decision table; attribute reduction; fuzzy rough sets

10.3969/j.issn.1000-1565.2013.04.001

2013-01-17

河北省教育廳科學(xué)研究計(jì)劃資助項(xiàng)目(2009312)；河北省科技廳軟科學(xué)項(xiàng)目(12457662)；河北省自然科學(xué)基金資助項(xiàng)目(F2011201063)

張群峰(1963-)，男，河北成安人，河北大學(xué)副教授，主要從事粗糙集理論及應(yīng)用、機(jī)器學(xué)習(xí)理論方向研究.

E-mail:zhangqunfeng@hbu.cn

O235

A

1000-1565(2013)04-0337-05

MSC201068T05

(責(zé)任編輯王蘭英)