Chapter 10 - Learning without Supervision.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:d0a528bc10b3bb6717a054cfee3f7306cf4daa84f567a233c234843c5cfe34dd"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Chapter 10 - Learning without Supervision"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "-- *A Python Course for the Humanities*"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<img src=\"images/cluster.png\" alt=\"cluster\" style=\"width: 280px;\" align=\"right\"/>\n",
      "Something wrong with the image here on my machine.\n",
      "\n",
      "In the previous chapter we have developed a system that on the basis of examples attempts to learn a function to classify new, unseen examples. Not always do we have the luxury of a labeled data set. In fact, most of the time only unlabeled data is available. In unsupervised machine learning, or learning without supervision, we attempt the create systems that detect patterns in our data, such as groupings or clusters. Given a collection of texts, we could for example try to measure the pairwise distances between all texts and given these distances construct a grouping of the texts. Another example of unsupervised learning is the popular method of *Topic Modeling* in which we attempt to find clusters of semantically coherent words that together form a topic. \n",
      "\n",
      "In this chapter we will introduce you to some of the techniques to cluster you data without supervision. As is the case with supervised learning, there are many different approaches to clustering. We will discuss one of the most popular ones: hierachical agglomerative clustering. We will develop a general hierarchical cluster module and implement a number of different cluster procedures. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Hierarchical Clustering"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "All cluster techniques follow a similar procedure. We start with a data set consisting of $n$ different data points. The end state will be a data set with $k$ clusters each consisting of a number of original data points. The cluster procedure iteratively moves through all data points and assigns each data point to a particular cluster. Cluster techniques differ with respect to how the merging of data points happens. In this section we will look at hierarchical clustering, which is a clustering method that builds hierarchies of clusters. Typically hierarchical clustering techniques construct a so-called dendrogram, which has a top or root node covering all other data points. The leaf nodes of the dendrogram, or cluster tree, consists of all original data points. If we think of the original datapoints as singleton clusters, hierarchical clustering is an iterative procedure in which in each iteration two clusters are merged into a new cluster. This process is repeated until we arrive at the root node.\n",
      "\n",
      "At each iteration, the two clusters with the highest similarity combined. The definition of what counts as being similar is what differentiates between the different hierarchical clustering methods. One popular clustering method is **single-linkage clustering**. Mathematically, the single linkage function \u2013 the distance $D(X,Y)$ between clusters $X$ and $Y$ \u2013 is described by the expression\n",
      "\n",
      "$$D(X,Y)=\\min_{x\\in X, y\\in Y} d(x,y),$$\n",
      "\n",
      "where $X$ and $Y$ are any two clusters, and $d(x,y)$ represents the distance between the two data points $x$ and $y$. The two clusters $A$ and $B$ of which $D(A,B)$ is the smallest are merged into a new cluster $C$.\n",
      "\n",
      "Let's have a look at a small example to make this all a little more concrete. The following table presents a data set of apples. Each apple is described according to a number of different features:\n",
      "\n",
      "\n",
      "<table border=\"1\" class=\"dataframe\">\n",
      "  <thead>\n",
      "    <tr style=\"text-align: right;\">\n",
      "      <th></th>\n",
      "      <th>quality</th>\n",
      "      <th>color</th>\n",
      "      <th>firmness</th>\n",
      "      <th>taste</th>\n",
      "    </tr>\n",
      "  </thead>\n",
      "  <tbody>\n",
      "    <tr>\n",
      "      <th>0</th>\n",
      "      <td> bad</td>\n",
      "      <td>    red</td>\n",
      "      <td> firm</td>\n",
      "      <td> sweet</td>\n",
      "    </tr>\n",
      "    <tr>\n",
      "      <th>1</th>\n",
      "      <td> bad</td>\n",
      "      <td>    red</td>\n",
      "      <td> firm</td>\n",
      "      <td> sweet</td>\n",
      "    </tr>\n",
      "    <tr>\n",
      "      <th>2</th>\n",
      "      <td> bad</td>\n",
      "      <td> yellow</td>\n",
      "      <td> firm</td>\n",
      "      <td>  sour</td>\n",
      "    </tr>\n",
      "    <tr>\n",
      "      <th>3</th>\n",
      "      <td> good</td>\n",
      "      <td>    red</td>\n",
      "      <td> soft</td>\n",
      "      <td>  sour</td>\n",
      "    </tr>\n",
      "    <tr>\n",
      "      <th>4</th>\n",
      "      <td> good</td>\n",
      "      <td> yellow</td>\n",
      "      <td> soft</td>\n",
      "      <td> sweet</td>\n",
      "    </tr>\n",
      "    <tr>\n",
      "      <th>5</th>\n",
      "      <td> bad</td>\n",
      "      <td> yellow</td>\n",
      "      <td> firm</td>\n",
      "      <td>  sour</td>\n",
      "    </tr>\n",
      "  </tbody>\n",
      "</table>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To construct clusters from these items, we need have some way to compute the distance or similarity between two items. A very simple distance method would be to take the length of the difference between the feature values of two apples $A$ and $B$:\n",
      "\n",
      "$$ A \\cup B = \\{ x: x \\in A | x \\not\\in B\\} $$\n",
      "\n",
      "Take apple$_0$ and apple$_2$ as an example:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "apple_a = {\"bad\", \"red\", \"firm\", \"sweet\"}\n",
      "apple_b = {\"bad\", \"yellow\", \"firm\", \"sour\"}\n",
      "len(apple_a.difference(apple_b))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can do the same thing for all items to obtain the pairwise distances between all apples:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "apples = [(0, {\"bad\", \"red\", \"firm\", \"sweet\"}), \n",
      "          (1, {\"bad\", \"red\", \"firm\", \"sour\"}),\n",
      "          (2, {\"bad\", \"yellow\", \"firm\", \"sour\"}),\n",
      "          (3, {\"good\", \"red\", \"soft\", \"sour\"}),\n",
      "          (4, {\"good\", \"yellow\", \"soft\", \"sweet\"}),\n",
      "          (5, {\"bad\", \"yellow\", \"firm\", \"sour\"})]\n",
      "\n",
      "n = len(apples)\n",
      "distances = [[0 for i in range(n)] for _ in range(n)]\n",
      "for i in range(n):\n",
      "    for j in range(i):\n",
      "        distance = len(apples[i][1].difference(apples[j][1]))\n",
      "        distances[i][j] = distance\n",
      "        distances[j][i] = distances[i][j]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The result is a distance matrix in which for each combination of items the distance is given:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "distances"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "If you look closely, you'll notice that the upper and lower triangle of the matrix are the same. Now that we have all pairwise distances, we can start clustering the examples. We have to start with merging the two clusters of which the data points are most similar. Can you figure out which clusters are most similar to each other?\n",
      "\n",
      "Indeed, the clusters containing apple$_2$ and apple$_5$. Let's merge these two clusters into a new cluster:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "apples[2] = (6, (apples[2], apples[5]))\n",
      "del apples[5]\n",
      "apples"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We now continue our clustering procedure and again select the two items that are most similar to each other. We see that $D(\\text{apple$_0$}, \\text{apple$_1$}) = 1$. The same holds for $D(\\text{apple$_1$}, \\text{apple$_2$})$ and $D(\\text{apple$_1$}, \\text{apple$_5$})$. In such cases we choose one of these pairs at random. Let's go for the pair of apple$_0$ and apple$_1$ and merge these two into a new cluster:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "apples[0] = (7, (apples[0], apples[1]))\n",
      "del apples[1]\n",
      "apples"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We continue and select the next pair with the shortest distance. This is $D(\\text{apple$_1$}, \\text{apple$_2$})$. Since apple$_1$ is in cluster 7 and apple$_2$ in cluster 6, we now merge cluster 6 and 7:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "apples[0] = (8, (apples[0], apples[1]))\n",
      "del apples[1]\n",
      "apples"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next on our list is the pair of apple$_3$ and apple$_4$:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "apples[1] = (9, (apples[1], apples[2]))\n",
      "del apples[2]\n",
      "apples"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We conclude the clustering procedure by merging the last two clusters:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "apples[0] = (10, (apples[0], apples[1]))\n",
      "del apples[1]\n",
      "apples"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "What does our clustering tell us? We can distinguish two main groups: cluster 8 (consisting of apple$_0$, apple$_1$, apple$_2$ and apple$_5$), and cluster 9 (consisting of apple$_3$ and apple$_4$). These two clusters seem to point out that the quality of the apples is considered on the basis of their firmness and that, apparently, soft apples are considered to be better than hard apples.\n",
      "\n",
      "Hopefully, you will now have a better feeling of hierarchical clustering and what the single linkage method is about. It is about time that we start with our own implementation of the hierarchical clustering algorithm."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Quiz!"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**a)** We will begin with implementing a simple similarity metric, called the **Jaccard Distance**. This metric computes the dissimilarity between two sets by dividing the difference of the sizes of the union and the intersection of two sets by the size of their union:\n",
      "\n",
      "$$d_J(A,B) = 1 - J(A,B) = { { |A \\cup B| - |A \\cap B| } \\over |A \\cup B| }$$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def jaccard_distance(a, b):\n",
      "    # insert your code here\n",
      "\n",
      "# these tests should return True if your code is correct\n",
      "print(jaccard_distance({'a', 'b', 'c'}, {'b', 'c', 'a'}) == 0.0)\n",
      "print(round(jaccard_distance({'a', 'b', 'c'}, {'b', 'c'}), 2) == 0.33)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**b)** Write a function `pairwise_distances` that takes as input a list of examples and some distance function and returns a matrix represented by a nested list which contains all pairwise distances."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def pairwise_distances(X, distance_fn=jaccard_distance):\n",
      "    # insert your code here\n",
      "\n",
      "# these tests should return True if your code is correct\n",
      "X = [{'a', 'f', 'c'}, {'b', 'd', 'a'}, {'a', 'b', 'c'}, {'f', 'b', 'c'}]\n",
      "print(pairwise_distances(X) == [[0,   0.8, 0.5, 0.5],\n",
      "                               [0.8, 0,   0.5, 0.8],\n",
      "                               [0.5, 0.5, 0,   0.5],\n",
      "                               [0.5, 0.8, 0.5, 0  ]])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**c)** Next, we will write a function that takes as input a distance matrix represented as a nested list and returns two indexes $i$ and $j$ corresponding to the two clusters $A, B$ with the smallest distance $D(A, B)$:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from itertools import combinations\n",
      "\n",
      "def smallest_distance(dm):\n",
      "    # insert your code here\n",
      "\n",
      "# these tests should return True if your code is correct\n",
      "distances = [[0, 1, 2, 3, 3, 2],\n",
      "             [1, 0, 1, 2, 4, 1],\n",
      "             [2, 1, 0, 3, 3, 0],\n",
      "             [3, 2, 3, 0, 2, 3],\n",
      "             [3, 4, 3, 2, 0, 3],\n",
      "             [2, 1, 0, 3, 3, 0]]\n",
      "print(smallest_distance(distances) == (2, 5))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "So, we have created a function to compute the distance between two sets, a function to compute the pairwise distances between items given a distance function and a function to extract the indices corresponding to the clusters with the smallest distance. Next, we need to define a data structure to represent the hierarchical tree of clusters. First, we will define a class named `Cluster` which represents a single node in a cluster tree. A `Cluster` consists of a cluster ID, and a list of its child nodes. A `Cluster` object is actually no more than a nested list in Python where each list has a unique ID. We therefore define `Cluster` as a subclass of a `list` object:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Cluster(list):\n",
      "    \"\"\"Represents a Cluster node in a Dendrogram. A Cluster can be\n",
      "    initialized using \n",
      "    \n",
      "    >>> c = Cluster(1)\n",
      "    \n",
      "    to create a cluster leaf node with id=1. You can also initialize \n",
      "    a non-terminal `Cluster` node using\n",
      "    \n",
      "    >>> c = Cluster(3, Cluster(1), Cluster(2))\n",
      "    \n",
      "    where Cluster(1) and Cluster(2) are the children of Cluster(3).\"\"\"\n",
      "        \n",
      "    def __init__(self, id, *children):\n",
      "        self.id = id\n",
      "        super(Cluster, self).__init__(children)\n",
      "        \n",
      "    def __repr__(self):\n",
      "        childstr = \", \".join(str(c) for c in self)\n",
      "        if self:\n",
      "            return '%s(%s, [%s])' % (type(self).__name__, self.id, childstr)\n",
      "        return '%s(%s)' % (type(self).__name__, self.id)\n",
      "    \n",
      "    def __str__(self):\n",
      "        return self.pprint()\n",
      "    \n",
      "    def pprint(self, indent=0):\n",
      "        s = '%s(%s' % (type(self).__name__, self.id)\n",
      "        for child in self:\n",
      "            if child:\n",
      "                s += '\\n' + ' ' * (indent + 2) + child.pprint(indent=indent+2)\n",
      "            else:\n",
      "                s += '\\n' + ' ' * (indent + 2) + '%r' % child\n",
      "        return s + ')'"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We create a new `Cluster` using:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "c1 = Cluster(1)\n",
      "c2 = Cluster(2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To create a non-terminal `Cluster` we initialize a `Cluster` object as follows:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(Cluster(3, c1, c2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Quiz!"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A `ClusterTree` is an object that consists of multiple `Cluster` objects. At initialization, each `Cluster` node obtains an ID within the range 0 to $n$ where $n$ is the number of data points to be clustered. You can also pass a list of labels to the `labels` argument of the constructor, which will then be used as ID's. The class `ClusterTree` is responsible for merging two `Cluster` nodes into a new `Cluster`. Complete the method `merge`. It takes as input two indices $i$ and $j$, corresponding to two `Cluster` objects $C_i$ and $C_j$. These two clusters are merged into a new cluster which takes the original position of cluster $C_i$. Don't forget to remove cluster $C_j$ and initialize the new cluster with an appropriate ID."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class ClusterTree:\n",
      "    \"\"\"A ClusterTree, or Dendrogram consists of one or more\n",
      "    `Cluster` objects. Initialize a `ClusterTree` using\n",
      "    \n",
      "    >>> tree = ClusterTree(n=10)\n",
      "    \n",
      "    where n is the number of original data points to be clustered.\"\"\"\n",
      "    \n",
      "    def __init__(self, n, labels=None):\n",
      "        self._n = n\n",
      "        if labels is None:\n",
      "            labels = range(n)\n",
      "        self._clusters = [Cluster(i) for i in labels]\n",
      "    \n",
      "    def merge(self, i, j):\n",
      "        # insert your code here\n",
      "    \n",
      "    def __str__(self):\n",
      "        return '%s' % self._clusters[0]\n",
      "        \n",
      "# these tests should return True if your code is correct\n",
      "tree = ClusterTree(5)\n",
      "tree.merge(1, 2)\n",
      "print(len(tree._clusters[1]) == 2)\n",
      "print(tree._clusters[1].id == 5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now it's time for the most tricky part of our clustering algorithm: computing the linkage function. We have already implemented a function that extracts the two indices corresponding to the two clusters that are closest to each other. But how do we find the indices of two clusters when they have been merged? One way would be to recursively go through the `ClusterTree` and extract the indices from there. There is however another way which makes it possible to use the same `smallest_distance` function at each iteration of the clustering procedure. As we will see this method is particularly beneficial because it will allow us to implement a number of different linkage functions in a elegant and simple way.\n",
      "\n",
      "Recall that in the single linkage function \u2013 the distance $D(X,Y)$ between clusters $X$ and $Y$ \u2013 is described by the expression\n",
      "\n",
      "$$D(X,Y)=\\min_{x\\in X, y\\in Y} d(x,y),$$\n",
      "\n",
      "where $X$ and $Y$ are any two clusters, and $d(x,y)$ represents the distance between the two data points $x$ and $y$. Since we are only interested in the minimal distance of ${x\\in X, y\\in Y}$, we can store that information directly in our distance matrix. Let's go through an example to show you more clearly what this means.\n",
      "\n",
      "Say we have a distance matrix containing the pairwise distance between 6 clusters:\n",
      "\n",
      "    distances = [[0, 1, 2, 3, 3, 1],\n",
      "                 [ , 0, 1, 2, 4, 1],\n",
      "                 [ ,  , 0, 3, 3, 0],\n",
      "                 [ ,  ,  , 0, 2, 3],\n",
      "                 [ ,  ,  ,  , 0, 3],\n",
      "                 [ ,  ,  ,  ,  , 0]]\n",
      "                 \n",
      "The smallest distance can be found between cluster 2 and cluster 5, which can be obtained using our function `smallest_distance`:\n",
      "\n",
      "    >>> smallest_distance(distances)\n",
      "    (2, 5)\n",
      "    \n",
      "So far we haven't done anything different. Here comes the crucial step. Before we enter the next iteration of our clustering procedure, we update the distance matrix to reflect the minimal distances between all clusters with respect to cluster 2 and cluster 5. For example, we compare cluster 0 to both cluster 2 and cluster 5. The distance between cluster 0 and cluster 2 is 2. The distance between cluster 0 and cluster 5 is 1, which is the smallest. We update the largest distance (between cluster 0 and cluster 2) to 1 to represent the minimal distance between 0 and any of cluster 2 or cluster 5:\n",
      "\n",
      "    distances = [[0, 1, 1, 3, 3, 1],\n",
      "                 [ , 0, 1, 2, 4, 1],\n",
      "                 [ ,  , 0, 3, 3, 0],\n",
      "                 [ ,  ,  , 0, 2, 3],\n",
      "                 [ ,  ,  ,  , 0, 3],\n",
      "                 [ ,  ,  ,  ,  , 0]]\n",
      "                 \n",
      "we do this for all remaining clusters to obtain the following distance matrix:\n",
      "\n",
      "    distances = [[0, 1, 1, 3, 3, 1],\n",
      "                 [ , 0, 1, 2, 4, 1],\n",
      "                 [ ,  , 0, 3, 3, 0],\n",
      "                 [ ,  ,  , 0, 2, 3],\n",
      "                 [ ,  ,  ,  , 0, 3],\n",
      "                 [ ,  ,  ,  ,  , 0]]\n",
      "                 \n",
      "Since all distances between any cluster and the cluster (2, 5) are now stored in both the rows and columns of cluster 2 and 5, we can remove one of them to obtain the following distance matrix.\n",
      "\n",
      "    distances = [[0, 1, 1, 3, 3],\n",
      "                 [ , 0, 1, 2, 4],\n",
      "                 [ ,  , 0, 3, 3],\n",
      "                 [ ,  ,  , 0, 2],\n",
      "                 [ ,  ,  ,  , 0]]\n",
      "                 \n",
      "From here on the same procedure is repeated until there is only one cluster left. So, again we extract the two indices corresponding to the two clusters that are closest to each other. \n",
      "\n",
      "    >>> smallest_distance(distances)\n",
      "    (1, 2)\n",
      "    \n",
      "We update the distance matrix\n",
      "\n",
      "    distances = [[0, 1, 2, 3], \n",
      "                 [ , 0, 3, 3], \n",
      "                 [ ,  , 0, 2], \n",
      "                 [ ,  ,  , 0]]\n",
      "                 \n",
      "and go on with the next iteration."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Quiz!"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**a)** Implement the function called `single_linkage`. It takes as input a distance matrix, and two indices $i$ and $j$ corresponding to the two clusters in the distance matrix that are closest to each other. Update the matrix according to the procedure described above and return the new matrix without row$_j$ and column$_j$."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def single_linkage(dm, i, j):\n",
      "    # insert your code here\n",
      "\n",
      "# these tests should return True if your code is correct\n",
      "\n",
      "distances = [[0, 1, 2, 3, 3, 1],\n",
      "             [1, 0, 1, 2, 4, 1],\n",
      "             [2, 1, 0, 3, 3, 0],\n",
      "             [3, 2, 3, 0, 2, 3],\n",
      "             [3, 4, 3, 2, 0, 3],\n",
      "             [1, 1, 0, 3, 3, 0]]\n",
      "\n",
      "print(single_linkage(distances, 2, 5) == [[0, 1, 1, 3, 3], \n",
      "                                          [1, 0, 1, 2, 4], \n",
      "                                          [1, 1, 0, 3, 3], \n",
      "                                          [3, 2, 3, 0, 2], \n",
      "                                          [3, 4, 3, 2, 0]])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**b)** Great. Now that we have our linkage function in place, we start working on the final piece of the clustering algorithm: the main iterative loop, of which the skeleton is given below. Fill in the missing elements."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def cluster(data_points, labels=None, linkage=single_linkage, distance_fn=jaccard_distance):\n",
      "    # initialize a `ClusterTree` with n=len(data_points)\n",
      "    tree = # insert your code here\n",
      "    # compute the pairwise distances between all data points \n",
      "    # using the provided distance function\n",
      "    dm = # insert your code here\n",
      "    while len(dm) > 1:\n",
      "        # extract the indices of the clusters corresponding to the \n",
      "        # two closest clusters in the distance matrix\n",
      "        i, j = # insert your code here\n",
      "        # update the distance matrix using the provided linkage function\n",
      "        dm = # insert your code here\n",
      "        # merge the two clusters in the ClusterTree:\n",
      "        # insert your code here\n",
      "    return tree\n",
      "\n",
      "# these tests should return True if your code is correct\n",
      "apples = [{\"bad\", \"red\", \"firm\", \"sweet\"}, {\"bad\", \"red\", \"firm\", \"sour\"},\n",
      "          {\"bad\", \"yellow\", \"firm\", \"sour\"}, {\"good\", \"red\", \"soft\", \"sour\"},\n",
      "          {\"good\", \"yellow\", \"soft\", \"sweet\"}, {\"bad\", \"yellow\", \"firm\", \"sour\"}]\n",
      "tree = cluster(apples)\n",
      "print(tree._clusters[0].id == 10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Single linkage is just one of many different clustering strategies in hierarchical clustering. Another important linkage function is **complete linkage**. Complete linkage is very similar to single linkage except that we do not take the minimal distance between two clusters but the maximal distance. The distance $D(X,Y)$ between clusters $X$ and $Y$ \u2014 is described by the following expression\n",
      "\n",
      "$$D(X,Y)= \\max_{x\\in X, y\\in Y} d(x,y)$$\n",
      "\n",
      "where $d(x,y)$ is the distance between elements $x \\in X$ and $y \\in Y$. $X$ and $Y$ are both clusters. \n",
      "\n",
      "The difference between single linkage and complete linkage lies only in the function used to compute the distance of a cluster to all other clusters (i.e. `min` or `max`). We could write a function `complete_linkage` that is almost equal to our `single_linkage` function except for the function to compute the distances. However, this would imply that we repeat quite a bit of code, which is never good practice. Instead, we will make an abstraction over the two linkage functions in the function called `general_linkage`. This function takes the same arguments as our `single_linkage` function plus an argument that specifies the distance function used."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def general_linkage(dm, i, j, distance_fn):\n",
      "    for k in range(len(dm)):\n",
      "        if k != i and k != j:\n",
      "            dm[i][k] = distance = distance_fn(dm[i][k], dm[j][k])\n",
      "            dm[k][i] = distance\n",
      "    dm = [[val for c, val in enumerate(row) if c != j] \n",
      "               for r, row in enumerate(dm) if r != j]\n",
      "    return dm"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This general formulation allows us to redefine the `single_linkage` function as follows:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def single_linkage(dm, i, j):\n",
      "    return general_linkage(dm, i, j, min)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Quiz!"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Implement the complete_linkage function."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def complete_linkage(dm, i, j):\n",
      "    # insert your code here\n",
      "\n",
      "# these tests should return True if your code is correct\n",
      "\n",
      "distances = [[0, 1, 2, 3, 3, 1],\n",
      "             [1, 0, 1, 2, 4, 1],\n",
      "             [2, 1, 0, 3, 3, 0],\n",
      "             [3, 2, 3, 0, 2, 3],\n",
      "             [3, 4, 3, 2, 0, 3],\n",
      "             [1, 1, 0, 3, 3, 0]]\n",
      "\n",
      "complete_linkage(distances, 2, 5) == [[0, 1, 2, 3, 3],\n",
      "                                      [1, 0, 1, 2, 4],\n",
      "                                      [2, 1, 0, 3, 3],\n",
      "                                      [3, 2, 3, 0, 2],\n",
      "                                      [3, 4, 3, 2, 0]]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Practical: Clustering Distances of West-European Languages"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now that we have implemented all functions to perform hierarchical cluster analysis, let's apply the method to a more realistic and more interesting example than clustering apples. Within the family of Indo-European languages we can distinguish multiple sub-families, such as Germanic languages (e.g. German and Dutch) or Romance languages (e.g. French and Italian). In the cell below I listed the first 10 numerals in the variable `numerals` for each of the 10 languages stored in the variable `languages`:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "numerals = [\n",
      "   [\"one\", \"two\", \"three\", \"four\", \"five\", \"six\", \"seven\", \"eight\", \"nine\", \"ten\"],\n",
      "   [\"een\", \"twee\", \"drie\", \"vier\", \"vijf\", \"zes\", \"zeven\", \"acht\", \"negen\", \"tien\"],\n",
      "   [\"ien\", \"twa\", \"trije\", \"fjouwer\", \"fiif\", \"seis\", \"san\", \"acht\", \"njoggen\", \"tsien\"],\n",
      "   [\"eins\", \"zwei\", \"drei\", \"vier\", \"funf\", \"sechs\", \"sieben\", \"acht\", \"neun\", \"zehn\"],\n",
      "   [\"en\", \"to\", \"tre\", \"fire\", \"fem\", \"seks\", \"sju\", \"atte\", \"ni\", \"ti\"],\n",
      "   [\"\u00e9n\", \"to\", \"tre\", \"fire\", \"fem\", \"seks\", \"syv\", \"otte\", \"ni\", \"ti\"],\n",
      "   [\"en\", \"tva\", \"tre\", \"fyra\", \"fem\", \"sex\", \"sju\", \"atta\", \"nio\", \"tio\"],\n",
      "   [\"uno\", \"dos\", \"tres\", \"cuatro\", \"cinco\", \"seis\", \"siete\", \"ocho\", \"nueve\", \"diez\"],\n",
      "   [\"un\", \"deux\", \"trois\", \"quatre\", \"cinq\", \"six\", \"sept\", \"huit\", \"neuf\", \"dix\"],\n",
      "   [\"uno\", \"due\", \"tre\", \"quattro\", \"cinque\", \"sei\", \"sette\", \"otto\", \"nove\", \"dieci\"]]\n",
      "\n",
      "languages = ['English', 'Dutch', 'Frisian', 'German', 'Norwegian', \n",
      "             'Danish', 'Swedish', 'Spanish', 'French', 'Italian']"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We apply hierarchical cluster analysis to investigate whether we can detect some interesting and meaningful groupings of these languages on the basis of their first 10 numerals. \n",
      "\n",
      "We first need to decide how to compute the distance between two languages. One simple way is to take the sum of the distances between each numeral in language $A$ and language $B$. Mathematically, the distance between two languages $A$ and $B$ is described by the following expression:\n",
      "\n",
      "$$ D(A, B) = \\sum^n_{i=1} d(A_i, B_i) $$\n",
      "\n",
      "$A$ and $B$ are two vectors with $n$ items and $d$ is some distance function. How do we compute the distance between two numerals like Dutch *een* and English *one*? There are more appropriate and advanced methods to compute this distance, but for the moment let's make use of the jaccard distance function, we defined above:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "dutch_one = set(list(\"een\"))\n",
      "english_one = set(list(\"one\"))\n",
      "jaccard_distance(dutch_one, english_one)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Quiz!"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**a)** Write a function `summed_jaccard_distance` that takes as input two equally sized lists $A$ and $B$. Return $D(A, B) = \\sum^n_{i=1} d(A_i, B_i)$ where $d$ is the jaccard distance."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def summed_jaccard_distance(A, B):\n",
      "    # insert your code here\n",
      "\n",
      "# these tests should return True if your code is correct\n",
      "print(round(summed_jaccard_distance(numerals[0], numerals[4]), 2) == 5.57)\n",
      "print(round(summed_jaccard_distance(numerals[5], numerals[6]), 2) == 4.8)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**b)** Perform a cluster analysis using single linkage and the summed jaccard distance on the numerals data. Report on your findings."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "solution = # insert your code here\n",
      "print(solution)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**c)** This [website](http://www.zompist.com/numbers.htm) contains a data set with the numbers from 1 to 10 in over 5000 languages. Visit the website and add some other languages (preferably from different language families) to the data set. Run the analyis again and report on you findings."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "---"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "You've reached the end of the chapter. Ignore the code below, it's just here to make the page pretty:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from IPython.core.display import HTML\n",
      "def css_styling():\n",
      "    styles = open(\"styles/custom.css\", \"r\").read()\n",
      "    return HTML(styles)\n",
      "css_styling()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "by Folgert Karsdorp (Meertens Instituut)\n",
      "\n",
      "Licensed under the [GNU Free Documentation License](http://www.gnu.org/copyleft/fdl.html)"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}