Popular Courses
Beginner – Linear Regression
Introduction
Beginner – Decision Trees
Introduction
Beginner – Neural Networks
Introduction

Sign in to Curvingo

or

New Account     Reset Password     

Plans

Details
Decision Trees
Introduction
Decision Tree
Where To Partition?
Information Gain
Another Look At Our Decision Tree
The Problem of Perturbations
Going Beyond A Single Tree
Code with Python
Summary
Curvingo · Made in India

Share

Send us Feedback

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

This will delete your progress and chat data for all chapters in this course, and cannot be undone!

Glossary

Select one of the keywords on the left…

Decision TreesInformation Gain

Reading time: ~10 min

A cut is good when the boxes after it are much purer than the box before it. The drop in entropy is called the information gain. The two new boxes can be of different sizes, so we average their entropies with weights:

\text{Gain} = H_{\text{before}} - H_{\text{after}}

H_{\text{after}} = \dfrac{n_{\text{yes}}}{n} H_{\text{yes}} + \dfrac{n_{\text{no}}}{n} H_{\text{no}}

Let's score Meena's first question, "length ≤ 10.25 cm", by hand.

  • Before: 10 Alphonso and 10 Totapuri, an even mix, so H_{\text{before}} = .
  • Yes side: 9 Alphonso and 1 Totapuri. With \log_2 0.9 = -0.152 and \log_2 0.1 = -3.322, we get H_{\text{yes}} = 0.9 \times 0.152 + 0.1 \times 3.322 = .
  • No side: 1 Alphonso and 9 Totapuri — the same mix the other way round, so H_{\text{no}} = 0.469 too.

Each side holds 10 of the 20 mangoes, so H_{\text{after}} = 0.5 \times 0.469 + 0.5 \times 0.469 = 0.469, and the gain is 1 - 0.469 = .

Now the best question about weight, "weight ≤ 230 g". Its yes side holds 7 Alphonso and no Totapuri, so H_{\text{yes}} = 0. Its no side holds 3 Alphonso and 10 Totapuri, H_{\text{no}} \approx 0.78, and it has 13 of the 20 mangoes. So its gain is 1 - 0.65 \times 0.78 \approx 0.49. Which question should the tree ask first? The one about .

Length wins, 0.53 against 0.49. The tree always asks the question with the largest information gain first.

Try Every Cut

The computer does not guess. It slides the cut through every gap between two neighbouring mangoes, for every feature, and works out the gain each time. Slide the cut and watch the gain chart fill in.

That scan is exactly how the computer grows a tree:

  1. Work out the entropy of the box.
  2. Try every feature, and every cut halfway between two neighbouring values.
  3. For each cut, work out the weighted entropy of the two new boxes, and so the information gain.
  4. Ask the question with the largest gain, then repeat all four steps inside each new box.

Note

Entropy is not the only way to measure a mess. Gini impurity is 1 minus the square of each kind's share; for 9 Alphonso and 1 Totapuri it is 1 - 0.9^2 - 0.1^2 = 0.18. Like entropy, it is 0 for a pure box and largest for an even mix, but it needs no logarithms. The two usually choose the same questions; scikit-learn uses Gini unless you ask for entropy.

Sina