A unified approach to reducts in dominance-based rough set approach

Abstract

The Dominance-based Rough Set Approach (DRSA), which is an extension of the Rough Set Approach (RSA), analyzes a sorting problem for a given data set. Attribute reduction is one of major topics in RSA as well as DRSA. By attribute reduction, we can find an important attribute set, which is called a reduct. In this paper, we propose a new approach to reducts in DRSA. A few kinds of reducts have been already proposed in DRSA, therefore, we clarify relations among the proposed and previous ones. We prove that they are consolidated into four kinds. Moreover, we show that all kinds of reducts can be enumerated based on two discernibility matrices.

1 Introduction

Rough sets (Pawlak 1982) have been applied to the analysis of decision tables, data tables composed of condition attributes describing objects (or items) and decision attribute showing classification results. Because of its usefulness, rough set approaches have been used in pattern recognition, machine learning, knowledge discovery, medical informatics, decision analysis, kansei engineering and so on (Słowiński 1992; Pawlak and Słowiński 1994; Polkowski and Skowron 1998; Greco et al. 2006). If objects take common condition attribute values, we cannot discern them by those condition attributes. When two or more indiscernible objects take different decision attribute values, the decision table is not consistent. In order to accommodate the inconsistency in the decision table, lower and upper approximations are introduced in a rough set approach. The lower and upper approximations in the classical rough sets are defined using such an indiscernibility relation which is an equivalence relation. In decision tables, the indiscernibility relation implies that all attributes are nominal. However, in the real world, we may face cases when some attribute values are ordinal. For example, consider two test scores as condition attributes and the comprehensive evaluation as the decision attribute, all attributes are ordinal. As in this example, we may sometimes suppose the monotonicity between the condition attributes and decision attribute.

When we suppose a monotonicity between the condition attributes and the decision attribute, the classical rough set approach developed for nominal attributes is not sufficient as demonstrated by Greco et al. (2001). To overcome this insufficiency, Greco et al. (2001) proposed the Dominance-based Rough Set Approach (DRSA). In DRSA, upward/downward unions of decision classes instead of decision classes are approximated based on a dominance relation instead of the indiscernibility relation. The similar analysis to the classical rough set analysis can be performed by DRSA.

Attribute reduction (Ślęzak 2000; Kryszkiewcz 2001; Inuiguchi and Tsurumi 2006) is one of major topics in the rough set approach and is also discussed in DRSA. As the result of attribute reduction, superfluous attributes are removed and we find important attributes as a set of condition attributes called a reduct. Therefore, attribute reduction can be applied to feature selection, evaluation of attribute importance, and so on. Susmaga et al. (2000) proposed reducts preserving an information measure called a quality of sorting. Shao and Zhang (2005) studied attribute reduction for an incomplete and consistent decision table. Yang et al. (2008) have proposed four kinds of reducts preserving lower/upper approximations of upward/downward unions of decision classes. Inuiguchi and Yoshioka (2008) have proposed several kinds of reducts preserving upper approximations, lower approximations, and/or boundary regions of upward and/or downward unions. The four kinds of reducts by Yang et al. (2008) are included in many kinds of reducts by Inuiguchi and Yoshioka (2008). Those are called union-based reducts because they do not consider the approximations of decision classes but those of upward/downward unions of decision classes. The relations among union-based reducts have been investigated in (Inuiguchi and Yoshioka 2008) but the relations between the kind of reducts proposed by Susmaga et al. (2000) and union-based reducts have not yet.

In this paper, we define lower and upper approximations and boundary regions of decision classes in DRSA and investigate reducts preserving those approximations and boundary regions. Because we consider the approximations of decision classes, we call them class-based reducts. We investigate the relations among the Susmaga’s reduct, union-based reducts and class-based reducts. Moreover, we propose a comprehensive method enumerating all kinds of reducts based on the discernibility matrices (Słowiński 1992). We show that all kinds of reducts can be enumerated by two discernibility matrices associated with generalized decisions (Dembczyáski et al. 2006).

In next section, DRSA and previous reducts are reviewed. In Sect. 3, approximations of decision classes in DRSA are defined and the reducts based on these approximations are proposed. Moreover, relations among many kinds of reducts are investigated. In Sect. 4, giving reducts based on generalized decisions, we show all kinds of reducts are enumerated by two discernibility matrices associated with generalized decisions. Finally, we describe conclusions in Sect. 5.

2 Dominance-based rough set approach and reducts

2.1 Dominance-based rough set approach (DRSA)

In DRSA (Greco et al. 2001; Susmaga et al. 2000), decision tables with order relations are analyzed. A decision table is defined by a quadruple ${{\mathcal{T}}}=\langle U,C\cup\{d\},V,f\rangle,$ where $U$ is a finite set of objects (universe), $C$ is a finite set of condition attributes, $d\not\in C$ is a decision attribute, $V_q$ is the domain of the attribute $q,$ $V=\bigcup_{q\in C\cup\{d\}}V_q$ is a set of attribute values and a total function $f: U\times C\cup\{d\}\rightarrow V$ such that $\forall x\in U,\forall q\in C\cup\{d\},f(x,q)\in V_q$ is called an information function. The attribute set $C\cup\{d\}$ is partitioned into $C^C\cup\{d\}$ and $C^A,$ where $C^C\cup\{d\}$ is the set of criteria and $C^A$ is the set of nominal attributes. For a criterion $q\in C^C\cup\{d\},$ we assume a weak order $\succeq_q$ on $U$ based on $V_q,$ where a weak order is a reflexive, transitive and complete. The relation $x\succeq_q y$ means “$x$ is at least as good as $y$ with respect to criteria $q$”. For $a\in C^A,$ we define $x=_a y\Leftrightarrow f(x,a) = f(y,a),$ then $=_a$ is an equivalence relation, i.e., reflexive, transitive and symmetric. As a background knowledge, we assume a monotonicity such that $x \succeq_q y$ for all $q \in C^C$ and $x=_a y$ for all $a\in C^A$ implies $x \succeq_d y.$

We generalize relations $\succeq$ and $=$ for condition attributes. For $q\in C,$ we define a relation $D_q$ by $xD_q y$ if and only if $x\succeq_q y,$ when $q\in P^C; x=_q y,$ when $q\in P^A.$ We note that the relation $D_p$ is preorder, i.e., reflexive and transitive. For $P\subseteq C,$ we define a dominance relation $D_p$ by $xD_P y$ if and only if $\forall q\in P, xD_q y,$ where $xD_P y$ implies that $x$ dominates $y$ with respect to $P.$ The decision attribute $d$ partitions $U$ into a set of decision classes ${{\mathcal{C}}}=\{Cl_1,Cl_2,{\ldots},Cl_n\}.$ For simplicity, we define $T=\{1,2,{\ldots},n\}.$ We assume $s > t$ if and only if $\forall x \in Cl_s,\ \forall y \in Cl_t, x \succ_d y.$

Remark 1

In this paper, we assume that the decision attribute set is a singleton in order to impose a total order on ${{\mathcal{C}}}$ as in Greco et al. (2001). When a decision attribute set includes more than one criteria, ${{\mathcal{C}}}$ becomes a partially ordered set. However, even in this case, a similar approach could be applied but the results would be more complex.

In DRSA, the following upward unions $Cl_t^{\ge}$ and downward unions $Cl_t^{\le}$ of decision classes are approximated by means of the dominance relation:

$$ Cl_t^{\ge}=\bigcup_{k\ge t}Cl_k, \quad Cl_t^{\le}=\bigcup_{k\le t}Cl_k,\ t \in T. $$

(1)

We have $Cl_1^{\geq}=Cl_n^\leq=U, Cl_tx^{\geq}=U-Cl_{t-1}^\leq (t \geq 2).$ Using dominance relation $D_P(P \subseteq C),$ $P$-dominating set and $P$-dominated set are, respectively, defined by

$$ D_P^+(x)=\{y\in U|y D_P x\}, $$

(2)

$$ D_P^-(x)=\{y\in U|x D_P y\}. $$

(3)

$P$ -lower and $P$ -upper approximations of $Cl_t^{\geq}$ are respectively defined by

$$ \underline{P}(Cl_t^{\geq}) = \{x\in U|D_P^+(x)\subseteq Cl_t^{\ge}\}, $$

(4)

$$ \overline{P}(Cl_t^{\ge})= \{x\in U|D_P^-(x)\cap Cl_t^{\ge}\neq \emptyset\}. $$

(5)

Similarly, $P$ -lower and $P$ -upper approximations of $Cl_t^{\le}$ are defined by

$$ \underline{P}(Cl_t^{\le})= \{x\in U|D_P^-(x)\subseteq Cl_t^{\le}\}, $$

(6)

$$ \overline{P}(Cl_t^{\le})=\{x\in U|D_P^+(x)\cap Cl_t^{\le}\neq \emptyset\}. $$

(7)

If $x$ belongs to $\underline{P}(Cl_t^{\ge}),$ then all objects dominating $x$ do not belong to $Cl_{t-1}^\le,$ i.e., there exists no evidence for $x\in Cl_{t-1}^\le$ on the monotonicity assumption. Therefore, we can say that $x$ certainly belongs to $Cl_t^{\ge}.$ On the other hand, if $x$ belongs to $\overline{P}(Cl_t^{\ge})$ then $x$ is dominating an object belonging to $Cl_t^\ge,$ i.e., there exists at least an evidence for $x\in Cl_t^\ge$ on the monotonicity assumption. Therefore, we can say that $x$ possibly belongs to $Cl_t^{\ge}.$ The similar interpretations can be applied to $\underline{P}(Cl_t^{\le})$ and $\overline{P}(Cl_t^{\le}).$

The difference between the upper and lower approximations is called a boundary region, the boundary regions $Bn_P(Cl_t^{\ge})$ and $Bn_P(Cl_t^{\le})$ are defined by

$$ Bn_P(Cl_t^{\ge}) = \overline{P}(Cl_t^{\ge})-\underline{P}(Cl_t^{\ge}),\\ $$

(8)

$$ Bn_P(Cl_t^{\le}) = \overline{P}(Cl_t^{\le})-\underline{P}(Cl_t^{\le}). $$

(9)

The objects in the boundary region of an upward or downward union are classified neither to that union nor to the complement with certain.

2.2 Properties of upper and lower approximations

Let $P\subseteq C$ and $t\in T.$ Then the upper and lower approximations and boundary regions satisfy the following properties (Greco et al. 2001, 2005):

$$ \overline{P}(Cl_1^{\ge})=\underline{P}(Cl_1^{\ge})=U, \overline{P}(Cl_n^{\le})=\underline{P}(Cl_n^{\le})=U, $$

(10)

$$ \underline{P}(Cl_t^{\ge})\subseteq Cl_t^{\ge}\subseteq \overline{P}(Cl_t^{\ge}), $$

(11)

$$ \underline{P}(Cl_t^{\le})\subseteq Cl_t^{\le} \subseteq \overline{P}(Cl_t^{\le}), $$

(12)

$$ \overline{P}(Cl_t^{\ge})=U-\underline{P}(Cl_{t-1}^{\le}),\quad (t \geq 2), $$

(13)

$$ \overline{P}(Cl_{t-1}^{\le})=U-\underline{P}(Cl_{t}^{\ge}), \quad (t \geq 2), $$

(14)

$$ \overline{P}(Cl_t^{\ge})\cup \overline{P}(Cl_{t-1}^{\le})= U, \quad (t \geq 2), $$

(15)

$$ Bn_P(Cl_t^{\ge})=Bn_P(Cl_{t-1}^{\le}), \quad (t \geq 2), $$

(16)

$$ \overline{P}(Cl_t^{\ge})=Bn_P(Cl_t^{\ge})\cup Cl_t^{\ge}, $$

(17)

$$ \overline{P}(Cl_t^{\le})=Bn_P(Cl_t^{\le})\cup Cl_t^{\le}, $$

(18)

$$ \underline{P}(Cl_t^{\ge})=Cl_t^{\ge}-Bn_P(Cl_t^{\ge}), $$

(19)

$$ \underline{P}(Cl_t^{\le})=Cl_t^{\le}-Bn_P(Cl_t^{\le}). $$

(20)

Let $P,Q \subseteq C$ and $s,t \in T.$ Then, we have the following monotonicity properties:

$$ s\ge t\Rightarrow \underline{P}(Cl_s^{\ge})\subseteq \underline{P}(Cl_t^{\ge}), \quad \overline{P}(Cl_s^{\ge})\subseteq \overline{P}(Cl_t^{\ge}), $$

(21)

$$ s\le t\Rightarrow \underline{P}(Cl_s^{\le})\subseteq \underline{P}(Cl_t^{\le}),\quad \overline{P}(Cl_s^{\le})\subseteq \overline{P}(Cl_t^{\le}), $$

(22)

$$ Q\subseteq P \Rightarrow \underline{Q}(Cl_t^{\ge})\subseteq \underline{P}(Cl_t^{\ge}), \quad \underline{Q}(Cl_t^{\le})\subseteq \underline{P}(Cl_t^{\le}), $$

(23)

$$ Q\subseteq P \Rightarrow \overline{Q}(Cl_t^{\ge})\supseteq \overline{P}(Cl_t^{\ge}), \quad \overline{Q}(Cl_t^{\le})\supseteq \overline{P}(Cl_t^{\le}). $$

(24)

2.3 Generalized decision

The generalized decision proposed by Dembczyński et al. (2006) plays an important role in discernibility matrices described in Sect. 4. Let $P\subseteq C$ and $x\in U, P$ -generalized decision $\delta_P(x)$ is defined by $\delta_P(x)=\langle l_P(x), u_P(x)\rangle,$ where we define

$$ l_P(x)=\hbox{min}\{t\in T | D_P^+(x)\cap Cl_t\neq\emptyset\}, $$

(25)

$$ u_P(x)=\hbox{max}\{t\in T | D_P^-(x)\cap Cl_t\neq\emptyset\}. $$

(26)

$\delta_P(x)$ shows the interval of decision classes to which $x$ may belong. $l_P(x)$ and $u_P(x)$ are the lower and upper bounds of the interval. Obviously, we have

$$ l_P(x)\le u_P(x). $$

(27)

$l_P(x)$ and $u_P(x)$ are monotone with respect to the inclusion relation between condition attribute sets. Namely, for $Q,P\subseteq C$ and $x\in U,$ we have

$$ Q\subseteq P\Rightarrow l_Q(x)\le l_P(x), u_Q(x)\ge u_P(x). $$

(28)

Using $\delta_P(x),$ the lower and upper approximations are represented as

$$ \underline{P}(Cl_t^{\ge}) = \{x\in U|l_P(x)\ge t\}, $$

(29)

$$ \underline{P}(Cl_t^{\le}) = \{x\in U|u_P(x)\le t\}, $$

(30)

$$ \overline{P}(Cl_t^{\ge}) = \{x\in U|u_P(x)\ge t\}, $$

(31)

$$ \overline{P}(Cl_t^{\le}) = \{x\in U|l_P(x)\le t\}. $$

(32)

2.4 Previous reducts in DRSA

Attribute reduction (Ślęzak 2000; Kryszkiewcz 2001; Inuiguchi and Tsurumi 2006) is one of major topics in the rough set approach. By the method, superfluous attributes are removed, so that we may find important attributes as a set of attributes called a reduct. According to many facets of consistency, various kinds of reducts have been proposed in the rough set approach.

In DRSA, a few approaches to attribute reduction have been already proposed. Susmaga et al. (2000) proposed the kind of reducts preserving the quality of sorting $\gamma_P({{\mathcal{C}}}),$ where for $P\subseteq C, \gamma_P({{\mathcal{C}}})$ is defined by

$$ \begin{aligned} \gamma_P({{\mathcal{C}}}) &=\frac{|U-\bigcup_{t\in T}Bn_P(Cl^{\le}_t)|}{|U|}\\ &=\frac{|U-\bigcup_{t\in T}Bn_P(Cl^{\ge}_t)|}{|U|}. \end{aligned} $$

(33)

In this paper, we call this reduct a Q-reduct. Yang et al. (2008) proposed four kinds of reducts for an incomplete decision table with dominance relation. They are reducts preserving lower/upper approximations of upward/downward unions. Inuiguchi and Yoshioka (2008) proposed several kinds of reducts and investigated their relations. They are reducts preserving only lower approximations, only upper approximations, both lower and upper approximations and boundary regions of upward/downward unions. Inuiguchi and Yoshioka showed that they are only three different kinds. Four kinds of reducts by Yang et al. (2008) are same as four kinds of reducts by Inuiguchi and Yoshioka (2008). Since those reducts are based on upward and downward unions, they are called union-based reducts (Inuiguchi and Yoshioka 2008).

Let us show the definitions of the previously proposed reducts.

Definition 1

(Q-reduct) A set $P\subseteq C$ is called a Q-reduct if and only if

• (Q1) $\gamma_P({{\mathcal{C}}})=\gamma_C({{\mathcal{C}}})$ and

• (Q2) ${\not\!\exists} Q\subset P$ such that $\gamma_Q({{\mathcal{C}}})=\gamma_P({{\mathcal{C}}}).$

Definition 2

($\hbox{L}^{\ge}$-reduct) A set $P\subseteq C$ is called an $\hbox{L}^{\ge}$-reduct if and only if

• $(\hbox{L1}^{\ge})$$\underline{P}(Cl_t^{\ge}) = \underline{C}(Cl_t^{\ge})$ for all $t\in T,$ and

• $(\hbox{L2}^{\ge})$${\not\!\exists} Q\subset P$ such that $\underline{Q}(Cl_t^{\ge}) = \underline{P}(Cl_t^{\ge})$ for all $t\in T.$

Definition 3

($\hbox{L}^{\le}$-reduct) A set $P\subseteq C$ is called an $\hbox{L}^{\le}$-reduct if and only if

• $(\hbox{L1}^{\le})$$\underline{P}(Cl_t^{\le}) = \underline{C}(Cl_t^{\le})$ for all $t\in T,$ and

• $(\hbox{L2}^{\le})$${\not\!\exists} Q\subset P$ such that $\underline{Q}(Cl_t^{\le})=\underline{P}(Cl_t^{\le})$ for all $t\in T.$

Definition 4

($\hbox{L}^{\diamond}$-reduct) A set $P\subseteq C$ is called an $\hbox{L}^{\diamond}$-reduct if and only if

• $(\hbox{L1}^{\diamond})$$\underline{P}(Cl_t^{\ge}) = \underline{C}(Cl_t^{\ge}),$$\underline{P}(Cl_t^{\le}) = \underline{C}(Cl_t^{\le})$ for all $t\in T,$ and

• $(\hbox{L2}^{\diamond})$${\not\!\exists} Q\subset P$ such that $\underline{Q}(Cl_t^{\ge}) = \underline{P}(Cl_t^{\ge}),\underline{Q}(Cl_t^{\le}) = \underline{P}(Cl_t^{\le})$ for all $t\in T.$

As shown in Inuiguchi and Yoshioka (2008), we have the following proposition.

Proposition 1

If$P$is an$\hbox{L}^{\diamond}$-reduct then$P$satisfies$(\hbox{L}1^{\ge})$and$(\hbox{L1}^{\le}).$

3 Class-based reducts in DRSA

3.1 Approximations of decision classes

In this section, we propose a few new concepts of reducts, called class-based reducts. Before giving the definitions, we need to define lower and upper approximations and boundary regions of decision classes.

Definition 5

For $P\subseteq C$ and $t\in T,$ lower and upper approximations of $Cl_t$ and the boundary region of $Cl_t$ are defined by

$$ \underline{P}(Cl_t) = \underline{P}(Cl_t^{\ge})\cap \underline{P}(Cl_t^{\le}), $$

(34)

$$ \overline{P}(Cl_t) = \overline{P}(Cl_t^{\ge})\cap \overline{P}(Cl_t^{\le}), $$

(35)

$$ Bn_{P}(Cl_t) = \overline{P}(Cl_t)-\underline{P}(Cl_t). $$

(36)

This definition is analogy to $Cl_t=Cl_t^\ge\cap Cl_t^\le.$

We can represent approximations of classes using the generalized decision as shown in the following proposition.

Proposition 2

For $P\subseteq C$ and $t\in T,$ we have

$$ \underline{P}(Cl_t) = \{x\in U|l_P(x)=u_P(x)=t\}, $$

(37)

$$ \overline{P}(Cl_t) = \{x\in U|l_P(x)\le t\le u_P(x)\}, $$

(38)

$$ Bn_P(Cl_t)=\left\{x\in U\left| \begin{array}{l} l_P(x)\le t\le u_P(x),\\ l_P(x) < u_P(x) \end{array}\right.\right\}. $$

(39)

Proof

We can easily prove those equations by Eqs.27 and 29–32.$\square$

The following proposition shows connections between approximations of unions and classes.

Proposition 3

For $P\subseteq C$ and $t\in T,$ we have

$$ \overline{P}(Cl_t^{\ge})=\bigcup_{k\ge t,k\in T} \overline{P}(Cl_k), $$

(40)

$$ \overline{P}(Cl_t^{\le})=\bigcup_{k\le t,k\in T} \overline{P}(Cl_k), $$

(41)

$$ Bn_P(Cl_t)=Bn_P(Cl_t^{\ge})\cup Bn_P(Cl_t^{\le}). $$

(42)

Proof

We prove of Eq. 41 by induction. When $t=1,$ $\overline{P}(Cl_1^{\le})=\overline{P}(Cl_1)$ holds. When $t=s < n,$ we suppose $\overline{P}(Cl^{\le}_s)=\bigcup_{k\le s,k\in T}\overline{P}(Cl_k)$ holds then

$$ \begin{aligned} &\bigcup\;_{k\le{s+1}}\overline{P}(Cl_k)\\ &=\overline{P}(Cl_s^{\le})\cup\overline{P}(Cl_{s+1})\\ &=\overline{P}(Cl_s^{\le})\cup (\overline{P}(Cl_{s+1}^{\ge}) \cap\overline{P}(Cl_{s+1}^{\le})) \\ &=(\overline{P}(Cl_s^{\le})\cup\overline{P}(Cl_{s+1}^{\ge})) \cap(\overline{P}(Cl_s^{\le})\cup\overline{P}(Cl_{s+1}^{\le})). \end{aligned} $$

By Eqs. 15 and 22, $\bigcup_{k\le{s+1}}\overline{P}(Cl_k)=\overline{P}(Cl_{s+1}^{\le})$ holds. Therefore, we have proved Eq. 41. The Eq. 40 can be shown in the same way.

We prove Eq. 42. By Eqs. 29–32, $Bn_P(Cl_t^\geq) =\{ x \in U \mid l_P(x) < t \leq u_P(x) \}$ and $Bn_P(Cl_t^\leq) =\{ x \in U \mid l_P(x) \leq t < u_P(x) \}.$ Then, from Eq. 39, $Bn_P(Cl_t^\geq) \cup Bn_P(Cl_t^\leq)=\{ x \in U \mid l_P(x) \leq t \leq u_P(x),\ l_P(x) < u_P(x) \}=Bn_P(Cl_t).$ $\square$

The properties of approximations of classes are shown in the following proposition.

Proposition 4

For $P\subseteq C$ and $t\in T,$ we have

$$ \underline{P}(Cl_t)\subseteq Cl_t\subseteq \overline{P} (Cl_t), $$

(43)

$$ \overline{P}(Cl_t)=Bn_P(Cl_t)\cup Cl_t, $$

(44)

$$ \underline{P}(Cl_t)=Cl_t-Bn_P(Cl_t), $$

(45)

$$ \underline{P}(Cl_t)=U-\bigcup_{k\neq t,k\in T}\overline{P}(Cl_k), $$

(46)

$$ U-\bigcup_{k\in T}\underline{P}(Cl_k)=\bigcup_{k\in T}Bn_{P}(Cl_k), $$

(47)

$$ Bn_P(Cl_t)=\overline{P}(Cl_t)\cap\bigcup_{k\neq t,k\in T} \overline{P}(Cl_k). $$

(48)

Proof

We prove Eqs. 46–48 only. The others can be shown straightforwardly. We prove Eq. 46. Applying De Morgan’s law, Eqs. 40 and 41 to the definition, we obtain $\underline{P}(Cl_t) =\underline{P}(Cl_t^{\le})\cap\underline{P}(Cl_t^{\ge}) = U-\overline{P}(Cl_{t+1}^{\ge})\cup\overline{P}(Cl_{t-1}^{\le}) =U-\bigcup_{k\neq t}\overline{P}(Cl_k).$ We prove Eq. 47. Applying Eqs. 15, 40, 41 and De Morgan’s law, we obtain

$$ \begin{aligned} U-\bigcup_{k\in T}\underline{P}(Cl_k) &=\bigcup_{k\in T}\overline{P}(Cl_k) -\bigcup_{k\in T}\underline{P}(Cl_k)\\ &=\bigcup_{k\in T}\overline{P}(Cl_k) \cap\bigcap_{k\in T}(U-\underline{P}(Cl_k))\\ &=\bigcup_{k\in T}(\overline{P}(Cl_k) \cap\bigcap_{l\in T}(U-\underline{P}(Cl_l))). \end{aligned} $$

By Eq. 46, we obtain $\overline{P}(Cl_k)\subseteq U-\underline{P}(Cl_l)$ for $l\neq k.$ Therefore,

$$ \begin{aligned} U-\bigcup_{k\in T}\underline{P}(Cl_k) &=\bigcup_{k\in T}(\overline{P}(Cl_k)\cap (U-\underline{P}(Cl_k)))\\ &=\bigcup_{k\in T}(\overline{P}(Cl_k)-\underline{P}(Cl_k))\\ &=\bigcup_{k\in T}Bn_P(Cl_k). \end{aligned} $$

Finally, we prove Eq. 48. By Eq. 46, we have $Bn_P(Cl_t)=\overline{P}(Cl_t) - \underline{P}(Cl_t) = \overline{P}(Cl_t)-(U-\bigcup_{k\neq t,k\in T}\overline{P}(Cl_k)) = \overline{P}(Cl_t)\cap\bigcup_{k\neq t,k\in T}\overline{P}(Cl_k).$ $\square$

Moreover, the approximations are also monotone with respect to the inclusion relation between condition attribute sets.

Proposition 5

For $P,Q \subseteq C$ and $t\in T,$ we have

$$ Q\subseteq P\Rightarrow \underline{Q}(Cl_t)\subseteq \underline{P}(Cl_t), \overline{Q}(Cl_t)\supseteq \overline{P}(Cl_t). $$

(49)

Proof

This can be shown by Eqs. 23 and 24. $\square$

3.2 Class-based reducts

Now, we are ready to define new kinds of reducts. The first kind of reducts, called L-reduct, preserves the lower approximations of decision classes, the second kind reduct, called U-reduct, preserves the upper approximations of decision classes, and the third kind of reduct, called B-reduct, preserves the boundary regions of decision classes. They are defined formally as follows.

Definition 6

(L-reduct) A set $P\subseteq C$ is called an L-reduct if and only if

• (L1) $\underline{P}(Cl_t) = \underline{C}(Cl_t)$ for all $t\in T,$ and

• (L2) ${\not\!\exists} Q\subset P$ such that $\underline{Q}(Cl_t)= \underline{P}(Cl_t)$ for all $t\in T.$

Definition 7

(U-reduct) A set $P\subseteq C$ is called a U-reduct if and only if

• (U1) $\overline{P}(Cl_t) = \overline{C}(Cl_t)$ for all $t\in T,$ and

• (U2) ${\not\!\exists} Q\subset P$ such that $\overline{Q}(Cl_t) = \overline{P}(Cl_t)$ for all $t\in T.$

Definition 8

(B-reduct) A set $P\subseteq C$ is called a B-reduct if and only if

• (B1) $Bn_{P}(Cl_t) = Bn_{C}(Cl_t)$ for all $t\in T,$ and

• (B2) ${\not\!\exists} Q\subset P$ such that $Bn_{Q}(Cl_t) = Bn_{P}(Cl_t)$ for all $t\in T.$

Those concepts are parallel to L-, U- and B-reducts (Inuiguchi and Tsurumi 2006) discussed in the setting of the classical rough sets.

From the properties of approximations, we have the following theorem.

Theorem 1

We have the following assertions:

• (a) If $P$ is a U-reduct then $P$ satisfies (L1).

• (b) $P$is a U-reduct if and only if$P$is a B-reduct.

Proof

We first prove (a). It suffices to prove that (U1) implies (L1). Suppose a condition attribute set $P$ satisfies (U1). Then by Eq. 46, $\underline{P}(Cl_t) = U-\bigcup_{k\neq t,k\in T}\overline{P}(Cl_k) = U-\bigcup_{k\neq t,k\in T}\overline{C}(Cl_k)=\underline{C}(Cl_t),$ where $t\in T.$ Next, we prove (b). It suffices to show that (U1) and (B1) are equivalent. It can be obtained from Eqs. 44 and 48 in the similar way to the proof of (a).$\square$

Consequently, we have only two kinds of class-based reducts: L-reduct and U-reduct (or B-reduct). This result is parallel to the result in the classical rough sets (Inuiguchi and Tsurumi 2006).

Let us discuss relations of the proposed class-based reducts and the previous reducts introduced in Sect. 2.4. We have the following theorems.

Theorem 2

$P$is an L-reduct if and only if$P$is a Q-reduct.

Proof

By Eqs. 16 and 42, $Bn_P(Cl_t)=Bn_P(Cl^{\le}_{t-1})\cup Bn_P(Cl^{\le}_{t}).$ Thus, $\bigcup_{t\in T}Bn_P(Cl_t)=\bigcup_{t\in T}Bn_P(Cl^{\le}_t).$ From Eq. 47, the quality of sorting $\gamma_P({{\mathcal{C}}})$ equals to the union of the lower approximations $\bigcup_{t\in T}\underline{P}(Cl_t).$ So it suffices to show $\left|\bigcup_{t\in T}\underline{P}(Cl_t)\right|= \left|\bigcup_{t\in T}\underline{C}(Cl_t)\right|$ if and only if $\forall t\in T, \underline{P}(Cl_t)=\underline{C}(Cl_t).$ From Eq. 43, $\underline{Q}(Cl_t)$ and $\underline{Q}(Cl_s)$ are disjoint for any $t,s \in T$ such that $t \neq s$ and for any $Q \subseteq C.$ Then, we have $\left|\bigcup_{t\in T}\underline{Q}(Cl_t)\right| = \sum_{t\in T}|\underline{Q}(Cl_t)|$ for $Q=P,C.$ From this and Eq. 49, we obtain $\left|\bigcup_{t\in T}\underline{P}(Cl_t)\right| = \left|\bigcup_{t\in T}\underline{C}(Cl_t)\right|$ if and only if $\forall t\in T, |\underline{P}(Cl_t)| = |\underline{C}(Cl_t)|$ which is equivalent to $\forall t\in T, \underline{P}(Cl_t) = \underline{C}(Cl_t).$ $\square$

Theorem 3

$P$is a U-reduct if and only if$P$is an$\hbox{L}^{\diamond}$-reduct.

Proof

This is easily obtained from Eqs. 13, 14, 35, 40 and 41.$\square$

As a result, all kinds of reducts proposed in DRSA are arranged in Fig. 1. Consequently, there exist four different kinds of reducts, i.e., U-reduct (or B-reduct or $\hbox{L}^\diamond$-reduct), L-reduct (or Q-reducts), $\hbox{L}^\ge$-reduct and $\hbox{L}^\le$-reduct in DRSA.

Fig. 1

Relations of reducts in DRSA

4 A unified approach to discernibility matrices

4.1 Reducts based on generalized decisions

A discernibility matrix is a popular approach to enumerate of all reducts in the rough set approach. For $\hbox{L}^{\geq}$-, $\hbox{L}^{\leq}$- and $\hbox{L}^{\diamond}$-reducts, suitable discernibility matrices have successfully proposed in (Inuiguchi and Yoshioka 2008; Yang et al. 2008). For Q-reduct, a similar approach to a discernibility matrix has been proposed in (Susmaga et al. 2000). Therefore, all kinds of reducts in DRSA can be enumerated by those previous approaches.

In this section, we propose alternative discernibility matrices for enumerations of all kinds of reducts. In the proposed approach, calculations of lower and upper approximations of downward and upward unions are not required but those of generalized decisions of all objects. The latter is a simpler formulation and would require less computation effort than the former. Moreover, we can treat all kinds of reducts comprehensively in the proposed approach.

We introduce some kinds of reducts based on generalized decisions.

Definition 9

($\delta$-reduct) A set $P\subseteq C$ is called a $\delta$-reduct if and only if

• $(\delta 1)$$\forall x\in U, \delta_P(x)=\delta_C(x)$ and

• $(\delta 2)$${\not\!\exists} Q\subset P$ such that $\forall x\in U, \delta_Q(x)=\delta_P(x).$

Definition 10

($\hbox{L}\delta$-reduct) A set $P\subseteq C$ is called an $\hbox{L}\delta$-reduct if and only if

• ($\hbox{L}\delta1)\forall x\in U, l_C(x)=u_C(x)$ implies $\delta_P(x)=\delta_C(x)$ and

• $(\hbox{L}\delta 2)$$\not\!\exists Q\subset P$ such that $\forall x\in U,$$l_C(x)=u_C(x)$ implies $\delta_Q(x)=\delta_P(x).$

Definition 11

($l$-reduct) A set $P\subseteq C$ is called an $l$-reduct if and only if

• $(l1)$$\forall x\in U,$$l_P(x)=l_C(x)$ and

• $(l2)$$\not\!\exists Q\subset P$ such that $\forall x\in U,$$l_Q(x)=l_P(x).$

Definition 12

($U$-reduct) A set $P\subseteq C$ is called a $U$-reduct if and only if

• $(u1)$$\forall x\in U,$$u_P(x)=u_C(x)$ and

• $(u2)$$\not\!\exists Q\subset P$ such that $\forall x\in U,$$u_Q(x)=u_P(x).$

We obtain the following theorem, which implies that four kinds of reducts in Fig. 1 can be represented by using generalized decisions.

Theorem 4

We have the following assertions:

• (a) $P$is a$\delta$-reduct if and only if$P$is a U-reduct, i.e., an$\hbox{L}^\diamond$-reduct.

• (b) $P$is an$\hbox{L}\delta$-reduct if and only if$P$is an L-reduct, i.e., a Q-reduct.

• (c) $P$is an$l$-reduct if and only if$P$is an$\hbox{L}^\geq$-reduct.

• (d) $P$is a$U$-reduct if and only if$P$is an$\hbox{L}^\leq$-reduct.

Proof

We prove only (b) since (a), (c) and (d) can be shown easily from Eqs. 29 and 30. It suffices to prove that $(\hbox{L}\delta 1)$ is equivalent to (L1). From Eq. 37, $(\hbox{L}\delta 1)$ if and only if $\forall t\in T, \underline{C}(Cl_t)\subseteq \underline{P}(Cl_t)$ which is (L1).$\square$

4.2 Discernibility matrices

Let $y\neg D_qx$ stand for $yD_qx$ does not hold for $q\in C,$ then we first obtain the following lemma.

Lemma 1

Let $x \in U,$ then we have the following equivalences:

$$ \begin{aligned} &l_P(x)=l_C(x)\;\hbox{if and only if}\\ &\forall y\in U, (l_C(y) < l_C(x)\;\hbox{implies}\; \exists q\in P, y\neg D_q x),\\ \end{aligned} $$

(50)

$$ \begin{aligned} &u_P(x)=u_C(x)\;\hbox{if and only if}\\ &\forall y\in U,(u_C(y) > u_C(x)\;\hbox{implies}\; \exists q\in P,x\neg D_q y). \end{aligned} $$

(51)

Proof

We prove only Eq. 50. The other can be shown in the same way.

First, under the supposition $\forall y\in U,(l_C(y) < l_C(x)$ implies $\exists q\in P, y\neg D_q x),$ we prove $l_C(x)\le l_P(x)$ by contradiction. Assume $l_C(x) > l_P(x),$ then there exists $y\in D_P^+(x)\cap Cl_{l_P(x)}.$ The fact $y\in Cl_{l_P(x)}$ and the reflexivity of $D_p$ $(y \in D_P^+(y))$ implies $l_C(y)\le l_P(x).$ From this and the assumption $l_C(x) > l_P(x),$ we have $l_C(y) < l_C(x).$ On the other hand, $y \in D_P^+(x)$ i.e., $yD_Px,$ i.e., $\forall q \in P, yD_q x.$ Facts $l_C(y) < l_C(x)$ and $yD_Px$ contradict the supposition. Consequently, we have $l_C(x)\le l_P(x).$ Moreover, from Eq. 28, $l_P(x)\le l_C(x)$ is equivalent to $l_C(x)=l_P(x).$

Next we prove the converse. Suppose $l_P(x)=l_C(x).$ Assume there exists $y \in U$ such that $l_C(y) < l_C(x)$ and $yD_P x.\;yD_P x$ implies $D_P^+(y) \subseteq D_P^+(x).$ By definition, this further implies $l_P(y) \geq l_P(x).$ Then, under the assumption, we have $l_C(y) < l_C(x)=l_P(x)\leq l_P(y).$ This contradicts Eq. 28. Then we have $l_C(y) < l_C(x)$ implies $\exists q \in P, y {\neg D_q} x$ for all $y \in U.$ $\square$

Now we are ready to define discernibility matrices. The $l$-discernibility matrix $M^{l}$ and $u$-discernibility matrix $M^{u}$ are defined as follows.

Definition 13

The $l$-discernibility matrix $M^{l}=(m_{ij}^{l}),$ where ${i,j=1,{\ldots},|U|},$ is composed of $(i,j)$-components $m_{ij}^{l}$ defined by

$$ m_{ij}^l= \left\{ \begin{array}{ll} \{q\in C|x_j\neg D_q x_i\}& \hbox{if}\; l_C(x_j) < l_C(x_i),\\ C& \hbox{otherwise}. \end{array} \right. $$

(52)

On the other hand, the $u$-discernibility matrix $M^{u}=(m_{ij}^{u})_{i,j=1,{\ldots},|U|}$ is composed of $(i,j)$-components $m_{ij}^u$ defined by

$$ m_{ij}^u= \left\{ \begin{array}{ll} \{q\in C|x_i\neg D_q x_j\}&\hbox{if}\;u_C(x_j) > u_C(x_i),\\ C& \hbox{otherwise}. \end{array} \right. $$

(53)

Based on $M^l$ and $M^u,$ we define four discernibility functions.

Definition 14

Let $\tilde{q}_i^P$ be a Boolean variable pertaining to a condition attribute $q_i$ and a condition attribute set $P$ defined by

$$ \tilde{q}_i^P= \left\{ \begin{array}{cl} \hbox{true} & \hbox{if}\;q_i\in P,\\ \hbox{false} & \hbox{otherwise}. \end{array} \right. $$

(54)

Then, we define the following Boolean functions $F^\geq, F^\leq, F^{\rm U}$ and $F^{\rm L}:$

$$F^\geq (\tilde{q}_1^P,{\ldots},\tilde{q}_{|C|}^P) = \bigwedge_{1\le i,j\le |U|} \bigvee_{q\in m_{ij}^{l}} \tilde{q}^P, $$

(55)

$$ F^\leq(\tilde{q}_1^P,{\ldots},\tilde{q}_{|C|}^P)= \bigwedge_{1\le i,j\le |U|} \bigvee_{q\in m_{ij}^{u}} \tilde{q}^P, $$

(56)

$$ F^{\rm U}(\tilde{q}_1^P,{\ldots},\tilde{q}_{|C|}^P)= \bigwedge_{1 \le i,j \le |U|} \bigvee_{q\in m_{ij}^{l}} \tilde{q}^P $$

(57)

$$\wedge \bigwedge_{1 \le i,j \le |U|} \bigvee_{q\in m_{ij}^{u}} \tilde{q}^P,$$

(58)

$$\begin{aligned} F^{\rm L}(\tilde{q}_1^P,{\ldots},\tilde{q}_{|C|}^P)&= \bigwedge_{i: l_C(x_i)=u_C(x_i)} \bigwedge_{1 \le j\le |U|} \bigvee_{q\in m_{ij}^{l}} \tilde{q}^P\\ &\wedge \bigwedge_{i: l_C(x_i)= u_C(x_i)} \bigwedge_{1 \le j\le |U|} \bigvee_{q\in m_{ij}^{u}} \tilde{q}^P.\\ \end{aligned}$$

(59)

From Lemma 1, we have the following theorem.

Theorem 5

We have the following equivalences:

$$ \begin{aligned} &P \subseteq C\;\hbox{satisfies}\;(\hbox{L}1^\geq),\hbox{i.e}.,(l1).\\ &\hbox{if and only if}\;F^{\geq}(\tilde{q}_{1}^P,{\ldots} ,\tilde{q}_{|C|}^P)=\hbox{true}, \end{aligned} $$

(60)

$$ \begin{aligned} &P \subseteq C\;\hbox{satisfies}\;(\hbox{L}1^\leq), \hbox{i.e}.,(u1)\\ &\hbox{if and only if}\;F^\leq(\tilde{q}_1^P,{\ldots},\tilde{q}_{|C|}^P)= \hbox{true},\\ \end{aligned} $$

(61)

$$ \begin{aligned} &P \subseteq C\;\hbox{satisfies}\;(\text {U}1),\hbox{i.e}., (\hbox{L}\delta1)\\ &\hbox{if and only if}\;F^{\rm U}(\tilde{q}_1^P,{\ldots},\tilde{q}_{|C|}^P) =\hbox{true},\\ \end{aligned} $$

(62)

$$ \begin{aligned} &P \subseteq C \; \hbox{satisfies} \;(\text L1), \hbox{i.e}., (\delta 1)\\ &\hbox{if and only if}\;F^{\rm L}(\tilde{q}_1^P,{\ldots},\tilde{q}_{|C|}^P) =\hbox{true}. \end{aligned} $$

(63)

Proof

First three equivalences are obvious by Lemma 1 and definitions of Boolean functions. The last one needs to show that any object $x$ such that $l_C(x) < u_C(x)$ never satisfies $l_P(x)=u_P(x).$ This is clear from Eq. 28.$\square$

From Theorem 5, all $\hbox{L}^\geq$-, $\hbox{L}^\leq$-, U- and L-reducts can be obtained as all prime implicants of Boolean functions $F^\geq,F^\leq, F^{\rm U}$ and $F^{\rm L},$ respectively.

The proposed discernibility matrices have two advantages comparing to the previous ones. One is the computational efficiency. We need to calculate neither lower, upper approximations nor boundary regions of unions but only the lower bounds $l_C$ and the upper bounds $u_C$ of all objects. Namely, the computation of the proposed approach is free from the number of decision classes. The other advantage is that the all Boolean functions with respect to $\hbox{L}^{\ge}$-reduct, $\hbox{L}^{\le}$-reduct, U-reduct and L-reduct are obtained from only two discernibility matrices.

Example 1

Consider a decision table given in Table 1. This table shows student evaluation in a school. Objects are seven students, i.e., $U=\{ S_1,\ S_2,{\ldots},S_7\}.$ Condition attributes are scores of mathematics (Ma), physics (Ph) and literature (Li), while decision attribute $(d)$ is a comprehensive evaluation (E). Namely, $C=\{\hbox{Ma},\hbox{Ph},\hbox{Li} \}.$ We may assume that the better scores in all subjects student takes, the better comprehensive evaluation he/she gets. The lower bounds $l_C$ and the upper bounds $u_C$ of objects are shown in the rightmost two columns of Table 1. To obtain $l_C(S_i)$ and $u_C(S_i),$ we search the minimum class in $D_C^+(S_i)$ and the maximum class in $D_C^-(S_i),$ respectively.

Table 1 A decision table

Discernibility matrices $M^{l}$ and $M^{u}$ are obtained as in Tables 2 and 3, respectively. For example, the entry corresponding to row $S_1$ and column $S_3$ on $M^{l}$ contains Ma and Li, because $S_3$ is worse than $S_1$ with respect to Ma and Li but not worse with respect to Ph. Symbol $C$ at some entries means $\{\hbox{Ma},\hbox{Ph},\hbox{Li}\}.$ The rows with asterisk shows objects belonging to one of lower approximations of decision classes.

Table 2 The discernibility matrix $M^{l}$ concerning Table 1

Table 3 The discernibility matrix $M^{u}$ concerning Table 1

The boolean function $F^{\ge}$ is obtained from $M^l$ as

$$ \begin{aligned} F^{\ge}(\tilde{\hbox{Ma}}^P,\tilde{\hbox{Ph}}^P,\tilde{\hbox{Li}}^P) &= \tilde{\hbox{Ph}}^P\wedge\tilde{\hbox{Li}}^P\wedge(\tilde{\hbox{Ma}}^P\vee\tilde{\hbox{Ph}}^P)\\ & \quad \wedge (\tilde{\hbox{Ma}}^P\vee\tilde{\hbox{Li}}^P) \wedge (\tilde{\hbox{Ph}}^P\vee\tilde{\hbox{Li}}^P)\\ &=\tilde{\hbox{Ph}}^P\wedge\tilde{\hbox{Li}}^P.\\ \end{aligned} $$

(64)

From Eq. 64, $F^{\ge}(\tilde{\hbox{Ma}}^P,\tilde{\hbox{Ph}}^P, \tilde{\hbox{Li}}^P)=\hbox{true}$ only when $\tilde{\hbox{Ph}}^P=\text{true}$ and $\tilde{\hbox{Li}}^P=\text{true}.$ This implies that only $\{\hbox{Ma},\hbox{Ph},\hbox{Li}\}$ and $\{\hbox{Ph},\hbox{Li}\}$ satisfy $(\hbox{L1}^\ge)$ owing to Theorem 5. An L$^\geq$-reduct is a minimal set of condition attributes that satisfies $(\hbox{L}1^\ge).$ Therefore, $\{\hbox{Ph},\hbox{Li}\}$ is a unique $\hbox{L}^\geq$-reduct. Moreover, the $\hbox{L}^\geq$-reduct corresponds to a unique prime implicant of $F^{\ge},$ i.e., $\tilde{\hbox{Ph}}^P\wedge\tilde{\hbox{Li}}^P.$

Similarly, boolean functions $F^{\le}, F^{\rm U}$ and $F^{\rm L}$ are

$$ \begin{aligned} F^{\le}\left(\tilde{\hbox{Ma}}^P,\tilde{\hbox{Ph}}^P,\tilde{\hbox{Li}}^P\right) &= \tilde{\hbox{Ma}}^P\wedge\tilde{\hbox{Ph}}^P\wedge\left(\tilde{\hbox{Ma}}^P\vee\tilde{\hbox{Ph}}^P\right)\\ &\wedge \left(\tilde{\hbox{Ma}}^P\vee\tilde{\hbox{Li}}^P\right)\wedge\left(\tilde{\hbox{Ph}}^P\vee\tilde{\hbox{Li}}^P\right)\\ &= \tilde{\hbox{Ma}}^P\wedge\tilde{\hbox{Ph}}^P,\\ \end{aligned} $$

(65)

$$ \begin{aligned} F^{\rm U}\left(\tilde{\hbox{Ma}}^P,\tilde{\hbox{Ph}}^P,\tilde{\hbox{Li}}^P\right) &= F^{\ge}\left(\tilde{\hbox{Ma}}^P,\tilde{\hbox{Ph}}^P,\tilde{\hbox{Li}}^P\right)\\ &\wedge F^{\le}\left(\tilde{\hbox{Ma}}^P,\tilde{\hbox{Ph}}^P,\tilde{\hbox{Li}}^P\right)\\ &= \tilde{\hbox{Ma}}^P\wedge\tilde{\hbox{Ph}}^P\wedge\tilde{\hbox{Li}}^P, \end{aligned} $$

(66)

$$ \begin{aligned} F^{\rm L}\left(\tilde{\hbox{Ma}}^P,\tilde{\hbox{Ph}}^P,\tilde{\hbox{Li}}^P\right) &= \left(\tilde{\hbox{Li}}^P\wedge (\tilde{\hbox{Ma}}^P\vee\tilde{\hbox{Ph}}^P)\right.\\ &\left.\phantom{\ }\wedge (\tilde{\hbox{Ma}}^P\vee\tilde{\hbox{Li}}^P) \wedge(\tilde{\hbox{Ph}}^P\vee\tilde{\hbox{Li}}^P)\right)\\ &\wedge\left(\tilde{\hbox{Ma}}^P\wedge (\tilde{\hbox{Ma}}^P\vee\tilde{\hbox{Ph}}^P)\right.\\ &\left.\phantom{\ }\wedge (\tilde{\hbox{Ma}}^P\vee\tilde{\hbox{Li}}^P) \wedge (\tilde{\mbox{Ph}}^P\vee\tilde{\hbox{Li}}^P)\right)\\ &=\tilde{\hbox{Ma}}^P\wedge\tilde{\hbox{Li}}^P. \end{aligned} $$

(67)

Consequently, we obtain $\{\hbox{Ph}, \hbox{Li}\}$ as a unique $\hbox{L}^\geq$-reduct, $\{\hbox{Ma},\hbox{Ph}\}$ as a unique $\hbox{L}^{\le}$-reduct, $C=\{\hbox{Ma},\hbox{Ph},\hbox{Li} \}$ as a unique U-reduct and $\{\hbox{Ma},\hbox{Li}\}$ as a unique L-reduct. As exemplified in this example, $\hbox{L}^\geq$-reduct, $\hbox{L}^{\le}$-reduct, U-reduct and L-reduct can be different.

5 Conclusions

In this paper, we have investigated attribute reduction in DRSA. We introduce class-based reducts and show relations with previous reducts. Moreover, we show that all kinds of reducts can be enumerated comprehensively based on two discernibility matrices associated with generalized decisions. The proposed approach to the enumeration of all reducts in a decision table can be computationally efficient.

The investigations about the class-based reducts in VC-DRSA (Variable Consistency-DRSA) as well as VP-DRSA (Variable Precision-DRSA) will be a next step of this research.