2. 计算智能重庆市重点实验室(重庆邮电大学), 重庆 400065
2. Chongqing Key Laboratory of Computational Intelligence (Chongqing University of Posts and Telecommunications), Chongqing 400065, China
粗糙集理论[1]是由波兰数学家Pawlak于1982年提出来的.它是一种处理不确定性问题的数学工具.属性约简是粗糙集理论中的核心问题之一.通过属性约简可以减少数据冗余,从而简化决策规则.一般说来,属性约简可以理解为保持给定决策表某种性质不变的最小属性集合[2].目前,粗糙集理论已被成功应用于决策支持、机器学习、数据挖掘、图像处理等众多研究领域[3,4,5].
经典粗糙集理论在模拟人类智能对模糊和不确定性概念进行处理时缺乏容错能力,泛化能力不强.为了解决这个问题,学者们通过在经典粗糙集模型中引入概率包含关系提出了许多概率粗糙集模型,其中具有代表性的有决策粗糙集模型DTRS(decision-theoretic rough set model)[6]、0.5概率粗糙集模型[7]、变精度粗糙集模型VPRS(variable precision rough set model)[8]和贝叶斯粗糙集模型BRS(Bayesian rough set model)[9]等.
基于概率粗糙集模型的属性约简问题已经取得了很多成果.例如,Inuiguchi[10]讨论了变精度粗糙集中几种属性约简方法的关系,并强调了分析变精度粗糙集和经典粗糙集属性约简的不同之处;Mi等人[11]基于变精度粗糙集提出了b下近似分布约简和b上近似分布约简的概念,并通过可辨识矩阵提供了计算b下近似分布约简和b上近似分布约简的方法;Slezak和Ziarko[9]提出了Bayesian粗糙集模型,通过用概率增益函数来评估Bayesian粗糙集模型的分类质量,给出了该模型下的属性约简计算方法;Zhou和Miao[12]研究了变精度粗糙集中b区间属性约简,提出了b区间核的概念,通过建立有序可辨识矩阵构造了获得b区间约简的启发式算法;Yao和Zhao[2]系统地阐述了决策粗糙集下的属性约简理论,并在研究了决策区域和决策规则的单调性以及规则的覆盖度、信任度和决策风险等各种评价标准的基础上提出了一种泛化属性约简;Jia等人[13]提出了一种决策风险最小化的属性约简方法,并设计了计算决策风险最小化属性约简的启发式算法、模拟退火算法和遗传算法.
与其他概率粗糙集模型相比,决策粗糙集通过引入贝叶斯决策步骤,给出了用于确定正域、边界域和负域阈值的方法.在决策论框架下,所需要的阈值可以通过具体问题的损失函数来计算.Yao等人[14]进一步分析了决策粗糙集和其他概率粗糙集之间的关系,并指出:通过设置不同的损失函数,可以推导出已有的几种概率粗糙集模型;同时,Yao[15]从语义角度出发,研究了粗糙集3个域在概率意义下的语义解释,即在决策粗糙集中,正域所获得的规则表示接受决策,边界域所获得的规则表示延迟决策,而负域所获得的规则表示拒绝决策.因此,决策粗糙集为概率粗糙集提供了一个统一的理论框架.
目前,关于决策粗糙集理论与应用的研究受到越来越多的关注并且取得了很多研究成果.例如,Li和Zhou[16]根据不同决策者不同的风险偏好,给出了基于决策粗糙集的乐观决策、悲观决策与中立决策的多角度决策模型;Herbert和Yao[17]提出了博弈论粗糙集,并将其应用到决策粗糙集中代价损失函数的确定中,为最优概率阈值的选定提供了一条新的途径;Yu等人[18]提出了基于决策粗糙集的自动聚类方法,将决策粗糙集中的风险函数用于对聚类过程进行评估,以此来指导子类的合并过程;Zhou等人[19]通过考虑不同的误分类代价,提出了多类决策粗糙集模型,并将其应用到代价敏感分类中;Qian等人[20]通过结合决策粗糙集与多个二元关系诱导的粒结构,提出了多粒度决策粗糙集模型,为多粒度粗糙集模型提供了统一的理论框架.
在决策粗糙集中,根据不同的标准,属性约简的定义主要包括正域或非负域(本文后面统称为决策域)的定量与定性保持约简[13, 21]、正域最大化属性约简[21]以及决策风险最小化属性约简[13]等.然而,由于在决策粗糙集中,决策域的确定引入了一对阈值,当属性减少时,正域或者非负域有可能变大、变小或者不变[21].也就是说,经典粗糙集中,决策域关于属性集合包含之间的单调性不再成立,这就使得决策域的定性等价与定量等价并不相等.因此导致在决策域的定量保持属性约简之后,决策域可能被改变;决策域的定性保持约简虽然不改变整个决策表的决策域,但是它并不能保证不改变每一个决策类的决策域.而正域最大化属性约简在可解释性上存在一定的困难,因为决策域的定义带有一定的不确定性.相比之下,决策风险最小化属性约简虽然更客观,但是它也有可能改变决策域.然而,用户通常并不希望改变决策域,属性约简的目的只是为了减少冗余,引入概率阈值的目的是为了增强分类能力,而不是改变决策域.
因此,为了不改变决策域,第2节将提出(a,b)正域分布保持约简和(a,b)非负域分布保持约简的定义.与前文提到的几种属性约简定义[13, 21]相比,决策域分布保持约简不改变每个决策类的决策域.第5节也将通过实验比较几种定义所获得约简的分类正确率与误分类代价,说明决策域分布保持约简是一种更好的选择.
另一方面,由于概率粗糙集中决策域与属性的增减之间并不存在单调性,为了获得约简,必须检查整个属性集合的所有子集,这为算法设计带来了很大的困难.为了有效降低算法设计的难度,具有单调性的启发式函数是必要的.值得注意的是,在概率粗糙集的相关研究中,并没有单调的度量函数用于属性约简,因此,大多数启发式算法实际上找到的可能是一个约简的超集(包含一个约简的属性集合).
因此,第3节将提出两种决策域分布条件信息量:(a,b)正域分布条件信息量和(a,b)非负域分布条件信息量,并证明其单调性.它们分别被用作计算(a,b)正域分布保持约简和(a,b)非负域分布保持约简的启发式信息.在此基础上将给出两种决策域分布保持约简核属性的定义以及求核算法.
给定一个决策表,通常存在多个约简,为了得到简洁而有效的决策规则,获得最小约简非常重要,而获取最小约简已被证明是一个NP-hard问题[22].目前,属性约简算法主要有两种[23]:一种是启发式的贪心算法,另一种是基于种群的随机优化方法.前者速度较快,但是通常只能找到约简而不是最小约简;后者比起前者找到最小约简的概率更大.在基于种群的随机优化方法中,通常将最小约简问题转化为组合优化问题.因此,设计合适的适应度函数非常关键.然而,这些研究大多是在经典粗糙集下进行的,在决策粗糙集中,由于决策域与属性增减之间的非单调性,在该模型下的属性约简与经典粗糙集模型下的属性约简相比具有较大的差异性[21].因此,我们有必要研究决策粗糙集模型下的最小属性约简问题.
本文第4节将讨论基于决策域分布保持的最小约简问题.首先,将最小约简问题转化为约束优化问题.考虑到遗传算法[24]在求解最小约简问题时的优良表现,本文提出基于遗传算法的正域分布保持约简算法以及非负域分布保持约简算法.适应度函数的最优值是否能够描述最优解,是算法成功与否的关键.理论分析说明,本文提出的适应度函数能够保证将最小约简问题转换为适应度函数最大化问题.此外,为了确保遗传算法能够搜索到决策域分布保持约简,在遗传算法中加入修正算子.修正算子通过第3节定义的两种决策域分布条件信息量,将决策域分布保持约简的超集转换为决策域分布保持约简.决策域分布条件信息量的单调性也保证了修正算子的正确性.第5节给出的在UCI数据集[25]上的实验结果验证了遗传算法找到最小约简的有效性.
1 决策粗糙集模型一个决策表表示为一个四元组:S=(U,At=CÈD,{Va|aÎAt},{Ia|aÎAt}),其中,U={x1,x2,…,xn}是非空有限对象集,C是条件属性集,D是决策属性集,CÇD=Æ,Va是属性aÎAt的值的非空集合,Ia:U®Va是一个信息函数,它指定U中每个对象的属性值.一般来说,V和I可省略,决策表简记为S=(U,At=CÈD).
给定一个决策表S=(U,At=CÈD),BÍAt,不可分辨关系定义为
IND(B)={(x,y)ÎUxU:Ia(x)=Ia(y),"aÎB}.
IND(B)是U上的一个等价关系,它形成U的一个划分,记为U/IND(B).给定一个对象xÎU,[x]B表示包含x的B等价类,即,[x]B={yÎU:(x,y)ÎIND(B)}.
给定一个对象x,假设状态集W={D1,D2,…,Dm}由m个决策类构成.m类分类问题可以转换成m个两类分类问题.具体而言,对第j个决策类Dj,j=1,2,…,m,其状态集可表示为Wj={Dj,ØDj},分别表示对象是否属于决策类Dj,如果对象x通过等价类[x]B刻画,则对象x属于Dj和不属于Dj的条件概率分别为和P(ØDj|[x]B)=1-P(Dj|[x]B).给定行为集,其中,分别表示将对象分类到正域POS(Dj)、边界域BND(Dj)和负域NEG(Dj)的3种行为.损失函数可由如下矩阵表示:
.
在该矩阵中,和表示当一个对象属于Dj时采取行为和引起的损失;和表示当一个对象不属于Dj时采取行为和引起的损失.
给定一个对象关于属性B的等价类[x]B,则采取3种行为的期望损失分别表示为
根据最小风险贝叶斯决策准则,可以得到如下形式的决策规则:
(P) If and decide xÎPOS(Dj);
(B) If and decide xÎBND(Dj);
(N) If and decide xÎNEG(Dj).
因为P(Dj|[x]B)+P(ØDj|[x]B)=1,考虑一组特殊的损失函数:
(c1)
该损失函数表示:将一个属于Dj的对象分类到Dj正域POS(Dj)的损失小于等于将它分类到Dj边界域BND(Dj)的损失,并且这两种损失都小于将它分类到Dj负域NEG(Dj)的损失;反之,将一个不属于Dj的对象分类到Dj负域NEG(Dj)的损失小于等于将它分类到Dj边界域BND(Dj)的损失,并且这两种损失都小于将它分类到Dj正域POS(Dj)的损失.在条件(c1)下,决策规则(P)~规则(N)可以简化为:
(P1) If P(Dj|[x]B)≥aj and P(Dj|[x]B)≥gj, decide xÎPOS(Dj);
(B1) If P(Dj|[x]B)≤aj and P(Dj|[x]B)≥bj, decide xÎBND(Dj);
(N1) If P(Dj|[x]B)≤bj and P(Dj|[x]B)≤gj, decide xÎNEG(Dj).
其中,参数aj,bj和gj可表示为
(1)
此外,对于边界区域,规则(B1)的条件表明aj>bj.因此,我们得到条件(c2):
(c2)
条件(c1)和条件(c2)说明1≥aj>gj>bj≥0.在这种情况下,经过权衡,决策规则(P1)~规则(N1)可进一步简化为:
(P2) If P(Dj|[x]B)≥aj,decide xÎPOS(Dj);
(B2) If bj<P(Dj|[x]B)<aj,decide xÎBND(Dj);
(N2) If P(Dj|[x]B)≤bj,decide xÎNEG(Dj).
参数gj不再需要,规则(P2)、规则(B2)和规则(N2)保证每个对象只被分类到一个区域.
根据规则(P2)、规则(B2)和规则(N2),(aj,bj)-正域、(aj,bj)-边界域和(aj,bj)-负域分别定义为
(2)
正域和边界域的并称为非负域,记为.
在接下来的论述中,我们记a=(a1,a2,…,am),b=(b1,b2,…,bm),决策属性D导出的划分为pD={D1,D2,…,Dm}.为了简化讨论与描述,假设每一个决策类具有同样的损失函数,即,对于任意DjÎpD,有:
2 基于决策域分布保持的属性约简
在这一节,首先分析了决策粗糙集中属性约简面临决策域变化的问题.为了解决这个问题,本文随后提出了决策域分布保持约简的概念.
2.1 存在的问题在粗糙集理论中,一个约简可以理解为保持给定决策表某种性质不变的最小属性集合,其定义如下:
定义1[27]. 给定一个决策表S=(U,At=CÈD),BÍC,用r来表示决策表的某种性质,则称B是保持性质r的C的一个约简,当且仅当满足以下条件:
(Ⅰ) B和C具有同样的性质r;
(Ⅱ) 对于"bÎB,B-{b}不满足性质r.
在定义1中,条件(Ⅰ)被称为充分条件,条件(Ⅱ)被称为必要条件.
在经典粗糙集模型中,根据不同的标准,性质r通常可以替换为决策表的正域[1]、分类质量[1]和条件信息熵[28]等.在概率粗糙集模型中,性质r通常被替换为决策划分pD的正域或者非负域的定量与定性标准,其中,决策划分的正域与非负域定义如下:
定义2. 给定一个决策表S=(U,At=CÈD),BÍC,则决策划分pD的正域和非负域分别定义为
(3)
为了简化,在接下来的讨论中我们只讨论正域,对于非负域有类似的结果.正如文献[21]所指出的:由于正域关于属性集合包含之间的单调性并不成立,因此,正域的定量等价()并不意味着它们的定性等价即并不意味着这就导致当用或者替换定义1中的性质r时,得到的约简结果有可能不相同.而在经典粗糙集中,因为正域与属性之间的单调性成立,这两种约简定义是等价的.
因此,在决策粗糙集中,当属性减少时,正域或者非负域有可能变大、变小或者不变[21].针对这个特点,Yao和Zhao[2]提出了一种属性约简的泛化定义,即一个约简可以理解为满足给定决策表某种性质的最小属性集合.其形式化的定义如下:
定义3[2]. 给定一个决策表S=(U,At=CÈD),BÍC,用一个度量集合E={e1,e2,…}来表示决策表的某种性质,则称B是和决策属性D相关的C的一个约简,当且仅当满足以下条件:
(Ⅰ) 对于所有eÎE,e(pD|pB)±e(pD|pC);
(Ⅱ) 对于"AÌB,有:对于所有eÎE,e(pD|pB)±e(pD|pC)不成立.
在这个定义中,对于给定的某种性质,可用一个度量来表示.该度量定义为从条件属性集的幂集2C到一个偏序集合L的映射,即e:2C®(L,±),其中,±是满足自反性、非对称性和传递性的偏序关系.
根据定义3,可以将已有的一些属性约简表示出来.例如,针对决策域的非单调,Zhao等人[21]将决策粗糙集中的属性约简理解为一种全局优化问题,即一个约简被定义为C的所有子集中使正域最大的最小属性集合,具体对于其他决策域也可以用同样的方法定义.但是,Jia等人[13]指出:由于决策域的单调性不满足,当属性增加或删除之后,决策域变大或者变小哪一种情况更好,这在可解释性上存在一定的困难.因此, Jia等人[13]提出了一种决策风险最小化属性约简定义,将属性约简理解为保持决策风险最小.其定义如下:
定义4[13]. 给定一个决策表S=(U,At=CÈD),BÍC,则称B是C的一个决策风险最小化属性约简,当且仅当满足如下的条件:
(Ⅰ) B=argminBÍC{COSTB};
(Ⅱ) 对于"AÌB,有COSTA>COSTB.
其中,
(4)
其中,
现在我们通过一个例子来说明上述几种定义中存在的问题.
例1:给定一个决策表S=(U,At=CÈD),见表 1,其中,U={x1,x2,…,x12},C={c1,c2,c3,c4,c5,c6},D={d}.假设所有损失函数为:lPP=lNN=0,lPN=6,lNP=3,lBP=1,lBN=3,那么根据公式(1),有:
a=(0.75,0.75,0.75), b=(0.60,0.60,0.60).
根据公式(2)和定义2,有:
根据定义1、定义3和定义4,可以得到{c2,c3}是一个正域的定量保持属性约简,{c5,c6}是一个正域的定性保持属性约简,{c4}是一个决策风险最小化属性约简,{c2,c4,c5}是一个正域最大化属性约简.
根据定义2,我们可以计算出这些不同约简的正域:
.
从以上结果可以看出,正域的定量保持属性约简和决策风险最小化属性约简都不同程度地改变了正域,正域最大化属性约简虽然使正域扩大,但是它的可解释性存在困难[13].正域的定性保持属性约简虽然不改变整个决策表的正域,即但它并不能保持每一个决策类的正域不变,例如:
与原始决策表每个决策类的正域分布相比,决策类D1和D2的正域被改变.
由例1可见,由于决策域关于属性集合的非单调性,上述几种属性约简的定义都有可能改变决策域.然而,实际应用中我们并不希望改变每个决策类的决策域,因为我们引入概率阈值的目的是为了增强分类能力,而不是改变决策域.属性约简的目的只是为了消除冗余属性.
此外,因为在决策粗糙集中决策域和决策风险相对于属性增减之间的非单调性,在定义1、定义3和定义4中的必要条件必须检查属性集合B的所有子集,而不是对B中每一个属性b依次检查一遍子集B-{b}[21].因而,传统的基于增加-删除法和基于直接删除法[27]的启发式约简算法可能会找到约简的超集而不是约简本身.相比之下,采取群体智能优化算法更容易求得最优解,例如遗传算法和粒子群优化算法等[13, 29].值得注意的是,为了减少算法设计上的困难,开发一种具有单调性的度量函数来指导概率粗糙集中属性约简算法的设计是必要的.
2.2 决策域分布保持约简的定义为了保证在属性约简之后每一个决策类的决策域不发生变化,我们给出了(a,b)正域分布保持约简和(a,b)非负域分布保持约简的定义.与上述几种属性约简定义相比,正域分布保持约简和非负域分布保持约简分别不改变每一个决策类的正域和非负域.
定义5. 给定一个决策表S=(U,At=CÈD),BÍC,记
(5)
(1) 如果则称B为S的(a,b)正域分布保持集;如果且对于"AÌB, 则称B为S的(a,b)正域分布保持约简.
(2) 如果则称B为S的(a,b)非负域分布保持集;如果且对于"AÌB,则称B为S的(a,b)非负域分布保持约简.
一个(a,b)正域(或非负域)分布保持集是保持决策表每个决策类的正域(或非负域)不变的属性集合.
例2:续例1.
根据定义5得到,B={c1,c2,c5,c6}是一个正域分布保持约简.此外,有:
可以看到,属性集合B能够保持决策表每个决策类的正域不变.不难发现,{c2,c3,c5}是一个非负域分布保持约简.
3 决策域分布保持约简的启发式计算方法这一节将给出决策域分布保持约简的启发式计算方法。在此基础上给出决策域分布保持约简核属性的定义以及求核算法.
3.1 决策域分布保持约简的启发式计算方法在设计属性约简算法时,度量函数的单调性是非常重要的.由于在决策粗糙集中,决策域的定义引入了概率阈值,因此决策域随属性的变化之间不具备单调性,这为算法设计带来了一定的困难.因为要找到一个约简就必须检查属性集合的所有子集,否则可能找到一个约简的超集,而检查所有子集是一个非常耗时的工作.因此,有必要开发满足单调性的启发式度量函数来简化算法设计的困难.在这一节中,我们通过条件信息量的变形提出了(a,b)正域分布条件信息量和(a,b)非负域分布条件信息量,并证明了其单调性。它们分别用于计算(a,b)正域分布保持约简和(a,b)非负域分布保持约简.
首先,让我们回顾一下条件信息量的定义.
定义6[30]. 给定一个决策表S=(U,At=CÈD),PÍAt,QÍAt,U/IND(P)={X1,X2,…,XN},U/IND(Q)={Y1,Y2,…,YM},Q相对于P的条件信息量定义为
(6)
接下来,我们通过条件信息量的变形,给出两种单调的决策域分布条件信息量.它们分别被称为(a,b)正域分布条件信息量和(a,b)非负域分布条件信息量.在此基础上,我们给出了(a,b)正域分布保持约简和(a,b)非负域分布保持约简的启发式计算方法.
给定一个决策表S=(U,At=CÈD),BÍC,记论域U上的两个覆盖:
其中,.
定义7. 给定一个决策表S=(U,At=CÈD),BÍC,U/IND(B)={X1,X2,…,XN}:
(1) 条件属性B相对于的(a,b)正域分布条件信息量定义为
(7)
(2) 条件属性B相对于的(a,b)非负域分布条件信息量定义为
(8)
(a,b)正域和(a,b)非负域分布条件信息量反映了条件属性的划分相对于每个决策类(a,b)正域和(a,b)非负域分布的协调程度.
为了证明(a,b)正域分布条件信息量和(a,b)非负域分布条件信息量的单调性,需要首先证明如下引理:
引理1. 给定一个决策表S=(U,At=CÈD),A1ÍC,A2ÍC,U/IND(A1)={X1,X2,…,XN},而U/IND(A2)={X1,…,Xi-1, Xi+1,…,Xj-1,Xj+1,…,XN,XiÈXj}是将划分U/IND(A1)中的某两个等价块Xi和Xj合并为XiÈXj得到的新划分.那么,
(1)
(2)
证明:
(1) 记:
令|Xi|=x,|Xj|=y,显然有x>0,y>0,0≤ak≤1,0≤bk≤1,则
当ak=bk时,即,对于"kÎ{1,2,…,m+1},都有的情况下,ID=0.
故,引理得证.
(2) 证明与情形(1)的证明类似.
引理1说明:如果将决策表条件属性集的分类进行合并,(a,b)正域分布条件信息量和(a,b)非负域分布条件信息量将单调不减.因此,我们得到如下的单调性定理:
定理1. 给定一个决策表S=(U,At=CÈD),AÍC,BÍC且AÍB,那么,
(1)
(2)
证明:
(1) 根据引理1,如果将决策表条件属性的分类进行合并,将使(a,b)正域分布条件信息量非严格单调增加,而划分U/IND(A)是可以通过将划分U/IND(B)中的部分等价类合并得到的,所以有:
(2) 证明与情形(1)的证明类似.
定理2. 给定一个决策表S=(U,At=CÈD),BÍC,那么,
(1)
(2)
证明:根据(a,b)正域分布条件信息量和(a,b)非负域分布条件信息量的定义直接可以得到.
定理3. 给定一个决策表S=(U,At=CÈD),BÍC,那么,
(1) B是S的一个(a,b)正域分布保持集当且仅当
(2) B是S的一个(a,b)非负域分布保持集当且仅当
证明:记x([x]B)={[y]C:[y]CÍ[x]B},因为BÍC,所以x([x]B)构成[x]B的一个划分.
(1) 设
必要性:因为B是S的一个(a,b)正域分布保持集,所以有因此有根据定理2可以得到
充分性:对任意1≤j≤m,若则可以得到或(1≤k≤m且k¹j)或
当或时,有:
这与矛盾,因此有又因为所以对于所有[y]CÎx([x]B),成立.这就是说,对于所有[y]CÎx([x]B),有P(Dj|[y]C)≥aj.从而
因此,
另一方面,如果那么有
又因为可以得到或
当时,因为所以对于所有[y]CÎx([x]B),有:
这就是说,对于所有[y]CÎx([x]B),有P(Dj|[y]C)<aj.从而
结果这与矛盾,因此从而
这就证明了对于任意1≤j≤m,有即B是S的一个(a,b)正域分布保持集.
(2) 证明与情形(1)的证明类似.
定理4. 给定一个决策表S=(U,At=CÈD),BÍC,那么,
(1) B中一个属性b相对于是不必要的当且仅当
(2) B中一个属性b相对于是不必要的当且仅当
根据定理4,立即得到如下推论:
推论1. 给定一个决策表S=(U,At=CÈD),BÍC,那么,
(1) B中一个属性b相对于是必要的当且仅当
(2) B中一个属性b相对于是必要的当且仅当
根据定理3和推论1,可以得到如下的定理:
定理5. 给定一个决策表S=(U,At=CÈD),BÍC,那么,
(1) B是S的一个(a,b)正域分布保持约简当且仅当:
(Ⅰ)
(Ⅱ) 对于任意bÎB,有
(2) B是S的一个(a,b)非负域分布保持约简当且仅当:
(Ⅰ)
(Ⅱ) 对于任意bÎB有
定理5给出了(a,b)正域分布保持约简和(a,b)非负域分布保持约简的启发式计算方法.
3.2 决策域分布保持约简的核属性在一个决策表中,核属性是决策表所有约简的交集.它通常可以作为属性约简算法的起点,然后利用一定的启发式信息求解属性约简,这样可以显著缩小约简算法在属性空间中的搜索范围,有效提高约简算法的运行效率.接下来,我们给出决策表中两种决策域分布保持约简核属性的形式化定义及其求核算法.
定义8. 给定一个决策表S=(U,At=CÈD),那么:
(1) (a,b)正域分布保持约简的核属性定义为
(9)
(2) (a,b)非负域分布保持约简的核属性定义为
(10)
其中,和分别是所有(a,b)正域分布保持约简和所有(a,b)非负域分布保持约简的集合.
根据定理3和定义8,可以得到如下的定理:
定理6. 给定一个决策表S=(U,At=CÈD),cÎC,那么:
(1) 当且仅当
(2) 当且仅当
证明:
(1) 必要性:设根据定理4,c在C中是不必要的.这与矛盾,因此有
充分性:如果根据推论1,c在C中是必要的,那么它一定出现在S的所有(a,b)正域分布保持约简中,因此,即
(2) 证明与情形(1)的证明类似.
根据定理6和定义8,可以得到如下的定义:
定义9. 给定一个决策表S=(U,At=CÈD),那么,
(1) (a,b)正域分布保持约简的核属性定义为
(11)
(2) (a,b)非负域分布保持约简的核属性定义为
(12)
定义9给出了两种决策域分布保持约简核属性的计算方法.根据定义9我们设计求核算法如下:
算法1. 求核算法.
Input:决策表S=(U,At=CÈD),阈值(a,b).
Output:决策域分布保持约简的核
Note:T=POS或ØNEG //T表示决策域分布保持约简的类型
Step 1. 计算
Step 2. 令
Step 3. for对每个cÎC do //计算核属性
计算
if then
end if
end for
Step 4. return
在算法1中,计算核需计算|C|次而计算的时间复杂度为O(|C||U|2),所以在最坏情况下,算法1的时间复杂度为O(|C|2|U|2).
4 基于决策域分布保持的最小约简问题及启发式算法这一节讨论了基于决策域分布保持的最小约简问题,将最小约简问题转化为约束优化问题.考虑到遗传算法在求解最小约简时所表现出的高效性,提出了基于遗传算法的决策域分布保持启发式约简算法.
4.1 最小约简问题描述一般来说,一个决策表存在多个约简.而在实际应用中,为了得到简洁的决策规则,获取最小约简非常有意义.为了设计智能优化算法,在这一节,我们将基于决策域分布保持的最小约简问题转化为如下约束优化问题:
定义10. 给定一个决策表S=(U,At=CÈD),那么,
(1) 基于(a,b)正域分布保持的最小约简问题定义为:最大化使得:
(13)
(2) 基于(a,b)非负域分布保持的最小约简问题定义为:最大化使得:
(14)
给定一个属性集合B,如果它是定义10中的一个可行解,那么它是一个决策域分布保持约简;如果它是定义10中的一个最优解,那么它是一个最小约简.
为了简化算法设计的难度,根据定理5,该优化问题可以等价地定义如下:
定义11. 给定一个决策表S=(U,At=CÈD),那么,
(1) 基于(a,b)正域分布保持的最小约简问题定义为:最大化使得:
(15)
(2) 基于(a,b)非负域分布保持的最小约简问题定义为:最大化使得:
(16)
4.2 基于遗传算法的决策域分布保持启发式约简算法这一节给出了利用遗传算法求解最小约简的设计方案,其中包括染色体的表示、适应度函数的设计以及各种遗传算子的设计,然后给出了基于遗传算法的决策域分布保持启发式约简算法.
(1) 染色体的表示
采用一个定长的二进制向量来表示每个染色体,染色体的长度等于条件属性全集所含属性的个数,染色体的每个基因位和相应的条件属性对应,二进制位等于1,表示备选解包含对应位的条件属性;二进制位等于0,表示备选解不包含对应位的条件属性.例如,假设在决策表S中有8个条件属性{c1,c2,…,c8},那么染色体10101100对应的可能解为{c1,c3,c5,c6}.
(2) 适应度函数
适应度函数是评价一个染色体表示的解有多好的确定性指标,它控制了种群的进化方向.在本文的算法中,适应度函数定义为
(17)
其中,chB表示一个染色体;条件表示一个染色体chB是一个决策域分布保持约简的超集(决策域分布保持集),这里,T表示决策域分布保持约简的类型,它可以取POS或ØNEG,分别表示正域分布保持约简和非负域分布保持约简.因为我们在设计选择算子时采用轮盘赌的方式,为了增加种群多样性避免算法过早收敛到次优解,在适应度函数中需要一个大于0的常量Q,常量Q保证了每一个染色体都有被选择到下一代进化的可能性,在本文中,我们设Q=0.5.显然,当chB是一个决策域分布保持约简的超集时,chB中包含的属性越少,适应度函数f(chB)的值越大;当chB是一个决策域分布保持约简的真子集时,适应度函数最小.这确保了适应度函数最大的染色体能够与最小约简相对应,由此说明了适应度函数的正确性.
(3) 选择算子
选择算子根据适应度函数的大小采取比例选择,通过轮盘赌的方式生成后代.每个个体被选择的概率为
(18)
其中,表示第i个染色体的适应度值,N是种群大小.同时采用精英保存策略,即,用当前种群中的最优个体替换新种群中的最差个体,且最优个体不进行交叉和变异,精英保存策略能够确保算法最终收敛到最优解.
(4) 交叉算子
交叉算子采用有性繁殖,随机选择两个父个体进行均匀交叉,对染色体的每个基因位,首先生成一个0~1之间的随机数,如果随机数小于交叉概率Pc,则将相应基因位上的两个染色体的基因进行互换.如果染色体的基因位对应决策域分布保持约简的核属性,则不进行交叉操作.
(5) 变异算子
变异算子采用均匀变异,对于每个基因位,随机生成一个0~1之间的随机数,如果随机数小于变异概率Pm,那么将该位上的基因值取反,即,如果该基因位上的基因值是0,那么将其变为1;如果是1,那么将其变为0.对于核属性所对应的基因位不进行变异操作.
(6) 修正算子
在本文的遗传算法中加入了一个修正算子,由于种群中适应度值大于常量Q的染色体是决策域分布保持约简的一个超集,因此,修正算子的作用是将这些表示决策域分布保持约简超集的染色体修正为表示决策域分布保持约简的染色体,以保证最终得到的约简是决策域分布保持约简而不是决策域分布保持约简的超集.算法2给出了对染色体进行修正运算的具体描述.
算法2. 修正算子.
Input:染色体.
Output:修正后的染色体.
Note:T=POS或ØNEG //T表示决策域分布保持约简的类型
Step 1. 将染色体解码为对应的属性集合B,令CD=B;
Step 2. for每一个aÎCD do
计算
end for
Step 3. 根据的大小将CD中的属性按降序排序;
Step 4. while CD¹Æ do
CD=CD-{a},其中,a是CD中的第1个属性;
if then
B=B-{a};
end if
end while
Step 5. 将属性集合B编码为对应的染色体chB;
Step 6. return chB
(a,b)正域分布条件信息量和(a,b)非负域分布条件信息量的单调性可以保证对每个决策域分布保持约简的超集执行完算法2后,能够获得相应的决策域分布保持约简.
对每个染色体的修正运算的时间复杂度为O(|C|2|U|2),而对整个种群修正运算在最坏情况下的时间复杂度为O(N|C|2|U|2),其中,N是种群大小.
(7) 算法终止条件
当种群变的稳定时算法终止,即连续t代最优个体的适应度值没有变化或迭代次数达到最大值.
(8) 遗传约简算法的实现
根据前面的描述,可以设计基于遗传算法的决策域分布保持启发式约简算法如下:
算法3. 基于遗传算法的决策域分布保持启发式约简算法.
Input:决策表S=(U,At=CÈD),阈值(a,b).
Output:决策域分布保持约简R.
Note:T=POS或ØNEG //T表示决策域分布保持约简的类型
Step 1. 通过算法1求决策域分布保持约简的核属性
Step 2. if then
令
go to Step 8;
end if
Step 3. 令t=1;
Step 4. 初始化:随机生成N个长度为|C|的二进制串组成初始种群pop(t),对每个属性cÎC,如果c是核属性,则相应的基因位初始化为1;如果c不是核属性,则随机初始化为0或1;
Step 5. 个体评价:评价pop(t)中每个个体的适应度;
Step 6. while 终止条件不满足 do
Step 6.1. 选择:从pop(t)中,运用选择算子选择出M/2对父个体,其中,M≥N;
Step 6.2. 交叉:对所选择的M/2对父个体,以概率Pc执行交叉,形成M个中间个体;
Step 6.3. 变异:对M个中间个体,分别独立以概率Pm执行变异,形成M个候选个体;
Step 6.4. 选择:从M个候选个体中,运用选择算子选择出N个个体,组成新一代种群pop(t+1);
Step 6.5. 修正:对新种群pop(t+1),运用修正算子进行修正操作;
Step 6.6. 个体评价:评价pop(t+1)中每个个体的适应度;
Step 6.7. 令t=t+1;
end while
Step 7. 令R为最优个体对应的属性集合;
Step 8. return R;
算法3在最坏情况下时间复杂度为O(N|I-max||C|2|U|2),其中,N是种群大小,|I-max|是最大迭代数.
5 实验结果与分析在这一节中,我们将通过实验比较几种属性约简定义的分类结果,并且验证遗传算法是否能够求得最小约简.数据集来自UCI机器学习数据库[25].在实验中,所有连续属性用等频率离散化方法进行离散.不完备数据用均值或者众数填充.所有程序基于weka[31]用Java语言编写.
5.16种定义的比较这一节通过分类正确率与误分类代价两个标准来评估本文第2节讨论的6种属性约简定义,并给出了各种定义下约简的平均长度;同时,也比较了两种决策域分布保持约简与原始未约简数据的分类正确率和误分类代价,说明决策域分布保持约简是一种更好的选择.
在实验中,对于每个数据集,随机生成10组不同的损失函数,损失函数的值在区间(0,1)范围内,分类正确率和误分类代价的均值与标准差被记录.为了简化,假设每个决策类具有同样的损失函数,损失函数满足接下来的限制条件,即,对于"DjÎpD,有lBP<lNP,lBN<lPN和lPP=lNN=0.十折交叉验证被用于测试,两种流行的分类算法J48[32]和Naive Bayes[33]被用于进行比较实验.
由于决策域和决策风险的非单调性,群体智能优化算法更容易求得最优解,因此,实验中所有6种定义全部基于遗传算法实现.正域分布保持约简和非负域分布保持约简通过本文方法实现,分别记为GA-PRDR和GA- NNRDR;决策风险最小化属性约简使用文献[13]中的算法,记为GA-MINDC;正域最大化属性约简采用文献[29]中的算法,记为GA-MAXPR.事实上,文献[29]给出了基于决策域保持属性约简的遗传算法框架,因此,基于正域的定性与定量保持属性约简可以通过修改文献[29]中的适应函数获得,分别记为GA-QLPRP和GA-QNPRP.6种遗传算法的详细参数见表 2,其中,Pc和Pm分别表示交叉概率和变异概率.
(1) 分类正确率
这个部分比较了不同属性约简定义所得到约简的分类正确率.表 3和表 4显示了采用J48和Naive Bayes分类算法进行测试的实验结果,平均最大分类正确率加粗显示.从结果中可以发现:在两种分类模型下,正域分布保持约简和非负域分布保持约简在多数情况下所选择的属性获得了更好的分类结果;相对而言,决策风险最小化属性约简所选择的属性与两种决策域分布保持约简所选择的属性分类效果相当,并且好于正域最大化和正域的定性与定量保持约简.与原始数据分类结果(记录在第2列Raw data中)相比,两种决策域分布保持约简在多数情况下,分类正确率有所提高.
(2) 误分类代价
这个部分比较了不同属性约简定义所得到约简的误分类代价.我们采用文献[13]给出的评价标准,即,误分类代价被定义为
mc=lPN×nPN+lNP×nNP (19)
其中,nPN和nNP分别表示误分类对象数量,即错误的肯定数量和错误的否定数量.在实验中,代价敏感分类方法被利用[31],同样地,J48与Naive Bayes分类器被用作基准分类器.
表 5和表 6分别给出了采用J48和Naive Bayes分类算法进行测试的实验结果,平均最小误分类代价加粗显示.从实验结果可以看出:两种决策域分布保持约简和决策风险最小化属性约简在多数情况下都获得了更低的误分类代价,与原始数据的误分类代价相比,两种决策域分布保持约简在多数情况下至少有1种分类器能够降低误分类代价.
因此,无论是分类正确率还是误分类代价,决策域分布保持约简都是一种更好的选择.
(3) 约简平均长度
表 7列出了用遗传算法求解每种约简的平均长度与标准差,其中,|U|是对象的个数,|C|是条件属性的个数.从约简长度的标准差可以看出:因为在我们的算法中加入了修正算子,使得遗传算法找到的是约简本身而不是约简的超集,因此,本文算法求得的约简长度较稳定.这也是由于决策域分布保持约简的定义更严格,因为它要求每一个决策类相应的决策域都不变.
为了验证本文提出的遗传算法是否能够找到最小约简,我们选取了一组UCI数据集进行实验.在实验中,每个决策类的阈值设为aj=0.8和bj=0.4.对于每个数据集,利用遗传算法分别对两种决策域分布保持约简实验20次,遗传算法参数设置见表 2.实验结果见表 8,其中,PRDPR表示正域分布保持约简,NNRDPR表示非负域分布保持约简,|Core|是核属性的个数,最小约简长度用Min-|R|表示,它是通过回溯算法[34]求出的.GA-|R|表示遗传算法获得的约简长度.在GA-|R|一列中,上标位置括号中的数字表示在这20次实验中获得该约简长度的实验次数.比如,在数据集Hepatitis上的实验结果,8(17)9(3)表示在20次运行中有17次得到的约简长度为8,3次得到的约简长度为9.
从实验结果可以看出:遗传算法每次运行可能会找到不同的约简;但在大多数运行情况下,表示遗传算法通常可以找到最小约简.比如,在数据集Wpbc上,20次实验都找到了最小属性约简.这是因为本文的适应度函数能够保证最小约简与适应度函数最大化问题等价.
6 结 论决策粗糙集是一种典型的概率粗糙集,由于引入了概率阈值,属性的增减与正域(或非负域)的变化不再似经典粗糙集理论中具备单调性.本文分析了决策粗糙集中属性约简中存在的一些问题.为了不改变决策域(正域或非负域),在决策粗糙集中引入了(a,b)正域分布保持约简和(a,b)非负域保持约简.此外,属性增减与决策域变化之间的非单调性给算法设计带来了一定的困难.为了简化算法设计,通过条件信息量的变形,提出了(a,b)正域分布条件信息量和(a,b)非负域分布条件信息量,并证明其具有单调性,它们分别作为设计计算(a,b)正域分布保持约简和(a,b)非负域保持约简的启发式信息;同时,本文也给出了两种决策域分布保持约简的核属性以及求核算法.为了获得最小约简,本文还提出了一种基于遗传算法的启发式约简算法.在遗传算法中,我们的适应度函数能够保证最优解与最小约简相对应.另外,通过上述两种满足单调性的决策域分布条件信息量,在遗传算法中加入了一种新的算子,称为修正算子.修正算子确保遗传算法找到的是约简本身而不是约简的超集.最后,通过实验的方法从分类正确率和误分类代价说明了决策域分布保持约简与其他几种属性约简定义之间的性能差异,并且验证了遗传算法求解最小属性约简的有效性.
[1] | Pawlak Z. Rough Sets-Theoretical Aspects of Reasoning about Data. Dordrecht: Kluwer Academic, 1991. |
[2] | Yao YY, Zhao Y. Attribute reduction in decision-theoretic rough set models. Information Sciences, 2008,178(17):3356-3373 . |
[3] | Shen Q, Jensen R. Rough sets, their extensions and applications. Int’l Journal of Automation and Computing, 2007,4(3):217-228 . |
[4] | Wu WZ, Leung Y, Shao MW. Generalized fuzzy rough approximation operators determined by fuzzy implicators. Int’l Journal of Approximation Reasoning, 2013,54(9):1388-1409 . |
[5] | Hu QH, Yu DR, Xie ZX. Numerical attribute reduction based on neighborhood granulation and rough approximation. Ruan Jian Xue Bao/Journal of Software, 2008,19(3):640-649 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/19/640.htm |
[6] | Yao YY, Wong SKM, Lingras P. A decision-theoretic rough set model. In: Ras ZW, Zemankova M, Emrich ML, eds. Proc. of the Methodologies for Intelligent Systems. New York: North-Holland, 1990. 17-24. |
[7] | Pawlak Z, Wong SKM, Ziarko W. Rough sets: Probabilistic versus deterministic approach. Int’l Journal of Man-Machine Studies, 1988,29(1):81-95 . |
[8] | Ziarko W. Variable precision rough set model. Journal of Computer and System Science, 1993,46(1):39-59 . |
[9] | Slezak D, Ziarko W. Attribute reduction in the Bayesian version of variable precision rough set model. Electronic Notes in Theoretical Computer Science, 2003,82(4):263-273 . |
[10] | Inuiguchi M. Attribute reduction in variable precision rough set model. Int’l Journal of Uncertainty, Fuzziness and Knowledge- Based Systems, 2006,14(4):461-479 . |
[11] | Mi JS, Wu WZ, Zhang WX. Approaches to knowledge reductions based on variable precision rough set model. Information Sciences, 2004,159(3-4):255-272 . |
[12] | Zhou J, Miao DQ. b-Interval attribute reduction in variable precision rough set model. Soft Computing, 2011,15(8):1643-1656 . |
[13] | Jia XY, Liao WH, Tang ZM, Shang L. Minimum cost attribute reduction in decision-theoretic rough set models. Information Sciences, 2013,219(10):151-167 . |
[14] | Yao YY. Probabilistic rough set approximations. Int’l Journal of Approximation Reasoning, 2008,49(2):255-271 . |
[15] | Yao YY. Two semantic issues in a probabilistic rough set model. Fundamenta Informaticae, 2010,108(3-4):1-17 . |
[16] | Li HX, Zhou XZ. Risk decision making based on decision-theoretic rough set: A three-way view decision model. Int’l Journal of Computational Intelligence Systems, 2011,4(1):1-11 . |
[17] | Herbert JP, Yao JT. Game-Theoretic rough sets. Fundamenta Informaticae, 2011,108(3-4):267-286 . |
[18] | Yu H, Chu SS, Yang DC. Autonomous knowledge-oriented clustering using decision-theoretic rough set theory. Fundamenta Informaticae, 2012,115(2-3):141-156 . |
[19] | Zhou B. Multi-Class decision-theoretic rough sets. Int’l Journal of Approximation Reasoning, 2014,55(1):211-224 . |
[20] | Qian YH, Zhang H, Sang YL, Liang JY. Multigranulation decision-theoretic rough sets. Int’l Journal of Approximation Reasoning, 2014,55(1):255-237 . |
[21] | Zhao Y, Wong SKM, Yao YY. A note on attribute reduction in the decision-theoretic rough set model. In: Peter JF, Skowron A, Chan CC, Grzymala-Busse JW, Ziarko W, eds. Proc. of the Trans. on Rough Sets XIII. LNCS 6499, Heidelberg: Springer-Verlag, 2011. 260-275. |
[22] | Wong SKM, Ziarko W. On optimal decision rules in decision tables. Bulletin of Polish Academy of Sciences, 1985,33:693-696. |
[23] | Ye DY, Chen ZJ, Ma SL. A novel and better fitness evaluation for rough set based minimum attribute reduction problem. Information Sciences, 2013,222(10):413-423 . |
[24] | Holland JH. Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press, 1975. |
[25] | Frank A, Asuncion A.. UCIrvine machine learning repository. 2011. http://archive.ics.uci.edu/ml . |
[26] | Liu D, Li TR, Li HX. A multiple-category classification approach with decision-theoretic rough sets. Fundamenta Informaticae, 2012,155(3-4):173-188 . |
[27] | Yao YY, Zhao Y, Wang J. On reduct construction algorithms. In: Gavrilova ML, Tan CJK, Wang YX, Yao YY, Wang GY, eds. Proc. of the Trans. on Computational Science II. LNCS 5150, Heidelberg: Springer-Verlag, 2008.100-117 . |
[28] | Wang GY, Yu H, Yang DC. Decision table reduction based on conditional information entropy. Journal of Computers, 2002,2(7): 759-766 (in Chinese with English abstract) . |
[29] | Chebrolu S, Sanjeevi SG. Attribute reduction in decision-theoretic rough set models using genetic algorithm. In: Panigrahi BK, Suganthan PN, Das S, Satapathy SC, eds. Proc. of the Swarm, Evolutionary, and Memetic Computing. LNCS 7076, Heidelberg: Springer-Verlag, 2011.307-314 . |
[30] | Liu ZH, Liu SY, Wang J. An attribute reduction algorithm based on the information quantity. Journal of Xidian University, 2003, 30(6):835-838 (in Chinese with English abstract) . |
[31] | Hall M, Frank E, Holmes G, Pfahringer B, Recutemann P, Witten IH. The WEKA data mining software: An update. SIGKDD Explorations, 2009,11(1):10-18 . |
[32] | Quinlan JR. C4.5: Programs for Machine Learning. San Mateo: Morgan Kaufmann Publishers, 1993. |
[33] | Kantardzic M. Data Mining-Concepts, Models, Methods, and Algorithms. 2nd ed., Hoboken: Wiley-IEEE Press, 2011. |
[34] | Min F, Zhu W. Attribute reduction of data with error ranges and test costs. Information Sciences, 2012,211(30):48-67 . |
[5] | 胡清华,于达仁,谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简.软件学报,2008,19(3):640-649. http://www.jos.org.cn/1000-9825/19/640.htm |
[28] | 王国胤,于洪,杨大春.基于条件信息熵的决策表约简.计算机学报,2002,25(7):759-766 . |
[30] | 刘振华,刘三阳,王珏.基于信息量的一种属性约简算法.西安电子科技大学学报,2003,30(6):835-838 . |