不完备混合决策粗糙集特定类多目标属性约简

蔡艳婧，程 实，王 强

(1.南通大学 信息科学技术学院，江苏 南通 226009； 2.江苏商贸职业学院 电子与信息学院，江苏 南通 226009)

0 引 言

决策粗糙集[1]是著名学者Yao在传统粗糙集理论上的重要推广，目前决策粗糙集成果已应用于数据分类[2,3]、数据聚类[4]、图像处理[5,6]以及模式识别[7]等领域。属性约简是粗糙集理论的核心研究内容[8]，针对决策粗糙集的属性约简问题，目前学者们进行了广泛深入的研究。Yao等在文献[9]中最早研究了决策粗糙集的属性约简问题。Ma等[10]基于保持决策正区域提出了决策粗糙集的正区域属性约简算法，Gao等[11]在决策粗糙集中提出了最大决策熵的属性约简。在另一方面，基于代价敏感的角度，Jia等[12]在决策粗糙集中提出了最小决策代价属性约简。杨志荣等[13]基于多代价的策略在决策粗糙集模型上提出了一种改进的最小代价属性约简。陈婉清等[14]联合决策代价和分类质量，在决策粗糙集下提出了一种新的属性约简。总之可以看出基于决策代价的属性约简是目前决策粗糙集的研究热点[15-18]。

然而，实际应用中的环境是复杂多样的，首先很多信息系统都是不完备混合型的，即数值型属性和符号型属性并存，然后在某些情形下，我们只需要关注信息系统中某个类或者某几个类[19,20]，并且在进行最小化决策代价属性约简的同时，可能也希望约简结果的测试代价尽量小[21，22]。例如在医疗诊断信息系统中，我们往往都只关注患病的样本病例，然后选择决策代价小的病理指标降低误诊的风险，但是某些指标的采集会产生高昂的费用，这时就需要将测试代价考虑进来，因此针对信息系统的特定类别，同时考虑决策代价和测试代价具有很高的现实意义。

在粗糙集理论中，测试代价[21,22]也是学者们重点关注的内容，目前已有多种测试代价的属性约简算法被提出。在本文，将提出一种不完备混合决策粗糙集模型，该模型进一步扩大了决策粗糙集的应用范围。接着在不完备混合决策粗糙集的基础上，定义了特定类别的决策代价，并将决策代价和属性集的测试代价同时作为属性约简的优化目标，提出一种特定类的多目标代价敏感启发式属性约简算法，该算法得到的属性约简可以使决策代价和测试代价综合最小。实验结果表明，所提算法具有更高的代价敏感属性约简性能，同时属性约简结果针对的是特定的决策类，不同的类可以得到不同的约简结果，因此所提算法具有更高的实用性能。

1 基本理论

在本节将简要介绍决策粗糙集的基本内容，为后文的展开提供铺垫。

定义1[8]在粗糙集中，数据集表示成决策信息系统S=(U,AT=C∪D) 的形式，其中U称为信息系统的论域，AT称为信息系统的属性全集，并且C和D分别称为条件属性集和决策属性集。给定论域中的对象∀x∈U在属性a∈AT下的属性值表示为a(x)，若信息系统包含缺失的属性值，该信息系统又称为不完备信息系统。

在粗糙集理论中，对于属性子集A⊆AT在信息系统下确定的等价关系[8]EA定义为

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

等价关系EA可以在信息系统论域U上诱导出一个划分U/EA，其中划分结果中的每个成员称之为等价类，对象x∈U在EA上的等价类表示为[x]A={y∈U|(x,y)∈EA}。

利用等价类作为基本运算单位，Pawlak提出了经典的粗糙集模型[8]。随着近几十年来粗糙集理论的研究和发展，学者们对传统的粗糙集模型进行了不断的扩展和改进，其中Yao等学者根据贝叶斯决策理论，将概率粗糙集进行推广，提出了决策粗糙集模型[1]，并且在该模型下诱导了三支决策理论，使得决策粗糙集成为了当今粗糙集领域最为活跃的研究分支。

表1 决策代价矩阵

表1中，代价值λPP,λBP和λNP表示对象x∈U处于状态X时采取aP,aB和aN这3种动作所产生的代价，代价值λPN,λBN和λNN表示对象x∈U处于状态Xc时采取aP,aB和aN这3种动作所产生的代价。

因此，对于信息系统∀x∈U可以得到采取3种动作决策时所产生的预期代价

CostP(x)=λPP·P(X|[x])+λPN·P(Xc|[x])
CostB(x)=λBP·P(X|[x])+λBN·P(Xc|[x])
CostN(x)=λNP·P(X|[x])+λNN·P(Xc|[x])

基于最小化决策代价原则，可以得到：

(1)若CostP(x)≤CostB(x) 且CostP(x)≤CostN(x)，则x∈POS(X)。

(2)若CostB(x)≤CostP(x) 且CostB(x)≤CostN(x)，则x∈BUN(X)。

(3)若CostN(x)≤CostP(x) 且CostN(x)≤CostB(x)，则x∈NEG(X)。

将上述的3个决策规则进行进一步推导，可以得到

使得

(1)当P(X|[x])≥α且P(X|[x])≥γ，那么x∈POS(X)；

(2)当P(X|[x])≤α且P(X|[x])≥β，那么x∈BUN(X)；

(3)当P(X|[x])≤β且P(X|[x])≤γ，那么x∈NEG(X)。

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

同时对象集X⊆U关于等价关系EA的决策粗糙集正区域、边界域和负区域分别定义为

特别地，决策属性集D在论域U上诱导的决策类划分为U/D={D1,D2,…,Dm}，决策属性集D关于等价关系EA的决策粗糙集正区域、边界域和负区域分别定义为

2 不完备混合决策粗糙集模型

Yao提出的决策粗糙集建立在离散完备的信息系统下。近年来，Li等[18]学者在数值型的信息系统下提出了邻域决策粗糙集，进一步地扩大了决策粗糙集模型的适用范围。然而实际应用中的数据类型是复杂多样的，其中数值型属性和符号型属性并存的不完备混合型信息系统便是最为常见的一种。本节将在不完备混合型信息系统下对决策粗糙集模型进行推广，提出一种更为广义化的模型。

在文献[23]中，Zhao等学者在不完备混合型的信息系统下构造了邻域容差关系，并且提出了对应的粗糙集模型，该模型在处理不完备混合型数据方法表现出了良好的性能，因此本节将采用Zhao等学者提出的邻域容差关系，用于不完备混合型决策粗糙集模型的构造。

类似于经典的决策粗糙集，对于不完备混合型信息系统中的对象∀x∈U，采取3种动作决策时所产生的预期代价为

基于最小化决策代价原则，可以得到

即

且

即

且

即

且

记

那么有

(1)当P(X|nδ(x))≥α且P(X|nδ(x))≥γ时，那么x∈POS(X)；

(2)当P(X|nδ(x))≤α且P(X|nδ(x))≥β时，那么x∈BUN(X)；

(3)当P(X|nδ(x))≤β且P(X|nδ(x))≤γ时，那么x∈NEG(X)。

通常表1中的代价满足λPP≤λBP<λNP且λNN≤λBN<λPN，此外，Yao[1]进一步假设代价满足

(λNP-λBP)·(λPN-λBN)>(λBP-λPP)·(λBN-λNN)

那么可以得到关系0≤β<γ<α≤1。因此

(1)当P(X|nδ(x))≥α时,那么x∈POS(X)；

(2)当P(X|nδ(x))≤α且P(X|nδ(x))≥β时,那么x∈BUN(X)；

(3)当P(X|nδ(x))≤β时,那么x∈NEG(X)。

根据如上推导，接下来可以得到不完备混合型决策信息系统下的决策粗糙集模型。

3 基于特定类的多目标属性约简算法

决策粗糙集是建立在代价基础上的粗糙集模型，因此基于代价敏感的属性约简是其研究的重点。在决策粗糙集模型中，目前学者们主要关注于决策代价的研究，而对于测试代价的研究比较少，然而在实际应用中，很多情形需要同时考虑这两方面的代价。

另一方面，传统的属性约简方法是全局的，即属性约简的结果是针对信息系统所有决策类的最优属性子集，然而实际应用中，可能往往只关注某个具体的类别，例如在医疗诊断中只关注患病的样本。因此针对这一问题，Yao和Zhang[19]提出了基于特定类属性约简的概念，进一步提高了属性约简的实用性。

综合考虑以上两个问题，本节将在不完备混合型决策粗糙集的基础上，提出一种特定类别的多目标最小化代价属性约简算法，该算法以信息系统特定类别为视角，通过同时最小化决策代价和测试代价两个代价目标来设计属性约简算法。

3.1 基于特定类的决策代价

表2 决策类Dt的代价矩阵

同时信息系统中对象决策为Dt的决策总代价表示为

定义5是通过特定决策类的角度来分析信息系统的决策代价，并且特定决策类的代价矩阵可以单独地进行指定，即信息系统中每个决策类可以设定不同的决策代价。例如在医疗诊断中，对于患病的病人，可以设定更高的误分类代价，而对于正常的人可以设定较低的误分类代价，另外对于不同严重程度的疾病，也可以设定不同程度的代价。因此基于类别设置不同代价矩阵具有更好的适用性和灵活性。

3.2 基于特定类的测试代价

在决策粗糙集模型中，对象分类入不同的决策结果将会产生相应的代价，并且不同的属性具有不同的代价结果。例如对于医疗诊断，判断病人的病情需要采集病人的各项生理指标，而采集的这些指标需要付出相应的金钱代价，并且对于不同的生理指标，其金钱代价也是不同的，因此这时测试代价的问题就要考虑进来。

在文献[24]中，Min等学者提出了多种最小化测试代价的属性约简算法。基于Min等学者的方法，本节这里进行延伸和拓展，提出不完备混合型信息系统的测试代价敏感模型。

定义6表明，当信息系统中每个属性的测试代价都为0时，则测试代价决策信息系统就退化为传统的不完备混合型信息系统。

3.3 基于特定类的多目标代价敏感属性约简

实际应用中可能需要同时考虑信息系统的决策代价和测试代价，因此需要将这两种代价进行综合。本节中，我们将这两种代价都作为属性约简的目标，提出一种基于特定类的多目标代价敏感属性约简算法。

由于多目标的属性约简需要同时考虑多个目标的情形，这往往很难保证属性约简结果使得每个目标都是最优的，因此需要对每个目标的结果进行权衡，即多目标的结果应该使整体达到最优。为此，这里定义了一个关于决策代价和测试代价的多目标综合代价函数。

其中，wdc≥0,wtc≥0,并且wdc+wtc=1，它们分别代表了决策代价和测试代价占据综合代价的比重。

根据定义7给出的综合代价，接下来可以得到特定类的多目标代价敏感属性约简的定义，具体如定义8所示。

寻找属性约简是一个NP难问题，而启发式搜索是求解属性约简的一种有效方法[9，10,18,23]，其中启发式搜索的关键是构造属性约简的启发式函数。根据定义7所示的多目标综合代价，我们可以进一步诱导出对应的启发式函数，即属性重要度函数。

根据定义9中属性重要度函数的定义，进行启发式搜索的属性约简算法如算法1所示。

算法1：不完备混合型决策粗糙集的特定类多目标代价敏感属性约简算法。

输入：不完备混合型测试代价决策信息系统为S=(U,AT=C∪D,tc)，邻域半径为δ，特定决策类Dt∈U/D，Dt的决策代价矩阵。

输出：类别Dt的决策代价和测试代价多目标属性约简red。

步骤1 初始化red←∅。

步骤6 返回最终属性约简结果red。

4 实验分析

在本节将通过实验来验证所提出算法的有效性。

4.1 实验数据集

表3所示的是参与实验的6个UCI数据集[25]，在这6个数据集中包含了4个混合类型、2个数值型和1个符号型的数据集，部分数据集为完备型的，实验前随机选择5%的属性值进行删除，同时为了消除数值型数据量纲的影响，进行实验前需要将所有数值型属性进行标准化处理，本实验标准化为[0,1]区间。

表3 实验数据集

4.2 参数选取

通过图1可以发现，随着邻域半径的逐渐增大，信息系统各个决策类的综合代价先减少后增大，即过大和过小的邻域半径不能够得到较好的实验结果。综合图1的每个子图的实验结果，可以得出当邻域半径δ介于0.15至0.21区间时，得到综合代价最小。在接下来的实验部分，我们选择δ=0.18进行实验。

4.3 实验比较

接下来将本文所提出的算法与文献[25]的属性约简算法进行实验比较，来验证本文算法的有效性。

在本小节进行实验前，本文算法的参数选取类似于4.2节，即每个决策类按照特定关系选取对应的决策代价，属性的测试代价按照区间[1,20]进行随机选取等。对于参与比较的算法，是一种基于不完备离散型信息系统的全局最小代价属性约简，因此进行实验时需要将表3中的数值型属性进行离散化处理，同时所有决策类选择统一的决策代价，这里也随机进行选取。

对于本文所提出的多目标属性约简与决策代价的属性约简，分别让这两种算法进行相应的属性约简，然后根据属性约简结果，我们分别计算出每个决策类的决策代价、测试代价以及综合代价，其结果见表4、表5和表6，由于实验结果是进行重复多次实验得到，因此实验结果以“均值±标准差”形式来表示，加粗的值表示的是最小的结果。

综合表4、表5和表6的实验结果，可以发现：

表4 属性约简结果的决策代价比较

表5 属性约简结果的测试代价比较

表6 属性约简结果的综合代价比较

(1)对于每个决策类的决策代价，文献[25]基于决策代价的属性约简在所有数据集中有7个决策类的决策代价最小，本文提出的特定类多目标属性约简在10个类中具有最小的决策代价。文献[25]的算法是一种全局的属性约简算法，即对所有的决策类选择出一个共同的属性子集使得决策代价最小，因而不能保证每个决策类都是决策代价最小的，而本文所提出的特定类多目标属性约简算法基于每个类进行属性选择，则多数类下具有较小的决策代价，部分决策类的决策代价稍高于文献[25]主要是由于本文是一种多目标的属性约简算法，属于约简的同时也考虑了测试代价的极小性。因此在决策类的决策代价方面，本文算法具有较优的属性约简性能。

(2)对于属性约简结果的测试代价，除数据集Cmc的决策类D2以外，本文提出的特定类多目标属性约简算法均具有较小的测试代价结果，这主要是由于本文的算法将测试代价作为一个优化目标进行属性约简，算法在进行属性选择的过程中，某个时刻可能有多个属性使得决策代价降低，但是本文的算法可以选择出测试代价较小的那个，而文献[25]中基于决策代价的属性约简算法，进行属性约简时只考虑决策代价最小，这使得选择的属性可能具有较高的测试代价，因而最终得到的约简结果测试代价较高。

同时可以发现，同一个数据集，基于决策代价的属性约简算法结果在每个决策类下的测试代价是一样的，这主要是由于该算法是一种全局的属性约简，即所有决策类得到了同一个约简结果，因此出现了这种现象。

(3)对于属性约简结果的综合代价，除了数据集Cmc的决策类D2和数据集German的决策类D1，本文提出的算法具有更低的综合代价，产生这一结果主要是由于本文的算法是在特定类别下进行多目标的属性约简，同时考虑了决策代价和测试代价，并且代价优化的对象具体到了对应的类别，因而属性约简的结果比全局的决策代价属性约简具有更好的约简性能。

综合以上实验结果，可以表明本文提出的算法在代价敏感的属性约简方面具有更高的性能，同时约简的目标针对具体的类，因此更加满足实际中的应用需求。

5 结束语

决策粗糙集是粗糙集理论的重要研究分支，属性约简是粗糙集理论的核心问题。本文将传统的决策粗糙集模型进行扩展和延伸，提出一种不完备混合决策粗糙集模型。决策代价和测试代价是决策粗糙集中两种重要的代价形式，本文基于特定类别的视角，将这两种代价同时作为属性约简的优化目标，提出一种特定类别的多目标属性约简算法。实验结果分析表明，所提出算法的属性约简结果能够使决策代价和测试代价综合最小，并且不同类别有着不同的属性约简，更加符合实际的应用。本文的研究拓宽了决策粗糙集属性约简的应用范围，因此接下来将在动态数据以及大数据环境下进行进一步研究。