Vectors and Distance: Explain the Neighbor You Choose

A nearest-neighbor classifier is only as meaningful as its coordinates, distance, and tie rules. In this module you will compute those choices by hand, implement them, then change a representation and predict how the result changes.

Prerequisites: dot products, square roots, and sorting tuples. The exercise uses equal-length numeric lists. Review linear algebra if a dot product or vector norm is unfamiliar. For saved training scales, use feature engineering; you do not need to complete the intervening classifiers first.

Derive three comparisons

Take a=[1,2] and b=[4,6]. Their difference is [-3,-4]:

Comparison	Calculation	Result
Euclidean L2 distance	sqrt(3^2+4^2)	5
Manhattan L1 distance	abs(-3)+abs(-4)	7
Cosine similarity	(1*4+2*6)/(sqrt(5)*sqrt(52))	approximately 0.9923

These answer different questions. L2 measures straight-line displacement; L1 adds coordinatewise displacement; cosine compares direction after dividing each nonzero vector by its own length. A pair can have large Euclidean distance and cosine one: [1,0] and [100,0] point in the same direction.

Neither L1 nor L2 automatically fixes different feature units. Squaring inside L2 gives large coordinate differences greater relative influence, but calling L1 generally “robust” or appropriate for different scales hides the representation choice.

Choose the representation before trusting distance

Let the query be [0,0], candidate A [1,100], and B [2,0]. Raw Euclidean distance chooses B (2 versus approximately 100). If the second coordinate's meaningful unit is 100, dividing that feature by 100 gives A [1,1], B [2,0], and chooses A (sqrt(2) versus 2). Scaling changed the decision.

Cosine is invariant to multiplying an entire nonzero vector by a positive scalar. It is not invariant to rescaling just one feature across the dataset: scaling coordinates changes angles too. Choose units and any fitted scaler using training data and domain meaning, then evaluate the resulting neighbors on held-out examples. There is no universal “always normalize” rule.

Zero vectors and distance conventions

Cosine is mathematically undefined if either vector has zero norm. This exercise deliberately returns similarity 0.0 in that case, so cosine_distance=1-similarity returns 1.0. normalize returns a zero vector unchanged. These are explicit fallback conventions, not proof that a zero vector has a direction or unit length.

For nonzero vectors, 1-cosine ranges from 0 to 2. Despite its common name, it is not a mathematical metric in general. For a=[1,0], b=[1,1], c=[0,1], distance(a,c)=1, while distance(a,b)+distance(b,c) is about 0.586; the triangle inequality fails. Do not assume every indexing algorithm for true metrics applies unchanged. The metric exercise asks for these formulas and conventions, not an index structure.

Trace a complete KNN prediction

Use training points [[0,0],[1,1],[2,2],[3,3]], labels [0,0,1,1], query [1.5,1.5], and k=3.

Sorted neighbor	Distance	Label
[1,1]	sqrt(0.5)	0
[2,2]	sqrt(0.5)	1
[0,0]	sqrt(4.5)	0
[3,3]	sqrt(4.5)	1

The exercise sorts (distance,label) tuples, so equal-distance neighbors use ascending label order. Take the first three, then count labels: two votes for 0, one for 1. The prediction is 0. The query's first two equally close neighbors do not determine a three-neighbor vote by themselves.

If labels tie in vote count, choose the label that occurs first in the sorted neighbor list. With k=2 above, both labels have one vote and 0 wins. With neighbors [(0.1,2),(0.9,1)], label 2 wins: this is a nearest-appearance tie rule, not always the smallest label. Labels are integers, and 1<=k<=number of training rows.

Computing all distances costs O(n*d), sorting costs O(n log n), and voting over k costs O(k). KNN stores training examples rather than learning weight vectors; changing k and scaling still requires validation. A larger k smooths decisions but may include other populations; it is not automatically more accurate.

Finish a trace before seeing the answer

Query [0] has training points [[1],[-1],[3]], labels [2,1,2], and k=2. Write the sorted tuples, the vote counts, and the predicted label. Then change only k to 3.

Check the neighbor and vote trace

The tuples are [(1,1),(1,2),(3,2)]. At k=2 the counts tie, so the first encountered label 1 wins. At k=3, label 2 has two votes and wins. Notice that equal distances are ordered by label, not by the input rows.

Independent transfer

Before coding, invent two nonzero vectors with cosine 1 but nonzero L2 distance, and a rescaling that changes a nearest-neighbor choice. Implement distance-metrics, then knn-classifier, without copying a full prediction function from the lesson. After passing tests, perturb a training coordinate and explain whether the predicted label should change; a correct answer on the worked dataset alone is not enough.

High dimensionality can reduce distance contrast for some distributions, but it does not imply that all real datasets become equidistant. Irrelevant dimensions, data geometry, and representation quality determine whether a metric helps. The next text-representation module makes this concrete using sparse word vectors.