# Semisupervised Bacterial Heuristic Feature Selection Algorithm for High-Dimensional Classification with Missing Labels

Authors: Hong Wang; Yikun Ou; Yixin Wang; Tongtong Xing; Lijing Tan
Journal: International Journal of Intelligent Systems
 (2023)

---

## Abstract

Feature selection is a crucial method for discovering relevant features in high-dimensional data. However, most studies primarily focus on completely labeled data, ignoring the frequent occurrence of missing labels in real-world problems. To address high-dimensional and label-missing problems in data classification simultaneously, we proposed a semisupervised bacterial heuristic feature selection algorithm. To track the label-missing problem, ak-nearest neighbor semisupervised learning strategy is designed to reconstruct missing labels. In addition, the bacterial heuristic algorithm is improved using hierarchical population initialization, dynamic learning, and elite population evolution strategies to enhance the search capacity for various feature combinations. To verify the effectiveness of the proposed algorithm, three groups of comparison experiments based on eight datasets are employed, including two traditional feature selection methods, four bacterial heuristic feature selection algorithms, and two swarm-based heuristic feature selection algorithms. Experimental results demonstrate that the proposed algorithm has obvious advantages in terms of classification accuracy and selected feature numbers.


---

## Body

## 1. Introduction

The dimensionality of data, which consists of many features, is one of the most influential aspects of the classification model’s effectiveness [1]. Based on feature properties, instances can be categorized into their respective classes. However, redundant, irrelevant, and noisy features in high-dimensional data will hamper classification accuracy [2, 3], e.g., medical or clinic data classification [4, 5]. Particularly, it is challenging to distinguish between representative and meaningless features without prior knowledge [6]. On the other hand, due to statistical norms and personal errors, data classification in real life often faces missing labels and loses more valid sample problems, which ultimately reduces the accuracy and robustness of the classification model [5, 7, 8]. To reduce feature dimensionality and improve the classification performance in classification, feature selection (FS) [9] is recommended to collect more relevant feature subsets from the original data space. As a tool for optimizing data space, FS can make classification less complicated and improve the precision of classification models [10].FS methods can be categorized as filter, wrapper, or embedded based on various feature evaluation criteria [11]. Filter methods use specific statistical metrics, such as information gain [12] and Fisher score [13], to evaluate the performance of created feature subsets, while wrapper methods use learning algorithms, such as K-nearest neighbor [14], naive Bayes [15], and linear discriminant analysis [16]. Embedded approaches, such as the least absolute shrinkage and selection operator [17] and ridge regression [18], embed FS into the training process for the learner. Filter methods typically execute faster than wrapper methods, but they cannot frequently achieve a higher degree of classification precision [19]. In addition, the process of designing embedded methods is intricate and necessitates plenty of prior experience [20]. Since the high-dimensional classification problem with only partial labels is already a hard task, this research investigates wrapper-based FS methods to ensure a higher accuracy while avoiding increasing classification difficulties.Wrappers seek to find the best subset from feature space according to one predetermined performance assessment. However, it is realistic to select all possible subsets of features measured by wrappers in high-dimensional classification problems because of the computational cost. Recently, wrappers based on population-based algorithms have been wildly developed without the necessity of evaluating all possible subsets. Tran et al. [21] proposed the first variable-length particle swarm optimization representation for FS, enabling particles to have different and shorter lengths, which improves the performance of the algorithm. Considering the convergency of the population, Song et al. [22] proposed a variable-size cooperative coevolutionary strategy to optimize the searching population, which employs the idea of “divide and conquer” in the cooperative coevolutionary approach. However, since wrapper-based FS methods do not perform feature filtering in advance, the searching space for them is the whole data space [23]. This means that in high-dimensional classification tasks, their search space is very large, so they have to use a heuristic strategy like random search to reduce the cost of computation [24]. Nevertheless, classic heuristic strategy wrapper-based FS methods, such as particle swarm optimization-based FS [25], differential evolution-based FS [26], and genetic algorithm-based FS [27], do not account for all potential feature combinations [28].In recent years, bacterial-based algorithms such as bacterial foraging optimization (BFO) [29] have been used to design FS methods to resolve combinatorial difficulties due to their global searching capability for control and optimization [30]. However, the intricate structure of BFO limits its computation efficiency. To achieve efficient classification results, bacterial colony optimization (BCO) [31] with a new bacterial life cycle was proposed and laid the foundation for the following research on bacterial-based FS algorithms and applications [6, 28, 30, 32, 33]. The majority of those research studies offer algorithmic enhancements in terms of weight setting, parameter optimization, and learning strategy optimization. Nonetheless, in actual applications, the integrity of data itself is a significant element, influencing the efficiency of FS, particularly the problem of incomplete sample labels, which is the most common and complicated task. This study focuses on developing an enhanced bacterial-based FS approach with a semisupervised learning strategy to address the high-dimensional medical data classification with partial labels.According to the integrity of data labels, learning tasks can be categorized into supervised learning, semisupervised learning, and unsupervised learning [33]. In the supervised task, training data have complete label information, whereas in semisupervised learning, label information is only available in part. Unsupervised learning means that analyzed data do not contain labels [34]. In the absence of prior knowledge, the accuracy of supervised learning is generally higher than that of semisupervised learning. Nevertheless, the cost of getting complete labeled data is extremely high in practical medical data collection. Moreover, unsupervised learning is usually used to disclose the initial pattern of unlabeled data [35]. Therefore, to address high-dimensional classification difficulty and label missing limitations in medical data, this paper investigated semisupervised medical data classification problems and optimized the classification model by learning from partially labeled data to classify unlabeled data into the correct class.Semisupervised learning has been widely studied in different fields, and in the human activity recognition (HAR) problem, Chen et al. [36] designed a semisupervised deep learning model that is useful in solving the problem of imbalanced distribution of labeled data over classes from multimodal wearable sensory data. In video semantic recognition problems, Luo et al. [37] proposed a novel semisupervised feature selection method to learn the optimal graph, which aims to upgrade the performance of video semantic recognition. Since the research studies mentioned above are based on multimodal data, it makes more sense to employ deep learning or graph machine learning to overcome the problem of missing data labels. Despite the fact that these methods are effective for multimodal data, they incur substantial computational costs. Frequently, for a single mode of data, it is not necessary to use overly complex techniques. In contrast, feature selection methods based on wrappers need less computation, and hence, they are more suitable for single-type data. In terms of wrapper-based FS methods, certain representative semisupervised classification algorithms, such as ensemble SVM-based semisupervised FS [38] and rough set-based semisupervised FS [39], have demonstrated the ability of ensemble learning to solve label-missing problems. Nevertheless, these methods rely on ensemble classifiers to choose the best subset by voting for the results, which increases the computational cost marginally. As a straightforward and easy-to-use technique, K-nearest neighbor (KNN)-based semisupervised learning [40] offers great promise for improving the classification effect with missing labels. A number of studies utilize semisupervised KNN. Zhang et al. [38] demonstrated that the introduction of semisupervised learning with K-nearest neighbor (KNN) can enhance the available training sample size, provided that K is held constant. However, Mehta et al. [41] discovered that the magnitude of K would impact the efficiency of the algorithm. The precision of the results was enhanced by the use of an exhaustive procedure to determine a suitable value of K for solving the problem. Nevertheless, in partially labeled data, different learning densities of KNN may lead to biased results. When the value of K is small, model learning may not be comprehensive. When the value of K is large, operation cost may increase. In other words, the selection of the K value is a key issue to be explored. Therefore, this study attempts to develop a new semisupervised KNN learning approach that allows for the selection of K and can be combined with bacterial-based FS to form an effective classification method.In this study, we propose a semisupervised bacterial heuristic feature selection (SHBFS) algorithm for the medical data classification mentioned earlier, i.e., label incomplete and high-dimensional redundant features. The main contributions of this research are as follows:(i)
A new self-adjusted semisupervised feature selection approach is proposed to solve the classification problems with missing labels and high-dimensional redundant features using a two-step self-training mechanism and an improved bacterial heuristic method(ii)
The strategies of hierarchical population initialization, dynamic learning, and elite population evolution are proposed to enhance the capacity of the bacterial heuristic algorithm in searching for various feature combinations(iii)
The proposed semisupervised bacterial heuristic feature selection algorithm is studied to be superior in addressing label incomplete and high-dimensional classification tasks in comparison to several state-of-the-art semisupervised FS algorithmsThe rest of this paper is organized as follows: Section2 gives the background of bacterial-based feature selection methods and some related works on these topics. The proposed method is introduced in Section 3. In Section 4, the experimental configuration is given. The experiments and analyses of the results are provided in Section 5. The final section presents the conclusions and a description of future work.


## 2. Related Work

The life cycle of the searching algorithm of the proposed bacterial-based FS approach in this study is inspired by BCO. Thus, this section briefly introduces its main principle and reviews of bacterial-based feature selection methods. More details are as follows.


### 2.1. Bacterial Colony Optimization

The life cycle of BFO is a triple-nested loop structure, which brings enormous computational complexity to solve high-dimensional problems. BCO simplifies the life cycle according to specific rules to address this computational drawback. Similar to BFO, BCO contains reproduction and elimination-dispersal processes. However, the chemotaxis steps in BCO are simplified as running and tumbling processes. Conditional controlling rules are used to cope with the traditional triple-nested loop structure to improve algorithm efficiency. The pseudocode of BCO is shown inPseudocode 1.Pseudocode 1: Bacterial colony optimization (BCO).
(1)
Input: original data(2)
Initialization: P (population), MaxIt (max iterations), and C (chemotaxis step size)(3)
While maximum iterations are not satisfied do(4)
For each bacterium do(5)
Chemotaxis process (refer to Equation (1))(6)
Fitness evaluation(7)
If previous fitness < current fitness(8)
Tumbling process (refer to (2))(9)
End//alternative mechanisms(10)
If the reproduction condition is satisfied do(11)
Reproduction process (refer to article [29])(12)
End(13)
If elimination-dispersal conditions are satisfied do(14)
Elimination-dispersal according to Equations (3) and (4)(15)
End(16)
End(17)
End//life cycle(18)
Output: optimal position with the best fitness


#### 2.1.1. Running Process

The running process is designed to speed convergence to the optimal position as(1)θit=θit−1+ri⋅gbest−θit−1+1−ri⋅pbesti−θit−1,where ri shows the learning coefficient randomly generated between [0, 1], gbest is the best position in the current bacterial colony, and pbesti represents the individual optimal position during the chemotaxis process. In addition, communication schemes such as dynamic neighbor and group-oriented learning can be embedded into the running process.


#### 2.1.2. Tumbling Process

The tumbling process avoids being trapped in the local optimum and explores more potential solution spaces. As shown in Equation (2), a random direction vector Δi is generated between [−1, 1] for the ith bacterium. Although the randomly generated direction is correct, i.e., the current fitness is improved, the bacterium continues to exploit in the same direction.(2)θit=θit−1+ri⋅gbest−θit−1+1−ri⋅pbesti−θit−1+Ci⋅ΔiΔiT⋅Δi.The reproduction and elimination mechanisms in BCO are consistent with those in BFO [29]. For the reproduction operation, half of the population with better performance is used to replace the remaining half with poor performance, while the elimination of BCO is realized by assigning the bacterium a new and random position within the search space. It can be formulated as follows.IfP<Ped, then(3)θt=lp+rand×up−lp.Otherwise,(4)θt=θt,where Ped is a constant to determine the probability of the ith bacterium being assigned in a new position and upandlp are the upper and the lower boundaries of the search space, respectively. In this study, all BFO or BCO-based FS are referred to as bacterial-based FS, and the pertinent research reviews are detailed in the following section.


### 2.2. Bacterial Heuristic Feature Selection Methods

In recent years, research on bacterial-based FS algorithm improvements and applications has gradually increased. The process of bacterial-based FS consists primarily of the following steps [42]: (i) input the original data, (ii) randomly search for different features to form a small subset, (iii) use the subset to train the classifier, with the classification results to guide the bacteria search, (iv) output the optimal fitness of the current iteration, and (v) loop steps ii∼iv until the maximum number of iterations is reached and output the final optimal fitness.In recent years, bacterial heuristic FS has many applications, including health care, recommendation, recognition, and model training [6, 30, 43, 44]. To improve the classification effect, bacterial-based FS has been improved in many ways. One improvement way is weight setting. Wang et al. [6] developed a weighted strategy to control the probability of different features being selected to enhance the accuracy. The other is population optimization, which can be further subdivided into position updates and population updates. For position updates, Wang and Chen [43] incorporated chaotic mechanisms into the chemotaxis and position-updating stages of bacterial populations to increase their adaptability. For population updates, some studies divided bacteria into multiple groups to perform different jobs under the control of different modified population updating strategies to improve the searching efficiency [32]. Furthermore, learning strategy optimization is also a common and useful method. For example, Kaur and Kadam [45] investigated multiobjective BFO to improve bacterial learning ability and improve the convergence speed of the algorithm. Wang et al. designed an adaptive attribute learning strategy to enhance the information communication ability among bacteria [30].In summary, bacterial-based FS research focuses mostly on algorithm enhancement and the application of various situations. However, the combined effect of missing labels and high-dimensional redundant features poses significant challenges to optimizers (including bacterial heuristic algorithms) in FS, as the search space of FS problems expands exponentially and the proportion of incomplete data increases synchronously. Therefore, improving the effectiveness and efficiency of bacterial heuristic algorithms while considering semisupervised learning methods and data dimension reduction simultaneously is worth studying. Therefore, in this study, we focus on the development of a semisupervised feature selection approach based on bacterial optimization to solve classification problems with missing labels and high-dimensional redundant features.


## 2.1. Bacterial Colony Optimization

The life cycle of BFO is a triple-nested loop structure, which brings enormous computational complexity to solve high-dimensional problems. BCO simplifies the life cycle according to specific rules to address this computational drawback. Similar to BFO, BCO contains reproduction and elimination-dispersal processes. However, the chemotaxis steps in BCO are simplified as running and tumbling processes. Conditional controlling rules are used to cope with the traditional triple-nested loop structure to improve algorithm efficiency. The pseudocode of BCO is shown inPseudocode 1.Pseudocode 1: Bacterial colony optimization (BCO).
(1)
Input: original data(2)
Initialization: P (population), MaxIt (max iterations), and C (chemotaxis step size)(3)
While maximum iterations are not satisfied do(4)
For each bacterium do(5)
Chemotaxis process (refer to Equation (1))(6)
Fitness evaluation(7)
If previous fitness < current fitness(8)
Tumbling process (refer to (2))(9)
End//alternative mechanisms(10)
If the reproduction condition is satisfied do(11)
Reproduction process (refer to article [29])(12)
End(13)
If elimination-dispersal conditions are satisfied do(14)
Elimination-dispersal according to Equations (3) and (4)(15)
End(16)
End(17)
End//life cycle(18)
Output: optimal position with the best fitness


### 2.1.1. Running Process

The running process is designed to speed convergence to the optimal position as(1)θit=θit−1+ri⋅gbest−θit−1+1−ri⋅pbesti−θit−1,where ri shows the learning coefficient randomly generated between [0, 1], gbest is the best position in the current bacterial colony, and pbesti represents the individual optimal position during the chemotaxis process. In addition, communication schemes such as dynamic neighbor and group-oriented learning can be embedded into the running process.


### 2.1.2. Tumbling Process

The tumbling process avoids being trapped in the local optimum and explores more potential solution spaces. As shown in Equation (2), a random direction vector Δi is generated between [−1, 1] for the ith bacterium. Although the randomly generated direction is correct, i.e., the current fitness is improved, the bacterium continues to exploit in the same direction.(2)θit=θit−1+ri⋅gbest−θit−1+1−ri⋅pbesti−θit−1+Ci⋅ΔiΔiT⋅Δi.The reproduction and elimination mechanisms in BCO are consistent with those in BFO [29]. For the reproduction operation, half of the population with better performance is used to replace the remaining half with poor performance, while the elimination of BCO is realized by assigning the bacterium a new and random position within the search space. It can be formulated as follows.IfP<Ped, then(3)θt=lp+rand×up−lp.Otherwise,(4)θt=θt,where Ped is a constant to determine the probability of the ith bacterium being assigned in a new position and upandlp are the upper and the lower boundaries of the search space, respectively. In this study, all BFO or BCO-based FS are referred to as bacterial-based FS, and the pertinent research reviews are detailed in the following section.


## 2.1.1. Running Process

The running process is designed to speed convergence to the optimal position as(1)θit=θit−1+ri⋅gbest−θit−1+1−ri⋅pbesti−θit−1,where ri shows the learning coefficient randomly generated between [0, 1], gbest is the best position in the current bacterial colony, and pbesti represents the individual optimal position during the chemotaxis process. In addition, communication schemes such as dynamic neighbor and group-oriented learning can be embedded into the running process.


## 2.1.2. Tumbling Process

The tumbling process avoids being trapped in the local optimum and explores more potential solution spaces. As shown in Equation (2), a random direction vector Δi is generated between [−1, 1] for the ith bacterium. Although the randomly generated direction is correct, i.e., the current fitness is improved, the bacterium continues to exploit in the same direction.(2)θit=θit−1+ri⋅gbest−θit−1+1−ri⋅pbesti−θit−1+Ci⋅ΔiΔiT⋅Δi.The reproduction and elimination mechanisms in BCO are consistent with those in BFO [29]. For the reproduction operation, half of the population with better performance is used to replace the remaining half with poor performance, while the elimination of BCO is realized by assigning the bacterium a new and random position within the search space. It can be formulated as follows.IfP<Ped, then(3)θt=lp+rand×up−lp.Otherwise,(4)θt=θt,where Ped is a constant to determine the probability of the ith bacterium being assigned in a new position and upandlp are the upper and the lower boundaries of the search space, respectively. In this study, all BFO or BCO-based FS are referred to as bacterial-based FS, and the pertinent research reviews are detailed in the following section.


## 2.2. Bacterial Heuristic Feature Selection Methods

In recent years, research on bacterial-based FS algorithm improvements and applications has gradually increased. The process of bacterial-based FS consists primarily of the following steps [42]: (i) input the original data, (ii) randomly search for different features to form a small subset, (iii) use the subset to train the classifier, with the classification results to guide the bacteria search, (iv) output the optimal fitness of the current iteration, and (v) loop steps ii∼iv until the maximum number of iterations is reached and output the final optimal fitness.In recent years, bacterial heuristic FS has many applications, including health care, recommendation, recognition, and model training [6, 30, 43, 44]. To improve the classification effect, bacterial-based FS has been improved in many ways. One improvement way is weight setting. Wang et al. [6] developed a weighted strategy to control the probability of different features being selected to enhance the accuracy. The other is population optimization, which can be further subdivided into position updates and population updates. For position updates, Wang and Chen [43] incorporated chaotic mechanisms into the chemotaxis and position-updating stages of bacterial populations to increase their adaptability. For population updates, some studies divided bacteria into multiple groups to perform different jobs under the control of different modified population updating strategies to improve the searching efficiency [32]. Furthermore, learning strategy optimization is also a common and useful method. For example, Kaur and Kadam [45] investigated multiobjective BFO to improve bacterial learning ability and improve the convergence speed of the algorithm. Wang et al. designed an adaptive attribute learning strategy to enhance the information communication ability among bacteria [30].In summary, bacterial-based FS research focuses mostly on algorithm enhancement and the application of various situations. However, the combined effect of missing labels and high-dimensional redundant features poses significant challenges to optimizers (including bacterial heuristic algorithms) in FS, as the search space of FS problems expands exponentially and the proportion of incomplete data increases synchronously. Therefore, improving the effectiveness and efficiency of bacterial heuristic algorithms while considering semisupervised learning methods and data dimension reduction simultaneously is worth studying. Therefore, in this study, we focus on the development of a semisupervised feature selection approach based on bacterial optimization to solve classification problems with missing labels and high-dimensional redundant features.


## 3. Proposed Approach

This section presents the proposed SHBFS approach to solve classification problems with missing labels and high-dimensional redundancy features. Figure1 shows the structure of SHBFS. From the figure, we can see that the SHBFS approach consists of two main parts. On the one hand, a self-adjusted, semisupervised KNN strategy is presented for solving the problem of missing labels. On the other hand, an improved bacterial heuristic method for FS is presented for addressing the feature redundant problem, including three improvements: hierarchical population initialization, dynamic learning, and elite population evolution strategy. Hierarchical population initialization is used to obtain informative searching positions for bacteria to accelerate population convergence. Dynamic learning increases the searching variety of the algorithm by adaptively changing the search step length of bacteria. Finally, an elite population evolution strategy is employed to enhance the ability of bacteria to escape from the local optimum.Figure 1
The overall structure of the proposed SHBFS approach.


### 3.1. Self-Adjusted, Semisupervised KNN

The proposed self-adjusted, semisupervised KNN is a two-step self-training method, consisting ofK value determination and label construction. Furthermore, to make the semisupervised learning method more adaptive to datasets of different sizes, the K value is adjusted as follows:(5)K=1:1:NS,NS<10,1:lgNS:10∗lgNS,10≤NS,where NS is the number of data samples, which means that the K value linearly increases when datasets have smaller samples, while the logarithmic function is employed for datasets with larger sample sizes. The primary process of the self-adjusted, semisupervised KNN is illustrated as follows:Step 1. K Value DeterminationThe samples with the labeled class and unlabeled class are separately saved in the datasetL and dataset U. As mentioned previously, a self-adjusted, semisupervised KNN is presented for labeling the data with no assignment in categories and finding the best K value for classification. This step is to determine a K value for the label reconstruction using the labeled samples in L, provided in Pseudocode 2.Step 2. Label ReconstructionLabel reconstruction is provided inPseudocode 3. First, self-adjusted, semisupervised KNN is used to predict the labels for the samples from the dataset U. Then, newly labeled samples are moved from the dataset U to the dataset L. With increasing L in the space size, the self-training step can increase the learning efficiency of the training model.Pseudocode 2: Determination of the K value.
(1)
Input: L (L is used to save the labeled samples in the original dataset)(2)
For each K obtained by Equation (5)(3)
For each running time(4)
Randomly divideL into two subsets/∗ half with saved labels and half with removed labels ∗/(5)
Use the labeled subset to predict the labels of the unlabeled subset by KNN(6)
Record the accuracy of label prediction on each running time(7)
End(8)
Record theK value and the average accuracy of label prediction of each K(9)
End(10)
Output: Best (K value with the maximum average accuracy)Pseudocode 3: Label reconstruction.
(1)
Input: labeled dataset L and unlabeled dataset U, best(2)
For each unlabeled sample in the dataset U(3)
Use the samples from the datasetL to predict the label by KNN (using Kbest)(4)
Assign the predicted label to the unlabeled sample and move it fromU to L(5)
End(6)
Output: the updated dataset L


### 3.2. Hierarchical Population Initialization

In BCO, the population is initialized randomly in a feasible space. However, addressing feature selection with high-dimensional features might make the bacterial colony fall into a poor searching position due to the high uncertainty of population initialization. As a result, more effort will be taken to jump out from their original position, which brings redundant computational complexity. To solve this problem, we develop a hierarchical population initialization strategy to enable bacteria to start at relatively good positions and further accelerate the convergence speed of the population. In contrast to the aforementioned variable-size cooperative coevolutionary technique, hierarchical population initialization does not use multipopulation for searching. Instead, it uses the idea of the proposed feature hierarchical division strategy to reconstruct a smaller search space before each search. The hierarchical population initialization consists of three steps. The details are as follows:Step 1. Feature Ranking and FilteringInitially, a symmetrical uncertainty (SU) [21] ranking is performed on the original features according to Equations (6)–(9). In this step, the correlations between features and classes are ranked, and the features’ relevant significance is ordered from highest to lowest. After ranking, the worst 10 percent of features with significance below the mean are eliminated.(i)
Symmetrical uncertainty (SU): the SU index has been widely used in traditional FS methods based on information theory. SU measures the uncertainty between feature variablesf∈F, with label signals l∈L given in Equations (6)–(9) based on the Shannon information entropy. In those formulas, pf is the prior probability for all values of f and pf|l is the posterior probability of f given l:(6)SUf,l=2Hf−Hf|lHf+Hl,(7)Hl=−∑i=1Nplilog2pli,(8)Hl=−∑l=1Nplilog2pli,(9)Hf|l=−∑j=1Nplj∑i=1Npfi|ljlog2pfi|lj,whereHf and Hl are the entropy of the feature variable f and the label signal l, respectively. N is the number of observation samples x∈X. SUf,l evaluates the correlation between features f and label signals l. A larger SUf,l indicates a higher significance of the feature f to the label l. This means that the feature f has more robust ability to discriminate labels, and the feature f needs to be selected into the feature subset.Step 2. Feature Hierarchical DivisionAs shown in Figure2, it is assumed that the numbers of SU are significant in the box. According to their significance, sorted features will be divided evenly into three layers, L1, L2, and L3. After that, 80% of the feature dimension will be randomly selected from the L1 set, 15% from the L2 set, and 5% from the L3 set to form a searching position for bacteria. This strategy can exclude subpar features and shrink the search space when dealing with high-dimensional features.Step 3. Feature Weight UpdatingWe assume that the feature size isH, and each feature of the ith bacterium is denoted as fi. We define the current fitness as fit(fi) and the historical fitness as Fit(fi). In this paper, we adopt a weight mechanism [6] to evaluate the performance of features. The rules are as follows: if fit(fi) < Fit(fi), then the performance weight pfi will be increased by (12). Otherwise, pfi will be decreased by Equation (13).Figure 2
Feature hierarchical division.Given that, after completing the aforementioned procedure, there are still unselected features in each feature layer. To increase these features’ probability of being selected in the future, we defined the unselected weight (Uweight) of fi as ufi and Uweight=uf1,uf2,...,ufH. Then, the weight of each unselected feature will be updated by Equation (10) after Step 2. In each feature selection process, if one feature has been selected repeatedly in each search, then its ufi will be decreased by Equation (11):(10)ufi=ufi+0.01ufi,ufi∈L1,ufi+0.001ufi,ufi∈L2,ufi+0.0001ufi,ufi∈L3,(11)ufi=ufi−maxufi−minufi,(12)pfi=pfi+Fitfi−fitfiFitfi,(13)pfi=pfi−Fitfi∗Fitfi−fitfi,where fi is each feature of the ith bacterium, ufi is the unselected weight, pfi is the performance weight, L1,L2,L3 are layers obtained in Step 2, fit(fi) is the current fitness of fi, and Fit(fi) is the historical fitness.


### 3.3. Dynamic Learning

In BCO, the chemotaxis step length of bacteria is governed by a set of fixed values denoted byCi. However, the lack of variation in step lengths may trap bacteria within the same search space. On a long-term basis, the diversity of feature subsets will decline. Therefore, in SHBFS, the running process is the same as that in BCO, while the tumbling process is improved by employing a dynamic learning strategy to increase the search variety.Specifically, a dynamic learning strategy is proposed by adopting an adaptive chemotaxis step length changing strategy, which is denoted asaC [46], and a step length communication strategy dC. Equations (14) and (15) show that aC is affected by the bacterial size S, where S = 1,2,…,i,i∈N+. We define the current fitness as fit, the upper bound of the step length as Cub, and the lower bound of the step length as Clb. ∂ is the disturbance factor. As the iteration proceeds, the disturbance effect of ∂ on aC will become small. In addition, the larger the fit, the larger the value of aC. The step length can be changed dynamically by aC:(14)∂=1−is×Cub−Clb+Clb,(15)aC=fitfit+∂.There is no information communication among the bacteria in BCO. To enhance the convergence speed and improve the search capability, this paper presents a step length communication strategy. LetdC be the step length after communication, and its size is S × D, where D = 1,2,…,d,d∈N+ is the dimension of bacteria. Equation (16) shows the communication process of ith bacteria in the tth iteration:(16)dCt=0.01×aC+cpi⋅Rpi⋅pbesti−θit+cgi⋅Rgi⋅gbesti−θit,where θit is the current position of the bacterium, cp and cg are constant learning factors, and Rp and Rg are random disturbance terms. Rp and Rg are confined to [0, 1]. The step length size in SBHFS learns from the best population record of individual bacteria (pbest) and the best population record of the bacteria (gbest). For this, bacteria will prefer to learn from the record with a larger position excursion. After updating the step length dC, bacterial population tumbling is conducted as follows:(17)θit=θit−1+dCt−1⋅ΔiΔiT⋅Δi⋅Oq,where ∆i is a random direction vector generated between [−1, 1] for the ith bacterium. Due to varying data sizes, the range of bacterial location change is greater in large samples than in small samples. Therefore, Oq = O1,O2,q=1,2. has been proposed in this paper to adjust the offset of the bacterial position. In the tumbling process, q = 1; in the swimming process, q = 2. The setting of O1 and O2 is explained in Section 4.3. We define the number of features of the whole dataset as H, and the selected feature subset size is D. If H < D, O1 = O2 = 1.After tumbling, the feature subset is formed by Equation (18), where · represents the rounding operator. The performance of the feature subset is measured by a classifier. Thus, we adopt the confusion matrix [47] as an evaluation metric, and the fitness is the error rate, which is updated by Equation (19).(18)θi1t,…,θidt,(19)fit=FP+FNTP+TN+FP+FN,where FP is the false-positive result, FN is the false-negative result, TP is the true-positive result, and TN is the true-negative result. fit is the current fitness. Fit is defined as the historical fitness. The current best fitness is fpbest, and the historical best fitness is fgbest. The main process of dynamic learning is shown in Pseudocode 4.Pseudocode 4: Dynamic learning.
(1)
Input: fit, Pweight, Uweight, fpbest, and fgbest(2)
For each bacterium(3)
Running process by equation (1)//running(4)
Update the guiding factoraC by Equations (14) and (15)(5)
Update the step lengthdC by Equation (16)(6)
Update the position by Equation (17)//tumbling(7)
Get the feature subset by Equation (18)(8)
Update fit by Equation (19) and update Uweight by Equation (11)(9)
If fit < fpbest(10)
fpbest = fit(11)
UpdatePweight by Equation (12)(12)
Else(13)
UpdatePweight by Equation (13)(14)
End(15)
Iffpbest < fgbest(16)
fgbest = fpbest(17)
End(18)
Swimming byPseudocode 5.(19)
End(20)
Output: fit and the feature subsetPseudocode 5: Elite population evolution mechanism.
(1)
Input: fit, Fit, Pweight, Uweight, fpbest, and fgbest(2)
For each bacterium(3)
While doing the swimming loop(4)
If fit < Fit(5)
Fit= fi(6)
IfbT > control threshold//it means bad effect searching(7)
Do dispersal elimination(8)
RankF by Uweight and save as SF//SF is the sorted feature(9)
Ɵ = randomly selecting D features from the top half of SF(10)
Else//D is the bacterial dimension(11)
Do reproduction(12)
Forr = 1: Sr//Sr is the reproduction size of bacteria(13)
Sort the positionƟ of bacteria(14)
Sort featuresF by Pweight and save as SF(15)
Ɵr+Sr = SF(Sr)(16)
End(17)
End(18)
End(19)
Get the feature subset by Equation (18)(20)
Update fit by Equation (19) and update Uweight by Equation (11)(21)
If fit < fpbest(22)
fpbest = fit(23)
UpdatePweight by Equation (12)(24)
Iffpbest < fgbest(25)
fgbest = fpbest(26)
End(27)
Else(28)
UpdatePweight by Equation (13)(29)
End(30)
End(31)
End(32)
Output: fit and the feature subset


### 3.4. Elite Population Evolution

In most bacterial-based methods, the population will randomly undergo dispersal elimination. This means that the new searching position of bacteria could be good or bad. The bad searching position may waste the search time. To make population evolution more meaningful, this paper designed an elite population evolution mechanism usingPweight and Uweight values aforementioned in Section 3.2, which are to guide bacteria to conduct reproduction and dispersal elimination.In SBHFS, either reproduction or dispersal elimination will be conducted per iteration. The elite population evolution mechanism is proposed to determine which operation is executed, as depicted in Figure3. After dynamic learning, bacteria will perform a swimming loop as BFO until they meet the threshold Ns (see Table 1). In the swimming loop, each bacterium will first undergo a fitness evaluation to determine its performance. errTre is defined as the performance threshold. If the fitness exceeds errTre, it will be counted in bT. When bT is larger than half of Ns, we can simply regard this bacterium by performing a bad search, and dispersal elimination is conducted based on the Uweight matrix. Otherwise, bacteria will reproduce based on the Pweight matrix. Next, we calculate the fitness of the new bacteria and updated two weights (Pweight and Uweight). Finally, we repeat preceding steps until the end of the loop. The main process of the elite population evolution mechanism is given in Pseudocode 5.Figure 3
The elite population evolution mechanism.Table 1
The settings of parameters for benchmark methods.
AlgorithmsParameter settingsSBHFSerrTre = 0.6, cp = 0.0015, cg = 0.0015, Ns = 4Cub = 0.15, Clb = 0.05, O1 = 1000, O2 = 100ACBFONre = 5,Ned = 2, Nc = 10, Ns = 4, alpha = 0.2,Ped = 0.25,dattract = hrepellant = 0.1, wattract = wrepellant = 0.2ISEDBFONre = 5, Ned = 2,Nc = 10, Ns = 4, alpha = 0.2,Ped = 0.25,dattract = hrepellant = 0.1, wattract = 5, wrepellant = 10SMAz = 0.3, r ∈ [0, 1], b = [0, 1]MOBIFSNre = 4, Ned = 2,Nc = 200, Ns = 4, alpha = 0.2, Ped = 0.25BMRFOTx=x/1+x2, S = 2, r, r1, r2, r3 ∈ [0, 1]IBFAγ=1, β0=1, α=0.5−0.5t/MaxItThe following is a description of reproduction and dispersal elimination processes: we assume that the bacterial dimension isD. In dispersal elimination, seldomly selected features are identified first by ranking features according to their Uweight. The new searching position for bacteria is then determined by randomly selecting D features from the top half of the seldomly selected features. In reproduction, features are initially ranked by their Pweight to identify the highest-performing features of the search history. Then, the half population of bacteria with poor performance will be gradually replaced by the dimensions of the highest-performing features. The overall pseudocode of SBHFS is given in Pseudocode 6, and here, we analyze the computation time of feature selection (lines 3 to 13) of SBHFS. We suppose that there are S bacteria in the population, the max iteration time is I, the original number of features is D, and the swimming time is M and M≪I.First, we analyze the initialization part. The feature ranking by SU and feature weighting are the main time consumption step. The time complexity of calculating SU scores and weight for features are bothO(D), which are related to the number of features. Thus, the time complexity of the initialization part is OD+OD≅OD. We further analyze the time computation of the main loop of Pseudocode 6 from lines 4 to 13. At iteration I, if the dynamic learning step in line 6 is conducted, the time complexity of this step is OSNI according to Pseudocode 4, where NI is the selected features at iteration I and NI≤D. In the elite population evolution part in line 11 of Pseudocode 6, if the evolution choice is dispersal elimination, the time complexity is OSM. If the evolution choice is reproduction, the time complexity is OSM+Os≅OSM, where s is the population to be updated and s≤S (usually, s is half of the population). Therefore, in the worst case for one iteration I, the complexity of SBHFS is OD+OSNI+OSM≅OSNI. Since NI denotes the number of selected features at iteration I and NI is smaller than or equal to D, the time complexity of SBHFS at iteration I is smaller than or equal to OSD. Thus, we can reach the conclusion that the time complexity of the main loop of SBHFS during I iterations is not larger than OISD.Pseudocode 6: SBHFS.
(1)
Input: missing labels and high-dimensional data and number of selected features: D(2)
Semisupervised learning: labeling by Pseudocodes 2 and 3(3)
Initialization: parameter setting follows Section 4.3; population initialization follows Section 3.2; iteration: I = 0; swimming: s = 0;(4)
WhileI < max iterations(5)
I = I + 1;(6)
Dynamic learning byPseudocode 4(7)
Obtain fitness and feature subset(8)
Ifs < Ns//Ns is the number of swimming times(9)
s = s + 1;(10)
Elite population evolution byPseudocode 5(11)
Obtain fitness and the feature subset(12)
End(13)
End(14)
Output: fitness and the feature subset


## 3.1. Self-Adjusted, Semisupervised KNN

The proposed self-adjusted, semisupervised KNN is a two-step self-training method, consisting ofK value determination and label construction. Furthermore, to make the semisupervised learning method more adaptive to datasets of different sizes, the K value is adjusted as follows:(5)K=1:1:NS,NS<10,1:lgNS:10∗lgNS,10≤NS,where NS is the number of data samples, which means that the K value linearly increases when datasets have smaller samples, while the logarithmic function is employed for datasets with larger sample sizes. The primary process of the self-adjusted, semisupervised KNN is illustrated as follows:Step 1. K Value DeterminationThe samples with the labeled class and unlabeled class are separately saved in the datasetL and dataset U. As mentioned previously, a self-adjusted, semisupervised KNN is presented for labeling the data with no assignment in categories and finding the best K value for classification. This step is to determine a K value for the label reconstruction using the labeled samples in L, provided in Pseudocode 2.Step 2. Label ReconstructionLabel reconstruction is provided inPseudocode 3. First, self-adjusted, semisupervised KNN is used to predict the labels for the samples from the dataset U. Then, newly labeled samples are moved from the dataset U to the dataset L. With increasing L in the space size, the self-training step can increase the learning efficiency of the training model.Pseudocode 2: Determination of the K value.
(1)
Input: L (L is used to save the labeled samples in the original dataset)(2)
For each K obtained by Equation (5)(3)
For each running time(4)
Randomly divideL into two subsets/∗ half with saved labels and half with removed labels ∗/(5)
Use the labeled subset to predict the labels of the unlabeled subset by KNN(6)
Record the accuracy of label prediction on each running time(7)
End(8)
Record theK value and the average accuracy of label prediction of each K(9)
End(10)
Output: Best (K value with the maximum average accuracy)Pseudocode 3: Label reconstruction.
(1)
Input: labeled dataset L and unlabeled dataset U, best(2)
For each unlabeled sample in the dataset U(3)
Use the samples from the datasetL to predict the label by KNN (using Kbest)(4)
Assign the predicted label to the unlabeled sample and move it fromU to L(5)
End(6)
Output: the updated dataset L


## 3.2. Hierarchical Population Initialization

In BCO, the population is initialized randomly in a feasible space. However, addressing feature selection with high-dimensional features might make the bacterial colony fall into a poor searching position due to the high uncertainty of population initialization. As a result, more effort will be taken to jump out from their original position, which brings redundant computational complexity. To solve this problem, we develop a hierarchical population initialization strategy to enable bacteria to start at relatively good positions and further accelerate the convergence speed of the population. In contrast to the aforementioned variable-size cooperative coevolutionary technique, hierarchical population initialization does not use multipopulation for searching. Instead, it uses the idea of the proposed feature hierarchical division strategy to reconstruct a smaller search space before each search. The hierarchical population initialization consists of three steps. The details are as follows:Step 1. Feature Ranking and FilteringInitially, a symmetrical uncertainty (SU) [21] ranking is performed on the original features according to Equations (6)–(9). In this step, the correlations between features and classes are ranked, and the features’ relevant significance is ordered from highest to lowest. After ranking, the worst 10 percent of features with significance below the mean are eliminated.(i)
Symmetrical uncertainty (SU): the SU index has been widely used in traditional FS methods based on information theory. SU measures the uncertainty between feature variablesf∈F, with label signals l∈L given in Equations (6)–(9) based on the Shannon information entropy. In those formulas, pf is the prior probability for all values of f and pf|l is the posterior probability of f given l:(6)SUf,l=2Hf−Hf|lHf+Hl,(7)Hl=−∑i=1Nplilog2pli,(8)Hl=−∑l=1Nplilog2pli,(9)Hf|l=−∑j=1Nplj∑i=1Npfi|ljlog2pfi|lj,whereHf and Hl are the entropy of the feature variable f and the label signal l, respectively. N is the number of observation samples x∈X. SUf,l evaluates the correlation between features f and label signals l. A larger SUf,l indicates a higher significance of the feature f to the label l. This means that the feature f has more robust ability to discriminate labels, and the feature f needs to be selected into the feature subset.Step 2. Feature Hierarchical DivisionAs shown in Figure2, it is assumed that the numbers of SU are significant in the box. According to their significance, sorted features will be divided evenly into three layers, L1, L2, and L3. After that, 80% of the feature dimension will be randomly selected from the L1 set, 15% from the L2 set, and 5% from the L3 set to form a searching position for bacteria. This strategy can exclude subpar features and shrink the search space when dealing with high-dimensional features.Step 3. Feature Weight UpdatingWe assume that the feature size isH, and each feature of the ith bacterium is denoted as fi. We define the current fitness as fit(fi) and the historical fitness as Fit(fi). In this paper, we adopt a weight mechanism [6] to evaluate the performance of features. The rules are as follows: if fit(fi) < Fit(fi), then the performance weight pfi will be increased by (12). Otherwise, pfi will be decreased by Equation (13).Figure 2
Feature hierarchical division.Given that, after completing the aforementioned procedure, there are still unselected features in each feature layer. To increase these features’ probability of being selected in the future, we defined the unselected weight (Uweight) of fi as ufi and Uweight=uf1,uf2,...,ufH. Then, the weight of each unselected feature will be updated by Equation (10) after Step 2. In each feature selection process, if one feature has been selected repeatedly in each search, then its ufi will be decreased by Equation (11):(10)ufi=ufi+0.01ufi,ufi∈L1,ufi+0.001ufi,ufi∈L2,ufi+0.0001ufi,ufi∈L3,(11)ufi=ufi−maxufi−minufi,(12)pfi=pfi+Fitfi−fitfiFitfi,(13)pfi=pfi−Fitfi∗Fitfi−fitfi,where fi is each feature of the ith bacterium, ufi is the unselected weight, pfi is the performance weight, L1,L2,L3 are layers obtained in Step 2, fit(fi) is the current fitness of fi, and Fit(fi) is the historical fitness.


## 3.3. Dynamic Learning

In BCO, the chemotaxis step length of bacteria is governed by a set of fixed values denoted byCi. However, the lack of variation in step lengths may trap bacteria within the same search space. On a long-term basis, the diversity of feature subsets will decline. Therefore, in SHBFS, the running process is the same as that in BCO, while the tumbling process is improved by employing a dynamic learning strategy to increase the search variety.Specifically, a dynamic learning strategy is proposed by adopting an adaptive chemotaxis step length changing strategy, which is denoted asaC [46], and a step length communication strategy dC. Equations (14) and (15) show that aC is affected by the bacterial size S, where S = 1,2,…,i,i∈N+. We define the current fitness as fit, the upper bound of the step length as Cub, and the lower bound of the step length as Clb. ∂ is the disturbance factor. As the iteration proceeds, the disturbance effect of ∂ on aC will become small. In addition, the larger the fit, the larger the value of aC. The step length can be changed dynamically by aC:(14)∂=1−is×Cub−Clb+Clb,(15)aC=fitfit+∂.There is no information communication among the bacteria in BCO. To enhance the convergence speed and improve the search capability, this paper presents a step length communication strategy. LetdC be the step length after communication, and its size is S × D, where D = 1,2,…,d,d∈N+ is the dimension of bacteria. Equation (16) shows the communication process of ith bacteria in the tth iteration:(16)dCt=0.01×aC+cpi⋅Rpi⋅pbesti−θit+cgi⋅Rgi⋅gbesti−θit,where θit is the current position of the bacterium, cp and cg are constant learning factors, and Rp and Rg are random disturbance terms. Rp and Rg are confined to [0, 1]. The step length size in SBHFS learns from the best population record of individual bacteria (pbest) and the best population record of the bacteria (gbest). For this, bacteria will prefer to learn from the record with a larger position excursion. After updating the step length dC, bacterial population tumbling is conducted as follows:(17)θit=θit−1+dCt−1⋅ΔiΔiT⋅Δi⋅Oq,where ∆i is a random direction vector generated between [−1, 1] for the ith bacterium. Due to varying data sizes, the range of bacterial location change is greater in large samples than in small samples. Therefore, Oq = O1,O2,q=1,2. has been proposed in this paper to adjust the offset of the bacterial position. In the tumbling process, q = 1; in the swimming process, q = 2. The setting of O1 and O2 is explained in Section 4.3. We define the number of features of the whole dataset as H, and the selected feature subset size is D. If H < D, O1 = O2 = 1.After tumbling, the feature subset is formed by Equation (18), where · represents the rounding operator. The performance of the feature subset is measured by a classifier. Thus, we adopt the confusion matrix [47] as an evaluation metric, and the fitness is the error rate, which is updated by Equation (19).(18)θi1t,…,θidt,(19)fit=FP+FNTP+TN+FP+FN,where FP is the false-positive result, FN is the false-negative result, TP is the true-positive result, and TN is the true-negative result. fit is the current fitness. Fit is defined as the historical fitness. The current best fitness is fpbest, and the historical best fitness is fgbest. The main process of dynamic learning is shown in Pseudocode 4.Pseudocode 4: Dynamic learning.
(1)
Input: fit, Pweight, Uweight, fpbest, and fgbest(2)
For each bacterium(3)
Running process by equation (1)//running(4)
Update the guiding factoraC by Equations (14) and (15)(5)
Update the step lengthdC by Equation (16)(6)
Update the position by Equation (17)//tumbling(7)
Get the feature subset by Equation (18)(8)
Update fit by Equation (19) and update Uweight by Equation (11)(9)
If fit < fpbest(10)
fpbest = fit(11)
UpdatePweight by Equation (12)(12)
Else(13)
UpdatePweight by Equation (13)(14)
End(15)
Iffpbest < fgbest(16)
fgbest = fpbest(17)
End(18)
Swimming byPseudocode 5.(19)
End(20)
Output: fit and the feature subsetPseudocode 5: Elite population evolution mechanism.
(1)
Input: fit, Fit, Pweight, Uweight, fpbest, and fgbest(2)
For each bacterium(3)
While doing the swimming loop(4)
If fit < Fit(5)
Fit= fi(6)
IfbT > control threshold//it means bad effect searching(7)
Do dispersal elimination(8)
RankF by Uweight and save as SF//SF is the sorted feature(9)
Ɵ = randomly selecting D features from the top half of SF(10)
Else//D is the bacterial dimension(11)
Do reproduction(12)
Forr = 1: Sr//Sr is the reproduction size of bacteria(13)
Sort the positionƟ of bacteria(14)
Sort featuresF by Pweight and save as SF(15)
Ɵr+Sr = SF(Sr)(16)
End(17)
End(18)
End(19)
Get the feature subset by Equation (18)(20)
Update fit by Equation (19) and update Uweight by Equation (11)(21)
If fit < fpbest(22)
fpbest = fit(23)
UpdatePweight by Equation (12)(24)
Iffpbest < fgbest(25)
fgbest = fpbest(26)
End(27)
Else(28)
UpdatePweight by Equation (13)(29)
End(30)
End(31)
End(32)
Output: fit and the feature subset


## 3.4. Elite Population Evolution

In most bacterial-based methods, the population will randomly undergo dispersal elimination. This means that the new searching position of bacteria could be good or bad. The bad searching position may waste the search time. To make population evolution more meaningful, this paper designed an elite population evolution mechanism usingPweight and Uweight values aforementioned in Section 3.2, which are to guide bacteria to conduct reproduction and dispersal elimination.In SBHFS, either reproduction or dispersal elimination will be conducted per iteration. The elite population evolution mechanism is proposed to determine which operation is executed, as depicted in Figure3. After dynamic learning, bacteria will perform a swimming loop as BFO until they meet the threshold Ns (see Table 1). In the swimming loop, each bacterium will first undergo a fitness evaluation to determine its performance. errTre is defined as the performance threshold. If the fitness exceeds errTre, it will be counted in bT. When bT is larger than half of Ns, we can simply regard this bacterium by performing a bad search, and dispersal elimination is conducted based on the Uweight matrix. Otherwise, bacteria will reproduce based on the Pweight matrix. Next, we calculate the fitness of the new bacteria and updated two weights (Pweight and Uweight). Finally, we repeat preceding steps until the end of the loop. The main process of the elite population evolution mechanism is given in Pseudocode 5.Figure 3
The elite population evolution mechanism.Table 1
The settings of parameters for benchmark methods.
AlgorithmsParameter settingsSBHFSerrTre = 0.6, cp = 0.0015, cg = 0.0015, Ns = 4Cub = 0.15, Clb = 0.05, O1 = 1000, O2 = 100ACBFONre = 5,Ned = 2, Nc = 10, Ns = 4, alpha = 0.2,Ped = 0.25,dattract = hrepellant = 0.1, wattract = wrepellant = 0.2ISEDBFONre = 5, Ned = 2,Nc = 10, Ns = 4, alpha = 0.2,Ped = 0.25,dattract = hrepellant = 0.1, wattract = 5, wrepellant = 10SMAz = 0.3, r ∈ [0, 1], b = [0, 1]MOBIFSNre = 4, Ned = 2,Nc = 200, Ns = 4, alpha = 0.2, Ped = 0.25BMRFOTx=x/1+x2, S = 2, r, r1, r2, r3 ∈ [0, 1]IBFAγ=1, β0=1, α=0.5−0.5t/MaxItThe following is a description of reproduction and dispersal elimination processes: we assume that the bacterial dimension isD. In dispersal elimination, seldomly selected features are identified first by ranking features according to their Uweight. The new searching position for bacteria is then determined by randomly selecting D features from the top half of the seldomly selected features. In reproduction, features are initially ranked by their Pweight to identify the highest-performing features of the search history. Then, the half population of bacteria with poor performance will be gradually replaced by the dimensions of the highest-performing features. The overall pseudocode of SBHFS is given in Pseudocode 6, and here, we analyze the computation time of feature selection (lines 3 to 13) of SBHFS. We suppose that there are S bacteria in the population, the max iteration time is I, the original number of features is D, and the swimming time is M and M≪I.First, we analyze the initialization part. The feature ranking by SU and feature weighting are the main time consumption step. The time complexity of calculating SU scores and weight for features are bothO(D), which are related to the number of features. Thus, the time complexity of the initialization part is OD+OD≅OD. We further analyze the time computation of the main loop of Pseudocode 6 from lines 4 to 13. At iteration I, if the dynamic learning step in line 6 is conducted, the time complexity of this step is OSNI according to Pseudocode 4, where NI is the selected features at iteration I and NI≤D. In the elite population evolution part in line 11 of Pseudocode 6, if the evolution choice is dispersal elimination, the time complexity is OSM. If the evolution choice is reproduction, the time complexity is OSM+Os≅OSM, where s is the population to be updated and s≤S (usually, s is half of the population). Therefore, in the worst case for one iteration I, the complexity of SBHFS is OD+OSNI+OSM≅OSNI. Since NI denotes the number of selected features at iteration I and NI is smaller than or equal to D, the time complexity of SBHFS at iteration I is smaller than or equal to OSD. Thus, we can reach the conclusion that the time complexity of the main loop of SBHFS during I iterations is not larger than OISD.Pseudocode 6: SBHFS.
(1)
Input: missing labels and high-dimensional data and number of selected features: D(2)
Semisupervised learning: labeling by Pseudocodes 2 and 3(3)
Initialization: parameter setting follows Section 4.3; population initialization follows Section 3.2; iteration: I = 0; swimming: s = 0;(4)
WhileI < max iterations(5)
I = I + 1;(6)
Dynamic learning byPseudocode 4(7)
Obtain fitness and feature subset(8)
Ifs < Ns//Ns is the number of swimming times(9)
s = s + 1;(10)
Elite population evolution byPseudocode 5(11)
Obtain fitness and the feature subset(12)
End(13)
End(14)
Output: fitness and the feature subset


## 4. Experimental Configuration

In this section, detailed information on the datasets, benchmark methods, and experimental design is given.


### 4.1. Datasets

In this paper, we verified the proposed method on different datasets, consisting of five high-dimensional microarray datasets and three benchmark datasets [6]. The description of the selected datasets is given in Table 2. #Features define the number of original features, #instance denotes the number of samples, and the number of classes is given in #Class. #Smallest class is the size of the class with the fewest instances, whereas #Largest class is the size of the class with the most instances. Among these datasets, Colon, SRBCT, DLBCL, Leukemia-AllAML (LA), and Central Nervous System (CNS) are datasets with the highest number of features up to 7129. All feature values in those five datasets are normalized within [0, 1]. Besides, the number of instances relative to the number of features in the last five datasets is considerably lower. Furthermore, all datasets are significantly imbalanced. These traits present FS and classification with formidable challenges. Since the proposed method is intended to handle missing label data, the original data will be transformed into partially labeled data, as described in Section 4.3.Table 2
Datasets for feature selection.
Datasets#Features#Instances#Class#Smallest class#Largest classAustralian156902222468German2410002300700Ionosphere33351238313Colon19996222240SRBCT23088341335DLBCL54697722575Leukemia-ALLAML (LA)71297242349Central Nervous System (CNS)71296022139


### 4.2. Comparison Methods

The proposed SBHFS method is measured and compared with six recently widely recognized bioinspired wrapper FS algorithms, denoted as benchmark methods. The parameters of the comparison algorithms are shown in Table1.The adaptive chemotaxis bacterial foraging optimization algorithm (ACBFO) [42], improved swarming and elimination-dispersal bacterial foraging optimization algorithm (ISEDBFO) [42], and multiobjective bacterial-inspired algorithm (MOBIFS) [48] are three recently proposed BFO variants for FS, which have good performances. ACBFO proposed an adaptive chemotaxis strategy, and ISEDBFO adopts a hyperbolic tangent function and a roulette technique to improve the search effects of BFO in FS. MOBIFS is an effective multiobjective BFO algorithm that handles FS issues using four information exchange mechanisms. The slime mold algorithm (SMA) [49], binary manta ray foraging optimization (BMRFO) [50], and improved binary butterfly algorithm (IBFA) [51] are three other bioinspired algorithms that have good performance in FS. SMA imitates slime mold’s foraging behavior and introduces the composite mutation strategy and restart strategy. BMRFO is a manta ray heuristic algorithm for FS problem solving that uses a rational transfer function. IBFA uses a new dynamic mutation operator to increase the diversity of the searching population.Except for the abovementioned six bioinspired benchmark algorithms, to better verify the effectiveness of SBHFS, we designed two more groups of comparison experiments: comparisons with standard BFO and BCO and comparisons with semisupervised methods:(i)
Comparison with Standard BFO and BCO. Based on the basic bacterial evolutionary framework, the SBHFS method has been developed with some efficient strategies. This comparison intends to evaluate the enhanced performance of the proposed approach compared with the standard bacterial heuristic algorithm.(ii)
Comparisons with Semisupervised Methods. The proposed self-adjustment, semisupervised learning method is being evaluated in this experimental group. First, original datasets are randomly divided into training and test sets. Moreover, the training set is further divided into a labeled subset and an unlabeled subset. Finally, two KNN-based semisupervised labeling techniques, semisupervised KNN (SSKNN) [38] and the best K semisupervised KNN (BKSKNN) [41], are selected to be executed on eight incompletely labeled datasets with SBHFS.


### 4.3. Design

In this study, all experiments were performed on a PC with Windows 10, Intel Core i7-7700, at 3.6 GHz, 8 GB RAM, and the Windows 10 operating system. Moreover, for all algorithms, the population size was set to 30, and the number of maximum iterations (maxiter) was set to 100. All experiments were run independently 30 times. Due to the facility to implement KNN, this paper used KNN as the learning algorithm to assess the classification performance after FS as in literature [38, 41]. In each dataset, 70% of the samples from each class were randomly selected as the training set and the remaining 30% as the testing set. To simulate partially labeled data, this paper divided the training set into half-labeled samples and half-unlabeled samples (see Section 3.1). According to the previous experiments [6], only a small subset of tenths of the features provides the ideal solution. When the number of features for the last five datasets in Table 1 is less than 50, it is possible to attain high classification accuracy. The desired number of features (Fno.) therefore varies between 1 and 10 for the first three datasets (with reduced feature subset size) and between 5 and 50 for the remaining datasets. The parameters of all benchmark methods are given in Table 2.For evaluation metrics (Equations.(20)–(25)), the classification error rate (denoted as Err.), true-positive rate (TPR), true-negative rate (TNR), precision (Pre), G-means (GM), and F1 score (F1) are used to assess feature selection results [52]. The effectiveness of feature selection approaches can be fully reflected by these evaluation metrics. The performance of the classification result for imbalanced data is assessed using the error rate and G-means. The TNR measures a method’s capacity to isolate true-positive samples (minority samples) from all other samples, whereas the TPR measures a method’s ability to isolate negative samples (majority samples) from all other samples. Precision gauges a method’s capacity to distinguish genuine positive samples from all other positive samples (including true positives and false positives). A thorough evaluation of TPR and precision performance is provided by the F1 score.(20)Err=FP+FNTP+TN+FP+FN,(21)TPR=TPTP+FN,(22)TNR=TNTN+FP,(23)Pre=TPTP+FP,(24)GM=TPR+TNR,(25)F1=2∗Pre∗TPRPre+TPR.Additionally, the Wilcoxon rank-sum test [53] was performed on each approach. It is marked as “=” when the p value is greater than 0.05, meaning there is no significant difference under the significance level of 5%. If the p value is less than 0.05, the recommended method is considered more significant than the comparison algorithms and marked as “+.” Otherwise, it is marked as “−.”


## 4.1. Datasets

In this paper, we verified the proposed method on different datasets, consisting of five high-dimensional microarray datasets and three benchmark datasets [6]. The description of the selected datasets is given in Table 2. #Features define the number of original features, #instance denotes the number of samples, and the number of classes is given in #Class. #Smallest class is the size of the class with the fewest instances, whereas #Largest class is the size of the class with the most instances. Among these datasets, Colon, SRBCT, DLBCL, Leukemia-AllAML (LA), and Central Nervous System (CNS) are datasets with the highest number of features up to 7129. All feature values in those five datasets are normalized within [0, 1]. Besides, the number of instances relative to the number of features in the last five datasets is considerably lower. Furthermore, all datasets are significantly imbalanced. These traits present FS and classification with formidable challenges. Since the proposed method is intended to handle missing label data, the original data will be transformed into partially labeled data, as described in Section 4.3.Table 2
Datasets for feature selection.
Datasets#Features#Instances#Class#Smallest class#Largest classAustralian156902222468German2410002300700Ionosphere33351238313Colon19996222240SRBCT23088341335DLBCL54697722575Leukemia-ALLAML (LA)71297242349Central Nervous System (CNS)71296022139


## 4.2. Comparison Methods

The proposed SBHFS method is measured and compared with six recently widely recognized bioinspired wrapper FS algorithms, denoted as benchmark methods. The parameters of the comparison algorithms are shown in Table1.The adaptive chemotaxis bacterial foraging optimization algorithm (ACBFO) [42], improved swarming and elimination-dispersal bacterial foraging optimization algorithm (ISEDBFO) [42], and multiobjective bacterial-inspired algorithm (MOBIFS) [48] are three recently proposed BFO variants for FS, which have good performances. ACBFO proposed an adaptive chemotaxis strategy, and ISEDBFO adopts a hyperbolic tangent function and a roulette technique to improve the search effects of BFO in FS. MOBIFS is an effective multiobjective BFO algorithm that handles FS issues using four information exchange mechanisms. The slime mold algorithm (SMA) [49], binary manta ray foraging optimization (BMRFO) [50], and improved binary butterfly algorithm (IBFA) [51] are three other bioinspired algorithms that have good performance in FS. SMA imitates slime mold’s foraging behavior and introduces the composite mutation strategy and restart strategy. BMRFO is a manta ray heuristic algorithm for FS problem solving that uses a rational transfer function. IBFA uses a new dynamic mutation operator to increase the diversity of the searching population.Except for the abovementioned six bioinspired benchmark algorithms, to better verify the effectiveness of SBHFS, we designed two more groups of comparison experiments: comparisons with standard BFO and BCO and comparisons with semisupervised methods:(i)
Comparison with Standard BFO and BCO. Based on the basic bacterial evolutionary framework, the SBHFS method has been developed with some efficient strategies. This comparison intends to evaluate the enhanced performance of the proposed approach compared with the standard bacterial heuristic algorithm.(ii)
Comparisons with Semisupervised Methods. The proposed self-adjustment, semisupervised learning method is being evaluated in this experimental group. First, original datasets are randomly divided into training and test sets. Moreover, the training set is further divided into a labeled subset and an unlabeled subset. Finally, two KNN-based semisupervised labeling techniques, semisupervised KNN (SSKNN) [38] and the best K semisupervised KNN (BKSKNN) [41], are selected to be executed on eight incompletely labeled datasets with SBHFS.


## 4.3. Design

In this study, all experiments were performed on a PC with Windows 10, Intel Core i7-7700, at 3.6 GHz, 8 GB RAM, and the Windows 10 operating system. Moreover, for all algorithms, the population size was set to 30, and the number of maximum iterations (maxiter) was set to 100. All experiments were run independently 30 times. Due to the facility to implement KNN, this paper used KNN as the learning algorithm to assess the classification performance after FS as in literature [38, 41]. In each dataset, 70% of the samples from each class were randomly selected as the training set and the remaining 30% as the testing set. To simulate partially labeled data, this paper divided the training set into half-labeled samples and half-unlabeled samples (see Section 3.1). According to the previous experiments [6], only a small subset of tenths of the features provides the ideal solution. When the number of features for the last five datasets in Table 1 is less than 50, it is possible to attain high classification accuracy. The desired number of features (Fno.) therefore varies between 1 and 10 for the first three datasets (with reduced feature subset size) and between 5 and 50 for the remaining datasets. The parameters of all benchmark methods are given in Table 2.For evaluation metrics (Equations.(20)–(25)), the classification error rate (denoted as Err.), true-positive rate (TPR), true-negative rate (TNR), precision (Pre), G-means (GM), and F1 score (F1) are used to assess feature selection results [52]. The effectiveness of feature selection approaches can be fully reflected by these evaluation metrics. The performance of the classification result for imbalanced data is assessed using the error rate and G-means. The TNR measures a method’s capacity to isolate true-positive samples (minority samples) from all other samples, whereas the TPR measures a method’s ability to isolate negative samples (majority samples) from all other samples. Precision gauges a method’s capacity to distinguish genuine positive samples from all other positive samples (including true positives and false positives). A thorough evaluation of TPR and precision performance is provided by the F1 score.(20)Err=FP+FNTP+TN+FP+FN,(21)TPR=TPTP+FN,(22)TNR=TNTN+FP,(23)Pre=TPTP+FP,(24)GM=TPR+TNR,(25)F1=2∗Pre∗TPRPre+TPR.Additionally, the Wilcoxon rank-sum test [53] was performed on each approach. It is marked as “=” when the p value is greater than 0.05, meaning there is no significant difference under the significance level of 5%. If the p value is less than 0.05, the recommended method is considered more significant than the comparison algorithms and marked as “+.” Otherwise, it is marked as “−.”


## 5. Experimental Results and Analyses

This section gives the comparison results and analyses of the three experimental groups. First, the improvement of the proposed bacterial heuristic optimization algorithm is proved by making comparisons with standard BFO and BCO for feature selection. Next, the enhanced semisupervised method is verified and discussed with two KNN-based semisupervised methods. Finally, the effectiveness of the overall proposed SBHFS method for tracking incomplete data classification is demonstrated. In Tables3–6, the value in bold represents the best value for the current indicator. When the p value is “=,” there is no significant difference between algorithms. Therefore, the evaluation index score corresponding to the p value will not be bold.Table 3
The results of the comparisons with standard BFO and BCO.
MethodsDatasetColonSRBCTErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1BHFSAve.0.03827.3800.9170.9880.9560.9510.9710.06927.4400.9770.9320.9360.9510.926Std.0.01115.0950.0280.0110.0150.0150.0090.04415.0400.0150.0460.0380.0340.048BFOFSAve.0.32127.5000.4770.8000.7310.6060.7610.47228.8890.8420.5430.5480.6570.520Std.0.07615.1380.1900.0700.0820.1160.0540.12815.3660.0420.1240.1470.0950.125P+=++++++=+++++BCOFSAve.0.11627.5000.7570.9580.8770.8480.9130.15027.5000.9500.8540.8550.8960.841Std.0.02215.1380.1180.0590.0550.0440.0160.05615.1380.0170.0720.0780.0490.074P+=+=++++=+++++MethodsDatasetIonosphereGermanErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1BHFSAve.0.05512.9090.9760.6840.8160.8110.7220.26910.3830.3170.9190.7530.5260.827Std.0.0156.9270.0280.1430.1100.0720.0550.0155.4680.0920.0480.0230.0760.011BFOFSAve.0.13615.1000.9360.3070.3590.4940.3000.34311.9830.3170.8270.7260.4890.770Std.0.03110.0050.0360.2630.1540.2040.1800.0287.2290.1080.0950.0230.0900.032P+=++++++=++==+BCOFSAve.0.07616.0000.9670.5540.6890.7250.5970.29112.0000.2910.8980.7440.4850.811Std.0.0119.9500.0260.1650.0880.0880.0640.0107.2110.1470.0760.0270.1230.016P+=++++++=====+MethodsDatasetCNSLAErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1BHFSAve.0.09327.4200.8370.9420.9250.8840.9310.00027.4401.0001.0001.0001.0001.000Std.0.01315.0660.0460.0230.0190.0200.0100.00015.0690.0000.0000.0000.0000.000BFOFSAve.0.42827.5000.3500.7230.6900.4820.7030.13627.5000.8860.8530.9450.8670.895Std.0.12015.1380.1660.1100.0680.1250.0790.06415.1380.1310.0690.0620.0760.050P+=++++++=+++++BCOFSAve.0.21127.5000.6330.8670.8300.7340.8440.04627.5000.9140.9730.9620.9420.967Std.0.05115.1380.1310.0980.0470.0590.0430.03715.1380.1000.0340.0430.0530.027P+=++++++=+++++MethodsDatasetAustralianDLBCLErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1BHFSAve.0.3595.6140.7410.4340.4500.5630.4380.00227.4000.9990.9981.0000.9990.999Std.0.0422.2970.0760.0690.0470.0340.0400.00515.0690.0000.0070.0000.0040.004BFOFSAve.0.4897.4710.5560.4570.3260.4850.3740.22527.5000.5870.8440.8550.6920.848Std.0.0494.1950.1180.1590.0320.0390.0650.10815.1380.2250.0830.0790.1660.073P+=++++++=+++++BCOFSAve.0.4077.5000.6890.3930.3800.5180.3840.05727.5000.8830.9650.9610.9210.962Std.0.0374.1830.0650.0520.0380.0290.0330.04115.1380.1120.0410.0370.0620.028P+=++++++=+++++Table 4
The average computation time (minutes) of BHFS, BFOFS, and BCOFS for each run.
DatasetsAlgorithmsBHFSBFOFSBCOFSAustralian4.56630.1045.477German4.66727.0465.371Ionosphere4.01923.0344.182Colon2.42022.3983.360SRBCT2.81825.9463.963DLBCL1.80329.4334.388Leukemia-ALLAML (LA)2.83334.7954.282Central Nervous System (CNS)3.54030.1536.104The bold values indicate that the SBHFS takes the least amount of time in each independent run.Table 5
The results of the comparisons with semisupervised methods.
MethodsDatasetColonSRBCTErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1SBHFSAve.0.04127.3200.9060.9900.9490.9460.9680.06527.4000.9770.9380.9410.9560.936Std.0.00814.9160.0300.0160.0160.0110.0060.03115.1060.0110.0290.0290.0210.029BHFS-SSKNNAve.0.15327.5000.6290.9750.8220.7780.8900.25427.3000.9070.7550.8170.8190.763Std.0.04615.1380.1380.0400.0540.0820.0300.04614.8180.0180.0510.0440.0420.052P+=+=++++=+++++BHFS-BKSKNNAve.0.12127.5000.7000.9830.8520.8270.9120.26327.5000.9120.7690.7890.8250.745Std.0.02515.1380.1050.0350.0430.0510.0160.04015.1380.0120.0400.0680.0300.052P+=+=++++=+++++MethodsDatasetIonosphereGermanErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1SBHFSAve.0.05013.6550.9940.5820.9260.7560.7040.27310.5170.2940.9130.7530.5060.824Std.0.0137.7940.0050.1100.0490.0720.0900.0165.7350.1120.0280.0250.0900.005BHFS-SSKNNAve.0.15215.5000.8600.7450.3840.7980.5050.28211.2500.2360.9330.7370.4580.822Std.0.0167.6340.0200.1120.0350.0550.0480.0106.3980.0950.0490.0190.0760.011P+=+−+=+===−===BHFS-BKSKNNAve.0.06314.1820.9820.5540.7830.7340.6440.28911.5830.2190.9210.7340.4410.817Std.0.0128.2800.0080.1030.0820.0690.0820.0087.1280.0890.0360.0160.0760.007P+=+=+==+===+=+MethodsDatasetCNSLAErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1SBHFSAve.0.10427.3800.7400.9730.8850.8460.9250.01227.5000.9890.9880.9950.9880.991Std.0.00615.0330.0440.0240.0170.0150.0050.01115.1380.0200.0100.0090.0130.008BHFS-SSKNNAve.0.13327.5000.6170.9920.8390.7800.9090.11427.5000.6710.9870.8690.8090.923Std.0.02915.1380.0810.0260.0270.0520.0190.04415.1380.1510.0280.0580.0820.029P+=+−++++=+=+++BHFS-BKSKNNAve.0.13327.4000.6170.9920.8400.7790.9090.03227.5001.0000.9531.0000.9760.976Std.0.03914.9760.1120.0260.0400.0700.0250.02215.1380.0000.0320.0000.0160.017P+=+−++========MethodsDatasetAustralianDLBCLErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1SBHFSAve.0.3505.8710.7710.3980.4540.5530.4230.00327.4800.9970.9960.9990.9960.998Std.0.0162.6000.0170.0430.0290.0300.0360.00615.1050.0110.0080.0040.0060.004BHFS-SSKNNAve.0.4837.6000.4190.7240.3510.4890.4620.11727.5000.5501.0000.8630.7400.927Std.0.0582.7160.2050.2590.0810.1350.1540.02115.1380.0810.0000.0220.0530.012P+=+−+=++=+=+++BHFS-BKSKNNAve.0.3306.3080.7880.4210.4880.5750.4510.05227.5000.8001.0000.9360.8920.966Std.0.0202.5940.0210.0500.0390.0350.0420.03415.1380.1310.0000.0410.0730.022P−===++++=+=+++The bold values for each method mean that they achieve the best results under the evaluation index.Table 6
The result of the comparisons with benchmark methods.
MethodsIndexesColonSRBCTErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1SBHFSAve.0.04127.50.920.9820.9570.9490.9680.06427.50.9790.9370.940.9560.932Std.0.01515.1380.0380.0150.0210.020.0120.03615.1380.0120.0420.0330.0290.044ACBFOAve.0.176390.60.6650.910.840.7690.8710.159458.350.9450.8630.8770.8940.853Std.0.02815.3640.0550.0310.0260.0350.0220.0319.5940.0110.0280.0250.0250.028P++++++++++++++ISEDBFOAve.0.153232.450.6790.9380.8480.7910.8880.162246.40.9440.8590.8690.8910.842Std.0.02956.9740.0730.0290.030.0460.0210.04373.6850.0150.0430.040.0340.048P++++++++++++++SMAAve.0.1354.30.7730.9160.8870.8320.8960.1347.8330.9550.8720.8870.9070.863Std.0.0351.3020.0740.060.0310.0390.0310.0355.8340.0110.0340.0380.0250.038P+−++++++−+++++MOBIFSAve.0.2519.1660.4380.790.910.4780.8450.4818.9240.9140.4710.7310.5610.62Std.0.1082.1040.4890.0650.0690.4020.0670.1173.6210.0830.0730.3260.2180.079P+==+=+++==++++BMRFOAve.0.17934.750.6660.9050.8380.7650.8660.1292160.9550.8880.8970.9140.874Std.0.03235.840.0920.0330.0380.0550.0230.048146.980.0170.0440.0350.0350.049P+=+++++++-++++IBFAAve.0.221988.30.5710.8860.8010.6950.8370.191140.80.930.840.860.880.83Std.0.02220.630.040.0270.0180.0290.0190.0221.710.010.020.020.020.02P++++++++++++++MethodsIndexesIonosphereGermanErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1SBHFSAve.0.06214.4910.9630.7210.7500.8290.7160.24610.9670.4070.9170.7770.5950.839Std.0.038.1140.0420.0990.1280.0430.0620.0245.9540.1250.0390.0360.1140.008ACBFOAve.0.1044.850.9760.7540.9490.8550.8340.2884.50.3510.8670.7580.5420.807Std.0.0110.9880.0130.0380.0270.0190.0210.011.5390.0640.0270.0130.0490.009P+−==−−−+−+++++ISEDBFOAve.0.0853.050.970.8170.940.890.8730.2754.10.4090.860.7740.5880.814Std.0.0080.510.0090.0220.0170.0120.0140.010.5530.0590.0210.0140.0410.007P+−=−−−−+−=+=++SMAAve.0.0912.50.9610.8160.9250.8840.8640.3052.90.3320.8510.7490.5130.793Std.0.0130.6070.0150.0210.0250.0140.0190.040.8520.0830.0390.0280.0820.032P+−+−−−−+−+++++MOBIFSAve.0.67711.7320.8810.1180.7380.3210.2030.299.2520.4970.7370.9240.6010.82Std.0.0592.9390.0520.0160.0640.0310.0260.0273.4340.1250.0090.0380.080.02P+=++=+++==+−=+BMRFOAve.0.093.10.9650.8110.9360.8830.8650.2794.60.3420.8840.760.5370.816Std.0.0090.9680.0120.0230.020.0120.0140.0151.8750.1010.0380.0210.0870.011P+−=−−−−+−+++++IBFAAve.0.1169.70.9780.7160.9510.8350.8140.2589.250.4410.8710.7850.6170.825Std.0.0091.8090.0090.020.0190.0130.0160.0161.7430.0420.0110.0130.0310.01P+===−=−+==+==+MethodsIndexesCNSLAErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1SBHFSAve.0.08227.50.820.9670.9180.8870.940.00227.4810.99710.9990.999Std.0.01815.1380.0420.0220.0180.0230.0140.00415.12700.00600.0030.003ACBFOAve.0.381411.20.4440.7160.7110.530.7020.1191394.70.9420.8530.9700.8940.905Std.0.02837.0470.0850.040.0350.0610.0250.01135.5340.0290.0110.0120.0160.009P++++++++++++++ISEDBFOAve.0.38731.80.4870.6950.7240.4950.6890.121647.30.9360.8580.9690.8920.905Std.0.031108.870.0710.0590.0210.0590.0380.01930.780.0460.0060.0210.0270.013P++++++++++++++SMAAve.0.031108.870.0710.0590.0210.0590.0380.0363.60.9690.9630.9860.9640.973Std.0.0671.3530.1120.070.0520.0930.0560.0282.6830.0470.0340.0210.0310.021P−+++++++−+++++MOBIFSAve.0.33319.2620.7220.6830.9010.6820.7750.17420.7340.9020.8150.9810.8540.889Std.0.1442.3050.3570.1010.0890.2850.0950.0944.5150.180.0820.0290.1230.057P+======+=+++++BMRFOAve.0.38358.30.4580.7010.7170.5180.6990.08116.350.9250.9160.9670.9170.938Std.0.059470.910.1030.0610.0560.0960.0510.02917.2360.0630.0330.0270.0380.022P++++++++++++++IBFAAve.0.4043517.70.4130.6940.6890.5180.690.1143492.30.9480.860.9720.9010.91Std.0.02536.1310.0490.0290.0210.0420.0210.01223.0860.0190.0130.0090.0130.009P++++++++++++++MethodsIndexesAustralianDLBCLErr.Fno.TNRTPRPre.GMF1Err.Fno.TNRTPRPre.GMF1SBHFSAve.0.3575.8570.70.5240.4560.6050.487027.4611111Std.0.0242.4740.030.0340.0320.0250.03015.12400000ACBFOAve.0.14510.9250.7990.9310.8590.8590.1081084.60.7980.9240.9340.8520.927Std.00000000.01830.6590.0630.0220.0170.0330.012P−−−−−−−+++++++ISEDBFOAve.0.14510.9250.7990.9310.8590.8590.057623.60.8870.9620.9640.920.962Std.00000000.015127.1090.0480.0170.0150.0250.01P−−−−−−−+++++++SMAAve.0.14510.9250.7990.930.8590.8590.09712.550.810.9360.9390.8640.935Std.00000000.03617.1110.0960.0280.0290.060.024P−−−−−−−+−+++++MOBIFSAve.0.4482.5560.7340.3930.6250.5370.4810.2219.6330.9370.7840.9660.8740.865Std.0.0241.2620.0020.0150.0290.010.0050.0972.3870.0810.0710.0410.0680.058P−=−−−−=+=+++++BMRFOAve.0.1441.50.9120.8110.9220.8590.8610.10476.050.750.9420.9270.8170.931Std.0.0021.2350.0310.0280.0210.0010.0060.03981.1270.1120.0420.0310.0890.028P−−−−−−−+++++++IBFAAve.0.1542.20.870.8260.8930.8450.8550.092684.90.810.940.940.870.94Std.0.0141.1520.0620.0270.040.020.0080.0222.440.040.010.010.020.01P−==−==−+++++++The values that are in bold show that each method got the best results based on the evaluation metrics.


### 5.1. Comparisons with Standard BFO and BCO

This comparison aims to verify the effectiveness of the proposed three strategies in BHFS, including hierarchical population initialization, dynamic learning, and elite population evolution. Table3 shows the comparison results among the proposed bacterial heuristic optimization algorithm for FS (BHFS) and BFO for FS (BFOFS) and BCO for FS (BCOFS). The rows of Ave. and Std. show the average and standard deviation classification metrics of 30 independent runs, respectively. The rows of p show the significance values obtained by the Wilcoxon rank-sum test.From the specific data, the feature numbers of these algorithms are consistently unchanged. This is because the controlling strategies for BHFS, BFOFS, and BCOFS are the same (see Section4.3). Consequently, there is no difference in the significance of Fno.On the whole, excluding Fno, BHFS obtains significantly better results in 92 out of 96 cases versus BFOFS while achieving statistically similar performance in 4 cases. Since the proposed three strategies of BHFS are the improvements of BFOFS and BCOFS, they are also the key modules that compose BHFS, where each strategy is interlinked. This result proves that BHFS is better than BFOFS and BCOFS, which reflects that our improvements are effective.From the comparison between BFOFS and BCOFS, we can see that the classification results of BCOFS perform better than those of BFOFS. This demonstrates that the improved life cycle model in BCOFS performs better than the triple-nested loop structure, in which optimization capability is further enhanced. Moreover, compared with BFOFS and BCOFS, BHFS achieves significantly better performance in 86 out of 96 cases while obtaining statistically similar results in 10 cases. In particular, it almost achieves the best classification error rate for eight datasets. Except for the German dataset with the 26.9% classification error rate on average, BHFS for other datasets has achieved an accuracy rate of more than 90%, even the 100% accuracy rate achieved for LA and DLBCL, two microarray datasets. Thus, it is evident that BHFS outperforms both BFOFS and BCOFS. The primary reason is that BHFS has further developed the life cycle with the three proposed strategies, which improve the algorithm’s search ability to locate the optimal space in the population initialization step, increase the probability of individual learning in the chemotaxis stage, and enhance the quality of population evolution in the reproduction and dispersal-elimination stages.Table4 illustrates the average calculation time for feature selection and classification in each run. Compared to all bacterial-based methods, BHFS achieves a superior classification effect with less computational complexity. Throughout the iteration period, the computing time of the BFO algorithm increases exponentially due to its nested structure. However, life cycle enhancement offered by BCO streamlines this procedure, hence reducing computing cost dramatically. Inspired by BCO, BHFS modifies the parts of the population update based on BCO so that reproduction and dispersal-elimination operations can be carried out just one at a time, and the algorithm is additionally programmed with a rule to instantly stop iterating when the ideal solution occurs repeatedly.


### 5.2. Comparisons with Semisupervised Methods

Since BHFS demonstrates its superiority and usefulness in Section5.1, this section evaluates the effectiveness of the proposed self-adjustment, semisupervised KNN strategy for BHFS. In the following context, we refer to BHFS with the self-adjusted, semisupervised KNN strategy as SBHFS. The compared two semisupervised techniques based on KNN are as follows: One is the semisupervised KNN (SSKNN) [38], which assigns the unlabeled sample’s label to the label of the labeled sample that is closest to it. The best K semisupervised KNN (BKSKNN) [41] is another comparative technique. By learning about their neighbors, BKSKNN also labels unlabeled samples. In contrast, BKSKNN has two steps as opposed to SSKNN, the first of which is to compute the accuracy of the labeling result of KNN using various K values. K is then set from 1 to 51. The process finds the best K value with the highest level of labeling accuracy and then uses the best-labeled data to perform the subsequent procedure. These two semisupervised learning approaches are embedded into BHFS for the comparison of the effectiveness of different semisupervised methods, and they are recorded as BHFS-SSKNN and BHFS-BKSKNN, respectively. Table 5 shows the average, standard deviation classification metric, and statistical test results of different semisupervised learning approaches for benchmark datasets. Since all three methods are based on BHFS, their feature subset size control methodologies are identical (see Section 4.3). Consequently, the significance of Fno. does not change in the three methods.SBHFS outperforms BHFS-SSKNN and BHFS-BKSKNN in the majority of classification evaluation metrics, demonstrating the efficacy of the self-adjusted, semisupervised KNN technique. Self-adjusted, semisupervised KNN will adaptively update theK value to find a better label for each sample from varying data sizes, whereas SSKNN will simply apply the fixed K value that limits the algorithm’s performance.Compared with BHFS-SSKNN, SBHFS obtains a lower error rate in all data cases. In other classification metrics, BHFS-SSKNN shows better performance with the true-positive rate (TPR), indicating that the SSKNN method is more capable of correctly labeling positive samples, while SBHFS can achieve significantly better or similar performance with the true-negative rate (TNR). This proves that using TPR or TNR metrics alone to judge the performance of algorithms is one-sided. Therefore, it is necessary to deeply analyze the algorithm effect through the remaining three comprehensive evaluation indicators (Pre, GM, andF1). The results demonstrate that the Pre scores of SBHFS are 100 percent superior to those of BHFS-SSKNN, while the GM scores of SBHFS are higher for five out of eight datasets, and the F1 scores are higher for half of the datasets. Thus, self-adjusted, semisupervised KNN does improve the performance of SBHFS.Figure4 shows the bar chart of the comparison results with semisupervised methods. The horizontal axis corresponds to evaluation metrics. Fno. is excluded since the comparison algorithms use the same feature subset size control methods. The ordinate represents each algorithm’s score, with larger values indicating superior performance. From Table 5 and Figure 4, we can see that SBHFS can achieve statistically significant better classification performance for all high-dimensional datasets with the most different metrics. For benchmark datasets, statistical significance is not as obvious. One reason is that in a low-dimensional space, the KNN-based semisupervised learning method is less affected by the value of K. Therefore, we conclude that the proposed self-adjusted, semisupervised KNN mechanism is more suitable for high-dimensional data analysis.Figure 4
The bar chart of the comparison results with semisupervised methods.


### 5.3. Comparisons with Benchmark Methods

We further compare the proposed SBHFS method with other bioinspired wrapper FS algorithms. Table6 shows different evaluation metrics (i.e., Err., Fno., TPR, TNR, Pre, GM, and F1) of SBHFS and benchmark methods for test sets. In general, SBHFS achieves competitive results compared to the other six bioinspired feature selection methods, which means that SBHFS is superior to other bioinspired wrapper FS algorithms.From the specific results, SBHFS performs best for five datasets (i.e., LA, CNS, Colon, SRBCT, and DLBCL) with the most evaluation metrics. However, for the Australian dataset, the proposed method does not perform best. Comparing the results of other algorithms reveals that the effect of SBHFS may be influenced by the sparsity of features. To be specific, according to the results for the Australian dataset, we can see that smaller subsets produce better results and that the number of effective features of the Australian dataset is about 1 or 2. Nevertheless, SBHFS sets the subset size to integers between 1 and 10 when the total dataset contains fewer than 50 features (see Section4.3). This increases the average size of the subset in each iteration, which exceeds the effective feature size of the Australian dataset. Except for this, based on the results of statistical significance tests for all datasets, SBHFS achieves considerably enhanced efficiency in 229 of 336 cases (39 cases with the “=” p value are excluded), which illustrates that SBHFS performs well for most of the datasets, especially for high-dimensional ones.From the perspective of the fundamental algorithm, SBHFS achieves notable significance in 150 out of 224 cases (25 cases with the “=”p value are excluded) in comparison to four other bacterial-based FS methods, i.e., ACBFO, ISEDBFO, SMA, and MOBIFS. The results demonstrate that the improvements in SBHFS are better than in other bacterial-based algorithms in this study. The proposed strategies optimize the searching ability of the algorithm, achieving smaller classification error rates and better results on other evaluation indexes. Moreover, the superiority of SBHFS is more obvious for high-dimensional datasets (i.e., #features > 1999). For example, compared with ISEDBFO, SBHFS achieves 11.2% lower Err. for Colon (#features = 1999) and 9.8% lower Err. for SRBCT (#features = 2308). This demonstrates that the dimension redundancy capability of the suggested feature selection approach is satisfactory.Furthermore, compared with BMRFO and IBFA, SBHFS achieves superior performance in 79 out of 112 cases (14 cases with the “=”p value are excluded). Specifically, compared to IBFA, SBHFS achieves 9.9% higher F1 for LA (# Features = 7129) and 1.4% higher F1 for SRBCT (# Features = 2308). Compared to bacterial-based algorithms, the effects between SHBFS and other bioinspired algorithms are better. This shows that the proposed modified bacterial-based FS algorithm is better for solving dimension reduction problems and that SBHFS can be used not only for high-dimensional datasets but also for some low-dimensional datasets.To verify the stability of SBHFS, the boxplot in Figure5 shows the comparison results of the SBHFS with other bioinspired FS methods. According to the boxplot, except for the Australian dataset with the 35.7% average classification error rate, SBHFS has achieved the best accuracy rate compared with other algorithms for other datasets. Moreover, the median results show that SBHFS generally achieves lower error rates, and the width of boxes indicates that SBHFS is more stable than other comparison methods. This is due to the dynamic learning method that allows the bacterial population of each iteration to move closer to the optimal solution instead of searching randomly.Figure 5
The box-line plot of comparison results with benchmark methods.


## 5.1. Comparisons with Standard BFO and BCO

This comparison aims to verify the effectiveness of the proposed three strategies in BHFS, including hierarchical population initialization, dynamic learning, and elite population evolution. Table3 shows the comparison results among the proposed bacterial heuristic optimization algorithm for FS (BHFS) and BFO for FS (BFOFS) and BCO for FS (BCOFS). The rows of Ave. and Std. show the average and standard deviation classification metrics of 30 independent runs, respectively. The rows of p show the significance values obtained by the Wilcoxon rank-sum test.From the specific data, the feature numbers of these algorithms are consistently unchanged. This is because the controlling strategies for BHFS, BFOFS, and BCOFS are the same (see Section4.3). Consequently, there is no difference in the significance of Fno.On the whole, excluding Fno, BHFS obtains significantly better results in 92 out of 96 cases versus BFOFS while achieving statistically similar performance in 4 cases. Since the proposed three strategies of BHFS are the improvements of BFOFS and BCOFS, they are also the key modules that compose BHFS, where each strategy is interlinked. This result proves that BHFS is better than BFOFS and BCOFS, which reflects that our improvements are effective.From the comparison between BFOFS and BCOFS, we can see that the classification results of BCOFS perform better than those of BFOFS. This demonstrates that the improved life cycle model in BCOFS performs better than the triple-nested loop structure, in which optimization capability is further enhanced. Moreover, compared with BFOFS and BCOFS, BHFS achieves significantly better performance in 86 out of 96 cases while obtaining statistically similar results in 10 cases. In particular, it almost achieves the best classification error rate for eight datasets. Except for the German dataset with the 26.9% classification error rate on average, BHFS for other datasets has achieved an accuracy rate of more than 90%, even the 100% accuracy rate achieved for LA and DLBCL, two microarray datasets. Thus, it is evident that BHFS outperforms both BFOFS and BCOFS. The primary reason is that BHFS has further developed the life cycle with the three proposed strategies, which improve the algorithm’s search ability to locate the optimal space in the population initialization step, increase the probability of individual learning in the chemotaxis stage, and enhance the quality of population evolution in the reproduction and dispersal-elimination stages.Table4 illustrates the average calculation time for feature selection and classification in each run. Compared to all bacterial-based methods, BHFS achieves a superior classification effect with less computational complexity. Throughout the iteration period, the computing time of the BFO algorithm increases exponentially due to its nested structure. However, life cycle enhancement offered by BCO streamlines this procedure, hence reducing computing cost dramatically. Inspired by BCO, BHFS modifies the parts of the population update based on BCO so that reproduction and dispersal-elimination operations can be carried out just one at a time, and the algorithm is additionally programmed with a rule to instantly stop iterating when the ideal solution occurs repeatedly.


## 5.2. Comparisons with Semisupervised Methods

Since BHFS demonstrates its superiority and usefulness in Section5.1, this section evaluates the effectiveness of the proposed self-adjustment, semisupervised KNN strategy for BHFS. In the following context, we refer to BHFS with the self-adjusted, semisupervised KNN strategy as SBHFS. The compared two semisupervised techniques based on KNN are as follows: One is the semisupervised KNN (SSKNN) [38], which assigns the unlabeled sample’s label to the label of the labeled sample that is closest to it. The best K semisupervised KNN (BKSKNN) [41] is another comparative technique. By learning about their neighbors, BKSKNN also labels unlabeled samples. In contrast, BKSKNN has two steps as opposed to SSKNN, the first of which is to compute the accuracy of the labeling result of KNN using various K values. K is then set from 1 to 51. The process finds the best K value with the highest level of labeling accuracy and then uses the best-labeled data to perform the subsequent procedure. These two semisupervised learning approaches are embedded into BHFS for the comparison of the effectiveness of different semisupervised methods, and they are recorded as BHFS-SSKNN and BHFS-BKSKNN, respectively. Table 5 shows the average, standard deviation classification metric, and statistical test results of different semisupervised learning approaches for benchmark datasets. Since all three methods are based on BHFS, their feature subset size control methodologies are identical (see Section 4.3). Consequently, the significance of Fno. does not change in the three methods.SBHFS outperforms BHFS-SSKNN and BHFS-BKSKNN in the majority of classification evaluation metrics, demonstrating the efficacy of the self-adjusted, semisupervised KNN technique. Self-adjusted, semisupervised KNN will adaptively update theK value to find a better label for each sample from varying data sizes, whereas SSKNN will simply apply the fixed K value that limits the algorithm’s performance.Compared with BHFS-SSKNN, SBHFS obtains a lower error rate in all data cases. In other classification metrics, BHFS-SSKNN shows better performance with the true-positive rate (TPR), indicating that the SSKNN method is more capable of correctly labeling positive samples, while SBHFS can achieve significantly better or similar performance with the true-negative rate (TNR). This proves that using TPR or TNR metrics alone to judge the performance of algorithms is one-sided. Therefore, it is necessary to deeply analyze the algorithm effect through the remaining three comprehensive evaluation indicators (Pre, GM, andF1). The results demonstrate that the Pre scores of SBHFS are 100 percent superior to those of BHFS-SSKNN, while the GM scores of SBHFS are higher for five out of eight datasets, and the F1 scores are higher for half of the datasets. Thus, self-adjusted, semisupervised KNN does improve the performance of SBHFS.Figure4 shows the bar chart of the comparison results with semisupervised methods. The horizontal axis corresponds to evaluation metrics. Fno. is excluded since the comparison algorithms use the same feature subset size control methods. The ordinate represents each algorithm’s score, with larger values indicating superior performance. From Table 5 and Figure 4, we can see that SBHFS can achieve statistically significant better classification performance for all high-dimensional datasets with the most different metrics. For benchmark datasets, statistical significance is not as obvious. One reason is that in a low-dimensional space, the KNN-based semisupervised learning method is less affected by the value of K. Therefore, we conclude that the proposed self-adjusted, semisupervised KNN mechanism is more suitable for high-dimensional data analysis.Figure 4
The bar chart of the comparison results with semisupervised methods.


## 5.3. Comparisons with Benchmark Methods

We further compare the proposed SBHFS method with other bioinspired wrapper FS algorithms. Table6 shows different evaluation metrics (i.e., Err., Fno., TPR, TNR, Pre, GM, and F1) of SBHFS and benchmark methods for test sets. In general, SBHFS achieves competitive results compared to the other six bioinspired feature selection methods, which means that SBHFS is superior to other bioinspired wrapper FS algorithms.From the specific results, SBHFS performs best for five datasets (i.e., LA, CNS, Colon, SRBCT, and DLBCL) with the most evaluation metrics. However, for the Australian dataset, the proposed method does not perform best. Comparing the results of other algorithms reveals that the effect of SBHFS may be influenced by the sparsity of features. To be specific, according to the results for the Australian dataset, we can see that smaller subsets produce better results and that the number of effective features of the Australian dataset is about 1 or 2. Nevertheless, SBHFS sets the subset size to integers between 1 and 10 when the total dataset contains fewer than 50 features (see Section4.3). This increases the average size of the subset in each iteration, which exceeds the effective feature size of the Australian dataset. Except for this, based on the results of statistical significance tests for all datasets, SBHFS achieves considerably enhanced efficiency in 229 of 336 cases (39 cases with the “=” p value are excluded), which illustrates that SBHFS performs well for most of the datasets, especially for high-dimensional ones.From the perspective of the fundamental algorithm, SBHFS achieves notable significance in 150 out of 224 cases (25 cases with the “=”p value are excluded) in comparison to four other bacterial-based FS methods, i.e., ACBFO, ISEDBFO, SMA, and MOBIFS. The results demonstrate that the improvements in SBHFS are better than in other bacterial-based algorithms in this study. The proposed strategies optimize the searching ability of the algorithm, achieving smaller classification error rates and better results on other evaluation indexes. Moreover, the superiority of SBHFS is more obvious for high-dimensional datasets (i.e., #features > 1999). For example, compared with ISEDBFO, SBHFS achieves 11.2% lower Err. for Colon (#features = 1999) and 9.8% lower Err. for SRBCT (#features = 2308). This demonstrates that the dimension redundancy capability of the suggested feature selection approach is satisfactory.Furthermore, compared with BMRFO and IBFA, SBHFS achieves superior performance in 79 out of 112 cases (14 cases with the “=”p value are excluded). Specifically, compared to IBFA, SBHFS achieves 9.9% higher F1 for LA (# Features = 7129) and 1.4% higher F1 for SRBCT (# Features = 2308). Compared to bacterial-based algorithms, the effects between SHBFS and other bioinspired algorithms are better. This shows that the proposed modified bacterial-based FS algorithm is better for solving dimension reduction problems and that SBHFS can be used not only for high-dimensional datasets but also for some low-dimensional datasets.To verify the stability of SBHFS, the boxplot in Figure5 shows the comparison results of the SBHFS with other bioinspired FS methods. According to the boxplot, except for the Australian dataset with the 35.7% average classification error rate, SBHFS has achieved the best accuracy rate compared with other algorithms for other datasets. Moreover, the median results show that SBHFS generally achieves lower error rates, and the width of boxes indicates that SBHFS is more stable than other comparison methods. This is due to the dynamic learning method that allows the bacterial population of each iteration to move closer to the optimal solution instead of searching randomly.Figure 5
The box-line plot of comparison results with benchmark methods.


## 6. Conclusions

This paper presents a semisupervised bacterial heuristic feature selection algorithm (SBHFS) to address label incomplete and high-dimensional classification problems. The self-adjusted, semisupervised KNN strategy can reconstruct labels effectively with the help of the two-step self-training mechanism, and the improved bacterial heuristic method can enhance the searching precision by increasing feature selection variety and cooperating with hierarchical population initialization, dynamic learning, and elite population evolution strategies. To be specific, hierarchical population initialization accelerates the convergence of the algorithm with the help of the SU feature ranking method and the proposed layer mechanism. Then, the dynamic learning strategy increases the diversity of the feature subset because it promotes the communication of searching bacteria. Furthermore, the proposed elite population evolution strategy changes the population update method of the bacterial-based algorithm and improves its optimization performance. The comparisons with the semisupervised methods show that the proposed semisupervised learning method is effective for labeling incomplete data, especially for high-dimensional datasets.Although the proposed SBHFS approach has shown promise in high-dimensional classification with missing labels, the proposed semisupervised approach is based on the enhancement of the KNN semisupervised technique, and the semisupervised method based on other learners is not considered. This may limit the efficiency of the bacterial heuristic algorithm in FS for classification issues involving plenty of sparse features. Considering this information in feature selection may help bacterial heuristic algorithms achieve better results, although this is challenging to accomplish. In our future endeavors, we will consider this direction.



---

*Source: 4196920-2023-02-22.xml*