模糊决策表中基于OWA算子的三支属性约简

杨霁琳 张贤勇 唐 孝

(1．四川师范大学基础教学学院，成都,610068； 2．四川师范大学数学与软件科学学院，成都,610068)

引 言

粗糙集理论是一种处理模糊和不确定性知识的数学工具[1]，其主要思想是以等价关系为基础，利用已有的知识库来表示不确定或不精确的知识，在保持分类能力不变的前提下，通过知识约简导出问题的决策规则。这种模型在完备的信息系统中得到了成功运用[1,2]。

在模糊决策表中，数据往往被认为是一个模糊概念,于是研究者们对经典的粗糙集理论进行扩充[3,4]。许多学者在构造各种不同区分关系的基础上，讨论各种属性约简的理论和方法，并进行了相关应用研究[5,6]。管涛[7]等基于模糊集合的贴近度，构造模糊相似关系，取其截集后得到不可区分关系，利用水平集粗糙成员函数给出分布约简与分配约简；Jensen和Shen提出以依赖度函数作为启发信息的相对约简算法[8,9]，但Bhatt[10]指出该算法在许多实际分析中不收敛；张慧哲[11]等提出一种基于海明距离定义的相似度系数，通过定义模糊相似矩阵和不一致程度矩阵，给出属性约简的定义及算法；曾雪兰[12]等提出一种全序优势关系，该全序优势关系是Grecos[13]提出的优势关系的扩充，并进而给出关于对象的相对上下近似约简计算方法；胡清华等[14,15]提出邻域粗糙集模型，其中数值型属性通过欧式距离表示为模糊相似关系，以决策属性对条件属性的依赖度为标准给出属性约简的概念与约简方法；张家录[16]等提出基于模糊包含的模糊粗糙集模型，通过计算模糊信任测度、模糊似然测度来进行随机模糊信息系统的属性约简；赵涛[17]引入模糊随机变量，提出期望相关关系，并基于该关系讨论属性约简方法；黄兵等[18]将区分函数引入模糊信息系统, 以依赖度为约简标准，给出相应的知识约简方法。冯楠坪等[19]通过模糊相似关系建立条件相似度与决策相似度之间的相对比较矩阵，给出一种基于相似度比较的模糊属性约简方法。在模糊决策表中，利用区分函数完成属性约简，算法复杂度较高，并且在实际应用中，往往不需要找到所有的属性约简。因此，以上文献针对模糊决策表，都是在基于特定的不可区分关系之上，构造相应的属性约简标准，建立其属性约简方法。本文将借鉴此理论分析方法，在模糊决策表中，基于有序加权平均(Ordered weighted averaging, OWA)算子建立的相容关系，给出属性重要度，构造属性约简标准，建立一种启发式属性约简算法。

三支决策是一种处理不确定性信息决策的智能理论，特别适用于粗糙集及其属性约简[20]。在三支决策区域中，决策类的正域、边界域和负域分别对应接受、不承诺和拒绝决策。在模糊决策表中，以上文献大都基于正域对属性约简进行讨论。随着三支决策的发展，三支决策区域也用来构建三支属性约简[21]。因此，本文将在正域属性约简的基础上，扩展到三支区域，分别讨论正域、负域和边界域的属性约简。前期研究工作中，在模糊信息系统中OWA算子能够诱导相容关系[22,23]。在此基础上，本文进一步讨论属性约简方法。

1 基于OWA算子的粗糙集模型

1.1 基于OWA算子的相容关系

定义1[4]设模糊信息系统Ω=(U,A,V,f)，U={x1,x2,…,xn}是非空有限对象集，A={a1,a2,…,am}是属性集，V={Va|a∈A}是属性值集，此时Va可以是一个隶属函数值，则对象x在条件属性a下属性值可以表示为μa(x)∈[0,1]，f表示一个映射，f:U×A→Va，即(x,a)→μa(x)。

在模糊信息系统中，μa(x)∈[0,1]体现了数据的不确定性，但经典粗糙集的等价关系很难再成立。因此，经典粗糙集模型被许多学者做了进一步推广。在前期研究中，利用OWA算子聚合每个属性上在对象间区分时的差异，得到对象的相似度，从而利用对象相似度建立了λ截集的相容关系[22]。

在OWA算子中，根据聚合要求，加权向量一般可通过模糊量词Q确定[24]，即模糊量词Q表示为

(1)

式中:α,β∈[0,1]，(α,β)有多种取值方式，如参数(α,β)最常用的是3种取值：(0.3, 0.8)，(0, 0.5)，(0.5, 1) ,它们分别表示模糊量词“大多数”，“至少一半”和“尽可能多”[22]。相应地，有序加权向量w=(w1,w2,…,wm)可如下确定

(2)

定义3[22]设Ω=(U,A,V,f)是一个模糊信息系统，∀x,y∈U在属性集A上的相似度为

(3)

式中:FA是OWA算子，TA=(μa1(x,y),μa2(x,y),…,μam(x,y)),μaj(x,y)=|μaj(x)-μaj(y)|(j=1,2,…,m)，是对象x和y在属性aj上的差异。HA=(w1,w2,…,wm)根据式(1)和式(2)获得，它是模糊信息系统属性集A中各属性对应的权重。TA中各对象μaj(x,y)按值从大到小排序后，得到EA=(μaσ(1)(x,y),μaσ(2)(x,y),…,μaσ(m)(x,y))且满足∀l∈{1,2,…,m}，有μaσ(l)(x,y)≥μaσ(l+1)(x,y)。

定义4[22]设Ω=(U,A,V,f)是一个模糊信息系统，∀x,y∈U，在属性集B⊆A下，不可区分关系定义为Rλ:U×U→[0,1]，xRλy={(x,y)∈U×U|sB(x,y)≥λ}。其中，sB(x,y)是对象x和y在属性集B上的相似度，λ∈[0,1]是阈值，可根据具体问题设置。显然，Rλ满足自反性和对称性，但不一定满足传递性，因此Rλ是相容关系。

定义5[22]设Ω=(U,A,V,f)是一个模糊信息系统，∀x∈U，在属性集A下，其相容类定义为

[x]Rλ={y∈U|sA(x,y)≥λ}

(4)

[x]Rλ是一个自反、对称的信息粒。基于OWA算子，利用对象相似度建立的相容关系主要受两个因素的影响[22]：一是判定两个对象相似度的阈值λ的选值；二是OWA算子中模糊量词参数(α,β)的选取。这两个因素直接影响模糊信息系统中论域不同的划分，即不同粒度的表示。模糊量词参数(α,β)的选取对粗糙集模型的影响已在前期工作中详细分析[23]。在实际问题中，根据对粒度要求的粗细，可灵活选取λ和(α,β)的值，使得建立的信息粒更合理更实用。

1.2 基于OWA算子的粗糙集模型

在模糊决策表中，基于OWA算子建立的λ截集相容关系建立粗糙集模型。

定义6设Ω=(U,A∪D,V,f)是一个模糊决策表，U={x1,x2,…,xn}是对象集合，A={a1,a2,…,am}是条件属性集合，VA={Va|a∈A}是属性值集，μa(x)∈[0,1]，fA:U×A→Va，即有(x,a)→μa(x)。D为决策属性集，有U/D={D1,D2,…,Dr}。

在同一模糊决策表中，约定当各条件属性的权重由OWA算子确定后将不再更改。因此若B⊆A，则相应的对象相似度定义如下。

定义7设Ω=(U,A∪D,V,f)是一个模糊决策表，若B⊆A,则∀x,y∈U在属性集B上的相似度为

(5)

其中TB=(μa1(x,y),μa2(x,y),…,μam(x,y)),若B⊂A，∃a∈A，且a∉B，则有μa(x,y)∈TB，同时μa(x,y)=0。HA=(w1,w2,…,wm)是属性集A中各属性对应的权重。

性质1在模糊决策表Ω=(U,A∪D,V,f)中，若B⊆A,∀x,y∈U，有sB(x,y)≥sA(x,y)。

证明当B=A，则sB(x,y)=sA(x,y)；当B⊂A，则∃a∈A，a∉B，且μa(x,y)=0，则EB=(μaσ(1)(x,y),μaσ(2)(x,y),…,μa(x,y))=(μaσ(1)(x,y),μaσ(2)(x,y),…,0)而EA=(μaσ(1)(x,y),μaσ(2)(x,y),…,μaσ(m)(x,y))，μaσ(m)(x,y)≥0,因此HA(EB)T≤HA(EA)T，则1-HA(EB)T≥1-HA(EA)T，根据定义3和定义4，即有sB(x,y)≥sA(x,y)。因此，若B⊆A，有sB(x,y)≥sA(x,y)。

证明根据定义5和性质1，易证。

性质2在模糊决策表Ω=(U,A∪D,V,f)中，若B⊆A, 则

(1) POSB(Dt)⊆POSA(Dt);(2) BNDB(Dt)⊇BNDA(Dt);(3) NEGB(Dt)⊆NEGA(Dt)。

定义8给出了一个决策类Dt的三支区域定义，进而所有决策类集合D相对于条件属性集B的三支区域系统可以定义如下。

性质3在模糊决策表Ω=(U,A∪D,V,f)中，若B⊆A, 则

(1) POSB(D)⊆POSA(D); (2) BNDB(D)⊇BNDA(D)。

证明根据性质2和定义9易证。

2 基于OWA算子的三支属性约简

根据Pawlak粗糙集理论的经典思想，属性约简是信息系统保持分类能力不变的条件下，去掉冗余属性。将这种思想引入到模糊决策表中，基于三支区域(即正域、边界域和负域)给出三支属性约简如下。

定义10Ω=(U,A,V,f)是一个模糊决策表，∀x∈U，B⊆A，有POSB(D)=POSA(D)，且∀b∈B，有POSB-{b}(D)≠POSB(D)，则称B是一个正域属性约简。

定义11Ω=(U,A,V,f)是一个模糊决策表，∀x∈U，B⊆A，有BNDB(D)=BNDA(D)，且∀b∈B，有BNDB-{b}(D)≠BNDB(D)，则称B是一个边界域属性约简。

定义12Ω=(U,A,V,f)是一个模糊决策表，∀x∈U，B⊆A，有POSB(D)=POSA(D)，且∀b∈B，有NEGB-{b}(D)≠NEGB(D)，则称B是一个负域属性约简。

2.1 属性贡献度与属性约简可能性

在模糊决策表Ω=(U,A∪D,V,f)中，基于OWA算子的相容关系Rλ是根据对象间的相似度sA(x,y)确定的，而sA(x,y)是通过聚合对象x和y在每个属性aj上的差异μaj(x,y)而得到的。在聚合时，每个属性μaj(x,y)所对应的权重有可能不一样。直观地，属性对应的权重越大，对x和y的区分贡献越大，即该属性相对越重要；相反地，属性对应的权重越小，其对x和y的区分贡献越小，即该属性的重要性相对越小。因此，在聚合对象x和y在每个属性上的差异时，其每个属性aj对应权重的大小决定了aj在对x和y进行区分时贡献度的大小。

定义13设Ω=(U,A∪D,V,f)是一个模糊决策表，∀x,y∈U，其每个属性的相对贡献度为

(6)

定义14设Ω=(U,A∪D,V,f)是一个模糊决策表，对象集U={x1,x2,…,xn}，属性集A={a1,a2,…,am}。∀x,y∈U，属性集中相对于对象x和y的最小贡献度属性为

(7)

式中:j,l∈{1,2,…,m}；wmin=min(w1,w2,…,wm)是权重向量中的最小值。

性质4设Ω=(U,A∪D,V,f)是一个模糊决策表，∀x,y∈U,有

(1)amin(x,x)=Ø;(2)amin(x,y)=amin(y,x);(3)|amin(x,y)|≥1。

根据定义14可以找到任意对象x和y进行区分时的最小贡献度属性。直观地，∀x,y∈U，若属性a在所有amin(x,y)中出现的频率越高，即a对较大多数对象间的区分贡献度越小，其被约掉的可能性越大；若属性a在所有amin(x,y)出现的频率越低，即a对较大多数对象间的区分贡献度越大，其被约掉的可能性也越小。因此，属性集中各属性被约简的可能性可形式化如下。

定义15设Ω=(U,A∪D,V,f)是一个模糊决策表，∀a∈A，则属性被约简的可能性为

(8)

式中:∀x,y∈U，M(a)={amin(x,y)|a∈amin(x,y)}，|M(a)|为集合的势，n为U中对象的个数。0≤P(a)<1，由于amin(x,x)=Ø，且amin(x,y)=amin(y,x)，因此只统计amin(x,y)，有P(a)<1。

显然，P(a)的值越小，该属性被约简的可能性越小；反之，P(a)的值越大，该属性被约简的可能性越大。例如：若P(a)=0，即∀x,y∈U，有a∉amin(x,y)，表示属性a对每个对象间区分的贡献度都较大，显然a被约掉的可能性很小；若当P(a)越接近1时，∀x,y∈U，若有a∈amin(x,y)，表示属性a对每个对象间区分的贡献度都最小，显然a是冗余的，被约掉的可能性最大。

2.2 基于OWA算子的属性约简算法

直观地，定义15的属性约简可能性给出了一个属性约简顺序，即在约简中，首先考虑约简可能性大的属性是否可以被约掉。因此，本小节利用属性重要度进行启发，构建基于OWA算子的三支属性约简算法。下面主要以正域属性约简算法(即如下算法1)的构建为例。

算法1基于OWA算子的启发式正域属性约简算法

输入：模糊决策表Ω=(U,A∪D,V,f)；

输出：模糊决策表的一个正域属性约简。

步骤1在OWA算子中，根据式(1)和(2)

(1) 设定α,β的值；

(2) 计算权重向量wi(i=1,2,…,m)。

步骤2∀x∈U，相容关系的建立，根据式(3，4)和定义8,9

(1) 计算相似度sA(x,y)；

步骤3∀x,y∈U，∀a∈A，根据式(6—8)

(2) 计算每个属性的约简可能性P(a)；

(3) 根据P(a)的值，得到启发式属性约简的顺序A′=(a1,a2,…,am)，其中

P(a1)≥P(a2)≥…≥P(am)。

步骤4属性约简判断

(1) 初始化k=1，C=Ø；

(2)Ak=A-{ak}，∀x,y∈U，令μak(x,y)=0，计算sAk(x,y)和POSAk(D)；

(3) 若POSAk(D)=POSA(D)，则C=Ak，跳转到步骤4(5)，否则继续；

(4) 若k

(5) 若k

基于以上步骤可得到模糊决策表Ω=(U,A∪D,V,f)的一个正域属性约简。类似地，根据算法1，将步骤2计算正域POSA(D)，分别改为计算边界域BNDA(D)或负域NEGA(D)，在步骤4(3)中，将判定条件对应改为BNDAk(D)=BNDA(D)或NEGAk(D)=NEGA(D)，则将得到模糊决策表的一个边界域约简或负域约简。

该启发式属性约简算法在三支区域属性约简的过程中，根据属性间顺序(属性被约简的可能性)进行约简，可以减少约简的搜索空间，同时尽可能避免约简时的盲目性。

3 实例分析

下面利用1个模糊决策表实例，分析本文启发式属性约简方法进行三支区域属性约简的合理性及有效性。

例1Ω=(U，A∪D，V，f)是一个模糊决策表(如表1)。其中对象集合U={x1,x2,…,x8}，条件属性集合A={a,a2,a3}，决策属性集D={d},Vd={0,1,2}。

表1 Ω=(U，A∪D，V，f)模糊决策表

根据表1，U/D={D1，D2，D3}，D1={x1，x5}，D2={x2，x7，x8}，D3={x3，x4，x6}。

表2 相似度sA(x,y)数据表

表3 对象间最小贡献度属性amin(x,y)数据表

根据步骤4，选取a2作为最有可能被约掉的属性，初始化k=1，于是A1=A-{a2}={a1,a3}，仍以对象x1和x2为例，有μa1(x1,x2)=0.9，μa2(x1,x2)=0，μa3(x1,x2)=0.6，则x1和x2在属性集A1的相似度为

(9)

则对象相似度sA1(x1,x2)=sA(x1,x2)。计算所有的对象在属性集A1下的相似度，结果如表4所示。

表4 相似度sA1(x,y)数据表

表5 相似度sA2(x,y)数据表

类似地，可以计算在属性集A下，边界域和负域分别为BNDA(D)={x1,x4,x5},NEGA(D)=Ø；在属性集A1下分别为BNDA1(D)={x1,x4,x5},NEGA1(D)=Ø；在属性集A2下分别为BNDA2(D)={x1,x3,x4,x5,x7},NEGA2(D)=Ø。显然，有BNDA2≠BNDA1=BNDA(D),NEGA2(D)=NEGA1(D)=NEGA(D)。因此，A1={a1,a3}也是模糊决策表的一个边界域属性约简。因为NEGA2(D)=NEGA(D)=Ø，而A2={a1}为单元集，故A2为模糊决策表的一个负域约简。

根据以上实例计算和分析，基于OWA算子的模糊粗糙集模型中，利用OWA算子的权重定义属性的贡献度，从而给出属性约简的顺序，建立一种启发式约简方法，对于模糊粗糙集模型中基于正域、负域和边界域的三支属性约简都是合理有效的。属性贡献度的定义为属性重要性度量给出了一种新的思考方法，同时该启发式属性约简方法能减少搜索空间，有效地寻找到分别基于三支的属性约简。

在模糊决策表中，利用本文方法进行属性约简时，可灵活选取(α,β)和λ的值。一般来讲，选取(α,β)的值，以保证聚合算子中权重向量w=(w1,w2,…,wn),有w1>w2>…>wn，即在聚合对象间区分差异时，属性值差异较大的属性对应较大的权重，从而该属性获得较大的属性贡献度；属性值差异较小的属性对应较小的权重，从而该属性获得较小的属性贡献度。直观地，这在属性约简过程中是合理的，实例也证明了其合理性和可行性。

4 结束语

在模糊决策表中，基于OWA算子的λ截集相容关系，本文定义了三支区域以及基于三支区域的属性约简标准，讨论了基于三支区域的属性约简。通过利用OWA算子中的权重给出每个属性的贡献度，进一步定义了属性约简的可能性，即给出了一个属性约简的顺序，从而给出了模糊决策表中一种启发式三支区域属性约简方法。实例说明该约简方法可以在模糊决策表中找到基于正域、边界域和负域的一个属性约简。在启发式约简算法过程中，利用OWA权重定义贡献度为属性重要性度量给出了一种新的思考方法，同时，该启发式约简算法在能减少属性约简的搜索空间，更有利于模糊决策表在实际特征选取中的应用。在今后的研究工作中，可以考虑该分别和同时基于三支区域属性约简，它们之间的联系和相关性质，以及利用实际应用数据来优化OWA算子参数的选取，实现不同程度的属性约简。