Minimum attribute reduction algorithm based on quick extraction and multi-strategy social spider optimization

Abstract

Intelligent optimization algorithm combined with rough set theory to solve minimum attribute reduction (MAR) is time consuming due to repeated evaluations of the same position. The algorithm also finds in poor solution quality because individuals are not fully explored in space. This study proposed an algorithm based on quick extraction and multi-strategy social spider optimization (QSSOAR). First, a similarity constraint strategy was called to constrain the initial state of the population. In the iterative process, an adaptive opposition-based learning (AOBL) was used to enlarge the search space. To obtain a reduction with fewer attributes, the dynamic redundancy detection (DRD) strategy was applied to remove redundant attributes in the reduction result. Furthermore, the quick extraction strategy was introduced to avoid multiple repeated computations in this paper. By combining an array with key-value pairs, the corresponding value can be obtained by simple comparison. The proposed algorithm and four representative algorithms were compared on nine UCI datasets. The results show that the proposed algorithm performs well in reduction ability, running time, and convergence speed. Meanwhile, the results confirm the superiority of the algorithm in solving MAR.

Keywords

Intelligent optimization rough set theory attribute reduction social spider optimization opposition-based learning

1 Introduction

Data mining, also known as knowledge discovery in database, refers to the discovery of hidden rules and knowledge from massive data. With the explosive growth of data in all walks of life, data mining is facing great challenges. Rough set theory (RST) is an important means of data mining [28]. Santra et al. applied RST to medical diagnosis [14]. Watada et al. used fuzzy random variables and statistical t-test on the data mining of electric power company [20]. Jing et al. designed an incremental attribute reduction algorithm to solve the problem of adding attributes and objects at the same time [7]. Ding et al. proposed a multi-granularity strategy to solve the efficiency problem of uncertain fuzzy attribute reduction [4]. RST has achieved very good results in the field of data mining. Attribute reduction (AR), as one of the core research contents of RST and a necessary step of data mining, has gradually attracted the attention of researchers.

Attribute reduction is a key of RST and has important meaning in the application of RST. It removes redundant and irrelevant attributes to reduce data dimension without affecting the classification capability of the information system. The Minimum attribute reduction (MAR) is a hotspot in AR research. The basic idea of MAR algorithm is to generate all possible reductions and select the one with the smallest cardinality. There are some problems with MAR algorithm. On the one hand, as the increase of data volume, the running time grows exponentially [17]. On the other hand, positive field [13], information entropy [11], mutual information [10] were used, as heuristic information, to search and obtain the minimum attribute reduction, but the search may be toward a non-minimum path.

Swarm intelligent optimization algorithm originated from simulating the behavior of biological groups in the natural world. It has the characteristics of simple operation, strong robustness and easy parallelism. Kulik et al. applied genetic algorithm to the optimization problem in the robot field [8], and achieved good results. Sun et al. proposed an improved particle swarm optimization algorithm by initializing population chaos, dynamically improving inertia weight, and adjusting acceleration factor, and applied it to the overall kitchen design for the first time [15]. Tang et al. constructed an optimal accounting model through the combination of particle swarm optimization algorithm and ant colony algorithm [16]. Yan et al. proposed a hybrid whale optimization algorithm based on Levy flight strategy and lateral suppression to solve underwater image matching in a UUV vision system [25].

The intelligent optimization algorithm, due to the above-mentioned advantages, have also been widely used to solve the problem of AR. Jensen and Shen applied genetic algorithm to solve attribute reduction [6]. Xu et al. developed an attribute reduction method combining particle swarm optimization with RST [22]. Wei et al. introduced improved information gain rate and redundancy detection into the standard ant colony algorithm [21] and achieved good results. Min et al. proposed a partial complete search technique of ant colony algorithm to obtain rough intensive reduction, which improved the computational efficiency [12]. Yamany et al. used algorithms that imitated the social leadership and hunting behavior of gray wolves in nature to implement AR [23]. In addition, there are other new intelligent optimization algorithms that have been proposed to solve attribute reduction algorithms such as the artificial fish swarm algorithm, artificial bee colony and firefly algorithm [2 , 26]. Nevertheless, the probability of obtaining the minimum attribute reduction in the actual calculation is still very small, and the quality of the solution needs to be improved. Therefore, it is necessary to explore new and more efficient intelligent optimization algorithm to solve attribute reduction problems.

Social spider optimization (SSO) algorithm was proposed by Cuevas et al. in 2013 [3], which designed to simulate a series of behaviors such as cooperative predation between individual cluster spiders, exchange of information on public webs, and reproduction between male and female individuals. Compared with other intelligent algorithms, SSO has its unique advantages. For example, compared with genetic algorithm, SSO only needs simple mathematical operators to get the optimal solution. In addition, SSO has a variety of optimization methods, while particle swarm optimization mainly focuses on the relationship between speed and position. Many improved algorithms based on SSO have been proposed and widely used to solve various complex optimization problems. Zhou et al. [29], aiming at clustering, proposed a simplex method-based SSO that enhanced the population diversity and local search ability of the algorithm. Zhao et al. developed an elite opposition-based SSO called EOSSO for global function optimization [27], in which elitism learning was used to enhance the convergence rate and calculation accuracy. In order to solve multi-objective problems, a standardized fitness function was proposed by Wang et al. [19], using the non-dominant ranking and crowding distance to evaluate the merits and demerits of individuals and using gravity factors to balance the influence of fitness and distance on individual performance. Abd El Aziz and Hassanien constructed a minimum attribute reduction algorithm based on improved social spider optimization [1]. Ibrahim et al. [5] introduced opposition-based learning (OBL) to the traditional social spider optimization, which expanded the diversity of the spiders and enhanced the exploration ability. Although many improved SSO have good performance, most of them only achieve local optimum, and their convergence speed needs to be improved. Besides, continuous evaluation of individual computing overhead leads to excessive running time. Therefore, it is necessary to put forward new improvements.

In this paper, we applied social spider optimization to solve minimum attribute reduction, and presented a new algorithm for attribute reduction based on quick extraction and multi-strategy SSO (QSSOAR). By using fast extraction to reduce the running time of the algorithm, multi-strategy was introduced to improve the quality of solving the minimum attribute reduction. The main contributions of the paper are the following:

This paper constructed a quick calculation method of fitness function based on the combination of array and key-value pairs. The proposed strategy avoids the double calculation in the process of individual evaluation.

This algorithm introduced the similarity constraint strategy. The individuals with poor performance were reinitialized by comparing the similarity values between the optimal individuals and the remaining individuals. This strategy made the initial population include more individuals with good performance to facilitate the exploration of the population.

Adaptive opposition-based learning (AOBL) strategy was incorporated in the iterative process. The algorithm evaluated both individuals below the average fitness value and opposite individuals, and selected individuals with higher fitness values to replace the original individuals. Reverse exploration not only expands the search space, but also improves the possibility of finding better solutions.

The dynamic redundancy detection (DRD) strategy based on attribute importance was used to remove redundant attributes from the reduction results. This strategy made the reduction as concise as possible.

The proposed algorithm and four representative algorithms were compared on nine UCI datasets. The present findings demonstrate the superiority of the proposed algorithm for solving MAR.

The rest of the paper is organized as follows. Section 2 mainly introduces the RST and SSO. Section 3 describes the proposed algorithm. The experimental results are present in Section 4 and conclusions and future works are finally written in Section 5.

2 Preliminaries

2.1 Rough set theory

This section introduces the relevant knowledge of rough set theory in knowledge, which will be used to evaluate candidate attribute subsets in the proposed algorithm. These concepts include information systems, decision systems, indiscernible relations, upper and lower approximations, positive and negative domains and attribute dependencies and importance.

Let S = (U, A, V, f) be a decision system. U is a non-empty finite set of objects. A = C ∪ D, where C and D are condition attribute and decision attribute, respectively. A system is divided into an information system (information table) and a decision system (decision table) by decision information. V_α represents the value region of attribute α. f : U × A → V is metric information function. Table 1 represents a decision table, where U ={ e₁, e₂, e₃, e₄, e₅ } is the domain and represents each patient. C ={ Muscle, Headache, Snivel, Flu } is a conditional attribute set, representing symptom information. D is the decision attribute, indicating whether the patient has influenza. All attribute values are either Yes or No.

Table 1
An example of decision system

Patient Muscle Headache Snivel Flu

e ₁ Yes Yes Yes Yes

e ₂ No Yes No Yes

e ₃ Yes No No No

e ₄ No No Yes Yes

e ₅ No No No No

Patient	Muscle	Headache	Snivel	Flu
e ₁	Yes	Yes	Yes	Yes
e ₂	No	Yes	No	Yes
e ₃	Yes	No	No	No
e ₄	No	No	Yes	Yes
e ₅	No	No	No	No

Definition 1. Given a decision table S = (U, C ∪ D, V, f), with any B ⊆ A, there is an associated equivalence relation IND (B):

$\begin{matrix} IND (B) & = {(x, y) \in U \times U | \forall α \in B, f (x, α) \\ = f (y, α)} \end{matrix}$ (1)

The partition of U, generated by IND (B) is called U/IND (B) and can be calculated as follows: $U / IND (B) = {[x]_{B} | x \in U}$ (2) where [x] _B denotes the equivalence class determined by x with respect to C, i.e., [x] _B ={ y ∈ U| (x, y) ∈ IND (B) }.

Definition 2 [13]. Given a decision table S = (U, C ∪ D, V, f), for indiscernibility relation IND (B) and a subset X ⊆ U, the B-lower and B-upper approximations of X can be calculated as follows: $\underline{B} (X) = {x | (\forall x \in U) \land ([x]_{B} \subseteq X)}$ (3) $\bar{B} (X) = {x | (\forall x \in U) \land ([x]_{B} \cap X \neq \emptyset)}$ (4)

Definition 3 [13]. For two subsets P, Q ⊆ A which give raise to two equivalence relationship IND (P) and IND (Q), the positive and negative regions can be defined as: ${POS}_{P} (Q) = \underset{X \in U / IND (Q)}{\cup} \underline{P} (X)$ (5) ${NEG}_{P} (Q) = U - \underset{X \in U / IND (Q)}{\cup} \bar{P} (X)$ (6)

Definition 4 [13]. The reduction set can be obtained by dependency. The dependence between P and Q can be expressed as: $γ_{P} (Q) = card ({POS}_{P} (Q)) / card (U)$ (7) where card (*) represents the cardinality of the set. If γ_P (Q) =0, Q does not depend on P, if 0 < γ_P (Q) <1, Q depends partially on P, while if γ_P (Q) =1, Q depends totally on P.

Therefore, given a decision system S = (U, C ∪ D, V, f), the importance of attribute α is defined as: $\begin{matrix} sig (α, R; D) = γ_{R} (D) - γ_{R - {α}} (D) \\ = \frac{card ({POS}_{R} (D))}{card (U)} - \frac{card ({POS}_{R - {α}} (D))}{card (U)} \end{matrix}$ (8)

D efinition 5 [13]. Given a decision table S = (U, C ∪ D, V, f) and any R ⊆ C, then R is a reduction requiring the following conditions: $γ_{R} (D) = γ_{C} (D) and \forall α \in R, γ_{R - {α}} (D) < γ_{R} (D)$ (9)

The reduction R may have the reduction results of different attribute combinations, but all of the reduction results must contain the result of the minimum cardinality. The goal of this paper is to find this reduction.

2.2 Social spider optimization algorithm

SSO simulates the cooperative behavior of social spiders [3]. In the algorithm, the population is divided into a female spider population and a male spider population which are used as two different search agents. Female accounts for 65% to 90% of the total population. Individuals are controlled by different operators to collaborate according to their genders.

The transmission of information among the spiders is achieved through vibrations in the public network and the information transmitted is determined by the weight and distance of individuals. The weight is determined by the fitness value F. The distance between spiders is measured by the Euclidean distance. The vibration perceived by individual i and emitted by individual j can be defined as [3]: ${Vib}_{i, j} = w_{j} \cdot e^{- d_{i, j}^{2}}$ (10) where d_i,j is the distance between spiders i and j, which is calculated by d_i,j =∥ x_i - x_j ∥. w_j is the weight of spider j and it is defined as: $w_{j} = \frac{F (x_{j}) - {worst}_{x}}{{best}_{x} - {worst}_{x}}$ (11) where F (x_j) is the fitness value and is determined by evaluating position x_j. best_x is the maximum fitness, while worst_x is the minimum fitness in the entire population.

2.2.1 Female cooperative operators

To simulate the cooperative behavior of the female spiders, operators need to consider the position of the female in the iterative process [3]. The locations are made up of three different elements. The first part is the Vibc_i generated by the nearest spider s_c whose weight is greater than spider i. The second is the Vibb_i produced by the best individual s_b in the entire population. The third is the random motion. Female spiders update its position as follows:

$x_{f_{i}}^{g + 1} = {\begin{matrix} \begin{matrix} x_{f_{i}}^{g} + β \cdot {Vibc}_{i} (s_{c} - x_{f_{i}}^{g}) + η \cdot {Vibb}_{i} \cdot (s_{b} - x_{f_{i}}^{g}) + \\ δ_{1} \cdot ({rand}_{1} - 0.5) {rand}_{2} ⩾ PF \end{matrix} \\ \begin{matrix} x_{f_{i}}^{g} - β \cdot {Vibc}_{i} (s_{c} - x_{f_{i}}^{g}) - η \cdot {Vibb}_{i} \cdot (s_{b} - x_{f_{i}}^{g}) + \\ δ_{1} \cdot ({rand}_{1} - 0.5) otherwise \end{matrix} \end{matrix}$ (12) where β, η, δ₁, rand₁ and rand₂ are random values between [0,1]. g is the number of iterations. PF is a threshold that spiders move far away from or close to the source of vibration.

2.2.2 Male cooperative operators

The male spiders in the population have a completely different strategy for updating their positions. Male spiders are divided into dominant and non-dominant males. Dominant males are attracted to females, while non-dominant males move towards the center of the males. Male spiders update its position as follows [3]: $x_{m_{i}}^{g + 1} = {\begin{matrix} \begin{matrix} x_{m_{i}}^{g} + σ_{1} \cdot {Vibf}_{i} \cdot (s_{f} - x_{m_{i}}^{g}) + \\ σ_{2} \cdot ({rand}_{3} - 0.5) w_{m_{i}} > {ind}_{med} \end{matrix} \\ \begin{matrix} x_{m_{i}}^{g} + σ_{1} \cdot (\sum_{j = 1}^{N_{m}} x_{m_{i}}^{g} \cdot w_{N_{f + j}} / \\ \sum_{j = 1}^{N_{m}} w_{N_{f + j}} - x_{m_{i}}^{g}) otherwise \end{matrix} \end{matrix}$ (13) where σ₁, σ₂ and rand₃ are the random numbers between [0,1]. ind_med is the weight which median of all-male spiders. s_f represents the female with the shortest distance from the ith male, and Vibf_i represents the vibration produced by s_f. The above Equation (13) has two advantages. Firstly, it considers the mating. Male spiders are attracted to females to prepare for mating, which promotes the diversity of spiders. Secondly, the introduction of weighted average can avoid the influence of very good and very bad spiders on the search process.

2.2.3 Mating and replacement

If the females and dominant males are within the specified range, they may be mating. The radius r_m is defined as: $r_{m} = \frac{Σ_{l = 1}^{n} (x_{l}^{high} - x_{l}^{low})}{2 \cdot n}$ (14)

In the situation of many males with only one female, the roulette wheel mechanism is used to choose parents and produce new offspring. Then, the new individual replaces the parent with the worst fitness function [3].

3 Description of the proposed algorithm

This section describes the proposed QSSOAR algorithm, which aims to solve the problem of minimum attribute reduction more effectively. Figure 1 is the flow chart of the QSSOAR algorithm.

Fig. 1

The flowchart of the proposed QSSOAR algorithm.

3.1 Encoding method

The proposed QSSOAR algorithm first generates a population X with n individuals. Each spider X_i in X is transformed into a binary vector of length n by Eqs. (15) and (16). $FP (x_{i}^{j} (g)) = \frac{1}{1 + e^{- x_{i}^{j} (g)}}$ (15) $x_{i}^{j} (g + 1) = {\begin{matrix} 1 FP (x_{i}^{j} (g)) > ζ \\ 0 otherwise \end{matrix}$ (16) where ζ is a random number in [0,1] and x_i represents the selection of the attribute, with the value of 0 or 1.

3.2 Fitness function

The performance of the individual is generally evaluated by putting his position into a certain function. Therefore, as the only deterministic criterion, the choice of the evaluation function is crucial. The evaluation function needs to be able to reflect both the classification ability and the number of attributes of the current reduction result. As in the fitness function [3], individual performance is assessed by dependency and the number of reductions. This paper adopted the same fitness function to evaluate the spider location, as shown in Equation (17). $F = λ * γ_{R} (D) + (1 - λ) * (\frac{card (C) - card (R)}{card (C)})$ (17)

where λ is a parameter that balances between a number of selected attributes and quality of classification. γ_R (D) is the dependence of conditional attribute R on decision attribute D, which can clearly reflect the dependence between conditional attribute sets and decision attribute. The smaller the number of attributes, the smaller the value of card (R).

3.3 Similarity constraint strategy

At the beginning of the iteration, the random distribution of individuals in the space may lead to the existence of individuals with poor performance. Improving the initial position of spiders in the population and restricting them to a better region can not only increase the convergence speed, but also help individuals find a better solution. The similarity constraint strategy was used in this study. Measure the similarity between each spider and the optimal spider, and set a threshold. The spiders below the threshold are reinitialized. Before measuring the similarity, the difference between the two spiders was measured by hamming distance. The calculation formula is as below: $D (x_{i}, x_{j}) = \sum_{l = 1}^{n} x_{i}^{l} \oplus x_{j}^{l}$ (18) where ⊕ addition modulo 2. After determining the difference value between spiders by Equation (18), the similarity of the two spiders is further calculated by Equation (19): $sim (x_{i}, x_{j}) = 1 - (\frac{\sum_{l = 1}^{n} x_{i}^{l} \oplus x_{j}^{l}}{n})$ (19)

Based on the above, the average similarity between each spider X_i and the current optimal spider G_loc can be calculated as below: $\bar{sim} = \frac{\sum_{i = 1}^{N - 1} sim (G_{loc}, x_{i})}{N - 1}$ (20)

We used the dataset in Table 1 as an example to illustrate the similarity constraint strategy. For ease of description, the conditional attributes Muscle, Headache and Snivel were denoted by a, b and c, respectively. The decision attribute Flu was denoted by d, Yes was represented by 1 and No by 0.

Assume the population has five individuals x₁ = {a}, x₂ = {b}, x₃ = {c}, x₄ = {a, b}, x₅ = {b, c}.

The fitness function of spider calculated according to Equation (17) is as below: $\begin{matrix} F (x_{1}) = λ * γ_{x 1} ({d}) + (1 - λ) * \\ ((card (C) - card (x_{1}))) \\ / card (C) = 0.9 * 0 + 0.1 * (2 / 3) \approx 0.067 \end{matrix}$

Similarly, F (x₂) ≈0.427, F (x₃) ≈0.427, F (x₄) ≈0.573, F (x₅) ≈0.933. The fitness function of x₅ is the largest and defined as G_loc. The similarity between individual x₁ and G_loc can be calculated as below:

$sim (G_{loc}, x_{1}) = 1 - \sum_{l = 1}^{n} G_{loc}^{l} \oplus x_{1}^{l} / n = 1 - 3 / 3 = 0$

In the same way, sim (G_loc, x₂) =1 - 1/3 = 2/3 ≈ 0.67, sim (G_loc, x₃) ≈0.67, sim (G_loc, x₄) ≈0.33. The average similarity is calculated as $\bar{sim} = \sum_{i = 1}^{4} sim (G_{loc}, x_{i}) = (0 + 0.67 + 0.67 + 0.33) / 4 = 0.4175$ , The similarity threshold $0.5 > \bar{sim}$ . The similarity values of x₁ and x₄ were less than the average similarity, and the initial positions x₁ = {c}, x₂ ={ a, c }. The similarity values sim (G_loc, x₁) ≈0.67, sim (G_loc, x₁) ≈0.33, $\bar{sim} = (0.33 + 0.67 + 0.67 + 0.67) / 4 = 0.585 > 0.5$ . At the same time, the fitness function values F (x₁) ≈0.427 > 0 and F (x₄) ≈0.573 of x₁ and x₄ were calculated, which showed that the fitness function value of F (x₁) was improved. It is proved that the proposed similarity constraint is effective.

3.4 Adaptive opposition-based learning

OBL was incorporated into the algorithm to improve its performance. After updating spider’s position based on traditional SSO, OBL was used to generate the opposite position of each position. After calculation of the fitness function value of each opposite individual, the original population and the opposite population were merged. Then, the best n solutions were selected from the union and constructed a new population. The best solution G_loc was selected from all the solutions. Based on opposition-based learning, the related concepts are defined as follows:

Definition 6. Let p ∈ [a, b] be a real number, and its opposite number p^* is defined by: $p^{*} = a + b - p$ (21) where a is the lower bound of the search space and b represents the upper bound.

Definition 7. Let p = (p₁, p₂, . . . , p_n) ∈ R be a point in n-dimensional space, where (p₁, p₂, . . . , p_n) ∈ R, p_i ∈ [a_i, b_i], and ∀i ∈ {1, 2, . . . , n}. p^* is the opposite point of p and is defined as: $p_{i}^{*} = a_{i} + b_{i} - p_{i}$ (22)

Definition 8. Let p = (p₁, p₂, . . . , p_n) and $p^{*} = (p_{1}^{*}, p_{2}^{*}, . . ., p_{n}^{*})$ be the two points in n-dimensional space. According to the definition of the opposite point, $p^{*} = (p_{1}^{*}, p_{2}^{*}, . . ., p_{n}^{*})$ is the opposite of p = (p₁, p₂, . . . , p_n). F (*) was used to measure the candidate’s fitness. If F (p *) ⩾ F (p), then point p* will replaces point p. Otherwise, point p will continue to be used.

The adaptive opposition-based learning (AOBL) strategy was adopted in this study. Different from the traditional OBL, the AOBL calculates the reverse solution of the poor performing individuals in the population instead of the whole population. Moreover, traditional opposition-based learning is called in every generation, while AOBL will evaluate the current iteration according to the number of iterations and decide whether or not to implement oppositional learning. At the beginning of iteration, it is necessary to search as many individuals in the population as possible as to help to find a better solution. However, in the late iteration, the individual reverse solution in the population is often poor. Avoiding assessing these individuals will greatly reduce redundancy. The AOBL can meet the above requirements due to its two advantages: one is that it can reasonably expand the search space. The other is to effectively reduce the computational redundancy. The following is a detailed introduction of AOBL, and the algorithm pseudocode and an example are given in the end.

First, S_a is used to determine whether to perform opposition-based learning, and it is calculated as follows:

$S_{a} = {\begin{matrix} 1 \frac{{Num}_{\max} - iter}{{Num}_{\max}} > {rand}_{4} \\ 0 otherwise \end{matrix}$ (23)

where rand₄ is a random number, iter is the current number of iterations, and Num_max is the total number of iterations. If S_a = 1, then calculate the average fitness function value $\bar{F}$ . Female and male spiders with the fitness value less than the average value are selected to create population NP and the number of individuals in the population is recorded as N′. Create the opposite population OP and calculate the fitness value. Merge NP and OP. The 2N′ spiders are sorted in descending order according to their fitness value and the top N′ spiders are selected as the new population NP′ to replace the population NP, and the new population NP′ was then merged with the individuals whose fitness was greater than the average in the original population as the new current population. Algorithm 1 shows the steps of the AOBL algorithm.

Algorithm 1 AOBL algorithm
Input: A decision table S = (U, C ∪ D, V, f), the size of spiders
N, spider position x.
Output: Spider position x.
1: IfS_a = 1 then
2: $\bar{F} = 0$ , NP =∅, N′ = 0;
3: fori = 0: Ndo
4: Calculate the fitness F (x_i) of x_i;
5: $\bar{F} = \bar{F} + F (x_{i})$ ;
6: end for
7: fori = 1: Ndo
8: if $F (x_{i}) < \bar{F}$ then
9: NP = NP ∪ {x_i};
10: N′ = N′ + 1;
11: end if
12: end for
13: Create the opposite spider population OP;
14: Combined NP and OP, select the top N′ spiders;
15: Replace NP with NP′;
16: end if

In order to demonstrate the effectiveness of the algorithm, an example of adaptive opposition-based learning is given as follows.

Assume the population has three individuals x₁ = {a}, x₂ = {b}, x₃ = {c}, the maximum number of iterations NUM_max = 200, the current iteration number iter = 1, rand₄ = 0.5, S_a is calculated according to Equation (23): $\begin{matrix} S_{a} = ({Num}_{\max} - iter) / {Num}_{\max} = (200 - 1) / 200 \\ = 0.995 > 0.5 \end{matrix}$

Calculate the fitness function value F (x₁) ≈0.067, F (x₂) ≈0.427, and F (x₃) ≈0.427. The average fitness function value is: $\begin{matrix} \bar{F} = (F (x_{1}) + F (x_{2}) + F (x_{3})) / 3 = (0.067 + 0.427 \\ + 0.427) / 3 = 0.921 / 3 = 0.307 \end{matrix}$

It can be known that $\bar{F} > F (x_{1})$ , the opposite individual $x_{1}^{*} = {b, c}$ of x₁ is created, and its fitness function $F (x_{1}^{*}) \approx 0.933 > F (x_{1})$ , then x₁ is replaced, and the AOBL is completed.

Then, assume the current iteration number iter = 200, the random number is still 0.5, S_a = 0 <0.5, the opposition-based learning will not be performed.

It can be seen from the above example that the probability of S_a will be less than the generated random number when the iteration enters the middle and late stage, which can expand the search space and reduce computational redundancy.

3.5 Quick extraction strategy

In the iterative process, the running time is mainly affected by the calculation of fitness function. Repeated calculation of fitness function greatly extends the running time. To solve the problems, this paper proposed a quick extraction strategy. The main idea is to create an array to record the number of selected attributes and create a linked list below the array. Different key-value pairs are stored in the linked list. The key corresponds to each reduction result, and the value is the fitness function value corresponding to the reduction. Taking the first generation as an example, the quick extraction strategy was explained and descripted, and its calculation, storage, search and extraction process of quick extraction strategy were shown in Fig. 2.

Fig. 2

Quick extraction strategy.

In Fig. 2, after initializing each spider, the reduction results of spider are x₁ = {α₁} x₂ = {α₃}, x₃ = {α₂, α₃}. The reduction number is 1, 1, 2. If there is no value in the corresponding array, then calculate the fitness value F (x_i), i = 1, 2, 3 for each spider, and store the key value in the corresponding position. When the fitness function value needs to be calculated again, the number of reductions will be calculated. If they are the same, the key values in the linked list under the array will be matched, and the corresponding values of the keys in the array will be extracted. If the key values same as x₂ and x₃ are found, the corresponding fitness values will be taken out.

3.6 Dynamic redundancy detection

The reduction results of the finally obtained global optimal solution may still contain redundant attributes during iteration. Therefore, the algorithm tries to eliminate the redundant attributes through the importance of attributes in the rough set.

Besides, an example of DRD is given to describe the implementation process of DRD. We describe the process in Algorithm 2.

Algorithm 2 DRD algorithm
Input: A decision table S = (U, C ∪ D, V, f), global optimal G_loc
and G_fit;
Output: Global optimal $G_{loc}^{'}$ and $G_{fit}^{'}$ .
1: Copy G_loc value to $G_{loc}^{'}$ and copy G_fit value to $G_{fit}^{'}$
2: For every $α_{i} \in G_{loc}^{'}$ do
3: If sig (α_i, G_loc ; D) =0 then
4: $G_{loc}^{'} = G_{loc}^{'} - {α_{i}}$ ;
5: else select next attribute;
6: end if
7: Calculate the fitness value $G_{fit}^{'}$ by $G_{loc}^{'}$ ;

Assume the optimal solution is $G_{loc}^{'} = {b, c}$ . Delete attribute b and calculate the importance of the attribute as follows:

$\begin{matrix} sig (b, G_{loc}^{'}; d) = γ_{G_{loc}^{'}} ({d}) - γ_{G_{loc}^{'} - {b}} ({d}) \\ = \frac{card ({POS}_{G_{loc}^{'}} ({d}))}{card (U)} - \frac{card ({POS}_{G_{loc}^{'} - {b}} ({d}))}{card (U)} \\ = 1 - 0.4 = 0.6 \end{matrix}$

After deleting attribute b, the value of attribute importance is not 0, so that it cannot be deleted. Then put attribute b back in the reduction set and delete attribute c: $\begin{matrix} sig (c, G_{loc}^{'}; d) = γ_{G_{loc}^{'}} ({d}) - γ_{G_{loc}^{'} - {c}} ({d}) \\ = \frac{card ({POS}_{G_{loc}^{'}} ({d}))}{card (U)} - \frac{card ({POS}_{G_{loc}^{'} - {c}} ({d}))}{card (U)} \\ = 1 - 0.4 = 0.6 \end{matrix}$

The attribute importance is not 0 either, after deleting attribute c, so it cannot be deleted. Then attribute c is put back into the reduction set too, and redundancy detection ends once.

Assuming that the optimal reduction result of the next generation is G_loc ={ b, c }, the redundancy detection result is shown in the above example. The redundancy detection is skipped, which effectively reduces the computation.

4 Experimental results and discussion

Four algorithms were compared with the proposed QSSOAR algorithm in this study, which were genetic algorithm (GARS) [6], ant colony algorithm (IGRARACO) [20], flower pollination optimisation (FLRSAR) [24] and whale optimization algorithm (FSRSWOA) [18].

4.1 Experimental environment and parameter setting

The performance of the proposed QSSOAR algorithm was tested on a personal Windows 7 computer with 3.2 GHZ processor and 8 G memory. Nine UCI machine learning datasets that contain different types of attributes was used (Table 2), such as the Zoo dataset, which is composed of Boolean, discrete, and nominal attributes. Wine data contains continuous values that need to be discussed first. In addition, mushroom dataset containing missing values, and so on. In our study, the experimental parameters are set as follows: population size N = 25, the proportion of female spiders was 0.65 < p_fm < 0.9, the weight factor λ = 0.9. PF = 0.7. Each dataset was tested 20 times, and the halting condition is reaching the maximum cycle.

Table 2
Description of datasets from UCI

ID Dataset Areas Information

No. of instances No. of attributes No. of class Missing value

1 Zoo Animal 101 16 7 No

2 Monk1 Life 124 7 2 No

3 Wine Physical 178 13 3 No

4 Heart-Statlog Medical 270 13 2 Yes

5 Vote Social 300 16 2 Yes

6 Breastcancer Medical 699 9 2 Yes

7 Pima-Indians Medical 786 8 2 No

8 Tic-Tac-Toe Game 958 9 2 No

9 Mushroom Botany 8124 22 2 Yes

ID	Dataset	Areas	Information
1	Zoo	Animal	101	16	7	No
2	Monk1	Life	124	7	2	No
3	Wine	Physical	178	13	3	No
4	Heart-Statlog	Medical	270	13	2	Yes
5	Vote	Social	300	16	2	Yes
6	Breastcancer	Medical	699	9	2	Yes
7	Pima-Indians	Medical	786	8	2	No
8	Tic-Tac-Toe	Game	958	9	2	No
9	Mushroom	Botany	8124	22	2	Yes

4.2 Analysis of reduction efficiency

To verify the proposed QSSOAR algorithm, the reduction results of each dataset in Table 2 analyzed by QSSOAR were compared with that by other algorithms in literature and the comparison was shown in Table 3. It lists the minimum reduction and average length of each of the nine dataset by different algorithms. Some algorithms may produce multiple effective reduction results for the evaluated data sets, while others have only one optimal reduction.

Table 3
Reduction sizes found by different attribute reduction methods

ID Dataset Before GARS IGRARACO FSRSWOA FLRSAR QSSOAR

Min Ave Min Ave Min Ave Min Ave Min Ave

1 Zoo 16 5^* 5.8 5^* 5^* 6 7.17 5^* 5.9 5^* 5.21

2 Monk1 7 3^* 3^* 3^* 3^* 3^* 3^* 3^* 3^* 3^* 3^*

3 Wine 13 4^* 4^* 4^* 4^* 4^* 4^* 4^* 4^* 4^* 4^*

4 Heart-Statlog 13 3^* 3^* 3^* 3^* 3^* 3^* 3^* 3^* 3^* 3^*

5 Vote 16 9 10 9 9 8^* 8.5 8^* 8.7 8^* 8.35

6 Breastcancer 9 4^* 4^* 4^* 4^* 4^* 4^* 4^* 4^* 4^* 4^*

7 Pima-Indians 8 3^* 3^* 3^* 3^* 3^* 3.4 3^* 3^* 3^* 3^*

8 Tic-Tac-Toe 9 7^* 7^* 8 8 7^* 7.6 7^* 7^* 7^* 7^*

9 Mushroom 22 6 7.35 4^* 4.4 5 5.8 7 7.8 4^* 4.55

ID	Dataset	Before	GARS	IGRARACO	FSRSWOA	FLRSAR	QSSOAR
1	Zoo	16	5^*	5.8	5^*	5^*	6	7.17	5^*	5.9	5^*	5.21
2	Monk1	7	3^*	3^*	3^*	3^*	3^*	3^*	3^*	3^*	3^*	3^*
3	Wine	13	4^*	4^*	4^*	4^*	4^*	4^*	4^*	4^*	4^*	4^*
4	Heart-Statlog	13	3^*	3^*	3^*	3^*	3^*	3^*	3^*	3^*	3^*	3^*
5	Vote	16	9	10	9	9	8^*	8.5	8^*	8.7	8^*	8.35
6	Breastcancer	9	4^*	4^*	4^*	4^*	4^*	4^*	4^*	4^*	4^*	4^*
7	Pima-Indians	8	3^*	3^*	3^*	3^*	3^*	3.4	3^*	3^*	3^*	3^*
8	Tic-Tac-Toe	9	7^*	7^*	8	8	7^*	7.6	7^*	7^*	7^*	7^*
9	Mushroom	22	6	7.35	4^*	4.4	5	5.8	7	7.8	4^*	4.55

GARS: genetic algorithm; IGRARACO: ant colony algorithm; FSRSWOA: whale optimization algorithm; FLRSAR: flower pollination optimization; QSSOAR: the proposed improved social spider optimization algorithm in this study, Min: minimum reduction; Ave: the average length.

It can be seen from Table 3 that, all the algorithms obtained the minimum reduction of dataset Monk1, Wine, Heart-Statlog and Breastcancer. QSSOAR and GARS got the same reduction of dataset Pima-Indians and Tic-Tac-Toe. But QSSOAR gained better reduction on Zoo, Vote and Mushroom datasets than GARS, proving that the reduced ability of QSSOAR is better than that of GARS. FSRSWOA didn’t obtain the minimum reduction of dataset Zoo, Vote, Pima-Indians, Tic-Tac-Toe and Mushroom, and its output still contained redundant attributes. Of the nine datasets, FLRSAR only got the suboptimal solution of dataset Zoo, Vote and Mushrooms. It can be seen that, GARS, FSRSWOA and FLRSAR algorithms are difficult to gain the MAR of dataset Zoo, Vote and Mushroom. Because of the increasing number of attributes and the combination of attributes, the algorithm is easier to achieve local optimization and cannot get the best solutions. While the proposed QSSOAR can fully explore to obtain the minimum attribute reduction when the dataset contains multiple attributes.

In comparison, IGRARACO gained better reduction results in dataset Zoo and Mushroom, which indicates that it has improved information gain rate as heuristic information has a stronger ability. However, for the Vote and Tic-Tac-Toe dataset, IGRARACO only obtained the suboptimal solution, and its output still contains redundant attributes. By contrast, QSSOAR obtained better solution for these two datasets. IGRARACO adopts two redundancy detection based on mutual information, which can quickly obtain a minimum reduction result but will lose the diversity. QSSOAR balances the diversity and convergence through AOBL and DRD strategy, and can achieve smaller reduction.

4.3 Analysis of running time

The proposed QSSOAR algorithm was further evaluated in terms of the running time. To show the effect of quick extraction strategy, the algorithm without adding quick extraction strategy was called the attribute reduction algorithm based on improved social spider optimization (ISSOAR). Its running time was compared with that of the QSSOAR algorithm which merged the quick extraction strategy. For each dataset, the algorithm was run 20 times and the average running time was calculated.

4.3.1 Comparison of running time between QSSOAR and ISSOAR

The ISSOAR algorithm contains a variety of improvement strategies, which results in that the fitness function value is calculated many times. Thus, the running time greatly extends. After adding the quick extraction strategy, the running time of QSSOAR algorithm is significantly shortened. The running time of QSSOAR and ISSOAR of different datasets were calculated and compared (Fig. 3). The results showed that, when the number of iterations is 25, the running time of QSSOAR was shorter than that of ISSOAR. At the end of iteration, the lines gradually flatten, which indicates that the running time growth is gradually slowing down. In addition, from the Monk, Breastcancer, Pima-Indians and Tic-Tac-Toe datasets, it can be seen that the effect of quick extraction strategy on datasets with less attributes is more obvious. For the dataset with more attributes, the running time of the algorithm becomes less as time goes on.

Fig. 3

Running time of algorithms QSSOAR and ISSOAR of different datasets.

4.3.2 Comparison of running time between QSSOAR and other algorithms

Figure 4 shows the running time of QSSOAR and IGRARACO, and Fig. 5 shows the running time of QSSOAR, FSRSWOA, FLRSAR and GARS.

Fig. 4

Running time of algorithms QSSOAR and IGRARACO of different datasets.

Fig. 5

Running time of algorithm QSSOAR, FSRSWOA, FLRSAR and GARS of different datasets.

It can be seen from Figs. 4 and 5 that the running time of GARS, FLRSAR and FSRSWOA was the shortest for Zoo, Monk1, Wine, Heart-Statlog, Vote, Mushroom datasets. While for the Breastcancer, Pima-Indians and Tic-Tac-Toe datasets, the running time of the proposed QSSOAR algorithm was close to that of GARS, FLRSAR and FSRSWOA, or even shorter. This is because the algorithm is sensitive to the number of attributes. When the number of attributes is small, the quick extraction strategy performs well. Compared with FSRSWOA and FLRSAR, GARS run longer in most cases due to the lack of mathematical operators. The running times of FSRSWOA and FLRSAR were close. The running time of IGRARACO algorithm was longer than that of the other four algorithms, due to the calculation of improved information gain rate and multiple redundancy detection calculation based on mutual information.

4.4 Analysis of optimization ability and convergence rate

In order to evaluate the optimization and convergence ability of our algorithm, the fitness value of different algorithms changing with the number of iterations was compared. The fitness value was calculated by the length weighting of attribute dependence and attribute subset according to Equation (17).

Table 4 shows the fitness function values of the five algorithms of 9 datasets. The maximum value of fitness function in iteration is regarded as the best fitness and the minimum fitness value is the worst fitness. Ave fitness is the average fitness of 200 iterations. The greater the best fitness, the better the solution. The smaller the worst fitness, the worse the solution. When the best fitness and worst fitness of two algorithms are the same, the greater the Ave fitness is, the better solution can be obtained with fewer iterations, which reflects the convergence and optimization ability of the algorithm.

Table 4
The fitness function value of each algorithm

Dataset Zoo

GARS IGRARACO FSRSWOA FLRSAR QSSOAR

Best fitness 0.96875 0.96875 0.95625 0.96875 0.96875

Worst fitness 0.93125 0.96875 0.95 0.95625 0.95625

Ave fitness 0.96359 0.96875 0.95609 0.96561 0.96866

Dataset Monk1

GARS IGRARACO FSRSWOA FLRSAR QSSOAR

Best fitness 0.95 0.95 0.95 0.95 0.95

Worst fitness 0.93333 0.95 0.93333 0.93333 0.95

Ave fitness 0.93833 0.95 0.93565 0.94967 0.95

Dataset Wine

GARS IGRARACO FSRSWOA FLRSAR QSSOAR

Best fitness 0.96923 0.96923 0.96923 0.96923 0.96923

Worst fitness 0.96154 0.96923 0.96154 0.96154 0.96923

Ave fitness 0.969 0.96923 0.96796 0.96869 0.96923

Dataset Heart-Statlog

GARS IGRARACO FSRSWOA FLRSAR QSSOAR

Best fitness 0.97692 0.97692 0.97692 0.97692 0.97692

Worst fitness 0.96154 0.97692 0.96923 0.96154 0.97692

Ave fitness 0.97681 0.97692 0.97688 0.96725 0.97692

Dataset Vote

GARS IGRARACO FSRSWOA FLRSAR QSSOAR

Best fitness 0.94375 0.94375 0.93552 0.93966 0.94586

Worst fitness 0.92909 0.94375 0.93134 0.9272 0.9375

Ave fitness 0.94251 0.94375 0.93545 0.93719 0.94569

Dataset Breastcancer

GARS IGRARACO FSRSWOA FLRSAR QSSOAR

Best fitness 0.95556 0.95556 0.95556 0.95556 0.95556

Worst fitness 0.94783 0.95556 0.95298 0.95169 0.95556

Ave fitness 0.95513 0.95556 0.95548 0.95550 0.95556

Dataset Pima-Indians

GARS IGRARACO FSRSWOA FLRSAR QSSOAR

Best fitness 0.9625 0.9625 0.9625 0.9625 0.9625

Worst fitness 0.95 0.9625 0.95 0.95547 0.9625

Ave fitness 0.9618 0.9625 0.96231 0.96236 0.9625

Dataset Tic-Tac-Toe

GARS IGRARACO FSRSWOA FLRSAR QSSOAR

Best fitness 0.9147 0.91111 0.91471 0.91471 0.91471

Worst fitness 0.91111 0.91111 0.91111 0.91111 0.91471

Ave fitness 0.91413 0.91111 0.91427 0.91453 0.91471

Dataset Mushroom

GARS IGRARACO FSRSWOA FLRSAR QSSOAR

Best fitness 0.96963 0.98788 0.97727 0.96818 0.98182

Worst fitness 0.96364 0.97727 0.95909 0.95909 0.96875

Ave fitness 0.96883 0.98735 0.97513 0.96773 0.98136

Dataset	Zoo
Best fitness	0.96875	0.96875	0.95625	0.96875	0.96875
Worst fitness	0.93125	0.96875	0.95	0.95625	0.95625
Ave fitness	0.96359	0.96875	0.95609	0.96561	0.96866
Dataset	Monk1
	GARS	IGRARACO	FSRSWOA	FLRSAR	QSSOAR
Best fitness	0.95	0.95	0.95	0.95	0.95
Worst fitness	0.93333	0.95	0.93333	0.93333	0.95
Ave fitness	0.93833	0.95	0.93565	0.94967	0.95
Dataset	Wine
	GARS	IGRARACO	FSRSWOA	FLRSAR	QSSOAR
Best fitness	0.96923	0.96923	0.96923	0.96923	0.96923
Worst fitness	0.96154	0.96923	0.96154	0.96154	0.96923
Ave fitness	0.969	0.96923	0.96796	0.96869	0.96923
Dataset	Heart-Statlog
	GARS	IGRARACO	FSRSWOA	FLRSAR	QSSOAR
Best fitness	0.97692	0.97692	0.97692	0.97692	0.97692
Worst fitness	0.96154	0.97692	0.96923	0.96154	0.97692
Ave fitness	0.97681	0.97692	0.97688	0.96725	0.97692
Dataset	Vote
	GARS	IGRARACO	FSRSWOA	FLRSAR	QSSOAR
Best fitness	0.94375	0.94375	0.93552	0.93966	0.94586
Worst fitness	0.92909	0.94375	0.93134	0.9272	0.9375
Ave fitness	0.94251	0.94375	0.93545	0.93719	0.94569
Dataset	Breastcancer
	GARS	IGRARACO	FSRSWOA	FLRSAR	QSSOAR
Best fitness	0.95556	0.95556	0.95556	0.95556	0.95556
Worst fitness	0.94783	0.95556	0.95298	0.95169	0.95556
Ave fitness	0.95513	0.95556	0.95548	0.95550	0.95556
Dataset	Pima-Indians
	GARS	IGRARACO	FSRSWOA	FLRSAR	QSSOAR
Best fitness	0.9625	0.9625	0.9625	0.9625	0.9625
Worst fitness	0.95	0.9625	0.95	0.95547	0.9625
Ave fitness	0.9618	0.9625	0.96231	0.96236	0.9625
Dataset	Tic-Tac-Toe
	GARS	IGRARACO	FSRSWOA	FLRSAR	QSSOAR
Best fitness	0.9147	0.91111	0.91471	0.91471	0.91471
Worst fitness	0.91111	0.91111	0.91111	0.91111	0.91471
Ave fitness	0.91413	0.91111	0.91427	0.91453	0.91471
Dataset	Mushroom
	GARS	IGRARACO	FSRSWOA	FLRSAR	QSSOAR
Best fitness	0.96963	0.98788	0.97727	0.96818	0.98182
Worst fitness	0.96364	0.97727	0.95909	0.95909	0.96875
Ave fitness	0.96883	0.98735	0.97513	0.96773	0.98136

In comparison with GARS, FSRSWOA and FLRSAR, QSSOAR had greater fitness function value and faster convergence, indicating that the algorithm can obtain better quality and fewer attributes reduction results in a short time. In addition, compared with IGRARACO algorithm, QSSOAR had greater fitness value of dataset Vote and Tic-Tac-Toe. This is because IGRARACO introduced the second redundancy detection strategy, which caused premature convergence and insufficient exploration, resulting in the suboptimal solution. Introduced similarity constraint strategy, adaptive opposition-based learning strategy and dynamic redundancy detection strategy, the proposed algorithm in this study has strong exploration ability, and can find a better solution.

5 Conclusions and future work

In this paper, we presented a new algorithm for attribute reduction based on quick extraction and multi-strategy social spider optimization. The algorithm has the advantages as follows.

Intelligent optimization computation mainly results from frequent calculation of fitness function values. Repeated calculation of fitness function will increase runtime. The fast extraction strategy proposed in this paper avoids the repeated calculation of fitness function and reduces the running time.

The initial population is no longer irregularly distributed in space. Individuals are restricted by the similarity constraint strategy close to the better performing individuals, which facilitates population exploration during the iteration process.

The quality of the reverse solution may be better than that of the original solution in the iterative process. Adaptive opposition-based learning strategy was incorporated to expand the search space and increase the possibility of exploring better solutions.

The dynamic redundancy detection strategy based on attribute importance was used to remove redundant attributes from the reduction results. The number of attributes is less without changing the classification ability.

Nine datasets were tested by the proposed QSSOAR and four representative algorithms such as GARS, FLRSAR, IGRARACO and FSRSWOA. The results indicate the IGRARACO algorithm has a good reduction efficiency, but the running time is too long. The GARS, FLRSAR, FSRSWOA algorithms run a short time, but the reduction effect is not ideal. In comparison, the algorithm proposed in this study has the advantages of strong reduction ability, short running time and fast convergence speed. At the same time, the experimental results show that the algorithm is sensitive to the number of attributes and can effectively reduce the running time when the number of attributes is small. However, for datasets with more attributes, performance needs to be improved because there may be too many combinations. In the future, we will try to combine fast calculation of equivalent classes with our algorithm to reduce the running time of datasets with more attributes. At the same time, we will try to use our algorithm to solve general combinatorial optimization problems.

Footnotes

Acknowledgments

I would like to express my deep gratitude to my mentor Qianjin Wei for his encouragement and guidance. Without his consistent and enlightening guidance, this paper cannot reach its present form. At the same time, we thank all reviewers for their valuable comments.

Funding

This work is supported by the Natural Science Foundation of China (Grand Nos. U1811264, U1711263, 61966009 and 61866007), Natural Science Foundation of Guangxi Province (Grand No. 2018GXNSFDA281045), and the Guangxi Key Laboratory of Trusted Software (Grand No. KX20202024).

References

Abd El Aziz

and Hassanien

A.E.

, An improved social spider optimization algorithm based on rough sets for solving minimum number attribute reduction problem, Neural Computing and Applications 30 (2018), 2441–2452.

Chen

, Zhu

and Xu

, Finding rough set reducts with fish swarm algorithm, Knowledge-Based Systems 81 (2015), 22–29.

Cuevas

, Cienfuegos

, Zaldívar

and Pérez-Cisneros

, A swarm optimization algorithm inspired in the behavior of the social-spider, Expert Systems with Applications 40 (2013), 6374–6384.

Ding

, Wang

and Wang

, Multigranulation consensus fuzzy-rough based attribute reduction, Knowledge-Based Systems 198 (2020), 105945.

Ibrahim

R.A.

, Elaziz

M.A.

, Oliva

, Cuevas

and Lu

, An opposition-based social spider optimization for feature selection, Soft Computing 23 (2019), 13547–13567.

Jensen

and Shen

, Semantics-preserving dimensionality reduction: rough and fuzzy-rough-based approaches, IEEE Transactions on Knowledge and Data Engineering 16 (2004), 1457–1471.

Jing

, Li

, Fujita

, Wang

and Cheng

, An incremental attribute reduction method for dynamic data mining, Information Sciences 465 (2018), 202–218.

Kulik

S.D.

and Protopopova

, Genetic algorithm and software tools for solving optimization problems in intelligent robotics, In Advanced Technologies in Robotics and Intelligent Systems, pp. 171–178. Springer, (2020).

Long

N.C.

, Meesad

and Unger

, Attribute reduction based on rough sets and the discrete firefly algorithm, In Recent Advances in Information and Communication Technology, pp. 13–22. Springer, (2014).

10.

Miao

and Hu

, A heuristic algorithm for reduction of knowledge, Journal of computer research and development 36 (1999), 681–684.

11.

Miao

and Wang

, An information representation of the concepts and operations in rough set theory, Journal of Software 10 (1999), 113–116.

12.

Min

, Zhang

Z.-H.

and Dong

, Ant colony optimization with partial-complete searching for attribute reduction, Journal of Computational Science 25 (2018), 170–182.

13.

Pawlak

, Rough sets, International Journal of Computer & Information Sciences 11 (1982), 341–356.

14.

Santra

, Basu

S.K.

, Mandal

J.K.

and Goswami

, Rough set based lattice structure for knowledge representation in medical expert systems: Low back pain management case study, Expert Systems with Applications 145 (2020), 113084.

15.

Sun

and Ji

, Integrated kitchen design and optimization based on the improved particle swarm intelligent algorithm, Computational Intelligence 36 (2020), 1638–1649.

16.

Tang

, Srivastava

and Liu

, Swarm intelligence and ant colony optimization in accounting model choices, Journal of Intelligent & Fuzzy Systems 38 (2020), 2415–2423.

17.

Vluymans

, D’eer

, Saeys

and Cornelis

, Applications of fuzzy rough set theory in machine learning: A survey, Fundamenta Informaticae 142 (2015), 53–86.

18.

Wang

and Chen

, Feature selection method based on rough sets and improved whale optimization algorithm, Computer Science 47 (2020), 44–50.

19.

Wang

, Sun

, Wang

and Tao

, Multi-objective social spider optimisation algorithm, The Journal of Engineering 2018 (2018), 1521–1527.

20.

Watada

, Tan

S.C.

, Matsumoto

and Vasant

, Rough setbased text mining from a large data repository of experts’ diagnoses for power systems, In Intelligent Decision Technologies 2017, pp. 136–144. Springer, (2018).

21.

Wei

, Wei

and Wen

, Attribute reduction algorithm based on improved information gain rate and ant colony optimization, In Advances in Knowledge Discovery and Data Mining, pp. 139–150. Springer, (2018).

22.

, Zhang

, Xie

and Xie

, An attribute reduction algorithm based on mutual information of particle swarm optimization, Acta Electronica Sinica 45 (2017), 2695–2704.

23.

Yamany

, Emary

and Hassanien

A.E.

, New rough set attribute reduction algorithm based on grey wolf optimization, In The 1st International Conference on Advanced Intelligent System and Informatics (AISI2015), pp. 241–251. Springer, (2016).

24.

Yamany

, Emary

, Hassanien

A.E.

, Schaefer

and Zhu

S.Y.

, An innovative approach for attribute reduction using rough sets and flower pollination optimisation, Procedia Computer Science 96 (2016), 403–409.

25.

Yan

, Zhang

and Tang

, Modified whale optimization algorithm for underwater image matching in a UUV vision system, Multimedia Tools and Applications 80 (2021), 187–213.

26.

and Chen

, An efficient combinatorial artificial bee colony algorithm for solving minimum attribute reduction problem, Acta Electronica Sinica (2015), 1014–1020.

27.

Zhao

, Luo

and Zhou

, Elite opposition-based social spider optimization algorithm for global function optimization, Algorithms 10 (2017), 9.

28.

Zhou

, Guo

, Sun

and Wu

, Data mining method based on rough set and fuzzy neural network, Journal of Intelligent & Fuzzy Systems 38 (2020), 3717–3725.

29.

Zhou

, Zhou

, Luo

and Abdel-Basset

, A simplex method-based social spider optimization algorithm for clustering analysis, Engineering Applications of Artificial Intelligence 64 (2017), 67–82.

Minimum attribute reduction algorithm based on quick extraction and multi-strategy social spider optimization

Abstract

Keywords

1 Introduction

2 Preliminaries

2.1 Rough set theory

Table 1 An example of decision system Patient Muscle Headache Snivel Flu e 1 Yes Yes Yes Yes e 2 No Yes No Yes e 3 Yes No No No e 4 No No Yes Yes e 5 No No No No

4 Experimental results and discussion

4.1 Experimental environment and parameter setting

4.3.1 Comparison of running time between QSSOAR and ISSOAR

Footnotes

Acknowledgments

Funding

References

Table 1
An example of decision system

Patient Muscle Headache Snivel Flu

e ₁ Yes Yes Yes Yes

e ₂ No Yes No Yes

e ₃ Yes No No No

e ₄ No No Yes Yes

e ₅ No No No No