Classification and Regression Tree (CART)

Introduction

Regression and classification tree (CART) is a tree based method, that partition the feature into a set of regions and then individually fit a model, which can be used for nonlinear variable prediction.

1. Classification tree: use in predict categorical variables, ex: color, gender
2. Regression tree: use in predict numerical variables, ex: height, weight

For example, given $X$ to predict $Y$.

First, partition feature into a set of regions.

Then individually fit a model, like a constant.

Regression tree

One Dimension Partition

Considering binary partitioning and constant fitting, each partition should consider the split point $t_m$ (or region $R_m$) and the coefficient ​​$c_m$ of the region.

Determine $c_m$ ($1 \leq m \leq M$) which minimize the sum of square error (SSE)

Next, determine $R_m$ by binary partition

Seek the best $t$ also minimize SSE,

But we won’t consider $t \in \mathbb R$, in stead, only consider $t$ in the range of data points. Define $X_{(i)}$ be the order statistic of $X_1, X_2, \cdots, X_n$, try $t$ from $X_{(2)}$ to $X_{(n - 1)}$, find the $t$ that minimize SSE.

Multi Dimension Partition

Suppose $X$ has $p$ dimension,

Seek the best $j$ and $t$ that minimize SSE,

Start $j$ from $1$ to $p$, in particular

Use iris data set to build a regression tree (numerical part)

Start from $j = 1$, i.e. try to partition $X_1$

Simalliry, try to partition $X_2$ and $X_3$

Finally, find the smallest $j$ and $t$ minimize

The best cut at $(j, t) = (3, 1.9)$, i.e.

Now mark the point of $R_1$ in red.

Next, remove the red poins, the remain part will be $R_2$.

We can still perform a CART again for remain part, we will get

Repeat the process, until the cut SSE has no obvious minimum value.

Cost Complexity Criterion

Let $|T|$ be the number of terminal nodes in the tree $T$, and let

Define the cost complexity criterion, for a given $\alpha \geq 0$,

Our goal is to minimize this criterion, where $\alpha$ is a tuning parameter, it punishes trees that are too large or too complex. The larger the $\alpha$, the smaller the tree.

Classification Tree

For categorical variable (e.g. color), square error is not available, assume $y$ only take values in $K$ classes, denote by $\\{1, 2, \cdots, K\\}$, for $k = 1, 2, \cdots, K$, use impurity to measure the $Q_m (T)$, let

Classify in node $m$ to class

There some different impurity measure of $Q_m (T)$,

1. Misclassification error:

   $$ \begin{align*} \frac{1}{N_m} \sum_{x_i \in R_m} I (y_i \ne k(m)) = 1 - \hat p_{m k (m)}. \end{align*} $$

2. Gini index:

   $$ \begin{align*} \sum_{k \ne l} \hat p_{m k} \hat p_{m l} = \sum_{k = 1}^{K} \hat p_{m k} (1 - \hat p_{m k}). \end{align*} $$

3. Cross-entropy or deviance:

   $$ \begin{align*} - \sum_{k = 1}^{K} \hat p_{m k} \ln (\hat p_{m k}). \end{align*} $$

Other Building Method

To build a tree, we have two step to consider:

1. Partition feature into a set of regions.
2. Individually fit a model.

Linear Combination Splits

Origin partition consider $X_j < t$, we can splits along the linear combition of the form $\sum_{j = 1}^{p} a_j X_j < t$. To determine $a_j$ and the cut point $t$, that is minimize the Gini index criterion.

For example, the first two columns of iris are basically perfect separation.

Regression Fitting Tree

Instead of just constant fitting, we can also fit regression models to different regions individually, and our goal is still to minimize cost complexity criterion (or SSE).

Example in R

# load data
data = iris 

# split train 70% and test 30%
set.seed(0)
samples = sample(1:dim(data)[1], dim(data)[1] * 0.7)
train = data[samples, ]
test = data[-samples, ]

# train model by rpart
library(rpart)
model = rpart(Species ~ ., data = train) 

# confusion matrix
predictions = predict(model, newdata = test, type = "class")
confusion_matrix = table(Actual = test$Species, Predicted = predictions)
print(confusion_matrix) 

# accuracy
accuracy = sum(diag(confusion_matrix)) / sum(confusion_matrix)
print(paste("Accuracy:", accuracy))

# plot model
library(rpart.plot)
rpart.plot(model) 

Result:

            Predicted
Actual       setosa versicolor virginica
  setosa         15          0         0
  versicolor      0         15         1
  virginica       0          2        12
[1] "Accuracy: 0.933333333333333"

References

The Element of Statistical Learning (Trevor Hastie)