Week 4 – k Nearest Neighbours

Description

k-Nearest Neighbours is one of the most famous supervised classification and regression algorithms. The beauty of the algorithm is that we can observe it in our real life, i.e., our nature is to be close with people who are the most like us.

In this assignment you are required to prepare a Python class KNN which can be used by anyone for classification. The detailed instructions are given to you in this document.

Your task is to complete the code for the class KNN and its methods

You are provided with the following files:

1. week4.py

2. SampleTest.py

Note: These sample test cases are just for your reference.

SAMPLE TEST CASE Data

The training data is given in the form below (N=10, D=2)

The dataset here consists of N points each of D dimensions and the class that the data points belong to (x1 and x2 represent the dimensions, and y represents the class/category that the point belongs to). All dimensions are numerical and continuous in nature; hence you do not need to encode the data in any way.

Note that there may be more than 2 classes. Do not assume that number of classes will be 2 always!

Important Points:

1. Please do not make changes to the function definitions that are provided to you. Use the skeleton as it has been given. Also do not make changes to the sample test file provided to you. Run it as it is.

2. You are free to write any helper functions that can be called in any of these predefined functions given to you. Helper functions must be only in the file named ‘YOUR_SRN.py’.

3. Note that the code is for classification only.

4. Your code will be auto evaluated by our testing script and our dataset and test cases will not be revealed. Please ensure you take care of all edge cases!

5. The experiment is subject to zero tolerance for plagiarism. Your code will be tested for plagiarism against every code of all the sections and if found plagiarized both the receiver and provider will get zero marks without any scope for explanation.

6. Kindly do not change variable names or use any other techniques to escape from plagiarism, as the plagiarism checker is able to catch such plagiarism

7. Hidden test cases will not be revealed post evaluation.

8. The distance metric used in this implementation is the Minkowski Distance (the parameter ‘p’ of the Minkowski Distance will be supplied as input to the KNN class constructor).

8. In case of any ambiguities during choosing the class from the K-nearest neighbours, choose the class which is lexicographically smallest.

8. All the classes (targets for classification) will be integer-valued

8. In case the ‘weighted’ flag is set to True, you are required to use the reciprocal of the distance between the point and the query as the weight of that point. Mathematically:

1

⁼(,)

week4 .py

^✓ You are provided with structure of class KNN.

^✓ The class KNN contains one constructor and five methods. ^✓ Your task is to write code for the four of these five methods.

def init (self, k_neigh, weighted=False, p=2)

This is the constructor of the class KNN

You are not required to edit this method. However, it is necessary to understand the initialization to implement other methods.

parameters: k_neigh: int , weighted= Boolean , p= int/float

k_neigh: defines the k value for the algorithm

weighted: if True, weighted kNN algorithm should be used else vanilla kNN should be used p :defines the parameter of Minkowski distance (when p==2 ,Euclidean)

def fit(self, data, target)

This method has already been implemented, and you are not required to make any changes to this function.

if import error occurs due to any libraries that is mentioned in the skeleton code try:

python3.7 SampleTest.py –SRN YOUR_SRN