K-Nearest Neighbor Algorithm
The k-nearest neighbours (KNN) technique calculates the likelihood that a data point will belong to one group or another based on which group the data points closest to it do.
The k-nearest neighbour algorithm is an example of a supervised machine learning technique used to solve classification and regression problems. Its primary application, however, is in classification issues.
KNN is a slow, non-parametric learning method. It is known as a lazy learning algorithm or lazy learner because it does not perform any training when you provide the training data. During the training period, it does not perform any calculations and simply stores the data. A model is not created before a query is run on the dataset.
As a result, KNN is ideal for data mining. It is classified as a non-parametric method because it makes no assumptions about the underlying data distribution. KNN, in short, seeks to identify the group to which a data point belongs by examining the data points around it.
Think about the two groups, A and B. The algorithm examines the nearby data points' states to determine if a data point belongs to group A or group B. It is quite likely that the data point in question is in group A if the bulk of the data points is in group A, and vice versa. KNN also called the closest neighbour, is a technique for categorizing data points by comparing them to their nearest annotated data point.
K-NN classification should not be confused with K-means clustering. A supervised classification system called KNN sorts new data points according to the nearby ones. K-means clustering, on the other hand, divides data into a K number of clusters and is an unsupervised clustering algorithm.
Algorithm
The KNN algorithm is implemented using programming languages like Python and R. The KNN pseudocode is as follows:
1.Fill the data up
2.Select K value
3.For every informational point in the data:
3.1.All training data samples' Euclidean distance should be determined.
3.2.Place the distances on a list that is ordered, then sort it.
3.3.Pick the first K items in the sorted list.
3.4.Based on the vast majority of classes contained in the chosen points, label the test point.
4.End
Why KNN?
A crucial issue in data science and machine learning is classification. One of the earliest and most precise algorithms for pattern categorization and regression models is the KNN.
The following are some applications for the k-nearest neighbour algorithm:
Credit rating
Loan approval
Data preprocessing
Pattern recognition
KNN can be also used in recommendation systems because it can help find users with similar characteristics. It can, for example, be used in an online video streaming platform to recommend content that a user is more likely to watch based on what similar users watch.
For image classification, the KNN algorithm is used in computer vision. It's helpful in a variety of computer vision applications because it can group similar data points, such as grouping cats together and dogs in a different class.
Advantage
- It is simple to understand and implement.
- It applies to both classification and regression problems.
- It is ideal for non-linear data because it makes no assumptions about the underlying data.
- It is naturally capable of handling multi-class cases.
- With enough representative data, it can perform well.
Disadvantage
- Because it stores all of the training data, the associated computation cost is high.
- High memory storage is required.
- K's value must be determined.
- If N is large, prediction takes a long time.
- Sensitive to irrelevant characteristics
Example
Image classification
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import time
%matplotlib inline
from sklearn.datasets import load_digits
Load dataset
digits = load_digits()
digits.keys()
#dict_keys(['data', 'target', 'target_names', 'images', 'DESCR'])
digits.DESCR
Already processed images
digits.images[0]
'''array([[ 0., 0., 5., 13., 9., 1., 0., 0.],
[ 0., 0., 13., 15., 10., 15., 5., 0.],
[ 0., 3., 15., 2., 0., 11., 8., 0.],
[ 0., 4., 12., 0., 0., 8., 8., 0.],
[ 0., 5., 8., 0., 0., 9., 8., 0.],
[ 0., 4., 11., 0., 1., 12., 7., 0.],
[ 0., 2., 14., 5., 10., 12., 0., 0.],
[ 0., 0., 6., 13., 10., 0., 0., 0.]])'''
Predictors, independent variables, features
digits.data
'''array([[ 0., 0., 5., ..., 0., 0., 0.],
[ 0., 0., 0., ..., 10., 0., 0.],
[ 0., 0., 0., ..., 16., 9., 0.],
...,
[ 0., 0., 1., ..., 6., 0., 0.],
[ 0., 0., 2., ..., 12., 0., 0.],
[ 0., 0., 10., ..., 12., 1., 0.]])'''
Target variable, class, dependent variable
digits.target
#array([0, 1, 2, ..., 8, 9, 8])
These 1797 images (8 by 8 for a dimension of 64)
print('Image Data Shape', digits.images.shape)
print('Label Data Shape', digits.target.shape)
X = digits.images
plt.figure(figsize=(20,10))
columns = 5
for i in range(5):
plt.subplot(5 / columns + 1, columns, i + 1)
plt.imshow(X[i],cmap=plt.cm.gray_r,interpolation='nearest')
from sklearn.metrics import accuracy_score,confusion_matrix # metrics error
from sklearn.model_selection import train_test_split # resampling method
X = digits.data
y = digits.target
Since its a multi-class prediction, to prevent error, we need some library
from sklearn.multiclass import OneVsRestClassifier
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=0)
from sklearn.neighbors import KNeighborsClassifier
knn = OneVsRestClassifier(KNeighborsClassifier())
knn.fit(X_train,y_train)
Predict for one observation
knn.predict(X_test[0].reshape(1,-1))
Predict for multiple observations (images) at once
knn.predict(X_test[0:10])
//array([2, 8, 2, 6, 6, 7, 1, 9, 8, 5])
Make predictions on the entire test data
predictions = knn.predict(X_test)
%time
print('KNN Accuracy: %.3f' % accuracy_score(y_test,predictions))
//CPU times: user 0 ns, sys: 0 ns, total: 0 ns
//Wall time: 10 µs
//KNN Accuracy: 0.980
To create nice confusion metrics
import seaborn as sns
cm = confusion_matrix(y_test,predictions)
plt.figure(figsize=(9,9))
sns.heatmap(cm,annot=True, fmt='.3f', linewidths=.5, square=True,cmap='Blues_r')
plt.ylabel('Actual label')
plt.xlabel('Predicted label')
all_sample_title = 'Accuracy Score: {0}'.format(accuracy_score(y_test,predictions))
plt.title(all_sample_title,size=15)
#Text(0.5, 1.0, 'Accuracy Score: 0.98')
Conclusion
This article clearly explains the process of image classification using KNN in the machine learning model. To learn more about machine learning and how to make machine learning models, check out my machine learning series. If you have any questions or doubts, mention them in this article's comments section, and connect with me to learn more about machine learning.
Learning is an interesting habit..!
