Four matroidal structures of covering and their relationships with rough sets

Covering is a common form of data representation, and covering-based rough sets serve as an efficient technique to process this type of data. However, many important problems such as covering reduction in covering-based rough sets are NP-hard so that most algorithms to solve them are greedy. Matroids provide well-established platforms for greedy algorithm foundation and implementation. Therefore, it is necessary to integrate covering-based rough set with matroid. In this paper, we propose four matroidal structures of coverings and establish their relationships with rough sets. First, four different viewpoints are presented to construct these four matroidal structures of coverings, including 1-rank matroids, bigraphs, upper approximation numbers and transversals. The respective advantages of these four matroidal structures to rough sets are explored. Second, the connections among these four matroidal structures are studied. It is interesting to find that they coincide with each other. Third, a converse view is provided to induce a covering by a matroid. We study the relationship between this induction and the one from a covering to a matroid. Finally, some important concepts of covering-based rough sets, such as approximation operators, are equivalently formulated by these matroidal structures. These interesting results demonstrate the potential to combine covering-based rough sets with matroids.     

A rough set approach to the characterization of transversal matroids

Rough sets are efficient for data pre-processing during data mining. However, some important problems such as attribute reduction in rough sets are NP-hard and the algorithms required to solve them are mostly greedy ones. The transversal matroid is an important part of matroid theory, which provides well-established platforms for greedy algorithms. In this study, we investigate transversal matroids using the rough set approach. First, we construct a covering induced by a family of subsets and we propose the approximation operators and upper approximation number based on this covering. We present a sufficient condition under which a subset is a partial transversal, and also a necessary condition. Furthermore, we characterize the transversal matroid with the covering-based approximation operator and construct some types of circuits. Second, we explore the relationships between closure operators in transversal matroids and upper approximation operators based on the covering induced by a family of subsets. Finally, we study two types of axiomatic characterizations of the covering approximation operators based on the set theory and matroid theory, respectively. These results provide more methods for investigating the combination of transversal matroids with rough sets.     

Matroidal approaches to rough sets via closure operators

This paper studies rough sets from the operator-oriented view by matroidal approaches. We firstly investigate some kinds of closure operators and conclude that the Pawlak upper approximation operator is just a topological and matroidal closure operator. Then we characterize the Pawlak upper approximation operator in terms of the closure operator in Pawlak matroids, which are first defined in this paper, and are generalized to fundamental matroids when partitions are generalized to coverings. A new covering-based rough set model is then proposed based on fundamental matroids and properties of this model are studied. Lastly, we refer to the abstract approximation space, whose original definition is modified to get a one-to-one correspondence between closure systems (operators) and concrete models of abstract approximation spaces. We finally examine the relations of four kinds of abstract approximation spaces, which correspond exactly to the relations of closure systems.     

On some types of covering rough sets from topological points of view

The concept of coverings is one of the fundamental concepts in topological spaces and plays a big part in the study of topological problems. This motivates the research of covering rough sets from topological points of view. From topological points of view, we can get a good insight into the essence of covering rough sets and make our discussions concise and profound. In this paper, we first construct a type of topology called the topology induced by the covering on a covering approximation space. This notion is indeed in the core of this paper. Then we use it to define the concepts of neighborhoods, closures, connected spaces, and components. Drawing on these concepts, we define several pairs of approximation operators. We not only investigate the relationships among them, but also give clear explanations of the concepts discussed in this paper. For a given covering approximation space, we can use the topology induced by the covering to investigate the topological properties of the space such as separation, connectedness, etc. Finally, a diagram is presented to show that the collection of all the lower and upper approximations considered in this paper constructs a lattice in terms of the inclusion relation ⊆.     

Topological approximations of multisets

Rough set theory is a powerful mathematical tool for dealing with inexact, uncertain or vague information. The core concept of rough set theory are information systems and approximation operators of approximation spaces. In this paper, we define and investigate three types of lower and upper multiset approximations of any multiset. These types based on the multiset base of multiset topology induced by a multiset relation. Moreover, the relationships between generalized rough msets and mset topologies are given. In addition, an illustrative example is given to illustrate the relationships between different types of generalized definitions of rough multiset approximations.     

On some types of neighborhood-related covering rough sets

Covering rough sets are natural extensions of the classical rough sets by relaxing the partitions to coverings. Recently, the concept of neighborhood has been applied to define different types of covering rough sets. In this paper, by introducing a new notion of complementary neighborhood, we consider some types of neighborhood-related covering rough sets, two of which are firstly defined. We first show some basic properties of the complementary neighborhood. We then explore the relationships between the considered covering rough sets and investigate the properties of them. It is interesting that the set of all the lower and upper approximations belonging to the considered types of covering rough sets, equipped with the binary relation of inclusion ?, constructs a lattice. Finally, we also discuss the topological importance of the complementary neighborhood and investigate the topological properties of the lower and upper approximation operators.     

Matroids on convex geometries (cg-matroids)

We consider matroidal structures on convex geometries, which we call cg-matroids. The concept of a cg-matroid is closely related to but different from that of a supermatroid introduced by Dunstan, Ingleton, and Welsh in 1972. Distributive supermatroids or poset matroids are supermatroids defined on distributive lattices or sets of order ideals of posets. The class of cg-matroids includes distributive supermatroids (or poset matroids). We also introduce the concept of a strict cg-matroid, which turns out to be exactly a cg-matroid that is also a supermatroid. We show characterizations of cg-matroids and strict cg-matroids by means of the exchange property for bases and the augmentation property for independent sets. We also examine submodularity structures of strict cg-matroids.     

模糊粗糙近似算子公理集的独立性

用双论域上的模糊关系定义了广义模糊粗糙近似算子,并讨论了近似算子的性质。用公理刻画了模糊集合值算子,各种公理化的近似算子可以保证找到相应的二元模糊关系,使得由模糊关系通过构造性方法定义的模糊粗糙近似算子恰好就是用公理定义的近似算子。讨论了刻画各种特殊近似算子的公理集的独立性,从而给出各种特殊模糊关系所对应的模糊粗糙近似算子的最小公理集。     

基于k阶二元关系的直觉模糊粗糙集

利用k阶二元关系定义直觉模糊粗糙集,讨论了分别为串行、自反、对称、传递关系时所对应的上、下近似算子的性质。在有限论域U中,研究了任一自反二元关系所诱导的直觉模糊拓扑空间中直觉模糊闭包、内部算子与相对应的上、下近似算子的关系。