<jupyter_start><jupyter_text>Assignment 1: Part 1 - kNN BasicsIn 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<jupyter_code>import numpy as np
from sklearn.datasets import make_classification 
from sklearn.model_selection import train_test_split
import matplotlib.pyplot as plt<jupyter_output><empty_output><jupyter_text>Data explorationWe 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.<jupyter_code>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)<jupyter_output><empty_output><jupyter_text>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<jupyter_code># 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<jupyter_output><empty_output><jupyter_text>Data VisualisationIt'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.<jupyter_code>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()
# You can use this block play around 
# notation: superscript = example, subscript = feature 
x_a = [0, 1]
x_b = [0, 5]<jupyter_output><empty_output><jupyter_text>Task 1: Distance FunctionYour 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()`<jupyter_code>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
# 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)
# 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<jupyter_output><empty_output><jupyter_text>Task 2: Calculate list of distancesFor 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 1The distances must be stored in a Python list, not a numpy array.Some helpful functions:\Python's built-in `append()` function<jupyter_code>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
# 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)
# 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]<jupyter_output><empty_output><jupyter_text>Task 3: Determine k Nearest NeighboursThis 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()`<jupyter_code>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
# 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
# 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]<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>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
# 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)
# 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()<jupyter_output><empty_output><jupyter_text>Task 4: Predict ClassYou 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.<jupyter_code>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
# 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))
# 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<jupyter_output><empty_output><jupyter_text>Task 5: Predict for an entire batch of test examplesAfter 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()`<jupyter_code>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)
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))
# 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()<jupyter_output><empty_output><jupyter_text>Task 6: Accuracy metricIn this task you will create a function to measure the overall accuracy of your model. $$ACC = \frac{\ correct predictions}{\ total examples}$$<jupyter_code>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
    
# Free cell
Yt = np.array([0, 1, 0, 1])
Yp = np.array([1, 0, 1, 1])

accuracy(Yp, Yt)
# 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<jupyter_output><empty_output><jupyter_text>Task 7: Test your modelNow 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.<jupyter_code>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
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) ) 
# I can't show you an example test because it would give away the answer<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12334462580843857, 'fraction_numerical': 0.029360435273585873, 'mean_word_length': 3.105141171512853, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 55, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '628993', 'license': 'MIT', 'n_tokens_mistral': 6844, 'n_tokens_neox': 6357, 'n_words': 2262, 'path': 'part1.ipynb', 'repo_name': 'yusufheylen/kNN_Distance_metric_learning', 'size': '19482'}