Machine Learning

Ensemble Learning, Gradient Boosting, and Introduction to Unsupervised Learning

📅 Published: 2026-06-29

🎓 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

Ensemble Learning — covered in Lecture 13
Ensemble Methods — covered in Lecture 14
Unsupervised Learning — covered in Lecture 1
Clustering — covered in Lecture 1

Ensemble Learning: Gradient Boosting, XGBoost, and Introduction to Unsupervised Learning

15.1 Ensemble Learning Recap

Hook: Why trust one model when you can ask a roomful of models to vote? A committee of experts makes fewer blunders than any single expert — ensemble learning borrows this idea from everyday decision-making.

Intuition + Analogy: Think of a medical diagnosis panel. One doctor might misread a symptom. But if five doctors examine you independently and four say "flu" while one says "cold," the majority vote tilts toward the right answer. Each doctor (weak learner) needs to be only slightly better than guessing. Their collective judgment (strong learner) is far more accurate. The analogy breaks when doctors collude — just as correlated models don't help ensembles. Independence among base learners is what makes the committee work.

15.1.1 What Has Been Studied So Far

The ensemble learning framework has been covered in depth in previous sessions. Here is a summary:

Ensemble learning means combining multiple models — a committee of models — to produce one strong predictor. The core question is how to combine the results of base learners (weak learners).

Combination strategies studied: voting, averaging, and weighted combining.

Types of ensemble methods covered: - Bootstrap aggregating (bagging): trains each model on a random bootstrap sample. Models built in parallel. - Random forest: bagging variant that also randomly selects a subset of features at each split. - Boosting: models built sequentially. Each new model focuses on errors of the previous one.

15.1.2 AdaBoost Review

AdaBoost (Adaptive Boosting) is a sequential boosting algorithm.

Round 1: Randomly choose a subset of records (e.g., 10). Train first weak learner, compute predictions.

Between rounds: Increase the weight of wrongly predicted records. Decrease weight of correctly predicted ones.

Round 2: Choose another random subset. Train second weak learner focused on previously mispredicted records.

Repeat until errors reduce.

Two versions exist: 1. Version 1: Uses bootstrapping at each round with weighted combination. 2. Version 2: No bootstrapping — all records used every round, but weights are adjusted.

Q: Is AdaBoost parallel or sequential?

A: It is sequential. The first weak learner predicts, the second works on the outcome of the first prediction, and so on. Several students asked this — the parallel/sequential distinction is the most commonly confused point in ensemble methods.

15.1.3 Weak Learner Definition

A weak learner is a model just slightly better than random guessing. Random guessing gives 50-50 chance for binary classification. Each weak learner must have accuracy strictly greater than 0.5. This is critical.

Pitfall: A model with exactly 50% accuracy is NOT a weak learner — it's a random guesser. The mathematical guarantee of boosting (that it can convert weak learners into a strong learner) requires each base model to beat random chance, even if only by a tiny margin. If your base model cannot clear the 0.5 bar, boosting will fail.

The goal of ensemble learning: combine many weak learners into one strong predictive model.

Recap: Ensemble methods combine multiple weak models. Bagging builds in parallel (reducing variance); boosting builds sequentially (reducing bias). AdaBoost tweaks data weights between rounds. Next, gradient boosting upgrades this by optimizing the model function itself.

Real-world connection: Bagging's most famous application is the random forest, used everywhere from credit scoring to medical diagnosis. AdaBoost was the first boosting algorithm to achieve widespread success — it powered early face detection systems (Viola-Jones, 2001) that ran in real time on consumer cameras.

15.2 Gradient Boosting

Hook: What if instead of tweaking knobs on a single model, you could add a new model that fixes exactly what the previous ones got wrong? That is gradient boosting — it grows a forest one tree at a time, each tree undoing the last one's mistakes.

Intuition + Analogy: You are paying off a loan. Instead of trying to pay the whole amount in one impossible lump sum, you pay what you can each month. Month 1: you pay part of the balance. The remaining balance is what you still owe. Month 2: you pay toward the remaining balance — not the original total. Each payment reduces the outstanding amount. Gradient boosting works the same way: each model chisels away at the remaining error (the residual), not at the original target. The analogy breaks in one place: unlike fixed monthly payments, each model in gradient boosting is freshly trained on the current residuals and can adapt its "payment strategy."

15.2.1 The Core Idea

Gradient boosting is an ensemble method where weak learners are added sequentially. The key difference from AdaBoost is what is being optimized.

AdaBoost tweaks numerical parameters (record weights) to reduce error. It lacks a formal mathematical theory behind its weight-update rule.

Gradient boosting does not tweak parameters of a single model. Instead it optimizes the entire model function by adding new weak learners sequentially:

Optimize a cost function over function space by iteratively choosing a function that points in the negative gradient direction.

Standard optimization: tweak weights to reduce error.

Gradient boosting: add new functions (new weak learners) to the ensemble. Each new model is trained to fix the residual error of the previous ensemble.

15.2.2 The Negative Gradient Direction

Think of the loss surface as a hill. The "hill" represents model error. The bottom of the hill is minimum error.

In gradient descent, we walk toward the steepest point — the bottom. The negative gradient direction is the direction of steepest descent — the fastest way to the bottom.

The algorithm calculates the gradient of the error, which is the residual — the difference between actual and predicted. Each new weak learner is trained to predict this residual, fixing a specific part of the error.

15.2.3 Symbol Registry — Gradient Boosting

Symbol	Meaning	LaTeX	Type/Domain
$y$	actual target value	$y$	scalar
$y^$	predicted value	$y^$	scalar
$y - y^$	residual (gradient of error)	$y - y^$	scalar
$F_{1} (x)$	first weak learner prediction	$F_{1} (x)$	function
$F_{2} (x)$	second weak learner (predicts residual)	$F_{2} (x)$	function
$η$	learning rate (shrinkage)	$η$	scalar in $(0, 1)$
$F_{m} (x)$	the $m$ -th weak learner	$F_{m} (x)$	function
$N$	number of training records	$N$	integer

15.2.4 Worked Example: The Golf Analogy

Imagine playing golf. The hole is 10 meters away.

Shot 1 (Model 1): Aim for the hole at 10 meters. Ball goes 6 meters. - Residual = actual − predicted = $10 - 6 = 4$ meters. - You are 4 meters short.

Shot 2 (Model 2): In gradient boosting, the second model does NOT aim for the original target of 10 meters. You stand at 6 meters. Your new aim is to cover the remaining distance — the residual of 4 meters.

Suppose shot 2 goes 3 meters: - Final prediction = $6 + 3 = 9$ meters. - New residual = $10 - 9 = 1$ meter.

Add a third model to predict the remaining 1 meter, and continue until the residual is tiny.

Key insight: Each sequential model does not try to predict the original target. It predicts the error of the previous ensemble. The final prediction is the sum:

$y^_{final} = F_{1} (x) + F_{2} (x) + F_{3} (x) + \dots$

Sense-check: After three shots, the ball is 9 meters out — close to the 10-meter hole. The residual shrank from 10 → 4 → 1, confirming the process converges.

15.2.5 Why the Name "Gradient Boosting"

The standard loss function for regression is mean squared error (MSE):

$MSE = (y - y^)^{2}$

Take the derivative of MSE with respect to prediction $y^$ :

$\frac{\partial}{\partial y ^} (y - y^)^{2} = - 2 (y - y^)$

Ignoring the constant factor $- 2$ , the derivative is proportional to $y - y^$ — exactly the residual.

Moving your prediction by the value of the residual is equivalent to moving down the slope of the error curve. You reduce the gradient (the residual) at each step. Hence gradient boosting.

More formally: for any differentiable loss function $L (y, y^)$ , we fit each new weak learner to the negative gradient of the loss with respect to the current prediction:

$r_{im} = - [\frac{\partial L ( y _{i} , F ( x _{i} ))}{\partial F ( x _{i} )}]_{F = F_{m - 1}}$

For squared-error loss $L = \frac{1}{2} (y - F)^{2}$ , this reduces to $r_{im} = y_{i} - F_{m - 1} (x_{i})$ — the ordinary residual. The framework generalizes: for classification with log-loss, the negative gradient produces "pseudo-residuals" that are not simple differences but probability adjustments.

15.2.6 Worked Example: House Price Prediction

Predict house prices. You have columns: size, number of rooms, etc. Five records with known prices.

Step 1 — Dumb initial prediction: With no model, predict the average price across all records. Suppose average = 200K. Every record gets prediction = 200K.

Step 2 — Calculate residuals: - House A: actual = 250K, predicted = 200K → residual = $+ 50$ K - House B: actual = 180K, predicted = 200K → residual = $- 20$ K

Step 3 — Train a weak learner to predict residuals: Build a decision tree whose target is these residuals, NOT the actual house prices.

Suppose the second model predicts 45K for House A (true residual was 50K).

Step 4 — Compute new prediction with learning rate $η$ :

$y^_{new} = y^_{old} + η \cdot (prediction of second model)$

For House A with $η = 0.1$ : $y^_{new} = 200 K + 0.1 \times 45 K = 204.5 K$

For House B, if second model predicts $- 15$ K: $y^_{new} = 200 K + 0.1 \times (- 15 K) = 198.5 K$

The process repeats: calculate new residuals, train another model to predict those, update predictions.

Sense-check: House A's prediction moved from 200K → 204.5K toward the true 250K. The step was conservative (only 10% of the correction) because of the small learning rate — deliberate, to avoid overfitting.

15.2.7 Mathematical Formulation

Given training data $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})$ , we fit a model $F (x)$ that minimizes squared loss.

If $F (x)$ is not perfect, we add a correction model $h (x)$ :

$F_{new} (x) = F (x) + h (x)$

$h (x)$ compensates for shortcomings of $F (x)$ . The residual for each data point:

$residual_{i} = y_{i} - F (x_{i})$

$h (x)$ is trained to predict these residuals. If $F (x) + h (x)$ is still unsatisfactory, we add another regression tree, and so on.

The general gradient boosting update at iteration $m$ is:

$F_{m} (x) = F_{m - 1} (x) + η \cdot h_{m} (x)$

where $h_{m} (x)$ is the weak learner trained on the pseudo-residuals of $F_{m - 1}$ , and $η$ is the learning rate.

15.2.8 Worked Example: Height, Age, Gender → Weight

Input variables: height, age, gender. Output: weight.

Step 1 — Dumb model (average): Compute average weight of all samples. Say average = 71.2 kg. Every record gets this prediction.

Step 2 — First residuals: For each record: $residual = actual weight - 71.2$

Step 3 — Train a decision stump: A decision stump is a decision tree with minimal depth (one root node or very shallow tree). It is built to predict the residuals using height, age, and gender.

Why decision trees? Most ensemble methods use decision trees as weak learners because trees handle non-linear data effectively. For bagging, any model works; for boosting (sequential), trees are predominant.

Step 4 — Decision tree predictions (illustrative leaf values): - Gender: Male, Height > 5.5 → leaf prediction = 3.8 - Gender: Male, Height ≤ 5.5, Age > 25 → leaf prediction = $16.8$ - Gender: Male, Height ≤ 5.5, Age ≤ 20 → leaf prediction = $- 5.2$ - Gender: Female → leaf prediction = $- 14.2$

These are called pseudo residuals. In an exam, these tree-prediction values would be given. When multiple records fall into the same leaf, the prediction is their average (leaf weight averaging).

Step 5 — Updated prediction with $η = 0.1$ :

For a record in the $16.8$ leaf: $y^= 71.2 + 0.1 \times 16.8 = 72.88$

For a record in the $- 5.2$ leaf: $y^= 71.2 + 0.1 \times (- 5.2) = 70.68$

Step 6 — Pseudo residuals (iteration 2): Compute new residuals. Example: actual = 88, predicted = 72.9 → residual = 15.1.

If residuals are still large, add a third decision tree to predict these new residuals.

Step 7 — Third model prediction: Values like 4.7, −12.8, 3.4, 15.1. Update:

$y^= 71.2 + 0.1 \times (model_{2}) + 0.1 \times (model_{3})$

For a record with model₂ = 16.8 and model₃ = 15.1: $y^= 71.2 + 1.68 + 1.51 = 74.39$

Sense-check: The prediction for this record climbed from 71.2 → 72.88 → 74.39, approaching the true value of 88. The residuals are shrinking across iterations, confirming convergence. With more trees, the prediction would get closer to 88.

Key observation: Check if residuals are reducing across iterations. The values should converge toward zero.

Stopping: Add models until error is small, or set max models in advance (n_estimators parameter, e.g., 50 or 100), or set an error threshold.

15.2.9 The Learning Rate $η$

The learning rate $η$ (shrinkage) scales down each new model's contribution:

$y^_{new} = y^_{previous} + η \cdot (new model prediction)$

Purpose: Prevent overfitting. Without it, each model fully corrects previous error in one step, causing overfitting.

Effect of different rates: - $η$ too large (near 1): very fast learning, large steps. Risk of skipping the minimum, oscillations, overfitting. - $η$ too small (below 0.05): very slow learning, tiny steps. May never converge in reasonable iterations. - $η$ medium (0.05 to 0.2): balanced. Common default $η = 0.1$ .

Think of walking down a hill: large steps jump over the valley; tiny steps inch endlessly; medium steps give steady descent.

Pitfall — $η$ and $M$ trade-off: A smaller learning rate almost always improves generalization but requires more trees (larger $M$ ). The two hyperparameters are coupled: $η = 0.01$ with $M = 500$ trees may give the same training error as $η = 0.1$ with $M = 50$ , but the small- $η$ model usually generalizes better. In practice, set $η$ small (0.01–0.05) and use early stopping (via a validation set) to choose $M$ .

Q: Is there a rule for picking the learning rate?

A: No hard mathematical rule. Chosen from experience. Typically 0.05 to 0.2, with 0.1 as a common default. Several students asked this — the learning rate is the most frequently tuned hyperparameter.

Q: Can oscillations happen with wrong learning rates?

A: Yes. With large rates, predictions may overshoot, then overshoot back, causing oscillations around the minimum. This is analogous to a pendulum swinging past the bottom and back — the system wastes iterations correcting its own overcorrections.

15.2.10 Decision Trees and Non-Linearity

Q: Why use decision trees as weak learners in gradient boosting?

A: Decision trees handle non-linear data very effectively. Most ensemble methods naturally pair with trees. Bagging can use any model; boosting predominantly uses decision trees. Trees also produce the piecewise-constant predictions that work well as additive correction terms — each tree contributes a small, localized adjustment.

Q: Does a decision tree always split strictly into yes/no?

A: Yes. Standard decision trees categorize records into one branch or the other — no in-between. Gaussian Mixture Models (later in this lecture) handle the "in-between" case via soft clustering.

15.2.11 Summary: Gradient Boosting

Recap: Gradient boosting is a sequential ensemble method. The first model predicts the target (or uses a dumb average). Each subsequent model predicts the residuals of the previous ensemble. The final prediction is the sum of all model contributions, each scaled by a learning rate $η$ . The name comes from the fact that residuals are the negative gradient of squared-error loss — each step moves down the error surface.

Bridge: The theoretical framework is powerful, but raw implementations are slow. Next, we look at XGBoost — the optimized implementation that dominates Kaggle competitions.

Scope & Assumptions: - Gradient boosting assumes the loss function is differentiable (so we can compute gradients). Squared error for regression and log-loss for classification are standard choices. - It assumes weak learners (trees) can be trained to predict residuals — the tree must be able to fit the residual signal, however small. - The additive structure assumes each new tree contributes independently. With large $η$ or highly correlated trees, this assumption breaks and overfitting occurs. - Gradient boosting works best with structured/tabular data. For images or text, deep learning methods (CNNs, transformers) typically outperform boosting.

Visual intuition: Imagine a 3D error surface shaped like a bowl. Your current ensemble prediction is a point on the rim. The residual is the arrow pointing downhill from that point. Each new tree takes a small step along that arrow. With enough trees, you walk to the bottom of the bowl — the minimum error. The learning rate controls your step size.

Real-world & domain connection: Gradient boosting powers most winning solutions in tabular-data competitions on Kaggle. Beyond competitions, it is used in credit scoring (predicting loan defaults), insurance pricing (claim frequency models), e-commerce recommendation (predicting purchase likelihood), and anomaly detection in finance. Its ability to handle mixed data types (numeric + categorical) and missing values with minimal preprocessing makes it the go-to algorithm for structured data problems in industry. Friedman's 2001 paper "Greedy Function Approximation: A Gradient Boosting Machine" established the general framework that all modern implementations build on.

15.3 XGBoost and Variants

Hook: Gradient boosting is a brilliant idea. But the naive implementation is painfully slow. XGBoost takes the same mathematics and makes it scream — it is the reason gradient boosting dominates every structured-data competition on Kaggle.

15.3.1 Gradient Boosting vs. XGBoost

Gradient boosting is the theoretical framework — the mathematical concept of fitting new models to residuals.

XGBoost (Extreme Gradient Boosting) is the optimized software implementation of that framework, created by Tianqi Chen (2014, 2016).

Comparison — Gradient Boosting vs. XGBoost:

Aspect	Basic Gradient Boosting	XGBoost
Regularization	None built-in	L1 and L2 regularization
Tree building	Fully sequential	Nodes within a tree built in parallel
Tree pruning	Greedy (stop early)	Depth-first: grow deep, then prune
Large datasets	Fits in memory only	Out-of-core computing
Cross-validation	Manual	Built-in after each iteration
Speed on large data	Slow	Fast (parallelized, optimized C++)

When to pick which: There is essentially no reason to use raw gradient boosting over XGBoost for tabular data. The basic version exists for teaching the concept; XGBoost is the production tool.

15.3.2 XGBoost Optimizations

XGBoost uses gradient boosting plus:

Regularization: L1 (Lasso) and L2 (Ridge) penalty terms are added to the objective function. Basic gradient boosting has no built-in regularization — it relies solely on the learning rate and early stopping to prevent overfitting. XGBoost's regularized objective:

$Obj = i = 1 \sum N L (y_{i}, y^_{i}) + m = 1 \sum M Ω (f_{m})$

where $Ω (f_{m}) = γ T + \frac{1}{2} λ ∥ w ∥^{2}$ penalizes both the number of leaves $T$ and the leaf weights $w$ .

Parallel tree building: The boosting process is sequential (model after model), but nodes within each tree are built in parallel. Finding the best split for each feature can be done simultaneously across CPU cores.
Depth-first search (DFS) for tree pruning: Standard trees use a greedy approach — stop splitting when loss reduction is negative or minimal. XGBoost uses DFS: grows the tree deep first to a max_depth limit, then prunes backward, removing splits that give negative gain. This "grow first, prune later" strategy often finds better tree structures.
Out-of-core computing: Handles datasets larger than RAM by compressing data and streaming from disk in blocks.
Inbuilt cross-validation: Tracks model performance on a validation set after each boosting round. Helps decide when to stop adding trees (early stopping).

Real-world: XGBoost dominates Kaggle competitions due to these speed and accuracy advantages. Of 29 winning solutions in Kaggle competitions in 2015, 17 used XGBoost.

15.3.3 scikit-learn vs. XGBoost

Pitfall: scikit-learn has GradientBoostingRegressor and GradientBoostingClassifier. They are very slow for large models because tree building is fully sequential and implemented in pure Python/Cython with no parallel node construction. Nearly all practitioners use XGBoost, LightGBM, or CatBoost instead of scikit-learn's native gradient boosting for real work.

15.3.4 LightGBM

LightGBM (Light Gradient Boosting Machine, Microsoft, 2017) is another optimized gradient boosting implementation. Its key innovation is Gradient-based One-Side Sampling (GOSS) — it keeps data points with large gradients (hard-to-predict points) and randomly samples points with small gradients. This makes it even faster and more memory-efficient than XGBoost for certain data types, especially high-dimensional sparse data.

15.3.5 CatBoost

CatBoost (Categorical Boosting, Yandex, 2017) handles categorical (text) data automatically using ordered target encoding — no separate one-hot encoding, label encoding, or preprocessing needed. It also uses ordered boosting to reduce overfitting from the standard residual computation. The name comes from "categorical."

Comparison summary:

Library	Creator	Year	Key Strength
XGBoost	Tianqi Chen	2014	Best all-around, regularization
LightGBM	Microsoft	2017	Fastest on large/high-dim data
CatBoost	Yandex	2017	Best with categorical features

Recap: Gradient boosting is the math; XGBoost, LightGBM, and CatBoost are the implementations. Pick based on your data: many categorical columns → CatBoost; huge sparse data → LightGBM; otherwise → XGBoost.

Bridge: All these algorithms — gradient boosting included — are supervised methods. They need labeled data. Next, we shift to the other half of machine learning: what happens when you have no labels at all.

15.3.6 Exam Context

Exam note: For ensemble learning exam problems, model predictions will be given. You compute combined predictions and residuals. You will not be asked to compute decision tree splits using entropy/Gini from scratch. You will not need to implement XGBoost optimizations — the conceptual understanding (regularization, parallel tree building, pruning strategy) is what matters.

Real-world connection: XGBoost is used at Uber for ETA prediction, at Airbnb for search ranking, at Netflix for recommendation, and in high-frequency trading. Its speed and accuracy on structured data make it the default algorithm for tabular prediction problems where interpretability (via SHAP values) is also desired.

15.4 Supervised to Unsupervised Transition

15.4.1 Algorithms Covered So Far

All algorithms studied up to this point are supervised — they use labeled training data $(x_{i}, y_{i})$ where $y_{i}$ is the known correct answer:

Linear Regression, Logistic Regression, Decision Trees, Bayesian Learning (Naive Bayes), KNN, Bagging, Random Forest, AdaBoost, Gradient Boosting, XGBoost.

15.4.2 Algorithm Selection Framework

A quick decision guide for choosing algorithms:

Scenario	Algorithm
Linear data	Linear Regression
Non-linear data	Decision Tree
Need speed + accuracy on tabular data	XGBoost
One model insufficient	Ensemble methods (Bagging, Random Forest, Boosting)
No labels available	Clustering (K-Means, GMM) — the topic of the second half

15.4.3 Exam Note

Formulas and slides are available in the exam. You may need to solve numerical problems. Conceptual understanding — knowing which algorithm fits which scenario — is the most important real-world skill.

Bridge: Every algorithm so far needed a teacher (labels). Now we enter the world where the data must speak for itself — unsupervised learning.

15.5 Unsupervised Learning

Hook: Imagine walking into a library where every book is blank — no titles, no categories, no labels. Your job: organize thousands of books into meaningful groups using only their content. This is unsupervised learning — finding structure without being told what to look for.

15.5.1 Definition

In unsupervised learning, we have only features (inputs). We do not have labels (outputs/targets). There are no correct answers to train on.

The goal shifts from prediction to understanding the underlying pattern: - What groups exist in the data? (clustering) - What distribution did the data come from? (density estimation) - What is the underlying structure? (dimensionality reduction, latent variable models)

15.5.2 Why Use It?

Large amounts of data often come without labels. Labeling is expensive (think of paying humans to tag millions of images). Clustering techniques extract meaning without labels.

Real-world example — News articles: An algorithm scans thousands of articles, understands word patterns, and groups: - "score," "stadium," "match" → sports - "election," "vote," "senate" → politics

This grouping happens purely from similarity in the underlying data — no labels were ever provided.

15.5.3 Supervised vs. Unsupervised — Cat and Dog Analogy

Intuition + Analogy:

Supervised: Someone told you "this is a cat" (5 labeled examples) and "this is a dog" (5 labeled examples). You learn what a cat looks like from labeled examples. New animal with pointed ears, four legs, long tail, short height → you know it is a cat.

Unsupervised: Nobody told you what the animals are. You observe: these four have pointed ears, whiskers, short height — they look similar. You group them together. You don't know the name "cat" — a human must supply that label later. You only know they share characteristics.

The analogy maps exactly: supervised = learning from named examples; unsupervised = grouping by similarity alone. It breaks where data has overlapping characteristics — a small dog might get grouped with cats if whisker-like features dominate.

Q: If unsupervised learning means no labels, how is clustering different from labeling?

A: Clustering groups objects purely by characteristics, not by pre-existing labels. After clustering into C1 and C2, a human-in-the-loop says "C1 is humans and C2 is polar bears." The algorithm grouped; the human named. The algorithm never saw labels during grouping. Several students asked this — the distinction between "grouping" and "labeling" is subtle but fundamental.

15.5.4 Feature Vectors

A feature vector is a numeric representation of measurable characteristics. Every object or data point is converted to a vector of numbers that the algorithm can compute with.

Example — representing juice: - Attributes: color (yellow=1, red=2, green=3), taste (sweet=1, sour=2) - Green and sour juice: vector = (3, 2) - Red and sweet juice: vector = (2, 1)

15.5.5 What Is Clustering?

Clustering groups similar objects together based on their feature vectors.

Uses: - Summarizing data: Count how many items of each category exist (like a histogram). Understand the distribution of types. - Prediction: Points in the same cluster share characteristics and may share labels — useful for semi-supervised learning and anomaly detection.

15.5.6 Human-in-the-Loop

After clustering, a human interprets each group: - Group 1 → "men" - Group 2 → "women" - Or: Group 1 → cats, Group 2 → pandas, Group 3 → giraffes

Pitfall: Never assume the clusters found by an algorithm correspond to the categories you care about. The algorithm groups by whatever patterns exist in the feature vectors — which may reflect noise, artifacts, or attributes you didn't intend. A clustering of customer data might separate by "browser type" rather than "spending behavior" if browser metadata leaks into the feature set. Always inspect what each cluster actually contains before naming it.

Recap: Unsupervised learning finds structure without labels. Clustering groups similar objects; a human supplies the names afterward. The algorithm's job is to answer "what goes with what" — not "what is this called."

Bridge: The simplest and most widely used clustering algorithm is K-Means. It operationalizes "similarity" as Euclidean distance and iteratively refines cluster centers. Next, we dive into how it works.

Real-world connection: Unsupervised learning powers product recommendation ("customers who bought this also bought…"), customer segmentation, and anomaly detection in network security. Google News uses document clustering to group related stories without human editors. Spotify uses clustering on song audio features to power its "Discover Weekly" playlist.

15.6 K-Means Clustering

Hook: You have a thousand dots on a page. Group them into $K$ piles so dots in the same pile are close together and dots in different piles are far apart. Do it without knowing what the piles mean. K-Means solves this with just two simple rules: assign, then average, then repeat.

15.6.1 Overview

Purpose: K-Means is the most popular clustering algorithm. Given $N$ data points and a number $K$ , it partitions the data into $K$ clusters, each summarized by a centroid (prototype) denoted $μ_{k}$ . The goal is to minimize the total within-cluster squared distance.

15.6.2 The Algorithm Steps

Inputs & Outputs: - Input: Dataset of $N$ points ${x_{1}, \dots, x_{N}}$ in $R^{d}$ , number of clusters $K$ . - Output: $K$ centroids ${μ_{1}, \dots, μ_{K}}$ and an assignment of each point to a cluster.

Steps: 1. Initialization: Randomly pick $K$ points from the dataset as initial centroids. 2. Expectation Step (Assignment): Assign each data point to the nearest centroid (Euclidean distance). 3. Maximization Step (Update): Recalculate each centroid as the mean of all points assigned to it. 4. Repeat steps 2–3 until centroids stop changing (convergence) or a max iteration limit is reached.

These are the Expectation-Maximization (EM) steps. For basic K-Means, think "assign points" then "recalculate centers."

15.6.3 What Does "K" Mean?

$K$ is the number of clusters — chosen beforehand by the user.

Analogy: In KNN, $K$ is the number of neighbors. If a bird's $K$ nearest neighbors are ducks, the bird is classified as a duck. In K-Means, $K$ is how many clusters to form. Same letter, completely different meaning — do not confuse them.

Real-world: For Amazon customer segmentation, $K = 5$ might give: high spenders, medium spenders, low spenders, and two other behavioral groups — chosen by domain knowledge, not computed by the algorithm.

15.6.4 Distance Measure

The standard version uses Euclidean distance:

$∥ x_{n} - μ_{k} ∥ = j = 1 \sum d (x_{nj} - μ_{k j})^{2}$

This measures straight-line distance in the feature space. Points are assigned to the nearest centroid by this measure.

15.6.5 Symbol Registry — K-Means

Symbol	Meaning	LaTeX	Type/Domain
$K$	number of clusters	$K$	integer, user-chosen
$N$	number of data points	$N$	integer
$μ_{k}$	centroid of cluster $k$	$μ_{k}$	vector in $R^{d}$
$x_{n}$	the $n$ -th data point	$x_{n}$	vector in $R^{d}$
$r_{nk}$	binary assignment: 1 if point $n$ ∈ cluster $k$ , else 0	$r_{nk} \in {0, 1}$	binary scalar
$J$	sum of squared distances (cost/objective)	$J$	scalar

15.6.6 Worked Example: 2D Point Clustering

Trace: Run K-Means on a tiny concrete dataset.

Data points in 2 dimensions:

Point	X	Y
A	0	1
B	3	0
C	4	2
D	2	1
E	3	5

Task: Cluster into $K = 2$ .

Step 1 — Pairwise Euclidean distances:

A to B: $(0 - 3)^{2} + (1 - 0)^{2} = 9 + 1 = 10 \approx 3.16$

All pairs computed for reference: A-B: 3.16, A-C: 4.12, A-D: 2.00, A-E: 5.00, B-C: 2.24, B-D: 1.41, B-E: 5.00, C-D: 2.24, C-E: 1.41, D-E: 4.12.

Step 2 — Random initial centroids: Choose A(0,1) and C(4,2).

Step 3 — First assignment (E-step):

B: dist(A,B) = 3.16, dist(C,B) = $(4 - 3)^{2} + (2 - 0)^{2} = 1 + 4 \approx 2.24$ → closer to C (2.24 < 3.16) → C2.
D: dist(A,D) = $(0 - 2)^{2} + (1 - 1)^{2} = 2.00$ , dist(C,D) = $(4 - 2)^{2} + (2 - 1)^{2} = 4 + 1 \approx 2.24$ → closer to A → C1.
E: dist(A,E) = $(0 - 3)^{2} + (1 - 5)^{2} = 9 + 16 = 5.00$ , dist(C,E) = $(4 - 3)^{2} + (2 - 5)^{2} = 1 + 9 \approx 3.16$ → closer to C → C2.

Wait — let me recompute: B is closer to C (2.24 vs 3.16). Let me redo all assignments more carefully.

A: dist to A = 0, to C ≈ 4.12 → C1
B: dist to A ≈ 3.16, to C = 2.24 → C2
C: dist to A ≈ 4.12, to C = 0 → C2
D: dist to A = 2.00, to C ≈ 2.24 → C1
E: dist to A = 5.00, to C ≈ 3.16 → C2

Result: C1 = {A, D}, C2 = {B, C, E}.

Step 4 — Recalculate centroids (M-step):

$μ_{1} = (\frac{0 + 2}{2}, \frac{1 + 1}{2}) = (1.0, 1.0)$

$μ_{2} = (\frac{3 + 4 + 3}{3}, \frac{0 + 2 + 5}{3}) = (\frac{10}{3}, \frac{7}{3}) \approx (3.33, 2.33)$

Step 5 — Second assignment (E-step):

A to $μ_{1}$ (1,1): $(0 - 1)^{2} + (1 - 1)^{2} = 1.00$ ; to $μ_{2}$ (3.33,2.33): $(0 - 3.33)^{2} + (1 - 2.33)^{2} \approx 3.56$ → C1
B to $μ_{1}$ (1,1): $(3 - 1)^{2} + (0 - 1)^{2} = 4 + 1 \approx 2.24$ ; to $μ_{2}$ (3.33,2.33): $(3 - 3.33)^{2} + (0 - 2.33)^{2} \approx 2.36$ → C1
C to $μ_{1}$ (1,1): $(4 - 1)^{2} + (2 - 1)^{2} = 9 + 1 \approx 3.16$ ; to $μ_{2}$ (3.33,2.33): $(4 - 3.33)^{2} + (2 - 2.33)^{2} \approx 0.75$ → C2
D to $μ_{1}$ (1,1): $(2 - 1)^{2} + (1 - 1)^{2} = 1.00$ ; to $μ_{2}$ (3.33,2.33): $(2 - 3.33)^{2} + (1 - 2.33)^{2} \approx 1.89$ → C1
E to $μ_{1}$ (1,1): $(3 - 1)^{2} + (5 - 1)^{2} = 4 + 16 \approx 4.47$ ; to $μ_{2}$ (3.33,2.33): $(3 - 3.33)^{2} + (5 - 2.33)^{2} \approx 2.69$ → C2

Result: C1 = {A, B, D}, C2 = {C, E}. Assignment changed!

Step 6 — Recalculate centroids again (M-step):

$μ_{1} = (\frac{0 + 3 + 2}{3}, \frac{1 + 0 + 1}{3}) = (\frac{5}{3}, \frac{2}{3}) \approx (1.67, 0.67)$

$μ_{2} = (\frac{4 + 3}{2}, \frac{2 + 5}{2}) = (3.5, 3.5)$

Step 7 — Third assignment (E-step):

A to $μ_{1}$ (1.67,0.67): $(0 - 1.67)^{2} + (1 - 0.67)^{2} \approx 1.69$ ; to $μ_{2}$ (3.5,3.5): $(0 - 3.5)^{2} + (1 - 3.5)^{2} \approx 4.30$ → C1
B to $μ_{1}$ (1.67,0.67): $(3 - 1.67)^{2} + (0 - 0.67)^{2} \approx 1.49$ ; to $μ_{2}$ (3.5,3.5): $(3 - 3.5)^{2} + (0 - 3.5)^{2} \approx 4.61$ → C1
C to $μ_{1}$ (1.67,0.67): $(4 - 1.67)^{2} + (2 - 0.67)^{2} \approx 3.14$ ; to $μ_{2}$ (3.5,3.5): $(4 - 3.5)^{2} + (2 - 3.5)^{2} \approx 1.58$ → C2
D to $μ_{1}$ (1.67,0.67): $(2 - 1.67)^{2} + (1 - 0.67)^{2} \approx 0.47$ ; to $μ_{2}$ (3.5,3.5): $(2 - 3.5)^{2} + (1 - 3.5)^{2} \approx 4.92$ → C1
E to $μ_{1}$ (1.67,0.67): $(3 - 1.67)^{2} + (5 - 0.67)^{2} \approx 5.22$ ; to $μ_{2}$ (3.5,3.5): $(3 - 3.5)^{2} + (5 - 3.5)^{2} \approx 1.58$ → C2

Assignments unchanged from previous iteration → CONVERGED.

Final clusters: C1 = {A, B, D}, C2 = {C, E}.

Final centroids: $μ_{1} \approx (1.67, 0.67)$ , $μ_{2} = (3.5, 3.5)$ .

Sense-check: Points in C1 have low Y values (0 to 1); C2 has Y values 2 and 5. The algorithm separated them roughly by the Y-coordinate, which makes geometric sense — the gap between Y=1 and Y=2 is a natural split point.

Q: What if a point is exactly equidistant from two centroids?

A: Assign to either one — the choice is arbitrary. Practically, a person equally interested in sports and politics gets categorized as one. K-Means requires hard assignment. (Gaussian Mixture Models allow partial membership — the topic of the next lecture.)

15.6.7 Algorithm — Formal Statement

Input: Dataset $D$ of $N$ objects in $R^{d}$ , number of clusters $K$ .

Output: Set of $K$ clusters with centroids ${μ_{1}, \dots, μ_{K}}$ .

Algorithm: 1. Arbitrarily choose $K$ objects from $D$ as initial centroids. 2. Repeat: - (E-step) Assign each object to the cluster whose centroid is closest: $r_{nk} = {10 if k = ar g min_{j} ∥ x_{n} - μ_{j} ∥^{2} otherwise$ - (M-step) Update each centroid as the mean of its assigned objects: $μ_{k} = \frac{\sum _{n = 1}^{N} r _{nk} \cdot x _{n}}{\sum _{n = 1}^{N} r _{nk}}$ 3. Until assignments stop changing (convergence).

15.6.8 Pictorial Understanding

Scattered data points: 1. Pick $K$ random points as centers (red and blue crosses). 2. Expectation: Each point assigned to nearest center. Equivalent to classifying by which side of the perpendicular bisector between centers they fall on. The bisector is the decision boundary. 3. Maximization: Centers recomputed as means of assigned points. Centers shift toward the center of mass of their assigned points. 4. Repeat until centers stop moving.

15.6.9 Hard Clustering

K-Means performs hard clustering — every point belongs to exactly one cluster. Represented by binary $r_{nk}$ :

$r_{nk} = {10 if point n is in cluster k otherwise$

For each point $n$ , the sum across all clusters equals 1: $k = 1 \sum K r_{nk} = 1$

A point cannot be 50% cluster 1 and 50% cluster 2. This is hard assignment — also called the 1-of-K coding scheme.

Example (3 clusters, 5 points):

Point	$r_{n 1}$	$r_{n 2}$	$r_{n 3}$
1	1	0	0
2	0	0	1
3	0	1	0
4	0	0	1
5	1	0	0

Each row sums to 1. Point 1 is fully in cluster 1; point 2 is fully in cluster 3; etc.

Q: Can K-Means say a point is 40% cluster 1 and 60% cluster 2?

A: No. K-Means cannot express partial membership. This is a fundamental limitation. Gaussian Mixture Models (next lecture) provide soft assignments with probabilities — a point can be 0.4 in cluster 1 and 0.6 in cluster 2.

15.6.10 Mathematical Formulation — EM View

K-Means minimizes the cost function $J$ — the sum of squared distances (also called distortion measure or inertia):

$J = n = 1 \sum N k = 1 \sum K r_{nk} ∥ x_{n} - μ_{k} ∥^{2}$

Small $J$ means: objects in the same cluster are close to their centroid; the clusters are compact.

Expectation Step — minimize $J$ w.r.t. $r_{nk}$ , fixing $μ_{k}$ :

$r_{nk} = {10 if k = ar g min_{j} ∥ x_{n} - μ_{j} ∥^{2} otherwise$

Derivation: Since $J$ is linear in each $r_{nk}$ and $r_{nk}$ are independent across $n$ , we simply pick the $k$ that gives the smallest $∥ x_{n} - μ_{k} ∥^{2}$ for each $n$ .

Maximization Step — minimize $J$ w.r.t. $μ_{k}$ , fixing $r_{nk}$ :

$\frac{\partial J}{\partial μ _{k}} = 2 n = 1 \sum N r_{nk} (x_{n} - μ_{k}) = 0$

Solving: $μ_{k} = \frac{\sum _{n = 1}^{N} r _{nk} \cdot x _{n}}{\sum _{n = 1}^{N} r _{nk}}$

Numerator: sum of all data vectors in cluster $k$ . Denominator: count of points in cluster $k$ . This is simply the cluster mean — the center of mass.

15.6.11 Evaluating Clustering Quality

Compare two clusterings using sum of squared errors $J$ : - Clustering 1: C1 = {A, B, D}, C2 = {C, E} → SSE computed from final centroids. - Clustering 2: C1 = {A, B}, C2 = {C, D, E} → compute its SSE.

The clustering with lower $J$ is better — it has more compact clusters.

Pitfall: SSE always decreases as $K$ increases (at $K = N$ , each point is its own centroid → SSE = 0). So SSE alone cannot tell you the "correct" $K$ . Use the elbow method or silhouette analysis (covered in section 15.10) to choose $K$ .

Complexity & Cost

Complexity: Each iteration requires computing $O (K N d)$ distance calculations ( $K$ centroids × $N$ points × $d$ dimensions). For large datasets, this is expensive. The algorithm typically converges in few iterations (often < 10-20 for well-behaved data), so the total cost is $O (I K N d)$ where $I$ is the number of iterations.

Scalability limits: K-Means scales linearly with $N$ and $d$ , making it usable for moderate-sized datasets. For very large $N$ (millions), mini-batch K-Means or approximate nearest-neighbor methods are used. The standard algorithm requires the entire dataset in memory — out-of-core variants exist but are not standard.

When to Use / Alternatives

Scenario	Best Method
Globular, equal-density clusters	K-Means
Non-spherical shapes	DBSCAN, spectral clustering
Soft/overlapping clusters	Gaussian Mixture Models (GMM)
Categorical data	K-Modes, K-Prototypes
Unknown $K$	Use elbow + silhouette to choose

Recap: K-Means iterates between assigning points to nearest centroids (E-step) and recomputing centroids as cluster means (M-step). It converges when assignments stop changing. It performs hard clustering — each point belongs to exactly one cluster. The number of clusters $K$ must be chosen beforehand.

Bridge: K-Means doesn't just give clusters — it can also tell you which points don't fit well in any cluster. Next: using K-Means for outlier detection.

Real-world connection: K-Means is used in customer segmentation (grouping shoppers by purchase behavior), image compression (reducing an image to $K$ representative colors), document clustering, and anomaly detection. It is often the first clustering algorithm tried because of its simplicity and speed. It serves as a baseline before trying more complex methods like GMM or DBSCAN.

15.7 Outlier Detection with K-Means

15.7.1 Basic Idea

Hook: After clustering, some points sit awkwardly far from everyone else in their group. These are the outliers — and K-Means gives you a natural way to find them.

After clustering, outliers are points far from their centroid compared to peers in the same cluster.

15.7.2 The Outlier Ratio

$outlier ratio = \frac{distance of point x to its own centroid}{average distance of all points in that cluster to the centroid}$

Higher ratio → more likely an outlier. A ratio near 1 means the point is about as far from the center as the average point in its cluster. A ratio of 5 or 10 means the point is dramatically farther than expected.

15.7.3 Worked Example

Cluster C1 (points A, B, D) with centroid $μ_{1} \approx (1.67, 0.67)$ : - dist(A, centroid) = 1.69 - dist(B, centroid) = 1.49 - dist(D, centroid) = 0.47

Average distance: $\frac{1.69 + 1.49 + 0.47}{3} = \frac{3.65}{3} \approx 1.22$

Ratios: - A: 1.69 / 1.22 ≈ 1.39 - B: 1.49 / 1.22 ≈ 1.22 - D: 0.47 / 1.22 ≈ 0.39

Sense-check: No ratio is extreme — all values are within 1.5× of the cluster average. If a ratio were 5 or 10, that point would be flagged as an outlier.

15.7.4 Note on Centroids and Outliers

Pitfall: Outliers are included in centroid calculation during normal K-Means. The centroid shifts toward outliers, which can mask them — the centroid moves closer to the outlier, making the outlier's distance seem less extreme. Outlier detection happens after clustering is complete. For a more robust approach, use K-Medoids (which picks actual data points as centers) or remove extreme points before running K-Means.

Recap: After K-Means converges, compute each point's distance-to-centroid ratio. Large ratios flag outliers. The centroid itself may be pulled toward outliers, so this method is approximate.

Bridge: Outlier detection relies on the clustering having converged to a stable state. Next: what convergence means and when K-Means actually stops.

Real-world connection: K-Means outlier detection is used in fraud detection — flagging unusual transactions far from the normal-spending cluster. It also powers network intrusion detection (traffic patterns far from normal clusters) and quality control in manufacturing (products far from the cluster of good units).

15.8 Convergence and Stopping

15.8.1 When Does K-Means Converge?

Convergence: Centroids do not change between two consecutive iterations. Points remain in the same clusters. Formally: $μ_{k}^{(t + 1)} = μ_{k}^{(t)}$ for all $k$ .

A computer checks numerically: recalculate centroids. If they are identical (within floating-point tolerance) to the previous iteration → stop. Alternatively, if cost $J$ stops decreasing → stop.

Pitfall: K-Means is guaranteed to converge (each E-step and M-step reduces or maintains $J$ ), but it converges to a local minimum, not necessarily the global minimum. Different random initializations can lead to different final clusterings. This is why multiple runs with different starting points (see section 15.9) are recommended.

15.8.2 Convergence Visualization

Visual intuition: Plot iteration number on the X-axis and cost $J$ on the Y-axis.

Initial random centroids → $J$ is very high (poor clustering).
1st iteration → $J$ drops sharply (biggest improvement).
2nd iteration → $J$ drops further, but less.
3rd iteration → $J$ flat (constant) — the curve has leveled off.

The flat point is convergence. The curve looks like a rapidly descending staircase that quickly flattens — think of a ball rolling down a bowl and settling at the bottom. Typically within 2–5 iterations for simple datasets, and rarely more than 10–20 for real-world data.

15.8.3 Alternative: Maximum Iterations

Set a max iteration count (like max_iter=300 in scikit-learn). The algorithm stops at convergence OR at the limit, whichever comes first. This prevents infinite loops on pathological datasets. Requires domain expertise to set appropriately.

Recap: K-Means converges when assignments stop changing, typically in a few iterations. The cost $J$ decreases monotonically but may settle at a local minimum.

Bridge: The quality of the final clustering depends heavily on where you start. Next: strategies for choosing good initial centroids.

15.9 Choosing Initial Centroids

Hook: K-Means is like dropping $K$ magnets onto a sheet of iron filings — where the magnets land decides the final pattern. Bad initial centroids mean bad final clusters, no matter how many iterations you run.

15.9.1 Method 1: Multiple Runs

Run K-Means many times with different random initial centroids. Pick the result with the lowest final cost $J$ .

Advantage: Best chance of finding the global minimum.

Disadvantage: Very costly for large datasets — you run the entire algorithm tens or hundreds of times.

In practice: scikit-learn's K-Means defaults to n_init=10 — it runs 10 times and keeps the best result. For production use, n_init='auto' dynamically adjusts.

15.9.2 Method 2: Hierarchical Clustering Pre-Processing

Run hierarchical clustering first (AGNES — bottom-up agglomerative, or DIANA — top-down divisive).
Get final clusters from hierarchical clustering.
Use their centroids as initial centroids for K-Means.

Hierarchical clustering: AGNES (Agglomerative Nesting) starts with each point as its own cluster and merges the closest pairs repeatedly. DIANA (Divisive Analysis) starts with all points in one cluster and recursively splits.

Advantage: Better starting points — hierarchical clustering provides a reasonable initial partition.

Disadvantage: Runs another full clustering method first — adds $O (N^{2})$ or worse cost. But for high accuracy on moderate datasets, this is sometimes acceptable.

15.9.3 Method 3: Select More Than $K$ Candidates

Choose more than $K$ random candidate centroids (e.g., for $K = 3$ , pick 5).
Calculate pairwise distances between all candidates.
Select the $K$ that are most widely separated from each other.

Pitfall: This method risks picking outliers as centroids because outliers are far from other points. Always remove or winsorize outliers before applying this strategy. The farthest-apart points may be noise, not genuine cluster centers.

15.9.4 Post-Processing

Run the algorithm once, examine the results (cluster sizes, SSE), then use that information to choose better initial centroids for a second run. For example, if one cluster is tiny and another is huge, you might initialize centroids closer to the dense region. Not always purely random — can be guided by these strategies.

15.9.5 K-Means++ (Industry Standard)

The most widely used initialization method is K-Means++, which selects initial centroids to be far apart with probability proportional to squared distance:

Choose the first centroid uniformly at random from the data.
For each subsequent centroid, choose a data point with probability proportional to its squared distance from the nearest already-chosen centroid.
Repeat until $K$ centroids are chosen.

This gives a provable $O (lo g K)$ approximation to the optimal clustering and typically converges in fewer iterations than random initialization. Scikit-learn uses K-Means++ by default.

Recap: Good initialization matters. Use K-Means++ (the default in modern libraries), or run multiple random starts and pick the best. Hierarchical pre-clustering works when accuracy matters more than speed.

Bridge: You also need to know $K$ — the number of clusters. This is not computed; it is chosen. Next: methods for picking the right $K$ .

Real-world connection: K-Means++ (Arthur & Vassilvitskii, 2007) is the default in scikit-learn and Spark MLlib. It reduces the average number of iterations by roughly 2× compared to random initialization while giving better final clusterings.

15.10 Determining $K$ — Number of Clusters

Hook: The hardest question in clustering isn't "how" — it's "how many?" K-Means never tells you $K$ . You must choose it yourself, and the right choice can make or break your analysis.

15.10.1 Domain Knowledge

Primary method: expertise. Customer segmentation → 3 groups (high/medium/low spenders). Professional grouping → categories you care about. When you know what you're looking for, you know $K$ . This is the most common approach in industry.

15.10.2 Method 1: $N /2$ Rule of Thumb

$K = \frac{N}{2}$

For $N = 100$ : $K = 50 \approx 7$ .

Limitation: Impractically large $K$ for big datasets. For $N = 1, 000, 000$ , this gives $K \approx 707$ — far too many clusters for practical interpretation. Use only as a rough starting point for small datasets.

15.10.3 Method 2: Elbow Method

Run K-Means for $K = 2, 3, 4, 5, 6, \dots$ . For each $K$ , compute the final SSE ( $J$ ). Plot $K$ (X-axis) vs. SSE (Y-axis). As $K$ increases, SSE always decreases (more clusters = more centroids = points closer to their assigned center). Look for the elbow — the point where the decrease rate sharply changes from steep to shallow. That $K$ is recommended.

Why it works: Before the elbow, each additional cluster captures a genuinely new group, sharply reducing error. After the elbow, additional clusters merely subdivide existing groups, giving diminishing returns.

Example (1D data): Suppose you get these SSE values:

$K$	SSE
2	73
3	57
4	48
5	45
6	44

The drop from $K = 2$ to $K = 3$ is 16; from $K = 3$ to $K = 4$ is 9; from $K = 4$ to $K = 5$ is 3; from $K = 5$ to $K = 6$ is 1. The elbow is at $K = 4$ — after that, adding clusters barely helps. Recommended $K = 4$ .

Cost: Requires multiple K-Means runs (one per $K$ ), but accuracy gain justifies the cost.

Homework: Run elbow method on slide data for $K = 2, 3, 4, 5$ . Compute SSEs, plot, identify elbow.

15.10.4 Method 3: Silhouette Analysis

Measures how well each point fits in its own cluster compared to the nearest other cluster. Score range: $[- 1, + 1]$ . Higher = better.

For each point $i$ : - $a (i)$ = average distance to other points in its own cluster (want small — tight cluster). - $b (i)$ = average distance to points in the nearest other cluster (want large — well-separated).

$s (i) = \frac{b ( i ) - a ( i )}{max { a ( i ) , b ( i )}}$

Interpretation: - $s \approx + 1$ : well matched to its own cluster, far from others (good). - $s \approx 0$ : on the boundary between two clusters (ambiguous). - $s \approx - 1$ : probably in the wrong cluster (bad — closer to another cluster's points than its own).

Procedure: 1. Run K-Means for different $K$ (2, 3, 4, 5, …). 2. Compute the average silhouette score across all points for each $K$ . 3. Plot $K$ (X-axis) vs. average silhouette score (Y-axis). 4. Choose the $K$ with the highest average score.

Pitfall — Elbow vs. Silhouette: These two methods can disagree. The elbow method favors simpler models (fewer clusters); silhouette analysis favors well-separated clusters (which may require more $K$ ). In practice, use both and let domain knowledge break ties. Also, silhouette is $O (N^{2})$ to compute — expensive for large $N$ .

Homework: Using elbow method clusters for $K = 2, 3, 4, 5$ , compute $s = (b - a) / max (a, b)$ , plot, find best $K$ .

Recap: Choose $K$ by domain knowledge first. If unknown, use the elbow method (look for the bend in the SSE curve) or silhouette analysis (maximize the score). Both require running K-Means multiple times at different $K$ values.

Bridge: K-Means works well for globular, equal-sized clusters. But real data is messier. Next: when K-Means fails.

Real-world connection: The elbow method is the most commonly cited $K$ -selection technique. In practice, many practitioners simply try $K = 3, 5, 10$ and evaluate the clusters qualitatively. For automated pipelines, the gap statistic (Tibshirani, 2001) compares the within-cluster dispersion to its expected value under a null reference distribution.

15.11 K-Means Limitations

15.11.1 Different Sizes

Pitfall: K-Means produces clusters of roughly equal size. If true groups have very different sizes (e.g., one cluster has 1000 points, another has 10), K-Means may split the large group into pieces or absorb the small group into a larger one. The cost function $J$ penalizes large distances from centroids. Splitting a large cluster into two reduces $J$ more than keeping a tiny cluster intact.

15.11.2 Different Densities

If one cluster is dense (points packed tightly) and another sparse (points spread out), K-Means struggles. The dense cluster may get split. Splitting it creates two very tight sub-clusters, each with low SSE. That is more attractive to the algorithm than maintaining the sparse cluster, which always has high SSE.

15.11.3 Non-Globular Shapes

Pitfall: K-Means can only find globular (spherical/elliptical) clusters. Crescent, ring, spiral, or winding shapes are cut into circular pieces. Any shape not approximately circular is misrepresented. This is because K-Means uses Euclidean distance from a single center — the decision boundary is linear (perpendicular bisector), making cluster boundaries straight lines that cannot wrap around curves.

Visual intuition: Imagine two concentric rings (a doughnut). K-Means with $K = 2$ will draw a straight-line boundary through both rings, slicing each ring in half. It cannot separate the inner ring from the outer ring because the Euclidean distance to a single center cannot capture the "ring" geometry. For such shapes, use DBSCAN or spectral clustering instead.

15.11.4 Overcoming Limitations

Solution: Increase $K$ . Even with 3 true groups, set $K$ larger (e.g., 10–15).

Why: More clusters → smaller, more homogeneous groups. Objects from different true groups won't be mixed. A crescent shape becomes several small circular clusters along the arc.

After clustering: Human-in-the-loop (or a post-processing algorithm) merges small clusters into true semantic groups. E.g., clusters 1, 3, 7, 11, 14 → all same type → merge. This human role is increasingly done by AI agents and automated hierarchical merging.

Recap: K-Means assumes clusters are globular, equal-sized, and equal-density. Real data violates these assumptions. The workaround: over-cluster (use a larger $K$ ) and then merge. For genuinely non-globular data, use DBSCAN, spectral clustering, or Gaussian Mixture Models.

Bridge: GMM addresses the hard-assignment limitation by giving each point a probability of belonging to each cluster. Next: a preview of soft clustering with Gaussian Mixture Models.

Real-world connection: K-Means limitations are why DBSCAN is preferred for spatial data (GPS trajectories, geographic clustering). Spectral clustering is used for graph-based data (social networks, image segmentation). Each algorithm makes different assumptions about cluster shape.

15.12 Preview: Gaussian Mixture Models (GMM)

Hook: K-Means forces every point into exactly one group. But real life is messier — a song can be partly rock and partly blues. Gaussian Mixture Models let a point belong to multiple clusters at once, with probabilities instead of hard yes/no.

15.12.1 Hard vs. Soft Clustering

K-Means limitation: Strict binary assignment ( $r_{nk} \in {0, 1}$ ). In real life, a person might be 60% interested in politics and 40% in sports. K-Means cannot express this — the person is forced entirely into one group.

GMM solution: Soft clustering — each point gets a probability (responsibility) for each cluster. A point can have 0.6 probability of being in cluster 1 and 0.4 probability of being in cluster 2. The assignments sum to 1 per point:

$k = 1 \sum K γ_{nk} = 1, γ_{nk} \in [0, 1]$

where $γ_{nk}$ (gamma) is the responsibility that cluster $k$ takes for point $n$ .

K-Means is actually a special limiting case of GMM — it corresponds to GMM with identical spherical covariance matrices, in the limit as the variance goes to zero. In that limit, the soft responsibilities harden into 0/1 assignments.

15.12.2 What to Review

Before the next session, refresh: - Gaussian (normal) distribution PDF: $N (x ∣ μ, σ^{2}) = \frac{1}{2 π σ ^{2}} exp (- \frac{( x - μ ) ^{2}}{2 σ ^{2}})$ - Likelihood and Maximum Likelihood Estimation (MLE) for Gaussian distributions: given data, how to estimate $μ$ and $σ^{2}$ . - These have been covered in earlier sessions (see Chapter 2 and Chapter 13 review material).

15.12.3 Upcoming Topics

Gaussian Mixture Models (next session) — full probabilistic clustering with the EM algorithm
Support Vector Machines (SVM) — study from mathematics class material; will be touched briefly
Ethics, bias, and responsible AI — critical real-world considerations
Two more sessions remain in the course

Recap: GMM extends K-Means by replacing hard 0/1 assignments with soft probabilities. Each cluster is a Gaussian distribution; each point gets a probability of belonging to each Gaussian. The EM algorithm (already seen in K-Means) generalizes to fit GMMs using maximum likelihood.

Bridge: The EM framework you learned for K-Means — alternate between assignment and update — carries directly over to GMM. The difference: in GMM, the E-step computes probabilities (not hard labels), and the M-step updates means, covariances, and mixing weights (not just means).

Real-world connection: GMMs are used in speaker identification (each speaker's voice is a Gaussian in acoustic feature space) and background subtraction in video (pixels belonging to the background vs. moving objects). In finance, GMMs model return distributions as mixtures of "normal market" and "crisis" regimes. GMM is also the foundation for more advanced generative models.

Exam Guidance Summary

Exam note: This section consolidates all exam-relevant guidance from the lecture.

Algorithms tested: Linear Regression, Logistic Regression, Decision Trees, Naive Bayes, KNN, Bagging, Random Forest, AdaBoost, Gradient Boosting, XGBoost, K-Means.
Ensemble problems: Model predictions will be given. You compute combined predictions and residuals using the formulas provided. Tree splits via entropy/Gini not required — you will not build a decision tree from scratch in the ensemble context.
Gradient boosting problems: Given initial prediction, residuals, and weak learner predictions, compute updated predictions with learning rate $y^_{new} = y^_{old} + η \cdot h (x)$ . Iterate for multiple rounds. Know why the residual is the negative gradient of MSE.
K-Means problems: Numerical — compute Euclidean distances, assign points to nearest centroids, recalculate centroids as means, check convergence. Full worked example in section 15.6.6.
Elbow method and silhouette analysis: Computational homework using slide data for $K = 2, 3, 4, 5$ . Know both formulas: elbow uses SSE vs. $K$ ; silhouette uses $s (i) = (b (i) - a (i)) / max (a (i), b (i))$ .
Formulas are available on slides during exam. You must know how to apply them, not memorize them.
Conceptual understanding: Which algorithm for which scenario is the most important real-world skill tested:
Linear data → Linear Regression
Non-linear data → Decision Tree
Speed + accuracy on tabular data → XGBoost
Multiple models needed → Ensemble methods
No labels → K-Means / GMM
GMM: Refresh Gaussian PDF formula and MLE before next session.
SVM: Study from mathematics class material — will be covered briefly.
K-Means convergence: Know that the algorithm always converges (to a local minimum), usually in 2–5 iterations. Be able to check convergence numerically.
Initialization: Know K-Means++ as the default method. Understand why multiple random starts help.
K-Means limitations: Equal cluster sizes, equal densities, globular shapes only. Know the over-clustering workaround.

Key Industry Applications

Ensemble Methods & Gradient Boosting

XGBoost: Dominant in Kaggle competitions — of 29 winning solutions in Kaggle 2015, 17 used XGBoost. Used at Uber (ETA prediction), Airbnb (search ranking), Netflix (recommendation), and in high-frequency trading (price movement prediction). Its speed, accuracy, and built-in regularization make it the default algorithm for tabular data in production.
LightGBM: Preferred for high-dimensional sparse data. Used at Microsoft for click-through rate prediction and at financial institutions for fraud detection where feature spaces can have millions of dimensions.
CatBoost: Handles categorical data automatically without preprocessing. Popular in retail (product categorization) and any domain with many categorical features (survey data, demographic data).
scikit-learn GradientBoostingRegressor / GradientBoostingClassifier: exists for educational purposes but too slow for production use. All serious practitioners use XGBoost, LightGBM, or CatBoost.

K-Means & Unsupervised Learning

Customer segmentation: Primary K-Means use case. Amazon, Walmart, and telecom companies group customers by spending patterns, browsing behavior, and demographics to tailor marketing campaigns. Typical $K$ values: 3–10.
Document clustering: News articles auto-grouped into topics (sports, politics, technology) without human labels. Google News uses clustering to group related stories. Research paper repositories (arXiv, PubMed) use clustering for topic-based search.
Image compression (vector quantization): Reducing an image to $K$ representative colors. Each pixel is replaced by its nearest cluster centroid, achieving compression ratios of 4–16% (see Bishop §9.1.1 for a worked example with $K = 2, 3, 10$ ).
Anomaly / outlier detection: After clustering, points far from their centroids are flagged. Used in fraud detection (unusual transactions), network security (unusual traffic patterns), and quality control (defective products).
AI agents increasingly handle human-in-the-loop clustering interpretation — automatically naming clusters, merging sub-clusters, and generating human-readable summaries of what each group represents.

Algorithm Selection Quick Reference

Data Scenario	Recommended Algorithm
Tabular data with labels, need best accuracy	XGBoost / LightGBM
Many categorical features	CatBoost
Unlabeled data, globular clusters	K-Means (K-Means++ init)
Unlabeled data, non-globular shapes	DBSCAN, Spectral Clustering
Soft/overlapping cluster membership	Gaussian Mixture Models (GMM)
Interpretability critical	Decision Tree, Logistic Regression

ML Lecture 15 notes · Ensemble Learning, Gradient Boosting, and Introduction to Unsupervised Learning

Machine Learning· postgraduate· 2026-06-29

Sections Breakdown

1Ensemble Learning Recap

Review of bagging, boosting, AdaBoost, and weak learner definition.

2Gradient Boosting

Core idea, residuals, negative gradient, worked examples, learning rate.

3XGBoost and Variants

XGBoost optimizations, LightGBM, CatBoost comparison.

4Supervised to Unsupervised Transition

Algorithm selection framework bridging supervised to unsupervised learning.

5Unsupervised Learning

Definition, feature vectors, clustering, human-in-the-loop interpretation.

6K-Means Clustering

Algorithm steps, EM view, hard clustering, worked 2D example.

7Outlier Detection with K-Means

Outlier ratio, worked example, centroid bias.

8Convergence and Stopping

Local minimum guarantee, convergence visualization, maximum iterations.

9Choosing Initial Centroids

Multiple runs, hierarchical pre-processing, K-Means++.

10Determining K — Number of Clusters

Elbow method, silhouette analysis, sqrt(N/2) heuristic.

11K-Means Limitations

Different sizes, densities, non-globular shapes, over-clustering workaround.

12Preview: Gaussian Mixture Models

Hard vs soft clustering, GMM introduction.

13Exam Guidance Summary

Consolidated exam-relevant guidance.

14Key Industry Applications

Real-world applications of ensemble methods and K-Means.

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.

Ensemble Learning Methods

Must-know: Bagging builds models in parallel (reducing variance); boosting builds sequentially (reducing bias). Weak learners must beat random chance (>0.5 accuracy).

$y^_{ensemble} = m = 1 \sum M w_{m} \cdot h_{m} (x)$

⚠️ Top pitfall: Confusing parallel (bagging) vs sequential (boosting) — the most common exam mistake in ensemble methods.

Self-check: If you have high bias in your model, would you use bagging or boosting?

Connects to: AdaBoost, Gradient Boosting, Bias-Variance Tradeoff

Gradient Boosting

Must-know: Each new model predicts the residuals of the previous ensemble. The residual is the negative gradient of MSE. Final prediction is the sum of all scaled contributions.

$F_{m} (x) = F_{m - 1} (x) + η \cdot h_{m} (x) where h_{m} fits residuals y_{i} - F_{m - 1} (x_{i})$

⚠️ Top pitfall: Forgetting the learning rate $η$ scales each new model's contribution. Without it, models overfit in one step.

Self-check: In the house price example, why does gradient boosting use residuals instead of original prices?

Connects to: AdaBoost, XGBoost, Learning Rate

XGBoost and Variants

Must-know: XGBoost extends gradient boosting with L1/L2 regularization, parallel tree node building, and depth-first pruning. Choose XGBoost for general tabular data, LightGBM for large sparse data, CatBoost for categorical features.

$Obj = i = 1 \sum N L (y_{i}, y^_{i}) + m = 1 \sum M Ω (f_{m}), Ω (f) = γ T + \frac{1}{2} λ ∥ w ∥^{2}$

⚠️ Top pitfall: Using scikit-learn's GradientBoostingRegressor for large datasets — it is fully sequential and very slow compared to XGBoost.

Self-check: What three optimizations make XGBoost faster than basic gradient boosting?

Connects to: Gradient Boosting, LightGBM, CatBoost

Unsupervised Learning and K-Means

Must-know: K-Means alternates between assigning points to nearest centroid (E-step) and recomputing centroids as means (M-step). It performs hard clustering — each point belongs to exactly one cluster.

$J = n = 1 \sum N k = 1 \sum K r_{nk} ∥ x_{n} - μ_{k} ∥^{2}, μ_{k} = \frac{\sum _{n} r _{nk} x _{n}}{\sum _{n} r _{nk}}$

⚠️ Top pitfall: Confusing K in K-Means (number of clusters) with K in KNN (number of neighbors) — same letter, completely different meaning.

Self-check: After running K-Means, point A is assigned to cluster 1. Can it also be 40% in cluster 2?

Connects to: GMM, Hard Clustering, EM Algorithm

Choosing K and Evaluating Clusters

Must-know: Use the elbow method (plot SSE vs K, look for the bend) or silhouette analysis (maximize average silhouette score). K-Means++ is the standard initialization method.

$s (i) = \frac{b ( i ) - a ( i )}{max { a ( i ) , b ( i )}}, K = \frac{N}{2} (heuristic)$

⚠️ Top pitfall: SSE always decreases as K increases — the elbow is not always obvious. Elbow and silhouette can disagree; use domain knowledge to decide.

Self-check: If silhouette score for a point is -0.3, what does that tell you?

Connects to: K-Means++, Elbow Method, Silhouette Analysis

K-Means Limitations

Must-know: K-Means assumes globular, equal-sized, equal-density clusters. For non-globular shapes, use DBSCAN or spectral clustering. For soft assignments, use GMM.

$Limitation: boundary is linear (perpendicular bisector)$

⚠️ Top pitfall: Applying K-Means to crescent-shaped or ring-shaped data — the algorithm splits these shapes into circular pieces.

Self-check: What is the workaround when your data has non-globular clusters but you must use K-Means?

Connects to: DBSCAN, GMM, Spectral Clustering

Previous LectureLecture 14 · Ensemble Methods — Bagging, Random Forest, and Boosting

Next LectureLecture 16 · Gaussian Mixture Models and Support Vector Machines

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.