Double-local conditional probability based fast calculation method for approximation regions of local rough sets

Abstract

As an important extension of classical rough sets, local rough set model can effectively process data with noise. How to effectively calculate three approximation regions, namely positive region, negative region and boundary region, is a crucial issue of local rough sets. Existing calculation methods for approximation regions are based on conditional probability, the time complexity is O (|X||U||C|). In order to improve the computational efficiency of three approximation regions of local rough sets, we propose a double-local conditional probability based fast calculation method. First, to improve the computational efficiency of equivalence class, we define the double-local equivalence class. Second, based on the double-local equivalence class, we define the double-local conditional probability. Finally, given the probability thresholds and a local equivalence class, the monotonicity of double-local conditional probability is proved, on this basis, a double-local conditional probability based fast calculation method for approximation regions of local rough sets is proposed, and the time complexity is O (MAX (|X|²|C|, |X||X^C||C|)). Experimental results based on 9 datasets from UCI demonstrate the effectiveness of the proposed method.

Keywords

Local rough sets approximation regions double-local equivalence class double-local conditional probability

1 Introduction

Pawlak’s rough set theory provides a powerful mathematical framework for analyzing and handling imprecise, inconsistent, and incomplete data [1 –3]. It has been successfully applied in many fields, such as machine learning, pattern recognition, artificial intelligence, and data mining [4 –8]. However, classical rough set theory is based on complete inclusion relation, which cannot effectively processe data with noise. In order to better meet the needs of practical applications, by introducing conditional probability and probabilistic thresholds, different kinds of probabilistic rough set models have been proposed [9 –21], such as decision-theoretic rough sets [11 –13], variable precision rough sets [14], Bayesian rough sets [15], local rough sets [16 –19], double-quantitative rough sets [20] and game-theoretic rough sets [21]. They are insensitive to noise data and improve the applicability and generality of rough sets [22 –35].

Concept approximation is a key point in probabilistic rough sets. A concept is a subset of the universe of objects. Given an undefinable concept, probabilistic rough sets use a pair of crisp approximation sets, called the lower approximation set and upper approximation set to express this concept approximately. Based on concept approximation, the universe is divided into three pairwise disjoint approximation regions, namely, the positive region, the negative region and the boundary region. Three approximation regions are the base of attribute reduction and rule extraction of probabilistic rough sets. When calculating the approximations of a given target concept, the probabilistic rough set models first calculate the equivalence classes of all objects in the universe. Therefore, such models are very time-consuming and even infeasible when processing large-scale datasets. In order to improve computational efficiency of probabilistic rough sets, Qian et al. [16] proposed local rough set model. As an extended model of the probabilistic rough set, compared to the rough set model, the local rough set can process data with noise. Different from existing probabilistic rough set models, when calculating the approximations of the target concept, it does not calculate the equivalence classes of all objects in the universe, but only the equivalence classes of objects in the concept, which can avoid the calculation of a large number of equivalence classes.

In the local rough set, given a universe U and a target concept X, The calculation process of existing local rough set algorithms [16 –19] generally includes the following three steps: 1) Compare each object in the target concept with all objects in the universe to calculate the equivalent classes. The time complexity is O (|X||U||C|), where |C| is the number of attributes; 2) Compute the conditional probability of each object based on its equivalence class, and the time complexity is O (|X||U|); 3) Compare the conditional probability of each object with the given probability thresholds to calculate the approximations, and the time complexity is O (|X|). It can be seen that the calculation of equivalence classes and conditional probability are the two most time-consuming steps in existing researches. The reason for the high time complexity of step 1 is that, the calculation of the equivalence class of each object requires comparing the object with all objects in the universe, and the reason for the high time complexity of step 2 is that, the calculation of the conditional probability of each object requires calculating the intersection of the given target concept and the equivalent class. Therefore, when calculating the equivalent classes of objects, reducing the number of objects compared with them can improve the calculation efficiency, and when calculating conditional probability, avoiding intersection operation can also improve the calculation efficiency. Based on the above analysis, this paper proposes a fast local rough set approximation algorithm based on double-local conditional probability. The time complexity of the algorithm is O (MAX (|X|²|C|, |X||X^C||C|)), where |X^C| is the number of objects in the complementary set of the target concept. The main contributions are as follows. Firstly, in order to improve the computational efficiency of equivalence class, based on the idea of divide and conquer, the double-local equivalence class is defined; Then, based on the double-local equivalence class, the definition of double-local conditional probability is given; Finally, given the probability thresholds and a local equivalence class, the monotonicity of double-local conditional probability is proved, on this basis, a double-local conditional probability based fast calculation method for approximation regions of local rough sets is proposed, which can effectively improve the computational efficiency of approximation regions by reducing the number of comparisons between objects. Experiments based on UCI datasets demonstrate the effectiveness of the proposed algorithm.

In order to intuitively show the innovations of this paper, we illustrate the variations of time complexity of approximate regions calculation of classical probabilistic rough sets, local rough sets and the proposed double-local conditional probability based fast calculation method for approximation regions of local rough sets in Fig. 1. In Fig. 1, the time complexity of the approximate regions calculation of classical probabilistic rough sets is O (|U||U||C|), where the first |U| is the number of objects to calculate the equivalent class, and the second |U| is the number of objects to be compared with each object that needs to calculate the equivalent class. The local rough sets reduce the time complexity of approximate region calculation to O (|X||U||C|) by changing the number of objects to calculate the equivalent class from |U| objects in the universe to |X| objects in the concept. The proposed double-local conditional probability based fast calculation method for approximation regions of local rough sets further reduces the time complexity of approximate region calculation to O (MAX (|X|²|C|, |X||X^C||C|)) by changing the number of objects to be compared with each object that need to calculate the equivalent class from |U| to |X| and |X^C|.

Fig. 1

Variations of time complexity of approximate regions calculation of probabilistic rough sets, local rough sets and double-local conditional probability based fast calculation method for approximation regions of local rough sets.

The remainder of the paper is organized as follows: Section 2 briefly reviews some related concepts of the local rough sets. In Section 3, a double-local conditional probability based fast calculation method for approximation regions of local rough sets is proposed. In Section 4, the effectiveness of the proposed method is demonstrated by experiments. Finally, we conclude our work and present future challenges in Section 5.

2 Basic concepts of local rough sets

In this section, we briefly review some related concepts of the local rough sets.

Definition 1. [9] DIS = (U, AT = C ∪ D, V, f) is a decision information system. U is a nonempty finite set of objects called universe. AT is a nonempty finite set of attributes, where C is the set of condition attributes and D is a decision attribute respectively, C∩ D = ∅. V = ⋃ _a∈ATV_a, V_a is the domain of attributes AT. f : U × AT → V is an information function, ∀x ∈ U, ∀ a ∈ AT, f (x, a) ∈ V_a denotes the attribute value of object x with respect to attribute a.

Definition 2. [9] Given a decision information system DIS = (U, AT = C ∪ D, V, f). Suppose A ⊆ C is a subset of attributes. The equivalence relation on U with respect to A is defined as: $R_{A} = {(x, y) \in U \times U ∣ f (x, a) = f (y, a), \forall a \in A}$ (1) [x] _A ={ y ∈ U ∣ (x, y) ∈ R_A } is the equivalent class of object x with respect to A.

From definition 2, it is obvious that the calculation of the equivalence class of each object requires comparing the object with all objects in the universe, namely, the calculation of equivalence class is based on all (global) objects in the universe.

Definition 3. [9] Given a decision information system DIS = (U, AT = C ∪ D, V, f). Suppose X ⊆ U is a target concept, A ⊆ C is a subset of attributes. ∀x ∈ U, the conditional probability of x with respect to A is defined as: $\Pr (X ∣ [x]_{A}) = \frac{| X \cap [x]_{A} |}{| [x]_{A} |}$ (2)

Definition 4. [9] Given a decision information system DIS = (U, AT = C ∪ D, V, f), X ⊆ U, A ⊆ C. ∀x ∈ U, suppose Pr(X ∣ [x] _A) is the conditional probability of x with respect to A. Given probabilistic thresholds (α, β), 0 ≤ β ≤ α ≤ 1. The lower approximation and upper approximation of X with respect to A of the local rough set are defined as: $\begin{matrix} {\underline{apr}}_{A}^{(α, β)} (X) = {x ∣ \Pr (X ∣ [x]_{A}) \geq α, x \in X} \\ {\bar{apr}}_{A}^{(α, β)} (X) = \cup {[x]_{A} ∣ \Pr (X ∣ [x]_{A}) > β, x \in X} \end{matrix}$ (3)

Based on these two approximations, the universe can be divided into three disjoint approximation regions, which are the positive region ${POS}_{A} (X, α, β) = {\underline{apr}}_{A}^{(α, β)} (X)$ , the boundary region ${BND}_{A} (X, α, β) = {\bar{apr}}_{A}^{(α, β)} (X) - {\underline{apr}}_{A}^{(α, β)} (X)$ and the negative region $NE G_{A} (X, α, β) = U - {\bar{apr}}_{A}^{(α, β)} (X)$ .

3 Double-local conditional probability based fast calculation method for approximation regions of local rough sets

In this section, we introduce a double-local conditional probability based fast calculation method for approximation regions of local rough sets. First, using the strategy of “divide and conquer”, we define the double-local equivalence class, which divides the calculation of equivalence class into two parts.

Definition 5. Given a decision information system DIS = (U, AT = C ∪ D, V, f), X ⊆ U, A ⊆ C. ∀x ∈ U, the double-local equivalence class of x with respect to A is defined as: $[x]_{A} = [x]_{A}^{X} \cup [x]_{A}^{X^{C}}$ (4)

Where, X^C is the complement of X, $[x]_{A}^{X} = {y \in X ∣ f (x, a) = f (y, a), \forall a \in A}$ is called the local equivalence class of x relative to X, $[x]_{A}^{X^{C}} = {y \in X^{C} ∣ f (x, a) = f (y, a), \forall a \in A}$ is called the local equivalence class of x relative X^C.

Based on definition 5, ∀x ∈ U, when calculating its equivalence class, we compare it with objects in X and X^C respectively rather than with objects in U. Based on the double-local equivalence class, we define the double-local conditional probability as follows:

Definition 6. Given a decision information system DIS = (U, AT = C ∪ D, V, f), X ⊆ U, A ⊆ C. ∀x ∈ U, the double-local conditional probability is defined as: $DLP (X ∣ [x]_{A}) = \frac{| [x]_{A}^{X} |}{| [x]_{A}^{X} | + | [x]_{A}^{X^{C}} |}$ (5)

Property 1. Given a decision information system DIS = (U, AT = C ∪ D, V, f), X ⊆ U, A ⊆ C. ∀x ∈ U, suppose Pr(X ∣ [x] _A) is the conditional probability of x with respect to A and DLP (X ∣ [x] _A) is the double-local conditional probability of x with respect to A. Pr(X ∣ [x] _A) = DLP (X ∣ [x] _A).

Proof.According to definition 3, $\Pr (X ∣ [x]_{A}) = \frac{| X \cap [x]_{A} |}{| [x]_{A} |}$ . According to definition 5, $[x]_{A} = [x]_{A}^{X} \cup [x]_{A}^{X^{C}}$ , so $| [x]_{A} | = | [x]_{A}^{X} | + | [x]_{A}^{X^{C}} |$ . And because $[x]_{A}^{X} = {y \in X ∣ f (x, a) = f (y, a), \forall a \in A, \forall x \in U}$ , $X \cap [x]_{A} = [x]_{A}^{X}$ , so $| [x]_{A} \cap X | = | [x]_{A}^{X} |$ . Hence, Pr(X ∣ [x] _A) = DLP (X ∣ [x] _A).

Definition 6 indicates that the double-local conditional probability is only related to $| [x]_{A}^{X} |$ and $| [x]_{A}^{X^{C}} |$ . Property 1 shows that the value of double-local conditional probability is equal to that of conditional probability. In what follows, given $| [x]_{A}^{X} |$ , with an increase of $| [x]_{A}^{X^{C}} |$ , we illustrate that the double-local conditional probability decreases monotonically.

According to Definition 6, given $| [x]_{A}^{X} |$ , the double-local conditional probability DLP (X ∣ [x] _A)) decreases with the increase of $| [x]_{A}^{X^{C}} |$ . The monotonicity decrease theorem of the double-local conditional probability is described in Theorem 1.

Theorem 1. Given a decision information system DIS = (U, AT = C ∪ D, V, f), X ⊆ U, A ⊆ C. Given $| [x]_{A}^{X} |$ , the double-local conditional probability DLP (X ∣ [x] _A) decreases with the increase of $| [x]_{A}^{X^{C}} |$ .

According to Theorem 1, it is not difficult to find that when $| [x]_{A}^{X} |$ is given, we only need to calculate $| [x]_{A}^{X^{C}} |$ to deserve DLP (X ∣ [x] _A). As DLP (X ∣ [x] _A) decreases with the increase of $| [x]_{A}^{X^{C}} |$ , in the process of calculating $| [x]_{A}^{X^{C}} |$ , we compare x with objects in X^C one by one. If $| [x]_{A}^{X^{C}} |$ makes DLP (X ∣ [x] _A) ≤ β hold, there is no need to compare x with remaining objects in X^C and we can divide x into the negative region. Otherwise, we should compare x with all remaining objects in X^C to calculate $| [x]_{A}^{X^{C}} |$ and divide x into the positive region or the boundary region according to DLP (X ∣ [x] _A). In other words, when the probabilistic thresholds (α, β) and $| [x]_{A}^{X} |$ are given, according to the condition of DLP (X ∣ [x] _A) ≤ β, We can calculate what condition $| [x]_{A}^{X^{C}} |$ should meet when x could be divided into the negative region, namely, $| [x]_{A}^{X^{C}} | \geq \frac{| [x]_{A}^{X} | (1 - β)}{β}$ . In this situation, we can stop comparing x with the objects in X^C and divide x into the negative region. According to the condition of $DLP (X ∣ [x]_{A}) = \frac{| [x]_{A}^{X} |}{| [x]_{A}^{X} | + | [x]_{A}^{X^{C}} |} \geq α$ , we can calculate what condition $| [x]_{A}^{X^{C}} |$ should meet when x could be divided into the positive region, namely, $| [x]_{A}^{X^{C}} | \leq \frac{| [x]_{A}^{X} | (1 - α)}{α}$ . According to the condition of $β < DLP (X ∣ [x]_{A}) = \frac{| [x]_{A}^{X} |}{| [x]_{A}^{X} | + | [x]_{A}^{X^{C}} |} < α$ , we can calculate what condition $| [x]_{A}^{X^{C}} |$ should meet when x could be divided into the boundary region, namely, $\frac{| [x]_{A}^{X} | (1 - α)}{α} < | [x]_{A}^{X^{C}} | < \frac{| [x]_{A}^{X} | (1 - β)}{β}$ .

Based on the above discussions, when probabilistic thresholds (α, β) and $| [x]_{A}^{X} |$ are given, we can define the X-based double-local conditional probability local rough set as follows:

Definition 7. Given a decision information system DIS = (U, AT = C ∪ D, V, f), X ⊆ U, A ⊆ C. ∀x ∈ U, given $| [x]_{A}^{X} |$ and probabilistic thresholds (α, β), 0 ≤ β ≤ α ≤ 1. The positive region, boundary region and negative region of the X-based double-local conditional probability local rough set are defined as:

$\begin{matrix} \begin{matrix} {DLPOS}_{A}^{(α, β)} (X) = {x | | [x]_{A}^{X^{C}} ∣ \leq \frac{| [x]_{A}^{X} | (1 - α)}{α}, x \in X} \\ \begin{matrix} DLBN D_{A}^{(α, β)} (X) = \cup {\begin{matrix} [x]_{A}^{X} \cup [x]_{A}^{X^{C}} ∣ \frac{| [x]_{A}^{X} | (1 - α)}{α} < \\ | [x]_{A}^{X^{C}} | < \frac{| [x]_{A}^{X} | (1 - β)}{β}, x \in X \end{matrix}} \\ \cup {[x]_{A}^{X^{C}} | | [x]_{A}^{X^{C}} ∣ \leq \frac{| [x]_{A}^{X} | (1 - α)}{α}, x \in X} \end{matrix} \\ DLNE G_{A}^{(α, β)} (X) = \cup {\begin{matrix} [x]_{A}^{X} \cup [x]_{A}^{X^{C}} | | [x]_{A}^{X^{C}} ∣ \geq \\ \frac{| [x]_{A}^{X} | (1 - β)}{β}, x \in U \end{matrix}} \end{matrix} \end{matrix}$ (6)

When calculating three approximation regions of the X-based double-local conditional probability local rough set according to definition 7, ∀x ∈ X, suppose $| [x]_{A}^{X} |$ is given, we only need to calculate $| [x]_{A}^{X^{C}} |$ to divide x into the positive region, boundary region or negative region. To do this, first, we initialize $[x]_{A}^{X^{C}} = \emptyset$ , then we compare x with the object y ∈ X^C one by one, if (x, y) ∈ R_A, $[x]_{A}^{X^{C}} = [x]_{A}^{X^{C}} \cup {y}$ , ${| | x |}_{A}^{X^{C}} | = | [x]_{A}^{X^{C}} ∣ + 1$ . If $| [x]_{A}^{X^{C}} | \geq \frac{| [x]_{A}^{X} | (1 - β)}{β}$ , we can stop comparing x with remaining objects in X^C and divide x into the negative region. Otherwise, we need to compare x with all objects in X^C to compute the final $| [x]_{A}^{X^{C}} |$ and divide x into the positive region or the boundary region according to $| [x]_{A}^{X^{C}} |$ . Therefore, when calculating the negative region according to the X-based double-local conditional probability local rough set, we can improve the computational efficiency by reducing the number of objects in X^C to be compared with x.

The fast algorithm for calculating approximation regions of X-based double-local conditional probability local rough set is shown in Algorithm 1:

In Algorithm 1, step 2 calculates $| [x]_{A}^{X} |$ , the time complexity is O (|X||A|). Steps 4-11 calculation $| [x]_{A}^{X^{C}} |$ , the time complexity of is O (|X^C||A|). Therefore, the time complexity of algorithm 1 is O (|X| (|X||A| + |X^C||A|)) = O (MAX (|X|²|C|, |X||X^C||C|)).

To sum up, based on the double-local conditional probability, when $| [x]_{A}^{X} |$ is given, the theorem that double-local conditional probability decreases with the increase of $| [x]_{A}^{X^{C}} |$ is proved. Based on this, the X-based double-local conditional probability local rough set and the fast algorithm for calculating approximation regions of X-based double-local conditional probability local rough set are proposed. In the following part, we investigate the monotonicity of the double-local conditional probability with the increase of $| [x]_{A}^{X} |$ when $| [x]_{A}^{X^{C}} |$ is given. Then, the X^C-based double-local conditional probability local rough set and the fast algorithm for calculating approximation regions of X^C-based double-local conditional probability local rough set are proposed.

According to Definition 6, given $| [x]_{A}^{X^{C}} |$ , the double-local conditional probability DLP (X ∣ [x] _A) increases with the increase of $| [x]_{A}^{X} |$ . The monotonicity increase theorem of the double-local conditional probability is described in Theorem 2.

Theorem 2. Given a decision information system DIS = (U, AT = C ∪ D, V, f), X ⊆ U, A ⊆ C. Given $| [x]_{A}^{X^{C}} |$ , the double-local conditional probability DLP (X ∣ [x] _A) increases with the increase of $| [x]_{A}^{X} |$ .

According to Theorem 2, it is not difficult to find that when $| [x]_{A}^{X^{C}} |$ is given, we only need to calculate $| [x]_{A}^{X} |$ to deserve DLP (X ∣ [x] _A). As DLP (X ∣ [x] _A) increases with the increase of $| [x]_{A}^{X} |$ , in the process of calculating $| [x]_{A}^{X} |$ , we compare x with objects in X one by one. If $| [x]_{A}^{X} |$ makes DLP (X ∣ [x] _A) ≥ α hold, there is no need to compare x with remaining objects in X and we can divide x into the positive region. Otherwise, we should compare x with all remaining objects in X to calculate $| [x]_{A}^{X} |$ and divide x into the negative region or the boundary region according to DLP (X ∣ [x] _A). In other words, when the probabilistic thresholds (α, β) and $| [x]_{A}^{X^{C}} |$ are given, according to the condition of $DLP (X ∣ [x]_{A}) = \frac{| [x]_{A}^{X} |}{| [x]_{A}^{X} | + | [x]_{A}^{X^{C}} |} \geq α$ , We can calculate what condition $| [x]_{A}^{X} |$ should meet when x could be divided into the positive region, namely, $| [x]_{A}^{X} | \geq | [x]_{A}^{X^{C}} | (\frac{α}{1 - α})$ . In this situation, we can stop comparing x with the objects in X and divide x into the positive region. According to the condition of $DLP (X ∣ [x]_{A}) = \frac{| [x]_{A}^{X} |}{| [x]_{A}^{X} | + | [x]_{A}^{X^{C}} |} \leq β$ , we can calculate what condition $| [x]_{A}^{X} |$ should meet when x could be divided into the negative region, namely, $| [x]_{A}^{X} | \leq | [x]_{A}^{X^{C}} | (\frac{β}{1 - β})$ . According to the condition of $β < DLP (X ∣ [x]_{A}) = \frac{| [x]_{A}^{X} |}{| [x]_{A}^{X} | + | [x]_{A}^{X^{C}} |} < α$ , we can calculate what condition $| [x]_{A}^{X} |$ should meet when x could be divided into the boundary region, namely, $| [x]_{A}^{X^{C}} | (\frac{β}{1 - β}) < | [x]_{A}^{X} | < | [x]_{A}^{X^{C}} | (\frac{α}{1 - α})$ .

Based on the above discussions, when probabilistic thresholds (α, β) and $| [x]_{A}^{X^{C}} |$ are given, we can define the X^C-based double-local conditional probability local rough set as follows:

Definition 8. Given a decision information system DIS = (U, AT = C ∪ D, V, f), X ⊆ U, A ⊆ C. ∀x ∈ U, given $| [x]_{A}^{X^{C}} |$ and probabilistic thresholds (α, β), 0 ≤ β ≤ α ≤ 1. The positive region, boundary region and negative region of the X^C-based double-local conditional probability local rough set are defined as: $\begin{matrix} \begin{matrix} {DLPOS}_{A}^{(α, β)} (X) = {x | | [x]_{A}^{X} | \geq | [x]_{A}^{X^{C}} ∣ (\frac{α}{1 - α}), x \in X} \\ \begin{matrix} DLBN D_{A}^{(α, β)} (X) = \cup {\begin{matrix} [x]_{A}^{X} \cup [x]_{A}^{X^{C}} | | [x]_{A}^{X^{C}} ∣ (\frac{β}{1 - β}) < \\ | [x]_{A}^{X} | < | [x]_{A}^{X^{C}} | (\frac{α}{1 - α}), x \in X \end{matrix}} \\ \cup {[x]_{A}^{X^{C}} | | [x]_{A}^{X} | \geq | [x]_{A}^{X^{C}} ∣ (\frac{α}{1 - α}), x \in X} \end{matrix} \\ DLNE G_{A}^{(α, β)} (X) = \cup {\begin{matrix} [x]_{A}^{X} \cup [x]_{A}^{X^{C}} | | [x]_{A}^{X} ∣ \leq \\ | [x]_{A}^{X^{C}} | (\frac{β}{1 - β}), x \in U \end{matrix}} \end{matrix} \end{matrix}$ (7)

When calculating three approximation regions of the X^C-based double-local conditional probability local rough set according to definition 8, ∀x ∈ U, suppose $| [x]_{A}^{X^{C}} |$ is given, we only need to calculate $| [x]_{A}^{X} |$ to divide x into the positive region, boundary region or negative region. To do this, first, we initialize $[x]_{A}^{X} = \emptyset$ , then we compare x with the object y ∈ X one by one, if (x, y) ∈ R_A, $[x]_{A}^{X} = [x]_{A}^{X} \cup {y}$ , $| [x]_{A}^{X} | = | [x]_{A}^{X} | + 1$ . If $| [x]_{A}^{X} | \geq | [x]_{A}^{X^{C}} | (\frac{α}{1 - α})$ , we can stop comparing x with remaining objects in X and divide x into the positive region. Otherwise, we need to compare x with all objects in X to compute the final $| [x]_{A}^{X} |$ and divide x into the negative region or the boundary region according to $| [x]_{A}^{X} |$ . Therefore, when calculating the positive region according to the X^C-based double-local conditional probability local rough set, we can improve the computational efficiency by reducing the number of objects in X to be compared with x.

The fast algorithm for calculating approximation regions of X^C-based double-local conditional probability local rough set is shown in Algorithm 2:

In Algorithm 2, step 2 calculates $| [x]_{A}^{X^{C}} |$ , the time complexity is O (|X^C| * |A|). Steps 4-13 calculation $| [x]_{A}^{X} |$ , the time complexity of is O (|X| * |A|). Therefore, the time complexity of algorithm 2 is O (|X| * (|X^C| * |A| + |X| * |A|)) = O (MAX (|X|²|C|, |X||X^C||C|)).

Both algorithm 1 and algorithm 2 can quickly calculate three approximation regions of the double-local conditional probability local rough set. Although the time complexity of algorithm 1 and algorithm 2 is the same, their actual computing time is different. According to algorithm 1, ∀x ∈ X, we need to compare x with all objects in X to compute $| [x]_{A}^{X} |$ . However, when we calculate $| [x]_{A}^{X^{C}} |$ , if x belongs to the negative region, we do not need to compare x with all objects in X^C, thus the number of objects to be compared with x is reduced. According to algorithm 2, ∀x ∈ X, we need to compare x with all objects in X^C to compute $| [x]_{A}^{X^{C}} |$ . However, when we calculate $| [x]_{A}^{X} |$ , if x belongs to the positive region, we do not need to compare x with all objects in X, thus the number of objects to be compared with x is reduced. Therefore, in practical applications, we can choose algorithm 1 or algorithm 2 according to the size of |X| and |X^C| to further improve computational efficiency. If |X| < |X^C|, we choose algorithm 1. If |X| > |X^C|, we choose algorithm 2. If |X| = |X^C|, it is free to choose algorithm 1 or algorithm 2. The fast algorithm for calculating approximation regions of double-local conditional probability based local rough set is given in Algorithm 3:

In the following part, we use an example to illustrate the fast algorithm for calculating approximation regions of double-local conditional probability based local rough set (FADLLRS).

Example 1. Given a information system DIS = (U, AT = C ∪ D, V, f), as shown in Table 1, where U ={ x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀, x₁₁, x₁₂ }, A = {a, b} is the condition attribute sets, d is the decision attribute. Let X ={ x₁, x₂, x₃ }, X^C ={ x₄, x₅, x₆, x₇, x₈, x₉, x₁₀, x₁₁, x₁₂ }, α = 0.7, β = 0.3.

Table 1

A decision information system

U	a	b	d
x ₁	red	big	1
x ₂	black	average	1
x ₃	black	average	1
x ₄	red	big	2
x ₅	red	big	2
x ₆	red	big	2
x ₇	black	average	2
x ₈	black	small	2
x ₉	black	small	2
x ₁₀	blue	big	2
x ₁₁	blue	big	2
x ₁₂	blue	average	2

The fast algorithm for calculating approximation regions of double-local conditional probability based local rough set (FADLLRS) is used to calculate three approximation regions of Table 1. Because |X| < |X^C|, algorithm 1 is selected. The detailed calculation process of algorithm 1 is described as follows:

For x₁ ∈ X, first, we calculate the local equivalence class of x₁ with respect to X, ${[x_{1}]}_{A}^{X} = {x_{1}}$ , $| {[x_{1}]}_{A}^{X} | = 1$ . In terms of $| {[x_{1}]}_{A}^{X} | = 1$ and probability thresholds α = 0.7, β = 0.3, we can calculate $\frac{| {[x_{1}]}_{A}^{X} | (1 - α)}{α} = 0.43$ , $\frac{| {[x_{1}]}_{A}^{X} | (1 - β)}{β} = 2.33$ . Then, initialize ${[x_{1}]}_{A}^{X^{C}} = \emptyset$ and start comparing x₁ with the objects in X^C one by one. As (x₁, x₄) ∈ R_A, ${[x_{1}]}_{A}^{X^{C}} = {[x_{1}]}_{A}^{X^{C}} \cup {x_{4}}$ , $| {[x_{1}]}_{A}^{X^{C}} | = 1 < 2.33$ , we need to continue comparing x₁ with the remaining objects in X^C one by one. As (x₁, x₅) ∈ R_A, ${[x_{1}]}_{A}^{X^{C}} = {[x_{1}]}_{A}^{X^{C}} \cup {x_{5}}$ , $| {[x_{1}]}_{A}^{X^{C}} | = 2 < 2.33$ , we need to continue comparing x₁ with the remaining objects in X^C one by one. As (x₁, x₆) ∈ R_A, ${[x_{1}]}_{A}^{X^{C}} = {[x_{1}]}_{A}^{X^{C}} \cup {x_{6}}$ , $| {[x_{1}]}_{A}^{X^{C}} | = 3 > 2.33$ , we could divide x₁ into the negative region and stop comparing x₁ with the remaining objects in X^C. Therefore, x₁ is compared with six objects in U totally. If according to definition 4, x₁ needs to be compared with all twelve objects in U. Thus, six objects were avoided to be compared with x₁ by using the proposed algorithm.

For x₂ ∈ X, first, we calculate the local equivalence class of x₂ with respect to X, ${[x_{2}]}_{A}^{X} = {x_{2}, x_{3}}$ , $| {[x_{2}]}_{A}^{X} | = 2$ . In terms of $| {[x_{2}]}_{A}^{X} | = 2$ and probability thresholds α = 0.7, β = 0.3, we can calculate $\frac{| {[x_{2}]}_{A}^{X} | (1 - α)}{α} = 0.86$ , $\frac{| {[x_{2}]}_{A}^{X} | (1 - β)}{β} = 4.67$ . Then, initialize ${[x_{2}]}_{A}^{X^{C}} = \emptyset$ and start comparing x₂ with the objects in X^C one by one. As x₄, x₅ and x₆ are not equivalent to x₂, ${[x_{2}]}_{A}^{X^{C}} = \emptyset$ , $| {[x_{2}]}_{A}^{X^{C}} | = 0 < 4.67$ , we need to continue comparing x₂ with the remaining objects in X^C one by one. (x₂, x₇) ∈ R_A, ${[x_{2}]}_{A}^{X^{C}} = {[x_{2}]}_{A}^{X^{C}} \cup {x_{7}}$ , $| {[x_{2}]}_{A}^{X^{C}} | = 1 < 4.67$ , we need to continue comparing x₂ with the remaining objects in X^C one by one. As x₈, x₉, x₁₀, x₁₁ and x₁₂ are not equivalent to x₂, ${[x_{2}]}_{A}^{X^{C}} = {x_{7}}$ remains unchanged. As x₂ has been compared with all objects in X^C, and $0.86 < | {[x_{2}]}_{A}^{X^{C}} | < 4.67$ , we should divide x₂ into the boundary region. Therefore, x₂ is compared with all objects in U. Compared with the calculation according to definition 4, the proposed algorithm does not reduce the number of objects to be compared with x₂.

For x₃ ∈ X, x₃ is equivalent to x₂. Therefore, x₃ is compared with all objects in U and x₃ should be divided into the boundary region. Compared with the calculation according to definition 4, the proposed algorithm does not reduce the number of objects to be compared with x₃.

To sum up, the calculation results of FADLLRS are: $DLPO S_{A}^{(0.7, 0.3)} (X) = \emptyset$ , $DLBN D_{A}^{(0.7, 0.3)} (X) = {x_{2}, x_{3}, x_{7}}$ , $DLNE G_{A}^{(0.7, 0.3)} (X) = {x_{1}, x_{4}, x_{5}, x_{6}, x_{8}, x_{9}, x_{10}, x_{11}, x_{12}}$ . The number of comparisons between objects in the universe is 30. Based on existing methods to calculate approximation regions of local rough sets, the number of comparisons between objects in the universe is 36. Therefore, FADLLRS can effectively reduce the number of comparisons between objects in the universe and improve the computational efficiency.

4 Experiments

In this section, 9 datasets from UCI machine learning data repository [36] are selected to verify the effectiveness of the fast algorithm for calculating approximation regions of double-local conditional probability based local rough set. The datasets are described in Table 2.

Table 2
Description of the datasets

ID Datasets Number of objects Number of attributes Number of classes

1 Blood Transfusion Service Center (BTSC) 748 4 2

2 Wilt (WT) 4889 5 2

3 Parkinsons Telemonitoring (PT) 5456 24 4

4 Page Blocks Classification (PBC) 5473 10 5

5 Dry Bean Dataset (DBD) 13611 16 7

6 HTRU2(HU) 17898 8 2

7 MAGIC Gamma Telescope (MGT) (WDG) 19020 10 2

8 AVILA(AVILA) 20867 10 12

9 Shuttle (SE) 58000 9 5

ID	Datasets	Number of objects	Number of attributes	Number of classes
1	Blood Transfusion Service Center (BTSC)	748	4	2
2	Wilt (WT)	4889	5	2
3	Parkinsons Telemonitoring (PT)	5456	24	4
4	Page Blocks Classification (PBC)	5473	10	5
5	Dry Bean Dataset (DBD)	13611	16	7
6	HTRU2(HU)	17898	8	2
7	MAGIC Gamma Telescope (MGT) (WDG)	19020	10	2
8	AVILA(AVILA)	20867	10	12
9	Shuttle (SE)	58000	9	5

In these datasets, Blood Transfusion Service Center is a categorical dataset, and the others are continuous datasets. The continuous dataset is discretized into categorical ones using equal-frequency discretization method [37]. We compare our proposed algorithm with two methods, including the classical method for calculating approximation regions of the local rough set [16] and the method for calculating approximation regions of the local rough set based on double-local rough set [38]. To simplify the discussion, the proposed fast algorithm for calculating approximation regions of double-local conditional probability based local rough set is denoted as FADLLRS, the classical method for calculating approximation regions of the local rough set is denoted as CLRS, and the method for calculating approximation regions of the local rough set based on double-local rough set is denoted as DLLRS. We implement experiments on a PC with Windows 10, Intel (R) Core (TM) i5-11400 CPU 2.60 GHz and 16 GB memory. The programming language is Python on the platform of IDEA 2018.

We implement two groups of experiments. In the first group of experiments, given a pair of probability thresholds and a set of target concepts with different sizes, we compare the running time of FADLLRS, CLRS and DLLRS to show the impact of different sizes of the target concept on the running time. In the second group of experiments, given a target concept and a set of probability threshold pairs, we compare the running time of FADLLRS, CLRS and DLLRS to show the impact of different probability thresholds on the running time. We run each experiment 100 times and take the average result.

Given a pair of probability thresholds: α = 0.7, β = 0.3. To compare the running time of FADLLRS, CLRS and DLLRS with different sizes of the target concept, 10%, 20%, …, 90% of the objects in the universe are selected randomly as the target concept. The running time of FADLLRS, CLRS and DLLRS with different sizes of the target concept is shown in Fig. 2.

Fig. 2

Running time of FADLLRS, CLRS and DLLRS with different sizes of the target concept.

In Fig. 2, the x-axis represents the size of the target concept, the y-axis represents the running time. Figure 1 shows that FADLLRS is generally superior to CLRS and DLLRS with different sizes of the target concept.With an increase of the size of the target concept, the running time of CLRS and DLLRS increases monotonously. Moreover, the running time of FADLLRS first increases and then decreases with an increase of the size of the target concept, which is a convex line in Fig. 2. The reason is analyzed as follows.

According to FADLLRS, when the size of the target concept is less than the size of the complementary set of target concept, FADLLRS executes algorithm 1 and the running time of algorithm 1 increases with the increasing size of the target concept. When the size of the target concept is more than the size of the complementary set of target concept, FADLLRS executes algorithm 2 and the running time of algorithm 2 decreases with the increasing size of the target concept. So the running time of FADLLRS first increases and then decreases with an increase of the size of the target concept.

In the following part, given a target concept and a set of probability threshold pairs, we compare the running time of FADLLRS, CLRS and DLLRS with different probability threshold pairs. When calculating the approximation regions by FADLLRS, ∀x ∈ U, assume that $| [x]_{A}^{X} |$ is given, if $| [x]_{A}^{X^{C}} | \geq \frac{| [x]_{A}^{X} | (1 - β)}{β}$ , we can stop comparing x with the objects in X^C and divide x into the negative region. The larger the value of $\frac{| [x]_{A}^{X} | (1 - β)}{β}$ is, the more of objects in X^C needed to be compared with x, and the longer the running time of FADLLRS. Moreover, $\frac{| [x]_{A}^{X} | (1 - β)}{β}$ increases with the decrease of β, so we set β from 0.5 and gradually decreases to 0.05 with step of 0.05. ∀x ∈ U, assume that $| [x]_{A}^{X^{C}} |$ is given, if $| [x]_{A}^{X} | \geq | [x]_{A}^{X^{C}} | (\frac{α}{1 - α})$ , we can stop comparing x with the objects in X and divide x into the positive region. The larger the value of $| [x]_{A}^{X^{C}} | (\frac{α}{1 - α})$ is, the more of objects in X needed to be compared with x, and the longer the running time of FADLLRS. Moreover, $| [x]_{A}^{X^{C}} | (\frac{α}{1 - α})$ increases with the increase of α, so we set α from 0.5 and gradually increases to 0.95 with step of 0.05. Consequently, a set of probability threshold pairs are given: α₁ = 0.50 and β₁ = 0.50; α₂ = 0.55 and β₂ = 0.45; α₃ = 0.60 and β₃ = 0.40; α₄ = 0.65 and β₄ = 0.35; α₅ = 0.70 and β₅ = 0.30; α₆ = 0.75 and β₆ = 0.25; α₇ = 0.80 and β₇ = 0.20;α₈ = 0.85 and β₈ = 0.15; α₉ = 0.90 and β₉ = 0.10; α₁₀ = 0.95 and β₁₀ = 0.05. The first decision class of each dataset is used as the target concept. With different probability thresholds, the running time of FADLLRS, CLRS and DLLRS is shown in Fig. 3.

Fig. 3

Running time of FADLLRS, CLRS and DLLRS with different probability thresholds.

In Fig. 3, the x-axis represents the probability thresholds (α, β) and the y-axis represents the running time. Figure 3 shows that the running time of CLRS and DLLRS does not change with different probability thresholds. The running time of FADLLRS increases with an increase of α and a decrease of β. However, with different probability thresholds, the running time of the proposed FADLLRS is significantly less than that of CLRS and DLLRS on all datasets, which indicates that FADLLRS is still superior to CLRS and DLLRS with different probability thresholds.

5 Conclusions

The local rough set is an important extended model of the rough set theory. The calculation of approximation regions is a crucial issue of local rough sets. However, the time complexity of existing methods for calculating approximation regions of local rough sets is high. Therefore, this paper proposes a double-local conditional probability based fast calculation method. Firstly, based on the idea of “divide and conquer”, we propose the double-local equivalence class. Based on the double-local equivalence class, the definition of double-local conditional probability is given. Finally, a fast algorithm for calculating approximation regions of double-local conditional probability based local rough set is proposed. Experimental results show the effectiveness of the proposed algorithm. In future work, on the one hand, considering the dynamic changes in the information system, we will further study the incremental algorithm for calculating approximation regions of local rough set when the decision information system varies dynamically with objects, attributes, or attribute values. On the other hand, considering the flourishing development of multi-criteria classification [39, 40], We will study the application of fast algorithms in multi-criteria classification.

Footnotes

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 62076002, 61402005, 61972001), the Natural Science Foundation of Anhui Province, China (No. 2008085MF194, 1308085QF114, 1908085MF188), the Higher Education Natural Science Foundation of Anhui Province, China (No. KJ2013A015).

Conflict of Interest/Competing Interests

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Consent for publication

Manuscript is approved by all authors for publication.

Availability of data and materials

Data and materials will be made available on request.

Code availability

Code will be made available on request.

Authors’ contributions

Yi Xu: Conceptualization, Methodology, Supervision, Writing –original draft. Meng Zhou: Software, Data curation, Writing –review & editing.

References

Zdzisław Pawlak , Rough sets, International Journal of Computer & Information Sciences 11(5) (1982), 341–356.

Zdzislaw Pawlak , Jerzy Grzymala-Busse , Roman Slowinski and Wojciech Ziarko , Rough sets, Communications of the ACM 38(11) (1995), 88–95.

Yao

Y.Y.

, Generalized rough set models, Rough Sets in Knowledge Discovery 1 (1998), 286–318.

Kai Zhang , Jianming Zhan and Wei-Zhi Wu , On multicriteria decision-making method based on a fuzzy rough set model with fuzzy rough set model with fuzzy neighborhoods, IEEE Transactions on Fuzzy Systems 29(9) (2020), 2491–2505.

Xiao Zhang , Changlin Mei , Degang Chen , Yanyan Yang and Jinhai Li , Active incremental feature selection using a fuzzy rough- set-based information entropy, IEEE Transactions on Fuzzy Systems 28(5) (2019), 901–915.

Wenbin Pei , Bing Xue , Lin Shang and Mengjie Zhang , Detecting overlapping areas in unbalanced high-dimensional data using neighborhood rough set and genetic programming, IEEE Transactions on Evolutionary Computation, pages 1–1, 2022.

Xianyong Zhang and Yiyu Yao , Tri-level attribute reduction in rough set theory, Expert Systems with Applications 116187 (2022), 190.

Hexiang Bai , Deyu Li , Yong Ge , JinfengWang and Feng Cao , Spatial rough set-based geographical detectors for nominal target variables, Information Sciences 586 (2022), 525–539.

Yiyu Yao , Probabilistic rough set approximations, International Journal of Approximate Reasoning 49(2) (2008), 255–271.

10.

Yiyu Yao , Salvatore Greco and Roman Słowiński, Probabilistic rough sets, In Springer handbook of computational intelligence, pages 387–411. Springer, 2015.

11.

Yao

Y.Y.

, Wong

S.K.M.

and Lingras

, Adecision-theoretic rough set model, methodologies for intelligent systems 5, zw ras, m. zemankova and ml emrich, 1990.

12.

Yiyu Yao , Decision-theoretic rough set models, In International conference on rough sets and knowledge technology, pages 1–12. Springer, 2007.

13.

Hongmei Chen , Tianrui Li , Chuan Luo , Shi-Jinn Horng and GuoyinWang , A decision-theoretic rough set approach for dynamic data mining, IEEE Transactions on fuzzy Systems 23(6) (2015), 1958–1970.

14.

Wojciech Ziarko , Variable precision rough set model, Journal of Computer and System Sciences 46(1) (1993), 39–59.

15.

Dominik Slezak and Wojciech Ziarko , The investigation of the bayesian rough set model, International Journal of Approximate Reasoning 40(1–2) (2005), 81–91.

16.

Yuhua Qian , Xinyan Liang , Qi Wang , Jiye Liang , Bing Liu , Andrzej Skowron , Yiyu Yao , Jianmin Ma and Chuangyin Dang , Local rough set: a solution to rough data analysis in big data, International Journal of Approximate Reasoning 97 (2018), 38–63.

17.

Yuhua Qian , Xinyan Liang , Guoping Lin , Qian Guo and Jiye Liang , Local multigranulation decision-theoretic rough sets, International Journal of Approximate Reasoning 82 (2017), 119–137.

18.

Qi Wang , Yuhua Qian , Xinyan Liang , Qian Guo and Jiye Liang , Local neighborhood rough set, Knowledge-Based Systems 153 (2018), 53–64.

19.

Yanting Guo , Eric Tsang

, Weihua Xu and Degang Chen , Local logical disjunction double-quantitative rough sets, Information Sciences 500 (2019), 87–112.

20.

Xianyong Zhang and Duoqian Miao , Two basic doublequantitative rough set models of precision and grade and their investigation using granular computing, International Journal of Approximate Reasoning 54(8) (2013), 1130–1148.

21.

Joseph Herbert

and JingTao Yao , Game-theoretic rough sets, Fundamenta Informaticae 108(3–4) (2011), 267–286.

22.

Yixing Chen and JingTao Yao , Sentiment analysis using partof- speech-based feature extraction and game-theoretic rough sets. In 2021 International Conference on Data Mining Workshops (ICDMW), pages 110–117, 2021.

23.

Libo Zhang , Huaxiong Li , Xianzhong Zhou , Bing Huang and Lin Shang , Cost-sensitive sequential three-way decision for face recognition. In Rough Sets and Intelligent Systems Paradigms, pages 375–383. Springer, 2014.

24.

Sebastian Maldonado , Georg Peters and Richard Weber , Credit scoring using three-way decisions with probabilistic rough sets, Information Sciences 507 (2020), 700–714.

25.

Mamata Wagh and Pradipta Kumar Nanda , Decision-theoretic rough sets based automated scheme for object and background classification in unevenly illuminated images, Applied Soft Computing 119 (2022), 108596.

26.

Roberto Abbruzzese , Angelo Gaeta , Vincenzo Loia , Luigi Lomasto and Francesco Orciuoli , Detecting influential news in online communities: An approach based on hexagons of opposition generated by three-way decisions and probabilistic rough sets, Information Sciences 578 (2021), 364–377.

27.

Jingjing Xie , Bao Qing Hu and Haibo Jiang , A novel method to attribute reduction based on weighted neighborhood probabilistic rough sets, International Journal of Approximate Reasoning 144 (2022), 1–17.

28.

Xi-Ao Ma , Fuzzy entropies for class-specific and classification-based attribute reducts in three-way probabilistic rough set models, International Journal of Machine Learning and Cybernetics 12(2) (2021), 433–457.

29.

Jiali He , Liangdong Qu , Zhihong Wang , Yiying Chen , Damei Luo and Ching-Feng Wen , Attribute reduction in an incomplete categorical decision information system based on fuzzy rough sets, Artificial Intelligence Review, pages 1–36, 2022.

30.

Qinghua Hu , Lingjun Zhang , Yucan Zhou and Witold Pedrycz , Large-scale multimodality attribute reduction with multikernel fuzzy rough sets, IEEE Transactions on Fuzzy Systems 26(1) (2017), 226–238.

31.

Tareq M Al-shami , An improvement of rough sets’ accuracy measure using containment neighborhoods with a medical application, Information Sciences 569 (2021), 110–124.

32.

Tareq Al-shami

and Davide Ciucci , Subset neighborhood rough sets, Knowledge-Based Systems 237 (2022), 107868.

33.

Tareq Al-Shami

, Maximal rough neighborhoods with a medical application, Journal of Ambient Intelligence and Humanized Computing, pages 1–12, 2022.

34.

Tareq Al-shami

, Topological approach to generate new rough set models, Complex & Intelligent Systems 8(5) (2022), 4101–4113.

35.

Tareq Al-shami

, Improvement of the approximations and accuracy measure of a rough set using somewhere dense sets, Soft Computing 25(23) (2021), 14449–14460.

36.

Uci machine learning repository. 2023. URL http://archive.ics.uci.edu/datasets.

37.

John Ching

, Andrew Wong

K.C.

and Keith Chan

C.C.

, Class-dependent discretization for inductive learning from continuous and mixed-mode data, IEEE Transactions on Pattern Analysis and Machine Intelligence 17(7) (1995), 641–651.

38.

Guoqiang Wang , Tianrui Li , Pengfei Zhang , Qianqian Huang and Hongmei Chen , Double-local rough sets for efficient data mining, Information Sciences 571 (2021), 475–498.

39.

Zhuolin Li , Zhen Zhang and Wenyu Yu , Consensus reaching for ordinal classification-based group decision making with heterogeneous preference information, Journal of the Operational Research Society, pages 1–22, 2023.

40.

Zhen Zhang and Zhuolin Li , Consensus-based topsis-sort-b for multi-criteria sorting in the context of group decision- making, Annals of Operations Research, pages 1–28, 2022.