区间值决策表中基于相对知识粒度的属性约简

唐鹏飞，莫智文，谢 鑫

(四川师范大学 a.数学科学学院；b.智能信息与量子信息研究所， 成都 610066)

粗糙集理论是不确定性分析与智能计算的有效数学工具[1]。在粗糙集理论中，属性约简是核心内容与研究热点，其主要是在保持相同分类能力的前提下进行冗余属性删除，从而达到数据表的优化处理。知识粒度广泛用于不确定性测量、属性约简、机器学习。针对经典信息(决策)表，文献[2-3]提出基于知识粒度的属性约简，而文献[4-7]在不同决策信息系统下推广并改进基于知识粒度的属性约简；文献[8]从多粒度视角提出基于知识粒度的增量属性约简。寻找最小属性约简问题是NP难题[9]，因此启发式约简算法构建成为一种有效优化策略。例如文献[10]提出邻域近似条件熵来构建启发式约简算法；文献[11]利用粗糙集理论设计基于依赖计算的启发式约简算法；文献[12]提出近似质量来构建启发式约简算法；文献[13]引入广义决策保持相似度构建启发式约简算法。可见，知识粒度与启发式算法是决策表进行属性约简的重要手段，值得推广使用。

区间值决策表[14]是经典决策表的一种扩展，其属性值为区间值(即用上下边界来表示一个不确定概念)，从而能更好地刻画不确定性对象，当前具有深入研究。例如，文献[15]基于相似关系，将近似精度和近似粗糙度推广到区间值决策表中，研究了不确定性度量问题；文献[16]基于信息熵研究了区间值信息(决策)系统的属性约简，并提出2个启发式约简算法；文献[17]针对不完备区间值信息系统，提出基于弱相似关系的不确定性度量；文献[18]提出区间值决策系统的特定类分布属性约简；文献[19]针对区间值信息系统，基于相似等价关系提出一种非监督的属性约简算法。特别地，文献[20]从代数角度，提出基于正域的区间值决策表属性约简及其启发式约简算法。

综上，区间值决策表的属性约简研究是有意义的，但基本的相对知识粒度较少被涉及，而其相关引入可以提供直接而有效属性约简手段。由此，本文基于相似关系[15]，定义区间相对知识粒度及区间属性重要度等概念，建立基于区间相对知识粒度的属性约简及其启发式约简算法，并提供实例分析。相关工作将推广相对知识粒度的使用，并从粒计算视角提供一种新的属性约简策略。

1 预备知识

本节首先复习基于相对知识粒度的经典决策表属性约简，再预备区间值决策表的基本概念。

1.1 基于相对知识粒度的经典决策表属性约简

经典决策表DT={U，AT=C∪d，V,f}，其中U为一个有限非空对象集合，称为论域；AT为属性集，其中C为有限条件属性集，d为有限决策属性集，C∩d=φ；属性值域V=∪a∈ATVa，其中Va为任意属性a∈AT的值域；一个映射函数满足f∶U×C→Va满足对于∀xi∈U，在属性a上的值为f(xi，a)∈Va。对任意条件属性子集B⊆C，定义U上等价关系：IND(B)={(xi，xj)∈U2|f(xi，a)=f(xj，a)，∀a∈B}它诱导论域U的一个知识划分，即U/IND(B)或U/B。设决策属性d所诱导的决策划分U/d={D1，…，Dm}，其中Dh(1≤h≤m)表示决策类。此外，本文用|·|表示集合的基数。

定义1[3]设任意一个条件属性子集B⊆C所诱导的划分U/B={X1，X2，…，Xn}，那么决策表中B相对于d的相对知识粒度为

(1)

定义2[3]属性子集B⊆C，B为C的一个属性约简，若它满足2个条件

(s)RG(B;d)=RG(C;d);

(n) ∀a∈B，RG(B;d)≠RG(B-{a};d)。

定义3[3]∀a∈C，a在决策表中的属性重要度为

Sig(a，C，d)=RG(C-{a};d)-RG(C;d)

(2)

定义1提供相对知识粒度，其能够直接表征知识划分对决策划分的分辨能力。由此，定义2提出基于相对知识粒度的属性约简，相应的属性重要度(定义3)可以用于设计启发式约简算法。

1.2 区间值决策表

区间值决策表IVDT={U，AT=C∪d，V,f}，其中U与属性集C，d类似于上述经典情况；属性值域V=∪a∈ATVa，其中Va为任意属性a∈AT的值域；信息函数f:U×C→Va满足对于∀xi∈U，在属性a上的值为f(xi，a)∈Va是一个区间值。决策属性值仍为单值型。

定义4[15]属性子集B⊆C，阈值δ∈[0，1]，则关于B的相似关系为

(3)

(4)

所有的相似类构成一个对应于元素的|U|维粒化结构:

(5)

命题1[15]设属性子集B⊆C，0≤δ1≤δ2≤1，则有：

定义4提供了对应于元素的|U|维粒化结构，其由相似类进行组建，并通过属性集子集关系及阈值大小关系来实现知识粒化(命题1)。考虑到相对知识粒度能够直接表征知识划分对决策划分的分辨能力，下面基于相似关系诱导的粒化结构，将其引入区间值决策表中，提出一种新的属性约简方法。

2 基于区间相对知识粒度的属性约简

经典相对知识粒度能够刻画知识的粗细程度及反映知识划分对决策划分的解释能力，但不适用于区间值决策表。因此，本节在相似关系[15]的基础上，建立基于区间相对知识粒度的属性约简及其启发式约简算法。并且针对一致区间值决策表，证明区间相对知识粒度约简与代数约简是等价的。

2.1 区间相对知识粒度

定义5设IVDT={U，AT=C∪d，V,f}是一个区间值决策表，B⊆C，阈值δ∈[0，1]。则B相对于d的区间相对知识粒度为

(6)

命题2RG(δ;B;d)=

(7)

引理1

1)f(g1，g2，…，gm-1，gm)=2(g1g2+g1g3+…+gm-1gm)。

2) 若0≤g1≤t1，0≤g2≤t2，…，0≤gm≤tm，则f(g1，g2，…，gm-1，gm)≤f(t1，t2，…，tm-1，tm)。

证明1)是显然的。而对于2)有

f(t1，t2，…，tm-1，tm)-f(g1，g2，…，gm-1，gm)=

2(t1t2+t1t3+…+tm-1tm)-

2(g1g2+g1g3+…+gm-1gm)=

2[(t1t2-g1g2)+(t1t3-g1g3)+…+

(tm-1tm-gm-1gm)]≥0

当且仅当g1=t1，g2=t2，…，gm=tm时等号成立。

命题3设IVDT={U，AT=C∪d，V,f}是一个区间值决策表，A，B⊆C，阈值δ∈[0，1]。则以下结论成立：

1) 若A⊆B，则RG(δ;B;d)≤RG(δ;A;d)；

2) 若0≤δ1≤δ2≤1，则RG(δ2;B;d)≤RG(δ1;B;d)。

证明1)

由命题2，关于B和A的区间相对知识粒度简化为

因此，RG(δ;B;d)≤RG(δ;A;d)。

2) 与1)的证明类似。

命题3表明，区间相对知识粒度具有关于属性与阈值的双重粒化单调性。进而，命题4给出相应的值域与最值条件。接下来，给出属性的必要性和独立性定义以及属性约简构建。

定义6设IVDT={U，AT=C∪d，V,f}是一个区间值决策表，∀a∈C，若RG(δ;C-a;d)=RG(δ;C;d)，则称a为C中d不必要的属性，否则称a为C中d必要的属性。

定义8设IVDT={U，AT=C∪D，V,f}是一个区间值决策表，属性集B⊆C，B为C的一个属性约简，若它满足2个条件

(s)RG(δ;B;d)=RG(δ;C;d);

(n) ∀a∈B，RG(δ;B;d)≠RG(δ;B-{a};d)。

这里，属性约简模拟传统情况，主要依托区间相对知识粒度这一核心度量及其粒化单调性。特别地，区间相对知识粒度的粒化单调性可以引导启发式搜索；由此，下面提出对应的属性重要度。

定义9设IVDT={U，AT=C∪d，V,f}是一个区间值决策表，∀a∈C，a关于C相对于d的区间属性内重要度为

Siginner(δ;a，C，d)=RG(δ;C-{a};d)-RG(δ;C;d)

(8)

B⊆C，∀a∈C-B，a关于B相对于d的区间属性外重要度为

Sigouter(δ;a，B，d)=RG(δ;B;d)-RG(δ;B∪{a};d)

(9)

区间属性内重要度Siginner(δ;a，C，d)描述属性a从属性集C去除之后导致的区间相对知识粒度增加量，区间属性外重要度Sigouter(δ;a，B，d)描述属性a添加到属性集B之后导致的区间相对知识粒度减少量。相关度量变化越大，则说明该属性越重要，因此两者提供了快速约简的属性选择机制。根据核属性概念(定义7)，下面利用区间内属性重要度构造了一个求核方法。

命题5设IVDT={U，AT=C∪d，V,f}是一个区间值决策表，∀a∈C，则a为C中d必要的属性⟺Siginner(δ;a，C，d) > 0，从而

(10)

证明若a为C中d必要的属性，则RG(δ;C-{a};d)≠RG(δ;C;d)，由区间相对知识粒度的粒化单调性知，RG(δ;C-{a};d)>RG(δ;C;d)。

因此，Siginner(δ;a，C，d)>0。反之，若Siginner(δ;a，C，d)>0，则RG(δ;C-{a};d)>RG(δ;C;d)，从而RG(δ;C-{a};d)≠RG(δ;C;d)。由定义6知，a为C中d必要的属性，故式(10)成立。

2.2 基于区间相对知识粒度的启发式属性约简算法

依据以上分析，本小节以区间属性内与外重要度为启发式信息，开发一个以核为约简起点的启发式约简算法，从而快速获取一个属性约简。其中，核充当基础，这是因为(鉴于粒化单调性)核在每个属性约简中，这点与传统情况类似不再详述。具体算法步骤如下：

算法1基于区间相对知识粒度的启发式属性约简算法

输入 区间值决策表IVDT及阈值δ。

输出 IVDT的一个约简R。

步骤1 计算C相对于d的区间相对知识粒度RG(δ;C;d)。

步骤3计算R相对于d的区间相对知识粒度。若RG(δ;R;d)=RG(δ;C;d)，则转向步骤5，否则转向下述步骤4；

步骤4∀a∈(C-R)，计算区间属性外重要度Sigouter(δ;a，R，d)，选择区间属性外重要度最大的条件属性a*并入R中，即进行更新R←R∪{a*}。如果此时有RG(δ;R;d)>RG(δ;C;d)，则重复该步骤的选择与更新过程，直到达到条件RG(δ;R;d)=RG(δ;C;d)，则进入步骤5；

步骤5 输出R。

算法1的时间复杂度分析如下：

步骤1计算RG(δ;C;d)的时间复杂度为：

O(|U|2·|C|·|U/D|)

步骤2要对每个属性计算区间属性内重要度Siginner(δ;a，C，d)，所以时间复杂度为：

O(|U|2·|C|2·|U/D|)

步骤3计算RG(δ;R;d)的时间复杂度为：

O(|U|2·|R|·|U/D|)

步骤4每添加一个属性到约简集R中，需对|U-R|个属性计算区间属性外重要度Sigouter(δ;a，R，d)，其时间复杂度为：

O(|U|2·|R|·|C-R|·|U/D|)

所以，考虑其最坏情况下，步骤4时间复杂度为：

O(|U|2[|C|×1+(|C|-1|)×2+

(|C|-2|)×3+…+

3×(|C|-2)+2×(|C|-1|)+

1×|C|]|U/d|)

而该式的时间复杂度不超过

因此，整个算法1的时间复杂度为：

而文献[20]给出的基于正域的启发式约简算法的时间复杂度为O(|U|2·|C|3·|U/D|)，对比可见，本文所提算法1运行效率优于文献[20]。

2.3 区间相对知识粒度约简与代数约简等价性证明

文献[20]提出基于正域的区间值决策表属性约简(即代数约简)，其满足正域相等与独立性2个条件，而本文定义的基于区间相对知识粒度的属性约简同样满足两个条件：区间相对知识粒度相等与独立性条件。下面证明在一致区间值决策表中，区间相对知识粒度约简与代数约简是等价的。在此之前，先给出一致区间值决策表的定义如下。

命题6设IVDT={U，AT=C∪d，V,f}是一个区间值决策表，则IVDT是一致区间值决策表，当且仅当RG(δ;C;d)=0。

所以，RG(δ;C;d)=0。

命题6表明，区间相对知识粒度能够刻画区间值决策表的一致性。

命题7表明，在一致区间值决策表中，区间相对知识粒度与文献[20]中正域的定义是等价的。因此，基于区间相对知识粒度的属性约简与代数约简的定义是等价的。

3 实例分析

为验证区间相对知识粒度性质的正确性及算法1的有效性，选择一个已知其约简的区间值决策表实例进行说明。文献[20]从代数角度分析了表1所示区间值决策表的属性约简，其属性约简结果为R1={a1，a2}和R2={a2，a3}，此时δ=0.65。

例1区间值决策表IVDT如表1[20]所示，其中U={x1，x2，x3，x4，x5，x6，x7，x8，x9，x10}表示10个对象，C={a1，a2，a3，a4}表示条件属性集，d为决策属性集。

表1 区间值决策表

设阈值δ=0.65，构造属性增链如下：

A1={a1}⊂A2={a1，a2}⊂

B={a1，a2，a3}⊂

C={a1，a2，a3，a4}

取属性增链中的链元B，构造阈值增链如下：

δ1=0.55<δ2=0.65<δ3=0.75<

δ4=0.85<δ5=0.95

下面计算区间相对知识粒度：

1) 对于属性增链有

RG(0.65;A1;d)=0.64>RG(0.65;A2;d)=0.34≥

RG(0.65;B;d)=0.34≥RG(0.65;C;d)=0.34

2) 对于阈值增链有

RG(0.55;B;d)=0.34≥RG(0.65;B;d)=

0.34>RG(0.75;B;d)=0≥

RG(0.85;C;d)=0≥

RG(0.95;B;d)=0

上述2个不等式验证了区间相对知识粒度关于属性与阈值的双重粒化单调性(命题3)。所有度量值均隶属理论双界范围[0，|U|-1](命题4)。

最后根据算法1求解该区间值决策表的一个属性约简。首先设置阈值δ=0.65，执行步骤1，计算C相对于d的区间相对知识粒度：

RG(0.65;C;d)=1.17-0.83=0.34

Siginner(0.65;a1，C，d)=0.34-0.34=0，

Siginner(0.65;a2，C，d)=0.64-0.34=0.30，

Siginner(0.65;a3，C，d)=0.34-0.34=0，

Siginner(0.65;a4，C，d)=0.34-0.34=0，

执行步骤3，计算R关于d的区间相对知识粒度：

RG(0.65;R={a2};d)=0.84>0.34=RG(0.65;C;d)

执行步骤4，∀a∈C-R，计算每个属性关于R相对于d的区间属性外重要度：

Sigouter(0.65;a1，R，d)=0.84-0.34=0.50，

Sigouter(0.65;a3，R，d)=0.84-0.34=0.50，

Sigouter(0.65;a4，R，d)=0.84-0.84=0，

基于最大值选取一个属性并入R中，因属性a1与a3的区间属性外重要度相同，为不失一般性，对a1与a3都进行检验，即分别检验R={a1，a2}，R={a2，a3}，可得：

RG(0.65;R={a1，a2};d)=0.34=RG(0.65;C;d)，

RG(0.65;R={a2，a3};d)=0.34=RG(0.65;C;d)；

执行步骤5，输出R={a1，a2}或R={a2，a3}。

可见，通过算法1求解的约简结果与文献[20]基于正域的约简结果相同，即本文所提算法可以有效获取区间值决策表的属性约简。

4 结论

1) 引入区间相对知识粒度等概念，构建基于区间相对知识粒度的属性约简及其启发式约简算法。

2) 针对一致区间值决策表，证明区间相对知识粒度表示与代数表示是等价的。

3) 通过具体实例验证了区间相对知识粒度性质的正确性及算法1的有效性。

4) 所得结果深化了知识学习与特征优化，对区间值决策表的知识发现具有重要意义。

5) 在现实生活中，属性值有可能产生缺失的情况，因此下一步将对基于区间相对知识粒度的不完备区间值决策表属性约简进行研究。