区间值决策信息系统中基于正域的属性约简

陈华峰，龙建武，瞿先平,

(1.重庆电讯职业学院 基础部， 重庆 402247；2.重庆理工大学 计算机科学与工程学院， 重庆 400054)

粗糙集理论作为一种有效的数据挖掘工具，自20世纪80年代由波兰数学家Pawlak[1]提出以来，其对知识的自动获取、机器学习以及模式识别等多个科学研究领域的发展都起到了积极的推动作用。该理论主要是基于一个等价关系对论域进行划分，然后通过一对上、下近似算子来描述任意对象集的近似范围，以此从数据库挖掘出以规则形式进行表达的知识。随着粗糙集理论研究及实际应用的不断深入，经典的Pawlak 粗糙集模型存在着一定的不足之处，为此大量的学者对广义粗糙集模型进行了深入的研究[2-4]。常见的方法是将经典粗糙集模型中的等价关系推广为一般二元关系，也即是将等价关系所需满足的3条(自反性、对称性、传递性)删除1条或多条，从而构造满足特定要求的二元关系，以此建立基本信息粒结构[5-6]。也有通过邻域来建立基本信息粒的，即按照某一度量方式得到小于给定的阈值的对象构成的集合为一个基本信息粒[7-8]。还有学者结合实际问题的需要，提出了多粒度粗糙集方法[9-10]，这些方法常用于不完备信息系统或广义值信息系统的知识发现研究中。

信息系统作为数据描述的基本形式，是基于粗糙集理论研究的基础[11]。随着数据的多元化和复杂化，用简单的实数值来描述对象和属性之间的关系明显不够，为此学者们分别对模糊值信息系统[12]、模糊决策序信息系统[13]、直觉模糊信息系统[14-15]、基于覆盖的决策信息系统[16]等进行了系统的研究。这些广义的信息系统的研究以及应用极大地推动了粗糙集理论的发展，让粗糙集理论在解决实际问题时展现出了强大的应用能力。由于在数据采集过程中不可避免地会有许多不必要的或者冗余知识混入其中，直接对大规模复杂数据进行研究，不仅会对资源造成大量的浪费，甚至有可能是一项不可能完成的任务，因此如何对数据进行必要的筛选，在保持数据所蕴含的知识不变或极小损失的同时，尽可能地降低数据规模，是一个值得研究的课题[17]。

属性约简是粗糙集理论研究的核心问题之一，可以简单理解为在保持知识库分类能力不变的情况下，删除其中的一些不相关或不要的属性，从而达到降低数据规模的目的[18]。由于寻找属性约简是NP-hard问题，解决这类问题的一般是采用启发式搜索，通过在算法中加入启发式信息，缩小问题的搜索空间，进而获得最优解或近似解，因此启发式约简方法被广泛应用于各类基于粗糙集的属性约简问题中[19-21]。对于决策信息系统来讲，决策规则是研究者最关注的话题，其中又尤以确定性规则最为重要，那么如何以尽可能少的条件属性获取相当水平的确定性规则，即基于正域的属性约简值得研究。为此，本文将对区间值决策信息系统中基于正域的属性约简方法进行讨论，并设计相应的启发式属性约简算法，然后结合案例分析对模型建立以及利用算法搜寻约简的过程进行演示。

1 预备知识

本节介绍一些研究所需要基本知识，包括信息系统与粗糙集的基本定义，以及属性约简的相关概念等。

设四元组S=(U,AT,V,f)为一个信息系统，其中U={x1,x2,…,xn}为论域，是非空有限对象集，AT={a1,a2,…,am}为非空有限属性集，V为有限值域，f:U×AT→V一个信息函数，它给定U中的任意对象x的属性值。对任意的A⊆AT可以得到一个不可分辨关系，即

IND(A)={(x,y)∈U×U∶∀a∈A,f(x,a)=f(y,a)}

则U中关于属性A所有与x具有不可分辨关系IND(A)的对象的集合为

[x]A={y∈U,(x,y)∈IND(A)}

即x关于属性集A的等价类。显然IND(A)为一个等价关系，通常简写为RA或R。基于这一基本划分，建立经典的粗糙集模型如下：

定义1[1]设S=(U,AT,V,f)为一个信息系统，对任意的X⊆U和A⊆AT，则可得X关于属性集A的上、下近似集分别为：

基于这一对近似算子可以得到其他的粗糙集区域，其中正域为

在决策分析中正域有着极为突出的地位，是一个广受关注的研究课题。一个信息系统S中如果加入决策属性，则称之为一个决策信息系统即S=(U,AT∪D,V,f)，其中AT∩D=∅。更一般地，如果对象关于条件属性的取值不是一个单一的实数值，而是一个区间数(即f(x,a)=I=[l,r]，其中l≤r)，则称之为区间值决策信息系统，本文将在该信息系统中展开讨论。对于一个信息系统来讲，不同属性的重要性是不一样的，其中不免有一些不重要甚至冗余的属性，常通过基于属性构造的二元关系来衡量属性是否必要。

定义2[11]设S=(U,AT,V,f)为一个信息系统，对任意的A⊆AT且a∈A，如果

IND(A)=IND(A-{a})

则称a在A中是不必要的属性，否则称a为A中是必要的属性，不可以约简。如果A中的每一个属性都是必要的，则称A是独立的，否则称为依赖的。基于此可以得到，对任意的属性集B⊆A，若B是独立的，且IND(B)=IND(A)，则称B为A的一个约简，记作Red(A)。对于一个属性集A来说，约简一般不是唯一的但一定存在，所有约简的核的交集称为核，记作Core(A)。

在决策信息系统中，需要研究条件属性的分类和决策属性分类之间的关系，此时需要对相对约简和相对核进行讨论。

定义3[11]设S=(U,AT∪D,V,f)为一决策信息系统，对任意的A⊆AT，则D关于条件属性集A的正域为：

它表示论域U中所有根据RA分类的信息，可以准确划分到决策属性D的等价类中去的对象的集合。类似地，可以定义任意的a∈A是否必要，如果

posA(D)=posA-{a}(D)

则称a为A中D不必要的，否则称a为A中D必要的。如果A中的每一个属性都是D必要的，则称A为D独立的。对任意的B⊆A，如果B是D独立的，且posA(D)=posB(D)则称B为A的D约简。而A的所有D约简的交集称为A的D核，记为CoreA(D)，它所描述的是A中所有D必要的原始关系构成的集合。

2 区间值决策信息系统中基于正域的属性约简方法

本节将在区间值决策信息系统讨论基于正域的属性约简方法。由于在区间值决策信息系统基于等价关系的划分已不再有效，因此在对象之间建立相似性度量，并设定一个阈值以此得到一个邻域，然后展开本文的讨论。

对于任意的两个区间数，其相似性度量方式有多种，文献[22]利用包含度定义了任意两个区间数之间的关系。设I1=[l1,r1]和I2=[l2,r2]为两个区间数，则I1关于I2的区间包含度为

其中：ρ(I1)=r1-l1，I1∩I2=[max{l1,l2}, min{r1,r2}]。

特别地，如果max{l1,l2}≥min{r1,r2}，则ρ(I1∩I2)=0。此外，Dai从另外一个角度定义了I1相对I2相似度，也正是本文所采用的定义方式。

定义4[22]设I1=[l1,r1]和I2=[l2,r2]为两个区间数，则I1大于I2的概率定义为

基于这一度量，Dai给出了I1和I2之间的相似性度量，即

s(I1,I2)=1-|P12-P21|

该度量是自反的，即s11=1,对称的s12=s21。基于这一度量，如果给定一个阈值δ∈(0,1]，则可以得到相应的δ领域。

定义5设S=(U,AT∪D,V,f)为一个区间值决策信息系统，对任意的A⊆AT，给定阈值δ∈(0,1]，则任意的x∈U关于条件属性集A的δ邻域为：

δA(x)={y∈U:sa(x,y)≤δ,∀a∈A}

其中sa(x,y)表示对象x和y关于条件属性a的值之间的相似度，利用定义4所得。利用类似于经典的粗糙集模型的方法在区间值决策信息系统中建立粗糙集模型。

定义6设S=(U,AT∪D,V,f)为一个区间值决策信息系统，对任意的A⊆AT，给定阈值δ∈(0,1]，则Dj∈U/D基于邻域的下、上近似集分别为：

在实际应用中要找到一个信息系统的所有约简并不是一件简单的事情，有时只需找到一个约简即可，因此可设计启发式算法来寻找满足条件的约简。而设计启发式算法需要设计一个合适的起点以及找到一个恰当的启发式信息，通常采用分类质量来度量某一个条件属性对正域的影响。

定义7设S=(U,AT∪D,V,f)为一个区间值决策信息系统，对任意的A⊆AT，δ∈(0,1]，则D关于A的分类质量为：

定义8设S=(U,AT∪D,V,f)为一个区间值决策信息系统，对任意的δ∈(0,1]，A⊆AT且a∈A，则属性a在属性A中关于决策属性D的相对重要度为：

对任意的属性a∈A有Sig(a,A,D)∈[0,1]。当Sig(a,A,D)=0时，意味着a在D决策中是不必要的，因此可以得到决策值信息系统中基于正域的属性约减。即满足如下2个条件的属性集：

在设计搜寻一个约简的启发式算法时，从空集出发，以属性的相对重要度为启发式信息设计启发式算法，如算法1所示。

算法1 区间值决策信息系统中基于正域的的启发式属性约简算法

输入：一个区间值决策信息系统S=(U,AT,V,f)，以及阈值δ；

输出：该信息系统的一个约简Red(AT)

1. let Red(AT)=∅; //初始化约简为空

2. for eacha∈ATdo

3. compute:Sig(a,AT,D);

4. end

7. Red(AT)=Red(AT)∪{b};

8. end

9. for eacha∈Red(AT) do

11. Red(AT)=Red(AT)-{a};

12. end

13. end

16. return：Red(AT).

3 实例分析

基于以上讨论，本节用1个实例来展现在区间值信息系统的粗糙集建模，以及各个度量的具体计算方式，并按照算法1求解给定区间值决策信息系统的1个约简。本案例分析中所采用的数据改编自文献[23]。

例1给定一个区间值决策信息系统S，其中U={x1,x2,…,x10}表示10个对象，AT={a1,a2,a3,a4}表示条件属性，D为决策属性，有关该决策信息系统的具体数据如表1所示。

表1 某区间值决策信息系统

由定义4的相似度定义可以计算任意两个对象关于任意属性的相似度。为不失一般性，选取x1和x2关于属性a1为例，即I1=[0.5,0.8]，I2=[0.4,0.7]，则可得

则

s(I1,I2)=1-|0.67-0.33|=0.66

即x1和x2关于属性a1的相似度为0.66。类似地，可以得到任意的两个对象关于所有属性的相似度。如果在实际应用中给定一个阈值δ∈(0,1]，则可以由定义5得到一个邻域。在接下来的研究中不妨取δ=0.65，则可以得δAT(x)对任意的x∈U，结果如下：

δAT(x1)={x1,x2,x4,x5,x6,x8,x10}

δAT(x2)={x1,x2,x5,x6}

δAT(x3)={x3,x7,x9}

δAT(x4)={x1,x4,x5,x8}

δAT(x5)={x1,x2,x4,x5,x6,x8}

δAT(x6)={x1,x2,x5,x6}

δAT(x7)={x3,x7,x9}

δAT(x8)={x1,x4,x5,x8}

δAT(x9)={x3,x7,x9}

δAT(x10)={x1,x10}

由表1可知论域U关于决策属性分为两类，即U/D={D1,D2}，q且

D1={x1,x4,x5,x6,x8,x10}

D2={x2,x3,x7,x9}

通过定义6可以得到决策属性D关于条件属性集AT的正域为

则

进一步可以得到D关于AT的分类质量为

基于以上的计算，进一步计算每一个属性的相对重要性为

Sig(a1,AT,D)=0

Sig(a2,AT,D)=0.33

Sig(a3,AT,D)=0,

Sig(a4,AT,D)=0

接下来利用分类质量来对属性集进行检测。显然空集不是一个约简，因此选取属性度重要度最大的属性a2，即

Red(AT)={a2}

进一步检验，有

由计算结果知{a1,a2}和{a2,a3}都有可能是约简，接下来进行算法9～13行的检验，有

显然都是不可进一步去掉的属性，也就是说{a1,a2}和{a2,a3}都是在阈值δ=0.65时保持关于决策属性正域的约简，即

由于启发式算法的目的是找到一个满足条件的约简即可，因此该区间值决策信息系统可能还存在其他的约简，一般可以基于辨识矩阵的方法求解。但当只需要找到一个约简的时候，启发式约简算法更为简洁有效。因此，在实际应用中如果只需搜寻一个满足条件的约简时，可以将本算法作为参考。

4 结束语

本文在区间值决策信息系统基于邻域建立了粗糙集模型，为了删除在数据采集过程中存在的一些不必要的或冗余的条件属性，本文基于决策属性关于条件属性的正域，设计了一种启发式属性约简算法。通过一个案例的求解，对区间值决策信息系统的粗糙集建模过程，以及基于本文所设计的启发式属性约简算法过程进行了演示。实验结果表明：给定一个区间值信息系统，本文所给出的方法可以找到一个基于正域得到的属性约简。在接下来的研究中，将进一步讨论区间值决策信息系统中的其他约简方法，并在带模糊决策的区间值信息系统的研究属性约简方法。