2 knn cdist impl.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:e4edaa49f942e6e0369e17dbf25bff6468afac9c163af5fc6d824422597261f7"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%matplotlib inline\n",
      "import numpy as np\n",
      "from matplotlib import pyplot as plt"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# implementation of pairwise distance function\n",
      "\n",
      "# make datasets of coordinates\n",
      "I = -np.random.randint(10,size=(4,2))\n",
      "J = -np.random.randint(10,size=(3,2))\n",
      "\n",
      "I"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "array([[-4, -5],\n",
        "       [-9, -3],\n",
        "       [-7, -5],\n",
        "       [-2, -5]])"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "J"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "array([[-4, -2],\n",
        "       [ 0, -2],\n",
        "       [-6, -8]])"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We want to replicate what the scipy cdist function does:\n",
      "\n",
      "http://docs.scipy.org/doc/scipy-0.17.0/reference/generated/scipy.spatial.distance.cdist.html"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from scipy.spatial import distance\n",
      "\n",
      "distance.cdist(I, J)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "array([[ 3.        ,  5.        ,  3.60555128],\n",
        "       [ 5.09901951,  9.05538514,  5.83095189],\n",
        "       [ 4.24264069,  7.61577311,  3.16227766],\n",
        "       [ 3.60555128,  3.60555128,  5.        ]])"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# ignoring other metrics, we want to implement euclidean distance\n",
      "# sqrt((x0-x1)**2 + (y0-y1)**2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "np.mgrid[:I.shape[0],:J.shape[0]]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "array([[[0, 0, 0],\n",
        "        [1, 1, 1],\n",
        "        [2, 2, 2],\n",
        "        [3, 3, 3]],\n",
        "\n",
        "       [[0, 1, 2],\n",
        "        [0, 1, 2],\n",
        "        [0, 1, 2],\n",
        "        [0, 1, 2]]])"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# create a rectangular grid that is Ni by Nj\n",
      "i, j = np.mgrid[:I.shape[0],:J.shape[0]]\n",
      "i"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 20,
       "text": [
        "array([[0, 0, 0],\n",
        "       [1, 1, 1],\n",
        "       [2, 2, 2],\n",
        "       [3, 3, 3]])"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "j"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 25,
       "text": [
        "array([[0, 1, 2],\n",
        "       [0, 1, 2],\n",
        "       [0, 1, 2],\n",
        "       [0, 1, 2]])"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# now we want the pairs of points I[i] and J[j]\n",
      "J[j]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 24,
       "text": [
        "array([[[-4, -2],\n",
        "        [ 0, -2],\n",
        "        [-6, -8]],\n",
        "\n",
        "       [[-4, -2],\n",
        "        [ 0, -2],\n",
        "        [-6, -8]],\n",
        "\n",
        "       [[-4, -2],\n",
        "        [ 0, -2],\n",
        "        [-6, -8]],\n",
        "\n",
        "       [[-4, -2],\n",
        "        [ 0, -2],\n",
        "        [-6, -8]]])"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "J[j]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 32,
       "text": [
        "array([[[-6, -8],\n",
        "        [-1, -7],\n",
        "        [-7, -2]],\n",
        "\n",
        "       [[-6, -8],\n",
        "        [-1, -7],\n",
        "        [-7, -2]],\n",
        "\n",
        "       [[-6, -8],\n",
        "        [-1, -7],\n",
        "        [-7, -2]],\n",
        "\n",
        "       [[-6, -8],\n",
        "        [-1, -7],\n",
        "        [-7, -2]]])"
       ]
      }
     ],
     "prompt_number": 32
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# to subtract x0-x1 and y0-y1 simultaneously, we need this expression\n",
      "I[i] - J[j]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 25,
       "text": [
        "array([[[ 0, -3],\n",
        "        [-4, -3],\n",
        "        [ 2,  3]],\n",
        "\n",
        "       [[-5, -1],\n",
        "        [-9, -1],\n",
        "        [-3,  5]],\n",
        "\n",
        "       [[-3, -3],\n",
        "        [-7, -3],\n",
        "        [-1,  3]],\n",
        "\n",
        "       [[ 2, -3],\n",
        "        [-2, -3],\n",
        "        [ 4,  3]]])"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# then we square it\n",
      "s = (I[i] - J[j])**2\n",
      "s"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 28,
       "text": [
        "array([[[ 0,  9],\n",
        "        [16,  9],\n",
        "        [ 4,  9]],\n",
        "\n",
        "       [[25,  1],\n",
        "        [81,  1],\n",
        "        [ 9, 25]],\n",
        "\n",
        "       [[ 9,  9],\n",
        "        [49,  9],\n",
        "        [ 1,  9]],\n",
        "\n",
        "       [[ 4,  9],\n",
        "        [ 4,  9],\n",
        "        [16,  9]]])"
       ]
      }
     ],
     "prompt_number": 28
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# now take the sum of squares along the 3rd axis (we're summing (x0-x1)**2 and (y0-y1)**2)\n",
      "sq = np.sum(s,axis=2)\n",
      "sq"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 31,
       "text": [
        "array([[ 9, 25, 13],\n",
        "       [26, 82, 34],\n",
        "       [18, 58, 10],\n",
        "       [13, 13, 25]])"
       ]
      }
     ],
     "prompt_number": 31
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# now take the square root\n",
      "np.sqrt(sq)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 32,
       "text": [
        "array([[ 3.        ,  5.        ,  3.60555128],\n",
        "       [ 5.09901951,  9.05538514,  5.83095189],\n",
        "       [ 4.24264069,  7.61577311,  3.16227766],\n",
        "       [ 3.60555128,  3.60555128,  5.        ]])"
       ]
      }
     ],
     "prompt_number": 32
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# here it is as a function\n",
      "def cdist(I, J):\n",
      "    i, j = np.mgrid[:I.shape[0],:J.shape[0]]\n",
      "    return np.sqrt(np.sum((I[i] - J[j])**2,axis=2))\n",
      "\n",
      "cdist(I, J)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 33,
       "text": [
        "array([[ 3.        ,  5.        ,  3.60555128],\n",
        "       [ 5.09901951,  9.05538514,  5.83095189],\n",
        "       [ 4.24264069,  7.61577311,  3.16227766],\n",
        "       [ 3.60555128,  3.60555128,  5.        ]])"
       ]
      }
     ],
     "prompt_number": 33
    }
   ],
   "metadata": {}
  }
 ]
}