区间值序决策表的条件熵属性约简

张晓燕，匡洪毅

（西南大学 人工智能学院，重庆 400715）

0 引言

粗糙集理论［1］最初由波兰数学家Pawlak提出，是一种处理不精确、不一致与不完全数据的数学工具。近年来，随着知识发现、机器学习、数据挖掘、决策分析等领域的兴起，粗糙集理论的研究与应用也逐渐得到更多学者的关注［2］。

现实问题中，由于环境的复杂性（噪音、信息缺失、决策者具有偏好特性等），许多问题的描述不是一个精确的值，而很可能是一个模糊的数值区间。同时，数据的属性值之间往往存在大小、强弱等优势关系，因此优势关系下的粗糙集模型相对于经典模型具有更广阔的应用空间。例如，多属性决策问题中需要对样本的属性值进行排序从而筛选出最优方案。因此，对于连续且具有偏序关系的区间值数据的研究具有重要价值。

知识约简是粗糙集理论的核心问题之一。所谓知识约简，就是在保持信息系统的分类能力不变的前提下， 删除其中的冗余属性，从而快速地从庞大、繁杂的数据中提取有效信息。现有的属性约简方法可分为以下几类：基于差别矩阵的属性约简算法［3］、基于正区域的属性约简算法［4-5］以及基于信息论的约简算法［6］。

针对区间值序信息系统的约简方法研究中，Qian等［7］最早提出一种通过比较区间的上下边界给对象排序的方法，并给出了基于优势粗糙集（DRSA）的属性约简方法。Shi等［8］对区间值进行模糊化，并求其分布约简判定条件和可辨识矩阵。Yang等［9］为减少差别矩阵的冗余元素，提出差别信息树并提高了计算效率。Zhang等［10］基于 α-容差关系，保证系统的上下近似在特定意义下不变，提出了α-上、下近似约简。上述方法均通过构建差别矩阵进行约简，其时空复杂度较高。而启发式属性约简算法是一种更高效的约简途径，即通过构建评估属性重要程度的指标并结合贪心算法得到约简。其中，利用信息论的观点评估属性重要度是一种不错的方法。Dai等［11］提出了基于α -弱相似的不完备区间值信息系统的不确定性度量方法。Feng等［12］基于覆盖诱导的划分，构造了区间值信息系统的信息熵和补熵度量方式。Yan等［13］从互信息的角度讨论了特征重要性，并以此构建增量式约简算法。

本文在上述研究的基础上，针对优势关系下的区间值决策表作进一步研究。文献［13］可作为一种无监督的特征选择方法，但当数据包含决策信息时，将其考虑在内能更好地提取到有效信息。因此，本文讨论了条件熵作为不确定性测度的可行性，并基于此提出了启发式属性约简算法。最后，通过对比实验验证了本算法在约简率上的优越性。

1 预备知识

1.1 粗糙集理论与序信息表

信息系统又称信息表或知识表示系统，主要表现形式是一张反映对象与属性之间关系的数据表。一张信息表可形象地表示为I=(U，AT，V，f)，其中，U 表示对象集论域，AT 是属性集合，V是属性值域，f：U×AT→V是信息函数，表示论域到属性集的映射。Pawlak粗糙集在近似空间下为信息表赋予了新意义，它使得每个属性集确定一个二元不可区分关系（等价关系）。但在实际问题中，并非所有信息系统都是可精确划分的，有不少信息系统是基于偏序关系，也称优势关系。针对这种情况，序信息系统应运而生，下面给出相关定义。

在一个信息系统中，如果在某属性值域上存在优势关系，则称这个属性为一个准则。当所有的属性都为准则时，该信息系统称为序信息 系 统［14］，形象地表示为 I≥=(U，AT，V，f)。对 ∀xi，xj∈U，可用“xi≥axj”表示 xi在准则 a 下优于xj。若在属性集A⊆AT下比较两对象，则“xi≥Axj”表示xi相对于A中的所有属性都优于或者等于xj。

设 I≥=(U，AT，V，f)为一序信息系统，类似于粗糙集中的等价关系，并基于上述描述，可定义序信息系统中的优势关系为:

由条件属性集AT和决策属性集D所诱导的覆盖簇分别为

1.2 区间值序决策表

在现实生活中，并非所有问题的属性都可以被刻画为一个确切的值，而很可能是一个不确定的数值区间或范围。对拥有这种属性的信息表定义如下［15］。

设 I=(U，AT⋃D，F，G)为 一 个 决 策 信 息表，若它满足对∀x∈U，∀a∈AT，∀f∈F，则有：

称其为区间值决策表，其中f(xi，a)表示xi在属性a下的属性值区间，aL(xi)和aU(xi)分别为区间的左右端点，且aL(xi)≤aU(xi)。

对具有优势关系的区间值信息表可以表示为 I=(U，AT⋃D，F，G)，对准则 a∈AT 所诱导的优势关系表示为

若对∀a∈AT都满足上述优势关系，则称该区间值信息表为区间值序决策表，其中，由优势关系集合A∈AT所诱导的优势类和覆盖为

为了更直观方便地理解，下面给出区间值序决策表的完整数学定义。区间值序决策表可以用一个五元组表示为I≥=(U，AT⋃D，F，G)， 其中U={ u1，u2，…，un}，表示有限对象集论域；AT={a1，a2，…，aT}，表示有限条件属性集 ；D={d1，d2，…，ds}，表示有限决策属性集合 ；F=，表示论域与条件属性集的关系集合；G={g ：U→Vd，d∈D }，表示论域与决策属性集的关系集合。

设 I=(U，AT⋃D，F，G)为区间值序决 策表，易证其上的优势关系有如下性质：

（1）自反性、传递性，但不一定具有对称性；

定义1 类似于粗糙集中等价关系的上下近似定义，在区间值序决策表中，对优势关系也可定义一对上下近似算子。

2 知识的粗糙条件熵与属性重要度及属性约简算法

2.1 区间值序决策表中知识的粗糙条件熵

属性对系统的协调性贡献是评价属性重要性的关键指标，即去掉某一属性，若系统不协调程度（也称粗糙度）增加越多，则该属性越重要。而条件熵就可作为该指标，其主要思想是：在已知某变量的情况下，评估另一变量的不确定性。在区间值序决策表中，我们引入该概念来评价此类信息系统的粗糙程度。

定义2 设I≥=(U，AT⋃D，F，G)为一区间值序决策表，在属性集A⊆AT下，粗糙条件熵定义为

定理1（最大值） 设 I≥=(U，AT⋃D，F，G)为一区间值序决策表，且P⊆AT，I≥的粗糙条件熵最大值为Ulog||U， 当 且 仅 当∀ui∈U，R≥P(ui)=U 且 ∀Di∈U/D，| |Dj=1，此时优势关系退化等价关系。

定理2 （最小值） 设 I≥=(U，AT⋃D，F，G)为一区间值序决策表，且P⊆AT，D相对于P的粗糙条件熵最小值为0，当且仅当对∀di，dj∈D，有 di=dj。

定理3（单调性） 设 I≥=(U，AT⋃D，F，G)为一区间值序决策表，且P⊆AT，Q⊆AT若P⊆Q，则H( D | Q)≤H( D | P)。

对求和的每一项可看作一个二元函数

f(x,y)=−xlog(x/(x+y))(x>0,y≥0),分别对x和y求偏导都可得到单调递增函数，因此

即：H( D | Q)≤H( D | P)。该定理说明随着分辨能力的增强，粗糙条件熵单调递减，即决策属性相对于条件属性的不确定性增加、系统更加粗糙。

2.2 区间值序决策表中属性的重要度

本节给出基于粗糙条件熵的属性重要度判定方法，作为该系统下启发式属性约简算法的基础。

定义3 设 I≥=(U，AT⋃D，F，G)为区间值序决策表，且A⊆AT，定义属性a在A中的绝对重要度为

记属性集A的核为Core(A)，表示刻画决策属性所必要的属性。

定理4 结合上述定义及定理1和定理2易得

（2）当A={}a 时，用 DS(a)替代 DS(a，A)，

定义4 设 I≥=(U，AT⋃D，F，G)为区间值序决策表，C⊆A，对∀a∈AC，定义a相对于C的相对重要度为

由上述定义可知，当DR(a，C)值越大时，属性a相对于C的重要度就越高。因此在属性约简过程中，每一步都先将满足

的属性纳入核中，得到次最优或最优约简。

定义5 设 I≥=(U，AT⋃D，F，G)为区间值序决策表，B⊆AT，若满足H( |D B)=，且对 ∀a∈B，有 DR(a，B)>0，则 B为AT的一个约简。由定义3可求得属性集AT的核，由于核唯一并且为任何约简的子集，因此核可以作为最小约简的起点。由定义4中的属性重要度，基于当下未选的属性集合，逐步将最重要的属性添加到核中，直至其粗糙条件熵等于H( D | AT)。即在Core(AT)的基础上通过增加属性构成的最小约简。

2.3 基于条件熵的区间值序决策表属性约简算法

首先，对给定的一个区间值序信息系统，根据定义3计算属性集的核。其次，将属性集合分为两部分，一部分为已选择属性，即约简属性集，另一部分为未选择属性，以核作为约简的起点。接着，根据定义4中的属性重要度，对未选择的属性集排序，选择对于约简集最重要的属性并添加到约简集中。然后，更新上述两部分集合并重复上一步操作。最后，当约简集的条件熵等于原信息表的条件熵时完成约简。算法的具体实现见表1。

3 案例分析

下面给出一个具体案例来说明本文给出方法的具体操作步骤。设 I≥=(U，AT⋃D，F，G)为一个区间值序决策表，论域代表6个投资对象：U={u1，u2，u3，u4，u5，u6}，属性集代表3种不同的风险：AT={a1，a2，a3} ，属性值代表风险范围，决策属性d={1，2，3} 代表风险等级。统计数据如表3所示。

原表下各对象的优势类如下：

根据属性约简算法，对表3进行属性约简。首先求条件属性集的核Core(AT)。由定义2

4 实验分析

本节将通过实验对2节中提出的算法性能进行验证，并与另外两个算法分析比较。本文从UCI数据集网站http://archive.ics.uci.edu/ml/datasets.html下载了6个数据集，数据的具体信息如表4所示。整个实验在一台私人电脑上实现，其具体配置如表5所示。

首先，将数据集转化为区间值形式，具体做法［16］为：假设实值数据集(U，C∪{d }，V，f)，a∈C，则

其中，对样本xi来说，σd为与xi同标签的样本在属性a下特征值的标准差。

然后，将算法1和对比算法分别对6个区间值序信息系统进行属性约简。对比算法如下：（1）文献［15］中针对序信息系统提出了一种基于粗糙熵（类似于信息熵）的启发式属性约简方法，我们将其引入到区间值序信息系统中；（2）文献［16］针对区间值信息系统提出了一种基于正域不变的启发式属性约简方法，同样也可拓展到本系统。上述方法的约简思路与本文相似，但衡量属性重要程度的标准不同。

最后，从属性约简率和约简后信息系统的分类能力两方面进行对比。

关于分类器的选择，目前可用的区间值数据分类器很少，采用文献［17］中扩展的K近邻（KNN）分类器来比较分类效果。对于每种算法，随机抽取10%的样本，代入不同K值（1≤，N为样本数）来选取该算法适合的K值，采用十折交叉验证做分类预测。属性约简率如表6所示，分类效果结果如表7所示。

从表6可以得出，条件熵的属性约简率均高于另外两种算法。相较于粗糙熵和正域的约简算法，本文算法的约简性能更稳定、无低约简率出现，使得所有数据集均得到有效约简，平均约简率达73.3%，高于另外两种算法14% ～ 25%。

从表7的约简后分类效果来看，条件熵算法的分类效果大多优于粗糙熵算法并与保持正域算法持平，且总体分类效果较好。综合来看，相较于另外两种算法，条件熵算法能保持高约简率的同时分类效果较好。因此，本文提出的算法在区间值序信息系统下是可行的且具有应用价值。

5 结论

本文在区间值信息系统下进行研究，基于信息论的中条件熵概念提出了一种搜索式属性约简算法。条件熵可以充分利用数据的标签信息，以此评价数据中支持正确分类的信息量，并筛选掉对分类不重要的属性。基于条件熵，定义了属性重要度并提出启发式约简算法，以确保我们逐步选取的属性都是当前最优解，从而构成最佳约简。之后，分析了算法的时间复杂度。最后，通过实验分析并与一些该信息系统下的约简算法做对比，验证了该算法的有效性。在未来的工作中，将针对区间值序信息系统下不同的偏序定义进行研究，并将该算法推广到其中。