两类广义粗糙集的拟阵结构

徐国晔 王兆浩

摘要：基于邻域粗糙集模型和覆盖粗糙集模型，分别构造了两类拟阵结构，即邻域上近似数诱导的拟阵和覆盖上近似数诱导的拟阵。一方面，通过广义粗糙集定义了两类上近似数，并证明了它们满足拟阵理论中的秩公理，从而由秩函数的观点出发得到了两类拟阵； 另一方面，利用粗糙集方法研究了这两类拟阵的独立集、极小圈、闭包、闭集等的表达形式，说明了粗糙集中的上近似算子与拟阵中的闭包算子的关系，进一步通过探讨覆盖和拟阵的关系，得到了覆盖中的元素及其任意并是由覆盖上近似数诱导的拟阵的闭集。

关键词：粗糙集；拟阵；覆盖；邻域；上近似数

中图分类号：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.