Home / Summaries / COMP 3711 / impurity-error-classification

Classification - Impurity Measures

Q: What is an impurity measure? What do maximum and minimum impurity mean?

An impurity measure quantifies how mixed the class distribution is at a node: Maximum impurity — all classes are equally represented (e.g., 50/50 for binary) → most uncertain Minimum impurity (0) — all records belong to the same class → perfectly pure node The goal of splitting is to choose the attribute that most reduces impurity in the child nodes.

7 important questions on Classification - Impurity Measures

What is an impurity measure? What do maximum and minimum impurity mean?

An impurity measure quantifies how mixed the class distribution is at a node:

Maximum impurity — all classes are equally represented (e.g., 50/50 for binary) → most uncertain
Minimum impurity (0) — all records belong to the same class → perfectly pure node

The goal of splitting is to choose the attribute that most reduces impurity in the child nodes.

Write the formulas for Entropy, Gini Index, and Classification Error.

Let p(i|t) = fraction of records at node t belonging to class i, over c classes:

Entropy: −Σᵢ p(i|t) · log₂ p(i|t)
Gini Index: 1 − Σᵢ [p(i|t)]²
Classification Error: 1 − maxᵢ p(i|t)

All three equal 0 at a pure node and are maximised at a uniform distribution.

For a binary node with p fraction positive, compute all three impurity measures at p = 0.5 and p = 0.

At p = 0.5 (most impure):

Entropy: −(0.5·log₂0.5 + 0.5·log₂0.5) = 1.0 bit
Gini: 1 − (0.5² + 0.5²) = 0.5
Classification error: 1 − 0.5 = 0.5

At p = 0 (pure):

All three measures = 0

What is the key behavioural difference between classification error and the other two measures?

Classification error is less sensitive to changes in class probabilities than Gini or Entropy. Near the extremes (very pure or very impure nodes), classification error changes slowly while Gini and Entropy change more sharply. This means classification error is a cruder signal for choosing splits — it may not distinguish between two splits that Gini or Entropy would rank differently.

What is the gain criterion Δ? Write the formula.

The gain of a split measures the reduction in impurity:
Δ = I(parent) − Σⱼ (N(vⱼ)/N) · I(vⱼ)
Where:

I(parent) = impurity of the parent node
N(vⱼ) = number of records in child j
N = total records at parent
I(vⱼ) = impurity of child j

The split with the highest Δ is selected. When entropy is used as I, Δ is called Information Gain.

Why does Information Gain favour high-cardinality attributes? Give an example.

An attribute with many distinct values (e.g., Customer ID) creates many tiny child nodes — often one record per node — which are each perfectly "pure" (one class). This maximises the impurity reduction Δ, making it look like the best split.
But it has zero predictive power: the model has memorised training IDs, not learned a general pattern. It will fail completely on unseen records with new IDs.

What is Gain Ratio? How does it penalise high-cardinality attributes?

Gain Ratio = Information Gain / Split Info
Split Info = −Σⱼ (N(vⱼ)/N) · log₂(N(vⱼ)/N)
Split Info is the entropy of the attribute's own value distribution. If an attribute creates many partitions (high cardinality), its Split Info is high — dividing by it reduces the Gain Ratio and penalises that attribute. Used by C4.5.

The question on the page originate from the summary of the following study material:

COMP 3711

View summary

A unique study and practice tool
Never study anything twice again
Get the grades you hope for
100% sure, 100% understanding

Remember faster, study better. Scientifically proven.

Classification - Impurity Measures

7 important questions on Classification - Impurity Measures

What is an impurity measure? What do maximum and minimum impurity mean?

Write the formulas for Entropy, Gini Index, and Classification Error.

For a binary node with p fraction positive, compute all three impurity measures at p = 0.5 and p = 0.

What is the key behavioural difference between classification error and the other two measures?

What is the gain criterion Δ? Write the formula.

Why does Information Gain favour high-cardinality attributes? Give an example.

What is Gain Ratio? How does it penalise high-cardinality attributes?

Summaries related to Classification - Impurity Measures

COMP 3711

Global politics

Essentials of international relations

Behavioral genetics

Management and organisational behaviour

Follow Up Engels idioom 4/5 H

International Business

Marketing fundamentals

Projectmanagement, A practical Approach-Engl…

Basic Management Accounting for the Hospital…

International business

Organization theory and design