兩類廣義粗糙集的擬陣結(jié)構(gòu)

徐國(guó)曄 王兆浩

摘要：基于鄰域粗糙集模型和覆蓋粗糙集模型，分別構(gòu)造了兩類擬陣結(jié)構(gòu)，即鄰域上近似數(shù)誘導(dǎo)的擬陣和覆蓋上近似數(shù)誘導(dǎo)的擬陣。一方面，通過廣義粗糙集定義了兩類上近似數(shù)，并證明了它們滿足擬陣?yán)碚撝械闹裙?，從而由秩函?shù)的觀點(diǎn)出發(fā)得到了兩類擬陣； 另一方面，利用粗糙集方法研究了這兩類擬陣的獨(dú)立集、極小圈、閉包、閉集等的表達(dá)形式，說明了粗糙集中的上近似算子與擬陣中的閉包算子的關(guān)系，進(jìn)一步通過探討覆蓋和擬陣的關(guān)系，得到了覆蓋中的元素及其任意并是由覆蓋上近似數(shù)誘導(dǎo)的擬陣的閉集。

關(guān)鍵詞：粗糙集；擬陣；覆蓋；鄰域；上近似數(shù)

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A

Abstract：Based on neighborhoodbased rough set model and coveringbased rough set model， two matroidal structures which were matroid induced by neighborhood upper approximation number and matroid induced by covering upper approximation number were constructed. On one hand， two types of upper approximation number were defined through generalized rough set， and they were proven to satisfy rank function axiom in matroid theory， thus two types of matroids were obtained from the viewpoint of the rank function. On the other hand， some properties， such as independent sets， circuits， closures， closed sets， were proposed through rough set approach. Moreover， the concentions between upper approximation operators and closure operators were investigated. Futhuremore， the relationship between the covering and the matroid was studied. Result shows that elements and any union of them in covering are the closed sets of matroid induced by covering upper approximation number.

Key words：rough set； matroid； covering； neighborhood； upper approximation number

0 引言

粗糙集是1982年由Pawlak提出來的，主要解決信息系統(tǒng)中的粒度問題，該理論是建立在等價(jià)關(guān)系或者劃分上的，核心概念是上下近似算子。目前該理論已被廣泛應(yīng)用于屬性約簡(jiǎn)[1]、規(guī)則提取、特征選擇等領(lǐng)域。但由于等價(jià)關(guān)系太過嚴(yán)格，一些學(xué)者對(duì)粗糙集進(jìn)行了推廣[2]。其中，基于鄰域的粗糙集和基于覆蓋的粗糙集就是經(jīng)典粗糙集的推廣形式，這些廣義粗糙集由于更具有一般性，因此近年來受到研究者的廣泛關(guān)注。

將其他理論，如模糊集、拓?fù)鋵W(xué)、格論等，融入到廣義粗糙集中，是粗糙集進(jìn)行推廣研究的一個(gè)重要方面。其中，研究粗糙集理論與擬陣?yán)碚摰慕Y(jié)合，既有重大的理論意義，又有深遠(yuǎn)的現(xiàn)實(shí)意義。擬陣是一種應(yīng)用型極強(qiáng)的代數(shù)結(jié)構(gòu)，它已廣泛應(yīng)用于整數(shù)規(guī)劃、組合優(yōu)化、邏輯電路等領(lǐng)域。擬陣具有完備的理論體系和廣闊的應(yīng)用平臺(tái)。建立擬陣和廣義粗糙集的聯(lián)系，有利于充分利用擬陣的理論體系和應(yīng)用平臺(tái)來發(fā)展粗糙集，這對(duì)于進(jìn)一步發(fā)展粗糙集是有深遠(yuǎn)意義的。

擬陣可以由它的獨(dú)立集、基、極小圈、秩函數(shù)、閉包算子或閉集等唯一地確定。文獻(xiàn)[3-7]分別利用擬陣的獨(dú)立集公理[3]、基公理[4]、閉包公理[5-6]和閉集公理[7]研究了覆蓋粗糙集或鄰域粗糙集的擬陣結(jié)構(gòu)。本文從擬陣的秩函數(shù)出發(fā)，構(gòu)造了兩類擬陣結(jié)構(gòu)，在廣義粗糙集理論中引入了擬陣。首先基于鄰域粗糙集和覆蓋粗糙集定義了上近似數(shù)，通過研究上近似數(shù)的性質(zhì)，發(fā)現(xiàn)其滿足擬陣?yán)碚撝兄裙淼娜齻€(gè)條件，進(jìn)而由其作為秩函數(shù)誘導(dǎo)兩類擬陣結(jié)構(gòu)； 其次討論了擬陣中獨(dú)立集、極小圈、閉包、閉集等特征； 最后研究了這兩類擬陣結(jié)構(gòu)的一些其他性質(zhì)，進(jìn)一步揭示了覆蓋與擬陣的關(guān)系，即覆蓋中的元素及其任意并都是擬陣的閉集。

1 基本概念

1.1 粗糙集

命題23和注4說明覆蓋中的元素及其任意并都是擬陣M（fTH）的閉集，然而反過來并不成立。因此很自然會(huì)考慮覆蓋滿足什么條件時(shí)，集合T={∪B|BC}滿足閉集公理，進(jìn)而由閉集出發(fā)考慮擬陣與粗糙集結(jié)合的問題。

4 結(jié)語

本文建立了廣義粗糙集和擬陣之間的關(guān)系，構(gòu)造了覆蓋粗糙集和鄰域粗糙集下的兩類擬陣結(jié)構(gòu)，并利用粗糙集的方法研究了這兩類擬陣的特性。具體來說，通過定義上近似數(shù)，分別給出了由鄰域上近似數(shù)和覆蓋上近似數(shù)誘導(dǎo)的擬陣，得到了這兩類擬陣的獨(dú)立集、極小圈、閉包、閉集等表達(dá)形式。討論了粗糙集中上近似算子與擬陣中閉包算子的關(guān)系，并研究了覆蓋和擬陣的關(guān)系。這些結(jié)果為進(jìn)一步豐富粗糙集的理論和應(yīng)用奠定了基礎(chǔ)。

參考文獻(xiàn)：

[1]李永華， 蔣蕓， 王小菊. 一種基于Rough 集的屬性約簡(jiǎn)的改進(jìn)算法[J]. 計(jì)算機(jī)應(yīng)用， 2008， 28（8）： 2000-2002.（LI Y H， JIANG Y， WANG X J. An improved algorithm for attribute reduction based on rough sets[J]. Journal of Computer Applications， 2008， 28（8）： 2000-2002.）

[2]馬希驁 ， 王國(guó)胤， 張清華， 等. 基于改進(jìn)的完備容差關(guān)系的擴(kuò)充粗糙集模型[J]. 計(jì)算機(jī)應(yīng)用， 2010， 30（7）： 1873-1877.（MA X A， WANG G Y， ZHANG Q H， et al. Extended rough set model based on improved complete tolerance relation[J]. Journal of Computer Applications， 2010， 30（7）： 1873-1877.）

[3]蘇禮潤(rùn)， 林姿瓊， 祝峰. 一種覆蓋粗糙集的擬陣結(jié)構(gòu)[J]. 南京大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2013， 49（5）： 561-566.（SU L R， LIN Z Q， ZHU F. A type of matroidal structure of covering based rough sets[J]. Journal of Nanjing University （Natural Sciences）， 2013， 49（5）： 561-566.）

[4]李清銀， 祝峰. 基于鄰域的覆蓋粗糙集的上近似擬陣結(jié)構(gòu)[J]. 山東大學(xué)學(xué)報(bào)（理學(xué)版）， 2014， 49（8）： 6-11.（LI Q Y， ZHU F. Matroidal structure of the upper approximation of covering based rough set defined by the neighborhood[J]. Journal of Shangdong University （Natural Science）， 2014， 49（8）： 6-11.）

[5]林姿瓊， 黃愛萍. 覆蓋的兩類擬陣結(jié)構(gòu)[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2014， 35（11）： 2519-2522.（LIN Z Q， HUANG A P. Two matroidal structures of coverings[J]. Journal of Chinese Computer Systems， 2014， 35（11）： 2519-2522.）

[6]李清銀， 林姿瓊， 祝峰. 覆蓋擬陣及其可圖性[J]. 模式識(shí)別與人工智能， 2014， 27（6）： 481-486.（LI Q Y， LIN Z Q， ZHU F. Covering matroid and its graphical representation[J]. Pattern Recognition and Aitificial Intelligence， 2014， 27（6）： 481-486.）

[7]劉慧， 祝峰. 任意關(guān)系下粗糙集的擬陣結(jié)構(gòu)[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2015， 36（8）： 1813-1816.（LIU H， ZHU F. Matroidal structure of the generalized rough set based on arbitrary relations[J]. Journal of Chinese Computer Systems， 2015， 36（8）： 1813-1816.）

[8]PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Sciences， 1982， 11（5）： 341-356.

[9]ZHU W. Relationship among basic concepts in coveringbased rough sets[J]. Information Sciences， 2009， 179（14）： 2478-2486.

[10]ZHU F， WANG F. Reduction and axiomization of covering generalized rough sets[J]. Information Sciences， 2003， 152（1）： 217-230.

[11]BONIKOWSKI Z， BRYNIARSKI E， WYBRANIECSKARDOWSKA U. Extensions and intentions in the rough set theory[J]. Information Sciences， 1998， 107（1/2/3/4）： 149-167.

[12]TSANG E， CHENG D， LEE J， et al. On the upper approximations of covering generalized rough sets[C]// Proceedings of the 2004 International Conference on Machine Learning and Cybernetics. Piscataway， NJ： IEEE， 2004， 7： 4200-4203.

[13]ZHU W. Relationship among basic concepts in coveringbased rough sets[J]. Information Sciences， 2009， 179（14）： 2478-2486.

[14]賴虹建.擬陣論[M].北京：高等教育出版社， 2001：7-33.（LAI H J. Matroid Theory[M]. Beijing： Higher Education Press， 2001： 7-33.）

[15]WANG S， ZHU Q， ZHU W， et al. Matroidal structure of rough sets and its characterization to attribute reduction[J]. Knowledgebased System， 2012， 36： 155-161.

[16]WANG S， WILLAM Z， MIN F. Characteristics of 2circuit matroids through rough sets[C]// Proceedings of the 2012 IEEE International Conference on Granular Computing. Piscataway， NJ： IEEE， 2012： 771-774.

[17]WANG J， ZHU W， WANG F， et al. Conditions for coverings to induce matroids[J]. International Journal of Machine Learning and Cybernetics， 2014， 5（6）： 947-954.