6_hierarchical_clustering_blank.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hierarchical Clustering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Hierarchical clustering** refers to a class of clustering methods that seek to build a **hierarchy** of clusters, in which some clusters contain others. In this assignment, we will explore a top-down approach, recursively bipartitioning the data using k-means."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note to Amazon EC2 users**: To conserve memory, make sure to stop all the other notebooks before running this notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Import packages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following code block will check if you have the correct version of GraphLab Create. Any version later than 1.8.5 will do. To upgrade, read [this page](https://turi.com/download/upgrade-graphlab-create.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import graphlab\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import sys\n",
    "import os\n",
    "import time\n",
    "from scipy.sparse import csr_matrix\n",
    "from sklearn.cluster import KMeans\n",
    "from sklearn.metrics import pairwise_distances\n",
    "%matplotlib inline\n",
    "\n",
    "'''Check GraphLab Create version'''\n",
    "from distutils.version import StrictVersion\n",
    "assert (StrictVersion(graphlab.version) >= StrictVersion('1.8.5')), 'GraphLab Create must be version 1.8.5 or later.'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Load the Wikipedia dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "wiki = graphlab.SFrame('people_wiki.gl/')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we did in previous assignments, let's extract the TF-IDF features:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "wiki['tf_idf'] = graphlab.text_analytics.tf_idf(wiki['text'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To run k-means on this dataset, we should convert the data matrix into a sparse matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from em_utilities import sframe_to_scipy # converter\n",
    "\n",
    "# This will take about a minute or two.\n",
    "tf_idf, map_index_to_word = sframe_to_scipy(wiki, 'tf_idf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To be consistent with the k-means assignment, let's normalize all vectors to have unit norm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.preprocessing import normalize\n",
    "tf_idf = normalize(tf_idf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bipartition the Wikipedia dataset using k-means"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall our workflow for clustering text data with k-means:\n",
    "\n",
    "1. Load the dataframe containing a dataset, such as the Wikipedia text dataset.\n",
    "2. Extract the data matrix from the dataframe.\n",
    "3. Run k-means on the data matrix with some value of k.\n",
    "4. Visualize the clustering results using the centroids, cluster assignments, and the original dataframe. We keep the original dataframe around because the data matrix does not keep auxiliary information (in the case of the text dataset, the title of each article).\n",
    "\n",
    "Let us modify the workflow to perform bipartitioning:\n",
    "\n",
    "1. Load the dataframe containing a dataset, such as the Wikipedia text dataset.\n",
    "2. Extract the data matrix from the dataframe.\n",
    "3. Run k-means on the data matrix with k=2.\n",
    "4. Divide the data matrix into two parts using the cluster assignments.\n",
    "5. Divide the dataframe into two parts, again using the cluster assignments. This step is necessary to allow for visualization.\n",
    "6. Visualize the bipartition of data.\n",
    "\n",
    "We'd like to be able to repeat Steps 3-6 multiple times to produce a **hierarchy** of clusters such as the following:\n",
    "```\n",
    "                      (root)\n",
    "                         |\n",
    "            +------------+-------------+\n",
    "            |                          |\n",
    "         Cluster                    Cluster\n",
    "     +------+-----+             +------+-----+\n",
    "     |            |             |            |\n",
    "   Cluster     Cluster       Cluster      Cluster\n",
    "```\n",
    "Each **parent cluster** is bipartitioned to produce two **child clusters**. At the very top is the **root cluster**, which consists of the entire dataset.\n",
    "\n",
    "Now we write a wrapper function to bipartition a given cluster using k-means. There are three variables that together comprise the cluster:\n",
    "\n",
    "* `dataframe`: a subset of the original dataframe that correspond to member rows of the cluster\n",
    "* `matrix`: same set of rows, stored in sparse matrix format\n",
    "* `centroid`: the centroid of the cluster (not applicable for the root cluster)\n",
    "\n",
    "Rather than passing around the three variables separately, we package them into a Python dictionary. The wrapper function takes a single dictionary (representing a parent cluster) and returns two dictionaries (representing the child clusters)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def bipartition(cluster, maxiter=400, num_runs=4, seed=None):\n",
    "    '''cluster: should be a dictionary containing the following keys\n",
    "                * dataframe: original dataframe\n",
    "                * matrix:    same data, in matrix format\n",
    "                * centroid:  centroid for this particular cluster'''\n",
    "    \n",
    "    data_matrix = cluster['matrix']\n",
    "    dataframe   = cluster['dataframe']\n",
    "    \n",
    "    # Run k-means on the data matrix with k=2. We use scikit-learn here to simplify workflow.\n",
    "    kmeans_model = KMeans(n_clusters=2, max_iter=maxiter, n_init=num_runs, random_state=seed, n_jobs=-1)    \n",
    "    kmeans_model.fit(data_matrix)\n",
    "    centroids, cluster_assignment = kmeans_model.cluster_centers_, kmeans_model.labels_\n",
    "    \n",
    "    # Divide the data matrix into two parts using the cluster assignments.\n",
    "    data_matrix_left_child, data_matrix_right_child = data_matrix[cluster_assignment==0], \\\n",
    "                                                      data_matrix[cluster_assignment==1]\n",
    "    \n",
    "    # Divide the dataframe into two parts, again using the cluster assignments.\n",
    "    cluster_assignment_sa = graphlab.SArray(cluster_assignment) # minor format conversion\n",
    "    dataframe_left_child, dataframe_right_child     = dataframe[cluster_assignment_sa==0], \\\n",
    "                                                      dataframe[cluster_assignment_sa==1]\n",
    "        \n",
    "    \n",
    "    # Package relevant variables for the child clusters\n",
    "    cluster_left_child  = {'matrix': data_matrix_left_child,\n",
    "                           'dataframe': dataframe_left_child,\n",
    "                           'centroid': centroids[0]}\n",
    "    cluster_right_child = {'matrix': data_matrix_right_child,\n",
    "                           'dataframe': dataframe_right_child,\n",
    "                           'centroid': centroids[1]}\n",
    "    \n",
    "    return (cluster_left_child, cluster_right_child)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following cell performs bipartitioning of the Wikipedia dataset. Allow 20-60 seconds to finish.\n",
    "\n",
    "Note. For the purpose of the assignment, we set an explicit seed (`seed=1`) to produce identical outputs for every run. In pratical applications, you might want to use different random seeds for all runs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "wiki_data = {'matrix': tf_idf, 'dataframe': wiki} # no 'centroid' for the root cluster\n",
    "left_child, right_child = bipartition(wiki_data, maxiter=100, num_runs=8, seed=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's examine the contents of one of the two clusters, which we call the `left_child`, referring to the tree visualization above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "left_child"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here is the content of the other cluster we named `right_child`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "right_child"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualize the bipartition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We provide you with a modified version of the visualization function from the k-means assignment. For each cluster, we print the top 5 words with highest TF-IDF weights in the centroid and display excerpts for the 8 nearest neighbors of the centroid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def display_single_tf_idf_cluster(cluster, map_index_to_word):\n",
    "    '''map_index_to_word: SFrame specifying the mapping betweeen words and column indices'''\n",
    "    \n",
    "    wiki_subset   = cluster['dataframe']\n",
    "    tf_idf_subset = cluster['matrix']\n",
    "    centroid      = cluster['centroid']\n",
    "    \n",
    "    # Print top 5 words with largest TF-IDF weights in the cluster\n",
    "    idx = centroid.argsort()[::-1]\n",
    "    for i in xrange(5):\n",
    "        print('{0:s}:{1:.3f}'.format(map_index_to_word['category'][idx[i]], centroid[idx[i]])),\n",
    "    print('')\n",
    "    \n",
    "    # Compute distances from the centroid to all data points in the cluster.\n",
    "    distances = pairwise_distances(tf_idf_subset, [centroid], metric='euclidean').flatten()\n",
    "    # compute nearest neighbors of the centroid within the cluster.\n",
    "    nearest_neighbors = distances.argsort()\n",
    "    # For 8 nearest neighbors, print the title as well as first 180 characters of text.\n",
    "    # Wrap the text at 80-character mark.\n",
    "    for i in xrange(8):\n",
    "        text = ' '.join(wiki_subset[nearest_neighbors[i]]['text'].split(None, 25)[0:25])\n",
    "        print('* {0:50s} {1:.5f}\\n  {2:s}\\n  {3:s}'.format(wiki_subset[nearest_neighbors[i]]['name'],\n",
    "              distances[nearest_neighbors[i]], text[:90], text[90:180] if len(text) > 90 else ''))\n",
    "    print('')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's visualize the two child clusters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "display_single_tf_idf_cluster(left_child, map_index_to_word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "display_single_tf_idf_cluster(right_child, map_index_to_word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The left cluster consists of athletes, whereas the right cluster consists of non-athletes. So far, we have a single-level hierarchy consisting of two clusters, as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "                                           Wikipedia\n",
    "                                               +\n",
    "                                               |\n",
    "                    +--------------------------+--------------------+\n",
    "                    |                                               |\n",
    "                    +                                               +\n",
    "                 Athletes                                      Non-athletes\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is this hierarchy good enough? **When building a hierarchy of clusters, we must keep our particular application in mind.** For instance, we might want to build a **directory** for Wikipedia articles. A good directory would let you quickly narrow down your search to a small set of related articles. The categories of athletes and non-athletes are too general to facilitate efficient search. For this reason, we decide to build another level into our hierarchy of clusters with the goal of getting more specific cluster structure at the lower level. To that end, we subdivide both the `athletes` and `non-athletes` clusters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Perform recursive bipartitioning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cluster of athletes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To help identify the clusters we've built so far, let's give them easy-to-read aliases:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "athletes = left_child\n",
    "non_athletes = right_child"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the bipartition function, we produce two child clusters of the athlete cluster:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Bipartition the cluster of athletes\n",
    "left_child_athletes, right_child_athletes = bipartition(athletes, maxiter=100, num_runs=8, seed=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The left child cluster mainly consists of baseball players:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "display_single_tf_idf_cluster(left_child_athletes, map_index_to_word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On the other hand, the right child cluster is a mix of football players and ice hockey players:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "display_single_tf_idf_cluster(right_child_athletes, map_index_to_word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note**. Concerning use of \"football\"\n",
    "\n",
    "The occurrences of the word \"football\" above refer to [association football](https://en.wikipedia.org/wiki/Association_football). This sports is also known as \"soccer\" in United States (to avoid confusion with [American football](https://en.wikipedia.org/wiki/American_football)). We will use \"football\" throughout when discussing topic representation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our hierarchy of clusters now looks like this:\n",
    "```\n",
    "                                           Wikipedia\n",
    "                                               +\n",
    "                                               |\n",
    "                    +--------------------------+--------------------+\n",
    "                    |                                               |\n",
    "                    +                                               +\n",
    "                 Athletes                                      Non-athletes\n",
    "                    +\n",
    "                    |\n",
    "        +-----------+--------+\n",
    "        |                    |\n",
    "        |                    +\n",
    "        +                 football/\n",
    "     baseball            ice hockey\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Should we keep subdividing the clusters? If so, which cluster should we subdivide? To answer this question, we again think about our application. Since we organize our directory by topics, it would be nice to have topics that are about as coarse as each other. For instance, if one cluster is about baseball, we expect some other clusters about football, basketball, volleyball, and so forth. That is, **we would like to achieve similar level of granularity for all clusters.**\n",
    "\n",
    "Notice that the right child cluster is more coarse than the left child cluster. The right cluster posseses a greater variety of topics than the left (ice hockey/football vs. baseball). So the right child cluster should be subdivided further to produce finer child clusters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's give the clusters aliases as well:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "baseball            = left_child_athletes\n",
    "ice_hockey_football = right_child_athletes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cluster of ice hockey players and football players"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In answering the following quiz question, take a look at the topics represented in the top documents (those closest to the centroid), as well as the list of words with highest TF-IDF weights.\n",
    "\n",
    "**Quiz Question**. Bipartition the cluster of ice hockey and football players. Which of the two child clusters should be futher subdivided?\n",
    "\n",
    "**Note**. To achieve consistent results, use the arguments `maxiter=100, num_runs=8, seed=1` when calling the `bipartition` function.\n",
    "\n",
    "1. The left child cluster\n",
    "2. The right child cluster"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Caution**. The granularity criteria is an imperfect heuristic and must be taken with a grain of salt. It takes a lot of manual intervention to obtain a good hierarchy of clusters.\n",
    "\n",
    "* **If a cluster is highly mixed, the top articles and words may not convey the full picture of the cluster.** Thus, we may be misled if we judge the purity of clusters solely by their top documents and words. \n",
    "* **Many interesting topics are hidden somewhere inside the clusters but do not appear in the visualization.** We may need to subdivide further to discover new topics. For instance, subdividing the `ice_hockey_football` cluster led to the appearance of golf."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz Question**. Which diagram best describes the hierarchy right after splitting the `ice_hockey_football` cluster? Refer to the quiz form for the diagrams."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cluster of non-athletes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let us subdivide the cluster of non-athletes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Bipartition the cluster of non-athletes\n",
    "left_child_non_athletes, right_child_non_athletes = bipartition(non_athletes, maxiter=100, num_runs=8, seed=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "display_single_tf_idf_cluster(left_child_non_athletes, map_index_to_word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "display_single_tf_idf_cluster(right_child_non_athletes, map_index_to_word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first cluster consists of scholars, politicians, and government officials whereas the second consists of musicians, artists, and actors. Run the following code cell to make convenient aliases for the clusters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "scholars_politicians_etc = left_child_non_athletes\n",
    "musicians_artists_etc = right_child_non_athletes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz Question**. Let us bipartition the clusters `scholars_politicians_etc` and `musicians_artists_etc`. Which diagram best describes the resulting hierarchy of clusters for the non-athletes? Refer to the quiz for the diagrams.\n",
    "\n",
    "**Note**. Use `maxiter=100, num_runs=8, seed=1` for consistency of output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}