EE5934-Assignment 1 K- Nearest Neighbors Solved

n this assignment, you are required to implement a k-NN classifier to perform image classification on the USPS dataset. First, set up the environment and load the dataset as follows.
In [1]:
# Run this cell to set up the environment and data

import os
import sys
sys.path.append("../../homework/")

import matplotlib.pyplot as plt
import numpy as np

%load_ext autoreload
%autoreload 2

# Load the USPS data
usps_dir = "../data/usps.h5"
import h5py
with h5py.File(usps_dir, 'r') as hf:
        train = hf.get('train')
        trainX = train.get('data')[:]
        trainy = train.get('target')[:]
        test = hf.get('test')
        testX = test.get('data')[:]
        testy = test.get('target')[:]
        
# A small subset of USPS for you to run kNN on
# as kNN is a little bit slow
sub_trainX, sub_trainy = trainX[:5000], trainy[:5000]
sub_testX, sub_testy = testX[:1000], testy[:1000]

 
kNN
Next, implement the k-NN classifier which consists of the following two stages:

Training stage: k-NN classifier loads the training data and remembers it;
Testing stage: k-NN classifies every test image by comparing with all training images and transferring the labels of the k most similar training examples.
 
Training Stage:
In [2]:
from knn import KNN

classifier = KNN()
classifier.train(sub_trainX, sub_trainy)

 
Testing Stage:
Implement the k-NN classifier by completing the class method KNN.predict in homework/Assignment1/knn.py and evaluate the k-NN classification error.
In [3]:
y_pred = classifier.predict(sub_testX, k=1)

acc = np.sum(y_pred == sub_testy) / len(sub_testy)
print("Accuracy: ", acc)

 
Accuracy:  0.942

 
Cross Validation:
To find the best k, it is tempting to test different k on the test data. However, this leads to overfitting the test data.

Read Section 5.3.1 of the Deep Learning book for information about cross validation which is a technique for testing a model on unseen data.

Complete the cell below to carry out cross-validation as follows: split the training data and the corresponding labels into 5 subsets(folds), and then do a 5-fold cross validation to test different values of k.
In [4]:
# k_to_accuracies is a dictionary to hold the classification accuracies obtained when
# running cross-validation for different values of k. After running cross-validation,
# k_to_accuracies[k] would comprise 5 classification accuracy values found for the 
# particular value of k.
k_to_accuracies = {}

################################################################################
# TODO:     WRITE CODE FOR THE FOLLOWING                                       #
# Perform 5-fold cross validation to find the best value of k as follows: for  #
# each value of k being considered, run the k-NN algorithm 5 times where in    #
# each run, one fold is used as validation data while the other folds are      #
# used as training data. Store the accuracies for all folds for each value     #
# of k in the k_to_accuracies dictionary.                                      #
################################################################################
k_cands = [1,2,3,4,5,7,9,12,15,18,22,26,30]
trainX_folds = np.split(sub_trainX,5)
trainy_folds = np.split(sub_trainy,5)

for k in k_cands:
    accs = []
    for i in range(5):
        trainX_fold = trainX_folds.copy()
        trainy_fold = trainy_folds.copy()
        valX_fold = trainX_fold.pop(i)
        valy_fold = trainy_fold.pop(i)
        trainX_fold = np.concatenate(trainX_fold)
        trainy_fold = np.concatenate(trainy_fold)
        classifier.train(trainX_fold, trainy_fold)
        y_pred = classifier.predict(valX_fold, k)
        acc = np.sum(y_pred == valy_fold) / len(valy_fold)
        accs.append(acc)
    k_to_accuracies[k] = accs
################################################################################
#                                 END OF YOUR CODE                             #
################################################################################

# Print out the computed accuracies
for k in sorted(k_to_accuracies):
    for accuracy in k_to_accuracies[k]:
        print('k = %d, accuracy = %f' % (k, accuracy))

 
k = 1, accuracy = 0.960000
k = 1, accuracy = 0.975000
k = 1, accuracy = 0.950000
k = 1, accuracy = 0.953000
k = 1, accuracy = 0.961000
k = 2, accuracy = 0.957000
k = 2, accuracy = 0.975000
k = 2, accuracy = 0.947000
k = 2, accuracy = 0.937000
k = 2, accuracy = 0.948000
k = 3, accuracy = 0.957000
k = 3, accuracy = 0.973000
k = 3, accuracy = 0.950000
k = 3, accuracy = 0.954000
k = 3, accuracy = 0.958000
k = 4, accuracy = 0.951000
k = 4, accuracy = 0.972000
k = 4, accuracy = 0.946000
k = 4, accuracy = 0.948000
k = 4, accuracy = 0.952000
k = 5, accuracy = 0.955000
k = 5, accuracy = 0.969000
k = 5, accuracy = 0.946000
k = 5, accuracy = 0.950000
k = 5, accuracy = 0.954000
k = 7, accuracy = 0.950000
k = 7, accuracy = 0.967000
k = 7, accuracy = 0.943000
k = 7, accuracy = 0.938000
k = 7, accuracy = 0.953000
k = 9, accuracy = 0.947000
k = 9, accuracy = 0.964000
k = 9, accuracy = 0.938000
k = 9, accuracy = 0.936000
k = 9, accuracy = 0.943000
k = 12, accuracy = 0.940000
k = 12, accuracy = 0.960000
k = 12, accuracy = 0.931000
k = 12, accuracy = 0.932000
k = 12, accuracy = 0.936000
k = 15, accuracy = 0.931000
k = 15, accuracy = 0.953000
k = 15, accuracy = 0.920000
k = 15, accuracy = 0.926000
k = 15, accuracy = 0.935000
k = 18, accuracy = 0.933000
k = 18, accuracy = 0.953000
k = 18, accuracy = 0.919000
k = 18, accuracy = 0.926000
k = 18, accuracy = 0.933000
k = 22, accuracy = 0.926000
k = 22, accuracy = 0.946000
k = 22, accuracy = 0.915000
k = 22, accuracy = 0.917000
k = 22, accuracy = 0.928000
k = 26, accuracy = 0.923000
k = 26, accuracy = 0.942000
k = 26, accuracy = 0.908000
k = 26, accuracy = 0.910000
k = 26, accuracy = 0.927000
k = 30, accuracy = 0.918000
k = 30, accuracy = 0.938000
k = 30, accuracy = 0.904000
k = 30, accuracy = 0.906000
k = 30, accuracy = 0.920000

In [5]:
# visualize the results above.

################################################################################
# TODO:     WRITE CODE FOR THE FOLLOWING                                       #
# To better understand the influence of different k values,                    #
# show the above printed results in the scatter plot and then plot the trend   #
# with error bars that correspond to standard deviation.                       #
################################################################################
import matplotlib.pyplot as plt
# scatter plot
for k in k_cands:
    plt.scatter([k]*5,k_to_accuracies[k])

acc_means = []
acc_stds = []
for k in k_cands:
    acc_means.append(np.mean(k_to_accuracies[k]))
    acc_stds.append(np.std(k_to_accuracies[k]))
    
plt.errorbar(k_cands,acc_means,yerr=acc_stds)
################################################################################
#                                 END OF YOUR CODE                             #
################################################################################
plt.title('Cross-validation on k')
plt.xlabel('k')
plt.ylabel('Cross-validation accuracy')
plt.show()

 
 
In [6]:
################################################################################
# TODO:                                                                        #
# Based on the cross-validation results above, identify the best value for k   #
# and apply it to "best_k" below. Then, retrain the classifier using all the   #
# training data, and test it on the test data.                                 #
################################################################################
best_k = 1
################################################################################
#                                 END OF YOUR CODE                             #
################################################################################

classifier = KNN()
classifier.train(sub_trainX, sub_trainy)
y_test_pred = classifier.predict(sub_testX, k=best_k)

# Compute and display the accuracy
accuracy = np.sum(y_test_pred == sub_testy) / len(sub_testy)
print('accuracy: %f' % accuracy)

 
accuracy: 0.942000

 
Inline question:

In practice, why do we often choose an odd number for k? Give your answer below.
 
As we can see from figure-the Cross-validation on k, it has obvious vallys as k = 2,4,12. The ambiguity will happend when the test point has equal number voters of different classes. If we choose odd number, that case will not happen.