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}) = 