Take a Break
5:00
Inhale…
Give your mind a break — no phone, no music, just idle time or a quick walk.
Supervised Machine Learning: Naive Bayes, Decision Trees, and Random Forest
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
- Machine learning fundamentals and the supervised/unsupervised taxonomy — covered in Lecture 12
- Core definitions and learning paradigms — covered in Lecture 13
- Unsupervised clustering (k-means, hierarchical) — covered in Lecture 13
14.1 Supervised Learning Overview and Foundations
Hook — how does a machine "learn" the right answer without being told every rule? Consider a real-estate company that must price thousands of houses it has never seen. It cannot write an if-else rule for every house, but it does hold thousands of past sales where each house's features and its actual selling price are both recorded. The machine can mine those historical records and then guess the price of any new house. That idea — learning a prediction rule from examples whose answers are already known — is the supervised learning paradigm.
Supervised machine learning is a core paradigm (a defining framework or way of doing machine learning) that operates on labeled historical training data. In a supervised setting, every input sample is paired with a target label (also called the ground-truth output) that the model aims to learn. The primary objective is to analyze historical feature patterns and infer a functional mapping that accurately predicts the target labels for new, unseen, and unlabeled sample data.
Intuition — learning from a graded answer key. Think of a student revising for an exam with a solved question bank: each practice problem (features) comes with its official answer (label). By studying the pairing, the student learns the general pattern — not by memorizing one problem, but by noticing how feature values tend to produce certain answers. On exam day the student faces unseen questions and applies the inferred pattern. That is exactly what a supervised model does with historical data.
14.1.1 Target Variables in Classification and Regression
The single most important fork in supervised learning is the mathematical nature of the target variable — what kind of answer the model must produce. This one decision selects the entire family of algorithms.
- Classification: The target variable represents discrete categorical labels or class memberships, such as predicting binary outcomes like \(\text{Yes} / \text{No}\), \(\text{True} / \text{False}\), or multi-class categories like \(\text{Class 1}, \text{Class 2}, \dots, \text{Class } k\). The output is a membership — the sample belongs to exactly one of a fixed set of named groups.
- Regression: The target variable represents continuous numeric values, such as predicting historical house prices, stock values, or continuous percentage values. The output is a number on a scale — there is no fixed list of answers, only a range of possible values.
Scope — reading the target type before choosing the algorithm. The boundary between the two families is decided by the target column, not by the features. If the answer column holds categories (spam/not spam, fraud/legit), you need a classifier; if it holds numbers on a continuous scale (price in dollars, temperature in degrees), you need a regressor. A common trap is treating an ordinal code like \(\text{Class } 1, \text{Class } 2, \text{Class } 3\) as a continuous number — the model then "predicts" meaningless averages between categories. The examinable algorithms in this lecture (Naive Bayes, Decision Trees, Random Forest) are all classifiers; regression appears only as the sibling category that motivates the distinction.
Real-world: Supervised machine learning models are widely deployed in automated valuation systems to predict continuous house prices based on physical property characteristics (square footage, number of bedrooms, location) and historical sales data. These same systems power credit scoring, insurance premium estimation, and demand forecasting.
14.1.2 Supervised Learning vs. Unsupervised Learning
The label column is the dividing line between the two great families of machine learning. Unlike unsupervised learning algorithms such as k-means clustering and hierarchical clustering — which partition unlabeled data solely by discovering intrinsic distance patterns — supervised algorithms rely explicitly on known target outputs to guide model training.
| Dimension | Supervised Learning | Unsupervised Learning |
|---|---|---|
| Training data | Labeled — every sample has a known target | Unlabeled — only features, no answers |
| Goal | Learn the mapping from features to the label | Discover hidden structure (groups, patterns) |
| Typical task | Classification, regression | Clustering (k-means, hierarchical), association rules |
| Evaluation | Compare predicted vs. known labels | Subjective / internal measures (e.g., cluster cohesion) |
| Example | Predict house price from features | Group customers into segments by similarity |
When to pick which: use supervised learning when a trusted answer column exists and the goal is prediction of that answer; use unsupervised learning when the goal is to explore the data's natural structure and no answer column exists.
Exam note: The regular semester examinations cover supervised classification algorithms — specifically the Naive Bayes Classifier and Random Forests, along with foundational Decision Trees. Regression trees and linear regression variants are designated for self-study and specialized makeup assessments, so focus revision energy on the three classification algorithms built up in the coming sections.
Pitfalls:
- Assuming "supervised" means "someone must label everything." Supervised learning needs labels on the training set only; the whole point is to predict labels for new, unlabeled data automatically.
- Conflating classification with regression. Ask "is the answer a category or a number?" before picking an algorithm; the entire rest of the pipeline (metrics, loss, evaluation) depends on it.
- Thinking clustering is a supervised task. k-means and hierarchical clustering find groups without any label; they cannot be scored against ground truth the way a classifier can.
- Ignoring label quality. A supervised model is only as good as its training labels — noisy or biased labels are learned and repeated, a fact the professor returns to when discussing overfitting later.
Recap + bridge: Supervised learning learns a features-to-label mapping from historical labeled data, and splits into classification (categorical target) and regression (continuous target). Next, we build the first classifier from the ground up: Naive Bayes starts from the humble act of counting past events — the traffic on past Sundays.
Real-world: In industry, supervised models are the workhorses behind automated valuation (house pricing), credit-risk scoring, fraud detection, and medical diagnosis support. The specific algorithms that follow — Naive Bayes, Decision Trees, and Random Forest — are chosen because they scale to the massive, high-dimensional datasets typical of Big Data platforms such as Apache Spark MLlib.
14.2 Naive Bayes Classifier
Hook — can counting the past tell us the future? You check the weather app before deciding whether to play outdoor tennis, and you instinctively weigh how often similar days led to a fun game. The Naive Bayes Classifier turns exactly that instinct into mathematics: it counts how often each class occurred in the past, combines those counts with the current evidence, and picks the class with the highest computed probability. No optimization loop, no gradient — just careful counting and multiplying.
The Naive Bayes Classifier is a probabilistic supervised learning algorithm built upon Bayes' Theorem. It relies heavily on probability calculations to determine the most likely target class for a given set of input feature observations. Instead of drawing decision boundaries, it computes scores — how likely each candidate class is, given the features it observes.
14.2.1 Probabilistic Learning Intuition via Traffic Density
To understand how probability enables machine learning, consider predicting road traffic density on an upcoming Sunday based on 4 weeks of historical traffic observations recorded across days of the week. The historical observations for past Sundays yield the following traffic frequency distributions across 4 total Sunday samples:
| Traffic density on past Sundays | Count (out of 4) |
|---|---|
| Low | 3 |
| Medium | 1 |
| High | 0 |
Human intuition estimates the upcoming Sunday traffic by selecting the majority outcome. In probability theory, majority corresponds directly to maximum likelihood — the outcome that the observed data makes most probable. The empirical probabilities are calculated by dividing each count by the total number of Sunday samples:
The probability of traffic being Low on Sunday is three out of four: \[ P(\text{Traffic} = \text{Low} \mid \text{Day} = \text{Sunday}) = \frac{3}{4} = 0.75 \] where \(P(\text{Traffic} = \text{Low} \mid \text{Day} = \text{Sunday})\) is the conditional probability of experiencing low traffic given that the day is Sunday.
The probability of traffic being Medium on Sunday is one out of four: \[ P(\text{Traffic} = \text{Medium} \mid \text{Day} = \text{Sunday}) = \frac{1}{4} = 0.25 \] where \(P(\text{Traffic} = \text{Medium} \mid \text{Day} = \text{Sunday})\) is the conditional probability of experiencing medium traffic given that the day is Sunday.
The probability of traffic being High on Sunday is zero out of four: \[ P(\text{Traffic} = \text{High} \mid \text{Day} = \text{Sunday}) = \frac{0}{4} = 0.00 \] where \(P(\text{Traffic} = \text{High} \mid \text{Day} = \text{Sunday})\) is the conditional probability of experiencing high traffic given that the day is Sunday.
Formalize — the majority outcome is the maximum-likelihood prediction. A conditional probability \(P(A \mid B)\) answers the question "given that \(B\) happened, how likely is \(A\)?" Here the condition is \(\text{Day} = \text{Sunday}\), and the three candidate outcomes are the traffic levels. Because \(0.75 > 0.25 > 0.00\), the algorithm predicts that traffic on the next Sunday will be Low. This is a complete, working classifier in miniature: it has classes (Low/Medium/High), a conditioning feature (the day), learned frequencies, and a decision rule (pick the class with the highest conditional probability).
Worked example — sense-checking the frequency counts. The counts must sum to the total, and each probability must lie in \([0, 1]\):
- \(3 + 1 + 0 = 4\) samples — the denominator is consistent.
- \(P(\text{Low}) = 0.75\), \(P(\text{Medium}) = 0.25\), \(P(\text{High}) = 0.00\), and \(0.75 + 0.25 + 0.00 = 1.00\) — the probabilities partition the sample space.
- Since Low has the largest share, "Low" wins. Sense-check: three of the four recorded Sundays were low-traffic, so betting on Low on the next Sunday is the safest choice — and it matches what a human would guess without any probability theory.
The brain implicitly uses past event frequencies to anticipate future occurrences, forming the baseline instinct for probabilistic learning.
14.2.2 Intuition for Conditional Probability
An event's likelihood changes when secondary information about a related event becomes known. This is the everyday core of conditional probability: new evidence updates old beliefs.
Intuition — the weather forecast changes your mood, the recession changes your job fears. Suppose you plan a vacation and have baseline expectations about your emotional state tomorrow (Happy, Normal, or Sad). Before going to sleep, you receive updated information on your phone indicating that tomorrow's weather will be awesome. Receiving positive weather information increases the intensity and probability of feeling Happy. Conversely, if the forecast predicts heavy rain, the probability of feeling Happy decreases. The probability of a primary event \(A\) (feeling Happy) varies dynamically when we know that a secondary event \(B\) (awesome weather) has occurred.
Corporate layoffs occur periodically in business environments regardless of overall economic health. However, when news of an economic recession emerges, the intensity and fear of layoffs spike dramatically. The occurrence of the secondary event (recession) directly amplifies the conditional probability of the primary event (layoffs).
The shared structure of both examples: the unconditional chance of \(A\) (happy mood, layoffs) is one number, but the conditional chance \(P(A \mid B)\) given a relevant event \(B\) (nice weather, recession) is a different, usually larger or smaller number. Conditional probability is the mathematical tool for that update.
14.2.3 Derivation of Bayes' Theorem
Conditional probability quantifies the likelihood of event \(A\) occurring given that event \(B\) has already taken place, denoted as \(P(A \mid B)\). We build the formula from a concrete counting example, then rearrange it into Bayes' Theorem.
Consider a universal sample space containing \(N = 40\) total element outcomes divided across two overlapping events, \(A\) and \(B\):
- Elements residing strictly in event \(A\) alone: 15
- Elements residing in the intersection of \(A\) and \(B\) (\(A \cap B\)): 5
- Elements residing strictly in event \(B\) alone: 10
- Elements residing outside both \(A\) and \(B\): 10
The total number of elements in event \(A\) is \(15 + 5 = 20\). The unconditional probability of event \(A\) is: \[ P(A) = \frac{20}{40} = 0.50 \] where \(P(A)\) is the probability of event \(A\) in the universal sample space.
The total number of elements in event \(B\) is \(10 + 5 = 15\). The unconditional probability of event \(B\) is: \[ P(B) = \frac{15}{40} = 0.375 \] where \(P(B)\) is the probability of event \(B\) in the universal sample space.
The joint probability of both events \(A\) and \(B\) occurring simultaneously is five out of forty: \[ P(A \cap B) = \frac{5}{40} = 0.125 \] where \(P(A \cap B)\) is the joint probability of the intersection of \(A\) and \(B\).
Formalize — conditioning shrinks the sample space. When event \(B\) is given, the effective sample space shrinks from the universal space of 40 down strictly to the space covered by event \(B\) (15 outcomes). Within this restricted space \(B\), the favorable outcomes for event \(A\) are constrained to the intersection \(A \cap B\) (5 outcomes). The conditional probability of event \(A\) given event \(B\) is the joint probability divided by the probability of event \(B\): \[ P(A \mid B) = \frac{P(A \cap B)}{P(B)} = \frac{5/40}{15/40} = \frac{5}{15} = \frac{1}{3} \] where \(P(A \mid B)\) is the conditional probability of \(A\) given \(B\), \(P(A \cap B)\) is the joint probability, and \(P(B)\) is the probability of the given condition \(B\).
Similarly, the conditional probability of event \(B\) given event \(A\) is: \[ P(B \mid A) = \frac{P(B \cap A)}{P(A)} = \frac{5/40}{20/40} = \frac{5}{20} = \frac{1}{4} \] where \(P(B \mid A)\) is the conditional probability of \(B\) given \(A\), and \(P(A)\) is the probability of condition \(A\).
Because set intersection is commutative, \(P(A \cap B) = P(B \cap A)\). Expressing the joint probabilities from both conditional probability formulas yields: \[ P(A \cap B) = P(A \mid B) \cdot P(B) \] \[ P(B \cap A) = P(B \mid A) \cdot P(A) \]
Equating the right-hand sides of both equations gives: \[ P(A \mid B) \cdot P(B) = P(B \mid A) \cdot P(A) \]
Dividing both sides by \(P(B)\) yields Bayes' Theorem: \[ P(A \mid B) = \frac{P(B \mid A) \cdot P(A)}{P(B)} \] where \(P(A \mid B)\) is the posterior probability of target event \(A\) given feature event \(B\), \(P(B \mid A)\) is the likelihood of observing feature \(B\) given class \(A\), \(P(A)\) is the prior probability of class \(A\), and \(P(B)\) is the marginal predictor probability of feature \(B\).
The four moving parts of Bayes' Theorem — a naming that will appear on the exam:
- Prior \(P(A)\): what we believed about \(A\) before seeing evidence — in the vacation analogy, your baseline mood before checking the weather app.
- Likelihood \(P(B \mid A)\): how consistent the evidence \(B\) is with the hypothesis \(A\).
- Posterior \(P(A \mid B)\): the updated belief about \(A\) after observing \(B\) — this is what a classifier actually uses.
- Marginal \(P(B)\): the overall frequency of the evidence, acting as a normalizing constant.
Worked example — verifying the numbers. Every probability must lie in \([0, 1]\) and the joint must be reachable from either conditional:
- \(P(A) = 0.50\), \(P(B) = 0.375\), \(P(A \cap B) = 0.125\), and \(0.125 \le \min(0.50, 0.375)\) — an intersection can never exceed either marginal.
- Round-trip check: \(P(A \mid B) \cdot P(B) = \frac{1}{3} \cdot \frac{3}{8} = \frac{1}{8} = 0.125 = P(A \cap B)\). Likewise \(P(B \mid A) \cdot P(A) = \frac{1}{4} \cdot \frac{1}{2} = \frac{1}{8}\). Both routes give the same joint, which is exactly why the two right-hand sides can be equated.
- Sense-check: \(P(A \mid B) = \frac{1}{3}\) means "among the 15 outcomes where \(B\) holds, 5 also belong to \(A\)" — \(5/15\), correct.
14.2.4 The Naive Independence Assumption and Multi-Feature Classification
Real classification problems rarely have a single feature — the Play Tennis problem uses four (Outlook, Temperature, Humidity, Wind). When predicting a target class \(C_k\) given multiple observed feature variables \(\mathbf{X} = (X_1, X_2, \dots, X_n)\), Bayes' Theorem extends to: \[ P(C_k \mid X_1, X_2, \dots, X_n) = \frac{P(X_1, X_2, \dots, X_n \mid C_k) \cdot P(C_k)}{P(X_1, X_2, \dots, X_n)} \] where \(P(C_k \mid X_1, \dots, X_n)\) is the posterior probability of class \(C_k\) given all features, \(P(X_1, \dots, X_n \mid C_k)\) is the joint likelihood of all features given class \(C_k\), \(P(C_k)\) is the class prior probability, and \(P(X_1, \dots, X_n)\) is the joint marginal probability of the features.
Computing the joint likelihood \(P(X_1, X_2, \dots, X_n \mid C_k)\) directly from data requires massive amounts of co-occurrence data across all feature combinations — we would need counts for every possible combination of Outlook, Temperature, Humidity, and Wind together. With many features, those combinations explode and most are never observed in the training data. To resolve this, the Naive Bayes algorithm introduces the Naive Independence Assumption: it assumes that all feature variables \(X_1, X_2, \dots, X_n\) are conditionally independent of each other given the target class \(C_k\).
Formalize — the naive assumption turns one giant table into many small ones. Under conditional independence, the joint likelihood decomposes into the product of individual conditional probabilities: \[ P(X_1, X_2, \dots, X_n \mid C_k) = P(X_1 \mid C_k) \cdot P(X_2 \mid C_k) \cdots P(X_n \mid C_k) = \prod_{i=1}^n P(X_i \mid C_k) \] where \(P(X_i \mid C_k)\) is the individual conditional probability of feature \(X_i\) given target class \(C_k\). Each factor is easy to estimate: it is just a single-feature pivot count, exactly the kind of counting we did for traffic on Sunday.
Substituting this product back into Bayes' Theorem yields the Naive Bayes formula: \[ P(C_k \mid X_1, X_2, \dots, X_n) = \frac{P(C_k) \cdot \prod_{i=1}^n P(X_i \mid C_k)}{P(X_1, X_2, \dots, X_n)} \]
In real-world applications, features are rarely strictly independent (for example, atmospheric humidity and weather outlook exhibit natural physical correlations). However, researchers and practitioners have established that assuming independence yields highly effective and robust classification performance in practice — the model is "naive" because it pretends the features do not influence each other, yet this simplification usually costs little accuracy.
When comparing target classes (such as predicting whether Play = Yes vs. Play = No), the denominator \(P(X_1, X_2, \dots, X_n)\) is identical across all candidate classes. Therefore, the denominator can be safely omitted during class selection: \[ \text{Predict } C_k = \arg\max_{C_k} \left[ P(C_k) \cdot \prod_{i=1}^n P(X_i \mid C_k) \right] \]
The notation \(\arg\max_{C_k}\) reads "the class \(C_k\) that maximizes the expression inside the brackets." Because we only ever compare classes, the shared denominator cannot change which class wins — dropping it is safe and saves computation.
14.2.5 Worked Computational Example: Play Tennis Dataset
Worked example — full Naive Bayes computation on the Play Tennis dataset. Consider a historical dataset containing 14 total weather observations with four feature columns—Outlook, Temperature, Humidity, and Wind—and one target column, Play Tennis (\(\text{Play} \in \{\text{Yes}, \text{No}\}\)).
Step 0 — read off the class counts and priors. Overall target frequencies across 14 total observations: 9 Yes samples and 5 No samples. The prior probability of Play being Yes is nine out of fourteen: \[ P(\text{Yes}) = \frac{9}{14} \approx 0.6429 \] where \(P(\text{Yes})\) is the prior probability of class Yes. The prior probability of Play being No is five out of fourteen: \[ P(\text{No}) = \frac{5}{14} \approx 0.3571 \] where \(P(\text{No})\) is the prior probability of class No.
We want to predict whether tennis will be played under the following new weather query instance:
- Outlook = Sunny
- Temperature = Cool
- Humidity = High
- Wind = Strong
Step 1 — feature likelihoods given Play = Yes (out of 9 Yes samples). Pivot table feature counts among the 9 Yes instances yield:
| Feature value | Count among Yes (9) | \(P(\cdot \mid \text{Yes})\) |
|---|---|---|
| Sunny | 2 | \(2/9\) |
| Cool | 3 | \(3/9\) |
| High | 3 | \(3/9\) |
| Strong | 3 | \(3/9\) |
- Sunny given Yes occurs 2 times:
\[ P(\text{Sunny} \mid \text{Yes}) = \frac{2}{9} \]
- Cool given Yes occurs 3 times:
\[ P(\text{Cool} \mid \text{Yes}) = \frac{3}{9} \]
- High Humidity given Yes occurs 3 times:
\[ P(\text{High} \mid \text{Yes}) = \frac{3}{9} \]
- Strong Wind given Yes occurs 3 times:
\[ P(\text{Strong} \mid \text{Yes}) = \frac{3}{9} \]
The score for Yes is the product of all conditional feature likelihoods given Yes and the prior probability of Yes: \[ \text{Score}(\text{Yes}) = P(\text{Sunny} \mid \text{Yes}) \cdot P(\text{Cool} \mid \text{Yes}) \cdot P(\text{High} \mid \text{Yes}) \cdot P(\text{Strong} \mid \text{Yes}) \cdot P(\text{Yes}) \] \[ \text{Score}(\text{Yes}) = \left(\frac{2}{9}\right) \cdot \left(\frac{3}{9}\right) \cdot \left(\frac{3}{9}\right) \cdot \left(\frac{3}{9}\right) \cdot \left(\frac{9}{14}\right) \] \[ \text{Score}(\text{Yes}) = \frac{2 \cdot 3 \cdot 3 \cdot 3 \cdot 9}{9 \cdot 9 \cdot 9 \cdot 9 \cdot 14} = \frac{486}{91854} \approx 0.005291 \]
Step 2 — feature likelihoods given Play = No (out of 5 No samples). Pivot table feature counts among the 5 No instances yield:
| Feature value | Count among No (5) | \(P(\cdot \mid \text{No})\) |
|---|---|---|
| Sunny | 3 | \(3/5\) |
| Cool | 1 | \(1/5\) |
| High | 4 | \(4/5\) |
| Strong | 3 | \(3/5\) |
- Sunny given No occurs 3 times:
\[ P(\text{Sunny} \mid \text{No}) = \frac{3}{5} \]
- Cool given No occurs 1 time:
\[ P(\text{Cool} \mid \text{No}) = \frac{1}{5} \]
- High Humidity given No occurs 4 times:
\[ P(\text{High} \mid \text{No}) = \frac{4}{5} \]
- Strong Wind given No occurs 3 times:
\[ P(\text{Strong} \mid \text{No}) = \frac{3}{5} \]
The score for No is the product of all conditional feature likelihoods given No and the prior probability of No: \[ \text{Score}(\text{No}) = P(\text{Sunny} \mid \text{No}) \cdot P(\text{Cool} \mid \text{No}) \cdot P(\text{High} \mid \text{No}) \cdot P(\text{Strong} \mid \text{No}) \cdot P(\text{No}) \] \[ \text{Score}(\text{No}) = \left(\frac{3}{5}\right) \cdot \left(\frac{1}{5}\right) \cdot \left(\frac{4}{5}\right) \cdot \left(\frac{3}{5}\right) \cdot \left(\frac{5}{14}\right) \] \[ \text{Score}(\text{No}) = \frac{3 \cdot 1 \cdot 4 \cdot 3 \cdot 5}{5 \cdot 5 \cdot 5 \cdot 5 \cdot 14} = \frac{180}{8750} \approx 0.020571 \]
Step 3 — comparison and final prediction. Comparing the computed posterior scores: \[ \text{Score}(\text{No}) = 0.020571 > \text{Score}(\text{Yes}) = 0.005291 \]
Because the posterior score for No is significantly higher than that for Yes, the Naive Bayes classifier predicts that Tennis will Not be played (\(\text{Play} = \text{No}\)) under the specified weather conditions.
Sense-check: The query instance is Sunny + Cool + High + Strong — four conditions that are all more common among the 5 No rows than among the 9 Yes rows (Sunny \(3/5 > 2/9\), Cool \(1/5\) vs \(3/9\), High \(4/5 > 3/9\), Strong \(3/5 = 3/9\)). Notice how the larger No likelihoods overwhelm the Yes prior (\(0.6429\)); the evidence outweighs the prior. That is why No wins despite Yes being the more frequent class overall — and it is exactly the kind of intuition to check after any Naive Bayes calculation.
Assumptions & Scope of Naive Bayes:
- Conditional independence: the whole formula rests on \(P(X_1, \dots, X_n \mid C_k) = \prod_i P(X_i \mid C_k)\). If two features are strongly correlated (e.g., Temperature = Cool and Outlook = Rain co-occurring), the product double-counts the shared evidence and the scores become distorted.
- Sufficient data per cell: each \(P(X_i \mid C_k)\) is estimated from counts; with few samples or rare feature values, a single zero count can drive an entire product to zero. (In practice, tools add a small smoothing constant — but the exam questions here use the raw counts.)
- Scope: Naive Bayes is especially strong for text-like, high-dimensional, sparse features (spam filters, sentiment) where independence is a workable approximation and where other classifiers would need far more data.
14.2.6 Student Questions and Answers
Q: Do we need to calculate the denominator when running Naive Bayes classification? A: No. The denominator \(P(X_1, X_2, \dots, X_n)\) represents the marginal probability of observing that specific combination of features. Because that value is identical for both \(P(\text{Yes} \mid \mathbf{X})\) and \(P(\text{No} \mid \mathbf{X})\), it cancels out during relative comparison. Omitted denominators reduce computational overhead without altering the argmax decision — you only ever need the numerator scores to rank the classes.
Pitfalls:
- Forgetting the priors. The full score is likelihoods times the class prior \(P(C_k)\). Dropping the prior turns Naive Bayes into plain likelihood comparison and can flip the answer when classes are imbalanced.
- Using raw counts instead of fractions. Each \(P(X_i \mid C_k)\) must be a probability (count divided by class total), not the raw count itself — otherwise classes with more rows automatically "win."
- Multiplying zero without noticing. A single unseen feature value makes its likelihood \(0\) and collapses the whole product. Note the answer, but check whether a real system would smooth the counts.
- Reading scores as true probabilities. \(0.020571\) and \(0.005291\) are unnormalized scores (denominator omitted), so they do not sum to 1. Only their relative size matters.
Recap + bridge: Naive Bayes predicts a class by multiplying each feature's conditional likelihood given that class with the class prior, then picking the largest score; the naive independence assumption makes those likelihoods cheap to estimate, and the shared denominator is dropped because it cannot change the winner. Next, we meet a completely different strategy — instead of multiplying probabilities, decision trees ask a sequence of yes/no questions that progressively purify the data.
Real-world: Naive Bayes is a workhorse for text classification and sentiment analysis — spam filtering, customer feedback categorization, and document routing — where the "bag of words" features are sparse and near-independent enough for the naive assumption to pay off. The same probability machinery also powers traffic and event forecasting, where conditional distributions estimated from historical data predict urban congestion and operational workload from weather forecasts and calendar events.
14.3 Decision Trees for Classification
Hook — what is the best question to ask first? A doctor deciding whether a patient has heart disease can ask many questions: age, blood pressure, chest-pain type, cholesterol. Asking the wrong first question wastes time; asking the right one splits the patients into groups that are already mostly decided. A Decision Tree is a machine that discovers, straight from the data, which question to ask first, which to ask next, and when to stop and give an answer.
A Decision Tree is a non-parametric supervised learning algorithm that partitions a dataset into progressively purer subsets by creating a flowchart-like tree structure of conditional if-else decisions. "Non-parametric" means it makes no strong assumption about the shape of the data (unlike, say, assuming a straight line) — it simply grows wherever the data leads.
14.3.1 Intuition via Sorted Passenger Discount Data
Intuition — sorting the passengers by age already reveals the tree. Consider a sample dataset of 13 airline passenger records listing passenger age and the corresponding discount percentage awarded:
- Passengers aged 2 to 5 receive a 100% discount.
- Passengers aged 7 to 59 (such as age 45 or 55) receive a 0% discount.
- Passengers aged 63 to 79 (such as age 65) receive a 40% discount.
Sorting the dataset by age reveals clear numerical decision thresholds:
- If \(\text{Age} \le 5 \rightarrow \text{Discount} = 100\%\)
- If \(5 < \text{Age} \le 59 \rightarrow \text{Discount} = 0\%\)
- If \(\text{Age} > 63 \rightarrow \text{Discount} = 40\%\)
Writing manual if-else rules in code is traditional programming, not machine learning — a human wrote those rules by looking at the data. Automatically inspecting raw feature data to discover optimal threshold decision points and building a flowchart tree for future prediction is the essence of decision tree machine learning.
Formalize — the difference between programming and learning. A program is given rules and applies them to data. A decision tree is given data and produces the rules. The learner tries many candidate thresholds (Age ≤ 5? Age ≤ 59? Age ≤ 63?), measures how cleanly each one separates the target classes, and keeps the best. In the passenger example the thresholds 5 and 59 emerge naturally because the discount jumps exactly at those ages — the algorithm discovers them, it is not told them.
14.3.2 Node Purity and Quantitative Impurity Metrics
To construct optimal decision boundaries, a decision tree evaluates candidate feature splits based on node purity — how homogeneous a subset's target labels are. A perfectly pure node contains only one class; a maximally impure node is a 50/50 toss-up.
Consider four bags containing combinations of apples and oranges:
- Bag 1: 5 Apples, 5 Oranges (10 total) \(\rightarrow\) Completely mixed (Maximum Impurity).
- Bag 2: 10 Apples, 20 Oranges (30 total) \(\rightarrow\) Moderately mixed.
- Bag 3: 25 Apples, 25 Oranges (50 total) \(\rightarrow\) Completely mixed (Maximum Impurity).
- Bag 4: 0 Apples, 15 Oranges (15 total) \(\rightarrow\) Completely homogeneous (Completely Pure, 0 Impurity).
Two mathematical metrics quantify impurity across candidate splits. Both are functions of the class proportions \(p_i\) alone — the total count does not matter, only the mix (Bag 1 and Bag 3 have identical impurity because both are 50/50).
1. Gini Index (Gini Impurity)
Formalize — the Gini Index. The Gini Index measures the frequency with which a randomly chosen element from a subset would be incorrectly labeled if randomly classified according to the label distribution. Imagine picking one fruit at random and then guessing its class at random using the node's own proportions: Gini is the chance the guess is wrong.
The Gini index is one minus the sum of squared class probabilities: \[ \text{Gini} = 1 - \sum_{i=1}^k p_i^2 = 1 - p_1^2 - p_2^2 - \dots - p_k^2 \] where \(p_i\) is the proportion or probability of class \(i\) present in the node, and \(k\) is the total number of target classes.
For binary classification, Gini Index ranges from \(0.0\) (completely pure, single class) to \(0.5\) (maximum impurity, 50/50 split).
- Calculation for Bag 1 (5 Apples, 5 Oranges):
\[ \text{Gini} = 1 - \left(\frac{5}{10}\right)^2 - \left(\frac{5}{10}\right)^2 = 1 - 0.25 - 0.25 = 0.50 \]
- Calculation for Bag 4 (0 Apples, 15 Oranges):
\[ \text{Gini} = 1 - \left(\frac{0}{15}\right)^2 - \left(\frac{15}{15}\right)^2 = 1 - 0 - 1 = 0.00 \]
2. Entropy
Formalize — Entropy. Entropy measures the degree of randomness or information disorder within a dataset subset — borrowed from thermodynamics, where entropy is the disorder of a physical system. In a pure node there is no disorder (all one class), so entropy is zero; in a 50/50 node the uncertainty is maximal.
Entropy is the negative sum of class probabilities multiplied by their log base 2: \[ \text{Entropy} = -\sum_{i=1}^k p_i \log_2(p_i) \] where \(p_i\) is the probability of class \(i\), and \(\log_2\) denotes the logarithm base 2.
For binary classification, Entropy ranges from \(0.0\) (completely pure) to \(1.0\) (maximum entropy/disorder).
- Calculation for Bag 1 (5 Apples, 5 Oranges):
\[ \text{Entropy} = -\left[\left(\frac{5}{10}\right)\log_2\left(\frac{5}{10}\right) + \left(\frac{5}{10}\right)\log_2\left(\frac{5}{10}\right)\right] = -\left[0.5(-1) + 0.5(-1)\right] = 1.00 \]
- Calculation for Bag 4 (0 Apples, 15 Oranges):
\[ \text{Entropy} = -\left[0 + \left(\frac{15}{15}\right)\log_2\left(\frac{15}{15}\right)\right] = 0.00 \]
Worked example — both metrics agree on the four bags. Compute Gini and Entropy for all four bags:
| Bag | Apples : Oranges | Gini | Entropy |
|---|---|---|---|
| Bag 1 | 5 : 5 | \(1 - 0.25 - 0.25 = 0.50\) | \(1.00\) |
| Bag 2 | 10 : 20 | \(1 - (1/3)^2 - (2/3)^2 = 1 - 0.111 - 0.444 = 0.444\) | \(-\left[\frac{1}{3}\log_2\frac{1}{3} + \frac{2}{3}\log_2\frac{2}{3}\right] \approx 0.918\) |
| Bag 3 | 25 : 25 | \(0.50\) | \(1.00\) |
| Bag 4 | 0 : 15 | \(0.00\) | \(0.00\) |
Sense-check: Gini reaches its maximum \(0.5\) for the 50/50 bags (1 and 3) regardless of total size, Entropy reaches \(1.0\) there too, and both drop to \(0\) for the pure bag. The two metrics are different numbers but always rank nodes the same way — which is why a tree built with Gini and a tree built with Entropy usually look nearly identical.
Which to use? Gini is cheaper to compute (no logarithms) and is the default in many libraries (including Spark MLlib and scikit-learn's CART). Entropy is more sensitive to small probability differences. For this course both are examinable as single-node calculations.
14.3.3 Evaluating Split Quality via Weighted Impurity
A single node's impurity is not enough — a split produces several child nodes, and the tree must compare whole splits. When a candidate decision rule splits a parent dataset of \(N\) samples into child subsets \(S_1, S_2, \dots, S_m\) containing \(N_1, N_2, \dots, N_m\) samples, the overall effectiveness of the split is determined by its weighted average impurity: \[ \text{Impurity}_{\text{split}} = \sum_{j=1}^m \frac{N_j}{N} \cdot \text{Impurity}(S_j) \] where \(\frac{N_j}{N}\) represents the proportion of samples routed to child node \(S_j\), and \(\text{Impurity}(S_j)\) is the Gini or Entropy value of child node \(S_j\).
The weighting matters: a child holding 70 of the 100 samples contributes far more to the average than a child holding 5. Lower weighted split impurity indicates a superior decision threshold.
Worked example — which split best separates 40 Apples from 60 Oranges? Consider a dataset of 100 fruits containing 40 Apples and 60 Oranges. We evaluate three candidate split decisions:
Candidate Rule 1: Weight > 150g
- Left child node (\(\text{Weight} > 150\text{g}\)): 30 fruits (25 Apples, 5 Oranges).
\[ \text{Gini}_{\text{left}} = 1 - \left(\frac{25}{30}\right)^2 - \left(\frac{5}{30}\right)^2 = 1 - 0.6944 - 0.0278 = 0.2778 \]
- Right child node (\(\text{Weight} \le 150\text{g}\)): 70 fruits (15 Apples, 55 Oranges).
\[ \text{Gini}_{\text{right}} = 1 - \left(\frac{15}{70}\right)^2 - \left(\frac{55}{70}\right)^2 = 1 - 0.0459 - 0.6173 = 0.3367 \]
- Weighted Gini of Split 1:
\[ \text{Gini}_{\text{split1}} = \left(\frac{30}{100}\right)(0.2778) + \left(\frac{70}{100}\right)(0.3367) = 0.0833 + 0.2357 = 0.3190 \approx 0.32 \]
Candidate Rule 2: Weight > 100g
- Left child node (\(\text{Weight} > 100\text{g}\)): 50 fruits (35 Apples, 15 Oranges).
\[ \text{Gini}_{\text{left}} = 1 - \left(\frac{35}{50}\right)^2 - \left(\frac{15}{50}\right)^2 = 1 - 0.49 - 0.09 = 0.4200 \]
- Right child node (\(\text{Weight} \le 100\text{g}\)): 50 fruits (5 Apples, 45 Oranges).
\[ \text{Gini}_{\text{right}} = 1 - \left(\frac{5}{50}\right)^2 - \left(\frac{45}{50}\right)^2 = 1 - 0.01 - 0.81 = 0.1800 \]
- Weighted Gini of Split 2:
\[ \text{Gini}_{\text{split2}} = \left(\frac{50}{100}\right)(0.4200) + \left(\frac{50}{100}\right)(0.1800) = 0.2100 + 0.0900 = 0.3000 \]
Comparing Rule 1 (\(0.32\)) and Rule 2 (\(0.30\)), Rule 2 produces a lower weighted impurity, proving mathematically that Weight > 100g is a better split threshold than Weight > 150g.
Candidate Rule 3: Color == Orange
- Left child node (\(\text{Color} == \text{Orange}\)): 60 fruits (0 Apples, 60 Oranges) \(\rightarrow \text{Gini}_{\text{left}} = 0.00\).
- Right child node (\(\text{Color} \ne \text{Orange}\)): 40 fruits (40 Apples, 0 Oranges) \(\rightarrow \text{Gini}_{\text{right}} = 0.00\).
- Weighted Gini of Split 3:
\[ \text{Gini}_{\text{split3}} = \left(\frac{60}{100}\right)(0.00) + \left(\frac{40}{100}\right)(0.00) = 0.0000 \]
Rule 3 achieves a weighted impurity of \(0.00\), proving mathematically that splitting by Color == Orange creates a perfectly pure classification split.
Sense-check: Rule 3 wins because the color feature happens to divide the data perfectly (all oranges on one side, all apples on the other). Between the two weight rules, Rule 2 wins because its children are more lopsided toward a single class — one child is 70% apples, the other 90% oranges. Lower weighted Gini = cleaner separation = better split.
Scope — the weighted-average view of splitting. The weighted impurity formula is the core of greedy tree learning: at every node, the algorithm tries every candidate feature and threshold, computes each split's weighted impurity, and keeps the minimum. Two caveats worth noting:
- Greedy, not global: the tree optimizes one split at a time, so the best root split does not guarantee the globally best tree — later splits can only work with what earlier splits left behind.
- Perfect splits are rare: real datasets almost never admit a \(0.00\) impurity split, so trees usually stop with small-but-nonzero impurity and use majority vote at the leaves.
14.3.4 Step-by-Step Decision Tree Construction on Play Tennis Dataset
Worked example — building the full Play Tennis tree, one split at a time. We demonstrate full tree construction using the 14-sample Play Tennis dataset (9 Yes, 5 No). The recipe at every node: compute the weighted Gini of each candidate feature's split and pick the smallest.
Step 1 — selecting the root node feature. We compute the weighted Gini impurity for splits generated by each of the four features across all 14 sample observations:
- Outlook Split (3 branches: Overcast [4 samples], Rain [5 samples], Sunny [5 samples]):
- Overcast (0 No, 4 Yes): \(\text{Gini}_{\text{Overcast}} = 1 - (0/4)^2 - (4/4)^2 = 0.00\)
- Rain (2 No, 3 Yes): \(\text{Gini}_{\text{Rain}} = 1 - (2/5)^2 - (3/5)^2 = 1 - 0.16 - 0.36 = 0.48\)
- Sunny (3 No, 2 Yes): \(\text{Gini}_{\text{Sunny}} = 1 - (3/5)^2 - (2/5)^2 = 1 - 0.36 - 0.16 = 0.48\)
- Weighted Gini(Outlook):
\[ \text{Gini}_{\text{Outlook}} = \left(\frac{4}{14}\right)(0.00) + \left(\frac{5}{14}\right)(0.48) + \left(\frac{5}{14}\right)(0.48) = \frac{4.8}{14} \approx 0.3429 \approx 0.34 \]
- Temperature Split (Cool, Hot, Mild): Weighted Gini = \(0.44\)
- Wind Split (Strong, Weak): Weighted Gini = \(0.43\)
- Humidity Split (High, Normal): Weighted Gini = \(0.37\)
Because Outlook achieves the lowest weighted Gini impurity (\(0.34\)), Outlook is selected as the root decision node.
Step 2 — branch construction and child node evaluation.
Branch 1: Outlook = Overcast. The subset routed to Overcast contains 4 Yes and 0 No samples. Because this node is completely pure (\(\text{Gini} = 0.00\)), branching stops immediately and assigns the terminal leaf prediction Play = Yes.
Branch 2: Outlook = Sunny. The subset routed to Sunny contains 5 samples (3 No, 2 Yes), which is impure. We evaluate splits across remaining features (Temperature, Humidity, Wind) on these 5 Sunny samples:
- Temperature split: Weighted Gini = \(0.20\)
- Wind split: Weighted Gini = \(0.40\)
- Humidity split (High [3 No, 0 Yes], Normal [0 No, 2 Yes]):
- High Humidity Gini: \(1 - (3/3)^2 - 0 = 0.00\)
- Normal Humidity Gini: \(1 - 0 - (2/2)^2 = 0.00\)
- Weighted Gini(Humidity \(\mid\) Sunny) = \(0.00\)
Because Humidity yields a perfectly pure split (\(0.00\)), Humidity is chosen for the Sunny branch:
- If \(\text{Humidity} = \text{High} \rightarrow \mathbf{\text{No}}\)
- If \(\text{Humidity} = \text{Normal} \rightarrow \mathbf{\text{Yes}}\)
Branch 3: Outlook = Rain. The subset routed to Rain contains 5 samples (2 No, 3 Yes), which is impure. Evaluating remaining features on these 5 Rain samples:
- Wind split (Strong [2 No, 0 Yes], Weak [0 No, 3 Yes]):
- Strong Wind Gini: \(0.00\)
- Weak Wind Gini: \(0.00\)
- Weighted Gini(Wind \(\mid\) Rain) = \(0.00\)
Because Wind yields a perfectly pure split (\(0.00\)), Wind is chosen for the Rain branch:
- If \(\text{Wind} = \text{Strong} \rightarrow \mathbf{\text{No}}\)
- If \(\text{Wind} = \text{Weak} \rightarrow \mathbf{\text{Yes}}\)
Final constructed decision tree architecture: \[ \text{Root: Outlook?} \] \[ \begin{cases} \text{Overcast} \rightarrow \mathbf{\text{Play = Yes}} \\ \text{Sunny} \rightarrow \text{Humidity?} \begin{cases} \text{High} \rightarrow \mathbf{\text{Play = No}} \\ \text{Normal} \rightarrow \mathbf{\text{Play = Yes}} \end{cases} \\ \text{Rain} \rightarrow \text{Wind?} \begin{cases} \text{Strong} \rightarrow \mathbf{\text{Play = No}} \\ \text{Weak} \rightarrow \mathbf{\text{Play = Yes}} \end{cases} \end{cases} \]
Sense-check: Follow one path end-to-end — a Sunny, Normal-humidity day lands on Play = Yes; a Rainy, Strong-wind day lands on Play = No. Every leaf is 100% pure, so the tree reproduces all 14 training rows perfectly. In this tiny dataset the tree stops at depth 2; on real data the process continues feature by feature until a stopping rule fires.
Visual intuition of the final tree: picture a decision tree drawn with the root at the top. The root node is labeled Outlook with three arrows leaving it: the leftmost arrow (Overcast) points straight down to a green leaf labeled Yes; the middle arrow (Sunny) reaches a node labeled Humidity, whose two arrows end in No (High) and Yes (Normal) leaves; the right arrow (Rain) reaches a node labeled Wind, whose two arrows end in No (Strong) and Yes (Weak) leaves. Reading the picture top-to-bottom is the same as following the if-else rules: each path is one rule, and the whole tree is the complete rule set learned from data.
14.3.5 Tree Depth, Overfitting, and Hyperparameter Tuning
If a decision tree is allowed to grow without constraints on massive datasets containing millions of rows, it will construct thousands of fine-grained branches until every single leaf node is 100% pure. This results in an overfitted tree (metaphorically 100 km long) that memorizes training noise and fails to generalize to new data.
Pitfall — the perfect-training tree that fails in the wild. An unconstrained tree chases 100% training accuracy by carving a unique branch for every stray example, including the noise — a single mislabeled row, an unusual coincidence. That tree looks flawless on the training data (0% error) yet performs badly on new rows, because it memorized accidents instead of learning patterns. This is the classic overfitting failure, and the professor's "100 km long tree" image captures it: a tree deep enough to touch every training row is a tree too tangled to generalize.
To prevent overfitting, practitioners tune key hyperparameters:
- Maximum Tree Depth (
maxDepth): Hard limit on the maximum depth or distance from root to terminal leaf (e.g. limiting tree depth to 20 levels). Depth is the tree's "generation count" — every extra level lets the tree split further, so capping depth caps how finely it can memorize. - Minimum Instances per Node (
minInstancesPerNode): Stopping threshold that halts node splitting if a child subset contains fewer than a specified minimum number of sample records (e.g. 50 samples). When splitting stops early, the terminal leaf prediction is assigned via majority voting (mode) across the remaining samples — a leaf with 100 samples, 80 of them Yes, predicts Yes even though it is not perfectly pure.
Exam note: Expect questions that test the effect of a hyperparameter rather than a long calculation — for example, "what happens if maxDepth is increased?" (deeper, more specialized tree, more overfitting risk) or "what happens if minInstancesPerNode is raised?" (tree stops growing earlier, leaves become fewer and coarser, less overfitting). The trade-off is always the same: complexity versus generalization.
Real-world: In Big Data systems handling datasets with up to 90,000 features and millions of records, single-machine tree construction suffers from memory exhaustion. Distributed computing engines like Apache Spark MLlib split feature evaluation across cluster nodes to construct decision trees efficiently — which is why the tree algorithms in this lecture are discussed alongside Spark throughout the course.
14.3.6 Student Questions and Answers
Q: Do decision trees always split into multi-branch nodes, or can they perform binary splits? A: Decision trees can perform multi-branch splits (e.g. Sunny, Overcast, Rain) or binary splits (e.g. Outlook == Overcast vs Outlook != Overcast). In complex feature spaces, trees can also evaluate compound boolean conditions (such as Outlook == Rain AND Humidity == High). However, evaluating all multi-branch and compound feature combinations dramatically increases computational complexity, requiring distributed frameworks like Apache Spark MLlib. (In practice, many libraries — CART in scikit-learn and Spark — always build binary trees, converting a multi-valued feature into a sequence of binary questions, because binary splits are far cheaper to search over.)
Pitfalls:
- Reading impurity as accuracy. Gini 0.48 on a branch does not mean "48% wrong" — it is an impurity score, not an error rate. Compare splits only through their weighted values.
- Forgetting the weights in weighted impurity. A child holding most of the samples dominates the average; computing plain average impurity instead of weighted average picks the wrong split.
- Letting the tree grow forever. Without
maxDepthorminInstancesPerNode, the tree overfits — perfect on training data, poor on new data. - Confusing majority voting at leaves with bagging. A leaf uses the mode of its own samples; Random Forest (next section) uses the mode across many trees.
Recap + bridge: A decision tree repeatedly splits the data on the feature that minimizes weighted impurity (Gini or Entropy), stops when leaves are pure or hyperparameters say stop, and predicts via leaf majority. The single tree is intuitive but unstable and prone to overfitting — which sets up the natural fix: instead of trusting one tree, build many trees and let them vote. That is Random Forest.
Real-world: Decision trees are prized for credit risk assessment and property price estimation because their if-else structure is explainable — a loan officer can read exactly why an application was rejected, and a regulator can audit the rule. That transparency, plus the ability to run at scale on Apache Spark MLlib, keeps trees at the center of automated risk and pricing valuation systems.
14.4 Random Forest and Bagging
Hook — is one expert better than a hundred ordinary people? Sometimes, no. A single decision tree can be brilliant or can confidently overfit a fluke in the data. Random Forest's answer is to stop betting on one tree and instead ask a crowd of trees — each one slightly different and individually imperfect — and let the crowd's majority decide. The result is one of the most reliable classifiers in practical machine learning.
Random Forest is an ensemble supervised learning algorithm that builds a multitude of independent decision trees during training and merges their predictions to improve accuracy and control overfitting. "Ensemble" means it combines many models instead of relying on one.
14.4.1 Motivation via the KBC Audience Poll Analogy
Professor's analogy — the KBC audience poll lifeline. Consider the audience poll lifeline on the quiz show Kaun Banega Crorepati (KBC). A contestant in the hot seat may possess extensive knowledge but occasionally get stumped by a difficult question.
Instead of relying on a single expert, the contestant polls 100 audience members. Individual audience members are "weak learners" — they lack complete domain expertise and have not read every textbook. Yet when 100 weak learners vote collectively, their aggregated majority decision yields a remarkably reliable correct answer. Individual errors cancel out; the majority is usually right.
Random Forest applies this exact collective principle: it aggregates predictions from hundreds of individually weak decision trees to form a robust, highly accurate ensemble predictor. The individual trees are the audience members — each built on a different random sample of the data — and the final prediction is their vote.
14.4.2 The Bagging (Bootstrap Aggregating) Protocol
Purpose — why bagging? A single unpruned tree has high variance: small changes in the training data produce very different trees. Bagging (short for Bootstrap Aggregating) trains many trees on random variations of the data and averages their opinions, so the random wobble of any one tree is smoothed away by the others. The crowd's variance is far lower than any individual's.
Bagging reduces prediction variance through four systematic steps:
- Row Bootstrapping (Sampling with Replacement): Given an original training set of \(N\) records, create \(B\) distinct bootstrap datasets of size \(N'\) by randomly selecting sample rows with replacement. Certain rows appear multiple times in a bootstrap sample, while others are omitted.
- Column Bootstrapping (Random Feature Subsets): At every split node within each decision tree, randomly select a small subset of features \(m \ll M\) (where \(M\) is the total feature count, such as selecting a fraction out of 90,000 features). The tree is forced to evaluate splits strictly among the chosen candidate features.
- Independent Tree Growth: Train an unpruned decision tree independently on each bootstrap subset using its designated feature subsets.
- Ensemble Aggregation:
- For Classification: Predictions across all \(B\) trees are aggregated using Majority Voting (mode).
\[ \hat{y}_{\text{ensemble}} = \text{mode}\left(\hat{y}_1, \hat{y}_2, \dots, \hat{y}_B\right) \] where \(\hat{y}_b\) is the predicted class label output by tree \(b\).
- For Regression: Predictions across all \(B\) trees are aggregated using Averaging (mean).
\[ \hat{y}_{\text{ensemble}} = \frac{1}{B} \sum_{b=1}^B \hat{y}_b \] where \(\hat{y}_{\text{ensemble}}\) is the final ensemble regression output, and \(\hat{y}_b\) is the continuous prediction from tree \(b\).
Why randomize twice? Row bootstrapping alone makes each tree see a different data sample; column bootstrapping additionally makes each tree consider different features at each split. The second randomization matters because if all trees used the same strongest feature, they would all make the same mistake — the crowd would agree on the wrong answer. Random feature subsets guarantee the trees disagree, and disagreement is what makes the majority vote reliable. This double randomization is the defining trait of Random Forest (bagging alone uses only row bootstrapping).
Inputs & Outputs: Inputs are the labeled training set (with \(N\) rows and \(M\) features) plus hyperparameters \(B\) (number of trees, e.g. 100–200), \(m\) (features tried per split, e.g. \(\sqrt{M}\) for classification), and optional tree limits (maxDepth, minInstancesPerNode). The output is an ensemble model that, at prediction time, runs the input through all \(B\) trees and returns the majority class (classification) or the average (regression).
14.4.3 Worked Computational Walkthrough: 10-Round Bagging Dataset
Worked example — ten bagging rounds on a tiny one-feature dataset. Consider a 1-dimensional continuous feature dataset \(x \in [0.1, 1.0]\) paired with binary target labels \(y \in \{+1, -1\}\):
| \(x\) | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0 |
|---|---|---|---|---|---|---|---|---|---|---|
| \(y\) | +1 | +1 | +1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
The underlying truth is a single threshold near \(x = 0.35\), but each bootstrap sample will estimate it slightly differently. We execute \(B = 10\) bagging rounds to construct 10 independent decision tree classifiers:
Round 1 sample
- Bootstrap sample: \(\{0.1, 0.2, 0.2, 0.3, 0.4, 0.4, 0.5, 0.9, 0.9, 1.0\}\)
- Optimal threshold selected via minimum impurity: \(x \le 0.35\)
- Tree 1 Decision Rule: If \(x \le 0.35 \rightarrow \hat{y}_1 = +1\); else \(\hat{y}_1 = -1\)
Round 2 sample
- Bootstrap sample: \(\{0.1, 0.2, 0.3, 0.4, 0.5, 0.5, 0.9, 1.0, 1.0, 1.0\}\)
- Optimal threshold selected: \(x \le 0.70\)
- Tree 2 Decision Rule: If \(x \le 0.70 \rightarrow \hat{y}_2 = +1\); else \(\hat{y}_2 = -1\)
Round 3 sample
- Bootstrap sample: \(\{0.1, 0.1, 0.3, 0.3, 0.4, 0.6, 0.7, 0.8, 0.9, 1.0\}\)
- Optimal threshold selected: \(x \le 0.35\)
- Tree 3 Decision Rule: If \(x \le 0.35 \rightarrow \hat{y}_3 = +1\); else \(\hat{y}_3 = -1\)
Rounds 4 through 10 independently construct Decision Trees \(T_4\) through \(T_{10}\) following identical bootstrap sampling and threshold optimization procedures.
Ensemble prediction for query input \(x = 0.1\). We pass new input \(x = 0.1\) through all 10 trained decision trees:
- Tree 1 (\(x \le 0.35\)): Predicts \(\hat{y}_1 = +1\)
- Tree 2 (\(x \le 0.70\)): Predicts \(\hat{y}_2 = +1\)
- Tree 3 (\(x \le 0.35\)): Predicts \(\hat{y}_3 = +1\)
- Trees 4 through 10 evaluate \(x = 0.1\) and yield majority predictions of \(+1\).
Aggregating predictions via majority voting: \[ \text{Votes for } +1: 9 \quad \vert \quad \text{Votes for } -1: 1 \] \[ \hat{y}_{\text{ensemble}} = \arg\max(+1, -1) = +1 \]
The ensemble outputs a predicted class label of \(+1\).
Sense-check: The individual trees disagreed about the exact threshold (0.35 vs 0.70), yet for \(x = 0.1\) they agree unanimously — it is far below every threshold, so all 10 predict \(+1\). The 9 : 1 vote tally reflects that one tree drew a bootstrap sample heavy enough in negative rows to shift its threshold. Because \(x = 0.1\) is genuinely a \(+1\) point in the original data, the ensemble's majority is the correct answer — and this is precisely why the crowd beats any single noisy tree.
14.4.4 Distributed Random Forest in Apache Spark MLlib
Building hundreds of decision trees over massive datasets with 90,000 features and millions of rows is computationally impossible on a single machine — even one tree exhausts a single machine's memory.
Apache Spark MLlib distributes Random Forest training across a cluster:
- Parallel Tree Construction: Bootstrap datasets and feature subsets are dispatched to separate worker nodes across a cluster (e.g. 64-core worker nodes), allowing dozens of decision trees to be trained simultaneously in parallel. Each worker grows whole trees (or large sub-trees) on its own slice of the data, so the wall-clock time scales with the cluster rather than with the number of trees.
- Model Orchestration: The Spark driver node aggregates individual decision tree parameters, manages pipeline transformers/estimators, and coordinates fast parallelized majority voting during inference — feeding each query row to all trees in parallel and tallying the votes.
Scope — when is Random Forest the right tool? Random Forest shines on wide, messy, high-dimensional data: it handles continuous, categorical, and text predictors together, captures conditional and non-linear relationships, and stays fast even above 10 million rows when run on a cluster. It is less attractive when you need a single human-readable rule (a lone decision tree is more transparent) or when the dataset is tiny (the ensemble's variance reduction has little to gain). The textbook also notes that Naive Bayes remains more suitable for text-dominated variables, where its simplicity and speed are hard to beat.
14.4.5 Student Questions and Answers
Q: Does the number of bootstrap sets in bagging need to be an odd number to avoid tied votes? A: Not necessarily. While an odd number of trees guarantees no tie when choosing between two binary classes (\(K = 2\)), multi-class problems (\(K \ge 3\)) can still experience tied vote counts even with an odd number of trees. In practice, Random Forests use large tree counts (such as 100 or 200 trees), making exact ties extremely rare; any residual tie is broken randomly or by selecting the class with higher overall prior probability.
Pitfalls:
- Expecting every tree to be good. The magic is in the aggregation; individual trees are intentionally weak and noisy. Judging a Random Forest by any single tree's accuracy misses the point.
- Using too few trees. A forest of 5 trees can still be swayed by bad draws; 100–200 trees is the standard safety margin, and more trees only cost training time, not accuracy.
- Forgetting the column randomization. Row bootstrapping alone is bagging, not Random Forest — without random feature subsets the trees correlate and the majority vote loses its corrective power.
- Reading the vote count as a confidence percentage. \(9 : 1\) does not mean "90% confidence"; the trees are correlated and share biases, so vote margins are not calibrated probabilities.
Recap + bridge: Random Forest = bagging + random feature subsets + many unpruned trees; classification aggregates by majority vote, regression by averaging, and the whole procedure parallelizes naturally on Spark MLlib. This closes the three-algorithm arc of the lecture — Naive Bayes (probabilistic counting), Decision Trees (greedy impurity splitting), and Random Forest (a crowd of trees) — all supervised classifiers with different strategies for turning labeled history into predictions.
Real-world: Random Forest is the go-to model for high-dimensional industrial analytics — training on datasets exceeding 90,000 features and millions of rows with Apache Spark MLlib distributed clusters. It powers credit-risk scoring, fraud detection, churn prediction, and the same automated valuation systems introduced at the start of the lecture, where robustness across noisy, wide feature sets matters more than a single explainable tree.
Exam Guidance Summary
Exam note: The following guidelines summarize examination policies, question formats, and preparation advice:
- Syllabus Coverage:
- Regular Semester Examinations cover Naive Bayes, Decision Trees (Classification), and Random Forest.
- The upcoming extra session covering Apache Spark MLlib, Cassandra, and Recommendation Algorithms is excluded from the regular exam syllabus.
- For students taking makeup examinations, all material covered in the extra sessions (including Spark MLlib and Cassandra) is included in the exam scope.
- Exam Rules and Restricted Tools:
- Assessments are conducted using a locked Safe Browser environment.
- Reference materials are strictly restricted to provided PDFs and PPT slides.
- Microsoft Excel is strictly prohibited per university examination regulations. Standard scientific calculators are permitted as specified.
- Pruned Question Patterns:
- Because students cannot use Excel to perform multi-step table calculations during timed exams, complex calculation questions will be pruned.
- Expect focused questions such as:
- Computing Gini Index or Entropy for a single given node split.
- Selecting the optimal root feature given pre-calculated weighted split impurities.
- Calculating Naive Bayes posterior numerator scores for a given test query.
- Identifying hyperparameter effects (such as max tree depth or min instances per leaf).
How to prepare for each pattern:
- Gini / Entropy for one node: write the class proportions \(p_i\), square them (Gini) or take \(-\sum p_i \log_2 p_i\) (Entropy), and sanity-check the range — binary Gini in \([0, 0.5]\), binary Entropy in \([0, 1]\).
- Optimal root feature: compare only the weighted split impurities (\(\sum \frac{N_j}{N} \cdot \text{Impurity}(S_j)\)) and pick the smallest; never compare raw child impurities.
- Naive Bayes numerator scores: multiply the prior \(P(C_k)\) by each feature likelihood \(P(X_i \mid C_k)\); the denominator cancels, so only the numerator products are needed — and always state which class wins.
- Hyperparameter effects: memorize the direction of each knob — larger
maxDepth→ deeper, more overfit tree; largerminInstancesPerNode→ earlier stopping, coarser leaves, less overfitting.
Key Industry Applications
Real-world: The algorithms covered in this lecture support core industry analytics systems:
- High-Dimensional Big Data Analytics: Training Random Forest models on industrial datasets exceeding 90,000 features and millions of rows using Apache Spark MLlib distributed clusters — the ensemble's parallel tree construction makes it the practical choice when a single machine cannot even hold one tree.
- Text Classification and Sentiment Analysis: Deploying Naive Bayes classifiers for real-world spam filtering, customer feedback classification, and document categorizing — the naive independence assumption is a workable approximation for bag-of-words features and keeps training fast on millions of documents.
- Predictive Traffic and Event Forecasting: Modeling conditional probability distributions to predict urban traffic density and operational workload based on weather forecasts and calendar events — the same conditional-probability machinery that predicted Sunday traffic from four weeks of history.
- Automated Risk and Pricing Valuation: Utilizing decision tree models in real estate and financial services for automated credit risk assessment and property price estimation — tree structure keeps the model explainable to regulators and loan officers while remaining accurate at scale.
The through-line: each algorithm in this lecture earns its industry role from its core strength — Naive Bayes from cheap probabilistic counting over sparse text features, Decision Trees from explainable if-else rules, and Random Forest from crowdsourced robustness that scales across a Spark cluster. Choosing the right one for a real problem means matching that strength to the data's shape and the stakeholder's need for transparency.
BDA Lecture 14 notes
Sections Breakdown
Defines supervised learning on labeled data, the classification vs. regression fork, and the contrast with unsupervised learning.
Builds Naive Bayes from Bayes' theorem, the naive independence assumption, and a fully worked Play Tennis posterior computation.
Covers node purity with Gini and Entropy, weighted split impurity, full Play Tennis tree construction, and overfitting via hyperparameters.
Explains bagging with row and column bootstrapping, a 10-round majority-vote walkthrough, and distributed training on Spark MLlib.
Examination scope, restricted tools, pruned question patterns, and preparation strategies for each expected question type.
Real-world deployments of Random Forest, Naive Bayes, decision trees, and conditional-probability forecasting at scale.
Exam Revision Notes
Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.
14.1 Supervised Learning Overview and Foundations
Must-know: Supervised learning learns a mapping from features to a known target label using labeled historical data; classification has a discrete categorical target (Yes/No, Class 1..k) while regression has a continuous numeric target (price, value). Unsupervised learning (k-means, hierarchical) has no labels and discovers structure. Regular exams cover Naive Bayes, Decision Trees, Random Forest; regression trees and linear regression are self-study/makeup.
⚠️ Top pitfall: Treating an ordinal code like Class 1, 2, 3 as a continuous number; thinking clustering is supervised; ignoring label quality.
Self-check: Is predicting house price (continuous dollars) classification or regression, and why?
Connects to: Naive Bayes Classifier, Decision Trees for Classification, Random Forest and Bagging
14.2 Naive Bayes Classifier
Must-know: Naive Bayes computes, for each class C_k, the unnormalized score P(C_k) * product of P(X_i | C_k) and predicts argmax. The denominator is identical across classes and is dropped. Priors come from class frequencies (9/14 Yes, 5/14 No); likelihoods come from per-class pivot counts. Given (Sunny, Cool, High, Strong), Score(No)=0.020571 > Score(Yes)=0.005291, so Play = No.
\[\text{Predict } C_k = \arg\max_{C_k} \left[ P(C_k) \cdot \prod_{i=1}^n P(X_i \mid C_k) \right]\]
⚠️ Top pitfall: Forgetting the class prior; using raw counts instead of fractions; a single zero likelihood collapsing the whole product; reading unnormalized scores as true probabilities.
Self-check: For the query (Sunny, Cool, High, Strong), which class wins and why does the Yes prior not save the Yes class?
Connects to: Supervised Learning Overview and Foundations, Decision Trees for Classification, Random Forest and Bagging
14.3 Decision Trees for Classification
Must-know: A decision tree greedily picks the split with lowest weighted impurity (Gini = 1 - sum p_i^2, or Entropy = -sum p_i log2 p_i), weighting each child by N_j/N. On Play Tennis, Outlook (0.34) beats Temperature (0.44), Wind (0.43), Humidity (0.37) as root; Sunny branch splits on Humidity (pure), Rain branch on Wind (pure); Overcast is a pure Yes leaf. Unconstrained growth overfits; maxDepth and minInstancesPerNode stop it.
\[\text{Impurity}_{\text{split}} = \sum_{j=1}^m \frac{N_j}{N} \cdot \text{Impurity}(S_j)\]
⚠️ Top pitfall: Reading Gini 0.48 as 48% error; forgetting to weight children by sample proportion; letting the tree grow until every leaf is pure and memorizing noise (overfitting); confusing leaf majority voting with bagging.
Self-check: Which feature becomes the root of the Play Tennis tree and what is its weighted Gini?
Connects to: Supervised Learning Overview and Foundations, Naive Bayes Classifier, Random Forest and Bagging
14.4 Random Forest and Bagging
Must-know: Random Forest trains B unpruned trees, each on a bootstrap sample (rows drawn with replacement) and with random feature subsets per split, then predicts by majority vote (mode) for classification or mean for regression. In the 10-round walkthrough, query x = 0.1 gets 9 votes for +1 and 1 for -1, so the ensemble predicts +1. Odd tree counts avoid binary ties but not multi-class ties; large counts (100-200) make ties negligible.
\[\hat{y}_{\text{ensemble}} = \text{mode}\left(\hat{y}_1, \hat{y}_2, \dots, \hat{y}_B\right)\]
⚠️ Top pitfall: Judging the forest by a single tree; using too few trees; forgetting the random feature subsets (that is bagging, not Random Forest); reading vote margins as calibrated confidence.
Self-check: Why does the query x = 0.1 receive 9 votes for +1 even though only one threshold was 0.35?
Connects to: Supervised Learning Overview and Foundations, Naive Bayes Classifier, Decision Trees for Classification
Exam Guidance Summary
Must-know: Exam scope: Naive Bayes, Decision Trees (classification), Random Forest (makeup exams also include the extra-session material). Excel is prohibited; scientific calculators are allowed. Expect single-node Gini/Entropy computations, root-feature choice from weighted impurities, Naive Bayes numerator scores, and hyperparameter effect questions.
⚠️ Top pitfall: Preparing for long multi-step table calculations that will be pruned from the exam because Excel is banned; studying excluded extra-session topics for the regular exam.
Self-check: Which topics are excluded from the regular exam but included for makeup exams?
Connects to: Supervised Learning Overview and Foundations, Naive Bayes Classifier, Decision Trees for Classification, Random Forest and Bagging
Key Industry Applications
Must-know: Each algorithm maps to a named industry role: Random Forest (high-dimensional Spark MLlib analytics), Naive Bayes (text/spam/sentiment), conditional probability (traffic and event forecasting), decision trees (explainable risk and pricing valuation).
⚠️ Top pitfall: Learning the algorithms without a real-world anchor; the applications section shows why each design choice exists and when to pick which model.
Self-check: Why is a decision tree preferred over a Random Forest in regulated credit decisions?
Connects to: Supervised Learning Overview and Foundations, Naive Bayes Classifier, Decision Trees for Classification, Random Forest and Bagging