machine-learning/classification/k-nearest-neighbors-classification-implementation-from-scratch.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "k-Nearest Neighbors Classification Implementation from Scratch",
      "provenance": [],
      "authorship_tag": "ABX9TyMrAZsvUwqitGpvTM1l8zNu"
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dZe5Fp3fzscj"
      },
      "source": [
        "# ***k*-Nearest Neighbors Classification Implementation from Scratch**\n",
        "\n",
        "*By Carlos Santiago Bañón*\n",
        "\n",
        "* **Year:** 2020\n",
        "* **Technologies:** Python, Pandas, NumPy, Matplotlib\n",
        "* **Areas**: Machine Learning, Classification\n",
        "* **Keywords:** `classification`, `k-nn`, `k-nn-classification`, `k-nearest-neighbors`, `machine-learning`\n",
        "* **Description:** This notebook presents an implementation of *k*-nearest neighbors classification from scratch. The data used is a preprocessed version of the Kaggle Titanic dataset hosted in the GitHub repository for this notebook."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UX94UXm8z7Nv"
      },
      "source": [
        "## 1. Import Statements\n",
        "---"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dnrBRGX3z9mQ"
      },
      "source": [
        "import matplotlib.pyplot as plt\n",
        "import numpy as np\n",
        "import pandas as pd"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8wyC0ZRn0LHm"
      },
      "source": [
        "## 2. Load the Data\n",
        "---"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LWxu2qDP2fsE"
      },
      "source": [
        "First, we import the preprocessed Kaggle Titanic dataset hosted in the GitHub repository for this notebook."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mM6bKcvH0Nva"
      },
      "source": [
        "# Import the data into Pandas DataFrames.\n",
        "train_df = pd.read_csv('https://bit.ly/39AQRJj')\n",
        "test_df = pd.read_csv('https://bit.ly/3aoJzHG')\n",
        "y_test_df = pd.read_csv('https://bit.ly/2YxfKzi')"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 419
        },
        "id": "jZhgO8OJ0a_E",
        "outputId": "5d17277f-788e-456a-db19-b8491b765821"
      },
      "source": [
        "# Show the training set.\n",
        "train_df"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>Age</th>\n",
              "      <th>Survived</th>\n",
              "      <th>Pclass</th>\n",
              "      <th>SibSp</th>\n",
              "      <th>Fare</th>\n",
              "      <th>Gender</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>2</td>\n",
              "      <td>0</td>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>2</td>\n",
              "      <td>1</td>\n",
              "      <td>3</td>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>3</td>\n",
              "      <td>0</td>\n",
              "      <td>3</td>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>...</th>\n",
              "      <td>...</td>\n",
              "      <td>...</td>\n",
              "      <td>...</td>\n",
              "      <td>...</td>\n",
              "      <td>...</td>\n",
              "      <td>...</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>886</th>\n",
              "      <td>2</td>\n",
              "      <td>0</td>\n",
              "      <td>2</td>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>887</th>\n",
              "      <td>2</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>2</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>888</th>\n",
              "      <td>2</td>\n",
              "      <td>0</td>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "      <td>2</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>889</th>\n",
              "      <td>2</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>2</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>890</th>\n",
              "      <td>3</td>\n",
              "      <td>0</td>\n",
              "      <td>3</td>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "<p>891 rows × 6 columns</p>\n",
              "</div>"
            ],
            "text/plain": [
              "     Age  Survived  Pclass  SibSp  Fare  Gender\n",
              "0      2         0       3      1     0       0\n",
              "1      3         1       1      1     3       1\n",
              "2      2         1       3      0     1       1\n",
              "3      3         1       1      1     3       1\n",
              "4      3         0       3      0     1       0\n",
              "..   ...       ...     ...    ...   ...     ...\n",
              "886    2         0       2      0     1       0\n",
              "887    2         1       1      0     2       1\n",
              "888    2         0       3      1     2       1\n",
              "889    2         1       1      0     2       0\n",
              "890    3         0       3      0     0       0\n",
              "\n",
              "[891 rows x 6 columns]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 419
        },
        "id": "Hg4hhA3F0c4b",
        "outputId": "8fdb4414-4401-4b00-83b3-881625d481c6"
      },
      "source": [
        "# Show the test set.\n",
        "test_df"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>Age</th>\n",
              "      <th>Pclass</th>\n",
              "      <th>SibSp</th>\n",
              "      <th>Fare</th>\n",
              "      <th>Gender</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>3</td>\n",
              "      <td>3</td>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>4</td>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>5</td>\n",
              "      <td>2</td>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>2</td>\n",
              "      <td>3</td>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>2</td>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>...</th>\n",
              "      <td>...</td>\n",
              "      <td>...</td>\n",
              "      <td>...</td>\n",
              "      <td>...</td>\n",
              "      <td>...</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>413</th>\n",
              "      <td>3</td>\n",
              "      <td>3</td>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>414</th>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>415</th>\n",
              "      <td>3</td>\n",
              "      <td>3</td>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>416</th>\n",
              "      <td>3</td>\n",
              "      <td>3</td>\n",
              "      <td>0</td>\n",
              "      <td>1</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>417</th>\n",
              "      <td>3</td>\n",
              "      <td>3</td>\n",
              "      <td>1</td>\n",
              "      <td>2</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "<p>418 rows × 5 columns</p>\n",
              "</div>"
            ],
            "text/plain": [
              "     Age  Pclass  SibSp  Fare  Gender\n",
              "0      3       3      0     0       0\n",
              "1      4       3      1     0       1\n",
              "2      5       2      0     1       0\n",
              "3      2       3      0     1       0\n",
              "4      2       3      1     1       1\n",
              "..   ...     ...    ...   ...     ...\n",
              "413    3       3      0     1       0\n",
              "414    3       1      0     3       1\n",
              "415    3       3      0     0       0\n",
              "416    3       3      0     1       0\n",
              "417    3       3      1     2       0\n",
              "\n",
              "[418 rows x 5 columns]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ekK9B6Yd0khJ"
      },
      "source": [
        "# Set up the learning matrices.\n",
        "X_train = train_df.drop('Survived', axis=1, inplace=False).to_numpy()\n",
        "y_train = train_df[['Survived']].to_numpy()\n",
        "X_test = test_df.to_numpy()\n",
        "y_test = y_test_df.drop('PassengerId', axis=1, inplace=False).to_numpy()"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E7P0ZAo60rXW"
      },
      "source": [
        "## 3. *k*-Nearest Neighbors Classification\n",
        "---"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "18K0JkTx0upe"
      },
      "source": [
        "### 3.1. Define the *k*-NN Model"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3Upnc3t38mGf"
      },
      "source": [
        "def knn_distances(X_train, X_test, k):\n",
        "\n",
        "  \"\"\"\n",
        "  Find the k-nearest neighbors of X_test in X_train.\n",
        "  \"\"\"\n",
        "  \n",
        "  # Calculate the Eucledian distance.\n",
        "  distances = -2 * X_train @ X_test.T + np.sum(X_test ** 2, axis=1) + np.sum(X_train ** 2, axis=1)[:, np.newaxis]\n",
        "  distances[distances < 0] = 0\n",
        "  distances = distances ** .5\n",
        "\n",
        "  # Get the indices of the sorted items.\n",
        "  indices = np.argsort(distances, 0)\n",
        "\n",
        "  # Sort the distances.\n",
        "  distances = np.sort(distances, 0)\n",
        "\n",
        "  # Return the top-k distances.\n",
        "  return indices[0:k, :], distances[0:k, :]"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Tpy0X1VP8wkC"
      },
      "source": [
        "def knn_predictions(X_train, y_train, X_test, k=3):\n",
        "    \n",
        "  \"\"\"\n",
        "  Use X_train and y_train to predict X_test.\n",
        "  \"\"\"\n",
        "\n",
        "  indices, distances = knn_distances(X_train, X_test, k)\n",
        "  y_train = y_train.flatten()\n",
        "  rows, columns = indices.shape\n",
        "  predictions = list()\n",
        "\n",
        "  for j in range(columns):\n",
        "\n",
        "    temp = list()\n",
        "\n",
        "    for i in range(rows):\n",
        "\n",
        "      cell = indices[i][j]\n",
        "      temp.append(y_train[cell])\n",
        "\n",
        "    # Get the mode value.\n",
        "    predictions.append(max(temp, key=temp.count))\n",
        "\n",
        "  predictions = np.array(predictions)\n",
        "\n",
        "  return predictions"
      ],
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XPgG4NLG8zew"
      },
      "source": [
        "def knn_accuracy(y_test, predictions):\n",
        "\n",
        "  \"\"\"\n",
        "  Evaluate the accuracy of the knn_predictions.\n",
        "  \"\"\"\n",
        "\n",
        "  x = y_test.flatten() == predictions.flatten()\n",
        "  grade = np.mean(x)\n",
        "\n",
        "  return np.round(grade * 100, 2)"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eJi74y7y04i_"
      },
      "source": [
        "### 3.2. Run the *k*-NN Model"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RWz87jzE86HP",
        "outputId": "f77145b8-5e47-4fc9-87c3-66686f29a293"
      },
      "source": [
        "# Set the max k and accuracies array.\n",
        "num_k = 35\n",
        "accuracies = np.empty(num_k)\n",
        "\n",
        "for i in range(0, num_k):\n",
        "\n",
        "  # Train and run the KNN model.\n",
        "  knn_pred = knn_predictions(X_train, y_train, X_test, k = i + 1)\n",
        "\n",
        "  # Compute the accuracy.\n",
        "  accuracies[i] = knn_accuracy(y_test, knn_pred)\n",
        "\n",
        "  # Show the progress.\n",
        "  print(\"Training for k =\", i + 1, \"> Accuracy:\", accuracies[i])"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Training for k = 1 > Accuracy: 73.44\n",
            "Training for k = 2 > Accuracy: 73.44\n",
            "Training for k = 3 > Accuracy: 80.38\n",
            "Training for k = 4 > Accuracy: 81.34\n",
            "Training for k = 5 > Accuracy: 84.93\n",
            "Training for k = 6 > Accuracy: 86.6\n",
            "Training for k = 7 > Accuracy: 84.93\n",
            "Training for k = 8 > Accuracy: 83.25\n",
            "Training for k = 9 > Accuracy: 84.21\n",
            "Training for k = 10 > Accuracy: 84.45\n",
            "Training for k = 11 > Accuracy: 86.6\n",
            "Training for k = 12 > Accuracy: 86.84\n",
            "Training for k = 13 > Accuracy: 85.89\n",
            "Training for k = 14 > Accuracy: 85.65\n",
            "Training for k = 15 > Accuracy: 86.6\n",
            "Training for k = 16 > Accuracy: 86.12\n",
            "Training for k = 17 > Accuracy: 85.41\n",
            "Training for k = 18 > Accuracy: 86.12\n",
            "Training for k = 19 > Accuracy: 86.36\n",
            "Training for k = 20 > Accuracy: 86.12\n",
            "Training for k = 21 > Accuracy: 87.32\n",
            "Training for k = 22 > Accuracy: 87.56\n",
            "Training for k = 23 > Accuracy: 86.84\n",
            "Training for k = 24 > Accuracy: 85.41\n",
            "Training for k = 25 > Accuracy: 88.28\n",
            "Training for k = 26 > Accuracy: 85.41\n",
            "Training for k = 27 > Accuracy: 89.71\n",
            "Training for k = 28 > Accuracy: 87.32\n",
            "Training for k = 29 > Accuracy: 88.76\n",
            "Training for k = 30 > Accuracy: 87.32\n",
            "Training for k = 31 > Accuracy: 87.8\n",
            "Training for k = 32 > Accuracy: 84.21\n",
            "Training for k = 33 > Accuracy: 86.36\n",
            "Training for k = 34 > Accuracy: 83.97\n",
            "Training for k = 35 > Accuracy: 89.47\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1RcBpok-6WUE"
      },
      "source": [
        "### 3.3. Show the Accuracy"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_sVomIVR88p7",
        "outputId": "767c74c5-4e36-46ad-c441-0d8682603c27"
      },
      "source": [
        "# Show the accuracies.\n",
        "print(accuracies)"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[73.44 73.44 80.38 81.34 84.93 86.6  84.93 83.25 84.21 84.45 86.6  86.84\n",
            " 85.89 85.65 86.6  86.12 85.41 86.12 86.36 86.12 87.32 87.56 86.84 85.41\n",
            " 88.28 85.41 89.71 87.32 88.76 87.32 87.8  84.21 86.36 83.97 89.47]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 299
        },
        "id": "GeITvcb1893d",
        "outputId": "bccff8b0-d671-4933-da02-d7bf178898fa"
      },
      "source": [
        "# Plot the accuracies.\n",
        "fig = plt.figure()\n",
        "ax = plt.axes()\n",
        "x = np.linspace(1, num_k, num_k)\n",
        "ax.bar(x, accuracies, color='orange')\n",
        "\n",
        "# Set the labels.\n",
        "plt.title('Accuracy vs. $k$')\n",
        "plt.xlabel('$k$')\n",
        "plt.ylabel('Accuracy');"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEaCAYAAAAWvzywAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAUaUlEQVR4nO3dfZBldX3n8ffHGeTRDSgTRECHXQ3IIg/uhNXVNS6TTYhP4GoIGGXWMkFr1QW1XNTaKjGVpDSbxIc1RQolOImOIwKCa1UeXALlwxrMgASQkQDKYwYYNhAERAS++8c5vWmb7p47Q5+59/bv/arq6nvOfTifPjP9uad/99zfTVUhSWrHU8YdQJK0c1n8ktQYi1+SGmPxS1JjLH5JaozFL0mNsfglqTEWvyQ1xuKXlqEktyU5etw5NJksfk20JJcluTfJruPOMi2S7APsD2wedxZNJotfEyvJauDfAwW8Zidve+XO3N4SewFwY1U9PO4gmkwWvybZKcDfAJ8B1s2+IslBSS5MsjXJ/03yycXW99dVkufOWv5Mkt+etXxzkjOSXA08mOS/J7kpyQ+TXJfktdvKkOS9SS6Yc7tPJPn43B+u39b5c9Z9PMknZl1/R7/965OsHXG/HQFc2z/GHkk29Dn3GvH+WuYsfk2yU4DP9V+/nGQ/gCQrgK8AtwCrgQOAjQut385tngy8EtgbuJ7uL46fAT4EfDbJ/otlAD4LHJdk7/52K4GTgD+dZ1sbgVckedqsxzwR2JDkEOAdwM9X1dOAXwZuHvFneAFwTZKDgW/2P8frquqBkfeCljWLXxMpyUuB5wDnVdUVwE3AG/qrjwGeBby3qh6sqoer6huLrN8en6iq26rqR1X1xar6h6p6vKq+ANzQb2PBDFW1Bfga8Kv97Y4D7ul/hp9SVbcAVwIzf0kcCzxUVX8DPAbsChyWZJequrmqbhrxZziCboz/UuDMqvpQOQ2vZrH4NanWAX9VVff0yxv45+Geg4BbqurROfdZaP32uG3mQpJTklyV5L4k9wGHA/uOsK31wBv7y28E/myR7W2g+ysDuie2DQBVdSNwOnAmcHeSjUmeta3wSdLnfC1wVlVdvK37qD0WvyZOkt3phjx+IcmdSe4E3gUcmeRIunJ+9jwvwC60fsZDwB6zlp85z22qz/Ac4FN0wy3PqKq96cbNM8K2LgKOSHI48Cq6oaqFfBF4eZID6cp6w/8PUrWhqmb+8ingI4s8zoyD+++/CLwnyZoR7qPGWPyaRCfQDXUcBhzVfz0f+DrduP+3gS3Ah5PsmWS3JC9ZZP2Mq4A3JFmR5DjgFxbJsCdd2W4FSPJmuiPpGQtuqz+b5ny6Ev92Vd260EaqaitwGXAu8IOq2txv75Akx/ansT4M/Ah4fNG91jkCuLqqrgFOBb4087qENMPi1yRaB5xbVbdW1Z0zX8AngV+nO+p+NfBc4FbgduDXquqx+dbPetzT+uvv6x/nooUCVNV1wB8A3wLuonvB9Juzrt/Wttb391lsmGfGBroj9A2z1u0KfBi4B7gT+Fng/TNXJvnzJB+Y57FeAFzdZ7wIOBu4KMluI+RQI+JrPtLSS/Js4HvAM6vq/nHnkWbziF9aYkmeArwb2GjpaxJN87sTpYmTZE+6oaFb6E7llCaOQz2S1BiHeiSpMVMx1LPvvvvW6tWrxx1DkqbKFVdccU9VrZq7fiqKf/Xq1WzatGncMSRpqiS5Zb71DvVIUmMsfklqjMUvSY2x+CWpMRa/JDXG4pekxlj8ktQYi1+SGmPxS1JjpuKdu5KWgQ1Z+Lo3NDxZ5Bj2i0f8ktQYj/glTRf/cnjSLH5J22bZLisWv6T2NP5EZvFLk2qUclpuBbZUP89y2y9LzOLXsPwFHC/3v+Zh8U+aaftFnZS8k5IDJiuLhjWl/9YWv9oxScMIU1oYWh4sfo1fi2PZ0hhZ/NJsLT7BTNJfQtopLP6dyV8wSRPA4m+VwyvS4pbx/3+LX5KGNIFPIE7SJkmN8Yh/OZrAIwxJk8MjfklqjMUvSY2x+CWpMYOO8Sd5F/AbQAHXAG8G9gc2As8ArgDeVFWPDJljp3BcXdKUGOyIP8kBwH8F1lTV4cAK4CTgI8BHq+q5wL3AW4bKIEl6oqHP6lkJ7J7kJ8AewBbgWOAN/fXrgTOBswbO8eR5RC9pmRjsiL+q7gB+H7iVrvD/iW5o576qerS/2e3AAfPdP8mpSTYl2bR169ahYkpSc4Yc6tkHOB44GHgWsCdw3Kj3r6qzq2pNVa1ZtWrVQCklqT1DntXzi8APqmprVf0EuBB4CbB3kpkhpgOBOwbMIEmaY8jivxV4UZI9kgRYC1wHXAq8vr/NOuDiATNIkuYYcoz/cuB84Eq6UzmfApwNnAG8O8mNdKd0njNUBknSEw16Vk9VfRD44JzV3weOGXK7kqSF+c5dSWqMxS9JjbH4JakxFr8kNcbil6TGWPyS1BiLX5IaY/FLUmMsfklqzNDz8Y/fKPPoO9e+pIZ4xC9JjbH4JakxFr8kNcbil6TGWPyS1BiLX5IaY/FLUmMsfklqjMUvSY2x+CWpMRa/JDXG4pekxlj8ktQYi1+SGmPxS1JjLH5JaozFL0mNsfglqTEWvyQ1xuKXpMZY/JLUGItfkhpj8UtSYyx+SWqMxS9JjbH4JakxFr8kNWbQ4k+yd5Lzk3wvyeYkL07y9CRfTXJD/32fITNIkn7a0Ef8Hwf+oqoOBY4ENgPvAy6pqucBl/TLkqSdZLDiT/IzwMuAcwCq6pGqug84Hljf32w9cMJQGSRJTzTkEf/BwFbg3CTfSfLpJHsC+1XVlv42dwL7zXfnJKcm2ZRk09atWweMKUltGbL4VwIvBM6qqqOBB5kzrFNVBdR8d66qs6tqTVWtWbVq1YAxJaktQxb/7cDtVXV5v3w+3RPBXUn2B+i/3z1gBknSHIMVf1XdCdyW5JB+1VrgOuDLwLp+3Trg4qEySJKeaOXAj/9O4HNJngp8H3gz3ZPNeUneAtwCnDhwBknSLIMWf1VdBayZ56q1Q25XkrQw37krSY2x+CWpMRa/JDXG4pekxmyz+JO8OolPEJK0TIxS6L8G3JDk95IcOnQgSdKwtln8VfVG4GjgJuAzSb7Vz6PztMHTSZKW3EhDOFV1P92UCxuB/YHXAlcmeeeA2SRJAxhljP81Sb4EXAbsAhxTVb9CN7/+e4aNJ0laaqO8c/d1wEer6muzV1bVQ/20C5KkKTJK8Z8JzMyfT5Ld6ebUv7mqLhkqmCRpGKOM8X8ReHzW8mP9OknSFBql+FdW1SMzC/3lpw4XSZI0pFGKf2uS18wsJDkeuGe4SJKkIY0yxv82ujn1PwkEuA04ZdBUkqTBbLP4q+om4EVJ9uqXHxg8lSRpMCN9EEuSVwL/GtgtCQBV9VsD5pIkDWSUN3D9Md18Pe+kG+r5VeA5A+eSJA1klBd3/11VnQLcW1UfAl4M/NywsSRJQxml+B/uvz+U5FnAT+jm65EkTaFRxvj/V5K9gf8BXAkU8KlBU0mSBrNo8fcfwHJJVd0HXJDkK8BuVfVPOyWdJGnJLTrUU1WPA380a/nHlr4kTbdRxvgvSfK6zJzHKUmaaqMU/1vpJmX7cZL7k/wwyf0D55IkDWSUd+76EYuStIxss/iTvGy+9XM/mEWSNB1GOZ3zvbMu7wYcA1wBHDtIIknSoEYZ6nn17OUkBwEfGyyRJGlQo7y4O9ftwPOXOogkaecYZYz/f9K9Wxe6J4qj6N7BK0maQqOM8W+adflR4PNV9c2B8kiSBjZK8Z8PPFxVjwEkWZFkj6p6aNhokqQhjPTOXWD3Wcu7A/97mDiSpKGNUvy7zf64xf7yHsNFkiQNaZTifzDJC2cWkvwb4EfDRZIkDWmUMf7TgS8m+Qe6j158Jt1HMUqSptAob+D62ySHAof0q66vqp+MuoEkK+jODLqjql6V5GBgI/AMuncAv6mqHtn+6JKkHTHKh62/Hdizqq6tqmuBvZL8l+3YxmnA5lnLHwE+WlXPBe4F3rI9gSVJT84oY/y/2X8CFwBVdS/wm6M8eJIDgVcCn+6XQzfHz/n9TdYDJ2xPYEnSkzNK8a+Y/SEs/dDNU0d8/I8B/w14vF9+BnBfVT3aL98OHDDfHZOcmmRTkk1bt24dcXOSpG0Zpfj/AvhCkrVJ1gKfB/58W3dK8irg7qq6YkeCVdXZVbWmqtasWrVqRx5CkjSPUc7qOQM4FXhbv3w13Zk92/IS4DVJXkE3nfO/AD4O7J1kZX/UfyBwx3anliTtsG0e8fcfuH45cDPdXPzH8tMv1i50v/dX1YFVtRo4Cfjrqvp14FLg9f3N1gEX71BySdIOWfCIP8nPASf3X/cAXwCoqv/wJLd5BrAxyW8D3wHOeZKPJ0naDosN9XwP+Drwqqq6ESDJu3ZkI1V1GXBZf/n7dH85SJLGYLGhnv8EbAEuTfKp/oXdLHJ7SdIUWLD4q+qiqjoJOJRuXP504GeTnJXkl3ZWQEnS0hrlxd0Hq2pD/9m7B9KNy58xeDJJ0iC26zN3q+re/vz6tUMFkiQNa0c+bF2SNMUsfklqjMUvSY2x+CWpMRa/JDXG4pekxlj8ktQYi1+SGmPxS1JjLH5JaozFL0mNsfglqTEWvyQ1xuKXpMZY/JLUGItfkhpj8UtSYyx+SWqMxS9JjbH4JakxFr8kNcbil6TGWPyS1BiLX5IaY/FLUmMsfklqjMUvSY2x+CWpMRa/JDXG4pekxlj8ktQYi1+SGmPxS1JjBiv+JAcluTTJdUm+m+S0fv3Tk3w1yQ39932GyiBJeqIhj/gfBd5TVYcBLwLenuQw4H3AJVX1POCSflmStJMMVvxVtaWqruwv/xDYDBwAHA+s72+2HjhhqAySpCfaKWP8SVYDRwOXA/tV1Zb+qjuB/XZGBklSZ/DiT7IXcAFwelXdP/u6qiqgFrjfqUk2Jdm0devWoWNKUjMGLf4ku9CV/ueq6sJ+9V1J9u+v3x+4e777VtXZVbWmqtasWrVqyJiS1JQhz+oJcA6wuar+cNZVXwbW9ZfXARcPlUGS9EQrB3zslwBvAq5JclW/7gPAh4HzkrwFuAU4ccAMkqQ5Biv+qvoGkAWuXjvUdiVJi/Odu5LUGItfkhpj8UtSYyx+SWqMxS9JjbH4JakxFr8kNcbil6TGWPyS1BiLX5IaY/FLUmMsfklqjMUvSY2x+CWpMRa/JDXG4pekxlj8ktQYi1+SGmPxS1JjLH5JaozFL0mNsfglqTEWvyQ1xuKXpMZY/JLUGItfkhpj8UtSYyx+SWqMxS9JjbH4JakxFr8kNcbil6TGWPyS1BiLX5IaY/FLUmMsfklqjMUvSY2x+CWpMWMp/iTHJbk+yY1J3jeODJLUqp1e/ElWAH8E/ApwGHByksN2dg5JatU4jviPAW6squ9X1SPARuD4MeSQpCalqnbuBpPXA8dV1W/0y28C/m1VvWPO7U4FTu0XDwGuH+Hh9wXuWcK4Q5umvNOUFcw7pGnKCm3nfU5VrZq7cuUSPfiSq6qzgbO35z5JNlXVmoEiLblpyjtNWcG8Q5qmrGDe+YxjqOcO4KBZywf26yRJO8E4iv9vgeclOTjJU4GTgC+PIYckNWmnD/VU1aNJ3gH8JbAC+JOq+u4SPfx2DQ1NgGnKO01ZwbxDmqasYN4n2Okv7kqSxst37kpSYyx+SWrMsij+aZsCIsnNSa5JclWSTePOM1eSP0lyd5JrZ617epKvJrmh/77PODPOtkDeM5Pc0e/jq5K8YpwZZyQ5KMmlSa5L8t0kp/XrJ3L/LpJ3Uvfvbkm+neTv+rwf6tcfnOTyviO+0J9YMqlZP5PkB7P27VFLvu1pH+Pvp4D4e+A/ArfTnTV0clVdN9Zgi0hyM7CmqibyTSVJXgY8APxpVR3er/s94B+r6sP9k+s+VXXGOHPOWCDvmcADVfX748w2V5L9gf2r6sokTwOuAE4A/jMTuH8XyXsik7l/A+xZVQ8k2QX4BnAa8G7gwqramOSPgb+rqrMmNOvbgK9U1flDbXs5HPE7BcQSq6qvAf84Z/XxwPr+8nq6X/6JsEDeiVRVW6rqyv7yD4HNwAFM6P5dJO9Eqs4D/eIu/VcBxwIzRToR+3eRrINbDsV/AHDbrOXbmeD/mL0C/irJFf3UFNNgv6ra0l++E9hvnGFG9I4kV/dDQRMxdDJbktXA0cDlTMH+nZMXJnT/JlmR5CrgbuCrwE3AfVX1aH+TiemIuVmrambf/k6/bz+aZNel3u5yKP5p9NKqeiHdDKVv74cqpkZ144OTPkZ4FvCvgKOALcAfjDfOT0uyF3ABcHpV3T/7ukncv/Pkndj9W1WPVdVRdLMCHAMcOuZIC5qbNcnhwPvpMv888HRgyYf8lkPxT90UEFV1R//9buBLdP85J91d/XjvzLjv3WPOs6iquqv/pXoc+BQTtI/78dwLgM9V1YX96ondv/PlneT9O6Oq7gMuBV4M7J1k5g2rE9cRs7Ie1w+vVVX9GDiXAfbtcij+qZoCIsme/YtkJNkT+CXg2sXvNRG+DKzrL68DLh5jlm2aKdHea5mQfdy/oHcOsLmq/nDWVRO5fxfKO8H7d1WSvfvLu9Od9LGZrlRf399sIvbvAlm/N+sAIHSvRSz5vp36s3oA+lPJPsY/TwHxO2OOtKAk/5LuKB+6KTM2TFreJJ8HXk43PexdwAeBi4DzgGcDtwAnVtVEvKC6QN6X0w1DFHAz8NZZY+hjk+SlwNeBa4DH+9UfoBs3n7j9u0jek5nM/XsE3Yu3K+gObM+rqt/qf+820g2dfAd4Y39EPTaLZP1rYBUQ4CrgbbNeBF6abS+H4pckjW45DPVIkraDxS9JjbH4JakxFr8kNcbil6TGWPyS1BiLX5IaY/FLOyDJ2iR/Nu4c0o6w+KUdcyTdO0ClqWPxSzvmSOA7SXbtPzHpd/u5VaSJt3LbN5E0jyPoZtD8S+DTVfXZMeeRRuZcPdJ26qcpvoduMrW3VtW3xhxJ2i4O9Ujb7/l004E/Cjw25izSdrP4pe13JPB/6D774dwkE/cxidJiLH5p+x0JXFtVf0/3sXjn9cM/0lRwjF+SGuMRvyQ1xuKXpMZY/JLUGItfkhpj8UtSYyx+SWqMxS9Jjfl/og9TNPeGUjgAAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WSwoqtJr9AAQ",
        "outputId": "ac643b92-90b1-4be3-e836-6d9b83d1a791"
      },
      "source": [
        "# Get the best k-value.\n",
        "best_k = np.argmax(accuracies, axis=0)\n",
        "print(\"Best k-Value:\", best_k + 1)"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Best k-Value: 27\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "P8ow3lXZ9BFL",
        "outputId": "7ee8e70c-f604-4e5c-d57b-45fbc162e66a"
      },
      "source": [
        "print(\"Accuracy:\", accuracies[best_k])"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Accuracy: 89.71\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}