We need to specify a distance metric in our future space, so we know how to properly select the nearby neighbors. In the fruit classification example, we use the simple straight line, or Euclidean distance to measure the distance between points.

University of Michigan - Ann Arbor

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

Specifying a distance metric for k-Nearest Neighbors algorithm

1. $k \ge 1$.

2. There is no structured method to find the best value for “K”. We need to try to use training data and testing data to get accuracy.

3. A too small value for k (e.g. k=1 for 100 samples) may produce results that are too noisy and will have a higher influence on the result.

4. A too large value for k may produce categories with small number of samples in each. This is referred to as the curse of dimensionality where too many dimensions for the dataset may lead to a poor prediction of a given sample. Larger values of K will have smoother decision boundaries which mean lower variance but increased bias. Also, computationally expensive.

5. Another way to choose K is though cross-validation. One way to select the cross-validation dataset from the training dataset. Take the small portion from the training dataset and call it a validation dataset, and then use the same to evaluate different possible values of K. This way we are going to predict the label for every instance in the validation set using with K equals to 1, K equals to 2, K equals to 3. and then we look at what value of K gives us the best performance on the validation set and then we can take that value and use that as the final set of our algorithm so we are minimizing the validation error.

6. In general, practice, choosing the value of k is $k = \sqrt{N}$ where N stands for the number of samples in your training dataset.

7. The Elbow method for selecting optimal k.

Specifying K = the number of the nearest neighbors for a k-Nearest Neighbors algorithm

We may want to give some neighbors more influence on the outcome. For example, we may decide that neighbors that are closer to the new instance that we're trying to classify, should have more influence, or more votes on the final label.

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

In order to find the Euclidean distance, one has to take the square root of the sum of the squared difference between two points. The formula for calculating the Euclidean distance is given by:

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


Euclidean Distance

The Manhattan distance is found by using the absolute value of the sum of the difference between two points. Its formula is given by:

		$\sum_{i = 1}^k {|x_i-y_i|}$ 

Manhattan Distance

If you are using categorical variables, then using the Hamming distance will be helpful. If two points are the same, then the difference between them is 0. If they are not the same, the difference between them is 1. Its formula is given by:

		$D_H =  \sum_{i=1}^k {|x_i - y_i|}$
		$if x = y \Rightarrow 0$
		$if x \neq y \Rightarrow 1$

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