面向局部多约束的属性约简方法研究*

董 杰，王 逊+，张文冬，王平心，杨习贝

1.江苏科技大学 计算机学院，江苏 镇江 212003

2.江苏科技大学 理学院，江苏 镇江 212003

1 引言

作为一种刻画不确定与不精确问题的数学工具，粗糙集理论与方法[1]近年来在机器学习、人工智能等领域得到了广泛的应用。除了粗糙集模型的构建以外，属性约简[2-5]是粗糙集理论中公认的一个核心研究问题。所谓属性约简，一般来说可以理解为从所有属性中找出一些满足给定约束条件的属性子集。这些约束条件大多是建立在由粗糙集模型与方法所得到的一些度量（如近似质量[6]、条件熵[7]、决策错误率[8]等）基础上的，具体的约束可以是找到一些属性子集能够保持这些度量或在给定的阈值范围内达到预期的度量标准。

例如，将近似质量作为约简约束条件中的度量，利用启发式算法可以求得一个使得近似质量满足给定约束的最小属性子集。然而值得注意的是，这一约简仅仅能够使得近似质量满足约束条件，但并不表示这个约简能够满足其他诸如条件熵度量下的约束条件。这主要是因为利用单一度量指标所构建的约束条件其指向明确，同时粗糙集理论中的不同度量指标之间可能并不存在必然的一致性。除此之外，仅仅考虑近似质量约束的约简策略并不一定适用，这主要是因为近似质量的约束虽然能够得到满足，但每一个决策类所对应的下近似集的变化情况是不一样的。例如对于约束条件为达到原始近似质量95%的情形来说，这是一种典型的近似约简[9]，虽然经过约简后所得到的近似质量可以达到预期的目标，但是并不一定能够保证每一个决策类的下近似集都能够达到与原始下近似集相似度等于或高于95%这一目标。

为解决上述问题，在文献[10-11]工作的基础上，选取近似质量和条件熵这两种度量准则构建约束条件，并从局部的视角出发，定义了局部多约束的属性约简，进而设计了求解这一约简的启发式算法。值得注意的是，经典Pawlak粗糙集模型是建立在等价关系基础上的，仅能用于处理离散型数据，而对于现实中广泛存在的连续型数据却束手无策。因此，Hu等人[12]提出了邻域粗糙集方法，该方法不仅可以用于直接处理连续型数据，而且由于邻域半径的存在，依据不同大小的半径，可以自然地形成一个多粒度结构框架，极大地拓展了粗糙集理论的应用范畴[13-17]。本文将借助这一模型来实现新的属性约简方法。

本文主要内容安排如下：第2章简要介绍邻域粗糙集的基本知识；第3章在传统属性约简的基础上，构建了局部多约束属性约简策略；第4章进行实验对比分析；第5章总结全文。

2 基础知识

在粗糙集理论中，研究对象为一个决策系统DS=＜U,AT∪D＞,U是所有样本构成的集合，即论域；AT是所有条件属性的集合；D是决策属性的集合且AT∩D=∅。U/IND(D)={X1,X2,…,XN}表示根据决策属性D所诱导出的论域上的划分。

定义1给定一个决策系统DS,∀x∈U,∀δ∈[0,1],r(x,y)为欧氏距离函数，则点集δ(x)={y|r(x,y)≤δ,y∈U}表示x的δ邻域，δ称为邻域半径。

给定论域U={x1,x2,…,xn}，假设M=(rij)n×n为论域上的相似度矩阵，rij表示样本xi与xj之间的欧氏距离。为了解决因半径过小而产生空邻域的问题[18]，可以采用邻域区间的表示方法。给定半径δ,∀xi∈U,xi的邻域区间为：

定义2[19-20]给定一个决策系统DS,U/IND(D)={X1,X2,…,XN},∀B⊆AT,D关于B的下近似和上近似定义为：

对于任一决策类Xi∈U/IND(D)：

决策类的下近似集是表示确定属于该决策类的样本的合集，借助下近似集，可以得到如下所示近似质量的定义。

定义3[21]给定一个决策系统DS,U/IND(D)={X1,X2,…,XN},∀B⊆AT,D关于B的近似质量定义如下：

其中，|X|表示集合X的基数。

显然 0≤γ(B,D)≤1成立。γ(B,D)表示根据条件属性B，那些确定属于某一决策类别的样本占总体样本的比例。

除了近似质量之外，条件熵也是粗糙集理论中一种常用的用于刻画不确定性的度量方法，以下定义4中给出了邻域条件熵的形式化描述。

定义4给定一个决策系统DS，论域U={x1,x2,…,xn},∀B⊆AT,D关于B的条件熵定义如下：

其中，[xi]D是指决策系统中包含样本xi的决策类。

3 属性约简

3.1 传统近似质量约简

属性约简是粗糙集理论研究中的重要内容，它是依据某种度量准则设置一约束条件，使得删除决策系统中的冗余属性后能够满足这一约束。

值得注意的是，由于文中使用式（1）所示的邻域区间计算邻域，因此邻域粗糙集的近似质量并不一定随着属性的增加而呈单调增加变化。当考虑将近似质量作为度量准则时，约简中的约束条件可以设置为“利用约简所求得的近似质量不低于利用原始属性集合所求得的近似质量”，如定义5所示。

定义5给定一个决策系统DS,∀B⊆AT,B被称为一个近似质量约简当且仅当γ(B,D)≥γ(AT,D)且∀B′⊂B,γ(B′,D)＜γ(AT,D)。

决策系统中的一个近似质量约简是一个能够保持邻域粗糙集的近似质量不降低的最小属性子集。根据定义5所示的约简定义，可以进一步使用如下所示的重要度进行约简的求解。

给定一个决策系统DS,∀B⊆AT且对于任意的a∈AT-B, 如果γ(B∪{a},D)=γ(B,D)，那么就表明属性a对于近似质量的提升没有任何贡献，a是冗余的；如果γ(B∪{a},D)＞γ(B,D)，那么就表示加入属性a后可以提高近似质量。因此，属性重要度定义为：

根据上述属性重要度，可以构建一个启发式属性约简算法。该算法以空集为起点，每次计算全部剩余属性的属性重要度，从中选择属性重要度值最大的属性加入约简集合中，直到利用当前约简集合中的属性所求得的近似质量满足约简中的约束条件。

算法1近似质量约简

输入：邻域决策系统DS=＜U,AT∪D＞，邻域半径参数δ。

输出：一个约简red。

步骤1red←∅,γ(red,D)=-∞，计算γ(AT,D)。

步骤2若γ(red,D)≥γ(AT,D)，则转步骤5，否则转步骤3。

步骤3（1）∀ai∈AT-red，计算Sig(ai,red,D)；

（2）选择aj，满足Sig(aj,red,D)=max{Sig(ai,red,D):∀ai∈AT-red}；

（3）令red=red∪{aj}；

（4）计算γ(red,D)，返回步骤2。

步骤4输出red。

3.2 局部近似质量约简

算法1在迭代过程中，求解属性重要度是依据全体样本所得到的近似质量差异，如式（9）。但这种重要度计算方法仅考虑的是决策系统中由所有决策类所生成下近似而得到的近似质量，忽略了每一个决策类别的下近似集在约简前后的变化程度。

然而在实际应用中，一些特殊的决策类往往会使得研究者更为关注。例如，为了得到更简洁的规则，可以从局部的视角出发，针对每一个决策类别进行约简[5,22]。鉴于此，以下给出局部近似质量的公式，用以量化地反映每一个决策类下近似集的大小，并在此基础上，进一步定义了基于局部近似质量的属性约简。

定义6给定一个决策系统DS,U/IND(D)={X1,X2,…,XN},∀B⊆AT,∀Xi∈U/IND(D)，类别Xi关于B的局部近似质量定义表示为：

定义7给定一个决策系统DS,∀B⊆AT,∀Xi∈U/IND(D)，B被称为一个局部近似质量约简当且仅当γ(B,Xi)≥γ(AT,Xi)且 ∀B′⊆B,γ(B′,Xi)＜γ(AT,Xi)。

式（10）描述的是在决策系统中第i类样本的近似质量，这是一种基于类别标记的局部近似质量。利用这一概念，可以构建第i个类别标记下的属性重要度公式形如：

求解局部近似质量约简的具体步骤如算法2所示。

算法2局部近似质量约简

输入：邻域决策系统DS=＜U,AT∪D＞，决策类Xi且Xi∈U/IND(D)，邻域半径参数δ。

输出：一个针对第i类标记的约简red。

步骤1red←∅,γ(red,Xi)=-∞，计算γ(AT,Xi)。

步骤2若γ(red,Xi)≥γ(AT,Xi)，则转步骤5，否则转步骤3。

步骤3（1）∀ai∈AT-red，计算Sig(ai,red,Xi)；

（2）选择aj，满足Sig(aj,red,Xi)=max{Sig(ai,red,Xi):∀ai∈AT-red}；

（3）令red=red∪{aj}；

（4）计算γ(red,Xi)，返回步骤2。

步骤4输出red。

3.3 局部多约束属性约简

算法2是选取单一度量准则作为求取约简的方法，但这一方法并不能保证所求得的约简能够同时满足两个或两个以上的约束条件。为解决这一问题，可以进一步地引入多个度量准则，文中以下再将局部条件熵作为约简的约束条件，使得约简在局部视角下满足多方面约束的条件。

定义8给定一个决策系统DS，论域U={x1,x2,…,xn},∀B⊆AT,D关于Xi的局部条件熵定义如下：

定义9给定一个决策系统DS，∀B⊆AT,∀Xi∈U/IND(D),B被称为一个局部多约束属性约简当且仅当：

（1）γ(B,Xi)≥γ(AT,Xi)且H(D|Xi)≤H(D|B)；

（2）∀B′⊆B,γ(B′,Xi)＜γ(AT,Xi)或H(D|Xi)＜H(D|B′)。

算法3详细介绍了求解局部多约束属性约简的算法。

算法3局部多约束属性约简算法

输入：邻域决策系统DS=＜U,AT∪D＞。

输出：属性约简red。

步骤 1red←∅,γ(red,Xi)=-∞,H(Xi|red)=∞，计算γ(AT,Xi),H(Xi|AT)。

步骤2若γ(red,Xi)≥γ(AT,Xi)且H(Xi|red)≤H(Xi|AT)，转步骤6，否则转步骤3。

步骤3∀ai∈AT-red，计算γ(red∪{ai},Xi),H(Xi|red∪{ai})。

步骤4若aj满足γ(red∪{aj},Xi)=max{γ(red∪{ai},Xi):∀ai∈AT-red};ak满足H(Xi|red∪{ak})=min{H(Xi|red∪{ai}):∀ai∈AT-red}。

步骤5选取am满足m=min(j,k)，令red=red∪{am}，计算γ(red,Xi)和H(Xi|red)，返回步骤2。

步骤6输出red。

在算法3的步骤5中，若所求得的aj=ak，则步骤5中的am=aj=ak，而若aj≠ak，则说明利用近似质量度量指标与条件熵度量指标所得到的属性有冲突，此时选取位置最靠前的属性加入到约简的属性集合中去。然后返回步骤2，判断属性集合是否同时满足近似质量和条件熵两个约束条件。若满足则输出red，否则算法继续。

4 实验分析

为了验证局部多约束属性约简的有效性，从UCI数据集中选择了6组数据，数据的基本描述如表1所列。实验环境为PC机，双核2.60 GHz CPU，8 GB内存，Windows 10操作系统，Matlab R2016a实验平台。

实验采用了5折交叉验证[23]的方法并且选取了10个不同的半径δ，值分别为0.03，0.06，…，0.3。5折交叉验证的具体过程是将实验数据中的样本平均分成5份，即U1,U2,…,U5，第一次使用U2∪U3∪…∪U5作为训练集求得约简red1，使用U1作为测试集并在其中利用red1求得近似质量与条件熵；第二次使用U1∪U3∪…∪U5作为训练集求得约简red2，使用U2作为测试集并在其中利用red2求得近似质量与条件熵；依次类推，第五次使用U1∪U2∪…∪U4作为训练集求得约简red5，使用U5作为测试集并在其中利用red5求得近似质量与条件熵。

本组实验选取了全局近似质量、局部近似质量以及局部多约束准则作为约简的度量标准[24-25]，在上述6组数据集上分别比较了基于这3种约简的近似质量与条件熵。实验结果如图1、图2所示。

观察图1可以发现，在10个半径下，针对每个决策类，利用3种约简在测试集上所求得的近似质量值相差并不大。因此不难得出如下结论：

（1）利用局部近似质量约简可以保证决策类的每个类别的近似质量能够满足属性约简准则。

（2）利用局部多约束约简依然可以满足全局近似质量约简与局部近似质量约简的约束条件。

（3）利用全局近似质量约简所得到的局部近似质量值并不一定占据优势，例如在“Seeds”数据集中，半径为0.15时，对于决策类X2来说，利用全局近似质量约简所得到X2的局部近似质量值为0.7，而利用X2的局部近似质量约简所得到的局部近似质量值为0.8。

根据图2，在10个半径下，利用全局近似质量约简所求得的条件熵往往低于利用局部近似质量约简所求得的条件熵，而利用局部多约束约简所求得的条件熵相较于利用全局近似质量所求得的条件熵来说，值更低。因此可以得出如下结论：

（1）局部近似质量约简不能有效地降低条件熵，因此不满足条件熵约简的约束条件。例如在“Wine”数据集中，对于决策类X2来说，利用局部近似质量约简所得到X2的局部条件熵明显要高于利用X2的全局近似质量约简和局部多约束约简所得到的局部条件熵。

（2）利用局部多约束准则约简可以有效地降低条件熵，因此满足条件熵约简的约束条件。

5 结束语

利用邻域粗糙集求解约简时，传统的近似质量约简是在考虑所有决策类的前提下进行，忽视了具体某种决策类别下近似质量的变化情形。并且基于单一准则的属性约简的结果虽然能够满足约束条件，但是不能保证其仍然满足其他度量准则下的约束条件。鉴于此，从局部视角出发，将局部近似质量与局部条件熵作为约简的多约束准则，利用启发式算法求解多约束约简。实验结果表明，该方法不仅可以保证决策类的近似质量满足约束条件，而且能够显著地降低条件熵，即仍然能够满足条件熵这一度量准则下的约束条件。

Table 1 Data sets description表1 数据集描述

Fig.1 Comparisons among approximate qualities with 3 different reductions图1 3种不同约简下近似质量对比

在此基础上，下一步将讨论由不同决策类生成的局部多约束约简之间的结构关系，同时为减少约简时间消耗寻求更高效的约简算法。

Fig.2 Comparisons among conditional entropies with 3 different reductions图2 3种不同约简下条件熵对比