兩類廣義粗糙集的擬陣結構

徐國曄 王兆浩

摘要：基于鄰域粗糙集模型和覆蓋粗糙集模型，分別構造了兩類擬陣結構，即鄰域上近似數誘導的擬陣和覆蓋上近似數誘導的擬陣。一方面，通過廣義粗糙集定義了兩類上近似數，并證明了它們滿足擬陣理論中的秩公理，從而由秩函數的觀點出發得到了兩類擬陣； 另一方面，利用粗糙集方法研究了這兩類擬陣的獨立集、極小圈、閉包、閉集等的表達形式，說明了粗糙集中的上近似算子與擬陣中的閉包算子的關系，進一步通過探討覆蓋和擬陣的關系，得到了覆蓋中的元素及其任意并是由覆蓋上近似數誘導的擬陣的閉集。

關鍵詞：粗糙集；擬陣；覆蓋；鄰域；上近似數

中圖分類號：TP18 文獻標志碼：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提出來的，主要解決信息系統中的粒度問題，該理論是建立在等價關系或者劃分上的，核心概念是上下近似算子。目前該理論已被廣泛應用于屬性約簡[1]、規則提取、特征選擇等領域。但由于等價關系太過嚴格，一些學者對粗糙集進行了推廣[2]。其中，基于鄰域的粗糙集和基于覆蓋的粗糙集就是經典粗糙集的推廣形式，這些廣義粗糙集由于更具有一般性，因此近年來受到研究者的廣泛關注。

將其他理論，如模糊集、拓撲學、格論等，融入到廣義粗糙集中，是粗糙集進行推廣研究的一個重要方面。其中，研究粗糙集理論與擬陣理論的結合，既有重大的理論意義，又有深遠的現實意義。擬陣是一種應用型極強的代數結構，它已廣泛應用于整數規劃、組合優化、邏輯電路等領域。擬陣具有完備的理論體系和廣闊的應用平臺。建立擬陣和廣義粗糙集的聯系，有利于充分利用擬陣的理論體系和應用平臺來發展粗糙集，這對于進一步發展粗糙集是有深遠意義的。

擬陣可以由它的獨立集、基、極小圈、秩函數、閉包算子或閉集等唯一地確定。文獻[3-7]分別利用擬陣的獨立集公理[3]、基公理[4]、閉包公理[5-6]和閉集公理[7]研究了覆蓋粗糙集或鄰域粗糙集的擬陣結構。本文從擬陣的秩函數出發，構造了兩類擬陣結構，在廣義粗糙集理論中引入了擬陣。首先基于鄰域粗糙集和覆蓋粗糙集定義了上近似數，通過研究上近似數的性質，發現其滿足擬陣理論中秩公理的三個條件，進而由其作為秩函數誘導兩類擬陣結構； 其次討論了擬陣中獨立集、極小圈、閉包、閉集等特征； 最后研究了這兩類擬陣結構的一些其他性質，進一步揭示了覆蓋與擬陣的關系，即覆蓋中的元素及其任意并都是擬陣的閉集。

1 基本概念

1.1 粗糙集

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

4 結語

本文建立了廣義粗糙集和擬陣之間的關系，構造了覆蓋粗糙集和鄰域粗糙集下的兩類擬陣結構，并利用粗糙集的方法研究了這兩類擬陣的特性。具體來說，通過定義上近似數，分別給出了由鄰域上近似數和覆蓋上近似數誘導的擬陣，得到了這兩類擬陣的獨立集、極小圈、閉包、閉集等表達形式。討論了粗糙集中上近似算子與擬陣中閉包算子的關系，并研究了覆蓋和擬陣的關系。這些結果為進一步豐富粗糙集的理論和應用奠定了基礎。

參考文獻：

[1]李永華， 蔣蕓， 王小菊. 一種基于Rough 集的屬性約簡的改進算法[J]. 計算機應用， 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]馬希驁 ， 王國胤， 張清華， 等. 基于改進的完備容差關系的擴充粗糙集模型[J]. 計算機應用， 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]蘇禮潤， 林姿瓊， 祝峰. 一種覆蓋粗糙集的擬陣結構[J]. 南京大學學報（自然科學版）， 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]李清銀， 祝峰. 基于鄰域的覆蓋粗糙集的上近似擬陣結構[J]. 山東大學學報（理學版）， 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]林姿瓊， 黃愛萍. 覆蓋的兩類擬陣結構[J]. 小型微型計算機系統， 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]. 模式識別與人工智能， 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]劉慧， 祝峰. 任意關系下粗糙集的擬陣結構[J]. 小型微型計算機系統， 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.