CLU06-NB01.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": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import print_function # to conform python 2.x print to python 3.x\n",
    "import turicreate\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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Checking whether there is an H2O instance running at http://localhost:54321 ..... not found.\n",
      "Attempting to start a local H2O server...\n",
      "  Java Version: openjdk version \"11.0.9.1\" 2020-11-04; OpenJDK Runtime Environment (build 11.0.9.1+1-Ubuntu-0ubuntu1.20.04); OpenJDK 64-Bit Server VM (build 11.0.9.1+1-Ubuntu-0ubuntu1.20.04, mixed mode, sharing)\n",
      "  Starting server from /home/yomomma/.local/lib/python3.8/site-packages/h2o/backend/bin/h2o.jar\n",
      "  Ice root: /tmp/tmpxs7d2wwy\n",
      "  JVM stdout: /tmp/tmpxs7d2wwy/h2o_yomomma_started_from_python.out\n",
      "  JVM stderr: /tmp/tmpxs7d2wwy/h2o_yomomma_started_from_python.err\n",
      "  Server is running at http://127.0.0.1:54321\n",
      "Connecting to H2O server at http://127.0.0.1:54321 ... successful.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div style=\"overflow:auto\"><table style=\"width:50%\"><tr><td>H2O_cluster_uptime:</td>\n",
       "<td>01 secs</td></tr>\n",
       "<tr><td>H2O_cluster_timezone:</td>\n",
       "<td>America/New_York</td></tr>\n",
       "<tr><td>H2O_data_parsing_timezone:</td>\n",
       "<td>UTC</td></tr>\n",
       "<tr><td>H2O_cluster_version:</td>\n",
       "<td>3.32.0.3</td></tr>\n",
       "<tr><td>H2O_cluster_version_age:</td>\n",
       "<td>1 month and 8 days </td></tr>\n",
       "<tr><td>H2O_cluster_name:</td>\n",
       "<td>H2O_from_python_yomomma_iezhe8</td></tr>\n",
       "<tr><td>H2O_cluster_total_nodes:</td>\n",
       "<td>1</td></tr>\n",
       "<tr><td>H2O_cluster_free_memory:</td>\n",
       "<td>3.877 Gb</td></tr>\n",
       "<tr><td>H2O_cluster_total_cores:</td>\n",
       "<td>8</td></tr>\n",
       "<tr><td>H2O_cluster_allowed_cores:</td>\n",
       "<td>8</td></tr>\n",
       "<tr><td>H2O_cluster_status:</td>\n",
       "<td>accepting new members, healthy</td></tr>\n",
       "<tr><td>H2O_connection_url:</td>\n",
       "<td>http://127.0.0.1:54321</td></tr>\n",
       "<tr><td>H2O_connection_proxy:</td>\n",
       "<td>{\"http\": null, \"https\": null}</td></tr>\n",
       "<tr><td>H2O_internal_security:</td>\n",
       "<td>False</td></tr>\n",
       "<tr><td>H2O_API_Extensions:</td>\n",
       "<td>Amazon S3, XGBoost, Algos, AutoML, Core V3, TargetEncoder, Core V4</td></tr>\n",
       "<tr><td>Python_version:</td>\n",
       "<td>3.8.5 final</td></tr></table></div>"
      ],
      "text/plain": [
       "--------------------------  ------------------------------------------------------------------\n",
       "H2O_cluster_uptime:         01 secs\n",
       "H2O_cluster_timezone:       America/New_York\n",
       "H2O_data_parsing_timezone:  UTC\n",
       "H2O_cluster_version:        3.32.0.3\n",
       "H2O_cluster_version_age:    1 month and 8 days\n",
       "H2O_cluster_name:           H2O_from_python_yomomma_iezhe8\n",
       "H2O_cluster_total_nodes:    1\n",
       "H2O_cluster_free_memory:    3.877 Gb\n",
       "H2O_cluster_total_cores:    8\n",
       "H2O_cluster_allowed_cores:  8\n",
       "H2O_cluster_status:         accepting new members, healthy\n",
       "H2O_connection_url:         http://127.0.0.1:54321\n",
       "H2O_connection_proxy:       {\"http\": null, \"https\": null}\n",
       "H2O_internal_security:      False\n",
       "H2O_API_Extensions:         Amazon S3, XGBoost, Algos, AutoML, Core V3, TargetEncoder, Core V4\n",
       "Python_version:             3.8.5 final\n",
       "--------------------------  ------------------------------------------------------------------"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import h2o\n",
    "h2o.init()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Load the Wikipedia dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "wiki = turicreate.SFrame('people_wiki.sframe/')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we did in previous assignments, let's extract the TF-IDF features:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "wiki['tf_idf'] = turicreate.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": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from em_utilities import sframe_to_scipy # converter\n",
    "\n",
    "# This will take about a minute or two.\n",
    "wiki = wiki.add_row_number()\n",
    "tf_idf, map_word_to_index = 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": 6,
   "metadata": {},
   "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": 7,
   "metadata": {},
   "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 = turicreate.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 2+ minutes 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": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/yomomma/.local/lib/python3.8/site-packages/sklearn/cluster/_kmeans.py:792: FutureWarning: 'n_jobs' was deprecated in version 0.23 and will be removed in 1.0 (renaming of 0.25).\n",
      "  warnings.warn(\"'n_jobs' was deprecated in version 0.23 and will be\"\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3.36 s, sys: 52.2 ms, total: 3.42 s\n",
      "Wall time: 3.41 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "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=1, seed=0)"
   ]
  },
  {
   "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": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'matrix': <30219x547979 sparse matrix of type '<class 'numpy.float64'>'\n",
       " \twith 5282514 stored elements in Compressed Sparse Row format>,\n",
       " 'dataframe': Columns:\n",
       " \tid\tint\n",
       " \tURI\tstr\n",
       " \tname\tstr\n",
       " \ttext\tstr\n",
       " \ttf_idf\tdict\n",
       " \n",
       " Rows: Unknown\n",
       " \n",
       " Data:\n",
       " +----+-------------------------------+-------------------------------+\n",
       " | id |              URI              |              name             |\n",
       " +----+-------------------------------+-------------------------------+\n",
       " | 1  | <http://dbpedia.org/resour... |         Alfred J. Lewy        |\n",
       " | 3  | <http://dbpedia.org/resour... |      Franz Rottensteiner      |\n",
       " | 5  | <http://dbpedia.org/resour... |         Sam Henderson         |\n",
       " | 7  | <http://dbpedia.org/resour... |        Trevor Ferguson        |\n",
       " | 9  | <http://dbpedia.org/resour... |          Cathy Caruth         |\n",
       " | 10 | <http://dbpedia.org/resour... |          Sophie Crumb         |\n",
       " | 11 | <http://dbpedia.org/resour... |         Jenn Ashworth         |\n",
       " | 12 | <http://dbpedia.org/resour... |        Jonathan Hoefler       |\n",
       " | 13 | <http://dbpedia.org/resour... | Anthony Gueterbock, 18th B... |\n",
       " | 14 | <http://dbpedia.org/resour... |       David Chernushenko      |\n",
       " +----+-------------------------------+-------------------------------+\n",
       " +-------------------------------+-------------------------------+\n",
       " |              text             |             tf_idf            |\n",
       " +-------------------------------+-------------------------------+\n",
       " | alfred j lewy aka sandy le... | {'time': 1.325334207420049... |\n",
       " | franz rottensteiner born i... | {'kurdlawitzpreis': 10.986... |\n",
       " | sam henderson born october... | {'asses': 9.60020102810530... |\n",
       " | trevor ferguson aka john f... | {'concordia': 6.2502969408... |\n",
       " | cathy caruth born 1955 is ... | {'2002': 1.875312588782230... |\n",
       " | sophia violet sophie crumb... | {'who': 0.9098952189804214... |\n",
       " | jenn ashworth is an englis... | {'left': 2.191367476812056... |\n",
       " | jonathan hoefler born augu... | {'permanent': 3.9183233888... |\n",
       " | anthony fitzhardinge guete... | {'port': 4.491229833288186... |\n",
       " | david chernushenko born ju... | {'won': 1.3836400683164753... |\n",
       " +-------------------------------+-------------------------------+\n",
       " [? rows x 5 columns]\n",
       " Note: Only the head of the SFrame is printed. This SFrame is lazily evaluated.\n",
       " You can use sf.materialize() to force materialization.,\n",
       " 'centroid': array([4.15457842e-05, 9.83150338e-06, 6.27215886e-05, ...,\n",
       "        0.00000000e+00, 6.81369371e-06, 3.63626164e-06])}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'matrix': <28852x547979 sparse matrix of type '<class 'numpy.float64'>'\n",
       " \twith 5096769 stored elements in Compressed Sparse Row format>,\n",
       " 'dataframe': Columns:\n",
       " \tid\tint\n",
       " \tURI\tstr\n",
       " \tname\tstr\n",
       " \ttext\tstr\n",
       " \ttf_idf\tdict\n",
       " \n",
       " Rows: Unknown\n",
       " \n",
       " Data:\n",
       " +----+-------------------------------+-------------------------------+\n",
       " | id |              URI              |              name             |\n",
       " +----+-------------------------------+-------------------------------+\n",
       " | 0  | <http://dbpedia.org/resour... |         Digby Morrell         |\n",
       " | 2  | <http://dbpedia.org/resour... |         Harpdog Brown         |\n",
       " | 4  | <http://dbpedia.org/resour... |             G-Enka            |\n",
       " | 6  | <http://dbpedia.org/resour... |         Aaron LaCrate         |\n",
       " | 8  | <http://dbpedia.org/resour... |          Grant Nelson         |\n",
       " | 15 | <http://dbpedia.org/resour... |         Joerg Steineck        |\n",
       " | 17 | <http://dbpedia.org/resour... | Paddy Dunne (Gaelic footba... |\n",
       " | 18 | <http://dbpedia.org/resour... |       Alexandros Mouzas       |\n",
       " | 20 | <http://dbpedia.org/resour... |         Chris Batstone        |\n",
       " | 21 | <http://dbpedia.org/resour... |         Ceiron Thomas         |\n",
       " +----+-------------------------------+-------------------------------+\n",
       " +-------------------------------+-------------------------------+\n",
       " |              text             |             tf_idf            |\n",
       " +-------------------------------+-------------------------------+\n",
       " | digby morrell born 10 octo... | {'melbourne': 3.8914310119... |\n",
       " | harpdog brown is a singer ... | {'society': 2.444804726208... |\n",
       " | henry krvits born 30 decem... | {'curtis': 5.2995200328853... |\n",
       " | aaron lacrate is an americ... | {'streamz': 10.98649538922... |\n",
       " | grant nelson born 27 april... | {'heavies': 8.907053847545... |\n",
       " | joerg steineck is a german... | {'gap': 5.531174273867493,... |\n",
       " | paddy dunne was a gaelic f... | {'hall': 2.635356782139039... |\n",
       " | alexandros mouzas born 196... | {'philharmonic': 4.3811974... |\n",
       " | chris batstone was the 200... | {'video': 3.08179147535144... |\n",
       " | ceiron thomas born 23 octo... | {'resulting': 4.6286531227... |\n",
       " +-------------------------------+-------------------------------+\n",
       " [? rows x 5 columns]\n",
       " Note: Only the head of the SFrame is printed. This SFrame is lazily evaluated.\n",
       " You can use sf.materialize() to force materialization.,\n",
       " 'centroid': array([2.55855043e-04, 1.64982802e-04, 1.03192980e-04, ...,\n",
       "        3.34661331e-06, 3.16086940e-06, 0.00000000e+00])}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 13,
   "metadata": {
    "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 range(5):\n",
    "        print('{0}:{1:.3f}'.format(map_index_to_word['category'], 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 range(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": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.021\n",
      "113949:0.015\n",
      "113949:0.013\n",
      "113949:0.012\n",
      "113949:0.010\n",
      "\n",
      "* Kayee Griffin                                      0.97358\n",
      "  kayee frances griffin born 6 february 1950 is an australian politician and former australi\n",
      "  an labor party member of the new south wales legislative council serving\n",
      "* %C3%81ine Hyland                                   0.97370\n",
      "  ine hyland ne donlon is emeritus professor of education and former vicepresident of univer\n",
      "  sity college cork ireland she was born in 1942 in athboy co\n",
      "* Christine Robertson                                0.97373\n",
      "  christine mary robertson born 5 october 1948 is an australian politician and former austra\n",
      "  lian labor party member of the new south wales legislative council serving\n",
      "* Anita Kunz                                         0.97471\n",
      "  anita e kunz oc born 1956 is a canadianborn artist and illustratorkunz has lived in london\n",
      "   new york and toronto contributing to magazines and working\n",
      "* Barry Sullivan (lawyer)                            0.97488\n",
      "  barry sullivan is a chicago lawyer and as of july 1 2009 the cooney conway chair in advoca\n",
      "  cy at loyola university chicago school of law\n",
      "* Margaret Catley-Carlson                            0.97534\n",
      "  margaret catleycarlson oc born 6 october 1942 is a canadian civil servant she was chair an\n",
      "  d is now a patron of the global water partnership\n",
      "* Vanessa Gilmore                                    0.97579\n",
      "  vanessa diane gilmore born october 1956 is a judge on the united states district court for\n",
      "   the southern district of texas she was appointed to\n",
      "* James A. Joseph                                    0.97624\n",
      "  james a joseph born 1935 is an american former diplomatjoseph is professor of the practice\n",
      "   of public policy studies at duke university and founder of\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(left_child, map_word_to_index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.023\n",
      "113949:0.017\n",
      "113949:0.017\n",
      "113949:0.016\n",
      "113949:0.016\n",
      "\n",
      "* Patricia Scott                                     0.97143\n",
      "  patricia scott pat born july 14 1929 is a former pitcher who played in the allamerican gir\n",
      "  ls professional baseball league for parts of four seasons\n",
      "* Madonna (entertainer)                              0.97181\n",
      "  madonna louise ciccone tkoni born august 16 1958 is an american singer songwriter actress \n",
      "  and businesswoman she achieved popularity by pushing the boundaries of lyrical\n",
      "* Janet Jackson                                      0.97257\n",
      "  janet damita jo jackson born may 16 1966 is an american singer songwriter and actress know\n",
      "  n for a series of sonically innovative socially conscious and\n",
      "* Natashia Williams                                  0.97343\n",
      "  natashia williamsblach born august 2 1978 is an american actress and former wonderbra camp\n",
      "  aign model who is perhaps best known for her role as shane\n",
      "* Todd Williams                                      0.97384\n",
      "  todd michael williams born february 13 1971 in syracuse new york is a former major league \n",
      "  baseball relief pitcher he attended east syracuseminoa high school\n",
      "* Marilyn Jenkins                                    0.97430\n",
      "  marilyn a jenkins jenks born september 18 1934 is a former catcher who played in the allam\n",
      "  erican girls professional baseball league listed at 5 ft\n",
      "* Kayla Bashore Smedley                              0.97496\n",
      "  kayla bashore born february 20 1983 in daegu south korea is an american field hockey defen\n",
      "  der and midfielder now living in san diego california she\n",
      "* Cher                                               0.97510\n",
      "  cher r born cherilyn sarkisian may 20 1946 is an american singer actress and television ho\n",
      "  st described as embodying female autonomy in a maledominated industry\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(right_child, map_word_to_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The right cluster consists of athletes and artists (singers and actors/actresses), whereas the left cluster consists of non-athletes and non-artists. 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",
    "         Non-athletes/artists                                Athletes/artists\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/artists` and `non-athletes/artists` clusters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Perform recursive bipartitioning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cluster of athletes and artists"
   ]
  },
  {
   "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": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "non_athletes_artists   = left_child\n",
    "athletes_artists       = 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": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/yomomma/.local/lib/python3.8/site-packages/sklearn/cluster/_kmeans.py:792: FutureWarning: 'n_jobs' was deprecated in version 0.23 and will be removed in 1.0 (renaming of 0.25).\n",
      "  warnings.warn(\"'n_jobs' was deprecated in version 0.23 and will be\"\n"
     ]
    }
   ],
   "source": [
    "# Bipartition the cluster of athletes and artists\n",
    "left_child_athletes_artists, right_child_athletes_artists = bipartition(athletes_artists, maxiter=100, num_runs=6, seed=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The left child cluster mainly consists of athletes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.036\n",
      "113949:0.032\n",
      "113949:0.027\n",
      "113949:0.026\n",
      "113949:0.025\n",
      "\n",
      "* Todd Williams                                      0.95702\n",
      "  todd michael williams born february 13 1971 in syracuse new york is a former major league \n",
      "  baseball relief pitcher he attended east syracuseminoa high school\n",
      "* Gord Sherven                                       0.95840\n",
      "  gordon r sherven born august 21 1963 in gravelbourg saskatchewan and raised in mankota sas\n",
      "  katchewan is a retired canadian professional ice hockey forward who played\n",
      "* Justin Knoedler                                    0.95907\n",
      "  justin joseph knoedler born july 17 1980 in springfield illinois is a former major league \n",
      "  baseball catcherknoedler was originally drafted by the st louis cardinals\n",
      "* Chris Day                                          0.95918\n",
      "  christopher nicholas chris day born 28 july 1975 is an english professional footballer who\n",
      "   plays as a goalkeeper for stevenageday started his career at tottenham\n",
      "* Tony Smith (footballer, born 1957)                 0.95948\n",
      "  anthony tony smith born 20 february 1957 is a former footballer who played as a central de\n",
      "  fender in the football league in the 1970s and\n",
      "* Ashley Prescott                                    0.96017\n",
      "  ashley prescott born 11 september 1972 is a former australian rules footballer he played w\n",
      "  ith the richmond and fremantle football clubs in the afl between\n",
      "* Leslie Lea                                         0.96052\n",
      "  leslie lea born 5 october 1942 in manchester is an english former professional footballer \n",
      "  he played as a midfielderlea began his professional career with blackpool\n",
      "* Tommy Anderson (footballer)                        0.96060\n",
      "  thomas cowan tommy anderson born 24 september 1934 in haddington is a scottish former prof\n",
      "  essional footballer he played as a forward and was noted for\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(left_child_athletes_artists, map_word_to_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On the other hand, the right child cluster consists mainly of artists (singers and actors/actresses):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.033\n",
      "113949:0.031\n",
      "113949:0.026\n",
      "113949:0.026\n",
      "113949:0.021\n",
      "\n",
      "* Madonna (entertainer)                              0.96003\n",
      "  madonna louise ciccone tkoni born august 16 1958 is an american singer songwriter actress \n",
      "  and businesswoman she achieved popularity by pushing the boundaries of lyrical\n",
      "* Janet Jackson                                      0.96110\n",
      "  janet damita jo jackson born may 16 1966 is an american singer songwriter and actress know\n",
      "  n for a series of sonically innovative socially conscious and\n",
      "* Cher                                               0.96531\n",
      "  cher r born cherilyn sarkisian may 20 1946 is an american singer actress and television ho\n",
      "  st described as embodying female autonomy in a maledominated industry\n",
      "* Laura Smith                                        0.96572\n",
      "  laura smith is a canadian folk singersongwriter she is best known for her 1995 single shad\n",
      "  e of your love one of the years biggest hits\n",
      "* Lizzie West                                        0.96669\n",
      "  lizzie west born in brooklyn ny on july 21 1973 is a singersongwriter her music can be des\n",
      "  cribed as a blend of many genres including\n",
      "* Anne Harris (musician)                             0.96681\n",
      "  anne harris is a singer songwriter violinist recording artist and actor based in chicago i\n",
      "  llinois she has independently produced and released four studio albums on\n",
      "* Maggie Smith                                       0.96711\n",
      "  dame margaret natalie maggie smith ch dbe born 28 december 1934 is an english actress she \n",
      "  made her stage debut in 1952 and has had\n",
      "* Natashia Williams                                  0.96715\n",
      "  natashia williamsblach born august 2 1978 is an american actress and former wonderbra camp\n",
      "  aign model who is perhaps best known for her role as shane\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(right_child_athletes_artists, map_word_to_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our hierarchy of clusters now looks like this:\n",
    "```\n",
    "                                           Wikipedia\n",
    "                                               +\n",
    "                                               |\n",
    "                    +--------------------------+--------------------+\n",
    "                    |                                               |\n",
    "                    +                                               +\n",
    "         Non-athletes/artists                                Athletes/artists\n",
    "                                                                    +\n",
    "                                                                    |\n",
    "                                                         +----------+----------+\n",
    "                                                         |                     |\n",
    "                                                         |                     |\n",
    "                                                         +                     |\n",
    "                                                     athletes               artists\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",
    "Both the athletes and artists node can be subdivided more, as each one can be divided into more descriptive professions (singer/actress/painter/director, or baseball/football/basketball, etc.). Let's explore subdividing the athletes cluster further to produce finer child clusters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's give the clusters aliases as well:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "athletes    = left_child_athletes_artists\n",
    "artists     = right_child_athletes_artists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cluster of athletes"
   ]
  },
  {
   "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",
    "Let us bipartition the cluster of athletes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/yomomma/.local/lib/python3.8/site-packages/sklearn/cluster/_kmeans.py:792: FutureWarning: 'n_jobs' was deprecated in version 0.23 and will be removed in 1.0 (renaming of 0.25).\n",
      "  warnings.warn(\"'n_jobs' was deprecated in version 0.23 and will be\"\n"
     ]
    }
   ],
   "source": [
    "left_child_athletes, right_child_athletes = bipartition(athletes, maxiter=100, num_runs=6, seed=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.110\n",
      "113949:0.103\n",
      "113949:0.051\n",
      "113949:0.046\n",
      "113949:0.045\n",
      "\n",
      "* Steve Springer                                     0.89327\n",
      "  steven michael springer born february 11 1961 is an american former professional baseball \n",
      "  player who appeared in major league baseball as a third baseman and\n",
      "* Dave Ford                                          0.89574\n",
      "  david alan ford born december 29 1956 is a former major league baseball pitcher for the ba\n",
      "  ltimore orioles born in cleveland ohio ford attended lincolnwest\n",
      "* Todd Williams                                      0.89823\n",
      "  todd michael williams born february 13 1971 in syracuse new york is a former major league \n",
      "  baseball relief pitcher he attended east syracuseminoa high school\n",
      "* Justin Knoedler                                    0.90084\n",
      "  justin joseph knoedler born july 17 1980 in springfield illinois is a former major league \n",
      "  baseball catcherknoedler was originally drafted by the st louis cardinals\n",
      "* Kevin Nicholson (baseball)                         0.90614\n",
      "  kevin ronald nicholson born march 29 1976 is a canadian baseball shortstop he played part \n",
      "  of the 2000 season for the san diego padres of\n",
      "* Joe Strong                                         0.90645\n",
      "  joseph benjamin strong born september 9 1962 in fairfield california is a former major lea\n",
      "  gue baseball pitcher who played for the florida marlins from 2000\n",
      "* James Baldwin (baseball)                           0.90658\n",
      "  james j baldwin jr born july 15 1971 is a former major league baseball pitcher he batted a\n",
      "  nd threw righthanded in his 11season career he\n",
      "* James Garcia                                       0.90726\n",
      "  james robert garcia born february 3 1980 is an american former professional baseball pitch\n",
      "  er who played in the san francisco giants minor league system as\n",
      "\n",
      "113949:0.030\n",
      "113949:0.030\n",
      "113949:0.029\n",
      "113949:0.026\n",
      "113949:0.024\n",
      "\n",
      "* Gord Sherven                                       0.95829\n",
      "  gordon r sherven born august 21 1963 in gravelbourg saskatchewan and raised in mankota sas\n",
      "  katchewan is a retired canadian professional ice hockey forward who played\n",
      "* Ashley Prescott                                    0.95974\n",
      "  ashley prescott born 11 september 1972 is a former australian rules footballer he played w\n",
      "  ith the richmond and fremantle football clubs in the afl between\n",
      "* Jason Roberts (footballer)                         0.95975\n",
      "  jason andre davis roberts mbe born 25 january 1978 is a former professional footballer and\n",
      "   now a football punditborn in park royal london roberts was\n",
      "* Chris Day                                          0.95977\n",
      "  christopher nicholas chris day born 28 july 1975 is an english professional footballer who\n",
      "   plays as a goalkeeper for stevenageday started his career at tottenham\n",
      "* Sol Campbell                                       0.96051\n",
      "  sulzeer jeremiah sol campbell born 18 september 1974 is a former england international foo\n",
      "  tballer a central defender he had a 19year career playing in the\n",
      "* Todd Curley                                        0.96075\n",
      "  todd curley born 14 january 1973 is a former australian rules footballer who played for co\n",
      "  llingwood and the western bulldogs in the australian football league\n",
      "* Tony Smith (footballer, born 1957)                 0.96134\n",
      "  anthony tony smith born 20 february 1957 is a former footballer who played as a central de\n",
      "  fender in the football league in the 1970s and\n",
      "* Richard Ambrose                                    0.96218\n",
      "  richard ambrose born 10 june 1972 is a former australian rules footballer who played with \n",
      "  the sydney swans in the australian football league afl he\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(left_child_athletes, map_word_to_index)\n",
    "display_single_tf_idf_cluster(right_child_athletes, map_word_to_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz Question**. Which diagram best describes the hierarchy right after splitting the `athletes` cluster? Refer to the quiz form for the diagrams.\n",
    "\n",
    "**A:** \n",
    "1. Athletes\n",
    "  1. Baseballers\n",
    "  1. Non-Baseballers"
   ]
  },
  {
   "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 runners and golfers."
   ]
  },
  {
   "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": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/yomomma/.local/lib/python3.8/site-packages/sklearn/cluster/_kmeans.py:792: FutureWarning: 'n_jobs' was deprecated in version 0.23 and will be removed in 1.0 (renaming of 0.25).\n",
      "  warnings.warn(\"'n_jobs' was deprecated in version 0.23 and will be\"\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 10.4 s, sys: 132 ms, total: 10.5 s\n",
      "Wall time: 10.5 s\n"
     ]
    }
   ],
   "source": [
    "%%time \n",
    "# Bipartition the cluster of non-athletes\n",
    "left_child_non_athletes_artists, right_child_non_athletes_artists = bipartition(non_athletes_artists, maxiter=100, num_runs=3, seed=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.021\n",
      "113949:0.017\n",
      "113949:0.015\n",
      "113949:0.014\n",
      "113949:0.014\n",
      "\n",
      "* Anita Kunz                                         0.97141\n",
      "  anita e kunz oc born 1956 is a canadianborn artist and illustratorkunz has lived in london\n",
      "   new york and toronto contributing to magazines and working\n",
      "* %C3%81ine Hyland                                   0.97487\n",
      "  ine hyland ne donlon is emeritus professor of education and former vicepresident of univer\n",
      "  sity college cork ireland she was born in 1942 in athboy co\n",
      "* Ruth Rosen                                         0.97515\n",
      "  ruth rosen born 1956 is a pioneering historian of gender and society an awardwinning journ\n",
      "  alist and a professor emerita at university of california davisshe is\n",
      "* Catherine Hakim                                    0.97532\n",
      "  catherine hakim born 30 may 1948 is a british sociologist who specialises in womens employ\n",
      "  ment and womens issues she is currently a professorial research fellow\n",
      "* Ren%C3%A9e Fox                                     0.97544\n",
      "  rene c fox a summa cum laude graduate of smith college in 1949 earned her phd in sociology\n",
      "   in 1954 from radcliffe college harvard university\n",
      "* Melba Padilla Maggay                               0.97670\n",
      "  melba padilla maggay is a filipina writer and a social anthropologist she holds a doctorat\n",
      "  e in philippine studies a masteral degree in english literature and\n",
      "* Sandra Harding                                     0.97677\n",
      "  this article is about the american philosopher not the australian sociologist and universi\n",
      "  ty administrator of the same namesandra g harding born 1935 is an american\n",
      "* Archie Brown                                       0.97691\n",
      "  archibald haworth brown cmg fba commonly known as archie brown born 10 may 1938 is a briti\n",
      "  sh political scientist and historian in 2005 he became\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(left_child_non_athletes_artists, map_word_to_index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.030\n",
      "113949:0.027\n",
      "113949:0.027\n",
      "113949:0.025\n",
      "113949:0.023\n",
      "\n",
      "* Kayee Griffin                                      0.95724\n",
      "  kayee frances griffin born 6 february 1950 is an australian politician and former australi\n",
      "  an labor party member of the new south wales legislative council serving\n",
      "* Lucienne Robillard                                 0.96152\n",
      "  lucienne robillard pc born june 16 1945 is a canadian politician and a member of the liber\n",
      "  al party of canada she sat in the house\n",
      "* Marcelle Mersereau                                 0.96243\n",
      "  marcelle mersereau born february 14 1942 in pointeverte new brunswick is a canadian politi\n",
      "  cian a civil servant for most of her career she also served\n",
      "* Maureen Lyster                                     0.96244\n",
      "  maureen anne lyster born 10 september 1943 is an australian politician she was an australi\n",
      "  an labor party member of the victorian legislative assembly from 1985\n",
      "* Carol Skelton                                      0.96349\n",
      "  carol skelton pc born december 12 1945 in biggar saskatchewan is a canadian politician she\n",
      "   is a member of the security intelligence review committee which\n",
      "* Liz Cunningham                                     0.96350\n",
      "  elizabeth anne liz cunningham is an australian politician she was an independent member of\n",
      "   the legislative assembly of queensland from 1995 to 2015 representing the\n",
      "* Doug Lewis                                         0.96353\n",
      "  douglas grinslade doug lewis pc qc born april 17 1938 is a former canadian politician a ch\n",
      "  artered accountant and lawyer by training lewis entered the\n",
      "* David Anderson (British Columbia politician)       0.96379\n",
      "  david a anderson pc oc born august 16 1937 in victoria british columbia is a former canadi\n",
      "  an cabinet minister educated at victoria college in victoria\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(right_child_non_athletes_artists, map_word_to_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The clusters are not as clear, but the left cluster has a tendency to show important female figures, and the right one to show politicians and government officials.\n",
    "\n",
    "Let's divide them further."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "female_figures = left_child_non_athletes_artists\n",
    "politicians_etc = right_child_non_athletes_artists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz Question**. Let us bipartition the clusters `female_figures` and `politicians`. 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=6, seed=1` for consistency of output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/yomomma/.local/lib/python3.8/site-packages/sklearn/cluster/_kmeans.py:792: FutureWarning: 'n_jobs' was deprecated in version 0.23 and will be removed in 1.0 (renaming of 0.25).\n",
      "  warnings.warn(\"'n_jobs' was deprecated in version 0.23 and will be\"\n"
     ]
    }
   ],
   "source": [
    "left_child_female_figures, right_child_female_figures = bipartition(female_figures, maxiter=100, num_runs=6, seed=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.017\n",
      "113949:0.015\n",
      "113949:0.013\n",
      "113949:0.013\n",
      "113949:0.011\n",
      "\n",
      "* Archie Brown                                       0.97612\n",
      "  archibald haworth brown cmg fba commonly known as archie brown born 10 may 1938 is a briti\n",
      "  sh political scientist and historian in 2005 he became\n",
      "* Timothy Luke                                       0.97651\n",
      "  timothy w luke is university distinguished professor of political science in the college o\n",
      "  f liberal arts and human sciences as well as program chair of\n",
      "* Lawrence W. Green                                  0.97701\n",
      "  lawrence w green is best known by health education researchers as the originator of the pr\n",
      "  ecede model and codeveloper of the precedeproceed model which has\n",
      "* Jerry L. Martin                                    0.97726\n",
      "  jerry l martin is chairman emeritus of the american council of trustees and alumni he serv\n",
      "  ed as president of acta from its founding in 1995\n",
      "* Loren Graham                                       0.97799\n",
      "  loren r graham born june 29 1933 in hymera indiana is a noted american historian of scienc\n",
      "  e considered the leading scholar on russian science outside\n",
      "* Robert G. Picard                                   0.97821\n",
      "  robert g picard born 1951 is an american writer and scholarone of the leading academic exp\n",
      "  erts on media businesses and considered the father of the\n",
      "* Robert Bates (political scientist)                 0.97823\n",
      "  robert hinrichs bates born 1942 is an american political scientist he is eaton professor o\n",
      "  f the science of government in the departments of government and\n",
      "* Elijah Anderson                                    0.97857\n",
      "  elijah anderson is an american sociologist he holds the william k lanman jr professorship \n",
      "  in sociology at yale university where he teaches and directs the\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(left_child_female_figures, map_word_to_index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.092\n",
      "113949:0.062\n",
      "113949:0.050\n",
      "113949:0.026\n",
      "113949:0.019\n",
      "\n",
      "* Anita Kunz                                         0.93573\n",
      "  anita e kunz oc born 1956 is a canadianborn artist and illustratorkunz has lived in london\n",
      "   new york and toronto contributing to magazines and working\n",
      "* Maryam Hashemi                                     0.94241\n",
      "  maryam hashemi persian is an iranian painter based in london uk since 2002 she grew up in \n",
      "  tehran and graduated in graphic design from azad\n",
      "* Samella Lewis                                      0.94295\n",
      "  samella sanders lewis born february 27 1924 in new orleans is an africanamerican artist pr\n",
      "  imarily a printmaker and painter author art historian and former educator\n",
      "* Lois Conner                                        0.94702\n",
      "  lois conner born 1951 is an american photographer she is noted particularly for her platin\n",
      "  um print landscapes that she produces with a 7 x 17\n",
      "* Roberta Smith                                      0.94989\n",
      "  roberta smith is an art critic for the new york times and a lecturer on contemporary artbo\n",
      "  rn in new york city and raised in lawrence\n",
      "* Lorraine O'Grady                                   0.95048\n",
      "  lorraine ogrady born 1934 is an american conceptual artist who has worked in the areas of \n",
      "  performance art and photo and video installation her work\n",
      "* Lauren Royal                                       0.95086\n",
      "  lauren royal born march 3 circa 1965 is a book writer from california royal has written bo\n",
      "  th historic and novelistic booksa selfproclaimed angels baseball fan\n",
      "* Barbara T. Smith                                   0.95126\n",
      "  barbara turner smith born 1931 pasadena california is an american artist known for her per\n",
      "  formance work in the late 1960s she studied painting art history\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(right_child_female_figures, map_word_to_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Female Figures\n",
    "  1. Academics (Males)\n",
    "  1. Female Artists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/yomomma/.local/lib/python3.8/site-packages/sklearn/cluster/_kmeans.py:792: FutureWarning: 'n_jobs' was deprecated in version 0.23 and will be removed in 1.0 (renaming of 0.25).\n",
      "  warnings.warn(\"'n_jobs' was deprecated in version 0.23 and will be\"\n"
     ]
    }
   ],
   "source": [
    "left_child_politicians_etc, right_child_politicians_etc = bipartition(politicians_etc, maxiter=100, num_runs=6, seed=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.103\n",
      "113949:0.072\n",
      "113949:0.054\n",
      "113949:0.039\n",
      "113949:0.035\n",
      "\n",
      "* William G. Young                                   0.90773\n",
      "  william glover young born 1940 is a united states federal judge for the district of massac\n",
      "  husetts young was born in huntington new york he attended\n",
      "* George B. Daniels                                  0.90920\n",
      "  george benjamin daniels born 1953 is a united states federal judge for the united states d\n",
      "  istrict court for the southern district of new yorkdaniels was\n",
      "* Barry Sullivan (lawyer)                            0.91213\n",
      "  barry sullivan is a chicago lawyer and as of july 1 2009 the cooney conway chair in advoca\n",
      "  cy at loyola university chicago school of law\n",
      "* James G. Carr                                      0.91469\n",
      "  james g carr born july 7 1940 is a federal district judge for the united states district c\n",
      "  ourt for the northern district of ohiocarr was\n",
      "* Jean Constance Hamilton                            0.91538\n",
      "  jean constance hamilton born 1945 is a senior united states district judge of the united s\n",
      "  tates district court for the eastern district of missouriborn in\n",
      "* Robinson O. Everett                                0.91573\n",
      "  robinson o everett march 18 1928 june 12 2009 was an american lawyer judge and a professor\n",
      "   of law at duke universityeverett was born in\n",
      "* Bernard Bell (attorney)                            0.91683\n",
      "  bernard bell is the associate dean for academic affairs and faculty professor of law and h\n",
      "  erbert hannoch scholar at rutgers school of lawnewark bell received\n",
      "* Pasco Bowman II                                    0.91907\n",
      "  pasco middleton bowman ii born 1933 is a senior federal judge on the united states court o\n",
      "  f appeals for the eighth circuit a former fulbright\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(left_child_politicians_etc, map_word_to_index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113949:0.036\n",
      "113949:0.032\n",
      "113949:0.032\n",
      "113949:0.024\n",
      "113949:0.023\n",
      "\n",
      "* Kayee Griffin                                      0.95325\n",
      "  kayee frances griffin born 6 february 1950 is an australian politician and former australi\n",
      "  an labor party member of the new south wales legislative council serving\n",
      "* Lucienne Robillard                                 0.95664\n",
      "  lucienne robillard pc born june 16 1945 is a canadian politician and a member of the liber\n",
      "  al party of canada she sat in the house\n",
      "* Maureen Lyster                                     0.95771\n",
      "  maureen anne lyster born 10 september 1943 is an australian politician she was an australi\n",
      "  an labor party member of the victorian legislative assembly from 1985\n",
      "* Marcelle Mersereau                                 0.95783\n",
      "  marcelle mersereau born february 14 1942 in pointeverte new brunswick is a canadian politi\n",
      "  cian a civil servant for most of her career she also served\n",
      "* Carol Skelton                                      0.95928\n",
      "  carol skelton pc born december 12 1945 in biggar saskatchewan is a canadian politician she\n",
      "   is a member of the security intelligence review committee which\n",
      "* Margaret Beckett                                   0.95972\n",
      "  dame margaret mary beckett dbe mp born 15 january 1943 is a british labour party politicia\n",
      "  n who has been the member of parliament mp for\n",
      "* Liz Cunningham                                     0.96009\n",
      "  elizabeth anne liz cunningham is an australian politician she was an independent member of\n",
      "   the legislative assembly of queensland from 1995 to 2015 representing the\n",
      "* Monique Landry                                     0.96012\n",
      "  monique landry pc born december 25 1937 is a former canadian politician a physiotherapist \n",
      "  and administrator she was first elected to the canadian house of\n",
      "\n"
     ]
    }
   ],
   "source": [
    "display_single_tf_idf_cluster(right_child_politicians_etc, map_word_to_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Politicians\n",
    "  1. American Lawyers\n",
    "  1. Non-American politicians"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}