# the $k$-nearest neighbors (kNN) supervised learning algorithm

* can be used for regression or classification
* non-parametric
* imposes only mild structural assumptions about the data

let's explore $k$-nearest neighbor classification.

training data examples: $\{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), ..., (\mathbf{x}_n, y_n)\}$ where $\mathbf{x}_i$ is the feature vector and $y_i \in \{0, 1\}$ is the label on data point $i$. This is a binary classification since each data point is labeled with $0$ or $1$.

the $k$-NN algorithm uses the training data to classify new data points. say we have a new data point $\mathbf{x}$ but we don't know its label. the $k$-NN algorithm predicts the class of this data point as:
\begin{equation}
    \hat{y}(\mathbf{x})= \frac{1}{k} \displaystyle \sum_{\mathbf{x}_i \in N_k(\mathbf{x})} y_i
\end{equation}
where $N_k(x)$ is the *neighborhood* of $\mathbf{x}$ defined as the $k$ "closest" points in the training data set. For "closest" to be mathematically defined, we need a distance metric. One such distance metric is Euclidean distance. In words, the $k$ data points closest to $\mathbf{x}$ vote on whether we should classify this point as a 0 or 1 with their labels.


```julia
using CSV
using DataFrames
using PyPlot
using ScikitLearn # machine learning package
using StatsBase
using Random
using LaTeXStrings # for L"$x$" to work instead of needing to do "\$x\$"
using Printf

# (optional)change settings for all plots at once, e.g. font size
rcParams = PyPlot.PyDict(PyPlot.matplotlib."rcParams")
rcParams["font.size"] = 16

# (optional) change the style. see styles here: https://matplotlib.org/3.1.1/gallery/style_sheets/style_sheets_reference.html
PyPlot.matplotlib.style.use("seaborn-white")   
```

## classifying breast tumors as malignant or benign

source: [UCI Machine Learning Repository](https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Diagnostic))

> Features are computed from a digitized image of a fine needle aspirate (FNA) of a breast mass. They describe characteristics of the cell nuclei present in the image.

The mean radius and smoothness of the cell nuclei (the two features) and the outcome (M = malignant, B = benign) of the tumor are in the `breast_cancer_data.csv`.


```julia
df = CSV.read("breast_cancer_data.csv")
first(df, 5)
```




<table class="data-frame"><thead><tr><th></th><th>mean_radius</th><th>mean_smoothness</th><th>outcome</th></tr><tr><th></th><th>Float64</th><th>Float64</th><th>String</th></tr></thead><tbody><p>5 rows × 3 columns</p><tr><th>1</th><td>13.85</td><td>1.495</td><td>B</td></tr><tr><th>2</th><td>9.668</td><td>2.275</td><td>B</td></tr><tr><th>3</th><td>9.295</td><td>2.388</td><td>B</td></tr><tr><th>4</th><td>19.69</td><td>4.585</td><td>M</td></tr><tr><th>5</th><td>9.755</td><td>1.243</td><td>B</td></tr></tbody></table>




```julia

```

let's map the outcomes to a number, 0 or 1, to facilitate the NN algo.

benign (B) : 0<br>
malignant (M) : 1


```julia

```

let's also have a color scheme for the class labels.


```julia

```

since this is a two-dimensional feature space, we have the luxury of visualizing how the classes are distributed in feature space. in practice, we do not have this luxury. I choose a 2D feature space for pedagogical purposes :)


```julia

```

### using Scikitlearn for $k$-nearest neighbor classification

scikitlearn documentation for `KNeighborsClassifier` [here](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html)


```julia
@sk_import neighbors : KNeighborsClassifier
@sk_import model_selection : train_test_split
@sk_import metrics : confusion_matrix
```

    ┌ Warning: Module model_selection has been ported to Julia - try `import ScikitLearn: CrossValidation` instead
    └ @ ScikitLearn.Skcore /home/cokes/.julia/packages/ScikitLearn/bo2Pt/src/Skcore.jl:140





    PyObject <function confusion_matrix at 0x7fe40f6b6c80>



scikitlearn takes as input:
* a feature matrix `X`, which must be `n_samples` by `n_features`
* a target vector `y`, which must be `n_samples` long (of course)


```julia

```

construct a nearest neighbor object in scikitlearn


```julia

```

pass the `KNeighborsClassifier` object our training data. this will be used to make predictions on future, unseen data.


```julia

```

we can now make predictions on new, unseen data. that is, if we know the mean radius and mean smoothness of a new tumor, we can make a prediction about whether this tumor is malignant or benign. let's imagine we take measurements on a new tumor and it has the feature vector `x_new` below. we aim to predict whether it is benign or malignant.


```julia
# new tumor. unknown if malignant or benign...
x_new = [10.0 1.5] # should be B
x_new = [20.0 5.0] # should be M
```




    1×2 Array{Float64,2}:
     20.0  5.0



first, let's plot where it falls in feature space


```julia

```

predict whether this new tumor is benign or malignant


```julia

```

visualize the decision boundary


```julia

```


```julia
figure()
xlabel("mean radius")
ylabel("mean smoothness")
```

we can compute the accuracy of the prediction on the training data. but when $k=1$ we get 100% accuracy by construction!


```julia

```

### the test/train paradigm

randomly split your data set into a training and test set. train the $k$-NN algo on the training data, then use the trained model to make predictions on data in the test set. we can compare the predicted label to the true label. the test set error is a quality prediction of generalization error on *unseen* data. we could write our own code for this, but scikitlearn provides `test_train_split` for us.


```julia

```

to fully assess the performance of our model, trained on the training set, and tested on the test set, we can plot a so-called confusion matrix. it tells us about false positives, true positives, false negatives, and true negatives.


```julia
# see https://scikit-learn.org/stable/auto_examples/model_selection/plot_confusion_matrix.html#sphx-glr-auto-examples-model-selection-plot-confusion-matrix-py
function plot_confusion_matrix(y_true::Array{Float64}, y_pred::Array{Float64}, classes::Array{String})
    # calculate confusion matrix from scikitlearn
    cm = confusion_matrix(y_true, y_pred)
    
    fig, ax = plt.subplots()
    ax.imshow(cm, interpolation="nearest", cmap=plt.cm.Greens)
    ax.set(
        xlim=[-0.5, 1.5],
        ylim=[-0.5, 1.5],
        xticks=[0, 1],
        yticks=[0, 1],
        xticklabels=classes,
        yticklabels=classes,
        xlabel="predicted label",
        ylabel="true label"
    )

    for i = 1:2
        for j = 1:2
            ax.text(j-1, i-1, @sprintf("%d", cm[i, j]), ha="center", va="center")
        end
    end
    tight_layout()
end
```




    plot_confusion_matrix (generic function with 1 method)



to find the best $k$, we can scan over all $k$, train the model in the training set, then test the model on the test set (unseen data) to see how it performs. we take the "best" $k$ as the one that yields the lowest test set error, as we expect it to have the lowest generalization error on unseen data.


```julia

```

the optimal $k$ is around 8. So we should train our $k$-NN algo with $k=8$, then deploy this model, since it should result in the best accuracy on unseen data.


```julia

```

001405c8088211b4ab788b4df94b6383b0f578e3
ipynb
Jupyter Notebook
CHE599-IntroDataScience/lectures/knn/kNN_algo_sparse.ipynb
leanth/OSUCoursework
ccfbf5f9daa8f6d3818bb5e4cc8df7c5135a5f34
MIT
CHE599-IntroDataScience/lectures/knn/kNN_algo_sparse.ipynb
leanth/OSUCoursework
ccfbf5f9daa8f6d3818bb5e4cc8df7c5135a5f34
MIT
CHE599-IntroDataScience/lectures/knn/kNN_algo_sparse.ipynb
leanth/OSUCoursework
ccfbf5f9daa8f6d3818bb5e4cc8df7c5135a5f34
MIT
Qwen/Qwen-72B
1. YES
2. YES