Robust optimal classification trees under noisy labels

Discrete Optimization has experienced a tremendous growth in the last decades, both in its theoretical and practical sides, partially provoked by the emergence of new computational resources as well as real-world applications that have boosted this growth. This impulse has also motivated the use of Discrete Optimization models to deal with problems involving a large number of variables and constraints, that years before would have not been possible to be dealt with. One of the fields in which Discrete Optimization has caused a larger impact is in Machine Learning. The incorporation of binary decisions to the classical approaches as Support Vector Machine Cortes and Vapnik (1995), Classification Trees Breiman et al. (1984), Linear Regression and Clustering, amongst other, has considerably enhanced their performance in terms of accuracy and interpretability (see e.g. Benati et al. (2017, 2021); Bertsimas and Dunn (2017); Blanco et al. (2020a, 2020c, 2018); Blanquero et al. (2020a, 2020b); Drucker et al. (1997); Gaudioso et al. (2017)). In particular, one of the most interesting applications of Machine Learning is that related with Supervised Classification.

Supervised classification aims at finding hidden patterns from a training sample of labeled data in order to predict the labels of out-of-sample data. Several methods have been proposed in order to construct highly predictive classification tools. Some of the most widely used methodologies are based on Deep Learning mechanisms Agarwal et al. (2018), k-Nearest Neighborhoods Cover and Hart (1967); Tang and Xu (2016), Naïve Bayes Lewis (1998), Classification Trees Breiman et al. (1984); Friedman et al. (2001) and Support Vector Machines Cortes and Vapnik (1995). The massive use of these tools has induced, in many situations, that malicious adversaries adaptively manipulate their data to mislead the outcome of an automatic analysis, and new classification rules must be designed to handle the possibility of this noise in the training labels. A natural example are the spam filters for emails, where malicious emails are becoming more difficult to automatically be detected since they have started to incorporate patterns that typically appear in legitimate emails (see e.g., Guzella and Caminhas (2009); Yu and Xu (2008)). As a consequence, the development of robust methods against these kind of problems has attracted the attention of researchers (see e.g., Bertsimas et al. (2019); Blanco et al. (2020b)).

In the context of binary classification problems, Support Vector Machines (SVM), introduced by Cortes and Vapnik Cortes and Vapnik (1995), builds the decision rule by means of a separating hyperplane with large margin between classes. This hyperplane can be obtained by solving a convex quadratic optimization problem, in which the goal is to separate data by their two differentiated classes, maximizing the margin between them and minimizing the misclassification errors. Duality properties of this optimization problem allow one to extend the methodology to find nonlinear separators by means of kernels. In Classification and Regression Trees (CART), firstly introduced by Breiman et. al Breiman et al. (1984), one constructs the decision rule based on a hierarchical relation among a set of nodes which is used to define paths that lead observations from the root node (highest node in the hierarchical relation), to some of the leaves in which a class is assigned to the data. These paths are obtained according to different optimization criteria over the predictor variables of the training sample. The decision rule comes up naturally, the classes predicted for new observations are the ones assigned to the terminal nodes in which observations fall in. Historically, CART is obtained heuristically through a greedy approach, in which each level of the tree is sequentially constructed: starting at the root node and using the whole training sample, the method minimizes an impurity measure function obtaining as a result a split that divides the sample into two disjoint sets which determine the two descendant nodes. This process is repeated until a given termination criterion is reached (minimum number of observations belonging to a leaf, maximum depth of the tree, or minimum percentage of observations of the same class on a leaf, among others). In this approach, the tree grows following a top-down greedy approach, an idea that is also shared in other popular decision tree methods like C4.5 Quinlan (1993) or ID3 Quinlan (1996). The advantage of these methods is that the decision rule can be obtained rather quickly even for large training samples, since the whole process relies on solving manageable problems at each node. Furthermore, these rules are interpretable since the splits only take into account information about lower or upper bounds on a single feature. Nevertheless, there are some remarkable disadvantages in these heuristic methodologies. The first one is that they may not obtain the optimal classification tree, since they look for the best split locally at each node, not taking into account the splits that will come afterwards. Thus, these local branches may not capture the proper structure of the data, leading to misclassification errors in out-of-sample observations. The second one is that, specially under some termination criteria, the solutions provided by these methods can result into very deep (complex) trees, resulting in overfitting and, at times, loosing interpretability of the classification rule. This difficulty is usually overcome by pruning the tree as it is being constructed by comparing the gain on the impurity measure reduction with respect to the complexity cost of the tree.

Mixing together the powerful features of standard classification methods and Discrete Optimization has motivated the study of supervised classification methods under a new paradigm (see Bertsimas and Dunn (2019)). In particular, recently, Bertsimas and Dunn Bertsimas and Dunn (2017) introduced the notion of Optimal Classification Trees (OCT) by approaching CART under optimization lens, providing a Mixed Integer Linear Programming formulation to optimally construct Classification Trees. In this formulation, binary variables are introduced to model the different decisions to be taken in the construction of the trees: deciding whether a split is applied and if an observation belongs to a terminal node. Moreover, the authors proved that this model can be solved for reasonable size datasets, and equally important, that for many different real datasets, significant improvements in accuracy with respect to CART can be obtained. In contrast to the standard CART approach, OCT builds the tree by solving a single optimization problem taking into account (in the objective function) the complexity of the tree, avoiding post pruning processes. Moreover, every split is directly applied in order to minimize the misclassification errors on the terminal nodes, and hence, OCTs are more likely to capture the essence of the data. Furthermore, OCTs can be easily adapted in the so-called OCT-H model to decide on splits based on hyperplanes (oblique) instead of on single variables. Another remarkable advantage of using optimization tools in supervised classification methods is that features such as sparsity or robustness, can be incorporated to the models by means of binary variables and constraints Günlük et al. (2018). The interested reader is refereed to the recent survey Carrizosa et al. (2020). We would like to finish this discussion pointing out one of the main differences between SVM and Classification Trees: SVM accounts for misclassification errors based on distances (to the separating hyperplane), i.e., the closer to the correct side of the separating hyperplane, the better, whereas in Classification Trees all misclassified observations are equally penalized.

Recently, Blanco et. al Blanco et al. (2020b) proposed different SVM-based methods that provide robust classifiers under the hypothesis of label noises. The main idea supporting those methods is that labels are not reliable, and in the process of building classification rules it may be beneficial to flip some of the labels of the training sample to obtain more accurate classifiers. With this paradigm, one of the proposed methods, RE-SVM, is based on constructing a SVM separating hyperplane, but simultaneously allowing observations to be relabeled during the training process. The results obtained by this method, in datasets in which noise was added to the training labels, showed that this strategy outperforms, in terms of accuracy, classical SVM and other SVM-based robust methodologies. See Bertsimas et al. (2019) for alternative robust classifiers under label noise.

In this paper we propose a novel binary supervised classification method, called Optimal Classification Tree with Support Vector Machines (OCTSVM), that profits both from the ideas of SVM and OCT to build classification rules. Specifically, our method uses the hierarchical structure of OCTs, which leads to easily interpretable rules, but splits are based on SVM hyperplanes, maximizing the margin between the two classes at each node of the tree. The fact that the combination of SVM and classification tree tools provides enhanced classifiers is not new. A similar approach can be found in Bennett and Blue (1998). Nevertheless, in that paper the authors analyze the greedy CART strategy by incorporating, sequentially the maximization of the margin, over known assignments of observations to the leaves of the tree. Opposite to that, OCTSVM does not assume those assumptions and it performs an exact optimization approach. Moreover, this new method also incorporates decisions on relabeling observations in the training dataset, making it specially suitable for datasets where adversary attacks are suspected. The results of our experiments show that OCTSVM outperforms other existing methods under similar testing conditions. In contrast to the robust classifiers under label noise provided in Bertsimas et al. (2019), our method is not based on the worst-case paradigm commonly used in the field of robust optimization, but in the convenience of finding good classifiers under the presence of unknown noisy labels.

The rest of the paper is organized as follows. In Sect. 2 we recall the main ingredients of our approach, in particular, SVM, RE-SVM and OCTs, as well as the notation used through the paper. Section 3 is devoted to introduce our methodology, and presents a valid Mixed Integer Non Linear Programming (MINLP) formulation. In Sect. 4 we report the results obtained in our computational experiments, in particular, the comparison of our method with OCT, OCT-H and the greedy CART. Finally, some conclusions and further research on the topic are drawn in Sect. 5.

In this section we recall the main ingredients in the approach that will be presented in Sect. 3 which allows us to construct robust classifiers under label noises, namely, Support Vector Machines with Relabeling (RE-SVM) and Optimal Classification Trees with oblique splits (OCT-H).

All through this paper, we consider that we are given a training sample \(\mathcal {X} = \left\{ (x_1,y_1)\right. \), \(\left. \ldots (x_n,y_n), \right\} \subseteq \mathbb {R}^p \times \left\{ -1, +1 \right\} \), in which p features have been measured for a set of n individuals (\(x_1, \ldots , x_n\)) as well as a \(\pm 1\) label is also known for each of them (\(y_1, \ldots , y_n\)). The goal of supervised classification is, to derive, from \(\mathcal {X}\), a decision rule \(D_\mathcal {X}: \mathbb {R}^p \rightarrow \{-1,1\}\) capable to accurately predict the right label of out-sample observations given only the values of the features. We assume, without loss of generality that the features are normalized, i.e., \(x_1, \ldots , x_n \in [0,1]^p\).

This section is devoted to introduce our new classification methodology, namely OCTSVM. The rationale of this approach is to combine the advantage of hierarchical classification methods such as Classification Trees, with the benefits from using distance-based classification errors, by means of hyperplanes maximizing the margin between them (SVM paradigm). Therefore, this new model rests on the idea of constructing an optimal classification tree in which the splits of the nodes are performed by following the underlying ideas of model (RE – SVM): (1) the splits are induced by hyperplanes in which the positive and the negative classes are separated maximizing the margin between classes, (2) minimizing the classification errors, and (3) allowing observations to be relabeled along the training process. In contrast to what it is done in other Classification Tree methods, OCTSVM does not make a distinction (beyond the hierarchical one) between branch and leaf nodes, in the sense that RE-SVM based splits are sequentially applied in each node, and the final classification for any observation comes from the hyperplanes resulting at the last level of the tree, in case there are no pruned branches, or at the last node where a split was made in case of a pruned branch.

As it has been pointed out before, OCT-H is a classification tree that allows the use of general (oblique) hyperplane splits, which is built by solving a single optimization problem that takes into account the whole structure of the tree. Nevertheless, despite the good results this method has proven to obtain in real classification problems, a further improvement is worth to be considered. In Fig. 2 we see a set of points in the plane differentiated by geometrical elements (triangles and circles) in two classes. Looking at the left picture, one can see one of the optimal solutions of OCT-H for depth equal to two, where the red hyperplane is the split applied at the root node and the black ones are applied on the left and right descendants, which define the four leaves. This solution is optimal, for a certain value of the cost-complexity parameters, since it does not make any mistakes on the final classification. Nevertheless, since this method does not have any kind of control on the distances from points to the hyperplanes, one can observe that the blue class has very tiny margins at the leaves, and hence, for this class, misclassification errors are more likely to occur in out-of-sample observations. On the other hand, on the right side of Fig. 2 one sees another possible optimal solution for the OCTSVM model with depth equal to one (note that unlike OCT-H, OCTSVM constructs a final SVM-based classifier at each of the leaf nodes, which may be identified with an extra depth). Again, the red hyperplane is the split applied at the root node and the black ones are the classification splits applied at the two leaves. Despite these two methods are obtaining a perfect classification on the training sample, Fig. 2 shows that OCTSVM provides a more balanced solution than OCT-H since it has wider margins between both classes, what could be translated into a higher accuracy for out-of-sample observations.

In order to formulate the OCTSVM as a MINLP, we will start describing the rationale of its objective function that must account for the margins induced by the splits at all nodes, the classification errors, the penalty paid for relabelling observations and the cost-complexity of the final classification tree. To formulate the above concepts we need different sets of variables. First of all, we consider continuous variables: \(\omega _t \in \mathbb {R}^p,\ \omega _{t_0} \in \mathbb {R},\ t = 1,\ldots , T\), which represent the coefficients and the intercept of the hyperplane performing the split at node t. Taking into account that the margin of the hyperplane \(\mathcal {H}_t = \{z: \omega _t z + \omega _{t0} =0\}\) is given by \(\frac{2}{||\omega _t||}\), maximizing the minimum margin between classes induced by the splits can be done introducing an auxiliary variable \(\delta \in \mathbb {R}\) (that will be minimized in the objective function) which is enforced by the following constraints:Once the maximization of the margin is set, we have to model the minimization of the errors at the nodes, whereas at the same time we minimize the number of relabelled observations. These two tasks are accomplished by the variables \(e_{it} \in \mathbb {R},\ i = 1,\ldots ,n, \ t=1,\ldots ,T\), that account for the misclassification error of observation i at node t, and \(\xi _{it}\in \left\{ 0 ,1\right\} \) binary variables modelling whether observation i is relabeled or not at node t. If \(c_1\) and \(c_2\) are the unit costs of misclassification and relabelling, respectively, our goal is achieved adding to the objective function the following two terms:The correct meaning of these two sets of variables must be enforced by some families of constraints that we describe next. Nevertheless, for the sake of readability before describing those constraints modeling these \(e_{it}\) and \(\xi _{it}\), we must introduce another family of variables the \(\beta _{it} \in \mathbb {R}^p, \beta _{i0} \in \mathbb {R}, \ i=1,\ldots , n, \ t=1,\ldots , T\), which are continuous variables equal to the coefficients of the separating hyperplane at node t when observation i is relabelled, and equal to zero otherwise. In addition, we consider binary variables \(z_{it}\in \left\{ 0 , 1 \right\} \) needed to control whether observation i belongs to node t of the tree. Now, putting all these elements together, as it is done in RE-SVM, we can properly define the splits and their errors at each node of the tree using the following constraints:Constraints (4), which can be easily linearized, are used to define the \(\beta _{it}\) variables: they equal the \(\omega _t\) variables when the observation i is relabelled (\(\xi _i = 1\)), and are equal to zero otherwise (\(\xi _i = 0\)). On the other hand, constraints (3) control the relabelling at each node of the tree. If an observation i is in node t (\(z_{it}=1\)), and \(\xi _i=0\), we obtain the standard SVM constraints for the separating hyperplane. Nevertheless, if \(\xi _i=1\), then the separating constraints are applied for the observation i as if its class were the opposite to its actual one, i.e., as if observation i is relabeled. Moreover, since M is a big enough constant, these constraints do not have any kind of impact in the error variables of node t if observation i does not belong to this node (\(z_{it}=0\)).

On the other hand, there are still some details left that must be imposed to make the model to work as required. In the decision tree, observations start at the root node and they advance descending through the levels of the tree until they reach a leaf or a pruned node. Hence, we have to guarantee that observations must belong to one, and only one, node per level. By means of the \(z_{it}\) variables, this can be easily done by the usual assignment constraints applied in each level, \(u\in U\), of the tree:Moreover, for consistency in the relation between a node and its ancestor, it is clear that if observation i is in node t (\(z_{it}=1\)), then, observation i must be also in the parent of node t (\(z_{ip(t)}=1\)), with the only exception of the root node. Besides, if observation i is not in node t (\(z_{it}=0\)), then i can not be in its successors, and this is modeled by adding the following constraints to the problem:So far, the OCTSVM model has everything it needs to properly perform the splits by following the RE-SVM rationale described in (RE – SVM), taking into consideration the tree complexity, and maintaining the hierarchical relationship among nodes. The last element that we need to take care of, to assure the correct performance of the whole model, is to define how observations follow their paths inside the tree. We get from constraints (6) that observations move from parent to children (nodes), but every non terminal node has a left and a right child node, and we need to establish how observations take the left or the right branch. Since the splits are made by the separating hyperplane, we force observations that lie on the positive half space of a hyperplane to follow the right branch of the parent node, and observations that lie on the negative one to take the left branch. This behavior is modeled with the binary variables \(\theta _{it}\in \left\{ 0,1 \right\} \), that are used to identify whether observation i lies in the positive half space of the separating hyperplane at node t, \(\theta _{it}=1\), or if observation i lies on the negative half space, \(\theta _{it}=0\). By considering M a big enough constant, the correct behavior of the path followed by the observations is enforced by the following constraints:Hence, by making use of these \(\theta _{it}\) variables, and distinguishing between nodes that come from left splits, \(\tau _{bl}\) (nodes indexed by even numbers), and right splits, \(\tau _{br}\) (nodes indexed by odd numbers), we control that the observations follow the paths through the branches in the way we described above throughout the following constraints:According to constraints (9), if an observation i is on the parent node of an even node t (\(z_{ip(t)}=1\)), and i lies on the negative half space of the hyperplane defining the split on p(t) (\(\theta _{ip(t)}=0\)), then \(z_{it}\) is forced to be 1. Hence, \(\theta _{ip(t)}=0\) implies that observation i takes the left branch to the child node \(t \in \tau _{bl}\). Moreover, we can see that this constraint is consistent since if \(z_{ip(t)}=1\), but observation i is not in the left child node, \(z_{it}=0\), \(t\in \tau _{bl}\), then \(\theta _{ip(t)}\) equals 1, what means that observation i lies on the positive half space of the hyperplane of p(t). On the other hand, constraints (10) are similar but for the right child nodes, \(\tau _{br}\). If an observation i is in the parent node of an odd node \(t \in \tau _{br}\), and i lies on the positive half space of the hyperplane of p(t) (\(\theta _{ip(t)} = 1\)), then, \(z_{it}=1\) what means that observation i has to be on node t.

The final term to be included in the objective function of the problem is the complexity of the resulting tree. Following the approach in OCT and OCT-H, we consider binary variables \(d_t\in \left\{ 0 ,1\right\} , \ t=1,\ldots , T\), that control whether a separating split is applied at node t. Thus, to control the tree complexity resulting of the process, we minimize the sum of these variables multiplied by a cost penalty \(c_3\). Gathering all the components together, the objective function to be minimized in our problem results inAccording to this, it is important to make a distinction between the methods that use, or the ones that do not use, SVM based splits. When a model does not use SVM based splits, taking into account that the binary variable \(d_t=1\) implies that a hyperplane is being used to split the points in node t, complexity can be easily regulated by just imposing \(\Vert \omega _t\Vert _2 \le M d_t\) in all the branch nodes. Nevertheless, when using a SVM based method such as the one we are presenting here, the previous constraint would be in conflict with constraints (3). This is due to the fact that \(d_t = 0\) would imply \(\Vert \omega _t\Vert _2 = 0\), and under this scenario, observations in this node would have to pay for the margin violation error \(e_{it}=1\), even though these errors are not justified since points are not being separated at this node. To overcome this issue, we need to add some other constraints to the model, but before getting into the mathematical formulation, we would like to emphasize the different aspects that explain the difficulty of the problem. The objective function accounts for the complexity cost of node t (\(d_t=1\)) when a hyperplane is actually built so as to split the points in node t. In case we do not pay the complexity cost in node t (\(d_t=0\)), it does not necessarily mean that a hyperplane is not built at this node, it could simply turn out to be a hyperplane that leaves all the observations at one of the half spaces it creates, i.e., a hyperplane that is not splitting the points. These non splitting hyperplanes do not affect the training set at all, and more importantly, they would not affect out of sample observations since predictions will occur in leaf nodes or in the first branch node in which \(d_t=0\). Going back to the formulation, the first step now is to introduce some binary variables, \(h_{it}\in \left\{ 0,1\right\} ,\ i\in N,\ t\in \tau _b\), that will be relaxed afterwards, defined by \(h_{it}=z_{it}\theta _{it}\). These variables tell us which observations belong to node t and at the same time lie on the positive half space of the split created in t. It is important to define these variables because they are used to measure whether the hyperplane is splitting the points in node t or not. This is going to be done by means of some new binary variables \(v_{t}\in \left\{ 0,1\right\} ,\ t\in \tau _b\), that will be equal to zero in case all the points in node t belong to the positive half space of the hyperplane built in this node, \(\mathcal {H}_t\), and one otherwise. For the definition of the \(d_t\) variables to make sense, the following constraints must simultaneously be considered:where M is a big enough constant. The reader should observe that (11) is the definition of the \(h_{it}\) variables as the product of \(z_{it}\) by \(\theta _{it}\). These constraints can be easily linearized by the usual tricks. On the other hand, taking into account that \(v_{t}\) variables would tend to be zero (by the effects on constraints (13)), constraints (12) stand for the definition of the \(v_{t}\) variables, since these variables could be equal to zero just in case all the \(h_{it}\) are equal to one, what means that all the observations belong to the positive half space of \(\mathcal {H}_t\). Finally, we obtain through constraints (13) the definition of the \(d_t\) variables. Since these variables are being minimized in the objective function, they would try to be equal to zero. Nevertheless, this can just happen if \(v_t=0\), what means that all the observations belong to the positive half space of \(\mathcal {H}_t\), or if \(\displaystyle \sum _{i\in N} h_{it} = 0\) in case \(v_t=1\), what means that all the observations belong to the negative half space of \(\mathcal {H}_t\). Hence, \(d_t\) is equal to one if and only if the points in node t are being actually separated by \(\mathcal {H}_t\).

Finally, another point that it is important to remark about the \(d_t\) variables is that once a non-leaf node does not split (that is, the corresponding branch is pruned at this node), the successors of node t can not make splits either to maintain the correct hierarchical structure of the tree. Recalling that p(t) is the parent node of node t, we can guarantee this relationship throughout the following constraintsSome of the constraints discussed above require big-M constants. The value of these constants can be adjusted once we know the dimension (n, p) of the dataset involved in the optimization problem. Recall that \(x_i \in [0,1]^p\), therefore it is well known that the maximum distance between two points in such a domain is \(\sqrt{p}\). Hence, the maximum distance from a point to a hyperplane is also \(\sqrt{p}\). According to this, the big-M constant in constraints (3), (6) and (7) is actually \(\sqrt{p}\).

On the other hand, the \(h_{it}\) variables are upper bounded by one, and therefore \(\displaystyle \sum _{i=1}^n h_{it}\) is upper bounded by n. As a result, the big-M constant involved in constraints (11) and (12) is n as well.

Gathering all the constraints together, and substituting the generic big-M constants by those estimated in our discussion above, the OCTSVM is obtained by solving the following MINLP:The reader may note that the above formulation has two families of bilinear constraints, namely (15) and (16), that can be easily linearized giving rise to a mixed integer second order cone formulation.

In Table 1 we summarize the variables, index sets and parameters used in our model.

In this section we present the results of our computational experiments. Five different classification tree-based methods are compared, CART, OCT, OCT-H, OCT+SVM and OCTSVM, on nine popular real-life datasets from UCI Machine Learning Repository Dua and Graff (2017). Notice that OCT+SVM is a modification of our OCTSVM in which the \(\xi _{it}\) variables are fixed to zero, i.e., no relabeling is allowed in the model. This method is included so as to assess the isolated effect of using margin-based splits, without relabeling, within the classification trees. The considered datasets together with their names and dimensions (n: number of observations, p: number of features) are reported in the three tables of this section.

Our computational experiments focus on the analysis of the accuracy and AUC (area under the ROC curve) of the different classification tree-based methods. This analysis is based in four different experiments for each one of the nine considered dataset. Our goal is to analyze the usefulness of the different methods for classifying data affected by label noise. Therefore, in our experiments we use, apart from the original datasets, three different modifications where in each one of them a percentage of the labels in the sample are randomly flipped. The percentages of flipped labels range in \(\left\{ 0\%, 20\%, 30\%, 40\% \right\} \), where \(0\%\) indicates that the original training data set is used to construct the tree.

We perform a 4-fold cross-validation scheme, i.e., datasets are split into four random train-test partitions. One of the folds is used for training the model while the rest are used for testing. When testing the classification rules, we compute the accuracy, in percentage, on out of sample data:

\(\textit{ACC} = \frac{\#\textit{Well Classified Test Observations}}{\#\textit{Test Observations}}\cdot 100\).

as well as the AUC, which provides an aggregate measure of performance across all possible classification thresholds. One way of interpreting AUC is as the probability that the model ranks a random positive example more highly than a random negative example.

The CART method was coded in R using the rpart library. OCT, OCT-H, OCT+SVM and OCTSVM mathematical programming models were coded in Python and solved using Gurobi 8.1.1 on a PC Intel Core i7-7700 processor at 2.81 GHz and 16GB of RAM. A time limit of 30 seconds was set for training. Not all the problems were solved to optimality, nevertheless, this time limit was enough in order to obtain good classifiers. The average gap of the experiments is reported in table 4.

The calibration of the parameters of the different optimization-based models compared in these experiments was set as follows:Last to mention, the depth, D, considered in these experiments was set equal to three for CART, OCT and OCT-H, whereas for OCTSVM and OCT+SVM we fixed depth equal to two, creating consequently trees with 3 levels, to set a fair comparison among the different methods.

For each dataset, we replicate each experiment four times. In Table 2 we show the average (± standard deviation) accuracies for each one of the methods and datasets. In addition, Table 3 shows the average (± standard deviation) AUC results. The best results are highlighted (boldfaced). The first column stands for the percentage of flipped labels (FL) of the training sets. On the other hand, the last column shows the mean difference (Diff) between OCTSVM and the best result among OCT and OCT-H. Finally, in Table 4 we report the average MINLP gaps obtained by the models at the end of the training time limit.

Observe that when \(0\%\) of the training labels are flipped (i.e., the original dataset), one realizes of a general trend in accuracy and AUC of the different models: CART < OCT < OCT-H < OCTSVM, with the only exceptions of Wholesale and Banknote in which OCT-H obtains a non-meaningful slightly larger average accuracy. We would like to emphasize that these results are not surprising. Indeed, on the one hand, OCT is an optimal classification version of the CART algorithm, and hence better results should be expected from this model, as already shown in the computational experience in Bertsimas and Dunn (2017), and also evidenced in our experiments. Moreover, OCT is just a restricted version of OCT-H, in that in the latter, the set of admissible hyperplanes is larger than in the former. Also, as already pointed out in Fig. 2, OCTSVM goes one step further and, apart from allowing oblique hyperplanes based trees, has a more solid structure due to the margin maximization, the distance based errors and the possibility of relabeling points. All together results in higher accuracy and AUC results as shown in our experiments. In some datasets the comparison of the different methods gives rather similar results, however in some others OCTSVM is above the other methods more than \(5\%\) percent both in accuracy and AUC. The simplified methodology based on OCTSVM in which no relabeling is allowed, named OCT+SVM, shows a similar performance in both accuracy and AUC than OCT-H.

Turning to the results on datasets with flipped labels on the training dataset, OCTSVM clearly outperforms the rest of methods and consistently keeps its advantage in terms of accuracy and AUC with respect to the other methods. OCT, OCT-H and OCT+SVM, which are both above CART, alternate higher-lower results among the different datasets. Our method, namely OCTSVM, clearly is capable to capture the wrongly labeled observations and constructs classification rules able to reach higher accuracies and AUC, even when \(40\%\) of the labels were flipped, while other methods, give rise to classifiers that significantly worsen their performance in terms of accuracy and AUC in the test sample.

Concerning the MINLP Gaps obtained with the optimization-based methods (Table 4) one can observe that within the 30 seconds of time limit, most of the instances, for all the methods, are not optimally solved, but still good quality classifiers are constructed in all cases. In particular, OCT, OCT-H and OCTSVM finish the CPU time for training with large gaps, which indicates the computational complexity of the problems. In contrast, the gaps obtained with OCT+SVM are considerably smaller with respect to OCT-H and OCTSVM, but of the same size than OCT, which shows that the decision on relabeling observations makes the problem harder to solve.

Supervised classification is a fruitful field that has attracted the attention of researchers for many years. One of the methods that has experienced a more in depth transformation in the last years is classification trees. Since the pioneer contribution by Breiman et al. Breiman et al. (1984), where CART was proposed, this technique has included tools from mathematical optimization giving rise to the so called OCT Bertsimas and Dunn (2017); Bertsimas et al. (2019), methods that are optimal in some sense. In spite of that, there is still some extra room for further improvements, in particular making classifiers more robust against perturbed datasets. Our contribution is this paper goes in that direction and it augments the catalogue of classification tree methods able to handle noise in the labels of the dataset.

We have proposed a new optimal classification tree approach able to handle label noise in the data. Two main elements support our approach: the splitting rules for the classification trees are designed to maximize the separation margin between classes and wrong labels of the training sample are detected and changed at the same time that the classifier is built. The method is encoded on a Mixed Integer Second Order Cone Optimization problem so that one can solve medium size instances by any of the nowadays available off-the-shelf solvers. We report intensive computational experiments on a battery of datasets taken from UCI Machine Learning repository showing the effectiveness and usefulness of our approach.

Future research lines on this topic include the analysis of nonlinear splits when branching in OCTSVM, both using kernel tools derived from SVM classifiers or specific families of nonlinear separators. This approach will result into more flexible classifiers able to capture the nonlinear trends of many real-life datasets. Additionally, we also plan to address the design of math-heuristic algorithms which keep the essence of OCTs but capable to train larger datasets and the analysis of a multiclass version of our approach.