Linear regression is an example of a parametric method because it assumes a linear functional form for f(X). But if the specified functional form is far from the truth, and prediction accuracy is our goal, then the parametric method will perform poorly. This leads to higher bias. There is also a well known statistical theory behind linear regression.

KNN is an example of non parametric method that uses feature similarity. It is pretty useful, because in the real world, most of the practical data does not obey the typical theoretical assumptions made (eg gaussian mixtures, linearly separable etc). Non-parametric methods do not explicitly assume a parametric form for f(X), and thereby provide an alternative and more flexible approach for performing regression. This means it will have less bias and is more robust with highly non-linear settings. However, KNN regression is not as widely studied as linear regression.

Comparison of Linear Regression with K-Nearest Neighbors

For regression problems, a K value is first chosen, as well as a prediction point ($x_0$). The algorithm starts off by finding the K training observations that are closes to $x_0$. These training observations are denoted by $N_0$. In order to find $f(x_0)$, or the response value of your predicted point, KNN uses the average of the training observations in $N_0$. To do this, it does the following:

1. Depending on the value of k, it finds the distance (typically Euclidean) between it and the other observations.
2. It then chooses the k closest observations based on this distance ($N_0$).
3. The response values of the chosen k observations are averaged to predict the output of $x_0$.

Formally, the equation for this process is:

$$\hat{f}(x_0) =  \frac{1}{K} \sum_{x_i \in N_0}y_i$$
 
    

Regression Process of K-Nearest Neighbors

To implement KNN in R you need to install package "class"

Step 1: Clean your dataset, change categorical variables into dummy variables
Don't forget to change  your dataset since the input of knn must be numerical variables. To change categorical variables into dummy variables you can use the code below.
data_cleaned<- as.data.frame(model.matrix(~ . -1, data = dataset you want to use)

Step 2: Normalize your dataset

normalize <- function(x){
  return ((x - min(x)) / (max(x) - min(x)))
}
data_normalized <- as.data.frame(lapply(data_cleaned, normalize))


Step 3: Split your dataset into trainning data and test data, and get labels for these data

output<-data_normalized$outputcolumn
data_normalized$outputcolumn<-NULL
(This step is to get labels from dataset and delete label column from dataset as it's dependent variables)

test <- data_normalized[1:n, ]
train <- data_normalized[n:datasize,]
test_label <- output[1:n]
train_label <- output[n:datasize]

n depends on how you want to split your dataset

Step 4: Build your KNN model 
prediction <- knn(train = train, test = test, cl = train_label, k = n)

you can use any value for n

Step 5: See the accuracy using CrossTable
library(gmodels)
CrossTable(test_label, prediction)

accuracy=(true positive + true negative)/number of test labels


Step 6: Improve your accuracy
change k to improve accuracy



Implemention of KNN in R

(1) n_neighbors: the number of nearest neighbors to consider. The default value is 5. For a very low value of n_neighbors leads to overfitting on the training data, while high value of n_neighbors will make the model perform poorly on both train and validation set. We can draw a validation error curve to determine the optimal value of n_neighbors.
(2) metric: distance function between data points. The default value is Minkowski distance with power parameter p=2, which is equivalent to the standard Euclidean metric.

The important parameters of KNN classifier and regressor

The k-Nearest Neighbor (k-NN) Classifier
Algorithm

The k-Nearest Neighbor (k-NN) Classifier Algorithm

Algorithm：
Given a training set X_train with labels y_train, and given a new instance x_test to be classified:
1. Find the most similar instances (let's call them X_NN) to x_test that are in X_train.
2. Get the labels y_NN for the instances in X_NN
3. Predict the label for x_test by combining the labels y_NN
Implementation：
from sklearn.neighbors import KNeighborsClassifier
X_train, X_test, y_train, y_test = train_test_split(X_C1, y_C1, random_state = 0)
knnc = KNeighborsClassifier(n_neighbors = 5).fit(X_train, y_train)
knnc.predict(X_test)
knnc.score(X_test, y_test)

Implemention of KNN in Python

Exponentially weighted average is a technique frequently used for time-series data. By taking the average sum of previous data, you could smooth your data series and get an approximate trend of it. 

Consider you have a series of data points $\theta_0,...,\theta_n$,
$$\left\{ \begin{array}{ll}v_t = \theta_t & t=0 \\
v_t = \beta v_{t-1} +(1-\beta)\theta_t & otherwise \end{array}\right.$$
If we expand the second formula,
$v_t  = \beta v_{t-1}+(1-\beta)\theta_t$ 
      $= (1-\beta)\theta_t+\beta(\beta v_{t-2}+(1-\beta)\theta_{t-1})$
      $= (1-\beta)\theta_t + (1-\beta)\beta\theta_{t-1}+ (1-\beta)\beta^2\theta_{t-2}+...$
To get a sense of how the weighted term changes as $\beta$ gets closer to 1,
$$(1 - \epsilon)^{1 / \epsilon}\approx \frac{1}{\epsilon} \Rightarrow \beta^{1/(1-\beta)}\approx \frac{1}{\epsilon}$$
If we denote $w_i$ be the weight we assign to $\theta_i$, then
                                         $w_{t-1/(1-\beta)}=\frac{1}{\epsilon}w_t$
Therefore, we are approximately average over $1/(1-\beta)$ days when calculating $v_t$.

Exponentially Weighted Average

When using KNN for regression problems, the model is based off of ‘feature similarity’ which means that the output value of an observation you are trying to find is based on how closely it resembles the points in the training data set. With regression using KNN, this similarity is based on the average distance, typically using Euclidean distance, between the chosen observation and those around it.

University of Michigan - Ann Arbor

K-nearest neighbors is a non-parametric statistical method, which predicts based on the *k* nearest neighbors. k-NN classifiers are an example of what's called instance based or memory based supervised learning.

It can be applied to both classification and regression problems.
- When applied to classification problems, the prediction result would be the most common one among the *k* nearest training observations.
- When applied to regression problems, the prediction result would be the average of the *k* nearest training observations.

Some key notes about this method:
- It makes few assumptions about structure of data
- It gives potentially accurate but sometimes unstable predictions 
- It is sensitive to small changes in training data



K-nearest Neighbors (k-NN)

James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An introduction to statistical learning (Vol. 112, pp. 3-7). New York: springer.

An Introduction to Statistical Learning with Applications in R

Statquest with Josh Starmer.(2017, June 26). Statquest: K-nearest neighbors, Clearly Explained [Video]. Youtube.  [www.youtube.com/watch?v=HVXime0nQeI](https://www.youtube.com/watch?v=HVXime0nQeI) 

Reference Video: K-Nearest Neighbors

Dhiraj, K. (2019, August 29). Difference between K-Nearest Neighbor(K-NN) and K-Means Clustering. Medium. [medium.com/@dhiraj8899/difference-between-k-nearest-neighbor-k-nn-and-k-means-clustering-d9a44859182f](https://medium.com/@dhiraj8899/difference-between-k-nearest-neighbor-k-nn-and-k-means-clustering-d9a44859182f) 

Medium: Difference between K-Means and KNN

This reference gets into mathmatical ways how KNN and K-Nearest Neighbors are different concepts

Umamaheswaran, Venkatesh. (2018, November 12). Comprehending K-means and KNN Algorithms. Medium. Retrieved From [becominghuman.ai/comprehending-k-means-and-knn-algorithms-c791be90883d](https://becominghuman.ai/comprehending-k-means-and-knn-algorithms-c791be90883d) 

Math/Python Explanation: Difference Between K-Means and KNN

A good source that talks about KNN, it's various uses, its algorithm, and examples.

Harrison, O. (2019, July 14). Machine Learning Basics with the K-Nearest Neighbors Algorithm. Retrieved March 12, 2020, from [towardsdatascience.com/machine-learning-basics-with-the-k-nearest-neighbors-algorithm-6a6e71d01761](https://towardsdatascience.com/machine-learning-basics-with-the-k-nearest-neighbors-algorithm-6a6e71d01761) 

Machine Learning Basics with KNN Algorithm

KNN Regression

Singh, A. (2019, August 9). A Practical Introduction to K-Nearest Neighbor for Regression. Retrieved March 18, 2020, from https://www.analyticsvidhya.com/blog/2018/08/k-nearest-neighbor-introduction-regression-python/

A Practical Introduction to K-Nearest Neighbors Algorithm for Regression (Reference)

KNN can be useful in solving problems that have solutions that depend on identifying similar objects.
1. Recommender Systems
For example: Recommending products on Amazon, articles on Medium, movies on Netflix, or videos on YouTube.
2. Concept Search
This is used to search for semantically similar documents (i.e., documents containing similar topics). We could find it in many e-Discovery software packages, which are used for helping companies find all of the e-mails, contracts, etc.
3. Herta Security
They then use k-NN to identify a person by compare the face to their watchlist. 

KNN in practice

The UM online course: Applied Machine Learning in Python->Week 2-> K-Nearest Neighbors: Classification and Regression. The link is: https://www.online.umich.edu/courses/applied-machine-learning-in-python/



Reference video: K-Nearest Neighbors: Classification and Regression

Scikit-learn enables the creation of classifier objects. For example, 
```python
from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors = 5, weights = 'distance')
```
In this example, the classifier object (named knn) will consider 5 neighbors in its kneighbors queries.   Setting the weights parameter to 'distance' means that closer neighbors will be more influential than those farther away  (in terms of detemrining which category the "target" point belongs to).

sklearn.neighbors.KNeighborsClassifier

K-nearest neighbors can be used to classify data. Given a training set X_train with labels y_train, and given a new instance x_test to be classified:

- Find the k most similar instances (X_NN) to x_test that are in X_train.
- Get the labels y_NN for the instances in X_NN.
- Predict the label for x_test by combining the labels y_NN. The combination can be done through different methods, e.g., a simple majority vote can find the label that is the most common among the k most similar examples.

For example, if K = 1, then the first closest neighbor will be used to classify the unknown data point. If K = 14, then the 14 nearest neighbors will be used. If the data point falls between multiple clusters, then you choose the category that holds the most.

Classification Algorithm of K-Nearest Neighbors

Advantages
- It is easy and simple to implement
- Since it is non-parametric, you don’t have to make any assumptions about $f$
- A model does not need to be created
- It can be used for various statistical methods (classification, regression, etc.)

Disadvantages
- As the number of predictors increase, KNN can get very slow and at some point, not usable anymore.


K-Nearest Neighbors Advantages and Disadvantages

Used the data for classes 0, 1, and 2 plotted in the image.

What class would a KNeighborsClassifer classify the new point as for k = 1 and k = 3?

Which of the following is true for the nearest neighbor classifier?

The $$1$$-nearest neighbor algorithm is the simplest case of the $$k$$-nearest neighbor approach, where $$k=1$$. At training time, the learner memorizes the dataset, and at prediction time, it assigns a new data point the label of its single closest neighbor based on a chosen distance function $$d$$. Because it memorizes the data, the algorithm always achieves a training error of zero by perfectly interpolating the training data. Despite this, it can still generalize; under mild conditions, the $$1$$-nearest neighbor algorithm is a consistent estimator, meaning it eventually converges to the optimal predictor.

1-Nearest Neighbor Algorithm

In nonparametric methods like the $$k$$-nearest neighbor algorithm, a distance function, denoted as $$d$$, must be specified to measure the similarity between data points. Equivalently, this involves defining a vector-valued basis function $$\phi(\mathbf{x})$$ for featurizing the data. The choice of distance metric is critical because it encodes different inductive biases and represents specific assumptions about the underlying data patterns. With a finite amount of available data, different distance functions will yield different predictors depending on how compatible these assumptions are with the observed data.

Learn Before

Related

Learn After