可調(diào)整多粒度覆蓋粗糙集模型
2016-01-20 05:08:43葉培培呂躍進(jìn)
葉培培,呂躍進(jìn)
(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院, 廣西南寧530004)
?
可調(diào)整多粒度覆蓋粗糙集模型
葉培培,呂躍進(jìn)
(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院, 廣西南寧530004)
摘要:多粒度粗糙集是近幾年粗糙集理論的一個(gè)研究熱點(diǎn)，而其中的多粒度覆蓋粗糙集的研究集中于模型的推廣，文中分析樂觀多粒度覆蓋粗糙集下近似的不足之處，提出了一種可調(diào)整的多粒度覆蓋粗糙集。研究可調(diào)整多粒度覆蓋粗糙集的性質(zhì)，并提出一種粒度重要性的啟發(fā)式約簡算法，實(shí)例分析結(jié)果驗(yàn)證該方法的可行性。
關(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)系(等價(jià)關(guān)系)定義上、下近似來刻畫未知的概念。隨著研究的進(jìn)一步深入，等價(jià)關(guān)系逐步被弱化，如優(yōu)勢關(guān)系[7]、容差關(guān)系[8]、相似關(guān)系[9]等。
從粒的角度看，經(jīng)典粗糙集及其推廣的粗糙集模型都是在單粒度空間上進(jìn)行目標(biāo)概念刻畫的。然而在粒計(jì)算理論中，多粒度是最重要的概念之一。多粒度表示在兩個(gè)甚至多個(gè)不同的?？臻g上對目標(biāo)概念問題進(jìn)行研究。同時(shí)由于實(shí)際問題處理的需要，文獻(xiàn)[10]提出了多粒度粗糙集的概念。文獻(xiàn)[11-12]將多粒度的思想引入到覆蓋粗糙集中，其中文獻(xiàn)[11]提出了一種基于覆蓋近似空間中一個(gè)對象最小描述的多粒度覆蓋粗糙集模型，經(jīng)分析其模型中下近似的定義過于寬松，即在m個(gè)粒結(jié)構(gòu)下只要一個(gè)粒結(jié)構(gòu)中存在Cij∈MdCi(x),使得Cij?X成立，那么x就屬于X的下近似。文獻(xiàn)[12]根據(jù)單粒度的覆蓋粗糙集(交運(yùn)算成立)推廣到多粒度覆蓋粗糙集，其不足同文獻(xiàn)[11]的一樣?；诖耍疚奶岢隽丝烧{(diào)整多粒度覆蓋粗糙集，在m個(gè)粒結(jié)構(gòu)下只要一定數(shù)目的粒結(jié)構(gòu)中存在知識粒[x]Pi，滿足[x]Pi?X，就可認(rèn)為x屬于X的下近似，并研究可調(diào)整多粒度覆蓋粗糙集的性質(zhì)。
另一方面，對粒度約簡算法的研究，目前有文獻(xiàn)[13]在等價(jià)關(guān)系下研究悲觀多粒度粗糙集的一種粒度重要度，以此為啟發(fā)設(shè)計(jì)了一種粒度約簡算法。文獻(xiàn)[14]在等價(jià)關(guān)系下研究悲觀多粒度粗糙集的粒度約簡，以粒度的信息量為啟發(fā)因子，設(shè)計(jì)了一種信息量的悲觀多粒度約簡算法。學(xué)者研究的是在等價(jià)關(guān)系下的多粒度粗糙集粒度約簡，對于非等價(jià)關(guān)系的尚無研究，本文研究一種非等價(jià)關(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上的一個(gè)等價(jià)關(guān)系，由這個(gè)等價(jià)關(guān)系可以導(dǎo)出U上的一個(gè)劃分，記為U/IND(A),?x∈U,那么x的等價(jià)類可記為[x]A，[x]A={y∈U|(x,y)∈IND(A)}。
定義3設(shè)(U,AT,V,F)為一個(gè)信息系統(tǒng)，對?X?U,A?AT,定義X關(guān)于屬性A的下、上近似[2]，分別記為:
U/IND(A)={[x]A|x∈U},
也被稱為一個(gè)粒結(jié)構(gòu)。
1.2 覆蓋粗糙集
定義4設(shè)U為論域,C={c1,c2,…,cn}是論域U上的一個(gè)覆蓋。對?x∈U,x在覆蓋近似空間
1.3 多粒度覆蓋粗糙集
定義6設(shè)U為論域,C1,C2,…,Ck為論域上的一族覆蓋。對?X?U,則X的多粒度覆蓋粗糙集定義[11]如下:
命題1設(shè)U為論域,C1,C2,…,Ck為論域上的一族覆蓋[11]，對?X?U,則有：
命題1說明了多粒度覆蓋粗糙集的下近似是所有單粒度覆蓋下近似的并，也就是說只要其中一個(gè)粒度存在Cij∈MdCi(x),使得Cij?X成立，那么x就屬于X的下近似；而上近似就是所有單粒度覆蓋上近似的交。
2可調(diào)整多粒度覆蓋粗糙集模型
由定義6知,覆蓋近似空間中一個(gè)對象最小描述的多粒度覆蓋粗糙集(樂觀多粒度覆蓋粗糙集)的下近似僅要求在m個(gè)粒結(jié)構(gòu)下只要有一個(gè)粒結(jié)構(gòu)中存在Cij∈MdCi(x),使得Cij?X成立,x就屬于X的下近似，這個(gè)條件太過于寬松。本文則在m個(gè)粒結(jié)構(gòu)下只要有一定數(shù)目的粒結(jié)構(gòu)中存在知識粒[x]Pi，使得[x]Pi?X，就認(rèn)為x屬于X的下近似。并且用參數(shù)α來控制滿足條件的粒結(jié)構(gòu)的個(gè)數(shù)，于是稱此為可調(diào)整多粒度覆蓋粗糙集。這樣就能夠解決對象最小描述誘導(dǎo)的多粒度覆蓋粗糙集下近似過松的問題。
由于在覆蓋決策信息系統(tǒng)中，每個(gè)屬性都可以產(chǎn)生一個(gè)覆蓋，即每個(gè)屬性都可以產(chǎn)生一個(gè)粒度，所以本文研究的可調(diào)整多粒度覆蓋粗糙集中的覆蓋是屬性產(chǎn)生的覆蓋。
2.1 可調(diào)整多粒度粗糙集模型的定義
定義7設(shè)U是有限論域，C是U的一個(gè)子集族，如果C中的子集都是非空的，且∪C=U，則稱C是U的一個(gè)覆蓋。若C={C1,C2,…,Cm}中的每個(gè)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的一個(gè)覆蓋，稱其為由Δ誘導(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∪u0kwia0,V,F)是覆蓋決策信息系統(tǒng),P1,P2,…,Pm?AT,P={P1,P2,…,Pm}, 0≤α≤1,D=Coiemyqy={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∪msea0aq,V,F)是覆蓋決策信息系統(tǒng)，其中a∈Pi?AT,D=Cgc0000k={D1,D2,D3,…,Dn},則粒度Pt在P下重要性為：
由定義可知sigPt(D)大于或等于零。當(dāng)sigPt(D)=0時(shí)，表示約去粒度Pt后，決策類D的下近似分布不發(fā)生變化，則Pt是關(guān)于決策類D下近似不重要的。當(dāng)sigPt(D)>0時(shí)，表示約去粒度Pt后決策類D的下近似分布發(fā)生變化，則Pt是關(guān)于決策類D下近似重要的。
約簡算法：
輸入：覆蓋決策信息系統(tǒng)(U,AT∪ew0eims,V,F),P1,P2,…,Pm?AT,Pi∩Pj=Φ(i≠j,i,j=1,2,…,m)，其中P={P1,P2,…,Pm};
輸出：該覆蓋信息系統(tǒng)的約簡；
Step 1: 對每一個(gè)Pi∈P，計(jì)算其產(chǎn)生的誘導(dǎo)覆蓋C(Pi)以及C(D);
Step 3: 對每一個(gè)Pi∈P，計(jì)算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)為最大值時(shí)的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每個(gè)屬性都可以產(chǎn)生一個(gè)覆蓋，其中將條件屬性集分成3個(gè)粒度，P1={P,M},P2={S,MS},P3={FS,L},根據(jù)前面的定義和定理，對表1進(jìn)行多粒度的粒約簡。
表1 覆蓋決策信息系統(tǒng)
每個(gè)屬性產(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}}。
兩個(gè)屬性誘導(dǎo)的覆蓋：
利用約簡算法計(jì)算各粒度的重要性：
粒度P1的重要性：
sigP1(D)=0。
粒度P2的重要性：
粒度P3的重要性：
4結(jié)語
本文提出了可調(diào)整多粒度覆蓋粗糙集模型，對多粒度覆蓋粗糙集模型進(jìn)行了推廣。同時(shí)定義了粒度重要性，提出了粒度約簡算法。用粒度相對于粒度集重要性找出重要的粒度，對粒度進(jìn)行約簡。通過實(shí)例對文中的算法進(jìn)行了驗(yàn)證，結(jié)果表明粒度約簡方法的有效性、合理性。
參考文獻(xiàn)：
[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é)報(bào):2012, 28(5): 10-13.
[12]李氣芳,李進(jìn)金,林國平.多粒度覆蓋信息系統(tǒng)的屬性約簡方法比較[J]. 計(jì)算機(jī)工程與應(yīng)用,2013, 49(10):121-124.
[13]桑妍麗, 錢宇華.一種悲觀多粒度粗糙集中的粒度約簡算法[J]. 模式識別與人工智能,2012, 25(3):361-366.
[14]孟慧麗, 馬媛媛, 徐久成.基于信息量的悲觀多粒度粗糙集粒度約簡[J]. 南京大學(xué)學(xué)報(bào):自然科學(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é)報(bào):自然科學(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
文獻(xiàn)標(biāo)識碼:A
文章編號：1001-7445(2015)06-1603-08
doi:10.13624/j.cnki.issn.1001-7445.2015.1603
通訊作者：呂躍進(jìn)(1958—)，男，廣東龍川人，廣西大學(xué)教授; E-mail:lvyjin@126.com。
基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(71361002)；廣西自然科學(xué)基金資助項(xiàng)目(2013GXNSFAA019016)
收稿日期：2015-09-21；
修訂日期：2015-10-30
