Machine Learning

kNN and Nearest-Neighbor Geometry

kNN turns a metric into a local vote or average: change K or the distance, and the neighborhood itself changes.

status: reviewimportance: importantdifficulty 3/5math: graduateread: 21mlive demo

Back to Machine Learning Next: Model Selection and Hyperparameter Search

Concept Structure

kNN and Nearest-Neighbor Geometry

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

2prerequisites

3next concepts

4related links

Learner Contract

What this page should let you do.

You are here becausekNN turns a metric into a local vote or average: change K or the distance, and the neighborhood itself changes.

This Machine Learning concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

Before thisNorms, Inner Products, and Induced Matrix Norms (review)

2 prerequisites listed; refresh them before leaning on the math or code.

Norms, Inner Products, and Induced Matrix Norms (review)Train/Dev/Test Splits, Cross-Validation, and Leakage

By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Then go nextModel Selection and Hyperparameter Search

Follow this edge after making one prediction here; the next page should reuse the result, not restart the route.

Test the linkManipulate one control and predict the visible change.Then continue to Model Selection and Hyperparameter Search

Claim/source review status

Substantive review recorded

1/1 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.

Claims1/1 reviewed

Sources5 cited

Codeattached

Demolive

Reviewed2026-07-02

Updatedpage 2026-07-02

Learning item flow

4/4 sections readyAsk about this Research room

ConceptkNN and Nearest-Neighbor GeometryMachine Learning EquationkNN and Nearest-Neighbor Geometry equation 1Exact equation CodekNN and Nearest-Neighbor Geometry runnable code 1Exact runnable code DemokNN and Nearest-Neighbor Geometry interactive demoInteractive demo ClaimkNN predicts a point from the labels or values of the K closest train...Exact claim check SourceCS231n: Image Classification, Data-driven Approach, k-Nearest NeighborExact source

ConceptkNN and Nearest-Neighbor GeometryMachine Learning

5 sources attachedLocal snapshot ready

concept:machine-learning/knn-nearest-neighbor-geometry

Codenearby Predictbefore reveal Roomitem handoff

01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

k-nearest neighbors is easy to underestimate because the rule is so short:

find the nearby examples, then let them vote.

But the word nearby carries almost the whole model. A point is not close in the abstract. It is close under a distance rule, after a representation and scaling choice have already decided which differences count.

If two houses differ by 1 bedroom and 1 mile from downtown, should those differences matter equally? If two images are close in raw pixels but one is shifted a few pixels to the right, are they visually close? If two documents share terms but disagree in embedding space, which geometry should retrieval trust?

kNN makes these questions visible. It stores the training examples. For a new point $x_\star$ , it measures distances from $x_\star$ to each training input, takes the $K$ smallest, and predicts from their labels or responses.

Small $K$ is very local. It can trace a jagged decision boundary and react strongly to noise. Large $K$ smooths the boundary, but it may average across regions that should stay separate. The metric matters too: Euclidean distance draws circular neighborhoods in two dimensions, Manhattan distance draws diamonds, and Chebyshev distance draws squares. Those shapes can include different neighbors even when the training set and probe point do not move.

The highest-level lesson is:

kNN is not just a simple classifier. It is a microscope for the geometry your representation has chosen.

That is why nearest-neighbor ideas keep reappearing in modern AI: retrieval, memory, embedding search, deduplication, clustering diagnostics, and exemplar-based evaluation all depend on some answer to “what counts as near?” The baseline is simple; the modeling judgment is not.

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt

Equation 1 $\mathcal D=\{(x_i,y_i)\}_{i=1}^n,$ Equation 2 $d:\mathbb R^d\times\mathbb R^d\to\mathbb R_{\ge 0}.$

Let the training set be

\mathcal D=\{(x_i,y_i)\}_{i=1}^n,

where each input vector $x_i\in\mathbb R^d$ and each label $y_i$ is either a class label for classification or a real-valued response for regression.

Choose a distance function

d:\mathbb R^d\times\mathbb R^d\to\mathbb R_{\ge 0}.

For a query point $x_\star$ , define $\mathcal N_K(x_\star)$ as the indices of the $K$ training examples with the smallest distances $d(x_i,x_\star)$ .

For classification, kNN estimates the local class proportion by

\widehat p(c\mid x_\star) = \frac{1}{K}\sum_{i\in\mathcal N_K(x_\star)} \mathbf 1[y_i=c],

then predicts the class with the largest local proportion:

\widehat y(x_\star)=\arg\max_c \widehat p(c\mid x_\star).

For regression, the simplest kNN predictor averages the nearby responses:

\widehat f(x_\star) = \frac{1}{K}\sum_{i\in\mathcal N_K(x_\star)} y_i.

The metric determines the neighbor set. Common choices include

d_2(x,z)=\left(\sum_{j=1}^d (x_j-z_j)^2\right)^{1/2},

d_1(x,z)=\sum_{j=1}^d |x_j-z_j|,

and

d_\infty(x,z)=\max_{1\le j\le d}|x_j-z_j|.

These are all valid metrics, but they carve different neighborhoods. In two dimensions, $d_2$ gives circles, $d_1$ gives diamonds, and $d_\infty$ gives axis-aligned squares. If the data coordinates are rescaled, these shapes stretch; if the representation changes, the entire neighbor ranking can change.

The choice of $K$ is a model-selection problem. When $K=1$ , the training prediction can be extremely flexible because every training point can classify itself. As $K$ grows, the predictor averages over a larger region. That usually reduces variance but can increase bias.

High dimensions add another warning. A local neighborhood needs volume. For an interior point in a unit $d$ -cube, an $L_\infty$ cube of radius $r$ has volume fraction

q=(2r)^d.

Solving for $r$ gives

r=\frac{1}{2}q^{1/d}.

For a fixed fraction $q$ , the required radius approaches half the side length as $d$ increases. This simple cube calculation is not a full theorem about all data distributions, but it shows the geometric pressure: in high dimensions, “nearby” can become much less local unless the representation concentrates the relevant signal.

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt

Runnable code 1import numpy as np X = np.array([ [0.66, 0.66], [0.34, 0.66], [0.64, 0.35], [0.78, 0.50], [0....python

import numpy as np

X = np.array([
    [0.66, 0.66], [0.34, 0.66], [0.64, 0.35],
    [0.78, 0.50], [0.50, 0.77], [0.23, 0.51],
    [0.18, 0.22], [0.82, 0.84], [0.36, 0.20],
    [0.68, 0.22],
])
y = np.array(["teal", "teal", "teal", "coral", "coral",
              "coral", "teal", "coral", "teal", "coral"])
x_star = np.array([0.50, 0.50])

def distances(X, x, metric):
    delta = np.abs(X - x)
    if metric == "l1":
        return delta.sum(axis=1)
    if metric == "linf":
        return delta.max(axis=1)
    return np.sqrt((delta ** 2).sum(axis=1))

def knn_predict(metric="l2", k=5):
    dist = distances(X, x_star, metric)
    order = np.lexsort((np.arange(len(dist)), dist))[:k]
    labels, counts = np.unique(y[order], return_counts=True)
    winner = labels[np.argmax(counts)]
    return winner, list(zip(order.tolist(), y[order], np.round(dist[order], 3)))

for metric in ["l2", "l1", "linf"]:
    print(metric, knn_predict(metric, k=5))

The same points give different neighbor sets when the metric changes. That is the point: a nearest-neighbor model inherits the geometry of its distance function.

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

Use the lab to predict what kNN will trust before you see the vote ledger. Change $K$ and the metric, commit to the governing rule, then reveal the neighbor set, local vote, metric lens, and decision-region tint. The high-dimensional strip is separate: it shows why local methods need representation discipline before distance becomes meaningful.

Live Concept Demo

Explore kNN and Nearest-Neighbor Geometry

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 3/5graduatecode-aligned

Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what kNN and Nearest-Neighbor Geometry should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

kNN turns a metric into a local vote or average: change K or the distance, and the neighborhood itself changes.

Prediction open01 / Intuition

Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change kNN and Nearest-Neighbor Geometry should make visible.

Visual Inquiry

Make the image answer a mathematical question

kNN turns a metric into a local vote or average: change K or the distance, and the neighborhood itself changes.

4/4 stages readyLive demo connected

Visual cueWhich visible object should carry the first intuition?

Inspection depth2/4

Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make kNN and Nearest-Neighbor Geometry easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

course-notes · 2026CS231n: Image Classification, Data-driven Approach, k-Nearest NeighborStanford CS231n

Supports the data-driven nearest-neighbor classifier, distance functions such as L1, k as a hyperparameter, and validation-set selection of k and distance choices.

Open source

book · 2023An Introduction to Statistical Learning, Chapters 2-4James, Witten, Hastie, Tibshirani, and Taylor

Supports KNN classification as voting among the K closest training points, KNN regression as averaging nearby responses, K's effect on boundary flexibility, and validation pressure from the bias-variance tradeoff.

Open source

book · 2009The Elements of Statistical Learning, Chapters 2 and 13Hastie, Tibshirani, and Friedman

Supports nearest-neighbor methods as local learning, their connection to local averaging, and the warning that local methods become fragile in high-dimensional spaces.

Open source

book · 2020Mathematics for Machine Learning, Chapter 3Deisenroth, Faisal, and Ong

Supports norms, inner-product-induced distances, Euclidean distance, metric axioms, and the fact that distance changes when the underlying norm or inner product changes.

Open source

paper · 1967Nearest Neighbor Pattern ClassificationCover and Hart

Canonical nearest-neighbor classification paper; used here only for historical positioning, not for asymptotic risk claims in the toy demo.

Open source

Claim Review

kNN turns a metric into a local vote or average: change K or the distance, and the neighborhood itself changes.

Status1 substantive review recorded

Claims without a substantive review badge still need exact source-support review.

Sources5 references

cs231n-nearest-neighbor-classifier, james-2023-islr-knn, hastie-2009-esl-nearest-neighbors, deisenroth-2020-mml-metrics, cover-hart-1967-nearest-neighbor

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewedkNN predicts a point from the labels or values of the K closest training examples under a chosen distance; K controls locality/flexibility, the metric controls neighborhood shape, and high-dimensional distance geometry can make naive nearest-neighbor locality unreliable.Claim metadata: source checked

The page's central contract is supported across the sources: choose a metric, sort training examples by distance, vote or average the K nearest responses, tune K/metric with held-out evidence, and treat high-dimensional nearest neighbors as representation-sensitive rather than automatically local.

Sources: CS231n: Image Classification, Data-driven Approach, k-Nearest Neighbor, An Introduction to Statistical Learning, Chapters 2-4, The Elements of Statistical Learning, Chapters 2 and 13, Mathematics for Machine Learning, Chapter 3, Nearest Neighbor Pattern ClassificationThe lab is a 2D exact-distance classifier; it omits indexing/ANN, learned metrics, weighting, calibration, imbalance handling, regression uncertainty, and full high-dimensional proofs.A bounded review summary is present; still check caveats and exact reference scope.

Checked Stanford CS231n, ISLR, ESL, and MML for nearest-neighbor voting/averaging, L1/L2-style metric choices, validation-tuned K, K's bias-variance/flexibility effect, metric-dependent distance geometry, and high-dimensional local-method cautions. GPT Pro remains pending because 127.0.0.1:51672 was unavailable.

Reviewer: codex-local-source-review; reviewed 2026-07-02

source-span-cs231n-nearest-neighbor-classifier source-span-james-2023-islr-knn source-span-hastie-2009-esl-nearest-neighbors source-span-deisenroth-2020-mml-metrics Equation 1 Equation 2 Runnable code 1 Interactive demo

Source support candidates

course-notes 2026CS231n: Image Classification, Data-driven Approach, k-Nearest Neighbor

Supports the data-driven nearest-neighbor classifier, distance functions such as L1, k as a hyperparameter, and validation-set selection of k and distance choices.

book 2023An Introduction to Statistical Learning, Chapters 2-4

book 2009The Elements of Statistical Learning, Chapters 2 and 13

Supports nearest-neighbor methods as local learning, their connection to local averaging, and the warning that local methods become fragile in high-dimensional spaces.

book 2020Mathematics for Machine Learning, Chapter 3

Supports norms, inner-product-induced distances, Euclidean distance, metric axioms, and the fact that distance changes when the underlying norm or inner product changes.

Mechanism checks

Equation 1

\mathcal D=\{(x_i,y_i)\}_{i=1}^n,

Equation 2

d:\mathbb R^d\times\mathbb R^d\to\mathbb R_{\ge 0}.

Runnable code 1import numpy as np X = np.array([ [0.66, 0.66], [0.34, 0.66], [0.64, 0.35], [0.78, 0.50], [0....Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

kNN turns a metric into a local vote or average: change K or the distance, and the neighborhood itself changes.

Readiness0/3 checks ready

Predict

Before touching the demo, predict one visible change that should happen in kNN and Nearest-Neighbor Geometry.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Your answer canvas

Local checks

Claim

A concrete answer is on the canvas.

Mechanism

The answer names why the claim should hold.

Bridge

It touches the page context or a neighboring idea.

Misconception check

Grounded research drawerClose

ConceptkNN and Nearest-Neighbor GeometryMachine Learning

Runnable code comparisonkNN and Nearest-Neighbor Geometry runnable code 1X = np.array([Prediction before revealkNN and Nearest-Neighbor Geometry interactive demoManipulate one control and predict the visible change.

Grounded room questionWhat is the smallest example that makes kNN and Nearest-Neighbor Geometry click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.

Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptMachine Learning

kNN and Nearest-Neighbor Geometry

Attached question

What is the smallest example that makes kNN and Nearest-Neighbor Geometry click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action

Local action draft

This draft stays in this browser, attached to the selected learning item.

Draft noteNext action

No local draft saved.

Evidence to inspect

References to inspect: attached references on this page.
Definition, prerequisite, and contrast concept links
The equation or runnable code that makes the concept operational
One demo state that shows the invariant instead of a slogan

What would resolve this

The learner can state the mechanism in their own words
The learner can name the prerequisite that would repair confusion
The learner can predict how the mechanism changes under one perturbation

Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - kNN and Nearest-Neighbor Geometry Selected item key: recorded for copy. Context: Machine Learning Page anchor: recorded for copy. Open question: What is the smallest example that makes kNN and Nearest-Neighbor Geometry click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context

concept/concept-notebook/machine-learning/knn-nearest-neighbor-geometry
concept:machine-learning/knn-nearest-neighbor-geometry

Learning Map

Before / Now / Try / Next

BeforeNorms, Inner Products, and Induced Matrix Norms (review)

NowIntuition -> Math -> Code -> Demo

TryManipulate one control and predict the visible change.

NextModel Selection and Hyperparameter Search

Intuitionready
Mathready
Codeready
Interactive Demoready

AI Companion

Ask beside the selected object

kNN turns a metric into a local vote or average: change K or the distance, and the neighborhood itself changes.

Your question

GoalComfortStyleStuck on

Context prompt

You are my AI learning companion for Continuous Function. Current context: Machine Learning concept. Learning surface: kNN and Nearest-Neighbor Geometry. What this page says: kNN turns a metric into a local vote or average: change K or the distance, and the neighborhood itself changes. Current section: Intuition, math, code, and interactive demo. Suggested next step: Manipulate one control and predict the visible change.. Learner goal: Understand the idea. Learner comfort level: New to this. Preferred explanation style: Visual first. Task: Explain the central idea in plain language, then restate it with the exact math objects from the page. Answer in a way that helps me learn: ask one clarifying question only if needed, use intuition before notation, and end with one thing I should try on the page.

Domain

Machine Learning

machine-learningnearest-neighborsnonparametric-learningmetricsgeometryretrieval

Prerequisites

Norms, Inner Products, and Induced Matrix Norms (review)Train/Dev/Test Splits, Cross-Validation, and Leakage

Leads To

Model Selection and Hyperparameter Search PCA as Optimization and Eigenspace Projection RAG Retrieval Fundamentals: BM25, Dense Retrieval, Reranking, Chunking, and Evaluation (review)

Classification Metrics, Thresholds, and Calibration Bias-Variance Decomposition Linear Regression & Least Squares Logistic Regression

Within this domain