Gaussian kernel fuzzy rough based attribute reduction: An acceleration approach

2.1 Classical fuzzy rough set

Generally speaking, a decision system can be described as DS =< U, A, d >, in which U is the finite set of samples, also known as universe, A is the set of condition attributes, and d is the decision attribute. ∀x ∈ U, a (x) denotes the value of sample x over the attribute a ∈ A, while d (x) indicates the label of sample x. Following the decision attribute d, an equivalence relation over universe U can be obtained by d such that IND _d  = {(x, y) ∈ U × U : d (x) = d (y)}. Immediately, a partition U/IND _d  = {X₁, X₂, …, X _q } over universe U can be induced, in which X _p  (X _p  ∈ U/IND _d ) is the p-th decision class consisting of samples with the same label.

In rough set theory [32, 33], the indiscernibility relation [35] can be regarded as the basic mechanism for granulating the universe, and then the corresponding results of granulation can be used to approximate the target concept, i.e., the decision class. However, if the considered data is continuous, then such model may be powerless in handling and analysing these data. This is mainly because the indiscernibility relation is only suitable for dealing with categorical data. In view of this, various approaches have been proposed to expand classical rough set [11, 60] with respect to different requirements. Presently, the concept of fuzzy rough set has been widely concerned and can be regarded as one of the effective rough sets for analyzing continuous data. An important reason is that the fuzzy rough set is constructed based on the similarity among samples and it will not change the distribution of the raw data. As what has been reported in Reference [13], the Gaussian kernel can be employed to measure the similarity among samples and then such approach has formed a bridge between rough sets and kernel methods.

Given a decision system DS =< U, A, d >, ∀B ⊆ A, the similarity between arbitrary two samples can be measured by the Gaussian kernel function such that R B σ ( x , y ) = exp ( - ∥ x - y ∥ B 2 2 σ 2 ) , in which ∥x - y ∥  _B is the Euclidean distance between samples x and y, i.e., ∥ x - y ∥ B = ∑ a ∈ B ( a ( x ) - a ( y ) ) 2 , and σ is the Gaussian kernel parameter. Obviously, given B ⊆ A, ∀x, y ∈ U, different kernel parameters will generate different similarities between x and y. Moreover, the Gaussian kernel based fuzzy relation can be denoted as R B σ = { R B σ ( x , y ) : ∀ x , y ∈ U } . Immediately, the fuzzy rough set of X _p  ∈ U/IND _d can be defined as follows.

Definition 1. [10] Given a decision system DS =< U, A, d >, ∀B ⊆ A and ∀x ∈ U, the fuzzy rough lower and upper approximations of X _p can be respectively denoted as the following membership functions R B σ _ X p ( x ) = inf y ∈ U - X p { 1 - R B σ ( x , y ) } ,(1) R B σ ¯ X p ( x ) = sup y ∈ X p { R B σ ( x , y ) } ,(2) in which R B σ is the fuzzy relation induced by Gaussian kernel and B.

Following Definition 1, it is not difficult to observe that the membership degree of x ∈ U belonging to fuzzy rough lower approximation of X _p is actually the fuzzy dissimilarity between x and its nearest sample from U - X _p . Similarly, the membership degree of x ∈ U belonging to fuzzy rough upper approximation of X _p is actually the fuzzy similarity between x and its nearest sample from X _p [10].

Following Definition 1, the operators play an essential role in deriving fuzzy rough approximations, it follows that different operators will result in different fuzzy rough approximations, and then different fuzzy rough set models can be constructed. Therefore, Hu et al. [12] have not only analyzed the inherent limitations of classical fuzzy rough set, but also investigated several operators, and further proposed corresponding fuzzy rough set models. The detailed definitions with respect to these operators are shown as follows.

Definition 2. [12] Given a random variable X, and the observed values of its t samples, which are denoted as x₁, x₂, …, x _t , assuming that x₁ < x₂ < … < x _t . Then the k - trimmed minimum of X is x_k+1; the k - trimmed maximum of X is x_t-k; k - mean minimum of X is ∑ i = 1 k x i k ; the k - mean maximum of X is ∑ i = t - k + 1 t x i k ; the k - median minimum of X is median (x₁, x₂, …, x _k ); the k - median maximum of X is median (x_t-k+1, x_t-k+2, …, x _t ), in which median(·) is a function to calculate the median value. These operators can be respectively denoted as min k - trimmed ( X ) , max k - trimmed ( X ) , min k - mean ( X ) , max k - mean ( X ) , min k - median ( X ) and max k - median ( X ) .

Following the operators shown in Definition 2, Hu et al. [12] have proposed three fuzzy rough set models which are referred to as k-trimmed, k-mean and k-median fuzzy rough sets, respectively. The detailed definitions of fuzzy rough approximations with respect to these three models can be formulated as follows.

Definition 3.[12] Given a decision system DS =< U, A, d >, ∀B ⊆ A and ∀x ∈ U, the fuzzy rough lower and upper approximations of X _p with respect to different operators can be respectively denoted as the following membership functions R B σ _ k - trimmed X p ( x ) = min k - trimmed y ∈ U - X p { 1 - R B σ ( x , y ) } ,(3) R B σ ¯ k - trimmed X p ( x ) = max k - trimmed y ∈ X p { R B σ ( x , y ) } ,(4) R B σ _ k - mean X p ( x ) = min k - mean y ∈ U - X p { 1 - R B σ ( x , y ) } ,(5) R B σ ¯ k - mean X p ( x ) = max k - mean y ∈ X p { R B σ ( x , y ) } ,(6) R B σ _ k - median X p ( x ) = min k - median y ∈ U - X p { 1 - R B σ ( x , y ) } ,(7) R B σ ¯ k - median X p ( x ) = max k - median y ∈ X p { R B σ ( x , y ) } ,(8) in which R B σ is the fuzzy relation induced by Gaussian kernel and B,

Definition 4.[10] Given a decision system DS =< U, A, d >, ∀B ⊆ A and based on the classical fuzzy rough set, the fuzzy positive region of d with respect to B is defined as POS B σ ( d ) = ⋃ p = 1 q R B σ _ X p .(9)

The fuzzy positive region of decision attribute with respect to condition attribute set shown in Definition 4 is actually a fuzzy set, which is derived by the union of fuzzy rough lower approximations of decision classes. Additionally, the fuzzy positive regions with respect to different fuzzy rough sets can be obtained by replacing the counterparts in Equation (9) with fuzzy rough lower approximations based on corresponding operators.

Definition 5.[10] Given a decision system DS =< U, A, d >, ∀B ⊆ A and based on the classical fuzzy rough set, the fuzzy dependency of d with respect to B is defined as γ B σ ( d ) = ∑ x ∈ U POS B σ ( d ) ( x ) | U | ,(10) in which |X| is the cardinality of the set X, and POS B σ ( d ) ( x ) = sup { R B σ _ X p ( x ) : ∀ X p ∈ U / IND d } .

The fuzzy dependency shown in Definition 5 reflects the average degree of the samples which certainly belong to decision classes. Obviously, 0 ≤ γ B σ ( d ) ≤ 1 holds. Similarly, the fuzzy dependencies with respect to different fuzzy rough sets can be derived by replacing the counterparts in Equation (10) with fuzzy positive regions based on corresponding operators.

Definition 6. Given a decision system DS =< U, A, d >, ∀B ⊆ A, B is regarded as a γ-reduct if and only if:

γ B σ ( d ) = γ A σ ( d ) ;

Following Definition 6, it is not difficult to observe that the first condition aims to find all the relevant attributes, while the second condition guarantees that no redundant attributes are contained in the obtained reduct. Obviously, the fuzzy dependency is important in the attribute reduction shown in Definition 6, and the fuzzy dependency can be employed to design significance function, which is used for evaluating the significance of the candidate attribute. The definition of significance function can be formulated as follows.

Definition 7. Given a decision system DS =< U, A, d >, ∀B ⊂ A, and ∀a ∈ A - B, the significance of attribute a with respect to fuzzy dependency is Sig σ ( a , B , d ) = γ B ∪ { a } σ ( d ) - γ B σ ( d ) .(11)

Sig ^σ  (a, B, d) can reflect the variation of fuzzy dependency when attribute a is added into B, therefore, the higher value of Sig ^σ  (a, B, d) is, the more important the attribute a will be. And such significance function can be employed in the forward greedy searching algorithm to compute γ-reduct. Immediately, the main steps of forward greedy searching for computing γ-reduct can be described as follows.

Potential reduct B is initialized to an empty set.

Based on the above steps, and to simplify our discussion, the detailed algorithm to compute γ-reduct based on classical fuzzy rough set can be described as follows, and the algorithms to compute γ-reduct with respect to different fuzzy rough set models can be analogized.

Algorithm 1. Forward greedy searching algorithm to compute γ-reduct

Inputs: DS =< U, A, d >, kernel parameter σ, threshold ɛ ∈ [0, 1);

Outputs: A γ-reduct B.

1. B← ∅;

2. Compute γ A σ ( d ) ;

3. Do

    1) ∀a ∈ A - B, compute Sig ^σ  (a, B, d);

    2) Select b such that Sig ^σ  (b, B, d) = max {Sig ^σ  (a, B, d) : ∀ a ∈ A - B};

    3) B ← B ∪ {b};

    4) Compute γ B σ ( d ) ;

While γ A σ ( d ) - γ B σ ( d ) > ɛ · γ A σ ( d )

4. Do

    C ← B;

    For each c ∈ B

      Compute γ B - { c } σ ( d ) ;

      If γ A σ ( d ) - γ B - { c } σ ( d ) ≤ ɛ · γ A σ ( d )

        B ← B - {c};

      End

    End

While C ≠ B

5. Return B.

Following Algorithm 1, it should be noticed that the fuzzy dependency derived by arbitrary attribute subset will be less than that induced by the whole attribute set. This is mainly because the Gaussian kernel based similarity among samples will decrease with the growth of number of the used attributes, and then the membership degrees of samples belonging to the fuzzy rough lower approximations will be increased, which will lead to the increasing of value of fuzzy dependency. That is, the value of fuzzy dependency increases with the growth of number of the considered attributes. Consequently, the threshold ɛ in Algorithm 1 is employed to avoid the case that no attribute can be removed from the raw attribute set.

Moreover, it is not difficult to observe that all candidate attributes should be scanned in the process of searching reduct through using Algorithm 1, and the main time consumption of such algorithm lies in the evaluation of significance of candidate attribute. It follows that the time complexity of Algorithm 1 is O (|U|² · |A|²).

3.1 Problem description

Following discussions above, it is not difficult to observe that one and only one parameter has been considered in most of previous researches related to Gaussian kernel based fuzzy rough attribute reduction. However, it should be emphasised that there are some inherent limitations in one and only one parameter based attribute reduction, as what has been pointed out in the part of Introduction, and these limitations can be attributed to the following two points: 1) single parameter based attribute reduction may result in the lack of better adaptability to granularity world; 2) single parameter based attribute reduction may not be suitable for observing the variation tendency of generalization performance of derived reduct.

Consequently, to overcome the inherent limitations mentioned above, it is necessary to search reducts over a set of different parameters.

3.2 Naive approach for attribute reduction

Regarding the problem stated above, given a set of considered parameters, a naive approach can be directly designed: compute reducts repeatedly through using Algorithm 1 over a set of different parameters. Immediately, the main steps of naive approach for searching reducts over a set of considered parameters can be described as follows.

The set of γ-reducts 𝔹 over a set of kernel parameters T is initialized to an empty set.

Based on the above steps, and to simplify our discussion, take the classical fuzzy rough set as an example, the detailed naive algorithm to compute γ-reducts over a set of parameters is shown as follows.

Algorithm 2. Naive algorithm to compute γ-reducts over a set of parameters

Inputs: DS =< U, A, d >, a set of kernel parameters T, threshold ɛ ∈ [0, 1);

Outputs: A set of γ-reducts 𝔹 .

1. 𝔹 ← ∅ ;

2. For each σ ∈ T

       1) Compute reduct B based on σ through using Algorithm 1;

       2) Add B into 𝔹 ;

  End

3. Return 𝔹 .

Following Algorithm 2, it should be noticed that the output result is a set of reducts instead of one and only one reduct. Moreover, it is not difficult to reveal that Algorithm 2 is mainly performed through repeating the process of Algorithm 1. It follows that the time complexity of Algorithm 2 is O (n · |U|² · |A|²), where n is the number of kernel parameter in T.

3.3 Forward acceleration strategy for attribute reduction

Following Algorithm 2, it is trivial to know that the process of naive approach for searching reducts based multiple parameters is time-consuming, especially the number of the considered parameters is great. Immediately, how to accelerate the process of computing reducts over multiple parameters has become an open topic. For such purpose, an acceleration approach will be designed as follows. Given a decision system DS, if two kernel parameters are considered such that σ₁ ≤ σ₂, then the main mechanism of our forward acceleration strategy is that the process of finding the σ₂ based reduct B₂ is in terms of the σ₁ based reduct B₁. In detail, to search the reduct with respect to σ₂, we begin our searching with σ₁ based reduct instead of an empty set. Correspondingly, the main steps in our forward acceleration strategy can be summarized as follows.

Compute the σ₁ based reduct B₁ through using Algorithm 1.

Through applying the above mechanism to the searching of multiple parameters based reducts, and based on classical fuzzy rough set, a forward acceleration algorithm to compute γ-reudcts over a set of parameters can be designed as follows.

Algorithm 3. Forward acceleration algorithm to compute γ-reducts over a set of parameters

Inputs: DS =< U, A, d >, a set of kernel parameters T, threshold ɛ ∈ [0, 1);

Outputs: A set of γ-reducts 𝔹 .

1. 𝔹 ← ∅ ;

2. Sort kernel parameters in T such that T = {σ₁, σ₂, …, σ _n }, in which σ₁ ≤ σ₂ ≤ … ≤ σ _n ;

3. Compute reduct B₁ based on σ₁ through using Algorithm 1, and then add B₁ into 𝔹 ;

4. For s = 2 to n

    1) B _s  ← B_s-1;

    2) If B _s is the σ _s based reduct

        Add B _s into 𝔹 ;

        s ← s + 1, and go to 1);

      Else

        Compute γ A σ s ( d ) , and go to 3);

      End

    3) Do

      num 1) ∀a ∈ A - B _s , compute Sig ^{σ _s}  (a, B _s , d);

      num 2) Select b such that Sig ^{σ _s}  (b, B _s , d) = max {Sig ^{σ _s}  (a, B _s , d) : ∀ a ∈ A - B _s };

      num 3) B _s  ← B _s  ∪ {b};

        num 4) Compute γ B s σ s ( d ) ;

      While γ A σ s ( d ) - γ B s σ s ( d ) > ɛ · γ A σ s ( d )

    4) Do

        C ← B _s ;

        For each c ∈ B _s

          Compute γ B s - { c } σ s ( d ) ;

          If γ A σ s ( d ) - γ B s - { c } σ s ( d ) ≤ ɛ · γ A σ s ( d )

            B _s  ← B _s  - {c};

          End

        End

      While C ≠ B _s

    5) Add B _s into 𝔹 ;

  End

5. Return 𝔹

Following Algorithm 3, it should be noticed that the first parameter based reduct is still derived by using Algorithm 1, it follows that the time complexity of computing reduct B₁ is O (|U|² · |A|²). However, the time complexity of computing reduct B₂ is O (|U|² · |A - B₁|²). This is mainly because in the worst case, B₁ does not satisfy the constraint with respect to parameter σ₂, and then the searching space of attributes is actually A - B₁ instead of A. Similarly, the time complexity of computing reduct B₃ is O (|U|² · |A - B₂|²); …; the time complexity of computing reduct B _n is O (|U|² · |A - B_n-1|²). Consequently, the time complexity of Algorithm 3 is O ( | U | 2 · | A | 2 + | U | 2 · ∑ s = 1 n - 1 | A - B s | 2 ) . It is obvious that the reduct obtained by using Algorithm 1 is nonempty, it follows that O ( | U | 2 · | A | 2 + | U | 2 · ∑ s = 1 n - 1 | A - B s | 2 ) < O ( n · | U | 2 · | A | 2 ) . From this point of view, compared with the naive approach, it is expected that the proposed forward acceleration strategy may contribute to lower elapsed time of searching reducts over a set of parameters.

Additionally, to facilitate the understanding of our proposed acceleration strategy, an example is presented as follows.

Example 1. Let us consider the following example of data which includes 12 samples and 9 condition attributes. All samples are classified into three decision classes by d (see Table 1).

Suppose that the threshold ɛ is 0.05 and classical fuzzy rough set is used, we want to find γ-reducts over a set of kernel parameters such that T = {σ₁, σ₂, σ₃} = {0.01, 0.03, 0.05} by Algorithm 3. The main process of computing reducts over T is elaborated as follows.

For kernel parameter σ₁, the corresponding reduct is initially derived by using Algorithm 1 such that B₁ = {a₁, a₂}.

Following Example 1, it is not difficult to observe that different from the naive approach, the searching space of attributes has been reduced in the framework of our forward acceleration strategy. For instance, if σ₂ based reduct is required, then all candidate attributes in A should be searched by using Algorithm 2, while only the candidate attributes in A - B₁ are searched in terms of Algorithm 3.

In the following, the elapsed time of searching reducts over a set of kernel parameters through using the naive approach and our acceleration strategy will be compared. The detailed results are exhibited in the following.

With a careful investigation of Fig. 2, it is not difficult to observe the following.

Compared with the naive approach, our proposed acceleration approach can significantly reduce the elapsed time of finding reducts over multiple different parameters, especially based on k-trimmed, k-mean and k-median fuzzy rough set models. Moreover, in most cases, if the value of employed σ increases, then the corresponding time consumption of finding reduct may tend to be higher. This is mainly because with the increasing of value of σ, then the constraint with respect to σ may be stricter, it follows that more attributes may be required to satisfy such constraint, and then the corresponding time consumption of searching reduct may be increased.

OPEN IN VIEWER

Fig.2

Comparisons among time consumption (seconds) of finding reducts.

To further compare the time consumption of computing reducts between these two comparative approaches from the viewpoint of statistical theory, Wilcoxon rank sum test [46] will be employed. The purpose of our computation is trying to reject the null-hypothesis that such two approaches perform equally well in the elapsed time of searching reducts over multiple parameters. Assuming that the significance level is set to be 0.05, if the returned p-values are less than 0.05, then we reject the null-hypothesis. The detailed results of p-values are shown as follows.

Following Table 3, it is not difficult to observe that all the returned p-values are less than 0.05. Therefore, we can reject the null-hypothesis that such two approaches perform equally well in terms of time consumption of computing reducts over multiple different parameters. In other words, such result suggests that the elapsed time of computing reducts by using such two approaches is significantly different.

Additionally, following the results shown in Fig. 2 and Table 3, it is not difficult to reveal that compared with the naive approach, our proposed acceleration strategy can significantly reduce the elapsed time of finding reducts over multiple different parameters.

In the following, the classification performances of attributes in the obtained reducts will be compared. The KNN (parameter in KNN is 3) and SVM (LIBSVM [2]) classifiers are used for testing the classification performance. Note that the maximal and mean values of classification accuracies over a set of parameters will be mainly compared in this experiment. The detail results are presented as follows, where the higher values of classification accuracies are highlighted in bold, and the value in brackets is the kernel parameter corresponding to the maximal classification accuracy.

With a deep investigation of Tables 4–7, it is not difficult to observe the following.

No matter which fuzzy rough set model is employed, the maximal values of classification accuracies obtained by using our proposed acceleration approach are similar to those induced by using the naive approach. Take the data set “Breast Tissue” (ID: 3) as an example, if KNN classifier is employed, then the maximal value of classification accuracies derived by NA-FRS is 0.6801, and the maximal value of classification accuracies derived by FAS-FRS is 0.6706; if SVM classifier is used, then the maximal value of classification accuracies derived by NA-FRS is 0.5952, and the maximal value of classification accuracies derived by FAS-FRS is 0.5952.

Similarly, Wilcoxon rank sum test [46] will be employed to compare the naive approach and our acceleration strategy in terms of the classification performance of attributes in the obtained reducts. Assuming that the significance level is set to be 0.05. The detailed p-values are shown in the following, where the poorer values are highlighted in italics.

Through a careful investigation of Tables 8 and 9, it is not difficult to observe that the derived p-values over the most data sets are greater than 0.05. In view of such result, for KNN and SVM classifiers, the classification performances of attributes in the obtained reducts generated by such two approaches are not significantly different.

Moreover, by Tables 4–9, it is not difficult to conclude that compared with the naive approach, our acceleration strategy can generate the reducts of which the attributes may not contribute to poorer classification performance.

In the following, the lengths of reducts, which are generated by using the naive approach and our acceleration strategy based on different fuzzy rough set models, will be compared. The detailed results are shown as follows.

With a careful investigation of the results shown in Fig. 3, it is not difficult to observe the following.

The length of reducts generated with our acceleration strategy is similar to that generated with the naive approach over most data sets. Such observation result indicates that compared with the naive approach, the using of our acceleration strategy will not lead to significant difference in terms of the length of obtained reducts.

OPEN IN VIEWER

Fig.3

Comparisons of lengths among different reducts.

Similar to Sections 4.1 and 4.2, Wilcoxon rank sum test [46] is selected for comparing the lengths of reducts derived by the naive approach and our acceleration strategy. The detailed p-values are shown in the following, where the poorer values are highlighted in italic.

Assuming that the significance level is set to be 0.05, following the results shown in Table 10, it is not difficult to observe that the most p-values are greater than 0.05. From this point of view, such two approaches do not have significant difference with respect to the length of the obtained reducts.∥Moreover, based on the results shown in Fig. 3 and Table 10, it is not difficult to conclude that lengths of reducts derived by the naive approach and our acceleration strategy are similar, and the differences between such two approaches are not significant. That is, compared with the naive approach, the using of our acceleration strategy will not contribute to significant variation of the length of the obtained reduct.