Machine Learning - Supervised Learning - Information Gain Tutorial

We can define information gain as a measure of how much information a feature/nodes provides about a class. Information gain helps to determine the order of attributes in the nodes of a decision tree.

The information gain is based on the decrease in entropy after a dataset is split on an attribute. Constructing a decision tree is all about finding attribute that return the highest information gain.

Information Gain= Entropy(S)- [(Weighted Avg) *Entropy(each feature)

Example:
Now, lets draw a Decision Tree for the following data using Information gain.

Training set: 3 features(X,Y,Z) and 2 classes(I & II)

To build a decision tree using Information gain. We will take each of the feature and calculate the information for each feature. 

Split on feature X

Split on feature Y

Split on feature Z

From the above images we can see that the information gain is maximum when we make a split on feature Y. So, for the root node best suited feature is feature Y. Now we can see that while splitting the dataset by feature Y, the child contains pure subset of the target variable. So we don’t need to further split the dataset.

The final tree for the above dataset would be look like this:

• Gini index/impurity

It is always between 0 and 0.5, where 0 mean all the sample got the same result, and 0.5 mean that split is done at the exactly middle.

• Gini index is a measure of impurity or purity used while creating a decision tree in the CART (Classification and Regression Tree) algorithm.
• An attribute with the low Gini index should be preferred as compared to the high Gini index.
• It only creates binary splits, and the CART algorithm use only Gini index to create binary splits.
• Gini index can be calculated using the below formula:

Gini Index= 1- (P_y² ₊ P_n²)

• Pruning: Getting an Optimal Decision Tree

Pruning is a process of deleting unnecessary nodes from a tree without reducing accuracy in order to get the optimal decision tree.

Pruning helps to reduce the risk of overfitting on the large tree by making it small tree of important features.

Pruning can occur in:

• Top-down fashion. It will traverse nodes and trim subtrees starting at the root
• Bottom-up fashion. It will begin at the leaf nodes

Two types of Pruning Technology is-

• Cost Complexity Pruning
• Reduced Error Pruning.

There is a popular pruning algorithm called reduced error pruning, in which:

Starting at the leaves, each node is replaced with its most popular class

If the prediction accuracy is not affected, the change is kept

There is an advantage of simplicity and speed