—

Data Mining

K-Nearest Neighbor and Ensemble Methods

Published: 2026-08-05

Level: postgraduate

Audience: Postgraduate students in Data Mining

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

Classification: supervised learning and prediction — covered in Lecture 6 (Classification, Performance Measures, and Overfitting)
Overfitting and underfitting — covered in Lecture 6 (Classification, Performance Measures, and Overfitting)
Decision trees: greedy best-split construction — covered in Lecture 7 (Decision Trees)
Distance and similarity measures — covered in Lecture 2 (Data Mining Fundamentals)
Normalization: min-max, z-score, and decimal scaling — covered in Lecture 4 (Data Preprocessing: Noise, Integration, Transformation, and Reduction)

This session covers the last two pieces of the classification unit: K-nearest neighbor (KNN), a lazy learning classifier, and ensemble methods, the final classification topic before association rule mining. KNN answers a simple question — "who is closest to me, and what class are they?" — with a surprisingly powerful rule. Ensemble methods answer another: if many models each make a prediction, how do we combine them into one better prediction?

9.1 Eager Learning vs Lazy Learning

Hook. Where does a classification model come from? One family of algorithms builds its model during training, before it ever sees a test sample. Another family builds almost nothing at all — it keeps the raw training data and only starts working when a test sample arrives. The two styles are called eager learning and lazy learning, and the difference decides when you pay your computing cost.

Before looking at KNN itself, we need the two styles of learning that organize classification algorithms: eager learning and lazy learning, also called instance-based learning. The names say it all. One does its work eagerly, up front; the other stays lazy until a test sample actually arrives.

9.1.1 Eager Learning

Eager learning means that, given the training data, we first construct a classification model and only then receive test data to classify. With a decision tree, we receive the training data, build the tree, and then feed testing examples through it to make predictions and measure the model's performance. Rule-based classifiers and naive Bayes work the same way: build the model first, use it later. The model is the product of training.

Think of the tree as a list of questions already worked out: which attribute to split on, in what order, with what thresholds. Once the tree stands, the training data has served its purpose — the tree has absorbed everything the data had to say, and from that moment on the data itself is no longer consulted.

9.1.2 Lazy Learning: Store, Don't Build

Lazy learning — also called instance-based learning — takes the opposite path. Given the training data, we simply store it, with some minor pre-processing. No classification model is built: no tree, no rules, nothing. Then, when a test sample arrives, we do the computation to make the prediction. KNN is the classic example of lazy learning. Decision trees, rule-based classifiers, and naive Bayes are eager.

The name "instance-based" comes from the stored objects: each row of the training data is an instance, and the instances themselves do the classifying. The training step is barely a step — store the table, and you are done training.

9.1.3 Train Time vs Test Time

The trade-off follows directly. Eager learning has high training time — we build the model up front — but very low test time: a test sample just runs through the finished tree or rules. Lazy learning has negligible training time, since storing data costs almost nothing, but very high test time, because all the work of finding neighbors happens when the test sample arrives. A good exercise: take the same dataset, build a decision tree model and then a KNN model, and compare their train and test times side by side.

	Eager learning (e.g., decision tree)	Lazy learning (e.g., KNN)
Training time	High — model built up front	Negligible — just store the data
Test time	Low — run the sample through the model	High — all the distance work happens here
Where the work happens	Training phase	Every test prediction

The table is the whole trade-off in one glance: eager pays once at training, lazy pays on every single prediction.

9.1.4 Hypothesis Commitment and Where the Knowledge Lives

Two deeper points distinguish the styles. First, commitment. Eager learning commits to a single hypothesis: once the tree is built, that tree is our hypothesis about the data, and we stick with it as long as possible. Lazy learning instead combines many local functions — many small local hypotheses — into an implicit global approximation function. If that sounds abstract, the promise is that the Voronoi cell discussion makes it concrete, and the session explicitly asks you to "hold this thought for the next 15 minutes."

Second, knowledge location. In eager learning the model holds the knowledge: the tree contains what was learned. In lazy learning the training instances themselves are the knowledge — the training data you were given is your knowledge, stored as-is. Prediction becomes a search: find the stored training instance that most closely resembles the test instance, and take its class label.

9.1.5 Rote Learning and Nearest Neighbor

Lazy learning splits into two flavors. Rote learning memorizes the entire training data and classifies by finding an exact match: given a test sample, search the training data for a sample identical to it, and if one exists, assign its class label to the test sample. If no exact match exists, rote learning cannot predict anything — that is its fatal weakness. Nearest neighbor (KNN) relaxes the requirement: instead of an exact match, find the closest or most similar training examples, and let their class labels decide.

Rote learning is the textbook definition of memorization: it never generalizes beyond what it has already seen. KNN takes the single step from "identical" to "similar," and that step turns a toy method into a working classifier.

9.1.6 Worked Example: Golf Play Prediction with Rote Learning

Worked example: deciding whether to play golf.

Real-world setting: this is a small decision-support system — given today's weather, should you play golf?

The golf play prediction system has four attributes — temperature, outlook, humidity, and windy — and predicts whether to play golf or not. The training data sits at the top, and a test tuple sits at the bottom with an unknown class label.

With rote learning we scan the training data for an exact match of the test tuple. The scan finds one tuple whose attribute values match the test tuple exactly. Whatever class label that training tuple carries is assigned to the test tuple: the prediction is "yes." One match, one answer.

Step 1: take the test tuple, attribute by attribute.
Step 2: search all stored tuples for one with identical values on all four attributes — temperature, outlook, humidity, and windy.
Step 3: exactly one tuple matches; copy its class label, "yes," onto the test tuple.

Sense-check: the training data contained a day exactly like today's, and that day was a play day — so the advice is to play. Nothing was learned or built; one lookup decided it.

9.1.7 Worked Example: Golf Play Prediction with KNN

Worked example: the same weather, now classified with KNN.

The same setting, now with KNN. The test tuple has no exact match in the training data, so rote learning would be stuck. KNN does not need all four attributes to match: if all four match, that is ideal, but even three matching attributes are good enough.

Step 1: count attribute matches against every training tuple.
Step 2: find the tuples that match on three of the four attributes — four such tuples exist.
Step 3: read their labels: three say "yes," one says "no."
Step 4: apply the tiebreaker — majority voting: three of four votes say "yes," so the KNN prediction for the test tuple is "yes."

Sense-check: the test day resembles four past days, and three of those were play days; the majority of similar experience says play.

This is the whole idea in one example: you do not need identity, you need similarity, plus a rule for breaking ties.

9.1.8 The Duck Analogy and the Neighborhood Picture

Intuition. The guiding intuition: "if it walks like a duck, then most probably you are a duck." If most of the test sample's properties match a training sample, assign the training sample's label to it. The mapping is direct: properties = attributes, "walks like" = close distance, "most probably" = majority vote. Where the analogy breaks: a duck costume — a test sample that resembles the wrong class on a few important attributes — will fool the rule, because KNN has no built-in sense of which attributes matter unless the data is scaled (see 9.6).

Visually: project the training examples into a two-dimensional space, and project the test sample into the same space. The class label of the test sample is decided by its surroundings — if most points in its neighborhood are of the red class, assign red; if most are green, assign green.

Picture the space as a map with two axes. Every training example is a colored dot — red or green — and the test sample is a new dot placed at its coordinates. Draw a circle around the test dot. If the circle holds mostly red dots, color the test dot red; if mostly green, color it green. How big the neighborhood is, how many samples it should contain, and how ties are broken are questions the session deliberately deferred, answering them as the concept builds.

Pitfalls.

Rote learning cannot predict at all when no exact match exists — the whole system silently fails.
Lazy learning looks cheap but is not: every prediction pays the full distance bill.
A single nearby noisy sample can hijack a small neighborhood's verdict — the K = 1 story in 9.2.

Recap. Eager learning builds one global model up front (high training cost, low test cost); lazy learning stores the data and computes at test time (low training cost, high test cost), combining many local decisions into one implicit global function. KNN is the classic lazy learner. Next: 9.2 turns "how many neighbors and how to break ties" into concrete choices.

Real-world: lazy, instance-based thinking shows up wherever the data itself must stay the final authority — pattern recognition systems, recommendation engines that compare you to similar users, and satellite-image classifiers that judge each pixel by the labeled pixels nearest to it. When the true boundary is too wiggly for a simple global model, storing examples and judging by neighbors is often the most reliable option.

9.2 The K Parameter and Tiebreakers

9.2.1 What K Means

In K-nearest neighbor, K is how many neighbors the algorithm considers for the final prediction. It is a parameter you give the algorithm: one neighbor, fifty neighbors, five hundred neighbors — all possible. The session then walks the same dataset through K = 1, K = 3, and K = 2 to show how the choice of K changes the answer.

K, written as a capital K, is the single knob the user turns. The same data and the same distance formula will produce different predictions for different K — which is why the parameter deserves care.

9.2.2 Worked Example: K = 1

Worked example: the closest single sample decides.

Binary problem with a positive class and a negative class, and a test sample in between. K = 1 means consider exactly one neighbor: the single closest training sample. The closest training sample to the test sample belongs to the negative class, so the predicted class is negative.

The rule in symbols: let $D_{z}$ be the set of the K training samples closest to the test sample $z$ . With K = 1, $D_{z}$ holds one sample, and the prediction is simply that sample's class. One vote, no counting needed.

Step 1: measure the distance from $z$ to every training sample.
Step 2: keep the single smallest distance.
Step 3: take that sample's class — negative.

Sense-check: the test point sits closer to the negative crowd than to any positive sample, so a strict one-neighbor rule says negative.

9.2.3 Worked Example: K = 3

Worked example: the same point, three neighbors, opposite answer.

Same data, same test sample, K = 3: look at the three closest training samples. Two are positive class, one is negative class. Majority voting — the simplest tiebreaker — gives positive. So the same dataset, same algorithm, with K = 1 gives negative and with K = 3 gives positive: two different predictions for the same test sample. The takeaway: K must be chosen intelligently, never randomly.

Majority voting as a formula: count the votes for each class among the K nearest samples, and predict the class with the most votes:

$y^= ar g v max i \in D_{z} \sum 1 (y_{i} = v)$

where $y^$ is the predicted class, $v$ runs over the possible class labels, $i$ runs over the samples in $D_{z}$ , $y_{i}$ is the class of the $i$ -th neighbor, and $1 (\cdot)$ is an indicator function that returns 1 when its statement is true and 0 otherwise.

Step 1: keep the three smallest distances.
Step 2: count classes among them — positive twice, negative once.
Step 3: majority wins — positive.

Sense-check: widening the circle to three neighbors flipped the verdict, because the test point sits near two positive samples that were just beyond the first neighbor. The outcome depends on where you draw the circle.

9.2.4 Worked Example: K = 2 and Distance-Weighted Voting

Worked example: a perfect tie, broken by distance.

With K = 2 the two nearest neighbors are one positive and one negative sample: a perfect tie. Majority voting cannot break it. The solution offered is distance weighting: weight each neighbor's vote by its distance from the test sample, with the weight inversely proportional to the distance:

$w_{i} \propto \frac{1}{d _{i}}$

where $w_{i}$ is the weight of the $i$ -th neighbor and $d_{i}$ is its distance from the test sample. Closer neighbors get more weight. In the example, the negative sample is closer to the test sample, so it receives more weight, and the prediction becomes negative. Many tiebreakers exist in the literature; majority voting is the simplest, and distance weighting is one step up.

Say the two neighbors sit at distances $d_{1} = 2$ and $d_{2} = 5$ . Their weights are $w_{1} = 1/2 = 0.5$ and $w_{2} = 1/5 = 0.2$ . The closer neighbor (negative class) carries 0.5 of a vote against 0.2 for the farther one (positive class), so the weighted total favors negative.

Step 1: find the two closest samples — one positive, one negative.
Step 2: weight each by $w_{i} = 1/ d_{i}$ .
Step 3: compare weighted vote totals — the closer sample's class (negative) wins.

Sense-check: distance weighting reads naturally as "the closer it is, the more it speaks for the test sample," and it needs no extra machinery — only the distances already computed.

Notation note: many texts weight the vote with the inverse square of the distance, $w_{i} = 1/ d_{i}^{2}$ , which damps far neighbors even harder; the session's inverse form $1/ d_{i}$ is the simpler variant. Either breaks the tie, and both agree that closer means more influence.

9.2.5 Choosing K: Too Small, Too Large, and Just Right

If K is too small, you get highly unstable, highly variable decision boundaries that are very sensitive to noise and have a high chance of overfitting, meaning over-learning the data. If K is too large — think of K = infinity — the dominant class in the dataset dominates everything: with 50 positive samples and 10 negative samples in the training set, every test sample anywhere would be predicted positive, because its neighborhood is majority positive.

So K should be neither very small nor very large, but somewhere in the middle, and there is no thumb rule to find it. The honest procedure is empirical: use cross-validation — the K-fold cross-validation seen earlier in the course — and keep track of the training error through the process, checking again and again whether the error is coming down.

The golf recap makes the same point: if the matched training samples split two negatives and two positives, you are stuck again — change K, or use a better weighting factor or tiebreaker.

Exam note: the question "how do we determine the value of K?" was explicitly flagged as an important question in this session. The answer pattern to reproduce: too small K → unstable boundaries and overfitting; K → infinity → the dominant class swallows everything; the correct procedure → empirical search with cross-validation while watching the error, and no thumb rule.

9.2.6 Worked Example: A Noisy Point with 1-NN vs 3-NN

Worked example: one noisy neighbor vs three honest ones.

The same dataset appears on the left and right; the left side uses one nearest neighbor, the right side uses three. For a test point, the closest training point under 1-NN is a blue point that looks like a noisy sample: the classification boundary ought to sit elsewhere, since most red samples lie above it and most blue samples below it. Treating that blue point as the single neighbor, 1-NN predicts the wrong class.

With 3-NN, the same test point looks at three neighbors. Even if the closest one is the noisy point, the other two neighbors belong to the correct class, so the majority is right and the prediction is correct. This is the concrete reason K should not be very low: a single noisy neighbor can hijack the prediction.

Step 1: with K = 1, the lone closest sample is a mislabeled blue outlier — the prediction is the wrong class.
Step 2: with K = 3, the two next-closest samples are correctly labeled — the majority says the right class.

Sense-check: majority voting is a small insurance policy — three honest votes outweigh one stray vote. The geometry of this example returns in 9.3, where small K produces boundaries that hug every point.

9.2.7 Student Questions and Answers

Q: How do we determine the value of K? A: If K is too small you get unstable boundaries and overfitting; if K is infinite, the dominant class dominates everything. Choose K empirically: do cross-validation, keep a track of the training error throughout, and pick a value in the middle. There is no thumb rule.

Q: How do we do the weighting calculation in golf? A: In the golf data we could not find a tuple where all four attributes matched, so we matched three attributes and found four such tuples: three said yes, one said no, so the prediction was yes. And if the matched tuples tie two-to-two, you change the value of K or use a better weighting factor.

Q: How does KNN work in regression? A: The neighborhood idea carries over with one change: instead of voting on a class, average the target values of the K nearest samples — the average of the neighbors' real-valued labels. The session pointed out a specific example in the literature — post on the forum and the exact reference follows.

Pitfalls.

Randomly chosen K: the same data gave negative with K = 1 and positive with K = 3 — never leave K to chance.
Even K in a two-class problem invites ties; distance weighting or an odd K sidesteps them.
Watching only the training error without cross-validation can fool you — the model can overfit the training set while generalizing badly.

Recap. K decides how many neighbors vote; majority voting is the default tiebreaker and distance weighting ( $w_{i} \propto 1/ d_{i}$ ) the upgrade; K is chosen empirically with cross-validation because small K overfits and huge K drowns the signal. Next: 9.3 shows the geometry of these neighborhoods — Voronoi cells — and why many local lines make one global boundary.

9.3 Voronoi Cells and the Decision Boundary

9.3.1 What a Voronoi Cell Is

The Voronoi cell answers a geometric question: what is the area of influence of one training sample? If a test sample falls inside that area, it comes under the influence of that training sample, and the training sample's class label is assigned to it. The idea is explained for one nearest neighbor, but it extends to K-nearest neighbor as well.

A Voronoi cell (the region of the space where one training sample is the nearest sample) answers "who owns this patch of space?" Every point in the cell is closer to its owner than to any other training sample, and the collection of all cells covers the whole space with no gaps and no overlaps.

9.3.2 Building the Boundaries: Perpendicular Bisectors

To find the boundary of a training sample's cell, take each of its neighbors in turn. Connect the training sample to a neighbor with a line segment, then draw the perpendicular at the midpoint of that segment — the perpendicular bisector. Every point on one side of that bisector is closer to our training sample; every point on the other side is closer to the neighbor. Repeat for every neighbor: on the left side, on the right side, on the top — connect, bisect, and the enclosing region is the Voronoi cell. Do this for all training samples and the whole space divides into cells.

Why the midpoint? A perpendicular bisector (a line through the midpoint of a segment, at right angles to it) is exactly the set of points that are equally far from the two ends of the segment. Points on one side are closer to one endpoint; points on the other side are closer to the other. So the bisector is a natural border: both neighbors are equal exactly on the line, and stepping off it decides the winner.

Intuition — two points on a line. Take two samples A = (0, 0) and B = (2, 0). A point P = (x, y) is equally far from both when its distances match:

$(x - 0)^{2} + (y - 0)^{2} = (x - 2)^{2} + (y - 0)^{2}$

Square both sides and expand the right-hand side:

$x^{2} + y^{2} = (x - 2)^{2} + y^{2} = x^{2} - 4 x + 4 + y^{2}$

Cancel $x^{2} + y^{2}$ from both sides: $0 = - 4 x + 4$ , so $x = 1$ . The tie line is the vertical line through the midpoint (1, 0) — the perpendicular bisector. Any point with $x < 1$ is closer to A; any point with $x > 1$ is closer to B.

9.3.3 Voronoi Tessellation and the Classification Boundary

Doing this for every training sample produces a Voronoi tessellation: a partition of the space into regions, one per training sample. Building on the cells, we derive the classification boundary. In the example, blue and red classes are spread across the cells, and the model still has to predict red or blue, so it needs a boundary between them.

The key rule: boundaries are drawn only where two neighboring cells belong to different classes. Where both samples around a candidate boundary belong to the same class, no decision boundary is placed there. The line segments that separate cells of different classes form the classification boundary of the KNN model. That boundary is what this classifier offers instead of a tree or a rule set.

A Voronoi tessellation (a tiling of the space into cells, one per sample, so every location is assigned to its nearest sample) is the full mosaic. The classification boundary is then a subset of the tessellation edges: a blue cell and a red cell sharing a border need that border; two red cells sharing a border do not. The result is a piecewise-linear boundary — jagged, but completely data-driven. A useful fact from the geometry: for $n$ samples there are on the order of $n^{2}$ candidate bisectors, yet the full tessellation can be built in about $n lo g n$ steps.

9.3.4 Local Lines into a Global Boundary

Now the deferred idea pays off. Each boundary segment is a local linear function — literally a straight line between two samples. Combining many local linear functions produces an implicit global approximation: a highly complex, nonlinear final boundary. Lazy methods build a richer hypothesis space by combining many local hypotheses, and the KNN boundary is exactly that — many local lines stitched into one global boundary.

Remember the "hold this thought" from 9.1: each bisector is a tiny linear rule — "left of this line means A, right of it means B." No single line explains the whole space, but the mosaic of lines does. This is how lazy learning chases boundaries that a single global model cannot express.

9.3.5 Overfitting in 1-NN

One limitation of the approach: with a single neighbor, the model can overfit the data. The 1-NN boundary hugs every training point; the 3-NN boundary is smoother. This is the geometry behind the earlier warning that small K overfits.

Pitfalls.

With K = 1 the boundary passes through every training point — the decision surface is a perfect memory of the training set, including its mistakes.
Larger K merges cells before voting, so the boundary smooths out and noisy samples lose their personal cells.
The boundary complexity grows with the data size, and the tessellation cost is paid at test time — nothing about KNN is free when a query arrives.

Recap. A Voronoi cell is the area of influence of one training sample; perpendicular bisectors between samples carve the space into a tessellation; the edges between differently labeled cells form KNN's classification boundary — many local linear pieces forming one global nonlinear boundary. Next: 9.4 supplies the ruler — the distance formulas that decide "closest."

Real-world: Voronoi thinking appears wherever "nearest facility" matters — cellular networks assign every location to the nearest tower, and logistics systems route each address to the nearest depot. The KNN classifier uses the same geometry for prediction: whoever owns the territory owns the label.

9.4 Distance Metrics and Euclidean Distance

9.4.1 Three Distance Measures

To find nearest neighbors we need a distance metric — a way to measure how far apart two points are. Three measures are named: Euclidean distance, Manhattan distance, and Hamming distance. The session works through Euclidean distance in detail.

A distance metric (a rule that turns two points into a non-negative number saying how far apart they are) is the ruler KNN uses. The three named rulers suit different data:

Euclidean distance — the straight-line distance "as the crow flies," for numeric attributes.
Manhattan distance — the distance along grid lines, also called city-block or L1 distance: in two dimensions it is the sum of absolute differences, $∣ x_{1} - x_{2} ∣ + ∣ y_{1} - y_{2} ∣$ , the distance a taxi drives on a rectangular street grid.
Hamming distance — for strings of equal length: count the positions where the two strings differ.

9.4.2 Euclidean Distance Between Two Points

Take two points A and B in two-dimensional space. The horizontal separation is $x_{2} - x_{1}$ , and the vertical separation is $y_{2} - y_{1}$ . The build-up in the session: "you compute P and Q and then finally it would be like this — P square plus Q square under root," with $P = x_{2} - x_{1}$ and $Q = y_{2} - y_{1}$ . So:

$d (A, B) = P^{2} + Q^{2} = (x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2}$

where $d (A, B)$ is the Euclidean distance between points A and B, and $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ are their coordinates.

The formula is the Pythagorean rule: the horizontal gap and the vertical gap are the two legs of a right triangle, and the distance is the hypotenuse. That is why squaring appears — it removes signs and honors the geometry.

A practical tip from the session: keep the subtraction order uniform — always $x_{2} - x_{1}$ or always $x_{1} - x_{2}$ . The squaring removes the sign anyway, so consistency avoids mistakes.

Worked example: two points, one number.

Take A = (1, 2) and B = (4, 6). Then:

$P Q d (A, B) = x_{2} - x_{1} = 4 - 1 = 3 = y_{2} - y_{1} = 6 - 2 = 4 = 3^{2} + 4^{2} = 9 + 16 = 25 = 5$

The two points are 5 units apart. Sense-check: a 3-4-5 triangle is the classic right triangle, and the arithmetic confirms it — horizontal gap 3, vertical gap 4, straight-line distance 5.

9.4.3 The Formula in D Dimensions

In a dataset with many attributes, the same idea extends term by term. The session describes it with named dimensions: "under root of $A_{2} - A_{1}$ square plus $B_{2} - B_{1}$ square and so on." Written out:

$d (A, B) = (a_{1} - b_{1})^{2} + (a_{2} - b_{2})^{2} + \dots + (a_{D} - b_{D})^{2} = i = 1 \sum D (a_{i} - b_{i})^{2}$

where $a_{i}$ and $b_{i}$ are the $i$ -th coordinates of points A and B, and $D$ is the number of dimensions. The formula has exactly one term per dimension — and that single fact drives the curse of dimensionality below.

The sum runs over all $D$ dimensions: every attribute contributes its own squared difference. Add one attribute and you add one term to every distance you ever compute.

Worked example: three dimensions.

Take A = (1, 2, 3) and B = (4, 6, 7):

$d (A, B) = (4 - 1)^{2} + (6 - 2)^{2} + (7 - 3)^{2} = 3^{2} + 4^{2} + 4^{2} = 9 + 16 + 16 = 41 \approx 6.40$

Sense-check: adding a third term grew the distance beyond the two-dimensional case (where it was 5) — every dimension adds information, and every dimension adds work.

Recap. Distance is the ruler of KNN: Euclidean (straight line, one squared term per dimension), Manhattan (grid walking), and Hamming (counting differing positions). The Euclidean formula has exactly one term per dimension — a fact that returns as the curse of dimensionality in 9.6.

9.5 The Nearest-Neighbor Search Procedure and Complexity

9.5.1 How KNN Finds Its Neighbors

Prediction is a two-step process at test time. First, compute the distance from the test point to every training point — all of them, one by one. Second, sort the distances in ascending order, with the minimum distance at the top and the largest at the end, and take the K nearest neighbors. The majority class among those K neighbors is the prediction.

Purpose. KNN must answer one question at test time: which K stored samples are closest to this new sample? Everything else — no model, no rules, no training pass — is skipped. Inputs and outputs. Inputs: the stored training set (N samples, each with D numeric attributes and a class label), the test sample, the parameter K, and a distance formula. Output: the predicted class label of the test sample.

The procedure itself, step by step:

Steps.

For the test sample $z$ , compute $d (z, x_{i})$ against every training sample $x_{i}$ , for $i = 1, \dots, N$ , using the chosen distance formula.
Collect the N distances into a list.
Sort the list in ascending order — smallest first.
Read off the first K entries; their training samples are the K nearest neighbors.
Count class labels among the K neighbors (majority voting) and output the winning class.

9.5.2 Complexity: O(D), O(ND), and Sorting

With $N$ training examples in $D$ dimensions, one distance computation touches every dimension, so a single distance costs $O (D)$ . Computing the distance from the test point to all $N$ examples costs:

$O (N \cdot D)$

because there are $N$ points, each requiring $D$ work. Sorting the $N$ distances adds another term. The session stated a sorting complexity of $O (N K)$ ; the standard count for sorting $N$ numbers with a comparison sort is $O (N lo g N)$ , so the spoken form is a garbled version of the sorting step. Whichever way we count it, the message is the same: as the number of dimensions grows, the cost of KNN grows drastically.

Why $O (N lo g N)$ for the sort? Sorting N distances arranges N items, and each comparison between two distances settles part of the ordering; a comparison sort needs about $lo g_{2} N$ comparisons per item, so the whole sort costs $N lo g_{2} N$ — written $O (N lo g N)$ . Two refinements matter in practice: only the K smallest distances are wanted, so a partial selection can be cheaper than a full sort, and indexed structures (search trees, KD-trees) can replace the full distance scan with about $O (lo g N)$ comparisons per query.

9.5.3 Why the Cost Grows with Dimensions

Every extra dimension adds one more term to every distance computation, and we compute distances to every training point for every test point. Ten dimensions make the formula ten terms long; a thousand dimensions make it a thousand terms long. Nothing is cached in advance — that is the price of being lazy — so high-dimensional data makes KNN genuinely expensive.

Trace — a tiny run. Suppose N = 3 training samples in 2 dimensions: $x_{1} = (0, 0)$ , $x_{2} = (1, 0)$ , $x_{3} = (0, 2)$ , and test sample $z = (0.2, 0.1)$ with K = 2.

Distances (Euclidean): $d (z, x_{1}) = 0. 2^{2} + 0. 1^{2} = 0.05 \approx 0.22$ ; $d (z, x_{2}) = 0. 8^{2} + 0. 1^{2} = 0.65 \approx 0.81$ ; $d (z, x_{3}) = 0. 2^{2} + 1. 9^{2} = 3.65 \approx 1.91$ .
Sorted ascending: 0.22 ( $x_{1}$ ), 0.81 ( $x_{2}$ ), 1.91 ( $x_{3}$ ).
K = 2 nearest: $x_{1}$ and $x_{2}$ . If both carry the class "yes," the prediction is "yes."

Sense-check: each of the 3 distances needed 2 squared terms (D = 2), and the run sorted 3 numbers — both cost factors, N and D, are visible in this miniature run.

When to use / alternatives. KNN is the right tool when the boundary is complex, training is cheap, and test-time latency is tolerable. When queries must be fast on huge data, the alternatives step in: build an index (search trees, KD-trees) to avoid the full scan, subsample or prune the stored set (editing and condensing), or switch to an eager model that pays its cost once at training.

Recap. KNN prediction = compute all N distances (each O(D)) → sort (O(N log N)) → vote among the K smallest. The lazy design moves the whole bill to test time, and every added dimension raises every distance bill. Next: 9.6 collects what actually goes wrong — the curse of dimensionality, counterintuitive distances, and the scaling problem.

9.6 Limitations of KNN

9.6.1 Curse of Dimensionality

The first limitation is the curse of dimensionality: as you increase the number of features in the dataset, the performance of the classification model decreases drastically. The reason is computational. With 50 dimensions, each distance is a 50-term computation; with 5,000 dimensions, each distance sums 5,000 squared differences, using "all 5,000 dimensions" as the session puts it. Since the distance formula has one term per dimension and we must compute distances to every training point, the computation explodes as dimensions grow.

Formalize. The cost sits inside the formula itself: $d (A, B) = \sum_{i = 1}^{D} (a_{i} - b_{i})^{2}$ . One distance costs $O (D)$ ; distances to all N training samples cost $O (N D)$ . Doubling the dimensions doubles every distance computation — and the problem is deeper than speed: in many dimensions, neighborhoods become mostly empty, so the stored samples are too far apart to judge anything locally.

9.6.2 Counterintuitive Results

A second issue: KNN is sometimes counterintuitive. Four examples A, B, C, and D live in three dimensions (attributes D1, D2, D3). The distance between A and B comes out to 1.4, and the distance between C and D also comes out to 1.4 — yet the two pairs of points are very different from each other. Distance is a single number; it compresses all the differences down to one value, and relying on distance alone can produce results that look wrong.

Worked example: same distance, different pairs.

Let A = (0, 0, 0), B = (1, 1, 0), C = (0, 0, 1), D = (1, 1, 1), with the three attributes (D1, D2, D3):

$d (A, B) = (1 - 0)^{2} + (1 - 0)^{2} + (0 - 0)^{2} = 2 \approx 1.4$

$d (C, D) = (1 - 0)^{2} + (1 - 0)^{2} + (1 - 1)^{2} = 2 \approx 1.4$

Both pairs are about 1.4 apart — the value the session quoted — yet the pairs are completely different: the first pair moves within the D1-D2 plane, the second pair moves identically but one level up in D3. Distance collapses six numbers into two identical scalars. Sense-check: this is not a bug in the formula — it is the formula working as designed. Distance is a summary, and summaries throw information away; KNN must live with that.

9.6.3 The Scaling Problem

A third issue is scaling. Attributes with higher scales become dominant. Consider height, weight, and income: height in meters runs from about 1.5 to 1.8, weight in pounds runs into the hundreds, and income in dollars runs even higher. In absolute value, the attribute with the larger numbers dominates all computations in KNN — whether or not it is the attribute that actually separates the classes.

9.6.4 Worked Example: S1, S2, S3

Worked example: the bigger-number attribute hijacks the vote.

The demo dataset has two attributes. Training samples S1 and S2 and test sample S3 take the values S1 = (1, 150), S2 = (2, 110), and S3 = (1, 100). The distances:

$d (S_{1}, S_{3}) = (1 - 1)^{2} + (150 - 100)^{2} = 0 + 2500 = 50$

$d (S_{2}, S_{3}) = (2 - 1)^{2} + (110 - 100)^{2} = 1 + 100 = 101 \approx 10.05$

The session quoted the second distance as 10.5; the exact value is $101 \approx 10.05$ , so the spoken figure was a rounding.

Since 10.05 is less than 50, the test sample S3 is closer to S2, so S2's class label is assigned to S3. Now look at what actually separates the two training samples: attribute 1 doubles between S1 and S2 (1 to 2), while attribute 2 barely moves relative to its scale. Attribute 1 is the real differentiator — the discriminatory feature. But attribute 2 has much larger absolute values, so it dominates the Euclidean distance calculation, and the classifier effectively ignores the attribute that matters. Both distance computations run almost entirely through the attribute-2 part of the formula.

Step 1: compute both distances term by term. In $d (S_{1}, S_{3})$ , the attribute-2 term contributes 2500 of the 2500 inside the root; in $d (S_{2}, S_{3})$ , it contributes 100 of the 101. Attribute 1 contributes 0 and 1.
Step 2: compare — 10.05 < 50, so S3 takes S2's class.
Step 3: diagnose — the decision ran on attribute 2 alone, although attribute 1 is the discriminatory feature (it doubles between S1 and S2 while attribute 2 only moves 150 to 110 on a hundreds-range scale).

Sense-check: if the attributes had been scaled to comparable ranges, attribute 1's doubling would have registered in the distance, and the classifier could have seen the information it is currently blind to.

Exam note: this scaling computation is exactly the kind of numerical that appeared in the pre-processing question of the mid-semester exam, which students found lengthy — practice it until the steps are fast.

9.6.5 Fixing the Scale

The fix is scaling in the pre-processing stage. Z-score scaling, min-max scaling, and decimal scaling all get the attribute values into similar ranges, and then the Euclidean distance sees both attributes fairly. There is no set formula for whether you scale attribute 1 up to match attribute 2 or scale attribute 2 down — both work; the requirement is that both attributes sit on the same scale. A discriminatory feature is one that helps in classification and prediction; if its scale is small while a less informative feature has a huge scale, the distance measure follows the scale, not the information. This is not a KNN-only problem: any algorithm in data mining that works on a distance measure suffers the same way when attributes are not scaled.

The three scaling tools, briefly (worked in full in the pre-processing lectures): min-max scaling maps a value $v$ into a fixed range, z-score scaling centers the attribute on its mean and divides by the standard deviation, and decimal scaling moves the decimal point. All three exist to make "one unit on attribute 1" mean the same kind of thing as "one unit on attribute 2."

9.6.6 Student Questions and Answers

Q: Why does the performance of the classification model come down when we increase the number of dimensions? A: Because the distance formula has one term per dimension — with 50 dimensions you compute 50 terms, with 5,000 dimensions you compute 5,000 terms — and the distance between points must be computed with all of them. The computations increase drastically, and that is why KNN suffers from the curse of dimensionality.

Pitfalls.

Unscaled attributes: a feature measured in thousands silently outvotes a feature measured in single digits, whether or not it matters.
Treating distance as the whole truth: identical distances can hide completely different pairs of points.
Adding features naively: more dimensions means slower computation and thinner neighborhoods.

Recap. KNN has three known weaknesses: the curse of dimensionality (cost grows with D), counterintuitive distances (one number hides the detail), and the scaling problem (big-number attributes dominate). The scaling problem has a standard fix in pre-processing; the other two are structural. Next: 9.7 compares KNN with decision trees — when locality beats greediness.

9.7 KNN vs Decision Trees: Missing Data and Complex Boundaries

9.7.1 How Each Algorithm Thinks

The session compared the algorithms on how they think. Decision trees work on a greedy strategy: at each step, pick the best split. KNN works on locality: look into the neighborhood, and whatever class dominates the neighborhood is the test sample's class. Naive Bayes was not covered in this session — it comes next in the classification series.

Comparison — greedy vs local. The two algorithms sit on opposite sides of the same map:

	Decision tree	KNN
Strategy	Greedy: at each node, pick the best split	Local: whatever class dominates the neighborhood
Training	Eager: build the tree up front	Lazy: store the data
Hypothesis	One global model	Many local pieces combined
Boundary shape	Rectilinear rectangles	Arbitrary, wiggly pieces

The one-line pick: when the true boundary is axis-aligned and simple, a tree is compact and fast; when the boundary is genuinely wiggly, locality wins.

9.7.2 Missing Data Handling

How do the algorithms handle missing data? With a decision tree, you might want to skip the attribute or skip the tuple. With KNN, you can calculate the mean of the attribute and fill the missing value with it. KNN also degrades as the curse of dimensionality sets in — the closeness logic that works in two dimensions thins out in many.

9.7.3 Complex Boundaries: Where KNN Shines

KNN behaves very well on problems whose true classification boundary is complex and nonlinear — the kind of wiggly boundary where a shape-based classifier struggles. A decision tree would break the sample space into multiple rectangles recursively; to approximate such a boundary it would need huge depth, and the rectangular boundary would never be clean. In these cases the neighborhood approach gives better visualization and better prediction power than a decision tree. That is a good reason to keep KNN in the toolbox even though it is simple.

Why the shapes differ. A tree splits on one attribute at a time — every boundary line is perpendicular to an axis, so the decision region is a union of rectangles. KNN's Voronoi boundary (9.3) is made of bisectors at any angle, so it can follow a diagonal or curved frontier with small straight pieces. A diagonal boundary is exactly what a rectangle-based model approximates badly: it needs many small boxes to trace one straight slanted line.

Real-world: this is why nearest-neighbor thinking still appears inside modern systems — complex, wiggly decision regions are common in real data, and locality handles them naturally.

9.7.4 What to Study Next

Naive Bayes and SVM were not covered in the session due to lack of time; both are available in the recorded lecture series, and finishing them is the homework from this session. The listed books are the reference to study from.

Recap. Decision trees think greedily and draw rectangle boundaries; KNN thinks locally and draws piecewise-linear boundaries that hug complex shapes. Missing values: trees skip, KNN fills by the mean. Next: 9.8 steps back from individual classifiers to the ensemble question — many predictors instead of one.

9.8 Ensemble Methods: The Big Idea

Ensemble methods are the last topic of the classification unit, and they rest on one idea: many predictors are better than a single predictor. Instead of using one decision tree, use many trees and combine their results at the end.

9.8.1 Wisdom of the Crowd

Hook. If ten doctors each examine you and nine say "flu," would you really prefer one doctor's answer over the nine? An ensemble is that bet, made with classifiers instead of doctors.

Real-world: this is the wisdom of the crowd, made famous by quiz shows. In the quiz show KBC (Kaun Banega Crorepati), there are two lifelines: phone-a-friend asks one expert — that is a single predictor — while the audience poll asks a room full of people and aggregates their answers. The audience poll is an ensemble: many votes, aggregated into one answer. The aggregated answer of a crowd is famously reliable, and ensemble methods industrialize that effect.

An ensemble (a set of predictors whose answers are combined into one final answer) works precisely because the members are not copies of each other: different members make different mistakes, and the mistakes cancel while the correct answers stack.

9.8.2 Many Predictors Instead of One

Instead of one decision tree, use five trees or fifty trees. The tree is just an example: the predictors can all come from one algorithm — that is the structure family question of bagging versus boosting — or from different algorithms: decision trees, SVM, naive Bayes, any combination. Every model predicts something, and the final step aggregates the predictions into one answer. Named members of the family: Random Forest, AdaBoost, Gradient Boost, Histogram Boost, and XGBoost.

The family tree (briefly). Random Forest grows many trees on random subsets of the data and features; AdaBoost trains a sequence of weak learners, each one focusing on the mistakes of the previous; Gradient Boost builds the sequence by fitting each new model to the remaining error; Histogram Boost (the histogram-based variant used by modern libraries) and XGBoost are fast, highly engineered members of the same boosting family. The exact structure details — bagging vs boosting — are the promised content of the next class; the point here is that all of them are "many predictors, one answer."

Real-world: Random Forest, AdaBoost, Gradient Boost, and friends are the workhorse of production machine learning — deployed across countless systems today.

9.8.3 The Two Key Design Questions

Two issues define an ensemble design. First: which classification algorithms, and what structure? How does the structure look in bagging, and how does it look in boosting? The session promises these for the next class. Second: how do we aggregate the results? If all models agree, aggregation is easy; if they disagree, we need a rule. The session spends its time on aggregation and defers structure.

9.8.4 Why Ensemble Works

Two statistical arguments. First, ensembles improve generalization performance: instead of rote-learning minute details, the combined model keeps a general idea about the data. Second, an ensemble reduces the risk of selecting one poorly performing classifier. Suppose you believe decision trees always work, and you build one on some data that gives 50% accuracy. A single bad pick is a total loss; with a group of classifiers, the bad pick is diluted and the group's generalizable capability improves. Formally: a series of classifiers $M_{1}, \dots, M_{K}$ is combined into a final predictor $M^{*}$ that makes the final prediction.

Two conditions make the argument work: the members should do better than random guessing, and their errors should be as independent as possible. Correlated members — all trained on the same data the same way — fail like one big classifier with many heads.

9.8.5 The Error Example: 0.35 to 0.06

Worked example: twenty-five weak classifiers beat any one of them.

The quantitative claim: each individual classification model makes an error of 0.35. Combined in a particular order — in a particular sequence — the overall error drops to 0.06. Combining properly decreases the overall error of the model and improves its generalization capability at the same time. That is the promise ensemble methods make, and it is why production systems use them.

Where the numbers come from: suppose 25 binary classifiers, each with error rate $ε = 0.35$ , vote by majority. If their errors are independent, the ensemble is wrong only when 13 or more of the 25 members are wrong at once. That probability is the binomial tail:

$e_{ensemble} = i = 13 \sum 25 (i 25) ε^{i} (1 - ε)^{25 - i} = i = 13 \sum 25 (i 25) 0.3 5^{i} \cdot 0.6 5^{25 - i} \approx 0.06$

Each term picks which $i$ members fail — $(i 25)$ choices — multiplies their failure probability $ε^{i}$ by the success probability of the rest $(1 - ε)^{25 - i}$ , and the sum over $i = 13, \dots, 25$ collects every way the majority can be wrong. The total evaluates to about 0.06 — the number the session quoted.

Sense-check: if the classifiers were identical instead of independent, they would fail on exactly the same examples and the ensemble error would stay 0.35 — independence is the whole engine. And if a member were worse than random guessing ( $ε > 0.5$ ), the majority of a crowd of bad guesses is a bad guess; the 0.35 to 0.06 magic requires better-than-random, weakly correlated members.

Exam note: the 0.35 to 0.06 figure is the standard illustration of why ensembles work. Remember both numbers, the conditions (better than random, independent errors), and the meaning of the binomial tail formula: majority voting fails only when more than half of the members fail together.

Real-world: production machine learning leans on ensembles — credit scoring, fraud detection, recommender systems, and antivirus engines all ship ensembles, because a 0.35-error model improved to 0.06 is a very different product.

Pitfalls.

Copying the same model five times is not an ensemble — identical members make identical mistakes.
A member worse than random guessing drags the vote down.
Aggregation needs a rule; "combine somehow" without a plan is not an ensemble design.

Recap. Ensembles answer "many predictors instead of one": diverse members, aggregated answers, better generalization, and lower risk of a bad single pick. Two design questions follow — structure (bagging vs boosting, next class) and aggregation (9.9, now).

9.9 Aggregating Predictions: Four Strategies

9.9.1 Committee: Majority Voting and Unweighted Average

The first aggregation strategy is the committee. In classification, a committee is simple majority voting, like an election: count the positive votes against the negative votes; if more models say positive, the ensemble predicts positive, otherwise negative. Like a department committee resolving a conflict, each member gets one vote and the majority wins.

In regression, the committee is an unweighted average.

Worked example: three petrol price forecasts.

Real-world: predicting the price of petrol — model one predicts price $P_{1} = 102$ , model two predicts $P_{2} = 98$ , model three predicts $P_{3} = 106$ , and the ensemble prediction is simply the average:

$P_{ens} = \frac{P _{1} + P _{2} + P _{3}}{3} = \frac{102 + 98 + 106}{3} = \frac{306}{3} = 102$

Sense-check: 102 lies between the three forecasts, and the individual misses tend to cancel — averaging multiple price forecasts is a standard practice for combining estimates in regression settings.

9.9.2 Weighted Average

The weighted average gives each model a vote of different weight. With models $Y_{1}, Y_{2}, Y_{3}$ built on the same data, the ensemble prediction is the aggregation of weighted predictions:

$y^_{ens} = i \sum α_{i} Y_{i}$

where $Y_{i}$ is the prediction of the $i$ -th model and $α_{i}$ is the weight of the $i$ -th model. The weights are not equal, and there are sensible rules for setting them: weight directly proportional to accuracy (the high-accuracy model gets more weight); weight inversely proportional to variance (the model whose results vary least gets more weight, because it steadies the ensemble); and weight inversely proportional to error (low error, high weight; high error, low weight). Committee voting is the special case where all weights are equal.

The weights usually sum to 1, so the weighted average is a convex combination — a compromise point pulled toward the models that deserve trust. The committee of 9.9.1 is exactly the special case $α_{i} = 1/ K$ for all $i$ .

Worked example: a weighted three-model forecast.

Models $Y_{1}, Y_{2}, Y_{3}$ predict 90, 80, and 100. Weights chosen from accuracy: $α_{1} = 0.5$ , $α_{2} = 0.2$ , $α_{3} = 0.3$ , which sum to 1:

$y^_{ens} = 0.5 \cdot 90 + 0.2 \cdot 80 + 0.3 \cdot 100 = 45 + 16 + 30 = 91$

Sense-check: the plain average would be 90; the weights pull the answer toward the most accurate model (which predicted 90), landing at 91.

9.9.3 Predictors of Predictor

The third strategy builds a new model on top of the old ones. Models Y1, Y2, and Y3 each predict a class label. Now build another classification model whose features are those predicted class labels — Y1, Y2, Y3 — instead of the original features X. The second-level model learns a classification boundary over the first-level predictions, which is why the strategy is called a predictor of predictor. Notably, neural networks work on this principle: layer after layer, each predictor is a function of earlier predictors.

A miniature stacking setup: level 1 models produce one vote per sample; each sample is now described by the vector of votes (Y1, Y2, Y3); a level 2 model is trained on those vote vectors and makes the final call. The level 2 model can exploit patterns in the disagreement — for example, "whenever Y1 and Y3 disagree but Y2 is confident, trust Y2."

9.9.4 Mixture of Experts

The fourth strategy is the mixture of experts. Divide the entire vector space into partitions, and build a separate expert model for each partition. In a five-class example — positive, negative, circle, cross, triangle — partition one gets its own classification boundary, partition two contains a single class (no boundary needed), partition three gets its own boundary, and so on. When a test sample arrives, you do not run the complete model: you run only the expert built for the partition the test sample falls into. Each expert is a specialist in its region, and combining the specialists is an ensemble strategy.

Worked example: routing by region.

Suppose the space splits into three partitions. Partition A covers the region where the positive and negative classes meet: it gets a small classifier of its own. Partition B contains only circle samples: no boundary is needed there — any sample landing in B is labeled circle immediately. Partition C mixes cross and triangle: it gets its own boundary. A test sample arriving in B is handled by the B rule alone — the complete model never runs for it.

Sense-check: the whole space is covered by specialists, and each test sample is judged by the specialist for its region — one model per partition instead of one model for everything.

Pitfalls.

Equal weights where accuracy differs widely: the committee wastes the strongest votes.
Designing for agreement only: "all models agree" is the easy case; the design must also handle disagreement.
Mixture of experts with wrong partitions: if the partitions are misplaced, the specialists are experts in the wrong regions.

Real-world: the session notes these strategies are all available in the literature and used heavily in today's applications — mixture of experts, for example, routes each input to a specialist submodel, a design now common in large-scale language systems where different expert networks handle different kinds of input.

Recap. Four aggregation strategies: committee (majority vote / unweighted average), weighted average (trust by accuracy, variance, or error), predictors of predictor (a model of models), and mixture of experts (one specialist per region). This closes the classification unit — next comes association rule mining.

Exam Guidance Summary

The mid-semester exam feedback discussion sets the pattern for this course. The exam contains both theory and numerical questions, deliberately not dominated by either. Students found the pre-processing numerical lengthy — the scaling computations shown in this session are exactly that kind of numerical, so practice them until the steps are fast. Input from this session is considered for the comprehensive exam: the course listens to requests for more numericals, more programming, and more real-world context.

The assignment is most likely a combination of questions and classification, solved with coding; one quiz was dropped to make room for the assignment.
A classification tutorial is coming within the next few days, followed by clustering tutorials; tutorial sheets carry extra numerical practice because class time is limited (about 24 classes) and must balance concepts with numericals.
Real-world application classes come at the end of the course: how classification, clustering, and association rule mining solve today's problems, their challenges, and their research and implementation issues.
Homework from this session: Naive Bayes and SVM, available in the recorded lecture series, plus the reference books listed for study.
The question "how do we determine the value of K?" was flagged as an important question — the empirical cross-validation procedure for choosing K is core material.
Ensemble methods are the last classification topic; the session gives a basic background and continues with bagging and boosting structures in the next class.

Exam note: the two numerically testable items from this session are the Euclidean distance computations (including the scaling example, which appeared as a lengthy pre-processing numerical in the mid-semester exam) and the error-reduction argument behind ensembles (0.35 to 0.06, with the independence and better-than-random conditions attached). Both are practice-until-fast material.

Key Industry Applications

Real-world: golf play prediction is a small decision-support example of lazy learning in action — store the data, and judge each new day by its closest past days.
Real-world: the ensemble family is the workhorse of production machine learning: Random Forest, AdaBoost, Gradient Boost, Histogram Boost, and XGBoost power countless deployed systems.
Real-world: committee-style averaging of multiple forecasts (the petrol price example) is a standard practice for combining estimates in regression settings.
Real-world: mixture of experts models are used heavily in today's applications, routing each input to a specialist submodel.
Real-world: malware analysis and detection is a concrete research application — machine learning and deep learning models are used to build antivirus engines, a core research direction of the field.
Real-world: neural networks implement the predictors-of-predictor principle: each layer is a predictor built on the predictions of the previous layer.

DM Lecture 9 notes · K-Nearest Neighbor and Ensemble Methods

Data Mining· postgraduate· 2026-08-05

Sections Breakdown

19.1 Eager Learning vs Lazy Learning

Two learning styles: eager builds a model up front, lazy stores data and computes at test time; rote learning and nearest neighbor as flavors of lazy learning.

29.2 The K Parameter and Tiebreakers

How K sets the number of voting neighbors, worked examples for K = 1, 2, 3, tiebreakers including distance-weighted voting, and empirical K selection by cross-validation.

39.3 Voronoi Cells and the Decision Boundary

Voronoi cells as areas of influence, perpendicular bisectors, tessellation, and the piecewise-linear KNN classification boundary with overfitting at K = 1.

49.4 Distance Metrics and Euclidean Distance

Euclidean, Manhattan, and Hamming distances; the Euclidean formula with one term per dimension.

59.5 The Nearest-Neighbor Search Procedure and Complexity

The test-time procedure of computing, sorting, and voting; complexity O(D), O(ND), and the sorting step.

69.6 Limitations of KNN

Curse of dimensionality, counterintuitive distances, and the scaling problem with the worked S1, S2, S3 example and the pre-processing fix.

79.7 KNN vs Decision Trees: Missing Data and Complex Boundaries

Greedy rectangle boundaries versus local wiggly boundaries; missing-data handling; where KNN shines.

89.8 Ensemble Methods: The Big Idea

Many predictors instead of one: wisdom of the crowd, the two design questions, and the 0.35 to 0.06 error example.

99.9 Aggregating Predictions: Four Strategies

Committee, weighted average, predictors of predictor, and mixture of experts.

10Exam Guidance Summary

Exam format, numerically testable items, homework, and the flagged K-selection question.

11Key Industry Applications

Lazy learning, ensemble workhorses, forecast averaging, mixture of experts, malware analysis, and layered predictors in production systems.

Postgraduate students in Data Mining

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.

Eager Learning vs Lazy Learning

Must-know: Eager learning: build model first (high train time, low test time, single committed hypothesis, knowledge in the model). Lazy learning: store data, compute at test time (low train time, high test time, knowledge in the instances). KNN is lazy; trees, rules, naive Bayes are eager. Rote learning needs an exact match and fails without one.

⚠️ Top pitfall: Rote learning cannot predict at all when no exact match exists; lazy learning pays the full distance bill at every prediction.

Self-check: If a test sample arrives and all computation happens only then, which learning style is this?

Connects to: 9.2, 9.3

The K Parameter and Tiebreakers

Must-know: K = number of neighbors. K=1 vs K=3 can flip the same prediction. Tiebreakers: majority voting, then distance weighting. Choosing K: too small overfits, too large dominates; use cross-validation while tracking the error; no thumb rule.

$w_{i} \propto \frac{1}{d _{i}}$

⚠️ Top pitfall: A single noisy neighbor hijacks a 1-NN prediction; even K invites ties.

Self-check: Same data and same test point: K=1 gives negative, K=3 gives positive. What does this prove about K?

Connects to: 9.1, 9.3, 9.6

Voronoi Cells and the Decision Boundary

Must-know: Voronoi cell = region where one sample is nearest. Boundaries = perpendicular bisectors (points equidistant from two samples). Classification boundary = edges between cells of different classes only. Many local linear segments form an implicit global nonlinear boundary. 1-NN boundary hugs every point (overfits).

$d (P, A) = d (P, B) \Rightarrow x = 1$

⚠️ Top pitfall: With K=1 the boundary passes through every training point, memorizing noise.

Self-check: Why is no decision boundary drawn between two cells of the same class?

Connects to: 9.1, 9.2

Distance Metrics and Euclidean Distance

Must-know: Euclidean distance d(A,B) = sqrt((x2-x1)^2 + (y2-y1)^2); in D dimensions one term per dimension. Keep subtraction order consistent; squaring removes the sign. Manhattan = sum of absolute differences; Hamming = count of differing positions in equal-length strings.

$d (A, B) = i = 1 \sum D (a_{i} - b_{i})^{2}$

⚠️ Top pitfall: Inconsistent subtraction order invites sign mistakes, though squaring hides them.

Self-check: Compute the Euclidean distance between (1,2) and (4,6).

Connects to: 9.5, 9.6

The Nearest-Neighbor Search Procedure and Complexity

Must-know: Test-time procedure: compute all N distances, sort ascending, take K smallest, majority vote. Complexity: one distance O(D), all distances O(ND), sorting O(N log N). The session's stated O(NK) sorting cost is a garbled form of the standard O(N log N).

$O (N \cdot D)$

⚠️ Top pitfall: High-dimensional data makes KNN genuinely expensive because nothing is cached and every extra dimension adds a term to every distance.

Self-check: Why does adding one attribute raise the cost of every distance computation?

Connects to: 9.4, 9.6

Limitations of KNN

Must-know: Curse of dimensionality: 50 dimensions = 50 terms, 5,000 dimensions = 5,000 terms per distance. Identical distances can hide different pairs of points. Scaling example: S1=(1,150), S2=(2,110), S3=(1,100) gives d(S1,S3)=50 and d(S2,S3)=sqrt(101)≈10.05 (session quoted 10.5), so S3 takes S2's class even though attribute 1 is the discriminatory feature. Fix: z-score, min-max, or decimal scaling.

$d (S_{2}, S_{3}) = (2 - 1)^{2} + (110 - 100)^{2} = 101 \approx 10.05$

⚠️ Top pitfall: Unscaled attributes: a huge-scale feature dominates the distance whether or not it separates the classes.

Self-check: In the S1/S2/S3 example, which attribute dominates the distance computation and which one is actually discriminatory?

Connects to: 9.4, 9.5

KNN vs Decision Trees: Missing Data and Complex Boundaries

Must-know: Decision tree = greedy, eager, single global model, rectangle (rectilinear) boundaries. KNN = local, lazy, arbitrary wiggly boundaries. Missing values: tree skips attribute/tuple; KNN fills the attribute mean. Complex nonlinear boundaries are where KNN beats trees.

⚠️ Top pitfall: A tree approximates a diagonal boundary with many rectangles; KNN follows it with angled bisector pieces.

Self-check: Which algorithm draws boundaries at any angle, and why can it do that?

Connects to: 9.3, 9.8

Ensemble Methods: The Big Idea

Must-know: Ensemble = many predictors, one aggregated answer. Design questions: (1) structure — bagging vs boosting (next class); (2) aggregation rule. Conditions: members better than random, errors independent. 25 classifiers with error 0.35, majority vote, independent errors: binomial tail sum from i=13 to 25 of C(25,i) 0.35^i 0.65^(25-i) = 0.06.

$e_{ens} = i = 13 \sum 25 (i 25) 0.3 5^{i} \cdot 0.6 5^{25 - i} \approx 0.06$

⚠️ Top pitfall: Identical classifiers fail identically — the ensemble error stays 0.35 without independence.

Self-check: Why does the ensemble error stay 0.35 if the base classifiers are identical rather than independent?

Connects to: 9.9

Aggregating Predictions: Four Strategies

Must-know: Committee: majority vote (classification), unweighted average (regression) — equal weights. Weighted average: y_hat = sum of alpha_i * Y_i; weights proportional to accuracy, inversely proportional to variance, inversely proportional to error; committee is the equal-weight special case. Predictors of predictor: model trained on predicted labels (stacking; neural networks layer by layer). Mixture of experts: partition the space, one expert per partition, run only the expert of the test sample's partition.

$y^_{ens} = i \sum α_{i} Y_{i}$

⚠️ Top pitfall: Equal weights waste strong votes when accuracy differs; MoE needs correct partitions.

Self-check: If three models predict petrol prices 102, 98, and 106, what does the committee predict?

Connects to: 9.8

Exam Guidance Summary

Must-know: Practice distance and scaling computations until fast (mid-semester numericals were lengthy). How to determine K (cross-validation, track error) is an important question. Homework: Naive Bayes and SVM from the recorded series.

⚠️ Top pitfall: Running out of time on scaling numericals — practice until the steps are fast.

Self-check: Which two numerically testable items does this session contribute?

Connects to: 9.2, 9.6, 9.8

Key Industry Applications

Must-know: Ensemble family powers production ML; averaging forecasts is standard practice; mixture of experts routes inputs to specialist submodels; malware analysis builds antivirus engines; neural networks stack predictors layer by layer.

Self-check: Name one production system that relies on the ensemble family.

Connects to: 9.8, 9.9

Previous LectureLecture 08 · Rule-Based Classification

Next LectureLecture 10 · Ensemble Algorithms

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.

Prerequisite Knowledge

Previously Covered in This Subject

9.1 Eager Learning vs Lazy Learning

9.1.1 Eager Learning

9.1.2 Lazy Learning: Store, Don't Build

9.1.3 Train Time vs Test Time

9.1.4 Hypothesis Commitment and Where the Knowledge Lives

9.1.5 Rote Learning and Nearest Neighbor

9.1.6 Worked Example: Golf Play Prediction with Rote Learning

9.1.7 Worked Example: Golf Play Prediction with KNN

9.1.8 The Duck Analogy and the Neighborhood Picture

9.2 The K Parameter and Tiebreakers

9.2.1 What K Means

9.2.2 Worked Example: K = 1

9.2.3 Worked Example: K = 3

9.2.4 Worked Example: K = 2 and Distance-Weighted Voting

9.2.5 Choosing K: Too Small, Too Large, and Just Right

9.2.6 Worked Example: A Noisy Point with 1-NN vs 3-NN

9.2.7 Student Questions and Answers

9.3 Voronoi Cells and the Decision Boundary

9.3.1 What a Voronoi Cell Is

9.3.2 Building the Boundaries: Perpendicular Bisectors

9.3.3 Voronoi Tessellation and the Classification Boundary

9.3.4 Local Lines into a Global Boundary

9.3.5 Overfitting in 1-NN

9.4 Distance Metrics and Euclidean Distance

9.4.1 Three Distance Measures

9.4.2 Euclidean Distance Between Two Points

9.4.3 The Formula in D Dimensions

9.5 The Nearest-Neighbor Search Procedure and Complexity

9.5.1 How KNN Finds Its Neighbors

9.5.2 Complexity: O(D), O(ND), and Sorting

9.5.3 Why the Cost Grows with Dimensions

9.6 Limitations of KNN

9.6.1 Curse of Dimensionality

9.6.2 Counterintuitive Results

9.6.3 The Scaling Problem

9.6.4 Worked Example: S1, S2, S3

9.6.5 Fixing the Scale

9.6.6 Student Questions and Answers

9.7 KNN vs Decision Trees: Missing Data and Complex Boundaries

9.7.1 How Each Algorithm Thinks

9.7.2 Missing Data Handling

9.7.3 Complex Boundaries: Where KNN Shines

9.7.4 What to Study Next

9.8 Ensemble Methods: The Big Idea

9.8.1 Wisdom of the Crowd

9.8.2 Many Predictors Instead of One

9.8.3 The Two Key Design Questions

9.8.4 Why Ensemble Works

9.8.5 The Error Example: 0.35 to 0.06

9.9 Aggregating Predictions: Four Strategies

9.9.1 Committee: Majority Voting and Unweighted Average

9.9.2 Weighted Average

9.9.3 Predictors of Predictor

9.9.4 Mixture of Experts

Exam Guidance Summary

Key Industry Applications

DM Lecture 9 notes · K-Nearest Neighbor and Ensemble Methods

Sections Breakdown

Exam Revision Notes

Eager Learning vs Lazy Learning

The K Parameter and Tiebreakers

Voronoi Cells and the Decision Boundary

Distance Metrics and Euclidean Distance

The Nearest-Neighbor Search Procedure and Complexity

Limitations of KNN

KNN vs Decision Trees: Missing Data and Complex Boundaries

Ensemble Methods: The Big Idea

Aggregating Predictions: Four Strategies

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat