07-Textual-Similarity/01-Textual-Similarity.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Textual Similarity\n",
    "\n",
    "This notebook is designed to reproduce several findings from Andrew Piper's article \"Novel Devotions: Conversional Reading, Computational Modeling, and the Modern Novel\" (<i>New Literary History</i> 46.1 (2015), 63-98). See especially Fig 2 (p 72), Fig 4 (p 75), and Table 1 (p 79).\n",
    "\n",
    "Piper has made his research corpus of novels available here: https://figshare.com/articles/txtlab_Novel450/2062002\n",
    "\n",
    "We'll download it with `wget`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "!wget https://ndownloader.figshare.com/files/3686778 -P data/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%%capture\n",
    "!unzip data/3686778 -d data/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bag of Words (BoW) language model\n",
    "\n",
    "Today we'll see our first, admittedly primitive, computational model of language called \"Bag of Words\". This model was very popular in early text analysis, and continues to be used today. In fact, the models that have replaced it are still very difficult to actually interpret, giving the BoW approach a slight advantage if we want to understand why the model makes certain decisions.\n",
    "\n",
    "Getting into the model we'll have to revisit Term Frequency (think `Counter`). We'll then see the Document-Term Matrix (DTM), which we've discusssed briefly before. We'll have to normalize these counts if we want to compare. Then we'll look at the available Python libraries to streamline this process.\n",
    "\n",
    "Once we have our BoW model we can analyze it in a high-dimensional vector space, which gives us more insights into the similarities and clustering of different texts. We'll then get into Piper's analysis.\n",
    "\n",
    "We'll build our model  from scratch with `numpy` and `datascience` libraries before we get into the higher level libraries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "from datascience import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's read in Augustine's *Confessions* text:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "with open('data/Augustine-Confessions.txt') as f:\n",
    "    confessions = f.read()\n",
    "\n",
    "confessions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There should be 13 books, which are fortunately separated by six line breaks:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "confessions_list = confessions.split('\\n'*6)\n",
    "len(confessions_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's peek at the first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "confessions_list[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Term Frequency Revisited\n",
    "\n",
    "We'll remember from last week, that while `split` might be a quick way to get tokens, it's not the most accurate because it doesn't separate punctuation and contractions. We'll use `spacy` again to get tokens."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import spacy\n",
    "nlp = spacy.load('en', parser=False) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "first_book = confessions_list[0]\n",
    "parsed = nlp(first_book)\n",
    "first_token_list = [token.text for token in parsed]\n",
    "first_token_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can use `Counter` to get the term frequency:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "word_freq = Counter(first_token_list)\n",
    "word_freq.most_common(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Challenge\n",
    "\n",
    "Write some code to get the 20 most common words of the second book. How similar are they to those of the first book?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Document-Term Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we plan to compare word frequencies across texts, we could collate these `Counter` dictionaries for each book in `Confessions`. But we don't want to write all that code! There is an easy function that streamlines the process called `CountVectorizer`. We saw it in the first notebook with Moretti, but didn't really explain what it does.\n",
    "\n",
    "Let's look at the docstring:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sklearn.feature_extraction.text import CountVectorizer\n",
    "CountVectorizer?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cool. So we'll create the `CountVectorizer` object, then transform it on our `list` of documents, here that would be the books in Augustine's `Confessions`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "cv = CountVectorizer()\n",
    "dtm = cv.fit_transform(confessions_list)\n",
    "dtm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What's this? A sparse matrix just means that some cells in the table don't have value. Why? Because the vocabulary base is not the same for all the books! Let's try to demonstrate this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# de-sparsify\n",
    "desparse = dtm.toarray()\n",
    "\n",
    "# create labels for columns\n",
    "word_list = cv.get_feature_names()\n",
    "\n",
    "# create a new Table\n",
    "dtm_tb = Table(word_list).with_rows(desparse)\n",
    "dtm_tb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Welcome to the ***Document Term Matrix***. This is a core concept in NLP and text analysis. It's not that complicated!\n",
    "\n",
    "We have columns for each word *in the entire corpus*. Then each *row* is for each *document*. In our case, that's books in *Confessions*. The values are the word count for that word in the corresponding document. Note that there are many 0s, that word just doesn't show up in that document!\n",
    "\n",
    "We can call up frequencies for a given word for each chapter easily, since they are the column names:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dtm_tb['read']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looks to be about 13 counts, one for each book, let's double check!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "len(dtm_tb['read'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Normalization\n",
    "\n",
    "Piper notes:\n",
    "\n",
    "> The words were thus normalized according to their relative importance within the work. [95]\n",
    "\n",
    "Let's get the total number of occurences of each word in the whole text. The key to the code below is `sum(desparse)`, which sums the column for all the books in our matrix:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "toks_tab = Table()\n",
    "toks_tab.append_column(label=\"Word List\", values=word_list)\n",
    "toks_tab.append_column(label=\"Frequency\", values=sum(desparse))  # this sum(desparse) will sum the word count column\n",
    "toks_tab.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cool, but we already know how to do this much faster with `Counter`. Let's take this another step further. In order to make apples-to-apples comparisons across Books, we can normalize our values by dividing each word count by the total number of words in its Book. To do that, we'll need to `sum` on `axis=1`, which means summing the row (number of words in that book), as opposed to summing the column.\n",
    "\n",
    "Once we have the total number of words in that Book, we can get the percentage of words that one particular word accounts for, and we can do that for every word across the matrix!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "row_sums = np.sum(desparse, axis=1)\n",
    "normed = desparse/row_sums[:,None]\n",
    "dtm_tb = Table(word_list).with_rows(normed)\n",
    "dtm_tb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reading the matrix above, we see that the word \"abandoned\" accounts for .0145406% of words in Book 1, and .0277855% of words in Book 2.\n",
    "\n",
    "We can still grab out the normalized frequencies of the word 'read' for each book:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dtm_tb['abandoned']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a variety of reasons we like to remove words like \"the\", \"of\", \"and\", etc. These are refered to as 'stopwords.' As Piper notes in footnote 24:\n",
    "\n",
    "> I removed stop words and only kept those words that appeared in at least sixty percent\n",
    "of the documents (twelve of the twenty parts). [95]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.feature_extraction.stop_words import ENGLISH_STOP_WORDS\n",
    "ENGLISH_STOP_WORDS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since we are using an older translation of Augustine, we have to remove archaic forms of these stopwords as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ye_olde_stop_words = ['thou','thy','thee', 'thine', 'ye', 'hath','hast', 'wilt','aught',\\\n",
    "                      'art', 'dost','doth', 'shall', 'shalt','tis','canst','thyself',\\\n",
    "                     'didst', 'yea', 'wert']\n",
    "\n",
    "stop_words = list(ENGLISH_STOP_WORDS) + ye_olde_stop_words\n",
    "\n",
    "# remove stopwords from column list\n",
    "dtm_tb = dtm_tb.drop(stop_words)\n",
    "\n",
    "# it is often more efficient to perform operations on arrays rather than tables\n",
    "dtm_array = dtm_tb.to_array()\n",
    "dtm_array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Question\n",
    "\n",
    "In the script above, we normalized term frequencies before removing stopwords. However, it would have been just as easy to do those steps in the opposite order. Are there situations where this decision has more or less of an impact on the output?\n",
    "\n",
    "Note: Generally stopwords are removed [*before*](https://github.com/scikit-learn/scikit-learn/blob/ef5cb84a/sklearn/feature_extraction/text.py#L605) counting term frequencies and normalization."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Streamlining"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was a lot of work, if this is such a common task hasn't someone streamlined this? In fact, we can simply instruct `CountVectorizer` not to include stopwords at all and another function, `TfidfTransformer`, normalizes easily."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.feature_extraction.text import TfidfTransformer\n",
    "\n",
    "cv = CountVectorizer(stop_words = stop_words)\n",
    "dtm = cv.fit_transform(confessions_list)\n",
    "tt = TfidfTransformer(norm='l1',use_idf=False)\n",
    "dtm_tf = tt.fit_transform(dtm)\n",
    "\n",
    "word_list = cv.get_feature_names()\n",
    "dtm_array = dtm_tf.toarray()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "> Note: If you are processing a text that uses only contemporary English, it may be unnecessary to import the list of stopwords explicitly. Simply pass the value `\"english\"` into the `\"stop_words\"` argument in `CountVectorizer`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Table(word_list).with_rows(dtm_array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vector Space Model of Language"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">  My question was: how does a vocabulary\n",
    "that runs throughout the majority of a work change over the course of that work? I then\n",
    "calculated the Euclidean distance between each of the twenty parts of the work based on\n",
    "the frequency of the remaining words and stored those results in a symmetrical distance\n",
    "table. [95]\n",
    "\n",
    "Great, now we have a matrix with normalized frequencies of all the words ***in the entire corpus***. Right now our corpus is just all the books in Augustine's *Confessions*.\n",
    "\n",
    "Let's move away from the table and just create a list of 13 vectors with only the normalized frequency values, one for each Book."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dtm_array = dtm_tf.toarray()\n",
    "dtm_array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each vector has a number of coordinates equal to the number of unique words in the corpus. Let's just take Book 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "dtm_array[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One way to measure the similarity of texts, which Piper uses in his article, would be to measure the *Euclidean distance* between their coordinates in space. According to Wikipedia:\n",
    "\n",
    ">The Euclidean distance or Euclidean metric is the \"ordinary\" straight-line distance between two points in Euclidean space\n",
    "\n",
    ">$\\mathrm{d}(\\mathbf{b},\\mathbf{a})=\\sqrt{(a_1-b_1)^2 + (a_2-b_2)^2}$\n",
    "\n",
    "Let's consider a simple 2 dimensional model. We have two point in space:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = (2,6)\n",
    "b = (5,10)\n",
    "\n",
    "euc_dist = np.sqrt( (a[0]-b[0])**2  +  (a[1]-b[1])**2 )\n",
    "euc_dist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can visualize this too:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "plt.scatter([a[0], b[0]], [a[1], b[1]])\n",
    "plt.plot([a[0], b[0]], [a[1], b[1]])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can think of this 2 dimensional distance between 2 points as looking at 2 different texts. In this *very* simple 2-d model though, we only have 2 words in the entire corpus! `(2,6)` and `(5,10)` would be the absolute counts for each text. Imagine:\n",
    "\n",
    "```\n",
    "Document 1:\n",
    "\n",
    "the dog the dog dog dog dog dog\n",
    "\n",
    "Document 2:\n",
    "\n",
    "the dog the dog the dog the dog the dog dog dog dog dog dog\n",
    "\n",
    "```\n",
    "\n",
    "That would yield the comparison above. If we added a third point (document), we could see which 2 documents were closest to one another!\n",
    "\n",
    "---\n",
    "\n",
    "Ok, not too bad, but how do we do this with hundreds or thousands of dimensions (words) acorss hundreds or thousands of points (documents)? Well it actually scales the same way! Here it is for 3 dimensions:\n",
    "\n",
    "$\\mathrm{d}(\\mathbf{b},\\mathbf{a})=\\sqrt{(a_1-b_1)^2 + (a_2-b_2)^2 + (a_3-b_3)^2}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = (2,6,15)\n",
    "b = (5,10,3)\n",
    "\n",
    "euc_dist = np.sqrt( (a[0]-b[0])**2 +  (a[1]-b[1])**2 + (a[2]-b[2])**2 )\n",
    "euc_dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib as mpl\n",
    "from mpl_toolkits.mplot3d import Axes3D\n",
    "\n",
    "mpl.rcParams['legend.fontsize'] = 10\n",
    "\n",
    "fig = plt.figure()\n",
    "ax = fig.gca(projection='3d')\n",
    "ax.scatter([a[0], b[0]], [a[1], b[1]], [a[2], b[2]])\n",
    "ax.plot([a[0], b[0]], [a[1], b[1]], [a[2], b[2]])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We don't have to use our cool formula to calculate this, or to scale it up for *n* dimensions. That's what `scipy` is for:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from scipy.spatial import distance\n",
    "distance.euclidean(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "Another measure of two vectors, more common for text analysis, is called *cosine similarity*. According to Wikipedia:\n",
    "\n",
    ">Cosine similarity is a measure of similarity between two non-zero vectors of an inner product space that measures the cosine of the angle between them. The cosine of 0° is 1, and it is less than 1 for any other angle. It is thus a judgment of orientation and not magnitude: two vectors with the same orientation have a cosine similarity of 1, two vectors at 90° have a similarity of 0, and two vectors diametrically opposed have a similarity of -1, independent of their magnitude.\n",
    "\n",
    ">$\\text{similarity} = \\cos(\\theta) = {\\mathbf{A} \\cdot \\mathbf{B} \\over \\|\\mathbf{A}\\|_2 \\|\\mathbf{B}\\|_2} = \\frac{ \\sum\\limits_{i=1}^{n}{A_i  B_i} }{ \\sqrt{\\sum\\limits_{i=1}^{n}{A_i^2}}  \\sqrt{\\sum\\limits_{i=1}^{n}{B_i^2}} }$\n",
    "\n",
    "Essentially we want to take the cosine of the angle formed between two vectors (documents). We start the vector at the origin and measure the angle between the two vectors we're interested in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "mpl.rcParams['legend.fontsize'] = 10\n",
    "\n",
    "origin = (0,0,0)\n",
    "\n",
    "fig = plt.figure()\n",
    "ax = fig.gca(projection='3d')\n",
    "ax.scatter([a[0], b[0], origin[0]], [a[1], b[1], origin[1]], [a[2], b[2], origin[2]])\n",
    "ax.plot([origin[0], a[0]], [origin[1], a[1]], [origin[2], a[2]])\n",
    "ax.plot([origin[0], b[0]], [origin[1], b[1]], [origin[2], b[2]])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's go back to two dimensions for the vanilla `numpy` calculation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = (2,6)\n",
    "b = (5,10)\n",
    "\n",
    "# don't worry about the formula so much as the intuition behind it: angle between vectors\n",
    "cos_dist = 1 - (a[0]*b[0] + a[1]*b[1]) / ( np.sqrt(a[0]**2 + a[1]**2 ) * np.sqrt(b[0]**2 + b[1]**2 ) )\n",
    "cos_dist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, `scipy` has taken care of this for us too:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "distance.cosine(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the 3-d model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = (2,6,15)\n",
    "b = (5,10,3)\n",
    "distance.cosine(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Challenge\n",
    "\n",
    "Try passing different values into both the euclidean and cosine distance functions. What is your intuition about these different measurements? Remember that all values in the Term-Frequency Matrix are positive, between [0,1], and that most are very small."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Visualizing Texts in Vector Space"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's walk through this now. Say we have 3 texts, `a`, `b`, and `c`. The whole corpus, again, only has 2 words (dimensions)!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = (2,6)\n",
    "b = (5,10)\n",
    "c = (14,11)\n",
    "\n",
    "print(distance.euclidean(a,b))\n",
    "print(distance.euclidean(a,c))\n",
    "print(distance.euclidean(b,c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll make a matrix for the points:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "point_matrix = np.array([a,b,c])\n",
    "point_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can use `sklearn`'s `pairwise_distances` method to compare each book to each book:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.metrics import pairwise\n",
    "pairwise.pairwise_distances(point_matrix, metric='euclidean')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cool! We got what we calculated. Note: the results are mirrored because the columns and rows are both the same texts.\n",
    "\n",
    "We can do the same thing on Augustine's *Confessions*, remember the rows are for each Book too!:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dist_matrix = pairwise.pairwise_distances(dtm_tf, metric='euclidean')\n",
    "\n",
    "title_list = ['Book '+str(i+1) for i in range(len(confessions_list))]\n",
    "Table(title_list).with_rows(dist_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Visualizing hundreds of dimensions is difficult for us. So we can use multi-dimensional scaling (MDS) to put this into a 2-d graph for us:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "from sklearn.manifold import MDS\n",
    "\n",
    "mds = MDS(n_components = 2, dissimilarity=\"precomputed\")\n",
    "embeddings = mds.fit_transform(dist_matrix)\n",
    "\n",
    "_, ax = plt.subplots(figsize=(10,10))\n",
    "ax.scatter(embeddings[:,0], embeddings[:,1], alpha=0)\n",
    "for i in range(13):\n",
    "    ax.annotate(i+1, ((embeddings[i,0], embeddings[i,1])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Homework\n",
    "\n",
    "Try visualizing the textual similarities again using the Cosine distance. How does that change the result? Why?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Brief Aside: K-Means Clustering\n",
    "\n",
    "Tries to find natural groupings among points, once we tell it how many groups to look for."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from sklearn.cluster import KMeans\n",
    "\n",
    "kmeans = KMeans(n_clusters=2)\n",
    "kmeans.fit_predict(dist_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> A standard clustering test such as k-means indicates that the two clusters consist of Books 11–12, with Book 13 being grouped with Books 1–10.) [71]\n",
    "\n",
    "This array (length 13) classifies each book into the `n_clusters` we decide based on their vector similarities. We won't do much more clustering, but just know that it's an ***unsupervised*** machine learning algorithm to classify data. We have to choose how many classes (categories) there are, and the algorithm will decide in which bucket to place the observation.\n",
    "\n",
    "---\n",
    "\n",
    "# The Conversional Novel\n",
    "\n",
    "> The first step was to divide each novel into twenty equal parts. Rather than rely on the\n",
    "irregularity of chapter divisions, which can vary within and between works, this process creates\n",
    "standard units of analysis. [95]\n",
    "\n",
    "Instead of actually using chapter divisions, Piper elects to split each novel into 20 equal parts. We can write a function `text_splitter` that will take in a `str` of the text and return a list of 20 equal parts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def text_splitter(text):\n",
    "    n = int(len(text)/20)  # get length n of each part\n",
    "    text_list = [text[i*n:(i+1)*n] for i in range(20)]  # slice out the text\n",
    "    return(text_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> I then\n",
    "calculated the Euclidean distance between each of the twenty parts of the work based on\n",
    "the frequency of the remaining words and stored those results in a symmetrical distance\n",
    "table. In the end, for each work I had a 20x20 table of distances between every part of\n",
    "a work to every other, in which the distances are considered to be measures of the similarity\n",
    "of the language between a work’s individual parts. [95]\n",
    "\n",
    "Piper then calculates the ***Euclidean*** distances between each part to every other part. So we'll have to calculate the distance and use our `pairwise` method. We can write a function for that too! To make it better, let's have it take in a list of texts that our `text_splitter` will output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def text_distances(text_list):\n",
    "    \n",
    "    from sklearn.feature_extraction.stop_words import ENGLISH_STOP_WORDS\n",
    "    from sklearn.feature_extraction.text import CountVectorizer, TfidfTransformer\n",
    "    from sklearn.metrics import pairwise\n",
    "    \n",
    "    ye_olde_stop_words = ['thou','thy','thee', 'thine', 'ye', 'hath','hast', 'wilt','aught',\\\n",
    "                          'art', 'dost','doth', 'shall', 'shalt','tis','canst','thyself',\\\n",
    "                         'didst', 'yea', 'wert']\n",
    "    stop_words = list(ENGLISH_STOP_WORDS)+ye_olde_stop_words\n",
    "    cv = CountVectorizer(stop_words = stop_words, min_df=0.6)\n",
    "    dtm = cv.fit_transform(text_list)\n",
    "    tt = TfidfTransformer(norm='l1',use_idf=False)\n",
    "    dtm_tf = tt.fit_transform(dtm)\n",
    "    dist_matrix = pairwise.pairwise_distances(dtm_tf, metric='euclidean')\n",
    "    return(dist_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Piper the introduces two new ideas.\n",
    "\n",
    "> for the ***in-half distance*** I took the average distance of each part in the first half of a work to every other part in that half and subtracted it from the average distance of every part of the second half to itself. [95]\n",
    "\n",
    "Let's write a function that does that, and have it take in our matrix returned by `text_distances`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def in_half_dist(matrix):\n",
    "    n = len(matrix)  # length of work, should be 20\n",
    "    d1 = []  # will hold distances for first half\n",
    "    d2 = []  # will hold distances for second half\n",
    "    for i in range(int(n/2)-1):  # loop through first half of work (10 in our case)\n",
    "        for j in range(i+1, int(n/2)):  # loop through itself (first half again)\n",
    "            d1.append(matrix[i,j])  # append distance between one part to another (in first half)\n",
    "    for i in range(int(n/2), n-1):\n",
    "        for j in range(i+1, n):\n",
    "            d2.append(matrix[i,j])\n",
    "    return(abs(sum(d1)-sum(d2))/len(d1))  # take average of each distance array and subtract 2 from 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! And now for his second measure:\n",
    "\n",
    "> For the cross-half distance, I took the average distance between\n",
    "all of the first ten parts of a work to all of the second ten parts of a work, similar to the\n",
    "process used in group average clustering. [95]\n",
    "\n",
    "Let's write another function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cross_half_dist(matrix):\n",
    "    n = len(matrix)  # number of parts, here 20\n",
    "    d = []  # will hold distnaces\n",
    "    for i in range(int(n/2)):  # loop through first half\n",
    "        for j in range(int(n/2), n):  # loop through second half\n",
    "            d.append(matrix[i,j])  # append distance between first and second\n",
    "    return(sum(d)/len(d))  # take average"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Awesome! We can also write ourselves a quick function to call the four functions we just wrote:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def text_measures(text):\n",
    "    text_list = text_splitter(text)\n",
    "    dist_matrix = text_distances(text_list)\n",
    "    return(cross_half_dist(dist_matrix), in_half_dist(dist_matrix))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`text_measures` should now return two values. The first values is the `cross_half_dist` and the second values is the `in_half_dist`. Let's test this out on Augustine's `Confessions':"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "text_measures(confessions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looks good! Now we can read in the corpus Piper used:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "metadata_tb = Table.read_table('data/2_txtlab_Novel450.csv')\n",
    "metadata_tb.show(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll stick with English so we don't have to think about the possible issues of going between languages:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "metadata_tb = metadata_tb.where('language', \"English\")\n",
    "metadata_tb.show(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll slightly change our `text_measures` function so that it can read in the file of the text we want to read in, instead of taking the `confessions` string we already had:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "corpus_path = 'data/2_txtalb_Novel450/'\n",
    "\n",
    "def text_measures_alt(text_name):\n",
    "    with open(corpus_path+text_name, 'r') as file_in:\n",
    "        text = file_in.read()\n",
    "    text_list = text_splitter(text)\n",
    "    dist_matrix = text_distances(text_list)\n",
    "    return(cross_half_dist(dist_matrix), in_half_dist(dist_matrix))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can use `Table`'s `apply` method to call the function `text_measures_alt` on all the files in the corpus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "measures = metadata_tb.apply(text_measures_alt, 'filename')\n",
    "measures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's add these measures to our `Table`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "metadata_tb['Cross-Half'] = measures[:,0]\n",
    "metadata_tb['In-Half'] = measures[:,1]\n",
    "metadata_tb.show(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we want to see which novels stick out, we might be interested in the z-score for a particular novel. This is how many standard devations the novel is away from the mean. Let's write a function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_zscores(values):\n",
    "\n",
    "    import numpy as np\n",
    "    mn = np.mean(values)\n",
    "    st = np.std(values)\n",
    "    zs = []\n",
    "    \n",
    "    for x in values:\n",
    "        z = (x-mn)/st\n",
    "        zs.append(z)\n",
    "\n",
    "    return zs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can add these to the `Table` too:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "metadata_tb['Cross-Z-Score'] = get_zscores(measures[:,0])\n",
    "metadata_tb['In-Z-Score'] = get_zscores(measures[:,1])\n",
    "metadata_tb.show(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scatter plot, please!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "metadata_tb.scatter('In-Half', 'Cross-Half')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Homework\n",
    "\n",
    "Use our z-scores to rank the novels. Which novels are most \"conversional\"?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Piper includes only words that appeared in at least 60% of the book's sections. How might that shape his findings? What if he had used a 50% threshold?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try changing the `min_df` argument to 0.5. How do the rankings change? Try eliminating the `min_df` altogether."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Bonus (not assigned)\n",
    "\n",
    "Visualize distances among the twenty sections of the top-ranked conversional novel in the corpus using the MDS technique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}