<jupyter_start><jupyter_text>*This notebook is part of  course materials for CS 345: Machine Learning Foundations and Practice at Colorado State University.Original versions were created by <NAME>.The content is availabe [on GitHub](https://github.com/asabenhur/CS345).**The text is released under the [CC BY-SA license](https://creativecommons.org/licenses/by-sa/4.0/), and code is released under the [MIT license](https://opensource.org/licenses/MIT).*<jupyter_code>import numpy as np
from matplotlib import pylab as plt
%autosave 0
%matplotlib inline<jupyter_output><empty_output><jupyter_text>Nearest neighbor classificationRecall the nearest neighbor classifier:```Nearest neighbor classifier- Find the example in the training data that is closest to  the example that needs to be classified.- Return its label```  Nearest neighbors for regressionWe can easily turn our nearest neighbor classifier into a regression method.  In-fact, there is nothing that need change in our implementation - by returning the label of the nearest neighbor, it's already a regression method!<jupyter_code>def distance(x1, x2):
    return np.sqrt(np.dot(x1-x2, x1-x2))

class nearest_neighbor:
    def __init__(self):
        pass
    def fit(self, X, y):
        self.X = X
        self.y = y
    def get_nearest(self, x):
        distances = [distance(x, self.X[i]) for i in range(len(self.X))]
        return np.argmin(distances)
    def predict(self, x) :
        return self.y[self.get_nearest(x)]<jupyter_output><empty_output><jupyter_text>To illustrate that, let's run the algorithm on a simple one-dimensional regression problem:<jupyter_code>from numpy.random import default_rng
rng = default_rng(1)
X = np.sort(5 * rng.random(40))
y = np.sin(X) + rng.normal(0, 0.05, size=(len(X)))
X = X[:, np.newaxis]
print("shape of training data: ", X.shape, y.shape)

nn = nearest_neighbor()
nn.fit(X, y)

X_test = np.linspace(0, 5, 500)[:, np.newaxis]
y_pred = np.array([nn.predict(X_test[i]) for i in range(len(X_test))])
plt.scatter(X, y, color='orange', label='data')
plt.plot(X_test, y_pred, label='prediction')

plt.legend();<jupyter_output>shape of training data:  (40, 1) (40,)<jupyter_text>Running timePredicting the class of a given input requires iteration over the entire training set of $N$ training examples.  Each step requires the computation of the distance to some training example, which requires time proportional to the number of dimensions.  In CS-speak, we say that it is $O(d)$ (see e.g. this article on [big-O notation](https://en.wikipedia.org/wiki/Big_O_notation)).  Therefore, the overall training time is proportional to $N\cdot d$, i.e. is $O(N\cdot d)$.  This can be expensive for large datasets.  Pros and cons of nearest neighbor classification Pros* Simple to understand and implement* Trivial to train* Works for just about any learning problem:  classification, regression etc.* Highly expressive - decision boundary is not limited to any particular form* Easy to explain the results Cons* Expensive during testing* Accuracy can be low for high dimensional data; usually not the best performing classifierThe drawbacks of the nearest neighbor classifier can be addressed to some extent as described next.  Improving the running time of nearest neighbor methodsSolutions for improving the running time:* Condensing the dataset:  Retain only a relatively small fraction of the training data, as much of it is likely to be redundant.* Efficient data structures for representing and searching the training data.  These include KD-tree, ball-tree, vantage-point tree.  These tree-based methods can reduce the search time to be $O(\log N)$.  The KD-tree and ball-tree methods are implemented in scikit-learn.  Improving the accuracy of the basic nearest neighbor classifier* Feature selection / removal of noisy features* Feature normalization / rescaling* Base the decision on multiple nearest neighbors.  This is referred to as **k-NN**.  k-nearest neighbors (k-NN)In this variant of the nearest neighbor algorithm the classification is decided based on the $k$ nearest neighbors of a test example.  How do we choose the predicted class label?  Typically a majority vote.  The distances can be used as weights for each vote.Let us illustrate the difference this makes in the decision boundary:<jupyter_code>from matplotlib.colors import ListedColormap

def plot_boundary(classifier, X, y, num_plots=1, plot_num=1, title=None) :
    """
    code based on:
    https://scikit-learn.org/stable/auto_examples/neighbors/plot_classification.html
    """
    classifier.fit(X, y)
    # color maps
    cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
    cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
    # create a two dimensional grid of points
    h = .02  # grid size
    x_min, x_max = X[:, 0].min() - 0.2, X[:, 0].max() + 0.2
    y_min, y_max = X[:, 1].min() - 0.2, X[:, 1].max() + 0.2
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    Z = classifier.predict(np.c_[xx.ravel(), yy.ravel()])

    # plot the predictions on the grid
    Z = Z.reshape(xx.shape)
    
    ax = plt.subplot(1, num_plots, plot_num)

    plt.pcolormesh(xx, yy, Z, cmap=cmap_light)

    # plot the training points
    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold, alpha=0.5)
    
    plt.xlim(x_min, x_max)
    plt.ylim(y_min, y_max)
    if title is not None :
        plt.title(title)<jupyter_output><empty_output><jupyter_text>Let's compare a one-nearest neighbor with k-NN:<jupyter_code>from sklearn.datasets import make_classification
X,y = make_classification(n_samples=100, n_features=2, n_informative=2, n_redundant=0, n_repeated=0, n_classes=2, n_clusters_per_class=1, class_sep=0.35, random_state=1)

from sklearn.neighbors import KNeighborsClassifier
plt.figure(figsize=(10,5))
classifier = KNeighborsClassifier(1)
plot_boundary(classifier, X, y, 2, 1, 'one-nearest-neighbor')

classifier = KNeighborsClassifier(10)
plot_boundary(classifier, X, y, 2, 2, '10-nearest-neighbor')

from sklearn.datasets import load_breast_cancer
X, y = load_breast_cancer(return_X_y = True)
X.shape, y.shape
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, 
    test_size=0.3, shuffle=True, random_state=1)
num_neighbors = [1,3,5,10,15,20,25,30]
test_accuracy = []
training_accuracy = []
for k in num_neighbors :
    classifier = KNeighborsClassifier(k, p=2, weights='uniform')
    classifier.fit(X_train, y_train)
    y_pred = classifier.predict(X_test)
    test_accuracy.append(np.sum(y_pred == y_test)/len(y_test))
    y_pred = classifier.predict(X_train)
    training_accuracy.append(np.sum(y_pred == y_train)/len(y_train))
     
plt.plot(num_neighbors, training_accuracy, 'or', alpha=0.5, label = 'training set')
plt.xlabel('number of neighbors')
plt.ylabel('accuracy');
plt.plot(num_neighbors, test_accuracy, 'ob', alpha=0.5, label = 'test set')
plt.legend();<jupyter_output><empty_output><jupyter_text>As we can see, using the k-NN classifier with $k>1$ instead of the one-nearest neighbor classifier leads to improved accuracy.For the one-nearest neighbor classifier we clearly see what is called **overfitting**:  perfect accuracy on the training set, and much lower accuracy on the test set.  Question* Why do you expect the k-NN classifier with $k>1$ to perform better than the one-nearest neighbor classifier?  Distance functions The Euclidean distance is one of many ways for computing distance.  Recall that the Euclidean distance is defined by:$$d_2(\mathbf{x}, \mathbf{x}')^2 = ||\mathbf{x} - \mathbf{x}'||^2_2(\mathbf{x} - \mathbf{x}')^\top (\mathbf{x} - \mathbf{x}') = \sum_{i=1}^d (x_i - x_i')^2,$$where $||\cdot||_2$ is the $L_2$ or Euclidean norm of a vector.The **Manhattan distance** is another common distance function that derives from the $L_1$ norm:$$d_1(\mathbf{x}, \mathbf{x}') = ||\mathbf{x} - \mathbf{x}'||_1\sum_{i=1}^d |x_i - x_i'|,$$where $|x|$ is the absolute value.The **Minkowski distance** is a generalization of both of these distances.  It has a parameter $p\geq 0$ and is defined by:$$d_p(\mathbf{x}, \mathbf{x}') = \left( \sum_{i=1}^d |x_i - x_i'|^p \right)^{1/p}.$$The Euclidean distance is a special case with $p=2$, and is also called the $L_2$ distance; the Manhattan distance is another special case with $p=1$, and is also called the $L_1$ distance.The $L_1$ and $L_2$ distances are the most commonly used in machine learning.  The geometry of the L$_1$ distanceLet's talk about circles.  A circle is the set of points that are a fixed distance from its center.  A circle with respect to the $L_1$ distance looks quite different than what we are used to.In fact, as shown on the right, a circle under the Manhattan distance looks like a square!  For another interesting property consider the two points on the right:  the green line is the shortest path in the Euclidean distance; in the Manhattan distance, the shortest path is not unique, and the blue, green, and yellow paths all have the same distance.  Question* What is the equation for the points on a unit circle in two dimensions under the $L_1$ and $L_2$ distances? The different geometry of the two ways of measuring distance makes their Voronoi diagrams different, which translates to a difference in the shape of the decision boundary.   At this point, let's see which distance works better for our example dataset.<jupyter_code>num_neighbors = [1,3,5,10,15,20,25,30]
accuracy_l1 = []
accuracy_l2 = []
for k in num_neighbors :
    classifier = KNeighborsClassifier(k, p=1, weights='uniform')                              
    classifier.fit(X_train, y_train)
    y_pred = classifier.predict(X_test)
    accuracy_l1.append(np.sum(y_pred == y_test)/len(y_test))

    classifier = KNeighborsClassifier(k, p=2, weights='uniform')
    classifier.fit(X_train, y_train)
    y_pred = classifier.predict(X_test)
    accuracy_l2.append(np.sum(y_pred == y_test)/len(y_test))
    
plt.plot(num_neighbors, accuracy_l1, 'ob', alpha=0.5, label='L1 distance')
plt.plot(num_neighbors, accuracy_l2, 'dg', alpha=0.5, label='L2 distance')
plt.legend()
plt.xlabel('number of neighbors')
plt.ylabel('accuracy');<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10901120311738918, 'fraction_numerical': 0.016171456405260593, 'mean_word_length': 4.6655629139072845, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 27, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '313868', 'license': 'MIT', 'n_tokens_mistral': 3406, 'n_tokens_neox': 3231, 'n_words': 1137, 'path': 'notebooks/module02_05_more_nearest_neighbors.ipynb', 'repo_name': 'lottieandrews/CS345', 'size': '10270'}