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
- No assumptions about data
- Simple algorithm — easy to understand
- Can be used for classification and regression
- 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
- 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.
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 =
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)
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.
Given our confusion matrix, our model has an accuracy of 121/143 = 84.6%.
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.