Attribute Selection Measures in Data Mining

Every decision tree, at every node, has to answer the same question: of all the attributes still available, which one should this split be based on? Attribute Selection Measures (ASMs) are the statistical criteria that answer that question, by scoring how well each candidate attribute separates the data into purer subsets. This lesson works through the three most common measures — entropy, information gain, and the Gini index — with one dataset carried through all three so the numbers can be compared directly.

The Dataset Used Throughout This Lesson

Ten training records record whether a match was played, alongside the day's weather:

Weather = Sunny:    4 records (1 Play=Yes, 3 Play=No)
Weather = Overcast: 3 records (3 Play=Yes, 0 Play=No)
Weather = Rainy:    3 records (2 Play=Yes, 1 Play=No)
Total:              10 records (6 Play=Yes, 4 Play=No)

Entropy: Measuring Impurity

Entropy measures how mixed a set of records is with respect to the target class. A set containing only one class has entropy 0 (completely pure); a set split evenly between two classes has the maximum possible entropy for two classes, 1. The formula for a set D with two classes is:

Entropy(D) = -p(Yes) x log2(p(Yes)) - p(No) x log2(p(No))

Applied to the full dataset before any split (6 Yes, 4 No out of 10):

p(Yes) = 0.6,  log2(0.6) ≈ -0.7370
p(No)  = 0.4,  log2(0.4) ≈ -1.3219

Entropy(D) = -(0.6 x -0.7370) - (0.4 x -1.3219) = 0.4422 + 0.5288 ≈ 0.9710

An entropy of 0.9710 (close to the maximum of 1) confirms what the raw counts already suggest: the dataset is close to evenly split and therefore highly impure before any splitting is done.

Information Gain: Measuring the Value of a Split

Information Gain is simply how much the entropy drops after splitting on a candidate attribute — the entropy before the split, minus the size-weighted average entropy of the resulting subsets:

IG(D, A) = Entropy(D) - sum over each subset Dv of [ (|Dv| / |D|) x Entropy(Dv) ]

First, compute the entropy of each subset produced by splitting on Weather:

Sunny (1 Yes, 3 No out of 4):
  Entropy = -(0.25 x log2(0.25)) - (0.75 x log2(0.75)) = -(0.25 x -2.0) - (0.75 x -0.415) = 0.500 + 0.311 ≈ 0.8113

Overcast (3 Yes, 0 No out of 3):
  Entropy = 0   (a pure subset always has zero entropy)

Rainy (2 Yes, 1 No out of 3):
  Entropy = -(0.667 x log2(0.667)) - (0.333 x log2(0.333)) = -(0.667 x -0.585) - (0.333 x -1.585) = 0.390 + 0.528 ≈ 0.9183

Then combine them, weighted by how large each subset is relative to the full dataset:

Weighted entropy after split = (4/10 x 0.8113) + (3/10 x 0) + (3/10 x 0.9183)
                              = 0.3245 + 0 + 0.2755
                              = 0.6000

Information Gain(Weather) = Entropy(D) - Weighted entropy = 0.9710 - 0.6000 = 0.3710

A gain of 0.3710 bits means splitting on Weather removes a substantial fraction of the original uncertainty — and because information gain is computed the same way for every candidate attribute, the tree-building algorithm simply picks whichever attribute produces the largest gain at each node, which is exactly how C4.5, covered in its own dedicated lesson, decides where to split.

The Gini Index: A Faster Alternative to Entropy

The Gini index measures impurity using a different formula that avoids logarithms entirely, which makes it computationally cheaper — this is the criterion CART-style trees use by default:

Gini(D) = 1 - sum of (p_i)^2 for each class i

Computing it for the same dataset and the same three-way split:

Gini(D) = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 1 - 0.52 = 0.48

Gini(Sunny)    = 1 - (0.25^2 + 0.75^2) = 1 - (0.0625 + 0.5625) = 0.375
Gini(Overcast) = 1 - (1.0^2 + 0.0^2)   = 1 - 1.0 = 0            (pure, same as entropy)
Gini(Rainy)    = 1 - (0.667^2 + 0.333^2) = 1 - (0.445 + 0.111) = 0.444

Weighted Gini after split = (4/10 x 0.375) + (3/10 x 0) + (3/10 x 0.444)
                           = 0.150 + 0 + 0.133
                           = 0.283

Gini Gain(Weather) = Gini(D) - Weighted Gini = 0.48 - 0.283 = 0.197

Entropy and Gini agree on the direction of the result here — both show Weather reduces impurity substantially, and both correctly identify Overcast as a perfectly pure subset — but they don't have to agree on which of two candidate attributes is best in every case, because the two formulas weight impurity slightly differently. In practice, Gini's avoidance of logarithms makes it noticeably faster to compute on large datasets with many candidate attributes, which is why it's the default splitting criterion in many implementations even though entropy-based information gain remains the more commonly taught measure.

Where This Fits

These measures are the mechanism inside every decision-tree algorithm covered elsewhere in this series — C4.5 and rule-based classification both depend on choosing the right attribute at each split — and the same overfitting risk that motivates tree pruning, covered in its own dedicated lesson, is precisely the risk of a tree that keeps splitting on attributes with only a marginal information gain, chasing patterns specific to the training data rather than patterns that generalize.