Handling Imbalanced Classification Problems with Support Vector Machines via Evolutionary Bilevel Optimization

1 Handling Imbalanced Classification Problems with Support Vector Machines via Evolutionary Bilevel Optimization Alejandro Rosales-P´erez, Salvador Garc´ıa, Francisco Herrera, Senior Member, IEEE Abstract—Support vector machines are popular learning algorithms to deal with binary classification problems. They traditionally assume equal misclassification costs for each class; however, real-world problems may have an uneven class distribution. This paper introduces EBCS-SVM: Evolutionary Bilevel Costsensitive Support Vector Machines. EBCS-SVM handles imbalanced classification problems by simultaneously learning the support vectors and optimizing the SVM hyper-parameters, which comprise the kernel parameter and misclassification costs. The resulting optimization problem is a bilevel problem, where the lower-level determines the support vectors and the upper-level the hyper-parameters. This optimization problem is solved using an evolutionary algorithm at the upper-level and Sequential Minimal Optimization at the lower-level. These two methods work in a nested fashion, i.e., the optimal support vectors help guide the search of the hyper-parameters, and the lower-level is initialized based on previous successful solutions. The proposed method is assessed using 70 datasets of imbalanced classification and compared with several state-of-the-art methods. The experimental results, supported by a Bayesian test, provided evidence of the effectiveness of EBCS-SVM when working with highly imbalanced datasets. Index Terms—Support Vector Machines, Imbalanced Classification, Data Preprocessing, Evolutionary Algorithms, Bilevel Optimization. I. Introduction SUPPORT vector machines (SVMs) [1] are among the most popular supervised learning algorithms, with strong theoretical foundations and high effectiveness in real-world problems. The idea behind SVMs is to find the hyper-plane that maximizes the separation margin between two categories. In their canonical form, SVMs assume an equal cost for each class. This assumption This work was partially supported by Project PID2020-119478GBI00 funded by MICINN/AEI/10.13039/501100011033 and by Project A-TIC-434-UGR20 funded by FEDER/Junta de Andaluc´ıaConsejer´ıa de Transformaci´on Econ´omica, Industria, Conocimiento y Universidades. The authors acknowledge the support from “Laboratorio de Superc´omputo del Baj´ıo” through project 300832 from CONACyT. A. Rosales-P´erez ([email protected]) is with the Centro de Investigaci´on en Matem´aticas (CIMAT), Monterrey, N.L., Mexico. S. Garc´ıa (salv[email protected]) and F. Herrera (her- [email protected]) are with the Department of Computer Science and Artificial Intelligence, Andalusian Research Institute in Data Science and Computational Intelligence (DaSCI), University of Granada, 18071, Granada, Spain. works well when the number of instances for each class is roughly similar. However, real-world problems seldom have a balanced class distribution. The imbalanced classification problem refers to an uneven class distribution [2]–[4], i.e., there is an overrepresented class, known as the majority class, and an under-represented class, known as the minority class. Imbalanced classification problems further have the characteristic that the minority class is the one of interest. Therefore, accurately recognizing the minority class becomes crucial in several applications, such as medical diagnosis, fraud detection, and face recognition. There are two main approaches to deal with imbalanced classification problems with SVMs: data-level and algorithm-level methods [5]. The first approach aims to balance the dataset through oversampling the minority class [3], [6]–[8] or undersampling the majority class [3], [9]–[11]. Then, SVM learns from the edited dataset [12]. Although data-level methods are flexible, they ignore the particularities of learning algorithms. Conversely, algorithm-level methods modify the learning algorithm to be robust to uneven class distributions. For SVMs, common modifications comprise hyper-plane shifting [13], [14], kernel adaptation [15], and cost-sensitive [16]. Algorithmlevel methods often offer better performance than datalevel ones [16]; however, they need to define a set of hyperparameters, such as the extent of shifting compensation or the correct costs1for each class. Therefore, methods for imbalanced classification must not only learn when class distributions are unequal, but their hyper-parameters must also be tuned to get peak performance. Bilevel optimization (BLO) arises as an alternative for hyper-parameter optimization. BLO differs from traditional optimization in that the optimization problem has as part of its constraints a second optimization problem. In our context, the principal optimization or upper-level problem is the hyper-parameter optimization, and the second or lower-level problem is the learning of support vectors. These two problems interplay, i.e., the definition of the hyper-parameters influences the optimal set of support vectors, and this set of support vectors defines the model to predict unseen cases. However, BLO problems are computationally challenging because of their non-convexity 1The misclassification costs are the weights applied to errors incurred by classifying positive or negative samples. arXiv:2204.10231v1 [cs.LG] 21 Apr 2022 2 and non-linearity [17], [18]. Evolutionary algorithms (EAs) are powerful search tools capable of solving complex optimization problems, such as BLO problems. Recently, the interest in using EAs to address machine learning problems is growing fastly [19]– [29]. For imbalanced learning, EAs have been used for data sampling [30], [31] and cost-sensitive learning [32]. Although recent studies address the problem of determining the optimal misclassification costs [32], [33], they have paid little attention to considering the hyper-parameters of the learning algorithm, along with exploiting the hierarchical nature of parameter and hyper-parameter learning to guide search. Furthermore, taking advantage of the properties of the learning algorithm to estimate the classification performance efficiently in imbalanced problems is almost unexplored. In the light of the above mentioned, this paper introduces EBCS-SVM: Evolutionary Bilevel Cost-Sensitive Support Vector Machines. EBCS-SVM combines an EA and the Sequential Minimal Optimization (SMO) algorithm in a nested manner. The EA optimizes the cost of hyper-parameters, which are the costs of each class and the kernel parameters, and the SMO learns the optimal support vectors. These two optimizers interact such that information from one level is used by the other to improve search and convergence capabilities. We summarize the main contributions of this paper as follows: •We propose EBCS-SVM, which allows learning SVMs in imbalanced classification problems and automatically sets the misclassification costs and kernel parameter. •EBCS-SVM uses the information from the lower-level to guide the search to the upper-level and takes advantage of the previous successful hyper-parameters to initialize the set of support vectors. •The bilevel formulation that jointly learns parameters and hyper-parameters. •The definition of the upper-level objective function that allows estimating the performance of the SVM without performing cross-validation. The performance of EBCS-SVM was assessed using a suite of 70 benchmark datasets of imbalanced classification and compared with the state-of-the-art methods. The experimental evaluation revealed an outstanding efficacy of EBCS-SVM when faced with problems with a high disproportion of classes. The hierarchical Bayesian test supported the main findings. The rest of this paper is organized as follows. Section II introduces the related works on imbalanced classification problems, hyper-parameter optimization, and bilevel optimization. Section III describes the general bilevel formulation for cost-sensitive SVM. Next, Section IV describes the proposed EBCS-SVM. Section V details the datasets, reference methods, and performance measures, while Section VI presents the experimental results. Finally, Section VII discusses the main conclusions. II. Related Work This section presents the preliminaries. Section II-A describes the main approaches for imbalanced classification. Then, Section II-B describes the hyper-parameter optimization problem, and Section II-C presents the main concepts related to bilevel optimization. A. Methods for Imbalance Classification Most learning algorithms may face difficulties when dealing with imbalanced classification problems, as they can favor the majority class, leading to an ineffective classification model. Two main approaches to dealing with imbalanced datasets are sampling strategies and algorithm adaptation [2]–[4]. The former works with training data by modifying its class distribution, while the latter adjusts the training algorithm or inference process to consider the imbalance. We describe these two approaches below. 1) Data-Level Preprocessing Methods: This approach aims to reduce the effect of class imbalance by adding or removing samples from training data to balance the class distribution [34]. There are two primary sampling strategies: •Oversampling methods attempt to balance the dataset by replicating or creating samples from the minority class. Random oversampling (ROS) [3] is the simplest method for data balancing that replicates samples from the minority class. SMOTE [6] is a popular method for generating artificial samples through a linear interpolation of samples from the minority class. Variants of SMOTE include SVMSMOTE [7] and ADASYN [8]. The major criticism of oversampling methods is that the synthetic samples can cause overfitting of the classification model. •Undersampling methods balance the dataset by removing instances from the majority class. Random undersampling (RUS) [3] is an uninformed method that removes instances from the majority class at random. The condensed nearest neighbor (CNN) [9] is an informed method that eliminates examples distant from the boundary decision. The major criticism of undersampling methods is that they can discard meaningful instances and lead to loss of information. It is unclear whether oversampling is better than undersampling or vice versa [35], [36]. Both methods are effective in handling imbalanced classification problems. 2) Algorithm-Level Methods: This approach aims to adapt the way a particular classifier learns in such a manner that it can deal with imbalanced problems. For SVMs, there are three main approaches of adaptation: •Cost-sensitive methods consider different costs to each class during learning, such that minority class errors have a higher penalization than those of the majority class. SVMs can work in a cost-sensitive framework by using different regularization parameters for positive and negative samples [37]. Also, an 3 instance can be weighted based on the density of its neighborhood [38]. However, the proper setting of the costs is unknown. •Kernel adaptation methods adapt the kernel function or kernel matrix to reduce the bias towards the majority class. For example, WK-SMOTE [15] expands the kernel matrix by incorporating the dot products of artificial samples generated in the feature space. Then, the SVM training algorithm uses the modified kernel matrix to learn a model. •Hyper-plane shifting methods shift the separating hyper-plane to enlarge the margin around minority class [14]. The major criticism of the algorithm-level methods is that they are algorithm-specific and require in-depth knowledge of the classifier. However, these methods are more accurate than data-level methods [2]. B. Hyper-Parameter Optimization Hyper-parameter optimization refers to the problem of automatically setting the hyper-parameter configuration of a learning algorithm to optimize the performance. Hyper-parameter optimization is a complicated problem with several challenges. The challenges include computationally expensive evaluations of the objective function, a complex and non-convex search space, hyper-parameters that cannot be differentiable, and a finite amount of data that may limit the estimation of the generalization performance [39]. Formally, the hyper-parameter optimization problem can be stated as follows [39]: θ∗= arg min θ∈Θ EDtrain,Dval L(Aθ, Dtrain, Dval) (1) where L(Aθ, Dtrain, Dval) is a loss function that measures the loss of the model learned by algorithm Awith hyperparameters θthat is trained with Dtrain and is validated with Dval. Global optimization techniques are commonly adopted to face the non-convex nature of the hyper-parameter optimization problem. For SVMs, the works on hyperparameter optimization can be categorized into: •Model-free optimization includes classical techniques such as Grid Search [40], Random Search [40], Evolutionary Algorithms [41], [42], and Particle Swarm Optimization [21]. •Model-based optimization includes Bayesian optimization [43], [44] and surrogate-assisted optimization [27]. Works on SVMs hyper-parameter optimization have also considered the optimization of the model pipeline (data preprocessing + learning algorithm) [42], [45], the training set selection problem [28], [46], [47], or more recently a combination of feature and training set selection together with hyper-parameter optimization [48]. However, these studies neglected the imbalanced classification problem. C. Evolutionary Bilevel Optimization Bilevel optimization is a hierarchical optimization problem with two levels: the upper-level, also known as the leader, and the lower-level, also called the follower. Formally, a bilevel optimization problem is stated as follows [17], [18]: minfu(vu,vl) s.t. vl∈ {arg min fl(vu,vl:gl(vu,vl)≤0)} gu(vu,vl)≤0 (2) where vuand vlare the upper-level and the lower-level variables, respectively, fuand flrepresent the objective functions for the upper-level and lower-level, and guand glare the set of constraints for upper-level and lower-level, respectively. The lower-level is a constraint to the upper-level optimization problem. Therefore, the lower-level solution partially determines the upper-level solution. The nested structure leads to several difficulties, such as non-linearity, non-convexity, and disconnectedness. These difficulties can be present even for the simplest bilevel problems [17], [18], [49]. EAs have shown success when dealing with complex optimization problems. Thus, EAs emerge as an alternative to deal with bilevel optimization problems. Most of the current EAs proposed to handle these problems are nested in nature. These approaches have two optimization algorithms, where one algorithm runs within the other. Overviews of evolutionary bilevel algorithms can be found in [17], [18]. Supervised learning can be treated as a bilevel problem, in which the upper-level optimizes the hyperparameters that minimize the expected generalization error, and the lower-level learns the parameters [50]. Next, we explain the bilevel formulation for learning parameters and hyperparameters for an SVM with cost-sensitive. III. Bilevel Cost-Sensitive Support Vector Machine: Optimization Problem The bilevel formulation breaks the problem down into two levels: the upper-level concerned with the hyperparameters configuration and the lower-level with the SVM training. In this section, we explain the optimization objectives at each level. First, Section III-A defines the lower-level that finds the optimal separating hyper-plane when training the SVM. Next, Section III-B explains the objective function for the upper-level, which optimizes the classification performance considering the uneven class distributions for a given hyper-parameter configuration. A. Lower-Level – Optimizing Parameters The lower-level problem focuses on finding the support vectors that define the hyper-plane for an imbalanced classification problem. A cost-sensitive SVM penalizes the errors differently for positive and negative classes. This is formulated as follows [37]: 4 min1 2kwk2+C+X i:y=1 ξi+C−X i:y=−1 ξi subject to yi(hw,xii+b)≥1−ξi ξi≥0 (3) where h·,·i represents the dot product, wis the separating hyper-plane, and C+and C−are the costs for the positive and negative samples, respectively. The dual problem obtained through Lagrange multipliers is as follows: max n X i=1 αi−1 2 n X i,j αiαjyiyjhxi,xji subject to n X i=1 yiαi= 0 0≤αi≤C+, i :y= +1 0≤αi≤C−, i :y=−1 (4) For learning nonlinear functions, the dot product hxi,xjiis replaced by a kernel function K(xi,xj). The Radial basis function (RBF) is a kernel function that is highly effective and theoretically supported [51], [52]. The RBF kernel is defined as: K(xi,xj)=e−γkxi−xjk2(5) where γis an adjustable parameter given by the upperlevel. Section III-B explains the upper-level optimization problem that optimizes the hyper-parameters C+,C−, and the γvalue for the RBF kernel. B. Upper-Level – Optimizing Hyper-Parameters The upper-level optimizes the hyper-parameters used in the lower-level to learn the support vectors. Let λbe a vector that encodes the hyper-parameters C+,C−, and γ. The goal of the upper-level is to find the set of hyperparameters that gets the minimum generalization error on imbalanced classification problems, which is estimated using the balanced error rate (BER) score. The BER is defined as: BER (λ, α∗, b) = 1 2F N T P +F N +F P F P +T N (6) where T P and T N are, respectively, the number of positive and negative samples correctly classified; and F N and F P are, respectively, the number of positive and negative samples incorrectly classified. Computing BER using the training set can lead to overfitting. K-fold cross-validation is commonly used to assess the expected performance and to reduce the risk of overfitting. However, this procedure can become computationally inefficient, as it implies solving the lower-level problem K times for each configuration of hyper-parameters λ. We face that disadvantage by approximating the bound on the leave-one-out cross-validation for the upper-level. Based on the lower-level solution α∗, the predicted value for the jth training sample is given by: f(xj) = n X i=1 α∗ iyiK(xj,xi) + b(7) where bis the bias term and is set to satisfy the KarushKuhn-Tucker condition. Eliminating a non-support vector from the training set does not affect the model; therefore, we focus on support vectors, as they can contribute to the error. Assuming that the set of support vectors remains the same during the leave-one-out procedure, we can approximate the output when removing the jth support vector from the training set as: ˆ f(xj) = n X i=1 α∗ iyiK(xj,xi) + b−α∗ jyjK(xj,xj) (8) In the case of the RBF kernel, the term K(xj,xj) equals one. Simplifying (8) and multiplying it by yj, an instance xjis incorrectly classified if: yj n X i=1 α∗ iyiK(xi,xj) + b−α∗ jyj!<0 (9) After determining the incorrectly classified instances with (9), the BER of each individual at the upper-level is determined using (6). After solving the bilevel optimization problem, the optimal support vectors are used to classify a new instance using (7). IV. EBCS-SVM: Evolutionary Bilevel Cost-Sensitive Support Vector Machines EBCS-SVM aims to build an optimal SVM model for handling imbalanced classification problems through bilevel optimization. EBCS-SVM determines the hyperparameters values, i.e., the costs of each class and the kernel parameters that minimize BER at the upper-level, and the lower-level finds the optimal separating hyperplane. Fig. 1 graphically depicts the bilevel interaction between the lower-level and upper-level in EBCS-SVM. Algorithm 1 describes EBCS-SVM, and it works as follows: 1) In line 1, a population for the upper-level is randomly created with usindividuals and three variables representing the costs for the positive and the negative class, and the γvalue for RBF kernel, based on the bounds given in Section IV-B. 2) In lines 2–5, each upper-level solution is evaluated. To this end, the following steps are carried out: a) The lower-level problem described in Section III-A is solved using the SMO algorithm and the given hyper-parameters. b) The resulting SVM model is evaluated by computing the BER, as described in Section III-B. 5 Upper-level: Hyper-parameters Lower-level: SVM training C+, C−, γ w, b Maximize margin Minimize BER Fig. 1: Bilevel scheme to learn support vectors machine in a cost-sensitive approach. The figure depicts the dependency between hyper-parameters and support vectors, optimizing the margin with different penalties. Algorithm 1 EBCS-SVM Require: X, the set of samples, y, the set of classes labels, us, upper population size, me, maximum number of evaluations at the upper-level, τ, tolerance threshold for lower-level, m, maximum number of iterations for lower-level. Ensure: The set of support vectors 1: Generate randomly an initial population of hyperparameters, Pu, with usindividuals 2: for each individual puin Pudo 3: Use SMO with the hyper-parameters defined in puto find the optimal support vectors. 4: Compute the BER for the upper-level individual using the optimal support vectors. 5: end for 6: while a stopping criterion is not met do 7: Apply evolutionary operator to produce an upper-level offspring population, Ou. 8: for each individual ouin Oudo 9: Find the nearest neighbors of ouin Pu. 10: Warm starting the set of support vectors of the lowerlevel based on the nearest neighbors. 11: Use SMO with the hyper-parameters defined in outo find the optimal support vectors. 12: Compute the BER for the upper-level offspring using the optimal support vectors. 13: end for 14: end while 15: Choose the solution with the lowest BER as the optimal SVM for handling imbalanced datasets. If there are more than one solution with similar BER to the lowest one, choose the one with the lower number of support vectors. 3) In lines 6–14, the evolutionary process takes place. a) In line 7, a new population of hyper-parameters is created by applying evolutionary operators over Puusing the adaptation of DE operators proposed by SHADE [53]. b) In line 9, the nearest neighbors in Puare found for each individual in Ou. In line 10, the set of support vectors for the lower-level is warm started by considering the nearest neighbors of the upper-level to determine how probable an instance is a support vector, as described in Section IV-A. c) Line 11 solves the lower-level optimization problem with the SMO algorithm and, line 12 computes the BER score for the given hyperparameters. A. Lower-level Initialization When solving the lower-level using the hyper-parameter of the initial upper-level population, all training instances are initially assumed to be a support vector, and the SMO solves the lower-level problem. The solutions obtained by the initial configuration of hyper-parameters are stored to perform a warm starting of the lower-level. The warm starting takes place after the first generation of the upper-level and works as follows. First, for a new given hyper-parameters configuration, its mnearestneighbors are found among the hyper-parameters from the current population. After, the set of support vectors is retrieved and used to determine the chance of an instance becoming a support vector, based on the relative frequency of its mnearest-neighbors. Finally, the SMO algorithm solves the lower-level based on previous initialization. The premise for using this initialization is that similar configurations of hyper-parameters lead to a similar set of support vectors. The value of mis determined during the search. For doing so, the number of neighbors is randomly selected between [1, us] with uniform probability. Then, the probability of each value of mis updated based on the normalized frequency of success of such value, i.e., an improvement in the BER score. 6 B. Representation and Evolutionary Operators At the upper-level, individuals encode the hyperparameters as a real-value vector. Initially, C+and C−are randomly generated in the range 2−5,210and γbetween 2−10,25. Individuals at this level are then evolved using DE [54], [55]. However, the classical DE requires the definition of two parameters: the differential weights (F) and the crossover rate (CR). For this reason, we adopt a self-adaptative variant called SHADE [53], which uses history information to adapt the values of Fand CR during the search and a greedy current-to-best mutation strategy. Therefore, these parameters are learned during the search. After a child solution of hyper-parameters is created and its BER value is computed, it competes with the current individual to determine which one is better and therefore survives. A child solution is better if its BER value is lower than the BER value of the current individual, or if the BER values of both solutions are equivalent, but the child has fewer support vectors. V. Experimental Settings In this section, we describe the configuration setup for our experimental study. In Section V-A, we present the set of benchmark datasets considered for experimentation. Section V-B provides the metrics used to assess the performance of all methods and the test to analyze them. Finally, Section V-C details the state-of-the-art techniques used to compare the performance and their respective tuning of hyper-parameters. A. Datasets The performance of EBCS-SVM is assessed using a benchmark of 70 datasets from the KEEL repository [56]. Table I details the characteristics of the datasets, including the number of instances (Inst.), the number of features (Feat.), and the imbalance ratio (IR)2. These datasets are diverse in the IR, number of samples, and number of features. Thus, the performance is assessed using problems with different characteristics. We divided the datasets into three groups based on the degree of IR: ten datasets with small IR, i.e., the IR is less than or equal to three; 35 datasets with medium IR, that is an IR higher than three and less than or equal to 20; and 25 datasets with high IR, i.e., the IR is higher than 20. Datasets were partitioned using the 10 ×5-fold crossvalidation. In the 5-fold cross-validation, the dataset is randomly split into five disjoint subsets. In each fold, a subset is used as the test set and the remaining as the training set. Then, 5-fold cross-validation is repeated ten times, with a different split each time. Thus, each dataset is tested 50 times. 2IR is defined as the ratio between the number of samples in the majority class and the number of samples in the minority. Therefore, the higher the IR, the greater the imbalance. TABLE I: Description of datasets based on the number of instances (Inst.), number of features (Feat.), and the imbalance ratio (IR). ID Dataset Inst. Feat. IR Small IR 1 ecoli-0 vs 1 220 7 1.857 2 glass0 214 9 2.057 3 glass1 214 9 1.816 4 haberman 306 3 2.778 5 iris0 150 4 2.000 6 pima 768 8 1.866 7 vehicle1 846 18 1.029 8 vehicle2 846 18 2.881 9 vehicle3 846 18 1.029 10 wisconsin 683 9 1.858 Medium IR 11 abalone9-18 731 8 16.405 12 cleveland-0 vs 4 173 13 12.308 13 dermatology-6 358 34 16.900 14 ecoli-0-1-4-6 vs 5 280 6 13.000 15 ecoli-0-1-4-7 vs 2-3-5-6 336 7 10.586 16 ecoli-0-1-4-7 vs 5-6 332 6 12.280 17 ecoli-0-1 vs 2-3-5 244 7 9.167 18 ecoli-0-3-4-7 vs 5-6 257 7 9.280 19 ecoli-0-3-4 vs 5 200 7 9.000 20 ecoli-0-6-7 vs 5 220 6 10.000 21 ecoli1 336 7 3.364 22 ecoli2 336 7 5.462 23 ecoli3 336 7 8.600 24 ecoli4 336 7 15.800 25 glass-0-1-2-3 vs 4-5-6 214 9 3.196 26 glass-0-1-5 vs 2 172 9 9.118 27 glass-0-1-6 vs 5 184 9 19.444 28 glass-0-4 vs 5 92 9 9.222 29 glass-0-6 vs 5 108 9 11.000 30 glass2 214 9 11.588 31 glass4 214 9 15.462 32 glass6 214 9 6.379 33 led7digit-0-2-4-5-6-7-8-9 vs 1 443 7 8.630 34 new-thyroid1 215 5 5.143 35 newthyroid2 215 5 5.143 36 page-blocks-1-3 vs 4 472 10 15.857 37 segment0 2308 19 6.015 38 shuttle-c0-vs-c4 1829 9 13.870 39 vehicle0 846 18 3.251 40 vowel0 988 13 9.978 41 yeast-0-3-5-9 vs 7-8 506 8 9.120 42 yeast-0-5-6-7-9 vs 4 528 8 9.353 43 yeast-1 vs 7 459 7 14.300 44 yeast-2 vs 4 514 8 9.078 45 yeast3 1484 8 8.104 High IR 46 abalone-17 vs 7-8-9-10 2338 8 39.310 47 abalone-20 vs 8-9-10 1916 8 72.692 48 abalone-21 vs 8 581 8 40.500 49 abalone-3 vs 11 502 8 32.467 50 abalone19 4174 8 129.438 51 car-good 1728 6 24.043 52 flare-F 1066 11 23.791 53 glass5 214 9 22.778 54 poker-8-9 vs 5 2075 10 82.000 55 poker-8-9 vs 6 1485 10 58.400 56 poker-8 vs 6 1477 10 85.882 57 poker-9 vs 7 244 10 29.500 58 shuttle-6 vs 2-3 230 9 22.000 59 winequality-red-3 vs 5 691 11 68.100 60 winequality-red-4 1599 11 29.170 61 winequality-red-8 vs 6-7 855 11 46.500 62 winequality-red-8 vs 6 656 11 35.444 63 winequality-white-3-9 vs 5 1482 11 58.280 64 winequality-white-3 vs 7 900 11 44.000 65 yeast-1-2-8-9 vs 7 947 8 30.567 66 yeast-1-4-5-8 vs 7 693 8 22.100 67 yeast-2 vs 8 482 8 23.100 68 yeast4 1484 8 28.098 69 yeast5 1484 8 32.727 70 yeast6 1484 8 41.400 7 B. Performance Metrics and Statistical Tests We assessed the performance of the methods using a set of metrics well-suited for imbalanced classification problems [57]. Let sensitivity (sen) and specificity (spe) be defined as: sen =T P T P +F N spe =T N T N +F P (10) where T P and T N are, respectively, the number of positive and negative samples correctly classified; and F N and F P are, respectively, the number of positive and negative samples incorrectly classified. The metrics described in [57] can be defined in terms of specificity and sensitivity. These metrics are listed below: •BAR, the balanced accuracy rate is equivalent to 1BER and is defined as the average between sensitivity and specificity, i.e., BAR = 1 2(sen +spe) (11) •BMI, the bookmarker informedness is defined as the sum of sensitivity and specificity minus one, i.e., BMI = sen +spe −1 (12) •GM indicates the geometric mean between sensitivity and specificity, i.e., GM = √sen ·spe (13) •uF1 [57] is the unbiased version of the F1 score and is defined as two times the sensitivity between the sum of two plus sensitivity minus specificity, i.e., uF1 = 2·sen 2 + sen −spe (14) •uMCC [57] is the unbiased version of the Matthews correlation coefficient, and is defined as follows: uMCC = sen ·spe −1 q1−(sen −spe)2(15) The Bayesian hypothesis tests are used to analyze EBCS-SVM regarding reference methods. They allow comparing the difference in the results achieved by two algorithms, estimating the posterior probabilities that one algorithm is better than the other and that both are practically equivalent. These tests are not affected by the number of datasets. Moreover, they can provide more information than the null hypothesis significance test, even when the latter does not reject the null hypothesis [58], [59]. We used the hierarchical Bayesian test to analyze the results, as it considers both the mean and the variance through the cross-validation partitions for each dataset. In the analysis, we considered that two methods are equivalent if the difference is below 0.01. C. Reference Methods We compared EBCS-SVM with several state-of-theart techniques for imbalanced classification. To this end, we considered methods for both data-level preprocessing and algorithm-level. Specifically, the comparative study considers the following methods. •SVM. The standard SVM (BL) is used on the dataset without preprocessing or modification to weight the class distributions. •Data-level methods (DL). The methods in this group are used to preprocess the data. Then, the edited dataset is used to train an SVM. This group consists of ROS [3], SMOTE [6], SVMSMOTE [7], RUS [3], and CNN [9]. •Algorithm-level methods (AL). This group encompasses SVMDC [37], uNBSVM [14], WKSMOTE [15], CSSVM [60], and RBI-LP-SVM [16]. Reference methods require defining a set of hyperparameters to use in training. Properly selecting hyperparameters is a crucial step to compare classification algorithms [51], [61]. We adopted the RBF kernel because of its effectiveness with SVM. For the sake of a fair comparison, the hyper-parameters of each method were optimized for each dataset independently by optimizing the BER, computed through an internal stratified 5-fold cross-validation on the training set. The set of hyper-parameters includes: the γvalue optimized in the range of 2−10,25for all methods; the regularization parameter Cin the range of 2−5,210for SVM, data-level methods, and CSSVM; the regularization parameter for positive (C+) and negative (C−) class optimized between 2−5,210for both WKSMOTE and SVMDC; the regularization parameter for synthetic samples (Cs) optimized between 2−5,210for WK-SMOTE; the weight factor for positive (ωp) and negative (ωn) class in the range of [0,1] for uNBSVM; the cost-sensitive parameter (κ) ranges from zero to one and the margin violation weight (C1) is the range of [1,10] for CSSVM; the amount of sampling is searched in the range of hnm+1 nM,1i, with nmand nMas the number of samples in the minority and majority class, respectively, for data-level methods and WK-SMOTE, and the number of neighbors is between 1,nm 2for SMOTE, SVMSMOTE, and WKSMOTE. SHADE was also used to optimize the hyperparameters, which ran with a population size equals to 30 and the stopping criteria considered performing 1,000 fitness function evaluations or that the standard deviation of fitness values of the population is below 0.001. We provide the implementation of EBCS-SVM, datasets, splits, and detailed results in each partition as supplementary material. The supplementary material can be downloaded at www.cimat.mx/∼alejandro.rosales/ resources/EBCSSVM.tar.gz. VI. Experimental Results and Discussion This section presents the experimental results reported by EBCS-SVM and reference methods. Section VI-A shows the results obtained with datasets with small IR. 8 Next, Section VI-B considers the 35 datasets with medium IR, and Section VI-C presents the results using the 25 datasets with high IR. Finally, Section VI-D compares the training time required by each method. A. Experiments on Small Imbalance Ratio In this section, we focused on comparing the performance of EBCS-SVM against reference methods. Table I shows the results on the ten datasets with a small IR. The reported results correspond to the average and standard deviations for BAR, BMI, GM, uF1, and uMCC scores. Fig. 2 graphically depicts barycenter plots for the posterior probabilities reported by the hierarchical Bayesian test for the BAR score. Each point on the barycenter plot represents an estimate of the probability that it belongs to each region. Based on the results and the analysis carried out by the hierarchical Bayesian test, the following observations are highlighted: •Most methods showed a competitive performance when dealing with small IR. •For metrics BAR, GM, and uF1, most methods reported scores above 0.820. The exceptions were WKSMOTE and RBI-LP-SVM, which obtained performances below 0.800. On the other hand, for metrics BMI and MCC, most methods reported scores above 0.710, except for WK-SMOTE, nNBSVM, and RBILP-SVM. •CSSVM obtained the highest performance in all metrics. SVMDC was the second-best position for BAR, BMI, GM, and uMCC, and the third-best for uF1. On the other hand, EBCS-SVM ranked second-best for uF1; it was in the seventh position for BAR, BMI, and uMCC; and in the eighth position for GM. •The hierarchical Bayesian tests provided strong evidence on the practical equivalence between CSSVM and EBC-SVM. We can observe similar behavior when EBCS-SVM is compared with SVM, ROS, SMOTE, SVMSMOTE, RUS, CNN, and SVMDC. Thus, EBCS-SVM exhibited a performance practically similar to that of CSSVM, the best-ranked method. •Among data-level methods, ROS had the best average performance over the ten datasets with a small IR for BAR, BMI, GM, and uMCC, while for uF1 CNN was the best data-level approach. Conversely, CNN was the worst data-level method for BAR, DMI, GM, and uMCC, while SVMSMOTE was the worst for uF1. •RBI-LP-SVM showed the lowest performance among algorithm-level methods. The hierarchical Bayesian test reported probabilities above 0.999 in the region of EBCS-SVM for all metrics. •Algorithm-level methods generally reported better performance than data-level methods. EBCS-SVM, uNBSVM, CSSVM, and ROS were highly effective methods to classify problems with a small IR. In the next section, we delved into our analysis when the IR increases. B. Experiments with Medium Imbalance Ratio In this section, we analyzed the performance of EBCSSVM and reference methods when using the 35 benchmark datasets with medium IR. Table II presents the average results obtained by each method, and Fig. 3 shows the posterior plots for the BAR score when EBCS-SVM is compared with reference methods. From these, the following is pointed out: •Most methods reported results above 0.800 for BAR, GM, and uF1 scores, except for SVM for GM and uF1; WK-SMOTE for BAR, GM, and uF1; uNBSVM for GM and uF1; and RBI-LP-SVM for BAR, GM, and uF1. •Regarding BMI and uMCC, most methods reported performances above 0.700. The exceptions were SVM for BMI and WK-SMOTE, uNBSVM, and RBI-LPSVM for BMI and uMCC. •ROS achieved the highest performance for BAR, BMI, GM, and uMCC and the second-best performance for uF1. RUS achieved the best performance for uF1 and the second-best performance for BAR, BMI, GM, and MCC. EBCS-SVM ranked the third-best for all metrics. •The hierarchical Bayesian analysis revealed a probability above 0.900 in the region of practical equivalence when EBCS-SVM was compared with ROS, SMOTE, SVMSMOTE, and RUS for all metrics. Thus, there is evidence in favor of the competitiveness of these methods for handling medium IR problems. We can observe this behavior in Fig. 3, where we can note that the center mass is in the region of practical equivalence. Although for CNN and SVMDC, the center mass fell in the practically equivalent region, the posterior plot distribution was spread throughout the area of EBCS-SVM, providing at some extent evidence in favor of EBCS-SVM. •ROS stood out as the most effective data-level method. •Among algorithm-level methods, EBCS-SVM obtained the best performance, and CSSVM was the second-best. Conversely, RBI-LP-SVM ranked in the last position. For datasets with a medium IR, EBCS-SVM, ROS, and RUS were the most superior methods. ROS is highlighted as a prominent method for problems with medium IR. CSSVM remained a competitive method. In the next section, methods are evaluated when handling datasets with a high IR. C. Experiments with High Imbalance Ratio In this section, we considered the 25 datasets with an IR above 20 to analyze the performance of EBCS-SVM and reference methods. Table III reports the average results for all metrics, and Fig. 4 shows the posterior probabilities obtained with the hierarchical Bayesian test. Based on these results, we remark the following: 9 TABLE I: Obtained results on small IR datasets for BAR, BMI, GM, uF1, and uMCC scores. Fam. Method BAR BMI GM uF1 uMCC BL SVM 0.8626 ±0.1461 0.7251 ±0.2922 0.8494 ±0.1651 0.8312 ±0.1904 0.7343 ±0.2831 DL ROS 0.8726 ±0.1321 0.7452 ±0.2643 0.8643 ±0.1430 0.8515 ±0.1600 0.7528 ±0.2554 DL SMOTE 0.8719 ±0.1328 0.7439 ±0.2656 0.8632 ±0.1447 0.8502 ±0.1628 0.7512 ±0.2569 DL SVMSMOTE 0.8723 ±0.1345 0.7447 ±0.2690 0.8627 ±0.1487 0.8499 ±0.1681 0.7519 ±0.2601 DL RUS 0.8712 ±0.1335 0.7424 ±0.2670 0.8636 ±0.1442 0.8548 ±0.1560 0.7489 ±0.2593 DL CNN 0.8688 ±0.1345 0.7377 ±0.2690 0.8616 ±0.1448 0.8586 ±0.1506 0.7441 ±0.2613 AL SVMDC 0.8730 ±0.1324 0.7460 ±0.2649 0.8644 ±0.1446 0.8552 ±0.1570 0.7529 ±0.2569 AL CSSVM 0.8740 ±0.1267 0.7480 ±0.2533 0.8689 ±0.1327 0.8674 ±0.1357 0.7535 ±0.2481 AL WK-SMOTE 0.7322 ±0.1137 0.4643 ±0.2275 0.6194 ±0.1743 0.5753 ±0.1930 0.5069 ±0.2181 AL uNBSVM 0.8419 ±0.1325 0.6839 ±0.2650 0.8257 ±0.1479 0.8415 ±0.1310 0.6960 ±0.2582 AL RBI-LP-SVM 0.5293 ±0.0568 0.0587 ±0.1136 0.0676 ±0.1136 0.6724 ±0.0474 0.0604 ±0.1135 AL EBCS-SVM 0.8696 ±0.1310 0.7391 ±0.2619 0.8585 ±0.1473 0.8622 ±0.1419 0.7468 ±0.2536 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 0.9975 pC1= 0.0020 pC2= 0.0005 (a) SVM – EBC-SVM 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 0.9970 pC1= 0.0000 pC2= 0.0030 (b) ROS – EBC-SVM 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 0.9960 pC1= 0.0000 pC2= 0.0040 (c) SMOTE – EBC-SVM 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 0.9975 pC1= 0.0015 pC2= 0.0010 (d) SVMSMOTE – EBC-SVM 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 0.9995 pC1= 0.0000 pC2= 0.0005 (e) RUS – EBC-SVM 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 1.0000 pC1= 0.0000 pC2= 0.0000 (f) CNN – EBC-SVM 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 0.9955 pC1= 0.0000 pC2= 0.0045 (g) SVMDC – EBC-SVM 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 0.9985 pC1= 0.0000 pC2= 0.0015 (h) CSSVM – EBC-SVM 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 0.5760 pC1= 0.4230 pC2= 0.0010 (i) uNBSVM 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 0.0000 pC1= 0.9995 pC2= 0.0005 (j) WK-SMOTE – EBC-SVM 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 prope = 0.0000 pC1= 1.0000 pC2= 0.0000 (k) RBI-LP-SVM – EBC-SVM Fig. 2: Posterior distribution for BAR when comparing EBCS-SVM with the reference methods on small IR datasets. The region of the bottom-left represents EBCS-SVM, the region at the top is for rope, and the region in the bottom-right represents the reference method. •EBCS-SVM excelled in dealing effectively with highly imbalanced datasets in all metrics. Ergo, the superiority of EBCS-SVM is stressed when the IR is increased. •Among data-level methods, RUS had the best score in all metrics and ranked second-best position globally. ROS was the second-best data-level method and ranked third-best position globally. •Among algorithm-level methods, EBCS-SVM was the best one, followed by SVMDC. However, when observing the posterior probabilities reported by the hierarchical Bayesian test, we noted that the center mass is in the region of EBCS-SVM. Furthermore, the posterior odds revealed strong evidence in favor of EBCS-SVM. We observed this behavior for all metrics. •Posterior probabilities plots also showed that, for most reference methods, the center mass fell in the region of EBCS-SVM. The exception was RUS, whose center mass is in the region of practical equivalence; however, its distribution spreads in the regions of both EBCS-SVM and RUS. As the IR increased, the performance of EBCS-SVM stood out over the reference methods, regardless of the adopted metric. The hierarchical Bayesian test reported high probabilities in favor of EBCS-SVM that supported these observations. D. Computational Time In this section, we analyze the training time for each method. We used the performance profile [62], which represents the cumulative distribution on a performance metric. The performance profile is constructed for the necessary training time required by each method to optimize the hyper-parameters and learn the classification model. Fig. 5 depicts the performance profile for all methods. The y−axis represents the probability (ρ(τ)) that a method can learn a model within a factor τtimes the