CART Classification (R)

Decision Trees¶

Decision trees are a collection of predictive analytic techniques that use tree-like graphs for predicting the response variable. One such method is CHAID explained in a previous blog. The most popular decision tree method is the CART or the Classification and regression trees. Decision trees partition the data set into mutually exclusive and exhaustive subsets, which results in the splitting of the original data resembling a tree-like structure.

CART Classification¶

We can use the CART method for regression and classification. In this blog, I will go through the CART classification in detail using the titanic example. Any decision tree model consists of 5 steps:
1. Start with the complete training data in the root node.
2. Decide on a splitting criterion
3. Split the data into two or more subsets based on the above metric
4. Using independent variables, repeat step 3 for each of the subsets of the data until
--(a) All the dependent variables are exhausted, or they are not statistically significant at alpha
--(b) We meet the stopping criteria
5. Generate business rules for the terminal nodes (nodes without any branches) of the tree

Step 1: Start with complete data¶

The data used in this blog is the same as the used in other classification posts, i.e. the Titanic dataset from Kaggle. In this problem, we have to identify what types of people had a higher chance of survival. A sample of the data is shown below. A basic EDA is performed in the blog on Logistic regression.

Step 2: Decide on a splitting criterion¶

In CHAID bases classification, we used p-value from hypothesis tests as the splitting criterion. In CART, we will use impurity metrics like Gini Index and Entropy.

Gini Index¶

It is defined mathematically as: $$ Gini\,Index = \sum_{i=1}^k \sum_{j=1,i\neq 1}^k P(C_i|t)\times P(C_j|t)$$ where \(P(C_i|t)\) = Proportion of observations belonging to class \(C_i\) in node t. For a binary classification,

Gini Index is a measure of total variance across the classes. It has a small value if all the \(P(C_i|t)\) are close to zero or one. For this reason, the Gini index is a measure of node purity. A small value indicates that a node contains observations from a single class predominantly.

Entropy¶

An alternative to the Gini index is entropy, given by entropy: $$ Entropy = - \sum_{i=1}^k P(C_i|t)\times log[P(C_i|t]$$ Like the Gini index, the entropy is a small value if the node is pure. The Gini index and the entropy are quite similar numerically.

For this blog, I want to consider the Gini index as my impurity measure. The aim is to minimise the Gini Index as much as possible.

Step 3. Split the data into two or more subsets based on the above metric¶

The Gini impurity in the base node (complete data) is

## [1] 0.472365

The impurity of the overall data is 0.47. Let us look at the purity if we split the data based on various features.

Gender:¶

If we split based on gender, the male and female branches individually have lower impurity (Gini index) than the base node. I have built the decision tree as the total weighted Gini index after splitting is lesser than the Gini index of the overall data.

## [1] "The total weighted impurity after the split is: 0.3338"

Passenger class¶

Similarly, for passenger class, the three categories (if we split into three branches) have an impurity as follows:

In CART, we can split the data into two branches only. By combining passenger class 1 and passenger class 2 into one category, we will have the below Gini impurities. I have built the decision tree as the total weighted Gini index after splitting is lesser than the Gini index of the overall data.

## [1] "The total weighted impurity after the split is: 0.423943259996532"

Number of siblings¶

The number of siblings is a categorical variable in this problem as the probability of survival is not linearly dependent on the number of siblings. According to intuition, people with one or two siblings will have a higher rate of survival as they will take care of each other. The impurity for each class is:

By combining the number of siblings of 1 and 2 into one category and all others into another group, we will have the following Gini index:

## [1] "The total weighted impurity after the split is: 0.457085468377958"

Number of parents/children¶

Just like the number of siblings, the number of parents/children of a person is also a categorical variable. The Gini index among the categories are:

By combining the number of parents/siblings of 1, 2 and 3 into one group and others into another group, we will have the following impurity:

## [1] "The total weighted impurity after the split is: 0.459125378001722"

Embarked location¶

There are three locations where the passengers have embarked. The Gini index within each of the location is:

Combining Q and S into one category, we have:

## [1] "The total weighted impurity after the split is: 0.458719142423424"

Age¶

Age is a continuous variable, so we have to find the ideal age to split the data along with the impurity metrics. To find the ideal cutoff, I have plotted the weighted gini index for split based on different ages.

We can observe the minimum Gini index when the data is split at Age=7 years.

## [1] "The total weighted impurity after the split is: 0.46"

Fare¶

Similar to age, fare is a continuous variable and we have to find the optimal fare to split first.

The optimal fare is 11. The impurity metrics for this split are:

Conclusion¶

Among all the factors above, Gender has the least Gini Index of 0.3338. So the initial split of the data would be on Gender.

Step 4: Repeat step 3 until stopping criterion¶

After splitting the data based on gender, we will get two data sets. We should perform a similar analysis to step 2 to split the data further, and so on. The splitting should stop when we meet the stopping criterion. Different stopping criterion for CART classification trees are:
1. The number of cases in the node is less than some pre-specified limit.
2. The purity of the node is more than some pre-specified threshold.
3. Depth of the node is more than some pre-specified threshold.
4. Predictor values for all records are identical

In this blog, I want to give a maximum depth of trees as 3. In the machine learning blogs, I will go deeper into how to select ideal stopping criterion. For max depth=3, we get the following decision tree:

Step 5: Making business rules¶

From the above tree, I can see generate the following rules:
1. A female passenger has a higher probability of surviving unless she is travelling in third class with a fare less than 23.
2. A male passenger has a lower likelihood of surviving unless he is a child of age less than six years and with up to two siblings.

Using this decision tree, we can observe how sociological factors like gender, age and monetary status affected the decisions on who would get into a lifeboat at a crucial time during the titanic disaster.

References¶

1. Business Analytics: The Science of Data-Driven Decision Making - Dinesh Kumar
2. Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow, 2^nd Edition
3. An Introduction to Statistical Learning: With Applications in R