euclidean distance

The Euclidean distance is the measure of the true straight-line distance between two points in a Euclidean space. It is the geometric distance you would measure with a ruler, representing the shortest path between those points.

The Formula

#

In a 2D Space, for two points $P_1(x_1, y_1)$ and $P_2(x_2, y_2)$:

It is used in the K-means algorithm to calculate the distance from the centroids, and it is also the core error metric used to build and optimize regression decision trees by selecting the best split that results in the lowest total RSS for the resulting child nodes:

Core Characteristics

#

• Pythagorean Basis: It is a direct extension of the Pythagorean theorem ($a^2 + b^2 = c^2$).
• Scale Sensitivity: It is highly sensitive to the scale of the axes. If one variable has much larger numbers than another, it will dominate the distance calculation (requiring data normalization or standardization).
• Curse of Dimensionality: In very high-dimensional spaces (like text embeddings), Euclidean distance becomes less effective because the distances between all pairs of points begin to converge.

Vector Context

#

In vector calculus, the Euclidean distance between two vectors $\mathbf{p}$ and $\mathbf{q}$ is equivalent to the L2 norm of their difference:

Vectorized euclidean distance implementation

#

The first function that can be made more efficient is the one calculating distances.
In algorithms like KNN or K-means, rather than looping over all the queries and the training samples (KNN) or the training samples and the centroids (K-means), we can do the following:

• multiply the training matrix by its transpose with squaredX = np.matmul(X, X.T). If we imagine the row of features for every training sample, this method squares and pairs every feature of every training row with every other row. We obtain a squared matrix for all training samples.
• extract the diagonal of that matrix since the diagonal contains only the values multiplied by themselves with diagX = np.diag(squaredX) (so we turn every 2D grid into a 1D list of values)
• we need to match the shape of the other matrix at the following step (similar to the first step on the list, but between X and the test data Z), so we repeat the array resulting from the previous step M times (where M is the number of queries) over the features axis 1 with XX = np.tile(diagX, (Z.shape[0], 1))
• We also transpose the resulting matrix with XX_transposed = XX.T to perform the dot product of the next steps
• repeat the above for the test data, with the
• We follow the same steps for the test data ZZ= np.tile(np.diag(np.matmul(Z, Z.T)), (X.shape[0],1)) , with the difference that the shape to match is the one of the training data N
• we compute the distances between points from X and points from Z using the dot product again: XZ=np.matmul(X, Z.T); if row $i$ is a training point and row $j$ is a query point, the result at position $(i,j)$ is the dot product $X_i \cdot Z_j$
• finally, we compute the square root of the distances D= np.sqrt(XX-2*XZ+ZZ) breaking down the $(x1 - x2)^2$ into $(x_1^2 + x_2^2 - 2x_1x_2)$

In numpy:

def euclidean_distance_vectorized_numpy(X, Z):    
    # Find the distance from each point 
    
    squaredX = np.matmul(X, X.T)
    diagX = np.diag(squaredX)
    XX = np.tile(diagX, (Z.shape[0], 1))
    XX_transposed = XX.T
    
    ZZ= np.tile(np.diag(np.matmul(Z, Z.T)), (X.shape[0],1))
    
    XZ=np.matmul(X, Z.T)
    
    D= np.sqrt(XX_transposed-2*XZ+ZZ)
    
    return D

In PyTorch:

def euclidean_distance_vectorized_PyTorch(X, Z):
	# Find the distance from each point 
    
    squaredX = X @cX.T
    diagX = torch.diag(squaredX)
    XX = torch.tile(diagX, (Z.shape[0], 1))
    XX_transposed = XX.T
    
    ZZ= torch.tile(torch.diag(torch.matmul(Z, Z.T)), (X.shape[0],1))
    
    XZ= X @ Z.T
    
    D= np.sqrt(XX_transposed-2*XZ+ZZ)
    
    return D