Move the question, watch the evidence change

Nearby examples become the rule

At the original query, the nearest observation belongs to B. With three neighbors, two of the selected observations belong to A, so the classification changes to A. The numerical regression output uses their targets instead of their categories. Neither output requires an affine weight or bias.

This is instance-based learning. Training stores a feature representation and its observed outcomes. Inference compares a new query with the stored inputs, selects a neighborhood and aggregates its outcomes. This does not mean there are no modeling choices: the feature representation, metric, scales, neighbor count and tie policy all influence the returned rule.

In a real task, each feature must be information available at prediction time. A target cannot quietly become a coordinate merely because that would make the nearest neighbor easy to identify. A point’s category and numerical target are separate outcomes in this toy sheet.

Define a neighborhood precisely

For observations $x_i\in\mathbb R^d$ and query $q\in\mathbb R^d$, let $d(q,x_i)$ be a chosen feature distance. The experiment initially uses the scaled Euclidean distance

$d_2(q,x_i)=\left(\sum_{j=1}^d \left|\frac{q_j-x_{ij}}{s_j}\right|^2\right)^{1/2}, \qquad s_j>0.$

A reference scale $s_j$ states how much a coordinate difference should count. Here both feature axes are dimensionless toy coordinates, initially with unit reference scales. Changing a scale changes the neighborhood; it is a model choice, not a harmless change to the drawing.

Sort all stored rows by increasing distance. For equal computed distances, sort by the stable sample ID using the declared UTF-16 code-unit order. Define $N_k(q)$ as the first $k$ rows of that ordering. The unweighted classification rule is

$\hat c(q)=\operatorname*{arg\,max}_{c\in\{A,B\}} \sum_{i\in N_k(q)}\mathbf 1[c_i=c].$

The sheet chooses A on an exact vote-count tie. That convention produces a reproducible decision; it does not supply additional evidence for A. A different application could abstain or use another declared rule.

For numerical outcomes, the regression rule is

$\hat y(q)=\frac1k\sum_{i\in N_k(q)}y_i.$

This average minimizes the sum of squared deviations from the selected targets: differentiating $\sum_{i\in N_k}(a-y_i)^2$ gives $2ka-2\sum_i y_i=0$. Classification votes and this regression mean answer different questions even though they share the same feature neighborhood.

The individual feature vectors are $2\times1$ columns. The batch $X$ stores six sample rows, so it is $6\times2$; the query is $2\times1$, and distances and numerical targets are $6\times1$. Categories A/B are labels, not numerical values to average.

Work through the original query

These six observations are hand-authored synthetic examples, not measured data. The targets are arbitrary numerical quantities.

At $q=(0,0)$ with unit scales, the complete order is s4 at distance $1$; s2, s3 and s5 at $\sqrt2$; s1 at $2$; and s6 at $\sqrt5$. For $k=3$, ID order selects s2 and s3 from the tied group alongside s4. The votes are A:2, B:1, while

$\hat y=\frac{8+4+6}{3}=6.$

Move the query to $(1.5,0)$. The first row is s4 at $0.5$. Rows s5 and s6 both have distance $\sqrt{1.25}$, so the selected set is s4, s5, s6. All vote B, and the regression output is $(8+10+12)/3=10$.

With $k=1$, the original query chooses B and target 8. With $k=6$, votes tie three to three, the declared classifier chooses A, and the average is $42/6=7$. These changes illustrate a modeling tradeoff rather than proof that any one k is best.

Duplicate geometry is not duplicate identity

Load Conflicting duplicates. Rows s4 and s7 occupy $(1,0)$ but have different categories and targets. At the coincident query with $k=2$, both have distance zero. They remain separate observations: votes tie, the declared choice is A, and the mean is $(8+0)/2=4$.

For $k=1$, the ID tie rule selects s4. Removing s7 would change the dataset and its predictions. Whether coincident rows are genuine repeated measurements or accidental data duplication is a provenance question that a geometric algorithm cannot answer.

Execute the actual reference

Run .venv/bin/python -B code/python/p03/nearest_neighbors.py from the book root. It emits the original prediction, the rightward query result and a complete query-path trace. The NumPy target column supplies the unweighted average; sorting and voting are explicit.

"""From-scratch k-NN: exact identities, distances, votes and unweighted average."""
import copy
import json
import numpy as np
from common import distance, id_key, number, power_for

CANONICAL = {
    "samples":[
        {"id":"s1","x":-2,"y":0,"category":"A","target":2},
        {"id":"s2","x":-1,"y":1,"category":"A","target":4},
        {"id":"s3","x":-1,"y":-1,"category":"A","target":6},
        {"id":"s4","x":1,"y":0,"category":"B","target":8},
        {"id":"s5","x":1,"y":1,"category":"B","target":10},
        {"id":"s6","x":2,"y":-1,"category":"B","target":12},
    ],
    "query":{"x":0,"y":0},"k":3,"metric":"L2","p":2,"scales":[1,1],
    "provenance":"Hand-authored six-row toy dataset",
}

def derive(state):
    state = copy.deepcopy(state)
    state["query"] = {key:number(state["query"][key],"Query coordinate") for key in ("x","y")}
    samples = state["samples"]
    if not isinstance(samples, list) or not 1 <= len(samples) <= 32:
        raise ValueError("Neighbors require 1 to 32 observations.")
    k = int(number(state["k"], "k", 1, 64, True))
    power_for(state["metric"], state["p"])
    if not isinstance(state["provenance"], str):
        raise ValueError("Provenance must be text.")
    ids, rows = set(), []
    for index,row in enumerate(samples):
        if not isinstance(row,dict) or not all(key in row for key in ("id","x","y","category","target")):
            raise ValueError(f"Observation at index {index} must be a sample record with id, x, y, category and target.")
        ident = row["id"]
        if not isinstance(ident, str) or not ident.strip() or ident in ids:
            raise ValueError("Sample IDs must be unique nonempty strings.")
        ids.add(ident)
        if row["category"] not in ("A", "B"):
            raise ValueError("A sample category must be A or B.")
        for key in ("x","y","target"):
            row[key] = number(row[key], "Sample "+key)
        d = distance([row["x"],row["y"]],[state["query"]["x"],state["query"]["y"]],state["metric"],state["p"],state["scales"])
        rows.append(dict(row, distance=d))
    rows.sort(key=lambda row:(row["distance"],id_key(row["id"])))
    reason = "k exceeds the number of observations; no neighbor prediction is defined." if k > len(rows) else None
    rows = [dict(row,rank=j+1,selected=reason is None and j < k) for j,row in enumerate(rows)]
    selected = [row for row in rows if row["selected"]]
    votes = [{"category":c,"count":sum(row["category"] == c for row in selected)} for c in ("A","B")]
    values = np.asarray([row["target"] for row in selected],dtype=np.float64).reshape(-1,1)
    largest = float(np.max(np.abs(values))) if len(values) else 0
    mean = None if reason else 0.0 if largest == 0 else float(number(largest*float(np.mean(values/largest)),"Regression average"))
    return {"state":copy.deepcopy(state),"rows":rows,"selectedIds":[row["id"] for row in selected],"votes":votes,
            "classification":None if reason else "A" if votes[0]["count"] >= votes[1]["count"] else "B",
            "regression":mean,"reason":reason,"voteTie":reason is None and votes[0]["count"] == votes[1]["count"],
            "boundaryTie":reason is None and k < len(rows) and rows[k-1]["distance"] == rows[k]["distance"],
            "duplicateIds":[row["id"] for row in rows if any(other["id"] != row["id"] and other["x"] == row["x"] and other["y"] == row["y"] for other in rows)],
            "shapes":{"X":[len(rows),2],"query":[2,1],"distances":[len(rows),1],"targets":[len(rows),1]}}

def trace(state):
    states = [copy.deepcopy(state)] + [dict(copy.deepcopy(state),query={"x":x,"y":0}) for x in (-1.5,0,1.5)]
    return [{"index":j,"state":value,"derived":derive(value)} for j,value in enumerate(states)]

if __name__ == "__main__":
    after = dict(copy.deepcopy(CANONICAL),query={"x":1.5,"y":0})
    print(json.dumps({"before":derive(CANONICAL),"after":derive(after),"trace":trace(CANONICAL)},allow_nan=False))

"""Part III boundary checks. Numbers are quantities, never bools or numeric strings."""
import math
import numpy as np

def number(value, name, lower=None, upper=None, integer=False):
    try:
        valid = isinstance(value, (int, float)) and not isinstance(value, bool) and math.isfinite(float(value))
    except (OverflowError, TypeError):
        valid = False
    normalized = float(value) if valid else 0
    if not valid or (lower is not None and normalized < lower) or (upper is not None and normalized > upper) or (integer and normalized != math.floor(normalized)):
        raise ValueError(f"{name} must be a finite {'integer' if integer else 'number'} in its supported range.")
    return int(normalized) if integer else normalized

def power_for(metric, p):
    number(p, "Minkowski power", 1, 8)
    if metric not in ("L1", "L2", "Lp"):
        raise ValueError("Choose L1, L2 or Lp.")
    return 1 if metric == "L1" else 2 if metric == "L2" else p

_UNIT_SCALES = object()

def distance(a, b, metric="L2", p=2, scales=_UNIT_SCALES):
    """Column-vector norm; rescale before powers. Scales carry the feature units."""
    if not isinstance(a, (list, tuple)) or not isinstance(b, (list, tuple)) or not 1 <= len(a) <= 32 or len(a) != len(b):
        raise ValueError("Distance needs matching vectors of 1 to 32 components.")
    if scales is not _UNIT_SCALES and (not isinstance(scales, (list, tuple)) or len(scales) != len(a)):
        raise ValueError("Distance needs a matching scale vector.")
    q = power_for(metric, p)
    differences = []
    for j, (left, right) in enumerate(zip(a, b)):
        left = number(left, "First component"); right = number(right, "Second component")
        scale = 1 if scales is _UNIT_SCALES else number(scales[j], "Scale")
        if scale <= 0:
            raise ValueError("Scales must be positive.")
        delta = number(left-right, "Coordinate difference")
        differences.append(number(abs(delta)/scale, "Scaled difference"))
    column = np.asarray(differences, dtype=np.float64).reshape(-1, 1)
    largest = float(np.max(column))
    if largest == 0:
        return 0.0
    result = largest * float(np.sum((column/largest)**q))**(1/q)
    return float(number(result, "Distance arithmetic"))

def id_key(value):
    return value.encode("utf-16-be", errors="surrogatepass")

def lcg(seed):
    number(seed, "Seed", 0, 2**32-1, True)
    state = int(seed)
    while True:
        state = (1664525*state+1013904223) % 2**32
        yield state/2**32

The norm rescales before powers to avoid overflow from squaring a large but representable coordinate. All accepted numerical quantities are binary64 in both runtimes. Integer spellings beyond exact binary64 integer precision therefore enter the same representation before subtraction or duplicate comparison.

Committed expectations come from high-precision norm arithmetic and exhaustive enumeration of small neighbor subsets, with exact target averaging. Agreement between Python and the browser is checked against that independent result.

Explore a discontinuous decision

Move the query slowly across a neighbor boundary. Distances vary continuously, but a selected row can change abruptly. Classification can jump when a vote changes, and unweighted regression can jump when a different target enters the average.

The dashed contour illustrates the kth distance; a polygonal drawing is a projection of the numeric metric. The ordered table determines the actual selected set. Squares, triangles, labels, filling and dotted links retain meaning without color.

Try L1 and Lp and then change one feature reference scale. The next chapter explains why raw units can dominate a distance. Choose k and preprocessing using an appropriate validation design; k=1 can memorize noisy observations, while a large neighborhood can erase useful local structure.

Replay retains the current observations, metric, scales and k. Every frame changes the controls, diagram, table, votes and equation together. Editing starts from the selected frame and ends replay. Reset returns the original six-row state.

Numerical limits and failure cases

The API accepts 1–32 rows with unique nonempty IDs, finite coordinates and targets, positive scales and integer k from 1 to 64. Coincident coordinates are valid. k larger than the row count is retained visibly but has no defined prediction; the algorithm neither clamps k nor invents rows. Empty data and malformed quantities are rejected.

The plot supports coordinates from $-3$ to $3$ and scales from $0.1$ to $10$. Arrow movement preserves existing fine precision; pointer dragging deliberately snaps to a $0.1$ lattice. Unsupported keyboard or numeric changes preserve the previous valid mathematical state with a visible reason. No display rounding is fed back into computation.

A finite input can still produce a nonfinite difference or final distance; that arithmetic is rejected. Exact computed distance ties and exact vote ties have separate policies. This sheet implements two-dimensional, unweighted k-NN with two categories, not approximate search, weighted voting or an empirical accuracy guarantee.

Check your understanding

Checkpoints

You can reconstruct a neighborhood from distances and identities, distinguish votes from numerical averaging, and explain why k, scales, duplicates and ties change the rule. k-NN converts stored local evidence into a decision; its geometry must match the prediction you report.