👨 1-Nearest Neighbors (1-NN)

1-NN is a supervised algorithm solving a classification problem. It is probably the most simple supervised classification algorithm, and it works as follow:

Given a data set $\left\lbrace\boldsymbol{x}_i\right\rbrace$ with corresponding labels $\left\lbrace y_i\right\rbrace$ the algorithm maps any new vector $\tilde{\boldsymbol{x}}$ to the label corresponding to the closest $\boldsymbol{x}_i$:

$$\hat{i} = \underset{i}{\arg\min}\left\lVert \tilde{\boldsymbol{x}} - \boldsymbol{x}_i\right\lVert_2 \\ \hat{y} = y_\hat{i}$$

👫👬 K-Nearest Neighbors (K-NN)

K-NN is a simple extension of the basic 1-NN, where instead just using the single closest neighbor, we will use the $K$ nearest neighbors. After retrieving the $K$ nearest points we will take the majority vote (the most common label among the $K$ samples) to be our prediction.

🦠 Dataset: Breast Cancer Wisconsin

One of the methods which are used today to diagnose cancer is through a procedure called Fine-needle aspiration (FNA). In this procedure a sample of the tissue in question is extracted using a needle, and is then investigated under a microscope to determine whether the tissue is:

• Malignant - cancerous tissue
• or Benign - non-cancerous tissue

An example of a sample collected using FNA:

Image taken from Wikipedia

The Breast Cancer Wisconsin Diagnostic is a dataset which was collected by researchers at the University of Wisconsin. It includes 30 numeric properties, such as the average cell area, which were extracted from 569 different samples. The samples are provided along with the labels of whether the sample is malignant or benign.

This dataset is commonly used as an example of a binary classification problem.

The original dataset can be found here: Breast Cancer Wisconsin (Diagnostic) Data Set

The dataset which we will be using in this course can be found here

❓️ Problem: Predict the Correct Diagnostic

We would like to help the medical crew make the correct diagnostic by giving them a prediction based on the 30 values which can be extracted from each sample.

A comment: Usually in problems such as this we do not intend to replace experienced human making the diagnostic, but merely to give him an extra suggestion.

🕵️ Data Inspection

After loading the data, let take a look at it by printing out the 10 first rows.

Number of rows in the dataset: $N=569$

The Data Fields and Types

For simplicity we will not work with all the data columns and will limit ourselves to the following columns:

• diagnosis - The correct diagnosis: M = malignant (cancerous), B = benign (non-cancerous)
• radius_mean - The average radius of the cells in the sample.
• texture_mean - The average standard deviation of gray-scale values of the cells in the sample.

(A full description for each of the other columns can be found here)

📉 Dataset Inspection Plots

The number of malignant and benign samples in the dataset

Distribution of samples as a function of the measured values

And in a 2D plot

📜 Problem Definition

The Task and the Goal

This is a supervised learning problem of binary classification.

We would like to find a prediction function $h\left(\cdot\right)$, mapping form the space of $\boldsymbol{x}=\left[\text{mean_radius},\text{mean_texture}\right]^T$ to the space of labels $y$

Evaluation Method: The Misclassification Rate

$$R\left\lbrace h, \left\lbrace\boldsymbol{x},y\right\rbrace\right\rbrace=\frac{1}{N}\sum_i I\left\lbrace h\left(\boldsymbol{x}_i\right)\neq y_i\right\rbrace$$

📚 Splitting the dataset

By the given dataset, we want to split the data to two sets, train set - $\{\boldsymbol{X}_{train},\boldsymbol{Y}_{train}\}$ and test set - $\{\boldsymbol{X}_{test},\boldsymbol{Y}_{test}\}$ in order to train our model and evaluate the performance.

💡 Model & Learning Method Suggestion 1: 1-NN

We will use the 1-NN algorithm to generate our prediction function. The 1-NN has no learning stage

Voronoi Diagram

Let us plot the prediction function.

We will also add the Voronoi Diagram to it using the Voronoi and voronoi_plot_2d function from the SciPy package

⏱️ Performance evaluation

The test risk is: $0.14$

💡 Model & Learning Method Suggestion 1: K-NN

We expect to be able to improve our results using the K-NN algorithm, the question is how can we select $K$? One simple way to do so is to simply test all the relevant values of $K$ and pick the best one.

This is a common case in machine learning, where we have some part of the model which we do not have an efficient way to optimally select. We call these parameters the hyper-parameters of the model.

Three more hyper-parameters which we have encountered so far are:

• The number of bins in a histogram.
• The kernel and width in KDE.
• The $K$ in K-Means.

Two optional methods for selecting the hyper-parameters:

Brute Force / Grid Search

In some cases, like this one, we will be able to go over all the relevant range of possible values. In this case, we can simply test all of them and pick the values which result in the minimal risk.

Trial and error

In many other cases we will simply start by setting the hyper-parameters manually according to some rule of thumb or some smart guess, and iteratively:

1. Solve the model given the fixed hyper-parameters.
2. Update the hyper-parameters according to the results we get.

The workflow revisited - Hyper-parameters

Let us add the loop/iterations over the hyper-parameters to our workflow

✍️ Exercise 5.1

Select the optimal $K$ from the range $\left[1,100\right]$. Plot the risk as a function of $K$

Use SciKit-Learn’s KNeighborsClassifier class

Solution 5.1

The optimal $K$ is $K=12$ The test risk is: $0.061$

Train-Validation-Test Separation

In the above example, we have selected the optimal $K$ based upon the risk which was calculated using the test set. As we stated before this situation is problematic since the risk over the test set would be too optimistic due to overfitting.

The solution to this problem is to divide the dataset once more. Therefore in cases, where we would also be required to optimize over some hyper-parameters, we would divide our data into three sets: a train-set a validation-set and a test-set.

A common practice is to use 60% train - 20% validation - 20% test.

✍️ Exercise 5.2

Repeat the learning process using the 3-fold split.

Solution 5.2

The optimal $K$ is $K=19$ The validation risk is: $0.097$

⏱ Performance evaluation

The test risk is: $0.087$

Cross-Validation

When using a 60%-20%-20% split we are in fact using only 60% of the collected data to train our model which is a waste of good data. Cross-validation attempts to partially solve this issue. In Cross-validation we do not set a fixed portion of the data to be a validation set and instead we split all the training data (all the data which is not in the test set) in to $k$ equal groups and evaluate the risk using the following method:

• For some given hyper-parameters repeat the process of learning and evaluating the risk each time using a different group as the validation group.
• The report the estimated risk as the average risks from the previous step.

Image taken from SciKit Learn

✍️ Exercise 5.4

Repeat the process using cross-validation

Use SciKit-Learn’s cross_val_score function

Solution 5.4

We will return to our original 80%-20% split

The optimal $K$ is $K=22$ The validation risk is: $0.09$

⏱ Performance evaluation

The test risk is: $0.079$