基于粒度计算的决策规则评测

史 琨

(阳泉师范高等专科学校 山西阳泉 045200)

引言

粒度计算(Granular computing，GrC)是信息处理的一种新的概念和计算方式，它覆盖了所有有关粒度的理论、方法、技术和工具的研究[1]，主要用于处理不确定的、模糊的、不完整的和海量的信息以及人工智能领域的研究.研究的模型大致有3种：基于模糊集合论的词计民算模型、粗糙集模型和基于商空间的粒度计算模型，其中粗糙集模型中的粒度计算主要研究的问题之一就是论域粒化.

1982年，由Pawlak教授提出的粗糙集理论[1]，是处理不确定的、模糊的、和不完备性问题的新型数学工具，并得到了广泛的重视和发展[2～4].决策规则性能的评测是粗糙集研究的主要内容之一，国内外学者提出了许多评测指标[5～6]，其中确定度是衡量决策规则性能的重要指标.一般情况，是将条件属性集作为一个整体去评测决策规则的确定性，或者是利用决策规则在局部属性集上的差异来评测规则.由于粒度计算作为一种新型的研究热点已经应用到各个领域中， 如何通过粒度计算来评测决策规则成为了新的研究问题.因此，本文基于粒度计算的思想提出一种对论域粒化的算法， 通过它来选择适当的属性集，对决策规则进行评测.实例证明该方法评测效果较为理想.

1 基本概念

当∀i，jτ，i≠j⟹Gi∩Gj=Ø,则称{Gi}iτ是论域的无重叠粒度划分，简记为{Gi}iτ=[U]；当∃i，jτ，i≠j⟹Gi∩Gj≠Ø,则称{Gi}iτ是论域的一种覆盖，简记为{Gi}iτ=〈U〉.

定义3[1](信息粒度粗细)设R是论域上关系的全体，且R1，R2R,若对∀x,yU,xR1y⟹xR2y，则称R1比R2细，简记为R2

定义5[2]设S=(U,C∪D)是一个决策表，XiU/C，YjU/D，desc(Xi)是Xi在C下的唯一描述，desD(Yj)是Yj在D下的唯一描述.决策规则定义如下：

rij:desc(Xi)→desD(Yj)，Xi∩Yj=Ø，

决策规则rij的确定度μ(Xi,Yj)=|Xi∩Yj|/|Xi|，0<μ(Xi,Yj)≤1.

当μ(Xi,Yj)=1时，rij是确定的； 当0<μ(Xi,Yj)<1时，rij是不确定的.

定义6[7]设S=(U,C∪D)是一个决策表，B⊆C，XiU/C，YjU/D，rij:desC(Xi)→desD(Yj)规则rij相对于局部属性集B的确定度：

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

定义7[7]设S=(U,C∪D)是一个决策表，XiU/C，xXi，由Xi在局部属性集B⊆C下产生的规则集的不确定度量定义为：

其中YiU/D，k为U/D中等价类个数.

定义8[7]设S=(U,C∪D)是一个决策表，|C|=m，xXi，XiU/C，YjU/D，rij:desC(Xi)→desD(Yj)， 规则rij相对于C中n(n

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

2 决策规则的评测标准

下面通过举例说明决策规则的评测标准.

例1 关于诊断感冒的决策表S=(U,C∪D)如表1所示，其中U={x1,x2,x3,x4,x5,x6,x7,x8}，C={a1,a2,a3}={头疼，肌肉疼，体温}，D={d}={感冒}.

表1 关于诊断感冒的决策表

根据表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.

评测方法1：

将条件属性集作为一个整体去评测决策规则的确定性.如对新对象x9(头疼=是，肌肉疼=是，体温=高烧)进行分类时，根据上述规则， 应用此方法，适用的规则是r21和r22，由于μ(X2,Y1)>μ(X2,Y2)，则认为x9属于Y1的可能性较大.

评测方法2：

3 决策规则的评测算法

针对上述评测方法的讨论，可以提出一种基于粒度计算的算法，通过论域粒化，使得决策规则的评测更为准确.算法的步骤如下：

输入：信息系统S=(U,C∪D)

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

Step1：计算U/C={Xi}i=m，0

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

Step3：计算μ{c1}(Xi,Yj),c1C,ι=1,2,…,|C|,Yj⊆U/D.找出最小的E{c1}(Xi)值及其对应的属性c；

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

Step5：根据C′′=C-C′-{c}={cK}，0≤k≤|C|-1,则U/C(n)=U/{Rc}，∀R⊆C′′.

算法分析：

首先执行Step1和Step2，根据评测方法一，先将条件属性集作为一个整体去评测，如果能够作出评测， 则表明论域作为最细粒度可以进行决策规则的评测.如果不能评测，则执行Step3，借鉴评测方法二，将论域这个粒度适当变粗，主要是找寻到最具有区分能力的单个属性，也就是最小的不确定度值对应的属性.再根据求出的μ{c1}值筛选出不具有区分能力的属性.由于C′′中包含的属性ck比属性c的区分能力小，但同样具有一定的区分能力，所以，C′′中的任意属性集和属性c构成的集合都将论域这个粒度变粗了，都能够对决策规则作出评测.

4 实例分析

以例1为例，对新对象x10(头疼=否，肌肉疼=否，体温=低烧)，采用论域粒化的算法进行分类.

⑴计算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中，对x10的分类适用的规则为r31和r32，并且μ(X3,Y1)=μ(X3,Y2).

⑷因为C′′=C-C′-{c}={a1}，则U/C(1)={a1,a2} ，U/C(2)={a2} .

⑸根据上述可得论域的两种粗化结果，分别对新对象x10进行评测， 评测过程如下：

当U/{a2}={{x1,x2,x3,x8},{x4,x5,x6,x7}}时，

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

当U/{a2}={{x1,x2,x3,x8},{x4,x5,x6,x7}}时，

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

⑹综上，x10属于Y2的可能性大于Y1.

5 结语

本文提出一种基于粒度计算的论域粒化的算法，可以对决策规则作出较好的评测. 此算法既克服了传统确定度的局限性， 又考虑了局部属性集的评测准确性. 通过实例表明该算法评测效果较好.

参考文献：

[1]李道国，苗夺谦，张红云.粒度计算的理论、模型与方法[J].复旦学报，2004，43(5)：837.

[2]张文修，吴伟志，梁吉业，等.粗糙集理论与方法[M].北京：科学出版社，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]曲开社，翟岩慧，梁吉业，等.形式概念分析对粗糙集理论的表示及扩展[J].软件学报，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]史琨，曲开社，翟岩慧.一种基于局部属性集的规则确定度[J].计算机应用，2008，28(11)：2970.