可变精度邻域区间值决策表的属性约简

徐伟华，李思琪

(西南大学 人工智能学院，重庆 400715)

1965年,Zadeh首次提出了模糊集的概念[1],标志着模糊数学的诞生。 该学科在1995年被ACM列为新兴的计算机科学研究领域,如今正在继续发展。 因其建立在分类基础上,可以有效处理不完整不确定问题，所以在实践中广泛应用[2]。同时,区间值决策表[3-4]作为一个分支,能很好描绘不精确对象的特征,在医学、金融、机械制造等领域意义重大。Lin和Hu在Zadeh的知识粒化的基础上将邻域引入粗糙集,以粗糙集理论为基础,衍生出了邻域粗糙集理论。 该理论重新定义上下近似,实现了一种全新的近似逼近。 邻域粗糙集理论已经广泛应用在决策分析、过程控制以及模式识别等[5-9]领域。

在使用过程中需要对属性值进行属性约简。 属性约简是粗糙集理论研究的核心问题之一,决策表中有一些条件属性,由于其属性值难以测量或测量这些属性值花费极高,需要将之删去。 在保持分类水平不变的情况下,尽力删除这些冗余属性,使剩余属性达到最简,以降低统计难度。 这就是属性约简。 事实上,寻找约简集合[10-13]是 NP-hard 问题,解决这类问题一般是采用启发式搜索以获得近似解。

然而,属性约简后的属性值不可避免会丢失部分原始数据,导致一定程度的信息缺失,限制了粗糙集的应用范围,为了解决这个问题,前人用邻域关系代替等价关系，重新定义上下近似与正域,建立了可变精度邻域决策表[14-15]及相应的属性约简算法。 但是现实生活中,区间值决策表应用范围更加广泛。 如果能将这种方法推广到区间值决策表,会得到更广泛的应用。

为此,本文将经典可变精度邻域信息决策表推广到区间值信息决策表上,定义区间距离以用于计算邻域,用可变精度阈值计算出条件的正域,对信息表进行属性约简。并以属性质量度为判断依据,设计相应启发式属性约简算法。最后，通过实验验证了算法的正确性。

1 基本概念

本节将介绍可变精度邻域决策表以及区间值信息决策表的相关概念。

1.1 可变精度邻域决策表

一个决策表[2]可表示为二元组DT=〈U，AT∪d〉,其中非空有限集合U={x1,x2,…,xn}为对象集,称为全域或样本空间,AT表示一个非空的有限条件属性集合,用于描述U的实数型特征,d是决策属性。

∀x∈U，∀a∈AT,a(x)表示样本x在属性a上的取值,而d(x)为样本x在决策属性d上的值,U/d={X1,X2,…,Xm}代表U被决策属性d划分出的决策类。

给定一个决策表DT=〈U,AT∪d〉,且邻域半径δ∈(0,1),则对于∀x∈U,邻域δ(x)定义为

δ(x)={xj|xj∈U,Δ(x,xj)≤δ,δ>0},

其中，Δ(x,xj)代表对象x和xj之间的距离。

给定一个决策表DT= 〈U,AT∪d〉，设集合X⊆U，集合Y⊆U，则X关于Y的错误分类率可表示为

定义1给定一个邻域信息决策表NDT=〈U，AT∪d〉，该决策表中有m个等价类U/d={X1,X2,…,Xm}。对于∀B⊆AT，引入可变精度的正确率阈值α(0.5≤α≤1)。则该精度下邻域信息决策表相对于决策属性d的上近似为

下近似为

正域为

其中：

传统意义的邻域决策表在定义上下近似时并未考虑容错率,因此对错误的分类非常敏感。为了更好地处理不确定关系以及减少噪声干扰,更常使用具有一定容错性的可变精度邻域决策表。

如上文所示,可变精度邻域粗糙集的上下近似是基于α的容错划分,通过增大α的值,使之具有更好的覆盖率。α越小,正域将扩大,容错率也变大;相反的,α越大,正域越小,容错率越小,上下近似越精确。 我们需要选择一个合适的α,使决策表具有良好辨识性的同时,保证一定容错率。

1.2 区间值信息决策表

一个区间值决策表可以表示为IVDT=〈U， AT∪d,VAT,f〉, 其中， 决策属性d的取值同经典情况(即单值, 而非区间值)。Va为任意条件属性a∈vAT的值域,那么其条件属性值域VAT=∪a∈ATVa。信息函数f:U×AT→VAT满足∀xi∈U,∀a∈AT,且f(xi,a)为一个区间值。

定义2设有两个不同的区间A与B，区间A=[a-,a+],B=[b-,b+]。则A区间相对于B区间的优势度定义为

由该定义易知，

1)PA≥B≠PB≥A；

2) 0≤PA≥B≤1；

3)PA≥B+PB≥A=1；

4)PA≥A=0.5。

即2个对象在条件集AT下的欧氏距离,通过这个关系,可以将区间值决策表与邻域可变精度决策表结合到一起。显然,它满足如下关系，

1) Δ(x,x)=0;

2) Δ(x,y)=Δ(y,x);

3) Δ(x,z)≤Δ(x,y)+Δ(y,z)。

2 变精度邻域区间决策表属性约简

本节将可变精度邻域粗糙集引入区间值信息决策表,并提出该决策表的约简方式。

2.1 属性质量度

给定一个区间值邻域决策表INDT=〈U,

AT∪d〉,其中,∀B⊆AT,∀a∈AT-B，且X是由决策属性d划分而出的等价类。现有xi∈PosB∪{a}(d),xj∈PosB(d),则属性a相对于属性子集B的平均正确分类率的增量函数定义为

即正域改变前后其内所有样本正确分类率求和取均值后的增量,显然有

区间值邻域决策表INDT=〈U,AT∪d〉，B⊆AT，若a∈AT-B,则a相对于属性子集B关于决策属性d的正域增量函数，可用正域与全域基数之比的增量表示,即文献[13]中定义的属性重要性,其定义为

即增加属性a前后正域的相对改变量,显然有

定义4区间值邻域决策表INDT=〈U,

AT∪d〉,若∀B⊆AT,∀a∈AT-B,则a相对于属性子集B关于决策属性d的属性质量度可以定义如下，

2.2 属性约简

给定区间值邻域决策表INDT=〈U,AT∪d〉,若red是AT的一个约简集合,对于∀a∈red，red需满足

1) Posred-{a}(d)

2) Posred(d)=PosAT(d)。

属性质量度函数是正域增量与正确分类率增量的乘积,因此可以用属性质量度表示这种正域的变化。 即,若∀b∈AT-red,以上关系也可表示为

即red中任意一个属性都是必不可少的,而red以外任意一个属性对red都是冗余的。 这与经典集的定义是几乎一致的,只是增加了数值粒化而已。 这样可以保证约简red与全部条件属性具有相同的分辨能力的同时达到最精简。

给定区间值邻域决表INDT=〈U,AT∪d〉,若B1,B2,…,Bn是该表的全部约简集合,则称∩i≤nBi为此信息决策表的核。

3 案例分析

为了说明上一节属性约简的具体机理,本节给出一个具体案例以进行详细分析。

现从一个信息表中中抽取8个数据组成一个小型区间值信息决策表INDT=〈U,AT∪d〉,U={x1,x2,x3,x4,x5,x6,x7,x8},决策属性d={Rainfall}(Y代表降雨,N代表未降雨)。条件集AT={Vegetation,Humidity,Airflow Rainfall}。 为方便后续计算,以首字母简写代替。 并对其进行归一化,将区间值映射到[0,1],处理后的信息决策表见表1。

表1 关于降雨的影响因素的信息决策表

若选取邻域为δ=0.3,正确率阈值α=0.8,以此表为实例进行计算。依次计算所有属性子集的邻域,如表2所示。

表2 所有属性子集的邻域

根据表1,决策属性Rainfall将论域划分为2个等价类:X1={x1，x4，x5，x6，x8},X2={x2,x3,x7},初始化约简集合red=∅。

根据前文的定义,首先分别求得3个条件及条件全集的正域，

Pos{V}(R)={x1，x3，x4，x5，x6，x7，x8}，

Pos{H}(R)={x1，x3，x4，x5，x7，x8}，

Pos{A}(R)={x1，x3，x4，x5，x6，x7，x8}，

Pos{AT}(R)={x1，x2，x3，x4，x5，x6，x7，x8}。

进一步可求出3个条件的属性质量度，

根据计算结果,选取属性质量度最高的条件V或A,即red1={V},red2={A}。

如果选取red1为约简集合,再分别计算{V,H}、{V，A}的正域，

Pos{V,H}(R)={x1，x2，x3，x4，x5，x6，x7，x8}；

Pos{V,A}(R)={x1，x3，x4，x5，x6，x7，x8}。

再分别计算条件H与条件A相对与red1的属性质量度，

说明条件A对于red1是冗余的,选取属性质量度最大的条件H将其加入到约简集合red1。

又因Pos{V,H}(R)=PosAT(R),即正域不再发生变化,所以red1={Vegetation,Humidity}即为约简集合。

同理,可求出red2={Humidity,Airflow}也是一个约简集合,2个约简集合的交集{Humidity}为该信息表的核。结果如表3所示。

表3 约简集合及核

4 算法设计与数值实验

4.1 算法设计及时间复杂度分析

具体算法如算法1所示。

算法1关于可变精度邻域区间值决策表属性约简的启发式算法

输入 区间邻域决策表 IVDT= 〈U,AT∪d〉，可变精度阈值α，邻域取值δ。

输出 属性约简集合 red。

1) begin

2) computeU/d={X1,X2,…,Xm};

3) red←∅;Qmax←0; /*初始化约简集合和属性质量度*/

4) fora∈AT - red do

5) forx∈Udo

6) computeδ(x);/*计算全体对象在{a}∪red下的邻域*/

7) end

12) end

13) end

14) ifQmax>0 then

15) red←red ∪{amax}; /*属性质量度最大的属性被加入约简集合*/

16) goto 4;

17) else

18) return red;

19) end

20) end

接下来分析该算法的时间复杂度。在该算法中,循环体主要应用于求解邻域与计算条件的属性质量度中。 假设一共有n个条件,最后得到的约简集合中条件m个,在此时刻约简了k个条件。

计算属性质量度时,求出每个条件的正域需要循环(n-k)×|U|次,求出各条件的属性质量度需要循环(n-k)次,这两个循环是线性关系,所以时间复杂度为O(n×|U|)。

将新属性添加至约简集合的循环需要经历(m+1)次,时间复杂度为O(n)。

综上,时间复杂度为O(n2×|U|2)。

4.2 实验数据与实验环境

为了验证算法的正确性,本次实验选用UCI库上的4个分类数据集。

首先将非数值型的特征值替换为数值型,对数据使用Min-Max归一化将值映射到[0,1]区间,以消除量纲影响,随后将其按照下列方法转换为区间值信息决策表,使用算法对其进行属性约简。

此外,为验证算法有效性,我们对其约简前后的分类能力做了对比,按照8∶2的比例划分训练集和测试集,并且选用支持向量机(SVM)与梯度提升模型(GBDT)对其进行验证。选用的数据集信息如表4所示。

表4 数据集描述

4.3 实验结果分析

实验研究了算法在不同邻域阈值δ(0.4～0.6)和不同可变精度阈值α(0.6～0.9)下得出的约简集合以及约简前后分类预测准确率的变化。比较分类精度变化需要对样本进行机器学习,此时选取的邻域和变精度为

σ=0.5,α=0.7

以此判断约简集合是否可以近似代表整个系统的信息。

图1反应了约简前后的数据集在支持向量机(SVM)和梯度提升决策树(GBDT)下的分类准确率的变化。表5为在上述参数下约简前后的准确率。实验结果表明,约简后的分类准确率均不小于约简前的准确率。 说明算法选择的属性可以有效地近似数据集的分类能力。

表5 一定条件下约简前后的分类精度

图1 4种数据集约简前后的准确率

表6为4个数据集使用本文的方法得出的约简集,其中的元素是决策属性的序号,可见在某些条件下约简集合不止一个。

表6 数据集的约简集结果

同时,本文选2两种约简算法作为对比算法,分别是来自参考文献[3]中的RDAR算法和误分代价算法,比较了3种约简算法的准确率,结果如图2所示。可见本文算法在4个数据集上的准确率基本大于另外2种算法。

图2 3种约简算法准确率

5 结语

本文在基于可变精度邻域关系的区间值决策信息表的模型下,提出区间距离计算公式,并基于此提出该信息表中上下近似、核和正域的概念。 同时,为了删除在数据采集过程中存在的一些不必要的条件属性,本文使用正域以及分类正确率的变化定义了属性质量度,设计了一种启发式属性约简算法,并通过实验验证了该算法的有效性。实验结果表明,该算法选择的属性可以近似原数据集的分类能力。