模糊决策粗糙集的特定类最小化决策代价属性约简算法

卓雪雪 朱苍璐

（安徽三联学院计算机工程学院 安徽合肥 230000）

Yao等学者提出的决策粗糙集模型是传统粗糙集理论的重要推广[1]。决策粗糙集模型通过引入贝叶斯理论来最小化决策的风险，利用参数阈值的限制来对概率粗糙集划分的区域给出了语义解释，在决策粗糙集中，阈值可以通过最小化代价函数进一步计算得到，因此给定决策代价，我们可以直接确定信息系统三支决策的区域划分，并诱导出相应的决策规则[2]。

属性约简是粗糙集理论最重要的应用之一。属性约简其目的是寻找原始属性集中的一个最小子集，使得与整个属性集的分类能力相当。在决策粗糙集模型中，Yao等[3]学者提出了基于决策粗糙集正区域的属性约简；Ma等[4]学者在Yao的基础上，提出了决策区域保持的属性约简，同时，Meng等[5]学者针对决策粗糙集提出了一种快速属性约简；基于熵度量的方法，Gao等[6]学者在决策粗糙集下提出了最大决策熵模型，并提出一种属性约简方法；姚晟等[7]学者基于正区域非单调性方法，提出一种改进的属性约简；Li等[8]学者利用多目标优化的方法提出一种新的决策粗糙集属性约简；杨璇等[9]学者提出了一种决策粗糙集最优尺度选择的约简。另一方面，决策粗糙集建立在代价的基础上，因此有学者通过决策代价作为出发点进行属性约简的构造。例如，Jia等[10:1-2]学者针对决策粗糙集三区域划分的决策代价，提出了最早的最小化决策代价属性约简算法；Song等[11]学者在模糊决策粗糙集下提出了最小化决策代价的属性约简，Fang等[12]学者提出了一种改进的决策粗糙集属性约简。到目前为止，决策粗糙集的属性约简受到了研究人员越来越多的关注。

然而，在实际应用环境下，我们可能往往只关注某一个决策类，例如，在医疗诊断中，决策者往往只关注患病的样本集，同时实际应用环境下的数据可能是数值型的，并且具有一定的模糊性，因此传统的决策粗糙集属性约简很难直接对其应用。针对信息系统中所关注的决策类，Ma等[13-14]学者提出了特定类的决策粗糙集属性约简，李明等[15]学者提出了集成学习方法的特定类决策粗糙集属性约简，彭莉莎等[16]学者提出了特定类的三支概率属性约简。但是这些成果很少有对模糊性数据环境进行相关研究，针对这一问题，本文提出一种模糊决策粗糙集的特定类最小化决策代价属性约简算法。

针对传统的决策粗糙集，本文将考虑信息系统的模糊性，提出一种模糊相似关系的决策粗糙集，称之为模糊决策粗糙集，然后在该模型中考虑特定决策类的决策划分，提出了模糊决策粗糙集的三支决策规则，最后基于最小化决策代价原则，提出了一种基于特定决策类的最小化代价属性约简算法。实验结果证明了本文所提出算法的有效性。

一、基本理论

对于决策粗糙集，给定一个对象集X，状态集由两个类表示，即Ω ={X,～X}，分别表示对象x属于或不属于X；动作集Γ ={aP,aB,aN}，aP,aB,aN分别表示三个动作：aP表示对象x被划分为X的正区域；aB表示对象x被划分为X的边界域；aN表示对象x被划分为X的负区域。关于两种不同状态下的三个动作的代价矩阵如表1所示。

表1 代价矩阵

在表1中，λPP，λBP和λNP分别表示对象x属于X时进行aP，aB和aN动作的代价；λPN，λBN和λNN分别表示对象x不属于X时进行aP，aB和aN动作的代价。通常，代价满足0≤λPP≤ λBP< λNP<1，0≤ λNN≤ λBN< λPN<1。

对于决策粗糙集中，对象隶属于集合概率的阈值是由每个分类决策的最小代价来确定，这提供了决策区域划分的语义解释，具体定义结果如定义1所示。

这里的阈值(α,β)是由代价矩阵确定的一对数值，定义为

定义2[4].考虑决策信息系统IS=(U,AT=C∪ D)，对于对象集X⊆U和属性集A⊆C，那么对象集X⊆U在阈值(α,β)下的决策近似区域划分为

与经典粗糙集中的规则不同，决策粗糙集中三个区域获得的三种规则可能是不确定的，它们代表了在做出决策时对错误的容忍程度，因而具有更高的泛化性能。

二、特定类下的模糊决策粗糙集

由于实际应用环境下，我们可能往往只关注某一个决策类，同时实际应用环境下的数据可能具有一定的模糊性。针对这一情形，本节将提出一种基于特定类的模糊决策粗糙集模型。

定义3[11].考虑决策信息系统IS=(U,AT=C∪D)，属性集A⊆ C。如果二元模糊关系满足如下3个条件，那么又被称为模糊T等价关系：

在本文，我们利用高斯核函数[17]来构造对象之间的模糊关系。

定义4[17].考虑决策信息系统

IS=(U,AT=C ∪ D)，属性集A⊆ C，∀x,y∈U之间的模糊相似度定义为

接下来，在模糊关系的基础上提出特定类视角下的模糊决策粗糙集模型。

在模糊决策粗糙集模型中，给定一个特定类的对象X，该对象集的状态集由两个类表示，即Ω={X,～X}，分别表示对象x属于或不属于X；动作集Γ ={aP,aB,aN}，aP,aB,aN分别表示三个动作：aP表示对象x被划分为X的正区域；aB表示对象x属于X的边界域；aN表示对象x属于X的负区域。关于特定类两种不同状态下的三个动作的代价矩阵如表2所示。

表2 特定类X的代价矩阵

针对特定类X，对象x采取三种动作的预期成本可以表示如下：

因此我们可以得到基于特定类的模糊决策粗糙集模型以及三个决策区域的划分。

定义6.考虑决策信息系统IS=(U,AT=C∪ D)，属性集A⊆C。信息系统特定类X代价函数确定的一对决策阈值为αX和βX，那么特定类X关于(αX,βX)确定的模糊决策粗糙集上下近似集定义为

定义7.考虑决策信息系统IS=(U,AT=C∪ D)，属性集A⊆C。信息系统特定类X代价函数确定的一对决策阈值为αX和βX，那么特定类X关于(αX,βX)的模糊决策粗糙集三个决策区域定义为

在定义7中，特定类的三个决策区域可以根据三支决策进行语义解释。由(αX,βX)确定的决策正区域可以诱导用于进行接受决策的规则，由(αX,βX)确定的决策负区域可以诱导用于做出拒绝决策的规则，由(αX,βX)确定的决策边界域可以产生非承诺规则。根据非承诺规则，我们既不做出接受或拒绝的决策，而是做出非承诺的决策。

三、特定类的最小化代价属性约简

三支决策在日常决策中起着关键的角色，它们可以根据成本进行评估决策。在现实世界的应用中，往往需要考虑决策的成本，寻找一个条件属性的最小子集，使得所关注的特定决策类具有最小化的决策成本，这种称之为最小化决策代价的属性约简。在本节，我们将提出一种特定类视角下基于模糊决策粗糙集的最小化代价属性约简算法。

考虑决策信息系统IS=(U,AT=C∪D)，属性集A⊆ C。信息系统特定类X关于(αX,βX)的模糊决策粗糙集三 个 决 策 区 域 分 别 为

根据模糊决策粗糙集的代价矩阵和决策规则，我们可以得出特定类在正区域、边界区域和负区域的三个规则的决策成本：

根据特定类X的三个决策成本，可以进一步得到特定类的决策总成本，表示为

基于特定类的决策代价，我们提出一种特定类的最小化决策代价属性约简。

定义8.考虑决策信息系统IS=(U,AT=C∪ D)，特定类X代价函数确定的一对决策阈值为αX和βX，那么特定类X的最小化决策代价属性约简集red定义为

(1)Costred(X)≤CostC(X);

(2)∀a ∈ red,Costred(X)

在定义8所示的最小化决策代价属性约简中，(1)限制了特定类X在属性约简集red下的决策代价不大于在属性全集下的决策代价；(2)要求该属性约简集red是极小的，移除任意一个属性会增加决策代价。

在粗糙集理论中，学者们通过两种方法来计算寻找属性约简[10:6-7]：穷举算法和启发式算法。穷举算法通过可识别矩阵构造所有约简的集合，然而，该算法是一个NP难问题。启发式算法引起了学者们的广泛关注，目前基于粗糙集理论的属性约简大多采用启发式的方法。本文将采用启发式的方法实现所提出的属性约简算法，首先给出了启发式函数的定义。

定义9.考虑决策信息系统IS=(U,AT=C∪D)，A⊆C，对于∀a∈A关于特定类X的属性重要度定义为

由于CostA(X)是固定的，即只需要计算代价Cost{a}(X)，那么Sig(a,A,X)适用于确定属性a的显著性。Sig(a,A,X)表示在特定类X下属性a相对于属性集A的显著性程度，当Sig(a,A,X)的值越大，属性a就越显著，反之亦然。

基于定义9的属性重要度作为启发式函数，我们提出一种基于模糊决策粗糙集模型的特定类最小化决策代价属性约简算法。

算法1：基于模糊决策粗糙集的特定类最小化决策代价属性约简算法

输入：决策信息系统IS=(U,AT=C∪ D)，信息系统特定类X⊆U，特定类X的代价矩阵。

输出：特定类X的最小化决策代价属性约简结果red。

1.利用特定类X的代价矩阵计算出决策阈值αX和βX；

2.初始化设置red← ∅，A← C；

3.对于∀a∈A，计算每个属性的属性重要度Sig(a,A,X)；

4.选择属性集A中属性重要度最大的属性amax，若满足关系CostA-{amax}(X)

5.对于 ∀a∈red，如果满足关系 Costred-{a}(X)≤Costred(X)，那么进行red ← red-{a}。

6.返回属性约简结果red。

算法1的基本思想是从空集开始不断搜索出一个属性约简结果，根据属性重要度函数，选择显著性值最大的属性作为候选属性，直到满足定义8中的条件(1)，然后，我们按照定义8中的条件(2)逐个删除属性约简集中的属性，直到满足属性约简结果的极小性。算法1的计算量主要集中在计算属性的重要度上，因此算法1的时间复杂度为O(|C|2·|U|2)。

四、实验分析

本节将进行一系列实验来测试所提出属性约简算法的有效性。实验各个环节在操作系统Windows7、CPU i3-6100 3.7GHz和内存8GB的个人计算机上，算法通过Matlab2012b进行实现运行。实验从UCI数据集库中选取了5个数值型类型的公用实验数据集，具体如表3所示，同时在实验前对这些数据集进行标准化处理。

表3 UCI实验数据集

对于本文所提出算法,我们进行如下设置:(1)设置高斯核函数的δ=1.0；(2)设置特定类的代价矩阵里面的，其余选择区间[0,1]范围内的随机值，并满足关系

利用本文所提出的属性约简算法对表3中各个数据集的每个决策类进行最小化决策代价属性约简，并计算每个决策类在属性约简集下的决策代价，重复进行实验10次并记录其平均值。表4展示了各个数据集每个决策类在原始属性全集下和属性约简集下的决策代价结果，其中Xi表示每个数据集第i个决策类。观察表4的实验结果可以看出，相比较于各个决策类属性全集的决策代价，属性约简集的决策代价有着大幅度的减少，其平均结果降低了39.32%。因此，本文所提出的属性约简算法可以大幅度降低信息系统进行决策的代价。

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

表5所示的是表3中各个数据集属性约简的平均长度结果，观察表5可以看出，每个决策类对应的属性约简结果均少于原始数据集的属性集，部分数据集的约简长度大幅度少于原始数据集，例如，数据集Ionosphere的原始属性集长度为34，而决策类X2的平均约简长度为12.3，数据集Sonar的原始属性集长度为60，而决策类X2的平均约简长度为15.8。各个数据集每个决策类属性约简的平均长度为10.49，各个数据集属性全集的平均长度为25.92，降低了59.53%。因此本文所提出的属性约简方法可以大幅度降低属性的数量。

表5 属性约简长度结果

本实验通过支持向量机(SVM)分类器基于十次交叉训练分类的方法评估各个数据集对于每个决策类属性约简集的分类精度，表6所示的是各个数据集每个决策类属性约简的SVM分类精度结果，通过表6可以看出，属性约简后每个决策类的分类精度均高于原始属性集，其中对于原始属性集，每个决策类的平均分类精度为83.35%，对于约简集，其平均分类精度为89.11%，整体提升了6.91%。因此本文所提出的属性约简在降低决策代价的同时，可以进一步提高特定类的分类性能。

表6 属性约简分类精度结果(%)

五、结语

属性约简是粗糙集的重要研究内容。在决策粗糙集模型中，基于代价敏感的属性约简是当前的研究热点。在实际应用环境下，我们往往只关注某个特定的决策类,同时实际的数据可能是数值型或模糊型,这给传统的决策粗糙集属性约简带来一定的挑战。针对这一问题，本文提出一种基于模糊决策粗糙集模型特定类的最小化决策代价属性约简真法，实验分析表明，本文算法得到的约简结果在降低属性数量和决策代价的同时，可以提高数据集的分类性能,具有一定的优越性。接下来，我们可以将本文属性约简方法进行推广，提出大数据环境下的属性约简算法，进一步提升实际环境下的应用性能。