PIXELBANKv8.2.0
Menu
Sign In

Information Gain

EasyDecision Trees

Compute the information gain from splitting a dataset.

Given a parent set of labels and the labels in two child subsets after a split, compute:

IG=H(parent)−∣left∣∣parent∣H(left)−∣right∣∣parent∣H(right)IG = H(parent) - \frac{|left|}{|parent|} H(left) - \frac{|right|}{|parent|} H(right)

where HH is the entropy: H=−∑k=1Kpklog⁡2(pk)H = -\sum_{k=1}^{K} p_k \log_2(p_k)

Use 0log⁡2(0)=00 \log_2(0) = 0 by convention. Return the information gain rounded to 4 decimal places.

Example:

Input:
parent = [1, 1, 0, 0]
left = [1, 1]
right = [0, 0]
Output:
1.0
Reasoning:
  • First, we calculate the entropy of the parent set: H(parent)=−(24log⁡2(24)+24log⁡2(24))=−(12log⁡2(12)+12log⁡2(12))=1H(parent) = -\left(\frac{2}{4} \log_2\left(\frac{2}{4}\right) + \frac{2}{4} \log_2\left(\frac{2}{4}\right)\right) = -\left(\frac{1}{2} \log_2\left(\frac{1}{2}\right) + \frac{1}{2} \log_2\left(\frac{1}{2}\right)\right) = 1
  • Then, we calculate the entropy of the left and right child sets: H(left)=−(22log⁡2(22))=0H(left) = -\left(\frac{2}{2} \log_2\left(\frac{2}{2}\right)\right) = 0 and H(right)=−(22log⁡2(22))=0H(right) = -\left(\frac{2}{2} \log_2\left(\frac{2}{2}\right)\right) = 0
  • Next, we apply the information gain formula: IG=H(parent)−∣left∣∣parent∣H(left)−∣right∣∣parent∣H(right)=1−24⋅0−24⋅0=1IG = H(parent) - \frac{|left|}{|parent|} H(left) - \frac{|right|}{|parent|} H(right) = 1 - \frac{2}{4} \cdot 0 - \frac{2}{4} \cdot 0 = 1
  • The final output is 1.01.0 after rounding to 4 decimal places

Constraints:

  • parent, left, right are lists of class labels
  • left and right together form the parent
  • Return information gain rounded to 4 decimal places
  • Use log base 2
Editor

Test Results

0/0
Run code to see test results.