基于辨识矩阵的多伴随模糊粗糙集属性约简

2019-05-15梁美社

石家庄职业技术学院学报 2019年2期

梁美社

(石家庄职业技术学院科技发展与校企合作部，河北石家庄 050081)

粗糙集理论是20世纪80年代波兰学者Pawlak教授提出的，主要用于处理关系数据库中不完备、不精确的信息[1-2].当前，粗糙集理论被广泛应用于工业控制[3-4]、生物医学[5-6]、市场预测[7]、图像处理[8-9]等领域.

早期粗糙集理论的经典著作主要利用一些等价关系，来处理数据集中对象关于属性取值为特殊离散值的情况.等价关系的交集仍是等价关系，Pawlak将其称为不可辨识关系[1-2].因为等价关系的要求过于严苛，因此在实际应用中往往受到很大的限制.在过去的20年中，针对不同的问题，学者们对等价关系进行了多种形式的推广，如优势关系[10-11]、容差关系[12-13]、模糊关系[14-16]和相容关系等.

1965年，Zadeh教授提出了模糊集的概念[17].粗糙集与模糊集都是处理不确定性信息的重要工具，也是研究信息系统中知识不完全、不确定问题的重要方法.将粗糙集中被近似的经典集合扩展到模糊集合，将等价关系推广到模糊关系，就得到了模糊粗糙集的概念[18].后来，一些学者进一步把经典逻辑算子推广为模糊逻辑算子[19-24].而多伴随算子的运用，使其理论发展到了一个全新的阶段.

现有的多伴随模糊粗糙集模型[25]中，通过定义模糊测度，得到的属性约简均为水平α下的近似约简.本文拟在多伴随模糊粗糙集模型的基础上，通过构造属性约简的可辨识矩阵，给出属性约简的计算方法和相关性质，进而得到模糊决策信息系统的精确属性约简.

1 预备知识

1.1 粗糙集理论

经典粗糙集理论[1]中，信息系统通常表示为IS=(U,Α)，其中对象集合U={x1,…,xn}，属性集合Α={a1,…,am}，是非空有限集.对于∀a∈Α，定义映射fa:U→Va，其中Va是属性a在U上的值域. 对于B⊆A，记为RB={(x,y)∈U×U:∀a∈B,fa(x)=fa(y)}，则RB是由属性集合B确定的U上的等价关系. 由RB可以得到U上的一个划分.U/RB={[x]B:x∈U}，其中[x]B={y∈U:(x,y)∈RB}.

对于X⊆U，它关于RB的下、上近似分别为:

若rA=1，称(U,Α∪{d})为一致的决策信息系统. 若POSB=POSA，且∀B′⊂B，有POSB′≠POSA，称B为A的决策约简.

经典粗糙集中，另一种求属性约简的方法是基于可辨识矩阵和辨识函数的.

决策信息系统(U,Α∪{d})的辨识矩阵O是一个(n×n)阶矩阵，具体定义为：

其辨识函数定义为f(U,RA)=∧{∨Oij}(i≠j).由辨识函数计算得到的最小析取范式，即为该决策信息系统(U,Α∪{d})的所有约简.

1.2 多伴随模糊粗糙集理论

多伴随模糊粗糙集是对粗糙集理论的一种推广.通过引入一组伴随对来计算模糊集的上下近似.不同伴随对的使用表达了研究者对不同对象的偏好.这种推广极大地增强了粗糙集理论的应用.

定义1[21]设(P1,≤1)，(P2,≤2)，(P3,≤3)为三个偏序集，定义映射:P1×P2→P3， ↙:P3×P2→P1，↖:P3×P1→P2，若对于任意x∈P1，y∈P2，z∈P3，满足:

(1)x≤1z↙y当且仅当x&y≤3z，当且仅当y≤2z↖x;

(2)&对两个参数是单调增的;

(3)↙,↖对第一个参数单调增，对第二个参数单调减;

(4)称(&,↙,↖)是关于P1,P2,P3的伴随三元组.

常用的有Godel，product，ukasiewiczt-模及其蕴含算子构成的伴随三元组，它们分别定义[21]为：

x&Py=x·y,z↖Px=min{1,z/x};

x&Ly=max{0,x+y-1},

z↖Lx=min{1,1-x+z}.

假设(U,Α∪{d})为模糊决策信息表，(P,≤)为一偏序集，TP为P中最大元素，对于∀a∈A，定义映射Ra:U×U→P为P-模糊容差关系，使其满足自反性，即对于∀x∈U，有Ra(x,x)=TP;使其满足对称性，即∀x,y∈U，有Ra(x,y)=Ra(y,x).

在多伴随面向属性框架下，考虑形式背景(U,U,RB,τ)，对于∀x,y∈U，定义似然算子和必然算子:

g↑π(x)=sup{RB(x,y)&τ(x,y)g(y)|y∈U}，

f↓N(y)=inf{f(x)↖τ(x,y)RB(x,y)|x∈U}.

g↑π是g的上近似，f↓N是f的下近似.{(&τ(x,y),↙τ(x,y),↖τ(x,y)为伴随对集合，其中τ:U×U→I表示将任意一对对象映射为某一特定的伴随对，I为一指标集.

定义3[24]对于给定模糊子集h∈LX，(h↓N,h↑π)称为多伴随模糊粗糙集.

在模糊决策信息表(U,A∪D,f,V)中，D={d}为决策属性，利用必然算子定义多伴随模糊粗糙集正域，对于∀y∈X，

文献[25]中利用模糊蕴含和模糊基数来定义正域依赖度，通过模糊蕴含算子来定义L-测度.

由定义4可以得到，模糊决策信息表(U,A∪D,f,V)中属性子集B的正域依赖度为：

定义6[24]设γ:Ρ(Α)→L是决策系统(U,Α∪{d})的一个L-测度，B⊆Α且α∈L，若γ(B)≥α，α≠⊥L则称B是一个α水平下L-决策超约简.若对于∀B1⊂B，有γ(B1)<α，则称B是一个α水平的下L-决策约简.

显然，这个约简与参数α的取值密切相关.给定α后，其得到的约简均为近似约简.

2 基于辨识矩阵的模糊正域约简

在定义2中，模糊不可辨识关系是通过一个单调聚合算子得到的.而在经典的粗糙集理论中，对于属性子集B⊆A，其等价关系为RB=∩a∈BRa.本文将借鉴这个思路，给出新的模糊不可辨识关系的定义.

为了方便讨论问题，本文的模糊信息决策表为(U,A∪D,V,f)，其中，|U|=n，|A|=m，D={d}，且决策属性为经典的明确关系.

证明由定义7可直接得到.

如果保证模糊正域不变，则可得到属性约简定义8.

定义9给出了利用辨识矩阵求解模糊决策约简的方法.

定理3设(U,A∪D,V,f)为一模糊决策信息表，属性子集B⊆A，B∩mij≠Ø(i≠j,i,j≤n)，则B是一个模糊正域协调集.

定理4设(U,A∪D,V,f)为一模糊信息决策表，MF为其辨识矩阵，有以下性质：

(1)mii=A，i≤n；

(2)若a为核心属性，当且仅当存在i,j≤n时，

(3)使得mij=a.

(2)设a为核心属性，若任意包含a的可辨识属性集mij(i≠j)中至少含有两个元素，令B=∪i≠j(mij-{a})，则B∩mij≠Ø(∀i≠j).由定理3可知，B是一个模糊正域协调集，因而存在C⊆B使得C为一个模糊正域约简.显然a∉C，这与a为核心属性矛盾.

反之，设mi0j0={a}，∃B⊆A(a∉B)为一个模糊正域约简，则B是一个模糊正域协调集，由定理3可知，B∩mij≠Ø(i≠j,i,j≤n)，这与B∩mi0j0≠Ø矛盾，故若B为一个模糊正域约简，均有a∈B，由核心属性定义可知，a为核心属性.

定义10设(U,A∪D,V,f)为一模糊决策信息决策表，MF为模糊决策信息表的可辨识矩阵，定义fF(U,RA)=∧{∨mij}，其中i≠j.称fF(U,RA)为(U,A∪D,V,f)上的记辨识函数.

证明根据定义9、定理3和最小析取范式的定义即可证得结论.

所有约简集合的交集称为核心属性，记为CoreF(A).

3 实例分析

例1设属性集A={a1,a2,a3,a4}，决策属性集合D={d}，对象集U={x1,x2,…,x7}，映射f:U×A→V，模糊决策表(U,A∪D,V,f)如表1所示.

表1 模糊决策表(U,A∪D,V,f)

同样的方法，可以得到A的所有子集的模糊容差关系矩阵.令

由此计算出关于所有属性子集的直觉模糊正域依赖度如下：

kA=0.91,k{a1,a2,a4}=0.90,k{a1,a2}=0.81,k{a2,a4}=0.76,k{a1,a2,a3}=0.84,k{a1,a3}=0.36,k{a2,a3}=0.71,k{a1,a3,a4}=0.85,k{a2,a3,a4}=0.84,k{a3,a4}=0.75,k{a1,a4}=0.80,k{a1}=0.30,k{a2}=0.61,k{a3}=0.19,k{a4}=0.46.

令I=↖L，根据定义5有，γA=1,γ{a1,a2,a4}=0.99,γ{a1,a2}=0.90,γ{a2,a4}=0.85,γ{a1,a2,a3}=0.93,γ{a1,a3}=0.45,γ{a2,a3}=0.80,γ{a1,a3,a4}=0.94,γ{a2,a3,a4}=0.93,γ{a3,a4}=0.84,γ{a1,a4}=0.89,γ{a1}=0.39,γ{a2}=0.70,γ{a3}=0.28,γ{a4}=0.55.

若α=0.95，则B={a1,a2,a4}为L-决策约简；若α=0.90，则{a1,a3,a4,a2,a3,a4,a1,a2}为L-决策约简.

表2 属性集合A的模糊容差关系矩阵

例2例1中的模糊决策表(U,A∪D,V,f)，根据定义7，可得到属性集合A的新模糊不可辨识关系矩阵，见表3.

表3 属性集合A的新模糊容差关系矩阵

根据定义9，可得到模糊信息决策表(U,A∪D,V,f)的辨识矩阵MF如表4. 由定义10中辨识函数计算公式可知，B={a1,a2,a4}为模糊信息决策表(U,A∪D,V,f)的一个约简.a1,a2,a4均为核心属性.

表4 辨识矩阵

利用模糊L-测度求解模糊信息决策表约简时，最坏的情况是，先求出所有属性子集所对应的模糊关系矩阵，然后再求各个关系矩阵下的模糊正域，其计算时间复杂度应不小于o(2n·(m+n)n2)；利用辨识矩阵求解约简时，不需要求解所有属性子集的模糊关系矩阵及相应模糊正域，在最坏情况下的时间复杂度为o((3m+n)n2). 因此，辨识矩阵方法在求解约简时可大大降低时间复杂度.