<jupyter_start><jupyter_text><NAME> - <NAME> - CSE My Github Profile  K- Nearest Neighbours Code Implementation from scratch with complete explaination Images and some explainations are taken from Various Medium Blogs and official documentation  Machine Learning Basics with the K-Nearest Neighbors Algorithm![title](http://res.cloudinary.com/dyd911kmh/image/upload/f_auto,q_auto:best/v1531424125/KNN_final1_ibdm8a.png)The k-nearest neighbors (KNN) algorithm is a simple, easy-to-implement supervised machine learning algorithm that can be used to solve both classification and regression problems - The KNN algorithm assumes that similar things exist in close proximity. In other words, similar things are near to each other.__“Birds of a feather flock together.”__- KNN captures the idea of similarity (sometimes called distance, proximity, or closeness) with some mathematics we might have learned in our childhood— calculating the distance between points on a graph.     What’s KNN?- KNN (K — Nearest Neighbors) is one of many (supervised learning) algorithms used in data mining and machine learning, it’s a __classifier algorithm where the learning is based “how similar” is a data (a vector) from other .__ ![title](https://cdn-images-1.medium.com/max/1200/1*3-NZnN68PNp12y0Q9G0X6w.png)  __‘k’__ in KNN is a parameter that refers to the number of nearest neighbours to include in the majority of the voting process. __How shall I choose the value of k in KNN Algorithm?__![title](https://cdn-images-1.medium.com/max/1600/0*kzsntHPVInqJghMs.gif) __k’ in KNN algorithm is based on feature similarity choosing the right value of K is a process called parameter tuning and is important for better accuracy. Finding the value of k is not easy.__Research has shown that no optimal number of neighbors suits all kind of data sets. Each dataset has it's own requirements. In the __case of a small number of neighbors__, __the noise will have a higher influence on the result, and a large number of neighbors make it computationally expensive__<jupyter_code>import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
# plt.style.use('seaborn-poster')
dfx=pd.read_csv("Data_sets/xdata.csv")
dfy=pd.read_csv("Data_sets/ydata.csv")
X=dfx.values# first column of dataframe  contains the serial numbers that we not required so we need to drop that
Y=dfy.values
print(X.shape)
print(Y.shape)
X
dfx[0:5]
X=X[:,1:]
Y=Y[:,1:].reshape((-1,))
print(X.shape)
print(Y.shape)
    print(X[0:5])
    print(Y[0:5])
plt.scatter(X[:,0],X[:,1],c=Y)
#Lets have a query point
query_x=np.array([2,3])
plt.scatter(X[:,0],X[:,1],c=Y)
plt.scatter(query_x[0],query_x[1],c='red')
plt.show()<jupyter_output><empty_output><jupyter_text>__To determine which of the K instances in the training dataset are most similar to a new input__ a distance measure is used. For real-valued input variables, the most popular distance measure is __Euclidean distance__.- __Euclidean distance is calculated as the square root of the sum of the squared differences between a new point (x) and an existing point (xi) across all input attributes j.__    - __EuclideanDistance(x, xi) = sqrt( sum( (xj – xij)^2 ) )__- The value for K can be found by __algorithm tuning__. It is a good idea to try many different values for K (e.g. values from 1 to 21) and see what works best for your problem.<jupyter_code>def euclid_dist(x1,x2):
    return np.sqrt(sum((x1-x2)**2))

def knn(X,Y,query_point,k=5):
    
    dist_values=[]
    m=X.shape[0]
    
    for i in range(m):
        d=euclid_dist(query_point,X[i])
        dist_values.append((d,Y[i]))#(distance,label)
#     print(dist_values[0:5])
    dist_values=sorted(dist_values)
    #Nearest /First K points
    dist_values=dist_values[:k]
#     print(dist_values)
    vals=np.array(dist_values)
#     print(vals)
    new_vals=np.unique(vals[:,1],return_counts=True)
    print(new_vals[0][new_vals[1].argmax()]) #new_vals[1].argmax() will give the index of maximum frquency oflabel 
    

knn(X,Y,query_x,k=5)<jupyter_output>0.0<jupyter_text>Recognising Handwritten Digits on MNIST Dataset using KNN<jupyter_code>df=pd.read_csv("Data_sets/mnist_train.csv")
print(df.shape) #Each image is 28*28=784 pixel
print(df.columns)
df.head(n=5)
data=df.values
print(data.shape)
print(type(data))
X=data[:,1:]
Y=data[:,0]
print(X.shape)
print(Y.shape)
## Can also use scikit split method
from sklearn.model_selection import train_test_split
X_train,X_test,Y_train,Y_test =train_test_split(X,Y,test_size=0.2)
print(X_train.shape,X_test.shape,Y_train.shape,Y_test.shape)
# Visualise Some Samples

def drawImg(sample):
    img=sample.reshape(28,28)
    plt.imshow(img,cmap='gray')
    plt.show()
drawImg(X_train[785])
print(Y_train[785])<jupyter_output><empty_output><jupyter_text>Step2: Knn<jupyter_code>def euclid_dist(x1,x2):
    return np.sqrt(sum((x1-x2)**2))

def knn(X,Y,query_point,k=5):
    
    dist_values=[]
    m=X.shape[0]
    
    for i in range(m):
        d=euclid_dist(query_point,X[i])
        dist_values.append((d,Y[i]))#(distance,label)
#     print(dist_values[0:5])
    dist_values=sorted(dist_values)
    #Nearest /First K points
    dist_values=dist_values[:k]
#     print(dist_values)
    vals=np.array(dist_values)
#     print(vals)
    new_vals=np.unique(vals[:,1],return_counts=True)
    print(new_vals[0][new_vals[1].argmax()]) #new_vals[1].argmax() will give the index of maximum frquency oflabel<jupyter_output><empty_output><jupyter_text>Step3: Make Predictions<jupyter_code>knn(X_train,Y_train,X_test[78])
drawImg(X_test[78])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11123052122514777, 'fraction_numerical': 0.02041912950026867, 'mean_word_length': 5.267115600448934, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 22, 'https://': 2, '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': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '367247', 'license': 'MIT', 'n_tokens_mistral': 1993, 'n_tokens_neox': 1916, 'n_words': 553, 'path': 'Supervised Learning/K-Nearest Neighbours.ipynb', 'repo_name': 'AshwinKushwah/hacktoberfest2k19-data-science-contributions', 'size': '5592'}