Chapter 7 - Clustering.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "- <a href='#7-1-1'>Exercise 7.1.1</a>\n",
    "- <a href='#7-1-2'>Exercise 7.1.2</a>\n",
    "- <a href='#7-2-1'>Exercise 7.2.1</a>\n",
    "- <a href='#7-2-2'>Exercise 7.2.2</a>\n",
    "- <a href='#7-2-3'>Exercise 7.2.3</a>\n",
    "    - <a href='#7-2-3-a'>Exercise 7.2.3 (a)</a>\n",
    "    - <a href='#7-2-3-b'>Exercise 7.2.3 (b)</a>\n",
    "- <a href='#7-2-4'>Exercise 7.2.4</a>\n",
    "- <a href='#7-2-5'>Exercise 7.2.5 Computing clustroids</a>\n",
    "- <a href='#using-heaps'>*Using Heaps to improve running time of hierchical clustering</a>\n",
    "- <a href='#7-3-1'> Exercise 7.3.1</a>\n",
    "- <a href='#7-3-2'> Exercise 7.3.2</a>\n",
    "- <a href='#7-3-4'> Exercise 7.3.4</a>\n",
    "- <a href='#7-3-5'> Exercise 7.3.5</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from __future__ import division"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='7-1-1'></a>\n",
    "# 7.1.1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Monte Carlo Integration of E(|X-Y|) where X and Y are independent U(0,1) random variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.33258109412725673"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 100000\n",
    "sum = 0\n",
    "for i in range(n):\n",
    "    x = np.random.rand()\n",
    "    y = np.random.rand()\n",
    "    sum += np.abs(x-y)\n",
    "sum/n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<a id='7-1-2'></a>\n",
    "# 7.1.2 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simulation to estimate the expected Euclidean distance between two random points of a unit square."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.33258109412725673"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 100000\n",
    "sum_ed = 0\n",
    "for i in range(n):\n",
    "    x = np.random.rand(2)\n",
    "    y = np.random.rand(2)\n",
    "    sum_ed += np.sqrt((x[0]-y[0])**2+(x[1]-y[1])**2)\n",
    "sum/n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='7-2-1'></a>\n",
    "# 7.2.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Euclidean(x,y):\n",
    "    \"\"\"\n",
    "    This function returns the Euclidean distance between two vectors\n",
    "    of a Euclidean space.\n",
    "    \"\"\"\n",
    "    xc = np.array(x)\n",
    "    yc = np.array(y)\n",
    "    return np.sqrt(np.dot(xc-yc,xc-yc))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.6055512754639891"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# sqrt[(4-1)^2+(4-2)^2]\n",
    "Euclidean(np.array([4,4]), np.array([1,2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Euclidean([1],[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mean(x):\n",
    "    \"\"\"\n",
    "    This function takes as input a lists of the clusters and outputs\n",
    "    the overall average of these clusters. This output is stored as\n",
    "    a tuple so that it can be used to access the cluster index.\n",
    "    \"\"\"\n",
    "    N = len(x)\n",
    "    n = len(x[0])\n",
    "    sum_vec = np.zeros(n)\n",
    "    for point in x:\n",
    "        sum_vec += np.array(point)\n",
    "    mean_vec = sum_vec / N\n",
    "    return tuple(mean_vec)\n",
    "\n",
    "# mean([[1],[2]])\n",
    "# mean([[1,2],[3,4],[5,6]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def agg_(clusters, print_summary = True):\n",
    "    \"\"\"\n",
    "    This function takes as input a dictionary of clusters in \n",
    "    Euclidean space and returns the Agglomerative clustering. \n",
    "    The key of the dictionary is the centroid of the corresponding\n",
    "    cluster.\n",
    "    \n",
    "    Note that the clustering agglomerative clustering is done in\n",
    "    place with respect to the clusters list input.\n",
    "    \"\"\"\n",
    "    step = 1\n",
    "    while len(clusters) > 1:\n",
    "#     while step < 3:\n",
    "        # clusters hash table (use centroids as hash keys)\n",
    "        clusters_ix = {el[0]:i for i,el in enumerate(clusters)}\n",
    "        # double loop to consider the minimal distance between all pairs of clusters\n",
    "        n = len(clusters)\n",
    "        min_dist = 2**32-1\n",
    "        c1 = None\n",
    "        c2 = None\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                # the distance between centroids of cluster i and cluster j\n",
    "                distance_ij = Euclidean(clusters[i][0], clusters[j][0])\n",
    "                if distance_ij < min_dist:\n",
    "                    min_dist = distance_ij\n",
    "                    c1 = clusters[i]\n",
    "                    c2 = clusters[j]\n",
    "        # merge the two clusters that result in minimum Euclidean distance\n",
    "        new_cluster = c1[1] + c2[1]\n",
    "        new_centroid = mean(new_cluster)\n",
    "        clusters.append([new_centroid, new_cluster])\n",
    "        # remove the merged clusters from the list \n",
    "        del clusters[max(clusters_ix[c1[0]],clusters_ix[c2[0]])]\n",
    "        del clusters[min(clusters_ix[c1[0]],clusters_ix[c2[0]])]\n",
    "        if print_summary:\n",
    "            print 'Step %d:' % step\n",
    "            print 'Merged clusters: %s and %s' %(str(c1[1]),str(c2[1]))\n",
    "            print 'Minimum distance: %f' % min_dist\n",
    "            print 'New clusters list:'\n",
    "            print [el[1] for el in clusters] \n",
    "            print 'New centroids:'\n",
    "            print [el[0] for el in clusters]\n",
    "            print ''\n",
    "            print '--------------------------------------------------------'\n",
    "            print ''\n",
    "        step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(1,), [[1]]],\n",
       " [(4,), [[4]]],\n",
       " [(9,), [[9]]],\n",
       " [(16,), [[16]]],\n",
       " [(25,), [[25]]],\n",
       " [(36,), [[36]]],\n",
       " [(49,), [[49]]],\n",
       " [(64,), [[64]]],\n",
       " [(81,), [[81]]]]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# an array storing centroid and cluster\n",
    "clusters = [[(i**2,), [[i**2]]] for i in range(1,10)]\n",
    "clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 1:\n",
      "Merged clusters: [[1]] and [[4]]\n",
      "Minimum distance: 3.000000\n",
      "New clusters list:\n",
      "[[[9]], [[16]], [[25]], [[36]], [[49]], [[64]], [[81]], [[1], [4]]]\n",
      "New centroids:\n",
      "[(9,), (16,), (25,), (36,), (49,), (64,), (81,), (2.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 2:\n",
      "Merged clusters: [[9]] and [[1], [4]]\n",
      "Minimum distance: 6.500000\n",
      "New clusters list:\n",
      "[[[16]], [[25]], [[36]], [[49]], [[64]], [[81]], [[9], [1], [4]]]\n",
      "New centroids:\n",
      "[(16,), (25,), (36,), (49,), (64,), (81,), (4.666666666666667,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 3:\n",
      "Merged clusters: [[16]] and [[25]]\n",
      "Minimum distance: 9.000000\n",
      "New clusters list:\n",
      "[[[36]], [[49]], [[64]], [[81]], [[9], [1], [4]], [[16], [25]]]\n",
      "New centroids:\n",
      "[(36,), (49,), (64,), (81,), (4.666666666666667,), (20.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 4:\n",
      "Merged clusters: [[36]] and [[49]]\n",
      "Minimum distance: 13.000000\n",
      "New clusters list:\n",
      "[[[64]], [[81]], [[9], [1], [4]], [[16], [25]], [[36], [49]]]\n",
      "New centroids:\n",
      "[(64,), (81,), (4.666666666666667,), (20.5,), (42.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 5:\n",
      "Merged clusters: [[9], [1], [4]] and [[16], [25]]\n",
      "Minimum distance: 15.833333\n",
      "New clusters list:\n",
      "[[[64]], [[81]], [[36], [49]], [[9], [1], [4], [16], [25]]]\n",
      "New centroids:\n",
      "[(64,), (81,), (42.5,), (11.0,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 6:\n",
      "Merged clusters: [[64]] and [[81]]\n",
      "Minimum distance: 17.000000\n",
      "New clusters list:\n",
      "[[[36], [49]], [[9], [1], [4], [16], [25]], [[64], [81]]]\n",
      "New centroids:\n",
      "[(42.5,), (11.0,), (72.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 7:\n",
      "Merged clusters: [[36], [49]] and [[64], [81]]\n",
      "Minimum distance: 30.000000\n",
      "New clusters list:\n",
      "[[[9], [1], [4], [16], [25]], [[36], [49], [64], [81]]]\n",
      "New centroids:\n",
      "[(11.0,), (57.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 8:\n",
      "Merged clusters: [[9], [1], [4], [16], [25]] and [[36], [49], [64], [81]]\n",
      "Minimum distance: 46.500000\n",
      "New clusters list:\n",
      "[[[9], [1], [4], [16], [25], [36], [49], [64], [81]]]\n",
      "New centroids:\n",
      "[(31.666666666666668,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "agg_(clusters)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(31.666666666666668,), [[9], [1], [4], [16], [25], [36], [49], [64], [81]]]]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#final clusters list\n",
    "clusters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='7-2-2'></a>\n",
    "# 7.2.2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) Using the minimum distance between any two points, one from each cluster as the criterion for selecting two clusters to merge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mins(x,y):\n",
    "    \"\"\"\n",
    "    This function takes as input two clusters of points (i.e. vectors) each of which \n",
    "    are represented by of their own individual lists. The output of this function\n",
    "    is the minimum distance between any two points one from each cluster\n",
    "    \"\"\"\n",
    "    nx = len(x)\n",
    "    ny = len(y)\n",
    "    running_min = 2**32 - 1\n",
    "    for pt_x in x:\n",
    "        for pt_y in y:\n",
    "            if Euclidean(pt_x,pt_y) < running_min:\n",
    "                running_min = Euclidean(pt_x,pt_y)\n",
    "    return running_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Euclidean([1],[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mins([[1]],[[3],[2],[0.5]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def agg_(clusters, print_summary = True, dist = 'Euclidean'):\n",
    "    \"\"\"\n",
    "    This function takes as input a dictionary of clusters in \n",
    "    Euclidean space and returns the Agglomerative clustering. \n",
    "    The key of the dictionary is the centroid of the corresponding\n",
    "    cluster.\n",
    "    \n",
    "    Note that the clustering agglomerative clustering is done in\n",
    "    place with respect to the clusters list input.\n",
    "    \"\"\"\n",
    "    \n",
    "    # specifying the distance function used\n",
    "    if dist == 'Euclidean':\n",
    "        f_dist = Euclidean\n",
    "        r_ = 0\n",
    "    if dist == 'mins':\n",
    "        f_dist = mins\n",
    "        r_ = 1\n",
    "    step = 1    \n",
    "    while len(clusters) > 1:\n",
    "#     while step < 3:\n",
    "        # clusters hash table (use centroids as hash keys)\n",
    "        clusters_ix = {el[0]:i for i,el in enumerate(clusters)}\n",
    "        # double loop to consider the minimal distance between all pairs of clusters\n",
    "        n = len(clusters)\n",
    "        min_dist = 2**32-1\n",
    "        c1 = None\n",
    "        c2 = None\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                # the distance between centroids of cluster i and cluster j\n",
    "                distance_ij = f_dist(clusters[i][r_], clusters[j][r_])\n",
    "                if distance_ij < min_dist:\n",
    "                    min_dist = distance_ij\n",
    "                    c1 = clusters[i]\n",
    "                    c2 = clusters[j]\n",
    "        # merge the two clusters that result in minimum Euclidean distance\n",
    "        new_cluster = c1[1] + c2[1]\n",
    "        new_centroid = mean(new_cluster)\n",
    "        clusters.append([new_centroid, new_cluster])\n",
    "        # remove the merged clusters from the list \n",
    "        del clusters[max(clusters_ix[c1[0]],clusters_ix[c2[0]])]\n",
    "        del clusters[min(clusters_ix[c1[0]],clusters_ix[c2[0]])]\n",
    "        if print_summary:\n",
    "            print 'Step %d:' % step\n",
    "            print 'Merged clusters: %s and %s' %(str(c1[1]),str(c2[1]))\n",
    "            print 'Minimum distance: %f' % min_dist\n",
    "            print 'New clusters list:'\n",
    "            print [el[1] for el in clusters] \n",
    "            print 'New centroids:'\n",
    "            print [el[0] for el in clusters]\n",
    "            print ''\n",
    "            print '--------------------------------------------------------'\n",
    "            print ''\n",
    "        step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(1,), [[1]]],\n",
       " [(4,), [[4]]],\n",
       " [(9,), [[9]]],\n",
       " [(16,), [[16]]],\n",
       " [(25,), [[25]]],\n",
       " [(36,), [[36]]],\n",
       " [(49,), [[49]]],\n",
       " [(64,), [[64]]],\n",
       " [(81,), [[81]]]]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# an array storing centroid and cluster\n",
    "clusters = [[(i**2,), [[i**2]]] for i in range(1,10)]\n",
    "clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 1:\n",
      "Merged clusters: [[1]] and [[4]]\n",
      "Minimum distance: 3.000000\n",
      "New clusters list:\n",
      "[[[9]], [[16]], [[25]], [[36]], [[49]], [[64]], [[81]], [[1], [4]]]\n",
      "New centroids:\n",
      "[(9,), (16,), (25,), (36,), (49,), (64,), (81,), (2.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 2:\n",
      "Merged clusters: [[9]] and [[1], [4]]\n",
      "Minimum distance: 5.000000\n",
      "New clusters list:\n",
      "[[[16]], [[25]], [[36]], [[49]], [[64]], [[81]], [[9], [1], [4]]]\n",
      "New centroids:\n",
      "[(16,), (25,), (36,), (49,), (64,), (81,), (4.666666666666667,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 3:\n",
      "Merged clusters: [[16]] and [[9], [1], [4]]\n",
      "Minimum distance: 7.000000\n",
      "New clusters list:\n",
      "[[[25]], [[36]], [[49]], [[64]], [[81]], [[16], [9], [1], [4]]]\n",
      "New centroids:\n",
      "[(25,), (36,), (49,), (64,), (81,), (7.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 4:\n",
      "Merged clusters: [[25]] and [[16], [9], [1], [4]]\n",
      "Minimum distance: 9.000000\n",
      "New clusters list:\n",
      "[[[36]], [[49]], [[64]], [[81]], [[25], [16], [9], [1], [4]]]\n",
      "New centroids:\n",
      "[(36,), (49,), (64,), (81,), (11.0,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 5:\n",
      "Merged clusters: [[36]] and [[25], [16], [9], [1], [4]]\n",
      "Minimum distance: 11.000000\n",
      "New clusters list:\n",
      "[[[49]], [[64]], [[81]], [[36], [25], [16], [9], [1], [4]]]\n",
      "New centroids:\n",
      "[(49,), (64,), (81,), (15.166666666666666,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 6:\n",
      "Merged clusters: [[49]] and [[36], [25], [16], [9], [1], [4]]\n",
      "Minimum distance: 13.000000\n",
      "New clusters list:\n",
      "[[[64]], [[81]], [[49], [36], [25], [16], [9], [1], [4]]]\n",
      "New centroids:\n",
      "[(64,), (81,), (20.0,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 7:\n",
      "Merged clusters: [[64]] and [[49], [36], [25], [16], [9], [1], [4]]\n",
      "Minimum distance: 15.000000\n",
      "New clusters list:\n",
      "[[[81]], [[64], [49], [36], [25], [16], [9], [1], [4]]]\n",
      "New centroids:\n",
      "[(81,), (25.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 8:\n",
      "Merged clusters: [[81]] and [[64], [49], [36], [25], [16], [9], [1], [4]]\n",
      "Minimum distance: 17.000000\n",
      "New clusters list:\n",
      "[[[81], [64], [49], [36], [25], [16], [9], [1], [4]]]\n",
      "New centroids:\n",
      "[(31.666666666666668,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "agg_(clusters, dist = 'mins')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) Using the average of the distances between pairs of points, one from each of the two clusters as our distance measurement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def avg(x,y):\n",
    "    \"\"\"\n",
    "    This function takes as input two clusters of points (i.e. vectors) each of which \n",
    "    are represented by of their own individual lists. The output of this function\n",
    "    is the average distance between any two points one from each of the two clusters.\n",
    "    \"\"\"\n",
    "    nx = len(x)\n",
    "    ny = len(y)\n",
    "    running_sum = 0\n",
    "    for pt_x in x:\n",
    "        for pt_y in y:\n",
    "            running_sum += Euclidean(pt_x,pt_y)\n",
    "    return running_sum/(nx*ny) # total number of pairs is nx*ny (i.e., by multiplication rule)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def agg_(clusters, print_summary = True, dist = 'Euclidean'):\n",
    "    \"\"\"\n",
    "    This function takes as input a dictionary of clusters in \n",
    "    Euclidean space and returns the Agglomerative clustering. \n",
    "    The key of the dictionary is the centroid of the corresponding\n",
    "    cluster.\n",
    "    \n",
    "    Note that the clustering agglomerative clustering is done in\n",
    "    place with respect to the clusters list input.\n",
    "    \"\"\"\n",
    "    \n",
    "    # specifying the distance function used\n",
    "    if dist == 'Euclidean':\n",
    "        f_dist = Euclidean\n",
    "        r_ = 0 # index to be used in the argument\n",
    "    if dist == 'mins':\n",
    "        f_dist = mins\n",
    "        r_ = 1\n",
    "    if dist == 'avg':\n",
    "        f_dist = avg\n",
    "        r_ = 1\n",
    "    \n",
    "    # start main code to conduct clustering\n",
    "    step = 1    \n",
    "    while len(clusters) > 1:\n",
    "#     while step < 3:\n",
    "        # clusters hash table (use centroids as hash keys)\n",
    "        clusters_ix = {el[0]:i for i,el in enumerate(clusters)}\n",
    "        # double loop to consider the minimal distance between all pairs of clusters\n",
    "        n = len(clusters)\n",
    "        min_dist = 2**32-1\n",
    "        c1 = None\n",
    "        c2 = None\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                # the distance between centroids of cluster i and cluster j\n",
    "                distance_ij = f_dist(clusters[i][r_], clusters[j][r_])\n",
    "                if distance_ij < min_dist:\n",
    "                    min_dist = distance_ij\n",
    "                    c1 = clusters[i]\n",
    "                    c2 = clusters[j]\n",
    "        # merge the two clusters that result in minimum Euclidean distance\n",
    "        new_cluster = c1[1] + c2[1]\n",
    "        new_centroid = mean(new_cluster)\n",
    "        clusters.append([new_centroid, new_cluster])\n",
    "        # remove the merged clusters from the list \n",
    "        del clusters[max(clusters_ix[c1[0]],clusters_ix[c2[0]])]\n",
    "        del clusters[min(clusters_ix[c1[0]],clusters_ix[c2[0]])]\n",
    "        if print_summary:\n",
    "            print 'Step %d:' % step\n",
    "            print 'Merged clusters: %s and %s' %(str(c1[1]),str(c2[1]))\n",
    "            print 'Minimum distance: %f' % min_dist\n",
    "            print 'New clusters list:'\n",
    "            print [el[1] for el in clusters] \n",
    "            print 'New centroids:'\n",
    "            print [el[0] for el in clusters]\n",
    "            print ''\n",
    "            print '--------------------------------------------------------'\n",
    "            print ''\n",
    "        step += 1\n",
    "    \n",
    "# Alternatively, can use np.mean to create the new centroid\n",
    "# new_centroid = tuple(np.mean(np.array(new_cluster),axis=0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(1,), [[1]]],\n",
       " [(4,), [[4]]],\n",
       " [(9,), [[9]]],\n",
       " [(16,), [[16]]],\n",
       " [(25,), [[25]]],\n",
       " [(36,), [[36]]],\n",
       " [(49,), [[49]]],\n",
       " [(64,), [[64]]],\n",
       " [(81,), [[81]]]]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# an array storing centroid and cluster\n",
    "clusters = [[(i**2,), [[i**2]]] for i in range(1,10)]\n",
    "clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 1:\n",
      "Merged clusters: [[1]] and [[4]]\n",
      "Minimum distance: 3.000000\n",
      "New clusters list:\n",
      "[[[9]], [[16]], [[25]], [[36]], [[49]], [[64]], [[81]], [[1], [4]]]\n",
      "New centroids:\n",
      "[(9,), (16,), (25,), (36,), (49,), (64,), (81,), (2.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 2:\n",
      "Merged clusters: [[9]] and [[1], [4]]\n",
      "Minimum distance: 6.500000\n",
      "New clusters list:\n",
      "[[[16]], [[25]], [[36]], [[49]], [[64]], [[81]], [[9], [1], [4]]]\n",
      "New centroids:\n",
      "[(16,), (25,), (36,), (49,), (64,), (81,), (4.666666666666667,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 3:\n",
      "Merged clusters: [[16]] and [[25]]\n",
      "Minimum distance: 9.000000\n",
      "New clusters list:\n",
      "[[[36]], [[49]], [[64]], [[81]], [[9], [1], [4]], [[16], [25]]]\n",
      "New centroids:\n",
      "[(36,), (49,), (64,), (81,), (4.666666666666667,), (20.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 4:\n",
      "Merged clusters: [[36]] and [[49]]\n",
      "Minimum distance: 13.000000\n",
      "New clusters list:\n",
      "[[[64]], [[81]], [[9], [1], [4]], [[16], [25]], [[36], [49]]]\n",
      "New centroids:\n",
      "[(64,), (81,), (4.666666666666667,), (20.5,), (42.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 5:\n",
      "Merged clusters: [[9], [1], [4]] and [[16], [25]]\n",
      "Minimum distance: 15.833333\n",
      "New clusters list:\n",
      "[[[64]], [[81]], [[36], [49]], [[9], [1], [4], [16], [25]]]\n",
      "New centroids:\n",
      "[(64,), (81,), (42.5,), (11.0,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 6:\n",
      "Merged clusters: [[64]] and [[81]]\n",
      "Minimum distance: 17.000000\n",
      "New clusters list:\n",
      "[[[36], [49]], [[9], [1], [4], [16], [25]], [[64], [81]]]\n",
      "New centroids:\n",
      "[(42.5,), (11.0,), (72.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 7:\n",
      "Merged clusters: [[36], [49]] and [[64], [81]]\n",
      "Minimum distance: 30.000000\n",
      "New clusters list:\n",
      "[[[9], [1], [4], [16], [25]], [[36], [49], [64], [81]]]\n",
      "New centroids:\n",
      "[(11.0,), (57.5,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 8:\n",
      "Merged clusters: [[9], [1], [4], [16], [25]] and [[36], [49], [64], [81]]\n",
      "Minimum distance: 46.500000\n",
      "New clusters list:\n",
      "[[[9], [1], [4], [16], [25], [36], [49], [64], [81]]]\n",
      "New centroids:\n",
      "[(31.666666666666668,)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "agg_(clusters,dist='avg')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='7-2-3'></a>\n",
    "# 7.2.3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using Euclidean distance of the centroids as for Example 7.2 ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "clusters = [[(4,10),[[4,10]]], [(7,10),[[7,10]]], [(4,8),[[4,8]]],\n",
    "           [(6,8),[[6,8]]],[(3,4),[[3,4]]],[(2,2),[[2,2]]],[(5,2),[[5,2]]],\n",
    "           [(12,6),[[12,6]]],[(10,5),[[10,5]]],[(11,4),[[11,4]]],[(9,3),[[9,3]]],\n",
    "           [(12,3),[[12,3]]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(4, 10), [[4, 10]]],\n",
       " [(7, 10), [[7, 10]]],\n",
       " [(4, 8), [[4, 8]]],\n",
       " [(6, 8), [[6, 8]]],\n",
       " [(3, 4), [[3, 4]]],\n",
       " [(2, 2), [[2, 2]]],\n",
       " [(5, 2), [[5, 2]]],\n",
       " [(12, 6), [[12, 6]]],\n",
       " [(10, 5), [[10, 5]]],\n",
       " [(11, 4), [[11, 4]]],\n",
       " [(9, 3), [[9, 3]]],\n",
       " [(12, 3), [[12, 3]]]]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 1:\n",
      "Merged clusters: [[10, 5]] and [[11, 4]]\n",
      "Minimum distance: 1.414214\n",
      "New clusters list:\n",
      "[[[4, 10]], [[7, 10]], [[4, 8]], [[6, 8]], [[3, 4]], [[2, 2]], [[5, 2]], [[12, 6]], [[9, 3]], [[12, 3]], [[10, 5], [11, 4]]]\n",
      "New centroids:\n",
      "[(4, 10), (7, 10), (4, 8), (6, 8), (3, 4), (2, 2), (5, 2), (12, 6), (9, 3), (12, 3), (10.5, 4.5)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 2:\n",
      "Merged clusters: [[4, 10]] and [[4, 8]]\n",
      "Minimum distance: 2.000000\n",
      "New clusters list:\n",
      "[[[7, 10]], [[6, 8]], [[3, 4]], [[2, 2]], [[5, 2]], [[12, 6]], [[9, 3]], [[12, 3]], [[10, 5], [11, 4]], [[4, 10], [4, 8]]]\n",
      "New centroids:\n",
      "[(7, 10), (6, 8), (3, 4), (2, 2), (5, 2), (12, 6), (9, 3), (12, 3), (10.5, 4.5), (4.0, 9.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 3:\n",
      "Merged clusters: [[12, 6]] and [[10, 5], [11, 4]]\n",
      "Minimum distance: 2.121320\n",
      "New clusters list:\n",
      "[[[7, 10]], [[6, 8]], [[3, 4]], [[2, 2]], [[5, 2]], [[9, 3]], [[12, 3]], [[4, 10], [4, 8]], [[12, 6], [10, 5], [11, 4]]]\n",
      "New centroids:\n",
      "[(7, 10), (6, 8), (3, 4), (2, 2), (5, 2), (9, 3), (12, 3), (4.0, 9.0), (11.0, 5.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 4:\n",
      "Merged clusters: [[7, 10]] and [[6, 8]]\n",
      "Minimum distance: 2.236068\n",
      "New clusters list:\n",
      "[[[3, 4]], [[2, 2]], [[5, 2]], [[9, 3]], [[12, 3]], [[4, 10], [4, 8]], [[12, 6], [10, 5], [11, 4]], [[7, 10], [6, 8]]]\n",
      "New centroids:\n",
      "[(3, 4), (2, 2), (5, 2), (9, 3), (12, 3), (4.0, 9.0), (11.0, 5.0), (6.5, 9.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 5:\n",
      "Merged clusters: [[3, 4]] and [[2, 2]]\n",
      "Minimum distance: 2.236068\n",
      "New clusters list:\n",
      "[[[5, 2]], [[9, 3]], [[12, 3]], [[4, 10], [4, 8]], [[12, 6], [10, 5], [11, 4]], [[7, 10], [6, 8]], [[3, 4], [2, 2]]]\n",
      "New centroids:\n",
      "[(5, 2), (9, 3), (12, 3), (4.0, 9.0), (11.0, 5.0), (6.5, 9.0), (2.5, 3.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 6:\n",
      "Merged clusters: [[12, 3]] and [[12, 6], [10, 5], [11, 4]]\n",
      "Minimum distance: 2.236068\n",
      "New clusters list:\n",
      "[[[5, 2]], [[9, 3]], [[4, 10], [4, 8]], [[7, 10], [6, 8]], [[3, 4], [2, 2]], [[12, 3], [12, 6], [10, 5], [11, 4]]]\n",
      "New centroids:\n",
      "[(5, 2), (9, 3), (4.0, 9.0), (6.5, 9.0), (2.5, 3.0), (11.25, 4.5)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 7:\n",
      "Merged clusters: [[4, 10], [4, 8]] and [[7, 10], [6, 8]]\n",
      "Minimum distance: 2.500000\n",
      "New clusters list:\n",
      "[[[5, 2]], [[9, 3]], [[3, 4], [2, 2]], [[12, 3], [12, 6], [10, 5], [11, 4]], [[4, 10], [4, 8], [7, 10], [6, 8]]]\n",
      "New centroids:\n",
      "[(5, 2), (9, 3), (2.5, 3.0), (11.25, 4.5), (5.25, 9.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 8:\n",
      "Merged clusters: [[5, 2]] and [[3, 4], [2, 2]]\n",
      "Minimum distance: 2.692582\n",
      "New clusters list:\n",
      "[[[9, 3]], [[12, 3], [12, 6], [10, 5], [11, 4]], [[4, 10], [4, 8], [7, 10], [6, 8]], [[5, 2], [3, 4], [2, 2]]]\n",
      "New centroids:\n",
      "[(9, 3), (11.25, 4.5), (5.25, 9.0), (3.3333333333333335, 2.6666666666666665)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 9:\n",
      "Merged clusters: [[9, 3]] and [[12, 3], [12, 6], [10, 5], [11, 4]]\n",
      "Minimum distance: 2.704163\n",
      "New clusters list:\n",
      "[[[4, 10], [4, 8], [7, 10], [6, 8]], [[5, 2], [3, 4], [2, 2]], [[9, 3], [12, 3], [12, 6], [10, 5], [11, 4]]]\n",
      "New centroids:\n",
      "[(5.25, 9.0), (3.3333333333333335, 2.6666666666666665), (10.800000000000001, 4.2000000000000002)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 10:\n",
      "Merged clusters: [[4, 10], [4, 8], [7, 10], [6, 8]] and [[5, 2], [3, 4], [2, 2]]\n",
      "Minimum distance: 6.617003\n",
      "New clusters list:\n",
      "[[[9, 3], [12, 3], [12, 6], [10, 5], [11, 4]], [[4, 10], [4, 8], [7, 10], [6, 8], [5, 2], [3, 4], [2, 2]]]\n",
      "New centroids:\n",
      "[(10.800000000000001, 4.2000000000000002), (4.4285714285714288, 6.2857142857142856)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 11:\n",
      "Merged clusters: [[9, 3], [12, 3], [12, 6], [10, 5], [11, 4]] and [[4, 10], [4, 8], [7, 10], [6, 8], [5, 2], [3, 4], [2, 2]]\n",
      "Minimum distance: 6.704126\n",
      "New clusters list:\n",
      "[[[9, 3], [12, 3], [12, 6], [10, 5], [11, 4], [4, 10], [4, 8], [7, 10], [6, 8], [5, 2], [3, 4], [2, 2]]]\n",
      "New centroids:\n",
      "[(7.083333333333333, 5.416666666666667)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "agg_(clusters)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Double checking the mean() function using numpy built in function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7.083333333333333, 5.416666666666667)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mean([[9, 3], [12, 3], [12, 6], [10, 5], [11, 4], [4, 10], [4, 8], [7, 10], [6, 8], [5, 2], [3, 4], [2, 2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "a = np.array([[9, 3], [12, 3], [12, 6], [10, 5], [11, 4], [4, 10], [4, 8], [7, 10], [6, 8], [5, 2], [3, 4], [2, 2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 7.08333333,  5.41666667])"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(a, axis = 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='7-2-3-a'></a>\n",
    "## 7.2.3 (a) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def radius(x,y=[]):\n",
    "    \"\"\"\n",
    "    This function takes as input two clusters of points (i.e. vectors) each of which \n",
    "    are represented by of their own individual lists. The output of this function\n",
    "    is the radius of the custer which results from the merge of x and y.\n",
    "    \n",
    "    If the input is simply one cluster, then the output is the radius of that\n",
    "    cluster.\n",
    "    \"\"\"\n",
    "    nx = len(x)\n",
    "    ny = len(y)\n",
    "    # merge two clusters x and y\n",
    "    merged_clus = x + y \n",
    "    # the centroid of the new merged cluster\n",
    "    merged_cent = mean(merged_clus)\n",
    "    # determine the radius of this merged cluster\n",
    "    # radius is the maximum distance between all the points and the centroid\n",
    "    radius = 0\n",
    "    for pt in merged_clus:\n",
    "        if Euclidean(pt,merged_cent) > radius:\n",
    "            radius = Euclidean(pt,merged_cent)\n",
    "    return radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.1633307652783942"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# checking this function with the result of Example 7.4\n",
    "radius([[12,6]],[[10,5],[11,4],[12,3],[9,3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.1633307652783942"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# can also use radius on a single cluster\n",
    "radius([[12,6],[10,5],[11,4],[12,3],[9,3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def agg_(clusters, print_summary = True, dist = 'Euclidean'):\n",
    "    \"\"\"\n",
    "    This function takes as input a dictionary of clusters in \n",
    "    Euclidean space and returns the Agglomerative clustering. \n",
    "    The key of the dictionary is the centroid of the corresponding\n",
    "    cluster.\n",
    "    \n",
    "    Note that the clustering agglomerative clustering is done in\n",
    "    place with respect to the clusters list input.\n",
    "    \"\"\"\n",
    "    \n",
    "    # specifying the distance function used\n",
    "    if dist == 'Euclidean':\n",
    "        f_dist = Euclidean\n",
    "        r_ = 0 # index to be used in the argument\n",
    "    if dist == 'mins':\n",
    "        f_dist = mins\n",
    "        r_ = 1\n",
    "    if dist == 'avg':\n",
    "        f_dist = avg\n",
    "        r_ = 1\n",
    "    if dist == 'radius':\n",
    "        f_dist = radius\n",
    "        r_ = 1\n",
    "    \n",
    "    # start main code to conduct clustering\n",
    "    step = 1    \n",
    "    while len(clusters) > 1:\n",
    "#     while step < 3:\n",
    "        # clusters hash table (use centroids as hash keys)\n",
    "        clusters_ix = {el[0]:i for i,el in enumerate(clusters)}\n",
    "        # double loop to consider the minimal distance between all pairs of clusters\n",
    "        n = len(clusters)\n",
    "        min_dist = 2**32-1\n",
    "        c1 = None\n",
    "        c2 = None\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                # the distance between centroids of cluster i and cluster j\n",
    "                distance_ij = f_dist(clusters[i][r_], clusters[j][r_])\n",
    "                if distance_ij < min_dist:\n",
    "                    min_dist = distance_ij\n",
    "                    c1 = clusters[i]\n",
    "                    c2 = clusters[j]\n",
    "        # merge the two clusters that result in minimum Euclidean distance\n",
    "        new_cluster = c1[1] + c2[1]\n",
    "        new_centroid = mean(new_cluster)\n",
    "        clusters.append([new_centroid, new_cluster])\n",
    "        # remove the merged clusters from the list \n",
    "        del clusters[max(clusters_ix[c1[0]],clusters_ix[c2[0]])]\n",
    "        del clusters[min(clusters_ix[c1[0]],clusters_ix[c2[0]])]\n",
    "        if print_summary:\n",
    "            print 'Step %d:' % step\n",
    "            print 'Merged clusters: %s and %s' %(str(c1[1]),str(c2[1]))\n",
    "            print 'Minimum distance: %f' % min_dist\n",
    "            print 'New clusters list:'\n",
    "            print [el[1] for el in clusters] \n",
    "            print 'New centroids:'\n",
    "            print [el[0] for el in clusters]\n",
    "            print ''\n",
    "            print '--------------------------------------------------------'\n",
    "            print ''\n",
    "        step += 1\n",
    "    \n",
    "# Alternatively, can use np.mean to create the new centroid\n",
    "# new_centroid = tuple(np.mean(np.array(new_cluster),axis=0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "clusters = [[(4,10),[[4,10]]], [(7,10),[[7,10]]], [(4,8),[[4,8]]],\n",
    "           [(6,8),[[6,8]]],[(3,4),[[3,4]]],[(2,2),[[2,2]]],[(5,2),[[5,2]]],\n",
    "           [(12,6),[[12,6]]],[(10,5),[[10,5]]],[(11,4),[[11,4]]],[(9,3),[[9,3]]],\n",
    "           [(12,3),[[12,3]]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 1:\n",
      "Merged clusters: [[10, 5]] and [[11, 4]]\n",
      "Minimum distance: 0.707107\n",
      "New clusters list:\n",
      "[[[4, 10]], [[7, 10]], [[4, 8]], [[6, 8]], [[3, 4]], [[2, 2]], [[5, 2]], [[12, 6]], [[9, 3]], [[12, 3]], [[10, 5], [11, 4]]]\n",
      "New centroids:\n",
      "[(4, 10), (7, 10), (4, 8), (6, 8), (3, 4), (2, 2), (5, 2), (12, 6), (9, 3), (12, 3), (10.5, 4.5)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 2:\n",
      "Merged clusters: [[4, 10]] and [[4, 8]]\n",
      "Minimum distance: 1.000000\n",
      "New clusters list:\n",
      "[[[7, 10]], [[6, 8]], [[3, 4]], [[2, 2]], [[5, 2]], [[12, 6]], [[9, 3]], [[12, 3]], [[10, 5], [11, 4]], [[4, 10], [4, 8]]]\n",
      "New centroids:\n",
      "[(7, 10), (6, 8), (3, 4), (2, 2), (5, 2), (12, 6), (9, 3), (12, 3), (10.5, 4.5), (4.0, 9.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 3:\n",
      "Merged clusters: [[7, 10]] and [[6, 8]]\n",
      "Minimum distance: 1.118034\n",
      "New clusters list:\n",
      "[[[3, 4]], [[2, 2]], [[5, 2]], [[12, 6]], [[9, 3]], [[12, 3]], [[10, 5], [11, 4]], [[4, 10], [4, 8]], [[7, 10], [6, 8]]]\n",
      "New centroids:\n",
      "[(3, 4), (2, 2), (5, 2), (12, 6), (9, 3), (12, 3), (10.5, 4.5), (4.0, 9.0), (6.5, 9.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 4:\n",
      "Merged clusters: [[3, 4]] and [[2, 2]]\n",
      "Minimum distance: 1.118034\n",
      "New clusters list:\n",
      "[[[5, 2]], [[12, 6]], [[9, 3]], [[12, 3]], [[10, 5], [11, 4]], [[4, 10], [4, 8]], [[7, 10], [6, 8]], [[3, 4], [2, 2]]]\n",
      "New centroids:\n",
      "[(5, 2), (12, 6), (9, 3), (12, 3), (10.5, 4.5), (4.0, 9.0), (6.5, 9.0), (2.5, 3.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 5:\n",
      "Merged clusters: [[12, 6]] and [[10, 5], [11, 4]]\n",
      "Minimum distance: 1.414214\n",
      "New clusters list:\n",
      "[[[5, 2]], [[9, 3]], [[12, 3]], [[4, 10], [4, 8]], [[7, 10], [6, 8]], [[3, 4], [2, 2]], [[12, 6], [10, 5], [11, 4]]]\n",
      "New centroids:\n",
      "[(5, 2), (9, 3), (12, 3), (4.0, 9.0), (6.5, 9.0), (2.5, 3.0), (11.0, 5.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 6:\n",
      "Merged clusters: [[9, 3]] and [[12, 3]]\n",
      "Minimum distance: 1.500000\n",
      "New clusters list:\n",
      "[[[5, 2]], [[4, 10], [4, 8]], [[7, 10], [6, 8]], [[3, 4], [2, 2]], [[12, 6], [10, 5], [11, 4]], [[9, 3], [12, 3]]]\n",
      "New centroids:\n",
      "[(5, 2), (4.0, 9.0), (6.5, 9.0), (2.5, 3.0), (11.0, 5.0), (10.5, 3.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 7:\n",
      "Merged clusters: [[5, 2]] and [[3, 4], [2, 2]]\n",
      "Minimum distance: 1.795055\n",
      "New clusters list:\n",
      "[[[4, 10], [4, 8]], [[7, 10], [6, 8]], [[12, 6], [10, 5], [11, 4]], [[9, 3], [12, 3]], [[5, 2], [3, 4], [2, 2]]]\n",
      "New centroids:\n",
      "[(4.0, 9.0), (6.5, 9.0), (11.0, 5.0), (10.5, 3.0), (3.3333333333333335, 2.6666666666666665)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 8:\n",
      "Merged clusters: [[4, 10], [4, 8]] and [[7, 10], [6, 8]]\n",
      "Minimum distance: 2.015564\n",
      "New clusters list:\n",
      "[[[12, 6], [10, 5], [11, 4]], [[9, 3], [12, 3]], [[5, 2], [3, 4], [2, 2]], [[4, 10], [4, 8], [7, 10], [6, 8]]]\n",
      "New centroids:\n",
      "[(11.0, 5.0), (10.5, 3.0), (3.3333333333333335, 2.6666666666666665), (5.25, 9.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 9:\n",
      "Merged clusters: [[12, 6], [10, 5], [11, 4]] and [[9, 3], [12, 3]]\n",
      "Minimum distance: 2.163331\n",
      "New clusters list:\n",
      "[[[5, 2], [3, 4], [2, 2]], [[4, 10], [4, 8], [7, 10], [6, 8]], [[12, 6], [10, 5], [11, 4], [9, 3], [12, 3]]]\n",
      "New centroids:\n",
      "[(3.3333333333333335, 2.6666666666666665), (5.25, 9.0), (10.800000000000001, 4.2000000000000002)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 10:\n",
      "Merged clusters: [[5, 2], [3, 4], [2, 2]] and [[4, 10], [4, 8], [7, 10], [6, 8]]\n",
      "Minimum distance: 4.925983\n",
      "New clusters list:\n",
      "[[[12, 6], [10, 5], [11, 4], [9, 3], [12, 3]], [[5, 2], [3, 4], [2, 2], [4, 10], [4, 8], [7, 10], [6, 8]]]\n",
      "New centroids:\n",
      "[(10.800000000000001, 4.2000000000000002), (4.4285714285714288, 6.2857142857142856)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 11:\n",
      "Merged clusters: [[12, 6], [10, 5], [11, 4], [9, 3], [12, 3]] and [[5, 2], [3, 4], [2, 2], [4, 10], [4, 8], [7, 10], [6, 8]]\n",
      "Minimum distance: 6.124858\n",
      "New clusters list:\n",
      "[[[12, 6], [10, 5], [11, 4], [9, 3], [12, 3], [5, 2], [3, 4], [2, 2], [4, 10], [4, 8], [7, 10], [6, 8]]]\n",
      "New centroids:\n",
      "[(7.083333333333333, 5.416666666666667)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "agg_(clusters, dist = 'radius')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='7-2-3-b'></a>\n",
    "## 7.2.3 (b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def diameter(x,y=[]):\n",
    "    \"\"\"\n",
    "    This function takes as input two clusters of points (i.e. vectors) each of which \n",
    "    are represented by of their own individual lists. The output of this function\n",
    "    is the diameter of the merged custer of x and y.\n",
    "    \n",
    "    If the input is simply one cluster, then the output is the diameter of that\n",
    "    cluster.\n",
    "    \"\"\"\n",
    "    # merge two clusters x and y\n",
    "    merged_clus = x + y \n",
    "    n = len(merged_clus)\n",
    "    # determine the diameter of this merged cluster\n",
    "    # diameter is the maximum distance between any two points of the cluster\n",
    "    diameter = 0\n",
    "    for i in range(n-1):\n",
    "        for j in range(i+1,n):\n",
    "            distance_ij = Euclidean(merged_clus[i],merged_clus[j])\n",
    "            if distance_ij > diameter:\n",
    "                diameter = distance_ij\n",
    "    return diameter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.2426406871192848"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# checking result with Example 7.4\n",
    "diameter([[12,6]],[[10,5],[11,4],[12,3],[9,3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.2426406871192848"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# using only one argument\n",
    "diameter([[12,6],[10,5],[11,4],[12,3],[9,3]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def agg_(clusters, print_summary = True, dist = 'Euclidean'):\n",
    "    \"\"\"\n",
    "    This function takes as input a dictionary of clusters in \n",
    "    Euclidean space and returns the Agglomerative clustering. \n",
    "    The key of the dictionary is the centroid of the corresponding\n",
    "    cluster.\n",
    "    \n",
    "    Note that the clustering agglomerative clustering is done in\n",
    "    place with respect to the clusters list input.\n",
    "    \"\"\"\n",
    "    \n",
    "    # specifying the distance function used\n",
    "    # r_ = 0 implies we consider centroids of the two clusters in merge step\n",
    "    # r_ = 1 means that we consider the points of the two clusters themselves in merge step\n",
    "    if dist == 'Euclidean':\n",
    "        f_dist = Euclidean\n",
    "        r_ = 0 \n",
    "    if dist == 'mins':\n",
    "        f_dist = mins\n",
    "        r_ = 1 \n",
    "    if dist == 'avg':\n",
    "        f_dist = avg\n",
    "        r_ = 1\n",
    "    if dist == 'radius':\n",
    "        f_dist = radius\n",
    "        r_ = 1\n",
    "    if dist == 'diameter':\n",
    "        f_dist = diameter\n",
    "        r_ = 1\n",
    "    \n",
    "    # start main code to conduct clustering\n",
    "    step = 1    \n",
    "    while len(clusters) > 1:\n",
    "#     while step < 3:\n",
    "        # clusters hash table (use centroids as hash keys)\n",
    "        clusters_ix = {el[0]:i for i,el in enumerate(clusters)}\n",
    "        # double loop to consider the minimal distance between all pairs of clusters\n",
    "        n = len(clusters)\n",
    "        min_dist = 2**32-1\n",
    "        c1 = None\n",
    "        c2 = None\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                # the distance between centroids of cluster i and cluster j\n",
    "                distance_ij = f_dist(clusters[i][r_], clusters[j][r_])\n",
    "                if distance_ij < min_dist:\n",
    "                    min_dist = distance_ij\n",
    "                    c1 = clusters[i]\n",
    "                    c2 = clusters[j]\n",
    "        # merge the two clusters that result in minimum Euclidean distance\n",
    "        new_cluster = c1[1] + c2[1]\n",
    "        new_centroid = mean(new_cluster)\n",
    "        clusters.append([new_centroid, new_cluster])\n",
    "        # remove the merged clusters from the list \n",
    "        del clusters[max(clusters_ix[c1[0]],clusters_ix[c2[0]])]\n",
    "        del clusters[min(clusters_ix[c1[0]],clusters_ix[c2[0]])]\n",
    "        if print_summary:\n",
    "            print 'Step %d:' % step\n",
    "            print 'Merged clusters: %s and %s' %(str(c1[1]),str(c2[1]))\n",
    "            print 'Minimum distance: %f' % min_dist\n",
    "            print 'New clusters list:'\n",
    "            print [el[1] for el in clusters] \n",
    "            print 'New centroids:'\n",
    "            print [el[0] for el in clusters]\n",
    "            print ''\n",
    "            print '--------------------------------------------------------'\n",
    "            print ''\n",
    "        step += 1\n",
    "    \n",
    "# Alternatively, can use np.mean to create the new centroid\n",
    "# new_centroid = tuple(np.mean(np.array(new_cluster),axis=0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "clusters = [[(4,10),[[4,10]]], [(7,10),[[7,10]]], [(4,8),[[4,8]]],\n",
    "           [(6,8),[[6,8]]],[(3,4),[[3,4]]],[(2,2),[[2,2]]],[(5,2),[[5,2]]],\n",
    "           [(12,6),[[12,6]]],[(10,5),[[10,5]]],[(11,4),[[11,4]]],[(9,3),[[9,3]]],\n",
    "           [(12,3),[[12,3]]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 1:\n",
      "Merged clusters: [[10, 5]] and [[11, 4]]\n",
      "Minimum distance: 1.414214\n",
      "New clusters list:\n",
      "[[[4, 10]], [[7, 10]], [[4, 8]], [[6, 8]], [[3, 4]], [[2, 2]], [[5, 2]], [[12, 6]], [[9, 3]], [[12, 3]], [[10, 5], [11, 4]]]\n",
      "New centroids:\n",
      "[(4, 10), (7, 10), (4, 8), (6, 8), (3, 4), (2, 2), (5, 2), (12, 6), (9, 3), (12, 3), (10.5, 4.5)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 2:\n",
      "Merged clusters: [[4, 10]] and [[4, 8]]\n",
      "Minimum distance: 2.000000\n",
      "New clusters list:\n",
      "[[[7, 10]], [[6, 8]], [[3, 4]], [[2, 2]], [[5, 2]], [[12, 6]], [[9, 3]], [[12, 3]], [[10, 5], [11, 4]], [[4, 10], [4, 8]]]\n",
      "New centroids:\n",
      "[(7, 10), (6, 8), (3, 4), (2, 2), (5, 2), (12, 6), (9, 3), (12, 3), (10.5, 4.5), (4.0, 9.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 3:\n",
      "Merged clusters: [[7, 10]] and [[6, 8]]\n",
      "Minimum distance: 2.236068\n",
      "New clusters list:\n",
      "[[[3, 4]], [[2, 2]], [[5, 2]], [[12, 6]], [[9, 3]], [[12, 3]], [[10, 5], [11, 4]], [[4, 10], [4, 8]], [[7, 10], [6, 8]]]\n",
      "New centroids:\n",
      "[(3, 4), (2, 2), (5, 2), (12, 6), (9, 3), (12, 3), (10.5, 4.5), (4.0, 9.0), (6.5, 9.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 4:\n",
      "Merged clusters: [[3, 4]] and [[2, 2]]\n",
      "Minimum distance: 2.236068\n",
      "New clusters list:\n",
      "[[[5, 2]], [[12, 6]], [[9, 3]], [[12, 3]], [[10, 5], [11, 4]], [[4, 10], [4, 8]], [[7, 10], [6, 8]], [[3, 4], [2, 2]]]\n",
      "New centroids:\n",
      "[(5, 2), (12, 6), (9, 3), (12, 3), (10.5, 4.5), (4.0, 9.0), (6.5, 9.0), (2.5, 3.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 5:\n",
      "Merged clusters: [[12, 6]] and [[10, 5], [11, 4]]\n",
      "Minimum distance: 2.236068\n",
      "New clusters list:\n",
      "[[[5, 2]], [[9, 3]], [[12, 3]], [[4, 10], [4, 8]], [[7, 10], [6, 8]], [[3, 4], [2, 2]], [[12, 6], [10, 5], [11, 4]]]\n",
      "New centroids:\n",
      "[(5, 2), (9, 3), (12, 3), (4.0, 9.0), (6.5, 9.0), (2.5, 3.0), (11.0, 5.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 6:\n",
      "Merged clusters: [[5, 2]] and [[3, 4], [2, 2]]\n",
      "Minimum distance: 3.000000\n",
      "New clusters list:\n",
      "[[[9, 3]], [[12, 3]], [[4, 10], [4, 8]], [[7, 10], [6, 8]], [[12, 6], [10, 5], [11, 4]], [[5, 2], [3, 4], [2, 2]]]\n",
      "New centroids:\n",
      "[(9, 3), (12, 3), (4.0, 9.0), (6.5, 9.0), (11.0, 5.0), (3.3333333333333335, 2.6666666666666665)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 7:\n",
      "Merged clusters: [[9, 3]] and [[12, 3]]\n",
      "Minimum distance: 3.000000\n",
      "New clusters list:\n",
      "[[[4, 10], [4, 8]], [[7, 10], [6, 8]], [[12, 6], [10, 5], [11, 4]], [[5, 2], [3, 4], [2, 2]], [[9, 3], [12, 3]]]\n",
      "New centroids:\n",
      "[(4.0, 9.0), (6.5, 9.0), (11.0, 5.0), (3.3333333333333335, 2.6666666666666665), (10.5, 3.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 8:\n",
      "Merged clusters: [[4, 10], [4, 8]] and [[7, 10], [6, 8]]\n",
      "Minimum distance: 3.605551\n",
      "New clusters list:\n",
      "[[[12, 6], [10, 5], [11, 4]], [[5, 2], [3, 4], [2, 2]], [[9, 3], [12, 3]], [[4, 10], [4, 8], [7, 10], [6, 8]]]\n",
      "New centroids:\n",
      "[(11.0, 5.0), (3.3333333333333335, 2.6666666666666665), (10.5, 3.0), (5.25, 9.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 9:\n",
      "Merged clusters: [[12, 6], [10, 5], [11, 4]] and [[9, 3], [12, 3]]\n",
      "Minimum distance: 4.242641\n",
      "New clusters list:\n",
      "[[[5, 2], [3, 4], [2, 2]], [[4, 10], [4, 8], [7, 10], [6, 8]], [[12, 6], [10, 5], [11, 4], [9, 3], [12, 3]]]\n",
      "New centroids:\n",
      "[(3.3333333333333335, 2.6666666666666665), (5.25, 9.0), (10.800000000000001, 4.2000000000000002)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 10:\n",
      "Merged clusters: [[5, 2], [3, 4], [2, 2]] and [[4, 10], [4, 8], [7, 10], [6, 8]]\n",
      "Minimum distance: 9.433981\n",
      "New clusters list:\n",
      "[[[12, 6], [10, 5], [11, 4], [9, 3], [12, 3]], [[5, 2], [3, 4], [2, 2], [4, 10], [4, 8], [7, 10], [6, 8]]]\n",
      "New centroids:\n",
      "[(10.800000000000001, 4.2000000000000002), (4.4285714285714288, 6.2857142857142856)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 11:\n",
      "Merged clusters: [[12, 6], [10, 5], [11, 4], [9, 3], [12, 3]] and [[5, 2], [3, 4], [2, 2], [4, 10], [4, 8], [7, 10], [6, 8]]\n",
      "Minimum distance: 10.770330\n",
      "New clusters list:\n",
      "[[[12, 6], [10, 5], [11, 4], [9, 3], [12, 3], [5, 2], [3, 4], [2, 2], [4, 10], [4, 8], [7, 10], [6, 8]]]\n",
      "New centroids:\n",
      "[(7.083333333333333, 5.416666666666667)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "agg_(clusters, dist = 'diameter')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='7-2-4'></a>\n",
    "# 7.2.4 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) Computing density if we take # of points in a cluster divided by square of the radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(5.25, 9.0)\n",
      "(3.3333333333333335, 2.6666666666666665)\n",
      "(10.800000000000001, 4.2000000000000002)\n"
     ]
    }
   ],
   "source": [
    "# lists of the three clusters of Figure 7.2\n",
    "c1 = [[4,10],[4,8],[6,8],[7,10]]\n",
    "c2 = [[3,4],[2,2],[5,2]]\n",
    "c3 = [[10,5],[9,3],[11,4],[12,3],[12,6]]\n",
    "\n",
    "# printing the centers of these clusters\n",
    "print mean(c1)\n",
    "print mean(c2)\n",
    "print mean(c3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# compute the radius of each cluster\n",
    "radius1 = radius(c1)\n",
    "radius2 = radius(c2)\n",
    "radius3 = radius(c3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.98461538461538478, 0.93103448275862088, 1.0683760683760679]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# compute density\n",
    "density1 = len(c1)/radius1**2\n",
    "density2 = len(c2)/radius2**2\n",
    "density3 = len(c3)/radius3**2\n",
    "\n",
    "[density1, density2, density3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.28847771236333053, 0.27931034482758615, 0.20703598867771936]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# density of merging any two of these clusers\n",
    "c12 = c1 + c2\n",
    "c13 = c1 + c3\n",
    "c23 = c2 + c3\n",
    "\n",
    "radius12 = radius(c12)\n",
    "radius13 = radius(c13)\n",
    "radius23 = radius(c23)\n",
    "\n",
    "density12 = len(c12)/radius12**2\n",
    "density13 = len(c13)/radius13**2\n",
    "density23 = len(c23)/radius23**2\n",
    "\n",
    "[density12, density13, density23]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The densities have decreased substantially. Hence, merging clusters do not result in adequate clusters.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) repeating (a) except this time the denominator of the density is given by diameter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3.6055512754639891, 3.0, 4.2426406871192848]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# compute the diameter of each cluster\n",
    "diameter1 = diameter(c1)\n",
    "diameter2 = diameter(c2)\n",
    "diameter3 = diameter(c3)\n",
    "\n",
    "[diameter1,diameter2,diameter3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.1094003924504583, 1.0, 1.1785113019775793]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# compute density\n",
    "density1 = len(c1)/diameter1\n",
    "density2 = len(c2)/diameter2\n",
    "density3 = len(c3)/diameter3\n",
    "\n",
    "[density1, density2, density3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.74199851600445199, 0.84664878154523748, 0.74278135270820744]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# density of merging any two of these clusers\n",
    "c12 = c1 + c2\n",
    "c13 = c1 + c3\n",
    "c23 = c2 + c3\n",
    "\n",
    "diameter12 = diameter(c12)\n",
    "diameter13 = diameter(c13)\n",
    "diameter23 = diameter(c23)\n",
    "\n",
    "density12 = len(c12)/diameter12\n",
    "density13 = len(c13)/diameter13\n",
    "density23 = len(c23)/diameter23\n",
    "\n",
    "[density12, density13, density23]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The densities have decreased substantially. Hence, merging clusters do not result in adequate clusters.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='7-2-5'></a>\n",
    "# 7.2.5 Computing clustroids "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Criterion for selecting the clustroid: the point with the minimum sum of distance to other point in the cluster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def clustroid(x):\n",
    "    \"\"\"\n",
    "    This function takes as an input a cluster x (i.e. a list of points)\n",
    "    and returns the clustroid of that cluster. The clustroid is \n",
    "    a point within the cluster itself which \"best\" represents the cluster\n",
    "    to which it belongs.\n",
    "    \n",
    "    The criteria for this function is the minimum sum of distance to the \n",
    "    other points in the cluster.\n",
    "    \n",
    "    Might be a good idea to use a heap.\n",
    "    \"\"\"\n",
    "    sums = {tuple(pt):0 for pt in x}\n",
    "    sum = 0\n",
    "    for pt in x:\n",
    "        for pt_compare in x:\n",
    "            sum += Euclidean(pt,pt_compare) # can do this because Euclidean(x,x)=0\n",
    "        sums[tuple(pt)] = sum\n",
    "    return min(sums.values()), sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7.8284271247461898,\n",
       " {(4, 8): 15.433978400210179,\n",
       "  (4, 10): 7.8284271247461898,\n",
       "  (6, 8): 22.498473502456161,\n",
       "  (7, 10): 31.340092755419938})"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clustroid(c1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5.0644951022459797,\n",
       " {(2, 2): 10.300563079745769,\n",
       "  (3, 4): 5.0644951022459797,\n",
       "  (5, 2): 16.128990204491959})"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clustroid(c2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(8.7147766421188653,\n",
       " {(9, 3): 20.429553284237727,\n",
       "  (10, 5): 8.7147766421188653,\n",
       "  (11, 4): 27.730116363983498,\n",
       "  (12, 3): 37.972757051102782,\n",
       "  (12, 6): 49.687533693221653})"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clustroid(c3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='using-heaps'></a>\n",
    "# Using Heaps to improve running time of the hierarchical clustering "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import heapq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using heaps to increase the speed of the hierarchical clustering merge step:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "clusters = [[(4,10),[[4,10]]], [(7,10),[[7,10]]], [(4,8),[[4,8]]],\n",
    "           [(6,8),[[6,8]]],[(3,4),[[3,4]]],[(2,2),[[2,2]]],[(5,2),[[5,2]]],\n",
    "            [(12,6),[[12,6]]],[(10,5),[[10,5]]],[(11,4),[[11,4]]],[(9,3),[[9,3]]],\n",
    "           [(12,3),[[12,3]]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{((2, 2),): [[2, 2]],\n",
       " ((3, 4),): [[3, 4]],\n",
       " ((4, 8),): [[4, 8]],\n",
       " ((4, 10),): [[4, 10]],\n",
       " ((5, 2),): [[5, 2]],\n",
       " ((6, 8),): [[6, 8]],\n",
       " ((7, 10),): [[7, 10]],\n",
       " ((9, 3),): [[9, 3]],\n",
       " ((10, 5),): [[10, 5]],\n",
       " ((11, 4),): [[11, 4]],\n",
       " ((12, 3),): [[12, 3]],\n",
       " ((12, 6),): [[12, 6]]}"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# creating a dictionary tracking the remaining clusters\n",
    "clusters_remaining = {tuple(tuple(el) for el in clusters[i][1]):clusters[i][1] \n",
    "                      for i in range(len(clusters))}\n",
    "clusters_remaining"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# creating a heap h with item keys (dist, pair)\n",
    "h = []\n",
    "n = len(clusters)\n",
    "f_dist = Euclidean\n",
    "r_ = 0\n",
    "clusters_handle = {} # keys are centroids of the pairs of clusters\n",
    "for i in range(n-1):\n",
    "    for j in range(i+1,n):\n",
    "        distance_ij = f_dist(clusters[i][r_],clusters[j][r_])\n",
    "        ati = tuple(tuple(el) for el in clusters[i][1])\n",
    "        tun = tuple(tuple(el) for el in clusters[j][1])\n",
    "        foo = [distance_ij, (tuple(ati),tuple(tun)), \n",
    "               clusters[i][1]+clusters[j][1]]\n",
    "        clusters_handle[(tuple(ati),tuple(tun))] = foo\n",
    "        heapq.heappush(h,foo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1.4142135623730951, (((10, 5),), ((11, 4),)), [[10, 5], [11, 4]]],\n",
       " [1.4142135623730951, (((11, 4),), ((12, 3),)), [[11, 4], [12, 3]]],\n",
       " [2.0, (((4, 8),), ((6, 8),)), [[4, 8], [6, 8]]],\n",
       " [2.0, (((4, 10),), ((4, 8),)), [[4, 10], [4, 8]]],\n",
       " [2.8284271247461903, (((3, 4),), ((5, 2),)), [[3, 4], [5, 2]]],\n",
       " [2.8284271247461903, (((4, 10),), ((6, 8),)), [[4, 10], [6, 8]]],\n",
       " [2.2360679774997898, (((7, 10),), ((6, 8),)), [[7, 10], [6, 8]]],\n",
       " [2.2360679774997898, (((3, 4),), ((2, 2),)), [[3, 4], [2, 2]]],\n",
       " [5.0, (((6, 8),), ((10, 5),)), [[6, 8], [10, 5]]],\n",
       " [3.0, (((4, 10),), ((7, 10),)), [[4, 10], [7, 10]]]]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "REMOVED = '<removed-cluster>'\n",
    "def remove_clusters(i):\n",
    "    \"\"\"\n",
    "    This function lazily deletes any clusters that have been \n",
    "    merged from the dictionary clusters_handle.\n",
    "    \"\"\"\n",
    "    for key in clusters_handle.keys():\n",
    "        if i in key:\n",
    "            # mark task as removed\n",
    "            clusters_handle[key][1] = REMOVED"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def pop_cluster():\n",
    "    \"\"\"\n",
    "    To maintain the heap property, we lazily deleted merged clusters.\n",
    "    In this function, we only pop (extract) minimum distance \n",
    "    clusters if the merged cluster has not been removed.\n",
    "    \"\"\"\n",
    "    # this pops until it returns something\n",
    "    while h: # while there are entries in the heap\n",
    "        distance, tup, merged_clus = heapq.heappop(h)\n",
    "        if tup != REMOVED:\n",
    "            del clusters_handle[tup]\n",
    "            # remove newly merged clusters from heap task dict and clusters_remaining dictionary\n",
    "            for cluster in tup:\n",
    "                remove_clusters(cluster)\n",
    "                del clusters_remaining[cluster]\n",
    "            return distance, tup, merged_clus\n",
    "    raise KeyError('pop from an empty heap')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def add_cluster(entry):\n",
    "    \"\"\"\n",
    "    This function takes the pop'ed entry and calculates the\n",
    "    distances of the newly-merged cluster to all of the clusters\n",
    "    in the clusters_remaining dictionary.\n",
    "    \"\"\"\n",
    "    distance, tup, merged_clus = entry\n",
    "    tup = tup[0] + tup[1]\n",
    "    centroid = mean(merged_clus)\n",
    "    # for every entry in the clusters_remaining compute new distances\n",
    "    for tup_cmp, clus_cmp in clusters_remaining.items():\n",
    "        centroid_cmp = mean(clus_cmp)\n",
    "        new_distance = Euclidean(centroid, centroid_cmp)\n",
    "        # generate new entry for the heap\n",
    "        new_tup = (tup, tup_cmp)\n",
    "        new_merged_clus = merged_clus + clus_cmp\n",
    "        new_entry = [new_distance, new_tup, new_merged_clus]\n",
    "        # add new entry to clusters_handle \n",
    "        clusters_handle[new_tup] = new_entry\n",
    "        # add new entry to the heap\n",
    "        heapq.heappush(h,new_entry)\n",
    "    # add the recently merged cluster to clusters_remaining dict\n",
    "    clusters_remaining[tup] = merged_clus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Run the following lines in sequence to see the what each function does\n",
    "\n",
    "# entry = pop_cluster()\n",
    "# clusters_remaining\n",
    "# add_cluster(entry)\n",
    "# clusters_remaining\n",
    "\n",
    "# clusters_handle\n",
    "# h[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def agg_heap(clusters, print_summary = True):\n",
    "    \"\"\"\n",
    "    This function takes as input a dictionary of clusters in \n",
    "    Euclidean space and returns the Agglomerative clustering. This is\n",
    "    an improvement over agg_ since it exploits the heap data structure.\n",
    "    \n",
    "    Note that Python heapq and queue module do not support element deletion.\n",
    "    As a result, this algorithm uses lazy deletion.\n",
    "    \"\"\"\n",
    "    # add methods here to create heap from clusters and \n",
    "    # other necessary components\n",
    "    #clusters_remaining = {tuple(tuple(el) for el in clusters[i][1]):clusters[i][1] \n",
    "                      #for i in range(len(clusters))}\n",
    "    \n",
    "    # start main code to conduct clustering\n",
    "    step = 1    \n",
    "    while len(clusters_remaining) > 1:\n",
    "        entry = pop_cluster()\n",
    "        add_cluster(entry)\n",
    "        distance, tup, merged_clus = entry\n",
    "        if print_summary:\n",
    "            print 'Step %d:' % step\n",
    "            print 'Merged clusters: %s and %s' %(str(tup[0]),str(tup[1]))\n",
    "            print 'Minimum distance: %f' % distance\n",
    "            print 'New clusters list:'\n",
    "            print [key for key in clusters_remaining.keys()] \n",
    "            print 'New centroids:'\n",
    "            print [mean(el) for el in clusters_remaining.values()]\n",
    "            print ''\n",
    "            print '--------------------------------------------------------'\n",
    "            print ''\n",
    "        step += 1\n",
    "    \n",
    "# Alternatively, can use np.mean to create the new centroid\n",
    "# new_centroid = tuple(np.mean(np.array(new_cluster),axis=0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "clusters = [[(4,10),[[4,10]]], [(7,10),[[7,10]]], [(4,8),[[4,8]]],\n",
    "           [(6,8),[[6,8]]],[(3,4),[[3,4]]],[(2,2),[[2,2]]],[(5,2),[[5,2]]],\n",
    "            [(12,6),[[12,6]]],[(10,5),[[10,5]]],[(11,4),[[11,4]]],[(9,3),[[9,3]]],\n",
    "           [(12,3),[[12,3]]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 1:\n",
      "Merged clusters: ((10, 5),) and ((11, 4),)\n",
      "Minimum distance: 1.414214\n",
      "New clusters list:\n",
      "[((7, 10),), ((4, 10),), ((3, 4),), ((2, 2),), ((5, 2),), ((12, 3),), ((6, 8),), ((9, 3),), ((4, 8),), ((12, 6),), ((10, 5), (11, 4))]\n",
      "New centroids:\n",
      "[(7.0, 10.0), (4.0, 10.0), (3.0, 4.0), (2.0, 2.0), (5.0, 2.0), (12.0, 3.0), (6.0, 8.0), (9.0, 3.0), (4.0, 8.0), (12.0, 6.0), (10.5, 4.5)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 2:\n",
      "Merged clusters: ((4, 8),) and ((6, 8),)\n",
      "Minimum distance: 2.000000\n",
      "New clusters list:\n",
      "[((7, 10),), ((4, 10),), ((3, 4),), ((2, 2),), ((5, 2),), ((12, 3),), ((4, 8), (6, 8)), ((9, 3),), ((12, 6),), ((10, 5), (11, 4))]\n",
      "New centroids:\n",
      "[(7.0, 10.0), (4.0, 10.0), (3.0, 4.0), (2.0, 2.0), (5.0, 2.0), (12.0, 3.0), (5.0, 8.0), (9.0, 3.0), (12.0, 6.0), (10.5, 4.5)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 3:\n",
      "Merged clusters: ((10, 5), (11, 4)) and ((9, 3),)\n",
      "Minimum distance: 2.121320\n",
      "New clusters list:\n",
      "[((7, 10),), ((4, 10),), ((3, 4),), ((2, 2),), ((5, 2),), ((12, 3),), ((10, 5), (11, 4), (9, 3)), ((4, 8), (6, 8)), ((12, 6),)]\n",
      "New centroids:\n",
      "[(7.0, 10.0), (4.0, 10.0), (3.0, 4.0), (2.0, 2.0), (5.0, 2.0), (12.0, 3.0), (10.0, 4.0), (5.0, 8.0), (12.0, 6.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 4:\n",
      "Merged clusters: ((3, 4),) and ((2, 2),)\n",
      "Minimum distance: 2.236068\n",
      "New clusters list:\n",
      "[((7, 10),), ((4, 10),), ((3, 4), (2, 2)), ((5, 2),), ((12, 3),), ((10, 5), (11, 4), (9, 3)), ((4, 8), (6, 8)), ((12, 6),)]\n",
      "New centroids:\n",
      "[(7.0, 10.0), (4.0, 10.0), (2.5, 3.0), (5.0, 2.0), (12.0, 3.0), (10.0, 4.0), (5.0, 8.0), (12.0, 6.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 5:\n",
      "Merged clusters: ((4, 8), (6, 8)) and ((4, 10),)\n",
      "Minimum distance: 2.236068\n",
      "New clusters list:\n",
      "[((7, 10),), ((3, 4), (2, 2)), ((5, 2),), ((12, 3),), ((10, 5), (11, 4), (9, 3)), ((12, 6),), ((4, 8), (6, 8), (4, 10))]\n",
      "New centroids:\n",
      "[(7.0, 10.0), (2.5, 3.0), (5.0, 2.0), (12.0, 3.0), (10.0, 4.0), (12.0, 6.0), (4.666666666666667, 8.6666666666666661)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 6:\n",
      "Merged clusters: ((10, 5), (11, 4), (9, 3)) and ((12, 3),)\n",
      "Minimum distance: 2.236068\n",
      "New clusters list:\n",
      "[((10, 5), (11, 4), (9, 3), (12, 3)), ((7, 10),), ((3, 4), (2, 2)), ((5, 2),), ((12, 6),), ((4, 8), (6, 8), (4, 10))]\n",
      "New centroids:\n",
      "[(10.5, 3.75), (7.0, 10.0), (2.5, 3.0), (5.0, 2.0), (12.0, 6.0), (4.666666666666667, 8.6666666666666661)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 7:\n",
      "Merged clusters: ((4, 8), (6, 8), (4, 10)) and ((7, 10),)\n",
      "Minimum distance: 2.687419\n",
      "New clusters list:\n",
      "[((10, 5), (11, 4), (9, 3), (12, 3)), ((4, 8), (6, 8), (4, 10), (7, 10)), ((3, 4), (2, 2)), ((5, 2),), ((12, 6),)]\n",
      "New centroids:\n",
      "[(10.5, 3.75), (5.25, 9.0), (2.5, 3.0), (5.0, 2.0), (12.0, 6.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 8:\n",
      "Merged clusters: ((3, 4), (2, 2)) and ((5, 2),)\n",
      "Minimum distance: 2.692582\n",
      "New clusters list:\n",
      "[((10, 5), (11, 4), (9, 3), (12, 3)), ((4, 8), (6, 8), (4, 10), (7, 10)), ((3, 4), (2, 2), (5, 2)), ((12, 6),)]\n",
      "New centroids:\n",
      "[(10.5, 3.75), (5.25, 9.0), (3.3333333333333335, 2.6666666666666665), (12.0, 6.0)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 9:\n",
      "Merged clusters: ((10, 5), (11, 4), (9, 3), (12, 3)) and ((12, 6),)\n",
      "Minimum distance: 2.704163\n",
      "New clusters list:\n",
      "[((4, 8), (6, 8), (4, 10), (7, 10)), ((3, 4), (2, 2), (5, 2)), ((10, 5), (11, 4), (9, 3), (12, 3), (12, 6))]\n",
      "New centroids:\n",
      "[(5.25, 9.0), (3.3333333333333335, 2.6666666666666665), (10.800000000000001, 4.2000000000000002)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 10:\n",
      "Merged clusters: ((3, 4), (2, 2), (5, 2)) and ((4, 8), (6, 8), (4, 10), (7, 10))\n",
      "Minimum distance: 6.617003\n",
      "New clusters list:\n",
      "[((3, 4), (2, 2), (5, 2), (4, 8), (6, 8), (4, 10), (7, 10)), ((10, 5), (11, 4), (9, 3), (12, 3), (12, 6))]\n",
      "New centroids:\n",
      "[(4.4285714285714288, 6.2857142857142856), (10.800000000000001, 4.2000000000000002)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n",
      "Step 11:\n",
      "Merged clusters: ((3, 4), (2, 2), (5, 2), (4, 8), (6, 8), (4, 10), (7, 10)) and ((10, 5), (11, 4), (9, 3), (12, 3), (12, 6))\n",
      "Minimum distance: 6.704126\n",
      "New clusters list:\n",
      "[((3, 4), (2, 2), (5, 2), (4, 8), (6, 8), (4, 10), (7, 10), (10, 5), (11, 4), (9, 3), (12, 3), (12, 6))]\n",
      "New centroids:\n",
      "[(7.083333333333333, 5.416666666666667)]\n",
      "\n",
      "--------------------------------------------------------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "agg_heap(clusters)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{((3, 4), (2, 2), (5, 2), (4, 8), (6, 8), (4, 10), (7, 10), (10, 5), (11, 4), (9, 3), (12, 3), (12, 6)): [[3, 4], [2, 2], [5, 2], [4, 8], [6, 8], [4, 10], [7, 10], [10, 5], [11, 4], [9, 3], [12, 3], [12, 6]]}\n"
     ]
    }
   ],
   "source": [
    "# only one cluster in clusters remaining: (tup):[cluster]\n",
    "print clusters_remaining"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(clusters_remaining)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{(((10, 5), (11, 4)), ((4, 10),)): [8.5146931829632013, '<removed-cluster>', [[10, 5], [11, 4], [4, 10]]], (((10, 5), (11, 4), (9, 3)), ((7, 10),)): [6.7082039324993694, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [7, 10]]], (((3, 4),), ((11, 4),)): [8.0, '<removed-cluster>', [[3, 4], [11, 4]]], (((4, 8), (6, 8)), ((10, 5), (11, 4))): [6.5192024052026492, '<removed-cluster>', [[4, 8], [6, 8], [10, 5], [11, 4]]], (((3, 4), (2, 2)), ((4, 8), (6, 8))): [5.5901699437494745, '<removed-cluster>', [[3, 4], [2, 2], [4, 8], [6, 8]]], (((7, 10),), ((9, 3),)): [7.2801098892805181, '<removed-cluster>', [[7, 10], [9, 3]]], (((4, 10),), ((4, 8),)): [2.0, '<removed-cluster>', [[4, 10], [4, 8]]], (((3, 4), (2, 2)), ((12, 6),)): [9.9624294225856378, '<removed-cluster>', [[3, 4], [2, 2], [12, 6]]], (((10, 5), (11, 4)), ((12, 6),)): [2.1213203435596424, '<removed-cluster>', [[10, 5], [11, 4], [12, 6]]], (((10, 5), (11, 4), (9, 3)), ((3, 4),)): [7.0, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [3, 4]]], (((5, 2),), ((10, 5),)): [5.8309518948453007, '<removed-cluster>', [[5, 2], [10, 5]]], (((5, 2),), ((12, 3),)): [7.0710678118654755, '<removed-cluster>', [[5, 2], [12, 3]]], (((7, 10),), ((12, 3),)): [8.6023252670426267, '<removed-cluster>', [[7, 10], [12, 3]]], (((3, 4),), ((9, 3),)): [6.0827625302982193, '<removed-cluster>', [[3, 4], [9, 3]]], (((3, 4),), ((12, 6),)): [9.2195444572928871, '<removed-cluster>', [[3, 4], [12, 6]]], (((4, 8),), ((12, 6),)): [8.2462112512353212, '<removed-cluster>', [[4, 8], [12, 6]]], (((4, 8), (6, 8), (4, 10)), ((5, 2),)): [6.674994798166928, '<removed-cluster>', [[4, 8], [6, 8], [4, 10], [5, 2]]], (((12, 6),), ((9, 3),)): [4.2426406871192848, '<removed-cluster>', [[12, 6], [9, 3]]], (((11, 4),), ((12, 3),)): [1.4142135623730951, '<removed-cluster>', [[11, 4], [12, 3]]], (((6, 8),), ((12, 6),)): [6.324555320336759, '<removed-cluster>', [[6, 8], [12, 6]]], (((6, 8),), ((5, 2),)): [6.0827625302982193, '<removed-cluster>', [[6, 8], [5, 2]]], (((4, 8),), ((12, 3),)): [9.4339811320566032, '<removed-cluster>', [[4, 8], [12, 3]]], (((6, 8),), ((10, 5),)): [5.0, '<removed-cluster>', [[6, 8], [10, 5]]], (((10, 5), (11, 4), (9, 3)), ((2, 2),)): [8.2462112512353212, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [2, 2]]], (((4, 8), (6, 8)), ((9, 3),)): [6.4031242374328485, '<removed-cluster>', [[4, 8], [6, 8], [9, 3]]], (((4, 8), (6, 8), (4, 10), (7, 10)), ((10, 5), (11, 4), (9, 3), (12, 3))): [7.4246212024587486, '<removed-cluster>', [[4, 8], [6, 8], [4, 10], [7, 10], [10, 5], [11, 4], [9, 3], [12, 3]]], (((4, 10),), ((5, 2),)): [8.0622577482985491, '<removed-cluster>', [[4, 10], [5, 2]]], (((5, 2),), ((11, 4),)): [6.324555320336759, '<removed-cluster>', [[5, 2], [11, 4]]], (((4, 8),), ((11, 4),)): [8.0622577482985491, '<removed-cluster>', [[4, 8], [11, 4]]], (((2, 2),), ((9, 3),)): [7.0710678118654755, '<removed-cluster>', [[2, 2], [9, 3]]], (((10, 5), (11, 4)), ((7, 10),)): [6.5192024052026492, '<removed-cluster>', [[10, 5], [11, 4], [7, 10]]], (((7, 10),), ((2, 2),)): [9.4339811320566032, '<removed-cluster>', [[7, 10], [2, 2]]], (((3, 4),), ((10, 5),)): [7.0710678118654755, '<removed-cluster>', [[3, 4], [10, 5]]], (((10, 5), (11, 4), (9, 3)), ((4, 10),)): [8.4852813742385695, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [4, 10]]], (((3, 4), (2, 2)), ((7, 10),)): [8.3216584885466194, '<removed-cluster>', [[3, 4], [2, 2], [7, 10]]], (((4, 10),), ((6, 8),)): [2.8284271247461903, '<removed-cluster>', [[4, 10], [6, 8]]], (((4, 8), (6, 8), (4, 10)), ((3, 4), (2, 2))): [6.0667582410670979, '<removed-cluster>', [[4, 8], [6, 8], [4, 10], [3, 4], [2, 2]]], (((3, 4), (2, 2)), ((12, 3),)): [9.5, '<removed-cluster>', [[3, 4], [2, 2], [12, 3]]], (((12, 6),), ((10, 5),)): [2.2360679774997898, '<removed-cluster>', [[12, 6], [10, 5]]], (((10, 5), (11, 4), (9, 3)), ((12, 6),)): [2.8284271247461903, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [12, 6]]], (((4, 10),), ((11, 4),)): [9.2195444572928871, '<removed-cluster>', [[4, 10], [11, 4]]], (((2, 2),), ((11, 4),)): [9.2195444572928871, '<removed-cluster>', [[2, 2], [11, 4]]], (((4, 8),), ((9, 3),)): [7.0710678118654755, '<removed-cluster>', [[4, 8], [9, 3]]], (((5, 2),), ((12, 6),)): [8.0622577482985491, '<removed-cluster>', [[5, 2], [12, 6]]], (((4, 8), (6, 8)), ((12, 6),)): [7.2801098892805181, '<removed-cluster>', [[4, 8], [6, 8], [12, 6]]], (((3, 4), (2, 2)), ((4, 10),)): [7.1589105316381767, '<removed-cluster>', [[3, 4], [2, 2], [4, 10]]], (((7, 10),), ((4, 8),)): [3.6055512754639891, '<removed-cluster>', [[7, 10], [4, 8]]], (((10, 5), (11, 4), (9, 3), (12, 3), (12, 6)), ((4, 8), (6, 8), (4, 10), (7, 10))): [7.3377448851810056, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [12, 3], [12, 6], [4, 8], [6, 8], [4, 10], [7, 10]]], (((4, 10),), ((12, 6),)): [8.9442719099991592, '<removed-cluster>', [[4, 10], [12, 6]]], (((2, 2),), ((12, 6),)): [10.770329614269007, '<removed-cluster>', [[2, 2], [12, 6]]], (((10, 5), (11, 4), (9, 3), (12, 3)), ((4, 8), (6, 8), (4, 10))): [7.6289834767738798, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [12, 3], [4, 8], [6, 8], [4, 10]]], (((2, 2),), ((10, 5),)): [8.5440037453175304, '<removed-cluster>', [[2, 2], [10, 5]]], (((2, 2),), ((5, 2),)): [3.0, '<removed-cluster>', [[2, 2], [5, 2]]], (((4, 8), (6, 8)), ((12, 3),)): [8.6023252670426267, '<removed-cluster>', [[4, 8], [6, 8], [12, 3]]], (((4, 8), (6, 8), (4, 10)), ((12, 6),)): [7.8031332738130823, '<removed-cluster>', [[4, 8], [6, 8], [4, 10], [12, 6]]], (((10, 5), (11, 4), (9, 3)), ((4, 8), (6, 8))): [6.4031242374328485, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [4, 8], [6, 8]]], (((4, 10),), ((3, 4),)): [6.0827625302982193, '<removed-cluster>', [[4, 10], [3, 4]]], (((4, 8),), ((3, 4),)): [4.1231056256176606, '<removed-cluster>', [[4, 8], [3, 4]]], (((4, 8), (6, 8)), ((5, 2),)): [6.0, '<removed-cluster>', [[4, 8], [6, 8], [5, 2]]], (((3, 4),), ((5, 2),)): [2.8284271247461903, '<removed-cluster>', [[3, 4], [5, 2]]], (((4, 10),), ((12, 3),)): [10.63014581273465, '<removed-cluster>', [[4, 10], [12, 3]]], (((4, 10),), ((7, 10),)): [3.0, '<removed-cluster>', [[4, 10], [7, 10]]], (((7, 10),), ((10, 5),)): [5.8309518948453007, '<removed-cluster>', [[7, 10], [10, 5]]], (((4, 10),), ((10, 5),)): [7.810249675906654, '<removed-cluster>', [[4, 10], [10, 5]]], (((10, 5), (11, 4)), ((6, 8),)): [5.7008771254956896, '<removed-cluster>', [[10, 5], [11, 4], [6, 8]]], (((10, 5), (11, 4)), ((2, 2),)): [8.8600225733346747, '<removed-cluster>', [[10, 5], [11, 4], [2, 2]]], (((3, 4), (2, 2), (5, 2)), ((10, 5), (11, 4), (9, 3), (12, 3))): [7.2480840380215108, '<removed-cluster>', [[3, 4], [2, 2], [5, 2], [10, 5], [11, 4], [9, 3], [12, 3]]], (((10, 5), (11, 4), (9, 3), (12, 3), (12, 6)), ((3, 4), (2, 2), (5, 2))): [7.6224813690964321, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [12, 3], [12, 6], [3, 4], [2, 2], [5, 2]]], (((10, 5), (11, 4), (9, 3), (12, 3)), ((7, 10),)): [7.1632743909472012, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [12, 3], [7, 10]]], (((10, 5), (11, 4), (9, 3), (12, 3)), ((3, 4), (2, 2))): [8.0350793399940983, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [12, 3], [3, 4], [2, 2]]], (((3, 4), (2, 2)), ((10, 5), (11, 4), (9, 3))): [7.5663729752107782, '<removed-cluster>', [[3, 4], [2, 2], [10, 5], [11, 4], [9, 3]]], (((9, 3),), ((12, 3),)): [3.0, '<removed-cluster>', [[9, 3], [12, 3]]], (((10, 5), (11, 4)), ((5, 2),)): [6.0415229867972862, '<removed-cluster>', [[10, 5], [11, 4], [5, 2]]], (((4, 8), (6, 8), (4, 10), (7, 10)), ((12, 6),)): [7.3866433513470788, '<removed-cluster>', [[4, 8], [6, 8], [4, 10], [7, 10], [12, 6]]], (((10, 5),), ((9, 3),)): [2.2360679774997898, '<removed-cluster>', [[10, 5], [9, 3]]], (((7, 10),), ((5, 2),)): [8.2462112512353212, '<removed-cluster>', [[7, 10], [5, 2]]], (((7, 10),), ((11, 4),)): [7.2111025509279782, '<removed-cluster>', [[7, 10], [11, 4]]], (((4, 8), (6, 8), (4, 10), (7, 10)), ((5, 2),)): [7.00446286306095, '<removed-cluster>', [[4, 8], [6, 8], [4, 10], [7, 10], [5, 2]]], (((10, 5), (11, 4)), ((4, 8),)): [7.3824115301167001, '<removed-cluster>', [[10, 5], [11, 4], [4, 8]]], (((12, 6),), ((11, 4),)): [2.2360679774997898, '<removed-cluster>', [[12, 6], [11, 4]]], (((10, 5),), ((12, 3),)): [2.8284271247461903, '<removed-cluster>', [[10, 5], [12, 3]]], (((6, 8),), ((11, 4),)): [6.4031242374328485, '<removed-cluster>', [[6, 8], [11, 4]]], (((6, 8),), ((2, 2),)): [7.2111025509279782, '<removed-cluster>', [[6, 8], [2, 2]]], (((4, 8),), ((10, 5),)): [6.7082039324993694, '<removed-cluster>', [[4, 8], [10, 5]]], (((6, 8),), ((12, 3),)): [7.810249675906654, '<removed-cluster>', [[6, 8], [12, 3]]], (((4, 8),), ((5, 2),)): [6.0827625302982193, '<removed-cluster>', [[4, 8], [5, 2]]], (((4, 8), (6, 8)), ((3, 4),)): [4.4721359549995796, '<removed-cluster>', [[4, 8], [6, 8], [3, 4]]], (((7, 10),), ((6, 8),)): [2.2360679774997898, '<removed-cluster>', [[7, 10], [6, 8]]], (((4, 10),), ((9, 3),)): [8.6023252670426267, '<removed-cluster>', [[4, 10], [9, 3]]], (((4, 8),), ((2, 2),)): [6.324555320336759, '<removed-cluster>', [[4, 8], [2, 2]]], (((7, 10),), ((12, 6),)): [6.4031242374328485, '<removed-cluster>', [[7, 10], [12, 6]]], (((6, 8),), ((3, 4),)): [5.0, '<removed-cluster>', [[6, 8], [3, 4]]], (((3, 4),), ((12, 3),)): [9.0553851381374173, '<removed-cluster>', [[3, 4], [12, 3]]], (((10, 5), (11, 4), (9, 3)), ((5, 2),)): [5.3851648071345037, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [5, 2]]], (((12, 6),), ((12, 3),)): [3.0, '<removed-cluster>', [[12, 6], [12, 3]]], (((4, 8), (6, 8)), ((2, 2),)): [6.7082039324993694, '<removed-cluster>', [[4, 8], [6, 8], [2, 2]]], (((10, 5), (11, 4)), ((3, 4),)): [7.5166481891864541, '<removed-cluster>', [[10, 5], [11, 4], [3, 4]]], (((4, 8), (6, 8), (4, 10)), ((10, 5), (11, 4), (9, 3))): [7.0867638751564321, '<removed-cluster>', [[4, 8], [6, 8], [4, 10], [10, 5], [11, 4], [9, 3]]], (((7, 10),), ((3, 4),)): [7.2111025509279782, '<removed-cluster>', [[7, 10], [3, 4]]], (((10, 5), (11, 4), (9, 3), (12, 3)), ((5, 2),)): [5.7716981903075979, '<removed-cluster>', [[10, 5], [11, 4], [9, 3], [12, 3], [5, 2]]], (((10, 5), (11, 4)), ((12, 3),)): [2.1213203435596424, '<removed-cluster>', [[10, 5], [11, 4], [12, 3]]], (((5, 2),), ((9, 3),)): [4.1231056256176606, '<removed-cluster>', [[5, 2], [9, 3]]], (((2, 2),), ((12, 3),)): [10.04987562112089, '<removed-cluster>', [[2, 2], [12, 3]]], (((4, 10),), ((2, 2),)): [8.2462112512353212, '<removed-cluster>', [[4, 10], [2, 2]]], (((11, 4),), ((9, 3),)): [2.2360679774997898, '<removed-cluster>', [[11, 4], [9, 3]]], (((4, 8), (6, 8)), ((7, 10),)): [2.8284271247461903, '<removed-cluster>', [[4, 8], [6, 8], [7, 10]]], (((3, 4), (2, 2), (5, 2)), ((12, 6),)): [9.2855921847894116, '<removed-cluster>', [[3, 4], [2, 2], [5, 2], [12, 6]]], (((4, 8), (6, 8), (4, 10), (7, 10)), ((3, 4), (2, 2))): [6.6001893912220426, '<removed-cluster>', [[4, 8], [6, 8], [4, 10], [7, 10], [3, 4], [2, 2]]], (((4, 8), (6, 8), (4, 10)), ((12, 3),)): [9.2676258496385628, '<removed-cluster>', [[4, 8], [6, 8], [4, 10], [12, 3]]], (((6, 8),), ((9, 3),)): [5.8309518948453007, '<removed-cluster>', [[6, 8], [9, 3]]]}\n"
     ]
    }
   ],
   "source": [
    "# see all the lazy deletions in the cluster_handle dictionary \n",
    "# this was used to to maintain the heap invariant\n",
    "# python priority queues don't support O(log n) deletions\n",
    "# could have done heapify which takes O(n) time but this would have same running time as algorithm above\n",
    "print clusters_handle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K-means clustering Exercises "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<a id='7-3-1'></a>\n",
    "# 7.3.1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 1, 1: 2, 2: 3}"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y ={0:1, 1:2, 2:3}\n",
    "y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from heapq import heappop, heappush"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def selectk(points, k, start=None):\n",
    "    \"\"\"\n",
    "    This function takes points in Euclidean space and selects\n",
    "    k of them as the initial points of a k-means clustering procedure.\n",
    "    The method used is described in Section 7.3.2 in MMDS.\n",
    "    \"\"\"\n",
    "    n = len(points)\n",
    "    if start == None:\n",
    "        start_ix = np.random.randint(0,n-1,size=1)[0]\n",
    "        start = points[start_ix]\n",
    "    else:\n",
    "        start_ix = points.index(start)\n",
    "        \n",
    "    initial_points = {start_ix: start}\n",
    "    points_remaining = {i:point for i,point in enumerate(points)}\n",
    "    del points_remaining[start_ix]\n",
    "    \n",
    "    # calculate distances between each point and store in matrix\n",
    "    # this computes duplicate entries\n",
    "    distances = np.zeros(n**2).reshape(n,n)\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            distances[i,j] = Euclidean(points[i],points[j])\n",
    "    # fix distances diagonal to not be zero\n",
    "    for i in range(n):\n",
    "        distances[i,i] = np.max(distances) + 1\n",
    "            \n",
    "    # selecting remaining points\n",
    "    while len(initial_points) < k:\n",
    "        # store in a maximum heap (i.e., take negative keys in minimum heaps)\n",
    "        candidates = []\n",
    "        for i in points_remaining.keys():\n",
    "            heappush(candidates, (-np.min(distances[i,initial_points.keys()]), i))\n",
    "        #print candidates\n",
    "        # add the largest min distance to initial_points\n",
    "        dist, newpt_ix = heappop(candidates)\n",
    "        initial_points[newpt_ix] = points[newpt_ix]\n",
    "        del points_remaining[newpt_ix]\n",
    "    return initial_points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([6, 4])"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.array([1,2,3,4,5,6,7,8,9]).reshape(3,3)\n",
    "# selecting speicfic columns in an np multidimensional array\n",
    "x[1,[2,0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "points = [[4,10],[7,10],[4,8],[6,8],[3,4],[2,2],[5,2],[10,5],[12,6],[11,4],[9,3],[12,3]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Verifying results in Example 7.8 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{3: [6, 8], 5: [2, 2], 11: [12, 3]}"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "selectk(points, k=3, start=[6,8])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: [4, 10], 5: [2, 2], 7: [10, 5]}"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "selectk(points, k=3, start=[10,5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Answering Exercise 7.3.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: [7, 10], 4: [3, 4], 8: [12, 6]}"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "selectk(points, k=3, start=[3,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<a id='7-3-2'></a>\n",
    "# 7.3.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# the three clusters\n",
    "clus1 = [[4,10],[7,10],[4,8],[6,8]]\n",
    "clus2 = [[3,4],[2,2],[5,2]]\n",
    "clus3 = [[10,5],[9,3],[12,6],[11,4],[12,3]]\n",
    "\n",
    "# calculating the diameters of each cluster\n",
    "diam1 = diameter(clus1)\n",
    "diam2 = diameter(clus2)\n",
    "diam3 = diameter(clus3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3.6055512754639891, 3.0, 4.2426406871192848]"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "diams = [diam1, diam2, diam3]\n",
    "diams"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# calculating minimum intercluster distance\n",
    "icds = [mins(clus1,clus2), mins(clus1,clus3),\n",
    "               mins(clus2,clus3)]\n",
    "\n",
    "min_icd = min(icds) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.1231056256176606"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_icd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4.1231056256176606, 5.0, 4.1231056256176606]"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "icds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='7-3-4'></a>\n",
    "# 7.3.4 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# summary stats for each clusters\n",
    "N1 = len(clus1)\n",
    "N2 = len(clus2)\n",
    "N3 = len(clus3)\n",
    "\n",
    "sum1 = np.sum(clus1,axis=0)\n",
    "sum2 = np.sum(clus2,axis=0)\n",
    "sum3 = np.sum(clus3,axis=0)\n",
    "\n",
    "sumsq1 = np.sum(np.array(clus1)**2,axis=0)\n",
    "sumsq2 = np.sum(np.array(clus2)**2,axis=0)\n",
    "sumsq3 = np.sum(np.array(clus3)**2,axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# variance and sd of each cluster in each dim\n",
    "var1 = (sumsq1 - sum1**2 /N1) / N1\n",
    "var2 = (sumsq2 - sum2**2 /N2) / N2\n",
    "var3 = (sumsq3 - sum3**2 /N3) / N3\n",
    "\n",
    "# sdev\n",
    "sd1 = np.sqrt(var1)\n",
    "sd2 = np.sqrt(var2)\n",
    "sd3 = np.sqrt(var3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[array([ 1.6875,  1.    ]), array([ 1.55555556,  0.88888889]), array([ 1.36,  1.36])]\n",
      "[array([ 1.29903811,  1.        ]), array([ 1.24721913,  0.94280904]), array([ 1.16619038,  1.16619038])]\n"
     ]
    }
   ],
   "source": [
    "print [var1,var2,var3]\n",
    "print [sd1,sd2,sd3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1.6875  1.    ]\n",
      "[ 1.55555556  0.88888889]\n",
      "[ 1.36  1.36]\n"
     ]
    }
   ],
   "source": [
    "# check above calculations using built-in numpy methods\n",
    "print np.var(clus1,axis=0)\n",
    "print np.var(clus2,axis=0)\n",
    "print np.var(clus3,axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1.29903811  1.        ]\n",
      "[ 1.24721913  0.94280904]\n",
      "[ 1.16619038  1.16619038]\n"
     ]
    }
   ],
   "source": [
    "print np.std(clus1,axis=0)\n",
    "print np.std(clus2,axis=0)\n",
    "print np.std(clus3,axis=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='7-3-5'></a>\n",
    "# 7.3.5 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "mahaldist = Euclidean([1/2,-3/3,4/5],[0,0,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.172507018523451"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mahaldist"
   ]
  }
 ],
 "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": 0
}