kNN_Annoy.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approximate Nearest Neighbour using Annoy  \n",
    "https://pypi.org/project/annoy/  \n",
    "Based on code from   \n",
    "https://www.kaggle.com/nicw102168/nearest-neighbor-classification-with-annoy\n",
    "\n",
    "### Install Annoy\n",
    "To install `annoy` use:  \n",
    "`pip install annoy`  \n",
    "If you have problems on a Mac make sure your XCode is up to date. \n",
    "\n",
    "### Other Requirements\n",
    "To run this notebook you will need to download the three data files and the `.py` file that loads the data:  \n",
    "- `kNNDataLoader.py`\n",
    "- `CC_default.csv`\n",
    "- `HTRU_2.csv`\n",
    "- `shuttle.csv`\n",
    "- `letter-recognition.csv`  \n",
    "\n",
    "You will also need `kNNAnnoy.py` - it contains code to wrap the annoy library in an sklearn-like object with `fit` and `predict` methods.  \n",
    "These are all available in the git-hub repository. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import annoy\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "from sklearn import preprocessing\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "from kNNAnnoy import kNNAnnoyClassifier\n",
    "from sklearn.model_selection import train_test_split\n",
    "import time\n",
    "import statistics\n",
    "from sklearn import metrics\n",
    "import kNNDataLoader\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load the four datasets. \n",
    "Make sure you have downloaded the loader module (`kNNDataLoader.py`) and the four data files. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Name_arr, X_dir, y_dir = kNNDataLoader.data_loader()\n",
    "Name_arr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## kNNAnnoyClassifier\n",
    "\n",
    "### Defaults\n",
    "metric = 'euclidean'\n",
    "n_trees = 10\n",
    "n_neighbors = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from kNNAnnoy import kNNAnnoyClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ANN = kNNAnnoyClassifier(n_neighbors = 5, n_trees = 10)\n",
    "ts = time.time()\n",
    "ds = 'Letter'\n",
    "X_train, X_test, y_train, y_test = train_test_split(X_dir[ds], y_dir[ds], \n",
    "                                                    random_state=0, test_size=1/2)\n",
    "  \n",
    "ANN = ANN.fit(X_train, y_train)\n",
    "y_hat = ANN.predict(X_test)\n",
    "\n",
    "tf = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "acc = metrics.accuracy_score(y_test, y_hat)\n",
    "conf = metrics.confusion_matrix(y_test, y_hat)\n",
    "\n",
    "print(\"AnnonykNN Time: {0:.2f}\".format(tf-ts))\n",
    "print(\"Accuracy: {0:.2f}\".format(acc)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ANN Accuracy Evaluation\n",
    "In this first test, we use a single tree in the ANN (`n_trees` = 1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ANN = kNNAnnoyClassifier(n_neighbors = 5, n_trees = 1)\n",
    "kNN = KNeighborsClassifier(n_neighbors=5)\n",
    "\n",
    "m_names = ['k-NN','ANN']\n",
    "models = {'k-NN':kNN, 'ANN':ANN}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ANN_acc = {}\n",
    "ANN_t = {}\n",
    "\n",
    "for m_name in models:\n",
    "    m = models[m_name]\n",
    "    print(m_name)\n",
    "    times = {}\n",
    "    accs = {}\n",
    "    for ds in Name_arr:\n",
    "        print(ds)\n",
    "        X = X_dir[ds]\n",
    "        y = y_dir[ds]\n",
    "        \n",
    "        t_start = time.time()\n",
    "        X_train, X_test, y_train, y_test = train_test_split(X_dir[ds], y_dir[ds], \n",
    "                                                    random_state=0, test_size=1/2)\n",
    "        Model = m.fit(X_train, y_train)\n",
    "        y_hat = Model.predict(X_test)\n",
    " \n",
    "        t = time.time()-t_start\n",
    "        acc = metrics.accuracy_score(y_test, y_hat)\n",
    "\n",
    "        times[ds]= t\n",
    "        accs[ds]= acc\n",
    "        print(t)\n",
    "    ANN_acc[m_name]=accs\n",
    "    ANN_t[m_name]=times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "resA_pd = pd.DataFrame(ANN_acc)\n",
    "rest_pd = pd.DataFrame(ANN_t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rest_pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "resA_pd['Acc Percent']=resA_pd['ANN']/resA_pd['k-NN']*100\n",
    "resA_pd['Time Percent']=rest_pd['ANN']/rest_pd['k-NN']*100\n",
    "resA_pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "width = .35 # width of a bar\n",
    "\n",
    "ax1=resA_pd[['k-NN','ANN']].plot(kind='bar', width = width, \n",
    "                                 figsize=(6,4),\n",
    "                                 color = ('royalblue','skyblue'))\n",
    "ax2=resA_pd['Time Percent'].plot(secondary_y=True, color = 'r', markersize=12, mew =2,\n",
    "                                 marker = 'x', linewidth = 0)\n",
    "\n",
    "plt.xlim([-width, 4-2*width])\n",
    "ax2.set_ylim(0,100)\n",
    "ax1.set_ylabel('Accuracy',fontsize = 14)\n",
    "ax2.set_ylabel('Time %', color = 'r', fontsize = 14)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Accuracy v No of Trees\n",
    "In the test above, there is no loss of accuracy with ANN, except in the `Letter` dataset.   \n",
    "We now increase the number of trees to see if this accuracy can be recovered, and at what time cost. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "TTrees = 10\n",
    "nTrials = 5\n",
    "ds = 'Letter'\n",
    "X = X_dir[ds]\n",
    "y = y_dir[ds]\n",
    "X_train, X_test, y_train, y_test = train_test_split(X_dir[ds], y_dir[ds], \n",
    "                                                    random_state=0, test_size=1/2)\n",
    "times = []\n",
    "accs = []\n",
    "\n",
    "# Baseline figures for kNN\n",
    "t_max = rest_pd['k-NN']['Letter']\n",
    "a_max = resA_pd['k-NN']['Letter']\n",
    "\n",
    "for nt in range(1, TTrees + 1):\n",
    "    ANN = kNNAnnoyClassifier(n_neighbors = 5, n_trees = nt)\n",
    "    tot = 0\n",
    "    for tt in range(nTrials):\n",
    "        t_start = time.time()\n",
    "        Model = ANN.fit(X_train, y_train)\n",
    "        y_hat = Model.predict(X_test)\n",
    "        tot += (time.time()-t_start)\n",
    "        acc = metrics.accuracy_score(y_test, y_hat)\n",
    "    t_avg = tot/nTrials\n",
    "    times.append(t_avg/t_max*100)   \n",
    "    accs.append(acc/a_max*100)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.DataFrame(list(zip(times, accs)), index = range(1,TTrees + 1),\n",
    "              columns =['Time', 'Accuracy']) \n",
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax1 = plt.subplots(figsize=(6,4))\n",
    "r = range(1,11)\n",
    "color = 'skyblue'\n",
    "ax1.set_xlabel('Trees')\n",
    "ax1.set_ylabel('Accuracy %', fontsize = 14 )\n",
    "ax1.bar(r, df['Accuracy'], color=color, width = 0.5)\n",
    "ax1.grid(which = 'major')\n",
    "ax1.set_ylim(1,100)\n",
    "\n",
    "\n",
    "ax2 = ax1.twinx()  # instantiate a second axes that shares the same x-axis\n",
    "\n",
    "color = 'r'\n",
    "ax2.set_ylabel('Time %',color = 'r', fontsize = 14 )  # we already handled the x-label with ax1\n",
    "ax2.set_ylim(1,100)\n",
    "\n",
    "ax2.plot(r, df['Time'], color=color, marker = 'x', markersize=12, mew =2,\n",
    "                                  linewidth = 0,label='Time')\n",
    "ax2.legend(loc = 'upper left')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}