Classification Trees for Imbalanced Data: Surface-to-Volume Regularization

Training data are denoted as $\mathscr{D}_{n}=\{(X_{i},Y_{i})\}_{i=1}^{n}$, with $X_{i}\in\Omega\subset\mathbb{R}^{d}$ a vector of features and $Y_{i}\in\{0,1\}$ a class label. Uppercase letters $(X,Y)$ denote random variables, while lowercase $x,y$ denote specific values. Denote the $j$th feature of $X$ as $X[j]$. Let $\mathbb{P}^{*}$ denote the true distribution of i.i.d. samples $(X_{i},Y_{i})$ and let $\mathbb{P}$ denote the weighted distribution that up weights the minority class samples by a constant $\alpha\geq 1$. That is, for any measurable subset $A\subset\Omega$,

Up weighting minority class samples is a conventional technique to counter imbalance and we will focus on the weighted measure $\mathbb{P}$ in the rest of the paper. Denote $\mathbb{P}_{n}$ as the weighted empirical distribution which assigns mass $w_{0}\alpha/n$ to minority class training samples and $w_{0}/n$ to majority class training samples. The constant $w_{0}$ is set to ensure the measures of all training samples add up to $1$.

We use $f$ with various subscripts and diacritics to denote a general classifier from $\Omega$ to $\{0,1\}$, while $T$ with various subscripts and diacritics denotes a tree classifier from $\Omega$ to $\{0,1\}$. A tree classifier is formed by finite splitting steps and its decision sets are a finite union of hyperrectangles. When discussing the probability of certain events that include $n$ random variables $\{(X_{i},Y_{i})\}_{i=1}^{n}$, we simply use $\mathbb{P}$ to represent the probability measure in the $n$-product space. For example, for any $a>0$, $\mathbb{P}\left(n^{-1}\sum_{i=1}^{n}X_{i}>a\right)$ denotes the probability of the event $\{\{(X_{i},Y_{i})\}_{i=1}^{n}:n^{-1}\sum_{i=1}^{n}X_{i}>a\}$. We use $\mathbb{E}$ for expectations over $\mathbb{P}$ and $\mathbb{E}_{n}$ for expectations over $\mathbb{P}_{n}$. We use $\eta$ and $\eta_{n}$ to denote the conditional expectations of $Y$ given $X$ under the true and empirical measure, respectively. That is, $\eta(X)=\mathbb{E}(Y=1|X)$ and $\eta_{n}(X)=\mathbb{E}_{n}(Y=1|X)$.

For all $d\in\mathbb{N}$, consider the space $\mathbb{R}^{d}$ equipped with Lebesgue measure $\mu$. For any Lebesgue measurable closed set $A\subset\Omega$, we define its volume as the Lebesgue measure of set $A$: $V(A)=\mu(A)$. If $A$ can be represented as a finite union of hyperrectangles, we define the surface of $A$ as the $d-1$ dimensional Lebesgue measure of the boundary of $A$: $S(A)=\mu_{d-1}(\partial A)$; otherwise, if there exists $A_{i},i\geq 1$ such that each $A_{i}$ is a finite union of hyperrectangles and $A_{i}$ converges to $A$ in Hausdorff distance, we define the surface of $A$ as $S(A)=\lim_{n\to\infty}S(A_{i})$, provided the limit exists. In general, if all $A_{i},i\geq 1$ are regularly shaped, it will be proven in Proposition 2 that the limit exists. Our definition of surface is different from the convention of the word “surface”. For example, in our definition a $d$ dimensional ball with radius $1/2$ has the same surface as a $d$ dimensional cube with side length $1$, as approximating such a ball with hyperrectangles results in the same surface area as the cube. We adopt this definition of surface since we focus on tree classifiers whose decision sets are always finite unions of hyperrectangles.

For any set $A$ with $0<\mu(A)<\infty$, the surface-to-volume ratio (SVR) can be obtained as $r(A)=\frac{S(A)}{V(A)}.$ For sets with the same volume, the $d$-dimensional cube has the smallest SVR, while sets having multiple disconnected subsets and/or irregular boundaries have relatively high SVR. We visualize sets with different SVR in two-dimensional space in Figure 2, with the subfigures (a)-(c) corresponding to the decision sets in Figure 1. We can see that decision sets with larger SVR tend to have more branches, disconnected components, or irregularly shaped borders than those with smaller SVR.

A classification tree partitions the sample space into multiple leaf nodes, assigning one class label to each leaf node. The tree should be built to maximize homogeneity of the training sample class labels within nodes. This motivates the following definition.

Let $p_{0}$ and $p_{1}$ represent the probabilities of belonging to the majority and minority class, respectively, within some branch of the tree. Ideally, splits of the tree are chosen so that, after splitting, $p_{0}$ and $p_{1}$ move closer to 0 or 1 and further from 1/2. Many different tree building algorithms use impurity to measure the quality of a split; for example, CART uses Gini impurity and C4.5 uses entropy, which is effectively a type of impurity measure. In the remainder of the paper, the term ‘impurity function’ refers to the Gini impurity. That is, $\phi(p_{0},p_{1})=1-p_{0}^{2}-p_{1}^{2}$.

Let $A_{1},A_{2},\ldots,A_{m}$ be the leaf nodes of a classification tree $T$ and let $z_{j}\in\{0,1\}$ be the predictive class label for node $A_{j}$, for $j=1,\ldots,m$. Let $\mathbb{P}$ be the weighted probability measure defined in section 2.1. Then the impurity of leaf node $A_{j}$ is $I(A_{j},\mathbb{P})=\phi(\mathbb{P}(Y=0|X\in A_{j}),\mathbb{P}(Y=1|X\in A_{j}))$. The impurity of node $A_{j}$ measures the class homogeneity in $A_{j}$, but does not depend on the predictive class label $z_{j}$. Let $\tilde{z}_{j}=\mathbbm{1}_{\{\mathbb{P}(Y=1|X\in A_{j})\geq 1/2\}}$ denote the dominant class label in $A_{j}$ under weighted measure $\mathbb{P}$. We define a signed impurity taking into account $z_{j}$ as

Signed impurity serves as a proxy to classification accuracy. If the predictive class label $z_{j}$ matches the dominant class label $\tilde{z}_{j}$ in node $A_{j}$, the signed impurity of node $A_{j}$ is equal to the impurity of node $A_{j}$ and is no greater than $1/2$. Otherwise, an extra penalty of $1-2I(A_{j},\mathbb{P})$ is applied. It is easy to see $1-2I(A_{j},\mathbb{P})=[1-2\mathbb{P}(Y=0|X\in A_{j})]^{2}$. In other words, the signed impurity uses quadratic loss instead of the absolute value loss function of classification accuracy. Taking a weighted average of the signed impurities across the leaf nodes, one obtains the tree impurity and signed tree impurity.

The SVR-Tree classifier is the minimizer of the weighted average of signed tree impurity and surface-to-volume ratio. Letting $\mathscr{T}$ be the collection of possible trees, the SVR-Tree classifier is defined as

where $\lambda_{n}$ is a penalty. The unknown probability measure $\mathbb{P}$ is replaced with the empirical measure $\mathbb{P}_{n}$ that assigns mass $1/n$ to each training sample $(X_{i},Y_{i}),1\leq i\leq n$. Unfortunately, without restricting the space of trees $\mathscr{T}$, optimization problem (1) is intractable. In the following subsection, we introduce an iterative greedy search algorithm that limits the size of $\mathscr{T}$ in each step to efficiently obtain a tree having provably good performance.

The SVR-Tree Algorithm is designed to find a nearly optimal SVR-Tree classifier. SVR-Tree proceeds in a greedy manner. We begin with the root node. At each step, we operate on one leaf node of the current tree, splitting it into two new leaf nodes by finding the solution of (1). The node to split at each step is uniquely specified by a breadth-first searching order. After splitting, the tree is updated and the node to split in the next step will be specified. The process stops when further splitting of leaf nodes either does not improve the loss or a prespecified maximum number of leaf nodes is achieved.

We first describe how to split a current leaf node to improve the solution to (1). Suppose the current tree is $T$ and the node to split is $A$, with $n^{\prime}$ training samples. For each feature $j$, sort all samples in $A$ by increasing order of the $j$th feature as $X[j]_{j_{1}},X[j]_{j_{2}},\ldots,X[j]_{j_{n^{\prime}}}$. We only allow splits to occur at $(X[j]_{j_{i}}+X[j]_{j_{i+1}})/2,\;1\leq i\leq n^{\prime}-1,\;1\leq j\leq d$, the midpoint of two adjacent values of each feature. The total number of different splits is no more than $(n^{\prime}-1)d$. After each such split of $A$, we keep all other leaf nodes unchanged while allowing all $4$ different class label assignments at the two new daughter nodes of $A$. The current set of trees $\mathscr{T}$ to choose from in optimizing (1) includes the initial $T$ and all the split trees described above. The cardinality of $\mathscr{T}$ is no more than $1+4(n^{\prime}-1)d$, a linear order of $n^{\prime}$. We compute the risk for all $T\in\mathscr{T}$ to find the minimizer. If the initial $T$ is the risk minimizer, we do not make any split in this step and mark the node $A$ as “complete”. Any node marked as complete will no longer be split in subsequent steps.

It remains to specify the ‘breadth-first’ searching order determining which node to split in each step. Let depth of a node be the number of edges to the root node, which has depth 0. Breadth-first algorithms explore all nodes at the current depth before moving on (Cormen et al. 2009, chapter 22.2). To keep track of changes in the tree, we use a queue¹¹1A queue is a dynamic set in which the elements are kept in order and the principal operations on the set are the insertion of elements to the tail, known as enqueue, and deletion of elements from the head, known as dequeue. See chapter 10.1 of Cormen et al. (2009) for details.. We begin our algorithm with a queue where the only entity is the root node. At each step, we remove the node at the front terminal of the queue, and split at this node as described in the previous paragraph. If a split tree is accepted as the risk minimizer over the current set $\mathscr{F}$, we enqueue two new leaf nodes; otherwise, the unsplit tree is the risk minimizer over the current set $\mathscr{F}$, so we don’t enqueue any new node. The nodes in the front of the queue have the lowest depth. Therefore, our algorithm naturally follows a breadth-first searching order. We preset the maximal number of leaf nodes as $\bar{a}_{n}$. The process is stopped when either the queue is empty, in which case all the leaf nodes are marked as complete, or the number of leaf nodes is $\bar{a}_{n}$. On many datasets, Algorithm 1 will stop before reaching the maximal number of leaf nodes $\bar{a}_{n}$. The upper bound is necessary in certain circumstances, since our algorithm, like the majority of practical tree algorithms, is greedy and not guaranteed to find the global minimum. Provided we can solve the global minimum, the upperbound $\bar{a}_{n}$ is no longer required, as shown in Theorem 2 and discussed thereafter.

Our SVR-Tree algorithm has a coarse to fine tree building style, tending to first split the sample space into larger pieces belonging to two different classes, followed by modifications to the surface of the decision set to decrease tree impurity and SVR. The steps are sketched in Algorithm 1, where feature selection steps are marked as optional. A more detailed and rigorous version is in Section 4.1 of the supplementary material.

The average time complexity of Algorithm 1 is $O(dn\log n)$, which is the same as many tree algorithms like CART and C4.5. A detailed analysis of computational complexity is available at Section 4.2 of the supplementary material.

Let the classification risk under measure $\mathbb{P}$ be $R(f)=\mathbb{E}|Y-f(X)|$ and its empirical version under measure $\mathbb{P}_{n}$ be $R_{n}(f)=\mathbb{E}_{n}|Y-f(X)|$. Let $\mathscr{F}$ be the collection of all measurable functions from $\Omega$ to $\{0,1\}$. Then the oracle classifier and oracle risk can be defined as $f^{*}=\arg\min_{f\in\mathscr{F}}R(f)$ and $R^{*}=R(f^{*})$, respectively. We define the consistency of a sequence of classifiers based on the excess risk comparing to oracle risk.

In the case when $\mathbb{P}(\{X\in\Omega:\eta(X)=1/2\})=0$, consistency of $f_{n}$ is equivalent to requiring $\lim_{n\to\infty}\mathbb{E}|f_{n}-f^{*}|=0$ almost surely. For any hyperrectangle $A\subset\Omega$, denote the component-wise conditional expectation of $A$ as $\eta_{A,j}(X[j])=\mathbb{E}(Y|X[j],X\in A)$. To ensure the consistency of Algorithm 1, we need the following identifiability condition.

Condition 1 is indispensable for proving the consistency of our SVR regularized tree classifiers without requiring the diameter of each leaf node to go to zero. This is because CART-type algorithms can only make splits based on the component-wise conditional expectation. If all the component-wise conditional expectations $\eta_{A,j}(X[j])$ are constants but the overall conditional expectation $\eta(x)$ varies in $x$, then the problem is not identifiable to CART-type split rules. Condition 1 can also be viewed as a relaxed version of Condition (H1) in Scornet et al. (2015) who studied the consistency of random forest regression. Their Condition (H1) requires that the mean of $Y$ given $X$ follows an additive model in the regression tree setup. An analogous condition to their (H1) for our classification tree setup would require $\eta(x)$ to be an additive function, which would imply our Condition 1.

Denote the tree obtained from Algorithm 1 as $\hat{T}_{n}$. Theorem 1 shows $\hat{T}_{n}$ is consistent under mild conditions.

We now consider the empirical risk minimizer over a class of trees under the SVR constraint and derive the rate of convergence for this empirical risk minimizer. This empirical risk minimizer can be considered as an idealized classifier.

We first introduce the family of SVR constrained classifiers. For ease of notation, for any classifier $f$, we denote its decision set by $\Omega_{1}(f)=\{x\in\Omega:f(x)=1\}$. Define $\mathscr{F}_{0}$ as the family of all possible classifiers generated from trees with finite depth: $\mathscr{F}_{0}=\left\{f:\Omega\to[0,1]:\Omega_{1}(f)\;\;\text{is a finite union of hyperrectangles}\right\}.$ For $\gamma>0$, the family of SVR constrained classifiers $\mathscr{F}_{\gamma}$ is defined as

where $A\operatorname*{\bigtriangleup}B=(A\cap B^{c})\cup(A^{c}\cap B)$ denotes the set difference between two generic sets $A$ and $B$. The elements of $\mathscr{F}_{\gamma}$ are constrained by SVR in the sense that the surface area of $\Omega_{1}(f)$ can decrease at most proportionally to the change in its volume. The parameter $\gamma$ is set to be no smaller than $2d$ to prevent $\mathscr{F}_{\gamma}$ from being empty. The definition of $\mathscr{F}_{\gamma}$ matches the intuition in Algorithm 1 where SVR in every leaf node is checked. Moreover, the following proposition reveals that the regularized risk minimizer of all trees over the true measure, provided it exists, always lies in the family $\mathscr{F}_{\gamma}$. Therefore, in the subsequent analysis, we will focus on the effect of $\gamma$ on the convergence of excess risk since it plays an equivalent role to $\lambda$ in the minimization problem (1).

The family $\mathscr{F}_{\gamma}$ only contains tree classifiers and is not closed. It is desirable to consider the class of all classifiers that can be well approximated by tree classifiers. Let $d_{H}(A,B)$ be the Hausdorff distance between two generic sets $A$ and $B$. We define the closure of $\mathscr{F}_{\gamma}$ with respect to Hausdorff distance of decision sets as

The elements of $\overline{\mathscr{F}_{\gamma}}$ have a well-defined surface area as shown in Proposition 2.

The proof of Proposition 1 and 2 are available in the supplementary material. To better control the rate of convergence of excess risk, we also need the following margin condition.

Condition 2 is essentially Assumption (A1) in Tsybakov (2004), which is known as the Tsybakov’s margin condition and widely used in classification problems for obtaining fast convergence rate of excess risk (Tsybakov, 2004; Audibert and Tsybakov, 2007). Condition 2 holds as long as $\mathbb{P}(|\eta(X)-1/2|\leq t)\leq C_{\eta}t^{1/(\kappa-1)}$ for all $t\in(0,t^{*})$ and some constants $C_{\eta}>0$ and $t^{*}\in(0,1/2)$; see Proposition 1 in Tsybakov (2004). Under Condition 2, our main theorem states the rate of convergence for the empirical risk minimizer over $\mathscr{F}_{\gamma}$.

Theorem 2 provides an upper bound in (4) for the rate of convergence of the excess risk from the empirical risk minimizer $\hat{T}_{n,\gamma}$ among all SVR constrained tree classifiers in $\mathscr{F}_{\gamma}$ to the theoretically best possible classifier $f^{*}$ in $\overline{\mathscr{F}_{\gamma}}$ with a well-defined surface area. Because we have limited restrictions on the split locations of $\hat{T}_{n,\gamma}$ apart from belonging to $\mathscr{F}_{\gamma}$, it is possible for a split to land directly on an observed sample under the empirical measure. In such situations, we allow the tree of $\hat{T}_{n,\gamma}$ to assign the sample to either leaf node. Hence, the leaf nodes of $\hat{T}_{n,\gamma}$ can be open, closed, or half open half closed. On the other hand, the theoretically best classifier $f^{*}$ can lie in the much larger family of $\overline{\mathscr{F}_{\gamma}}$. Although the classifiers from $\mathscr{F}_{\gamma}$ are tree classifiers, there is no limitation on how many leaf nodes they can have. Therefore, they can approximate decision sets with smooth boundaries, for example a $d$-dimensional ball. In fact, by adjusting $\gamma$, $\overline{\mathscr{F}_{\gamma}}$ will contain most classifiers with regularly shaped decision sets.

The rate of convergence for the excess risk in the upper bound (4) is $O((\log n/n)^{\frac{1}{d+1-1/\kappa}})$, which is the same as the minimax rate of set estimation on the family of sets with first order differentiable boundaries as in Mammen and Tsybakov (1995). Although Mammen and Tsybakov (1995) do not use the margin condition and hence the term $1/\kappa$ does not appear explicitly in their rates, their results will yield the same rate as ours up to logarithm factors if the margin condition is applied; see for example, Theorem 4 of Scott and Nowak (2006). Furthermore, in the upper bound (4) in Theorem 2, we have explicitly characterized the effect of the SVR regularization $\gamma$ from the set $\mathscr{F}_{\gamma}$. By definition, the SVR constraint in $\mathscr{F}_{\gamma}$ becomes weaker as $\gamma$ increases. As expected, the upper bound in (4) increases with $\gamma$ given the increasing complexity of the set $\mathscr{F}_{\gamma}$. A direct implication of this upper bound is that if the true tree classifier belongs to a family $\overline{\mathscr{F}_{\gamma}}$ with a smaller $\gamma$, i.e. a smaller SVR ratio, then the excess risk of the empirical risk minimizer $\hat{T}_{n,\gamma}$ also tends to be smaller.

Theorem 2 is related to the literature on classification risk of decision trees, but with important differences. In general, the rate of convergence for the excess risk depends on two assumptions: the margin condition as in our Condition 2 and the complexity, or the $\epsilon$-entropy, of the family of decision sets (Scott and Nowak, 2006). Suppose the $\epsilon$-entropy is $(1/\epsilon)^{\rho}$ for some $\rho>0$. If $\rho<1$, then together with a suitable margin condition like Condition 2, the rate of convergence can be faster than $O(n^{-1/2})$ or even faster than $O(n^{-1})$ (Tsybakov, 2004; Audibert and Tsybakov, 2007). If $\rho\geq 1$, then the rate of convergence is typically of order $n^{-\frac{1}{\rho+c}}$ with $c$ being a constant independent of $\rho$ (Mammen and Tsybakov, 1995). Although it is possible to slightly improve the constant $c$ by refining the margin condition, the overall rate of convergence is still governed by the $\epsilon$-entropy if $\rho$ is very large. Therefore the major objective of our research is to find a suitable family of sets with controllable $\epsilon$-entropy as well as a practically feasible algorithm. This is not easy, because there are limited families of sets having known $\epsilon$-entropy, including convex sets and sets with smooth boundaries. Both smoothness and convexity impose strong assumptions on the local properties of the boundary $\partial\Omega_{1}(f)$. In contrast, we propose to consider the family of SVR constrained sets $\mathscr{F}_{\gamma}$ as a new family of decision sets, which directly imposes a simple and intuitive assumption on the shape of decision sets and additionally has a tractable $\epsilon$-entropy.

Scott and Nowak (2006) also noticed that the family of sets with smooth boundaries is not very realistic for practical problems. They proposed a family of decision sets named the “box-counting class” which satisfies the conclusion of our Lemma 5. However, they did not further characterize the behavior of sets in their class, and hence they must compute the tree for all smallest dyadic splits and then merge all these trees bottom-up, which can be regarded as an exhaustive search in the lowest split level. This leads to a computational complexity $O(dnL^{d}\log(nL^{d}))$, with $L$ being the number of dyadic splits. The complexity will become intractable when $d$ is large, with the authors noting that $d\geq 10$ will pose a problem. Scott and Nowak (2006) also proposed an alternative to the Tsybakov’s margin condition (Condition 2) and obtained a faster convergence rate in some specific situations, such as when $\Omega$ lies in a low dimensional manifold. However, their alternative condition directly bounds the excess error between a possible dyadic tree and the oracle classifier, which is much stronger than the standard margin condition we have used.

The proof of Theorem 2 is in the Appendix. The key idea is to construct an $\epsilon$-net on $\mathscr{F}_{\gamma}$ under a symmetric set difference from the true measure and to show that this $\epsilon$-net is also a $2\epsilon$-net under a symmetric set difference from the empirical measure with high probability. This nontrivial property is the reason why we can derive the rate of convergence for the empirical risk minimizer over the whole family of $\mathscr{F}_{\gamma}$ rather than just for the minimizer over an $\epsilon$-net of this family, as adopted by some previous classification literature (Mammen and Tsybakov, 1995; Tsybakov, 2004).

We test our method on 12 datasets from the UCI Machine Learning Repository (Dua and Graff, 2017) and KEEL-dataset repository (Alcalá-Fdez et al., 2011), varying in size, number of features and level of imbalance. For datasets with three or more classes, classes are combined to form binary class datasets. Table 2 gives an overview of the datasets; detailed descriptions and preprocessing of these datasets are available in Section 5.1 of the supplementary material.

We test the performance of SVR-Tree, SVR-Tree with feature selection, CART (Breiman et al., 1984) with duplicated oversampling, CART with SMOTE (Chawla et al., 2002), CART with Borderline-SMOTE (Han et al., 2005), CART with ADASYN (He et al., 2008) and Hellinger Distance Decision Tree (Cieslak et al., 2012) on all 12 datasets. Features are linearly transformed so that samples lie in $[0,1]^{d}$.

We use $3\times 5$ nested stratified cross validation to evaluate the out-of-sample performance of all methods. The nested cross validation has two layers: the inner layer is used to choose tuning parameters and the outer layer is used to evaluate the out-of-sample performance. For each method and each dataset, we run the nested cross validation procedure 20 times. In each run, we randomly partition the whole dataset into three stratified folds²²2the proportions of samples of each class are roughly the same in all folds. and run three times. Each time one of the three folds is selected as the testing set and the other two folds are training sets. On the training sets, we use 5-fold stratified cross validation to choose the tuning parameter. That is, we further divide the training set into five folds and run for five times. Each time we use four folds as (inner) training sets and the other fold for validation. We define the cross-validation TPR, TNR in the same manner as the cross-validation accuracy and use the cross validation TPR, TNR to compute the cross-validation F-measure. The tuning parameter with the highest cross validation F-measure is selected. We then train the model with the selected tuning parameter on the whole training set and evaluate its performance on the test set. The cross validation accuracy, precision, TPR, F-measure and G-mean are recorded. The mean and standard error of these statistics from 20 nested cross validation runs are reported in Table 3.

SVR-Tree with and without feature selection are described in Algorithm 1. The weight for the minority class, $\alpha$, is set to be the largest integer that makes the total weight of the minority class no greater than the total weight of the majority class. The maximal number of leaf nodes $\bar{a}_{n}$ is $2\sqrt{n}$. The penalty parameter $\lambda_{n}$ for SVR is chosen from a geometric sequence in $[2^{0},2^{10}]\times 10^{-3}\times n^{-1/3}$ and the value with the highest F-measure across 20 runs is selected. For SVR-Tree with feature selection, the constant $c_{0}$ in equation (2) is fixed to $c_{0}=4$. In practice, the results are insensitive to $c_{0}$.

For the other methods except Hellinger distance decision tree, we first over sample the minority class samples, such that the number of minority samples are multiplied by the same weight $\alpha$ used for SVR tree. We than build the CART tree on the over sampled dataset and prune it. The pruning parameter of CART is selected to maximize the F-measure. By the algorithm proposed by Breiman et al. (1984), the range from which to choose the pruning parameter will be available after we build the tree and does not need to be specified ahead of time.

For duplicated oversampling, we sample each minority class sample $\alpha-1$ times where $\alpha$ is the weight used for SVR tree. For SMOTE, the number of nearest samples is set as $k=5$. For Borderline-SMOTE, we adopt the Borderline-SMOTE1 of Han et al. (2005), with the number of nearest samples $k=5$. For both SMOTE and Borderline-SMOTE, if $\alpha-1\geq k$, some nearest neighbors may be used multiple times to generate synthetic samples, such that the total weight of minority class samples of these oversampling methods are the same as that of SVR tree. For ADASYN, if we denote the number of majority class samples as $n_{0}$ and the number of minority class samples as $n_{1}$, then the parameter $\beta$ is set to be $\beta=\alpha n_{1}/n_{0}$.

For Hellinger distance decision tree, we directly call its java implementation available at Weka software (https://www.cs.waikato.ac.nz/ml/weka/). Although it is claimed that the Hellinger distance tree is insensitive to imbalance, their current implementation occasionally classifies all samples into a single class. We set the default leaf prediction strategy as “Naive Bayes” since it works well on most datasets. However, if the algorithm classifies all samples into a single class, we will set the leaf prediction strategy as “Majority Voting”. The third leaf prediction strategy “Naive Bayes Adapative” always produces the same results as one of the other two strategies in our experiments.

We compute the mean and standard error of accuracy, precision, TPR, F-measure and G-mean across the 20 nested cross validations. Due to limited space, results of 4 representative datasets are shown in Table 3 with the remaining results in Section 5.2 of the supplementary material. If a method classifies all samples into the majority class, precision is not well-defined and we simply set it to be zero. In the column “Method”, SVR = SVR-Tree, SVR-Select = SVR-Tree with feature selection, Duplicate = CART with duplicated oversampling, SMOTE = CART with SMOTE, BSMOTE = CART with Borderline-SMOTE, ADASYN = CART with ADASYN and HDDT = Hellinger Distance Decision Tree. For each dataset and evaluation measure, the method with the highest mean value ranks first and is highlighted in bold. As suggested by Brazdil and Soares (2000), the average rankings of all 12 datasets are displayed in Table 3 to evaluate the overall performance of each method across all datasets. If two methods are tied, the ranking is set to the average.

The results in Table 3 show that oversampling based methods generally perform well in accuracy and precision, with SMOTE the best of these methods. However, SVR and SVR-select outperform the oversampling methods in the rankings of TPR, F-measure and G-mean on many datasets and on average. The behavior of HDDT is unstable across datasets, being competitive in TPR and G-mean for some datasets but sometimes assigning all samples to the majority class. Since all methods (except duplicated sampling) are built on ideal theoretical assumptions, their practical performance is typically data-dependent. For example, SMOTE is outperformed by SVR-select in all measures for the Segment dataset, while the opposite happens for the Page dataset.