Implementing the K Nearest Neighbors algorithm from scratch in Python
Tags: machinelearning, algorithms, python
Published: 2021-03-02 23:02:02

Machine learning to most is a black box technique. This means that the inputs and outputs are known but the process is not fully understood. However, I think that for most classical algorithms this should not be the case. This piece aims to help you learn to implement the K Nearest Neighbor algorithm in Python.

The principle behind nearest neighbor methods, in general, is to find a predefined number of training samples closest in distance to the new point, and predict the label from these. The number of samples, in this case, is a user-defined constant.

Despite its simplicity, nearest neighbor methods have been successful in a large number of classification and regression problems, including handwritten digits and satellite image scenes.

The optimal choice of the value "k" is dependent on the data but in general, a larger value suppresses the effects of noise but makes the classification boundaries less distinct. Enough of the talking, lets begin...

```
import numpy as np
from scipy.spatial.distance import euclidean
from sklearn.base import BaseEstimator

class KNNBase(BaseEstimator):
    ...
```

Firstly, we import the relevant modules which are `numpy`, `euclidean` and `BaseEstimator`. [Euclidean](https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.euclidean.html) determines how distance is calculated while `BaseEstimator` is the base class for all estimators in sklearn.

The `KNNBase` class thus takes this class as its parent and inherits its methods. This then becomes the base class for the K Nearest Neighbors classifier and regressor.

```
class KNNBase(BaseEstimator):
    def __init__(self, n_neighbors = 5, distance_func = euclidean):
        self.n_neighbours = n_neighbors
        self.distance_func = euclidean
    
    def _fit(self, X, Y):
      self.X = X
      self.Y = Y
      return self
```

The KNNBase class is initialized in the `__init__` method with 2 parameters namely the number of neighbors and the distance function. The former denotes the number of neighbors and determines the prediction for a particular data point while the latter determines how the distance is calculated.

The default values are taken as 5 for `n_neighbors` and `euclidean` for `distance_func` (any function from `scipy.spatial.distance` will do for `distance_func`).

The `_fit` method takes in the training features `X` and targets `Y` and stores them as instance variables. It then returns the now updated instance via `self`.
```
    def _vote(self, neighbors_targets):
        raise NotImplementedError()

    def _predict(self, X_test):
        Y_pred = np.empty(X_test.shape[0])
        for index, entry in enumerate(X_test):
          distances = [self.distance_func(i, entry) for i in self.X]
          neighbors = np.argsort(distances)[: self.n_neighbors]

          neighbors_prediction = [self.Y[j] for j in neighbors]

          Y_pred[index] = self._vote(neighbors_prediction)
        return Y_pred
```

The `_vote` method is a helper function that is not implemented in `KNNBase` class since it will be different for the classifier and regressor. However, its aim is to return the single prediction for a data point given its neighbor's targets.

The `_predict` method is the powerhouse of the algorithm and it takes in the data points `X_test` who's targets are to be predicted. The first thing we do is instantiate an empty array with the same number of elements as there are data point in `X_test`.

Next up, we loop through `X_test` and for each data point, the distances from every training example are calculated with the euclidean function.

These distances are then sorted with the `np.argsort` function and this returns the sorted array but instead of the values themselves as elements, it returns their indexes. This is useful to us because we need the indexes to get the corresponding predicted values for the nearest neighbors. 

The first k neighbors are sliced out of the sorted array and the targets at those points stored in `neighbors_prediction`. A vote is made using these values by calling on the `self._vote` method and the result is stored by filling up the once empty array `Y_pred`.

The complete `KNNBase` class is thus:
```
class KNNBase(BaseEstimator):
  def __init__(self, n_neighbors = 5, distance_func = euclidean):
    self.n_neighbors = n_neighbors
    self.distance_func = euclidean
  
  def fit(self, X, Y):
    self.X = X
    self.Y = Y
    return self
  
  def _vote(self, neighbors_targets):
    raise NotImplementedError()

  def predict(self, X_test):
    """
    Predict the targets of the test data.
    """

    Y_pred = np.empty(X_test.shape[0])
    for index, entry in enumerate(X_test):
      distances = [self.distance_func(i,entry) for i in self.X]
      neighbors = np.argsort(distances)[:self.n_neighbors]

      neighbors_prediction = [self.Y[j] for j in neighbors]

      Y_pred[index] = self._vote(neighbors_prediction)
    return Y_pred
```
## **The Classifier**

```
class KNNClassifier(KNNBase):
  
  def _vote(self, neighbors_target):
    count_ = np.bincount(neighbors_target)
    return np.argmax(count_)
  
```
This class inherits from the `KNNBase` class and implements the `_vote` method. In the `_vote` method, we take in the `neighbors_target` list and use the `np.bincount` method to generate the frequency of each class in the `neighbors_target` list. Then we return the argument with the highest value with `np.argmax`. If there is a tie for the most common label among the neighbors, then the predicted label is arbitrary.
## **The Regressor**

```
class KNNRegressor(KNNBase):
  def _vote(self, neighbors_target):
    return np.mean(neighbors_target)
```

This class also inherits from the KNNBase class and implements the `_vote` method. However, in the `_vote` method, we take in the `neighbors_target` list and use the `np.mean` function to find and return the mean of all its values.
To be sure that our algorithm works, we will compare its result on the Boston housing dataset with that of the sklearn implementation.

```
from sklearn.datasets import load_boston
from sklearn.neighbors import KNeighborsRegressor
X, y = load_boston(return_X_y = True)
model = KNNRegressor().fit(X,y)
pred= model.predict(X[:10])
print("For the first 10 data points,")
print(f"Our implementation gives: {pred}")

model1= KNeighborsRegressor().fit(X,y)
pred1= model1.predict(X[:10])
print(f"The Sklearn Implementation gives: {pred1}")
```
> ```
For the first 10 data points,
Our implementation gives: [21.78 22.9  25.36 26.06 27.1  27.1  20.88 19.1  18.4  19.48]
The Sklearn Implementation gives: [21.78 22.9  25.36 26.06 27.1  27.1  20.88 19.1  18.4  19.48]```

We have now successfully implemented the K-Nearest Neighbour algorithm. Feel free to test it on any other dataset.

I hope you enjoyed reading this. If you have any questions, you can contact me on Twitter [@phortz](https://www.twitter.com/fortsadek).

### References:
- [Sklearn Neighbours documentation](https://scikit-learn.org/stable/modules/neighbors.html)
- [Display Image Source](https://experiencelife.com/article/how-to-cope-with-a-bad-neighbor/)