To implement a K-Nearest Neighbors (KNN) classifier in R, you can use the `knn()` function from the `class` package. The general process involves data preparation, prediction, and evaluation:

1. **Clean Dataset**: KNN requires numerical inputs. Convert categorical variables into dummy variables:
```r
data_cleaned <- as.data.frame(model.matrix(~ . - 1, data = dataset))
```

2. **Normalize Dataset**: Scale numerical features to ensure they contribute equally to the distance metric:
```r
normalize <- function(x) { return ((x - min(x)) / (max(x) - min(x))) }
data_normalized <- as.data.frame(lapply(data_cleaned, normalize))
```

3. **Train-Test Split**: Separate the labels and split the dataset:
```r
labels <- data_normalized$outputcolumn
data_normalized$outputcolumn <- NULL

train <- data_normalized[1:split_index, ]
test <- data_normalized[(split_index + 1):nrow(data_normalized), ]
train_labels <- labels[1:split_index]
test_labels <- labels[(split_index + 1):length(labels)]
```

4. **Build Model and Predict**:
```r
library(class)
prediction <- knn(train = train, test = test, cl = train_labels, k = 5)
```

5. **Evaluate Model**: Assess accuracy using tools like `CrossTable` from the `gmodels` package:
```r
library(gmodels)
CrossTable(test_labels, prediction)
```

Implementation of K-Nearest Neighbors (KNN) Classifier in R

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

University of Michigan - Ann Arbor

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.

KNN Regression

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 K-Nearest Neighbors (KNN) regression, a value $$K$$ and a prediction point $$x_0$$ are first chosen. The algorithm estimates the response value $$f(x_0)$$ by averaging the training observations closest to $$x_0$$. The process is as follows: 1. Calculate the distance (typically Euclidean) between $$x_0$$ and all other training observations. 2. Identify the $$K$$ training observations closest to $$x_0$$, denoted by the set $$N_0$$. 3. Average the response values of these $$K$$ observations to predict the output for $$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

(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

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$.

Learn Before

Related

Learn After

Learn After

Related