---
abstract: 'Classification algorithms face difficulties when one or more classes have limited training data. We are particularly interested in classification trees, due to their interpretability and flexibility. When data are limited in one or more of the classes, the estimated decision boundaries are often irregularly shaped due to the limited sample size, leading to poor generalization error. We propose a novel approach that penalizes the Surface-to-Volume Ratio (SVR) of the decision set, obtaining a new class of SVR-Tree algorithms. We develop a simple and computationally efficient implementation while proving estimation and feature selection consistency for SVR-Tree. SVR-Tree is compared with multiple algorithms that are designed to deal with imbalance through real data applications.'
author:
- |
    Yichen Zhu[^1]\
    Department of Statistical Science, Duke University\
    and\
    David B. Dunson[^2]\
    \
    Department of Statistical Science, Duke University
bibliography:
- 'IBbib.bib'
title: '**Classification Trees for Imbalanced and Sparse Data: Surface-to-Volume Regularization**'
---

1

[1]{}

0

[1]{}

[**Classification Trees for Imbalanced and Sparse Data: Surface-to-Volume Regularization**]{}

[*Keywords:*]{} CART, Categorical data, Decision boundary, Feature Selection, Shape penalization, Variable selection

Introduction
============

We are interested in the common setting in which one has a set of training data $\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,\ldots,J-1\}$ a class label. The goal is to estimate a classifier $f: \Omega \to \{0,\ldots,J-1\}$, which outputs a class label given an input feature vector. This involves partitioning the feature space $\Omega$ into subsets having different class labels, as illustrated in Figure 1. Classification trees are particularly popular to their combined flexibility and interpretability. Competitors like deep neural networks (DNN; @schmidhuber2015deep) often have higher accuracy in prediction, but are essentially uninterpretable black boxes.

Our focus is on the case in which $n_j = \sum_{k=1}^n \bm{1}_{\{Y_i = j\}}$ is small, for one or more $j \in \{0,\ldots,J-1\}$. For simplicity in exposition, we assume $J=2$, so that there are only two classes. Without loss of generality, suppose that $j=0$ is the majority class, $j=1$ is the minority class, and call set $\{x\in\Omega: f(x)=1\}$ the decision set (of the minority class). Hence, $n_1$ is relatively small compared to $n_0$ by this convention.

To illustrate the problems that can arise from this imbalance, we consider a toy example. Let the sample space of $X$ be $\Omega = [0,1]\times[0,1]\subset \mathbb{R}^2$. Let the conditional distribution of $X$ given $Y$ be $X|Y=1 \sim U([0,0.75]\times[0.25,0.75])$, $X|Y=0 \sim U(\Omega)$. We generate a training data set with $5$ minority samples and $200$ majority samples. The estimated decision sets of unpruned CART and optimally pruned CART [@breiman1984classification] are shown in Figure (a) and (b), respectively. Minority samples are given weight 32 while majority samples are given weight 1 to naively address the imbalance. Both decision sets are inaccurate, with unpruned CART overfitting and pruned CART also poor.

Imbalanced data problems have drawn substantial interest; see [@haixiang2017learning], [@he2008learning], [@krawczyk2016learning] and [@fernandez2017insight] for reviews. Some early work relied on random under- or over-sampling, which is essentially equivalent to modifying the weights and cannot address the key problem. [@chawla2002smote] proposed SMOTE, which instead creates synthetic samples. For each minority class sample, they create synthetic samples along the line segments that join each minority class sample with its k nearest neighbors in the minority class. Building on this idea, many other synthetic sampling methods have been proposed, including ADASYN [@he2008adasyn], Borderline-SMOTE [@han2005borderline], SPIDER [@stefanowski2008selective], safe-level-SMOTE [@bunkhumpornpat2009safe] and WGAN-Based sampling [@wang2019wgan]. These synthetic sampling methods have been demonstrated to be relatively effective.

However, current understanding of synthetic sampling is inadequate. [@chawla2002smote] motivates SMOTE as designed to “create large and less specific decision regions”, “rather than smaller and more specific regions”. Later papers fail to improve upon this heuristic justification. Practically, the advantage of synthetic sampling versus random over-sampling diminishes as the dimension of the feature space increases. In general, for each minority sample, we require at least $d$ synthetic samples to fully describe its neighborhood. This is often infeasible due to the sample size of the majority class and to computational complexity. Hence, it is typical to fix the number of synthetic samples regardless of the dimension of the feature space [@chawla2002smote], which may fail to “create large and less specific decision regions” when the dimension is high.

Motivated by these issues, we propose to directly penalize the Surface-to-Volume Ratio (SVR) of the decision set. A primary issue with imbalanced data is estimating a decision set consisting of small neighborhoods around each minority class sample. By penalizing SVR we favor regularly shaped decision sets much less subject to such over-fitting. With this motivation, we propose a new class of SVR-Tree algorithms.

The rest of the paper is organized as follows. Section 2 describes our methodology. Section 3 provides theory on estimation and feature selection consistency. Section 4 presents numerical studies for real datasets. Section 5 contains a discussion, and proofs are included in an Appendix.

[0.32]{} ![Decision sets for different methods. Red crosses denote minority class samples, while blue points denote majority class samples. Rectangles with dashed frames denote the support of minority class samples, while rectangles filled with green color denote the minority class decision set.[]{data-label=""}](toy_CART_unpruned.png "fig:"){width="\textwidth"}

[0.32]{} ![Decision sets for different methods. Red crosses denote minority class samples, while blue points denote majority class samples. Rectangles with dashed frames denote the support of minority class samples, while rectangles filled with green color denote the minority class decision set.[]{data-label=""}](toy_CART_pruned.png "fig:"){width="\textwidth"}

[0.32]{} ![Decision sets for different methods. Red crosses denote minority class samples, while blue points denote majority class samples. Rectangles with dashed frames denote the support of minority class samples, while rectangles filled with green color denote the minority class decision set.[]{data-label=""}](toy_SVRTree.png "fig:"){width="\textwidth"}

Methodology
===========

We first introduce the definition of surface-to-volume ratio (SVR) and tree impurity, and then define SVR-Tree as the minimizer of a weighted average of tree impurity and SVR. We then state the algorithm to estimate this tree from training data $\mathscr{D}_n = \{(X_i, Y_i)\}_{i=1}^n$. We assume readers have basic knowledge of tree-based classifiers like CART [@breiman1984classification] and C4.5 [@quinlan2014c4]. In the rest of the paper, the word “tree” refers specifically to classification trees that specify a class label associated with each leaf node.

Notations
---------

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. We denote the $j$th feature of $X$ as $X[j]$. The true distribution of $(X_i, Y_i)$ is denoted by $\mathbb{P}$, while the empirical distribution, which assigns mass $1/n$ to each training data point, is denoted by $\mathbb{P}_n$. For a constant $\alpha>1$, let $\mathbb{P}_\alpha$ modify $\mathbb{P}$ to up weight minority class samples by $\alpha$. That is, for any subset $A\subset \Omega$, $$\mathbb{P}_\alpha(A\times\{1\}) = \frac{\alpha\mathbb{P}(A\times\{1\})}{\mathbb{P}(\Omega\times\{0\})+\alpha\mathbb{P}(\Omega\times\{1\})}, \;\; \;\mathbb{P}_\alpha(A\times\{0\}) = \frac{\mathbb{P}(A\times\{0\})}{\mathbb{P}(\Omega\times\{0\})+\alpha\mathbb{P}(\Omega\times\{1\})}.$$ Similarly, let $\mathbb{P}_{n,\alpha}$ be the weighted version of $\mathbb{P}_n$. To avoid complex subscripts, with some abuse of notation, we also use $\mathbb{P}, \mathbb{P}_\alpha, \mathbb{P}_n, \mathbb{P}_{n,\alpha}$ to denote the corresponding marginal probability measures on $X$. For example, $$\mathbb{P}_\alpha(A) \triangleq \mathbb{P}_\alpha(A\times\{0,1\}) = \frac{\mathbb{P}(A\times\{0\})+\alpha\mathbb{P}(A\times\{1\})}{\mathbb{P}(\Omega\times\{0\})+\alpha\mathbb{P}(\Omega\times\{1\})}.$$ Whether they refer to the joint distribution of $(X, Y)$ or the marginal distribution of $X$ should be clear from the context. 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 $\mu>0$, $\mathbb{P}\left((\sum_{i=1}^n X_i)/n >\mu\right)$ denotes the probability of the event $\{\{(X_i, Y_i)\}_{i=1}: (\sum_{i=1}^n X_i)/n > \mu\}$. We use $\mathbb{E}$ for expectations over $\mathbb{P}$ and $\mathbb{E}_n$ for expectations over $\mathbb{P}_n$.

Surface-to-Volume Ratio
-----------------------

For all $d \in \mathbb{N}$, define a $d$-dimensional measure space as $(\mathbb{R}^d, \mathscr{B}, \mu)$, where $\mathscr{B}$ is the collection of Borel sets, and $\mu$ is Lebesgue measure. For any measurable closed set $A \in \mathscr{B}$, we define its volume as Lebesgue measure of set $A$: $V(A) = \mu(A)$. We define the surface as the $d-1$ dimensional Lebesgue measure of the boundary of $A$: $S(A) = \mu_{d-1}(\partial A).$ 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 ball has the smallest SVR, while sets having multiple disconnected subsets and/or irregular boundaries have relatively high SVR.

#### Surface-to-Volume Ratio of a Classification Tree

For training data $\mathscr{D}_n$, we define a closed bounded sample space $\Omega\subset \mathbb{R}^d$ such that the support of $X$ is a subset of $\Omega$. A classification tree $T$ divides the sample space $\Omega \subset \mathbb{R}^d$ into two disjoint subsets $\Omega_0$, $\Omega_1$, where $\Omega_0 \cup \Omega_1= \Omega$. The tree $T$ predicts a new sample $X^*$ belongs to class 0 if $X^* \in \Omega_0$, and class 1 if $X^* \in \Omega_1$. The surface-to-volume ratio of a classification tree is defined as the surface-to-volume-ratio of set $\Omega_1$: $r(T) = r(\Omega_1).$

Impurity Function and Tree Impurity
-----------------------------------

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.

An impurity function $\phi(\cdot, \cdot)$ is defined on the set of pairs $(p_0, p_1)$ satisfying $p_0\ge0, p_1\ge0$, $p_0+p_1=1$ with the properties (i) $\phi(\cdot, \cdot)$ achieves its maximum only at $(1/2, 1/2)$; (ii) $\phi(\cdot, \cdot)$ achieves its minimum only at $(1, 0), (0,1)$; (iii) $\phi(\cdot, \cdot)$ is symmetrical in $(p_0, p_1)$, i.e., $\phi(p_0, p_1) = \phi(p_1, p_0)$.

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.

When data are imbalanced, it is important to modify the definition of impurity to account for the fact that $p_1$ is much smaller than $p_0$. With this in mind, we propose the following weighted impurity function.

\[weighted impurity\] Letting $\phi(\cdot, \cdot)$ be an impurity function, a weighted impurity function with weight $\alpha$ for the minority class is defined as $$\varphi_\alpha(p_0, p_1) = \phi\Big(\frac{p_0}{p_0+\alpha p_1}, \frac{\alpha p_1}{p_0 + \alpha p_1}\Big).$$

In the remainder of the paper, the term ‘impurity function’ refers to $\varphi_\alpha$ in Definition \[weighted impurity\] with $\alpha\ge1$ and the function $\phi(\cdot,\cdot)$ refers to the Gini impurity. That is, $$\varphi_\alpha(p_0, p_1) = 1 - \Big(\frac{p_0}{p_0+\alpha p_1}\Big)^2 - \Big(\frac{\alpha p_1}{p_0 + \alpha p_1}\Big)^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 a probability measure over $\Omega\times\{0,1\}$. Then the impurity of leaf node $A_j$ is $I_\alpha(A_j, \mathbb{P}) = \varphi_\alpha (\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)\ge1/(1+\alpha)\}}$ denote the dominant class label in $A_j$ under weight $\alpha$. We define a signed impurity taking into account $z_j$ as $$\tilde{I}_\alpha(A_j, \mathbb{P}) = \mathbbm{1}_{\{z_j=\tilde{z}_j\}} I_\alpha(A_j, \mathbb{P}) + \mathbbm{1}_{\{z_j\ne\tilde{z}_j\}} (1-I_\alpha(A_j, \mathbb{P})).$$ 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 is applied. Taking a weighted average of the signed impurities across the leaf nodes, one obtains the tree impurity and signed tree impurity.

\[tree impurity\] Let $T$ be a tree and $A_1, A_2, \ldots A_m$ be all the leaf nodes of this tree. Up-weighting the minority class by $\alpha$, the tree impurity of $T$ is $$I_\alpha(T, \mathbb{P}) = \sum_{j=1}^m \mathbb{P}_\alpha(X\in A_j) I_\alpha(A_j, \mathbb{P}),$$ where $\mathbb{P}_\alpha(X\in A_j)$ is the weighted version of $\mathbb{P}$ defined in section 2.1.

\[signed tree impurity\] Under the notation of Definition \[tree impurity\], the signed tree impurity is $\tilde{I}_\alpha(T, \mathbb{P}) = \sum_{j=1}^m \mathbb{P}_\alpha(X\in A_j) \tilde{I}_\alpha(A_j, \mathbb{P}).$

SVR-Tree Classifiers
--------------------

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 formally defined as $$\label{Tree Impu}
\hat{T} = \operatorname*{argmin}_{T\in\mathscr{T}}[\tilde{I}_\alpha(T,\mathbb{P}_n) + \lambda_n r(T)],$$ 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\le i\le n$. Unfortunately, without restricting the space of trees $\mathscr{T}$, optimization problem (\[Tree Impu\]) 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
----------------------

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, partitioning it into two new leaf nodes by finding the solution of (\[Tree Impu\]). The node to partition at each step is uniquely specified by a breadth-first searching order. After partitioning, the tree is updated and the node to partition 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 (\[Tree Impu\]). Suppose the current tree is $T$ and the node to partition is $A$, with $n'$ 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'}$. We only allow partitions to occur at $(X[j]_{j_i}+ X[j]_{j_{i+1}})/2, \;1\le i\le n'-1,\; 1\le j\le d$, the midpoint of two adjacent values of each feature. The total number of different partitions is no more than $(n'-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 (\[Tree Impu\]) include the initial $T$ and all the partitioned trees described above. The cardinality of $\mathscr{T}$ is no more than $1 + 4(n'-1)d$, a linear order of $n'$. 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 partition in this step and mark the node $A$ as “complete”. Any node marked as complete will no longer be partitioned in subsequent steps.

It remains to specify the ‘breadth-first’ searching order determining which node to partition 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 (@cormen2009introduction, chapter 22.2). To keep track of changes in the tree, we use a queue[^3]. 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 partition at this node as described in the previous paragraph. If a partitioned tree is accepted as the risk minimizer over the current set $\mathscr{F}$, we enqueue two new leaf nodes; otherwise, the unpartitioned 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$.

Our SVR-Tree algorithm has a coarse to fine tree building style, tending to first partition 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 the last section of supplemental material.

Input training data $\{(X_i, Y_i)\}_{i=1}^n$, impurity function $f(\cdot)$, weight for minority class $\alpha$, SVR penalty parameter $\lambda_n$, and maximal number of leaf nodes $\bar{a}_n\in\mathbb{N}$. Let ${\mathrm}{node\_queue}$ be a queue of only root node

#### Optional Step for Feature Selection

It is likely that some features will not help to predict class labels. These features should be excluded from our estimated tree. Under some mild conditions, a split on a redundant feature has minimal impact on the tree impurity compared to a partition in a non-redundant feature. Thus feature selection can be achieved by thresholding. Suppose we are partitioning node $A$ into two new leaf nodes $A_1, A_2$. Then the (unsigned) **tree impurity decrease** after this partition is defined as: $$\Delta I_\alpha(T, \mathbb{P}_n) = \mathbb{P}_{n,\alpha}(A) [I_\alpha(A, \mathbb{P}_n) - I_\alpha(A_1,\mathbb{P})\mathbb{P}_{n,\alpha}(A_1|A) -  I_\alpha(A_2,\mathbb{P})\mathbb{P}_{n,\alpha}(A_2|A)].$$ Let $J_0\subset \{1, 2, \ldots d\}$ be the indices of features that have been partitioned in previous tree building steps. Given that we are partitioning on node $A$, let $\Delta I_0$ be the maximal tree impurity decrease over all partitions in feature $X[j], j\in J_0$. Then a partition in a new feature $X[j'], j'\not\in J_0$, with tree impurity decrease $\Delta I_\alpha(T, \mathbb{P}_n)$, is accepted if $$\label{impu decr}
\Delta I_\alpha(T, \mathbb{P}_n) \ge \Delta I_0 + c_0\lambda_n,$$ where $c_0$ is a constant independent of the training data. By equation (\[impu decr\]), a partition on a new feature is accepted if its tree impurity decrease is greater than $\Delta I_0$, the tree impurity decrease over all previously partitioned features, plus a threshold term $c_0\lambda_n$. Theoretical support for this thresholding approach is provided in Section 3.

Computational Complexity
------------------------

Recall the number of training samples is $n$ and the number of features is $d$. Denote the depth of the estimated tree as $h$ and let the maximal number of leaf nodes be $\bar{a}_n = O(\sqrt{n})$.[^4] The storage complexity is trivial and is the same as usual decision trees, i.e., $O(dn)$. We analyze the time complexity of Algorithm 1 in this section. We first introduce the approach to compute surface-to-volume ratio, then discuss the time complexity of building the tree.

#### Computing SVR

Suppose in some intermediate state of building the SVR Tree, the current tree has $m$ leaf nodes $R_1, R_2, \cdots R_m$. We already know the surface and volume of the current tree. Now we need to perform a partition at node $R_1$, which has $n'$ samples. Suppose we partition at $X[j] = x_j$ and obtain two child nodes. The volume of the tree after this partition can be computed by adding the volume of the minority class child node(s), which takes $O(d)$ time. The major concern lies in the computation of the surface area. If both child nodes are in the majority class or the minority class, the surface after partitioning is the surface that node $R_1$ is labeled as the majority class or the minority class. It takes $O(d^2)$ time to compute the surface of $R_1$, and $O(md)$ time to compute all the overlapping surface between $R_1$ and $R_j, 2\le j\le m$. Therefore, the time complexity to compute the surface of the tree after partitioning is $O(d^2+md)$.

If one child node belongs to the minority class and the other belongs to the majority class, the problem becomes more complicated. Let $S_{01,j}(x_j)$ be the surface of the partitioned tree if $R_1$ is partitioned at $X[j]=x_j$ and the left child is labeled as $0$ and the right child is labeled as $1$. $S_{10,j}(x_j)$ is similarly defined. Both $S_{01,j}(x_j)$ and $S_{10,j}(x_j)$ are piecewise constant functions whose change points can only exist at borders of $R_j, 2\le j\le m$. Therefore, we first compute the analytical forms of $S_{01,j}(x_j)$ and $S_{10,j}(x_j)$ for all $1\le j\le m$. This requires us to find all the borders of $R_j, 2\le j\le m$, to compute all the overlapping surface between $R_1$ and $R_j, 2\le j\le m$ and to compute the surface of $R_1$ itself. The process of computing the analytical forms of $S_{01}(x_j)$ and $S_{10}(x_j)$ for all $1\le j\le m$, takes $O(d^2+md)$ time. The cost of evaluating $S_{01,j}(x_j)$ and $S_{10,j}(x_j)$ at a specific value $x_j$ can takes as much as $O(m)$ time; but if the samples are pre-sorted for all features, it only takes $O(dm+dn')$ time to evaluate $S_{01}(x_j)$ and $S_{10}(x_j)$, $\forall 1\le j\le m$, at all the possible partition locations of $R_1$. Therefore, it takes $O(d^2+md+n'd)$ time to compute surface area for all the possible partition locations and class label assignments. Similarly, the costs of computing volume for all possible partition locations is $O(n'd)$. Thus for all the possible partition locations and class label assignments at $R_1$, the total cost of computing SVR is $O(d^2+md+n'd)$.

#### Time Complexity of Algorithm 1

Before working on any partitions, we first need to sort the whole dataset for all features, taking $O(dn\log n)$ time. For a node with $n'$ samples and $m$ leaf nodes in the current tree, there are $dn'$ possible partition locations. It takes $O(dn')$ time to compute signed impurity for all possible class label assignments and all partition locations; $O(d^2+md+n'd)$ time to compute surface-to-volume ratio for all possible class label assignments and all partition locations; $O(dn')$ time to find the best partition when all the signed impurities and SVR are already computed. The overall time complexity of finding the best partition at this node is $O(d^2+md+n'd)$. Let $a_n$ be the number of leaf nodes of the tree output by Algorithm 1, with $a_n\le \bar{a}_n = O(\sqrt{n})$. The time complexity is $$O(dn\log n) + \sum_{m=1}^{ a_n} O(d^2+md+n'd) \le O(dn\log n + \sqrt{n}d^2 + nhd),$$ where we use the fact that $\sum_{m=1}^{ a_n} n' \le nh$. This shows the efficiency of Algorithm 1.

Theoretical Properties
======================

In this section, we will discuss the consistency of our classification tree obtained from Algorithm 1 in two aspects: the first is estimation consistency – as sample size goes to infinity, a generalized distance between SVR-Tree and the oracle classifier converges to zero; the other is feature selection consistency – for redundant features that are conditionally independent of $Y$ given the other features, the probability of SVR-Tree excluding these features converges to one.

Estimation Consistency
----------------------

We define a generalized metric on the space of all nonrandom classifiers, introduce classifier risk, and define our notions of classifier consistency.

For any weight $\alpha$ and classifier $f:\Omega \to \{0,1\}$, we define the risk as $$R(f) = \mathbb{E} \left[\alpha \max(Y-f(X),0) + \max(f(X)-Y,0)\right],$$ where the expectation is taken over probability measure $\mathbb{P}$ for random variables $(X,Y)$.

Let $\mathscr{F}$ be the collection of all measurable functions from $\Omega$ to $\{0,1\}$. Then the oracle classifier and minimal risk are defined as $f^* = \arg\min_{f\in\mathscr{F}} R(f)$ and $R^* = R(f^*),$ respectively. Without loss of generality, we assume $\mathbb{P}(\mathbb{E}(Y|X)=1/(1+\alpha))=0$. Then the oracle classifier is unique almost surely. We now define the consistency of a sequence of classifiers based on L1 distance from the oracle classifier.

A sequence of classifiers $f_n$ is consistent if $ \lim_{n\to\infty}  \mathbb{E} |f_n - f^*| = 0.$

Denote the tree obtained from Algorithm 1 as $\hat{T}_n$ and the classifier$:\Omega\to\{0,1\}$ associated with $\hat{T}_n$ as $\hat{f}_n$. Theorem \[consistency\] shows $\hat{f}_n$ is consistent under mild conditions.

\[consistency\] Let $\mathbb{P}$ be absolutely continuous with respect to Lebesgue measure on $\mathbb{R}^d$. Assume $\lim_{n\to\infty}\bar{a}_n = \infty,$ $\lim_{n\to\infty}\lambda_n = 0,$ and $\lim_{n\to\infty}\frac{\bar{a}_n d\log n}{n} = 0.$ Let $\alpha$ be a constant no smaller than one. Then the classifier $\hat{f}_n$ obtained from Algorithm 1 is consistent.

Feature Selection Consistency
-----------------------------

Let $X[-j]$ denote the set of all features except $X[j]$. We say $X[j]$ is redundant if conditionally on $X[-j]$, $Y$ is independent of $X[j]$. We denote $X'$ as the collection of all non-redundant features, and $X''$ as the collection of all redundant features. Under two conditions on the distribution of $Y, X'$ and $X''$, we can show if $\lambda_n$ goes to zero slower than $n^{-1/2}$, the probability of $\hat{T}_n$ excluding all redundant features goes to one. We assume there are $q \;(1\le q < d)$ non-redundant features denoted as $X[j_1], X[j_2], \cdots X[j_q]$. The redundant features are denoted as $X[j_{q+1]}, X[j_{q+2}], \cdots X[j_d]$.

Before stating these two conditions, we need to discuss how a partition can decrease the tree impurity. Suppose we are partitioning on node $A$ at feature $X[j]$, resulting in two new leaf nodes: $A_1 = \{X\in A: X[j] \le x_j\}$ and $A_2 = \{X\in A: X[j] > x_j\}$. Then the weighted conditional expectation of $Y$ in node $A_1, A_2$ is $$\label{p1alpha fs}
p_{h, \alpha} = \frac{\alpha \mathbb{E}(Y|X\in A_h)}{1-\mathbb{E}(Y|X\in A_h) + \alpha\mathbb{E}(Y|X\in A_h)},\quad h=1,2.$$ Thus the impurity of $A_1, A_2$ is $I_\alpha(A_1, \mathbb{P}) = 1 - p_{1, \alpha}^2 - (1-p_{1, \alpha})^2 = 2p_{1, \alpha}(1-p_{1,\alpha}),$ and $I_\alpha(A_2, \mathbb{P}) = 2p_{2,\alpha}(1-p_{2,\alpha}).$ Similarly, denoting the weighted conditional expectation of $Y$ in node $A$ as $p_\alpha$, the impurity of $A$ is $I_\alpha(A,\mathbb{P}) = 2p_\alpha(1-p_\alpha)$. The impurity decrease on node $A$ is $$\label{delta Ialpha}
\Delta I_\alpha(A, \mathbb{P}) = 2p_\alpha(1-p_\alpha) - 2p_{1,\alpha}(1-p_{1,\alpha})\mathbb{P}_\alpha(A_1|A) - 2p_{2,\alpha}(1-p_{2,\alpha})\mathbb{P}_\alpha(A_2|A),$$ Noting $A_1, A_2$ is determined by $x_j$, $\Delta I_\alpha(A, \mathbb{P})$ can be considered as a function of $x_j$. Denoting $\Delta I_\alpha(A,\mathbb{P}) = h_{A,j}(x_j)$, then the maximal impurity decrease at feature $X[j]$ is $$\label{Mj}
M_{A,j} = \max_{x_j\in(x_{j,1},x_{j,2})} h_{A,j}(x_j).$$ The quality of $M_{A,j}$ in reducing the impurity of node $A$ is measured relative to the oracle impurity decrease at node $A$. Suppose we partition node $A$ into measurable sets $A_1$ and $A_2$ satisfying $\mathbb{P}_\alpha(A_1| A) = V_1,$ $A_1\cup A_2=\Omega,$ $A_1\cap A_2 = \emptyset,$ for all $X_1\in A_1,$ $X_2\in A_2,$ and $\mathbb{E}(Y|X_1)\le\mathbb{E}(Y|X_2),$ where $V_1\in[0,1]$ and $A_1, A_2$ are not required to be hyper rectangles. By definition, the set $A_1$ corresponds to the $V_1$ proportion of $A$ having the smallest $\mathbb{E}(Y|X)$ values, while the set $A_2$ corresponds to the $1-V_1$ proportion of $A$ having the largest $\mathbb{E}(Y|X)$ values. Similar to equation (\[p1alpha fs\]) and (\[delta Ialpha\]), we can define $p_{1,\alpha}, p_{2,\alpha}$ and the impurity decrease $\Delta I_\alpha(A,\mathbb{P})$. Given $V_1\in [0,1]$, the impurity decrease $\Delta I_\alpha(A,\mathbb{P})$ is unique, which is also the maximal impurity decrease for all measurable $A_1, A_2$ satisfying $\mathbb{P}_\alpha(A_1| A) = V_1,\; \mathbb{P}_\alpha(A_2|A) = 1-V_1$. Thus we can denote the impurity decrease as $\Delta I_\alpha(A,\mathbb{P}) = h^*_A(V_1)$. The oracle impurity decrease is the maximal value of $h^*_A(V_1)$: $M_{A}^* = \max_{V_1\in[0,1]} h^*_A(V_1).$ In general, the larger impurity decrease will tend to correspond to non-redundant features; this will particularly be the case under Conditions 1-2.

\[condition 1\] There exists $c_1\in [0,1]$, such that for all $A\subset\Omega$, $\sup_{1\le j\le q} M_{A,j} \ge c_1 M_A^*.$

Condition \[condition 1\] relates the impurity decrease in non-redundant features to the oracle impurity decrease. The strength of the condition is dependent on the value of $c_1$. If $c_1=0$, the condition does not impose any restrictions; if $c_1 =1$, partitions in non-redundant features can fully explain the oracle impurity decrease. Here we give some examples of models with different $c_1$ values.

Let $\Omega = [0,1]^d$ and the marginal distribution of $\mathbb{P}_\alpha$ be the uniform distribution on $\Omega$. Suppose $\mathbb{E}(Y|X)= \phi(a^T X + b),$ where $\phi(\cdot)$ is a monotonically increasing function, $a\in\mathbb{R}^d$ and $b\in\mathbb{R}$. Let $A_{y1}, A_{y2}$ be measurable sets having $A_{y1}\cap A_{y2}=\emptyset$ and $A_{y1}\cup A_{y2} = \Omega$, which achieve the oracle impurity decrease $M_A^*$, and let $\min\{\mathbb{P}_\alpha(A_{y1}), \mathbb{P}_\alpha(A_{y2})\}=h$. Then the constant $c_1$ in Condition 1 satisfies $c_1 \ge (\sqrt{2}-1)h + o(h)$ if $h \le 1/d!$ and $c_1 \ge F_{d-1}(F_d^{-1}(h)-h) - F_{d-1}(F_d^{-1}(h)-2h)$ if $h>1/d!$, where $F_d(z) = \frac{1}{d!} \sum_{k=0}^{\lfloor z\rfloor}(-1)^k {d\choose k} (z-k)^{d-1}$ is the cumulative distribution function for the Irwin-Hall distribution with parameter $d$.

Let $\Omega = [0,1]^2$ and $\mathbb{P}_X$ be the uniform distribution on $\Omega$. Let $A_1 = [0,1/2]\times[0,1/2],$ $A_2 =  [1/2,1]\times[0,1/2],$ $A_3 = [0,1/2]\times[1/2,1],$ $A_4 =  [1/2,1]\times[1/2,1],$ and $\mathbb{E}(Y|X) = 1$ if $X \in A_1\cup A_4$ and $0$ if $X\in A_2\cup A_3.$ Further assume $\alpha=1$. Then $c_1=0$.

\[condition 2\] The weighted probability measure $\mathbb{P}_\alpha$ has density $\rho_\alpha(X', X'')$ in $\Omega$. Moreover, $\rho_\alpha(X', X'') = \rho_{1,\alpha}(X') \rho_{2,\alpha}(X'') + \rho_{3,\alpha}(X', X''),$ where for all $(X', X'')\in \Omega$, $\rho_{3,\alpha}(X', X'') \le c_2 \rho_\alpha(X', X''),$ with $c_2\in [0,1]$ a constant.

Condition \[condition 2\] asserts that the joint density of $X', X''$ can be decomposed into an independent component plus a dependent component, where the dependent component is dominated by the independent component up to a constant. This condition controls the dependence between $X'$ and $X''$. Since given $X'$, $Y$ is independent of $X''$, this condition will also control the dependence between $Y$ and $X''$. The strength of the condition depends on the constant $c_2$. When $c_2=1$, the condition imposes no restrictions; when $c_2=0$, the condition asserts $X'$ and $X''$ are completely independent.

Using Conditions \[condition 1\]-\[condition 2\], we establish feature selection consistency in Theorem \[feature selection\].

\[feature selection\] If the optional steps in Algorithm 1 are enabled, condition \[condition 1\], \[condition 2\] are satisfied with $c_1>(1-c_2)/[c_2(2-c_2)]$ and $\lambda_n\ge c_3 n^{-(1/2-\beta)}$ for some constant $c_3>0$, $\beta\in (0, 1/2)$, we have $$\lim_{n\to\infty}\mathbb{P}(\hat{T}_n \;\text{does not have partitions in}\; X[j_{q+1}], X[j_{q+2}], \cdots X[j_d]) = 1.$$

In Theorem \[feature selection\] conditions 1 and 2 are complementary. If $c_2$ is smaller (i.e., condition 2 is stronger), $c_1$ can be smaller (i.e., condition 1 is weaker). The opposite also holds. The following two Corollaries cover special cases.

\[feature selection monotonic\] If the optional steps in Algorithm 1 are enabled, condition \[condition 1\] is satisfied with $c_1=1$ (that is, in each hyper-rectangle, the maximal impurity decrease at non-redundant features is equal to the oracle impurity decrease) and $\lambda_n\ge c_3 n^{-(1/2-\beta)}$ for some constant $c_3>0$, $\beta\in (0, 1/2)$, we have $$\lim_{n\to\infty}\mathbb{P}(\hat{T}_n \;\text{does not have partitions in}\; X[j_{q+1]}, X[j_{q+2}], \cdots X[j_d]) = 1.$$

\[feature selection independent\] If the optional steps in Algorithm 1 are enabled, $X'$ and $X''$ are independent and $\lambda_n\ge c_3 n^{-(1/2-\beta)}$ for some constant $c_3>0$, $\beta\in (0, 1/2)$, we have $$\lim_{n\to\infty}\mathbb{P}(\hat{T}_n \;\text{does not have partitions in}\; X[j_{q+1]}, X[j_{q+2}], \cdots X[j_d]) = 1.$$

Corollary \[feature selection independent\] is a direct result of theorem \[feature selection\] with $c_2=0$ and an arbitrary value of $c_1$.

Numerical Studies
=================

We compare SVR Tree with popular imbalanced classification methods on real datasets, adding redundant features to these datasets in evaluating feature selection. A confusion matrix (Table \[confusion matrix\]) is often used to assess classification performance. A common criteria for accuracy is $(TP + TN)/(TP + TN + FP + FN).$ When $1$s are relatively rare, it is often important to give higher priority to true positives, which is accomplished using the true positive rate (recall) $TPR = \frac{TP}{TP+FN}$ and precision $\frac{TP}{TP+FP}.$ To combine these, the F-measure is often used: $(1+\beta^2)TPR\times Precision/(\beta^2 TPR + Precision)$.

[ccc|c|]{} & &\
& & 1 & 0\
& & True Positive (TP) & False Positive (FP)\
& & False Negative (FN) & True Negative (TN)\

Datasets
--------

We test our method on 5 datasets from the UCI Machine Learning Repository [@Dua:2019], varying in size, number of features and level of imbalance.

#### Glass dataset

<https://archive.ics.uci.edu/ml/datasets/Glass+Identification> consists of 213 samples and 9 features. The objective is to classify samples into one of seven types of glass. We choose class 7 (headlamps) as the minority class and class 1-6 as the majority class, yielding 29 minority class samples.

#### Vehicle dataset

[@siebert1987vehicle] <https://archive.ics.uci.edu/ml/datasets/Statlog+(Vehicle+Silhouettes)> consists of 846 samples and 18 features. The aim is to classify a silhouette into one of four types of vehicles. As in [@he2008adasyn], we choose class “Van” as the minority class and the other three types of vehicles as the majority class, resulting in 199 minority class samples.

#### Abalone dataset

<https://archive.ics.uci.edu/ml/datasets/Abalone> aims to predict the age of abalone by physical measurements. As in [@he2008adasyn], we let class “18” be the minority class and class “9” be the majority class. This yields 731 samples in total, among which 42 samples belong to the minority class. We also remove the discrete feature “sex”, which gives us 9 features.

#### Satimage dataset

<https://archive.ics.uci.edu/ml/datasets/Statlog+(Landsat+Satellite)> consists of a training set and a test set. We have 6435 samples and 36 features. As in [@chawla2002smote], we choose class ‘4’’ as the minority class and collapsed all other classes into a single majority class, resulting in 626 minority class samples.

#### Wine dataset

[@cortez2009modeling] <https://archive.ics.uci.edu/ml/datasets/Wine+Quality> collects information on wine quality. We focus on the red wine subset, which has 1599 samples and 11 features. We let the minority class be samples having quality $\ge 7$, while the majority class has quality $\le 6$. This generates 217 minority class samples.

Experimental Setup {#setup}
------------------

We test the performance of SVR-Tree, SVR-Tree with feature selection, CART [@breiman1984classification] with duplicated oversampling, CART with SMOTE [@chawla2002smote], CART with Borderline-SMOTE [@han2005borderline] and CART with ADASYN [@he2008adasyn] on all five datasets. Features are linearly transformed so that samples lie in $[0,1]^d$.

For each method and dataset, we run the algorithm 50 times. For each run, we randomly choose 2/3 samples as training and 1/3 as testing. The average values of TP, TN, FP, FN on testing sets are used to compute the accuracy, TPR, precision and F-measure. The specific settings for each method are discussed below.

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; If $\alpha$ is greater than $15$, it is truncated to be $15$. 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}]\times10^{-3}\times n^{-1/3}$; the parameter with highest F-measure on 50 runs is selected. For SVR-Tree with feature selection, the constant $c_0$ in equation (\[impu decr\]) is fixed to $c_0=4$; In practice, the results are insensitive to $c_0$.

For the other methods, we first over sample the minority class samples, such that the number of minority samples are multiplied by $\alpha$ after oversampling. 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 [@breiman1984classification], 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; For SMOTE, the number of nearest samples is set as $k=5$; For Borderline-SMOTE, we adopt the Borderline-SMOTE1 of [@han2005borderline], with the number of nearest samples $k=5$. For both SMOTE and Borderline-SMOTE, if $\alpha-1\ge k$, some nearest neighbors may be used multiple times to generate synthetic samples. For ADASYN, 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$.

Results
-------

The average values of accuracy, precision, TPR, F-measure and number of selected features across the 50 runs are shown in Table \[results\]. In the column “Method”, SVR = SVR-Tree, SVR-Select = SVR-Tree with feature selection, Duplicate = CART with duplicated oversampling, SMOTE = CART with SMOTE, and BSMOTE = CART with Borderline-SMOTE and ADASYN = CART with ADASYN. For each dataset and evaluation measure, the method that ranks first is highlighted in bold. The number of wins for each performance measure are also calculated. The SVR methods perform the best overall, with SVR-Select having particularly good performance. Furthermore, SVR-Select chooses the fewest number of features for each dataset, so has a good balance of accuracy and parsimony.

   Data set     Method      Accuracy    Precision       TPR       F-measure    $n(\mathrm{features})$
  ---------- ------------ ------------ ------------ ------------ ------------ ------------------------
                 SVR         0.9583       0.8161       0.8956       0.8540              4.98
              SVR-Select   **0.9683**   **0.8668**     0.9067     **0.8863**          **1.0**
              Duplicate      0.9646       0.8489       0.9000       0.8737            **1.0**
                SMOTE        0.9624       0.8295       0.9111       0.8684              1.02
                BSMOTE       0.9602       0.8160     **0.9133**     0.8619            **1.0**
                ADASYN       0.9498       0.7713       0.8978       0.8297              5.72
                 SVR       **0.9368**   **0.8659**     0.8652       0.8655             14.76
              SVR-Select     0.9355       0.8544       0.8748       0.8645            **5.7**
              Duplicate      0.9362       0.8377     **0.9039**   **0.8696**           11.64
                SMOTE        0.9317       0.8385       0.8791       0.8583             10.98
                BSMOTE       0.9309       0.8417       0.8697       0.8554             13.96
                ADASYN       0.9341       0.8423       0.8855       0.8634             11.58
                 SVR         0.9212       0.3251       0.3457       0.3351              6.88
              SVR-Select   **0.9244**   **0.3431**     0.3457     **0.3444**          **5.6**
              Duplicate      0.9184       0.2956       0.3043       0.2999              6.94
                SMOTE        0.8974       0.2578     **0.4186**     0.3191              6.94
                BSMOTE       0.8960       0.2479       0.3986       0.3057              6.96
                ADASYN       0.8937       0.2480     **0.4186**     0.3114              6.92
                 SVR       **0.9036**   **0.5032**     0.6969       0.5844              34.5
              SVR-Select     0.9029       0.5008       0.7020     **0.5845**         **28.12**
              Duplicate      0.9032       0.5017       0.6553       0.5683             34.58
                SMOTE        0.8895       0.4578     **0.7364**     0.5646              29.2
                BSMOTE       0.8945       0.4720        0.71        0.5671             31.38
                ADASYN       0.8946       0.4711       0.6831       0.5576             34.72
                 SVR         0.8476       0.4564       0.6433       0.5340             10.96
              SVR-Select     0.8481       0.4578     **0.6475**   **0.5363**         **10.54**
              Duplicate    **0.8553**   **0.4744**     0.6103       0.5338              11.0
                SMOTE        0.8513       0.4647       0.6311       0.5353              11.0
                BSMOTE       0.8503       0.4608       0.6047       0.5231              11.0
                ADASYN       0.8477       0.4554       0.6228       0.5261              11.0
                 SVR         **2**        **2**          0            0       
              SVR-Select     **2**        **2**          1          **4**     
              Duplicate        1            1            1            1       
                SMOTE          0            0         **1.5**         0       
                BSMOTE         0            0            1            0       
                ADASYN         0            0           0.5           0       

  : Results of Numerical Studies on five real world datasets.[]{data-label="results"}

Additional Experiments for Feature Selection
--------------------------------------------

For the Wine and Abalone datasets, we generate 10 additional uninformative features independently from $U([0,1])$. We reran the analyses as above and results are shown in Table \[results feature selection\], where $n(\mathrm{features}_o)$ denotes the average number of original features selected by the method and $n(\mathrm{features}_r)$ denotes the average number of artificially generated features selected by the method.

SVR-Select performs well when there are a considerable number of redundant features. SVR-Select selects significantly more original features than artificially generated features, suggesting effectiveness in feature selection. For all other methods, the relative difference between number of original features and number of artificially generated features is much smaller. In addition, nearly all methods select fewer of the original features when compared with results in Table \[results\].

   Data set     Method      Accuracy    Precision       TPR       F-measure    $n(\mathrm{features}_o)$   $n(\mathrm{features}_r)$
  ---------- ------------ ------------ ------------ ------------ ------------ -------------------------- --------------------------
                 SVR       **0.8277**   **0.4242**     0.5486       0.4785              10.72                       8.58
              SVR-Select     0.8115       0.3910     **0.6975**   **0.5011**           **3.96**                   **0.26**
              Duplicate      0.8186       0.3963       0.6439       0.4906               9.58                       7.32
                SMOTE        0.8085       0.3838       0.6789       0.4904               8.8                        5.74
                BSMOTE       0.8136       0.3883       0.6492       0.4859               7.6                        4.24
                ADASYN       0.8073       0.3816       0.6767       0.4880               8.6                        6.44
                 SVR         0.8779       0.2173       0.4329       0.2894               5.34                       8.0
              SVR-Select   **0.9106**   **0.2788**     0.3500     **0.3104**             2.42                       0.7
              Duplicate      0.7730       0.1472     **0.6157**     0.2376             **1.0**                    **0.0**
                SMOTE        0.8471       0.1706        0.43        0.2443               3.32                       4.14
                BSMOTE       0.8761       0.2028       0.3943       0.2678               3.7                        3.7
                ADASYN       0.8383       0.1640       0.4429       0.2393               3.48                       4.12

  : Additional Numerical Study for Feature Selection.[]{data-label="results feature selection"}

Discussion
==========

A major challenge in analyzing imbalanced data is small sample size in the minority class leading to overfitting. It is natural to consider using regularization to address this problem. Regularization of classification trees is an old idea; for example, [@breiman1984classification] proposed to penalize the number of leaf notes in the tree. Other classification trees like C4.5 [@quinlan2014c4] and Ripper [@cohen1995fast] also prune the overgrown tree. However, the number of leaf nodes may not be a good measure of complexity of a classification tree. Recently, [@hahn2020bayesian] adds a Bayesian prior to an ensemble of trees, which functions as indirect regularization. Following the idea of directly regularizing the shape of the decision set and complexity of the decision boundary, we instead penalize the surface-to-volume ratio. To our knowledge, this is a new idea in the statistical literature on classification.

SVR-Tree can be trivially generalized to the multi-class case and balanced datasets. For multiple classes, we can apply SVR to one or more minority classes and take the sum of these ratios as regularization. For balanced datasets, we can either compute the SVR ratio of all classes, or we can simply regularize the surface of the decision boundary. The principle behind these generalizations is to regularize the complexity of the decision boundaries and shapes of the decision sets.

[**SUPPLEMENTARY MATERIAL**]{}

[**Proofs and a Detailed Algorithm:**]{} Supplemental Material for “Classification Trees for Imbalanced and Sparse Data: Surface-to-Volume Regularization”.\
[**Codes:**]{} <https://github.com/YichenZhuDuke/Classification-Tree-with->\
[Surface-to-Volume-ratio-Regularization.git](Surface-to-Volume-ratio-Regularization.git).

Proofs
======

We prove Theorem 1 and 2 here. Proofs for Corollary 1, $c_1$ bounds in examples 1-2 and lemmas in Appendix are in the supplemental material. Without loss of generality, we assume $\Omega = [0,1]^d$ in this section.

Proof of Theorem \[consistency\]
--------------------------------

The proof builds on [@nobel1996histogram], [@gyorfi2006distribution], [@tsybakov2004optimal] and [@scornet2015consistency]. We first establish a sufficient condition for consistency, showing a classification tree whose signed impurity converges to an oracle bound is consistent. We then break the difference between signed impurity of $\hat T_n$ and the oracle bound into two parts. The first is estimation error, which goes to zero if the number of leaves $a_n$ increases slower than $n$; the second is approximation error, which goes to zero if $\mathbb{E}(Y|X\in A)$ goes to a constant within each leaf node and penalty $\lambda_n$ goes to zero.

Denote $p(x) = \mathbb{E}(Y=1|X=x)$, and its weighted version $p_\alpha(x) = [\alpha p(x)][1-p(x)+\alpha p(x)]$. Define the oracle lower bound for signed impurity as $I_\alpha^* = \int_\Omega 2p_\alpha(x)(1-p_\alpha(x)) d\mathbb{P}_\alpha(x).$ The following lemma shows if the signed impurity of a classification tree converges to $T^*$ as $n\to\infty$, the classifier associated with the tree is consistent.

\[lem: signed impu consistency\] Let $T_n$ be a sequence of classification trees, let $f_n: \Omega\to \{0,1\}$ be the classifier associated with $T_n$. $T_n$ is consistent if $\tilde{I}_\alpha(T_n, \mathbb{P}) \to I^*_\alpha$ in probability.

We then decompose the difference between signed impurity of $\hat{T}_n$ and the oracle bound into estimation error and approximation error.

\[lem:decompose\] Let $\hat{T}_n$ be a classification tree trained from data $\mathscr{D}_n$, $A_1, A_2, \ldots A_m$ be all the leaf nodes of $\hat{T}_n$. Define the set of classifiers $\mathscr{T}_n$ as: $$\mathscr{T}_n = \{T: T\text{'s associated classifier }f:\Omega\to\{0,1\}\text{ is constant on all }A_j, \;\; 1\le j \le m\}.$$ We have $$\label{decompose}
\tilde{I}_\alpha(\hat{T}_n,\mathbb{P}) - I^*_\alpha \le 2 \sup_{T\in\mathscr{T}_n}|\tilde{I}_\alpha(T, \mathbb{P}) - \tilde{I}_\alpha(T,\mathbb{P}_n)| + \inf_{T\in\mathscr{T}_n}|\tilde{I}_\alpha(T, \mathbb{P})+\lambda_n r(T) - I^*_\alpha|.$$

The first term on the right hand side of equation (\[decompose\]) is the “estimation error”, which measures the difference between functions evaluated under the empirical and true distributions. The second term is “approximation error”, which measures the ability of $\mathscr{T}_n$ to approximate the oracle prediction function. The next two lemmas show both terms go to zero in probability.

\[estimation error\] If $\frac{\bar{a}_n d\log n}{n} = o(1),$ we have $\sup_{T\in\mathscr{T}_n}|\tilde{I}_\alpha(T, \mathbb{P}) - \tilde{I}_\alpha(T,\mathbb{P}_n)| \to 0$ in probability.

\[approximation error\] As $n\to\infty$, if $\lambda_n\to 0$ and $\bar{a}_n\to\infty$, $\inf_{T\in\mathscr{T}_n} |\tilde{I}_\alpha(T,\mathbb{P}) + \lambda_n r(T) - I_\alpha^*| \to 0$ in probability.

Combining lemma \[lem: signed impu consistency\], \[lem:decompose\], \[estimation error\], \[approximation error\], we finish the proof.

Proof of Theorem \[feature selection\]
--------------------------------------

The proof of theorem \[feature selection\] mainly consists of two parts. The first works on the true distribution $\mathbb{P}$, proving that under $\mathbb{P}$, the partition with highest impurity decrease is always in non-redundant features; The second works on the randomness brought by $\mathbb{P}_n$, proving that with high probability, the randomness of the tree impurity decrease can be controlled by the threshold $c_0\lambda_n$. Combining these two parts with theorem \[consistency\], we can show the probability of rejecting all redundant features in the tree building procedure goes to zero. We now focus on the first part.

\[theoretical exclude\] Under the conditions of theorem \[feature selection\], for all hyperrectangles $A\subset \Omega$, we have $\sup_{1\le j\le q} M_{A,j} \ge \sup_{q+1\le l\le d} M_{A,l},$ where $M_{A,j}$ is the maximal impurity decrease of feature $j$ at node $A$ defined in equation (\[Mj\]).

We now work on the second part, proving the randomness in tree impurity decrease can be bounded by $c_0\lambda_n$ with high probability.

\[noise thre\] Suppose $\lambda_n \ge n^{-1/2+\beta}$ and the density of $X$ exists, then for all hyperrectangles $A\subset \Omega$, let $A_1, A_2$ be the two child nodes of $A$ obtained by an arbitrary partition, and let $n'$ be the number of samples in $A$. To highlight the dependence of impurity decrease and the child node $A_1, A_2$, denote the impurity decrease on node $A$ after partitioning $A$ into $A_1, A_2$, under measure $\mathbb{P}$ and $\mathbb{P}_n$, as $\Delta I_\alpha(A,A_1,\mathbb{P})$ and $\Delta I_\alpha(A,A_1,\mathbb{P}_n)$, respectively. Then we have $$\lim_{n\to\infty}\mathbb{P}\left(\sup_{A_1} |\Delta I_\alpha(A, A_1,\mathbb{P}) - \Delta I_\alpha(A, A_1,\mathbb{P}_n)|>\frac{c_0\lambda_n n}{2n'}\right) = 0.$$

We are now prepared to prove Theorem \[feature selection\].

Let $T_k^*$ be the theoretical tree with $k$ leaf nodes defined in Algorithm 2 of supplemental material, and let $\hat{T}_{n,k}$ be the tree consisting of the first $k$ partitions of tree $\hat{T}_n$. The proof of theorem \[feature selection\] consists of two steps. In the first step, we show there exists $k_0\in\mathbb{N}$, such that as $n$ goes to infinity, the probability of $\hat{T}_{n,k_0}$ including all non-redundant features and excluding all redundant features goes to one. In the second step, we show if all the non-redundant features are already included in the tree, the probability of including any new redundant features in all the following partition procedures goes to zero.

We begin with the first step. By lemma \[theoretical exclude\], the theoretical tree $T_k^*$ will not include any redundant features. We now show all non-redundant features are included in $T_k^*$ provided $k$ is large enough. Let $f_k^*$ be the classifier associated with tree $T_k^*$. Let $\psi_k(x)$ be the leaf node of $T_k^*$ that contains $x$, and let $e_k(x)$ be the average of $\mathbb{E}(Y|X)$ in each leaf node $e_k(x) \triangleq \mathbb{E}(Y|X\in\psi_k(x)).$ By Lemma 1 in [@scornet2015consistency], we have $e_k(x)$ converges to $\mathbb{E}(Y|X)$ almost surely. If there exists a non-redundant feature $X[j]$, such that $X[j]$ is excluded in partitions of $T_k^*,\; \forall k\in\mathbb{N}$, we have $\mathbb{E}(e_k(X)|X[-j]) = e_k(X),\;\forall k\in \mathbb{N}$, hence $\mathbb{E}(Y|X[-j]) = \mathbb{E}(Y|X)$. This contradicts the fact that $X[j]$ is a non-redundant feature. Therefore, for all non-redundant features $X[j]$, there exists some $k_j\in\mathbb{N}$, such that feature $X[j]$ is included in partitions of $T_k^*$ for $k\ge k_j$. Since the number of features is finite, there exists $k_0\in\mathbb{N}$, such that $T_{k_0}^*$ includes all non-redundant features. By Technical Lemma 4 in the supplemental material, as $n$ goes to infinity, with probability tending to one, $\hat T_{n,k_0}$ includes all non-redundant features while excluding all redundant features.

It remains to show no redundant features will be included after the $k_0$th partition. For the $k'$th ($k_0<k'\le \bar{a}_n$) partition, which partitions node $A$ into $A_1, A_2$, denote $\Delta I_{\alpha,n}(T,\mathbb{P}_n)$ and $\Delta I_{\alpha,r}(T,\mathbb{P}_n)$ as the maximal tree impurity decrease measured by $\mathbb{P}_n$ when the partition is in a non-redundant feature and redundant feature, respectively. Then by Algorithm 1, the partition at a redundant feature will be rejected if $\Delta I_{\alpha,r}(T,\mathbb{P}_n) \le \Delta I_{\alpha,n}(T,\mathbb{P}_n) + c_0\lambda_n.$ Similarly, denote $\Delta I_{\alpha,n}(A,\mathbb{P}_n)$ and $\Delta I_{\alpha,r}(A,\mathbb{P}_n)$ as the maximal impurity decrease of node $A$ measured by $\mathbb{P}_n$ when the partition is in a non-redundant feature and redundant feature, respectively. Further denote $\Delta I_{\alpha,n}(A,\mathbb{P})$ and $\Delta I_{\alpha,r}(A,\mathbb{P})$ as the maximal impurity decrease of node $A$ when the probability measure is the true probability $\mathbb{P}_n$. By lemma \[theoretical exclude\], for the impurity decrease on node $A$ measured under true probability $\mathbb{P}$, we have $\Delta I_{\alpha,n}(A,\mathbb{P}) \le \Delta I_{\alpha,r}(A,\mathbb{P}).$ By lemma \[noise thre\], we have with probability greater than $1-\sigma(n)$ $$|\Delta I_{\alpha,n}(A,\mathbb{P}_n) - \Delta I_{\alpha,n}(A,\mathbb{P})|\le \frac{c_0\lambda_n n}{2n'\alpha},$$ $$|\Delta I_{\alpha,r}(A,\mathbb{P}_n) - \Delta I_{\alpha,r}(A,\mathbb{P})|\le \frac{c_0\lambda_n n}{2n'\alpha}.$$ Therefore, we have with probability greater than $1-\sigma(n)$ $$\begin{aligned}
|\Delta I_{\alpha,r}(T,\mathbb{P}_n)-\Delta I_{\alpha,n}(T,\mathbb{P}_n)|
     \le & \mathbb{P}_{n,\alpha}(A) |\Delta I_{\alpha,r}(A,\mathbb{P}_n) -\Delta I_{\alpha,n}(A,\mathbb{P}_n)| \\
        \le & \alpha \frac{n'}{n} \Big(0 + \frac{c_0\lambda_n n}{2n'\alpha} + \frac{c_0\lambda_n n}{2n'\alpha}\Big) \\
        \le & c_0\lambda_n.\end{aligned}$$ Therefore, for all $k'$ ($k_0<k'\le \bar{a}_n$), the probability of partitioning at a redundant feature is smaller than $\sigma(n)$. Since $\bar{a}_n\le n$ and $\lim_{n\to \infty} n\sigma(n) = 0$, with probability tending to one, $\hat{T}_n$ will not partition at redundant features.

[^1]: Yichen Zhu is Ph.D. student, Department of Statistical Science, Duke University, Durham, NC 27708.

[^2]: David B. Dunson is art and science professor, Department of Statistical Science, Duke University, Durham, NC 27708. The research was partially supported by grant N000141712844 of the United States Office of Naval Research.

[^3]: A 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 [@cormen2009introduction] for details.

[^4]: In our experiments, we set $\bar{a}_n = 2\sqrt{n}$.
