I skipped MLP and KNN and resumed with decision trees, partly to prepare for XGBoost, LightGBM, and CatBoost later.

As an aside, today I watched DeepSeek dominate GitHub’s rankings. I have never seen anything like it: six of the top ten projects were related to DeepSeek.

Decision trees

A single decision tree is easy to understand: it uses conditions to predict a class or value. As conditions increase, it deepens the tree to encode more information.

The central idea is to partition data by features and recursively form a tree. Partitions need to be mutually exclusive and collectively exhaustive, so every path is unique. How to partition data is the key problem, and it is where ID3, C4.5, and CART differ.

ID3: information gain

Entropy is defined as:

$$H(D) = -\sum_{i=1}^{k} p_i \log_2{p_i},$$

where $p_i$ is the probability of class $i$. Entropy measures uncertainty: higher entropy means greater disorder.

Information gain measures the entropy reduction after feature $A$ partitions dataset $D$:

$$IG(D, A) = H(D) - \sum_{v \in A} \frac{|D_v|}{|D|} H(D_v).$$

$H(D)$ is original entropy and $D_v$ is the subset split by feature value $v$. Greater entropy reduction means the feature is more important. In practice, calculate empirical entropy from the target, recursively calculate every feature’s information gain, and choose the largest as the next split.

C4.5: gain ratio

In ID3, a feature with many unique values appears to contain more information and is therefore favored. C4.5 fixes this with the information-gain ratio:

$$GainRatio(D, A) = \frac{IG(D, A)}{IV(A)},$$

where the intrinsic value is the feature’s entropy:

$$IV(A) = -\sum_{v \in A} \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|}.$$

Information value is also common in risk control, though its formula is based on weight of evidence (WOE):

$$IV = \sum_{i=1}^{n} \left(WOE_i \times (p_i - q_i)\right), \qquad WOE_i = \log \frac{p_i}{q_i}.$$

Here $p_i$ is the good-customer share and $q_i$ the bad-customer share in group $i$. $p_i-q_i$ measures the group’s distribution imbalance; WOE measures separation of good and bad customers; their product measures the group’s overall contribution, and summing it scores feature importance.

CART: Gini coefficient

After improvement, CART supports classification and regression. It recursively builds a binary tree. For classification it selects features by minimizing the Gini index; for regression it minimizes MSE.

$$Gini(D) = 1 - \sum_{i=1}^{k} p_i^2,$$

and feature $A$ has:

$$GiniIndex(D, A) = \sum_{v \in A} \frac{|D_v|}{|D|} Gini(D_v).$$

Strengths and weaknesses

Strengths	Weaknesses
Intuitive and easy to understand	Easily overfits
Fast to train	Sensitive to noise
Supports classification and regression	Weak at continuous variables
Works on small datasets	Can depend heavily on feature selection

As tree depth grows, decision trees easily overfit. Pruning or Bagging/Boosting is usually used to improve robustness. Feature selection requires computing feature entropy over all data at every split, making tree construction slow for large datasets.

Regression trees

Decision trees originally predicted only discrete values. CART added continuous-value prediction by replacing cross-entropy with losses such as MSE or RMSE, and by predicting each leaf’s target mean.

Before splitting, for $n$ samples the target mean is:

$$\bar{y} = \frac{1}{n} \sum_{i=1}^{n} y_i.$$

If splitting stops, $\bar{y}$ is the prediction. A regression tree chooses feature $A$ and split $s$ to minimize:

$$MSE = \sum_{i=1}^{n} (y_i - \bar{y})^2.$$

After a split, the left and right subsets predict their own means. Recursion ends at a stopping criterion, such as too few samples in a leaf; the leaf then predicts the mean of all its targets.

For example, to predict house prices from area, consider areas 50, 55, 70, 75, 90, 100 square meters with prices 150, 160, 180, 190, 220, 250 ten-thousand yuan. The overall mean is 191.67. A split at 70 gives a left mean of 163.33 and a right mean of 220.00. A home at or below 70 square meters is predicted at 163.33; one above it at 220.00.

February 3, 2025, Suzhou