# 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
by(df, :outcome, total=:outcome => length)
```




<table class="data-frame"><thead><tr><th></th><th>outcome</th><th>total</th></tr><tr><th></th><th>String</th><th>Int64</th></tr></thead><tbody><p>2 rows × 2 columns</p><tr><th>1</th><td>B</td><td>180</td></tr><tr><th>2</th><td>M</td><td>120</td></tr></tbody></table>



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

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


```julia
df[!, :class] = map(row -> row == "B" ? 0 : 1, df[:, :outcome])
first(df, 5)
```




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



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


```julia
color_scheme = Dict("M" => "r", "B" => "g")
```




    Dict{String,String} with 2 entries:
      "B" => "g"
      "M" => "r"



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
figure()
xlabel("mean radius")
ylabel("mean smoothness")
for df_c in groupby(df, :outcome)
    outcome = df_c[1, :outcome]
    scatter(df_c[:, :mean_radius], df_c[:, :mean_smoothness], label="$outcome", 
        marker="o", facecolor="None", edgecolor=color_scheme[outcome])
end
legend()
axis("equal")
```

### 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: redefining constant KNeighborsClassifier
    ┌ 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
    WARNING: redefining constant train_test_split
    WARNING: redefining constant confusion_matrix





    PyObject <function confusion_matrix at 0x7f46d1b8aea0>



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
n_tumors = nrow(df)

X = zeros(n_tumors, 2)
y = zeros(n_tumors)
for (i, tumor) in enumerate(eachrow(df))
    X[i, 1] = tumor[:mean_radius]
    X[i, 2] = tumor[:mean_smoothness]
    y[i] = tumor[:class]
end
X # look at y too!
```




    300×2 Array{Float64,2}:
     13.85   1.495
      9.668  2.275
      9.295  2.388
     19.69   4.585
      9.755  1.243
     16.11   4.533
     14.78   2.45 
     15.78   3.598
     15.71   1.972
     14.68   3.195
     13.71   3.856
     21.09   4.414
     11.31   1.831
      ⋮           
     11.08   1.719
     18.94   5.486
     15.32   4.061
     14.25   5.373
     20.6    5.772
      8.671  1.435
     11.64   2.155
     12.06   1.171
     13.88   1.709
     14.9    3.466
     19.59   2.916
     14.81   1.677



construct a nearest neighbor object in scikitlearn


```julia
knn = KNeighborsClassifier(n_neighbors=1)
```




    PyObject KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
                         metric_params=None, n_jobs=None, n_neighbors=1, p=2,
                         weights='uniform')



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


```julia
knn.fit(X, y)
```




    PyObject KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
                         metric_params=None, n_jobs=None, n_neighbors=1, p=2,
                         weights='uniform')



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
figure()
xlabel("mean radius")
ylabel("mean smoothness")
for df_c in groupby(df, :outcome)
    outcome = df_c[1, :outcome]
    scatter(df_c[:, :mean_radius], df_c[:, :mean_smoothness], label="$outcome", 
        marker="o", facecolor="None", edgecolor=color_scheme[outcome])
end

# plot where new tumor falls
scatter(x_new[1], x_new[2], marker="s", label="new data pt", color="k")

legend()
axis("equal")
```

predict whether this new tumor is benign or malignant


```julia
knn.predict(x_new)
```




    1-element Array{Float64,1}:
     1.0



visualize the decision boundary


```julia
radius = 5:0.25:30
smoothness = 0.0:0.25:20.0

knn_prediction = zeros(length(smoothness), length(radius))
for i = 1:length(radius)
    for j = 1:length(smoothness)
        x = [radius[i] smoothness[j]]
        knn_prediction[j, i] = knn.predict(x)[1]
    end
end
```


```julia
figure()
contourf(radius, smoothness, knn_prediction, alpha=0.4, [0.0, 0.5, 1.0], colors=["g", "r"])
for df_c in groupby(df, :outcome)
    outcome = df_c[1, :outcome]
    scatter(df_c[:, :mean_radius], df_c[:, :mean_smoothness], label="$outcome", 
        marker="o", facecolor="None", edgecolor=color_scheme[outcome])
end
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
knn.score(X, y)
```




    0.9166666666666666



### 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
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33)
```




    4-element Array{Array{Float64,N} where N,1}:
     [12.06 1.171; 18.31 1.817; … ; 13.44 1.572; 9.295 2.388]                                               
     [23.27 4.603; 18.01 5.353; … ; 20.29 5.438; 13.65 1.391]                                               
     [0.0, 1.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0  …  1.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.0]
     [1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0, 0.0  …  1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0]



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

k = 3
knn = KNeighborsClassifier(n_neighbors=k)
knn.fit(X_train, y_train)
y_pred = knn.predict(X_test)

plot_confusion_matrix(y_test, y_pred, ["benign", "malignant"])
```

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
ks = 1:20
test_accuracy = zeros(length(ks))
train_accuracy = zeros(length(ks))
for (i, k) in enumerate(ks)
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    test_accuracy[i] = knn.score(X_test, y_test)
    train_accuracy[i] = knn.score(X_train, y_train)
end

figure()
plot(ks, train_accuracy, marker="o", label="train")
plot(ks, test_accuracy, marker="o", label="test")
legend()
xlabel(L"$k$")
ylabel("accuracy")
```

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
knn = KNeighborsClassifier(n_neighbors=8)
knn.fit(X, y) # *this* is the model we deploy

# look at new decision boundary
for i = 1:length(radius)
    for j = 1:length(smoothness)
        x = [radius[i] smoothness[j]]
        knn_prediction[j, i] = knn.predict(x)[1]
    end
end

figure()
contourf(radius, smoothness, knn_prediction, alpha=0.4, [0.0, 0.5, 1.0], colors=["g", "r"])
for df_c in groupby(df, :outcome)
    outcome = df_c[1, :outcome]
    scatter(df_c[:, :mean_radius], df_c[:, :mean_smoothness], label="$outcome", 
        marker="o", facecolor="None", edgecolor=color_scheme[outcome])
end
xlabel("mean radius")
ylabel("mean smoothness")
```

b6f36df03f1dccecac7712a252c88b9df0d3aa71
ipynb
Jupyter Notebook
CHE599-IntroDataScience/lectures/knn/kNN_algo.ipynb
leanth/OSUCoursework
ccfbf5f9daa8f6d3818bb5e4cc8df7c5135a5f34
MIT
CHE599-IntroDataScience/lectures/knn/kNN_algo.ipynb
leanth/OSUCoursework
ccfbf5f9daa8f6d3818bb5e4cc8df7c5135a5f34
MIT
CHE599-IntroDataScience/lectures/knn/kNN_algo.ipynb
leanth/OSUCoursework
ccfbf5f9daa8f6d3818bb5e4cc8df7c5135a5f34
MIT
2019-10-02T16:11:36.000Z
2019-10-15T20:10:40.000Z
Qwen/Qwen-72B
1. YES
2. YES