决策代价约简求解中的交叉验证策略

doi:10.13232/j.cnki.jnju.2019.04.010

决策代价约简求解中的交叉验证策略

张龙波¹, 李智远¹, 杨习贝^,², 王怡博³

1. 江苏师范大学科文学院，徐州，221116

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

3. 东南大学计算机科学与工程学院，南京，211189

Cross⁃validation strategy in attribute reduction based on decision cost

Zhang Longbo¹, Li Zhiyuan¹, Yang Xibei^,², Wang Yibo³

1. Kewen College, Jiangsu Normal University, Xuzhou, 221116, China

2. School of Computer, Jiangsu University of Science and Technology, Zhenjiang, 212003, China

3. School of Computer Science and Engineering, Southeast University, Nanjing, 211189, China

通讯作者: E⁃mail:zhenjiangyangxibei@163.com

收稿日期: 2019-05-28 网络出版日期: 2019-07-17

基金资助:

国家自然科学基金. 61572242,61502211,61503160

Received: 2019-05-28 Online: 2019-07-17

摘要

属性约简是粗糙集理论中的核心问题，其目的是剔除冗余属性以找到具有较好泛化能力的属性子集.在决策粗糙集理论中，决策代价经常被作为属性约简的约束条件.但值得注意的是，虽然基于决策代价的约简求解算法可以有效地降低训练样本集上的总决策代价，但其往往忽视了测试样本集上的总决策代价.为解决这一问题，利用交叉验证的基本思想，设计了以决策代价为约束条件的一种新的属性约简求解算法.在八个UCI数据集上的实验结果表明，相较于传统基于决策代价的约简求解算法，所提算法不仅能有效地降低训练集合和测试集合的总决策代价，而且找出的属性子集亦可以带来更好的分类性能.

关键词： 决策粗糙集 ; 属性约简 ; 交叉验证 ; 代价敏感

Abstract

Attribute reduction is a core problem in rough set theory,with its purpose of getting rid of redundant attributes to obtain a reduct with better generalized performance. In decision⁃theoretic rough set,the decision cost is frequently regarded as constraint of attribute reduction. However,it is worthy to notice that although the reduct obtained by the algorithm based on the consideration of decision cost can effectively reduce the decision cost of the training set,it may fails to effectively reduce the decision cost of the test set. To solve such problem,a new algorithm, based on the method of cross⁃validation,is designed through using the decision cost as constraint. The experimental result over eight UCI data sets show that compared with the traditional algorithm based on decision cost,the proposed algorithm not only reduces the decision cost of training set and the test set,but also brings better classification performance.

Keywords： decision⁃theoretic rough set ; attribute reduction ; cross⁃validation ; cost⁃sensitive

PDF (1895KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

张龙波, 李智远, 杨习贝, 王怡博. 决策代价约简求解中的交叉验证策略. 南京大学学报(自然科学版)[J], 2019, 55(4): 601-608 doi:10.13232/j.cnki.jnju.2019.04.010

Zhang Longbo, Li Zhiyuan, Yang Xibei, Wang Yibo. Cross⁃validation strategy in attribute reduction based on decision cost. Journal of nanjing University(Natural Science)[J], 2019, 55(4): 601-608 doi:10.13232/j.cnki.jnju.2019.04.010

粗糙集理论^[1]是波兰学者Pawlak提出的一种处理不确定、不精确信息系统的数学工具，被广泛地应用于机器学习^[2,3,4]、粒计算^[5]、模式识别^[6,7]和知识发现^[8,9]等领域.属性约简^{[10,11,12,13,14,15,16]}作为一种数据处理的方法，是粗糙集理论中的核心问题.通过属性约简，不仅可以从数据集中剔除冗余属性来获得更简洁的规则，而且相对于其他特征选择方法，所求得的特征子集往往具有明确的语义解释.

随着对粗糙集理论研究的不断深入，

Pawlak粗糙集模型在容错能力上的缺陷^[17]逐渐引起了广大学者的注意.为了克服这一缺陷，加拿大学者Yao et al^[18]提出了基于贝叶斯风险分析的决策粗糙集模型.该模型主要有两大优势^[19]：(1)决策粗糙集模型重新定义粗糙集的正域、边界域和负域，给予传统粗糙集模型全新的解释，丰富了传统决策方法；(2)决策粗糙集理论通过构建代价矩阵获取概率粗糙集所需要的一对阈值，引入损失函数，将粗糙集方法和代价敏感问题联系到一起.

近年来，以代价敏感^[20]为基础的属性约简问题越来越受到粗糙集学者的关注,他们将各式各样的策略运用到基于代价敏感的属性约简问题当中.相对于时间复杂度较高的穷举法^[21,22]，基于适应度函数的启发式搜索方法^[23,24]因具有较高的求解速度和普适性，被广泛地运用到面向代价敏感的属性约简问题中，但值得注意的是，根据启发式方法搜索出的属性子集往往仅能降低训练样本集上的决策代价，但却未必能够有效地保证测试样本集上的决策代价也能够被降低.鉴于此，本文试图将交叉验证^[25,26]的思想引入到属性约简当中，其目的是在训练样本集上的搜索进程中设置一个早停止策略，一旦决策代价不能够被降低了，则立即停止搜索.这一模式在训练样本集上模拟了测试样本的代价变化情况，证明它不仅进一步降低了训练集合的决策代价，而且能有效地测试集合的决策代价，从代价敏感的角度提高了属性子集的泛化能力.

1 决策粗糙集

经典的决策粗糙集理论是建立在两个状态与三个行动基础上^[18]的.一般的，定义状态集合Ω={X，~X}表示两种状态：对象x属于集合X和对象x不属于集合X；定义行动集A={a_P,a_B,a_N}，a_P,a_B,a_N分别表示对象x属于集合X的正域、边界域、负域.此时，若考虑对象x属于某个状态时，做出某个动作所需的代价函数值，则可以定义如下表1所示的代价矩阵.

表1 决策粗糙集中的代价矩阵

Table 1 Cost matrix in decision⁃theoretic rough set

	X	~X
a_P	λ_PP	λ_PN
a_B	λ_BP	λ_BN
a_N	λ_NP	λ_NN

新窗口打开| 下载CSV

表1中，λ_PP，λ_BP和λ_NP分别表示当对象x属于集合X时，采取行动a_P,a_B,a_N付出的代价；λ_PN，λ_BN和λ_NN分别表示当对象x属于集合~X时，采取行动a_P,a_B,a_N付出的代价.根据代价函数值的定义，显然有如下关系：0≤λ_PP≤λ_BP≤λ_NP，0≤λ_NN≤λ_BN≤λ_PN.在决策粗糙集理论中，根据贝叶斯最小风险决策原则可以得到如下三种决策规则：

(1)若 $P r (X | {[x]}_{A T}) \geq α$ ，则 $x \in P O S (X)$ ；

（2）若 $β < P r (X | {[x]}_{A T}) < α$ ，则 $x \in$ $B N D (X)$ ；

（3）若 $P r (X | {[x]}_{A T}) \leq β$ ，则 $x \in N E G (X)$ .

其中，

α = \frac{λ_{P N} - λ_{B N}}{(λ_{P N} - λ_{B N}) + (λ_{B P} - λ_{P P})}

β = \frac{λ_{B N} - λ_{N N}}{(λ_{B N} - λ_{N N}) + (λ_{N P} - λ_{B P})}

且α，β满足关系： $0 \leq β < α \leq 1$ .

一般的，在粗糙集理论中，一个决策系统可被记为：

D S = 〈U, A T ⋃ \{d\}〉

其中，U是所有样本组成的非空集合，称为论域；AT是所有条件属性组成的集合；{d}是决策属性组成的集合.根据如上所示三种决策规则，∀A⊇AT，则可以定义决策粗糙集的下近似集和上近似集分别为：

\underset{̲}{N_{A}} (X) = \{x_{i} \in U : P r (X | [x_{i}]_{A}) \geq α\}

(1)

\bar{N_{A}} (X) = \{x_{i} \in U : P r (X | [x_{i}]_{A}) > β\}

(2)

其中，

{[x_{i}]}_{A} = \{y \in U : (x_{i}, y) \in I N D (A)\}

因此，不难得出X的正域为:

P O S_{A} (X) = \underset{̲}{N_{A}} (X)

X的边界域为:

B N D_{A} (X) = \bar{N_{A}} (X) - \underset{̲}{N_{A}} (X)

X的负域为:

N E G_{A} (X) = U - \bar{N_{A}} (X)

至此，根据相应的决策规则，可以计算得该决策系统的总决策代价. $\forall A \subseteq A T$ 有：

\begin{matrix} C O S T_{A} = C O S T_{A}^{P O S} + C O S T_{A}^{B N D} + C O S T_{A}^{N E G} = \\ \overset{t}{\sum_{j = 1}} \sum_{x_{_{i}} \in P O S_{A} (X)} P r (X_{j} | [x_{i}]_{A}) \cdot λ_{P P} + (1 - P r (X_{j} | [x_{i}]_{A})) \cdot λ_{P N} + \\ \overset{t}{\sum_{j = 1}} \sum_{x_{_{i}} \in B N D_{A} (X)} P r (X_{j} | [x_{i}]_{A}) \cdot λ_{B P} + (1 - P r (X_{j} | [x_{i}]_{A})) \cdot λ_{B N} + \\ \overset{t}{\sum_{j = 1}} \sum_{x_{_{i}} \in N E G_{A} (X)} P r (X_{j} | [x_{i}]_{A}) \cdot λ_{N P} + (1 - P r (X_{j} | [x_{i}]_{A})) \cdot λ_{N N} \end{matrix}

(3)

2 基于决策代价的启发式约简

属性约简是粗糙集理论中的一个核心问题，其本质是在受一定约束条件约束的前期下，删除条件属性中一定的冗余的属性，得到满足约束条件的最小条件属性子集.本文以决策代价为基础，对属性约简的方法进行讨论.

定义1 给定决策系统DS, $\forall A \subseteq A T$ ,A被称为AT的一个决策代价约简当且仅当：

\begin{array}{l} (1) C O S T_{A} \leq C O S T_{A T}; \\ (2) \forall B \subset A, C O S T_{B} > C O S T_{A} . \end{array}

定义2 给定决策系统DS, $\forall A \subseteq A T,$ $\forall a \in A T - A,$ 属性a的重要度函数定义为：

S i g (U, a, A) = C O S T_{A ⋃ \{a\}} - C O S T_{A}

(4)

定义1的约简保证总决策代价不会增加最小条件属性子集.定义2的重要度函数Sig(U,a,A)表示属性a加入集合A后该决策系统总决策代价的变化.加入属性a后有 $C O S T_{A ⋃ \{a\}} \leq$

$C O S T_{A}$ 则表示属性a对总决策代价的降低做出了贡献；否则属性a为冗余属性.

当前，已有许多学者给出多种求解约简的算法.相对于基于穷举法的求解约简算法，启发式算法因具有较高的求解效率，所以广受青睐.根据定义2中重要度函数的定义，给出启发

式算法求解约简的一般步骤.

算法1 基于决策代价的启发式算法

输入：决策系统 $D S = 〈U, A T ⋃ \{d\}〉$ ,邻域半径

输出：约简A

步骤1 $A = ϕ$ ;

步骤2 $\forall a_{i} \in A T - A$ ,计算：

S i g (U, a, A) = C O S T_{A ⋃ \{a\}} - C O S T_{A}

定义 $C O S T_{ϕ} = 0$ ;

步骤3 选择特征b满足：

S i g (U, b, A) = m i n \{\forall a_{i} \in A T - A : S i g (U, a_{i}, A\}

；

步骤4 若 $S i g (a_{k}, A) < 0$ ,则 $A = A ⋃ \{b\}$ ,转到步骤2，否则转到步骤5;

步骤5 Do $\forall a \in A$ ,计算 $C O S T_{A - \{a\}}$ ;

If $C O S T_{A - \{a\}} \leq C O S T_{A}$

A = A - \{a\}

Until $C O S T_{A - \{a\}} \geq C O S T_{A}$ ；

步骤6 输出约简集合A.

算法1的时间复杂度是 $O (| U |^{2} \cdot | A T |^{2})$ ,|U|是样本的总个数，|AT|是条件属性的总个数.

3 基于交叉验证思想的决策代价约简

尽管基于决策代价的启发式约简方法具有较高的求解效率，但是这种算法求解出来的属性子集往往只能有效地降低训练集合的总决策代价，却经常不能有效地降低测试集合的总决策代价.为了解决上述算法不能有效地降低测试集合总决策代价的问题，本文将交叉验证的思想引入到属性约简当中，具体设计如算法2所示.

算法2 基于交叉验证思想的决策代价约简算法

输入：决策系统 $D S = 〈U, A T ⋃ \{d\}〉$ ，邻域半径δ，交叉折数k

输出：约简A

步骤1 $A = ϕ$ ；

步骤2 将样本集合分为k个部分：T₁,T₂,…,T_k;

步骤3 For j=1 to k

(1) 令 U_{t r a i n}^{j} = U - T_{j}

；

(2) \forall a_{i} \in A T - A, 计 算 S i g (U_{t r a i n}^{j},

a_{i}, A)

；

End For

步骤4 $\forall a_{i} \in A T - A$ ，计算：

m e a n (a_{i}) = \frac{\overset{k}{\sum_{j = 1}} S i g (U_{t r a i n}^{j}, a_{i}, A)}{k}

；

步骤5 选择特征b满足：

S i g (b, A) = m i n \{\forall a_{i} \in A T - A : m e a n (a_{i})\}

;

步骤6 For j=1 to k

令 $U_{t e s t} = T_{j}$

计算 $C O S T_{A ⋃ \{b\}} (T_{j})$ 和 $C O S T_{A} (T_{j})$

定义 $C O S T_{ϕ} (T_{j}) = i n f$ ;

End For

步骤7 (1)计算：

C O S T_{A ⋃ \{b\}}^{t e s t} = \frac{\overset{k}{\sum_{j = 1}} C O S T_{A ⋃ \{b\}} (T_{j})}{k}

和

C O S T_{A}^{t e s t} = \frac{\overset{k}{\sum_{j = 1}} C O S T_{A} (T_{j})}{k}

(2)若 $C O S T_{A \cup {b}}^{t e s t} \leq C O S T_{A}^{t e s t}$ ，则 $A = A ⋃ \{b\}$ 转到步骤3，否则转到步骤8;

步骤8 输出约简集合A.

算法2的时间复杂度是 $O (k \cdot | U |^{2} \cdot | A T |^{2})$ ,其中k是交叉验证的折数，|U|是样本的总个数，|AT|是条件属性的总个数.算法2在传统启发式决策代价约简的基础上引入了交叉验证的思想，其目的是期望约简集合可以有效地降低测试集合总决策代价.

4 实验分析

为了验证所提算法的有效性，选择UCI上的八组数据集合进行了实验验证.这八组数据的基本描述如表2所示.实验的硬件配置为Windows 10操作系统，2.50 GHz CPU, 8 G内存的个人计算机，用Matlab 2017a实现算法.

表2 数据集的描述

Table 2 Description of datasets

ID	数据集	样本个数	属性个数	决策类个数
1	Breast Tissue	106	9	6
2	Connectionist Bench (Vowel Recognition⁃Deterding Data)	990	14	11
3	Dermatology	366	34	6
4	Ecoli	336	7	8
5	Forest	523	27	4
6	Ionosphere	351	34	2
7	Statlog(Vehicle⁃Silhouettes)	846	19	4
8	Urban Land Cover	675	147	9

新窗口打开| 下载CSV

在邻域粗糙集的框架下，选择10个不同的半径，半径的值分别是0.03，0.06，…，0.30.为了对比所提算法的有效性，采用五折交叉验证.该方法的具体操作流程是：用分层抽样的方法尽可能保证数据分布的一致性，将样本集合中的样本平均分为五份，即U₁,U₂,…,U₅；第一次将U₂∪U₃∪U₄∪U₅作为训练集，U₁作为测试集，分别求得两种算法在该半径下的约简集合；……；第五次将U₁∪U₂∪U₃∪U₄作为训练集，U₅作为测试集，分别求得两种算法在该半径下的约简集合.

4.1　分类精度和约简长度对比

实验使用KNN分类器(K值取5)、SVM分类器、CART分类器分别求解两种算法在测试集合上的分类精度，同时用对分类精度和约简长度取算术平均值方法求得最终实验结果，实验结果如表3所示，表中黑体字表示较高的分类精度或者较大的约简长度.

表3 分类精度和约简长度对比

Table 3 Classification accuracies and lengths of feature subsets

ID	KNN		SVM		CART		约简长度
ID	算法1	算法2	算法1	算法2	算法1	算法2	算法1	算法2
1	0.6087	0.6043	0.5315	0.5387	0.6147	0.6318	2.14	2.58
2	0.8652	0.9196	0.5290	0.5384	0.7230	0.7565	5.78	9.82
3	0.8944	0.9185	0.9002	0.9270	0.8956	0.9300	5.70	7.44
4	0.8154	0.8647	0.8068	0.8381	0.7721	0.8078	4.28	5.64
5	0.8152	0.8458	0.8223	0.8380	0.7816	0.8003	2.82	4.64
6	0.8958	0.8975	0.8581	0.8618	0.8538	0.8806	2.32	3.80
7	0.6351	0.6672	0.5316	0.5507	0.6117	0.6477	3.42	5.04
8	0.7874	0.8163	0.7453	0.7914	0.7671	0.7982	3.30	4.78

新窗口打开| 下载CSV

观察表3，不难得到如下结论：

(1)相比于算法1，算法2求解出来的属性子集具有更好的分类性能.在KNN,SVM,CART三种分类器上的求解出的分类精度均普遍高于算法1.

(2)相对于算法1，算法2求解出来的属性子集具有较多的属性.

4.2　总决策代价对比

观察图1，不难发现，基于决策代价的启发式约简算法求解出的属性子集虽然在训练集合上可以有效地降低总决策代价，但当属性子集作用于测试集合时会出现不能有效降低总决策代价的情况.例如，数据集“Ecoli”在半径大于0.15时，基于决策代价的启发式约简算法求得的属性子集明显不能有效降低总决策代价.而相比于算法1，运用交叉验证思想的算法2求解出来的属性子集不仅进一步降低了训练集合的总决策代价，而且更加有效地降低了测试集合的决策总代价.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 两种算法的总决策代价对比

Fig.1 Decision cost of two algorithms

此外，值得注意的是，根据图1所示的结果，可以观察到：随着半径的增大，无论是利用所有属性，还是利用算法1或算法2所选择出来的属性子集，在训练样本以及测试样本上所求得的总决策代价都会相应地增加.这主要是因为随着半径的增大，决策粗糙集中的正域会进一步地缩减，而边界域和负域则会相应地扩张.又根据表1，边界域和负域中样本所对应的决策代价显然要大于正域样本所对应的决策代价，因此带来了总决策代价的增高.

4.3　时间消耗对比

从表4和两种算法的时间复杂度可以看到，算法2求解约简的时间明显长于算法1，这主要是因为算法2在求解属性子集的时候将数据集分成k部分，用交叉验证的方法会大幅度增加算法迭代次数，因此算法2具有较大的时间消耗.

表4 两种算法的时间消耗对比

Table 4 Time consumption of two algorithms

ID	算法1	算法2
1	0.0676	0.3095
2	3.6052	21.7105
3	2.0940	11.3334
4	0.2941	1.2293
5	1.5900	8.2857
6	0.9510	4.7678
7	1.6639	9.9960
8	10.4979	149.1929

新窗口打开| 下载CSV

5 结束语

决策粗糙集理论将粗糙集和代价敏感问题联系到一起，有效地丰富了粗糙集理论.基于决策代价的启发式约简算法，虽然具有较高的求解效率，但在测试集合上经常会出现不能有效地降低总决策代价的情况.鉴于此，结合交叉验证思想，本文基于决策代价设计了新的算法.通过实验对比分析可以看出，所提的新算法能够显著地降低测试集合的总决策代价，提高约简结果的分类精度.因而，基于交叉验证思想的决策代价约简算法是有效的.

在本文工作的基础上，笔者将就以下的问题进行进一步探讨：

(1)本文将交叉验证思想运用到基于决策代价的属性约简算法中，可以将该思想运用到其他约简算法当中，提高其他算法的有效性.

(2)虽然本文算法能有效降低测试集合的总决策代价，但是具有较大的时间消耗.笔者将进一步优化算法，减少算法的时间消耗.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Pawlak

Rough sets

International Journal of Computer & Information Sciences，1982，11(1)：341-356.