决策系统中约简的不一致分析

邓大勇

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

0 引 言

粗糙集理论是一种处理不完全、不精确、不一致数据的有效数学工具[1-9].自20世纪80年代初Pawlak教授创立粗糙集理论以来，粗糙集理论在数据挖掘、机器学习、模式识别、人工智能等领域有着非常广泛的应用.其理论发展很快，到目前为止已创立了很多种类的粗糙集扩展模型，主要包括：可变精度粗糙集、概率粗糙集、贝叶斯粗糙集、S粗糙集、占优关系粗糙集、特征关系粗糙集、相容或相似关系粗糙集、粗糙模糊集和模糊粗糙集等[1-11].

众多的粗糙集理论都应用于分类，上近似、下近似等概念是其核心的内容，数据约简是它们最主要的应用.大部分粗糙集方法都只对正区域内的个体进行分类，对负区域和边界区域的个体则是通过转化为其他决策或知识的正区域来处理.数据约简一般都是保持正区域，而忽略其他区域.

但是,粗糙集的约简对数据本身有多大的影响呢？对此类问题的研究还未见相关报道.本文应用3种常用的粗糙集模型，对决策系统中的不一致程度进行了分析.在Pawlak粗糙集、一般决策粗糙集和可变精度粗糙集下，对约简前后决策系统的分类率、未分类率、分类正确率以及决策表的不一致层次等方面进行了比较，从而说明这3种粗糙集模型下的数据约简对数据本身的影响.讨论结果对粗糙集理论的应用和发展具有一定的指导作用，主要体现在应用和研究中如何选择粗糙集及控制分类的精度等方面.

1 决策系统

设DS=(U,A,D)是一个决策系统(或决策表)，其中U是非空有限的个体集合，称为论域，A是非空的条件属性集，D是决策属性集.在决策表DS中,属性集A的属性个数有多个，而决策属性集中的属性个数只有1个，记为d.本文讨论的正是这种情况.

对∀a∈A∪{d}，存在一个对应的a:U→Va，Va是属性a的值域.任意的属性子集合B⊆A∪{d}确定了如下一个不可区分关系IND(B):

IND(B)={(x,y)∈U×U|a∈B∧a(x)=a(y)}.

IND(B)是一个等价关系，它对U的划分记为U/IND(B)或简记为U/B.相对于B的包含x的等价类记为IB(x)或[x]B，即IB(x)=[x]B={y∈U| (x,y)∈IND(B)}.于是

U/A={Xj,j=1,2,…,m}={[x]A|x∈U},Xi≠Xj(i≠j);

U/{d}={Yj,j=1,2,…,p}={[x]d|x∈U},Yi≠Yj(i≠j).

函数∂B:U→P(Vd)(P(Vd)表示Vd的幂集,B⊆A)定义为∂B(x)={d(y) |y∈[x]B}.其中，∂B称为DS中的一般决策.如果对所有的x∈U都有card(∂A(x))=1，则DS是一致的，否则DS不一致.其中card(5)表示集合的势.

2 不一致的层次

在粗糙集理论中，决策系统可分为一致决策系统和不一致决策系统，不一致的决策系统还缺少一个对不一致程度进行度量的指标.下面就引入这个指标.

当W=U时，LI(U)称为决策系统DS的不一致层次.

当个体的不一致层次为1时，对于这个个体的决策是一致的;当个体的不一致层次大于1时，对于该个体的决策是不一致的.同样，当决策系统的不一致层次等于1时，整个决策系统是一致的;当决策系统的不一致层次大于1时，该决策系统存在不一致.不一致的层次越高，不一致的程度越高.根据定义1，很容易得到下面几个命题：

命题1在决策系统DS=(U,A,d)中，对∀y∈[x]A，都有LI(y)=LI(x).

命题2在决策系统DS=(U,A,d)中，个体和整个决策系统的不一致层次随着条件属性个数的减少而单调递增.

命题3在决策系统DS=(U,A,d)中，不一致的最大层次小于等于card(Vd).

不一致层次可以刻画决策系统中个体和整个决策表的不一致程度.粗糙集理论是一种处理不完全、不精确、不一致数据的数学工具，而且是一种用于分类的数学工具,这就有必要从分类的角度对粗糙集理论进行分析.通常是用分类率、未分类率、分类正确率等指标对分类理论或分类算法进行考核.分类率是指能够被分类的数据占整个数据的比率；分类正确率是指被分类的数据中正确分类的数据的比率；未分类率是指不能分类的数据在整个数据中所占的比率.在粗糙集理论中，往往只能对正区域中的数据进行分类，在Pawlak粗糙集中，正区域的数据是能够分类而且能正确分类，在其他形式的粗糙集模型中，正区域的数据虽然能够分类，但不一定能正确分类.下面将对几种粗糙集下决策系统中分类率、未分类率、分类正确率以及不一致层次在约简前后进行对比分析.

3 不一致的Pawlak粗糙集分析

在决策系统DS=(U,A,d)中，B⊆A，Y⊆U，在Pawkak粗糙集下，下、上近似分别定义为:

⊆

Pawlak粗糙集的属性约简定义如下：

定义2在决策系统DS=(U,A,d)中,称B⊆A是一个约简，当且仅当B满足下面2个条件：

1)POSB(d)=POSA(d)；2)对∀a∈B,都有POSB-{a}(d)≠POSA(d).

根据定义2知，Pawlak粗糙集的属性约简是一种保持正区域的约简，约简后的正区域、边界区域和负区域与约简前的正区域、边界区域和负区域分别保持相等，从而在Pawlak粗糙集的属性约简作用下，决策系统的分类率、未分类率以及分类正确率保持不变.但是,对于决策表中个体以及整个决策表的不一致层次却不一样.经过属性约简,个体和整个决策表的不一致层次会产生变化，命题4正是刻画决策表经过Pawlak约简之后不一致层次的变化规律.

命题4决策表经过Pawlak粗糙集的属性约简之后，正区域部分的个体的不一致层次保持不变，边界区域的个体的不一致层次随着属性的减少而单调递增,从而决策表经过Pawlak粗糙集的属性约简之后，正区域部分的不一致层次不变，边界区域的不一致层次随着属性的减少而单调递增(证明略).

4 不一致的一般决策分析

在不一致决策系统中，非常少的约简算法得到的约简是Pawlak粗糙集约简，大部分约简算法都不是Pawlak粗糙集约简.一般决策在一般情况下不被认为是一种单独的粗糙集模型，但由于和Skowron差别矩阵有关的约简算法(包括差别矩阵约简算法和遗传算法的约简算法等)所得到的约简一般情况下都是一般决策约简[8]，所以本文将它看成是一个独立的粗糙集模型.

个体的一般决策约简是指在决策系统中该个体保持一般决策不变的最小属性子集;决策系统的一般决策约简是指决策系统中的每个个体都保持一般决策不变的最小属性子集.

命题5决策系统经过一般决策约简之后，决策系统中的任何个体的不一致层次都保持不变，从而整个决策表的不一致层次保持不变.

5 不一致的可变精度粗糙集分析

现实的数据是存在噪音的，可变精度粗糙集模型正是基于这点建立的.可变精度粗糙集模型共有3种类型:1种为参数不对称的可变精度粗糙集模型;2种为参数对称的可变精度粗糙集模型.在2种参数对称的可变精度粗糙集模型中，一种模型中的参数β表示错误率，另一种模型中的参数β表示正确率[12-15].这里仅研究后一种情形.

定义6给定论域U，不可区分关系B⊆U×U，Y⊆U，β∈(0.5,1]，则

分别称为Y在B下的β下近似和Y在B下的β上近似.Y在B下的β下近似也称为Y在B下的β正区域，记为POS(B,Y,β)；BND(B,Y,β)=Bβ(Y)-Bβ(Y)称为Y在B下的β边界区域，NEG(B,Y,β)=U-Bβ(Y)称为Y在B下的β负区域.

从以上的分析容易得到，在决策系统DS=(U,A,d)中分类率随着β的增大而减小，分类正确率随β的增大而增大，未分类率随β的增大而增大.当β=H(DS)>0.5时，β正区域POS(A,d,β)=U，β边界区域和β负区域都等于φ.

定义7对于决策系统DS=(U,A,d)，给定β，称B⊆A是条件属性集A关于决策属性d的β约简，当且仅当B满足下面2个条件：

1)γ(A,d,β)=γ(B,d,β)；2)任何B的真子集都不满足条件1).

在决策系统DS=(U,A,d)中，给定参数β，经过可变精度粗糙集约简之后，可能出现决策异常的问题[5,16]，从而决策系统中不论是β正区域部分还是其他部分，都有可能出现不一致的层次增加的现象，这就会导致分类正确率的下降，此时的分类正确率的下限是β.

命题6在可变精度粗糙集参数为β(0.5,1] 的属性约简过程中，决策系统中在β正区域、β边界区域和β负区域中的个体的不一致层次都随属性的减少而单调增加，从而整个决策系统的不一致层次随属性的减少而单调增加(证明略).

通过以上的分析可以得到该3种粗糙集模型下属性约简对决策表的影响.将该3种粗糙集约简前后的分类率、分类正确率、未分类率、不一致的层次变化作一比较，结果如表1所示.在表1中,()内的数据或文字表示约简后的相应指标值，()上面的数值表示约简前相应指标的数值.

表1 决策表中约简前后4种指标的比较

从表1可以看出，和其他2种粗糙集相比，Pawlak粗糙集的分类率比较小，未分类率比较大，分类正确率是1，这3个指标在约简前后不发生变化，不一致层次在约简后有可能增加；在一般决策下，分类率为1，未分类率为0，但是分类正确率比较小，约简前后的4种指标都不发生变化，也就是说，一般决策约简对这4个指标不产生影响；在可变精度粗糙集下，约简使得分类正确率有所下降，不一致层次有所上升，分类率和未分类率在约简前后不变.

表2 决策表DS

6 应用举例

表2是一个决策表DS=(U,A,d)，其中A={a,b,c}是条件属性，d为决策属性.决策表DS的4种指标的对比结果如表3所示.从表3可以看出，在Pawlak粗糙集下，约简前后，分类率、未分类率和分类正确率都不发生变化，但是不一致的层次在约简前后发生了变化，约简后的不一致层次增大了；在一般决策下，约简前后4种指标都不变；在可变精度粗糙集下，从表3可以看出，约简后只有不一致的层次增大了，而分类率、分类正确率以及未分类率都没有变化，这是因为决策表DS在β等于0.8和0.9的情况下都没有发生决策异常的现象，当β减小到一定的程度时，一旦发生决策异常，决策表的分类正确率在约简前后将会发生变化，约简后的分类正确率小于约简前的分类正确率.从表3还可以看出，β越大，分类正确率越大，分类率越小;反之，β越小,分类率越大，分类正确率越小.所以，在进行数据处理时要根据实际需要选择适当的粗糙集模型.

表3 决策表DS的4种指标的比较

7 结 论

定义了决策系统中的不一致层次的概念，用来刻画决策系统的不一致程度.通过分析3种粗糙集模型在约简前后正区域、负区域和边界区域的变化，比较了3种粗糙集模型在约简前后的分类率、未分类率、分类正确率以及不一致的层次的变化，所得结果对实际应用中选择何种粗糙集理论具有指导意义.

参考文献：

[1]Pawlak Z.Rough Sets—Theoretical Aspect of Reasoning about Data[M].Dordrecht:Kluwer Academic Publishers,1991.

[2]张文修，吴伟志，梁吉业，等.粗糙集理论与方法[M].北京：科学出版社，2001.

[3]王国胤.Rough集理论与知识获取[M].西安：西安交通大学出版社，2001.

[4]刘清.Rough集及Rough推理[M].北京：科学出版社,2001.

[5]王加阳.面向海量数据的粗糙集理论与方法研究[D].长沙：中南大学，2005.

[6]王基一，林仁炳.模糊粗糙集粗糙熵的修正[J].浙江师范大学学报:自然科学版，2006，29(4):394-397.

[7]邓大勇，黄厚宽，李向军.不一致决策系统中约简之间的比较[J].电子学报,2007,35(2):252-255.

[8]邓大勇.基于粗糙集的数据约简及粗糙集扩展模型的研究[D].北京：北京交通大学，2007.

[9]苗夺谦,王国胤,刘清,等.粒计算：过去、现在与展望[M].北京：科学出版社，2007.

[10]Kryszkiewicz M.Comparative Studies of Alternative Type of Knowledge Reduction in Inconsistent Systems[J].International Journal of Intelligent Systems,2001,16(1):105-120.

[11]Dubois D,Prade H.Rough fuzzy sets and fuzzy rough sets[J].International Journal of General Systems,1990,17(2/3):191-209.

[12]Slezak D,Ziarko W.The investigation of the bayesian rough set model[J].International Journal of Approximate Reasoning,2005,40(1/2):81-91.

[13]Ziarko W.Variable precision rough sets model[J].Journal of Computer and System Sciences,1993,46(1):39-59.

[14]Katzberg J D,Ziarko W.Variable precision extension of rough set[J].Foundamenta Informaticae,1996,27(2/3):155-168.

[15]An A,Shan N,Chan C,et al.Discovering rules for water demand prediction:An enhanced rough-set approach[J].Engineering Application and Artificial Intelligence,1996,9(6):645-653.

[16]Kryszkiewicz M.Maintenance of Reducts in the Variable Precise Rough Sets Model[C]//ICS Research Report.Warsaw:Warsaw University of Technology,1994:31-94.