Keywords

1 Introduction

Decision-theoretic rough set (DTRS) models [15, 16] are probabilistic generalizations of Pawlak rough sets [9]. One feature of DTRS models is the tolerance of decision errors. In contrast to Pawlak approximations [9], both probabilistic positive and negative regions are not certain and contain errors [1, 8, 13]. Consequently, the notion of attribute reducts becomes more complicated. In addition to the condition of positive region preservation required by a Pawlak attribute reduct [10], we must also consider boundary and negative regions. This leads to the notion of region vector based attribute reducts.

Compared with Pawlak’s three regions, probabilistic regions of DTRS models are not monotonic with respect to the set inclusion relation on sets of attributes [5, 18]. Definitions of, and methods for constructing, Pawlak attribute reducts may not be appropriate for DTRS models. To address the problem of non-monotonicity, many authors proposed different types of attribute reducts, such as minimum cost attribute reducts by Jia et al. [2, 4], non-monotonic attribute reducts by Li et al. [5], cost-sensitive attribute reducts by Liao et al. [6], decision region distribution preservation reducts by Ma et al. [7], and so on.

Zhao et al. [18] proposed a general definition of an attribute reduct as a minimal set of condition attributes satisfying properties given in terms of a set of evaluation measures. Jia et al. [3] studied systematically several specific classes of attribute reducts based on a general definition of attribute reducts. Yao [14] provided a more general conceptual definition of reducts of a set, embracing notions of attribute reducts, attribute-value pair reducts, and rule reducts.

Based on results from these studies, in this paper we study attribute reducts by considering changes of decision regions. By using region vector based three-way approximations, we propose three new definitions of attribute reducts. The new definitions require that an attribute reduct should perverse high confidence rules. A method for constructing an attribute reduct is proposed by using the notion of a discernibility matrix introduced by Skowron and Rauszer [11].

2 Three-Way Approximations of a Classification

An information table is defined by \(IT = (U,AT,\{ {V_a}|a \in AT\},\{ {I_a}|a \in AT\} )\), where U is a finite nonempty set of objects, AT is a finite nonempty set of attributes, \({V_a}\) is a nonempty set of values for \(a \in AT\), and \({I_a}:U \rightarrow {V_a}\) is an information function that maps an object in U to one value in \({V_a}\). If \(AT = C \cup D\), where C is a finite set of condition attributes, D is a finite set of decision attributes and \(C \cap D = \emptyset \), the information table is called a decision table, denoted by DT.

For a subset of attributes \(A \subseteq AT\), one defines an equivalence relation on U as follows:

$$\begin{aligned} x{R_A}y \Leftrightarrow \forall a \in A ({I_a}(x) = {I_a}(y)). \end{aligned}$$
(1)

The equivalence relation \(R_A\) induces a partition of U, denoted by \(U/{R_A} = \{ {[x]_{{R_A}}}\mid x \in U\} \) and U / A or \({\pi _A}\) for short. The equivalence class containing x is given by \({[x]_A} = \{ y \mid \forall a \in A({I_a}(x) = {I_a}(y))\}\). According to Pawlak [10], a partition induced by a subset of attributes is called a classification of U. The classification based on the set of decision attributes is given by U / D or \({\pi _D}\).

For a subset of objects \(X \subseteq U\) and a subset of attributes \(A \subseteq AT\), Let \(\Pr (X|{[x]_A})\) denote the conditional probability of an object belonging to X given that the object belongs to \({[x]_A}\). This probability may be simply estimated as \(\text {Pr} (X|[x]_A) = \left| X \cap [x]_{A} \right| \big / {\left| [x]_{A} \right| }\), where \(\left| \cdot \right| \) denotes the cardinality of a set. In terms of conditional probability, the main results of DTRS models are approximations of a set through a pair of lower and upper approximations or three pair-wise disjoint positive, boundary and negative regions. In this paper, we adopt the formulation with three-way approximations [13, 14] by using a slightly different notional system.

Definition 1

In a decision table \(DT = (U,AT = C \cup D,\{ {V_a}|a \in AT\},\{ {I_a}|a \in AT\} )\), given a subset of attributes \(A \subseteq C\) and a pair of thresholds \(0 \le \beta < \alpha \le 1\), the following sets:

$$\begin{aligned} \mathrm{{POS}}_{(\alpha ,\beta )}(X| {\pi _A})= & {} \{ x \in U\mid \Pr (X|{[x]_A}) \ge \alpha \}, \nonumber \\ \mathrm{{BND}}_{(\alpha ,\beta )}(X| {\pi _A})= & {} \{ x \in U\mid \beta < \Pr (X|{[x]_A}) < \alpha \}, \nonumber \\ \mathrm{{NEG}}_{(\alpha ,\beta )}(X| {\pi _A})= & {} \{ x \in U\mid \Pr (X|{[x]_A}) \le \beta \}, \end{aligned}$$
(2)

are called \((\alpha ,\beta )\)-positive, boundary and negative regions of a subset of objects X with respect to the partition \({\pi _A}\).

The three regions are pair-wise disjoint and their union is U. Some of the three regions may be the empty set. Thus, the family of these regions may not necessarily be a partition of U.

One can extend the three-way approximations of a set to three-way approximations of a classification \({\pi _D} = \{ {D_1},{D_2}, \cdots ,{D_r}\}\). A straightforward way is to define three-way approximations component-wise.

Definition 2

In a decision table DT, given a subset of attributes \(A \subseteq C\) and a pair of thresholds \(0 \le \beta < \alpha \le 1\), the vector based \((\alpha ,\beta )\)-positive, boundary and negative regions of \({\pi _D}\) with respect to the partition \({\pi _A}\) are given by:

$$\begin{aligned} {\overrightarrow{\mathrm{{POS}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A})= & {} (\mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_1}|{\pi _A}), \cdots ,\mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_r}|{\pi _A})), \nonumber \\ {\overrightarrow{\mathrm{{BND}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A})= & {} (\mathrm{{BN}}{\mathrm{{D}}_{(\alpha ,\beta )}}({D_1}|{\pi _A}), \cdots ,\mathrm{{BN}}{\mathrm{{D}}_{(\alpha ,\beta )}}({D_r}|{\pi _A})), \nonumber \\ {\overrightarrow{\mathrm{{NEG}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A})= & {} (\mathrm{{NE}}{\mathrm{{G}}_{(\alpha ,\beta )}}({D_1}|{\pi _A}), \cdots , \mathrm{{NE}}{\mathrm{{G}}_{(\alpha ,\beta )}}({D_r}|{\pi _A})). \end{aligned}$$
(3)

By taking a component-wise union of regions in two vectors \({\overrightarrow{\mathrm{{POS}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A})\) and \({\overrightarrow{\mathrm{{BND}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A})\), we obtain a non-negative region vector:

$$\begin{aligned} {\overrightarrow{\lnot \mathrm{{NEG}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A}) = (\lnot \mathrm{{NE}}{\mathrm{{G}}_{(\alpha ,\beta )}}({D_1}|{\pi _A}), \cdots ,\lnot \mathrm{{NE}}{\mathrm{{G}}_{(\alpha ,\beta )}}({D_r}|{\pi _A})), \end{aligned}$$
(4)

where \(\lnot \mathrm{{NE}}{\mathrm{{G}}_{(\alpha ,\beta )}}({D_j}|{\pi _A}) = \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _A}) \cup \mathrm{{BN}}{\mathrm{{D}}_{(\alpha ,\beta )}}({D_j}|{\pi _A})\), \(j = 1, \cdots ,r\).

Another definition is based on the union of the three-way approximations of all decision classes, we call it a set based definition.

Definition 3

In a decision table DT, given a subset of attributes \(A \subseteq C\) and a pair of thresholds \(0 \le \beta < \alpha \le 1\), the set based \((\alpha ,\beta )\)-positive, boundary and negative regions of \({\pi _D}\) with respect to the partition \({\pi _A}\) are given by:

$$\begin{aligned} \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A})= & {} \bigcup \nolimits _{j = 1}^r {\mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _A})},\nonumber \\= & {} \{ x \in U\mid \exists {D_j} \in {\pi _D}(\Pr ({D_j}|{[x]_A}) \ge \alpha )\};\nonumber \\ \mathrm{{BN}}{\mathrm{{D}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A})= & {} \bigcup \nolimits _{j = 1}^r {\mathrm{{BN}}{\mathrm{{D}}_{(\alpha ,\beta )}}({D_j}|{\pi _A})},\nonumber \\= & {} \{ x \in U\mid \exists {D_j} \in {\pi _D}(\beta < \Pr ({D_j}|{[x]_A}) < \alpha )\};\nonumber \\ \mathrm{{NE}}{\mathrm{{G}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A})= & {} U- \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A}) \cup \mathrm{{BN}}{\mathrm{{D}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A}),\nonumber \\= & {} \{ x \in U\mid \forall {D_j} \in {\pi _D}(\Pr ({D_j}|{[x]_A}) \le \beta )\}. \end{aligned}$$
(5)

A set based \((\alpha ,\beta )\)-non-negative region is defined as the union of positive and boundary regions:

$$\begin{aligned} \lnot \mathrm{{NE}}{\mathrm{{G}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A}) = \bigcup \nolimits _{j = 1}^r {\{ x \in U|\exists {D_j} \in {\pi _D}(\Pr ({D_j}\mid {{[x]}_A}) > \beta \}}. \end{aligned}$$
(6)

As \(\mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A})\) only depends on the threshold \(\alpha \), Li et al. [5] call it the \(\alpha \)-positive region. For convenience, we still call it \((\alpha ,\beta )\)-positive region. In the special case when \(\alpha = 1\) and \(\beta = 0\), \(\mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({\pi _D}|{\pi _A})\) and \(\mathrm{{BN}}{\mathrm{{D}}_{(1,0)}}({\pi _D}|{\pi _A})\) are, in fact, the positive and boundary regions in Pawlak rough set model, respectively. In this case, \(\mathrm{{NE}}{\mathrm{{G}}_{(1,0)}}({\pi _D}|{\pi _A}) = \emptyset \).

One can construct decision or classification rules from the three regions. In general, a rule in rough set theory can be expressed in the form of \({[x]_A} \rightarrow {D_j}\), stating that an object with description \({[x]_A}\) would be in the decision class \({D_j}\). Given a rule \({[x]_A} \rightarrow {D_j}\), \(\Pr ({D_j}|{[x]_A})\) is its confidence and \(\Pr ({[x]_A}|{D_j})\) its coverage [17].

Skowron [12] introduced a concept of generalized decisions. For an object x, the generalized decision for x is the set all possible decisions for objects in the equivalence class \([x]_A\). For DTRS, Zhao et al. [18] introduced the notion of \((\alpha ,\beta )\)-positive, boundary and non-negative decisions. Specifically, for an equivalence class \({[x]_A} \in {\pi _A}\), we have:

$$\begin{aligned} {D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_A}\mathrm{{)}}= & {} \{ {D_j} \in {\pi _D}\mid (\Pr ({D_j}|{[x]_A}) \ge \alpha )\}, \nonumber \\ {D_{\mathrm{{BND}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_A}\mathrm{{)}}= & {} \{ {D_j} \in {\pi _D}\mid (\beta < \Pr ({D_j}|{[x]_A}) < \alpha )\},\nonumber \\ {D_{\mathrm{{\lnot NEG}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_A}\mathrm{{)}}= & {} {D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_A}\mathrm{{)}} \cup {D_{\mathrm{{BND}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_A}). \end{aligned}$$
(7)

They are probabilistic versions of the generalized decisions.

3 Region Vector Based Attribute Reducts for DTRS Models

In existing studies, the set based regions are widely used in defining attribute reducts for DTRS models. The problem of searching for an attribute reduct is to remove redundant attributes. By successively removing attributes, the resulting partitions will become coarser. As a result, the decision regions will be changed. Compared with Pawlak rough set model, the monotonicity of decision region change no longer holds for DTRS models. It is therefore very important to analyze how decision region changes with the decrease of attributes.

3.1 An Analysis of Set Based Decision Regions

For the set based three regions, it is easy to verify the following properties:

$$\begin{aligned} (1)&\mathrm{{NE}}{\mathrm{{G}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A}) \mathrm{~may~not~be~empty},\\ (2)&\mathrm{{NE}}{\mathrm{{G}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A}) \cap \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A}) = \emptyset ,\\ (3)&\mathrm {NEG}_{(\alpha ,\beta )}({\pi _D}|{\pi _A}) \cap \mathrm {BND}_{(\alpha ,\beta )}({\pi _D}|{\pi _A}) = \emptyset ,\\ (4)&\mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A}) \mathrm{~and~} \mathrm{{BN}}{\mathrm{{D}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _A}) \mathrm{~may~have~an~overlap},\\ (5)&\mathrm{When}~\alpha > 0.5, \forall {D_i},{D_j} \in {\pi _D},i \ne j,\\&~~~~~\mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_i}|{\pi _A}) \cap \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _A}) = \emptyset , \\ (6)&\mathrm{When}~\alpha \le 0.5, \mathrm{~there~may~exist~decision~classes~such~that}\\&~~~~~\mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_i}|{\pi _A}) \cap \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _A}) \ne \emptyset , ~~i\ne j. \end{aligned}$$

These properties are essential to our study of attribute reducts in DTRS models.

When we remove some attributes, the confidence of decision rules, as defined by the conditional probability may change. Consider a subset of condition attributes \(A \subseteq C\). By definition, an equivalence class of \(\pi _A\) is the union of a family of equivalence classes of C. That is, \([x]_A = \cup _{y\in [x]_A} [y]_C = \cup _{k=1}^m [y_k]_C\), where \([y_1]_C, \ldots , [y_m]_C\) are the family of distinct equivalence classes of \(\pi _C\) such that their union is \([x]_A\). Based on this result, one can easily verify the next lemma.

Lemma 1

For \({D_j} \in {\pi _D}\), we have:

$$\begin{aligned} (1)&\Pr ({D_j}|{[x]_A}) = \sum _{k = 1}^m \frac{| [y_k]_C|}{|[x]_A|} \Pr (D_j|[y_j]_C), \\ (2)&\min \{ \Pr ({D_j}|{[{y}]_C}) \mid y \in [x]_A \}\le \Pr ({D_j}|{[x]_A}) \le \max \{ \Pr ({D_j}|{[{y}]_C}) \mid y \in [x]_A\}. \end{aligned}$$

By removing some attributes, we in fact combine a family rules into a single rule. According to Lemma 1, the confidence of the new rule \({[x]_A} \rightarrow {D_j}\) is the weighted sum of the confidence of individual rules \({[y_k]_C} \rightarrow {D_j}\), \(k=1, \ldots , m\).

By the set based definition of three regions, \([x]_C\) is put into the \((\alpha ,\beta )\)-positive region \(\mathrm {POS}_{(\alpha ,\beta )}({\pi _D}|{\pi _C})\) if \(\Pr ({D_j}|{[x]_C}) \ge \alpha \) for some \({D_j} \in {\pi _D}\). Equivalence classes in positive regions induced by \(\pi _C\) with different decision set may merge into a new equivalence class \(\pi _A\) when removing attributes and the new equivalence class may be in the negative region \(\mathrm {NEG}_{(\alpha ,\beta )}({\pi _D}|{\pi _C})\), as shown by the following example from [2].

Example 1

Consider a decision Table 1, where \(U = \{ {x_1}, \cdots , {x_9}\}\), \(C = \{ {c_1},{c_2}\}\), and \(D=\{d\}\). The partition induced by the set of condition attributes is given by \(U/C = \{ {C_1},{C_2},{C_3},{C_4}\}\), where \({C_1} = \{ {x_1},{x_4}\}\), \({C_2} = \{ {x_2},{x_6},{x_8}\}\), \({C_3} = \{ {x_3}\}\), and \({C_4} = \{ {x_5},{x_7},{x_9}\}\). The decision partition is given by \(U/D = \{ {D_1},{D_2},{D_3}\}\), where \({D_1} = \{ {x_1},{x_2}\} \), \({D_2} = \{ {x_3},{x_4},{x_5}\} \), and \({D_3} = \{ {x_6},{x_7},{x_8},{x_9}\} \). Let \(A = \{ {c_1}\} \), then \(U/A = \{ {A_1},{A_2}\} \), where \({A_1} = {C_1} \cup {C_2}\) and \({A_2} = {C_3} \cup {C_4}\).

Assume that \(\alpha = 0.6\) and \(\beta = 0.5\). We have \(\mathrm{{PO}}{\mathrm{{S}}_{(0.6, 0.5)}}({\pi _D}|{\pi _C}) = {C_2} \cup {C_3} \cup {C_4}\) and \(\mathrm{{NE}}{\mathrm{{G}}_{(0.6, 0.5)}}({\pi _D}|{\pi _A}) = U\). The equivalence classes \({C_3}\) and \({C_4}\) in partition U / C is merged into \({A_2}\) in partition U / A when we remove attribute \({c_2}\). The equivalence class \(A_2\) is put into negative region \(\mathrm {NEG}_{(0.6, 0.5)}({\pi _D}|{\pi _A})\).

When \(\alpha = 0.6\) and \(\beta = 0.4\), the equivalence class \({A_2}\) is put into the boundary region \(\mathrm {BND}_{(0.6, 0.4)}({\pi _D}|{\pi _A})\). When \(\alpha = 0.5\) and \(\beta = 0.3\), \({A_2}\) is put into positive region \(\mathrm {POS}_{(0.5, 0.3)}({\pi _D}|{\pi _A})\).

Table 1. A decision table
Full size table

Analogously, some equivalence classes in the positive or negative regions merge into a new equivalence class, which may be put into the positive, boundary or negative region. There is one exception, that is, the merge of equivalence classes in the negative region is still in the negative region according to the definition of negative region. Table 2 summarizes the main results, where the second column gives the regions of equivalences before the merge, and the third column gives the regions of the new equivalence class.

Table 2. Changes of decision regions after removing attributes
Full size table

3.2 Region Vector Based Attribute Reducts

According to the previous analysis, a set based region may become larger, unchanged or smaller when we remove some condition attributes. This results in difficulties in constructing an attribute reduct for DTRS models. For example, when equivalence classes in positive and negative regions merge, the new equivalence class will be put into positive, boundary or negative regions. If it is put into the positive region, the new positive region will be larger. Such a move may not be desirable because it puts original lower confidence rules into positive region. On the other hand, if the merged equivalence class is put into the boundary or negative regions, it cannot guarantee that a positive rule is still a positive rule after removing attributes.

When equivalence classes with the same decision set are combined, the new equivalence class can put into the positive region according to Lemma 1. An original positive rule is still a positive rule after reducing attributes. The generality stay the same and there is no risk to misclassify a low confidence rule as a high confidence rule.

Similarly, if equivalence classes in boundary regions with the same decision set are merged, the merged equivalence class is still in the boundary region by Lemma 1. This will not change the positive, boundary and negative regions. When equivalence classes in negative region are merged, the merged equivalence classes must be put into negative region. This does not change the generality and nor increases the cost of decision risk.

Based on the above analysis, we propose a new type of attribute reducts based on a vector representation of three regions.

Definition 4

In a decision table DT, given a subset of attributes \(R \subseteq C\) and a pair of thresholds \(0 \le \beta < \alpha \le 1\), R is an \((\alpha ,\beta )\)-vregion attribute reduct of C with respect to the set of decision attributes D if it satisfies the following two conditions:

$$\begin{aligned} (1)&{\overrightarrow{\mathrm{{vregion}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _R}) = {\overrightarrow{\mathrm{{vregion}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _C});\\ (2)&\mathrm{for~any}~ R' \subset R, {\overrightarrow{\mathrm{{vregion}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _{R'}}) \ne {\overrightarrow{\mathrm{{vregion}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _C}). \end{aligned}$$

Especially, if vregion is a positive, boundary, negative or non-negative region, then R is called an \((\alpha ,\beta )\)-positive, boundary, negative or non-negative region attribute reduct of C, respectively. If R only satisfies condition (1), it is called an \((\alpha ,\beta )\)-positive, boundary, negative or non-negative region consistent attribute subset of C.

Theorem 1

\({\overrightarrow{\mathrm{{POS}}}_{(1,0)}}({\pi _D}|{\pi _R}) = {\overrightarrow{\mathrm{{POS}}}_{(1,0)}}({\pi _D}|{\pi _C})\) if and only if

\(\mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({\pi _D}|{\pi _R})\) \( = \mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({\pi _D}|{\pi _C})\).

Proof. (\(\Rightarrow \)) If \({\overrightarrow{\mathrm{{POS}}}_{(1,0)}}({\pi _D}|{\pi _R}) = {\overrightarrow{\mathrm{{POS}}}_{(1,0)}}({\pi _D}|{\pi _C})\), by definitions of these regions, we immediately have \(\mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({\pi _D}|{\pi _R}) = \mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({\pi _D}|{\pi _C})\).

(\(\Leftarrow \)) By definition, \(\mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({D_i}|{\pi _R}) \cap \mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({D_j}|{\pi _R}) = \emptyset \) for any \({D_i},{D_j} \in {\pi _D}, i \ne j\) and \(\mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({D_j}|{\pi _R}) \subseteq \mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({D_j}|{\pi _C})\). Hence, if \(\mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({\pi _D}|{\pi _R}) = \mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({\pi _D}|{\pi _C})\), we have \(\mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({D_j}|{\pi _R}) = \mathrm{{PO}}{\mathrm{{S}}_{(1,0)}}({D_j}|{\pi _C})\). It follows that \({\overrightarrow{\mathrm{{POS}}}_{(1,0)}}({\pi _D}|{\pi _R}) = {\overrightarrow{\mathrm{{POS}}}_{(1,0)}}({\pi _D}|{\pi _C})\).

Theorem 1 shows that, in Pawlak rough set model, the two representation forms are equivalent in judging whether R is a positive region preservation consistent set of C. For boundary region, we can only get a one-way inference. That is, \({\overrightarrow{\mathrm{{BND}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _R}) = {\overrightarrow{\mathrm{{BND}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _C}) \Rightarrow \mathrm{{BN}}{\mathrm{{D}}_{(1,0)}}({\pi _D}|{\pi _R}) = \mathrm{{BN}}{\mathrm{{D}}_{(1,0)}}({\pi _D}|{\pi _C})\), and the reverse is not necessarily true. For a decision-theoretic rough set model, we can only get one-way inference, i.e.,

$$\begin{aligned} {\overrightarrow{\mathrm{{POS}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _R}) = {\overrightarrow{\mathrm{{POS}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _C})\Rightarrow & {} \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _R}) = \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _C}), \\ {\overrightarrow{\mathrm{{BND}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _R}) = {\overrightarrow{\mathrm{{BND}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _C})\Rightarrow & {} \mathrm{{BN}}{\mathrm{{D}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _R}) = \mathrm{{BN}}{\mathrm{{D}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _C}). \end{aligned}$$

The reverse is not necessarily true. The regions based on vector representation do not have the monotonicity, as shown by the next example.

Example 2

(continued from Example 1) Let \(\alpha = 0.40,\beta = 0.35\), \(R = \{ {c_1}\} \), we have:

$$\begin{aligned}&\mathrm{{PO}}{\mathrm{{S}}_{(0.40, 0.35)}}({\pi _D}|{\pi _R}) = \mathrm{{PO}}{\mathrm{{S}}_{(0.40, 0.35)}}({\pi _D}|{\pi _C}) = U,\\&{\overrightarrow{\mathrm{{POS}}}_{(0.40, 0.35)}}({\pi _D}|{\pi _C}) = ({C_1},{C_1} \cup {C_3},{C_2} \cup {C_4}),\\&{\overrightarrow{\mathrm{{POS}}}_{(0.40, 0.35)}}({\pi _D}|{\pi _R}) = ({C_1} \cup {C_2},{C_3} \cup {C_4},U). \end{aligned}$$

They show that the monotonicity does not hold.

4 A Reduct Construction Method

For an \((\alpha ,\beta )\)-positive region attribute reduct, the positive rule set does not change if we merge equivalence classes with the same decisions. We can construct a discernibility matrix \({M_{{D_{\mathrm{{POS}}}}}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{,[}}y{\mathrm{{]}}_C}\mathrm{{)}}\) for positive region attribute reduct as follows:

$$\begin{aligned} {M_{{D_{\mathrm{{POS}}}}}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{,[}}y{\mathrm{{]}}_C}\mathrm{{)}} = \left\{ \begin{array}{l} \{a \in C|{I_a}(x) \ne {I_a}(y) \},\\ ~~~~~~~\mathrm{if} ~D_\mathrm{{POS}(\alpha ,\beta )} ([x]_C) \ne D_\mathrm{{POS}(\alpha ,\beta )}([y]_C),\\ C, ~~~\mathrm{otherwise}. \end{array} \right. \end{aligned}$$
(8)

By the discernibility function proposed by Skowron and Rauszer [11]:

$$\begin{aligned} f({M_{{D_{\mathrm{{POS}}}}}}) = \wedge \vee {M_{{D_{\mathrm{{POS}}}}}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{,[}}y{\mathrm{{]}}_C}\mathrm{{)}}. \end{aligned}$$
(9)

We can get a decision reduct, which is a prime implicants of the reduced disjunctive form of the discernibility function.

If \(\alpha > 0.5\), Eq. (8) degenerates into the discernibility matrix of a variable precision rough set (VPRS) model [8]. We can get an \(\alpha \)-lower-approximation attribute reduct. Since VPRS is a special case of DTRS with \(\alpha > 0.5\) and \(\beta = 1- \alpha \), we give a general conclusion for any pair of thresholds \((\alpha ,\beta )\) with \(0 \le \beta < \alpha \le 1\).

Theorem 2

In a decision table DT, given a subset of attributes \(A \subseteq C\) and a pair of thresholds \(0 \le \beta < \alpha \le 1\), A is an \((\alpha ,\beta )\)-positive region consistent set of C iff for any \(x,y \in U\), \({D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{)}} \ne {D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}y{\mathrm{{]}}_C}\mathrm{{)}}\) implies \({\mathrm{{[}}x\mathrm{{]}}_A} \cap {\mathrm{{[}}y\mathrm{{]}}_A} = \emptyset \).

Proof. \((\Rightarrow )\) For any \(x,y \in U\), if \({\mathrm{{[}}x\mathrm{{]}}_A} \cap {\mathrm{{[}}y\mathrm{{]}}_A} \ne \emptyset \), \({\mathrm{{[}}x\mathrm{{]}}_A}\mathrm{{ = [}}y{\mathrm{{]}}_A}\). Thus, we have \({D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_A}\mathrm{{) }} = {D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}y{\mathrm{{]}}_A}\mathrm{{)}}\). Since A is an \((\alpha ,\beta )\)-positive region consistent set of C, \(\mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _A}) = \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _C})\) for any \({D_j} \in {\pi _D}\). It follows that \( x \in \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _A}) \Leftrightarrow x \in \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _C})\), i.e., \({D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_A}\mathrm{{) }}={D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{)}}\). Similarly, we have \({D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}y{\mathrm{{]}}_A}\mathrm{{) }}={D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}y{\mathrm{{]}}_C}\mathrm{{)}}\). Therefore, we can conclude that \({D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{) }}={D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}y{\mathrm{{]}}_C}\mathrm{{)}}\), which conflicts with the assumption.

(\(\Leftarrow \)) Since \(A \subseteq C\), it is easy to verify that \(T({[x]_A}) = \{ {[y]_C} \mid {[y]_C} \in {[x]_A}/C\} \) is a partition of \({[x]_A}\).

(i) For any \({D_j} \in {\pi _D}\), if \(x \in \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _A})\), then \({[x]_A} \subseteq \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _A})\). Since \({\mathrm{{[}}x\mathrm{{]}}_A}\mathrm{{ = [}}y{\mathrm{{]}}_A}\) for any \(y \in {[x]_A}\), according to the arbitrariness of y and the assumption that \({D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{) = }}{D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}y{\mathrm{{]}}_C}\mathrm{{)}}\), we have \({D_j} \in {D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{)}}\), i.e., \(x \in \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _C})\).

(ii) If \(x \in \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _C})\), then \({D_j} \in {D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{)}}\). Since \({\mathrm{{[}}x\mathrm{{]}}_A}\mathrm{{ = [}}y{\mathrm{{]}}_A}\) for any \({[y]_C} \in T({[x]_A})\), by the assumption, we have \({D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{) = }}{D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}y{\mathrm{{]}}_C}\mathrm{{)}}\). It follows that \({D_j} \in {D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{([}}y{\mathrm{{]}}_C}\mathrm{{)}}\) i.e., \(\Pr ({D_j}|{[y]_C}) \ge \alpha \). Hence,

$$\begin{aligned} p({D_j}|{[x]_A}) = \sum \limits _{{{[y]}_C} \in T({{[x]}_A})} {\frac{{\left| {{{[y]}_C}} \right| }}{{\left| {{{[x]}_A}} \right| }}} \frac{{\left| {{{[y]}_C} \cap {D_j}} \right| }}{{\left| {{{[y]}_C}} \right| }} > \alpha , \end{aligned}$$
(10)

i.e., \(x \in \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _A})\).

Based on (i) and (ii), we have \(\mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _A}) = \mathrm{{PO}}{\mathrm{{S}}_{(\alpha ,\beta )}}({D_j}|{\pi _C})\) for any \({D_j} \in {\pi _D}\), which follows that A is an \((\alpha ,\beta )\)-positive region consistent set of C.

According to Theorem 2, when deleting some attributes, if only equivalence classes with same decision set are merged, it can guarantee that the deleted attributes are redundant and the remaining set of attributes is an \((\alpha ,\beta )\)-positive region consistent set of C.

Example 3

Consider a decision Table 3, where \(U =\{ {x_1}, \cdots ,{x_{10}}\}\), \(C = \{ {c_1},{c_2}\}\), and \(D=\{d\}\). For the set of condition attributes, we have \(U/C = \{ {C_1},{C_2},{C_3}\} \), where \({C_1} = \{ {x_1},{x_2},{x_3},{x_4}\} \), \({C_2} = \{ {x_5},{x_6},{x_7}\} \), \({C_3} = \{ {x_8},{x_9},{x_{10}}\}\). For the set of decision attributes, we have \(U/D = \{ {D_1},{D_2}\} \), where \({D_1} = \{ {x_1},{x_2},{x_3},{x_7},{x_8},{x_9}\} \) and \({D_2} = \{ {x_4},{x_5},{x_6},{x_{10}}\} \). Let \(R = \{ {c_1}\}\). We have \(U/R = \{ {R_1},{R_2}\}\), where \({R_1} = {C_1} \cup {C_3}\) and \({R_2} = {C_2}\). If \(\alpha = 0.6\), then \({\overrightarrow{\mathrm{{POS}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _C}) = ({C_1} \cup {C_3},{C_2})\) and \({\overrightarrow{\mathrm{{POS}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _R}) = ({R_1},{R_2}) = {\overrightarrow{\mathrm{{POS}}}_{(\alpha ,\beta )}}({\pi _D}|{\pi _C})\). It is easy to verity that \(\{ {c_1}\}\) is an \((\alpha ,\beta )\)-positive region attribute reduct of C, it guarantees that the positive rules unchanged although their confidence is different. Before removing attributes, the positive rules are \({C_1}{ \rightarrow _P}{D_1}\), \({C_3}{ \rightarrow _P}{D_1}\), with confidence 0.750 and 0.667, respectively. By deleting attribute set \(\{ {c_2}\}\), equivalence classes \({C_1}\) and \({C_3}\) merge into \({R_1}\). We get a new positive rule \({R_1}{ \rightarrow _P}{D_1}\), with a confidence of 0.714.

On the other hand, we have \({D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{(}}{C_1}\mathrm{{) = \{ }}{D_1}\mathrm{{\} }}\), \({D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{(}}{C_2}\mathrm{{) = \{ }}{D_2}\mathrm{{\} }}\), \({D_{\mathrm{{POS}}(\alpha ,\beta )}}\mathrm{{(}}{C_3}\mathrm{{) = \{ }}{D_1}\mathrm{{\} }}\). The corresponding discernibility matrix \({M_{\mathrm{{POS}}(0.6,\beta )}}\) is showed in Table 4. The attribute reduct is \(\{ {c_1}\}\), which is consistent with Definition 4.

Table 3. A decision table
Full size table
Table 4. The discernibility matrix \({M_{\mathrm{{POS}}(0.6,\beta )}}\) of Table 3
Full size table

Similarly, we can present the discernibility matrix \({M_{{D_{\mathrm{{\lnot NEG}}}}}}({[x]_C},{[y]_C})\) for non-negative region attribute reducts as follows:

$$\begin{aligned} {M_{{D_{\lnot \mathrm{{NEG}}}}}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{,[}}y{\mathrm{{]}}_C}\mathrm{{)}} = \left\{ \begin{array}{l} \{ a \in C|{I_a}(x) \ne {I_a}(y)\},\\ ~~~~~~~\mathrm{if}~ {D_{\lnot \mathrm{{NEG}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{)}} \ne {D_{\lnot \mathrm{{NEG}}(\alpha ,\beta )}}\mathrm{{([}}y{\mathrm{{]}}_C}\mathrm{{),}}\\ C, ~~~\mathrm{otherwise.} \end{array} \right. \end{aligned}$$
(11)

Theorem 3

Given a decision table DT, \(A \subseteq C\) is an \((\alpha ,\beta )\)-non-negative region consistent set of C iff for any \(x,y \in U\), if \({D_{\lnot \mathrm{{NEG}}(\alpha ,\beta )}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{)}} \ne {D_{\lnot \mathrm{{NEG}}(\alpha ,\beta )}}\mathrm{{([}}y{\mathrm{{]}}_C}\mathrm{{)}}\), then \({\mathrm{{[}}x\mathrm{{]}}_A} \cap {\mathrm{{[}}y\mathrm{{]}}_A} = \emptyset \).

Proof. It is similar to the proof of Theorem 2.

The discernibility function of the matrix is given by:

$$\begin{aligned} f({M_{D_{\lnot \mathrm{{NEG}}}}}) = \wedge \vee {M_{{D_{\lnot \mathrm{{NEG}}}}}}\mathrm{{([}}x{\mathrm{{]}}_C}\mathrm{{,[}}y{\mathrm{{]}}_C}\mathrm{{)}}. \end{aligned}$$
(12)

A prime implicant of the reduced disjunctive form of the discernibility function is an \((\alpha ,\beta )\)-non-negative region attribute reduct.

5 Conclusion

In this paper, we analyze the decision region changes when deleting attributes. It is found that positive rules are unchanged when equivalence classes in positive region with the same decision set are merged. It is also true for the equivalence classes in non-negative region with the same decision set. The notion of vector based attribute reduct is proposed. One can use the standard method to construct a reduct based on a discernibility matrix.