<jupyter_start><jupyter_text>Acknowledgment     This project was one of the assignments of Ecornell Machine learning course.         About this ProjectIn this project you will implement k-NN to classify images of faces. You will use the NumPy library to implement functions that will find nearest neighbors, calculate absolute loss, perform k-NN classification on a data set, and calculate the accuracy of your classifier.EvaluationThis project must be successfully completed and submitted in order to receive credit for this course. Your score on this project will be included in your final grade calculation.    You are expected to write code where you see  YOUR CODE HERE within the cells of this notebook. Not all cells will be graded; code input cells followed by cells marked with Autograder test cell will be graded. Upon submitting your work, the code you write at these designated positions will be assessed using an "autograder" that will run all test cells to assess your code. You will receive feedback from the autograder that will identify any errors in your code. Use this feedback to improve your code if you need to resubmit. Be sure not to change the names of any provided functions, classes, or variables within the existing code cells, as this will interfere with the autograder. Also, remember to execute all code cells sequentially, not just those you’ve edited, to ensure your code runs properly.    You can resubmit your work as many times as necessary before the submission deadline. If you experience difficulty or have questions about this exercise, use the Q&A discussion board to engage with your peers or seek assistance from the instructor.Before starting your work, please review eCornell's policy regarding plagiarism (the presentation of someone else's work as your own without source credit).Submit Code for Autograder FeedbackOnce you have completed your work on this notebook, you will submit your code for autograder review. Follow these steps:  Save your notebook.  Mark as Completed — In the blue menu bar along the top of this code exercise window, you’ll see a menu item called Education. In the Education menu, click Mark as Completed to submit your code for autograder/instructor review. This process will take a moment and a progress bar will show you the status of your submission.	Review your results — Once your work is marked as complete, the results of the autograder will automatically be presented in a new tab within the code exercise window. You can click on the assessment name in this feedback window to see more details regarding specific feedback/errors in your code submission.  Repeat, if necessary — The Jupyter notebook will always remain accessible in the first tabbed window of the exercise. To reattempt the work, you will first need to click Mark as Uncompleted in the Education menu and then proceed to make edits to the notebook. Once you are ready to resubmit, follow steps one through three. You can repeat this procedure as many times as necessary. Import LibrariesBefore you get started, you need to import a few libraries. You can do this by executing the following code. Remember, run code in a cell by selecting the cell, holding the shift key, and pressing enter/return.<jupyter_code>import numpy as np
from scipy.stats import mode
import sys
%matplotlib notebook
import matplotlib
import matplotlib.pyplot as plt
from scipy.io import loadmat
import time
from helper import *

print('You\'re running python %s' % sys.version.split(' ')[0])<jupyter_output>You're running python 3.7.6<jupyter_text>k-Nearest Neighbors Implementation in PythonThe goal of implementing your $k$-NN classifier is to build a classifier for face recognition. We have obtained some data, images of faces, for testing your code. The data resides in the file faces.mat, which holds the dataset for our exercises below. We will refer to the training vectors as xTr with labels yTr. Our testing vectors are xTe with labels yTe.As a reminder, to predict the label or class of an image in xTe, we will look for the k-nearest neighbors in xTr and predict a label based on their labels in yTr. For evaluation, we will compare these labels against the true labels provided in yTe.  Visualizing the DataLet us take a look at the data. The following script will take the first ten training images from the face dataset and visualize them. Run the code cell to see the visualized data.<jupyter_code>xTr,yTr,xTe,yTe=loaddata("faces.mat")

plt.figure(figsize=(11,8))
plotfaces(xTr[:9, :])<jupyter_output><empty_output><jupyter_text>Implement k-NN for Facial RecognitionThe following four project parts will step you through implementing each function necessary to build your facial recognition system. Part 1: Implement findknn [Graded]Implement the function findknn, which should find the $k$ nearest neighbors of a set of vectors within a given training data set. The call of: [I,D]=findknn(xTr,xTe,k); should result in two matrices $I$ and $D$, both of dimensions $k\times n$, where $n$ is the number of input vectors in xTe. The matrix $I(i,j)$ is the index of the $i^{th}$ nearest neighbor of the vector $xTe(j,:)$.So, for example, if we set i=I(1,3), then xTr(i,:) is the first nearest neighbor of vector xTe(3,:). The second matrix $D$ returns the corresponding distances. So $D(i,j)$ is the distance of $xTe(j,:)$ to its $i^{th}$ nearest neighbor.You can use the function l2distance from the previous exercise (which is readily available to you.) You may find np.argsort(D,0) and np.sort(D,0) useful when implementing findknn.<jupyter_code>def findknn(xTr,xTe,k):
    """
    function [indices,dists]=findknn(xTr,xTe,k);
    
    Finds the k nearest neighbors of xTe in xTr.
    
    Input:
    xTr = nxd input matrix with n row-vectors of dimensionality d
    xTe = mxd input matrix with m row-vectors of dimensionality d
    k = number of nearest neighbors to be found
    
    Output:
    indices = kxm matrix, where indices(i,j) is the i^th nearest neighbor of xTe(j,:)
    dists = Euclidean distances to the respective nearest neighbors
    """
    n,d1 = xTr.shape
    m,d2 = xTe.shape
    
    dist = l2distance(xTr,xTe)
    dist_sorted = np.sort(dist,axis=0)
    D = dist_sorted[0:k,:]
    i = np.argsort(dist,0)
    I = i[0:k,:]
    return (I,D)
# Run this self-test cell to check your code

def knn_0():
    # checking output types
    xTr = np.random.rand(500,10) # defininng 500 training data points 
    xTe = np.random.rand(300,10) # defining 300 testing data points
    Ig,Dg = findknn(xTr,xTe,5) # compute indices and distances to the 5- nearest neighbors 
    # check if Ig is a matrix of integers, Dg a matrix of floats
    test=(type(Ig)==np.ndarray)  & (type(Ig)==np.ndarray) & ((type(Dg[0][0])==np.float64) or (type(Dg[0][0])==np.float32)) & ((type(Dg[0][0])==np.float64) or (type(Dg[0][0])==np.float32))
    return test

def knn_1():
    # checking output dimensions
    xTr = np.random.rand(500,10) # defininng 500 training data points 
    xTe = np.random.rand(300,10) # defining 300 testing data points
    Ig,Dg = findknn(xTr,xTe,5) # compute indices and distances to the 5- nearest neighbors 
    test=(Ig.shape==(5,300)) & (Dg.shape==(5,300)) # test if output dimensions are correct
    return test

def knn_2():
    # checking 1-NN accuracy
    xTr = np.random.rand(500,10) # defininng 500 training data points 
    xTe = np.random.rand(300,10) # defining 300 testing data points
    Ig,Dg = findknn_grader(xTr,xTe,1) # compute indices and distances to the nearest neighbors with *our* code
    Is,Ds = findknn(xTr,xTe,1) # Use *your* code
    test = np.linalg.norm(Ig - Is) + np.linalg.norm(Dg - Ds) # compare results
    return test<1e-5 

def knn_3():
    # checking 3-NN accuracy
    xTr = np.random.rand(500,10) # defininng 500 training data points 
    xTe = np.random.rand(300,10) # defining 300 testing data points
    Ig,Dg = findknn_grader(xTr,xTe,3) # compute indices and distances to the 3-nearest neighbors with *our* code
    Is,Ds = findknn(xTr,xTe,3) # Use *your* code
    test = np.linalg.norm(Ig - Is) + np.linalg.norm(Dg - Ds) # compare results
    return test<1e-5 

runtest(knn_0,'knn_0')
runtest(knn_1,'knn_1')
runtest(knn_2,'knn_2')
runtest(knn_3,'knn_3')
# Autograder test cell - worth 1 point
# runs knn_0
# Autograder test cell - worth 1 point
# runs knn_1
# Autograder test cell - worth 1 point
# runs knn_2
# Autograder test cell - worth 1 point
# runs knn_3<jupyter_output><empty_output><jupyter_text>The following demo samples random points in 2D. If your findknn function is correctly implemented, you should be able to click anywhere on the plot to add a test point. The function should then draw direct connections from your test point to the k  nearest neighbors. Verify manually if your code is correct.<jupyter_code>%matplotlib notebook
visualize_knn_2D(findknn)<jupyter_output><empty_output><jupyter_text>We can visualize the k=3 nearest training neighbors of some of the test points (Click on the image to cycle through different test points).<jupyter_code>%matplotlib notebook
visualize_knn_images(findknn, imageType='faces')<jupyter_output><empty_output><jupyter_text>Part 2: Implement accuracy [Graded]The function accuracy should compute the accuracy of a classifier. The call of:  result=accuracy(truth,preds);should output the accuracy in variable result. The input variables truth and preds should contain vectors of true and predicted labels respectively.For example, the call:>> accuracy([1 2 1 2],[1 2 1 1])should return an accuracy of 0.75. Here, the true labels are 1,2,1,2 and the predicted labels are 1,2,1,1. So the first three examples are classified correctly, and the last one is wrong --- 75% accuracy.You may find the following functions helpful: flatten(), np.mean() and np.abs().<jupyter_code>def accuracy(truth,preds):
    """
    function output=accuracy(truth,preds)         
    Analyzes the accuracy of a prediction against the ground truth
    
    Input:
    truth = n-dimensional vector of true class labels
    preds = n-dimensional vector of predictions
    
    Output:
    accuracy = scalar (percent of predictions that are correct)
    """
    
    truth = truth.flatten()
    preds = preds.flatten()
    a1 = np.abs(truth - preds)
    a1 = (a1==0)
    accuracy = np.mean(a1)
    return accuracy
# Run this self-test cell to check your code

def accuracy_test0():
    # check type of output is correct
    truth = np.array([1, 2, 3, 4])
    preds = np.array([1, 2, 3, 0])
    return type(accuracy(truth,preds))==np.float64

def accuracy_test1():
    # accuracy check on 4 sample data
    truth = np.array([1, 2, 3, 4]) # define truth 
    preds = np.array([1, 2, 3, 0]) # define preds
    return abs(accuracy(truth,preds) - 0.75)<1e-10 # check if accuracy is correct

def accuracy_test2():
    # accuracy check on random samples
    p=np.random.rand(1,1000); # define random string of [0,1] as truth
    truth=np.int16(p>0.5)
    p2=p+np.random.randn(1,1000)*0.1; # define very similar version as preds
    preds=np.int16(p2>0.5)
    return abs(accuracy(truth,preds) - accuracy_grader(truth,preds))<1e-10 # check if accuracy is correct

runtest(accuracy_test0,'accuracy_test0 (types)')
runtest(accuracy_test1,'accuracy_test1 (exactness)')
runtest(accuracy_test2,'accuracy_test2 (exactness)')
# Autograder test cell - worth 1 point
# runs accuracy_test0
# Autograder test cell - worth 1 point
# runs accuracy_test1
# Autograder test cell - worth 1 point
# runs accuracy_test2<jupyter_output><empty_output><jupyter_text>Part 3: Implement knnclassifier [Graded]Implement the function knnclassifier, which should perform $k$ nearest neighbor classification on a given test data set. The call:preds=knnclassifier(xTr,yTr,xTe,k)should output the predictions for the data in xTe i.e. preds[i] will contain the prediction for xTe[i,:].You may find it helpful to use flatten() in the implementation of this function. It will also be useful to  refer back to the mode function you implemented in Additional NumPy Exercises.<jupyter_code>def knnclassifier(xTr,yTr,xTe,k):
    """
    function preds=knnclassifier(xTr,yTr,xTe,k);
    
    k-nn classifier 
    
    Input:
    xTr = nxd input matrix with n row-vectors of dimensionality d
    xTe = mxd input matrix with m row-vectors of dimensionality d
    k = number of nearest neighbors to be found
    
    Output:
    
    preds = predicted labels, ie preds(i) is the predicted label of xTe(i,:)
    """
    # fix array shapes
    yTr = yTr.flatten()

    I, D = findknn(xTr,xTe,k)
    a,b = I.shape
    I2 = I.flatten()
    pred1 = yTr[I2]
    pred1 = pred1.reshape(a,b)
    pred = mode(pred1)[0][0]
    return pred

# Run this self-test cell to check your code

def knn_classifier_test0():
    # test if output is a numpy array, and of the right length
    X = np.array([[1,0,0,1],[0,1,0,1]]).T
    y = np.array([1,1,2,2])
    preds=knnclassifier(X,y,X,1)
    return type(preds)==np.ndarray and preds.shape==(4,)


def knn_classifier_test1():
    X = np.array([[1,0,0,1],[0,1,0,1]]).T
    y = np.array([1,1,2,2])
    np.testing.assert_allclose(knnclassifier(X,y,X,1),y)
    return np.testing.assert_allclose


def knn_classifier_test2():
    X = np.array([[1,0,0,1],[0,1,0,1]]).T
    y = np.array([1,1,2,2])
    y2 = np.array([2,2,1,1])
    return np.array_equal(knnclassifier(X,y,X,3),y2)

def knn_classifier_test3():
    X = np.array([[-4,-3,-2,2,3,4]]).T
    y = np.array([1,1,1,2,2,2])
    X2 = np.array([[-1,1]]).T
    y2 = np.array([1,2])
    return np.array_equal(knnclassifier(X,y,X2,2),y2)

def knn_classifier_test4():
    X = np.array([[-4,-3,-2,2,3,4]]).T
    y = np.array([1,1,1,2,2,2])
    X2 = np.array([[0,1]]).T
    y2 = np.array([1,2])
    y3 = np.array([2,2])
    return np.array_equal(knnclassifier(X,y,X2,2),y2) or np.array_equal(knnclassifier(X,y,X2,2),y3)

def knn_classifier_test5():
    X = np.random.rand(4,4)
    y = np.array([1,2,2,2])
    return accuracy(knnclassifier(X,y,X,1),y) == 1

def knn_classifier_test6():
    X = np.random.rand(4,4)
    y = np.array([1,2,1,2])
    return accuracy(knnclassifier(X,y,X,1),y) == 1

def knn_classifier_test7():
    X = np.random.rand(10,100)
    y = np.round(np.random.rand(10)).astype('int')
    return accuracy(knnclassifier(X,y,X,1),y) == 1

runtest(knn_classifier_test1,'knn_classifier_test1')
runtest(knn_classifier_test2,'knn_classifier_test2')
runtest(knn_classifier_test3,'knn_classifier_test3')
runtest(knn_classifier_test4,'knn_classifier_test4')
runtest(knn_classifier_test5,'knn_classifier_test5')
runtest(knn_classifier_test6,'knn_classifier_test6')
runtest(knn_classifier_test7,'knn_classifier_test7')
# Autograder test cell - worth 1 point
# runs knn_classifier_test1
# Autograder test cell - worth 1 point
# runs knn_classifier_test2
# Autograder test cell - worth 1 point
# runs knn_classifier_test3
# Autograder test cell - worth 1 point
# runs knn_classifier_test4
# Autograder test cell - worth 1 point
# runs knn_classifier_test5
# Autograder test cell - worth 1 point
# runs knn_classifier_test6
# Autograder test cell - worth 1 point
# runs knn_classifier_test7<jupyter_output><empty_output><jupyter_text>You can compute the actual classification error on the test set by calling>> accuracy(yTe,knnclassifier(xTr,yTr,xTe,3)) Part 4: Calculate AccuracyThe following script runs your $k$-nearest neighbor classifier over the faces and digits data set. The faces data set has $40$ classes and the digits data set has $10$. What classification accuracy would you expect from a random classifier?<jupyter_code>print("Face Recognition: (1-nn)")
xTr,yTr,xTe,yTe=loaddata("faces.mat") # load the data
t0 = time.time()
preds = knnclassifier(xTr,yTr,xTe,1)
result=accuracy(yTe,preds)
t1 = time.time()
print("You obtained %.2f%% classification acccuracy in %.4f seconds\n" % (result*100.0,t1-t0))<jupyter_output>Face Recognition: (1-nn)
You obtained 95.83% classification acccuracy in 0.0158 seconds<jupyter_text>k-NN Boundary VisualizationTo help give you a visual understanding of how the k-NN boundary is affected by $k$ and the specific dataset, feel free to play around with the visualization below.Instructions:    Run the cell below.    Click anywhere in the graph to add a negative class point.    Hold down 'p' key and click anywhere in the graph to add a positive class point.    To increase $k$, hold down 'h' key and click anywhere in the graph.<jupyter_code>%matplotlib notebook
visualize_knn_boundary(knnclassifier)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09273486177484726, 'fraction_numerical': 0.02625370516000242, 'mean_word_length': 4.392041748206132, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '375466', 'license': 'MIT', 'n_tokens_mistral': 5477, 'n_tokens_neox': 5259, 'n_words': 1971, 'path': 'Facial_Recognition_System.ipynb', 'repo_name': 'prashanta99/FaceDetection', 'size': '16531'}