<jupyter_start><jupyter_text>kNN Introductionk Nearest Neighbours is one of the simples classification technique widely used in the Machine Learning domain. kNN is a non-parametric and lazy learning technique.Non-parametric means that it doesn't make any underline assumption on the distribution of data, that is, the model structure is determined from the data.Lazy learning means that kNN doesn't involve a training phase as in most algorithms. The prediction is made using most(all) of the data and no training has to be done before predicting a sample point.Due to the above 2 main points, kNNs have a lot of real world applications, name, Anomaly Detection, Spam detection, Credit ratings, OCR etc In this notebook we'll look how to apply KNN on the famous digit recognition dataset, the MNIST dataset  Preparing the dataset1. Download and place the ```mnist_train.csv``` and ```mnist_test.csv``` files into the current directory2. Read ```mnist_train.csv``` and ```mnist_test.csv```Link: https://pjreddie.com/projects/mnist-in-csv/<jupyter_code>import pandas as pd # for reading and manipulating csv files
import numpy as np # for mathematical manipulation
# read the csv file
# note the csv file doesn't include a header row, hence we'll use the auto generated headers
df_train = pd.read_csv('./mnist_train.csv', header=None)
df_train.head()<jupyter_output><empty_output><jupyter_text>Here, we can see that the 0th column is actually the label of the data, therefore we'll extract it<jupyter_code>data = df_train.drop([0], axis=1)
labels = df_train[0]
# convert the data and labels into numpy arrays
X_train = np.array(data)
y_train = np.array(labels)
X_train.shape, y_train.shape
df_test = pd.read_csv('./mnist_test.csv', header=None)
df_test.head()
data_test = df_test.drop([0], axis=1)
labels_test = df_test[0]
# convert the data and labels into numpy arrays
X_test = np.array(data_test)
y_test = np.array(labels_test)<jupyter_output><empty_output><jupyter_text>kNN algorithm from sk-learn libraryBefore implementing our own kNN algorithm let's see how well does sklearn's kNN work with our dataset<jupyter_code># import the kNN classifier
from sklearn.neighbors import KNeighborsClassifier
# create an instance of kNN classifier with k=5
knn = KNeighborsClassifier(n_neighbors=5)
# fit the model using X_train as training data and y_train as target values
knn.fit(X_train, y_train)<jupyter_output><empty_output><jupyter_text>Let's check how the kNN model is doing on a random data point<jupyter_code># returns the distance of k closest naighbours and their indices
dist, indices = knn.kneighbors(X_test[54].reshape(1,-1))
for i in range(len(indices)):
    print(y_train[indices[i]])
# get the correct label
y_test[54]<jupyter_output><empty_output><jupyter_text>The model predicts that the digit is 6 and it indeed is. Awesome! Now, let's calculate the accuracy over all the test data points<jupyter_code># returns the mean accuracy on the given test data and labels
knn.score(X_test, y_test)<jupyter_output><empty_output><jupyter_text>Accuracy = 96.88% We've taken a look into sklearn's implementation of kNN algorithm. Now, it's time to implement our own algorithm  kNN Algorithm from scratch@TODO<jupyter_code>from collections import Counter
class KNeighborsClassifier:
    def __init__(self, n_neighbors=5):
        self.n_neighbors = n_neighbors
        self.labels = []
        self.X_train = []
        self.y_train = []
        self.distances = []
        
    def fit(self, X_train, y_train):
        self.X_train = np.array(X_train)
        self.y_train = np.array(y_train)
        
    def euclidean_distance(self, X):
        x = np.array(X)
        distances = []
        for index, data_point in enumerate(self.X_train):
            data_point = np.array(data_point)
            distance = np.linalg.norm(data_point - x)
            distances.append([distance, y_train[index]])
            
        return distances
            
    def get_class_votes(self, distances):
        distances_sorted = sorted(distances)[:self.n_neighbors]
        label = Counter([distance[1] for distance in distances_sorted]).most_common(1)[0][0]
        
        return [label]
    
    def predict(self, X):
        predicted = []
        for element in X:
            distances = self.euclidean_distance(element)
            predicted.append(self.get_class_votes(distances))
        return np.array(predicted)
    
    def score(self, X, y):
        predicted = self.predict(X)
        _y = y.reshape(-1,1)
        checked = np.equal(predicted, _y)
        
        return np.mean(checked)
# create an instance of kNN classifier with k=5
knn = KNeighborsClassifier(n_neighbors=5)
# fit the model using X_train as training data and y_train as target values
knn.fit(X_train, y_train)
# returns the mean accuracy on the given test data and labels
knn.score(X_test, y_test)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08436926839209292, 'fraction_numerical': 0.0065212961076013855, 'mean_word_length': 4.080745341614906, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 25, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '649029', 'license': 'MIT', 'n_tokens_mistral': 1552, 'n_tokens_neox': 1493, 'n_words': 507, 'path': 'kNN MNIST.ipynb', 'repo_name': 'frextrite/kNN-MNIST', 'size': '4907'}