<jupyter_start><jupyter_text>PC Lab 2: Nearest neighbour and data preprocessingPredictive modelling  IntroductionIn our previous lab session, we explored the iris dataset. In this dataset, there are no missing values in the variable "Species". But what if there are new observations without a value in the "Species" variable? So, imagine the case that for a 'new' iris flower we know the values for the other columns (sepal/petal length and height) but it is unknown to which of the three species it belongs to (dataset irisNA.csv). A natural task would beto try to guess to which species each of the new flowers belongs to. This task(or problem) is called a classification problem in machine learning. In this practical exercise session, a firstsimple algorithm that provides an answer to this problem is described. Notations and vocabularyIn the iris dataset (iris120.csv), each instance (each flower is an instance) is described by five properties:the species it belongs to, the width of its petals, the length of its petals, the width of its sepals and thelength of its sepals. In this PC-lab, for simplicity, only species, sepal length and sepal width will be used.These properties can be seen as variables, and for a given flower, each of these variables takes a specificvalue. In a classification setting, the aim is to predict the value of one of the variables (here the species),based on the value of the other variables (here petal width and length). The variable of which the valueshave to be predicted is called the output variable and the variables used to make this prediction are calledthe input variables or features. A dataset consists of a set of observations of input-output couples $(\boldsymbol{x}, y)$. In this dataset, the observed valuesfor the features of the $i$-th instance are denoted $\boldsymbol{x_i}$ $= (x_{i1}, ... , x_{ip})^T$ , where $p$ the number of features, and the observed value of its outputis denoted $y_i$. Using this notation, a training dataset $T$ containing $n$ instances can be written as $$T = \{(\boldsymbol{x_1}, y_1), ... , (\boldsymbol{x_n}, y_n)\}.$$Using this dataset, we will try to build a model (generally denoted $f$) that is able to predict the value of theoutput variable, based on the value of the input variables. When this output variable is nominal, this processis called a classification problem.    In the iris problem, both input variables take real values $(\boldsymbol{x_i} \in \mathbb{R}^2)$. The output variable, however, isnominal, it takes values from a finite set $\{setosa, versicolor, virginica\}$. Because of this, the model $\textit{f}$ we arelooking for is one which performs a mapping $$\textit{f} : \mathbb{R}^2 \rightarrow  \{setosa, versicolor, virginica\}.$$    Nearest neighbour for classificationSeveral techniques exist that are capable of deriving classification models from data. A very simple one isthe nearest neighbour model. This model departs from the assumption that instances whose features arehighly similar, are likely to have the same labels. The one nearest neighbour (1-NN) model applies thisidea in its most extreme form: the label for an instance (with unknown label) is predicted as the label of theclosest instance in the training dataset.   To be able to select the ‘closest’ instance in the training dataset, a distance measure has to be defined. Inthis text, we will use $d(\boldsymbol{x_i}, \boldsymbol{x_j})$ to denote the distance between two feature vectors $\boldsymbol{x_i}$ and $\boldsymbol{x_j}$. As a simpledistance measure, the Euclidean distance can be used$$d_E(\boldsymbol{x_i}, \boldsymbol{x_j}) = \sqrt{\sum_{k=1}^{p} (x_{i,k} - x_{j,k})^2}$$Using this distance function, the nearest neighbour algorithm performs the following steps:1. For an instance with unknown label and known feature vector $\boldsymbol{x}$, calculate the distance to each instance in the dataset: $d_E(\boldsymbol{x}, \boldsymbol{x_i})$ where $i = 1, ... ,n.$2. Select the closest instance and take its label as the prediction for the unknown label. This first codeblock downloads all the necessary data for this pc-lab.<jupyter_code>import urllib.request
urllib.request.urlretrieve("https://raw.githubusercontent.com/gdewael/teaching/main/predmod/lab2/iris120.csv", "iris120.csv")
urllib.request.urlretrieve("https://raw.githubusercontent.com/gdewael/teaching/main/predmod/lab2/irisNA.csv", "irisNA.csv")
urllib.request.urlretrieve("https://raw.githubusercontent.com/gdewael/teaching/main/predmod/lab2/abaloneTrain700.csv", "abalone.csv")<jupyter_output><empty_output><jupyter_text>EXERCISE: **Load the dataset iris120.csv in to the memory and select the columns 'Sepal.Length', 'Sepal.Width', and 'Species'. Additionally, load the set of unclassifiedinstances (irisNA.csv) and select the same columns. Both datasets should be loaded as data frames. **<jupyter_code>import numpy as np
import pandas as pd

iris120 = # ... load in dataset iris120.csv
iris120 = iris120[] # ... select the right columns

irisNA =  # ... repeat for irisNA.csv
irisNA = irisNA[] # ... repeat for irisNA.csv
iris120.head()
irisNA.head()<jupyter_output><empty_output><jupyter_text>EXERCISE: **Implement the nearest neighbour algorithm for the iris problem in a function called nnIrisPredict.Use this function to predict the species of unknown flowers irisNA.csv in the dataset. Make sureyour function has the following structure:**<jupyter_code>new_observation_features = irisNA.iloc[0, 0:2] # taking the first two columns
new_observation_features
trainDataset = iris120
trainDataset
def nnIrisPredict(featuresNewInstance, trainDataset):
    # create a variable 'dist' containing the euclidean distance of the
    # new instance to all instances (rows) in the training dataset:
    dist = # ...
    # what is the index of the nearest neighbor 'nn' in our training dataset:
    nn = np.argmin(dist)
    # Extract the species label of that nearest neighbor
    # and return that as prediction:
    label = trainDataset.iloc[nn]['Species']
    return label


# call the function
nnIrisPredict(new_observation_features, trainDataset)<jupyter_output><empty_output><jupyter_text>where trainDataset is a data frame (containing flowers with known species label) with columns"Sepal.Length", "Sepal.Width" and "Species". featuresNewInstance is a vector with the sepallength in the first position and the sepal width in the second position. Label should be one of thestrings "setosa", "versicolor" and "virginica".  The nearest neighbour algorithm for regressionIn the previous section, the output was a nominal variable (no numerical values, specific classes). When the output is real-valued, the prediction problem is called a regression problem. As with nominal outputs, the nearest neighbour algorithm canbe used to predict the output variable of unlabeled instances. The algorithm is identical to the one forclassification, however, the prediction will be the real-valued label of the closest instance in the trainingdataset instead of its class label. Data preprocessingIn this section, some elementary data preprocessing steps are described. Dummy encoding of nominal variablesThe basic nearest neighbour algorithm implemented in the previous assignment can only be used withnumerical features. However, often types of variables such as nominal variables or ordinal variables arepresent. A simple solution to this problem exists in using a dummy encoding for each nominal variable.When a variable $\boldsymbol{x^i}$ is nominal with $k$ values, it is replaced by $k$ new binary variables. As an imaginary example,consider a dataset with a feature containing weather status. This feature ($\boldsymbol{x^1}$) could for example contain three values: Sunny, Overcast and Rainy.Each of these values could be represented by a dummy variable: $\boldsymbol{x^{1a}}$, $\boldsymbol{x^{1b}}$ and $\boldsymbol{x^{1c}}$ with the following values:     *  $x^{1a} = 1$ if $x^1 = "Sunny"$ and  $x^{1a} = 0$ otherwise  * $x^{1b} = 1$ if $x^1 = "Overcast"$ and $x^{1b} = 0$ otherwise  * $x^{1c} = 1$ if $x^1 = "Rainy"$ and $x^{1c} = 0$ otherwise  See the following example in python. In this example, we use  the Abalone dataset (abaloneTrain700.csv) which contains measurements of physical properties of several abalone (an edible sea snail) specimen. Using these physical properties, the aim is to build a predictive model for the age of these animals (more information concerning this dataset can be found in [abalone.info](https://archive.ics.uci.edu/ml/datasets/Abalone)). In the following example, we replace the nominal variable 'sex' with 3 dummy variables (as many as the values it takes). In python, there are functions such as the [get_dummies()](https://pandas.pydata.org/pandas-docs/stable/generated/pandas.get_dummies.html) function which are used for this purpose. (Another option is scikit-learn's [OneHotEncoder](https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.OneHotEncoder.html)) So firstly, we create the dummy variables, then we concatenate them with the original dataset and finally we remove the original variable form the dataset.<jupyter_code># load dataset
abalone = pd.read_csv('abalone.csv')
print(abalone.head())
# create dummies
dummies = pd.get_dummies(abalone.sex) 
print(dummies.head())
# concatenate them with the dataset
abalone_with_dummies = pd.concat([abalone, dummies], axis=1)
# remove the original sex column
abalone_with_dummies = abalone_with_dummies.drop(['sex'], axis=1)
print(abalone_with_dummies.head())<jupyter_output><empty_output><jupyter_text>Missing valuesMissing values are commonly encountered in data mining studies. Often, missing values are imputed(replaced by a value). Several techniques exist to choose this value. A simple, but often used methodis mean imputation. Here, each missing value is replaced by the mean of the observed values forthat variable. More advanced methods exist of building separate models to predict the missingvalues.When implementing the mean imputation, the [Imputer](http://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.Imputer.html) of scikit-learn library might be handy. The PC labs in this practical have no missing values however:<jupyter_code>np.isnan(abalone_with_dummies).any()<jupyter_output><empty_output><jupyter_text>Standardizing the dataIn realistic datasets, most features have different means and standard deviations. For the nearestneighbour algorithm, it can easily be seen that features with a high standard deviation will be moreinfluential than features with a lower standard deviation. In most cases, this is unwanted since itis not known in advance which features are most important. To overcome this problem, featuresare often standardized. The standardized version of $x^i$ can be obtained as   $$\frac{x^i - \mu_i}{\sigma_i}$$    where $\mu_i$ and $\sigma_i$ represent the sample mean and standard deviation of $\boldsymbol{x^i}$.The [Scaler](http://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.scale.html) of scikit-learn can be used to perform this standardizing.Notice that we're doing here (scaling the training and test set together in one operation) is usually considered bad practice as it will leak data from train to test and hence bias model evaluation.<jupyter_code>from sklearn.preprocessing import scale

y = abalone_with_dummies['age'].values # keep the target variable
X = abalone_with_dummies.drop(['age'], axis=1) # remove it from the feature set
X = scale(X)
X
y<jupyter_output><empty_output><jupyter_text>Data splitting and Prediction qualityTo test the performance of the nearest neighbour algorithm, an option is to use test data withknown labels and to compare the predictions with these labels. In this case, we have two differentdatasets, a training set T and a test set T$^*$. In case of a regression problem, the mean of squaredresiduals is commonly used to evaluate the quality of a model. This measure is calculated as follows:   1. Mean of squared residuals on test set:$$Err_{T^*} = \frac{1}{|T^*|}\sum_{\boldsymbol{x_i} \in T^*} (Y(\boldsymbol{x_i}) - y_i)^2$$2. Additionally, the error on the training data itself can be computed:   $$Err_{T} = \frac{1}{|T|}\sum_{\boldsymbol{x_i} \in T} (Y(\boldsymbol{x_i}) - y_i)^2$$Naturally, it is desirable to keep the mean of squared residuals as small as possible. EXERCISE: **To prepare the dataset for the following exercise, split the dataset in a portion (80%) we will use to train on, and a portion we will use to predict on (20%) (test set). See the documentation of scikit learn's [train_test_split](https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.train_test_split.html) for more info on how to do this.**<jupyter_code># import train_test_split function

# you should get four variables named: X_train, y_train, X_test & y_test
# ... = train_test_split( ... )<jupyter_output><empty_output><jupyter_text>k-nearest-neighboursA simple extension of the nearest neighbour algorithm consists of taking more than only the nearestneighbour into account. Let $N_k(\boldsymbol{x}) \subset T$ be the k nearest neighbours of an instance with featurevector $\boldsymbol{x}$. The k-nearest neighbour prediction $Y(\boldsymbol{x})$ can be determined as follows1. For classification problems:  $Y(\boldsymbol{x})$ is set as the label that occurs most often in $N_k(\boldsymbol{x})$ (themode).2. For regression problems, the average of the $k$ nearest outputs can be taken $Y(\boldsymbol{x}) = \frac{1}{k}\sum_{\boldsymbol{x_i} \in N_k(\boldsymbol{x})} y_i$     k-nearest-neighbours in pythonAs with the 1-nearest neighbour algorithm, it is possible to implement a version of the k-nearest neighboursalgorithm in python. However, an alternative is to use a pre-implemented version of thisalgorithm. For most popular machine learning algorithms, these functions are packed in specific python“packages". An implementation ofthe k-nearest-neighbours algorithm is available in the [scikit-learn](http://scikit-learn.org/stable/) library (as well). You can load and see more info about the usage of this function by typing: (or by going to the [documentation page](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsRegressor.html))<jupyter_code>from sklearn import neighbors
help(neighbors.KNeighborsRegressor)<jupyter_output><empty_output><jupyter_text>As you can see in the help window, in scikit-learn, an estimator for classification/regression is a Python object that implements the methods fit(X, y) and predict(T). The constructor of an estimator takes as arguments the parameters of the model (in our case the basic parameters are the number of neighbours and the distance metric). So the first step is to create a KNN instance:<jupyter_code>knn = neighbors.KNeighborsRegressor(n_neighbors = 5, metric = 'euclidean')<jupyter_output><empty_output><jupyter_text>We call our estimator instance `knn`. It now must be fitted to the data, that is, it must learn from the data. This is done by passing our training set to the fit method.<jupyter_code>knn.fit(X_train, y_train)<jupyter_output><empty_output><jupyter_text>Now you can predict new values, in particular, we can ask to the estimator which is the age of the first example in our test dataset (remember: by doing this, we are now comparing the features of this example to the features of all training samples, then determining what the closest neighbors are, then averaging the age of those neighbors as predictions)<jupyter_code>y_pred = knn.predict(X_test[0].reshape(1, -1))<jupyter_output><empty_output><jupyter_text>We can calculate the mean squared error of the prediction we get before (for the first example of the test dataset) by calculating it ourselves or by using the [mean_squared_error()](http://scikit-learn.org/stable/modules/generated/sklearn.metrics.mean_squared_error.html) function of scikit-learn.<jupyter_code>from sklearn.metrics import mean_squared_error
print(y_test[0], y_pred)
print(mean_squared_error(y_pred, y_test[0].reshape(1, -1)))<jupyter_output><empty_output><jupyter_text>EXERCISE: **Build a 3-nearest-neighbor regressor in a similar manner as before. Predict the age for all training samples and test samples and compute the mean squared error of both prediction sets. Which predictions are better?**<jupyter_code># Instantiate the knn object

# Fit

# Predict train

# Predict test

# MSE train

# MSE test<jupyter_output><empty_output><jupyter_text>EXERCISE: **Now do the same but iterate over possible values for 'k' as the number of nearest neighbors taken into account, where k ranges between 1 and 50 (step size equal to 3). Plot the resulting errors of the models as a function of 'k'. 'k' is what we call a hyperparameter: a type of parameter that is (most often) tuned by hand according to the prediction task. For some datasets/tasks we will for example need more or less neighbors (as predictions tasks have varying difficulty).**<jupyter_code>#results_train = []
#results_test = []
# for i in range(...):

for i in range(...):
    # call, fit and predict ...

    # append MSE train to list
    # results_train.append(...)

    # append MSE test to list
    # results_test.append(...)

import matplotlib.pyplot as plt

plt.plot(...) # training MSEs
plt.plot(...) # test MSEs
plt.ylabel('MSE')
plt.xlabel('$k$ nearest neighbors')
plt.legend(['Train MSE', 'Test MSE'])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08323301805674979, 'fraction_numerical': 0.005961593579822299, 'mean_word_length': 5.253046594982079, 'pattern_counts': {'":': 0, '<': 57, '<?xml version=': 0, '>': 57, 'https://': 8, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '14', 'dir': 'jupyter-structured-clean-dedup', 'id': '351120', 'license': 'MIT', 'n_tokens_mistral': 4857, 'n_tokens_neox': 4670, 'n_words': 2159, 'path': 'predmod/lab2/Lab2_KNN_2022.ipynb', 'repo_name': 'gdewael/teaching', 'size': '17445'}