<jupyter_start><jupyter_text>Table of Contents1&nbsp;&nbsp;Objectives2&nbsp;&nbsp;Concept of the $k$-Nearest Neighbors Algorithm2.1&nbsp;&nbsp;Who's Nearby?2.2&nbsp;&nbsp;Summary of $k$NN2.3&nbsp;&nbsp;Implementing in Scikit-Learn2.3.1&nbsp;&nbsp;Training the KNN2.3.2&nbsp;&nbsp;Make Some Predictions3&nbsp;&nbsp;The Pros and Cons3.1&nbsp;&nbsp;Advantages3.2&nbsp;&nbsp;Disadvantages4&nbsp;&nbsp;Classification with sklearn.neighbors4.1&nbsp;&nbsp;Train-Test Split4.2&nbsp;&nbsp;Validation Split4.3&nbsp;&nbsp;Different $k$ Values4.3.1&nbsp;&nbsp;$k=1$4.3.2&nbsp;&nbsp;$k=3$4.3.3&nbsp;&nbsp;$k=5$4.3.4&nbsp;&nbsp;Observing Different $k$ Values4.4&nbsp;&nbsp;Scaling4.4.1&nbsp;&nbsp;More Resources on Scaling5&nbsp;&nbsp;$k$ and the Bias-Variance Tradeoff5.1&nbsp;&nbsp;The Relation Between $k$ and Bias/Variance6&nbsp;&nbsp;Level Up: Distance Metrics ![wilson](img/wilson.jpg)<jupyter_code>import pandas as pd
import numpy as np

import matplotlib.pyplot as plt
import seaborn as sns

from sklearn.metrics import f1_score, confusion_matrix,\
recall_score, precision_score, accuracy_score
from src.confusion import plot_confusion_matrix
from src.k_classify import predict_one
from src.plot_train import *
from src.euclid import *

from sklearn import datasets
from sklearn.preprocessing import StandardScaler, MinMaxScaler, LabelEncoder
from sklearn.neighbors import KNeighborsClassifier, NearestNeighbors
from sklearn.model_selection import train_test_split, KFold<jupyter_output><empty_output><jupyter_text>Objectives - Describe the $k$-nearest neighbors algorithm- Identify multiple common distance metrics- Tune $k$ appropriately in response to models with high bias or variance  Concept of the $k$-Nearest Neighbors Algorithm<jupyter_code>#KNN can be used with more than one target.<jupyter_output><empty_output><jupyter_text>First let's recall what is **supervised learning**.> In **supervised learning** we use example data (_training data_) to inform our predictions of future data Note that this definition includes _classification_ and _regression_ problems. And there are a variety of ways we  can make predictions from past data.$k$-nearest neighbors is one such method of making predictions.  Who's Nearby? One strategy to make predictions on a new data is to just look at what _similar_ data points are like. ![](img/best_k_fs.png) We can say _nearby_ points are _similar_ to one another. There are a few different wasy to determine how "close" data points are to one another. Check out the [Level Up section on distance metrics](Level-Up:-Distance-Metrics) for some more detail.  Summary of $k$NN ![](img/knn-process.png)  Implementing in Scikit-Learn > [`KNeighborsClassifier`](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html) & [`KNeighborsRegressor`](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsRegressor.html) Let's try doing some basic classification on some data using the KNN algorithms.<jupyter_code>iris = sns.load_dataset('iris')
display(iris)
# Let's convert this over to NumPy array
X = iris.iloc[:,:2].to_numpy()
# Let's convert classes to numerical values
y = LabelEncoder().fit_transform(iris['species'])
y
f, ax = plt.subplots()

sns.scatterplot(x=X[:,0], y=X[:,1], ax=ax, hue=y, palette='colorblind')
ax.get_legend().remove()<jupyter_output><empty_output><jupyter_text>Training the KNN<jupyter_code>neigh = KNeighborsClassifier(n_neighbors=3, metric='euclidean')
neigh.fit(X, y)<jupyter_output><empty_output><jupyter_text>Make Some Predictions<jupyter_code># Made up data points
pred_pts = np.array([
    [7.0, 3.0],
    [8.0, 3.5],
    [7.0, 4.0],    
    [4.0, 3.0],
    [5.0, 3.0],
    [5.5, 4.0],
    [5.0, 2.0],
    [6.0, 2.5],
    [5.8, 3.5],
])<jupyter_output><empty_output><jupyter_text>Let's see these new points against the training data. Think about how they'll be made classified.<jupyter_code>f, ax = plt.subplots()

sns.scatterplot(x=X[:,0], y=X[:,1], ax=ax, hue=y, palette='colorblind')
sns.scatterplot(x=pred_pts[:,0], ax=ax, y=pred_pts[:,1], marker="*", s=200, edgecolor='black', color='magenta')
ax.get_legend().remove()
# Make predictions
pred_y = neigh.predict(pred_pts)
print(pred_y)
# Probabilities for KNN (how they voted)
for p,prob in zip(pred_y,neigh.predict_proba(pred_pts)):
    print(f'{p}: {prob}')
f, ax = plt.subplots()

sns.scatterplot(x=X[:,0],y=X[:,1], ax=ax, hue=y, palette='colorblind')
sns.scatterplot(x=pred_pts[:,0], ax=ax, y=pred_pts[:,1], hue=pred_y, palette='colorblind', marker="*", s=200, edgecolor='black')
ax.get_legend().remove()<jupyter_output><empty_output><jupyter_text>Let's see those predictions plotted with the other points after the classification.  The Pros and Cons Models have different use cases and it helps to understand the strengths and weaknesses  Advantages - Lazy learning (no training phase)- Simple algorithm to understand and implement  Disadvantages - Has to be kept in memory (small data with few features)- Not robust; doesn't generalize well- Soft boundaries are troublesome- "Curse of Dimensionality"  Classification with `sklearn.neighbors` $k$-Nearest Neighbors is a modeling technique that works for both regression and classification problems. Here we'll apply it to a version of the Titanic dataset.<jupyter_code>titanic = pd.read_csv('data/cleaned_titanic.csv')
titanic = titanic.iloc[:, :-2]
titanic.head()<jupyter_output><empty_output><jupyter_text>**For visualization purposes, we will use only two features for our first model.**<jupyter_code>X = titanic[['Age', 'Fare']]
y = titanic['Survived']
y.value_counts()<jupyter_output><empty_output><jupyter_text>Train-Test Split This dataset of course presents a binary classification problem, with our target being the `Survived` feature.<jupyter_code>X_train, X_test, y_train, y_test = train_test_split(X, y,
                                                    random_state=42,
                                                    test_size=0.25)<jupyter_output><empty_output><jupyter_text>Validation Split<jupyter_code>X_t, X_val, y_t, y_val = train_test_split(X_train, y_train,
                                          random_state=42,
                                          test_size=0.25)
knn = KNeighborsClassifier()

knn.fit(X_t, y_t)
print(f"training accuracy: {knn.score(X_t, y_t)}")
print(f"validation accuracy: {knn.score(X_val, y_val)}")

y_hat = knn.predict(X_val)

plot_confusion_matrix(confusion_matrix(y_val, y_hat), classes=['Perished', 'Survived'])
X_for_viz = X_t.sample(15, random_state=40)
y_for_viz = y_t[X_for_viz.index]

fig, ax = plt.subplots(figsize=(10, 10))
sns.scatterplot(X_for_viz['Age'], X_for_viz['Fare'], 
                hue=y_for_viz, palette={0: 'red', 1: 'green'}, 
                s=200, ax=ax)

ax.set_xlim(0, 80)
ax.set_ylim(0, 80)
plt.legend()
plt.title('Subsample of Training Data');<jupyter_output>C:\Users\IM\anaconda3\lib\site-packages\seaborn\_decorators.py:36: FutureWarning: Pass the following variables as keyword args: x, y. From version 0.12, the only valid positional argument will be `data`, and passing other arguments without an explicit keyword will result in an error or misinterpretation.
  warnings.warn(<jupyter_text>The $k$-NN algorithm works by simply storing the training set in memory, then measuring the distance from the training points to a new point.Let's drop a point from our validation set into the plot above.<jupyter_code>X_for_viz = X_t.sample(15, random_state=40)
y_for_viz = y_t[X_for_viz.index]

fig, ax = plt.subplots(figsize=(10, 10))
sns.scatterplot(X_for_viz['Age'], X_for_viz['Fare'],
                hue=y_for_viz, palette={0: 'red', 1: 'green'},
                s=200, ax=ax)

plt.legend()

#################^^^Old code^^^##############
####################New code#################

# Let's take one sample from our validation set and plot it
new_x = pd.DataFrame(X_val.loc[484]).T
new_y = y_val[new_x.index]

sns.scatterplot(new_x['Age'], new_x['Fare'], color='blue',
                s=200, ax=ax, label='New', marker='P')

ax.set_xlim(0, 100)
ax.set_ylim(0, 100);
new_x<jupyter_output><empty_output><jupyter_text>Then, $k$-NN finds the $k$ nearest points. $k$ corresponds to the `n_neighbors` parameter defined when we instantiate the classifier object. **If $k$ = 1, then the prediction for a point will simply be the value of the target for the nearest point.**  Different $k$ Values A big factor in this algorithm is choosing $k$ ![](img/k_vs_errors.png)  $k=1$<jupyter_code>knn = KNeighborsClassifier(n_neighbors=1)<jupyter_output><empty_output><jupyter_text>Let's fit our training data, then predict what our validation point will be based on the (one) closest neighbor.<jupyter_code>knn.fit(X_for_viz, y_for_viz)
knn.predict(new_x)<jupyter_output><empty_output><jupyter_text>**When we raise the value of $k$, $k$-NN will act democratically: It will find the $k$ closest points, and take a vote based on the labels.**  $k=3$ Let's raise $k$ to 3.<jupyter_code>knn3 = KNeighborsClassifier(n_neighbors=3)
knn3.fit(X_for_viz, y_for_viz)
knn3.predict(new_x)<jupyter_output><empty_output><jupyter_text>It's not easy to tell what which points are closest by eye.Let's update our plot to add indices.<jupyter_code>X_for_viz = X_t.sample(15, random_state=40)
y_for_viz = y_t[X_for_viz.index]

fig, ax = plt.subplots(figsize=(10,10))
sns.scatterplot(X_for_viz['Age'], X_for_viz['Fare'], hue=y_for_viz, 
                palette={0: 'red', 1: 'green'}, s=200, ax=ax)


# Now let's take another sample

# new_x = X_val.sample(1, random_state=33)
new_x = pd.DataFrame(X_val.loc[484]).T
new_x.columns = ['Age', 'Fare']
new_y = y_val[new_x.index]

print(new_x)
sns.scatterplot(new_x['Age'], new_x['Fare'], color='blue', 
                s=200, ax=ax, label='New', marker='P')
ax.set_xlim(0, 100)
ax.set_ylim(0, 100)
plt.legend()

#################^^^Old code^^^##############
####################New code#################

# add annotations one by one with a loop
for index in X_for_viz.index:
    ax.text(X_for_viz.Age[index]+0.7, X_for_viz.Fare[index],
            s=index, horizontalalignment='left', size='medium',
            color='black', weight='semibold')<jupyter_output>C:\Users\IM\anaconda3\lib\site-packages\seaborn\_decorators.py:36: FutureWarning: Pass the following variables as keyword args: x, y. From version 0.12, the only valid positional argument will be `data`, and passing other arguments without an explicit keyword will result in an error or misinterpretation.
  warnings.warn(
C:\Users\IM\anaconda3\lib\site-packages\seaborn\_decorators.py:36: FutureWarning: Pass the following variables as keyword args: x, y. From version 0.12, the only valid positional argument will be `data`, and passing other arguments without an explicit keyword will result in an error or misinterpretation.
  warnings.warn(<jupyter_text>We can use `sklearn`'s NearestNeighors object to see the exact calculations.<jupyter_code>df_for_viz = pd.merge(X_for_viz, y_for_viz, left_index=True, right_index=True)
neighbor = NearestNeighbors(3)
neighbor.fit(X_for_viz)
nearest = neighbor.kneighbors(new_x)

nearest
df_for_viz.iloc[nearest[1][0]]
new_x
# Use Euclidean distance to see how close they are to this point
print(((29-24)**2 + (33-25.4667)**2)**0.5)
print(((26-24)**2 + (16.1-25.4667)**2)**0.5)
print(((20-24)**2 + (15.7417-25.4667)**2)**0.5)<jupyter_output>9.041604331643805
9.57784260102451
10.515494519992865<jupyter_text>$k=5$ And with five neighbors?<jupyter_code>knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_for_viz, y_for_viz)
knn.predict(new_x)<jupyter_output><empty_output><jupyter_text>Observing Different $k$ Values Let's iterate through $k$, odd numbers 1 through 10, and see the predictions.<jupyter_code>for k in range(1, 10, 2):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_for_viz, y_for_viz)
    print(f'k={k}', knn.predict(new_x))<jupyter_output>k=1 [1]
k=3 [1]
k=5 [0]
k=7 [0]
k=9 [0]<jupyter_text>Which models were correct?<jupyter_code>new_y<jupyter_output><empty_output><jupyter_text>Scaling You may have suspected that we were leaving something out. For any distance-based algorithms, scaling is very important. Look at how the shape of the array changes before and after scaling. ![non-normal](img/nonnormal.png) ![normal](img/normalized.png) Let's look at our data_for_viz dataset:<jupyter_code>X_train, X_test, y_train, y_test = train_test_split(X, y,
                                                    random_state=42,
                                                    test_size=0.25)
X_t, X_val, y_t, y_val = train_test_split(X_train, y_train,
                                          random_state=42,
                                          test_size=0.25)

knn = KNeighborsClassifier(n_neighbors=5)

ss = StandardScaler()
X_ind = X_t.index
X_col = X_t.columns

X_t_s = pd.DataFrame(ss.fit_transform(X_t))
X_t_s.index = X_ind
X_t_s.columns = X_col

X_v_ind = X_val.index
X_val_s = pd.DataFrame(ss.transform(X_val))
X_val_s.index = X_v_ind
X_val_s.columns = X_col

knn.fit(X_t_s, y_t)
print(f"training accuracy: {knn.score(X_t_s, y_t)}")
print(f"Val accuracy: {knn.score(X_val_s, y_val)}")

y_hat = knn.predict(X_val_s)
# The plot_train() function just does what we did above.

plot_train(X_t, y_t, X_val, y_val)
plot_train(X_t_s, y_t, X_val_s, y_val, -2, 2, text_pos=0.1 )<jupyter_output>Age     Fare
484  24.0  25.4667<jupyter_text>Look at how much that changes things.Look at points 166 and 150.  Look at the group 621, 143, and 191. Now let's run our classifier on scaled data and compare to unscaled.<jupyter_code>X_train, X_test, y_train, y_test = train_test_split(X, y,
                                                    random_state=42,
                                                    test_size=0.25)
X_t, X_val, y_t, y_val = train_test_split(X_train, y_train,
                                          random_state=42,
                                          test_size=0.25)

# The predict_one() function prints predictions on a given point
# (#484) for k-nn models with k ranging from 1 to 10.

predict_one(X_t, X_val, y_t, y_val)
mm = MinMaxScaler()

X_t_s = pd.DataFrame(mm.fit_transform(X_t))
X_t_s.index = X_t.index
X_t_s.columns = X_t.columns

X_val_s = pd.DataFrame(mm.transform(X_val))
X_val_s.index = X_val.index
X_val_s.columns = X_val.columns


predict_one(X_t_s, X_val_s, y_t, y_val)<jupyter_output>[0]
[0]
[0]
[0]
[1]
[1]
[1]
[1]
[1]
[1]<jupyter_text>More Resources on Scaling https://sebastianraschka.com/Articles/2014_about_feature_scaling.html   http://datareality.blogspot.com/2016/11/scaling-normalizing-standardizing-which.html  $k$ and the Bias-Variance Tradeoff<jupyter_code>X_train, X_test, y_train, y_test = train_test_split(X, y,
                                                    random_state=42,
                                                    test_size=0.25)
# Let's slowly increase k and see what happens to our accuracy scores.

kf = KFold(n_splits=5)

k_scores_train = {}
k_scores_val = {}


for k in range(1, 20):
    knn = KNeighborsClassifier(n_neighbors=k)
    accuracy_score_t = []
    accuracy_score_v = []
    for train_ind, val_ind in kf.split(X_train, y_train):
        
        X_t, y_t = X_train.iloc[train_ind], y_train.iloc[train_ind] 
        X_v, y_v = X_train.iloc[val_ind], y_train.iloc[val_ind]
        mm = MinMaxScaler()
        
        X_t_ind = X_t.index
        X_v_ind = X_v.index
        
        X_t = pd.DataFrame(mm.fit_transform(X_t))
        X_t.index = X_t_ind
        X_v = pd.DataFrame(mm.transform(X_v))
        X_v.index = X_v_ind
        
        knn.fit(X_t, y_t)
        
        y_pred_t = knn.predict(X_t)
        y_pred_v = knn.predict(X_v)
        
        accuracy_score_t.append(accuracy_score(y_t, y_pred_t))
        accuracy_score_v.append(accuracy_score(y_v, y_pred_v))
        
        
    k_scores_train[k] = np.mean(accuracy_score_t)
    k_scores_val[k] = np.mean(accuracy_score_v)
k_scores_train
k_scores_val
fig, ax = plt.subplots(figsize=(15, 15))

ax.plot(list(k_scores_train.keys()), list(k_scores_train.values()),
        color='red', linestyle='dashed', marker='o',  
         markerfacecolor='blue', markersize=10, label='Train')
ax.plot(list(k_scores_val.keys()), list(k_scores_val.values()),
        color='green', linestyle='dashed', marker='o',  
         markerfacecolor='blue', markersize=10, label='Val')
ax.set_xlabel('k')
ax.set_ylabel('Accuracy')
plt.legend();<jupyter_output><empty_output><jupyter_text>The Relation Between $k$ and Bias/Variance > Small $k$ values leads to overfitting, but larger $k$ values tend towards underfitting ![alt text](img/K-NN_Neighborhood_Size_print.png) > From [Machine Learning Flashcards](https://machinelearningflashcards.com/) by <NAME><jupyter_code>mm = MinMaxScaler()

X_train_ind = X_train.index
X_train = pd.DataFrame(mm.fit_transform(X_train))
X_train.index = X_train_ind

X_test_ind = X_test.index
X_test =  pd.DataFrame(mm.transform(X_test))
X_test.index = X_test_ind

knn = KNeighborsClassifier(n_neighbors=9)
knn.fit(X_train, y_train)

print(f"training accuracy: {knn.score(X_train, y_train)}")
print(f"Test accuracy: {knn.score(X_test, y_test)}")

y_hat = knn.predict(X_test)

plot_confusion_matrix(confusion_matrix(y_test, y_hat), classes=['Perished', 'Survived'])
recall_score(y_test, y_hat)
precision_score(y_test, y_hat)<jupyter_output><empty_output><jupyter_text>Level Up: Distance Metrics > The "closeness" of data points → proxy for similarity ![](img/distances.png) **Minkowski Distance**:$$dist(A,B) = (\sum_{k=1}^{N} |a_k - b_k|^c)^\frac{1}{c} $$<jupyter_code>#Minkowski is a generalization. With a value of 2 it is the same as Euclidean<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13093021943927344, 'fraction_numerical': 0.0249901280532521, 'mean_word_length': 4.522741433021807, 'pattern_counts': {'":': 0, '<': 92, '<?xml version=': 0, '>': 97, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '24', 'dir': 'jupyter-structured-clean-dedup', 'id': '55225', 'license': 'MIT', 'n_tokens_mistral': 6760, 'n_tokens_neox': 6371, 'n_words': 1483, 'path': 'Phase_3/ds-k-nearest_neighbors-main/knn.ipynb', 'repo_name': 'ismizu/ds-east-042621-lectures', 'size': '17732'}