史 琨

(陽泉師范高等專科學(xué)校 山西陽泉 045200)

引言

粒度計(jì)算(Granular computing，GrC)是信息處理的一種新的概念和計(jì)算方式，它覆蓋了所有有關(guān)粒度的理論、方法、技術(shù)和工具的研究[1]，主要用于處理不確定的、模糊的、不完整的和海量的信息以及人工智能領(lǐng)域的研究.研究的模型大致有3種：基于模糊集合論的詞計(jì)民算模型、粗糙集模型和基于商空間的粒度計(jì)算模型，其中粗糙集模型中的粒度計(jì)算主要研究的問題之一就是論域?；?

1982年，由Pawlak教授提出的粗糙集理論[1]，是處理不確定的、模糊的、和不完備性問題的新型數(shù)學(xué)工具，并得到了廣泛的重視和發(fā)展[2～4].決策規(guī)則性能的評(píng)測(cè)是粗糙集研究的主要內(nèi)容之一，國內(nèi)外學(xué)者提出了許多評(píng)測(cè)指標(biāo)[5～6]，其中確定度是衡量決策規(guī)則性能的重要指標(biāo).一般情況，是將條件屬性集作為一個(gè)整體去評(píng)測(cè)決策規(guī)則的確定性，或者是利用決策規(guī)則在局部屬性集上的差異來評(píng)測(cè)規(guī)則.由于粒度計(jì)算作為一種新型的研究熱點(diǎn)已經(jīng)應(yīng)用到各個(gè)領(lǐng)域中， 如何通過粒度計(jì)算來評(píng)測(cè)決策規(guī)則成為了新的研究問題.因此，本文基于粒度計(jì)算的思想提出一種對(duì)論域?；乃惴?， 通過它來選擇適當(dāng)?shù)膶傩约?，?duì)決策規(guī)則進(jìn)行評(píng)測(cè).實(shí)例證明該方法評(píng)測(cè)效果較為理想.

1 基本概念

當(dāng)?i，jτ，i≠j?Gi∩Gj=?,則稱{Gi}iτ是論域的無重疊粒度劃分，簡記為{Gi}iτ=[U]；當(dāng)?i，jτ，i≠j?Gi∩Gj≠?,則稱{Gi}iτ是論域的一種覆蓋，簡記為{Gi}iτ=〈U〉.

定義3[1](信息粒度粗細(xì))設(shè)R是論域上關(guān)系的全體，且R1，R2R,若對(duì)?x,yU,xR1y?xR2y，則稱R1比R2細(xì)，簡記為R2

定義5[2]設(shè)S=(U,C∪D)是一個(gè)決策表，XiU/C，YjU/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是不確定的.

定義6[7]設(shè)S=(U,C∪D)是一個(gè)決策表，B?C，XiU/C，YjU/D，rij:desC(Xi)→desD(Yj)規(guī)則rij相對(duì)于局部屬性集B的確定度：

μB(Xi,Yj)=|[x]B∩Yj|/|[x]B|.

定義7[7]設(shè)S=(U,C∪D)是一個(gè)決策表，XiU/C，xXi，由Xi在局部屬性集B?C下產(chǎn)生的規(guī)則集的不確定度量定義為：

其中YiU/D，k為U/D中等價(jià)類個(gè)數(shù).

定義8[7]設(shè)S=(U,C∪D)是一個(gè)決策表，|C|=m，xXi，XiU/C，YjU/D，rij:desC(Xi)→desD(Yj)， 規(guī)則rij相對(duì)于C中n(n

μ(n)(Xi,Yj)=μBn(Xi,Yj).

2 決策規(guī)則的評(píng)測(cè)標(biāo)準(zhǔn)

下面通過舉例說明決策規(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=syggg00={感冒}.

表1 關(guān)于診斷感冒的決策表

根據(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.

評(píng)測(cè)方法1：

將條件屬性集作為一個(gè)整體去評(píng)測(cè)決策規(guī)則的確定性.如對(duì)新對(duì)象x9(頭疼=是，肌肉疼=是，體溫=高燒)進(jìn)行分類時(shí)，根據(jù)上述規(guī)則， 應(yīng)用此方法，適用的規(guī)則是r21和r22，由于μ(X2,Y1)>μ(X2,Y2)，則認(rèn)為x9屬于Y1的可能性較大.

評(píng)測(cè)方法2：

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

針對(duì)上述評(píng)測(cè)方法的討論，可以提出一種基于粒度計(jì)算的算法，通過論域?；?，使得決策規(guī)則的評(píng)測(cè)更為準(zhǔn)確.算法的步驟如下：

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

輸出：S的粗化粒度U/C(n)

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

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

Step3：計(jì)算μ{c1}(Xi,Yj),c1C,ι=1,2,…,|C|,Yj?U/D.找出最小的E{c1}(Xi)值及其對(duì)應(yīng)的屬性c；

Step4：令C′=?，若μ{c1}(Xi,Y1)=μ{c1}(Xi,Y2)=…=μ{c1}(Xi,Yn)，c1C，ι=1,2,…,|C|,，則C′=C′∪{c1}；

Step5：根據(jù)C′′=C-C′-{c}={cK}，0≤k≤|C|-1,則U/C(n)=U/{Rc}，?R?C′′.

算法分析：

首先執(zhí)行Step1和Step2，根據(jù)評(píng)測(cè)方法一，先將條件屬性集作為一個(gè)整體去評(píng)測(cè)，如果能夠作出評(píng)測(cè)， 則表明論域作為最細(xì)粒度可以進(jìn)行決策規(guī)則的評(píng)測(cè).如果不能評(píng)測(cè)，則執(zhí)行Step3，借鑒評(píng)測(cè)方法二，將論域這個(gè)粒度適當(dāng)變粗，主要是找尋到最具有區(qū)分能力的單個(gè)屬性，也就是最小的不確定度值對(duì)應(yīng)的屬性.再根據(jù)求出的μ{c1}值篩選出不具有區(qū)分能力的屬性.由于C′′中包含的屬性ck比屬性c的區(qū)分能力小，但同樣具有一定的區(qū)分能力，所以，C′′中的任意屬性集和屬性c構(gòu)成的集合都將論域這個(gè)粒度變粗了，都能夠?qū)Q策規(guī)則作出評(píng)測(cè).

4 實(shí)例分析

以例1為例，對(duì)新對(duì)象x10(頭疼=否，肌肉疼=否，體溫=低燒)，采用論域?；乃惴ㄟM(jìn)行分類.

⑴計(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).

⑷因?yàn)镃′′=C-C′-{c}={a1}，則U/C(1)={a1,a2} ，U/C(2)={a2} .

⑸根據(jù)上述可得論域的兩種粗化結(jié)果，分別對(duì)新對(duì)象x10進(jìn)行評(píng)測(cè)， 評(píng)測(cè)過程如下：

當(dāng)U/{a2}={{x1,x2,x3,x8},{x4,x5,x6,x7}}時(shí)，

所以x10屬于Y2的可能性大于Y1.

當(dāng)U/{a2}={{x1,x2,x3,x8},{x4,x5,x6,x7}}時(shí)，

所以x10屬于Y2的可能性大于Y1.

⑹綜上，x10屬于Y2的可能性大于Y1.

5 結(jié)語

本文提出一種基于粒度計(jì)算的論域?；乃惴?，可以對(duì)決策規(guī)則作出較好的評(píng)測(cè). 此算法既克服了傳統(tǒng)確定度的局限性， 又考慮了局部屬性集的評(píng)測(cè)準(zhǔn)確性. 通過實(shí)例表明該算法評(píng)測(cè)效果較好.

參考文獻(xiàn)：

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

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

[3]J Y Liang，Z Z Shi， D Y Li ，et al. Information entropy，rough entropy and knowledge granulation in incomplete information systems[J].International Journal of General Systems，2006，35(6)：641.

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

[5]I Duntsch，G Gediaga. Uncertainty measures of rough set prediction[J].Artificial Intelligence，1998，106(1)： 109.

[5]Y H Qian， J Y Liang，D Y Li，et al. Measures for evaluating the decision performance of a decision table in rough set theory [J]. Information Sciences，2008，178(1)：181.

[5]史琨，曲開社，翟巖慧.一種基于局部屬性集的規(guī)則確定度[J].計(jì)算機(jī)應(yīng)用，2008，28(11)：2970.