In a $$k$$-Nearest Neighbors ($$k$$-NN) algorithm, a distance metric must be specified to determine how the proximity between data points in the feature space is calculated. This metric allows the algorithm to properly identify and select the nearest neighbors for a given query instance.

University of Michigan - Ann Arbor

Google

1. A distance metric
2. K = the of the nearest neighbors to use in making a prediction
3. Optional weighting function on the neighbor points
4. Method for aggregating the classes of neighbor points

Parameters to specify when training a k-Nearest Neighbors algorithm

Often times, statistical methods rely on measuring the distance between quantitative data points. However, there are various ways to measure this distance. These include:

1. Euclidean distance 
2. Manhattan distance
3. Hamming Distance

Measuring Distance Between Quantitative Data Points

In a $$k$$-Nearest Neighbors ($$k$$-NN) algorithm, an optional weighting function can assign varying levels of influence to neighbor points based on their distance from the query instance. Typically, closer neighbors are weighted more heavily, giving them greater influence on the final classification or prediction than neighbors that are further away.

Specifying the optional weighting function on the neighbor points for a k-Nearest Neighbors algorithm

Once we have the labels of the k nearby points, we must specify how to combine them to produce a final prediction.

Specifying a method for aggregating the classes of neighbor points for a k-Nearest Neighbors algorithm

Specifying the number of nearest neighbors, $$K$$, is a critical step in configuring a K-Nearest Neighbors (K-NN) algorithm:

- **Constraint**: $$K \ge 1$$.
- **Small $$K$$**: A value that is too small (e.g., $$K=1$$) makes the model overly sensitive to local noise, resulting in jagged decision boundaries, high variance, and overfitting.
- **Large $$K$$**: A value that is too large produces overly smoothed decision boundaries, leading to lower variance but increased bias (underfitting). It also increases computational cost.
- **Heuristic**: A common rule of thumb is setting $$K = \sqrt{N}$$, where $$N$$ is the total number of training samples.
- **Cross-Validation**: A more robust method is evaluating different $$K$$ values on a validation dataset and selecting the $$K$$ that minimizes the validation error.
- **Elbow Method**: This approach involves plotting the validation error rates for different $$K$$ values to visually identify the "elbow" or optimal point of diminishing returns.

Specifying K (the Number of Neighbors) for a K-Nearest Neighbors Algorithm

Specifying a Distance Metric for a k-Nearest Neighbors Algorithm

Euclidean distance is the straight-line distance between two points in a Euclidean space. For two points $$x$$ and $$y$$ in a $$k$$-dimensional space, the distance is calculated as the square root of the sum of the squared differences between their coordinates:

$$d(x, y) = \\sqrt{ \\sum_{i=1}^k (x_i - y_i)^2 }$$

Euclidean Distance

The Manhattan distance between two points is the sum of the absolute differences of their corresponding Cartesian coordinates. For two points $$x$$ and $$y$$ in a $$k$$-dimensional space, the distance is calculated as: $$d(x, y) = \sum_{i=1}^k |x_i - y_i|$$

Manhattan Distance

The Hamming distance is a metric useful for comparing categorical variables. It measures distance by counting the number of positions at which corresponding elements differ. For each position, if the two elements are the same, the difference is 0; if they are different, the difference is 1. Its formula is given by: $$D_H = \sum_{i=1}^k |x_i - y_i|$$ where $$|x_i - y_i| = 0$$ if $$x_i = y_i$$, and $$|x_i - y_i| = 1$$ if $$x_i \neq y_i$$.

Hamming Distance

The reference below has a good reference to KNN, as well as different ways in which distance is measured.

Brownlee, J. (2019, August 12). K-Nearest Neighbors for Machine Learning. Retrieved March 23, 2020, from [machinelearningmastery.com/k-nearest-neighbors-for-machine-learning/](https://machinelearningmastery.com/k-nearest-neighbors-for-machine-learning/) 

Learn Before

Related