局部廣義多粒度粗糙集*

王 虹，李敏贏

(山西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,山西 臨汾 041004)

1 引言

粗糙集理論是由Pawlak[1,2]在1982年提出的，它是處理不精確、不確定、模糊的有效工具。該理論已廣泛應(yīng)用于數(shù)據(jù)挖掘、特征選擇、粒計(jì)算等領(lǐng)域。經(jīng)典粗糙集理論是基于單粒即僅有一個(gè)等價(jià)關(guān)系,而多粒度粗糙集是與多個(gè)粒結(jié)構(gòu)有關(guān),即具有多個(gè)等價(jià)關(guān)系。多粒度粗糙集是由Qian等[3]在2006年首次提出的，是粗糙集理論的一個(gè)重要研究方向，并已成功地應(yīng)用在許多方面，如多源信息系統(tǒng)、多尺度信息系統(tǒng)等[4]。近幾年來(lái)已經(jīng)被許多學(xué)者關(guān)注并廣泛研究。Qian等[5]研究了局部多粒度決策論粗糙集，Wang等[6]提出了局部領(lǐng)域粗糙集。 文獻(xiàn)[7]在多粒度粗糙集的基礎(chǔ)上提出了廣義多粒度粗糙集與最優(yōu)粒選擇。文獻(xiàn)[8-10]提出了多粒度粗糙集模型，分為樂(lè)觀多粒度粗糙集和悲觀多粒度粗糙集。Liu[11]提出了變精度粗糙集的矩陣方法。Yao等[12]研究了多?？臻g的4種粗糙集模型并提出了一個(gè)統(tǒng)一框架來(lái)分類(lèi)和比較現(xiàn)有的研究結(jié)果。 Qian等[13]用局部粗糙集解決大數(shù)據(jù)中粗糙數(shù)據(jù)分析。汪小燕等[14]研究了基于矩陣的多粒度粗糙集上、下近似表示。劉鳳玲等[15]提出了局部鄰域多粒度粗糙集模型。以上模型依然存在不足，如廣義多粒度粗糙集處理海量數(shù)據(jù)比較耗時(shí)，局部多粒度粗糙集模型中樂(lè)觀和悲觀模型過(guò)于嚴(yán)格或過(guò)于寬松，具有一定的局限性。

本文將在這些研究的基礎(chǔ)上，研究局部廣義多粒度粗糙集模型，同時(shí)提出一種用矩陣求解局部廣義多粒度粗糙集上下近似的方法，既考慮了少數(shù)服從多數(shù)的情況，又節(jié)省了時(shí)間。

2 預(yù)備知識(shí)

2.1 廣義多粒度粗糙集的上下近似

2.2 局部多粒度粗糙集

定義3[5]設(shè)R1,R2,…,Rm?R是U上的m個(gè)等價(jià)關(guān)系，?X?U,局部多粒度粗糙集上下近似定義為：

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

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

邊界域或者不確定性區(qū)域的定義為：

2.3 關(guān)系矩陣[11]

設(shè)U={x1,x2,…,xn}是有限對(duì)象集，R是U上的二元關(guān)系，定義rR(x)={y|y∈U,xRy}。如果?x∈U,rR(x)≠?，則R是串行的。

如果?X?U,?x∈U,定義X的特征函數(shù)λX為：

定義4對(duì)于U上串行的關(guān)系R,假設(shè)MR=(aij)n×n是R的關(guān)系矩陣，即aij=λR(xi,xj)。定義n×n矩陣:

WR=NRMR=

設(shè)R是U上串行的關(guān)系。?X?U,則：

其中T表示轉(zhuǎn)置。

3 局部廣義多粒度粗糙集模型

3.1 局部廣義多粒度粗糙集的上下近似

對(duì)于未標(biāo)記數(shù)據(jù)，即在決策屬性下只能有限數(shù)據(jù)帶標(biāo)記，當(dāng)求廣義多粒度粗糙集下近似和上近似時(shí)需要所有對(duì)象的等價(jià)類(lèi)，包括標(biāo)記對(duì)象和未標(biāo)記對(duì)象，而局部廣義多粒度粗糙集上近似用等價(jià)類(lèi)的并表示，即某些對(duì)象的等價(jià)類(lèi)里包含未標(biāo)記的對(duì)象，只需要計(jì)算目標(biāo)概念X的對(duì)象，因此可用帶標(biāo)記的有限數(shù)據(jù)集充分發(fā)現(xiàn)未標(biāo)記數(shù)據(jù)集隱藏的信息，同時(shí)也節(jié)約了大量時(shí)間。

3.2 局部廣義多粒度粗糙集上下近似的矩陣表示

定義6設(shè)I=(U,A,V,f)是信息系統(tǒng)，設(shè)U={x1,x2,…,xn},X?U,P={P1,P2,…,Pl},Pi?A(i=1,2,…,l)，設(shè)關(guān)于X的特征函數(shù)為:

記對(duì)角矩陣:

和對(duì)象多粒關(guān)系矩陣:

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

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

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

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

定義7設(shè)I=(U,A,V,f)是信息系統(tǒng)，X?U,P={P1,P2,…,Pl},Pi?A(i=1,2,…,l),稱(chēng)(μ(x))α是關(guān)于X多粒度粗糙集布爾矩陣。

定義9設(shè)I=(U,A,V,f)是信息系統(tǒng)，X?U,P={P1,P2,…,Pl},Pi?A(i=1,2,…,l),關(guān)于X多粒度粗糙集矩陣Bβ(X)=(bij)定義為：

多粒度粗糙集矩陣包含|X|行、l列，其中|X|表示X中元素的個(gè)數(shù)，l表示粒度個(gè)數(shù)，多粒度粗糙集矩陣的非空元素由等價(jià)類(lèi)或者?組成。

關(guān)于X多粒度粗糙集矩陣表示為:

記:

定義10設(shè)I=(U,A,V,f)是信息系統(tǒng)，X?U,P={P1,P2,…,Pl},Pi?A(i=1,2,…,l),局部廣義多粒度粗糙集上近似為:

其中,lλ是整數(shù)時(shí)，h=lλ;當(dāng)lλ是分?jǐn)?shù)時(shí)，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設(shè)I=(U,A,V,f)是信息系統(tǒng)，X,Y?U,P={P1,P2,…,Pl},Pi?A(i=1,2,…,l)。?λ∈(0,1],當(dāng)α>β時(shí),下列性質(zhì)成立：

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

而

由引理1可得:

(7)、(8)的證明與(5)、(6)的類(lèi)似。

(12)的證明與(11)的類(lèi)似。

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

定理2設(shè)I=(U,A,V,f)是信息系統(tǒng)，X?U,P={P1,P2,…,Pl},Pi?A(i=1,2,…,l)。?λ∈(0,1],當(dāng)α>β時(shí),局部廣義多粒度粗糙集的上下近似與樂(lè)觀多粒度粗糙集和悲觀多粒度粗糙集有下列性質(zhì)成立：

(2)的證明與(1)的類(lèi)似。

例1表1是一個(gè)信息系統(tǒng)，假設(shè)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 信息系統(tǒng)1

為了計(jì)算局部廣義多粒度粗糙集的下近似，只需要計(jì)算來(lái)自集合X1中對(duì)象的等價(jià)類(lèi)，經(jīng)計(jì)算可得：

[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}。

D(X1|[x1]P1)=1,D(X1|[x2]P1)=1,D(X1|[x3]P1)=1,D(X1|[x4]P1)=1/3,D(X1|[x7]P1)=1/2,D(X1|[x1]P2)=1,D(X1|[x2]P2)=1,D(X1|[x3]P2)=1/2,D(X1|[x4]P2)=1/3,D(X1|[x7]P2)=1,D(X1|[x1]P3)=1,D(X1|[x2]P3)=1,D(X1|[x3]P3)=1,D(X1|[x4]P3)=1/3,D(X1|[x7]P3)=1/2。

當(dāng)β=0.4,λ=0.7時(shí),經(jīng)計(jì)算可得矩陣:

綜上注1一般不成立。

例2表2是一個(gè)信息系統(tǒng)，假設(shè)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 信息系統(tǒng)2

為了計(jì)算局部廣義多粒度粗糙集的下近似，只需要計(jì)算來(lái)自集合X中對(duì)象的等價(jià)類(lèi)，經(jīng)計(jì)算可得：

[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}。

D(X|[x1]P1)=4/5,D(X|[x2]P1)=1/4,D(X|[x4]P1)=4/5,D(X|[x5]P1)=2/3,D(X|[x8]P1)=2/3,D(X|[x9]P1)=4/5,D(X|[x16]P1)=4/5。

D(X|[x1]P2)=1,D(X|[x2]P2)=1,D(X|[x4]P2)=1,D(X|[x5]P2)=1/2,D(X|[x8]P2)=1,D(X|[x9]P2)=1,D(X|[x16]P2)=1。

D(X|[x1]P3)=1,D(X|[x2]P3)=1,D(X|[x4]P3)=1,D(X|[x5]P3)=1/2,D(X|[x8]P3)=1,D(X|[x9]P3)=1/3,D(X|[x16]P3)=1。

D(X|[x1]P4)=1/2,D(X|[x2]P4)=1/2,D(X|[x4]P4)=1/2,D(X|[x5]P4)=1/2,D(X|[x8]P4)=1/2,D(X|[x9]P4)=1/2,D(X|[x16]P4)=1/2。

當(dāng)β=0.4,λ=0.6時(shí),經(jīng)計(jì)算可得矩陣Bβ(X)。

Bβ(X)=[B1B2]

為了計(jì)算廣義多粒度粗糙集的下近似，只需要計(jì)算來(lái)自集合U中對(duì)象的等價(jià)類(lèi)，經(jīng)計(jì)算可得：

[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}。

D(X|[x1]P1)=4/5,D(X|[x2]P1)=1/4,D(X|[x3]P1)=0,D(X|[x4]P1)=4/5,D(X|[x5]P1)=2/3,D(X|[x6]P1)=4/5,D(X|[x7]P1)=0,D(X|[x8]P1)=2/3,D(X|[x9]P1)=4/5,D(X|[x10]P1)=2/3,D(X|[x11]P1)=4/5,D(X|[x12]P1)=0,D(X|[x13]P1)=1/4,D(X|[x15]P1)=1/4,D(X|[x16]P1)=4/5。

D(X|[x1]P2)=1,D(X|[x2]P2)=1,D(X|[x3]P2)=0,D(X|[x4]P2)=1,D(X|[x5]P2)=1/2,D(X|[x6]P2)=0,D(X|[x7]P2)=1/2,D(X|[x8]P2)=1,D(X|[x9]P2)=1,D(X|[x10]P2)=0,D(X|[x11]P2)=0,D(X|[x12]P2)=0,D(X|[x13]P2)=0,D(X|[x14]P2)=0,D(X|[x15]P2)=0,D(X|[x16]P2)=1。

D(X|[x1]P3)=1,D(X|[x2]P3)=1,D(X|[x3]P3)=0,D(X|[x4]P3)=1,D(X|[x5]P3)=1/2,D(X|[x6]P3)=0,D(X|[x7]P3)=0,D(X|[x8]P3)=1,D(X|[x9]P3)=1/3,D(X|[x10]P3)=0,D(X|[x11]P3)=0,D(X|[x12]P3)=0,D(X|[x13]P3)=1/3,D(X|[x14]P3)=0,D(X|[x15]P3)=1/3,D(X|[x16]P3)=1。

D(X|[x1]P4)=1/2,D(X|[x2]P4)=1/2,D(X|[x3]P4)=1/2,D(X|[x4]P4)=1/2,D(X|[x5]P4)=1/2,D(X|[x6]P4)=0,D(X|[x7]P4)=1/2,D(X|[x8]P4)=1/2,D(X|[x9]P4)=1/2,D(X|[x10]P4)=0,D(X|[x11]P4)=1/2,D(X|[x12]P4)=1/2,D(X|[x13]P4)=1/2,D(X|[x14]P4)=1/2,D(X|[x15]P4)=1/2,D(X|[x16]P4)=1/2。

通過(guò)例2可得，局部廣義多粒度粗糙集模型在每個(gè)粒下只需要計(jì)算7個(gè)等價(jià)類(lèi)，而廣義多粒度粗糙集模型在每個(gè)粒下只需要計(jì)算16個(gè)等價(jià)類(lèi)，從而節(jié)省了大量時(shí)間。

算法1計(jì)算局部廣義多粒粗糙集下近似的算法

輸入：I=(U,A,V,f)是一個(gè)信息系統(tǒng)，粒度空間P={P1,P2,…,Pl},Pi?A(i=1,2,…,l),目標(biāo)概念X?U,參數(shù)α,λ。

輸出：下近似集LL。

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

計(jì)算[xj]Pi;

4 結(jié)束語(yǔ)

多粒度粗糙集是從多個(gè)角度和多個(gè)層次進(jìn)行問(wèn)題求解的，是經(jīng)典粗糙集的推廣，已經(jīng)被大量學(xué)者廣泛研究，本文在廣義多粒度粗糙集模型的基礎(chǔ)上進(jìn)一步提出了局部廣義多粒度粗糙集模型。在此基礎(chǔ)上，給出了一種用矩陣求解局部廣義多粒度粗糙集上下近似的方法，進(jìn)一步研究了他們的性質(zhì)。最后，通過(guò)一個(gè)實(shí)例來(lái)驗(yàn)證它的有效性。未來(lái)，將研究不同信息系統(tǒng)的局部粗糙集模型。