KNN Classification Algorithm

The KNN (K-Nearest Neighbor) algorithm assumes that items similar to each other are close to each other.

The KNN algorithm aims to predict the correct class for the test data by calculating the distance between the test data and all the learning points.

The KNN algorithm calculates the probability that the test data belongs to each of the "K" training data classes, then chooses the class with the highest probability.

Then it selects the number K of points closest to the test data.

In the KNN algorithm, the nearest neighbors are the data points with the shortest distance in feature space from the new data point.

The K represents the number of data points we consider in our algorithm implementation.

Accordingly, the KNN algorithm has two key factors:

- The distance metric.

- The K value.

Euclidean distance is the most popular distance measure used in the KNN algorithm.

# -*- coding: utf-8 -*-
"""
Created on Thu Jun 23 13:45:09 2022
 
@author: https://openclassrooms.com/fr/courses/4011851-initiez-vous-au-machine-learning/4022441-entrainez-votre-premier-k-nn
"""
import numpy as np
from matplotlib import pyplot as plt
from sklearn.datasets import fetch_openml
mnist = fetch_openml('mnist_784', version=1)
 
# Le dataset principal qui contient toutes les images
print (mnist.data.shape)
 
# Le vecteur d'annotations associé au dataset (nombre entre 0 et 9)
print (mnist.target.shape)
 
sample = np.random.randint(70000, size=5000)
data = mnist.data.values[sample]
target = mnist.target.values[sample]
 
from sklearn.model_selection import train_test_split
 
xtrain, xtest, ytrain, ytest = train_test_split(data, target, train_size=0.8)
 
from sklearn import neighbors
 
knn = neighbors.KNeighborsClassifier(n_neighbors=3)
knn.fit(xtrain, ytrain)
 
error = 1 - knn.score(xtest, ytest)
print('Erreur: %f' % error)
 
errors = []
for k in range(2,15):
    knn = neighbors.KNeighborsClassifier(k)
    errors.append(100*(1 - knn.fit(xtrain, ytrain).score(xtest, ytest)))
plt.plot(range(2,15), errors, 'o-')
plt.show()
 
# On récupère le classifieur le plus performant
knn = neighbors.KNeighborsClassifier(4)
knn.fit(xtrain, ytrain)
 
# On récupère les prédictions sur les données test
predicted = knn.predict(xtest)
 
# On redimensionne les données sous forme d'images
images = xtest.reshape((-1, 28, 28))
 
# On selectionne un echantillon de 12 images au hasard
select = np.random.randint(images.shape[0], size=12)
 
# On affiche les images avec la prédiction associée
fig,ax = plt.subplots(3,4)
 
for index, value in enumerate(select):
    plt.subplot(3,4,index+1)
    plt.axis('off')
    plt.imshow(images[value],cmap=plt.cm.gray_r,interpolation="nearest")
    plt.title('Predicted: {}'.format( predicted[value]) )
 
plt.show()
 
# on récupère les données mal prédites 
misclass = (ytest != predicted)
misclass_images = images[misclass,:,:]
misclass_predicted = predicted[misclass]
 
# on sélectionne un échantillon de ces images
select = np.random.randint(misclass_images.shape[0], size=12)
 
# on affiche les images et les prédictions (erronées) associées à ces images
for index, value in enumerate(select):
    plt.subplot(3,4,index+1)
    plt.axis('off')
    plt.imshow(misclass_images[value],cmap=plt.cm.gray_r,interpolation="nearest")
    plt.title('Predicted: {}'.format(misclass_predicted[value]) )
 
plt.show()