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 TreesWhere To Partition?

Reading time: ~10 min

How did the computer know which cut was the best? It needs a number that says how mixed-up a box is. That number is called entropy.

Think of a crate that holds only Alphonsos. Pull out a mango without looking and you know what you will get: no surprise at all. That crate has low entropy, and we call it pure. A crate that is half Alphonso and half Totapuri is a gamble every time: high entropy, or impure. A tree's whole job is to take one messy pile and keep splitting it into neat, low-entropy boxes.

Sort these.

A crate of only Alphonso mangoes
A bowl of mixed namkeen
A coin with heads on both sides
A well-shuffled pack of cards
A class in which everyone chose Biology
A bag of 5 red and 5 blue marbles
Pure — low entropy
Mixed — high entropy

Measuring the Mess

For a box with two kinds, where a fraction p of the mangoes are Alphonso and 1 - p are Totapuri, the entropy is

H = -p \log_2 p - (1 - p) \log_2 (1 - p)

For example, a crate of 3 Alphonso and 1 Totapuri has p = 0.75, so

H = -0.75 \log_2 0.75 - 0.25 \log_2 0.25

H = 0.75 \times 0.415 + 0.25 \times 2

H = 0.311 + 0.5 = 0.811

The minus signs are there because the logarithm of a number below 1 is negative; they make H come out positive. The purple curve shows H for every possible mix. Change the crate and complete both missions.

Alphonso in the crate: ${a}

Totapuri in the crate: ${b}

The curve shows three facts at once. H = 0 at both ends, where all the mangoes are of one kind. H is largest — exactly 1 — in the middle, where the kinds are equally mixed. And the more even the mix, the higher H.

Note

Why base 2? Entropy counts yes/no questions. A 50/50 box needs exactly one question to settle it, so its entropy is 1 bit. Sina's eight equally likely cards had an entropy of \log_2 8 = 3 bits — and you needed exactly three questions. With more than two kinds, the formula simply gets one more term for each kind.

Speed Round: How Mixed?

Get five right to move on.

Sina