AnalysisPlan.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##1. Specific Aim\n",
    "\n",
    "For the final project I will be applying natural language processing (NLP) techniques to cluster Hillary Clinton's State Department emails into distinct topics or categories. For example, an email specifically discussing the controversial raid on Benghazi would be clustered with similar emails. \n",
    "\n",
    "   ### Data Source\n",
    "    \n",
    "The data used for this project are, former Secretary of State, Hillary Clinton's State Department emails. The emails were originally releases in PDF format but were scraped and posted on Kaggle on September 11, 2015. \n",
    "\n",
    "The data are stored in a SQLite database containing five tables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(u'Emails',), (u'Persons',), (u'Aliases',), (u'EmailReceivers',)]\n"
     ]
    }
   ],
   "source": [
    "import sqlite3\n",
    "import pandas as pd\n",
    "con = sqlite3.connect('input/database.sqlite')\n",
    "cursor = con.cursor()\n",
    "cursor.execute(\"SELECT name FROM sqlite_master WHERE type='table';\")\n",
    "print [x for x in cursor.fetchall()]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Emails\n",
    "  1. This dataframe contains all relevant email information including the email subject, date sent, sender name, and email body.\n",
    "2. Persons\n",
    "  1. This dataframe contains a list of all the sender names with a unique identifier to merge on other tables\n",
    "3. Aliases\n",
    "  1. This dataframe contains a list of sender aliases that correspond to a unique person in the Persons table. \n",
    "4. EmailReceivers\n",
    "  1. This dataframe links an unique email ID with a sender person ID and alias ID."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the purposes of this project, a majority of the analysis will be performed on the **Emails** table which contains the body text of the email."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###Sample Size\n",
    "\n",
    "The emails datasets contains 7,945 emails. However, a portion of these emails are heavily redacted and contain no remaining email text. After we remove emails without text, we are left with 6,742 emails. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(7945, 22)\n",
      "(6742, 22)\n"
     ]
    }
   ],
   "source": [
    "emails_all= pd.read_sql_query(\"Select * From Emails\",con)\n",
    "emails= pd.read_sql_query(\"Select * From Emails where ExtractedBodyText!=''\",con)\n",
    "print emails_all.shape\n",
    "print emails.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###Time Period\n",
    "The emails begin in 2009 and end in 2012."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###Preliminary Hypothesis \n",
    "The analysis I am planning is entirely unsupervised and, as a result, it does lend itself to traditional hypotheses a priori. My plan is to apply the following topic modeling techniques to Hillary Clinton's emails and evaluate/compare the performance:\n",
    "  1. K-Means clustering and\n",
    "  2. Latent-Dirichlet Allocation (**LDA**)\n",
    "  \n",
    "I am not concerned with prediction and would classify the project as an exploration of various clustering/topic modeling techinques rather than a traditional train/test model. Overall, the goal is to understand which of these techniques performs the \"best\" in defining a cluster or topic for a specific email. I put \"best\" in quotes because determining whether a specific topic is appropriate to an email is subjective to my interpretation. However, moving forward I am looking to identify different ways to classify \"best\" in this context.\n",
    "\n",
    "One obvious approach would be to apply some cross-validation techniques to assess the performance of each technique on out-of-sample data. My one concern with this approach is that it would diminish my already small sample size of emails (6,742).\n",
    "\n",
    "Another possible evalution approach, specific to LDA only, would be to put the words associated with each topic through **Word2Vec** in gensim. Then calculate similarity measures between words in a topic to determine whether the topic defined by LDA was \"coherent\".\n",
    "\n",
    "A final approach for evaluation would be performing _word intrusion_ as defined by [Chang et. al](http://www.umiacs.umd.edu/~jbg/docs/nips2009-rtl.pdf). They describe a method where for each trained topic, a word is chosen at random and then substituted into the first ten (or five) word associated with a topic. Then if a human is able to detect which word is not appropriate for that topic it is said that the topic is coherent. My approach would try to take advantage of the **doesnt_match** function in **Word2Vec**, rather than using human judgement. \n",
    "\n",
    "Overall, my expectation is that rather than one clearly superior method, a combination of clustering/topic modeling techniques will need to be used to create the best classifier. For example, it may be the case that LDA is better at identifying emails concerned with _Yoga_ and K-Means is better at identifying emails concerned with _Libya_.\n",
    "  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##2. Methods\n",
    "\n",
    "###Outcome\n",
    "As mentioned above, this is an unsupervised learning approach with no established outcome a priori. None of the emails are categorized into topics before they are run through each of the categorization or topic modeling algorithms.\n",
    "\n",
    "###Predictors\n",
    "The predictor used for each algorithm is some numerical representation of the words in each email, either a **term frequency - inverse document frequency matrix** or a **document-term matrix** . At the beginning, however, each email body is a long string of characters (see below). Notice that each email is formatted differently and in some cases the .PDF scraping was not perfect so there are some extraneous words.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Example Email #1:\n",
      "' What is his email at White House? '\n",
      " \n",
      "Example Email #2:\n",
      "' Secretary Clinton,\n",
      "I hope that all is well back in the States and just wanted to let you know that I will be in Washington\n",
      "Wednesday. If you might have a minute to spare to follow up on your last message in person or by phone this\n",
      "week or over the weekend, I would very much appreciate the opportunity. Congratulations on the Europe\n",
      "trip!\n",
      "Yours sincerely, Jackie\n",
      "Jacqueline Newmyer\n",
      "President, Long Term Strategy Group\n",
      "12 Eliot St., Cambridge, MA 02138\n",
      "617-661-1626 (fax)\n",
      "www.ltstrategy.com '\n"
     ]
    }
   ],
   "source": [
    "print \"Example Email #1:\"\n",
    "print \"'\",emails.ExtractedBodyText[789],\"'\"\n",
    "print \" \"\n",
    "print \"Example Email #2:\"\n",
    "print \"'\",emails.ExtractedBodyText[1234],\"'\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The body of each email will need to cleaned and tokenized in order to run through the various algorithms. At the moment I am still determing whether stemming is a necessary part of the cleaning process. By stemming, I mean reducing words to their root and eliminating any suffixes or prefixes. From my initial work, stemming seems to return strange word results. For example the stemmed version of \"secretary\" is \"secretari\" (see below) or \"house\" is \"hous\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%run ./review_to_words.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Example Email #1: Cleaned\n",
      "email white hous\n",
      " \n",
      "Example Email #2: Cleaned\n",
      "secretari clinton hope well back state want let know washington wednesday might minut spare follow last messag person phone week weekend would much appreci opportun congratul europ trip sincer jacki jacquelin newmyer presid long term strategi group eliot st cambridg ma fax www ltstrategi com\n"
     ]
    }
   ],
   "source": [
    "print \"Example Email #1: Cleaned\"\n",
    "print review_to_words(emails[\"ExtractedBodyText\"][789])\n",
    "print \" \"\n",
    "print \"Example Email #2: Cleaned\"\n",
    "print review_to_words(emails[\"ExtractedBodyText\"][1234])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###Algorithms under consideration\n",
    "\n",
    "I plan to explore the following clustering and topic modeling techniques:\n",
    "  1. K-Means clustering and,\n",
    "  2. Latent-Dirichlet Allocation (**LDA**),\n",
    "  \n",
    "####K-Means Clustering\n",
    "When it comes to unsupervised text analysis and grouping documents or texts together, K-Means Clustering seems to be a very popular approach. Also, since it was one of the very first techniques we learned, it seemed to be a good place to start the exploration of text clustering. \n",
    "\n",
    "To perform the K-Means clustering, each email will need to be transformed into a numerical dataset that the K-Means algorithm can interpret. (Of course, of all this will have to be performed after significant text cleaning.) To accomplish this, all the emails will be represented in a term frequency - inverse document frequency (**tf-idf**) matrix. From my understanding, each column in this tf-idf matrix will represent an email and each row will represent a word. The value for a specific word and email combination is the term frequency multiplied by the inverse document frequency. The term frequency is simply the ratio of the number of occurrences of that word over the total word length of the email. The inverse document frequency is the log of ratio of the total number of emails over the total number of emails containing that word. By multiplying these two values together the tf-idf value assigns greater weight to words that appear frequently in the email but are rare across all emails.\n",
    "\n",
    "Once the words are represented in a numerical dataframe, I will use the  **scikit** **kmeans( )** algorithm to determine the clustering of each email. Note that this algorithm will return a distinct cluster group for each email, or a distinct topic for each email. This is not the case in LDA. \n",
    "\n",
    "####Latent-Dirichlet Allocation\n",
    "\n",
    "The second technique I will be using is Latent-Dirichlet Allocation (LDA). I chose LDA because it was consistently referenced as the most popular technique for topic modeling. Latent Dirichlet is a unsupervised learning technique that defines topics from a set of texts. The number of topics the LDA algorithm defines is set by the user.\n",
    "\n",
    "From my very basic understanding of LDA, to define topics the algorithm makes assumptions on how a document or a piece of text was made and then reverses the process to backout a particular set of topics. LDA assumes that documents, or in our case emails, are written in following steps:\n",
    "\n",
    "1. Determine the number of words the email will have according to some distribution.\n",
    "2. Determine a mixture of K topics to be used in the email. For example, the email may be split between 'Benghazi'(50%),'House Committee' (30%), and 'Election\" (20%). These three topics also have their own distribution of words. For example:\n",
    "  * Benghazi: Qaddaffi (50%) and Libya(50%)\n",
    "  * House Committee: Boehner (50%) and Investigation(50%)\n",
    "  * Election: Polls (50%) and Vote(50%)\n",
    "3. Then to pick each word in the email you:\n",
    "  1. Pick a topic according to the distribution 'Benghazi'(50%),'House Committee' (30%), and 'Election\" (20%).\n",
    "  2. Pick a word from the topic distribution.\n",
    "  \n",
    "The LDA algorithm 'reverses' this process to backout the topic distribution for each email. The algorithm begins by randomly assigning words in each email to a topic. This, of course, assigns topics to words that do not make any sense. The algorithm then reassigns each word a new topic based on the probablity that each topic would generate that specific word.(These calcuations are done interatively and I am still trying to understand how they are calculated). This process is done iteratively with the probability of a specific word for each topic being recalculated each iteration. This is performed many of times until the document reaches a steady state. \n",
    "\n",
    "The LDA algorithm returns a mixture of topics for each email. For example email #1, the text is split 70% between Topic Benghazi and 30% House Committee. Note that this is different from K-Means which returns disjoint clusters.\n",
    "\n",
    "To perform the LDA topic modeling, each email will need to be transformed into a numerical dataset that the LDA algorithm can interpret. To accomplish this, all the emails will be represented in a document-term matrix. The document-term matrix is very simlar the the tf-idf matrix. From my understanding, each column in this matrix will represent an email and each row will represent a word. The value for a specific word and email combination is the frequency of that word.\n",
    "\n",
    "Once this matrix is prepared, the **LdaModel()** function within the **gensim** package will define the number of topics I ask."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Result\n",
    "My expectation is that both methods (K-Means and LDA) will provide distinct benefits and drawbacks. K-Means will be useful in clustering emails that have strictly defined topics, for example emails that only discuss _Benghazi_ or emails that only discuss _Elections_. K-Means will be less useful in clustering emails that contain multiple topics.\n",
    "\n",
    "On the other hand, LDA will be more useful in defining the topics for multi-topic emails. Likewise, it will be less informative in emails that a distinctly one topic."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##4. Limitations and Modeling Assumptions\n",
    "1. Body of emails contains only relevant words or text specific to that email. The scraping that was performed to collect the emails was not perfect, it is very likely that some extraneous words or text slip through data cleaning.For the purposes of this project, it is assumed that all words in a document are relevant.\n",
    "\n",
    "2. All emails are complete. Every single email was reviewed by the State Department before release, and in some cases the emails were redacted. For the purposes of this project, it is assumed that all emails are complete.\n",
    "\n",
    "3. Emails are written using the steps outlined earlier. Without this assumption, the LDA algorithm would not be able to define K topics. This assumption includes other probabilistic assumptions on how topics are picked for an email (i.e. Dirichlet distribution).\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Expected Hurdles\n",
    "I anticipate two major hurdles in completing this project:\n",
    "\n",
    "####Cleaning Data\n",
    "As I have mentioned earlier, these emails were scraped from PDFs and a majority of the email body text is very dirty. I'm still reviewing many raw emails to determine what else I need to clean or edit before running through either algorithm. So far I have identified the following problems and still have no solution:\n",
    "\n",
    "1. A handful of emails list out the schedule of the day. This is a problem as I am currently removing all numeric text from the emails. How can I retain the topic of schedule in the email without keeping the numeric values?\n",
    "2. At the moment, some of the words that are extracted from the emails do not even seem to be English. How do I keep only English words?\n",
    "3. Some emails contain attachments, such as word documents, that are included in the body of the email. For example, the entire text of a specific attachement will be inside the email body. I'm not sure if this is a mistake but I would like to remove this extra text.\n",
    "4. If the email is part of long thread or discussion, how do I extract only the relevant text? How do I identify only the text from that specific email.\n",
    "5. How can I efficiently remove email addresses and/or web addresses?\n",
    "\n",
    "Being able to effectively clean the email body is a crucial step in ensuring that the two algorithms will return useful results. If I use dirty and muddy data with the algorithms, then I can expect to get dirty and muddy results that have litte coherence.\n",
    "####Evaluating Accuracy\n",
    "Since both of these algorithms are unsupervised, evaluating model accuracy is not straight-forward. When it comes to the K-Means algorithm, I understand that there are measures of similarity that can be calculated to evaluate model performance. However, I am struggling with evaluation methods for LDA topic modeling.\n",
    "\n",
    "The only approach I can think of is calculating the LDA topic model on a training set of emails and fitting the model to test set. My concern with this approach is the small sample size of the 6,742 emails. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. Where I Need Help\n",
    "1. What is the best way to determine the number of topics in LDA?\n",
    "2. What is the best way to determine the number of clusters in K-Means?\n",
    "3. Are there other popular topic modeling algorithms that I am not reviewing?\n",
    "4. I am still searching for ways to evaluate the LDA topic modeling algorithm. Any pointers on how to evaluate this algorithm would be greatly appreciated.\n",
    "5. How important is stemming to NLP algorithms?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}