<jupyter_start><jupyter_text>KNN KNN stands for K-Nearest Neighbours. KNN is simple classification algorithm and it is generally used for datasets in which data points are separated into several classes and we have to predict the class for the new sample point.KNN is non-parametric and lazy learning algorithm.Non-parametric basically means that the algorithm does not make any assumptions on the given data distribution. NON-parametric covers technique that do not rely on data belonging to particular distribution and do not assume the structure of model to be fixed. So, KNN is used as classification algorithm in cases where we do not have much information about the distribution of the data.KNN is referred to as Lazy algorithm since is does not uses training points to do any generalization, which means that there is no separate training phase. KNN keeps all the training data and uses most of the training data during the testing phase. Thus, KNN does not learn any model, it make predictions on the fly, computing similarity between testing point and each training data point. KNN algorithm is  based on feature similarity. We can classify the testing data point on the basis of resemblance of its features with that of the training data set.![title](knn_intro.png) The test sample(green circle) should either be classified into Class 1(blue squares) or Class 2(red triangles).The class for the sample testing point is decided on the basis of majority vote-out.If value of K=1, the nearest training point belongs to Class 1, so we will say that the testing sample belongs to Class 1. Now, take the value of K to be 3, again using the methodology of majority vote, we will say that testing sample belongs to Class 2(red traingles), since out of three nearest training data points, two belongs to Class 2 and one belong to Class 1.Hence, using the same method, we can predict the class for the tesing smaple, using pre-decided value of K. KNN can be used for Classification as well as Regression.While using KNN for classification - output is a class membership, we will classify the sample point using the technique of majority vote among its neighbors and the most common class among its k nearest neighbours is assigned to the testing point. In regression, output is the property value of object, this value is average or median of the value of its K nearest neighbors.In classification, KNN is used to predict a class which is a discrete value whereas in regression, KNN predicts continuous values.  Why don't we choose value value of K=1 ?Choosing the value of K=1 makes our model more prone to outliers and overfitting. Value of K=1 means that we will consider only the closest (or nearest) neighbor to predict the class for our testing sample, and in majority of the cases it will lead to overfitting.![title](knn_k1.jpg) Consider the case here, if we choose value of K=1, the given training sample will get classified as dot(Class 2), instead of being classified as a cross(Class 1). So, in such cases certain optimal value of K should be choosen to get good results. Choosing the value of K = 1, leads to formation of complex decision boundaries and hence will lead to overfitting to the data. Since we will be using the majority vote technique, so value of K is taken to be odd, to obtain clear result about the class of the testing data sample.  Distance Metric for KNNThere are various distance metrices that can be choosen are Manhattan Distance, Euclidian Distance, etc. \begin{equation*}\textbf{MANHATTAN DISTANCE} = \left| \sum_{i=1}^n X_1 ^ i - X_2 ^ i \right|\end{equation*} \begin{equation*}\textbf{EUCLIDIAN DISTANCE} = \sqrt{ \sum_{i=1}^n \left( X_1 ^ i - X_2 ^ i \right) ^ 2 }\end{equation*} Where X1 and X2 are two different data points and 'i' traverse over all the features in the given dataset.   Variations in KNNVariations in KNN are possible on the basis of how neighboring points are going to vote. The weight of the vote of the testing point(s) is inversely proportional to its distance from the testing point. We can go either with uniform voting or with weighted voting. In case of weighted voting, the point nearer to the testing sample will have a larger say in the vote as compared to the point which is farther away from the testing point.  Feature Scaling before KNNIn KNN, we are looking for points which are closest to the testing point. In case we do not perform feature scaling, if we have value of one feature in thousands and value of other feature in smaller units, then the effect of first feature will completely overpower and dominate over the effect of second feature in the final output. So, it is of utmost importance to apply feature scaling before applying KNN so that all the features have equal contribution in the final predicted output for the given testing point.  KNN in SklearnWe will be applying KNN on Breast Cancer Dataset and use inbuilt KNN Classifier inside sklearn.<jupyter_code>from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
import matplotlib.pyplot as plt
cancer = datasets.load_breast_cancer()
cancer.feature_names
cancer.target
x_train, x_test, y_train, y_test = train_test_split(cancer.data, cancer.target, test_size = 0.2, random_state = 0)
clf = KNeighborsClassifier()
clf.fit(x_train, y_train)
clf.score(x_test, y_test)<jupyter_output><empty_output><jupyter_text>Default value of K (number of neighbors) is equal to 5 in Sklearn. By default, Sklearn implements Minkowski distance metric. General form of Minkowski distance is : \begin{equation*}\textbf{MINKOWSKI DISTANCE} = \left| \sum_{i=1}^n X_1 ^ i - X_2 ^ i \right| ^ p\end{equation*} If p = 1, that means we are using Manhattan Distance and if p = 2, that means we are using Euclidian Distance.  Cross Validation The best value of K is the one for which we get lowest error on testing data. So, what we can do is to repeatedly train our model using both training and testing data, for different values of parameter K and then finally choose value of K which results in minimum error. But in this process, we are using the testing data as a part of our training process to obtain the optimal value of K. Hence, this process is not to be used. On the other hand if we use only training data and tune the value of parameter K, it will lead to overfitting. This will result in lower value of error on training data, but comparatively higher value of error on the testing data.So, to obtain the optimal value of K, we use a method known as CROSS VALIDATION. Cross Validation basically means taking out the subset from the training data and not using this subset in the training process. This subset of training data is called the 'validation set'. There are various techniques available for cross validation, we will be using the most general one, known as K-fold cross validation. ![title](knn_crossval.png) In K fold cross validation, the training data is randomly split into K different samples(or folds). One of the sample is taken to be the validation set and the model is fitted on the remaining K-1 samples. The accuracy of the model is then computed. The same process is repeated K times, each time taking a different sample of points to be in the validation set. This results in K value for test error and these values are averaged out to obtain the overall result.Cross Validation is used to estimate the test error and generate more robust models.  Cross Validation in Sklearn<jupyter_code>x_axis = []
k_scores = []
for k in range(1,50, 2):
    x_axis.append(k)
    clf = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(clf, x_train, y_train, cv=10, scoring='accuracy')
    k_scores.append(scores.mean())
    
    #Printing values
    print("K = ",k)
    print("Scores : ")
    print(scores)
    print("Mean Score = ",scores.mean())
    print()
plt.plot(x_axis, k_scores)
plt.show()
optimal_k = x_axis[k_scores.index(max(k_scores))]
optimal_k<jupyter_output><empty_output><jupyter_text>By this way, we can choose the optimal value of K using cross validation. If the value of K is very less, for eg, say K=1, it will lead to overfitting and result in formation of complex decision boundaries. On the the hand, if the value of K is very high, we are basically underfitting and not actually taking class of neighbors into consideration. In this case, we predict the class of the testing sample from the majority class of the overall training data rather than from the majority class given by the neighbors. Lower values of K corresponds to low bias but high variance and result in jagged and complex decision boundaries, while higher value of K corresponds to lower variance but increased bias and leads to formation of smoother decision boundaries.K = 1             |   K = 20:-------------------------:|:-------------------------:![](knn_dec1.png)  |  ![](knn_dec20.png)  Implement KNN<jupyter_code>from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from collections import Counter
from sklearn.metrics import accuracy_score
cancer = datasets.load_breast_cancer()
X_train, X_test, Y_train, Y_test = train_test_split(cancer.data, cancer.target, test_size = 0.2, random_state = 0)
clf = KNeighborsClassifier(n_neighbors = 7)
clf.fit(X_train, Y_train)
clf.score(X_test,Y_test)
def train(x,y):
    return

def predict_one(x_train, y_train, x_test, k):
    distances = []
    for i in range(len(x_train)):
        distance = ((x_train[i,:] - x_test)**2).sum()
        distances.append([distance,i])
    distances = sorted(distances)
    targets = []
    for i in range(k):
        index_of_training_data = distances[i][1]
        targets.append(y_train[index_of_training_data])
    return Counter(targets).most_common(1)[0][0]
    
def predict(x_train, y_train, x_test_data, k):
    predictions = []
    for x_test in x_test_data:
        predictions.append(predict_one(x_train, y_train, x_test, k))
    return predictions
y_pred = predict(X_train, Y_train, X_test, 7)
accuracy_score(Y_test, y_pred)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.05800509504213208, 'fraction_numerical': 0.005780913188320596, 'mean_word_length': 4.48763440860215, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 0, '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': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '455427', 'license': 'Apache-2.0', 'n_tokens_mistral': 2745, 'n_tokens_neox': 2611, 'n_words': 1467, 'path': 'notes/15 KNN/KNN_MAIN.ipynb', 'repo_name': 'subhendu17620/ML-Coding-Ninjas', 'size': '10206'}