汪小燕, 申元霞

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

?

基于粒度矩陣的程度多粒度粗糙集粒度約簡(jiǎn)

汪小燕, 申元霞

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

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

程度多粒度粗糙集; 粒度矩陣; 核粒度; 粒度約簡(jiǎn)

0 引 言

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

1 相關(guān)概念

Pawlak粗糙集計(jì)算下近似要求集合間必須是完全包含關(guān)系,不考慮一定程度上的“包含”,當(dāng)集合間沒(méi)有完全包含關(guān)系,卻具有對(duì)分類重要的重疊信息時(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)用多粒度知識(shí),文獻(xiàn)[16] 分別從樂(lè)觀和悲觀方面提出兩種程度多粒度粗糙集。

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

(3)

(4)

|[x]Am∩X|≤k}

(5)

(6)

2 粒度矩陣

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

k∧[x]A∩X≠φ}

(7)

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

φ}

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

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

證畢

定義 7 設(shè)S=是一個(gè)信息系統(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,對(duì)?Y∈U/D,若?Y∈U/D列不存在只包含粒度集合A-{a}中所有粒度的元素,則在程度悲觀多粒度粗糙集中粒度a在粒度集合A中是不必要的,否則稱粒度a在粒度集合A中是必要的。

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

證畢

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

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

證畢

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

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

證畢

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

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

證畢

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

3 粒度約簡(jiǎn)

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

證畢

程度樂(lè)觀多粒度粗糙集的粒度約簡(jiǎn)算法步驟描述如下。

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

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

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

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

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

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

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

步驟 6 輸出粒度約簡(jiǎn)集red。

在程度樂(lè)觀多粒度粗糙集粒度約簡(jiǎn)算法中,計(jì)算各個(gè)粒度對(duì)論域劃分的時(shí)間復(fù)雜度為O(m|U|2),建立粒度矩陣的時(shí)間復(fù)雜度為O(mn|U|),在最壞情況下利用粒度矩陣獲得粒度約簡(jiǎn)的時(shí)間復(fù)雜度為O(mn|U|)。在決策信息系統(tǒng)中,一般對(duì)象的個(gè)數(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≠?,而對(duì)?red′?red,存在red′-mij=?,則集合red為程度悲觀多粒度粗糙集的下近似分布粒度約簡(jiǎn)。

證畢

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

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

輸出 決策信息系統(tǒng)的一個(gè)程度悲觀多粒度粗糙集的粒度約簡(jiǎn)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 輸出粒度約簡(jiǎn)集red。

在程度悲觀多粒度粗糙集粒度約簡(jiǎn)算法中,計(jì)算每個(gè)粒度劃分論域的時(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=,其中對(duì)象集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ì)算程度樂(lè)觀多粒度粗糙集粒度約簡(jiǎn)

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

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

5 結(jié) 論

本文針對(duì)程度多粒度粗糙集,定義了粒度矩陣,圍繞粒度矩陣,研究了程度多粒度粗糙集的相關(guān)理論。粒度矩陣可以方便計(jì)算程度樂(lè)(悲)觀多粒度粗糙集的上、下近似。給出程度樂(lè)觀多粒度粗糙集核粒度定義,提出了基于粒度矩陣的程度多粒度粗糙集粒度約簡(jiǎn)算法。在提取核粒度(或必要粒度)的基礎(chǔ)上,可快速計(jì)算出程度樂(lè)(悲)觀多粒度粗糙集的下近似約簡(jiǎn)。下一步的研究工作是對(duì)粒度約簡(jiǎn)后的信息系統(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. (孫文鑫,卓春英,王國(guó)棟,等. 序信息系統(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. (桑妍麗,錢宇華.一種悲觀多粒度粗糙集中的粒度約簡(jiǎn)算法[J].模式識(shí)別與人工智能, 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. (孟慧麗,馬媛媛,徐久成.基于信息量的悲觀多粒度粗糙集粒度約簡(jiǎn)[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].模式識(shí)別與人工智能,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。

國(guó)家青年科學(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