Machine Learning

Decision Trees

📅 Published: 2026-06-28

🎓 Level: postgraduate

👥 Audience: Postgraduate students in Machine Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

1.5.2.1 Classification — covered in Introduction to Machine Learning
2.6 Data Preprocessing Overview — covered in Data Preprocessing for Machine Learning
3.1 Feature Engineering — Overview — covered in Feature Engineering and Linear Regression
3.9.3 Classification, Regression, and Probability Estimation — covered in Feature Engineering and Linear Regression
4.7.2 Data — covered in Linear Regression Complete Lecture Notes
5.13 Multi-Class Classification with Logistic Regression — covered in Logistic Regression — Lecture Notes

Decision Trees

8.1. Information Theory

Hook. You flip a coin. Before it lands, you are uncertain. If I tell you "it's a fair coin," you're still uncertain — 50-50. If I tell you "it's a double-headed coin," your uncertainty vanishes. Decision trees face this same problem at every split: how much did we just reduce our uncertainty? Information theory gives us a ruler to measure that reduction.

8.1.1 Intuition

Everyday analogy — Weather surprise. You check tomorrow's forecast. If the forecast says "100% chance of rain," you are not surprised when it rains. zero surprise. If it says "50% rain, 50% sun," you're maximally uncertain. If it says "90% rain," you'd be mildly surprised if it's sunny. However, not shocked.

Information theory quantifies this average surprise. A pure node (all records are class A) has zero surprise. you already know the answer. A 50-50 node has maximum surprise. you have no idea which class the next record belongs to. The math of entropy is designed to capture exactly this: it is the expected surprise of drawing a random record from a node and observing its class.

Where the analogy breaks: the weather forecast gives you one probability. A decision tree node gives you a distribution over C classes. Entropy generalizes the surprise idea to any number of classes.

8.1.2 Formal Definition

Information theory is the mathematical framework for quantifying, storing. communicating information. It studies three core operations: how to quantify information, how to transmit messages from one place to another. how to store messages.

In classification, information means a measure of uncertainty associated with a random event. When a sample arrives and its class label is unknown, there is uncertainty about which category it belongs to. Before classifying, we must quantify that uncertainty.

Information theory metrics. entropy, Gini index, misclassification error. are used inside decision tree classification to measure how pure or impure a node is after splitting.

A split that tells you "half the records are class A and half are class B" leaves uncertainty high. A split that tells you "all the records are class A" drops uncertainty to zero. Information theory gives us numbers for this intuition.

8.1.3 Worked Mini-Example

Tiny entropy calculation. A node has 6 records: 4 cats, 2 dogs.

The fraction of cats is $P (cat) = 4/6 \approx 0.667$ . The fraction of dogs is $P (dog) = 2/6 \approx 0.333$ .

If entropy is defined as $- \sum P lo g_{2} P$ :

$H = - [0.667 \times lo g_{2} (0.667) + 0.333 \times lo g_{2} (0.333)] \approx - [0.667 \times (- 0.585) + 0.333 \times (- 1.585)] \approx - [- 0.390 - 0.528] = 0.918$

An entropy of 0.918 means the node is somewhat impure. more cat-heavy. So less than maximum entropy (which would be 1.0 for a 3-3 split). However, not pure.

Sense-check: The node is not 50-50. So entropy should be less than 1. It's not all one class. So entropy should be more than 0. 0.918 sits in between, tilted toward the impure side because 4-2 is still somewhat mixed.

8.1.4 Assumptions & Scope

Scope: When entropy applies. Entropy (and information theory in general) assumes:

The class labels are discrete categories. Entropy is not directly meaningful for continuous targets (use variance/MSE instead).
The records are drawn independently from the same distribution (IID). If records are correlated (e.g., time series), the entropy of the empirical distribution may mislead.
The logarithm base determines the unit: base 2 gives bits, base e gives nats, base 10 gives dits. Decision trees use base 2 because information gain is measured in bits. how many yes/no questions you save.

When it breaks. Entropy is only a summary statistic of the class distribution. Two nodes with the same class proportions have the same entropy, even if one has 10 records and the other has 10,000. With very small samples, the empirical fractions $P (i ∣ t)$ are noisy estimates. entropy computed from 3 records is far less reliable than from 300.

8.1.5 Visual Intuition

The entropy curve for binary classification. Plot the fraction of the positive class $p$ on the x-axis (from 0 to 1) against entropy on the y-axis (from 0 to 1).

At $p = 0$ (all negative): entropy = 0. the curve touches the x-axis.
At $p = 1$ (all positive): entropy = 0. the curve touches the x-axis again.
At $p = 0.5$ (50-50 split): entropy = 1. the curve peaks, forming an arch.

The shape is a symmetric upside-down U. It rises steeply from the edges (a small admixture of the other class causes a rapid increase in entropy) and flattens near the peak (near 50-50, adding more of the majority class doesn't change entropy much).

Takeaway: Entropy is lowest at the extremes (pure nodes) and highest at the center (maximum confusion). A good split pushes child nodes toward the edges of this curve.

8.1.6 Pitfalls

"Entropy = 0 means no information." Wrong. Entropy = 0 means no uncertainty. you have perfect information. High entropy means high uncertainty. you lack information. The direction is inverted from everyday usage.
Confusing entropy with accuracy. Entropy measures node purity, not prediction accuracy. A node can have low entropy (mostly one class) but still misclassify the minority class records.
Forgetting the log base. Using natural log instead of $lo g_{2}$ changes the entropy values but not the ranking of attributes by information gain. the scaling factor cancels in the subtraction. However, the interpretability as "bits" is lost with natural log.

8.1.7 Student Q&A

Q: Why do we need both Gini index and entropy? Aren't they measuring the same thing? A: They both measure impurity. However, with different sensitivity. Entropy is grounded in information theory. it measures the expected number of bits needed to encode the class of a random record. Gini is a simpler quadratic that approximates entropy but is faster to compute (no logarithms). In practice they usually agree on the best split. However, not always. scikit-learn defaults to Gini because it's computationally cheaper, though entropy is available as criterion='entropy'.

8.1.8 Recap & Bridge

Entropy is a single number that says "how mixed are the classes in this node?" Zero = pure, maximum = 50-50. It is the yardstick we will use to measure whether a split was worth making. Next: the decision tree itself. the structure that uses these impurity numbers to grow.

8.1.9 Real-World & Domain Connection

Information theory, invented by Claude Shannon at Bell Labs in 1948, was originally built to solve a communication problem: how many bits do you need to send a message reliably over a noisy channel? The same math turned out to govern classification. Every time a decision tree splits on an attribute, it is essentially asking: "How many bits of information about the class label does this attribute give me?" This bridge between communication theory and machine learning is why decision trees are sometimes called information-theoretic classifiers.

8.1.10 Symbol Registry

Symbol	Meaning	LaTeX	Type / Domain
$P (i ∣ t)$	Fraction of records belonging to class $i$ at node $t$	$P (i ∣ t)$	scalar in $[0, 1]$
$C$	Total number of classes in the dataset	$C$	integer $\geq 2$
$t$	A particular node in the tree	$t$	node identifier
$D$	The dataset or parent node	$D$	set of records
$H (D)$	Entropy of dataset $D$ (or parent node)	$H (D)$	scalar $\geq 0$

Notation note: The lecture uses $P (i ∣ t)$ . Standard texts (Mitchell, Tan) often write this as $p_{i}$ when the node is clear from context. Both mean the same thing: the proportion of class $i$ at the current node.

8.2. Decision Tree Representation

Hook. Imagine a doctor diagnosing a patient. First question: "Do you have a fever?" If yes, one set of follow-ups. If no, a different path. The doctor is walking a mental decision tree. and so is every machine learning classifier built on this idea. The magic question: can we build this tree automatically from data?

8.2.1 Intuition

Everyday analogy — The twenty-questions game. You think of an animal. I ask: "Does it have fur?" If yes, I narrow to mammals. "Does it fly?" If yes, probably a bat. Each question cuts the remaining possibilities roughly in half. A good player picks questions that eliminate as many candidates as possible per question.

A decision tree does exactly this: at each internal node, it picks the attribute that best separates the classes. The "best" attribute is the one that gives the purest children. just like the twenty-questions player picks the question that leaves the fewest ambiguous candidates.

Where the analogy breaks: in twenty questions, the questions are chosen by a human with world knowledge. The decision tree algorithm has no world knowledge. it computes purity mathematically from the data alone.

8.2.2 Formal Definition

A decision tree is a flowchart-like structure used for classification. Given an instance with unknown class label, the attribute values of that instance are tested against the tree. Starting from the root, a series of questions about the characteristics of the instance lead down branches until a leaf node is reached. This holds the predicted class label.

Structure:

Root node. the topmost node in the tree. The root is an internal node because it tests an attribute. There is exactly one root.
Internal node. every internal node denotes a test on exactly one attribute (e.g., "Is body temperature warm or cold?").
Branch. each branch represents one possible outcome of the test (e.g., "Yes" or "No"). In a binary tree, every internal node has exactly two outgoing branches.
Leaf node. holds a class label. No further tests are made. The classification stops here.

Each path from root to leaf is a conjunction of attribute tests (e.g., "Outlook = Sunny AND Humidity = Normal"). The whole tree is a disjunction of these paths — "classify as Yes if Path-1 OR Path-2 OR Path-3."

8.2.3 Worked Example — Trace Through the Loan Default Tree

Dataset columns: homeowner (yes/no), marital status (single/married/divorced), annual income (continuous). Target: defaulted borrower (yes/no).

The trained tree:

           [Homeowner?]
           /          \
         Yes           No
          |             |
     Leaf: NO      [Marital Status?]
                  /        |         \
            Married    Single    Divorced
                |          \        /
            Leaf: NO    [Income < 80K?]
                         /         \
                       Yes          No
                        |            |
                   Leaf: YES    Leaf: NO

Trace three applicants: Applicant A: Homeowner=Yes → Leaf: NO. The tree predicts no default. Only one question needed. Applicant B: Homeowner=No, Marital Status=Married → Leaf: NO. Two questions, same prediction. Applicant C: Homeowner=No, Marital Status=Single, Annual Income=60K → Income < 80K = Yes → Leaf: YES. The tree predicts default. Three questions. Sense-check: The tree makes intuitive sense. homeowners and married applicants are lower risk. single/divorced non-homeowners with low income are higher risk. The tree captured a sensible risk hierarchy.

8.2.4 Assumptions & Scope

Scope: Where decision trees work best. Decision trees are naturally suited to problems where:

Instances are described by attribute-value pairs (fixed set of features).
The target function has discrete output values (classification).
Disjunctive descriptions may be required (the data separates into distinct "if-this OR if-that" regions).
The training data may contain errors or missing values (trees are strong to both).

Where they struggle:

When the true decision boundary is a smooth diagonal line (trees produce axis-aligned step boundaries).
When individual attributes are weak but combinations of many attributes are strong (a single tree tests one attribute at a time).
When the number of features is enormous relative to the number of samples (the tree can easily overfit).

8.2.5 Visual Intuition

Picture a tree drawn top-down. At the top sits the root node. a rectangle containing the first question. Below it, lines (branches) lead to child nodes. Each internal node is another rectangle with a question. Leaves are ovals (or rectangles with rounded corners) containing class labels like "Yes" or "No." In the loan default tree:

The root splits the dataset into two groups: 3 homeowners (all "No") and 7 non-homeowners.
The right child of the root splits again, separating married (3 records, all "No") from single/divorced (4 records, mixed).
The deepest leaf sits 3 levels down, reached only by non-homeowner, single/divorced, low-income applicants.

Takeaway: The depth of a leaf tells you how many questions were needed to isolate that prediction. Shallow leaves mean the class was easy to separate. deep leaves mean the class required many conditions.

8.2.6 Pitfalls

"The root is not an internal node." It is. The root tests an attribute. So it IS an internal node. Only leaves are not internal nodes.
"One leaf appears at every level." The loan default example happened to produce one leaf at each level. This is coincidental. not a general rule. Deeper trees may have no leaves until many levels down.
"The same attribute cannot appear twice." It can and often does. The age attribute might appear at depth 2 in one branch and depth 4 in another. A tree is not a linear ranking of features.

8.2.7 Comparison — Multi-Way vs Binary Trees

Property	Multi-way split (ID3, C4.5)	Binary split (CART)
Branches per node	One per attribute value	Always 2
Nominal attributes	Natural mapping	Must group values into two sets
Ordinal attributes	Preserves order naturally	Must preserve order when grouping
Tree depth	Shallower (wider nodes)	Deeper (more nodes)
Interpretability	Each branch = one value	Must decode groupings
scikit-learn	Not available	Default (CART-based)

When to pick which: Binary trees (CART) are more general. they handle any attribute type uniformly. Multi-way trees are more interpretable for nominal attributes with few values. In practice, binary trees dominate because of scikit-learn's CART implementation.

8.2.8 Student Q&A

Q: Can two different internal nodes use the same attribute? A: Yes. For example, after splitting on "car type," the "family" branch might use "gender" next. the "luxury" branch might also use "gender" next. Different branches are independent subproblems. they can reuse any attribute. Q: How is the root node chosen? How is the tree actually constructed? A: The algorithm evaluates every attribute as a candidate for the root. For each attribute, it computes an impurity measure (entropy or Gini) on the resulting children. The attribute that produces the purest children. largest reduction in impurity. is chosen as the root. This process repeats recursively at each child node. The specific math (information gain) is covered in the next sections.

8.2.9 Recap & Bridge

A decision tree is a hierarchy of attribute tests ending in class predictions. The root and internal nodes ask questions. leaves give answers. The same dataset can produce many different trees. the algorithm's job is to find the best one. Next: Hunt's algorithm, the recursive method that grows these trees.

8.2.10 Real-World & Domain Connection

Decision trees are among the most widely deployed machine learning models in industry because of their interpretability. Banks use them for credit scoring (the loan default example is real). Medical diagnosis systems use them to triage patients based on symptoms. Customer support routing systems use decision trees to direct callers to the right department. In all these cases, the "why" of a prediction matters as much as the prediction itself. and decision trees provide a human-readable trail of decisions that neural networks cannot.

Key insight (from lecture): Multiple different trees can fit the same dataset. If "marital status" had been the root instead of "homeowner," the tree would look different. The challenge is finding the best tree. and that is what impurity measures and splitting criteria are designed to solve.

8.3. Hunt's Algorithm — The Basic Decision Tree Building Method

Hook. You have a pile of loan applications. some defaulted, some didn't. You want a flowchart that separates them. But there are billions of possible flowcharts. Which one is best? And how do you build it without trying all of them? Hunt's algorithm gives the recursive recipe that every major decision tree algorithm still uses today.

8.3.1 Purpose

Hunt's algorithm is the foundational recursive method that underlies all major decision tree algorithms — ID3, C4.5, CART, SLIQ, and SPRINT. It solves the problem of growing a decision tree from training data by recursively partitioning records into successively purer subsets. Every modern decision tree algorithm is a variation on Hunt's core idea, differing mainly in how they choose the "best" attribute at each split.

8.3.2 Inputs & Outputs

Inputs:

$D_{t}$ : the set of training records at the current node $t$
A set of candidate attributes available for splitting
An impurity measure (entropy, Gini, or misclassification error) for choosing splits

Outputs:

A decision tree where each leaf is labeled with a class
The tree may have some impure leaves if attributes run out before purity is reached

8.3.3 Steps — The Recursive Recipe

Hunt's algorithm proceeds as follows. At each node $t$ with records $D_{t}$ :

Check for purity. If all records in $D_{t}$ belong to the same class $y$ , then $t$ is a leaf node labeled $y$ . Stop.

Rationale: A pure node needs no further splitting. the answer is already certain.

Check for exhausted attributes. If no more attributes remain for splitting, $t$ is a leaf node labeled with the majority class in $D_{t}$ . Stop.

Rationale: You've used all available information. The best you can do is guess the most common class.

Otherwise, split. Select the "best" attribute $A^{*}$ (using an impurity measure. see sections 5-6). For each possible value $v$ of $A^{*}$ , create a child node and assign to it the subset $D_{t, v}$ of records where $A^{*} = v$ .

Rationale: The attribute that produces the purest children gives the biggest reduction in uncertainty.

Recurse. Apply steps 1–4 to each child node, using the remaining attributes.

Rationale: Each child is now an independent subproblem. a smaller dataset with one fewer attribute.

Stopping conditions summary:

All records at a node belong to the same class (node is pure).
No more attributes remain for splitting (majority vote applied).
Optional: early termination (max depth reached, min samples per leaf, etc.. covered in section 13 on overfitting).

8.3.4 Trace — Loan Default Data Step by Step

Dataset: 10 loan applicants. Target: defaulted borrower (Yes/No). Attributes: homeowner, marital status, annual income.

Step A — Initial tree (single node): All 10 records sit at the root. The majority class is "No" (more non-defaulters). If forced to stop here, the tree would label the single node "defaulted = No". the majority guess. This is the default prediction for any tree that cannot split further.

Step B — First split on "homeowner": The root is impure (both Yes and No). So we split. Homeowner is chosen as the best attribute (the math of why it's best is covered in section 6).

Homeowner = Yes: 3 records, all "defaulted = No." → Leaf: defaulted = No (pure. rule 1 triggers).
Homeowner = No: 7 records. mixture of classes. → Internal node labeled "defaulted = No" (majority provisional label). However, impure. must recurse (rule 3).

Step C — Split "homeowner = No" on "marital status": CART uses binary splits. So the three marital status values must be grouped into two sets. The algorithm determines {Married} vs {Single, Divorced} is best.

Married: 3 records, all "defaulted = No." → Leaf: defaulted = No (pure).
Single/Divorced: 4 records, mixed classes. → Internal node. must recurse.

Step D — Split "Single/Divorced" on "annual income": A threshold of 80K is found to give the best binary split:

Annual income < 80K: records are all "defaulted = Yes." → Leaf: defaulted = Yes (pure).
Annual income ≥ 80K: records are all "defaulted = No." → Leaf: defaulted = No (pure).

Step E — Final tree complete. All branches end in pure leaves. The tree has 3 internal nodes and 5 leaves.

Key observation: At every level of this particular tree, exactly one leaf appeared. This is coincidental for this dataset — NOT a general rule. Deeper datasets may require many levels before any leaf node emerges.

Sense-check: The tree's logic is interpretable. homeowners are safe, married renters are safe, single/divorced renters are risky only if income is low. This matches banking intuition.

8.3.5 Complexity & Cost

At each node, the algorithm must evaluate every remaining attribute as a candidate split. For $d$ attributes and $n$ records:

Per-node cost: $O (d \cdot n lo g n)$ for continuous attributes (sorting to find thresholds) or $O (d \cdot n)$ for categorical.
Tree depth: In the worst case, the tree can be $O (n)$ deep (one record per leaf. severe overfitting).
Total worst-case: $O (d \cdot n^{2} lo g n)$ for a full tree without pruning.

In practice, with reasonable depth limits (e.g., max_depth=5 or max_depth=10), the cost is $O (d \cdot n lo g n)$ . very fast for typical datasets with thousands of records and dozens of features.

8.3.6 Pitfalls

"One leaf per level is normal." The loan default example produced one leaf at each level purely by chance. Most real datasets produce leaves at irregular depths.
"The algorithm backtracks." Hunt's algorithm is greedy. once an attribute is chosen as a split, it is never reconsidered. A suboptimal choice at the root cascades through the entire tree. There is no global optimization.
"More attributes = better tree." Exhausting all attributes forces the tree to split on weak or irrelevant features, leading to overfitting. Early stopping (pre-pruning) is often better.

8.3.7 Student Q&A

Q: Why are "single" and "divorced" combined into one group? A: CART (and scikit-learn) performs only binary splits. When an attribute has more than two values. like marital status with three. the algorithm must partition the values into two groups. It evaluates all possible groupings and picks the one that gives the purest children. Here, {Married} vs {Single, Divorced} was best. A multi-way split algorithm like ID3 would create three separate branches instead.

Q: What happens if we use all attributes and still have impure nodes? A: The tree terminates. The impure node is labeled with the majority class. the model accepts the resulting error. 100% training accuracy is not guaranteed. and chasing it usually leads to severe overfitting anyway.

Q: Does the algorithm assign weights to attributes? A: Not directly. The tree grows by testing attribute values, not by weighting them. The advantage of decision trees is that they work well without requiring explicit feature importance weights. though feature importance can be derived after training by measuring how much each attribute reduced impurity across all splits.

8.3.8 Recap & Bridge

Hunt's algorithm is the recursive guts of every decision tree: check if pure → if not, pick the best attribute and split → recurse on each child. The algorithm is greedy and never backtracks. Next: the splitting criteria. how "best attribute" is actually measured.

8.3.9 Real-World & Domain Connection

Hunt's algorithm dates back to the 1960s (Hunt, Marin, & Stone, 1966) and was one of the earliest machine learning algorithms for concept learning. Its recursive divide-and-conquer pattern influenced not just decision trees but many later algorithms. random forests, gradient boosted trees. even some neural architecture search methods. In modern libraries like scikit-learn, the DecisionTreeClassifier uses an optimized CART variant of Hunt's algorithm. The same recursive partitioning logic underpins XGBoost and LightGBM, two of the most successful algorithms in Kaggle competitions and industry ML systems.

8.4. Splitting Criteria

Hook. An attribute with 1000 distinct values can split the data into 1000 pure child nodes. Perfect purity! But the tree is useless. each leaf has one record. you've learned nothing general. This is the splitting criteria paradox: pure splits are not always good splits. How you split depends on what kind of attribute you have.

8.4.1 Intuition

Everyday analogy — Sorting your bookshelf. You have books by different authors from different genres spanning different centuries. You can split them by author (nominal. no natural order), by publication decade (ordinal. has an order), or by page count (continuous. a number). Each type of split requires a different rule. "Author = Tolstoy" is a yes/no test. "Decade < 1950" is a threshold test. "Page count in [100, 300]" is a range test. Decision trees must decide what kind of test each attribute allows.

Where the analogy breaks: books can belong to multiple genres (overlapping categories). However, decision tree attributes are mutually exclusive. each record follows exactly one branch.

8.4.2 Formal Definition

At each recursive step of tree growth, we must select an attribute test condition to divide records into smaller subsets. Three things are needed:

A method for specifying the test condition for different attribute types (binary, nominal, ordinal, continuous).
A measure for evaluating the goodness of a split (impurity measures. section 5).
A stopping condition (covered in section 3).

8.4.3 Splitting by Attribute Type

#### Nominal Attributes (e.g., marital status, car type, color)

Nominal attributes have values with no intrinsic order. Two splitting strategies:

Multi-way split: one branch per distinct value. Marital status → three branches: Single | Married | Divorced. Used by ID3 and C4.5.
Binary split: partition values into two groups. For marital status with 3 values, there are $2^{3 - 1} - 1 = 3$ possible binary groupings:

{Single, Divorced} vs {Married}
{Single, Married} vs {Divorced}
{Single} vs {Married, Divorced}

CART evaluates all possible groupings and picks the one with the lowest weighted impurity. For an attribute with $k$ values, there are $2^{k - 1} - 1$ possible binary groupings. manageable for small $k$ , explosive for large $k$ .

#### Ordinal Attributes (e.g., shirt size: S, M, L, XL, XXL. education level)

Ordinal attributes have values with a meaningful order. Binary splits must preserve the order property:

✅ Valid: {S, M} vs {L, XL, XXL}. the split is at a single cut point in the ordering.
✅ Valid: {S, M, L} vs {XL, XXL}. another cut point.
❌ Invalid: {S, L} vs {M, XL, XXL}. This grouping jumps across the ordering, destroying the ordinal relationship.

An ordinal attribute with $k$ values allows $k - 1$ possible binary splits (one at each gap in the ordering). This is much fewer than the $2^{k - 1} - 1$ groupings for nominal attributes, making ordinal splits computationally cheaper.

#### Continuous Attributes (e.g., annual income, temperature, age)

Continuous attributes can take any real value. Two strategies:

Binary split (threshold): Choose a threshold $v$ . Two branches: " $< v$ " and " $\geq v$ ." The threshold is found by sorting values and testing candidate cut points where the class label changes (see section 10 for the full algorithm). This is the CART approach.
Multi-way split (discretization): Convert continuous values into discrete bins before tree building. For example, income could become: <10K, 10K–25K, 25K–50K, 50K–80K, >80K. This is a preprocessing step. the tree sees a nominal/ordinal attribute afterward.

Discretization can help when the relationship between the attribute and the class is non-monotonic. However, it risks losing fine-grained information. Binary threshold splits preserve more granularity.

8.4.4 Algorithm-Specific Split Types

Algorithm	Split type	Notes
ID3	Multi-way	Original algorithm. natural for nominal attributes
C4.5	Multi-way	ID3's successor. adds gain ratio and continuous handling
CART	Binary only	Most widely used. scikit-learn's default
SLIQ, SPRINT	Binary only	Scalable CART variants for large datasets

8.4.5 Assumptions & Scope

Scope: What splitting criteria assume.

Each record follows exactly one branch. the test condition partitions the data disjointly and exhaustively.
For binary splits of nominal attributes with many values, the number of possible groupings grows exponentially ( $2^{k - 1} - 1$ ). With $k > 20$ , exhaustive search becomes impractical. heuristic grouping methods are used instead.
For continuous attributes, the threshold search assumes that the optimal split lies between records with different class labels. This is always true for impurity-based measures. there is never a reason to split between two records with the same class.

8.4.6 Visual Intuition

Picture a dataset as points on a plane, colored by class. A decision tree can only draw axis-aligned boundaries. vertical or horizontal lines.

A nominal split asks "Is the shape a circle or a square?". it partitions by category membership.
An ordinal split asks "Is the size small/medium or large/XL?". it partitions at a rank boundary.
A continuous split asks "Is x < 5?". it draws a vertical line at x=5, splitting the plane into left and right halves.

After the first split, each sub-region gets its own axis-aligned boundary, recursively. The final decision boundary is a staircase of axis-aligned segments. If the true boundary is a diagonal line, the tree approximates it with many small steps. requiring depth proportional to precision.

Takeaway: The type of attribute determines what shape of boundary the tree can draw. Continuous attributes give the finest granularity (any threshold), nominal attributes give the coarsest (one branch per value or group).

8.4.7 Pitfalls

Binary-splitting a nominal attribute with many values. An attribute like "zip code" with 500 values requires checking $2^{499} - 1$ groupings. computationally impossible. Algorithms either use heuristics or fall back to multi-way splits with gain ratio normalization.
Ordinal treated as nominal. If you tell the algorithm "shirt size" is nominal, it may propose the invalid grouping {S, L} vs {M, XL}. Always declare ordinal attributes correctly.
Discretizing continuous before splitting. Pre-discretization can hide useful threshold information. Let the tree find the threshold itself (CART approach) unless you have a domain reason for specific bins.

8.4.8 Recap & Bridge

How you split depends on what kind of attribute you have: nominal (group values), ordinal (preserve order), continuous (find threshold). Different algorithms offer different split types. Next: how to measure whether a split was actually good. impurity measures.

8.4.9 Real-World & Domain Connection

The choice between binary and multi-way splits has practical deployment implications. Binary trees (CART) produce deeper but more uniform trees that are easier to code as nested if-else statements in production systems (e.g., credit scoring engines). Multi-way trees produce shallower trees but require case/switch logic that some deployment environments don't handle efficiently. This is why scikit-learn (and most production ML libraries) default to CART-style binary splits.

8.5. Impurity Measures — Quantifying Node Purity

Hook. You walk into a room with 100 people. Everyone is a cat person. You ask one person "cat or dog?". zero uncertainty. Next room: 50 cat people, 50 dog people. Now you have no idea what the next person will say. Decision trees need a number for this feeling. a single value that says "how mixed is this node?" That number is the impurity measure.

8.5.1 Intuition

Everyday analogy — Sorting a bag of marbles. You have a bag with blue and red marbles. If all marbles are blue, one glance tells you everything. zero impurity. If half are blue and half are red, you're maximally uncertain about what you'll draw next. If the bag is 80% blue and 20% red, you have a good guess (blue) but you'll be wrong 20% of the time. moderate impurity.

Three ways to put a number on this:

Gini: "What's the chance two random draws disagree?" (0 = never disagree, 0.5 = coin flip)
Entropy: "How many bits do I need to encode what I drew?" (0 bits = always the same, 1 bit = 50-50 for two classes)
Misclassification error: "If I always guess the majority, how often am I wrong?" (simplest to understand, weakest for guiding splits)

Where the analogy breaks: in the marble bag, you can count marbles physically. In a decision tree node, the "marbles" are training records. the fractions are empirical proportions.

8.5.2 Formal Definition

An impurity measure quantifies how mixed the class labels are at a given node. A node where all records belong to one class has minimum impurity (pure). A node where records are equally split across classes has maximum impurity.

Three impurity measures exist:

Gini Index. used by CART (and scikit-learn default).
Entropy. used by ID3 and C4.5.
Misclassification Error. rarely used in practice for tree growth.

Notation: $P (i ∣ t)$ is the fraction of records belonging to class $i$ at node $t$ . For 6 records of class 0 and 4 of class 1: $P (0 ∣ t) = 0.6$ , $P (1 ∣ t) = 0.4$ . Standard texts (Tan §4.3) write this as $p (i ∣ t)$ . equivalent.

8.5.3 Gini Index

$Gini (t) = 1 - i = 0 \sum C - 1 [P (i ∣ t)]^{2}$

Where $C$ is the number of classes. Gini measures the probability that two randomly chosen records from the node have different class labels. Minimum = 0 (all same class), maximum = $1 - 1/ C$ (uniform distribution).

Gini values for binary classification (example node with 6 records):

Distribution (C0, C1)	Gini	Interpretation
(0, 6)	$1 - [0^{2} + 1^{2}] = 0$	Pure
(1, 5)	$1 - [(1/6)^{2} + (5/6)^{2}] = 1 - 26/36 \approx 0.278$	Low impurity
(3, 3)	$1 - [(3/6)^{2} + (3/6)^{2}] = 1 - 18/36 = 0.5$	Maximum impurity (binary)

For binary classification, the maximum Gini is 0.5. For C classes, the maximum is $1 - 1/ C$ .

8.5.4 Entropy

$Entropy (t) = - i = 0 \sum C - 1 P (i ∣ t) lo g_{2} P (i ∣ t)$

With the convention $0 \cdot lo g_{2} 0 = 0$ .

Why the negative sign? $P (i ∣ t)$ is a fraction in $[0, 1]$ , and $lo g_{2}$ of a fraction is negative. The leading minus makes entropy positive.

Why log base 2? Information is measured in bits. With $n$ bits, you can represent $2^{n}$ states. If there are $S$ possible states, the information is $lo g_{2} S$ bits. Base-2 log converts exponential growth of states into additive bits: $1024 \times 1024$ states → $lo g_{2} 1024 + lo g_{2} 1024 = 10 + 10 = 20$ bits. This additive property makes calculations tractable.

Entropy values for binary classification:

Distribution (C0, C1)	Entropy	Interpretation
(0, 6)	0	Pure
(1, 5)	$- [(1/6) lo g_{2} (1/6) + (5/6) lo g_{2} (5/6)] \approx 0.650$	Low impurity
(3, 3)	1	Maximum impurity (binary)

Multiclass maximum entropy: The maximum is $lo g_{2} C$ :

2 classes → max = 1
4 classes → max = 2
8 classes → max = 3
16 classes → max = 4

Entropy can exceed 1 for multi-class problems. The upper bound grows logarithmically with the number of classes.

8.5.5 Misclassification Error

$Error (t) = 1 - i max P (i ∣ t)$

The fraction of records that do not belong to the majority class. Simple and intuitive. However, rarely used for tree growth because it is less sensitive to changes in class distribution than Gini or entropy. it only cares about the majority class, ignoring the distribution of the minority classes.

8.5.6 Worked Example — All Three Measures on One Node

Node with 10 records: 6 cats, 3 dogs, 1 bird. $C = 3$ classes.

$P (cat) = 0.6, P (dog) = 0.3, P (bird) = 0.1$

Gini: $Gini = 1 - [0. 6^{2} + 0. 3^{2} + 0. 1^{2}] = 1 - [0.36 + 0.09 + 0.01] = 1 - 0.46 = 0.54$

Entropy: $Entropy = - [0.6 lo g_{2} 0.6 + 0.3 lo g_{2} 0.3 + 0.1 lo g_{2} 0.1] \approx - [0.6 \times (- 0.737) + 0.3 \times (- 1.737) + 0.1 \times (- 3.322)] \approx - [- 0.442 - 0.521 - 0.332] = 1.295$

Misclassification Error: $Error = 1 - 0.6 = 0.4$

Sense-check: For 3 classes, max Gini = $1 - 1/3 \approx 0.667$ and max entropy = $lo g_{2} 3 \approx 1.585$ . Our values (0.54, 1.295) are below the maxima but above zero. consistent with a node that is somewhat impure but tilted toward one class.

8.5.7 Comparison of Measures (Binary Classification)

For a node with probability $p$ of the positive class (x-axis: 0 to 1):

All three measures are 0 at $p = 0$ and $p = 1$ (pure nodes).
All three peak at $p = 0.5$ : Gini = 0.5, Entropy = 1, Error = 0.5.
Entropy has the steepest curve near the edges. it penalizes impurity more aggressively than Gini.
Misclassification error is piecewise linear. it only changes when the majority class changes, making it insensitive to distribution changes within the same majority.

Takeaway: Gini and entropy are concave functions that reward purer children more strongly. Error is linear and less discriminating. which is why it's rarely used for tree growth, though it's perfectly fine for final evaluation.

8.5.8 Assumptions & Scope

Scope: What impurity measures assume.

Class labels are discrete. For continuous targets, impurity is measured by variance or MSE (regression trees. section 14).
The empirical proportions $P (i ∣ t)$ are reliable estimates of the true class probabilities. With very few records in a node, these proportions are noisy.
Entropy uses the convention $0 lo g_{2} 0 = 0$ . Without this, entropy would be undefined for pure nodes. This is a limit: $lim_{p \to 0^{+}} p lo g_{2} p = 0$ .

When Gini and entropy disagree. They usually agree on the best split. However, not always. Gini tends to favor splits that isolate the largest class. entropy tends to favor splits that produce balanced child distributions. This difference is subtle and emerges in practice. see section 8 for a worked example where they might diverge.

8.5.9 Visual Intuition

Plot fraction of positive class $p$ on the x-axis (0 to 1), impurity on the y-axis.

Entropy (steepest): rises sharply from 0 at the edges, forms a tall arch peaking at (0.5, 1.0).
Gini (middle): same arch shape but flatter. peaks at (0.5, 0.5).
Misclassification error (flattest): linear rise from 0 to 0.5 at the center, then linear fall. Forms a triangle, not an arch.

All three curves are symmetric around $p = 0.5$ . The key difference is sensitivity: entropy reacts strongly to small deviations from purity. Gini reacts moderately. error barely reacts until the majority class actually changes.

Takeaway: Entropy is the most "concave". it gives the biggest reward for making a node purer. This is why ID3/C4.5 use it for splitting, even though Gini is computationally cheaper.

8.5.10 Pitfalls

"Gini ranges from 0 to 1." For binary classification, it ranges from 0 to 0.5. For C classes, it ranges from 0 to $1 - 1/ C$ . It never reaches 1.
"Entropy can't exceed 1." It can. For C classes, max entropy = $lo g_{2} C$ . A 16-class problem has max entropy = 4.
"Gini is always worse than entropy." Neither is universally better. They prioritize different splits. scikit-learn defaults to Gini for speed. However, the accuracy difference is usually negligible.
Using misclassification error for tree growth. Don't. It's fine for measuring final accuracy but too insensitive to guide which attribute to split on. it can't distinguish between two candidate splits that both preserve the same majority class.

8.5.11 Student Q&A

Q: Can Gini index be negative? A: No. Since $P (i ∣ t)$ is always between 0 and 1. the sum of squares is at most 1, Gini is always between 0 and $1 - 1/ C$ . never negative.

Q: What is misclassification error conceptually? A: It is the fraction of records you'd get wrong if you always predicted the majority class at that node. A node with 60% class A and 40% class B has error = 0.4. you'd be wrong 40% of the time. This is the simplest impurity measure to explain but the least useful for actually building the tree.

8.5.12 Recap & Bridge

Three impurity measures, one job: put a number on "how mixed is this node?" Gini (CART's choice) is fast. Entropy (ID3/C4.5's choice) is theoretically grounded. Error is too crude for tree-building. Now that we can measure impurity, we can measure how much a split reduces it. that's Information Gain.

8.5.13 Real-World & Domain Connection

The Gini index originally comes from economics. it measures income inequality in a population (the Gini coefficient). A Gini of 0 means perfect equality (everyone has the same income). a Gini of 1 means perfect inequality (one person has all the income). CART borrowed this concept because "class inequality" in a node is the same idea: a pure node has perfect class inequality (one class has everything), a 50-50 node has perfect class equality. The same math that measures wealth distribution measures classification purity.

8.6. Information Gain — Choosing the Best Split

Hook. You're at a fork in the road. Left path: you know the terrain is 50% swamp, 50% solid ground. still uncertain. Right path: 90% solid, 10% swamp. much clearer. Which path gives you more information about what you'll step on next? Information gain measures exactly this: how much cleaner is the view after the split compared to before?

8.6.1 Intuition

Everyday analogy — Filtering job applicants. You have a pile of 100 résumés: 60 good, 40 bad. That's your parent node. somewhat impure. Now you filter by "has a college degree."

With degree (70 applicants): 55 good, 15 bad. fairly pure.
Without degree (30 applicants): 5 good, 25 bad. also fairly pure. However, in the opposite direction.

Before the filter, you had a mixed pile. After the filter, each pile is more homogeneous. The reduction in impurity. how much cleaner each pile is, weighted by its size. is the information gain. A filter that separates good from bad gives high gain. A filter that leaves both piles equally mixed gives zero gain.

Key insight: you don't just want pure children. you want pure children that are large enough to matter. A split that isolates one pure record in a child of size 1 contributes almost nothing to the weighted average. That's why the weighting by child size is essential.

8.6.2 Formal Definition

Information gain measures how much a split reduces impurity. The goal is to maximize information gain. choosing the attribute that produces the purest children relative to the parent.

Formula:

$Gain = Impurity (parent) - Impurity (children)$

Where the collective impurity of children is the weighted average (each child's impurity weighted by its proportion of the parent's records):

$Impurity (children) = j = 1 \sum k \frac{n _{j}}{n} \times Impurity (child_{j})$

$k$ = number of child nodes (partitions)
$n_{j}$ = number of records at child $j$
$n$ = total number of records at the parent node

When entropy is used as the impurity measure, the resulting Gain is called Information Gain (denoted $Δ_{info}$ in Tan, or $Gain (S, A)$ in Mitchell). When Gini is used, it's called Gini Gain.

Standard form (from Mitchell §3.4.1.2, Tan §4.3.4):

$Δ = I (parent) - j = 1 \sum k \frac{N ( v _{j} )}{N} \cdot I (v_{j})$

This is equivalent to the lecture's notation. the lecture writes $\frac{n _{j}}{n}$ for the weight and $Impurity (child_{j})$ for $I (v_{j})$ .

8.6.3 Procedure

Step-by-step:

Compute the impurity of the parent node (before splitting).
For each candidate attribute, compute the weighted average impurity of the children after splitting.
Compute Gain = Impurity(parent) − Impurity(children).
Choose the attribute that maximizes Gain.

Equivalence: "Maximizing information gain" is the same as "minimizing the weighted average impurity of the children," because Impurity(parent) is the same constant for all candidate attributes being compared at that node.

8.6.4 Worked Mini-Example — Computing Gain

Parent node: 10 records — 6 class A, 4 class B. $Gini (parent) = 1 - [(0.6)^{2} + (0.4)^{2}] = 1 - [0.36 + 0.16] = 0.48$

Candidate split on Attribute X:

Child 1 (X = yes): 4 records — 3 A, 1 B. Gini = $1 - [(0.75)^{2} + (0.25)^{2}] = 0.375$
Child 2 (X = no): 6 records — 3 A, 3 B. Gini = $1 - [(0.5)^{2} + (0.5)^{2}] = 0.5$

$Weighted Gini = \frac{4}{10} \times 0.375 + \frac{6}{10} \times 0.5 = 0.15 + 0.30 = 0.45$

$Gini Gain = 0.48 - 0.45 = 0.03$

Candidate split on Attribute Y:

Child 1 (Y = yes): 5 records — 5 A, 0 B. Gini = 0
Child 2 (Y = no): 5 records — 1 A, 4 B. Gini = $1 - [(0.2)^{2} + (0.8)^{2}] = 0.32$

$Weighted Gini = \frac{5}{10} \times 0 + \frac{5}{10} \times 0.32 = 0.16$

$Gini Gain = 0.48 - 0.16 = 0.32$

Attribute Y wins (Gain 0.32 vs 0.03). Y produces much purer children.

Sense-check: Y isolates all class A records in one child. a nearly perfect split. X barely moves the needle. The gain numbers reflect this: Y's gain is 10× larger.

8.6.5 Assumptions & Scope

Scope: When information gain works.

The impurity measure used (Gini or entropy) must be strictly concave. otherwise gain can be zero even for useful splits. Both Gini and entropy satisfy this.
The parent impurity is the same for all candidate attributes at a given node. So only the weighted child impurity matters for ranking. This means you can skip computing Gain and just compare weighted impurities directly. lower weighted impurity = better split.
Gain is always non-negative for the best attribute. If all candidate splits produce negative gain (increase impurity), the node should become a leaf.

8.6.6 Visual Intuition

Picture a bar chart comparing impurity before and after splitting:

Left bar (tall): Impurity(parent). the mixed-ness before the split. This is the same height for all candidate attributes.
Right bars (shorter): Weighted Impurity(children) for each candidate attribute. Each is a stack of colored segments. one per child, height proportional to $\frac{n _{j}}{n} \times Impurity (child_{j})$ .

The attribute with the biggest drop from left bar to right bar has the highest Gain. The drop represents how much uncertainty the attribute eliminated.

Takeaway: Information gain is the height of the impurity "waterfall" from parent to children. The taller the waterfall, the better the split.

8.6.7 Pitfalls

"Negative gain means the split is mathematically impossible." It's possible. it means the split made things worse. That branch should be ended. But with proper impurity measures, the best attribute at each node will always have non-negative gain.
"Higher gain is always better, even if the tree becomes enormous." Information gain is biased toward attributes with many distinct values (like Customer ID). A pure but useless split gets maximum gain. See section 9 — Gain Ratio fixes this.
Forgetting to weight by child size. The raw average of child impurities (without weighting) would treat a child with 1 record the same as a child with 1000 records. Always use the weighted average.

8.6.8 Recap & Bridge

Information gain = parent impurity minus weighted-average child impurity. Pick the attribute with the biggest drop. Simple formula. However, it has a blind spot: it loves attributes with too many values. Next: the full Golf dataset worked example, then Gain Ratio to fix the blind spot.

8.6.9 Real-World & Domain Connection

Information gain is the theoretical backbone of decision tree learning. However, it also appears outside of trees. In feature selection for any classifier, mutual information (the information-theoretic generalization of information gain) ranks features by how much they reduce uncertainty about the target. The same math that picks the root node of a decision tree also picks which columns to keep in a high-dimensional genomics dataset. The concept extends to information bottleneck methods in deep learning and to entropy-based discretization in data preprocessing.

8.7. Full Worked Example — Golf Dataset with ID3 (Entropy)

Hook. Here is the exam question: you're given 14 days of golfing data — Outlook, Temperature, Humidity, Wind. whether golf was played. Build the entire decision tree by hand, computing every entropy and information gain. This is the canonical worked example from Quinlan (1986) that appears in Mitchell's textbook and in countless ML exams. You will be asked to reproduce this.

8.7.1 The Dataset

#	Outlook	Temperature	Humidity	Windy	Play Golf
1	Sunny	Hot	High	False	No
2	Sunny	Hot	High	True	No
3	Overcast	Hot	High	False	Yes
4	Rainy	Mild	High	False	Yes
5	Rainy	Cool	Normal	False	Yes
6	Rainy	Cool	Normal	True	No
7	Overcast	Cool	Normal	True	Yes
8	Sunny	Mild	High	False	No
9	Sunny	Cool	Normal	False	Yes
10	Rainy	Mild	Normal	False	Yes
11	Sunny	Mild	Normal	True	Yes
12	Overcast	Mild	High	True	Yes
13	Overcast	Hot	Normal	False	Yes
14	Rainy	Mild	High	True	No

14 records. Target: Play Golf — 9 Yes, 5 No.

8.7.2 Step 1 — Entropy of the Parent

$H (PlayGolf) = - \frac{9}{14} lo g_{2} \frac{9}{14} - \frac{5}{14} lo g_{2} \frac{5}{14}$

Breaking it down: $\frac{9}{14} \frac{5}{14} \approx 0.643, \approx 0.357, \approx 0.410 + 0.530 = 0.940 lo g_{2} (0.643) lo g_{2} (0.357) \approx - 0.637 \approx - 1.485 [4 pt] H = - 0.643 \times (- 0.637) - 0.357 \times (- 1.485)$

This matches the standard value from Mitchell (1997, §3.4.2): Entropy([9+,5−]) = 0.940.

8.7.3 Step 2 — Evaluate Attribute "Outlook"

Outlook has three values: Sunny (5 records), Overcast (4 records), Rainy (5 records).

Sunny (3 Yes, 2 No): $H (Sunny) = - \frac{3}{5} lo g_{2} \frac{3}{5} - \frac{2}{5} lo g_{2} \frac{2}{5} \approx 0.971$

Overcast (4 Yes, 0 No): All one class → $H (Overcast) = 0$ (pure).

Rainy (2 Yes, 3 No): $H (Rainy) = - \frac{2}{5} lo g_{2} \frac{2}{5} - \frac{3}{5} lo g_{2} \frac{3}{5} \approx 0.971$

Weighted entropy: $H (PlayGolf ∣ Outlook) = \frac{5}{14} \times 0.971 + \frac{4}{14} \times 0 + \frac{5}{14} \times 0.971 \approx 0.694$

Information Gain: $Gain (Outlook) = 0.940 - 0.694 = 0.246$

8.7.4 Step 3 — Evaluate Attribute "Temperature"

Temperature: Hot (4), Mild (6), Cool (4).

Hot (2 Yes, 2 No): $H (Hot) = 1.0$ (50-50, max entropy)

Mild (4 Yes, 2 No): $H (Mild) = - \frac{4}{6} lo g_{2} \frac{4}{6} - \frac{2}{6} lo g_{2} \frac{2}{6} \approx 0.918$

Cool (3 Yes, 1 No): $H (Cool) = - \frac{3}{4} lo g_{2} \frac{3}{4} - \frac{1}{4} lo g_{2} \frac{1}{4} \approx 0.811$

Weighted entropy: $H (PlayGolf ∣ Temperature) = \frac{4}{14} \times 1.0 + \frac{6}{14} \times 0.918 + \frac{4}{14} \times 0.811 \approx 0.911$

Information Gain: $Gain (Temperature) = 0.940 - 0.911 = 0.029$

8.7.5 Step 4 — Evaluate Attribute "Humidity"

Humidity: High (7), Normal (7).

High (3 Yes, 4 No): $H (High) = - \frac{3}{7} lo g_{2} \frac{3}{7} - \frac{4}{7} lo g_{2} \frac{4}{7} \approx 0.985$

Normal (6 Yes, 1 No): $H (Normal) = - \frac{6}{7} lo g_{2} \frac{6}{7} - \frac{1}{7} lo g_{2} \frac{1}{7} \approx 0.592$

Weighted entropy: $H (PlayGolf ∣ Humidity) = \frac{7}{14} \times 0.985 + \frac{7}{14} \times 0.592 \approx 0.788$

Information Gain: $Gain (Humidity) = 0.940 - 0.788 = 0.152$

Note: Mitchell (1997) reports this as 0.151. the difference of 0.001 is rounding.

8.7.6 Step 5 — Evaluate Attribute "Windy"

Windy: False (8), True (6).

False (6 Yes, 2 No): $H (False) = - \frac{6}{8} lo g_{2} \frac{6}{8} - \frac{2}{8} lo g_{2} \frac{2}{8} \approx 0.811$

True (3 Yes, 3 No): $H (True) = 1.0$

Weighted entropy: $H (PlayGolf ∣ Windy) = \frac{8}{14} \times 0.811 + \frac{6}{14} \times 1.0 \approx 0.892$

Information Gain: $Gain (Windy) = 0.940 - 0.892 = 0.048$

8.7.7 Step 6 — Choose the Root Node

Attribute	Information Gain
Outlook	0.246
Humidity	0.152
Windy	0.048
Temperature	0.029

Outlook has the highest information gain → chosen as the root node.

8.7.8 Step 7 — Build Level 1

                    [Outlook?]
                   /    |     \
              Sunny  Overcast  Rainy

Overcast: Entropy = 0 (4 Yes, 0 No). → Leaf: YES. Done.
Sunny: 5 records (3 Yes, 2 No). impure, must split further.
Rainy: 5 records (2 Yes, 3 No). impure, must split further.

8.7.9 Step 8 — Split the "Sunny" Branch

Filter to the 5 Sunny records only. Parent entropy:

H (Sunny) = - \frac{3}{5} lo g_{2} \frac{3}{5} - \frac{2}{5} lo g_{2} \frac{2}{5} \approx 0.971

Evaluate Temperature, Humidity, and Windy on this subset:

Windy = False: 3 records, all Yes → $H = 0$
Windy = True: 2 records, all No → $H = 0$

Weighted entropy =

\frac{3}{5} \times 0 + \frac{2}{5} \times 0 = 0

Gain = 0.971 − 0 = 0.971 → Windy chosen. Both children are pure → both become leaves: YES and NO.

8.7.10 Step 9 — Split the "Rainy" Branch

Filter to the 5 Rainy records only.

Humidity = High: 3 records, all No → $H = 0$
Humidity = Normal: 2 records, all Yes → $H = 0$

Weighted entropy = 0. Gain = high → Humidity chosen. Both children pure → leaves: NO (High) and YES (Normal).

8.7.11 Final Decision Tree

                    [Outlook?]
                   /    |     \
              Sunny  Overcast  Rainy
                |       |        |
             [Windy?]  YES    [Humidity?]
             /     \           /       \
         False   True       High     Normal
           |       |         |         |
          YES     NO        NO        YES

Temperature was never used. The tree achieved perfect classification using only Outlook, Windy, and Humidity. The algorithm naturally discards uninformative attributes.

8.7.12 Visual Intuition

Imagine the 14 data points as colored dots in a 4-dimensional attribute space. The first split (Outlook) divides them into three groups. One group (Overcast) is already all green (Yes). that branch stops. The other two groups (Sunny, Rainy) are mixed red and green. The second-level splits (Windy for Sunny, Humidity for Rainy) cleanly separate the remaining mixed groups. The final partition is:

Path 1: Outlook=Overcast → Yes
Path 2: Outlook=Sunny ∧ Windy=False → Yes
Path 3: Outlook=Sunny ∧ Windy=True → No
Path 4: Outlook=Rainy ∧ Humidity=Normal → Yes
Path 5: Outlook=Rainy ∧ Humidity=High → No

These five paths form a disjunction of conjunctions. the logical form of any decision tree.

8.7.13 Pitfalls

Arithmetic errors in log computation. The most common exam mistake: forgetting that $lo g_{2} (0.5) = - 1$ (not 0, not 1), or using natural log instead of $lo g_{2}$ . Double-check: $lo g_{2} (0.5) = - 1$ , $lo g_{2} (0.25) = - 2$ , $lo g_{2} (0.125) = - 3$ .
Forgetting the negative sign. The formula is $- \sum p lo g p$ . Without the minus, you get a negative number. entropy must be ≥ 0.
Not weighting by child size. If you average child entropies without weighting, you treat a child with 2 records the same as one with 10.
"Temperature was irrelevant." Temperature was irrelevant for this dataset. For a different dataset or a different split order, it might matter. Never generalize from a single run.

8.7.14 Student Q&A

Q: Is it possible for entropy to increase when splitting? A: Yes, it can happen. the split creates more confusion. That branch should be ended (another stopping criterion). However, with proper impurity measures, the best attribute at each node always has non-negative gain. If all candidates have negative gain, the node becomes a leaf. Q: For the exam, how many levels will we be asked to compute? A: The professor indicated maximum 2 levels (course-specific. confirm with your own instructor). The computation is recursive. So once you show the method at the first split, the second level follows the same process. Q: Will different branches use different attributes? A: Yes. they typically do. In this example, Sunny → Windy while Rainy → Humidity. Each branch is an independent subproblem. There is no requirement that branches use the same attribute.

8.7.15 Exam Guidance

Exam note: Decision tree construction by hand is a common exam question. You'll be given a small dataset (10–20 records, 3–5 attributes) and asked to compute the root node using entropy and information gain, possibly one more level. Know: (1) the entropy formula, (2) how to compute weighted average, (3) how to subtract from parent entropy to get gain. Bring a calculator that can compute

lo g_{2}

. Memorize key

lo g_{2}

values:

lo g_{2} (0.5) = - 1

lo g_{2} (0.25) = - 2

lo g_{2} (1) = 0

lo g_{2} (0) = - \infty

(but

0 lo g_{2} 0 = 0

by convention).

8.7.16 Recap & Bridge

The Golf dataset ID3 walkthrough: compute parent entropy → compute weighted child entropy for each attribute → pick max gain → recurse. Outlook won the root with gain 0.246. The final tree uses only 3 of 4 attributes. Next: the same dataset. However, using Gini instead of entropy. and a warning that the trees might differ.

8.7.17 Real-World & Domain Connection

This exact dataset. the "Play Tennis" / "Golf" example. was introduced by Ross Quinlan in 1986 as the motivating example for ID3. It has since become the "Hello World" of decision tree learning, appearing in Mitchell (1997), Tan et al. (2018). virtually every ML textbook. The dataset is small enough to compute by hand but rich enough to illustrate every major concept: entropy, information gain, multi-way splits, recursive partitioning. the fact that some attributes end up unused. If you understand every step of this example, you understand decision tree learning.

8.8. Worked Example — Golf Dataset with Gini Index

Hook. Same dataset, different yardstick. If we swap entropy for Gini, does the tree change? For the Golf dataset, you get the same root. but that is NOT guaranteed. The professor warns: "It comes as a shocking reveal when you implement it. sometimes Gini picks a different attribute." Let's compute every Gini value and see why.

8.8.1 Intuition

The process is identical to the entropy walkthrough. just swap the formula. Instead of $- \sum p lo g_{2} p$ , use $1 - \sum p^{2}$ . The attribute with the highest Gini Gain (parent Gini minus weighted child Gini) wins. The ranking may differ from entropy's ranking. and when it does, the tree changes.

8.8.2 Gini Formula

$Gini (t) = 1 - i = 0 \sum C - 1 [P (i ∣ t)]^{2}$

For binary classification, Gini ranges from 0 (pure) to 0.5 (50-50). Gain is computed the same way as information gain:

$Gini Gain = Gini (parent) - j \sum \frac{n _{j}}{n} \times Gini (child_{j})$

8.8.3 Step 1 — Gini of the Parent

$Gini (PlayGolf) = 1 - [(\frac{9}{14})^{2} + (\frac{5}{14})^{2}] = 1 - [\frac{81}{196} + \frac{25}{196}] = 1 - \frac{106}{196} \approx 0.459$

Compare: entropy was 0.940. Gini is roughly half because its maximum for binary is 0.5, while entropy's maximum is 1.0.

8.8.4 Step 2 — Evaluate "Outlook" with Gini

Sunny (3 Yes, 2 No): $Gini (Sunny) = 1 - [(\frac{3}{5})^{2} + (\frac{2}{5})^{2}] = 1 - [\frac{9}{25} + \frac{4}{25}] = 1 - 0.52 = 0.48$

Overcast (4 Yes, 0 No): $Gini (Overcast) = 1 - [1^{2} + 0^{2}] = 0$

Rainy (2 Yes, 3 No): $Gini (Rainy) = 1 - [(\frac{2}{5})^{2} + (\frac{3}{5})^{2}] = 1 - [\frac{4}{25} + \frac{9}{25}] = 1 - 0.52 = 0.48$

Weighted Gini: $\frac{5}{14} \times 0.48 + \frac{4}{14} \times 0 + \frac{5}{14} \times 0.48 \approx 0.343$

Gini Gain: $Gain (Outlook) = 0.459 - 0.343 = 0.116$

8.8.5 Step 3 — Evaluate "Temperature" with Gini

Hot (2 Yes, 2 No): $Gini (Hot) = 1 - [(0.5)^{2} + (0.5)^{2}] = 1 - 0.5 = 0.5$

Mild (4 Yes, 2 No): $Gini (Mild) = 1 - [(\frac{4}{6})^{2} + (\frac{2}{6})^{2}] = 1 - [\frac{16}{36} + \frac{4}{36}] = 1 - \frac{20}{36} \approx 0.444$

Cool (3 Yes, 1 No): $Gini (Cool) = 1 - [(\frac{3}{4})^{2} + (\frac{1}{4})^{2}] = 1 - [\frac{9}{16} + \frac{1}{16}] = 1 - 0.625 = 0.375$

Weighted Gini: $\frac{4}{14} \times 0.5 + \frac{6}{14} \times 0.444 + \frac{4}{14} \times 0.375 \approx 0.440$

Gini Gain: $Gain (Temperature) = 0.459 - 0.440 = 0.019$

8.8.6 Step 4 — Evaluate "Humidity" with Gini

High (3 Yes, 4 No): $Gini (High) = 1 - [(\frac{3}{7})^{2} + (\frac{4}{7})^{2}] = 1 - [\frac{9}{49} + \frac{16}{49}] = 1 - \frac{25}{49} \approx 0.490$

Normal (6 Yes, 1 No): $Gini (Normal) = 1 - [(\frac{6}{7})^{2} + (\frac{1}{7})^{2}] = 1 - [\frac{36}{49} + \frac{1}{49}] = 1 - \frac{37}{49} \approx 0.245$

Weighted Gini: $\frac{7}{14} \times 0.490 + \frac{7}{14} \times 0.245 \approx 0.368$

Gini Gain: $Gain (Humidity) = 0.459 - 0.368 = 0.091$

8.8.7 Step 5 — Evaluate "Windy" with Gini

False (6 Yes, 2 No): $Gini (False) = 1 - [(\frac{6}{8})^{2} + (\frac{2}{8})^{2}] = 1 - [\frac{36}{64} + \frac{4}{64}] = 1 - \frac{40}{64} = 0.375$

True (3 Yes, 3 No): $Gini (True) = 1 - [(0.5)^{2} + (0.5)^{2}] = 0.5$

Weighted Gini: $\frac{8}{14} \times 0.375 + \frac{6}{14} \times 0.5 \approx 0.429$

Gini Gain: $Gain (Windy) = 0.459 - 0.429 = 0.030$

8.8.8 Step 6 — Compare and Choose

Attribute	Information Gain (Entropy)	Gini Gain
Outlook	0.246	0.116
Humidity	0.152	0.091
Windy	0.048	0.030
Temperature	0.029	0.019

Ranking is the same for this dataset. Outlook wins under both measures. But the relative margins differ — Gini compresses the differences (all gains smaller because Gini's range is 0–0.5 vs entropy's 0–1). On other datasets, the ranking can flip, giving a different root node.

8.8.9 Key Caveat

"The Gini tree coincidentally looks identical to the entropy tree for this dataset. This is NOT always the case." — Professor

The professor explicitly warns: when you implement decision trees in code, you may be surprised to find Gini and entropy selecting different attributes. This is normal. Neither is "wrong". they optimize slightly different objectives. Gini tends to isolate the largest class. entropy balances all classes. The practical accuracy difference is usually negligible. However, the trees can look different.

8.8.10 Comparison — Entropy vs Gini on the Same Data

Property	Entropy	Gini
Parent value (Golf)	0.940	0.459
Maximum (binary)	1.0	0.5
Shape	Steep near edges, flat near center	Gentler curve
Computational cost	Slower (log)	Faster (square only)
Sensitivity to impurity	High	Moderate
Default in scikit-learn	`criterion='entropy'`	`criterion='gini'` (default)

8.8.11 Recap & Bridge

Gini Gain follows the same template as Information Gain. just use $1 - \sum p^{2}$ instead of $- \sum p lo g_{2} p$ . For the Golf dataset, both chose Outlook. But the professor warns: they can disagree. when they do, neither is "wrong." Next: the Customer ID problem. why both measures need a penalty term — Gain Ratio.

8.8.12 Real-World & Domain Connection

In production ML, Gini dominates because of scikit-learn's default. Most practitioners never switch to entropy because the accuracy difference is usually within noise. The real choice that matters is not Gini vs entropy but tree depth, pruning strategy. ensemble methods (Random Forest, XGBoost) that build on top of these single trees. Knowing both measures matters for exams and for understanding what your library is doing under the hood.

8.9. Gain Ratio — Handling the Customer ID Problem

Hook. You discover an attribute that splits your data into perfectly pure children. Information gain is at its theoretical maximum. You've found the perfect split! Except the attribute is "Customer ID". unique for every record. Your tree has achieved 100% training accuracy and 0% generalization ability. This is the dirty secret of information gain: it loves attributes with too many values.

8.9.1 Intuition

Everyday analogy — Sorting students by name vs by grade. You want to predict who passes an exam. If you split by student name (unique to each person), each leaf has exactly one student. perfectly pure! But the split is useless for predicting new students. If you split by "hours studied" (a few categories), the leaves are impure but the pattern generalizes.

Information gain rewards purity above all else. It cannot distinguish between a useful split (Car Type) and a memorization split (Customer ID). Gain Ratio fixes this by asking: "How many splits are you making. how evenly are they distributed?" It penalizes attributes that slice the data into too many thin pieces.

Where the analogy breaks: in the classroom, you know intuitively that "name" is useless. The algorithm has no common sense. it only sees purity numbers. Gain Ratio is the mathematical patch for this blindness.

8.9.2 Formal Definition

Gain Ratio penalizes attributes that create many splits by dividing Information Gain by the entropy of the split itself:

$Gain Ratio = \frac{Information Gain}{Split Information}$

Where Split Information measures the entropy of the attribute values (NOT the class labels. This is a different entropy):

$Split Information = - j = 1 \sum k \frac{n _{j}}{n} lo g_{2} \frac{n _{j}}{n}$

$k$ = number of distinct values (branches) for that attribute
$n_{j}$ = number of records with value $j$
$n$ = total records

Standard form (from Mitchell §3.7.2, Tan §4.3.4):

$GainRatio (S, A) = \frac{Gain ( S , A )}{SplitInformation ( S , A )}$

This is exactly the lecture's formula. Mitchell defines SplitInformation as the entropy of S with respect to the values of attribute A. distinct from the entropy of S with respect to the target.

8.9.3 Why It Works

Customer ID (20 distinct values, one per record): Split Information = $lo g_{2} 20 \approx 4.32$ (very high). Even with maximum Information Gain of 1.0, Gain Ratio ≈ $1/4.32 \approx 0.23$ . low.
Gender (2 values, roughly equal): Split Information ≈ 1.0. Even with modest Information Gain, Gain Ratio stays reasonable.
Car Type (3 values, uneven): Split Information is moderate. With good Information Gain, Gain Ratio emerges as the winner.

The denominator acts as a "complexity penalty". the more branches an attribute creates, the larger the denominator, the lower the Gain Ratio. An attribute must earn its branches by providing genuinely better purity.

8.9.4 Worked Example — Computing Gain Ratio

Dataset: 20 records, 10 class C0, 10 class C1. Attributes: Gender, Car Type, Customer ID.

Customer ID:

Each ID maps to exactly one record → all children pure.
Information Gain = $1.0 - 0 = 1.0$ (maximum).
Split Information = $- \sum_{j = 1}^{20} \frac{1}{20} lo g_{2} \frac{1}{20} = - 20 \times \frac{1}{20} \times (- lo g_{2} 20) = lo g_{2} 20 \approx 4.32$ .
Gain Ratio = $1.0/4.32 \approx 0.23$ .

Gender:

Suppose Gender produces Gain ≈ 0.03.
Split Information = $- [\frac{10}{20} lo g_{2} \frac{10}{20} + \frac{10}{20} lo g_{2} \frac{10}{20}] = - [0.5 \times (- 1) + 0.5 \times (- 1)] = 1.0$ .
Gain Ratio = $0.03/1.0 = 0.03$ .

Car Type (Family: 4, Sports: 8, Luxury: 8):

Suppose Car Type produces Gain ≈ 0.52.
Split Information = $- [\frac{4}{20} lo g_{2} \frac{4}{20} + \frac{8}{20} lo g_{2} \frac{8}{20} + \frac{8}{20} lo g_{2} \frac{8}{20}]$

= $- [0.2 \times (- 2.322) + 0.4 \times (- 1.322) + 0.4 \times (- 1.322)]$ = $- [- 0.464 - 0.529 - 0.529] \approx 1.522$ .

Gain Ratio = $0.52/1.522 \approx 0.34$ .

Winner: Car Type with Gain Ratio 0.34. Customer ID (Gain Ratio 0.23), despite having the purest split, ranks below Car Type.

Sense-check: Customer ID had the best Information Gain (1.0) but the worst Gain Ratio (0.23). The penalty worked. the useless attribute was demoted. Car Type. This creates 3 meaningful groups, won.

8.9.5 Practical Handling of Zero Denominator

Edge case: When Split Information is zero or very small (all records have the same value for that attribute), Gain Ratio becomes undefined or enormous. The standard fix (Quinlan 1986): first filter attributes by computing Information Gain, keep only those with above-average Gain, then apply Gain Ratio to the survivors. This prevents attributes with near-zero Split Information from winning by a numerical accident.

8.9.6 Assumptions & Scope

Scope: When Gain Ratio helps. Gain Ratio is most useful when:

The dataset contains attributes with widely varying numbers of distinct values (e.g., zip code vs gender).
You are using multi-way splits (ID3/C4.5), where the bias toward many-valued attributes is strongest.
Binary-split algorithms (CART) are less affected because they always create exactly 2 branches. So the bias is muted. but not eliminated (binary splits of many-valued nominal attributes still have many candidate groupings to try).

When it doesn't help. If all attributes have roughly the same number of values, Gain Ratio and Information Gain will produce identical rankings.

8.9.7 Student Q&A

Q: Why can't we use Customer ID when it gives the purest split? A: Customer ID is unique per record. Splitting on it means memorizing individual training records rather than learning general patterns. The tree would have zero ability to classify new, unseen customers. the definition of overfitting. Several students asked this. it's a common trap because the math seems to reward Customer ID.

Q: What if the dataset has very few attributes? A: The method works the same way. Calculate Gain Ratio for each attribute and pick the highest. With few attributes, there's less risk of a Customer-ID-like trap. However, Gain Ratio is still good practice. it costs nothing to compute and guards against accidentally overfitting on a high-cardinality attribute.

8.9.8 Recap & Bridge

Information Gain loves attributes with many values. Gain Ratio fixes this by dividing by the entropy of the split itself. penalizing attributes that create too many branches. It is the standard splitting criterion in C4.5. Next: how to handle continuous attributes. This have infinitely many possible split points.

8.9.9 Real-World & Domain Connection

The Gain Ratio problem appears everywhere in ML, not just in decision trees. In feature selection, mutual information (the generalization of information gain) is biased toward high-cardinality features. The fix — normalized mutual information. is the same idea as Gain Ratio. In database indexing, the same math determines which columns to index: a column with unique values (like a primary key) has high "split information" and makes an excellent index. However, a poor grouping criterion. The tension between purity and cardinality is a fundamental tradeoff in any discretization or bucketing problem.

8.10. Continuous-Valued Attributes — Threshold Determination

Hook. An attribute like "annual income" can take thousands of different values. You can't create one branch per value. that's the Customer ID problem again. Instead, you pick a single number. a threshold. and ask: "Is the value above or below this line?" But which number? Testing every possible threshold naively would be $O (n^{2})$ . There's a smarter way.

8.10.1 Intuition

Everyday analogy — Setting a speed limit. You have accident data for a road: at each speed, whether an accident occurred. You want one number. the speed limit. that best separates "accident-prone" speeds from "safe" speeds. You could test every possible speed (60.0, 60.1, 60.2…). However, that's infinite. The insight: the optimal threshold is always between two speeds where the accident outcome changes. If 60 mph is "safe" and 61 mph is "accident," the threshold should be 60.5. You only need to test boundaries where the class label flips.

8.10.2 Algorithm — Finding the Best Threshold (CART)

This is a procedural concept. The algorithm for determining the best threshold for a continuous attribute:

Sort all values of the continuous attribute in ascending order, carrying their class labels.
Identify candidate thresholds only at positions where the class label changes between two consecutive sorted values. The candidate threshold is the midpoint (average) of those two values.
For each candidate threshold, evaluate the binary split: left = values < threshold, right = values ≥ threshold. Compute the weighted impurity (Gini or entropy) of the two resulting children.
Choose the threshold that produces the lowest weighted impurity (equivalently, highest gain).

Why only class-change boundaries? A threshold between two records with the same class label produces the same partition as the next boundary. it can never be optimal. By only testing boundaries where the class changes, the number of candidates drops from $n - 1$ to at most $C - 1$ (where $C$ is the number of classes). in practice far fewer.

From Tan §4.3.4: "This approach allows us to reduce the number of candidate split positions from 11 to 2" in their worked example.

8.10.3 Trace — Temperature Threshold Example

Sorted temperature values with class labels:

Temp	60	65	67	70	71	72	75	80	85
Class	Y	N	Y	Y	N	Y	N	N	N

Candidate thresholds (only at class-change boundaries):

60→65: Y→N → threshold = (60+65)/2 = 62.5
65→67: N→Y → threshold = (65+67)/2 = 66.0
70→71: Y→N → threshold = (70+71)/2 = 70.5
71→72: N→Y → threshold = (71+72)/2 = 71.5
72→75: Y→N → threshold = (72+75)/2 = 73.5

Only 5 candidate thresholds to test (instead of 8 midpoints between all consecutive values). For each, compute the weighted impurity. The one with the lowest Gini. in the professor's example, it produces Gini ≈ 0.3. is chosen.

Note: The lecture notes reference a threshold value of 97 in a different, larger dataset (likely the annual income example from Tan §4.3.4 where $v = 97$ was the optimal split). The principle is the same regardless of the specific number.

8.10.4 Complexity & Cost

Sorting: $O (n lo g n)$ for the attribute values.
Candidate identification: $O (n)$ . one pass through sorted values.
Evaluating each candidate: $O (n)$ if done naively → $O (n^{2})$ total. Optimization: maintain running counts of each class as you sweep through sorted values, updating Gini/entropy in $O (1)$ per candidate → $O (n lo g n)$ total (dominated by sorting).
For $d$ continuous attributes, total cost is $O (d \cdot n lo g n)$ per node.

8.10.5 Pitfalls

Testing all midpoints, not just class-change boundaries. This wastes computation. thresholds between same-class records can never be optimal for impurity-based measures.
Forgetting to sort. The threshold search requires sorted values. Using unsorted data produces meaningless splits.
"The threshold 97 is the answer for every dataset." The value 97 came from a specific example in Tan §4.3.4 (annual income). Your dataset will have its own optimal threshold. compute it, don't memorize it.

8.10.6 Recap & Bridge

For continuous attributes: sort → find class-change boundaries → test each midpoint → pick the one with lowest weighted impurity. The optimization of only testing class-change boundaries makes this efficient. Next: the full ID3 algorithm specification, tying together everything we've built.

8.10.7 Real-World & Domain Connection

Continuous attribute splitting is where decision trees show their age. Modern gradient-boosted trees (XGBoost, LightGBM) use histogram-based splitting: they bucket continuous values into 256 bins and only test bin boundaries, trading a tiny amount of precision for a massive speedup. The principle. only test boundaries where the distribution changes. is the same idea, just approximated. This is why XGBoost can handle millions of records with hundreds of features in seconds while a naive scikit-learn decision tree would take hours.

8.11. ID3 Algorithm — Formal Specification

Hook. You've computed entropy by hand. You've picked the best attribute. Now what? ID3 is the algorithm that puts it all together. a recursive, greedy, top-down procedure that builds the entire tree from data. It's the algorithm behind every decision tree you'll ever build. Here is the exact pseudocode.

8.11.1 Purpose

ID3 (Iterative Dichotomiser 3), invented by Ross Quinlan in 1986, is built on Hunt's algorithm. It uses entropy and information gain to select the best attribute at each step and performs multi-way splits (one branch per attribute value). It is the canonical decision tree learning algorithm and the basis for C4.5, its widely-used successor.

The pseudocode below is adapted from Mitchell (1997, Table 3.1), specialized for multi-class classification.

8.11.2 Inputs & Outputs

Inputs:

Examples: the set of training records at the current node.
Target_attribute: the attribute whose value is to be predicted (the class label).
Attributes: the set of remaining attributes available for splitting.

Output:

A decision tree that (attempts to) correctly classify all training examples.

8.11.3 Algorithm Steps

ID3(Examples, Target_attribute, Attributes):

1.  Create a Root node for the tree.

2.  If all Examples have the same value for Target_attribute:
        Return Root as a leaf node labeled with that value.
        (Base case: the node is pure.)

3.  If Attributes is empty:
        Return Root as a leaf node labeled with the MOST COMMON
        value of Target_attribute in Examples.
        (Base case: no more attributes to test. majority vote.)

4.  Otherwise:
    a.  Let A* be the attribute from Attributes that MAXIMIZES
        Information Gain(Examples, A).
        (The central decision. entropy and gain from sections 5-6.)

    b.  Set Root's test condition to A*.

    c.  For each possible value v_i of A*:
        i.   Add a new branch below Root for A* = v_i.
        ii.  Let Examples_{v_i} be the subset of Examples where A* = v_i.
        iii. If Examples_{v_i} is empty:
                 Attach a leaf labeled with the MOST COMMON value of
                 Target_attribute in Examples (the PARENT's examples).
                 (Edge case: a value with no training records.)
        iv.  Else:
                 Recursively call:
                 ID3(Examples_{v_i}, Target_attribute, Attributes − {A*})
                 and attach the resulting subtree below this branch.

5.  Return Root.

8.11.4 Trace — Running ID3 on the Golf Dataset

Initial call: ID3(all 14 records, PlayGolf, {Outlook, Temp, Humidity, Windy}) Iteration 1:

Step 2: Not all same class (9 Yes, 5 No) → continue.
Step 3: Attributes not empty → continue.
Step 4a: Compute Gain for all 4 attributes. Outlook wins (Gain = 0.246).
Step 4c: For each Outlook value:

Sunny (5 records): Recurse with {Temp, Humidity, Windy}.
Overcast (4 records, all Yes): Step 2 → Leaf: Yes.
Rainy (5 records): Recurse with {Temp, Humidity, Windy}.

Iteration 2 — Sunny branch: ID3(5 Sunny records, PlayGolf, {Temp, Humidity, Windy})

Step 4a: Windy wins (Gain = 0.971).
Step 4c: False → Leaf: Yes. True → Leaf: No.

Iteration 2 — Rainy branch: ID3(5 Rainy records, PlayGolf, {Temp, Humidity, Windy})

Step 4a: Humidity wins.
Step 4c: High → Leaf: No. Normal → Leaf: Yes.

All recursive calls return. Tree complete.

8.11.5 Convergence Conditions (Stopping Rules)

The algorithm ALWAYS ends because:

At each recursive call, at least one attribute is removed from Attributes (Step 4c-iv).
The attribute set is finite.
When Attributes is empty, Step 3 forces a leaf (majority vote).
When all examples agree on the target, Step 2 forces a leaf (pure node).

Edge case. empty child (Step 4c-iii): If a value

v_{i}

of A* appears in the parent's data but has zero records, the algorithm attaches a leaf labeled with the parent's majority class. This handles the case where a value is possible in theory but absent in the training data.

8.11.6 ID3 vs CART Summary

Property	ID3	CART
Split type	Multi-way (one branch per value)	Binary only (two branches)
Impurity measure	Entropy (Information Gain)	Gini (or entropy optionally)
Attribute selection	Max Information Gain	Max Gini Gain
Continuous attributes	Discretization (preprocessing)	Binary threshold (internal)
Missing values	Not handled natively	Handled via surrogate splits
Tree preference	Shorter (wider nodes)	Deeper (more levels)
scikit-learn	Not available	`DecisionTreeClassifier`

8.11.7 Pitfalls

ID3 cannot handle continuous attributes directly. Values must be discretized before training. CART handles them natively via binary thresholds.
ID3 is greedy. The choice of A* at the root is never revisited, even if a later split reveals it was suboptimal.
ID3 prefers attributes with many values. Information Gain bias. use Gain Ratio (C4.5's improvement) instead.

8.11.8 Recap & Bridge

ID3 is the recursive algorithm: check purity → pick best attribute by information gain → create branches → recurse. It's the canonical decision tree learner, later improved by C4.5 (Gain Ratio, continuous handling, pruning). Next: how to actually use decision trees in Python with scikit-learn.

8.11.9 Real-World & Domain Connection

ID3 was a breakthrough in 1986. it was one of the first algorithms that could learn symbolic rules (decision trees) from data without human guidance. Its successor, C4.5, was the most widely used ML algorithm throughout the 1990s and early 2000s, powering applications from medical diagnosis to credit scoring. While modern libraries use CART (scikit-learn) or boosted ensembles (XGBoost), ID3's architecture. recursive partitioning guided by information theory. remains the conceptual blueprint for all tree-based methods.

8.12. Decision Tree Implementation in Python (scikit-learn)

Hook. You know the theory. entropy, Gini, information gain, recursive splitting. Now: two lines of Python and you have a trained decision tree. But what actually happens when you call .fit()? And how do you read the tree that comes out?

8.12.1 Purpose

scikit-learn's DecisionTreeClassifier is an optimized CART implementation. It uses binary splits, defaults to Gini impurity. provides parameters to control tree growth and prevent overfitting. This section walks through a real medical dataset example shown in the lecture.

8.12.2 Dataset — COVID-19 Hospital Data

The professor showed a real COVID-19 dataset with these columns:

Features: gender (M/F), age (numerical), comorbidities (0/1), admit date, discharge date, remedies given (0/1), days of stay, COVID severity (numerical), COVID severity description.
Target: discharge_type — "recovered" or "expired."

This is a binary classification problem with a mix of categorical and numerical features.

8.12.3 Preprocessing Steps

Before training, the raw data must be prepared:

Label Encoding: Categorical columns are converted to numbers. sklearn.preprocessing.LabelEncoder converts gender from M/F to 1/0.
Target isolation: discharge_type is separated as the target label $y$ .
Train-Test Split: 70-30 split using train_test_split(X, y, test_size=0.3). The model trains on 70% and is evaluated on the unseen 30%.
Irrelevant columns dropped: Admit date, discharge date, and COVID severity description are removed. they either leak the target or duplicate information already in other columns.

8.12.4 Training Code

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

model = DecisionTreeClassifier(criterion='gini', max_depth=5)
model.fit(X_train, y_train)
predictions = model.predict(X_test)

Key parameters:

criterion='gini'. the impurity measure. Can also be 'entropy'.
max_depth=5. limits tree depth to 5 levels. Without this, the tree would grow until every training record is perfectly classified. a classic overfitting recipe producing an enormous, unreadable tree.

8.12.5 Interpreting the Output Tree

The trained tree on the COVID dataset revealed:

Root node: remedies_were_given ≤ 0.5 (binary 0/1. threshold is the midpoint). This was the single most informative split.
True branch (remedies given): Next split on days_of_stay with a computed threshold.
False branch (no remedies): Next split on age with a computed threshold.
Deeper nodes: gender, covid_severity, and age (again) appeared in different branches.

Each node in the printed/scikit-learn output displays:

Gini: impurity at that node (lower = purer).
Samples: number of training records reaching that node.
Value: class distribution, e.g., [12, 5] means 12 recovered, 5 expired.
Class: the predicted class (majority in value).

Key takeaway: The same attribute (age) appeared at different depths in different branches. confirming that decision trees are not simple linear rankings of features.

8.12.6 Accuracy — Confusion Matrix

Accuracy is the fraction of correct predictions:

Accuracy = \frac{T P + T N}{T P + T N + F P + F N}

Where:

TP (True Positive): predicted "expired" and actually expired.
TN (True Negative): predicted "recovered" and actually recovered.
FP (False Positive): predicted "expired" but actually recovered.
FN (False Negative): predicted "recovered" but actually expired.

This is the same confusion matrix framework used for ALL classifiers. logistic regression, SVM, neural networks, etc. Know it for the exam.

8.12.7 Student Q&A

Q: Is max_depth optional? A: Yes. If omitted, the tree grows until every leaf is pure. This produces a very large tree with perfect training accuracy and terrible generalization. Q: What is the ideal depth? A: There is no universal ideal. Too shallow → underfitting (high bias). Too deep → overfitting (high variance). The right depth is found through cross-validation: try depths 1–20, pick the one with best validation accuracy. scikit-learn's GridSearchCV automates this.

8.12.8 Pitfalls

Not setting max_depth. The default is None. the tree grows without limit. Always set a depth or another stopping criterion (min_samples_leaf, min_impurity_decrease).
Interpreting the tree without context. A tree that splits on "days_of_stay ≤ 3.5" is easy to read. A tree with depth 20 and hundreds of leaves is not. Limit depth for interpretability.
Using LabelEncoder on the target. The target should be left as-is for classification. Label encoding is for features.

8.12.9 Recap & Bridge

scikit-learn gives you CART with two lines of code. But the real work is preprocessing (encoding, splitting) and tuning (max_depth, criterion). The tree's output is human-readable: each node shows Gini, samples. class distribution. Next: what happens when you let the tree grow too deep. overfitting.

8.12.10 Real-World & Domain Connection

The COVID-19 dataset example is not a toy. during the pandemic, decision trees were deployed in hospitals to triage patients based on risk factors. The interpretability of decision trees (you can trace exactly why a patient was classified as high-risk) made them preferable to black-box models when doctors needed to trust and understand the predictions. The same pattern applies in credit scoring (Fair Lending laws require explainable decisions) and medical diagnosis.

8.13. Overfitting in Decision Trees

Hook. Your tree gets 100% accuracy on the training data. Perfect! Until you test it on new patients and it's wrong half the time. What happened? Your tree didn't learn medicine. it memorized the training records. This is overfitting. it's the #1 enemy of decision trees.

8.13.1 Intuition

Everyday analogy — Memorizing the answer key. You have a practice exam with 20 questions and the answer key. You memorize all 20 answers perfectly. On the practice exam, you score 100%. On the real exam. with different questions. you fail. You didn't learn the underlying concepts. you memorized specific question-answer pairs.

A decision tree with no depth limit does the same thing: it creates branches so specific that each leaf contains exactly one training record. It memorizes the training data instead of learning the general pattern. The tree has high variance. change one training record and the tree structure shifts dramatically.

Where the analogy breaks: real students can sometimes deduce general principles from memorized facts. A decision tree has no such ability. pure memorization is all an unconstrained tree can do.

8.13.2 Formal Definition

Overfitting occurs when a model learns the noise and peculiarities of the training data rather than the underlying generalizable pattern. In decision trees, overfitting manifests as:

Excessive depth. the tree grows branches for very specific combinations of attribute values that appear in only one or two training records.
High variance. small changes in the training data produce structurally different trees.
Perfect training accuracy with poor test accuracy. the hallmark symptom.

Why it happens in decision trees specifically:

Hunt's algorithm keeps splitting until nodes are pure or attributes run out.
Without a stopping criterion, the algorithm WILL achieve 100% training accuracy. by creating one leaf per training record if necessary.
Each more level of depth adds parameters (split conditions) that can fit noise rather than signal.

8.13.3 Handling Overfitting — Two Strategies

1. Pre-pruning (early stopping): Stop tree growth BEFORE it overfits, using a stopping rule:

max_depth: maximum tree depth (e.g., 5).
min_samples_split: minimum records required to split a node.
min_samples_leaf: minimum records required in a leaf node.
min_impurity_decrease: minimum gain required to justify a split.

Pros: Computationally cheap. you never build the full tree. Cons: It's hard to know when to stop. stopping too early can underfit.

2. Post-pruning (prune after growth): Grow the full tree (let it overfit), then prune back branches that don't improve generalization:

Use a validation set (held-out data, not used in training).
For each internal node, compare: error with the subtree vs. error if this node were a leaf (majority class).
If making it a leaf does not increase validation error, prune the subtree.

Pros: More strong. you see the full tree first, then prune. Cons: More expensive. you build the full overfit tree first. Used by C4.5.

The professor noted: "Two approaches, to be covered in the next session." This section is a preview. full treatment comes later.

8.13.4 Visual Intuition

Plot training accuracy and test accuracy on the y-axis against tree depth on the x-axis:

Depth = 1: Both training and test accuracy are low (underfitting. the tree is too simple).
Depth = 3–5: Training accuracy rises. Test accuracy peaks. This is the sweet spot.
Depth = 10+: Training accuracy approaches 100%. Test accuracy drops. the gap between the two curves widens. This gap IS overfitting.

Takeaway: The goal is the depth where test accuracy peaks, NOT where training accuracy peaks. The gap between the curves is your enemy.

8.13.5 Pitfalls

"100% training accuracy = good model." It usually means overfitting, especially with decision trees. A tree that perfectly classifies training data is almost certainly too deep.
"Post-pruning is always better." It's more strong but more expensive. For large datasets, pre-pruning with max_depth is often the pragmatic choice.
"Cross-validation prevents overfitting." Cross-validation helps you DETECT overfitting (by showing the train-test gap). It doesn't prevent it. you need pruning or depth limits to actually prevent it.

8.13.6 Recap & Bridge

Overfitting = the tree memorizes instead of learns. Fix it with pre-pruning (stop early using max_depth, min_samples_leaf) or post-pruning (grow full, then trim with a validation set). More details in the next lecture. Next: a brief look at regression trees. decision trees for predicting numbers instead of classes.

8.13.7 Real-World & Domain Connection

Overfitting is not just an academic concern. it caused real failures. In 2008, some quantitative finance models (including tree-based models) were so overfit to pre-2008 market data that they catastrophically failed during the financial crisis. The models had learned the noise of a bull market, not the underlying risk. Post-pruning and depth limits are not optional refinements. they are essential safeguards for any model deployed in high-stakes decisions.

8.14. Regression Trees

Hook. Decision trees classify. cat or dog, yes or no. But what if you need to predict a number. house price, temperature, stock return? The same tree structure works. You just change the splitting rule and the leaf prediction. Welcome to regression trees.

8.14.1 Intuition

Everyday analogy — Grouping houses by price. Instead of sorting houses into "expensive" and "cheap" (classification), you want to predict the exact price. A regression tree asks: "Is the square footage > 2000?" If yes, the houses in that branch have an average price of $500K. If no, ask "Number of bedrooms > 2?" Continue until each leaf contains houses with similar prices. The leaf predicts the average price of houses in that leaf.

Where the analogy breaks: classification trees stop when all records in a leaf have the same class. Regression trees almost never achieve "all same value" purity. the target is continuous. So exact equality is vanishingly rare. Instead, they stop when further splits don't reduce error enough.

8.14.2 Formal Definition

A regression tree is a decision tree adapted for predicting a continuous target value instead of a class label.

Key differences from classification trees:

Aspect	Classification Tree	Regression Tree
Target	Discrete class (Yes/No)	Continuous value (price, temperature)
Impurity measure	Gini, Entropy, Error	MSE (Mean Squared Error) or MAE
Leaf prediction	Majority class	Mean of target values in leaf
Stopping	Node is pure (one class)	Further splits don't reduce MSE enough
scikit-learn	`DecisionTreeClassifier`	`DecisionTreeRegressor`

Splitting criterion — MSE: $MSE (t) = \frac{1}{n} i \in t \sum (y_{i} - y ˉ_{t})^{2}$

Where $y ˉ_{t}$ is the mean target value of the records at node $t$ . The split that minimizes the weighted MSE of the children is chosen. exactly analogous to minimizing weighted Gini/entropy in classification.

Leaf prediction: $y^_{leaf} = \frac{1}{n _{leaf}} i \in leaf \sum y_{i}$

The mean of all training target values that fall into that leaf.

8.14.3 Worked Mini-Example

Predicting house prices. 4 houses in a node:

Sq Ft	Bedrooms	Price ($K)
1500	2	300
2000	3	400
2500	3	500
3000	4	600

Parent node MSE: Mean price = (300+400+500+600)/4 = 450. $MSE = \frac{( 300 - 450 ) ^{2} + ( 400 - 450 ) ^{2} + ( 500 - 450 ) ^{2} + ( 600 - 450 ) ^{2}}{4} = \frac{22500 + 2500 + 2500 + 22500}{4} = 12500$

Split on "Sq Ft < 2250":

Left child (1500, 2000): prices 300, 400. Mean = 350. MSE = ((300-350)² + (400-350)²)/2 = (2500+2500)/2 = 2500.
Right child (2500, 3000): prices 500, 600. Mean = 550. MSE = ((500-550)² + (600-550)²)/2 = (2500+2500)/2 = 2500.

Weighted MSE = (2/4)×2500 + (2/4)×2500 = 2500. Gain = 12500 − 2500 = 10000.

Sense-check: The split perfectly separates low-priced from high-priced houses. MSE dropped from 12500 to 2500. a dramatic improvement.

8.14.4 Pitfalls

"Regression trees can achieve zero MSE on training data." They can (with enough depth, one record per leaf). However, this is severe overfitting. same as classification trees.
Using classification accuracy to evaluate regression trees. Accuracy is meaningless for continuous targets. Use MSE, MAE, or R².
Forgetting that leaves predict means, not individual values. A leaf with houses at 300K and 500K predicts 400K. The prediction is always the average of training records in that leaf.

8.14.5 Recap & Bridge

Regression trees = same recursive structure. However, MSE replaces Gini/entropy. leaves predict means instead of majority classes. scikit-learn's DecisionTreeRegressor is the CART implementation. Next: a conceptual distinction that appears on the exam. discriminative vs generative classifiers.

8.14.6 Real-World & Domain Connection

Regression trees are the building blocks of some of the most accurate predictive models in existence. Gradient Boosted Regression Trees (GBRT), implemented in XGBoost and LightGBM, combine hundreds of shallow regression trees to predict everything from housing prices (Zillow's Zestimate) to click-through rates (ad tech) to weather forecasts. The individual trees are typically only 3–6 levels deep. too shallow to be useful alone. However, powerful in ensembles.

8.15. Discriminative vs Generative Classifiers

Hook. Two artists are asked to draw the difference between cats and dogs. The first draws a line down the middle and labels one side "cat," the other "dog." The second draws a complete picture of a cat and a complete picture of a dog, then compares. Both can tell cats from dogs. But only the second can tell you what a cat actually looks like. This is the discriminative-generative divide.

8.15.1 Intuition

Everyday analogy — Border guard vs biographer.

A discriminative classifier is like a border guard who only cares about the boundary line. "Which side of the line are you on?" It learns what separates classes. the decision boundary. and nothing else. Logistic regression and decision trees are border guards.

A generative classifier is like a biographer who studies each class in depth. "I know everything about cats. their fur, size, behavior. I know everything about dogs. Now. This one do you look more like?" It learns the full distribution of each class. how features are generated for each category. Naive Bayes and Gaussian Mixture Models are biographers.

Where the analogy breaks: the border guard can't tell you if a creature is neither cat nor dog (outlier detection). The biographer can — "this doesn't look like any animal I've studied." Generative models support density estimation. discriminative models do not.

8.15.2 Formal Definitions

Discriminative classifiers learn the decision boundary $P (y ∣ x)$ . the conditional probability of the class given the features. They focus on what distinguishes one class from another.

Examples: logistic regression, decision trees, SVM, neural networks (for classification).

Generative classifiers learn the joint distribution $P (x, y)$ . how the features and class co-occur. Using Bayes' rule, they compute $P (y ∣ x) = P (x ∣ y) P (y) / P (x)$ . They model how data for each class is generated.

Examples: Naive Bayes, Hidden Markov Models, Gaussian Mixture Models, Linear Discriminant Analysis.

8.15.3 Comparison Table

Property	Discriminative	Generative
What is learned	$P (y ∣ x)$ . decision boundary	$P (x, y)$ or $P (x ∣ y)$ . class distributions
Focus	What separates classes	What defines each class
Training goal	Minimize classification error	Maximize data likelihood
Can detect outliers?	No	Yes (via density estimation)
Can generate new data?	No	Yes (sample from $P (x ∣ y)$ )
Handles missing features?	Needs imputation	Can marginalize over missing values
Sample efficiency	Needs more data for complex boundaries	Can work with less data if model is right
Examples	Logistic regression, decision trees, SVM	Naive Bayes, HMM, GMM, LDA

When to pick which:

Choose discriminative when you only care about classification accuracy and have enough data. it directly optimizes the decision boundary.
Choose generative when you need outlier detection, data generation, handling missing values, or when you have strong domain knowledge about how each class is distributed.

8.15.4 Worked Example — Exam Application

Sample exam question (from the lecture):

> "Your friend needs to classify job applications into good/bad categories and also detect applicants who lie using density estimation to detect outliers. Do you recommend a discriminative or generative classifier?"

Answer: Generative.

Why: Density estimation. modeling the full distribution of "honest" applications to detect those that fall outside it. is a generative capability. A discriminative classifier only draws a line between good and bad. it cannot tell you whether an application is anomalous relative to all known patterns. Generative models learn $P (x ∣ y)$ . This lets them flag "this application doesn't look like any honest or dishonest application I've seen."

8.15.5 Assumptions & Scope

Scope: When generative models struggle. Generative models make stronger assumptions about the data distribution (e.g., Naive Bayes assumes feature independence. GMM assumes Gaussian clusters). When these assumptions are violated, discriminative models often outperform because they make fewer distributional assumptions. they just learn the boundary.

8.15.6 Pitfalls

"Decision trees are generative." No. they learn decision boundaries, not class distributions. They are discriminative.
"Generative models are always better because they know more." Knowing more (the full distribution) means making more assumptions. When those assumptions are wrong, the extra knowledge hurts rather than helps.
**Confusing the direction of $P (x ∣ y)$ vs $P (y ∣ x)$ .** Generative models learn $P (x ∣ y)$ — "given the class, what features are likely?" Discriminative models learn $P (y ∣ x)$ — "given the features, what class is likely?"

8.15.7 Exam Guidance

Exam note: Expect conceptual questions: "Which type of classifier would you use for [scenario]?" and "Is [algorithm X] discriminative or generative?" The density estimation / outlier detection angle is the most common differentiator. If the problem mentions detecting anomalies, outliers, or generating new samples → generative. If it only mentions classification → either could work. However, discriminative is usually the default.

8.15.8 Recap

Discriminative = learns the boundary ( $P (y ∣ x)$ ). Generative = learns the full picture ( $P (x, y)$ ). Decision trees are discriminative. If you need outlier detection or data generation, you need a generative model. This distinction appears on the exam.

8.15.9 Real-World & Domain Connection

The discriminative-generative spectrum is not binary. Modern deep learning has blurred the line: Generative Adversarial Networks (GANs) are generative (they create images). However, the discriminator inside a GAN is discriminative. Variational Autoencoders (VAEs) learn $P (x)$ . purely generative. Large language models (GPT) are generative. they model $P (next word ∣ previous words)$ . Knowing which paradigm applies helps you understand what a model can and cannot do.

8.16. Exam Guidance

This section consolidates all exam-relevant information from the lecture. The professor discussed the exam format, topic coverage. sample question types. Use this as a study checklist.

8.16.1 Format and Logistics

Both typed and handwritten submission options are available. If typing, submit directly. If handwriting, scan and upload.
Calculators are permitted. essential for entropy, Gini. information gain calculations.
Expect calculation/numerical questions from every major topic.
The question paper will be uploaded. sample questions from previous papers were discussed.

8.16.2 Topics Covered (up to this lecture)

#	Topic	Question Type	Priority
1	Linear Regression	Conceptual	Review
2	Logistic Regression	Numerical calculation possible	Study
3	Regularization (Ridge, Lasso)	Conceptual. bias-variance, λ effects	Study
4	Decision Trees (ID3)	Manual construction. entropy & gain	High
5	Confusion Matrix	Numerical — TP, FP, TN, FN, accuracy, precision, recall, F-score	High
6	Data Preprocessing	Identify inconsistencies, missing values, scaling, encoding	Study
7	Gradient Descent vs Normal Equation	When to use which	Review
8	Feature Scaling	Importance in convergence	Review
9	Discriminative vs Generative	Conceptual + application scenario	High
10	Overfitting and Pruning	Pre-pruning vs post-pruning concepts	Study

8.16.3 Sample Question Types (from the lecture discussion)

Data Preprocessing Task: Given a messy dataset. inconsistent names, impossible age (350), missing height, inconsistent encoding ("positive" / "1"). list the preprocessing steps to clean it. Answer should cover: standardize categorical values, remove/fix impossible numeric values, impute missing values, unify binary encoding.

Discriminative vs Generative: "Classify job applications into good/bad AND detect liars using density estimation for outlier detection. Which type of classifier?" → Generative. Density estimation (modeling the full distribution to flag anomalies) is a generative capability.

Ridge Regression Diagnosis: "Training error ≈ validation error, both fairly high. High bias or high variance? Action?" → High bias (underfitting). Decrease λ to allow more model flexibility. If it were high variance (overfitting), you'd increase λ.

Gradient Descent vs Least Squares: "Very large dataset. which approach?" → Gradient descent. Normal equation matrix inversion is $O (d^{3})$ . infeasible for large d. Gradient descent scales better.

Feature Scaling: Explain its importance. In logistic regression with gradient descent, unscaled features create elongated contour ellipses → gradient path jitters → slow convergence.

Confusion Matrix — Fraud Detection: "200 test transactions. Which metric matters more. precision or recall?" → Recall. You want to catch as many fraudulent transactions as possible, even at the cost of some false positives. Missing a fraud is far worse than flagging a legitimate transaction.

Decision Tree Construction: Given a small dataset (10–20 records, 3–5 attributes), construct the tree using ID3. Compute entropy at each node, information gain for all attributes, pick the best. Manual computation at 1–2 levels. One question on this in the sample paper.

8.16.4 General Exam Advice

Read the question paper structure beforehand.
Questions test understanding, not memorization. Interpretations and justifications are the "theory" component.
Most questions are calculation-based with interpretation required.
The professor noted: "The first exam after a long break can be surprising. the sample discussion should give a clear idea of the format."

Key Industry Applications and Real-World Connections

Decision trees are not just classroom exercises. they power production systems across industries. This section maps each concept from the lecture to its real-world instantiation.

Concept	Industry Application	Tool / Library
Decision Tree Classification	Credit scoring, loan default prediction in banking	scikit-learn `DecisionTreeClassifier`
Decision Tree Regression	House price prediction, demand forecasting	scikit-learn `DecisionTreeRegressor`
CART Algorithm	The default decision tree in virtually all ML libraries	scikit-learn, R `rpart`
Entropy / Information Gain	Feature selection, mutual information in genomics	scikit-learn `mutual_info_classif`
Gini Index	Default splitting criterion in production trees	scikit-learn default (`criterion='gini'`)
Gain Ratio	C4.5 algorithm, still used in research and education	Weka `J48` classifier
Confusion Matrix	Fraud detection, medical diagnosis evaluation	scikit-learn `confusion_matrix`
Pruning	Preventing overfitting in production models	`max_depth`, `ccp_alpha` in scikit-learn

COVID-19 Dataset: The professor showed a real hospital dataset (anonymized) predicting patient outcomes (recovered vs expired). This represents the medical diagnosis use case. decision trees are preferred when doctors need to understand why a prediction was made.

Credit Risk / Loan Default: The loan default example throughout the lecture is directly from banking. Decision trees are used in credit scoring because regulators require explainable decisions (Fair Lending laws).

Fraud Detection: Confusion matrix metrics. especially recall. are critical when the cost of missing a positive case (fraud) far outweighs the cost of a false alarm.

Gini vs Entropy in Practice: scikit-learn defaults to Gini because it's computationally faster (no log computations). Entropy is available as criterion='entropy' when information-theoretic purity is preferred. In most real applications, the choice makes negligible accuracy difference.

Summary of Key Formulas

All formulas from this lecture in one place. Use this as a quick reference for exam preparation.

Formula	Expression	Used By	Range / Notes
Gini Index	$1 - \sum_{i = 0}^{C - 1} [P (i ∣ t)]^{2}$	CART	$[0, 1 - 1/ C]$
Entropy	$- \sum_{i = 0}^{C - 1} P (i ∣ t) lo g_{2} P (i ∣ t)$	ID3, C4.5	$[0, lo g_{2} C]$
Misclassification Error	$1 - max_{i} P (i ∣ t)$	Rarely used	$[0, 1 - 1/ C]$
Information Gain (Δ)	$I (parent) - \sum_{j} \frac{n _{j}}{n} \cdot I (child_{j})$	ID3, C4.5	$[0, I (parent)]$
Gain Ratio	$\frac{Information Gain}{Split Information}$	C4.5	Normalized Gain
Split Information	$- \sum_{j = 1}^{k} \frac{n _{j}}{n} lo g_{2} \frac{n _{j}}{n}$	C4.5	$[0, lo g_{2} k]$
Weighted Impurity	$\sum_{j} \frac{n _{j}}{n} \cdot I (child_{j})$	All algorithms	Weighted average

Notation:

$P (i ∣ t)$ . fraction of class $i$ at node $t$
$C$ . number of classes
$n$ . total records at parent
$n_{j}$ . records at child $j$
$k$ . number of children (branches)

Quick memory aids:

$lo g_{2} (0.5) = - 1$ , $lo g_{2} (0.25) = - 2$ , $lo g_{2} (1) = 0$ , $0 lo g_{2} 0 = 0$ (convention)
Max Gini (binary) = 0.5. max Entropy (binary) = 1.0
Information Gain = parent impurity − weighted child impurity
Gain Ratio = Information Gain ÷ Split Information (entropy of the split itself)

Key Pedagogical Moments

The professor's most memorable teaching points. the lines that make concepts stick. Each is a distillation of a core insight from the lecture.

"50-50 split tells you nothing." A node that is half class A and half class B has maximum impurity. you are as confused as if you hadn't split at all. This is the core intuition behind all impurity measures.

"Think of it like a flowchart of yes/no questions." The decision tree is natural. humans classify things the same way by asking sequential questions about characteristics. The algorithm just automates what we do intuitively.

"The root is an internal node." A subtlety students often miss. The root of the tree tests an attribute. So it IS an internal node. only leaves are not internal nodes.

"Customer ID gives the purest split. but it's useless." The most counterintuitive result in decision tree learning: the attribute with maximum information gain can be the worst possible choice. This is why Gain Ratio exists.

"Multiple trees can fit the same data." The choice of root node dramatically changes the tree. Different impurity measures can lead to different trees. There is no single "correct" tree. only better and worse ones.

"If a split increases entropy, stop that branch." Splitting should reduce confusion. If it adds confusion, stop. it's a valid stopping criterion.

"Logarithms make multiplication into addition." The mathematical reason for log in entropy: it converts exponential growth of states into additive bits, making calculations manageable.

"Temperature was never used." Not all attributes end up in the final tree. The algorithm naturally discards uninformative features. This is a form of built-in feature selection.

"Same attribute can appear at different depths." A tree is not a simple linear ranking of features. The same feature may be useful at different points in different branches.

"Don't expect the Gini tree to match the entropy tree." They can select different root nodes. This is normal and expected. neither is "wrong."

"Too shallow = underfitting. Too deep = overfitting." The depth hyperparameter controls the bias-variance tradeoff. There is no universal ideal depth. it must be tuned per dataset.

ML Lecture 8 notes · Decision Trees

Machine Learning· postgraduate· 2026-06-28

Sections Breakdown

18.1 Information Theory

Mathematical framework of entropy, impurity measures, and information gain for decision tree splits

28.2 Decision Tree Representation

Flowchart-like structure of root, internal, and leaf nodes for classification

38.3 Hunt's Algorithm

Recursive partitioning method underlying all major decision tree algorithms

48.4 Splitting Criteria

Strategies for binary, multi-way, nominal, ordinal, and continuous attribute splits

58.5 Impurity Measures

Gini index, entropy, and misclassification error for quantifying node purity

68.6 Information Gain

Measuring impurity reduction to choose the best splitting attribute

78.7 Golf Dataset with ID3

Full worked example computing entropy and information gain by hand

88.8 Golf Dataset with Gini

Full worked example computing Gini gain and comparing with entropy results

98.9 Gain Ratio

Normalized information gain addressing bias toward many-valued attributes

108.10 Continuous-Valued Attributes

Threshold determination algorithm for continuous attributes in CART

118.11 ID3 Algorithm

Formal specification of the Iterative Dichotomiser 3 algorithm

128.12 Python Implementation

Using scikit-learn's DecisionTreeClassifier with real COVID-19 hospital data

138.13 Overfitting

Pre-pruning and post-pruning strategies to prevent memorization

148.14 Regression Trees

Decision trees for continuous target prediction using MSE splitting

158.15 Discriminative vs Generative

Comparison of decision boundaries and class distribution modeling approaches

168.16 Exam Guidance

Format, topics, and sample question types for the ML exam

Postgraduate students in Machine Learning

Exam Revision Notes

Below is the distilled, exam-ready core of this lecture. Every entry is built from the full textbook notes above. Use this section for rapid review — but if something doesn't make sense, go back to the full explanation in the main content.

Entropy and Impurity Measures

Must-know: Entropy measures the average surprise of a node's class distribution. Pure nodes have entropy = 0; 50-50 splits have maximum entropy (1.0 for binary classification).

$e x t E n t r o p y (t) = - i = 0 \sum C - 1 P (i ∣ t) lo g_{2} P (i ∣ t)$

⚠️ Top pitfall: Forgetting the negative sign or using natural log instead of $lo g_{2}$ . $lo g_{2} (0.5) = - 1$ , $lo g_{2} (0.25) = - 2$ .

Self-check: A node has 6 records of class A and 4 of class B. What is its entropy?

Connects to: Information Gain, Gini Index

Information Gain

Must-know: Information gain = parent impurity minus weighted average child impurity. Choose the attribute with the maximum gain at each split.

$Gain = I (e x t p a r e n t) - j = 1 \sum k \frac{n _{j}}{n} \times I (e x t c hi l d_{j})$

⚠️ Top pitfall: Not weighting child impurities by the number of records. A child with 1 record should contribute less than a child with 100.

Self-check: Parent Gini = 0.48. Child 1 (4 records) Gini = 0.5, Child 2 (6 records) Gini = 0.375. What is the Gini gain?

Connects to: Entropy, Gini Index, Hunt's Algorithm

Gini Index

Must-know: Gini measures the probability two randomly chosen records have different classes. Default in scikit-learn. Ranges from 0 (pure) to 0.5 (binary maximum).

$e x t G ini (t) = 1 - i = 0 \sum C - 1 [P (i ∣ t)]^{2}$

⚠️ Top pitfall: Thinking Gini ranges from 0 to 1 for binary classification. It ranges from 0 to 0.5. Gini gain and entropy gain usually agree but not always.

Self-check: A node has 3 Yes and 3 No. What is its Gini index?

Connects to: Entropy, CART algorithm

Gain Ratio

Must-know: Fixes information gain's bias toward many-valued attributes (the Customer ID problem). Divides gain by the entropy of the split itself.

$Gain Ratio = \frac{e x t I n f or ma t i o n G ain}{e x t S pl i t I n f or ma t i o n} where Split Information = - j = 1 \sum k \frac{n _{j}}{n} lo g_{2} \frac{n _{j}}{n}$

⚠️ Top pitfall: Zero denominator when Split Information is near zero. Standard fix: first filter by above-average Information Gain, then apply Gain Ratio.

Self-check: Why does Customer ID produce high Information Gain but low Gain Ratio?

Connects to: Information Gain, C4.5 algorithm

ID3 Algorithm

Must-know: Recursive, greedy, top-down algorithm using entropy and information gain with multi-way splits. Base cases: pure node or no attributes remain.

$e x t I D 3 (e x t E x am pl es, e x t T a r g e t, e x t A tt r ib u t es) i g h t a r r o w e x t T r ee$

⚠️ Top pitfall: ID3 cannot handle continuous attributes directly — they must be discretized first. ID3 is greedy and never backtracks from a suboptimal root choice.

Self-check: What are the three stopping conditions for ID3?

Connects to: CART, Hunt's Algorithm, C4.5

Overfitting in Decision Trees

Must-know: A tree with no depth limit achieves 100% training accuracy by memorizing individual records (one leaf per record). Fix with pre-pruning (max_depth, min_samples_leaf) or post-pruning with a validation set.

⚠️ Top pitfall: Treating 100% training accuracy as a success. It almost always means severe overfitting. The gap between training and test accuracy IS overfitting.

Self-check: Training accuracy = 99%, Validation accuracy = 65%. What is happening and what should you do?

Connects to: Bias-Variance Tradeoff, Pruning

Discriminative vs Generative Classifiers

Must-know: Discriminative models learn the boundary P(y|x). Generative models learn the full distribution P(x,y). Decision trees are discriminative. Use generative when you need outlier detection or data generation.

⚠️ Top pitfall: Thinking decision trees are generative. They only learn decision boundaries, not class distributions.

Self-check: You need to detect fraudulent transactions and also identify novel fraud patterns. Which classifier type?

Connects to: Logistic Regression, Naive Bayes

Previous LectureLecture 07 · Logistic Regression — Complete Enriched Lecture Notes

Next LectureLecture 09 · Decision Trees — Overfitting, Pruning, and MDL

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.