作为一种处理不精确、不确定性问题的数学工具,粗糙集理论^[1] (rough set)由波兰学者Pawlak提出后便受到了广泛关注^[2-4]。然而由于数据测量的误差、数据获取的限制等原因,导致了所面临的信息系统往往是不完备的。为处理这类问题,王国胤^[5]提出了限制容差关系。进一步,杨习贝^[6]提出了一种新的基于可变精度分类的拓展粗糙集模型,对限制容差关系进行了改进。然而,在实际工程应用中,数据的获取是需要付出一些成本或代价的,称其为测试代价。针对该问题,Min等^[7-11]率先将测试代价引入到粗糙集的约简问题中，终究未能将测试代价引入到不完备信息系统环境下粗糙集本身的近似模型上。

1 基本概念

形式化地,信息系统可表示为四元组,其中U={x₁,x₂,…,x_m}为研究对象的有限集合,称为论域;A_T={a₁,a₂,…,a_n}为描述对象的全部属性所组成的集合;为属性集合A_T的值域,其中V_a为属性a的值域; 为信息函数,表示对每一个x∈U,a∈A_T,f(x,a)∈V_a。特别地,当信息系统中属性集A=A_T∪D且(其中A_T为条件属性集合,D为决策属性集合)时,信息系统也被称为决策系统。

定义1^[6] 设S为不完备信息系统,,由A决定的可变精度分类关系记为V_A^α,且

式中：P_A(x)={a∈A: f(x,a)已知},α∈[0,1],| X | 表示集合X的基数,I_U为恒等关系且。

定义2^[6] 设S为不完备信息系统,,对于任意的X⊆U,X基于可变精度分类关系V_A^α的下、上近似集合分别记为和:

式中：表示对象x的可变精度容差类。

2 测试代价与可变精度分类粗糙集

不完备信息系统环境下的粗糙集模型未考虑数据的代价问题,Min等^[8]将测试代价引入到信息系统中,具体的描述见定义3。

定义3^[8] 一个测试代价敏感的不完备决策系统TCSIIDS为一个五元组,U,A_T∪D,V和f的含义与第1节所示相同,为测试代价函数(R⁺表示正整数集),即,其中表示单个属性a_i的测试代价。本文假设所有属性的测试代价均为正整数,即,。

定义4 令TCSIIDS为测试代价敏感不完备决策系统,其中A⊆A_T,∀x,y∈U,∀a∈A,定义特征函数如下所示:

式中：P_a(x)={a∈A: f (x,a)已知}。

定义5 设TCSIIDS为测试代价敏感不完备决策系统,其中A⊆A_T,由A决定的可变精度分类关系记为且

其中：α∈[0,1]。

定义6 设TCSIIDS为测试代价敏感不完备决策系统,A⊆A_T,对于∀X⊆U,X基于可变精度分类关系的下、上近似集分别记为和

式中：表示在测试代价敏感不完备决策系统中对象x的可变精度容差类。

3 属性约简

属性约简是粗糙理论的主要研究内容之一。然而,寻找决策表的最小约简已被证明是一个NP-hard问题,在处理大规模数据时计算时间代价很大,针对这一问题,许多学者提出了许多高效的约简算法,启发式搜索方法就是其中的一个典型代表。

定义7 设TCSIIDS为测试代价敏感不完备决策系统,α∈[0,1],U/IND(D)={X₁,…X_n}表示根据决策属性得到的所有决策类的合集,那么U/IND(D)的近似质量可定义为

定理1 令TCSIIDS为测试代价敏感不完备决策系统,,若,则有

证明 根据定义6,定理1易证。

定义8 令TCSIIDS为测试代价敏感不完备决策系统,α∈[0, 1],A⊆AT为一个约简当且仅当且。

令TCSIIDS为测试代价敏感决策系统,α∈[0, 1],,的重要度为

可以看出,LSig_in(a_i,B,D)反映了a_i从当前条件属性集A中删除后近似质量的变化,相应地也可定义

式中：a_i∈A_T-A,LSig_out(a_i,A,D)用以度量向属性集A增加属性a_i后近似质量的变化。根据上述属性的重要度可以设计启发式属性约简算法。Min等在文献[11]中设计了传统的启发式算法(记为算法1)。其算法复杂度为。

Min等从获取约简的测试代价最小出发设计出新的约简算法,即回溯算法(记为算法2)。其算法复杂度为。详细算法见文献[11]。

3.1 考虑属性测试代价的启发式算法

由上文可知回溯算法的时间复杂度为。考虑到现实生活中存在着大量高维属性的数据,这样一种机制将会大大制约属性约简的时间。为解决这一问题,本文依然从启发式算法的角度出发,将属性的测试代价考虑到属性重要度定义中。为此,给出如下的属性融合重要度定义。

式中：θ≤0。可以看出,TCSLSig_in(a_i,A_T,D)是LSig_in(a_i,A_T,D)与之和。当θ=0时,无论属性的测试代价取何值,都有,这说明TCSLSig_in(a_i,A_T,D)的大小与属性测试代价的大小无关,仅与LSig_in(a_i,A_T,D)的值有关。随着θ值的不断减小,的值也不断减小(本文随机产生测试代价在[10,100]),此时在TCSLSig_in(a_i,A_T,D)中所占的比重也越来越小,表明属性测试代价在属性的重要度中的影响作用越来越小。根据新的属性融合重要度,不难设计出综合考虑了测试代价的启发式算法,具体算法流程见算法1。

算法1 基于测试代价敏感不完备决策系统TCSIIDS综合考虑测试代价的启发式算法

输入:测试代价敏感不完备决策系统TCSIIDS,α;

输出:约简red及约简的测试代价c^*(red)。

1)计算;令θ=0,;

2) ;

3) ,计算属性a_i的重要度TCSLSig_in(a_i,A_T,D);

4)若,则,计算;

5)若,则重复以下循环,否则转6);

①,计算TCSLSig_out(a_i,red,D);

②若,则;

6),若,则red=red-a_i,tmp=c^*(red);

7);

8)若θ大于给定阈值,则(此处δ为步长,δ>0)且重复2)~7),否则转9);

9)输出red及c^*(red)。

3.2 实验分析

本节将通过实验,对比算法1、算法2和算法3。表 1列出了实验中使用的4组测试数据的基本信息,所有数据集均下载于UCI数据集。由于UCI数据集中的大部分数据不含有测试代价,所以在本组实验中为每个数据集的属性随机增加了取值在[10,100]之间的测试代价。

由于基于测试代价敏感的可变精度分类粗糙集模型的下、上近似集由阈值α控制,因此,在实验中选取了10组不同的α值分别对比3个算法的测试代价,在算法3的第8步中,给定阈值设为-5,步长δ为0.5,即重复求得10次约简,取其中的最小测试代价作为输出。具体的实验结果见图 1。

由图 1的实验结果,可以得到: 1)传统的启发式算法所获取的约简的测试代价最大,回溯算法所约简的测试代价最小,而综合考虑测试代价的改进的启发式算法得到约简的测试代价则是基于两者之间。2)从图 1的4个子图可以发现,3种算法的测试代价随α值的不断增加呈现先增加达到一定峰值后再下降的大致趋势,从实验的角度可看出α值在这3个算法中发挥着调节正域的作用。

4 结束语

本文将测试代价引入不完备信息系统中,提出了基于测试代价敏感的可变精度分类粗糙集模型。进一步地,通过分析传统启发式约简算法未考虑测试代价以及回溯约简算法为获取最优测试需要消耗大量时间的不足,本文对传统属性重要度测量进行了改进,并根据新的属性重要度测量设计了一种新的启发式算法用以获取测试代价次优的约简。实验表明,总体而言,改进的启发式算法是寻找约简测试代价次优的合适方法。