Machine Learning

Instance-Based Learning and K-Nearest Neighbors

📅 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

Data Preprocessing & Attribute Types — covered in Lecture 2 (Data Preprocessing for Machine Learning)
Information Theory & Splitting Criteria — covered in Lecture 8 (Decision Trees)
Overfitting & Model Evaluation — covered in Lecture 9 (Overfitting, Pruning, and MDL)

Instance-Based Learning and K-Nearest Neighbors

10.1 Model-Based Learning vs Instance-Based Learning

Hook. What if a learning algorithm refused to learn anything at all — until the exact moment you asked it a question? That is instance-based learning. It stores every example and only "thinks" when a prediction is needed. The opposite — learning a rule upfront and then discarding the data — is how most algorithms work. Why would anyone choose laziness over eagerness?

10.1.1 Definition and Explanation

Intuition + Analogy. Picture two students preparing for an exam.

Eager learner: Reads the textbook cover to cover, distills the rules into a cheat sheet, then throws the textbook away. On exam day, she answers every question from the cheat sheet alone. This is model-based learning.
Lazy learner: Keeps the textbook on his desk unopened. When a question arrives on the exam, he flips through the pages to find the most similar solved problem and adapts its answer. This is instance-based learning.

The lazy learner does zero work upfront but works hard for every single question. The eager learner invests upfront but answers quickly. The analogy breaks in one way: the lazy learner here still has a brain that generalizes; the KNN algorithm does not generalize at all — it purely matches.

In model-based learning, the algorithm takes training data, learns a generalized target function from it, and then uses that function to predict outcomes for new unseen records. Once the model is learned, the training data can be discarded. Linear regression and logistic regression are examples of model-based learning. This is also called eager learning — the model learns immediately when training data is provided.

In instance-based learning, the algorithm simply stores the training examples. It does not generalize. It does not create any model. Until a new record arrives that needs a prediction, the algorithm does nothing — generalization is postponed. This is also called lazy learning.

How instance-based learning works step by step:

Store all training examples in memory.
Wait. Do nothing until a new unseen record (query point) arrives.
Search. When a query point $x_{q}$ arrives, find the stored examples that are similar to $x_{q}$ .
Assign. Based on the similarity (or the class labels of the most similar records), assign a target value $y^$ to $x_{q}$ .

$Store (X, Y) \Rightarrow When x_{new} arrives, find similar stored x_{i} and use their y_{i}$

Every time a new instance is encountered, the algorithm calculates the relationship between that incoming record and all stored examples. Predictions are made based on similarity to the stored examples — no global model is ever built.

By contrast, model-based learning follows a different flow:

$Learn parameters θ from training data (X, Y) \Rightarrow y^= f_{θ} (x_{new})$

Once $θ$ is learned, the training data can be discarded. The function $f_{θ}$ is a compressed, generalized summary of the entire dataset.

10.1.2 Advantages and Disadvantages

Advantages of instance-based learning:

Handles complex patterns. There is no single generalized model for the entire dataset. For every query point, different training examples may be considered. If the data has intricate, non-uniform patterns, instance-based methods can still work well.
Flexible. The method adapts to new data dynamically. If you add 50 more training examples, nothing changes structurally — when the next query point comes, the algorithm simply calculates distances to all 150 examples instead of 100.
Local approximations. Decisions are made based on the local neighborhood of the query point, not a global model that may not fit every region equally well. The method constructs a different approximation to the target function for each distinct query instance.

Disadvantages of instance-based learning:

High memory usage. All (or most) training data must be retained in memory.
Slow prediction speed. All calculations happen at prediction time. For KNN, the algorithm must compute the similarity between the query point and every training example, sort the distances, and then identify the nearest neighbors — all when a prediction is requested. This is the cost of laziness.

Scope: When does each approach break?

Model-based (eager) learning breaks when the true underlying function is too complex for a single global model — one equation cannot fit every region of the data well. Think of a dataset where the pattern in the top-left corner is completely different from the pattern in the bottom-right. A single linear regression line will fail somewhere.

Instance-based (lazy) learning breaks when:

The training set is enormous — storing and searching through millions of examples at query time becomes infeasible.
Many attributes are irrelevant noise — the distance metric gets swamped by meaningless dimensions (see Section 10.10, the curse of dimensionality).
Real-time predictions are required — computing distances to all training examples for every query is too slow.

Visual intuition. Imagine a 2D scatter plot where the x-axis is one feature and the y-axis is another. Each point is colored by its class (red or blue). Model-based learning draws a single decision boundary — a straight line, a curve, or a complex surface — that partitions the whole space in one shot. Instance-based learning draws no line at all. It waits for a query point (a new dot you place on the plot), then looks at the colored dots nearest to it and votes. The decision "boundary" is implicit — it emerges from whatever neighbors happen to be closest to each possible query location. For 1-Nearest-Neighbor, the decision surface is a Voronoi diagram: each training point owns a convex polygon of influence. The takeaway: model-based gives you a map; instance-based gives you a compass that only points when you ask.

Pitfalls.

"Lazy means simple." Lazy learning is simple in concept, but the distance calculations, sorting, and neighbor lookup at prediction time make it computationally heavy. Do not confuse algorithmic simplicity with computational efficiency.
"More data always helps." Adding training examples improves coverage but linearly increases prediction cost. At some point, you need indexing structures (kd-trees, ball trees) to stay practical.
"Eager is always faster at prediction." True for KNN vs linear regression, but some eager models (deep neural networks, large ensembles) can also be slow at inference. The eager/lazy distinction is about when the work happens, not the total work.
"One approach is universally better." Neither is universally superior. Instance-based methods shine when the target function is complex and local; model-based methods shine when a compact global description exists and predictions must be fast. The choice depends on the data and the deployment constraints.

Model-based learning builds a compressed global summary upfront; instance-based learning stores raw data and generalizes only when asked. The tradeoff is training cost vs prediction cost — and the ability to capture complex local patterns without forcing a single global fit. Next: what real-world problems naturally fit the lazy-learning mold?

Real-world & domain connection. The eager-vs-lazy tradeoff appears everywhere in computing. Database indexes are eager (built upfront, queries are fast); full table scans are lazy (no prep, slow per query). Web search engines are a hybrid: they eagerly index the web (Google's crawler builds a massive precomputed index), but ranking algorithms compute relevance scores lazily per query. In machine learning specifically, the lazy approach powers recommendation systems (Section 10.2). Netflix does not precompute a single "taste model" for all users; it finds similar users on the fly when you need a recommendation. The lazy paradigm is also the foundation of case-based reasoning in legal and medical expert systems, where past cases are stored and retrieved by similarity to guide decisions on new cases.

10.2 Applications of Instance-Based Learning

Hook. You open Amazon and see "Customers who bought this also bought…" You open Netflix and see "Because you watched…" Neither Amazon nor Netflix built a single model of your personality. Instead, they found people whose past behavior looks like yours — and copied their taste. This is instance-based thinking at planet scale.

Intuition + Analogy. Instance-based learning is the "ask your neighbors" strategy. When you move to a new neighborhood and want to know which plumber to call, you don't build a statistical model of plumber quality across the city. You knock on your nearest neighbors' doors and ask. The three applications below are just three different versions of "knocking on the nearest door" — the only difference is whose door and what you ask.

10.2.1 Recommendation Systems — Collaborative Filtering

Recommendation systems suggest items to users based on past behavior. Collaborative filtering is one major approach that works on instance-based learning principles.

User-user similarity: Given a user's past preferences, identify similar users — users whose preferences closely match the target user's preferences. Then recommend items liked by those similar users. This requires calculating a similarity score between every pair of users, which is an $n \times n$ computation on the user base.

Item-item similarity: Identify items that are similar to the ones the user has already interacted with or purchased. Recommend those similar items. This requires calculating similarity between items — often more stable than user-user similarity because item characteristics change less than user tastes.

Real-world: Amazon product recommendations, Netflix movie suggestions, Spotify music recommendations all use collaborative filtering techniques rooted in similarity calculations. Amazon's "item-item collaborative filtering" was famously described in a 2003 paper ("Amazon.com Recommendations: Item-to-Item Collaborative Filtering" by Linden, Smith, and York) and scaled to hundreds of millions of users.

10.2.2 Anomaly Detection

An anomaly (or outlier) is a data point that is far away from other data points in feature space — a point that is dissimilar from other objects.

Anomaly detection can be reframed as a proximity problem: identify the objects that are highly dissimilar from other objects in the training set. For each point, compute its distance to its $k$ -th nearest neighbor. Points whose $k$ -NN distance is unusually large (beyond some threshold) are flagged as anomalies.

This is inherently instance-based — you are not learning what "normal" looks like as a global model; you are measuring how isolated each individual point is from the rest.

Worked intuition: In credit card fraud detection, each transaction is a point in a feature space (amount, time of day, merchant category, location). A legitimate transaction sits comfortably in a dense cluster of similar past transactions. A fraudulent transaction — say, a \$2000 purchase at 3 AM from a foreign country — is far from all other points. Its distance to even the nearest legitimate transaction is large, so it gets flagged. No global model of "fraud" is needed — just proximity.

10.2.3 Context-Based Search / Document Retrieval

When a user submits a query, the system calculates the similarity between the query and existing documents. Documents with the highest similarity to the query are retrieved.

The query is treated as a short pseudo-document. Both the query and every stored document are converted into vectors in a shared term space (a document-term matrix). Cosine similarity (Section 10.9) measures the angle between the query vector and each document vector. Documents with the smallest angle (highest cosine similarity) are returned as results.

This is lazy in the purest sense: documents are stored as vectors, no global category model is learned, and every query triggers a fresh similarity scan.

Scope: When similarity-based retrieval breaks. If the query uses vocabulary that never appeared in any stored document (the "vocabulary gap" problem), cosine similarity returns zero for everything — the system has no neighbor to ask. This is why modern search engines augment exact keyword matching with semantic embeddings that capture meaning beyond surface words.

Visual intuition. Picture a 2D grid where every dot is a document, and every dot is colored by topic (sports = blue, politics = red, technology = green). A new query appears as a star. Recommendation: find the nearest blue dots to the star and suggest what they "liked." Anomaly detection: find any dot so isolated that even its closest neighbor is far away — that dot is suspicious. Document retrieval: find the dots whose direction from the origin most closely matches the star's direction. Three tasks, one engine: proximity.

Pitfalls.

Cold-start problem. A new user with no history has no neighbors — user-user collaborative filtering cannot help. A new item with no ratings has no similar items. These are the "new user" and "new item" cold-start problems. Solutions include using content-based features (item descriptions) or defaulting to global popularity until enough data accumulates.
Popularity bias. Collaborative filtering tends to recommend already-popular items, creating a rich-get-richer feedback loop. Less popular but potentially better-matched items get buried.
Anomaly threshold tuning. There is no universal threshold for "how far is too far." It depends on the dataset density and the cost of false positives vs false negatives. Cross-validation on labeled anomalies (when available) is essential.
Synonymy in search. Different words for the same concept ("car" vs "automobile") produce orthogonal vectors in a pure term-frequency representation. Latent Semantic Indexing (LSI) and modern embeddings address this.

Three major applications — recommendation, anomaly detection, and document retrieval — all reduce to computing and acting on pairwise proximities. The core engine is the same: store everything, then measure similarity. Next: how do we actually define and compute "similarity" and "dissimilarity"?

Real-world & domain connection. Collaborative filtering drove the Netflix Prize (2006–2009), a \$1M competition that advanced recommendation research globally. The winning solution was an ensemble, but instance-based nearest-neighbor methods were core components. In cybersecurity, distance-based anomaly detection is used in intrusion detection systems (IDS) that flag network traffic patterns far from normal baselines. In legal tech, case-based reasoning systems like CATO and HYPO retrieve precedent cases by measuring similarity between the fact patterns of a current case and historical rulings — an instance-based approach to legal argument. The common thread: when the "rules" are too complex or unknowable, let the data speak through its neighbors.

10.3 Data Similarity and Dissimilarity — Proximity Measures

Hook. Two photos of the same face, taken seconds apart. Two bank transactions, one legitimate and one fraudulent. Two documents, one about football and one about soccer. In every case, a machine must answer: how alike are these two things? Everything in instance-based learning. KNN, recommendations, anomaly detection — rests on getting this one number right.

10.3.1 Core Definitions

Intuition + Analogy. Think of proximity as a universal remote with a "distance" dial. Turn the dial to 0: the two objects sit on top of each other — identical. Turn it up: they drift apart. The dial itself is proximity. Whether you read the number as "how close" (similarity, where bigger = closer) or "how far" (dissimilarity, where smaller = closer) is just a labeling choice. Most formulas in machine learning compute dissimilarity (distance) and then derive similarity from it — just like you naturally measure how far apart two cities are, not how close they are.

The analogy breaks for non-numeric attributes. You can't put "red" and "blue" on a number line. Sections 10.4–10.8 are all about building that dial for every kind of data.

Similarity: A numerical measure of how alike two data objects are. Higher value means more alike. Often falls in the range $[0, 1]$ , where $1$ means identical and $0$ means completely different.

Dissimilarity (also called distance): A numerical measure of how different two data objects are. Lower value means more alike. Minimum dissimilarity is often $0$ (meaning the objects are identical). Upper limit can vary — values of $1$ or above indicate high dissimilarity.

Proximity: The umbrella term that covers both. "What is the proximity between these two objects?" means "How similar or dissimilar are they?"

Relationship (when both are normalized to $[0, 1]$ ):

$Similarity = 1 - Dissimilarity$

In practice, dissimilarity is more commonly computed; similarity is then derived from it. This is partly because many natural distance formulas (Euclidean, Manhattan) are inherently dissimilarity measures — they start at 0 and grow without bound.

Scope: What makes a valid dissimilarity measure? A proper distance metric $d (i, j)$ must satisfy four axioms for any objects $i, j, k$ :

Non-negativity: $d (i, j) \geq 0$ — distances can't be negative.
Identity of indiscernibles: $d (i, j) = 0$ if and only if $i = j$ — the only thing at zero distance from an object is itself.
Symmetry: $d (i, j) = d (j, i)$ — the distance from A to B equals the distance from B to A.
Triangle inequality: $d (i, j) \leq d (i, k) + d (k, j)$ — going directly is never longer than going through a third point.

Not every proximity measure used in practice satisfies all four (cosine similarity is not a proper metric because it fails the triangle inequality), but Euclidean and Manhattan distances do. When a measure fails an axiom, be aware of what you're giving up.

10.3.2 Data Matrix vs Dissimilarity Matrix

Data matrix: An $n \times p$ structure — $n$ data points (rows) with $p$ attributes (columns). This is an object-by-attribute structure — also called two-mode because both objects and attributes appear. Each cell $x_{ij}$ is the value of attribute $j$ for object $i$ .

$X = x_{11} x_{21} ⋮ x_{n 1} x_{12} x_{22} ⋮ x_{n 2} \dots \dots ⋱ \dots x_{1 p} x_{2 p} ⋮ x_{n p}$

Dissimilarity matrix: An $n \times n$ structure — registers only the pairwise distance between objects. This is an object-by-object structure — single-mode (only objects appear). It is triangular because $d (i, j) = d (j, i)$ :

$D = 0 d_{12} 0 d_{13} d_{23} 0 \dots \dots \dots ⋱ d_{1 n} d_{2 n} d_{3 n} ⋮ 0$

The diagonal is always $0$ because the distance of an object to itself is zero. Only the lower triangle (or upper triangle) needs to be stored — giving $\frac{n ( n - 1 )}{2}$ distinct values for $n$ objects. For 1000 objects, that is 499,500 pairwise distances. For 1 million objects, it is roughly 500 billion — the matrix becomes infeasible to store densely.

Worked example — from data matrix to dissimilarity matrix.

Given three points in 2D: $A = (0, 0)$ , $B = (3, 0)$ , $C = (0, 4)$ .

Data matrix ( $3 \times 2$ ): $X = 030004$

Compute Euclidean distances:

$d (A, B) = (3 - 0)^{2} + (0 - 0)^{2} = 9 = 3$
$d (A, C) = (0 - 0)^{2} + (4 - 0)^{2} = 16 = 4$
$d (B, C) = (0 - 3)^{2} + (4 - 0)^{2} = 9 + 16 = 25 = 5$

Dissimilarity matrix ( $3 \times 3$ ): $D = 034305450$

Sense-check: $d (B, C) = 5$ — this is the hypotenuse of the 3-4-5 right triangle formed by A, B, C. ✓

Visual intuition. Picture the data matrix as a spreadsheet: rows are customers, columns are "age," "income," "purchases." The dissimilarity matrix is a heatmap where cell $(i, j)$ is colored by how different customer $i$ is from customer $j$ . The diagonal is dark blue (distance 0). Two nearly identical customers produce a light-colored cell. Two completely different customers produce a bright red cell. The matrix is symmetric across the diagonal. When you run KNN, you are effectively reading one row of this heatmap — the distances from your query point to everyone else.

Pitfalls.

Confusing the two matrices. The data matrix is $n \times p$ (objects $\times$ attributes). The dissimilarity matrix is $n \times n$ (objects $\times$ objects). Mixing them up — trying to compute distances on the dissimilarity matrix as if it were data — is a common beginner error.
Forgetting symmetry. Always compute only $\frac{n ( n - 1 )}{2}$ distances, not $n^{2}$ . For large $n$ , the difference is a factor of 2 in both time and storage.
Ignoring attribute types. The data matrix looks clean and numeric, but if column 3 is actually a nominal category encoded as numbers (e.g., ZIP codes), applying Euclidean distance to it produces nonsense. Always check the attribute type before choosing a proximity measure.
Normalization matters. If one attribute ranges from 0–1 and another from 0–100,000, the large-range attribute dominates every distance calculation. Always normalize or standardize numeric attributes before computing the dissimilarity matrix.

Proximity is the universal language of instance-based learning. Every method in this lecture ultimately reduces to "compute a number that says how similar two things are." The data matrix holds the raw facts; the dissimilarity matrix distills those facts into pairwise relationships. Next: how do we compute that number for nominal (categorical) data, where there is no number line?

Real-world & domain connection. The distinction between data matrices and dissimilarity matrices is fundamental to all of data mining, not just instance-based learning. Clustering algorithms like k-means operate on the data matrix directly; hierarchical clustering operates on the dissimilarity matrix. In bioinformatics, phylogenetic trees are built from DNA sequence dissimilarity matrices. In marketing, customer segmentation often starts by computing a dissimilarity matrix on purchasing behavior, then clustering. The concept of "distance" between data points is so central that entire subfields — metric learning, manifold learning — are dedicated to learning the right distance function for a given task.

10.4 Proximity Measures for Nominal (Categorical) Attributes

Hook. Colors. ZIP codes. Marital status. Country names. None of these live on a number line — you cannot subtract "blue" from "red" or average two ZIP codes. Yet KNN must still decide which objects are similar. How do you measure distance when there is no ruler?

Intuition + Analogy. Nominal attributes are like name tags at a conference. Two people either have the same name tag ("Speaker") or different name tags ("Speaker" vs "Attendee"). There is no "halfway between Speaker and Attendee." The distance is binary per attribute: match = 0, mismatch = 1. The overall distance is simply the fraction of name tags that don't match. If you have 5 name tags and 3 match, you are 40% different — that's it.

10.4.1 Formula and Worked Examples

For a dataset containing only nominal attributes, the dissimilarity between two objects $i$ and $j$ is the fraction of attributes on which they disagree:

$d (i, j) = \frac{p - m}{p}$

where:

$p$ = total number of nominal attributes
$m$ = number of attributes where the two objects have matching values
$p - m$ = number of attributes where they differ

The result is always in $[0, 1]$ :

$d = 0$ : identical on every attribute (all match)
$d = 1$ : different on every attribute (no match)
Intermediate values: proportion of mismatches

Example 1 — Single attribute (color):

| Object | Color |

1	R
2	B
3	G
4	R

$d (1, 2)$ : $p = 1$ , colors R vs B do not match → $m = 0$ , so $d = \frac{1 - 0}{1} = 1.0$ → maximally dissimilar
$d (1, 4)$ : $p = 1$ , both are R → $m = 1$ , so $d = \frac{1 - 1}{1} = 0$ → identical

Sense-check: with only one attribute, any two objects are either identical (0) or completely different (1). There is no middle ground. ✓

Example 2 — Two attributes (color and position):

| Object | Color | Position |

1	R	L
2	B	R
3	G	C
4	R	L
5	B	C
6	G	R

$d (1, 3)$ : $p = 2$ , color R vs G (mismatch), position L vs C (mismatch) → $m = 0$ , $d = \frac{2 - 0}{2} = 1.0$
$d (3, 6)$ : $p = 2$ , color G vs G (match ✓), position C vs R (mismatch) → $m = 1$ , $d = \frac{2 - 1}{2} = 0.5$
$d (1, 4)$ : $p = 2$ , color R vs R (match ✓), position L vs L (match ✓) → $m = 2$ , $d = \frac{2 - 2}{2} = 0$

The most similar pair is (1, 4) with $d = 0$ . The most dissimilar pairs — (1,2), (1,3), (1,5), (2,3), (2,4), (2,6), (3,5), (4,5), (4,6), (5,6) — all have at least one mismatch; several reach $d = 1$ .

The full dissimilarity matrix:

$D = 011011 1011 0.5 1 11011 0.5 011011 1 0.5 1101 11 0.5 110$

Sense-check: objects 1 and 4 are identical on both attributes → $d = 0$ . Objects with one match → $d = 0.5$ . Objects with no matches → $d = 1$ . ✓

Scope & Assumptions. This formula assumes all nominal attributes are equally important and that every mismatch counts the same. It also assumes there is no meaningful ordering among the values. "R vs B" is the same kind of difference as "R vs G." If some nominal values are semantically closer than others (e.g., "cat" is more similar to "dog" than to "airplane"), this formula cannot capture that — you would need external domain knowledge to define a custom distance.

Visual intuition. Imagine two rows in a spreadsheet with 5 nominal columns. Slide a window over both rows simultaneously. Count how many columns show different values. Divide by 5. That fraction is the dissimilarity. For 2 columns: picture a 2×2 grid where one axis is color (R, B, G) and the other is position (L, C, R). Each object is a cell. Two objects in the same cell have $d = 0$ . Two objects sharing one coordinate but not the other have $d = 0.5$ . Two objects in completely different rows and columns have $d = 1$ .

Pitfalls.

Missing values. If an attribute value is missing for one or both objects, the formula breaks. The standard fix is to exclude that attribute from both $p$ and $m$ for that pair — effectively computing distance only on attributes where both objects have values. This is exactly what the Gower distance (Section 10.8) formalizes.
Encoding nominal values as integers. If you encode "R=1, B=2, G=3" and then apply Euclidean distance, you'll get $d (R, G) = ∣1 - 3∣ = 2$ and $d (R, B) = ∣1 - 2∣ = 1$ , implying Green is "twice as far" from Red as Blue is — complete nonsense for nominal data.
All-or-nothing with few attributes. With only 1 or 2 nominal attributes, the distance can only take a few discrete values (0, 0.5, 1). This coarse granularity can cause many ties in KNN — many objects are "equally close" to a query point. Tie-breaking rules become important.

For nominal attributes, dissimilarity is simply the fraction of attributes that don't match: $d = (p - m) / p$ . Simple, interpretable, and bounded in $[0, 1]$ . Next: what if the attributes have a meaningful order — small < medium < large — but we still cannot quantify the gaps?

Real-world & domain connection. Nominal distance is the backbone of market basket analysis. When a retailer compares two shopping baskets, each basket is a binary vector over thousands of products (purchased = 1, not purchased = 0). The nominal distance — counting how many products one customer bought that the other didn't — tells the retailer which customers are "similar shoppers." This drives targeted coupon campaigns: "Customers similar to you also bought…" The same principle applies in genetics when comparing DNA sequences by counting position-by-position mismatches (Hamming distance), and in record linkage (deduplication) where nominal fields like name, city, and phone number are compared to decide if two database records refer to the same person.

10.5 Proximity Measures for Ordinal Attributes

Hook. "Small," "medium," "large." "Poor," "fair," "good," "excellent." You know the order — large is bigger than small, excellent is better than poor. But how much bigger? Is the jump from small to medium the same as from medium to large? Is "good" halfway between "fair" and "excellent"? Ordinal data gives you order without scale. To feed it into KNN, you must first give it numbers.

Intuition + Analogy. Ordinal attributes are like a race where you know who came 1st, 2nd, and 3rd, but you don't know the finish times. The gap between 1st and 2nd might be a photo finish (0.01 seconds) while 2nd to 3rd might be a minute — but all you have are the ranks. The three-step process below converts ranks into numbers on a $[0, 1]$ scale by assuming the gaps are equal (the best we can do without more information), then lets any numeric distance formula take over.

Brewing coffee strength: "mild," "medium," "strong." Assign ranks 1, 2, 3. Normalize to 0, 0.5, 1. Now you can say a mild and a strong coffee are distance 1 apart — the maximum on this scale. The analogy breaks when the true gaps are known (e.g., actual caffeine mg) — then you'd use the numeric formula directly.

10.5.1 Three-Step Process

Ordinal attributes have an inherent order (e.g., small < medium < large) but the differences between consecutive values cannot be quantified directly. The process to compute dissimilarity follows three steps:

Step 1. Assign ranks. Assign integer ranks to each state while preserving the order. Use consecutive integers starting from 1. For example, for test scores: fair = 1, good = 2, excellent = 3. Let $M_{f}$ be the total number of distinct states for attribute $f$ . Reverse order (excellent = 1, fair = 3) is also valid as long as it is consistent across all objects.

Step 2 — Normalize the ranks. Use min-max normalization to bring every rank into the $[0, 1]$ interval:

$normalized rank_{i f} = \frac{r _{i f} - 1}{M _{f} - 1}$

where $r_{i f}$ is the integer rank of object $i$ on attribute $f$ , and $M_{f}$ is the number of distinct states. This maps the lowest rank to 0 and the highest to 1, with equal spacing between consecutive ranks.

Step 3 — Treat as numeric. Apply any numeric distance measure (Euclidean, Manhattan, etc.) to the normalized ranks. The normalized ranks are now ordinary numbers in $[0, 1]$ — use whichever metric suits the data.

Worked example — Single ordinal attribute (test score):

States: fair, good, excellent. $M_{f} = 3$ .

Ranks: fair = 1, good = 2, excellent = 3.

Normalize:

fair: $\frac{1 - 1}{3 - 1} = \frac{0}{2} = 0$
good: $\frac{2 - 1}{3 - 1} = \frac{1}{2} = 0.5$
excellent: $\frac{3 - 1}{3 - 1} = \frac{2}{2} = 1$

Distance between "excellent" (1) and "fair" (0) using Manhattan: $∣1 - 0∣ = 1$ .

Sense-check: the maximum possible distance on one ordinal attribute is 1 (between the extremes). ✓

Worked example — Two ordinal attributes (size and quality):

| Object | Size | Quality |

A	small	good
B	large	excellent
C	large	fair
D	medium	poor

Size: 3 states (small, medium, large). $M_{size} = 3$ .

Ranks: small = 1, medium = 2, large = 3
Normalized: small = $\frac{1 - 1}{3 - 1} = 0$ , medium = $\frac{2 - 1}{3 - 1} = 0.5$ , large = $\frac{3 - 1}{3 - 1} = 1$

Quality: 4 states (poor, fair, good, excellent). $M_{quality} = 4$ .

Ranks: poor = 1, fair = 2, good = 3, excellent = 4
Normalized: poor = $\frac{1 - 1}{4 - 1} = 0$ , fair = $\frac{2 - 1}{4 - 1} = 0.33$ , good = $\frac{3 - 1}{4 - 1} = 0.67$ , excellent = $\frac{4 - 1}{4 - 1} = 1$

Now compute Euclidean distances:

$d (A, B) d (C, A) d (C, B) d (D, C) d (D, A) d (D, B) = (0 - 1)^{2} + (0.67 - 1)^{2} = 1 + 0.1089 = 1.1089 \approx 1.053 = (1 - 0)^{2} + (0 - 0.67)^{2} = 1 + 0.4489 = 1.4489 \approx 1.204 = (1 - 1)^{2} + (0 - 1)^{2} = 0 + 1 = 1.000 = (0.5 - 1)^{2} + (0 - 0.33)^{2} = 0.25 + 0.1089 = 0.3589 \approx 0.599 = (0.5 - 0)^{2} + (0 - 0.67)^{2} = 0.25 + 0.4489 = 0.6989 \approx 0.836 = (0.5 - 1)^{2} + (0 - 1)^{2} = 0.25 + 1 = 1.25 \approx 1.118$

Most similar pair: D and C with $d \approx 0.599$ — medium size & poor quality vs large size & fair quality. Most dissimilar pair: C and A with $d \approx 1.204$ — large size & fair quality vs small size & good quality.

> Dissimilarity can exceed $1$ . Any value of $1$ or above indicates high dissimilarity. With Euclidean distance on normalized ranks, the maximum possible distance between two objects with 2 ordinal attributes is $1^{2} + 1^{2} = 2 \approx 1.414$ .

Scope & Assumptions. This process assumes equal spacing between consecutive ranks — that the gap from "poor" to "fair" is the same as from "fair" to "good." If you have domain knowledge that the gaps are unequal (e.g., the jump from "good" to "excellent" is much harder than from "fair" to "good"), you could assign custom numeric scores instead of uniform ranks. The normalization step also assumes the lowest and highest ranks are meaningful endpoints — if a new object arrives with a value beyond the original range, you'd need to re-normalize.

Visual intuition. Picture a number line from 0 to 1. Each ordinal state is a tick mark equally spaced along it. "Poor" sits at 0, "fair" at 0.33, "good" at 0.67, "excellent" at 1. Two objects are points on parallel number lines (one line per attribute). The Euclidean distance between them is the straight-line distance in this normalized space — pull out a ruler and measure. The spacing is artificial (equal), but it's the best you can do without knowing the true gaps.

Pitfalls.

Reverse the order by accident. If you assign fair=1, good=2, excellent=3 for one object but excellent=1, good=2, fair=3 for another, the distance is corrupted. Pick one direction and apply it consistently to all objects.
Forgetting to normalize. Computing Euclidean distance directly on raw ranks (1, 2, 3) makes the distance depend on the number of states — an attribute with 10 ordinal levels would dominate one with 3 levels even if both are equally important. Always normalize to $[0, 1]$ first.
Using the wrong numeric metric. After normalization, Euclidean and Manhattan distances may give different neighbor orderings. Manhattan on normalized ranks is often more interpretable (differences are per-attribute, additive). Euclidean squares the differences, which penalizes large single-attribute disagreements more heavily.
Assuming the spacing is correct. The equal-spacing assumption is a convenience, not a fact. If the ordinal scale is heavily skewed (e.g., 90% of values are "good," 9% are "excellent," 1% are "poor"), the normalized ranks may not reflect the true distribution. Quantile-based normalization can help.

Ordinal distance is a three-step pipeline: rank → normalize to $[0, 1]$ → apply a numeric distance formula. The key insight: you convert "order without scale" into numbers by assuming equal spacing, then let standard distance formulas take over. Next: what about binary attributes, where there are only two states — but the symmetry (or asymmetry) of those states matters?

Real-world & domain connection. Ordinal distance is ubiquitous in survey analysis and psychometrics. Likert scales ("strongly disagree" to "strongly agree" on a 5-point or 7-point scale) are ordinal — researchers routinely treat them as numeric after assigning 1–5 or 1–7 ranks. In medicine, pain scales (0–10) and cancer staging (Stage I–IV) are ordinal. In education, letter grades (A, B, C, D, F) are ordinal. GPA calculations convert them to numbers using exactly this three-step logic. In customer analytics, star ratings (1–5 stars) on Amazon or Yelp are ordinal — a 5-star item is better than a 4-star item, but the "distance" between 4 and 5 stars may not equal the distance between 1 and 2 stars in terms of customer satisfaction.

10.6 Proximity Measures for Binary Attributes

Hook. Two shoppers. One bought milk and bread. The other bought milk and eggs. Are they similar? It depends — does the fact that neither bought diapers matter? For some problems, a shared absence means nothing. For others, it is as informative as a shared presence. Binary proximity has a split personality, and choosing the wrong one can break your model.

Intuition + Analogy. Binary attributes are yes/no checkboxes. When comparing two checklists, you count four things: boxes both checked ( $q$ ), boxes only the first person checked ( $r$ ), boxes only the second checked ( $s$ ), and boxes neither checked ( $t$ ). The question is: do you count the "both unchecked" boxes?

If the checkboxes are "has a driver's license" — both having one ( $q$ ) and both not having one ( $t$ ) are equally informative. That's symmetric. If the checkboxes are "has a rare disease" — both having it is huge, but both not having it is the default for 99.9% of people and tells you nothing. That's asymmetric — you ignore $t$ . The Jaccard coefficient is the asymmetric version's similarity score, and it is the backbone of recommendation systems and text mining.

10.6.1 The Contingency Table

For binary attributes (values are $0$ or $1$ ), a $2 \times 2$ contingency table is constructed for each pair of objects $i$ and $j$ :

Object $i$ = 1	$q$	$r$	$q + r$
Object $i$ = 0	$s$	$t$	$s + t$
Column sum	$q + s$	$r + t$	$p$

where $p = q + r + s + t$ is the total number of binary attributes.

$q$ = number of attributes where both have $1$ (positive match)
$r$ = number where $i$ has $1$ and $j$ has $0$
$s$ = number where $i$ has $0$ and $j$ has $1$
$t$ = number where both have $0$ (negative match)

10.6.2 Symmetric Binary Attributes

A symmetric binary attribute is one where both states (0 and 1) are equally important and equally informative. There is no preference for encoding one outcome as 1 versus 0 — you could flip all 0s and 1s and the meaning would not change.

Examples: gender (male/female), marital status (married/unmarried), employment type (full-time/part-time), citizenship status, flipping a coin (heads/tails).

Symmetric binary dissimilarity (also called simple matching coefficient distance):

$d (i, j) = \frac{r + s}{q + r + s + t} = \frac{r + s}{p}$

The numerator counts total mismatches — cases where one object has $1$ and the other has $0$ , regardless of direction. The denominator counts all $p$ attributes. Both positive matches ( $q$ ) and negative matches ( $t$ ) are treated as agreements and do not contribute to the distance.

Worked example — Symmetric binary:

Data with 6 attributes, all symmetric binary:

Ahmed	1	1	0	1	0	1
Surekha	0	1	0	0	1	1

For Ahmed ( $i$ ) and Surekha ( $j$ ), count attribute by attribute:

Gender	1	0	$r$
Food	1	1	$q$
Caste	0	0	$t$
Education	1	0	$r$
Hobby	0	1	$s$
Job	1	1	$q$

Sums: $q = 2$ , $r = 2$ , $s = 1$ , $t = 1$ . Check: $2 + 2 + 1 + 1 = 6 = p$ . ✓

$d (Ahmed, Surekha) = \frac{2 + 1}{2 + 2 + 1 + 1} = \frac{3}{6} = 0.5$

Interpretation: Ahmed and Surekha disagree on 3 out of 6 attributes. They are exactly halfway between identical and completely different.

10.6.3 Asymmetric Binary Attributes and the Jaccard Coefficient

An asymmetric binary attribute is one where the presence of the attribute (value = 1) is considered much more important than its absence (value = 0). The usual convention is to encode the rarer, more meaningful outcome as 1.

Examples: result of a medical test (positive = 1, negative = 0), item purchased (purchased = 1, not purchased = 0), fraud detected (fraud = 1, not fraud = 0), word appears in document (present = 1, absent = 0).

Asymmetric binary dissimilarity:

$d (i, j) = \frac{r + s}{q + r + s}$

Notice that $t$ (both 0 — the negative matches) is excluded from the denominator entirely. Why? Because when most attributes are 0 for most objects (sparse data), including $t$ would make everything look similar — the massive number of shared zeros would drown out the few meaningful positive matches.

Jaccard coefficient (Jaccard similarity) is the corresponding similarity measure:

$Jaccard similarity = 1 - d (i, j) = \frac{q}{q + r + s}$

The Jaccard coefficient ranges from 0 (no shared positive attributes) to 1 (all positive attributes match, no disagreements on positives).

Worked example — Medical tests (mixed symmetric and asymmetric):

Jack	M	1	1	0
Mary	F	1	1	1
Jim	M	1	0	0

Gender is symmetric binary (M and F are equally informative).
Fever, Cough, Test1–Test4 are asymmetric binary — presence (1) is the important, rarer outcome.

Jack vs Mary (asymmetric attributes only — 6 attributes):

Tally each of the 6 asymmetric attributes:

Fever	1	1	$q$
Cough	0	0	$t$
Test1	1	1	$q$
Test2	0	0	$t$
Test3	0	1	$s$
Test4	0	0	$t$

$q = 2$ (Fever, Test1), $r = 0$ , $s = 1$ (Test3), $t = 3$ (Cough, Test2, Test4).

$d (Jack, Mary) = \frac{0 + 1}{2 + 0 + 1} = \frac{1}{3} \approx 0.333$

$Jaccard similarity = \frac{2}{2 + 0 + 1} = \frac{2}{3} \approx 0.667$

Jack vs Jim:

Fever	1	1	$q$
Cough	0	0	$t$
Test1	1	0	$r$
Test2	0	0	$t$
Test3	0	0	$t$
Test4	0	0	$t$

$q = 1$ , $r = 1$ , $s = 0$ , $t = 4$ .

$d (Jack, Jim) = \frac{1 + 0}{1 + 1 + 0} = \frac{1}{2} = 0.5$

Mary vs Jim:

Fever	1	1	$q$
Cough	0	0	$t$
Test1	1	0	$r$
Test2	0	0	$t$
Test3	1	0	$r$
Test4	0	0	$t$

$q = 1$ , $r = 2$ , $s = 0$ , $t = 3$ .

$d (Mary, Jim) = \frac{2 + 0}{1 + 2 + 0} = \frac{2}{3} \approx 0.667$

Result: Jack and Mary are the most similar pair ( $d \approx 0.333$ ). Mary and Jim are the most dissimilar pair ( $d \approx 0.667$ ). Sense-check: Jack and Mary share both Fever and Test1 positive; Mary and Jim share only Fever — the Jaccard comparisons reflect this. ✓

Scope: Symmetric vs Asymmetric. How to choose. Ask one question: "If both objects lack this attribute, does that tell me they are similar?" If yes → symmetric. If no → asymmetric. In market basket data, two customers who both didn't buy diapers tells you nothing — almost nobody buys diapers on any given trip. That's asymmetric. In gender, two people both being male tells you something meaningful — that's symmetric. Choosing wrong inflates or deflates similarity systematically.

Visual intuition. Picture two rows of 10 checkboxes each. For symmetric binary: a match is a match, whether checked or unchecked. Color every mismatch red. Count red boxes; divide by 10. That's the distance. For asymmetric binary: only pay attention when at least one box is checked. If both are unchecked, it's as if that attribute doesn't exist for this pair. The Jaccard coefficient is: "of the attributes where at least one is checked, what fraction are both checked?"

Pitfalls.

Treating asymmetric as symmetric. In a dataset with 10,000 products and the average basket contains 5 items, using symmetric distance makes every pair of customers look ~99.95% similar (because they share ~9,990 "not purchased" zeros). The distance becomes meaningless.
Encoding confusion. For asymmetric attributes, always encode the rarer/meaningful outcome as 1. If you encode "cancer negative = 1, cancer positive = 0," the Jaccard coefficient will measure similarity on negative tests — missing the whole point.
Mixing symmetric and asymmetric in one distance. Some attributes may be symmetric, others asymmetric. Compute them separately using their respective formulas, then combine using Gower distance (Section 10.8). Don't apply one formula blindly to all.
Sparse data sensitivity. When $q + r + s$ is very small (few positive attributes at all), the Jaccard coefficient becomes unstable — a single additional positive match can swing it dramatically. This is the sparse-data cousin of the curse of dimensionality.

Binary proximity splits into two formulas: symmetric counts all matches (including both-0); asymmetric ignores both-0 and uses only attributes where at least one object has a 1. The Jaccard coefficient = $q / (q + r + s)$ is the go-to similarity for sparse binary data. Next: numeric attributes — finally, data that lives on a real number line where we can use familiar geometric distances.

Real-world & domain connection. The Jaccard coefficient powers the "Customers who bought this also bought…" feature on Amazon. Each product is a binary vector over all customers (1 = purchased, 0 = didn't). Two products with high Jaccard similarity are frequently co-purchased. In plagiarism detection, documents are represented as binary vectors over a vocabulary of n-grams; Jaccard similarity flags suspicious overlap. In ecology, the Jaccard index measures biodiversity similarity between two habitats — which species do they share? In social network analysis, Jaccard similarity on neighbor sets predicts which unconnected nodes are likely to form a link (link prediction). The formula is over a century old (Paul Jaccard, 1901) and still ubiquitous.

10.7 Proximity Measures for Numeric Attributes

Hook. You are standing at (1, 2) and need to reach (3, 5). A crow flies 3.6 units. A taxi drives 5 units. A chess king moves 3 squares. Same start, same destination — three different "distances." Which one should KNN use? The answer changes which neighbors are nearest.

Intuition + Analogy. All numeric distances answer "how far?", but they disagree on what "far" means. Think of three travelers:

Euclidean traveler: A drone. Flies straight, ignores obstacles. Distance = direct line.
Manhattan traveler: A taxi in a grid city. Can only move north-south or east-west, never diagonal. Distance = sum of horizontal + vertical blocks.
Supremum traveler: A chess king. Can move any direction, and the distance is the longest single move needed (max coordinate difference).

Each traveler lives in a different geometry. KNN's choice of distance metric picks which traveler's map to use. The analogy breaks when dimensions go high — in 100-D space, all three travelers start reporting similar distances (the curse of dimensionality).

10.7.1 Euclidean Distance

Euclidean distance is the straight-line, "as the crow flies" distance. It is the ordinary distance you measure with a ruler. For two points in $n$ -dimensional space:

$d (i, j) = k = 1 \sum n (x_{ik} - x_{j k})^{2}$

Each dimension's difference is squared (making large differences count disproportionately), summed, and then square-rooted to return to original units.

Euclidean distance is the $L_{2}$ norm of the difference vector: $d (i, j) = ∥ x_{i} - x_{j} ∥_{2}$ .

Worked example: $X_{1} = (1, 2)$ and $X_{2} = (3, 5)$ .

$d (X_{1}, X_{2}) = (3 - 1)^{2} + (5 - 2)^{2} = 2^{2} + 3^{2} = 4 + 9 = 13 \approx 3.606$

Sense-check: a right triangle with legs 2 and 3 has hypotenuse $13 \approx 3.606$ . ✓

Euclidean distance works well for low-dimensional data. It is the default in most ML libraries and the most intuitive geometrically. However, the squaring operation makes it sensitive to outliers — a single large difference in one dimension gets amplified by the square.

10.7.2 Manhattan Distance

Manhattan distance (also called city block distance, taxicab geometry, or $L_{1}$ norm) measures distance as the sum of absolute differences along each axis — like driving through a city grid where you can only go north-south or east-west.

$d (i, j) = k = 1 \sum n ∣ x_{ik} - x_{j k} ∣$

No squaring, no square root. Each dimension contributes its absolute difference linearly.

Worked example: Same points $X_{1} = (1, 2)$ and $X_{2} = (3, 5)$ .

$d (X_{1}, X_{2}) = ∣3 - 1∣ + ∣5 - 2∣ = 2 + 3 = 5$

Note: Manhattan (5) > Euclidean (3.606) for the same points. This is always true. Euclidean is the shortest path; Manhattan adds detours. For points on a diagonal (e.g., (0,0) to (3,3)), Euclidean = $18 \approx 4.24$ , Manhattan = 6. The ratio Manhattan/Euclidean grows with dimensionality.

Manhattan distance is preferred for:

High-dimensional data — the $L_{1}$ norm is less affected by the curse of dimensionality than $L_{2}$ .
Discrete/binary attributes — absolute differences of 0 or 1 are natural and interpretable.
Robustness to outliers — no squaring means a single large deviation does not dominate.

Real-world: GPS navigation systems (Google Maps, etc.) effectively use Manhattan-like distance because they follow road grids. In chess, a rook moves in Manhattan distance.

10.7.3 Minkowski Distance

Minkowski distance is a parameterized family that generalizes both Euclidean and Manhattan:

$d (i, j) = (k = 1 \sum n ∣ x_{ik} - x_{j k} ∣^{h})^{1/ h}$

The parameter $h$ controls the behavior:

$h = 1$ : Manhattan distance ( $L_{1}$ )
$h = 2$ : Euclidean distance ( $L_{2}$ )
$h \to \infty$ : Supremum distance ( $L_{\infty}$ )

Think of Minkowski not as a separate distance but as a dial: turn $h$ to 1 for Manhattan, 2 for Euclidean, or anywhere in between for a compromise. In practice, $h = 1$ and $h = 2$ cover the vast majority of use cases.

Which distance to use?

Situation	Recommended metric
Low-dimensional, continuous data	Euclidean ( $h = 2$ )
High-dimensional data	Manhattan ( $h = 1$ )
Many discrete/binary attributes	Manhattan ( $h = 1$ )
Outliers present	Manhattan ( $h = 1$ ) — more robust
Want smooth, differentiable distance	Euclidean ( $h = 2$ )

As dimensionality increases, all Minkowski distances converge to similar values — this is the curse of dimensionality (Section 10.10). Cross-validation can determine the best $h$ for a specific dataset.

10.7.4 Supremum Distance

Supremum distance (also called Chebyshev distance or $L_{\infty}$ norm) takes the maximum absolute difference across all dimensions:

$d (i, j) = k max ∣ x_{ik} - x_{j k} ∣$

Only the single dimension with the largest difference matters. All other dimensions are ignored.

Worked example: $X_{1} = (1, 2)$ and $X_{2} = (3, 5)$ .

Horizontal difference: $∣3 - 1∣ = 2$
Vertical difference: $∣5 - 2∣ = 3$
Supremum distance: $max (2, 3) = 3$

Interpretation: "In the worst dimension, these points are 3 units apart." In chess, the king moves in Chebyshev distance — one square in any direction (including diagonal) counts as one move. The number of moves a king needs to reach a target square is exactly the Chebyshev distance.

Comparison of all four on the same points $X_{1} = (1, 2)$ , $X_{2} = (3, 5)$ :

Metric	Formula	Result
Manhattan ( $L_{1}$ )	$\sum ∣Δ∣$	5
Euclidean ( $L_{2}$ )	$\sum Δ^{2}$	3.606
Supremum ( $L_{\infty}$ )	$max ∣Δ∣$	3
Minkowski ( $h$ )	$(\sum ∣Δ ∣^{h})^{1/ h}$	varies with $h$

Manhattan ≥ Euclidean ≥ Supremum (always, for the same points). As $h$ increases, the Minkowski distance decreases and approaches the Supremum from above.

Scope & Assumptions. All four distances assume:

All dimensions are on the same scale. If feature A ranges 0–1 and feature B ranges 0–1000, feature B dominates every distance. Always normalize (min-max or z-score) before computing distances.
All dimensions are equally important. If you know some features matter more, use weighted versions (multiply each term by a weight $w_{k}$ ).
The space is Euclidean. These distances measure straight-line proximity in a flat coordinate space. If the data lies on a curved manifold, geodesic distances (distance along the manifold surface) may be more appropriate.

Visual intuition. In 2D, draw the "unit circle" for each metric — the set of points at distance 1 from the origin. Euclidean gives a circle. Manhattan gives a diamond (rotated square). Supremum gives an axis-aligned square. The shape reveals what each metric considers "equidistant." For a query point, KNN's nearest neighbors are the training points inside the smallest such shape that encloses exactly $K$ of them. Euclidean draws a growing circle; Manhattan draws a growing diamond.

Pitfalls.

Not normalizing. The single most common KNN failure mode. A feature measured in dollars (range 0–100,000) will completely swamp a feature measured as a ratio (range 0–1). Always `StandardScaler` or `MinMaxScaler` first.
Euclidean in high dimensions. Above ~20 dimensions, Euclidean distances between random points become nearly identical. KNN with Euclidean breaks down. Consider Manhattan or dimensionality reduction first.
Forgetting to handle missing values. Any `NaN` in any dimension makes the distance `NaN`. Impute or use Gower distance (Section 10.8).
Using Supremum when all dimensions matter. Supremum only looks at the worst dimension. If 9 out of 10 features match perfectly but the 10th differs by 100, Supremum says distance = 100 — ignoring the 9 perfect matches entirely. Use only when the "worst-case" dimension is what you actually care about.

Four numeric distances, one family (Minkowski). Euclidean is the geometric default; Manhattan is more robust in high dimensions and against outliers; Supremum looks only at the worst dimension. Normalize first, then pick the metric that matches your data's nature. Next: what if your dataset mixes nominal, ordinal, binary, and numeric attributes in a single table?

Real-world & domain connection. Euclidean distance powers k-means clustering, PCA, and most "vanilla" ML pipelines. Manhattan distance is the workhorse of LASSO regression ( $L_{1}$ regularization) and robust statistics. Chebyshev distance is used in warehouse logistics (a gantry crane moving simultaneously on x and y axes takes time proportional to the max distance, not the sum), in CNC machining path planning, and in chess AI evaluation. The Minkowski family also appears in $L_{p}$ regularization — $L_{1}$ (lasso) for sparsity, $L_{2}$ (ridge) for smoothness — connecting distance metrics directly to model training.

10.8 Proximity Measures for Mixed-Type Attributes

Hook. A bank wants to decide if a loan applicant is similar to past defaulters. The data has: gender (nominal), credit grade (ordinal: poor/fair/good/excellent), income (numeric), and default history (binary, asymmetric). One formula cannot handle all four. Do you compute four separate distances and then… average them? What if some attributes are missing? This is the mixed-type problem — and Gower distance is the answer.

Intuition + Analogy. Gower distance is like a report card with different grading systems for different subjects. Math is graded 0–100 (numeric), Art is graded "pass/fail" (binary), Conduct is graded "poor/fair/good/excellent" (ordinal), and Homeroom is just a room number (nominal). To get one overall "distance" between two students, you first grade each subject using its own scale, then average those grades — but only for subjects where both students have scores. If one student missed the Art exam, you skip Art and average over the remaining subjects. That is Gower: per-attribute distance, weighted average, missing-aware.

10.8.1 Gower Distance

Real-world datasets rarely contain only one type of attribute. They mix nominal, ordinal, binary (symmetric and asymmetric), and numeric attributes in a single table. Gower distance (Gower, 1971) handles this by computing a per-attribute dissimilarity using the appropriate formula for each attribute's type, then taking a weighted average.

Gower distance formula:

$d (i, j) = \frac{\sum _{f = 1}^{p} δ _{ij}^{(f)} \cdot d _{ij}^{(f)}}{\sum _{f = 1}^{p} δ _{ij}^{(f)}}$

where:

$p$ = total number of attributes
$d_{ij}^{(f)}$ = dissimilarity between objects $i$ and $j$ on attribute $f$ , computed using the formula appropriate for attribute $f$ 's type (nominal, ordinal, binary symmetric, binary asymmetric, or numeric — all normalized to $[0, 1]$ range)
$δ_{ij}^{(f)}$ = indicator:
$1$ if both objects have a (non-missing) value for attribute $f$
$0$ if either object has a missing value for attribute $f$
The denominator is the number of attributes actually used (non-missing for both objects)

Weighted Gower distance:

$d (i, j) = \frac{\sum _{f = 1}^{p} w _{f} \cdot δ _{ij}^{(f)} \cdot d _{ij}^{(f)}}{\sum _{f = 1}^{p} δ _{ij}^{(f)}}$

By default, $w_{f} = 1$ for all attributes. Domain knowledge can assign higher weights to more important attributes. For example, in predicting loan default, income might get weight $1.0$ while marital status gets weight $0.5$ .

The result is always in $[0, 1]$ because each per-attribute $d_{ij}^{(f)}$ is normalized to $[0, 1]$ and the formula is a weighted average.

Worked example — Three mixed attributes:

1	R	excellent	475
2	B	good	10
3	G	fair	1000
4	R	excellent	500

Step 1: Compute per-attribute dissimilarities.

Color (nominal, $p_{color} = 1$ ): $d_{color} = (1 - m) /1$ where $m = 1$ if match, $0$ otherwise.

| Pair | Match? | $d_{color}$ |

(1,2)	No	1
(1,3)	No	1
(1,4)	Yes	0
(2,3)	No	1
(2,4)	No	1
(3,4)	No	1

Quality (ordinal): States: poor, fair, good, excellent. $M = 4$ . Ranks: poor=1, fair=2, good=3, excellent=4. Normalized = $(r ank - 1) /3$ : poor=0, fair=0.333, good=0.667, excellent=1.

Normalized values: Obj1=1, Obj2=0.667, Obj3=0.333, Obj4=1.

Ordinal distance = absolute difference of normalized values:

| Pair | Calculation | $d_{qual}$ |

(1,2)	$∣1 - 0.667∣$	0.333
(1,3)	$∣1 - 0.333∣$	0.667
(1,4)	$∣1 - 1∣$	0
(2,3)	$∣0.667 - 0.333∣$	0.333
(2,4)	$∣0.667 - 1∣$	0.333
(3,4)	$∣0.333 - 1∣$	0.667

Quantity (numeric): Normalize by range: $d_{quant} = \frac{∣ x _{i} - x _{j} ∣}{m a x - m i n}$ . $max = 1000$ , $min = 10$ , range = 990.

| Pair | Calculation | $d_{quant}$ |

(1,2)	$∣475 - 10∣/990 = 465/990$	0.470
(1,3)	$∣475 - 1000∣/990 = 525/990$	0.530
(1,4)	$∣475 - 500∣/990 = 25/990$	0.025
(2,3)	$∣10 - 1000∣/990 = 990/990$	1.000
(2,4)	$∣10 - 500∣/990 = 490/990$	0.495
(3,4)	$∣1000 - 500∣/990 = 500/990$	0.505

Step 2: Combine using Gower formula (all $δ = 1$ , $w_{f} = 1$ ):

$d (i, j) = \frac{d _{color} + d _{qual} + d _{quant}}{3}$

(1,2)	1	0.333	0.470	1.803	0.601
(1,3)	1	0.667	0.530	2.197	0.732
(1,4)	0	0	0.025	0.025	0.008
(2,3)	1	0.333	1.000	2.333	0.778
(2,4)	1	0.333	0.495	1.828	0.609
(3,4)	1	0.667	0.505	2.172	0.724

Most similar: Objects 1 and 4 ( $d \approx 0.008$ ) — same color (R), same quality (excellent), nearly identical quantity (475 vs 500). Most dissimilar: Objects 2 and 3 ( $d \approx 0.778$ ) — different color, different quality (good vs fair), extreme quantity gap (10 vs 1000).

Sense-check: Objects 1 and 4 are almost twins — only a 25-unit difference in quantity out of a 990-unit range. The Gower distance correctly captures this. ✓

Scope & Assumptions. Gower distance assumes:

Each per-attribute distance is normalized to $[0, 1]$ — this is why we used nominal fraction, ordinal normalization, and range-scaled Manhattan for numeric.
Missing values are handled by exclusion ( $δ = 0$ ), not imputation. This works well for sparse missingness but can be problematic if missingness is systematic (e.g., high-income individuals refusing to disclose income).
All attributes contribute equally by default ( $w_{f} = 1$ ). If attribute importance varies dramatically, set weights explicitly.
The weighted average is valid — this assumes the per-attribute distances are comparable, which is guaranteed by the $[0, 1]$ normalization.

Visual intuition. Picture a dashboard with one gauge per attribute, each showing 0 to 1. For two objects, each gauge needle swings to the per-attribute distance. The Gower distance is the average position of all needles (weighted, if you choose). Missing attributes have their gauge dark — it does not count. The final number is one clean summary of an otherwise messy multi-scale comparison.

Pitfalls.

Forgetting to normalize numeric attributes. If Quantity were left as raw numbers, the distance contribution would be hundreds of times larger than the nominal and ordinal contributions. Always normalize each numeric attribute to $[0, 1]$ using range or z-score before plugging into Gower.
Treating all binaries as symmetric. In the loan default example, "previously defaulted" is asymmetric — both not having defaulted is far less informative than both having defaulted. Mixing symmetric and asymmetric binary formulas correctly per attribute is essential.
Missingness patterns. If 80% of objects are missing attribute X, Gower effectively ignores X for most pairs. Yet X might be the most predictive attribute. Consider imputation before distance computation when missingness is high.
Weight selection. Setting $w_{f}$ arbitrarily can overfit. Cross-validation is the proper way to learn attribute weights (see Section 10.11).

Gower distance is the universal translator for mixed data: use each attribute's native distance formula, normalize to $[0, 1]$ , handle missing values by exclusion, and average. It is the standard answer to "how do I compute distance when my columns are not all numbers?" Next: a specialized similarity measure for text — where the data is not rows of a table but bags of words.

Real-world & domain connection. Gower distance is implemented in R's `cluster` package (`daisy()` function) and Python's `gower` library. It is the default distance metric in many clinical research pipelines where patient data mixes lab results (numeric), diagnoses (binary), and severity grades (ordinal). In credit scoring, Gower distance identifies similar past loan applicants to assess default risk. In ecology, it computes dissimilarity between field sites that mix soil pH (numeric), vegetation type (nominal), and disturbance level (ordinal). The Gower distance was introduced by J.C. Gower in 1971 and remains the most widely cited method for mixed-type proximity after more than 50 years.

10.9 Cosine Similarity for Text and Document Retrieval

Hook. You type "best laptop for programming" into Google. Google has billions of documents. None of them contains exactly your four words in that order. Yet the right results appear at the top. How? By treating your query and every document as an arrow in a high-dimensional word-space and measuring the angle between them — not the distance. This is cosine similarity, and it is why search works.

Intuition + Analogy. Imagine every document is a shopping list of words with quantities. "team=5, score=3, win=2" is one list. A second list is "team=3, score=2, play=1." If you compare these lists by counting how many words they share (dot product), you get a sense of overlap. But longer documents naturally have higher word counts — a 10-page article will have a bigger dot product with everything than a 1-paragraph query, even if they are unrelated. Cosine similarity fixes this by dividing by the length of each list. It asks: "what fraction of their word-energy points in the same direction?" Two documents about sports will have their word-arrows pointing in similar directions; two documents on different topics will be nearly perpendicular. Length no longer matters — only direction.

10.9.1 Document-Term Matrix

In information retrieval and NLP, a collection of documents is represented by a document-term matrix. Each row is a document vector, each column is a unique term (keyword from the vocabulary), and each cell records the frequency (or TF-IDF weight) of that term in that document.

The matrix is constructed after preprocessing: tokenizing, lowercasing, removing stop words (words without standalone meaning like "in", "at", "the", "is"), and stemming/lemmatizing words to their root forms.

Example document-term matrix (4 documents, 8 terms):

D1	5	0	3	2	0	0	2
D2	3	0	2	0	1	1	0
D3	0	7	0	2	0	3	0
D4	0	1	0	0	1	2	0

Each document is now an 8-dimensional vector. D1 = $(5, 0, 3, 2, 0, 0, 2, 0)$ . A new query — say, "team win" — becomes a vector in the same 8-D space: $Q = (1, 0, 0, 1, 0, 0, 0, 0)$ .

10.9.2 Cosine Similarity Formula

Cosine similarity measures the cosine of the angle $θ$ between two vectors. It ranges from $- 1$ (opposite directions) to $1$ (identical direction), with $0$ meaning orthogonal (no overlap).

$cosine similarity (D_{a}, D_{b}) = cos θ = \frac{D _{a} \cdot D _{b}}{∥ D _{a} ∥ \cdot ∥ D _{b} ∥}$

where:

$D_{a} \cdot D_{b} = \sum_{j} d_{aj} \cdot d_{bj}$ — the dot product (sum of term-by-term products)
$∥ D_{k} ∥ = \sum_{j} d_{k j}^{2}$ — the Euclidean norm (magnitude, length) of vector $D_{k}$

Because term frequencies are non-negative, cosine similarity for documents is always in $[0, 1]$ . $1$ means identical word distribution (same direction), $0$ means no shared words (perpendicular).

Worked example — D1 vs D2:

Dot product (term-by-term): $D_{1} \cdot D_{2} = (5 \times 3) + (0 \times 0) + (3 \times 2) + (2 \times 0) + (0 \times 1) + (0 \times 1) + (2 \times 0) + (0 \times 0) = 15 + 0 + 6 + 0 + 0 + 0 + 0 + 0 = 21$

Magnitudes: $∥ D_{1} ∥ = 5^{2} + 0^{2} + 3^{2} + 2^{2} + 0^{2} + 0^{2} + 2^{2} + 0^{2} = 25 + 9 + 4 + 4 = 42 \approx 6.481$

$∥ D_{2} ∥ = 3^{2} + 0^{2} + 2^{2} + 0^{2} + 1^{2} + 1^{2} + 0^{2} + 0^{2} = 9 + 4 + 1 + 1 = 15 \approx 3.873$

Cosine similarity: $sim (D_{1}, D_{2}) = \frac{21}{6.481 \times 3.873} \approx \frac{21}{25.10} \approx 0.837$

Compare with D1 vs D3: $D_{1} \cdot D_{3} = (5 \times 0) + (0 \times 7) + (3 \times 0) + (2 \times 2) + (0 \times 0) + (0 \times 3) + (2 \times 0) + (0 \times 0) = 4$ $∥ D_{3} ∥ = 0^{2} + 7^{2} + 0^{2} + 2^{2} + 0^{2} + 3^{2} + 0^{2} + 0^{2} = 49 + 4 + 9 = 62 \approx 7.874$ $sim (D_{1}, D_{3}) = \frac{4}{6.481 \times 7.874} \approx \frac{4}{51.03} \approx 0.078$

Sense-check: D1 and D2 share "team" and "score" heavily → high similarity (0.837). D1 and D3 share only "win" (2 occurrences) → low similarity (0.078). ✓

For search, a query $Q = (1, 0, 0, 1, 0, 0, 0, 0)$ ("team win") against all documents: $sim (Q, D_{1}) = \frac{5 + 2}{2 \times 6.481} \approx \frac{7}{9.165} \approx 0.764$ D1 is the best match — it contains both query terms with high frequency. D3 shares "win" (2) but not "team" — lower rank.

Scope: Cosine vs Euclidean for text. Euclidean distance on raw term frequencies penalizes document length — a long document about sports and a short document about sports can be far apart in Euclidean space simply because one has more words. Cosine similarity ignores length and compares only the pattern of word usage. For text, always prefer cosine (or variants like TF-IDF weighted cosine). For general numeric data where magnitude matters, use Euclidean or Manhattan.

Visual intuition. Picture each document as an arrow from the origin in an 8-dimensional space (one axis per term). D1 points strongly along the "team," "score," and "championship" axes. D2 points along "team," "score," "season," and "play." The angle between D1 and D2 is small ( $cos θ \approx 0.837$ means $θ \approx 3 3^{\circ}$ ) — they point in roughly the same direction. D1 and D3 are nearly perpendicular ( $θ \approx 8 6^{\circ}$ ). The query is a short arrow; the search engine finds documents whose arrows are most closely aligned with it.

Pitfalls.

Using Euclidean on text. Raw term-frequency Euclidean distance makes long documents seem far from everything and short documents seem close to everything. Always use cosine (or normalize vectors to unit length first, which makes Euclidean and cosine equivalent).
Ignoring TF-IDF. Raw term frequency over-weights common words. "The" might appear 50 times and dominate the dot product. TF-IDF (term frequency × inverse document frequency) down-weights terms that appear in many documents and up-weights rare, discriminative terms. Always prefer TF-IDF over raw counts in practice.
Zero vectors. If a document has no terms from the vocabulary (or a query uses only out-of-vocabulary words), its vector is all zeros. Cosine similarity with a zero vector is undefined (division by zero). Handle this edge case by returning 0 similarity.
Synonymy and polysemy. "Car" and "automobile" are different columns with zero dot product even though they mean the same thing. "Bank" (river) and "bank" (financial) share a column but mean different things. Cosine similarity on surface words cannot handle these — this is why modern search uses embeddings (word2vec, BERT) that capture meaning beyond exact word matching.

Cosine similarity measures the angle between document vectors, ignoring length to focus on the pattern of term usage. It is the standard similarity measure in information retrieval, search engines, and any domain where data is naturally represented as sparse count vectors. Next: a fundamental problem that affects ALL distance metrics — why more features can make your nearest neighbors meaningless.

Real-world & domain connection. Cosine similarity powers the vector space model of information retrieval (Salton, 1970s), which is the foundation of every modern search engine. Google's PageRank determines importance, but cosine similarity (on TF-IDF vectors) determines relevance. In recommender systems, item-item cosine similarity on user rating vectors finds "similar movies." In bioinformatics, cosine similarity on gene expression vectors groups co-regulated genes. In plagiarism detection, cosine similarity between student submissions flags suspicious overlap. The formula is deceptively simple — a normalized dot product — but it scales to billions of documents and remains the first line of defense in text matching after 50+ years.

10.10 Curse of Dimensionality

Hook. Add one feature to your dataset — accuracy goes up. Add ten — even better. Add a hundred — and suddenly KNN can't tell neighbors from strangers. Every point looks the same distance from every other point. More information has made you blind. This is the curse of dimensionality, and it is the single biggest threat to instance-based learning.

Intuition + Analogy. Imagine you are in a 1-dimensional world — a long hallway. Two people standing 1 meter apart are close. Now stretch the hallway into a 2D room — to stay 1 meter apart, they need to agree on both x AND y. Now stretch to a 100-dimensional hypercube. To be "close," two people must agree on all 100 coordinates simultaneously. The volume of space explodes so fast that random points are almost never close.

Think of it like this: in 1D, half of all random points fall within distance 0.5 of a given point. In 2D, only 25% fall within a circle of radius 0.5. In 100D, virtually zero random points fall within a hypersphere of radius 0.5 — the volume is concentrated in the corners, far from the center. KNN's "find the nearest neighbor" fails because there is no "near" anymore — everybody is far.

The formal name is the curse of dimensionality (Bellman, 1961). It is not just a KNN problem — it affects clustering, density estimation, and any method that relies on distances in high-dimensional spaces.

10.10.1 The Problem

Dimensionality refers to the number of attributes (features) in a dataset, denoted $d$ . The curse of dimensionality is the phenomenon where, as $d$ increases, pairwise distances between points converge to similar values — making the very concept of "nearest neighbor" meaningless.

The mathematical intuition: Consider a $d$ -dimensional unit hypercube $[0, 1]^{d}$ . Two random points drawn uniformly from this cube have expected Euclidean distance:

$E [d (x_{i}, x_{j})] \propto d$

The expected distance grows with $d$ . But the ratio of the distance to the nearest neighbor vs the distance to the farthest neighbor approaches 1 as $d \to \infty$ . In plain terms: in high dimensions, your nearest neighbor is almost as far as your farthest neighbor. There is no "near" anymore.

Why this destroys KNN: In a dataset with 100 attributes where only 2 are truly relevant to the target, the remaining 98 irrelevant attributes contribute random noise to every distance calculation. Two records that are truly identical on the 2 relevant attributes will still be far apart in the 100-dimensional space because the 98 noise dimensions push them apart. KNN's "nearest neighbors" are determined by noise, not signal. The inductive bias. "nearby points have similar labels" — collapses when "nearby" stops meaning anything.

Concrete demonstration: Consider a unit hypercube $[0, 1]^{d}$ . Sample 1000 random points. Compute the ratio:

$r = \frac{distance to nearest neighbor}{distance to farthest neighbor}$

1	~0.001	~1.0	~0.001
2	~0.03	~1.4	~0.02
5	~0.25	~2.2	~0.11
10	~0.55	~3.2	~0.17
20	~0.95	~4.5	~0.21
50	~1.8	~7.1	~0.25
100	~2.8	~10.0	~0.28

As $d$ grows, the ratio $r$ creeps toward 1. By $d = 100$ , the nearest neighbor is only about 3.6× closer than the farthest — a weak basis for a "nearest neighbor" vote. In contrast, at $d = 2$ , the nearest neighbor is 50× closer than the farthest — a strong signal.

10.10.2 Solutions

Solution 1 — Attribute weighting (axis stretching). Multiply each dimension by a weight $z_{j}$ before computing distance:

$d (i, j) = k = 1 \sum d z_{k} \cdot (x_{ik} - x_{j k})^{2}$

Stretch relevant axes (large $z_{k}$ ), shrink irrelevant axes (small $z_{k}$ ). The weights can be learned by cross-validation: try different weight vectors, pick the one that minimizes classification error on held-out data. This is equivalent to metric learning — learning a Mahalanobis-like distance tailored to your task.

Solution 2 — Feature selection. Eliminate irrelevant attributes entirely ( $z_{k} = 0$ ). Methods include filter methods (correlation with target), wrapper methods (cross-validate feature subsets), and embedded methods (LASSO regularization). Moore and Lee (1994) developed efficient leave-one-out cross-validation for feature selection in KNN.

Solution 3 — Dimensionality reduction. Project data onto a lower-dimensional subspace using PCA, t-SNE, or autoencoders — keeping the dimensions that capture the most variance or structure. Then run KNN in the reduced space.

Solution 4. Use Manhattan distance. The $L_{1}$ norm is less affected by the curse of dimensionality than the $L_{2}$ norm. In high dimensions, Manhattan distances retain more contrast between near and far points. This is why Manhattan is preferred for high-dimensional data (Section 10.7.3).

Scope & Assumptions. The curse of dimensionality assumes features are largely independent and uniformly distributed. If your data actually lies on a low-dimensional manifold (e.g., a 2D surface curled inside a 100D space), then the intrinsic dimensionality is only 2, and KNN can still work — but only if you use a distance metric that respects the manifold structure. The standard Euclidean distance in the ambient 100D space will still fail.

Visual intuition. In 1D: points are on a line. Nearest neighbor is obvious. In 2D: points on a plane. Still clear. In 3D: points in a cube. Getting harder to visualize, but nearest neighbors still identifiable. Now imagine 100D: every point is in the corner of a hypercube. The hypercube has $2^{100}$ corners — an astronomical number. Your 1000 training points occupy a negligible fraction of them. The space is mostly empty, and every point is isolated. The "neighborhood" around any query point contains almost no training examples.

Pitfalls.

"More features = better model." The single most dangerous assumption in applied ML. Every irrelevant feature you add dilutes the signal in your distance metric. Be ruthless about feature selection.
Normalization doesn't fix the curse. Normalizing all features to $[0, 1]$ prevents scale domination but does not fix the fundamental problem that random noise dimensions still contribute to distance. Weighting or eliminating features is the only cure.
Thinking Euclidean in high-D is still Euclidean. Intuition from 2D/3D geometry fails catastrophically in high dimensions. The volume of a hypersphere is concentrated in a thin shell near its surface. The diagonals of a hypercube are far longer than intuition suggests. Trust the math, not your 3D geometric imagination.
Ignoring intrinsic dimensionality. If your 1000-D face images actually lie on a ~50-D manifold, PCA to 50 dimensions can rescue KNN. Always estimate intrinsic dimensionality before declaring KNN dead.

As dimensions grow, all points look equally far apart. The nearest-neighbor concept — the foundation of instance-based learning — collapses. Fight back with attribute weighting, feature selection, dimensionality reduction, or switching to Manhattan distance. Next: a technique that helps you tune KNN's hyperparameters and validate that your distance metric actually works — cross-validation.

Real-world & domain connection. The curse of dimensionality is not unique to ML. In database indexing, high-dimensional indexes (R-trees, kd-trees) degrade to linear scan above ~10–20 dimensions. In numerical integration, the number of sample points needed for a given accuracy grows exponentially with dimension. In optimization, high-dimensional search spaces are mostly empty plateaus — gradient-free methods struggle. The practical lesson: never blindly throw features at a distance-based model. Netflix's recommendation system uses dimensionality reduction (matrix factorization) to compress millions of user-item interactions into ~100 latent factors before computing similarities. Genomics pipelines routinely reduce tens of thousands of gene expression measurements to a few dozen principal components before clustering. The curse is real, but dimensionality reduction is the standard antidote.

10.11 Cross-Validation (K-Fold)

Hook. You split your data: 80% training, 20% test. Accuracy = 94%. Great — but was that luck? What if a different split gave 82%? A single train-test split is like judging a restaurant based on one meal. Cross-validation eats at the restaurant $K$ times and averages the reviews. It is the gold standard for honest model evaluation — and it is free in KNN, because "training" costs nothing.

Intuition + Analogy. A teacher wants to estimate how well students will do on the final exam. She has 5 past exams. Instead of using 4 to predict scores on the 5th (one split), she does this: use exams {1,2,3,4} to predict exam 5; then {1,2,3,5} to predict 4; then {1,2,4,5} to predict 3; and so on. She averages the 5 accuracy estimates. Every exam serves as both training AND test data exactly once. No exam gets special treatment. The final average is a far more reliable estimate than any single split.

In KNN, cross-validation has a special superpower: since KNN has no training phase, re-running it on different training folds is computationally cheap. You just exclude some stored examples and query them as if they were new. No model to retrain. This makes K-fold CV on KNN nearly $K$ times the cost of a single prediction run — not $K$ times a full training cycle.

10.11.1 Concept and Purpose

Cross-validation is a resampling technique to get a more reliable estimate of model performance and to avoid bias from any single train-test split. It ensures that every data point participates in both training and testing, giving a lower-variance estimate of generalization error.

In the context of KNN specifically, cross-validation serves two purposes:

Hyperparameter tuning — choosing $K$ (the number of neighbors) and the distance metric.
Attribute weight learning — finding optimal weights $z_{j}$ to stretch/shrink axes (curse of dimensionality solution).

10.11.2 K-Fold Cross-Validation Procedure

The K-Fold CV algorithm:

Split the dataset of $N$ samples into $K$ equal-sized folds. Each fold has approximately $N / K$ examples. (Typical choices: $K = 5$ or $K = 10$ .)
Iterate $K$ times. In iteration $i$ :

Use $K - 1$ folds as the training set
Use the remaining 1 fold as the test set
Train the model (for KNN: just store the training examples) and compute accuracy (or other metric) on the test fold

Average the $K$ performance scores to get the final cross-validated estimate:

$CV accuracy = \frac{1}{K} i = 1 \sum K accuracy_{i}$

Worked example: $N = 100$ , $K = 5$ .

Each fold has 20 records.

1	2, 3, 4, 5	1	80	20
2	1, 3, 4, 5	2	80	20
3	1, 2, 4, 5	3	80	20
4	1, 2, 3, 5	4	80	20
5	1, 2, 3, 4	5	80	20

Suppose the accuracies are: 0.85, 0.90, 0.88, 0.87, 0.90.

$CV accuracy = \frac{0.85 + 0.90 + 0.88 + 0.87 + 0.90}{5} = \frac{4.40}{5} = 0.88$

The standard deviation of the 5 scores (≈0.019) tells you how stable the model is across different splits. High variance across folds suggests the model is sensitive to which data it sees — a red flag.

Special case. Leave-One-Out CV (LOOCV): When $K = N$ , each fold contains exactly one example. Every example serves as the test set exactly once, trained on all $N - 1$ others. LOOCV is computationally expensive for most models (requires $N$ retraining runs), but for KNN it is surprisingly practical — because there is no training phase, LOOCV for KNN just means querying each stored example against all others. Moore and Lee (1994) exploited this for efficient feature selection in KNN.

Scope: When K-Fold CV is reliable. CV estimates generalize to unseen data from the same distribution. If your data is a random sample from the population, CV accuracy ≈ future performance. But if the data has temporal structure (time series), spatial correlations, or group-level dependencies, random K-Fold CV leaks information across folds and gives overly optimistic estimates. Use time-series split or group K-Fold for those cases.

Visual intuition. Picture the dataset as a pie cut into $K = 5$ equal slices. In round 1, you hide slice 1 behind your back, train on slices 2–5, then test on slice 1. Record the score. Repeat for each slice being the hidden one. The final score is the average of all 5 rounds. Every crumb of data got tested exactly once.

Pitfalls.

Data leakage. If you normalize or impute using statistics computed on the full dataset before splitting into folds, the test fold's information leaks into the training folds. Always fit the scaler/imputer on training folds only, then transform the test fold.
$K$ too small. $K = 2$ gives only two accuracy estimates — high variance. $K = N$ (LOOCV) gives $N$ estimates but can be computationally expensive. $K = 5$ or $K = 10$ is the standard sweet spot.
Imbalanced classes. If one class has 95% of examples, random K-Fold CV might produce folds where the minority class is absent from training or test. Use stratified K-Fold to preserve class proportions in every fold.
Using CV accuracy as final model accuracy. CV accuracy estimates how well your modeling approach (algorithm + hyperparameters) generalizes. The final model you deploy should be retrained on all $N$ examples. Its true performance is approximately the CV estimate, but never exactly.

K-Fold cross-validation gives a low-variance, unbiased estimate of model performance by rotating every data point through the test set. For KNN specifically, CV is computationally cheap (no retraining) and essential for tuning $K$ , choosing distance metrics, and learning attribute weights. Next: the algorithm that ties all of this together. K-Nearest Neighbors.

Real-world & domain connection. Cross-validation is universal in ML. Kaggle competitions are won and lost on CV strategy — competitors who overfit to the public leaderboard (a single test split) lose when the private test set is revealed. In medical diagnosis, CV ensures a model's reported accuracy is not an artifact of lucky patient selection. In finance, time-series CV (walk-forward validation) ensures trading models are tested on future data they haven't seen — the only kind of test that matters. The $K$ -fold procedure was formalized by Stone (1974) and Geisser (1975) and has been standard practice for 50 years.

10.12 K-Nearest Neighbors (KNN) Algorithm

Hook. You have never seen this flower before. But it has long, narrow petals and short, wide sepals. You flip through your field guide, find the three most similar-looking flowers, and notice two of them are Iris versicolor. You label the unknown flower the same way — not because you built a botanical theory, but because its neighbors said so. This is K-Nearest Neighbors: the simplest, laziest, and surprisingly effective learning algorithm in machine learning.

Intuition + Analogy. "If it walks like a duck and quacks like a duck, it is probably a duck." KNN does not claim certainty. It claims probability based on local evidence. You are judged by the company you keep — literally. In a new city, you ask your three nearest neighbors which restaurant to try. Two say "the Italian place on Oak Street," one says "the sushi bar on Elm." Majority rules: Italian it is. KNN works exactly the same way in feature space: find the $K$ closest training examples, take a vote.

The key tradeoff: small $K$ (like $K = 1$ ) makes the model sensitive to every local wiggle and outlier — it is like asking only your immediate next-door neighbor, who might be eccentric. Large $K$ smooths out noise but blurs sharp boundaries — like polling the entire neighborhood and getting a bland average. There is no universally correct $K$ ; cross-validation picks the best one for your data.

10.12.1 KNN Classification

KNN is the classic example of instance-based (lazy) learning. Let us walk through it using the procedural spine.

Purpose: Classify a new query point $x_{q}$ into one of the discrete classes in $V = {v_{1}, v_{2}, \dots, v_{c}}$ by consulting the $K$ most similar training examples and taking a majority vote.

Inputs:

Training set: $n$ labeled examples ${(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})}$
Hyperparameter: $K$ (number of neighbors, a positive integer, typically odd to avoid ties)
Distance metric: $d (\cdot, \cdot)$ (Euclidean by default, but any from Sections 10.4–10.8 works)
Query point: $x_{q}$ (unlabeled)

Output: Predicted class label $y^(x_{q}) \in V$ .

Steps:

Choose $K$ . Odd values (1, 3, 5, …) are preferred to reduce ties. Tune using cross-validation.

Calculate distances. For every training example $x_{i}$ , compute $d (x_{q}, x_{i})$ using the chosen metric. This produces $n$ distance values.

Sort. Arrange the $n$ distances in ascending order.

Select neighbors. Take the first $K$ entries from the sorted list. These are the $K$ -nearest neighbors: $x_{(1)}, x_{(2)}, \dots, x_{(K)}$ , with corresponding labels $y_{(1)}, y_{(2)}, \dots, y_{(K)}$ .

Majority vote. Assign to $x_{q}$ the most frequent class among the $K$ neighbors:

$y^(x_{q}) = ar g v \in V max i = 1 \sum K δ (v, y_{(i)})$

where $δ (a, b) = 1$ if $a = b$ and $0$ otherwise. The sum counts how many of the $K$ neighbors belong to class $v$ . The $ar g max$ picks the class with the highest count.

Key notation: $max$ returns the highest value (e.g., $max [75, 92, 88] = 92$ ). $ar g max$ returns where that value occurs (e.g., $ar g max [75, 92, 88] = 2$ , the index of 92). In KNN voting, $ar g max$ returns the class label, not the vote count.

Trace — Full worked example with $K = 3, 5, 7$ :

Training data:

| Point | $x_{1}$ | $x_{2}$ | Class |

X1	7	7	−
X2	7	4	+
X3	3	4	+
X4	1	4	−
X5	4	5	+
X6	4	7	+
X7	6	3	−
X8	10	5	−

Query point: $x_{q} = (1, 1)$

Step 2 — Euclidean distances from $x_{q}$ :

$d (x_{q}, X_{1}) d (x_{q}, X_{2}) d (x_{q}, X_{3}) d (x_{q}, X_{4}) d (x_{q}, X_{5}) d (x_{q}, X_{6}) d (x_{q}, X_{7}) d (x_{q}, X_{8}) = (7 - 1)^{2} + (7 - 1)^{2} = 36 + 36 = 72 \approx 8.485 = (7 - 1)^{2} + (4 - 1)^{2} = 36 + 9 = 45 \approx 6.708 = (3 - 1)^{2} + (4 - 1)^{2} = 4 + 9 = 13 \approx 3.606 = (1 - 1)^{2} + (4 - 1)^{2} = 0 + 9 = 9 = 3.000 (closest) = (4 - 1)^{2} + (5 - 1)^{2} = 9 + 16 = 25 = 5.000 = (4 - 1)^{2} + (7 - 1)^{2} = 9 + 36 = 45 \approx 6.708 = (6 - 1)^{2} + (3 - 1)^{2} = 25 + 4 = 29 \approx 5.385 = (10 - 1)^{2} + (5 - 1)^{2} = 81 + 16 = 97 \approx 9.849 (farthest)$

Step 3–4 — Sorted nearest neighbors:

1	X4	3.000	−
2	X3	3.606	+
3	X7	5.385	−
4	X5	5.000	+
5	X2	6.708	+
6	X6	6.708	+
7	X1	8.485	−
8	X8	9.849	−

Step 5 — Predictions:

$K = 3$ : Neighbors X4(−), X3(+), X7(−) → Votes: − = 2, + = 1 → Prediction: − (negative)
$K = 5$ : Add X5(+) and X2(+) → Votes: − = 2, + = 3 → Prediction: + (positive)
$K = 7$ : Add X6(+) and X1(−) → Votes: − = 3, + = 4 → Prediction: + (positive)

The prediction changes with $K$ . This is why choosing $K$ carefully — through cross-validation — is critical.

Iris dataset example: The Iris flower dataset has 4 features (sepal length, sepal width, petal length, petal width) and 3 classes (Setosa, Versicolor, Virginica). With $K = 3$ , a query flower with long narrow petals might have 2 Versicolor neighbors and 1 Setosa neighbor → predicted Versicolor. Different $K$ values can produce different predictions at decision boundaries.

Complexity & Cost:

Training time: $O (1)$ — just store the data.
Prediction time: $O (n \cdot d)$ for distance computation + $O (n lo g n)$ for sorting (or $O (n \cdot K)$ with a partial sort) = $O (n \cdot d + n lo g n)$ per query. Dominated by distance calculation for large $n$ .
Memory: $O (n \cdot d)$ — must store the entire training set.
Scaling: Prediction cost grows linearly with $n$ . For $n > 1 0^{6}$ , becomes impractical without approximate nearest-neighbor indexes (kd-trees, ball trees, LSH, FAISS).

When to use: KNN is the right tool when the decision boundary is complex and local, when you have modest-sized clean data (<100K examples), and when prediction latency is not critical. It is also the go-to baseline — if your fancy deep learning model cannot beat KNN with $K = 5$ , something is wrong.

Tie-breaking strategies (when no class has a clear majority):

Distance-weighted: Pick the class of the single nearest neighbor among the tied candidates.
Reduce $K$ : If $K = 4$ and the vote is 2-2, use $K = 3$ (drop the farthest neighbor) or $K = 1$ .
Lexicographic: Pick the class that comes first alphabetically (arbitrary but deterministic).
Weighted voting: Weight each neighbor's vote by $1/ d (x_{q}, x_{i})$ or $1/ d^{2}$ . Closer neighbors count more. This is the distance-weighted KNN variant and it naturally avoids most ties.

In practice, ties are rare for sensible choices of $K$ (odd, small relative to the number of classes) and have minor impact on overall accuracy.

Exam note: Expect a question where a query point and a small dataset are given. You must compute Euclidean distances, sort them, identify the $K$ nearest neighbors for a given $K$ (typically $K = 3$ , $K = 5$ ), and predict the class using majority voting. You may also be asked to compare predictions for different $K$ values.

10.12.2 KNN Regression

KNN can also predict continuous (numeric) target values — this is KNN regression. The procedure is identical to classification for steps 1–4. For step 5, replace majority voting with a simple average:

$y^(x_{q}) = \frac{1}{K} i = 1 \sum K y_{(i)}$

where $y_{(i)}$ is the target value of the $i$ -th nearest neighbor.

Worked example: The three nearest neighbors of a query house have sale prices: 36, 35, and 45 (in lakhs or any unit).

$y^= \frac{36 + 35 + 45}{3} = \frac{116}{3} \approx 38.67$

Sense-check: 38.67 is between the minimum (35) and maximum (45) of the neighbors — the average always is. A large outlier among neighbors (e.g., 36, 35, 200) would pull the prediction to $\approx 90.33$ — misleading. This is why outlier removal is critical for KNN regression too.

Distance-weighted KNN regression weights each neighbor's target by the inverse of its distance, giving closer neighbors more influence:

$y^(x_{q}) = \frac{\sum _{i = 1}^{K} w _{i} \cdot y _{(i)}}{\sum _{i = 1}^{K} w _{i}}, where w_{i} = \frac{1}{d ( x _{q} , x _{(i)} ) ^{2}}$

10.12.3 True Function $F^{*}$

Hook. Behind every dataset is a hidden truth — the real relationship between inputs and outputs that nature uses. If you knew it, you could predict perfectly. You never do. The gap between what KNN guesses and what the universe actually does is the central tension of all machine learning.

True function $F^{*}$ is the real, unknown underlying mapping from inputs to outputs in the world — the function we are trying to estimate. No learning algorithm ever sees $F^{*}$ directly; it only sees noisy samples $(x_{i}, F^{*} (x_{i}) + noise)$ .

In KNN (instance-based learning), the prediction approximates the nearest stored observation:

$F^{*} (x_{q}) \approx f (x_{N})$

where $x_{N}$ is the nearest training example to the query point $x_{q}$ .

In model-based learning, a global function $f^$ is learned from all training data, and:

$F^{*} (x_{q}) \approx f^(x_{q})$

Both are approximations. Neither is $F^{*}$ itself. The estimation error comes from three sources: (1) finite training data, (2) noise in the training labels, and (3) the mismatch between the model's hypothesis space and the true $F^{*}$ .

Worked example: Suppose the true underlying function is $F^{*} (x) = x^{2}$ — but we do not know this.

Training examples (noiseless, for simplicity):

$F^{*} (1) = 1$
$F^{*} (2) = 4$
$F^{*} (3) = 9$

Query point: $x_{q} = 2.5$ .

KNN ( $K = 1$ ): Nearest neighbor is $x = 2$ (distance 0.5) or $x = 3$ (distance 0.5) — tie. Either way: $F^{*} (2.5) \approx f (2) = 4 or F^{*} (2.5) \approx f (3) = 9$

KNN ( $K = 3$ , average): $F^{*} (2.5) \approx \frac{1 + 4 + 9}{3} = \frac{14}{3} \approx 4.67$

True value: $F^{*} (2.5) = 2. 5^{2} = 6.25$ .

Model-based (linear regression would be wrong since $x^{2}$ is not linear; polynomial regression of degree 2 could recover exactly): A model-based learner that discovers $f^(x) = x^{2}$ would give $F^{*} (2.5) = 6.25$ exactly.

The gap between KNN's approximation (4.67) and the truth (6.25) is the approximation error — the cost of using local neighbors instead of discovering the global pattern. But if $F^{*}$ were a jagged, non-polynomial shape, a global model would struggle while KNN would adapt locally. Neither wins universally.

Scope: The gap between $f^$ and $F^{*}$ . KNN is a non-parametric method — it makes no assumptions about the shape of $F^{*}$ . This gives it high flexibility but also means it needs dense training data to approximate $F^{*}$ well everywhere. A parametric model (like linear regression) assumes a shape (a line) and can extrapolate with fewer data points, but fails catastrophically if the assumption is wrong. The bias-variance tradeoff: KNN has low bias (few shape assumptions) but high variance (predictions change a lot with different training samples); linear regression has high bias but low variance.

Student Q&A (deduplicated):

Q: So the $F (x) = x^{2}$ example — that function would be discovered by model-based learning, right?

A: Yes, if the model-based learner had the right hypothesis class (polynomials). Model-based learning searches for a global pattern across all training data. Instance-based learning (KNN) does not search for a pattern at all — it looks at what happened near the query point and assumes the same thing will happen again. This means KNN can fit any shape — no "wrong hypothesis class" problem — but it cannot extrapolate. Ask KNN about $x_{q} = 10$ with training data only up to $x = 3$ and it still gives you 9 (the nearest known value). A model-based learner might correctly extrapolate to 100.

Q: What if there is an outlier in the training data and KNN treats it as the nearest neighbor?

A: Several students asked variations of this. There are three lines of defense:

Preprocessing: Remove or correct outliers before training. KNN is especially sensitive because every outlier can misclassify every query point in its Voronoi region.

Choose $K > 1$ : With $K = 1$ , a single outlier neighbor poisons the prediction. With $K = 5$ , four normal neighbors outvote one outlier. Larger $K$ smooths out isolated noise.

Distance weighting: Weight votes by $1/ d^{2}$ . A training point that exactly matches the query (distance 0) dominates; a distant outlier (even if among the $K$ nearest) gets a tiny weight.

There is a harder case: outliers in the test set (unseen real-world data). You cannot remove those. A new user on Netflix who has watched only one obscure documentary is an "outlier" — far from all other users in feature space, yet you must still recommend something. In that case, KNN does its best with whatever neighbors exist, possibly falling back to global popularity when local evidence is sparse.

Pitfalls (KNN-specific).

Choosing $K$ without cross-validation. Guessing $K = 3$ because "it's standard" is gambling. Small $K$ = high variance, jagged decision boundaries, sensitive to noise. Large $K$ = high bias, smooth boundaries, may miss local structure. Always cross-validate.

Forgetting to scale features. A feature with range 0–1000 dominates Euclidean distance over a feature with range 0–1. KNN has no built-in mechanism to handle this — unlike decision trees, which split on one feature at a time. Always `StandardScaler` or `MinMaxScaler`.

Using KNN on high-dimensional data without dimensionality reduction. Above ~20 dimensions with many irrelevant features, KNN degrades. Use PCA, feature selection, or Manhattan distance first.

Applying KNN to imbalanced classes. If class A has 1000 training examples and class B has 10, a $K = 15$ query will almost never predict B, even if B is the true class. Use distance-weighted voting or adjust the decision threshold.

Confusing KNN regression output with confidence. The average of neighbor values is a point estimate. It tells you nothing about how spread out those values are. The variance of the $K$ neighbor targets can serve as a rough uncertainty estimate — but it is not a formal confidence interval.

KNN is the canonical lazy learner: store everything, compute nothing upfront, and predict by asking the $K$ closest stored examples to vote. It is simple, assumption-free, and adapts locally — at the cost of high memory and slow predictions. Tune $K$ with cross-validation. Scale your features. Remove outliers. And remember: KNN approximates the true function $F^{*}$ from local evidence, not from a learned global formula. Next: how to implement this in code and what to watch for in practice.

Real-world & domain connection. KNN is the "hello world" of ML classifiers but far from a toy. It powered early handwriting recognition systems (USPS digit recognition used KNN on pixel features). In recommender systems, the "users who liked this also liked…" widget is essentially KNN on user-item matrices. In finance, KNN detects credit card fraud by finding transactions that are anomalously far from their neighbors. In medicine, KNN classifies tissue samples as benign or malignant based on nearest pathological precedents. The algorithm is implemented in every ML library (`sklearn.neighbors.KNeighborsClassifier`, `class::knn` in R) and remains the first baseline any practitioner should run — before reaching for neural networks, before gradient boosting, before anything complex. If your sophisticated model can't beat KNN, simplify.

10.13 Implementation Notes

Hook. You now understand every formula from nominal distance to Gower to cosine to KNN voting. Do you need to code any of it from scratch? No. scikit-learn does it in one line. But knowing what happens inside that line — the "breakdown" — is what separates a practitioner who debugs from one who guesses.

Intuition + Analogy. The "assemble, then breakdown" philosophy: when you want to build a bookshelf, you buy one from IKEA and assemble it (use the library). Later, when you want to understand why it holds weight, you take it apart and study the joints (break down the internals). In ML, assemble first — `KNeighborsClassifier(n_neighbors=5).fit(X, y).predict(X_test)` — get results. Then break down: what distance is it using? How does it handle ties? What happens with unscaled features? The breakdown makes you better. The assembly makes you productive.

10.13.1 Python Implementation of KNN

Code pattern (scikit-learn):

```python from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import train_test_split from sklearn.preprocessing import StandardScaler from sklearn.metrics import accuracy_score

# 1. Split X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

# 2. Scale (CRITICAL for KNN) scaler = StandardScaler() X_train = scaler.fit_transform(X_train) X_test = scaler.transform(X_test) # use SAME scaler, do NOT fit again

# 3. Fit and predict model = KNeighborsClassifier(n_neighbors=5) model.fit(X_train, y_train) y_pred = model.predict(X_test)

# 4. Evaluate print(accuracy_score(y_test, y_pred)) ```

Key parameters of `KNeighborsClassifier`:

`n_neighbors` = $K$ (default 5)

`metric` = distance type: `'euclidean'`, `'manhattan'`, `'minkowski'`, `'cosine'` (default `'minkowski'` with `p=2`, which is Euclidean)

`weights` = `'uniform'` (all neighbors equal) or `'distance'` (weight by inverse distance)

`algorithm` = `'auto'`, `'ball_tree'`, `'kd_tree'`, `'brute'` (indexing method for fast neighbor search)

Critical implementation pitfalls.

Fitting scaler on test data. `scaler.fit_transform(X_test)` leaks test information into training. Always `fit_transform` on train, `transform` only on test.

Forgetting to scale at all. If `X` has columns with different ranges, Euclidean distance is dominated by the widest column. Always scale.

Using `KNeighborsRegressor` for classification. For regression targets, use `KNeighborsRegressor`. The `.predict()` method returns averages, not class labels.

Large $K$ on small datasets. If $K >$ the number of examples in the smallest class, that class can never win a majority vote. Keep $K < min_{c} (n_{c})$ .

10.13.2 Practical Considerations

The "assemble then breakdown" approach:

Assemble: Use `KNeighborsClassifier` with sensible defaults. Get a baseline accuracy.

Breakdown: If accuracy is poor, investigate:

Are features scaled? (Check `X_train.std(axis=0)` — all should be ~1 after `StandardScaler`)

Is $K$ appropriate? (Cross-validate over [1, 3, 5, 7, 9, 11, 15, 21])

Is the distance metric right for the data types? (Nominal features need custom metric)

Are there irrelevant features? (Try feature selection or PCA)

Is the curse of dimensionality at play? (Check ratio of features to samples)

This mirrors the modern AI-driven development lifecycle: build fast with existing tools, then deep-dive into the parts that need understanding. You do not need to reimplement Euclidean distance — but you do need to know when it is the wrong choice.

KNN in code is one line of fit-predict. The entire mathematical machinery — distance computation, sorting, voting — runs silently. But every design choice (scaling, $K$ , metric, weighting) is yours to make. The breakdown is where the learning happens. Next: exam guidance — what to expect and how to prepare.

Real-world & domain connection. Beyond scikit-learn, approximate nearest-neighbor libraries like FAISS (Facebook AI Similarity Search) and Annoy (Spotify) scale KNN to billions of vectors using quantization and graph-based indexes. Spotify uses Annoy to find similar songs in milliseconds across 100M+ tracks. FAISS powers Facebook's face recognition and semantic search. The principles are identical to what you have learned — distances, neighbors, votes — but the engineering to make it fast at scale is a field of its own.

10.14 Exam Guidance Summary

Exam note: The following is based on the professor's explicit exam guidance for this lecture.

One question from proximity/similarity calculation is compulsory on the end-semester exam — expected complexity similar to the worked examples in Sections 10.4–10.8. You must be fluent with all proximity formulas for nominal, ordinal, binary (symmetric and asymmetric), numeric, and mixed-type (Gower) attributes.

KNN classification question: A query point and a small dataset will be given. You must calculate distances (using the appropriate metric based on data type), sort them, identify the $K$ nearest neighbors, and predict the class using majority voting. Questions may ask you to compare predictions for different $K$ values (e.g., $K = 3$ vs $K = 5$ vs $K = 7$ ). Practice the full distance table approach shown in Section 10.12.1.

Mixed-type proximity calculation (Gower distance): High chance of appearing. You must compute per-attribute dissimilarity matrices (using the correct formula for each attribute type) and combine them using the Gower distance formula. The worked example in Section 10.8.1 is the template.

This lecture's content is not included in the makeup exam — the makeup exam covers the same syllabus as the regular exam.

Distance metrics to know: Euclidean ( $\sum Δ^{2}$ ), Manhattan ( $\sum ∣Δ∣$ ), Minkowski (generalization with parameter $h$ ), nominal formula ( $p - m) / p$ , ordinal process (rank → normalize → numeric distance), symmetric binary ( $\frac{r + s}{q + r + s + t}$ ), asymmetric binary / Jaccard coefficient ( $\frac{r + s}{q + r + s}$ , Jaccard = $\frac{q}{q + r + s}$ ), cosine similarity ( $\frac{D _{a} \cdot D _{b}}{∥ D _{a} ∥∥ D _{b} ∥}$ ), Gower distance (weighted average of per-attribute normalized distances).

Concepts to know: Instance-based vs model-based learning, lazy vs eager learning, advantages/disadvantages of each, curse of dimensionality (what it is, why it happens, solutions), cross-validation (K-Fold procedure and its use for tuning $K$ and attribute weights), true function $F^{*}$ (how KNN approximates it vs model-based learning), tie-breaking strategies, distance-weighted KNN, data matrix vs dissimilarity matrix.

Study strategy: The worked examples in Sections 10.4 through 10.8 and 10.12.1 are directly representative of exam questions. Practice them with different numbers. For the KNN question, memorize the Euclidean distance formula and the majority voting equation. For mixed-type, memorize the Gower formula structure — per-attribute distance, indicator $δ_{ij}^{(f)}$ for missing values, weighted average.

10.15 Key Industry Applications

Application How instance-based learning is used Key technique

Recommendation systems (Amazon, Netflix, Spotify) Collaborative filtering — user-user similarity and item-item similarity Cosine similarity, Jaccard coefficient on user/item matrices

Anomaly / fraud detection Identify data points that are highly dissimilar from the majority Distance to $k$ -th nearest neighbor; points beyond threshold = anomalies

Document retrieval / search engines Cosine similarity between query and document vectors TF-IDF weighted cosine similarity on document-term matrix

GPS navigation (Google Maps) Manhattan (city block) distance for road networks $L_{1}$ norm approximates grid-based driving distances

Medical diagnosis Classify patient conditions based on similar past cases KNN on lab results + symptoms; case-based reasoning

Image recognition KNN on pixel feature vectors (historically) Euclidean distance on flattened pixel intensities

Credit scoring / loan approval Gower distance on mixed applicant data Mixed-type proximity: nominal (employment type), ordinal (credit grade), numeric (income), binary (prior default)

Legal case-based reasoning Retrieve precedent cases by fact-pattern similarity Jaccard or custom similarity on case attributes

Music recommendation (Spotify) Approximate nearest-neighbor search on audio embeddings Annoy library; cosine similarity on learned embedding vectors

Face recognition (Facebook) Billion-scale nearest-neighbor search on face embeddings FAISS library; $L_{2}$ distance on deep learning embeddings

Application	How instance-based learning is used	Key technique
Recommendation systems (Amazon, Netflix, Spotify)	Collaborative filtering — user-user similarity and item-item similarity	Cosine similarity, Jaccard coefficient on user/item matrices
Anomaly / fraud detection	Identify data points that are highly dissimilar from the majority	Distance to $k$ -th nearest neighbor; points beyond threshold = anomalies
Document retrieval / search engines	Cosine similarity between query and document vectors	TF-IDF weighted cosine similarity on document-term matrix
GPS navigation (Google Maps)	Manhattan (city block) distance for road networks	$L_{1}$ norm approximates grid-based driving distances
Medical diagnosis	Classify patient conditions based on similar past cases	KNN on lab results + symptoms; case-based reasoning
Image recognition	KNN on pixel feature vectors (historically)	Euclidean distance on flattened pixel intensities
Credit scoring / loan approval	Gower distance on mixed applicant data	Mixed-type proximity: nominal (employment type), ordinal (credit grade), numeric (income), binary (prior default)
Legal case-based reasoning	Retrieve precedent cases by fact-pattern similarity	Jaccard or custom similarity on case attributes
Music recommendation (Spotify)	Approximate nearest-neighbor search on audio embeddings	Annoy library; cosine similarity on learned embedding vectors
Face recognition (Facebook)	Billion-scale nearest-neighbor search on face embeddings	FAISS library; $L_{2}$ distance on deep learning embeddings

10.16 Named References

Iris dataset (Fisher, 1936) — Classic ML dataset with 3 flower species (Iris setosa, Iris versicolor, Iris virginica), 4 features (sepal length/width, petal length/width), 150 samples. Used throughout this lecture as the canonical KNN example.

scikit-learn (Pedregosa et al., 2011) — Python ML library. `KNeighborsClassifier` and `KNeighborsRegressor` in `sklearn.neighbors`; `StandardScaler` and `MinMaxScaler` in `sklearn.preprocessing`; `train_test_split` and `cross_val_score` in `sklearn.model_selection`.

Jaccard coefficient (Jaccard, 1901) — Also known as Jaccard similarity: $J (A, B) = ∣ A \cap B ∣/∣ A \cup B ∣$ . The standard asymmetric binary similarity measure. In binary vector form: $q / (q + r + s)$ .

Gower distance (Gower, 1971) — The standard formula for mixed-type attribute proximity. Implemented in R's `cluster::daisy()` and Python's `gower` package.

Curse of dimensionality (Bellman, 1961) — The phenomenon where distance metrics lose discriminative power as the number of dimensions increases. Originally from dynamic programming; widely cited in ML in the context of nearest-neighbor methods.

Moore and Lee (1994) — Efficient cross-validation methods for feature selection in KNN, including leave-one-out approaches that exploit KNN's zero training cost.

Voronoi diagram — The partition of space into convex polyhedra, each associated with one training point. The 1-NN decision surface is exactly the Voronoi diagram of the training set.

kd-tree (Bentley, 1975; Friedman et al., 1977) — A space-partitioning data structure for efficient nearest-neighbor search in low-to-moderate dimensions. Stored training examples at leaf nodes; query time $O (lo g n)$ in favorable cases.

Shepard's method (Shepard, 1968) — Distance-weighted KNN using all training examples (global method). The forerunner of modern kernel-based methods.

FAISS (Johnson et al., 2019) — Facebook AI Similarity Search. Library for efficient approximate nearest-neighbor search at billion scale using quantization and GPU acceleration.

Annoy (Spotify) — Approximate Nearest Neighbors Oh Yeah. Library using random projection trees for fast similarity search; used by Spotify for music recommendation.

ML Lecture 10 notes · Instance-Based Learning and K-Nearest Neighbors

Machine Learning· postgraduate· 2026-06-29

Sections Breakdown

110.1 Model-Based Learning vs Instance-Based Learning

Definition, comparison, advantages and disadvantages of eager vs lazy learning

210.2 Applications of Instance-Based Learning

Recommendation systems, anomaly detection, context-based search and document retrieval

310.3 Data Similarity and Dissimilarity — Proximity Measures

Core definitions of similarity, dissimilarity, proximity, data matrix vs dissimilarity matrix

410.4 Proximity Measures for Nominal Attributes

Simple matching approach for categorical data with formula and worked examples

510.5 Proximity Measures for Ordinal Attributes

Three-step rank-normalize-measure process for ordinal data

610.6 Proximity Measures for Binary Attributes

Symmetric binary, asymmetric binary, Jaccard coefficient with contingency tables

710.7 Proximity Measures for Numeric Attributes

Euclidean, Manhattan, Minkowski, and Supremum distance with comparison

810.8 Proximity Measures for Mixed-Type Attributes

Gower distance for mixed nominal, ordinal, binary, and numeric data

910.9 Cosine Similarity for Text and Document Retrieval

Document-term matrix, cosine similarity formula, worked search examples

1010.10 Curse of Dimensionality

Problem of distance concentration in high dimensions and solutions

1110.11 Cross-Validation (K-Fold)

K-fold cross-validation procedure for tuning KNN hyperparameters

1210.12 K-Nearest Neighbors (KNN) Algorithm

KNN classification and regression, true function F*, distance-weighted voting

1310.13 Implementation Notes

Python scikit-learn implementation and practical considerations

14Exam Guidance Summary

Professor's exam strategy and key topics to study

15Key Industry Applications

Real-world applications of instance-based learning across industries

16Named References

References to key papers, libraries, and historical works

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.

Model-Based vs Instance-Based Learning

Must-know: Instance-based (lazy) learning stores all training data and postpones generalization until query time; model-based (eager) learning builds a global model upfront and discards the data. Key tradeoff: training cost vs prediction cost and ability to capture complex local patterns.

$Store (X, Y) \Rightarrow When x_{new} arrives, find similar stored x_{i} and use their y_{i}$

⚠️ Top pitfall: Thinking 'lazy means simple' — lazy learning shifts all computation to prediction time, making it computationally heavy at inference.

Self-check: If you add 50 new training examples to a KNN model, what changes structurally?

Connects to: Instance-Based Learning, K-Nearest Neighbors

Proximity Measures for Nominal Attributes

Must-know: Dissimilarity for nominal data = fraction of attributes where two objects disagree: d = (p-m)/p. Simple, bounded [0,1], assumes all mismatches are equally important.

$d (i, j) = \frac{p - m}{p}$

⚠️ Top pitfall: Encoding nominal values as integers (R=1, B=2, G=3) and applying Euclidean distance — this implies an artificial ordering and unequal gaps.

Self-check: Objects A and B have 3 nominal attributes. They match on 1 attribute. What is d(A, B)?

Connects to: Proximity Measures, Gower Distance

Proximity Measures for Ordinal Attributes

Must-know: Three-step pipeline: assign ranks (1 to M), normalize to [0,1] via (r-1)/(M-1), then apply any numeric distance formula. Assumes equal spacing between ranks.

$normalized rank_{i f} = \frac{r _{i f} - 1}{M _{f} - 1}$

⚠️ Top pitfall: Forgetting to normalize before computing Euclidean distance — raw ranks produce scale-dependent distances.

Self-check: A survey uses 5-point Likert scale: strongly disagree to strongly agree. What are the normalized ranks?

Connects to: Proximity Measures, Gower Distance

Proximity Measures for Binary Attributes

Must-know: Symmetric (both 0 and 1 matter): d = (r+s)/(q+r+s+t). Asymmetric (only 1 matters, ignore t): d = (r+s)/(q+r+s). Jaccard similarity = q/(q+r+s). Use asymmetric for sparse data like market baskets.

$d_{symmetric} = \frac{r + s}{p}, d_{asymmetric} = \frac{r + s}{q + r + s}, Jaccard = \frac{q}{q + r + s}$

⚠️ Top pitfall: Treating asymmetric as symmetric — in a dataset of 10,000 products with average basket of 5 items, symmetric distance makes all customers appear ~99.95% similar.

Self-check: Two patients share 2 positive test results. Both are negative on 5 tests. Patient A has 1 positive test that B lacks. What is their Jaccard similarity?

Connects to: Proximity Measures, Cosine Similarity

Proximity Measures for Numeric Attributes

Must-know: Euclidean (L2): straight-line distance, sqrt of squared diffs. Manhattan (L1): sum of absolute diffs, more robust in high dimensions. Minkowski generalizes both with parameter h. Supremum (L∞): max absolute diff. Always normalize first.

$d_{Euclid} = \sum (x_{ik} - x_{j k})^{2}, d_{Manh} = \sum ∣ x_{ik} - x_{j k} ∣, d_{Mink} = (\sum ∣ x_{ik} - x_{j k} ∣^{h})^{1/ h}$

⚠️ Top pitfall: Not normalizing features before computing distance — a feature with range 0-100,000 dominates Euclidean distance over a feature with range 0-1.

Self-check: Points A=(1,2) and B=(3,5). Compute Euclidean, Manhattan, and Supremum distances.

Connects to: Proximity Measures, Curse of Dimensionality

Gower Distance for Mixed-Type Attributes

Must-know: Gower distance computes per-attribute dissimilarity using each attribute's native formula (normalized to [0,1]), then takes a weighted average, excluding missing values. Universal for mixed data.

$d (i, j) = \frac{\sum _{f = 1}^{p} δ _{ij}^{(f)} \cdot d _{ij}^{(f)}}{\sum _{f = 1}^{p} δ _{ij}^{(f)}}$

⚠️ Top pitfall: Forgetting to normalize numeric attributes to [0,1] before plugging into Gower — numeric contributions can swamp nominal/ordinal ones.

Self-check: Three attributes: color (nominal), quality (ordinal), quantity (numeric). How do you compute d for each type before combining via Gower?

Connects to: Proximity Measures, Mixed-Type Attributes

Cosine Similarity for Document Retrieval

Must-know: Cosine similarity measures the angle between document vectors: dot product divided by product of magnitudes. Length-independent, range [0,1] for non-negative term frequencies.

$cosine sim (D_{a}, D_{b}) = \frac{D _{a} \cdot D _{b}}{∥ D _{a} ∥ \cdot ∥ D _{b} ∥}$

⚠️ Top pitfall: Using Euclidean distance on raw term frequencies — long documents seem far from everything. Always use cosine for text.

Self-check: Document vectors D1=(5,0,3,2) and D2=(3,0,2,0). Compute their cosine similarity.

Connects to: Document-Term Matrix, TF-IDF

Curse of Dimensionality

Must-know: As dimensions increase, pairwise distances converge to similar values — nearest and farthest neighbors become almost equally far, breaking KNN's fundamental assumption. Solutions: attribute weighting, feature selection, dimensionality reduction, or Manhattan distance.

$r = \frac{distance to nearest neighbor}{distance to farthest neighbor} \to 1 as d \to \infty$

⚠️ Top pitfall: Thinking 'more features = better model.' Every irrelevant feature dilutes distance signal. Normalization does not fix the curse — weighting or eliminating features is the only cure.

Self-check: Why does the ratio of nearest-to-farthest neighbor distance approach 1 in high dimensions?

Connects to: Dimensionality Reduction, Feature Selection

K-Fold Cross-Validation

Must-know: Split data into K folds, train on K-1, test on the held-out fold, repeat K times, average scores. For KNN, CV is computationally cheap because 'training' is just storing data. Used to tune K and distance metric.

$CV accuracy = \frac{1}{K} i = 1 \sum K accuracy_{i}$

⚠️ Top pitfall: Data leakage: normalizing on full dataset before splitting — test fold information leaks into training folds. Always fit scaler on training folds only.

Self-check: With N=100 samples and K=5 folds, what is the train/test size per iteration?

Connects to: Hyperparameter Tuning, Model Evaluation

K-Nearest Neighbors Algorithm

Must-know: KNN is the canonical lazy learner: store all training data, compute distances from query to all stored points, pick K nearest, majority vote (classification) or average (regression). Key hyperparameters: K (odd to avoid ties), distance metric, weighting scheme.

$y^(x_{q}) = ar g v \in V max i = 1 \sum K δ (v, y_{(i)}), y^(x_{q}) = \frac{1}{K} i = 1 \sum K y_{(i)}$

⚠️ Top pitfall: Choosing K without cross-validation. Small K = high variance, sensitive to noise. Large K = high bias, may miss local structure. Always cross-validate.

Self-check: A query point has 8 neighbors sorted by distance. Classes: X4(−), X3(+), X7(−), X5(+), X2(+), X6(+), X1(−), X8(−). Predict for K=3 and K=5.

Connects to: Instance-Based Learning, Cross-Validation

True Function F*

Must-know: F* is the real, unknown underlying mapping that generates the data. KNN approximates F* locally by averaging nearby observed values. Model-based learning tries to discover a global approximation. Neither ever sees F* directly.

$F^{*} (x_{q}) \approx \frac{1}{K} i = 1 \sum K y_{(i)} (KNN approximation of true function)$

⚠️ Top pitfall: Confusing KNN regression output with confidence — the average of neighbor values is a point estimate, not a confidence interval.

Self-check: True function F*(x) = x². Training: (1,1), (2,4), (3,9). Query: x=2.5. What does KNN (K=3) predict vs the true value?

Connects to: K-Nearest Neighbors, Bias-Variance Tradeoff

Previous LectureLecture 09 · Decision Trees — Overfitting, Pruning, and MDL
Next LectureLecture 11 · Instance-Based Learning — Distance-Weighted KNN, Locally Weighted Regression, and Bayesian Learning Foundations

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

Instance-Based Learning and K-Nearest Neighbors

10.1 Model-Based Learning vs Instance-Based Learning

10.1.1 Definition and Explanation

10.1.2 Advantages and Disadvantages

10.2 Applications of Instance-Based Learning

10.2.1 Recommendation Systems — Collaborative Filtering

10.2.2 Anomaly Detection

10.2.3 Context-Based Search / Document Retrieval

10.3 Data Similarity and Dissimilarity — Proximity Measures

10.3.1 Core Definitions

10.3.2 Data Matrix vs Dissimilarity Matrix

10.4 Proximity Measures for Nominal (Categorical) Attributes

10.4.1 Formula and Worked Examples

10.5 Proximity Measures for Ordinal Attributes

10.5.1 Three-Step Process

10.6 Proximity Measures for Binary Attributes

10.6.1 The Contingency Table

10.6.2 Symmetric Binary Attributes

10.6.3 Asymmetric Binary Attributes and the Jaccard Coefficient

10.7 Proximity Measures for Numeric Attributes

10.7.1 Euclidean Distance

10.7.2 Manhattan Distance

10.7.3 Minkowski Distance

10.7.4 Supremum Distance

10.8 Proximity Measures for Mixed-Type Attributes

10.8.1 Gower Distance

10.9 Cosine Similarity for Text and Document Retrieval

10.9.1 Document-Term Matrix

10.9.2 Cosine Similarity Formula

10.10 Curse of Dimensionality

10.10.1 The Problem

10.10.2 Solutions

10.11 Cross-Validation (K-Fold)

10.11.1 Concept and Purpose

10.11.2 K-Fold Cross-Validation Procedure

10.12 K-Nearest Neighbors (KNN) Algorithm

10.12.1 KNN Classification

10.12.2 KNN Regression

10.12.3 True Function F∗

10.13 Implementation Notes

10.13.1 Python Implementation of KNN

10.13.2 Practical Considerations

10.14 Exam Guidance Summary

10.15 Key Industry Applications

10.16 Named References

ML Lecture 10 notes · Instance-Based Learning and K-Nearest Neighbors

Sections Breakdown

Exam Revision Notes

Model-Based vs Instance-Based Learning

Proximity Measures for Nominal Attributes

Proximity Measures for Ordinal Attributes

Proximity Measures for Binary Attributes

Proximity Measures for Numeric Attributes

Gower Distance for Mixed-Type Attributes

Cosine Similarity for Document Retrieval

Curse of Dimensionality

K-Fold Cross-Validation

K-Nearest Neighbors Algorithm

True Function F*

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat

10.12.3 True Function $F^{*}$