kNearestNeighbor

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Problem 3\n",
    "import itertools\n",
    "import operator\n",
    "import math\n",
    "import numpy as np\n",
    "\n",
    "def most_common(L):\n",
    "  # get an iterable of (item, iterable) pairs\n",
    "  SL = sorted((x, i) for i, x in enumerate(L))\n",
    "  # print 'SL:', SL\n",
    "  groups = itertools.groupby(SL, key=operator.itemgetter(0))\n",
    "  # auxiliary function to get \"quality\" for an item\n",
    "  def _auxfun(g):\n",
    "    item, iterable = g\n",
    "    count = 0\n",
    "    min_index = len(L)\n",
    "    for _, where in iterable:\n",
    "      count += 1\n",
    "      min_index = min(min_index, where)\n",
    "    # print 'item %r, count %r, minind %r' % (item, count, min_index)\n",
    "    return count, -min_index\n",
    "  # pick the highest-count/earliest item\n",
    "  return max(groups, key=_auxfun)[0]\n",
    "\n",
    "class kNN:\n",
    "    def __init__(self, n, trainingDataPath, validationDataPath, testDataPath):\n",
    "        self.n = n\n",
    "        \n",
    "        self.trainingData = np.genfromtxt(trainingDataPath, dtype=\"i8\", delimiter=' ')\n",
    "        self.validationData = np.genfromtxt(validationDataPath, dtype=\"i8\", delimiter=' ')\n",
    "        self.testData = np.genfromtxt(testDataPath, dtype=\"i8\", delimiter=' ')\n",
    "        \n",
    "        self.features = self.testData[0].size-1\n",
    "        \n",
    "        self.nearestNeighborDistances = np.zeros((self.trainingData.shape[0],0))\n",
    "        \n",
    "        self.validationError = 0\n",
    "        self.trainingError = 0\n",
    "        \n",
    "    #finds the Euclidean distance between two vectors using a built-in numpy function\n",
    "    def euclideanDistance(self, vectorOne, vectorTwo, omitN):\n",
    "        dist = np.linalg.norm(vectorOne-vectorTwo)\n",
    "        return dist\n",
    "    \n",
    "    #creates a matrix of (closest neighbor distance, closest neighbor index) pairs for each datapoint\n",
    "    def createDistanceIndexMatrix(self, dataToCompareToTraining):\n",
    "        numFeaturesInDataToCompare = dataToCompareToTraining.shape[0]\n",
    "        intTupleDataType = np.dtype((np.int32, 2))\n",
    "        outputMatrix = np.zeros((numFeaturesInDataToCompare, self.n), dtype= intTupleDataType)\n",
    "        \n",
    "        for c_index, compareVector in enumerate(dataToCompareToTraining):\n",
    "            for t_index, trainingVector in enumerate(self.trainingData):\n",
    "                newDistance = self.euclideanDistance(trainingVector, compareVector, 1)\n",
    "                \n",
    "                #current outputMatrix nearestneighbor vector is full\n",
    "                if outputMatrix[c_index][self.n-1][0] != 0:\n",
    "                    #so find the biggest distance\n",
    "                    maximumDistance = 0\n",
    "                    indexOfMaximumDistanceInDistanceIndexArray = 0\n",
    "                    for (indexInDistanceIndexArray, distanceIndexArray) in enumerate(outputMatrix[c_index]):\n",
    "                        distanceToTraining = distanceIndexArray[0]\n",
    "                        indexInTrainingData = distanceIndexArray[1]\n",
    "                    \n",
    "                        if distanceToTraining > maximumDistance:\n",
    "                            maximumDistance = distanceToTraining\n",
    "                            indexOfMaximumDistanceInDistanceIndexArray = indexInDistanceIndexArray\n",
    "                                \n",
    "                    outputMatrix[c_index][indexOfMaximumDistanceInDistanceIndexArray] = (newDistance, t_index)\n",
    "                #current outputMatrix nearestneighbor vector not full\n",
    "                else:\n",
    "                    #so just find the next spot and put the distance and index in\n",
    "                    for indexInDistanceIndexArray, distanceIndexArray in enumerate(outputMatrix[c_index]):\n",
    "                        distanceToTestData = distanceIndexArray[0]\n",
    "                        if distanceToTestData == 0:\n",
    "                            outputMatrix[c_index][indexInDistanceIndexArray] = (newDistance, t_index)\n",
    "        \n",
    "        return outputMatrix\n",
    "    \n",
    "    #using a distance-index matrix (created above), creates a vector of (label-guess, label) pairs\n",
    "    def createGuessLabelVector(self, distanceIndexMatrix, dataMatrix):\n",
    "        digitGuessArray = []\n",
    "        for c_index, distanceIndexPairArray in enumerate(distanceIndexMatrix):\n",
    "            nearestNeighborDigits = []\n",
    "            for (distance, index) in distanceIndexPairArray:\n",
    "                nearestNeighborDigits.append(self.trainingData[index][vectorSize-1])\n",
    "            guessLabelPair = (most_common(nearestNeighborDigits), dataMatrix[c_index][self.features])\n",
    "            digitGuessArray.append(guessLabelPair)\n",
    "        \n",
    "        return digitGuessArray\n",
    "    \n",
    "    #calculates the error of the classifier on the data\n",
    "    def calculateError(self, matrix, data):\n",
    "        guessesAndLabels = self.createGuessLabelVector(matrix,data)\n",
    "        numErrors = 0.\n",
    "        for guess, label in guessesAndLabels:\n",
    "            if guess != label:\n",
    "                numErrors += 1.\n",
    "                \n",
    "        return(numErrors/data.shape[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.883, 0.86], [0.089, 0.16666666666666666], [0.087, 0.13333333333333333], [0.115, 0.17666666666666667], [0.135, 0.17666666666666667], [0.157, 0.20333333333333334]]\n"
     ]
    }
   ],
   "source": [
    "#Part 1\n",
    "\n",
    "#create a list of k values and an empty error table\n",
    "kVals = [1,3,5,11,16,21]\n",
    "errorTable = []\n",
    "\n",
    "#loop through k, computing error values\n",
    "for errorTableIndex, k in enumerate(kVals):\n",
    "    someNN = kNN(k, 'hw2train.txt','hw2validate.txt','hw2test.txt')\n",
    "    trainingOutputMatrix = someNN.createDistanceIndexMatrix(someNN.trainingData)\n",
    "    validationOutputMatrix = someNN.createDistanceIndexMatrix(someNN.validationData)\n",
    "    \n",
    "    trainingError = someNN.calculateError(trainingOutputMatrix, someNN.trainingData)\n",
    "    validationError = someNN.calculateError(validationOutputMatrix, someNN.validationData)\n",
    "    \n",
    "    errorTable.append([trainingError, validationError])\n",
    "    \n",
    "print(errorTable)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.893  0.     0.     0.     0.     0.     0.     0.     0.     0.   ]\n",
      " [ 0.     1.     0.036  0.071  0.     0.     0.036  0.     0.     0.   ]\n",
      " [ 0.     0.     0.868  0.     0.     0.     0.     0.     0.026  0.   ]\n",
      " [ 0.     0.     0.     0.533  0.     0.033  0.     0.     0.     0.   ]\n",
      " [ 0.     0.     0.     0.     0.893  0.     0.     0.     0.     0.071]\n",
      " [ 0.     0.     0.     0.077  0.     0.808  0.     0.     0.     0.   ]\n",
      " [ 0.081  0.     0.     0.     0.     0.     0.919  0.     0.027  0.   ]\n",
      " [ 0.     0.     0.1    0.233  0.     0.1    0.067  1.     0.1    0.1  ]\n",
      " [ 0.     0.     0.036  0.071  0.     0.036  0.     0.     0.821  0.   ]\n",
      " [ 0.     0.     0.     0.037  0.111  0.     0.     0.     0.     0.815]]\n"
     ]
    }
   ],
   "source": [
    "#Part 2\n",
    "\n",
    "#create an empty confusion matrix and a 3NN classifier\n",
    "confusionMatrix = np.zeros((10,10), dtype='f8')\n",
    "threeNN = kNN(3, 'hw2train.txt','hw2validate.txt','hw2test.txt')\n",
    "\n",
    "#get a vector of (label-guess, labels) pairs\n",
    "testOutputMatrix = threeNN.createDistanceIndexMatrix(threeNN.testData)\n",
    "guessLabelVector = threeNN.createGuessLabelVector(testOutputMatrix, threeNN.testData)\n",
    "\n",
    "#go through each entry in the vector and use it to populate the confusion matrix\n",
    "for guess,label in guessLabelVector:\n",
    "    confusionMatrix[guess][label] += 1\n",
    "    \n",
    "#fix up the confusion matrix and print it\n",
    "confusionMatrix = np.round(confusionMatrix/(np.sum(confusionMatrix, axis=0)[:,None]), decimals=3)\n",
    "print(confusionMatrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}