Closed-set lattice of regular sets based on a serial and transitive relation through matroids
- PDF / 387,931 Bytes
- 7 Pages / 595.276 x 790.866 pts Page_size
- 56 Downloads / 197 Views
ORIGINAL ARTICLE
Closed-set lattice of regular sets based on a serial and transitive relation through matroids Qingyin Li • William Zhu
Received: 13 January 2013 / Accepted: 15 May 2013 Ó Springer-Verlag Berlin Heidelberg 2013
Abstract Rough sets are efficient for data pre-processing in data mining. Matroids are based on linear algebra and graph theory, and have a variety of applications in many fields. Both rough sets and matroids are closely related to lattices. For a serial and transitive relation on a universe, the collection of all the regular sets of the generalized rough set is a lattice. In this paper, we use the lattice to construct a matroid and then study relationships between the lattice and the closed-set lattice of the matroid. First, the collection of all the regular sets based on a serial and transitive relation is proved to be a semimodular lattice. Then, a matroid is constructed through the height function of the semimodular lattice. Finally, we propose an approach to obtain all the closed sets of the matroid from the semimodular lattice. Borrowing from matroids, results show that lattice theory provides an interesting view to investigate rough sets. Keywords Rough set Regular set Semimodular lattice Height function Matroid Independent set Rank function Closed-set lattice
1 Introduction Rough set theory was introduced by Pawlak [19] in 1982. It is a new mathematical tool to handle inexact, uncertain or vague knowledge and has been successfully applied to many fields such as machine learning, pattern recognition and data mining [6, 7, 13, 17, 20]. In order to meet various Q. Li W. Zhu (&) Lab of Granular Computing, Minnan Normal University, Zhangzhou 363000, China e-mail: [email protected]
practical applications, rough set theory has been connected with other theories, such as fuzzy set theory [18, 22], boolean algebra [21, 23], topology [15, 26, 30], lattice theory [2–5, 9, 10] and so on. Matroid theory also has been used to study rough set theory in recent years [27, 31]. Matroid theory [14] proposed by Whitney is a generalization of linear algebra, graph theory, transcendence theory and semimodular lattice theory. Matroids have been applied to a number of fields, such as combinatorial optimization [16], algorithm design [8], information coding [24] and so on. Both rough sets and matroids are closely linked to lattices. The fixed points of the lower approximation of the upper approximation of generalized rough sets based on relations are regular sets. For a serial and transitive relation, the collection of all the regular sets based on the relation is a lattice. In this paper, a matroidal structure is constructed by the lattice, and then relationships between the lattice and the closed-set lattice of the matroid are studied. In fact, the collection of all the regular sets based on a serial and transitive is a semimodular lattice. We define a family of subsets by the height function of the semimodular lattice, and then prove that this family satisfies the independent se
Data Loading...
