Keywords

1 Introduction

Data classification is an essential process in data works, the sorting scheme for large-scale data brings severe challenges. For example, a good searching engine needs to classify large-scale data in a webpage, such as Yahoo!’s webpage taxonomy, which has around 300 thousand categories [1]. Besides, many enterprises attach importance to the customer relationship management system to maintain a good relation with customers. Its core function of accurate identification needs a well classification method [2]. In summary, massive amount of data will to be processed, efficiency becomes an important factor in Internet environment.

Feature selection is a widely used tool for data classification with substantial efficiency and effectiveness [2]. It refers to many areas, including text classification, chest pathology identification, facial emotion recognition [3, 4], and so on. With the exponentially increasing time of data processing in classification problems, improving the computational speed while ensuring the accuracy is a hot issue. Feature selection methods select representative features from massive data and the generating optimized subsets can help improve the efficiency of computation in classification. Cutting down the irrelevant, redundant or the trivial features is the core of it [5,6,7]. Methods of feature selection can be classified into two main categories. One divides the methods into supervised, semi-supervised and unsupervised types by observing the number of features’ label [8]. The other divides the methods into filter, wrapper and embedded by distinguishing the structure of the algorithms. [9, 10]. These methods have their own special characteristics, but are related to each other. Filter sorts and screens data before classification and delete the lower ranking features [13, 15]. Nevertheless, this method often loops over all data, which cost lots of time in solving high dimensional data. Different from this, wrapper randomly selecting features by combing classifiers with different heuristic algorithms such as PSO, ACO, GA [11, 12, 16] etc.

The classifiers often includes, naive Bayes classifier, SVM, random forest classifier and so on. Their combination reduces the amount of calculation. But the accuracy is decreased. To deal with this, embedded method has been created. It combines the advantage of filter and wrapper, aiming at improving calculating effectiveness of algorithms [17]. However, selecting an appropriate combination is very much depends on the researchers’ practice experience [18].

As a popular heuristic algorithm, BFO is selected to be modified. It’s proposed in 2002, inspired by the process of bacterial survival and reproduction [19]. This algorithm is good at randomly searching optimal solutions, because of its ‘reproduction’ and ‘dispersal-elimination’ strategies that can help the individual escapes from the local optima. Although, it can be applied into preprocessing the multidimensional data, the accuracy will not be increased if only use the original algorithm. Adding adaptive strategy can change the swimming method of each bacteria and makes their searching area more diversity [25]. Besides, a supervised classification method, KNN has been adapted as the classifier.

In sum up, this paper proposed a wrapper-supervised classification method, ACBFO (Adapting Chemotaxis Bacterial Foraging Optimization), which aims to realize the high efficiency of data classification. It is empirically faster and more accurate than the other methods in most of time, especially when dealing with large-scale data. In practice, this achievement is significant, which can save many computation costs in data works. The contribution in this research is a novel method that improves the classification efficiency of the heuristic algorithm (BFO). The main goals and organization of the paper are as follow.

1.1 Goals

Three classical heuristic algorithms will be compared: Bacterial Foraging Optimization (BFO) [19], Bacterial Foraging Optimization with linear chemotaxis (BFOLIW) [20], and Binary Particle Swarm Optimization (BPSO) [21]. The first two methods are bacterial foraging based algorithm, they adapt the same optimization framework but different in chemotaxis strategies, while BPSO employ the binary mechanism based on the PSO. The main aims of this research are listed below:

  • A modified bacterial foraging based algorithm is proposed with adaptive chemotaxis to increase the accuracy of classification.

  • An elite feature combination strategy are designed to adaptively reduce the dimension of feature subset to increase the classification efficiency.

  • The reproduction and elimination mechanisms are redesigned to reduce the computation cost.

1.2 Organization

The other components of this paper are as follows: Sect. 2 introduces the basic information of Bacterial foraging optimization algorithm. Section 3 elaborates the concrete details of proposed algorithm. The experimental design and result are discussed in Sect. 4. Finally, the conclusion and future work are presented in Sect. 5.

2 Bacterial Foraging Optimization Algorithm

Combining heuristic algorithm with certain classifier is popular used in data classification nowadays. It will be implemented by means if feature selection methods. Feature selection can be realized by multitudinous approaches. Traditional approaches are based on statistics which sorts the features one by one through traversing entire dataset generating feature subsets and evaluating them by evaluation function [2]. This is appropriate for less quantity data.

Large amount of time will be cost when dealing with high dimension. Heuristic algorithms have exceptional performance in optimization which is good to be integrated with the evaluation function of feature selection. As one of common heuristic algorithm, bacterial foraging optimization is a heuristic distributed optimization algorithm. It emulates the social foraging habits of E. coli bacteria which contains chemotaxis, reproduction and elimination-dispersal nested processing [19].

Chemotaxis simulates the process of bacterial foraging. In this secession, bacteria swarming towards the place with high concentration of nutrients. One chemotaxis contains two steps [19], a tumble after tumble or a run after a tumble. They determine the nutrient concentration at the site by special pheromone. Once a unit find a good place, it will release attraction pheromone to inform other units [22]. On the contrary, if the nutrients is low concentration or is presenting noxious substances, it will release repulsive pheromone to notice other units to avoid approaching. In the BFO algorithm, this mechanism can help find the fitness of evaluation function more precisely. The step size of bacterial foraging optimization during chemotaxis stage is:

$$ \theta^{i} \left( {j + 1,k,l} \right)\, = \,\theta^{i} \left( {j,k,l} \right)\, + \, C\left( i \right) \frac{\vartriangle \left( i \right)}{{\sqrt {\vartriangle^{T} \left( i \right) \vartriangle \left( i \right)} }} $$
(1)

where the \( \theta^{i} \left( {j,k,l} \right) \) indicates the concentration of nutrients in \( j_{th} \) chemotaxis, \( k_{th} \) reproduction and \( l_{th} \) elimination-dispersal. \( C\left( i \right) \) is the chemotaxis step and \( \Delta \left( i \right) \) is a random vector limited in [−1,1]. Formula of cell to cell effect of bacterial foraging optimization is:

$$ J \left( {i,j,k,l} \right)\, = \,J\left( {i,j,k,l} \right)\, + \,J_{cc} \left( {\theta^{i} \left( {j,k,l} \right),\,P\left( {j,k,l} \right)} \right) $$
(2)

where \( J\left( {i,j,k,l} \right) \) presents the pheromone of \( i_{th} \) bacteria. \( J_{cc} \left( {\theta^{i} \left( {j,k,l} \right),P\left( {j,k,l} \right)} \right) \) controls the spreading rate of attractant or repelling agent [19].

Reproduction means the updating of bacterial group which contains two steps. Firstly, ranking the concentration of remaining nutrients in the environment [23]. Second, half of the bacterial are replaced by the reproduction of the top 50%. The change of bacterial foraging optimization nutrients:

$$ J _{health}^{i} \, = \, \sum\limits_{ j = 1}^{{ N_{c} + 1}} {J \left( { i ,j , k ,l } \right)} $$
(3)

where the \( J_{health}^{i} \) is the concentration of remaining nutrients, it presents the consumption of nutrients, the less \( J_{health}^{i} \), the higher it ranks.

Elimination-dispersal happens randomly in a custom probability generation mechanism [24]. When the conditions are met, the position of bacterial will be reset to enhance the algorithm’s ability of escaping from the local optimum. In the next section, the proposed methods for feature selection based on BFO will be introduced.

3 Adapting Chemotaxis Bacterial Foraging Optimization

The basic BFO can be used in training the classifier of feature selection. However, it often takes long time to do it due to the high dimension of data will increase the calculation cost with the nested structural BFO algorithm. Besides, the size of the training data also has impact on it which cannot be ignored. To improve these deficiencies, Adapting Chemotaxis Bacterial Foraging Optimization algorithm (ACBFO) which design an adapting learning strategy in chemotaxis section. Meanwhile, the K Nearest Neighbor algorithm holds the position of classifier for its fast speed and the characteristics of easy implement. The basic framework of ACBFO shows in Fig. 1.

Fig. 1.
figure 1

The overall flow of Adapting Chemotaxis Bacterial Foraging Optimization.

Full size image

3.1 Adapting Chemotaxis Mechanism

Basic chemotaxis step in BFO is fixed, but the movement of bacteria is not rigid in reality. Fixed step makes the bacteria easy to be caught in a same local place which is not benefit for the steady development of the population. A simple adaptive step changing method is adopted [26]. In the ACBFO, the initial step for each bacterium is:

$$ \alpha \, = \,\left| {\left( {1\, - \,\left( {i \div S} \right)} \right)\,*\,\left( {C_{start} \, - \,C_{end} } \right)\, + \,C_{end } } \right| $$
(4)
$$ C_{step} \, = \, \frac{{\left| { J \left( { i ,j } \right) } \right|}}{{\left| { J \left( { i , j } \right) } \right| + \alpha }} \, = \, \frac{1}{{ \left( { 1 + \frac{1}{{\left| { J \left( { i ,j } \right) } \right|}} } \right)}} $$
(5)

It means that each bacterium \( i \) has different swimming step, which increasing the diversity of bacterial population.

During the foraging time, every unit needs to learning from others which can improving the probability to find a nutrient-rich place. The learning strategy is classical in particle swarm optimization algorithm.

$$ C \, = \,C_{step} \, + \,c_{1} R_{1} \left( {PBest_{i} \, - \,Pos_{i} } \right)\, + \,c_{2} R_{2} \left( {Best\, - \,Pos_{i} } \right) $$
(6)

where the \( PBest_{i} \) is the personal optimal value for each bacterial colony and the \( Best \) is the global best value for each iteration. The pseudo code of ACBFO is below.

3.2 Feature Combination Updating Mechanism

When dealing with high dimension data, reducing the features which are barely improving the classification is good to better training the classifier and reduce the calculation time. The basic position updating formula is:

$$ Pos\left( {i,j + 1} \right)\, = \,Pos\left( {i,j} \right)\, + \,C\left( i \right)\frac{\Delta \left( i \right)}{{\sqrt {\Delta^{T} \left( i \right)\Delta \left( i \right)} }} $$
(7)

after this step, a judge mechanism is design to updating the feature combination for next calculation of nutrient \( J\left( {i,j} \right) \). The judge mechanism has shown in Table 1 and the calculating formula for \( J\left( {i,j} \right) \) is:

Table 1. The pseudo code of ACBFO
Full size table
$$ J\left( {i,j} \right) = Classifier_{KNN} \left( { Pos \left( { i ,j + 1 } \right) } \right) $$
(8)

The pseudo code of feature combination updating is below (Table 2).

Table 2. The pseudo code of Feature combination updating
Full size table

3.3 Bacterial Population Position Updating Mechanism

Bacterial population is updated after feature combination updating. During the bacterium swimming period, if the training performance of classifier is bad (e.g. training result leads the error rate lower than threshold value over certain times), elimination-dispersal will start. The population of bacterium needs reset. Otherwise, reproduce the bacterial population. The pseudo code of bacterial population updating is below (Table 3):

Table 3. The pseudo code of bacterial population updating
Full size table

4 Experimental Design and Result

In this section, the proposed algorithm is compared with three classical intelligent heuristic algorithms. This paper evaluate the ACBFO algorithm with binary PSO, standard BFO and its variants BFOLIW (with linear chemotaxis) empirically by comparing their classification accuracy and time. The parameter setting and datasets for testing are as follow.

4.1 Parameter Setting

The parameters setting of them are followed: The popular size S is 50, the dimension of datasets is averagely divided into 10 parts. For example, 11_Tumors datasets take the rule of ‘5:5:50’, which means the number of selected features that be inputted into the algorithm is from 5 to 50, with the grow step of 5. The run times of algorithm in each dimension is 30. In this experiment, there is not much difference of accuracy between 5 iterations and 30 iterations. So, the iteration times of each runs is 5, because the amount of computation is enough under the appropriate population size and run times.

4.2 Datasets for Testing

The performance of the algorithms are evaluated by the classification accuracy based on 12 datasets which are widely used in testing the effect of feature selection algorithm. Table 4 shows the detail of the datasets, they are obtained from the http://www.gems-system.org/. which is used in testing the performance of a discrete bacterial algorithm for feature selection [27]. When training the classifier, randomly choosing 70% of the data as training set, the remain 30% are as testing set.

Table 4. Datasets for feature selection
Full size table

4.3 Experiment Result in Accuracy

The experiment was implemented in MATLAB, aims at analyzing the accuracy and run time of the proposed algorithm. The accuracy was measured by the rules ‘Accuracy = 1- The error rate of classification’. The results are shown in Fig. 2. The abscissa represents the number of evaluated features in each evaluation and the ordinate represents the accuracy of classification. The proposed ACBFO algorithm performs well in most of time, especially in SRBCT, Lung Cancer Large and Leukemia 2 for their ‘accuracy’ is higher than 90%. These datasets has 50 ~ 200 instances, 3 ~ 11 classes and the average ‘instances/feature attribution’ rate is 1.2%. It reflects the ACBFO is good at dealing with multi-attribution data.

Fig. 2.
figure 2

Average classification accuracy of each algorithm on different datasets

Full size image

As shown in Fig. 3, ACBFO does well in (g), (h) and (l) which has small ratio of ‘instances/feature attribution’. However, it is unsteady when dealing with the data with little attributions. The accuracy lower than the compared algorithm serval times in 2 class datasets (i), (j) and (k). In conclusion, ACBFO can increase the accuracy and efficiency of data classification when dealing with high dimension datasets. But it’s unstable if the classes of the dataset is less than 3.

Fig. 3.
figure 3

Average classification accuracy of each algorithm on different datasets

Full size image

4.4 Experiment Result in Efficiency

Table 5 shows the average accuracy and the average computation time of each compared algorithms. As shown in the results, the ACBFO still performance better than other compared algorithms in most time. Although, it seems to be surpassed several times in certain datasets, the overall performance in raising classification accuracy is good. On one hand, even BPSO is better than ACBFO in ‘German’ datasets, the actual accuracy difference is only 0.002. On the other hand, the computational effective of ACBFO is well in nigh-twelfth of data.

Table 5. Accuracy and time of each algorithms
Full size table

What needs illustration is that the statistics below are acquired from a new experiment that the population size of each algorithm are set into 5. The data in Table 5 proof that, the proposed algorithm can get good result even the searching group is small.

5 Conclusion and Future Work

Based on the basic BFO, a modified algorithm is proposed. ACBFO includes an adapting chemotaxis strategy and a feature updating strategy. It improves the performance of heuristic algorithm in feature selection and classification. After testing it in 12 popular basics datasets, the results shows that it can obtain better classification accuracy in the datasets of smaller ‘instances/feature attribution’ ratio. In theory, this research find a different way to make the BFO better connect with KNN classifier, acquiring a well computation accuracy and efficiency. In practice, this achievement can save many computation costs in data works. The contribution of this paper is a novel method that improves the classification efficiency of the heuristic algorithm (BFO). Comparing with BFO, BFOLIW and BPSO, the performance of ACBFO should to be enhance by increasing the stability and further improving of computational accuracy. For example, designing a communicating mechanism in different bacterial groups to avoid bacterium units becoming too scattered, which is averse to result convergency.