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

汪小燕, 申元霞

(安徽工業大學計算機科學與技術學院, 安徽 馬鞍山 243032)

?

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

汪小燕, 申元霞

(安徽工業大學計算機科學與技術學院, 安徽 馬鞍山 243032)

多粒度是粗糙集理論中的一種有效的數據處理方法,粒度約簡是獲取信息系統簡潔規則的前提。研究了程度樂(悲)觀多粒度粗糙集粒度約簡理論,改進了程度粗糙集的下近似定義,提出了程度多粒度粗糙集的粒度矩陣。基于粒度矩陣,研究了程度多粒度粗糙集下近似計算理論和粒度的必要性,提出程度樂觀多粒度粗糙集核粒度的定義。針對程度樂(悲)觀多粒度粗糙集,提出基于粒度矩陣的粒度約簡方法。最后利用實例分析驗證了所提粒度約簡方法的正確性。

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

0 引 言

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

1 相關概念

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

定義 1[15]設信息系統S,屬性子集A1,A2,…,Am?AT,k為非負常數,?X?U,X關于A,依據程度k的下、上近似分別定義為

(1)

(2)

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

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

(3)

(4)

|[x]Am∩X|≤k}

(5)

(6)

2 粒度矩陣

定義 4 設信息系統S=對于?X?U,A?AT,k為非負常數,X的程度粗糙集下近似為

k∧[x]A∩X≠φ}

(7)

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

φ}

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

證明 由定義1,定義4和集合的相對補集、絕對補運算可得證。

證畢

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

(8)

粒度矩陣包含|U|行, |U/D|列, |U|表示信息系統中實例數, |U/D|表示決策屬性類數,粒度矩陣中的非空元素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中所有粒度的元素,同時也包含粒度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所對應的元素只包含一個唯一粒度Ai∈A,則Ai為程度樂觀多粒度粗糙集的核粒度。

3 粒度約簡

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

證畢

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

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

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

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

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

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

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

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

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

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

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

證畢

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

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

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

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

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

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

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

步驟 5 如果T=?,則轉步驟7；否則,轉步驟6。

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

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

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

4 實例分析

例 1 設決策系統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) 計算程度樂觀多粒度粗糙集粒度約簡

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

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

5 結 論

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

[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.(馬睿,劉文奇. 基于集值信息系統的多粒度粗糙集[J].系統工程與電子技術, 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. (孫文鑫,卓春英,王國棟,等. 序信息系統的一般多粒度粗糙集[J].計算機科學與探索, 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].南京大學學報(自然科學版), 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.(吳志遠, 鐘培華, 胡建根.程度多粒度粗糙集[J].模糊系統與數學, 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;網絡優先出版日期:2016-10-22。

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

TP 18

A

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

汪小燕(1974-),女,副教授,碩士,主要研究方向為數據挖掘、粗糙集理論。

E-mail: wxyzjx@126.com

申元霞(1979-),女,副教授,博士,主要研究方向為智能計算、數據挖掘。

E-mail: yuanxiashen@163.com

網絡優先出版地址:http:∥www.cnki.net/kcms/detail/11.2422.TN.20161022.2349.002.html