K Nearest Neighbor Algorithm In Python

K Nearest Neighbor Algorithm In Python

K-Nearest Neighbors, or KNN for short, is one of the simplest machine learning algorithms and is used in a wide array of institutions. KNN is a non-parametric, lazy learning algorithm. When we say a technique is non-parametric, it means that it does not make any assumptions about the underlying data. In other words, it makes its selection based off of the proximity to other data points regardless of what feature the numerical values represent. Being a lazy learning algorithm implies that there is little to no training phase. Therefore, we can immediately classify new data points as they present themselves.

Some pros and cons of KNN

Pros:

• No assumptions about data
• Simple algorithm — easy to understand
• Can be used for classification and regression

Cons:

• High memory requirement — All of the training data must be present in memory in order to calculate the closest K neighbors
• Sensitive to irrelevant features
• Sensitive to the scale of the data since we’re computing the distance to the closest K points

Algorithm

1. Pick a value for K (i.e. 5).

2. Take the K nearest neighbors of the new data point according to their Euclidean distance.

3. Among these neighbors, count the number of data points in each category and assign the new data point to the category where you counted the most neighbors.

Code

Let’s take a look at how we could go about classifying data using the K-Nearest Neighbors algorithm in Python. For this tutorial, we’ll be using the breast cancer dataset from the sklearn.datasets module. We need to start by importing the proceeding libraries.

import numpy as np  
import pandas as pd  
from matplotlib import pyplot as plt  
from sklearn.datasets import load_breast_cancer  
from sklearn.metrics import confusion_matrix  
from sklearn.neighbors import KNeighborsClassifier  
from sklearn.model_selection import train_test_split  
import seaborn as sns  
sns.set()

The dataset classifies tumors into two categories (malignant and benign) and contains something like 30 features. In the real world, you’d look at the correlations and select a subset of features that plays the greatest role in determining whether a tumor is malignant or not. However, for the sake of simplicity, we’ll pick a couple at random. We must encode categorical data for it to be interpreted by the model (i.e. malignant = 0 and benign = 1).

breast_cancer = load_breast_cancer()  
X = pd.DataFrame(breast_cancer.data, columns=breast_cancer.feature_names)  
X = X[['mean area', 'mean compactness']]  
y = pd.Categorical.from_codes(breast_cancer.target, breast_cancer.target_names)  
y = pd.get_dummies(y, drop_first=True)

As mentioned in another tutorial, the point of building a model, is to classify new data with undefined labels. Therefore, we need to put aside data to verify whether our model does a good job at classifying the data. By default, train_test_split sets aside 25% of the samples in the original dataset for testing.

X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=1)

The sklearn library has provided a layer of abstraction on top of Python. Therefore, in order to make use of the KNN algorithm, it’s sufficient to create an instance of KNeighborsClassifier. By default, the KNeighborsClassifier looks for the 5 nearest neighbors. We must explicitly tell the classifier to use Euclidean distance for determining the proximity between neighboring points.

knn = KNeighborsClassifier(n_neighbors=5, metric='euclidean')  
knn.fit(X_train, y_train)

Using our newly trained model, we predict whether a tumor is benign or not given its mean compactness and area.

y_pred = knn.predict(X_test)

We visually compare the predictions made by our model with the samples inside the testing set.

sns.scatterplot(  
    x='mean area',  
    y='mean compactness',  
    hue='benign',  
    data=X_test.join(y_test, how='outer')  
)

Another way of evaluating our model is to compute the confusion matrix. The numbers on the diagonal of the confusion matrix correspond to correct predictions whereas the others imply false positives and false negatives.

confusion_matrix(y_test, y_pred)

Given our confusion matrix, our model has an accuracy of 121/143 = 84.6%.

Conclusion

The K Nearest Neighbors algorithm doesn’t require any additional training when new data becomes available. Rather it determines the K closest points according to some distance metric (the samples must reside in memory). Then, it looks at the target label for each of the neighbors and places the new found data point into the same category as the majority. Given that KNN computes distance, it’s imperative that we scale our data. In addition, since KNN disregards the underlying features, it’s our responsibility to filter out any features that are deemed irrelevant.