Closed-set lattice and modular matroid induced by covering-based rough sets
- PDF / 338,235 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 26 Downloads / 168 Views
ORIGINAL ARTICLE
Closed-set lattice and modular matroid induced by covering-based rough sets Lirun Su • William Zhu
Received: 30 June 2014 / Accepted: 12 November 2014 Ó Springer-Verlag Berlin Heidelberg 2014
Abstract Covering is a common form of data representation, and covering-based rough sets, a technique of granular computing, provide an effective tool to deal with this type of data. However, many important problems of covering-based rough sets, such as covering reduction, are NP-hard so that most algorithms to solve them are greedy ones. Matroid theory, based on linear algebra and graph theory, provides well-established platforms for greedy algorithms. Lattice has been widely used in diverse fields, especially algorithm design, which plays an important role in covering reduction. Therefore, it is necessary to integrate covering-based rough sets with matroid and lattice. In this paper, we construct three types of matroids through covering-based rough sets and investigate their modularity. Moreover, we investigate some characteristics of these types of closed-set lattices induced by these three types of matroids and the relationships among these closed-set lattices. First, based on covering-based rough sets, three families of sets are constructed and proved to satisfy independent set axiom of matroids. So three types of matroids are induced by covering-based rough sets in this way. Second, some characteristics of these matroids, such as rank function, closure operator and closed set, are presented. Moreover, we investigate the characteristics of these closed-set lattices induced by these three types of matroids, such as modular pair, modular element. Finally, the relationships among these closed-set lattices induced by these three types of matroids are investigated. Especially, we prove that these three types of matroids induced by covering-based rough sets are all modular matroids. L. Su W. Zhu (&) Lab of Granular Computing, Minnan Normal University, Zhangzhou 363000, China e-mail: [email protected]
Keywords Closed-set lattice Modular matroid Covering Rough sets Granular computing
1 Introduction Rough set theory was proposed by Pawlak [31] to deal with vagueness and granularity in information systems. It has been successfully applied to process control, economics, feature selection [11, 13], attribution reduction [9, 10], rule extraction [6, 33] and other fields [23, 38, 39]. The classical rough set theory is based on equivalence relations or partitions which impose restrictions and limitations on many applications and it has been extended to relationbased rough sets [14, 15, 40], covering-based rough sets [1, 20, 41–43]. In real world applications, covering is an important data structure and it is widely used to represent data sets. Covering-based rough sets are more general and complex than classical rough and are proposed to deal with this type of data [3, 18]. However, many problems in coveringbased rough sets are NP-hard and those algorithms to solve them are almost greedy ones [12,
Data Loading...
