局部广义多粒度粗糙集*

2020-09-03李敏赢

计算机工程与科学 2020年8期

王虹，李敏赢

(山西师范大学数学与计算机科学学院,山西临汾 041004)

1 引言

粗糙集理论是由Pawlak[1,2]在1982年提出的，它是处理不精确、不确定、模糊的有效工具。该理论已广泛应用于数据挖掘、特征选择、粒计算等领域。经典粗糙集理论是基于单粒即仅有一个等价关系,而多粒度粗糙集是与多个粒结构有关,即具有多个等价关系。多粒度粗糙集是由Qian等[3]在2006年首次提出的，是粗糙集理论的一个重要研究方向，并已成功地应用在许多方面，如多源信息系统、多尺度信息系统等[4]。近几年来已经被许多学者关注并广泛研究。Qian等[5]研究了局部多粒度决策论粗糙集，Wang等[6]提出了局部领域粗糙集。文献[7]在多粒度粗糙集的基础上提出了广义多粒度粗糙集与最优粒选择。文献[8-10]提出了多粒度粗糙集模型，分为乐观多粒度粗糙集和悲观多粒度粗糙集。Liu[11]提出了变精度粗糙集的矩阵方法。Yao等[12]研究了多粒空间的4种粗糙集模型并提出了一个统一框架来分类和比较现有的研究结果。 Qian等[13]用局部粗糙集解决大数据中粗糙数据分析。汪小燕等[14]研究了基于矩阵的多粒度粗糙集上、下近似表示。刘凤玲等[15]提出了局部邻域多粒度粗糙集模型。以上模型依然存在不足，如广义多粒度粗糙集处理海量数据比较耗时，局部多粒度粗糙集模型中乐观和悲观模型过于严格或过于宽松，具有一定的局限性。

本文将在这些研究的基础上，研究局部广义多粒度粗糙集模型，同时提出一种用矩阵求解局部广义多粒度粗糙集上下近似的方法，既考虑了少数服从多数的情况，又节省了时间。

2 预备知识

2.1 广义多粒度粗糙集的上下近似

2.2 局部多粒度粗糙集

定义3[5]设R1,R2,…,Rm⊆R是U上的m个等价关系，∀X⊆U,局部多粒度粗糙集上下近似定义为：

{x|P(X|[x]R1)≥α∨P(X|[x]R2)≥

α∨…∨P(X|[x]Rm)≥α}

边界域或者不确定性区域的定义为：

2.3 关系矩阵[11]

设U={x1,x2,…,xn}是有限对象集，R是U上的二元关系，定义rR(x)={y|y∈U,xRy}。如果∀x∈U,rR(x)≠∅，则R是串行的。

如果∀X⊆U,∀x∈U,定义X的特征函数λX为：

定义4对于U上串行的关系R,假设MR=(aij)n×n是R的关系矩阵，即aij=λR(xi,xj)。定义n×n矩阵:

WR=NRMR=

设R是U上串行的关系。∀X⊆U,则：

其中T表示转置。

3 局部广义多粒度粗糙集模型

3.1 局部广义多粒度粗糙集的上下近似

对于未标记数据，即在决策属性下只能有限数据带标记，当求广义多粒度粗糙集下近似和上近似时需要所有对象的等价类，包括标记对象和未标记对象，而局部广义多粒度粗糙集上近似用等价类的并表示，即某些对象的等价类里包含未标记的对象，只需要计算目标概念X的对象，因此可用带标记的有限数据集充分发现未标记数据集隐藏的信息，同时也节约了大量时间。

3.2 局部广义多粒度粗糙集上下近似的矩阵表示

定义6设I=(U,A,V,f)是信息系统，设U={x1,x2,…,xn},X⊆U,P={P1,P2,…,Pl},Pi⊆A(i=1,2,…,l)，设关于X的特征函数为:

记对角矩阵:

和对象多粒关系矩阵:

其中,aij=Ri(x,xj);i=1,2,…,l;j=1,2,…,n。根据矩阵的乘法得:

WR(x)=NR(x)M(x)=

μ(x)=WR(x)λX(x)=

设X={xi1,xi2,…,xis},(μ(x))α是μ(x)的α截集，则有I=E1×n(μ(x))α=(l1,l2,…,ls),(μ(x))α=(μ(xi1),μ(xi2),…,μ(xis))α。

定义7设I=(U,A,V,f)是信息系统，X⊆U,P={P1,P2,…,Pl},Pi⊆A(i=1,2,…,l),称(μ(x))α是关于X多粒度粗糙集布尔矩阵。

定义9设I=(U,A,V,f)是信息系统，X⊆U,P={P1,P2,…,Pl},Pi⊆A(i=1,2,…,l),关于X多粒度粗糙集矩阵Bβ(X)=(bij)定义为：

多粒度粗糙集矩阵包含|X|行、l列，其中|X|表示X中元素的个数，l表示粒度个数，多粒度粗糙集矩阵的非空元素由等价类或者∅组成。

关于X多粒度粗糙集矩阵表示为:

记:

定义10设I=(U,A,V,f)是信息系统，X⊆U,P={P1,P2,…,Pl},Pi⊆A(i=1,2,…,l),局部广义多粒度粗糙集上近似为:

其中,lλ是整数时，h=lλ;当lλ是分数时，h=[lλ]+1。

引理1[7]∀a1,a2,b1,b2∈[0,1],下列不等式成立：

(1)a1∧b1+a2∧b2≤(a1+a2)∧(b1+b2);

(2)a1∨b1+a2∨b2≤(a1+a2)∨(b1+b2)。

定理1设I=(U,A,V,f)是信息系统，X,Y⊆U,P={P1,P2,…,Pl},Pi⊆A(i=1,2,…,l)。∀λ∈(0,1],当α>β时,下列性质成立：

证明(1)和(2)可直接由局部广义多粒度粗糙集的上下近似得到。

而

由引理1可得:

(7)、(8)的证明与(5)、(6)的类似。

(12)的证明与(11)的类似。

(14) 由(4)和(12)直接得证。

定理2设I=(U,A,V,f)是信息系统，X⊆U,P={P1,P2,…,Pl},Pi⊆A(i=1,2,…,l)。∀λ∈(0,1],当α>β时,局部广义多粒度粗糙集的上下近似与乐观多粒度粗糙集和悲观多粒度粗糙集有下列性质成立：

(2)的证明与(1)的类似。

例1表1是一个信息系统，假设P={P1,P2,P3},α=0.6,β=0.4,λ=0.7,X1={x1,x2,x3,x4,x7},X2={x1,x2,x3,x4,x7,x8}。

Table 1 Information system 1表1 信息系统1

为了计算局部广义多粒度粗糙集的下近似，只需要计算来自集合X1中对象的等价类，经计算可得：

[x1]P1={x1,x2,x3},[x2]P1={x1,x2,x3},[x3]P1={x1,x2,x3},[x4]P1={x4,x5,x8},[x7]P1={x6,x7}。

[x1]P2={x1,x2},[x2]P2={x1,x2},[x3]P2={x3,x8},[x4]P2={x4,x5,x6},[x7]P2={x7}。

[x1]P3={x1,x3},[x2]P3={x2},[x3]P3={x1,x3},[x4]P3={x4,x5,x6},[x7]P3={x7,x8}。

当β=0.4,λ=0.7时,经计算可得矩阵:

综上注1一般不成立。

例2表2是一个信息系统，假设P={P1,P2,P3,P4},其中P1={a,b},P2={c,d},P3={e,f},P4={g},α=0.6,β=0.4,λ=0.6,X={x1,x2,x4,x5,x8,x9,x16}。

Table 2 Information system 2表2 信息系统2

为了计算局部广义多粒度粗糙集的下近似，只需要计算来自集合X中对象的等价类，经计算可得：

[x1]P1={x1,x4,x9,x11,x16},[x2]P1={x2,x6,x13,x15},[x4]P1={x2,x6,x13,x15},[x5]P1={x5,x8,x10},[x8]P1={x5,x8,x10},[x9]P1={x1,x4,x9,x11,x16},[x16]P1={x1,x4,x9,x11,x16}。

[x1]P2={x1,x8,x9},[x2]P2={x2,x4,x16},[x4]P2={x2,x4,x16},[x5]P2={x5,x7},[x8]P2={x1,x8,x9},[x9]P2={x1,x8,x9},[x16]P2={x2,x4,x16}。

[x1]P3={x1,x2,x4,x8},[x2]P3={x1,x2,x4,x8},[x4]P3={x1,x2,x4,x8},[x5]P3={x5,x16},[x8]P3={x1,x2,x4,x8},[x9]P3={x9,x13,x15},[x16]P3={x5,x16}。

[x1]P4={x1,x8,x11,x15},[x2]P4={x2,x3,x7,x16},[x4]P4={x4,x12},[x5]P4={x5,x9,x13,x14},[x8]P4={x1,x8,x11,x15},[x9]P4={x5,x9,x13,x14},[x16]P4={x2,x3,x7,x16}。

当β=0.4,λ=0.6时,经计算可得矩阵Bβ(X)。

Bβ(X)=[B1B2]

为了计算广义多粒度粗糙集的下近似，只需要计算来自集合U中对象的等价类，经计算可得：

[x1]P1={x1,x4,x9,x11,x16},[x2]P1={x2,x6,x13,x15},[x3]P1={x3,x7,x12,x14},[x4]P1={x2,x6,x13,x15},[x5]P1={x5,x8,x10},[x6]P1={x2,x6,x13,x15},[x7]P1={x3,x7,x12,x14},[x8]P1={x5,x8,x10},[x9]P1={x1,x4,x9,x11,x16},[x10]P1={x5,x8,x10},[x11]P1={x1,x4,x9,x11,x16},[x12]P1={x3,x7,x12,x14},[x13]P1={x2,x6,x13,x15},[x14]P1={x3,x7,x12,x14},[x15]P1={x2,x6,x13,x15},[x16]P1={x1,x4,x9,x11,x16}。

[x1]P2={x1,x8,x9},[x2]P2={x2,x4,x16},[x3]P2={x3,x6,x10,x13},[x4]P2={x2,x4,x16},[x5]P2={x5,x7},[x6]P2={x3,x6,x10,x13},[x7]P2={x5,x7},[x8]P2={x1,x8,x9},[x9]P2={x1,x8,x9},[x10]P2={x3,x6,x10,x13},[x11]P2={x11,x12,x15},[x12]P2={x11,x12,x15},[x13]P2={x3,x6,x10,x13},[x14]P2={x14},[x15]P2={x11,x12,x15},[x16]P2={x2,x4,x16}。

[x1]P3={x1,x2,x4,x8},[x2]P3={x1,x2,x4,x8},[x3]P3={x3,x6,x11,x14},[x4]P3={x1,x2,x4,x8},[x5]P3={x5,x16},[x6]P3={x3,x6,x11,x14},[x7]P3={x7,x10,x12},[x8]P3={x1,x2,x4,x8},[x9]P3={x9,x13,x15},[x10]P3={x7,x10,x12},[x11]P3={x3,x6,x11,x14},[x12]P3={x7,x10,x12},[x13]P3={x9,x13,x15},[x14]P3={x3,x6,x11,x14},[x15]P3={x9,x13,x15},[x16]P3={x5,x16}。

[x1]P4={x1,x8,x11,x15},[x2]P4={x2,x3,x7,x16},[x3]P4={x2,x3,x7,x16},[x4]P4={x4,x12},[x5]P4={x5,x9,x13,x14},[x6]P4={x6,x10},[x7]P4={x2,x3,x7,x16},[x8]P4={x1,x8,x11,x15},[x9]P4={x5,x9,x13,x14},[x10]P4={x6,x10},[x11]P4={x1,x8,x11,x15},[x12]P4={x4,x12},[x13]P4={x5,x9,x13,x14},[x14]P4={x5,x9,x13,x14},[x15]P4={x1,x8,x11,x15},[x16]P4={x2,x3,x7,x16}。

通过例2可得，局部广义多粒度粗糙集模型在每个粒下只需要计算7个等价类，而广义多粒度粗糙集模型在每个粒下只需要计算16个等价类，从而节省了大量时间。

算法1计算局部广义多粒粗糙集下近似的算法

输入：I=(U,A,V,f)是一个信息系统，粒度空间P={P1,P2,…,Pl},Pi⊆A(i=1,2,…,l),目标概念X⊆U,参数α,λ。

输出：下近似集LL。

步骤1 Fori=1 tol,j=1 to |X|

计算[xj]Pi;

4 结束语

多粒度粗糙集是从多个角度和多个层次进行问题求解的，是经典粗糙集的推广，已经被大量学者广泛研究，本文在广义多粒度粗糙集模型的基础上进一步提出了局部广义多粒度粗糙集模型。在此基础上，给出了一种用矩阵求解局部广义多粒度粗糙集上下近似的方法，进一步研究了他们的性质。最后，通过一个实例来验证它的有效性。未来，将研究不同信息系统的局部粗糙集模型。