基于粒度矩陣的程度多粒度粗糙集粒度約簡

汪小燕, 申元霞

(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 安徽 馬鞍山 243032)

?

基于粒度矩陣的程度多粒度粗糙集粒度約簡

汪小燕, 申元霞

(安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 安徽 馬鞍山 243032)

多粒度是粗糙集理論中的一種有效的數(shù)據(jù)處理方法,粒度約簡是獲取信息系統(tǒng)簡潔規(guī)則的前提。研究了程度樂(悲)觀多粒度粗糙集粒度約簡理論,改進(jìn)了程度粗糙集的下近似定義,提出了程度多粒度粗糙集的粒度矩陣?；诹６染仃?研究了程度多粒度粗糙集下近似計(jì)算理論和粒度的必要性,提出程度樂觀多粒度粗糙集核粒度的定義。針對程度樂(悲)觀多粒度粗糙集,提出基于粒度矩陣的粒度約簡方法。最后利用實(shí)例分析驗(yàn)證了所提粒度約簡方法的正確性。

程度多粒度粗糙集; 粒度矩陣; 核粒度; 粒度約簡

0 引 言

Pawlak粗糙集是從整體上對所有條件屬性集合或決策屬性集合,依據(jù)等價(jià)關(guān)系,將論域劃分形成條件屬性類或決策屬性類。文獻(xiàn)[1-5]分析研究了Pawlak粗糙集整體劃分構(gòu)成單個粒度空間的不足,提出了多粒度粗糙集模型。根據(jù)下近似條件寬松與嚴(yán)格,定義了樂(悲)觀多粒度粗糙集模型。多粒度粗糙集將條件屬性劃分成多個粒度,每個粒度分別對論域劃分,形成多個粒度空間。應(yīng)用到實(shí)際決策問題時(shí),依據(jù)多個?？臻g獲得的知識對比Pawlak粗糙集的單一知識更加合理。一些學(xué)者在集值信息系統(tǒng)[6]、序信息系統(tǒng)[7]、不完備信息系統(tǒng)[8]、鄰域關(guān)系[9]、模糊關(guān)系[10]等方面對多粒度粗糙集做出了不同角度的擴(kuò)展。多粒度粗糙集中的粒度約簡是在不影響信息系統(tǒng)決策前提下,刪除對獲取知識沒有意義的粒度。粒度約簡對獲取簡潔、有效的決策規(guī)則具有重要意義。因此,一些學(xué)者深入研究了多粒度粗糙集中的粒度約簡,提出不同的方法。針對悲觀多粒度粗糙集,文獻(xiàn)[11-13]分別提出了下近似分布約簡、基于信息量的下近似分布約簡方法和基于重要度的上(下)近似分布約簡方法。文獻(xiàn)[14]提出了可變多粒度粗糙集粒度約簡方法。目前的多粒度粗糙集的粒度約簡主要是基于悲觀多粒度粗糙集,利用粒度重要性進(jìn)行約簡的。本文利用程度多粒度粗糙集模型,提出程度多粒度粗糙集粒度矩陣,結(jié)合粒度矩陣提出一種簡單有效的粒度約簡方法。

1 相關(guān)概念

Pawlak粗糙集計(jì)算下近似要求集合間必須是完全包含關(guān)系,不考慮一定程度上的“包含”,當(dāng)集合間沒有完全包含關(guān)系,卻具有對分類重要的重疊信息時(shí),應(yīng)當(dāng)考慮一定程度的包含。在這種背景下,文獻(xiàn)[15]提出了程度粗糙集。

定義 1[15]設(shè)信息系統(tǒng)S,屬性子集A1,A2,…,Am?AT,k為非負(fù)常數(shù),?X?U,X關(guān)于A,依據(jù)程度k的下、上近似分別定義為

(1)

(2)

在程度粗糙集中應(yīng)用多粒度知識,文獻(xiàn)[16] 分別從樂觀和悲觀方面提出兩種程度多粒度粗糙集。

|[x]Am|-|[x]Am∩X|≤k}

(3)

(4)

|[x]Am∩X|≤k}

(5)

(6)

2 粒度矩陣

定義 4 設(shè)信息系統(tǒng)S=對于?X?U,A?AT,k為非負(fù)常數(shù),X的程度粗糙集下近似為

k∧[x]A∩X≠φ}

(7)

定理 1 設(shè)信息系統(tǒng)S=,對于?X?U,A?AT,k為非負(fù)常數(shù),X的程度粗糙集下近似和上近似分別為

φ}

式中,[x]A-X表示集合X相對于集合[x]A的補(bǔ)集。

證明 由定義1,定義4和集合的相對補(bǔ)集、絕對補(bǔ)運(yùn)算可得證。

證畢

定義 7 設(shè)S=是一個信息系統(tǒng),其中A1,A2,…,Am?AT,D為決策屬性,k為非負(fù)常數(shù),A={A1,A2,…,Am},U/D={Y1,Y2,…,Yn},則程度多粒度粗糙集粒度矩陣M={mij}定義為

(8)

粒度矩陣包含|U|行, |U/D|列, |U|表示信息系統(tǒng)中實(shí)例數(shù), |U/D|表示決策屬性類數(shù),粒度矩陣中的非空元素mij是滿足|[xi]B-Yj|≤k∧[xi]B∩Yj≠φ的條件屬性粒度B組成的集合。

定理 2 程度多粒度粗糙集粒度矩陣M={mij}中,A是所有條件屬性粒度集合,a∈A,對?Y∈U/D,若?Y∈U/D列不存在只包含粒度集合A-{a}中所有粒度的元素,則在程度悲觀多粒度粗糙集中粒度a在粒度集合A中是不必要的,否則稱粒度a在粒度集合A中是必要的。

證明 由定義5和推論4可證。

證畢

定理 3 程度多粒度粗糙集粒度矩陣M={mij}中,A是所有條件屬性粒度集合,B?A,a∈A-B,對?Y∈U/D,若?Y∈U/D列所有包含粒度集合B中所有粒度的元素,同時(shí)也包含粒度a,則在程度悲觀多粒度粗糙集中粒度a對粒度集合B是不必要的;否則,稱粒度a對粒度集合B是必要的。

證明 由定義6和推論5可證。

證畢

定理 4 程度多粒度粗糙集粒度矩陣M={mij}中,A是所有條件屬性粒度集合,a∈A,對?Y∈U/D,若?Y∈U/D列不存在只包含粒度a的元素,則在程度樂觀多粒度粗糙集中粒度a在粒度集合A中是不必要的;否則,稱粒度a在粒度集合A中是必要的。

證明 由定義5和推論9可證。

證畢

定理 5 程度多粒度粗糙集粒度矩陣M={mij}中,A是所有條件屬性粒度集合,B?A,a∈A-B,對?Y∈U/D,若?Y∈U/D列不存在包含粒度a且不包含粒度集合B中任意粒度的元素,則在程度樂觀多粒度粗糙集中粒度a對粒度集合B是不必要的,否則稱粒度a對粒度集合B是必要的。

證明 由定義6和推論10可證。

證畢

定義 8 程度多粒度粗糙集粒度矩陣M={mij}中,A是所有條件屬性粒度集合,若某個對象x∈U與某個決策類?Y∈U/D所對應(yīng)的元素只包含一個唯一粒度Ai∈A,則Ai為程度樂觀多粒度粗糙集的核粒度。

3 粒度約簡

定理 6 在粒度矩陣M中,A是所有條件屬性粒度集合,T={mij|mij為粒度矩陣中所有不為?的元素},若red?A,且?mij∈T,red∩mij≠?,而對?red′?red,存在red′∩mij=?,則集合red為程度樂觀多粒度粗糙集的下近似分布粒度約簡。

證畢

程度樂觀多粒度粗糙集的粒度約簡算法步驟描述如下。

輸入 決策信息系統(tǒng)S=,A1,A2,…,Am?AT為條件屬性粒度,A={A1,A2,…,Am},U/D={Y1,Y2,…,Yn}。

輸出 決策信息系統(tǒng)的一個程度樂觀多粒度粗糙集的粒度約簡red。

步驟 1 根據(jù)定義7建立粒度矩陣M={mij}。

步驟 2 將粒度矩陣中的核粒度加入到red中。

步驟 3 將粒度矩陣中的包含集合red中任意粒度的元素改為?。

步驟 4 若粒度矩陣中的所有元素都為?,則轉(zhuǎn)步驟6;否則轉(zhuǎn)步驟5。

步驟 5 將粒度矩陣中不為?的元素中選擇一粒度加入到集合red中,轉(zhuǎn)步驟3。

步驟 6 輸出粒度約簡集red。

在程度樂觀多粒度粗糙集粒度約簡算法中,計(jì)算各個粒度對論域劃分的時(shí)間復(fù)雜度為O(m|U|2),建立粒度矩陣的時(shí)間復(fù)雜度為O(mn|U|),在最壞情況下利用粒度矩陣獲得粒度約簡的時(shí)間復(fù)雜度為O(mn|U|)。在決策信息系統(tǒng)中,一般對象的個數(shù)大于決策屬性分類數(shù),所以該算法需要的時(shí)間復(fù)雜度為O(m|U|2)。粒度矩陣的空間復(fù)雜度為O(n|U|)。

定理 7 在粒度矩陣M中,A是所有條件屬性粒度集合,T={mij|mij?A且mij≠?},若red?A,且?mij∈T,red-mij≠?,而對?red′?red,存在red′-mij=?,則集合red為程度悲觀多粒度粗糙集的下近似分布粒度約簡。

證畢

針對程度悲觀多粒度粗糙集,給出基于粒度矩陣的粒度約簡算法步驟如下。

輸入 決策信息系統(tǒng)為S=,A1,A2,…,Am?AT為條件屬性粒度,A={A1,A2,…,Am},U/D={Y1,Y2,…,Yn},T=?。

輸出 決策信息系統(tǒng)的一個程度悲觀多粒度粗糙集的粒度約簡red。

步驟 1 根據(jù)定義7建立粒度矩陣M={mij}。

步驟 2 將粒度矩陣中的mij?A且mij≠?的元素加入到集合T中。

步驟 3 選擇必要粒度加入到集合red中。

步驟 4 將集合T中所有滿足red-mij≠?的元素刪除。

步驟 5 如果T=?,則轉(zhuǎn)步驟7；否則,轉(zhuǎn)步驟6。

步驟 6 在A-red中選擇一粒度加入到集合red中,轉(zhuǎn)步驟4。

步驟 7 輸出粒度約簡集red。

在程度悲觀多粒度粗糙集粒度約簡算法中,計(jì)算每個粒度劃分論域的時(shí)間復(fù)雜度為O(m|U|2),建立程度多粒度粗糙集粒度矩陣的時(shí)間復(fù)雜度為O(mn|U|),計(jì)算所有必要性粒度的時(shí)間復(fù)雜度為O(m2n|U|)。所以,該算法需要的時(shí)間復(fù)雜度為O(m|U|2+m2n|U|)。

4 實(shí)例分析

例 1 設(shè)決策系統(tǒng)S=,其中對象集U={x1,x2,…,x9},條件屬性為a1,a2,a3,a4,d為決策屬性,如表1所示。令條件屬性粒度集A={A1,A2,A3}={{a1,a2},{a2,a3},{a3,a4}},取k=1。U/IND(d)={D1,D2}={{x2,x4,x6,x8},{x1,x3,x5,x7,x9}}

建立程度多粒度粗糙集粒度矩陣如表2所示。

表1 決策信息表

表2 粒度矩陣表

(1) 計(jì)算程度樂觀多粒度粗糙集粒度約簡

核粒度為A2,將粒度矩陣中的包含A2的元素改為?后,只有m52={A1A3}≠?,所以最終獲得的粒度約簡為{A1,A2}或{A2,A3}。

(2) 計(jì)算程度悲觀多粒度粗糙集粒度約簡

5 結(jié) 論

本文針對程度多粒度粗糙集,定義了粒度矩陣,圍繞粒度矩陣,研究了程度多粒度粗糙集的相關(guān)理論。粒度矩陣可以方便計(jì)算程度樂(悲)觀多粒度粗糙集的上、下近似。給出程度樂觀多粒度粗糙集核粒度定義,提出了基于粒度矩陣的程度多粒度粗糙集粒度約簡算法。在提取核粒度(或必要粒度)的基礎(chǔ)上,可快速計(jì)算出程度樂(悲)觀多粒度粗糙集的下近似約簡。下一步的研究工作是對粒度約簡后的信息系統(tǒng)進(jìn)行規(guī)則提取研究。

[1] Qian Y H, Liang J Y. Rough set method based on multigranulations[C]∥Proc.ofthe5thIEEEInternationalConferenceonCognitiveInformatics, 2006:297-304.

[2] Qian Y H,Liang J Y,Wei W.Pessimistic rough decision[C]∥Proc.ofthe2ndInternationalWorkshoponRoughSetsTheory, 2010: 440-449.

[3] Qian Y H, Liang J Y,Yao Y Y, et al. MGRS: A multi-granulation rough set[J].InformationSciences, 2010,180(6): 949-970.

[4] Qian Y H, Liang J Y, Dang C Y. Incomplete multi-granulation rough set[J].IEEETrans.onSystems,Man,andCybernetics-PartA:SystemsandHumans, 2010, 40(2): 420-431.

[5] Qian Y H, Zhang H, Sang Y L, et al. Multigranulation decision-theoretic rough sets[J].InternationalJournalofApproximateReasoning, 2014, 55(1): 225-237.

[6] Ma R, Liu W Q. Multi-granulation rough set model based on set-valued information system[J].SystemsEngineeringandElectronics, 2014, 36(5): 920-925.(馬睿,劉文奇. 基于集值信息系統(tǒng)的多粒度粗糙集[J].系統(tǒng)工程與電子技術(shù), 2014, 36(5): 920-925.)

[7] Sun W X, Zhuo C Y, Wang G D, et al. Generalized multi-granulation rough set in ordered information system[J].JournalofFrontiersofComputerScienceandTechnology, 2015,9(3):376-384. (孫文鑫,卓春英,王國棟,等. 序信息系統(tǒng)的一般多粒度粗糙集[J].計(jì)算機(jī)科學(xué)與探索, 2015, 9(3): 376-384)

[8] Zhang M, Tang Z M, Xu W Y, et al. Incomplete variable multi-granulation rough sets decision[J].AppliedMathematics&InformationScience, 2014, 8(3):1159-1166.

[9] Lin G P, Qian Y H, Li J J. NMGRS: neighborhood-based multi-granulation rough sets[J].InternationalJournalofApproximateReasoning, 2012, 53(7): 1080-1093.

[10] Lin G P, Liang J Y, Qian Y H, et al. A fuzzy multi-granulation decision theoretic approach to multi-source fuzzy information systems[J].Knowledge-BasedSystems, 2016, 91(C): 102-113.

[11] Sang Y L, Qian Y H. A granular space reduction approach to pessimistic multi-granulation rough sets[J].PatternRecognitionandArtificialIntelligence, 2012, 25(3): 361-366. (桑妍麗,錢宇華.一種悲觀多粒度粗糙集中的粒度約簡算法[J].模式識別與人工智能, 2012, 25(3): 361-366)

[12] Meng H L, Ma Y Y, Xu J C. The granularity reduction of pessimistic multi-granulation rough set based on the information quantity[J].JournalofNanjingUniversity(NaturalSciences), 2015, 51(2): 343-348. (孟慧麗,馬媛媛,徐久成.基于信息量的悲觀多粒度粗糙集粒度約簡[J].南京大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,51(2):343-348)

[13] Qian Y H, Li S Y, Liang J Y, et al. Pessimistic rough set based decisions: a multi-granulation fusion strategy[J].InformationSciences, 2014, 264(6): 196-210.

[14] Zhang M, Tang Z M, Xu W Y, et al. Variable multi-granulation rough set model[J].PatternRecognitionandArtificialIntelligence, 2012, 25(4): 709-720.(張明,唐振民,徐維艷,等.可變多粒度粗糙集模型[J].模式識別與人工智能,2012,25(4):709-720)

[15] Yao Y Y,Lin T Y. Generalization of rough sets using modal logics[J].IntelligentAutomation&SoftComputing, 1996, 2(2): 103-120.

[16] Wu Z Y, Zhong P H, Hu J G. The graded multi-granulation rough set[J].FuzzySystemsandMathematics, 2014, 28(3): 165-172.(吳志遠(yuǎn), 鐘培華, 胡建根.程度多粒度粗糙集[J].模糊系統(tǒng)與數(shù)學(xué), 2014, 28(3): 165-172.)

Granulation reduction of graded multi-granulation rough set based on granulation matrix

WANG Xiao-yan, SHEN Yuan-xia

(SchoolofComputerScience&Technology,AnhuiUniversityofTechnology,Ma’anshan243032,China)

Multi-granularity is an effective data processing method in rough set theory. Granularity reduction is the prerequisite for obtaining the concise rules of the information system. The granulation reduction of graded optimism (pessimism) multi-granulation rough set is researched and the lower approximation definition of graded rough set is improved. The granulation matrix of graded multi-granulation rough set is proposed. Based on the granulation matrix, the lower approximation calculation and necessity of granularity are studied in graded multi-granulation rough set. Then the core granulation definition on graded optimism multi-granulation rough set is given. The granulation reduction of graded optimism (pessimism) multi-granulation rough set is proposed based on granulation matrix. Finally, a numerical example is given to demonstrate the correctness of the proposed method for granularity reduction.

graded multi-granulation rough set; granulation matrix; core granulation; granulation reduction

2016-04-12;

2016-09-19;網(wǎng)絡(luò)優(yōu)先出版日期:2016-10-22。

國家青年科學(xué)基金(61300059)資助課題

TP 18

A

10.3969/j.issn.1001-506X.2016.12.31

汪小燕(1974-),女,副教授,碩士,主要研究方向?yàn)閿?shù)據(jù)挖掘、粗糙集理論。

E-mail: wxyzjx@126.com

申元霞(1979-),女,副教授,博士,主要研究方向?yàn)橹悄苡?jì)算、數(shù)據(jù)挖掘。

E-mail: yuanxiashen@163.com

網(wǎng)絡(luò)優(yōu)先出版地址:http:∥www.cnki.net/kcms/detail/11.2422.TN.20161022.2349.002.html