<jupyter_start><jupyter_text>K - Nearest Neighbours Implementation (KNN) This notebook explains various NumPy techniques that can be used to implement the KNN algorithm from scratch.  About K - Nearest Neighbours K - Nearest Neighbours is a non-parameteric machine learning algorithm which can be used for both classification and regression. Here $k$ is the hyper parameter for the model. This model is usually evaluated with different values of $k$ to find the best value of the $k$. It uses distance measuring function (which computes the similarities between the points). Typically a squared euclidean distance is used. Training:Since KNN uses the raw data points for prediction, there is no model training occurs. we just simply store the Training points as it is. Classification:1. Calculate the distance between test point $\mathbf{\hat x}$ and all the points $\mathbf{x_i}$ in the training set.2. Argsort the distances and take the first k values inorder to find the indices of the K nearest neighbours from the training set.3. Predict the class of the test point $\hat y$ by majority voting(i.e, the class with most occurences), using the classes $y_i$ of the k nearest neighbours. Regression:1. Step 1 and 2 is same as for classification.2. Predict the value of $\hat y$ by computing the mean of the $y_i$ of the k nearest neighbours.  Importing Modules Lets import all the required modules. This notebook only uses NumPy for the KNN algorithm. Pandas is just used for loading  the dataset.  Version info<jupyter_code>!pip list scipy | grep -E '(numpy|scipy|pandas) '
import numpy as np
import pandas as pd
import scipy as sp
print(f'numpy == {np.__version__}',f'scipy == {sp.__version__}', f'pandas == {pd.__version__}',sep='\n')<jupyter_output>numpy == 1.21.0
scipy == 1.7.0
pandas == 1.3.0<jupyter_text>KNN Classification  Loading and processing the Diabetes dataset(For Classification) Now lets load the pima indians diabetes dataset using Pandas. As the dataset is loaded as pd.DataFrame, we use variable `diabetes_df` for stroing the dataset.  **Note:** The suffix "df"(short for DataFrame) is used with pd.DataFrame objects to differentiate them.<jupyter_code>diabetes_df = pd.read_csv("datasets/pima-indians-diabetes.csv")
diabetes_df.head()<jupyter_output><empty_output><jupyter_text>X - y split<jupyter_code>X = diabetes_df.iloc[:,:-1].values
y = diabetes_df.iloc[:,-1].values<jupyter_output><empty_output><jupyter_text>Min - Max Normalization (Min - Max scaling) Min-Max Normalization or Min-Max Scaling is one of the feature scaling methods, which scales the features to a range of 0-1.Which is mathematically represented as:$$\text{MimMax}(\mathbf{x}) = \frac{\mathbf{x} -\min (\mathbf{x})}{\max (\mathbf{x}) -\min (\mathbf{x})}$$<jupyter_code>def min_max_scale(X):
    X_min, X_max = X.min(axis = 0) , X.max(axis =0)
    return (X-X_min)/(X_max-X_min)
X = min_max_scale(X)
X<jupyter_output><empty_output><jupyter_text>Train - Test split<jupyter_code>def train_test_split(X,y,split_ratio=.7,shuffle=False):
    sl = int(X.shape[0]*split_ratio)
    if shuffle:
        indices = np.arange(X.shape[0])
        np.random.shuffle(indices)
        X,Y = X[indices],y[indices]
    X_train,y_train = X[:sl],y[:sl]
    X_test,y_test = X[sl:],y[sl:]
    return X_train,y_train,X_test,y_test<jupyter_output><empty_output><jupyter_text>Now lets split the data set into training and testing sets with a split ratio of 7:3.<jupyter_code>X_train,y_train,X_test,y_test = train_test_split(X,y,.7)<jupyter_output><empty_output><jupyter_text>Calculating Squared euclidean distance The squared euclidean distance between two feature vectors (or data points) $\mathbf{a} = (a_1,a_2,...,a_n)^T$ and $\mathbf{b} = (b_1,b_2,...,b_n)^T$ can be computed as follows$$\text{sqEuclidean}(\mathbf{a},\mathbf{b}) = \sum_{i=0}^{n} (a_i - b_i)^2 = (\mathbf{a}- \mathbf{b}) \cdot (\mathbf{a} - \mathbf{b}) = (\mathbf{a} - \mathbf{b})^T (\mathbf{a} - \mathbf{b})$$Lets discuss multiple methods the squrared euclidean function can be implemented with numpy. One vs OneTo find the squared euclidean distance between two points $\mathbf{a}$ and $\mathbf{b}$<jupyter_code>def sq_euclidean_1(a,b):
    """Squared Euclidean distance using summation."""
    return np.sum((a-b)**2)

def sq_euclidean_2(a,b):
    """Squrared Euclidean distance using dot product"""
    diff = a-b
    return np.dot(diff,diff)

def sq_euclidean_3(a,b):
    """Squared Euclidean distance using matrix multiplication"""
    diff = a-b
    return diff.T @ diff
a, b = X_train[0],X_train[1]
print(sq_euclidean_1(a,b))
print(sq_euclidean_2(a,b))
print(sq_euclidean_3(a,b))<jupyter_output>0.3178707190193263
0.3178707190193263
0.3178707190193263<jupyter_text>Many vs OneNow lets try to find the squared euclidean distance between a set of $m$ points $A$ and a point $b$<jupyter_code>A, b = X_train[:5],X_train[5]
print(sq_euclidean_1(A,b))
print(sq_euclidean_1(A,b)) 
print(sq_euclidean_1(A,b))<jupyter_output>2.0541060222933143
2.0541060222933143
2.0541060222933143<jupyter_text>This is not the required result, we need $m = 5$ distances, thus the requried result must have the shape `(m,)`, in this case `(5,)`. So lets make changes to the code so that it could find m different distances.<jupyter_code>def sq_euclidean_4(A,b):
    """Squared Euclidean distance using summation. Also supports A to be 2D"""
    return np.sum((A-b)**2, axis =-1) #Here -1 denotes the last axis<jupyter_output><empty_output><jupyter_text>we cannot use dot product or matrix multiplication directly in this case because those funcions does not provide flexibility in specifying the axes on which the sum of products is calculated. Thus we could use `np.einsum` function to implement this.<jupyter_code>def sq_euclidean_5(A,b):
    """Squared Euclidean distance using einstein summation. Also supports A to be 2D"""
    diff = A-b # numpy broad casting is used here
    return np.einsum("ij,ij->i",diff,diff) 
A, b = X_train[:5],X_train[5]
print(sq_euclidean_4(A,b))
print(sq_euclidean_5(A,b))<jupyter_output>[0.31298594 0.17433988 0.19394755 0.16849053 1.20434212]
[0.31298594 0.17433988 0.19394755 0.16849053 1.20434212]<jupyter_text>Thus we get our expected results.   Many vs Many Now lets compute the distances between set of $m$ points $A$ and set of $n$ points $B$. Thus we need $m\times n$ distances and the expected shape is `(n,m)`. So to get the result as expected we make use of the array broadcasting feature in numpy.**Note:** Here `(n,m)` is used instead of `(m,n)` because it is assumed that B will be the set of test points. thus it is convenient to have it in the 0-th axis.<jupyter_code>def sq_euclidean_6(A,B):
    """Squared Euclidean distance using summation. Also supports A and B to be 2D"""
    return np.sum((A-B[:,np.newaxis,:])**2, axis =-1) 

def sq_euclidean_7(A,B):
    """Squared Euclidean distance using einstein summation. Also supports A and B to be 2D"""
    diff = A-B[:,np.newaxis,:] 
    return np.einsum("ijk,ijk->ij",diff,diff) # also added an additional dimension<jupyter_output><empty_output><jupyter_text>**Note:** The only difference between the previous set and this was the introuction of a new axis to allow numpy broadcating.Refer [this link](https://numpy.org/devdocs/user/theory.broadcasting.html) to know more about numpy array broadcasting rules<jupyter_code>A, B = X_train[:3],X_train[3:7]
dist6 = sq_euclidean_6(A,B)
dist7 = sq_euclidean_7(A,B)
print(dist6)
print(dist7) 
print(f"Shape of A = {A.shape} and Shape of B = {B.shape}")
print("Is dist6 and dist7 are same?",np.all(dist6 == dist7))
print(f"Shape of dist6 = {dist6.shape} and shape of dist7 = {dist7.shape}")<jupyter_output>[[0.4827717  0.05087282 0.54448802]
 [0.839176   0.90589191 1.04147037]
 [0.31298594 0.17433988 0.19394755]
 [0.38682202 0.05719462 0.54931948]]
[[0.4827717  0.05087282 0.54448802]
 [0.839176   0.90589191 1.04147037]
 [0.31298594 0.17433988 0.19394755]
 [0.38682202 0.05719462 0.54931948]]
Shape of A = (3, 8) and Shape of B = (4, 8)
Is dist6 and dist7 are same? True
Shape of dist6 = (4, 3) and shape of dist7 = (4, 3)<jupyter_text>Now that we made our function accept two two dimensioal arrays, Lets generalize this so that it accepts $B$ in $N$ dimensions.<jupyter_code>def sq_euclidean_8(A,B):
    """Squared Euclidean distance using summation. Supports A to be 2D and B to be N dimensional."""
    return np.sum((A-B[...,np.newaxis,:])**2, axis =-1) # added ellipsis to support N dimensions.

def sq_euclidean_9(A,B):
    """Squared Euclidean distance using einstein summation. Supports A to be 2D and B to be N dimensional."""
    diff = A-B[...,np.newaxis,:] 
    return np.einsum("...i,...i->...",diff,diff) # added ellipis to support N dimensions.
A, B = X_train[:3],X_train[3:9].reshape(2,3,-1)
dist8 = sq_euclidean_8(A,B)
dist9 = sq_euclidean_9(A,B)
print(dist8)
print(dist9) 
print(f"Shape of A = {A.shape} and Shape of B = {B.shape}")
print("Is dist6 and dist7 are same?",np.all(dist8 == dist9))
print(f"Shape of dist6 = {dist8.shape} and shape of dist7 = {dist9.shape}")<jupyter_output>[[[0.4827717  0.05087282 0.54448802]
  [0.839176   0.90589191 1.04147037]
  [0.31298594 0.17433988 0.19394755]]

 [[0.38682202 0.05719462 0.54931948]
  [0.72359709 0.70798156 0.49305372]
  [0.58316553 0.90399208 0.93269195]]]
[[[0.4827717  0.05087282 0.54448802]
  [0.839176   0.90589191 1.04147037]
  [0.31298594 0.17433988 0.19394755]]

 [[0.38682202 0.05719462 0.54931948]
  [0.72359709 0.70798156 0.49305372]
  [0.58316553 0.90399208 0.93269195]]]
Shape of A = (3, 8) and Shape of B = (2, 3, 8)
Is dist6 and dist7 are same? True
Shape of dist6 = (2, 3, 3) and shape of dist7 = (2, 3, 3)<jupyter_text>Squared Euclidean distance using cdist `cdist` is a function defined in the scipy library, which can be used to calculate the distances using various metrics including squared euclidean distance. But `cdist` require $A$ and $B$ to be strictly 2 dimensional. But we can reshape the array before passing it into it and after returning.<jupyter_code>from scipy.spatial.distance import cdist
def sq_euclidean_dist(A,B):
    '''Returns Squared Euclidean Distance, between two set of points A and B using scipy.spatial.distance.cdist.\
Requires A to be 2-D and B can be N-D'''
    m,n = A.shape
    final_shape = *B.shape[:-1],m
    return cdist(B.reshape(-1,n),A,metric="sqeuclidean").reshape(final_shape)
dist = sq_euclidean_dist(A,B) # B, A is used instead of A, B, to be consistent with out previous implementations.
print(dist)
print("Shape of dist is :", dist.shape)
sq_euclidean_9(A,B) == sq_euclidean_dist(A,B)<jupyter_output><empty_output><jupyter_text>Comparision of implementations<jupyter_code>%%timeit
sq_euclidean_8(A,B)
%%timeit
sq_euclidean_9(A,B)
%%timeit
sq_euclidean_dist(A,B)<jupyter_output>11.3 µs ± 1.09 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)<jupyter_text>From the above implementations it is clear that the `sq_euclidean_dist` (using cdist) perfroms the fastest among our implementations.  Finding the y Values of the k nearest neignbours Now lets find the y values of the k nearest neighbours.To do that 1. Use the `np.argsort` to get the indices in order of distances in acending order. 2. Slice the first k indices to get the indices of the k nearest neignbours3. by using indexing on y with the computed indices, we get the required y values<jupyter_code>k = 3
k_nearest_ys = y_train[np.argsort(sq_euclidean_dist(X_train,X_test))[...,:k]]
print(
    k_nearest_ys[0],
    k_nearest_ys[3],
    k_nearest_ys[5],
    sep="\n"
)<jupyter_output>[1 0 0]
[0 0 0]
[1 0 0]<jupyter_text>Majority voting for calssification 1. Find the classes available in the training using `np.unique` and store it in `classes`2. Compute the equality tensor for each point by equating it with the classes in a fashion similar to outer product.3. Compute the sum of the equality tensor to get the comut tensor, containing the count of each classes among the nearest neighbours.4. Using the `np.argmax` find the index of the class with the maximum count among the nearest neighbours.5. Get the class name from at the found index by indexing the `classes`<jupyter_code>classes = np.unique(y_train)
equality_tensor = k_nearest_ys[...,np.newaxis,:] == classes.reshape(-1,1)
count_tensor = np.sum(equality_tensor,axis = -1)
max_count_class_index = np.argmax(count_tensor, axis = -1)
y_hat = classes[max_count_class_index]
print(
    "Nearest ys of 0, 3 and 5",
    k_nearest_ys[0],
    k_nearest_ys[3],
    k_nearest_ys[5],
    sep="\n"
)
print(
    "Equality tensor of 0, 3 and 5",
    equality_tensor[0],
    equality_tensor[3],
    equality_tensor[5],
    sep="\n"
)
print(
    "Count tensor of 0, 3 and 5",
    count_tensor[0],
    count_tensor[3],
    count_tensor[5],
    sep="\n"
)
print(
    "Max count class index of 0, 3 and 5",
    max_count_class_index[0],
    max_count_class_index[3],
    max_count_class_index[5],
    sep="\n"
)
print(
    "Predicted class of 0, 3 and 5",
    y_hat[0],
    y_hat[3],
    y_hat[5],
    sep="\n"
)<jupyter_output>Nearest ys of 0, 3 and 5
[1 0 0]
[0 0 0]
[1 0 0]
Equality tensor of 0, 3 and 5
[[False  True  True]
 [ True False False]]
[[ True  True  True]
 [False False False]]
[[False  True  True]
 [ True False False]]
Count tensor of 0, 3 and 5
[2 1]
[3 0]
[2 1]
Max count class index of 0, 3 and 5
0
0
0
Predicted class of 0, 3 and 5
0
0
0<jupyter_text>Class for KNN Classifier Lets Ecapsulate everything we discussed into a python class<jupyter_code>class KNN:
    '''Base class for KNN'''
    def __init__(self,k=3,weights:{'uniform','distance'}='uniform',dist=sq_euclidean_dist):
        self.dist = dist
        self.k = k
    
    def fit(self,X_train,y_train):
        self.X_train = X_train
        self.y_train = y_train
        
    def k_nearest_ys(self,X_test):
        '''Returns the y values of the k nearest neighbours.\ 
This is computed for both classification and regression.'''
        return self.y_train[np.argsort(self.dist(self.X_train,X_test))[...,:self.k]]
    
class KNNClassifier(KNN):
    """K Nearest Neighbour Classifier"""
    def fit(self,X_train,y_train):
        super().fit(X_train, y_train)
        self.classes = np.unique(y_train)
    
    def predict(self,X_test):
        '''Returns the predicted class for the points in test_x, i.e, classification result'''
        return self.classes[
            np.argmax(
                np.sum(
                    self.k_nearest_ys(X_test)[...,np.newaxis,:] == self.classes.reshape(-1,1),
                    axis = -1
                ),
                axis=-1
            )
        ]<jupyter_output><empty_output><jupyter_text>Implementing the KNN classifier  Evaluation metrics for classifier<jupyter_code>def classifier_accuracy(y_test, y_pred,in_percent=False):
    '''Returns the Classifier accuarcy of the classifier.It is defined as  
(no. of correct classifications) / (no. of test items)'''
    accuracy = (y_pred == y_test).mean()
    if in_percent : return accuracy*100
    return accuarcy<jupyter_output><empty_output><jupyter_text>Evaluating the Classifier model<jupyter_code>diabetes_predictor = KNNClassifier(k = 3)
diabetes_predictor.fit(X_train,y_train)
y_pred = diabetes_predictor.predict(X_test)
print(f"Acuracy of the classifier is : {classifier_accuracy(y_test,y_pred,in_percent = True):.3f} %",)<jupyter_output>Acuracy of the classifier is : 76.623 %<jupyter_text>Evaluating with multiple values for k (Hyperparamer tuning)<jupyter_code>for k in range(4,7):
    diabetes_predictor = KNNClassifier(k = k)
    diabetes_predictor.fit(X_train,y_train)
    y_pred = diabetes_predictor.predict(X_test)
    print(f"Acuracy of the classifier with k = {k} is : {classifier_accuracy(y_test,y_pred,in_percent = True):.3f} %",)<jupyter_output>Acuracy of the classifier with k = 4 is : 77.922 %
Acuracy of the classifier with k = 5 is : 75.325 %
Acuracy of the classifier with k = 6 is : 74.459 %<jupyter_text>Thus by varying the the value of $k$ the optimal value of k is found to be **4**.  **Note:** The process of finding the optimal values for the hyper parameters is called as hyper parameter tuning  Comparing our KNNClassifier with sklearn KNeighboursClassifier  Importing sklearn KNN Classifier<jupyter_code>from sklearn.neighbors import KNeighborsClassifier<jupyter_output><empty_output><jupyter_text>Evaluating SkLearn KNN classifier<jupyter_code>skl_diabetes_predictor = KNeighborsClassifier(4)
skl_diabetes_predictor.fit(X_train,y_train)
y_pred = skl_diabetes_predictor.predict(X_test)
print(f"Acuracy of the SkLearn classifier is :{classifier_accuracy(y_test,y_pred,True):.3f}",)<jupyter_output>Acuracy of the SkLearn classifier is :77.922<jupyter_text>KNN Regressor  Loading and processing Real estate Dataset (For Regression)<jupyter_code>real_estate_df = pd.read_csv("datasets/real-estate.csv")
real_estate_df.head()<jupyter_output><empty_output><jupyter_text>Spliting Training and Testing data Here we also get rid of the first column (No) since it does not help in regression<jupyter_code>X = real_estate_df.iloc[:,1:-1].values 
y = real_estate_df.iloc[:,-1].values<jupyter_output><empty_output><jupyter_text>Min - Max Normalization (Min - Max scaling)<jupyter_code>X_min, X_max = X.min(axis = 0) , X.max(axis =0)
X = X_min + X/(X_max-X_min)
X<jupyter_output><empty_output><jupyter_text>Train - Test split<jupyter_code>X_train,y_train,X_test,y_test = train_test_split(X,y,.7)<jupyter_output><empty_output><jupyter_text>Average and Distance weighted average for regression For regression we use the Average or distance wighted average of the K nearest neighbours as the predicted value. Using Average$$\hat y = \frac{\displaystyle\sum_{x_i \in \text{KNN}} y_i}{k} = \frac{\displaystyle \mathbf{y}_\text{KNN} \cdot \mathbf{1}}{k}$$ Using Distance weighted average$$\hat y = \frac{\displaystyle \sum_{x_i \in \text{KNN}} \frac{y_i}{d_i} }{\displaystyle \sum_{x_i \in \text{KNN}} \frac{1}{d_i}}= \frac{\displaystyle\frac{1}{\mathbf{d}_\text{KNN}}\cdot \mathbf{y}_\text{KNN}}{\displaystyle \frac{1}{\mathbf{d}_\text{KNN}}.\mathbf{1}}$$where, $d_i$ is the distance from the test point to the $i$th training point.  Class For KNN Regressor<jupyter_code>class KNNRegressor(KNN):
    '''K Nearest Neighbour Regressor'''
    
    def predict(self, X_test):
        '''Returns the predicted y values for the points in test_x, i.e, regression result.'''
        return np.mean(self.k_nearest_ys(X_test), axis = -1)<jupyter_output><empty_output><jupyter_text>Implementing the KNN Regressor<jupyter_code>housing_price_predictor = KNNRegressor(k = 3)
housing_price_predictor.fit(X_train,y_train)
y_pred = housing_price_predictor.predict(X_test)<jupyter_output><empty_output><jupyter_text>Evaluating KNN Regressor<jupyter_code>rmse = np.sqrt(np.mean((y_test-y_pred)**2))
print(f"Root Mean Squared Error {rmse:.3f}")<jupyter_output>Root Mean Squared Error 8.065<jupyter_text>Evaluating KNN Regressor for multiple values of k<jupyter_code>for k in range(4,10):
    housing_price_predictor = KNNRegressor(k = k)
    housing_price_predictor.fit(X_train,y_train)
    y_pred = housing_price_predictor.predict(X_test)
    rmse = np.sqrt(np.mean((y_test-y_pred)**2))
    print(f"Root Mean Squared Error {rmse:.3f}")<jupyter_output>Root Mean Squared Error 7.686
Root Mean Squared Error 7.481
Root Mean Squared Error 7.601
Root Mean Squared Error 7.617
Root Mean Squared Error 7.698
Root Mean Squared Error 7.558<jupyter_text>Comparing our KNNRegressor with sklearn KNeighboursRegressor  Importing sklearn KNN Regressor<jupyter_code>from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error
skl_housing_price_predictor = KNeighborsRegressor(3)
skl_housing_price_predictor.fit(X_train,y_train)
y_pred = skl_housing_price_predictor.predict(X_test)<jupyter_output><empty_output><jupyter_text>Evaluating SkLearn KNN Regressor<jupyter_code>rmse = np.sqrt(np.mean((y_test-y_pred)**2))
print(f"Root Mean Squared Error {rmse:.3f}")<jupyter_output>Root Mean Squared Error 8.070
{'fraction_non_alphanumeric': 0.11502745881178232, 'fraction_numerical': 0.053369945082376434, 'mean_word_length': 4.8416447944006995, 'pattern_counts': {'":': 0, '<': 118, '<?xml version=': 0, '>': 121, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '33', 'dir': 'jupyter-structured-clean-dedup', 'id': '588630', 'license': 'MIT', 'n_tokens_mistral': 7923, 'n_tokens_neox': 7034, 'n_words': 2088, 'path': 'K Nearest Neigbours using NumPy.ipynb', 'repo_name': 'livinNector/machine-learning-projects', 'size': '20030'}