knn_tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we will implement the k-Nearest Neighbors (KNN) algorithm from scratch using Python! \n",
    "\n",
    "KNN is a **supervised** classification and regression method. This differs from **k-means clustering** in that **k-means clustering** is an **unsupervised** method for clustering unlabeled data. \n",
    "\n",
    "We will work with the [Iris datsaet from sklearn](https://scikit-learn.org/stable/auto_examples/datasets/plot_iris_dataset.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import datasets\n",
    "from sklearn.model_selection import train_test_split\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's begin by loading the dataset from sklearn and converting it to a data frame for easy viewing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "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>sepal length (cm)</th>\n",
       "      <th>sepal width (cm)</th>\n",
       "      <th>petal length (cm)</th>\n",
       "      <th>petal width (cm)</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>5.1</td>\n",
       "      <td>3.5</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>4.9</td>\n",
       "      <td>3.0</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>4.7</td>\n",
       "      <td>3.2</td>\n",
       "      <td>1.3</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4.6</td>\n",
       "      <td>3.1</td>\n",
       "      <td>1.5</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5.0</td>\n",
       "      <td>3.6</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   sepal length (cm)  sepal width (cm)  petal length (cm)  petal width (cm)\n",
       "0                5.1               3.5                1.4               0.2\n",
       "1                4.9               3.0                1.4               0.2\n",
       "2                4.7               3.2                1.3               0.2\n",
       "3                4.6               3.1                1.5               0.2\n",
       "4                5.0               3.6                1.4               0.2"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iris = datasets.load_iris()\n",
    "iris_df = pd.DataFrame(data = iris.data, columns = iris.feature_names)\n",
    "iris_df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because the KNN algorithm is a supervised learning method, it relies on labeled data. It essentially clasifies new data points based on knowledge of the $k$ nearest, or most similar, data points which already have known categorical labels. Thus, important steps in this implementation of KNN are:\n",
    "\n",
    "1. Split dataset into known (train) data points and unknown (test) data points to label with the algorithm. \n",
    "2. Determine a value of $k$ \n",
    "3. Define a function for calculating distance/similarity between data points \n",
    "\n",
    "We will use Euclidean distance in this tutorial to calculate distance between data points. Specifically, for each unknown (test) data point in the data, we will:\n",
    "1. Find the Euclidian distance to each training data point\n",
    "2. Store the distances and label of the training data point on an ordered list and sort\n",
    "3. Choose the top $k$ entries on this list\n",
    "4. Determine the most frequently appearing label of the top $k$ entries and assign this label to the test data point\n",
    "\n",
    "Let's start by defining the distance function here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def euclidean_distance(test_point, train_point):\n",
    "    assert len(test_point)==len(train_point), \"Data points do not have the same dimensions\"\n",
    "    ssd = 0 # sum of squared distances\n",
    "    for i in range(len(test_point)):\n",
    "        ssd += (test_point[i]-train_point[i])**2\n",
    "    return ssd**(0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will split up the iris dataset into a training dataset and a test dataset. We will compute distances between each test data point and all of the training data points to make predictions about the test data points, and then measure the accuracy of these predictions. By default, the [`train_test_split`](https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.train_test_split.html) function from sklearn sets aside 25% of the dataset for the test set and 75% for the training set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "112 points in training dataset, 38 points in test set\n"
     ]
    }
   ],
   "source": [
    "X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target)\n",
    "\n",
    "print('%d points in training dataset, %d points in test set' % (len(X_train), len(X_test)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will define some helper functions and a function to run the algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sort_distances(train, test):\n",
    "    '''\n",
    "    for a given test point, find distance to all points in training set\n",
    "    '''\n",
    "    distances = []\n",
    "    for i in range(len(train)):\n",
    "        distances.append(euclidean_distance(test, train[i,]))\n",
    "    return(distances)\n",
    "\n",
    "def predict_class(distances, y_train, k):\n",
    "    '''\n",
    "    given distances, labels of training data, and k\n",
    "    identify most common label among k nearest neighbors\n",
    "    '''\n",
    "    neighbor_labels = y_train[np.argsort(distances)[:k]]\n",
    "    counts = Counter(neighbor_labels)\n",
    "    prediction = sorted(counts.items(), key = lambda item: item[1], reverse = True)[0][0]\n",
    "    return(prediction)\n",
    "\n",
    "def knn(X_train, X_test, y_train, y_test, k):\n",
    "    '''\n",
    "    make prediction for a single test data point given training data and k\n",
    "    X_test and y_test are for single data points\n",
    "    X_train and y_train are for entire training data set \n",
    "    k must be an integer\n",
    "    '''\n",
    "    distances = sort_distances(X_train, X_test)\n",
    "    prediction = predict_class(distances, y_train, k)\n",
    "    \n",
    "    print('expected class: %s, npredicted class: %s' % (y_test, prediction))\n",
    "    return((prediction, y_test))\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we make a prediction for each data point in the test data set using the training data set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "expected class: 1, npredicted class: 1\n",
      "expected class: 0, npredicted class: 0\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 0, npredicted class: 0\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 0, npredicted class: 0\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 0, npredicted class: 0\n",
      "expected class: 1, npredicted class: 2\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 0, npredicted class: 0\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 0, npredicted class: 0\n",
      "expected class: 0, npredicted class: 0\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 0, npredicted class: 0\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 1, npredicted class: 1\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 2, npredicted class: 2\n",
      "expected class: 1, npredicted class: 1\n"
     ]
    }
   ],
   "source": [
    "knn_predictions = list()\n",
    "\n",
    "for i in range(len(X_test)):\n",
    "    result = knn(X_train, X_test[i], y_train, y_test[i], 5)\n",
    "    knn_predictions.append(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculate accuracy for predictions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "prediction accuracy on test set = 97.37%\n"
     ]
    }
   ],
   "source": [
    "accuracy = sum([x[0]==x[1] for x in knn_predictions])/len(knn_predictions)*100\n",
    "print(\"prediction accuracy on test set = %.2f%%\" % accuracy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An alternative approach could have been to use k-fold cross validation and evaluate performance on each fold of data, e.g. \n",
    "\n",
    "```python\n",
    "from sklearn.model_selection import KFold\n",
    "\n",
    "kf = KFold(n_splits=5)\n",
    "folds = kf.split(iris.data, iris.target)\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}