<jupyter_start><jupyter_text>Nearest-Neighbor MethodsThis is a python implementation of the Nearest-Neighbor algorithms presented in Section 2.3.2.First, let's define the notations used in this example:   * $\mathbf{X}$ is a matrix of inputs with size $N \times p$, where $N$ is the number of obervations and $p$ is the number of columns/ features / dimension.          * Note that              $$\mathbf{X} = \begin{bmatrix}x_{11} & x_{12} & \cdots & x_{1p} \\ x_{21} & x_{22} & \cdots & x_{2p} \\ \vdots & \cdots & \cdots & \vdots\\x_{N1} & \cdots & \cdots & x_{Np}\end{bmatrix}$$              where $x_{ij}$ denotes the $i^{th}$ observation (row) of the $j^{th}$ feature of $\mathbf{X}$, $X_k$ denotes the $k^{th}$ column of $\mathbf{X}$ and $x_i$ denotes the $i^{th}$ row of $\mathbf{X}$.          * $\mathbf{Y}$ is a matrix of outputs with size $N \times 1$.      * $k$ denotes the number of nighborhood.      * Any variables with $\hat{}$ on top  denote predicted / estimated variables.      * $\mathbf{e}$ denotes a vector of ones with an appropriate size. Nearest-Neighbor ModelK-nearest neighbors model has the form:$$\hat{\mathbf{Y}} = \frac{1}{k} \sum_{x_{i}\in N_k(\mathbf{X})} \mathbf{Y}_i$$where $N_k(\mathbf{X})$ is the neighborhood of $\mathbf{X}$ defined by the $k$ closest points $x_{i}$ in the training sample.From the above equation, there are **3 parts** we need to define/compute:   * **Closeness of data points** (Euclidean distance as an example)   * **Nearest neighboors of a data point**   * **Prediction as given by the above equation**These 3 parts are the main building blocks of nearest-neighbor algoritm. However, there are more advanced methods to compute each part.  Python's implementation using Mixture datasetHere, we'll try to implement the 3 parts of the algorithm from scratch.<jupyter_code># import necessary packages
import sys
import numpy as np
from ml_datasets.esl import Mixture
from ml_datasets.utils import plot_2D
# loading dataset
mixture = Mixture()
x, y = mixture.load()
# check the input and output shapes
print("x: {}, y: {}".format(x.shape, y.shape))
# visualize the data
plt = plot_2D(x, y, "ESL-Mixture Dataset", axis='on')<jupyter_output><empty_output><jupyter_text>Part 1: Compute the closeness of data pointsIn this example, we use euclidean distance, which is defined as:$$d(x_1, x_2) = d(x_2, x_1) = \sqrt{(x_{11} - x_{21}) ^ 2 + (x_{12} - x_{22}) ^ 2 + \cdots + (x_{1p} - x_{2p}) ^ 2}$$The following method calculates this distance:<jupyter_code>def euclidean_distance(x1, x2):
    return np.sqrt(np.sum(np.square(x1 - x2)))<jupyter_output><empty_output><jupyter_text>Part 2: Find the nearest neighboors of a data pointThe following method locates the $k$ nearest of a data point using Euclidean distance. It returns $k$ indexes of training data points that are the closest to the data point of interest.<jupyter_code>def get_neighbor(i, x_row, x, num_neighbor=1):
    distance = np.zeros(x.shape[0])
    for j, x_ in enumerate(x):
        distance[j] = euclidean_distance(x_row, x_)

    return np.argsort(distance)[:num_neighbor]<jupyter_output><empty_output><jupyter_text>Part 3: Compute the PredictionAfter the first two parts are done, the prediction is then computed using the following equation:$$\hat{\mathbf{Y}} = \frac{1}{k} \sum_{x_{i}\in N_k(\mathbf{X})} \mathbf{Y}_i$$And the final classification output is given as:$\hat{\mathbf{G}} = \begin{cases}    \color{orange}{\text{ORANGE}} \color{black}{\text{ or 1}}, & \text{if } \hat{\mathbf{Y}} > 0.5\\    \color{blue}{\text{BLUE}} \color{black}{\text{ or 0}},              & \text{if } \hat{\mathbf{Y}} \leq 0.5\end{cases}$The following method implements these equations:<jupyter_code>def classify(x_test, x_train, y, num_neighbor=1, threshold=0.5):
    y_hat = np.zeros(x_test.shape[0]).astype(float)
    G_hat = np.zeros_like(y_hat).astype(int)
    for i, x_row in enumerate(x_test):
        index_neighbor = get_neighbor(i, x_row, x_train, num_neighbor=num_neighbor)

        y_hat[i] = (1.000 / num_neighbor) * np.sum(y[index_neighbor]).astype(float)

        if y_hat[i] > threshold:
            G_hat[i] = 1
        else:
            G_hat[i] = 0
    
    return G_hat<jupyter_output><empty_output><jupyter_text>Since this algorithm is not a parametric model, i.e., there is no parameters to use to calculate the boundary equation, we need to generate some possible predictions in our input space and plot the contour of these predictions.The next several lines of codes generate a grid of data points in the input space.<jupyter_code># prepare data points for creating decision boundary
step = 0.05
x_1_range = np.arange(min(x[:, 0]), max(x[:, 0]), step)
x_2_range = np.arange(min(x[:, 1]), max(x[:, 1]), step)
x_1, x_2 = np.meshgrid(x_1_range,  x_2_range)
x_12 = np.concatenate((x_1.ravel().reshape(-1, 1), x_2.ravel().reshape(-1, 1)), axis=1)<jupyter_output><empty_output><jupyter_text>When we are ready to show the classification results, we can use the following method to plot them.<jupyter_code># this method is used to plot the classification results (ground truth vs prediction and decision boundary)
def plot_classification(x, y, G_hat, Z, num_neighbor):
    BLUE, ORANGE = "#57B5E8", "#E69E00"
    plt.figure(figsize=(8, 8))
    plt.scatter(x[:, 0][y==1], x[:, 1][y==1], s=100, marker="o", edgecolors=ORANGE, facecolors="none", label='ground truth - class 1')
    plt.scatter(x[:, 0][y==0], x[:, 1][y==0], s=100, marker="o", edgecolors=BLUE, facecolors="none", label='ground truth - class 0')
    plt.scatter(x[:, 0][G_hat==1] + 0.03, x[:, 1][G_hat==1], s=100, marker="*", edgecolors=ORANGE, facecolors="none", label='prediction - class 1')
    plt.scatter(x[:, 0][G_hat==0] + 0.03, x[:, 1][G_hat==0], s=100, marker="*", edgecolors=BLUE, facecolors="none", label='prediction - class 0')
    plt.contour(x_1, x_2, Z.reshape(x_1.shape), colors="black", levels=[0], linewidths=1)
    plt.legend()
    plt.axis("off")
    plt.title("{}-Nearest-Neighbor Classification".format(num_neighbor))
    plt.show()<jupyter_output><empty_output><jupyter_text>Classification results using 15-nearest neighborsThe book shows some result using 15-nearest neighbors<jupyter_code>num_neighbor = 15
threshold = 0.5
G_hat = classify(x, x, y, num_neighbor=num_neighbor, threshold=threshold)
Z = classify(x_12, x, y, num_neighbor=num_neighbor, threshold=threshold)
plot_classification(x, y, G_hat, Z, num_neighbor)<jupyter_output><empty_output><jupyter_text>Classification results using 1-nearest neighborThe book also shows some result using 1-nearest neighbor<jupyter_code>num_neighbor = 1
threshold = 0.5
G_hat = classify(x, x, y, num_neighbor=num_neighbor, threshold=threshold)
Z = classify(x_12, x, y, num_neighbor=num_neighbor, threshold=threshold)
plot_classification(x, y, G_hat, Z, num_neighbor)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14362866734783244, 'fraction_numerical': 0.022770398481973434, 'mean_word_length': 4.782278481012658, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 35, 'https://': 0, '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': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '85262', 'license': 'MIT', 'n_tokens_mistral': 2430, 'n_tokens_neox': 2304, 'n_words': 703, 'path': 'Notebooks/Chapter 02 - Overview of Supervised Learning/2.3.2 Nearest-Neighbor Methods.ipynb', 'repo_name': 'abkoesdw/ESL', 'size': '6851'}