{'fraction_non_alphanumeric': 0.023890784982935155, 'fraction_numerical': 0.0082426427973469, 'mean_word_length': 4.918445121951219, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Effective Metaheuristic for Bi-objective Feature Selection in Two-Class Classification Problem

Feature selection is known as a very useful technique in machine learning practice as it may result in the development of more straightforward models with better accuracy. Traditionally, feature selection is considered as a single-objective problem, however, it can be easily formulated in terms of two objectives. The solving of such problems requires the application of appropriate multi-objective optimization methods that do not always offer equally good solutions even under the same conditions. This paper focuses on the development of a metaheuristic optimization approach for bi-objective feature selection problem in two-class classification. We consider the solving of this problem in terms of minimization of both misclassification error and feature subset size. For solving the considered problem, an adaptation of the Multi-Objective Adaptive Memory Programming (MOAMP) metaheuristic based on the tabu search strategy is proposed. Our MOAMP adaption has been utilized to obtain the sets of most relevant features for two real classification problems with two classes. Finally, using popular Pareto front quality indicators, the obtained results have been compared with the sets of non-dominated solutions derived by the well-known NSGA2 algorithm. The conducted research allows concluding about the ability of the MOAMP adaptation to get a better efficient frontier for the same number of objective function calls.


Introduction
Feature or variable selection (FS) constitutes a process of selecting the most relevant variables that form a less redundant subset of features with keeping their explanatory power with respect to the target variable. FS is a very popular methodology in machine learning as it allows increasing the prediction accuracy, constructing less complex predictor with faster training process, getting a better understanding of the analyzed data [1], as well as it may contribute to the prevention of model overfitting [2]. However, feature selection is known as a problem with high computational costs that results from the exponential growth of the number of possible feature subsets with an increase of a total number of variables [3]. Hence, taking into account the modern tendency of data dimensionality growth, the development of effective FS techniques remains to be a relevant problem which solving can contribute significantly in machine learning practice. For minimization of the size of feature subset and keeping the maximum of the explanatory ability of a predictor, FS should be considered as a bi-objective optimization problem. In particular, FS problem statement, in terms of feature subset size minimization and classification accuracy maximization, is seen popular [4,5]. Classification is a type of supervised machine learning problem that lies in predicting to which category a new instance belongs to using a previously trained classifier on the basis of available observations. The development of robust classifiers with optimal feature subsets is a widespread challenging problem, which covers a variety of real-life applications such as text data processing [6], facial recognition technology [7], faults detection in the technical system [8], bankruptcy prediction [9] etc. This paper is focused on the development of an effective feature selection approach for pervasive twoclass classification problem. We deal with the selection of relevant feature subset from the bi-objective perspective, considering both minimization of misclassification error and features subset size. Consequently, the objective is to obtain a set of non-dominated solutions forming an approximation of Pareto front for a considered classification problem. For doing so, we have proposed a methodology based on an adaptation of Multi-objective Adaptive Memory Programming (MOAMP) metaheuristic [10,11] that uses the tabu search strategy for getting global optima [12,13]. The MOAMP approach has been used successfully in some real problems of scheduling-routing planning [14][15][16] and supply chain design [17]. In this work, an attempt has been made to develop an adaptation of MOAMP metaheuristic with respect to the bi-objective feature selection problem. For the purpose of reasonable merit assessment, results of the MOAMP adaptation are compared with the approximations obtained by widely recognized Non-Dominated Sorting Genetic Algorithm 2 (NSGA2). The comparison is based on the estimation of Pareto front quality indicators such as cardinality and hypervolume. Both multi-objective optimization techniques are applied to features selection problem for two popular classifiers based on Logistic regression and Linear Discriminant analysis. The experiments have been performed using on real-life financial data. But the proposed MOAMP based bi-objective feature selection approach can be easily applied to different datasets that will be an object of our future research. The remainder of the paper is organized as follows. Section 2 presents the bi-objective feature selection problem. In section 3, the proposed MOAMP based technique is described. Section 4 is devoted to the experimental part and comparative analysis of MOAMP and NSGA2 results. Finally, in section 5, the main conclusions are offered.

Problem formulation
In case of a classification problem, the objective of machine learning is the training of a classifier using an available set A of n observations (or cases). Each observation is represented by a vector of values of m features V = {v 1 , v 2 , …, v m } and an information about to which class (0 or 1) the case belongs to (also named "label information"). Hence, in supervised learning, the training set A consists of a matrix with n rows and m columns, which corresponds to each feature value for each observation, and a vector L of label information for all n available observations. Generally, the training set A is divided into two parts, the first is in fact for the training process and the second subset serves for model validation. The proven practice to overcome the classifier overfitting is to perform crossvalidation. After the training process with cross-validation, the classifier can be used for prediction of the label for a new vector of feature values V. Thus, the aim of feature selection is to find the smallest possible feature subset S of size k, ⊂ , that keeps the predictable ability of the classifier. In other words, a classifier built on the subset S, must predict the labels of the available observations with minimal misclassification error. Consequently, the bi-objective feature selection problem can be formulated as the search such a feature subset S with the minimum size (objective function f 1 (S)) that concurrently minimize the misclassification error of the considered classifier (objective function f 2 (S)). As we deal with two objectives, our challenge is to find a set of non-dominated solution that forms efficient frontier or Pareto front of the considered biobjective optimization problem.

Bi-objective feature selection metaheuristic
The Multi-objective Adaptive Memory Programming (MOAMP) metaheuristic based on the tabu search (TS) strategy tries to adapt TS routine to the structure of the set of non-dominated solutions of a multi-objective problem [18]. Generally, the MOAMP framework includes three phases. The first phase is intended to get an initial approximation of the efficient set performing series of tabu searches. Whereas the second phase tries to improve the previously obtained set of solutions conducting searches with a modified objective function. And on the last stage, the searches are carried out around all solutions from the current efficient set until these searches does not provide improvements of the current efficient set. It is should be noticed that the MOAMP metaheuristic is quite a flexible technique and it can be considered as a framework that should be adapted to each particular type of an optimization problem. Here, in pseudo-code 1, we present our adaptation of MOAMP concept for bi-objective feature selection problem with some comments for each step. Pseudo-code 1. Adaptation of MOAMP metaheuristic Update S ND while performing this phase Phase 2 Repeat 5. = (0, 1); 6. ← ℎ( , ); 7. Update S ND Until S ND does not change for maxPhase2 iterations Phase 3 Repeat 8. Explore the neighborhood of each S from S ND that has not been explored and update S ND 9. Identify new non-dominated solutions Until S ND does not change The search process starts from the approximation the initial efficient set S ND with the empty set (step 1). The core of the first phase is the execution of two consecutive tabu search procedures (step 2 and 3).
Step 2 serves to find the left side optimum 1 that corresponds to the minimum of feature subset size 1 and to the maximum of misclassification error 2 . Then, starting from the solution 1 , TabuSearch routine is conducted, moving to the right side of solution space and trying to reach the minimum of misclassification error 2 .
Step 3 performs a similar search, but from the right side of the solution space. First, using the same TabuSearch routine with the complete set of variables V, it seeks to reach the right side optimum 2 that coincides with the minimum of the misclassification error 2 and the corresponded maximum number of features 1 . Furthermore, the optimum 2 is used like a starting point for TabuSearch procedure, which aims to move back to the left side optimum 1 . Thus, in steps 2 and 3, two crosssearches are carried out on the basis of tabu strategy 1 → 2 and 2 → 1 , consequently. While both steps are conducted, the current set of non-dominated solutions is continually updated with the new solutions that could improve it. As already mentioned, the second phase of MOAMP metaheuristic is designed to improve the set of non-dominated solutions , obtained in Phase 1. This is possible through the change of the objective function that is used during tabu searches. The modified objective function is given by: min  1  1  2  2  max  min  max  min  1  1  2  2 max , 1 , where λ is the weight factor randomly generated from a uniform distribution U(0, 1). during the specified number of iterations maxPhase2. The last third phase of the MOMAP adaptation does not perform optimization procedures, instead, the neighborhood of each solution from the efficient set is analysed. In other words, only neighbour solutions are added to the set if they improve it. This stage is continued until new explorations of neighbourhoods do not give better results. The neighborhood exploration of the last MOAMP phase is similar to the construction of a candidate list in tabu searches. In both cases, three types of operations (or moves) are done: add, drop and interchange. It means that, in the case of the add operation, a variable from the set of all unused features can be appended to the current vector of variables. Drop move serves for the opposite operation that excludes a variable from the current vector and put it into the set of unused features. Interchange implies the combining of add and drop operations when one feature is removed from the current vector of variables, whereas an alternative variable is appended to the vector. General condition for making these moves is inactive tabu status of a considered feature. The control of tabu status is realized through a memory structure that contains two registers for add and drop moves. For example, if an untapped variable is considered to be added to the current vector of features, then it must have an inactive tabu status in the corresponded register. Consequently, the algorithm checks register that is responsible for operation to be done. In the case of interchange moves, both registers are checked. If the operation is permitted i.e. tabu status of the variable is inactive, then the algorithm performs this move and updates the corresponded register, activating tabu status for some number of search iterations. This parameter is called tabu tenure and defines how long tabu status can be active. We have mentioned the general condition to perform a move, and it comes down to the inactive status of a feature. However, there is an exception that is called Aspiration criteria and it implies an opportunity to make a move even with active tabu status. This is possible only if this move can improve the best ever found solution. Hence, due to the application of tabu memory structure and Aspiration criteria, tabu search algorithms are able to explore solution space beyond local optimality. Thus, implementing all three phases of the tabu search based MOAMP adaptation, it is possible to obtain set of non-dominated solutions or efficient set that forms Pareto front for the considered biobjective feature selection problem. In order to provide a better understanding of how our MOAMP metaheuristic works, in figure 1 and 2, the results of three MOAMP stages are illustrated. These data are a part of the experimental results that will be presented in section 4.   Figure 1, a demonstrates some trajectories of tabu searches that were done during the first phase. The star-shaped marks correspond to the solutions, passed by TabuSearch routine in step 2.2, whereas the circle marks show solutions that were added to the current approximation of the efficient set on this step. The pentagram icons illustrate how the tabu search procedure was passing in step 3.1 in order to reach the optimum 2 . The output of the first phase is the set of non-dominated solutions depicted by the diamond marks. This set was obtained in step 3.2 through updating current approximation with all visited solutions which could improve it. In figure 1

Experiments
In order to make the merit estimation of the proposed MOAMP adaptation, eight computational experiments have been performed with two real classification problems from the financial area, denoted S and I problem. Both datasets contain m = 38 features and n = 1538 observations. For each problem, two types of classifiers were considered, on the basis of Logistic regression (LR) and using Linear Discriminant analysis (LD). Consequently, four classification problems, S_38_LR, S_38_LD, I_38_LR, and I_38_LD, were investigated from the perspective of the abovementioned bi-objective features selection problem. For each stated classification problem, two experiments have been carried out, using the proposed MOAMP metaheuristic and well-known and proven NSGA2 algorithm. Both metaheuristics were driven for the same number of objective function calls and with the default seed of random number generator. All classifiers were trained with 5-folds cross-validation. The MOAMP adaptation has three main hyperparameters, which values were set as follows: tabu tenure equals to m-1, maxPhase2 = 5 and the number of iterations of TabuSearch routine without improvement of the best solution equals to m. NSGA2 hyperparameters are given by: population size is 2·m, crossover percentage is 0.7 and mutation rate that equals to 1/m. For each classification problem and metaheuristic, two Pareto front quality indicators were calculated on the basis of the obtained sets of non-dominated solutions, such as cardinality [19] and hypervolume [20]. Hence, these indicators are used for the comparison MOAMP and NSGA2 algorithms, and the greater value of an indicator, the more effective is the considered technique.