Decision Trees: Gini Index, Information Gain and How Splits Are Chosen
A decision tree classifies records with a series of attribute tests. At each node a greedy algorithm picks the test that most reduces impurity, measured by the Gini index or entropy.
A decision tree has a root, internal nodes that hold an attribute test condition, and leaves with class labels. In the general framework for building a classification model, the training records are used to induce a model that is then applied to the test set. Tree growing is greedy: at each node it picks the locally best split without looking ahead, which is fast but not guaranteed optimal.
Impurity measures: for a node t with class fractions p(i), Gini = 1 - sum of p(i) squared, and entropy = - sum of p(i) log2 p(i). If all records at node t belong to one class, Gini is 0 (pure). For a 2-class problem with probabilities p and 1 - p, Gini is maximum, 0.5, when p = 0.5 and 0 when p is 0 or 1. The gain of a split = impurity of the parent - weighted average impurity of the children; pick the split with the highest gain.
Test conditions depend on the attribute type. Nominal: multiway split (one branch per value) or binary split grouping values. Ordinal: groupings that preserve order (do not mix Small with Large while leaving Medium out). Continuous: a binary split with a threshold (A < v) or discretization into ranges.
Key points
- Gini = 1 - sum p(i)^2; pure node has Gini 0; 2-class maximum is 0.5.
- Gain = parent impurity - weighted child impurity.
- Greedy: best local split at each node.
- Ordinal splits must preserve order.
- Continuous attributes use thresholds or discretization.
Worked example
A node has 6 records of class A and 4 of class B: Gini = 1 - 0.36 - 0.16 = 0.48. A split gives left (4 A, 0 B) with Gini 0 and right (2 A, 4 B) with Gini = 1 - 1/9 - 4/9 = 0.444. Weighted = 0.6 x 0.444 = 0.267, so gain = 0.48 - 0.267 = 0.213.
Common questions
What is the Gini value of a pure node?
0, because all records belong to one class.
Why are decision trees called greedy?
They choose the best split at each step without considering later steps.
Practice questions on this topic
Try these, then open the app to check your answers with explanations.
- When designing a test condition for an ordinal attribute (e.g., Shirt Size: Small, Medium, Large, Extra Large), which group split violates the order property?
- A. {Small, Medium} and {Large, Extra Large}
- B. Multi-way split using all distinct values
- C. {Small} and {Medium, Large, Extra Large}
- D. {Small, Large} and {Medium, Extra Large}
- How is the Gain calculated when choosing an attribute test condition to find the best split?
- A. Gain = M - P
- B. Gain = P + M
- C. Gain = P * M
- D. Gain = P - M (P is impurity before, M is weighted child impurity)
- What are the primary ways of handling splitting based on continuous attributes in decision trees?
- A. Using only multi-way splits with equal frequency bucketing
- B. Converting continuous attributes directly into class labels
- C. Discretization (static/dynamic) and Binary Decisions (A < v or A ≥ v)
- D. Bagging and Boosting only
- In the general framework for building a classification model, what is the correct technical distinction between the two core phases?
- A. Induction is used on the test set to map attribute sets, while Deduction builds the model using the training set.
- B. Induction evaluates node impurity, whereas Deduction optimizes the Gini gain.
- C. Induction learns a model from the training set, whereas Deduction applies the learned model to classify records in the test set.
- D. Induction calculates the class probability distribution, while Deduction discretizes continuous variables.
- How can nominal attributes be split when constructing test conditions for decision trees?
- A. Only through dynamic discretization ranges.
- B. Strictly through binary splits that preserve strict numeric ordering.
- C. Either via multi-way splits (using as many partitions as distinct values) or binary splits (dividing values into two subsets).
- D. Only via multi-way splits based on the exact count of unique records.
- What is the defining characteristic of a greedy approach when determining the best split in decision tree induction?
- A. It evaluates all future tree branches globally before making the first split.
- B. It selects the split that produces nodes with purer class distributions at the current step without looking ahead.
- C. It avoids calculating impurity measures to speed up training.
- D. It prioritizes multi-way splits over binary splits to minimize tree depth.
Related topics
- What is Data Mining? Tasks: Classification, Clustering, Regression, Association Rules
- The KDD Process: Knowledge Discovery in Databases Steps
- Types of Attributes: Nominal, Ordinal, Interval and Ratio
- Data Cleaning: Noise, Outliers, Missing Values and Inconsistent Data
- Binning: Equal-Width vs Equal-Frequency (Equal-Depth) with Examples
- Data Normalization: Min-Max, Z-Score and Decimal Scaling with Examples
- All topics: Data Mining
BASMAGLY is an independent student project, not an official Delta University site. Check lectures and your instructor for the final word.