Binarized support vector machines

Binarized Support Vector Machines ∗ Emilio Carrizosa Universidad de Sevilla (Spain). [email protected] Bel´ en Mart ´ ın-Barrag´ an Universidad Carlos III de Madrid (Spain). [email protected] Dolores Romero Morales University of Oxford (United Kingdom). dolores.romero-mo[email protected] July 28, 2008 Abstract The widely used Support Vector Machine (SVM) method has shown to yield very good results in Supervised Classification problems. Other methods such as Classification Trees have become more popular among practitioners than SVM thanks to their interpretability, which is an important issue in Data Mining. In this work, we propose an SVM-based method that automatically detects the most important predictor variables, and the role they play in the classifier. In particular, the proposed method is able to detect those values and intervals which are critical for the classification. The method involves the optimization of a Linear Programming problem with a large number of decision variables. The numerical experience reported shows that a rather direct use of the standard Column-Generation strategy leads to a classification method which, in terms of classification ability, is competitive against the standard linear SVM and Classification Trees. Moreover, the proposed method is robust, i.e., it is stable in the presence of outliers and invariant to change of scale or ∗This work has been partially supported by projects MTM2005-09362-C03-01 of MEC, Spain, and FQM-329 of Junta de Andaluc´ıa, Spain. 1 measurement units of the predictor variables. When the complexity of the classifier is an important issue, a wrapper feature selection method is applied, yielding simpler, still competitive, classifiers. Keywords: Supervised Classification, Binarization, Column Generation, Support Vector Machines. 1 Introduction and literature review Classifying objects or individuals into different classes or groups is one of the aims of Data Mining. This topic has been addressed in different areas such as Statistics, Operations Research and Artificial Intelligence. A general introduction of Data Mining can be found in [19]. We focus on the well-known so-called Supervised Classification problem, usually referred as Discriminant Analysis by statisticians, where we have a set of objects Ω and the aim is to build a classification rule which predicts the class membership cuof an object uinto one of a predefined set of classes C, by means of its predictor vector xu.The predictor vector xtakes values in a set Xwhich is usually assumed to be a subset of IRp,such as {0,1}p, and the components x`, ` = 1,2, . . . , p, of the predictor vector xare called predictor variables. The other piece of information defining uis the class cuobject ubelongs. In this paper we restrict ourselves to the case in which two classes exist, C={−1,1},since the multiclass case can be reduced to a series of two-class problems, as has been suggested e.g. in [20, 22, 35]. Not all the information about the objects in Ω is available, but only in a subset I, called the training sample, where both predictor vector and class-membership of the objects are known. With this information, the classification rule must be built. The Support Vector Machines (SVM) [12] approach is based on margin maximization, which consists in finding the separating hyperplane which is furthest from the closest object. SVM has shown to be a very powerful tool for Supervised Classification. The most popular versions of SVM embed, via a kernel function, the original predictor variables into a higher (possibly infinite) dimensional space, [22]. In this way one obtains classifiers with good generalization properties but, in general, hard to interpret. 2 In some application fields, practitioners, such as doctors or businessmen, may be very unwilling to use a classifier they cannot interpret. For them, Data Mining methods sometimes proceed like a black-box, so they would not feel confident enough to use the classifier unless they can interpret it somehow. For instance, it is easy to interpret and manage queries of type •Is predictor variable `1big? •Is predictor variable `2small? •Does predictor variable `3attain a very extreme value? where the concept of ‘big’, ‘small’ and ‘extreme value’ must be quantified, e.g. in the form is predictor variable `greater than or equal to b? (1) This type of queries are used e.g. in Classification Trees. Because of its very intuitive graphical display, practitioners can interpret the classifier, describing how it works. Moreover, they can detect the values of a predictor variable critical for the classification. We work in this paper in an SVM-based framework, where the feature space is defined by binarizing each predictor variable, i.e., by transforming each numerical predictor variable `into a large series of binary variables, obtained by making queries of type (1) for many different cutoffs b. Since we are using SVM after binarizing the predictor variables, we call our method Binarized Support Vector Machines (BSVM). Our aim is to show that, if SVM is run after such binarization, the resulting classifier has valuable properties concerning classification ability, interpretability and robustness. First, the numerical experience reported in Section 4 shows that BSVM yields lower misclassification rates than Classification Trees and is competitive (better in most cases we tested) against linear SVM. Second, BSVM takes us a step forward towards interpretability of SVMs. Since the obtained classification rule is based on queries of type (1), the critical values and intervals of the predictor variables are identified, as done by Classification Trees. 3 Third, BSVM is linear, in the sense it yields a classification rule which is linear in the features selected, and can be seen as a linear SVM after transforming the variables via a nonlinear mapping. Such mapping, which can be visualized by means of a graphical procedure, is valuable in terms of interpretability, since it shows the way each predictor variable influences the classifier. The capability of BSVM to capture nonlinearities presents an advantage with respect to the standard linear SVM, with important consequences in the classification ability, as shown in our numerical results. Finally, the use of queries of type (1) in our method makes it appealing in terms of robustness against outliers and changes of scale in the data. The numerical experience reported shows that our procedure behaves as Classification Trees, and clearly better than linear SVMs in presence of outliers. Moreover, whereas the linear SVM is influenced by the scale in the data – even a linear change of scale in the predictor variables may change the classifier and thus the classification ability of the SVM methodology– our proposal yields a classifier which is invariant to change of scale, in the sense that, if the data were modified by a monotonic (non-)linear transformation, the classifier obtained would be the same. The idea of binarizing continuous predictor variables is not new at all in the field of Classification. Indeed, Classification Trees are precisely based on the strategy of defining, for different predictor variables, appropriate cutoffs; moreover, binarizing is also natural in other classification procedures, such as Neural Networks, where the well-known step activation function, already at the heart of the perceptron method, allows one to discretize any predictor variable or combination of them. Binarizing continuous predictor variables has also been proposed in the so-called rule extraction procedures, within SVM [3, 4, 16, 27, 29] and Neural Networks as well, e.g. [1, 2, 13]. When a rule extraction method is applied to a classifier, one obtains an alternative classifier which hopefully have a similar behavior on data, but is more interpretable, since it is based on simple rules, such as those derived from queries of type (1). Whereas our method shares with rule extraction procedures the aim of enhancing interpretability of the output of an SVM, we are not proposing to replace the SVM classifier by a more interpretable one which, based on queries of type (1), mimics the behavior of the SVM classifier; instead, we are proposing a binarization in the data, via queries of type (1) and obtaining the SVM classifier for such transformed data. This way, we increase 4 interpretability with respect to standard SVM, and, as shown in our numerical experience, provide a competitive method in terms of misclassification rates. As far as we are aware, there is no paper using this way binarization for Support Vector Machines, and thus our strategy is new in the context of SVM. The classifier proposed in this paper, BSVM, is described in Section 2, where we analyze the interpretability of the proposed method, and propose a visualization tool for plotting the role a predictor variable plays in the classifier. Since the number of features to be considered may be huge, the BSVM method yields an optimization problem with a large number of decision variables. In Section 3, a Column-Generation-based algorithm is proposed in order to solve such an optimization problem. Numerical results are presented in Section 4, to illustrate the classification ability as well as the desirable properties of BSVM, showing that the proposed approach gives a classifier which is competitive against the standard linear SVM or Classification Trees. Conclusions and some lines for future research are discussed in Section 5. 2 Binarized Support Vector Machines Queries of type (1) are simple and hence are, by themselves, easy to interpret. In Section 2.1, we introduce a classifier which is made up by queries of this type. We propose in Section 2.2 a visualization tool which graphically represents the role any original predictor variable plays in the classifier. The search of a good classifier is based on SVM ideas, as described in Section 2.3. 2.1 Using simple queries In practical applications, simple classification rules based on queries of type (1) are very desirable because of their interpretability. For example, a doctor would say that having high blood pressure is a symptom of disease. Choosing the threshold bfrom which a specific blood pressure would be considered high is not usually an easy task. 5 We theoretically consider all the possible queries of type (1), mathematically formalized by the function φ`b(x) =        1 if x`≥b 0 otherwise (2) for b∈IR and `= 1,2, . . . , p. In what follows, each function of type φ`b is called feature. Our method constructs a classifier after binarizing all predictor variables. This binarization procedure could be done in a tedious preprocessing step, where all the possible features are created. Instead, as will be seen later, we propose a method to generate, by means of a dynamic process, only those features which are more promising in terms of classification ability. The set of possible cutoff values b(and, thus the number of features) is, in principle, infinite. However, given a training sample I, many of those possible cutoffs will yield exactly the same classification in the objects in I, which are the objects whose information is available. In this sense, given the training sample I, for any given predictor variable `, all values of bbetween two consecutive values of `lead to functions φ`b which behave identically on the training sample I. Hence, if we construct for each predictor variable `, the finite set B`of midpoints between consecutive values of `in the training sample I, it turns out that the set of functions {φ`b :b∈B`}is, on I, as rich as the full set of step functions {φ`b :b∈IR}.Instead of working with the full set of functions defined by all possible cutoffs b∈IR, the family of features under consideration in this paper is given by F={φ`b :b∈B`, ` = 1,2, . . . , p}. These features are used to classify in the following way: each feature φ`b has associated a weight ω`b,measuring its contribution for the classification into the class −1 or 1.The weighted sum of those features plus a threshold β constitute the score function, f(x) = ω>Φ(x) + β= p X `=1 X {b∈B`|x`≥b} ω`b +β, (3) where Φ(x) = (φ`b(x))b∈B`, `=1,2,...,p and ω>Φ(x) denotes the scalar product of vectors ωand Φ(x), ω>Φ(x) = Pp `=1 Pb∈B`ω`bφ`b(x) = Pp `=1 P{b∈B`|x`≥b}ω`b. Objects will be allocated to class −1 if f(x)<0,and to class 1 if f(x)>0.In case of ties, i.e. f(x) = 0,objects 6 can be allocated randomly or by some predefined order. In this paper, following a worst case approach, they will be considered as misclassified. For a certain predictor variable `, the coefficient ω`b associated to feature φ`b represents the amount with which the query ‘is x`≥b?’ contributes to the score function (3). Those predictor variables `for which ω`b are zero for all b∈B`are not needed for the classification, and can be discarded. In other words, only those values bfor which the corresponding ω`b are non-zero can be considered as critical values, in terms of classification, in the predictor variable `. Moreover, the magnitude of ω`b enables us to quantify the importance of the cutoff point bto separate individuals of class 1 and −1. To fix ideas, let us consider, for instance, the Wisconsin Breast Cancer Database from the UCI Machine Learning Repository, [28], with data from cancer diagnosis. Each individual has 30 predictor variables, which, in principle, are to be taken into consideration. However, if we use BSVM, it turns out that only some of these predictor variables are shown to be relevant for the classification. In particular, with a specific choice of the parameter in our model, only 12 have at least one non-zero ω`b,and are thus those which need to be taken into account. Tables 1 and 2 focus on two of these relevant predictor variables, namely Mean Concave Points and Worst Radius. For instance, for predictor variable Mean Concave Points and cutoff b= 0.0514,the weight is 0.514. For predictor variable Worst Radius, the only cutoff is b= 17.72,and has a weight of 0.1006. Since the output of the features proposed in this paper is always binary, the importance represented by the coefficient is always measured in the same scale. This means that having Mean Concave Points greater than or equal to 0.0514 is more important for the classification than having Worst Radius greater than or equal to 17.72. Moreover, for predictor variable Worst Radius, the only important issue for classification purposes is whether this variable takes a value greater than or equal to its unique critical value, namely, 17.72. In contrast, for variable Mean Concave Points other cutoffs are also used in the classifier. 2.2 Visualization tool The weight ω`b gives insightful knowledge about how predictor variable `together with the cutoff binfluences the classification. In this section, we focus on the influence of predictor variable `as a whole, instead of a particular 7 b ω`b 0.0492 0.0279 0.0514 0.5140 0.0559 0.0615 Table 1: Cutoffs and weights for predictor variable Mean Concave Points. b ω`b 17.720 0.1006 Table 2: Cutoffs and weights for predictor variable Worst Radius. cutoff. The role of predictor variable `in the score function is modeled by the stepwise function s7→ X {b∈B`|s≥b} ω`b.(4) This stepwise function is useful since it approximates the most adequate mapping to be applied to predictor variable `to optimize the classification task. As an illustration, Table 3 shows, for predictor variable Worst Texture, its cutoffs b, the corresponding weights ω`b and the cumulative weights Pb0≤bω`b0. b ω`b Pb0≤bω`b0 20.845 0.1117 0.1117 22.860 0.1508 0.2626 25.725 0.2514 0.5140 27.530 0.0279 0.5419 Table 3: Weights and cumulative weights for predictor variable Worst Texture. We propose a plot of function (4) in order to gain insight about the contribution of predictor variable `to the classifier. This plot is a valuable tool to practitioners, who can use it to interpret the classifier, describing the role every predictor variable plays in the classification. In particular, it allows a direct choice of the relevant predictor variables, and detection of critical values and intervals. In Figure 1 we show, for each of the 12 relevant predictor variables, i.e., those with at least one non-zero ω`b,its 8 contribution to the score function. Predictor variables Mean Concave Points,Worst Area and Worst Concave Points are the most important, whereas Worst Texture and Worst Perimeter have a medium importance. Using this graphical representation, in predictor variable Mean Concave Points, we can detect a critical value which, as said in the previous section, is at point 0.0514. In the case of Worst Texture, in the interval between 21 and 27 the importance of this predictor variable grows up little by little, whereas outside this interval it remains constant. We can say that in this case we have a critical interval instead of a critical cutoff. We have also plotted in Figure 1 the median (represented by a star) and the mean (represented by a cross). It can be seen how, although the mean or the median are sometimes a good choice for the cutoff, this does not happen in general, and BSVM prefers other choices. Figure 1: Contribution of predictor variables 9 (6-F0) is solved for such initial set of features. The dual values of the optimal solution found, are used to generate new features. In every step of the column generation algorithm, instead of generating just one feature (the one maximizing |Γ(φ)|),we generate two features for every predictor variable `, given by the cutoffs b+ `,b− `for which Γ(φ`b) is respectively maximal and minimal. This is done using Algorithm 1, as described in Section 3.2. We do it for all the predictor variables, thus obtaining 2pfeatures. Those generated features having |Γ(φ)|>1 are added to F and the LP problem (6-F) is solved. These steps are repeated until all the generated features have |Γ(φ)| ≤ 1,in which case, we have found an optimal solution of Problem (6). A summary of this Column Generation Algorithm is described as follows. Algorithm for Column Generation. Step 0. Set F0← {φ1b∗ 1, φ2b∗ 2, . . . , φpb∗ p},where b∗ `is the median of the predictor variable `, for `= 1,2, . . . , p. Set F←F0. Step 1. Solve Problem (6-F). Let (ω∗, β∗) be its optimal solution, with dual values λ∗ u,∀u∈I. Step 2. For each `= 1,2, . . . , p do: Step 2.1. Run Algorithm 1 to choose b+ `and b− `. Step 2.2. If Γ(φ`b+ `)>1,then set F←F∪ {φ`b+ `}. Step 2.3. If Γ(φ`b− `)<−1,then set F←F∪ {φ`b− `}. Step 3. If Fhas been modified, then go to Step 1, otherwise STOP: we have found an optimal solution of Problem (6). In Step 1, we need to solve the LP problem (6-F). In our numerical results we have used CPLEX 8.1.0 as the LP solver. Our numerical experience shows that the number of features used by our classifier, i.e., the ones that have been generated by the BSVM and have non-zero coefficient in the classifier, is usually rather large. In order to obtain 16 a more simple classifier, we proceed with a wrapper feature selection procedure in which features are recursively deleted. In this procedure, which has been successfully applied in standard SVM, see [18], all the generated features with zero coefficient in the classifier as well as the feature with non-zero coefficient having the smallest absolute value are eliminated. Then, the coefficients are recomputed by the optimization of the Problem (6). This elimination procedure is repeated until the number of features with non-zero coefficient is below a number given in advance. As reported in our numerical experience in Section 4.5, this procedure typically allows one to reduce the number of features used in the classifier at the expense of a mild loss in the classification ability. 4 Numerical results 4.1 Databases, benchmarking methods and accuracy measure In this section we illustrate the classification ability as well as the most desirable properties of BSVM. With this aim, a series of numerical experiments has been performed using databases publicly available from the UCI Machine Learning Repository [28]. Nine different databases were used, namely, the Sonar Database, called here sonar; the Cylinder Bands Database, called here bands; the Credit Screening Database, called here credit; the Ionosphere Database, called here ionosphere; the New Diagnostic Database, contained in the Wisconsin Breast Cancer Databases, called here wdbc; the Cleveland Clinic Foundation Database, called here cleveland; the Boston Housing Database, called here housing; the Pima Indians Diabetes Database, called here pima; and the BUPA Liver-disorders Database, called here bupa. In case of existence of missing values, as occurs for instance in bands and credit, objects with missing values were removed from the database. In databases such as bands and credit, some of the predictor variables were nominal. Each of these predictor variables has been replaced by a set of binary variables in the following way: for every possible value ˆxof the original nominal predictor variable `, a new binary variable is built taking value one when x`is equal to ˆxand zero otherwise. The housing database is a typical regression dataset, but it is often used as a classification dataset, where the class indicates whether the median value of houses exceeds $21,000. Finally, 17 for each database, the final number of objects and the number of predictor variables (all quantitative) can be found in the second column of each table. All databases used are of small/moderate size. Very large datasets do not seem to be so suitable for a crude implementation of BSVM, since column generation methods are known to be time-consuming. In practice, for databases of much larger size than those used in these experiments, it might be convenient to either select a subsample of data with manageable size, or perform some dimensionality reduction technique such as Principal Component Analysis to obtain an appropriate number of variables. In order to compare the BSVM classifier with other classifiers, we have tested the performance of three different benchmarking methods: Classification Trees, both with pruning (TreePr) and without pruning (TreeCr), linear SVM and a benchmarking method for the SVM with the L1norm regularization, namely, the NLPSVM proposed by Fung and Mangasarian in [15]. The classification accuracy of each method is measured by the leave-one-out correctness, as done in [15]. Below we give a brief description of this measure. In the leave-one-out correctness, in what follows looc, for each object, the training sample is equal to the whole database except for this object, while the testing sample is equal to the excluded object. For each training sample, we construct a classifier which will be applied in the corresponding testing sample, returning a 1 if the only object in the testing sample is correctly classified and 0 otherwise. The looc is equal to the percentage of correctly classified objects. Since looc uses all but one object to build the classifier, the provided classification can be expected to be close to the one of the classifier trained with the complete dataset. Given a training sample, it remains to specify the way the SVM as well as the BSVM classifiers are constructed. Problem (6), as well as the corresponding optimization problem for the linear SVM, contains a parameter that needs to be tuned, namely, the regularization parameter Cwhich trades off misclassification errors in the training sample with the generalization error. As in [15], we limit the values of this parameter to the values 2iwith i=−12,−11, . . . , 12. Parameter Cis then chosen so that it minimizes the misclassification rate after performing 10-fold cross-validation in the training data (which, as said before contains all but one object.) It has been empirically observed, e.g. [7, 11, 15], that the choice of the parameter Cmay strongly influence the number of features selected. Hence, one might have also chosen Cby balancing misclassification rates and number of features 18 selected. 4.2 Classification ability In Table 4 we report the looc of both Classification Trees, with and without pruning, linear SVM with normalized data, NLPSVM and BSVM. Note that for NLPSVM we only have results on five databases, the ones reported by Fung and Mangasarian [15] in their paper. From Table 4, we can see that BSVM outperforms the three benchmarking methods in six out of the nine databases we consider in this paper. This happens in the ionosphere, the housing and the bupa databases. For the sonar,credit and wdbc databases, Fung and Mangasarian [15] do not report any results, but BSVM outperforms Classification Trees and linear SVM. In these six databases, the increase in accuracy of BSVM with respect to the best reported accuracy, ranges from 0.35% for the wdbc database up to 12.01% for the sonar database. For the bands database, we are able to outperform Classification Trees, but not the linear SVM, which has an accuracy of 71.12% while we have 70.40%. Similarly, for the cleveland database, we are able to outperform Classification Trees, but linear SVM and NLPSVM have a better classification accuracy, 84.51% and 85.90% respectively, while the one of BSVM is 81.44%. For the pima database, BSVM underperforms the rest of the methods, where the decrease in accuracy of BSVM with respect to the best reported accuracy is equal to 4.44%. As a summary, we conclude that BSVM can be seen as a CART-like method (which may very good for practitioners, since relevant predictor variables and critical values of them are identified), with a classification power which is at least comparable, and in some cases much better than competing benchmarking techniques such as CART or other versions of SVM. 4.3 Interpretability Classification Trees are widely used in applied fields as diverse as Medicine (diagnosis), Computer Science (data structures), Botany (classification), and Psychology (decision theory), mainly because they are easy to interpret. Therefore, high accuracy is not the only desirable property of a classifier, but also its interpretability. BSVM improves largely the interpretability of standard SVMs by the use of queries of type (1). In this section we illustrate how our method takes us one step further towards interpretability via the use of the visualization tool 19 size TreePr TreeCr SVM NLPSVM BSVM sonar 208 ×60 71.63 65.38 78.37 - 90.38 bands 277 ×56 62.82 67.51 71.12 - 70.40 credit 653 ×43 86.22 83.31 85.91 - 87.75 ionosphere 351 ×34 89.17 86.32 84.90 88.00 92.31 wdbc 569 ×30 92.09 92.62 96.66 - 97.01 cleveland 297 ×13 78.79 68.69 84.51 85.90 81.44 housing 506 ×13 83.99 84.78 85.38 85.20 86.97 pima 768 ×8 76.43 72.92 76.17 77.10 72.66 bupa 345 ×6 67.83 66.67 69.28 68.80 74.78 Table 4: Looc for BSVM and benchmarking methods proposed in Section 2.2. To do this, we have considered two databases with different characteristics, namely bupa and sonar, which have respectively 6 and 60 predictor variables. Since the focus here is on interpretability, and not generalization ability, the whole database have been used to build the classifier. Parameter Chas been chosen by 10-fold cross-validation in the whole database. If SVM is performed, bupa uses all 6 predictor variables, i.e., all predictor variables have associated a non-zero weight. BSVM uses all 6 predictor variables as well, where we say that a predictor variable has been used if there exists at least one feature associated to this predictor variable which has a non-zero coefficient in the classifier. The total number of features used by BSVM is 62. A quick look at Figure 3, with information from bupa, allows us to say that predictor variables 3, 4 and 5 have the strongest influence in the classifier. It is particularly simple to analyze from the picture the influence of predictor variable 3. Indeed, we can see that predictor variable 3 presents an S-shaped form, with a linear behavior within the interval with endpoints 0 and 25 and constant outside. Moreover, the slopes are negative, meaning that, the higher the value of the predictor variable (up to 25), the stronger the tendency to be classified in the negative class. On top of that, we see that whether predictor variable 3 takes a value of, say, 25, or, instead, a much higher value, turns out to be irrelevant for classification purposes. 20 A similar behavior is detected for predictor variable 4. From 0 to 25, the influence is linear, but after that is stable and finally jumps around value 45. Now the slopes are positive, implying that, the higher the value of predictor variable 4, the stronger the tendency to be classified in the positive class. Predictor variable 5 shows a logarithmic behavior, again with positive slopes and one critical value after which the function remains almost constant. Figure 3: Graphical representation for bupa In general, this example shows that the presence of many cutoffs, as in predictor variables 3, 4 and 5, is not an inconvenience for interpreting the classifier, whose behavior is easily detected via the visualization tool proposed. Now, take the example of database sonar, which has 60 predictor variables. If SVM is performed, all 60 are used again, whereas BSVM uses 98 features, involving 45 different predictor variables. Hence, BSVM is able to make feature selection (it is able to detect as irrelevant for classification 25% of the predictor variables) in a database where linear SVM would consider all variables as relevant. 21 Figure 4: Graphical representation for sonar 22 In Figure 4 the 45 used predictor variables are shown, renumbered for convenience. A simple look to this figure indicates that there are only four out of the 45 predictor variables with strong influence in the classifier, namely predictor variables 11, 20, 26 and 36. Predictor variables in positions 11 and 20 have just one main critical value, whereas predictor variables 26 and 36 present an almost linear behavior in a clearly identified interval. We see again that the use of BSVM allows us to choose the relevant predictor variables, interpret the way such variables influence the classifier, and detect the critical values and intervals for each predictor variable. 4.4 Size of the BSVM classifier Simplicity in the classifier is another desirable property for practitioners. Because both BSVM and Classification Trees are based on simple queries of type (1), the size of the resulting classifier is a good proxy for their complexity. In Table 5, we compare the size of the classifiers constructed by BSVM and Classification Trees. We report average results over all the objects, i.e., over all the testing samples. For both Classification Trees, with and without pruning, we report the total number of nodes in the final tree as well as the number of leaf nodes. For the BSVM classifier, we report the number of used predictor variables as well as the number of used features. In our opinion, the fairest comparison for the complexity is to measure the number of nodes generated by Classification Trees against the number of features used by BSVM. As the results show, the size of the Classification Tree with pruning is always smaller. For the Classification Tree without pruning, in four out of the nine databases, namely credit,cleveland,pima and bupa, BSVM is smaller in size, while in a fifth one, housing, both classifiers are of similar size. This result in complexity for BSVM should be balanced with its better classification ability. From Table 4, BSVM outperforms Classification Trees with pruning except for the pima database, with an increase in accuracy which ranges from 1.53% for the credit database up to 18.75% for the sonar database. Similarly, BSVM outperforms Classification Trees without pruning except for the pima database in which both methods have basically the same accuracy. The increase in accuracy of BSVM ranges from 2.19% for the housing database up to 25.00% for the sonar database. From the numerical experience reported, we can assert that BSVM outperforms Classification Trees in terms 23 size TreePr TreePr TreeCr TreeCr BSVM BSVM leaf nodes nodes leaf nodes nodes predictor variables features sonar 208 ×60 2.76 4.52 18.40 35.80 45.10 97.50 bands 277 ×56 8.95 16.91 28.81 56.62 23.40 78.80 credit 653 ×43 2.11 3.21 42.71 84.42 18.50 80.00 ionosphere 351 ×34 3.00 5.00 18.94 36.88 27.20 71.60 wdbc 569 ×30 5.45 9.90 16.00 31.00 26.00 74.20 cleveland 297 ×13 5.33 9.67 23.00 45.01 12.20 32.00 housing 506 ×13 4.58 8.16 33.84 66.67 12.00 68.30 pima 768 ×8 4.06 7.11 69.15 137.29 8.00 61.50 bupa 345 ×6 3.76 6.52 36.99 72.99 6.00 43.90 Table 5: Size of benchmarking classifiers of its classification ability, at the expense of a higher complexity of the classifier, which is comparable to the complexity of Classification Trees if no pruning is performed. 4.5 Reducing the number of used features The complexity of the classifiers obtained by BSVM is usually high because a high number of features may be present in the rule, as we have discussed in the previous section. With the aim of reducing the complexity of the classifier obtained by our procedure, we have performed several experiments implementing the wrapping procedure described in Section 3.3. Due to computational burden, we present results on five databases. The selection of the databases has been done based on the running times, and it does not affect our conclusions. In Table 6 results on databases sonar,ionosphere,cleveland,housing and bupa are shown. For convenience, we repeat some of the results already given in previous tables. The third and fourth columns report the best accuracy among all three benchmarking methods as well as the one of BSVM (when no wrapper procedure is applied), both processed from the data in Table 4. The fifth column contains the size (measured as number of used features) of the BSVM classifier, obtained from Table 5. The sixth column reports the accuracy of BSVM when the size of the classifier is reduced up to a maximum of 30 features. From those results we can 24 conclude that the classification ability of BSVM slightly deteriorates. More specifically, the cleveland database, which was one in which the linear SVM outperformed BSVM, has essentially the same accuracy as before. This is not surprising, since the average number of features used by BSVM is equal to 32, as reported in Table 5. For the ionosphere and the housing databases, the looc remains almost the same, and therefore, BSVM outperforms the best of the three benchmarking methods while using at most 30 features. In the bupa database, the decrease in accuracy is equal to 1.74%, but even after this deterioration, BSVM with wrapping procedure still gives us the best accuracy. The conclusions for the sonar database are similar. Thus, even with this limit on the number of features, BSVM is still able to outperform the three benchmarking methods, except for the case of the cleveland database in which, as happens without wrapping, BSVM is outperformed by the linear SVM and the NLPSVM. We decided to further investigate those databases in which the wrapping of the BSVM classifiers did not affect the accuracy, namely the cleveland,ionosphere and housing databases. In the housing database, the wrapped BSVM classifier, as said above, has the best accuracy, while its size is half of that from the tree without pruning (which is the best of the two trees in terms of accuracy). For cleveland and ionosphere, the size was not competitive enough. Therefore, we further reduced the number of used features to a maximum of 20. The looc of cleveland and ionosphere was exactly the same as the one obtained when the number of used features was limited to 30. This is specially remarkable for the ionosphere database, in which we can reduce the number of features to less than a third, from 71.60 to at most 20, while the accuracy decreases only by 0.29%. size best reported BSVM BSVM BSVM + Wrapper looc features looc sonar 208 ×60 78.37 90.38 97.50 87.50 ionosphere 351 ×34 89.17 92.31 71.60 92.02 cleveland 297 ×13 85.90 81.44 32.00 81.48 housing 506 ×13 85.38 86.97 68.30 86.76 bupa 345 ×6 69.28 74.78 43.90 73.04 Table 6: Looc of BSVM after reducing the number of features to a maximum of 30 25