楊貴如

(陽(yáng)泉師范高等?？茖W(xué)校，山西 陽(yáng)泉 045200)

粒度計(jì)算(GrC)是信息處理的一種新的概念，主要研究的是模糊的、不完整的、不確定的和海量的信息。它的三大研究模型分別為基于模糊集合論的詞計(jì)算模型、基于粗糙集理論的粒度計(jì)算模型和基于商空間的粒度計(jì)算模型，已經(jīng)廣泛應(yīng)用于各個(gè)領(lǐng)域[1-3]。其中粗糙集模型中的論域?；蔀檠芯康臒狳c(diǎn)之一。

1982年，Pawlak教授提出了粗糙集理論[4]，作為一種處理不確定的、模糊的、和不完備性問(wèn)題的新型數(shù)學(xué)工具，被國(guó)內(nèi)外學(xué)者廣泛的重視和發(fā)展[5-7]。其中決策規(guī)則性能的評(píng)測(cè)，是粗糙集的一大熱點(diǎn)研究?jī)?nèi)容，通常采用確定度來(lái)衡量其性能。由于粒度計(jì)算這種新型的研究工具已經(jīng)得到了廣泛的應(yīng)用，如何通過(guò)粒度計(jì)算來(lái)評(píng)測(cè)決策規(guī)則成為了新的研究問(wèn)題。因此，本文基于粒度計(jì)算的思想，以知識(shí)距離為準(zhǔn)則，提出了一種?；乃惴?，通過(guò)粗化條件屬性集，實(shí)現(xiàn)對(duì)決策規(guī)則的評(píng)測(cè)。實(shí)例證明該方法評(píng)測(cè)效果較為理想。

1 基本概念

定義3[9]設(shè)S=(U,C∪D)是一個(gè)決策表，Xi∈U/C，Yj∈U/D，desC(Xi)是Xi在C下的唯一描述，desD(Yj)是Yj在D下的唯一描述。決策規(guī)則定義如下：

rij∶desC(Xi)→desD(Yj),Xi∩Yj≠?,決策規(guī)則rij的確定度μ(Xi,Yj)=|Xi∩Yj|/|Xi|，0<μ(Xi,Yj)≤1.

當(dāng)μ(Xi,Yj)=1時(shí)，rij是確定的；當(dāng)0<μ(Xi,Yj)<1時(shí)，rij是不確定的。

定義4[9]設(shè)有集合A和集合B，A和B的集合貼近度定義為：

其中0≤H(A,B)≤1.

定義5[9]設(shè)S=(U,A)是一個(gè)信息系統(tǒng)，P，Q?A，P和Q所對(duì)應(yīng)的知識(shí)分別為：

U/SIM(P)={SP(x1),SP(x2),…,SP(x|U|)}和

U/SIM(Q)={SQ(x1),SQ(x2),…,SQ(x|U|)}

則知識(shí)U/SIM(P)和知識(shí)U/SIM(Q)的知識(shí)貼近度定義為：

定義6[9]設(shè)有集合A和集合B，A和B的集合差異度可以定義為：

定義7[9]設(shè)S=(U,A)是一個(gè)信息系統(tǒng)，P，Q?A，P和Q所對(duì)應(yīng)的知識(shí)分別為：

U/SIM(P)={SP(x1),SP(x2),…,SP(x|U|)}和

U/SIM(Q)={SQ(x1),SQ(x2),…,SQ(x|U|)}

則知識(shí)U/SIM(P)和知識(shí)U/SIM(Q)的知識(shí)距離定義為：

2 決策規(guī)則的評(píng)測(cè)

下面通過(guò)例1來(lái)說(shuō)明決策規(guī)則的評(píng)測(cè)標(biāo)準(zhǔn)。

例1關(guān)于診斷感冒的決策表S=(U,C∪D)如下表1，其中U={x1,x2,x3,x4,x5,x6,x7,x8}，C={a1,a2,a3}={頭疼，肌肉疼，體溫}，D=ewqg8ss={感冒}。

表1 診斷感冒的決策表Tab.1 The decision table in the diagnosis of a cold

根據(jù)表1得：

U/C={X1,X2,X3,X4,X5}={{x1},{x2,x3,x8},{x4,x5},{x6},{x7}}；

U/D={Y1,Y2}={{x1,x2,x3,x4},{x5,x6,x7,x8}}；

r11∶desC(X1)→desD(Y1),μ(X1,Y1)=1;

r42∶desC(X4)→desD(Y2),μ(X4,Y2)=1;

r52∶desC(X5)→desD(Y2),μ(X5,Y2)=1;

如對(duì)新對(duì)象x9(頭疼=是，肌肉疼=是，體溫=高燒)進(jìn)行分類時(shí)，根據(jù)上述規(guī)則，適用的規(guī)則是r21和r22，由于μ(X2,Y1)>μ(X2,Y2)，則認(rèn)為x9屬于Y1的可能性較大。

如對(duì)新對(duì)象x10(頭疼=否，肌肉疼=否，體溫=低燒)進(jìn)行分類，適用的規(guī)則是r31和r32，由于μ(X3,Y1)=μ(X3,Y2)，此時(shí)無(wú)法就x10的歸屬做出決策。因此，本文運(yùn)用知識(shí)距離，提出了一種基于粒度計(jì)算的評(píng)測(cè)方法，能夠較好的解決上述問(wèn)題。

3 決策規(guī)則的評(píng)測(cè)算法

針對(duì)上述問(wèn)題可以看出，當(dāng)條件屬性集以整體的形式來(lái)評(píng)測(cè)決策規(guī)則時(shí)，制約評(píng)測(cè)結(jié)果的因素過(guò)多過(guò)細(xì)，使得無(wú)法對(duì)規(guī)則作出較為準(zhǔn)確的評(píng)測(cè)。為此，可以適當(dāng)?shù)膶⒅萍s的條件刪減一些，即粗化條件屬性集，這樣不僅充分考慮了確定性在粗化條件屬性集上的差異，還能較理想的對(duì)規(guī)則作出評(píng)測(cè)。

根據(jù)粒度計(jì)算的思想，提出了一種?；惴ǎ撍惴ㄒ灾R(shí)距離為準(zhǔn)則，通過(guò)粗化條件屬性集，對(duì)決策規(guī)則進(jìn)行評(píng)測(cè)。算法的步驟如下：

輸入：信息系統(tǒng)S=(U,C∪D)

輸出：S的?；疭′=(U,C′∪D)

Step1：計(jì)算U/C={Xi}i=m，0

Step2：若存在Xi→Y1，Xi→Y2,…,Xi→Yn，其中Xi∈{Xi}i=m,0

Step3：計(jì)算知識(shí)距離D(C,{cl}),cl∈C,l=1,2,…,|C|.找出最大的D(C,{cl})值及其對(duì)應(yīng)的屬性c，并將屬性c從條件屬性集C中刪除，得到?；臈l件屬性集C′；

Step4：根據(jù)新的條件屬性集C′，得到了S的?；疭′=(U,C′∪D).并重新計(jì)算U/C′={Xk}k=r，0

算法分析：

首先執(zhí)行Step1和 Step2，將條件屬性集作為一個(gè)整體去評(píng)測(cè)，如果能夠作出評(píng)測(cè)，則表明在最細(xì)粒度下可以進(jìn)行決策規(guī)則的評(píng)測(cè)。如果不能評(píng)測(cè)，則執(zhí)行Step3，以知識(shí)距離為準(zhǔn)則，計(jì)算單個(gè)條件屬性和條件屬性集這兩個(gè)知識(shí)的知識(shí)距離，從中刪減掉知識(shí)距離最大的屬性，實(shí)現(xiàn)了將條件屬性集粗?；男Ч?。根據(jù)得到的粗?；畔⑾到y(tǒng)S′，求出相應(yīng)的規(guī)則和確定度，以新的確定度對(duì)決策規(guī)則進(jìn)行評(píng)測(cè)。若粗化后的信息系統(tǒng)對(duì)決策規(guī)則還是無(wú)法進(jìn)行評(píng)測(cè)，則實(shí)行再次粗化，直至能夠?qū)Q策規(guī)則進(jìn)行評(píng)測(cè)為止。

4 實(shí)例分析

以例1為例，對(duì)新對(duì)象x10(頭疼=否，肌肉疼=否，體溫=低燒)，采用知識(shí)距離粒化的算法進(jìn)行分類。

(1)計(jì)算U/C={X1,X2,X3,X4,X5}={{x1},{x2,x3,x8},{x4,x5},{x6},{x7}}，U/D={Y1,Y2}={{x1,x2,x3,x4},{x5,x6,x7,x8}}，在例1中，對(duì)x10的分類適用的規(guī)則為r31和r32，并且μ(X3,Y1)=μ(X3,Y2).

(2)根據(jù)知識(shí)距離的定義可得：

U/SIM(C)={{x1},{x2,x3,x8},{x2,x3,x8},{x4,x5},{x4,x5},{x6},{x7},{x2,x3,x8}}

U/SIM({a1})={{x1,x2,x3,x6,x8},{x1,x2,x3,x6,x8},{x1,x2,x3,x6,x8},{x4,x5,x7},{x4,x5,x7},{x1,x2,x3,x6,x8},{x4,x5,x7},{x1,x2,x3,x6,x8}}

U/SIM({a2})={{x1,x2,x3,x8},{x1,x2,x3,x8},{x1,x2,x3,x8},{x4,x5,x6,x7},{x4,x5,x6,x7},{x4,x5,x6,x7},{x4,x5,x6,x7},{x1,x2,x3,x8}}

U/SIM({a3})={{x1,x4,x5,x6},{x2,x3,x8},{x2,x3,x8},{x1,x4,x5,x6},{x1,x4,x5,x6},{x1,x4,x5,x6},{x7},{x2,x3,x8}}

(4)計(jì)算，U/C′={X1,X2,X3,X4}={{x1},{x2,x3,x8},{x4,x5,x6},{x7}}，U/D={Y1,Y2}={{x1,x2,x3,x4},{x5,x6,x7,x8}}

r11′∶dexC(X1)→desD(Y1),μ(X1,Y1)=1;

r42′∶dexC(X4)→desD(Y2),μ(X4,Y2)=1.

(5)根據(jù)?；瘲l件屬性集的結(jié)果，對(duì)新對(duì)象x10評(píng)測(cè)的過(guò)程為：

適用的規(guī)則是r31′和r32′，由于μ(X3,Y2)>μ(X3,Y1)，所以x10屬于Y2的可能性大于Y1.

為了證明算法的可行性，另外列舉了一個(gè)例子作說(shuō)明。

例2為一個(gè)知識(shí)管理的決策表S=(U,C∪D)如表2，其中，U={x1,x2,x3,x4,x5,x6}，C={a1,a2,a3,a4},D={a5}.

根據(jù)表1得：

U/C={X1,X2,X3,X4}={{x1,x2},{x3},{x4},{x5,x6}}

U/D={Y1,Y2}={{x1,x2,x5},{x3,x4,x6}}

r11∶desC(X1)→desD(Y1),μ(X1,Y1)=1;

r22∶desC(X2)→desD(Y2),μ(X2,Y2)=1;

r32∶desC(X3)→desD(Y2),μ(X3,Y2)=1;

表2 知識(shí)管理的決策表Tab.2 The decision table of knowledge management

如對(duì)新對(duì)象x7(1，0，0，0)進(jìn)行分類，適用的規(guī)則是r41和r42，由于μ(X4,Y1)=μ(X4,Y2)，無(wú)法就x7的歸屬做出決策。因此，我們通過(guò)執(zhí)行算法來(lái)解決x7的歸屬問(wèn)題。

(1)根據(jù)知識(shí)距離的定義可得：

U/SIM(C)={{x1,x2},{x1,x2},{x3},{x4},{x5,x6},{x5,x6}};

U/SIM({a1})={{x1,x2,x5,x6},{x1,x2,x5,x6},{x3,x4},{x3,x4},{x1,x2,x5,x6},{x1,x2,x5,x6}}

U/SIM({a2})={{x1,x2,x5,x6},{x1,x2,x5,x6},{x3,x4},{x3,x4},{x1,x2,x5,x6},{x1,x2,x5,x6}}

U/SIM({a3})={{x1,x2},{x1,x2},{x3,x4,x5,x6},{x3,x4,x5,x6},{x3,x4,x5,x6},{x3,x4,x5,x6}}

U/SIM({a4})={{x1,x2,x4},{x1,x2,x4},{x3,x5,x6},{x1,x2,x4},{x3,x5,x5},{x3,x5,x6}}

(2)由D(C,{a1})=D(C,{a2})=1=0.5可知，a1,a2為知識(shí)距離最大的屬性，故刪除a1,a2得到了?；蟮男碌臈l件屬性集C′={a3,a4}.

(3)計(jì)算U/C′={X1,X2,X3}={{x1,x2},{x3,x5,x6},{x4}}，U/D={Y1,Y2}={{x1,x2,x5},{x3,x4,x6}}

r11′∶desC(X1)→desD(Y1),μ(X1,Y1)=1;

r32′∶desC(X3)→desD(Y2),μ(X3,Y2)=1.

(4)根據(jù)?；瘲l件屬性集的結(jié)果，對(duì)新對(duì)象x7評(píng)測(cè)的過(guò)程為：

適用的規(guī)則是r21′和r22′，由于μ(X2,Y2)>μ(X2,Y1)，所以x7屬于Y2的可能性大于Y1.

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

提出一種基于粒度計(jì)算思想的算法，根據(jù)知識(shí)距離實(shí)現(xiàn)對(duì)條件屬性集的粗化，通過(guò)此算法可以較好的解決決策規(guī)則的評(píng)測(cè)問(wèn)題。實(shí)例表明該算法評(píng)測(cè)效果比較理想。

參考文獻(xiàn)：

[1] 張鈴，張鈸.模糊商空間理論(模糊粒度計(jì)算方法)[J].軟件學(xué)報(bào)，2003，14(4)：770-776.

[2] 王飛躍.詞計(jì)算和語(yǔ)言動(dòng)力學(xué)系統(tǒng)的計(jì)算理論框架[J].模式識(shí)別與人工智能，2001，14(4)：377-384.

[3] 李士勇.模糊控制·神經(jīng)控制和智能控制論[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，1998.

[4] PAWLAK Z.Rough Sets-Theoretical Aspects of Reasoning about Data[M].Dordrecht，Boston，London：Kluwer Academic Publishers，1991.

[5] 張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法[M].北京：科學(xué)出版社，2001.

[6] LIANG J Y，SHI Z Z，LI D Y，et al.Information entropy，rough entropy and knowledge granulation in incomplete information systems[J].International Journal of General Systems，2006，35(6)：641-654.

[7] 曲開(kāi)社，翟巖慧，梁吉業(yè)，等.形式概念分析對(duì)粗糙集理論的表示及擴(kuò)展[J].軟件學(xué)報(bào)，2007，18(9)：2174-2182.

[8] 李道國(guó)，苗奪謙，張紅云.粒度計(jì)算的理論、模型與方法[J].復(fù)旦學(xué)報(bào)，2004，43(5)：837-841.

[9] 史琨.粗糙集的知識(shí)獲取方法研究[D].太原：山西大學(xué)，2009.