C#: entropy and information gain for decision trees

Before you start

C# Math.Log2 and loops.

Measure how much a feature reduces uncertainty about a label, the criterion used to choose a split.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A decision tree chooses the feature that best separates the labels. Entropy measures the impurity of a set: for a probability p of the positive class it is −p·log2(p) − (1 − p)·log2(1 − p). It is 0 for a pure set and 1 for an even split of two classes.

Information gain is the entropy of the whole set minus the weighted average entropy of the subsets after splitting on a feature. The classic play-tennis data have 9 yes and 5 no, giving entropy 0.940. Splitting on Outlook gives Sunny (2 yes, 3 no), Overcast (4 yes, 0 no), and Rain (3 yes, 2 no), and a gain of 0.247, the largest of the four features, so ID3 would put Outlook at the root.

Code example

using System;
using System.Globalization;

class Program {
  static double Entropy(int yes, int no) {
    double total = yes + no;
    double result = 0;
    foreach (int count in new[] { yes, no }) {
      if (count > 0) {
        double p = count / total;
        result -= p * Math.Log2(p);
      }
    }
    return result;
  }

  static string F(double v) {
    return v.ToString("F3", CultureInfo.InvariantCulture);
  }

  static void Main() {
    double whole = Entropy(9, 5);
    int[][] outlook = { new[] { 2, 3 }, new[] { 4, 0 }, new[] { 3, 2 } };
    double remainder = 0;
    foreach (int[] group in outlook) {
      remainder += (group[0] + group[1]) / 14.0 * Entropy(group[0], group[1]);
    }
    Console.WriteLine("entropy of the data: " + F(whole));
    Console.WriteLine("entropy after splitting on Outlook: " + F(remainder));
    Console.WriteLine("information gain: " + F(whole - remainder));
  }
}

Output

entropy of the data: 0.940
entropy after splitting on Outlook: 0.694
information gain: 0.247

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1using System;

2using System.Globalization;

4class Program {

5 static double Entropy(int yes, int no) {

6 double total = yes + no;

7 double result = 0;

8 foreach (int count in new[] { yes, no }) {

9 if (count > 0) {

10 double p = count / total;

11 result -= p * Math.Log2(p);

12 }

13 }

14 return result;

15 }

17 static string F(double v) {

18 return v.ToString("F3", CultureInfo.InvariantCulture);

19 }

21 static void Main() {

22 double whole = Entropy(9, 5);

23 int[][] outlook = { new[] { 2, 3 }, new[] { 4, 0 }, new[] { 3, 2 } };

24 double remainder = 0;

25 foreach (int[] group in outlook) {

26 remainder += (group[0] + group[1]) / 14.0 * Entropy(group[0], group[1]);

27 }

28 Console.WriteLine("entropy of the data: " + F(whole));

29 Console.WriteLine("entropy after splitting on Outlook: " + F(remainder));

30 Console.WriteLine("information gain: " + F(whole - remainder));

31 }

32}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Each class adds −p·log2(p) bits; a class with count 0 contributes nothing.	`—`	—
9 yes and 5 no gives about 0.940 bits.	`entropy = 0.940`	—
Weight each subset's entropy by its share of the data: Sunny 5/14, Overcast 4/14, Rain 5/14.	`Overcast is pure, so it contributes 0`	—
Gain = 0.940 − 0.694 = 0.247 bits.	`Overcast is pure, so it contributes 0`	entropy of the data: 0.940 entropy after splitting on Outlook: 0.694 information gain: 0.247

Behind the scenes

How C# processes this code

C# compiles to code for the .NET runtime, which invokes the program entry point.

Cost and common mistakes

O(n·d) to evaluate every feature for n rows and d features.

Information gain favours features with many distinct values, such as an ID column. Gain ratio and pruning address this.
Skipping the count > 0 test would compute 0 · log(0), which is NaN.
Real trees stop growing or are pruned to avoid memorizing the training data.

Try it yourself

What is the entropy of a 50/50 split?

Reveal answer and reasoning

Exactly 1 bit: −0.5·log2(0.5) − 0.5·log2(0.5) = 1.