In the realm of machine learning, the concept of distance serves as the mathematical foundation for determining how similar or dissimilar two data points are. Among all distance measures, Euclidean distance stands as the most intuitive and historically significant—it is the "straight-line" distance we experience in physical space.

When we say that K-Nearest Neighbors finds the K closest training examples to make predictions, we must precisely define what closest means. This seemingly simple question opens a rich mathematical domain with profound implications for algorithm behavior, computational efficiency, and prediction quality.

Euclidean distance, named after the ancient Greek mathematician Euclid of Alexandria, extends the familiar notion of distance from the Pythagorean theorem to arbitrary dimensions. It forms the default metric in most implementations of KNN and serves as the reference point against which all other distance measures are compared.

The Euclidean distance formula emerges naturally from the Pythagorean theorem, one of the oldest and most fundamental results in mathematics. Let us build the formula systematically, starting from the familiar two-dimensional case and extending to arbitrary dimensions.

The Two-Dimensional Case

Consider two points in the Cartesian plane:

$$\mathbf{p} = (x_1, y_1) \quad \text{and} \quad \mathbf{q} = (x_2, y_2)$$

To find the straight-line distance between $\mathbf{p}$ and $\mathbf{q}$, we construct a right triangle where:

• The horizontal leg has length $|x_2 - x_1|$ (the difference in x-coordinates)
• The vertical leg has length $|y_2 - y_1|$ (the difference in y-coordinates)
• The hypotenuse is the straight-line distance we seek

By the Pythagorean theorem, the hypotenuse $d$ satisfies:

$$d^2 = (x_2 - x_1)^2 + (y_2 - y_1)^2$$

Taking the square root:

$$d(\mathbf{p}, \mathbf{q}) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

This is the Euclidean distance in two dimensions.

Extension to Three Dimensions

The extension to three dimensions is straightforward. For points:

$$\mathbf{p} = (x_1, y_1, z_1) \quad \text{and} \quad \mathbf{q} = (x_2, y_2, z_2)$$

We apply the Pythagorean theorem twice:

1. First, find the distance in the xy-plane: $d_{xy} = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$
2. Then, form a right triangle with $d_{xy}$ and the z-difference: $d^2 = d_{xy}^2 + (z_2-z_1)^2$

Substituting:

$$d^2 = (x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2$$

$$d(\mathbf{p}, \mathbf{q}) = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2}$$

The General n-Dimensional Formula

Inductively extending this pattern to $n$ dimensions, for vectors:

$$\mathbf{p} = (p_1, p_2, \ldots, p_n) \quad \text{and} \quad \mathbf{q} = (q_1, q_2, \ldots, q_n)$$

The Euclidean distance (also called the L² norm of the difference vector) is:

$$d(\mathbf{p}, \mathbf{q}) = \sqrt{\sum_{i=1}^{n}(p_i - q_i)^2} = |\mathbf{p} - \mathbf{q}|_2$$

This elegant formula encapsulates the "straight-line" distance in any number of dimensions.

Euclidean distance has a profound connection to linear algebra and vector spaces. Understanding this connection provides deeper insight into why Euclidean distance behaves as it does and how it relates to other concepts in machine learning.

Distance as a Norm of the Difference

The Euclidean distance between points $\mathbf{p}$ and $\mathbf{q}$ can be expressed as the L² norm (also called the Euclidean norm) of their difference vector:

$$d(\mathbf{p}, \mathbf{q}) = |\mathbf{p} - \mathbf{q}|_2$$

where the L² norm of a vector $\mathbf{v} = (v_1, v_2, \ldots, v_n)$ is:

$$|\mathbf{v}|2 = \sqrt{\sum{i=1}^{n} v_i^2}$$

This interpretation reveals that distance is fundamentally about the magnitude of the displacement vector between two points.

Connection to Inner Products

The squared Euclidean distance has an elegant expression using inner products (dot products):

$$d(\mathbf{p}, \mathbf{q})^2 = (\mathbf{p} - \mathbf{q}) \cdot (\mathbf{p} - \mathbf{q}) = \mathbf{p} \cdot \mathbf{p} - 2\mathbf{p} \cdot \mathbf{q} + \mathbf{q} \cdot \mathbf{q}$$

This expansion is computationally useful:

$$d(\mathbf{p}, \mathbf{q})^2 = |\mathbf{p}|^2 - 2\mathbf{p}^T\mathbf{q} + |\mathbf{q}|^2$$

Key insight: If we precompute $|\mathbf{p}|^2$ for all training points, computing distances to a query point $\mathbf{q}$ requires only the dot products $\mathbf{p}^T\mathbf{q}$ and the single value $|\mathbf{q}|^2$. This is especially efficient for matrix-based implementations.

Geometric Interpretation: The Unit Ball

Every distance metric induces a geometry on the space. The unit ball for a metric is the set of all points at distance ≤ 1 from the origin:

$$B = {\mathbf{x} : d(\mathbf{0}, \mathbf{x}) \leq 1}$$

For Euclidean distance, the unit ball is:

• A circle in 2D
• A sphere in 3D
• A hypersphere in $n$D

This spherical geometry has important implications:

1. Isotropy: Euclidean distance treats all directions equally. Moving 1 unit in any direction produces the same distance.

2. Rotation Invariance: Euclidean distance is unchanged by rotations of the coordinate system. Mathematically, for any orthogonal matrix $R$: $$d(R\mathbf{p}, R\mathbf{q}) = d(\mathbf{p}, \mathbf{q})$$

3. Translation Invariance: Distance depends only on the relative positions, not absolute positions: $$d(\mathbf{p} + \mathbf{t}, \mathbf{q} + \mathbf{t}) = d(\mathbf{p}, \mathbf{q})$$ for any translation vector $\mathbf{t}$

These properties make Euclidean distance natural for physical measurements but can be problematic when features have different scales or when the geometry of the data is non-spherical.

A distance function (or metric) must satisfy four fundamental axioms to be mathematically well-defined. These axioms capture our intuitive understanding of what "distance" should mean. We will prove that Euclidean distance satisfies all four axioms, making it a proper metric.

The Four Axioms of a Metric

A function $d: X \times X \to \mathbb{R}$ is a metric on set $X$ if for all points $\mathbf{p}, \mathbf{q}, \mathbf{r} \in X$:

Axiom 1: Non-negativity

$$d(\mathbf{p}, \mathbf{q}) \geq 0$$

Proof for Euclidean distance: Since $(p_i - q_i)^2 \geq 0$ for all $i$, the sum is non-negative, and the square root of a non-negative number is non-negative. ∎

Axiom 2: Identity of Indiscernibles

$$d(\mathbf{p}, \mathbf{q}) = 0 \iff \mathbf{p} = \mathbf{q}$$

Proof for Euclidean distance:

• ($\Leftarrow$) If $\mathbf{p} = \mathbf{q}$, then $p_i = q_i$ for all $i$, so each $(p_i - q_i)^2 = 0$, giving $d = 0$.
• ($\Rightarrow$) If $d = 0$, then $\sum_i (p_i - q_i)^2 = 0$. Since each term is non-negative, all terms must be zero, so $p_i = q_i$ for all $i$. ∎

Axiom 3: Symmetry

$$d(\mathbf{p}, \mathbf{q}) = d(\mathbf{q}, \mathbf{p})$$

Proof for Euclidean distance: Since $(p_i - q_i)^2 = (q_i - p_i)^2$, the sums are equal. ∎

Axiom 4: Triangle Inequality

$$d(\mathbf{p}, \mathbf{r}) \leq d(\mathbf{p}, \mathbf{q}) + d(\mathbf{q}, \mathbf{r})$$

The triangle inequality states that the direct path is never longer than any indirect path—"the shortest distance between two points is a straight line."

Proof of the Triangle Inequality

We prove the more general result: for vectors $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$:

$$|\mathbf{u} + \mathbf{v}|_2 \leq |\mathbf{u}|_2 + |\mathbf{v}|_2$$

Step 1: Square both sides (preserves inequality since both sides are non-negative): $$|\mathbf{u} + \mathbf{v}|_2^2 \leq (|\mathbf{u}|_2 + |\mathbf{v}|_2)^2$$

Step 2: Expand the left side: $$|\mathbf{u} + \mathbf{v}|_2^2 = (\mathbf{u} + \mathbf{v}) \cdot (\mathbf{u} + \mathbf{v}) = |\mathbf{u}|_2^2 + 2\mathbf{u} \cdot \mathbf{v} + |\mathbf{v}|_2^2$$

Step 3: Expand the right side: $$(|\mathbf{u}|_2 + |\mathbf{v}|_2)^2 = |\mathbf{u}|_2^2 + 2|\mathbf{u}|_2|\mathbf{v}|_2 + |\mathbf{v}|_2^2$$

Step 4: We need to show: $$\mathbf{u} \cdot \mathbf{v} \leq |\mathbf{u}|_2 |\mathbf{v}|_2$$

This is the Cauchy-Schwarz inequality, one of the most important inequalities in mathematics.

Step 5: Cauchy-Schwarz proof (brief): Define $f(t) = |\mathbf{u} + t\mathbf{v}|_2^2 = |\mathbf{u}|_2^2 + 2t(\mathbf{u} \cdot \mathbf{v}) + t^2|\mathbf{v}|_2^2$

This parabola in $t$ is always non-negative. For a quadratic $at^2 + bt + c \geq 0$ to hold for all $t$, the discriminant must be non-positive: $b^2 - 4ac \leq 0$.

Applying: $(2\mathbf{u} \cdot \mathbf{v})^2 - 4|\mathbf{v}|_2^2 |\mathbf{u}|_2^2 \leq 0$

Simplifying: $(\mathbf{u} \cdot \mathbf{v})^2 \leq |\mathbf{u}|_2^2 |\mathbf{v}|_2^2$

Taking square roots: $|\mathbf{u} \cdot \mathbf{v}| \leq |\mathbf{u}|_2 |\mathbf{v}|_2$ ∎

The triangle inequality follows immediately.

Computing Euclidean distances efficiently is critical for KNN performance. In a brute-force KNN search with $N$ training points of dimension $D$, we compute $N$ distances, each requiring $O(D)$ operations. Understanding computational optimizations is essential for practical implementations.

The Squared Distance Optimization

The most important optimization arises from a key insight: when comparing distances, we often don't need the actual distances—only their relative ordering.

Since the square root function is monotonically increasing: $$d(\mathbf{p}, \mathbf{q}) < d(\mathbf{p}, \mathbf{r}) \iff d(\mathbf{p}, \mathbf{q})^2 < d(\mathbf{p}, \mathbf{r})^2$$

This means we can skip the square root operation entirely when:

• Finding the K nearest neighbors (comparison-based)
• Sorting points by distance
• Checking if a point is within a threshold distance (if threshold is squared)

Computational savings: The square root operation is typically 10-30x slower than basic arithmetic operations on modern processors.

Matrix-Based Batch Distance Computation

When computing distances between many point pairs, we can leverage matrix operations for massive speedups through BLAS/LAPACK optimizations.

For a query matrix $Q$ of shape $(m, D)$ and data matrix $X$ of shape $(N, D)$, we want the distance matrix $D$ of shape $(m, N)$ where $D_{ij} = d(\mathbf{q}_i, \mathbf{x}_j)$.

Using the identity: $$d(\mathbf{q}, \mathbf{x})^2 = |\mathbf{q}|^2 - 2\mathbf{q}^T\mathbf{x} + |\mathbf{x}|^2$$

We can compute all distances as:

1. Compute $|\mathbf{q}_i|^2$ for all queries (vector of length $m$)
2. Compute $|\mathbf{x}_j|^2$ for all data points (vector of length $N$)
3. Compute $QX^T$ (matrix multiply, shape $(m, N)$)
4. Combine: $D^2_{ij} = |\mathbf{q}i|^2 - 2(QX^T){ij} + |\mathbf{x}_j|^2$

The matrix multiplication dominates the computation and benefits from highly optimized BLAS implementations.

Euclidean distance has a critical property that is both a strength and a weakness: it treats all dimensions equally. This isotropy becomes problematic when features have different scales or units.

The Problem Illustrated

Consider a dataset with two features:

• Age: ranges from 0 to 100 years
• Income: ranges from $0 to $1,000,000

Compare two pairs of people:

• Person A (Age=25, Income=$50,000) vs Person B (Age=26, Income=$50,000)
• Person A (Age=25, Income=$50,000) vs Person C (Age=25, Income=$950,000)

Euclidean distance:

• $d(A, B) = \sqrt{(26-25)^2 + (50000-50000)^2} = 1$
• $d(A, C) = \sqrt{(25-25)^2 + (950000-50000)^2} = 900000$

The income difference completely dominates, making the age feature effectively invisible. A $900,000 income difference contributes 900,000² = 810 billion to the squared distance, while a 1-year age difference contributes just 1.

Solutions: Feature Scaling

The standard solutions involve transforming features to comparable scales:

1. Min-Max Normalization (Rescaling)

Scale each feature to the range $[0, 1]$:

$$x'_i = \frac{x_i - \min(x)}{\max(x) - \min(x)}$$

Pros: Bounded output, preserves zero values for sparse data Cons: Sensitive to outliers (a single extreme value stretches the range)

2. Z-Score Standardization

Transform each feature to have zero mean and unit variance:

$$x'_i = \frac{x_i - \mu}{\sigma}$$

where $\mu$ is the mean and $\sigma$ is the standard deviation.

Pros: Handles outliers better, centers the data Cons: Unbounded output, doesn't preserve sparsity

3. Robust Scaling

Use median and interquartile range (IQR) instead of mean and standard deviation:

$$x'_i = \frac{x_i - \text{median}(x)}{\text{IQR}(x)}$$

Pros: Highly resistant to outliers Cons: Doesn't capture the full data range

Despite its limitations, Euclidean distance remains the default choice for many applications. Understanding when it performs well helps in selecting the appropriate metric.

Ideal Conditions for Euclidean Distance

Euclidean distance is the optimal or near-optimal choice when:

1. Isotropic Data Geometry

When the "true" similarity between data points follows spherical geometry—meaning similarity decreases equally in all directions—Euclidean distance correctly captures this structure.

Example: Physical sensor data where deviation in any feature direction is equally significant (temperature, pressure, vibration magnitude).

2. Low to Moderate Dimensionality

Euclidean distance works well in low dimensions (D < 20) where the curse of dimensionality hasn't yet made all points equidistant. The geometric intuition from 2D/3D extends naturally.

3. Continuous, Dense Features

For continuous numerical features that can take any value in an interval, Euclidean distance provides smooth gradients of similarity. It naturally handles the interpolation between nearby values.

Example: Scientific measurements, engineering specifications, any data derived from physical quantities.

4. Post-Normalization Data

After proper scaling (Z-score standardization), features become comparable, and Euclidean distance provides a principled weighting where each standard deviation of change contributes equally.

5. When Rotation Invariance Matters

Euclidean distance is invariant to rotations of the coordinate system. If your problem has no preferred direction (isotropic), this is desirable.

Example: Comparing molecular conformations in 3D space after alignment.

Euclidean distance can fail dramatically in certain scenarios. Recognizing these pathologies helps avoid misapplication.

High-Dimensional Catastrophe

In high dimensions, Euclidean distance suffers from a phenomenon called distance concentration. For random points in high-dimensional space:

$$\frac{d_{\max} - d_{\min}}{d_{\min}} \to 0 \text{ as } D \to \infty$$

All points become approximately equidistant! This makes nearest-neighbor search meaningless—every point is almost equally close to every other point.

Mathematical intuition: In $D$ dimensions, distance is $d = \sqrt{\sum_{i=1}^D (x_i - y_i)^2}$. By the law of large numbers, as $D \to \infty$, the sum concentrates around its expected value, and relative variations shrink.

Sparse Data Problems

For sparse data (many zero entries), Euclidean distance can be problematic:

• Two documents with no words in common have distance proportional to the document lengths, not semantic difference
• Zero values contribute nothing to similarity but inflate distance from non-zero points
• The "background" of zeros dominates the signal

Axis-Aligned Biases

Euclidean distance treats axis-aligned differences the same as diagonal differences. But in many domains, this is inappropriate:

Example - Chess: A king moves one square in any direction (including diagonals). Manhattan distance (covered next) says diagonal is distance 2; Euclidean says it's $\sqrt{2}$. Neither matches the king's actual movement (Chebyshev distance: 1).

Wrapping Domains

Euclidean distance doesn't handle periodic or cyclical features:

Example - Time of day: 11:55 PM and 12:05 AM (midnight) are 10 minutes apart, but Euclidean distance on 24-hour representation (23.92 vs 0.08) gives 23.84, suggesting nearly maximum difference!

Solutions:

• Transform to circular coordinates: $(\cos(2\pi t / 24), \sin(2\pi t / 24))$
• Use specialized periodic distance functions

Heterogeneous Feature Types

Euclidean distance is fundamentally designed for continuous numerical features. Mixing in:

• Categorical features: What is $d(\text{"red"}, \text{"blue"})$?
• Ordinal features: Is the distance between ratings 1 and 2 the same as between 4 and 5?
• Binary features: How should presence/absence contribute?

Solutions: Use hybrid distance functions like Gower distance, or embed categorical features appropriately.

Euclidean distance is the fundamental building block of distance-based machine learning. Its simplicity, intuitive geometric interpretation, and strong theoretical foundations make it the default starting point. However, its assumptions—isotropy, continuous features, comparable scales—must be verified before application.

Key Takeaways