kNN Classifier from Scratch (numpy only)

kNN Classifier from Scratch (numpy only)

Posted by Mario Valadez Trevino

Updated: Nov 24, 2019

k-Nearest Neighbors is a supervised machine learning algorithm for regression, classification and is also commonly used for empty-value imputation.  This technique "groups" data according to the similarity of its features.

KNN has only one hyper-parameter: the size of the neighborhood (k):

  • k represents the number of neighbors to compare data with.  Most of the times, at least in classification and imputation, k is odd just in case there is a tie between different neighbors.
  • the bigger the k, the less 'defined' the classification areas.

Distance is a key factor in order to determine who is the closest. Distance impacts the size and characteristics of the neighborhoods. The most commonly used is Euclidean, which is pretty simple, as it gives the closest distance between 2 points. But it is not suited for all distance calculations. Based on your needs, you may select one of the following forms of distance measurements:

  • Euclidean: the shortest distance between two points. This might not be the best option when features are normalized. It's typically used in face recognition.
  • Taxicab or Manhattan: the sum of the absolute differences of the Cartesian coordinates of 2 points. It works the same way as when a car needs to move around 'blocks' to get to the destination. So, it is basically adding the  horizontal and vertical distances in a 2 dimensional setting. 
  • Minkowski: a mix of both Euclidean and Minkowski.

The number of features influences kNN significantly because the more points we have, the more 'unique' each neighborhood becomes. It also affects speed because we need to measure each distance first in order to determine who are the closest k neighbors.

The kNN Algorithm

For downloading the code or testing it with the classic iris dataset, please see the GitHub repository.

The most efficient way to calculate the algorithm is in a vectorized form, so instead of calculating the points one by one is better to vectorize the final table and then sort the elements with shortest distances.

1.- Create a matrix with all the distances. The size of the matrix is i x j where i = rows in training set and j = rows in testing set.

[code language='python']

import pandas as pd
import numpy as np

def knn(xTrain, xTest, k):
    Finds the k nearest neighbors of xTest in xTrain.
    xTrain = n x d matrix. n=rows and d=features
    xTest = m x d matrix. m=rows and d=features (same amount of features as xTrain)
    k = number of nearest neighbors to be found
    dists = distances between xTrain/xTest points. Size of n x m
    indices = kxm matrix with indices of yTrain labels
    #the following formula calculates the Euclidean distances.
    distances = -2 * xTrain@xTest.T + np.sum(xTest**2,axis=1) + np.sum(xTrain**2,axis=1)[:, np.newaxis]
    #because of numpy precision, some really small numbers might 
    #become negatives. So, the following is required.
    distances[distances < 0] = 0
    #for speed you can avoid the square root since it won't affect
    #the result, but apply it for exact distances.
    distances = distances**.5
    indices = np.argsort(distances, 0) #get indices of sorted items
    distances = np.sort(distances,0) #distances sorted in axis 0
    #returning the top-k closest distances.
    return indices[0:k, : ], distances[0:k, : ]


2.- Sort the matrix by columns. Since all testing point distances to each training points is now in a matrix, we can sort the indexes for each testing point to find the closest k-neighbors.

3.- Get the y-label that repeats more (classification) or the average of the y-labels (regression). Find the points in the training set that are closer to the testing set points. Use mean for regression or mode for classification.

4- Create a new array with the projected label of the testing set. The size of the array is the same size as the y of the testing set.

[code language='python']

def knn_predictions(xTrain,yTrain,xTest,k=3):
    xTrain = n x d matrix. n=rows and d=features
    yTrain = n x 1 array. n=rows with label value
    xTest = m x d matrix. m=rows and d=features
    k = number of nearest neighbors to be found
    predictions = predicted labels, ie preds(i) is the predicted label of xTest(i,:)
    indices, distances = knn(xTrain,xTest,k)
    yTrain = yTrain.flatten()
    rows, columns = indices.shape
    predictions = list()
    for j in range(columns):
        temp = list()
        for i in range(rows):
            cell = indices[i][j]
        predictions.append(max(temp,key=temp.count)) #this is the key function, brings the mode value
    return predictions


5- Calculate accuracy of the projected labels. Evaluate the differences between the projected label of y in the testing set with the actual y of the testing set. If accuracy is low, we can change it by modifying k.

#from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
from sklearn import metrics
import matplotlib.pyplot as plt 

#will first check which is the best k
Ks = 15
mean_acc = np.zeros((Ks-1))
std_acc = np.zeros((Ks-1))
#ConfustionMx = [];
for n in range(1,Ks):    
    #Train Model and Predict
    #neigh = KNeighborsClassifier(n_neighbors = n).fit(xTrain,yTrain)
    mean_acc[n-1] = metrics.accuracy_score(yTest, yhat)    

print( "The best accuracy was:", np.round(mean_acc.max()*100,2), "% with k=", mean_acc.argmax()+1) 

plt.fill_between(range(1,Ks),mean_acc - 1 * std_acc,mean_acc + 1 * std_acc, alpha=0.05)
plt.legend(('Accuracy ', '+/- 3xstd'))
plt.ylabel('Accuracy ')
plt.xlabel('Number of Neighbors (k)')
In this case, the best k is equal to five.

Mario Valadez Trevino

Mario Valadez Trevino is a NYC Data Science Fellow with a B.S. in Industrial Engineering with minor in Systems Engineering and an MBA. Mario has relevant experience in demand forecasting, production and transportation planning, warehouse management systems and...

View all articles

Topics from this blog: Machine Learning Alumni python machine learning

Interested in becoming a Data Scientist?

Get Customized Course Recommendations In Under a Minute