可調(diào)整多粒度覆蓋粗糙集模型

葉培培,呂躍進

(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院, 廣西南寧530004)

?

可調(diào)整多粒度覆蓋粗糙集模型

葉培培,呂躍進

(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院, 廣西南寧530004)

摘要:多粒度粗糙集是近幾年粗糙集理論的一個研究熱點，而其中的多粒度覆蓋粗糙集的研究集中于模型的推廣，文中分析樂觀多粒度覆蓋粗糙集下近似的不足之處，提出了一種可調(diào)整的多粒度覆蓋粗糙集。研究可調(diào)整多粒度覆蓋粗糙集的性質(zhì)，并提出一種粒度重要性的啟發(fā)式約簡算法，實例分析結(jié)果驗證該方法的可行性。

關(guān)鍵詞:多粒度，覆蓋信息系統(tǒng)，粒度約簡

0引言

粗糙集理論[1-2]是波蘭數(shù)學(xué)家Pawlak于1982年提出的，它可以作為一種分析和處理不確定、不精確、不完整信息的有效方法。經(jīng)過三十多年的發(fā)展，已被廣泛應(yīng)用到數(shù)據(jù)挖掘[3]、知識發(fā)現(xiàn)[4]、圖像處理[5]、模式識別[6]等領(lǐng)域。經(jīng)典粗糙集通過構(gòu)建不可分辨的二元關(guān)系(等價關(guān)系)定義上、下近似來刻畫未知的概念。隨著研究的進一步深入，等價關(guān)系逐步被弱化，如優(yōu)勢關(guān)系[7]、容差關(guān)系[8]、相似關(guān)系[9]等。

從粒的角度看，經(jīng)典粗糙集及其推廣的粗糙集模型都是在單粒度空間上進行目標(biāo)概念刻畫的。然而在粒計算理論中，多粒度是最重要的概念之一。多粒度表示在兩個甚至多個不同的粒空間上對目標(biāo)概念問題進行研究。同時由于實際問題處理的需要，文獻[10]提出了多粒度粗糙集的概念。文獻[11-12]將多粒度的思想引入到覆蓋粗糙集中，其中文獻[11]提出了一種基于覆蓋近似空間中一個對象最小描述的多粒度覆蓋粗糙集模型，經(jīng)分析其模型中下近似的定義過于寬松，即在m個粒結(jié)構(gòu)下只要一個粒結(jié)構(gòu)中存在Cij∈MdCi(x),使得Cij?X成立，那么x就屬于X的下近似。文獻[12]根據(jù)單粒度的覆蓋粗糙集(交運算成立)推廣到多粒度覆蓋粗糙集，其不足同文獻[11]的一樣?；诖耍疚奶岢隽丝烧{(diào)整多粒度覆蓋粗糙集，在m個粒結(jié)構(gòu)下只要一定數(shù)目的粒結(jié)構(gòu)中存在知識粒[x]Pi，滿足[x]Pi?X，就可認為x屬于X的下近似，并研究可調(diào)整多粒度覆蓋粗糙集的性質(zhì)。

另一方面，對粒度約簡算法的研究，目前有文獻[13]在等價關(guān)系下研究悲觀多粒度粗糙集的一種粒度重要度，以此為啟發(fā)設(shè)計了一種粒度約簡算法。文獻[14]在等價關(guān)系下研究悲觀多粒度粗糙集的粒度約簡，以粒度的信息量為啟發(fā)因子，設(shè)計了一種信息量的悲觀多粒度約簡算法。學(xué)者研究的是在等價關(guān)系下的多粒度粗糙集粒度約簡，對于非等價關(guān)系的尚無研究，本文研究一種非等價關(guān)系在可調(diào)整多粒度覆蓋粗糙集下的一種粒度約簡的算法。

1預(yù)備知識

1.1　單粒度粗糙集

定義2設(shè)(U,AT,V,F)為信息系統(tǒng)，?A?AT，定義A上的不可分辨關(guān)系[2]：

IND(A)={(x,y)∈U2|,?a∈A,f(x,a)=f(y,a)}。

不可分辨關(guān)系滿足傳遞性、自反性和對稱性，為U上的一個等價關(guān)系，由這個等價關(guān)系可以導(dǎo)出U上的一個劃分，記為U/IND(A),?x∈U,那么x的等價類可記為[x]A，[x]A={y∈U|(x,y)∈IND(A)}。

定義3設(shè)(U,AT,V,F)為一個信息系統(tǒng)，對?X?U,A?AT,定義X關(guān)于屬性A的下、上近似[2]，分別記為:

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

也被稱為一個粒結(jié)構(gòu)。

1.2　覆蓋粗糙集

定義4設(shè)U為論域,C={c1,c2,…,cn}是論域U上的一個覆蓋。對?x∈U,x在覆蓋近似空間中的最小描述[16]記為Mdc(x),MdC(x)={ci∈C|x∈ci∧?cj∈C, (x∈cj∧cj?ci?ci=cj)}。

1.3　多粒度覆蓋粗糙集

定義6設(shè)U為論域,C1,C2,…,Ck為論域上的一族覆蓋。對?X?U,則X的多粒度覆蓋粗糙集定義[11]如下:

命題1設(shè)U為論域,C1,C2,…,Ck為論域上的一族覆蓋[11]，對?X?U,則有：

命題1說明了多粒度覆蓋粗糙集的下近似是所有單粒度覆蓋下近似的并，也就是說只要其中一個粒度存在Cij∈MdCi(x),使得Cij?X成立，那么x就屬于X的下近似；而上近似就是所有單粒度覆蓋上近似的交。

2可調(diào)整多粒度覆蓋粗糙集模型

由定義6知,覆蓋近似空間中一個對象最小描述的多粒度覆蓋粗糙集(樂觀多粒度覆蓋粗糙集)的下近似僅要求在m個粒結(jié)構(gòu)下只要有一個粒結(jié)構(gòu)中存在Cij∈MdCi(x),使得Cij?X成立,x就屬于X的下近似，這個條件太過于寬松。本文則在m個粒結(jié)構(gòu)下只要有一定數(shù)目的粒結(jié)構(gòu)中存在知識粒[x]Pi，使得[x]Pi?X，就認為x屬于X的下近似。并且用參數(shù)α來控制滿足條件的粒結(jié)構(gòu)的個數(shù)，于是稱此為可調(diào)整多粒度覆蓋粗糙集。這樣就能夠解決對象最小描述誘導(dǎo)的多粒度覆蓋粗糙集下近似過松的問題。

由于在覆蓋決策信息系統(tǒng)中，每個屬性都可以產(chǎn)生一個覆蓋，即每個屬性都可以產(chǎn)生一個粒度，所以本文研究的可調(diào)整多粒度覆蓋粗糙集中的覆蓋是屬性產(chǎn)生的覆蓋。

2.1　可調(diào)整多粒度粗糙集模型的定義

定義7設(shè)U是有限論域，C是U的一個子集族，如果C中的子集都是非空的，且∪C=U，則稱C是U的一個覆蓋。若C={C1,C2,…,Cm}中的每個Ci(i≤m)都是U的覆蓋，則稱C是U的覆蓋族[16]。

定義9Δ={Ci:i=1,2,…,m}是U的一族覆蓋，?x∈U,Δx=∩{Cix:Cix∈Cov(Ci),x∈Cix}，則Cov(Δ)={Δx:x∈U}也是U的一個覆蓋，稱其為由Δ誘導(dǎo)的覆蓋[18]。

定義10設(shè)(U,AT,V,F)為一信息系統(tǒng)，P1,P2,…,Pm?AT，對?X?U，其特征函數(shù)可定義為：

其中[x]Pi是屬性集Pi產(chǎn)生的覆蓋中x所在的類。

定義11設(shè)U為論域,P1,P2,…,Pm?AT，對?X?U,X關(guān)于屬性集P1,P2,…,Pm的可調(diào)整的多粒度覆蓋粗糙集下上近似可分別定義如下：

其中：α∈(0,1],C(Pi)是由屬性集Pi誘導(dǎo)覆蓋。

2.2　可調(diào)整多粒度覆蓋粗糙集性質(zhì)

定理1設(shè)S=(U,AT,V,F)為一信息系統(tǒng),P1,P2,…,Pm?AT,?X,Y?U,可調(diào)整的多粒度覆蓋粗糙集有以下性質(zhì):

證明①和②根據(jù)定義2易證。

同理可證⑥⑦。

3粒度約簡

定義12設(shè)(U,AT∪j5i0abt0b,V,F)是覆蓋決策信息系統(tǒng),P1,P2,…,Pm?AT,P={P1,P2,…,Pm}, 0≤α≤1,D=Cj5i0abt0b={D1,D2,…,Dn}，分別定義:

為下上近似分布函數(shù)。若:

①如果Lp-{Pi}(D)=LP(D)，則稱Pi在粒度集P是不必要的；否則Pi在粒度集P是必要的。

②如果存在Q?P，使得LQ(D)=LP(D)，則稱Q是P的下近似協(xié)調(diào)集，若對Q的任意真子集Q′，都有LQ(D)≠LQ′(D)，則稱Q是P的下近似約簡。

③如果存在Q?P，使得UQ(D)=UP(D)，則稱Q是P的上近似協(xié)調(diào)集，若對Q的任意真子集Q′，都有UQ(D)≠UQ′(D)，則稱Q是P的上近似約簡。

如果Q既是P的上近似分布約簡又是P下近似分布約簡，那么稱Q是P的近似分布約簡。

為了找到約簡，基于多粒度下近似粒度相對重要性的定義，很據(jù)粒度相對重要性找出信息系統(tǒng)的約簡集，由此得出最小的約簡。

定義13設(shè)(U,AT∪j5i0abt0b,V,F)是覆蓋決策信息系統(tǒng)，其中a∈Pi?AT,D=Cj5i0abt0b={D1,D2,D3,…,Dn},則粒度Pt在P下重要性為：

由定義可知sigPt(D)大于或等于零。當(dāng)sigPt(D)=0時，表示約去粒度Pt后，決策類D的下近似分布不發(fā)生變化，則Pt是關(guān)于決策類D下近似不重要的。當(dāng)sigPt(D)>0時，表示約去粒度Pt后決策類D的下近似分布發(fā)生變化，則Pt是關(guān)于決策類D下近似重要的。

約簡算法：

輸入：覆蓋決策信息系統(tǒng)(U,AT∪j5i0abt0b,V,F),P1,P2,…,Pm?AT,Pi∩Pj=Φ(i≠j,i,j=1,2,…,m)，其中P={P1,P2,…,Pm};

輸出：該覆蓋信息系統(tǒng)的約簡；

Step 1: 對每一個Pi∈P，計算其產(chǎn)生的誘導(dǎo)覆蓋C(Pi)以及C(D);

Step 3: 對每一個Pi∈P，計算sigPi(D)， 令P的下近似約簡為R，R=Φ;

Step 4: 判斷LRα(D)=LPα(D)是否成立，若成立則轉(zhuǎn)step 6，否則轉(zhuǎn)step 5;

Step 5: 對任意的Pi∈P,取sigPi(D)為最大值時的Pi，使R=R∪{Pi}, (i=1,2,…,m)，轉(zhuǎn)step 4;

Step 6: 輸出R,R就是粒度集P的約簡集。

例1如表1給出小汽車的信息，AT={P,M,S,MS,FS,L}，其中P,M,S,MS,FS,L分別表示Price，Mileage，Size，Max-Speed，F(xiàn)uel Sumption，Life每個屬性都可以產(chǎn)生一個覆蓋，其中將條件屬性集分成3個粒度，P1={P,M},P2={S,MS},P3={FS,L},根據(jù)前面的定義和定理，對表1進行多粒度的粒約簡。

表1　覆蓋決策信息系統(tǒng)

每個屬性產(chǎn)生的覆蓋如下：

C({FS})={{x1,x5},{x2,x6},{x3,x4}};

C({L})={{x1,x5},{x2,x4},{x3,x6}};

C({D})={{x1,x6},{x2,x5},{x2,x3,x5},{x1,x4,x6}}。

兩個屬性誘導(dǎo)的覆蓋：

利用約簡算法計算各粒度的重要性：

粒度P1的重要性：

sigP1(D)=0。

粒度P2的重要性：

粒度P3的重要性：

4結(jié)語

本文提出了可調(diào)整多粒度覆蓋粗糙集模型，對多粒度覆蓋粗糙集模型進行了推廣。同時定義了粒度重要性，提出了粒度約簡算法。用粒度相對于粒度集重要性找出重要的粒度，對粒度進行約簡。通過實例對文中的算法進行了驗證，結(jié)果表明粒度約簡方法的有效性、合理性。

參考文獻：

[1]PAWLAK Z.Rough Sets[J]. International Journal of Computerand Information sciences, 1982, 11(5): 341-356.

[2]PAWLAK Z.Rudiments of rough sets[J]. Information Sciences, 2007, 177(1): 3-27.

[3]ZHANG Jun-bo, LI Tian-rui, CHEN Hong-mei.Composite rough sets for dynamic data mining [J]. Information Sciences, 2014, 257:81-100.

[4]LI Y L, XIAO D M.Bifurcations of a predator-prey system of Holling and Leslie types[J]. Chaos, Solitons and Fractals,2007,34 (2):606-620.

[5]WANG Q, FAN M, WANG K.Dynamics of class of Nonautonomous semi-ratio-dependent predator-prey systems with functional responses[J]. Math Anal Appl, 2003, 278(2):443-471.

[6]LIANG Ji-ye, WANG Feng, DANG Chuang-yin, et al.An efficient rough feature selection algorithm with a multi-granulation view[J]. Information Journal of Approximate Reasoning, 2012, 53(6): 912-926.

[7]GRECO S, MATARAZZO B, SLOWINSKI R.Rough sets theory for multicriteria decision analysis[J]. European Journal of Operational Research, 2001, 129(1): 1-47.

[8]LEUNG Y, LI D.Maximal consistent block technique for rule acquisition in incomplete information systems[J]. Information Sciences, 2003, 153: 85-106.

[9]STEFANOWSKI J, TSOUKIAS A.Incomplete information tables and rough classification[J]. Computational Intelligence, 2001, 17(3): 545-566.

[10]QIAN YU-HUA, LIANG JI-YE.Rough set method based on multi-granulations[C]//5th IEEE International Conference on Cognitive Informatics. Beijing:IEEE,2006 :297-304.

[11]周國正.一種多粒度覆蓋粗糙集模型[J]. 齊齊哈爾大學(xué)學(xué)報:2012, 28(5): 10-13.

[12]李氣芳,李進金,林國平.多粒度覆蓋信息系統(tǒng)的屬性約簡方法比較[J]. 計算機工程與應(yīng)用,2013, 49(10):121-124.

[13]桑妍麗, 錢宇華.一種悲觀多粒度粗糙集中的粒度約簡算法[J]. 模式識別與人工智能,2012, 25(3):361-366.

[14]孟慧麗, 馬媛媛, 徐久成.基于信息量的悲觀多粒度粗糙集粒度約簡[J]. 南京大學(xué)學(xué)報:自然科學(xué)版,2015, 51(2):343-348.

[15]張文修, 梁怡, 吳偉志.信息系統(tǒng)與知識發(fā)現(xiàn)[M]. 北京:科學(xué)出版社,2003.

[16]BONIKOWSKI Z, BRYNIARSKI E, WYBRANIEC U .Extensions and intentions in the rough set theory Information Science[J]. Information Sciences, 1998, 107:149-167.

[17]胡軍,王國胤.覆蓋粒度空間的層次模型[J]. 南京大學(xué)學(xué)報:自然科學(xué)版,2008, 44(5):551-558.

[18]CHEN De-gang，WANG Chang-zhong，HU Qing-hua.A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets[J]. Information Sciences,2007, 177(17):3500-3518.

(責(zé)任編輯梁碧芬)

Adjustable multi-granulation covering rough set model

YE Pei-pei, LYU Yue-jin

(College of Mathematics and Information Science, Guangxi University, Nanning 530004,China)

Abstract:Multi-granulation is a research focus in rough sets in recent year, of which multi-granulation covering rough set research focused on the model of the extension.By analyzing the limitations of the optimistic multi-granulation covering rough set, the adjustable multi-granulation covering rough set is proposed.The properties of the adjustable multi-granulation covering rough sets are discussed.Furthermore,the heuristic algorithm of the granular significance is introduced.The experimental results show the effectiveness of the approach.

Key words:multi-granulation; covering information system; granular reduction

中圖分類號:TP181

文獻標(biāo)識碼:A

文章編號：1001-7445(2015)06-1603-08

doi:10.13624/j.cnki.issn.1001-7445.2015.1603

通訊作者：呂躍進(1958—)，男，廣東龍川人，廣西大學(xué)教授; E-mail:lvyjin@126.com。

基金項目：國家自然科學(xué)基金資助項目(71361002)；廣西自然科學(xué)基金資助項目(2013GXNSFAA019016)

收稿日期：2015-09-21；

修訂日期：2015-10-30