Four Operators of Rough Sets Generalized to Matroids and a Matroidal Method for Attribute Reduction

Abstract

Rough sets provide a useful tool for data preprocessing during data mining. However, many algorithms related to some problems in rough sets, such as attribute reduction, are greedy ones. Matroids propose a good platform for greedy algorithms. Therefore, it is important to study the combination between rough sets and matroids. In this paper, we investigate rough sets and matroids through their operators, and provide a matroidal method for attribute reduction in information systems. Firstly, we generalize four operators of rough sets to four operators of matroids through the interior, closure, exterior and boundary axioms, respectively. Thus, there are four matroids induced by these four operators of rough sets. Then, we find that these four matroids are the same one, which implies the relationship about operators between rough sets and matroids. Secondly, a relationship about operations between matroids and rough sets is presented according to the induced matroid. Finally, the girth function of matroids is used to compute attribute reduction in information systems.

1. Introduction

Rough set theory was proposed by Pawlak [1,2] in 1982 as a mathematical tool to deal with various types of data in data mining. There are many practical problems have been solved by it, such as rule extraction [3,4], attribute reduction [5,6,7], feature selection [8,9,10] and knowledge discovery [11]. In Pawlak’s rough sets, the relationships of objects are equivalence relations. However, it is well known that this requirement is excessive in practice [12,13]. Hence, Pawlak’s rough sets have been extended by relations [14,15], coverings [16,17,18] and neighborhoods [6,19]. They have been combined with other theories including topology [20], lattice theory [21,22], graph theory [23,24] and fuzzy set theory [25,26].

However, many optimization issues related to rough sets, including attribute reduction, are NP-hard. Therefore, the algorithms to deal with them are often greedy ones [27]. Matroid theory [28,29,30] is a generalization of graph and linear algebra theories. It has been used in information coding [31] and cryptology [32]. Recently, the combination between rough sets and matroids has attracted many interesting research. For example, Zhu and Wang [33] established a matroidal structure through the upper approximation number and studied generalized rough sets with matroidal approaches. Liu and Zhu [34] established a parametric matroid through the lower approximation operator of rough sets. Li et al. [35,36] used matroidal approaches to investigate rough sets through closure operators. Su and Zhu [37] presented three types of matroidal structures of covering-based rough sets. Wang et al. [38] induced a matroid named 2-circuit matroid by equivalence relations, and equivalently formulated attribute reduction with matroidal approaches. Wang and Zhu used matrix approaches to study the 2-circuit matroid [39], and used contraction operation in matroids to study some relationships between a subset and the upper approximation of this subset in rough sets [40]. Unfortunately, all of these papers never study matroids and rough sets through the positive, negative and boundary operators of rough sets. Thus, it is necessary to further study rough sets and matroids by these operators in this paper. In addition, only Wang et al. [38] presented two equivalent descriptions of attribute reduction by closure operators and rank functions of matroids, respectively. We consider presenting a novel approach to attribute reduction through the girth function of matroids in this paper.

In this paper, we mainly use the positive operator, the negative operator and the boundary operator to study matroids and rough sets, and propose a method to compute attribute reduction in information systems through the girth function of matroids. Firstly, we generalize the positive (the lower approximation operator), upper approximation, negative and boundary operators of rough sets to the interior, closure, exterior and boundary operators of matroids respectively. Among them, the upper and lower approximation operators have been studied in [35]. Thus, there are four matroids induced by these four operators of rough sets. Then, the relationship between these four matroids is studied, which implies the relationship about operators between rough sets and matroids. In fact, these four matroids are the same one. Secondly, a relationship about the restriction operation both in matroids and rough sets is proposed. Finally, a matroidal approach is proposed to compute attribute reduction in information systems through the girth function of matroids, and an example about attribute reduction is solved. Using this matroidal approach, we can compute attribute reduction through their results “2” and “∞”.

The rest of this paper is organized as follows. Section 2 recalls some basic notions about rough sets, information systems and matroids. In Section 3, we generalize four operators of rough sets to four operators of matroids, respectively. In addition, we study the relationship between four matroids induced by these four operators of rough sets. Moreover, a relationship about operations between matroids and rough sets is presented. In Section 4, an equivalent formulation of attribute reduction through the girth function is presented. Based on the equivalent formulation, a novel method is proposed to compute attribute reduction in information systems. Finally, Section 5 concludes this paper and indicates further works.

2. Basic Definitions

In this section, we review some notions in Pawlak’s rough sets, information systems and matroids.

2.1. Pawlak’s Rough Sets and Information Systems

The definition of approximation operators is presented in [1,41].

Let R an equivalence relation on U. For any $X\subseteq U$, a pair of approximation $\overline{R}(X)$ and $\underline{R}(X)$ of X are defined by

$$\begin{array}{c}\overline{R}(X)=\{x\in U:RN(x)\bigcap X\ne \varnothing \},\hfill \\ \underline{R}(X)=\{x\in U:RN(x)\subseteq X\},\hfill \end{array}$$

where $RN(x)=\{y\in U:xRy\}$. $\overline{R}$ and $\underline{R}$ are called the upper and lower approximation operators with respect to R, respectively.

In this paper, U is a nonempty and finite set called universe. Let $-X$ be the complement of X in U and ∅ be the empty set. We have the following conclusions about $\overline{R}$ and $\underline{R}$.

Proposition 1.

Refs. [1,41] Let R be an equivalence relation on U. For any $X,Y\subseteq U$,

$$\begin{array}{ccc}\begin{array}{c}(\mathit{1}L)\underline{R}(U)=U,\hfill \\ (\mathit{2}L)\underline{R}(\varphi )=\varphi ,\hfill \\ (\mathit{3}L)\underline{R}(X)\subseteq X,\hfill \\ (\mathit{4}L)\underline{R}(X\bigcap Y)=\underline{R}(X)\bigcap \underline{R}(Y),\hfill \\ (\mathit{5}L)\underline{R}(\underline{R}(X))=\underline{R}(X),\hfill \\ (\mathit{6}L)X\subseteq Y\Rightarrow \underline{R}(X)\subseteq \underline{R}(Y),\hfill \\ (\mathit{7}L)\underline{R}(-\underline{R}(X))=-\underline{R}(X),\hfill \\ (\mathit{8}LH)\underline{R}(-X)=-\overline{R}(X),\hfill \end{array}\hfill & & \hfill \begin{array}{c}(\mathit{1}H)\overline{R}(U)=U,\hfill \\ (\mathit{2}H)\overline{R}(\varphi )=\varphi ,\hfill \\ (\mathit{3}H)X\subseteq \overline{R}(X),\hfill \\ (\mathit{4}H)\overline{R}(X\bigcup Y)=\overline{R}(X)\bigcup \overline{R}(Y),\hfill \\ (\mathit{5}H)\overline{R}(\overline{R}(X))=\overline{R}(X),\hfill \\ (\mathit{6}H)X\subseteq Y\Rightarrow \overline{R}(X)\subseteq \overline{R}(Y),\hfill \\ (\mathit{7}H)\overline{R}(-\overline{R}(X))=-\overline{R}(X),\hfill \\ (\mathit{9}LH)\underline{R}(X)\subseteq \overline{R}(X).\hfill \end{array}\end{array}$$

On the basis of the upper and lower approximation operators with respect to R, one can define three operators to divide the universe, namely, the negative operator $NE{G}_R$, the positive operator $PO{S}_R$ and the boundary operator $BN{D}_R$:

$$\begin{array}{c}NE{G}_R(X)=U-\overline{R}(X),\hfill \\ PO{S}_R(X)=\underline{R}(X),\hfill \\ BN{D}_R(X)=\overline{R}(X)-\underline{R}(X).\hfill \end{array}$$

An information system [38] is an ordered pair $IS=(U,A)$, where U is a nonempty finite set of objects and A is a nonempty finite set of attributes such that $a:U\to V_a$ for any $a\in A$, where $V_a$ is called the value set of a. For all $B\subseteq A$, the indiscernibility relation induced by B is defined as follows:

$$IND(B)=\{(x,y)\in U\times U:\forall b\in B,b(x)=b(y)\}.$$

Definition 1.

(Reduct [38]) Let $IS=(U,A)$ be an information system. For all $B\subseteq A$, B is called a reduct of $IS$, if the following two conditions hold:

(1) $IND(B)\ne IND(B-b)$ for any $b\in B$,

(2) $IND(B)=IND(A)$.

2.2. Matroids

Definition 2.

(Matroid [29,30]) Let U is a finite set, and $\mathit{I}$ is a nonempty subset of $2^U$ (the set of all subsets of U). $(U,\mathit{I})$ is called a matroid, if the following conditions hold:

$(I1)$ If $I\in \mathit{I}$ and $I^{\prime }\subseteq I$, then $I^{\prime }\in \mathit{I}$.

$(I2)$ If $I_1,I_2\in \mathit{I}$ and $|I_1|<|I_2|$, then there exists $e\in I_2-I_1$ such that $I_1\bigcup \{e\}\in \mathit{I}$, where $|I|$ denotes the cardinality of I.

Let $M=(U,\mathbf{I})$ be a matroid. We shall often write $U(M)$ for U and $\mathbf{I}(M)$ for $\mathbf{I}$, particularly when several matroids are being considered. The members of $\mathbf{I}$ are the independent sets of M.

Example 1.

Let $U=\{a_1,a_2,a_3,a_4,a_5\}$ and $\mathit{I}=\{\varnothing ,\{a_1\},\{a_2\},\{a_3\},\{a_4\},\{a_5\},\{a_1,a_3\},\{a_1,a_4\},\{a_1,a_5\},$ $\{a_2,a_3\},\{a_2,a_4\},\{a_2,a_5\},\{a_3,a_4\},\{a_3,a_5\},\{a_4,a_5\},\{a_1,a_3,a_4\},\{a_1,a_3,a_5\},\{a_1,a_4,a_5\},\{a_2,a_3,a_4\},$ $\{a_2,a_3,a_5\},\{a_2,a_4,a_5\}\}$. Then, $M=(U,$ $\mathit{I})$ is a matroid.

In order to make some expressions brief, some denotations are presented. Let $\mathbf{A}\subseteq 2^U$. Then,

$$\begin{array}{c}Min(\mathbf{A})=\{X\in \mathbf{A}:\forall Y\in \mathbf{A},Y\subseteq X\Rightarrow X=Y\},\hfill \\ Max(\mathbf{A})=\{X\in \mathbf{A}:\forall Y\in \mathbf{A},X\subseteq Y\Rightarrow X=Y\},\hfill \\ Opp(\mathbf{A})=\{X\subseteq U:X\notin \mathbf{A}\}.\hfill \end{array}$$

The set of all circuits of M is defined as $\mathbf{C}(M)=Min(Opp(\mathbf{I}))$. The rank function $r_M$ of M is denoted by $r_M(X)=max\{|I|:I\subseteq X,I\in \mathbf{I}\}$ for any $X\subseteq U$. $r_M(X)$ is called the rank of X in M. The closure operator $c{l}_M$ of M is defined as

$$c{l}_M(X)=\{u\in U:r_M(X)=r_M(X\bigcup \{u\})\}\mathrm{for}\mathrm{all}X\subseteq U$$

.

We call $c{l}_M(X)$ the closure of X in M. X is called a closed set if $c{l}_M(X)=X$, and we denote the family of all closed sets of M by $\mathbf{F}(M)$. The closure axiom of a matroid is introduced in the following proposition.

Proposition 2.

(Closure axiom [29,30]) Let $cl$ be an operator of U. Then, there exists one and only one matroid M such that $cl=c{l}_M$ iff $cl$ satisfies the following four conditions:

$(CL1)$$X\subseteq cl(X)$ for any $X\subseteq U$;

$(CL2)$ If $X\subseteq Y\subseteq U$, then $cl(X)\subseteq cl(Y)$;

$(CL3)$$cl(cl(X))=cl(X)$ for any $X\subseteq U$;

$(CL4)$ For any $x,y\in U$, if $y\in cl(X\bigcup \{x\})-cl(X)$, then $x\in cl(X\bigcup \{y\})$.

Example 2.

(Continued from Example 1) Let $X=\{a_3,a_4\}$. Then,

$\mathit{C}(M)=Min(Opp(\mathit{I}))=\{\{a_1,a_2\},\{a_3,a_4,a_5\}\}$,

$r_M(X)=max\{|I|:I\subseteq X,I\in \mathit{I}\}=2$,

$c{l}_M(X)=\{u\in U:r_M(X)=r_M(X\bigcup \{u\})\}=\{a_3,a_4,a_5\}$,

$\mathit{F}(M)=\{\varnothing ,\{a_3\},\{a_4\},\{a_5\},\{a_1,a_2\},\{a_1,a_2,a_3\},\{a_1,a_2,a_4\},\{a_1,a_2,a_5\},\{a_3,a_4,a_5\},\{a_1,a_2,a_3,a_4,a_5\}\}$.

Based on $\mathbf{F}(M)$, the interior operator $in{t}_M$ of M is defined as

$$in{t}_M(X)=\bigcup \{Y\subseteq X:U-Y\in \mathbf{F}(M)\}\mathrm{for}\mathrm{any}X\subseteq U$$

.

$in{t}_M(X)$ is called the interior of X in M. X is called a open set if $in{t}_M(X)=X$. The following proposition shows the interior axiom of a matroid.

Proposition 3.

(Interior axiom [29,30]) Let $int$ be an operator of U. Then, there exists one and only one matroid M such that $int=in{t}_M$ iff $int$ satisfies the following four conditions:

$(INT1)$$int(X)\subseteq X$ for any $X\subseteq U$,

$(INT2)$ If $X\subseteq Y\subseteq U$, then $int(X)\subseteq int(Y)$,

$(INT3)$$int(int(X))=int(X)$ for any $X\subseteq U$,

$(INT4)$ For any $x,y\in U$, if $y\in int(X)-int(X-\{x\})$, then $x\notin int(X-\{y\})$.

Example 3.

(Continued from Example 2) $in{t}_M(X)=\bigcup \{Y\subseteq X:U-Y\in \mathit{F}(M)\}=\{a_3,a_4\}$.

Based on the closure operator $c{l}_M$, the exterior operator $e{x}_M$ and the boundary operator $b{o}_M$ of M are defined as

$$e{x}_M(X)=-c{l}_M(X)\mathrm{and}b{o}_M(X)=c{l}_M(X)\bigcap c{l}_M(-X)\mathrm{for}\mathrm{all}X\subseteq U$$

.

$e{x}_M(X)$ is called the exterior of X in M, and $b{o}_M(X)$ is called the boundary of X in M. The following two propositions present the exterior and boundary axioms, respectively.

Proposition 4.

(Exterior axiom [42]) Let $ex$ be an operator of U. Then, there exists one and only one matroid M such that $ex=e{x}_M$ iff $e{x}_M$ satisfies the following four conditions:

$(EX1)$$X\bigcap ex(X)=\varnothing$ for any $X\subseteq U$;

$(EX2)$ If $X\subseteq Y\subseteq U$, then $ex(Y)\subseteq ex(X)$;

$(EX3)$$ex(-ex(X))=ex(X)$ for any $X\subseteq U$;

$(EX4)$ For any $x,y\in U$, if $y\in ex(X)-ex(X\bigcup \{x\})$, then $x\notin ex(X\bigcup \{y\})$.

Proposition 5.

(Boundary axiom [42]) Let $bo$ be an operator of U. Then, there exists one and only one matroid M such that $bo=b{o}_M$ iff $bo$ satisfies the following five conditions:

$(BO1)$$bo(X)=bo(-X)$ for any $X\subseteq U$;

$(BO2)$$bo(bo(X))\subseteq bo(X)$ for any $X\subseteq U$;

$(BO3)$$X\bigcap Y\bigcap (bo(X)\bigcup bo(Y))\subseteq X\bigcap Y\bigcap bo(X\bigcap Y)$ for any $X,Y\subseteq U$;

$(BO4)$ For any $x,y\in U$, if $y\in bo(X\bigcup \{x\})-bo(X)$, then $x\in bo(X\bigcup \{y\})$;

$(BO5)$$bo(X\bigcup bo(X))\subseteq bo(X)$ for any $X\subseteq U$.

Example 4.

(Continued from Example 2) $e{x}_M(X)=U-\{a_3,a_4,a_5\}=\{a_1,a_2\}$,

$b{o}_M(X)=c{l}_M(X)\bigcap c{l}_M(-X)=\{a_3,a_4,a_5\}\bigcap \{a_1,a_2,a_5\}=\{a_5\}$.

The following proposition shows some relationships between these above four operators, namely $c{l}_M$, $in{t}_M$, $e{x}_M$ and $b{o}_M$.

Proposition 6.

Ref. [42] Let $M=(U,\mathit{I})$ be a matroid. For all $X\subseteq U$, the following statements hold:

$(1)$$in{t}_M(X)=-c{l}_M(-X)$ and $c{l}_M(X)=-in{t}_M(-X)$;

$(2)$$c{l}_M(b{o}_M(X))=b{o}_M(X)$;

$(3)$$b{o}_M(e{x}_M(X))=b{o}_M(-X)$.

3. The Relationship about Operators between Rough Sets and Matroids

In this section, four matroids are induced by four operators of rough sets. These four matroids are induced by the lower approximation operator $\underline{R}$ (because $\underline{R}=PO{S}_R$, we only consider $\underline{R}$), the upper approximation operator $\overline{R}$, the negative operator $NE{G}_R$ and the boundary operator $BN{D}_R$ through the interior axiom, the closure axiom, the exterior axiom and the boundary axiom, respectively. Among them, the upper approximation operator $\overline{R}$ has been studied in [35]. Then, the relationship between these four matroids are studied, and we find that these four are the same one. According to this work, we present the relationship about operators between rough sets and matroids.

3.1. Four Matroids Induced by Four Operators of Rough Sets

In this subsection, we generalize the positive operator (the lower approximation operator), the upper approximation operator, the negative operator and the boundary operator of rough sets to the interior operator, the closure operator, the exterior operator and the boundary operator of matroids, respectively. Firstly, the following lemma is proposed.

Lemma 1.

Refs. [1,41] Let R be an equivalence relation on U. For any $x,y\in U$, if $x\in RN(y)$, then $y\in RN(x)$.

The following proposition shows that the lower approximation operator $\underline{R}$ satisfies the interior axiom of matroids.

Proposition 7.

Let R be an equivalence relation on U. Then, $\underline{R}$ satisfies $(INT1)$, $(INT2)$, $(INT3)$ and $(INT4)$ of Proposition 3.

Proof. 

By $(1L)$, $(6L)$ and $(5L)$ of Proposition 1, $\underline{R}$ satisfies $(INT1)$, $(INT2)$ and $(INT3),$ respectively. $(INT4)$: For any $x,y\in U$, if $y\in \underline{R}(X)-\underline{R}(X-\{x\})$, then $y\in \underline{R}(X)$ but $y\notin \underline{R}(X-\{x\})$. Hence, $RN(y)\subseteq X$ but $RN(y)\neg \subseteq X-\{x\}$. Therefore, $x\in RN(y)$. According to Lemma 1, $y\in RN(x)$. Hence, $RN(x)\neg \subseteq X-\{y\}$, i.e., $x\notin \underline{R}(X-\{y\})$. ☐

Inspired by Proposition 7, there is a matroid such that $\underline{R}$ is its interior operator.

Definition 3.

Let R be an equivalence relation on U. The matroid whose interior operator is $\underline{R}$ is denoted by $M(\underline{R})$. We say $M(\underline{R})$ is the matroid induced by $\underline{R}$.

Corollary 1.

Let R be an equivalence relation on U. Then, $in{t}_{M(\underline{R})}=PO{S}_R$.

Proof. 

According to Definition 3, $in{t}_{M(\underline{R})}=\underline{R}$. Since $PO{S}_R=\underline{R}$, so $in{t}_{M(\underline{R})}=PO{S}_R$. ☐

The upper approximation operator $\overline{R}$ satisfies the closure axiom in [35,38].

Proposition 8.

Refs. [35,38] Let R be an equivalence relation on U. Then, $\overline{R}$ satisfies $(CL1)$, $(CL2)$, $(CL3)$ and $(CL4)$ of Proposition 2.

Proposition 8 determines the second matroid induced by $\overline{R}$.

Definition 4.

Let R be an equivalence relation on U. The matroid whose closure operator is $\overline{R}$ is denoted by $M(\overline{R})$. We say that $M(\overline{R})$ is the matroid induced by $\overline{R}$.

The negative operator $NE{G}_R$ satisfies the exterior axiom.

Proposition 9.

Let R be an equivalence relation on U. Then, $NE{G}_R$ satisfies $(EX1)$, $(EX2)$, $(EX3)$ and $(EX4)$ of Proposition 4.

Proof. 

$(EX1)$: For any $X\subseteq U$, $NE{G}_R(X)=U-\overline{R}(X)$. According to $(3H)$ of Proposition 1, $X\subseteq \overline{R}(X)$. Therefore, $X\bigcap NE{G}_R(X)=\varnothing$;

$(EX2)$: According to $(6H)$ of Proposition 1, if $X\subseteq Y\subseteq U$, then $\overline{R}(X)\subseteq \overline{R}(Y)$. Therefore, $U-\overline{R}(Y)\subseteq U-\overline{R}(Y)$, i.e., $NE{G}_R(Y)\subseteq NE{G}_R(X)$;

$(EX3)$: For any $X\subseteq U$, $NE{G}_R(X)=U-\overline{R}(X)$. Hence, $-NE{G}_R(X)=U-NE{G}_R(X)=U-(U-\overline{R}(X))=\overline{R}(X)$. Therefore, $NE{G}_R(-NE{G}_R(X))=NE{G}_R(\overline{R}(X))=U-\overline{R}(\overline{R}(X))$. According to $(5H)$ of Proposition 1, $\overline{R}(\overline{R}(X))=\overline{R}(X)$. Hence, $NE{G}_R(-NE{G}_R(X))=U-\overline{R}(X)=NE{G}_R(X)$;

$(EX4)$: For any $x,y\in U$, if $y\in NE{G}_R(X)-NE{G}_R(X\bigcup \{x\})$, then $y\in NE{G}_R(X)$ but $y\notin NE{G}_R(X\bigcup \{x\})$, i.e., $y\in U-\overline{R}(X)$ but $y\notin U-\overline{R}(X\bigcup \{x\})$. Since $\overline{R}(X)\subseteq U$ and $\overline{R}(X\bigcup \{x\})\subseteq U$, so $y\in \overline{R}(X\bigcup \{x\})$ but $y\notin \overline{R}(X)$. Hence, $RN(y)\bigcap (X\bigcup \{x\})\ne \varnothing$ but $RN(y)\bigcap X=\varnothing$. Therefore, $RN(y)\bigcap \{x\}\ne \varnothing$, i.e., $x\in RN(y)$. According to Lemma 1, $y\in RN(x)$. Hence, $RN(x)\bigcap (X\bigcup \{y\})\ne \varnothing$, i.e., $x\in \overline{R}(X\bigcup \{y\})$. Therefore, $x\notin U-\overline{R}(X\bigcup \{y\})$, i.e., $x\notin NE{G}_R(X\bigcup \{y\})$. ☐

Proposition 9 determines the third matroid such that $NE{G}_R$ is its exterior operator.

Definition 5.

Let R be an equivalence relation on U. The matroid whose exterior operator is $NE{G}_R$ is denoted by $M(NE{G}_R)$. We say $M(NE{G}_R)$ is the matroid induced by $NE{G}_R$.

In order to certify the boundary operator $BN{D}_R$ satisfies the boundary axiom, the following two lemmas are proposed.

Lemma 2.

Refs. [1,41] Let R be an equivalence relation on U. For all $X,Y\subseteq U$, $\overline{R}(X\bigcap Y)\subseteq \overline{R}(X)\bigcap \overline{R}(Y)$.

Lemma 3.

Let R be an equivalence relation on U. If $X\subseteq Y\subseteq U$, then $X\bigcap BN{D}_R(Y)\subseteq BN{D}_R(X)$.

Proof. 

For any $x\in X\bigcap BN{D}_R(Y)$, $X\bigcap BN{D}_R(Y)=X\bigcap (\overline{R}(X)-\underline{R}(X))=X\bigcap \overline{R}(X)\bigcap \overline{R}(-X))$. Since $X\subseteq Y\subseteq U$, so $-Y\subseteq -X\subseteq U$. According to $(6H)$ of Proposition 1, $X\bigcap \overline{R}(X)\bigcap \overline{R}(-X))=X\bigcap \overline{R}(-X)\subseteq \overline{R}(X)\bigcap \overline{R}(-X)=BN{D}_R(X)$. Hence, $x\in BN{D}_R(X)$, i.e., $X\bigcap BN{D}_R(Y)$ $\subseteq BN{D}_R(X)$. ☐

The boundary operator $BN{D}_R$ satisfies the boundary axiom.

Proposition 10.

Let R be an equivalence relation on U. Then, $BN{D}_R$ satisfies $(BO1)$, $(BO2)$, $(BO3)$, $(BO4)$ and $(BO5)$ of Proposition 5.

Proof. 

$(BO1)$: According to $(8LH)$ of Proposition 1, $\underline{R}(-X)=-\overline{R}(X)$. For any $X\subseteq U$,

$$\begin{array}{cc}BN{D}_R(-X)\hfill & =\overline{R}(-X)-\underline{R}(-X)\hfill \\ & =\overline{R}(-X)\bigcap (U-\underline{R}(-X))\hfill \\ & =(-\underline{R}(X))\bigcap \overline{R}(X)\hfill \\ & =\overline{R}(X)\bigcap (-\underline{R}(X))\hfill \\ & =\overline{R}(X)-\underline{R}(X)\hfill \\ & =BN{D}_R(X).\hfill \end{array}$$

$(BO2)$: For any $X\subseteq U$,

$$\begin{array}{cc}BN{D}_R(BN{D}_R(X))\hfill & =\overline{R}(BN{D}_R(X))-\underline{R}(BN{D}_R(X))\hfill \\ & =\overline{R}(BN{D}_R(X))\bigcap (U-\underline{R}(BN{D}_R(X)))\hfill \\ & =\overline{R}(BN{D}_R(X))\bigcap (-\underline{R}(BN{D}_R(X)))\hfill \\ & =\overline{R}(BN{D}_R(X))\bigcap (\overline{R}(-BN{D}_R(X)))\hfill \\ & \subseteq \overline{R}(BN{D}_R(X))\hfill \\ & =\overline{R}(\overline{R}(X)-\underline{R}(X))\hfill \\ & =\overline{R}(\overline{R}(X)\bigcap (-\underline{R}(X))).\hfill \end{array}$$

According to Lemma 1, we know

$$\begin{array}{cc}\overline{R}(\overline{R}(X)\bigcap (-\underline{R}(X)))\hfill & \subseteq \overline{R}(\overline{R}(X))\bigcap \overline{R}(-\underline{R}(X))\hfill \\ & =\overline{R}(X)\bigcap \overline{R}(-\underline{R}(X))\hfill \\ & =\overline{R}(X)-\underline{R}(X)\hfill \\ & =BN{D}_R(X).\hfill \end{array}$$

Hence, $BN{D}_R(BN{D}_R(X))\subseteq BN{D}_R(X)$;

$(BO3)$: For any $X,Y\subseteq U$, $X\bigcap Y\bigcap (BN{D}_R(X)\bigcup BN{D}_R(Y))=X\bigcap Y\bigcap ((\overline{R}(X)-\underline{R}(X))\bigcup (\overline{R}(Y)-\underline{R}(Y)))=X\bigcap Y\bigcap$$((\overline{R}(X)\bigcap \overline{R}(-X))\bigcup (\overline{R}(Y)\bigcap \overline{R}(-Y)))\subseteq X\bigcap Y\bigcap (\overline{R}(-X)\bigcup \overline{R}(-Y))$. According to $(4H)$ of Proposition 1, we know $X\bigcap Y\bigcap$ $(\overline{R}(-X)\bigcup \overline{R}(-Y))=X\bigcap Y\bigcap \overline{R}((-X)\bigcup (-Y))=X\bigcap Y\bigcap \overline{R}(-(X\bigcap Y))$. According to $(6H)$ of Proposition 1, we know $X\bigcap Y\subseteq \overline{R}(X\bigcap Y)$. Therefore, $X\bigcap Y\bigcap$ $\overline{R}(-(X\bigcap Y))=X\bigcap Y\bigcap \overline{R}(-(X\bigcap Y))\bigcap \overline{R}(X\bigcap Y)=X\bigcap Y\bigcap BN{D}_R(X\bigcap Y)$.

$(BO4)$: When $x=y$ or $x\in X$, it is straightforward. When $y\in X$, it does not hold. (In fact, we suppose $y\in X$. If $y\in BN{D}_R(X\bigcup \{x\})$, according to Lemma 3, we know $y\in X\bigcap BN{D}_R(X\bigcup \{x\})\subseteq BN{D}_R(X)$, which is contradictory with $y\in BN{D}_R(X\bigcup \{x\})-BN{D}_R(X)$. Hence, $y\notin X$.) We only need to prove it for $x\ne y$ and $x,y\notin X$. If $y\in BN{D}_R(X\bigcup \{x\})-BN{D}_R(X)$, since

$$\begin{array}{cc}& BN{D}_R(X\bigcup \{x\})-BN{D}_R(X)\hfill \\ =\hfill & (\overline{R}(X\bigcup \{x\})-\underline{R}(X\bigcup \{x\}))-(\overline{R}(X)-\underline{R}(X))\hfill \\ =\hfill & (\overline{R}(X\bigcup \{x\})\bigcap \overline{R}(-(X\bigcup \{x\})))-(\overline{R}(X)\bigcap \overline{R}(-X))\hfill \\ =\hfill & (\overline{R}(X\bigcup \{x\})\bigcap \overline{R}(-(X\bigcup \{x\})))\bigcap ((-\overline{R}(X))\bigcup (-\overline{R}(-X)))\hfill \\ =\hfill & (\overline{R}(X\bigcup \{x\})\bigcap \overline{R}(-(X\bigcup \{x\}))\bigcap (-\overline{R}(X)))\bigcup (\overline{R}(X\bigcup \{x\})\hfill \\ & \bigcap (\overline{R}(-(X\bigcup \{x\})))\bigcap (-\overline{R}(-X)))\hfill \\ =\hfill & \overline{R}(X\bigcup \{x\})\bigcap \overline{R}(-(X\bigcup \{x\}))\bigcap (-\overline{R}(X))\hfill \\ =\hfill & \overline{R}(X\bigcup \{x\})\bigcap (-\overline{R}(X))\bigcap \overline{R}(-(X\bigcup \{x\}))\hfill \\ =\hfill & (\overline{R}(X\bigcup \{x\})-\overline{R}(X))\bigcap \overline{R}(-(X\bigcup \{x\})),\hfill \end{array}$$

then $y\in \overline{R}(X\bigcup \{x\})-\overline{R}(X)$ and $y\in \overline{R}(-(X\bigcup$ $\{x\}))$. According to Proposition 8, we have $x\in \overline{R}(X\bigcup \{y\})$. Since $y\in \overline{R}(-(X\bigcup \{x\}))$, so $x\in \overline{R}(-(X\bigcup \{y\}))$. Hence, $y\in \overline{R}(X\bigcup \{y\})\bigcap \overline{R}(-(X\bigcup \{y\}))$, i.e., $y\in BN{D}_R(X\bigcup \{y\})$.

$(BO5)$: For any $X,Y\subseteq U$,

$$\begin{array}{cc}BN{D}_R(X\bigcup BN{D}_R(X))\hfill & =\overline{R}(X\bigcup BN{D}_R(X))-\underline{R}(X\bigcup BN{D}_R(X))\hfill \\ & =\overline{R}(X\bigcup BN{D}_R(X))\bigcap \overline{R}(-(X\bigcup BN{D}_R(X)))\hfill \\ & =\overline{R}(X\bigcup BN{D}_R(X))\bigcap \overline{R}((-X)\bigcap (BN{D}_R(-X)))\hfill \\ & \subseteq \overline{R}(X\bigcup BN{D}_R(X))\bigcap \overline{R}(-X)\hfill \\ & =\overline{R}(X\bigcup (\overline{R}(X)\bigcap \overline{R}(-X)))\bigcap \overline{R}(-X)\hfill \\ & =\overline{R}(\overline{R}(X)\bigcap U)\bigcap \overline{R}(-X)\hfill \\ & =\overline{R}(\overline{R}(X))\bigcap \overline{R}(-X).\hfill \end{array}$$

According to $(5H)$ and $(8LH)$ of Proposition 1, $\overline{R}(\overline{R}(X))\bigcap \overline{R}(-X)=\overline{R}(X)\bigcap \overline{R}(-X)=\overline{R}(X)-\underline{R}(X)=BN{D}_R(X)$. Therefore, $BN{D}_R(X\bigcup BN{D}_R(X))\subseteq BN{D}_R(X)$. ☐

Proposition 8 determines the fourth matroid such that $BN{D}_R$ is its boundary operator.

Definition 6.

Let R be an equivalence relation on U. The matroid whose boundary operator is $BN{D}_R$ is denoted by $M(BN{D}_R)$. We say that $M(BN{D}_R)$ is the matroid induced by $BN{D}_R$.

3.2. The Relationship between These Four Matroids

This subsection studies the relationship between these four matroids in the above subsection. In fact, these four matroids are the same one.

Theorem 1.

Let R be an equivalence relation on U. Then,

$$M(\underline{R})=M(\overline{R})=M(NE{G}_R)=M(BN{D}_R)$$

.

Proof. 

$(1)$ On one hand, $M(\underline{R})$ and $M(\overline{R})$ have the same grand U. On the other hand, according to Definition 3, we know $in{t}_{M(\underline{R})}(X)=\underline{R}(X)$ for any $X\subseteq U$. By Proposition 6, $c{l}_{M(\underline{R})}(X)=-in{t}_{M(\underline{R})}(-X)=-\underline{R}(-X)$. According to $(8LH)$ of Proposition 1, $-\underline{R}(-X)=\overline{R}(X)$. Hence, $c{l}_{M(\underline{R})}(X)=\overline{R}(X)$. According to Definition 4, $c{l}_{M(\overline{R})}(X)=\overline{R}(X)$. Therefore, $c{l}_{M(\underline{R})}(X)=c{l}_{M(\overline{R})}(X)$, i.e., $M(\underline{R})=M(\overline{R})$.

$(2)$ On one hand, $M(\overline{R})$ and $M(NE{G}_R)$ have the same grand U. On the other hand, according to Definition 4, we know $c{l}_{M(\overline{R})}=\overline{R}$. For any $X\subseteq U$, $e{x}_{M(\overline{R})}(X)=-c{l}_{M(\overline{R})}(X)=-\overline{R}(X)=U-\overline{R}(X)=NE{G}_R(X)$. By Definition 5, $e{x}_{M(NE{G}_R)}(X)=NE{G}_R(X)$. Hence, $e{x}_{M(\overline{R})}(X)=e{x}_{M(NE{G}_R)}(X)$, i.e., $M(\overline{R})=M(NE{G}_R)$.

$(3)$ On one hand, $M(\overline{R})$ and $M(NE{G}_R)$ have the same grand U. On the other hand, according to Definition 4, we have $c{l}_{M(\overline{R})}=\overline{R}$. For all $X\subseteq U$, $b{o}_{M(\overline{R})}(X)=c{l}_{M(\overline{R})}(X)\bigcap c{l}_{M(\overline{R})}(-X)=\overline{R}(X)\bigcap \overline{R}(-X)=\overline{R}(X)\bigcap \overline{R}(-X)=\overline{R}(X)-\underline{R}(X)=BN{D}_R(X)$. According to Definition 6, $b{o}_{M(NE{G}_R)}(X)=BN{D}_R(X)$. Therefore, $b{o}_{M(\overline{R})}(X)=b{o}_{M(NE{G}_R)}(X)$, i.e., $M(\overline{R})=M(NE{G}_R)$. ☐

Definition 7.

Let R be an equivalence relation on U. The matroid whose interior operator, closure operator, exterior operator and boundary operator are $\underline{R}$, $\overline{R}$, $NE{G}_R$ and $BN{D}_R$ is defined as $M(R)$. We say that $M(R)$ is the matroid induced by R.

According to the above definition, we have the relationship about operators between rough sets and matroids as

Table 1. The relationship about operators between rough sets and matroids.

$\mathit{M}(\mathit{R})$ Is the Matroid Induced by R
$in{t}_{M(R)}=\underline{R}=PO{S}_R$
$c{l}_{M(R)}=\overline{R}$
$e{x}_{M(R)}=NE{G}_R$
$b{o}_{M(R)}=BN{D}_R$

:

3.3. The Relationship about Operations between Matroids and Rough Sets

In this subection, a relationship about the restriction operation both in matroids and rough sets is proposed. First of all, two definitions of these two operations are presented in the following two definitions.

Definition 8.

(Restriction [29,30]) Let $M=(U,\mathit{I})$ be a matroid. For $X\subseteq U$, the restriction of M to X is defined as $M|X=(X,{\mathit{I}}_X)$, where ${\mathit{I}}_X=\{I\subseteq X:I\in \mathit{I}\}$.

Not that $\mathbf{C}(M|X)=\{C\subseteq X:C\in \mathbf{C}(M)\}$. For an equivalence relation R on U, there is also a definition of restriction of R. For any $X\subseteq U$, $R|X$ is an equivalence relation called the restriction of R to X, where $R|X=\{(x,y)\in X\times X:(x,y)\in R\}$, $X\times X$ is the product set of X and X. According to Definition 7, $M(R|X)$ is a matroid on X.

In [38], the set of independent sets of $M(R)$ is proposed in the following lemma.

Lemma 4.

Ref. [38] Let R be an equivalence relation on U. Then,

$$\mathit{I}(M(R))=\{X\subseteq U:\forall x,y\in X,x\ne y\Rightarrow (x,y)\notin R\}$$

.

Example 5.

Let R be an equivalence relation on U with $U=\{a,b,c,d,e\}$, and $U/R=\{\{a,b\},\{c,d,e\}\}$. According to Lemma 4, $\mathit{I}(M(R))=\{\varnothing ,\{a\},\{b\},\{c\},\{d\},\{e\},\{a,c\},\{b,c\},\{a,d\},\{b,d\},\{a,e\},\{b,e\}\}$.

Proposition 11.

Let R be an equivalence relation on U and $X\subseteq U$. Then, $M(R|X)=M(R)|X$.

Proof. 

For any $X\subseteq U$, $R|X$ is an equivalence relation on X. Thus, $M(R|X)$ is a matroid on X. By Definition 8, $M(R)|X$ is a matroid on X. Therefore, we need to prove only $\mathbf{I}(M(R|X))=\mathbf{I}(M(R)|X)$. According to Lemma 4, $\mathbf{I}(M(R|X))=\{Y\subseteq X:\forall x,y\in Y,x\ne y\Rightarrow (x,y)\notin R|X\}$, $\mathbf{I}(M(R)|X)=\{Y\subseteq X:\forall x,y\in Y,x\ne y\Rightarrow (x,y)\notin R\}$. On one hand, since $R|X\subseteq R$, $\mathbf{I}(M(R)|X)\subseteq \mathbf{I}(M(R|X))$. On the other hand, suppose $Y\in \mathbf{I}(M(R|X))-\mathbf{I}(M(R)|X)$. For any $x,y\in Y$, if $x\ne y$, then $(x,y)\notin R|X$ but $(x,y)\in R$. Therefore, $x,y\notin X$ but $x,y\in U$, i.e., $x,y\in U-X$. Hence, $Y\subseteq U-X$, which is contradictory with $Y\subseteq X$, i.e., $Y\in \mathbf{I}(M(R|X))-\mathbf{I}(M(R)|X)$. Thus, $\mathbf{I}(M(R|X))\subseteq \mathbf{I}(M(R)|X)$. ☐

Example 6.

(Continued from Example 5) Let $X=\{a,b,c\}$. According to Definition 8, $\mathit{I}(M(R)|X)=\{\varnothing ,\{a\},\{b\},\{c\},$ $\{a,c\},\{b,c\}\}$, and $M(R)|X=(X,\mathit{I}(M(R)|$ $X))$. Since $R|X=\{(a,a),(b,b),(c,c),(a,b),(b,a)\}$, so $X/(R|X)=\{\{a,b\},\{c\}\}$. According to Lemma 4, $\mathit{I}(M(R|X))=\{\varnothing ,\{a\},\{b\},\{c\},\{a,c\},\{b,c\}\}$, and $M(R|X)$ $=(X,\mathit{I}(M(R|X))$. Therefore, $M(R|X)=M(R)|X$.

4. A Matroidal Approach to Attribute Reduction through the Girth Function

In this section, a matroidal approach is proposed to compute attribute reduction in information systems through the girth function of matroids.

4.1. An Equivalent Formulation of Attribute Reduction through the Girth Function

Lemma 5.

Ref. [15] Let $R_1$ and $R_2$ be two equivalence relations on U, respectively. Then, $\underline{R_1}=\underline{R_2}$ if and only if $R_1=R_2$.

Based on Lemma 5, we propose a necessary and sufficient condition for two equivalence relations induce the same matroids.

Proposition 12.

Let $R_1$ and $R_2$ be two equivalence relations on U, respectively. Then, $M(R_1)=M(R_2)$ if and only if $R_1=R_2$.

Proof. 

According to Definition 7, $M(R_1)$ and $M(R_2)$ have the same grand U. According to Proposition 3, Proposition 7 and Lemma 5,

$$\begin{array}{cc}M(R_1)=M(R_2)\hfill & \iff in{t}_{M(R_1)}=in{t}_{M(R_2)}\hfill \\ & \iff \underline{R_1}=\underline{R_2}\hfill \\ & \iff R_1=R_2.\hfill \end{array}$$

 ☐

An equivalent formulation of attribute reduction in information systems is presented from the viewpoint of matroids.

Proposition 13.

Let $IS=(U,A)$ be an information system. For all $B\subseteq A$, B is a reduct of $IS$ if and only if it satisfies the following two conditions:

(1) For all $b\in B$, $M(IND(B))\ne M(IND(B-b))$;

(2) $M(IND(B))=M(IND(A))$.

Proof. 

Since $IND(A)$, $IND(B)$ and $IND(B-b)$ are equivalence relations on U, $M(IND(A))$, $M(IND(B))$ and $M(IND(B-b))$ are matroids on U. According to Proposition 12,

(1) For all $b\in B$, $M(IND(B))\ne M(IND(B-b))\iff IND(B)\ne IND(B-b)$;

(2) $M(IND(B))=M(IND(A))\iff IND(B)=IND(A)$.

According to Definition 1, it is immediate. ☐

In Proposition 13, the equivalent formulation of attribute reduction is not convenient for us to compute the attribute reduction. We consider to use the girth function of matroids to compute it.

Definition 9.

(Girth function [29,30]) Let $M=(U,\mathit{I})$ be a matroid. The girth $g(M)$ of M is defined as:

$$g(M)=\left\{\begin{array}{cc}min\{|C|:C\in \mathit{C}(M)\},\hfill & \mathit{C}(M)\ne \varnothing ;\hfill \\ \infty ,\hfill & \mathit{C}(M)=\varnothing .\hfill \end{array}\right.$$

For all $X\subseteq U$, the girth function $g_M$ is defined as $g_M(X)=g(M|X)$. $g_M(X)$ is called the girth of X in M.

According to Definition 9, the girth function is related to circuits. Thus, the following lemma presents the family of all circuits of $M(R)$.

Lemma 6.

Ref. [38] Let R be an equivalence relation on U. Then,

$$\mathit{C}(M(R))=\{\{x,y\}\subseteq U:x\ne y\wedge (x,y)\in R\}$$

.

Example 7.

(Continued from Example 5) $\mathit{C}(M(R))=\{\{a,b\},\{c,d\},\{c,e\},\{d,e\}\}$.

Based on the characteristics of the matroid induced by an equivalence relation, a type of matroids is abstracted, which is called a 2-circuit matroid. M is called a 2-circuit matroid if $|C|=2$ for all $C\in \mathbf{C}(M)$. Note that, if $\mathbf{C}(M)=\varnothing$, then M is also a 2-circuit matroid. In this section, we don’t consider this case. The matroid $M(R)$ is a 2-circuit matroid.

Proposition 14.

Let R be an equivalence relation on U and $X\subseteq U$. Then,

$$g(M(R))=\left\{\begin{array}{cc}2,\hfill & \mathit{C}(M(R))\ne \varnothing ;\hfill \\ \infty ,\hfill & \mathit{C}(M(R))=\varnothing ;\hfill \end{array}\right.$$

$$g_{M(R)}(X)=\left\{\begin{array}{cc}2,\hfill & \mathit{C}(M(R)|X)\ne \varnothing ;\hfill \\ \infty ,\hfill & \mathit{C}(M(R)|X)=\varnothing .\hfill \end{array}\right.$$

Proof. 

Since $M(R)$ is a 2-circuit matroid, $|C|=2$ for all $C\in \mathbf{C}(M(R))$. According to Definition 9, it is immediate. ☐

Corollary 2.

Let R be an equivalence relation on U and $X\subseteq U$. Then,

$$g(M(R))=\left\{\begin{array}{cc}2,\hfill & \exists x\in U,s.t.,|RN(x)|\ge 2;\hfill \\ \infty ,\hfill & otherwise,\hfill \end{array}\right.$$

$$g_{M(R)}(X)=\left\{\begin{array}{cc}2,\hfill & \exists x\in X,s.t.,|RN(x)\bigcap X|\ge 2;\hfill \\ \infty ,\hfill & otherwise.\hfill \end{array}\right.$$

Proof. 

According to Lemma 6,

$$\begin{array}{cc}\mathbf{C}(M(R))\ne \varnothing \hfill & \iff \exists x,y\subseteq U,s.t.,x\ne y\wedge (x,y)\in R\hfill \\ & \iff \exists x\in U,s.t.,|RN(x)|\ge 2.\hfill \end{array}$$

Hence,

$$g(M(R))=\left\{\begin{array}{cc}2,\hfill & \exists x\in U,s.t.,|RN(x)|\ge 2;\hfill \\ \infty ,\hfill & otherwise.\hfill \end{array}\right.$$

Since $\mathbf{C}(M(R)|X)=\{C\subseteq X:C\in \mathbf{C}(M(R))\}=\{\{x,y\}\subseteq X:x\ne y\wedge (x,y)\in R\}$,

$$\begin{array}{cc}\mathbf{C}(M(R)|X)\ne \varnothing \hfill & \iff \exists x,y\subseteq X,s.t.,x\ne y\wedge (x,y)\in R\hfill \\ & \iff \exists x\in U,s.t.,|RN(x)\bigcap X|\ge 2.\hfill \end{array}$$

Hence,

$$g_{M(R)}(X)=\left\{\begin{array}{cc}2,\hfill & \exists x\in X,s.t.,|RN(x)\bigcap X|\ge 2;\hfill \\ \infty ,\hfill & otherwise.\hfill \end{array}\right.$$

 ☐

Lemma 7.

Refs. [1,41] Let $R_1$ and $R_2$ be two equivalence relations on U, respectively. Then, for any $x\in U$,

$$(R_1\bigcap R_2)N(x)=R_{1}N(x)\bigcap R_{2}N(x)$$

.

According to Corollary 2, the girth function of the matroid induced by attribute subsets is presented in the following proposition.

Proposition 15.

Let $IS=(U,A)$ be an information system and $X\subseteq U$. Then, for all $B\subseteq A$,

$$g(M(IND(B)))=\left\{\begin{array}{cc}2,\hfill & \exists x\in U,s.t.,|\bigcap _{R_i\in B}{R}_{i}N(x)|\ge 2;\hfill \\ \infty ,\hfill & otherwise,\hfill \end{array}\right.$$

$$g_{M(IND(B))}(X)=\left\{\begin{array}{cc}2,\hfill & \exists x\in X,s.t.,|(\bigcap _{R_i\in B}{R}_{i}N(x))\bigcap X|\ge 2;\hfill \\ \infty ,\hfill & otherwise.\hfill \end{array}\right.$$

Proof. 

According to Lemma 7 and Corollary 2, it is immediate. ☐

Note that $R_i$ in $R_{i}N$ denotes the equivalence relation induced by attribute $R_i\in A$. According to the girth axiom, we know that a matroid is corresponding to one and only one girth function.

Proposition 16.

(Girth axiom [29,30]) Let $g:2^U\to {\mathbb{Z}}^{+}\bigcup \{0,\infty \}$ be a function. Then, there exists one and only one matroid M such that $g=g_M$ iff g satisfies the following three conditions:

$(G1)$ If $X\subseteq U$ and $g(X)<\infty$, then X has a subset Y such that $g(X)=g(Y)=|Y|$.

$(G2)$ If $X\subseteq Y\subseteq U$, then $g(X)\ge g(Y)$.

$(G3)$ If X and Y are distinct subsets of U with $g(X)=|X|$, $g(Y)=|Y|$, then $g((X\bigcup Y)-\{e\})<\infty$ for any $e\in X\bigcap Y$.

Inspired by Propositions 13 and 16, we can use the girth function in matroids to compute attribute reduction.

Theorem 2.

Let $IS=(U,A)$ be an information system. For all $B\subseteq A$, B is a reduct of $IS$ if and only if it satisfies the following two conditions:

(1) For all $b\in B$, there exists $X\subseteq U$ such that $g_{M(IND(B))}(X)\ne g_{M(IND(B-b))}(X)$.

(2) For all $X\subseteq U$, $g_{M(IND(B))}(X)=g_{M(IND(A))}(X)$.

Proof. 

According to Propositions 13 and 16, it is immediate. ☐

4.2. The Process of the Matroidal Methodology

In this subsection, we give the process of the matroidal approach to compute attribute reduction in information systems according to the equivalent description in Section 4.1.

In order to obtain all results of an information system $IS=(U,A)$, we need to compute $g_{M(IND(B))}(X)$ for all $B\subseteq A$ and $X\subseteq U$ based on Theorem 2. According to Definition 1, we know a reduct of $IS$ will not be ∅. Hence, we only consider $B\subseteq A$ and $B\ne \varnothing$. On the other hand, for all $X\subseteq U$ and $B\subseteq A$, if $|X|\le 1$, then $g_{M(IND(B))}(X)=g_{M(IND(A))}(X)$. According to Theorem 2, we only consider X whose $|X|\ge 2$. Therefore, the process is shown as follows:

• Input: An information system $IS=(U,A)$, where $U=\{u_1,u_2,\cdots ,u_n\}$ and $A=\{a_1,a_2,\cdots ,a_m\}.$
• Output: All results of $IS$.
• Step 1: Suppose $B_i\subset A$ ($B_i\ne \varnothing$ and $i=1,2,\cdots ,2^m-2$), we compute all $IND(B_i)$ and $IND(A)$.
• Step 2: For any $i=1,2,\cdots ,2^m-2$, we compute $g_{M(IND(B_i))}(X)$ and $g_{M(IND(A))}(X)$ for any $X\subseteq U$ and $|X|\ge 2$.
• Step 3: Obtain all results of $IS$ according to Theorem 2.

4.3. An Applied Example

Example 8.

Let us consider the following information system $IS=(U,A)$ as is shown in

Table 2. An information system.

	${\mathit{a}}_1$	${\mathit{a}}_2$	${\mathit{a}}_3$
$u_1$	0	1	0
$u_2$	1	2	2
$u_3$	1	0	0
$u_4$	2	1	1
$u_5$	1	1	2

.

Let $B_1=\{a_1\}$, $B_2=\{a_2\}$, $B_3=\{a_3\}$, $B_4=\{a_1,a_2\}$, $B_5=\{a_1,a_3\}$, $B_6=\{a_2,a_3\}$, $A=\{a_1,a_1,a_3\}$. $g_{B_i}$ denotes $g_{M(IND(B_i))}$ for $1\le i\le 6$ and $g_A$ denotes $g_{M(IND(A))}$. All girth functions induced by attribute subsets as is shown in

Table 3. Girth functions induced by attribute subsets.

	${\mathit{g}}_{{\mathit{B}}_1}$	${\mathit{g}}_{{\mathit{B}}_2}$	${\mathit{g}}_{{\mathit{B}}_3}$	${\mathit{g}}_{{\mathit{B}}_4}$	${\mathit{g}}_{{\mathit{B}}_5}$	${\mathit{g}}_{{\mathit{B}}_6}$	${\mathit{g}}_{\mathit{A}}$
$u_1,u_2$	∞	∞	∞	∞	∞	∞	∞
$u_1,u_3$	∞	∞	2	∞	∞	∞	∞
$u_1,u_4$	∞	2	∞	∞	∞	∞	∞
$u_1,u_5$	∞	2	∞	∞	∞	∞	∞
$u_2,u_3$	2	∞	∞	∞	∞	∞	∞
$u_2,u_4$	∞	∞	∞	∞	∞	∞	∞
$u_2,u_5$	∞	∞	2	∞	2	∞	∞
$u_3,u_4$	∞	∞	∞	∞	∞	∞	∞
$u_3,u_5$	∞	∞	∞	∞	∞	∞	∞
$u_4,u_5$	∞	2	∞	∞	∞	∞	∞
$u_1,u_2,u_3$	2	∞	2	∞	∞	∞	∞
$u_1,u_2,u_4$	∞	2	∞	∞	∞	∞	∞
$u_1,u_2,u_5$	∞	2	2	∞	2	∞	∞
$u_1,u_3,u_4$	∞	2	2	∞	∞	∞	∞
$u_1,u_3,u_5$	∞	2	2	∞	∞	∞	∞
$u_1,u_4,u_5$	∞	2	∞	∞	∞	∞	∞
$u_2,u_3,u_4$	2	∞	∞	∞	∞	∞	∞
$u_2,u_3,u_5$	2	∞	∞	∞	2	∞	∞
$u_2,u_4,u_5$	∞	2	2	∞	2	∞	∞
$u_3,u_4,u_5$	∞	2	∞	∞	∞	∞	∞
$u_1,u_2,u_3,u_4$	2	2	2	∞	∞	∞	∞
$u_1,u_2,u_3,u_5$	2	2	2	∞	2	∞	∞
$u_1,u_2,u_4,u_5$	∞	2	2	∞	2	∞	∞
$u_1,u_3,u_4,u_5$	∞	2	2	∞	∞	∞	∞
$u_2,u_3,u_4,u_5$	2	2	2	∞	2	∞	∞
$u_1,u_2,u_3,u_4,u_5$	2	2	2	∞	2	∞	∞

.

Accordingly, there are two reducts of $IS$: $B_4=\{a_1,a_2\}$ and $B_6=\{a_2,a_3\}$.

5. Conclusions

In this paper, we generalize four operators of rough sets to four operators of matroids through the interior axiom, the closure axiom, the exterior axiom and the boundary axiom, respectively. Moreover, we present a matroidal approach to compute attribute reduction in information systems. The main conclusions in this paper and the continuous work to do are listed as follows:

• There are four matroids induced by these four operators of rough sets. In fact, these four matroids are the same one, which implies the relationship about operators between rough sets and matroids. In this work, we assume an equivalence relation. However, there are other structures have been used in rough set theory, among them, tolerance relations [43], similarity relations [44], and binary relations [15,45]. Hence, they can suggest as a future research, the possibility of extending their ideas to these types of settings.
• The girth function of matroids is used to compute attribute reduction in information systems. This work can be viewed as a bridge linking matroids and information systems in the theoretical impact. In the practical impact, it is a novel method by which calculations will become algorithmic and can be implemented by a computer. Based on this work, we can use the girth function of matroids for attribute reduction in decision systems in the future.
• In the future, we will further expand the research content of this paper based on some new studies on neutrosophic sets and related algebraic structures [46,47,48,49,50].