基于集成学习的决策粗糙集特定类属性约简算法

李 明 甘秀娜 王月波

1(石家庄铁道大学四方学院经济管理系 河北 石家庄 051132)2(石家庄铁路职业技术学院组织人事部 河北 石家庄 050041)3(河北银行股份有限公司信息技术部 河北 石家庄 050000)

0 引 言

粗糙集模型是目前处理不确定性数据的一种重要的机器学习和数据挖掘理论[1]，近年来受到学者们的广泛关注和研究。决策粗糙集模型[2]是传统粗糙集的重要延伸，Yao[2]通过在决策粗糙集中融入最小化决策代价的原则，提出了三支决策理论，进一步地扩大决策粗糙集的应用范围[3]，目前决策粗糙集与三支决策已成功运用于数据挖掘等各个领域[4-6]。

属性约简是粗糙集理论的主要研究内容[1]，在决策粗糙集模型中，学者们提出了多种属性约简方法。第一类为基于正区域的属性约简，例如：Yao等[7]在决策粗糙集中提出了正区域属性约简，这也是决策粗糙集模型最早的属性约简方法；Ma等[8]对文献[7]方法进一步改进，将决策边界域和决策负区域也加入到决策区域属性约简的范畴，提出了保持决策区域的属性约简算法；Meng等[9]在算法的效率上进行改进，提出了一种正区域的快速决策粗糙集属性约简；Gao等[10]通过信息熵的视角，提出一种最大决策熵的决策粗糙集属性约简算法；姚晟等[11]进一步对正区域属性约简进行改进，提出一种决策区域最大化的决策粗糙集属性约简。第二类为基于决策代价的属性约简方法，Jia等[12-13]在决策粗糙集中定义了最小化决策代价属性约简，并设计了多种相应的启发式属性约简算法；Dou等[14]利于多代价的策略，提出了相应的最小化决策代价的属性约简；Song等[15]在模糊决策粗糙集下定义了决策代价，同时相应的最小化决策代价属性约简算法也被提出；Li等[16]将决策粗糙集推广至邻域空间，并提出邻域空间下的最小化决策代价属性约简。总之，决策粗糙集在这两方面的属性约简中已取得了丰硕的成果。

然而在实际应用环境下，往往只考虑某个或某几个特定的决策类，并且在进行决策区域的属性约简时也需要考虑代价的问题。例如：在医疗诊断中可能只关注患病的样本类，并且在保证诊断正确率的同时也要尽可能地降低诊断所付出的代价，这对目前的属性约简方法带来一定的挑战。针对特定类的问题，Yao等[17]在传统粗糙集模型中提出了基于特定类的属性约简，在此基础上，Ma等在决策粗糙集下分别提出了特定类的正区域属性约简[18]和决策代价属性约简[19]；彭莉莎等[20]提出了基于概率的特定类属性约简。然而这些研究成果也仅限于单一的属性约简视角，未同时考虑决策区域和决策代价的属性约简问题。

为了在特定类视角下同时兼顾决策区域和决策代价，本文将这两方面同时作为决策粗糙集属性约简的优化目标，定义一种特定类的属性约简，在该属性约简中，约简结果在保证决策区域极大化的同时，使得进行决策区域划分时也具有较低的决策代价，并且这些约简的目标都是针对特定决策类的。为了实现这种属性约简，本文接着利用集成学习的方法，设计出了相应的属性约简算法，最后通过与单一的决策区域属性约简和单一的最小化决策代价属性约简进行实验分析对比，证明了本文算法的有效性和优越性。

1 决策粗糙集模型与三支决策

决策信息系统[1]表示为二元组S=(U,C∪D)，这里的U为非空有限对象集，被称为论域。C为非空有限条件属性集，D为非空有限决策属性集，并且C∩D=∅。对于对象∀x∈U在属性∀a∈C∪D均有一个确定的属性值，表示为f(x,a)，通过对象、属性与属性值这三个组成部分，构建了整个决策信息系统。

定义1[1]考虑决策信息系统S=(U,C∪D)，属性子集A⊆C确定的等价关系定义为：

EA={(x,y)∈U×U|∀a∈A,f(x,a)=f(y,a)}

(1)

等价关系满足自反性、对称性和传递性。基于等价关系可以将论域诱导出一个划分，表示为U/EA。在U/EA中，包含对象x的等价类[x]A定义为：

[x]A={y∈U|(x,y)∈EA}

(2)

定义2[1]考虑决策信息系统S=(U,C∪D)，属性子集A⊆C确定的等价关系为EA，对于对象集X⊆U关于等价关系EA的下近似集和上近似集分别定义为:

(3)

(4)

由于传统的粗糙集建立在等价关系基础之上，对象与近似集之间的粗糙逼近关系过于严格。为了进行改进，Yao[2]提出了一种决策粗糙集模型与三支决策理论，通过一对阈值来限定等价类与近似集之间的逼近程度，提高了粗糙集模型的容噪性能[3]。

设决策信息系统中的状态集为Ω={X,Xc},Xc为X的补集，分别表示对象属于状态X或不属于状态X，设动作集为Γ={aP,aB,aN}，分别表示对象分类入状态X的正区域POS(X)、边界域BUN(X)和负区域NEG(X)，即接受、延迟和拒绝三种决策行为。当对象处于不同状态时采取不同的动作行为，三支决策模型定义了相应的决策代价矩阵，具体如表1所示。在表1中，λPP、λBP和λNP分别表示对象处于状态X时采取aP、aB和aN决策动作时所产生的代价；λPN、λBN和λNN分别表示对象处于状态Xc时采取aP、aB和aN决策动作时所产生的代价。

表1 决策代价矩阵

考虑决策信息系统S=(U,C∪D)，对于属性子集A⊆C确定的等价关系为EA，对象∀x∈U诱导出的等价类为[x]A，那么对象x隶属于对象集X⊆U和Xc的概率表示为：

(5)

给定决策代价矩阵，那么对象x∈U采取不同动作的决策代价可表示为：

(1)CostaP(x)=λPP·P(X|[x]A)+λPN·P(Xc|[x]A)。

(2)CostaB(x)=λBP·P(X|[x]A)+λBN·P(Xc|[x]A)。

(3)CostaN(x)=λNP·P(X|[x]A)+λNN·P(Xc|[x]A)。

根据贝叶斯决策准则，可以得到如下最小化决策代价规则：

(1) 当CostaP(x)≤CostaB(x)且CostaP(x)≤CostaN(x)时，则有x∈POS(X)；

(2) 当CostaB(x)≤CostaP(x)且CostaB(x)≤CostaN(x)时，则有x∈BUN(X)；

(3) 当CostaN(x)≤CostaP(x)且CostaN(x)≤CostaB(x)时，则有x∈NEG(X)。

进一步推导可以得到：

(1) 若P(X|[x]A)≥α且P(X|[x]A)≥γ,那么x∈POS(X);

(2) 若P(X|[x]A)≤α且P(X|[x]A)≥β,那么x∈BUN(X);

(3) 若P(X|[x]A)≤β且P(X|[x]A)≤γ,那么x∈NEG(X)。

其中：

那么对于决策信息系统S=(U,C∪D)，属性子集A⊆C确定的等价关系为EA，对象集X在等价关系EA下的三支决策区域[2]表示为：

(6)

同时，决策属性D在信息系统下诱导的决策类划分表示为πD={D1,D2,…,Dm}，那么决策属性D关于属性子集A的三支决策区域[7]为：

(7)

2 基于特定类的决策代价属性约简

决策粗糙集模型下的三支决策给出了一种新的决策模式[2-3,5-6]，进一步降低了决策行为的决策代价。然而，实际应用系统中的某些属性对决策和分类不相关，这些属性的删除可能会保持或者降低整个信息系统的决策代价[12-13]。针对这类研究问题，学者们提出了一种最小化决策代价的属性约简算法[12]，该算法旨在找出信息系统拥有最小决策代价的属性子集。

考虑决策信息系统S=(U,C∪D)，给定决策代价矩阵，属性子集A⊆C确定的等价关系为EA。决策属性D诱导的决策类划分为πD={D1,D2,…,Dm}，那么对象∀x∈U对于不同决策规则所产生的决策代价[12]表示为：

(1) 接受决策：p(x)·λPP+(1-p(x))·λPN；

(2) 延迟决策：p(x)·λBP+(1-p(x))·λBN；

(3) 拒绝决策：p(x)·λNP+(1-p(x))·λNN。

这里的p(x)=P(Dmax([x]A)|[x]A)，并且：

(8)

通常当对象决策为正确的区域时，是不会产生任何代价的，因此代价λPP=λNN=0，那么决策规则代价可以进一步简化为：

(1) 接受决策：(1-p(x))·λPN；

(2) 延迟决策：p(x)·λBP+(1-p(x))·λBN；

(3) 拒绝决策：p(x)·λNP。

那么整个决策信息系统的决策总代价[12]可以表示为如下形式：

(9)

基于决策代价的属性约简，即找出决策总代价最小的属性子集，其定义如下所示。

定义3[12]考虑决策信息系统S=(U,C∪D)，给定决策代价矩阵，属性子集A⊆C确定的等价关系为EA。决策属性D诱导的决策类划分为πD={D1,D2,…,Dm}，若属性子集A是属性集C的最小决策代价属性约简集，那么当且仅当：

(2) ∀A′⊂A,COSTA′(πD)>COSTA(πD)。

根据定义3所示的属性约简定义，学者们提出了多种属性约简算法以及多种扩展的属性约简算法[14-16],并且目前提出的这些算法均是针对全局的决策类，即算法得到约简子集使得所有决策类整体决策代价最小。然而，对于实际中的某些情形，我们可能只关注某个或某几个决策类，例如在疾病诊断中，如果对患病的样本进行属性约简，得到约简结果可以进一步降低决策代价，提高诊断的质量。如果对于某一类疾病，基于该类别进行属性约简，那么得到的约简结果与该种疾病是相适应的，不同疾病得到与之对应的属性子集，这样可以提高医疗诊断的效率和性能。因此针对某个或某几个类进行属性约简可以达到更好的处理性能，提高实际运用的适用性。

考虑决策信息系统S=(U,C∪D)，属性子集A⊆C确定的等价关系为EA。决策属性D诱导的决策类划分为πD={D1,D2,…,Dm}，给定特定决策类Dt∈πD以及对应的决策代价矩阵，那么对象∀x∈U关于特定决策类Dt的决策代价表示为：

(1) 接受决策：(1-pDt(x))·λPN；

(2) 延迟决策：pDt(x)·λBP+(1-pDt(x))·λBN；

(3) 拒绝决策：pDt(x)·λNP。

这里的pDt(x)=P(Dt|[x]A)。

那么整个决策信息系统关于决策类Dt的决策总代价可以表示为：

(10)

决策信息系统决策类Dt的决策总代价满足如下性质。

定理1考虑决策信息系统S=(U,C∪D)，给定特定决策类Dt∈πD，Dt相应的决策代价矩阵如表2所示，设两个属性子集满足A1⊆A2⊆C，并且确定的等价关系分别为EA1和EA2，那么决策类Dt关于属性集A1和A2的决策代价满足：

证明根据等价关系的定义可以得到，随着属性的增加，对象的等价类是单调性变化的，即满足当A1⊆A2时有[x]A2⊆[x]A1。然而随着属性的变化，三支决策区域却不是单调性变化的[7-8]，即随着属性数量的增加，三支决策区域的变化是随机的。对于∀x∈U，属性变化前后x隶属区域的变化可分为9种，分别表示为：

为了简便，假设属性增加时只有一个等价类发生变化，多个等价变化时可根据单个变化进行类推。当对象x的区域隶属变化满足情形(1)、(5)和(9)时，可以直接得到COSTA1(Dt)=COSTA2(Dt)。

COSTA2(Dt)-COSTA1(Dt)=

COSTA1(Dt)≥COSTA2(Dt)

COSTA2(Dt)-COSTA1(Dt)=

综上所述，可以得到COSTA1(Dt)≥COSTA2(Dt)。

证明完毕。

定理1表明了特定类的决策代价随着属性满足单调性的变化，这也进一步地解释了三支决策的实际意义[2]，即随着属性的增加，可用于决策的有用信息会越来越多，从而决策的准确率会更高，决策代价会更小。在决策的过程中，并不是所有的属性都是对决策有用的，有些属性的加入并不会降低决策代价，因此这类属性需要进行删除。基于此，接下来将给出特定类的最小化决策代价属性约简的定义。

定义4考虑决策信息系统S=(U,C∪D)，给定特定的决策类Dt∈πD以及对应的决策代价矩阵，属性子集A⊆C确定的等价关系为EA，若属性子集A是C的决策类Dt最小决策代价属性约简，那么当且仅当：

(1)COSTA(Dt)=COSTC(Dt);

(2) ∀A′⊂A,COSTA′(Dt)>COSTA(Dt)。

在定义4中，由于特定类决策代价的单调性，因此属性全集C拥有最小的决策代价，那么属性约简的目的是为了找出与属性全集C有着同样决策代价的属性子集，并且该属性子集中不包含其他任何的冗余属性，即属性约简集满足极小性。

核属性集[1]在寻找属性约简的过程中发挥着很重要的作用，由于满足属性约简定义的属性子集并不唯一，但是核属性集是确定的，并且是所有属性约简结果的交集，因此找出属性约简的核属性具有很重要的意义。

定义5考虑决策信息系统S=(U,C∪D)，给定特定的决策类Dt∈πD以及对应的决策代价矩阵，若属性子集族REDDt表示决策类Dt所有属性约简结果的集合，那么核属性集可定义为：

根据定义5所示的核属性集定义，采用其他学者的研究方法，核属性集可直接计算为：

Core(Dt)={a∈C|COSTC-{a}(Dt)>COSTC(Dt)}

3 基于集成学习的特定类属性约简

在决策粗糙集模型中，目前主要有两种类型的属性约简受到学者们的广泛关注：一是基于决策代价的属性约简；二是基于决策正区域的属性约简。实际应用环境下可能需要综合考虑这两类问题进行属性约简，Li等[21]在全局类下提出了多目标的属性约简，使得约简的结果具有更为广泛的适用性能。在特定类视角下，Ma等[18]提出了基于正区域的三支决策特定类属性约简，因此本节将Ma等的正区域属性约简与上节提出的决策代价属性约简进行综合，提出特定类的决策粗糙集多目标属性约简算法。

定义6[18]考虑决策信息系统S=(U,C∪D)，给定特定的决策类Dt∈πD以及对应的决策代价矩阵，属性子集A⊆C确定的等价关系为EA，若属性子集A是C的决策类Dt正区域属性约简，那么当且仅当：

由于三支决策模型中决策类的三个区域并不是随属性集单调性变化的，即属性子集的正区域既可能会大于属性全集的正区域，也可能会小于属性全集的正区域。因此属性约简结果需要保证约简集的正区域不低于属性全集的正区域，并且约简集是所有属性子集中最小的，这样就保证了属性约简结果具有较高的区分性能[18]。

接下来将综合特定类的正区域属性约简与本文提出的特定类决策代价属性约简，探讨其属性约简的问题。

属性约简[21]同时将多个目标作为属性约简的内容，使得约简结果能够同时对多个目标达到属性约简的效果。本文将同时考虑特定类的决策正区域和决策代价，但是多目标的属性约简结果不一定达到局部最优。故所得到的约简结果不一定既具有最小的决策代价又具有最大的决策正区域，因此这里采用全局最优的方式进行属性约简。

(11)

在定义7中，当属性子集A的决策代价越小，且决策正区域越大时，综合目标函数F(Dt)则越小。因此对于所提出属性约简，其优化的目标是选择出属性子集使得F(Dt)尽可能的小。

(1)FA(Dt)≤FC(Dt);

(2) ∀A′⊂A,FA′(Dt)>FA(Dt)。

集成学习[22]是一种常用机器学习方法，该方法让多个学习模型进行集成，通过整合共同的学习结果来对最终的结果进行学习，本文需要得到特定类下正区域和决策代价整体最优的属性约简结果。首先分别计算正区域属性约简和决策代价属性约简的核属性集，然后将得到的核属性集进行求取交集。交集可以看成正区域与决策代价得到的集成结果，然后在这个集成结果的基础上逐渐去整合剩余属性来得到最终的属性约简结果。具体的算法实现如算法1所示。

算法1基于集成学习的特定类属性约简算法

输入：决策信息系统S=(U,C∪D)，决策类Dt∈πD，决策类Dt的决策代价矩阵。

输出：决策类Dt的属性约简集RedDt。

步骤1初始化Red(Dt)=∅，并根据决策代价矩阵计算阈值α和β。

步骤2根据定义5计算决策类Dt的决策代价核属性集，记为Corecost(Dt)。

步骤3根据文献[18]计算决策类Dt的正区域核属性集，记为Corepos(Dt)。

步骤4记：

Core(Dt)=Corecost(Dt)∩Corepos(Dt)

RCore(Dt)=C-Core(Dt)

并令Red(Dt)=Core(Dt)。

步骤5比较FRed(Dt)(Dt)与FC(Dt)的大小，若FRed(Dt)(Dt)>FC(Dt)，跳转入步骤6。若FRed(Dt)(Dt)≤FC(Dt)，跳转进入步骤7。

步骤6对于∀a∈RCore(Dt)，计算：

如果FRed(Dt)(Dt)-FRed(Dt)∪{amax}(Dt)>0，那么：

Red(Dt)=Red(Dt)∪{amax}

RCore(Dt)=RCore(Dt)-{amax}

并重新跳转进入步骤5。

步骤7对于∀a∈Red(Dt)，若存在FRed(Dt)-{a}(Dt)≤FC(Dt)，那么Red(Dt)=Red(Dt)-{a},并重复步骤7，否则跳转入步骤8。

步骤8返回决策类Dt的约简结果Red(Dt)。

4 实验与结果分析

本节将通过进行实验来验证本文所提出的属性约简算法的有效性和优越性。

4.1 数据集

表3所示的是实验中所运用的UCI数据集[23]。其中：|U|表示数据集中对象的数量；|C|表示条件属性的数量；|πD|表示数据集决策类的数量。

表3 实验数据集

4.2 实验设置

4.3 分类精度比较

表4-表6展示的是各个属性约简算法得到的属性约简集在不同分类算法下的分类精度，其中分类精度结果采用十折交叉验证法进行计算得到，加粗的数值表示每行结果的最大值。本文提出的属性约简算法是针对具体的决策类，因此每个决策类将得到相应的属性约简结果，然后基于每个决策类对应的属性约简集利用分类器对其进行分类精度计算，得到每个决策类的分类精度结果，最后将每个决策类的精度进行综合，得到整个数据集的分类精度。

表4 各个数据集属性约简集的J48分类精度结果

续表5

表6 各个数据集属性约简集的SMO分类精度结果

在表4所示的J48分类精度结果中，可以发现本文算法得到的属性约简结果在大部分数据集下最高，只在数据集Lymphography和数据集Cancer低于其他算法。正区域算法在Lymphography有着最高的分类精度，粒子群优化算法在Cancer下有着最高的分类精度，并且正区域算法和粒子群优化算法的分类精度总体上要高于决策代价算法。在表5所示的RandomForest分类精度结果中，同样除Lymphography和Mushroom以外的所有数据集，本文所提出的算法具有最高的分类精度，其余算法在少部分数据集的分类精度稍高，并且决策代价算法稍低于正区域算法和粒子群优化算法。在表6所示的SMO分类精度结果中，同样可以看出本文算法在大部分数据集下的分类精度是最高的。

表5 各个数据集属性约简集的RandomForest分类精度结果

综合表4-表6的实验结果，表明本文算法得到的属性约简结果具有更好的分类性能。这主要是由于本文算法是一种多目标的属性约简算法，约简结果兼顾了数据集的分类性能和决策代价，并且约简的对象是具体的决策类，那么每个决策类可以得到与之相适应的约简结果，从而进一步地提高了每个决策类的分类性能，因此数据集整体的分类精度要更高。

4.4 决策代价比较

表7展示的是在属性约简结果下，各个数据集每个决策类的决策代价结果，其中加粗的数值表示每行结果的最小值。在表7中，最小的决策代价主要分布在本文的属性约简算法和决策代价算法，这主要是由于这两类算法都是关于最小化决策代价的算法，而其余的算法未考虑决策代价问题，因此得到的决策代价均高于这两种算法。对比本文算法和决策代价算法，可以发现本文算法只在少部分数据集下的决策代价稍高于决策代价算法，而决策代价算法的决策代价高于本文算法的决策类，其决策代价值大幅度高于本文算法。产生这种现象的主要原因是由于决策代价算法进行的是全局的属性约简，得到的约简结果只保证整体决策代价最小，而某些特定决策类的决策代价可能会更高。但本文的算法是基于特定的决策类，每个决策类得到了对应的最小决策代价属性子集，因此整体的决策代价要小于决策代价算法。

表7 各个决策类在属性约简结果下的决策代价比较

综合两部分实验结果，表明了本文所提出的属性约简算法同时兼顾了分类精度和决策代价两方面性能，并且针对特定的决策类进行属性约简，得到了对应决策类的约简结果，在属性约简方面有着很好的自适应性，其优越性更高。

5 结 语

决策粗糙集是一种重要的扩展粗糙集模型，其中基于正区域的属性约简和基于决策代价的属性约简是该模型的研究重点。在实际应用中，属性约简的研究对象可能只针对某个决策类，并且需要同时考虑约简的正区域和决策代价。本文针对信息系统的特定决策类，将正区域和决策代价同时作为属性约简的优化目标，定义一种特定类的属性约简，并利用集成学习的方法设计出相应的启发式属性约简算法，实验结果验证了该算法的有效性和优越性。今后拟将该算法进一步扩展至邻域信息系统以及混合型信息系统，提高特定类属性约简的适用范围。