k_nearest_neighbours.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**K Nearest Neighbors and Decision Trees**\n",
    "\n",
    "Here we tackle a simple classification problem - that of labelling emails as spam or non-spam, based on their content in terms of words. The dataset has been taken from UCI Machine learning repository (https://archive.ics.uci.edu/ml/datasets/Spambase ). This will be achieved using two machine learning methods based on distances - nearest neighbors and decision trees. First, we import the required libraries.  \n",
    "\n",
    "**numpy**: This is a library that has functions to facilitate numerical computations in Python. Allows us to deal with matrices, vectors and other such algebraic objects in a fluid manner. \n",
    "\n",
    "**sys**: Used for system functions. \n",
    "\n",
    "**sklearn**: Scikit-learn. A very powerful library that has many machine learning models implemented that can be used out of the box, with highly customizable parameters. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import sys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we create the class for k nearest neighbors. \n",
    "<br>__init__ is the constructor function for Python classes, and only needs the number of neighbors to be used during testing as a parameter. \n",
    "<br>**fit** is the function that is supposed to implement the training algorithm, but since kNNs don't have an explicit training phase, this just saves the training data as local class variables. \n",
    "<br>**predict** is where the whole logic of kNN lies - it helps predict the class label of a new test point by finding out its distance from all the training points, finding out which ones are the closest to it, and then taking a majority vote from these neighbors to predict the label of our test point. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class k_nearest_neighbours(object):\n",
    "    def __init__(self, k):\n",
    "        self.k = k\n",
    "        \n",
    "    def fit(self, Xtr, Ytr):\n",
    "        self.Xtr = Xtr\n",
    "        self.Ytr = Ytr\n",
    "    \n",
    "    def predict(self, Xts):\n",
    "        Y_hat_ts = np.zeros(Xts.shape[0])\n",
    "        for test_idx in range(len(Xts)):\n",
    "            # this loop runs over all the test data points\n",
    "            test_point = Xts[test_idx]\n",
    "            distance_vector = np.zeros(self.Xtr.shape[0])\n",
    "            for idx in range(len(self.Xtr)):\n",
    "                # computing distances from all training points\n",
    "                train_point = self.Xtr[idx]\n",
    "                # distance is defined here as the l2 norm of the difference, or the Euclidean distance\n",
    "                distance_vector[idx] = np.linalg.norm(test_point - train_point) \n",
    "            # getting the indices of the training points in increasing order of distance from the test point. \n",
    "            distance_vector_sorted = np.argsort(distance_vector)\n",
    "            num_positives = 0\n",
    "            for i in range(self.k):\n",
    "                num_positives += self.Ytr[distance_vector_sorted[i]]\n",
    "            # majority vote\n",
    "            if num_positives > self.k / 2:\n",
    "                Y_hat_ts[test_idx] = 1\n",
    "            else:\n",
    "                Y_hat_ts[test_idx] = 0\n",
    "        return Y_hat_ts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The spam dataset has to be saved in the same directory as this notebook. If the notebook's path is *path*, then the dataset's training data is *path/spam/Xtr* and so on. \n",
    "\n",
    "This dataset's description as to the number and type of features, number of spam emails, etc. can be found at https://archive.ics.uci.edu/ml/datasets/Spambase. A version of this dataset will be uploaded on Google drive and its link will be sent to you in order to allow you to complete this notebook. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = \"spam\"\n",
    "path = \"./\" + dataset + \"/\"\n",
    "\n",
    "Xtr = np.load(path + \"Xtrain.npy\")\n",
    "Ytr = np.load(path + \"Ytrain.npy\")\n",
    "Xts = np.load(path + \"Xtest.npy\")\n",
    "Yts = np.load(path + \"Ytest.npy\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create a kNN classifier by creating an object from the class defined earlier. The value of *k* can be adjusted. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 1\n",
    "classifier = k_nearest_neighbours(k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also create a decision tree classifier, but this one won't be hard coded. The DecisionTreeClassifier class from sklearn is used to instantiate a DT with our choice of split criterion ('entropy'). \n",
    "\n",
    "**Note**: If you want to classify using k Nearest Neighbors, don't run this cell, since it would overwrite that classifier with the DT. On the other hand, if you want to classify using a DT, run this cell and proceed. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "classifier = tree.DecisionTreeClassifier(criterion='entropy')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, train whichever classifier you have picked using **fit**. Get predictions on the test data from this model, and compare the predictions with the actual test labels to get a measure of the accuracy. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "91.5309446254\n"
     ]
    }
   ],
   "source": [
    "# train the chosen classifier on the training data\n",
    "classifier.fit(Xtr, Ytr)\n",
    "\n",
    "# get predictions on the test data using the trained classifier. \n",
    "predictions = classifier.predict(Xts)\n",
    "\n",
    "# compute accuracy by comparing test labels with classifier predictions\n",
    "accuracy = 0.0\n",
    "for i in range(len(predictions)):\n",
    "    if predictions[i] == Yts[i]:\n",
    "        accuracy += 1\n",
    "accuracy /= len(predictions)\n",
    "accuracy *= 100\n",
    "test_accuracy = accuracy\n",
    "print test_accuracy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also compute the training accuracy, though it would be very high for both our models. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99.9184782609\n"
     ]
    }
   ],
   "source": [
    "# getting predictions on the training data. \n",
    "predictions = classifier.predict(Xtr)\n",
    "\n",
    "# computation of training accuracy\n",
    "accuracy = 0.0\n",
    "for i in range(len(predictions)):\n",
    "    if predictions[i] == Ytr[i]:\n",
    "        accuracy += 1\n",
    "accuracy /= len(predictions)\n",
    "accuracy *= 100\n",
    "train_accuracy = accuracy\n",
    "print train_accuracy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11+"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}