# Assignment 1: Part 1 - kNN Basics
In this assignment you will implement a kNN model from scratch. The objectives are:
- To familiarise yourself with Python and some aspects of Numpy if you are not accustomed to it
- To gain some hands-on experience with a simple machine learning model
- Classify a set of test data



```python
import numpy as np
from sklearn.datasets import make_classification 
from sklearn.model_selection import train_test_split
import matplotlib.pyplot as plt
```

# Data exploration
We can use sklearn to generate random data. For now we will classify data with two input features that may belong to one of two classes.
The full dataset is split 50/50 into a training and test set.
For now we will not do any pre-processing on the data.

At a later stage we will look at real-world datasets and some of the problems that might be experienced with real-world data.


```python
X, Y = make_classification(n_samples=500, n_features=2, n_redundant=0, n_informative=1, n_classes=2, n_clusters_per_class=1)
X_train, X_test, Y_train, Y_test = train_test_split(X, Y, test_size=0.5)
```

It is very useful to know the shape of the data you are working with. Very often it serves as a quick way to debug parts of your code. If you are working with Python lists you can use the `len()` function, but you would have to use it for each dimension of your data. e.g.\
`dim1 = len(my_list)` ,
`dim2 = len(my_list[0])` ,
`dim3 = len(my_list([0][0])`\
Numpy provides easy access to the shape of n-dimensional arrays `ndarrays` e.g. \
`my_array.shape => (dim1, dim2, dim3)` \
You will notice that I have provided clues about the shape of the data for each function where necessary.

You can use the cell block below to examine the data however you wish. It will not be graded. I suggest confirming that the data shapes make sense. For example the data matix $\mathbf{X}$ would be given by
\begin{align}
\mathbf{X} &= \begin{bmatrix}
			\mathbf{x_1}^T \\
			\mathbf{x_2}^T \\
			\vdots \\
			\mathbf{x_n}^T
		\end{bmatrix}
		=
		\begin{bmatrix}
			x_{1}^{[1]} & x_{2}^{[1]}  & \dots  & x_{m}^{[1]} \\
			x_{1}^{[2]} & x_{2}^{[2]}  & \dots  & x_{m}^{[2]} \\
			\vdots & \vdots & \ddots & \vdots \\
			x_{1}^{[n]} & x_{2}^{[n]}  & \dots  & x_{m}^{[n]}
		\end{bmatrix}
\end{align}
Where there are $n$ number of examples and $m$ number of features


```python
# You can use this block to play around. n = number of examples, m = number of features => each row is an example
# Just make sure not to change the generated data as these are global variables.
# You can re-run the data generating block to create new data
Y_train.shape
```




    (250,)



# Data Visualisation
It's useful to visualise the data. Here it is easy because we only have two features. High-dimensional inputs need additional tools in order to help visualise them. 


```python
fig = plt.figure(figsize=(6,6))
plt.scatter(X_train[:, 0], X_train[:, 1], c=Y_train, cmap='cool')
plt.ylabel('$x_2$')
plt.xlabel('$x_1$')
plt.show()
```


```python
# You can use this block play around 
# notation: superscript = example, subscript = feature 
x_a = [0, 1]
x_b = [0, 5]
```

# Task 1: Distance Function
Your first task is to develop a function that takes in two feature vectors (numpy arrays), $\mathbf{x}^{[a]}$, and $\mathbf{x}^{[b]}$ and ouputs the Euclidean distance between them

$$
d\left(\mathbf{x}^{[a]}, \mathbf{x}^{[b]}\right) = \sqrt{\sum\limits_{j=1}^m\left(x_j^{[a]} - x_j^{[b]}\right)^2}
$$

Some helpful functions:\
`np.sqrt()`, `np.sum()` and `np.pow()`


```python
def euclideanDistance(x_a, x_b):
    """
    Calculates the Euclidean distance between two vectors
    
    Arguments:
        x_a (array): shape [m_features, ] a single vector a
        x_b (array): shape [m_features, ] a single vector b
    
    Returns:
        distance (float): distance between vectors x_a and x_b
    """
    
    # YOUR CODE HERE
    # Each x_a, x_b are examples in D. They each have m features 
    # Steps: 
    # 1. find the difference between each corresponding element in x_a and x_b. Store in array
    # 2. square each of these values 
    # 3. Sum all these elements together. And take the root
    
    distance = np.sum((x_a - x_b)**2)**(1/2)
    
    #raise NotImplementedError()
    return distance
```


```python
# Free cell
D = np.array([[1, 4], [2, 5], [2, 2], [3, 1], [4, 3], [5, 1]])
xt = np.array([3, 2])

dist_list = []

for example in D:
    dist_list.append(euclideanDistance(example, xt))

print(dist_list)
```

    [2.8284271247461903, 3.1622776601683795, 1.0, 1.0, 1.4142135623730951, 2.23606797749979]



```python
# The following tests are visible to you
x1_grade = np.array((-1.0, 2.0))
x2_grade = np.array((2.5, -2.0))
assert euclideanDistance(x1_grade, x2_grade) == 5.315072906367325

x1_grade = np.array((1.0, -1.0, 0))
x2_grade = np.array((-2.0, 2.6, 1.8))
assert euclideanDistance(x1_grade, x2_grade) == 5.019960159204453

```

# Task 2: Calculate list of distances
For the kNN algorithm you need to generate the distances between a single test example and all possible training examples.To do this you will need to write a function that takes in a test example and a list of examples, calculates the distance between the test example and each of the other example, and outputs a list of distances. The distances should be in the correct order as they correspond to a specific training example. To give you an idea what the output should be:

$$
\mathcal{distance\_list} = \left[d\left(\mathbf{x}^{[t]}, \mathbf{x}^{[1]}\right), \ldots, d\left(\mathbf{x}^{[t]}, \mathbf{x}^{[n]}\right)\right]
$$

where $d\left(\mathbf{x}^{[t]}, \mathbf{x}^{[1]}\right)$ is the distance function from task 1

The distances must be stored in a Python list, not a numpy array.

Some helpful functions:\
Python's built-in `append()` function


```python
def calculateDistances(x_test, X_in):
    """
    Calculates the distance between a single test example, x_test,
    and a list of examples X_in. 
    
    Args:
        x_test (array): shape [n_features,] a single test example
        X_in (array): shape [n_samples, n_features] a list of examples to compare against.
    
    Returns:
        distance_list (list of float): The list containing the distances       
    """
    
    distance_list = []
    for example in X_in:
        distance_list.append(euclideanDistance(example, x_test))
    return distance_list
```


```python
# Free cell
D = np.array([[1, 4], [2, 5], [2, 2], [3, 1], [4, 3], [5, 1]])
xt = np.array([3, 2])

dist_list = calculateDistances(xt, D)

print(dist_list)
```

    [2.8284271247461903, 3.1622776601683795, 1.0, 1.0, 1.4142135623730951, 2.23606797749979]



```python
# The following tests are visible to you
x1_grade = np.array((1.0, -1.0))
x2_grade = np.array([(2.0, -1.0),
              (-1.5, 2.5),
              (-2, -2),
              (0, 0)])

assert calculateDistances(x1_grade, x2_grade) == [1.0, 4.301162633521313, 3.1622776601683795, 1.4142135623730951]

```

# Task 3: Determine k Nearest Neighbours
This task is broken into subtasks that will create a set of the k nearest neighbours to a single test example.
$$
\mathcal{D}_k = \{(\mathbf{x}^{[i]}, \mathbf{y}^{[i]}), \ldots, (\mathbf{x}^{[k]}, \mathbf{y}^{[k]})\}
$$
## Task 3.1 Sorting the distances and returning indices 
To find the k nearest neighbours you first need to sort the list of distances in ascending order. For a naive kNN we don't care about the actual distances, so we only need to know which examples are responsible for the k smallest distances. We can do this by sorting the list of distances while keeping track of the corresponding indices so that we can pull the examples from the original training data at those indices. 

Your function must return a numpy array (it will make indexing the original dataset easier compared to python lists)

Some helpful functions:\
`np.argsort()`


```python
def kNearestIndices(distance_list, k):
    """
    Determines the indices of the k nearest neighbours
    
    Arguments:
        distance_list (list of float): list of distances between a test point 
            and every training example
        k (int): the number of nearest neighbours to consider
    
    Returns:
        k_nearest_indices (array of int): shape [k,] array of the indices 
            corresponding to the k nearest neighbours
    """
    
    # YOUR CODE HERE
    k_nearest_indices = np.array( np.argsort(distance_list)[:k] )
    return k_nearest_indices
```


```python
# Free cell
D = np.array([[1, 4], [2, 5], [2, 2], [3, 1], [4, 3], [5, 1]])
xt = np.array([3, 2])

dl = calculateDistances(xt, D)

kNearestIndices(dl, 3) + 1
```




    array([3, 4, 5])




```python
# The following tests are visible to you
distance_list_grade = [5.0, 3.5, 2.5, 1.0]
k_grade = 3
assert kNearestIndices(distance_list_grade, k_grade).tolist() == [3, 2, 1]

distance_list_grade = [5.0, 3.0, 3.5, 1.0, 10.0]
k_grade = 4
assert kNearestIndices(distance_list_grade, k_grade).tolist() == [3, 1, 2, 0]


```

## Task 3.2: Create $\mathcal{D}_k$
Now write a function that samples the original training set to produce the set of k nearest neighbours. 
For now the function should return the `X_k` and `Y_k` data matrices seperately as indicated.


```python
def kNearestNeighbours(k_nearest_indices, X_in, Y_in):
    """
    Creates the dataset of k nearest neighbours
    
    Arguments:
        k_nearest_indices (array of int): shape [k,] array of the indices 
            corresponding to the k nearest neighbours
        X_in (array): shape [n_examples, n_features] the example data matrix to sample from
        Y_in (array): shape [n_examples, ] the label data matrix to sample from
    
    Returns:
        X_k (array): shape [k, n_features] the k nearest examples
        Y_k (array): shape [k, ] the labels corresponding to the k nearest examples
    """
    
    X_k = []
    Y_k = []

    for i in k_nearest_indices:
        X_k.append(X_in[i])
        Y_k.append(Y_in[i])
        
    X_k = np.array(X_k)
    Y_k = np.array(Y_k)
    return X_k, Y_k
```


```python
# Free cell
D = np.array([([1, 4], 1), ([2, 5], 1), ([2, 2], 1), ([3, 1], 0), ([4, 3], 0), ([5, 1], 0)])
xt = np.array([3, 2])

X = []
Y = []
for p in D:
    X.append(p[0])
    Y.append(p[1])
X = np.array(X)
Y = np.array(Y)


dl = calculateDistances(xt, X)
kNN = kNearestIndices(dl, 3) 

kNearestNeighbours(kNN, X, Y)
```




    (array([[2, 2],
            [3, 1],
            [4, 3]]),
     array([1, 0, 0]))




```python
# The following tests are visible to you

# dummy dataset for autograding purposes
X_train_grade = np.array([[1, 1],
                       [0, 2],
                       [1, 2],
                       [2, 2],
                       [10, 10],
                       [5, 10],
                       [6, 6],
                       [2, 3]])
Y_train_grade = np.array([0, 0, 0, 0, 1, 1, 1, 0])

X_k_grade, Y_k_grade = kNearestNeighbours([0, 1, 3], X_train_grade, Y_train_grade)
assert  np.equal(X_k_grade, np.array([[1, 1],[0, 2],[2, 2]])).all()
assert  np.equal(Y_k_grade, np.array([0, 0, 0])).all()

```

# Task 4: Predict Class
You can now write a function to predict the class of a test example by choosing the class the appears most frequently in ground truth labels for the k nearest neighbours i.e. the mode.
$$
h(\mathbf{x}^{[t]}) = mode(\{y^{[i]}, \ldots, y^{[k]}\})
$$

Some helpful functions:\
`mode()` function from scipy. 


```python
from scipy.stats import mode
def predict(x_test, X_in, Y_in, k):
    """
    Predicts the class of a single test example
    
    Arguments:
        x_test (array): shape [n_features, ] the test example to classify
        X_in (array): shape [n_input_examples, n_features] the example data matrix to sample from
        Y_in (array): shape [n_input_labels, ] the label data matrix to sample from
    
    Returns:
        prediction (array): shape [1,] the number corresponding to the class 
    """
    
    distance_list = calculateDistances(x_test, X_in)
    kNN_indices = kNearestIndices(distance_list, k)
    X_k, Y_k = kNearestNeighbours(kNN_indices, X_in, Y_in)
    prediction =  mode(Y_k, axis=None)[0]

    return prediction
```


```python
# Free cell
from scipy.stats import mode
k = 3
D = np.array([([1, 4], 1), ([2, 5], 1), ([2, 2], 1), ([3, 1], 0), ([4, 3], 0), ([5, 1], 0)])
xt = np.array([3, 2])

X = []
Y = []
for p in D:
    X.append(p[0])
    Y.append(p[1])
X = np.array(X)
Y = np.array(Y)


dl = calculateDistances(xt, X)
kNI = kNearestIndices(dl, k) 

kNN = kNearestNeighbours(kNI, X, Y)
Dk = list(zip(kNN[0].tolist(), kNN[1].tolist()))

p = predict(xt, X, Y, k)
print( p == 0)
print(type(p))
```

    [ True]
    <class 'numpy.ndarray'>



```python
# The following tests are visible to you

# dummy dataset for autograding purposes
X_train_grade = np.array([[1, 1],
                       [0, 2],
                       [2, 1],
                       [1, 3],
                       [10, 10],
                       [5, 10],
                       [6, 8],
                       [2, 3]])
Y_train_grade = np.array([0, 0, 0, 0, 1, 1, 1, 0])

x1_grade = np.array([1, 2])
k_grade = 3
assert predict(x1_grade, X_train_grade, Y_train_grade, k_grade) == 0

x1_grade = np.array([6, 9])
k_grade = 2
assert predict(x1_grade, X_train_grade, Y_train_grade, k_grade) == 1

```

# Task 5: Predict for an entire batch of test examples
After you can successfully classify a single test example you need to repeat this across an entire batch of examples so we can apply performance metrics to assess the model.
\begin{align}
\hat{\mathbf{Y}}(\mathbf{X}_{test}) &= \{h(\mathbf{x}_{test}^{[i]}), \ldots, h(\mathbf{x}_{test}^{[j]})\} \\
&= \{\hat{y}^{[1]}, \ldots, \hat{y}^{[j]}\}
\end{align}

Sklearn and many other machine learning libraries will provide the data in terms of numpy arrays or similar (i.e. the tensors are commonly used by libraries such as tensorflow and pytorch and in most cases will work similarly to numpy arrays). If you take a slice of label data for example: \
Slicing the first 3 labels from Y, `Y[:3] => array([0, 1, 1])`. The shape of this would be (n_train_labels, ) *more generally (n_train_labels, n_output_features) if your output is a vector. If you had a python list it would appear as `Y[:3] => [0, 1, 1]`

You want to make sure that a batch of predicted outputs from your model matches the same form as a batch of labels for when you start making calculations such as accuracy. e.g, you want `y_hat.shape => (n_test_labels,)` to have the same shape as the lables `y.shape => (n_test_labels,)`. 

Most libraries will have this as part of how they create their models, but when building your own algorithms you may have intermediate steps that do not produce it exactly like this. These kinds of errors regarding data shape and dimensions pop up very often in practise. 

Some helpful functions:\
To combine multiple arrays: `np.concatenate()` *beware of axis when concatenating or for convenience `np.vstack()`
To change the shape of an array: `ndarray.reshape(shape)` or sometimes conventiently `ndarray.flatten()`


```python
def predictBatch(X_t, X_in, Y_in, k):
    """
    Performs predictions over a batch of test examples
    
    Arguments:
        X_t (array): shape [n_test_examples, n_features]
        X_in (array): shape [n_input_examples, n_features]
        Y_in (array): shape [n_input_labels, ]
        k (int): number of nearest neighbours to consider
    
    Returns:
        predictions (array): shape [n_test_examples,] the array of predictions
        
    """
    predictions = []
    for x_t_i in X_t:
        predictions.append(predict(x_t_i, X_in, Y_in, k)[0])
    
    return np.array(predictions)
```


```python
X_train_grade = np.array([[1, 1],
                       [0, 2],
                       [2, 1],
                       [1, 3],
                       [10, 10],
                       [5, 10],
                       [6, 8],
                       [2, 3]])
Y_train_grade = np.array([0, 0, 0, 0, 1, 1, 1, 0])

X_test_grade = np.array([[0, 0],
                [0, 1],
                [6, 10],
                [9, 8]])
Y_test_grade = np.array([0, 0, 1, 1])
k_grade=2

p = predictBatch(X_test_grade, X_train_grade, Y_train_grade, k=k_grade)
print(p.shape)
print(type(p))
```

    (4,)
    <class 'numpy.ndarray'>



```python
# The following tests are visible to you
# dummy dataset for grading purposes
X_train_grade = np.array([[1, 1],
                       [0, 2],
                       [2, 1],
                       [1, 3],
                       [10, 10],
                       [5, 10],
                       [6, 8],
                       [2, 3]])
Y_train_grade = np.array([0, 0, 0, 0, 1, 1, 1, 0])

X_test_grade = np.array([[0, 0],
                [0, 1],
                [6, 10],
                [9, 8]])
Y_test_grade = np.array([0, 0, 1, 1])
k_grade=1
assert np.equal(predictBatch(X_test_grade, X_train_grade, Y_train_grade, k=k_grade), Y_test_grade).all()
```

# Task 6: Accuracy metric
In this task you will create a function to measure the overall accuracy of your model. 
$$
ACC = \frac{\# correct predictions}{\# total examples}
$$


```python
def accuracy(Y_pred, Y_test):
    """
    Calculates the accuracy of the model 
    
    Arguments:
        Y_pred (array): shape [n_test_examples,] an array of model predictions
        Y_test (array): shape [n_test_labels,] an array of test labels to 
            evaluate the predictions against
    
    Returns:
        accuracy (float): the accuracy of the model
    """
    assert(Y_pred.shape == Y_test.shape)
    
    correct = 0
    total = len(Y_test)

    for i in range(total):
        if (Y_pred[i] == Y_test[i]):
            correct += 1
    
    accuracy = correct/total
    return accuracy
    
```


```python
# Free cell
Yt = np.array([0, 1, 0, 1])
Yp = np.array([1, 0, 1, 1])

accuracy(Yp, Yt)
```




    0.25




```python
# The following tests are visible to you

Y_test_grade = np.array([0, 1, 0, 0])
Y_pred_grade = np.array([0, 1, 1, 0])

assert accuracy(Y_pred_grade, Y_test_grade) == 0.75

Y_pred_grade = np.array([1, 0, 0, 0])
assert accuracy(Y_pred_grade, Y_test_grade) == 0.5

```

# Task 7: Test your model
Now you can combine the rest of the functions you've built into on function run your model with the generated training and test to data evaluate your model. This is really just to make running multiple tests more convenient.   


```python
def run(X_train, X_test, Y_train, Y_test, k):
    """
    Evaluates the model on the test data
    
    Arguments:
        X_train (array): shape [n_train_examples, n_features]
        X_test (array): shape [n_test_examples, n_features]
        Y_train (array): shape [n_train_examples, ]
        Y_test (array): shape [n_test_examples, ]
        k (int): number of nearest neighbours to consider
    
    Returns:
        test_accuracy (float): the final accuracy of your model 
    """
    Y_pred = predictBatch(X_test, X_train, Y_train, k)
    test_accuracy = accuracy(Y_pred, Y_test)

    return test_accuracy
```


```python
X_train_grade = np.array([[1, 1],
                       [0, 2],
                       [2, 1],
                       [1, 3],
                       [10, 10],
                       [5, 10],
                       [6, 8],
                       [2, 3]])
Y_train_grade = np.array([0, 0, 0, 0, 1, 1, 1, 0])

X_test_grade = np.array([[0, 0],
                [0, 1],
                [8, 3],
                [6, 10],
                [9, 8],
                [2, 9]])
Y_test_grade = np.array([0, 0, 0, 1, 1, 1])
k_grade=1 #Outlier in i=3, using k=2 improves

print( run(X_train_grade, X_test_grade, Y_train_grade, Y_test_grade, k_grade) ) 
```

    0.8333333333333334



```python
# I can't show you an example test because it would give away the answer
```

# End of Part 1
That concludes this part of assignment 1. 

ab8e30f1bf075e50a02ce8b44954786749cff990
ipynb
Jupyter Notebook
part1.ipynb
yusufheylen/kNN_Distance_metric_learning
b1f37391b2a4005069eac4c2522044e2c351400c
MIT
part1.ipynb
yusufheylen/kNN_Distance_metric_learning
b1f37391b2a4005069eac4c2522044e2c351400c
MIT
part1.ipynb
yusufheylen/kNN_Distance_metric_learning
b1f37391b2a4005069eac4c2522044e2c351400c
MIT
Qwen/Qwen-72B
1. YES
2. YES