Clustering categories in support vector machines

Clustering Categories in Support Vector Machines ∗ Emilio Carrizosa 1 , Amaya Nogales-Gómez 1 , and Dolores Romero Morales 2 1 Departamento de Estadística e Investigación Operativa Facultad de Matemáticas Universidad de Sevilla Spain {ecarrizosa,amayanogales}@us.es 2 Saïd Business School University of Oxford United Kingdom [email protected] Abstract Support Vector Machines (SVM) is the state-of-the-art in Supervised Classication. In this paper the Cluster Support Vector Machines (CLSVM) methodology is proposed with the aim to reduce the complexity of the SVM classier in the presence of categorical features. The CLSVM methodology lets categories cluster around their peers and builds an SVM classier using the clustered dataset. Four strategies for building the CLSVM classier are presented based on solving: the original SVM formulation, a Quadratically Constrained Quadratic Programming formulation, and a Mixed Integer Quadratic Programming formulation as well as its continuous relaxation. The computational study illustrates the performance of the CLSVM classier using two clusters. In the tested datasets our methodology achieves comparable accuracy to that of the SVM with original data but with a dramatic decrease in complexity. Keywords: Support vector machines, Categorical features, Classier complexity, Clustering, Quadratically constrained programming, 0-1 programming ∗ This work has been partially supported by projects MTM2012-36163 of Ministerio de Economía y Competitividad, Spain, P11-FQM-7603 and FQM-329 of Junta de Andalucía, Spain. 1 1 Introduction In Supervised Classication, [1, 14, 28], we are given a set of objects Ω partitioned, in its simplest setting, into two classes, and the aim is to classify new objects. Given an object i∈Ω , it is represented by a vector (xi, x0 i, yi) . The feature vector xi is associated with J categorical features, that can be binarized by splitting each feature into a series of 0-1 dummy features, one for each category, and takes values on a set X⊆ {0,1}PJ j=1 Kj , where Kj is the number of categories of feature j . The feature vector x0 i is associated with J0 continuous features and takes values on a set X0⊆RJ0 . Finally, yi∈ {−1,+1} is the class membership of object i . Information about objects is only available in the so-called training sample , with n objects. In many applications of Supervised Classication datasets are composed by a large number of features and/or objects, making it hard to both build the classi- er and interpret the results. In this case, it is desirable to obtain a less complex classier, which may make classication easier to handle and interpret, less prone to overtting and computationally cheaper when classifying new objects. The most popular strategy proposed in the literature to achieve this goal is feature selection [12, 13, 26], which aims at selecting the subset of most relevant features for classication while maintaining or improving accuracy and preventing the risk of overtting. Feature selection reduces the number of features by means of all-or-nothing procedure. For categorical features, binarized as explained above, it simply ignores some categories of some features, and does not give valuable insight on the relationship between feature categories. These issues may imply a signicant loss of information. A state-of-the-art method in Supervised Classication is Support Vector Machines (SVM). The SVM aims at separating both classes by means of a classier, (ω)>x+ (ω0)>x0+b= 0 , (ω, ω0) being the so-called score vector, where ω is associated with the categorical features and ω0 is associated with the continuous features. Given an object i , it is classied in the positive or the negative class, according to the sign of the score function, sign((ω)>xi+ (ω0)>x0 i+b) , while for the case (ω)>xi+ (ω0)>x0 i+b= 0 , the object is classied randomly. See [4, 9, 13, 17, 21] for successful applications of the SVM and [8] for a recent review on Mathematical Optimization and the SVM. In this paper, a methodology to reduce the complexity of the Support Vector Machines (SVM) classier for datasets composed by categorical features, sometimes containing many categories, and eventually continuous features, is proposed. This is done by clustering the dierent categories of each categorical feature into a given number of clusters, and then obtaining an SVM-type classier for the clustered dataset. We call this the Cluster Support Vector Machines (CLSVM) methodology and we will refer to the CLSVM classier. As an illustration, let us consider the well-known German credit dataset, german , which is one of the datasets from the UCI repository, [3], used in our computational tests. This is a credit scoring dataset, with good customers dening the positive class ( y= +1 ) and bad customers dening the negative class ( y=−1 ), and has been used in the context of Supervised Classication, such as in [2]. In this dataset each object is composed by 20 features: 11 categorical features, binarized into 52 dummies, and 9 continuous features. For this dataset, the SVM formulation with original data, hereafter denoted by SVM O , gives a classier leading to a classication 2 accuracy of 76.67% and whose categorical score subvector ω0 has 50 relevant features, i.e., card({ω0 j6= 0}) = 50 . However, using the CLSVM methodology described in this paper, where the categories of each categorical feature are grouped just into two clusters, the classication accuracy is increased to 80.00% while the CLSVM classier uses 2×11 = 22 relevant dummies. In other words, the methodology proposed here allows one to obtain a much simpler classier with an accuracy even higher than the original one. The clustering is shown in Figure 8, where we can see each categorical feature separated by a discontinuous line and each category from each categorical feature represented by a circle. The two clusters are distinguished by the coloring with dark grey and light grey circles. For instance, the categorical feature "Property" originally had four categories, namely, "real estate", "building society savings agreement/life insurance", "car or other" and "unknown/no property". As we will see later, the three rst categories, colored in dark grey, are those indicating good customers, and will be grouped into one single cluster, against the category indicating bad customers, namely "unknown/no property". In this paper, four strategies to build the CLSVM classier are proposed using dierent mathematical optimization formulations. The rst strategy proposed solves the SVM O as initial step. Then, categories are clustered using the SVM O scores and the CLSVM classier consists of building an SVM classier using the clustered values. For the second strategy a Mixed Integer Nonlinear Programming (MINLP) formulation of the same type as the SVM formulation is proposed, but in this case dening a score for each cluster of each categorical feature. The second strategy is based on solving the continuous relaxation of this MINLP formulation, a Quadratically Constrained Quadratic Programming (QCQP) formulation to nd a clustering, and the CLSVM classier consists of building again an SVM classier using the clustered dataset. The third and fourth strategies are based on a Mixed Integer Quadratic Programming (MIQP) formulation derived from the MINLP formulation using the big M modeling trick to reformulate the nonlinear terms in the feasible region. The third strategy works similarly to the second one, but solves the continuous relaxation of the MIQP. The fourth strategy solves the MIQP formulation itself and obtains the clustering and the classier at once. In the computational results, the four strategies are compared against the SVM O in ten real-life datasets using two performance criteria, namely accuracy and complexity of the classier for the categorical data. We conclude from our experiments that the CLSVM achieves a comparable or even better accuracy than the SVM O in nine of the ten datasets tested. In addition, the CLSVM methodology provides a reduction on the complexity of the classier for the categorical data, while the SVM O uses more dummy features for all the strategies and for all ten datasets. The remainder of this paper is organized as follows. In Section 2 we set up notation and terminology. Then, the CLSVM methodology is introduced together with two mathematical optimization formulations. Two theoretical results relevant to the formulations are presented. In Section 3 the four CLSVM strategies are presented. Section 4 is devoted to the computational experience, where the CLSVM classier and the SVM O classier are compared using ten datasets. Finally, Section 5 contains a brief summary, nal conclusions and some lines for future research. 3 2 The CLSVM methodology In this section the CLSVM methodology is introduced. An MINLP formulation is presented for building the CLSVM classier and some theoretical results for the formulation are stated and proved. Then, an MIQP formulation is derived from the MINLP one, using the big M modeling trick to reformulate the nonlinear terms in the feasible region. The theoretical results also hold for this formulation. The CLSVM methodology is based on the SVM formulation, but takes into account the way categorical features are handled in the SVM (and other linear classiers): splitting each feature into a series of 0-1 dummy features, the classier assigns one score to each dummy feature, and thus to each value of the categorical feature. Instead, the CLSVM methodology lets dummies cluster around their peers and builds an SVM classier using the clustered dataset, which may reduce the number of relevant features. We will say that category k from categorical feature j is relevant to the classier if ωj,k 6= 0 . Similarly, if ω0 j06= 0 , then we will say that continuous feature j0 is relevant to the classier. Let us focus now on categorical features. If a category is relevant to the classier, we will say that category k from feature j points towards the positive class if the score associated to the category is positive, i.e., if ωj,k >0 . Analogously, if ωj,k <0 we will say that category k from feature j points towards the negative class. The fact that a category points towards the positive (or negative) class means that it contributes to classify objects in the positive (or negative) class respectively, i.e., contributes to make sign((ω)>xi+ (ω0)>x0 i+b) equal to +1 ( −1 ). Let us introduce some notation. Given an object i in the training set , we let xi= (xi,j,k) , where xi,j,k is equal to 1 if the value of categorical feature j in object i is equal to category k and 0 otherwise. First, we present the standard SVM formulation, [8, 10, 23, 24]. The SVM aims at separating both classes by means of a hyperplane, found by minimizing the socalled hinge loss and the squared l2 -norm of the score vector, [8]. The SVM classier is obtained by solving the following Quadratic Programming (QP) formulation with linear constraints: min ω,ω0,b,ξ J X j=1 Kj X k=1 (ωj,k)2 2+ J0 X j0=1 (ω0 j0)2 2+C n n X i=1 ξi (1) s.t. (SVM) yi( J X j=1 Kj X k=1 ωj,k xi,j,k + (ω0)>x0 i+b)≥1−ξi∀i= 1, . . . , n (2) ξi≥0∀i= 1, . . . , n (3) ω∈RPJ j=1 Kj (4) ω0∈RJ0 (5) b∈R, (6) where (ξi) denotes the vector of deviation variables and the parameter denoted by C is a nonnegative regularization parameter that calls for tuning, [6, 8]. 4 The methodology proposed in this paper, the CLSVM, receives as input a dataset containing categorical and eventually continuous features. We will denote by Lj the number of clusters in which the Kj dummies of categorical feature j are clustered. As a rst step, the CLSVM performs a clustering for each categorical feature, dened by an assignment vector z∗ , where z∗ j,k,` is equal to 1 if category k from feature j is assigned to the ` - th cluster and 0 otherwise, for j= 1, . . . , J, k = 1, . . . , Kj, ` = 1, . . . , Lj . Then, the dataset is clustered according to z∗ , see Figure 1, and an SVM- type classier is constructed for the clustered dataset, given by (¯ω)>¯x+(ω0)>x0+b= 0 . For categorical feature j , the component ¯ωj,` denotes the score for the ` - th cluster, j= 1, . . . , J, ` = 1, . . . , Lj . The pseudocode of the CLSVM methodology can be found in Figure 2. To avoid symmetry between clustering solutions, the rst category of each categorical feature is always assigned to its rst cluster. For each i∈Ω : Step 1. Input: • original object (yi, xi, x0 i) , xi∈ {0,1}PJ j=1 Kj , x0 i∈RJ0 . • assignment vector z∗∈ {0,1}PJ j=1 LjKj where Lj X `=1 z∗ j,k,` = 1,∀j= 1, . . . , J;∀k= 1, . . . , Kj . Step 2. Output: • clustered object (yi,¯xi, x0 i) , ¯xi∈ {0,1}PJ j=1 Lj , x0 i∈RJ0 where ¯xi= (¯xi,1,1,...,¯xi,J,LJ) with ¯xi,j,` = Kj X k=1 z∗ j,k,`xi,j,k . Figure 1: Pseudocode for the clustered dataset dened by the assignment vector z∗ . Given a dataset Ω : Step 1. Find the assignment vector z∗ , defining a clustering for the categorical features. Step 2. Obtain the clustered dataset ¯ Ω as in Figure 1. Step 3. Find the CLSVM classifier for ¯ Ω , (¯ω)>¯x+ (ω0)>x0+b= 0 . Figure 2: Pseudocode for the CLSVM methodology. 2.1 Formulations for the CLSVM In this section two dierent mathematical optimization formulations are proposed for the CLSVM methodology, an MINLP and an MIQP formulations. The MIQP formulation is derived from the MINLP formulation using the big M modeling trick to reformulate the nonlinear terms in the feasible region. 5 First, we introduce the Cluster (CL) formulation, an MINLP formulation with nonlinear constraints and 0-1 decision variables. This formulation aims at nding a classier, but at the same time clustering categorical feature j into Lj clusters, for each j= 1, . . . , J . The CL is formulated as follows: min ¯ω,ω0,b,ξ,z J X j=1 Lj X `=1 (¯ωj,`)2 2+ J0 X j0=1 (ω0 j0)2 2+C n n X i=1 ξi (7) s.t. (CL) yi  J X j=1 Lj X `=1 ¯ωj,` Kj X k=1 zj,k,` xi,j,k + (ω0)>x0 i+b ≥1−ξi∀i= 1, . . . , n (8) Lj X `=1 zj,k,` = 1 ∀j= 1, . . . , J;∀k= 1, . . . , Kj (9) ξi≥0∀i= 1, . . . , n (10) z∈ {0,1}PJ j=1 LjKj (11) ¯ω∈RPJ j=1 Lj (12) ω0∈RJ0 (13) b∈R. (14) This formulation resembles the SVM formulation (1)-(6), and we will discuss their main dierences. Here we have a score associated with each feature and each cluster, ¯ωj,` , as opposed to a score for each category, ωj,k . With respect to the decision variables, we have PJ j=1 LjKj new 0-1 variables, the number of components of the assignment vector z , but the number of continuous features associated with the score vector decreases from PJ j=1 Kj to PJ j=1 Lj . Constraint (8) corresponds to constraint (2). Constraint (9) ensures that, given a categorical feature, each category is assigned to a unique cluster, which means that there are PJ j=1 Kj additional constraints to those in the SVM formulation. We will say that a categorical feature j is irrelevant to the classier if ¯ωj,` = 0,∀`= 1, . . . , Lj . On the contrary, if the feature is relevant to the classier, we will say that cluster ` from feature j points towards the positive class if the score associated to the cluster is positive, i.e., if ¯ωj,` >0 . Analogously, if ¯ωj,` <0 we will say that cluster ` from feature j points towards the negative class. The eective use of the clusters by the CL formulation is stated in the following theoretical results. Proposition 2.1 For any optimal solution of CL, given a categorical feature j∗ , if there exists `∗ such that zj∗,k,`∗= 1 ∀k= 1, . . . , Kj∗ , then ¯ωj∗,` = 0 ∀`= 1, . . . , Lj∗ . Proof: The proposition will be proved by contradiction. Let (¯ω, ω0, b, ξ, z) be an optimal solution of CL for which the desired property does not hold. For the case `=`∗ , if ¯ωj∗,`∗6= 0 , then (¯ω∗, ω0∗, b∗, ξ∗, z∗) obtained by setting ¯ω∗ j∗,`∗= 0 and b∗=b+ ¯ωj∗,`∗ is a feasible solution for (7)-(14) and has a smaller objective value, which contradicts the fact that the solution (¯ω, ω0, b, ξ, z) is optimal. 6 Now we analyze the case `6=`∗ . If ¯ωj∗,` 6= 0 , then (¯ω∗, ω0∗, b∗, ξ∗, z∗) obtained by setting ¯ω∗ j∗,` = 0 is a feasible solution for (7)-(14) and has a smaller objective value, which contradicts the fact that the solution (¯ω, ω0, b, ξ, z) is optimal.  From this proposition, we obtain: Corollary 2.1 Given a categorical feature, if all its categories belong to the same cluster, then the feature is irrelevant to the CLSVM classier. The clustering given in the CL formulation for a categorical feature j with Lj= 2 , groups the categories into two clusters. It is easy to see that either the feature is irrelevant or one of the clusters of the feature points towards the positive class while the other points towards the negative one. Proposition 2.2 If Lj= 2 , for a given j , for any optimal solution of CL, it holds that: ¯ωj,1·¯ωj,2≤0. (15) Proof: The proposition will be proved by contradiction. Let (¯ω, ω0, b, ξ, z) be an optimal solution of CL for which the desired property does not hold, i.e., ¯ωj,1·¯ωj,2> 0 . Then (¯ω∗, ω0∗, b∗, ξ∗, z∗) obtained by setting ¯ω∗ j,1=¯ωj,1−¯ωj,2 2 , ¯ω∗ j,2=¯ωj,2−¯ωj,1 2 and b∗=b+¯ωj,1+¯ωj,2 2 satises (15), is a feasible solution for (7)-(14) and has a smaller objective value, which contradicts the fact that the solution (¯ω, ω0, b, ξ, z) is optimal.  Figure 8 of dataset german , mentioned in Section 1, illustrates the applicability of Proposition 2.2, where the clustering gives the additional information of which cluster points towards the positive class or the negative class. We have assigned a dark gray coloring to clusters in which ¯ωj,` >0 in the CLSVM classier, and therefore, those clusters point towards good customers; similarly, a light gray coloring is assigned to clusters in which ¯ωj,` <0 in the CLSVM classier, and therefore, those clusters point towards bad customers. For the four categories of feature "Property", the two clusters are given by { "real estate", "building society savings agreement/life insurance", "car or other" } and { "unknown/no property" } . The categories of the rst cluster point towards the positive class, i.e., they are likely to be associated with good customers, while the category "unknown/no property" points towards the negative class, i.e., bad customers. Nonconvex nonlinear constraints such as (8) are known to be computationally dicult to deal with, e.g. [22]. Therefore, one may want to reformulate constraint (8) from the MINLP formulation in order to obtain an MIQP formulation where the nonlinear term of the product of variables ¯ωj,` Kj X k=1 zj,k,` xi,j,k in constraint (8) is reformulated by introducing new big M constraints. This implies adding PJ j=1 LjKj continuous variables, ˜ωj,k,`, j = 1, . . . , J, k = 1, . . . , Kj, ` = 1, . . . , Lj , yielding min ¯ω,˜ω,ω0,b,ξ,z J X j=1 Lj X `=1 (¯ωj,`)2 2+ J0 X j0=1 (ω0 j0)2 2+C n n X i=1 ξi (16) 7 s.t. (CL-bigM) yi  J X j=1 Lj X `=1 ˜ωj,k(i),` + (ω0)>x0 i+b ≥1−ξi∀i= 1, . . . , n (17) Lj X `=1 zj,k,` = 1 ∀k= 1, . . . , Kj,∀j= 1, . . . , J (18) ˜ωj,k,` ≤¯ωj,` +M(1 −zj,k,`)∀k= 1, . . . , Kj,∀`= 1, . . . , Lj,∀j= 1, . . . , J (19) ˜ωj,k,` ≥¯ωj,` −M(1 −zj,k,`)∀k= 1, . . . , Kj,∀`= 1, . . . , Lj,∀j= 1, . . . , J (20) ˜ωj,k,` ≤M zj,k,` ∀k= 1, . . . , Kj,∀`= 1, . . . , Lj,∀j= 1, . . . , J (21) ˜ωj,k,` ≥ −M zj,k,` ∀k= 1, . . . , Kj,∀`= 1, . . . , Lj,∀j= 1, . . . , J (22) ξi≥0∀i= 1, . . . , n (23) z∈ {0,1}PJ j=1 LjKj (24) ¯ω∈RPJ j=1 Lj (25) ω0∈RJ0 (26) ˜ω∈RPJ j=1 LjKj (27) b∈R. (28) We will compare this with the CL formulation. Both objective functions are exactly the same. The dierence between the two formulations comes from the constraints, and the addition of new variables, PJ j=1 LjKj new continuous variables. Constraint (17) is the corresponding to constraint (8). Here, the nonlinear term is replaced with the variable ˜ωj,k(i),` , where k(i) identies the category in which object i falls for feature j . In order to reformulate constraint (8) as a collection of linear constraints, it is a very well-known modeling trick to use a 0-1 variable to control if constraint (8) is active or not, see [27]. Then, constraint (8) is reformulated as linear constraint (17), and 4·PJ j=1 LjKj more constraints are needed for the reformulation, (19)-(22), the so-called big M constraints. Please note that Proposition 2.1, Proposition 2.2 and Corollary 2.1 also hold for the CL-bigM formulation, as it is a valid reformulation of the CL formulation. 3 Strategies for the CLSVM In this section four dierent strategies are proposed to obtain the CLSVM classi- er. The rst, and natural, way to dene a CLSVM classier is by clustering the categories using the scores of the original SVM, the SVM O . This is a cheap strategy but underperforming in some cases in terms of accuracy, as we will see in the computational section. Three alternative strategies are proposed based on the two mathematical optimization formulations introduced in Section 2, the CL and the CL-bigM. In the remainder of this section, when describing the strategies, we will explain how to obtain the partial solution (¯ω, ω0, b) , which determines the CLSVM classier, and the assignment vector z∗ . Then, the assignment vector z∗ performs a clustering for the original dataset, obtaining a clustered dataset, as shown in Figure 1. 8 The rst strategy, the centroid SVM (SVM C ) Strategy, is based on the SVM O scores. As initial step, the SVM O classier is built for the original dataset, then the categories of categorical feature j are clustered into Lj clusters by clustering the SVM O scores, for each j . This is done by solving the minimum sum of squares clustering problem (MSSC), [15]. Given a categorical feature j , MSSC clusters all the categories into Lj clusters such that the sum of the squared distance of the score of a category from the centroid of the cluster is minimized. The pseudocode of the MSSC problem can be found in Figure 3, where the j index has been dropped for the sake of clarity, and calligraphic font is used to denote sets, while regular font for their cardinality. After clustering the dataset, the CLSVM classier builds an SVM classier using the clustered dataset. The pseudocode of this strategy can be found in Figure 4. Given a vector ν∈RK associated with a categorical feature with K categories, Step 1. Sort the values νk , k= 1, . . . , K , increasingly, such that: ν(1) ≤ν(2) ≤. . . ≤ν(K) Step 2. Set Ii0=∅ Set Ii`={1, . . . , i`} Set IiL={1, . . . , K} Set F(Ii`) = X i∈Ii`  ν(i)−1 Ii`X h∈Ii` ν(h)  2 Solve min i1,...,iL−1 L X `=1 F(Ii`\ Ii`−1) Step 3. Return the assignment vector z∗ defined by the L clusters, determined by Ii1,...,IiL−1 . Figure 3: Pseudocode for the MSSC problem. For each C , Step 1. Solve the SVM O and obtain the (partial) optimal solution ω . Step 2. For each j , cluster the Kj categories of feature j into Lj clusters solving the MSSC problem for ν=ωj· , obtaining the components from the assignment vector z∗ j.. . Step 3. Solve the SVM formulation with clustered data defined by z∗ , and return this as the CLSVM classifier. Choose the best C using the CLSVM classifier. Figure 4: Pseudocode for the SVM C Strategy. The second strategy, the CL randomized rounding (CL RR ) Strategy, performs a randomized rounding, [19], to the fractional assignment vector returned by the 9 Table 1: Datasets. Name Name in Repository |Ω|n Class split (in % ) J J0PJ j=1 KjKj census income Census-Income (KDD) Data Set 95130 5000 94/6 31 9 491 9,52,47,17,3,7,24,15,5,10,3,6,8,6,6, 50,38,8,9,8,9,3,3,5,42,42,42,5,3,3,3 adult Adult 30956 5000 24/76 11 3 117 5,8,5,16,5,7,14,6,5,5,41 mushrooms Mushrooms 8124 5000 48/52 17 4 111 6,4,10,9,4,3,12,4,4,9,9,4,3,8,9,6,7 coil 2000 Insurance Company Benchmark (COIL 2000) 5822 3900 94/6 5 80 77 41,6,10,10,10 abalone Abalone 4177 2800 50/50 1 7 3 3 molecular Molecular Biology (Splice-junction Gene Sequences) 3190 2200 52/48 60 0 480 8,8,8, ... careval Car Evaluation 1728 1200 30/70 6 0 21 4,4,4,3,3,3 solar-c Solar Flare Data Set 1066 800 83/17 5 5 23 7,6,4,3,3 german Statlog (German Credit Data) 1000 700 30/70 11 9 52 4,5,11,5,5,5,3,4,3,3,4 australian Statlog (Australian Credit Approval) 690 500 56/44 4 10 29 3,14,9,3 Table 2: Accuracy and complexity results in % for the original SVM (SVM O ). Name SVM O Accuracy Complexity mean std med mean std med census income 94.90 0.00 94.90 63.14 0.00 63.14 adult 84.57 0.22 84.63 83.93 3.26 84.62 mushrooms 100.00 0.00 100.00 71.17 0.00 71.17 coil 2000 100.00 0.00 100.00 1.30 0.00 1.30 abalone 79.87 1.18 79.72 100.00 0.00 100.00 molecular 94.22 0.80 94.04 57.04 3.12 58.54 careval 96.74 1.34 96.97 99.05 2.86 100.00 solar-c 83.53 1.23 83.46 52.17 34.51 69.57 german 74.60 2.71 75.66 94.62 1.88 95.19 australian 84.11 3.17 84.73 86.90 4.83 89.66 16 Table 3: Accuracy and complexity results in % for the SVM C Strategy. Name SVM C Accuracy Complexity mean std med mean std med census income 94.85 0.00 94.85 10.18 0.00 10.18 adult 88.22 2.44 89.59 13.76 2.21 13.68 mushrooms 100.00 0.00 100.00 23.42 0.00 23.42 coil 2000 100.00 0.00 100.00 1.30 0.00 1.30 abalone 79.90 1.05 79.44 66.67 0.00 66.67 molecular 93.94 0.73 93.84 0.00 0.00 0.00 careval 82.80 5.15 82.95 44.76 8.57 38.10 solar-c 83.61 1.38 83.46 12.17 10.43 8.70 german 74.80 2.36 75.00 42.31 0.00 42.31 australian 84.42 3.32 84.73 19.31 9.66 24.14 Table 4: Accuracy and complexity results in % for the CL RR Strategy. Name CL RR Accuracy Complexity mean std med mean std med census income 94.84 0.04 94.82 8.31 0.33 8.55 adult 83.44 0.37 83.44 16.58 1.34 16.24 mushrooms 100.00 0.00 100.00 19.28 4.56 18.02 coil 2000 100.00 0.00 100.00 1.30 0.00 1.30 abalone 79.86 1.02 79.44 66.67 0.00 66.67 molecular 93.40 1.28 93.53 24.87 0.19 25.00 careval 92.23 1.28 92.42 41.90 12.2 38.10 solar-c 83.83 1.08 83.46 5.22 11.14 0.00 german 74.60 3.12 74.00 38.27 4.59 41.35 australian 84.53 3.12 84.73 15.17 11.03 13.79 17 Table 5: Accuracy and complexity results in % for the CLM RR and the CLM strategies. Name CLM RR CLM Accuracy Complexity Accuracy Complexity mean std med mean std med mean std med mean std med census income 94.40 0.04 94.37 8.55 1.62 8.35 94.37 0.00 94.37 0.00 0.00 0.00 adult 88.75 2.96 89.63 10.17 4.36 8.55 85.35 3.16 83.44 9.23 3.64 9.83 mushrooms 98.58 0.77 98.59 21.71 5.87 22.07 100.00 0.00 100.00 14.77 1.57 14.41 coil 2000 100.00 0.00 100.00 1.30 0.00 1.30 100.00 0.00 100.00 1.30 0.00 1.30 abalone 79.87 0.96 79.66 66.67 0.00 66.67 79.65 1.25 79.29 66.67 0.00 66.67 molecular 88.04 1.68 88.38 22.71 0.90 22.50 51.92 0.00 51.92 0.00 0.00 0.00 careval 83.94 4.91 85.41 29.52 10.82 28.57 94.17 2.84 93.37 49.52 3.81 47.62 solar-c 83.76 1.02 83.46 0.87 2.61 0.00 83.61 1.38 83.46 11.31 7.83 8.70 german 72.53 3.77 71.66 36.92 4.28 36.54 75.60 3.01 76.34 42.31 0.00 42.31 australian 84.53 3.05 84.73 5.52 2.76 6.90 85.37 3.28 85.26 23.45 5.52 27.59 18 References [1] C. Apte. The big (data) dig. OR/MS Today , 30(1):2429, February 2003. [2] B. Baesens, R. Setiono, C. Mues, and J. Vanthienen. Using neural network rule extraction and decision tables for credit-risk evaluation. Management Science , 49(3):312329, 2003. [3] C.L. Blake and C.J. Merz. UCI Repository of Machine Learning Databases. http://www.ics.uci.edu/ ∼ mlearn/MLRepository.html, 1998. University of California, Irvine, Department of Information and Computer Sciences. [4] J.P. Brooks. Support vector machines with the ramp loss and the hard margin loss. Operations Research , 59(2):467479, 2011. [5] E. Carrizosa, B. Martín-Barragán, and D. Romero Morales. Binarized support vector machines. INFORMS Journal on Computing , 22(1):154167, 2010. [6] E. Carrizosa, B. Martín-Barragán, and D. Romero Morales. A nested heuristic for parameter tuning in support vector machines. Computers and Operations Research , 43:328334, 2014. [7] E. Carrizosa, A. Nogales-Gómez, and D. Romero Morales. Strongly agree or strongly disagree?: Rating features in Support Vector Machines. Working Paper, 2014. [8] E. Carrizosa and D. Romero Morales. Supervised classication and mathematical optimization. Computers and Operations Research , 40:150165, 2013. [9] W. A. Chaovalitwongse, Y.-J. Fan, and R. C. Sachdeo. Novel optimization models for abnormal brain activity classication. Operations Research , 56(6):1450 1460, 2008. [10] N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods . Cambridge University Press, 2000. [11] J. Czyzyk, M.P. Mesnier, and J.J. More. The neos server. IEEE Computational Science Engineering , 5(3):6875, 1998. [12] G. Fung and O.L. Mangasarian. A feature selection Newton method for support vector machine classication. Computational Optimization and Applications , 28(2):185202, 2004. [13] I. Guyon, J. Weston, S. Barnhill, and V. Vapnik. Gene selection for cancer classication using support vector machines. Machine Learning , 46:389422, 2002. [14] H. Hand, H. Mannila, and P. Smyth. Principles of Data Mining . MIT Press, 2001. [15] P. Hansen and B. Jaumard. Cluster analysis and mathematical programming. Mathematical Programming , 79(1-3):191215, 1997. [16] IBM-Cplex, v. 12.5. http://www-01.ibm.com/software/integration/optimization/cplex/. [17] D. Martens, B. Baesens, T.V. Gestel, and J. Vanthienen. Comprehensible credit scoring models using rule extraction from support vector machines. European Journal of Operational Research , 183(3):14661476, 2007. 19 [18] D. Martens and F. Provost. Explaining data-driven document classications. MIS Quarterly , 38(1):7399, 2014. [19] P. Raghavan and C. D. Tompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica , 7(4):365 374, 1987. [20] D. Romero Morales and J. Wang. A parallel discretization algorithm for cancellation rate forecasting in revenue management. Working Paper, Saïd Business School, University of Oxford, UK, 2009. [21] D. Romero Morales and J. Wang. Forecasting cancellation rates for services booking revenue management using data mining. European Journal of Operational Research , 202(2):554562, 2010. [22] M. Tawarmalani and N. V. Sahinidis. Convexication and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications . Kluwer Academic Publishers, Boston MA, 2002. [23] V. Vapnik. The Nature of Statistical Learning Theory . Springer-Verlag, 1995. [24] V. Vapnik. Statistical Learning Theory . Wiley, 1998. [25] A. Wächter and L. T. Biegler. On the implementation of an interior-point lter line-search algorithm for large-scale nonlinear programming. Mathematical Programming , 106(1):2557, 2006. [26] J. Weston, S. Mukherjee, O. Chapelle, M. Pontil, T. Poggio, and V. Vapnik. Feature selection for SVMs. In T.K. Leen, T.G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems , pages 668674, Cambridge, MA, 2000. MIT Press. [27] H.P. Williams. Model building in Mathematical Programming . Wiley, New York, 1985. [28] X. Wu, V. Kumar, J. Ross Quinlan, J. Ghosh, Q. Yang, H. Motoda, G.J. McLachlan, A. Ng, B. Liu, P.S. Yu, Z.-H. Zhou, M. Steinbach, D.J. Hand, and D. Steinberg. Top 10 algorithms in data mining. Knowledge and Information Systems , 14:137, 2007. 20