Decision Tree Splitting

A decision tree recursively partitions the input space with (feature, threshold) splits; the splitting criterion measures split quality. Entropy: $H(D) = -\sum_{k=1}^{K} p_k \log_2 p_k$; Gini impurity: $G(D) = 1 - \sum_{k=1}^{K} p_k^2$, which reduces to $G = 2p(1-p)$ in binary classification (max 0.5 at $p = 0.5$). The CART classifier greedily picks the feature $A$ and split point $v$ maximizing the Gini decrease $\Delta G(A, v) = G(D) - \frac{|D_L|}{|D|} G(D_L) - \frac{|D_R|}{|D|} G(D_R)$, where $D_L = \{ x \mid x_A \leq v \}$ and $D_R = D \setminus D_L$. ID3 uses information gain $\text{Gain}(D, A) = H(D) - \sum_{v=1}^{V} \frac{|D_v|}{|D|} H(D_v)$, which favors many-valued features (finer partitions lower $H(D_v)$); C4.5 uses the gain ratio $\text{Gain\_ratio}(D, A) = \frac{\text{Gain}(D, A)}{\text{IV}(A)}$ with intrinsic value $\text{IV}(A) = -\sum_{v=1}^{V} \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|}$ to penalize the number of values; CART is always binary (one threshold per split), using Gini for classification and variance reduction $\text{err}(D) = \frac{1}{|D|} \sum_{i \in D} \left(y_i - \bar{y}_D\right)^2$ for regression. Continuous features: after sorting, only midpoints $\frac{x^{(i)} + x^{(i+1)}}{2}$ of adjacent samples are candidate split points (any threshold is equivalent to the midpoint of the cell it falls into), at most $n-1$ candidates, $O(n \log n)$ per feature.

classic interview trio — differences among ID3 / C4.5 / CART criteria, why information gain prefers many-valued features, and how continuous features are split; it is also the starting point for deriving RF (Gini) and XGBoost/LightGBM (structural gain) splitting.

it turns the exponential search over (feature, threshold) combinations (optimal decision trees are NP-hard) into one greedy linear scan per node — each candidate split costs $O(n)$, so a node costs $O(d \cdot n \log n)$; greedy splitting is not globally optimal but is good enough in practice with pruning and randomization, and the criteria depend only on class proportions/variance, so they are scale-free and handle nonlinearity natively.

Whiteboard Gini impurity $G = 1 - \sum_k p_k^2$: why does it reduce to $2p(1-p)$ for binary classes? Pros and cons vs entropy?

Write information gain and explain its bias toward many-valued features; how does the gain ratio fix it with the intrinsic value $\text{IV}(A)$?

What splitting criteria do ID3 / C4.5 / CART use? Why must CART be a binary tree?

How are continuous features split? Why only midpoints of adjacent sorted values? What is the per-feature complexity?

What are the splitting criterion and leaf output of a CART regression tree? Why is the leaf output the mean $\bar{y}$?